Posts by Ion Păvăloiu

Abstract

We present some new conditions which assure that the Aitken-Steffensen method yields bilateral approximation for the solution of a nonlinear scalar equation. The auxiliary functions appearing in the method are constructed under the hypothesis that the nonlinear application is not differentiable on an interval containing the solution.

Author

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

Keywords

nonlinear equations in R; Aitken-Steffensen method; monotone iterations; bilateral approximations.

PDF

PDF-LaTeX file (on the journal website).

Cite this paper as:

I. Păvăloiu, Aitken-Steffensen-type methods for nonsmooth functions (II), Rev. Anal. Numér. Théor. Approx., 31 (2002) no. 2, pp. 191-196. https://doi.org/10.33993/jnaat312-724

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

References

[1] Balazs, M., A bilateral approximating method for finding the real roots of real equations , Rev. Anal. Num ́er. Th ́eor. Approx., 21, no. 2, pp. 111–117, 1992.

[2] Casulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25–44, 1977.

[3] Cobzas ̧, S., Mathematical Analysis, Presa Universitar a Clujean a, Cluj-Napoca, 1997 (in Romanian).

[4] Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, 1960.

[5] Pavaloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensens’s method, Mathematica (Cluj), 35 (58), no. 1, pp. 71–76, 1993.

[6] Pavaloiu, I., Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numer. Theor. Approx., 23 , no. 1, pp. 95–100, 1994.

[7] Pavaloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, no. 1–2, pp. 69–82, 1995.

[8] Pavaloiu, I., Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal.Numer. Theor. Approx., 31, no. 1, pp. 111–116, 2002.

[9] Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.

Paper (preprint) in HTML form

Aitken-Steffensen-type methods for nonsmooth functions (II)∗

Aitken-Steffensen-type methods
for nonsmooth functions (II)^∗

Ion Păvăloiu^†

(Date: January 16, 2002.)

Abstract.

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

^†“T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68–1, 3400 Cluj-Napoca, Romania (pavaloiu@ictp.acad.ro).

{amssubject}

65H05.

{keyword}

Aitken-Steffensen iterations.

1. Introduction

In this note we continue the study of the convergence of the Aitken-Steffensen-type iterations

(1)

x_{n+1}=g_{1}\left(x_{n}\right)-\frac{f\left(g_{1}\left(x_{n}\right)\right)}{% \left[g_{1}\left(x_{n}\right),g_{2}\left(x_{n}\right);f\right]},\quad n=0,1,% \ldots,\quad x_{0}\in I

for solving

(2)

f\left(x\right)=0,

where $f:\left[a,b\right]\rightarrow\mathbb{R},\;a,b\in\mathbb{R},\;a<b.$

The functions $g_{1}$ and $g_{2}$ in (2) are chosen such that equations

(3)

\displaystyle x-g_{i}\left(x\right)

\displaystyle=0,\quad i=1,2,

to be equivalent to equation (1).

Under supplementary assumptions we shall show, as in [7], that (2) generates three monotone sequences, converging to the solution $\bar{x}$ of (1).

Regarding the monotonicity and convexity of $f$ we shall consider the notions introduced in [3]. We shall also use Theorem 1 and Lemma 2 from [8].

For defining the functions $g_{1}$ and $g_{2}$ , we shall consider $\alpha,\beta\in\mathbb{R}$ such that $a<\alpha<\beta<b$ and $f\left(\alpha\right)<0,\;f\left(\beta\right)>0,$ defining then:

(4)

\displaystyle g_{1}\left(x\right)

\displaystyle=x-\tfrac{f\left(x\right)}{\left[\beta,b;f\right]},\quad x\in% \left[\alpha,\beta\right],

(5)

\displaystyle g_{2}\left(x\right)

\displaystyle=x-\tfrac{f\left(x\right)}{\left[a,\alpha;f\right]},\quad x\in% \left[\alpha,\beta\right].

Regarding $f$ we shall make the following assumptions.

i.

$f\left(\alpha\right)\cdot f\left(\beta\right)<0;$
ii.

