Given a nonlinear function $F:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, in order to approximate a solution of the equation

the classical Newton method is usually applied:

or, equivalently,

But in many cases it turns out that the above linear systems are not solved exactly, so, in order to study the convergence and the convergence order of the method, an error term must be taken into account.

In the paper [3] there are considered the inexact Newton methods:

Local convergence of these methods is studied and also necessary and sufficient conditions on the magnitude of $r_{k}$ are imposed for a certain convergence order to be achieved.

In the present paper we shall show how these results can be easily extended to the chord method, which has a theoretically higher efficiency index than the Newton method, since at each step for forming the linear system, only the values of $F$ at $x_{k}$ and $x_{k-1}$ are needed. Unfortunately the chord method is not very safe for all practical cases since, for example, a too fast convergence of one component in the sequence $\left(x_{k}\right)$ may lead to overflow errors or division by zero.

DEFINITION 1.1 [4] We call the first order divided difference of $F$ on the distinct points $x,y\in\mathbb{R}^{n}$, denoted by $[x,y;F]$, a linear operator belonging to $\mathscr{E}\left(\mathbb{R}^{n}\right)$ and satisfying

1. 1.

   $[x,y;F](y-x)=F(y)-F(x)$;

   Report issue for preceding element
2. 2.

   If $F$ is Fréchet differentiable at $z\in\mathbf{R}^{\prime\prime}$ then $\lim_{x,y\rightarrow z}[x,y;F]=F^{\prime}(z)$.

   Report issue for preceding element

It is known [1] that there are several ways to choose the linearly independent first order divided differences for given $F,x,y$, depending on the dimension $n\in\mathbf{N}$.

For example if $x=\left(x_{i}\right)_{i=1,n},y=\left(y_{i}\right)_{i=1,n}\in\mathbf{R}^{n}$, with $x_{i}\neq y_{i},i=\overline{1,n}$ then we can take

The chord method is given by the iteration

and it has the convergence order $\frac{1+\sqrt{5}}{2}$. The inexact chord method studied is

the residual $r_{k}$ satisfying $\left\|r_{k}\right\|/\left\|F\left(x_{k}\right)\right\|\leq\eta_{k}$, where $\|\cdot\|$ is a given norm in $\mathbf{R}^{n}$.
We shall suppose hereafter that the function $F$ obeys the following conditions:
C1) There exists an $x^{*}\in\mathbf{R}^{n}$ such that $F\left(x^{*}\right)=0$;
C2) $F$ is continuously Fréchet differentiable at $x^{*}$;
C3) $F^{\prime}\left(x^{*}\right)$ is nonsingular.

As in the case of inexact Newton methods, when the forcing sequence $\left(\eta_{k}\right)$ is uniformly less than one, an attraction theorem can b. stated, i.e. for any sufficiently good initially guesses $x_{0}$ and $x_{1}$, the sequence ( $x_{k}$ ) converges to $x^{*}$.

Lemma 2.1 If the conditions C1)-C3) hold, then for any $\gamma>0$ there exists $\varepsilon>0$ such that if $x,y\in B\left(x^{*},\varepsilon\right)=\left\{z\in\mathbf{R}^{n}\mid\left\|z-x^{*}\right\|\leq\varepsilon\right\}$ then $[x,y;F]$ is nonsingular and

1. 1.

   $\left|\left|[x,y;F]-F^{\prime}\left(x^{*}\right)\right|\right|\leq\gamma$;

   Report issue for preceding element
2. 2.

   $\left\|[x,y;F]^{-1}-F^{\prime}\left(x^{*}\right)^{-1}\right\|\leq\gamma$.

   Report issue for preceding element

Lemma 2.2 If $F$ is differentiable at $x^{*}$, then for any $\gamma>0$ there exists $\varepsilon>0$ such that

if $\left\|y-x^{*}\right\|\leq\varepsilon$.
The lemmas are immediate consequences of Definition 1.1, respectively of the definition of $F^{\prime}\left(x^{*}\right)$.

