Improving the rate of convergence of some Newton-like methods for the solution of nonlinear equations containing a nondifferentiable term

8 years ago

Emil Cătinaş

(original), html, Numerical Analysis, paper

Abstract

Authors

Ioannis K. Argyros
(Cameron University, USA)

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

Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

Keywords

chord/secant method; semilocal convergence; r-convergence order.

Cite this paper as:

I. Argyros, E. Cătinaş, I. Păvăloiu, Improving the rate of convergence of some Newton-like methods for the solution of nonlinear equations containing a nondifferentiable term, Rev. Anal. Numér. Théor. Approx., 27 (1998) no. 2, pp. 191-202.

PDF

Scanned paper: on the journal website.

Latex-pdf version of the paper.

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

MR

ZBL

Google Scholar citations

[1] K. Argyros, On the solution of equations with nondifferentiable operators and the Ptak error estimates, BIT, 30 (1990), pp. 752-754.

[2] I. K. Argyros, On the solution of nonlinear equations with a nondifferentiable term, Rev. Anal. Numer. Theor. Approx., 22 (1993) 2, pp. 125-135.

[3] I. K. Argyros, On some iterative methods for solving nonlinear equations with a nondifferentiable term of order between 1.618… and 1.839. (submitted to this joumal).

[4] I. K. Arglros, and F. Szidarovszky, The Theory and Application of lteration Method, CRC Press, Inc., Boca Raton, Florida, 1993.

[5] E. Cătinaș, On some iterative methods for solving nonlinear equations, Rev. Anal. Numer. Theor. Approx., 23, I (1994), pp. 47-53.

[6] G. Goldner, and M. Balazs, Remarks on divided differences and method of chords, Rev. Anal. Numer. Theor. Approx., 3, I (1974), pp. 19-30.

[7] L. V. Kantorovich, The method of successive approximation for functional equations, Acta Math. 71 (1939), pp. 63-97.

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

[9] I. Păvăloiu, Sur une generalisation de la methode de Steffensen, Rev. Anal. Numer. Theor. Approx., 21, 1 (1992), pp. 59-65.

[10] I. Păvăloiu, A convergence theorem concerning the chord methods, Rev. Anal. Numer. Theor. Approx., 22, 1 (1993), pp. 83-85.

[11] F. A, Potra, On an iterative algorithm of order 1.839 . . . for solving nonlinear equations, Numer. Funct. Anal. Optimiz. 7, I (1984-1985), pp. 75-106.

[12] T. Yamamoto and X. Chen, Convergence domains of certain iterative methods for solving nonlinear equations, Numer. Funct. Anal. Optimiz. 10, 1 and 2 (1989), pp.37-48.

Paper (preprint) in HTML form

Improving the rate of convergence of some Newton-Like methods for the solution of nonlinear equations containing A nondifferentiable term

Ioannis K. Argyros, Emil Cătinaş, Ion Păvăloiu

$s u b s o l :$ AMS (MOS) Subject Classification: 65J15, 65G99, 47H15, 49D15.

1 Introduction

In this study we are concerned with the problem of approximating a locally unique solution $x^{\ast}$ of a nonlinear equation

F\left(x\right)+G\left(x\right)=0

(1)

where $F, G$ are defined on a closed convex subset $D$ of a Banach space $E_{1}$ with values in a Banach space $E_{2}.$ The operator $F$ is Fréchet-differentiable on $D$ whereas $G$ is only continuous there.

We use the Newton-Like method given by

x_{n+1}=x_{n}+A_{n}^{-1}\left(F\left(x_{n}\right)+G\left(x_{n}\right)\right)\ % \ \ \left(n\geq 0\right)

(2)

to generate a sequence $\{x_{n}\}\left(n\geq 0\right)$ converging to $x^{\ast}.$ Here $A_{n}$ is a linear operator approximating $F^{\prime}\left(x_{n}\right)\left(n\geq 0\right).$ Sufficient conditions for the convergence of (2) to $x^{\ast}$ have given by several authors ([1], [2], [3], [4], [5],[7], [8], [11] and [12]). Recently, Cătinaş in [5] has used (2) for

A_{n}=F^{\prime}\left(x_{n}\right)+\left[x_{n-1},x_{n};G\right]\ \ \left(n\geq 1% \right),

(3)

where $\left[x,y;G\right]$ denotes a divided difference of order one of $G$ on $D$ for $x,y\in E_{1}.$ This way Cătinaş has managed to show that the order of convergence denoted by $\lambda\$ lies in $\left[\frac{1+\sqrt{5}}{2},2\right].$ Cătinaş has also showed that iteration (2) is faster than iterations appearing in [1],[2], [4], [5], [7], [8],[11] and [12] for choices of $A_{n}$ other than the one given by (3).

In [3] we used (2) for

A_{n}=\left[x_{n},x_{n-1};F\right]+\left[x_{n-2},x_{n};F\right]-\left[x_{n-2},% x_{n-1};F\right]+\left[x_{n-1},x_{n};G\right]\ \ \left(n\geq 0\right).

(4)

We showed that $\lambda\in\left[\frac{1+\sqrt{5}}{2},1.839...\right].$ Sufficient conditions were also provided under which our error bounds are sharper than all previous ones (in particular those in [5]). We also note that our method is cheaper to use than that in [5].

In this study we have made a further attempt to improve the rate of convergence of iteration (2) by choosing $A_{n}$ appropriately. Sufficient convergence conditions as well as an error analysis have been provided.

Finally we show that our error bounds are smaller than all earlier ones ([1], [2], [3], [4], [5], [7], [8], [9], [10], [11] and[12]).

