Chapitre 8 – Les Méthodes Numériques en Algorithmique

Dans le monde réel, de nombreux problèmes ne peuvent pas être résolus par des formules exactes ou des solutions analytiques. C'est là qu'interviennent les méthodes numériques, un ensemble de techniques permettant d'approximer des solutions à des problèmes mathématiques complexes grâce au calcul informatique.

Pourquoi utiliser des méthodes numériques ? Certaines fonctions, équations différentielles ou intégrales sont impossibles à résoudre exactement. Les méthodes numériques nous permettent d'obtenir des approximations suffisamment précises pour les applications pratiques, que ce soit en ingénierie, en finance, en sciences physiques ou en apprentissage automatique.

1. L'Interpolation Polynomiale

L'interpolation consiste à construire une fonction (généralement un polynôme) qui passe exactement par un ensemble de points donnés. Cette technique permet de reconstruire une courbe complète à partir d'observations discrètes.

1.1 Principe

Étant donné n points distincts (x₁, y₁), (x₂, y₂), ... (xₙ, yₙ), nous cherchons un polynôme P(x) de degré au plus n-1 tel que P(xᵢ) = yᵢ pour tout i de 1 à n.

x y (x₁, y₁) (x₂, y₂) (x₃, y₃) (x₄, y₄) Interpolation polynomiale à travers 4 points

1.2 Rappel sur les polynômes

Un polynôme de degré n est une fonction de la forme P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ, où les coefficients a₀, a₁, ..., aₙ sont des constantes et aₙ ≠ 0. Les polynômes sont particulièrement utiles pour l'interpolation car ils sont faciles à manipuler mathématiquement.

1.3 Le polynôme d'interpolation

Pour n points distincts, il existe un unique polynôme de degré au plus n-1 qui passe par tous ces points. Les méthodes les plus courantes pour trouver ce polynôme sont :

  • Interpolation de Lagrange : Construit directement le polynôme interpolateur en utilisant des polynômes de base
  • Méthode de Newton : Utilise des différences divisées pour construire le polynôme de manière récursive
  • Interpolation par splines : Utilise des polynômes de degré inférieur (souvent cubiques) entre chaque paire de points, créant une courbe lisse et évitant les oscillations

1.4 Le programme

Exemple d'implémentation de l'interpolation de Lagrange en TypeScript

// Implémentation de l'interpolation de Lagrange
function lagrangeInterpolation(
xValues: number[],
yValues: number[],
x: number
): number {
if (xValues.length !== yValues.length) {
throw new Error("Les tableaux x et y doivent avoir la même longueur");
}

let result = 0;
const n = xValues.length;

for (let i = 0; i < n; i++) {
let term = yValues[i];

for (let j = 0; j < n; j++) {
 if (i !== j) {
   term *= (x - xValues[j]) / (xValues[i] - xValues[j]);
 }
}

result += term;
}

return result;
}

// Exemple d'utilisation
const xPoints = [0, 1, 2, 4];
const yPoints = [1, 3, 2, 5];

// Calculer des points intermédiaires
const interpolatedPoints: [number, number][] = [];
for (let x = 0; x <= 4; x += 0.1) {
const y = lagrangeInterpolation(xPoints, yPoints, x);
interpolatedPoints.push([x, y]);
}

console.log(interpolatedPoints); // Points pour tracer la courbe complète

1.5 La fonction interp1d de la bibliothèque Python scipy

Dans l'écosystème Python, la bibliothèque SciPy offre une fonction interp1d qui simplifie l'interpolation :

# Exemple d'utilisation de interp1d en Python
from scipy import interpolate
import numpy as np
import matplotlib.pyplot as plt

# Points connus
x = np.array([0, 1, 2, 4])
y = np.array([1, 3, 2, 5])

# Création de la fonction d'interpolation
f = interpolate.interp1d(x, y, kind='cubic')

# Nouveaux points pour une courbe lisse
x_new = np.linspace(0, 4, 100)
y_new = f(x_new)

# Visualisation
plt.figure(figsize=(10, 6))
plt.plot(x, y, 'o', label='Points donnés')
plt.plot(x_new, y_new, '-', label='Interpolation cubique')
plt.legend()
plt.title('Interpolation avec scipy.interpolate.interp1d')
plt.grid(True)
plt.show()

2. Méthode des moindres carrés

Contrairement à l'interpolation qui passe exactement par tous les points, la méthode des moindres carrés cherche à trouver la courbe (souvent une droite) qui se rapproche au mieux d'un ensemble de points, minimisant la somme des carrés des écarts entre les points observés et la courbe.

