Local convergence of some Newton-type methods
for nonlinear systems^∗

Ion Păvăloiu^† Dedicated to Professor Elena Popoviciu on the occasion of her 80th birthday.

(Date: January 21, 2004)

Abstract.

In order to approximate the solutions of nonlinear systems

F(x)=0,

with $F:D\subseteq{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{n}$ , $n\in{\mathbb{N}}$ , we consider the method

	$\displaystyle x_{k+1}$	$\displaystyle=x_{k}-A_{k}F(x_{k})$
	$\displaystyle A_{k+1}$	$\displaystyle=A_{k}(2I-F^{\prime}(x_{k+1})A_{k}),\;k=0,1,...,\ A_{0}\in M_{n}(% {\mathbb{R}}),x_{0}\in D,$

and we study its local convergence.

Key words and phrases:

Nonlinear systems of equations.

1991 Mathematics Subject Classification:

65H10.

^∗This work has been supported by the Romanian Academy under grant GAR 16/2004.

^†“T. Popoviciu” Institute of Numerical Analysis, O.P 1, C.P. 68, Cluj-Napoca, and North University Baia Mare, Romania, e-mail: pavaloiu@ictp.acad.ro.

1. Introduction

Most of the problems regarding the methods of approximating the solutions of nonlinear equations in abstract spaces lead, as is well known, to solving of linear systems in ${\mathbb{R}}^{n}$ , $n\in{\mathbb{N}}.$ From here, the importance of the study of the methods of approximating the solutions of linear and nonlinear problems in ${\mathbb{R}}^{n}.$

For the linear systems there have been studied several methods which offer very good results for some relatively large classes of problems. In the case of the nonlinear systems, the number of the methods is limited and the possibility of their applications differs from system to system.

One of the most used methods is the Newton method. The application of this method to nonlinear systems requires at each step the approximate solution of a linear system. It is well known that the matrix of this linear system is given by the Jacobian of the nonlinear system.

The approximate computation of the elements of the matrix may introduce not only truncation errors, but also rounding errors, and therefore the resulted linear system at each iteration step is a perturbed one. Further errors may appear from the algorithm used for solving the linear system.

A method which can overcome a part of the above mentioned difficulties seems to be the one which at each iteration step uses an approximation for the inverse of the Jacobian.

More precisely, let $F:D\subseteq{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{n}$ and the equation

(1)

F(x)=0.

We denote by $M_{n}({\mathbb{R}})$ the set of the square matrices of order $n$ , having real elements.

Let $x_{0}\in D$ and $A_{0}\in M_{n}({\mathbb{R}}).$ Consider the sequences $(x_{k})_{k\geq 0}$ and $(A_{k})_{k\geq 0}$ given by

(2)		$\displaystyle x_{k+1}$	$\displaystyle=x_{k}-A_{k}F(x_{k})$
	$\displaystyle A_{k+1}$	$\displaystyle=A_{k}(2I-F^{\prime}(x_{k+1})A_{k}),\;k=0,1,...$

where $I$ is the unity matrix.

The matrices $A_{k}$ approximate, as we shall see, the inverse of the Jacobian matrix.

In this note we show that locally, the $r$ -convergence order of the sequence $(x_{k})_{k\geq 0}$ is the same as for the sequence given by the Newton method, i.e., 2. This result completes those obtained in [2]–[8].

2. Local convergence

The following results have maybe a smaller practical importance, but they prove that, theoretically, the Newton method and method (2) offer the same results regarding the local convergence. Method (2) presents the advantage that eliminates the algorithm errors mentioned above. However, the truncation and the rounding errors cannot be avoided by this algorithm. This algorithm may be easily programmed.

Regarding the function $F$ we make the following assumptions:

a)

system (1) has a solution $x^{\ast}\in D$ ;
b)

$F$ is of class $C^{1}$ on $D$ ;
c)

there exists $F^{\prime}(x^{\ast})^{-1}.$

Lemma 1.

If $F$ verifies assumptions $a)-c)$ and there exists $r>0$ such that:

i.

$S=\left\{x\in R^{n}:\left\|x-x^{\ast}\right\|\leq r\right\}\subseteq D$
ii.

$mcr=q<1,$ where $m=\sup_{x\in D}\left\|F^{\prime\prime}(x)\right\|$ and $c=\left\|F^{\prime}(x^{\ast})^{-1}\right\|$ ,

then for any $x\in S$ there exists $F^{\prime}(x)^{-1}$ and

(3)

\left\|F^{\prime}(x)^{-1}\right\|\leq\tfrac{c}{1-q}.

Proof.

Let $x\in D$ and consider the difference

(4)

\Delta(x)=F^{\prime}(x^{\ast})-F^{\prime}(x)=F^{\prime}(x^{\ast})\left(I-F^{% \prime}(x^{\ast})^{-1}F^{\prime}(x)\right).

It follows that

