Interpolation newtonienne

En analyse numérique, l'interpolation newtonienne, du nom d'Isaac Newton, est une méthode d'interpolation polynomiale permettant d'obtenir le polynôme de Lagrange comme combinaison linéaire de polynômes de la « base newtonienne ».

Contrairement à l'interpolation d'Hermite par exemple, cette méthode ne diffère de l'interpolation lagrangienne que par la façon dont le polynôme est calculé, le polynôme d'interpolation qui en résulte est le même. Pour cette raison on parle aussi plutôt de la forme de Newton du polynôme de Lagrange.

Définition

Étant donnés k + 1 {\displaystyle k+1} points

( x 0 , y 0 ) , … , ( x k , y k ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})} (les xj tous distincts 2 à 2), l'interpolation polynomiale dans une base de Newton est une combinaison linéaire de polynômes appartenant à cette base
N ( x ) = ∑ j = 0 k a j n j ( x ) {\displaystyle N(x)=\sum _{j=0}^{k}a_{j}n_{j}(x)}

avec les polynômes de Newton définis de la manière suivante

n j ( x ) = ∏ 0 ≤ i < j ( x − x i ) j = 0 , … , k {\displaystyle n_{j}(x)=\prod _{0\leq i<j}(x-x_{i})\qquad j=0,\ldots ,k}

(en particulier n 0 = 1 {\displaystyle n_{0}=1} , le produit vide)

et les coefficients égaux aux différences divisées :

a j = [ y 0 , … , y j ] . {\displaystyle a_{j}=[y_{0},\ldots ,y_{j}].}

En résumé :

Le polynôme d'interpolation de Newton N ( x ) {\displaystyle N(x)} associé à k + 1 {\displaystyle k+1} points ( x 0 , y 0 ) , … , ( x k , y k ) {\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})} est défini par :

N ( x ) = [ y 0 ] + [ y 0 , y 1 ] ( x − x 0 ) + … + [ y 0 , … , y k ] ( x − x 0 ) … ( x − x k − 1 ) . {\displaystyle N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\ldots +[y_{0},\ldots ,y_{k}](x-x_{0})\ldots (x-x_{k-1}).}

Théorème d'interpolation de Newton

Le théorème suivant justifie le nom de « polynôme d'interpolation » pour N {\displaystyle N}  :

Ce polynôme N {\displaystyle N} est égal au polynôme d'interpolation de Lagrange associé aux k + 1 {\displaystyle k+1} points, c'est-à-dire à l'unique polynôme L {\displaystyle L} de degré inférieur ou égal à k {\displaystyle k} vérifiant : ∀ i ∈ { 0 , … , k } L ( x i ) = y i . {\displaystyle \forall i\in \{0,\dots ,k\}\quad L(x_{i})=y_{i}.}

Démonstration

Montrons d'abord, par récurrence sur k {\displaystyle k} , que le coefficient de degré k {\displaystyle k} de L {\displaystyle L} est égal à [ y 0 , … , y k ] {\displaystyle [y_{0},\dots ,y_{k}]} . Pour 1 {\displaystyle 1} point, cette égalité est immédiate. Supposons-la vraie pour k {\displaystyle k} points, et notons P {\displaystyle P} le polynôme d'interpolation associé aux k {\displaystyle k} premiers points (d'indices 0 {\displaystyle 0} à k − 1 {\displaystyle k-1} ) et Q {\displaystyle Q} celui associé aux k {\displaystyle k} derniers (d'indices 1 {\displaystyle 1} à k {\displaystyle k} ). Alors,

L ( x ) = ( x − x 0 ) Q ( x ) − ( x − x k ) P ( x ) x k − x 0 {\displaystyle L(x)={\frac {(x-x_{0})Q(x)-(x-x_{k})P(x)}{x_{k}-x_{0}}}}

donc (par hypothèse de récurrence) le coefficient de degré k {\displaystyle k} de L {\displaystyle L} est bien égal à [ y 1 , … , y k ] − [ y 0 , … , y k − 1 ] x k − x 0 = [ y 0 , … , y k ] {\displaystyle {\frac {[y_{1},\dots ,y_{k}]-[y_{0},\dots ,y_{k-1}]}{x_{k}-x_{0}}}=[y_{0},\dots ,y_{k}]} .

