Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Calcul Scientiﬁque TP2 corrig? October 6, 2019 1 TP2 : Interpolation polynomial

Calcul Scientiﬁque TP2 corrig? October 6, 2019 1 TP2 : Interpolation polynomiale 1.1 Objectif L’objectif de ce TP est : • d’interpoler un nombre de points donné par un polynôme en utilisant les méthodes d’interpolation de Lagrange et Newton, • d’étudier l’évolution de l’erreur d’interpolation, d’une fonction, en fonction du nombre de points à interpoler. 1.2 Rappel sur l’interpolation Soient n + 1 points (x0, y0), (x1, y1) .. . .. (xn, yn). Interpoler ces points correspond à déterminer le polynôme P ∈Rn[X] passant par ces derniers : ∀i ∈{0, · · · , n}, P(xi) = yi. Les abscisses (xi)0≤i≤n et les ordonnées (yi)0≤i≤n sont appelées, respectivement, les points et les valeurs d’interpolation. Pour interpoler une fonction f, on déﬁnit ses valeurs d’interpolation comme suit : yi = f (xi), ∀0 ≤i ≤n. Dans ce qui suit, nous présentons deux méthodes d’interpolation : par les polynômes de Lagrange et par les polynômes de Newton. 2 Pôlynomes d’interpolation de Lagrange 2.1 Théorème Soient n + 1 points de coordonnées (xi, yi)0≤i≤n tels que xi ̸= xj, pour 0 ≤i, j ≤n et i ̸= j. Il existe alors un unique polynôme d’interpolation de Lagrange Pn ∈Rn[X] vériﬁant Pn(xi) = yi, ∀i ∈{0, · · · , n}. Ce polynôme s’exprime comme : Pn(x) = n ∑ i=0 yiLi(x), x ∈R où Li(x) = n ∏ j=0 j̸=i x −xj xi −xj . 1 La famille de polynômes de Lagrange {L0, L1, · · · , Ln} associés aux points (xi, yi)0≤i≤n est une base de l’ensemble Rn[X]. Ecrire une fonction Lagrange(t,i,x) qui évalue, au point t, le polynôme de Lagrange Li, i ∈{0, · · · , n} associé aux points d’interpolation x = (xi)0≤i≤n. [1]: import numpy as np import matplotlib.pyplot as plt [2]: def Lagrange(t,i,x): n=len(x) L=1 for j in np.arange(0,n): if j!=i: L*=(t-x[j])/(x[i]-x[j]) return L Tester la fonction Lagrange(t,i,x)sur les points {−1, 0, 1}. Représenter les polynômes L0, L1 et L2 sur $[-1,1]$. [3]: x=np.arange(-1,2,1) t=np.linspace(-1,1,21) # permet dobtenir un tableau 1D allant de -1 à 1␣ , →contenant 21 éléments. plt.figure(figsize=(20,10)) plt.plot(t,Lagrange(t,0,x),'ro--',t,Lagrange(t,1,x),'b^--',t,␣ , →Lagrange(t,2,x),'g*--',linewidth=3,markersize=12) plt.xlabel('t',fontsize=30) plt.xticks(fontsize=20) plt.yticks(fontsize=20) plt.legend(('L0','L1','L2'),fontsize=20, loc = 0) plt.grid(True) plt.text(-1,-0.1,"(-1,0)",ha="center",va="top",fontsize=30) plt.text(0,-0.1,"(0,0)",ha="center",va="top",fontsize=30) plt.text(1,-0.1,"(1,0)",ha="center",va="top",fontsize=30) plt.text(-1,1.05,"(-1,1)",ha="center",va="bottom",fontsize=30) plt.text(0,1.05,"(0,1)",ha="center",va="bottom",fontsize=30) plt.text(1,1.05,"(1,1)",ha="center",va="bottom",fontsize=30) [3]: Text(1, 1.05, '(1,1)') 2 Ecrire une fonction Interpolation_Labgrange(t,x,y) qui évalue, au point t, le polynôme d’interpolation P de Lagrange associé aux points d’interpolation (xi, yi)0≤i≤n, avec x = (xi)0≤i≤n et y = (yi)0≤i≤n. Représeneter ensuite le polynôme P graphiquement qui interpole les points (−1, 8), (0, 3) et (1, 6). [4]: def Interpolation_Lagrange(t,x,y): n=len(x) P=np.zeros((len(t))) for i in np.arange(0,n): P+=y[i]*Lagrange(t,i,x) return P [5]: y=[8,3,6] P=Interpolation_Lagrange(t,x,y) plt.figure(figsize=(20,10)) plt.plot(t,P,'mo--',linewidth=3,markersize=12) plt.xlabel('t',fontsize=30) plt.xticks(fontsize=20) plt.yticks(fontsize=20) plt.grid(True) plt.legend(('Polynome d\'interpolation de Lagrange',),fontsize=20, loc = 0) plt.text(-1,8.5,"(-1,8)",ha="center",va="top",fontsize=30) plt.text(0,3.5,"(0,3)",ha="center",va="top",fontsize=30) plt.text(1,6.5,"(1,6)",ha="center",va="top",fontsize=30) [5]: Text(1, 6.5, '(1,6)') 3 Exercice: 1. Interpoler, par la méthode de Lagrange, la fonction cos aux points d’interpolation : {−π, −π 2 , 0, π 2 , π}. 2. Sur [−3π 2 , 3π 2 ], tracer sur un même graphe la courbe de la fonction cos et P son polynôme d’interpolation de Lagrange associé aux points {−π, −π 2 , 0, π 2 , π}. 3. Interpréter les résultats. [6]: x=np.linspace(-np.pi,np.pi,5) t=np.linspace(-1.5*np.pi,1.5*np.pi,100) P=Interpolation_Lagrange(t,x,np.cos(x)) plt.figure(figsize=(20,10)) plt.plot(t,P,'r-',t,np.cos(t), 'b--',x,np.cos(x),'mo',linewidth=3,markersize=12) plt.xlabel('t',fontsize=30) plt.xticks(fontsize=20) plt.yticks(fontsize=20) plt.grid(True) plt.legend(('Polynome d\'interpolation de Lagrange', 'cosinus',␣ , →'points'),fontsize=20, loc = 0) [6]: <matplotlib.legend.Legend at 0x220b432fe80> 4 Inconvénient Un inconvénient majeur de la méthode d’interpolation par les polynômes de Lagrange réside en l’ajout d’un point (xn+1, yn+1) à l’ensemble de n points d’interpolation. Dans ce cas, il n’est numériquement pas évident de déduire Pn+1 de Pn. Tous les calculs seront refaits de zéro. D’où l’introduction de l’interpolation par les polynômes de Newton. 3 Pôlynomes d’interpolation de Newton 3.1 Théorème Soient n + 1 points de coordonnées (xi, yi)0≤i≤n tels que xi ̸= xj, pour 0 ≤i, j ≤n et i ̸= j. Il existe alors un unique polynôme d’interpolation de Newton Pn ∈Rn[X] vériﬁant Pn(xi) = yi, ∀i ∈{0, · · · , n}. Ce polynôme s’exprime comme : Pn(x) = n ∑ i=0 βiωi(x), x ∈R (1) = β0. 1 |{z} ω0 + β1(x −x0) | {z } ω1 + β2(x −x0)(x −x1) | {z } ω2 + .... + βn(x −x0)(x −x1)...(x −xn−1) | {z } ωn (2) où ωi(x) = i−1 ∏ j=0 (x −xi), ∀1 ≤i ≤n et ω0(x) = 1. La famille de polynômes de Newton {ω0, ω1, · · · , ωn} associés aux points (xi, yi)0≤i≤n forme une base de l’ensemble Rn[X]. Les réels βi, i ∈{0, · · · , n} correspondent aux coefﬁcients du polynôme. Pour les déterminer, nous utilisons la méthode des différences divisées. Ecrire une fonction Newton(t,i,x) qui évalue, au point t, le polynôme de Newton ωi, i ∈ {0, · · · , n} associé aux points d’interpolation x = (xi)0≤i≤n. 5 [7]: def Newton(t,i,x): n=len(x) if i==0: return np.ones((len(t))) else: W=1 for j in np.arange(0,i): W*=(t-x[j]) return W Tester la fonction Newton(t,i,x) sur les points {−1, 0, 1}. Représenter les polynômes ω0, ω1 et ω2 sur $[-1,1]$. [8]: x=np.arange(-1,2,1) t=np.linspace(-1,1,21) plt.figure(figsize=(20,10)) plt.plot(t,Newton(t,0,x),'ro--',t,Newton(t,1,x),'b^--',t,␣ , →Newton(t,2,x),'g*--',linewidth=3,markersize=12) plt.xlabel('t',fontsize=30) plt.xticks(fontsize=20) plt.yticks(fontsize=20) plt.legend(('W0','W1','W2'),fontsize=20, loc = 0) plt.grid(True) plt.text(-1,-0.1,"(-1,0)",ha="center",va="top",fontsize=30) plt.text(0,-0.1,"(0,0)",ha="center",va="top",fontsize=30) plt.text(1,-0.1,"(1,0)",ha="center",va="top",fontsize=30) plt.text(-1,1.05,"(-1,1)",ha="center",va="bottom",fontsize=30) plt.text(0,1.05,"(0,1)",ha="center",va="bottom",fontsize=30) plt.text(1,1.05,"(1,1)",ha="center",va="bottom",fontsize=30) [8]: Text(1, 1.05, '(1,1)') 6 3.2 Différences divisées 3.2.1 Déﬁnition On considère (n + 1) points (xi, yi)0≤i≤n, deux à deux distincts : 1. La différence divisée d’ordre 1 de xi−1 et xi, 0 < i ≤n est : f [xi−1, xi] = yi −yi−1 xi −xi−1 2. La différence divisée d’ordre n des n + 1 points est déﬁnie par récurrence entre deux dif- férences divisées d’ordre n −1 comme suit : f [x0, x1, · · · , xn] = f [x1, · · · , xn] −f [x0, x1, · · · , xn−1] xn −x0 3.2.2 Explication de la méthode des différences divisées pour le calcul des βi, 0 ≤i ≤n. Le polynome d’interpolation de Newton de degré n, Pn , évalué au point x0 donne Pn(x0) = n ∑ i=0 β0ωi(x0) = β0 = y0 = f [x0]. On note f [x0] = y0 la différence divisée d’ordre 0, correspondante à β0. De même, on évalue le polynome d’interpolation de Newton, Pn, au point x1. On obtient : Pn(x1) = n ∑ i=0 βiωi(x1) (3) = β0 + β1(x1 −x0) (4) = f [x0] + β1(x1 −x0) (5) = f [x1] = y1 (6) d’où β1 = f [x1] −f [x0] x1 −x0 = f [x0, x1] $ f[x_0, x_1]$ correspond à la différence divisée d’ordre 1. On procède par par récurrence pour obtenir : βk = f [x1, ..., xk] −f [x0, ...., xk−1] xk −x0 = f [x0, ..., xk] où f [x0, ..., xk] désigne la différence divisée d’ordre k. Ecrire une fonction diff_div(x,y)qui renvoit les coefﬁcients βi, i ∈{0, · · · , n} en utilisant la méthode des différences divisées. [9]: def diff_div(x,y): n=len(y) beta=y.copy() for i in np.arange(1,n): 7 for j in np.arange(n-1,i-1,-1): beta[j]=(beta[j]-beta[j-1])/(x[j]-x[j-i]) return beta Ecrire une fonction Interpolation_Newton(t,x,y) qui évalue, au point t, le polynôme d’interpolation de Newton associé aux points d’interpolation (xi, yi)0≤i≤n, avec x = (xi)0≤i≤n et y = (yi)0≤i≤n. Représeneter ensuite le polynôme P graphiquement qui interpole les points (−1, 8), (0, 3) et (1, 6). [10]: def Interpolation_Newton(t,x,y): n=len(x) P=np.zeros((len(t))) beta=diff_div(x,y) for i in np.arange(0,n): P+=beta[i]*Newton(t,i,x) return P [11]: P=Interpolation_Newton(t,x,y) plt.figure(figsize=(20,10)) plt.plot(t,P,'mo--',linewidth=3,markersize=12) plt.xlabel('t',fontsize=30) plt.xticks(fontsize=20) plt.yticks(fontsize=20) plt.grid(True) plt.legend(('Polynome d\'interpolation de Newton',),fontsize=20, loc = 0) plt.text(-1,8.5,"(-1,8)",ha="center",va="top",fontsize=30) plt.text(0,3.5,"(0,3)",ha="center",va="top",fontsize=30) plt.text(1,6.5,"(1,6)",ha="center",va="top",fontsize=30) [11]: Text(1, 6.5, '(1,6)') 8 3.3 Avantages du polynôme de Newton Un des avantages de la méthode de Newton pour l’interpolation des points (xi, yi)0≤i≤n, deux à deux distincts, est le suivant : si on note par Pk le polynôme d’interplation tronqué : le polynôme de degré inférieur ou égal à k, 0 ≤k ≤n, qui interpole que les points (xi, yi)0≤i≤k, exprimé dans la base de polynômes de Newton {ω1, · · · , ωk}, comme suit : Pk(x) = β0. 1 |{z} ω0 + β1(x −x0) | {z } ω1 + β2(x −x0)(x −x1) | {z } ω2 + ....+ βk(x −x0)(x −x1)...(x −xk−1) | {z } ωk , x ∈R, alors Pk+1, 0 ≤k < n, le polynôme tronqué de degré inférieur ou égal à k + 1 interpolant les points (xi, yi)0≤i≤k+1, sera exprimé en fonction de Pk comme suit : Pk+1(x) = Pk(x) + βk+1(x −x0)(x −x1)..(x −xk) | {z } ωk+1 . Par conséquent, si l’on connait le polynôme Pn, interpolant les points (xi, yi)0≤i≤n, et que l’on rajoute un point d’interpolation (xn+1, yn+1), alors le polynôme Pn+1 interpolant les n + 2 points sera déduit de celui interpolant les anciens n + 1 points comme suit : Pn+1(x) = Pn(x) + βn+1(x −x0)(x −x1)..(x −xn) | {z } ωn+1 . Les coefﬁcients β0, ..., βn resteront les mêmes, il sufﬁt de calculer le coefﬁcient βn+1 et de déduire le polynôme de Newton associé ωn+1 = ωn(x −xn). Exercice 1. Ecrire une fonction Interpolation_Newton_opt(t,x,y) qui optimise le calcul de la détermination du polynôme d’interpolation par la méthode de Newton. 2. Représeneter ensuite le polynôme P graphiquement qui interpole les points (−1, 8), (0, 3) et (1, uploads/Management/ tp2-interpolation-polynomiale-corrige.pdf