مسابقة دكتوراه 2016 — Université Echahid Hamma Lakhdar d'El Oued — الموضوع 02

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

Concours d'accès au Doctorat 3e cycle, LMD 2016/2017, Spécialité : Mathématiques Appliquées, Épreuve : Analyse numérique, Faculté Sciences Exactes, Département Mathématiques, Université d'El-Oued, 22 Octobre 2016, durée 1h30.

التمرين 1

Exercice 01 — Méthode du gradient à pas constant

#gradient-method#linear-systems#convergence#spectral-radius

On veut résoudre le système linéaire $Ax = b$ , $x, b \in \mathbb{R}^n$ (avec $A$ symétrique définie positive) par une méthode de gradient à pas constant. Soit $x^*$ la solution de ce système. On propose l'algorithme suivant :

$\begin{cases} x^{(0)},\; r^{(0)} = b - Ax^{(0)} \\ x^{(k+1)} = x^{(k)} + \alpha r^{(k)} \end{cases}$

où $\alpha$ est un réel constant (le pas) et $r^{(k)} = b - Ax^{(k)}$ .

Soit $e^{(k)} = x^{(k)} - x^*$ , $k \geq 0$ . Montrer que $e^{(k)} = (I - \alpha A)^k e^{(0)}$ pour $k \geq 0$ .
Soient $0 < \theta_n \leq \theta_{n-1} \leq \ldots \leq \theta_1$ les valeurs propres de $A$ . Montrer que l'algorithme converge si et seulement si $0 < \alpha \leq \dfrac{2}{\theta_1}$ .
Montrer que le meilleur choix de $\alpha$ est $\alpha_{\mathrm{opt}} = \dfrac{2}{\theta_1 + \theta_n}$ et qu'alors le rayon spectral

$\rho(I - \alpha_{\mathrm{opt}} A) = \frac{\theta_1 - \theta_n}{\theta_1 + \theta_n}.$

◀الحل

1.

$e^{(k+1)} = x^{(k+1)}-x^* = x^{(k)}+\alpha r^{(k)}-x^* = e^{(k)}+\alpha(b-Ax^{(k)}) = e^{(k)}-\alpha A e^{(k)} = (I-\alpha A)e^{(k)}$ . Par récurrence : $e^{(k)} = (I-\alpha A)^k e^{(0)}$ .

2.

Convergence $\Leftrightarrow$ $\rho(I-\alpha A) < 1$ . Les valeurs propres de $I-\alpha A$ sont $1-\alpha\theta_i$ . Condition : $|1-\alpha\theta_i| < 1$ pour tout $i$ , i.e. $0 < \alpha\theta_i < 2$ . La contrainte la plus forte est $\alpha < 2/\theta_1$ . Donc convergence $\Leftrightarrow$ $0 < \alpha < 2/\theta_1$ .

3.

$\rho(I-\alpha A) = \max_i|1-\alpha\theta_i| = \max(|1-\alpha\theta_1|, |1-\alpha\theta_n|)$ . Minimiser en $\alpha$ : l'optimum est $1-\alpha\theta_1 = -(1-\alpha\theta_n)$ , donnant $\alpha_{\mathrm{opt}} = \frac{2}{\theta_1+\theta_n}$ et $\rho = \frac{\theta_1-\theta_n}{\theta_1+\theta_n}$ .

$\boxed{\alpha_{\mathrm{opt}} = \frac{2}{\theta_1+\theta_n}, \quad \rho(I-\alpha_{\mathrm{opt}}A) = \frac{\theta_1-\theta_n}{\theta_1+\theta_n}.}$

التمرين 2

Exercice 02 — Méthode du point fixe pour x = tg(x)

#fixed-point#root-finding#tangent-equation#convergence

Soit l'équation $(1) : x = \tan(x)$ , $x \in \mathbb{R}$ .

Donner un intervalle contenant la plus petite solution strictement positive, notée $\alpha$ , de l'équation $(1)$ .
Peut-on appliquer la méthode du point fixe pour résoudre l'équation $(1)$ , en prenant $g(x) = \tan(x)$ ?
Montrer que la solution $\alpha$ de $(1)$ est aussi solution de l'équation $(2) : x = \pi + \arctan(x)$ .
Peut-on appliquer la méthode du point fixe pour résoudre l'équation $(2)$ , en prenant $g(x) = \pi + \arctan(x)$ ?

