Najszybszy algorytm do obliczania liczby warunków dużej macierzy w Matlab / Octave

9

Z definicji numeru warunku wydaje się, że do obliczenia potrzebna jest inwersja macierzy, zastanawiam się, czy dla ogólnej macierzy kwadratowej (lub lepiej, jeśli symetryczny dodatni określony) można wykorzystać rozkład macierzy do obliczenia liczby warunków w szybszy sposób.

linear-algebra matrix condition-number linello
źródło

7

Obliczenie liczby warunków (nawet przybliżenie jej do współczynnika 2) wydaje się mieć taką samą złożoność jak obliczenie faktoryzacji, chociaż w tym kierunku nie ma żadnych twierdzeń.

Od rzadkiego czynnika Choleskiego $R$ symetrycznej dodatniej określonej macierzy lub z rzadkiej $QR$ faktoryzacja (z domniemanym $Q$ ) ogólnej macierzy kwadratowej, liczbę warunkową można uzyskać w normie Frobeniusa, obliczając rzadki odwrotny podzbiór $(R^TR)^{-1}$ , co jest znacznie szybsze niż obliczenie pełnego odwrotności. (Powiązany z tym jest mój artykuł: Hybrydowe normy i granice dla przesadnie określonych układów liniowych, Linear Algebra Appl. 216 (1995), 257-266. Http://www.mat.univie.ac.at/~neum/scan/74 .pdf )

Edycja: Jeśli $A=QR$ następnie w odniesieniu do każdego niezmiennie niezmiennego norn,

do o n re (ZA) = do o n re (R) = \sqrt{do o n re (R^{T.} R)} .

$cond(A)=cond(R)=\sqrt{cond(R^TR)}.$ Aby obliczyć rzadkie faktoryzacje QR, patrz np .
Http://dl.acm.org/citation.cfm?id=174408 .
Aby obliczyć rzadką odwrotność, patrz np. Mój artykuł: Ograniczone oszacowanie maksymalnego prawdopodobieństwa kowariancji w rzadkich modelach liniowych, Genetics Selection Evolution 30 (1998), 1-24.
https://www.mat.univie.ac.at/~neum/ms/reml.pdf Koszt jest około 3 razy większy niż koszt faktoryzacji.

Arnold Neumaier
źródło

Sugerujesz więc, aby: Mając matrycę

A

$\mathbf{A}$ obliczyć jego QR formularza

A = Q R

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

R

$\mathbf{R}$ jest górną trójkątną matrycą i

Q

$\mathbf{Q}$ jest macierzą ortogonalną, a następnie numer warunku jest podawany przez

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

$\textrm{cond}(\mathbf{A})=||A|| ||A^{-1}|| (\mathbf{R}^T\mathbf{R})^{-1}$ Chodzi o to, jak znaleźć szybką metodę obliczania faktoryzacji QR. Czy mam rację?

linello

@linello: niezupełnie; zobacz moją edycję.

Arnold Neumaier

Dzięki! Zamierzam to sprawdzić, a co za koszt tego kroku?

linello

@linello: Aby uzyskać pełną matrycę,

O (n^{3})

$O(n^3)$ ; dla rzadkiej matrycy zależy to w dużej mierze od struktury rzadkości.

Arnold Neumaier

4

Z pewnością łatwo jest użyć rozkładu wartości własnej / wektora własnego macierzy symetrycznej lub SVD macierzy ogólnej do obliczenia liczby warunków, ale nie są to szczególnie szybkie sposoby postępowania.

Istnieją iteracyjne algorytmy, które mogą obliczyć szacunkową liczbę warunków, która jest przydatna do większości celów, bez konieczności wykonywania całej pracy związanej z obliczeniami $A^{-1}$ . Zobacz na przykład condestfunkcję w MATLAB.

Brian Borchers
źródło

Ale szacunek jest czasami znacznie za mały. Obliczenie liczby warunków (nawet przybliżenie jej do współczynnika 2) wydaje się mieć taką samą złożoność jak obliczenie faktoryzacji, chociaż w tym kierunku nie ma żadnych twierdzeń.

Arnold Neumaier

1

Dla rzadkich matryc hermitowskich $H$ , możesz użyć algorytmu Lanczos do obliczenia jego wartości własnych. Gdyby $H$ nie jest pustelnikiem, można obliczyć jego wartości osobliwe, obliczając wartości własne $H^TH$ .

Ponieważ największe i najmniejsze wartości własne / wartości osobliwe można znaleźć bardzo szybko (na długo przed zakończeniem tridiagonalizacji), metoda Lanczosa jest szczególnie przydatna do obliczenia liczby warunków.

chaohuang
źródło

Zawsze zastanawiałem się, gdzie znaleźć czytelny kod Matlaba dla iteracji lanczos, który wyjaśnia, w jaki sposób uzyskać najmniejszą lub największą wartość własną. Czy możesz mi zasugerować?

linello

Nie mam kodów MATLAB dla algorytmu Lanczos.

chaohuang

Najszybszy algorytm do obliczania liczby warunków dużej macierzy w Matlab / Octave

Odpowiedzi: