Warunek wstępny - Preconditioner

W matematyce , hartowanie jest zastosowanie transformacji, zwany przygotowujący , że warunki dany problem w postaci, która jest bardziej odpowiednia dla numerycznych metod rozwiązywania. Wstępne uwarunkowanie jest zazwyczaj związane ze zmniejszeniem liczby warunków problemu. Wstępnie uwarunkowany problem jest zwykle rozwiązywany metodą iteracyjną .

Kondycjonowanie wstępne dla systemów liniowych

W Algebra liniową i analizę numeryczną , A prekondycjonerze macierzy jest macierz tak, że ma mniejszą liczbę stan niż . Powszechne jest również wywoływanie warunku wstępnego, a nie , ponieważ sam rzadko jest jawnie dostępny. We współczesnym uwarunkowaniu wstępnym, zastosowanie , tj. mnożenie wektora kolumnowego lub bloku wektorów kolumnowych przez , jest powszechnie wykonywane przez raczej wyrafinowane pakiety oprogramowania komputerowego w sposób bezmacierzowy , tj. gdzie ani , ani (i często not even ) są jawnie dostępne w postaci macierzy. ${\displaystyle P}$${\ Displaystyle A}$${\ Displaystyle P ^ {-1} A}$${\ Displaystyle A}$${\ Displaystyle T = P ^ {-1}}$${\displaystyle P}$${\displaystyle P}$${\ Displaystyle T = P ^ {-1}}$${\ Displaystyle T = P ^ {-1}}$${\displaystyle P}$${\ Displaystyle T = P ^ {-1}}$${\ Displaystyle A}$

Przygotowujące są użyteczne w metodach iteracyjnego rozwiązania układu liniowego na ponieważ szybkość zbieżności dla większości iteracyjnych rozwiązują liniowe wzrasta, ponieważ liczba stan matrycy zmniejsza się w wyniku wstępnego. Wstępnie uwarunkowane solwery iteracyjne zazwyczaj przewyższają solwery bezpośrednie, np. eliminację Gaussa , w przypadku dużych, szczególnie rzadkich macierzy . Solwery iteracyjne mogą być używane jako metody bezmacierzowe , tj. stają się jedynym wyborem, jeśli macierz współczynników nie jest przechowywana wprost, ale jest dostępna przez ocenę iloczynów macierzy i wektorów. ${\ Displaystyle Axe = b}$${\displaystyle x}$${\ Displaystyle A}$

Opis

Zamiast rozwiązywania pierwotnego układu liniowego powyżej, można rozważyć właściwy układ wstępnie uwarunkowany

${\ Displaystyle AP ^ {-1} (Px) = b}$

i rozwiąż

${\ Displaystyle AP ^ {-1} y = b}$

dla i ${\displaystyle y}$

${\displaystyle Px=y}$

dla . ${\displaystyle x}$

Alternatywnie można rozwiązać lewy układ wstępnie uwarunkowany

${\ Displaystyle P ^ {-1} (Ax-b) = 0.}$

Oba systemy dają to samo rozwiązanie, co system oryginalny, o ile macierz warunków wstępnych jest nieosobliwa . Lewe uwarunkowanie wstępne jest bardziej tradycyjne. ${\displaystyle P}$

Dwustronny układ prekondycjonowanych

${\ Displaystyle QAP ^ {-1} (Px) = Qb}$

korzystne może być np. zachowanie symetrii macierzy: jeśli pierwotna macierz jest rzeczywiście symetryczna, a rzeczywiste warunki wstępne i spełniają warunki wstępne, to macierz uwarunkowania wstępnego jest również symetryczna. Dwustronne uwarunkowanie wstępne jest wspólne dla skalowania diagonalnego, w którym warunki wstępne i są diagonalne, a skalowanie jest stosowane zarówno do kolumn, jak i wierszy macierzy oryginalnej , np. w celu zmniejszenia zakresu dynamicznego wpisów macierzy. ${\ Displaystyle A}$${\displaystyle Q}$${\displaystyle P}$${\ Displaystyle Q ^ {T} = P ^ {-1}}$${\ Displaystyle QAP ^ {-1}}$${\displaystyle Q}$${\displaystyle P}$${\ Displaystyle A}$

