Sufficient convergence conditions for certain accelerated successive approximations

Emil Cătinaş
(proceedings), Fixed point theory, inexact/perturbed iterations, paper, semilocal convergence, solving F(x)=0 iteratively, successive approximations

Abstract

We have recently characterized the q-quadratic convergence of the perturbed successive approximations. For a particular choice of the parameters, these sequences resulted as accelerated iterations toward a fixed point. We give here a Kantorovich-type result, which provides sufficient conditions ensuring the convergence of the accelerated iterates.

Authors

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

Emil Cătinaş

Keywords

fixed point; successive approximations; accelerated successive approximations; nonlinear system of equations in Rn; inexact Newton method; perturbed Newton method; ; local convergence; convergence order.

References

PDF

https://ictp.acad.ro/wp-content/uploads/2026/01/2005-Catinas-IBoMat-Sufficient-convergence-conditions-for-certain-accelerated-successive-approximations.pdf

Cite this paper as:

E. Cătinaş, Sufficient convergence conditions for certain accelerated successive approximations. In: Mache D.H., Szabados J., de Bruin M.G. (eds) Trends and Applications in Constructive Approximation. ISNM International Series of Numerical Mathematics, vol 151, pp. 71-75, 2005. Birkhäuser Basel

About this paper

Book

Trends and Applications in Constructive Approximation. ISNM International Series of Numerical Mathematics, vol 151.

Publisher Name

Birkhäuser Basel

DOI

10.1007/3-7643-7356-3_6

Print ISBN

978-3-7643-7124-1

Online ISBN

978-3-7643-7356-6

Google Scholar Profile

??

Paper (preprint) in HTML form

2005-Catinas-IBoMat-Sufficient-convergence-conditions-for-certain-accelerated-successive-approximati

Sufficient convergence conditions for certain accelerated successive approximations

Emil Cătinaş

Abstract

We have recently characterized the q q qqq-quadratic convergence of the perturbed successive approximations. For a particular choice of the parameters, these sequences resulted as accelerated iterations toward a fixed point.

We give here a Kantorovich-type result, which provides sufficient conditions ensuring the convergence of the accelerated iterates.

1 Introduction

