Apakah "teknik kofaktor" untuk membalik matriks memiliki makna praktis?

Judulnya adalah pertanyaan. Teknik ini melibatkan penggunaan "matriks kofaktor", atau "matriks adjugate", dan memberikan formula eksplisit untuk komponen kebalikan dari matriks kuadrat. Tidak mudah dilakukan dengan tangan untuk sebuah matriks yang lebih besar dari, katakanlah, $3\times 3$ . Untuk $n\times n$ matriks, membutuhkan komputasi determinan dari matriks itu sendiri dan komputasi $n^2$ faktor penentu $(n-1)\times(n-1)$ matriks. Jadi saya kira itu tidak berguna untuk aplikasi. Tapi saya ingin konfirmasi.

Saya tidak bertanya tentang signifikansi teoretis dari teknik dalam membuktikan teorema tentang matriks.

linear-algebra matrix complexity Stefan Smith
sumber

Jawaban:

Anda benar - sama sekali tidak ada relevansi praktis untuk komputasi. Bahkan jika menghitung determinan adalah operasi , kompleksitas metode akan setidaknya dan, akibatnya, kompleksitas yang sama dengan eliminasi Gaussian. Dalam prakteknya, menghitung determinan matriks sebenarnya adalah kompleksitas eksponensial, membuat metode ini sama sekali tidak dapat digunakan. $O(n)$ $O(n^3)$

Wolfgang Bangerth
sumber

Dua hal yang ingin saya tambahkan: Kompleksitas Aturan Cramer (menggunakan determinan untuk menghitung invers) adalah

Yang jauh lebih besar daripada Eliminasi Gaussian

. Juga, secara umum, Anda tidak ingin menghitung invers kecuali Anda benar-benar harus.

O (n!)

$O(n!)$

O (n^{3})

$O(n^3)$

Paul

OTOH, mungkin ada beberapa keadaan di mana ekspansi Laplace mungkin lebih disukai, misalnya matriks berpita. Namun memang, secara umum, ekspansi Laplace memiliki kompleksitas

O (n!)

$O(n!)$

@Stefan, ya, eliminasi Gaussian dapat digunakan untuk menghitung determinan. Karena

, dan eliminasi Gaussian menghasilkan faktor (segitiga) yang faktor penentunya mudah dihitung, maka memang diperlukan upaya

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

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

O (n^{3})

$O(n^3)$

Ya, Anda benar - penentu dapat dihitung dengan biaya dekomposisi

(Cara naif ditampilkan dalam buku teks menggunakan ekspansi rekursif adalah eksponensial dalam kompleksitas

- the

disebutkan oleh Paul). Tapi itu masih menghasilkan kompleksitas keseluruhan

untuk algoritma yang diusulkan - jauh lebih dari eliminasi Gaussian, jika seseorang menggunakannya, dan bahkan lebih dari pemecah iteratif.

L U

$LU$

n

$n$

n!

$n!$

O (n^{5})

$O(n^5)$

Wolfgang Bangerth

Benar. Reduksi baris adalah setengah dari komputasi dekomposisi

Ini mengurangi

ke faktor

Separuh pekerjaan lainnya melakukan operasi yang sama mulai dari matriks identitas, menghasilkan matriks

Memang benar bahwa Anda dapat menghindari yang terakhir jika yang Anda pedulikan adalah penentu.

L U

$LU$

A

$A$

U

$U$

L

$L$

Wolfgang Bangerth

Saya akan menentang kerumunan - matriks adjugate sebenarnya sangat berguna untuk beberapa aplikasi khusus dengan dimensi kecil (seperti empat atau kurang), khususnya ketika Anda membutuhkan kebalikan dari matriks tetapi tidak peduli skala.

Dua contoh termasuk perhitungan homografi terbalik dan iterasi hasil Rayleigh untuk masalah yang sangat kecil (yang selain disederhanakan dengan menggunakan adjugate secara numerik lebih baik).

nonbasketless
sumber

Saya sepenuhnya setuju, ada beberapa kasus (secara umum dengan matriks kecil) yang sangat membantu! (misalnya, untuk menghitung koordinat barycentric dalam simpleks kecil)

BrunoLevy