Discussion :

[Lesquestions]

Bonjour,

Je cherche à faire un programme Python résolvant cette récurrence :



Voici ce que j'ai fait :

Code :

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
import numpy as np
import matplotlib.pyplot as plt
 
a=1
b=50
n=1000
 
def P_0(x) :
  n=0
  return i,1
 
def P_1(x) : 
  n=1
  return i,x
 
def P_n(n,x) : 
 
  f=(2*n-1)/(n)*x*P_n(n-1,x)-P_n(n-2,x)*(n-1)/(n)
  return n, f
 
x = np.linspace(a, b, n+1)
y=P_n(30,x)
 
plt.plot(x, y)
 
plt.show()

Il s'agit d'un des premiers programme que je fais en python, soyez indulgent

A vous lire

[User]

Bonjour,

Si tu souhaite évaluer le polynôme en fonction de n et x, comme tu as une relation de récurrence, tu peux créer une fonction récursive à partir de cette relation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def P_n(n,x) :
 
    if n==0: # si n=0, renvoie 1 : sortie
        return 1
    else:
        if n==1: # si n=1, renvoie x : sortie
            return x
        else: # sinon : appels récursifs :
            return ((2*n-1)/n)*x*P_n(n-1,x) - P_n(n-2,x)*(n-1)/n

[CosmoKnacki]

À ta place j'éviterais de créer une fonction récursive, car si ton intention est de calculer la valeur au rang 30, cela nécessitera pas moins de 2692537 appels de ta fonction. À mon avis mieux vaut opter pour une boucle allant jusqu'à n dans laquelle tu mets à jour les deux termes précédents, la complexité sera moins grande.

[User]

Ah oui en effet je n'avais pas vu le degré n=30.

Dans ce cas oui il vaut mieux utiliser une boucle, c'est peut-être moins lisible pour un débutant mais nettement plus rapide à l'exécution.

Un peu comme pour le calcul du nième terme de la suite de Fibonacci à l'aide d'une boucle, mais en un peu plus compliqué

[User]

Bonjour,

J'ai ajouté les fonctions dans ton code pour afficher le graphique si tu es toujours dessus. Il reste peut-être quelques petites erreurs.

On peut donc optimiser le code en utilisant la programmation dynamique : on mémorise les résultats intermédiaires pour éviter de les calculer plusieurs fois :

La méthode ascendante (proposée par CosmoKnacki) :

Code :

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
import numpy as np
import matplotlib.pyplot as plt
 
 
def P_leg(n,x):
 
    if n==0:
        return 1
 
    # initialisation des 2 variables
    p_prec = 1
    p_cour = x
 
    # parcours des i
    for i in range(2,n+1):
        # relation de récurrence
        pi = ((2*i-1)/i)*x*p_cour - p_prec*(i-1)/i
        p_prec = p_cour; p_cour = pi
 
    return p_cour
 
n=3
 
a=-1
b=1
 
x = np.linspace(a, b, 1000)
 
y = [P_leg(n,xi) for xi in x]
 
plt.plot(x, y, label="P_leg(n,x)")
 
plt.legend()
 
plt.show()

Habituellement on mémorise les résultats intermédiaires dans un tableau.


La méthode descendante :

Code :

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
import numpy as np
import matplotlib.pyplot as plt
 
def P(n,x) :
 
    if n not in p_dict:
        # appels récursifs :
        p_dict[n] = ((2*n-1)/n)*x*P(n-1,x) - P(n-2,x)*(n-1)/n
 
    return p_dict[n]
 
def P_leg(n,x):
    global p_dict
 
    if n==0:
        return 1
 
    # initialisation du dico : 2 première valeurs 1 et x
    p_dict = {0: 1, 1: x}
 
    # appel de la fonction récursive Pn(n,x) et renvoi de son résultat
    return P(n,x)
 
n=3
 
a=-1
b=1
 
x = np.linspace(a, b, 1000)
 
y = [P_leg(n,xi) for xi in x]
 
plt.plot(x, y, label="P_leg(n,x)")
 
plt.legend()
 
plt.show()

On utilise dans ce cas un dictionnaire pour mémoriser les valeurs déjà calculées.

Tout est expliqué en détail sur cette page Wikipedia :

https://fr.wikipedia.org/wiki/Programmation_dynamique

Il y a aussi plein d'exemples sur internet il suffit de chercher un peu.

Voilà si ça peut être utile