\documentclass[a4paper,10pt]{article}
\usepackage[french]{babel}    % pour dire que le texte est en français
\usepackage{a4}               % pour la taille
\usepackage[T1]{fontenc}      % pour les font postscript
\usepackage{amsmath, amsthm}  % très bon mode mathématique
\usepackage{amsfonts,amssymb} % permet la définition des ensembles
\usepackage{float}            % pour le placement des figures
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{fancyhdr}
\usepackage{fancybox}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{moreverb}
\usepackage{hyperref}
\usepackage{lscape}
\usepackage{eurosym}
\usepackage{layout}
\documentclass[a4paper, 10pt]{article}
\usepackage{ananu}



\begin{document}



%%  Le titre du TP
\title{\textbf{ANALYSE NUMERIQUE - TP2}}
\pageGardeAnaNu{1}{D17}{Sheryl Lafosse Marin} {Sophie Ruelland}{ }

\tableofcontents

\newpage
\section{Introduction}

\bigskip
 Le but du TP est de comparer trois méthodes d'inversion des matrices :
 une méthode directe, résolution par décomposition LU et deux méthodes itératives, la méthode de Jacobi et la méthode relaxée de Jacobi.

\newpage

\section{La méthode de décomposition LU}
\bigskip
    Dans cette partie, nous allons étudier le principe de la décomposition LU
    puis rendre compte des résultats obtenus.

\subsection{Etude préalable}
\bigskip
    La méthode de Décomposition LU est une méthode directe, elle
établit en effet la solution en un nombre fini et prédéterminé
d'étapes. Le nombre d'étapes est fonction de la taille de la
matrice.

Les méthodes directes ont pour principe de remplacer la résolution
du système  Ax=b par un système plus facile à résoudre, par
exemple par un système équivalent de matrice triangulaire ou
diagonale.

Pour diagonaliser une matrice, on doit calculer ses éléments
propres mais c'est un problème difficile à résoudre. On utilise
donc la méthode de décomposition LU, c'est à dire :
 remplacer A par le produit de deux matrices triangulaires, notées
 L traingulaire infèrieure, et
 U triangulaire supèrieure.

On résout alors successivement deux systèmes triangulaires:
 Ly = b puis Ux = y d'où LUx = Ly et ainsi A = LU

Le premier système permet de calculer y par substitution directe,
le second système permet d'obtenir la solution cherchée par
substitution inverse.

\subsection{Résultats obtenus}
\subsubsection{Questions a,b et c}
\bigskip
On étudie la précision numerique du resultat de la methode de la
decomposition LU en utilisant le critère de la norme infinie de
\vert Ax-b\vert \propto,en fonction de la taille de la matrice A
de taille n. On effectue cette étude pour différentes tailles de
la matrice A, n = 10, 20, 40, 80. Pour cela nous avons developpé
notre fonction resoudreLU(). La console de calcul du logiciel
Scilab nous donne : \rightarrow resoudreLU() pour n= 10 la norme
de Ax-b vaut 2.220D-16 , le nombre d'iterations vaut 90. Le temps
de calcul de LU et la résolution en seconde vallent 0.
......................................... pour n= 20 la norme de
Ax-b vaut 2.220D-16 , le nombre d'iterations vaut 380.Le temps de
calcul de LU et la résolution en seconde vallent 0.
......................................... pour n= 40. La norme de
Ax-b vaut 2.220D-16, le nombre d'iteration vaut 1560.Le temps de
calcul de LU et la résolution en seconde vallent 0.03125.
......................................... pour n= 80.La norme de
Ax-b vaut 2.220D-16, le nombre d'itération vaut 6320.Le temps de
calcul de LU et la résolution en seconde vallent 0.046875.
–––––––––––––––––––––––––––––––––––––––––
\subsubsection{Discussion des résultats obtenus}
\bigskip
    On observe différents résultats/
