| 1 |
francois |
948 |
|
| 2 |
|
|
\begin{encadre}{Objectif du chapitre} |
| 3 |
|
|
Ce chapitre met l'emphase sur le passage d'un problème d'ingénierie vers une mise en équation puis vers une méthode de résolution de cette équation. |
| 4 |
|
|
Des techniques de solution des équations non linéaires à une variable sont ensuite présentées. Ceci concerne tous problèmes nécessitants la résolution d'une équation sous la forme $f(x)=0$ quelque soit la forme de $f$. |
| 5 |
|
|
\end{encadre} |
| 6 |
|
|
\\[1cm] |
| 7 |
|
|
\begin{encadre}{Connaissances antérieures nécessaires} |
| 8 |
|
|
\begin{itemize} |
| 9 |
|
|
\item les mathématiques : résolution d'équation à une variable, calcul différentiel. |
| 10 |
|
|
\item programmation de base en Basic ou C : les types, les opérations élémentaires et la structuration de programme en mode console |
| 11 |
|
|
\end{itemize} |
| 12 |
|
|
|
| 13 |
|
|
\end{encadre} |
| 14 |
|
|
|
| 15 |
|
|
|
| 16 |
|
|
|
| 17 |
|
|
|
| 18 |
francois |
939 |
\section[Construction d'un problème d'ingénierie]{Construction d'un problème d'ingénierie amenant à une équation non linéaire} |
| 19 |
|
|
Dans ce paragraphe, nous allons montrer la méthodologie qui permet de passer d'un problème d'ingénierie en un problème numérique. L'exemple est quelque peu complexe pour montrer que le passage n'est pas toujours direct. |
| 20 |
|
|
\\ |
| 21 |
|
|
Le problème : Déformation par vibration d'une poutre de longueur $L$ encastrée aux deux bouts. |
| 22 |
|
|
\\ |
| 23 |
|
|
Le déplacement de la poutre $u(x,t)$ est solution de |
| 24 |
|
|
\begin{eqnarray*} |
| 25 |
|
|
\frac{\partial^2u}{\partial t^2}+C^2\frac{\partial^4 u}{\partial x^4}=0 |
| 26 |
|
|
\end{eqnarray*} |
| 27 |
|
|
avec $C$ fonction des caractéristiques élastiques de la poutre. |
| 28 |
|
|
\\ |
| 29 |
francois |
948 |
et pour conditions aux limites |
| 30 |
francois |
939 |
\begin{eqnarray*} |
| 31 |
|
|
u(0,t)=u(L,t)=0\\ |
| 32 |
|
|
\frac{\partial u(0,t)}{\partial x}=\frac{\partial u(L,t)}{\partial x}=0 |
| 33 |
|
|
\end{eqnarray*} |
| 34 |
|
|
On a donc une équation partielle d'ordre 4 à résoudre. |
| 35 |
|
|
\\Une résolution par séparation des variables est utilisée : |
| 36 |
|
|
\\ on pose |
| 37 |
|
|
\begin{eqnarray*} |
| 38 |
|
|
u(x,t)&=&F(x)G(t)\\ |
| 39 |
|
|
F(0)&=&F(L)=F'(0)=F'(L)=0\\ |
| 40 |
|
|
\frac{\partial u}{\partial x}&=&F'(x)G(t)\\ |
| 41 |
|
|
\frac{\partial^2 u}{\partial x^2}&=&F''(x)G(t)\\ |
| 42 |
|
|
\frac{\partial^3 u}{\partial x^3}&=&F'''(x)G(t)\\ |
| 43 |
|
|
\frac{\partial^4 u}{\partial x^4}&=&F''''(x)G(t)\\ |
| 44 |
|
|
\frac{\partial u}{\partial t}&=&F(x)G'(t)\\ |
| 45 |
|
|
\frac{\partial^2 u}{\partial t^2}&=&F(x)G''(t)\\ |
| 46 |
|
|
\end{eqnarray*} |
| 47 |
|
|
et l'équation de départ devient |
| 48 |
|
|
\begin{eqnarray*} |
| 49 |
|
|
G''(t)F(x)+C^2F''''(x)G(t)&=&0\\ |
| 50 |
|
|
\frac{G''(t)F(x)+C^2F''''(x)G(t)}{F(x)G(t)}&=&0\\ |
| 51 |
|
|
\frac{G''(t)}{G(t)}+C^2\frac{F''''(x)}{F(x)}&=&0\\ |
| 52 |
|
|
-\frac{G''(t)}{C^2G(t)}&=&\frac{F''''(x)}{F(x)}\\ |
| 53 |
|
|
\end{eqnarray*} |
| 54 |
|
|
Cette dernière équation est le rapport de deux fonctions de deux variables indépendantes différentes. Le rapport est donc constant. |
| 55 |
|
|
\begin{eqnarray*} |
| 56 |
|
|
-\frac{G''(t)}{C^2G(t)}&=&\frac{F''''(x)}{F(x)}=\beta^4\\ |
| 57 |
|
|
\end{eqnarray*} |
| 58 |
|
|
On aboutit à un système de deux équations différentielles |
| 59 |
|
|
\begin{eqnarray*} |
| 60 |
|
|
\left \{ |
| 61 |
|
|
\begin{array}{l} |
| 62 |
|
|
F''''(x)-\beta^4F(x)=0\\ |
| 63 |
|
|
G''(t)+C^2\beta^4G(t)=0\\ |
| 64 |
|
|
\end{array} |
| 65 |
|
|
\right. |
| 66 |
|
|
\end{eqnarray*} |
| 67 |
|
|
Étude de la première équation différentielle |
| 68 |
|
|
\begin{eqnarray*} |
| 69 |
|
|
F''''(x)-\beta^4F(x)=0\\ |
| 70 |
|
|
\end{eqnarray*} |
| 71 |
francois |
948 |
Une solution s?écrit sous la forme |
| 72 |
francois |
939 |
\begin{eqnarray*} |
| 73 |
|
|
F(x)&=&A\cos\beta x+B\sin\beta x+C\cosh\beta x+D\sinh\beta x\\ |
| 74 |
|
|
F'(x)&=&\beta(-A\sin\beta x+B\cos\beta x+C\sinh\beta x+D\cosh\beta x)\\ |
| 75 |
|
|
\end{eqnarray*} |
| 76 |
|
|
On applique les conditions aux limites : |
| 77 |
|
|
\begin{eqnarray*} |
| 78 |
|
|
F(0)&=&0=A+C\quad soit \quad A=-C\\ |
| 79 |
|
|
F'(0)&=&0=B(B+D)\quad soit \quad B=-D\\ |
| 80 |
|
|
F(L)&=&A(\cos\beta L-\cosh\beta L)+B(\sin\beta L-\sinh\beta L)=0\\ |
| 81 |
|
|
F'(L)&=&\beta(A(-\sin\beta L-\sinh\beta L)+B(\cos\beta L-\cosh\beta L))=0 |
| 82 |
|
|
\end{eqnarray*} |
| 83 |
|
|
Il reste donc deux équations à deux inconnues. Si ces deux équations sont indépendantes on a une solution non satisfaisante $A=B=C=D=0$. |
| 84 |
|
|
\\ |
| 85 |
|
|
Les deux équations sont donc dépendantes et le déterminent du système est nul: |
| 86 |
|
|
\begin{eqnarray*} |
| 87 |
|
|
\left | |
| 88 |
|
|
\begin{array}{ll} |
| 89 |
|
|
\cos\beta L-\cosh\beta L & \sin\beta L-\sinh\beta L\\ |
| 90 |
|
|
\beta(-\sin\beta L-\sinh\beta L) & \beta(\cos\beta L-\cosh\beta L)\\ |
| 91 |
|
|
\end{array} |
| 92 |
|
|
\right | &=&0\\ |
| 93 |
|
|
\beta(\cos\beta L-\cosh\beta L)^2+\beta(\sin\beta L+\sinh\beta L)(\sin\beta L-\sinh\beta L)&=&0\\ |
| 94 |
|
|
2\beta(1-\cos\beta L\cosh\beta L)&=&0 |
| 95 |
|
|
\end{eqnarray*} |
| 96 |
|
|
Il reste une équation non linéaire $1-\cos\beta L\cosh\beta L=0$ d'inconnue $\beta$ à trouver pour trouver $F(x)$. |
| 97 |
|
|
La solution du problème revient à chercher les zéros d'une fonction non linéaire. |
| 98 |
|
|
\\ |
| 99 |
|
|
Beaucoup d'autres problèmes d'ingénierie nécessite la résolution de fonction non linéaire. Dans le reste de ce chapitre nous allons montrer trois méthodes différentes pour solutionner numériquement ces équations. |
| 100 |
|
|
|
| 101 |
|
|
\section{Méthode de la bissection} |
| 102 |
|
|
\subsection{Description de la méthode} |
| 103 |
|
|
L'idée de la méthode est de dire qu'autour d'un zéro d'une fonction d'équation $f(x)=0$, $f$ change de signe en général. |
| 104 |
|
|
\\ |
| 105 |
|
|
Soit $[x_1,x_2]$ tel que $f(x_1)f(x_2)<0$ on pose $x_m=\frac{x_1+x_2}{2}$. L'intervalle $[x_1,x_2]$ est divisé en $[x_1,x_m]$ et $[x_m,x_2]$. La racine se trouve dans l'un où l'autre des deux intervalles. |
| 106 |
|
|
On recommence le processus jusqu'à obtenir un petit intervalle. |
| 107 |
|
|
|
| 108 |
|
|
\begin{algorithm}[H] |
| 109 |
|
|
\SetAlgoLined |
| 110 |
|
|
%\LinesNumbered |
| 111 |
|
|
\KwData{\\$\epsilon_r$ la précision relative de la solution souhaitée.\\ $N$ un nombre maximal d'itération.\\$f(x)$ une fonction.\\$[x_1,x_2]$ un intervalle pour lequel $f$ possède un zéro} |
| 112 |
|
|
\KwResult{Racine $r$ de la fonction $f(x)$} |
| 113 |
|
|
$compteur=0$\\ |
| 114 |
|
|
\Repeat{$\frac{|x_2-x_1|}{2|x_m|}<\epsilon_r$} |
| 115 |
|
|
{ |
| 116 |
|
|
$x_m=\frac{x_1+x_2}{2}$\\ |
| 117 |
|
|
\eIf{$f(x_1)f(x_m)<0$}{$x_2=x_m$}{\If{$f(x_m)f(x_2)<0$}{$x_1=x_m$}} |
| 118 |
|
|
compteur=compteur+1\\ |
| 119 |
|
|
\If{$compteur>N$}{Arrêt non convergence} |
| 120 |
|
|
} |
| 121 |
|
|
$r=x_m$ est la racine de $f(x)$ |
| 122 |
|
|
\caption{Algorithme de la méthode de la bissection} |
| 123 |
|
|
\end{algorithm} |
| 124 |
|
|
|
| 125 |
|
|
\subsection{Étude de la précision et de la convergence} |
| 126 |
|
|
La méthode de la bissection consiste à diviser un intervalle en deux à chaque itération. A l'itération $n$ la taille de l'intervalle est de $\frac{x_2-x_1}{2^n}$. L'erreur sur la solution à l'itération $n$ peut être déterminée à l'avance : |
| 127 |
|
|
\begin{eqnarray*} |
| 128 |
|
|
\Delta r=\frac{x_2-x_1}{2^n} |
| 129 |
|
|
\end{eqnarray*} |
| 130 |
|
|
On en déduit le nombre d'itération pour atteindre la précision souhaitée $\epsilon$ : |
| 131 |
|
|
\begin{eqnarray*} |
| 132 |
|
|
\epsilon&=&\frac{x_2-x_1}{2^n}\\ |
| 133 |
|
|
2^n&=&\frac{x_2-x_1}{\epsilon}\\ |
| 134 |
|
|
n\ln 2&=&\ln \frac{x_2-x_1}{\epsilon}\\ |
| 135 |
|
|
Soit\quad n&>&\frac{\ln \frac{x_2-x_1}{\epsilon}}{\ln 2} |
| 136 |
|
|
\end{eqnarray*} |
| 137 |
|
|
Le méthode de bissection présente la particularité d'avoir une convergence lente mais sûre à partir du moment ou il y a un changement de signe dans l'intervalle de départ. |
| 138 |
|
|
|
| 139 |
|
|
\subsection{Exemple} |
| 140 |
|
|
On désire calculé la racine de $f(x)=x^2-3=0$ par la méthode de la bissection. |
| 141 |
|
|
\\ |
| 142 |
|
|
On note que $f(1)=-2$ et que $f(2)=1$. Dans $[1,2]$ il y a un changement de signe donc il y a une racine. |
| 143 |
|
|
\\Calcul de la racine : \\ |
| 144 |
|
|
\footnotesize |
| 145 |
|
|
\begin{tabular}{|r|r|r|r|r|r|r|} |
| 146 |
|
|
\hline |
| 147 |
|
|
$x_1$ & $x_2$ & $x_m$ & $f(x_1)$ & $f(x_2)$ & $f(x_m)$ & $\Delta r$ \\ |
| 148 |
|
|
\hline |
| 149 |
|
|
$1$ & $2$ & $1.5$ & $-2$ & $1$ & $-0.75$ & $1$\\ |
| 150 |
|
|
$1,5$& $2$ &$1,7$5 &$-0,75$ &$1$ &$0,0625$& $0,5$ \\ |
| 151 |
|
|
$1,5$& $1,75$ &$1,625$ &$-0,75$ &$0,0625$ &$-0,359375$ &$0,25$ \\ |
| 152 |
|
|
$1,625$ &$1,75$ &$1,6875$ &$-0,359375$ &$0,0625$& $-0,15234375$ &$0,125$ \\ |
| 153 |
|
|
$1,6875$ &$1,75$ &$1,71875$ &$-0,15234375$ &$0,0625$ &$-0,0458984375$ &$0,0625 $\\ |
| 154 |
|
|
$1,71875$ &$1,75$ &$1,734375$ &$-0,0458984375$ &$0,0625$& $0,0080566406$ &$0,03125$\\ |
| 155 |
|
|
$1,71875$ &$1,734375$ &$1,7265625$ &$-0,0458984375$ &$0,0080566406$ &$-0,0189819336$ &$0,015625$ \\ |
| 156 |
|
|
$1,7265625$ &$1,734375$ &$1,73046875$ &$-0,0189819336$& $0,0080566406$ &$-0,0054779053$& $0,0078125$ \\ |
| 157 |
|
|
$1,73046875$ &$1,734375$ &$1,732421875$ &$-0,0054779053$ &$0,0080566406$& $0,001285553$ &$0,00390625$ \\ |
| 158 |
|
|
$1,73046875$ &$1,732421875$ &$1,7314453125$ &$-0,0054779053$ &$0,001285553$ &$-0,0020971298$ &$0,001953125$ \\ |
| 159 |
|
|
|
| 160 |
|
|
\hline |
| 161 |
|
|
\end{tabular} |
| 162 |
|
|
\normalsize |
| 163 |
|
|
\hspace{5cm}\\ |
| 164 |
|
|
\\ |
| 165 |
|
|
Après $10$ itérations la solution est $r=1,7314453125\pm0,0009765625$ alors que la solution théorique est $r=\sqrt{3}=1,732050808$. |
| 166 |
|
|
|
| 167 |
|
|
|
| 168 |
|
|
\section{Méthode du point fixe} |
| 169 |
|
|
\subsection{Calcul d'un point fixe} |
| 170 |
|
|
Définition d'un point fixe : un point fixe d'une fonction $f(x)$ est un point invariant de cette fonction. $x_0$ défini par $x_0=f(x_0)$ est un point fixe de $f$. |
| 171 |
|
|
\\Un point fixe d'une fonction se calcule de la façon suivante : |
| 172 |
|
|
\begin{eqnarray*} |
| 173 |
|
|
\left \{ |
| 174 |
|
|
\begin{array}{l} |
| 175 |
|
|
x_0\quad donne\\ |
| 176 |
|
|
x_{n+1}=f(x_n) |
| 177 |
|
|
\end{array} |
| 178 |
|
|
\right. |
| 179 |
|
|
\end{eqnarray*} |
| 180 |
|
|
\begin{algorithm}[H] |
| 181 |
|
|
\SetAlgoLined |
| 182 |
|
|
%\LinesNumbered |
| 183 |
francois |
948 |
\KwData{\\$\epsilon_a$ un critère d'arrêt.\\ $N$ un nombre maximal d'itération.\\$f(x)$ une fonction.\\$x_0$ une valeur de départ} |
| 184 |
francois |
939 |
\KwResult{Racine $r$ de la fonction $f(x)$} |
| 185 |
|
|
$compteur=0$\\ |
| 186 |
|
|
\Repeat{$\frac{|x_{n+1}-x_n|}{|x_n|}<\epsilon_a$} |
| 187 |
|
|
{ |
| 188 |
|
|
$x_{n+1}=f(x_n)$\\ |
| 189 |
|
|
compteur=compteur+1\\ |
| 190 |
|
|
\If{$compteur>N$}{Arrêt non convergence} |
| 191 |
|
|
} |
| 192 |
|
|
$r=x_{n+1}$ est la racine de $f(x)$ |
| 193 |
|
|
\caption{Algorithme de la méthode du point fixe} |
| 194 |
|
|
\end{algorithm} |
| 195 |
|
|
\hspace{3cm}\\ |
| 196 |
|
|
Pour résoudre l'équation $f(x)=0$ à l'aide de la méthode du point fixe, il suffit de transformer le problème en une équation $g(x)=x$ et rechercher un point fixe de cette seconde équation. Il y a donc plusieurs solutions pour effectuer cette transformation. |
| 197 |
|
|
\subsection{Exemple} |
| 198 |
|
|
Dans cette exemple on veut résoudre $f(x)=x^2-2x-3=0$. |
| 199 |
|
|
On effectue trois transformations différentes : |
| 200 |
|
|
\begin{itemize} |
| 201 |
|
|
\item cas 1 |
| 202 |
|
|
\begin{eqnarray*} |
| 203 |
|
|
x^2&=&2x+3\\ |
| 204 |
|
|
x&=&\sqrt{2x+3}\\ |
| 205 |
|
|
g_1(x)&=&\sqrt{2x+3} |
| 206 |
|
|
\end{eqnarray*} |
| 207 |
|
|
\item cas 2 |
| 208 |
|
|
\begin{eqnarray*} |
| 209 |
|
|
x(x-2)-3&=&0\\ |
| 210 |
|
|
x&=&\frac{3}{x-2}\\ |
| 211 |
|
|
g_2(x)&=&\frac{3}{x-2} |
| 212 |
|
|
\end{eqnarray*} |
| 213 |
|
|
\item cas 3 |
| 214 |
|
|
\begin{eqnarray*} |
| 215 |
|
|
x^2-3&=&2x\\ |
| 216 |
|
|
x&=&\frac{x^2-3}{2}\\ |
| 217 |
|
|
g_3(x)&=&\frac{x^2-3}{2} |
| 218 |
|
|
\end{eqnarray*} |
| 219 |
|
|
|
| 220 |
|
|
\end{itemize} |
| 221 |
|
|
Calcul de racines selon chaque cas : |
| 222 |
|
|
|
| 223 |
|
|
\footnotesize |
| 224 |
|
|
\begin{tabular}{|r|r|r|r|} |
| 225 |
|
|
\hline |
| 226 |
|
|
& $g_1(x)$ & $g_2(x)$ & $g_3(x)$ \\ |
| 227 |
|
|
\hline |
| 228 |
|
|
$x_0$ & $4$ & $4$ & $4$ \\ |
| 229 |
|
|
$x_1$ & $3,3166247904$ & $ 1,5$ & $ 6,5$ \\ |
| 230 |
|
|
$x_2$ &$3,103747667$ & $ -6$ & $ 19,625$ \\ |
| 231 |
|
|
$x_3$ & $3,0343854953$ & $ -0,375$ & $ 191,0703125$ \\ |
| 232 |
|
|
$x_4$ &$3,0114400194$ & $ -1,2631578947$ & $ 18252,4321594238$ \\ |
| 233 |
|
|
$x_5$ & $3,0038109193$ & $ -0,9193548387$ & $ 1,66575638E+008$ \\ |
| 234 |
|
|
$x_6$ & $3,0012700376$ & $ -1,0276243094$ & $ 1,38737216E+016$ \\ |
| 235 |
|
|
$x_7$ & $3,000423316$ & $ -0,9908759124$ & $ 9,62400762E+031$ \\ |
| 236 |
|
|
$x_8$ & $3,000141102$ & $ -1,0030506406$ & $ 4,63107613E+063$ \\ |
| 237 |
|
|
$x_9$ & $3,0000470336$ & $ -0,9989841528$ & $ 1,07234331E+127$ \\ |
| 238 |
|
|
$x_{10}$ & $3,0000156778$ & $ -1,0003387304$ & $ 5,74960084E+253$ \\ |
| 239 |
|
|
\hline |
| 240 |
|
|
\end{tabular} |
| 241 |
|
|
\normalsize |
| 242 |
|
|
\hspace{5cm}\\ |
| 243 |
|
|
\\On constate que le cas 1 converge vers la racine $3$, le cas 2 converge vers la racine $-1$ et le cas 3 diverge. |
| 244 |
|
|
\subsection{Analyse de convergence} |
| 245 |
|
|
L'exemple précédent montre que la convergence de l'algorithme n'est pas immédiate. Nous voulons ici trouver les conditions de convergence. |
| 246 |
|
|
Soit $r$ une racine de $f(x)$. $r$ est aussi point fixe d'une fonction $g(x)$. On a donc |
| 247 |
|
|
\begin{eqnarray*} |
| 248 |
|
|
\left \{ |
| 249 |
|
|
\begin{array}{l} |
| 250 |
|
|
f(r)=0\\ |
| 251 |
|
|
r=g(r) |
| 252 |
|
|
\end{array} |
| 253 |
|
|
\right. |
| 254 |
|
|
\end{eqnarray*} |
| 255 |
|
|
A chaque itération l'erreur $e_n$ est |
| 256 |
|
|
\begin{eqnarray*} |
| 257 |
|
|
e_n=x_n-r |
| 258 |
|
|
\end{eqnarray*} |
| 259 |
|
|
Si $e_n\to 0$ alors il y a convergence sinon il y a divergence. |
| 260 |
|
|
On a alors |
| 261 |
|
|
\begin{eqnarray*} |
| 262 |
|
|
e_{n+1}&=&x_{n+1}-r\\ |
| 263 |
|
|
&=&g(x_n)-g(r)\\ |
| 264 |
|
|
&=&g(e_n+r)-g(r)\\ |
| 265 |
|
|
\end{eqnarray*} |
| 266 |
|
|
On développe l'expression de $g(e_n+r)$ en série de Taylor: |
| 267 |
|
|
\begin{eqnarray*} |
| 268 |
|
|
g(e_n+r)=g(r)+g'(r)e_n+\frac{g''(r)}{2!}e_n^2+...+\frac{g^{(n)}(r)}{n!}e_n^n |
| 269 |
|
|
\end{eqnarray*} |
| 270 |
|
|
et on a alors |
| 271 |
|
|
\begin{eqnarray*} |
| 272 |
|
|
e_{n+1}&=&g'(r)e_n+\frac{g''(r)}{2!}e_n^2+...+\frac{g^{(n)}(r)}{n!}e_n^n\\ |
| 273 |
|
|
e_{n+1}&\simeq &g'(r)e_n\quad si \quad g'(r)\neq 0\\ |
| 274 |
|
|
e_{n+1}&\simeq &\frac{g''(r)}{2}e_n^2\quad si \quad g'(r)=0 \quad et \quad g''(r)\neq 0\\ |
| 275 |
|
|
\end{eqnarray*} |
| 276 |
|
|
\\ |
| 277 |
|
|
On dit qu'une méthode des points fixes converge à l'ordre $p$ si |
| 278 |
|
|
\begin{eqnarray*} |
| 279 |
|
|
|e_{n+1}|&\simeq &C|e_n|^p |
| 280 |
|
|
\end{eqnarray*} |
| 281 |
|
|
où $C$ est une constante. La convergence d'ordre $1$ est dite linéaire et la convergence d'ordre $2$ est dite quadratique. |
| 282 |
|
|
\\ |
| 283 |
|
|
Si $|C|<1$ il y a diminution de l'erreur après chaque itération. Il y a donc convergence à l'ordre $p$. Si $C$ est négative alors il y a convergence par oscillation autour le la racine $r$. |
| 284 |
|
|
\\Si $|C|>1$ il y a augmentation de l'erreur après chaque itération. Il y a donc divergence. |
| 285 |
|
|
\\Si $|C|=1$ il y a indétermination de la convergence. |
| 286 |
|
|
\\$|C|$ représente aussi le taux de convergence de la méthode. Plus $|C|$ est petit plus la convergence est rapide. |
| 287 |
|
|
\\La convergence dépend aussi du choix de $x_0$. En général on essaie de prendre $x_0$ le plus proche possible de la solution. Ceci n'est pas un problème en ingénierie parce que l'on a toujours une petite idée de la solution avant d'entreprendre un calcul. |
| 288 |
|
|
\subsection{Analyse de la convergence sur l'exemple } |
| 289 |
|
|
Calcul du taux de convergence pour chaque cas de l'exemple précédent. |
| 290 |
|
|
|
| 291 |
|
|
\begin{tabular}{|c|c|c|} |
| 292 |
|
|
\hline |
| 293 |
|
|
& $r_1=3$ & $r_2=-1$ \\ |
| 294 |
|
|
\hline |
| 295 |
|
|
$g_1'(r)=\frac{1}{\sqrt{2r+3}}$ & $\frac{1}{3}$ & $1$\\ |
| 296 |
|
|
$g_2'(r)=-\frac{3}{(r-2)^2}$ & $-3$ & $-\frac{1}{3}$\\ |
| 297 |
francois |
1034 |
$g_3'(r)=r$ & $3$ & $-1$\\ |
| 298 |
francois |
939 |
\hline |
| 299 |
|
|
\end{tabular} |
| 300 |
|
|
|
| 301 |
|
|
On retrouve que le cas 1 converge vers $r_1$ et que le cas 2 converge avec oscillation vers $r_2$ alors que le cas 3 diverge. |
| 302 |
|
|
\subsection{Exercice} |
| 303 |
|
|
On désire calculé la racine de $f(x)=x^2-3=0$ comme dans la méthode de la bissection. |
| 304 |
|
|
\\On cherche à mettre le problème sous la forme de recherche de point fixe. |
| 305 |
|
|
\begin{eqnarray*} |
| 306 |
|
|
f(x)=x^2-3&=&0\\ |
| 307 |
|
|
x^2&=&3\\ |
| 308 |
|
|
x&=&\frac{3}{x}\\ |
| 309 |
|
|
g(x)&=&\frac{3}{x} |
| 310 |
|
|
\end{eqnarray*} |
| 311 |
|
|
Calcul du point fixe avec $x_0=1$.\\ |
| 312 |
|
|
\footnotesize |
| 313 |
|
|
\begin{tabular}{|r|r|} |
| 314 |
|
|
\hline |
| 315 |
|
|
Itération & $g_n(x)$ \\ |
| 316 |
|
|
\hline |
| 317 |
|
|
$0$ & $1$ \\ |
| 318 |
|
|
$1$ & $3$ \\ |
| 319 |
|
|
$2$ & $1$ \\ |
| 320 |
|
|
$3$ & $3$ \\ |
| 321 |
|
|
$4$ & $1$ \\ |
| 322 |
|
|
\hline |
| 323 |
|
|
\end{tabular} |
| 324 |
|
|
\normalsize |
| 325 |
|
|
\\Il y a divergence avec cette fonction $g$. Ceci est normal puisque $g'(\sqrt{3})=\frac{-3}{x^2}=-1$, la convergence ne peut pas être atteinte et il y a oscillation autour de la solution. |
| 326 |
|
|
\\On cherche à mettre le problème sous une autre forme de point fixe. |
| 327 |
|
|
\begin{eqnarray*} |
| 328 |
|
|
f(x)=x^2-3&=&0\\ |
| 329 |
|
|
\frac{x^2-3}{2x}&=&0\\ |
| 330 |
|
|
-\frac{x^2-3}{2x}&=&0\\ |
| 331 |
|
|
-\frac{x^2-3}{2x}+x&=&x\\ |
| 332 |
|
|
g(x)&=&x-\frac{x^2-3}{2x}\\ |
| 333 |
|
|
\end{eqnarray*} |
| 334 |
|
|
|
| 335 |
|
|
Calcul du point fixe avec $x_0=1$.\\ |
| 336 |
|
|
\footnotesize |
| 337 |
|
|
\begin{tabular}{|r|r|} |
| 338 |
|
|
\hline |
| 339 |
|
|
Itération & $g_n(x)$ \\ |
| 340 |
|
|
\hline |
| 341 |
|
|
$0$ & $1$ \\ |
| 342 |
|
|
$1$ & $2$ \\ |
| 343 |
|
|
$2$ & $1,75$ \\ |
| 344 |
|
|
$3$ & $1,7321428571$ \\ |
| 345 |
|
|
$4$ & $1,73205081$ \\ |
| 346 |
|
|
$5$ & $1,7320508076$\\ |
| 347 |
|
|
$6$ & $1,7320508076$\\ |
| 348 |
|
|
\hline |
| 349 |
|
|
\end{tabular} |
| 350 |
|
|
\normalsize |
| 351 |
|
|
\\La méthode a convergé vers $r=\sqrt{3}$ |
| 352 |
|
|
\\Il y a convergence d'ordre 2 puisque $g'(\sqrt{3})=\frac{1}{2}-\frac{3}{2x^2}=0$ et que $g''(\sqrt{3})=\frac{3}{2x^3}=\frac{\sqrt{3}}{6}$ ce qui donne un taux de convergence de $\frac{\sqrt{3}}{12}$. |
| 353 |
|
|
\section{Méthode de Newton-Raphson} |
| 354 |
|
|
\subsection{Description de la méthode} |
| 355 |
|
|
L'idée de la méthode de newton-Raphson est de rechercher les racines de la fonction $f(x)$ en la remplaçant par son développement en série de Taylor autour du point $x_0$. |
| 356 |
|
|
\begin{eqnarray*} |
| 357 |
|
|
f(x)&=&0\\ |
| 358 |
|
|
f(x_0)+f'(x_0)\delta x+\frac{f''(x_0)}{2!}\delta x^2+.....&=&0\\ |
| 359 |
|
|
f(x_0)+f'(x_0)\delta x&\simeq&0\\ |
| 360 |
|
|
\delta x&\simeq&-\frac{f(x_0)}{f'(x_0)}\\ |
| 361 |
|
|
\end{eqnarray*} |
| 362 |
|
|
on pose ensuite $x_1=x_0+\delta x$ et on recommence le processus jusqu'à atteindre la convergence.\\ |
| 363 |
|
|
\begin{algorithm}[H] |
| 364 |
|
|
\SetAlgoLined |
| 365 |
|
|
%\LinesNumbered |
| 366 |
francois |
1034 |
\KwData{\\$\epsilon_a$ un critère d'arrêt.\\ $N$ un nombre maximal d'itération.\\$f(x)$ une fonction.\\$f'(x)$ la dérivée de $f$.\\$x_0$ une valeur de départ} |
| 367 |
francois |
939 |
\KwResult{Racine $r$ de la fonction $f(x)$} |
| 368 |
|
|
$compteur=0$\\ |
| 369 |
|
|
\Repeat{$\frac{|x_{n+1}-x_n|}{|x_n|}<\epsilon_a$} |
| 370 |
|
|
{ |
| 371 |
|
|
$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$\\ |
| 372 |
|
|
compteur=compteur+1\\ |
| 373 |
|
|
\If{$compteur>N$}{Arrêt non convergence} |
| 374 |
|
|
} |
| 375 |
|
|
$r=x_{n+1}$ est la racine de $f(x)$ |
| 376 |
|
|
\caption{Algorithme de Newton-Raphson} |
| 377 |
|
|
\end{algorithm} |
| 378 |
|
|
|
| 379 |
|
|
\subsection{Exemple} |
| 380 |
|
|
Résoudre $f(x)=e^{-x}-x=0$.\\ |
| 381 |
|
|
On calcul $f'(x)=-e^{-x}-1$ et on effectue l'algorithme de Newton-Raphson en utilisant $x_0=0$.\\ |
| 382 |
|
|
\footnotesize |
| 383 |
|
|
\begin{tabular}{|r|r|} |
| 384 |
|
|
\hline |
| 385 |
|
|
Itération & $x_{n+1}$ \\ |
| 386 |
|
|
\hline |
| 387 |
|
|
$0$ & $0$ \\ |
| 388 |
|
|
$1$ & $0.5$ \\ |
| 389 |
|
|
$2$ & $0.5663110$ \\ |
| 390 |
|
|
$3$ & $0.5671432$ \\ |
| 391 |
|
|
$4$ & $0.5671433$ \\ |
| 392 |
|
|
\hline |
| 393 |
|
|
\end{tabular} |
| 394 |
|
|
\normalsize |
| 395 |
|
|
\hspace{6cm}\\ |
| 396 |
|
|
\\ L'algorithme converge vers la racine $r=0.5671433$. |
| 397 |
|
|
\subsection{Analyse de convergence} |
| 398 |
|
|
Si on définit la fonction $g(x)$ tel que |
| 399 |
|
|
\begin{eqnarray*} |
| 400 |
|
|
g(x)&=&x-\frac{f(x)}{f'(x)}\\ |
| 401 |
|
|
\end{eqnarray*} |
| 402 |
|
|
alors la méthode de Newton-Raphson apparaît comme une méthode du point fixe. |
| 403 |
|
|
Le taux de convergence est donc donnée par $|g'(r)|$. |
| 404 |
|
|
\\En calculant |
| 405 |
|
|
\begin{eqnarray*} |
| 406 |
|
|
g'(x)&=&1-\frac{f'^2(x)-f(x)f''(x)}{f'^2(x)}=\frac{f(x)f''(x)}{f'^2(x)}\\ |
| 407 |
|
|
\end{eqnarray*} |
| 408 |
|
|
on a |
| 409 |
|
|
\begin{eqnarray*} |
| 410 |
|
|
g'(r)&=&\frac{f(r)f''(r)}{f'^2(r)}=0\quad si \quad f'(r)\neq0\\ |
| 411 |
|
|
\end{eqnarray*} |
| 412 |
|
|
La convergence de la méthode de Newton-Raphson est au moins quadratique. |
| 413 |
|
|
\\En calculant |
| 414 |
|
|
\begin{eqnarray*} |
| 415 |
|
|
g''(x)&=&\frac{f'^3(x)f''(x)+f(x)f'''(x)f'^2(x)-2f(x)f'(x)f''^2(x)}{f'^4(x)} \\ |
| 416 |
|
|
\end{eqnarray*} |
| 417 |
|
|
on a |
| 418 |
|
|
\begin{eqnarray*} |
| 419 |
|
|
g''(r)&=&\frac{f'^3(r)f''(r)+f(r)f'''(r)f'^2(r)-2f(r)f'(r)f''^2(r)}{f'^4(r)} \\ |
| 420 |
|
|
&=&\frac{f'^3(r)f''(r)}{f'^4(r)}=\frac{f''(r)}{f'(r)} \quad si \quad f'(r)\neq0 |
| 421 |
|
|
\end{eqnarray*} |
| 422 |
francois |
948 |
$f''(r)$ et $f'(r)$ ne sont pas a priori non nulles. On peut dire que $g''(r)=\frac{f''(r)}{f'(r)}$ |
| 423 |
|
|
\\L'erreur s?écrit alors |
| 424 |
|
|
\begin{eqnarray*} |
| 425 |
|
|
e_{n+1}=\left|\frac{f''(r)}{2f'(r)}\right|e_n^2 |
| 426 |
|
|
\end{eqnarray*} |
| 427 |
|
|
Le taux de convergence de la méthode de Newton-Raphson est $\left|\frac{f''(r)}{2f'(r)}\right|$. |
| 428 |
|
|
\\Dans le cas de l'exemple précédent le taux de convergence vaut |
| 429 |
|
|
\begin{eqnarray*} |
| 430 |
|
|
C=\left|\frac{f''(r)}{2f'(r)}\right|=\left|\frac{e^{-r}}{2(-e^{-r}-1)}\right|=\left|\frac{r}{2(-r-1)}\right|=\frac{r}{2(r+1)}=0.180948 |
| 431 |
|
|
\end{eqnarray*} |
| 432 |
|
|
|
| 433 |
francois |
939 |
\subsection{Exercice} |
| 434 |
|
|
On vérifie que la solution de $f(x)=x^2-3=0$ calculée par la méthode du point fixe a été en fait réalisé par la méthode de Newton-Raphson. En effet la fonction $g(x)$ utilisé est en fait |
| 435 |
|
|
\begin{eqnarray*} |
| 436 |
|
|
g(x)&=&x-\frac{x^2-3}{2x}\\ |
| 437 |
|
|
g(x)&=&x-\frac{f(x)}{f'(x)}\\ |
| 438 |
|
|
\end{eqnarray*} |
| 439 |
francois |
948 |
\\[2cm] |
| 440 |
francois |
939 |
|
| 441 |
francois |
948 |
\begin{encadre}{À retenir} |
| 442 |
|
|
L'utilisation d'une méthode numérique pour solutionner un problème d'ingénierie complexe nécessite une mise en équation du problème. |
| 443 |
|
|
Le choix de la méthode numérique utilisée pour résoudre le problème doit être validé et le résultat doit être analysé en tenant compte de l'erreur numérique. |
| 444 |
|
|
Les notions de convergence d'une méthode numérique et de rapidité de convergence doivent être comprises. |
| 445 |
|
|
Les techniques de bissection, point fixe et Newton-Raphson doivent être maîtrisées. |
| 446 |
francois |
939 |
|
| 447 |
|
|
|
| 448 |
francois |
948 |
\end{encadre} |
| 449 |
francois |
939 |
|
| 450 |
|
|
|
| 451 |
francois |
948 |
|
