Jaka jest najgorsza złożoność gradientu sprzężonego?

9

Pozwolić $A\in \mathbb{R}^{n\times n}$ , symetryczny i dodatni określony. Załóżmy, że to trwa $m$ jednostki pracy do pomnożenia wektora przez $A$ . Powszechnie wiadomo, że wykonuje się algorytm CG $A$ z numerem warunku $\kappa$ wymaga $\mathcal{O} (m\sqrt{\kappa})$ , jednostki pracy.

Teraz oczywiście będąc $\mathcal{O}$ oświadczenie to jest górna granica. Algorytm CG może zawsze kończyć się w zerowych krokach przy szczęśliwym początkowym zgadywaniu.

Czy wiemy, czy istnieje RHS i wstępne (pechowe) przypuszczenie, które będzie wymagać $\mathcal{\Theta}(\sqrt{\kappa})$ kroki? Innymi słowy, naprawdę najgorsza złożoność pracy CG $\Theta( m \sqrt{\kappa})$ ?

To pytanie powstaje, gdy próbowałem ustalić, czy korzyść ze stanu wstępnego (niższa $\kappa$ ) przeważyło koszt (wyższy $m$ ). Obecnie pracuję z problemami z zabawkami i chciałbym mieć lepszy pomysł, zanim zaimplementuję cokolwiek w skompilowanym języku.

conjugate-gradient

— Fred
źródło

5

Można przypuszczalnie skonstruować początkowe zgadywanie, uruchamiając algorytm CG „do tyłu” i wkładając odpowiednią energię do każdego z

A

$A$ -ortogonalne kierunki wyszukiwania, że algorytm wymaga wszystkich kroków.

— origimbo

9

Odpowiedź brzmi: tak. Granica współczynnika konwergencji wynosząca $(\sqrt{\kappa}-1) / (\sqrt{\kappa}+1)$ jest ostry w stosunku do zbioru symetrycznych dodatnich macierzy z określoną liczbą warunków $\kappa$ . Innymi słowy, nie wiedząc o niczym więcej $A$ niż liczba warunków, CG naprawdę może wziąć $\sim\sqrt{\kappa}$ iteracje do zbieżności. Mówiąc luźniej, górna granica jest osiągana, jeśli wartości własne $A$ są równomiernie rozmieszczone (tzn. „pieprzone”) w przedziale liczby warunków $\kappa$ .

Oto bardziej rygorystyczne stwierdzenie. Wersje deterministyczne są bardziej zaangażowane, ale działają na tych samych zasadach.

Twierdzenie (wybór najgorszego przypadku z $A$ ). Wybierz dowolną losową macierz ortogonalną $U$ , pozwolić $\lambda_1,\ldots,\lambda_n$ być $n$ liczby rzeczywiste jednolicie próbkowane z rzeczywistego przedziału $[1,\kappa]$ , i pozwól $b=[b_1;\ldots;b_n]$ być $n$ liczby rzeczywiste próbkowane iid ze standardowego Gaussa. Definiować

A = U d i a g (λ_{1}, \dots, λ_{n}) U^{T} .

$A=U\mathrm{diag}(\lambda_1,\ldots,\lambda_n)U^T.$ Następnie w limicie

n \to \infty

$n\to\infty$ , gradienty sprzężone zbiegną się z prawdopodobieństwem jeden do jednego

ϵ

$\epsilon$ dokładne rozwiązanie

A x = b

$Ax=b$ w nie mniej niż

Ω (\sqrt{κ} \log ϵ^{- 1})

$\Omega(\sqrt{\kappa}\log\epsilon^{-1})$ iteracje.

Dowód. Standardowy dowód oparty jest na optymalnych przybliżeniach wielomianowych Czebyszewa, z wykorzystaniem technik znalezionych w wielu miejscach, takich jak książka Greenbauma lub książka Saada .

— Richard Zhang
źródło

1

Granica nie jest ostra, jak wyjaśnia później odpowiedź: Jeśli wartości własne nie są równomiernie rozmieszczone, cg zbiega się szybciej, ponieważ nie jest to iteracja postacyjna. Dlatego musimy dowiedzieć się więcej o matrycy.

— Guido Kanschat,

@GuidoKanschat: Dobra uwaga, i poprawiłem to stwierdzenie, aby wyjaśnić, że ostrość została osiągnięta ponad wszystko

A

$A$ z warunkiem

κ

$\kappa$ .

— Richard Zhang

Dowód sprowadza się do minimalizacji

‖ p (A) ‖

