Memoire

Projet mathématique

Mémoire

CAILLER Mélody

QUEMY Alexandre

RAMONDENC Pierre

2009-2010

Mémoire de projet mathématique INSA 2010-2011 : Résolution des systèmes linéaires. P a g e | 1

Table des matières

I- Introduction ..................................................................................................................................................... 3

1. Présentation du projet .................................................................................................................................. 3

2. Contexte ....................................................................................................................................................... 3

3. Objectifs ........................................................................................................................................................ 3

4. Gestion du projet et repartition des rôles .................................................................................................... 4

II- Programme principal ........................................................................................................................................... 5

1. Présentation ................................................................................................................................................. 5

2. Amélioration ................................................................................................................................................. 5

3. Utilisation ...................................................................................................................................................... 6

III- Résolution des systems linéaires ....................................................................................................................... 8

1. Méthode du Pivot de Gauss ......................................................................................................................... 8

a. Présentation ................................................................................................................................... 8

b. Algorithme ...................................................................................................................................... 9

c. Sources ......................................................................................................................................... 10

d. Critiques ....................................................................................................................................... 10

2. Décomposition LU ...................................................................................................................................... 11

a. Présentation ................................................................................................................................. 11

b. Algorithme .................................................................................................................................... 12

c. Sources ......................................................................................................................................... 13

d. Critiques ....................................................................................................................................... 13

4. Factorisation de Cholesky ........................................................................................................................... 14

a. Présentation ................................................................................................................................. 14

b. Algorithme .................................................................................................................................... 16

c. Sources ......................................................................................................................................... 17

d. Critiques ....................................................................................................................................... 17

5. Méthode de Jacobi ..................................................................................................................................... 18

a. Présentation ................................................................................................................................. 18

b. Algorithme .................................................................................................................................... 19

c. Sources ......................................................................................................................................... 19

d. Critiques ....................................................................................................................................... 19

6. Autres methodes & pistes .......................................................................................................................... 20

a. Méthode de Gauss-Seidel ............................................................................................................ 20

b. Méthode du gradient conjugué .................................................................................................... 20

c. Les systemes non-carrés .............................................................................................................. 20

i. Systèmes rectangulaires avec infinité solutions ........................................................... 21

ii. Systèmes rectangulaires avec une unique solution ....................................................... 22


IV- Conditionnement ............................................................................................................................................. 24

1. Problème de conditionnement ................................................................................................................... 24

2. Solutions proposées ................................................................................................................................... 24

a. Cas où le second membre varie ................................................................................................... 25

b. Cas où la matrice varie ................................................................................................................. 25

V- Conclusion ......................................................................................................................................................... 26

Bibliographie.......................................................................................................................................................... 27

Remerciements ...................................................................................................................................................... 27

Annexes ................................................................................................................................................................. 28

1. Algorithme de Lanczos ................................................................................................................................ 28

2. Méthode d’élimination de Gauss pour inverser une matrice carrée ......................................................... 29

Sources ................................................................................................................................................................... 30


I – Introduction

1- Presentation du projet

Durant l’EC « Projet Mathématiques », nous avons travaillé sur les méthodes permettant de résoudre les systèmes d'équations linéaires. Il s'agissait de travailler en groupe sur les différents moyens permettant la résolution de systèmes matriciels plus ou moins grands et d'étudier la complexité des algorithmes mis en place, ainsi que leurs performances et leurs limites.

Nous avons également été amenés à aborder le problème du conditionnement d'une matrice et de l'introduction d'erreurs dans les solutions.

2- Contexte

Aujourd'hui les systèmes linéaires sont partout. En météorologie, dans toutes les sciences, dans tous les domaines de l'industrie. Il est donc primordial pour l'ingénieur de pouvoir résoudre ce genre de système de manière efficace, d'autant plus qu'il s'agit d'un outil très courant.

La théorie est très simple : il suffirait d'inverser la matrice A, et de la multiplier à notre vecteur de mesure. Sauf qu'en pratique, il est déraisonnable de vouloir inverser une matrice pour des raisons de temps et donc de rentabilité : combien de temps prendrait l'inversion d'une matrice contenant plusieurs centaines de milliers de valeurs ? Certainement beaucoup plus que les quelques heures dont dispose Météo France pour traiter des matrices de cette taille.

Et le problème n'est pas récent puisque depuis de nombreux siècles des scientifiques ont mis au point des méthodes permettant de résoudre intelligemment les systèmes linéaires. Ainsi des mathématiciens comme Gauss ou Jacobi ont travaillé sur ce problème dès le 18ème siècle.

Il n’existe pas de méthode systématique qui permettrait la résolution de tout système linéaire Ax = b quels que soient ses particularités. De fait, le choix d’une méthode de résolution est conditionné dans un premier temps par la nature du système (sa symétrie, sa convergence par exemple) puis par la mémoire disponible. On distingue ainsi, deux types de méthodes de résolution :

Les méthodes directes : donnent une solution « exacte » en nombre fini d’opérations.

Les méthodes itératives : donnent une solution approchée en engendrant une « suite finie ou infinie » de vecteurs tendant vers la solution.

3- Objectifs

L'objectif principal de ce projet était d'acquérir des méthodes pour l'ingénieur de résolution de systèmes linéaires en étudiant les différents moyens de résoudre ces systèmes et d'en analyser les avantages et inconvénients.

Un second objectif était de réussir à travailler en groupe et effectuer des recherches efficaces.


4- Gestion du projet et répartition des rôles

Le projet a été découpé en deux phases. La première phase est constituée des séances obligatoires allouées au projet qui nous ont permis de comprendre les méthodes présentées, et de les retranscrire de manière algorithmique. C'était également le moment pour se répartir les taches pour la seconde phase du projet.

