Etude de différents algorithmes de résolution

Vous allez dans cette partie implanter différents algorithmes de résolution. Ces algorithmes sont des algorithmes itératifs qu'il convient d'arrêter lorsque l'on atteint un critère. Le critère d'arrêt retenu sera\( |x_{n}-x_{n-1}| < 1e-10\) sauf indication contraire.

Pour chacun des algorithmes, on observera l'ordre de convergence \(\textrm{ordre}(i) = \dfrac{\log(|x_{i}-x_{\infty}|)}{\log(|x_{i-1}-x_{\infty}|)}.\) Plus l'ordre est élevé, plus l'algorithme converge rapidement vers la solution.

Méthode par dichotomie

La méthode par dichotomie est d'approcher la solution par réduction successive de l'intervalle de recherche.

Cette méthode est adaptée pour les fonctions monotones dont on recherche le zéro.

Méthode :

choix de l'intervalle de départ\( [a, b]\), tant que \(|b-a|> \varepsilon \), \(c=\dfrac{a+b}{2}\), \(\textrm{sign}(f(c))\) identique à \(\textrm{sign}(f(a))\), alors \(a=c\)

sinon \(b=c\)

Question

Implanter cet algorithme dans une fonction \(\texttt{dichotomie(f, a, b)}\) et vérifier que le résultat renvoyé correspond à celui attendu, on fixera \(\texttt{epsilon=1e-10}\) .

Solution

1
def dichotomie(f,a,b):
2
    while (abs(a-b)>1e-10 ):
3
        if f((a+b)/2)*f(a) < 0 : #donc signe différent
4
            b = (a+b) / 2
5
        else:
6
            a = (a+b) / 2
7
    return (a+b)/2

Question

Modifier votre algorithme pour afficher le nombre d'itérations, les solutions successives obtenues à chaque itération (on supposera que la solution à chaque itération est \(\dfrac{a+b}{2}\) ainsi que la solution quand la convergence est atteinte.

Solution

1
def dichotomie(f,a,b):
2
    niter=0
3
    xv=[(a+b)/2]
4
    while (abs(a-b)>1e-10 and niter < 500):
5
        if f((a+b)/2)*f(a) < 0 : #donc signe différent
6
            b = (a+b) / 2
7
        else:
8
            a = (a+b) / 2
9
        niter+=1
10
        xv.append((a+b)/2)
11
    return (a+b)/2,niter,xv

Question

Écrire une fonction \(\texttt{ordre(liste_x)}\) qui renvoie la liste contenant l'ordre de convergence en fonction des itérations. En déduire l'ordre de convergence de la méthode par dichotomie.

Indice

On utilisera \(\texttt{np.log(abs(x[i]-x[i-1]))}\)

Solution

1
def ordre(x):
2
    ord = []
3
    for i in range(2,len(x)):
4
        ord.append(np.log(abs(x[i]-x[i-1]))/np.log(abs(x[i-1]-x[i-2])))
5
    return ord

La dernière valeur donne l'ordre à convergence soit environ 2 ! ! 

Méthode de Newton

Le principe de la méthode de Newton est de chercher le zéro d'une fonction en prenant comme nouvelle approximation l'abscisse du point d'intersection de la tangente à la fonction au point d'approximation précédente.

Quand cette dérivée n'est pas connue, on peut déterminer une approximation numérique par : \(f'(x_k)=\dfrac{f(x_k+h)-f(x_k)}{h}\).

Ici, on peut calculer cette dérivée : \(\lambda_1'(\alpha)=\dfrac{- a L\sin(\alpha-130)-b L\cos(\alpha-130)}{\sqrt{\left(L\cos(\alpha-130) +a\right)^2+\left(L\sin(\alpha-130)-b\right)^2}}\)

Question

Calculer la dérivé de la fonction : \(\lambda\) des deux manières, on écrira une fonction \(\texttt{fpexact(alpha)}\) puis une fonction \(\texttt{fpnum(f,alpha)}\).

Solution

1
def fpexact(alpha):
2
    return ((a*L*np.sin(-130*np.pi/180+alpha)+b*L*np.cos(-130*np.pi/180+alpha))/lambda1(alpha))
1
def fpnum(f,alpha,pas):
2
    return (f(alpha+pas)-f(alpha)) / pas

Question

Écrire une fonction \(\texttt{newton(f, xini)}\) qui affiche la solution, le nombre d'itérations et qui renvoie la liste des approximations \(x_k\) successives en prenant la dérivée exacte, on fixera \(\texttt{epsilon=1e-10}\).

Solution

1
#Algo Newton exacte
2
def newton(f,fp,xini):
3
    xv=[]
4
    x = xini
5
    niter = 0
6
    while(abs(f(x))> 1e-10):
7
        fp1 = fpexact(x)
8
        x = x - f(x) / fp1
9
        niter+=1
10
        xv.append(x)
11
    return x,niter,xv
12
Question
Écrire une fonction \(\texttt{newton2(f, xini)}\) qui affiche la solution, le nombre d'itérations et qui renvoie la liste des approximations  \(x_k\) successives en prenant la dérivée approchée avec \(h=0.1\), on fixera  \(\texttt{epsilon=1e-10}\).
Solution
1
def newton2(f,xini):
2
    xv=[]
3
    x = xini
4
    h = .1
5
    niter = 0
6
    while(abs(f(x))> 1e-10 and niter < 500):
7
        xo = x
8
        fp1 = fpnum(f,x,h)
9
        x = x - f(x) / fp1
10
        niter+=1
11
        xv.append(x)
12
    return x,niter,xv
Question
Comparer la convergence de cet algorithme pour différentes valeurs de \(h\) par pas de 10 (\(10^{-2}, 10^{-3}, 10^{-4}...)\) et déterminer une valeur qui semble optimale.
Question
Déterminer l'évolution de l'ordre de convergence en fonction des itérations et en déduire l'ordre de convergence pour différentes valeurs de \(h\) . Comparer à la valeur théorique qui est de 2.