On the convergence of some quasi-Newton iterates studied by I. Păvăloiu

Emil Cătinaş
(original), Fixed point theory, local convergence, Newton method, nonlinear equations in Banach spaces, nonlinear systems in Rn, Numerical Analysis, paper, solving F(x)=0 iteratively, successive approximations

Abstract

In 1986, I. Păvăloiu [6] has considered a Banach space and the fixed point problem \[x=\lambda D\left( x\right) +y, \qquad D:X\rightarrow X \ \textrm{nonlinear},\ \lambda\in {\mathbb R},\ y\in X \ \textrm{given}\]written in the equivalent form \(F(x):=x -\lambda D\left( x\right) -y=0\) and solved by the general quasi-Newton method\[x_{n+1}=x_n-A(x_n) \left[ x_n-\lambda D(x_n) -y\right] ,\qquad n=0,1,\ldots\]Semilocal convergence results were obtained, ensuring linear convergence of these iterates. Further results were obtained for the iterates \[x_{n+1}=x_n-[I+\lambda D^\prime(x_n)] \left[x_n+\lambda D(x_n) -y\right] ,\qquad n=0,1,\ldots\] In this note, we analyze the local convergence of these iterates, and, using the Ostrowski local attraction theorem, we give some sufficient conditions such that the iterates converge locally either linearly or with higher convergence orders. The local convergence results require fewer differentiability assumptions for \(D\).

Authors

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

Keywords

nonlinear equations in Banach spaces; inexact Newton method; quasi-Newton method; Ostrowski local attraction theorem; local convergence; convergence order.

References

PDF

https://ictp.acad.ro/jnaat/journal/article/view/2015-vol44-no1-art3/pdf

About this paper

Cite this paper as:

E. Cătinaş, On the convergence of some quasi-Newton iterates studied by I. Păvăloiu, J. Numer. Anal. Approx. Theory, 44 (2015) no. 1, pp. 38-41.

Journal

Journal of Numerical Analysis and Approximation Theory

Publisher Name

Editura Academiei Române

Paper on the journal website

https://ictp.acad.ro/jnaat/journal/article/view/2015-vol44-no1-art3

Print ISSN

2457-6794

Online ISSN

2501-059X

Google Scholar Profile

[1]   E. Catinas, On  the  superlinear  convergence  of  the  successive  approximations  method, J. Optim. Theory Appl., 113 (2002) no. 3, pp. 473-485. http://dx.doi.org/10.1023/A:1015304720071

[2]   E. Catinas, The  inexact,  inexact  perturbed  and  quasi-Newton  methods  are  equivalent models, Math. Comp., 74 (2005) no. 249, pp. 291-301, http://dx.doi.org/10.1090/S0025-5718-04-01646-1

[3]  E. Catinas, On the convergence orders , manuscript.

[4]   Diaconu, A., Pavaloiu, I., Sur quelque methodes iteratives pour la resolution des  equations operationnel les, Rev. Anal. Numer. Theor. Approx., vol. 1, 45-61 (1972),

https://ictp.acad.ro/jnaat/journal/article/view/1972-vol1-art3

[5]  J.M. Ortega,  W.C. Rheinboldt, Iterative  solution  of  nonlinear  equations  in  several Variables , Academic Press, New York, 1970.

[6]  I. Pavaloiu, La convergence de certaines methodes iteratives pour resoudre certaines equations  operationnelles, Seminar on functional analysis and numerical methods, Preprint(1986), pp. 127-132 (in French).

[7] I. Pavaloiu, A unified treatment of the modified Newton and chord methods, Carpathian J. Math. 25 (2009) no. 2, pp. 192-196.

.

Paper (preprint) in HTML form

jnaat,+Journal+manager,+2015-1-Catinas-16-01-08

ON THE CONVERGENCE OF SOME QUASI-NEWTON ITERATES STUDIED BY I. PĂVĂLOIU

EMIL CĂTINAŞ*Dedicated to prof. I. Păvăloiu on the occasion of his 75th anniversary

Abstract

