On accelerating the convergence of the successive approximations method

Emil Cătinaş
(original), Fixed point theory, inexact/perturbed iterations, local convergence, nonlinear systems in Rn, Numerical Analysis, paper, solving F(x)=0 iteratively, successive approximations

Abstract

No q-superlinear convergence to a fixed point \(x^\ast\) of a nonlinear mapping \(G\) may be attained by the successive approximations when \(G^\prime(x^\ast)\) has no eigenvalue equal to 0, as shown by us in [8].

However, high q-convergence orders may be attained if one considers perturbed successive approximations.

We characterize the correction terms which must be added at each step in order to obtain convergence with q-order 2 of the resulted iterates.

Authors

Emil Cătinaş
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

Keywords

fixed point problems; acceleration of convergence; nonlinear system of equations in Rn; inexact Newton method; linear systems of equation in Rn; residual; local convergence; q-convergence order.

Cite this paper as:

E. Cătinaş, On accelerating the convergence of the successive approximations method, Rev. Anal. Numér. Théor. Approx., 30 (2001) no. 1, pp. 3-8, https://ictp.acad.ro/jnaat/journal/article/view/2001-vol30-no1-art1

PDF

Latex-pdf version of the paper.

About this paper

Journal

Revue d’Analyse Numérique et de Théorie de l’Approximation

Publisher Name

Editions de l’Academie Romaine

Paper on the journal website

https://doi.org/10.33993/jnaat301-675

Print ISSN

1222-9024

Online ISSN

2457-8126

MR

1222-9024

Online ISSN

2457-8126

Google Scholar citations

Google Scholar citations

[1] I.  Argyros,  F.  Szidarovszky, The  Theory  and  Applications  of  Iteration  Methods, CRC Press, Boca Raton, 1993.

[2] I. Argyros, On the convergence of the modified contractions, J. Comp. Appl. Math., 55(1994), 183–189.

[3] E. Catinas, Newton and Newton-Krylov methods for solving nonlinear systems in Rn, PhD Thesis, Babes-Bolyai University of Cluj-Napoca, Cluj-Napoca, Romania, 1999.

[4] E. Catinas, On the high convergence orders of the Newton-GMBACK methods, Rev. Anal. Numer. Theor. Approx., 28 (1999) no. 2, 125-132.

[5] E. Catinas, A note on the quadratic convergence of the inexact Newton methods, Rev. Anal. Numer. Theor. Approx. 29 (2000) no. 2, 129-133.

[6] E. Catinas, Inexact  perturbed  Newton  methods  and  applications  to  a  class  of  Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3, 543-570.

[7] E. Catinas, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, submitted.

[8] E. Catinas, On the superlinear convergence of the successive approximations method, submitted.

[9] R.S. Dembo, S.C. Eisenstat, T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal., 19 (1982), 400-408.

[10] J.E. Dennis, Jr., J. J. More, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28 (1974), 549-560.

[11] J.E. Dennis, Jr., R.B. Schnabel, Numerical Methods for Unconstrained Optimization and  Nonlinear  Equations, Prentice-Hall Series in Computational Mathematics, Engle-wood Cliffs, 1983.

[12] P.  Deuflhard,  F.  A.  Potra, Asymptotic  mesh  independence  of  Newton-Galerkin methods via a refined Mysovskii theorem, SIAM J. Numer. Anal.,29 (1992), 1395-1412.

[13] S.C.  Eisenstat,  H.F.  Walker, Choosing  the  forcing  terms  in  an  inexact  Newton method, SIAM J. Sci. Comput.,17(1996), 16-32.

[14] Emil Catinas, N.J.  Higham, Accuracy  and  Stability  of  Numerical  Algorithms,  SIAM,  Philadelphia,1996.

[15] V.I. Istratescu, Introduction  to  the  Fixed  Points  Theory,  Editura  Academiei  RSR, Bucharest, Romania, 1973 (in Romanian).

[16] C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, Pennsylvania, 1995.

[17] St. Maruster, Quasi-nonexpansivity and two classical methods for solving nonlinear equations, Proc. AMS, 62 (1977), 119-123

[18] St. Maruser, Numerical  Methods  for  Solving  Nonlinear  Equations, Editura Tehnica, Bucharest, Romania, 1981 (in Romanian).

[19] J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970.

[20] A.M. Ostrowski, Solution  of  Equations  and  Systems  of  Equations, Academic Press, New York, 1966.

[21] I.Pavaloiu, Introduction to the Theory of Approximating the Solutions of Equations, Editura Dacia, Cluj-Napoca, Romania, 1976 (in Romanian).

[22] F.A. Potra, V. Ptak, Nondiscrete Induction and Iterative Processes, Pitman, London,1984.

