Méthode de Newton-Gregory (différences descendantes)

Objectifs d'apprentissage

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

• Calculer les différences finies descendantes $\Delta^n f$
• Construire une table de différences
• Appliquer la formule de Newton-Gregory pour l'interpolation
• Estimer l'erreur d'interpolation à partir des différences
• Passer efficacement d'un polynôme de degré $n$ à $n+1$

Prérequis

• Polynômes de Lagrange
• Notion de pas constant (intervalles équidistants)

Motivation

Limitations de la méthode de Lagrange

La formule de Lagrange présente un inconvénient majeur : si on ajoute un nouveau point de données, il faut tout recalculer depuis le début. La méthode de Newton-Gregory résout ce problème en construisant le polynôme de manière incrémentale.

Avantages de Newton-Gregory

• Passage facile du degré $n$ au degré $n+1$
• Structure récursive permettant d'estimer l'erreur
• Particulièrement adaptée aux données à pas constant

Différences finies descendantes

Définition

Pour une fonction $f$ tabulée aux points équidistants $x_0, x_1, x_2, \ldots$ avec un pas $h$, les différences descendantes sont définies récursivement :

Différence d'ordre 0 (valeur de la fonction) :

Différence d'ordre 1 :

Différence d'ordre 2 :

Différence d'ordre n :

Construction de la table de différences

Exemple : table de sin(x)

Considérons $f(x) = \sin(x)$ avec $x_0 = 0.1$ et $h = 0.4$ :

Calcul des différences

Différences d'ordre 1 :

• $\Delta f_0 = f_1 - f_0 = 0.47943 - 0.09983 = 0.37960$
• $\Delta f_1 = f_2 - f_1 = 0.78333 - 0.47943 = 0.30390$
• $\Delta f_2 = f_3 - f_2 = 0.96356 - 0.78333 = 0.18023$
• $\Delta f_3 = f_4 - f_3 = 0.99166 - 0.96356 = 0.02810$

Différences d'ordre 2 :

• $\Delta^2 f_0 = \Delta f_1 - \Delta f_0 = 0.30390 - 0.37960 = -0.07570$
• $\Delta^2 f_1 = \Delta f_2 - \Delta f_1 = 0.18023 - 0.30390 = -0.12367$
• $\Delta^2 f_2 = \Delta f_3 - \Delta f_2 = 0.02810 - 0.18023 = -0.15213$

Et ainsi de suite pour les ordres supérieurs.

Formule de Newton-Gregory descendante

Variable réduite

Pour simplifier l'écriture, on introduit la variable réduite $s$ :

Cette variable mesure « combien de pas $h$ » on s'est déplacé depuis $x_0$ :

• Si $s = 0$, on est en $x = x_0$
• Si $s = 1$, on est en $x = x_1 = x_0 + h$
• Si $s = 0.5$, on est à mi-chemin entre $x_0$ et $x_1$

Coefficient binomial généralisé

La notation binomiale généralisée étend la formule classique aux valeurs non entières :

C'est un produit de $k$ facteurs consécutifs au numérateur, divisé par $k!$.

Exemples de calcul :

• $\binom{s}{0} = 1$ (par convention)
• $\binom{s}{1} = s$
• $\binom{s}{2} = \frac{s(s-1)}{2}$
• $\binom{s}{3} = \frac{s(s-1)(s-2)}{6}$

La formule

Le polynôme d'interpolation de Newton-Gregory est :

Ou de manière compacte :

Lecture : Le polynôme est une somme pondérée des différences $\Delta^k f_0$, où les poids sont les coefficients binomiaux évalués en $s$.

Exemple : calcul de sin(0.8)

Données

Utilisons la table de sin(x) avec $x_0 = 0.1$, $h = 0.4$.

Pour $x = 0.8$ :

Polynôme de degré 2

Avec les valeurs :

• $f_0 = 0.09983$
• $\Delta f_0 = 0.37960$
• $\Delta^2 f_0 = -0.07570$

Polynôme de degré 3

Pour améliorer la précision, ajoutons le terme de degré 3 :

Comparaison

Le passage au degré 3 a réduit l'erreur d'un facteur 10.

Estimation de l'erreur

Sans connaître la fonction exacte

Un avantage majeur de Newton-Gregory est qu'on peut estimer l'erreur sans connaître la fonction $f$.

L'erreur du polynôme de degré $n$ est approximativement :

C'est simplement le terme suivant dans le développement !

Exemple

Pour $P_2(0.8)$, l'erreur estimée est :

L'erreur réelle était 0.00290, l'estimation est donc raisonnable.

Exemple complet : estimation d'erreur avec F(x)