Celem uwarunkowania wstępnego jest zmniejszenie liczby warunków , np. lewej lub prawej macierzy układu uwarunkowanego wstępnie lub . Małe liczby warunków sprzyjają szybkiej konwergencji solwerów iteracyjnych i poprawiają stabilność rozwiązania w odniesieniu do perturbacji w macierzy systemu i po prawej stronie, np. pozwalając na bardziej agresywną kwantyzację wpisów macierzy przy użyciu mniejszej precyzji komputera . ${\ Displaystyle P ^ {-1} A}$${\ Displaystyle AP ^ {-1}}$

Wstępnie uwarunkowana macierz lub rzadko jest jawnie tworzona. Może być konieczne obliczenie tylko czynności polegającej na zastosowaniu operacji rozwiązywania uwarunkowań wstępnych do danego wektora. ${\ Displaystyle P ^ {-1} A}$${\ Displaystyle AP ^ {-1}}$${\ Displaystyle P ^ {-1}}$

Zazwyczaj jest kompromis w wyborze . Ponieważ operator musi być zastosowany na każdym kroku iteracyjnego solwera liniowego, powinien on mieć niewielki koszt (czas obliczeniowy) zastosowania tej operacji. Najtańszy kondycjoner byłby więc od tamtego czasu. Oczywiście skutkuje to oryginalnym systemem liniowym, a kondycjoner wstępny nie robi nic. Z drugiej strony, wybór daje ten, który ma optymalny warunek numer 1, wymagający pojedynczej iteracji dla zbieżności; jednak w tym przypadku i zastosowanie warunku wstępnego jest tak trudne, jak rozwiązanie oryginalnego systemu. Dlatego wybiera się coś pomiędzy tymi dwoma skrajnościami, próbując osiągnąć minimalną liczbę iteracji liniowych przy zachowaniu możliwie najprostszego operatora . Niektóre przykłady typowych podejść do warunkowania wstępnego są wyszczególnione poniżej. ${\displaystyle P}$${\ Displaystyle P ^ {-1}}$${\ Displaystyle P ^ {-1}}$${\displaystyle P=I}$${\ Displaystyle P ^ {-1} = I.}$${\ Displaystyle P = A}$${\ Displaystyle P ^ {-1} A = AP ^ {-1} = ja,}$${\ Displaystyle P ^ {-1} = A ^ {-1}}$${\displaystyle P}$${\ Displaystyle P ^ {-1}}$

Wstępnie uwarunkowane metody iteracyjne

Wstępnie uwarunkowane metody iteracyjne są w większości przypadków matematycznie równoważne standardowym metodom iteracyjnym zastosowanym do wstępnie uwarunkowanego systemu Na przykład standardowa iteracja Richardsona do rozwiązywania jest ${\ Displaystyle Ax-b = 0}$${\ Displaystyle P ^ {-1} (Ax-b) = 0.}$${\ Displaystyle Ax-b = 0}$

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} (A \ mathbf {x} _ {n} - \ mathbf {b}}), \ n\geq 0.}$

Zastosowany w systemie wstępnie kondycjonowanym zamienia się w metodę kondycjonowania wstępnego ${\ Displaystyle P ^ {-1} (Ax-b) = 0,}$

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} P ^ {-1} (A \ mathbf {x} _ {n} - \ mathbf {b} ),\ n\geq 0.}$

