\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 17 juin 2015, de 9h \`a 12h. \\
  \it Documents, calculatrices et ordinateurs ultraportables
  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éthode LU et méthode de Jacobi. (12 points)}
Dans tout l'exercice, on numérote les lignes et colonnes de matrices
à partir de 0.

Soit $I$ la matrice carrée de taille $n$, $\sigma$ une application
des entiers de 0 à $n-1$ dans lui-même n'ayant pas de point fixe 
($\forall i \in [0,n-1], \sigma(i) \neq i$), $S_\sigma$ la matrice dont la
$i$-ième ligne ne contient que des 0 sauf un 1 à la colonne $\sigma(i)$.
Pour $\epsilon$ un réel élément de $]0,1/2[$, on définit
$A=\epsilon S_\sigma +(1-\epsilon) I$.

Par exemple pour $n=3$ et $\sigma(0)=2, \sigma(1)=0, \sigma(2)=0$,
on a 
$$ A=\left( \begin{array}{ccc}
1-\epsilon & 0 & \epsilon \\
\epsilon & 1-\epsilon & 0 \\
\epsilon & 0 & 1-\epsilon
\end{array}
\right)$$
On veut comparer la méthode $LU$ et la m\'ethode de Jacobi pour résoudre le système
linéaire $Ax=b$
\begin{enumerate}
\item On pose $\epsilon=1/10$ et $b=(1/2,1/4,1/4)$.
Effectuer la décomposition $LU$ de $A$ 
puis déterminer la solution exacte
du système 
en utilisant la d\'ecomposition $LU$ pr\'ec\'dente
(on indiquera les \'etapes interm\'ediaires des deux calculs).
\item D\'eterminer une suite r\'ecurrente qui converge vers
la solution du syst\`eme $Ax=b$ en appliquant la méthode de Jacobi.
\item Calculer la dixi\`eme itération pour $\epsilon=0.1$
et $b=(.5,.25,.25)$.
\item A quelle vitesse la suite semble-t-elle converger~?
\item Dans la suite, on ne suppose plus que $n=3$.
Pour quelle raison la méthode de Jacobi converge-t-elle~?
\item Estimer la vitesse de convergence en fonction de $\epsilon$.
\item Quel est en fonction de $n$
le coût d'une itération de la méthode de Jacobi pour $A$ ayant la
forme particulière de cet exercice~?
\item Estimer en fonction de $n$ le cout pour obtenir la
solution de $Ax=b$ avec une précision donnée.
\item Quel est le cout en fonction de $n$ de la résolution
par la méthode $LU$~? Quelle méthode est la moins couteuse
lorsque $n$ est grand~?
\end{enumerate}


\section{\'Equation diff\'erentielle (8 points)}
%
Pour r\'esoudre de mani\`ere approch\'ee
une \'equation (ou un syst\`eme diff\'erentiel) $y'=f(t,y)$ avec $f$ de
classe $C^2$,
on va appliquer la m\'ethode explicit\'ee ci-dessous, appel\'ee
m\'ethode de Heun de pas constant $h$. Soit
$y_0=y(t_0)$ la condition initiale, $t_n=t_0+nh$, on approche
$y(t_n)$ par la suite r\'ecurrente $y_n$ d\'efinie par~:
$$ \tilde{y}_{n+1}=y_n+hf(t_n,y_n), \quad
y_{n+1}=y_n+\frac{h}{2}(f(t_n,y_n)+f(t_n+h,\tilde{y}_{n+1}))$$
\begin{enumerate}
\item On suppose que $f(t,y)$ ne d\'epend pas de $y$,
quelle est la m\'ethode num\'erique d'int\'egration correspondante~?
En d\'eduire une majoration de l'erreur locale
$|y_1-y(t_0+h)|$ en fonction de $h$ dans ce cas.
\item On admet que l'erreur locale est encore 
du m\^eme ordre en puissance de
$h$ lorsque $f(t,y)$ d\'epend de $y$. On pose $y_{n+1}=y_n+h\Phi(t_n,y_n,h))$,
donner l'expression de $\Phi$ en fonction de $f$, justifier que $\Phi$
est lipschitzienne par rapport \`a $y$, et en d\'eduire une majoration
de l'erreur globale $|y_n-y(t_n)|$.
\item On suppose dans la suite que $f(t,y)=y$ et que $h\leq 0.1$.
Calculer une constante de Lispchitz pour $\Phi$. 
\item Programmer la m\'ethode. D\'eterminer une valeur approch\'ee
de $y(1)$ obtenue par cette m\'ethode
pour l'\'equation $y'=y, y(0)=1$ avec $h=0.1, 0.01, 0.001$.
Comparer avec la valeur exacte de $y(1)$, observe-t-on le comportement attendu
en puissance de $h$~?
\item D\'eterminer de m\^eme une valeur approch\'ee $y_N$ 
de $y(t_N)$ pour $t_N=4$
et $h=0.1,0.01, 0.001$ (donc $N=40, 400, 4000$), calculer l'erreur 
en utilisant la valeur exacte de $y(t_N)$, observe-t-on le
comportement attendu en fonction de $t_N$~?
%\item Application \`a un syst\`eme~?
\end{enumerate}

\end{document}