(5)

\left(I-F^{\prime}(x^{\ast})^{-1}F^{\prime}(x)\right)=F^{\prime}(x^{\ast})^{-1% }\Delta(x).

The finite increment formula [6] leads to relation

\left\|\Delta(x)\right\|=\left\|F^{\prime}(x^{\ast})-F^{\prime}(x)\right\|\leq m% \left\|x^{\ast}-x\right\|\leq mr,

from which, by (5) we get

\left\|I-F^{\prime}(x^{\ast})^{-1}F^{\prime}(x)\right\|\leq cmr=q<1.

It follows by the Banach lemma that $F^{\prime}(x^{\ast})^{-1}F^{\prime}(x)$ is invertible and

\left(F^{\prime}(x^{\ast})^{-1}F^{\prime}(x)\right)^{-1}=\big[I-F^{\prime}(x^{% \ast})^{-1}\Delta x\big]^{-1}.

Further,

F^{\prime}(x)^{-1}=\left(I-F^{\prime}(x^{\ast})^{-1}\Delta x\right)^{-1}F^{% \prime}(x^{\ast})^{-1},

whence, by taking norms we obtain (3). ∎

Regarding the convergence of the iteration (2) we obtain the following result.

Theorem 2.

If $F$ obeys the hypothesis of Lemma 1 and the initial approximations $x_{0}\in D$ and $A_{0}\in M_{n}(R)$ are taken such that

(6)	$\displaystyle\delta_{0}$	$\displaystyle=\tfrac{am}{2}\left\\|x^{\ast}-x_{0}\right\\|\leq\alpha d,$
(7)	$\displaystyle\rho_{0}$	$\displaystyle=\left\\|I-F^{\prime}(x_{0})A_{0}\right\\|\leq\beta d,$
(8)	$\displaystyle\tfrac{2\alpha d}{am}$	$\displaystyle\leq r,$

where $a=\frac{c}{1-q},$ $d<1$ and $\alpha,\beta>0$ obey

(9)		$\displaystyle\alpha+\beta ab$	$\displaystyle<1$
(10)		$\displaystyle\left[\beta+2ab\left(\beta d+1\right)^{2}\alpha\right]$	$\displaystyle<\beta$

where $b=\sup_{x\in D}\left\|F^{\prime}(x)\right\|.$

Then for all $k\in N$ , we have $x_{k}\in S$ and

(11)		$\displaystyle\left\\|x_{k}-x^{\ast}\right\\|$	$\displaystyle\leq\tfrac{2\alpha}{ma}d^{2^{k}},$
(12)		$\displaystyle\left\\|I-F^{\prime}(x_{k})A_{k}\right\\|$	$\displaystyle\leq\beta d^{2^{k}},\;\;k=0,1,....$

Proof.

From (8) and (6) it follows $\left\|x^{\ast}-x_{0}\right\|\leq r$ and therefore $x_{0}\in S.$ From the identity

\theta=F(x^{\ast})=F(x^{\ast})-F(x_{0})-F^{\prime}(x_{0})(x^{\ast}-x_{0})+F^{% \prime}(x_{0})(x^{\ast}-x_{0})+F(x_{0}),

taking into account (2) for $k=0,$ we get

(13)		$\displaystyle x_{1}-x^{\ast}=-F^{\prime}(x_{0})^{-1}\big[$	$\displaystyle F(x^{\ast})-F(x_{0})-F^{\prime}(x_{0})(x^{\ast}-x_{0})$
		$\displaystyle+(I-F^{\prime}(x_{0})A_{0})F(x_{0})\big].$

From the Taylor formula [6], it follows

(14)		$\displaystyle\left\\|F(x^{\ast})-F(x_{0})-F^{\prime}(x_{0})(x^{\ast}-x_{0})\right\\|$	$\displaystyle\leq\tfrac{m}{2}\left\\|x^{\ast}-x_{0}\right\\|^{2},\;\text{and}$
(15)		$\displaystyle\left\\|F(x_{0})\right\\|$	$\displaystyle=\left\\|F(x^{\ast})-F(x_{0})\right\\|\leq b\left\\|x^{\ast}-x_{0}% \right\\|.$

By (14), (15), (3) and (13) it results

\left\|x_{1}-x^{\ast}\right\|\leq\tfrac{am}{2}\left\|x^{\ast}-x_{0}\right\|^{2% }+ab\left\|I-F^{\prime}(x_{0})A_{0}\right\|\left\|x^{\ast}-x_{0}\right\|.

From the above relation, denoting by $\delta_{1}=\frac{am}{2}\left\|x_{1}-x^{\ast}\right\|$ and taking into account (6), (7) and (9),

\delta_{1}\leq\delta_{0}^{2}+ab\delta_{0}\rho_{0}\leq\alpha^{2}d^{2}+ab\alpha% \beta d^{2}\leq\alpha d^{2}.