Przykłady popularnych metod iteracyjnych z warunkowaniem wstępnym dla systemów liniowych obejmują metodę gradientu wstępnie uwarunkowanych koniugatów , metodę gradientu dwukoniugatów i uogólnioną metodę minimalnej pozostałości . Metod iteracyjnych, wykorzystujące produkty skalarne do obliczania parametrów iteracyjnych, wymagają odpowiednich zmian w iloczynem skalarnym wraz z podstawienie dla${\ Displaystyle P ^ {-1} (Ax-b) = 0}$${\ Displaystyle Ax-b = 0.}$

Podział macierzy

Stacjonarny sposób iteracyjny jest określona przez rozszczepienie osnowy i matrycą iteracji . Przy założeniu, że ${\ Displaystyle A = MN}$${\ Displaystyle C = IM ^ {-1} A}$

• macierz systemu jest symetryczna dodatnio określona ,${\ Displaystyle A}$
• macierz podziału jest symetryczna dodatnio określona ,${\ Displaystyle M}$
• stacjonarna metoda iteracyjna jest zbieżna, co określa ,${\ Displaystyle \ rho (C) <1}$

liczba warunek jest ograniczony z góry przez ${\ Displaystyle \ kappa (M ^ {-1} A)}$

${\ Displaystyle \ kappa (M ^ {-1} A) \ leq {\ Frac {1+ \ rho (C)} {1-\ rho (C)}} \,.}$

Interpretacja geometryczna

W przypadku symetrycznej dodatnio określonej macierzy warunek wstępny jest zwykle wybierany tak, aby był również symetryczny dodatnio określony. Operator warunkowy jest wtedy również symetryczny dodatnio określony, ale w odniesieniu do iloczynu skalarnego opartego na . W tym przypadku pożądanym efektem zastosowania warunku wstępnego jest uczynienie kwadratowej postaci operatora uwarunkowania wstępnego w odniesieniu do iloczynu skalarnego opartego na prawie kulistym. ${\ Displaystyle A}$${\displaystyle P}$${\ Displaystyle P ^ {-1} A}$${\displaystyle P}$${\ Displaystyle P ^ {-1} A}$${\displaystyle P}$

Zmienne i nieliniowe uwarunkowanie wstępne

Wskazując , podkreślamy, że uwarunkowanie wstępne jest praktycznie zaimplementowane jako pomnożenie jakiegoś wektora przez , tj. obliczenie iloczynu W wielu aplikacjach nie jest podawany jako macierz, ale raczej jako operator działający na wektor . Jednak niektóre popularne uwarunkowania wstępne zmieniają się wraz z nimi, a zależność od nich może nie być liniowa. Typowe przykłady obejmują stosowanie nieliniowych metod iteracyjnych , np. metody gradientu sprzężonego , jako części konstrukcji warunku wstępnego. Takie uwarunkowania wstępne mogą być praktycznie bardzo wydajne, jednak ich zachowanie jest trudne do przewidzenia teoretycznie. ${\ Displaystyle T = P ^ {-1}}$${\ Displaystyle r}$${\ Displaystyle T}$${\ Displaystyle Tr.}$${\ Displaystyle T}$${\displaystyle T(r)}$${\ Displaystyle r}$${\ Displaystyle r}$${\ Displaystyle r}$

Losowe uwarunkowanie wstępne

Interesującym szczególnym przypadkiem warunkowania zmiennych jest losowe warunkowanie wstępne, np. wielosiatkowe warunkowanie wstępne na losowych siatkach kursów. W przypadku stosowania w metodach opadania gradientowego losowe warunkowanie wstępne może być postrzegane jako implementacja stochastycznego opadania gradientowego i może prowadzić do szybszej zbieżności w porównaniu ze stałym warunkowaniem wstępnym, ponieważ przerywa asymptotyczny „zygzakowaty” wzór opadania gradientowego .

Widmowo równoważne uwarunkowanie wstępne