Let ( X , ‖ ⋅ ‖ ) ( X , ‖ ⋅ ‖ ) (X,||*||)(X,\|\cdot\|)(X,‖⋅‖) be a Banach space and G : Ω ⊆ X → Ω G : Ω ⊆ X → Ω G:Omega sube X rarr OmegaG: \Omega \subseteq X \rightarrow \OmegaG:Ω⊆X→Ω a nonlinear mapping having x ∗ ∈ int Ω x ∗ ∈ int Ω x^(**)in int Omegax^{*} \in \operatorname{int} \Omegax∗∈intΩ as fixed point:
x ∗ = G ( x ∗ ) x ∗ = G x ∗ x^(**)=G(x^(**))x^{*}=G\left(x^{*}\right)x∗=G(x∗)
We are interested in the q q qqq-quadratic convergence toward x ∗ x ∗ x^(**)x^{*}x∗ of the sequences of successive approximation type. Recall that an arbitrary sequence ( y k ) k ≥ 0 ⊂ X y k k ≥ 0 ⊂ X (y_(k))_(k >= 0)sub X\left(y_{k}\right)_{k \geq 0} \subset X(yk)k≥0⊂X converges ( q q qqq-)quadratically to its limit y ¯ ∈ X y ¯ ∈ X bar(y)in X\bar{y} \in Xy¯∈X if [11], [12], [13]
inf { α ∈ [ 1 , + ∞ ) : Q α { y k } = + ∞ } = 2 inf α ∈ [ 1 , + ∞ ) : Q α y k = + ∞ = 2 i n f{alpha in[1,+oo):Q_(alpha){y_(k)}=+oo}=2\inf \left\{\alpha \in[1,+\infty): Q_{\alpha}\left\{y_{k}\right\}=+\infty\right\}=2inf{α∈[1,+∞):Qα{yk}=+∞}=2
where
Q α { y k } = { 0 , if y k = y ¯ , for all but finitely many k lim sup k → ∞ + ∞ , ‖ y k + 1 − y ¯ ‖ ‖ y k − y ¯ ‖ α , if y k ≠ y ¯ , for all but finitely many k otherwise Q α y k = 0 ,       if  y k = y ¯ ,  for all but finitely many  k lim sup k → ∞ + ∞ ,   y k + 1 − y ¯ y k − y ¯ α ,       if  y k ≠ y ¯ ,  for all but finitely many  k       otherwise  Q_(alpha){y_(k)}={[0","," if "y_(k)= bar(y)","" for all but finitely many "k],[l i m   s u p_({:[k rarr oo],[+oo","]:})(||y_(k+1)-( bar(y))||)/(||y_(k)-( bar(y))||^(alpha),)," if "y_(k)!= bar(y)","" for all but finitely many "k],[," otherwise "]:}Q_{\alpha}\left\{y_{k}\right\}= \begin{cases}0, & \text { if } y_{k}=\bar{y}, \text { for all but finitely many } k \\ \limsup _{\substack{k \rightarrow \infty \\+\infty,}} \frac{\left\|y_{k+1}-\bar{y}\right\|}{\left\|y_{k}-\bar{y}\right\|^{\alpha},} & \text { if } y_{k} \neq \bar{y}, \text { for all but finitely many } k \\ & \text { otherwise }\end{cases}Qα{yk}={0, if yk=y¯, for all but finitely many klim supk→∞+∞,‖yk+1−y¯‖‖yk−y¯‖α, if yk≠y¯, for all but finitely many k otherwise 
In the case when 0 < Q 2 { y k } < + ∞ 0 < Q 2 y k < + ∞ 0 < Q_(2){y_(k)} < +oo0<Q_{2}\left\{y_{k}\right\}<+\infty0<Q2{yk}<+∞, one obtains the well known estimate of the form
‖ y k + 1 − y ¯ ‖ ≤ ( Q p { y k } + ε ) ‖ y k − y ¯ ‖ 2 , for all k ≥ k 0 y k + 1 − y ¯ ≤ Q p y k + ε y k − y ¯ 2 ,  for all  k ≥ k 0 ||y_(k+1)-( bar(y))|| <= (Q_(p){y_(k)}+epsi)||y_(k)-( bar(y))||^(2),quad" for all "k >= k_(0)\left\|y_{k+1}-\bar{y}\right\| \leq\left(Q_{p}\left\{y_{k}\right\}+\varepsilon\right)\left\|y_{k}-\bar{y}\right\|^{2}, \quad \text { for all } k \geq k_{0}‖yk+1−y¯‖≤(Qp{yk}+ε)‖yk−y¯‖2, for all k≥k0
(in the sense that for all ε > 0 ε > 0 epsi > 0\varepsilon>0ε>0 there exists k 0 ≥ 0 k 0 ≥ 0 k_(0) >= 0k_{0} \geq 0k0≥0 such the above inequalities hold).
The successive approximations converging quadratically to x ∗ x ∗ x^(**)x^{*}x∗ are characterized by the following result.
Theorem 1.1 [6] Assume that G G GGG is differentiable on a neighborhood D D DDD of x ∗ x ∗ x^(**)x^{*}x∗, with the derivative G ′ G ′ G^(')G^{\prime}G′ Lipschitz continuous:
‖ G ′ ( x ) − G ′ ( y ) ‖ ≤ L ‖ x − y ‖ , ∀ x , y ∈ D . G ′ ( x ) − G ′ ( y ) ≤ L ‖ x − y ‖ , ∀ x , y ∈ D . ||G^(')(x)-G^(')(y)|| <= L||x-y||,quad AA x,y in D.\left\|G^{\prime}(x)-G^{\prime}(y)\right\| \leq L\|x-y\|, \quad \forall x, y \in D .‖G′(x)−G′(y)‖≤L‖x−y‖,∀x,y∈D.
Suppose further that for a certain initial approximation x 0 ∈ D x 0 ∈ D x_(0)in Dx_{0} \in Dx0∈D, the successive approximations
x k + 1 = G ( x k ) , k ≥ 0 x k + 1 = G x k , k ≥ 0 x_(k+1)=G(x_(k)),quad k >= 0x_{k+1}=G\left(x_{k}\right), \quad k \geq 0xk+1=G(xk),k≥0
converge to x ∗ x ∗ x^(**)x^{*}x∗, and 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 order 2 if and only if G ′ G ′ G^(')G^{\prime}G′ has a zero eigenvalue and, starting 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 corresponding eigenvectors:
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
This condition holds equivalently iff the errors x k − x ∗ x k − x ∗ x_(k)-x^(**)x_{k}-x^{*}xk−x∗ are corresponding eigenvectors:
G ′ ( x ∗ ) ( x k − x ∗ ) = 0 , ∀ k ≥ k 0 G ′ x ∗ x k − x ∗ = 0 , ∀ k ≥ k 0 G^(')(x^(**))(x_(k)-x^(**))=0,quad AA k >= k_(0)G^{\prime}\left(x^{*}\right)\left(x_{k}-x^{*}\right)=0, \quad \forall k \geq k_{0}G′(x∗)(xk−x∗)=0,∀k≥k0
or iff
x k ∈ x ∗ + Ker G ′ ( x ∗ ) , ∀ k ≥ k 0 x k ∈ x ∗ + Ker G ′ x ∗ , ∀ k ≥ k 0 x_(k)inx^(**)+KerG^(')(x^(**)),quad AA k >= k_(0)x_{k} \in x^{*}+\operatorname{Ker} G^{\prime}\left(x^{*}\right), \quad \forall k \geq k_{0}xk∈x∗+KerG′(x∗),∀k≥k0
This result implies that if G ′ G ′ G^(')G^{\prime}G′ has no eigenvalue 0 , there exists no sequence of successive approximations converging to x ∗ x ∗ x^(**)x^{*}x∗ with order 2 . 1 2 . 1 2.^(1)2 .{ }^{1}2.1 In such a case, one may choose to consider for some ( δ k ) k ≥ 0 ⊂ X δ k k ≥ 0 ⊂ X (delta_(k))_(k >= 0)sub X\left(\delta_{k}\right)_{k \geq 0} \subset X(δk)k≥0⊂X the perturbed successive approximations
(1) x k + 1 = G ( x k ) + δ k , k ≥ 0 (1) x k + 1 = G x k + δ k , k ≥ 0 {:(1)x_(k+1)=G(x_(k))+delta_(k)","quad k >= 0:}\begin{equation*} x_{k+1}=G\left(x_{k}\right)+\delta_{k}, \quad k \geq 0 \tag{1} \end{equation*}(1)xk+1=G(xk)+δk,k≥0
Their quadratic convergence is characterized by the following result, which does not require the existence of the eigenvalue 0 .
Theorem 1.2 [6] Suppose that G G GGG satisfies the assumptions of Theorem 1.1, and that the sequence (1) of perturbed successive approximations converges to x ∗ x ∗ x^(**)x^{*}x∗. Then the convergence is with q q qqq-order 2 iff
(2) ‖ G ′ ( x k ) ( x k − G ( x k ) ) + ( I − G ′ ( x k ) ) δ k ‖ = O ( ‖ x k − G ( x k ) ‖ 2 ) , as k → ∞ . (2) G ′ x k x k − G x k + I − G ′ x k δ k = O x k − G x k 2 ,  as  k → ∞ . {:(2)||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\|=O\left(\left\|x_{k}-G\left(x_{k}\right)\right\|^{2}\right), \text { as } k \rightarrow \infty . \tag{2} \end{equation*}(2)‖G′(xk)(xk−G(xk))+(I−G′(xk))δk‖=O(‖xk−G(xk)‖2), as k→∞.
In [5] we have shown that if we write
δ 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)δk=(I−G′(xk))−1(G′(xk)(G(xk)−xk)+γk)
with ( γ k ) k ≥ 0 ⊂ X γ k k ≥ 0 ⊂ X (gamma_(k))_(k >= 0)sub X\left(\gamma_{k}\right)_{k \geq 0} \subset X(γk)k≥0⊂X, then condition
γ k = O ( ‖ x k − G ( x k ) ‖ 2 ) , as k → ∞ , γ k = O x k − G x k 2 ,  as  k → ∞ , gamma_(k)=O(||x_(k)-G(x_(k))||^(2)),quad" as "k rarr oo,\gamma_{k}=O\left(\left\|x_{k}-G\left(x_{k}\right)\right\|^{2}\right), \quad \text { as } k \rightarrow \infty,γk=O(‖xk−G(xk)‖2), as k→∞,
is equivalent to (2).
We have also noticed in [5] that, under the assumption ‖ G ′ ( x ) ‖ ≤ q < 1 G ′ ( x ) ≤ q < 1 ||G^(')(x)|| <= q < 1\left\|G^{\prime}(x)\right\| \leq q<1‖G′(x)‖≤q<1 for all x x xxx in a certain neighborhood of x ∗ x ∗ x^(**)x^{*}x∗, and for a given K > 0 K > 0 K > 0K>0K>0, 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
(3) q i k + 2 1 − q ≤ K ‖ x k − G ( x k ) ‖ (3) q i k + 2 1 − q ≤ K x k − G x k {:(3)(q^(ik)+2)/(1-q) <= K||x_(k)-G(x_(k))||:}\begin{equation*} \frac{q^{i k}+2}{1-q} \leq K\left\|x_{k}-G\left(x_{k}\right)\right\| \tag{3} \end{equation*}(3)qik+21−q≤K‖xk−G(xk)‖
When applying Theorem 1.2 to characterize the quadratic convergence of the resulted sequence
(4) x k + 1 = G ( x k ) + ( I + ⋯ + G ′ ( x k ) i k ) G ′ ( x k ) ( G ( x k ) − x k ) , k ≥ 0 (4) x k + 1 = G x k + I + ⋯ + G ′ x k i k G ′ x k G x k − x k , k ≥ 0 {:(4)x_(k+1)=G(x_(k))+(I+cdots+G^(')(x_(k))^(i_(k)))G^(')(x_(k))(G(x_(k))-x_(k))","quad k >= 0:}\begin{equation*} x_{k+1}=G\left(x_{k}\right)+\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), \quad k \geq 0 \tag{4} \end{equation*}(4)xk+1=G(xk)+(I+⋯+G′(xk)ik)G′(xk)(G(xk)−xk),k≥0
with i k i k i_(k)i_{k}ik given by (3), we must assume that this sequence converges to the fixed point x ∗ x ∗ x^(**)x^{*}x∗. But is this assumption reasonable? The purpose of this note is to show that under certain natural conditions the sequence converges to x ∗ x ∗ x^(**)x^{*}x∗, so the answer is positive.

2 Main result

First of all, we remark that the fixed point problem is equivalent to solving
F ( x ) = 0 , with F ( x ) = x − G ( x ) , F ( x ) = 0 ,  with  F ( x ) = x − G ( x ) , F(x)=0," with "F(x)=x-G(x),F(x)=0, \text { with } F(x)=x-G(x),F(x)=0, with F(x)=x−G(x),
for which the Newton method generates the iterates
(5) s k N = − F ′ ( x k ) − 1 F ( x k ) x k + 1 = x k + s k N , k = 0 , 1 , … (5) s k N = − F ′ x k − 1 F x k x k + 1 = x k + s k N , k = 0 , 1 , … {:[(5)s_(k)^(N)=-F^(')(x_(k))^(-1)F(x_(k))],[x_(k+1)=x_(k)+s_(k)^(N)","quad k=0","1","dots]:}\begin{align*} s_{k}^{N} & =-F^{\prime}\left(x_{k}\right)^{-1} F\left(x_{k}\right) \tag{5}\\ x_{k+1} & =x_{k}+s_{k}^{N}, \quad k=0,1, \ldots \end{align*}(5)skN=−F′(xk)−1F(xk)xk+1=xk+skN,k=0,1,…
In this setting, iterations (4) may be rewritten as
(6) x k + 1 = x k + ( I + G ′ ( x k ) + … + G ′ ( x k ) i k + 1 ) ( G ( x k ) − x k ) := x k + s k , k = 0 , 1 , … with i k s.t. q i k + 2 1 − q ≤ K ‖ F ( x k ) ‖ (6) x k + 1 = x k + I + G ′ x k + … + G ′ x k i k + 1 G x k − x k := x k + s k , k = 0 , 1 , …  with  i k  s.t.  q i k + 2 1 − q ≤ K F x k {:[(6)x_(k+1)=x_(k)+(I+G^(')(x_(k))+dots+G^(')(x_(k))^(i_(k)+1))(G(x_(k))-x_(k))],[:=x_(k)+s_(k)","quad k=0","1","dots],[" with "i_(k)" s.t. "(q^(i_(k)+2))/(1-q) <= K||F(x_(k))||]:}\begin{align*} x_{k+1} & =x_{k}+\left(I+G^{\prime}\left(x_{k}\right)+\ldots+G^{\prime}\left(x_{k}\right)^{i_{k}+1}\right)\left(G\left(x_{k}\right)-x_{k}\right) \tag{6}\\ & :=x_{k}+s_{k}, \quad k=0,1, \ldots \\ & \text { with } i_{k} \text { s.t. } \frac{q^{i_{k}+2}}{1-q} \leq K\left\|F\left(x_{k}\right)\right\| \end{align*}(6)xk+1=xk+(I+G′(xk)+…+G′(xk)ik+1)(G(xk)−xk):=xk+sk,k=0,1,… with ik s.t. qik+21−q≤K‖F(xk)‖
i.e., as quasi-Newton iterations (see, e.g., [11], [8], [7]).
We obtain the following sufficient Kantorovich-type conditions for the convergence to x ∗ x ∗ x^(**)x^{*}x∗ of these iterates.
Theorem 2.1 Assume that G G GGG is differentiable on the domain Ω Ω Omega\OmegaΩ, with G ′ G ′ G^(')G^{\prime}G′ bounded on Ω Ω Omega\OmegaΩ by
(7) ‖ G ′ ( x ) ‖ ≤ q < 1 , ∀ x ∈ Ω (7) G ′ ( x ) ≤ q < 1 , ∀ x ∈ Ω {:(7)||G^(')(x)|| <= q < 1","quad AA x in Omega:}\begin{equation*} \left\|G^{\prime}(x)\right\| \leq q<1, \quad \forall x \in \Omega \tag{7} \end{equation*}(7)‖G′(x)‖≤q<1,∀x∈Ω
and Lipschitz continuous:
‖ G ′ ( x ) − G ′ ( y ) ‖ ≤ L ‖ x − y ‖ , ∀ x , y ∈ Ω G ′ ( x ) − G ′ ( y ) ≤ L ‖ x − y ‖ , ∀ x , y ∈ Ω ||G^(')(x)-G^(')(y)|| <= L||x-y||,quad AA x,y in Omega\left\|G^{\prime}(x)-G^{\prime}(y)\right\| \leq L\|x-y\|, \quad \forall x, y \in \Omega‖G′(x)−G′(y)‖≤L‖x−y‖,∀x,y∈Ω
Let x 0 ∈ Ω x 0 ∈ Ω x_(0)in Omegax_{0} \in \Omegax0∈Ω and K > 0 K > 0 K > 0K>0K>0 be chosen such that
(8) ν = ( L 2 ( 1 − q ) 2 + K ( 1 + q ) ) ‖ F ( x 0 ) ‖ < 1 , (8) ν = L 2 ( 1 − q ) 2 + K ( 1 + q ) F x 0 < 1 , {:(8)nu=((L)/(2(1-q)^(2))+K(1+q))||F(x_(0))|| < 1",":}\begin{equation*} \nu=\left(\frac{L}{2(1-q)^{2}}+K(1+q)\right)\left\|F\left(x_{0}\right)\right\|<1, \tag{8} \end{equation*}(8)ν=(L2(1−q)2+K(1+q))‖F(x0)‖<1,
and suppose that B ¯ r ( x 0 ) = { x ∈ X : ‖ x − x 0 ‖ ≤ r } ⊆ Ω B ¯ r x 0 = x ∈ X : x − x 0 ≤ r ⊆ Ω bar(B)_(r)(x_(0))={x in X:||x-x_(0)|| <= r}sube Omega\bar{B}_{r}\left(x_{0}\right)=\left\{x \in X:\left\|x-x_{0}\right\| \leq r\right\} \subseteq \OmegaB¯r(x0)={x∈X:‖x−x0‖≤r}⊆Ω for
r = 1 ( 1 − ν ) ( 1 − q ) ‖ F ( x 0 ) ‖ r = 1 ( 1 − ν ) ( 1 − q ) F x 0 r=(1)/((1-nu)(1-q))||F(x_(0))||r=\frac{1}{(1-\nu)(1-q)}\left\|F\left(x_{0}\right)\right\|r=1(1−ν)(1−q)‖F(x0)‖
Then the elements of the sequence defined by (6) remain in the ball B ¯ r ( x 0 ) B ¯ r x 0 bar(B)_(r)(x_(0))\bar{B}_{r}\left(x_{0}\right)B¯r(x0) and converge to a fixed point x ∗ x ∗ x^(**)x^{*}x∗ of G G GGG, which is unique in this ball. According to Theorem 1.2, the convergence is quadratic.
Proof. Recall first [11, 3.2.12] that the Lipschitz hypothesis on G ′ G ′ G^(')G^{\prime}G′ implies that
‖ G ( y ) − G ( x ) − G ′ ( x ) ( y − x ) ‖ ≤ L 2 ‖ y − x ‖ 2 , ∀ x , y ∈ Ω G ( y ) − G ( x ) − G ′ ( x ) ( y − x ) ≤ L 2 ‖ y − x ‖ 2 , ∀ x , y ∈ Ω ||G(y)-G(x)-G^(')(x)(y-x)|| <= (L)/(2)||y-x||^(2),quad AA x,y in Omega\left\|G(y)-G(x)-G^{\prime}(x)(y-x)\right\| \leq \frac{L}{2}\|y-x\|^{2}, \quad \forall x, y \in \Omega‖G(y)−G(x)−G′(x)(y−x)‖≤L2‖y−x‖2,∀x,y∈Ω
while (7) attracts the existence of ( I − G ′ ( x ) ) − 1 = I + G ′ ( x ) + … + G ′ ( x ) k + … I − G ′ ( x ) − 1 = I + G ′ ( x ) + … + G ′ ( x ) k + … (I-G^(')(x))^(-1)=I+G^(')(x)+dots+G^(')(x)^(k)+dots\left(I-G^{\prime}(x)\right)^{-1}=I+G^{\prime}(x)+\ldots+G^{\prime}(x)^{k}+\ldots(I−G′(x))−1=I+G′(x)+…+G′(x)k+… and the bound
‖ ( I − G ′ ( x ) ) − 1 ‖ ≤ 1 1 − q , ∀ x ∈ Ω I − G ′ ( x ) − 1 ≤ 1 1 − q , ∀ x ∈ Ω ||(I-G^(')(x))^(-1)|| <= (1)/(1-q),quad AA x in Omega\left\|\left(I-G^{\prime}(x)\right)^{-1}\right\| \leq \frac{1}{1-q}, \quad \forall x \in \Omega‖(I−G′(x))−1‖≤11−q,∀x∈Ω
Our hypotheses imply the following inequalities:
‖ s 0 ‖ ≤ 1 1 − q ‖ F ( x 0 ) ‖ s 0 ≤ 1 1 − q F x 0 ||s_(0)|| <= (1)/(1-q)||F(x_(0))||\left\|s_{0}\right\| \leq \frac{1}{1-q}\left\|F\left(x_{0}\right)\right\|‖s0‖≤11−q‖F(x0)‖
i.e., x 1 ∈ B ¯ r ( x 0 ) x 1 ∈ B ¯ r x 0 x_(1)in bar(B)_(r)(x_(0))x_{1} \in \bar{B}_{r}\left(x_{0}\right)x1∈B¯r(x0) and also
‖ F ( x 1 ) ‖ = ‖ F ( x 1 ) − F ( x 0 ) − F ′ ( x 0 ) s 0 N ‖ ( by ( 5 ) ) ≤ ‖ F ( x 1 ) − F ( x 0 ) − F ′ ( x 0 ) s 0 ‖ + ‖ F ′ ( x 0 ) ( s 0 N − s 0 ) ‖ ≤ ‖ G ( x 1 ) − G ( x 0 ) − G ′ ( x 0 ) s 0 ‖ + ( 1 + q ) ‖ s 0 N − s 0 ‖ ≤ L 2 ‖ s 0 ‖ 2 + ( 1 + q ) ‖ G ′ ( x 0 ) i 0 + 2 ( I + G ′ ( x 0 ) + … ) F ( x 0 ) ‖ ≤ L 2 ( 1 + q + … + q i 0 + 1 ) 2 ‖ F ( x 0 ) ‖ 2 + q i 0 + 2 1 − q ( 1 + q ) ‖ F ( x 0 ) ‖ ≤ L ( 1 − q i 0 + 2 ) 2 2 ( 1 − q ) 2 ‖ F ( x 0 ) ‖ 2 + K ( 1 + q ) ‖ F ( x 0 ) ‖ 2 ≤ ν ‖ F ( x 0 ) ‖ F x 1 = F x 1 − F x 0 − F ′ x 0 s 0 N (  by  ( 5 ) ) ≤ F x 1 − F x 0 − F ′ x 0 s 0 + F ′ x 0 s 0 N − s 0 ≤ G x 1 − G x 0 − G ′ x 0 s 0 + ( 1 + q ) s 0 N − s 0 ≤ L 2 s 0 2 + ( 1 + q ) G ′ x 0 i 0 + 2 I + G ′ x 0 + … F x 0 ≤ L 2 1 + q + … + q i 0 + 1 2 F x 0 2 + q i 0 + 2 1 − q ( 1 + q ) F x 0 ≤ L 1 − q i 0 + 2 2 2 ( 1 − q ) 2 F x 0 2 + K ( 1 + q ) F x 0 2 ≤ ν F x 0 {:[||F(x_(1))||=||F(x_(1))-F(x_(0))-F^(')(x_(0))s_(0)^(N)||quad(" by "(5))],[ <= ||F(x_(1))-F(x_(0))-F^(')(x_(0))s_(0)||+||F^(')(x_(0))(s_(0)^(N)-s_(0))||],[ <= ||G(x_(1))-G(x_(0))-G^(')(x_(0))s_(0)||+(1+q)||s_(0)^(N)-s_(0)||],[ <= (L)/(2)||s_(0)||^(2)+(1+q)||G^(')(x_(0))^(i_(0)+2)(I+G^(')(x_(0))+dots)F(x_(0))||],[ <= (L)/(2)(1+q+dots+q^(i_(0)+1))^(2)||F(x_(0))||^(2)+(q^(i_(0)+2))/(1-q)(1+q)||F(x_(0))||],[ <= (L(1-q^(i_(0)+2))^(2))/(2(1-q)^(2))||F(x_(0))||^(2)+K(1+q)||F(x_(0))||^(2)],[ <= nu||F(x_(0))||]:}\begin{aligned} \left\|F\left(x_{1}\right)\right\| & =\left\|F\left(x_{1}\right)-F\left(x_{0}\right)-F^{\prime}\left(x_{0}\right) s_{0}^{N}\right\| \quad(\text { by }(5)) \\ & \leq\left\|F\left(x_{1}\right)-F\left(x_{0}\right)-F^{\prime}\left(x_{0}\right) s_{0}\right\|+\left\|F^{\prime}\left(x_{0}\right)\left(s_{0}^{N}-s_{0}\right)\right\| \\ & \leq\left\|G\left(x_{1}\right)-G\left(x_{0}\right)-G^{\prime}\left(x_{0}\right) s_{0}\right\|+(1+q)\left\|s_{0}^{N}-s_{0}\right\| \\ & \leq \frac{L}{2}\left\|s_{0}\right\|^{2}+(1+q)\left\|G^{\prime}\left(x_{0}\right)^{i_{0}+2}\left(I+G^{\prime}\left(x_{0}\right)+\ldots\right) F\left(x_{0}\right)\right\| \\ & \leq \frac{L}{2}\left(1+q+\ldots+q^{i_{0}+1}\right)^{2}\left\|F\left(x_{0}\right)\right\|^{2}+\frac{q^{i_{0}+2}}{1-q}(1+q)\left\|F\left(x_{0}\right)\right\| \\ & \leq \frac{L\left(1-q^{i_{0}+2}\right)^{2}}{2(1-q)^{2}}\left\|F\left(x_{0}\right)\right\|^{2}+K(1+q)\left\|F\left(x_{0}\right)\right\|^{2} \\ & \leq \nu\left\|F\left(x_{0}\right)\right\| \end{aligned}‖F(x1)‖=‖F(x1)−F(x0)−F′(x0)s0N‖( by (5))≤‖F(x1)−F(x0)−F′(x0)s0‖+‖F′(x0)(s0N−s0)‖≤‖G(x1)−G(x0)−G′(x0)s0‖+(1+q)‖s0N−s0‖≤L2‖s0‖2+(1+q)‖G′(x0)i0+2(I+G′(x0)+…)F(x0)‖≤L2(1+q+…+qi0+1)2‖F(x0)‖2+qi0+21−q(1+q)‖F(x0)‖≤L(1−qi0+2)22(1−q)2‖F(x0)‖2+K(1+q)‖F(x0)‖2≤ν‖F(x0)‖
In an analogous fashion, we obtain by induction that for all k ≥ 2 k ≥ 2 k >= 2k \geq 2k≥2
‖ F ( x k ) ‖ ≤ ( L 2 ( 1 − q ) 2 + K ( 1 + q ) ) ‖ F ( x k − 1 ) ‖ 2 ≤ ν ‖ F ( x k − 1 ) ‖ ⋮ ≤ ν k ‖ F ( x 0 ) ‖ F x k ≤ L 2 ( 1 − q ) 2 + K ( 1 + q ) F x k − 1 2 ≤ ν F x k − 1 ⋮ ≤ ν k F x 0 {:[||F(x_(k))|| <= ((L)/(2(1-q)^(2))+K(1+q))||F(x_(k-1))||^(2)],[ <= nu||F(x_(k-1))||],[vdots],[ <= nu^(k)||F(x_(0))||]:}\begin{aligned} \left\|F\left(x_{k}\right)\right\| & \leq\left(\frac{L}{2(1-q)^{2}}+K(1+q)\right)\left\|F\left(x_{k-1}\right)\right\|^{2} \\ & \leq \nu\left\|F\left(x_{k-1}\right)\right\| \\ & \vdots \\ & \leq \nu^{k}\left\|F\left(x_{0}\right)\right\| \end{aligned}‖F(xk)‖≤(L2(1−q)2+K(1+q))‖F(xk−1)‖2≤ν‖F(xk−1)‖⋮≤νk‖F(x0)‖
‖ x k − x k − 1 ‖ = ‖ s k − 1 ‖ ≤ 1 1 − q ‖ F ( x k − 1 ) ‖ ≤ ν k − 1 1 − q ‖ F ( x 0 ) ‖ ‖ x k − x 0 ‖ ≤ ‖ x k − x k − 1 ‖ + … + ‖ x 1 − x 0 ‖ ≤ 1 ( 1 − ν ) ( 1 − q ) ‖ F ( x 0 ) ‖ = r x k − x k − 1 = s k − 1 ≤ 1 1 − q F x k − 1 ≤ ν k − 1 1 − q F x 0 x k − x 0 ≤ x k − x k − 1 + … + x 1 − x 0 ≤ 1 ( 1 − ν ) ( 1 − q ) F x 0 = r {:[||x_(k)-x_(k-1)||=||s_(k-1)|| <= (1)/(1-q)||F(x_(k-1))|| <= (nu^(k-1))/(1-q)||F(x_(0))||],[||x_(k)-x_(0)|| <= ||x_(k)-x_(k-1)||+dots+||x_(1)-x_(0)|| <= (1)/((1-nu)(1-q))||F(x_(0))||=r]:}\begin{aligned} \left\|x_{k}-x_{k-1}\right\| & =\left\|s_{k-1}\right\| \leq \frac{1}{1-q}\left\|F\left(x_{k-1}\right)\right\| \leq \frac{\nu^{k-1}}{1-q}\left\|F\left(x_{0}\right)\right\| \\ \left\|x_{k}-x_{0}\right\| & \leq\left\|x_{k}-x_{k-1}\right\|+\ldots+\left\|x_{1}-x_{0}\right\| \leq \frac{1}{(1-\nu)(1-q)}\left\|F\left(x_{0}\right)\right\|=r \end{aligned}‖xk−xk−1‖=‖sk−1‖≤11−q‖F(xk−1)‖≤νk−11−q‖F(x0)‖‖xk−x0‖≤‖xk−xk−1‖+…+‖x1−x0‖≤1(1−ν)(1−q)‖F(x0)‖=r
It follows that
‖ x k + m − x k ‖ ≤ ‖ x k + m − x k + m − 1 ‖ + … + ‖ x k + 1 − x k ‖ ≤ ν k + m − 1 + … + ν k ( 1 − q ) ‖ F ( x 0 ) ‖ ≤ ν k ( 1 − ν ) ( 1 − q ) ‖ F ( x 0 ) ‖ x k + m − x k ≤ x k + m − x k + m − 1 + … + x k + 1 − x k ≤ ν k + m − 1 + … + ν k ( 1 − q ) F x 0 ≤ ν k ( 1 − ν ) ( 1 − q ) F x 0 {:[||x_(k+m)-x_(k)|| <= ||x_(k+m)-x_(k+m-1)||+dots+||x_(k+1)-x_(k)||],[ <= (nu^(k+m-1)+dots+nu^(k))/((1-q))||F(x_(0))||],[ <= (nu^(k))/((1-nu)(1-q))||F(x_(0))||]:}\begin{aligned} \left\|x_{k+m}-x_{k}\right\| & \leq\left\|x_{k+m}-x_{k+m-1}\right\|+\ldots+\left\|x_{k+1}-x_{k}\right\| \\ & \leq \frac{\nu^{k+m-1}+\ldots+\nu^{k}}{(1-q)}\left\|F\left(x_{0}\right)\right\| \\ & \leq \frac{\nu^{k}}{(1-\nu)(1-q)}\left\|F\left(x_{0}\right)\right\| \end{aligned}‖xk+m−xk‖≤‖xk+m−xk+m−1‖+…+‖xk+1−xk‖≤νk+m−1+…+νk(1−q)‖F(x0)‖≤νk(1−ν)(1−q)‖F(x0)‖
which shows that ( x k ) k ≥ 0 x k k ≥ 0 (x_(k))_(k >= 0)\left(x_{k}\right)_{k \geq 0}(xk)k≥0 is a Cauchy sequence, and therefore converges to a certain x ∗ ∈ B ¯ r ( x 0 ) x ∗ ∈ B ¯ r x 0 x^(**)in bar(B)_(r)(x_(0))x^{*} \in \bar{B}_{r}\left(x_{0}\right)x∗∈B¯r(x0). By the definition and continuity of F , x ∗ F , x ∗ F,x^(**)F, x^{*}F,x∗ is a fixed point of G G GGG, which is unique in B ¯ r ( x 0 ) B ¯ r x 0 bar(B)_(r)(x_(0))\bar{B}_{r}\left(x_{0}\right)B¯r(x0) (and also in Ω Ω Omega\OmegaΩ ) since G G GGG is a contraction.
We note that condition (8) contains certain natural demands: ‖ F ( x 0 ) ‖ F x 0 ||F(x_(0))||\left\|F\left(x_{0}\right)\right\|‖F(x0)‖ is sufficiently small (which holds, e.g., when x 0 x 0 x_(0)x_{0}x0 is sufficiently close to x ∗ x ∗ x^(**)x^{*}x∗ ), q q qqq is sufficiently small (in accordance with the results in [6]), the Lipschitz constant L L LLL is sufficiently small (the graph of G G GGG is close to a constant in case X = R X = R X=RX=RX=R ) and K K KKK is sufficiently small (the linear systems are solved with increasingly precision, the iterates approaching to those given by the Newton method - see the classical results of Dennis and Moré [8]).
Acknowledgement: The author would like to thank Professor Detlef Mache for his kind support regarding the participation to the IBoMat04 Conference.

References

[1] I. Argyros, On the convergence of the modified contractions, J. Comp. Appl. Math., 55 (1994), 183-189.
[2] C. Brezinski, Dynamical systems and sequence transformations, J. Phys. A, 34 (2001), pp. 10659-10669.
[3] C. Brezinski and J.-P. Chehab, Nonlinear hybrid procedures and fixed point iterations, Numer. Funct. Anal. Optimiz., 19 (1998), pp. 465-487.
[4] E. Cătinaş, Inexact perturbed Newton methods and applications to a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001), 543-570.
[5] 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.
[6] E. Cătinas, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl., 113 (2002) no. 3, pp. 473-485
[7] E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comp., (www.ams.org/mcom) to appear.
[8] J. E. Dennis, Jr., and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28 (1974), 549560.
[9] Şt. Măruşter, Quasi-nonexpansivity and two classical methods for solving nonlinear equations, Proc. AMS, 62 (1977), 119-123.
[10] I. Moret, On the behaviour of approximate Newton methods, Computing, 37 (1986), pp. 185-193.
[11] J. M. Ortega, and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970.
[12] F. A. Potra, On Q Q QQQ-order and R R RRR-order of convergence, J. Optim. Theory Appl., 63 (1989), 415-431.
[13] W. C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, SIAM, Philadelphia, 1998.
[14] D. A. Smith, W. F. Ford and A. Sidi, Extrapolation methods for vector sequences, SIAM Rev., 29 (1987), pp. 199-233.
"T. Popoviciu" Institute of Numerical Analysis (Romanian Academy)
P.O. Box 68-1
3400 Cluj-Napoca, Romania
Email address: ecatinas@ictp.acad.ro, ecatinas@cs.ubbcluj.ro
  1. 1 1 ^(1){ }^{1}1 In this case, the successive approximations cannot converge faster than q q qqq-linearly [6].
2005

Related Posts