Cette seconde phase, en parallèle à la première, fut consacrée à l'élaboration du mémoire, la recherche personnelle sur le sujet des systèmes linéaires (autres méthodes, historique, conditionnement, matrice non-carrée, etc.) puis la mise en commun par mails où lors de brèves réunions de ces recherches.

C'est également durant cette phase que fut codé le logiciel présenté ci-dessous, ainsi que d'autres méthodes que celles proposées par le sujet (Jacobi par exemple), et mis au « propre » le code des méthodes réalisées en cours (indentation correcte, lisibilité, commentaires, etc.).


II – Programme principal

1- Présentation

Nous avons décidé, au delà des consignes générales du projet mathématiques, de réaliser un programme fonctionnel regroupant toutes les méthodes étudiées et qui permet ainsi de résoudre des systèmes linéaires par chacune de ces méthodes. Nous avons ajouté une fonctionnalité qui nous semblait importante pour que le programme ait une utilité : la définition des systèmes à partir de fichier externe, au format texte. Ainsi, dans le cas de très grands systèmes linéaires, l'utilisateur n'aurait pas à rentrer sa matrice à chaque fois, le programme la charge à partir du fichier.

A noter que le logiciel est open-source : nous laissons à chacun la possibilité de modifier et ainsi améliorer le programme à sa guise.

A noter : Le logiciel présenté ici n'est qu'une première version et continuera d'évoluer après le « projet mathématiques » INSA comme projet personnel. Le principal défaut du logiciel est qu'il ne teste pas encore les conditions d'application d'une méthode à un système et de ce fait, il peut renvoyer des résultats incorrects (par exemple, il ne teste pas si la matrice A est symétrique définie positive ce qui est une condition nécessaire à l'application de la factorisation de Cholesky).

Les sources du logiciel (compilant sous systèmes UNIX et Windows) sont disponibles à l’adresse suivante :

http://linear.alwaysdata.net

2- Améliorations

Beaucoup d'améliorations sont envisageables. On peut penser à l'initialisation des matrices par différents types de fichiers (tableaux Excel par exemple), l'exportation des résultats, notamment le vecteur solution sous ces différents types de fichier afin d'en garder une trace exploitable.

Il serait également possible d'afficher les étapes intermédiaires de calculs de chaque méthode afin que l'on se rende compte des différences entre les méthodes qui conduisent pourtant au même résultat.

Encore mieux, intégrer des benchmarks, c'est à dire des tests de performance (par exemple le nombre d'itérations nécessaires par rapport à une autre méthode, le temps de calcul afin de trouver la solution) permettrait de mettre en évidence de façon plus explicite les avantages et inconvénients de chacune des méthodes : certaines méthodes peuvent-être plus intéressantes à utiliser sur des systèmes de grande envergure, d'autres sur des plus petits systèmes, etc.

Nous pourrions également ajouter une interface plus esthétique et ergonomique au programme, avec Qt par exemple, bien que cela ne soit qu'accessoire d'un point de vu résultat.

Une idée intéressante serait de recoder le logiciel en GPGPU (via le framework CUDA pour nVidia par exemple) particulièrement adapté au calcul matriciel, c'est à dire d'exécuter tous les calculs par la carte graphique et non plus par le processeur. L'avantage est que comparativement, un processeur actuel dispose au maximum de 4 cœurs avec une capacité de calcul de 5 gigaflop contre 512 cœurs et 500 gigaflop voir 1teraflop de capacité pour les dernières cartes graphiques. Ainsi, on pourrait diviser par 100 le temps de calcul sur un ordinateur personnel, ce qui n'est pas négligeable. Le logiciel pourrait alors devenir intéressant pour les PME qui n'ont pas forcément les moyens d'acquérir un matériel informatique haut de gamme (super-ordinateur notamment).


Enfin, il est évident qu'il faut améliorer les méthodes proposées en incorporant les algorithmes nécessaires pour vérifier qu'une méthode est applicable au système désiré.

3- Utilisation

Déclaration manuelle de la matrice :

Déclaration de la matrice par un fichier texte (arrêt du programme si le chemin n’est pas valide).


Format du fichier texte :

N // ordre de la matrice

x11 ... x1n // Définition de la matrice, avec un espace pour séparer les valeurs

. . .

. . .

. . .

xn1 ... xnn

b1 ... bn // Définition du vecteur b

Exemple d’utilisation de la méthode de Jacobi :


III – Résolution des systèmes linéaires

L’objet du projet mathématique est l’étude des systèmes linéaires. Cependant, notre étude se restreint aux systèmes carrés dont la solution est unique. Ceci s’explique par la grande difficulté qu’impose la résolution de systèmes rectangulaires ou de systèmes possédant une infinité de solutions. En effet, nos compétences actuelles et le temps qui nous est impartit nous ont contraints d’étudier des systèmes

« simples ».

1- Méthode du pivot de Gauss

a- Présentation

Nous portons tout d’abord notre regard sur cette méthode de résolution directe de système linéaire, la méthode dite du pivot de Gauss ou de l’élimination de Gauss-Jordan, nommée en l’honneur de Carl Friedrich Gauss et Wilhem Jordan. Cette méthode fut rendue connue grâce aux mathématiciens allemands au cours du XIXème siècle, mais elle est connue des chinois depuis le Ier siècle environ.

La méthode du pivot de Gauss permet la transformation d’un système linéaire en un autre système équivalent, puis la résolution de ce système au moyen d’un algorithme dit « de remontée ».

Ce qu’on cherche à résoudre, c’est bien entendu le système Ax=b. Pour cela on va tout d’abord triangulariser la matrice A. Ce système peut s’écrire sous la forme :

La première étape de la triangularisation consiste en l’élimination des variables x1 dans toutes les lignes allant de 2 à n. Ensuite, il s’agit d’éliminer les variables x2 dans toutes les lignes allant de 3 à n, et ainsi de suite. On réitère donc ce type d’opération n-1 fois pour obtenir une matrice A triangularisée.

