Inversion de matrice - résolution de systèmes d'équations linéaires

Soyez le premier à donner votre avis sur cette source.

Vue 29 421 fois - Téléchargée 794 fois

Description

Il est souvent pratique de résoudre des systèmes d'équations linéaires.
Je me suis donc lancé dans l'inversion de matrices.
J'ai utilisé la formule A^(-1) = (1/dét(A))*tcom(A)

Mon code comprend donc :
- une fonction qui calcule le déterminant de matrices carrées
- une procédure pour calculer la transposée
- une procédure pour calculer les matrices mineures (on enlève une ligne et une colonne)
- une procédure de calcul des cofacteurs (=déterminant de la matrice mineure à un coefficient -1 près)
- et finalement une procédure de calcul de la matrice inverse

Enfin, une procédure de multiplication de matrice permet d'obtenir la solution d'un système A*X=B (car B = A^(-1)*B)

Source / Exemple :


Function deter_vb(mat() As Double)
'cette fonction nécessite uniquement une matrice d'entrée carrée : mat()
Dim i As Integer, j As Integer
Dim dim1 As Long, dim1_1 As Long
Dim mat_min() As Double
Dim deter As Double, deter_1 As Double

    'Vérification portant sur la matrice qui doit être carrée
    dim1 = UBound(mat, 1)
    If dim1 <> UBound(mat, 2) Then
        MsgBox "la matrice doit être carrée"
    End If
    'Initialisation de la valeur à 0
    déter = 0
    
    If dim1 = 1 Then
    'si la matrice est de dimension 1, le déterminant est trivialement égal au coef a11
        deter = mat(1, 1)
    Else
    'sinon, il faut décomposer le déterminant en une somme de n déterminants de dimension (n - 1)
        For j = 1 To dim1
            'appel de la procédure de calcul de la comatrice de la matrice d'entrée pour i = 1 et le j en cours
            Call mat_mineur(mat(), 1, j, mat_min(), dim1_1)
            'appel de la procédure de calcul du déterminant de la comatrice (de dimension (n-1))
            deter_1 = deter_vb(mat_min())
            'ajout du terme correspondant au déterminant de la comatrice
            deter = deter + (-1) ^ (1 + j) * mat(1, j) * deter_1
        Next j
    End If
    deter_vb = deter
End Function

Sub mat_mul(mat1() As Double, mat2() As Double, mat3() As Double)
Dim i As Integer, j As Integer, k As Integer
Dim dimx1 As Long, dimy1 As Long
Dim dimx2 As Long, dimy2 As Long
    
    dimx1 = UBound(mat1, 1)
    dimy1 = UBound(mat1, 2)
    dimx2 = UBound(mat2, 1)
    dimy2 = UBound(mat2, 2)
    
    If dimy1 <> dimx2 Then
        MsgBox "les dimensions des deux matrices sont incompatibles"
    End If
    
    ReDim mat3(1 To dimx1, 1 To dimy2)
    For i = 1 To dimx1
        For j = 1 To dimy2
            mat3(i, j) = 0
            For k = 1 To dimx2
                mat3(i, j) = mat3(i, j) + mat1(i, k) * mat2(k, j)
            Next k
        Next j
    Next i
    
End Sub

Sub mat_inverse(mat() As Double, mat_inv() As Double)
Dim i As Integer, j As Integer
Dim dim1 As Long
    
    'Vérification portant sur la matrice qui doit être carrée
    dim1 = UBound(mat, 1)
    If dim1 <> UBound(mat, 2) Then
        MsgBox "la matrice doit être carrée"
    End If
    
    ReDim mat_inv(1 To dim1, 1 To dim1)
    Dim deter As Double
    Dim mat_compl() As Double
    
    deter = deter_vb(mat())
    
    If deter = 0 Then
        MsgBox "la matrice n'est pas inversible car son déterminant est nul !"
    Else
        Call mat_complementaire(mat(), mat_compl())
        
        For i = 1 To dim1
            For j = 1 To dim1
                mat_inv(i, j) = (1 / deter) * mat_compl(i, j)
            Next j
        Next i
    End If
    
End Sub

Sub mat_transposee(mat() As Double, mat_transp() As Double)
Dim i As Integer, j As Integer, k As Integer
Dim dimx As Long, dimy As Long
    
    dimx = UBound(mat, 1)
    dimy = UBound(mat, 2)
    
    ReDim mat_transp(1 To dimy, 1 To dimx)
    For i = 1 To dimy
        For j = 1 To dimx
            mat_transp(i, j) = mat(j, i)
        Next j
    Next i
    
