La résolution des équations par interpolation

par
Ion Păvăloiu

1. La notation de diffèrence divisée.

Soient $X$ et $Y$ deux espaces lineaires normés et $G:X\rightarrow Y$ une application. Nous considérons $n+1$ éléments distincts de l’espace $X$

(1)

x_{1},x_{2},\ldots,x_{n+1}.

Nous désignons par $L\left(X,Y\right)$ l’ensemble des applicatons linéaires et continues définies sur $X$ et à valeurs en $Y$ et nous déffinisons par récurrence les ensembles suivants:

L_{i}\left(X,Y\right)=L\left(X,L_{i-1}\left(X,Y\right)\right),\ \;\;i=2,3,\ldots

où

L_{1}\left(X,Y\right)=L\left(X,Y\right).

Autrement dit les ensembles $L_{i}\left(X,Y\right)$ sont les espaces des applications $i$ -linéaires et continues définies sur $X$ et à valeurs en $Y .$

Définition 1.

L’application $\left[.,.;G\right]:X^{2}\rightarrow L\left(X,Y\right)$ s’appelle difference divisée d’ordre un de l’approximation $G$ sur les points $x_{i},x_{j}$ du système (1) si

1)

$\left[x_{i},x_{j};G\right]\left(x_{j}-x_{i}\right)=G\left(x_{j}\right)-G\left(% x_{i}\right)$
2)

s’il existe la dérivée au sens de Fréchet de l’application $G$ sur le point $x_{i},$ alors $\left[x_{i},x_{i};G\right]=G^{\prime}\left(x_{i}\right).$

Nous avons défini ci-dessus la différence divisée d’ordre un de l’application $G$ sur deux éléments arbitraires du système (1).

En considérant maintenant des points consècutifs du système (1) nous pouvons considérer les différences divisées suivantes:

\left[x_{1},x_{2};G\right],\left[x_{2},x_{3};G\right],\ldots,\left[x_{n},x_{n+% 1};G\right].

A l’aide des différences divisées définies ci-dessus nous définissons la notion de différence divisée d’ordre $n$ $\left(n>1\right)$ de l’application $G .$

Nous supposons que nous avons défini l’application $\left[\cdot,\cdot,\ldots,\cdot;G\right]:X^{i+1}\rightarrow L_{i}\left(X,Y\right)$ à l’aide de laquelle nous pouvons définir les différences divisées d’ordre $\ i$ de l’application $G$ sur $i+1$ éléments quelconques du système (1).

Soient $\left[x_{k+1},x_{k+2},\ldots,x_{k+i+1};G\right]$ et $\left[x_{k},x_{k+1},\ldots,x_{k+i};G\right]$ deux différences divisées d’ordre $i$ sur les points $x_{k+1},x_{k+2},\ldots,x_{k+i+1}$ respectivement $x_{k},x_{k+1},\ldots,x_{k+1}$ du système (1).

Définition 2.

L’application $\left[\cdot,\cdot,\ldots,\cdot;G\right]:X^{i+2}\rightarrow L_{i+1}\left(X,Y\right)$ s’appelle différence divisée d’ordre $i+1$ de l’application $G$ sur les points $x_{k},x_{k+1},\ldots,x_{k+i+1},$ si

1)

$\displaystyle\left[x_{k},\ldots,x_{k+i+1};G\right]\left(x_{k+i+1}-x_{k}\right)=$

$\displaystyle=\left[x_{k+1},\ldots,x_{k+i+1};G\right]-\left[x_{k},\ldots,x_{k+% i};G\right]$
2)

s’il existe la dérivée au sens de Fréchet d’ordre $i+1$ de l’application $G$ sur le point $x_{i},$ alors:

$\left[x_{s},x_{s},\ldots,x_{s};G\right]=\tfrac{1}{\left(i+1\right)!}G^{\left(i% +1\right)}\left(x_{s}\right).$

Pour pouvoir utiliser ces différences divisées à la construction des polynomes d’interpolation il est néccessaire d’introduire la notion de différence divisée symétrique par rapport aux points considérés.

Définition 3.

La différence divisée $\left[x_{1},x_{2},\ldots,x_{k};G\right]$ où $x_{1},x_{2},\ldots,x_{k}$ sont des points du système (1) est dite symétrique par raport à les points, si on a:

(2)

\left[x_{1},x_{2},\ldots,x_{k};G\right]=\left[x_{i_{1}},x_{i_{2}},\ldots,x_{i_% {k}};G\right]

pour chaque permutation $\left(i_{1},i_{2},\ldots,i_{k}\right)$ des nombres $\left(1,2,3,\ldots,k\right).$