Avec les mêmes notations, montrons maintenant, à nouveau par récurrence sur k {\displaystyle k} , que L = N {\displaystyle L=N} . Pour 1 {\displaystyle 1} point, cette égalité est immédiate. Supposons-la vraie pour k {\displaystyle k} points. L − P {\displaystyle L-P} est de degré inférieur ou égal à k {\displaystyle k} et nul en x 0 , … , x k − 1 {\displaystyle x_{0},\dots ,x_{k-1}} et son coefficient de degré k {\displaystyle k} est égal à celui de L {\displaystyle L} donc, d'après ce qui précède, à [ y 0 , … , y k ] {\displaystyle [y_{0},\dots ,y_{k}]} . Par conséquent, L ( x ) {\displaystyle L(x)} est égal à P ( x ) + [ y 0 , … , y k ] ( x − x 0 ) … ( x − x k − 1 ) {\displaystyle P(x)+[y_{0},\ldots ,y_{k}](x-x_{0})\ldots (x-x_{k-1})} , c'est-à-dire (par hypothèse de récurrence) à N ( x ) {\displaystyle N(x)} .

Remarque

Le polynôme d'interpolation de Lagrange L {\displaystyle L} appartient à l'espace vectoriel des polynômes de degré inférieur ou égal à k {\displaystyle k} , dont la « base de Newton » n := ( n 0 , … , n k ) {\displaystyle n:=(n_{0},\dots ,n_{k})} définie ci-dessus est une base. D'après le théorème d'interpolation de Newton, les coordonnées de L {\displaystyle L} dans n {\displaystyle n} sont ( a 0 , … , a k ) {\displaystyle (a_{0},\dots ,a_{k})} , où les a i {\displaystyle a_{i}} sont les différences divisées. Une méthode naïve de calcul direct des coordonnées de L {\displaystyle L} dans n {\displaystyle n} serait de résoudre le système d'équations linéaires

∑ j = 0 i a j n j ( x i ) = y i i = 0 , … , k {\displaystyle \sum _{j=0}^{i}a_{j}n_{j}(x_{i})=y_{i}\qquad i=0,\dots ,k} ,

qui se réécrit

( 1 0 1 x 1 − x 0 1 x 2 − x 0 ( x 2 − x 0 ) ( x 2 − x 1 ) ⋮ ⋮ ⋱ 1 x k − x 0 … … ∏ j = 0 k − 1 ( x k − x j ) ) ( a 0 ⋮ a k ) = ( y 0 ⋮ y k ) . {\displaystyle {\begin{pmatrix}1&&&&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&&\\\vdots &\vdots &&\ddots &\\1&x_{k}-x_{0}&\ldots &\ldots &\prod _{j=0}^{k-1}(x_{k}-x_{j})\end{pmatrix}}{\begin{pmatrix}a_{0}\\\vdots \\a_{k}\end{pmatrix}}={\begin{pmatrix}y_{0}\\\vdots \\y_{k}\end{pmatrix}}.}

Puisque ce système est échelonné et même triangulaire inférieur, on pourrait le résoudre de proche en proche en commençant par la ligne i = 0 {\displaystyle i=0} qui nous donnerait a 0 {\displaystyle a_{0}} puis pour i = 1 {\displaystyle i=1} , le calcul de a 0 {\displaystyle a_{0}} nous permettrait de déduire a 1 {\displaystyle a_{1}} , et ainsi de suite jusqu'à i = k {\displaystyle i=k} .

Applications

Comme le montre la définition des différences divisées, des points supplémentaires peuvent être ajoutés pour créer un nouveau polynôme d'interpolation sans recalculer les coefficients. De plus, si un point est modifié, il est inutile de recalculer l'ensemble des coefficients. Autre avantage, si les xi sont équirépartis, le calcul des différences divisées devient nettement plus rapide. Par conséquent, la forme de Newton pour le polynôme d'interpolation est privilégiée par rapport à celle de Lagrange ou même par rapport à la méthode naïve ci-dessus, pour des raisons pratiques.

Le théorème d'interpolation de Newton permet de démontrer que toute fonction polynomiale est égale à sa série de Newton.

Voir aussi

Lien externe

Interpolation polynômiale (sic) de type Newton et différences divisées sur math-linux.com

Crédit d'auteurs

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Newton polynomial » (voir la liste des auteurs).
  • icône décorative Portail de l'analyse