Systèmes d’équations linéaires

Visites depuis le 14 juin 2002

Table des matières
Joindre l'auteur

Chapitre II : Systèmes d'équations linéaires

Plan

2. Equations et systèmes linéaires dans MATLAB

3. Méthode directe (Méthode du pivot)

4. Méthodes itératives
4.1. Méthode de Jacobi
4.2. Méthode de Gauss-Seidel

Avant de commencer les calculs numériques relatifs à l’application directe du cours de ‘Méthodes Numériques’, il est indispensable de savoir les informations nécessaires concernant l’algèbre linéaire sur MATLAB. L’objectif de cette étude est de donner à l’étudiant les bases fondamentales de l’algèbre linéaire concernant la résolution des systèmes d’équations linéaires.

1. Matrices et Vecteurs dans MATLAB

En mathématique, une matrice est constituée de n lignes et de m colonnes. Les coefficients de la matrice sont situés entre 2 parenthèses. Dans MATLAB, les parenthèses n’y figurent pas.

Une matrice carrée est une matrice dont le nombre de lignes est égal au nombre de colonnes (n=m). Une matrice ligne est une matrice d’ordre 1 appelée vecteur ligne. Une matrice colonne est une matrice d’ordre 1 appelée vecteur colonne. Une matrice d’ordre 0 est un scalaire.

Dans le cas général, une matrice de n lignes et de m colonnes a pour coefficients , où et . Si cette matrice est appelée A, ses coefficients sont les suivant :

Si B est autre matrice à p lignes et q colonnes, alors le produit de C=A*B n’est possible que si m=p. Dans ce cas, le coefficient c₁₁, par exemple de cette matrice C s’écrit :

(avec m=p).

Dans Matlab, la matrice produit C (= A*B) a pour coefficients c_ij. Ces coefficients sont calculés en fonction de a_ij et de b_ij :

Une matrice d’ordre zéro est une matrice à une ligne et une colonne : elle représente un scalaire. Une matrice nulle est une matrice dont les coefficients sont tous nuls. En attribuant le nom ‘A’ à cette matrice, alors dans Matlab A s’écrit :

>>A=zeros(n,m)

où n et m sont respectivement le nombre de lignes et le nombre de colonnes.

La matrice identité est définie dans Matlab par la fonction : ‘eye’

Exemple :

C’est une matrice carrée d’ordre 5. Dans Matlab, on peut l’écrire :

>>B=eye(5)
B =
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Si B^t est la matrice transposée de B, cette dernière s’écrit dans Matlab :

>>C=B' à (l’appostrophe représente la transposée)

C =
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Le déterminant d’une matrice carrée (C par exemple) est donné par :

>>det(C)
ans =
1

Soit A une matrice non nulle. La matrice inverse A^-1 de A (si elle existe) est telle que :

A*A^-1=IId

Dans Matlab, cette matrice inverse est donnée par :

A^-1=A^(-1)=inv(A)=pinv(A)

Exemple :

>>A=[1 3 5;2 -1 0;5 4 3]

A =
1 3 5
2 -1 0
5 4 3

La matrice inverse de A est :

>>inv(A)
ans =
-0.0682 0.2500 0.1136
-0.1364 -0.5000 0.2273
0.2955 0.2500 -0.1591

ou encore :

>>pinv(A)
ans =
-0.0682 0.2500 0.1136
-0.1364 -0.5000 0.2273
0.2955 0.2500 -0.1591

2. Equations et systèmes linéaires dans MATLAB

Considérons le systèmes suivants de n équations à m inconnues :

Dans ce système, on a connue, connues et inconnues.

Si n>m système sur-déterminé,
Si n=m système de Cramer à une solution unique (si det(A)),
Si n<m système sous-déterminé

La solution numérique du système (pour n=m) donne les inconnues x_i :

x=A/y
Pour un vecteur colonne y donné ( par exemple), la solution par Matlab est :
>>x=A^(-1)*y
x =
-0.5227
-1.0455
1.9318

Notation :

Soit la matrice :

Dans Matlab, la Matrice A peut être écrite sous les deux formes :

>>A=[1,3,5;2,-1,0;5,4,3];

ou bien :

>>A=[1 3 5;2 -1 0;5 4 3];

La séparation des lignes se fait par un point virgule et la séparation des colonnes se fait par un espace ou une virgule.

Exemple :

>>A=[1 3 5;2 -1 0;5 4 3]
A =
1 3 5
2 -1 0
5 4 3

Problèmes mal conditionnés :

Il existe un certain nombre d’équations linéaires solvables, mais leurs solutions sont incertaines à cause des erreurs d’arrondi lors des calculs. Les problèmes de ce type sont appelés ‘problèmes mal conditionnés’. L’arrondi durant les calculs ou les petits changements dans les coefficients calculés peuvent induire des erreurs significatives dans la résolution d’un problème (mal conditionné).

