RÉSOLUTION DES ÉQUATIONS SCALAIRES (RÉVISIONS ET COMPLÉMENTS)

1 - Dichotomie et variantes


a) Zéro avec changement de signe

?

def Dichotomie(f, a, b, ε) :



b) Cas des intervalles ouverts

?

from numpy import inf
?

def TrouverBorneDroite(f, a, b) : if b < inf : h = (b - a) / 2 while else :
?

def TrouverBorneGauche(f, a, b) :
?

def DichotomieOuvert(f, a, b, ε) :



c) Théorème des valeurs intermédiaires, bijections réciproques




d) Zéro sans changement de signe




e) Fonctions ayant des zéros isolés

On veut maintement écrire un programme qui calcule tous les zéros d'une fonction (continue) sur un segment donné.
    Soit \(f : \left[a\,;\,b\right] \rightarrow \mathbf{R}\) une fonction continue. On dit que ses zéros sont isolés s'il existe un nombre strictement positif \(\eta\) tel qu'aucun sous-intervalle de longueur \(\eta\) ne contient plus d'un zéro de \(f\). Un contre-exemple célèbre : \(g(x) = x^2 \times \sin(1/x)\), qui est continue sur \(\mathbf{R}\) tout entier (tout du moins si on la prolonge par la valeur zéro en \(x = 0\)), mais qui possède une infinité de zéros dans n'importe quel intervalle de la forme \(\left[0\,;\,\eta\right]\).
une fonction avec beaucoup de zéros
On va écarter ces fonctions parce qu'il est évidemment exclu qu'un algorithme puisse déterminer une infinité de valeurs en temps fini.


2 - Méthode de Newton (2ème acte)

a) En général

Soit \(\mathrm{I}\) un intervalle habité, et soit \(x_0\) l'un de ses points. Si \(f : \mathrm{I} \rightarrow \mathbf{R}\) est une fonction dérivable, on peut considérer la relation de récurrence \[ x_{n + 1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}, \] qui ne définit correctement une suite \((x_{n})_{n \geq 0}\) que si à chaque étape \(x_{n}\) est dans \(\mathrm{I}\) et \(f'(x_{n})\) est différent de zéro.

Propriété (convergence de la méthode de Newton, dans les cas qui vont bien).

Supposons que la suite ci-dessus est bien définie, qu'elle converge vers une limite \(\ell \in \mathrm{I}\), et que la suite \((f'(x_{n}))_{n \geq 0}\) est bornée. Alors \(\ell\) est une solution de l'équation \(f(x) = 0\).

Preuve : si \(x_n \rightarrow \ell\) alors on a aussi \(x_{n + 1} \rightarrow \ell\), et donc en passant à la limite dans la relation de récurrence on obtient \[ \underset{n \to \infty}{\lim}\; \frac{f(x_{n})}{f'(x_{n})} = 0. \] Le dénominateur est borné et la fraction tend vers zéro, donc le numérateur tend vers zéro aussi. Mais puisque \(f\) est continue (elle est dérivable), on a \(f(x_n) \rightarrow f(\ell)\). Par unicité de la limite on conclut que \(f(\ell) = 0\). C.Q.F.D.

def Dérivée(f, x, h = 1e-5) :
    return (f(x + h) - f(x - h)) / (2 * h)


def Newton(f, x_0, \(\varepsilon\) = 1e-10) :
    x = x_0
    dx = f(x) / Dérivée(f, x)
    while abs(dx) > \(\varepsilon\) :
        x -= dx
        dx = f(x) / Dérivée(f, x)
    return x - dx


?


b) Cas des racines \(d\)-ièmes

?


c) Racines d'un polynôme

?


3 - Systèmes d'équations (pas forcément linéaires)


Plus généralement considérons une fonction \(\mathrm{F} : \mathbf{R}^d \rightarrow \mathbf{R}^d\), écrivons \[ \mathrm{F}(x_0,\,x_1,\,\dots,\,x_{d-1}) = \begin{pmatrix} f_0(x_0,\,x_1,\,\dots,\,x_{d-1}) \\ f_1(x_0,\,x_1,\,\dots,\,x_{d-1}) \\ \vdots \\ f_{d-1}(x_0,\,x_1,\,\dots,\,x_{d-1}) \end{pmatrix} \in \mathrm{R}^d, \] et supposons que toutes les fonctions-composantes \(f_i : \mathrm{R}^d \rightarrow \mathrm{R}\) admettent des dérivées partielles par rapport à chaque variable. Pour chaque \(\mathrm{X} = (x_0,\,x_1,\,\dots,\,x_{d-1}) \in \mathbf{R}^d\) on pose \[ \mathrm{F}'(\mathrm{X}) = \left( \partial_j f_i(\mathrm{X}) \right)_{0 \leq i, j \leq d - 1} \in \mathscr{M}_{d}(\mathrm{R}), \] où \(\partial_j f_i\) désigne la dérivée par rapport à la \(j\)-ième variable. Admettons que cette matrice joue un rôle analogue à la dérivée, prenons n'importe quel vecteur de départ \(\mathrm{X}_0 \in \mathbf{R}^d\) et écrivons ce que devient la formule d'itération de Newton (au lieu de diviser par \(f'(x)\) on multiplie par l'inverse de \(\mathrm{F}'(\mathrm{X})\)) : on obtient \[ \mathrm{X}_{n + 1} = \mathrm{X}_n - \mathrm{F}'(\mathrm{X_n})^{-1} \times \mathrm{F}(\mathrm{X}_n). \] On programmera tout ceci dans un instant, mais observons d'abord un exemple pour se convaincre que ça marche. Soit à résoudre le système \[ \left\{ \begin{array}{rcl} x^2 y + e^y &=& 3 \\ ye^x + x &=& 2. \end{array} \right. \] On préfère quand c'est égal à zéro, donc on commence par ré-écrire tout ça ainsi \[ \left\{ \begin{array}{rcl} x^2 y + e^y - 3 &=& 0 \\ e^x y + x - 2 &=& 0, \end{array} \right. \] ce qui invite à considérer la fonction \[ \mathrm{F}(x, y) = \begin{pmatrix} x^2 y + e^y - 3 \\ e^x y + x - 2 \end{pmatrix}. \]
def F(X) :
    x = X[0, 0] ; y = X[1, 0]
    f0 = x ** 2 * y + exp(y) - 3
    f1 = exp(x) * y + x - 2
    return matrix([[f0], [f1]])


Juste pour être sûr qu'on a compris, calculons sa « dérivée » (mais le programme le fera pour nous tout à l'heure) : c'est \[ \mathrm{F}'(x, y) = \begin{pmatrix} 2xy & x^2 + e^y \\ e^x y + 1 & e^x \end{pmatrix}. \]