Index des cours

L'interpolation polynomiale Lagrangienne

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 :

  1. Par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)
  2. $$ \forall (i, j) \in \hspace{0.05em} \mathbb{N}^2, \enspace \forall X \in \mathbb{R}, $$

    $$ 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]$$

  3. Par la construction d'un polynôme \(P_n(X)\), en trouvant l'unique solution pour les \(\bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) inconnues du système \( (S) \)

  4. $$ (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 \} $$

    1. En résolvant directement le système par substitution ou par un pivot de Gauss

    2. $$ P_n(X) = a_0 + a_1 X + a_2 X^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n X^n$$

      Avec \( \bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) comme valeurs de la solution unique du système \( (S)\)


    3. En résolvant l'équivalent en produit matriciel

    4. $$ (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à :

      $$ P_n(X) = a_0 + a_1 X + a_2 X^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n X^n$$

      $$ \forall k \in [\![ 0, n]\!], \enspace a_k = \frac{det(X_k)}{det(X)}$$

      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\).


Démonstration


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

$$ \Bigl \{ \bigl \{x_0, y_0 \bigr\}, \bigl \{x_1, y_1 \bigr\}, ..., \bigl \{x_n, y_n \bigr\} \Bigr\} $$

Et tel que la figure ci-dessous en exemple :

Interpolation polynomiale Langrangienne - fonction polynomiale à déterminer correspondant à une série de valeurs donnée

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 :

$$ \forall i \in [\![ 0, m]\!] , \enspace \exists a_i \in \mathbb{R}, \enspace a_m \neq 0, \enspace \forall X \in \mathbb{R},$$

$$ P_m(X) = a_0 + a_1 X + a_2 X^2 + \hspace{0.1em}... \hspace{0.1em}+ a_m X^m$$

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 deux manières de générer ce polynôme \(L(X)\) :

  1. - Par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)

  2. - Par la construction d'un polynôme \(P_n(X)\), en trouvant l'unique solution pour les \(\bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) inconnues du système \( (S) \)


  1. Par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)

  2. 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 \end{gather*} $$

    Nous allons donc construire chaque polynôme un à un.

    Pour tout \( j \in [\![ 0, n]\!] \), il faut que les \( x_i \ ( i\neq j) \) soient racines pour que ce polynôme \( L_j(x_i) \) s'annule.

    Soit,

    $$ L_j(X) = \prod_{\underset{i \neq j}{i=0}}^n (X - x_i)$$

    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 à ce moment.

    Soit,

    $$ L_j(X) = \prod_{\underset{i \neq j}{i=0}}^n \frac{X - x_i}{x_j - x_i} $$

    Le fait d'ajouter un dénominateur ne change rien à la condition installée précedémment.

    La condition \( i \neq j \) nous assure bien que le dénominateur ne sera jamais nul.

    En 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 :

    $$ L(X) = y_0 L_0(X) + y_1 L_1(X) + \hspace{0.1em}... \hspace{0.1em}+ y_n L_n(X) $$

    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,

    $$ \forall (i, j) \in \hspace{0.05em} \mathbb{N}^2, \enspace \forall X \in \mathbb{R}, $$

    $$ 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]$$


  3. Par la construction d'un polynôme \(P_n(X)\), en trouvant l'unique solution pour les \(\bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) inconnues du système \( (S) \)

  4. É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 deux manières différentes pour résoudre \( (S) \) :

    1. - En résolvant directement le système par substitution ou par un pivot de Gauss

    2. - En résolvant l'équivalent en produit matriciel


    1. En résolvant directement le système par substitution ou par un pivot de Gauss

    2. 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 nul si et seulement si tous ces coefficient sont nuls.

      La solution du système \( (S_h)\) est alors unique :

      $$ \forall i \in [\![ 0, n]\!], \enspace \mathcal{S}_h \hspace{0.1em}= \Bigl\{ a_i =0 \Bigr\}$$

      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 :

      $$ P_n(X) = a_0 + a_1 X + a_2 X^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n X^n$$

      Avec \( \bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) comme valeurs de la solution unique du système \( (S)\)

    3. En résolvant l'équivalent en produit matriciel

    4. Il est possible de transposer ce système en produit 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} $$

      $$ (S)\Longleftrightarrow X \times A = 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.

      Ce'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.

      $$ \forall k \in [\![ 0, n]\!], \enspace a_k = \frac{det(X_k)}{det(X)}$$

      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 :

      $$ P_n(X) = a_0 + a_1 X + a_2 X^2 + \hspace{0.1em}... \hspace{0.1em}+ a_n X^n$$

      $$ \forall k \in [\![ 0, n]\!], \enspace a_k = \frac{det(X_k)}{det(X)}$$

      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\).


