Weighted finite difference methods for a class of space fractional partial differential equations with variable coefficients

A class of weighted finite difference methods (WFDMs) for solving a class of initial-boundary value problems of space fractional partial differential equations with variable coefficients is presented. Their stability and convergence properties are considered. It is proven that the WFDMs are unconditionally-stable for , and conditionally-stable for , here r is the weighting parameter subjected to 0≤r≤1. Some convergence results are given. These methods, problems and results generalize the corresponding methods, problems and results given in [7], [8] and [10]. Some numerical examples are provided to show the effectiveness of the methods with different weighting parameters.     

On acceleration methods for coupled nonlinear elliptic systems

Summary We compare both numerically and theoretically three techniques for accelerating the convergence of a nonlinear fixed point iterationuT(u), arising from a coupled elliptic system: Chebyshev acceleration, a second order stationary method, and a nonlinear version of the Generalized Minimal Residual Algorithm (GMRES) which we call NLGMR. All three approaches are implemented in Jacobian-free mode, i.e., only a subroutine which returnsT(u) as a function ofu is required.We present a set of numerical comparisons for the drift-diffusion semiconductor model. For the mappingT which corresponds to the nonlinear block Gauß-Seidel algorithm for the solution of this nonlinear elliptic system, NLGMR is found to be superior to the second order stationary method and the Chebychev acceleration. We analyze the local convergence of the nonlinear iterations in terms of the spectrum [T _u (u ^(*))] of the derivativeT _u at the solutionu ^(*). The convergence of the original iteration is governed by the spectral radius [T _U (u ^(*))]. In contrast, the convergence of the two second order accelerations are related to the convex hull of [T _u (u ^(*))], while the convergence of the GMRES-based approach is related to the local clustering in [I–T _u (u ^(*))]. The spectrum [I–T _u (u ^(*))] clusters only at 1 due to the successive inversions of elliptic partial differential equations inT. We explain the observed superiority of GMRES over the second order acceleration by its ability to take advantage of this clustering feature, which is shared by similar coupled nonlinear elliptic systems.     

On the convergence of the multivariate “homogeneous”qd-algorithm

The convergence of columns in the univariateqd-algorithm to reciprocals of polar singularities of meromorphic functions has often proved to be very useful. A multivariateqd-algorithm was discovered in 1982 for the construction of the so-called homogeneous Padé approximants.In the first section we repeat the univariate convergence results. In the second section we summarize the homogeneous multivariateqd-algorithm. In the third section a multivariate convergence result is proved by combining results from the previous sections. This convergence result is compared with another theorem for the general order multivariateqdg-algorithm. The main difference lies in the fact that the homogeneous form detects the polar singularities pointwise while the general form detects them curvewise.     

On rates of acceleration of extrapolation methods for oscillatory infinite integrals

The purpose of this work is to complement and expand our knowledge of the convergence theory of some extrapolation methods for the accurate computation of oscillatory infinite integrals. Specifically, we analyze in detail the convergence properties of theW- and -transformations of the author as they are applied to three integrals, all with totally different behavior at infinity. The results of the analysis suggest different convergence and acceleration of convergence behavior for the above mentioned transformations on the different integrals, and they improve considerably those that can be obtained from the existing convergence theories.     

Convergence rates for the approximations of the solutions to algebraic Riccati Equations with unbounded coefficients: case of analytic semigroups

Summary Approximations schemes for the solutions of the Algebraic Riccati Equations will be considered. We shall concentrate on the case when the input operator is unbounded and the dynamics of the system is described by an analytic semigroup. The main goal of the paper is to establish the optimal rates of convergence of the underlying approximations. By optimal, we mean such approximations which would reconstruct the optimal regularity of the original solutions as well as the best approximation properties of the finite-dimensional subspaces. It turns out that, if one aims to obtain the optimal rates in the case of unbounded input operators, the choice of the approximations to the generator, as well as to the control operator, is very critical. While the convergence results hold with any consistent approximations, the optimal rates require a careful selection of the approximating schemes. Our theoretical results will be illustrated by several examples of boundary/point control problems where the optimal rates of convergence are achieved with the appropriate numerical algorithms.Research partially supported by the NSF Grant DMS-8301668 and by the AFOSR Grant AFOSR 89-0511     