Prenons l’exemple d’un système linéaire carré d’ordre 3 que l’on peut écrire sous la forme du système suivant :

•1ère

étape :

•2ème

étape :

On élimine x1 dans les lignes L2 et L3.

On élimine x1 dans la ligne L3.


Il est désormais aisé de résoudre ce système en le remontant, c'est-à-dire en déduisant x3 dans la troisième ligne, puis x2 dans la deuxième et enfin x1 dans la première. C’est ce que l’on appelle l’algorithme « de remontée ».

Ainsi, on obtient :

b- Algorithme

On va d’abord par cet algorithme triangulariser la matrice A en une matrice triangulaire supérieure :

Pour i = 1 jusqu’à N faire

Pour k = i+1 jusqu’à N faire

c = A[k][i] / A[i][i]

B[k] = B[k] - c*B[i]

Pour j = i jusqu’à N faire

A[k][j]= A[k][j] - c*A[i][j]

Fin de boucle sur j

Fin de boucle sur k

Fin de boucle sur i

On va par la suite calculer cette matrice triangulaire supérieure à l’aide de l’algorithme de remontée :

Pour i = N jusqu’à 1 faire

S = 0

Pour j = i + 1jusqu’à N faire

S = S + A[i][j]*x[j]

Fin de boucle sur j

x[i] = (b[i] - S) / A[i][i]

Fin de boucle sur i


c- Sources

Le code source de notre programme contient la méthode permettant la triangularisation de notre matrice A, cette méthode est appelée Trisup. Puis le code source contient la méthode permettant la résolution par l’algorithme de remontée, cette méthode est appelée Solsup. Ces deux méthodes sont appelées par la méthode resolG qui correspond à la méthode du pivot de Gauss.

d- Critiques

Cette méthode d’élimination de Gauss présente dans un premier temps l’intérêt d’utiliser des opérateurs élémentaires d’additions, multiplications, ce qui la rend très simple d’utilisation.

De plus, cette méthode présente un avantage par rapport à la méthode LU (cf IV-2) dans la mesure où l’on ne résout qu’un système linéaire. En effet, le nombre de calculs réalisés dans la méthode du Pivot de Gauss de

l’ordre de est inférieur au nombre de calculs réalisés lors d’une factorisation LU. Cependant, cela ne

s’applique que pour la résolution d’un seul système linéaire, ce qui dans la pratique est très rare, voire inexistant puisque pour un même paramètre A on n’effectue jamais une seule série de mesures. Ces mesures correspondent au second membre b.

En outre, cette méthode présente un inconvénient non négligeable. Elle peut en effet s’avérer totalement inutile dans le cas de l’apparition d’un pivot nul. En effet, dans l’algorithme on se rend compte que si l’un des termes A*i+*i+ (pivot) devient nul, le calcul est impossible. Ainsi, la méthode d’élimination de Gauss n’est pas utilisable avec n’importe quel système dans l'état actuel de l'algorithme (alors qu'elle l'est d'un point de vue théorique).

Enfin, l’implémentation sur machine de l’algorithme de Gauss donne généralement de mauvais résultats, car les erreurs d’arrondis s’accumulent et faussent la valeur de la solution.


2- Factorisation LU

a- Présentation

Nous nous intéressons ici à une méthode directe de résolution de système linéaire, la décomposition LU. Nous cherchons à décomposer la matrice carrée inversible A en un produit d’une matrice triangulaire inférieure à diagonale unité appelée L (pour Lower) par une matrice triangulaire supérieure U (pour Upper).

On a ainsi

Avec les matrices L et U telles que :

Tout comme dans la méthode d’élimination de Gauss la première étape de la factorisation LU consiste à transformer la matrice A en matrice U triangulaire supérieure. Néanmoins, la triangularisation de la matrice se fait sans modification du second membre. Ensuite, la matrice étant triangularisée, il faut déterminer la matrice L triangulaire inférieure telle que A soit égal à LU. On peut déterminer à la main que les coefficients L[k][i] de la matrice L sont égaux à l’opposé des coefficients par lequel on multiplie la (k-1)

ème ligne dans le but de

triangulariser la matrice A.

Prenons l’exemple étudié dans le chapitre IV-1 :

La triangularisation de la matrice A donne :

Puis en identifiant les coefficients L[k][i] on trouve : .

Le système initial (E) est donc équivalent au système :

La transformation de notre premier système linéaire Ax=b en LUx=b permet ainsi la résolution du système initial grâce à deux résolutions plus simples.


Dans un premier temps celle du système Ly = b par ce que l’on appelle l’algorithme de descente puis celle du système Ux = y par l’algorithme de remontée.

Algorithme de descente :

Algorithme de remontée :

b- Algorithme

On va grâce à cet algorithme calculer la matrice L et transformer notre matrice A en la matrice U.

Il s’agit de l’algorithme de Doolittle. Il existe en effet, un second algorithme pour la décomposition qui est l’algorithme de Crout.

Pour i = 1 jusqu’à n faire

Pour k = i +1 jusqu’à n faire

L[k][i] = A[k][i]/ A[i][i]

Pour j = 2 à n faire

A[k][j] = A[k][j] - L[k][i] x A[i][j]

Fin de boucle sur j

Fin de boucle sur k

Fin de boucle sur i


c- Sources

Le code source de notre programme contient la méthode permettant de transformer le système Ax=b en LUx=b (Factorisation LU), puis il contient la méthode de résolution de ce dernier système qui permet à l’utilisateur d’obtenir sa solution.

d- Critiques

Cette méthode de factorisation LU présente par rapport à la méthode du pivot de Gauss un certain avantage. En effet, en pratique, on n’effectue pas des mesures isolées, ces mesures correspondent au second membre b qui est donc amené à être modifié un certain nombre de fois pour des paramètres fixes étant établis dans A. Comme la factorisation est unique lorsque l’on a déterminé les matrices inférieure et supérieure L et U il suffit de résoudre les équations (1) et (2) :

Concernant la méthode du pivot de Gauss, lorsque l’on modifie le système linéaire en changeant de second membre la matrice initiale est contrainte d’être modifiée. C’est donc là que la méthode de factorisation LU présente un avantage, lors de résolution multiples de systèmes linéaires.

Décomposition LU Pivot de Gauss

Nombre de calculs

On préfèrera donc la méthode par décomposition LU, chaque fois qu'on a à résoudre plusieurs systèmes avec la même matrice et des seconds membres distincts.

Tout comme dans la méthode d’élimination de Gauss, il est possible qu’un pivot nul apparaisse dans l’algorithme. Ainsi, le nombre de systèmes linéaires susceptibles d’être résolu avec la factorisation LU est réduit. Il faut néanmoins préciser qu’il existe une méthode permettant de contourner ce problème. Celle-ci consiste à permuter la ligne sur laquelle le pivot nul apparait avec une autre ligne ne possédant pas de pivot nul.

Nous pouvons donc espérer améliorer l'algorithme des deux méthodes.

Résolution de N

systèmes

Résolution d’un unique système


3- Décomposition de Cholesky

a- Présentation

Nous nous intéresserons ici à une méthode de résolution directe de systèmes linéaires : la méthode de factorisation de Cholesky. Cette méthode résultant des travaux d’un ingénieur et militaire français André-Louis Cholesky, est très utilisée en chimie quantique, mais aussi pour la simulation d’une loi multinormale.

La méthode de Cholesky consiste en la décomposition d’une matrice carrée symétrique définie positive A en le

produit d’une matrice triangulaire inférieure L et de sa transposée LT tel que l’on ait :

Avec et

On, montre que toute matrice carrée symétrique positive A admet une unique décomposition où L est une matrice triangulaire inférieure dont tous les éléments diagonaux sont strictement positifs.

Cette méthode est très analogue à celle de la décomposition LU puisqu’elle s’appuie sur un principe similaire de décomposition et de résolution.

Ainsi, tout comme dans la méthode de décomposition LU, on substitue la résolution du système linéaire initial

(1) à la résolution du système (2).

De fait, la résolution du système (1) se décompose en la résolution de deux systèmes plus simples.

Dans un premier temps, l’algorithme de remontée (cf IV-2-a)) permet la résolution du système (3) c'est-à-dire le calcul du vecteur y. Puis la résolution du système (4) grâce à l’algorithme de descente (cf IV-2-a)) permet la détermination du vecteur x, solution du système initial (1).