THEOREM 2.3 Suppose that $\eta_{k}\leq\bar{\eta}<q<1$ for all $k\in\mathbf{N}$ and write $\mu=\max\left\{\left\|F^{\prime}\left(x^{*}\right)\right\|,\left\|F^{\prime}\left(x^{*}\right)^{-1}\right\|\right\}$. Then there exists $\varepsilon\geq 0$ such that if $x_{0}x_{1}\in B\left(x^{*},\varepsilon\right)$ are chosen to satisfy $\left\|x_{1}-x^{*}\right\|\leq\frac{q}{\mu^{2}}\left\|x_{0}-x^{*}\right\|$ then the sequence $\left(x_{k}\right)$ given by (1.1) converges to $x^{*}$, and, moreover, the following inequalities hold:

where $\|y\|_{*}=\left\|F^{\prime}\left(x^{*}\right)y\right\|$.
Proof. From the definition of $\mu$ we get

Since $\bar{\eta}\leq q$, there exists $\gamma>0$ sufficiently small that

Now, by Lemmas 2.1 and 2.2, choose $\varepsilon\geq 0$ sufficiently small that

for $\left\|x-x^{*}\right\|\leq\mu^{2}\varepsilon$ and $\left\|y-x^{*}\right\|\leq\mu^{2}\varepsilon$.
We prove (2.1) by induction.
For $k=0$, by (2.2) we get

i.e. (2.1) hold.

Supposing now that it holds for $i=0,1,\ldots,k-1$, it follows that

so that (2.3)-(2.5) hold for $x=x_{k-1}$ and $y=x_{k}$.
By Lemma 2.1 we have now from (1.1) that $x_{k+1}$ exists. Moreover, since

taking norms, using (2.3)-(2.5) and the choice of $\gamma$ we obtain

which proves the linear convergence of $\left(x_{k}\right)$.

In this section the convergence order of inexact chord methods is characterized in terms of the rate of convergence of the relative residuals and of residuals.

DEFINITION 3.1 [3] Let $\left(x_{k}\right)$ be a sequence which converges to $x^{*}$. Then 1. the sequence $\left(x_{k}\right)$ converges to $x^{*}$ superlinearly if

1. 2.

   the sequence $\left(x_{k}\right)$ converges to $x^{*}$ with weak order at least $q(q>1)$ if

   Report issue for preceding element

LEMMA 3.2[3]Let $\alpha=\max\left\{\left\|F^{\prime}\left(x^{*}\right)\right\|+\frac{1}{2\beta},2\beta\right\}$, where $\beta=\left\|F^{\prime}\left(x^{*}\right)^{-1}\right\|$.
Then the following inequalities hold:

for $\left\|y-x^{*}\right\|$ sufficiently small.
THEOREM 3.3 Assume that the sequence $\left(x_{k}\right)$ given by (1.1) converges to $x^{*}$. Then $x_{k}\rightarrow x^{*}$ superlinearly if and only if

Proof. Assume that $x_{k}\rightarrow x^{*}$ superlinearly. Since

taking norms,

by Lemmas 2.1, 2.2 and 3.2.
Conversely, assume that $\left\|r_{k}\right\|=o\left(\left\|F\left(x_{k}\right)\right\|\right)$. As in the proof of theorem 2.3,

again by Lemmas 2.1, 2.2 and 3.2.

Definition 3.4 [4] Given the distinct points $x,y,z\in\mathbf{R}^{n}$, the second order divided difference of $F$ on $x,y$ and $z$ is a linear operator $[x,y,z;F]\in\mathscr{L}\left(\mathbf{R}^{n},\mathscr{P}\left(\mathbf{R}^{n}\right)\right)$ such that

1. 1.

   $[x,y,z;F](z-x)=[y,z;F]-[x,y;F]$ and

   Report issue for preceding element
2. 2.

   if $F$ is twice differentiable at $u\in\mathbf{R}^{n}$ then

   Report issue for preceding element

$\square$

Lemma 3.5 If there exist $\varepsilon>0$ and $K\geq 0$ such that for all $x,y\in B\left(x^{*},\varepsilon\right)$ we have
then

Proof. By Definition 3.4 we have

$\square$

Remark 3.6 The condition imposed in the above Lemma holds, for example, when $F$ is twice continuously differentiable at $x^{*}$.

Definition 3.7 [6] The mapping $F^{\prime}$ is Hölder continuous with exponent $p(0<p\leq 1)$ at $x^{*}$ if there exists $L\geq 0$ such that

for $\left\|p-x^{*}\right\|$ sufficiently small. $\square$