Tout d'abord, notons que la norme est indépendante de la taille de
la matrice. Cette norme est en effet bornée pour tous les calculs
effectués, elle est bornée par le plus petit nombre après 0 pour
le logiciel Scilab. De plus , le temps CPU et le nombre de calculs
effectués au sein de l'algorithme croissent en fonction de la
taille de la matrice( la complexité est exponentielle pour le
nombre de calculs effectués).

    La décomposition LU est particulièrement utile quand on veut inverser une matrice.
Dans ce cas on a AX = I et la décomposition LU donne un premier
calcul LY = I, d'où Y = L^(-1) et ensuite on obtient la matrice
inverse par la résolution de UX = Y.
    L'avantage de cette technique est de pouvoir effectuer une
approche de la solution optimale avec une erreur très faible, et
cela quelque soit la taille de la matrice.


\section{La méthode  de Jacobi}
\bigskip
Dans cette partie, nous allons étudier le principe de la méthode
de Jacobi puis rendre compte des résultats obtenus.

\subsection{Etude préalable}
\bigskip
La méthode de Jacobi est une méthode itérative de résolution de
système linéaire de la forme Ax = b. Nous pouvons réécrire ce
système sous la forme x = (A+I)x-b


Pour résoudre ce système, on utilise une suite x(k) qui converge
vers un point fixe x, solution du système d’équations linéaires.

La suite x(k) est définie par x(0) \in \vert R^n,
 x(k+1) = (A+I)x(k)-b
Ce qui est important c'est la capacité de l'algorithme à atteindre
un point fixe et ceci le plus rapidement possible.

Les algorithmes itératifs stationnaires procèdent à la
décomposition de la matrice A en deux matrices, selon le schéma
\begin{center}
 A= M-N, avec M régulière.
\end{center}
Il faut que la matrice M soit facile à inverser( ou que le système
correspondant soit facile à résoudre).

Pour les matrices M faciles à extraires de A et immédiatemment
inversibles, on peut penser à la diagonale de A ou à une matrice
triangulaire On décompose la matrice A de la façon suivante :
\begin{center}
A = D+L+U
\end{center}
avec D la diagonale, L la partie en dessous de la diagonale et U,
la partie au dessus.

En prenant M = D et N = -L-U on obtient
\begin{center}
x(0) \in \vert R^n, x(k+1) = -D^(-1)(L+U)x(k)+D^(-1)b


\subsection{Résultats obtenus}
\subsubsection{Questions a, b et c}
\bigskip
On effectue cette étude pour différentes taille de la matrice A, n
= 10, 20, 40, 80. Pour cela nous avons développés notre fonction
resolveJacobi(A, b, n) qui reçoit la matrice A, la matrice b, et
la dimension n en paramètres. La console de calcul du logiciel
Scilab nous donne : \rightarrow resoudreJacobi()
 Pour n= 10, la norme est 8.195D-12, le nombre d'itérations nécessaires vaut 562. Le
temps CPU utilisé en secondes vaut 0.0625
 Pour n= 20, la norme est 6.146D-12, le nombre d'itérations necessaires vaut 1981. Le temps CPU
utilisé en secondes vaut 0.15625
 Pour n= 40, la norme est 4.401D-12, le nombre d'itérations nécessaires vaut 7232. Le temps CPU
utilisé en secondes vaut 0.484375
 Pour n= 80, la norme est 3.142D-12, le nombre d'itérations nécessaires vaut 26887.Le temps CPU
utilisé en secondes vaut 3.234375

\subsubsection{Discussion des résultats obtenus}
\bigskip
 A partir de ces résultats on observe que la norme diminue en fonction de la taille de la
matrice. Donc, plus la matrice est grande de taille, plus l’erreur
commise par les calculs est petite. Le nombre d’itérations en
revanche augmente de façon exponentielle, ce qui est expliqué par
le nombre de boucle à l’intérieur de la fonction resolveJacobi(A,
b, n), mais aussi à cause des produits de matrice, et des
inversions de matrice sous-jacentes au calcul de la solution du
système linéaire. Le temps CPU lui augmente très fortement en
fonction de la taille de la matrice.

 Les deux inconvénients de cette méthode sont d'une part que D
