Multilevel ILU decomposition

Summary. In this paper, the multilevel ILU (MLILU) decomposition is introduced. During an incomplete Gaussian elimination process new matrix entries are generated such that a special ordering strategy yields distinct levels. On these levels, some smoothing steps are computed. The MLILU decomposition exists and the corresponding iterative scheme converges for all symmetric and positive definite matrices. Convergence rates independent of the number of unknowns are shown numerically for several examples. Many numerical experiments including unsymmetric and anisotropic problems, problems with jumping coefficients as well as realistic problems are presented. They indicate a very robust convergence behavior of the MLILU method. Received June 13, 1997 / Revised version received March 17, 1998     

Accelerated Gauss-Newton algorithms for nonlinear least squares problems

Recent theoretical and practical investigations have shown that the Gauss-Newton algorithm is the method of choice for the numerical solution of nonlinear least squares parameter estimation problems. It is shown that when line searches are included, the Gauss-Newton algorithm behaves asymptotically like steepest descent, for a special choice of parameterization. Based on this a conjugate gradient acceleration is developed. It converges fast also for those large residual problems, where the original Gauss-Newton algorithm has a slow rate of convergence. Several numerical test examples are reported, verifying the applicability of the theory.     

Generalized p-FEM in homogenization

Summary. A new finite element method for elliptic problems with locally periodic microstructure of length is developed and analyzed. It is shown that the method converges, as , to the solution of the homogenized problem with optimal order in and exponentially in the number of degrees of freedom independent of . The computational work of the method is bounded independently of . Numerical experiments demonstrate the feasibility and confirm the theoretical results. Received September 11, 1998 / Published online April 20, 2000     

Numerical solution of a secular equation

Summary. A method is proposed for the solution of a secular equation, arising in modified symmetric eigenvalue problems and in several other areas. This equation has singularities which make the application of standard root-finding methods difficult. In order to solve the equation, a class of transformations of variables is considered, which transform the equation into one for which Newton's method converges from any point in a certain given interval. In addition, the form of the transformed equation suggests a convergence accelerating modification of Newton's method. The same ideas are applied to the secant method and numerical results are presented. Received July 1, 1994     

An optimal order multigrid method for biharmonic,C 1 finite element equations

Summary In this paper, we study a special multigrid method for solving large linear systems which arise from discretizing biharmonic problems by the Hsieh-Clough-Tocher,C ¹ macro finite elements or several otherC ¹ finite elements. Since the multipleC ¹ finite element spaces considered are not nested, the nodal interpolation operator is used to transfer functions between consecutive levels in the multigrid method. This method converges with the optimal computational order.     

Two-level Schwarz method for solving variational inequality with nonlinear source terms

In this paper, we extend the two-level Schwarz method to solve the variational inequality problems with nonlinear source terms, and establish a convergence theorem. The method converges within finite steps with an appropriate initial point. The numerical results show that the methods are efficient.     

On local Hermitian and skew-Hermitian splitting iteration methods for generalized saddle point problems

In this paper, we first present a local Hermitian and skew-Hermitian splitting (LHSS) iteration method for solving a class of generalized saddle point problems. The new method converges to the solution under suitable restrictions on the preconditioning matrix. Then we give a modified LHSS (MLHSS) iteration method, and further extend it to the generalized saddle point problems, obtaining the so-called generalized MLHSS (GMLHSS) iteration method. Numerical experiments for a model Navier-Stokes problem are given, and the results show that the new methods outperform the classical Uzawa method and the inexact parameterized Uzawa method.     

An operator splitting method for nonlinear convection-diffusion equations

Summary. We present a semi-discrete method for constructing approximate solutions to the initial value problem for the -dimensional convection-diffusion equation . The method is based on the use of operator splitting to isolate the convection part and the diffusion part of the equation. In the case , dimensional splitting is used to reduce the -dimensional convection problem to a series of one-dimensional problems. We show that the method produces a compact sequence of approximate solutions which converges to the exact solution. Finally, a fully discrete method is analyzed, and demonstrated in the case of one and two space dimensions. ReceivedFebruary 1, 1996 / Revised version received June 24, 1996     

