Soient \( n \hspace{0.1em} \in \hspace{0.05em} \mathbb{N} \) un entier naturel, et une série de couples d'antécédents/images \( \Bigl \{ \bigl \{x_i, y_i \bigr \}_{ i \hspace{0.1em} \in \hspace{0.05em} n} \Bigr\}\).
Cette méthode permet de trouver l'expression d'une fonction polynomiale unique, avec cette série de valeurs donnée.
L'interpolation polynomiale Lagrangienne nous dit qu'il est possible de construire un polynôme unique correspondant à cette série de valeurs.
Il y aura deux manières de générer ce polynôme :
Par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)
$$ L(X) = \sum_{j = 0}^n y_j \Biggl[ \prod_{\underset{i \neq j}{i=0}}^n \frac{X - x_i}{x_j - x_i} \Biggr]$$
Étant donné le système \( (S) \) suivant :
$$ (S) \enspace \left \{ \begin{gather*} a_0 + a_1 x_0 + a_2 x_0 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_0 ^n = y_0 \\ a_0 + a_1 x_1 + a_2 x_1 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_1 ^n = y_1 \\ ........................ ............\\ a_0 + a_1 x_n + a_2 x_n ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_n ^n = y_n \\ \end{gather*} \right \} $$
On peut trouver ses solutions au moins de deux manières différentes :
Avec \( \bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) comme valeurs de la solution unique du système \( (S)\)
$$ (S^*) \enspace \Longleftrightarrow \enspace \underbrace{ \begin{pmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n \\ 1 & x_1 & x_1^2 & \dots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^n \\ \end{pmatrix} } _\text{X} \times \underbrace{ \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ . \\ a_n \\ \end{pmatrix} } _\text{A} = \underbrace{ \begin{pmatrix} y_0 \\ y_1 \\ y_2 \\ . \\ y_n \\ \end{pmatrix} } _\text{Y} $$
Et à ce moment-là :
Où \(X_k\) représente la matrice carrée formée par la matrice \(X\) dans laquelle on a interverti sa \(k\)-ième colonne avec la matrice colonne \(Y\).
Soient \( n \hspace{0.1em} \in \hspace{0.05em} \mathbb{N} \) un entier naturel, et une série de couples d'antécédents/images \( \Bigl \{ \bigl \{x_i, y_i \bigr \}_{ i \hspace{0.1em} \in \hspace{0.05em} n} \Bigr\}\) :
Et tel que la figure ci-dessous en exemple :
On souhaite trouver une fonction polynomiale qui correspondrait à cette série de valeurs donnée.
Pour un entier \(m \enspace (m \in \mathbb{N} )\) donné, une fonction polynomiale de degré \( m\) se définit de la manière suivante :
Pour trouver cette fonction \( L(X) \), il va donc falloir trouver une valeur pour chaque coefficient \(a_i\) pour un \(m\) donné.
On aura alors la correspondance entre nos coefficients et notre série de valeurs, ce qui nous donne le système \((S)\) suivant :
$$ (S) \enspace \left \{ \begin{gather*} a_0 + a_1 x_0 + a_2 x_0 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_m x_0 ^m = y_0 \\ a_0 + a_1 x_1 + a_2 x_1 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_m x_1 ^m = y_1 \\ ........................ ............\\ a_0 + a_1 x_k + a_2 x_k ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_m x_k ^m = y_k \\ ........................ ............\\ a_0 + a_1 x_m + a_2 x_m ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_m x_m ^m = y_m \\ \end{gather*} \right \} $$
Il y aura au moins deux manières de générer ce polynôme \(L(X)\) :
- par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)
- par la construction d'un polynôme \(P_n(X)\), en trouvant l'unique solution pour les coefficients \(\bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) inconnues du système \( (S) \)
La logique ici consiste à construire une série de \(n\) polynômes distincts \( \Bigl \{L_j(X) \Bigr\}_{ i \hspace{0.1em} \in \hspace{0.05em} \mathbb{N}} \) tels que :
$$ \forall (i,j) \in [\![ 0, n]\!]^2, \enspace i \neq j, \enspace \Biggl \{ \begin{gather*} L_j(x_j) = 1 \\ L_j(x_i) = 0 \qquad (C) \end{gather*} $$
Nous allons donc construire chaque polynôme un à un.
Pour tout \( j \in [\![ 0, n]\!] \), il faut que la condition \( (C) \) soit satisfaite, à savoir que les \( x_i \ ( i\neq j) \) soient racines pour que ce polynôme \( L_j(x_i) \) s'annule. On a,
Enfin, pour que le polynôme \( L_j(x_j) \) soit égal à \( 1 \), il faut la présence d'un dénominateur qui soit égal au numérateur lorsque \( X = x_j \). On a alors,
Le fait d'ajouter un dénominateur ne change rien à la condition \( (C) \) installée précedémment.
De plus, la condition \( i \neq j \) nous assure bien que le dénominateur ne sera jamais nul.
À ce stade, multipliant chaque polynôme \( L_j(X) \) par la valeur de \( y_j \), on s'assure bien que :
$$ \forall (i,j) \in [\![ 0, n]\!]^2, \enspace i \neq j, \enspace \Biggl \{ \begin{gather*} y_j L_j(x_j) = y_j \\ y_j L_j(x_i) = 0 \end{gather*} $$
Alors, ce polynôme résultant :
fera bien correspondre chaque image à son antécédent dans notre série de valeurs initale \( \Bigl \{ \bigl \{x_0, y_0 \bigr\}, \bigl \{x_1, y_1 \bigr\}, ..., \bigl \{x_n, y_n \bigr\} \Bigr\} \) .
Soit finalement,
$$ L(X) = \sum_{j = 0}^n y_j \Biggl[ \prod_{\underset{i \neq j}{i=0}}^n \frac{X - x_i}{x_j - x_i} \Biggr]$$
Étant donné que notre jeu de données comporte \(n\) couple de valeurs, on aura le système \((S)\) en fonction de \(n\) :
$$ (S) \enspace \left \{ \begin{gather*} a_0 + a_1 x_0 + a_2 x_0 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_0 ^n = y_0 \\ a_0 + a_1 x_1 + a_2 x_1 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_1 ^n = y_1 \\ ........................ ............\\ a_0 + a_1 x_n + a_2 x_n ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_n ^n = y_n \\ \end{gather*} \right \} $$
Il est inutile de prendre un polynôme de degré supérieur à \(n\), car dans les calculs il subsistera une ou plusieurs variables libres qui n'auront pas d'utilité.
On pourra procéder au moins deux manières différentes pour résoudre \( (S) \) :
- en résolvant directement le système \( (S) \) par substitution ou par un pivot de Gauss
- en résolvant le système matriciel \( (S^*) \) correspondant
Un système d'équations linéaires tel que le système \( (S) \) comporte une solution unique si et seulement si son système homogène associé \( (S_h) \) (c'est-à-dire sans second membre) comporte unique solution.
$$ (S_h) \enspace \left \{ \begin{gather*} a_0 + a_1 x_0 + a_2 x_0 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_0 ^n = 0 \\ a_0 + a_1 x_1 + a_2 x_1 ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_1 ^n =0 \\ ........................ ............\\ a_0 + a_1 x_n + a_2 x_n ^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n x_n ^n = 0 \\ \end{gather*} \right \} $$
Or, un polynôme est toujours nul si et seulement si tous ces coefficient sont nuls.
La solution du système \( (S_h)\) est alors unique et :
On en conclue alors que la solution du système \( (S)\) est elle aussi unique.
On résout alors ce système avec les valeurs \( \Bigl \{ \bigl \{x_0, y_0 \bigr\}, \bigl \{x_1, y_1 \bigr\}, ..., \bigl \{x_n, y_n \bigr\} \Bigr\}\) de la série, soit par substitution soit par un pivot de Gauss.
On obtiendra alors un polynôme unique :
Avec \( \bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) comme valeurs de la solution unique du système \( (S)\)
Il est possible de transposer ce système en système matriciel :
$$ (S^*) \enspace \Longleftrightarrow \enspace \underbrace{ \begin{pmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n \\ 1 & x_1 & x_1^2 & \dots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^n \\ \end{pmatrix} } _\text{X} \times \underbrace{ \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ . \\ a_n \\ \end{pmatrix} } _\text{A} = \underbrace{ \begin{pmatrix} y_0 \\ y_1 \\ y_2 \\ . \\ y_n \\ \end{pmatrix} } _\text{Y} $$
Avec un tel système, il existe une unique solution si et seulement sa matrice (ici \(X\)) est inversible. Et c'est le cas si son déterminant est non nul.
Ce qui sera le cas ici, car notre matrice est une matrice de Vondermonde, et la condition pour que son déterminant soit non nul est que les \(x_i \) soient deux-à-deux différents.
C'est le cas ici car notre série de valeurs comporte des \(x_i\) tous différents; la solution est donc unique.
On doit dans un premier temps calculer le déterminant générale de la matrice \(X\), ainsi que chaque déterminant particulier pour obtenir notre série de solutions \(\{ a_0, a_1, ..., a_n \}\), coefficients de nôtre polynôme à déterminer.
Où \(X_k\) représente la matrice carrée formée par la matrice \(X\) dans laquelle on a interverti sa \(k\)-ième colonne avec la matrice colonne \(Y\).
On obtiendra alors un polynôme unique :
Où \(X_k\) représente la matrice carrée formée par la matrice \(X\) dans laquelle on a interverti sa \(k\)-ième colonne avec la matrice colonne \(Y\).
Construisons un polynôme de dégré \(2\) à l'aide de cette méthode, et donnons-lui le jeu de données suivant sur trois points :
Construisons ce polynôme unique avec les deux possibilités vues plus haut :
- par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)
- par la construction d'un polynôme \(P_n(X)\), en trouvant l'unique solution pour les coefficients \(\bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) inconnues du système \( (S) \)
Nous avons trois polynômes à construire : \(L_0(X), L_1(X),L_2(X) \).
Selon la formule, chaque \(L_j(x)\) sera de la forme :
On a bien :
$$ \Biggl \{ \begin{gather*} L_0(x_0) = 1 \\ L_0(x_1) = 0, \enspace L_0(x_2) = 0 \end{gather*} $$
On a bien :
$$ \Biggl \{ \begin{gather*} L_1(x_1) = 1 \\ L_1(x_0) = 0, \enspace L_1(x_2) = 0 \end{gather*} $$
On a bien :
$$ \Biggl \{ \begin{gather*} L_2(x_2) = 1 \\ L_2(x_0) = 0, \enspace L_2(x_1) = 0 \end{gather*} $$
On peut alors construire notre polynôme en additionant les \(y_j L_j(X)\).
On cherche à résoudre le système \((S)\) suivant :
$$ (S) \enspace \left \{ \begin{gather*} a_0 + a_1 x_0 + a_2 x_0 ^2 = y_0 \\ a_0 + a_1 x_1 + a_2 x_1 ^2 = y_1 \\ a_0 + a_1 x_2 + a_2 x_2 ^2 = y_2 \\ \end{gather*} \right \} $$
Avec notre série de valeurs :
Soit,
$$ (S) \enspace \left \{ \begin{gather*} a_0 \hspace{5.5em} = 2 \qquad \hspace{0.5em} (L_1) \\ a_0 + \hspace{0.3em} a_1 \hspace{0.2em} + \hspace{0.2em} a_2 \hspace{0.4em} = -3 \qquad (L_2) \\ a_0 + 2a_1 + 4a_2 \hspace{0.1em} = 1 \qquad \hspace{0.7em} (L_3) \\ \end{gather*} \right \} \Longrightarrow a_0 = 2$$
Ensuite, on remplace dans les autres lignes \( a_0 \) par sa valeur :
$$ (S) \enspace \left \{ \begin{gather*} 2 + \hspace{0.3em} a_1 \hspace{0.2em} + \hspace{0.2em} a_2 \hspace{0.2em} = -3 \qquad (L_2) \\ 2 + 2a_1 + 4a_2 = 1 \qquad \hspace{0.6em} (L_3) \\ \end{gather*} \right \} $$
Avec \( (L_2) \), on a directement :
À ce stade, on injecte \( (a_1 = f(a_2)) \) dans \( (L_3) \) :
Enfin, on injecte \( (a_2) \) dans \( (L_2) \) :
On a comme solution unique pour \((S)\):
Soit le polynôme \(P_2(X) \) :
On cherche à résoudre le système matriciel \((S^*)\) suivant :
$$ (S^*) \enspace \Longleftrightarrow \enspace \begin{pmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n \\ 1 & x_1 & x_1^2 & \dots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^n \\ \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ . \\ a_n \\ \end{pmatrix} = \begin{pmatrix} y_0 \\ y_1 \\ y_2 \\ . \\ y_n \\ \end{pmatrix} $$
Soit dans notre cas :
$$ (S^*) \enspace \Longleftrightarrow \enspace \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2& 4 \\ \end{pmatrix} \times \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ \end{pmatrix} = \begin{pmatrix} 2 \\ \hspace{-0.8em} -3 \\ 1\\ \end{pmatrix} $$
On calcule \(det(X)\), le déterminant de la matrice \(X\).
$$ det(X) = \begin{vmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 2& 4 \\ \end{vmatrix} $$
$$ det(X) = 1\times \begin{vmatrix} 1 &1 \\ 2 & 4 \\ \end{vmatrix} -0 \times \begin{vmatrix} 1 &1 \\ 1 & 4 \\ \end{vmatrix} +0 \times \begin{vmatrix} 1 &1 \\ 1 &2 \\ \end{vmatrix} $$
Pour obtenir \(X_1 \), on remplace la \(1 ^{ière}\) colonne de la matrice \(X\) par \(Y\).
$$ X_1 = \begin{pmatrix} 2 & 0 & 0 \\ \hspace{-0.8em} -3 & 1 & 1 \\ 1 & 2& 4 \\ \end{pmatrix} $$
Puis on calcule son déterminant :
$$ det(X_1) = \begin{vmatrix} 2 & 0 & 0 \\ \hspace{-0.8em} -3 & 1 & 1 \\ 1 & 2& 4 \\ \end{vmatrix} $$
$$ det(X_1) = 2\times \begin{vmatrix} 1 &1 \\ 2 & 4 \\ \end{vmatrix} -0 \times \begin{vmatrix} -3&1 \\ \hspace{0.5em} 1 & 4 \\ \end{vmatrix} +0 \times \begin{vmatrix} -3 &1 \\ \hspace{0.5em} 1 &2 \\ \end{vmatrix} $$
Pour obtenir \(X_2 \), on remplace la \(2 ^{nde}\) colonne de la matrice \(X\) par \(Y\).
$$ X_2 = \begin{pmatrix} 1 & 2 & 0 \\ 1 & \hspace{-0.8em} -3 & 1 \\ 1 & 1& 4 \\ \end{pmatrix} $$
Puis on calcule son déterminant :
$$ det(X_2) = \begin{vmatrix} 1 &2 & 0 \\ 1 & \hspace{-0.8em} -3 & 1 \\ 1 & 1& 4 \\ \end{vmatrix} $$
$$ det(X_2) = 1\times \begin{vmatrix} \hspace{-0.8em} -3 &1 \\ 1 & 4 \\ \end{vmatrix} -2\times \begin{vmatrix} 1&1 \\ 1 & 4 \\ \end{vmatrix} +0 \times \begin{vmatrix} 1& \hspace{-0.8em} -3 \\ 1 & 1 \\ \end{vmatrix} $$
Pour obtenir \(X_3 \), on remplace la \(3 ^{ième}\) colonne de la matrice \(X\) par \(Y\).
$$ X_3 = \begin{pmatrix} 1 & 0 & 2 \\ 1 & 1 & \hspace{-0.8em} -3\\ 1 & 2& 1 \\ \end{pmatrix} $$
Puis on calcule son déterminant :
$$ det(X_3) = \begin{vmatrix} 1 & 0 & 2 \\ 1 & 1 & \hspace{-0.8em} -3\\ 1 & 2& 1 \\ \end{vmatrix} $$
$$ det(X_3) = 1\times \begin{vmatrix} 1 & \hspace{-0.8em} -3 \\ 2 & 1 \\ \end{vmatrix} -0\times \begin{vmatrix} 1& \hspace{-0.8em} -3 \\ 1 & 1 \\ \end{vmatrix} +2 \times \begin{vmatrix} 1& 1\\ 1 & 2 \\ \end{vmatrix} $$
On a comme solution unique pour \((S^*)\) :
Soit le polynôme \(P_2(X) \) :
On a trouvé pour les trois cas précédents un polynôme de degré 2 :
Vérifions à présent que notre polynôme vérifie bien les trois points de nos conditions initiales :
On a :
On a bien vérifié que :
$$ \Biggl \{ \begin{gather*} P_2(x_0) = y_0 \\ P_2(x_1) = y_1 \\ P_2(x_2) = y_2 \end{gather*} $$
On obtient finalement une courbe lissée correspondante à notre interpolation :
Retour en haut de page
