Optimal convergence rate for Yosida approximations of bounded holomorphic semigroups

In this paper, we obtain optimal bounds for convergence rate for Yosida approximations of bounded holomorphic semigroups. We also provide asymptotic expansions for semigroups in terms of Yosida approximations and obtain optimal error bounds for these expansions.     

Constrained interpolation and smoothing

Numerical and theoretical questions related to constrained interpolation and smoothing are treated. The prototype problem is that of finding the smoothest convex interpolant to given univariate data. Recent results have shown that this convex programming problem with infinite constraints can be recast as a finite parametric nonlinear system whose solution is closely related to the second derivative of the desired interpolating function. This paper focuses on the analysis of numerical techniques for solving the nonlinear system and on the theoretical issues that arise when certain extensions of the problem are considered. In particular, we show that two standard iteration techniques, the Jacobi and Gauss-Seidel methods, are globally convergent when applied to this problem. In addition we use the problem structure to develop an efficient implementation of Newton's method and observe consistent quadratic convergence. We also develop a theory for the existence, uniqueness, and representation of solutions to the convex interpolation problem with nonzero lower bounds on the second derivative (strict convexity). Finally, a smoothing spline analogue to the convex interpolation problem is studied with reference to the computation of convex approximations to noisy data.     

Numerical approximations of a nonlinear eigenvalue problem and applications to a density functional model

In this paper, we study numerical approximations of a nonlinear eigenvalue problem and consider applications to a density functional model. We prove the convergence of numerical approximations. In particular, we establish several upper bounds of approximation errors and report some numerical results of finite element electronic structure calculations that support our theory. Copyright © 2010 John Wiley & Sons, Ltd.     

On Early Stopping in Gradient Descent Learning

In this paper we study a family of gradient descent algorithms to approximate the regression function from reproducing kernel Hilbert spaces (RKHSs), the family being characterized by a polynomial decreasing rate of step sizes (or learning rate). By solving a bias-variance trade-off we obtain an early stopping rule and some probabilistic upper bounds for the convergence of the algorithms. We also discuss the implication of these results in the context of classification where some fast convergence rates can be achieved for plug-in classifiers. Some connections are addressed with Boosting, Landweber iterations, and the online learning algorithms as stochastic approximations of the gradient descent method.     

A posteriori error bounds for the zeros of a polynomial

Summary An algorithm for the computation of error bounds for the zeros of a polynomial is described. This algorithm is derived by applying Rouché's theorem to a Newton-like interpolation formula for the polynomial, and so it is suitable in the case where the approximations to the zeros of the polynomial are computed successively using deflation. Confluent and clustered approximations are handled easily. However bounds for the local rouding errors in deflation, e.g. in Horner's scheme, must be known. In practical application the method can, especially in some ill-conditioned cases, compete with other known estimates.     

Convergence of the control parameterization Ritz method for nonlinear optimal control problems

This paper studies the local convergence properties of the control parameterization Ritz method in which the control variable is approximated over a finite-dimensional subspace. The nonlinear free-endpoint optimal control problem is considered, and error bounds are derived for both the cost functional and state-control convergence. Explicit error bounds are obtained for the particular case of approximations over spline spaces. On specializing the general results to the linear-quadratic regulator problem, global convergence results are obtained. Computational results supporting the theoretically derived error bounds are presented.This research was supported by the University Grants Committee of New Zealand.     

Approximations of a Continuous Time Filter. Application to Optimal Allocation Problems in Finance

Abstract

In this article, we study a continuous time optimal filter and its various numerical approximations. This filter arises in an optimal allocation problem in the particular context of a non-stationary economy. We analyse the rates of convergence of the approximations of the filter when the model is misspecified and when the observations can only be made at discrete times. We give bounds that are uniform in time. Numerical results are presented.     

Reconstruction of signals from multiscale edges

We present a method for signal reconstruction based upon the location of its singularities which are identified by a wavelet transform technique. The reconstructed signal is an infconvolution spline approximant. The data for the interpolation problem which we solve comes from a compact signal coding procedure. Error bounds and convergence results for the calculated signal are given.     

Hermite spectral and pseudospectral methods for numerical differentiation

A numerical differentiation problem for a given function with noisy data is discussed in this paper. A mollification method based on spanned by Hermite functions is proposed and the mollification parameter is chosen by a discrepancy principle. The convergence estimates of the derivatives are obtained. To get a practical approach, we also derive corresponding results for pseudospectral (Hermite-Gauss interpolation) approximations. Numerical examples are given to show the efficiency of the method.     

Weak and strong convergence theorems for variational inequality problems

In this paper, we study the weak and strong convergence of two algorithms for solving Lipschitz continuous and monotone variational inequalities. The algorithms are inspired by Tseng’s extragradient method and the viscosity method with Armijo-like step size rule. The main advantages of our algorithms are that the construction of solution approximations and the proof of convergence of the algorithms are performed without the prior knowledge of the Lipschitz constant of cost operators. Finally, we provide numerical experiments to show the efficiency and advantage of the proposed algorithms.     

Classical solution of a one-dimensional parabolic boundary value problem with nonlinear boundary conditions and moving boundary

We consider a nonlinear parabolic boundary value problem of the Stefan type with one space variable, which generalizes the model of hydride formation under constant conditions. We suggest a grid method for constructing approximations to the unknown boundary and to the concentration distribution. We prove the uniform convergence of the interpolation approximations to a classical solution of the boundary value problem. (The boundary is smooth, and the concentration distribution has the necessary derivatives.) Thus, we prove the theorem on the existence of a solution, and the proof is given in constructive form: the suggested convergent grid method can be used for numerical experiments.     