Si $X=Y=\mathbb{R}$ alors, l’égalité (2) est toujours vérifiée. Alors les différences divisées des fonctions réelles d’une variable réelle sont symétrique par rapport aux points considérés.

Si nous supposons maintenant par example $X=\mathbb{R}^{2}$ et $Y=\mathbb{R},$ $f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ et si nous désignons par $\left(u^{\prime},v^{\prime}\right),$ $\left(u^{\prime\prime},v^{\prime\prime}\right)$ deux points de $\mathbb{R}^{2},$ nous avons

(3)

\left[x^{\prime},x^{\prime\prime};f\right]=\left[\tfrac{f\left(u^{\prime},v^{% \prime}\right)-f\left(u^{\prime\prime},v^{\prime}\right)}{u^{\prime}-u^{\prime% \prime}},\tfrac{f\left(u^{\prime\prime},v^{\prime}\right)-f\left(u^{\prime% \prime},v^{\prime\prime}\right)}{v^{\prime}-v^{\prime\prime}}\right]

où

x^{\prime}=\left(u^{\prime},v^{\prime}\right)\ \text{et }x^{\prime\prime}=% \left(u^{\prime\prime},v^{\prime\prime}\right).

On montre que la différence divisée (3) vérifie les conditions (1) et (2) de la définition 1, mais qu’elle n’est pas symétrique par rapport aux points $x^{\prime}$ et $x^{\prime\prime}.$

Mais nous povons construire une différence divisée sur ces points qui est symétrique. Par example si nous considérons la différence divisée définie par:

	$\displaystyle\left[x^{\prime},x^{\prime\prime};f\right]=$	$\displaystyle\tfrac{1}{2}\left[\tfrac{f\left(u^{\prime},v^{\prime}\right)-f]% \left(u^{\prime\prime},v^{\prime}\right)}{u^{\prime}-u^{\prime\prime}}+\tfrac{% f\left(u^{\prime\prime},v^{\prime}\right)-f\left(u^{\prime\prime},v^{\prime% \prime}\right)}{v^{\prime\prime}-v^{\prime}}\right.,$
		$\displaystyle\quad\left.\tfrac{f\left(u^{\prime\prime},v^{\prime}\right)-f% \left(u^{\prime\prime},v^{\prime\prime}\right)}{v^{\prime}-v^{\prime\prime}}+% \tfrac{f\left(u^{\prime},v^{\prime\prime}\right)-f\left(u^{\prime},v^{\prime}% \right)}{v^{\prime\prime}-v^{\prime}}\right]$

alors on a évidement

\left[x^{\prime},x^{\prime\prime};f\right]=\left[x^{\prime\prime},x^{\prime};f\right]

Soit maintenant $X=Y=C\left[0,1\right]$ où par $C\left[0,1\right]$ nous désignons l’ensemble des fonctions définies et contenues sur l’intervalle $\left[0,1\right].$ Considérons maintenant l’application $F:C\left[0,1\right]\times C\left[0,1\right]$ donnée par l’égalité suivante:

F\left(x\right)\left(s\right)=\int_{0}^{1}K\left(s,t,x\left(t\right)\right)dt

où $K:\left[0,1\right]\times\left[0,1\right]\times\mathbb{R}\rightarrow\mathbb{R}$ est une fonction continue sur tout son domaine de définition.

Soit maintenant $n+1$ -fonctions

(4)

x_{1},x_{2},\ldots,x_{n+1}

de l’espace $C\left[0,1\right]$ qui ont la propriété que $x_{j}\left(t\right)\neq x_{i}\left(t\right)$ pour $i\neq j$ et pour chaque $t\in\left[0,1\right].$

La différence divisée de l’application $F$ sur les fonctions $x_{i},x_{j}$ du systéme (4) peut se définir à l’aide de l’égalité suivante:

\left[x_{1},x_{2};F\right]h\left(s\right)=\int_{0}^{1}\tfrac{K\left(s,t,x_{2}% \left(t\right)\right)-K\left(s,t,x_{1}\left(t\right)\right)}{x_{2}\left(t% \right)-x_{1}\left(t\right)}h\left(t\right)dt

où

h\in C\left[0,1\right].

On montre immédiatement que l’application linéaire définie ci-dessus possède les propriétés (1) et (2) de la définition 1.

Si nous désignons par $\left[x_{i},x_{i+1},\ldots,x_{i+s};K\right]$ la différence divisée d’ordre $s$ de la fonction $K$ , alors la différence divisée d’ordre $s$ de l’application $F$ se définit par l’égalité suivante:

	$\displaystyle\left[x_{i},x_{i+1},\ldots,x_{i+s};F\right]h_{1}h_{2}\ldots h_{3}=$
	$\displaystyle={\int_{0}^{1}}\left[x_{i},x_{i+1},\ldots,x_{i+s};K\right]h_{1}% \left(t\right)h_{2}\left(t\right)\ldots h_{s}\left(t\right)dt$