Hence, by (8) it results that $x_{1}\in S$ and, moreover, (11) holds for $k=1.$

The second relation in (2) for $k=0$ implies that

(16)

\left\|I-F^{\prime}(x_{1})A_{1}\right\|\leq\left\|I-F^{\prime}(x_{1})A_{0}% \right\|^{2}.

The finite increment formula and the first relation in (2) imply

\left\|F^{\prime}(x_{1})-F^{\prime}(x_{0})\right\|\leq m\left\|x_{1}-x_{0}% \right\|\leq m\left\|A_{0}\right\|\left\|F(x_{0})\right\|.

If we take into account (15) and the above relation, denoting

\rho_{1}=\left\|I-F^{\prime}(x_{1})A_{1}\right\|

we are lead to

(17)

\rho_{1}\leq\left(\rho_{0}+mb\left\|A_{0}\right\|^{2}\left\|x^{\ast}-x_{0}% \right\|\right)^{2}.

Further, we have

\left\|A_{0}\right\|\leq\left\|F^{\prime}(x_{0})^{-1}\right\|\left\|F^{\prime}% (x_{0})A_{0}\right\|\leq a(\rho_{0}+1)\leq a(\beta d+1).

Using the above relation, by (17) and (10) it results

	$\displaystyle\rho_{1}$	$\displaystyle\leq\left[\rho_{0}+ma^{2}b(1+\beta d)\left\\|x^{\ast}-x_{0}\right% \\|\right]^{2}$
		$\displaystyle\leq\left[\rho_{0}+2ab(1+\beta d)\delta_{0}\right]^{2}$
		$\displaystyle\leq\beta d^{2},$

i.e., (12) for $k=1.$

Assuming now that (11) and (12) are verified for $k=i,$ $i\geq 1,$ then, proceeding as above, one can show that these relations also hold for $k=i+1.$

From (11), taking into account that $d<1,$ it follows that $\lim x_{k}=x^{\ast}.$ Since we have admitted that $F^{\prime}(x^{\ast})$ is continuous on $D,$ by (12) it follows that $\lim A_{k}=F^{\prime}(x^{\ast})^{-1}.$ ∎

Relations (11) and (12) show us that convergence order of method (2) is at least 2, i.e., is not smaller than that of the Newton method.

References

[1]
[2] Cătinaş, E. and Păvăloiu, I., On approximating the eigenvalues and eigenvectors of linear continuous operators, Rev. Anal. Numér. Théor. Approx., 26, nos. 1–2, pp. 19–27, 1997.
[3] Diaconu, A., On the convergence of an iterative proceeding of Chebyshev type, Rev. Anal. Numér. Théor. Approx., 24, nos. 1–2, pp. 19–27, 1995.
[4] Diaconu, A. and Păvăloiu, I., Sur quelques méthodes itératives pour la résolution des equations opérationelles, Rev. Anal. Numér. Théor. Approx., 1, no. 1, pp. 45–61, 1972.
[5] Lazăr, I., On a Newton type method, Rev. Anal. Numér. Théor. Approx., 23, no. 2, pp. 167–174, 1994.
[6] Păvăloiu, I., Introduction in the Theory of Approximating the Solutions of Equations, Ed. Dacia, Cluj-Napoca, 1976 (in Romanian).
[7] Ulm, S., On the iterative method with simultaneous approximation of the inverse of the operator, Izv. Nauk. Estonskoi S.S.R., 16, no. 4, pp. 403–411, 1967.
[8] Zehnder, J. E., A remark about Newton’s method, Comm. Pure Appl. Math., 37, pp. 361–366, 1974.
[9]

(14)		$\displaystyle\left\\|F(x^{\ast})-F(x_{0})-F^{\prime}(x_{0})(x^{\ast}-x_{0})\right\\|$	$\displaystyle\leq\tfrac{m}{2}\left\\|x^{\ast}-x_{0}\right\\|^{2},\;\text{and}$
(15)		$\displaystyle\left\\|F(x_{0})\right\\|$	$\displaystyle=\left\\|F(x^{\ast})-F(x_{0})\right\\|\leq b\left\\|x^{\ast}-x_{0}% \right\\|.$

Local convergence of some Newton type methods for nonlinear systems

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Local convergence of some Newton-type methods
for nonlinear systems^∗

Abstract.

Key words and phrases:

1991 Mathematics Subject Classification:

1. Introduction

2. Local convergence

Lemma 1.

Proof.

Theorem 2.

Proof.

References

Related Posts

Local convergence of some Newton type methods for nonlinear systems

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Local convergence of some Newton-type methods for nonlinear systems∗

Abstract.

Key words and phrases:

1991 Mathematics Subject Classification:

1. Introduction

2. Local convergence

Lemma 1.

Proof.

Theorem 2.

Proof.

References

Related Posts

Local convergence of some Newton-type methods
for nonlinear systems^∗