Sur Quelques Méthodes itératives de type Interpolatoire à vitesse de Convergence Optimale

par
I. Păvăloiu et Ioan Şerb
(Cluj-Napoca)

Dans cet article nous étudions une classe de méthodes iteŕatives pour la résolution des équations de la forme:

(1)

f\left(x\right)=0,

où $f:I\rightarrow\mathbb{R}$ est une fonction réelle d’une variable réelle et $I$ est un invervalle de l’axe réel.

Désignons par $x_{1},x_{2},\ldots,x_{n+1},\ n+1$ points distincts de l’intervalle $I$ et par $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1},\ n+1$ nombres naturels tels que:

(2)

\alpha_{1}+\alpha_{2}+\ldots+\alpha_{n+1}=m+1,

où $m\in\mathbb{N}$ .

Il est bien connu que quels que soiient les nombres $y_{i}^{j},\ j=0,\ 1,\ldots,\alpha_{i}-1,$ $i=1,2,\ldots,n+1,$ il existe un seul polynôme $H_{1}$ de degré au plus $m$ qui vérifie les conditions:

(3)

H_{1}^{\left(j\right)}\left(x_{i}\right)=y_{i}^{j},\ j=0,1,\ldots,\alpha_{i}-1% ,\ i=1,2,\ldots,n+1.

Le polynôme $H_{1}\$ déterminé par les conditions (3) a la forme:

(4)

H_{1}\left(x\right)=\sum_{i=1}^{n+1}\sum_{j=0}^{\alpha_{i}-1}\sum_{k=0}^{% \alpha_{i}-j-1}y_{i}^{j}\tfrac{1}{k!j!}\left[\tfrac{\left(x-x_{i}\right)^{% \alpha_{i}}}{\omega\left(x\right)}\right]_{x=x_{i}}^{\left(k\right)}\tfrac{% \omega\left(x\right)}{\left(x-x_{i}\right)^{\alpha_{i}-j-k}},

où

(5)

\omega\left(x\right)={\textstyle\prod\limits_{i=1}^{n+1}}\left(x-x_{i}\right)^% {\alpha_{i}}.

Si on suppose que la fonction $f$ admet une dérivée d’ordre $m+1$ sur l’intervalle $I$ et si $y_{i}^{j}=f^{\left(j\right)}\left(x_{i}\right),\ j=0,1,\ldots,\alpha_{i}-1,\ i% =1,2,\ldots,n+1,$ alors $H_{1}$ , le polynôme d’Hermite de la fonction $f$ , relativement aux noeuds $x_{i},$ aux ordres de mutiplicité $\alpha_{i}$ , vérifie l’égalité:

(6)

f\left(x\right)-H_{1}\left(x\right)=\tfrac{f^{\left(m+1\right)}\left(\xi\right% )}{\left(m+1\right)!}\omega\left(x\right),

où $\xi\in I$ .

Dans ce qui suit on suppose que $f^{\prime}\left(x\right)\neq 0$ quelque soit $x\in I$ et on désigne par $F=f\left(I\right)$ . Il résulte que $f:I\rightarrow F$ est une fonction bijective et il existe $f^{-1}:F\rightarrow I$ . La fonction inverse $f^{-1}$ admet une dérivée d’ordre $m+1,$ pour tout $x\in F.$

La dérivée d’ordre $k,k\leq m+1$ sur un point $y_{0}=f\left(x_{0}\right),\ y_{0}\in F$ peut se calculer par la formule:

(7)

\left(f^{-1}\right)^{\left(k\right)}\left(y_{0}\right)=\sum\tfrac{\left(2k-i_{% 1}-2\right)!\left(1-\right)^{k+i_{1}-1}}{i_{2}!\ldots i_{k}!\left(f^{\prime}% \left(x_{0}\right)\right)^{2k-1}}\big{(}\tfrac{f^{\prime}\left(x_{0}\right)}{1% !}\big{)}^{i_{1}}\big{(}\tfrac{f^{\prime\prime}\left(x_{0}\right)}{2!}\big{)}^% {i_{2}}\ldots\big{(}\tfrac{f^{\left(k\right)}\left(x_{0}\right)}{k!}\big{)}^{i% _{k}},

où la somme ci-dessus est étendue à toutes les solutions entières et nonnégatives du système:

(8)