Prenons l’exemple de la matrice carrée symétrique définie positive A suivante :

On cherche la matrice tel que .


De cette dernière égalité, on en déduit le calcul des termes diagonaux :

On en conclut que :

De la même façon on peut calculer les termes sous la diagonale :

On en conclut que :

Ainsi, si on considère une matrice A telle que A= .

La matrice A est égale au produit .


b- Algorithme

Pour calculer la matrice L à partir de la matrice A :

Pour i = 1 jusqu’à N-1

Pour j = i+1 jusqu’à N

Fin de la boucle sur j

Fin de la boucle sur i

Comme évoqué précédemment, la méthode de décomposition de Cholesky ne s’applique qu’aux matrices carrées symétriques définies positives A, c'est-à-dire que :

(la matrice A est symétrique)

(la matrice symétrique A est définie positive)

Dans notre programme, seul le critère de symétrie de la matrice sera vérifié, grâce à l’algorithme suivant :

Pour i =1 jusqu’à N

Pour j = 1 jusqu’à N

Si A[i][j] est différent de A[j][i]

Return faux

Fin de la boucle sur j

Fin de la boucle sur i


c- Sources

Les sources contiennent d’une part la méthode de factorisation de Cholesky permettant le calcul de la matrice triangulaire inférieure L appelée Cholesk. Ensuite, le code source comprend la méthode CholeskResol permettant la résolution du système (2) par l’appel des méthodes Cholesk, solInf et solSup. Enfin, nous avons intégré au programme une méthode permettant de déterminer si une matrice A de taille n respecte le critère de symétrie nécessaire à la méthode de décomposition de Cholesky.

d- Critiques

La méthode de décomposition de Cholesky présente un grand intérêt par rapport à la méthode de décomposition LU car elle nécessite le calcul d’une seule matrice L (la matrice L

T transposée de la matrice est

très simple à calculer) contre 2 L et U dans la deuxième méthode. Néanmoins, elle se révèle tout aussi coûteuse

en termes de calculs car on estime à le nombre de calculs nécessaires à la décomposition (pour une

matrice d’ordre n).

On peut également noter que les conditions sur la matrice A (carrée, symétrique, définie positive) pour l’utilisation de la décomposition de Cholesky sont très restrictives. Ainsi, cette méthode ne permet pas la résolution d’un système linéaire quelconque.


4- Méthode de Jacobi

a- Présentation

La méthode de Jacobi est une méthode itérative de résolution de système linéaire. L'objectif est de construire une suite vectorielle convergente vers la solution du système linéaire. En d'autres termes, nous allons approximer la solution du système et améliorer la précision de cette approximation de manière itérative jusqu'à un degré de précision acceptable.

Cette méthode est due au mathématicien allemand Charles Jacobi connu entre autres pour ses travaux sur la théorie des nombres, les fonctions elliptiques ou le calcul infinitésimal.

Afin de trouver x, solution du système, nous utilisons une suite convergente vers x, point fixe de cette suite. On cherche donc à établir la suite par récurrence x

(k + 1) = F(x

(k)) étant donné un x

(0) donné.

A = M − N où M est une matrice inversible.

où F est une fonction affine. M − 1

N est alors appelée Matrice de Jacobi

Si x est solution de Ax = b alors x = M − 1

Nx + M − 1

b

Pour garantir la convergence de notre suite, il faut que la matrice soit à diagonale dominante, c'est à dire que :