[23] F.A. Potra, On Q-order  and R-order  of  convergence,  J. Optim. Theory Appl., 63 (1989), 415–431.

[24] F.A. Potra, Q-superlinear  convergence  of  the  iterates  in  primal-dual  interior-point methods, Math. Progr., to appear.

[25] W.C.  Rheinboldt, Methods  for  Solving  Systems  of  Nonlinear  Equations,  SIAM, Philadelphia, 1998.

[26] H.F. Walker, An  approach  to  continuation  using  Krylov  subspace  methods,  Computational Science in the 21st Century, M.-O. Bristeau, G. Etgen, W. Fitzgibbon, J. L.Lions, J. Periaux and M. F. Wheeler, editors, John Wiley and Sons, Ltd., 72-82, 1997

Paper (preprint) in HTML form

jnaat,+Journal+manager,+2001+Catinas+-+ANTA+-+On+acceler+the+conv+of+the+succ+approx+meth+16-10-07.p

ACCELERATING THE CONVERGENCE OF THE SUCCESSIVE APPROXIMATIONS*

EMIL CĂTINAŞ † † ^(†){ }^{\dagger}†

Abstract

In a previous paper of us, we have shown that no q q qqq-superlinear convergence to a fixed point x ∗ x ∗ x^(**)x^{*}x∗ of a nonlinear mapping G G GGG may be attained by the successive approximations when G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗) has no eigenvalue equal to 0 . However, high convergence orders may theoretically be attained if one considers perturbed successive approximations.

We characterize here the correction terms which must be added at each step in order to obtain convergence with q q qqq-order 2 of the resulted iterates.

MSC 2000. 47 H 10 , 65 H 10 47 H 10 , 65 H 10 47H10,65H1047 \mathrm{H} 10,65 \mathrm{H} 1047H10,65H10.
Keywords. Successive approximations, inexact Newton methods, quadratic convergence.

1. INTRODUCTION

