Algoritma tercepat untuk menghitung nomor kondisi dari matriks besar di Matlab / Oktaf

9

Dari definisi bilangan kondisi tampaknya diperlukan inversi matriks untuk menghitungnya, saya bertanya-tanya apakah untuk matriks kuadrat generik (atau lebih baik jika simetris positif pasti) dimungkinkan untuk mengeksploitasi beberapa dekomposisi matriks untuk menghitung nomor kondisi dalam suatu cara yang lebih cepat.

linear-algebra matrix condition-number linello
sumber

7

Menghitung angka kondisi (bahkan memperkirakannya dalam faktor 2) tampaknya memiliki kompleksitas yang sama dengan menghitung faktorisasi, meskipun tidak ada teorema dalam arah ini.

Dari faktor Cholesky jarang dari matriks definitif positif simetris, atau dari faktorisasi jarang (dengan implisit ) dari matriks persegi umum, seseorang dapat memperoleh nomor kondisi dalam norma Frobenius dengan menghitung subset invers yang jarang dari , yang jauh lebih cepat daripada menghitung invers penuh. (Terkait dengan ini adalah makalah saya: Norma hibrida dan batas untuk sistem linier yang ditentukan secara berlebihan, Linear Algebra Appl. 216 (1995), 257-266. Http://www.mat.univie.ac.at/~neum/scan/74 .pdf ) $R$ $QR$ $Q$ $(R^TR)^{-1}$

Sunting: Jika maka sehubungan dengan setiap invarian yang tidak biasa, $A=QR$ Untuk perhitungan faktorisasi QR yang jarang, lihat, misalnya,http://dl.acm.org/citation.cfm?id=174408. Untuk perhitungan invers jarang, lihat, misalnya, makalah saya: Estimasi kemungkinan maksimum terbatas kovarian dalam model linear jarang, Genetika Seleksi Evolusi 30 (1998), 1-24. https://www.mat.univie.ac.at/~neum/ms/reml.pdf Biayanya sekitar 3 kali lipat biaya untuk faktorisasi.

c o n d (A) = c o n d (R) = \sqrt{c o n d (R^{T} R)} .

$cond(A)=cond(R)=\sqrt{cond(R^TR)}.$

Arnold Neumaier
sumber

Jadi Anda menyarankan yang berikut: Diberikan matriks

menghitung QR-nya dari bentuk

mana

adalah matriks segitiga atas dan

adalah matriks ortogonal dan kemudian nomor kondisi diberikan oleh

Intinya di sini adalah bagaimana menemukan metode cepat untuk menghitung faktorisasi QR. Apakah saya benar?

A

$\mathbf{A}$

A = Q R

$\mathbf{A}=\mathbf{Q}\mathbf{R}$

R

$\mathbf{R}$

Q

$\mathbf{Q}$

cond (A) = | | A | | | | A^{- 1} | | (R^{T} R)^{- 1}

$\textrm{cond}(\mathbf{A})=||A|| ||A^{-1}|| (\mathbf{R}^T\mathbf{R})^{-1}$

linello

@linello: tidak cukup; lihat hasil edit saya.

Arnold Neumaier

Terima kasih! Saya akan memeriksanya, tapi berapa biaya langkah ini?

linello

O (n^{3})

$O(n^3)$

4

Tentunya mudah menggunakan dekomposisi eigenvalue / eigenvektor matriks simetris atau SVD dari matriks umum untuk menghitung angka kondisi, tetapi ini bukan cara yang cepat untuk dilanjutkan.

$A^{-1}$ condest

Brian Borchers
sumber

Namun estimasi ini terkadang terlalu kecil. Menghitung angka kondisi (bahkan memperkirakannya dalam faktor 2) tampaknya memiliki kompleksitas yang sama dengan menghitung faktorisasi, meskipun tidak ada teorema dalam arah ini.

Arnold Neumaier

1

$H$ $H$ $H^TH$

Karena nilai eigen / nilai singular terbesar dan terkecil dapat ditemukan dengan sangat cepat (jauh sebelum tridiagonisasi selesai), metode Lanczos sangat berguna untuk menghitung nomor kondisi.

chaohuang
sumber

Saya selalu bertanya-tanya di mana menemukan kode matlab yang dapat dibaca untuk iterasi lanczos yang menjelaskan bagaimana cara mendapatkan nilai eigen terkecil atau terbesar. Bisakah Anda menyarankan saya satu?

linello

Saya tidak memiliki kode MATLAB untuk algoritma Lanczos.

chaohuang

Algoritma tercepat untuk menghitung nomor kondisi dari matriks besar di Matlab / Oktaf

Jawaban: