A note on the quadratic convergence of the inexact Newton methods

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

Abstract

We show that a new sufficient condition for the convergence with q-order two of the inexact Newton iterates may be obtained by considering the normwise backward error of the approximate steps and a result on perturbed Newton methods. This condition is in fact equivalent to the characterization given by Dembo, Eisenstat and Steihaug.

Authors

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

Keywords

nonlinear system of equations in Rn; inexact Newton method; residual; local convergence; forcing term; q-convergence order.

Cite this paper as:

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, pp. 129-133, https://ictp.acad.ro/jnaat/journal/article/view/2000-vol29-no2-art2

PDF

Scanned paper.

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 Roumaine

Paper on the journal website

https://doi.org/10.33993/jnaat292-662

 

Print ISSN

1222-9024

Online ISSN

2457-8126

MR

MR

Online ISSN

2457-8126

Google Scholar citations

Google Scholar citations

[1] E. Catinas, Inexact  perturbed  Newton  methods,  and  some  applications  for  a  class  of Krylov solvers, J. Optim. Theory Appl.,108 (2001) no. 3, pp. 543–570.

[2] E. Catinas, On  the  high  convergence  orders  of  the  Newton-GMBACK  methods, Rev. Anal. Num ́er. Th ́eor. Approx., 28 (1999) no. 2, pp. 125–132.

[3] E. Catinas, Newton and Newton-Krylov methods for solving nonlinear systems in Rn, Ph.D. thesis, ”Babes-Bolyai” University of Cluj–Napoca, Romania, 1999.

[4] E. Catinas, The  relationship  between  three  practical  models  of  Newton  methods  with high convergence orders , submitted.

[5] E.  Catinas, Inexact  perturbed  Newton  methods  for  nonlinear  systems  with  singular Jacobians, submitted.

[6] E. Catinas, The high convergence orders of the successive approximations, submitted.

[7] E.  Catinas, Finite  difference  approximations  in  the  Newton-Krylov  methods,  manuscript.

[8] D. Cores and R.A. Tapia, Perturbation Lemma for the Newton Method with Application  to  the  SQP  Newton  Method,  J. Optim. Theory Appl.,  97 (1998),  pp. 271–280.

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

[10] J. E. Dennis, Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice–Hall Series in Computational Mathematics, Englewood Cliffs, NJ, 1983.

[11] N. J. Higham, Accuracy  and  Stability  of  Numerical  Algorithms, SIAM, Philadelphia, PA, 1996.

[12] St.  Maruster, Numerical  Methods  for  Solving  Nonlinear  Equations,  Ed.  Tehnica, Bucharest, 1981 (in Romanian).

[13] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. 5 Quadratic convergence of the inexact Newton methods 133

[14] I.  Pavaloiu, Introduction  to  the  Approximation  of  the  Solutions  of  Equations,  Ed. Dacia, Cluj-Napoca, 1976 (in Romanian).

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

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

[17] J. L. Rigal and J. Gaches, On the compatibility of a given solution with the data of a linear system, J. ACM, 14 (1967), pp. 543–548.

[18] H. F. Walker, An approach to continuation using Krylov subspace methods, Research Report  1/97/89,  Dept.  of  Math.,  Utah  State  University,  appeared  in  ComputationalScience in the 21st Century, M.–O. Bristeau, G. Etgen, W. Fitzgibbon, J. L. Lions, J.

Periaux and M. F. Wheeler, eds., John Wiley and Sons, Ltd., 1997, pp. 72–82

Paper (preprint) in HTML form

jnaat,+Journal+manager,+2000+Catinas+-+ANTA+-+A+note+on+the+quadr+conv+of+the+inex+Newton+meths+16-1

A NOTE ON THE QUADRATIC CONVERGENCE OF THE INEXACT NEWTON METHODS*

EMIL CĂTINAŞ

Abstract