A spectral Galerkin approximation of the Orr-Sommerfeld eigenvalue problem in a semi-infinite domain

Summary The convergence of a Galerkin approximation of the Orr-Sommerfeld eigenvalue problem, which is defined in a semi-infinite domain, is studied theoretically. In case the system of trial functions is based on a composite of Jacobi polynomials and an exponential transform of the semi-infinite domain, the error of the Galerkin approximation is estimated in terms of the transformation parametera and the numberN of trial functions. Finite or infinite-order convergence of the spectral Galerkin method is obtained depending on how the transformation parameter is chosen. If the transformation parameter is fixed, then convergence is of finite order only. However, ifa is varied proportional to 1/N with an exponent 0<<1, then the approximate eigenvalue converges faster than any finite power of 1/N asN. Some numerical examles are given.     

On quadratic convergence bounds for theJ-symmetric Jacobi method

Summary This paper deals with quadratic convergence estimates for the serialJ-symmetric Jacobi method recently proposed by Veseli. The method is characterized by the use of orthogonal and hyperbolic plane rotations. Using a new technique recently introduced by Hari we prove sharp quadratic convergence bounds in the general case of multiple eigenvalues.     

Extended product integration rules

In this paper we introduce a class of extended product quadrature rules to associate with the corresponding standard product rules, and present an algorithm for their construction. A general discussion on the convergence of such formulas is then given. Finally some examples and applications are considered.Work sponsored by the Ministero della Pubblica Istruzione of Italy.     

Block SSOR preconditionings for high order 3d fe systems

For solving 3D high order hierarchical FE systems the block SSOR preconditioned CG algorithms based on new stripwise block two-color orderings of degrees of freedom and providing for efficient concurrent/vector implementation are suggested. As demonstrated by numerical results for the 3D Navier equations approximated using hierarchical orderp, 2 p 5, FE's the convergence rate of such BSSOR-CG algorithms is only slightly dependent onp and mesh nonunformity.     

On an iterative algorithm with superquadratic convergence for solving nonlinear operator equations

We study an iterative method with order for solving nonlinear operator equations in Banach spaces. Algorithms for specific operator equations are built up. We present the received new results of the local and semilocal convergence, in case when the first-order divided differences of a nonlinear operator are Hölder continuous. Moreover a quadratic nonlinear majorant for a nonlinear operator, according to the conditions laid upon it, is built. A priori and a posteriori estimations of the method’s error are received. The method needs almost the same number of computations as the classical Secant method, but has a higher order of convergence. We apply our results to the numerical solving of a nonlinear boundary value problem of second-order and to the systems of nonlinear equations of large dimension.     

