Sur l’ordre de convergence des méthodes d’itération

par
Ion Păvăloiu

Dans l’ouvrage [1] C. Brezinski a défini la notion d’ordre de convergence d’une suite et une notion de comparaison des vitesses de convergence de deux suites.

Dans l’analyse numérique un ensemble de méthodes de résolution des équations conduit a l’approximation des solutions des équations considérées par des éléments d’une suite convenablement construite.

Si nous pouvons construire une suite dont les termes approximent la solution de l’équation donnée, alors il est très important de connaître la vitesse de convergence de cette suite vers la solution de l’équation considérée.

Dans cette note nous chercherons un rapport entre l’ordre de convergence de deux suites qui ont la même vitesse de convergence. Nous appliquerons les résultats à un problème de convergence des méthodes numériques pour la résolution des équations.

Soit $\left(X,\rho\right)$ un espace métrique et $\left(u_{n}\right)_{n=0}^{\infty}$ un suite d’éléments de l’éspace $X$ . Nous supposons que la suite $\left(u_{n}\right)_{n=0}^{\infty}$ converge vers l’élément $u\in X$ .

Nous désignons par $r$ un nombre réel et positif quelconque.

Définition 1.

[1]. Nous disons que la suite $\left(u_{n}\right)_{n=0}^{\infty}$ a l’ordre de convergence $r$ s’il existe deux constantes positives $C_{1}$ et $C_{2}$ de telle manière que pour chaque $n=0,1,\ldots,$ ont lieu les inégalités