Application essentielle : Cette méthode est fondamentale en statistiques et en analyse de données pour trouver des tendances générales dans des données bruitées, comme en régression linéaire.

2.1 Principe

Pour une régression linéaire (y = ax + b), on cherche les paramètres a et b qui minimisent la somme des carrés des résidus : E = Σ(yᵢ - (axᵢ + b))²

x y Régression linéaire par moindres carrés y = ax + b (ligne optimale) Résidus

2.2 Rappel sur le calcul des distances

La distance entre un point (x₀, y₀) et une droite d'équation y = ax + b est donnée par : d = |y₀ - (ax₀ + b)| / √(1 + a²)

Dans la méthode des moindres carrés, nous utilisons le carré de la différence verticale : (y₀ - (ax₀ + b))².

2.3 Le programme

Exemple d'implémentation de la régression linéaire en TypeScript

// Régression linéaire par la méthode des moindres carrés
function linearRegression(
xValues: number[],
yValues: number[]
): { slope: number; intercept: number } {
if (xValues.length !== yValues.length) {
throw new Error("Les tableaux x et y doivent avoir la même longueur");
}

const n = xValues.length;

// Calcul des sommes nécessaires
let sumX = 0;
let sumY = 0;
let sumXY = 0;
let sumXX = 0;

for (let i = 0; i < n; i++) {
sumX += xValues[i];
sumY += yValues[i];
sumXY += xValues[i] * yValues[i];
sumXX += xValues[i] * xValues[i];
}

// Calcul des coefficients de la droite y = ax + b
const slope = (n * sumXY - sumX * sumY) / (n * sumXX - sumX * sumX);
const intercept = (sumY - slope * sumX) / n;

return { slope, intercept };
}

// Fonction pour calculer le coefficient de détermination R²
function calculateR2(
xValues: number[],
yValues: number[],
slope: number,
intercept: number
): number {
const n = xValues.length;

// Calcul de la moyenne de y
let meanY = 0;
for (let i = 0; i < n; i++) {
meanY += yValues[i];
}
meanY /= n;

// Calcul de la somme totale des carrés et des résidus
let totalSumSquares = 0;
let residualSumSquares = 0;

for (let i = 0; i < n; i++) {
const prediction = slope * xValues[i] + intercept;
totalSumSquares += Math.pow(yValues[i] - meanY, 2);
residualSumSquares += Math.pow(yValues[i] - prediction, 2);
}

return 1 - (residualSumSquares / totalSumSquares);
}

// Exemple d'utilisation
const xData = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const yData = [2, 3, 3.5, 4.5, 5, 5.5, 6, 7.5, 7.8];

const { slope, intercept } = linearRegression(xData, yData);
const r2 = calculateR2(xData, yData, slope, intercept);

console.log(`Équation de la droite: y = ${slope.toFixed(4)}x + ${intercept.toFixed(4)}`);
console.log(`Coefficient de détermination R²: ${r2.toFixed(4)}`);

// Prédiction pour une nouvelle valeur
function predict(x: number): number {
return slope * x + intercept;
}

console.log(`Prédiction pour x = 10: ${predict(10).toFixed(2)}`);

2.4 La fonction linalg.lstsq de la bibliothèque Python numpy

NumPy fournit la fonction np.linalg.lstsq qui implémente la méthode des moindres carrés de manière efficace :

# Exemple d'utilisation de np.linalg.lstsq en Python
import numpy as np
import matplotlib.pyplot as plt

# Données d'exemple
x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9])
y = np.array([2, 3, 3.5, 4.5, 5, 5.5, 6, 7.5, 7.8])

# Préparation du système d'équations
A = np.vstack([x, np.ones(len(x))]).T

# Résolution par moindres carrés
slope, intercept = np.linalg.lstsq(A, y, rcond=None)[0]

# Affichage des résultats
print(f"Équation de la droite: y = {slope:.4f}x + {intercept:.4f}")

# Visualisation
plt.figure(figsize=(10, 6))
plt.scatter(x, y, color='blue', label='Données')
plt.plot(x, slope*x + intercept, 'r', label=f'y = {slope:.2f}x + {intercept:.2f}')
plt.legend()
plt.grid(True)
plt.title('Régression linéaire avec numpy.linalg.lstsq')
plt.xlabel('x')
plt.ylabel('y')
plt.show()

3. Recherche des solutions d'équations

Trouver les racines d'une fonction signifie déterminer les valeurs x pour lesquelles f(x) = 0. Ces points sont cruciaux dans de nombreuses applications, comme la résolution d'équations, l'optimisation, et la modélisation physique.

