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

التمرين 1

Exercice 1 (Khenchela 2022) — Interpolation de Lagrange sur 4 points

#interpolation#Lagrange#différences divisées#Newton

Soit la fonction $f(x)=\cos(\pi x)$ connue par les valeurs suivantes :

$x_0=0$ , $x_1=1/3$ , $x_2=1/2$ , $x_3=1$ avec $f(x_0)=1$ , $f(x_1)=1/2$ , $f(x_2)=0$ , $f(x_3)=-1$ .

Écrire le polynôme d'interpolation de Lagrange $P_3(x)$ de $f$ passant par ces 4 points.
Calculer $P_3(2/3)$ et comparer avec $f(2/3)=-1/2$ . Donner une estimation de l'erreur d'interpolation.
Reprendre en écrivant $P_3$ sous la forme de Newton (différences divisées) et vérifier qu'on retrouve le même polynôme.

L'interpolation de Newton est numériquement plus stable et permet d'ajouter facilement un nouveau point sans recalculer tout. Erreur d'interpolation majorable par $\dfrac{M_{n+1}}{(n+1)!}\prod|x-x_i|$ . Pour minimiser cette borne, choisir les $x_i$ comme nœuds de Chebyshev.

◀الحل

Lagrange : $P_3(x)=\sum_{i=0}^3 f(x_i) L_i(x)$ avec $L_i(x)=\prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j}$ .

$L_0(x) = \dfrac{(x-1/3)(x-1/2)(x-1)}{(0-1/3)(0-1/2)(0-1)} = \dfrac{(x-1/3)(x-1/2)(x-1)}{-1/6} = -6(x-1/3)(x-1/2)(x-1)$ .
$L_1(x) = \dfrac{x(x-1/2)(x-1)}{(1/3)(-1/6)(-2/3)} = \dfrac{x(x-1/2)(x-1)}{1/27} = 27\,x(x-1/2)(x-1)$ .
$L_2(x) = \dfrac{x(x-1/3)(x-1)}{(1/2)(1/6)(-1/2)} = \dfrac{x(x-1/3)(x-1)}{-1/24} = -24\,x(x-1/3)(x-1)$ .
$L_3(x) = \dfrac{x(x-1/3)(x-1/2)}{(1)(2/3)(1/2)} = \dfrac{x(x-1/3)(x-1/2)}{1/3} = 3\,x(x-1/3)(x-1/2)$ .

$P_3(x) = 1\cdot L_0(x) + \dfrac{1}{2}L_1(x) + 0\cdot L_2(x) + (-1)\cdot L_3(x)$ .

Valeur en $2/3$ : calcul numérique de $P_3(2/3)$ . Comparaison avec $f(2/3)=\cos(2\pi/3)=-1/2$ . Erreur : $|P_3(2/3)-(-1/2)|$ .

Estimation théorique : $|f(x)-P_3(x)|\le \dfrac{M_4}{4!}|(x-x_0)(x-x_1)(x-x_2)(x-x_3)|$ avec $M_4=\max|f^{(4)}|=\pi^4$ (car $f^{(4)}(x)=\pi^4\cos(\pi x)$ ). En $x=2/3$ : $|(2/3)(1/3)(1/6)(-1/3)|=2/162=1/81$ , donc erreur $\le \pi^4/(24\cdot 81)\approx 0{,}051$ .

Newton : construire le tableau des différences divisées. $f[x_0]=1$ , $f[x_1]=1/2$ , $f[x_2]=0$ , $f[x_3]=-1$ . Différences divisées d'ordre 1 : $f[x_0,x_1]=(1/2-1)/(1/3)=-3/2$ , $f[x_1,x_2]=(0-1/2)/(1/6)=-3$ , $f[x_2,x_3]=(-1-0)/(1/2)=-2$ . Ordre 2 : $f[x_0,x_1,x_2]=(-3-(-3/2))/(1/2)=-3$ , $f[x_1,x_2,x_3]=(-2-(-3))/(2/3)=3/2$ . Ordre 3 : $f[x_0,x_1,x_2,x_3]=(3/2-(-3))/1=9/2$ .

Donc $P_3(x)=1-\dfrac{3}{2}x-3x(x-1/3)+\dfrac{9}{2}x(x-1/3)(x-1/2)$ . On vérifie qu'après développement on retrouve la même fonction polynômiale que par Lagrange.

التمرين 2

Exercice 2 (Khenchela 2022) — Méthode du point fixe et de dichotomie sur $e^x(1-x)=x$

#méthodes itératives#point fixe#dichotomie#convergence

On considère l'équation $e^x(1-x)-x=0$ sur $[0,1]$ .

Montrer que cette équation admet une unique solution $\alpha$ dans $[0,1]$ .
Utiliser la méthode de dichotomie pour donner une valeur approchée de $\alpha$ à $10^{-2}$ près. Combien d'itérations sont-elles nécessaires ?
On propose la méthode du point fixe $x_{n+1}=g(x_n)$ avec $g(x)=e^x(1-x)$ . Est-elle convergente au voisinage de $\alpha$ ? Proposer une reformulation qui garantit la convergence.

Règle d'or : point fixe converge localement ssi $|g'(\alpha)|<1$ . Toujours vérifier cette condition. Si divergence : essayer Newton (quadratique), sécante ou reformulation avec relaxation. Dichotomie : lente mais sûre, erreur en $2^{-n}$ .

◀الحل