End Sub

Sub mat_complementaire(mat() As Double, mat_compl() As Double)
Dim i As Integer, j As Integer
Dim dim1 As Integer

    'Vérification portant sur la matrice qui doit être carrée
    dim1 = UBound(mat, 1)
    If dim1 <> UBound(mat, 2) Then
        MsgBox "la matrice doit être carrée"
    End If
    
    Dim mat_cof() As Double
    
    Call mat_cofacteur(mat(), mat_cof())
    Call mat_transposee(mat_cof(), mat_compl())
    
End Sub

Sub mat_cofacteur(mat() As Double, mat_cof() As Double)
Dim i As Integer, j As Integer
Dim dim1 As Long, dim2 As Long
Dim deter As Double

    'Vérification portant sur la matrice qui doit être carrée
    dim1 = UBound(mat, 1)
    If dim1 <> UBound(mat, 2) Then
        MsgBox "la matrice doit être carrée"
    End If
    
    Dim mat_min() As Double
    ReDim mat_cof(1 To dim1, 1 To dim1) As Double
    
    For i = 1 To dim1
        For j = 1 To dim1
            'Appel de la procédure de calcul de la matrice mineure de la matrice d'entrée (ligne i et colonne j)
            Call mat_mineur(mat(), i, j, mat_min(), dim2)
            'Appel de la procédure de calcul du déterminant de la comatrice (de dimension (n-1))
            deter = deter_vb(mat_min())
            mat_cof(i, j) = (-1) ^ (i + j) * deter
        Next j
    Next i
    
End Sub

Sub mat_mineur(mat() As Double, lig As Integer, col As Integer, mat_min() As Double, dim2 As Long)
Dim i As Integer, j As Integer
Dim i_co As Integer, j_co As Integer
Dim dim1 As Long
    
    dim1 = UBound(mat, 1)
    dim2 = dim1 - 1
    
    ReDim mat_min(1 To dim2, 1 To dim2)
    i_co = 0
    For i = 1 To dim1
        If i <> lig Then i_co = i_co + 1
        j_co = 0
        For j = 1 To dim1
            If j <> col Then j_co = j_co + 1
            If i <> lig And j <> col Then
                mat_min(i_co, j_co) = mat(i, j)
            End If
        Next j
    Next i
    
End Sub

Conclusion :


Ca semble bien fonctionner sur des cas de matrice simples (comparaison avec les résultats issus des fonctions d'Excel).

Mais n'hésitez pas à me faire part de vos remarques, notamment si vous détectez un problème.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_janhsh
Messages postés
32
Date d'inscription
lundi 6 novembre 2000
Statut
Membre
Dernière intervention
24 janvier 2015
-
C'est bien d'un point de vue théorique, pour les matheux, mais pas utilisable en pratique.

Ton algorithme est O(n!) rien que par le calcul du déterminant ... Si tu a une matrice de 100 x 100, il te faudra très longtemps pour l'inverse avec cet algorithme. (en jours et plus...)

De plus, pour des problèmes réels, le résultat sera erroné a cause du principe de la virgule flotante. (Sur ordinateur, les nombres étant stocké de façon échantilionnés avec une perte de précision).

En pratique, pour résoudre un système d'équations linéaire, on n'inverse jamais une matrice.
on utilise plutôt des méthodes comme la décomposition LU et la décomposition QR
On peut aussi utiliser des méthodes comme Gauß Doolittle, Gauß-Jordan O(n^3), Strassen O(n^2.807), Coppersmith-Winograd O(n^2,378), Banachiewicz, ...

Ces méthodes sont beaucoups plus précise et plus rapides même si l'algorithme est plus complexe.
caco64
Messages postés
69
Date d'inscription
jeudi 27 septembre 2007
Statut
Membre
Dernière intervention
14 décembre 2007
-
J'avais cru comprendre en effet que cette méthode était en o(n!), mais c'est vrai qu'en ce qui me concerne, les matrices que j'utilise dépassent rarement la dimension 6 ou 7, le temps de résolution n'est alors plus véritablement un pb.

J'ai également programmé un algo basé sur la méthode de triangulation qui doit être en o(n^3) si je ne me trompe pas. Par contre, je ne connaissais pas l'existence de ces algo en o(n^2....)

Merci beaucoup pour tes remarques JANSH, ça m'a permis de tester qu'effectivement une matrice 100*100, ça coince dur.
ombredoree
Messages postés
1
Date d'inscription
lundi 6 novembre 2000
Statut
Membre
Dernière intervention
23 novembre 2007
-
..La critique est aisée, mais l'art est difficile!

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.