\documentclass[10pt,a4paper]{article}
\parindent=0cm
 
   \textheight 24cm
   \textwidth 16cm
\oddsidemargin=0cm

\usepackage[frenchb]{babel}
\usepackage[utf8]{inputenc}


\usepackage{url,amsmath,amssymb,amsthm,amsfonts,epsfig,eurosym,geometry}
\selectlanguage{french}

\def\var{\mathrm{var}}
\def\BB{\mathcal{B}}
\def\FF{\mathcal{F}}
\def\Pa{\mathcal{P}}
\def\M{\mathcal{M}}
\def\P{\mathcal{P}}
\def\T{\mathcal{T}}
\def\L{\mathcal{L}}

\def\AA{\mathfrak{A}}
\def\S{\mathfrak{S}}
\def\SS{\mathcal{S}}
\def\CC{\mathcal{C}}

\def\A{\mathbb{A}}
\def\B{\mathbb{B}}
\def\D{\mathbb{D}}
\def\U{\mathbb{U}}


\def\bq{\begin{quote}\begin{em}}
\def\eq{\end{em}\end{quote}}

\def\un{\mathbf{1}}
\def\dd{\mathrm{d}}
\def\ee{\mathrm{e}}
\def\ii{\mathrm{i}}
\def\eps{\varepsilon}

\def\hth{\widehat{\theta}}
\def\ovx{\overline{X}}
\def\ima{\mathrm{Im}}

\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}

