IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

Algorithme d'Interpolation polynomiale

Noter ce billet
par , 15/11/2021 à 10h49 (2376 Affichages)
Etant donné un ensemble de n+1 points (obtenu, par exemple, à la suite d'une expérience), on cherche un polynôme de degré n qui passe par tous ces points.

Nom : graph_interpolation_parabolique.png
Affichages : 653
Taille : 2,0 Ko

Soit donc une série de n+1 points (xi,yi) avec 0≤i<n, et on souhaite trouver les coefficients d'un polynôme de la forme :

p(x) = anxn + an-1xn-1 + ... + a1x + a0

Ce qui revient en fait à résoudre un système de n+1 équations à n+1 inconnues.

L'objectif de ce billet est de décrire, à l'aide de tableaux, les différentes étapes permettant de simplifier progressivement notre système initial, pour finalement aboutir à sa résolution.

Sans rechercher forcément l'efficacité de l'algorithme, on montrera en particulier l'intérêt de la différence finie et de la différence divisée dans ce type de problème, et comment les utiliser pour trouver les valeurs des coefficients du polynôme, solutions du système de départ.


I. Interpolation polynomiale pour des points uniformément répartis

Soit une série de 3 points (x0,y0), (x1,y1) et (x2,y2), et on recherche un polynôme de la forme p2(x) = a2x2 + a1x + a0 qui passe par ces points.

Ceci est équivalent au système :

p2(x0) = y0
p2(x1) = y1
p2(x2) = y2


Les valeurs de xi et de yi étant connues, il s'agit de trouver les coefficients a0, a1 et a2 dans le système de 3 équations à 3 inconnues :

a2x02 + a1x0 + a0 = y0
a2x12 + a1x1 + a0 = y1
a2x22 + a1x2 + a0 = y2


Qui peut également s'écrire :

s0 = y0
s1 = y1
s2 = y2


si représente la somme des termes du membre de gauche de l'équation d'indice i.

On notera la différence entre 2 valeurs consécutives de y :

y'i = yi+1 - yi

Et la différence entre 2 sommes successives de s :

s'i = si+1 - si

Plus généralement à l'ordre k :

yi(k) = yi+1(k-1) - yi(k-1)
si(k) = si+1(k-1) - si(k-1)


Note importante : On peut faire le lien avec la différence finie, en considérant la fonction f(x)=p(x) et la relation f(xi)=yi.

Si h est l'intervalle entre 2 valeurs de x successives, alors la différence avant en xi s'écrit :

Δh[f](xi) = f(xi+h) - f(xi) = yi+1 - yi = si+1 - si

D'autre part, la différence avant à l'ordre k de f(x) = anxn + an-1xn-1 + ... + a0 , ne conserve que les coefficients de degré supérieur ou égal à k.

Les coefficients de degré inférieur à k sont éliminés.

Cette propriété va nous permettre d'éliminer progressivement les coefficients dans les sommes s, s', s'', etc..

L'idée va être en fait de prendre la différence entre deux yi et deux si consécutifs, pour transformer les séries y et s, en séries y' et s', et pour passer d'un système de n+1 équations, à un système de n équations.

On va répéter cette procédure à l'ordre n, jusqu'à obtenir une équation à une seule inconnue, et au final un système triangulaire qui peut être résolu facilement.


I-A. Interpolation linéaire entre 2 points

Nom : graph_interpolation_lineaire.png
Affichages : 96
Taille : 5,7 Ko

L’interpolation linéaire est la méthode la plus simple pour estimer la valeur prise par une fonction continue entre deux points déterminés (interpolation). Elle consiste à utiliser pour cela la fonction affine, de la forme f(x) = ax + b, passant par les deux points déterminés.

Prenons un exemple simple :

Soient 2 points M1(1,3) et M2(2,5), on souhaite déterminer les coefficients a et b du polynôme p(x) = ax + b qui passe par ces points.

Dans notre cas, on suppose qu'on connaît déjà la fonction y(x) = 2x + 1 qui passe par ces points, et l'on souhaite retrouver les coefficients a=2 et b=1 de cette fonction.

Nom : interpolation_linéaire.png
Affichages : 95
Taille : 27,6 Ko


Ordre 0 : séries y et s

On utilise au départ notre fonction f(x)=2x + 1, pour évaluer y0 et y1.

Avec la formule :

yi = f(xi) = 2xi+ 1

On obtient donc :

y0 = y(1) = 3
y1 = y(2) = 5


On trouve de la même façon, l'expression des sommes de termes s0 et s1, à l'aide de notre polynôme d'interpolation p(x) = ax + b, exprimé pour x0=1 et x1=2.

Avec la formule :

si = p(xi) = axi + b

On obtient ainsi :

s0 = p(1) = a + b
s1 = p(2) = 2a + b


Puis, en utilisant l'égalité si = yi, on a logiquement le système de 2 équations :

a + b = 3
2a + b = 5



Ordre 1 : séries y' et s'

On évalue la différence entre les 2 valeurs consécutives de y :

y'0 = y1 - y0 = 2

Et pour s :

s'0 = s1 - s0 = a


Comme si= yi, on en déduit que s'i = y'i, et que :

a = 2

Finalement, on obtient le système triangulaire :

a + b = 3
a = 2



I-B. Interpolation parabolique pour 3 points uniformément répartis

L’interpolation parabolique consiste à rechercher un polynôme de la forme p(x) = ax2 + bx + c qui passe par 3 points donnés.

Dans notre exemple, on part d'une fonction connue f(x) = 2x2 + x + 1, et on souhaite retrouver ses coefficients à partir des valeurs prises par cette fonction en 3 points réguliers.

Nom : interpolation_parabolique1.png
Affichages : 93
Taille : 35,9 Ko


Ordre 0 : séries y et s

On utilise au départ notre fonction f(x) = 2x2 + x + 1, pour évaluer y0, y1 et y2.

En se basant sur la formule :

yi = y(xi) = 2xi2 + xi + 1

On obtient donc :

y0 = y(1) = 4
y1 = y(2) = 11
y2 = y(3) = 22


On trouve de la même façon, l'expression des sommes s0, s1 et s2, à l'aide de notre polynôme d'interpolation p(x) = ax2 + bx + c, exprimé pour x0=1, x1=2 et x2=3 .

Avec la formule :

si = p(xi) = axi2 + bxi + c

On obtient ainsi :

s0 = p(1) = a + b + c
s1 = p(2) = 4a + 2b + c
s2 = p(3) = 9a + 3b + c


Puis, en utilisant l'égalité si = yi, on a logiquement le système de 3 équations :

a + b + c = 4
4a + 2b + c = 11
9a + 3b + c = 22



Ordre 1 : séries y' et s'

On transforme les séries y et s, en y' et s'. Ceci va nous permettre ensuite de simplifier les 3 équations précédentes par c, pour obtenir un système de 2 équations à 2 inconnues.

On calcule pour cela les différences entre 2 valeurs consécutives de y :

y'0 = y1 - y0 = 11 - 4 = 7
y'1 = y2 - y1 = 22 - 11 = 11

Et pour s :

s'0 = s1 - s0 = (4a + 2b + c) - (a + b + c ) = 3a + b
s'1 = s2 - s1 = (9a + 3b + c) - (4a + 2b + c ) = 5a + b


Comme si= yi, on en déduit que s'i = y'i, et que :

3a + b = 7
5a + b = 11


Ordre 2 : y'' et s''

On transforme les séries y' et s', en y'' et s''.

Ceci nous permet de simplifier les 2 équations précédentes par b, pour obtenir une équation à 1 inconnue :

2a = 4

Finalement, le système d'équations triangulaire s'écrit :

a + b + c = 4
3a + b = 7
2a = 4


I-C. Implémentation en Python

La fonction interpolation_polynomiale_v1 prend en arguments 2 listes x et y, représentant en fait la série de valeurs (xi,yi), et renvoie la liste des coefficients du polynôme recherché.

Déroulé de la fonction :

  • Transformation de la liste x, en une liste s représentant la série initiale de sommes de termes ;
  • --- Parcours des ordres k ;
  • Calcul des différences entre 2 valeurs successives de y et de s ;
  • Ajout des différences dans 2 nouvelles listes dy et ds qui représentent le système d'équations à l'ordre k ;
  • Ajout de la 1re équation du système d'ordre k au système final ;
  • --- Répétition de la procédure jusqu'à l'ordre n ;
  • Résolution du système triangulaire final « en remontant » les valeurs des variables dans les équations.


Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def interpolation_polynomiale_v1(x,y):    
    n=len(x)-1 # Nombre de valeurs de la série - 1, il correspond au degré du polynôme, exemple pour n=2 : a2x^2 + a1x + a0, où a2, a1 et a0 représentent les coefficients
    s = [] # on initialise la liste permettant d'enregistrer la série de sommes de termes
 
    for i in range(n+1): # on parcourt la liste des indices des x
        si=generer_somme(x[i],n) # on remplace x par sa valeur dans le polynôme p(x) de degré n pour obtenir la somme de termes sous la forme [4, 2, 1] -> 4a2 + 2a1 + a0
        s = s + [si] # on ajoute la somme de termes si à la liste des sommes s : Ordre 0
 
    systeme = [(s[0],y[0])] # on initialise la liste permettant d'enregistrer le système d'équations final : ajout de la 1ère équation
 
    for k in range(1,n+1): # on parcourt les ordres suivants des différences finies        
        dy = [] # on initialise la liste dy permettant d'enregistrer les deltas de y.
        ds = [] # on initialise la liste ds permettant d'enregistrer les deltas de s.
 
        for i in range(len(y)-1): # on parcourt la liste des y
            dyi = y[i+1] - y[i] # on détermine la différence entre deux y successifs
            dsi = delta_sommes(s[i],s[i+1]) # on soustrait les 2 sommes de termes, pour former une nouvelle somme de termes.
 
            dy = dy + [dyi] # on ajoute le delta d à la liste dy            
            ds = ds + [dsi] # on ajoute le delta des sommes à la liste.
 
        systeme =  systeme + [(ds[0],dy[0])] # on ajoute à la liste la 1ère équation du système d'ordre k.
 
        y = dy # on copie la liste dy dans y.
        s = ds # on copie la liste ds dans s.
 
    i= n # indice ou degré du coefficient maxi, ex. : 2 pour a2x^2 + a1x + a0
    a = [] # initialisation de la liste des coefficients remontés
 
    # on résout notre système triangulaire « en remontant » les valeurs des variables dans les équations
    for eq in reversed(systeme): # on parcourt la liste des équations dans l'ordre inverse
        ai = eval_variable(eq,a,i) # on évalue le coefficient ai
        a = a + [ai]; i=i-1 # on ajoute la variable du coefficient et sa valeur à la liste
 
    return a # on renvoie la liste des coefficients

Pour obtenir les différences successives entre 2 sommes de termes sj+1 et sj, on exécute dans une boucle la fonction delta_sommes :

Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
def delta_sommes(s1,s2,h=1):
    s=[] # on initialise la liste permettant d'enregistrer les coefficients des variables, résultat de la différences entre les sommes de termes : (4a2 + 2a1 + a0) - (a2 + a1 + a0) = 3a2 +  a1-> [3, 1]
    for v1,v2 in zip(s1[:-1],s2[:-1]): # on parcourt simultanément les 2 listes s1 et s2 jusqu'à l'avant dernier élément : le dernier est éliminé
        coef=(v2-v1)/h # on soustrait les coefficients des variables
        s = s + [coef] # on ajoute le résultat à la liste
 
    return s # on retourne la liste représentant la somme de termes : 3a2 + a1 -> [3, 1]


Exemple de test avec notre série de 3 points uniformément répartis :

Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
liste_coefficients = interpolation_polynomiale_v1([1,2,3],[4,11,22])
print(liste_coefficients)


II. Interpolation polynomiale généralisée

Pour réaliser une interpolation polynômiale de points pas nécessairement uniformément répartis, on va utiliser la différence divisée entre 2 points.

Par exemple, les différences divisées d'ordre 0, 1 et 2 sont définies comme suit :

Nom : differences_divisées_ordre0.png
Affichages : 95
Taille : 667 octets

Nom : differences_divisées_ordre1.png
Affichages : 95
Taille : 1,4 Ko

Nom : differences_divisées_ordre2.png
Affichages : 95
Taille : 2,2 Ko

On obtient ainsi le schéma récursif suivant :

Nom : differences_divisées2.png
Affichages : 93
Taille : 6,6 Ko

Les différences divisées interviennent dans les polynômes de Newton.

Contrairement aux différences finies, les différences divisées tiennent compte de la distance de 2 points par rapport à l'axe des abscisses.

Cette propriété va ainsi nous permettre de déterminer un polynôme de degré n passant par une série de points pas nécessairement uniformément répartis.

On notera la différence divisée pour 2 valeurs consécutives de y :

y'i = [yi, yi+1] = (yi+1 - yi)/(xi+1 - xi)

Ou plus généralement à l'ordre k :

yi(k) = [yi, .., yi+k] = (yi+1(k-1) - yi(k-1) )/(xi+k - xi)

Note importante : la différence divisée à l'ordre k de f(x) = anxn + an-1xn-1 + ... + a0 , ne conserve que les coefficients de degré supérieur ou égal à k.

Les coefficients de degré inférieur à k sont éliminés.

Cette propriété va nous permettre d'éliminer progressivement les coefficients dans les sommes s, s', s'', etc..

L'idée va être de prendre la différence divisée entre deux yi et deux si consécutifs, pour transformer les séries y et s, en séries y' et s', et pour passer d'un système de n+1 équations, à un système de n équations.

On va répéter cette procédure à l'ordre n, jusqu'à obtenir une équation à une seule inconnue, et au final un système triangulaire qui peut être résolu facilement.


II-A. Interpolation parabolique généralisée

On recherche à nouveau un polynôme de la forme p(x) = ax2 + bx + c qui passe par 3 points donnés pas nécessairement répartis uniformément.

Dans notre exemple, on part une nouvelle fois de la fonction f(x) = 2x2 + x + 1, et on cherche à retrouver ses coefficients à partir des valeurs prises par cette fonction en 3 points non réguliers.

Nom : interpolation_parabolique2.png
Affichages : 93
Taille : 42,4 Ko


Ordre 0 : série y et s

De la même façon que dans l'exemple précédent, on obtient la série de 3 points (xi, yi) :

(1,4), (2,11) et (4,37)

Et le système d'équations :

a + b + c = 4
4a + 2b + c = 11
16a + 4b + c = 37



Ordre 1 : séries y' et s'

On transforme les séries y et s, en y' et s'. Ceci va nous permettre ensuite de simplifier les 3 équations précédentes par c, pour obtenir un système de 2 équations à 2 inconnues.

On évalue pour cela la différence divisée pour 2 valeurs consécutives de y :

y'0 = (y1 - y0) / (x1 - x0) = (11 - 4)/(2 - 1) = 7
y'1 = (y2 - y1)/ (x2 - x1) = (37 - 11)/(4 - 2) = 13

Et pour s :

s'0 = s1 - s0 = ((4a + 2b + c) - (a + b + c))/1 = 3a + b
s'1 = s2 - s1 = ((16a + 4b + c ) - (4a + 2b + c ))/2 = 6a + b


Comme si= yi, on en déduit que s'i = y'i, et que :

3a + b = 7
6a + b = 13


Ordre 2 : y'' et s''

On transforme de la même manière les séries y'i et s'i, en y''i et s''i.

On utilise pour cela la formule des différences divisées à l'ordre 2 :

y''i = [yi, .., yi+2] = (y'i+1 - y'i)/(xi+2 - xi)

Ceci nous permet de simplifier les 2 équations précédentes par b, pour obtenir une équation à 1 inconnue :

a = 2

Le système d'équations final s'écrit donc :

a + b + c = 4
3a + b = 7
a = 2

Note importante : on remarque que le coefficient de a dans la dernière équation est égal à 1, même chose pour le coefficient de b dans la 2e équation, et de c dans la 1re.

Ceci va encore encore simplifier la résolution du système triangulaire.


II-B. Implémentation en Python

La fonction interpolation_polynomiale_v2 prend en arguments 2 listes x et y, représentant en fait la série de valeurs (xi,yi), et renvoie la liste des coefficients du polynôme recherché.

Déroulé de la fonction :

  • Transformation des 2 listes x et y, en une liste s représentant la série initiale de sommes de termes ;
  • --- Parcours des ordres k ;
  • Calcul des différences divisées entre 2 valeurs successives de y et de s ;
  • Ajout des différences dans 2 nouvelles listes dy et ds qui représentent le système d'équations à l'ordre k ;
  • Ajout de la 1re équation du système d'ordre k au système final ;
  • --- Répétition de la procédure jusqu'à l'ordre n ;
  • Résolution du système triangulaire final « en remontant » les valeurs des variables dans les équations.


Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def interpolation_polynomiale_v2(x,y):    
    n=len(x)-1 # Nombre de valeurs de la série - 1, il correspond au degré du polynôme, exemple pour n=2 : a2x^2 + a1x + a0, où a2, a1 et a0 représentent les coefficients
    s = [] # on initialise la liste permettant d'enregistrer la série de sommes de termes
 
    for i in range(n+1): # on parcourt la liste des indices des x
        si=generer_somme(x[i],n) # on remplace x par sa valeur dans le polynôme p(x) de degré n pour obtenir la somme de termes sous la forme [4, 2, 1] -> 4a2 + 2a1 + a0
        s = s + [si] # on ajoute la somme de termes si à la liste des sommes s : Ordre 0
 
    systeme = [(s[0],y[0])] # on initialise la liste permettant d'enregistrer le système d'équations final : ajout de la 1ère équation
 
    for k in range(1,n+1): # on parcourt les ordres suivants des différences divisées        
        dy = [] # on initialise la liste dy permettant d'enregistrer les différences divisées de y.
        ds = [] # on initialise la liste ds permettant d'enregistrer les différences divisées de s.
 
        for i in range(len(y)-1): # on parcourt les indices des y            
            h = (x[i+k] - x[i]) # on détermine l'écart entre la dernière et la 1ère valeur de x pour la différence divisée
 
            dyi=(y[i+1] - y[i])/h # on évalue la différence divisée à l'ordre k
            dsi = delta_sommes(s[i],s[i+1],h) # on applique la différence divisée entre les 2 sommes de termes, pour former une nouvelle somme de termes.
 
            dy = dy + [dyi] # on ajoute la valeur d de la différence divisée à la liste dy           
            ds = ds + [dsi] # on ajoute le "delta divisé" des sommes à la liste.
 
        systeme =  systeme + [(ds[0],dy[0])] # on ajoute à la liste la 1ère équation du système d'ordre k.
 
        y = dy # on copie la liste dy dans y
        s = ds # on copie la liste ds dans s
 
    i= n # indice du coefficient maxi, ex. : 2 pour a2x^2 + a1x + a0
    a = [] # initialisation de la liste des coefficients remontés
 
    # on résout notre système triangulaire « en remontant » les valeurs des variables dans les équations
    for eq in reversed(systeme): # on parcourt la liste des équations dans l'ordre inverse
        ai = eval_variable(eq,a,i) # on évalue le coefficient ai
        a = a + [ai]; i=i-1 # on ajoute la variable du coefficient et sa valeur à la liste
 
    return a # on renvoie la liste des coefficients


Exemple de test avec notre série de 3 points :

Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
liste_coefficients = interpolation_polynomiale_v2([1,2,4],[4,11,37])
print(liste_coefficients)

Module complet :

Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
def correct_value(v):
    # corrige l'erreur éventuelle dans les résultats des opérations en virgule flottante
    return round(v,5)
 
def generer_somme(x,n):
    s=[] # initialisation de la liste représentant la somme de termes
    for i in reversed(range(n+1)): # parcours des n termes du polynôme
        coef=(x**i) # évaluation du coefficient de la variable "ai"        
        s = s + [coef] # ajout du coefficient de la variable à la liste
 
    return s # on renvoie la liste représentant la somme de termes - membre gauche de l'équation : 2a2 + a1 + a0 -> [2, 1, 1]
 
def delta_sommes(s1,s2,h=1):
    s=[] # on initialise la liste permettant d'enregistrer les coefficients des variables, résultat de la différences entre les sommes de termes : (4a2 + 2a1 + a0) - (a2 + a1 + a0) = 3a2 +  a1-> [3, 1]
    for v1,v2 in zip(s1[:-1],s2[:-1]): # on parcourt simultanément les 2 listes s1 et s2 jusqu'à l'avant dernier élément : le dernier est éliminé
        coef=(v2-v1)/h # on soustrait les coefficients des variables
        s = s + [coef] # on ajoute le résultat à la liste
 
    return s # on retourne la liste représentant la somme de termes : 3a2 + a1 -> [3, 1]
 
def eval_variable(eq,a,i):
    s = eq[0] # membre de gauche de l'équation correspondant à la somme de termes 
    v = eq[1] # membre de droite de l'équation : nombre réel
    s2=0 # initialisation de la somme de termes
 
    for j in range(len(s)-1): # on parcourt les termes de la somme situés avant la variable ai
        c = a[j][1] # copie de la valeur du coefficient de degré i+j
        s2 = s2 + s[j]*c # on ajoute la nouvelle valeur à la somme de termes
 
    coef = s[len(s)-1] # copie de la valeur du coefficient de la variable ai. Toujours égal à 1 avec les différences divisées      
    v = (v-s2)/coef # calcul de la valeur de la variable ai, la division par le coefficient de la variable 'ai' n'est pas utile avec les différences divisées
 
    return ('a' + str(i), correct_value(v)) # on renvoie la variable 'ai' et la valeur du coefficient ai
 
def interpolation_polynomiale_v1(x,y):    
    n=len(x)-1 # Nombre de valeurs de la série - 1, il correspond au degré du polynôme, exemple pour n=2 : a2x^2 + a1x + a0, où a2, a1 et a0 représentent les coefficients
    s = [] # on initialise la liste permettant d'enregistrer la série de sommes de termes
 
    for i in range(n+1): # on parcourt la liste des indices des x
        si=generer_somme(x[i],n) # on remplace x par sa valeur dans le polynôme p(x) de degré n pour obtenir la somme de termes sous la forme [4, 2, 1] -> 4a2 + 2a1 + a0
        s = s + [si] # on ajoute la somme de termes si à la liste des sommes s : Ordre 0
 
    systeme = [(s[0],y[0])] # on initialise la liste permettant d'enregistrer le système d'équations final : ajout de la 1ère équation
 
    for k in range(1,n+1): # on parcourt les ordres suivants des différences finies        
        dy = [] # on initialise la liste dy permettant d'enregistrer les deltas de y.
        ds = [] # on initialise la liste ds permettant d'enregistrer les deltas de s.
 
        for i in range(len(y)-1): # on parcourt la liste des y
            dyi = y[i+1] - y[i] # on détermine la différence entre deux y successifs
            dsi = delta_sommes(s[i],s[i+1]) # on soustrait les 2 sommes de termes, pour former une nouvelle somme de termes.
 
            dy = dy + [dyi] # on ajoute le delta d à la liste dy            
            ds = ds + [dsi] # on ajoute le delta des sommes à la liste.
 
        systeme =  systeme + [(ds[0],dy[0])] # on ajoute à la liste la 1ère équation du système d'ordre k.
 
        y = dy # on copie la liste dy dans y.
        s = ds # on copie la liste ds dans s.
 
    i= n # indice ou degré du coefficient maxi, ex. : 2 pour a2x^2 + a1x + a0
    a = [] # initialisation de la liste des coefficients remontés
 
    # on résout notre système triangulaire « en remontant » les valeurs des variables dans les équations
    for eq in reversed(systeme): # on parcourt la liste des équations dans l'ordre inverse
        ai = eval_variable(eq,a,i) # on évalue le coefficient ai
        a = a + [ai]; i=i-1 # on ajoute la variable du coefficient et sa valeur à la liste
 
    return a # on renvoie la liste des coefficients
 
 
def interpolation_polynomiale_v2(x,y):    
    n=len(x)-1 # Nombre de valeurs de la série - 1, il correspond au degré du polynôme, exemple pour n=2 : a2x^2 + a1x + a0, où a2, a1 et a0 représentent les coefficients
    s = [] # on initialise la liste permettant d'enregistrer la série de sommes de termes
 
    for i in range(n+1): # on parcourt la liste des indices des x
        si=generer_somme(x[i],n) # on remplace x par sa valeur dans le polynôme p(x) de degré n pour obtenir la somme de termes sous la forme [4, 2, 1] -> 4a2 + 2a1 + a0
        s = s + [si] # on ajoute la somme de termes si à la liste des sommes s : Ordre 0
 
    systeme = [(s[0],y[0])] # on initialise la liste permettant d'enregistrer le système d'équations final : ajout de la 1ère équation
 
    for k in range(1,n+1): # on parcourt les ordres suivants des différences divisées        
        dy = [] # on initialise la liste dy permettant d'enregistrer les deltas de y.
        ds = [] # on initialise la liste ds permettant d'enregistrer les deltas de s.
 
        for i in range(len(y)-1): # on parcourt les indices des y            
            h = (x[i+k] - x[i]) # on détermine l'écart entre la dernière et la 1ère valeur de x pour la différence divisée
 
            dyi=(y[i+1] - y[i])/h # on évalue la différence divisée à l'ordre k
            dsi = delta_sommes(s[i],s[i+1],h) # on applique la différence divisée entre les 2 sommes de termes, pour former une nouvelle somme de termes.
 
            dy = dy + [dyi] # on ajoute la valeur d de la différence divisée à la liste dy           
            ds = ds + [dsi] # on ajoute le "delta divisé" des sommes à la liste.
 
        systeme =  systeme + [(ds[0],dy[0])] # on ajoute à la liste la 1ère équation du système d'ordre k.
 
        y = dy # on copie la liste dy dans y
        s = ds # on copie la liste ds dans s
 
    i= n # indice du coefficient maxi, ex. : 2 pour a2x^2 + a1x + a0
    a = [] # initialisation de la liste des coefficients remontés
 
    # on résout notre système triangulaire « en remontant » les valeurs des variables dans les équations
    for eq in reversed(systeme): # on parcourt la liste des équations dans l'ordre inverse
        ai = eval_variable(eq,a,i) # on évalue le coefficient ai
        a = a + [ai]; i=i-1 # on ajoute la variable du coefficient et sa valeur à la liste
 
    return a # on renvoie la liste des coefficients
 
liste_coefficients = interpolation_polynomiale_v2([1,2,4],[4,11,37])
print(liste_coefficients)


III. Conclusion

Après avoir posé notre système d'équations initial, nous avons compris comment le réduire progressivement à l'aide de différences finies ou de différences divisées, pour finalement obtenir les valeurs des coefficients du polynôme recherché.

Ceci nous a permis ensuite d'implémenter une fonction en Python qui évalue les coefficients d'un polynôme à partir de 2 listes de valeurs représentant la série de points (xi,yi).

Il faut préciser qu'avec ce type de méthode, l'erreur d'interpolation peut s'amplifier démesurément, dans le cas particulier où les points sont uniformément répartis, et lorsqu'on augmente le nombre de points pour un intervalle [x0 , xn] donné. On parle dans ce cas de phénomène de Runge.


Sources :

https://fr.wikipedia.org/wiki/Interp..._lin%C3%A9aire
https://fr.wikipedia.org/wiki/Interpolation_polynomiale
https://fr.wikipedia.org/wiki/Diff%C3%A9rence_finie
https://fr.wikipedia.org/wiki/Diff%C..._divis%C3%A9es
https://fr.wikipedia.org/wiki/Interpolation_newtonienne

Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog Viadeo Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog Twitter Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog Google Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog Facebook Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog Digg Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog Delicious Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog MySpace Envoyer le billet « Algorithme d'Interpolation polynomiale » dans le blog Yahoo

Mis à jour 20/11/2021 à 20h34 par User

Catégories
Programmation , Python

Commentaires