Bilateral approximations for the Solutions
of Scalar Equations

Ion Păvăloiu
(Cluj-Napoca)

1. Introduction

Let $I=\left[a,b\right],\ a<b,$ be an interval on the real axis. Consider the equation:

(1)

f\left(x\right)=0,

with $f:I=\mathbb{R}$ .

In paper [1], to solve equation (1), the author has considered the sequences $\left(x_{n}\right)$ and $\left(g\left(x_{n}\right)\right),\ n=0,1,\ldots,$ generated by means of Steffensen’s method for the case when $f$ is of the form:

(2)

f\left(x\right)=x-g\left(x\right),

where $g:I\rightarrow\mathbb{R}$ , and he has studied the conditions under which the two above sequences are monotonous (one increasing, the other decreasing), both converging to the solution $\bar{x}$ of equation (1).

In paper [2] the same problem has been studied, considering Steffensen’s method for a more general case, that is, when $f$ and $g$ do not satisfy equality (2), but it is supposed that equation (1) is equivalent to the equation:

(3)

x-g\left(x\right)=0

Paper [2] points out the advantages of Steffensen’s method in the mentioned case ( $f$ and $g$ fulfill the above condition, hence (2) does not hold).

As known, Steffensen’s method, studied in [1] and [2]), consists in generating the sequences $\left(x_{n}\right)$ and $\left(g\left(x_{n}\right)\right),\ n=0,1,\ldots,$ through:

(4)

x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n},g\left(x_{n}\right);f% \right]},\ x_{0}\in I.

where $\left[x_{n},g\left(x_{n}\right);f\right]$ stands for the first order divided differences of $f$ on the points $x_{n}$ and $g\left(x_{n}\right)$ , [3].

In the present note we shall study the problem of [1] and [2] for the Aitken-Steffensen method. For this purpose, consider the following three equations:

(5)

\left\{\begin{array}[c]{c}f\left(x\right)=0;\\ x-g_{1}\left(x\right)=0;\\ x-g_{2}\left(x\right)=0,\end{array}\right.

where $g_{1},g_{2}:I\rightarrow\mathbb{R}$ .

Assuming that equations (5) are equivalent, in order to approximate the root $\bar{x}$ of equation (1) we shall consider the sequences $\left(x_{n}\right),\ g_{1}\left(x_{n}\right)),$ and $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right),\ n=0,1,\ldots,$ generated by the Aitken-Steffensen method, namely:

(6)

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(g_{1}\left(x_{n}\right)\right);f% \right]},\ x_{0}\in I

It is well known that the convergence order of Steffensen’s method for sequence (4) is 2 if the functions $f$ and $g$ verify equality (2).

In the case of the more general studied in [2], the convergence order is $p+1$ if the sequence $\left(y_{n}\right),\ n=0,1,\ldots,$ generated by $y_{n+1}=g\left(y_{n}\right),\ y_{0}\in I$ , has the convergence order $p\left(p\in\mathbb{R}\right),$ $p\geq 1).$

The convergence order of the method (6) is $p\left(q+1\right)$ if the sequence $\left(y_{n}\right)$ and $\left(z_{n}\right),\ n=0,1,\ldots,$ generated by $y_{n+1}=g_{1}\left(y_{n}\right),\ z_{n+1}=g_{2}\left(y_{n}\right),y_{0},z_{0}\in I$ , have the convergence orders $p$ and $q$ , respectively.

From this viewpoint the results of [2] and those of this paper can present certain advantages; more concretely, given the function $f$ , the functions $g$ and $g_{1},g_{2},$ respectively, may be chosen in infinitely various ways. These will be classified at the end of this note.

We shall adopt the notation $\left[x,y;f\right]$ and $\left[x,y,z;f\right],$ with $x,y,z\in I$ , for the first and second order divided differences of the function $f$ , respectively. We shall also use in proofs the following obvious identities:

(7)

\displaystyle g_{1}\left(x\right)-\frac{f\left(g_{1}\left(x\right)\right)}{% \left[g_{1}\left(x\right),g_{2}\left(g_{1}\left(x\right)\right);f\right]}=g_{2% }\left(g_{1}\left(x\right)\right)-\frac{f\left(g_{2}\left(g_{1}\left(x\right)% \right)\right)}{\left[g_{1}\left(x\right),g_{2}\left(g_{1}\left(x\right)\right% );f\right]}

(8)

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)\left(z-y\right)