Lemma 3.8 [6] If $F$ ’ is Hölder continuous with exponent $p$ at $x^{*}$, then there exists $L^{\prime}\geq 0$ such that

by (3.1),
THEOREM 3.9 Assume that the sequence $\left(x_{k}\right)$ given by (1.1) converges to $x^{*}$, $F^{\prime}$ is Hölder continuous with exponent $p_{0}$ at $x^{*}$, where $1+p_{0}=\frac{1+\sqrt{5}}{2}$.

If $x_{k}\rightarrow x^{*}$ with weak order at least $1+p_{0}$ then $r_{k}\rightarrow 0$ with weak order at least $1+p_{0}$.

If $r_{k}\rightarrow 0$ with weak order at least $1+p_{0},F$ satisfies the condition of Lemma 3.5 and there exists $k_{1}\in\mathbf{N}$ sufficiently large such that $\left\|x_{k_{1}}-x^{*}\right\|\leq c\gamma$ and $\left\|x_{k_{1}+1}-x^{*}\right\|\leq c\gamma^{1+p_{0}}$, with $c,\gamma$ given below by the weak convergence of $r_{k}$, then $x_{k}\rightarrow x^{*}$ with weak order at least $1+p_{0}$.

Proof. Let $L$ be the Hölder constant and let $\alpha$ and $L^{\prime}$ be the constants given in Lemma 3.2 and Lemma 3.8 respectively. Pick $\varepsilon>0$ sufficiently small that for all $x,y\in B\left(x^{*},\varepsilon\right)$, there exists $[x,y;F]^{-1}$ and

Such an $\varepsilon$ exists by Lemma 3.2, the continuity and the Hölder continuity of $F^{\prime}$ at $x^{*}$ and Lemma 3.8.

Asume that $x_{k}\rightarrow x^{*}$ with weak order at least $1+p_{0}$. Then there exist constants $0\leq\gamma<1$ and $k_{0}\geq 0$ such that

Now choose $k_{1}\geq k_{0}$ sufficiently large that

From the definition of $r_{k}$,

for $\left\|y-x^{*}\right\|$ sufficiently small.

so that

The result now follows immediately from the definition of weak order of convergence.

Conversely, assume that $\left\|r_{k}\right\|\rightarrow 0$ with weak order at least $1+p_{0}=\frac{1+\sqrt{5}}{2}$. Then there exist constants $0\leq\gamma<1$ and $k_{0}\geq 0$ such that

Suppose also that $\left\|\left[x^{*},x,y,F\right]\right\|\leq K$ for $x,y\in B\left(x^{*},\varepsilon\right)$.

Let

and

and admit that $k_{1}\geq k_{0}$ is sufficiently large that
and

From the definition of weak of convergence if suffices to prove that
The proof is by induction. When $k=k_{1}$ it follows from the assumption

on $k_{1}$ that

Received 7.03.1996

"T. Popoviciu" Institute of Numerical Analysis
P.O. Box 68 Cluj-Napoca 1 RO-3400

As in the proof of Theorem 2.3,

since $1+p_{0}$ satisfies $t^{2}=t+1$. We get
so that $x_{k}\rightarrow x^{*}$ with weak order of convergence $1+p_{0}$. $\square$

1. 1.

   M. Balázs, G. Goldner, Remarks Concerning the Divided Differences and Chord Method, (in Romanian), Rev. Numer. Anal. and Approx. Theory, 3, Fasc. 1 (1974),19-30.

   Report issue for preceding element
2. 2.

   J.E. Dennis, Jr., J.J. Moré, Quasi-Newton Methods, Motivation and Theory, SIAM Rev., 19 (1977), 46-89.

   Report issue for preceding element
3. 3.

   R.S. Dembo, S.C. Eisenstat, T. Steihaug, Inexact Newton Methods, SIAM J. Numer. Anal., 19 (2) (1982), 400-408.

   Report issue for preceding element
4. 4.

   G. Goldner, M. Balázs, On the Chord Method and on a Modification of It for Solving Nonlinear Operator Equations, (in Romanian), Stud. Cerc. Mat., 20 (7) (1968) 981-990.

   Report issue for preceding element
5. 5.

   I. Muntean, Functional Analysis, (in Romanian), "Babes-Bolyai" University, Cluj-Napoca,1993.

   Report issue for preceding element
6. 6.

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

   Report issue for preceding element