2 Convergence analysis

We need the following definitons on divided differences [4], [9], [10].

Definition 1

An operator denoted by $\left[x_{0},y_{0};H\right]$ belonging to the space $L\left(D,E_{2}\right),D\subseteq E_{1}$ (the Banach space of bounded linear operators from $E_{1}$ to $E_{2}$ is called the first order divided difference of the operator $H:D\rightarrow E_{2}$ at the points $x_{0},y_{0}\in D$ if the following hold:

(a)

\left[x_{0},y_{0};H\right]\left(y_{0}-x_{0}\right)=H\left(y_{0}\right)-H\left(% x_{0}\right),\ forx_{0}\neq y_{0}.

(5)

(b)

If $H$ is Fréchet-differentiable at $x_{0}\in D,$ then $\left[x_{0},x_{0};H\right]=H^{\prime}\left(x_{0}\right).$

Definition 2

An operator denoted by $\left[x_{0},y_{0},z_{0};H\right]$ belonging to the space $L\left(D,L\left(D,E_{2}\right)\right)$ is called the second order divided difference of the operator $H:D\subseteq E_{1}\rightarrow E_{2}$ at the points $x_{0},y_{0},z_{0}\in D$ if the following hold:

(a)

\left[x_{0},y_{0},z_{0};H\right]\left(z_{0}-x_{0}\right)=\left[y_{0},z_{0};H% \right]-\left[x_{0},y_{0};H\right].

(6)

(b)

If $H$ is twice Fréchet-differentiable at $x_{0}\in D,$ then

\left[x_{0},x_{0},x_{0};H\right]=\frac{1}{2}H^{\prime\prime}\left(x_{0}\right).

We can prove the following semilocal result concerning the convergence of iteration (2).

Theorem 3

Assume that there exist points $x_{0},x_{1}\in D$ and nonnegative real numbers $R$ , $\varepsilon$ and $m$ such that:

(a)

$U\left(x_{1},R\right)=\{x\in E_{1}|\ \left|\left|x-x_{1}\right|\right|\leq R\}% \subseteq D;$

(b)

the operators $F, G$ have divided differences of order one denoted by $\left[x,y;F\right]$ and $\left[x,y;G\right]$ respectively for all $x,y\in U\left(x_{1},R\right);$

(c)

the linear operators $A_{n}$ are invertible for all $n\geq 0$ and

\left|\left|A_{n}^{-1}B_{n}\right|\right|\leq p_{n}\left|\left|x_{n-1}-x_{n-2}% \right|\right|+q\left|\left|x_{n}-x_{n-1}\right|\right|=\varepsilon_{n}\ \left% (n\geq 1\right),

for some nonnegative sequences $\{p_{n}\},$ $\{q_{n}\}\ \left(n\geq 1\right)$ with

p_{n}+q_{n}\leq\varepsilon\ \left(n\geq 1\right),

where

B_{n}=\left[x_{n-1},x_{n};F\right]+\left[x_{n-1},x_{n};G\right]-A_{n-1}\ \left% (n\geq 1\right),

(d)

the points $x_{0},x_{1}$ satisfy $\left|\left|x_{1}-x_{0}\right|\right|\leq m;$

(e)

the following conditions hold:

\left|\left|x_{2}-x_{1}\right|\right|\leq\left|\left|x_{1}-x_{2}\right|\right|,

(7)

with $x_{2}$ given by (2) for $n=1,$

r=m\varepsilon<1,

(8)

R\geq\frac{m}{r}\sum_{k=1}^{\infty}r_{k},

(9)

r_{k}=r^{s_{k}},\left(k\geq 0\right),

(10)

where $\{s_{k}\}$ is the Fibonacci’s sequence

s_{0}=s_{1}=1,\ s_{k+1}=s_{k}+s_{k-1},\ \left(k\geq 0\right).

(11)

Then

(i)

the sequence $\{x_{n}\}\left(n\geq 0\right),$ generated by (2) is well defined, remains in $U\left(x_{0},R\right)$ and converges to a solution $x^{\ast}\in U\left(x_{0},R\right)$ of the equation $F\left(x\right)+G\left(x\right)=0;$

(ii)

the following a priori error estimated hold

\left|\left|x^{\ast}-x_{n}\right|\right|\leq\frac{mt_{n}}{r\left(1-t_{n}^{\ell% -1}\right)},\ \ \left(n\geq 1\right),

(12)

where

t_{n}=r^{\frac{\ell}{\sqrt{5}}},\left(n\geq 1\right)\ \ \text{and\ }\ell=\frac% {1+\sqrt{5}}{2};

(13)

(iii)

moreover, if there exists a nonnegative number $g$ such that

\left|\left|A_{n}^{-1}B_{n}^{\ast}\right|\right|\leq g<1,\ \ \left(n\geq 1% \right),

(14)

where

B_{n}^{\ast}=\left[y^{\ast},x_{n};F\right]+\left[y^{\ast},x_{n};G\right]-A_{n}% ,\ \ \left(n\geq 1\right),

(15)

with $y^{\ast}$ satisfying

F\left(y^{\ast}\right)+G\left(y^{\ast}\right)=0\ \ \text{and \ }y^{\ast}\in U\left(x_{0},R\right),

then

x^{\ast}=y^{\ast}.

Proof. We shall show by induction that, for all $n\geq 2$

x_{n}\in U\left(x_{1},R\right),

(16)

\left|\left|x_{n}-x_{n-1}\right|\right|\leq\left|\left|x_{n-1}-x_{n-2}\right|\right|

(17)

and

\left|\left|x_{n}-x_{n-1}\right|\right|\leq\frac{m}{r}r_{n-1}.

(18)

For $n=2$ relations (16)-(18) follow from hypothses (d) and (e). Suppose relations (16)-(18) hold for $n=2,3,...k,$ where $k\geq 2.$ Since $x_{k},x_{k-1}\in U\left(x_{1},R\right)$ and $A_{k}$ is invertible, via (2) we can compute $x_{k+1}.$ Using (2), we can obtain the approximation

$\displaystyle F\left(x_{k}\right)+G\left(x_{k}\right)$	$\displaystyle=F\left(x_{k}\right)+G\left(x_{k}\right)-F\left(x_{k-1}\right)-G% \left(x_{k-1}\right)-A_{k-1}\left(x_{k}-x_{k-1}\right)=$	(19)
	$\displaystyle=\left(\left[x_{k-1},x_{k};F\right]+\left[x_{k-1},x_{k};G\right]-% A_{k-1}\right)\left(x_{k}-x_{k-1}\right)=$
	$\displaystyle=B_{k}\left(x_{k}-x_{k-1}\right)\ \text{by (\ref{f.1.19}))}$