Cependant, une matrice à diagonale dominante implique une suite convergente, mais la réciproque n'est pas vraie.

La seule condition nécessaire et suffisante pour que la suite converge est que le rayon spectral (plus grande valeur propre en module) de B soit strictement inférieur à 1.

Afin de tester si le rayon spectral est inférieur à 1, il nous faut d'abord trouver les valeurs propres de la matrice. Pour ce faire, nous pourrions utiliser l'algorithme de Lanczos, qui est une méthode itérative qui permet de trouver ces valeurs. Cependant, l'algorithme n'est pas évident à mettre en place, et donc, par manque de temps nous considérerons que l'utilisateur a vérifié lui même la convergence de la suite (voire annexe A.1).


b- Algorithme

On choisit une approximation de la solution x0

Tant que la convergence n'est pas atteinte, faire :

Pour i = 1 jusqu'à n faire :

σ = 0

pour j = 1 jusqu'à n faire :

si j différent de i alors

fin de si

fin de boucle sur j

fin de boucle sur i

test de convergence

fin de boucle sur la convergence

c- Sources

Les sources contiennent en plus de l'algorithme de résolution et son affichage ainsi que le choix de la précision. Le nombre d'itération nécessaire pour obtenir la précision désirée est affiché à la suite du vecteur solution.

d- Critiques

On peut émettre plusieurs critiques face à la méthode de Jacobi. Tout d'abord, il existe une condition sur la matrice A qui ne permet pas de résoudre n'importe quel système linéaire. Ensuite, cette méthode a un coût de l'ordre de 3n

2 + 2n par itération et converge moins vite que la méthode

itérative de Gauss-Seidel. Cependant, elle est facilement parallélisable ce qui lui permet d'être particulièrement efficace avec une approche GPGPU (cf. II-3 Améliorations) et donc de devenir plus rapide que d'autres méthodes.


5- Autres méthodes & pistes

a- La méthode de Gauss-Seidel

La méthode de Gauss-Seidel est une méthode itérative de résolution de système linéaire. Tout comme la méthode de Jacobi, elle consiste en la création d’une suite vectorielle convergente.

L’approche étant très similaire à la méthode de Jacobi, et par manque de temps, nous avons choisi de ne pas l’étudier en profondeur et de ne pas en réaliser une version informatique.

La principale différence entre les deux méthodes est la décomposition de la matrice A.

Dans la méthode de Gauss-Seidel, on choisit

Alors que dans la méthode de Jacobi nous avons :

b- La méthode du gradient conjugué

La méthode du gradient conjugué a été mise au point en 1950 simultanément par Lanczos et Hestenes. Il s’agit d’une méthode itérative qui ne s’applique qu’aux matrices définies positivement symétriques. L’intérêt de cette méthode est qu’elle permet de trouver une approximation de la solution en un nombre d’itération égal à la taille du système.

Une méthode alternative dite « du gradient préconditionné » permet de réduire le nombre d’itérations par une initialisation astucieuse (préconditionnement) afin d’obtenir une estimation très proche de la solution exacte.

Cette méthode consiste en la construction par récurrence d’une base de vecteurs orthogonaux pour le produit scalaire et exprimer le vecteur solution dans cette base.

Pour choisir astucieusement le premier terme de la suite, on utilise l’intuition liée à la nature physique du problème. De ce fait, la méthode présente un peu moins d’intérêt pour nous, qui n’étudions que des systèmes abstraits et c’est, avec les contraintes de temps, la raison pour laquelle nous n’avons pas développé plus que cela l’étude de cette méthode qui a pourtant donné lieu à énormément de publications.

A noter qu’il existe une version généralisée aux matrices non-carrée nommée : « gradient biconjugué ».

c- Les systèmes non-carré

Comme évoqué en introduction, notre étude s’est principalement portée sur les systèmes carrés. Néanmoins, nous nous sommes sommairement intéressés en guise d’ouverture aux méthodes de résolution de systèmes quelconques.


On peut distinguer deux types de systèmes :

Les systèmes rectangulaires avec une infinité de solutions

Les systèmes rectangulaires avec une solution unique

Nous traiterons un exemple de chaque cas afin d’observer quelles sont ses particularités. La méthode utilisée est celle de Gauss-Jordan (ou de l’élimination de Gauss) consistant en la transformation d’un système initial

quelconque en un système équivalent plus simple . Concrètement, il s’agit de transformer la matrice A augmentée de son second membre b en une matrice échelonnée réduite A’ augmenté de son second membre b’ du type :

i. Systèmes rectangulaires avec infinité de solutions

Considérons le système suivant :

Voici son écriture sous forme matricielle :

On considère la matrice augmentée (A/B) , puis on applique l’élimination de Gauss afin

d’obtenir la forme échelon réduite de la matrice augmentée.

Dans un premier temps supprimons les premiers termes de la première colonne des lignes 2 et 3:

Faisons de même avec ceux de la 3ème

ligne et 3ème

colonne :

Forme échelonnée simple de (A/B)

Système à 3 équations et 4

inconnues systèmes avec

une infinité de solutions


Normalisons notre système :

Générons des « 0 » par remontée :

Colonnes de base contenant les pivots

Le système initial (E) se réduit à un système plus simple (E’) :

Exprimons les variables des colonnes de base en fonction des variables des colonnes hors base, c'est-à-dire

exprimons et en fonction de et .

(E’) :

D’où les solutions du système (E) :

Le système possède ici une infinité de solutions. Ceci s’explique par le fait qu’on ait à l’origine un système à trois équations (ou contraintes) pour quatre inconnues, et que l’une des trois équations est linéairement liée au deux autres, d’où la dépendance de deux variables aux deux autres.

Systèmes rectangulaires avec une solution unique

Considérons le système suivant :

Forme échelon réduite de (A/B)

Système à 4 équations et 3

inconnues système avec

