%Premier rapport TIPE
\documentclass[12pt,a4paper,draft]{article}
\usepackage[francais]{babel}\usepackage{indentfirst}\usepackage[T1]{fontenc}\usepackage{color}\usepackage{amssymb}\usepackage{graphicx}\usepackage{amsopn}
\definecolor{vert}{rgb}{0.13,0.64,0.13}
\setlength{\hoffset}{-18pt}  	
\setlength{\oddsidemargin}{0pt} 	% Marge gauche sur pages impaires
\setlength{\evensidemargin}{9pt} 	% Marge gauche sur pages paires
\setlength{\marginparwidth}{54pt} 	% Largeur de note dans la marge
\setlength{\textwidth}{481pt} 	% Largeur de la zone de texte (17cm)
\setlength{\voffset}{-18pt} 	% Bon pour DOS
\setlength{\marginparsep}{7pt} 	% Séparation de la marge
\setlength{\topmargin}{0pt} 	% Pas de marge en haut
\setlength{\headheight}{13pt} 	% Haut de page
\setlength{\headsep}{10pt} 	% Entre le haut de page et le texte
\setlength{\footskip}{27pt} 	% Bas de page + séparation
\setlength{\textheight}{708pt} 	% Hauteur de la zone de texte (25cm)

\title{\textbf{Résolution de Systèmes Linéaires}}

\author{Cyrielle Gandon, Fabien Traventhal}

\begin{document}

\maketitle

\section{Introduction}

Dans ce TP, nous allons étudier la résolution de système linéaire (SEL) de manière numérique en comparant différents critères. Nous allons analyser l'impact de la dimension de la matrice, de la valeur du conditionnement et du type de méthode utilisée sur la qualité des résultats obtenus. Dans ce rapport, nous allons expliquer les méthodes employées, puis présenter les résultats et enfin discuter sur les résultats obtenus.



\section{Contexte}

Nous allons nous intéresser aux SEL du type:

$$Ax = b; A \in \mathbb{R}^{n \times x}, x,b \in \mathbb{R}^{n}$$

Le but de ce TP est d'étudier la qualité du resultat obtenu selon trois critères:
\begin{itemize}
\item La valeur du conditionnement de la matrice
\item La dimension de la matrice
\item La méthode de résolution
\item Le coefficient de relaxation
\end{itemize}