$f$ is increasing on $\left[a,b\right];$
iii.

$f$ is convex on $\left[a,b\right]$ and continuous at $a$ and $b$ ;
iv.

if $\bar{x}\in\left(a,b\right)$ is the solution of (1), then $f$ is differentiable at $\bar{x}$ .

Remarks.

1^∘ Hypothesiis iii. ensures the continuity of $f$ on $\left[a,b\right]$ , and therefore the existence of $\bar{x}$ . Hypothesis ii. ensures the uniqueness of $\bar{x}$ .

2^∘ From hypotheses ii, iii and [8, Lm. 1.1], it follows that for any $u,v\in\left(\alpha,\beta\right)$ one obtains

(6)

\left[u,v;g_{1}\right]>0\quad\text{and\quad}\left[u,v;g_{2}\right]<0,

i.e., $g_{1}$ is increasing and $g_{2}$ is decreasing on $\left(\alpha,\beta\right)$ . ∎

Let $x_{0}\in\left(\alpha,\beta\right)$ be such that

a)

$f\left(x_{0}\right)<0$
b)

$g_{2}\left(x_{0}\right)<\beta.$

2. The convergence of the Aitken-Steffensen-type iterations

We shall study in the following the convergence of the sequences $\left(x_{n}\right)_{n\geq 0}$ $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ to the solution $\bar{x}$ . We obtain the following result.

Theorem 1.

If the function $f$ verifies assumptions i–iv., the functions $g_{1}$ and $g_{2}$ are given by (4) and (5), and $x_{0}\in\left(\alpha,\beta\right)$ verifies a) and b), then the sequences $\left(x_{n}\right)_{n\geq 0},\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ and $\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ , generated by (2) satisfy:

j.

$\left(x_{n}\right)_{n\geq 0}$ is increasing;
jj.

$\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ is increasing;
jjj.

$\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ is decreasing;
jv.

for all $n\in\mathbb{N},\;$ one has

(7) $x_{n}<g_{1}\left(x_{n}\right)<x_{n+1}<\bar{x}<g_{2}\left(x_{n}\right).$

Proof.

By $\left[\beta,b;f\right]>0$ and $f\left(x_{0}\right)<0$ it follows $g_{1}\left(x_{0}\right)>x_{0}$ , while by $x_{0}<\bar{x}$ and the fact that $g_{1}$ is increasing it follows $g_{1}\left(x_{0}\right)<g_{1}\left(\bar{x}\right)=\bar{x}$ , i.e. $g_{1}\left(x_{0}\right)<\bar{x}$ .

Now, since $x_{0}<\bar{x}$ , $g_{2}$ is decreasing one gets $g_{2}\left(x_{0}\right)>g_{2}\left(\bar{x}\right)=\bar{x}$ , i.e. the following relations hold:

(8)

x_{0}<g_{1}\left(x_{0}\right)<\bar{x}<g_{2}\left(x_{0}\right).

Let $x_{1}=g_{1}\left(x_{0}\right)-\frac{f\left(g_{1}\left(x_{0}\right)\right)}{% \left[g_{1}\left(x_{0}\right),g_{2}\left(x_{0}\right);f\right]},$ since $f\left(g_{1}\left(x_{0}\right)\right)<0$ implies $g_{1}\left(x_{0}\right)<x_{1}$ .

From the identity

	$\displaystyle f\left(x_{1}\right)=$	$\displaystyle f\left(g_{1}\left(x_{0}\right)\right)+\left[g_{1}\left(x_{0}% \right),g_{2}\left(x_{0}\right);f\right]\left(x_{1}-g_{1}\left(x_{0}\right)% \right)+$
		$\displaystyle+\left[x_{1},g_{1}\left(x_{0}\right),g_{2}\left(x_{0}\right);f% \right]\left(x_{1}-g_{1}\left(x_{0}\right)\right)\left(x_{1}-g_{2}\left(x_{0}% \right)\right)$

taking into account the convexity of $f$ and relation (1), we get $f\left(x_{1}\right)<0$ , i.e. $x_{1}<\bar{x}.$

