Interpolation polynomiale | EPFL Graph Search

En mathématiques, en analyse numérique, l'interpolation polynomiale est une technique d'interpolation d'un ensemble de données ou d'une fonction par un polynôme. En d'autres termes, étant donné un ensemble de points (obtenu, par exemple, à la suite d'une expérience), on cherche un polynôme qui passe par tous ces points, p(xi) = yi, et éventuellement vérifie d'autres conditions, de degré si possible le plus bas. Cependant, dans le cas de l'interpolation lagrangienne, par exemple, le choix des points d'interpolation est critique. L'interpolation en des points régulièrement espacés peut fort bien diverger même pour des fonctions très régulières (phénomène de Runge). Définition

Dans la version la plus simple (interpolation lagrangienne), on impose simplement que le polynôme passe par tous les points donnés. Étant donné un ensemble de n + 1 points, i.e. couples (xi , yi) (où les réels xi sont distincts 2 à 2, les yi pouvant être des réels, complexes o

MATHICSE Technical Report: Block Krylov subspace methods for functions of matrices II: Modified block FOM

Kathryn Dianne Lund

We analyze an expansion of the generalized block Krylov subspace framework of [Electron.\ Trans.\ Numer.\ Anal., 47 (2017), pp. 100-126]. This expansion allows the use of low-rank modifications of the matrix projected onto the block Krylov subspace and contains, as special cases, the block GMRES method and the new block Radau-Arnoldi method. Within this general setting, we present results that extend the interpolation property from the non-block case to a matrix polynomial interpolation property for the block case, and we relate the eigenvalues of the projected matrix to the latent roots of these matrix polynomials. Some convergence results for these modified block FOM methods for solving linear system are presented. We then show how {\em cospatial} residuals can be preserved in the case of families of shifted linear block systems. This result is used to derive computationally practical restarted algorithms for block Krylov approximations that compute the action of a matrix function on a set of several vectors simultaneously. We prove some convergence results and present numerical results showing that two modifications of FOM, the block harmonic and the block Radau-Arnoldi methods for matrix functions, can significantly improve the convergence behavior.

MATHICSE2019

Geometrical reconstruction of curves and surfaces using NURBS

Sylvain Rouge

The aim of this project is the analysis of different approaches for curve and surface reconstruction and the development of a related MATLAB library. We initially study the Lagrange polynomial interpolation, then the Bezier, the B-splines and the NURBS curves and finally we introduce the NURBS surfaces. At each step we list the useful properties of the different approaches, the details of the mathematical representation and the evolution from simpler to more complicated representations.

2008

Numerical methods for option pricing: polynomial approximation and high dimensionality

Francesco Statti

Options are some of the most traded financial instruments and computing their price is a central task in financial mathematics and in practice. Consequently, the development of numerical algorithms for pricing options is an active field of research. In general, evaluating the price of a specific option relies on the properties of the stochastic model used for the underlying asset price. In this thesis we develop efficient and accurate numerical methods for option pricing in a specific class of models: polynomial models. They are a versatile tool for financial modeling and have useful properties that can be exploited for option pricing. Significant challenges arise when developing option pricing techniques. For instance, the underlying model might have a high-dimensional parameter space. Furthermore, treating multi-asset options yields high-dimensional pricing problems. Therefore, the pricing method should be able to handle high dimensionality. Another important aspect is the efficiency of the algorithm: in real-world applications, option prices need to be delivered within short periods of time, making the algorithmic complexity a potential bottleneck. In this thesis, we address these challenges by developing option pricing techniques that are able to handle low and high-dimensional problems, and we propose complexity reduction techniques. The thesis consists of four parts: First, we present a methodology for European and American option pricing. The method uses the moments of the underlying price process to produce monotone sequences of lower and upper bounds of the option price. The bounds are obtained by solving a sequence of polynomial optimization problems. As the order of the moments increases, the bounds become sharper and eventually converge to the exact price under appropriate assumptions. Second, we develop a fast algorithm for the incremental computation of nested block triangular matrix exponentials. This algorithm allows for an efficient incremental computation of the moment sequence of polynomial jump-diffusions. In other words, moments of order 0, 1, 2, 3... are computed sequentially until a dynamically evaluated criterion tells us to stop. The algorithm is based on the scaling and squaring technique and reduces the complexity of the pricing algorithms that require such an incremental moment computation. Third, we develop a complexity reduction technique for high-dimensional option pricing. To this end, we first consider the option price as a function of model and payoff parameters. Then, the tensorized Chebyshev interpolation is used on the parameter space to increase the efficiency in computing option prices, while maintaining the required accuracy. The high dimensionality of the problem is treated by expressing the tensorized interpolation in the tensor train format and by deriving an efficient way, which is based on tensor completion, to approximate the interpolation coefficients. Lastly, we propose a methodology for pricing single and multi-asset European options. The approach is a combination of Monte Carlo simulation and function approximation. We address the memory limitations that arise when treating very high-dimensional applications by combining the method with optimal sampling strategies and using a randomized algorithm to reduce the storage complexity of the approach. The obtained numerical results show the effectiveness of the algorithms developed in this thesis.

EPFL2019

Numerical methods for option pricing: polynomial approximation and high dimensionality

Francesco Statti

EPFL2019