A convergency theorem concerning
the chord method

Ion Păvăloiu
(Cluj-Napoca)

Let $X$ be a Banach space, and let $f:X\rightarrow X$ be a mapping to solve the equation:

(1)

f\left(x\right)=0,

the chord method is well known, consisting of approximating the solution of (1) by elements of the sequence $\left(x_{n}\right)_{n\geq 0}$ generated by the following relations:

(2)

x_{n+1}=x_{n}-\left[x_{n-1},x_{n};f\right]^{-1}f\left(x_{n}\right),\;\;\ n=1,2% ,\ldots,x_{0},x_{1}\in X,

where $\left[x,y;f\right]\in\mathcal{L}\left(X\right)$ stands for the divided difference of $f$ on $x,y\in X.$ It is clear that to generate the elements of the sequence $\left(x_{n}\right)_{n\geq 0}$ by means of (2) we must ensure ourselves that at every iteration step the linear mapping $\left[x_{n-1},x_{n};f\right]$ is invertible. The mathematical literature dealing with the convergency of the chord method contains results which state by hypothesis that the mapping $\left[x,y;f\right]$ admits a bounded inverse for every $x,y\in D,$ where $D$ is a subset of $X .$

In this note we intend to establish convergency conditions for the method (2), supposing the existence of the inverse mapping only for the divided difference $\left[x_{0},x_{1};f\right].$

Let $r>0$ be a real number, and write $S\left(x_{0},r\right)=\{x\in X:\left\|x-x_{0}\right\|\leq r\}.$

Theorem.

If the mapping $f:X\rightarrow X,$ the real number $r>0$ and the element $x_{1}\in X$ fulfil the conditions:

(i)

the mapping $\left[x_{0},x_{1};f\right]$ admits a bounded inverse mapping, and $\|\left[x_{0},x_{1};f\right]^{-1}\|\leq B<+\infty;$
(ii)

the bilinear mapping $\left[x,y,z;f\right]$ (the second order divided difference of $f$ on $x, y, z$ ) is bounded for every $x,y,z\in S\left(x_{0},r\right),$ that is, $\left\|\left[x,y,z;f\right]\right\|\leq L<\infty;$
(iii)

$3BLr<1;$
(iv)

$\rho_{0}=\alpha\left\|f\left(x_{0}\right)\right\|<1,$ $\rho_{1}=\alpha\left\|f\left(x_{1}\right)\right\|\leq\rho_{0}^{t_{1}},$ where
$\alpha=LB^{2}/\left(1-3BLr\right)^{2}$ and $t_{1}=(1+\sqrt{5})/2;$
(v)

$B\rho_{0}/\big{[}\alpha\big{(}1-\rho_{0}^{t_{1}-1}\big{)}\left(1-3BLr\right)% \big{]}\leq r,$

then the following properties hold:
(j)

$x_{n}\in S\left(x_{0},r\right)$ for every $n=0,1,\ldots;$
(jj)

the mapping $\left[x_{i-1},x_{i};f\right]$ admits bounded inverse for every $i=1,2,\ldots;$
(jjj)

equation (1) has at least one solution $x^{\ast}\in S\left(x_{0},r\right);$
(jv)

the sequence $\left(x_{n}\right)_{n\geq 0}$ is convergent, and $\lim x_{n}=x^{\ast};$
(v)

$\left\|x^{\ast}-x_{n}\right\|\leq\frac{B\rho_{0}^{t_{1}^{n}}}{\big{[}\alpha(1-% 3BLr)\big{(}1-\rho_{0}^{t_{1}^{n}\left(t_{1}-1\right)}\big{)}\big{]}}.$

Proof.

We shall firstly show that for every $x,y\in S\left(x_{0},r\right)$ the following inequality holds:

(3)

\big{\|}\left[x_{0},x_{1};f\right]^{-1}\left(\left[x_{0},x_{1};f\right]-\left[% x,y;f\right]\right)\big{\|}\leq 3BLr<1.

