La «technique du cofacteur» pour inverser une matrice a-t-elle une signification pratique?

13

Le titre est la question. Cette technique consiste à utiliser la «matrice des cofacteurs», ou «matrice adjugée», et donne des formules explicites pour les composantes de l'inverse d'une matrice carrée. Ce n'est pas facile à faire à la main pour une matrice plus grande que, disons, 3×3 . Pour une matrice n×n , il faut calculer le déterminant de la matrice elle-même et calculer n2 déterminants des matrices (n1)×(n1) . Je suppose donc que ce n'est pas très utile pour les applications. Mais j'aimerais une confirmation.

Je ne pose pas de question sur la signification théorique de la technique pour prouver des théorèmes sur les matrices.

Stefan Smith
la source

Réponses:

11

Vous avez raison - cela n'a absolument aucune pertinence pratique pour l'informatique. Même si le calcul du déterminant était une opération , la complexité de la méthode serait au moins O ( n 3 ) et, par conséquent, de la même complexité que l'élimination gaussienne. En pratique, le calcul du déterminant d'une matrice est en fait d'une complexité exponentielle, rendant cette méthode totalement inutilisable.O(n)O(n3)

Wolfgang Bangerth
la source
4
Deux choses que je veux ajouter: La complexité de la règle de Cramer (en utilisant des déterminés pour calculer une inverse) est Qui est beaucoup plus grande que l'élimination gaussienne O ( n 3 ) . De plus, en général, vous ne voulez pas calculer un inverse à moins que vous ne deviez absolument le faire. O(n!)O(n3)
Paul
OTOH, il pourrait y avoir des circonstances où l'expansion de Laplace pourrait être préférée, par exemple des matrices à bandes. Mais en effet, en général, l'expansion de Laplace a une complexité . O(n!)
JM
3
@Stefan, oui, l'élimination gaussienne peut être utilisée pour calculer les déterminants. Puisque , et que l'élimination gaussienne produit des facteurs (triangulaires) dont les déterminants sont facilement calculables, il faudra en effet O ( n 3det(AB)=det(A)det(B) effort. O(n3)
JM
1
LUnn!O(n5)
1
LUAUL
Wolfgang Bangerth
9

Je vais contre la foule - la matrice adjugée est en fait très utile pour certaines applications spécialisées avec une petite dimensionnalité (comme quatre ou moins), en particulier lorsque vous avez besoin de l'inverse d'une matrice mais ne vous souciez pas de l'échelle.

Deux exemples incluent le calcul d'une homographie inverse et l' itération de quotient de Rayleigh pour de très petits problèmes (qui en plus d'être simplifiés par l'utilisation de adjugate est numériquement meilleur).

sans panier
la source
Je suis entièrement d'accord, il y a des cas (en général avec de petites matrices) où ça aide beaucoup! (par exemple, pour calculer les coordonnées barycentriques dans un petit simplex)
BrunoLevy