\documentclass[a4paper,12pt]{report} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[francais]{babel} \usepackage{soul} \usepackage{ulem} \usepackage{graphicx} \usepackage{verbatim} \usepackage{amsmath} \usepackage{amssymb} \usepackage{mathrsfs} \addto\captionsfrench{\renewcommand{\chaptername}{Partie}} \addto\captionsfrench{\renewcommand{\bibname}{Références}} \begin{document} \begin{titlepage} \vspace*{2cm} \begin{center} \begin{Huge} \bsc{Analyse Numérique - TP \no1\\ Calcul des Zéros des Fonctions}\\ \end{Huge} \vspace*{7cm} \begin{LARGE} \bsc{Groupe C06}\\ \end{LARGE} \vspace*{0.5cm} \begin{Large} Christian \bsc{Ingouff}\\ Pierre-Alexandre \bsc{Tyndal}\\ \vspace*{1cm} EISTI\\ \end{Large} \vspace*{0.6cm} 2013/2014\\ Semestre 2\\ \end{center} \end{titlepage} \tableofcontents \chapter*{Introduction} \addcontentsline{toc}{chapter}{Introduction} Le travail présenté dans ce rapport\cite{latex} traite du calcul de la valeur du minimum d'une fonction à une variable. Dans l'intérêt de notre étude, les fonctions manipulées dans le cadre de cette réalisation sont non linéaires et réelles.\\ Parmi les méthodes existantes, nous présenterons la méthode de Newton-Raphson pour le calcul des racines des fonctions. Ainsi, ce rapport présente le principe, les conditions, l'implémentation et le résultat de l'application d'une telle méthode. Ceci sera conclu par un récapitulatif critique de la méthode, présentant ses avantages et inconvénients. \chapter{Description mathématique : Méthode de Newton-Raphson} La méthode de Newton-Raphson\cite{eisti} est utilisée pour calculer les racines d'une fonction non linéaire. Pour cela, elle se fonde sur le développement de Taylor au premier ordre.\\ Soit \( f : D \rightarrow \mathbb{R} ; D \subset \mathbb{R}, f \in C^{2} \). On cherche la racine \( \xi \in D \) de la fonction \( f \). Pour cela, on prend \( x_{0} \in D \), pas trop éloigné de \( \xi \). La méthode consiste à obtenir \( x_{1} \in D \), qui devrait être plus proche de la racine, en résolvant l'équation suivante : \[ \begin{array}{l l} & f(x_{0}) + f'(x_{0})(x_{1} - x_{0}) = 0\\ \Leftrightarrow & x_{1} = x_{0} - \dfrac{f(x_{0})}{f'(x_{0})} ; f'(x_{0}) \neq 0\\ \end{array} \] \vspace*{1cm} \noindent En répétant la résolution plusieurs fois, on peut ainsi approcher la racine \( \xi \) au fur et à mesure. Le problème peut alors se modéliser sous la forme suivante : \[ \left\{ \begin{array}{l} x_{0} \in D\\ x_{n+1} = x_{n} - \dfrac{f(x_{n})}{f'(x_{n})} ; n \in \mathbb{N}, \forall n \in \mathbb{N}, f'(x_{n}) \neq 0\\ \end{array} \right. \] \noindent De cette manière, la logique de la méthode de Newton-Raphson dicterait que : \[ \lim_{n \to +\infty} x_{n} = \xi \] \newpage \noindent Pour adapter la méthode à la minimisation d'une fonction, on utilise la propriété suivante :\\ \[ x^{*} \text{ est un minimum} \Rightarrow f'(x^{*}) = 0 \] \vspace*{1.5cm} \noindent En récapitulatif, les conditions imposées à la méthode de Newton-Raphson sont les suivantes :\\ \begin{itemize} \item[\(\bullet\)] \( f \in C^{2} \) \item[\(\bullet\)] \( x_{0} \in D \), pas trop éloigné de la racine \( \xi \) \item[\(\bullet\)] \( \forall n \in \mathbb{N}, f'(x_{n}) \neq 0 \) \end{itemize} \chapter{Réalisation informatique} \section{Description} La réalisation informatique se concentre d'abord sur la recherche des racines d'une fonction. Pour cela, elle utilise la méthode de Newton-Raphson décrite précédemment.\\ Afin d'appliquer la méthode, il faut cependant aussi intégrer la notion de dérivées dans le programme. Nous proposons ainsi deux méthodes : la première utilise simplement la formule analytique (c'est-à-dire calculée au préalable), alors que la deuxième fera usage de l'approximation de Taylor au premier ordre : \[ f'(x) \simeq \dfrac{f(x+h) - f(x)}{h} \] \vspace*{1cm} Il s'agit désormais de répéter l'opération décrite précédemment pour pouvoir approcher la racine que l'on cherche. On sait que l'on approche d'une racine quand la différence entre les termes successifs tend vers 0, c'est-à-dire que l'on cherche \( n \) sous la condition suivante : \[ \forall \varepsilon > 0, \exists n \in \mathbb{N}, |x_{n+1} - x_{n}| < \varepsilon \] Dans le cas où il n'y a pas de racines, la suite \( (x_{n})_{n \in \mathbb{N}} \) diverge. Il faut donc penser à mettre un nombre \( n_{\text{max}} \) d'itérations (nous prenons ici arbitrairement \( n_{\text{max}} = 10000 \)). \newpage \section{Algorithme} \noindent Par conséquent, en définissant une précision \( \varepsilon \) pour la condition d'arrêt, l'algorithme de la méthode Newton-Raphson pour le calcul de racines se présente ainsi : \begin{verbatim} Fonction NewtonRaphson(f : fonction, x0 : réel, eps : réel) : réel // f : fonction à analyser // x0 : x de départ // eps : précision var X : tableau de réels // représente la suite (xn) i : entier // itération nmax : entier // maximum d'itérations Début X(0) <- x0 i <- 0 Tant que |X(i+1) - X(i)| > eps et i < nmax X[i+1] <- intersection(f, X(i)) i <- i+1 FinTantQue Si i < nmax alors Retourner X(i) Sinon Retourner "Aucune racine" FinSi Fin \end{verbatim} \noindent Pour le calcul du minimum d'une fonction, il suffit d'appliquer le calcul de l'intersection avec la dérivée de la fonction plutôt qu'avec la fonction elle-même. \newpage \chapter{Etude des résultats} \noindent Dans l'ensemble de l'étude, le programme\cite{scilab} a été lancé avec les données suivantes : \begin{itemize} \item Précision : \( \varepsilon = 0.000001 \) \item Approximation de Taylor : \( h = 0.0001 \) \item Newton-Raphson : \( n_{\text{max}} = 10000 \) \end{itemize} \section{Calcul de racines} \subsection{Phase de calcul} \vspace*{0.1cm} \noindent Soient les fonctions réelles : \[ \left\{ \begin{array}{l l} f_{1}(x) = x^{2} - a & a > 0\\ f_{2}(x) = x^{2} + 17 & (x_{0} = 1)\\ f_{3}(x) = x - 2\sin(x) & (x_{0} = 1.1)\\ \end{array} \right. \] \noindent Pour \( f_{1} \), nous testerons pour les valeurs \[ \left\{ \begin{array}{l} a = 2\\ x_{0} = 0.5\\ \end{array} \right. \] \noindent ainsi que \[ \left\{ \begin{array}{l} a = 42\\ x_{0} = 42\\ \end{array} \right. \] \newpage Les résultats escomptés\cite{wolfram} sont les suivants : \[ \left\{ \begin{array}{l l} f_{1}, a = 2 & \pm \sqrt{2} \simeq \pm 1.41421356237\\ f_{1}, a = 42 & \pm \sqrt{42} \simeq \pm 6.48074069841\\ f_{2} & \text{Pas de racines}\\ f_{3} & 0, \pm 1.89549426703 \end{array} \right. \] Ci-dessous se trouvent les tableaux des itérations de chaque calcul :\\ \begin{center} \begin{tabular}{c c} \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{1} \text{ avec } a = 2, x_{0} = 0.5 \)}\\ \multicolumn{2}{|c|}{(formule analytique)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0& 0.5000000000 \\ 1& 2.2500000000 \\ 2& 1.5694444444 \\ 3& 1.4218904041 \\ 4& 1.4142342902 \\ 5& 1.4142135527 \\ 6& 1.4142135151 \\ \hline \end{tabular} & \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{1} \text{ avec } a = 2, x_{0} = 0.5 \)}\\ \multicolumn{2}{|c|}{(approximation Taylor)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0& 0.5000000000 \\ 1& 2.2498250175 \\ 2& 1.5694066541 \\ 3& 1.4218914694 \\ 4& 1.4142345307 \\ 5& 1.4142135940 \\ 6& 1.4142135564 \\ \hline \end{tabular} \end{tabular} \vspace*{0.5cm} \begin{tabular}{c c} \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{1} \text{ avec } a = 42, x_{0} = 42 \)}\\ \multicolumn{2}{|c|}{(formule analytique)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0&42.0000000000 \\ 1&21.5000000000 \\ 2&11.7267441860 \\ 3&7.6541505982 \\ 4&6.5706847589 \\ 5&6.4813562660 \\ 6&6.4807406937 \\ 7&6.4807406921 \\ \hline \end{tabular} & \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{1} \text{ avec } a = 42, x_{0} = 42 \)}\\ \multicolumn{2}{|c|}{(approximation Taylor)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0&42.0000000000 \\ 1&21.5000244054 \\ 2&11.7267782296 \\ 3&7.6541798141 \\ 4&6.5706959860 \\ 5&6.4813571252 \\ 6&6.4807407576 \\ 7&6.4807406560 \\ \hline \end{tabular} \end{tabular} \end{center} \newpage \begin{center} \begin{tabular}{c c} \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{2} \text{ avec } x_{0} = 1 \)}\\ \multicolumn{2}{|c|}{(formule analytique)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0&1.0000000000 \\ 1&-8.0000000000 \\ 2&-2.9375000000 \\ 3&1.4248670213 \\ 4&-5.2530355365 \\ 5&-1.0084057445 \\ 6&7.9249442236 \\ 7&2.8899093666 \\ 8&-1.4963140112 \\ 9&4.9324688467 \\ ...&... \\ \hline \end{tabular} & \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{2} \text{ avec } x_{0} = 1 \)}\\ \multicolumn{2}{|c|}{(approximation Taylor)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0&1.0000000000 \\ 1&-7.9995500225 \\ 2&-2.9371836119 \\ 3&1.4254111812 \\ 4&-5.2502517864 \\ 5&-1.0061154978 \\ 6&7.9457213356 \\ 7&2.9031342819 \\ 8&-1.4762275043 \\ 9&5.0200263783\\ ...&...\\ \hline \end{tabular} \end{tabular} \vspace*{0.5cm} \begin{tabular}{c c} \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{3} \text{ avec } x_{0} = 1.1 \)}\\ \multicolumn{2}{|c|}{(formule analytique)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0&1.1000000000 \\ 1&8.4529922615 \\ 2&5.2564136940 \\ 3&203.3835760907 \\ 4&17.9874660259 \\ 5&-67.5943030253\\ ...&...\\ 43&266148.3335503269 \\ 44&-1911692.7225781712 \\ 45&-1002233.9088852162 \\ 46&-666267.7999207005 \\ 47&2367090.7485990403 \\ ...&...\\ 76&1.1855588632 \\ 77&3.8737537227 \\ 78&1.7789645934 \\ 79&1.9048070075 \\ 80&1.8955438144 \\ 81&1.8954942829 \\ 82&1.8954942499 \\ \hline \end{tabular} & \begin{tabular}{|c|c|} \hline \multicolumn{2}{|c|}{\( f_{3} \text{ avec } x_{0} = 1.1 \)}\\ \multicolumn{2}{|c|}{(approximation Taylor)}\\ \hline \hline n & \( x_{n} \) \\ \hline 0&1.1000000000 \\ 1&8.4459380395 \\ 2&5.2389139065 \\ 3&1358.1506668365 \\ 4&13744.2343976542 \\ 5&9078.3409039940 \\ ...&...\\ 108&-51471.9504141341 \\ 109&-103421.2473611150 \\ 110&-206882.9976709758 \\ 111&-135790.3976192583 \\ 112&-42537.5714124546 \\ ...&...\\ 147&420.2291872214 \\ 148&1314.7551891458 \\ 149&-1.3574862063 \\ 150&-2.3933483933 \\ 151&-1.9745456696 \\ 152&-1.8987429629 \\ 153&-1.8955001225 \\ 154&-1.8954942892 \\ 155&-1.8954942562 \\ \hline \end{tabular} \end{tabular} \end{center} \newpage \subsection{Interprétation des résultats} Pour \( f_{1} \), avec les deux couples de valeurs, les résultats coïncident avec un résultat escompté selon la précision donnée, que ce soit avec la formule analytique ou l'approximation de la dérivée. En effet, la racine obtenue est à chaque fois la plus proche du point \( x_{0} \) initial. Les deux formules nous permettent d'obtenir les résultats en 7 ou 8 itérations toutes les deux.\\ On remarque cependant tout de suite la précision perdue avec l'approximation en comparant par exemple, pour le premier couple de valeurs : \[ n = 1 \Rightarrow x_{1_{\text{analytique}}} = 2.25 \text{ et } x_{1_{\text{Taylor}}} = 2.2498250175 \] Ceci dénotera une convergence plus directe avec la formule analytique qu'avec l'approximation.\\ \( f_{2} \) présente un cas de non solution : par conséquent, la suite \( x_{n} \) diverge, ce qui est bien représenté par les données obtenues. Il n'y aura aucune combinaison successive de \( (x_{n}, x_{n+1} \) dont la différence conviendra à la précision donnée, ce qui explique le résultat.\\ On obtient bel et bien une solution escomptée pour le cas de \( f_{3} \). Cependant, le caractère de la fonction fait faire au programme des itérations qui éloignent beaucoup \( x \) d'une racine envisagée, expliquant la centaine d'itérations nécessaires afin d'aboutir au résultat.\\ En effet, l'utilisation de l'intersection de la tangente dans des fonctions incluant la fonction \( \sin \) nuit à l'aboutissement de la méthode Newton-Raphson. La méthode veut parcourir une pente croissante ou décroissante afin d'arriver à un zéro, mais comme \( f_{3} \) est successivement croissante et décroissante sur \( \mathbb{R} \), l'allure alternante des tangentes amènera l'algorithme dans une fausse direction.\\ \vspace*{0.5cm} En première conclusion, la méthode de Newton-Raphson n'opérera bien que si la fonction est au moins localement monotone autour des racines à chercher, ce qui constitue une limite déjà contraignante dans l'univers des fonctions non linéaires. Elle s'avère toutefois relativement satisfaisante pour, par exemple, des fonctions polynômiales ou pseudo-polynômiales.\\ \newpage \section{Calcul de minima} \subsection{Phase de calcul} \noindent Soient les fonctions suivantes : \[ \left\{ \begin{array}{l l} f_{4}(x) = \sin(3x) + x^{2} - 2 & x \in [-3, 3], x_{0} = 1\\ f_{5}(x) = x \cos(x) & x \in [-2\pi, 2\pi], x_{0} = 0.1 \text{ et } x_{0} = 2.5\\ \end{array} \right. \] \noindent Les résultats escomptés\cite{wolfram} sont les suivants : \[ \left\{ \begin{array}{l l} f_{4}, x \in [-3, 3] & x_{\text{min}} = -0.427307846\\ f_{5}, x \in [-2\pi, 2\pi] & x_{\text{min}} = -2\pi \simeq -6.283185307\\ \end{array} \right. \] \vspace*{0.5cm} L'approximation de Taylor ne donne pas de résultats exploitables : elle ne s'approche pas assez pour \( f_{4} \) et diverge trop pour \( f_{5} \), probablement à cause d'erreurs trop grandes. Par conséquent, l'ensemble des résultats ci-dessous utilise la formule analytique de la dérivée pour les calculs.\\ \begin{figure}[h!] \begin{center} \includegraphics[width=12cm]{img/graph-f4.png} \caption{\( f_{4} : x_{min} = 1.2445900098 \)} \end{center} \end{figure} \newpage \begin{figure}[h!] \begin{center} \includegraphics[width=12cm]{img/graph-f5a.png} \caption{\( f_{5}, x_{0} = 0.1 : x_{min} = 3.4256184171 \)} \end{center} \end{figure} \begin{figure}[h!] \begin{center} \includegraphics[width=12cm]{img/graph-f5b.png} \caption{\( f_{5}, x_{0} = 0.1 : x_{min} = 2\pi \) (collision avec la borne supérieure)} \end{center} \end{figure} \newpage \subsection{Interprétation des résultats} Les résultats obtenus avec la formule analytique correspondent à des extrema locaux, voisins à \( x_{0} \). En effet, les résultats obtenus pour \( f_{4} \text{ et } f_{5}, x_{0} = 0.1 \) correspondent à des minima locaux, mais non globaux. Le résultat obtenu avec \( f_{5}, x_{0} = 2.5 \) correspond à un maximum local plutôt qu'à un minimum : le fait est que même si \[ x^{*} \text{ est un minimum} \Rightarrow f'(x^{*}) = 0 \]la réciproque n'est vraie qu'en partie, et inclut les maxima et les points selles dans l'implication.\\ Ceci constitue de premières limites qui restreignent beaucoup le potentiel de la méthode dans la recherche de minima globaux. On relève cependant que la méthode fonctionne pour chercher des extrema locaux, et il est possible d'implémenter une vérification de la positivité ou non de la dérivée seconde autour de l'extremum afin de différencier les minima des maxima.\\ L'échec de l'implémentation de la méthode avec l'approximation de Taylor peut être due à l'approximation induite par la première dérivation effectuée pour l'adapter à la recherche de minima. La première dérivation se fait car on cherche les zéros dans la fonction dérivée. Une hypothèse plausible est que l'approximation n'est pas localement monotone autour de la racine à chercher, ce qui déroute la méthode. Cette hypothèse expliquerait aussi pourquoi la méthode ne fonctionne pas quelque soit le \( h \) spécifié pour l'approximation de la dérivée.\\ Il faut donc connaitre exactement la dérivée première de la fonction à analyser, ce qui constitue une énorme limite à la méthode Newton-Raphson.\\ \chapter*{Conclusion} \addcontentsline{toc}{chapter}{Conclusion} La méthode de Newton-Raphson a réussi à présenter des résultats cohérents sous une certaine mesure. Dans notre étude, nous avons notamment réussi à déterminer des racines pour des fonctions polynômiales ou pseudo-polynômiales.\\ La détection de l'absence de racines est aussi bien en place, comme nous l'a montré l'étude de \( f_{2} \). Ceci démontre la validité de la méthode.\\ De plus, elle réussit à obtenir ces racines de façon rapide la plupart du temps, ce qui est intéressant dans le cadre de l'analyse numérique de fonctions non linéaires.\\ Cependant, comme il a été vu, cette méthode comporte de nombreuses limites : \begin{itemize} \item Elle ne fonctionne que pour la recherche de racines de fonctions dont la monotonie est certaine autour de la racine recherchée. \item Elle nécessite l'expression exacte de la dérivée de la fonction à analyser pour une utilisation optimale. \item Son utilisation pour la recherche d'extrema se limite à un cadre local\\ \end{itemize} En conclusion, la méthode de Newton-Raphson comporte sa part de validité, mais ses limites l'empêchent d'être potentiellement utilisable dans un cadre plus poussé.\\ \begin{thebibliography}{9} \addcontentsline{toc}{chapter}{Références} \bibitem{scilab} \noindent Ce programme a été conçu dans Scilab 5.4.1. Les graphiques proposés proviennent de la fonction "plot" de Scilab.\\ \hspace*{0.5cm}http://www.scilab.org/\\ \bibitem{latex} \noindent Ce rapport a été rédigé en \LaTeX\\ \hspace*{0.5cm}http://www.latex-project.org/\\ \bibitem{wolfram} \noindent Il a été fait usage de WolframAlpha pour l'étude des fonctions et le calcul des résultats escomptés.\\ \hspace*{0.5cm}http://www.wolframalpha.com/\\ \bibitem{eisti} \noindent Les notions mathématiques introduites dans ce rapport proviennent de cours fournis à l'EISTI.\\ \hspace*{0.5cm}http://arel.eisti.fr/\\ \hspace*{0.5cm}http://sifoci.eisti.fr/\\ % oui oui, c'est totalement vrai. \end{thebibliography} \chapter*{Annexes} \addcontentsline{toc}{chapter}{Annexes} \section*{Annexe A : Organigramme du programme} \addcontentsline{toc}{section}{Annexe A : Organigramme du programme} \begin{figure}[h] \begin{center} \includegraphics[width=13.5cm]{img/organi.png} \caption{Organigramme du programme Scilab} \end{center} \end{figure} \newpage \section*{Annexe B : Guide d'utilisation du programme} \addcontentsline{toc}{section}{Annexe B : Guide d'utilisation du programme} \subsection*{Exécution du programme} \noindent Vous trouverez joint à ce rapport, dans le dossier \texttt{src}, le fichier \texttt{code.sce} qui peut être executé sous Scilab. Pour ceci, il faut accéder depuis la console Scilab au dossier contenant \texttt{code.sce} (par exemple : \texttt{cd ananu-tp1/src/;}), puis exécuter avec \texttt{exec("code.sce");}.\\ \noindent Le code ainsi executé, il suffit de lancer \texttt{main();} pour accéder au programme.\\ \subsection*{Utilisation du programme} \noindent Le programme ainsi lancé propose à l'utilisateur plusieurs options : \begin{itemize} \item Choisir une fonction pour la recherche de racines\\(choisir un entier de 1 à 3) \item Choisir une fonction pour la recherche de minima\\(choisir un entier de 4 à 6) \item Modifier la précision (choisir 7) \item Quitter le programme (choisir 0) \end{itemize} \noindent L'utilisateur choisit son option en entrant un entier au clavier et en validant avec \texttt{Entrée}.\\ \noindent La modification de la précision se fait de manière analogue : il sera demandé à l'utilisateur d'entrer un réel correspondant à la nouvelle précision et de valider avec \texttt{Entrée}.\\ \noindent Il est parfois demandé à l'utilisateur de répondre à des questions oui ou non, dénotées par \texttt{(o/n)}. L'utilisateur répond avec le clavier par un "o" pour oui ou par un "n" pour non et valide avec \texttt{Entrée}.\\ \newpage \subsection*{Utilisation de Newton-Raphson} \noindent Pour tous les calculs, il est demandé de spécifier si l'utilisateur veut utiliser la formule analytique pour les calculs (avec une question oui ou non). Le cas échéant, le calcul se fait avec l'approximation de Taylor.\\ \noindent Pour le calcul avec \( f_{1} \), il est demandé de spécifier les valeurs de \( a \) et de \( x_{0} \). Pour cela, quand la demande vient, l'utilisateur entre des réels avec le clavier et valide avec \texttt{Entrée}.\\ \noindent A l'issue de ces vérifications, le programme opère la recherche de racine ou de minimum et retourne une solution accompagnée du nombre d'itérations. Il fournit aussi la liste des valeurs de la suite \( x_{n} \) dans \texttt{src/log\_iteration.txt}.\\ \noindent S'il y a une solution valide, le programme propose à l'utilisateur de l'afficher par rapport à la fonction dans un graphique (via une question oui ou non). La validation de cette demande affiche une graphique généré grâce à \texttt{plot2D} représentant la solution graphiquement.\\ \noindent A l'issue de l'ensemble de ces demandes, l'utilisateur sera invité à relancer le programme depuis le choix de la fonction. Si l'utilisateur refuse de recommencer, le programme se termine.\\ \end{document}