Ce document, destiné aux étudiants des filières universitaires SM4 et SMI4, présente un examen d'Analyse Numérique. Il vise à évaluer la compréhension des concepts fondamentaux et l'application pratique des méthodes numériques.
Il couvre les notions suivantes:
- Définition d'algorithmes et approches de résolution de systèmes linéaires.
- Factorisation LU de matrices et utilisation de matrices de permutation.
- Résolution d'équations non linéaires par la méthode de dichotomie.
- Méthode de Newton, points fixes et leur attractivité.
Analyse Numérique : Résolution de Systèmes Linéaires et d'Équations Non Linéaires
Questions de Cours
Qu'est-ce qu'un algorithme en Analyse Numérique ?
En analyse numérique, un algorithme est une suite finie et bien définie d'instructions pour résoudre un problème mathématique donné. Il se caractérise par sa clarté, sa déterminisme, sa finitude et sa capacité à produire une solution approchée avec une précision spécifiée, tout en étant stable et efficace.
Approches pour la Résolution de Systèmes Linéaires
Il existe deux grandes catégories d'approches numériques pour résoudre un système linéaire Ax = b :
- Méthodes directes : Elles fournissent la solution exacte (en l'absence d'erreurs d'arrondi) en un nombre fini d'opérations. Elles sont généralement utilisées pour les systèmes de petite à moyenne taille.
- Exemples : Méthode d'élimination de Gauss, Factorisation LU, Factorisation de Cholesky (pour les matrices symétriques définies positives).
- Méthodes itératives : Elles génèrent une suite d'approximations qui convergent progressivement vers la solution exacte. Elles sont souvent préférables pour les grands systèmes linéaires, particulièrement les matrices creuses.
- Exemples : Méthode de Jacobi, Méthode de Gauss-Seidel, Méthode du Gradient Conjugué.
Problème 1 : Factorisation LU et Résolution de Systèmes Linéaires
Ce problème explore l'application de la factorisation LU pour la résolution de systèmes d'équations linéaires, une technique fondamentale en algèbre linéaire numérique.
1. Étude du premier système (Matrice A<sub>1</sub>)
- a. Calculer la factorisation LU de la matrice A<sub>1</sub>.
La factorisation LU décompose une matrice carrée A en un produit d'une matrice triangulaire inférieure L (Lower) et d'une matrice triangulaire supérieure U (Upper). Cette décomposition permet de transformer un système complexe en deux systèmes triangulaires plus simples à résoudre. - b. Résoudre le système linéaire A<sub>1</sub>x = b<sub>1</sub> en utilisant la factorisation LU de A<sub>1</sub>.
Une fois A<sub>1</sub> = LU est obtenue, le système A<sub>1</sub>x = b<sub>1</sub> est équivalent à LUx = b<sub>1</sub>. On résout d'abord Ly = b<sub>1</sub> par substitution avant, puis Ux = y par substitution arrière pour trouver x.
2. Étude du deuxième système (Matrice A<sub>2</sub>)
- a. Vérifier que l'algorithme de factorisation LU pour la matrice A<sub>2</sub> ne peut pas être exécuté jusqu'au bout.
La factorisation LU standard peut échouer si un élément pivot (diagonal) devient nul ou très proche de zéro pendant le processus d'élimination, ce qui rend la division impossible ou instable numériquement. - b. Trouver une matrice P de permutation de façon à ce que la matrice PA<sub>2</sub> soit factorisable, puis calculer la factorisation LU de PA<sub>2</sub>.
Pour contourner le problème des pivots nuls, on utilise le pivotage partiel ou total, qui implique une permutation des lignes (représentée par la matrice P) pour garantir un pivot non nul et maximiser la stabilité numérique. La factorisation obtenue est alors PA = LU. - c. Résoudre le système linéaire A<sub>2</sub>x = b<sub>2</sub> en utilisant la factorisation trouvée.
En partant du système original A<sub>2</sub>x = b<sub>2</sub>, on le multiplie par P pour obtenir PA<sub>2</sub>x = Pb<sub>2</sub>. Puis, en utilisant la factorisation PA<sub>2</sub> = LU, on résout LUx = Pb<sub>2</sub> par double substitution comme précédemment.
3. Calcul du déterminant des matrices A<sub>1</sub> et A<sub>2</sub>
Calculer le déterminant des matrices A<sub>1</sub> et A<sub>2</sub> en utilisant leurs factorisations LU.
Le déterminant d'une matrice A est simplement le produit des déterminants de ses facteurs. Étant donné que det(L) = 1 (pour L avec des 1 sur la diagonale) et det(U) est le produit de ses éléments diagonaux, alors det(A) = det(U). Si une permutation P est utilisée (PA = LU), alors det(A) = det(P) × det(U), où det(P) est soit 1 soit -1 selon le nombre de transpositions de lignes effectuées.
Problème 2 : Résolution d'Équations Non Linéaires
Ce problème aborde la recherche des racines de l'équation quadratique x² + x = 0 à l'aide de méthodes numériques.
1. Étude de la fonction f(x) = x² + x
- a. Tracer approximativement le graphe de la fonction.
La fonction f(x) = x² + x est une parabole ouverte vers le haut, qui coupe l'axe des abscisses aux points où f(x) = 0. Son sommet est situé à x = -b/(2a) = -1/2. - b. Encadrer les deux racines α<sub>1</sub> et α<sub>2</sub> de la fonction par des intervalles de longueur 1.
Les racines de l'équation x² + x = 0 (soit x(x+1)=0) sont α<sub>1</sub> = 0 et α<sub>2</sub> = -1. Des intervalles de longueur 1 encadrant ces racines pourraient être, par exemple, [-1.5, -0.5] pour -1 et [-0.5, 0.5] pour 0. - c. Montrer que α<sub>1</sub> + α<sub>2</sub> = -1 (Propriété des équations de second degré).
Pour toute équation quadratique de la forme ax² + bx + c = 0, la somme des racines est donnée par -b/a. Pour l'équation x² + x = 0, nous avons a=1 et b=1, donc la somme des racines est -1/1 = -1.
2. Approche d'une racine par dichotomie
La méthode de dichotomie (ou bissection) est une méthode robuste pour trouver les racines d'une fonction continue, en divisant répétitivement un intervalle de recherche.
- a. Appliquer la dichotomie jusqu’à l’encadrement d’une des deux racines par un intervalle de longueur 0.25.
La méthode commence par un intervalle [a, b] où f(a) et f(b) ont des signes opposés. À chaque étape, l'intervalle est divisé en deux, et le sous-intervalle où la racine doit se trouver est sélectionné, réduisant ainsi l'incertitude de moitié. - b. En déduire un intervalle d’encadrement de longueur 0.25 pour l’autre racine.
Connaissant une racine avec une certaine précision, et en utilisant les propriétés des équations quadratiques (comme la somme ou le produit des racines), il est possible de déduire la position approximative de l'autre racine.
3. Résolution par la méthode de Newton
La méthode de Newton-Raphson est une méthode itérative puissante qui utilise la dérivée de la fonction pour trouver ses racines, caractérisée par une convergence rapide sous certaines conditions.
- a. Donner la fonction g de point fixe associée à cette méthode.
La méthode de Newton est donnée par l'itération x<sub>n+1</sub> = x<sub>n</sub> - f(x<sub>n</sub>)/f'(x<sub>n</sub>). La fonction de point fixe g(x) est donc g(x) = x - f(x)/f'(x). Pour f(x) = x² + x, f'(x) = 2x + 1. Ainsi, g(x) = x - (x² + x)/(2x + 1). - b. Montrer que les deux racines sont des points fixes attractifs de g.
Un point fixe x* de g est attractif si |g'(x*)| < 1. Pour la méthode de Newton, il est souvent vrai que g'(x*) = 0 aux racines simples de f(x), ce qui garantit une convergence quadratique (extrêmement rapide) vers la racine. - c. Comment doit-on choisir le point initial x<sub>0</sub> pour converger vers l'une des racines ?
Le choix du point initial x<sub>0</sub> est crucial pour la méthode de Newton. Pour assurer la convergence vers une racine spécifique, x<sub>0</sub> doit être choisi suffisamment proche de cette racine. Un mauvais choix de x<sub>0</sub> peut entraîner une convergence vers une autre racine, une divergence, ou même la convergence vers un cycle.
FAQ - Questions Fréquentes en Analyse Numérique
Qu'est-ce qu'une factorisation LU ?
La factorisation LU est une méthode de décomposition d'une matrice carrée A en le produit d'une matrice triangulaire inférieure (L) et d'une matrice triangulaire supérieure (U). Elle est fondamentale en algèbre linéaire numérique car elle simplifie considérablement la résolution de systèmes d'équations linéaires, l'inversion de matrices et le calcul de déterminants.
Pourquoi est-il parfois nécessaire d'utiliser une matrice de permutation (P) avec la factorisation LU ?
Une matrice de permutation P est nécessaire lorsqu'un élément pivot (l'élément diagonal utilisé pour l'élimination) est nul ou très proche de zéro, ce qui entraînerait une division par zéro ou des erreurs numériques importantes. L'utilisation de P, via le pivotage, permet d'échanger des lignes pour éviter ces problèmes, assurant ainsi la stabilité et la faisabilité de l'algorithme de factorisation LU (PA=LU).
Comment la méthode de dichotomie garantit-elle la recherche d'une racine ?
La méthode de dichotomie repose sur le théorème des valeurs intermédiaires. Si une fonction continue f(x) change de signe sur un intervalle [a, b] (c'est-à-dire f(a) * f(b) < 0), alors il existe au moins une racine dans cet intervalle. La méthode divise l'intervalle en deux à chaque itération, garantissant que la racine reste dans le nouvel intervalle plus petit, et réduit ainsi l'incertitude de moitié à chaque étape jusqu'à atteindre la précision souhaitée.