where $x,y,z\in I$ . As to the notions of monotonicity and convexity of the function $f$ on the interval $I$ , we shall adopt the following definitions:

Definition 1.1.

The function $f:I\rightarrow\mathbb{R}$ is increasing (nondecreasing,decreasing, nonincreasing) on $I$ if for every $x,y\in I$ the relation $\left[x,y;f\right]>0$ ( $\geq 0,\ <0,\leq 0,$ respectively) holds.

Definition 1.2.

The function $f:I\rightarrow\mathbb{R}$ is convex (nonconcave, concave, nonconvex) on $I$ if for every $x,y,z\in I$ the relation $\left[x,y,z;f\right]>0$ ( $\geq 0,<0,\leq 0$ , respectively) holds.

2. Monotonicity of the sequences Generated by the Aitken-Steffensen Method

In the sequel we shall suppose that the function $f,g_{1},g_{2}$ fulfill the following conditions:

(a)

the functions $f,g_{1},g_{2}$ are continuous;
(b)

the function $g_{1}$ is increasing on $I;$
(c)

the equation $x-g_{1}\left(x\right)=0$ has only one root $\bar{x}\in I$ ;
(d)

the function $g_{2}$ is decreasing on $I$ ;
(e)

the equations (5) are equivalent on $I$ .

As to the problem stated in Section 1, some theorems are verified, as follows:

Theorem 2.1.

If the functions $f,g_{1},g_{2}$ fulfil the conditions (a)–(e) and, in addition,

(i₁).

$f$ is increasing and convex on $I;$
(ii₁).

there exists $x_{0}\in I$ for which $f\left(x_{0}\right)<0,\ x_{0}-g_{1}\left(x_{0}\right)<0$ and $g_{2}\left(g_{1}\left(x_{0}\right)\right)\in I$ ,

then the sequences $\left(x_{n}\right),\left(g_{1}\left(x_{n}\right)\right)$ and $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right),\ n=0,1,\mathbb{\ldots},$ have the properties:

(j₁).

the sequence $\left(x_{n}\right)$ and $\left(g_{1}\left(x_{n}\right)\right)$ are increasing and convergent;
(jj₁).

the sequence $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right)$ is decreasing and convergent;
(jjj₁).

limx ${}_{n}=\lim g_{1}\left(x_{n}\right)=\lim g_{2}\left(g_{1}\left(x_{n}\right)% \right)=\bar{x}$ , where $\bar{x}$ is the root of equation (1).

Proof.

Since equations (5) are equivalent, and $\bar{x}$ is the unique root for equation $x-g_{1}\left(x\right)=0,$ it results that $\bar{x}$ is the common unique root of equations (5).

Since $f$ is increasing and $f\left(x_{0}\right)<0$ , it follows that $x_{0}<\bar{x}$ . Observe now that from the fact that $\bar{x}$ is the unique root of $x-g_{1}\left(x\right)=0,g_{1}$ is increasing, and $x_{0}-g_{1}\left(x_{0}\right)<0,$ it results that $x-g_{1}\left(x\right)<0$ for every $x<\bar{x}$ . As $x_{0}<\bar{x}$ , it results that $g_{1}\left(x_{0}\right)<g_{1}\left(\bar{x}\right)=\bar{x}$ , that is, $g_{1}\left(x_{0}\right)<\bar{x}$ . The function $g_{2}$ is decreasing, hence $\ g_{2}\left(g_{1}\left(x_{0}\right)\right)>g_{2}\left(\bar{x}\right)=\bar{x}$ , namely $g_{2}g_{1}\left(x_{0}\right)>\bar{x}.$ Since $g_{1}\left(x_{0}\right)<\bar{x}$ , it follows that $f\left(g_{1}\left(x_{0}\right)\right)<0$ inequality which, together with $\left[g_{1}\left(x_{0}\right),g_{2}\left(g_{1}\left(x_{0}\right)\right);f% \right]>0$ , and taking into account (6) for $n=0$ , leads to the inequality $x_{1}>g_{1}\left(x_{0}\right)$ . From identity (7) for $x=x_{0}$ and from the fact that $f\left(g_{2}\left(g_{1}\left(x_{0}\right)\right)\right)>0$ it results that $g_{2}\left(g_{1}\left(x_{0}\right)\right)>x_{1}$ , therefore $x_{1}\in I$ .

