Parallel nonlinear multisplitting methods

Summary Linear multisplitting methods are known as parallel iterative methods for solving a linear systemAx=b. We extend the idea of multisplittings to the problem of solving a nonlinear system of equationsF(x)=0. Our nonlinear multisplittings are based on several nonlinear splittings of the functionF. In a parallel computing environment, each processor would have to calculate the exact solution of an individual nonlinear system belonging to his nonlinear multisplitting and these solutions are combined to yield the next iterate. Although the individual systems are usually much less involved than the original system, the exact solutions will in general not be available. Therefore, we consider important variants where the exact solutions of the individual systems are approximated by some standard method such as Newton's method. Several methods proposed in literature may be regarded as special nonlinear multisplitting methods. As an application of our systematic approach we present a local convergence analysis of the nonlinear multisplitting methods and their variants. One result is that the local convergence of these methods is determined by an induced linear multisplitting of the Jacobian ofF.Dedicated to the memory of Peter Henrici     

Comparison of Brown's and Newton's method in the monotone case

Summary In many cases when Newton's method, applied to a nonlinear sytemF(x)=0, produces a monotonically decreasing sequence of iterates, Brown's method converges monotonically, too. We compare the iterates of Brown's and Newton's method in these monotone cases with respect to the natural partial ordering. It turns out that in most of the cases arising in applications Brown's method then produces better iterates than Newton's method.     

A unified approach to methods for the simultaneous computation of all zeros of generalized polynomials

Summary Applying Newton's method to a particular system of nonlinear equations we derive methods for the simultaneous computation of all zeros of generalized polynomials. These generalized polynomials are from a function space satisfying a condition similar to Haar's condition. By this approach we bring together recent methods for trigonometric and exponential polynomials and a well-known method for ordinary polynomials. The quadratic convergence of these methods is an immediate consequence of our approach and needs not to be proved explicitly. Moreover, our approach yields new interesting methods for ordinary, trigonometric and exponential polynomials and methods for other functions occuring in approximation theory.     

Monotonieeigenschaften des Steffensen-Verfahrens

Steffensen's method is slightly generalized by introducing a real parameter. In this way one can get different monotonicity properties, depending on the choice of this parameter. These monotonicity statements give the possibility of bracketing the solution of a given problem. In a special case they even ensure the convergence and the existence of a solution. Furthermore there are given sufficient conditions, which show that Steffensen's method converges at least as quickly as Newton's method. A numerical example shows the efficiency of the theorems and compares Steffensen's and Newton's method.

     

Finite element simulations of window Josephson junctions

This paper deals with the numerical simulation of the steady state two dimensional window Josephson junctions by finite element method. The model is represented by a sine-Gordon type composite PDE problem. Convergence and error analysis of the finite element approximation for this semilinear problem are presented. An efficient and reliable Newton-preconditioned conjugate gradient algorithm is proposed to solve the resulting nonlinear discrete system. Regular solution branches are computed using a simple continuation scheme. Numerical results associated with interesting physical phenomena are reported. Interface relaxation methods, which by taking advantage of special properties of the composite PDE, can further reduce the overall computational cost are proposed. The implementation and the associated numerical experiments of a particular interface relaxation scheme are also presented and discussed.     

Global aspects of the continuous and discrete Newton method: A case study

Newton's method has recently become one of the paradigms in the revival of Julia set theory and complex dynamical systems. This paper, to a large extent experimental in nature, investigates Newton's method for some particular model problems as a real dynamical system of several simultaneous equations guided by the Julia set theory.     

Attractive cycles in the iteration of meromorphic functions

Summary The existence of attractive cycles constitutes a serious impediment to the solution of nonlinear equations by iterative methods. This problem is illustrated in the case of the solution of the equationz tanz=c, for complex values ofc, by Newton's method. Relevant results from the theory of the iteration of rational functions are cited and extended to the analysis of this case, in which a meromorphic function is iterated. Extensive numerical results, including many attractive cycles, are summarized.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under grants A3028 and A7691     

Interval solution of nonlinear equations using linear programming

A new computational test is proposed for nonexistence of a solution to a system of nonlinear equations in a convex polyhedral regionX. The basic idea proposed here is to formulate a linear programming problem whose feasible region contains all solutions inX. Therefore, if the feasible region is empty (which can be easily checked by Phase I of the simplex method), then the system of nonlinear equations has no solution inX. The linear programming problem is formulated by surrounding the component nonlinear functions by rectangles using interval extensions. This test is much more powerful than the conventional test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the proposed test to interval analysis, all solutions of nonlinear equations can be found very efficently. This work was partially supported by the Japanese Ministry of Education.     

Chord techniques and Newton's method for discrete bifurcation problems

Summary The numerical treatment of discrete bifurcation problems (2) with chord methods or Newton's method is a question of constructing appropriate initial approximations to prevent the sequence from converging to the trivial solution. This problem is being discussed under conditions which are satisfied for quite a few examples arising in applications (see Sect. 3).     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

Starlike domains of convergence for Newton's method at singularities