High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

We consider the problem of Lagrange polynomial interpolation in high or countably infinite dimension, motivated by the fast computation of solutions to partial differential equations (PDEs) depending on a possibly large number of parameters which result from the application of generalised polynomial chaos discretisations to random and stochastic PDEs. In such applications there is a substantial advantage in considering polynomial spaces that are sparse and anisotropic with respect to the different parametric variables. In an adaptive context, the polynomial space is enriched at different stages of the computation. In this paper, we study an interpolation technique in which the sample set is incremented as the polynomial dimension increases, leading therefore to a minimal amount of PDE solving. This construction is based on the standard principle of tensorisation of a one-dimensional interpolation scheme and sparsification. We derive bounds on the Lebesgue constants for this interpolation process in terms of their univariate counterpart. For a class of model elliptic parametric PDE’s, we have shown in Chkifa et al. (Modél. Math. Anal. Numér. 47(1):253–280, 2013) that certain polynomial approximations based on Taylor expansions converge in terms of the polynomial dimension with an algebraic rate that is robust with respect to the parametric dimension. We show that this rate is preserved when using our interpolation algorithm. We also propose a greedy algorithm for the adaptive selection of the polynomial spaces based on our interpolation scheme, and illustrate its performance both on scalar valued functions and on parametric elliptic PDE’s.     

Approximation by Interpolation Trigonometric Polynomials in Metrics of the Space Lp on the Classes of Periodic Entire Functions*

Ukrainian Mathematical Journal - We establish asymptotic equalities for the least upper bounds of approximations by interpolation trigonometric polynomials with equidistant distribution of...     

The necessity of Shishkin decompositions

In the present paper, we study model singularly perturbed convection-diffusion problems with exponential boundary layers. It has been believed for some time that only a complete splitting of the exact solution into regular and layer parts provides the information necessary for the study of the uniform convergence properties of numerical methods for these problems on layer-adapted grids (such as Shishkin meshes). In the present paper, we give new proofs of uniform interpolation error estimates for linear and bilinear interpolation; these proofs are based on the older a priori bounds derived by Kellogg and Tsan [1].     

A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models

We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances.

     

Approximation of Periodic Analytic Functions by Interpolation Trigonometric Polynomials

We obtain asymptotic equalities for the upper bounds of approximations by interpolation trigonometric polynomials on classes of convolutions of periodic functions admitting a regular extension to a fixed strip of the complex plane.     

Efficiently implementable iterative methods for linear elliptic variational inequalities with constraints on the gradient of solution

We construct and investigate a new iterative solution method for a finite-dimensional constrained saddle point problem. The results are applied to prove the convergence of different iterativemethods formesh approximations of variational inequalities with constraints on the gradient of solution. In particular, we prove the convergence of two-stage iterative methods. The main advantage of the proposed methods is the simplicity of their implementation. The numerical testing demonstrates high convergence rate of the methods.     

A nonoverlapping domain decomposition method for stabilized finite element approximations of the Oseen equations

A nonoverlapping domain decomposition algorithm of Robin–Robin type is applied to the discretized Oseen equations using stabilized finite element approximations of velocity and pressure thus allowing in particular equal-order interpolation. As a crucial result we have to inspect the proof of a modified inf–sup condition, in particular, the dependence of the stability constant with respect to the Reynolds number (cf. appendix). After proving coercivity and strong convergence of the method, we derive an a posteriori estimate which controls convergence of the discrete subdomain solutions to the global discrete solution provided that jumps of the discrete solution converge at the interface. Furthermore, we obtain information on the design of some free parameters within the Robin-type interface condition which essentially influence the convergence speed. Some numerical results confirm the theoretical ones.     

A comparison of variational approximations for fast inference in mixed logit models

Variational Bayesian methods aim to address some of the weaknesses (computation time, storage costs and convergence monitoring) of mainstream Markov chain Monte Carlo based inference at the cost of a biased but more tractable approximation to the posterior distribution. We investigate the performance of variational approximations in the context of the mixed logit model, which is one of the most used models for discrete choice data. A typical treatment using the variational Bayesian methodology is hindered by the fact that the expectation of the so called log-sum-exponential function has no explicit expression. Therefore additional approximations are required to maintain tractability. In this paper we compare seven different possible bounds or approximations. We found that quadratic bounds are not sufficiently accurate. A recently proposed non-quadratic bound did perform well. We also found that the Taylor series approximation used in a previous study of variational Bayes for mixed logit models is only accurate for specific settings. Our proposed approximation based on quasi Monte Carlo sampling performed consistently well across all simulation settings while remaining computationally tractable.     

Fitted mesh method for singularly perturbed reaction-convection-diffusion problems with boundary and interior layers

A robust numerical method for a singularly perturbed secondorder ordinary differential equation having two parameters with a discontinuous source term is presented in this article. Theoretical bounds are derived for the derivatives of the solution and its smooth and singular components. An appropriate piecewise uniform mesh is constructed, and classical upwind finite difference schemes are used on this mesh to obtain the discrete system of equations. Parameter-uniform error bounds for the numerical approximations are established. Numerical results are provided to illustrate the convergence of the numerical approximations.