next up previous
Suite: Approximation polynômiale Sommaire: Analyse Retour: Interpolation rationnelle

Interpolation d'Hermite


\fbox {PRESENTATION}


L'interpolation de Lagrange, qui fournit facilement un polynôme prenant des valeurs données, présente l'inconvénient dans certains cas de donner une qualité médiocre : entre les points d'interpolation la différence entre une fonction et son polynôme d'interpolation peut être grande, même si le nombre de points tend vers l'infini (phénomène dit de Runge [2]). Pour remédier à cela on peut essayer d'utiliser non seulement les valeurs d'une fonction mais aussi celles de ses dérivées : c'est l'interpolation d'Hermite, qui est ici mise en oeuvre à l'ordre 1.


\fbox {SUJET}


1.Algorithme

On considère une fonction f dérivable sur R et des points $x_1,\dots,x_n$ distincts.

On note yi=f(xi) et $d_i=f^\prime(x_i)$ et on cherche un polynôme d'interpolation de f.

On pose

\begin{displaymath}
Q_j(x)=\prod_{k=1,k\ne j}^{k=n}(x-x_k)^2\end{displaymath}

Calculer $Q_j^\prime(x)$ et $Q_j^\prime(x_j)$.

On définit

\begin{displaymath}
P(x)=\sum_{j=1}^n{{\textstyle Q_j(x)}\over{\textstyle Q_j(x_...
 ...e(x_j)}\over{\textstyle Q_j(x_j)}}\right)y_j
+(x-x_j)d_j\right]\end{displaymath}

Montrer que pour $i=1,\dots,n$ on a P(xi)=yi et $P^\prime(x_i)=d_i$.

On cherche maintenant le polynôme P sous la forme développée

\begin{displaymath}
P(x)=\sum_{k=0}^m a_kx^k\end{displaymath}

Que vaut m ? Montrer que les coefficients ak sont solution d'un système linéaire dont on explicitera la dimension, les coefficients et le second membre.

2.Programmation

On dispose d'un programme qui calcule les valeurs du polynôme d'interpolation d'Hermite pour des points donnés $x_1,\dots,x_n$, des valeurs données $y_1,\dots,y_n$ et des dérivées $d_1,\dots,d_n$ initialisés par le programme pour la fonction exponentielle.

On utilise les 2 méthodes vues dans la partie 1. afin de comparer les résultats entre eux et avec les valeurs exactes.

Ecrire les procédures suivantes dont seul l'en-tête a été indiqué :


FUNCTION Hermite1(x,y,d: Vecteur; n: integer;t: real):Real;

qui retourne la valeur du polynôme d'interpolation d'Hermite au point t pour les valeurs données

x[1],...,x[n]  y[1],...,y[n]  d[1],...,d[n]


PROCEDURE HermiteP(x,y,d:Vecteur;n:integer;

    VAR Pol:Polynome;VAR M:INTEGER);

qui retourne dans M le degré du polynôme d'interpolation et dans Pol[0],..., Pol[m] ses coefficients

On utilisera pour cela la procédure

Gauss(N:INTEGER;A:Matrice;B:Vecteur;VAR X:Vecteur;VAR Err:BOOLEAN);

déjà définie dans le programme, qui résout le système AX=B en retournant la solution dans le vecteur X et en mettant le booléen Err à vrai si le système n'a pas de solution.


\fbox {CORRIGE}



$\bullet$ Partie théorique

En utilisant la dérivée logarithmique on a

\begin{displaymath}
Q_j^\prime(x)=Q_j(x)\sum_{k=1,k\ne j}^{k=n}{{\textstyle 2}\over{\textstyle x-x_k}}\end{displaymath}

D'où

\begin{displaymath}
Q_j^\prime(x_j)=Q_j(x_j)\sum_{k=1,k\ne j}^{k=n}{{\textstyle 2}\over{\textstyle x_j-x_k}}\end{displaymath}

Ce qui donne pour P :

\begin{displaymath}
P(x_i)=\sum_{j=1}^n{{\textstyle Q_j(x_i)}\over{\textstyle Q_...
 ...x_j)}\over{\textstyle Q_j(x_j)}}\right)y_j
+(x_i-x_j)d_j\right]\end{displaymath}

Mais dans la sommation les facteurs Qj(xi) sont nuls sauf pour j=i :

