"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

Preprint Nr.1, 1983, pp. 175-182

Sur des Méthodes Itératives Optimales

par
Ion Păvăloiu et Ioan Şerb

Dans ce travail nous étudions des méthodes itératives pour la résolution de l’équation:

(1)

x=\varphi\left(x\right),

où $\varphi:I\rightarrow X$ est une aplication donnée et $\left(X,\rho\right)$ est un espace métrique complet.

A l’application $\varphi$ nous attacherons une aplication $F:X^{k}\rightarrow X$ , qui a la propriété suivante:

(2)

F\left(x,x,\ldots,x\right)=\varphi\left(x\right),\ \ \ \ x\in X.

Pour résoudre l’équation (1) nous considerons la méthode itérative à plusieurs pas, de la forme:

(3)

x_{n+1}=F\left(x_{n},x_{n-1},\ldots,x_{n-k+1}\right),\ n=k-1,k,k+1,\ldots

Si $i_{0},i_{1},\ldots,i_{k-1}$ est une permutation des nombres $0,1,\ldots,\ k-1$ , alors $i_{0}+n-k+1,\ i_{1}+n-k+1,\ldots,i_{k-1}+n-k+1$ sera une permutation qui correspond aux nombres $n-k+1,\ n-k+2,\ldots,n$ .

Pour une telle permutation on obtient une nouvelle méthode itérative à plusieurs pas:

(4)

x_{n+1}=F\left(x_{i_{0}+n-k+1},x_{i_{1}+n-k+1},\ldots,x_{i_{k-1}+n-k+1}\right),

où $n=k-1,\ k,\ldots$

De cette maniere, à partir de l’application donnée $F$ , on obtient $k!$ méthodes itératives, qui sont en général distinctes.

Si dans certaines conditions imposéea à l’application $F$ , toutes ces $k!$ méthodes itératives convergent vers une solution de l’équation (1), le problème se pose de choisir la méthode pour laquelle on obtient la meilleure délimitation de l’erreur.

Dans ce qui suit nous supposerons que $F$ vérifie la relation suivante:

(5)

\displaystyle\rho\left(F\left(u_{1},u_{2},\ldots,u_{k}\right),F\left(v_{1},v_{% 2},\ldots,v_{k}\right)\right)\leq\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{% i}\right)^{\beta}\Big{)}^{\frac{1}{\beta}},

quele que soient les éléments $u_{1},u_{2},\ldots,u_{k},\ v_{1},v_{2},\ldots,v_{k}\in X$ , où $a_{i}\geq 0$ et $\beta>0$ sont données et $0<\sum_{i=1}^{k}a_{i}<1.$

On remarque que si $F$ vérifie les conditions (2) et (5) alors $\varphi$ vérifie la condition:

	$\displaystyle\rho\big{(}\varphi\left(x\right),\varphi\left(y\right)\big{)}$	$\displaystyle=\rho\big{(}F\left(x,x,\ldots,x\right),F\left(y,y,\ldots,y\right)% \big{)}$
		$\displaystyle\leq\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(x,y\right)^{\beta}\Big{)}% ^{\frac{1}{\beta}}=\Big{(}\sum_{i=1}^{k}a_{i}\Big{)}^{\frac{1}{\beta}}\rho% \left(x,y\right),$

et du fait que $0<\sum_{i=1}^{k}a_{i}<1$ , il résulte que $\varphi$ est une contraction, c’est-à-dire que l’équation (1) a une seul solution.

D’autre part, si nous désignons par $\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)$ l’ensemble des fonctions $F$ vérifiant les conditions (2) et (5), alors si $\beta<\beta^{\prime}$ il résulte $\mathcal{F}_{\beta}\left(a_{1},a_{2},\mathcal{\ldots},a_{k}\right)\subset% \mathcal{F}_{\beta^{\prime}}\left(a_{1},a_{2},\ldots a_{k}\right)$ .

