Tle · Du modèle à l’autonomie

Algorithmique et Python : pas à pas

Observe un exemple expliqué, entraîne-toi avec des indices, puis résous une autre situation sur papier. Compare les étapes avant de faire le point.

Mon objectif

Retrouver mes révisions

Python : des instructions que l'on peut suivre

1. Observer

Partir de a = 2, b = 5, puis exécuter a = b et b = a. Les valeurs ont-elles été échangées ? Proposer une correction avec une variable temporaire.

Les deux noms valent 5. Les instructions se suivent : la seconde lit la nouvelle valeur de a. Pour échanger : temp = a, puis a = b, puis b = temp. On obtient 5 et 2. À réessayer : tracer les mêmes instructions avec $$a=-1,b=4$$ , sans consulter la correction.

2. S’entraîner avec aide

Que retourne la fonction suivante pour n = 5 ?

def mystere(n):
    S = 0
    for k in range(1, n + 1):
        S = S + k**2
    return S

Comparer avec l’explication

$$k$$	$$k^2$$	$$S$$ avant	$$S$$ après
1	1	0	1
2	4	1	5
3	9	5	14
4	16	14	30
5	25	30	55

Le résultat est $$55$$ . Pour un entier $n\geqslant0$ , l'invariant du cours justifie que le programme donne $\sum_{k=1}^n k^2$ . La formule connue $$n(n+1)(2n+1)/6$$ fournit un contrôle indépendant ; elle n'est pas nécessaire à l'exécution de la boucle.

3. Résoudre seul

Pour un entier $n\geqslant0$ , compléter le programme pour qu'il calcule $$n!$$ (factorielle de $$n$$ ) :

def factorielle(n):
    F = ...          # à compléter
    for k in range(..., ...):   # à compléter
        F = ...      # à compléter
    return F

Comparer avec l’explication

def factorielle(n):
    entier_naturel(n)
    F = 1
    for k in range(1, n + 1):
        F = F * k
    return F

On initialise à 1 pour un produit. Après les facteurs 1 à $$k$$ , $$F=k!$$ . Pour $$n=0$$ , la boucle est vide : elle renvoie 1, conformément à $$0!=1$$ . Initialiser à 0 annulerait tous les produits.

4. Aller plus loin

Exécuter à la main l'algorithme suivant et donner la valeur de S en sortie :

S = 0
u = 1
for k in range(5):
    S = S + u
    u = u * 2
print(S)

Comparer avec l’explication

$$k$$	$$S$$ avant	$$u$$ avant	$$S$$ après	$$u$$ après
0	0	1	1	2
1	1	2	3	4
2	3	4	7	8
3	7	8	15	16
4	15	16	31	32

On additionne $$u$$ avant de le doubler. La somme affichée est $$1+2+4+8+16=31$$ . Le dernier $$u=32$$ a été calculé mais n'a pas été additionné. Pour $$n$$ passages, la somme est $$2^n-1$$ , y compris $$n=0$$ .

Dichotomie : garder une solution entre deux bornes

1. Observer

À partir de $$[1{,}25;1{,}5]$$ , faire une étape de dichotomie pour $$x^2-2$$ . Donner l'intervalle conservé, sa largeur et son centre. Quelle borne obtient-on pour l'erreur de ce centre ?

Le nouvel intervalle est $$[1{,}375;1{,}5]$$ , de largeur $$0{,}125$$ . Son centre vaut $$1{,}4375$$ . Tout point de l'intervalle est à distance au plus $$0{,}0625$$ du centre ; c'est donc une borne pour l'erreur sur $\sqrt2$ . À réessayer : poursuivre une étape supplémentaire avec un tableau des signes.

2. S’entraîner avec aide

Utiliser la dichotomie pour résoudre $\e^x=3x$ sur $$[1,2]$$ à $10^{-8}$ près.
Combien d'étapes suffisent pour une largeur finale au plus $10^{-8}$ ?
Adapter pour trouver $\sqrt[3]{7}$ (zéro de $$x^3-7$$ sur $$[1,2]$$ ).

Comparer avec l’explication