Reprenons l'exemple de la leçon précédente (Lagrange). Soit la fonction $F(x)$ tabulée aux points :

Les points sont équidistants avec $h = 1$ et $x_0 = 0$. Nous voulons estimer $F(1.7)$.

Étape 1 : Construire la table de différences

Calcul des différences :

• $\Delta F_0 = F_1 - F_0 = 1 - 1 = 0$
• $\Delta F_1 = F_2 - F_1 = 2 - 1 = 1$
• $\Delta F_2 = F_3 - F_2 = 5 - 2 = 3$
• $\Delta^2 F_0 = \Delta F_1 - \Delta F_0 = 1 - 0 = 1$
• $\Delta^2 F_1 = \Delta F_2 - \Delta F_1 = 3 - 1 = 2$
• $\Delta^3 F_0 = \Delta^2 F_1 - \Delta^2 F_0 = 2 - 1 = 1$

Étape 2 : Calculer la variable réduite

Étape 3 : Polynôme de degré 2 et estimation de l'erreur

Calculons d'abord $P_2(1.7)$ en utilisant les 3 premiers points :

Avec $s = 1.7$ :

• $\binom{1.7}{1} = 1.7$
• $\binom{1.7}{2} = \frac{1.7 \times 0.7}{2} = \frac{1.19}{2} = 0.595$

Estimation de l'erreur de $P_2$ par le terme suivant :

L'erreur estimée est donc environ $0.06$ (en valeur absolue).

Étape 4 : Polynôme de degré 3 et son erreur

Pour $P_3(1.7)$, on ajoute le terme de degré 3 :

Arrondissons : $P_3(1.7) \approx 1.536$.

Estimation de l'erreur de $P_3$ : Pour estimer l'erreur de $P_3$, il faudrait calculer le terme suivant :

Or, pour calculer $\Delta^4 F_0$, il faudrait un 5ème point de données (car $\Delta^4 F$ nécessite 5 valeurs). Avec seulement 4 points, nous ne pouvons pas estimer l'erreur de $P_3$.

Synthèse : Ce qu'illustre cet exemple :

• On calcule $P_2(1.7) = 1.595$ avec 3 points
• L'estimation de l'erreur de $P_2$ est $|E_2| \approx 0.06$
• En passant à $P_3$, on ajoute simplement ce terme d'erreur : $P_3(1.7) = 1.595 - 0.0595 \approx 1.536$

L'important ici est de comprendre le principe :

1. On calcule $P_n(x)$ avec $n+1$ points
2. L'erreur est estimée par $\binom{s}{n+1} \Delta^{n+1} f_0$
3. Si cette erreur est trop grande, on passe à $P_{n+1}$ en ajoutant simplement ce terme

Formule d'erreur théorique

Énoncé

Si $f$ est $(n+1)$ fois continûment dérivable, l'erreur exacte est :

où $\xi$ est dans l'intervalle contenant $x$ et les points d'interpolation.

Lien avec les différences

On peut montrer que :

Ce qui justifie l'estimation empirique $E_n \approx \binom{s}{n+1} \Delta^{n+1} f_0$.

Forme polynomiale explicite

Développement

La formule de Newton-Gregory peut être développée sous forme polynomiale standard. Pour $P_3(x)$ avec les données de sin(x) :

Cette forme est utile pour l'évaluation efficace du polynôme par la méthode de Horner.

Algorithme Python

Structure de l'implémentation

L'algorithme se décompose en trois fonctions :

1. table_differences : Construit la table triangulaire des différences $\Delta^k f_i$ en appliquant récursivement la définition $\Delta^k f_i = \Delta^{k-1} f_{i+1} - \Delta^{k-1} f_i$.

2. binomial_s : Calcule le coefficient binomial généralisé $\binom{s}{k}$ de manière incrémentale, évitant le calcul explicite des factorielles.

3. newton_gregory : Assemble le polynôme $P_n(x) = \sum_{k=0}^{n} \binom{s}{k} \Delta^k f_0$ et estime l'erreur.

import numpy as np

