From: couchot Date: Thu, 21 Nov 2013 08:22:21 +0000 (+0100) Subject: j X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-mesi.git/commitdiff_plain?ds=inline j --- diff --git a/complexite.tex b/complexite.tex index 4fdf00d..6d66125 100644 --- a/complexite.tex +++ b/complexite.tex @@ -36,7 +36,7 @@ $5n^3\leq 10.\dfrac{n^3}{2}$. constante $c$ telle que $\dfrac{n^3}{2} \leq c.(n^2 +17n + 5)$ soit encore $\dfrac{n^3}{2(n^2 +17n + 5)} \leq c$ et donc -$\dfrac{n^3}{2} \leq c$ ce qui est impossible. +$\dfrac{n}{2} \leq c$ ce qui est impossible. \end{itemize} @@ -200,7 +200,7 @@ On considère tout d'abord l'algorithme suivant: \KwData{$n$: degré, $(a_i)_{0 \le i \le n}$: coefficients, $t$: réel en lequel on évalue} \KwResult{$\textit{val}$: réel tel que $\textit{val}= p(t)$} - $a' = a$ \; \nllabel{laff1} + $a' = a_n$ \; \nllabel{laff1} \For{$i=n-1$ \KwTo $0$}{\nllabel{laford} $a' = a_i + t \times a'$ \; \nllabel{lafori} \nllabel{laforf}} @@ -280,7 +280,7 @@ n & T_1(n) & T_2(n) \\ \begin{enumerate} \item En déduire quel sera le temps nécessaire au traitement de données de taille $n'=10^4$. -\item Même question avec $n'=200\lambda$ où $\lambda$ réel de $[1, +\infty[$. +\item Même question avec $n'=200\lambda$ où $\lambda$ réel de $[0, +\infty[$. \item Déterminer la taille maximale des données que peuvent traiter $A_1$ et $A_2$ si le temps disponible est $t=10^5$. \end{enumerate} diff --git a/equations.tex b/equations.tex index 8fec68d..bd10efc 100644 --- a/equations.tex +++ b/equations.tex @@ -1,6 +1,5 @@ \section{Motivation} -Bien qu’il puisse être posé simplement (trouver tous les $x$ tel que $P(x) =0$), -résoudre algébriquement des équations +Résoudre algébriquement des équations est un problème difficile. Depuis l'antiquité, l’homme a cherché des algorithmes donnant les valeurs des racines d'un polynôme @@ -12,18 +11,17 @@ la forme $ x^3 + px+q = 0 $ avec $p$ et $q$ non nuls. Calculons le discriminant -$\Delta = \frac{4}{27}p^3+ p^2$ et discutons de son signe: +$\Delta = \frac{4}{27}p^3+ q^2$ et discutons de son signe: \begin{itemize} \item si $\Delta$ est nul, l'équation possède deux solutions réelles, une simple et une double : - -$$ +$ \begin{cases} x_0=2\sqrt[3]{\frac{-q}2}=\frac{3q}p \\ x_1=x_2=-\sqrt[3]{\frac{-q}2}=\frac{-3q}{2p} \end{cases} -$$ +$ \item Si $\Delta$ est positif, l'équation possède une solution réelle @@ -31,21 +29,21 @@ $$ $u = \sqrt[3]{\frac{-q + \sqrt{\Delta}}2}$ et $v = \sqrt[3]{\frac{-q - \sqrt{\Delta}}2}$. La seule solution réelle est alors $x_0=u+v$. Il existe également deux solutions complexes conjuguées l'une de l'autre: -$$ +$ \begin{cases} x_1= j u +\bar{j} v \\ x_2= j^2u +\overline{j^2}\end{cases} -\qquad\textrm{ où }\qquad j=-\frac12+ i \frac{\sqrt3}2=e^{i\frac{2\pi}3} -$$ - -\item si $\Delta$ est négatif, l'équation possède trois solutions réelles: -$$ -x_k = 2 \sqrt{\frac{-p}{3}} \cos{\left(\frac13\arccos{\left(\frac{-q}{2}\sqrt{\frac{27}{-p^3}}\right)}+ \frac{2k\pi}{3}\right)}\qquad\mbox{ avec }\qquad k\in\{0,1,2\}. -$$ +\textrm{ où } j=-\frac12+ i \frac{\sqrt3}2=e^{i\frac{2\pi}3} +$ +\item sinon, l'équation a trois solutions réelles: +$ +x_k = 2 \sqrt{\frac{-p}{3}} \cos{\left(\frac13\arccos{\left(\frac{-q}{2}\sqrt{\frac{27}{-p^3}}\right)}+ \frac{2k\pi}{3}\right)}\textrm{ avec } k\in\{0,1,2\}. +$ \end{itemize} -Donnée à titre d'exemple, ce travail montre que rapidement on obtient +%Donnée à titre d'exemple, +Ce travail montre que rapidement on obtient des algorithmes compliqués. De plus, Abel a montrée en 1824 qu'il n'est pas toujours possible d'exprimer les racines de l'équation générale de @@ -83,7 +81,7 @@ le résultat est établi, c.-à-d. $f(a_{n+1})f(b_{n+1})\leq 0$; \item sinon, $f(a_n)f(x_n)> 0$. Ainsi $f(a_{n+1})f(b_{n+1})$ a le même signe que $f(a_{n+1})f(b_{n+1})f(a_n)f(x_n)$ c.-à-d. le signe de $f(x_{n})f(b_{n})f(a_n)f(x_n)$ soit encore le signe de $f(a_n)f(b_n)$. -Ce dernier est positif d'après l'hypothèse de récurence. +Ce dernier est négatif d'après l'hypothèse de récurence. \end{itemize} A chaque itération, l'intervalle $[a_n,b_n]$ est découpé @@ -221,9 +219,9 @@ Dans cet exercice, on suppose en plus que: \begin{enumerate} \item Montrer que l'on a $x_{n+1} \neq x_{n}$. \item Montrer que (\ref{eq:num:class}) est équivalente à -\begin{equation} +$ x_{n+1} = x_{n} - \frac{f(x_n)}{q_n} \label{eq:num:gen} -\end{equation} +$ \item Dans la représentation graphique donnée figure~\ref{fig:graphe1}: \begin{enumerate} \item donner l'équation de la droite tracée; @@ -234,14 +232,14 @@ x_{n+1} = x_{n} - \frac{f(x_n)}{q_n} \label{eq:num:gen} \end{enumerate} \item Dans la méthode de la corde, $q_n$ est constante et égale à -\begin{equation} -q_{n} = \frac{f(b) - f(a)}{b - a} \label{eq:num:corde} -\end{equation} +%\begin{equation} +$q_{n} = \frac{f(b) - f(a)}{b - a} \label{eq:num:corde} +$%\end{equation} \item Dans la méthode de Lagrange on a -\begin{equation} -q_{n} = \frac{f(x_{n}) - f(x_{n-1})}{x_n - x_{n-1}} \label{eq:num:lagrange} -\end{equation} +%\begin{equation} +$q_{n} = \frac{f(x_{n}) - f(x_{n-1})}{x_n - x_{n-1}} \label{eq:num:lagrange} +$%\end{equation} \item Dans la méthode de Newton on a $q_n = f'(x_n)$ \end{enumerate} @@ -282,6 +280,8 @@ solution $\alpha$ de cet intervalle. \begin{Prop}[Vitesse de convergence] +Si la suite des itérés obtenus par dichotomie converge, +alors la convergence est linéaire. Si la suite des itérés de Lagrange converge, alors la convergence est d'ordre $(1+\sqrt{5})/2$. Si la suite des itérés de Newton converge, @@ -310,6 +310,67 @@ fixe $g_i(x) =x$ avec \end{itemize} + +\begin{TP}[Comparaison d'approches] + +\begin{enumerate} +\item Écrire la fonction +\verb+[n,X] = iteration_dichotomie(a,b,m,epsilon,f)+ où +\begin{itemize} +\item \verb+a+, \verb+b+ sont les bornes de l'intervalle, \verb+m+ + est le nombre maximal + d'itérations, \texttt{epsilon} est la précision souhaitée + (voir équation (\ref{eq:erreur:epsilon})) et \verb+f+ la fonction à itérer; +\item \verb+n+ est le nombre d'itérations réalisées pour que +\verb+f(+$\verb+x+_{\verb+n+}$\verb+)+=0 ou que +$|\verb+x+_{\verb+n+}- \verb+x+_{\verb+n-1+}| \leq \verb+epsilon+$, \verb+n+ étant inférieur à \verb+m+ et \verb+X+ est + le vecteur contenant les + valeurs $\verb+x+_{\verb+0+},\ldots,\verb+x+_{\verb+n+}$. +\end{itemize} +\item Écrire la fonction +\verb+[n,X] = iteration_corde(a,b,+$\verb+x+_{\verb+0+}$\verb+,m,epsilon,f)+ où +\begin{itemize} +\item $\verb+x+_{\verb+0+}$ est le premier terme de la suite; +\end{itemize} +\item Écrire la fonction +\verb+[n,X] = iteration_Newton(+$\verb+x+_{\verb+0+}$\verb+,m,epsilon,f)+. +\end{enumerate} +\end{TP} + + +\begin{TP} +L'objectif du TP est de mesurer l'ordre de grandeur de la convergence d'une +méthode. +On suppose que la suite $(x_n)$ converge vers $l$ avec l'ordre $p\geq 1$. +On note $e_n= l -x_n$. On a $|e_{n+1}| \approx c |e_n|^p$ et donc +$\ln(|e_{n+1}|) \approx p \ln(|e_n|) + \ln(c)$. +En posant $y = \ln(|e_{n+1}|)$, $x = \ln(|e_n|)$ et $k = \ln(c)$ on a +$y = px + k$ soit l'équation d'une droite de pente $p$. +Pour estimer $p$, on peut donc tracer l'ensemble de points +$(\ln(|e_{n}|),\ln(|e_{n+1}|))$, contruire la droite de regression linéaire +et prendre son coefficient directeur. + +\begin{enumerate} +\item Construire la méthode +\verb+p=ordre_convergence(X,l)+ telle que +\begin{itemize} +\item \texttt{X} est le vecteur contenant les valeurs des itérés $\verb+x+_{\verb+0+}$, \ldots, $\verb+x+_{\verb+n+}$ et + \verb+l+ est la limite présumée de la suite; +\item cette fonction exploite la fonction +\verb+scipy.stats.linregress(x, y=None)+; +\item \verb+p+ est l'ordre de convergence calculé numériquement. +\end{itemize} + +\item Tester les méthodes du TP précédent + (dichotomie, corde, Lagrange, Newton) pour la fonction + $f$ définie par $f(x)=\cos(x)-x$ sur $[0,\pi/2]$. + Calculer l'ordre à l'aide de la fonction développée à la première question. +\item Comparer avec la fonction \verb+scipy.optimize.newton+. +\end{enumerate} +\end{TP} + + + \subsection{Algorithme du point fixe} L'algorithme du point fixe donné ci dessous (Algorithme~\ref{algo:pf}) est une version constructive de la suite $(x_n)$ définie par $x_0$ et pour tout $n \in \N$, @@ -358,7 +419,7 @@ Pour chacune des équations suivantes, étudier la convergence de la suite des itérés du point fixe pour un $x_0$ choisi dans l'intervalle proposé. \begin{enumerate} \item fonction $g_3$ de Ferrari sur $[2;4]$; -\item fonction $g_2$ de Ferrari sur $[3;\textrm{3,1}]$; +\item fonction $g_2$ de Ferrari sur $[3;\textrm{3,1}]$. \end{enumerate} \end{Exo} @@ -376,62 +437,5 @@ proposition~\ref{th:csconv:pf} sont suffisantes, pas nécessaires. \end{enumerate} \end{Exo} -\begin{TP} -Tout le code suivant est à faire en python. -\begin{enumerate} -\item Écrire la fonction -\verb+[n,X] = iteration_dichotomie(a,b,m,epsilon,f)+ où -\begin{itemize} -\item \verb+a+, \verb+b+ sont les bornes de l'intervalle, \verb+m+ - est le nombre maximal - d'itérations, \texttt{epsilon} est la précision souhaitée - (voir équation (\ref{eq:erreur:epsilon})) et \verb+f+ la fonction à itérer; -\item \verb+n+ est le nombre d'itérations réalisées pour que -\verb+f(+$\verb+x+_{\verb+n+}$\verb+)+=0 ou que -$|\verb+x+_{\verb+n+}- \verb+x+_{\verb+n-1+}| \leq \verb+epsilon+$, \verb+n+ étant inférieur à \verb+m+ et \verb+X+ est - le vecteur contenant les - valeurs $\verb+x+_{\verb+0+},\ldots,\verb+x+_{\verb+n+}$. -\end{itemize} -\item Écrire la fonction -\verb+[n,X] = iteration_corde(a,b,+$\verb+x+_{\verb+0+}$\verb+,m,epsilon,f)+ où -\begin{itemize} -\item $\verb+x+_{\verb+0+}$ est le premier terme de la suite; -\end{itemize} -\item Écrire la fonction -\verb+[n,X] = iteration_Newton(+$\verb+x+_{\verb+0+}$\verb+,m,epsilon,f)+. -\end{enumerate} -\end{TP} - - -\begin{TP} -L'objectif du TP est de mesurer l'ordre de grandeur de la convergence d'une -méthode. -On suppose que la suite $(x_n)$ converge vers $l$ avec l'ordre $p\geq 1$. -On note $e_n= l -x_n$. On a $|e_{n+1}| \approx c |e_n|^p$ et donc -$\ln(|e_{n+1}|) \approx p \ln(|e_n|) + \ln(c)$. -En posant $y = \ln(|e_{n+1}|)$, $x = \ln(|e_n|)$ et $k = \ln(c)$ on a -$y = px + k$ soit l'équation d'une droite de pente $p$. -Pour estimer $p$, on peut donc tracer l'ensemble de points -$(\ln(|e_{n}|),\ln(|e_{n+1}|))$, contruire la droite de regression linéaire -et prendre son coefficient directeur. - -\begin{enumerate} -\item Construire la méthode -\verb+p=ordre_convergence(X,l)+ telle que -\begin{itemize} -\item \texttt{X} est le vecteur contenant les valeurs des itérés $\verb+x+_{\verb+0+}$, \ldots, $\verb+x+_{\verb+n+}$ et - \verb+l+ est la limite présumée de la suite; -\item cette fonction exploite la fonction -\verb+scipy.stats.linregress(x, y=None)+; -\item \verb+p+ est l'ordre de convergence calculé numériquement. -\end{itemize} - -\item Tester les méthodes du TP précédent - (dichotomie, corde, Lagrange, Newton) pour la fonction - $f$ définie par $f(x)=\cos(x)-x$ sur $[0,\pi/2]$. - Calculer l'ordre à l'aide de la fonction développée à la première question. -\item Comparer avec la fonction \verb+scipy.optimize.newton+. -\end{enumerate} -\end{TP} diff --git a/interpol.tex b/interpol.tex index b5eef1f..a3d0cda 100644 --- a/interpol.tex +++ b/interpol.tex @@ -74,11 +74,11 @@ $$p_i(x) = p_{i-1}(x) + d_i \left[ \prod_{j=0}^{i-1} (x - x_j)\right].$$ Ainsi pour obtenir $p$ sur $x_0$, $x_1$, \ldots, $x_n$, il suffit: \begin{itemize} -\item de calculer $d_0$, pour définir $p_0$ qui interpole $p$ sur $x_0$, -\item de calculer $d_1$, pour définir $p_1$ qui interpole $p$ sur $x_0$ +\item de calculer $d_0$, pour définir $p_0$ qui interpole $f$ sur $x_0$, +\item de calculer $d_1$, pour définir $p_1$ qui interpole $f$ sur $x_0$ et $x_1$, \item \ldots -\item de calculer $d_n$, pour définir $p_n$ qui interpole $p$ sur +\item de calculer $d_n$, pour définir $p_n$ qui interpole $f$ sur $x_0$, $x_1$, \ldots, $x_n$. \end{itemize} diff --git a/partiels/13mesi/main.log b/partiels/13mesi/main.log index 5f4531e..401fce1 100644 --- a/partiels/13mesi/main.log +++ b/partiels/13mesi/main.log @@ -1,4 +1,4 @@ -This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2013.11.3) 3 NOV 2013 21:53 +This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2013.11.3) 4 NOV 2013 10:10 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -8,8 +8,8 @@ LaTeX2e <2011/06/27> Babel <3.9f> and hyphenation patterns for 4 languages loaded. (/usr/share/texlive/texmf-dist/tex/latex/base/article.cls Document Class: article 2007/10/19 v1.4h Standard LaTeX document class -(/usr/share/texlive/texmf-dist/tex/latex/base/size10.clo -File: size10.clo 2007/10/19 v1.4h Standard LaTeX file (size option) +(/usr/share/texlive/texmf-dist/tex/latex/base/size11.clo +File: size11.clo 2007/10/19 v1.4h Standard LaTeX file (size option) ) \c@part=\count79 \c@section=\count80 @@ -1100,12 +1100,12 @@ e * \topmargin=-80.81725pt * \headheight=12.0pt * \headsep=25.0pt -* \topskip=10.0pt +* \topskip=11.0pt * \footskip=30.0pt * \marginparwidth=72.26999pt -* \marginparsep=11.0pt +* \marginparsep=10.0pt * \columnsep=10.0pt -* \skip\footins=9.0pt plus 4.0pt minus 2.0pt +* \skip\footins=10.0pt plus 4.0pt minus 2.0pt * \hoffset=0.0pt * \voffset=0.0pt * \mag=1000 @@ -1162,24 +1162,24 @@ False_position_method.pdf>] [2] (./main.aux) ) Here is how much of TeX's memory you used: - 10017 strings out of 495002 - 150021 string characters out of 6180262 - 301242 words of memory out of 5000000 - 12956 multiletter control sequences out of 15000+600000 - 13949 words of font info for 48 fonts, out of 8000000 for 9000 + 10013 strings out of 495002 + 150022 string characters out of 6180262 + 301263 words of memory out of 5000000 + 12954 multiletter control sequences out of 15000+600000 + 13798 words of font info for 46 fonts, out of 8000000 for 9000 14 hyphenation exceptions out of 8191 44i,6n,64p,565b,257s stack positions out of 5000i,500n,10000p,200000b,80000s {/usr/share/texlive/texmf-dist/fonts/enc/dvips/base/8r.enc}< /usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi10.pfb> -Output written on main.pdf (2 pages, 113686 bytes). +Output written on main.pdf (2 pages, 113815 bytes). PDF statistics: 58 PDF objects out of 1000 (max. 8388607) 40 compressed objects within 1 object stream diff --git a/partiels/13mesi/main.pdf b/partiels/13mesi/main.pdf index 4268ee4..0060fb7 100644 Binary files a/partiels/13mesi/main.pdf and b/partiels/13mesi/main.pdf differ diff --git a/partiels/13mesi/main.tex b/partiels/13mesi/main.tex index e8c2577..5ed0b08 100644 --- a/partiels/13mesi/main.tex +++ b/partiels/13mesi/main.tex @@ -1,4 +1,4 @@ -\documentclass[10pt,a4paper,french]{article} +\documentclass[11pt,a4paper,french]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage{a4} @@ -29,7 +29,7 @@ Novembre 2013 (durée 45 mn). J.-F. Couchot,} \maketitle -\vspace{-5em} +\vspace{-3em} % \begin{tabular}{ll} % Nom:& ........................................\\ % Prénom:& ........................................\\ @@ -82,31 +82,35 @@ Vos réponses seront données directement ci-dessous. \item (2pts) Montrer que l'équation de la droite $(D_n)$ est $y - f(b_n) = \frac{f(b_n)-f(a_n)}{b_n-a_n} (x-b_n)$. -\vspace{4cm} +\vspace{3cm} \item (2pts) Montrer que le nombre $x_n$ est donné par l'équation $x_n = a_n - \frac{a_n-b_n}{f(a_n)-f(b_n)} f(a_n)$. -\vspace{4cm} +\vspace{3cm} \item (2pts) En moyenne, l'ordre de cette méthode est 1,618. Comparer cet ordre avec celui des autres méthodes du cours. -\vspace{4cm} +\vspace{3cm} \item (5pts) Quelle partie de cette méthode est commune avec la méthode par dichotomie? Est-elle toujours plus efficace? - Comparer les approches par exemple - sur l'intervalle $[-1,1]$ avec fonction $f$ définie sur $\mathds{R}$ par + Comparer les deux approches par exemple + sur l'intervalle $[-1,1]$ avec la fonction $f$ définie sur $\mathds{R}$ par $f(x)= 2x^3-4x^2+3x$. \vspace{6cm} +\newpage +\vspace{5cm} \item (4pts) Quelle partie de cette méthode est commune avec la méthode de Lagrange? Est-ce la même méthode? Si ce n'est pas le cas, Expliquer ce qui diffère. \vspace{4cm} -\item (5pts) Donner le code d'un programme qui implanterait cette méthode. +\item (5pts) Donner le code d'un programme qui implanterait cette méthode, + et ce dans le langage de votre choix. + \vspace{4cm} diff --git a/partiels/main.tex b/partiels/main.tex deleted file mode 100644 index 57c391d..0000000 --- a/partiels/main.tex +++ /dev/null @@ -1,117 +0,0 @@ -\documentclass[10pt,a4paper,french]{article} -\usepackage[francais]{babel} -\usepackage[utf8]{inputenc} -\usepackage{a4} -\usepackage{amsmath} -\usepackage{amsfonts} -\usepackage{amssymb} -\usepackage{framed} -\usepackage{dsfont} -\usepackage[amsmath,thmmarks,thref,framed]{ntheorem} -\usepackage[dvips]{graphics} -\usepackage{epsfig} -\usepackage{calc} -\usepackage{tabls} -\usepackage{slashbox} -\usepackage{times} -\usepackage{multicol} -\usepackage{tabularx} -\usepackage{textcomp} - -\usepackage{pst-all} - -\usepackage[a4paper]{geometry} - - -\date{} -\geometry{hmargin=1cm, tmargin=1cm,bmargin=1.5cm} -\begin{document} -\title{UE MESI, Master IMR 2ème année.\\ - Novembre 2012 (durée 1h). J.-F. Couchot,} - -\maketitle -\vspace{-5em} -\begin{tabular}{ll} -Nom:& ........................................\\ -Prénom:& ........................................\\ -\end{tabular} - - -On s'intéresse à résoudre une équation de la forme $f(x)=0$ par la -méthode de Müller. Dans cette méthode, on considère que l'on -a le triplet de points $(x_{n-2},x_{n-1},x_{n})$. Pour calculer -$x_{n+1}$, on fait comme suit: -\begin{enumerate} -\item \label{itm:1} on approche $f(x)$ par un polynôme $P(x)$ aux points - $(x_{n-2},x_{n-1},x_{n})$, -\item\label{itm:2} on résout l'équation $P(x)=0$. La racine la plus proche de $x_n$ est $x_{n+1}$; -\item on recommence avec le triplet $(x_{n-1},x_{n},x_{n+1})$\ldots -\end{enumerate} - - - - - - -Vos réponses seront données directement ci-dessous. - -\begin{enumerate} - -\item En utilisant une base de Lagrange, montrer que le polynôme $P(x)$ - obtenu à l'étape 1. de la première itération est défini par -$$ -P(x) = \dfrac{(x-x_{n-1})(x-x_{n-2})f(x_n)}{(x_n-x_{n-1})(x_n-x_{n-2})} + -\dfrac{(x-x_{n})(x-x_{n-2})f(x_{n-1})}{(x_{n-1}-x_{n})(x_{n-1}-x_{n-2})} + -\dfrac{(x-x_{n})(x-x_{n-1})f(x_{n-2})}{(x_{n-2}-x_{n})(x_{n-2}-x_{n-1})} -$$ - -\vspace{4cm} - -\item Montrer que le polynôme de la question précédente est de degré 2. - Est-ce cohérent avec le fait qu'on veuille approximer $f$ en trois points? -\vspace{4cm} - -\item Montrer que le polynôme de la première question peut s'écrire - sous la forme $P(x) = a_n x^2 + b_n x + c $ où -\begin{eqnarray*} -a_n & = & \dfrac{f(x_n)}{(x_n-x_{n-1})(x_n-x_{n-2})} + -\dfrac{f(x_{n-1})}{(x_{n-1}-x_{n})(x_{n-1}-x_{n-2})} + -\dfrac{f(x_{n-2})}{(x_{n-2}-x_{n})(x_{n-2}-x_{n-1})} \\ -b_n & = &-\dfrac{f(x_n)(x_{n-1}+x_{n-2})}{(x_n-x_{n-1})(x_n-x_{n-2})} - -\dfrac{f(x_{n-1})(x_{n}+x_{n-2})}{(x_{n-1}-x_{n})(x_{n-1}-x_{n-2})} - -\dfrac{f(x_{n-2})(x_{n}+x_{n-1})}{(x_{n-2}-x_{n})(x_{n-2}-x_{n-1})} \\ -c_n & = & \dfrac{f(x_n)x_{n-1}x_{n-2}}{(x_n-x_{n-1})(x_n-x_{n-2})} + -\dfrac{f(x_{n-1})x_{n}x_{n-2}}{(x_{n-1}-x_{n})(x_{n-1}-x_{n-2})} + -\dfrac{f(x_{n-2})x_{n}x_{n-1}}{(x_{n-2}-x_{n})(x_{n-2}-x_{n-1})} -\end{eqnarray*} -\vspace{8cm} - - -\item Exprimer les deux racines $x'_{n}$ et $x''_{n}$ du polynôme précédent -en fonctions de $a_n$, $b_n$ et $c_n$ lorsqu'on itère dans les réels. -\vspace{3cm} - -\item Comment est alors défini $x_{n+1}$? -\vspace{3cm} - -\item On pourrait montrer que l'ordre de la convergence est 1,84. Comparer cette vitesse de convergence avec celle de Newton et celle de Lagrange. -\vspace{3cm} - - -\item Donner le code Python de la fonction - $\verb+[n,X] = iteration_muller(x+_{\verb+0+},\verb+x+_{\verb+1+},\verb+x+_{\verb+2+}\verb+,m,epsilon,f)+$ où -\begin{itemize} -\item $\verb+x+_{\verb+0+}$, $\verb+x+_{\verb+1+}$ et $\verb+x+_{\verb+2+}$ sont les trois premières valeurs des itérés, \verb+m+ - est le nombre maximal - d'itérations, \texttt{epsilon} est la précision souhaitée - et \verb+f+ la fonction à itérer; -\item \verb+n+ est le nombre d'itérations réalisées pour que -\verb+f(+$\verb+x+_{\verb+n+}$\verb+)+=0 ou que -$|\verb+x+_{\verb+n+}- \verb+x+_{\verb+n-1+}| \leq \verb+epsilon+$, \verb+n+ étant inférieur à \verb+m+ et \verb+X+ est - le vecteur contenant les - valeurs $\verb+x+_{\verb+0+},\ldots,\verb+x+_{\verb+n+}$. -\end{itemize} -\end{enumerate} - - -\end{document} \ No newline at end of file diff --git a/tps/chap2/diff_div.py b/tps/chap2/diff_div.py index 8ac41e3..a2c7573 100644 --- a/tps/chap2/diff_div.py +++ b/tps/chap2/diff_div.py @@ -4,12 +4,12 @@ from math import * def coeffs(X,Y): - n = len(X)-1 - diff_div=[[0 for _ in xrange(n+1)] for _ in xrange(n+1)] - for i in xrange(n+1): + n = len(X) + diff_div=np.zeros((n,n)) + for i in range(n): diff_div[i][0] = Y[i] - for j in xrange(1,n+1): - for i in xrange(n-j+1): + for j in range(1,n): + for i in range(n-j): r = float(diff_div[i+1][j-1]-diff_div[i][j-1])/(X[i+j]-X[i]) diff_div[i][j] = r print diff_div @@ -34,6 +34,7 @@ def construit_et_eval_pol(X,Y,x): def construit_pol(X,Y): d = coeffs(X,Y) + print "les coeffs sont",d n = len(X)-1 return lambda x : \ sum([d[i]*prod([x - X[j] for j in xrange(i)]) for i in xrange(n+1)]) @@ -41,17 +42,18 @@ def construit_pol(X,Y): -""" + print "tp 2.1....." X = [10,25,60] XX= [15,40,100] Y = [2.3, 8, 24.6] p = construit_pol(X,Y) + Yp =[p(x) for x in XX] Ypp = [construit_et_eval_pol(X,Y,x) for x in XX] -print Yp, Ypp +print "Yp", Yp#, Ypp x=np.linspace(10,100,100) @@ -106,4 +108,4 @@ plt.ylabel('exp') plt.xlabel("x") plt.show() - +""" diff --git a/tps/chap3/jjm.py~ b/tps/chap3/jjm.py~ deleted file mode 100644 index da9ef8b..0000000 --- a/tps/chap3/jjm.py~ +++ /dev/null @@ -1,23 +0,0 @@ -def iteration_lagrange(x0, q0, m, epsilon, f): - def maj_test(xn,xnm1): - return f(xn)!=0 and abs(xn-xnm1)>epsilon - - n=0 - test=f(x0)!=0 - X=[x0] - xnm1=x0 - xn=float(x0-f(x0))/q0 - qn=q0 - print(xn,q0) - while n<=m and test: - qn=float((f(xn)-f(xnm1)))/(xn-xnm1) - xnm1=xn - xn=xnm1-f(xnm1)/qn - - X+=[xn] - test=maj_test(xn,xnm1) - n+=1 - return (n,X) - -//////////////////////////////////////////////////////////////////////////// -print(iteration_lagrange(pi/4,1,200,0.0000001,f)) diff --git a/tps/chap3/methodes.py b/tps/chap3/methodes.py index 8ae3b71..9c9424e 100644 --- a/tps/chap3/methodes.py +++ b/tps/chap3/methodes.py @@ -16,79 +16,61 @@ def fp(x): def iteration_dichotomie(a,b,m,epsilon,f): - def maj_test(xn,xnm1): - return f(xn) != 0 and abs(xnm1-xn) > epsilon - xnm1 = a - xn= a + def maj_test(xn,xnm1,n,m): + return f(xn) == 0 or abs(xnm1-xn) <= epsilon or n >= m + xn= float(a) + xnm1 =float(b) X=[] - n = 1 - an= a - bn=b - test = True - while n <= m and test: + n = 0 + an= float(a) + bn=float(b) + test = maj_test(xn,xnm1,n,m) + while not test: xnm1 = xn xn=float(an+bn)/2 - test = maj_test(xn,xnm1) X +=[xn] if f(an)*f(xn)<=0 : bn=xn else : an=xn n +=1 + test = maj_test(xn,xnm1,n,m) return (n,X) def iteration_newton(x0,m,epsilon,f,fp): - def maj_test(xn,xnm1): - return f(xn) != 0 and abs(xnm1-xn) > epsilon - n=0; - test= f(x0) != 0 - xn=x0 - X=[x0] - while n < m and test: + def maj_test(xn,xnm1,epsilon,n,m,f): + return f(xn) == 0 or abs(xnm1-xn) <= epsilon or n >= m + n = 0 + xn = float(x0) + X = [x0] + test = maj_test(xn,xn+2*epsilon,epsilon,n,m,f) + while not test: qn=fp(xn) xnm1=xn xn= xn-f(xn)/qn X += [xn] n=n+1 - test= maj_test(xn,xnm1) - -#f(x) !=0 and nepsilon + test= maj_test(xn,xnm1,epsilon,n,m,f) return (n,X) def iteration_corde(a,b,x0,m,epsilon,f): - def maj_test(xn,xnm1): - return f(xn) != 0 and abs(xnm1-xn) > epsilon - n=0; + def maj_test(xn,xnm1,n,m,f): + return f(xn)== 0 or abs(xnm1-xn) <= epsilon or n >= m + n=0 q=float(f(b)-f(a))/(b-a) - test= f(x0) != 0 - xn=x0 - X=[x0] - while n < m and test: + xnm1 = float(b) + xn=float(x0) + test= maj_test(xn,xnm1,n,m,f) + X=[float(x0)] + while not test: xnm1=xn - xn= xn-f(xn)/q + xn= xn-float(f(xn))/q X += [xn] n=n+1 - test= maj_test(xn,xnm1) - -#f(x) !=0 and nepsilon + test= maj_test(xn,xnm1,n,m,f) return (n,X) -"""def iteration_newton(x0,m,epsilon,f,fp): - n=0; - delta=float(1)/fp(x0) - test= f(x0) != 0 - x=x0 - X=[x0] - while(test): - xm1=x - x= x-delta*f(x) - delta=float(1)/fp(x) - X += [x] - n=n+1 - test= not (f(x)==0 or n>=m or abs(x-xm1)<=epsilon) - return (n,X) -""" def iteration_lagrange(x0,x1,m,epsilon,f): n=0; @@ -138,24 +120,24 @@ def iteration_muller(x0,x1,x2,m,epsilon,f): def main(): print "TP 3.1 ............ dichotomie" - print iteration_dichotomie(0,pi/2,200,0.00000001,f) + print iteration_dichotomie(0,pi/2,45,1E-9,f) - print "TP 3.1 ............ corde" - print iteration_corde(0,pi/2,0,200,0.00000001,f) - + print iteration_corde(0,pi/2,0,200,1E-9,f) print "TP 3.1 ............ newton" - print iteration_newton(0,200,0.00000001,f,fp) + print iteration_newton(0,200,1E-9,f,fp) + +""" print "TP 3.1 ............ lagrange" print iteration_lagrange(0,pi/2,200,0.00000001,f) print "TP 3.1 ............ muller" print iteration_muller(0,pi/4,pi/2,200,0.00000001,f) - +""" if __name__ == '__main__': main() diff --git a/tps/chap3/methodes.pyc b/tps/chap3/methodes.pyc index 29f025b..92edf69 100644 Binary files a/tps/chap3/methodes.pyc and b/tps/chap3/methodes.pyc differ diff --git a/tps/chap3/methodes.py~ b/tps/chap3/methodes.py~ deleted file mode 100644 index c7080e2..0000000 --- a/tps/chap3/methodes.py~ +++ /dev/null @@ -1,128 +0,0 @@ -import matplotlib.pyplot as plt -import numpy as np -from math import * - - - - - -def f(x): - return cos(x)-x - -def fp(x): - return -sin(x)-1 - - - - -def iteration_dichotomie(a,b,m,epsilon,f): - def maj_test(xn,xnm1): - return f(xn) != 0 and abs(xnm1-xn) > epsilon - xnm1 = a - xn= a - X=[] - n = 1 - an= a - bn=b - test = True - while n <= m and test: - xnm1 = xn - xn=float(an+bn)/2 - test = maj_test(xn,xnm1) - X +=[xn] - if f(an)*f(xn)<=0 : - bn=xn - else : - an=xn - n +=1 - return (n,X) - -def iteration_newton(x0,m,epsilon,f,fp): - def maj_test(xn,xnm1): - return f(xn) != 0 and abs(xnm1-xn) > epsilon - n=0; - test= f(x0) != 0 - xn=x0 - X=[x0] - while n < m and test: - qn=fp(xn) - xnm1=xn - xn= xn-f(xn)/qn - X += [xn] - n=n+1 - test= maj_test(xn,xnm1) - -#f(x) !=0 and nepsilon - return (n,X) - - -def iteration_corde(a,b,x0,m,epsilon,f): - def maj_test(xn,xnm1): - return f(xn) != 0 and abs(xnm1-xn) > epsilon - n=0; - q=float(f(b)-f(a))/(b-a) - test= f(x0) != 0 - xn=x0 - X=[x0] - while n < m and test: - xnm1=xn - xn= xn-f(xn)/q - X += [xn] - n=n+1 - test= maj_test(xn,xnm1) - -#f(x) !=0 and nepsilon - return (n,X) - -"""def iteration_newton(x0,m,epsilon,f,fp): - n=0; - delta=float(1)/fp(x0) - test= f(x0) != 0 - x=x0 - X=[x0] - while(test): - xm1=x - x= x-delta*f(x) - delta=float(1)/fp(x) - X += [x] - n=n+1 - test= not (f(x)==0 or n>=m or abs(x-xm1)<=epsilon) - return (n,X) -""" - -def iteration_lagrange(x0,x1,m,epsilon,f): - n=0; - delta=float(x1-x0)/(f(x1)-f(x0)) - test= f(x0) != 0 - x=x1 - X=[x1] - while(test): - xm1=x - x= x-delta*f(x) - delta=float(x-xm1)/(f(x)-f(xm1)) - X += [x] - n=n+1 - test= not (f(x)==0 or n>=m or abs(x-xm1)<=epsilon) - return (n,X) - - -def main(): - print "TP 3.1 ............ dichotomie" - print iteration_dichotomie(0,pi/2,200,0.00000001,f) - - - print "TP 3.1 ............ corde" - print iteration_corde(0,pi/2,0,200,0.00000001,f) - - - print "TP 3.1 ............ newton" - print iteration_newton(0,200,0.00000001,f,fp) - - - print "TP 3.1 ............ lagrange" - print iteration_lagrange(0,pi/2,200,0.00000001,f) - - -if __name__ == '__main__': - main() - diff --git a/tps/chap3/ordre.py b/tps/chap3/ordre.py index 95517ff..00283a8 100644 --- a/tps/chap3/ordre.py +++ b/tps/chap3/ordre.py @@ -22,16 +22,17 @@ def ordre_convergence(X,l=None) : def main(): - print "TP 3.2 ............ ordre convergence corde" - print ordre_convergence(iteration_corde(0,pi/2,0,200,0.00000001,f)[1]) + print "TP 4.2 ............ ordre convergence corde" + print ordre_convergence(iteration_corde(0,pi/2,0,200,1E-9,f)[1]) - print "TP 3.2 ............ ordre convergence newton" - print ordre_convergence(iteration_newton(0,200,0.00000001,f,fp)[1]) + print "TP 4.2 ............ ordre convergence lagrange" + print ordre_convergence(iteration_lagrange(0,pi/2,200,1E-9,f)[1]) - print "TP 3.1 ............ ordre convergence lagrange" - print ordre_convergence(iteration_lagrange(0,pi/2,200,0.00000001,f)[1]) + print "TP 4.2 ............ ordre convergence newton" + print ordre_convergence(iteration_newton(0,200,1E-9,f,fp)[1]) + if __name__ == '__main__':