OnM-functions and nonlinear relaxation methods

Globally convergent nonlinear relaxation methods are considered for a class of nonlinear boundary value problems (BVPs), where the discretizations are continuousM-functions.It is shown that the equations with one variable occurring in the nonlinear relaxation methods can always be solved by Newton's method combined with the Bisection method. The nonlinear relaxation methods are used to get an initial approximation in the domain of attraction of Newton's method. Numerical examples are given.     

Monotonically convergent iterative methods for nonlinear systems of equations

Summary This paper deals with discrete analogues of nonlinear elliptic boundary value problems and with monotonically convergent iterative methods for their numerical solution. The discrete analogues can be written asM(u)u+H(u)=0, whereM(u) is ann%n M-matrix for eachu ⁿ andH: ^{n n} . The numerical methods considered are the natural undeerrelaxation method, the successive underrelaxation method, and the Jacobi underrelaxation method. In the linear case and without underrelaxation these methods correspond to the direct, the Gauss-Seidel, and the Jacobi method for solving the underlying system of equations, resp. For suitable starting vectors and sufficiently strong underrelaxation, the sequence of iterates generated by any of these methods is shown to converge monotonically to a solution of the underlying system.     

On linear monotone iteration and Schwarz methods for nonlinear elliptic PDEs

Summary The Schwarz Alternating Method can be used to solve elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approximated by an infinite sequence of functions which results from solving a sequence of elliptic boundary value problems in each subdomain. In this paper, proofs of convergence of some Schwarz Alternating Methods for nonlinear elliptic problems which are known to have solutions by the monotone method (also known as the method of subsolutions and supersolutions) are given. In particular, an additive Schwarz method for scalar as well some coupled nonlinear PDEs are shown to converge to some solution on finitely many subdomains, even when multiple solutions are possible. In the coupled system case, each subdomain PDE is linear, decoupled and can be solved concurrently with other subdomain PDEs. These results are applicable to several models in population biology. This work was in part supported by a grant from the RGC of HKSAR, China (HKUST6171/99P)     

On the nonlinear domain decomposition method

Any domain decomposition or additive Schwarz method can be put into the abstract framework of subspace iteration. We consider generalizations of this method to the nonlinear case. The analysis shows under relatively weak assumptions that the nonlinear iteration converges locally with the same asymptotic speed as the corresponding linear iteration applied to the linearized problem.     

On the fast solutions of nonlinear elliptic equations

Summary In a recent paper we described a multi-grid algorithm for the numerical solution of Fredholm's integral equation of the second kind. This multi-grid iteration of the second kind has important applications to elliptic boundary value problems. Here we study the treatment of nonlinear boundary value problems. The required amount of computational work is proportional to the work needed for a sequence of linear equations. No derivatives are required since these linear problems are not the linearized equations.     

Block and asynchronous two-stage methods for mildly nonlinear systems

Block parallel iterative methods for the solution of mildly nonlinear systems of equations of the form are studied. Two-stage methods, where the solution of each block is approximated by an inner iteration, are treated. Both synchronous and asynchronous versions are analyzed, and both pointwise and blockwise convergence theorems provided. The case where there are overlapping blocks is also considered. The analysis of the asynchronous method when applied to linear systems includes cases not treated before in the literature. Received June 5, 1997 / Revised version received December 29, 1997     

On the stability of a class of convergence acceleration methods for power series

In this paper we study the problem of evaluating the sum of a power series whose terms are given numerically with a moderate accuracy. For a large class of divergent series a sum may be defined using analytic continuation. This sum may be estimated using the values of a finite number of terms. However, it is established here that the accuracy of this estimate will generally deteriorate if we use an ever-growing number of terms. A result on the stability of product quadrature is also obtained as a corollary of our main stability theorem.Dedicated to professor Germund Dahlquist, on the occasion of his 60th birthday     

On the computational efficiency index and some iterative methods for solving systems of nonlinear equations

In this paper two new iterative methods are built up and analyzed. A generalization of the efficiency index used in the scalar case to several variables in iterative methods for solving systems of nonlinear equations is revisited. Analytic proofs of the local order of convergence based on developments of multilineal functions and numerical concepts that will be used to illustrate the analytic results are given. An approximation of the computational order of convergence is computed independently of the knowledge of the root and the necessary time to get one correct decimal is studied in our examples.     

On nonlinear generalized conjugate gradient methods

Summary. The Generalized Conjugate Gradient method (see [1]) is an iterative method for nonsymmetric linear systems. We obtain generalizations of this method for nonlinear systems with nonsymmetric Jacobians. We prove global convergence results. Received April 29, 1992 / Revised version received November 18, 1993     

Superlinearly convergent PCG algorithms for some nonsymmetric elliptic systems

A preconditioned conjugate gradient method is applied to finite element discretizations of some nonsymmetric elliptic systems. Mesh independent superlinear convergence is proved, which is an extension of a similar earlier result from a single equation to systems. The proposed preconditioning method involves decoupled preconditioners, which yields small and parallelizable auxiliary problems.     