Najczęstszym zastosowaniem uwarunkowań wstępnych jest iteracyjne rozwiązywanie układów liniowych wynikające z przybliżeń równań różniczkowych cząstkowych . Im lepsza jakość aproksymacji, tym większy rozmiar matrycy. W takim przypadku celem optymalnego uwarunkowania wstępnego jest z jednej strony, aby liczba warunków spektralnych była ograniczona od góry stałą niezależną od rozmiaru macierzy, co D'yakonov nazywa spektralnie równoważnym uwarunkowaniem wstępnym . Z drugiej strony, koszt zastosowania powinien być idealnie proporcjonalny (również niezależny od wielkości macierzy) do kosztu mnożenia przez wektor. ${\ Displaystyle P ^ {-1} A}$${\ Displaystyle P ^ {-1}}$${\ Displaystyle A}$

Przykłady

Warunek wstępny Jacobiego (lub diagonalnego)

Jacobim prekondycjonerze jest jednym z najprostszych formach wstępnego, w którym środek przygotowujący jest wybrany na przekątnej macierzy Zakładając , otrzymujemy jest skuteczny do przekątnej dominujących matryc . ${\ Displaystyle P = \ operatorname {diag} (A).}$${\ Displaystyle A_ {ii} \ neq 0 \ dla wszystkich i}$${\ Displaystyle P_ {ij} ^ {-1} = {\ Frac {\ delta _ {ij}} {A_ {ij}}}.}$ ${\ Displaystyle A}$

HISZPANIA

W rozrzedzone Terminy odwrotne minimalizuje prekondycjonerze gdzie IS normą Frobeniusa oraz jest ograniczone odpowiednio od pewnego zbioru rzadkich macierzy . Zgodnie z normą Frobeniusa sprowadza się to do rozwiązania wielu niezależnych problemów najmniejszych kwadratów (po jednym na każdą kolumnę). Wpisy w muszą być ograniczone do jakiegoś wzorca rzadkości, w przeciwnym razie problem pozostanie tak trudny i czasochłonny, jak znalezienie dokładnej odwrotności . Metodę wprowadzili MJ Grote i T. Huckle wraz z podejściem do wyboru wzorców rzadkości. ${\ Displaystyle \ | AT-I \ | _ {F},}$${\ Displaystyle \ | \ cdot \ | _ {F}}$${\ Displaystyle T = P ^ {-1}}$${\ Displaystyle T}$${\ Displaystyle A}$

Inne warunki wstępne

• Niekompletna faktoryzacja Choleskiego
• Niepełna faktoryzacja LU
• Kolejny nadmierny relaks
  • Symetryczna sukcesywna nadrelaksacja
• Wstępne kondycjonowanie wielu sieci

Linki zewnętrzne

• Wstępnie uwarunkowany gradient koniugatu – math-linux.com
• Szablony rozwiązań systemów liniowych: bloki konstrukcyjne dla metod iteracyjnych

Warunkowanie wstępne dla problemów z wartością własną

Problemy z wartością własną można sformułować na kilka alternatywnych sposobów, z których każdy prowadzi do własnego uwarunkowania wstępnego. Tradycyjne uwarunkowanie wstępne opiera się na tak zwanych transformacjach spektralnych. Znając (w przybliżeniu) docelową wartość własną, można obliczyć odpowiadający jej wektor własny, rozwiązując powiązany jednorodny układ liniowy, co pozwala na użycie uwarunkowań wstępnych dla układu liniowego. Wreszcie, sformułowanie problemu wartości własnej jako optymalizacji ilorazu Rayleigha wprowadza na scenę wstępnie uwarunkowane techniki optymalizacji.

Transformacje spektralne

Analogicznie do systemów liniowych, dla problemu wartości własnej można pokusić się o zastąpienie macierzy macierzą za pomocą warunku wstępnego . Jednak ma to sens tylko wtedy, gdy szuka wektory z i są takie same. Tak jest w przypadku przekształceń widmowych. ${\ Displaystyle Axe = \ lambda x}$${\ Displaystyle A}$${\ Displaystyle P ^ {-1} A}$${\displaystyle P}$${\ Displaystyle A}$${\ Displaystyle P ^ {-1} A}$