\begin{displaymath}
P(x_i)={{\textstyle Q_i(x_i)}\over{\textstyle Q_i(x_i)}}
\le...
 ...}\over{\textstyle Q_i(x_i)}}\right)y_i
+(x_i-x_i)d_i\right]=y_i\end{displaymath}

On dérive P :

\begin{displaymath}
P^\prime(x)=\sum_{j=1}^n
{{\textstyle Q_j^\prime(x)}\over{\t...
 ...e(x_j)}\over{\textstyle Q_j(x_j)}}\right)y_j
+(x-x_j)d_j\right]\end{displaymath}

\begin{displaymath}
+\sum_{j=1}^n{{\textstyle Q_j(x)}\over{\textstyle Q_j(x_j)}}...
 ...j^\prime(x_j)}\over{\textstyle Q_j(x_j)}}\right)y_j
+d_j\right]\end{displaymath}

$Q_j^\prime(x_i)$ s'annulant pour tous les $j\ne i$ on déduit :

\begin{displaymath}
P^\prime(x_i)=
{{\textstyle Q_i^\prime(x_i)}\over{\textstyle...
 ...e Q_i^\prime(x_i)}\over{\textstyle Q_i(x_i)}}y_i+d_i\right]=d_i\end{displaymath}

Chaque polynôme Qj est de degré 2n-2 donc P est de degré au plus 2n-1.

On a $P^\prime(x)=\sum_{k=1}^m ka_kx^{k-1}$ d'où le système de 2n équations aux inconnues ak :


$\bullet$ Programmation

FUNCTION Hermite1(xa,ya,da: Vecteur; n: integer;x: real):Real;
VAR i,j,k: integer;
    q,qk,s,y: real;
BEGIN
  y:=0;
  FOR K:=1 TO N DO
  BEGIN
    Q:=1; Qk:=1; S:=0;
    FOR J:=1 TO N DO IF J<>K THEN
    BEGIN
      Q:=Q*SQR(X-Xa[J]);
      Qk:=Qk*SQR(Xa[K]-Xa[J]);
      S:=S+1/(Xa[K]-Xa[J]);
    END;
    Y:=Y+Q/Qk*(Ya[K]+(X-Xa[K])*(Da[K]-2*S*Ya[K]));
  END;
  Hermite1:=Y;
END;

PROCEDURE HermiteP(x,y,d:Vecteur;n:integer;
             VAR Pol:Polynome;VAR Degre:INTEGER);
VAR M:Matrice;
    i,j:INTEGER;
    Z:Real;
    B,S:Vecteur;
    Err:BOOLEAN;
BEGIN
  B:=Y;
  FOR I:=1 TO N DO
  BEGIN
    M[I,1]:=1;
    FOR J:=2 TO 2*N DO M[I,J]:=X[I]*M[I,J-1];
  END;
  FOR I:=N+1 TO 2*N DO
  BEGIN
    B[I]:=D[I-N];
    M[I,1]:=0;
    Z:=1;
    M[I,2]:=Z;
    FOR J:=3 TO 2*N DO
    BEGIN
      Z:=Z*X[I-N];
      M[I,J]:=(J-1)*Z;
    END;
  END;
  Gauss(2*N,M,B,S,Err);
  IF Err THEN WRITELN('Erreur solution syst\`eme !');
  FOR I:=1 TO 2*N DO Pol[I-1]:=S[I];
  Degre:=2*N-1;
END;


\fbox {COMMENTAIRES}


L'interpolation d'Hermite pour des yi et di donnés est unique : en effet si R est un autre polynôme satisfaisant les mêmes conditions que P on a P-R qui s'annule ainsi que sa dérivée pour tous les xi. P-R est donc divisible par $\prod_{i=1}^n(x-x_i)^2$, ce qui donne P-R=0 car P-R est de degré 2n-1. Cette unicité assure le fait que le système linéaire obtenu est bien de Cramer.

En fait l'écriture de P est simplement le développement dans la base des Hi et KiHi et Ki satisfont

Sur le plan numérique, et si on n'a besoin que d'évaluations de P, la détermination des coefficients ak n'est pas conseillée et il est préférable d'utiliser la formule explicite de P.

On peut également développer une interpolation analogue à un ordre quelconque (utilisant des dérivées d'ordre supérieur) mais elle présente un intérêt limité sur le plan pratique.


next up previous
Suite: Approximation polynômiale Sommaire: Analyse Retour: Interpolation rationnelle
Jean-Louis Maltret
5/18/1998