Qual é a pior complexidade do Gradiente Conjugado?

Seja $A\in \mathbb{R}^{n\times n}$ , simétrico e positivo definido. Suponhamos que leva $m$ unidades de trabalho para multiplicar um vector por $A$ . É sabido que a execução do algoritmo CG em $A$ com o número de condição $\kappa$ requer $\mathcal{O} (m\sqrt{\kappa})$, unidades de trabalho.

Agora, é claro, sendo uma declaração $\mathcal{O}$ , esse é um limite superior. E o algoritmo de CG pode sempre terminar em zero etapas com um palpite inicial de sorte.

Sabemos se existe um RHS e um palpite inicial (infeliz) que exigirá $\mathcal{\Theta}(\sqrt{\kappa})$etapas? Em outras palavras, a pior complexidade de trabalho do CG é realmente$\Theta( m \sqrt{\kappa})$?

Essa questão surge quando tentei determinar se o benefício de um pré-condicionador ( inferior $\kappa$) superava seu custo ( superior $m$). No momento, estou trabalhando com problemas de brinquedo e gostaria de ter uma idéia melhor antes de implementar qualquer coisa em uma linguagem compilada.

A resposta é um sim retumbante. A taxa de convergência vinculada de é nítido sobre o conjunto de matrizes definidas positivas simétricas com número de condição$(\sqrt{\kappa}-1) / (\sqrt{\kappa}+1)$ . Em outras palavras, sabendo nada mais sobre A que seu número de condição, o CG realmente pode assumir ∼ $\kappa$$A$iterações k para convergir. Em termos gerais, o limite superior é atingido se os valores próprios deAforem distribuídos uniformemente (isto é, "salpicados") dentro de um intervalo do número de condiçãoκ.$\sim\sqrt{\kappa}$$A$$\kappa$

Aqui está uma declaração mais rigorosa. As versões determinísticas estão mais envolvidas, mas funcionam usando os mesmos princípios.

Teorema (pior opção de ). Escolher qualquer matriz ortogonal aleatório L , deixar λ 1 , ... , λ n ser n números reais uniformemente amostrados a partir do intervalo verdadeira [ 1 , κ ] , e deixou b = [ b 1 ; ... ; b n ] sejam n números reais amostrados iid do gaussiano padrão. Defina A = U d i a g ( λ 1$A$$U$$\lambda_1,\ldots,\lambda_n$$n$$[1,\kappa]$$b=[b_1;\ldots;b_n]$$n$Em seguida, no limite n → ∞ , gradientes conjugados vai convergência com uma probabilidade para uma ε solução precisa de um x = b em não menos do que Ω (

$$A=U\mathrm{diag}(\lambda_1,\ldots,\lambda_n)U^T.$$ $n\to\infty$$\epsilon$$Ax=b$iterações.$\Omega(\sqrt{\kappa}\log\epsilon^{-1})$

Prova. A prova padrão é baseada em aproximações polinomiais ótimas de Chebyshev, usando técnicas encontradas em vários locais, como o livro de Greenbaum ou o livro de Saad .

Tomando isso como minha pergunta original: sabemos se existe um RHS e um palpite inicial (sem sorte) que exigirá etapas?$\Theta(\sqrt{\kappa})$

A resposta para a pergunta é "não". A idéia desta resposta vem do comentário de Guido Kanschat.

Reivindicação: Para qualquer condição número , existe uma matriz$k$ , com esse número de condição para o qual o algoritmo CG terminará em no máximo duas etapas (para qualquer RHS dado e estimativa inicial).$A$

Considere onde A = d i a g ( 1 , κ , κ , … , κ ) . Então o número da condição de A é κ . Seja b ∈ R n o RHS e denote os autovalores de A como λ i onde λ i = { 1 i = 1 k i ≠ 1$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$

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

Nós primeiro considerar o caso em que , a estimativa inicial, é zero. Denuncie x ( 2 ) ∈ R n como a segunda estimativa de A - 1 b do algoritmo CG. Mostramos que x ( 2 ) = A - 1 b , mostrando ⟨ x ( 2 ) - A - 1 b , A ( x ( 2 ) - $x^{(0)} \in \mathbb{R}^n$$x^{(2)}\in \mathbb{R}^n$$A^{-1}b$$x^{(2)} =A^{-1}b$ . De fato, temos$\langle x^{(2)}-A^{-1}b, A(x^{(2)}-A^{-1}b)\rangle =0$

$$\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*}$$

$\widehat{p}$$\widehat{p}(x)= (1+\kappa-x)/\kappa$. So we proven the case for $x^{(0)}= 0$.

If $x^{(0)} \not = 0$, then $x^{(2)}= \overline{x^{(2)}}+ x^{(0)}$ where $\overline{x^{(2)} }$ is the second estimate of the CG algorithm with $b$ replaced with $\overline{b} = b-A x^{(0)}$. So we have reduced this case to the previous one.