Przyspieszenie Andersona – Wikipedia

Posted on December 11, 2023 by lordneo

before-content-x4

L ‘ Przyspieszenie Andersona (znany również w języku angielskim jako Mieszanie Andersona ) jest metodą przyspieszenia zbieżności iteracji o stałych punktach. Wprowadzone przez Donalda G. Andersona ^[Pierwszy], tę metodę można zastosować do znalezienia rozwiązania równań o stałym punkcie

{DisplayStyle f (x) = x}

after-content-x4

$f(x)=x$ które często pojawiają się w dziedzinie nauki obliczeniowej.

Biorąc pod uwagę funkcję

{DisplayStyle f: Mathbb {r} ^{n} do mathbb {r} ^{n}}

${displaystyle f:mathbb {R} ^{n}to mathbb {R} ^{n}}$ , rozważ problem znalezienia ustalonego punktu

{DisplayStyle f}

$f$ lub rozwiązanie równania

{DisplayStyle f (x) = x}

$f(x)=x$ . Klasycznym podejściem do problemu jest użycie schematu iteracji o stałym punkcie ^[2]lub biorąc pod uwagę pierwszą hipotezę

{DisplayStyle x_ {0}}

$x_0$ Dla roztworu oblicz sekwencję

{DisplayStyle x_ {i+1} = f (x_ {i})}

${displaystyle x_{i+1}=f(x_{i})}$ Aż do spełnienia kryterium konwergencji. Jednak zbieżność programu nie jest ogólnie gwarantowana. Ponadto zbieżność jest ogólnie ogólna liniowa i dlatego może być zbyt wolna, szczególnie jeśli ocena funkcji

after-content-x4

{DisplayStyle f}

$f$ To jest drogie ^[2]. Przyspieszenie Andersona jest metodą przyspieszenia zbieżności iteracji o stałych punktach ^[2].

Definiuje siebie

{DisplayStyle g (x) = f (x) -x}

${displaystyle g(x)=f(x)-x}$ , To jest

{DisplayStyle g_ {k} = g (x_ {k})}

${displaystyle g_{k}=g(x_{k})}$ . Biorąc pod uwagę początkowy theter

{DisplayStyle x_ {0}}

$x_0$ i cały parametr

{DisplayStyle Mgeq 1}

${displaystyle mgeq 1}$ , metodę można sformułować w następujący sposób ^[3]^{[Za pomocą 1]}:

{DisplayStyle x_ {1} = f (x_ {0})}

{DisplayStyle forall k = 1,2, kropki}

Aby zakończyć iteracje metody, można zastosować kryteria aresztowania dla metod iteracyjnych. Na przykład iteracje można przerwać, kiedy

{DisplayStyle || x_ {k+1} -x_ {k} ||}

${displaystyle ||x_{k+1}-x_{k}||}$ jest pod przepisaną tolerancją lub gdy pozostałość

{DisplayStyle g (x_ {k})}

${displaystyle g(x_{k})}$ Jest poniżej zalecanej tolerancji.

W porównaniu z prostą iteracją o stałym punkcie stwierdzono, że metoda przyspieszenia Andersona zbiega się szybciej, bardziej solidniej ^[3]^[4].

Table of Contents