Existence-unicité : Posons $F(x)=e^x(1-x)-x$ . $F(0)=1>0$ , $F(1)=-1<0$ . $F$ continue, donc au moins une racine dans $]0,1[$ . Unicité : $F'(x) = e^x(1-x)-e^x-1 = -e^x x - 1 < 0$ sur $[0,1]$ (strict), donc $F$ strictement décroissante : unique racine $\alpha$ .
Dichotomie : $[a_0,b_0]=[0,1]$ . Nombre d'itérations : erreur après $n$ itérations $\le (b_0-a_0)/2^{n+1}=1/2^{n+1}$ . Pour avoir $\le 10^{-2}$ : $2^{n+1}\ge 100$ , $n+1\ge 7$ , donc $n=6$ itérations suffisent. Itérations : calculer $F(1/2)\approx e^{0{,}5}\cdot 0{,}5-0{,}5\approx 0{,}324>0$ , garder $[1/2,1]$ . $F(3/4)\approx e^{0{,}75}\cdot 0{,}25-0{,}75\approx -0{,}221<0$ , garder $[1/2,3/4]$ . On continue et on trouve $\alpha\approx 0{,}66$ après 6 dichotomies (valeur exacte : $\alpha\approx 0{,}6590$ ).
Point fixe avec $g(x)=e^x(1-x)$ . Convergence locale : $|g'(\alpha)|<1$ requis. $g'(x)=e^x(1-x)-e^x=-e^x x$ . $g'(\alpha)=-e^\alpha\alpha\approx -e^{0{,}66}\cdot 0{,}66\approx -1{,}28$ . $|g'(\alpha)|>1$ : divergence !

Reformulation : appliquer Newton : $x_{n+1}=x_n - F(x_n)/F'(x_n)$ . Ou réécrire $x = h(x)$ avec $h(x)=g(x)/(1+|g'|)$ (relaxation), par exemple $x_{n+1} = x_n - \omega F(x_n)$ avec $\omega$ bien choisi (méthode de Richardson). Choix classique : Newton $x_{n+1}=x_n+\dfrac{e^{x_n}(1-x_n)-x_n}{e^{x_n}x_n+1}$ , convergence quadratique.

التمرين 3

Exercice 3 (Khenchela 2022) — Factorisation de Crout $LU$ et système linéaire

#factorisation LU#Crout#système linéaire#descente-remontée

On considère le système linéaire $A\mathbf{x}=\mathbf{b}$ où $A = \begin{pmatrix} 2 & 1 & 0\\ 1 & 3 & 1\\ 0 & 1 & 2\end{pmatrix},\quad \mathbf{b}=\begin{pmatrix}3\\ 5\\ 3\end{pmatrix}.$

Effectuer la factorisation de Crout $A=LU$ avec $L$ triangulaire inférieure et $U$ triangulaire supérieure à diagonale unité.
Résoudre le système $A\mathbf{x}=\mathbf{b}$ par descente-remontée.

Crout : $U$ à diagonale unité ; Doolittle : $L$ à diagonale unité. Complexité $O(n^3/3)$ pour la factorisation, $O(n^2)$ pour chaque descente/remontée : économique quand on résout $A\mathbf{x}=\mathbf{b}$ pour plusieurs seconds membres.

◀الحل

Crout : $L = \begin{pmatrix}l_{11}&0&0\\ l_{21}&l_{22}&0\\ l_{31}&l_{32}&l_{33}\end{pmatrix}$ , $U = \begin{pmatrix}1&u_{12}&u_{13}\\ 0&1&u_{23}\\ 0&0&1\end{pmatrix}$ .

Identification $A=LU$ colonne par colonne :

Colonne 1 : $l_{11}=2$ , $l_{21}=1$ , $l_{31}=0$ .
Ligne 1 : $l_{11}u_{12}=1\Rightarrow u_{12}=1/2$ ; $l_{11}u_{13}=0\Rightarrow u_{13}=0$ .
Colonne 2 : $l_{21}u_{12}+l_{22}=3\Rightarrow l_{22}=3-1/2=5/2$ ; $l_{31}u_{12}+l_{32}=1\Rightarrow l_{32}=1$ .
Ligne 2 : $l_{21}u_{13}+l_{22}u_{23}=1\Rightarrow u_{23}=1/(5/2)=2/5$ .
Colonne 3 : $l_{31}u_{13}+l_{32}u_{23}+l_{33}=2\Rightarrow l_{33}=2-2/5=8/5$ .

Donc $L=\begin{pmatrix}2&0&0\\1&5/2&0\\0&1&8/5\end{pmatrix},\quad U=\begin{pmatrix}1&1/2&0\\0&1&2/5\\0&0&1\end{pmatrix}.$

Descente $L\mathbf{y}=\mathbf{b}$ :

$2y_1=3\Rightarrow y_1=3/2$ .
$y_1 + (5/2)y_2 = 5\Rightarrow y_2 = (5-3/2)/(5/2) = (7/2)/(5/2) = 7/5$ .
$y_2 + (8/5)y_3 = 3\Rightarrow y_3 = (3-7/5)/(8/5) = (8/5)/(8/5) = 1$ .

Remontée $U\mathbf{x}=\mathbf{y}$ :

$x_3 = 1$ .
$x_2 + (2/5)x_3 = 7/5\Rightarrow x_2 = 7/5-2/5 = 1$ .
$x_1 + (1/2)x_2 = 3/2\Rightarrow x_1 = 3/2-1/2 = 1$ .

Solution : $\mathbf{x}=(1,1,1)^T$ . Vérification : $A(1,1,1)^T=(3,5,3)^T=\mathbf{b}$ . ✓