Interpolation newtonienne

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

Sommaire

Définition

Étant donné un ensemble de k+1 points

(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) = \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) = \prod_{i=0}^{j-1} (x - x_i)

et les coefficients comme ceci

a_j = [y_0,\ldots,y_j]

[y_0,\ldots,y_j]

est la notation pour les différences divisées.

Par conséquent, le polynôme d'interpolation peut être écrit ainsi

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

Idée principale

Résoudre un problème d'interpolation conduit à un problème d'algèbre linéaire où nous devons inverser une matrice. En utilisant une méthode standard d'interpolation polynomiale, on obtient une matrice du type matrice de Vandermonde qui est très difficile à inverser. En choisissant une base newtonienne de polynômes, on obtient une matrice triangulaire inférieure qui s'inverse beaucoup plus facilement.

Pour k+1 points, on construit la base de Newton ainsi

n_j(x) = \prod_{i=0}^{j-1} (x - x_i) \qquad j=1,\ldots,k

En utilisant ces polynômes, nous devons inverser

 
\begin{bmatrix}
      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{bmatrix}
\begin{bmatrix}
     a_0 \\
     \vdots \\
     a_{k} 
\end{bmatrix}
=
\begin{bmatrix}
     y_0 \\
     \vdots \\
     y_{k}
\end{bmatrix}

pour résoudre le problème d'interpolation polynomiale.

Cette matrice peut être inversée successivement en résolvant

 \sum_{i=0}^{j} a_{i} n_{i}(x_j) = y_j \qquad j = 0,...,k

On commence par j = 0 qui nous donne a0 puis pour j = 1, le calcul de a0 nous permet de déduire a1. Et ainsi de suite jusqu'à j = k.

Application

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 équi-répartis, le calcul des différences divisées devient nettement plus rapide. Par conséquent, l'interpolation polynomiale dans une base de Newton est priviligiée par rapport à une interpolation lagrangienne pour des raisons pratiques.

Lien externe

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Interpolation newtonienne de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • Interpolation Polynomiale — En mathématiques, en analyse numérique, l interpolation polynomiale est une technique d interpolation d un ensemble de données ou d une fonction par un polynôme. En d autres termes, étant donné un ensemble de points (obtenu, par exemple, à la… …   Wikipédia en Français

  • Interpolation de Hermite — Interpolation polynomiale En mathématiques, en analyse numérique, l interpolation polynomiale est une technique d interpolation d un ensemble de données ou d une fonction par un polynôme. En d autres termes, étant donné un ensemble de points… …   Wikipédia en Français

  • Interpolation (mathématiques) — Interpolation numérique En analyse numérique (et dans son application algorithmique discrète pour le calcul numérique), l interpolation est une opération mathématique permettant de construire une courbe à partir de la donnée d un nombre fini de… …   Wikipédia en Français

  • Interpolation Numérique — En analyse numérique (et dans son application algorithmique discrète pour le calcul numérique), l interpolation est une opération mathématique permettant de construire une courbe à partir de la donnée d un nombre fini de points, ou une fonction à …   Wikipédia en Français

  • Interpolation numerique — Interpolation numérique En analyse numérique (et dans son application algorithmique discrète pour le calcul numérique), l interpolation est une opération mathématique permettant de construire une courbe à partir de la donnée d un nombre fini de… …   Wikipédia en Français

  • Interpolation Lagrangienne — En analyse numérique, les polynômes de Lagrange, du nom de Joseph Louis Lagrange, permettent d interpoler une série de points par un polynôme qui passe exactement par ces points appelés aussi nœuds. Cette technique d interpolation polynomiale a… …   Wikipédia en Français

  • Interpolation de Lagrange — Interpolation lagrangienne En analyse numérique, les polynômes de Lagrange, du nom de Joseph Louis Lagrange, permettent d interpoler une série de points par un polynôme qui passe exactement par ces points appelés aussi nœuds. Cette technique d… …   Wikipédia en Français

  • Interpolation de lagrange — Interpolation lagrangienne En analyse numérique, les polynômes de Lagrange, du nom de Joseph Louis Lagrange, permettent d interpoler une série de points par un polynôme qui passe exactement par ces points appelés aussi nœuds. Cette technique d… …   Wikipédia en Français

  • Interpolation polynomiale — En mathématiques, en analyse numérique, l interpolation polynomiale est une technique d interpolation d un ensemble de données ou d une fonction par un polynôme. En d autres termes, étant donné un ensemble de points (obtenu, par exemple, à la… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”