peut être assez éloigné de A, d'autre part qu'il faut conserver en
mémoire, à chaque itération, toutes les composantes du vecteur
x(k) et toutes les composantes du vecteur x(k+1).
 Ce que l’on peut dire c’est que cette méthode produit un résultat avec une erreur
proportionnelle à la taille de la matrice. Elle conviendrait pour
la résolution de système linéaire de grande taille.


\section{La méthode relaxée de Jacobi}
\bigskip
Dans cette partie, nous allons étudier le principe de la méthode
relaxée de Jacobi puis rendre compte des résultats obtenus.
\subsection{Etude préalable}
\bigskip
On injecte au calcul de x(k+1) une portion \mu de la valeur issue
du calcul du schéma de l'itération, le reste 1-\mu de la portion
est réservé à la valeur x(k), avec 0<\mu<2. Le coefficient \mu
s'appelle coefficient de relaxation. Le schéma itératif est donné
par
\begin{center}
x(0) \in \vert R^n, x(k+1) = (1-\mu)x(k)-\mu D^(-1)(L+U)x(k)+\mu
D^(-1)b Si \mu <1 nous avons une sous-relaxation et si \mu >1, une
sur-relaxation. Pour \mu = 1 nous avons le schéma de Jacobi
non-relaxé.

\subsection{Résultats obtenus}
\subsubsection{Questions a, b et c}
\bigskip
Dans un premier temps nous étudions l'influence du nombre \mu sur
le nombre d'itérations lors de la resolution. Le but est de
trouver \mu tel que le nombre d'erreurs soit le plus petit
possible, c'est à dire tel qu'il y ait le moins d'itérations
possibles. En fabriquant un graphique qui représente le nombre
d'itérations en fonction de \mu, on voit que le nombre
d'itérations est minimum pour \mu = 1. Le \mu optimal est donc
égal à 1. Dans cette partie on effectue une etude de la résolution
de systeme lineaire en utilisant la méthode de Jacobi relaxée en
choisissant comme coefficient de relaxation \mu = 1 . On effectue
cette étude pour différentes tailles de matrice A, n = 10, 20, 40,
80.

La console de calcul du logiciel Scilab nous donne :
 \rightarrow resolveJacobiRelaxe()
 Pour n= 10, la norme est 2.220D-16,le nombre
d'itérations necessaires vaut 824. Le temps CPU utilisé en
secondes vaut 0.09375
 Pour n= 20, la norme est 2.220D-16, le nombre
d'itérations nécessaires vaut 2949. Le temps CPU utilisé en
secondes vaut 0.359375
 Pour n= 40, la norme est 2.220D-16, le
nombre d'itérations necessaires vaut 10868. Le temps CPU utilisé
en secondes vaut 2.5
 Pour n= 80, la norme est 2.220D-16, le nombre
d'itérations necessaires vaut 40768. Le temps CPU utilisé en
secondes vaut 24.421875 .

\subsubsection{Discussion des résultats obtenus}
\bigskip
La norme \Vert Ax-b \Vert \propto est bornée à \varepsilon,cette
methode nous permet donc d'avoir une norme bornée, et cela
independamment de la taille de la matrice. Cepandant le nombre
d'itérations est très grand, on observe une variation
exponentielle du nombre d'itérations en fonction de la taille de
la matrice. Le temps CPU est lui encore plus grand, beaucoup plus
grand que le temps CPU observé par les autres methodes.

\section{Bilan de l'étude des différents méthodes de résolution
des systèmes linéaires}
\bigskip
En se basant sur le critère de la précision, seul la méthode LU et
la méthode de Jacobi relaxée donnent une précision sur la norme
assez satisfaisante (norme infèrieure à \varepsilon, et surtout
indépendante de la taille de la matrice. L'occupation de mémoire
peut etre evaluée par le nombre d'itérations effectuées par la
fonction. La méthode de Jacobi relaxée a la plus grande valeur.
D'un point de vue temporel, on observe differents temps de
calculs. En effet les temps les plus grands son atteints par la
methode de Jacobi relaxée. La methode la plus rapide étant la
methode LU.