\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 2014/2015           \\[-2mm]\hrule}


\begin{center}
%  {\Large\bf Math\'ematique assist\'ees par ordinateur} \\
  Examen du 19 mai 2015, de 14h \`a 17h. \\
  \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{M\'ethode de la puissance et de Newton (9 points)}
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}

\section{Interpolation, intégration (11 points)}
On souhaite expérimenter une méthode d'intégration où on approche la
fonction à intégrer $f$ sur $[-1,1]$ par
son polynôme d'interpolation $P$ aux $n$ points d'abscisses $x_1,...,x_n$ les
racines du $n$-ième polynôme de Tchebychev $T_n(\cos(x))=\cos(nx)$.
On pose donc~:
$$ I(f)=\sum_{j=1}^n \omega_j f(x_j)=\int_{-1}^1 P(t) \ dt $$
On va d'abord calculer les $\omega_j$ puis expérimenter.
\begin{enumerate}
\item Déterminer $x_1, x_2,x_3$ pour $n=3$. En posant $f_1=f(x_1),
f_2=f(x_2), f_3=f(x_3)$, déterminer la valeur de $P$ avec un logiciel
de calcul formel, puis $\int_{-1}^1 P(t) \ dt$, factoriser le résultat
et en déduire $\omega_1, \omega_2, \omega_3$ pour $n=3$.
Que pensez-vous de cette méthode pour calculer les $\omega_j$ lorsque
$j$ est grand~?
\item Rappeler pourquoi l'ordre de la méthode est au moins $n-1$,
donner la valeur de $I(1), I(x), ..., I(x^{n-1})$, et
en déduire un système linéaire vérifié par les $\omega_j$.
\item On rappelle qu'une matrice de Vandermonde est inversible si tous
ces arguments sont distincts. En déduire que le système précédent
permet de déterminer les $\omega_j$.
\item Faire le calcul par cette méthode pour $n=3$ et vérifier les
résultats de la première question.
\item Calculer une valeur approchée des $\omega_j$ pour $n=15$.
Déterminer le conditionnement de la matrice du système.
Que peut-on dire de la précision de la valeur des $\omega_j$
calcul\'es en r\'esolvant le syst\`eme~?
\item Quel est l'ordre de la méthode pour $n=3$~? Est-il meilleur 
pour $n=4$~?
\item On se place maintenant sur une subdivision $[\alpha,\beta]$
où on transporte la méthode
$$ I(f)=\sum_{j=1}^n \omega_j f(t_j), \quad  t_j=\frac{\alpha+\beta}2+
\frac{\beta-\alpha}2 x_j $$ 
Donner une majoration de l'erreur sur une subdivision, puis sur
$[a,b]$ si on le découpe en $N$ subdivisions (de taille $h=(b-a)/N$)
\item \'Ecrire une fonction \verb|I(f,a,b,N)| appliquant la
m\'ethode pr\'ec\'edente pour $n=3$.
\item Appliquer la méthode précédente pour approcher $\int_0^1 e^{-t^2} \ dt$
à \verb|1e-5| près lorsque $n=3$~: on déterminera une valeur de $N$ 
qui assure la majoration de l'erreur.
\item Comparer avec la valeur
approch\'ee de l'int\'egrale renvoyée par le logiciel, 
la majoration de l'erreur vous parait-elle fine ou grossi\`ere~?
Si la majoration est grossi\`ere, pourrait-on l'am\'eliorer~?
\end{enumerate}

\end{document}


