Guide Complet d'Algorithmique Numérique

Partie 1 : Résolution d'Équations Non Linéaires

1.1 Méthode de Dichotomie (Bissection)

Principe de base : On cherche une racine de f(x) = 0 dans l'intervalle [a,b] où f(a) et f(b) sont de signes
opposés.

Algorithme :

1. Calculer c = (a + b) / 2 (milieu de l'intervalle)

2. Si f(c) ≈ 0 ou |b - a| < ε, STOP → c est la solution

3. Si f(a) × f(c) < 0, alors b = c (la racine est dans [a,c])

4. Sinon a = c (la racine est dans [c,b])

5. Retour à l'étape 1

Avantages : Toujours convergente si f continue et f(a)×f(b) < 0 Inconvénients : Convergence lente

À retenir pour l'écrit :

Vérifier f(a)×f(b) < 0 au départ

Convergence linéaire : l'erreur est divisée par 2 à chaque itération

Nombre d'itérations : n ≥ log₂((b-a)/ε)

1.2 Méthode du Point Fixe

Principe de base : Transformer f(x) = 0 en x = g(x), puis itérer : x_{n+1} = g(x_n)

Algorithme :

1. Choisir x₀ (valeur initiale)

2. Calculer x₁ = g(x₀)

3. Si |x₁ - x₀| < ε, STOP → x₁ est la solution

4. Poser x₀ = x₁ et retour à l'étape 2

Condition de convergence : |g'(x)| < 1 au voisinage de la solution

À retenir pour l'écrit :

Plusieurs formulations possibles : si f(x) = x² - 3 = 0, on peut prendre g(x) = √3 ou g(x) = 3/x

 Vérifier |g'(x)| < 1 pour garantir la convergence

Si |g'(α)| < 1 près de la racine α, la méthode converge

1.3 Méthode de Newton-Raphson

Principe de base : Approximation linéaire de f par sa tangente.

Formule : x_{n+1} = x_n - f(x_n) / f'(x_n)

Algorithme :

1. Choisir x₀

2. Calculer x₁ = x₀ - f(x₀)/f'(x₀)

3. Si |x₁ - x₀| < ε, STOP

4. x₀ = x₁, retour à l'étape 2

Avantages : Convergence quadratique (très rapide) Inconvénients : Nécessite f'(x), peut diverger si x₀ mal
choisi

À retenir pour l'écrit :

Convergence quadratique : l'erreur est au carré à chaque itération

Attention si f'(x) = 0 (division par zéro)

Bon choix de x₀ crucial

1.4 Méthode de la Sécante

Principe de base : Approximation de la dérivée par différence finie (évite le calcul de f')

Formule : x_{n+1} = x_n - f(x_n) × (x_n - x_{n-1}) / (f(x_n) - f(x_{n-1}))

Algorithme :

1. Choisir x₀ et x₁

2. Calculer x₂ avec la formule ci-dessus

3. Si |x₂ - x₁| < ε, STOP

4. x₀ = x₁, x₁ = x₂, retour à l'étape 2

Avantages : Pas besoin de f', convergence rapide (super-linéaire) Inconvénients : Nécessite 2 valeurs initiales
1.5 Méthode de la Corde (Fausse Position)

Principe de base : Combinaison de dichotomie et sécante

Formule : c = a - f(a) × (b - a) / (f(b) - f(a))

Algorithme :

1. Vérifier f(a) × f(b) < 0

2. Calculer c avec la formule

3. Si |f(c)| < ε, STOP

4. Si f(a) × f(c) < 0 : b = c, sinon a = c

5. Retour à l'étape 2

Avantages : Plus rapide que dichotomie, toujours convergente Inconvénients : Plus lente que Newton

Exercice 1 : Dichotomie
Énoncé : Résoudre f(x) = x³ - x - 1 = 0 dans [1, 2] avec ε = 0.01

Solution détaillée :

Vérification initiale :

f(1) = 1 - 1 - 1 = -1

f(2) = 8 - 2 - 1 = 5

f(1) × f(2) = -5 < 0 ✓

Itération 1 :

c₁ = (1 + 2)/2 = 1.5

f(1.5) = 3.375 - 1.5 - 1 = 0.875 > 0

f(1) × f(1.5) < 0 → nouvelle intervalle [1, 1.5]

Itération 2 :

c₂ = (1 + 1.5)/2 = 1.25

f(1.25) = 1.953 - 1.25 - 1 = -0.297 < 0

f(1.25) × f(1.5) < 0 → nouvelle intervalle [1.25, 1.5]

Itération 3 :
 c₃ = (1.25 + 1.5)/2 = 1.375

f(1.375) = 2.599 - 1.375 - 1 = 0.224 > 0

Nouvelle intervalle [1.25, 1.375]

Itération 4 :

c₄ = (1.25 + 1.375)/2 = 1.3125

f(1.3125) ≈ -0.051 < 0

Nouvelle intervalle [1.3125, 1.375]

Itération 5 :

c₅ = 1.34375

|1.375 - 1.3125| = 0.0625 > 0.01, on continue...

Solution approximative : x ≈ 1.324 (après convergence)

Exercice 2 : Méthode de Newton

Énoncé : Résoudre f(x) = x² - 2 = 0 avec x₀ = 1 et ε = 0.001

Solution détaillée :

f(x) = x² - 2
f'(x) = 2x

Itération 1 :

x₁ = x₀ - f(x₀)/f'(x₀)

x₁ = 1 - (1 - 2)/(2×1) = 1 - (-1/2) = 1.5

Itération 2 :

f(1.5) = 2.25 - 2 = 0.25

f'(1.5) = 3

x₂ = 1.5 - 0.25/3 = 1.5 - 0.0833 = 1.4167

Itération 3 :

f(1.4167) = 2.007 - 2 = 0.007

f'(1.4167) = 2.8334
 x₃ = 1.4167 - 0.007/2.8334 = 1.4142

Itération 4 :

|x₃ - x₂| = 0.0025 > 0.001

x₄ = 1.4142 - f(1.4142)/f'(1.4142) ≈ 1.41421

Solution : x ≈ 1.41421 ≈ √2 ✓

Exercice 3 : Méthode de la Sécante

Énoncé : Résoudre f(x) = cos(x) - x = 0 avec x₀ = 0, x₁ = 1

Solution détaillée :

Itération 1 :

f(0) = cos(0) - 0 = 1

f(1) = cos(1) - 1 ≈ 0.540 - 1 = -0.460

x₂ = 1 - (-0.460) × (1-0)/(−0.460-1)

x₂ = 1 - (-0.460)/(-1.460) = 1 - 0.315 = 0.685

Itération 2 :

f(0.685) = cos(0.685) - 0.685 ≈ 0.776 - 0.685 = 0.091

x₃ = 0.685 - 0.091 × (0.685-1)/(0.091-(-0.460))

x₃ = 0.685 - 0.091 × (-0.315)/0.551 = 0.737

Itération 3 :

f(0.737) ≈ 0.006

x₄ ≈ 0.739

Solution : x ≈ 0.739 (point fixe de cos)

Partie 2 : Résolution de Systèmes Linéaires

2.1 Méthode de Gauss (Élimination)

Principe : Transformer le système Ax = b en système triangulaire supérieur

Étapes :

1. Phase d'élimination : Créer des zéros sous la diagonale

2. Remontée (substitution) : Résoudre de bas en haut

Algorithme détaillé :

Pour chaque ligne i de 1 à n-1 :

Pour chaque ligne j de i+1 à n :

Calculer multiplicateur : m = a[j][i] / a[i][i]

Pour chaque colonne k de i à n :

a[j][k] = a[j][k] - m × a[i][k]

b[j] = b[j] - m × b[i]

À retenir pour l'écrit :

Pivot : élément diagonal a[i][i] (ne doit pas être nul)

Complexité : O(n³)

Attention aux pivots nuls → permutation de lignes

2.2 Méthode de Gauss-Jordan

Principe : Aller jusqu'à la matrice identité (pas seulement triangulaire)

Différence avec Gauss :

Crée des zéros PARTOUT (au-dessus ET en-dessous de la diagonale)

Diagonalise complètement la matrice

Solution directe sans remontée

Avantage : Solution directe Inconvénient : Plus d'opérations que Gauss simple

2.3 Décomposition LU (Crout/Doolittle)

Principe : Décomposer A = L × U

L : matrice triangulaire inférieure

U : matrice triangulaire supérieure

Méthode : Résoudre Ax = b devient :

1. Ly = b (descente)

2. Ux = y (remontée)

Avantage : Si on résout plusieurs systèmes avec même A mais différents b, on décompose A une seule fois

Décomposition de Doolittle : diag(L) = (1,1,...,1) Décomposition de Crout : diag(U) = (1,1,...,1)

Exercice 4 : Méthode de Gauss

Énoncé : Résoudre le système :

2x + y - z = 8
-3x - y + 2z = -11
-2x + y + 2z = -3

Solution détaillée :

Matrice augmentée initiale :

[ 2 1 -1 | 8 ]
[-3 -1 2 | -11]
[-2 1 2 | -3 ]

Étape 1 : Éliminer x dans L2 et L3

Pour L2 : m₂₁ = -3/2 = -1.5

L2 = L2 - (-1.5)×L1
L2 = [-3, -1, 2, -11] + 1.5×[2, 1, -1, 8]
L2 = [-3, -1, 2, -11] + [3, 1.5, -1.5, 12]
L2 = [0, 0.5, 0.5, 1]

Pour L3 : m₃₁ = -2/2 = -1

L3 = L3 - (-1)×L1
L3 = [-2, 1, 2, -3] + [2, 1, -1, 8]
L3 = [0, 2, 1, 5]

Matrice après étape 1 :

 [ 2 1 -1 | 8]
[ 0 0.5 0.5| 1]
[0 2 1 | 5]

Étape 2 : Éliminer y dans L3

m₃₂ = 2/0.5 = 4

L3 = L3 - 4×L2
L3 = [0, 2, 1, 5] - 4×[0, 0.5, 0.5, 1]
L3 = [0, 2, 1, 5] - [0, 2, 2, 4]
L3 = [0, 0, -1, 1]

Matrice triangulaire finale :

[ 2 1 -1 | 8]
[ 0 0.5 0.5| 1]
[ 0 0 -1 | 1]

Étape 3 : Remontée

De L3 : -z = 1 → z = -1

De L2 : 0.5y + 0.5z = 1 → 0.5y + 0.5(-1) = 1 → 0.5y = 1.5 → y = 3

De L1 : 2x + y - z = 8 → 2x + 3 - (-1) = 8 → 2x = 4 → x = 2

Solution : (x, y, z) = (2, 3, -1)

Vérification :

2(2) + 3 - (-1) = 4 + 3 + 1 = 8 ✓

-3(2) - 3 + 2(-1) = -6 - 3 - 2 = -11 ✓

-2(2) + 3 + 2(-1) = -4 + 3 - 2 = -3 ✓

Exercice 5 : Décomposition LU
Énoncé : Décomposer A en LU puis résoudre Ax = b avec :

A = [ 1 2 3] b = [14]
[ 2 5 7] [30]
[ 3 5 3] [20]
Solution détaillée :

Phase 1 : Décomposition A = LU (méthode de Doolittle)

On cherche L et U telles que A = LU avec diag(L) = (1,1,1)

L = [1 0 0] U = [u11 u12 u13]

[l21 1 0] [0 u22 u23]
[l31 l32 1] [0 0 u33]

Calculs ligne par ligne :

Ligne 1 de U :

u₁₁ = 1, u₁₂ = 2, u₁₃ = 3

Colonne 1 de L :

l₂₁ = 2/1 = 2

l₃₁ = 3/1 = 3

Ligne 2 de U :

u₂₂ = 5 - l₂₁×u₁₂ = 5 - 2×2 = 1

u₂₃ = 7 - l₂₁×u₁₃ = 7 - 2×3 = 1

Colonne 2 de L :

l₃₂ = (5 - l₃₁×u₁₂)/u₂₂ = (5 - 3×2)/1 = -1

Ligne 3 de U :

u₃₃ = 3 - l₃₁×u₁₃ - l₃₂×u₂₃ = 3 - 3×3 - (-1)×1 = 3 - 9 + 1 = -5

Résultat :

L = [1 0 0] U = [1 2 3]
[2 1 0] [0 1 1]
[3 -1 1] [0 0 -5]

Phase 2 : Résolution de Ly = b (descente)

y₁ = 14
2y₁ + y₂ = 30 → y₂ = 30 - 28 = 2
3y₁ - y₂ + y₃ = 20 → y₃ = 20 - 42 + 2 = -20
y = [14, 2, -20]ᵀ

Phase 3 : Résolution de Ux = y (remontée)

-5z = -20 → z = 4
y + z = 2 → y = 2 - 4 = -2
x + 2y + 3z = 14 → x = 14 - 2(-2) - 3(4) = 14 + 4 - 12 = 6

Solution finale : x = [6, -2, 4]ᵀ

Méthodes pour Réussir à l'Écrit

1. Organisation de votre copie

Pour chaque exercice :

1. Recopier l'énoncé clairement

2. Identifier la méthode à utiliser

3. Écrire les formules clés

4. Présenter les calculs en tableau

5. Vérifier la solution

2. Pour les méthodes itératives

Tableau recommandé :

| n | xₙ | f(xₙ) | |xₙ₊₁ - xₙ| |

|---|-------|--------|------------|
| 0 | ... | ... | - |
| 1 | ... | ... | ... |

3. Pour les systèmes linéaires

Présentation par matrices augmentées :

Indiquer les opérations ligne par ligne

Ex : L₂ ← L₂ - 2L₁

Réécrire la matrice après chaque transformation

4. Vérifications essentielles

Équations non linéaires :

Vérifier f(solution) ≈ 0

Vérifier les conditions de convergence

Systèmes linéaires :

Substituer la solution dans toutes les équations

Vérifier Ax = b

5. Erreurs courantes à éviter

❌ Oublier de vérifier f(a)×f(b) < 0 pour dichotomie

❌ Division par zéro dans Newton (f'(x) = 0)
❌ Pivots nuls dans Gauss
❌ Erreurs de signe dans les calculs
❌ Ne pas simplifier les fractions

6. Astuces de calcul

Utiliser des fractions plutôt que des décimales quand c'est simple

Vérifier régulièrement vos calculs intermédiaires

Si un calcul semble bizarre, revérifier l'étape précédente

Garder au moins 4 chiffres significatifs

Formulaire Récapitulatif

Méthodes pour f(x) = 0

Méthode Formule Convergence Besoin

Dichotomie c = (a+b)/2 Linéaire f(a)×f(b)<0

Point fixe xₙ₊₁ = g(xₙ) Variable |g'(x)|<1

Newton xₙ₊₁ = xₙ - f(xₙ)/f'(xₙ) Quadratique f'(x)

Sécante xₙ₊₁ = xₙ - f(xₙ)(xₙ-xₙ₋₁)/(f(xₙ)-f(xₙ₋₁)) Super-linéaire 2 points

Corde c = a - f(a)(b-a)/(f(b)-f(a)) Super-linéaire f(a)×f(b)<0

Systèmes linéaires

Gauss : Élimination → triangulaire supérieur → remontée Gauss-Jordan : Élimination totale → matrice

identité LU : A = LU, résoudre Ly = b puis Ux = y

Conseils pour le Jour J

1. Lire tout le sujet avant de commencer

2. Gérer son temps : ne pas rester bloqué sur une question

3. Montrer son raisonnement même si le calcul est faux

4. Utiliser la calculatrice pour vérifier (si autorisée)

5. Soigner la présentation : c'est important !

6. Relire sa copie : vérifier les signes, les calculs

Bon courage pour ton devoir ! 💪