3.1 Principe de la méthode de Newton

La méthode de Newton-Raphson est une technique itérative pour trouver les racines d'une fonction de manière efficace. Elle utilise la dérivée de la fonction pour améliorer progressivement l'approximation.

x y a b racine xₙ xₙ₊₁ Recherche de racines : f(x) = 0

3.2 Rappel sur les dérivées

La dérivée d'une fonction f(x) au point x₀ représente la pente de la tangente à la courbe en ce point. Elle est définie par :

f'(x₀) = lim[h→0] (f(x₀+h) - f(x₀)) / h

Par exemple, si f(x) = x² + 2x + 1, alors f'(x) = 2x + 2.

3.3 Choix du point de départ pour la méthode de Newton

Le choix du point initial est crucial pour la convergence de la méthode de Newton :

  • Si le point initial est proche de la racine, la convergence est rapide (quadratique)
  • Si la dérivée est proche de zéro au point initial ou si le point est trop éloigné de la racine, la méthode peut diverger
  • En pratique, on utilise souvent une estimation grossière ou une heuristique basée sur le domaine du problème

3.4 Le programme

Exemple d'implémentation en TypeScript

// Méthode de la bissection
function bisectionMethod(
f: (x: number) => number,
a: number,
b: number,
tolerance: number = 1e-7,
maxIterations: number = 100
): number {
if (f(a) * f(b) >= 0) {
throw new Error("La fonction doit changer de signe dans l'intervalle [a, b]");
}

let left = a;
let right = b;
let iterations = 0;

while ((right - left) > tolerance && iterations < maxIterations) {
const mid = (left + right) / 2;
const fMid = f(mid);

if (Math.abs(fMid) < tolerance) {
 return mid; // Racine trouvée
}

if (f(left) * fMid < 0) {
 right = mid; // La racine est dans la partie gauche
} else {
 left = mid; // La racine est dans la partie droite
}

iterations++;
}

return (left + right) / 2; // Retourne l'approximation finale
}

// Méthode de Newton-Raphson
function newtonMethod(
f: (x: number) => number,
fPrime: (x: number) => number,
x0: number,
tolerance: number = 1e-7,
maxIterations: number = 100
): number {
let x = x0;
let iterations = 0;

while (iterations < maxIterations) {
const fx = f(x);

if (Math.abs(fx) < tolerance) {
 return x; // Racine trouvée
}

const fPrimeX = fPrime(x);

if (Math.abs(fPrimeX) < 1e-10) {
 throw new Error("Dérivée proche de zéro, la méthode de Newton peut diverger");
}

// Calcul de la nouvelle approximation
const xNew = x - fx / fPrimeX;

if (Math.abs(xNew - x) < tolerance) {
 return xNew; // Convergence atteinte
}

x = xNew;
iterations++;
}

throw new Error(`Pas de convergence après ${maxIterations} itérations`);
}

// Exemple d'utilisation
function f(x: number): number {
return Math.pow(x, 3) - 2 * x - 5; // f(x) = x³ - 2x - 5
}

function fPrime(x: number): number {
return 3 * Math.pow(x, 2) - 2; // f'(x) = 3x² - 2
}

// Bissection
const rootBisection = bisectionMethod(f, 1, 3);
console.log(`Racine par bissection: ${rootBisection.toFixed(6)}`);

// Newton
const rootNewton = newtonMethod(f, fPrime, 2);
console.log(`Racine par Newton: ${rootNewton.toFixed(6)}`);

À Retenir

  • Interpolation polynomiale : Permet de construire des courbes passant exactement par des points connus, idéale pour reconstruire des fonctions à partir d'observations discrètes.
  • Méthode des moindres carrés : Trouve la meilleure approximation (souvent linéaire) d'un ensemble de données bruitées, essentielle en statistiques et analyse de données.
  • Recherche des racines : Techniques pour trouver les valeurs x où f(x) = 0, fondamentales pour résoudre des équations et les problèmes d'optimisation.
  • Visualisation : Un outil crucial pour comprendre et communiquer le comportement des méthodes numériques et leurs résultats.
  • Applications pratiques : Les méthodes numériques sont partout - de l'ingénierie à la finance, des sciences aux applications web modernes.
  • Choix de la méthode : Dépend de la précision requise, de la nature du problème, et des contraintes de performance.

La maîtrise des méthodes numériques vous donne des outils puissants pour résoudre des problèmes qui semblent initialement insolubles, étendant considérablement votre capacité à modéliser et analyser des systèmes complexes.