\clearpage \section{Introduction} \bigskip En math\'ematiques, un syst\`eme d'\'equations lin\'eaires est un ensemble d'\'equation lin\'eaires qui portent sur les m\^emes inconnues. \\ La r\'esolution des SEL appartient aux probl\`emes les plus anciens dans les m\'eth\'ematiques et ceux-ci apparaissent dans beaucoup de domaines, comme en traitement du signal, en optimisation lin\'eaire, ou dans l'approximation de probl\`emes en analyse num\'erique.\\ Dans le cadre de notre TP, on s'int\'eresse \`a la r\'esolution d'un SEL \begin{center} \\$Ax = b$; $A \in \mathbb{R}\up{n \times n}$, $x$, $b \in \mathbb{R}\up{n}$ \\ \end{center} du point de vue num\'erique. \\ Le but de ce TP est d' \'etudier la qualit\'e de la solution sous trois aspects : \\ 1. Influence de la valeur de conditionnement de la matrice. \\ 2. Influence de la dimension de la matrice. \\ 3. Influence de la m\'ethode de r\'esolution utlilis\'ee (directe ou gradient conjugu\'ee). \\ Nous avons donc r\'ealis\'e un programme Scilab capable de cr\'eer des matrices carr\'ees r\'eguli\`eres, avec la dimension et les valeurs de conditionnement param\'etrables. Nous avons impl\'ement\'e quatres m\'ethodes de r\'esolutions de SEL pour comparer l'erreur par rapport \`a la solution exacte et discuter de la meilleure m\'ethode. \section{M\'ethodes et programme} \subsection{Mise en place des exp\'eriences} Pour faire l'\'etude de ces diff\'erentes m\'ethodes de la r\'esolution d'un SEL et d\'eterminer l'influence de la valeur de conditionnement de la matrice initiale ainsi que sa dimension, nous avons dans un premier temps cr\'e\'e une matrice diagonale \begin{center} $\Delta = diag(1, k ^{-\tfrac{1}{n-1}}, k ^{-\tfrac{1}{n-2}}, \cdots, k^{-1})$ \end{center} et la matrice tridiagonale \begin{center} $H = \begin{bmatrix} 2 & -1 & 0 & \cdots & \cdots & \cdots \\ -1 & 2 & -1 & 0 & \cdots & \cdots \\ 0 & -1 & \ddots & \ddots & 0 & \cdots \\ \cdots & 0 & \ddots & \ddots & -1 & 0 \\ \cdots & \cdots & 0 & -1 & 2 & -1 \\ \cdots & \cdots & \cdots & 0 & -1 & 2 \end{bmatrix} $ de dimension $(n \times n)$ \end{center} Ensuite nous nous servons de la fonction Scilab $svd$ pour faire une d\'ecomposition en valeurs singuli\`eres de cette matrice H, en faisant l'appel $[U, S, V] = svd(H)$. Les matrices U et V sont orthogonales et gr\^ace \`a elles, nous pouvons construire la matrice \begin{center} $A = U\up{T} \Delta V$ \\ \end{center} Nous calculons $b$ de telle sorte que $b = A \xi $ avec $\xi = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}$ \\ Nous appliquons les 4 m\'ethodes de r\'esolutions \begin{itemize} \item m\'ethode de r\'esolution directe, faisant partie de la biblioth\`eque Scilab \\ $[x] = linsolve(A, -b)$, \item m\'ethode du gradient conjugu\'e sans pr\'e-conditionnement gr\^ace \`a la fonction Scilab \\ $[x, fail, err, iter, res] = pcg(A, b, rr, nbMaxIter)$, \item m\'ethode du gradient conjugu\'e avec pr\'e-conditionnement \\ $[x, fail, err, iter, res] = pcg(A, b, rr, nbMaxIter, P)$ avec $P = diag(A)$, \item m\'ethode du gradient conjugu\'e avec pr\'e-conditionnement \\ $[x, fail, err, iter, res] = pcg(A, b, rr, nbMaxIter, P)$ avec \\ $P = (D-L)D^{-1}(D-L^{T})$ o\'u $D = diag(A)$ et $L$ est la partie triangulaire inf\'erieure de la matrice $A$. \end{itemize} Les param\`etres $fail$, $iter$, $res$ ne sont pas utiles dans notre \'etude. $rr$ est le seuil pour l'erreur r\'esiduelle que nous avons fix\'e \`a $10^{-12}$ et $nbMaxIter$ fix\'e \`a $10$. \\ Enfin, nous calculons la norme de l'erreur relative pour la premi\`ere m\'ethode car pour les autres, elle est d\'ej\`a donn\'ee par le param\`etre $err$ de la fonction $pcg$. \subsection{Programmes} Nous avons partag\'e notre travail en deux fichiers Scilab. Le premier fichier \textbf{etude.sce} est le programme qui concentre toutes les mesures demand\'ees dans l'\'enonc\'e, c'est-\`a-dire une matrice de dimension $n = 100, 400, 800, 1200$ et pour chacune d'entre elles, les valeurs de conditionnements $k = 10^{3}, 10^{6}, 10^{10}, 10^{16}$, ainsi que la r\'esolution par les quatre m\'ethodes. Il y a donc en tout $64$ mesures. Le deuxi\`eme fichier \textbf{test.sce} est le programme qui permet \`a l'utilisateur de rentrer lui m\^eme la dimension de la matrice et la valeur de conditionnement qu'il souhaite en tapant les valeurs dans la console. De cette fa\c con nous pouvons mesurer l'erreur avec les quatres m\'ethodes pour n'importe quelles valeurs. \\ Dans les deux fichiers on retrouve les m\^eme fonctions qui : \begin{itemize} \item cr\'ee la matrice diagonale $\Delta$, \item calcule le conditionnement de la matrice entr\'ee en param\`etre. Cette fonction sert \`a v\'erifier que le conditionnement de A est \'egal \`a la valeur de $k$, \item construit la matrice tridiagonale $H$, \item cr\'ee la matrice A par une d\'ecomposition gr\^ace \`a la fonction Scilab $svd$, \item calcule $b$ dans $b = Ax$ avec $x = [1, 1, \cdots, 1]^{T}$, \item r\'esoud le syst\`eme avec la fonction Scilab $linsolve$, \item calcule l'erreur relative par la premi\`ere m\'ethode de r\'esolution, \item calcule l'erreur relative par la deuxi\`eme m\'ethode avec le gradient conjugu\'e sans pr\'e-conditionnement, \item calcule l'erreur relative par la troisi\`eme et quatri\`eme m\'ethode de r\'esolution, le gradient conjugu\'e avec pr\'e-conditionnement. \\ Il faut prendre une matrice $P = diag(A)$ pour la troisi\`eme m\'ethode et $P = (D-L)D^{-1}(D-L^{T})$ o\'u $D = diag(A)$ et $L$ est la partie triangulaire inf\'erieure de la matrice $A$ pour la quatri\`eme m\'ethode. \end{itemize} Enfin nous avons une fonction \textit{main} dans laquelle on cr\'ee la matrice A en utilisant les fonctions que nous avons impl\'ement\'ees. La fonction \textit{main} a pour param\`etres d'entr\'ee deux entiers $K$ et $N$ qui sont respectivement le conditionnement de la matrice A, et sa dimension. Elle calcule ensuite la norme de l'erreur relative pour chaque m\'ethode, en prenant soin de changer la matrice $P$ pour la m\'ethode trois et quatre. Cette fonction renvoie un vecteur $[E1, E2, E3, E4]$ qui sont respectivement la norme des erreurs des m\'ethodes de r\'esolutions, E1 pour la m\'ethode de r\'esolution directe, E2 m\'ethode du gradient conjugu\'e sans pr\'e-conditionnement, E3 m\'ethode du gradient conjugu\'e avec pr\'e-conditionnement $P = diag(A)$, et E4 la derni\`ere m\'ethode. \subsection{Limites} Une des limites de notre programme est que le fichier r\'ealisant les 64 mesures prend beaucoup de temps et n\'ec\'essite la pr\'esence de l'utilisateur pour que le programme se d\'eroule convenablement. Il faut que l'utilisateur appuie sur une touche pour continuer \`a afficher, ce qui fait qu'il est impossible de laisser tourner le programme pour revenir plus tard avec les r\'esultats. L'autre limitation concerne la m\'emoire utilis\'ee. Si on prend une valeur de matrice trop importante (nous avons test\'e avec une dimension initiale de $10000 \times 10000$) on obtient une erreur $stacksize$ malgr\'e le fait que nous l'ayons param\'etr\'e au maximum. \section{R\'esultats} ========================================== \\ Les erreurs relatives \`a chaque m\'ethode de r\'esolution sont list\'ees de la mani\`ere suivante :\\ E1, erreur de la m\'ethode de r\'esolution directe avec linsolve ; \\ E2, erreur de la m\'ethode du gradient conjugu\'e sans pr\'e-conditionnement ; \\ E3, erreur de la m\'ethode du gradient conjugu\'e avec pr\'e-conditionnement, avec P=diag(A) ;\\ E4, erreur de la m\'ethode du gradient conjugu\'e avec pr\'e-conditionnement, avec P=(D-L)*inv(D)*(D-L^t) ;\\ ============================================ \\ =================================== \\ Matrice 100*100 \\ =============== \\ Conditionnement 10^3 \\ E1 = 0.0000000000005348882051 \\ E2 = 0.0189352569212012343536 \\ E3 = 0.0189029890012946434619 \\ E4 = 0.0071217578538137022923 \\ =============== \\ Conditionnement 10^6 \\ E1 = 8.9426938649431342298612 \\ E2 = 0.0191220739994641120152 \\ E3 = 0.0193042825679333243660 \\ E4 = 0.0217121180863589745280 \\ =============== \\ Conditionnement 10^1^0 \\ E1 = 8.9437431119301535886734 \\ E2 = 0.0085892440282820739506 \\ E3 = 0.0088109753010673953766 \\ E4 = 0.0166557879072178408042 \\ =============== \\ Conditionnement 10^1^6 \\ E1 = 9.3451467908636569603686 \\ E2 = 0.0055998548668947569634 \\ E3 = 0.0057719420982575769460 \\ E4 = 0.0133023800482627643782 \\ =================================== \\ Matrice 400*400 \\ =============== \\ Conditionnement 10^3 \\ E1 = 0.0000000000022524240595 \\ E2 = 0.0033445649619674362209 \\ E3 = 0.0033687735337411183964 \\ E4 = 0.0041449143599976709731 \\ =============== \\ Conditionnement 10^6 \\ E1 = 15.650454462219604678808 \\ E2 = 0.0008422324836211646498 \\ E3 = 0.0008401099567675521370 \\ E4 = 0.0073501602467070763225 \\ =============== \\ Conditionnement 10^1^0 \\ E1 = 15.66538329621800684777 \\ E2 = 0.0034069966029500057050 \\ E3 = 0.0034089850362050522041 \\ E4 = 0.0095545591504731935961 \\ =============== \\ Conditionnement 10^1^6 \\ E1 = 15.68237883713406510822 \\ E2 = 0.0026593655595245238414 \\ E3 = 0.0026620444715826224735 \\ E4 = 0.0056723199960285793780 \\ =================================== \\ Matrice 800*800 \\ =============== \\ Conditionnement 10^3 \\ E1 = 24.430094467062005492153 \\ E2 = 0.0095602642087307121432 \\ E3 = 0.0095589662732920785415 \\ E4 = 0.0039289815297709820840 \\ =============== \\ Conditionnement 10^6 \\ E1 = 24.438969704181729980519 \\ E2 = 0.0078839458018887271368 \\ E3 = 0.0079075815220016575091 \\ E4 = 0.0087991170209964324200 \\ =============== \\ Conditionnement 10^1^0 \\ E1 = 25.055510481364574815188 \\ E2 = 0.0026938101097932227318 \\ E3 = 0.0027156173843559693916 \\ E4 = 0.0068286255454667174267 \\ =============== \\ Conditionnement 10^1^6 \\ E1 = 25.089645239297219347918 \\ E2 = 0.0036808136782039858198 \\ E3 = 0.0037064728038327947497 \\ E4 = 0.0095568152475177473720 \\ =================================== \\ Matrice 1200*1200 \\ =============== \\ Conditionnement 10^3 \\ E1 = 29.777162926961789679581 \\ E2 = 0.0086971059022343047418 \\ E3 = 0.0086849191380181690880 \\ E4 = 0.0039823826294114140698 \\ =============== \\ Conditionnement 10^6 \\ E1 = 29.792091435223500894836 \\ E2 = 0.0068980322355066663736 \\ E3 = 0.0069304393872696408788 \\ E4 = 0.0077975827361760861878 \\ =============== \\ Conditionnement 10^1^0 \\ E1 = 30.513865554577211725018 \\ E2 = 0.0026288820060955909660 \\ E3 = 0.0026328241057440439181 \\ E4 = 0.0063702520560646735959 \\ =============== \\ Conditionnement 10^1^6 \\ E1 = 30.562553109409702045696 \\ E2 = 0.0036551483519059973885 \\ E3 = 0.0036653247181908069248 \\ E4 = 0.0078944751852141701459 \\ \section{Discussion} Nous avons test\'e pour toutes les m\'ethodes de r\'esolution, diff\'erents param\`etres pour voir leur influence sur la v\'eracit\'e des r\'esultats comme la dimension de la matrice ainsi que la valeur de conditionnement. Pour la r\'esolution lin\'eaire on remarque que lorsque la dimension de la matrice et la valeur de conditionnement sont relativement petites nous avons une erreur extr\^emement faible. Cependant lorsque la dimension de la matrice atteint $798\times798$ l'erreur devient tr\`es grande. (Nous nous sommes servis de notre second programme pour trouver cette valeur.) Pour toute dimension de matrice si on augmente le conditionnement nous avons une erreur trop grande. Pour la m\'ethode de gradient conjugu\'e sans pr\'e-conditionnement on remarque qu'en moyenne la valeur de l'erreur est acceptable quelque soit la dimension de la matrice et la valeur du conditionnement mais on remarque aussi que pour chaque dimension de la matrice, il y a une valeur de conditionnement o\`u l'erreur est plus faible. Par exemple pour une matrice $100\times100$ la meilleure valeur de conditionnement test\'ee est $10^{16}$ alors que pour une matrice $1200\times1200$ la meilleure valeur de conditionnement test\'ee est $10^{10}$. Pour la m\'ethode de gradient conjugu\'e avec pr\'e-conditionnement avec $P = diag(A)$, on remarque que les valeurs d'erreur sont tr\`es proches des valeurs de la m\'ethode de gradient conjugu\'e sans pr\'e-conditionnement, elles varient de $\pm 0.0001$ \`a chaque calcul. Pour la m\'ethode gradient conjugu\'e avec pr\'e-conditionnement avec $P = (D-L)D^{-1}(D-L^{T})$, on remarque que la dimension de la matrice n'influe pas sur l'erreur, alors que plus la valeur de conditionnement est faible plus l'erreur est faible. \section{Conclusion} Pour conclure ce TP, apr\`es diff\'erents calculs pour diff\'erencier les m\'ethodes et voir quelle m\'ethode est la meilleure, nous observons que lorsque nous sommes face \`a une matrice de petite taille avec une petite valeur de conditionnement la r\'esolution lin\'eaire est incontestablement la meilleure alors que si nous voulons une r\'esolution qui donne un r\'esultat acceptable \`a tous les coups nous choisissons la m\'ethode de gradient conjugu\'e sans pr\'e-conditionnement ou la m\'ethode de gradient conjugu\'e avec pr\'e-conditionnement o\`u $P = diag(A)$ car ce sont celles qui en moyenne ont une erreur acceptable. La m\'ethode gradient conjugu\'e avec pr\'e-conditionnement o\`u $P = (D-L)D^{-1}(D-L^{T})$ est int\'eressante lorsque la dimension de la matrice est tr\`es importante et que la valeur du conditionnement est faible.