Zrozumienie „współczynnika konwergencji” dla metod iteracyjnych

Według Wikipedii współczynnik konwergencji wyraża się jako konkretny stosunek norm wektorowych. Próbuję zrozumieć różnicę między szybkościami „liniowymi” i „kwadratowymi” w różnych punktach czasu (w zasadzie „na początku” iteracji i „na końcu”). Czy można stwierdzić, że:

• $e_{k+1}$$x_{k+1}$$\|e_k\|$

• z kwadratową konwergencją norma błędu iteracji x_ {k + 1} jest ograniczona przez \ | e_k \ | ^ 2$e_{k+1}$$x_{k+1}$$\|e_k\|^2$

Taka interpretacja oznaczałaby, że przy kilku (niewielkiej liczbie) iteracjach algorytmu liniowo zbieżnego algorytmu A1 (przy założeniu losowej inicjalizacji) osiągnięto by mniejszy błąd, niż przy kilku iteracjach algorytmu kwadratycznie zbieżnego algorytmu A2. Ponieważ jednak błąd maleje, a ze względu na kwadratowanie, późniejsze iteracje oznaczałyby mniejszy błąd dla A2.

Czy powyższa interpretacja jest ważna? Zauważ, że pomija współczynnik szybkości $\lambda$ .

W praktyce tak. Podczas gdy jest nadal duży, współczynnik szybkości będzie dominować nad błędem, a nie q-rate. (Pamiętaj, że są to stawki asymptotyczne , więc wyciągi, które podłączyłeś, zachowują limit tylko jako .)$e_k$$\lambda$$k\to\infty$

Na przykład w przypadku metod pierwszego rzędu w optymalizacji często obserwuje się początkowo szybki spadek błędu, który następnie się wyrównuje. Z drugiej strony, w przypadku metody Newtona może upłynąć trochę czasu, zanim rozpocznie się konwergencja superlinearna (lub kwadratowa) (w końcu jest ona tylko lokalnie superlinearnie zbieżna). Z tego powodu często rozpoczyna się od kilku kroków gradientu, aby przejść do metody Newtona, lub stosuje metody homotopii lub quasi-Newtona, które zachowują się początkowo jako metody pierwszego rzędu i zamieniają się w metodę Newtona w miarę zbliżania się do metody cel.

Oprócz odpowiedzi Christiana warto również zauważyć, że dla zbieżności liniowej masz gdzie masz jeśli metoda jest zbieżna. Z drugiej strony, dla zbieżności kwadratowej masz a fakt, że zbieżność metody niekoniecznie oznacza, że musi być mniejsza niż jeden. Warunkiem konwergencji jest$e_{k+1} \le \lambda_1 e_k$$\lambda_1<1$$e_{k+1} \le \lambda_2 e_k^2$$\lambda_2$$\lambda_2 e_1<1$- tzn. że początkowe przypuszczenie jest wystarczająco bliskie. Jest to często obserwowane zachowanie: że algorytmy kwadratycznie zbieżne należy uruchomić „wystarczająco blisko” od rozwiązania, aby uzyskać zbieżność, podczas gdy algorytmy liniowo zbieżne są zazwyczaj bardziej niezawodne. Jest to kolejny powód, dla którego często zaczyna się od kilku kroków algorytmu liniowej konwergencji (np. Metoda najbardziej stromego zejścia) przed przejściem na bardziej wydajne (np. Metoda Newtona).

Interpretacja jest jakościowo poprawna.

Zauważ, że zbieżność liniowa i kwadratowa dotyczy najgorszego przypadku, sytuacja w danym algorytmie może być lepsza niż uzyskana z analizy najgorszego przypadku podanej przez Wolfganga Bangertha, chociaż sytuacja jakościowa zwykle odpowiada tej analizie.

W konkretnych algorytmach (np. W optymalizacji) często sensowne jest najpierw iterowanie za pomocą taniej, ale tylko liniowo zbieżnej metody, aż postęp się zwolni, a następnie zakończenie metodą zbieżną kwadratową (lub przynajmniej superliniową). W praktyce konwergencja superliniowa jest na ogół tak samo dobra jak konwergencja kwadratowa tylko dlatego, że początkowa, powoli zbieżna część ma tendencję do dominacji nad całością pracy.