By (2), (7??), (8???) and (19) we get

\left|\left|x_{k+1}-x_{k}\right|\right|\leq\varepsilon_{k}\left|\left|x_{k}-x_% {k-1}\right|\right|\leq\varepsilon\left|\left|x_{k-1}-x_{k-2}\right|\right|% \cdot\left|\left|x_{k}-x_{k-1}\right|\right|.

(20)

From the induction hypothese, (20) give on the one hand, that

\left|\left|x_{n+1}-x_{k}\right|\right|\leq\frac{\varepsilon}{r}r_{k-2}m\left|% \left|x_{k}-x_{k-1}\right|\right|=r_{k-2}\left|\left|x_{k}-x_{k-1}\right|% \right|<\left|\left|x_{k}-x_{k-1}\right|\right|,

that is, (17) for $n=k+1,$ and, on the other hand

\left|\left|x_{k+1}-x_{k}\right|\right|\leq r_{k-2}\left|\left|x_{k}-x_{k-1}% \right|\right|\leq r_{k-2}r_{k-1}\frac{m}{r}=\frac{m}{r}r_{k},

which shows (18) for $n=k+1$ .

We must also show that $x_{k+1}\in U\left(x_{1},R\right).$ Indeed, from the induction hypotheses and the triangle inequality we get

\left|\left|x_{k+1}-x_{1}\right|\right|\leq\left|\left|x_{2}-x_{1}\right|% \right|+\left|\left|x_{3}-x_{2}\right|\right|+...+\left|\left|x_{k+1}-x_{k}% \right|\right|\leq\frac{m}{r}\sum_{j=1}^{k}r_{k}<R.

We must show that sequence $\{x_{n}\}\left(n\geq 0\right)$ is Cauchy. We have that the Fibonacci’s sequence $\{s_{k}\}\left(k\geq 0\right)$ given by (11) can also be written as

s_{k}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-\left(% \frac{1-\sqrt{5}}{2}\right)\right]\geq\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}% }{2}\right)\kappa=\frac{\ell_{k}}{\sqrt{5}}\left(k\geq 1\right).

Therefore, for any $k\geq 1,\ j\geq 1$ we get

	$\displaystyle\left\|\left\|x_{k+j}-x_{k}\right\|\right\|$	$\displaystyle\leq\left\|\left\|x_{k+1}-x_{k}\right\|\right\|+\left\|\left\|x_{k+2}-x% _{k+1}\right\|\right\|+...+\left\|\left\|x_{k+j}-x_{k+j-1}\right\|\right\|\leq$
		$\displaystyle\leq\frac{m}{r}\sum_{j=k}^{k+j-1}r_{i}\leq\frac{m}{r}\sum_{i=k}^{% k+j-1}r^{\frac{\ell^{l}}{\sqrt{5}}}.$

Moreover, by Bernoulli’s inequality we get

$\displaystyle\left\|\left\|x_{k+j}-x_{k}\right\|\right\|$	$\displaystyle\leq\frac{m}{r}r^{\frac{\ell^{k}}{5}}\left[1+r^{\frac{\ell^{k+1}-% \ell^{k}}{\sqrt{5}}}+r^{\frac{\ell^{k+2-\ell}}{5}}+...+r^{\frac{\ell^{k+j-1}-% \ell^{k}}{\sqrt{5}}}\right]\leq$	(21)
	$\displaystyle\leq\frac{m}{r}r^{\frac{\ell_{k}}{\sqrt{5}}}\left[1+r^{\frac{\ell% ^{l}\left(\ell-1\right)}{\sqrt{5}}}+r^{\frac{\ell_{k}\left[1+2\left(\ell-1% \right)-1\right]}{\sqrt{5}}}+...+r^{\frac{\left[1+\left(j-1\right)\left(\ell-1% \right)-1\right]}{\sqrt{5}}}\right]$
	$\displaystyle=\frac{m}{r}r^{\frac{\ell^{k}}{\sqrt{5}}}\frac{1-r^{\frac{v^{k}% \ell-1}{\sqrt{5}}j}}{1-r^{\frac{\ell^{l}\left(\ell-1\right)}{\sqrt{5}}}}\left(% k\geq 1\right).$

