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

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\times 3$ . Pour une matrice $n\times n$ , il faut calculer le déterminant de la matrice elle-même et calculer $n^2$ déterminants des matrices $(n-1)\times(n-1)$ . 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.

linear-algebra matrix complexity Stefan Smith
la source

Réponses:

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 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(n^3)$

Wolfgang Bangerth
la source

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

. De plus, en général, vous ne voulez pas calculer un inverse à moins que vous ne deviez absolument le faire.

O (n!)

$O(n!)$

O (n^{3})

$O(n^3)$

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!)

$O(n!)$

@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

det (A B) = det (A) det (B)

$\det(\mathbf A\mathbf B)=\det(\mathbf A)\det(\mathbf B)$

effort.

O (n^{3})

$O(n^3)$

L U

$LU$

n

$n$

n!

$n!$

O (n^{5})

$O(n^5)$

L U

$LU$

A

$A$

U

$U$

L

$L$

Wolfgang Bangerth

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