I. Păvăloiu has considered a Banach space X X XXX and the problem x = λ D ( x ) + y ( D : X → X , λ ∈ R , y ∈ X given ) x = λ D ( x ) + y ( D : X → X , λ ∈ R , y ∈ X  given  ) x=lambda D(x)+y quad(D:X rarr X,lambda inR,y in X" given ")x=\lambda D(x)+y \quad(D: X \rightarrow X, \lambda \in \mathbb{R}, y \in X \text { given })x=λD(x)+y(D:X→X,λ∈R,y∈X given ) written in the equivalent form F ( x ) := x − λ D ( x ) − y = 0 F ( x ) := x − λ D ( x ) − y = 0 F(x):=x-lambda D(x)-y=0F(x):=x-\lambda D(x)-y=0F(x):=x−λD(x)−y=0 and solved by the general quasi-Newton method x k + 1 = x k − A ( x k ) [ x k − λ D ( x k ) − y ] , k = 0 , 1 , … x k + 1 = x k − A x k x k − λ D x k − y , k = 0 , 1 , … x_(k+1)=x_(k)-A(x_(k))[x_(k)-lambda D(x_(k))-y],quad k=0,1,dotsx_{k+1}=x_{k}-A\left(x_{k}\right)\left[x_{k}-\lambda D\left(x_{k}\right)-y\right], \quad k=0,1, \ldotsxk+1=xk−A(xk)[xk−λD(xk)−y],k=0,1,…

