Upload
others
View
4
Download
0
Embed Size (px)
Citation preview
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 1/28
In [1]:
Méthodes numériques
TD n° 1 - Interpolation polynomiale
Exercice 1
1) On considère les abscisses et . Parmi les polynômes suivants, lequel est lepolynôme d'interpolation aux points (justifiez votre réponse) ?
Correction : Tout d'abord, on remarque que le polynôme que l'on cherche doit satisfaire p(0) = 0. On peut doncdéjà éliminer de la liste. Ensuite, le polynôme d'interpolation de n points et de degré n-1. Ainsi, p doit être dedegré 3. Le polynôme d'interpolation aux points est donc . On vérifie tout de même que .
2) Représentez sur une même figure les points d'interpolation, ainsi que les polynômes , et respectivement en noir, vert et rouge, sur l'intervalle .
x = [−2, 0, 1, 2] y = [4, 0, 0, 4]
x, y
(x) = − − 3 + xp1 x4 2
3x3 x2 8
3
(x) = −p2
4
3x2 4
3
(x) = + − xp3
1
3x3 x2 4
3
p2
x, y p3 (x) = yp3
p1 p2 p3
[−2.5, 2.5]
%matplotlib inline
from matplotlib.pyplot import *
from numpy import *
#from scipy import *
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 2/28
In [2]:
Exercice 2
1) Montrez qu'il existe une infinité de polynômes de degré 2 dont le graphe passe par les points et .
Correction : Cherchons les polynômes de degré 2 tels que et . Cequi est équivalent au système linéaire
En le résolvant, on obtient sans condition sur , ce qui correspond bien à une infinité depolynômes de degré 2.
2) Montrez qu'il n'existe pas de polynôme de degré 2 passant par les points , , et .
Correction : Comme dans la question précédante, on cherche tels que , , et . Ce qui est équivalent au système linéaire
(0, 0) (1, 0)
p(x) = a + bx + cx2 p(0) = 0 p(1) = 0
{c = 0
a + b + c = 0
p(x) = ax(x − 1) a
(0, 1) (1, 4) (2, 15) (3, 40)
p(x) = a + bx + cx2 p(0) = 1
p(1) = 4 p(2) = 15 p(3) = 40
c = 1
a + b + c = 4
4a + 2b + c = 15
9a + 3b + c = 40
[ True True True False]
#On rentre les données de l'énoncé
x = array([-2,0,1,2])
y = array([4,0,0,4])
#Définissons les polynômes p1, p2 et p3 :
p1 = lambda x:x**4 - (2/3)*x**3 - 3*x**2 + (8/3)*x
p2 = lambda x:(4/3)*x**2 - (4/3)
p3 = lambda x:(1/3)*x**3 + x**2 - (4/3)*x
#Il n'y a plus qu'à tracer tout ça :
t = linspace(-2.5,2.5)
plot(t,p1(t),'k')
plot(t,p2(t),'g')
plot(t,p3(t),'r')
plot(x,y,'bo')
#Profitons en pour vérifier que p3 interpole bien (x,y)
print(y == p3(x))
#On obtient [True True True False]
#mais le False vient simplement d'un problème d'arrondi
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 3/28
En le résolvant, on trouve qu'il n'y a pas de solution, ce qui conclue la question.
Exercice 3
1) Calculez les polynômes d'interpolation aux points suivants :
a) et
b) et
c) et
d) et
e) et
Correction : Il y a plusieurs manières de calculer les polynômes d'interpolation. Premièrement, comme dansl'exercice 2 en résolvant un système linéaire. Sinon, on peut utiliser la forme de Lagrange. Voir le cours(https://perso.math.univ-toulouse.fr/fdelebec/files/2018/03/chap01-L2.pdf)
a)
b)
c)
d)
e)
2) Représentez graphiquement les polynômes des points a) et b), accompagnés des points d'interpolationcorrespondants.
x = [−1, 2, 3] y = [4, 4, 8]
x = [−2,−1, 0, 1] y = [0,−2,−4, 0]
x = [−1, 0, 1, 2] y = [6, 2, 0, 0]
x = [−1, 0, 1] y = [1, 0, 1]
x = [−3,−1, 2, 10] y = [−3,−1, 2, 10]
− x + 2x2
+ 3 − 4x3 x2
− 3x + 2x2
x2
x
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 4/28
In [3]:
Exercice 4
Soit un polynôme. Montrez que son polynôme d'interpolation aux nœuds , , est égal aureste de la division euclidienne de par le polynôme .
Correction : Ecrivons la division euclidienne de par :
p ∈ ℝxi 0 ≤ i ≤ n
p (x) = (x − ) (x − ) … (x − )πn x0 x1 xn
p πn
Out[3]:
[<matplotlib.lines.Line2D at 0x7f983e9371d0>]
#On commence par le polynôme de la question a)
xa = [-1,2,3]
ya = [4,4,8]
pa = lambda x:x**2-x+2
#Puis on définit le polynôme de la question b)
xb = [-2,-1,0,1]
yb = [0,-2,-4,0]
pb = lambda x:x**3+3*x**2-4
#Il n'y a plus qu'à les représenter. On discrétise nos abscisses et on plot
t = linspace(-3,4)
plot(xa,ya,'bo')
plot(t,pa(t),'b')
figure()
plot(xb,yb,'ro')
plot(t,pb(t),'r')
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 5/28
où et sont des polynômes avec
On veut donc montrer que est le polynôme d'interpolation aux nœuds , . Pour cela, il suffitde montrer
Or, on a ce qui conclue.
p(x) = (x) × q(x) + r(x)πn
q r deg r < deg p
r ∈ ℝxi 0 ≤ i ≤ n
r( ) = p( ), ∀i ∈ [[0; n]]xi xi
r(x) = p(x) − (x) × q(x) = p(x) − (x − ) (x − ) … (x − ) × q(x)πn x0 x1 xn
Exercice 5
Pour , on considère la matrice
1) Montrez que .
Correction:
Ainsi, en développant selon la première ligne, on a
On conclut par récurrence
2) Soit . Montrez qu'il existe un unique polynôme tel que si et seulementsi pour tout .
Correction : On doit démontrer une équivalence. Pour ce faire, on démontre une implication puis l'autre.L'implication de droite à gauche est un théorème du cours. Pour l'autre sens, on le montre par contraposée : onva montrer :
Si tq , alors il n'existe pas un unique polynôme tel que .
Supposons donc qu'il existe et distincts tels que . Il y a alors deux cas possibles :
( , … , ) ∈x0 xn ℝn+1
V( , … , ) = .x0 xn
1
1
⋮
⋮
1
x0
x1
⋮
⋮
xn
x20
x21
⋮
⋮
x2n
…
…
…
…
…
xn0
xn1
⋮
⋮
xnn
det(V( , … , )) = ( − )x0 xn ∏(i,j), 0≤i<j≤n
xj xi
|
|
||||||||
1
1
⋮
1
x0
x1
⋮
xn
x20
x21
⋮
x2n
…
…
…
xn0
xn1
⋮
xnn
|
|
||||||||
=→ −Ci Ci x0Ci
|
|
|||||||
1
1
⋮
1
0
−x1 x0
⋮
−xn x0
0
−x21 x0x1
⋮
−x2n x0xn
…
…
…
0
−xn1 x0xn−11
⋮
−xnn x0xn−1n
|
|
|||||||
|
|
||||||||
1
1
⋮
1
x0
x1
⋮
xn
x20
x21
⋮
x2n
…
…
…
xn0
xn1
⋮
xnn
|
|
||||||||
=
|
|
|||||
−x1 x0
⋮
−xn x0
( − )x1 x1 x0
⋮
( − )xn xn x0
…
…
( − )xn−11 x1 x0
⋮
( − )xn−1n xn x0
|
|
|||||
det(V( , … , )) = ( − ) … ( − )x0 xn x1 x0 xn x0
|
|
|||||
1
⋮
1
x1
⋮
xn
…
…
xn−11
⋮
xn−1n
|
|
|||||
( , … , ) ∈y0 yn ℝn p ∈ ℝn p( ) =xi yi
≠xi xj (i, j), i ≠ j
∃(i, j), i ≠ j =xi xj p ∈ ℝn p( ) =xi yi
i j =xi xj
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 6/28
1. il n'existe pas de fonction telle que et .2. On a points d'interpolation. Il y a donc un unique polynôme d'interpolation de degré au plus
mais une infinité de polynôme d'interpolation de degré (raisonner avec le système linéaire)
3) Écrire un programme PolIntLag(Xint,Yint) qui calcule les coefficients dans la base canonique de du polynôme d'interpolation de Lagrange aux points et , en utilisant lamatrice .
≠yi yj p( ) =xi yi p( ) =xi yj=yi yj n
n − 1 n
ℝn
= ( , … , )Xint x0 xn = ( , … , )Yint y0 ynV
In [4]:
4) Écrire une fonction EvalPol(Xpol,Coef) qui retourne l'ensemble des valeurs prises par le polynôme aux points de .p(x) = Coef [0] + Coef [1] x + Coef [2] + … + Coef [n]x2 xn = ( , … , )Xpol X0 XM
In [5]:
Exercice 6
Trouvez et représentez graphiquement le polynôme de degré inférieur ou égal à 4 tel que
a) , , , ,
b) , , , , .
p
p(−2) = 11 p(−1) = 1 p(0) = 1 p(1) = 5 p(2) = 31
p(−1) = 1 (−1) = −1p′ p(0) = 0 p(1) = 1 (1) = 1p′
[ 0. 1. 0. -0.]
[0. 1. 2. 3. 4.]
def PolIntLag(Xint,Yint):
N = Xint.size
Coef = zeros([N,1])
V = zeros([N,N])
for kk in range(N):
V[:,kk] = Xint**kk
Coef = linalg.solve(V, Yint)
return Coef
#Test avec le polynôme f(x) = x
x = array([0,1,2,3])
y = array([0,1,2,3])
a = PolIntLag(x,y)
print(around(a))
def EvalPol(Xpol,Coef):
N = Coef.size
Ypol = zeros(Xpol.shape)
for kk in range(N):
Ypol = Ypol + Coef[kk]*Xpol**kk
return Ypol
#Test avec les résultats précédants
print(EvalPol(array([0,1,2,3,4]),array([0,1,0,0])))
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 7/28
In [6]:
Exercice 7
Soit (n+1) réels distincts deux à deux. Pour , on note
le -ième polynôme de Lagrange.
1) Montrez que est un polynôme de degré vérifiant pour tout .
Correction : Voir cours (https://perso.math.univ-toulouse.fr/fdelebec/files/2018/03/chap01-L2.pdf)
2) En déduire que la famille de polynôme forme une base de .
Correction : Voir cours (https://perso.math.univ-toulouse.fr/fdelebec/files/2018/03/chap01-L2.pdf)
, … ,x0 xn k ∈ {0, … , n}
(x) =Lk ∏j∈{0,…,n},j≠k
x − xj
−xk xj
k
Lk n ( ) =Lk xi δki k, i ∈ {0, … , n}
{ }Lk k∈{0,…,n} [X]ℝn
Out[6]:
[<matplotlib.lines.Line2D at 0x7f983e8fc470>]
#a)On calcule les coefficients du polynôme d'interpolation
xa = array([-2,-1,0,1,2])
ya = array([11,1,1,5,31])
a = PolIntLag(xa,ya)
#On le représente
t = linspace(-3,3)
pa = lambda x:a[4]*x**4 + a[3]*x**3 + a[2]*x**2 + a[1]*x + a[0]
plot(t,pa(t),'b')
plot(xa,ya,'bo')
#b) Ici, les conditions initiales sont différentes.
#Il y a 5 conditions initiales, mais 2 d'entre elles portent sur la dérivée de p
#Il faut donc procéder différemment :
#on pose p(x) = a_4x^4 + a_3x^3 + a_2x^2 + a_1x^1 + a_0
#Et en posant les conditions initiales,
#on obtient un système linéaire qu'on peut résoudre
#Finalement, on obtient p(x) = -(1/2)x^4+(3/2)x^2
pb = lambda x:-(1/2)*x**4+(3/2)*x**2
plot(t,pb(t),'r')
plot(-1,1,'ro')
plot(0,0,'ro')
plot(1,1,'ro')
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 8/28
3) Écrire une fonction PolLagrange(Xpol,Xint,k) qui calcule les valeurs prises par le -ième polynômede la base de Lagrange associé aux abscisses , en les points .
k
= ( , … , )Xint x0 xn = ( , … , )Xpol X0 XM
In [7]:
4) Écrire une fonction PolIntLag2(Xpol,Xint,Yint) qui calcule les valeurs prises aux points par le polynôme d'interpolation de Lagrange aux abscisses et
.= ( , … , )Xpol X0 XM = ( , … , )Xint x0 xn= ( , … , )Yint y0 yn
In [8]:
Exercice 8 (examen 2016)
Soient et des réels donnés , . On considère le polynôme d'interpolationsatisfaisant
1) Montrez que le polynôme est pair. Indication : on pourra écrire dans la base de Lagrange
Note : La correction suivante peut paraître lourde car elle utilise les notations avec les indices. Pour ne pas seperdre, il peut être utile et formateur de la reprendre sur un exemple avec un petit ( =3 par exemple).
= 0 < < … <x0 x1 xn yi 0 ≤ i ≤ n
P( ) = , P(− ) = P( ) = , 1 ≤ i ≤ n.x0 y0 xi xi yi
P P
n n
[ 1. -0.]
[0. 1. 2. 3.]
def PolLagrange(Xpol,Xint,k):
#On initialise les données
n = size(Xint)
x_k = Xint[k]
#On initialise notre produit L_k à 1
L_k = ones(size(Xpol))
for j in range(n) :
if j != k:
#Pour chaque j différent de k,
#je multiplie mon produit précédant, L_k par (x-x_j)/(x_k-x_j)
L_k = L_k*(Xpol-Xint[j])/(x_k-Xint[j])
return L_k
#Testons le sur un exemple simple x = [0,1] Normalement L_0(x) = -(x-1)
x = array([0,1])
print(PolLagrange(x,x,0))
def PolIntLag2(Xpol,Xint,Yint):
#On sait que le polynôme d'interpolation s'exprime dans la base de Lagrange,
#on peut donc utiliser PolLagrange
n = size(Xint)
#On initialise notre polynôme d'interpolation à 0
p = zeros(size(Xpol))
for k in range(n):
#On rajoute à p sa coordonnée en le k-ième polynôme de Lagrange
p = p + Yint[k]*PolLagrange(Xpol,Xint,k)
return p
#Testons le à nouveau sur l'exemple x=[0,1] et y = [0,1]
print(PolIntLag2(array([0,1,2,3]),x,x))
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 9/28
Correction : Les conditions que l'on impose au polynôme d'interpolation reviennent à se donner et demander : On a donc noeuds
d'interpolations.
Commençons par calculer :
Calculons le -ième polynôme de Lagrange :
Maintenant, si on isole la contribution de , on obtient :
où est une constante dont on ne se soucie pas (le multiple d'une fonction paire reste paire)
On peut maintenant "pairer" les termes de degré 1 deux à deux :
On en déduit de plus que
Ainsi, si on exprime dans la base de Lagrange, en demandant , on a :
En joignant ce que l'on a montré précédemment, on obtient :
On remarque que les termes de la somme sont tous des polynômes contenant uniquement des puissancespaires. Par somme, est donc pair.
2) En déduire en un minimum de calculs le polynôme d'interpolation vérifiant , , .
Correction : En utilisant la question précédante, on sait que le polynôme d'interpolation que l'on cherche est unpolynôme de degré au plus 2 pair. On peut donc l'écrire :
En imposant les conditions de la questions, on obtient donc le système suivant :
:= − et := , 1 ≤ i ≤ nx−i xi y−i yi P( ) = − n ≤ i ≤ nxi yi 2n + 1
L0
(x) = = ×L0 ∏j∈{−n,…,n},j≠0
x − xj
−xk xj ∏j∈{−n,…,−1}
x − xj
−xk xj ∏j∈{1,…,n}
x − xj
−xk xj
(x) = K (x − )(x + ) = K ( − ) où K est une constanteL0 ∏j∈{1,…,n}
xj xj ∏j∈{1,…,n}
x2 x2j
k
(x) = = × ×Lk ∏j∈{−n,…,n},j≠k
x − xj
−xk xj ∏j∈{−n,…,−1},j≠k
x − xj
−xk xj
x − x0
−xk x0∏
j∈{1,…,n},j≠k
x − xj
−xk xj
x−k
(x) = Cx × (x − ) × (x − ) × (x − )Lk x−k ∏j∈{−n,…,−1},j≠k,j≠−k
xj ∏j∈{1,…,n},j≠k,j≠−k
xj
C
(x) = C( − x ) × (x − )(x − ) = C( + x ) × ( − )Lk x2 x−k ∏j∈{1,…,n},j≠k,j≠−k
xj x−j x2 xk ∏j∈{1,…,n},j≠k,j≠−k
x2 x2j
(x) = C( − x ) × ( − )L−k x2 xk ∏j∈{1,…,n},j≠k,j≠−k
x2 x2j
P := , 1 ≤ i ≤ ny−i yi
P(x) = (x) × = (x) + (x) × + (x) ×∑k=−n
n
Lk yk L0 y0 ∑k=−n
−1
Lk yk ∑k=1
n
Lk yk
P(x) = (x) + ( (x) + (x))L0 y0 ∑k=1
n
yk Lk L−k
P(x) = (x) + C ( ( − )) ( + x + − x )L0 y0 ∑k=1
n
yk ∏j∈{1,…,n},j≠k,j≠−k
x2 x2j x2 xk x2 xk
P(x) = K ( − ) + 2C ( ( − ))∏j∈{1,…,n}
x2 x2j ∑
k=1
n
ykx2
∏j∈{1,…,n},j≠k,j≠−k
x2 x2j
P
P(−1) = 2 P(0) = 4 P(1) = 2
P(x) = a + bx2
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 10/28
d'où
{a + b = 2
b = 4
P(x) = −2 + 4x2
Exercice 9 (examen 1999)
1) Calculez le polynôme d'interpolation de Lagrange de la fonction relativement aux points , et .
Correction : On cherche tel que et . On cherche doncun polynôme de degré au plus 2 ayant pour racines 1 et -1. Autrement dit, est de la forme
En imposant la condition , on obtient
2) Même question en rajoutant le point .
Correction : Cette fois, on cherche un polynôme de degré au plus 3, ayant pour racines -1 et 1. Autrement dit, est de la forme
où est la troisième racine réelle de (exercice : pourquoi est réel ?)
Mais on peut aussi chercher sous la forme
En effet, le premier terme s'assure et grâce à laquestion précédante et le second terme ne contribue ni pour ou puisqu'il s'annule en cespoints. Le second terme s'assure également que est bien de degré au plus 3.
En imposant , on obtient d'où
Sinon... On cherche un polynôme de degré 3 qui interpole la fonction qui est elle-même unpolynôme de degré 3. Le polynôme que l'on cherche est donc elle-même !
f (x) = x ( − 1)x2
= −1x0 = 1x1 = 2x2
P P(−1) = f (−1) = 0,P(1) = f (1) = 0 P(2) = f (2)6
P
P(x) = a(x − 1)(x + 1)
P(2) = 6 P(x) = 2( − 1)x2
= −2x3
P
P(x) = P(x) = a(x − b)(x − 1)(x + 1)
b P b
P
P(x) = 2(x − 1)(x + 1) + (x − 1)(x + 1)(x − 2)a
P(−1) = f (−1) = 0,P(1) = f (1) = 0 P(2) = f (2)6
P(−1),P(1) P(2)
P
P(−2) = −6 a = 1
P(x) = 2(x − 1)(x + 1) + (x − 1)(x + 1)(x − 2) = x( − 1)x2
f (x) = x( − 1)x2
f
Exercice 10 (partiel 2003)
1) Rappelez l’expression de la base de Newton de associée aux noeuds 1, 2, 3, 4, 5, 6.
Correction : La base de Newton de associée aux noeuds 1, 2, 3, 4, 5, 6 est :
2) Montrez qu’il s’agit bien d’une base.
Correction : Puisque est de dimension 6 (Pour rappel, sa base canonique est ), il
suffit de montrer que c'est une famille libre :
Soient tels que
[x]ℝ5
[x]ℝ5
{1, (x − 1), (x − 1)(x − 2), (x − 1)(x − 2)(x − 3),
(x − 1)(x − 2)(x − 3)(x − 4), (x − 1)(x − 2)(x − 3)(x − 4)(x − 5)}
[x]ℝ5 {1, x, , , , }x2 x3 x4 x5
, , , , , ∈ ℝλ0 λ1 λ2 λ3 λ4 λ5
+ (x − 1) … (x − i) = 0λ0 ∑i=1
5
λi
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 11/28
On rappelle que cette égalité a lieu dans , elle est donc vraie pour tout . En particulier, pour , on obtient . Ensuite, pour , on a et ainsi de suite... On montre ainsi .
Donc c'est bien une base.
3) Donnez, dans cette base, l’expression du polynôme tel que et .
Pour calculer , il nous faut calculer les différences divisées. Pour ce faire, on peut faire un tableau (Voir cours(https://perso.math.univ-toulouse.fr/fdelebec/files/2018/03/chap01-L2.pdf) ) et de la relation de récurrence quiles relie:
On calcule la première colonne immédiatement :
Pour calculer la deuxième colonne, on se sert de la première colonne et de la relation de récurrence qui lie lesdifférences divisées.
Exemple : Pour 1 et 2, ça donne
[x]ℝ5 x ∈ ℝ
x = 1 = 0λ0 x = 2 = 0λ1 = 0, ∀iλi
P ∈ [X]ℝ5 P(1) = P(6) = 1
P(2) = P(3) = P(4) = P(5) = 0
P
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , … , ]xk xk+3 f [ , … , ]xk xk+4 f [ , , , , , ]x0 x1 x2 x3 x4 x5
= 1x0 f [1]
f [1, 2]
= 2x1 f [2] f [1, 2, 3]
f [2, 3] f [1, 2, 3, 4]
= 3x2 f [3] f [2, 3, 4] f [1, 2, 3, 4, 5]
f [3, 4] f [2, 3, 4, 5] f [1, 2, 3, 4, 5, 6]
= 4x3 f [4] f [3, 4, 5] f [2, 3, 4, 5, 6]
f [4, 5] f [3, 4, 5, 6]
= 5x4 f [5] f [4, 5, 6]
f [5, 6]
= 6x5 f [6]
f [ ] = f ( )ai ai
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , … , ]xk xk+3 f [ , … , ]xk xk+4 f [ , , , , , ]x0 x1 x2 x3 x4 x5
= 1x0 1
f [1, 2]
= 2x1 0 f [1, 2, 3]
f [2, 3] f [1, 2, 3, 4]
= 3x2 0 f [2, 3, 4] f [1, 2, 3, 4, 5]
f [3, 4] f [2, 3, 4, 5] f [1, 2, 3, 4, 5, 6]
= 4x3 0 f [3, 4, 5] f [2, 3, 4, 5, 6]
f [4, 5] f [3, 4, 5, 6]
= 5x4 0 f [4, 5, 6]
f [5, 6]
= 6x5 1
f [ , ] =a0 a1
f [ ] − f [ ]a1 a0
−a1 a0
f [1, 2] = = −1f [2] − f [1]
2 − 1
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , … , ]xk xk+3 f [ , … , ]xk xk+4 f [ , , , , , ]x0 x1 x2 x3 x4 x5
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 12/28
On précède ainsi de suite jusqu'à compléter le tableau :
Les coordonnées de dans la base de Newton se lisent alors sur la "diagonale" :
4) Calculez .
Correction :
5) Représentez graphiquement ce polynôme sur le segment , ainsi que les points d'interpolation.
= 1x0 1
−1
= 2x1 0 f [1, 2, 3]
0 f [1, 2, 3, 4]
= 3x2 0 f [2, 3, 4] f [1, 2, 3, 4, 5]
0 f [2, 3, 4, 5] f [1, 2, 3, 4, 5, 6]
= 4x3 0 f [3, 4, 5] f [2, 3, 4, 5, 6]
0 f [3, 4, 5, 6]
= 5x4 0 f [4, 5, 6]
1
= 6x5 1
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , … , ]xk xk+3 f [ , … , ]xk xk+4 f [ , … , ]x0 x5
= 1x0 1
−1
= 2x1 01
2
0 −1
6
= 3x2 0 01
24
0 0 0
= 4x3 0 01
24
01
6
= 5x4 01
2
1
= 6x5 1
P
P(x) = 1 − (x − 1) + (x − 1)(x − 2) − (x − 1)(x − 2)(x − 3) + (x − 1)(x − 2)(x − 3)(x − 4)1
2
1
6
1
24
P(0)
P(0) = 5
[0, 7]
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 13/28
In [9]:
Exercice 11 (Base de Newton)
1) Ecrire une fonction evalpolyNew(X,DD,x) qui évalue en x un polynôme écrit dans la base de Newton. Xest la liste des abcisses et DD la liste des différences divisées correspondantes.
Out[9]:
[<matplotlib.lines.Line2D at 0x7f983e941a90>]
#On définit p
p = lambda x:1-(x-1)+(x-1)*(x-2)/2-(x-1)*(x-2)*(x-3)/6+(x-1)*(x-2)*(x-3)*(x-4)/24
#On n'a plus qu'à discrétiser [0,7]
#et à représenter p ainsi que les points d'interpolations
x = [1,2,3,4,5,6]
y = [1,0,0,0,0,1]
t = linspace(0,7)
plot(x,y,'bo')
plot(t,p(t),'b')
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 14/28
In [10]:
2) Ecrire une fonction diffdiv(X,DD,nx,nv) de mise à jour des différences divisées (DD) par ajout d'unenouvelle abscisse nx et d'une nouvelle valeur d'interpolation nv. La fonction donnera la nouvelle liste desabscisses nX avec la liste X en première position, suivi de nx (utiliser pour cela la commande somme de listes)et la nouvelle liste des différences divisées nDD relatives à nX.
[5. 1. 0. 0. 0. 0. 1.]
def evalpolyNew(X,DD,x) :
#X contient (a_0,...,a_n) les noeuds
#DD contient (f[a_0],f[a_1],...,f[a_0,a_1],...,f[a_0,...,a_n])
n = size(X)
#On va stocker dans p le polynôme évalué en x
p = ones(size(x))*DD[0,0]
#On va stocker successivement dans prod
#les polynômes de la base de Newton évalués en x
prod = ones(size(x))
#On va calculer p et prod "petit à petit"
for j in range(1,n):
prod = prod*(x-X[j-1])
p = p + DD[j,j]*prod
return p
#Pour tester la fonction, on peut le faire avec l'exercice 10 :
X = array([1,2,3,4,5,6])
dd1 = [1,0,0,0,0,0]
dd2 = [0,-1,0,0,0,0]
dd3 = [0,0,1/2,0,0,0]
dd4 = [0,0,0,-1/6,0,0]
dd5 = [0,0,0,0,1/24,0]
dd6 = [1,1,1/2,1/6,1/24,0]
DD = array([dd1,dd2,dd3,dd4,dd5,dd6])
x = array([0,1,2,3,4,5,6])
print(evalpolyNew(X,DD,x))
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 15/28
In [11]:
3) Ecrire une fonction vtodiffdiv(X,Y) qui calcule les différences divisées DD relatives aux abscisses Xet aux valeurs Y associées. On utilisera pour ça la fonction précédente diffdiv.
[1. 0. 0. 0. 0. 1. 5.]
def diffdiv(X,DD,nx,nv):
#On veut ajouter nx à la fin X mais X est un array
#et la commande append ne fonctionne que pour les listes
#On va donc faire un changement de type temporaire
nX = list(X)
nX.append(nx)
nX = array(nX)
#On va s'occuper des différences divisées maintenant en rajoutant nx et nv,
#il suffit de rajouter une ligne
n = int(size(X))
nDD = zeros((n+1,n+1))
#On récupère d'abord DD
for i in range(n):
for j in range(n):
nDD[i,j] = DD[i,j]
#On calcule ensuite la dernière ligne
nDD[n,0] = nv
for j in range(1,n+1):
nDD[n,j] = (nDD[n,j-1]-nDD[n-1,j-1])/(nX[n]-nX[n-j])
return(nX,nDD)
#Testons la fonction sur la question précédante en rajoutant le noeud (0,5)
X = array([1,2,3,4,5,6])
dd1 = [1,0,0,0,0,0]
dd2 = [0,-1,0,0,0,0]
dd3 = [0,0,1/2,0,0,0]
dd4 = [0,0,0,-1/6,0,0]
dd5 = [0,0,0,0,1/24,0]
dd6 = [1,1,1/2,1/6,1/24,0]
DD = array([dd1,dd2,dd3,dd4,dd5,dd6])
(nX,nDD) = diffdiv(X,DD,0,5)
print(evalpolyNew(nX,nDD,nX))
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 16/28
In [12]:
4) Ecrire une fonction diffdivg(X,DD,nx,nv) qui réalise la mise à jour d'un polynôme d'interpolation écritdans la base de Newton lorsqu'un nouveau point d'interpolation (nx, nv) est ajouté et un ancien pointd'interpolation est supprimé (interpolation glissante). Le polynôme est donné par la liste X des abscisses et laliste DD des différences divisées correspondantes. On supprime les derniers éléments des listes X et DD. Lafonction diffdivg(X,DD,nx,nv) donne la nouvelle liste nX des abscisses constituée de la liste X privée desa dernière valeur complété par nX ainsi que la nouvelle liste nDD des différences divisées relatives à nX. Lafonction diffdivg s'obtient facilement à partir de la fonction diffdiv en modifiant quelques instructions.
[[ True True True True True True]
[ True True True True True True]
[ True True True True True True]
[ True True True True True True]
[ True True True True True True]
[ True True True True True True]]
def vtodiffdiv(X,Y):
#On commence par initialiser au cas où on a 1 abscisse et 1 valeur
DD = zeros((1,1))
DD[0,0] = array([Y[0]])
x = array([X[0]])
n = size(X)
#On calcule DD itérativement
for i in range(1,n):
(x,DD) = diffdiv(x,DD,X[i],Y[i])
return DD
#Testons sur le même exemple encore
X = array([1,2,3,4,5,6])
Y = array([1,0,0,0,0,1])
dd1 = [1,0,0,0,0,0]
dd2 = [0,-1,0,0,0,0]
dd3 = [0,0,1/2,0,0,0]
dd4 = [0,0,0,-1/6,0,0]
dd5 = [0,0,0,0,1/24,0]
dd6 = [1,1,1/2,1/6,1/24,0]
DD = array([dd1,dd2,dd3,dd4,dd5,dd6])
nDD = vtodiffdiv(X,Y)
print(DD==nDD)
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 17/28
In [13]:
Exercice 12 (partiel 2014)
Étant donnés six réels , , , , et , on considère le tableau de différences divisées suivant :
1) Calculez , , , , et .
Correction :
: On sait que . D'après l'énoncé, on sait que (car et les
différences divisées ne sont définies que pour des points distincts). On a donc :
x1 a b c d e
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3
= 0x0
x1
= −1x2
= 2x3
1
−1
0
a
1
b
c
d
e
2
3
x1 a b c d e
x1 f [ , ] =x0 x1
f [ ] − f [ ]x1 x0
−x1 x0
≠ 0x1 = 0x0
[1. 0. 0. 0. 0. 5.]
def diffdivg(X,DD,nx,nv):
#On veut ajouter nx à la fin X mais X est un array
#et la commande append ne fonctionne que pour les listes
#On va donc faire un changement de type temporaire
n = int(size(X))
nX = zeros(n)
nDD = zeros([n,n])
#On récupère nX
for i in range(n-1):
nX[i] = X[i]
nX[n-1] = nx
#On récupère d'abord DD privé de sa dernière ligne et de sa dernière colonne
for i in range(n-1):
for j in range(n-1):
nDD[i,j] = DD[i,j]
#On calcule ensuite la dernière ligne
nDD[n-1,0] = nv
for j in range(1,n):
nDD[n-1,j] = (nDD[n-1,j-1]-nDD[n-2,j-1])/(nX[n-1]-nX[n-1-j])
return(nX,nDD)
#Testons la fonction sur la question précédante
#en rajoutant le noeud (0,5) à la place de (6,1)
X = array([1,2,3,4,5,6])
dd1 = [1,0,0,0,0,0]
dd2 = [0,-1,0,0,0,0]
dd3 = [0,0,1/2,0,0,0]
dd4 = [0,0,0,-1/6,0,0]
dd5 = [0,0,0,0,1/24,0]
dd6 = [1,1,1/2,1/6,1/24,0]
DD = array([dd1,dd2,dd3,dd4,dd5,dd6])
(nX,nDD) = diffdivg(X,DD,0,5)
print(evalpolyNew(nX,nDD,nX))
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 18/28
d'où on peut donc compléter le tableau :
En se servant de la formule de récurrence
On obtient c'est-à-dire et on peut compléter encore le tableau :
Ainsi, on peut calculer et on continue à compléter :
On a alors d'où
1 =−1 − 1
− 0x1
= −2x1
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3
= 0x0
= −2x1
= −1x2
= 2x3
1
−1
0
a
1
b
c
d
e
2
3
f [ , , . . . , ] =a0 a1 alf [ , . . . , ] − f [ , . . . ]a1 al a0 al−1
−al a0
= b0 + 1
−1 + 2b = 1
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3
= 0x0
= −2x1
= −1x2
= 2x3
1
−1
0
a
1
1
c
d
e
2
3
d = = 01 − 1
−1 − 0
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3
= 0x0
= −2x1
= −1x2
= 2x3
1
−1
0
a
1
1
c
0
e
2
3
=e − 0
2 − 0
2
3e =
4
3
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3
= 0x0
= −2x1
= −1x2
= 2x3
1
−1
0
a
1
1
c
0
4
3
2
3
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 19/28
d'où
Et enfin, ,
2) Donnez, dans la base de Newton, le polynôme qui interpole , , et .
Correction :
On sait que
Donc, ici, on a, pour
Ainsi, sans faire de calculs, on a directement :
d'où :
3) On considère les fonctions suivantes définies sur :
Pour et deux réels, on définit la fonction . Montrez que est le polynômed'interpolation de en , , et si et seulement si et .
=c − 1
2 + 2
4
3c =
19
3
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3
= 0x0
= −2x1
= −1x2
= 2x3
1
−1
0
a
1
1
19
3
0
4
3
2
3
=a − 0
2 + 1
19
3a = 19
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3
= 0x0
= −2x1
= −1x2
= 2x3
1
−1
0
19
1
1
19
3
0
4
3
2
3
P3 (0, 1) ( ,−1)x1 (−1, 0) (2, a)
L[A; f ](x) = f [ , . . . , ](x − ). . . (x − aj − 1)∑j=0
d
a0 aj a0
= 0, = , = −1, = 2a0 a1 x1 a2 a3
(x) = f [ ] + f [ , ](x − )P3 a0 a0 a1 a0
+f [ , , ](x − )(x − ) + f [ , , , ](x − )(x − )(x − )a0 a1 a2 a0 a1 a0 a1 a2 a3 a0 a1 a2
(x) = 1 + 1(x − 0) + d(x − 0)(x − ) + (x − 0)(x − )(x + 1)P3 x1
2
3x1
(x) = 1 + x + x(x + 2)(x + 1)P3
2
3
ℝ
: x ↦ { , : x ↦ { .f12 + 9 x2
0
si x ≥ 0
sinonf2
0
−3 −x2 x3
si x ≥ −1
sinonα β f : x ∈ ℝ ↦ α (x) + β (x)f1 f2 P3
f x0 x1 x2 x3 α = 1
2β = 1
4
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 20/28
Correction:
est le polynôme d'interpolation de en , , et si et seulement si :
c'est-à-dire
c'est-à-dire
c'est-à-dire
d'où et .
À partir de maintenant, on pose et .
4) Calculez dans la base de Newton le polynôme qui interpole les points , , , et . est-il le polynôme d'interpolation à en , , , et ?
Correction :
Puisque , on a
avec et
Pour calculer , on a juste à reprendre le tableau précédant en rajoutant une ligne et enutilisant la relation de récurrence pour calculer tous les termes manquants
P3 f x0 x1 x2 x3
f ( )x0
f ( )x1
f ( )x2
f ( )x3
=
=
=
=
1
−1
0
19
f (0)
f (−2)
f (−1)
f (2)
=
=
=
=
1
−1
0
19
α (0) + β (0)f1 f2
α (−2) + β (−2)f1 f2
α (−1) + β (−1)f1 f2
α (2) + β (2)f1 f2
=
=
=
=
1
−1
0
19
2 α + 0 β
0 α − 4 β
0 α + 0 β
38 α + 0 β
=
=
=
=
1
−1
0
19
α = 12
β = 14
α = 1
2β = 1
4
P4 (0, 1) ( ,−1)x1 (−1, 0) (2, a)
(1, 6) P4 f 0 x1 −1 2 1
L[A; f ](x) = f [ , . . . , ](x − ). . . (x − xj − 1)∑dj=0 x0 xj x0
(x) = (x) + f [ , , , , ](x − )(x − )(x − )(x − )P4 P3 x0 x1 x2 x3 x4 x0 x1 x2 x3
= 1x3 f [ ] = 6x3
f [ , , , , ]x0 x1 x2 x3 x4
xk f [ ]xk f [ , ]xk xk+1 f [ , … , ]xk xk+2 f [ , , , ]x0 x1 x2 x3 f [ , , , , ]x0 x1 x2 x3 x4
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 21/28
Finalement, on remarque :
Mais on aurait pu l'anticiper puisque .
Maintenant, est le polynôme d'interpolation à en , , , et si et seulement si .
Or, . Donc n'est pas le polynôme d'interpolation à en ,
, , et
= 0x0
= −2x1
= −1x2
= 2x3
= 1x4
1
−1
0
19
6
1
1
19
3
13
0
4
3
10
3
2
3
2
3
0
(x) = (x) = 1 + x + x(x + 2)(x + 1)P4 P3
2
3(1) = 6P3
P4 f 0 x1 −1 2 1 f (1) = 6
f (1) = α (1) + β (1) = 11 α + 0 β = ≠ 6f1 f211
2P4 f 0
x1 −1 2 1
Exercice 13
Soit le polynôme d’interpolation de la fonction relativement aux noeuds pris deux àdeux distincts dans un intervalle fermé borné , .
1. Montrez que pour tout ,
Correction :
On note
D'après un corollaire du cours, on a :
où , et
Dans notre cas, et est soit un cosinus, soit un sinus. Donc
De plus, . Or, , . Donc
Finalement, on a :
2. En déduire que la suite converge vers la fonction uniformément sur .
Correction :
En utilisant ce qui précède, on peut déduire :
pn x ↦ sin(x) , … ,x1 xn[a, b] a < b
x ∈ [a, b]
(x) − sin(x) ≤ .||pn ||(b − a)n
n!
E(x) = (x) − sin(x)||pn ||
E(x) ≤ (x)∥∥f
(d+1)∥∥∞,[a,b]
(d + 1)!||πA ||
A = { , . . . , }a0 ad (x) = (x − )πA ∏dk=0 ak = (x)∥∥f
(d+1)∥∥∞,[a,b]maxx∈[a,b] |
|f(d+1) |
|
A = { , … , }x1 xn (x)f (n) ≤ 1∥∥f(n)∥∥∞,[a,b]
(x) = (x − ) … (x − )||πA || || x1 xn || ∀x ∈ [a, b] x − ≤ (b − a)|| xk|| (x) ≤ (b − a||πA || )n
(x) − sin(x) ≤ .||pn ||(b − a)n
n!
( )pn sin(x) [a, b]
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 22/28
On peut donc conclure que la suite converge vers la fonction uniformément sur .
Note : Pour la convergence de vers 0, appliquer la règle de d'Alembert.
3. Application numérique : on prend et . Représentez sur un même graphique la fonction et le polynôme d'interpolation à cette fonction en points choisis aléatoirement entre et , pour , , et .
≤ 0∥ − sin∥pn ∞,[a,b]
(b − a)n
n!⟶n→+∞
( )pn sin(x) [a, b]
( )(b − a)n
n!
a = 0 b = 2 π
sin(x) n 0 2 π
n = 3 6 9 12
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 23/28
In [14]:
Exercice 14
Out[14]:
[<matplotlib.lines.Line2D at 0x7f983e7e41d0>]
#Pour générer des points aléatoirement, on aura besoin de la fonction uniform du mo
from numpy.random import uniform
#On va se servir de la fonction PolIntLag2 définie dans l'exercice 7
#On commence par générer un vecteur de n points choisis aléatoirement
X3 = uniform(0,2*pi,3)
X6 = uniform(0,2*pi,6)
X9 = uniform(0,2*pi,9)
X12 = uniform(0,2*pi,12)
#On calcule son image par sin
Y3 = sin(X3)
Y6 = sin(X6)
Y9 = sin(X9)
Y12 = sin(X12)
#On utilise PolIntLag2 pour calculer l'image de t par le polynôme d'interpolation e
sint3 = PolIntLag2(t,X3,Y3)
sint6 = PolIntLag2(t,X6,Y6)
sint9 = PolIntLag2(t,X9,Y9)
sint12 = PolIntLag2(t,X12,Y12)
#On trace les graphes des différents polynômes :
plot(t,sint3,'b')
plot(t,sint6,'b')
plot(t,sint9,'b')
plot(t,sint12,'b')
#On finit par tracer le graphique de la fonction sin(x)
t = linspace(0,2*pi)
sint = sin(t)
plot(t,sint,'r')
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 24/28
On considère et le polynôme d’interpolation tel que , .Montrer que la suite de polynômes d’interpolation converge uniformément vers la fonction exponentiellelorsque tend vers l'infini.
Correction :
On note
Toujours d'après un corollaire du cours, on a :
où , , et .
Ainsi, comme , et .
De plus, comme , , , on a :
D'où :
Donc la suite de polynômes d'interpolation converge uniformément vers la fonction exponentielle sur lorsque tend vers l'infini.
a = < < … < = bx0 x1 xn ( ) =Pn xi exi 0 ≤ i ≤ n
Pn
n
E(x) = (x) −||Pn ex||
E(x) ≤ (x)∥∥f
(n+1)∥∥∞,[a,b]
(n + 1)!||πA ||
A = { , . . . , }x0 xn (x) = (x − )πA ∏nk=0 xk = (x)∥∥f
(n+1)∥∥∞,[a,b]maxx∈[a,b] |
|f(n+1) |
| f (x) = ex
f (x) = ex (x) =f (n+1) ex =∥∥f(n+1)∥∥∞,[a,b]
eb
x − ≤ (b − a)|| xk|| ∀x ∈ [a, b] ∀k ∈ {0, … , n}
E(x) ≤(b − aeb )n+1
(n + 1)!
≤ 0∥ − exp∥Pn ∞,[a,b]
(b − aeb )n+1
(n + 1)!⟶n→+∞
(Pn )n[a, b] n
Exercice 15
On considère la fonction .
1) On choisit, pour interpoler la fonction , abscisses equidistribuées sur . Tracez sur un mêmegraphique, sur , la fonction , les points d'interpolation et le polynôme d'interpolation correspondant,pour , , et . Que remarquez-vous ?
f : x ∈ ℝ ↦1
1 + 25 x2
f n [−1, 1]
[−1, 1] f
n = 5 10 15 20
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 25/28
In [15]:
On remarque que pour des abscisses équidistribuées, même pour , le polynôme d'interpolationn'approche pas bien la fonction : des oscillations apparaissent (phénomène de Runge).
n = 20
f
2) Même question, mais cette fois en choisissant avec , .
Que remarquez-vous ?
= ( , … , )Xint x0 xn = cos(π )xii
ni = 0, … , n
Out[15]:
[<matplotlib.lines.Line2D at 0x7f983e76bc88>]
#On va définir une fonction Exerc_15_1(n,t)
#qui calcule le polynôme d'interpolation pour un n donné en t
def Exerc_15_1(n,t):
#On commence par générer les points équidistribués
Xint = linspace(-1,1,n)
#Puis on calcule leurs images
Yint = 1/(1+25*Xint**2)
#Enfin, on trace le graphe du polynôme d'interpolation
ft = PolIntLag2(t,Xint,Yint)
return ft
t = linspace(-1,1)
plot(t,Exerc_15_1(5,t),'b')
plot(t,Exerc_15_1(10,t),'y')
plot(t,Exerc_15_1(15,t),'g')
plot(t,Exerc_15_1(20,t),'k')
ft = 1/(1+25*t**2)
plot(t,ft,'r')
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 26/28
In [16]:
On remarque qu'avec ces abscisses là, l'interpolation est meilleure.
Exercice 16
On reprend la fonction de l'exercice précédent. On voit que si on ne choisit pas correctement les abscissesd'interpolation sur , des oscillations apparaissent (phénomène de Runge), et le polynôme d'interpolationne converge pas vers la fonction .
Pour contrer cela, on se propose non plus de faire de l'interpolation polynomiale, mais de l'interpolationpolynomiale par morceau, c'est-à-dire :
on découpe l'intervalle en sous-intervalles de même longueursur chaque sous-intervalle, on interpole la fonction en utilisant abscisses équidistribuées
f
[−1, 1]
f
[−1, 1] N
f n
Out[16]:
[<matplotlib.lines.Line2D at 0x7f983e6db710>]
#On va définir une fonction Exerc_15_2(n,t)
#qui calcule le polynôme d'interpolation pour un n donné en t
def Exerc_15_2(n,t):
#On commence par générer les points équidistribués
Xint = zeros(n+1)
for i in range(n+1):
Xint[i] = cos((pi*i)/n)
#Puis on calcule leurs images
Yint = 1/(1+25*Xint**2)
#Enfin, on trace le graphe du polynôme d'interpolation
ft = PolIntLag2(t,Xint,Yint)
return ft
t = linspace(-1,1)
plot(t,Exerc_15_2(5,t),'b')
plot(t,Exerc_15_2(10,t),'y')
plot(t,Exerc_15_2(15,t),'g')
plot(t,Exerc_15_2(20,t),'k')
ft = 1/(1+25*t**2)
plot(t,ft,'r')
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 27/28
Écrire un programme dessinant la fonction et son interpolé par morceaux. Le tester pour différentes valeursde et .
f
N n
In [17]:
Out[17]:
0
#On va définir la fonction PolIntMorc(N,n)
#qui trace le graphique de f et son interpolé par morceaux
def PolIntMorc(N,n):
#On commence par générer les différents sous-intervalles
Xinter = linspace(-1,1,N+1)
#Pour chaque sous intervalle, on trace l'interpolé
for i in range(N):
ti = linspace(Xinter[i],Xinter[i+1])
#On commence par générer les points équidistribués
#sur l'intervalle Xinter[i],Xinter[i+1]
Xint = linspace(Xinter[i],Xinter[i+1],n)
#Puis on calcule leurs images
Yint = 1/(1+25*Xint**2)
#Enfin, on trace le graphe du polynôme d'interpolation
fti = PolIntLag2(ti,Xint,Yint)
plot(ti,fti,'b')
#Finalement, on trace la fonction f
t = linspace(-1,1)
ft = 1/(1+25*t**2)
plot(t,ft,'r')
return 0
#On peut commencer par tester la fonction
#pour N=1 et n=20 pour retrouver l'exercice précédant
PolIntMorc(1,20)
03/10/2018 Correction_TP1
http://localhost:8888/notebooks/Nextcloud/Documents/DCE/L2/Correction_TP1.ipynb 28/28
In [18]:
Out[18]:
0
#Ensuite, on peut le tester pour un grand N et un petit n
PolIntMorc(10,2)