Multistep approximation algorithms: Improved convergence rates through postconditioning with smoothing kernels

We show how certain widely used multistep approximation algorithms can be interpreted as instances of an approximate Newton method. It was shown in an earlier paper by the second author that the convergence rates of approximate Newton methods (in the context of the numerical solution of PDEs) suffer from a “loss of derivatives”, and that the subsequent linear rate of convergence can be improved to be superlinear using an adaptation of Nash–Moser iteration for numerical analysis purposes; the essence of the adaptation being a splitting of the inversion and the smoothing into two separate steps. We show how these ideas apply to scattered data approximation as well as the numerical solution of partial differential equations. We investigate the use of several radial kernels for the smoothing operation. In our numerical examples we use radial basis functions also in the inversion step. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some new approaches to the solution of the diffusion chaos problem

Using the solution of the Kuramoto–Tsuzuki equation as an example, we present the results of numerical investigations of diffusion chaos in the neighborhood of the thermodynamic branch of the “reaction–diffusion” equation system. Chaos onset scenarios are considered both in the small-mode approximation and for the solution of the second boundary-value problem for the original equation. In the phase space of the Kuramoto–Tsuzuki equation chaos sets in through period doubling bifurcation cascades and through subharmonic bifurcation cascades of two-dimensional tori by both internal and external frequency. Chaos onset scenarios in the Kuramoto–Tsuzuki equation phase space and in the Fourier coefficient space are compared both for the small-mode approximation and for direct numerical solution of the second boundary-value problem. Inappropriateness of the three-dimensional small-mode approximations is proved.     

Numerical approximations and solution techniques for the space-time Riesz–Caputo fractional advection-diffusion equation

In this paper, we consider a space-time Riesz–Caputo fractional advection-diffusion equation. The equation is obtained from the standard advection-diffusion equation by replacing the first-order time derivative by the Caputo fractional derivative of order α ∈ (0,1], the first-order and second-order space derivatives by the Riesz fractional derivatives of order β ₁ ∈ (0,1) and β ₂ ∈ (1,2], respectively. We present an explicit difference approximation and an implicit difference approximation for the equation with initial and boundary conditions in a finite domain. Using mathematical induction, we prove that the implicit difference approximation is unconditionally stable and convergent, but the explicit difference approximation is conditionally stable and convergent. We also present two solution techniques: a Richardson extrapolation method is used to obtain higher order accuracy and the short-memory principle is used to investigate the effect of the amount of computations. A numerical example is given; the numerical results are in good agreement with theoretical analysis.     

On polynomial collocation for second kind integral equations with fixed singularities of Mellin type

Summary.  We consider a polynomial collocation for the numerical solution of a second kind integral equation with an integral kernel of Mellin convolution type. Using a stability result by Junghanns and one of the authors, we prove that the error of the approximate solution is less than a logarithmic factor times the best approximation and, using the asymptotics of the solution, we derive the rates of convergence. Finally, we describe an algorithm to compute the stiffness matrix based on simple Gau? quadratures and an alternative algorithm based on a recursion in the spirit of Monegato and Palamara Orsi. All together an almost best approximation to the solution of the integral equation can be computed with 𝒪(n ²[log n]²) resp. 𝒪(n ²) operations, where n is the dimension of the polynomial trial space. Received February 18, 2002 / Revised version received May 15, 2002 / Published online October 29, 2002 RID="⋆" ID="⋆" Correspondence to: A. Rathsfeld Mathematics Subject Classification (1991): 65R20     

Theoretical and Numerical Analysis of a Class of Nonlinear Elliptic Equations

In this paper we show the existence of weak solutions for a nonlinear elliptic equation with arbitrary growth of the non linearity and data measure. A numerical algorithm to compute a numerical approximation of the weak solution is described and analyzed. In a first step a super-solution is computed using a domain decomposition method. Numerical examples are presented and commented. This work was supported by the French Grant “Action Intégrée MA/02/33”.     

Fractal measures and polynomial sampling: I.F.S.–Gaussian integration

Measures generated by Iterated Function Systems can be used in place of atomic measures in Gaussian integration. A stable algorithm for the numerical solution of the related approximation problem – an inverse problem in fractal construction – is proposed. Dedicated to Walter Gautschi.     

Two-stage stochastic problems with correlated normal variables: computational experiences

Two-stage models are frequently used when making decisions under the influence of randomness. The case of normally distributed right hand side vector – with independent or correlated components – is treated here. The expected recourse function is computed by an enhanced Monte Carlo integration technique. Successive regression approximation technique is used for computing the optimal solution of the problem. Computational issues of the algorithm are discussed, improvements are proposed and numerical results are presented for random right hand side and a random matrix in the second stage problems.     