Taking into account hypothesis (ii) and the definition of the second order divided difference [2], it results:

	$\displaystyle\left\\|\left[x_{0},x_{1};f\right]-\left[x,y,f\right]\right\\|$	$\displaystyle\leq\left\\|\left[x_{0},x_{1};f\right]-\left[x_{1},x;f\right]% \right\\|+\left\\|\left[x_{1},x;f\right]-\left[x,y;f\right]\right\\|$
		$\displaystyle\leq L\left\\|x-x_{0}\right\\|+L\left\\|y-x_{1}\right\\|<3Lr.$

From the above inequality and hypothesis (i) there follows (3).

Using Banach’s lemma on inverse mapping continuousness, it results from (3) that there exists $\left[x,y;f\right]^{-1},$ and:

\big{\|}\left[x,y;f\right]^{-1}\big{\|}\leq B/\left(1-3BLr\right).

Suppose now that the following properties hold:

(a)

$x_{i}\in S,$ $i=\overline{0,k};$
(b)

$\rho_{i}=\alpha\left\|f\left(x_{i}\right)\right\|\leq\rho_{0}^{t_{1}^{i}},i=% \overline{0,k};$

and prove that they hold for $i=k+1,$ too.

Indeed, to prove that $x_{n+1}\in S$ we estimate the difference:

	$\displaystyle\left\\|x_{k+1}-x_{0}\right\\|$	$\displaystyle\leq\sum_{i=0}^{k}\left\\|x_{i+1}-x_{i}\right\\|\leq\tfrac{B\alpha^% {-1}}{1-3BLr}\sum_{i=0}^{k}\alpha\left\\|f\left(x_{i}\right)\right\\|$
		$\displaystyle\leq B\rho_{0}\big{[}\alpha\big{(}1-\rho_{0}^{t_{1}-1}\big{)}% \left(1-3BLr\right)\big{]}^{-1}\leq r$

To prove (b) for $i=k+1$ we use Newton’s identity:

(4)

f\left(z\right)=f\left(x\right)+\left[x,y;f\right]\left(z-x\right)+\left[x,y,z% ;f\right]\left(z-x\right)(z-y)

and the obvious identity:

(5)

x-\left[x,y;f\right]^{-1}f\left(x\right)=y-\left[x,y;f\right]^{-1}f\left(y% \right).

Applying (4) and taking into account (2) and (5), we deduce:

	$\displaystyle\left\\|f\left(x_{k+1}\right)\right\\|$	$\displaystyle=\left\\|f\left(x_{k+1}\right)-f\left(x_{k}\right)-\left[x_{k-1},x% _{k};f\right]\left(x_{k+1}-x_{k}\right)\right\\|$
		$\displaystyle\leq\left\\|\left[x_{k-1},x_{k},x_{k+1};f\right]\right\\|\cdot\left% \\|x_{k+1}-x_{k}\right\\|\cdot\left\\|x_{k+1}-x_{k-1}\right\\|$
		$\displaystyle\leq LB^{2}\left\\|f\left(x_{k}\right)\right\\|\cdot\left\\|f\left(x% _{k-1}\right)\right\\|\cdot\left(1-3BLr\right)^{-2}$
		$\displaystyle\leq LB^{2}\left(1-3BLr\right)^{-2}\cdot\alpha^{-2}\rho_{k}\rho_{% k-1},$

and writing $\rho_{k+1}=\alpha\left\|f\left(x_{k+1}\right)\right\|$ we obtain:

\rho_{k+1}\leq\rho_{k}\rho_{k-1}<\rho_{0}^{t_{1}^{k}+t_{1}^{k-1}}=\rho_{0}^{t_% {1}^{k+1}}

that is, the property (b) holds for $i=k+1,$ too.

From (2) one obtains the following inequalities:

\left\|x_{n+1}-x_{n}\right\|\leq B\alpha^{-1}\left(1-3BLr\right)^{-1}\rho_{n}% \leq\tfrac{B\rho_{0}^{t_{1}^{n}}}{\alpha\left(1-3BLr\right)}

for every $n=0,1,\ldots$

From these relations, for every $m,n\in\mathbb{N}$ we deduce:

(6)		$\displaystyle\left\\|x_{n+m}-x_{n}\right\\|$	$\displaystyle\leq\sum_{i=n}^{m+n-1}\tfrac{B\rho_{0}^{t_{1}^{n}}}{\alpha\left(1% -3BLr\right)}$
		$\displaystyle\leq B\rho_{0}^{t_{1}^{n}}\alpha^{-1}(1-3BLr)^{-1}\Big{(}1-\rho_{% 0}^{t_{1}^{n\left(t_{1}-1\right)}}\Big{)}^{-1}$

from which, taking into account the fact that $t_{1}>1,$ there follows that the sequence $\left(x_{n}\right)_{n\geq 0}$ is fundamental.

At limit $\left(m\rightarrow\infty\right),$ (6) leads to

\left\|x^{\ast}-x_{n}\right\|<B\rho_{0}^{t_{1}^{n}}\alpha^{-1}\left(1-3BLr% \right)^{-1}\left(1-\rho_{0}^{t_{1}^{n}\left(t_{1}-1\right)}\right)^{-1}

where $x^{\ast}=\lim\limits_{n\rightarrow\infty}x_{n}.$ For $n=0$ follows that $x^{\ast}\in S\left(x_{0},r\right).$

It is obvious that $f\left(x^{\ast}\right)=0.$ ∎

Remark.

In the conditions of the above proved theorem, it results form (3) that $x^{\ast}$ is the unique solution of equation (1) in the sphere $S\left(x_{0},r\right).$

Indeed, supposing that $x^{\ast}$ and $y^{\ast}$ are two solutions of equation (1) in $S\left(x_{0,}r\right),x^{\ast}\neq y^{\ast},$ and using the identities:

	$\displaystyle x^{\ast}$	$\displaystyle=x^{\ast}-\left[x_{0},x_{1};f\right]^{-1}f\left(x^{\ast}\right)$
	$\displaystyle y^{\ast}$	$\displaystyle=y^{\ast}-\left[x_{0},x_{1};f\right]^{-1}f\left(y^{\ast}\right)$

we deduce

x^{\ast}-y^{\ast}=\big{(}I-\left[x_{0},x_{1};f\right]^{-1}\left[x^{\ast},y^{% \ast};f\right]\big{)}\left(x^{\ast}-y^{\ast}\right)

from which, taking into account (3) it follows that:

\left\|x^{\ast}-y^{\ast}\right\|\leq 3BLr\left\|x^{\ast}-y^{\ast}\right\|

but, since $3BLr<1,$ it results that the relation $x^{\ast}\neq y^{\ast}$ is impossible. ∎

References

[1] Argyros, K.I., The Secant Method and Point of Nonlinear Operators Mh. Math. 106 (1988), 85–94.
[2] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Introduction in the theory of approximation of equations solutions, Dacia Ed., Cluj-Napoca 1976, (in Romanian).
[3] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Remarks on the secant method for the solution of nonlinear operational equations, Research Seminars. Seminar on Mathematical analysis, Preprint 7, 127–132 (1991).

Received 1.III.1992 Institutul de Calcul

Academia Română, Filiala Cluj-Napoca

C.P.68, Cluj-Napoca

Romania

	$\displaystyle\left\\|f\left(x_{k+1}\right)\right\\|$	$\displaystyle=\left\\|f\left(x_{k+1}\right)-f\left(x_{k}\right)-\left[x_{k-1},x% _{k};f\right]\left(x_{k+1}-x_{k}\right)\right\\|$
		$\displaystyle\leq\left\\|\left[x_{k-1},x_{k},x_{k+1};f\right]\right\\|\cdot\left% \\|x_{k+1}-x_{k}\right\\|\cdot\left\\|x_{k+1}-x_{k-1}\right\\|$
		$\displaystyle\leq LB^{2}\left\\|f\left(x_{k}\right)\right\\|\cdot\left\\|f\left(x% _{k-1}\right)\right\\|\cdot\left(1-3BLr\right)^{-2}$
		$\displaystyle\leq LB^{2}\left(1-3BLr\right)^{-2}\cdot\alpha^{-2}\rho_{k}\rho_{% k-1},$

A convergency theorem concerning the chord method

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Article on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

A convergency theorem concerning
the chord method

Theorem.

Proof.

Remark.

References

Related Posts