Najpopularniejszą transformacją widmową jest tzw. transformacja przesunięto-i-odwrotna , gdzie dla danego skalara , zwanego przesunięciem , pierwotny problem wartości własnej zastępowany jest problemem przesunięcia i odwrócenia . Wektory własne są zachowywane, a problem przesunięcia i odwrócenia można rozwiązać za pomocą solwera iteracyjnego, np . iteracji potęgowej . Daje to iterację odwrotną , która zwykle zbiega się do wektora własnego, odpowiadającego wartości własnej najbliższej przesunięciu . Rayleigha iloraz iteracji jest sposób przesuwny i-inwertowanego o zmianie zmiennej. ${\ Displaystyle \ alfa}$${\ Displaystyle Axe = \ lambda x}$${\ Displaystyle (A-\ alfa I) ^ {-1} x = \ mu x}$${\ Displaystyle \ alfa}$

Transformacje spektralne są specyficzne dla problemów z wartościami własnymi i nie mają odpowiedników dla układów liniowych. Wymagają one dokładnego obliczenia numerycznego zachodzącej transformacji, co staje się głównym wąskim gardłem dla dużych problemów.

Ogólne warunki wstępne

Aby uzyskać ścisłe powiązanie z układami liniowymi, załóżmy, że docelowa wartość własna jest znana (w przybliżeniu). Następnie można obliczyć odpowiedni wektor własny z jednorodnego układu liniowego . Wykorzystując koncepcję lewostronnego uwarunkowania wstępnego dla układów liniowych otrzymujemy , gdzie jest warunkiem wstępnym, który możemy spróbować rozwiązać za pomocą iteracji Richardsona${\ Displaystyle \ lambda _ {\ gwiazda}}$${\ Displaystyle (A-\ lambda _ {\ gwiazda} I) x = 0}$${\ Displaystyle T (A-\ lambda _ {\ gwiazda} I) x = 0}$${\ Displaystyle T}$

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} T (A - \ lambda _ {\ gwiazda} I)) \ mathbf {x} _{n},\ n\geq 0.}$

Idealny Wstępne

Uogólniona macierz odwrotna jest przygotowujący, co sprawia, że iteracje Richardson powyżej zbieg się w jednym etapie , ponieważ , oznaczona jest prostopadły Projektor eigenspace, co odpowiada . Wybór jest niepraktyczny z trzech niezależnych powodów. Pierwsza właściwie nie jest znana, chociaż można ją zastąpić jej przybliżeniem . Po drugie, dokładna pseudoodwrotność Moore'a-Penrose'a wymaga znajomości wektora własnego, który próbujemy znaleźć. Można to nieco obejść za pomocą prekondycjonera Jacobiego-Davidsona , gdzie przybliża . Wreszcie, podejście to wymaga dokładnego rozwiązania numerycznego układu liniowego z macierzą układu , co w przypadku dużych problemów staje się tak samo kosztowne jak metoda przesunięcia i odwrócenia opisana powyżej. Jeśli rozwiązanie nie jest wystarczająco dokładne, krok drugi może być zbędny. ${\ Displaystyle T = (A-\ lambda _ {\ gwiazda} ja) ^ {+}}$${\ Displaystyle \ gamma _ {n} = 1}$${\ Displaystyle I-(A-\ lambda _ {\ gwiazda} ja) ^ {+} (A- \ lambda _ {\ gwiazda} ja)}$${\displaystyle P_{\gwiazda}}$${\ Displaystyle \ lambda _ {\ gwiazda}}$${\ Displaystyle T = (A-\ lambda _ {\ gwiazda} ja) ^ {+}}$${\ Displaystyle \ lambda _ {\ gwiazda}}$${\displaystyle {\tylda {\lambda}}_{\gwiazda}}$ ${\ Displaystyle T = (ja {\ tylda {P}} _ {\ gwiazda}) (A- {\ tylda {\ lambda}} _ {\ gwiazda} ja) ^ {-1} (ja {\ tylda {P}}_{\gwiazda})}$${\ Displaystyle {\ tylda {P}} _ {\ gwiazda}}$${\displaystyle P_{\gwiazda}}$${\ Displaystyle (A-{\ tylda {\ lambda}} _ {\ gwiazda} ja)}$