Exemple


Construction d'un polynôme du second de dégré

Construisons un polynôme de dégré \(2\) à l'aide de cette méthode.

Donnons-lui les caractéristiques suivantes sur trois points :

$$\Bigl \{ \bigl \{x_0 = 0, y_0 = 2 \bigr\}, \bigl \{x_1 =1, y_1 = -3 \bigr\}, \bigl \{x_2 = 2, y_2 = 1 \bigr\} \Bigr\} $$

Interpolation polynomiale Langrangienne - exemple 1

Construisons ce polynôme avec les deux possibilités vues plus haut :

  1. - Par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)

  2. - Par la construction d'un polynôme \(P_n(X)\), en trouvant l'unique solution pour les \(\bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) inconnues du système \( (S) \)


  1. Par la construction directe d'un polynôme \(L(X) = \sum L_j(X)\)

  2. 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 :

    $$ L_j(x) = \prod_{\underset{i \neq j}{i=0}}^n \frac{X - x_i}{x_j - x_i} $$

  3. Par la construction d'un polynôme \(P_n(X)\), en trouvant l'unique solution pour les \(\bigl \{a_0, \ a_1, \ ..., \ a_n \bigr\} \) inconnues du système \( (S) \)


    1. En résolvant directement le système par substitution ou par un pivot de Gauss
    2. 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 :

      $$\Bigl \{ \bigl \{x_0 = 0, y_0 = 2 \bigr\}, \bigl \{x_1 =1, y_1 = -3 \bigr\}, \bigl \{x_2 = 2, y_2 = 1 \bigr\} \Bigr\} $$

      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 :

      $$ a_1 + a_2 = -5 \Longleftrightarrow a_1 = -5- a_2 \qquad (a_1 = f(a_2)) $$

      On injecte \( (a_1 = f(a_2)) \) dans \( (L_3) \) :

      $$ 2 + 2(-5- a_2 ) + 4a_2 = 1 $$

      $$ -10 -2a_2 + 4a_2 = 1 - 2 $$

      $$ a_2 = \frac{9}{2} \qquad (a_2)$$

      Enfin, on injecte \( (a_2) \) dans \( (L_2) \) :

      $$ 2 + \hspace{0.3em} a_1 \hspace{0.2em} + \hspace{0.2em} \frac{9}{2} \hspace{0.2em} = -3 $$

      $$ a_1 = -\frac{19}{2} $$

      On a comme solution unique pour \((S)\):

      $$\mathcal{S} = \Bigl \{ a_0 = 2, \enspace a_1 = -\frac{19}{2},\enspace a_2 = \frac{9}{2} \Bigr\} $$

      Soit le polynôme \(P_2(X) \) :

      $$ P_2(X) = \frac{9}{2}X^2 - \frac{19}{2}X + 2 $$


    3. En résolvant l'équivalent en produit matriciel
    4. On cherche à résoudre le produit matriciel :

      $$ (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} $$

      $$ (S)\Longleftrightarrow X \times A = Y $$

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


  4. Vérification

  5. On a trouvé pour les trois cas précédents un polynôme de degré 2 :

    $$ P_2(X) = \frac{9}{2}X^2 - \frac{19}{2}X + 2 $$

    Vérifions que notre ploynôme vérifient bien les trois points de nos conditions initiales :

    $$\Bigl \{ \bigl \{x_0 = 0, y_0 = 2 \bigr\}, \bigl \{x_1 = 0, y_1 = -3 \bigr\}, \bigl \{x_2 = 2, y_2 = 1 \bigr\} \Bigr\} $$

    $$ P_2(x_0) = 0 - 0 + 2 = 2$$

    $$ P_2(x_1) = \frac{9}{2} - \frac{19}{2} +2 = -3$$

    $$ P_2(x_2) = \frac{36}{2} - \frac{38}{2} + 2 = -1 +2 = 1$$

    On a bien :

    $$ \Biggl \{ \begin{gather*} P_2(x_0) = y_0 \\ P_2(x_1) = y_1 \\ P_2(x_2) = y_2 \end{gather*} $$

Index des cours
Retour en haut de page