Multigrid algorithms for a vertex–centered covolume method for elliptic problems

Summary. We analyze V–cycle multigrid algorithms for a class of perturbed problems whose perturbation in the bilinear form preserves the convergence properties of the multigrid algorithm of the original problem. As an application, we study the convergence of multigrid algorithms for a covolume method or a vertex–centered finite volume element method for variable coefficient elliptic problems on polygonal domains. As in standard finite element methods, the V–cycle algorithm with one pre-smoothing converges with a rate independent of the number of levels. Various types of smoothers including point or line Jacobi, and Gauss-Seidel relaxation are considered. Received August 19, 1999 / Revised version received July 10, 2000 / Published online June 7, 2001     

Ein selektives Projektions-Iterationsverfahren und Anwendungen auf Verzweigungsprobleme

Summary In the present paper a projection-iteration procedure for solving nonlinear operator-equations is described in abstract spaces. The method possesses a selection property by yielding only those solutions which have certain stability properties. Parameter-dependent equations and bifurcation problems are considered as well. It is shown that in the case of bifurcation near a simple eigenvalue, the method converges locally always to the stable solution except for initial values on a proper submanifold. Numerical results for a nonlinear boundary-value problem are given illustrating this selection character.

Diese Arbeit wurde von der Deutschen Forschungsgemeinschaft unter Ki 131/2 gefördert     

Finite difference reaction–diffusion equations with nonlinear diffusion coefficients

Summary. A monotone iterative method for numerical solutions of a class of finite difference reaction-diffusion equations with nonlinear diffusion coefficient is presented. It is shown that by using an upper solution or a lower solution as the initial iteration the corresponding sequence converges monotonically to a unique solution of the finite difference system. It is also shown that the solution of the finite difference system converges to the solution of the continuous equation as the mesh size decreases to zero. Received February 18, 1998 / Revised version received April 21, 1999 / Published online February 17, 2000     

A multi-grid method with a priori and a posteriori level choice for the regularization of nonlinear ill-posed problems

Summary In this paper we study a multi-grid method for the numerical solution of nonlinear systems of equations arising from the discretization of ill-posed problems, where the special eigensystem structure of the underlying operator equation makes it necessary to use special smoothers. We provide uniform contraction factor estimates and show that a nested multigrid iteration together with an a priori or a posteriori chosen stopping index defines a regularization method for the ill-posed problem, i.e., a stable solution method, that converges to an exact solution of the underlying infinite-dimensional problem as the data noise level goes to zero, with optimal rates under additional regularity conditions. Supported by the Fonds zur F?rderung der wissenschaftlichen Forschung under grant T 7-TEC and project F1308 within Spezialforschungsbereich 13     

The modified method of characteristics with adjusted advection

Summary. The MMOC procedure for approximating the solutions of transport-dominated diffusion problems does not automatically preserve integral conservation laws, leading to (mass) balance errors in many kinds of flow problems. The variant, called the MMOCAA, discussed herein preserves the conservation law at a minor additional computational cost. It is shown that its solution, in either Galerkin or finite difference form, converges at the same rates as were proved earlier by Dougl as and Russell for the standard MMOC procedure. Received June 25, 1997 / Revised version received October 6, 1998 / Published online: July 7, 1999     

Convergence of the multigrid full approximation scheme for a class of elliptic mildly nonlinear boundary value problems

Summary The multigrid full approximation scheme (FAS MG) is a well-known solver for nonlinear boundary value problems. In this paper we restrict ourselves to a class of second order elliptic mildly nonlinear problems and we give local conditions, e.g. a local Lipschitz condition on the derivative of the continuous operator, under which the FAS MG with suitably chosen parameters locally converges. We prove quantitative convergence statements and deduce explicit bounds for important quantities such as the radius of a ball of guaranteed convergence, the number of smoothings needed, the number of coarse grid corrections needed and the number of FAS MG iterations needed in a nested iteration. These bounds show well-known features of the FAS MG scheme.     