By (8)and (21) it follows that the sequence $\{x_{n}\}\left(n\geq 0\right)$ is Caucchy in a Banch space $E_{1},$ and so it converges to some point $x^{\ast}\in U\left(x_{1},R\right)$ (since $U\left(x_{1},R\right)$ is a closed set). By letting $n\rightarrow\infty$ in (2), we obtain $F\left(x^{\ast}\right)+G\left(x^{\ast}\right)=0;$ that is, $x^{\ast}\in U\left(x_{1},R\right)$ is a solution of equation (1). Moreover, by letting $j\rightarrow\infty$ in (21) we obtain (12).

Furhermore, to show that $x^{\ast}$ is the unique solution of equation (1) in $U\left(x_{1},R\right),$ let us assume that $y^{\ast}\in U\left(x_{1},R\right)$ is a solution of equation (1) too.

$\displaystyle x_{k+1}-y^{\ast}$	$\displaystyle=x_{k}-y^{\ast}-X_{k}^{-1}\left(F\left(x_{k}\right)+G\left(x_{k}% \right)\right)=$	(22)
	$\displaystyle=-A_{k}^{-1}\left[F\left(x_{k}\right)-F\left(y^{\ast}\right)+G% \left(x_{k}\right)-Gy^{\ast}-A_{k}\left(x_{k}-y^{\ast}\right)\right]=$
	$\displaystyle=-A_{k}^{-1}B_{k}^{\ast}\left(x_{k}-y^{\ast}\right),$

and hypothesis (14), we get

	$\displaystyle\left\|\left\|x_{k+1}-y^{\ast}\right\|\right\|$	$\displaystyle\leq\left\|\left\|A_{k}^{-1}B_{k}^{\ast}\right\|\right\|\ \left\|\left% \|x_{k}-y^{\ast}\right\|\right\|\leq$		(23)
		$\displaystyle\leq g\left\|\left\|x_{k}-y^{\ast}\right\|\right\|\leq...\leq g^{k}% \left\|\left\|x_{1}-y^{\ast}\right\|\right\|\leq g^{k}R.$

Since $0\leq g<1,$ by letting $k\rightarrow\infty$ in (23) we get $\lim\limits_{k\rightarrow\infty}x_{k}=y^{\ast}.$ But we have also showed that $\lim\limits_{k\rightarrow\infty}x_{k}=x^{\ast}.$ Hence, we deduce $x^{\ast}=y^{\ast}.$

That completes the proof of the Theorem.

Remark 4

Let us consider some special choices for the linear operators $A_{n}.$ Set

A_{n}=\left[x_{n},y_{n};F\right]+\left[h_{n},z_{n};F\right]-\left[h_{n},z_{n-1% };F\right]+\left[v_{n},x_{n};G\right]\ \left(n\geq 0\right),

(24)

where the sequences $\{y_{n}\},$ $\{z_{n}\},$ $\{v_{n}\},$ $\{h_{n}\}\in U\left(x_{1},R\right)\left(n\geq 0\right)$ are given by

	$\displaystyle y_{n}$	$\displaystyle=x_{n}+\alpha_{n}\left(x_{n-1}-x_{n}\right),\ z_{n}=z_{n-1}\beta_% {n}\left(x_{n-1}-x_{n}\right),\ \ z_{-1}=x_{-1}\in U\left(x_{1},R\right),$
	$\displaystyle v_{n}$	$\displaystyle=x_{n}+y_{n}\left(x_{n-1}-x_{n}\right)\left(n\geq 0\right),$

for some linear operator sequence $\{\alpha_{n}\},$ $\{\beta_{n}\}$ and $\{\gamma_{n}\}\left(n\geq 0\right)$ with $\gamma_{n}\neq 0$ $\left(n\geq 0\right).$ Assume that there exist nonnegative numbers $a, b, c$ and a real sequence $\{a_{n}\}$ $\left(n\geq 0\right)$ such that for all $x,y,v,w,z\in U\left(x_{1},R\right)$

\left|\left|A_{0}^{-1}\left(\left[x,y;F\right]-\left[v,w;F\right]\right)\right% |\right|\leq v\left(\left|\left|x-v\right|\right|+\left|\left|y-w\right|\right% |\right)

(25)

\left|\left|A_{n}^{-1}A_{0}\right|\right|\leq a_{n}\leq a\ \left(n\geq 0\right),

(26)

and

\left|\left|A_{n}^{-1}\left[x,y,z;G\right]\right|\right|\leq c,

(27)

where $\left[x,y,z;G\right]$ is the divided difference of order two of $G$ on $U\left(x_{1},R\right).$ Then form the approximation

	$\displaystyle G\left(x_{n}\right)-G\left(x_{n-1}\right)-\left[v_{n-1},x_{n-1};% G\right]\left(x_{n}-x_{n-1}\right)=$
	$\displaystyle=\left(\left[x_{n-1};G\right]-\left[v_{n-1},x_{n-1};G\right]% \right)\left(x_{n}-x_{n-1}\right)=$
	$\displaystyle=\left[v_{n-1},x_{n-1},x_{n};G\right]\left(x_{n}v_{n-1}\right)% \left(x_{n}-x_{n-1}\right),$

hypotheses (25), (26) and (27) we get

	$\displaystyle\left\|\left\|A_{0}^{-1}\left(G\left(x_{n}\right)-G\left(x_{n-1}% \right)-\left[v_{n-1},x_{n-1};G\right]\left(x_{n}-x_{n-1}\right)\right)\right\|% \right\|\leq$
	$\displaystyle\leq c\left\|\left\|x_{n}-v_{n-1}\right\|\right\|\ \left\|\left\|x_{n}-% x_{n-1}\right\|\right\|\leq$
	$\displaystyle\leq c\left(\left\|\left\|x_{n}-v_{n-1}\right\|\right\|+\left\|\left\|% \gamma_{n}\right\|\right\|\ \left\|\left\|x_{n-1}-x_{n-2}\right\|\right\|\right)% \left\|\left\|x_{n}-x_{n-1}\right\|\right\|\left(n\geq 0\right).$

