Jak aproksymować liczbę warunków dużej matrycy?

Jak aproksymować liczbę warunków dużej matrycy $G$, gdyby $G$ jest kombinacją transformacji Fouriera $F$ (niejednorodne lub jednolite), różnice skończone $R$i macierze diagonalne $S$?

Matryce są bardzo duże i nie są przechowywane w pamięci i są dostępne tylko jako funkcje.

W szczególności mam następującą macierz:

$G_\mu=S^HF^HFS+\mu R^HR$

Chcę zbadać związek między $\mu$ i numer warunku $k(G_\mu)$.

Zakładam, że ktoś potrzebuje jakiegoś iteracyjnego podejścia? Optymalnie będzie dostępny kod MATLAB.

MATLAB ma kilka „exact” funkcje do tego, condi rcond, przy czym te ostatnie przekazujących Odwrotność liczby stan. Przybliżona funkcja Matlaba condestjest dokładniej opisana poniżej.

Często szacunki liczby warunków są generowane jako produkty uboczne rozwiązania układu liniowego dla macierzy, więc może być możliwe zastosowanie szacunków liczby warunków przy innych pracach, które należy wykonać. Zobacz tutaj na krótki opis, w jaki sposób szacunki są obliczane. Również dokumentacja Sandia Labs AztecOO zauważa (patrz rozdział 3.1), że opcjonalne szacunki liczby warunków są dostępne w iteracyjnych solverach (przy użyciu wygenerowanej trójosiowej macierzy Lanczos z gradientami sprzężonymi lub wygenerowanej macierzy Hessenburga z zrestartowanym GMRES).

Ponieważ macierze są „bardzo duże” i „dostępne tylko jako funkcje”, logicznym podejściem będzie metoda, która zastosuje piggyback na sprzężonym rozwiązaniu gradientowym lub wariancie.

Niedawny artykuł arXiv.org Niestacjonarne przybliżenia ekstremalnych wartości własnych w iteracyjnych rozwiązaniach układów liniowych i estymatorów błędu względnego proponuje takie podejście i zawiera kilka cytatów do wcześniejszej literatury.

Teraz, gdy patrzę, na tym forum jest wiele ściśle powiązanych poprzednich pytań (nie wszystkie z odpowiedziami, ale sprawdź komentarze):

Oszacuj ekstremalne wartości własne za pomocą CG

Oszacowanie liczb warunków dla bardzo dużych macierzy

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

Ponieważ dostępność kodu MATLAB była częścią pytania, oto kilka informacji na temat condestwbudowanej funkcji, która szacuje 1-normowy numer warunku$\|A\|_1 \|A^{-1}\|_1$. Pomysł pochodzi od Hagera (1984), z opisem i rozszerzeniami z 2010 roku , aby jawnie obliczyć (znaleźć maksymalną 1-normę kolumny) i oszacować metodą gradientową. Zobacz także Johna Burkardt za STANU , biblioteka MATLAB (pozostałe wersje) „dla obliczania lub szacowania liczby stan macierzy”.$\|A\|_1$$\|A^{-1}\|_1$

Ponieważ twoja macierz jest najwyraźniej pustelnikiem i jest pozytywnie określona, ​​być może 2-normowa liczba warunków jest bardziej interesująca. Problem polega zatem na oszacowaniu stosunku największych do najmniejszych (absolutnych) wartości własnych. Wyzwanie jest nieco równoległe do przypadku 1-normalnego, ponieważ ogólnie można łatwo uzyskać dobre oszacowanie największej wartości własnej , ale oszacowanie najmniejszej wartości własnej okazuje się trudniejsze.

Mimo że celowano w przypadki spoza SPD (a nawet nie kwadratowe), ten najnowszy artykuł arXiv.org, Reliable Iterative Estimation-Number Estimation , daje dobry przegląd najmniejszego problemu szacowania wartości własnej oraz obiecującą linię ataku przez podprzestrzeń Krylov metoda (LSQR), która w przypadku SPD jest równa gradientowi sprzężonemu.