\newcommand{\espmes }{(\Omega, {\cal F})}
\newcommand{\espprob}{(\Omega, {\cal F}, P)}
\newcommand{\va}{variable al\'eatoire }
\newcommand{\vas}{variables al\'eatoires }
\newcommand{\Vas}{Variables al\'eatoires }
\newcommand{\cov}{\hbox{cov}}
\newtheorem{theo}{Théorème}[section]
\newtheorem{coro}{Corollaire}[section]
\newtheorem{lemm}{Lemme}[section]
\newtheorem{defi}[theo]{Définition}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{rque}[theo]{Remarque}
\newtheorem{exem}[theo]{Exemple}
\newtheorem{exer}{Exercice}
\def\card{\mathrm{card}\,}

\newcommand{\tran}[1]{\,{}^{t}\!#1}
\renewcommand\det{\mathop{\textrm{d\'et}}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\def\demi{\frac{1}{2}}
\def\ds{\displaystyle}
\def\btheo{\begin{theo}}\def\etheo{\end{theo}}
\def\bcoro{\begin{coro}}\def\ecoro{\end{coro}}
\def\blemm{\begin{lemm}}\def\elemm{\end{lemm}}
\def\bdefi{\begin{defi}}\def\edefi{\end{defi}}
\def\bprop{\begin{prop}}\def\eprop{\end{prop}}
\def\brque{\begin{rque}}\def\erque{\end{rque}}
\def\bexem{\begin{exem}}\def\eexem{\end{exem}}

\def\bexer{\begin{exer}\begin{em}}\def\eexer{\end{em}\end{exer}}
\usepackage{graphics}
\usepackage{color}              % Need the color package
\usepackage{epsfig}
\def\F{{\cal F}}
\def\1{{\rm 1\kern-.8ex 1}}
\def\euro{\mbox{\raisebox{.25ex}{{\it =}}\hspace{-.5em}{\sf C}}} 
\newcommand{\bin}[2]{\left( \begin{array}{c} 
#1 \\#2\end{array}\right)}

\begin{document}
%\Large
\noindent Intro mod\'elisation num\'erique \hfill Point fixe, Newton, puissance \hfill {L3 2016/2017}\\

\bexer
On utilise la m\'ethode de dichotomie pour r\'esoudre une \'equation
$f(x)=0$ avec $x\in[a,b]$. On veut une approximation d'une solution
\`a $\varepsilon>0$ pr\`es. Montrer qu'on aura besoin d'au plus
$\left\lceil \ln_2(b-a)-\ln_2\varepsilon \right\rceil$  it\'erations
de l'algorithme, o\`u $\lfloor x\rfloor$ et $\lceil x \rceil$
d\'esignent respectivement le plus grand entier inf\'erieur \`a $x$ et
le plus petit entier sup\'erieur \`a $x$. \\
Comparer avec
une m\'ethode de point fixe $g(x)=x$ (telle que $f(x)=0 $ \'equivaut
\`a $g(x)=x$) de constante de contractance $k<1$.\\
Exemple on prendra $g(x)=\cos(x)$ sur $[0,1]$.
\eexer

\bexer Méthode de Newton-Heron\\
Soit $a>0$ et $n$ un entier supérieur ou égal à 2. Appliquer la
m\'ethode de Newton pour d\'eterminer une valeur approch\'ee
de $a^{\frac{1}{n}}$. On donnera une valeur de d\'epart $u_0$
de la suite qui garantit la convergence.\\
Illuster pour $n=2, n=3$ et $a=2, a=3$.
Donner une majoration de l'erreur pour $u_4$ et $u_5$ lorsque $u_0=a$.
\eexer

\bexer

Soit $f:\R\rightarrow\R, x\mapsto \mbox{arctan(x)}$.

L'équation $f(x)=0$ a une unique solution $0$.

Pour quelles valeurs de $x_0$ la méthode de Newton converge-t'elle ?
\eexer

\bexer Vitesse de convergence quadratique, d'ordre $p$.\\
On dit que la suite converge avec une {\it vitesse d'ordre au moins
  $p$}  s'il existe $C>0$ tel que ${|x_{n+1}-x|}\leq C{|x_{n}-x|^p}$
\`a partir d'un certain rang.
Comment se comporte le nombre de d\'ecimales exactes d'une suite
convergent \`a vitesse au moins $p$ lorsque $p>1$~?  Calculer le
nombre d'it\'erations n\'ecessaires pour obtenir une pr\'ecision de
$n$ d\'ecimales. Comparer avec une suite convergeant \`a vitesse
quadratique ou lin\'eaire. Dicuster l'int\'er\^et de telles m\'ethodes.
\eexer

\bexer M\'ethode de la s\'ecante~: si $f(a)$ et $f(b)$ sont
de signe oppos\'es, au lieu de faire une dichotomie, on prend
la corde reliant $(a,f(a))$ \`a $(b,f(b))$, $c$ l'abscisse de
l'intersection avec l'axe des $x$ puis on copie $b$ dans $a$ et $c$
dans $b$. Tester pour $f(x)=x^2-2$ sur $[1,2]$.
\eexer

\bexer
On consid\`ere les applications d\'efinies sur $\Omega=\R^2-\{0\}$ par 
$$ F(x,y)= (1+ \frac{1}{2}\sqrt{x^2+y^2},
1+\frac{1}{4}\sqrt[4]{x^4+y^4}), \quad
\Phi(x,y)= F(x,y)-(x,y)
$$
\begin{enumerate} 
\item Montrer que $F$ est de classe $C^{\infty}$ sur $\Omega$ et calculer $F'$.
\item Rappeler l'in\'egalit\'e des accroissements finis pour les applications de classe $C^1$ d\'efinies
sur un ouvert de $\R^2$. 
\item Montrer que la norme triple d'une matrice 
$A=\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array}\right)\in M_2(\R)$ relative \`a la norme euclidienne v\'erifie:
$|||A ||| \le \sqrt{a_{11}^2+ a_{12}^2+ a_{21}^2 +a_{22}^2}$
(indication~: utiliser Cauchy-Schwarz pour majorer chaque coordonn\'ee
de $A(x,y)$)
\item Montrer que $F$ est contractante sur $(\R^*_+)^2$. Indication~:
se ramener par homog\'en\'eit\'e en une variable et faire une \'etude
de fonction.
\item Montrer que $[1,+\infty[ \times [1,+\infty[$ est stable par $F$.
\item D\'eduire que la suite d\'efinie par $(x_0,y_0)=(1,1)$ et $(x_{n+1},y_{n+1})=F(x_n,y_n)$ converge vers $(\bar x,\bar y)\in \R^2$. 
\item Montrer que $\Phi'$ est inversible pour tout  $(x,y)\in \Omega$. 
\item La m\'ethode de Newton-Raphson pour r\'esoudre $\Phi(x,y)=(0,0)$ consiste \`a it\'erer une certaine application $N$. D\'ecrire explicitement $N$.
\item Observer la convergence de la suite $(x_k,y_k)_k$. 
\end{enumerate}

\eexer




\bexer

$\ $

Ecrire un programme it\'erant la m\'ethode de dichotomie et la
m\'ethode de Newton pour une fonction de $\R$ dans $\R$. 
L'utiliser pour calculer $\sqrt 2$. Tracer le nombre de d\'ecimales exactes en fonction du nombre d'it\'erations.\\
On appliquera ensuite la m\'ethode de Newton \`a la fonction $x\mapsto
\sin \pi x$ et 
on tracera le dixi\`eme it\'er\'e de la suite en fonction du point de 
d\'epart de l'algorithme. Qu'observez-vous~?
\eexer

\bexer
Utiliser la méthode de Newton pour résoudre $xe^{-x^2}=0$ d'une part
pour $x_0=0.52$ et d'autre part pour $x_0=0.42$.

\eexer
\bexer

$\ $

Dessiner le graphe des courbes planes d'\'equations
$x^2+y^3-x-y=0$ et $x^4+xy-y^2-2=0$ (on pourra utiliser la
commande \verb|implicitplot|). Combien y a-t-il de solutions au
syst\`eme (non-lin\'eaire) suivant $
\left\{ \begin{array}{l}
    x^2+y^3-x-y=0\\
    x^4+xy-y^2-2=0
\end{array}\right.?
 $

Donner une estimation grossi\`ere de chaque solution, puis raffiner
cette estimation en utilisant la m\'ethode de Newton.

Voir aussi les fonctions \verb|solve| (pour des syst\`emes
polynomiaux)  et \verb|fsolve| (approch\'e).
\eexer


\bexer
Soit $P$ une matrice transpos\'ee d'une matrice stochastique,
c'est-\`a-dire une matrice carr\'ee de taille $N$ dont les coefficients v\'erifient
$$ a_{ij} \in [0,1], \quad \sum_{i=1}^N a_{ij} =1 $$
la somme des coefficients d'une colonne donn\'ee vaut 1.\\
L'algorithme PageRank de Google construit une telle matrice \`a partir
du graphe connectant les pages web entre elles en posant
$a_{ij}=\frac{1}{n_j}$ si la page $j$ pointe vers la page $i$ et 0
sinon, avec $n_j$ le nombre de liens \'emis par la page $j$ (chaque lien
repr\'esente en quelque sorte un vote, dont le poids est pond\'er\'e
par le nombre de liens). Par
exemple
\[ P= \left(\begin{array}{ccccc}
0 & 0 & \frac{1}{4} & 0 & 0 \\
0 & 0 & \frac{1}{4} & 0 & 0 \\
\frac{1}{2} & 1 & 0 & \frac{1}{2} & 0 \\
0 & 0 & \frac{1}{4} & 0 & 0 \\
\frac{1}{2} & 0 & \frac{1}{4} & \frac{1}{2} & 1
\end{array}\right) \]
correspondrait \`a un web jouet de 5 pages
 o\`u la page 1 pointe vers les pages 3
et 5, la page 2 vers la page 3, la page 3 vers 1, 2, 4, 5, 
la page 4
vers les pages 3 et 5 et la page 5 vers elle-m\^eme.

On s'int\'eresse \`a l'\'equation~:
\[ r =(1-\alpha)Pr+\alpha \frac1N (1,...,1), \quad \alpha \in ]0,1[ \]
Dans PageRank $\alpha=0.15$ et
$r_j$ donne le rang de classement de la page $j$
\begin{enumerate}
\item D\'eterminer la norme de $P$ comme application lin\'eaire
de $\R^N$ dans $\R^N$ subordonn\'ee \`a la norme $L^1$ dans $\R^N$
$$ |||P|||_1 = \mbox{max}_{\{r/\|r\|_1=1\}} \|Pr\|_1, \quad
\|r\|_1=\sum_{j=1}^N |r_j| $$
\item En d\'eduire que la m\'ethode du point fixe permet
de r\'esoudre le probl\`eme.
\end{enumerate}
\eexer



{\bf Exercice 11 : Domaine de Gershgorin}\\
Soit $A\in {\cal M}_n(\C)$.
On note, pour $1\leq i\leq n$, $D_i$ la boule fermée dans $\C$ de 
centre $a_{i,i}$ et de rayon $\ds\sum_{j\not= i}|a_{i,j}|$.
Le domaine de Gershgorin, qu'on notera ${\cal G}(A)$ est la réunion des 
disques $D_i$ pour $1\leq i\leq n$.
Montrer que le spectre de $A$ est inclus dans ${\cal G}(A)$.

{\bf Exercice 12  (Méthode de la puissance)}\\
Soit $A=\left(\begin{array}{ccc}99&1&0\\1&100&1\\0&1&98\end{array}\right)$.
\begin{enumerate}
 \item Montrer que $A$ est diagonalisable et en utilisant l'exercice 
précédent que ses valeurs propres appartiennent à $[97,102]$.
\item Déterminer par la méthode de la puissance
une approximation de la plus grande valeur propre de $A$.

Pour ceci, on écrira une fonction qui donnera une valeur approchée 
de la plus grande valeur propre, une valeur approchée d'un 
vecteur propre associé et le nombre d'itérations utilisées 
pour ce calcul. La fonction aura comme argument une matrice carrée, 
un nombre d'iterations maximales (pour un test d'arrêt) 
et epsilon mesurant une erreur maximale.

\item Expliquer pourquoi en appliquant la méthode de la puissance à $A-97I_3$, 
on accélere la convergence.


\item Que se passe t-il si on applique la méthode de la puissance à 
$A-\gamma I_3$ si $\gamma$ est la valeur trouvée à la question 2) ?
\end{enumerate}

{\bf Exercice 13  (élimination)}\\
Soit $A$ une matrice réelle de taille $n$.
On suppose que les valeurs propres de $A$ notées $\{\lambda_1,\ldots,\lambda_n\}$ sont deux à deux distinctes et vérifient :
\[|\lambda_1|<|\lambda_2|<\cdots <|\lambda_n|\]
On note $u_i$ un vecteur propre associé à $\lambda_i$, pour $1\leq i\leq n$.
\begin{enumerate}
 \item Montrer que $\{\lambda_1,\ldots,\lambda_n\}$ sont les valeurs 
propres de $\ ^tA$.
On note $v_i$ un vecteur propre de $\ ^tA$ associé à $\lambda_i$, pour $1\leq i\leq n$.
\item Montrer que si $i\not= j$, $\langle u_i,v_j\rangle =0$.
(On pourra calculer $\langle Au_i,v_j\rangle$ de deux manières).\\
Montrer que pour tout $1\leq i\leq n$, $\langle u_i,v_i\rangle\not=0$.

\item Soit $B=A-\lambda_n\frac{u_n\ ^tv_n}{\langle u_n,v_n\rangle}$.
Montrer que les valeurs propres de $B$ sont 
$\{0,\lambda_1,\ldots,\lambda_{n-1}\}$.

\item Donner une méthode utilisant la méthode de la puissance appliquée 
plusieurs fois pour trouver des valeurs approchées des valeurs propres 
de A et de ses vecteurs propres.

L'appliquer à la matrice de l'exercice précédent.
\end{enumerate}

{\bf Exercice 14 (valeurs propres conjuguées)}\\
Si $A$ est une matrice réelle, sa plus grande valeur propre en module n'est
pas forcément réelle, $A$ peut avoir un couple de valeurs propres
complexes conjuguées de module maximal. On peut appliquer la
méthode de la puissance à un shift de $A$ dans le complexe, par
exemple $A-iI$, on peut aussi rester dans le réel en cherchant
une relation de récurrence approchée $u_{n+2}+au_{n+1}+bu_n$
(où $u_{n+1}=Au_n$ et $u_0$ aléatoire). Programmer les deux
méthodes et comparer l'efficacité avec une matrice aléatoire
réelle de taille 4 (non symétrique).

{\bf Exercice 15 (itérations inverses)} \\
Lorsqu'on a effectué quelques itérations de la méthode de la puissance,
on a une première approximation $\lambda$ 
de la valeur propre de module maximal.
Il peut alors être intéressant d'effectuer la méthode de la puissance
sur la matrice $(A-\lambda I)^{-1}$. Programmer cette méthode
et discuter les avantages (vitesse de convergence) et inconvénients
(précision du calcul de l'inverse). Testez sur l'une des matrices
de la feuille.

{\bf Exercice 16}\\
Utiliser la m\'ethode de la puissance pour d\'eterminer la norme
triple d'une matrice subordonn\'ee \`a la norme euclidienne.


{\bf Exercice 17}\\
Soit $A$ la matrice du laplacien discret de taille $n$ (2 sur la
diagonale et -1 sur les deux diagonales adjacentes).
On rappele que
$$u_k=(\sin(\frac{k\pi}{N+1}),...,
\sin(\frac{kj\pi}{N+1}),...,\sin(\frac{kN\pi}{N+1})) $$
est vecteur propre de $A$.
Appliquer la m\'ethode du gradient \`a pas constant pour
d\'eterminer les solutions du syst\`eme $Ax=b$ en
consid\'erant la fonctionnelle $J(x)=\frac12<Ax|x>-<b|x>$.
Quel valeur de pas peut-on prendre pour assurer la convergence~?
Comparer avec la m\'ethode de Jacobi.

{\bf Exercice 18}\\
Programmer la m\'ethode du gradient \`a pas constant pour trouver le
minimum de la fonction $f(x,y)=x^4-x^3+2xy+y^2-2y+1$. Illustrer du mieux
possible le chemin parcouru par les diff\'erentes \'etapes de l'algorithme.


{\bf Exercice 19}\\
Soit $J:\R^2\rightarrow\R$ définie par 
$$J((x_1,x_2))=\demi x_1^2+x_1\cos x_2$$
Illustrer sur cet exemple les méthodes de descente de gradient, à pas
fixe, à pas optimal
et la méthode de Newton pour les zéros du gradient.

On fera varier le pas pour le pas fixe, le point de départ.
On choisira un test d'arrêt $\|\nabla J(x)\|<10^{-6}$.
On comparera le nombre d'itérations pour chacune des méthodes.
On repr\'esentera graphiquement la suite des it\'er\'ees.


{\bf Exercice 20}\\
Utiliser la méthode QR pour trouver des valeurs approchées 
des valeurs propres de 
 \[A=\left(\begin{array}{ccccc}
0&1&0&0&0\\1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\0&0&0&1&2
\end{array}\right)\]
Observer la forme des matrices intermédiaires.
Pour une matrice g\'en\'erale, on utilise la forme de Hessenberg avant
de faire la m\'ethode QR.

{\bf Exercice 22}\\
Si $A$ est une matrice sym\'etrique, et si $\|(A-\lambda) u\| \leq
\varepsilon \| u\|$, montrer que la distance de $\lambda$ au spectre
de $A$ est inf\'erieure \`a $\varepsilon$ (on pourra utiliser une base
orthonormale de vecteurs propres de $A$).

\pagebreak
\noindent Intro mod\'elisation num\'erique \hfill Formulation
variationnelle \hfill {L3 2016/2017}\\


On consid\`ere l'\'equation diff\'erentielle 
$$ -u'{'}+\alpha u=f, \quad x \in [0,1], \quad u(0)=u(1)=0 $$
\begin{enumerate}
\item Discuter en fonction de $\alpha$ le nombre de solutions pour
  $f=0$. Comparer les conditions aux bords
avec le cas des conditions initiales $u(0)=0, u'(0)=0$.
\item On pose $\alpha>0$.
 D\'eterminer $a$ et $l$ de la formulation ``faible'' de cette \'equation
$ a(u,v)=l(v)$ pour tout $v$ de classe $C^1$ par morceaux nulle aux
bords.
\item Montrer que $a$ est sym\'etrique d\'efinie positive.
\item V\'erifier que la solution de $a(u,v)=l(v)$ est un extr\^emum
de  $J(u)=\frac12 a(u,u)-l(u)$ (formulation variationnelle de
l'\'equation diff\'erentielle).
\item Soit $N\geq2$, $h=1/N$ et $x_k=kh=k/N$ pour $k=0,..N$.\\
Pour $1\leq k \leq N-1$, on 
note $\phi_k(x)=\mbox{max}(0,1-|(x-x_k)/h|)$ la fonction 
atteignant son maximum 1 en $x_k$ et de
pente $\pm 1/h$ entre $[x_{k-1},x_{k+1}]$.\\
On va chercher le minimum de $J$ sur l'espace vectoriel
$E$ de dimension finie engendr\'e par les fonctions $\phi_k$
(c'est la projection orthogonale par rapport au produit scalaire 
induit par $a$ de la solution sur $E$, pourquoi~?)
D\'eterminer $a_{j,k}=a(\phi_j,\phi_k)$, $l_k=l(\phi_k)$.
\item Montrer que le minimum $u$ de $J$ sur $E$ v\'erifie $a(u,v)=l(v)$ pour
tout $v \in E$. En d\'eduire une matrice $A$ telle que
$A(u(x_j))_{j=1..N-1}=(l_j)_{j=1..N-1}$.
\item D\'eterminer $u(x_j)$ puis $u$.
\item Tracer sur une m\^eme figure $u$ et la solution exacte
pour $f(t)=1$ et pour $f(t)=t(1-t)$ pour $N=3$ et $N=10$.
\item Pour $N$ grand, quel est le cout de l'\'etape matricielle de la r\'esolution
par le pivot de Gauss~? Comparer avec la m\'ethode de Jacobi.
\item Que faut-il modifier lorsque $\alpha$ d\'epend de $x$~?
Comment se compare cette m\'ethode avec la m\'ethode des diff\'erences
finies de la feuille 1~?
\end{enumerate}

\end{document}
\pagebreak
{\bf Exercice 17}\\
Soit $P$ un polyn\^ome unitaire de degr\'e $d>0$ \`a coefficients
r\'eels 
(ou complexes)
$$ P=x^d+p_{d-1}x^{d-1}+...+p_1x+p_0$$
On suppose que $P$ admet une seule racine de
module maximal, que l'on notera $z$. 
On souhaite trouver une approximation de $z$
par une m\'ethode combinant la m\'ethode de la puissance et de Newton.
Par exemple pour fixer les id\'ees et tester~:
$$ P=x^7-11x^4+5x-55, \quad d=7$$
\begin{enumerate}
\item On construit une matrice compagnon $M$ de $P$ (commande
\verb|M:=tran(companion(P))| de Xcas) d\'efinie par~:
$$ M=\left(\begin{array}{cccccc}
0 & 1 & 0 & ... & 0 & 0 \\
0 & 0 & 1 & ... & 0 & 0 \\
...& ... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & 1 & 0 \\
0 & 0 & 0 & ... & 0 & 1 \\
-p_0 & -p_1 & -p_2 & ... & -p_{d-2} & -p_{d-1} \\
\end{array}\right)$$
on admettra que le polyn\^ome caract\'eristique
de $M$ est $P$. Expliquer pourquoi la m\'ethode de la puissance
appliqu\'ee \`a $M$ permet de d\'eterminer la racine $z$ de $P$.
\item En utilisant la structure particuli\`ere
de la matrice $M$, expliquer comment on peut calculer 
efficacement $v_{n+1}=Mv_n$ \`a partir de la liste $l$
des coefficients de $P$ par ordre croissant 
(\verb|l:=revlist(symb2poly(P,x))|) 
en $O(d)$ op\'erations.
\item \'Etant donn\'e un petit r\'eel $\varepsilon>0$, 
quel test d'arr\^et vous parait le plus judicieux pour
stopper le calcul des $v_n$~? Pourra-t-on certifier que l'estimation
de la valeur propre obtenue sera proche \`a $\varepsilon$ pr\`es de $z$~?
\item Programmer l'algorithme en passant en param\`etre
la liste \verb|l| et le petit r\'eel \verb|eps|
(on pourra utiliser \verb|v[1..d-1]|
qui extrait les \'el\'ements de \verb|v| d'indice \verb|1| \`a \verb|d-1|
inclus, \verb|dotprod(l,v)|
effectue le produit scalaire de \verb|l| et \verb|v| en tronquant
le vecteur le plus long lorsqu'ils ne sont pas de taille \'egale, 
et les instructions \verb|append| et \verb|normalize|)
\item Dans les questions suivantes, sauf la derni\`ere, on travaille
sur l'exemple. Donner une estimation $z_4$ de $z$
pour l'exemple pour $\varepsilon$=\verb|1e-4| et $z_8$ pour
$\varepsilon$=\verb|1e-8|. Combien d'it\'erations sont-elles
n\'ecessaires pour obtenir cette estimation~?
Pouvait-on s'y attendre~?
\item Afin d'acc\'el\'erer le calcul, on se propose d'utiliser la suite
it\'erative $u_n$ de la  m\'ethode de Newton en partant de $u_0=z_4$.
Donner l'expression de $u_{n+1}$ en fonction de $u_n$.
Quelle pr\'ecision peut-on esp\'erer 
en effectuant 2 it\'erations~?
\item Calculer $u_2$. Proposer un raisonnement pour
majorer l'erreur $|u_2-z|$ et calculer ce majorant.
\item Si on souhaite g\'en\'eraliser la m\'ethode ci-dessus \`a un
polyn\^ome unitaire quelconque (sans faire l'hypoth\`ese de
l'existence d'une unique racine de module maximal), quels
sont les obstacles pr\'evisibles~? Comment peut-on les contourner~?
\end{enumerate}

\pagebreak


\end{document}
% \bexer
% Soit $A$ la matrice tridiagonale de taille $n$ donnée par :
% \[A=\left(\begin{array}{ccccc}2&-1&&&\\-1&2&-1&&{\bf 0}\\
%     &\ddots&\ddots&\ddots&\\{\bf
%       0}&&-1&2&-1\\&&&-1&2 \end{array}\right)\]
% \begin{enumerate}
% \item
% Montrer que 
% $$u_k=(\sin(\frac{k\pi}{n+1}),...,
% \sin(\frac{kj\pi}{n+1}),...,\sin(\frac{kn\pi}{n+1})) $$
% est vecteur propre de $A$ et calculer la valeur propre associ\'ee.
% En d\'eduire que les m\'ethode de Jacobi, de Gauss-Seidel et de
% relaxation (pour $\omega<2$) convergent.
% \item
% %Soit $b=\left(\begin{array}{c}1\\0\\0\\\vdots\\0\\1\end{array}\right)$.
% Soit $b=(1,0,...,0,1)$.
% La solution du système linéaire $Ax=b$ est donnée par 
% %$x=\left(\begin{array}{c}1\\1\\\vdots\\1\end{array}\right)$.
% $x=(1,1,...,1)$.
% \'Evaluer le nombre d'itérations
% pour avoir une précision de \verb|1e-10| en appliquant la m\'ethode
% de Jacobi, de Gauss-Seidel et de relaxation (avec $\omega =1.5$). 
% On fera des simulations pour $4\leq n\leq 20$.
% Quel est le cout d'une it\'eration en fonction de $n$~? Comment se
% compare cette m\'ethode avec une m\'ethode directe~?
% \item
% Pour $n=20$, représenter la fonction donnant le rayon spectral de la 
% matrice de la méthode de relaxation en fonction de $\omega\in [0,2]$. 
% Trouver graphiquement le paramètre optimal et comparer le à 
% $\frac{2}{1+\sqrt{1-\rho(J)^2}}$.
% \end{enumerate}
% \eexer

% \bexer

% {\bf Méthode de Newton dans le plan complexe}

% On propose de représenter les bassins d'attraction des zéros de $z \mapsto z^3-1$ dans $\C$ pour la méthode de Newton.

% Les zéros sont $Z=\{1, j ,j^2\}$ où $j=e^{\frac{2i\pi}{3}}$.

% Si $a\in Z$, on note $A(a)=\{z_0\in\C\ /\ (z_n)_{n\in \N} \mbox{tend vers }a\}$ où $z_{n+1}=\frac{2z_n^2+1}{3z_n^3}$. $A(a)$ est appelé le bassin d'attraction de $a$.

% Soit $\epsilon >0$ et $N\in \N$. Soit $A_{N,\epsilon}(a)=\{z_0\in\C\ /\ |z_N-a|<\epsilon\}$.

% Ecrire un programme qui colorie en rouge les points de $A_{N,\epsilon}(1)$, en vert ceux de  $A_{N,\epsilon}(j)$ en bleu ceux de $A_{N,\epsilon}(j^2)$ et en jaune les autres.

% Même exercice avec le polynome $z \mapsto (z-1)(z-a+\demi)(z+a+\demi)$ où $a=-0.00508+0.333136i$.

% {\it voir http://images.math.cnrs.fr/La-methode-de-Newton-et-son.html}

% \eexer


\end{document}

