\NeedsTeXFormat{LaTeX2e}
\documentclass[10pt,a4paper]{amsart}
\usepackage{amsmath,amsfonts,amssymb,latexsym}
\usepackage{a4,mathptmx,helvet,courier}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\newcounter{exonum}[section]
\newenvironment{exo}{\begin{enumerate}\stepcounter{exonum}%
\renewcommand{\theenumi}{\thesection.\arabic{exonum}}%
\renewcommand{\labelenumi}{\bf\theenumi.}\item}{\end{enumerate}}

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

\begin{document} 

\pagestyle{empty}
\thispagestyle{empty}

{\footnotesize\noindent
Universit\'e Joseph Fourier, Grenoble I   \hfill $\bullet$ \hfill
L3 M\'ethodes num\'eriques                       \hfill $\bullet$ \hfill
Ann\'ee 2013/2014           \\[-2mm]\hrule}


\begin{center}
%  {\Large\bf Math\'ematique assist\'ees par ordinateur} \\
  CC du 19 mars 2014, de 13h \`a 15h. \\
  \it Documents, calculatrices et ordinateurs ultraportables
  (netbooks) d\'econnect\'es du r\'eseau autoris\'es.\\
  Ce sujet comporte 2 pages. 
Bar\^eme donn\'e \`a titre indicatif et non contractuel.
\end{center}

\section{Interpolation et conditonnement (12pts)}
On connait la valeur d'une fonction en $n+1$ points d'abscisse
$x_0,...,x_n$
et on cherche le polyn\^ome d'interpolation en ces $n+1$ points
de deux mani\`eres~: par la m\'ethode des diff\'erences
divis\'ees ou comme solution du syst\`eme lin\'eaire
$P(x_i)=y_i$ o\`u les inconnues sont les coefficients $a_0,..,a_n$
du polyn\^ome $P(x)=a_n x^n+..+a_0$.
\begin{enumerate}
\item Montrer que le syst\`eme lin\'eaire est de la forme $Ma=y$
o\`u $M$ est la matrice de Vandermonde de $x_0,...,x_n$
(\verb|vandermonde| dans Xcas). 
\item R\'esoudre avec Xcas
ce syst\`eme pour $$n=5, \
x_0=-1, x_1=-1+\frac{2}{n}, ..., x_k=-1+\frac{2k}{n}, ..., x_n=1$$
et $y_k=f(x_k)=1/(1+x_k^2)$.
Comparer avec la solution $P_5$ renvoy\'ee par les diff\'erences
divis\'ees.
\item Donner une majoration de l'erreur d'interpolation entre
  $f(x)=1/(1+x^2)$ et $P_5(x)$ sur $[-1,1]$ (Indication, utiliser
\verb|diff(f,x,k)| pour calculer la d\'eriv\'ee
$k$-i\`eme de l'expression \verb|f| et \verb|proot(diff(numer(),x))|
pour trouver les racines approch\'ees de la d\'eriv\'ee
du num\'erateur). En d\'eduire
une majoration de l'erreur $\int_{-1}^1|f(x)-P(x)| \ dx$
puis un encadrement de $\pi$.
\item D\'eterminer en fonction de $n$ un \'equivalent du nombre
d'op\'erations pour r\'esoudre le syst\`eme $Ma=y$, en indiquant
rapidement la m\'ethode utilis\'ee. 
Comparer avec l'algorithme des diff\'erences
divis\'ees lorsque $n$ est grand.
\item 
Calculer le nombre
de condition de $M$ pour $n=5,10,20$ subordonn\'e \`a 
la norme 1 ($\| y\|_1=\sum_{i=0}^n |y_i| $)
lorsque $x_0=-1, x_1=-1+2/n, ..., x_k=-1+2k/n, x_n=1$. 
On suppose qu'on connait
le vecteur $y=(y_0,...,y_n)$ avec une pr\'ecision relative
de \verb|1e-16| relativement \`a la norme 1, 
que peut-on dire de la pr\'ecision
relative de $a=(a_n,...,a_0)$~?
%\item M\^eme question pour la norme euclidienne.
%\item M\^emes questions si les $x_i$ sont les $n+1$ points de Tchebyshev sur $[-1,1]$.
\end{enumerate}

\section{M\'ethode de Newton (12pts).}
Soit $A$ une matrice carr\'ee de taille $m$
\`a coefficients r\'eels. On suppose que $A$ est diagonalisable 
et que toutes ses valeurs propres sont r\'eelles positives, on a donc
$$ A=PDP^{-1}$$  
avec $D$=\verb|diag|$(d_1,...,d_m)$ (matrice diagonale avec
$d_1,...,d_n$ sur la diagonale). 
On appellera racine carr\'ee de $D$ la matrice diagonale 
\begin{center}
$\sqrt{D}$=\verb|diag|$(\sqrt{d_1},...,\sqrt{d_m})$
\end{center}
 et racine carr\'ee de $A$ la matrice $\sqrt{A}=P\sqrt{D}P^{-1}$. 
Le but de l'exercice est de calculer
$\sqrt{A}$ sans calculer $P$ en appliquant la m\'ethode de Newton
pour r\'esoudre $x^2=A$.
\begin{enumerate}
\item Expliciter la m\'ethode de Newton pour trouver $\sqrt{d}$ lorsque
$d$ est un r\'eel positif. Montrer que la m\'ethode converge lorsqu'on prend $u_0=(1+d)/2$.
Calculer les premiers termes de la suite pour $d=220.121151781$
et pour $d=8011.87884822$. Combien de termes faut-il pour stabiliser
la suite avec 12 chiffres significatifs~?
\item Soient les suites de matrices $(U_n)$ et $(V_n)$ d\'efinies par~:
\begin{eqnarray*} %\label{eq:sqrt}
U_{n+1}&=&\frac{1}{2}(U_n+AU_n^{-1}), \quad U_0=(I_m+A)/2,
\\
V_n&=&P^{-1}U_n P 
\end{eqnarray*}
D\'eterminer $V_0$ et la relation de r\'ecurrence entre $V_{n+1}$ et $V_n$.
\item En d\'eduire que la suite $V_n$ est une suite de matrices diagonales 
qui converge vers $\sqrt{D}$.
\item Montrer que $U_n$ est convergente et calculer sa limite.
\item Calculer le 19i\`eme et 20i\`eme terme
en mode approch\'e de la suite $U_n$ pour $$A=\left(\begin{array}{rr}
7780. & -1324. \\
-1324. & 452.
\end{array}\right) $$ 
Comparer la vitesse de stabilisation avec celle des suites scalaires
pour trouver $\sqrt{d_1}$ et $\sqrt{d_2}$.
\item Soit $f(X)=X^2-A$ d\'efinie pour $X$ matrice carr\'ee de taille
  $m$, d\'evelopper $$f(X+H)-f(X)$$ et en d\'eduire que
la différentielle de $f$ en $X$ appliquée à $H$ vaut $XH+HX$.
\item Donner la suite de la m\'ethode de Newton qui permet
de r\'esoudre $X^2=A$. 
Expliciter cette suite en supposant que tous les termes de la suite
commutent entre eux. Montrer que c'est le cas de la suite $(U_n)$
d\'efinie \`a la question 2 si $U_0=(I_m+A)/2$ et 
qu'on effectue les calculs exactement
(indication~: montrer que tous les termes de la suite
sont des matrices fractions rationnelles en $A$).
\item Expliquer pourquoi la pr\'ecision est mauvaise \`a la question
  5, comment faudrait-t-il modifier la r\'ecurrence pour am\'eliorer
la pr\'ecision~?
\end{enumerate}

\end{document}