où

h_{1},h_{2},\ldots,h_{s}\in C{\left[0,1\right]}.

2. Interpolation

Dans tout ce qui suit nous supposerons que les différences divisées sont symétriques par rapport aux points considérées.

Nous désignons maintenant, par $\ L_{n}:X\rightarrow Y$ une application définie par l’égalité:

(5)		$\displaystyle L_{n}\left(x\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{n+1};G\right]\left(x-x_{n}\right)% \ldots\left(x-x_{1}\right)$

Allors nous avons le théorème suivant:

Théorème 1.

L’application $L_{n}$ définie par (5) possède les propriétés suivantes

1)

$L_{n}\left(x_{i}\right)=G\left(x_{i}\right),\ \;\;i=1,2,\ldots,n+1$
2)

$G\left(x\right)-L_{n}\left(x\right)=\left[x,x_{1},\ldots,x_{n+1};G\right]\left% (x-x_{n+1}\right)\ldots\left(x-x_{1}\right)$ pour $x\in X,$ $x\neq x_{i},$ $i=1,2,\ldots,n+1.$

Démonstration..

Nous démontrons l’égalité 2) par induction. Pour $n=0$ l’égalité 2) est évidente parce que $G\left(x\right)-G\left(x_{1}\right)=\left[x,x_{1};G\right]\left(x-x_{1}\right)$ qui n’est autre que l’égalité 1) de la définition 1. Nous supposons que l’égalité 2) est vraie par $n=k$ et nous montrerons qu’elle est vraie aussi pour $n=k+1.$

En effet si l’égalité suivante a lieu

(6)	$\displaystyle G\left(x\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x-x_{1}% \right)+\ldots$
	$\displaystyle+\left[x_{1},x_{2},\ldots,x_{k+1};G\right]\left(x-x_{k}\right)% \ldots\left(x-x_{1}\right)$
	$\displaystyle+\left[x,x_{1},\ldots,x_{k+1};G\right]\left(x-x_{k+1}\right)% \ldots\left(x-x_{1}\right),$

alors, en tenant compte de l’égalité

\left[x,x_{1},\ldots,x_{k+1};G\right]=\left[x,x_{1},\ldots,x_{k+2};G\right]% \left(x-x_{k+2}\right)+\left[x_{1},x_{2},..,x_{k+2};G\right]

qui résulte de la définition de la différence divisée d’ordre $k+2.$ Il résulte l’égalité suivante:

	$\displaystyle G\left(x\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{k+2};G\right]\left(x-x_{k+1}\right)% \ldots\left(x-x_{1}\right)$
		$\displaystyle+\left[x,x_{1},\ldots,x_{k+2};G\right]\left(x-x_{k+2}\right)% \ldots\left(x-x_{1}\right)$

ce qui montre que l’égalité 2) a lieu pour $n=k+1.$

Il reste à démontrer les égalités 1). De la définition de l’application $L_{n}$ il résulte:

(7)		$\displaystyle L_{n}\left(x_{i}\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x_{i}-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{i};G\right]\left(x_{i}-x_{i-1}\right% )\ldots\left(x_{i}-x_{1}\right).$

Si nous considérons maintenant le dernier terme à droite de l’égalité (7) et tenons compte de l’égalité:

	$\displaystyle\left[x_{1},x_{2},\ldots,x_{i};G\right]\left(x_{i}-x_{i-1}\right)=$
	$\displaystyle=\left[x_{i-1},x_{1},\ldots,x_{i-2},x_{i};G\right]\left(x_{i}-x_{% i-1}\right)$
	$\displaystyle=\left[x_{1},x_{2},\ldots,x_{i-2},x_{i};G\right]-\left[x_{i-1},x_% {1},\ldots,x_{i-2};G\right]$
	$\displaystyle=\left[x_{1},x_{2},\ldots,x_{i-1},x_{i};G\right]-\left[x_{1},x_{2% },\ldots,x_{i-2},x_{i-1};G)\right]$

nous obtenons

	$\displaystyle L_{n}\left(x_{i}\right)=$	$\displaystyle G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x_{i}-x_{1}% \right)+\ldots$
		$\displaystyle+\left[x_{1},x_{2},\ldots,x_{i-2},x_{i};G\right]\left(x_{i}-x_{i-% 2}\right)\ldots\left(x_{i}-x_{1}\right).$