possibilité d’une unique

solution si non redondance de

certaines équations


Voici son écriture sous forme matricielle :

On considère la matrice augmentée (A/B) , puis on applique l’élimination de Gauss afin

d’obtenir la forme échelon réduite de la matrice augmentée.

Dans un premier temps supprimons les premiers termes des lignes 2, 3 et 4 et de la première colonne :

Normalisons notre système :

Permutons les lignes 2, 3 et 4 afin d’échelonner la matrice:

Générons des « 0 » par remontée : puis

Le système initial (F) se réduit à un système plus simple à résoudre :

Ici, le système possède une unique solution. On a effectivement un système à 3 inconnues et 4 équations dont 3 sont indépendantes, d’où l’existence d’une seule et unique solution.

Colonnes de base contenant les pivots

Forme échelon

réduite

de (A/B)


V – Conditionnement

1- Problème de conditionnement

De nombreux problèmes rencontrés dans les domaines de la physique, de la chimie ou encore de la météorologie conduisent à la résolution de systèmes linéaires plus ou moins conséquents. Le plus souvent, les données de ces problèmes dépendent de mesures expérimentales connues avec une certaine erreur. En outre, il arrive parfois qu’une petite variation sur le second membre ou sur la matrice entraîne une grande variation sur la valeur du vecteur solution. Dans ce cas, le problème (ou la matrice) est dit mal conditionné.

Prenons un exemple :

On considère le système suivant

Par la méthode de Cholesky on trouve la solution du système .

Si on remplace le second membre initial par le vecteur suivant ., la méthode de Cholesky

nous donne la solution suivante .

On constate qu’une variation de sur le second membre peut entrainer une importante variation sur la solution, la rendant totalement inexploitable. Parfois, sur des systèmes très mal conditionnés on peut multiplier une erreur relative de 0.01 par des millions.

2- Solutions proposées

Les problèmes de « mauvais conditionnement » d’une matrice ou d’un problème font l’objet d’une étude approfondie qui constitue une discipline à part entière des mathématiques : le conditionnement. Cette discipline consiste en la mesure de la dépendance de la solution d'un problème numérique aux données du problème, ceci afin de contrôler la validité d'une solution calculée par rapport à ces données. Concrètement, ce calcul de dépendance consiste à majorer l’erreur relative sur la solution grâce à l’erreur relative sur les données du problème.

Pour ce faire, les mathématiciens on défini le nombre K(A) (relativement à une borne subordonnée) correspondant au conditionnement de la matrice A défini tel que :


Comme évoqué précédemment, deux situations peuvent se présenter : soit le second membre varie soit la matrice varie.

a- Cas où le second membre varie :

Soit le système Ax=b où les données sont la matrice A (considérée comme exacte) et le second membre b

connu avec une erreur . Majorons l’erreur relative sur la solution.

On a donc

Soit : (1)

On sait de plus que

Soit par combinaison des équations (1) et (2) on obtient :

Ainsi, selon le conditionnement K(A) de la matrice A et l’erreur relative commise sur le second membre on peut majorer l’erreur relative sur la solution et juger de son exactitude. Souvent on considère qu’un conditionnement environ égal à 1 est idéal.

b- Cas où la matrice varie :

Soit le système Ax=b où les données sont la matrice A connue avec une erreur δA et le second membre b supposé exact. Majorons l’erreur relative sur la solution.

Tout calcul fait on trouve que :

Ainsi, afin d’éviter les problèmes de mauvais conditionnement d’un problème l’idée serait de fixer une valeur maximale de l’écart relatif sur la solution, puis de le majorer grâce aux formules définies ci-avant afin de conclure sur la qualité de la résolution. Néanmoins, cette technique suppose le calcul de l’inverse d’une matrice qui très simple grâce à la méthode d’élimination de Gauss pour des systèmes de petites tailles mais qui peut s’avérer très lourd pour des systèmes d’ordre élevé.


IV – Conclusion

Ce projet mathématique a été l’occasion de découvrir plusieurs méthodes pour l’ingénieur de résolution de systèmes linéaires. C’est un outil de « tous les jours » pour l’ingénieur et donc une compétence non-négligeable que l’on a pu acquérir grâce à ce projet.

Nous pouvons désormais affirmer qu’il n’existe pas de méthode « magique » pour la résolution de système linéaire : il faut choisir l’algorithme en fonction de la situation (les contraintes sur la matrice liées à l’algorithme, la précision désirée, le matériel disponible, etc.).

De plus, le projet mathématique nous a appris à faire des recherches efficaces sur le domaine scientifique et à travailler en équipe. Les deux principaux objectifs que nous nous étions fixés ont donc été atteints.

Enfin, le domaine était extrêmement riche et intéressant, et nous avons malheureusement du passer sous silence dans ce mémoire bon nombre de choses qui nous ont pourtant intéressés. On peut citer les méthodes de relaxation, de surrelaxation successive appliquée aux méthodes itératives pour augmenter la rapidité de convergence, la décomposition QR pour les systèmes non-carrés ou encore les méthodes de Gauss par pivot total ou partiel.

L’étude plus poussée des algorithmes : tester leurs performances en parallélisation via MPI (Message Passing Interface), en GPGPU via CUDA (Compute Unified Device Architecture) par exemple, aurait été extrêmement intéressant.


Bibliographie

Sites Internet :

Nadir SOUALEM Résolution de systèmes linéaires, 2006

http://www.math-linux.com/spip.php?rubrique10

Wikipedia

http://fr.wikipedia.org/wiki/Gauss

http://fr.wikipedia.org/wiki/Jacobi

http://en.wikipedia.org/wiki/Jacobi_method

http://en.wikipedia.org/wiki/Cholesky_decomposition

*…+

Méthodes numériques pour l’ingénieur, département ASI, INSA-Rouen

http://asi.insa-rouen.fr/enseignement/siteUV/ananum/

