Obliczanie charakterystycznego wielomianu rzeczywistej macierzy rzadkiej

9

Biorąc pod uwagę ogólną macierz rzadką z ~~m << n~~ (korekta: ) niezerowe elementy (zwykle ). jest ogólne w tym sensie, że nie ma żadnych specyficznych właściwości (np. Dodatnia definitywność) i nie zakłada się żadnej struktury (np. Pasmowości). $A \in \mathbb{R}^{n\times n}$ $m \ll n^2$ $m \in {\cal O}(n)$ $A$

Jakie są dobre metody numeryczne do obliczenia charakterystycznego wielomianu lub minimalnego wielomianu ? $A$

linear-algebra algorithms sparse-matrix

3

Wygląda na to, że chcesz obliczyć wszystkie wartości własne. Dlaczego chcesz wielomianu i jak chcesz go wyrazić? Podstawa monomialna jest bardzo słabo uwarunkowana, więc współczynników prawdopodobnie nie można stabilnie obliczyć w arytmetyki skończonej precyzji.

— Jed Brown

@JedBrown więcej kontemplacji. W odpowiedzi na to pytanie podałem metodę algebraiczną odwracania macierzy, która jest dobrze znana w algebrze komputerowej (np. Macierze nad pierścieniami i polami przemiennymi). Chcę wiedzieć, czy mógłbym użyć go do matryc numerycznych. Zauważ, że do celów tego pytania interesują mnie numeryczne metody znajdowania charakterystycznego / minimalnego wielomianu zamiast odwrotnego.

1

Jeśli złożoność nie jest ogranicznikiem, możesz przyjrzeć się metodzie Danilewskiego. Jest dość dobrze znany w rosyjskiej literaturze na temat numerycznej algebry liniowej, ale po angielsku niewiele jest informacji. Możesz zacząć od tego linku . $O(n^3)$

Pomysł jest raczej prosty: matryca jest stopniowo redukowana do normalnej postaci Frobeniusa przez transformacje podobieństwa „eliminacji Gaussa”. Jeśli nie znajdziesz informacji, mogę ulepszyć algorytm.

— faleichik
źródło

1

Możesz użyć metody numerycznej, takiej jak faktoryzacja QR lub metoda mocy i jej wartości rzeczywiste (moc odwrotna itp.), Aby obliczyć wartości własne macierzy ogólnej. Następnie możesz obliczyć swój charakterystyczny wielomian przez rozkład na czynniki: (λ-λ1) (λ-λ2) ... (λ-λn) = 0, gdzie λi to obliczone wartości własne. Oto krótka prezentacja na temat metod zasilania i QR:

QR-Power

— chemeng
źródło

0

Nawiasem mówiąc: Czy chcesz powiedzieć, że masz wiele wpisów ? Jeśli rzeczywiście wówczas większość wierszy i kolumn będzie całkowicie pusta i prawdopodobne jest, że charakterystyczny wielomian faktycznie nie ma stopnia ale stopnia . $m \ll O(n^2)$ $m \ll O(n)$ $n$ $O(m)$

— Wolfgang Bangerth
źródło

Operacje Nie. Chciałem powiedzieć tj. . Przepraszam za to.

m ≪ n^{2},

$m \ll n^2,$

m \in O (n)

$m \in {\cal O}(n)$