@c (Math209:ASN 2018-2019) jean-baptiste.apoung@math.u-psud.fr
%matplotlib inline
%config InlineBackend.figure_format = 'retina'
import numpy as np
import matplotlib.pyplot as plt
## METTRE LE CODE ICI
def TraquerOrdre(xn, lim = 0.0, ax=None, title=''):
'''
Fonction qui calcule l'ordre de convergence ed la suite
passée en argument
ENTREE:
xn -> tableau des éléments de la suite
lim -> limite de la suite
SORTIE:
ordre de la suite
graphique qui trace à l'echelle log
- la courbe |x_n - lim| -> |x_{n+1} - lim|
- la courbe de regression linéaire associée
'''
#COMPLETER
Tester votre algorithme en calculant, si elle converge, l'ordre de convergence de chacune des suites suivantes $$ u_n = (0.08)^n, \qquad v_n = (0.99)^n \qquad w_n = (0.8)^{2^n}$$ On calculera et affichera les 30 premiers termes de ces suites. On pourra aussi représenter graphique les droites de pente 1, 2, 3 passant par un point bien choisi.
# METTRE LE CODE ICI
- Calculer à la main les constantes asymptotiques des suites données ci-dessus
- Montrer et vérifier numériquement qu'à chaque itération
- avec la suite $v_n$ il faut 230 itérations pour gagner une décimale
- avec la suite $u_n$ on gagne une décimale à chaque itération
Pour une suite géométrique, $s_n = r^n$, nous avons $$ s_{n+p} = r^{n+p} = s_n s_p.$$ Ainsi, pour avoir $s_{n+p} \leq s_n/10$, il faut exactement $p$ tel que $r^p\geq .1$, soit
# METTRE LE CODE ICI
# nombre de termes à calculer pour diviser par 10 la suite $u_n$
# nombre de termes à calculer pour diviser par 10 la suite $v_n$
Pour la suite $w_n=r^{2^n}$, nous avons $$w_{n+1} = (r^{2^n})^2.$$ Ainsi, à chaque itération, le nombre de décimales correctes est doublé.
Pour cet exercice on fera les tests avec les fonctions suivnates
- a) $\quad f(x) = e^{x} - 1 - 0.5 x - 0.5 x^2 \quad \text{sur} \quad [-1, 1]$
- b) $\quad f(x) = e^{x} - 1 - x \quad \text{sur} \quad [-1, 1]$
- c) $\quad f(x) = e^{x} - 1 - x - 0.5 x^2 \quad \text{sur} \quad [-1, 1]$
Commencez par implémenter ces 3 fonctions.
Implémenter la méthode de Dichotomie à travers une fonction x, niter, aL, bL = Dichotomie(f, a, b, tol, iterMax)
qui prend en arguments :
- la fonction $f$ dont on cherche la racine,
- l'intervalle $[a, b]$ avec $f(a) f(b) < 0$,
- le paramètre $tol$ du test d'arrêt : on arrête si $|f(x)| < tol$
- et le nombre $iterMax$ maximum d'itérations autorisées.
et qui retourne :
- $x$ la solution approchée,
- $niter$ le nombre d'itérations réalisées,
- $aL$ (respectivement $bL$) la liste des extrémités gauches (respectivement droites) des intervalles par itération.
## METTRE LE CODE ICI
def Dichotomie(f, a, b, tol = 1e-6, iterMax = 500):
'''
Approximation du zeros d'une fonction f passée en argument
ENTREES:
f -> la fonction
a, b -> intervalle [a,b] avec f(a) f(b) < 0
tol -> paramètre du test d'arrêt : arrêt si |f(x)| < tol ou si longueur de l'intervalle < tol
iterMax -> nombre maximal uatorisé d'itérations
SORTIES:
x -> la solution approchée
niter -> nombre d'itérations effectuées
aL, bL -> liste des extrémité des intervalles générés par itérations
aL[n] est l'extrémité gauche de l'intervalle à l'itération n
bL[n] est l'extrémité droite de l'intervalle à l'itération n
'''
# METTRE LE CODE ICI
Pour le cas a), b), c) ci-dessus,
- Tracer sur un graphique la fonction $f$ et la droite $y = 0$ et conclure que f admet bien une solution.
- Calculer la solution approchée $x^*$ et la représenter sur le même graphique. On prendra les paramètres
tol = 1e-6 iterMax = 5000
- Représenter sur une autre figure l'évolution des segments $[a_n, b_n]$ en représentant les segments de droites joignant les points $(a_n, n), (b_n, n), n=0,\ldots$
- Représenter aussi la ligne brisée joignant les points $(a_n,n),(a_{n+1},n+1), n=0\ldots$ ainsi que la ligne brisée $(b_n,n),(b_{n+1},n+1), n=0\ldots$.
- Que remarquez-vous ?
## METTRE LE CODE ICI
tol = 1.e-6
iterMax = 5000
- En utilisant la fonction TraquerOrdre et le cas test a).
- Estimer l'ordre de convergence des $a_n$, $b_n$ ver la racine $x^* = 0$ de $f$.
- Estimer l'ordre de convergence des longueurs des intervalles ($|b_n - a_n|$) vers 0.
- En utilisant un résultat du cours, estimer à l'avance le nombre d'itérations nécessaires dans le cas test ci-dessus. Comparer ce nombre à celui obtenu pendant le test.
## METTRE LE CODE ICI
Pour cet exercice on fera les tests avec les fonctions suivantes
- a) $\quad f(x) = e^{x} - 1 \quad \text{sur} \quad [-1, 1]$
- b) $\quad f(x) = e^{-x} - 1 \quad \text{sur} \quad [-1, 1]$
- c) $\quad f(x) = -e^{x} + 1 \quad \text{sur} \quad [-1, 1]$
- d) $\quad f(x) = -e^{-x} + 1 \quad \text{sur} \quad [-1, 1]$
Implémenter la méthode de fausse position à travers une fonction x, niter, aL, bL = FaussePosition(f, a, b, tol, iterMax). La nature des arguments sont comme décrits dans la méthode de Dichotomie ci-dessus.
## METTRE lE CODE ICI
def FaussePosition(f, a, b, tol = 1e-6, iterMax = 5000):
'''
Approximation du zeros d'une fonction f passée en argument
ENTREES:
f -> la fonction
a, b -> intervalle [a,b] avec f(a) f(b) < 0
tol -> paramètre du test d'arrêt : arrêt si |f(x)| < tol ou si longueur de l'intervalle < tol
iterMax -> nombre maximal uatorisé d'itérations
SORTIES:
x -> la solution approchée
niter -> nombre d'itérations effectuées
aL, bL -> liste des extrémité des intervalles générés par itérations
aL[n] est l'extrémité gauche de l'intervalle à l'itération n
bL[n] est l'extrémité droite de l'intervalle à l'itération n
'''
#COMPLETER
- Pour les différents cas tests ci-dessus, reprendre l'expérience de la question 2.2.1
- Sur le même graphique représenter sur l'axe des abscisses les 4 premiers itérés $a_0, a_1, a_2$ et $b_0, b_1, b_2$ et pour pour i = 0, 1, 2
- les points $(a_i, f(a_i))$, $(b_i, f(b_i))$,
- la droite joignant les points $(a_i, f(a_i))$ et $(b_{i}, f(b_{i}))$
- Remarquer dans chaque cas, que comme dans la méthode de dichotomie, les intervalles $[a_n,b_n]$ sont emboîtés. Mais contrairement à la méthode de dichotomie l'une des extrémités de l'intervalle reste fixe: c'est-à-dire que l'une des suites $a_n$ ou $b_n$ est stationnaire.
## METTRE LE CODE ICI
tol = 1.e-6
iterMax = 5000
En remarquant que $f$ dans chacun des cas ci-dessus est soit convexe soit concave, en évaluant les signes de $f(a)$ et $f(b)$, essayer d'identifier les configurations dans la méthode de fausse position où c'est la suite des extrémités gauches qui reste constante. Faites de même pour la suite des extrêmités de droites.
En utilisant la fonction TraquerOrdre et les cas test a). Determiner l'ordre de convergence de la suite $a_n$ ou $b_n$ vers la racine $x^* = 0$ de $f$.
## METTRE LE CODE ICI
On pourra dans cette question se contenter de comparer le nombre d'itérations.
- Pour le cas test $\quad f(x) = e^{x} - 1 - x - 0.5x^2 \quad \text{sur} \quad [-0.9, 1]$
- Comparer la méthode de dichotomie et celle de la fausse Position.
- Que remarquez-vous ?
- Reprendre dans le cas $\quad f(x) = e^{x} - 1 - 0.5 x - 0.5x^2 \quad \text{sur} \quad [-0.9, 1]$
## METTRE LE CODE ICI
Dans cette exercice, on va utiliser les fonctions et les données initiales $x_0$ correspondantes
a) $\quad f(x) = e^{x} - 1 - x - 0.5x^2 \quad \text{sur} \quad [-1, 1], \quad x_0 = -0.5$
b) $\quad f(x) = x - \sin(x) \quad \text{sur} \quad [-\frac{\pi}{2}, \frac{5\pi}{2}], \quad x_0 = 1$
- c) $\quad f(x) = x + \sin(x) \quad \text{sur} \quad [-\frac{\pi}{2}, \frac{5\pi}{2}], \quad x_0 = 1$
- d) $\quad f(x) = x + \cos(x) -1 \quad \text{sur} \quad [-\frac{\pi}{2}, \frac{5\pi}{2}], \quad x_0 = 1$
- e) $\quad f(x) = x - \cos(x) +1 \quad \text{sur} \quad [-\frac{\pi}{2}, \frac{5\pi}{2}], \quad x_0 = 1$
Remarque:
- Dans a) on cherche la racine de $e^{x} - 1 - 2 x - 0.5 x^2 = 0$.
- Dans les cas tests b), c), d), e), on cherche la racine simple $x^* = 0$ de $\sin(x) = 0$.
Implémenter la méthode du point fixe à travers une fonction x, niter, xL = PointFixe(f, x0, tol, iterMax)
## METTRE LE CODE ICI
- Pour chacun des cas tests ci-dessus faire
- Tracer dans un même graphique la courbe de la fonction $f$ et celle de la droite $x \mapsto x$. Et conclure que $f$ admet un unique point fixe dans l'intervalle $[a,b]$ considéré.
- Générer la suite des itérés $x_n$ de la méthode d'itération du point fixe.
- Représenter sur le même graphique la solution numérique $x^*$ si elle existe: en dessinant un point à la position $(x^*, f(x^*))$
- Représenter la ligne brisée joignant les points $(x_n, f(x_n)), (x_{n+1}, x_{n+1}), n=0,\ldots, $
- Que remarquez-vous ?
## METTRE LE CODE ICI
tol = 1.e-6
iterMax = 5000
- Pour chacun des cas tests ci-dessus faire
- si la méthode converge,
- calculer la vitesse de convergence de la suite (On pourra utiliser la fonction TraquerOrdre ci-dessus)
- calculer la constante asymptotique de convergence de la méthode
- estimer donner le nombre d'itérations nécessaires pour gangner un chiffre exacte et vérifier que c'est le cas effectivement.
- Calculer eventuellement $f^{'}(x^*), f^{''}(x^*), f^{'''}(x^*) $ où $x^*$ est le point fixe de $f$ vers lequel la méthode semble converger et justifier le comportement de la suite générée à la lueur de ces valeurs.
## METTRE LE CODE ICI
tol = 1.e-5
iterMax = 5000
Dans cette exercice, on va utiliser les fonctions et les données initiales $x_0$ correspondantes
- a) $\quad f(x) = e^x - 1 \quad \text{sur} \quad [-1, 1], \quad x_0 = -0.5$
- b) $\quad f(x) = e^{x} - 1 - x - 0.5 x^2 \quad \text{sur} \quad [-1, 1], \quad x_0 =-0.5$
- c) $\quad f(x) = e^{x} - 1 - 0.5 x - 0.5 x^2 \quad \text{sur} \quad [-1, 1], \quad x_0 =-0.5$
Implémenter la méthode de Newton à travers une fonction x, niter, xL = Newton(f, fprime, x0, tol, iterMax)
Les paramètres en entrées et de sorties sont comme dans la méthode du point fixe, avec la seule donnée suplémentaire, la fonction fprime qui représente la dérivée de f
- On peut même montrer que son implémentation peut se faire usage de la fonction PointFixe..
def Newton(f, fprime, x0, tol, iterMax):
'''
DOCUMENTATION ICI
'''
# COMPLETER
Dans les questions qui suivent pour utiliser les cas tests ci-dessus, il faudra fournir la fonction dérivée de $f$.
Pour le cas a)
- Tracer sur un graphique la fonction $f$ et la droite $y = 0$ et conclure que f admet bien une solution
- Calculée la solution approchée $x^*$ et la représenter sur le même graphique
- Sur le même graphique représenter sur l'axe des abscisses les 4 premiers itérés $x_0, x_1, x_2, x_3$ et pour i = 0, 1, 2
- le point $(x_i, f(x_i))$,
- la tangente à la courbe de $f$ passant par le point $(x_i, f(x_i))$
- Que remarquez-vous ?
## METTRE LE CODE ICI
- En utilisant la fonction TraquerOrdre
- Estimer l'ordre de convergence de la méthode dans le cas a).
- Estimer l'ordre de convergence dans le cas b). A-t-on l'ordre 2 ici ? Pouvez-vous expliquer pourquoi?
### METTRE LE CODE ICI
tol = 1.e-6
iterMax = 100
- Vérifier à la main l'ordre de multiplicite $m$ de la racine $x^* = $ de $f$ dans le cas b)
- Reprendre l'estimation de l'ordre de convergence de la suite générée dans le cas b) l'orsqu'on remplace
- l'appel
Newton(f, fp, tol, iterMax)parNewton(lambda x: m * f(x), fp, tol, iterMax)où $m$ est l'ordre de multiplicité de la racine obtenue ci-dessus.- Pouvez-vous expliquer la correction que l'on a apprortée à la méthode de Newton ?
- Pouvez-vous fournir une formule qui estime numériquement l'ordre de multiplicité $m$ de la racine $x^*$ à l'aide de la suite générée par la méthode de Newton non modifiée ?
## METTRE LE CODE ICI
Dans cette exercice, on va utiliser les fonctions et les données initiales $x_0, x_1$ correspondantes
- a) $\quad f(x) = e^{x} - 1 \quad \text{sur} \quad [-1, 1], \quad x_0 =-0.5, \quad x_1 = 1$
- b) $\quad f(x) = e^{x} - 1 - x \quad \text{sur} \quad [-1, 1], \quad x_0 =-0.5, \quad x_1 = 1$
- c) $\quad f(x) = e^{x} - 1 - x - 0.5 x^2 \quad \text{sur} \quad [-1, 1], \quad x_0 =-0.5, \quad x_1 = 1$
- d) $\quad f(x) = e^{x} - 1 - 0.5 x - 0.5 x^2 \quad \text{sur} \quad [-1, 1], \quad x_0 =-0.5, \quad x_1 = 1$
Implémenter la méthode de Sécante à travers une fonction x, niter, xL = Secante(f, x0, x1, tol, iterMax)
Les parmètres de sorties ainsi que les paramètres d'entréess f, x0, tol, iterMax sont comme dans la méthode de Newton. Mais cette fois-ci on a besoin d'une approximation initiale supplémentaire, d'où la présence de x1
On pourra remarquer que la méthode de Sécante consiste à remplacer dans laméthode de Newton, la dérivée $ f^{'}(x_n)$ par la défférence divisée $\frac{f(x_n) - f(x_{n-1}}{x_n - x_{n-1}}$. D'où la nécessiter de disposer de deux approximations initiales.
## METTRE LE CODE ICI
def Secante(f, x0, x1, tol, iterMax, m=1):
'''
DOCUMENTATION ICI
'''
##COMPLETER
Pour le cas a)
- Tracer sur un graphique la fonction $f$ et la droite $y = 0$ et conclure que f admet bien une solution
- Calculer la solution approchée $x^*$ et la représenter sur le même graphique
- Sur le même graphique représenter sur l'axe des abscisses les 4 premiers itérés $x_0, x_1, x_2, x_3$ et pour i = 0, 1, 2
- le point $(x_i, f(x_i))$,
- la droite joignant les points $(x_i, f(x_i))$ et $(x_{i+1}, f(x_{i+1}))$
- Que remarquez-vous ?
En utilisant la fonction TraquerOrdre
- Estimer l'ordre de convergence de la méthode dans le cas a). Comparer cette valeur au nombre d'or $\frac{1+ \sqrt{5}}{2}$.
- Estimer l'ordre de convergence dans le cas b).
- A-t-on la même valeur que dans le cas a) ?
- Estimer la constante asymptotique de l'erreur $\displaystyle K_b = \lim_{n \rightarrow \infty} \frac{x^* - x_{n+1}}{x^* - x_{n}}$.
- Estimer l'ordre de convergence dans le cas c).
- A-t-on la même valeur que dans le cas a), que dans le cas b)?
- Estimer la constante asymptotique $\displaystyle K_c = \lim_{n \rightarrow \infty} \frac{x^* - x_{n+1}}{x^* - x_{n}}$.
## METTRE LA REPONSE ICI
Déterminer à la main l'ordre de multiplicite $mb$ de la racine $x^* = 0$ de $f$ dans le cas b)
- Verifier que $K_b$ trouvé ci-dessus est racine de $K^{mb} + K^{mb - 1} - 1 = 0\,$ située dans $[(\frac{1}{2})^{\frac{1}{mb}}, (\frac{1}{2})^{\frac{1}{mb-1}}]$
- Améliorer alors la valeur de $K_b$ en résolvant cette équation numériquement si nécessaire par exemple par la méthode de Newton.
Déterminer à la main l'ordre de multiplicite $mc$ de la racine $x^* = $ de $f$ dans le cas c)
- Verifier que $K_c$ trouvé ci-dessus est racine de $K^{mc} + K^{mc - 1} - 1 = 0\,$ située dans $[(\frac{1}{2})^{\frac{1}{mc}}, (\frac{1}{2})^{\frac{1}{mc-1}}]$
- Améliorer la valeur de $K_c$.
Modifier la méthode de sécante en remplaçant le calcul
- $\displaystyle x_{n+1} = x_{n} - \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})} f(x_n)$ par
- $\displaystyle x_{n+1} = x_{n} - m \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})} f(x_n)$ où $m$ est l'estimation de l'ordre de multiplicité de la racine de $f$ cherchée.
- Remarquer que cela revient à fournir une fonction x, niter, xL = Secante(f,x, x0, x1, tol, iterMax, m = 1)
C'est-à-dire à passer l'ordre de multiplicité en dernier argument et en lui affectant la valeur 1 par defaut.
Reprendre l'estimation de l'ordre de convergence de la méthode Sécante dans les cas b) et c) lorsqu'on prend en compte les ordres de multiplicité mb et mc.
Que constatez-vous ?
def ConstanteAsymptotique(xL, xe):
'''
xL[n] converge linéairement vers xe
'''
xL = xe - np.asanyarray(xL, dtype='float')
return (xL[1:])/(xL[0:-1])
def ConstanteAsymptotiqueApprox(xL):
#xL[n] converge linéairement vers xe
xL = np.asanyarray(xL, dtype='float')
return (xL[2:] - xL[1:-1])/(xL[1:-1] - xL[0:-2])