By the above relations and by (8) it follows

x_{0}<g_{1}\left(x_{0}\right)<x_{1}<\bar{x}<g_{2}\left(x_{0}\right),

which shows that (7) is verified for $n=0.$

Repeating this reason, the induction shows that (7) holds for $n\in\mathbb{N}$ . This attracts in turn that the sequences $\left(x_{n}\right)_{n\geq 0}$ and $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ are increasing, i.e., statements j and jj.

We show next that $\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ is decreasing. Indeed, by $x_{n}<x_{n+1}$ for $n\in\mathbb{N}$ we get $g_{2}\left(x_{n}\right)>g_{2}\left(x_{n+1}\right)$ since $g_{2}$ is decreasing. Inequalities $x_{n}<\bar{x}$ , $n\in\mathbb{N}$ , show that $g_{2}\left(x_{n}\right)>g_{2}\left(\bar{x}\right)=\bar{x}$ .

Let us notice that the sequences $\left(x_{n}\right)_{n\geq 0}$ , $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ , $\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ are monotone and bounded, so they converge. Let $l_{1}=\lim x_{n}$ , $l_{2}=\lim g_{1}\left(x_{n}\right)$ and $l_{3}=\lim g_{2}\left(x_{n}\right)$ . We show that $l_{1}=l_{2}=l_{3}=\bar{x}.$

We prove first that $l_{1}=l_{2}$ . Assume the contrary, $l_{1}\neq l_{2}$ , e.g. $l_{1}<l_{2}$ . Obviously, $l_{1}=\sup_{n\in\mathbb{N}}\left\{x_{n}\right\}$ and $l_{2}=\sup_{n\in\mathbb{N}}\left\{g_{1}\left(x_{n}\right)\right\}.$ Let $0<\varepsilon<l_{2}-l_{1}$ be a positive number. Then there exists $n_{\varepsilon}\in\mathbb{N}$ such that $g_{1}\left(x_{n}\right)>l_{2}-\varepsilon$ for $n>n_{\varepsilon}$ .

This implies that

x_{n+1}>g_{1}\left(x_{n}\right)>l_{2}-\varepsilon>l_{1}

so $l_{1}$ is not the exact upper bound of the elements of the sequence $\left(x_{n}\right)_{n\geq 0}$ . Hence, clearly, $l_{1}=l_{2}=l$ ,

l=\lim x_{n}=\lim g_{1}\left(x_{n}\right)=g_{1}\left(l\right),

i.e., $l=\bar{x}$ . Since $\lim x_{n}=\bar{x}$ , it follows that

\lim g_{2}\left(x_{n}\right)=g_{2}\left(\bar{x}\right)=\bar{x},

since $\bar{x}$ is the unique solution of equation $x-g_{2}\left(x\right)=0.$ ∎

The above relations show that we have a control of the error at each iteration step, justified by

\bar{x}-x_{n+1}<g_{2}\left(x_{n}\right)-x_{n+1},\quad\ {\rm or}\ \ \bar{x}-x_{% n+1}<g_{2}\left(x_{n}\right)-g_{1}\left(x_{n}\right),\quad n=0,1,\ldots

The identity

	$\displaystyle 0=f\left(\bar{x}\right)=$	$\displaystyle f\left(g_{1}\left(x_{n}\right)\right)+\left[g_{1}\left(x_{n}% \right),g_{2}\left(x_{n}\right);f\right]\left(\bar{x}-g_{1}\left(x_{n}\right)% \right)+$
		$\displaystyle+\left[\bar{x},g_{1}\left(x_{n}\right),g_{2}\left(x_{n}\right);f% \right]\left(\bar{x}-g_{1}\left(x_{n}\right)\right)\left(\bar{x}-g_{2}\left(x_% {n}\right)\right)$

relation (7), and the hypotheses of the above theorem lead to

(9)

