Algorytm Lanczosa

W liniowym Algebra , że Lanczosa algorytm (lub Lanczosa metoda ) to algorytm iteracyjny w celu określenia wartości i wektorów własnych o kwadratowej macierzy lub w pojedynczej wartości rozkładu prostokątnej matrycy.

Algorytm ten nie ma związku z okienkowaniem Lanczosa (używanym na przykład do zmiany rozmiaru obrazów), z wyjątkiem tego, że oba wywodzą swoje nazwy od tego samego wynalazcy, węgierskiego fizyka i matematyka Corneliusa Lanczosa .

Opis algorytmu

Metoda iteracji zasilania

Metoda iteracji potęgowej w celu znalezienia największej wartości własnej symetrycznej macierzy kwadratowej rzędu p jest następująca. W{\ styl wyświetlania A \,}

Jeśli jest wektorem i , to . x0{\ styl wyświetlania x_ {0}}xnie+1=Wxnie{\ displaystyle x_ {n + 1} = Ax_ {n}}xnie=Wniex0{\ displaystyle x_ {n} = A ^ {n} x_ {0}}

Wiemy, że macierz symetryczna jest podatna na diagonalizację, a terminy macierzy diagonalnej są wartościami własnymi macierzy. Więc albo σja,ja=1...p{\ displaystyle \ sigma _ {i}, i = 1 ... p}

W=U⋅(σ10⋱σja⋱⋮⋱0σp)⋅U'=U⋅diag⁡(σja)⋅U'{\ displaystyle A = U \ cdot {\ begin {pmatrix} \ sigma _ {1} &&&&& 0 \\ & \ ddots &&&& \\ && \ sigma_ {i} &&& \\ &&& \ ddots && \\ && \ vdots && \ ddots & \\ 0 &&&&& \ sigma _ {p} \\\ end {pmatrix}} \ cdot U '= U \ cdot \ operatorname {diag} (\ sigma _ {i}) \ cdot U'}

wartością własną rozkładu z , gdzie U jest macierzą ortogonalną  ; więc W{\ styl wyświetlania A}

Wnie=Udiag⁡(σjanie)U'{\ styl wyświetlania A ^ {n} = U \ nazwa operatora {diag} (\ sigma _ {i} ^ {n}) U '}

W przypadku wartości bardzo dużych w diagonalnej macierzy wartości własnych będzie dominować największa z nich – z wyjątkiem przypadku, gdy są dwie większe równe wartości: rzeczywiście niech będzie wartość własna większego modułu. nie{\ styl wyświetlania n \,}σmwx{\ styl wyświetlania \ sigma _ {max}}

Limnie→∞Wnie=Limnie→∞|σmwx|nie⋅Udiag⁡(σjanie|σmwx|nie)U'=Udiag⁡(0 ... 0,(σmwx|σmwx|)nie,0 ... 0)U'{\ displaystyle \ lim _ {n \ rightarrow \ infty} A ^ {n} = \ lim _ {n \ rightarrow \ infty} | \ sigma _ {max} | ^ {n} \ cdot U \ operatorname {diag} ( {\ frac {\ sigma _ {i} ^ {n}} {| \ sigma _ {max} | ^ {n}}}) U '= U \ nazwa operatora {diag} (0 ... 0, \ lewo ( {\ frac {\ sigma _ {maks}} {| \ sigma _ {maks} |}} \ prawo) ^ {n}, 0 ... 0) U '}

Następnie zbiega się do największej wartości własnej i odpowiedniego wektora własnego. |xnie+1|/|xnie|{\ styl wyświetlania | x_ {n + 1} | / | x_ {n} |}xnie/|xnie|{\ styl wyświetlania x_ {n} / | x_ {n} |}

Jeśli istnieje kilka maksymalnych wartości własnych, zbiega się w kierunku wektora w podprzestrzeni generowanej przez wektory własne skojarzone z tymi wartościami. Po ustaleniu pierwszego można sukcesywnie ograniczyć algorytm do jądra znanych wektorów własnych w celu wyznaczenia pozostałych. xnie{\ styl wyświetlania x_ {n}}

W praktyce algorytm ten ma dwie wady: podatność na błędy zaokrągleń oraz czasami zbyt małą szybkość zbieżności.

Algorytm Lanczosa

Algorytm Lanczosa udoskonala poprzednią metodę, w której każda jest ograniczona do ortogonalnej wszystkich poprzednich wartości. Podczas konstrukcji tych wektorów stałe normalizacji są grupowane w macierz trójkątną, której najważniejsze wartości własne szybko zbliżają się do wartości własnych macierzy wyjściowej. ty{\ styl wyświetlania u \,}

Mnożenie przez jest wtedy jedyną operacją na dużą skalę, co czyni tę metodę interesującą. W{\ styl wyświetlania A}

Zastosowania, warianty i uogólnienia

Algorytm Lanczosa jest szczególnie przydatny do określania rozkładu bardzo dużych macierzy, w meteorologii lub przetwarzaniu języka naturalnego, gdzie macierze te mogą zawierać setki tysięcy wyrazów.

To uogólnia algorytm Arnoldi  (en) dla macierzy niesymetrycznych.

Wariant tego algorytmu służy do rozdzielczości układów liniowych (w szczególności pustych układów liniowych) i wyszukiwania elementów jądra macierzy. W tej postaci jest często stosowany w ramach algorytmów takich jak sito kwadratowe lub sito algebraiczne do faktoryzacji liczb całkowitych lub metoda indeksowa dla problemu logarytmów dyskretnych . Jest to związane z metodą gradientu sprzężonego .

Uwagi i referencje

1. W celu demonstracji zob. PG Ciarlet, Wprowadzenie do analizy i optymalizacji macierzy numerycznych , wyd. Masson, kol.  „Matematyka. Zał. na studia magisterskie ”,1985( przedruk  2001) ( ISBN  2-225-68893-1 )rozdz. 1, Twierdzenie 1.2.1
2. (w) R. Bellman, Wprowadzenie do analizy macierzy , SIAM al.  „Klasyka w Appl. Matematyka. ",1960( przedruk  1970, 1997) ( ISBN  0-89871-399-4 ) , "3" , s.  35-36

Zobacz również

Powiązane artykuły

• Algorytm wyszukiwania wartości własnych
• Metoda gradientu sprzężonego
• Metoda gradientu dwuskoniugowanego
• Eliminacja Gaussa-Jordana

Bibliografia

• (fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z anglojęzycznego artykułu z Wikipedii zatytułowanego „  Algorytm Lanczosa  ” ( patrz lista autorów ) .
• (en) Gene H. Golub i Charles F. Van Loan  (en) , Matrix Computations , JHU Press,1996, 694  s. ( ISBN  978-0-8018-5414-9 , prezentacja online )

Linki zewnętrzne

• (en) Andrew Y. Ng , Alice X. Zheng i Michael I. Jordan , „Analiza połączeń, wektory własne i stabilność” , w IJCAI-01 ,2001( czytaj online ) , s.  903-910 : porównanie metod rankingowych HITS i PageRank (algorytm Google) oraz ich zbieżności i stabilności wektorów własnych w obliczu zmian w zestawach linków organizowanych przez wyszukiwarki
• (en) Brian A. LaMacchia i Andrew M. Odlyzko , „Solving Large Sparse Linear Systems over Finite Fields” , w Proceeding CRYPTO '90 , s.  109-133, § 3: Lanczosa i metody gradientów sprzężonych

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">