Praktyczne uwarunkowanie wstępne

Najpierw zastąpmy wartość teoretyczną w powyższej iteracji Richardsona jej bieżącym przybliżeniem, aby uzyskać praktyczny algorytm ${\ Displaystyle \ lambda _ {\ gwiazda}}$${\ Displaystyle \ lambda _ {n}}$

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} T (A-\ lambda _ {n} ja) \ mathbf {x} _ { n},\ n\geq 0.}$

Popularnym wyborem jest użycie funkcji ilorazu Rayleigha . Praktyczne uwarunkowanie wstępne może być tak trywialne, jak samo użycie lub Dla niektórych klas problemów z wartościami własnymi skuteczność została wykazana, zarówno liczbowo, jak i teoretycznie. Wybór ten pozwala na łatwe wykorzystanie do rozwiązywania problemów z wartościami własnymi ogromnej różnorodności warunków wstępnych opracowanych dla systemów liniowych. ${\ Displaystyle \ lambda _ {n} = \ rho (x_ {n})}$${\displaystyle \rho (\cdot)}$${\ Displaystyle T = (diag (A)) ^ {-1}}$${\ Displaystyle T = (diag (A-\ lambda _ {n} I)) ^ {-1}.}$${\ Displaystyle T \ około A ^ {-1}}$${\ Displaystyle T \ około A ^ {-1}}$

Ze względu na zmieniającą się wartość wszechstronna teoretyczna analiza zbieżności jest znacznie trudniejsza w porównaniu do przypadku systemów liniowych, nawet dla najprostszych metod, takich jak iteracja Richardsona . ${\ Displaystyle \ lambda _ {n}}$

Linki zewnętrzne

• Szablony do rozwiązywania problemów algebraicznych z wartością własną: praktyczny przewodnik

Prekondycjonowanie w optymalizacji

W optymalizacji , warunkowanie wstępne jest zwykle używane do przyspieszenia algorytmów optymalizacji pierwszego rzędu .

Opis

Na przykład, w celu znalezienia minimum lokalne danej funkcji o wartościach rzeczywistych z wykorzystaniem metoda gradientu prostego , bierze się etapy proporcjonalne do ujemnego z gradientem (lub w przybliżeniu gradient) funkcji w bieżącym punkcie: ${\ Displaystyle F (\ mathbf {x} )}$ ${\displaystyle -\nabla F(\mathbf {a})}$

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} \ nabla F (\ mathbf {x} _ {n}), \ n \ geq 0.}$

Warunek wstępny jest stosowany do gradientu:

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} P ^ {-1} \ nabla F (\ mathbf {x} _ {n} ),\ n\geq 0.}$

Wstępne uwarunkowanie można tutaj postrzegać jako zmianę geometrii przestrzeni wektorowej w celu sprawienia, aby zestawy poziomów wyglądały jak koła. W tym przypadku wstępnie uwarunkowany gradient zmierza bliżej punktu ekstremów, jak na figurze, co przyspiesza zbieżność.

Połączenie z systemami liniowymi

Minimum funkcji kwadratowej

${\ Displaystyle F (\ mathbf {x} ) = {\ Frac {1} {2}} \ mathbf {x} ^ {T} A \ mathbf {x} - \ mathbf {x} ^ {T} \ mathbf { b} }$,