En procédant de la mème manière après un nombre fini des pas nous parvenons à l’égalitè suivante:

L_{n}\left(x_{i}\right)=G\left(x_{1}\right)+\left[x_{1},x_{2};G\right]\left(x_% {i}-x_{1}\right)=G\left(x_{1}\right)+G\left(x_{i}\right)-G\left(x_{1}\right)=G% \left(x_{i}\right).

L’application $L_{n}$ est dite pôlynome d’interpolation de Lagrange de l’application $G$ sur les noeuds $x_{i},i=1,2,\ldots,n+1$ du système (1) ∎

3. La résolution des équations par interpolation

On considère l’èquation

(8)

G\left(x\right)=\theta

$\theta$ est l’élément nul de l’éspace $Y$ et $G:X\rightarrow Y$ est un opérateur non linéaire.

Pour la résolution de l’équation (8) nous pouvons procéder de la manière suivante.

En supposant que les points du système (1) sont dans un voisinage de la soltuion $\bar{x}$ de l’équation (8), de l’égalité 2) (théorème 1) il rèsulte l’égalité suivante:

G\left(\bar{x}\right)=L_{n}\left(\bar{x}\right)+\left[\bar{x},x_{1},\ldots,x_{% n+1};G\right]\left(\bar{x}-x_{n+1}\right)\ldots\left(\bar{x}-x_{1}\right)=\theta

d’où il résulte

\left\|L_{n}\left(\bar{x}\right)\right\|\leq\left\|\left[\bar{x},x_{1},\ldots,% x_{n+1};G\right]\right\|\left\|x-x_{1}\right\|\ldots\left\|x-x_{n+1}\right\|.

Si nous supposons maintenant que nous avons les inégalités $\left\|\bar{x}-x_{i}\right\|\leq\varepsilon,$ $i=\overline{1,n+1}$ où $\varepsilon$ est un nombre réel et positif, alors on a:

\left\|L_{n}\left(\bar{x}\right)\right\|\leq\left\|\left[\bar{x},x_{1},\ldots,% x_{n+1};G\right]\right\|\varepsilon^{n+1}

d’où il résulte que pour trouver une approximation de la solution $\bar{x}$ il suffi de résoudre l’équation suivante:

(9)

L_{n}\left(x\right)=\theta.

La méthode exposée si-dessus présente quelques inconvénients, notamment:

Tout d’abord, la résolution d’une équation sous la forme (9) même dans le cas $n=1$ est un problème de mathématiques difficile et la dificulté du problème croit considérablement si $n>1.$ Même dans le cas $X=Y={\mathbb{R}},$ c’est-à-dire, quand $L_{n}$ est un polynome algébrique à coefficients réels, le problème peut être très difficile à cause du fait qu’une équation algebrique de dégré $n$ a $n$ racines, et alors il est nécessaire de choisir la racine de l’équation (9) qui approche la racine $\bar{x}$ de l’équation (8).

En second lieu, il est bien connue que la position des racines d’une équation algébrique dans le plan et la nature de ces racines peuvent se modifier considérablement quand les coefficients de l’équation sont affectés par des erreurs non essentielles.

Dans ce qui suit nous exposerons une autre méthode avec laquelle une parte des difficultés exposéss ci-dessus, s’élimine.

Nous supposons que les opérateurs linéaires

\left[x_{i},x_{j};G\right]\in L\left(X,Y\right),\ \;\;i\neq j;j=1,2,\ldots,n+1

sont inversables.

Il en résulte que $G\left(x_{i}\right)\neq G\left(x_{i}\right),$ $i\neq j.$ Soit maintenant $D$ un ensemble quelconque d’éléments de l’espace $X .$ Nous désignons par $\bar{G}=G|_{D}$ la restriction de l’application $G$ à l’ensemble $D .$

Nous supposons que l’application $\bar{G}$ est un homéomorphisme des ensembles $D$ et $G\left(D\right).$ Où par $G\left(D\right)$ nous avons désigné l’image de l’ensemble $D$ par $G .$

Nous avons le théorème suivant:

Théorème 2.

Si l’opérateur linéaire $\left[x_{i},x_{j};G\right],$ ou $x_{i},x_{j}\in D$ est inversable, alors a lieu l’égalité:

\big{[}y_{i},y_{j},\bar{G}^{-1}\big{]}=\left[x_{i},x_{j};G\right]^{-1}

où

y_{i}=G\left(x_{i}\right)\ \ \text{et\ \ }y_{j}=G\left(x_{j}\right).

Démonstration..

De la définition de différence divisée d’ordre 1 il résulte que