a) La fonction $f(x)=\e^x-3x$ est continue sur $$[1,2]$$ . Ses valeurs aux bornes sont de signes opposés : $f(1)=\e-3<0$ et $f(2)=\e^2-6>0$ . Elle décroît jusqu'à $\ln3$ , puis croît strictement ; son minimum est négatif et elle reste négative sur $[1,\ln3]$ . Il y a donc exactement un zéro dans $$[1,2]$$ .

from math import exp

def equation_ex4(x):
    return exp(x) - 3*x

print(dichotomie(equation_ex4, 1, 2, 1e-8))
print(dichotomie(lambda x: x**3 - 7, 1, 2, 1e-8))

lambda x: x**3 - 7 est une écriture courte d'une fonction renvoyant $$x^3-7$$ ; on peut la remplacer par une définition def. Le premier résultat vaut environ $$1{,}51213455$$ . La largeur visée est $10^{-8}$ , donc la borne idéale d'erreur du centre est $5\times10^{-9}$ .

b) Sans rencontre d'un zéro exact, on cherche $2^{-k}\leqslant10^{-8}$ :

k\geqslant\frac{8\ln10}{\ln2}\approx26{,}58.

Il suffit de 27 étapes pour la largeur demandée. C'est un contrôle de largeur, pas un test sur la seule taille de $$f(x)$$ .

c) La fonction $$x^3-7$$ est continue et strictement croissante sur $$[1,2]$$ , avec valeurs $$-6$$ et 1. Son unique zéro est $\sqrt[3]7\approx1{,}91293118$ .

3. Résoudre seul

Un modèle de capitalisation part de $$1000$$ € avec un taux annuel supposé constant de $3\%$ , sans versement ni retrait.

Écrire la suite $$(u_n)$$ du capital après $$n$$ années.
Écrire un programme qui détermine le nombre d'années pour doubler le capital.
Vérifier en résolvant l'inégalité $1{,}03^n>2$ et choisir le premier rang entier.

Comparer avec l’explication

a) Dans le modèle théorique à taux fixe de 3% chaque année, $$u_0=1000$$ , $u_{n+1}=1{,}03u_n$ , donc $u_n=1000\times1{,}03^n$ .

b) Pour dépasser strictement 2000 :

u = 1000
n = 0
while u <= 2000:
    u = 1.03 * u
    n = n + 1
print(n)                    # 24

c) La croissance du logarithme et $\ln1{,}03>0$ donnent

\begin{aligned}1{,}03^n>2 &\iff n\ln1{,}03>\ln2,\\[.35em]&\iff n>\frac{\ln2}{\ln1{,}03}\approx23{,}45.\end{aligned}

Le premier entier est 24. La suite tend vers $+\infty$ , ce qui justifie la terminaison. Cette situation sert de modèle de suite géométrique, à taux supposé constant.

4. Aller plus loin

On définit $$u_0=1$$ et $u_{n+1}=\frac{u_n+3}{2}$ .

Écrire un programme qui affiche les $$20$$ premiers termes.
Vers quelle valeur semble converger la suite ?
Écrire un programme qui détermine le plus petit $$n$$ tel que $|u_n-3|<10^{-6}$ .

Comparer avec l’explication

a) Afficher $$u_0$$ avant la mise à jour permet de voir exactement les vingt termes $$u_0$$ à $u_{19}$ :

u = 1
for n in range(20):
    print(n, u)
    u = (u + 3) / 2

b) Les premiers termes $1,2,2{,}5,2{,}75,\ldots$ suggèrent la limite 3. Une équation de point fixe fournit un candidat, mais ne prouve pas la convergence. Posons $$v_n=u_n-3$$ . Alors

\begin{aligned}v_{n+1}&=\frac{u_n+3}{2}-3,\\[.35em]&=\frac{u_n-3}{2},\\[.35em]&=\frac12v_n.\end{aligned}

Avec $$v_0=-2$$ , la suite géométrique donne $$v_n=-2(1/2)^n$$ , donc

\begin{aligned}u_n &= 3-2(1/2)^n\\[.35em]&\to 3.\end{aligned}

u = 1
n = 0
while abs(u - 3) >= 1e-6:
    u = (u + 3) / 2
    n = n + 1