Semilocal convergence results were obtained, ensuring linear convergence of this method. Further results were obtained for the iterates: x k + 1 = x k − [ I + λ D ′ ( x k ) ] [ x k − λ D ( x k ) − y ] , k = 0 , 1 , … x k + 1 = x k − I + λ D ′ x k x k − λ D x k − y , k = 0 , 1 , … x_(k+1)=x_(k)-[I+lambdaD^(')(x_(k))][x_(k)-lambda D(x_(k))-y],quad k=0,1,dotsx_{k+1}=x_{k}-\left[I+\lambda D^{\prime}\left(x_{k}\right)\right]\left[x_{k}-\lambda D\left(x_{k}\right)-y\right], \quad k=0,1, \ldotsxk+1=xk−[I+λD′(xk)][xk−λD(xk)−y],k=0,1,…

In this note, we analyze the local convergence of these iterates, and, using the Ostrowski local attraction theorem, we give some sufficient conditions such that the iterates converge locally either linearly or with higher convergence orders. The local convergence results require fewer differentiability assumptions for D D DDD.

MSC 2010. 65H10.
Keywords. quasi-Newton methods, Ostrowski local attraction theorem, local convergence.

1. INTRODUCTION

In [6], Păvăloiu has considered a Banach space ( X , ‖ ⋅ ‖ X , ‖ ⋅ ‖ X,||*||X,\|\cdot\|X,‖⋅‖ ), a nonlinear mapping D : X → X D : X → X D:X rarr XD: X \rightarrow XD:X→X, a parameter λ ∈ R λ ∈ R lambda inR\lambda \in \mathbb{R}λ∈R, an element y ∈ X y ∈ X y in Xy \in Xy∈X and the equation (arising from certain integral equations)
(1) x = λ D ( x ) + y (1) x = λ D ( x ) + y {:(1)x=lambda D(x)+y:}\begin{equation*} x=\lambda D(x)+y \tag{1} \end{equation*}(1)x=λD(x)+y
solved by the following iterations:
(2) x k + 1 = x k − A ( x k ) [ x k − λ D ( x k ) − y ] , k = 0 , 1 , … , x 0 ∈ E ⊆ X , (2) x k + 1 = x k − A x k x k − λ D x k − y , k = 0 , 1 , … , x 0 ∈ E ⊆ X , {:(2)x_(k+1)=x_(k)-A(x_(k))[x_(k)-lambda D(x_(k))-y]","quad k=0","1","dots","x_(0)in E sube X",":}\begin{equation*} x_{k+1}=x_{k}-A\left(x_{k}\right)\left[x_{k}-\lambda D\left(x_{k}\right)-y\right], \quad k=0,1, \ldots, x_{0} \in E \subseteq X, \tag{2} \end{equation*}(2)xk+1=xk−A(xk)[xk−λD(xk)−y],k=0,1,…,x0∈E⊆X,
where A ( x ) : E → E A ( x ) : E → E A(x):E rarr EA(x): E \rightarrow EA(x):E→E is a linear continuous mapping (i.e., A ( x ) ∈ L ( X ) A ( x ) ∈ L ( X ) A(x)inL(X)A(x) \in \mathcal{L}(X)A(x)∈L(X) ), for each x ∈ E x ∈ E x in Ex \in Ex∈E.
Denoting
(3) F ( x ) = x − λ D ( x ) − y (3) F ( x ) = x − λ D ( x ) − y {:(3)F(x)=x-lambda D(x)-y:}\begin{equation*} F(x)=x-\lambda D(x)-y \tag{3} \end{equation*}(3)F(x)=x−λD(x)−y
the above iterations can be written as
x k + 1 = x k − A ( x k ) F ( x k ) , k = 0 , 1 , … ; x k + 1 = x k − A x k F x k , k = 0 , 1 , … ; x_(k+1)=x_(k)-A(x_(k))F(x_(k)),quad k=0,1,dots;x_{k+1}=x_{k}-A\left(x_{k}\right) F\left(x_{k}\right), \quad k=0,1, \ldots ;xk+1=xk−A(xk)F(xk),k=0,1,…;
in a subsequent paper, Părăloiu [7] has analyzed the above iterations for general mappings F F FFF, not necessarily given by (3).
The following semilocal convergence results were obtained.
Theorem 1. [6] If the mappings D D DDD and A ( x ) A ( x ) A(x)A(x)A(x), the initial approximation x 0 x 0 x_(0)x_{0}x0 and the real number r > 0 r > 0 r > 0r>0r>0 satisfy the following conditions:
i. the mapping D D DDD admits Fréchet derivatives of order one and two on the ball S = S ( x 0 , r ) S = S x 0 , r S=S(x_(0),r)S=S\left(x_{0}, r\right)S=S(x0,r);
ii. ‖ A ( x ) ‖ ≤ β ‖ A ( x ) ‖ ≤ β ||A(x)|| <= beta\|A(x)\| \leq \beta‖A(x)‖≤β, for each x ∈ S x ∈ S x in Sx \in Sx∈S, and some β > 0 β > 0 beta > 0\beta>0β>0;
iii. ‖ I − F ′ ( x ) A ( x ) ‖ ≤ α I − F ′ ( x ) A ( x ) ≤ α ||I-F^(')(x)A(x)|| <= alpha\left\|I-F^{\prime}(x) A(x)\right\| \leq \alpha‖I−F′(x)A(x)‖≤α, for each x ∈ S x ∈ S x in Sx \in Sx∈S, and some α > 0 α > 0 alpha > 0\alpha>0α>0;
iv. ‖ D ′ ′ ( x ) ‖ ≤ M / | λ | D ′ ′ ( x ) ≤ M / | λ | ||D^('')(x)|| <= M//|lambda|\left\|D^{\prime \prime}(x)\right\| \leq M /|\lambda|‖D′′(x)‖≤M/|λ|, for each x ∈ S x ∈ S x in Sx \in Sx∈S, and some M > 0 M > 0 M > 0M>0M>0;
v. β ρ 0 1 − d 0 ≤ r β ρ 0 1 − d 0 ≤ r (betarho_(0))/(1-d_(0)) <= r\frac{\beta \rho_{0}}{1-d_{0}} \leq rβρ01−d0≤r, where ρ 0 = ‖ F ( x 0 ) ‖ , d 0 = M β 2 ρ 0 2 + α ρ 0 = F x 0 , d 0 = M β 2 ρ 0 2 + α rho_(0)=||F(x_(0))||,d_(0)=(Mbeta^(2)rho_(0))/(2)+alpha\rho_{0}=\left\|F\left(x_{0}\right)\right\|, d_{0}=\frac{M \beta^{2} \rho_{0}}{2}+\alphaρ0=‖F(x0)‖,d0=Mβ2ρ02+α;
vi. d 0 < 1 d 0 < 1 d_(0) < 1d_{0}<1d0<1,
then 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 (2) converges: x ∗ = lim k → ∞ x k x ∗ = lim k → ∞   x k x^(**)=lim_(k rarr oo)x_(k)x^{*}=\lim _{k \rightarrow \infty} x_{k}x∗=limk→∞xk, with F ( x ∗ ) = 0 F x ∗ = 0 F(x^(**))=0F\left(x^{*}\right)=0F(x∗)=0. The following estimations hold:
‖ x ∗ − x k ‖ ≤ β d 0 k ρ 0 1 − d 0 , k = 0 , 1 , … x ∗ − x k ≤ β d 0 k ρ 0 1 − d 0 , k = 0 , 1 , … ||x^(**)-x_(k)|| <= (betad_(0)^(k)rho_(0))/(1-d_(0)),quad k=0,1,dots\left\|x^{*}-x_{k}\right\| \leq \frac{\beta d_{0}^{k} \rho_{0}}{1-d_{0}}, \quad k=0,1, \ldots‖x∗−xk‖≤βd0kρ01−d0,k=0,1,…
When ‖ λ D ′ ( x ) ‖ < 1 λ D ′ ( x ) < 1 ||lambdaD^(')(x)|| < 1\left\|\lambda D^{\prime}(x)\right\|<1‖λD′(x)‖<1, it is known that the operator I − λ D ′ ( x ) I − λ D ′ ( x ) I-lambdaD^(')(x)I-\lambda D^{\prime}(x)I−λD′(x) is invertible, with ( I − λ D ′ ( x ) ) − 1 = I + λ D ′ ( x ) + λ 2 D ′ ( x ) 2 + … I − λ D ′ ( x ) − 1 = I + λ D ′ ( x ) + λ 2 D ′ ( x ) 2 + … (I-lambdaD^(')(x))^(-1)=I+lambdaD^(')(x)+lambda^(2)D^(')(x)^(2)+dots\left(I-\lambda D^{\prime}(x)\right)^{-1}=I+\lambda D^{\prime}(x)+\lambda^{2} D^{\prime}(x)^{2}+\ldots(I−λD′(x))−1=I+λD′(x)+λ2D′(x)2+… Păvăloiu has considered the operator A ( x ) A ( x ) A(x)A(x)A(x) as being given by the first two terms of this expansion, obtaining the following iterates
(4) x k + 1 = x k − ( I + λ D ′ ( x k ) ) [ x k − λ D ( x k ) − y ] , k = 0 , 1 , … , (4) x k + 1 = x k − I + λ D ′ x k x k − λ D x k − y , k = 0 , 1 , … , {:(4)x_(k+1)=x_(k)-(I+lambdaD^(')(x_(k)))[x_(k)-lambda D(x_(k))-y]","quad k=0","1","dots",":}\begin{equation*} x_{k+1}=x_{k}-\left(I+\lambda D^{\prime}\left(x_{k}\right)\right)\left[x_{k}-\lambda D\left(x_{k}\right)-y\right], \quad k=0,1, \ldots, \tag{4} \end{equation*}(4)xk+1=xk−(I+λD′(xk))[xk−λD(xk)−y],k=0,1,…,
and the following result.
Theorem 2. [6 If the mapping D D DDD, the initial approximation x 0 x 0 x_(0)x_{0}x0 and the real number r > 0 r > 0 r > 0r>0r>0 satisfy the following assumptions:
i. the mapping D D DDD admits Fréchet derivatives of order one and two for each x ∈ S = S ( x 0 , r ) x ∈ S = S x 0 , r x in S=S(x_(0),r)x \in S=S\left(x_{0}, r\right)x∈S=S(x0,r);
ii. ‖ D ′ ( x ) ‖ ≤ b D ′ ( x ) ≤ b ||D^(')(x)|| <= b\left\|D^{\prime}(x)\right\| \leq b‖D′(x)‖≤b, for each x ∈ S x ∈ S x in Sx \in Sx∈S;
iii. ‖ D ′ ′ ( x ) ‖ ≤ M / | λ | D ′ ′ ( x ) ≤ M / | λ | ||D^('')(x)|| <= M//|lambda|\left\|D^{\prime \prime}(x)\right\| \leq M /|\lambda|‖D′′(x)‖≤M/|λ|, for each x ∈ S x ∈ S x in Sx \in Sx∈S;
iv. 2 − M ρ 0 > 0 2 − M ρ 0 > 0 2-Mrho_(0) > 02-M \rho_{0}>02−Mρ0>0, where ρ 0 = ‖ x 0 − λ D ( x 0 ) − y ‖ ρ 0 = x 0 − λ D x 0 − y rho_(0)=||x_(0)-lambda D(x_(0))-y||\rho_{0}=\left\|x_{0}-\lambda D\left(x_{0}\right)-y\right\|ρ0=‖x0−λD(x0)−y‖;
v. ρ 0 ( 1 + | λ | b ) 1 − d 0 ≤ r ρ 0 ( 1 + | λ | b ) 1 − d 0 ≤ r (rho_(0)(1+|lambda|b))/(1-d_(0)) <= r\frac{\rho_{0}(1+|\lambda| b)}{1-d_{0}} \leq rρ0(1+|λ|b)1−d0≤r, where d 0 = M ( 1 + | λ | b ) 2 2 ρ 0 + λ 2 b 2 d 0 = M ( 1 + | λ | b ) 2 2 ρ 0 + λ 2 b 2 d_(0)=M((1+|lambda|b)^(2))/(2)rho_(0)+lambda^(2)b^(2)d_{0}=M \frac{(1+|\lambda| b)^{2}}{2} \rho_{0}+\lambda^{2} b^{2}d0=M(1+|λ|b)22ρ0+λ2b2;
vi. | λ | ≤ 2 − M ρ 0 b ( 2 + M ρ 0 ) | λ | ≤ 2 − M ρ 0 b 2 + M ρ 0 |lambda| <= (2-Mrho_(0))/(b(2+Mrho_(0)))|\lambda| \leq \frac{2-M \rho_{0}}{b\left(2+M \rho_{0}\right)}|λ|≤2−Mρ0b(2+Mρ0),
then the sequence given by (4) converges to a solution x ∗ x ∗ x^(**)x^{*}x∗ of equation (1) and the following estimates hold:
‖ x ∗ − x k ‖ ≤ ( 1 + | λ | b ) d 0 k ρ 0 1 − d 0 , k = 0 , 1 , … x ∗ − x k ≤ ( 1 + | λ | b ) d 0 k ρ 0 1 − d 0 , k = 0 , 1 , … ||x^(**)-x_(k)|| <= ((1+|lambda|b)d_(0)^(k)rho_(0))/(1-d_(0)),quad k=0,1,dots\left\|x^{*}-x_{k}\right\| \leq \frac{(1+|\lambda| b) d_{0}^{k} \rho_{0}}{1-d_{0}}, \quad k=0,1, \ldots‖x∗−xk‖≤(1+|λ|b)d0kρ01−d0,k=0,1,…
Remark 3. We note that the assumptions of the above results require the existence of the second derivative of D D DDD, and also that the smaller d 0 d 0 d_(0)d_{0}d0 (i.e., the smaller | λ | , b , M | λ | , b , M |lambda|,b,M|\lambda|, b, M|λ|,b,M and ρ 0 ρ 0 rho_(0)\rho_{0}ρ0 ), the faster is the convergence of sequence (4).

2. LOCAL CONVERGENCE

In order to analyze the local convergence of the considered iterates, we shall use the Ostrowski local attraction theorem, which offers sharp general conditions ensuring the local convergence. We shall consider for simplicity that X = R n X = R n X=R^(n)X=\mathbb{R}^{n}X=Rn, with ‖ ⋅ ‖ ‖ ⋅ ‖ ||*||\|\cdot\|‖⋅‖ an arbitrary given norm, though the results hold in Banach spaces (see, e.g., [5, NR 10.1-3.]).
Theorem 4 (Ostrowski local attraction theorem). [5, Th. 10.1.3] Suppose that G : Ω ⊂ R n → R n G : Ω ⊂ R n → R n G:Omega subR^(n)rarrR^(n)G: \Omega \subset \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}G:Ω⊂Rn→Rn has a fixed point x ∗ ∈ int ( Ω ) x ∗ ∈ int ( Ω ) x^(**)in int(Omega)x^{*} \in \operatorname{int}(\Omega)x∗∈int(Ω) and is differentiable at x ∗ x ∗ x^(**)x^{*}x∗. 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 , rho(G^(')(x^(**)))=sigma < 1,\rho\left(G^{\prime}\left(x^{*}\right)\right)=\sigma<1,ρ(G′(x∗))=σ<1,
then x ∗ x ∗ x^(**)x^{*}x∗ is a point of attraction of the successive approximations x k + 1 = G ( x k ) x k + 1 = G x k x_(k+1)=G(x_(k))x_{k+1}=G\left(x_{k}\right)xk+1=G(xk), k ≥ 0 k ≥ 0 k >= 0k \geq 0k≥0, i.e., there exists an open neighborhood V ⊆ Ω V ⊆ Ω V sube OmegaV \subseteq \OmegaV⊆Ω of x ∗ x ∗ x^(**)x^{*}x∗ such that ∀ x 0 ∈ V ∀ x 0 ∈ V AAx_(0)in V\forall x_{0} \in V∀x0∈V, the successive approximations given above all lie in Ω Ω Omega\OmegaΩ and converge to x ∗ x ∗ x^(**)x^{*}x∗.
Remark 5. The classical book of Ortega and Rheinboldt also contains completions to this result (see [5, Ch. 10]), in the sense that the spectral radius σ σ sigma\sigmaσ yields the "worst" ( r − r − r-r-r− )convergence factor among the sequences converging to the fixed point: when σ ≠ 0 σ ≠ 0 sigma!=0\sigma \neq 0σ≠0, the convergence of the (whole) process is not faster than linear (though, theoretically, there may exist sequences converging at least r r rrr-superlinearly), while when σ = 0 σ = 0 sigma=0\sigma=0σ=0, all the sequences converge at least r r rrr-superlinearly. This result was refined by us in [1], where we have shown that x k → x ∗ q x k → x ∗ q x_(k)rarrx^(**)qx_{k} \rightarrow x^{*} qxk→x∗q-superlinearly iff G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗) has a zero eigenvalue and, starting from a certain step, x ∗ − x k x ∗ − x k x^(**)-x_(k)x^{*}-x_{k}x∗−xk are corresponding eigenvectors. This implies that no q q qqq-superlinear convergence may occur when G ′ ( x ∗ ) G ′ x ∗ G^(')(x^(**))G^{\prime}\left(x^{*}\right)G′(x∗) has no zero eigenvalue.
The above result can be applied to method (2) if we notice that the derivative of x − A ( x ) F ( x ) x − A ( x ) F ( x ) x-A(x)F(x)x-A(x) F(x)x−A(x)F(x) has a simple form at the fixed point x ∗ x ∗ x^(**)x^{*}x∗, the following auxiliary result being similar to (Lemma) 10.2.1 in [5].
Lemma 6. Suppose that F : Ω ⊂ R n → R n F : Ω ⊂ R n → R n F:Omega subR^(n)rarrR^(n)F: \Omega \subset \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}F:Ω⊂Rn→Rn is differentiable at a point x ∗ ∈ int ( Ω ) x ∗ ∈ int ( Ω ) x^(**)in int(Omega)x^{*} \in \operatorname{int}(\Omega)x∗∈int(Ω) for which F ( x ∗ ) = 0 F x ∗ = 0 F(x^(**))=0F\left(x^{*}\right)=0F(x∗)=0. Let A : Ω 0 → L ( R n ) A : Ω 0 → L R n A:Omega_(0)rarrL(R^(n))A: \Omega_{0} \rightarrow \mathcal{L}\left(\mathbb{R}^{n}\right)A:Ω0→L(Rn) be defined on an open neighborhood Ω 0 ⊆ Ω Ω 0 ⊆ Ω Omega_(0)sube Omega\Omega_{0} \subseteq \OmegaΩ0⊆Ω of x ∗ x ∗ x^(**)x^{*}x∗ and continuous at x ∗ x ∗ x^(**)x^{*}x∗. Then the mapping G : S → R n G : S → R n G:S rarrR^(n)G: S \rightarrow \mathbb{R}^{n}G:S→Rn,
G ( x ) = x − A ( x ) F ( x ) G ( x ) = x − A ( x ) F ( x ) G(x)=x-A(x)F(x)G(x)=x-A(x) F(x)G(x)=x−A(x)F(x)
is differentiable at x ∗ x ∗ x^(**)x^{*}x∗ and
G ′ ( x ∗ ) = I − A ( x ∗ ) F ′ ( x ∗ ) . G ′ x ∗ = I − A x ∗ F ′ x ∗ . G^(')(x^(**))=I-A(x^(**))F^(')(x^(**)).G^{\prime}\left(x^{*}\right)=I-A\left(x^{*}\right) F^{\prime}\left(x^{*}\right) .G′(x∗)=I−A(x∗)F′(x∗).
Proof. The proof is elementary:
‖ G ( x ) − G ( x ∗ ) − [ I − A ( x ∗ ) F ′ ( x ∗ ) ] ( x − x ∗ ) ‖ = = ‖ ( A ( x ) − A ( x ∗ ) ) F ( x ) + A ( x ∗ ) [ F ( x ) − F ( x ∗ ) − F ′ ( x ∗ ) ( x − x ∗ ) ] ‖ = o ( ‖ x − x ∗ ‖ ) , as x → x ∗ G ( x ) − G x ∗ − I − A x ∗ F ′ x ∗ x − x ∗ = = A ( x ) − A x ∗ F ( x ) + A x ∗ F ( x ) − F x ∗ − F ′ x ∗ x − x ∗ = o x − x ∗ ,  as  x → x ∗ {:[||G(x)-G(x^(**))-[I-A(x^(**))F^(')(x^(**))](x-x^(**))||=],[=||(A(x)-A(x^(**)))F(x)+A(x^(**))[F(x)-F(x^(**))-F^(')(x^(**))(x-x^(**))]||],[=o(||x-x^(**)||)","quad" as "x rarrx^(**)]:}\begin{aligned} & \left\|G(x)-G\left(x^{*}\right)-\left[I-A\left(x^{*}\right) F^{\prime}\left(x^{*}\right)\right]\left(x-x^{*}\right)\right\|= \\ & =\left\|\left(A(x)-A\left(x^{*}\right)\right) F(x)+A\left(x^{*}\right)\left[F(x)-F\left(x^{*}\right)-F^{\prime}\left(x^{*}\right)\left(x-x^{*}\right)\right]\right\| \\ & =o\left(\left\|x-x^{*}\right\|\right), \quad \text { as } x \rightarrow x^{*} \end{aligned}‖G(x)−G(x∗)−[I−A(x∗)F′(x∗)](x−x∗)‖==‖(A(x)−A(x∗))F(x)+A(x∗)[F(x)−F(x∗)−F′(x∗)(x−x∗)]‖=o(‖x−x∗‖), as x→x∗
Now we can state the main results of this note. First, consider iterations (2).
Theorem 7. Let D : R n → R n , y ∈ R n , λ ∈ R , x ∗ D : R n → R n , y ∈ R n , λ ∈ R , x ∗ D:R^(n)rarrR^(n),y inR^(n),lambda inR,x^(**)D: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}, y \in \mathbb{R}^{n}, \lambda \in \mathbb{R}, x^{*}D:Rn→Rn,y∈Rn,λ∈R,x∗ a solution of F ( x ) := x − λ D ( x ) − y = 0 F ( x ) := x − λ D ( x ) − y = 0 F(x):=x-lambda D(x)-y=0F(x):= x-\lambda D(x)-y=0F(x):=x−λD(x)−y=0, and the mapping A A AAA is defined on an open neighborhood E E EEE of x ∗ , A : E → L ( R n ) x ∗ , A : E → L R n x^(**),A:E rarrL(R^(n))x^{*}, A: E \rightarrow \mathcal{L}\left(\mathbb{R}^{n}\right)x∗,A:E→L(Rn). If D D DDD is differentiable at x ∗ , A x ∗ , A x^(**),Ax^{*}, Ax∗,A is continuous at x ∗ x ∗ x^(**)x^{*}x∗ and
ρ ( I − A ( x ∗ ) ( I − λ D ′ ( x ∗ ) ) < 1 ρ I − A x ∗ I − λ D ′ x ∗ < 1 rho(I-A(x^(**))(I-lambdaD^(')(x^(**))) < 1:}\rho\left(I-A\left(x^{*}\right)\left(I-\lambda D^{\prime}\left(x^{*}\right)\right)<1\right.ρ(I−A(x∗)(I−λD′(x∗))<1
then x ∗ x ∗ x^(**)x^{*}x∗ is a point of attraction for the method (2).
The proof is an immediate application of Lemma 6 and Theorem 4.
The conditions are much simpler for the case of the second method.
Theorem 8. Let D : R n → R n , y ∈ R n , λ ∈ R , x ∗ D : R n → R n , y ∈ R n , λ ∈ R , x ∗ D:R^(n)rarrR^(n),y inR^(n),lambda inR,x^(**)D: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}, y \in \mathbb{R}^{n}, \lambda \in \mathbb{R}, x^{*}D:Rn→Rn,y∈Rn,λ∈R,x∗ a solution of F ( x ) := x − λ D ( x ) − y = 0 F ( x ) := x − λ D ( x ) − y = 0 F(x):=x-lambda D(x)-y=0F(x):= x-\lambda D(x)-y=0F(x):=x−λD(x)−y=0. If the mapping D D DDD is differentiable on an open neighborhood of x ∗ x ∗ x^(**)x^{*}x∗, with D ′ D ′ D^(')D^{\prime}D′ continuous at x ∗ x ∗ x^(**)x^{*}x∗, and
| λ | ρ ( D ′ ( x ∗ ) ) < 1 | λ | ρ D ′ x ∗ < 1 |lambda|rho(D^(')(x^(**))) < 1|\lambda| \rho\left(D^{\prime}\left(x^{*}\right)\right)<1|λ|ρ(D′(x∗))<1
then x ∗ x ∗ x^(**)x^{*}x∗ is a point of attraction for the method (4).
Proof. By Lemma 6 we get
G ′ ( x ∗ ) = I − ( I + λ D ′ ( x ∗ ) ) ( I − λ D ′ ( x ∗ ) ) = λ 2 D ′ ( x ∗ ) 2 , G ′ x ∗ = I − I + λ D ′ x ∗ I − λ D ′ x ∗ = λ 2 D ′ x ∗ 2 , G^(')(x^(**))=I-(I+lambdaD^(')(x^(**)))(I-lambdaD^(')(x^(**)))=lambda^(2)D^(')(x^(**))^(2),G^{\prime}\left(x^{*}\right)=I-\left(I+\lambda D^{\prime}\left(x^{*}\right)\right)\left(I-\lambda D^{\prime}\left(x^{*}\right)\right)=\lambda^{2} D^{\prime}\left(x^{*}\right)^{2},G′(x∗)=I−(I+λD′(x∗))(I−λD′(x∗))=λ2D′(x∗)2,
whence, by Theorem 4, the conclusion follows.
The same observations as in Remark 5 apply.

REFERENCES

[1] E. Cătinaş, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl., 113 (2002) no. 3, pp. 473-485. 뜬
[2] E. Cătinaş, The inexact, inexact perturbed and quasi-Newton methods are equivalent models, Math. Comp., 74 (2005) no. 249, pp. 291-301. ㄸ
[3] E. Cătinaş, On the convergence orders, manuscript.
[4] Diaconu, A., Păvăloiu, I., Sur quelque méthodes itératives pour la resolution des équations opérationnelles, Rev. Anal. Numér. Theor. Approx., vol. 1, 45-61 (1972). ㄸ
[5] J.M. Ortega, W.C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970.
[6] I. Păvăloiu, La convergence de certaines méthodes itératives pour résoudre certaines equations operationnelles, Seminar on functional analysis and numerical methods, Preprint no. 1 (1986), pp. 127-132 (in French).
[7] I. Păvăloiu, A unified treatment of the modified Newton and chord methods, Carpathian J. Math. 25 (2009) no. 2, pp. 192-196.
Received by the editors: October 3, 2015.
  1. *"T. Popoviciu" Institute of Numerical Analysis, P.O. Box 68-1, Cluj-Napoca, Romania, e-mail: ecatinas@ictp.acad.ro.
2015

Related Posts