On the best mean-square approximation of a real nonnegative finite continuous function of two variables by the modulus of a double Fourier integral. I

We study the nonlinear problem of mean-square approximation of a real finite nonnegative continuous function of two variables by the modulus of a double Fourier integral depending on two parameters. The solution of this problem is reduced to the solution of a nonlinear two-dimensional integral equation of the Hammerstein type. Numerical algorithms for determination of branching lines and branched solutions of equation are constructed and substantiated. Some numerical examples are given. Translated from Matematychni Metody ta Fizyko-Mekhanichni Polya, Vol. 51, No. 1, pp. 53–64, January–March, 2008.     

An efficient algorithm for the generalized centro-symmetric solution of matrix equation <Emphasis Type="Italic">A X B</Emphasis> = <Emphasis Type="Italic">C</Emphasis>

In this paper, an iterative algorithm is constructed for solving linear matrix equation AXB = C over generalized centro-symmetric matrix X. We show that, by this algorithm, a solution or the least-norm solution of the matrix equation AXB = C can be obtained within finite iteration steps in the absence of roundoff errors; we also obtain the optimal approximation solution to a given matrix X ₀ in the solution set of which. In addition, given numerical examples show that the iterative method is efficient.     

On the competition of elastic energy and surface energy in discrete numerical schemes

The Γ-limit of certain discrete free energy functionals related to the numerical approximation of Ginzburg–Landau models is analysed when the distance h between neighbouring points tends to zero. The main focus lies on cases where there is competition between surface energy and elastic energy. Two discrete approximation schemes are compared, one of them shows a surface energy in the Γ-limit. Finally, numerical solutions for the sharp interface Cahn–Hilliard model with linear elasticity are investigated. It is demonstrated how the viscosity of the numerical scheme introduces an artificial surface energy that leads to unphysical solutions.      

A finite volume scheme for nonlinear parabolic equations derived from one-dimensional local dirichlet problems

In this paper, we propose a new method to compute the numerical flux of a finite volume scheme, used for the approximation of the solution of the nonlinear partial differential equation u_t+div(qf(u))−ΔΦ(u)=0 in a 1D, 2D or 3D domain. The function Φ is supposed to be strictly increasing, but some values s such that Φ′(s)=0 can exist. The method is based on the solution, at each interface between two control volumes, of the nonlinear elliptic two point boundary value problem (qf(υ)+(Φ(υ))′)′=0 with Dirichlet boundary conditions given by the values of the discrete approximation in both control volumes. We prove the existence of a solution to this two point boundary value problem. We show that the expression for the numerical flux can be yielded without referring to this solution. Furthermore, we prove that the so designed finite volume scheme has the expected stability properties and that its solution converges to the weak solution of the continuous problem. Numerical results show the increase of accuracy due to the use of this scheme, compared to some other schemes.     

Solving elliptical equations with high-contrast coefficients in an unbounded region

An approximation model is proposed for an elliptical equation with complex rapidly varying coefficients. An efficient numerical method is developed and implemented. A problem of geoelectricity requiring solution of an equation in this setting is investigated. This research was partially supported by the Russian Foundation for Basic Research (grant No. 96-05-64340) and by the Interuniversity Scientific Program “Russian Universities: Basic Research.” Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 37–45, 1998.     

Mining the discrete velocity method for high quality solutions for one-dimensional Poiseuille flow

A fully discretized solution for Poiseuille flow in a one-dimensional channel is presented. Unlike previous semi-analytical methods, such as the Analytical Discrete-Ordinates (ADO) or the FN methods, which have been specifically designed to avoid spatial discretization error, no analytical advantage is assumed. Instead, the solution is “mined” in a process where each discrete approximation is an element in a sequence of solutions whose convergence to the solution is accelerated. This process leads most straightforwardly to high quality benchmark results for use in algorithm verification with a minimum of theoretical and numerical complexity.     

Numerical Approximation of a Unilateral Obstacle Problem

We consider a reformulation of the unilateral obstacle problem presented by the authors (Addou and Mermri in Math-Rech. Appl. 2:59–69, 2000). This reformulation introduces a continuous function, whose subdifferential characterizes the noncontact domain. Our goal in this paper is to give a numerical approximation of the solution of the reformulated problem. We consider discretization of the problem based on finite element method. Then we prove the convergence of the approximate solution to the exact one. Some numerical tests on one-dimensional obstacle problem are provided.     

