A modified Newton method with cubic convergence: the multivariate case. (English) Zbl 1059.65044

Homeier, H. H. H.

J. Comput. Appl. Math. 169, No. 1, 161-169 (2004).

Let \(m,n\in\mathbb{N}\), \(F: \mathbb{R}^m\to\mathbb{R}^n\) be a sufficiently differentiable mapping, \(x_0, x_n\in\mathbb{R}^m\), \(F_n:= F(x_n)\), and \(F_n':= F'(x_n)\) the Jacobi matrix at \(x_n\). The author considers the following multipoint method for the approximate computation of a zero of \(F\): \[ \text{For }n=1,2,\dots: F_n+ F_n'c_n= 0\Rightarrow c_n,\;F_n+ F'(x_n+\tfrac12 c_n) d_n= 0\Rightarrow d_n,\;x_{n+1}:= x_n+ d_n.\tag{+} \] He shows that (+) under appropiate conditions converges locally with order three to a simple zero of \(F\). Moreover, he uses two nontrivial examples to compare the computational results of (+) with those of Newton’s method but not, e.g. with the respective results of a similar multipoint method of – under appropiate assumptions – order three which differs from (+) in the second equation which is replaced by \(F(x_n+ c_n)+ F_n'c_n= 0\) (and then \(x_{n+1}:= x_n+ c_n+ d_n)\).
In this case, the two systems of linear equations in question to be solved in each iteration step have the same coefficient matrix, respectively [Comp., e.g., W. E. Bosarge, jun. and P. L. Falb, J. Optimization Theory Appl. 4, 155–166 (1969; Zbl 0172.18703)]. Finally, the author shortly discusses how certain numerical difficulties – e.g., if the Jadobi matrix at the zero of \(F\) is singular – could be dealt with, and under what conditions (+) may converge globally.

Reviewer: B. Döring (Düsseldorf)

MSC:

65H10

Numerical computation of solutions to systems of equations

Keywords:

systems of nonlinear equations; multipoint method of order three; generalized Bloch equation; convergence; comparison of methods; rootfinding; Newton method; coupled algebraic equations; affine-invariant Newton technique; hybrid method

Citations:

Zbl 0172.18703

Software:

Maple; GIANT

References:

[1]	Char, B.W; Geddes, K.O; Gonnet, G.H; Leong, B.L; Monagan, M.B; Watt, S.M, Maple V language reference manual, (1991), Springer Berlin
[2]	Char, B.W; Geddes, K.O; Gonnet, G.H; Leong, B.L; Monagan, M.B; Watt, S.M, Maple V library reference manual, (1991), Springer Berlin
[3]	D. Dent, M. Paprzycki, A. Kucaba-Pietal, Performance of solvers for systems of nonlinear equations, in: Proceedings of the 15th Annual Conference on Applied Mathematics, University of Central Oklahoma, Edmond, OK, 1999, pp. 67-77. · Zbl 0943.65058
[4]	Dent, D; Paprzycki, M; Kucaba-Pietal, A, Studying the numerical properties of solvers for systems of nonlinear equations, (), 113-118 · Zbl 0943.65058
[5]	D. Dent, M. Paprzycki, A. Kucaba-Pietal, Testing convergence of nonlinear system solvers, in: Proceedings of the First Southern Symposium on Computing, The University of Southern Mississippi, December 4-5, 1998, 1999. http://pax.st.usm.edu/cmi/fscc98_html/processed/.
[6]	Dent, D; Paprzycki, M; Kucaba-Pietal, A, Recent advances in solvers for nonlinear algebraic equations, Comput. assist. mech. eng. sci. (CAMES), 7, 493-505, (2000) · Zbl 0974.65051
[7]	Dent, D; Paprzycki, M; Kucaba-Pietal, A, Studying the performance nonlinear systems solvers applied to the random vibration test, (), 471-478 · Zbl 1031.65068
[8]	D. Dent, M. Paprzycki, A. Kucaba-Pietal, Comparing solvers for large systems of nonlinear algebraic equations, in: Proceedings of the Southern Conference on Computing, The University of Southern Mississippi, October 26-28, 2000, 2002. http://www.sc.usm.edu/conferences/scc2/papers/Dent-etal.ps. · Zbl 0974.65051
[9]	Deuflhard, P, A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting, Numer. math., 22, 289-315, (1974) · Zbl 0313.65070
[10]	Deuflhard, P, A relaxation strategy for the modified Newton method, (), 59-73
[11]	Homeier, H.H.H, A modified Newton method for root finding with cubic convergence, J. comput. appl. math., 157, 227-230, (2003) · Zbl 1070.65541
[12]	Meißner, H; Paldus, J, Direct iterative solution of the generalized Bloch equation. II. A general formalism for many-electron systems, J. chem. phys., 113, 7, 2594-2611, (2000)
[13]	Meißner, H; Paldus, J, Direct iterative solution of the generalized Bloch equation. III. application to H_{2}-cluster models, J. chem. phys., 113, 7, 2612-2621, (2000)
[14]	Meißner, H; Paldus, J, Direct iterative solution of the generalized Bloch equation. IV. application to H_{2} lih, beh, and CH2, J. chem. phys., 113, 7, 2622-2637, (2000)
[15]	U. Nowak, L. Weimann, GIANT—a software package for the numerical solution of very large systems of highly nonlinear equations, Technical Report TR 90-11, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1990. available from the ZIB ftp-server.
[16]	U. Nowak, L. Weimann, A family of Newton codes for systems of highly nonlinear equations, Technical Report TR 91-10, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1991. available from the ZIB ftp-server.
[17]	Paldus, J, Coupled cluster theory, (), 99-194
[18]	Powell, M.J.D, A hybrid method for nonlinear equations, (), 87-114 · Zbl 0277.65028
[19]	Rheinboldt, W.C, Methods for solving system of nonlinear equations, (1998), SIAM Philadelphia