A framework for polynomial preconditioners based on fast transforms I: Theory

Optimal and superoptimal approximations of a complex square matrix by polynomials in a normal basis matrix are considered. If the unitary transform associated with the eigenvectors of the basis matrix is computable using a fast algorithm, the approximations may be utilized for constructing preconditioners. Theorems describing how the parameters of the approximations could be efficiently computed are given, and for special cases earlier results by other authors are recovered. Also, optimal and superoptimal approximations for block matrices are determined, and the same type of theorems as for the point case are proved. This research was supported by the Swedish National Board for Industrial and Technical Development (NUTEK) and by the U.S. National Science Foundation under grant ASC-8958544.     

Boundary layer approximate approximations and cubature of potentials in domains

In this article we present a new approach to the computation of volume potentials over bounded domains, which is based on the quasi‐interpolation of the density by almost locally supported basis functions for which the corresponding volume potentials are known. The quasi‐interpolant is a linear combination of the basis function with shifted and scaled arguments and with coefficients explicitly given by the point values of the density. Thus, the approach results in semi‐analytic cubature formulae for volume potentials, which prove to be high order approximations of the integrals. It is based on multi‐resolution schemes for accurate approximations up to the boundary by applying approximate refinement equations of the basis functions and iterative approximations on finer grids. We obtain asymptotic error estimates for the quasi‐interpolation and corresponding cubature formulae and provide some numerical examples. This revised version was published online in June 2006 with corrections to the Cover Date.     

On approximation in total variation penalization for image reconstruction and inverse problems

In this paper, we examine some theoretical issues associated with the use of total variation based image reconstruction. Our investigations are motivated by problems of inverse interferome-try, in which laser light phase shifts are used to reconstruct medium density profiles in flow field sensing. The reconstruction problem is posed as a residual minimization with total variation reg-ularization applied to handle the inherent ill-posedness. We consider numerical approximations of these penalized minimal residual problems, and analyze some approximation strategies and their properties. The standard definition of total variation leads to inconsistent approximations, with piecewise constant basis functions, so we consider alternative definitions, which preserve the needed compactness and produce convergent approximations.     

On the construction of approximations to continuous functions under integral boundary conditions

On the basis of the resolvent of a simple differential operator, a method for finding approximations to continuous functions is constructed. In this method, both the approximated function and its approximations satisfy the given integral boundary condition.     

Long-Term Forecasts of Optimal Approximations to the Load Duration Curve

Little has been done by way of developing an objective technique for long-term forecasting of a utility load duration curve. This paper endeavours to rectify this situation by developing a methodology to provide forecasts of an economically optimal approximation to the load duration curve. A dynamic programming algorithm serves as the basis of the optimal approximations over a known horizon. These approximations are then forecast using time series analysis and an econometric model. The approach is implemented and the results are encouraging.     

Learning mixtures of polynomials of multidimensional probability densities from data using B-spline interpolation

Non-parametric density estimation is an important technique in probabilistic modeling and reasoning with uncertainty. We present a method for learning mixtures of polynomials (MoPs) approximations of one-dimensional and multidimensional probability densities from data. The method is based on basis spline interpolation, where a density is approximated as a linear combination of basis splines. We compute maximum likelihood estimators of the mixing coefficients of the linear combination. The Bayesian information criterion is used as the score function to select the order of the polynomials and the number of pieces of the MoP. The method is evaluated in two ways. First, we test the approximation fitting. We sample artificial datasets from known one-dimensional and multidimensional densities and learn MoP approximations from the datasets. The quality of the approximations is analyzed according to different criteria, and the new proposal is compared with MoPs learned with Lagrange interpolation and mixtures of truncated basis functions. Second, the proposed method is used as a non-parametric density estimation technique in Bayesian classifiers. Two of the most widely studied Bayesian classifiers, i.e., the naive Bayes and tree-augmented naive Bayes classifiers, are implemented and compared. Results on real datasets show that the non-parametric Bayesian classifiers using MoPs are comparable to the kernel density-based Bayesian classifiers. We provide a free R package implementing the proposed methods.     

Approximation of a fractional power of an elliptic operator

Some mathematical models of applied problems lead to the need of solving boundary value problems with a fractional power of an elliptic operator. In a number of works, approximations of such a nonlocal operator are constructed on the basis of an integral representation with a singular integrand. In the present article, new integral representations are proposed for operators with fractional powers. Approximations are based on the classical quadrature formulas. The results of numerical experiments on the accuracy of quadrature formulas are presented. The proposed approximations are used for numerical solving a model two‐dimensional boundary value problem for fractional diffusion.     

Near-best L1 approximations on circular and elliptical contours

Polynomial approximations are obtained to analytic functions on circular and elliptical contours by forming partial sums of order n of their expansions in Taylor series and Chebyshev series of the second kind, respectively. It is proved that the resulting approximations converge in the L₁ norm as n → ∞, and that they are near-best L₁ approximations within relative distances of the order of log n. Practical implications of the results are discussed, and they are shown to provide a theoretical basis for polynomial approximation methods for the evaluation of indefinite integrals on contours.     

Numerical simulation of convective motion in an anisotropic porous medium and cosymmetry conservation

The onset of convection in a porous anisotropic rectangle occupied by a heat-conducting fluid heated from below is analyzed on the basis of the Darcy–Boussinesq model. It is shown that there are combinations of control parameters for which the system has a nontrivial cosymmetry and a one-parameter family of stationary convective regimes branches off from the mechanical equilibrium. For the two-dimensional convection equations in a porous medium, finite-difference approximations preserving the cosymmetry of the original system are developed. Numerical results are presented that demonstrate the formation of a family of convective regimes and its disappearance when the approximations do not inherit the cosymmetry property.     