\left\{\begin{array}[c]{c}i_{2}+2i_{3}+\ldots+\left(k-1\right)i_{k}=k-1\\ i_{1}+i_{2}+\ldots+i_{k}=k-1.\end{array}\right.

Si on suppose que l’équation (1) a une racine dans l’intervalle $I$ , cette racine est unique parce que $f^{\prime}\left(x\right)\neq 0$ quel que soit $x\in I$ et nous la désignerons par $\bar{x}$ . Alors de $f\left(\bar{x}\right)=0$ il résulte que $\bar{x}=f^{-1}\left(0\right).$

Dans ce qui suit, dans l’expression du polynôme d’interpolation donnée par (4) on prendra comme noeuds d’interpolation les valeurs $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots,n+1$ et comme valeurs $y_{i}^{j}$ les valeurs des dérivées $\left(f^{-1}\right)^{\left(j\right)}\left(y_{i}\right),\ i=1,2,\ldots,n=1,\ j=% 0,1,\ldots,$ $\alpha_{i}-1$ . Par conséquent on obtient le polynôme d’interpolation d’Hermite pour la fonction inverse $f^{-1}$ . Ce polynôme a alors la forme suivante:

(9)

H\left(y\right)=\sum_{i=1}^{n+1}\sum_{j=0}^{\alpha_{i}-1}\sum_{k=0}^{\alpha_{i% }-j-1}\left(f^{-1}\right)^{\left(j\right)}\left(y_{i}\right)\tfrac{1}{k!j!}% \left[\tfrac{\left(y-y_{i}\right)^{\alpha_{i}}}{\omega\left(y\right)}\right]_{% y=y_{i}}^{\left(k\right)}\tfrac{\omega\left(y\right)}{\left(y-y_{i}\right)^{% \alpha_{i}-j-k}},

où

(10)

\omega\left(y\right)={\textstyle\prod\limits_{i=1}^{n+1}}\left(y-y_{i}\right)^% {\alpha_{i}}.

De (6) il résulte l’égalité

f^{-1}\left(y\right)-H\left(y\right)=\tfrac{\left(f^{-1}\right)^{\left(m+1% \right)}\left(\eta\right)}{\left(m+1\right)!}\omega\left(y\right),

où $\eta\in F$ .

Si $y=0$ , alors $\bar{x}=f^{-1}\left(0\right)$ et

(11)

\bar{x}-H\left(0\right)=\tfrac{\left(f^{-1}\right)^{\left(m+1\right)}\left(% \eta_{1}\right)}{\left(m+1\right)!}\omega\left(0\right),

où $\eta_{1}est$ un point du plus petit intervalle contenant les points:

0,f\left(x_{1}\right),\ldots,f\left(x_{n+1}\right).

Si on désigne par $F_{1}$ cet intervalle et par

M_{m+1}=\sup_{y\in F_{1}}\left|\left(f^{-1}\right)^{\left(m+1\right)}\left(y% \right)\right|,

alors

\left|\bar{x}-H\left(0\right)\right|\leq\tfrac{M_{m+1}}{\left(m+1\right)!}% \left|\omega\left(0\right)\right|.

De (10) et du fait que $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots,n+1$ on déduit

(12)

\left|\bar{x}-H\left(0\right)\right|\leq\tfrac{M_{m+1}}{\left(m+1\right)!}% \left|f\left(x_{1}\right)\right|^{\alpha_{1}}\cdot\left|f\left(x_{2}\right)% \right|^{\alpha_{2}}\ldots\left|f\left(x_{n+1}\right)\right|^{\alpha_{n+1}}.

De l’inégalité (12) il résulte que si $x_{1},x_{2},\ldots,x_{n+1}$ sont dans un voisinage suffisamment petit de $\bar{x}$ , alors $\prod\nolimits_{i=1}^{n+1}\left|f\left(x_{i}\right)\right|^{\alpha_{i}}$ se trouvera dans un voisinage donné d’avance de $0 .$ En conséquence, nous pouvons supposer que $H\left(0\right)$ est un approximant de la racine $\bar{x}$ de l’équation (1).

Si $\left|\bar{x}-H\left(0\right)\right|$ n’est pas suffisamment petit, alors, par des itérations successives on peut obtenir des approximations meilleures. Désignons par $x_{1},x_{2},\ldots,x_{n+1},$ $n+1$ approximations initiales de la racine $\bar{x}$ de (1). Soit $x_{n+2}=H\left(0\right)=H\left(y_{1},\alpha_{1};\ldots;y_{n+1},\alpha_{n+1};0% \right),$ où $H(y_{1},\alpha_{1};y_{2},\alpha_{2};\ldots;$ $y_{n+1},\alpha_{n+1};y)$ est le polynôme d’interpolation d’Hermite (9) de la fonction $f^{-1}$ relatif aux noeuds $y_{1},y_{2},\ldots,y_{n+1}$ aux ordres de multiplicité respectifs $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ et $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots,n+1$ . Si nous considérons maintenant le nouveau système de noeuds $x_{2},x_{3},\ldots,x_{n+1},x_{n+2}$ an obtient une nouvelle approximation $x_{n+3}=H\left(y_{2},\alpha_{1};y_{3},\alpha_{2};\ldots;y_{n+2},\alpha_{n+1};0\right)$ et ainsi de suite.

Mais, si nous rangeons les noeuds $x_{1},x_{2},\ldots,x_{n+1}$ dans l’ordre $x_{i_{1}},x_{i_{2}},\ldots,$ $x_{i_{n+1}}$ on obtient une nouvelle suite d’approximations de $\bar{x}$ , donnée par les formules

(13)

\left\{\begin{array}[c]{l}\!\!x_{n+2}\!=\!H\left(y_{i_{1}},\alpha_{i_{1}};y_{i% _{2}},\alpha_{i_{2}};\ldots;y_{i_{n+1}};\alpha_{i_{n+1}};0\right)=H\left(0% \right)\\ \!\!x_{n+s+2}\!=\!H\left(y_{i_{s+1}},\alpha_{i_{1}};\ldots;y_{i_{n+1}},\alpha_% {{}_{n+1-s}};y_{n+2},\alpha_{i_{n+2-s}};\ldots;y_{n+s+1},\alpha_{i_{n+1}};0% \right),\\ \qquad\qquad s=1,2,\ldots,n,\\ \!\!x_{n+s+2}\!=\!H\left(y_{s+1},\alpha_{i_{1}};y_{s+2},\alpha_{i_{2}};\ldots;% y_{n+s+1},\alpha_{i_{n+1}};0\right),\ s=n+1,n+2,\ldots\end{array}\right.

où $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots$

Pour chaque permutation des nombres $1,2,\ldots,n+1$ on obtient une suite d’approximations de $\bar{x}$ donnée par (13). En tout, il $y$ a $\left(n+1\right)!$ suites d’approximations de $\bar{x}$ .

On pose la question de choisir parmi ces $\left(n+1\right)!$ suites, celle qui assure la vitesse de convergence maximale.

Pour résoudre ce problème, on considère les équations suivantes

(14)	$\displaystyle P\left(t\right)=$	$\displaystyle t^{n+1}-a_{n+1}t^{n}-a_{n}t^{n-1}-\ldots-a_{2}t-a_{1}=0,$
(15)	$\displaystyle Q\left(t\right)=$	$\displaystyle t^{n+1}-a_{1}t^{n}-a_{2}t^{n-1}-\ldots-a_{n}t-a_{n+1}=0,$
(16)	$\displaystyle R\left(t\right)=$	$\displaystyle t^{n+1}-a_{i_{1}}t^{n}-\ldots-a_{i_{n}}t-a_{i_{n+1}}=0,$

où $a_{1},a_{2},\ldots,a_{n+1}\in R$ vérifient les relations

(17)		$\displaystyle a_{1}+a_{2}+\ldots+a_{n+1}>$	$\displaystyle 1,\ a_{i}\geq 0,\qquad i=1,2,\ldots,n+1,$
(18)		$\displaystyle a_{n+1}\geq$	$\displaystyle a_{n}\geq\ldots\geq a_{2}\geq a_{1},$

et $i_{1},i_{2},\ldots,i_{n+1}$ est une permutation quelconque de $1,2,\ldots,n+1.$

Lemme 1.

Si $a_{1},a_{2},\ldots,a_{n+1}$ vérifient la relation (17), alors chaque équation de la forme (16) a une seule racine plus grande que l’unité. Si, de plus, $a_{1},a_{2},\ldots,a_{n+1}$ vérifient la condition (18) et si $a, b, c$ sont respectivement les racine positives des équaitons (14), (15) ou (16), alors on a les inégalités

(19)

1<b\leq c\leq a

Démonstration..

On désigne par $s$ le plus grand nombre pour lequel $a_{i_{s}}\neq 0$ . Alors $a_{i_{s+1}}=a_{i_{s+2}}=\ldots=a_{i_{n}}=a_{i_{n+1}}=0,\ a_{i_{s}}\neq 0$ . Désignons par $\psi$ la fonction définie par $\psi\left(t\right)=R\left(t\right)/t^{n-s+1}$ . On a $\psi\left(1\right)=1-a_{i_{1}}-\ldots-a_{i_{s}}<0$ et $\lim\limits_{t\rightarrow\infty}\psi\left(t\right)=\infty,$ donc l’équation $\psi\left(t\right)=0$ admet une racine plus grande que l’unité. Alors, l’équation $R\left(t\right)=0$ a une racine plus grande que 1. L’unicité de cette racine résulte immédiatement en considérant la fonction $f\left(t\right)=-t^{n+1}R\left(1\backslash t\right)$ qui vérifie la condition $f^{\prime}\left(t\right)>0$ pour $t>0$ .

Pour prouver les inégalites (19) il suffit de montrer que $R\left(b\right)\leq 0$ et $R\left(a\right)\geq 0$ . En effet

	$\displaystyle R\left(b\right)=$	$\displaystyle R\left(b\right)-Q\left(b\right)$
	$\displaystyle=$	$\displaystyle\left(a_{1}-a_{i_{1}}\right)b^{n}+\left(a_{2}-a_{i_{2}}\right)b^{% n-1}+\ldots+\left(a_{n}-a_{i_{n}}\right)b+a_{n+1}-a_{i_{n+1}}$
	$\displaystyle=$	$\displaystyle\left(b-1\right)\big{[}\left(a_{1}-a_{i_{1}}\right)b^{n-1}+\left(% a_{1}+a_{2}-a_{i_{1}}-a_{i_{2}}\right)b^{n-2}+\ldots$
		$\displaystyle+(a_{1}+a_{2}+\ldots+a_{n-1}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{n-1% }})b$
		$\displaystyle+a_{1}+\ldots+a_{n}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{n}}\big{]}\leq 0$