G\left(x_{j}\right)=G\left(x_{i}\right)=\left[x_{i},x_{j};G\right]\left(x_{j}-% x_{j}\right)

où

\left[x_{i},x_{j};G\right]^{-1}\left(y_{j}-y_{i}\right)=x_{j}-x_{i}

C’est à dire

\bar{G}^{-1}\left(y_{j}\right)-\bar{G}^{-1}\left(y_{i}\right)=\left[x_{i},x_{j% };G\right]^{-1}\left(y_{j}-y_{i}\right)

d’où il résulte l’égalité de l’énoncé du théorème.

Soient maintenant $x_{1},$ $x_{2},\ldots,x_{n+1},$ $n+1$ - éléments de l’ensemble $D .$

Nous désignons par $y_{1},y_{2},\ldots,y_{n+1}$ les valeurs de l’application $G$ sur ces points, c’est-à-dire $y_{i}=G\left(x_{i}\right),$ $i=1,2,\ldots,n+1.$ Nous considérons l’application $L_{n}:Y\rightarrow X$ donnée par

(10)		$\displaystyle L_{n}\left(y\right)=$	$\displaystyle x_{1}+\big{[}y_{1},y_{2};\bar{G}^{-1}\big{]}\left(y-y_{1}\right)+\ldots$
		$\displaystyle+\big{[}y_{1},\ldots,y_{n+1};\bar{G}^{-1}\big{]}\left(y-y_{n}% \right)\left(y-y_{n+1}\right)\ldots\left(y-y_{1}\right)$

qui vérifie les égalités

(11)

\bar{G}^{-1}\left(y\right)=L_{n}\left(y\right)+\big{[}y,y_{1},\ldots,y_{n+1};% \bar{G}^{-1}\big{]}\left(y-y_{n+1}\right)\ldots\left(y-y_{1}\right)

(12)

\bar{G}^{-1}\left(y_{i}\right)=L_{n}\left(y_{i}\right)=x_{i},\qquad i=1,2,% \ldots,n+1.

Si nous supposons maintenant que la solution $\bar{x}$ de l’équation (8) apartient à l’ensemble $D,$ alors évidemment $\bar{x}=\bar{G}^{-1}\left(\theta\right)$ et de (11) nous déduisons:

(13)

\bar{x}=\bar{G}^{-1}\left(\theta\right)=L_{n}\left(\theta\right)+\left(-1% \right)^{n+1}\big{[}\theta,y_{1},\ldots,y_{n+1};\bar{G}^{-1}\big{]}y_{n+1}% \ldots y_{1}.

Si nous designons par

(14)

\bar{x}=L_{n}\left(\theta\right)

nous en déduisons:

(15)

\left\|\bar{x}-\bar{x}\right\|\leq\big{\|}\big{[}\theta,y_{1},\ldots,y_{n+1};% \bar{G}^{-1}\big{]}\big{\|}\cdot\left\|y_{n+1}\right\|\ldots\left\|y_{1}\right\|.

De l’égalité (15) il résulte que si les éléments $x_{1},x_{2},\ldots,x_{n+1}$ sont choisis de telle manière que $\left\|y_{1}\right\|=\left\|G\left(x_{i}\right)\right\|<\varepsilon,\ i=1,2,% \ldots,n+1$ où $\varepsilon$ est un nombre réel suffisamment petit, alors $\bar{x}$ est une bonne approximation pour $\bar{x}.$

Pour plus de clarté nous designons par $L_{n}\big{(}y_{1},y_{2},\ldots,y_{n+1};\bar{G}^{-1}|y\big{)}$ l’opérateur $L_{n}\left(y\right)$ donné par la relation (10). Soient maintenant $x_{1},$ $x_{2},\ldots,x_{n+1},n+1$ -éléments initiaux donnés et soit $\left(x_{n}\right)_{n=1}^{\infty}$ la suite généree par la rélation de récurrence:

(16)

x_{i+n+1}=L_{n}\big{(}y_{i,}y_{i+1},\ldots,y_{i+n};\bar{G}^{-1}|\theta\big{)},% \qquad i=1,2,\ldots\eqqed

Nous présenterons maintenant quelques cas particulieres du procédé itératif (16).

A. Soient $x_{1}$ et $x_{2}$ deux éléments arbitraires de l’espace $X .$ Si nous considérons les premiers deux termes du polynome d’interpolation inverse (10) tenons compte du théorème 2, nous avons

(17)

x_{k+1}=x_{k-1}-\left[x_{k-1},x_{k};G\right]^{-1}G\left(x_{k-1}\right),\qquad k% =2,3,\ldots

qui n’est autre chose que l’extension de la méthode de la corde.