We show that a new sufficient condition for the convergence with q q qqq-order two of the inexact Newton iterates may be obtained by considering the normwise backward error of the approximate steps and a result on perturbed Newton methods.

This condition is in fact equivalent to the characterization given by Dembo, Eisenstat and Steihaug.

AMS Subject Classification: 65 H 10 .

1. INTRODUCTION

The inexact Newton (IN) method is given by the algorithm
Choose an initial approximation y 0 ∈ D y 0 ∈ D y_(0)in Dy_{0} \in Dy0∈D
For k = 0 , 1 , … k = 0 , 1 , … k=0,1,dotsk=0,1, \ldotsk=0,1,… until "convergence" do
Find s k s k s_(k)s_{k}sk such that F ′ ( y k ) s k = − F ( y k ) + r k F ′ y k s k = − F y k + r k F^(')(y_(k))s_(k)=-F(y_(k))+r_(k)F^{\prime}\left(y_{k}\right) s_{k}=-F\left(y_{k}\right)+r_{k}F′(yk)sk=−F(yk)+rk
Set y k + 1 = y k + s k y k + 1 = y k + s k y_(k+1)=y_(k)+s_(k)y_{k+1}=y_{k}+s_{k}yk+1=yk+sk,
and it constitutes a classical model for the practical solving of nonlinear systems F ( y ) = 0 F ( y ) = 0 F(y)=0F(y)=0F(y)=0 by the Newton method, where F : D ⊆ R n → R n F : D ⊆ R n → R n F:D subeR^(n)rarrR^(n)F: D \subseteq \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}F:D⊆Rn→Rn. The error terms (the residuals) r k r k r_(k)r_{k}rk represent the amounts by which the approximate solutions s k s k s_(k)s_{k}sk fail to satisfy the exact linear systems F ′ ( y k ) s = − F ( y k ) F ′ y k s = − F y k F^(')(y_(k))s=-F(y_(k))F^{\prime}\left(y_{k}\right) s=-F\left(y_{k}\right)F′(yk)s=−F(yk).
Under certain conditions, the IN iterates converge to a solution y ∗ y ∗ y^(**)y^{*}y∗ of the mentioned nonlinear system, the convergence order being given by the magnitude of the residuals (see [9]).
We are interested in the high convergence orders of the iterates, namely in the convergence with q q qqq-order two (for the definitions of the convergence orders see [13, ch.9], and also [16], [15]). The (standard) assumptions on F F FFF for this case are the following:
  • there exists y ∗ ∈ D y ∗ ∈ D y^(**)in Dy^{*} \in Dy∗∈D such that F ( y ∗ ) = 0 F y ∗ = 0 F(y^(**))=0F\left(y^{*}\right)=0F(y∗)=0;
  • the mapping F F FFF is differentiable on a neighborhood of y ∗ y ∗ y^(**)y^{*}y∗, with the derivative F ′ F ′ F^(')F^{\prime}F′ Lipschitz continuous at y ∗ ⊴ 1 y ∗ ⊴ 1 y^(**)⊴^(1)y^{*} \unlhd^{1}y∗⊴1
‖ F ′ ( y ) − F ′ ( y ∗ ) ‖ ≤ L ‖ y − y ∗ ‖ , for some L ≥ 0 , when ‖ y − y ∗ ‖ < ε ; F ′ ( y ) − F ′ y ∗ ≤ L y − y ∗ ,  for some  L ≥ 0 ,  when  y − y ∗ < ε ; ||F^(')(y)-F^(')(y^(**))|| <= L||y-y^(**)||,quad" for some "L >= 0," when "||y-y^(**)|| < epsi;\left\|F^{\prime}(y)-F^{\prime}\left(y^{*}\right)\right\| \leq L\left\|y-y^{*}\right\|, \quad \text { for some } L \geq 0, \text { when }\left\|y-y^{*}\right\|<\varepsilon ;‖F′(y)−F′(y∗)‖≤L‖y−y∗‖, for some L≥0, when ‖y−y∗‖<ε;
  • the Jacobian F ′ ( y ∗ ) F ′ y ∗ F^(')(y^(**))F^{\prime}\left(y^{*}\right)F′(y∗) is nonsingular.
Dembo, Eisenstat and Steihaug proved the following result.
Theorem 1. [9] Suppose that F obeys the standard assumptions and that for some initial approximation y 0 ∈ D y 0 ∈ D y_(0)in Dy_{0} \in Dy0∈D, the sequence ( y k ) k ≥ 0 y k k ≥ 0 (y_(k))_(k >= 0)\left(y_{k}\right)_{k \geq 0}(yk)k≥0 given by the IN method converges to y ∗ y ∗ y^(**)y^{*}y∗. Then its q q qqq-convergence order is at least two if and only if ‖ r k ‖ = O ( ‖ F ( y k ) ‖ 2 ) r k = O F y k 2 ||r_(k)||=O(||F(y_(k))||^(2))\left\|r_{k}\right\|=\mathcal{O}\left(\left\|F\left(y_{k}\right)\right\|^{2}\right)‖rk‖=O(‖F(yk)‖2) as k → ∞ k → ∞ k rarr ook \rightarrow \inftyk→∞, or, equivalently,
(1) ‖ r k ‖ ‖ F ( y k ) ‖ = O ( ‖ F ( y k ) ‖ ) , as k → ∞ . (1) r k F y k = O F y k ,  as  k → ∞ . {:(1)(||r_(k)||)/(||F(y_(k))||)=O(||F(y_(k))||)","quad" as "k rarr oo.:}\begin{equation*} \frac{\left\|r_{k}\right\|}{\left\|F\left(y_{k}\right)\right\|}=\mathcal{O}\left(\left\|F\left(y_{k}\right)\right\|\right), \quad \text { as } k \rightarrow \infty . \tag{1} \end{equation*}(1)‖rk‖‖F(yk)‖=O(‖F(yk)‖), as k→∞.
In our recent paper [1] (see also [3]) we have introduced the inexact perturbed Newton methods, characterizing their convergence orders in terms of perturbations and residuals. In the following analysis we shall consider the perturbed Newton (PN) iterates:
( F ′ ( y k ) + Δ k ) s k = − F ( y k ) + δ k y k + 1 = y k + s k , k = 0 , 1 , … , y 0 ∈ D . F ′ y k + Δ k s k = − F y k + δ k y k + 1 = y k + s k , k = 0 , 1 , … , y 0 ∈ D . {:[(F^(')(y_(k))+Delta_(k))s_(k)=-F(y_(k))+delta_(k)],[y_(k+1)=y_(k)+s_(k)","quad k=0","1","dots","quady_(0)in D.]:}\begin{aligned} & \left(F^{\prime}\left(y_{k}\right)+\Delta_{k}\right) s_{k}=-F\left(y_{k}\right)+\delta_{k} \\ & y_{k+1}=y_{k}+s_{k}, \quad k=0,1, \ldots, \quad y_{0} \in D . \end{aligned}(F′(yk)+Δk)sk=−F(yk)+δkyk+1=yk+sk,k=0,1,…,y0∈D.
The matrices Δ k Δ k Delta_(k)\Delta_{k}Δk and the vectors δ k δ k delta_(k)\delta_{k}δk are some arbitrary perturbations to the linear systems F ′ ( y k ) s = − F ( y k ) F ′ y k s = − F y k F^(')(y_(k))s=-F(y_(k))F^{\prime}\left(y_{k}\right) s=-F\left(y_{k}\right)F′(yk)s=−F(yk), the perturbed linear systems being verified by the exact solutions s k s k s_(k)s_{k}sk (it is implicitely assumed that the perturbed Jacobians F ′ ( y k ) + Δ k F ′ y k + Δ k F^(')(y_(k))+Delta_(k)F^{\prime}\left(y_{k}\right)+\Delta_{k}F′(yk)+Δk are invertible for k = 0 , 1 , … k = 0 , 1 , … k=0,1,dotsk=0,1, \ldotsk=0,1,… ). We have obtained the following result: 2 2 ^(2){ }^{2}2
Corollary 2. [1, [8] Suppose that F obeys the standard assumptions and that for some initial approximation y 0 ∈ D y 0 ∈ D y_(0)in Dy_{0} \in Dy0∈D, the sequence ( y k ) k ≥ 0 y k k ≥ 0 (y_(k))_(k >= 0)\left(y_{k}\right)_{k \geq 0}(yk)k≥0 given by the PN method is well defined and converges to y ∗ y ∗ y^(**)y^{*}y∗. If
‖ Δ k ‖ = O ( ‖ F ( y k ) ‖ ) and ‖ δ k ‖ = O ( ‖ F ( y k ) ‖ 2 ) , as k → ∞ , Δ k = O F y k  and  δ k = O F y k 2 ,  as  k → ∞ , ||Delta_(k)||=O(||F(y_(k))||)" and "||delta_(k)||=O(||F(y_(k))||^(2)),quad" as "k rarr oo,\left\|\Delta_{k}\right\|=\mathcal{O}\left(\left\|F\left(y_{k}\right)\right\|\right) \text { and }\left\|\delta_{k}\right\|=\mathcal{O}\left(\left\|F\left(y_{k}\right)\right\|^{2}\right), \quad \text { as } k \rightarrow \infty,‖Δk‖=O(‖F(yk)‖) and ‖δk‖=O(‖F(yk)‖2), as k→∞,
then ( y k ) k ≥ 0 y k k ≥ 0 (y_(k))_(k >= 0)\left(y_{k}\right)_{k \geq 0}(yk)k≥0 converges with q q qqq-order at least two.
In the following section we shall show that the sufficient condition (1) may be expressed in an equivalent form.

2. MAIN RESULT

Let A ∈ R n × n A ∈ R n × n A inR^(n xx n)A \in \mathbb{R}^{n \times n}A∈Rn×n be a nonsingular matrix, b ∈ R n b ∈ R n b inR^(n)b \in \mathbb{R}^{n}b∈Rn an arbitrary vector, and consider an approximate solution x ~ ∈ R n x ~ ∈ R n tilde(x)inR^(n)\tilde{x} \in \mathbb{R}^{n}x~∈Rn of the linear system A x = b A x = b Ax=bA x=bAx=b. The normwise backward error of x ~ x ~ tilde(x)\tilde{x}x~ was introduced by Rigal and Gaches [17] and is defined by:
Π ( x ~ ) = min { ε : ( A + Δ A ) x ~ = b + Δ b , ‖ Δ A ‖ F ≤ ε ‖ E ‖ F , ‖ Δ b ‖ 2 ≤ ε ‖ f ‖ 2 } Π ( x ~ ) = min ε : A + Δ A x ~ = b + Δ b , Δ A F ≤ ε ‖ E ‖ F , Δ b 2 ≤ ε ‖ f ‖ 2 Pi( tilde(x))=min{epsi:(A+Delta_(A))( tilde(x))=b+Delta_(b),||Delta_(A)||_(F) <= epsi||E||_(F),||Delta_(b)||_(2) <= epsi||f||_(2)}\Pi(\tilde{x})=\min \left\{\varepsilon:\left(A+\Delta_{A}\right) \tilde{x}=b+\Delta_{b},\left\|\Delta_{A}\right\|_{F} \leq \varepsilon\|E\|_{F},\left\|\Delta_{b}\right\|_{2} \leq \varepsilon\|f\|_{2}\right\}Π(x~)=min{ε:(A+ΔA)x~=b+Δb,‖ΔA‖F≤ε‖E‖F,‖Δb‖2≤ε‖f‖2}, where the parameters E ∈ R n × n E ∈ R n × n E inR^(n xx n)E \in \mathbb{R}^{n \times n}E∈Rn×n and f ∈ R n f ∈ R n f inR^(n)f \in \mathbb{R}^{n}f∈Rn are arbitrary, and ‖ ⋅ ‖ F ‖ ⋅ ‖ F ||*||_(F)\|\cdot\|_{F}‖⋅‖F denotes the Frobenius norm: ‖ Z ‖ F = ( ∑ i , j = 1 , … , n z i j 2 ) 1 / 2 ‖ Z ‖ F = ∑ i , j = 1 , … , n   z i j 2 1 / 2 ||Z||_(F)=(sum_(i,j=1,dots,n)z_(ij)^(2))^(1//2)\|Z\|_{F}=\left(\sum_{i, j=1, \ldots, n} z_{i j}^{2}\right)^{1 / 2}‖Z‖F=(∑i,j=1,…,nzij2)1/2. The value of Π ( x ~ ) Π ( x ~ ) Pi( tilde(x))\Pi(\tilde{x})Π(x~) is
Π ( x ~ ) = ‖ b − A x ~ ‖ 2 ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 + ‖ f ‖ 2 , Π ( x ~ ) = ‖ b − A x ~ ‖ 2 ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 + ‖ f ‖ 2 , Pi( tilde(x))=(||b-A( tilde(x))||_(2))/(||E||_(F)*||( tilde(x))||_(2)+||f||_(2)),\Pi(\tilde{x})=\frac{\|b-A \tilde{x}\|_{2}}{\|E\|_{F} \cdot\|\tilde{x}\|_{2}+\|f\|_{2}},Π(x~)=‖b−Ax~‖2‖E‖F⋅‖x~‖2+‖f‖2,
and the minimum is attained by the backward errors
Δ A = ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 + ‖ f ‖ 2 ( b − A x ~ ) z t , with z = 1 ‖ x ~ ‖ 2 2 x ~ Δ b = − ‖ f ‖ 2 ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 + ‖ f ‖ 2 ( b − A x ~ ) Δ A = ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 + ‖ f ‖ 2 ( b − A x ~ ) z t ,  with  z = 1 ‖ x ~ ‖ 2 2 x ~ Δ b = − ‖ f ‖ 2 ‖ E ‖ F ⋅ ‖ x ~ ‖ 2 + ‖ f ‖ 2 ( b − A x ~ ) {:[Delta_(A)=(||E||_(F)*||( tilde(x))||_(2))/(||E||_(F)*||( tilde(x))||_(2)+||f||_(2))(b-A tilde(x))z^(t)","quad" with "z=(1)/(||( tilde(x))||_(2)^(2)) tilde(x)],[Delta_(b)=-(||f||_(2))/(||E||_(F)*||( tilde(x))||_(2)+||f||_(2))(b-A tilde(x))]:}\begin{aligned} \Delta_{A} & =\frac{\|E\|_{F} \cdot\|\tilde{x}\|_{2}}{\|E\|_{F} \cdot\|\tilde{x}\|_{2}+\|f\|_{2}}(b-A \tilde{x}) z^{t}, \quad \text { with } z=\frac{1}{\|\tilde{x}\|_{2}^{2}} \tilde{x} \\ \Delta_{b} & =-\frac{\|f\|_{2}}{\|E\|_{F} \cdot\|\tilde{x}\|_{2}+\|f\|_{2}}(b-A \tilde{x}) \end{aligned}ΔA=‖E‖F⋅‖x~‖2‖E‖F⋅‖x~‖2+‖f‖2(b−Ax~)zt, with z=1‖x~‖22x~Δb=−‖f‖2‖E‖F⋅‖x~‖2+‖f‖2(b−Ax~)
With these relations we can prove the following result.
Theorem 3. Suppose that F F FFF obeys the standard assumptions and that for some initial approximation y 0 ∈ D y 0 ∈ D y_(0)in Dy_{0} \in Dy0∈D, the sequence ( y k ) k ≥ 0 y k k ≥ 0 (y_(k))_(k >= 0)\left(y_{k}\right)_{k \geq 0}(yk)k≥0 given by the IN method converges to y ∗ y ∗ y^(**)y^{*}y∗. If
(2) ‖ r k ‖ 2 ‖ s k ‖ 2 + ‖ F ( y k ) ‖ 2 = O ( ‖ F ( y k ) ‖ 2 ) , as k → ∞ (2) r k 2 s k 2 + F y k 2 = O F y k 2 ,  as  k → ∞ {:(2)(||r_(k)||_(2))/(||s_(k)||_(2)+||F(y_(k))||_(2))=O(||F(y_(k))||_(2))","quad" as "k rarr oo:}\begin{equation*} \frac{\left\|r_{k}\right\|_{2}}{\left\|s_{k}\right\|_{2}+\left\|F\left(y_{k}\right)\right\|_{2}}=\mathcal{O}\left(\left\|F\left(y_{k}\right)\right\|_{2}\right), \quad \text { as } k \rightarrow \infty \tag{2} \end{equation*}(2)‖rk‖2‖sk‖2+‖F(yk)‖2=O(‖F(yk)‖2), as k→∞
then the iterates converge with q q qqq-order at least two.
Proof. For each k k kkk, consider the normwise backward errors of the approximate steps s k s k s_(k)s_{k}sk, choosing the parameters E E EEE and f f fff such that ‖ E ‖ F = ‖ F ( y k ) ‖ 2 ‖ E ‖ F = F y k 2 ||E||_(F)=||F(y_(k))||_(2)\|E\|_{F}=\left\|F\left(y_{k}\right)\right\|_{2}‖E‖F=‖F(yk)‖2 and ‖ f ‖ 2 = ‖ F ( y k ) ‖ 2 2 ‖ f ‖ 2 = F y k 2 2 ||f||_(2)=||F(y_(k))||_(2)^(2)\|f\|_{2}=\left\|F\left(y_{k}\right)\right\|_{2}^{2}‖f‖2=‖F(yk)‖22. Corollary 2 and the inequality ‖ Z ‖ 2 ≤ ‖ Z ‖ F ‖ Z ‖ 2 ≤ ‖ Z ‖ F ||Z||_(2) <= ||Z||_(F)\|Z\|_{2} \leq\|Z\|_{F}‖Z‖2≤‖Z‖F, true for all Z ∈ R n × n Z ∈ R n × n Z inR^(n xx n)Z \in \mathbb{R}^{n \times n}Z∈Rn×n (cf., e.g., [11]), lead to the stated result, provided that the ε ε epsi\varepsilonε 's are uniformly bounded. This condition is written as
Π ( s k ) = ‖ r k ‖ 2 ‖ s k ‖ 2 ⋅ ‖ F ( y k ) ‖ 2 + ‖ F ( y k ) ‖ 2 2 ≤ K , for some fixed K > 0 Π s k = r k 2 s k 2 ⋅ F y k 2 + F y k 2 2 ≤ K ,  for some fixed  K > 0 Pi(s_(k))=(||r_(k)||_(2))/(||s_(k)||_(2)*||F(y_(k))||_(2)+||F(y_(k))||_(2)^(2)) <= K,quad" for some fixed "K > 0\Pi\left(s_{k}\right)=\frac{\left\|r_{k}\right\|_{2}}{\left\|s_{k}\right\|_{2} \cdot\left\|F\left(y_{k}\right)\right\|_{2}+\left\|F\left(y_{k}\right)\right\|_{2}^{2}} \leq K, \quad \text { for some fixed } K>0Π(sk)=‖rk‖2‖sk‖2⋅‖F(yk)‖2+‖F(yk)‖22≤K, for some fixed K>0
which is exactly relation (2).
Remarks. 1. Condition (2) is in fact equivalent to condition (1). Indeed, Theorem 3 shows that relation (2) implies the quadratic convergence. For the converse, assuming that the IN iterates converge quadratically, we notice that
‖ r k ‖ 2 ‖ s k ‖ 2 + ‖ F ( y k ) ‖ 2 ≤ ‖ r k ‖ 2 ‖ F ( y k ) ‖ 2 ≤ K ‖ F ( y k ) ‖ 2 , k = 0 , 1 , … , r k 2 s k 2 + F y k 2 ≤ r k 2 F y k 2 ≤ K F y k 2 , k = 0 , 1 , … , (||r_(k)||_(2))/(||s_(k)||_(2)+||F(y_(k))||_(2)) <= (||r_(k)||_(2))/(||F(y_(k))||_(2)) <= K||F(y_(k))||_(2),quad k=0,1,dots,\frac{\left\|r_{k}\right\|_{2}}{\left\|s_{k}\right\|_{2}+\left\|F\left(y_{k}\right)\right\|_{2}} \leq \frac{\left\|r_{k}\right\|_{2}}{\left\|F\left(y_{k}\right)\right\|_{2}} \leq K\left\|F\left(y_{k}\right)\right\|_{2}, \quad k=0,1, \ldots,‖rk‖2‖sk‖2+‖F(yk)‖2≤‖rk‖2‖F(yk)‖2≤K‖F(yk)‖2,k=0,1,…,
which shows that quadratic convergence implies (2) (the right inequality above is ensured by Theorem 1 ).
2. It is easy to prove that the Euclidean norm from (2) may be replaced by an arbitrary norm on R n R n R^(n)\mathbb{R}^{n}Rn, since all norms are equivalent on a finite dimensional normed space.
3. Condition (2) has been obtained in a natural fashion by considering the normwise backward errors of the approximate steps. One can also obtain it taking into account that under the standard assumptions, the sequences ( y k − y ∗ ) k ≥ 0 y k − y ∗ k ≥ 0 (y_(k)-y^(**))_(k >= 0)\left(y_{k}-y^{*}\right)_{k \geq 0}(yk−y∗)k≥0 and ( s k ) k ≥ 0 s k k ≥ 0 (s_(k))_(k >= 0)\left(s_{k}\right)_{k \geq 0}(sk)k≥0 converge quadratically to zero only at the same time, with lim k → ∞ ‖ y k − y ∗ ‖ / ‖ y k + 1 − y k ‖ = 1 lim k → ∞   y k − y ∗ / y k + 1 − y k = 1 lim_(k rarr oo)||y_(k)-y^(**)||//||y_(k+1)-y_(k)||=1\lim _{k \rightarrow \infty}\left\|y_{k}-y^{*}\right\| /\left\|y_{k+1}-y_{k}\right\|=1limk→∞‖yk−y∗‖/‖yk+1−yk‖=1 (see [18]). The same situation appears concerning ( y k − y ∗ ) k ≥ 0 y k − y ∗ k ≥ 0 (y_(k)-y^(**))_(k >= 0)\left(y_{k}-y^{*}\right)_{k \geq 0}(yk−y∗)k≥0 and ( F ( y k ) ) k ≥ 0 F y k k ≥ 0 (F(y_(k)))_(k >= 0)\left(F\left(y_{k}\right)\right)_{k \geq 0}(F(yk))k≥0, since the standard assumptions ensure that there exists α > 0 α > 0 alpha > 0\alpha>0α>0 such that ‖ y − y ∗ ‖ / α ≤ ‖ F ( y ) ‖ ≤ α ‖ y − y ∗ ‖ y − y ∗ / α ≤ ‖ F ( y ) ‖ ≤ α y − y ∗ ||y-y^(**)||//alpha <= ||F(y)|| <= alpha||y-y^(**)||\left\|y-y^{*}\right\| / \alpha \leq\|F(y)\| \leq \alpha\left\|y-y^{*}\right\|‖y−y∗‖/α≤‖F(y)‖≤α‖y−y∗‖ when y y yyy is sufficiently close to y ∗ y ∗ y^(**)y^{*}y∗ (see [9]).

REFERENCES

[1] E. Cătinaş, Inexact perturbed Newton methods, and some applications for a class of Krylov solvers, J. Optim. Theory Appl., 108 (2001) no. 3, pp. 543-570. ©
[2] E. Cătinaş, On the high convergence orders of the Newton-GMBACK methods, Rev. Anal. Numér. Théor. Approx., 28 (1999) no. 2, pp. 125-132. ©
[3] E. Cătinaş, Newton and Newton-Krylov methods for solving nonlinear systems in R n R n R^(n)\mathbb{R}^{n}Rn, Ph.D. thesis, "Babeş-Bolyai" University of Cluj-Napoca, Romania, 1999.
[4] E. Cătinaş, The relationship between three practical models of Newton methods with high convergence orders, submitted. 뜸
[5] E. CĂtinaş, Inexact perturbed Newton methods for nonlinear systems with singular Jacobians, submitted.
[6] E. Cătinaş, The high convergence orders of the successive approximations, submitted. [
[7] E. Cătinaş, Finite difference approximations in the Newton-Krylov methods, manuscript.
[8] D. Cores and R.A. Tapia, Perturbation Lemma for the Newton Method with Application to the SQP Newton Method, J. Optim. Theory Appl., 97 (1998), pp. 271-280. 뜸
[9] R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal., 19 (1982), pp. 400-408. ㄸ
[10] J. E. Dennis, Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall Series in Computational Mathematics, Englewood Cliffs, NJ, 1983.
[11] N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, PA, 1996.
[12] Şt. Măruşter, Numerical Methods for Solving Nonlinear Equations, Ed. Tehnicǎ, Bucharest, 1981 (in Romanian).
[13] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[14] I. Păvăloiu, Introduction to the Approximation of the Solutions of Equations, Ed. Dacia, Cluj-Napoca, 1976 (in Romanian). s
[15] F. A. Potra, On Q Q QQQ-order and R R RRR-order of convergence, J. Optim. Theory Appl., 63 (1989), pp. 415-431. □
[16] W. C. Rheinboldt, Methods for Solving Systems of Nonlinear Equations, Second ed., SIAM, Philadelphia, 1998.
[17] J. L. Rigal and J. Gaches, On the compatibility of a given solution with the data of a linear system, J. ACM, 14 (1967), pp. 543-548. ㅁ
[18] H. F. Walker, An approach to continuation using Krylov subspace methods, Research Report 1/97/89, Dept. of Math., Utah State University, appeared in Computational Science in the 21st Century, M.-O. Bristeau, G. Etgen, W. Fitzgibbon, J. L. Lions, J. Periaux and M. F. Wheeler, eds., John Wiley and Sons, Ltd., 1997, pp. 72-82.
Received June 7, 1999
"T. Popoviciu" Institute of Numerical Analysis
Romanian Academy
P.O. Box 68, 3400 Cluj-Napoca 1
Romania
  1. *Work supported by the National Agency for Science, Technology and Innovation under grant GANSTI 6100 GR/2000.
  2. 1 1 ^(1){ }^{1}1 We shall use the symbols ‖ ⋅ ‖ ‖ ⋅ ‖ ||*||\|\cdot\|‖⋅‖ and ‖ ⋅ ‖ 2 ‖ ⋅ ‖ 2 ||*||_(2)\|\cdot\|_{2}‖⋅‖2 for an arbitrary, resp. for the Euclidean norm on R n R n R^(n)\mathbb{R}^{n}Rn, and for their induced operator norms.
    2 2 ^(2){ }^{2}2 The same result can be found in [8]; we have obtained independently this Corollary in the manuscript of 1 , before 8 was published.
2000

Related Posts