Résolution Numérique
La résolution numérique consiste à trouver une solution approchée d'une équation de la forme \( f(x) = 0 \), souvent dans les cas où une solution analytique est impossible ou complexe à obtenir. Cette approche repose sur des algorithmes itératifs qui convergent vers la solution avec une précision prédéfinie. Voici les principales méthodes étudiées :
Méthode de Dichotomie
La méthode de dichotomie est une méthode simple et robuste qui repose sur le théorème des valeurs intermédiaires. Elle est utilisée lorsqu'une fonction \( f(x) \) est continue et change de signe sur un intervalle \([a, b]\), c'est-à-dire \( f(a) \cdot f(b) < 0 \).
Étapes :
- 1. Vérifier que \( f(a) \cdot f(b) < 0 \).
- 2. Calculer le milieu de l'intervalle : \( m = \frac{a + b}{2} \).
- 3. Évaluer \( f(m) \) :
- Si \( f(m) = 0 \), alors \( m \) est la solution exacte.
- Sinon, on réduit l'intervalle à \([a, m]\) ou \([m, b]\), selon le signe de \( f(m) \).
- 4. Répéter l'étape 2 jusqu'à atteindre la précision souhaitée \( \varepsilon \), c'est-à-dire lorsque \( |b - a| < \varepsilon \).
Convergence : La méthode de dichotomie a une convergence linéaire. Le nombre d'itérations \( n \) nécessaire pour obtenir une précision \( \varepsilon \) est donné par :
\[ n \geq \log_2\left(\frac{b - a}{\varepsilon}\right). \]
Exemple : Trouver une racine de \( f(x) = x^2 - 2 \) dans l'intervalle \([1, 2]\) avec une précision de \( \varepsilon = 0.01 \).
Après plusieurs itérations, la solution converge vers \( \sqrt{2} \approx 1.4142 \).
Méthode de la Sécante
La méthode de la sécante est une méthode itérative qui utilise une interpolation linéaire entre deux points pour approximer la solution. Elle nécessite deux approximations initiales \( x_0 \) et \( x_1 \).
Formule :
\[ x_{n+1} = x_n - f(x_n) \cdot \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}. \]
Étapes :
- 1. Choisir deux approximations initiales \( x_0 \) et \( x_1 \).
- 2. Calculer \( x_2 \) en utilisant la formule de la sécante.
- 3. Répéter l'étape 2 jusqu'à convergence.
Convergence : La méthode de la sécante a une convergence quasi-quadratique. Elle converge plus rapidement que la dichotomie, mais nécessite des approximations initiales proches de la solution.
Exemple : Trouver une racine de \( f(x) = x^2 - 2 \) avec \( x_0 = 1 \) et \( x_1 = 2 \).
- \( x_2 = 1.3333 \).
- \( x_3 = 1.4118 \).
- \( x_4 = 1.4142 \).
Méthode de Newton
La méthode de Newton repose sur l'approximation locale de \( f(x) \) par sa tangente au point courant \( x_n \). Elle est très rapide mais nécessite la dérivée de \( f \).
Formule :
\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. \]
Étapes :
Convergence : La méthode de Newton converge quadratiquement si l'approximation initiale est suffisamment proche de la solution.
Exemple : Trouver une racine de \( f(x) = x^2 - 2 \) avec \( f'(x) = 2x \) et \( x_0 = 1.5 \).
- \( x_1 = 1.4167 \).
- \( x_2 = 1.4142 \).
La solution converge rapidement vers \( \sqrt{2} \).
Méthode de Lagrange (Fausse Position)
La méthode de Lagrange, aussi appelée méthode de la fausse position, est une variante de la méthode de la sécante qui conserve les propriétés de changement de signe de \( f \). Elle garantit que la solution reste dans l'intervalle donné.
Formule :
\[ x = a - \frac{f(a) \cdot (b - a)}{f(b) - f(a)}. \]
Étapes :
- 1. Vérifier \( f(a) \cdot f(b) < 0 \).
- 2. Calculer \( x \) avec la formule de Lagrange.
- 3. Réduire l'intervalle et répéter jusqu'à convergence.
Exemple : Trouver une racine de \( f(x) = x^3 - 2 \) dans \([1, 2]\).
Après plusieurs itérations, la solution converge vers \( \sqrt[3]{2} \).
Interpolation Polynomiale
L’interpolation polynomiale consiste à approximer une fonction \( f(x) \) en construisant un polynôme \( P(x) \) qui passe par un ensemble de points donnés \((x_i, y_i)\). Cela est utile pour estimer les valeurs de \( f(x) \) entre des points connus ou pour simplifier des calculs numériques.
Méthode de Lagrange
La méthode de Lagrange est une technique d’interpolation qui construit un polynôme d’interpolation unique sous la forme :
\[ P(x) = \sum_{i=0}^{n} y_i \cdot L_i(x), \]
où \( L_i(x) \) est le \( i \)-ème polynôme de Lagrange défini par :
\[ L_i(x) = \prod_{\substack{j=0 \\ j \neq i}}^{n} \frac{x - x_j}{x_i - x_j}. \]
Étapes :
- 1. Identifier les points d’interpolation \((x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\).
- 2. Calculer les polynômes \( L_i(x) \) pour chaque \( i \).
- 3. Construire le polynôme \( P(x) \) en combinant les \( L_i(x) \) avec les \( y_i \).
Exemple : Interpoler \( f(x) \) avec les points \((1, 1), (2, 4), (3, 9)\).
Solution :
- \( L_0(x) = \frac{(x - 2)(x - 3)}{(1 - 2)(1 - 3)} = \frac{(x - 2)(x - 3)}{2} \).
- \( L_1(x) = \frac{(x - 1)(x - 3)}{(2 - 1)(2 - 3)} = -(x - 1)(x - 3) \).
- \( L_2(x) = \frac{(x - 1)(x - 2)}{(3 - 1)(3 - 2)} = \frac{(x - 1)(x - 2)}{2} \).
- Le polynôme d'interpolation est alors :
\[
P(x) = 1 \cdot \frac{(x - 2)(x - 3)}{2} - 4 \cdot (x - 1)(x - 3) + 9 \cdot \frac{(x - 1)(x - 2)}{2}.
\]
Propriétés :
- Le polynôme \( P(x) \) est unique pour un ensemble donné de points.
- Le degré de \( P(x) \) est au plus \( n \), où \( n \) est le nombre de points - 1.
Méthode de Newton-Cotes
La méthode de Newton-Cotes est utilisée pour l’intégration numérique en interpolant la fonction \( f(x) \) à l’aide d’un polynôme, puis en intégrant ce polynôme. Elle est particulièrement utile lorsque les valeurs de \( f(x) \) sont données à des points régulièrement espacés.
Formule générale : Pour une fonction \( f(x) \) donnée sur un intervalle \([a, b]\) divisé en \( n \) sous-intervalles égaux de longueur \( h = \frac{b - a}{n} \), l’intégrale est approximée par :
\[ \int_a^b f(x) \, dx \approx \sum_{i=0}^{n} w_i \cdot f(x_i), \]
où \( w_i \) sont les poids associés aux points \( x_i \).
Méthodes spécifiques de Newton-Cotes :
- Règle du trapèze : \[ \int_a^b f(x) \, dx \approx \frac{h}{2} \left( f(a) + f(b) \right). \] Cette méthode utilise une interpolation linéaire entre les points \( a \) et \( b \).
- Règle de Simpson : \[ \int_a^b f(x) \, dx \approx \frac{h}{3} \left( f(a) + 4f\left(\frac{a+b}{2}\right) + f(b) \right). \] Cette méthode utilise une interpolation quadratique.
- Règle de Simpson 3/8 : \[ \int_a^b f(x) \, dx \approx \frac{3h}{8} \left( f(a) + 3f\left(\frac{2a+b}{3}\right) + 3f\left(\frac{a+2b}{3}\right) + f(b) \right). \] Cette méthode utilise une interpolation cubique.
Exemple : Approximer l’intégrale de \( f(x) = x^2 \) sur \([0, 2]\) avec la règle de Simpson.
- Points : \( x_0 = 0 \), \( x_1 = 1 \), \( x_2 = 2 \).
- Valeurs : \( f(0) = 0 \), \( f(1) = 1 \), \( f(2) = 4 \).
- Calcul : \[ \int_0^2 x^2 \, dx \approx \frac{2 - 0}{6} \left( 0 + 4 \cdot 1 + 4 \right) = \frac{2}{6} \cdot 8 = \frac{16}{6} = 2.6667. \]
Note : La précision des méthodes de Newton-Cotes dépend du degré du polynôme utilisé pour l’interpolation. Pour des fonctions très oscillantes, des méthodes avancées comme les quadratures de Gauss sont préférées.
Convergence et Ordre de Convergence
Lorsqu'une méthode numérique est utilisée pour résoudre une équation ou une approximation, il est essentiel d'étudier sa convergence et son ordre de convergence. Ces notions permettent de mesurer l'efficacité et la précision de la méthode.
Convergence
Une méthode numérique converge si, en augmentant le nombre d'itérations \( n \) (ou en diminuant le pas \( h \)), la solution approchée se rapproche de la solution exacte.
Définition :
Soit une séquence \( \{x_n\} \) obtenue par une méthode numérique pour résoudre une équation \( f(x) = 0 \). La méthode est dite convergente si : \[ \lim_{n \to \infty} x_n = x^*, \] où \( x^* \) est la solution exacte.
Exemple :
Considérons la méthode de dichotomie pour résoudre \( f(x) = 0 \). La séquence des approximations \( x_n \) converge toujours vers la solution \( x^* \), car l'intervalle contenant \( x^* \) se réduit à chaque itération.
Ordre de Convergence
L'ordre de convergence mesure la vitesse à laquelle une méthode convergente atteint la solution exacte.
Définition :
Une méthode numérique a un ordre de convergence \( p \) si l'erreur \( e_n = |x_n - x^*| \) satisfait la relation : \[ e_{n+1} \approx C \cdot e_n^p, \] où \( C > 0 \) est une constante et \( p \) est l'ordre de convergence.
Types de convergence :
- Si \( p = 1 \), la méthode a une convergence linéaire.
- Si \( p = 2 \), la méthode a une convergence quadratique.
- Si \( p > 2 \), la méthode est dite à convergence superlinéaire.
Exemple : Méthode de Newton
- Pour une méthode de Newton, l'erreur est donnée par : \[ e_{n+1} = C \cdot e_n^2. \] Cela indique que la méthode de Newton a une convergence quadratique.
- Dans la pratique, cela signifie que l'erreur est réduite de moitié en environ une itération.
Étude de l'Erreur
L'étude de l'erreur consiste à analyser la différence entre la solution exacte \( x^* \) et la solution approchée \( x_n \). Cela est crucial pour évaluer la précision d'une méthode numérique.
Erreur Globale et Erreur Locale
- Erreur globale : La différence entre la solution exacte et la solution approchée après \( n \) itérations : \[ E_n = |x_n - x^*|. \]
- Erreur locale : L'erreur introduite à chaque étape de la méthode. Par exemple, pour une méthode par pas \( h \), l'erreur locale est donnée par : \[ e_{\text{local}} \approx C \cdot h^p, \] où \( p \) est l'ordre de la méthode.
Étude de l'Erreur dans des Méthodes Spécifiques
- Méthode de la dichotomie :
À chaque itération, l'intervalle contenant la solution est divisé par 2. L'erreur après \( n \) itérations est donnée par : \[ E_n = \frac{b - a}{2^n}, \] où \([a, b]\) est l'intervalle initial.
- Méthode de Newton :
Pour une méthode de Newton, l'erreur au bout de \( n \) itérations est approximativement : \[ E_n = C \cdot (E_{n-1})^2, \] ce qui montre une convergence quadratique.
Étude de l'Erreur dans l'Interpolation
Lors de l'interpolation polynomiale, l'erreur est donnée par :
\[ R(x) = f(x) - P(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x - x_i), \]
où \( \xi \) est un point dans \([a, b]\).
Remarque : L'erreur dépend de la régularité de \( f(x) \) et de la répartition des points d'interpolation \((x_i)\).
Applications et Importance
- Permet de choisir la méthode numérique la plus adaptée en fonction de la précision souhaitée.
- Aide à déterminer le nombre d’itérations ou la taille de pas nécessaire pour atteindre une erreur acceptable.
- Utilisée pour vérifier la stabilité et l’efficacité des algorithmes numériques.
0 Commentaires