◀الحل

1.

La fonction $\tan$ a des discontinuités en $\pi/2 + k\pi$ . La plus petite solution positive est dans $]\pi, 3\pi/2[$ , plus précisément $\alpha \approx 4.49$ . On peut prendre l'intervalle $]\pi, 3\pi/2[$ .

2.

$g(x) = \tan(x)$ , $g'(x) = 1+\tan^2(x) \geq 1$ . La méthode du point fixe requiert $|g'| < 1$ sur l'intervalle, ce qui n'est pas satisfait. On ne peut pas appliquer la méthode avec $g(x) = \tan(x)$ .

3.

$\alpha = \tan(\alpha)$ et $\alpha \in ]\pi, 3\pi/2[$ donc $\arctan(\tan(\alpha)) = \alpha - \pi$ , i.e. $\arctan(\alpha) = \alpha - \pi$ , d'où $\alpha = \pi + \arctan(\alpha)$ .

4.

$g(x) = \pi + \arctan(x)$ , $g'(x) = \frac{1}{1+x^2}$ . Pour $x \in ]\pi, 3\pi/2[$ , $|g'(x)| < 1$ . On peut appliquer la méthode du point fixe, elle converge vers $\alpha$ .

$\boxed{\alpha \approx 4.493 \text{ ; méthode convergente avec } g(x) = \pi + \arctan(x).}$

التمرين 3

Exercice 03 — Schéma Saute-Mouton pour l'équation de transport

#numerical-schemes#transport-equation#stability#finite-differences

On considère le schéma « Saute-Mouton » pour approcher l'équation de transport : $\dfrac{\partial u}{\partial t} + a\dfrac{\partial u}{\partial x} = 0$ , où $a > 0$ , sur une grille spatiale régulière de pas $\Delta x$ et avec un pas de temps $\Delta t$ :

$u_j^{n+1} = u_j^{n-1} - \lambda(u_{j+1}^n - u_{j-1}^n), \quad n \geq 1$

où $u_j^0$ et $u_j^1$ sont donnés et $\lambda = a\dfrac{\Delta t}{\Delta x}$ .

Quel est l'ordre de ce schéma ?
On suppose que $u_j^0 = U_0 \exp(i\xi_j \Delta x)$ et $u_j^1 = U_1 \exp(i\xi_j \Delta x)$ . Montrer que la solution du schéma peut s'écrire sous la forme $u_j^n = U_n \exp(i\xi_j \Delta x)$ avec $U_n = A(r_+)^n + B(r_-)^n$ , $r_+$ et $r_-$ solutions d'une équation que l'on précisera. En déduire une condition nécessaire et suffisante de stabilité du schéma.

◀الحل

1.

Le schéma est d'ordre 2 en temps et en espace (erreur de troncature $O(\Delta t^2 + \Delta x^2)$ ).

2.

En substituant $u_j^n = U_n e^{i\xi j\Delta x}$ dans le schéma : $U_{n+1} = U_{n-1} - \lambda(e^{i\xi\Delta x}-e^{-i\xi\Delta x})U_n = U_{n-1} - 2i\lambda\sin(\xi\Delta x)U_n$ .

C'est une récurrence d'ordre 2 : $U_{n+1} + 2i\lambda\sin(\xi\Delta x)U_n - U_{n-1} = 0$ . L'équation caractéristique est :

$r^2 + 2i\lambda\sin(\xi\Delta x)r - 1 = 0$

dont les racines sont $r_{\pm} = -i\lambda\sin(\xi\Delta x) \pm \sqrt{1-\lambda^2\sin^2(\xi\Delta x)}$ .

Stabilité (condition de Von Neumann) : $|r_\pm| \leq 1$ pour tout $\xi$ . Si $\lambda^2\sin^2(\xi\Delta x) \leq 1$ , alors $|r_\pm|=1$ . Condition de stabilité :

$\boxed{\lambda = a\frac{\Delta t}{\Delta x} \leq 1 \quad \text{(condition CFL)}.}$

→←

→السابقConcours Doctorat 2016 — Université Abderrahmane Mira - Béjaïa — Épreuve N°02 التاليConcours Doctorat 2016 — École Nationale Supérieure de Statistique et d'Économie Appliquée (ENSSEA) — Épreuve N°02←