gdzie i są rzeczywistymi wektorami kolumnowymi i jest rzeczywistą symetryczną macierzą dodatnio określoną , jest dokładnie rozwiązaniem równania liniowego . Ponieważ , wstępnie uwarunkowaną metodą minimalizacji gradientu jest ${\displaystyle \mathbf {x}}$${\displaystyle \mathbf {b}}$${\ Displaystyle A}$ ${\ Displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ Displaystyle \ nabla F (\ mathbf {x} ) = A \ mathbf {x} - \ mathbf {b}}$${\ Displaystyle F (\ mathbf {x} )}$

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} P ^ {-1} (A \ mathbf {x} _ {n} - \ mathbf {b} ),\ n\geq 0.}$

Jest to wstępnie uwarunkowana iteracja Richardsona do rozwiązywania układu równań liniowych .

Połączenie z problemami z wartością własną

Minimum ilorazu Rayleigha

${\ Displaystyle \ rho (\ mathbf {x} ) = {\ Frac {\ mathbf {x} ^ {T} A \ mathbf {x}} {\ mathbf {x} ^ {T} \ mathbf {x}}} ,}$

gdzie jest rzeczywistym niezerowym wektorem kolumnowym i jest rzeczywistą symetryczną macierzą dodatnio określoną , jest najmniejszą wartością własną z , podczas gdy minimalizator jest odpowiednim wektorem własnym . Ponieważ jest proporcjonalna do , wstępnie uwarunkowana metoda opadania gradientu minimalizacji to ${\displaystyle \mathbf {x}}$${\ Displaystyle A}$ ${\ Displaystyle A}$${\ Displaystyle \ nabla \ rho (\ mathbf {x})}$${\ Displaystyle A \ mathbf {x} - \ rho (\ mathbf {x}) \ mathbf {x}}$${\ Displaystyle \ rho (\ mathbf {x} )}$

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} P ^ {-1} (A \ mathbf {x} _ {n} - \ rho (\mathbf {x_{n}} )\mathbf {x_{n}} ),\ n\geq 0.}$

Jest to odpowiednik wstępnie uwarunkowanej iteracji Richardsona do rozwiązywania problemów z wartościami własnymi.

Zmienne uwarunkowanie wstępne

W wielu przypadkach może być korzystna zmiana warunku wstępnego na pewnym lub nawet każdym kroku algorytmu iteracyjnego w celu dostosowania się do zmieniającego się kształtu zestawów poziomów, jak w

${\ Displaystyle \ mathbf {x} _ {n + 1} = \ mathbf {x} _ {n} - \ gamma _ {n} P_ {n} ^ {-1} \ nabla F (\ mathbf {x} _ {n}),\ n\geq 0.}$

Należy jednak pamiętać, że skonstruowanie wydajnego prekondycjonera jest bardzo często obliczeniowo kosztowne. Zwiększony koszt aktualizacji warunku wstępnego może z łatwością przesłonić pozytywny efekt szybszej konwergencji.

Bibliografia

Źródła

• Axelsson, Owe (1996). Iteracyjne metody rozwiązywania . Wydawnictwo Uniwersytetu Cambridge. str. 6722. ISBN 978-0-521-55569-2.
• D'yakonov, EG (1996). Optymalizacja w rozwiązywaniu problemów eliptycznych . CRC-Prasa. str. 592. Numer ISBN 978-0-8493-2872-5.
• Saad, Yousef i van der Vorst, Henk (2001). „Iteracyjne rozwiązanie układów liniowych w XX wieku”. W Breziński, C. i Wuytack, L. (red.). Analiza numeryczna: wydarzenia historyczne w XX wieku . Wydawnictwa naukowe Elsevier . §8 Metody kondycjonowania wstępnego, s. 193–8. Numer ISBN 0-444-50617-9.
• van der Vorsta, HA (2003). Iteracyjne metody Kryłowa dla dużych układów liniowych . Wydawnictwo Uniwersytetu Cambridge, Cambridge. Numer ISBN 0-521-81828-1.
• Ke Chen: „Macierzowe techniki warunkowania i zastosowania”, Cambridge University Press, ISBN  978-0521838283 (2005).