Pour $\beta<\beta^{\prime}$ on déduit de l’inégalité de Hölder:

	$\displaystyle\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta}% \Big{)}^{\frac{1}{\beta}}$	$\displaystyle=\Big{[}\sum_{i=1}^{k}\left(a_{i}^{\frac{\beta}{\beta^{\prime}}}% \rho\left(u_{i},v_{i}\right)^{\beta}\right)a_{i}^{1-\frac{\beta}{\beta^{\prime% }}}\Big{]}^{\frac{1}{\beta}}$
		$\displaystyle\leq\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta% ^{\prime}}\Big{)}^{\frac{1}{\beta^{\prime}}}\Big{[}\sum_{i=1}^{k}\Big{(}a_{i}^% {1-\frac{\beta}{\beta^{\prime}}}\Big{)}^{\frac{\beta^{\prime}}{\beta^{\prime}-% \beta}}\Big{]}^{\frac{\beta^{\prime}-\beta}{\beta\beta^{\prime}}}$
		$\displaystyle=\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta^{% \prime}}\Big{)}^{\frac{1}{\beta^{\prime}}}\Big{(}\sum_{i=1}^{k}a_{i}\Big{)}^{% \frac{\beta^{\prime}-\beta}{\beta\beta^{\prime}}}$
		$\displaystyle<\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta^{% \prime}}\Big{)}^{\frac{1}{\beta^{\prime}}}$

donc $\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)\subset\mathcal{F}_{% \beta^{\prime}}\left(a_{1},a_{2},\ldots,a_{k}\right)$ .

Considérons les nombres $\alpha_{i}\in\mathbb{R}$ , $i=1,2,\ldots,k$ , qui vérifient les relations:

(6)

\alpha_{1}\geq\alpha_{2}\geq\ldots\geq\alpha_{k-1}\geq\alpha_{k}\geq 0,

(6^′)

0<\sum_{i=1}^{k}\alpha_{i}<1.

Nous considérons à présent les équations

(7)

P\left(u\right)=u^{k}-\alpha_{1}u^{k-1}-\ldots-\alpha_{k-1}u-\alpha_{k}=0,

(8)

Q\left(u\right)=u^{k}-\alpha_{k}u^{k-1}-\ldots-\alpha_{2}u-\alpha_{1}=0,

(9)

R\left(u\right)=u^{k}-\alpha_{i_{1}}u^{k-1}-\ldots-\alpha_{i_{k-1}}u-\alpha_{i% _{k}}=0,

où $i_{1},i_{2},\ldots,i_{k}$ est une permutation quelconque des nombres $1,2,\ldots,k$ .

LEMME.

Si $\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$ vérifient les conditions (6) et (6^′) alors chaque équation de la forme (9) a une seule racine positive. Si nous désignons par a la racine positive de l’équation (7) et par $b$ la racine positive de l’équation (8), alors la racine positive $c$ de l’équation (9) vérifie les inégalités suivantes:

(10)

0<a\leq c\leq b<1.

Démonstration.

Soit $i_{1},i_{2},\ldots,i_{k}$ une permutation des nombres $1,2,\ldots,k$ et soit $s$ le plue grand indice pour lequel $\alpha_{i_{s}}\neq 0$ .

Nous avons évidement $\alpha_{i_{s+1}}=\alpha_{i_{s+2}}=\cdots=\alpha_{i_{k}}=0$ et $\alpha_{i_{s}}\neq 0$ .

Considérons la fonction $\psi\left(u\right)=R\left(u\right)/u^{k-s}$ . Alors $\psi\left(0\right)=-\alpha_{i_{s}}<0$ et $\psi\left(1\right)=R\left(1\right)=1-\alpha_{i_{1}}-\ldots-\alpha_{i_{k-1}}-% \alpha_{i_{k}}=1-\alpha_{1}-\ldots-\alpha_{k}>0$ .

Donc $\psi\left(u\right)$ a une racine positive dans l’intervalles $\left(0,1\right)$ . Il résulte que $R\left(u\right)=u^{k-s}\psi\left(u\right)$ a une racine dans l’intervalle $\left(0,1\right)$ .

L’unicité de cette racine résulte immédiatement en considérant l’équation $f\left(v\right)=-v^{k}R\left(1/v\right)=0$ , pour laquelle $f^{\prime}\left(v\right)>0$ si $v>0$ et $f\left(0\right)=-1$ .