The sequence $\{a_{n}\}\left(n\geq 1\right)$ can be computed as follows. Let us assume that there exist $\overline{c}\geq 0$ such that

\left|\left|A_{0}^{-1}\left(\left[x,y;G\right]-\left[v_{0},x_{0};G\right]% \right)\right|\right|\leq\overline{c}\left(\left|\left|x-v_{0}\right|\right|+% \left|\left|y-x_{0}\right|\right|\right),

(28)

for all $x,y,v_{0},x_{0}\in U\left(x_{1},R\right).$ Then from the approximation

	$\displaystyle A_{0}^{-1}\left(A_{n}-A_{0}\right)=A_{0}^{-1}\{\left[x_{n},y_{n}% ;F\right]+\left[h_{n},z_{n};G\right]-\left[h_{n},z_{n-1};G\right]+$
	$\displaystyle+\left[v_{n},x_{n};G\right]-\left[x_{0},y_{0};F\right]-\left[h_{0% },z_{0};F\right]+\left[h_{0},z_{-1};F\right]-\left[v_{0},x_{0};G\right]\},$

we can get as before

\left|\left|A_{0}^{-1}\left(A_{n}-A_{0}\right)\right|\right|\leq\overline{a}_{% n}\left(n\geq 1\right),

where

	$\displaystyle\overline{a}_{n}$	$\displaystyle=b\left(\left\|\left\|x_{n}-x_{0}\right\|\right\|+\left\|\left\|y_{n}-y% _{0}\right\|\right\|+2\left\|\left\|h_{n}-h_{0}\right\|\right\|+\left\|\left\|z_{n}-z_% {0}\right\|\right\|+\left\|\left\|z_{n-1}-z_{-1}\right\|\right\|\right)+$
		$\displaystyle+\overline{c}\left(\left\|\left\|v_{n}-x_{0}\right\|\right\|+\left\|% \left\|x_{n}-x_{0}\right\|\right\|\right)\ \left(n\geq 1\right),$

and $\overline{a}_{n}<1$ if the function $a\left(r\right)=\left(11b+2\overline{c}\right)r+\left(b+2\overline{c}\right)m$ satisfies

a\left(R\right)<1,

(29)

since

\overline{a}_{n}\leq a\left(R\right)\ \ \left(n\geq 1\right).

It follows from the Banach lemma on invertible operators that $A_{n}^{-1}$ exists $\left(n\geq 1\right)$ and

\left|\left|A_{n}^{-1}A_{0}\right|\right|\leq\left(1-\overline{a}_{n}\right)^{% -1}.

We can now set $a_{n}=\left(1-\overline{a}_{n}\right)\left(n\geq 1\right)$ and $a=\left(1-\left(R\right)\right)^{-1}.$ Moreover, from the approximation

	$\displaystyle F\left(x_{n}\right)-F\left(x_{n-1}\right)-$
	$\displaystyle-\left(\left[x_{n-1},y_{n-1};F\right]+\left[h_{n-1},z_{n-1};F% \right]-\left[h_{n-1},z_{n-1};F\right]\right)\left(x_{n}-x_{n-1}\right)$
	$\displaystyle=\left(\left[x_{n-1},x_{n};F]-[x_{n-1},y_{n-1};F\right]-\left[x_{% n-1},z_{n-1};F\right]\right)+\left[x_{n-1},z_{n-2};F\right])\left(x_{n}-x_{n-1% }\right),$

hypothese (25), (26), and (27) and (28) we also get

	$\displaystyle\|\|A_{0}^{-1}\{F\left(x_{n}\right)-F\left(x_{n-1}\right)-$		(30)
	$\displaystyle-(\left[x_{n-1},y_{n-1}:F\right]+\left[h_{n-1},z_{n-1};F\right]-% \left[h_{n-1},z_{n-2};F\right])\left(x_{n}-x_{n-1}\right)\}\|\|$
	$\displaystyle\leq b\left(\left\|\left\|x_{n}-y_{n-1}\right\|\right\|+\left\|\left\|z% _{n-1}-z_{n-2}\right\|\right\|\right)\left\|\left\|x_{n}-x_{n-1}\right\|\right\|\leq$
	$\displaystyle\leq b\left(\left\|\left\|x_{n}-x_{n-1}\right\|\right\|+\left\|\left\|% \alpha_{n-1}+\beta_{n-1}\right\|\right\|\ \left\|\left\|x_{n-2}-x_{n-1}\right\|% \right\|\right)\left\|\left\|x_{n}-x_{n-1}\right\|\right\|\left(n\geq 1\right).$

Define the sequences $\{d_{n}\},$ $\{\delta_{n}\}$ $\left(n\geq 1\right)$ by

d_{n}=\left(b+c\right)a_{n}\ \ \text{and \ }\delta_{n}=a_{n}(c\left|\left|% \gamma_{n}\right|\right|+b\left(\left|\left|\alpha_{n}\right|\right|+\left|% \left|\beta_{n}\right|\right|\right)]\ \ \left(n\geq 0\right).

(31)

