Quadrature du cercle | EPFL Graph Search

vignette|Le carré de côté a la même aire que le cercle de rayon 1. La quadrature du cercle est un problème classique de mathématiques apparaissant en géométrie. Il fait partie des trois grands problèmes de l'Antiquité, avec la trisection de l'angle et la duplication du cube. Le problème consiste à construire un carré de même aire qu'un disque donné à l'aide d'une règle et d'un compas (voir Nombre constructible). La quadrature du cercle nécessiterait la construction à la règle et au compas de la racine carrée du nombre π, ce qui est impossible en raison de la transcendance de π. Ne sont constructibles que certains nombres algébriques. Ce problème impossible à résoudre a donné naissance à l'expression , qui signifie tenter de résoudre un problème insoluble. De plus, ce problème mathématique est celui qui a résisté le plus longtemps aux mathématiciens. Ils ont mis plus de trois millénaires à étudier le problème, reconnu comme insoluble par Ferdinand von Lindemann en 1882. Histo

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

Square Trisection

Christian Blanvillain, János Pach

A square trisection is a problem of assembling three identical squares from a larger square, using a minimal number of pieces. This paper presents an historical overview of the square trisection problem starting with its origins in the third century. We detail the reasoning behind some of the main known solutions. Finally, we give a new solution and three ruler-and-compass constructions. We conclude with a conjecture of optimality of the proposed solution.

2010

Aggressively Truncated Taylor Series Method For Accurate Computation Of Exponentials Of Essentially Nonnegative Matrices

Meiyue Shao

Small relative perturbations to the entries of an essentially nonnegative matrix introduce small relative errors to entries of its exponential. It is thus desirable to compute the exponential with high componentwise relative accuracy. Taylor series approximation coupled with scaling and squaring is used to compute the exponential of an essentially nonnegative matrix. An a priori componentwise relative error bound of truncation is established, from which one can choose the degree of Taylor series expansion and the scale factor so that the exponential is computed with desired componentwise relative accuracy. To reduce the computational cost, the degree of the Taylor series expansion is chosen small, while the scale factor is chosen sufficiently large to achieve the desired accuracy. The rounding errors in the squaring stage are not serious as squaring is forward stable for nonnegative matrices. We also establish a posteriori componentwise error bounds and derive a novel interval algorithm for the matrix exponential of an essentially nonnegative matrix. Rounding error analysis and numerical experiments demonstrate the efficiency and accuracy of the proposed methods.

Siam Publications2014

Numerical methods for option pricing: polynomial approximation and high dimensionality

Francesco Statti

EPFL2019