📚 الرئيسية
دخول

مسابقة دكتوراه 2022 — Université Abbès Laghrour de Khenchela — الموضوع 01

مسابقة تخصص · Analyse Numérique & Optimisation · المعامل: 1 · المدة: 1سا 30د

⬇️ تحميل☆ حفظ

Concours d'accès au doctorat 3ème cycle LMD 2021/2022, Faculté des Sciences et de la Technologie, Département de Mathématiques & Informatique, Variante 2, Coefficient 01, Durée 1h30, 26/02/2022

التمرين 1

Exercice 1 — Polynôme d'interpolation et existence d'une racine

#interpolation#polynôme de Lagrange#théorème des valeurs intermédiaires#analyse numérique

Soit les points :

xix_i−1-1001122
yiy_i2211−1-1−2-2

  1. Calculer le polynôme d'interpolation PP vérifiant yi=P(xi)y_i = P(x_i).

  2. Montrer qu'il existe α∈]0,1[\alpha \in ]0,1[ tel que P(α)=0P(\alpha) = 0.

Astuce : pour cette question 2, on ne calcule pas α\alpha ; on invoque simplement TVI après avoir constaté un changement de signe. C'est le fondement théorique de toutes les méthodes de dichotomie.

◀الحل
  1. On peut utiliser les différences divisées de Newton avec les points ordonnés x0=−1,x1=0,x2=1,x3=2x_0=-1,x_1=0,x_2=1,x_3=2 et valeurs y0=2,y1=1,y2=−1,y3=−2y_0=2, y_1=1, y_2=-1, y_3=-2. • Ordre 0 : f[x0]=2,f[x1]=1,f[x2]=−1,f[x3]=−2f[x_0]=2, f[x_1]=1, f[x_2]=-1, f[x_3]=-2. • Ordre 1 : f[x0,x1]=(1−2)/(0−(−1))=−1f[x_0,x_1]=(1-2)/(0-(-1))=-1 ; f[x1,x2]=(−1−1)/(1−0)=−2f[x_1,x_2]=(-1-1)/(1-0)=-2 ; f[x2,x3]=(−2−(−1))/(2−1)=−1f[x_2,x_3]=(-2-(-1))/(2-1)=-1. • Ordre 2 : f[x0,x1,x2]=(−2−(−1))/(1−(−1))=−1/2f[x_0,x_1,x_2]=(-2-(-1))/(1-(-1))=-1/2 ; f[x1,x2,x3]=(−1−(−2))/(2−0)=1/2f[x_1,x_2,x_3]=(-1-(-2))/(2-0)=1/2. • Ordre 3 : f[x0,…,x3]=(1/2−(−1/2))/(2−(−1))=1/3f[x_0,\dots,x_3]=(1/2-(-1/2))/(2-(-1))=1/3.

P(x)=2+(−1)(x+1)+(−1/2)(x+1)x+(1/3)(x+1)x(x−1).P(x) = 2 + (-1)(x+1) + (-1/2)(x+1)x + (1/3)(x+1)x(x-1). En développant : P(x)=13x3−12x2−116x+1P(x) = \dfrac{1}{3}x^3 - \dfrac{1}{2}x^2 - \dfrac{11}{6}x + 1.