Casa Maths, auteur non-identifié (professeur agrégé semble-t-il)

http://casa.maths.free.fr/documents/Mod%E9lisation/Conditionnement%20d%27un%20syst%E8me%20lin%E9aire.pdf

Ouvrages consultés :

Techniques du calcul matriciel de D.PHAM

Divers :

Cours d’analyse « Systèmes linéaires et matrices » INSA de Rennes 1ère

année de cycle STPI

Remerciements

Nous souhaitons remercier M. Adel Hamdi pour son aide et ses conseils tout au long du projet mathématique et M. Varea pour ses pistes utiles

http://www.math-linux.com/spip.php?rubrique10

http://fr.wikipedia.org/wiki/Gauss

http://fr.wikipedia.org/wiki/Jacobi

http://en.wikipedia.org/wiki/Jacobi_method

http://en.wikipedia.org/wiki/Cholesky_decomposition

http://asi.insa-rouen.fr/enseignement/siteUV/ananum/




Annexes

A1. ALGORITHME DE LANCZOS

Avoir une matrice à diagonale dominante n'est pas une condition nécessaire et suffisante pour avoir une suite vectorielle convergente comme nous avons pu le voir dans la méthode de Jacobi.

Il nous faut alors trouver les valeurs propres de notre matrice afin d'en déterminer le rayon spectral et s'assurer que celui-ci est inférieur à 1.

Pour cela, il existe l'algorithme de Lanczos que nous n'avons pas implémenté dans notre programme par manque de temps, mais dont nous souhaitions parler en annexe brièvement.

L’algorithme de Lanczos permet de transformer une matrice A en une matrice tridiagonale (c'est-à-dire une matrice dont tous les coefficients qui ne sont ni sur la diagonale principale, ni sur la diagonale juste au-dessus, ni sur la diagonale juste en-dessous, sont nuls). Par exemple (ici une matrice carrée de dimension m) :

Ensuite, pour trouver les valeurs propres et vecteurs propres associés, il faut utiliser une seconde méthode du type algorithme QR. Le procédé est rendu très simple par la nature tridiagonale de la matrice.

Il est à noter que cet algorithme est très utilisé tant l’utilité des valeurs propres et vecteurs propres est grande. On peut citer par exemple Google qui l’utilise pour son « PageRank », son algorithme d’analyse des liens concourant au système de classement des pages Internet.

A2. MÉTHODE D’ÉLIMINATION DE GAUSS POUR INVERSER UNE MATRICE CARRÉE

Inverser une matrice A carrée inversible d’ordre n, revient à résoudre n systèmes Afi = ei pour i allant de 1 à n. Pour cela, on créé un tableau à n lignes et 2n colonnes en bordant la matrice A par la matrice identité In.

Ainsi, pour inverser la matrice A=(ai j) de format (n, n), on utilisera la matrice augmentée suivante :


La transformation de Gauss-Jordan consiste à transformer ce système en un système équivalent dont le bloc gauche est l'identité, c'est-à-dire qu'il faut modifier la matrice (A | I) pour qu'elle devienne de la forme (I | A − 1) en utilisant les propriétés de l'algorithme.


Sources

S1. METHODE DE GAUSS

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <iostream>

#define DIM 200

using namespace std;

void triSup(double A[DIM][DIM], double B[DIM], int N) {

double c;

for(int i = 0; i < N-1; i++) {

for(int k = i+1; k < N; k++) {

c = A[k][i] / A[i][i];

B[k] = B[k] - c*B[i];

for(int j = i; j < N; j++)

A[k][j]= A[k][j] - c*A[i][j];

}

}

}

void solSup (double A[DIM][DIM] , double b[DIM] , double x[DIM], int N) {

double S;

for (int i = N-1; i >= 0; i--) {

S = 0;

for (int j = i + 1; j < N; j++) {

S = S + A[i][j]*x[j];

}

x[i] = (b[i] - S) / A[i][i];

}


}

void resolG(double A[DIM][DIM], double b[DIM], double x[DIM], int N) {

triSup(A, b, N);

solSup(A, b, x, N);

}

main(void) {

double a[DIM][DIM],b[DIM],x[DIM];

int n= 3;

// Initialisation

cout << "Entrez la dimension de la matrice : ";

cin >> n;

cout << endl;

cout << "Entrez la matrice (par ligne, en séparant les valeurs par des espaces : " << endl;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cin >> a[i][j];

}

}

cout << "Entrez le vecteur b : " << endl;

for (int i = 0; i < n; i++) {

cin >> b[i];

}

resolG (a, b, x, n);

cout << "Matrice A :" << endl;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cout << a[i][j] << " ";


}

cout << endl;

}

cout << endl << "Vecteur b :" << endl;

for (int i = 0; i < n; i++) {

cout << b[i] << endl;

}

cout << endl << "Vecteur x solution :" << endl;

for (int i = 0; i < n; i++) {

cout << x[i] << endl;

}

system("pause");

}


S2. DÉCOMPOSITION LU

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <iostream>

#define DIM 200


void lu(double L[DIM][DIM], double A[DIM][DIM], int N) {

double c = 0;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

L[i][j] = 0;

if (i==j)

L[i][j] = 1;

}

}

for(int i=0;i<N-1;i++) {

for(int k=i+1;k<N;k++) {

c = A[k][i]/A[i][i];

L[k][i] = c;

for(int j=i;j<N;j++)

A[k][j]= A[k][j] - c*A[i][j];

}

}

}

void solInf (double A[DIM][DIM], double b[DIM], double x[DIM], int N) {

double S = 0;

for (int i = 0; i <= N-1 ; i++) {

S = 0;


for (int j = 0; j <= i-1; j++)

S = S + A[i][j]*x[j];

x[i] = (b[i] - S) / A[i][i];

}

}