Pour prouver l’inégalité (10) il suffit de montrer que $R\left(a\right)\leq R\left(c\right)=0$ et $R\left(b\right)\geq R\left(c\right)=0$ . En effet, on a:

	$\displaystyle R\left(a\right)=$	$\displaystyle a^{k}-\alpha_{i_{1}}a^{k-1}-\ldots-\alpha_{i_{k-1}}a-\alpha_{i_{% k}}$
	$\displaystyle=$	$\displaystyle\left(\alpha_{1}-\alpha_{i_{1}}\right)a^{k-1}+\left(\alpha_{2}-% \alpha_{i_{2}}\right)a^{k-2}+\ldots+\alpha_{k}-\alpha_{i_{k}}$
	$\displaystyle=$	$\displaystyle\left(a-1\right)\left(\alpha_{1}-\alpha_{i_{1}}\right)a^{k-2}+% \left(\alpha_{1}+\alpha_{2}-\alpha_{i_{1}}-\alpha_{i_{2}}\right)a^{k-3}+\ldots+$
		$\displaystyle+\left(\alpha_{1}+\alpha_{2}+\ldots+\alpha_{k-2}-\alpha_{i_{1}}-% \alpha_{i_{2}}-\ldots-\alpha_{i_{k-2}}\right)a+$
		$\displaystyle+\left(\alpha_{1}+\alpha_{2}+\ldots+\alpha_{k-1}-\alpha_{i_{1}}-% \alpha_{i_{2}}-\ldots-\alpha_{i_{k-1}}\right)\leq 0,$

parce que $0<a<1$ et de (6) il résulte que

\alpha_{1}+\alpha_{2}+\ldots+\alpha_{s}-\alpha_{i_{1}}-\alpha_{i_{2}}-\ldots-% \alpha_{i_{s}}\geq 0;

pour chaque $s=1,2,\ldots,k-1$ .

De manière analogue on montre que $R\left(b\right)\geq 0,\ Q.E.D.$

Maintenant, nous rangeons les coefficients $a_{i}$ de (5) en ordre décroissant, c’est-à-dire:

(11)

a_{i_{1}}\geq a_{i_{2}}\geq\ldots\geq a_{i_{k}}\geq 0,

et nous écrivons

(11^′)

\alpha_{s}=a_{i_{s}},\ s=1,2,\ldots,k.

Nous considérons l’application $G:X^{k}\rightarrow X$ , donnée par la relation

(12)

G\left(u_{1},u_{2},\ldots,u_{k}\right)=F\left(u_{i_{1}},u_{i_{2}},\ldots,u_{i_% {k}}\right),

où $i_{1},i_{2},\ldots,i_{k}$ est la permutation des nombres $1,2,\ldots,k$ qui correspond à la relation (11). On obtient alors de (5), pour $G$ , la condition

(13)

\displaystyle\rho\big{(}G\left(u_{1},u_{2},\ldots,u_{k}\right),G\left(v_{1},v_% {2},\ldots,v_{k}\right)\big{)}\leq\left(\sum_{i=1}^{k}\alpha_{i}\rho\left(u_{i% },v_{i}\right)^{\beta}\right)^{\frac{1}{\beta}},

quels que soient les éléments $u_{1},u_{2},\ldots,u_{k},\ v_{1},v_{2},\ldots,v_{k}\in X,$ où

\alpha_{1}\geq\alpha_{2}\geq\ldots\geq\alpha_{k}\geq 0,\ \beta>0.......0<\sum_% {i=1}^{k}\alpha_{i}<1.

Pour résoudre l’équation (1) nous considerons la méthode itérative suivante:

(14)

x_{n+1}=G\left(x_{n},x_{n-1},\ldots,x_{n-k+1}\right),\ n=k-1,k\ldots,

où $x_{0},x_{1},\ldots,x_{k-1}\in X$ .

Si nous écrivons $q_{i}=\rho\left(x_{i},x_{i+1}\right),\ i=0,1,\ldots$ , alors de (13) et (14) on obtient

(15)

q_{i}=\left(\sum_{s=1}^{k}\alpha_{s}q_{i-s}^{\beta}\right)^{\frac{1}{\beta}},% \ i=k,k+1,\ldots\ .

Si dans l’équation (7) $\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$ sont données par (11^′) et si $a$ est la racine positive de l’équation (7), alors $a^{\frac{1}{\beta}}\in\left(0,1\right)$ .

Soit $C$ une constante positive telle que:

q_{s}\leq Ca^{s/\beta}\text{ pour}\ s=0,1,\ldots,k-1.

De (15) on obtient:

	$\displaystyle q_{i}$	$\displaystyle\leq\left(\sum_{s=1}^{k}\alpha_{s}q_{i-s}^{\beta}\right)^{\frac{1% }{\beta}}\leq\left(C\ \sum_{s=1}^{k}\alpha_{s}a^{i-s}\right)^{\frac{i}{\beta}}$
		$\displaystyle=C\ a^{\left(i-k\right)/\beta}\left(\sum_{s=1}^{k}\alpha_{s}a^{k-% s}\right)^{\frac{1}{\beta}}=C\ a^{\left(i-k\right)/\beta}a^{k/\beta}=C\ a^{i/% \beta},$