Rozwiązanie problemu minimalizacji [[[ zmiana |. Modifica Wikitesto ]

Przy każdej iteracji algorytmu problem optymalizacji związanej

{DisplayStyle operatorname {argmin} || g_ {k} alpha || _ {2}}

${displaystyle operatorname {argmin} ||G_{k}alpha ||_{2}}$ , z zastrzeżeniem

{DisplayStyle Alpha w A_ {K}}

${displaystyle alpha in A_{k}}$ należy rozwiązać. Problem można wyrazić w niektórych równoważnych preparatach ^[3], które odpowiadają różnym metodom rozwiązania, które mogą spowodować bardziej wydajną implementację:

W obu poprzednich wyborach problem optymalizacji jest przedstawiony w postaci problemu przy minimalnych liniowych kwadratach, które nie są związane, co można rozwiązać za pomocą standardowych metod, w tym rozkładu QR ^[3]i rozkład do wartości liczby pojedynczej ^[4], być może w tym techniki regularyzacji w celu radzenia sobie z problemami związanymi z rankingiem i warunkowaniem problemu optymalizacji. Rozwiązywanie problemu minimum kwadratowego poprzez rozwiązanie równań normalnych na ogół nie jest zalecane ze względu na potencjalną niestabilność numeryczną i ogólnie wysokie koszty obliczeń.

Stagnacja metody (tj. Obliczanie kolejnych iteracji o tej samej wartości,

{DisplayStyle x_ {k+1} = x_ {k}}

${displaystyle x_{k+1}=x_{k}}$ ) Powoduje awarię z powodu osobliwości problemu minimalnych kwadratów. W ten sam sposób quasi-instalacja (

{DisplayStyle x_ {k+1} ok. x_ {k}}

${displaystyle x_{k+1}approx x_{k}}$ ) powoduje uwarunkowanie problemu do minimalnych kwadratów ^[3]. Ponadto wybór parametru

{DisplayStyle M}

$m$ Może to być istotne przy określaniu warunkowania problemu minimalnych kwadratów, jak pokazano później.

Relaks [[[ zmiana |. Modifica Wikitesto ]

Algorytm można zmienić, wprowadzając zmienny parametr relaksacji (lub parametr miksowania)

{DisplayStyle beta _ {k}> 0}

${displaystyle beta _{k}>0}”></span><sup id=$ [Pierwszy] ^[3]^[4]. Na każdym etapie nowe iterate należy obliczyć jako

{DisplayStyle x_ {k+1} = (1-beta _ {k}) sum _ {i = 0}^{m_ {k}} (alpha _ {k}) _ {i} x_ {k-m_ {k }+i}+beta _ {k} sum _ {i = 0}^{m_ {k}} (alpha _ {k}) _ {i} f (x_ {k-m_ {k}+i}); .}

${displaystyle x_{k+1}=(1-beta _{k})sum _{i=0}^{m_{k}}(alpha _{k})_{i}x_{k-m_{k}+i}+beta _{k}sum _{i=0}^{m_{k}}(alpha _{k})_{i}f(x_{k-m_{k}+i});.}$ Wybór wartości

{DisplayStyle beta _ {k}}

$beta _{k}$ Ważne jest, aby określić metody zbieżności metody; zasadniczo,

{DisplayStyle beta _ {k}}

$beta _{k}$ może się różnić dla każdej iteracji, chociaż często jest wybierany stał ^[4].

Wybór m [[[ zmiana |. Modifica Wikitesto ]

Parametr

{DisplayStyle M}

$m$ określa, ile informacji z poprzednich iteracji jest używane do obliczenia nowej iteracji

{DisplayStyle x_ {k+1}}

${displaystyle x_{k+1}}$ . Z jednej strony, jeśli

{DisplayStyle M}

$m$ Jest wybrany zbyt mały, używane jest niewiele informacji, a zbieżność może być powolna. Z drugiej strony, jeśli

{DisplayStyle M}

$m$ Jest zbyt duży, informacje o starych iteracjach można przechowywać w przypadku zbyt wielu kolejnych iteracji, również w tym przypadku poprzez spowolnienie zbieżności ^[3]. Również wybór

{DisplayStyle M}

$m$ Wpływa na wielkość problemu optymalizacji. Zbyt wielka wartość

{DisplayStyle M}

$m$ Może pogorszyć warunkowanie problemu minimalnych kwadratów i kosztów jego rozwiązania. Ogólnie rzecz biorąc, co jest dobrym wyborem

{DisplayStyle M}

$m$ To zależy od konkretnego problemu do rozwiązania ^[3].

Wybór ${DisplayStyle m_ {k}}$

W porównaniu z opisanym powyżej algorytmem, wybór

{DisplayStyle m_ {k}}

$m_{k}$ Każda iteracja można zmienić. Jedną z możliwości jest wybór

{DisplayStyle m_ {k} = k}

${displaystyle m_{k}=k}$ Dla każdej iteracji

{DisplayStyle K}

$k$ (Ten wybór jest czasem wskazany jako przyspieszenie Andersona bez obcięcia) ^[3]. W ten sposób każda nowa iteracja

{DisplayStyle x_ {k+1}}

${displaystyle x_{k+1}}$ Oblicza się go przy użyciu wszystkich poprzednich iteracji. Bardziej wyrafinowana technika opiera się na wyborze

{DisplayStyle m_ {k}}

$m_{k}$ w celu utrzymania dość małego uwarunkowania problemu przy minimalnych kwadratach ^[3].

Metodę Newtona można zastosować do rozwiązania

{DisplayStyle f (x) -x = 0}

${displaystyle f(x)-x=0}$ Aby obliczyć stały punkt

{DisplayStyle f (x)}

$f(x)$ Z kwadratową konwergencją. Jednak ta metoda wymaga dokładnej oceny pochodnej

{DisplayStyle f (x)}

$f(x)$ , co może być bardzo drogie ^[4]. Przybliżenie pochodnej poprzez różnice skończone jest możliwą alternatywą, ale wymaga wielu ocen

{DisplayStyle f (x)}

$f(x)$ do każdej iteracji, która znów może być bardzo droga. Przyspieszenie Andersona wymaga jedynie oceny funkcji

{DisplayStyle f (x)}

$f(x)$ do iteracji i brak oceny jej pochodnej. Z drugiej strony zbieżność sekwencji punktowej z przyspieszeniem Andersona jest ogólnie liniowa ^[5].

Kilku autorów podkreśliło podobieństwa między schematem przyspieszenia Andersona a innymi metodami rozwiązania równań nieliniowych. W szczególności:

Eyert ^[6]Egnij E ziarno ^[4]Zinterpretowali algorytm w klasie prawie nowych i wieloskulowych metod, które uogólniają dobrze znaną metodę SecurIT, dla rozwiązania równania nieliniowego ${DisplayStyle g (x) = 0}$
Walker e ni ^[3]Wykazali, że schemat przyspieszenia Andersona jest równoważny metodzie GMRES w przypadku problemów liniowych (tj. Problem znalezienia rozwiązania a ${DisplayStyle amathbf {x} = mathbf {x}}$

Ponadto inne autorzy opracowano inne równoważne lub prawie równoważne metody ^[8]^[9]^[dziesięć]^[11]^[dwunasty], chociaż przez większość czasu w kontekście konkretnego zastosowania zainteresowania, a nie jako ogólna metoda równań o stałym punkcie.

Poniżej znajduje się przykład implementacji w języku Matlab w schemacie przyspieszenia Andersona, aby znaleźć stały punkt funkcji

{DisplayStyle f (x) = sin (x)+arctan (x)}

${displaystyle f(x)=sin(x)+arctan(x)}$ . Zauważ, że:

Problem optymalizacji został rozwiązany w formie ${DisplayStyle gamma _ {k} = operatorname {argmin _ _ {gamma w mathbb {r {m_ {k}}}}} 2}}$
Obliczenie rozkładu QR nie jest optymalne: w rzeczywistości do każdej iteracji do macierzy dodaje się pojedyncza kolumna ${DisplayStyle {Mathcal {g}} _ {k}}$
Algorytm może być bardziej wydajny pod względem pamięci, oszczędzając tylko najnowsze iteracje i pozostałości, jeśli cały wektor iteracji ${DisplayStyle x_ {k}}$
Kod można łatwo uogólnić na przypadek ${DisplayStyle f (x)}$

F  =  @( X )  grzech ( X )  +  Atan ( X );  % Funkcji do obliczenia stałego punktu.  x0  =  Pierwszy ;  % Początkowa iteracja.  k_max  =  100 ;  % Maksymalna liczba iteracji.  TOL_RES  =  1E-6 ;  % Tolerancja na pozostałości.  M  =  3 ;  % Parametr m.  X  =  [[[ x0 W  F ( x0 )];  % Wektor wszystkich iteracji.  G  =  F ( X )  -  X ;  % Wektor wszystkich pozostałości.  G_k = g(2) - g(1); % Matrice degli incrementi dei residui.
X_k = x(2) - x(1); % Matrice degli incrementi nelle iterazioni.

k = 2;
while k < k_max && abs(g(k)) > tol_res
  m_k = min(k, m);
  
  % Soluzione del problema ai minimi quadrati con fattorizzazione QR.
  [Q, R] = qr(G_k);
  gamma_k = R  (Q' * g(k));
  
  % Calcolo della nuova iterata e del residuo corrispondente.
  x(k+1) = x(k) + g(k) - (X_k + G_k) * gamma_k;
  g(k+1) = f(x(k+1)) - x(k+1);
  
  % Aggiornamento delle matrici degli incrementi.
  X_k = [X_k, x(k+1) - x(k)];
  G_k = [G_k, g(k+1) - g(k)];
  
  n = size(X_k, 2);
  if n > m_k
    X_k = X_k(:,n-m_k+1:end);
    G_k = G_k(:,n-m_k+1:end);
  end
  
  k = k + 1;
end

% Stampa il risultato: Trovato punto fisso 2.013444 dopo 9 iterazioni
fprintf ("Trovato punto fisso %f dopo %d iterazionin", x(end), k);

Notatki wyjaśniające [[[ zmiana |. Modifica Wikitesto ]

^ Poniższe sformułowanie nie odpowiada dokładnie tej dostarczonej przez oryginalnego autora ^[Pierwszy], ale jest to równoważne sformułowanie podane przez Walkera i Ni ^[3].

Bibliografia [[[ zmiana |. Modifica Wikitesto ]

^ ^A^B^C^D Donald G. Anderson, Iteracyjne procedury nieliniowych równań integralnych , W Journal of the ACM (JACM) , tom. 12, n. 4, październik 1965, s. 547–560, doi: 10.1145/321296.321305 .
^ ^A^B^C Alfio Quarteroni, Riccardo Sacco i Fausto Saleri, Matematyka numeryczna , 2ª ed., Springr, ISBN 978-3440-49809-4.
^ ^A^B^C^D^{To jest}^F^G^H^I^J^k^L^M Grlr dla. Cok byy Przyspieszenie Anderson do iteracji o stałym punkcie , W SIAM Journal o analizie numerycznej , tom. 49, n. 4, styczeń 2011, s. 1715–1735, doi: 10.1137/10078356x .
^ ^A^B^C^D^{To jest}^F^G Haw-ren fang e yousef saad, Dwie klasy wieloskulowych metod przyspieszenia nieliniowego , W Numeryczna algebra liniowa z aplikacjami , tom. 16, n. 3, marzec 2009, s. 197–221, doi: 10.1002 / Great.617 .
^ Claire Evans, Sara Pollock E Leo G. Rebolz, Dowód, że przyspieszenie Andersona poprawia szybkość konwergencji w linii konwertujących metod stałego punktu (ale nie w przypadku zbieżności kwadratowo) , W SIAM Journal o analizie numerycznej , tom. 58, n. 1, 20 lutego 2020, s. 788–810, doi: 10.1137/19M1245384 .
^ V. Eyert, Porównawcze badanie metod przyspieszenia konwergencji iteracyjnych sekwencji wektorowych , W Journal of Computational Physics , tom. 124, n. 2, marzec 1996, s. 271–285, doi: 10.1006 / jcph.1996.0059 .
^ C. G. Broyden, Klasa metod rozwiązywania nieliniowych równań jednoczesnych , W Matematyka obliczeń , tom. 19, n. 92, 1965, s. 577–577, doi: 10.1090/S0025-5718-1965-0198670-6 .
^ ^A^B C. W. Oosterlee E T. Washio, Podprzestrzeń Krylova Przyspieszenie nieliniowego multigrid z zastosowaniem do recyrkulacji przepływów , W SIAM Journal on Scientific Computing , tom. 21, n. 5, styczeń 2000, s. 1670–1690, doi: 10.1137/S1064827598338093 .
^ Peter Pulay, Przyspieszenie konwergencji sekwencji iteracyjnych. przypadek iteracji SCF , W Listy fizyki chemicznej , tom. 73, n. 2, lipiec 1980, s. 393–398, doi: 10.1016/0009-2614 (80) 80396-4 .
^ P. Pulay, Ulepszenia przyspieszenia konwergencji , W Journal of Computational Chemistry , tom. 3, n. 4, 1982, s. 556–560, doi: 10.1002/JCC.540030413 .
^ Neil N. Carlson E Keith Miller, Projektowanie i zastosowanie kodu elementu skończonego ważonego gradientu I: W jednym wymiarze , W SIAM Journal on Scientific Computing , tom. 19, n. 3, maj 1998, s. 728–765, doi: 10.1137/s106482759426955x .
^ Keith Miller, Nieliniowy Krylov i ruchome węzły w metodzie linii , W Journal of Computational and Applied Mathematics , tom. 183, n. 2, listopad 2005, s. 275–287, doi: 10.1016/j.cam.2004.12.032 .
^ J. W. Daniell, W. Bragg E. Bragg E. Confman, Reorthogonalizacja i stabilne algorytmy do aktualizacji faktoralizacji QR Gram-Schmidt , W Matematyka obliczeń , tom. 30, n. 136, październik 1976, s. 772–772, doi: 10.1090/S0025-5718-1976-0431641-8 .

after-content-x4

Przyspieszenie Andersona – Wikipedia

Rozwiązanie problemu minimalizacji [[[ zmiana |. Modifica Wikitesto ]

Relaks [[[ zmiana |. Modifica Wikitesto ]

Wybór m [[[ zmiana |. Modifica Wikitesto ]

Wybór ${DisplayStyle m_ {k}}$

Notatki wyjaśniające [[[ zmiana |. Modifica Wikitesto ]

Bibliografia [[[ zmiana |. Modifica Wikitesto ]

Recent Posts

Recent Comments

Archives

Categories

Meta

Rozwiązanie problemu minimalizacji [[[ zmiana |. Modifica Wikitesto ]

Relaks [[[ zmiana |. Modifica Wikitesto ]

Wybór m [[[ zmiana |. Modifica Wikitesto ]

Wybór mk{DisplayStyle m_ {k}} [[[ M k {DisplayStyle m_ {k}} “> Edytuj |. M k {DisplayStyle m_ {k}} “> Modifica Wikitesto ]

Notatki wyjaśniające [[[ zmiana |. Modifica Wikitesto ]

Bibliografia [[[ zmiana |. Modifica Wikitesto ]

Recent Posts

Recent Comments

Archives

Categories

Meta

Wybór ${DisplayStyle m_ {k}}$