\bar{x}-x_{n+1}=-\frac{\left[\bar{x},g_{1}\left(x_{n}\right),g_{2}\left(x_{n}% \right);f\right]}{\left[g_{1}\left(x_{n}\right),g_{2}\left(x_{n}\right);f% \right]}\left(\bar{x}-g_{1}\left(x_{n}\right)\right)\left(\bar{x}-g_{2}\left(x% _{n}\right)\right).

Further, by Lemma 2 from [8] we get

(10)

\displaystyle\bar{x}-g_{1}\left(x_{n}\right)=\left[x_{n},\bar{x};g_{1}\right]% \left(\bar{x}-x_{n}\right)

(11)

\displaystyle\bar{x}-g_{2}\left(x_{n}\right)=\left[x_{n},\bar{x},g_{2}\right]% \left(\bar{x}-x_{n}\right)

and, taking into account (4) and (5),

\left[x_{n},\bar{x};g_{1}\right]=1-\tfrac{\left[x_{n},\bar{x};f\right]}{\left[% \beta,b;f\right]}<1-\tfrac{\left[a,\alpha;f\right]}{\left[\beta,b;f\right]}=1-% q<1.

Analogously,

\left[\bar{x},x_{n};g_{2}\right]=1-\tfrac{\left[\bar{x},x_{n};f\right]}{\left[% a,\alpha;f\right]}>1-\tfrac{\left[\beta,b;f\right]}{\left[a,\alpha,;\right]}=% \tfrac{\left[\beta,b;f\right]}{\left[a,\beta;f\right]}\Big(\tfrac{\left[a,% \alpha;f\right]}{[\beta,b;f]}-1\Big)=\tfrac{1}{q}(q-1)

where we have denoted $\left[a,\alpha;f\right]/\left[\beta,b;f\right]=q>0$ and by Lemma 2 from [8] $q<1.$ This relation, together with the decreasing of $g_{2}$ lead to $-\left[\bar{x},x_{n};g_{2}\right]<\tfrac{1}{q}\left(1-q\right),$ i.e., $\big|[\bar{x},x_{n};g_{2}]\big|<\tfrac{1}{q}\left(1-q\right).$

Denoting $M=\max_{u,v\in\left[\alpha.\beta\right]}\big|\left[\bar{x},u,v;f\right]\big|$ and $m=\left[a,\alpha;f\right]$ , by (9) we get

\left|\bar{x}-x_{n+1}\right|<\tfrac{M\left(1-q\right)^{2}}{mq}\left|\bar{x}-x_% {n}\right|^{2},\;n=1,2,\ldots

which characterizes the convergence order of the studied methods.

References

[1] Balázs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théor. Approx., 21, no. 2, pp. 111–117, 1992.
[2] Casulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25–44, 1977.
[3] Cobzaş, S., Mathematical Analysis, Presa Universitară Clujeană, Cluj-Napoca, 1997 (in Romanian).
[4] Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, 1960.
[5] Păvăloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensens’s method, Mathematica (Cluj), 35 (58), no. 1, pp. 71–76, 1993.
[6] Păvăloiu, I., Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 23, no. 1, pp. 95–100, 1994.
[7] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, no. 1–2, pp. 69–82, 1995.
[8] Păvăloiu, I., Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal. Numér. Théor. Approx., 31, no. 1, pp. 111–116, 2002.
[9] Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.

Posts by Ion Păvăloiu

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

Aitken-Steffensen-type methods
for nonsmooth functions (II)^∗

Abstract.

1. Introduction

Remarks.

2. The convergence of the Aitken-Steffensen-type iterations

Theorem 1.

Proof.

References

Related Posts

Aitken-Steffensen-type methods for nonsmooth functions (II)

Aitken-Steffensen-type methods for nondifferentiable functions (I)

On a Halley-Steffensen method for approximating the solutions of scalar equations

Optimal efficiency index of a class of Hermite iterative methods with two steps

On the Heron’s method for approximating the cubic root of a real number

Observations concerning some approximation methods for the solutions of operator equations

Bilateral approximations for the solutions of scalar equations

A convergency theorem concerning the chord method

Error estimation in numerical solution of equations and systems of equations

Optimal problems concerning interpolation methods of solution of equations