Global convergence of the nonmonotone MBFGS method for nonconvex unconstrained minimization

In this paper, we propose a new nonmonotone Armijo type line search and prove that the MBFGS method proposed by Li and Fukushima with this new line search converges globally for nonconvex minimization. Some numerical experiments show that this nonmonotone MBFGS method is efficient for the given test problems.     

Convergence of a penalty-finite element approximation for an obstacle problem

Summary This study establishes an error estimate for a penalty-finite element approximation of the variational inequality obtained by a class of obstacle problems. By special identification of the penalty term, we first show that the penalty solution converges to the solution of a mixed formulation of the variational inequality. The rate of convergence of the penalization is where is the penalty parameter. To obtain the error of finite element approximation, we apply the results obtained by Brezzi, Hager and Raviart for the mixed finite element method to the variational inequality.     

Numerical solutions for some coupled systems of nonlinear boundary value problems

Summary In the well-known Volterra-Lotka model concerning two competing species with diffusion, the densities of the species are governed by a coupled system of reaction diffusion equations. The aim of this paper is to present an iterative scheme for the steady state solutions of a finite difference system which corresponds to the coupled nonlinear boundary value problems. This iterative scheme is based on the method of upper-lower solutions which leads to two monotone sequences from some uncoupled linear systems. It is shown that each of the two sequences converges to a nontrivial solution of the discrete equations. The model under consideration may have one, two or three nonzero solutions and each of these solutions can be computed by a suitable choice of initial iteration. Numerical results are given for these solutions under both the Dirichlet boundary condition and the mixed type boundary condition.     

Some new results on Unsymmetric Successive Overrelaxation method

Summary The Unsymmetric Successive Overrelaxation (USSOR) iterative method is applied to the solution of the system of linear equationsA x=b, whereA is annxn nonsingular matrix. We find the values of the relaxation parameters and for which the USSOR iterative method converges. Then we characterize those matrices which are equimodular toA and for which the USSOR iterative method converges.     

Effective preconditioning of Uzawa type schemes for a generalized Stokes problem

Summary. The Schur complement of a model problem is considered as a preconditioner for the Uzawa type schemes for the generalized Stokes problem (the Stokes problem with the additional term in the motion equation). The implementation of the preconditioned method requires for each iteration only one extra solution of the Poisson equation with Neumann boundary conditions. For a wide class of 2D and 3D domains a theorem on its convergence is proved. In particular, it is established that the method converges with a rate that is bounded by some constant independent of . Some finite difference and finite element methods are discussed. Numerical results for finite difference MAC scheme are provided. Received May 2, 1997 / Revised version received May 10, 1999 / Published online May 8, 2000     

Block monotone iterative methods for numerical solutions of nonlinear elliptic equations

Summary. Two block monotone iterative schemes for a nonlinear algebraic system, which is a finite difference approximation of a nonlinear elliptic boundary-value problem, are presented and are shown to converge monotonically either from above or from below to a solution of the system. This monotone convergence result yields a computational algorithm for numerical solutions as well as an existence-comparison theorem of the system, including a sufficient condition for the uniqueness of the solution. An advantage of the block iterative schemes is that the Thomas algorithm can be used to compute numerical solutions of the sequence of iterations in the same fashion as for one-dimensional problems. The block iterative schemes are compared with the point monotone iterative schemes of Picard, Jacobi and Gauss-Seidel, and various theoretical comparison results among these monotone iterative schemes are given. These comparison results demonstrate that the sequence of iterations from the block iterative schemes converges faster than the corresponding sequence given by the point iterative schemes. Application of the iterative schemes is given to a logistic model problem in ecology and numerical ressults for a test problem with known analytical solution are given. Received August 1, 1993 / Revised version received November 7, 1994