\subsection{Conditionnement d'une matrice}
Le \textbf{conditionnement} donne une borne de l'erreur relative commise sur la solution $x$, ainsi une borne large peut entrainer des résultats expérimentaux inexploitables. Dans notre équation, une petite variation sur $b$ peut entraîner une grande variation sur la solution $x$.
\paragraph{}
On définit le conditionnement d'une matrice $A \in \mathbb{R}^{n \times n}$ par:
$$\kappa_{\alpha}(A)=\parallel A \parallel_{\alpha}\parallel A^{-1} \parallel_{\alpha} $$ $ \alpha = 2$
\paragraph{}
Dans notre étude, nous étudions trois valeurs différentes de $\kappa: 10, 10^{3}, 10^{6}$

\subsection{Dimension de la matrice}

La dimension de la matrice est importante dans la qualité des résultats. En effet, le nombre d'opération augmente selon la taille de matrice.
On choisit d'étudier quatres matrices carrées de taille différente: $n=10, 50, 100, 150$
\paragraph{}
Ainsi, on pourra voir l'impacte de la taille d'une matrice sur la précision du résultat dans la résolution d'un système lineaire.

\subsection{Méthodes de résolution}
\paragraph{}
On étudie deux types de méthodes différentes pour la résolution de notre système.

\begin{itemize}
\item Méthode Directe
\item Méthode Itérative
\end{itemize}

\paragraph{}
La \textbf{méthode directe} consiste à utiliser une fonction intégrée au logiciel Scilab: \textit{linsolve}. Elle prend en paramètres d'entrées une matrice $A$ et un vecteur $b$ et retourne le vecteur solution $x$.
\paragraph{}
La \textbf{méthode itérative} qu'on utilisera sera celle de Jacobi. Pour résoudre le système linéaire, on utilise une suite $x(k)$ qui converge vers un point fixe x, qui sera solution du système $Ax=b$. On peut réecrire le système sous la forme: $x = (A+I)x-b$
\paragraph{}
La suite x(k) est donc définie par: $$x(0) \in \mathbb{R}^{n},
 x(k+1) = (A+I)x(k)-b$$
\paragraph{}
Le but de cette algorithme est d'atteindre un point fixe et le plus rapidement possible.
\paragraph{}
On décompose la matrice A en deux matrices:
\begin{center}
 $A= M-N$, avec M régulière.
\end{center}
\paragraph{}
Ensuite, pour les matrices M faciles à extraires de A et immédiatemment
inversibles, on peut prendre la diagonale de A ou bien une matrice
triangulaire. On décompose la matrice A de la façon suivante :
\begin{center}
$A = D+L+U$
\end{center}
D étant la diagonale, L la partie en dessous de la diagonale et U,
la partie au dessus.
\paragraph{}
On prend $M = D$ et $N = -L-U$ pour enfin obtenir la formule suivante:

$$x(0) \in R^n, x(k+1) = -D^{-1}(L+U)x(k)+D^{-1}b$$
\section{Présentation du programme}

Pour étudier les différentes influences vu auparavant sur la résolution d'un SEL, nous avons codé en Scilab un programme permettant de faire cette étude. On peut paramètrer dans main.sce le nombre d'itération max que l'on veut pour la méthode de Jacobi, la taille de la matrice ainsi que la valeur du conditionnement. Une fois exécuté, notre programme permet d'afficher l'erreur pour la méthode directe, l'erreur résiduelle pour la méthode itérative ainsi que l'erreur à la k$^{éme}$ itération si la méthode converge. Si on atteint le nombre d'itérations maximum mais que l'utilisateur veut continuer d'exécuter l'algorithme, il lui suffit d'appuyer sur 1 ou sur un autre chiffre pour arrêter. Le programme permet également d'afficher le nombre d'itarations minimum pour atteindre le seuil de $10^{-8}$ pour l'erreur résiduelle.
\section{Résultats}

Voici les résultats obtenus pour chaque méthode, en fonction de la dimension n de la matrice et du conditionnement $\kappa$:

\subsection{Méthode Directe}



\begin{tabular}{|c|c|c|c|c|}
  \hline
    & $n = 10$ & $n = 50$ & $n = 100$ & $n = 150$ \\
  \hline
  $\kappa = 10$ & $3.82\times 10^{-15}$ & $1.12\times 10^{-14}$ & $1.92\times 10^{-14}$ & $2.62\times 10^{-14}$\\
  \hline
  $\kappa = 10^{3}$ & $5.82\times 10^{-14}$ & $1.49\times 10^{-13}$ & $1.57\times 10^{-13}$ & $2.62\times 10^{-13}$\\
  \hline
  $\kappa = 10^{6}$& $6.14\times 10^{-11}$ & $9.41\times 10^{-11}$ & 9.047 & 11.063\\
  \hline
\end{tabular}

\subsection{Méthode Jacobi: Erreur résiduelle}



\begin{tabular}{|c|c|c|c|c|}
  \hline
    & $n = 10$ & $n = 50$ & $n = 100$ & $n = 150$ \\
  \hline
  $\kappa = 10$ & $9.88\times 10^{-9}$ & $9.02\times 10^{-9}$ & $9.53\times 10^{-9}$ & $9.8\times 10^{-9}$\\
  \hline
  $\kappa = 10^{3}$ & diverge & $9.99\times 10^{-9}$ & $9.99\times 10^{-09}$ & $1\times 10^{-8}$\\
  \hline
  $\kappa = 10^{6}$& diverge & $1.00\times 10^{-8}$ &  & \\
  \hline
\end{tabular}
\paragraph{}
A cause du trop grand nombre d'itérations nécessaires pour résoudre le système avec une erreur résiduelle inférieure à $10^{-8}$ pour $\kappa=10^{6}$ et $n=100, 150$, notre programme n'a pas réussi à trouver les valeurs.

\subsection{Méthode Jacobi: Erreur à l'itération i}



\begin{tabular}{|c|c|c|c|c|}
  \hline
    & $n = 10$ & $n = 50$ & $n = 100$ & $n = 150$ \\
  \hline
  $\kappa = 10$ & $6.41\times 10^{-8}$ & $2.00\times 10^{-7}$ & $3.00\times 10^{-7}$ & $3.00\times 10^{-7}$\\
  \hline
  $\kappa = 10^{3}$ & diverge & $9.30\times 10^{-6}$ & $1.48\times 10^{-05}$ & $1.90\times 10^{-5}$\\
  \hline
  $\kappa = 10^{6}$& diverge & $5.17\times 10^{-3}$ &  & \\
  \hline
\end{tabular}
\paragraph{}
$\acute{E}$tant donné que nous calculons cette erreur à l'itération où l'erreur résiduelle est inférieure à $10^{-8}$ et que nous n'avons pas réussi à atteindre ce seuil pour $\kappa=10^{6}$ et $n=100, 150$, nous n'avons pu renseigner les deux cases vides.

\section{Interprétation des résultats}

Nous allons maintenant pouvoir étudier l'influence du conditionnement et de la taille de la matrice sur la qualité du résultat. Pour chacun des deux critères, nous comparerons aussi la méthode utilisée.

\subsection{Influence du conditionnement}

On voit que le conditionnement à une influence différente suivant la méthode employée. En effet, avec la méthode directe, alors que $\kappa$ augmente de $10^{5}$ la précision du résultat diminue d'un facteur $10^{3}$ alors que pour la méthode itérative et en se fiant à l'erreur résiduelle la précision diminue d'un facteur $10$. Cependant, en se fiant à l'erreur lors de la k-ième itération, la perte de précision est de l'orde de $2.10^{4}$. Le conditionnement a aussi un grand impact sur la convergence de la méthode de Jacobi puisque c'est la première élément qui entraîne une divergence de cette dernière lors de notre expérience.

\subsection{Influence de la taille de la matrice}

Contrairement, au conditionnement de la matrice, sa taille à une influence plutôt négligeable sur la qualité du résultat. En effet, pour la méthode itérative, la qualité du résultat est constante alors que pour la méthode directe on observe un facteur 10. Cependant, la taille de la matrice augmente de manière considérable le nombre d'itérations  et donc le temps nécessaire pour atteindre le seuil de $10^{-8}$. La taille a également une influence sur la convergence pour la méthode Jacobi. Dans notre cas, une matrice trop petite, pour un conditionnement trop grand à entraîner la divergence.

\subsection{Influence de la méthode utilsée}

La méthode directe semble être la méthode la plus à même de résoudre un système d'équations linéaires car elle présente des résultats plus précis et avec un temps de calcul beaucoup plus court. De plus, elle ne nécessite pas l'acceptation par un critère de convergence pour fonctionner. Cependant, on peut voir qu'elle peut avoir des limites lorsque la taille de la matrice et le conditionnement augmentent. Dans ce cas là, la méthode de Jacobi peut paraître plus adaptée mais encore faut-il que l'ordinateur soit assez puissant ou que l'algorithme ait une complexité optimale pour donné un résultat en un temps satisfaisant.

\subsection{Influence de la relaxation}

Pour ce qui est de la méthode de Jacobi relaxée, nous n'avons pas réussi à obtenir une convergence pour un autre coefficient que 1.0 qui correspond à la méthode de Jacobi sans relaxation. Nous ne pourrrons donc pas faire de conclusion par rapport à cela.

\section{Conclusion}

Si on regarde la précision des résultats obtenus, la méthode directe est la plus efficace. La seule limite de cette méthode est la taille de la matrice. Or, celle ci à une influence négligeable. Aussi, dans la méthode de Jacobi, le nombre d'itération pour atteindre le seuil souhaité de l'erreur résiduelle est d'environ $10^{7}$ itérations pour $\kappa = 10^{6} $ et $n=150$. La complexité de l'algorithme de cette méthode est donc très importante, ce qui rend les résultats très difficiles à obtenir quand le conditionnement de la matrice est élevé. Ainsi, pour avoir un résultat fiable, il est essentiel d'avoir une matrice bien conditionnée, c'est à dire une valeur de $\kappa$ faible car nous avons pu voir que c'était le facteur qui avait le plus d'influence. 


\end{document}