Summary Given a solutionx ^* of a system of nonlinear equationsf with singular Jacobian f(x ^*) we construct an open starlike domainR of initial points, from which Newton's method converges linearly tox ^*. Under certain conditions the union of those straight lines throughx ^*, that do not intersect withR is shown to form a closed set of measure zero, which is necessarily disjoint from any starlike domain of convergence. The results apply to first and higher order singularities.     

A quasi-Newton method for solving fixed point problems in Hilbert spaces

Summary We study the convergence properties of a projective variant of Newton's method for the approximation of fixed points of completely continuous operators in Hilbert spaces. We then discuss applications to nonlinear integral equations and we produce some numerical examples.     

On the efficient solution of nonlinear finite element equations. II

Summary We consider nonlinear variational inequalities corresponding to a locally convex minimization problem with linear constraints of obstacle type. An efficient method for the solution of the discretized problem is obtained by combining a slightly modified projected SOR-Newton method with the projected version of thec g-accelerated relaxation method presented in a preceding paper. The first algorithm is used to approximately reach in relatively few steps the proper subspace of active constraints. In the second phase a Kuhn-Tucker point is found to prescribed accuracy. Global convergence is proved and some numerical results are presented.     

A stepsize control for continuation methods and its special application to multiple shooting techniques

Summary A numerically applicable stepsize control for discrete continuation methods of orderp is derived on a theoretical basis. Both the theoretical results and the performance of the proposed algorithm are invariant under affine transformation of the nonlinear system to be solved. The efficiency and reliability of the method is demonstrated by solving three real life two-point boundary value problems using multiple shooting techniques. In two of the examples bifurcations occur and are significantly marked by sharp changes in the stepsize estimates.     

On the efficient solution of nonlinear finite element equations I

Summary On the efficient solution of nonlinear finite element equations. A fast numerical method is presented for the solution of nonlinear algebraic systems which arise from discretizations of elliptic boundary value problems. A simplified relaxation algorithm which needs no information about the Jacobian of the system is combined with a correspondingly modified conjugate gradient method. A global convergence proof is given and the number of operations required is compared with that of other algorithms which are equally applicable to a large class of problems. Numerical results verify the efficiency for some typical examples.     

L p estimates of boundary integral equations for some nonlinear boundary value problems

Summary Recently, Galerkin and collocation methods have been analyzed for boundary integral equation formulations of some potential problems in the plane with nonlinear boundary conditions, and stability results and error estimates in theH ^1/2-norm have been proved (Ruotsalainen and Wendland, and Ruotsalainen and Saranen). We show that these results extend toL ^p setting without any extra conditions. These extensions are proved by studying the uniform boundedness of the inverses of the linearized integral operators, and then considering the nonlinear equations. The fact that inH ^1/2 setting the nonlinear operator is a homeomorphism with Lipschitz continuous inverse plays a crucial role. Optimal error estimates for the Galerkin and collocation method inL ^p space then follow.This research was performed while the second author was visiting professor at the University of Delaware, spring 1989     

Nonlinear structural finite element analysis using the preconditioned Lanczos method on serial and parallel computers

The application of the Lanczos algorithm in Newton-like methods for solving non-linear systems of equations arising in nonlinear structural finite element analysis is presented. It is shown that with appropriate preconditioners iterative methods can be developed which are robust and efficient even for ill conditioned problems. Though the real advantage of iterative solvers seems to exist on distributed memory machines, even on serial machines the performance can be improved compared with direct solvers while saving memory capacity. With a specific modification of the Lanczos algorithm in combination with arc-length procedures a further speed-up of the nonlinear analysis can be achieved. For parallel implementations domain decomposition methods are used. A parallel preconditioning strategy based on an incomplete factorisation method is presented. An example is taken and the quality and efficiency of two different domain decomposition methods are discussed for a large shell structure. This work was supported by the BMBF (Bundesministerium für Bildung und Forschung) of Germany.     

A robust multigrid approach for variational image registration models

Variational registration models are non-rigid and deformable imaging techniques for accurate registration of two images. As with other models for inverse problems using the Tikhonov regularization, they must have a suitably chosen regularization term as well as a data fitting term. One distinct feature of registration models is that their fitting term is always highly nonlinear and this nonlinearity restricts the class of numerical methods that are applicable. This paper first reviews the current state-of-the-art numerical methods for such models and observes that the nonlinear fitting term is mostly ‘avoided’ in developing fast multigrid methods. It then proposes a unified approach for designing fixed point type smoothers for multigrid methods. The diffusion registration model (second-order equations) and a curvature model (fourth-order equations) are used to illustrate our robust methodology. Analysis of the proposed smoothers and comparisons to other methods are given. As expected of a multigrid method, being many orders of magnitude faster than the unilevel gradient descent approach, the proposed numerical approach delivers fast and accurate results for a range of synthetic and real test images.     

Accelerated Landweber iterations for the solution of ill-posed equations

Summary In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept.If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy.To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage.Numerical examples are given including a comparison to the method of conjugate gradients.This research was sponsored by the Deutsche Forschungsgemeinschaft (DFG).