Vérification : P(−1)=−1/3−1/2+11/6+1=(−2−3+11+6)/6=12/6=2P(-1)=-1/3-1/2+11/6+1 = (-2-3+11+6)/6 = 12/6=2 ✓ ; P(0)=1P(0)=1 ✓ ; P(1)=1/3−1/2−11/6+1=(2−3−11+6)/6=−6/6=−1P(1) = 1/3-1/2-11/6+1 = (2-3-11+6)/6 = -6/6=-1 ✓ ; P(2)=8/3−2−11/3+1=(8−6−11+3)/3=−6/3=−2P(2)= 8/3-2-11/3+1 = (8-6-11+3)/3 = -6/3=-2 ✓.

  1. P(0)=1>0P(0)=1>0 et P(1)=−1<0P(1)=-1<0. PP est un polynôme, donc continu sur [0,1][0,1]. Par le théorème des valeurs intermédiaires, il existe α∈]0,1[\alpha\in]0,1[ tel que P(α)=0P(\alpha)=0.

التمرين 2

Exercice 2 — Résolution de $e^x(1-x)-x=0$ par dichotomie ou point fixe

#équations non linéaires#dichotomie#point fixe#convergence#analyse numérique

Soit l'équation algébrique suivante : ex(1−x)−x=0,x∈[0,1].e^x(1-x) - x = 0,\qquad x\in[0,1].

  1. Montrer que cette équation admet une unique solution zˉ∈[0,1]\bar z\in[0,1].

  2. Justifier parmi ces deux méthodes numériques suivantes : Dichotomie et Point Fixe, celle qui semble meilleure.

  3. Montrer que la méthode choisie est convergente.

  4. Calculer la troisième itération à ε\varepsilon près par la méthode choisie, et évaluer son erreur.

Test contractance : vérifier ∣g′∣<1|g'|<1 sur l'intervalle d'étude avant de choisir un point fixe. Ici g(x)=ex(1−x)g(x)=e^x(1-x) a ∣g′∣|g'| qui dépasse 1 près de x=1x=1, donc la méthode ne convergerait pas globalement. La dichotomie est robuste mais lente (convergence linéaire de raison 1/21/2).

◀الحل

Notons F(x)=ex(1−x)−xF(x)=e^x(1-x)-x.

  1. F(0)=1>0F(0)=1>0 et F(1)=0−1=−1<0F(1)=0-1=-1<0. F′(x)=ex(1−x)+ex(−1)−1=−xex−1<0F'(x)=e^x(1-x)+e^x(-1)-1 = -xe^x - 1 < 0 sur [0,1][0,1] (x≥0x\ge 0 et ex>0e^x>0). Donc FF est strictement décroissante continue sur [0,1][0,1], avec un changement de signe : unique racine zˉ∈]0,1[\bar z\in]0,1[.

  2. Réécrivons l'équation en x=g(x)x = g(x) avec g(x)=ex(1−x)g(x) = e^x(1-x) (isoler le second xx). Alors g′(x)=−xexg'(x) = -xe^x, avec ∣g′(x)∣=xex|g'(x)| = xe^x sur [0,1][0,1], ∣g′(1)∣=e≈2.71>1|g'(1)| = e\approx 2.71 > 1. Le point fixe standard sur [0,1][0,1] n'est pas contractant. Une reformulation x=h(x)=x⋅e−x/(1−e−x⋅0)x = h(x)=x\cdot e^{-x}/(1-e^{-x}\cdot 0)... n'est pas plus favorable. La dichotomie, elle, converge sur tout intervalle où FF change de signe et est continue, sans hypothèse de contractance. → La méthode de dichotomie semble meilleure.

  3. Convergence de la dichotomie : FF continue et F(0)F(1)<0F(0)F(1)<0 ⇒ la suite (an,bn)(a_n,b_n) des extrémités des intervalles emboités vérifie bn−an=(b0−a0)/2n=1/2nb_n-a_n = (b_0-a_0)/2^n = 1/2^n. Le milieu xn=(an+bn)/2x_n = (a_n+b_n)/2 converge vers zˉ\bar z avec ∣xn−zˉ∣≤1/2n+1|x_n-\bar z|\le 1/2^{n+1}.

  4. Itérations : • n=0n=0 : a0=0,b0=1a_0=0, b_0=1, x0=0.5x_0=0.5, F(0.5)=e0.5(0.5)−0.5≈1.6487⋅0.5−0.5≈0.324>0F(0.5)=e^{0.5}(0.5)-0.5\approx 1.6487\cdot 0.5-0.5\approx 0.324>0. Donc a1=0.5,b1=1a_1=0.5, b_1=1. • n=1n=1 : x1=0.75x_1=0.75, F(0.75)=e0.75(0.25)−0.75≈2.117⋅0.25−0.75≈0.529−0.75=−0.221<0F(0.75)=e^{0.75}(0.25)-0.75\approx 2.117\cdot 0.25 - 0.75\approx 0.529-0.75=-0.221<0. Donc a2=0.5,b2=0.75a_2=0.5, b_2=0.75. • n=2n=2 : x2=0.625x_2=0.625, F(0.625)≈e0.625(0.375)−0.625≈1.8682⋅0.375−0.625≈0.7006−0.625=0.076>0F(0.625)\approx e^{0.625}(0.375)-0.625\approx 1.8682\cdot 0.375-0.625\approx 0.7006-0.625=0.076>0. Donc a3=0.625,b3=0.75a_3=0.625, b_3=0.75. • n=3n=3 : x3=0.6875x_3=0.6875 (troisième itération proprement dite, si on numérote à partir de x1x_1).

Erreur : ∣x3−zˉ∣≤(b0−a0)/24=1/16≈0.0625|x_3-\bar z|\le (b_0-a_0)/2^4 = 1/16 \approx 0.0625. (En réalité zˉ≈0.6591\bar z \approx 0.6591.)

التمرين 3

Exercice 3 — Résolution d'un système linéaire par la méthode de Crout (LU)

#systèmes linéaires#décomposition LU#Crout#déterminant#analyse numérique

Soit le système matriciel suivant : (101110201)(xyz)=(−121).(S)\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} -1 \\ 2 \\ 1 \end{pmatrix}. \quad (S)

  1. Montrer que (S)(S) possède une solution unique.

  2. Résoudre (S)(S) par la méthode directe de Crout (LULU).

  3. Déduire le déterminant de (S)(S).