void solSup (double A[DIM][DIM], double b[DIM], double x[DIM], int N) {

double S = 0;

for (int i = N-1; i >= 0; i--) {

S = 0;

for (int j = i + 1; j < N; j++)

S = S + A[i][j]*x[j];

x[i] = (b[i] - S) / A[i][i];

}

}

void resolLu (double A[DIM][DIM], double b[DIM], double x[DIM], int n) {

solInf(A, b, x, n);

solSup(A, b, x, n);

}

main(void) {

double a[DIM][DIM],b[DIM],x[DIM], L[DIM][DIM];

int n= 3;

// Initialisation


cin >> n;

cout << endl;


for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {


cin >> a[i][j];

}

}


for (int i = 0; i < n; i++) {

cin >> b[i];

}

triSup(a, b, n);

lu(L, a, n);

resolLu (a, b, x, n);


for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cout << a[i][j] << " ";

}

cout << endl;

}


for (int i = 0; i < n; i++) {


}


for (int i = 0; i < n; i++) {


}

system("pause");

}


S3. FACTORISATION DE CHOLESKY

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <iostream>

#define DIM 200


void solInf (double A[DIM][DIM], double b[DIM], double x[DIM], int N) {

double S = 0;

for (int i = 0; i <= N-1 ; i++) {

S = 0;

for (int j = 0; j <= i-1; j++)

S = S + A[i][j]*x[j];

x[i] = (b[i] - S) / A[i][i];

}

}

void solSup (double A[DIM][DIM], double b[DIM], double x[DIM], int N) {

double S = 0;

for (int i = N-1; i >= 0; i--) {

S = 0;

for (int j = i + 1; j < N; j++)

S = S + A[i][j]*x[j];

x[i] = (b[i] - S) / A[i][i];

}

}

void cholesk(double A[DIM][DIM], double L[DIM][DIM], int N) {


double S, F, M;

M = 0;

for (int i = 0; i < N ; i++)

for (int j = 0; j < N ; j++)

L[i][j] = 0;

for (int i = 0; i < N-1; i++) {

S = 0.0;

for (int k = 0; k < i; k++)

S = S + (L[i][k])*(L[i][k]);

L[i][i] = sqrt(A[i][i] - S);

for (int j = 1 + i; j < N; j++) {

F = 0.0;

for (int k = 0; k < i; k++)

F = F + (L[j][k])*(L[i][k]);

L[j][i] = (A[j][i] - F)/ L[i][i];

}

}

for (int j = 0; j < N-1; j++)

M = M + (L[N-1][j])*(L[N-1][j]);

L[N-1][N-1] = sqrt (A[N-1][N-1] - M);

}

void choleskResol(double A[DIM][DIM], int N, double L[DIM][DIM], double b[DIM], double x[DIM]) {

double Y[DIM], M[DIM][DIM];

cholesk(A,L,N);

for(int i = 0; i < N; i++)

for(int j = 0; j < N; j++)


M[i][j]=L[j][i];

solInf(L, b, Y, N);

solSup(M, Y, x, N);

}

main(void) {

double a[DIM][DIM],b[DIM],x[DIM], L[DIM][DIM];

int n= 3;

// Initialisation


cin >> n;

cout << endl;


for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cin >> a[i][j];

}

}


for (int i = 0; i < n; i++) {

cin >> b[i];

}

cholesk(a,L,n);

choleskResol (a, n, L, b, x);


for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {


cout << a[i][j] << " ";

}

cout << endl;

}


for (int i = 0; i < n; i++) {


}


for (int i = 0; i < n; i++) {


}

system("pause");

}


S4. METHODE DE JACOBI

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <iostream>

#define DIM 200


int isConv(double X[DIM],double XS[DIM],double eps,int n)

{

double s=0.00;

for(int i=0;i<n;i++)

s+=pow((X[i]-XS[i]),2);

s=sqrt(s);

if (s>eps)

return(0);

return(1);

}

void jacobi (double a[DIM][DIM], double x[DIM], double x0[DIM], double b[DIM], int n) {

for(int i=0;i<n;i++) // On redéfinit x0 comme étant l'élément d'ordre n-1 de la suite

x0[i]=x[i];

for(int i=0;i<n;i++) // Methode de Jacobi

{

x[i]=b[i];

for(int j=0;j<i;j++)

x[i]-=a[i][j]*x0[j];// Calcul des éléments du vecteur x (d'ordre n) à patir de ceux du vecteur x0 (d'ordre n-1)

for(int j=i+1;j<n;j++)

x[i]-=a[i][j]*x0[j];

x[i]=(x[i]/a[i][i]);

}


}

int main()

{

double a[DIM][DIM],b[DIM],x[DIM],j[DIM][DIM],x0[DIM];

int n = 2;

int it = 0; // Compteur d'itérations

double eps = 0; // Epsilon, précision et condition pour le test d'arrêt

// Initialisation


cin >> n;

cout << endl;


for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cin >> a[i][j];

}

}


for (int i = 0; i < n; i++) {

cin >> b[i];

}

cout << "Entrez le vecteur x0 : " << endl;

for (int i = 0; i < n; i++) {

cin >> x0[i];

}

cout << "Entrez la precision desiree : ";

cin >> eps;

cout << endl;


while(!isConv(x,x0,eps,n)) // Tant que la convergence est vérifiée

{

jacobi (a, x, x0, b, n);

it++;

}

// Affichage


for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cout << a[i][j] << " ";

}

cout << endl;

}


for (int i = 0; i < n; i++) {


}


for (int i = 0; i < n; i++) {


}

cout << endl << "Iterations : " << it <<endl;

cout << "Precision : " << eps << endl;

system("pause");

}


S4. PROGRAMME PRINCIPAL

Les sources du programme principal n’étant qu’une réunion des sources de méthodes précédentes, nous n’avons pas jugé utile de les mettre ici.

Cependant, vous pouvez les télécharger à l’adresse suivante : http://linear.alwaysdata.net

Documents

Memoire