$i=k,k+1,\ldots,$ . Puisque $a^{1/\beta}\in\left(0,1\right)$ il résulte que la suite $\left(x_{n}\right)_{n=0}^{\infty}$ est fondamentale. Désignons par $\bar{x}$ sa limite. Il est évident que $\bar{x}$ est l’unique solution de l’équation (1) et

(16)

\rho\left(\bar{x},x_{n}\right)\leq\tfrac{C\ a^{n/\beta}}{1-a^{1/\beta}}.

∎

Alors, en utilisant le lemma on obtient le théorème suivante:

THÉORÈME.

Supposons que $F\in\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)$ et que l’on donne les $k!$ méthodes itératives de la forme (4), attachées à $F$ .

La méthode itérative pour laquelle on obtient la meilleure délimitation de l’erreur est celle donnée par (14), avec $G$ définie par (12) et qui corresponds à l’ordre décreoissante de la suite des coefficients $a_{i},\ i=1,2,\ldots,k,$ de (5).

Remarques.

1) Parce que, de la $F\in\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)$ il résulte que $\varphi$ est une contraction, avec la constante de Lipschitz $\left(\sum_{i=1}^{k}a_{i}\right)^{1/\beta}$ , il est clair que la méthode itérative

(17)

x_{n+1}=\varphi\left(x_{n}\right),\ x_{0}\in X,\ n=0,1,\ldots\

converge vers la solution $\bar{x}$ de l’équation (1). De plus, nous avons

(18)

\rho\left(\bar{x},x_{n}\right)\leq C_{1}\frac{\left(\sum\limits_{i=1}^{k}a_{i}% \right)^{n/\beta}}{1-\left(\sum\limits_{i=1}^{k}a_{i}\right)^{1/\beta}}.

Nous démontrerons que $\sum_{i=1}^{k}a_{i}\leq a$ , où a est la solution de l’équation (7), avec $\alpha_{s},\ s=1,2,\ldots,k$ données par la formule (11^′).

On a:

		$\displaystyle P\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}=$
		$\displaystyle=\!\!\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}\!\!-% \!\alpha_{1}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}\!\!-\!% \alpha_{2}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-2}\!\!-\ldots-% \!\alpha_{k-1}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}-\alpha_{k}$
		$\displaystyle\leq\!\!\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}\!% \!-\!\alpha_{i}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}\!\!-\!% \alpha_{2}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}\!\!-\!% \ldots\!-\!\alpha_{k-1}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1% }\!\!-\!\alpha_{k}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}$
		$\displaystyle=\!\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}\!\!-\!% \Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}=0,$

d’où il résulte que $\sum_{i=1}^{k}a_{i}\leq a$ .

Soit maintenant $F\in\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)\$ et $\ \varphi\left(x\right)=F\left(x,x,\ldots,x\right)$ . Les formules (16) et (18) valables pour une métrique quelconque et pour chaque paire $\left(F,\varphi\right),$ avec les propriétés ci-dessus, nous montrent que pour la méthode itérative (17) on obtient une délimitation de l’erreur meilleure que dans le cas des autres méthodes de la forme (4). Ceci ne signifie pas que pour chaque choix des points initiaux et chaque aplciation $F,$ la méthode (17) converge plus vite que toutes les méthodes itératives de la forme (4).

Soit, par example, $\ X=\mathbb{R}$ , $\rho=\left|\cdot\right|,\ \varphi\left(x\right)=\frac{1}{4}\sin x,$ $F\left(x,y\right)=\frac{1}{2}\sin\frac{x}{2}\cos\frac{y}{2}$ . On a

\big{|}F\left(x_{1},y_{1}\right)-F\left(x_{2},y_{2}\right)\big{|}\leq\tfrac{1}% {4}\left|x_{1}-x_{2}\right|+\tfrac{1}{4}\left|y_{1}-y_{2}\right|,

pour chaque $x_{1},x_{2},y_{1},y_{2}\in\mathbb{R}$ ; $F\in\mathcal{F}_{1}\left(\tfrac{1}{4},\tfrac{1}{4}\right)\$ et $\ F\left(x,x\right)=\varphi\left(x\right)$ .