$\|p(A)\|$ w przestrzeni rzędu - wielomianów spełniających . Odpowiednio jest to. W podanym limicie , a rozwiązaniem problemu minimax jest wówczas wielomian Czebyszewa, którego błąd jest zbieżny jako

k

$k$

p (0) = 1

$p(0)=1$

min_{p} max_{λ \in Λ (A)} | p (λ) |

$\min_p \max_{\lambda\in\Lambda(A)} |p(\lambda)|$

Λ (A) \to [1, κ]

$\Lambda(A)\to[1,\kappa]$

\sim \sqrt{κ}

$\sim\sqrt{\kappa}$

— Richard Zhang

0

Przyjmując to jako moje pierwotne pytanie: Czy wiemy, czy istnieje RHS i początkowe (pechowe) przypuszczenie, które będzie wymagało kroków ? $\Theta(\sqrt{\kappa})$

Odpowiedź na pytanie brzmi „nie”. Idea tej odpowiedzi pochodzi z komentarza Guido Kanschata.

Twierdzenie: Dla każdego podanego numeru warunku istnieje macierz z tym numerem warunku, dla którego algorytm CG zakończy się co najwyżej w dwóch krokach (dla dowolnego RHS i początkowego przypuszczenia). $k$ $A$

Rozważ gdzie . Zatem numerem warunku jest . Niech będzie RHS, i oznacz wartości własne jako gdzie $A\in \mathbb{R}^{n\times n}$ $A=\mathrm{diag}(1,\kappa,\kappa,\ldots, \kappa)$ $A$ $\kappa$ $b\in \mathbb{R}^n$ $A$ $\lambda_i$

λ_{i} = {\begin{cases} 1 & i = 1 \\ κ & i \neq 1 \end{cases} .

$\lambda_i = \left\{\begin{array}{ll}1 & i=1\\ \kappa & i\not= 1 \end{array} \right. .$

Najpierw rozważamy przypadek, w którym , początkowe przypuszczenie, wynosi zero. Oznacz jako drugie oszacowanie bz algorytmu CG. Pokazujemy, że , pokazując . Rzeczywiście mamy $x^{(0)} \in \mathbb{R}^n$ $x^{(2)}\in \mathbb{R}^n$ $A^{-1}b$ $x^{(2)} =A^{-1}b$ $\langle x^{(2)}-A^{-1}b, A(x^{(2)}-A^{-1}b)\rangle =0$

\begin{aligned} ⟨ x^{(2)} - A^{- 1} b, A (x^{(2)} - A^{- 1} b) ⟩ & = {‖ x^{(2)} - A^{- 1} b ‖}_{A}^{2} \\ = min_{p \in {p o l y}_{1}} {‖ (p (A) - A^{- 1}) b ‖}_{A}^{2} \\ = min_{p \in {p o l y}_{1}} \sum_{i = 1}^{n} (p (λ_{i}) - λ_{i}^{- 1})^{2} λ_{i} b_{i}^{2} \\ \leq \sum_{i = 1}^{n} (\hat{p} (λ_{i}) - λ_{i}^{- 1})^{2} λ_{i} b_{i}^{2} = 0 \end{aligned}

$\begin{align*} \langle x^{(2)}-A^{-1}b, A(x^{(2)}-A^{-1}b)\rangle &= \left\| x^{(2)}-A^{-1}b \right\|_A^2 \\ &=\min_{p\in \mathrm{poly}_{1} } \left\| (p(A)-A^{-1}) b \right\|_A^2\\ &=\min_{p\in \mathrm{poly}_{1} } \sum_{i=1}^n (p(\lambda_i) - \lambda_i^{-1})^2 \lambda_i b_i^2 \\ &\le \sum_{i=1}^n (\widehat{p}(\lambda_i) - \lambda_i^{-1})^2 \lambda_i b_i^2 = 0 \end{align*}$

Gdzie używamy wielomianu pierwszego rzędu zdefiniowanego jako . Więc udowodniliśmy, że przypadek dla . $\widehat{p}$ $\widehat{p}(x)= (1+\kappa-x)/\kappa$ $x^{(0)}= 0$

Jeśli , to gdzie jest drugim oszacowaniem algorytmu CG z zastąpionym przez . Więc ograniczyliśmy tę sprawę do poprzedniej. $x^{(0)} \not = 0$ $x^{(2)}= \overline{x^{(2)}}+ x^{(0)}$ $\overline{x^{(2)} }$ $b$ $\overline{b} = b-A x^{(0)}$

— Fred
źródło

Ile z tego jest odporna na skończoną precyzję arytmetyki?

— origimbo

@origimbo Jeśli twoje pytanie zostało skierowane do mnie, odpowiedź brzmi: „nie wiem”.

— fred