B. Au cas où nous considérons trois éléments initiaux $x_{1},x_{2},x_{3}\in X$ et nous nous bornons aux trois premiers termes de la relation (10) on a:

(18)	$\displaystyle x_{k}=$	$\displaystyle x_{k-3}-\left[x_{k-3},x_{k-2};G\right]^{-1}G\left(x_{k-3}\right)$
	$\displaystyle-\left[x_{k-3},x_{k-2};G\right]^{-1}\left[x_{k-3},x_{k-1},x_{k-1}% ;G\right]\left[x_{k-3},x_{k-1};G\right]^{-1}\cdot$
	$\displaystyle\quad\cdot G\left(x_{k-3}\right)\cdot\left[x_{k-1},x_{k-2};G% \right]^{-1}G\left(x_{k-2}\right),\qquad k=4,5,\ldots$

Cette méthode est une extension à l’espace linéaire $X$ d’une méthode analogue à la méthode de Tchebycheff, bien connue. De (15) et de (16) nous déduisons

(19)

\displaystyle\left\|\bar{x}-x_{i+n+1}\right\|

\displaystyle\leq\big{\|}\big{[}\theta,y_{i},\ldots,y_{n+1};\bar{G}^{-1}\big{]% }\big{\|}\cdot\left\|y_{i}\right\|\ldots\left\|y_{n+1}\right\|,

$i=1,2,\ldots$

A propos de la méthode (16) il se pose les deux questions suivants:

1. Quelles sont les conditions pour la convergence de la méthode (16).

2. Dans le cas de la convergence de la méthode (16), quelle est la vitesse de convergence.

En ce qui concerne la vitese de convergence d’une méthode itérative de type (16), A. M. Ostrowski [1] a montré que l’ordre de convergence de cette méthode n’excède pas 2, pour chaque nombre de points d’interpolation donnée.

Dans ce qui suit nous montrerons que si a chaque pas d’iteration on choisit convenablement les points d’interpolation, alors l’ordre de convergence croit considérablement.

Ainsi qu’il est bien connue pour la résolution d’une équation de la forme (8) par une méthode itérative il est nécessaire de mettre en évidence une application $Q:X\rightarrow X$ qui a la propriété que chaque solution de l’équation (8) est un point fixe pour l’application $Q .$

Un opérateur $Q$ qui possède la propriété ci-dessus est dit opérateur itératif attaché à l’équation (8).

Pour les opérateurs attachés à l’équation (8) on peut définir la notion d’ordre.

Définition 4.

Soit $D\subseteq X$ une ensemble d’éléments de l’espace $X$ et $\rho>0$ un nombre réel.