print(n)                    # 21

La terminaison suit de $|u_n-3|\to0$ . Le seuil strict demandé donne

\begin{aligned}|u_n-3|<10^{-6} &\iff 2\times2^{-n}<10^{-6},\\[.35em]&\iff 2^n>2\times10^6,\\[.35em]&\iff n>\frac{\ln(2\times10^6)}{\ln2}\approx20{,}93.\end{aligned}

Le premier entier est 21 ; contrôler les rangs 20 et 21 permet aussi de vérifier le test de boucle.

Euler : avancer avec la pente actuelle

1. Observer

Pour $$y'=-2y+6$$ , $$y(0)=1$$ , $$h=0{,}25$$ , calculer les deux premiers points d'Euler. La seconde pente doit-elle être calculée avec 1 ou avec la nouvelle valeur ?

On obtient

\begin{aligned}y_1 &= 1+0{,}25\times4\\[.35em]&= 2,\end{aligned}

puis

\begin{aligned}y_2 &= 2+0{,}25\times2\\[.35em]&= 2{,}5,\end{aligned}

aux temps $$0{,}25$$ et $$0{,}5$$ . On recalcule la pente au début de chaque pas. À réessayer : faire les mêmes étapes avec $$h=0{,}5$$ et expliquer la différence avec la solution exacte $3-2\e^{-2t}$ .

2. S’entraîner avec aide

Appliquer Euler à $$y'=y$$ , $$y(0)=1$$ avec $$h=0{,}1$$ et $$n=10$$ (donc $t\in[0,1]$ ). Comparer $y_{10}$ à $\e$ .
Même question avec $$h=0{,}01$$ et $$n=100$$ . L'approximation est-elle meilleure ?
Approfondissement. Appliquer Euler à $y'=-y+\sin(t)$ , $$y(0)=0$$ avec $$h=0{,}01$$ sur $$[0,10]$$ . Tracer la solution.

Comparer avec l’explication

a) La solution exacte de $$y'=y$$ , $$y(0)=1$$ est $\e^t$ . Euler donne

\begin{aligned}y_{k+1} &= y_k+hy_k\\[.35em]&= (1+h)y_k.\end{aligned}

Ainsi $$y_k=(1+h)^k$$ . Avec $$h=0{,}1$$ et $$k=10$$ ,

\begin{aligned}y_{10} &= 1{,}1^{10}\\[.35em]&\approx 2{,}59374246.\end{aligned}

L'erreur absolue vaut environ $$0{,}12453937$$ ; l'erreur relative est $|y_{10}-\e|/\e\approx4{,}582\%$ .

b) Avec $$h=0{,}01$$ et $$k=100$$ , le même calcul donne $1{,}01^{100}\approx2{,}70481383$ , soit une erreur relative d'environ $0{,}495\%$ . On compare au même instant final $$t=1$$ ; cette précision est ici meilleure.

c) Extension à une équation dépendant du temps :

from math import sin
import matplotlib.pyplot as plt
T, Y = euler(lambda t, y: -y + sin(t), 0, 0, 0.01, 1000)
plt.plot(T, Y)
plt.xlabel("t")
plt.ylabel("Approximation d'Euler")
plt.show()

3. Résoudre seul

On considère l'équation $$y'=-0{,}5y+2$$ , $$y(0)=10$$ .

Déterminer la solution exacte.
Appliquer Euler avec $$h=0{,}5$$ et faire les 4 premières étapes à la main.
Comparer avec les valeurs exactes en $$t=0{,}5$$ , $$1$$ , $$1{,}5$$ , $$2$$ .

Comparer avec l’explication

a) Les solutions de $$y'=-0{,}5y+2$$ sont $y(t)=C\e^{-0{,}5t}+4$ . La condition initiale donne $$C+4=10$$ , donc $$C=6$$ .

b) Le pas $$h=0{,}5$$ conduit à

\begin{aligned}y_{k+1} &= y_k+0{,}5(-0{,}5y_k+2)\\[.35em]&= 0{,}75y_k+1.\end{aligned}

En conservant les valeurs exactes à chaque étape :

