Lecture Notes ni Mathematics Edited yb .A Dold dna .B Eckmann 953 evitaretI Solution of Nonlinear Systems of ~noitauqE Proceedings of a Meeting held at Oberwolfach, ,ynamreG Jan. 13 -Feb. ,5 1982 Edited yb .R Ansorge, .hT Meis, and .W TSrnig galreV-regnirpS Berlin Heidelberg New kroY 1982 Editors Rainer Ansorge Institut f~r Angewandte Mathematik, Universit~t Hamburg Bundesstr. 55, 2000 Hamburg ,31 Germany Theodor Meis Mathematisches Institut, Universit~t KSIn Weyertal 86-90, 5000 KSIn ,14 Germany Willi TSrnig Fachbereich Mathematik, TH Darmstadt SchloBgartenstr. ,7 6100 Darmstadt, Germany AMS Subject Classifications (1980): 65B05, 65F10, 65F15, 65G10, 65H10, 65H15, 65N 05, 65N 30, 70K10, 73D30, 76-04, 76D05, 76N10, 76S05 ISBN 0-387-11602-8 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-11602-8 Springer-Verlag New York Heidelberg Berlin This work is subject to copyright. llA rights era reserved, whether the whole or part of the lairetam si concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction yb photocopying machine or similar ,snaem dna storage ni data banks. Under 3£ 54 of the German Copyright waL where copies era made for other than private use, a eef is payable to "Verwertungsgesellschaft Wort", .hcinuM © yb galreV-regnirpS Berlin Heidelberg 1982 detnirP ni Germany Printing dna binding: Beltz Offsetdruck, Hemsbach/Bergstr. 0413/6412 012345- DROWEROF ehT meeting no Iterative Solution of Nonlinear smetsyS of Equations, held in the sehcsitamehtaM Forschungsinstitut Oberwolfach, Federal Republic of ,ynamreG during the six days of January 13 st to February 5 th 1982, saw attented yb forty eno mathematicians dna engineers from several countries. In all ~enty four lec- tures were given, thirteen of which are presented in these proceedings. sisahpmE saw no three main topics: multigrid methods, enotonom dna interval arith- metic iterations, dna applications in industrial practice. Several contmibutors reported no the effective esu of multigrid algorithms neve in bifurcation dna other highly nonlinear problems. ehT principle of error in- clusion yb snaem of interval arithmetics dna enotonom iterations sah been inves- tigated for several years. Recent secnavda in accelerating those iterations dna emos connections with the question of global convergence were reported no at the meeting. Finally there were stimulating contributions dna discussions no concrete numerical problems in scimanydorea dna emos other fields of engineering. eW want to thank the director of the Oberwolfach Institute, Prof. Barner, ohw evag su the opportunity to organize this meeting. eW also express our thanks to .rD Gipser dna Dipl.-Math. Kaspar, ohw coordinated the production of the -unam script, dna last but not least to the editors of the Lecture Notes series dna the Springer-Verlag for publishing this volume. ,grubmaH K~In, dna Darmstadt, June 2891 .R Ansorge, .hT Meis, .W T~rnig LIST SFROOTUBIRTNOC Alefeld, .G Prof. Dr. Kaspar, .B Dipl.-Math. Institut f. .wegnA kitamehtaM Fachbereich kitamehtaM Universit~t Karlsruhe HT tdatsmraD KaiserstraBe 21 SchloBgartenstraBe 7 oo57-D Karlsruhe oo16-D tdatsmraD Axelsson, .O Prof. .rD Meis, .hT Prof. .rD tnemtrapeD of scitamehtaM sehcsitamehtaM Institut University of negemjiN Universit~t nI~K 5256-LN ne~emjiN Weyertal 68 - 09 ooo5-D K~In 14 ,hcsubkcaH .W Prof. Dr. Mittelmann, .H .D Prof. .rD Abteilung f. kitamehtaM Abteilung kitamehtaM Universit~t muhcoB U~iversit~t dnumtroD Universit~tsstr. 15o, Geb. AN Postfach 005005 o364-D grubnereuQ-muhcoB oo64-D dnumtroD 05 ,gnunroH .U .rD ,reiamueN A. .rD Institut f. ehcsiremuN dnu Institut f. .wegnA kitamehtaM Instrumentelle kitamehtaM Universit~t Freiburg Universit~t retsnUM Hermann-Herder-Str. lo EinsteinstraBe 46 oo87-D Freibur~ oo44-D retsnUM V Nickel, .K Prof. .rD Potra, .F .A Prof. .rD Institut f. .wegnA kitamehtaM tnemtrapeD of scitamehtaM Universit~t Freiburg National Institute for Scientific .rtS-redreH-nnamreH lo dna Technical Creation oo87-D Freibur~ .dB Pacii 022 22697 Bukarest, ainamoR ,remmahteiN .W Prof. .rD Weiland, .C .rD Institut f. Prakt. kitamehtaM eguezgulF-BBM HbmG Universit~t Karlsruhe Postfach o611o8 EnglerstraBe 2 ooo8-D nehcnUM 08 oo57-D Karlsruhe .rD .W renreW hcierebhcaF kitamehtaM Universit~t zniaM SaarstraBe 12 oo56-D zniaM CONTENTS DIRGITLUM SDOHTEM ROF RAENILNON SMELBORP .O Axelsson: nO Global ecnegrevnoC of Iterative sdohteM 1 .W :hcsubkcaH Multi-Grid Solution of Continuation smelborP 02 .H .D Mittelmann: A Fast Solver for Nonlinear'Eigenvalue smelborP 64 ENOTONOM SNOITARETI DNA LANOITATUPMOC RORRE SDNUOB .H Cornelius dna .G Alefeld: A Device for the Acceleration of ecnegrevnoC 86 of a Monotonously Enclosing Iteration dohteM .B Kaspar: Overrelaxation in Monotonically Convergent 08 Iteration sdohteM .A :reiamueN Simple sdnuoB for Zeros of smetsyS of Equations 88 .K Nickel: saD Aufl~sungsverhalten nov nichtlinearen Fix- 601 nemetsyS-negnem .F .A Potra: nO the ecnegrevnoC of a Class of Newton-Like 521 sdohteM SNOITACILPPA DNA LAICEPS SCIPOT ._U :~nunroH sdohteM-IDA for Nonlinear Variational Inequali- 831 ties of Evolution .G Kolb dna .W :remmahteiN Relaxation sdohteM for the Computation of the 941 Spectral mroN .hT Meis dna .W :eksaaB Numerical Computation of Periodic Solutions of a 951 Nonlinear evaW Equation .C Weiland: Erfahrungen bei der gnudnewnA numerischer Ver- 271 fahren zur gnus~L nichtlinearer hyperbolischer Differentialgleichungssysteme .W :renreW nO the Simultaneous Determination of Polynomial 881 stooR ON GLOBAL CONVERGENCE OF ITERATIVE r~THODS O. Axelsson Department of Mathematics, University of Nijmegen The Netherlands We review and extend results on the local convergence of the classical Newton- Kantorovich method. Then we discuss globally convergent damped and inexact Newton methods and point out advantages of using a minimal error conjugate gradient method for the linear systems arising at each Newton step. Finally application on a nonlinear elliptic problem is considered. A combina- tion of nested iterations, dammed inexact Newton method and two-level grid finite element methods for the solution of the linear boundary value problems encountered at each step are discussed. .I Introduction For the solution of a nonlinear problem F(x) = 0 , F : X ~- X, X a Banachspace, to which we assume that there exists a solution x, we consider methods on the form (1.1) C k(x k+1 - kx ) = -TkF(xk). Here C k is nonsingular and in some sauce makes CkIF(x k) locally close to the solu- tion and approximately behave like x k - "x_ There are two main types of choices of Ck: )i( If there exists a linear operator A such that II F(x_ k) - A?I is almost inde- k pendent on x , then we let C k = A. In this case the problem is almost linear and we may use iterations of Picard type. An example is given in Section 2. (ii) If F is Fr4chet differentiable, then we may let C k = F'(Xk) and (1.1) becomes the classical Newton-Kantorovich method (with damping parameter ~k ) . We may also let C k be an approximation of F' (xj). The classical Newton method suffers from two disadvantages. Firstly, it is in general only locally convergent. This is discussed in Section 3. Secondly, at each step we have to solve a linear system of equations "exactly", and this may not be justified in particular when the approximations of the nonlinear system are far from the solution. Hence we consider inexact Newton methods where the Newton step is calculated by an iterative method and the iterations are stopped when the residual of the linear system is small enough. The global convergence is achieved when we use damped steplengths. Under the assumption of nonsingularity of F', we prove that there exists steplengths such that convergence is achieved for all initial approximations. However we point out that it may take many steps before we can achieve the superlinear convergence, which charac- terizes Newton type methods when we are close to a solution. This may be improved upon by use of a minimal error iterative algorithm instead of a minimal residual al- gorithm for the linear systems. Finally we discuss an application on nonlinear boundary value problems. We pro- pose a combination of a continuation method, through finer and finer meshes, with the use of a damped Newton method to solve the nonlinear system at each grid. The solution of the linear systems encountered at each Newton step, may be solved by finite elements and a multigrid method of two-level type. If we want a diseretiza- tion error O(h p) at the final mesh, with meshparameter h; the number of continuation steps will be O(Ilog hi). The computational complexity at each mesh is of optimal order, i.e. only proportional to the number of meshpoints. The order of the discre- tization error for the nonlinear nroblem follows directly from that valid for the corresponding linearized problems. 2. Picard iteration on a mildly nonlinear singular l~ perturbed boundary value problem. Consider the boundary value problem 2 -eV • ?u + b • Vu + cu = f(u) , x { 9 E R u = 0 on ~. ~f We assume that £ > 0, c ~ 0 and that ~u is bounded on ~. If the coefficients and the ~f boundary are smooth enough there exists a solution in C2(~) and if ~u S 0 on ~, it is unique. We discretize the problem by finite differences in such a way that the discre- tization operator h satisfies I. h is monotone (for instance, h is of Dositive type and is positive definite). 2. There exists a barrier function w 2 0 such that i h w ~ 6 > 0 V~ 6 O h. hl elU Definition 2.1. Let : max l ul ~e~ h We have then the following wellknown result, often called the Barrier-Lemma. For every u on 0 h with u = 0 on ~h' max w ~h (2.1) Iul0 h N min L h w ILh ul~ h " O h For the construction of a barrier function we assume that the first component of the velocity vector b = (bl,b 2) satisfies bl(~) ~ b 0 > 0 Vx ~ O . Let w(x,y) = Ixl~ - x 2 + 3R(Ixl~ + x) where R is the radius of a circle with center at the origin and which covers 0. We let L h be a central difference operator with h small enough (needed for positivity) or we use central differences for the second order term but upwind for the first order terms. Then we have w_>0 and L h w = 2e + b1(3R - 2x + Oh) + cw 2e + R b 0 V(x,y) £ 0 h , f 0 for central difference scheme where 0 i for upwind difference scheme. It follows from (2.1) that 6R 2 12.2) lul% < - 2~+~ ° IL h ul% We shall now solve the discretized equation (2.3) i h u h = f(uh) by Picard iteration, , (i-l), (2.4) i h u h (i) = ftuh , , i = 1,2, ... (0) where u h may be arbitrarily chosen. From (2.3), (2.4) we get (i)) ~f (i-i) Lh(Uh - Uh = ~u (Uh - Uh ) and by (2.2) we then get ul h u~i) I 6R2 I~-u(U(.))~f t ~ - - max - ~h 2c+R b 0 u ~h uh - u~i-l) "I Hence, if I~I is small enough ~l h ju h - u~ )i ~ plu h - u~i-l) I9 h , i = 1,2 .... )0( where 0 < p < I , and we have convergence for every u h Naturally, J~J small means that the problem is almost linear. 3. Newton-Kantorivich method, local convergence. Simplified proofs of classical results on local convergence of Newton-Kantoro- vich method (see Kantorovich 6, Rall i03, and Ortega, Rheinboldt 9) are pre- sented. The results are extended. We assume that the mapping F : X + X, where X is a Banach space, is continuous- ly Fr~chet differentiable with derivative F' nonsingular for all $ E X, with bound lll-)!( B = maxll F' . ~cx Further we assume that F' is Lipschitz continuous, (3.~) II~'(i) -F'(~)II ~KII!-~ll V~,n~ x, and that there exists a solution ~ of F(~) = 0. (A solution exists, and is unique, if in addition F is norm-coercive, i.e. limll F(~)II = +~ , II II~ ÷ =-) Let {67 } be the Newton sequence +I: -I , k: 0,I .... with ~O given. We have Theorem 3. .i Assume that d = ½~KII ! 1 - !011 < .I Then for any F satisfying the above conditions, we have 2 ~ d(2 )i Proof. Using the integral relation 1 (3.3) )_~(F = F(i) + F'(~) (n-~) + {f F'(~ + t(D-~)) - F'(!)dt}(~-- i) , 0