On the convergence order of the iterative methods

by
Ion Pavaloiu

In the work [ 1 ] C. Brezinski defined the notion of order of convergence of a sequence and a notion of comparison of the speeds of convergence of two sequences.

In numerical analysis, a set of methods for solving equations leads to the approximation of the solutions of the equations considered by elements of a suitably constructed sequence.

If we can construct a sequence whose terms approximate the solution of the given equation, then it is very important to know the speed of convergence of this sequence towards the solution of the equation considered.

In this note we will look for a relationship between the order of convergence of two sequences that have the same speed of convergence. We will apply the results to a problem of convergence of numerical methods for solving equations.

Either $\left(X,\rho\right)$ a metric space and $\left(u_{n}\right)_{n=0}^{\infty}$ a sequence of elements of space $X$ . We assume that the following $\left(u_{n}\right)_{n=0}^{\infty}$ converges to the element $u\in X$ .

We designate by $r$ any real and positive number.

Definition 1 .

[ 1 ] . We say that the following $\left(u_{n}\right)_{n=0}^{\infty}$ has the order of convergence $r$ if there are two positive constants $C_{1}$ And $C_{2}$ in such a way that for each $n=0,1,\ldots,$ inequalities take place

(1)

C_{2}\rho\left(u_{n},u\right)^{r}\leq\rho\left(u_{n+1},u\right)\leq C_{1}\rho% \left(u_{n},u\right)^{r},\qquad n=0,1,\ldots

Concerning the order of convergence of a sequence, in the work [ 1 ] we demonstrate the following theorem.

Theorem 1 .

Yes, please. $\left(u_{n}\right)_{n=0}^{\infty}$ has the order of convergence $r$ , SO $r$ is unique.

Be it now $\left(u_{n}\right)_{n=0}^{\infty},\ u_{n}$ $\in X,\ n=0,1,\ldots,$ And $\left(v_{n}\right)_{n=0}^{\infty},\ v_{n}\in X,\ n=0,1,\ldots,$ two sequences that converge to the same limit $u\in X$ .

Definition 2 .

[ 1 ] . We say that the following $\left(v_{n}\right)_{n=0}^{\infty}$ converges at least as quickly as $\left(u_{n}\right)_{n=0}^{\infty}$ if the following inequalities are verified:

(2)

\rho\left(v_{n},u\right)\leq C\rho\left(u_{n},u\right),\qquad n=0,1,\ldots,

Or $C$ is a positive constant independent of $n$ .

Definition 3 .

[ 1 ] We say that the suites $\left(u_{n}\right)_{n=0}^{\infty},$ $u_{n}\in X,\ n=1,2,\ldots,$ And $\left(v_{n}\right)_{n=0}^{\infty},\ v_{n}\in X,\ n=1,2,\ldots,$ have the same speed of convergence if there are two positive constants $C_{1}$ And $C_{2}$ such that, for each $n=0,1,\ldots,$ the inequalities are satisfied:

(3)

C_{1}\rho\left(u_{n},u\right)\leq\rho\left(v_{n},u\right)\leq C_{2}\rho\left(u% _{n},u\right)

Note 1 .

It is easy to show that if the inequalities ( 3 ) hold, then obviously, for each $n=0,1,\ldots,$ inequalities take place

(4)

\tfrac{1}{C_{2}}\rho\left(v_{n},u\right)\leq\rho\left(u_{n},u\right)\leq\tfrac% {1}{C_{1}}\rho\left(v_{n},u\right)

Note 2 .

Concerning the order of convergence of a sequence, we will now show, by a simple example, that there exist sequences without the order of convergence.

Either $X=R$ And $\left(a_{n}\right)_{n=0}^{\infty}$ a sequence of real numbers defined using equalities.

(5)