Substituting $z=x_{1},x=g_{1}\left(x_{0}\right),\ y=g_{2}\left(g_{1}\left(x_{0}\right)\right)$ in (8), and taking into account (6) for $n=0$ , we get the identity:

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

With this, and taking into account the convexity of $f$ and the above proved results, we obtain $f\left(x_{1}\right)<0$ , from which it results $x_{1}<\bar{x},$ hence $x_{1}-g_{1}\left(x_{1}\right)<0$ .

In this way the following relations were proved:

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

Since $x_{0}<x_{1}$ and $g_{1}$ is increasing, it follows that $g_{1}\left(x_{0}\right)<g_{1}\left(x_{1}\right),$ from which there results $g_{2}\left(g_{1}\left(x_{0}\right)\right)>g_{2}\left(g_{1}\left(x_{1}\right)% \right),$ because we assumed that $g_{2}$ is decreasing.

Let now $x_{n}\in I$ be arbitrary element of the sequence generated by (6) for which $f\left(x_{n}\right)>0$ and $g_{2}\left(g_{1}\left(x_{n}\right)\right)\in I$ . From $x_{n}<\bar{x}$ it results that $x_{n}-g_{1}\left(x_{n}\right)<0$ . Repeating (for $x_{n}$ ) the above procedure (corresponding to $x_{0}$ ), we obtain:

(9)

\left\{\begin{array}[c]{c}x_{n}<g_{1}\left(x_{n}\right)<x_{n+1}<\bar{x}<g_{2}% \left(g_{1}\left(x_{n}\right)\right);\\ g_{1}\left(x_{n}\right)<g_{1}\left(x_{n+1}\right);\\ g_{2}\left(g_{1}\left(x_{n}\right)\right)>g_{2}\left(g_{1}\left(x_{n+1}\right)% \right),\end{array}\right.

relations which prove the monotonicity of the two sequences. These relations also prove that both sequences are bounded.

Now we show that these sequences have a common limit, $l$ , where $l=\lim x_{n}$ .

Write $l_{1}=\lim g_{1}\left(x_{n}\right),\ l_{2}=\lim g_{2}\left(g_{1}\left(x_{n}% \right)\right),\$ and suppose that $l_{1}\neq l_{2}$ .

From the continuousness of $g_{1}$ and $g_{2}$ , and from the definition of $l$ , we deduce:

(10)		$\displaystyle l_{1}$	$\displaystyle=g_{1}\left(l\right);$
	$\displaystyle l_{2}$	$\displaystyle=g_{2}\left(l_{1}\right).$

But, by virtue of (9), $l_{1}\geq l\leq l_{2}$ , hence $g_{1}\left(l_{1}\right)\leq g_{1}\left(l\right)\leq g_{1}\left(l_{2}\right)$ and $g_{2}\left(l_{1}\right)\geq g_{2}\left(l\right)\geq g_{2}\left(l_{2}\right)$ , and, taking into account (10), it results $g_{1}\left(l_{1}\right)\leq l_{1}$ , namely $l_{1}-g_{1}\left(l_{1}\right)\geq 0$ , therefore $l_{1}\geq\bar{x}$ . In other words, the following inequalities hold:

\bar{x}\leq l_{1}\leq l\leq l_{2},

from which, taking into account the monotonicity of $g_{1}$ , we get:

\bar{x}=g_{1}\left(\bar{x}\right)\leq g_{1}\left(l_{1}\right)\leq g_{1}\left(l% \right)\leq g_{1}\left(l_{2}\right),

hence

\bar{x}\leq g_{1}\left(l_{1}\right)\leq l_{1}.

But, since $l_{1}\geq\bar{x},\ g_{1}$ is increasing and $g_{2}$ is decreasing, there results $g_{1}\left(l_{1}\right)\geq g_{2}\left(l_{1}\right)$ , from which we deduce $g_{1}\left(l_{1}\right)\geq l_{2}$ , which, together with $l_{1}\geq g_{1}\left(l_{1}\right)$ , leads to $l_{1}\geq l_{2}$ , and this one, together with $l_{1}\leq l_{2}$ , implies $l_{1}=l_{2}$ , which contradicts the hypothesis $l_{1}\neq l_{2}$ .

Therefore $l_{1}=l_{2}$ ; because $l_{1}\leq l\leq l_{2}$ , we have $l_{1}=l_{2}=l$ .

Passing at limit in (6), and considering the continuousness of the functions $f,g_{1},g_{2},$ it results that $l=\bar{x}$ is the root for equation (1).

With this, Theorem 2.1 is completely proved.

∎

The following theorems can be proved in a similar manner:

Theorem 2.2.

If the functions $f,g_{1},g_{2}$ fulfil the conditions (a)–(e) and, in addition:

(i₂)

$f$ is increasing and concave on $I$ ;
(ii₂)

there exists $x_{0}\in I$ for which $f\left(x_{0}\right)>0,\ x_{0}-g_{1}\left(x_{0}\right)>0$ and $g_{2}\left(g_{1}\left(x_{0}\right)\right)\in I$ ,

then the sequences $\left(x_{n}\right),\ \left(g_{1}\left(x_{n}\right)\right),\ \left(g_{2}\left(g% _{1}\left(x_{n}\right)\right)\right),\ n=0,1,\ldots,$ have the properties:

(j₂)

the sequences $\left(x_{n}\right)$ and $\left(g_{1}\left(x_{n}\right)\right)$ are decreasing and convergent;
(jj₂)

the sequence $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right)$ is increasing and convergent;
(jjj₂)