Nous disons que l’opérateur itératif $Q$ a l’ordre $k$ $\left(k>0\ \text{nombre r\'{e}el}\right)$ sur l’ensemble $D,$ par rapport à l’équation (8) si pour chaque $x\in D$ on a

(20)

\left\|G\left(Q\left(x\right)\right)\right\|\leq\rho\left\|G\left(x\right)% \right\|^{k}.

Soient maintenant $Q_{1},Q_{2},..,Q_{n};n$ -opérateurs itératif attachés à l’équation (8), respectivement d’ordre $k_{1},k_{2},\ldots,k_{n}.$

Nous considérons un élément arbitraire $x_{0}\in X$ et désignons par $x_{s}^{0};s=\overline{1,n}$ les expresions suivantes:

(21)

x_{1}^{0}=Q_{1}\left(x_{0}\right),\;\;x_{s}^{0}=Q_{s}\left(x_{s-1}^{0}\right),% \;\;s=2,3,\ldots,n

Si les éléments initiaux dans la méthode itérative (16) sont:

(22)

x_{0},x_{1}^{0},\ldots,x_{n}^{0}

alors si nous écrivons $y_{0}^{0}=G\left(x_{0}\right),y_{i}^{0}=G\left(x_{i}^{0}\right),i=1,2,\ldots,n,$ on a:

(23)

x_{1}=L_{n}\big{(}y_{0}^{0},y_{1}^{0},\ldots,y_{n}^{0};\bar{G}^{-1}|\theta\big% {)}.

Nous supposons maintenant que nous avons construit les premiers $i+1$ éléments de la suite $\left(x_{n}\right)_{n=0}^{\infty}$ alors l’élément $x_{n+1}$ s’obtient de la manière suivante:

Nous écrievons:

(24)

x_{1}^{i}=Q_{1}\left(x_{i}\right),\ \;\;x_{j}^{i}=Q_{j}\left(x_{j-1}^{i}\right% ),\ \;\;j=2,3,\ldots,n

y_{0}^{i}=G\left(x_{i}\right),\ \;\;y_{j}^{i}=G\left(x_{j}^{i}\right),\ \;\;j=% 1,2,\ldots,n

Alors l’élément $x_{i+1}$ a la forme suivante:

(25)

x_{i+1}=L_{n}\big{(}y_{0}^{i},y_{1}^{i},\ldots,y_{n}^{i};\bar{G}^{-1}|\theta% \big{)}

De (15) et de (25) on a:

(26)

\left\|\bar{x}-x_{i+1}\right\|\leq\big{\|}\big{[}\theta,y_{0}^{i},\ldots,y_{n}% ^{i};\bar{G}^{-1}\big{]}\big{\|}\left\|y_{0}^{i}\right\|\ldots\left\|y_{n}^{i}% \right\|.

Mais du fait que nous avons supposé que les opérateurs itératifs $Q_{j},\ j=1,2,\ldots,n$ ont respectivement les ordres $k_{j},$ avec les constantes $\rho_{j};\ j=1,2,\ldots,n$ il résulte les relations suivantes:

(27)

\left\|y_{0}^{i}\right\|=\left\|G\left(x_{i}\right)\right\|

(28)	$\displaystyle\left\\|y_{s}^{i}\right\\|$	$\displaystyle\leq\left\\|G\left(x_{s}^{i}\right)\right\\|=\left\\|G\left(Q_{s}% \left(x_{s-1}^{i}\right)\right)\right\\|\leq\rho_{s}\left\\|G\left(Q_{s-1}\left(% x_{s-2}^{i}\right)\right)\right\\|^{k_{s}}$
	$\displaystyle\leq\rho_{s}\rho_{s-1}^{k_{s}}\left\\|G\left(Q_{s-2}\left(x_{s-3}% \right)\right)\right\\|^{k_{s}\cdot k_{s-1}}$
	$\displaystyle\leq\rho_{s}\cdot\rho_{s-1}^{k_{s}}\cdot\rho_{s-1}^{k_{s}\cdot k_% {s-1}}\ldots\rho_{1}^{k_{s}k_{s-1}\ldots k_{2}}\cdot\left\\|G\left(x_{i}\right)% \right\\|^{k_{1}\cdot k_{2}\ldots k_{s}}$

pour $s=1,2,\ldots,n.$

Si nous écrivons maintenant

(29)

C_{s}=\rho_{s}\rho_{s-1}^{k_{s}}\cdot\rho_{s-2}^{k_{s}k_{s-1}}\ldots\rho_{1}^{% k_{s}k_{s-1}\ldots k_{2}};\ \;\;s=2,3,\ldots,n,

(30)

K=\textstyle\prod\limits_{s=2}^{n}C_{s}

(31)

m=1+k_{1}+k_{1}k_{2}+\ldots+k_{1}\cdot k_{2}\ldots k_{n}

et si nous supposons que les différences divisées $\big{[}\theta,y_{0}^{i},y_{1}^{i},\ldots,y_{n}^{i};\bar{G}^{-1}\big{]}$ sont fortement bornées par la même constante $M>0,$ alors on déduit de (26);

(32)

\left\|\bar{x}-x_{i+1}\right\|\leq MK\left\|G\left(x_{i}\right)\right\|^{m},% \qquad i=0,1,\ldots

Si nous supposons maintenant que les differences divisées d’ordre 1 de l’aplication $G$ sont fortement bornées par la même constante $B>0,$ on a:

(33)

\left\|G\left(x_{i}\right)\right\|\leq B\left\|\bar{x}-x_{i}\right\|\qquad i=0% ,1,\ldots

En tenant compte des inégalités (33) et (32) on obtient:

(34)

\left\|\bar{x}-x_{i+1}\right\|\leq MKB^{m}\left\|\bar{x}-x_{i}\right\|,\qquad i% =0,1,\ldots

En multipliant les inégalités (34) par $\left(MKB^{m}\right)^{\frac{1}{m-1}}$ et en écrivant

\delta_{k}=\left(MKB^{m}\right)^{\frac{1}{m-1}}\left\|\bar{x}-x_{k}\right\|,% \qquad k=0,1,\ldots,

on obtient de (34)

(35)

\delta_{i+1}\leq\delta_{i}^{m},\qquad i=0,1,\ldots

Nous admettrons maintenant que nous pouvons choisir les constantes $M,$ $K,$ $B$ et le point initial $x_{0}$ de telle manière que $\delta_{0}<1.$

Des inégalités (35) on déduit:

\delta_{i+1}\leq\delta_{0}^{m^{i}},\qquad i=0,1,\ldots

d’où en tenant compte de la condition $\delta_{0}<1$ l’on déduit

\lim_{i\rightarrow\infty}\delta_{i+1}=0

C’est-à-dire

\lim_{i\rightarrow i}x_{i+1}=\bar{x}.

Nous consiérons maintenant qulques cas particuliers de la méthode itérative (25).

1. Si nous considérons un seul opérateur itératif $Q$ d’ordre $k=1$ alors la méthode itérative (25) revient à la méthode bien connue de Aitken-Steffensen. Dans ce cas nous avons: $m=2.$

2. Si $Q_{1}=Q_{2}=\ldots=Q_{n},\ \ k_{1}=k_{2}=\ldots=k_{n}=k,\$ où $k\neq 1$ alors $C_{s}=\rho^{\frac{k^{n+1}-1}{k-1}}$ et $m=\frac{k^{n+1}-1}{k-1}.$

3. Si $Q_{1}=Q_{2}=\ldots=Q_{n}$ et $\ k_{1}=k_{2}=\ldots=k_{n}=1,$ alors $C_{s}=\rho^{s}$ et $m=n.$

Remarque.

L’ordre de convergence donné par l’égalité (31) de la méthode (25) est le plus grand possible par rapport aux opérateurs itératifs $Q_{1},$ $Q_{2},\ldots,Q_{n}$ donnés, si l’ordre dans lequel ils sont appliqués pour obténir les éléments (24), est donnée par l’ordre décroissant des nombres $k_{1},$ $k_{2},\ldots,k_{n}.$ C’est-à-dire, l’ordre de convergence $m$ est maximal si $k_{1}\geq k_{2}\geq\ldots\geq k_{n}$ et minimal si $k_{1}\leq k_{2}\leq\ldots\leq k_{m}.$ ∎

Bibliographie

[1] A.M. Ostrowski, Reşenie uravnenii i sistem uravnenii, Izd. inostr. lit. Moskva (1963).
[2] I. Păvăloiu, ^†^†margin: clickable $\rightarrow$ Interpolation dans les espaces linéaires normés et applications, Mathematica, Cluj, nr.12 (35), 2, (1970), pp. 309–324.
[3] I. Păvăloiu, ^†^†margin: clickable $\rightarrow$ Introducere în teoria aproximării soluţiilor ecuaţiilor, Editura Dacia, 1976.
[4] T. Popoviciu, ^†^†margin: clickable $\rightarrow$ Introduction à la théorie des différences divisées, Bulletin mathématique de la société Roumaine de Sciences, 42, 1, (1940) pp. 65–78. JSTOR
[5] A.S. Sergeev, O metode hord, Sibirski mat. Jurnal, XI, (2), (1961), pp. 282–289.
[6] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice Hall, Series in Automatic Computation, 1964.
[7] S. Ul’m, Ob obobscennyh razdelennîh raznostiah, II, Izv. Nauk Estonskoi SSR, 16, 2, (1967), 146–155.

Reçu, 8.IV.1980

(28)	$\displaystyle\left\\|y_{s}^{i}\right\\|$	$\displaystyle\leq\left\\|G\left(x_{s}^{i}\right)\right\\|=\left\\|G\left(Q_{s}% \left(x_{s-1}^{i}\right)\right)\right\\|\leq\rho_{s}\left\\|G\left(Q_{s-1}\left(% x_{s-2}^{i}\right)\right)\right\\|^{k_{s}}$
	$\displaystyle\leq\rho_{s}\rho_{s-1}^{k_{s}}\left\\|G\left(Q_{s-2}\left(x_{s-3}% \right)\right)\right\\|^{k_{s}\cdot k_{s-1}}$
	$\displaystyle\leq\rho_{s}\cdot\rho_{s-1}^{k_{s}}\cdot\rho_{s-1}^{k_{s}\cdot k_% {s-1}}\ldots\rho_{1}^{k_{s}k_{s-1}\ldots k_{2}}\cdot\left\\|G\left(x_{i}\right)% \right\\|^{k_{1}\cdot k_{2}\ldots k_{s}}$

Solving equations by interpolation

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

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

La résolution des équations par interpolation

1. La notation de diffèrence divisée.

Définition 1.

Définition 2.

Définition 3.

2. Interpolation

Théorème 1.

Démonstration..

3. La résolution des équations par interpolation

Théorème 2.

Démonstration..

Définition 4.

Remarque.

Bibliographie

Related Posts

	$\displaystyle\left[x_{k},\ldots,x_{k+i+1};G\right]\left(x_{k+i+1}-x_{k}\right)=$
	$\displaystyle=\left[x_{k+1},\ldots,x_{k+i+1};G\right]-\left[x_{k},\ldots,x_{k+% i};G\right]$