We are interested in the convergence of the successive approximations
(1) x k + 1 = G ( x k ) , k = 0 , 1 , … (1) x k + 1 = G x k , k = 0 , 1 , … {:(1)x_(k+1)=G(x_(k))","quad k=0","1","dots:}\begin{equation*} x_{k+1}=G\left(x_{k}\right), \quad k=0,1, \ldots \tag{1} \end{equation*}(1)xk+1=G(xk),k=0,1,…
to a fixed point x ∗ ∈ int ( D ) x ∗ ∈ int ( D ) x^(**)in int(D)x^{*} \in \operatorname{int}(D)x∗∈int(D) of the nonlinear mapping G : D ⊆ R n → D G : D ⊆ R n → D G:D subeR^(n)rarr DG: D \subseteq \mathbb{R}^{n} \rightarrow DG:D⊆Rn→D. A classical result on the local convergence of these sequences is given by the Ostrowski theorem. First we remind the definitions of the convergence orders.
Let ‖ ⋅ ‖ ‖ ⋅ ‖ ||*||\|\cdot\|‖⋅‖ denote a given norm on R n R n R^(n)\mathbb{R}^{n}Rn.
Definition 1. [19, ch. 9] Let ( x k ) k ≥ 0 ⊂ R n x k k ≥ 0 ⊂ R n (x_(k))_(k >= 0)subR^(n)\left(x_{k}\right)_{k \geq 0} \subset \mathbb{R}^{n}(xk)k≥0⊂Rn be an arbitrary sequence converging to some x ∗ ∈ R n x ∗ ∈ R n x^(**)inR^(n)x^{*} \in \mathbb{R}^{n}x∗∈Rn. The quotient and the root convergence factors are defined for each α ∈ [ 1 , + ∞ ) α ∈ [ 1 , + ∞ ) alpha in[1,+oo)\alpha \in[1,+\infty)α∈[1,+∞) as
Q α { x k } = { 0 , if x k = x ∗ , for all but finitely many k , lim sup k → ∞ ‖ x k + 1 − x ∗ ‖ ‖ x k − x ∗ ‖ α , if x k ≠ x ∗ , for all but finitely many k , + ∞ , otherwise , R α { x k } = { lim sup k → ∞ ‖ x k − x ∗ ‖ 1 / α k , when α > 1 , lim sup k → ∞ ‖ x k − x ∗ ‖ 1 / k , when α = 1 . Q α x k = 0 ,  if  x k = x ∗ ,  for all but finitely many  k , lim sup k → ∞   x k + 1 − x ∗ x k − x ∗ α ,  if  x k ≠ x ∗ ,  for all but finitely many  k , + ∞ ,  otherwise  , R α x k = lim sup k → ∞   x k − x ∗ 1 / α k ,  when  α > 1 , lim sup k → ∞   x k − x ∗ 1 / k ,  when  α = 1 . {:[Q_(alpha){x_(k)}={[0","," if "x_(k)=x^(**)","" for all but finitely many "k","],[l i m   s u p_(k rarr oo)(||x_(k+1)-x^(**)||)/(||x_(k)-x^(**)||^(alpha))","," if "x_(k)!=x^(**)","" for all but finitely many "k","],[+oo","," otherwise "","]:}],[R_(alpha){x_(k)}={[l i m   s u p_(k rarr oo)||x_(k)-x^(**)||^(1//alpha^(k))","," when "alpha > 1","],[l i m   s u p_(k rarr oo)||x_(k)-x^(**)||^(1//k)","," when "alpha=1.]:}]:}\begin{aligned} & Q_{\alpha}\left\{x_{k}\right\}= \begin{cases}0, & \text { if } x_{k}=x^{*}, \text { for all but finitely many } k, \\ \limsup _{k \rightarrow \infty} \frac{\left\|x_{k+1}-x^{*}\right\|}{\left\|x_{k}-x^{*}\right\|^{\alpha}}, & \text { if } x_{k} \neq x^{*}, \text { for all but finitely many } k, \\ +\infty, & \text { otherwise },\end{cases} \\ & R_{\alpha}\left\{x_{k}\right\}= \begin{cases}\limsup _{k \rightarrow \infty}\left\|x_{k}-x^{*}\right\|^{1 / \alpha^{k}}, & \text { when } \alpha>1, \\ \limsup _{k \rightarrow \infty}\left\|x_{k}-x^{*}\right\|^{1 / k}, & \text { when } \alpha=1 .\end{cases} \end{aligned}Qα{xk}={0, if xk=x∗, for all but finitely many k,lim supk→∞‖xk+1−x∗‖‖xk−x∗‖α, if xk≠x∗, for all but finitely many k,+∞, otherwise ,Rα{xk}={lim supk→∞‖xk−x∗‖1/αk, when α>1,lim supk→∞‖xk−x∗‖1/k, when α=1.
The q q qqq - and r r rrr-convergence orders are defined by
O Q { x k } = { + ∞ , if Q α { x k } = 0 , ∀ α ∈ [ 1 , + ∞ ) , inf { α ∈ [ 1 , + ∞ ) : Q α { x k } = + ∞ } , otherwise O R { x k } = { + ∞ , if R α { x k } = 0 , ∀ α ∈ [ 1 , + ∞ ) , inf { α ∈ [ 1 , + ∞ ) : R α { x k } = 1 } , otherwise O Q x k = + ∞ ,  if  Q α x k = 0 , ∀ α ∈ [ 1 , + ∞ ) , inf α ∈ [ 1 , + ∞ ) : Q α x k = + ∞ ,  otherwise  O R x k = + ∞ ,  if  R α x k = 0 , ∀ α ∈ [ 1 , + ∞ ) , inf α ∈ [ 1 , + ∞ ) : R α x k = 1 ,  otherwise  {:[O_(Q){x_(k)}={[+oo","quad" if "Q_(alpha){x_(k)}=0","quad AA alpha in[1","+oo)","],[i n f{alpha in[1,+oo):Q_(alpha){x_(k)}=+oo}","quad" otherwise "]:}],[O_(R){x_(k)}={[+oo","quad" if "R_(alpha){x_(k)}=0","quad AA alpha in[1","+oo)","],[i n f{alpha in[1,+oo):R_(alpha){x_(k)}=1}","quad" otherwise "]:}]:}\begin{aligned} O_{Q}\left\{x_{k}\right\} & =\left\{\begin{array}{l} +\infty, \quad \text { if } Q_{\alpha}\left\{x_{k}\right\}=0, \quad \forall \alpha \in[1,+\infty), \\ \inf \left\{\alpha \in[1,+\infty): Q_{\alpha}\left\{x_{k}\right\}=+\infty\right\}, \quad \text { otherwise } \end{array}\right. \\ O_{R}\left\{x_{k}\right\} & =\left\{\begin{array}{l} +\infty, \quad \text { if } R_{\alpha}\left\{x_{k}\right\}=0, \quad \forall \alpha \in[1,+\infty), \\ \inf \left\{\alpha \in[1,+\infty): R_{\alpha}\left\{x_{k}\right\}=1\right\}, \quad \text { otherwise } \end{array}\right. \end{aligned}OQ{xk}={+∞, if Qα{xk}=0,∀α∈[1,+∞),inf{α∈[1,+∞):Qα{xk}=+∞}, otherwise OR{xk}={+∞, if Rα{xk}=0,∀α∈[1,+∞),inf{α∈[1,+∞):Rα{xk}=1}, otherwise 
When Q 1 { x k } = 0 Q 1 x k = 0 Q_(1){x_(k)}=0Q_{1}\left\{x_{k}\right\}=0Q1{xk}=0 or R 1 { x k } = 0 R 1 x k = 0 R_(1){x_(k)}=0R_{1}\left\{x_{k}\right\}=0R1{xk}=0, the sequence converges q q qqq-, resp. r r rrr superlinearly; if Q α 0 { x k } < + ∞ Q α 0 x k < + ∞ Q_(alpha_(0)){x_(k)} < +ooQ_{\alpha_{0}}\left\{x_{k}\right\}<+\inftyQα0{xk}<+∞ for some α 0 > 1 α 0 > 1 alpha_(0) > 1\alpha_{0}>1α0>1, one may write
‖ x k + 1 − x ∗ ‖ = O ( ‖ x k − x ∗ ‖ α 0 ) , as k → ∞ . x k + 1 − x ∗ = O x k − x ∗ α 0 ,  as  k → ∞ . ||x_(k+1)-x^(**)||=O(||x_(k)-x^(**)||^(alpha_(0))),quad" as "k rarr oo.\left\|x_{k+1}-x^{*}\right\|=\mathcal{O}\left(\left\|x_{k}-x^{*}\right\|^{\alpha_{0}}\right), \quad \text { as } k \rightarrow \infty .‖xk+1−x∗‖=O(‖xk−x∗‖α0), as k→∞.
The q q qqq-convergence rates require conditions stronger than for the r r rrr-convergence rates: the q q qqq-convergence with a certain order implies r r rrr-convergence with at least the same order, the converse being false. We refer the reader to [19, ch. 9] and [23] (see also [25] ch. 3] and [24]) for other different relating results.
The fixed point x ∗ x ∗ x^(**)x^{*}x∗ is an attraction fixed point if there exists an open ball with center at x ∗ x ∗ x^(**)x^{*}x∗ such that for any initial approximation x 0 x 0 x_(0)x_{0}x0 from that ball, the sequence (1) converges to x ∗ x ∗ x^(**)x^{*}x∗. We shall denote by S S S\mathcal{S}S the set of all such sequences.
The q q qqq - and r r rrr-factors of the iterative process S S S\mathcal{S}S are then defined as
Q α ( S ) = sup { Q α { x k } : ( x k ) k ≥ 0 ∈ S } , respectively R α ( S ) = sup { R α { x k } : ( x k ) k ≥ 0 ∈ S } , Q α ( S ) = sup Q α x k : x k k ≥ 0 ∈ S ,       respectively  R α ( S ) = sup R α x k : x k k ≥ 0 ∈ S ,      {:[Q_(alpha)(S)=s u p{Q_(alpha){x_(k)}:(x_(k))_(k >= 0)inS}","," respectively "],[R_(alpha)(S)=s u p{R_(alpha){x_(k)}:(x_(k))_(k >= 0)inS}",",]:}\begin{array}{ll} Q_{\alpha}(\mathcal{S})=\sup \left\{Q_{\alpha}\left\{x_{k}\right\}:\left(x_{k}\right)_{k \geq 0} \in \mathcal{S}\right\}, & \text { respectively } \\ R_{\alpha}(\mathcal{S})=\sup \left\{R_{\alpha}\left\{x_{k}\right\}:\left(x_{k}\right)_{k \geq 0} \in \mathcal{S}\right\}, & \end{array}Qα(S)=sup{Qα{xk}:(xk)k≥0∈S}, respectively Rα(S)=sup{Rα{xk}:(xk)k≥0∈S},
the convergence orders being similarly defined as for a single sequence.
Now we can state the following classical result (see also [25, Th. 3.5]).
Theorem 1 (Ostrowski). [20, Th. 22.1], [19, Thms. 10.1.3, 10.1.4] Assume that the mapping G G GGG is differentiable at the fixed point x ∗ ∈ int ( D ) x ∗ ∈ int ( D ) x^(**)in int(D)x^{*} \in \operatorname{int}(D)x∗∈int(D). If the spectral radius of G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗) satisfies
σ = ρ ( G ′ ( x ∗ ) ) < 1 σ = ρ G ′ x ∗ < 1 sigma=rho(G^(')(x^(**))) < 1\sigma=\rho\left(G^{\prime}\left(x^{*}\right)\right)<1σ=ρ(G′(x∗))<1
then x ∗ x ∗ x^(**)x^{*}x∗ is an attraction fixed point. Moreover, R 1 ( S ) = σ R 1 ( S ) = σ R_(1)(S)=sigmaR_{1}(\mathcal{S})=\sigmaR1(S)=σ, and if σ > 0 σ > 0 sigma > 0\sigma>0σ>0 then O R ( S ) = O Q ( S ) = 1 O R ( S ) = O Q ( S ) = 1 O_(R)(S)=O_(Q)(S)=1O_{R}(\mathcal{S})=O_{Q}(\mathcal{S})=1OR(S)=OQ(S)=1.
According to this theorem, when σ = 0 σ = 0 sigma=0\sigma=0σ=0, all the sequences from S S S\mathcal{S}S converge r r rrr-superlinearly; however, this does not imply that they also converge q q qqq-superlinearly (an example is given in [19, E10.1-6]; see also [25, p. 30]). A sufficient condition for q q qqq-superlinear convergence of S S S\mathcal{S}S is that G ′ ( x ∗ ) = 0 G ′ x ∗ = 0 G^(')(x^(**))=0G^{\prime}\left(x^{*}\right)=0G′(x∗)=0 [19, Th. 10.1.6] (see also [25, p. 30]). The q q qqq-convergence order of S S S\mathcal{S}S is even higher under some supplementary smoothness conditions: if G G GGG is continuously differentiable on an open neighborhood of the fixed point x ∗ ∈ int ( D ) , G x ∗ ∈ int ( D ) , G x^(**)in int(D),Gx^{*} \in \operatorname{int}(D), Gx∗∈int(D),G is twice differentiable at x ∗ x ∗ x^(**)x^{*}x∗ and G ′ ( x ∗ ) = 0 G ′ x ∗ = 0 G^(')(x^(**))=0G^{\prime}\left(x^{*}\right)=0G′(x∗)=0, then O R ( S ) ≥ O Q ( S ) ≥ 2 O R ( S ) ≥ O Q ( S ) ≥ 2 O_(R)(S) >= O_(Q)(S) >= 2O_{R}(\mathcal{S}) \geq O_{Q}(\mathcal{S}) \geq 2OR(S)≥OQ(S)≥2 [19, Th. 10.1.7] (see also [25, Th. 3.6]).
These sufficient conditions (which are not also necessary) ensure the high convergence orders of all the successive approximations near the fixed point, but the restrictions on G ′ G ′ G^(')G^{\prime}G′ are rather strong. In our paper [8] we have characterized the high convergence orders of only one sequence converging to x ∗ x ∗ x^(**)x^{*}x∗. We shall consider here only the q q qqq-order 2 .
Theorem 2. [8] Assume that the mapping G G GGG is differentiable on an open neighborhood of the fixed point x ∗ x ∗ x^(**)x^{*}x∗, with G ′ G ′ G^(')G^{\prime}G′ Lipschitz continuous at x ∗ x ∗ x^(**)x^{*}x∗, i.e. there exists L , ε > 0 L , ε > 0 L,epsi > 0L, \varepsilon>0L,ε>0 such that
‖ G ′ ( x ) − G ′ ( x ∗ ) ‖ ≤ L ‖ x − x ∗ ‖ , when ‖ x − x ∗ ‖ < ε . G ′ ( x ) − G ′ x ∗ ≤ L x − x ∗ ,  when  x − x ∗ < ε . ||G^(')(x)-G^(')(x^(**))|| <= L||x-x^(**)||,quad" when "||x-x^(**)|| < epsi.\left\|G^{\prime}(x)-G^{\prime}\left(x^{*}\right)\right\| \leq L\left\|x-x^{*}\right\|, \quad \text { when }\left\|x-x^{*}\right\|<\varepsilon .‖G′(x)−G′(x∗)‖≤L‖x−x∗‖, when ‖x−x∗‖<ε.
Suppose also that σ = ρ ( G ′ ( x ∗ ) ) < 1 σ = ρ G ′ x ∗ < 1 sigma=rho(G^(')(x^(**))) < 1\sigma=\rho\left(G^{\prime}\left(x^{*}\right)\right)<1σ=ρ(G′(x∗))<1. Let x 0 ∈ D x 0 ∈ D x_(0)in Dx_{0} \in Dx0∈D be an initial approximation such that the sequence of successive approximations converges to x ∗ x ∗ x^(**)x^{*}x∗. Then ( x k ) k ≥ 0 x k k ≥ 0 (x_(k))_(k >= 0)\left(x_{k}\right)_{k \geq 0}(xk)k≥0 converges with q q qqq-order 2 iff
(2) ‖ G ′ ( x k ) ( x k − G ( x k ) ) ‖ = O ( ‖ x k − G ( x k ) ‖ 2 ) , as k → ∞ (2) G ′ x k x k − G x k = O x k − G x k 2 ,  as  k → ∞ {:(2)||G^(')(x_(k))(x_(k)-G(x_(k)))||=O(||x_(k)-G(x_(k))||^(2))","quad" as "k rarr oo:}\begin{equation*} \left\|G^{\prime}\left(x_{k}\right)\left(x_{k}-G\left(x_{k}\right)\right)\right\|=\mathcal{O}\left(\left\|x_{k}-G\left(x_{k}\right)\right\|^{2}\right), \quad \text { as } k \rightarrow \infty \tag{2} \end{equation*}(2)‖G′(xk)(xk−G(xk))‖=O(‖xk−G(xk)‖2), as k→∞
This result allowed us to show that condition (2) is in fact equivalent to
G ′ ( x ∗ ) ( x k + 1 − x k ) = 0 , ∀ k ≥ k 0 , G ′ x ∗ x k + 1 − x k = 0 , ∀ k ≥ k 0 , G^(')(x^(**))(x_(k+1)-x_(k))=0,quad AA k >= k_(0),G^{\prime}\left(x^{*}\right)\left(x_{k+1}-x_{k}\right)=0, \quad \forall k \geq k_{0},G′(x∗)(xk+1−xk)=0,∀k≥k0,
i.e., from a certain step, the corrections x k + 1 − x k x k + 1 − x k x_(k+1)-x_(k)x_{k+1}-x_{k}xk+1−xk are eigenvectors correspond-
ing to the eigenvalue 0 of G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗). As a direct consequence, it followed that the trajectories with high convergence orders are restricted to affine subspaces.
Apart from the instability in the presence of errors implied by this result, it also means bad news when G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗) is invertible (i.e. all its eigenvalues are nonzero), since no trajectory may attain high convergence rates.
We are interested in accelerating the convergence of the successive approximations in the case 0 < σ < 1 0 < σ < 1 0 < sigma < 10<\sigma<10<σ<1 (or even when G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗) is nonsingular) by adding some correction terms δ k ∈ R n δ k ∈ R n delta_(k)inR^(n)\delta_{k} \in \mathbb{R}^{n}δk∈Rn, i.e., by considering the sequence
(3) x k + 1 = G ( x k ) + δ k , k = 0 , 1 , … (3) x k + 1 = G x k + δ k , k = 0 , 1 , … {:(3)x_(k+1)=G(x_(k))+delta_(k)","quad k=0","1","dots:}\begin{equation*} x_{k+1}=G\left(x_{k}\right)+\delta_{k}, \quad k=0,1, \ldots \tag{3} \end{equation*}(3)xk+1=G(xk)+δk,k=0,1,…
In [8] we have characterized the high convergence orders of this sequence, but δ k δ k delta_(k)\delta_{k}δk were viewed as error terms, and the above sequence was called as perturbed successive approximations. We shall present a new result which allows (at least theoretically) the computation of some terms δ k δ k delta_(k)\delta_{k}δk leading to q q qqq-quadratic convergence of the iterations (3).

2. ACCELERATED CONVERGENCE OF THE SUCCESSIVE APPROXIMATIONS

We have obtained the following result:
Theorem 3. [8] Suppose that G G GGG satisfies the assumptions of Theorem 2, and that the sequence (3) of perturbed successive approximations converges to x ∗ x ∗ x^(**)x^{*}x∗. Then the convergence is with q q qqq-order 2 iff
(4) ‖ G ′ ( x k ) ( x k − G ( x k ) ) + ( I − G ′ ( x k ) ) δ k ‖ = O ( ‖ x k − G ( x k ) ‖ 2 ) , as k → ∞ . (4) G ′ x k x k − G x k + I − G ′ x k δ k = O x k − G x k 2 ,  as  k → ∞ . {:(4)||G^(')(x_(k))(x_(k)-G(x_(k)))+(I-G^(')(x_(k)))delta_(k)||=O(||x_(k)-G(x_(k))||^(2))","" as "k rarr oo.:}\begin{equation*} \left\|G^{\prime}\left(x_{k}\right)\left(x_{k}-G\left(x_{k}\right)\right)+\left(I-G^{\prime}\left(x_{k}\right)\right) \delta_{k}\right\|=\mathcal{O}\left(\left\|x_{k}-G\left(x_{k}\right)\right\|^{2}\right), \text { as } k \rightarrow \infty . \tag{4} \end{equation*}(4)‖G′(xk)(xk−G(xk))+(I−G′(xk))δk‖=O(‖xk−G(xk)‖2), as k→∞.
We note that this result no longer requires G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗) to be singular.
We obtain an equivalent form of condition (4) in the following result:
Theorem 4. Suppose that G G GGG satisfies the assumptions of Theorem 2, that the sequence ( x k ) k ≥ 0 x k k ≥ 0 (x_(k))_(k >= 0)\left(x_{k}\right)_{k \geq 0}(xk)k≥0 given by (3) converges to x ∗ x ∗ x^(**)x^{*}x∗, and that the matrices I − G ′ ( x k ) I − G ′ x k I-G^(')(x_(k))I- G^{\prime}\left(x_{k}\right)I−G′(xk) are invertible starting from a certain step. Then the convergence is with q q qqq-order 2 iff
δ k = ( I − G ′ ( x k ) ) − 1 ( G ′ ( x k ) ( G ( x k ) − x k ) + γ k ) , δ k = I − G ′ x k − 1 G ′ x k G x k − x k + γ k ,  delta_(k)=(I-G^(')(x_(k)))^(-1)(G^(')(x_(k))(G(x_(k))-x_(k))+gamma_(k))", "\delta_{k}=\left(I-G^{\prime}\left(x_{k}\right)\right)^{-1}\left(G^{\prime}\left(x_{k}\right)\left(G\left(x_{k}\right)-x_{k}\right)+\gamma_{k}\right) \text {, }δk=(I−G′(xk))−1(G′(xk)(G(xk)−xk)+γk), 
where ( γ k ) k ≥ 0 ⊂ R n γ k k ≥ 0 ⊂ R n (gamma_(k))_(k >= 0)subR^(n)\left(\gamma_{k}\right)_{k \geq 0} \subset \mathbb{R}^{n}(γk)k≥0⊂Rn is an arbitrary sequence converging to zero with γ k = O ( ‖ x k − G ( x k ) ‖ 2 ) γ k = O x k − G x k 2 gamma_(k)=O(||x_(k)-G(x_(k))||^(2))\gamma_{k}= \mathcal{O}\left(\left\|x_{k}-G\left(x_{k}\right)\right\|^{2}\right)γk=O(‖xk−G(xk)‖2), as k → ∞ k → ∞ k rarr ook \rightarrow \inftyk→∞.
Proof. We can easily obtain this result from the previous theorem by denoting
γ k = G ′ ( x k ) ( x k − G ( x k ) ) + ( I − G ′ ( x k ) ) δ k γ k = G ′ x k x k − G x k + I − G ′ x k δ k gamma_(k)=G^(')(x_(k))(x_(k)-G(x_(k)))+(I-G^(')(x_(k)))delta_(k)\gamma_{k}=G^{\prime}\left(x_{k}\right)\left(x_{k}-G\left(x_{k}\right)\right)+\left(I-G^{\prime}\left(x_{k}\right)\right) \delta_{k}γk=G′(xk)(xk−G(xk))+(I−G′(xk))δk
and then computing δ k δ k delta_(k)\delta_{k}δk.
Under the assumption that ‖ G ′ ( x ) ‖ < q < 1 G ′ ( x ) < q < 1 ||G^(')(x)|| < q < 1\left\|G^{\prime}(x)\right\|<q<1‖G′(x)‖<q<1 for all x x xxx in a certain neighborhood of x ∗ x ∗ x^(**)x^{*}x∗, a natural choice (implied by the Banach lemma) for δ k δ k delta_(k)\delta_{k}δk is
δ k = ( I + ⋯ + G ′ ( x k ) i k ) G ′ ( x k ) ( G ( x k ) − x k ) , δ k = I + ⋯ + G ′ x k i k G ′ x k G x k − x k , delta_(k)=(I+cdots+G^(')(x_(k))^(i_(k)))G^(')(x_(k))(G(x_(k))-x_(k)),\delta_{k}=\left(I+\cdots+G^{\prime}\left(x_{k}\right)^{i_{k}}\right) G^{\prime}\left(x_{k}\right)\left(G\left(x_{k}\right)-x_{k}\right),δk=(I+⋯+G′(xk)ik)G′(xk)(G(xk)−xk),
with i k i k i_(k)i_{k}ik such that
q i k + 2 1 − q ≤ K ‖ x k − G ( x k ) ‖ q i k + 2 1 − q ≤ K x k − G x k (q^(i_(k)+2))/(1-q) <= K||x_(k)-G(x_(k))||\frac{q^{i_{k}+2}}{1-q} \leq K\left\|x_{k}-G\left(x_{k}\right)\right\|qik+21−q≤K‖xk−G(xk)‖
for some fixed K > 0 K > 0 K > 0K>0K>0.
This choice may be useful when the powers of G ′ ( x ) G ′ ( x ) G^(')(x)G^{\prime}(x)G′(x) and their sums are computationally inexpensive ( G ′ ( x ) G ′ ( x ) G^(')(x)G^{\prime}(x)G′(x) is sparse, etc.). However, it is known that for a matrix A ∈ R n × n A ∈ R n × n A inR^(n xx n)A \in \mathbb{R}^{n \times n}A∈Rn×n with ρ ( A ) < 1 ρ ( A ) < 1 rho(A) < 1\rho(A)<1ρ(A)<1, additional conditions are needed in order that A k → 0 A k → 0 A^(k)rarr0A^{k} \rightarrow 0Ak→0 in floating point arithmetic (see [14, ch. 17] for a discussion of this topic).
Also, the local convergence of these iterations remains to be studied.

REFERENCES

[1] I. Argyros, F. Szidarovszky, The Theory and Applications of Iteration Methods, CRC Press, Boca Raton, 1993.
[2] I. Argyros, On the convergence of the modified contractions, J. Comp. Appl. Math., 55 (1994), 183-189. ㄸ
[3] E. Cătinaş, Newton and Newton-Krylov methods for solving nonlinear systems in R n R n R^(n)\mathbb{R}^{n}Rn, PhD Thesis, Babeş-Bolyai University of Cluj-Napoca, Cluj-Napoca, Romania, 1999.
[4] E. Cătinaş, On the high convergence orders of the Newton-GMBACK methods, Rev. Anal. Numér. Théor. Approx., 28 (1999) no. 2, 125-132. ㄸ
[5] E. Cătinaş, A note on the quadratic convergence of the inexact Newton methods, Rev. Anal. Numér. Théor. Approx. 29 (2000) no. 2, 129-133. ㅈ
[6] E. Cătinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3, 543-570. ㄸ
[7] E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, submitted. 뜸
[8] E. Cătinaş, On the superlinear convergence of the successive approximations method, submitted. ©
[9] R.S. Dembo, S.C. Eisenstat, T. Steihaug, Inexact Newton methods, SiAM J. Numer. Anal., 19 (1982), 400-408. ㄸ
[10] J.E. Dennis, Jr., J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28 (1974), 549-560. ㄸ
[11] J.E. Dennis, Jr., R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall Series in Computational Mathematics, Englewood Cliffs, 1983.
[12] P. Deuflhard, F. A. Potra, Asymptotic mesh independence of Newton-Galerkin methods via a refined Mysovskii theorem, SIAM J. Numer. Anal., 29 (1992), 1395-1412. □
[13] S.C. Eisenstat, H.F. Walker, Choosing the forcing terms in an inexact Newton method, SIAM J. Sci. Comput., 17 (1996), 16-32. 뜸
[14] N.J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996.
[15] V.I. Istrăţescu, Introduction to the Fixed Points Theory, Editura Academiei RSR, Bucharest, Romania, 1973 (in Romanian).
[16] C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, Pennsylvania, 1995.
[17] Şt. Măruşter, Quasi-nonexpansivity and two classical methods for solving nonlinear equations, Proc. AMS, 62 (1977), 119-123. ©
[18] Şt. Måruşer, Numerical Methods for Solving Nonlinear Equations, Editura Tehnicǎ, Bucharest, Romania, 1981 (in Romanian).
[19] J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970.
[20] A.M. Ostrowski, Solution of Equations and Systems of Equations, Academic Press, New York, 1966.
[21] I.Păvăloiu, Introduction to the Theory of Approximating the Solutions of Equations, Editura Dacia, Cluj-Napoca, Romania, 1976 (in Romanian). ㄸ
[22] F.A. Potra, V. Pták, Nondiscrete Induction and Iterative Processes, Pitman, London, 1984.
[23] F.A. Potra, On Q-order and R-order of convergence, J. Optim. Theory Appl., 63 (1989), 415-431. ㄸ
[24] F.A. Potra, Q-superlinear convergence of the iterates in primal-dual interior-point methods, Math. Progr., to appear. ㅈ
[25] W.C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, SIAM, Philadelphia, 1998.
[26] H.F. Walker, An approach to continuation using Krylov subspace methods, Computational Science in the 21st Century, M.-O. Bristeau, G. Etgen, W. Fitzgibbon, J. L. Lions, J. Periaux and M. F. Wheeler, editors, John Wiley and Sons, Ltd., 72-82, 1997.
Received by the editors: October 10, 2000.
  1. *This work has been supported by the Romanian Academy of Sciences under Grant GAR 64/2001.
    † † ^(†){ }^{\dagger}† "T. Popoviciu" Institute of Numerical Analysis, P.O. Box 68-1, 3400 Cluj-Napoca, Romania (ecatinas@ictp.acad.ro).
2001

Related Posts