$\lim x_{n}=\lim g_{1}\left(x_{n}\right)=\lim g_{2}\left(g_{1}\left(x_{n}\right% )\right)=\bar{x}$ , where $\bar{x}$ is the root of equation (1).

Theorem 2.3.

If the functions $f,g_{1},g_{2}$ fulfil the conditions (a)–(e) and, in addition,

(i₃)

$f$ is decreasing and convex in $I;$
(ii₃)

there exists $x_{0}\in I$ for which $f\left(x_{0}\right)<0,\ x_{0}-g_{1}\left(x_{0}\right)>0$ and $g_{2}\left(g_{1}\left(x_{0}\right)\right)\in I$ ,

then the sequences $\left(x_{n}\right),\left(g_{1}\left(x_{n}\right)\right),\ g_{2}\left(g_{1}% \left(x_{n}\right)\right)),\ n=0,1,\ldots,$ have the properties:

(j₃)

the sequences $\left(x_{n}\right)$ and $\left(g_{1}\left(x_{n}\right)\right)$ are decreasing and convergent;
(jj₃)

the sequence $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right)$ is increasing and convergent;
(jjj₃)

$\lim x_{n}=\lim g_{1}\left(x_{n}\right)=\lim g_{2}\left(g_{1}\left(x_{n}\right% )\right)=\bar{x}$ , where $\bar{x}$ is the root of equation (1).

Theorem 2.4.

If the functions $f,g_{1},g_{2}$ fulfil the condition (a)–(e) and, in addition,

(i₄)

$f$ is decreasing and concave;
(ii ${}_{4}t)$

there exists $x_{0}\in I$ for which $f\left(x_{0}\right)>0,\ x_{0}-g_{1}\left(x_{0}\right)<0$ and $g_{2}\left(g_{1}\left(x_{0}\right)\right)\in I$ ,

then the sequences $\left(x_{n}\right),\left(g_{1}\left(x_{n}\right)\right),~\left(g_{2}\left(g_{1% }\left(x_{n}\right)\right)\right),\ n=0,1,\ldots,$ have the properties:

(j₄)

the sequences $\left(x_{n}\right)$ and $\left(g_{1}\left(x_{n}\right)\right)$ are increasing and convergent;
(jj₄)

the sequence $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right)$ is decreasing and convergent;
(jjj₄)

$\lim x_{n}=\lim g_{1}\left(x_{n}\right)=\lim g_{2}\left(g_{1}\left(x_{n}\right% )\right)=\bar{x}$ , where $\bar{x}$ is the root of equation (1).

Remark 2.5.

If the function $f;\left[a,b\right]\rightarrow\mathbb{R}$ is continuous and two times differentiable on $I=\left[a,b\right],\ a<b$ , and if $f^{\prime}\left(x\right)\neq 0,\ f^{\prime\prime}\left(x\right)\neq 0$ for every $x\in I$ , then, according to the monotonicity and convexity of $f$ , the simple procedures for constructing $g_{1}$ and $g_{2}$ are obtained as follows:

If $f$ is increasing and convex, and equation (1) has a root $\bar{x}\in I$ , then we may consider $g_{1}\left(x\right)=x-f\left(x\right)/f^{\prime}\left(b\right),\ g_{2}\left(x% \right)=x-f\left(x\right)/f^{\prime}\left(a\right)$ . In this case $f,g_{1},g_{2}$ fulfil the conditions (a)–(e) and if $x_{0}\in I$ is a point for which $f\left(x_{0}\right)<0$ , then $x_{0}-g_{1}\left(x_{0}\right)=f\left(x_{0}\right)/f^{\prime}\left(b\right)<0;$ if, in addition, $g_{2}\left(g_{1}\left(x_{n}\right)\right)\in I$ and the equation $f\left(x\right)=0$ has the root $\bar{x}$ on $\left[a,b\right],$ then the hypotheses of Theorem 2.1 are verified, therefore the corresponding sequences satisfy the conclusions of this theorem.

The same conclusions as above are also true if $g_{1}$ and $g_{2}$ are provided by the relations $g_{1}\left(x\right)=x-\lambda_{1}f\left(x\right)$ and $g_{2}\left(x\right)=x-\lambda_{2}f\left(x\right)$ , respectively, where $\lambda_{1},\lambda_{2}\in\mathbb{R}$ , and $\lambda_{1}\geq f^{\prime}\left(b\right),\ 0<\lambda_{2}\leq f^{\prime}\left(a\right)$ .

Analogous constructions can be given using Theorems 2.2, 2.3 and 2.4. ∎

3. Numerical example

Consider the equation

f\left(x\right)=x-2\arctan x=0

for $x\in\left[3/2,3\right]$ . According to the above remark, we construct the functions $g_{1},g_{2}$ for $f$ , obtaining

	$\displaystyle g_{1}\left(x\right)$	$\displaystyle=\left(10\arctan x-x\right)/4,$
	$\displaystyle g_{2}\left(x\right)$	$\displaystyle=(26\arctan x-8x)/5.$

It is easy to see that, putting $x_{0}=3/2,$ the functions $f,g_{1}$ and $g_{2}$ fulfill the conditions of Theorem 9 on the interval $I=\left[3/2,3\right].$

The sequence generated by relation (6) for this case can be stopped at the step $n=3$ , because of the fact that $x_{3}=g_{1}\left(x_{3}\right)=g_{2}\left(g_{1}\left(x_{3}\right)\right),$ as results from the table below:

${\footnotesize n}$	${\footnotesize x}_{n}$	${\footnotesize g}_{1}\left(x_{n}\right)$	${\footnotesize g}_{2}\left(g_{1}\left(x_{n}\right)\right)$	${\footnotesize f}\left(x_{n}\right)$
0	1.500000000000000	2.081984308118323	2.508547854696064	-4.65 ${}\cdot{}$ 10^-01
1	2.323572652303234	2.330068291038034	2.331956675671997	-5.19 ${}\cdot{}$ 10^-03
2	2.331122226685893	2.331122350500425	2.331122386182527	-9.90 ${}\cdot{}$ 10^-08
3	2.331122370414423	2.331122370414423	2.331122370414423	-3.53 ${}\cdot{}$ 10^-17

References

[1] Balázs, M., ^†^†margin: available soon,
refresh and click here $\rightarrow$ A bilateral approximating method for finding the real roots of real equations., Rev. Anal. Numér. Théor. Approx. 21, 2 (1992), pp.111-117.
[2] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensen’s method, Mathematica, 35, (58), 1 (1993), pp. 71-76.
[3] Păvăloiu, I., ^†^†margin: available soon,
refresh and click here $\rightarrow$ Solving Equations by Interpolation. Ed. Dacia (1981) (in Romanian).

Received 8 XII 1993

Institutul de Calcul

Str. Republicii, Nr.37

PO. Box 68

3400 Cluj-Napoca

Romania

Bilateral approximations for the solutions of scalar equations

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

Bilateral approximations for the Solutions
of Scalar Equations

1. Introduction

Definition 1.1.

Definition 1.2.

2. Monotonicity of the sequences Generated by the Aitken-Steffensen Method

Theorem 2.1.

Proof.

Theorem 2.2.

Theorem 2.3.

Theorem 2.4.

Remark 2.5.

3. Numerical example

References

Related Posts

Bilateral approximations for the solutions of scalar equations

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

Bilateral approximations for the Solutions of Scalar Equations

1. Introduction

Definition 1.1.

Definition 1.2.

2. Monotonicity of the sequences Generated by the Aitken-Steffensen Method

Theorem 2.1.

Proof.

Theorem 2.2.

Theorem 2.3.

Theorem 2.4.

Remark 2.5.

3. Numerical example

References

Related Posts

Bilateral approximations for the Solutions
of Scalar Equations