Crout : la diagonale unité est placée sur UU (contrairement à Doolittle où elle est sur LL). Le calcul du déterminant devient trivial une fois LULU obtenue : det⁡A=∏ℓii\det A = \prod \ell_{ii}. Pratique en analyse numérique pour éviter les déterminants par cofacteurs, coûteux.

◀الحل

Notons AA la matrice du système.

  1. On calcule det⁡A\det A (par la règle de Sarrus ou développement) : det⁡A=1⋅(1⋅1−0⋅0)−0+1⋅(1⋅0−1⋅2)=1−2=−1≠0\det A = 1\cdot(1\cdot1-0\cdot0) - 0 + 1\cdot(1\cdot0-1\cdot2) = 1 - 2 = -1 \ne 0. Donc (S)(S) a une solution unique.

  2. Décomposition Crout A=LUA = LU avec LL triangulaire inférieure (ℓii\ell_{ii} quelconques) et UU triangulaire supérieure à diagonale unité. En posant : L=(ℓ1100ℓ21ℓ220ℓ31ℓ32ℓ33),U=(1u12u1301u23001).L=\begin{pmatrix}\ell_{11} & 0 & 0\\ \ell_{21} & \ell_{22} & 0\\ \ell_{31} & \ell_{32} & \ell_{33}\end{pmatrix},\quad U=\begin{pmatrix}1 & u_{12} & u_{13}\\ 0 & 1 & u_{23}\\ 0 & 0 & 1\end{pmatrix}. Identification A=LUA=LU : • Colonne 1 : ℓ11=1,ℓ21=1,ℓ31=2\ell_{11}=1, \ell_{21}=1, \ell_{31}=2. • Ligne 1 : ℓ11u12=0⇒u12=0\ell_{11}u_{12}=0\Rightarrow u_{12}=0 ; ℓ11u13=1⇒u13=1\ell_{11}u_{13}=1\Rightarrow u_{13}=1. • Colonne 2 : ℓ21u12+ℓ22=1⇒ℓ22=1\ell_{21}u_{12}+\ell_{22}=1\Rightarrow \ell_{22}=1 ; ℓ31u12+ℓ32=0⇒ℓ32=0\ell_{31}u_{12}+\ell_{32}=0\Rightarrow \ell_{32}=0. • Ligne 2 : ℓ21u13+ℓ22u23=0⇒1+u23=0⇒u23=−1\ell_{21}u_{13}+\ell_{22}u_{23}=0\Rightarrow 1+u_{23}=0\Rightarrow u_{23}=-1. • Colonne 3 : ℓ31u13+ℓ32u23+ℓ33=1⇒2+0+ℓ33=1⇒ℓ33=−1\ell_{31}u_{13}+\ell_{32}u_{23}+\ell_{33}=1\Rightarrow 2+0+\ell_{33}=1\Rightarrow \ell_{33}=-1.

Donc L=(10011020−1), U=(10101−1001)L=\begin{pmatrix}1&0&0\\1&1&0\\2&0&-1\end{pmatrix},\ U=\begin{pmatrix}1&0&1\\0&1&-1\\0&0&1\end{pmatrix}.

Résolution LY=b=(−1,2,1)TLY = b = (-1,2,1)^T : y1=−1y_1=-1 ; y1+y2=2⇒y2=3y_1+y_2=2\Rightarrow y_2=3 ; 2y1−y3=1⇒y3=2y1−1=−32y_1-y_3=1\Rightarrow y_3 = 2y_1 - 1 = -3. Puis UX=YUX = Y : z=−3z = -3 ; y−z=3⇒y=0y - z = 3\Rightarrow y = 0 ; x+z=−1⇒x=2x + z = -1\Rightarrow x = 2.

x=2, y=0, z=−3.\boxed{x=2,\ y=0,\ z=-3.}

  1. det⁡A=det⁡L⋅det⁡U=(1⋅1⋅(−1))⋅(1⋅1⋅1)=−1\det A = \det L \cdot \det U = (1\cdot 1\cdot(-1))\cdot(1\cdot 1\cdot 1) = -1.