Partitioned quasi-Newton methods for nonlinear equality constrained optimization

We derive new quasi-Newton updates for the (nonlinear) equality constrained minimization problem. The new updates satisfy a quasi-Newton equation, maintain positive definiteness on the null space of the active constraint matrix, and satisfy a minimum change condition. The application of the updates is not restricted to a small neighbourhood of the solution. In addition to derivation and motivational remarks, we discuss various numerical subtleties and provide results of numerical experiments.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the US Department of Energy under grant DE-FG02-86ER25013.A000, and by the US Army Research Office through the Mathematical Sciences Institute, Cornell University.     

A p-version finite element method for nonlinear elliptic variational inequalities in 2D

This article introduces and analyzes a p-version FEM for variational inequalities resulting from obstacle problems for some quasi-linear elliptic partial differential operators. We approximate the solution by controlling the obstacle condition in images of the Gauss–Lobatto points. We show existence and uniqueness for the discrete solution u _p from the p-version for the obstacle problem. We prove the convergence of u _p towards the solution with respect to the energy norm, and assuming some additional regularity for the solution we derive an a priori error estimate. In numerical experiments the p-version turns out to be superior to the h-version concerning the convergence rate and the number of unknowns needed to achieve a certain exactness of the approximation.     

Multilevel iterative methods for mixed finite element discretizations of elliptic problems

Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable.     

On algebraic multi-level methods for non-symmetric systems - Comparison results

We establish theoretical comparison results for algebraic multi-level methods applied to non-singular non-symmetric M-matrices. We consider two types of multi-level approximate block factorizations or AMG methods, the AMLI and the MAMLI method. We compare the spectral radii of the iteration matrices of these methods. This comparison shows, that the spectral radius of the MAMLI method is less than or equal to the spectral radius of the AMLI method. Moreover, we establish how the quality of the approximations in the block factorization effects the spectral radii of the iteration matrices. We prove comparisons results for different approximations of the fine grid block as well as for the used Schur complement. We also establish a theoretical comparison between the AMG methods and the classical block Jacobi and block Gauss-Seidel methods.     

On computation of solution curves for semilinear elliptic problems

We consider computation of solution curves for semilinear elliptic equations. In case solution is stable, we present an algorithm with monotone convergence, which is a considerable improvement of the corresponding schemes in [4] and [5]. For the unstable solutions, we show how to construct a fourth-order evolution equation, for which the same solution will be stable.     

Some new acceleration methods for periodic-linearly convergent power series

The aim of this paper is to study the acceleration properties of the Cauchy-type approximants defined by Brezinski for periodic-linearly convergent power series. In the case where the sufficient conditions for acceleration are not satisfied, we also propose a new acceleration method for these power series based on those approximants.     

A power series method for computing singular solutions to nonlinear analytic systems

Summary Given a system of analytic equations having a singular solution, we show how to develop a power series representation for the solution. This series is computable, and when the multiplicity of the solution is small, highly accurate estimates of the solution can be generated for a moderate computational cost. In this paper, a theorem is proven (using results from several complex variables) which establishes the basis for the approach. Then a specific numerical method is developed, and data from numerical experiments are given.     

Additive Schwarz methods for the Crouzeix-Raviart mortar finite element for elliptic problems with discontinuous coefficients

In this paper, we propose two variants of the additive Schwarz method for the approximation of second order elliptic boundary value problems with discontinuous coefficients, on nonmatching grids using the lowest order Crouzeix-Raviart element for the discretization in each subdomain. The overall discretization is based on the mortar technique for coupling nonmatching grids. The convergence behavior of the proposed methods is similar to that of their closely related methods for conforming elements. The condition number bound for the preconditioned systems is independent of the jumps of the coefficient, and depend linearly on the ratio between the subdomain size and the mesh size. The performance of the methods is illustrated by some numerical results. This work has been supported by the Alexander von Humboldt Foundation and the special funds for major state basic research projects (973) under 2005CB321701 and the National Science Foundation (NSF) of China (No.10471144) This work has been supported in part by the Bergen Center for Computational Science, University of Bergen     

On some classes of variationally derived Quasi-Newton methods for systems of nonlinear algebraic equations

Summary We consider the problem of solving systems of nonlinear algebraic equations by Quasi-Newton methods which are variationally obtainable. Properties of termination and of optimal conditioning of this class are studied. Extensive numerical experiments compare particular algorithms and show the superiority of two recently proposed methods.     

Finite element methods for semilinear elliptic stochastic partial differential equations

We study finite element methods for semilinear stochastic partial differential equations. Error estimates are established. Numerical examples are also presented to examine our theoretical results. This research is supported by Air Force Office of Scientific Research under the grant number FA9550-05-1-0133 and 985 Project of Jilin University.