Différences divisées et instabilité des polynômes

Objectifs d'apprentissage

À la fin de cette leçon, vous serez en mesure de :

• Calculer les différences divisées pour des points non équidistants
• Appliquer la formule de Newton avec différences divisées
• Identifier et comprendre le phénomène d'instabilité (oscillations de Runge)
• Proposer des solutions au problème d'instabilité

Prérequis

• Formule de Newton-Gregory
• Notion de convergence

Les différences divisées

Motivation

La méthode de Newton-Gregory nécessite des points équidistants. En pratique, les données expérimentales ne respectent pas toujours cette contrainte. Les différences divisées généralisent les différences finies au cas de points à intervalles irréguliers.

Définition récursive

Les différences divisées se définissent par récurrence sur l'ordre (le nombre de points impliqués moins un).

Différence divisée d'ordre 0 (un seul point) :

C'est simplement la valeur de au point .

Différence divisée d'ordre 1 (deux points) :

C'est la pente de la droite passant par et . Note : contrairement aux différences finies , ici on divise par l'écart .

Différence divisée d'ordre 2 (trois points) :

C'est la « pente des pentes », divisée par l'écart total .

Différence divisée d'ordre k (formule générale) :

Formule de Newton avec différences divisées

Énoncé

Le polynôme d'interpolation de Newton s'écrit :

Plus généralement :

Cette formule est valable pour des points quelconques (équidistants ou non).

Exemple : polynôme passant par 4 points

Données

Considérons les 4 points : .

Note : les points ne sont pas équidistants (le pas varie de 1 à 2).

Table des différences divisées

Calculs détaillés

Différences d'ordre 1 :

Différences d'ordre 2 :

Différence d'ordre 3 :

Polynôme résultant

Après développement :

Vérification

Extension au degré 4

Ajout d'un point

Si on ajoute le point , on peut étendre le polynôme en calculant :

Le nouveau polynôme est :

Le phénomène d'instabilité

Observation empirique

On pourrait penser que plus on ajoute de points d'interpolation, meilleure sera l'approximation. C'est faux !

Pour certaines fonctions, augmenter le degré du polynôme peut dégrader la qualité de l'approximation, surtout près des bords de l'intervalle.

Exemple : la fonction « chapeau »

Considérons la fonction définie par :

Cette fonction forme un « chapeau » triangulaire centré en 0, avec un pic de hauteur 1.

Interpolation avec différents degrés

Visualisation interactive : fonction de Runge

L'exemple classique est la fonction de Runge sur l'intervalle . Utilisez le sélecteur pour observer comment les oscillations s'amplifient avec le degré :

Cause du phénomène

Le problème provient de la nature même des polynômes de degré élevé :

1. Ils peuvent osciller fortement entre les points d'interpolation
2. La contrainte de passer par tous les points crée des « tensions » qui se manifestent par des oscillations
3. Ces oscillations sont amplifiées près des bords de l'intervalle

Solutions au problème d'instabilité

Solution 1 : Polynômes par morceaux

Au lieu d'un seul polynôme de degré élevé, on utilise plusieurs polynômes de degré faible sur des sous-intervalles.

Pour la fonction chapeau, on peut utiliser 3 polynômes de degré 2 :

• Un pour
• Un pour
• Un pour

Solution 2 : Splines

Les splines cubiques (que nous étudierons dans les prochaines leçons) sont des polynômes par morceaux avec des conditions de raccord garantissant la continuité de la fonction et de ses dérivées.

Solution 3 : Points de Tchebychev

Au lieu de points équidistants, on peut choisir des points de Tchebychev qui minimisent l'erreur d'interpolation :

Ces points sont plus concentrés près des bords, ce qui réduit les oscillations.

Comparaison interactive : Équidistants vs Tchebychev

La visualisation suivante permet de comparer l'interpolation avec des points équidistants et des points de Tchebychev. Observez comment les oscillations sont drastiquement réduites avec les points de Tchebychev :

Recommandations pratiques

Algorithme Python

import numpy as np

def table_differences_divisees(x_points, f_values):
  """
  Construit la table des différences divisées.

  Paramètres:
      x_points : abscisses (peuvent être non équidistantes)
      f_values : ordonnées correspondantes

  Retourne:
      table : matrice triangulaire des différences divisées
  """
  n = len(x_points)
  table = [[0.0] * (n - k) for k in range(n)]

  # Ordre 0
  table[0] = list(f_values)

  # Ordres supérieurs
  for k in range(1, n):
      for i in range(n - k):
          table[k][i] = (table[k-1][i+1] - table[k-1][i]) / (x_points[i+k] - x_points[i])

  return table

def newton_differences_divisees(x_points, f_values, x):
  """
  Interpolation par la formule de Newton avec différences divisées.
  """
  n = len(x_points)
  table = table_differences_divisees(x_points, f_values)

  # Évaluation du polynôme
  result = table[0][0]
  produit = 1.0

  for k in range(1, n):
      produit *= (x - x_points[k-1])
      result += table[k][0] * produit

  return result

# Exemple : points non équidistants
x_data = np.array([0, 1, 2, 4])
f_data = np.array([1, 1, 2, 5])

print("Table des différences divisées :")
table = table_differences_divisees(x_data, f_data)
for k, row in enumerate(table):
  print(f"  Ordre {k} : {[f'{v:.4f}' for v in row]}")

# Test d'interpolation
for x in [0.5, 1.5, 3.0]:
  px = newton_differences_divisees(x_data, f_data, x)
  print(f"P_3({x}) = {px:.4f}")

# Démonstration de l'instabilité
print("\n--- Instabilité avec la fonction chapeau ---")

def chapeau(x):
  if abs(x) <= 0.2:
      return 1 - 5 * abs(x)
  return 0.0

for n in [2, 4, 6, 8]:
  x_pts = np.linspace(-1.2, 1.0, n + 1)
  f_pts = np.array([chapeau(xi) for xi in x_pts])

  # Évaluer en x = -1.0 (près du bord)
  px = newton_differences_divisees(x_pts, f_pts, -1.0)
  exact = chapeau(-1.0)
  print(f"n={n}: P({-1.0}) = {px:.4f}, exact = {exact}, erreur = {abs(px - exact):.4f}")

Résumé

• Les différences divisées généralisent les différences finies aux points non équidistants
• La formule de Newton avec différences divisées permet l'interpolation incrémentale
• Le phénomène de Runge : les polynômes de degré élevé oscillent dangereusement
• Solutions : polynômes par morceaux, splines, points de Tchebychev

Pour aller plus loin

Les prochaines leçons présenteront les splines cubiques, une solution élégante au problème d'instabilité. Ces polynômes par morceaux garantissent la continuité de la fonction et de ses deux premières dérivées.