parce que $b>1$ et de (18) il résulte

a_{1}+a_{2}+\ldots+a_{s}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{s}}\leq 0,\qquad% \text{pour\ }s=1,2,\ldots,n.

De manière analogue on montre que $R\left(a\right)\geq 0.$

Soit maintenant $i_{1},i_{2},\ldots,i_{n+1}$ une permutation des nombres $1,2,\ldots,n+1,$ pour laquelle les nombres naturels $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ qui vérifient la relation (2) peuvent se ranger en ordre croissant

(20)

\alpha_{i_{1}}\leq\alpha_{i_{2}}\leq\ldots\leq\alpha_{i_{n}}\leq\alpha_{i_{n+1% }}.

Le suite correspondante des noeuds est $x_{i_{1}},x_{i_{2}},\ldots,x_{i_{n+1}}$ et la suite correspondante des approximations successive de $\bar{x}$ est donnée par (13). Si nous désignons par

(21)

a_{s}=\alpha_{i_{s}},s=1,2,\ldots,n+1

et par

(22)

u_{s}=x_{i_{s}},s=1,2,\ldots,n+1,

alors la suite d’approximations (13) devient $\left(u_{n}\right)_{n=1}^{\infty}$ où

(23)

x_{n+s+2}=H\left(y_{s+1},a_{1};y_{s+2},a_{2};\ldots;y_{s+n+1},a_{n+1};0\right),