A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix

Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn ²/4 processors, takingO(n log² n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center     

On the convergence rate of the conjugate gradients in presence of rounding errors

Summary We investigate here rounding error effects on the convergence rate of the conjugate gradients. More precisely, we analyse on both theoretical and experimental basis how finite precision arithmetic affects known bounds on iteration numbers when the spectrum of the system matrix presents small or large isolated eigenvalues.The present work was supported by the Programme d'impulsion en Technologie l'Information, financed by Belgian State, under contract No. IT/IF/14Supported by the Fonds National de la Recherche Scientifique, Chargé de recherches     

Parallel interval multisplittings

Summary We introduce interval multisplittings to enclose the setS={A^–1b|A[A], b[b]}, where [A] denotes an interval matrix and [b] an interval vector. The resulting iterative multisplitting methods have a natural parallelism. We investigate these methods with respect to convergence, speed of convergence and quality of the resulting enclosure forS.Dedicated to the memory of Peter Henrici     

Analysis of Atkinson’s variable transformation for numerical integration over smooth surfaces in ℝ3

Summary Recently, a variable transformation for integrals over smooth surfaces in ³ was introduced in a paper by Atkinson. This interesting transformation, which includes a grading parameter that can be fixed by the user, makes it possible to compute these integrals numerically via the product trapezoidal rule in an efficient manner. Some analysis of the approximations thus produced was provided by Atkinson, who also stated some conjectures concerning the unusually fast convergence of his quadrature formulas observed for certain values of the grading parameter. In a recent report by Atkinson and Sommariva, this analysis is continued for the case in which the integral is over the surface of a sphere and the integrand is smooth over this surface, and optimal results are given for special values of the grading parameter. In the present work, we give a complete analysis of Atkinsons method over arbitrary smooth surfaces that are homeomorphic to the surface of the unit sphere. We obtain optimal results that explain the actual rates of convergence, and we achieve this for all values of the grading parameter.     

An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.     

Convergence of sequential and asynchronous nonlinear paracontractions

Summary We establish the convergence of sequential and asynchronous iteration schemes for nonlinear paracontracting operators acting in finite dimensional spaces. Applications to the solution of linear systems of equations with convex constraints are outlined. A first generalization of one of our convergence results to an infinite pool of asymptotically paracontracting operators is also presented.Research supported in part by Sonderforschungsbereich 343 Diskrete Strukturen in der MathematikResearch supported in part by NSF Grant DMS-9007030 and by Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, Fakultät für Mathematik at the Universität BielefeldResearch supported in part by U.S. Air Force Grant AFOSR-88-0047, by NSF Grants DMS-8901860 and DMS-9007030, and by Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, Fakultät für Mathematik at the Universität Bielefeld     

Convergence properties of the Runge-Kutta-Chebyshev method

Summary The Runge-Kutta-Chebyshev method is ans-stage Runge-Kutta method designed for the explicit integration of stiff systems of ordinary differential equations originating from spatial discretization of parabolic partial differential equations (method of lines). The method possesses an extended real stability interval with a length proportional tos ². The method can be applied withs arbitrarily large, which is an attractive feature due to the proportionality of withs ². The involved stability property here is internal stability. Internal stability has to do with the propagation of errors over the stages within one single integration step. This internal stability property plays an important role in our examination of full convergence properties of a class of 1st and 2nd order schemes. Full convergence means convergence of the fully discrete solution to the solution of the partial differential equation upon simultaneous space-time grid refinement. For a model class of linear problems we prove convergence under the sole condition that the necessary time-step restriction for stability is satisfied. These error bounds are valid for anys and independent of the stiffness of the problem. Numerical examples are given to illustrate the theoretical results.Dedicated to Peter van der Houwen for his numerous contributions in the field of numerical integration of differential equations.Paper presented at the symposium Construction of Stable Numerical Methods for Differential and Integral Equations, held at CWI, March 29, 1989, in honor of Prof. Dr. P.J. van der Houwen to celebrate the twenty-fifth anniversary of his stay at CWI     

Average errors for zero finding: Lower bounds for smooth or monotone functions

Summary We study zero finding for functions fromC ^r ([0, 1]) withf(0) f(1) < 0 and for monotone functions fromC([0, 1]). We show that a lower bound ⁿ with a constant holds for the average error of any method usingn function or derivative evaluations. Here the average is defined with respect to conditionalr-fold Wiemer measures or Ulam measures, and the error is understood in the root or residual sense. As in the worst case, we therefore cannot obtain superlinear convergence even for classes of smooth functions which have only simple zeros.     

Numerical solution of a singularly perturbed problem via exponential splines

It is proved that a spline difference scheme for a singularly perturbed self-adjoint problem, derived by using exponential cubic splines at mid-points, has second order uniform convergence in a small parameter . Numerical experiments are presented to confirm the theoretical predictions.