\left|\left|x_{n+1}-x_{n}\right|\right|\leq\left(d_{n}\left|\left|x_{n}-x_{n-1% }\right|\right|+\delta_{n}\left|\left|x_{n-1}-x_{n-2}\right|\right|\right)% \left|\left|x_{n}-x_{n-1}\right|\right|\left(n\geq 1\right).

(32)

Hence we can set

p_{n}=\delta_{n}\ \ \ \ \text{and \ \ }d_{n}=q_{n}\ \ \left(n\geq 0\right).

(33)

We can impose additional conditions on the sequences $\{\alpha_{n}\},$ $\{\beta_{n}\}$ and $\{\gamma_{n}\}$ $\left(n\geq 0\right)that$ will guarantee that $\{y_{n}\},$ $\{z_{n}\},$ $\{v_{n}\}\in U\left(x_{1},R\right).$ Let us assume that there exist nonnegative numbers $\alpha,$ $\beta,$ and $\gamma$ such that

\left|\left|\alpha_{n}\right|\right|\leq a,\ \left|\left|\beta_{n}\right|% \right|\leq\beta\ \ \text{and \ }\left|\left|\gamma_{n}\right|\right|\leq\gamma\ \left(n\geq 0\right).\

Then, from the approximations

	$\displaystyle y_{n}-x_{1}$	$\displaystyle=\left(x_{n}-x_{1}\right)+\alpha_{n}\left(x_{n-1}-x_{n}\right)$
	$\displaystyle v_{n}-x_{1}$	$\displaystyle=\left(x_{n}-x_{1}\right)+\gamma_{n}\left(x_{n-1}-x_{n}\right)$
	$\displaystyle z_{n}-x_{1}$	$\displaystyle=\left(x_{n-1}-x_{1}\right)+\beta_{n}\left(x_{n-1}-x_{n}\right),$

we can have

\left|\left|x_{n}-x_{1}\right|\right|+\left|\left|\alpha_{n}\right|\right|\ % \left|\left|x_{n-1}-x_{n}\right|\right|\leq\frac{m}{r}\sum_{i=1}^{n-1}r_{i}+% \frac{m\alpha}{r}r_{n-1},

(34)

\left|\left|v_{n}-x_{1}\right|\right|+\left|\left|\gamma_{n}\right|\right|\ % \left|\left|x_{n-1}-x_{n}\right|\right|\leq\frac{m}{r}\sum_{i=1}^{n-1}r_{i}+% \frac{m\gamma}{r}r_{n-1},

(35)

and

\left|\left|z_{n}-x_{1}\right|\right|\leq\left|\left|z_{-1}-x_{1}\right|\right% |+\beta\sum_{i=0}^{n-1}\left|\left|x_{i}-x_{i-1}\right|\right|\leq\left|\left|% z_{-1}-x_{1}\right|\right|+\frac{\beta m}{r}\sum_{i=0}^{n-1}r_{i}.

(36)

Hence $y_{n},v_{n},z_{n}\in U\left(x_{1},R\right)\left(n\geq 0\right)$ if the right hand sider of the last three inequalities are respectively bounded above by $R$ .

Finally, the uniqueness of the solution $x^{\ast}$ can be extended in the ball $U\left(x_{1},R_{1}\right)$ for $R_{1}\geq R$ provided that the following inequality holds

g=\left(5\left(b+\overline{c}\right)R+\left(b+c\right)R_{1}+2m\overline{c}% \right)\left(1-a\left(R\right)\right)^{-1}<1.

(37)

Indeed, as in (22) we get

	$\displaystyle B_{n}^{\ast}$	$\displaystyle=\left(\left[y^{\ast},x_{n};F\right]-\left[x_{n},y_{n};F\right]% \right)+\left(\left[y^{\ast},x_{n};G\right]-\left[x_{0},v_{0};G\right]\right)+$
		$\displaystyle+\left(\left[x_{0},v_{0};G\right]-\left[v_{n},x_{n};G\right]% \right)+\left(\left[h_{n},z_{n-1};F\right]-\left[h_{n},z_{n};F\right]\right).$

Composing both sides of the above approximation by $A_{0}^{-1},$ we easily deduce that $A_{0}^{-1}B_{k}^{\ast}$ (in norm) is bounded above by the expression in the bracket of inequality (37). Hence, as in the proff of the Theorem, we deduce $x^{\ast}=y^{\ast}.$

Concluding, we note that we have showed: if hypotheses (c) of the Theorem are replaced by (24), (25), (26), (27), (28) and (37), then the conclusions of the Theorem hold in the ball $U\left(x_{1},R_{1}\right).$

Remark 5

Iteration (2) reduces to (4) considered in [5] if the linear operators $\{A_{n}\}\left(n\geq 0\right)$ are given by (24) for $\alpha_{n}=0,$ $\gamma_{n}=I,$ $\beta_{n}=0,$ $z_{n}=0$ $\left(n\geq 0\right).$

Using the notation introduced in [5], we can set

\varepsilon_{n}^{1}=MK\left|\left|x_{n-1}-x_{n-2}\right|\right|+M\left(\frac{% \ell}{2}+K\right)\left|\left|x_{n}-x_{n-1}\right|\right|\left(n\geq 2\right).

(38)

Hence our error bounds (12) will be smaller than those in [5] , say if (see also (33)).

p_{n}\leq MK\ \ \ \text{and\ \ }q_{n}\leq\left(M\frac{\ell}{2}+K\right)\left(n% \geq 2\right)

(39)