$s=0,1,\ldots,$ où $y_{i}=f\left(u_{i}\right),\ i=1,2,\ldots\ .$

L’inégalité (12) devient

(24)

\left|\bar{x}-H\left(0\right)\right|=\left|\bar{x}-u_{n+2}\right|\leq\tfrac{M}% {\left(m+1\right)!}\left|f\left(u_{1}\right)\right|^{a_{1}}\ldots\left|f\left(% u_{n+1}\right)\right|^{a_{n+1}},

où $M=\sup\limits_{y\in F}\left|\left(f^{-1}\right)^{\left(m+1\right)}\left(y% \right)\right|$ . Si nous désignons par $\beta=\sup\limits_{x\in I}\left|f^{\prime}\left(x\right)\right|$ alors de (23) et (24) on obtient

(25)

\left|\bar{x}-u_{n+2}\right|\leq\tfrac{M\beta^{m+1}}{\left(m+1\right)!}\left|% \bar{x}-u_{1}\right|^{a_{1}}\ldots\left|\bar{x}-u_{n+1}\right|^{a_{n+1}}.

En général, is les éléments de la suite $\left(u_{n}\right)_{n=1}^{\infty}$ sont dans l’intervalle $I$ , alors

(26)

\left|\bar{x}-u_{n+s+1}\right|\leq\tfrac{M\beta^{m+1}}{\left(m+1\right)!}\left% |\bar{x}-u_{s}\right|^{a_{1}}\ldots\left|\bar{x}-u_{s+n}\right|^{a_{n+1}}

