abstract: I focus on algorithms that generate good sampling points for function approximation. In 1D, it is well known that polynomial interpolation using equispaced points is unstable. On the other hand, using Chebyshev nodes provides both stable and highly accurate points for polynomial interpolation. In higher dimensional complex regions, optimal sampling points are not known explicitly. This work presents robust algorithms that find good sampling points in complex regions for polynomial interpolation, least-squares, and radial basis function (RBF) methods. The quality of these nodes is measured using the Lebesgue constant. I will also consider optimal sampling for constrained optimization, used to solve PDEs, where boundary conditions must be imposed. Furthermore, I extend the scope of the problem to include finding near-optimal sampling points for high-order finite difference methods. These high-order finite difference methods can be implemented using either piecewise polynomials or RBFs. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2019

[EN] The present PhD thesis is focused on numerical analysis and computing of finite difference schemes for several relevant option pricing models that generalize the Black-Scholes model. A careful analysis of desirable properties for the numerical solutions of option pricing models as the positivity, stability and consistency, is provided. In order to handle the free boundary that arises in American option pricing problems, various transformation techniques based on front-fixing method are applied and studied. Special attention is paid to multi-asset option pricing, such as exchange or spread option. Appropriate transformation allows eliminating of the cross derivative term. Transformation techniques of partial differential equations to remove convection and reaction terms are studied in order to simplify the models and avoid possible troubles of stability. This thesis consists of six chapters. The first chapter is an introduction containing definitions of option and related terms and derivation of the Black-Scholes equation as well as general aspects of theory of finite difference schemes, including preliminaries on numerical analysis. Chapter 2 is devoted to solve linear Black-Scholes model for American put and call options. A Landau transformation and a new front-fixing transformation are applied to the free boundary value problem. It leads to non-linear partial differential equation (PDE) in a fixed domain. Stable and consistent explicit numerical schemes are proposed preserving positivity and monotonicity of the solution in accordance with the behaviour of the exact solution. Efficiency of the front-fixing method demonstrated in Chapter 2 has motivated us to apply the method to some more complicated nonlinear models. A new change of variables resulting in a time dependent boundary instead of fixed one, is applied to nonlinear Black-Scholes model for American options, such as Barles and Soner and Risk Adjusted Pricing models. Chapter 4 provides a new alternative approach for solving American option pricing problem based on rationality of investor. There exists an intensity function that can be reduced in the simplest case to penalty approach. Chapter 5 deals with multi-asset option pricing. Appropriate transformation allows eliminating of the cross derivative term avoiding computational drawbacks and possible troubles of stability. Concluding remarks are given in Chapter 6. All the considered models and numerical methods are accompanied by several examples and simulations. The convergence rate is computed confirming the theoretical study of consistency. Stability conditions are tested by numerical examples. Results are compared with known relevant methods in the literature showing efficiency of the proposed methods. / [ES] La presente tesis doctoral se centra en la construcción de esquemas en diferencias finitas y el análisis numérico de relevantes modelos de valoración de opciones que generalizan el modelo de Black-Scholes. Se proporciona un análisis cuidadoso de las propiedades de las soluciones numéricas tales como la positividad, la estabilidad y la consistencia. Con el fin de manejar la frontera libre que surge en los problemas de valoración de opciones Americanas, se aplican y se estudian diversas técnicas de transformación basadas en el método de fijación de las fronteras (front-fixing). Se presta especial atención a la valoración de opciones de múltiples activos, como son las opciones ''exchange'' y ''spread''. Esta tesis se compone de seis capítulos. El primer capítulo es una introducción que contiene las definiciones de opción y términos relacionados y la derivación de la ecuación de Black-Scholes, así como aspectos generales de la teoría de los esquemas en diferencias finitas, incluyendo preliminares de análisis numérico. El capítulo 2 está dedicado a resolver el modelo lineal de Black-Scholes para opciones Americanas put y call. Para fijar las fronteras del problema de frontera libre se aplican transformaciones como la de Landau y un nuevo cambio de variable propuesto. La eficiencia del método front-fixing mostrada en el capítulo 2 ha motivado el estudio de su aplicación a algunos modelos no lineales más complicados. En particular, se propone un cambio de variables que lleva a una nueva frontera dependiente del tiempo en lugar de una fija. Este cambio se aplica a modelos no lineales de Black-Scholes para opciones Americanas, como son el de Barles y Soner y el modelo RAPM (Risk Adjusted Pricing Methodology). El capítulo 4 ofrece una nueva técnica para la resolución de problemas de valoración de opciones Americanas basada en la racionalidad de los inversores. Aparece una función de la intensidad que se puede reducir en el caso más simple a la técnica de penalización (penalty method). Este enfoque tiene en cuenta el posible comportamiento irracional de los inversores. En la sección 4.2 se aplica esta técnica al modelo de cambio de regímenes lo que lleva a un nuevo modelo que tiene en cuenta el posible ejercicio irracional, así como varios estados del mercado. El enfoque del parámetro de racionalidad junto con una transformación logarítmica permiten construir un esquema numérico eficiente sin aplicar el método front-fixing o la conocida formulación de LCP (Linear Complementarity Problem). El capítulo 5 se dedica a la valoración de opciones de activos múltiples. Una transformación apropiada permite la eliminación del término de derivadas cruzadas evitando inconvenientes computacionales y posibles problemas de estabilidad. Las conclusiones se muestran en el capítulo 6. Se pone en relieve varios aspectos de la presente tesis. Todos los modelos considerados y los métodos numéricos van acompañados de varios ejemplos y simulaciones. Se estudia la convergencia numérica que confirma el estudio teórico de la consistencia. Las condiciones de estabilidad son corroboradas con ejemplos numéricos. Los resultados se comparan con métodos relevantes de la bibliografía mostrando la eficiencia de los métodos propuestos. / [CA] La present tesi doctoral se centra en la construcció d'esquemes en diferències finites i l'anàlisi numèrica de rellevants models de valoració d'opcions que generalitzen el model de Black-Scholes. Es proporciona una anàlisi cuidadosa de les propietats de les solucions numèri-ques com ara la positivitat, l'estabilitat i la consistència. A fi de manejar la frontera lliure que sorgix en els problemes de valoració d'opcions Americanes, s'apliquen i s'estudien diverses tècniques de transformació basades en el mètode de fixació de les fronteres (front-fixing). Es presta especial atenció a la valoració d'opcions de múltiples actius, com són les opcions ''exchange'' i ''spread''. Esta tesi es compon de sis capítols. El primer capítol és una introducció que conté les definicions d'opció i termes relacionats i la derivació de l'equació de Black-Scholes, així com aspectes generals de la teoria dels esquemes en diferències finites, incloent aspectes preliminars d'anàlisi numèrica. El 2n capítol està dedicat a resoldre el model lineal de Black-Scholes per a opcions Americanes ''put'' i ''call''. Per a fixar les fronteres del problema de frontera lliure s'apliquen transformacions com la de Landau i s'ha proposat un nou canvi de variable proposat. Açò porta a una equació diferencial en derivades parcials no lineal en un domini fix. L'eficiència del mètode front-fixing mostrada en el 2n capítol ha motivat l'estudi de la seua aplicació a alguns models no lineals més complicats. En particular, es proposa un canvi de variables que porta a una nova frontera dependent del temps en compte d'una fixa. Este canvi s'aplica a models no lineals de Black-Scholes per a opcions Americanes, com són el de Barles i Soner i el model RAPM (Risk Adjusted Pricing Methodology). El 4t capítol oferix una nova tècnica per a la resolució de problemes de valoració d'opcions Americanes basada en la racionalitat dels inversors. Apareix una funció de la intensitat que es pot reduir en el cas més simple a la tècnica de penalització (penal method) . Este enfocament té en compte el possible comportament irracional dels inversors. En la secció 4.2 s'aplica esta tècnica al model de canvi de règims el que porta a un nou model que té en compte el possible exercici irracional, així com diversos estats del mercat. L'enfocament del paràmetre de racionalitat junt amb una transformació logarítmica permeten construir un esquema numèric eficient sense aplicar el mètode front-fixing o la coneguda formulació de LCP (Linear Complementarity Problem). El 5é capítol es dedica a la valoració d'opcions d'actius múltiples. Una transformació apropiada permet l'eliminació del terme de derivades mixtes evitant inconvenients computacionals i possibles problemes d' estabilitat. Les conclusions es mostren al 6é capítol. Es posa en relleu diversos aspectes de la present tesi. Tots els models considerats i els mètodes numèrics van acompanyats de diversos exemples i simulacions. S'estu-dia la convergència numèrica que confirma l'estudi teòric de la consistència. Les condicions d'estabilitat són corroborades amb exemples numèrics. Els resultats es comparen amb mètodes rellevants de la bibliografia mostrant l'eficiència dels mètodes proposats. / Egorova, V. (2016). Finite Difference Methods for nonlinear American Option Pricing models: Numerical Analysis and Computing [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/68501 / TESIS / Premios Extraordinarios de tesis doctorales

Este trabalho propõe um esquema de diferenças finitas compacta de alta ordem para resolver problemas elípticos com coeficientes variáveis em malhas composta. São apresentados a formulação matemática e a dedução do método compacto de quarta ordem aplicado à problemas elípticos bidimensionais, em malha regular e composta. Foi adotado o uso da biblioteca PETSc com os seus pré-condicionadores e métodos numéricos para resolver os sistemas lineares resultantes da discretização do problema. Por fim, testes visando verificar o código foram feitos, utilizando o método de soluções manufaturadas, para mostrar alta eficiência e acurácia do método desenvolvido. / This paper proposes a scheme of compact finite difference higher order for solve elliptic problems with variable coeficients in composite meshes. we present the mathematical formulation and the deduction of the compact method of fourth order applied to two-dimensional elliptic problems in regular and composite mesh . It was adopted using the PETSc library with its pre- conditioners and numerical methods for solving linear systems resulting from discretization of the problem. Finally , tests to verify the code were made using the method of manufactured solutions to show high eficiency and accuracy of the method developed .

Technological advancement has thrust MEMS design and fabrication into the forefront of modern technologies. It has become sufficiently self-sustained to allow mass production. The limiting factor which is stalling commercialization of MEMS is the packaging and device reliability. The challenging issues with MEMS packaging are application specific. The function of the package is to give the MEMS device mechanical support, protection from the environment, and electrical connection to other devices in the system. The current state of the art in MEMS packaging transcends the various packaging techniques available in the integrated circuit (IC) industry. At present the packaging of MEMS includes hermetic ceramic packaging and metal packaging with hermetic seals. For example the ADXL202 accelerometer from the Analog Devices. Study of the packaging methods and costs show that both of these methods of packaging are expensive and not needed for majority of MEMS applications. Due to this the cost of current MEMS packaging is relatively high, as much as 90% of the finished product. Reducing the cost is therefore of the prime concern. This Thesis explores the possibility of an inexpensive plastic package for MEMS sensors like accelerometers, optical MEMS, blood pressure sensors etc. Due to their cost effective techniques, plastic packaging already dominates the IC industry. They cost less, weigh less, and their size is small. However, porous nature of molding materials allows penetration of moisture into the package. The Thesis includes an extensive study of the plastic packaging and characterization of three different plastic package samples. Polymeric materials warp upon absorbing moisture, generating hygroscopic stresses. Hygroscopic stresses in the package add to the thermal stress due to high reflow temperature. Despite this, hygroscopic characteristics of the plastic package have been largely ignored. To facilitate understanding of the moisture absorption, an analytical model is presented in this Thesis. Also, an empirical model presents, in this Thesis, the parameters affecting moisture ingress. This information is important to determine the moisture content at a specific time, which would help in assessing reliability of the package. Moisture absorption is modeled using the single phase absorption theory, which assumes that moisture diffusion occurs freely without any bonding with the resin. This theory is based on the Fick's Law of diffusion, which considers that the driving force of diffusion is the water concentration gradient. A finite difference simulation of one-dimensional moisture diffusion using the Crank-Nicolson implicit formula is presented. Moisture retention causes swelling of compounds which, in turn, leads to warpage. The warpage induces hygroscopic stresses. These stresses can further limit the performance of the MEMS sensors. This Thesis also presents a non invasive methodology to characterize a plastic package. The warpage deformations of the package are measured using Optoelectronic holography (OEH) methodology. The OEH methodology is noninvasive, remote, and provides results in full-field-of-view. Using the quantitative results of OEH measurements of deformations of a plastic package, pressure build up can be calculated and employed to assess the reliability of the package.

Conservation laws with uncertain initial and boundary conditions are approximated using a generalized polynomial chaos expansion approach where the solution is represented as a generalized Fourier series of stochastic basis functions, e.g. orthogonal polynomials or wavelets. The stochastic Galerkin method is used to project the governing partial differential equation onto the stochastic basis functions to obtain an extended deterministic system. The stochastic Galerkin and collocation methods are used to solve an advection-diffusion equation with uncertain viscosity. We investigate well-posedness, monotonicity and stability for the stochastic Galerkin system. High-order summation-by-parts operators and weak imposition of boundary conditions are used to prove stability. We investigate the impact of the total spatial operator on the convergence to steady-state.  Next we apply the stochastic Galerkin method to Burgers' equation with uncertain boundary conditions. An analysis of the truncated polynomial chaos system presents a qualitative description of the development of the solution over time. An analytical solution is derived and the true polynomial chaos coefficients are shown to be smooth, while the corresponding coefficients of the truncated stochastic Galerkin formulation are shown to be discontinuous. We discuss the problematic implications of the lack of known boundary data and possible ways of imposing stable and accurate boundary conditions. We present a new fully intrusive method for the Euler equations subject to uncertainty based on a Roe variable transformation. The Roe formulation saves computational cost compared to the formulation based on expansion of conservative variables. Moreover, it is more robust and can handle cases of supersonic flow, for which the conservative variable formulation fails to produce a bounded solution. A multiwavelet basis that can handle  discontinuities in a robust way is used. Finally, we investigate a two-phase flow problem. Based on regularity analysis of the generalized polynomial chaos coefficients, we present a hybrid method where solution regions of varying smoothness are coupled weakly through interfaces. In this way, we couple smooth solutions solved with high-order finite difference methods with non-smooth solutions solved for with shock-capturing methods.

The principle of coordinate invariance states that all physical laws must be formulated in a mathematical form that is independent of the geometrical properties of any particular coordinate system. Embracing this principle is the key to understand how to systematically incorporate curved material interfaces into a numerical solution of Maxwell’s equations. This dissertation describes how to generate a coordinate invariant representation of Maxwell’s equations in differential form, and it demonstrates why employing such representation is crucial to the development of robust finite-difference discretisations with consistent global error properties. As part of this process, two original contributions are presented that address the issue of constructing finite-difference approximations at the locations of material interfaces. The first contribution is a domain-decomposition procedure to enforce the tangential field continuity conditions with a second-order local truncation error that can be applied in 2-D or 3-D. The second contribution is a similar domain-decomposition procedure that enforces the tangential field continuity conditions with a local truncation of order 2L—where L is an integer greater or equal to one—but that can only be applied in 1-D. To conclude, the dissertation also describes the interesting connection that exists between the use of a coordinate invariant representation of Maxwell’s equations to design artificial materials and the use of the same representation to model curved material interfaces in a finite-difference discretisation.

The principle of coordinate invariance states that all physical laws must be formulated in a mathematical form that is independent of the geometrical properties of any particular coordinate system. Embracing this principle is the key to understand how to systematically incorporate curved material interfaces into a numerical solution of Maxwell’s equations. This dissertation describes how to generate a coordinate invariant representation of Maxwell’s equations in differential form, and it demonstrates why employing such representation is crucial to the development of robust finite-difference discretisations with consistent global error properties. As part of this process, two original contributions are presented that address the issue of constructing finite-difference approximations at the locations of material interfaces. The first contribution is a domain-decomposition procedure to enforce the tangential field continuity conditions with a second-order local truncation error that can be applied in 2-D or 3-D. The second contribution is a similar domain-decomposition procedure that enforces the tangential field continuity conditions with a local truncation of order 2L—where L is an integer greater or equal to one—but that can only be applied in 1-D. To conclude, the dissertation also describes the interesting connection that exists between the use of a coordinate invariant representation of Maxwell’s equations to design artificial materials and the use of the same representation to model curved material interfaces in a finite-difference discretisation.

Este trabalho propõe um esquema de diferenças finitas compacta de alta ordem para resolver problemas elípticos com coeficientes variáveis em malhas composta. São apresentados a formulação matemática e a dedução do método compacto de quarta ordem aplicado à problemas elípticos bidimensionais, em malha regular e composta. Foi adotado o uso da biblioteca PETSc com os seus pré-condicionadores e métodos numéricos para resolver os sistemas lineares resultantes da discretização do problema. Por fim, testes visando verificar o código foram feitos, utilizando o método de soluções manufaturadas, para mostrar alta eficiência e acurácia do método desenvolvido. / This paper proposes a scheme of compact finite difference higher order for solve elliptic problems with variable coeficients in composite meshes. we present the mathematical formulation and the deduction of the compact method of fourth order applied to two-dimensional elliptic problems in regular and composite mesh . It was adopted using the PETSc library with its pre- conditioners and numerical methods for solving linear systems resulting from discretization of the problem. Finally , tests to verify the code were made using the method of manufactured solutions to show high eficiency and accuracy of the method developed .

Magister Scientiae - MSc / Efficient numerical approaches for parameter dependent problems have been an inter- esting subject to numerical analysts and engineers over the past decades. This is due to the prominent role that these problems play in modeling many real life situations in applied sciences. Often, the choice and the e ciency of the approaches depend on the nature of the problem to solve. In this work, we consider the general linear first-order singularly perturbed Volterra integro-differential equations (SPVIDEs). These singularly perturbed problems (SPPs) are governed by integro-differential equations in which the derivative term is multiplied by a small parameter, known as "perturbation parameter". It is known that when this perturbation parameter approaches zero, the solution undergoes fast transitions across narrow regions of the domain (termed boundary or interior layer) thus affecting the convergence of the standard numerical methods. Therefore one often seeks for numerical approaches which preserve stability for all the values of the perturbation parameter, that is "numerical methods. This work seeks to investigate some "numerical methods that have been used to solve SPVIDEs. It also proposes alternative ones. The various numerical methods are composed of a fitted finite difference scheme used along with suitably chosen interpolating quadrature rules. For each method investigated or designed, we analyse its stability and convergence. Finally, numerical computations are carried out on some test examples to con rm the robustness and competitiveness of the proposed methods.

High-order accurate finite difference methods have been applied to the acoustic wave equation in discontinuous media and curvilinear geometries, using the SBP-SAT method. Strict stability is shown for the 2-D wave equation with general boundary conditions. The fourth-order accurate method for the 3-D wave equation has been implemented in C and parallelized using MPI. The implementation has been verified against an analytical solution and runs efficiently on a large number of processors.