A “técnica de cofator” para inverter uma matriz tem algum significado prático?

O título é a pergunta. Essa técnica envolve o uso da "matriz de cofatores", ou "matriz de adjuntos" e fornece fórmulas explícitas para os componentes do inverso de uma matriz quadrada. Não é fácil fazer manualmente uma matriz maior que, digamos, $3\times 3$ . Para um $n\times n$ matriz, requer computar o determinante da própria matriz e computação $n^2$ determinantes de $(n-1)\times(n-1)$ matrizes. Então, acho que não é tão útil para aplicativos. Mas eu gostaria de confirmação.

Não estou perguntando sobre o significado teórico da técnica para provar teoremas sobre matrizes.

linear-algebra matrix complexity Stefan Smith
fonte

Respostas:

Você está certo - não tem absolutamente nenhuma relevância prática para a computação. Mesmo que a computação do determinante fosse uma operação , a complexidade do método seria pelo menos e, consequentemente, da mesma complexidade da eliminação gaussiana. Na prática, calcular o determinante de uma matriz é, na verdade, de complexidade exponencial, tornando esse método completamente inutilizável. $O(n)$ $O(n^3)$

Wolfgang Bangerth
fonte

Duas coisas que quero acrescentar: A complexidade da Regra de Cramer (usar determina para calcular um inverso) é

Que é muito, muito, muito maior que a Eliminação Gaussiana

. Além disso, em geral, você não deseja calcular um inverso, a menos que seja absolutamente necessário.

O (n!)

$O(n!)$

O (n^{3})

$O(n^3)$

Paul

OTOH, pode haver algumas circunstâncias em que a expansão de Laplace pode ser preferida, por exemplo, matrizes em faixas. Mas, de fato, em geral, a expansão de Laplace tem complexidade

O (n!)

$O(n!)$

@ Stefan, sim, a eliminação gaussiana pode ser usada para calcular determinantes. Como

e a eliminação gaussiana produzem fatores (triangulares) cujos determinantes são facilmente calculados, será necessário

esforço de

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

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

O (n^{3})

$O(n^3)$

Sim, você está correto - o determinante pode ser calculado ao custo de uma decomposição

(A maneira ingênua mostrado nos livros de texto usando a expansão recursiva é exponencial em

- o

Complexidade mencionado por Paulo). Mas isso ainda gera uma complexidade geral de

para o algoritmo proposto - muito mais do que a eliminação gaussiana, se for para usá-lo, e ainda mais do que solucionadores iterativos.

L U

$LU$

n

$n$

n!

$n!$

O (n^{5})

$O(n^5)$

Wolfgang Bangerth

Corrigir. A redução de linha é metade da computação da decomposição

Reduz

ao fator

A outra metade do trabalho está fazendo as mesmas operações a partir da matriz de identidade, produzindo a matriz

É verdade que você pode evitá-lo se tudo o que importa é o determinante.

L U

$LU$

A

$A$

U

$U$

L

$L$

Wolfgang Bangerth

Eu estou indo contra a multidão - a matriz adjunta é de fato muito útil para algumas aplicações especializadas com pequena dimensionalidade (como quatro ou menos), especialmente quando você precisa do inverso de uma matriz, mas não se importa com escala.

Dois exemplos incluem o cálculo de um inverso homografia e a iteração do quociente de Rayleigh para problemas muito pequenos (que, além de simplificados pelo uso de adjugado, são numericamente melhores).

sem cesto
fonte

Concordo plenamente, há alguns casos (em geral com pequenas matrizes) em que isso ajuda muito! (Por exemplo, para calcular coordenadas baricêntricas numa pequena simplex)

BrunoLevy