The QNET method for two-moment analysis of open queueing networks

Consider an open network of single-server stations, each with a first-in-first-out discipline. The network may be populated by various customer types, each with its own routing and service requirements. Routing may be either deterministic or stochastic, and the interarrival and service time distributions may be arbitrary. In this paper a general method for steady-state performance analysis is described and illustrated. This analytical method, called QNET, uses both first and second moment information, and it is motivated by heavy traffic theory. However, our numerical examples show that QNET compares favorably with W. Whitt's Queueing Network Analyzer (QNA) and with other approximation schemes, even under conditions of light or moderate loading. In the QNET method one first replaces the original queueing network by what we call an approximating Brownian system model, and then one computes the stationary distribution of the Brownian model. The second step amounts to solving a certain highly structured partial differential equation problem; a promising general approach to the numerical solution of that PDE problem is described by Harrison and Dai [8] in a companion paper. Thus far the numerical solution technique has been implemented only for two-station networks, and it is clear that the computational burden will grow rapidly as the number of stations increases. Thus we also describe and investigate a cruder approach to two-moment network analysis, called ΠNET, which is based on a product form approximation, or decomposition approximation, to the stationary distribution of the Brownian system model. In very broad terms, ΠNET is comparable to QNA in its level of sophistication, whereas QNET captures more subtle system interactions. In our numerical examples the performance of ΠNET and QNA is similar; the performance of QNET is generally better, sometimes much better.     

Equilibrium attractivity of Krylov-W-methods for nonlinear stiff ODEs

Since implicit integration schemes for differential equations which use Krylov methods for the approximate solution of linear systems depend nonlinearly on the actual solution a classical stability analysis is difficult to perform. A different, weaker property of autonomous dissipative systemsy′=f(y) is that the norm ‖f(y(t))‖ decreases for any solutiony(t). This property can also be analysed for W-methods using a Krylov-Arnoldi approximation. We discuss different additional assumptions onf and conditions on the Arnoldi process that imply this kind of attractivity to equilibrium points for the numerical solution. One assumption is general enough to cover quasilinear parabolic problems. This work was supported by Deutsche Forschungsgemeinschaft.     

On some optimality principles in multicriterial problems

We state two interpretations of an approximate solution of multicriterial problems: the concept of approximation with respect to a functional and approximation with respect to the argument of the set of Pareto-optimal strategies. We give propositions that justify numerical search for such approximations. In relation to these interpretations of the approximation of the set of Pareto-optimal strategies we study questions of the stability of multicriterial problems to computational errors. Bibliography: 14 titles. Translated fromMetody Matematicheskoi Fiziki, 1998, pp. 217–224.     

Analysis of search-extension method for finding multiple solutions of nonlinear problem

For numerical computations of multiple solutions of the nonlinear elliptic problemΔu f(u)=0 inΩ, u=0 onΓ, a search-extension method (SEM) was proposed and systematically studied by the authors. This paper shall complete its theoretical analysis. It is assumed that the nonlinearity is non-convex and its solution is isolated, under some conditions the corresponding linearized problem has a unique solution. By use of the compactness of the solution family and the contradiction argument, in general conditions, the high order regularity of the solution u∈H~(1 α),α>0 is proved. Assume that some initial value searched by suitably many eigenbases is already fallen into the neighborhood of the isolated solution, then the optimal error estimates of its nonlinear finite element approximation are shown by the duality argument and continuation method.     

Numerical method for coupling the macro and meso scales in stochastic chemical kinetics

A numerical method is developed for simulation of stochastic chemical reactions. The system is modeled by the Fokker–Planck equation for the probability density of the molecular state. The dimension of the domain of the equation is reduced by assuming that most of the molecular species have a normal distribution with a small variance. The numerical approximation preserves properties of the analytical solution such as non-negativity and constant total probability. The method is applied to a nine dimensional problem modelling an oscillating molecular clock. The oscillations stop at a fixed point with a macroscopic model but they continue with our two dimensional, mixed macroscopic and mesoscopic model. Dedicated to the memory of Germund Dahlquist (1925–2005). AMS subject classification (2000)  65M20, 65M60     

Error estimates for obstacle problems of higher order

For obstacle problems of higher order involving power growth functionals, a posteriori error estimates using methods in duality theory are proved. These estimates can be viewed as a reliable measure for the deviation of an approximation from the exact solution, which is independent of the concrete numerical scheme under consideration. Bibliography: 11 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 348, 2007, pp. 5–18.