\left\{\begin{array}[c]{c}a_{2k+1}=\tfrac{1}{2k+1},\qquad k=0,1,\ldots,\\ a_{2k}=\frac{1}{k^{k}},\qquad k=1,2,\ldots\end{array}\right.

The sequel $\left(x_{n}\right)_{n=0}^{\infty}$ defined above is convergent verso $0$ .

We will show that this sequence has no order of convergence in the sense of definition 1 .

From inequalities ( 1 ) we deduce the following inequalities:

C_{2}\leq\tfrac{\rho\left(u_{n+1},u\right)}{\rho\left(u_{n},u\right)^{r}}\leq C% _{1},\qquad n=0,1,\ldots,

from which it follows that for the continuation $\left(u_{n}\right)_{n=0}^{\infty}$ has an order of convergence $r$ it is necessary that there exists a $r$ in such a way that the following $\left(\delta_{n}\right)_{n=0}^{\infty}$ given by equality $\delta_{n}=\tfrac{\rho\left(u_{n+1},u\right)}{\rho\left(u_{n},u\right)^{r}},\ % n=0,1,\ldots,$ be limited.

But, in the case of the sequence ( 5 ) we have

\delta_{n}=\tfrac{a_{n+1}}{a_{n}^{r}},\qquad n=0,1,\ldots,

sequence which is not bounded, because its subsequence $\left(\delta_{2k}\right)_{k=1}^{\infty}$ is not limited for any $r>0$ because we have:

\delta_{2k}=\tfrac{a_{2k+1}}{\left(a_{2k}\right)^{k}}=\tfrac{k^{rk}}{2k+1},% \qquad k=0,1,\ldots\hfil\qed

Now we will prove the following theorem:

Theorem 2 .

If the sequels $\left(u_{n}\right)_{n=0}^{\infty}$ And $\left(v_{n}\right)_{n=0}^{\infty}\ u_{n},v_{n}\in X,\ n=0,1,\ldots,$ have the same speed of convergence, and if one of the two sequences has an order of convergence, then the other sequence has the same order of convergence.

Demonstration..

To clarify the ideas we designate by $r$ the order of convergence of the sequence $\left(u_{n}\right)_{n=0}^{\infty}$ . Because the two sequences have the same speed of convergence, the following inequalities result:

(6)

C_{1}\rho\left(u_{n},u\right)\leq\rho\left(v_{n},u\right)\leq C_{2}\rho\left(u% _{n},u\right),\qquad n=0,1,\ldots,

and taking into account that the following $\left(u_{n}\right)_{n=0}^{\infty}$ has the order of convergence $r$ results:

(7)

C_{r}^{\prime}\rho\left(u_{n},u\right)^{r}\leq\rho\left(u_{n+1},u\right)\leq C% _{2}^{\prime}\rho\left(u_{n},u\right)^{r},\qquad n=0,1,\ldots,

Or $C_{1},C_{2},C_{1}^{\prime},C_{2}^{\prime}$ are positive constants, independent of $n$ .

From ( 6 ) and ( 7 ) we deduce:

(8)

\rho\left(v_{n+1},u\right)\leq C_{2}\rho\left(u_{n+1},u\right)\leq C_{2}C_{2}^% {\prime}\rho\left(u_{n},u\right)^{r}\leq\tfrac{C_{2}C_{2}^{\prime}}{C_{1}^{r}}% \rho\left(v_{n},u\right)^{r},\ \ n=0,1,\ldots

Still from ( 6 ) and ( 7 ) we deduce:

(9)

\rho\left(v_{n+1},u\right)\geq C_{1}\rho\left(u_{n+1},u\right)\geq C_{1}C_{1}^% {\prime}\rho\left(u_{n},u\right)^{r}\geq\tfrac{C_{1}C_{1}^{\prime}}{C_{2}^{r}}% \rho\left(v_{n},u\right)^{r},n=0,1,\ldots

From inequalities ( 8 ) and ( 9 ) the double inequality results:

(10)

\tfrac{C_{1}C_{1}^{\prime}}{C_{2}^{r}}\rho\left(v_{n},u\right)^{r}\leq\rho% \left(v_{n+1},u\right)\leq\tfrac{C_{2}C_{2}^{\prime}}{C_{1}^{r}}\rho\left(v_{n% },u\right)^{r},\qquad n=0,1,\ldots

where the constants $\frac{C_{1}C_{1}^{\prime}}{C_{2}^{r}}$ And $\frac{C_{2}C_{2}^{\prime}}{C_{1}^{r}}$ do not depend on $n$ .

From Theorem 1 it follows that the real and positive number $r$ for which the inequalities ( 10 ) take place is unique.

Subsequently, we will apply the results presented above to specify the order of convergence of the numerical methods for solving operational equations.

Let $X$ And $AND$ two normed linear spaces and either

(11)

P\left(x\right)=\theta

an equation, where $P:X\rightarrow Y$ is an application and $\theta$ is the zero element of the space $AND$ .

We designate by $\bar{x}\in X$ a solution of equation ( 11 ) and we assume that we have constructed a sequence $\left(x_{n}\right)_{n=0}^{\infty}$ of elements of space $X$ , which converges towards $\bar{x}$ .

In practice we do not always manage to obtain the exact solution. $\bar{x}$ of equation ( 11 ) but we can approximate the element $\bar{x}$ by a suitable element of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ .

It is also important to know what is the convergence speed of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ towards $\bar{x}$ and to evaluate what is the number of steps such that $x_{n}^{\prime}$ considered as an approximation of the solution $\bar{x}$ can replace this solution with a precision given in advance.

But we don't know the element $\bar{x}$ and this is why it is very difficult to apply the results presented in this note to study the speed of convergence of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ .

A simple criterion to verify that $x_{n}$ ,approach $\bar{x}$ is to see what the distance is between the real number $\left\|P\left(x_{n}\right)\right\|$ And $0$ . From this remark we propose to study the speed of convergence of the sequence $\left(P\left(x_{n}\right)\right)_{n=0}^{\infty}$ .

We now assume that the application $P$ is continuous and then from the fact that $\bar{x}=\lim\limits_{n\rightarrow\infty}x_{n}$ it follows that $\lim\limits_{n\rightarrow\infty}\left\|P\left(x_{n}\right)\right\|=0$ .

Using notions similar to those presented in the first part of this work, we can clarify the notion of order of convergence for the following $\left(x_{n}\right)_{n=0}^{\infty}$ which approaches the solution $\bar{x}$ of equation ( 11 ). ∎

Definition 4 .

We say that the sequel $\left(x_{n}\right)_{n=0}^{\infty}$ has the order of convergence $r$ relative to equation ( 11 ), if there are two positive constants, $\rho_{1},\rho_{2}$ in such a way that for each $n=0,1,\ldots,$ we have:

(12)

\rho_{1}\left\|P\left(x_{n}\right)\right\|^{r}\leq\left\|P\left(x_{n+1}\right)% \right\|\leq\rho_{2}\left\|P\left(x_{n}\right)\right\|^{r},

It obviously follows from Theorem 1 that if $\left(x_{n}\right)_{n=0}^{\infty}$ has the order of convergence $r$ , SO $r$ is unique.

We now consider two sequences $\left(x_{n}\right)_{n=0}^{\infty}$ And $\left(y_{n}\right)_{n=0}^{\infty}$ which we assume have the same limit $\bar{x}\in X$ Or $\bar{x}$ is the solution to equation ( 11 ).

By analogy with the notions specified in definitions 2 and 3 we present the following definitions:

Definition 5 .

We say that the sequel $\left(x_{n}\right)_{n=0}^{\infty}$ converges at least as quickly as $\left(y_{n}\right)_{n=0}^{\infty}$ relative to equation ( 11 ) if the inequalities are verified:

(13)

\left\|P\left(x_{n}\right)\right\|\leq\rho\left\|P\left(y_{n}\right)\right\|,% \qquad n=0,1,\ldots

Or $\rho>1$ is a constant independent of $n$ .

Definition 6 .

We say that the sequels $\left(x_{n}\right)_{n=0}^{\infty}$ And $\left(y_{n}\right)_{n=0}^{\infty}$ have the same speed of convergence relative to equation ( 11 ) if there are two positive constants $\rho_{1}$ And $\rho_{2}$ in such a way that for each $n=0,1,\ldots,$ we have:

\rho_{1}\left\|P\left(x_{n}\right)\right\|\leq\left\|P\left(y_{n}\right)\right% \|\leq\rho_{2}\left\|P\left(x_{n}\right)\right\|.

A consequence of Theorem 2 is the following.

Theorem 3 .

If the sequels $\left(x_{n}\right)_{n=0}^{\infty}$ And $\left(y_{n}\right)_{n=0}^{\infty}$ have the same speed of convergence relative to equation ( 11 ) and if one of the two sequences has an order of convergence relative to equation ( 11 ) then the other sequence has the same order of convergence relative to equation ( 11 ).

Bibliography

[1] Brezinski, C., Comparison of convergent sequences , French Journal of Computer Science and Operational Research, No. R-2, 95–99, (1971).
[2] Pavaloiu, I., ^†^†margin: clickable $\rightarrow$ Introduction to the theory of approximation of solutions of equations , Dacia Publishing House, Cluj-Napoca, (1976).
[3] Pavaloiu, I., ^†^†margin: clickable $\rightarrow$ On iterative processes with a high order of convergence , Mathematica, Cluj, 12 (35), 2 309–324, (1970).

Received, 20.IV.1980

Institute of Mathematics,

37 Republic Street

PO Box 68 3400 Cluj-Napoca

Romania

On the convergence order of the iterative methods

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Notes

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On the convergence order of the iterative methods

Definition 1 .

Theorem 1 .

Definition 2 .

Definition 3 .

Note 1 .

Note 2 .

Theorem 2 .

Demonstration..

Definition 4 .

Definition 5 .

Definition 6 .

Theorem 3 .

Bibliography

Related Posts