and our initial error bounds $\left|\left|x_{1}-x_{0}\right|\right|$ are not greater than those in [5]. The choice of $p_{n},q_{n}$ given by (33) shows that conditions (39) will be true if $a_{n},\alpha_{n},\beta_{n}$ and $\gamma_{n}\left(n\geq 0\right)$ are ”small” enough.

Remark 6

Moreover, iteration (2) reduces to (1) considered in [11] if the linear operators $\{A_{n}\}\left(n\geq 0\right)$ are given by (24) for $G=0,$ $\alpha_{n}=I,$ $\beta_{n}=I,$ $z_{n}=x_{n}$ and $h_{n}=x_{n-2}\left(n\geq 0\right).$ Using the notation introduced in [11] we can set

\varepsilon_{n}^{2}=q_{0}\left|\left|x_{n-3}-x_{n-1}\right|\right|\ \left|% \left|x_{n-2}-x_{n-1}\right|\right|+p_{0}\left|\left|x_{n}-x_{n-1}\right|% \right|\ \left(n\geq 1\right).

(40)

Hence our error bounds (12) will be smaller in this case, say if

p_{n}\leq\left|\left|x_{n-3}-x_{n-1}\right|\right|\ \text{and }q_{n}\leq p_{0}% \ \ \left(n\geq 1\right).

(41)

Observations similar to those made at the end of Remark 2 can now follows.

Remark 7

Furthermore, iteration (2) reduces to (5) considered in [3] if the linear operators $\{A_{n}\}\ \left(n\geq 0\right)$ are given by (24) for

\alpha_{n}=I,\ \beta_{n}=0,\ \gamma_{n}=I,\ z_{n}=x_{n},\ h_{n}=x_{n-2}\ \left% (n\geq 0\right).

Using the notation introduced in [3], we can set

\varepsilon_{n}^{3}=\left(c_{4}+c_{2}\left|\left|x_{n-3}-x_{n-1}\right|\right|% \right)\left|\left|x_{n-1}-x_{n-2}\right|\right|+\left(x_{1}+c_{4}\right)\left% |\left|x_{n}-x_{n-1}\right|\right|\ \left(n\geq 1\right).

(42)

Hence our bounds will be smaller in this case say if

p_{n}\leq c_{4}+c_{2}\left|\left|x_{n-3}-x_{n-1}\right|\right|\ \text{and\ }q_% {n}\leq c_{1}+c_{4}\ \ \left(n\geq 1\right).

(43)

Remark 8

Our results extend to included perturbed Newton-like methods of the form

x_{n+1}=x_{n}-A_{n}^{-1}\left(F\left(x_{n}\right)+G\left(x_{n}\right)\right)-w% _{n}\ \ \left(n\geq 0\right).

(44)

The points $\{w_{n}\}\left(n\geq 0\right)$ are determined in such a way that interation $\{x_{n}\}$ $\left(n\geq 0\right)$ converges to a solution $x^{\ast}$ of equation (1). The import;ance of studying perturbed Newton-like methods comes from the fact that many commonly used variants of Newton’s method can be considered procedures of this type. Indeed, approximation (44) characterizes any iterative process in which corrections are taken as approximate solutions of Newton equations. We also note that if, for example, an equation on the real is solved, $F\left(x_{n}\right)>0\left(n\geq 0\right),$ and $A\left(x_{n}\right)\left(n\geq 0\right)$ overestimates the derivative $x_{n}-A_{n}^{-1}F\left(x_{n}\right),$ is always larger than the corresponding Newton iterate. In such cases, a positive $w_{n}\left(n\geq 0\right)$ correction term is appropriate. Let us assume that there exists a real sequence $\{u\}\left(n\geq 0\right)$ such that

\left|\left|A_{n}\left(w_{n}\right)-A_{n}\left(w_{n-1}\right)\right|\right|% \leq u_{n}\ \ \left(n\geq 1\right).

(45)

Moreover, there exist real sequences $\{\ell_{n}\},$ $\{m_{n}\}$ $\left(n\geq 0\right)$ such that

u_{n}\leq\left(\ell_{n}\left|\left|x_{n-1}-x_{n-2}\right|\right|+m_{n}\left|% \left|x_{n}-x_{n-1}\right|\right|\right)\left|\left|x_{n}-x_{n-1}\right|\right% |\ \ \left(n\geq 1\right).

(46)

Set

\overline{p}_{n}=p_{n}+\ell_{n}\ \ \text{and\ \ }\overline{q}_{n}=q_{n}+m_{n}% \ \ \ \left(n\geq 1\right).

Furthermore, assume that sequence $\{w_{n}\}\ \left(n\geq 0\right)$ is null. Finally, assume that the rest of the hypotheses of the Theorem are true with $\overline{p}_{n},\overline{q}_{n}$ replacing $p_{n},$ $q_{n}$ $\left(n\geq 1\right),$ respectively. Then it can easily be seen that the conclusions of the Theorem will hold for the perturbed Newton-Like method generated by (44). Indeed, for example, approximation (19) will read

F\left(x_{k}\right)+G\left(x\right)+A_{k}\left(w_{k}\right)=\left[B_{k}+\left(% A_{k}\left(w_{k}\right)-A_{k-1}\left(w_{k-1}\right)\right)\right]\left(x_{k}-x% _{k-1}\right)\ \ \left(n\geq 1\right)

and by using the proof of the theorem, (45) and (46) we can arrive at (20). The rest is left to the motivated reader.

Remark 9