(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

En ce qui concerne l’ordre de convergence d’un suite, dans l’ouvrage [1] on démontre le théorème suivante.

Théorème 1.

Si suite $\left(u_{n}\right)_{n=0}^{\infty}$ a l’ordre de convergence $r$ , alors $r$ est unique.

Soit maintenant $\left(u_{n}\right)_{n=0}^{\infty},\ u_{n}$ $\in X,\ n=0,1,\ldots,$ et $\left(v_{n}\right)_{n=0}^{\infty},\ v_{n}\in X,\ n=0,1,\ldots,$ deux suites qui convergent vers la même limite $u\in X$ .

Définition 2.

[1]. Nous disons que la suite $\left(v_{n}\right)_{n=0}^{\infty}$ converge au moins aussi rapidement que $\left(u_{n}\right)_{n=0}^{\infty}$ si sont vérifiées les inégalités suivantes:

(2)

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

où $C$ est une constante positive indépendent de $n$ .

Définition 3.

[1] Nous disons que les suites $\left(u_{n}\right)_{n=0}^{\infty},$ $u_{n}\in X,\ n=1,2,\ldots,$ et $\left(v_{n}\right)_{n=0}^{\infty},\ v_{n}\in X,\ n=1,2,\ldots,$ ont la même vitesse de convergence s’il existent deux constantes positives $C_{1}$ et $C_{2}$ telles que, pour chaque $n=0,1,\ldots,$ sont satisfaites les inégalités:

(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)

Remarque 1.

Il est facile de montrer que si les inégalités (3) ont lieu, alors évidemment, pour chaque $n=0,1,\ldots,$ ont lieu les inégalités

(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)

Remarque 2.

En ce qui concerne l’ordre de convergence d’une suite nous montrerons maintenant, par un exemple simple qu’il existe des suites sans l’ordre de convergence.

Soit $X=R$ et $\left(a_{n}\right)_{n=0}^{\infty}$ une suite de nombres réels définie à l’aide des égalitès.

(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.

La suite $\left(x_{n}\right)_{n=0}^{\infty}$ définie ci-dessus est convergente verso $0$ .

Nous montrerons que cette suite n’a pas d’ordre de convergence au sens de la définition 1.

Des inégalités (1) nous déduisons les inégalités suivantes:

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,

d’où il résulte que pour la suite $\left(u_{n}\right)_{n=0}^{\infty}$ posséde un ordre de convergence $r$ il est néccesaire qu’il existe un $r$ de telle manière que la suite $\left(\delta_{n}\right)_{n=0}^{\infty}$ donnée par l’egalité $\delta_{n}=\tfrac{\rho\left(u_{n+1},u\right)}{\rho\left(u_{n},u\right)^{r}},\ % n=0,1,\ldots,$ soit bornée.

Mais, dans le cas de la suite (5) on a

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

suite qui n’est pas bornée, parce que sa sous-suite $\left(\delta_{2k}\right)_{k=1}^{\infty}$ n’est pas bornée pour aucun $r>0$ parce que nous avons:

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

Maintenant nous démontrerons le théorême suivant:

Théorème 2.

Si les suites $\left(u_{n}\right)_{n=0}^{\infty}$ et $\left(v_{n}\right)_{n=0}^{\infty}\ u_{n},v_{n}\in X,\ n=0,1,\ldots,$ ont la même vitesse de convergence, et si l’une des deux suites a un ordre de convergence, alors l’autre suite a le même ordre de convergence.

Démonstration..

Pour préciser les idées nous désignons par $r$ l’ordre de convergence de la suite $\left(u_{n}\right)_{n=0}^{\infty}$ . Parce que les deux suites ont la même vitesse de convergence il résulte les inégalités:

(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,

et tenant compte que la suite $\left(u_{n}\right)_{n=0}^{\infty}$ a l’ordre de convergence $r$ résulte:

(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,

où $C_{1},C_{2},C_{1}^{\prime},C_{2}^{\prime}$ sont des constantes positives, indépendantes de $n$ .

De (6) et (7) on déduit:

(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

Toujours de (6) et (7) on déduit:

(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

Des inégaliteś (8) et (9) il résulte la double inégalité:

(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

où les constantes $\frac{C_{1}C_{1}^{\prime}}{C_{2}^{r}}$ et $\frac{C_{2}C_{2}^{\prime}}{C_{1}^{r}}$ ne dépendent pas de $n$ .

Du théorème 1 il résulte que la nombre réel et positif $r$ pour lequel ont lieu les inégalités (10) est unique.

Par la suite nous appliquerons les résultats exposés ci-dessus pour préciser l’ordre de convergence des méthodes numériques de résolution des équations opérationnelles.

Soient $X$ et $Y$ deux espaces linéaires normés et soit

(11)

P\left(x\right)=\theta

une équation, où $P:X\rightarrow Y$ est une application et $\theta$ est l’élément nul de l’éspace $Y$ .

Nous désignons par $\bar{x}\in X$ une solution de l’équation (11) et nous supposons que nous avons construit une suite $\left(x_{n}\right)_{n=0}^{\infty}$ d’éléments de l’éspace $X$ , qui converge vers $\bar{x}$ .

En practique nous ne parvenons pas toujours à obtenir exactement la solution $\bar{x}$ de l’équation (11) mais nous pouvons approximer l’élément $\bar{x}$ par un élément convenable de la suite $\left(x_{n}\right)_{n=0}^{\infty}$ .

Il est également important de connaître quelle est la vitesse de convergence de la suite $\left(x_{n}\right)_{n=0}^{\infty}$ vers $\bar{x}$ et d’évaluer quel est le nombre de pas tel que $x_{n}^{\prime}$ considéré comme une appoximation de la solution $\bar{x}$ puisse remplacer cette solution avec un précision donnée à l’avance.

Mais nous ne connaissons pas l’élément $\bar{x}$ et c’est pourquoi il est très difficile d’appliquer les résultats exposés dans cette note pour étudier la vitesse de convergence de la suite $\left(x_{n}\right)_{n=0}^{\infty}$ .

Un critérium simple pour vérifier que $x_{n}$ ,approche $\bar{x}$ est de voir quelle est la distance entre le nombre réel $\left\|P\left(x_{n}\right)\right\|$ et $0$ . A partir de cette remarque nous proposons de’étudier la vitesse de convergence de la suite $\left(P\left(x_{n}\right)\right)_{n=0}^{\infty}$ .

Nous supposons maintenant que l’application $P$ est continue et alors du fait que $\bar{x}=\lim\limits_{n\rightarrow\infty}x_{n}$ il résulte que $\lim\limits_{n\rightarrow\infty}\left\|P\left(x_{n}\right)\right\|=0$ .

Par des notions analogues aux notions présentées dans la première partie de cet ouvrage, nous pouvons préciser la notion d’ordre de convergence pour la suite $\left(x_{n}\right)_{n=0}^{\infty}$ qui approche la solution $\bar{x}$ de l’équation (11). ∎

Définition 4.

Nous disons que la suite $\left(x_{n}\right)_{n=0}^{\infty}$ a l’ordre de convergence $r$ relativement à l’équation (11), s’il existe deux constantes positives, $\rho_{1},\rho_{2}$ de telle manière que pour chaque $n=0,1,\ldots,$ on ait:

(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},

Il résulte évidemment du théorème 1 que si $\left(x_{n}\right)_{n=0}^{\infty}$ a l’ordre de convergence $r$ , alors $r$ est unique.

Nous considérons maintenant deux suites $\left(x_{n}\right)_{n=0}^{\infty}$ et $\left(y_{n}\right)_{n=0}^{\infty}$ dont nous supposons qu’elles ont le même limite $\bar{x}\in X$ où $\bar{x}$ est la solution de l’équation (11).

Par analogie avec les notions précisées dans les définitions 2 et 3 nous présentons les définitions suivantes:

Définition 5.

Nous disons que la suite $\left(x_{n}\right)_{n=0}^{\infty}$ converge au moins aussi rapidement que $\left(y_{n}\right)_{n=0}^{\infty}$ relativement à l’équation (11) si sont vérifiées les inégalités:

(13)

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

où $\rho>1$ est une constante indépendante de $n$ .

Définition 6.

Nous disons que les suites $\left(x_{n}\right)_{n=0}^{\infty}$ et $\left(y_{n}\right)_{n=0}^{\infty}$ ont la même vitesse de convergence relativement à l’équation (11) s’il existe deux constantes positives $\rho_{1}$ et $\rho_{2}$ de telle manière que pour chaque $n=0,1,\ldots,$ on ait:

\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\|.

Une conséquence du théorème 2 est la suivante.

Théorème 3.

Si les suites $\left(x_{n}\right)_{n=0}^{\infty}$ et $\left(y_{n}\right)_{n=0}^{\infty}$ ont la même vitesse de convergence relativement à l’équation (11) et si l’une des deux suites a un ordre de convergence relativement à l’équation (11) alors, l’autre suite a le même ordre de convergence relativement à l’équation (11).

Bibliographie

[1] Brezinski, C., Comparation de suites convergentes, Revue francaise d’informatique et de recherches operationnelles, Nr. R-2, 95–99, (1971).
[2] Păvăloiu, I., ^†^†margin: clickable $\rightarrow$ Introducere în teoria aproximării soluţiilor ecuaţiilor, Editura Dacia, Cluj-Napoca, (1976).
[3] Păvăloiu, I., ^†^†margin: clickable $\rightarrow$ Sur les procédés itératifs à un ordre élevé de convergence, Mathematica, Cluj, 12(35), 2 309–324, (1970).

Reçu, 20.IV.1980

Institutul de Matematică,

Str. Republicii 37

C.P. 68 3400 Cluj-Napoca

România

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