Cet effet d’arrondi, peut être illustré par le système des 2 équations suivantes, par exemple :

La solution de ce système est :

Pour monter l’erreur introduite sur les solutions en modifiant les coefficients (arrondi), on donne au coefficient ‘2,01045’ de la première équation une légère augmentation de ‘0,001’.

Dans ce cas, le système devient :

Ceci met en évidence l'erreur engendrée par un arrondi.

La matrice C correspondant au système précédent est :

La norme de C s’écrit :

Dans Matlab on définit le nombre-condition de la matrice C [notation cond(C)] par :

Ce nombre satisfait toujours la condition :

Pour les matrices inconditionnées, ce nombre-condition attiend des grandes valeurs, mais ne donne pas une estimation directe de l’erreur sur la solution.

Dans Matlab, ce nombre se calcule par la fonction ‘cond(C)’ où C est la matrice.

Exemple1 :

>>C
C =
0.1206 0.9878 0.9876

>>cond(C)
ans =
6.5598e+003

Exemple2 :

L'exemple de la matrice d’Hilbert représente un problème à matrice mal conditionnée. Cette matrice est définie par :

, où

Programmer le nombre-condition (cond(A)) ainsi que det(A).det(A^-1) pour une matrice d’Hilbert de 5 par 5 à 14 par 14 :

Solution :

clear;
for n=5:14
for i=1:n
for j=1:n
a(i,j)=1/(i+j-1);
end
end
C=cond(a);
d=det(a)*det(a^(-1));
fprintf('n=%3.0f\t cond(a)=%e\t det*det=%e\n',n,C,d);
end

Après exécution du programme, on obtient les résultats suivants :

n= 5 cond(a)=4.766073e+005 det*det=1.000000e+000
n= 6 cond(a)=1.495106e+007 det*det=1.000000e+000
n= 7 cond(a)=4.753674e+008 det*det=1.000000e+000
n= 8 cond(a)=1.525758e+010 det*det=9.999999e-001
n= 9 cond(a)=4.931532e+011 det*det=1.000001e+000
n= 10 cond(a)=1.602534e+013 det*det=9.999812e-001
n= 11 cond(a)=5.218389e+014 det*det=1.000119e+000
n= 12 cond(a)=1.768065e+016 det*det=1.015201e+000
n= 13 cond(a)=3.682278e+018 det*det=9.707419e-001
n= 14 cond(a)=1.557018e+018 det*det=-4.325761e+000

Durant l’exécution du programme, un message s’affiche sur l’écran pour n=11 à n=14 :
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.659249e-017.

Ce qui signifie qu’à partir de n=11 jusqu’à n=14, on a det(a)*det(a^-1) différent de 1, donc les erreurs d’arrondi commencent leurs apparitions.

3. Méthode directe (Méthode du pivot)

Soit à résoudre le système suivant de 3 équations à 3 inconnues par la méthode du pivot (dans Matlab) :

déterminer .

Solution :

1. On définit tout d’abord la matrice argument dans Matlab par :

>>A=[-0.04 0.04 0.12 3;0.56 -1.56 0.32 1; -0.24 1.24 -0.28 0] ;

2. On choisit la ligne 1 comme ligne pivot : a(1,1)=-0.04,

on divise la ligne 1 par a(1,1) à b(1,:)=a(1,:)/a(1,1) à nouvelle ligne,

on annule le 1^er terme de la ligne 2 et le 1^er terme de la ligne 3 :

à b(2,:)=a(2,:)-b(1,:)*a(2,1),
à b(3,:)=a(3,:)-b(1,:)*a(3,1).

On obtient après calculs :

b =
1 -1 -3 -75
0 -1 2 43
0 1 -1 -18

3. On choisit la ligne 2 comme ligne pivot.

On divise cette ligne par b(2,2)=-1, on obtient :

à c(2,:)=b(2,:)/b(2,2) à nouvelle ligne = 0 1 -2 -43

on annule le terme b(1,2) de la ligne 1 et le terme b(3.2) de la ligne 3 :

à c(1,:)=b(1,:)-c(2,:)*b(1,2) à 1 0 -5 118,
à c(3,:)=b(3,:)-c(2,:)*b(3,2) à 0 0 1 25.

4. On choisit la ligne 3 comme ligne pivot c(3, :).

On divise cette ligne par c(3,3)=1, on obtient :

à d(3,:)=c(3,:) à nouvelle ligne = 0 0 1 25

on annule dans la ligne 1 c(1,3) et dans la ligne 2 c(2,3) :

à d(1,:)=c(1,:)-d(3,:)*c(1,3) à 1 0 0 7,
à d(2,:)=c(2,:)-d(3,:)*c(2,3) à 0 1 0 7.