def table_differences(f_values):
  """
  Construit la table des différences descendantes.

  La table est une structure triangulaire :
      table[k][i] = Δ^k f_i

  Exemple pour 5 valeurs :
      table[0] = [f_0, f_1, f_2, f_3, f_4]      (5 éléments)
      table[1] = [Δf_0, Δf_1, Δf_2, Δf_3]       (4 éléments)
      table[2] = [Δ²f_0, Δ²f_1, Δ²f_2]          (3 éléments)
      table[3] = [Δ³f_0, Δ³f_1]                 (2 éléments)
      table[4] = [Δ⁴f_0]                        (1 élément)

  Paramètres:
      f_values : liste des valeurs [f_0, f_1, ..., f_n]

  Retourne:
      table : liste de listes, table[k][i] = Δ^k f_i
  """
  n = len(f_values)
  # Créer une table triangulaire : n-k éléments à l'ordre k
  table = [[0.0] * (n - k) for k in range(n)]

  # Ordre 0 : les valeurs elles-mêmes (Δ⁰f_i = f_i)
  table[0] = list(f_values)

  # Ordres supérieurs : Δ^k f_i = Δ^(k-1) f_(i+1) - Δ^(k-1) f_i
  for k in range(1, n):
      for i in range(n - k):
          table[k][i] = table[k-1][i+1] - table[k-1][i]

  return table

def binomial_s(s, k):
  """
  Calcule le coefficient binomial généralisé C(s, k) = s(s-1)...(s-k+1) / k!

  Utilise une formule incrémentale pour éviter les grands nombres :
      C(s, k) = C(s, k-1) * (s - k + 1) / k

  Paramètres:
      s : valeur réelle (variable réduite)
      k : ordre (entier >= 0)

  Retourne:
      C(s, k) : coefficient binomial (peut être négatif si s non entier)
  """
  if k == 0:
      return 1.0

  result = 1.0
  for j in range(k):
      # Multiplie par (s - j) / (j + 1) à chaque étape
      # Cela calcule s/1 * (s-1)/2 * (s-2)/3 * ... * (s-k+1)/k
      result *= (s - j) / (j + 1)

  return result

def newton_gregory(x_points, f_values, x, degre=None):
  """
  Interpolation par la formule de Newton-Gregory descendante.

  Hypothèse : les points x_points sont ÉQUIDISTANTS.

  Paramètres:
      x_points : abscisses équidistantes [x_0, x_1, ..., x_n]
      f_values : ordonnées correspondantes [f_0, f_1, ..., f_n]
      x : point où évaluer le polynôme
      degre : degré du polynôme (par défaut : le maximum permis par les
              données). Choisir un degré inférieur laisse une différence
              supplémentaire disponible pour estimer l'erreur.

  Retourne:
      (valeur, erreur_estimee) :
          - valeur : P_n(x)
          - erreur_estimee : |C(s, n+1) * Δ^(n+1) f_0| (si disponible)
  """
  n = len(x_points) - 1 if degre is None else degre
  h = x_points[1] - x_points[0]  # Pas supposé constant
  x0 = x_points[0]
  s = (x - x0) / h  # Variable réduite

  # Étape 1 : Construire la table de différences
  table = table_differences(f_values)

  # Étape 2 : Calculer P_n(x) = Σ C(s,k) * Δ^k f_0
  result = 0.0
  for k in range(n + 1):
      result += binomial_s(s, k) * table[k][0]

  # Étape 3 : Estimer l'erreur par le terme suivant (si on a assez de données)
  erreur = 0.0
  if len(table) > n + 1 and len(table[n+1]) > 0:
      erreur = abs(binomial_s(s, n + 1) * table[n + 1][0])

  return result, erreur

# === Exemple d'utilisation ===
x_data = np.array([0.1, 0.5, 0.9, 1.3, 1.7])  # Pas h = 0.4
f_data = np.array([0.09983, 0.47943, 0.78333, 0.96356, 0.99166])  # sin(x)

x_eval = 0.8

# Afficher la table de différences
table = table_differences(f_data)
print("Table de différences :")
for k, row in enumerate(table):
  print(f"  Δ^{k} f : {[f'{v:.5f}' for v in row]}")

# Interpolation avec différents degrés
for degre in range(1, 5):
  valeur, err = newton_gregory(x_data, f_data, x_eval, degre)
  exact = np.sin(x_eval)
  print(f"\nDegré {degre}: P_{degre}({x_eval}) = {valeur:.6f}")
  print(f"  Erreur réelle = {abs(exact - valeur):.6f}")
  if err > 0:
      print(f"  Erreur estimée = {err:.6f}")

Comparaison avec Lagrange

Résumé

• Les différences finies descendantes $\Delta^k f$ se calculent récursivement
• La formule de Newton-Gregory utilise ces différences avec la variable réduite $s = (x - x_0)/h$
• Avantage majeur : passer de degré $n$ à $n+1$ n'ajoute qu'un seul terme
• L'erreur peut être estimée par le terme suivant : $E_n \approx \binom{s}{n+1} \Delta^{n+1} f_0$
• La méthode nécessite des points équidistants

Pour aller plus loin

La prochaine leçon présentera les différences divisées, qui généralisent les différences finies au cas de points non équidistants. Nous étudierons également le phénomène d'instabilité des polynômes de degré élevé.