The selection of the points $\{y_{n}\},$ $\{z_{n}\},$ $\{v_{n}\}$ $\left(n\geq 0\right)$ can be generalized to include a wider range of problems. Let $T_{1},$ $T_{2},$ $T_{3}:D\subseteq E_{1}\rightarrow E_{2}$ begiven operators. Define for all $n\geq 0$ $y_{n}=T_{1}\left(x_{n}\right),$ $z_{n}-z_{n-1}=T_{2}\left(x_{n}\right),$ $z_{-1}=x_{-1}\in U\left(x_{1},R\right)\subseteq D$ and $v_{n}=T_{3}\left(x_{n}\right).$ For this choice of $T_{1},\ T_{2}\$ and $T_{3}$ iteration (2)becomes a Steffensen-like method ([8], [9] and [10]). Moreover, operators $T_{1},$ $T_{2}$ and $T_{3}$ must be chosen so that estimte (7??) be true. See how this is done, for example, in Remark 1.

References

[1] I. K. Argyros, On the solution of equations with nondifferentiable operators and the Ptak error estimates, BIT, 30 (1990), 752-754.
[2] I. K. Argyros, On the solution of nonlinear equations with a nodifferentiable term, Rev. Anal. Numér. Théorie Approximation 22, 2(1993), 125-135.
[3] I. K. Argyros, On some iterative methods for solving nonlinear equations with a nondifferentiable term of order between 1.618…and 1.839…(sumitted to this journal).
[4] I. K. Argyros, and F. Szidarovszky, The Theory and Application of Iteration Methods, C.R.C., Press, Inc., Boca Raton, Florida, 1993.
[5] E. Cătinaş, On some iterative method for solving nonlinear equations, Rev. Anal. Numér. Theorie Approximation 23, 1 (1994), 47-53.
[6] G. Goldner, and M. Balazs, Remarks on divided differences and method of chords, Rev. Anal. Numér Theorie Approximation 3, 1 (1974), 19-30.
[7] L. V. Kantorovich, The method of succesive approximation for functional equations, Acta. Math. 71 (1939), 63-97.
[8] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.
[9] I. Păvăloiu, Sur une généralisation de la méthod de Steffensen, Rev. Anal. Numér. Theorie Approximation 21, 1 (1972), 59-65.
[10] I. Păvăloiu, A convergence theorem concerning the chord methods, Rev. Anal. Numér. Theorie Approximation 22, 1 (1993), 83-85.
[11] F. A. Potra, On an iterative algorithm of order 1.839…for solving nonlinear equations, Numer. Funct. Anal. Optimiz. 7, 1 (1984-1985), 75-106.
[12] T. Yamamoto and X. Chen, Convergence domains of certain iterative methods for solving nonlinear equations, Numer. Funct. Anal. Optimix. 10, 1 and 2 (1989), 37-48.

Received August 10, 1996 Ioannis K. Argyros

Cameron University

Department of Mathematics

Lawton, OK 73505, U.S.A.

Emil Cătinaş and Ion Păvăloiu

Institutul de Calcul ”Tiberiu Popoviciu”

Str. Republicii Nr.37

C.P. 68, 3400 Cluj-Napoca, Romania

1998

Numerical modeling of the cavities during the alloys solidification

November 28, 2018

Methods of nonlinear analysis with applications in celestial mechanics

July 4, 2020

Transport processes in porous media. 1. Continuous modeling

August 21, 2018

	$\displaystyle\left\|\left\|x_{k+1}-y^{\ast}\right\|\right\|$	$\displaystyle\leq\left\|\left\|A_{k}^{-1}B_{k}^{\ast}\right\|\right\|\ \left\|\left% \|x_{k}-y^{\ast}\right\|\right\|\leq$		(23)
		$\displaystyle\leq g\left\|\left\|x_{k}-y^{\ast}\right\|\right\|\leq...\leq g^{k}% \left\|\left\|x_{1}-y^{\ast}\right\|\right\|\leq g^{k}R.$

	$\displaystyle\|\|A_{0}^{-1}\{F\left(x_{n}\right)-F\left(x_{n-1}\right)-$		(30)
	$\displaystyle-(\left[x_{n-1},y_{n-1}:F\right]+\left[h_{n-1},z_{n-1};F\right]-% \left[h_{n-1},z_{n-2};F\right])\left(x_{n}-x_{n-1}\right)\}\|\|$
	$\displaystyle\leq b\left(\left\|\left\|x_{n}-y_{n-1}\right\|\right\|+\left\|\left\|z% _{n-1}-z_{n-2}\right\|\right\|\right)\left\|\left\|x_{n}-x_{n-1}\right\|\right\|\leq$
	$\displaystyle\leq b\left(\left\|\left\|x_{n}-x_{n-1}\right\|\right\|+\left\|\left\|% \alpha_{n-1}+\beta_{n-1}\right\|\right\|\ \left\|\left\|x_{n-2}-x_{n-1}\right\|% \right\|\right)\left\|\left\|x_{n}-x_{n-1}\right\|\right\|\left(n\geq 1\right).$

Improving the rate of convergence of some Newton-like methods for the solution of nonlinear equations containing a nondifferentiable term

Abstract

Authors

Keywords

Cite this paper as:

PDF

About this paper

Journal

Publisher Name

Paper on the journal website

Print ISSN

Online ISSN

MR

ZBL

Google Scholar citations

References

Paper (preprint) in HTML form

Improving the rate of convergence of some Newton-Like methods for the solution of nonlinear equations containing A nondifferentiable term

1 Introduction

2 Convergence analysis

Definition 1

Definition 2

Theorem 3

Remark 4

Remark 5

Remark 6

Remark 7

Remark 8

Remark 9

References

Related Posts