$s=1,2,\ldots$ . Si nous écrivons $\rho_{i}=\beta\sqrt{\tfrac{\beta M}{\left(m+1\right)!}}\left|\bar{x}-u_{i}% \right|,i=1,2,\ldots,$ alors de (26) on obtient

(27)

\rho_{n+s+1}\leq\rho_{n+s}^{a_{n+1}}\rho_{n+s-1}^{a_{n}}\ldots\rho_{s+1}^{a_{2% }}\rho_{s}^{a_{1}},

$s=1,2,\ldots$ .

Nous supposons maintenant qu’il existe un nombre $d,0<d<1$ tel que

(28)

\rho_{i}\leq d^{\omega^{i}},\qquad i=1,2,\ldots,n+1,

où $\omega$ est l’unique racine positive de l’équation

(29)

t^{n+1}-a_{n+1}t^{n}-a_{n}t^{n-1}-\ldots-a_{2}t-a_{1}=0.

Si on suppose que pour un $s$ fixé $s\geq 2$ nous avons

(30)

\rho_{n+s}\leq d^{x+s},

alors de (27), (28) et (29) il résulte immédiatement que

(31)		$\displaystyle\rho_{n+s+1}$	$\displaystyle\leq d^{a_{n+1}\omega^{n+s}}\cdot d^{a_{n}\omega^{n+s-1}}\ldots d% ^{a_{2}\omega^{s+1}}\cdot d^{a_{1}\omega^{s}}$
		$\displaystyle=d^{a_{n+1}\omega^{n+s}+a_{n}\omega^{n+s-1}+\ldots+a_{2}\omega^{s% +1}+a_{1}\omega^{s}}=d^{\omega^{n+s+1}},$

et par induction il résulte que

(32)

\rho_{n}\leq d^{\omega^{n}},n=1,2,\ldots

La solution $\omega$ de l’équation (29) s’appelle l’ordre de convergence de la méthode itérative (23). On a

(33)

\left|\bar{x}-u_{n}\right|\leq\tfrac{1}{\beta\sqrt[m]{\frac{M\beta}{\left(m+1% \right)!}}}d^{\omega^{n}},n=1,2,\ldots,

d’où il résulte que $\lim\limits_{n\rightarrow\infty}u_{n}=\bar{x}$ . ∎

On remarque que l’ordre de convergence des méthodes (13) dépend de la racine positive $\omega$ de l’equation (29).

En tenant compte du lemme et des considérations ci-dessus on obtient le théorème suivant:

Théorème 1.

Soit $i_{1},i_{2},\ldots,i_{n+1}$ une permutation de $1,2,\ldots,n+1$ et $M\left(i_{1},i_{2},\ldots,i_{n+1}\right)$ la méthode itérative (13) correspondante. Si $\alpha_{i_{1}}\leq\alpha_{i_{2}}\leq\ldots\leq\alpha_{i_{n+1}}$ où $\alpha_{i_{j}}est$ l’ordre de multiplicité du noeud $y_{i_{j}}=f(x_{i_{j}}),$ $j=1,2,\ldots,n+1,$ alors dans les conditions (20) méthode (23) assure l’ordre de convergence $\omega$ maximal, parmi les $\left(n+1\right)!$ méthodes itératives de la forme (13).

Bibliographie

[1]
[2] Ostrowski, M. A., Solution of Equations and Systems of Equations, Academic Press, New-York and London, 1960.
[3] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Rezolvarea ecuaţiilor prin interpolare, Ed. Dacia, 1981.
[4] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Iancu, C., La résolution des équations par interpolation inverse de type Hermite, Seminar of functional analysis and Numerical methods, ”Babeş-Bolyai” University, Research Seminaries, Preprint Nr. 4, (1981), 72–84.
republished in: Mathematica (Cluj), 26(49) (1984), no. 2, pp. 115–123.

Recu le 5.III.1983

Institutul de Calcul al Universităţii Babeş-Bolyai

Str. Republicii 37

3400 Cluj-Napoca

On some interpolation iterative methods with optimal convergence speed

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Paper on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Sur Quelques Méthodes itératives de type Interpolatoire à vitesse de Convergence Optimale

Lemme 1.

Démonstration..

Théorème 1.

Bibliographie

Related Posts