D’où la matrice d s’écrit :

d =
1 0 0 7
0 1 0 7
0 0 1 25

et la solution est :

L’algorithme suivant (dans Matlab) permet de résoudre le système précédent :

clear %effacer toutes les variables en mémoire dans Matlab
a=[-0.04 0.04 0.12 3;0.56 -1.56 0.32 1;-0.24 1.24 -0.28 0];a
x=[0 0 0]'; %x est le vecteur colonne de composantes xi qui est initialisé ici
% 1er point pivot ligne 1 -calculs sur les lignes 2 et 3
b(1,:)=a(1,:)/a(1,1);
b(2,:)=a(2,:)-b(1,:)*a(2,1);
b(3,:)=a(3,:)-b(1,:)*a(3,1);b
% 2ème pivot ligne 2 - calculs sur les lignes 1 et 3
c(2,:)=b(2,:)/b(2,2);
c(1,:)=b(1,:)-c(2,:)*b(1,2);
c(3,:)=b(3,:)-c(2,:)*b(3,2);c
% 3ème pivot ligne 3 - calculs sur les lignes 1 et 2
d(3,:)=c(3,:)/c(3,3);
d(1,:)=c(1,:)-d(3,:)*c(1,3);
d(2,:)=c(2,:)-d(3,:)*c(2,3);d
%Solutions recherchées
x(1)=d(1,4);
x(2)=d(2,4);
x(3)=d(3,4);x

après l’exécution de ce programme, on obtient :

a =
-0.0400 0.0400 0.1200 3.0000
0.5600 -1.5600 0.3200 1.0000
-0.2400 1.2400 -0.2800 0

b =
1.0000 -1.0000 -3.0000 -75.0000
0 -1.0000 2.0000 43.0000
0 1.0000 -1.0000 -18.0000

c =
1.0000 0 -5.0000 -118.0000
0 1.0000 -2.0000 -43.0000
0 0 1.0000 25.0000

d =
1.0000 0 0 7.0000
0 1.0000 0 7.0000
0 0 1.0000 25.0000

x =
7.0000
7.0000
25.0000

4. Méthodes itératives

4.1. Méthode de Jacobi

Résoudre le système suivant par la méthode itérative de Jacobi :

Écrire un algorithme permettant de calculer x₁, x₂ et x₃ par itérations. Déterminer le nombre d’itérations nécessaires pour obtenir :

Solution :
Appelons l’algorithme permettant de calculer la solution ‘jacobi.m’. Dans cet algorithme, nous avons utilisé un facteur de relaxation "l" pour réaliser la convergence, car sinon le système diverge.

4.2. Méthode de Gauss-Seidel

Résoudre le même système précédent par la méthode de Gauss-Seidel. Écrire un algorithme (Matlab) permettant de résoudre ce système et déterminer le nombre d’itérations nécessaires pour obtenir une erreur .

Comparer les résultats avec la méthode de Jacobi et conclure.

Représenter sur le même graphe l’évolution des solutions en fonction du nombre d’itérations. Changer les valeurs initiales , exécuter le programme puis conclure.

Solution :

* Méthode itérative générale :

Appelons l’algorithme permettant de calculer la solution ‘G-seid.m’
On se donne des valeurs arbitraires : par exemple =0. Le système à résoudre est :
A*x=y ; où , et

La matrice A et le vecteur colonne y sont connus, le vecteur colonne x reste inconnu. Ainsi, la méthode itérative générale consiste à écrire :

pour et .

En particulier, pour un système de 3 équations à 3 inconnues, on a :

i=1 à j=2 et 3

i=2 à j=1 et 3

i=3 à j=1 et 2

et ceci pour chaque itération.

Programme itmg.m :

%******************************
% Résolution d'un système linéaire *
% par la méthode itérative générale *
%******************************

clear all;
clc;
fprintf('Méthode itérative générale\n');
n=30000;
a=[1 1 1;2 -1 3;3 2 -2];
y=[1 4 -2];
x=zeros(1,3);

w=0.2; % facteur de relaxation : 0<w<1

epsilon=1e-10;
for k=1:n
    erreur=0;
    for i=1:3
        s=0;
        xb=x(i);
        for j=1:3
            if i~=j
                s=s+a(i,j)*x(j);
            end
        end
        x(i)=w*(y(i)-s)/a(i,i)+(1-w)*x(i);
        erreur=erreur+abs(x(i)-xb);
    end
        if (erreur/3<epsilon)
        fprintf('Itération no. : %d\t Erreur = %7.2e\n',k,erreur);
        break;
    end
end
x

* Méthode de Jacobi :

Modifier le programme précédent pour résoudre le système par la méthode de Jacobi. Exécuter le programme et comparer le nombre d'itérations par rapport à celui de la méthode générale.