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}
\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}}
\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}
\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
$
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
$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
\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é
\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;
\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}
\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,
\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$,
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}
\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}
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}
-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.
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
* \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
[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></usr/s
-hare/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi5.pfb></usr/share/te
-xlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi7.pfb></usr/share/texlive/t
+hare/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi6.pfb></usr/share/te
+xlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi8.pfb></usr/share/texlive/t
exmf-dist/fonts/type1/public/amsfonts/cm/cmr10.pfb></usr/share/texlive/texmf-di
-st/fonts/type1/public/amsfonts/cm/cmr7.pfb></usr/share/texlive/texmf-dist/fonts
+st/fonts/type1/public/amsfonts/cm/cmr8.pfb></usr/share/texlive/texmf-dist/fonts
/type1/public/amsfonts/cm/cmsy10.pfb></usr/share/texlive/texmf-dist/fonts/type1
-/public/amsfonts/cm/cmsy7.pfb></usr/share/texlive/texmf-dist/fonts/type1/public
+/public/amsfonts/cm/cmsy8.pfb></usr/share/texlive/texmf-dist/fonts/type1/public
/doublestroke/dsrom10.pfb></usr/share/texlive/texmf-dist/fonts/type1/urw/times/
utmr8a.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
-\documentclass[10pt,a4paper,french]{article}
+\documentclass[11pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
Novembre 2013 (durée 45 mn). J.-F. Couchot,}
\maketitle
-\vspace{-5em}
+\vspace{-3em}
% \begin{tabular}{ll}
% Nom:& ........................................\\
% Prénom:& ........................................\\
\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}
+++ /dev/null
-\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
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
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)])
-"""
+
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)
plt.xlabel("x")
plt.show()
-
+"""
+++ /dev/null
-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))
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 n<m and abs(x-xm1)>epsilon
+ 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 n<m and abs(x-xm1)>epsilon
+ 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;
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()
+++ /dev/null
-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 n<m and abs(x-xm1)>epsilon
- 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 n<m and abs(x-xm1)>epsilon
- 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()
-
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__':