On considère les méthodes itératives suivantes:

(19)

x_{n+1}=\tfrac{1}{4}\sin x_{n},\ n=0,1,\ldots,\ \ x_{0}=\tfrac{\pi}{2},

(20)

x_{n+2}=\tfrac{1}{2}\sin\tfrac{x_{n+1}}{2}\cos\tfrac{x_{n}}{2},\ n=0,1,\ldots,% \ x_{0}=\tfrac{\pi}{2},\ x_{1}=0,

(21)

x_{n+2}=\tfrac{1}{2}\cos\tfrac{x_{n+1}}{2}\sin\tfrac{x_{n}}{2},\ n=0,1,\ldots,% \ \ x_{0}=\tfrac{\pi}{2},\ x_{1}=0.

Dans ce cas la suite (20) converge plus vite que la suite (19) où la suite (21).

2) Il existe des méthodes itératives de la forme (4) respectivement (17), pour lesquelles les délimitations (16) respectivement (18) ne peuvent pas s’améliorer, c’est-a-dire:

\overline{\lim_{n\rightarrow\infty}}\rho\left(\bar{x},x_{n}\right)^{1/n}=a^{1/% \beta},

respectivement

\overline{\lim_{n\rightarrow\infty}}\rho\left(\bar{x},x_{n}\right)^{1/n}=\left% (\sum_{i=1}^{k}a_{i}\right)^{1/\beta}.

Exemple.

Soit $X=\mathbb{R},\rho=\left|\cdot\right|,\ \varphi\left(x\right)=\tfrac{5}{6}x,$

	$\displaystyle\ F\left(x,y\right)$	$\displaystyle=\tfrac{1}{2}x+\tfrac{1}{3}y,$
	$\displaystyle F\left(x,x\right)$	$\displaystyle=\varphi\left(x\right),\$
	$\displaystyle\left\|F\left(x_{1},y_{1}\right)-F\left(x_{2},y_{2}\right)\right\|$	$\displaystyle\leq\tfrac{1}{2}\left\|x_{1}-x_{2}\right\|+\tfrac{1}{3}\left\|y_{1}-% y_{2}\right\|,\ \beta=1.$

Soit

(22)

x_{n+1}=\tfrac{5}{6}x_{n},\ n=0,1,\ldots\ ,\ x_{0}=1.

(23)

x_{n+2}=\tfrac{1}{2}x_{n+1}+\tfrac{1}{3}x_{n},\ n=0,1,\ldots\ ,\ x_{0}=1,\ x_{% 1}=1.

(24)

x_{n+2}=\tfrac{1}{3}x_{n+1}+\tfrac{1}{2}x_{n},\ n=0,1,\ldots\ \ <x_{0}=1,\ x_{% 1}=1.

Dans ce cas on obtient respectivement les formules:

(22^′)

\lim_{n\rightarrow\infty}(x_{n})^{\tfrac{1}{n}}=\tfrac{5}{6}=\tfrac{1}{2}+% \tfrac{1}{3},

(23^′)

\lim_{n\rightarrow\infty}x_{n}^{1/n}=a,

où a est la racine positive de l’équation $x^{2}-\tfrac{1}{2}x-\tfrac{1}{3}=0$ , c’est-à-dire $a=\frac{3+\sqrt{57}}{12}$ . De la même manière on obtient

(24^′)

\lim_{n\rightarrow\infty}x_{n}^{1/n}=b,

ou $b$ est la racine positive de l’équation caractéristique $x^{2}-\frac{1}{3}x-\tfrac{1}{2}=0\$ c’est-à-dire $b=\frac{1+\sqrt{19}}{6}$ . Il est clair que $\ \frac{5}{6}<\frac{3+\sqrt{57}}{12}<\frac{1+\sqrt{19}}{6}.$

Bibliographie

[1] I. Păvăloiu, ^†^†margin: $\leftarrow$ clickable
$\leftarrow$ clickable Introducere în teoria aproximării soluţiilor ecuaţiilor, Ed. Dacia, Cluj-Napoca, 1976.
[2] I. Păvăloiu, Rezolvarea ecuaţiilor prin interpolare, Ed. Dacia, Cluj-Napoca, 1981.
[3] Weinischke, J. H., Uber eine Klasse von Iterationsverfahren, Num. Math., 6 (1964), 395–404.

On optimal iterative methods

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

References

Paper (preprint) in HTML form