Taylor expansions of the value function associated with a bilinear optimal control problem

A general bilinear optimal control problem subject to an infinite-dimensional state equation is considered. Polynomial approximations of the associated value function are derived around the steady state by repeated formal differentiation of the Hamilton–Jacobi–Bellman equation. The terms of the approximations are described by multilinear forms, which can be obtained as solutions to generalized Lyapunov equations with recursively defined right-hand sides. They form the basis for defining a suboptimal feedback law. The approximation properties of this feedback law are investigated. An application to the optimal control of a Fokker–Planck equation is also provided.     

Corrected Collocation Approximations for the Harmonic Dirichlet Problem

Collocation approximations with harmonic basis functions tothe solution of the harmonic Dirichlet problem are investigated.The choice of collocation points for a best local approximationis discussed, and a result is given in terms of the abscissaeof some best quadrature formulae. A global near-best approximationis obtained by adding a correction term to the collocation approximation,utilizing basic properties of the Green's function. Numericalexamples are given, demonstrating the great improvement achieved.The same correction term can also improve on least-squares approximationsand Galerkin approximations, and the results can easily be adaptedto deal with mixed harmonic boundary value problems.     

Lower bounds of error estimates for singular perturbation problems with Jacobi-Spectral approximations

With weighted orthogonal Jacobi polynomials, we study spectral approximations for singular perturbation problems on an interval. The singular parameters of the model are included in the basis functions, and then its stiff matrix is diagonal. Considering the estimations for weighted orthogonal coefficients, a special technique is proposed to investigate the a posteriori error estimates. In view of the difficulty of a posteriori error estimates for spectral approximations, we employ a truncation projection to study lower bounds for the models. Specially, we present the lower bounds of a posteriori error estimates with two different weighted norms in details.     

Discrepancy Principle and Convergence Rates in Regularization of Monotone Ill-Posed Problems

The convergence rates of the regularized solution as well as its Galerkin approximations for nonlinear monotone ill-posed problems in a Banach space are established on the basis of the choice of a regularization parameter by the Morozov discrepancy principle.     

Approximate methods for equations of incompressible fluid

Approximate methods on the basis of sequential approximations in the theory of functional solutions to systems of conservation laws is considered, including the model of dynamics of incompressible fluid. Test calculations are performed, and a comparison with exact solutions is carried out.     

Nonlinear approximation using Gaussian kernels

It is well known that nonlinear approximation has an advantage over linear schemes in the sense that it provides comparable approximation rates to those of the linear schemes, but to a larger class of approximands. This was established for spline approximations and for wavelet approximations, and more recently by DeVore and Ron (in press) [2] for homogeneous radial basis function (surface spline) approximations. However, no such results are known for the Gaussian function, the preferred kernel in machine learning and several engineering problems. We introduce and analyze in this paper a new algorithm for approximating functions using translates of Gaussian functions with varying tension parameters. At heart it employs the strategy for nonlinear approximation of DeVore-Ron, but it selects kernels by a method that is not straightforward. The crux of the difficulty lies in the necessity to vary the tension parameter in the Gaussian function spatially according to local information about the approximand: error analysis of Gaussian approximation schemes with varying tension are, by and large, an elusive target for approximators. We show that our algorithm is suitably optimal in the sense that it provides approximation rates similar to other established nonlinear methodologies like spline and wavelet approximations. As expected and desired, the approximation rates can be as high as needed and are essentially saturated only by the smoothness of the approximand.     

An investigation of phase-distribution moment-matching algorithms for use in queueing models

Algorithms for matching moments to phase-type distributions are evaluated on the basis of their performance in their intended application, queueing models. The moment-matching algorithms under consideration match two moments to a hyperexponential distribution with balanced means and three moments to a mixture of two Erlang distributions of common order. These algorithms are used to approximate an interarrival-time distribution for a queueing model, and the accuracy of associated performance-measure approximations is then used to evaluate the moment-matching algorithms. Three performance measures are considered, and attention is focussed on the steady-state mean queue length (number in system) of theGI/M/1 queue. Performance-measure approximations are compared to three-moment bounds and performance-measure values arising from hypothetical approximated distributions.     

The approximation of planar curve evolutions by stable fully implicit finite element schemes that equidistribute

On the basis of our previous work, we introduce novel fully discrete, fully practical parametric finite element approximations for geometric evolution equations of curves in the plane. The fully implicit approximations are unconditionally stable and intrinsically equidistribute the vertices at each time level. We present iterative solution methods for the systems of nonlinear equations arising at each time level and present several numerical results. The ideas easily generalize to the evolution of curve networks and to anisotropic surface energies. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Numerical identification of the leading coefficient of a parabolic equation

For a multidimensional parabolic equation, we study the problem of finding the leading coefficient, which is assumed to depend only on time, on the basis of additional information about the solution at an interior point of the computational domain. For the approximate solution of the nonlinear inverse problem, we construct linearized approximations in time with the use of ordinary finite-element approximations with respect to space. The numerical algorithm is based on a special decomposition of the approximate solution for which the transition to the next time level is carried out by solving two standard elliptic problems. The capabilities of the suggested numerical algorithm are illustrated by the results of numerical solution of a model inverse two-dimensional problem.     

Tau method approximation of a generalized Epstein-Hubbell elliptic-type integral

We consider the evaluation of a recent generalization of the Epstein-Hubbell elliptic-type integral using the tau method approximation with a Chebyshev polynomial basis. This also leads to an approximation of Lauricella's hypergeometric function of three variables. Numerical results are given for polynomial approximations of degree 6.