\begin{aligned}y_1 &= 0{,}75\times10+1\\[.35em]&= 8{,}5,\\[.35em]y_2 &= 0{,}75\times8{,}5+1\\[.35em]&= 7{,}375,\\[.35em]y_3 &= 0{,}75\times7{,}375+1\\[.35em]&= 6{,}53125,\\[.35em]y_4 &= 0{,}75\times6{,}53125+1\\[.35em]&= 5{,}8984375.\end{aligned}

c) Comparaison avec $y(t)=4+6\e^{-0{,}5t}$ ; les colonnes « exacte » et « erreur relative » sont arrondies :

$$t$$	Euler	Solution exacte	Erreur relative
$$0{,}5$$	$$8{,}5$$	$$8{,}672805$$	$1{,}99\%$
1	$$7{,}375$$	$$7{,}639184$$	$3{,}46\%$
$$1{,}5$$	$$6{,}53125$$	$$6{,}834199$$	$4{,}43\%$
2	$$5{,}8984375$$	$$6{,}207277$$	$4{,}98\%$

L'erreur relative est $$|y_k-y(t_k)|/|y(t_k)|$$ . On n'arrondit pas les valeurs intermédiaires avant de poursuivre la récurrence.

4. Aller plus loin

On considère $y'=\cos(t)-y$ , $$y(0)=0$$ .

La solution exacte est $y(t)=\frac{1}{2}(\sin t+\cos t-\e^{-t})$ . Vérifier en dérivant.
Programmer Euler avec $$h=0{,}1$$ , $$h=0{,}01$$ , $$h=0{,}001$$ sur $$[0,10]$$ .
Tracer sur le même graphique les 3 approximations et la solution exacte.
Mesurer l'erreur maximale aux points calculés pour chaque $$h$$ . Comparer les erreurs divisées par $$h$$ ; distinguer une observation numérique d'une preuve de proportionnalité.

Comparer avec l’explication

a) Pour $y(t)=\frac12(\sin t+\cos t-\e^{-t})$ , on a

\begin{aligned}y'(t)&=\tfrac12(\cos t-\sin t+\e^{-t}),\\[.35em]\cos t-y(t) &= \tfrac12\cos t-\tfrac12\sin t+\tfrac12\e^{-t}\\[.35em]&= y'(t).\end{aligned}

De plus,

\begin{aligned}y(0) &= \tfrac12(0+1-1)\\[.35em]&= 0.\end{aligned}

Les deux conditions sont vérifiées.

b)–d) Le programme compare l'erreur aux points calculés. Les listes restent la seule collection utilisée ; le tracé facultatif nécessite Matplotlib.

from math import sin, cos, exp
import matplotlib.pyplot as plt

def exacte_ex14(t):
    return (sin(t) + cos(t) - exp(-t)) / 2

for h in [0.1, 0.01, 0.001]:
    n = round(10 / h)
    T, Y = euler(lambda t, y: cos(t) - y, 0, 0, h, n)
    erreurs = [abs(Y[k] - exacte_ex14(T[k]))
               for k in range(len(T))]
    print(h, max(erreurs))
    plt.plot(T, Y, label=f"Euler h={h}")

temps = [10*k/1000 for k in range(1001)]
plt.plot(temps, [exacte_ex14(t) for t in temps], "k--",
         label="Solution exacte")
plt.xlabel("t")
plt.legend()
plt.show()

$$h$$	Maximum observé aux nœuds	Maximum divisé par $$h$$
$$0{,}1$$	$\approx0{,}034174919$	$\approx0{,}341749$
$$0{,}01$$	$\approx0{,}003340880$	$\approx0{,}334088$
$$0{,}001$$	$\approx0{,}000333320$	$\approx0{,}333320$

Les rapports se rapprochent ici d'une constante ; les erreurs ne sont pas exactement proportionnelles à $$h$$ . Cela illustre un comportement d'ordre 1 dans ce problème régulier, sans démontrer à partir de trois mesures le théorème général ni le maximum sur tous les temps réels.

La recherche et les corrigés restent accessibles ici. JavaScript permet de mémoriser ton autoévaluation.