Qual é o princípio por trás da convergência dos métodos do subespaço de Krylov para resolver sistemas lineares de equações?

Pelo que entendi, existem duas categorias principais de métodos iterativos para resolver sistemas lineares de equações:

Métodos estacionários (Jacobi, Gauss-Seidel, SOR, Multigrid)
Métodos de Krylov Subespaço (Gradiente Conjugado, GMRES, etc.)

Entendo que a maioria dos métodos estacionários funciona relaxando (suavizando) iterativamente os modos de Fourier do erro. Pelo que entendi, o método de Gradiente Conjugado (método subespaço Krylov) funciona por "reforço" através de um conjunto ideal de instruções de pesquisa de competências da matriz aplicado ao $n$ th residual. Esse princípio é comum a todos os métodos do subespaço de Krylov? Caso contrário, como caracterizamos o princípio por trás da convergência dos métodos do subespaço de Krylov, em geral?

linear-algebra convergence krylov-method conjugate-gradient Paulo
fonte

Sua análise de métodos estacionários é influenciada por problemas simples do modelo, porque eles podem ser analisados em termos dos modos de Fourier. Ele também ignora a direção alternada implícita (ADI) e muitos outros métodos. O objetivo da maioria dos "Métodos estacionários" é combinar muitos solucionadores "parciais aproximados" simples em um solucionador iterativo. O objetivo dos métodos de Krylov é acelerar (ou até impor) a convergência de uma determinada iteração linear estacionária.

Thomas Klimpel

Um artigo que acho que foi escrito para responder às suas perguntas é Ipsen e Meyer. A idéia por trás dos métodos de Krylov, Amer. Matemática. Monthly 105 (1998) pp. 889-899. É um artigo maravilhosamente bem escrito e esclarecedor, disponível aqui .

Andrew T. Barker

@ AndrewT.Barker: Impressionante! Obrigado Andrew! :)

Paul

Respostas:

Em geral, todos os métodos de Krylov buscam essencialmente um polinômio pequeno quando avaliado no espectro da matriz. Em particular, o th residual de um método Krylov (com zero de estimativa inicial) pode ser escrita sob a forma $n$

r_{n} = P_{n} (A) b

$r_n = P_n (A) b$

onde é algum polinômio monônico de grau . $P_n$ $n$

Se é diagonalizável, com , temos $A$ $A=V\Lambda V^{-1}$

\begin{array}{rcl} ‖ r_{n} ‖ & \leq & ‖ V ‖ \cdot ‖ P_{n} (Λ) ‖ \cdot ‖ V^{- 1} ‖ \cdot ‖ b ‖ \\ = & κ (V) \cdot ‖ P_{n} (Λ) ‖ \cdot ‖ b ‖ . \end{array}

$\begin{eqnarray*} \|r_n\| &\leq& \|V\|\cdot \|P_n(\Lambda)\|\cdot \|V^{-1}\|\cdot \|b\|\\ &=& \kappa(V) \cdot \|P_n(\Lambda)\| \cdot \|b\|. \end{eqnarray*}$

No caso de ser normal (por exemplo, simétrico ou unitário), sabemos que GMRES constrói esse polinômio através da iteração de Arnoldi, enquanto CG constrói o polinômio usando um produto interno diferente (consulte esta resposta para obter detalhes) . Da mesma forma, o BiCG constrói seu polinômio através do processo não simétrico de Lanczos, enquanto a iteração Chebyshev usa informações anteriores sobre o espectro (geralmente estimativas dos maiores e menores valores próprios para matrizes definidas simétricas). $A$ $\kappa(V) = 1.$

Como um exemplo interessante (motivado por Trefethen + Bau), considere uma matriz cujo espectro é este:

Espectro de matriz

No MATLAB, eu construí isso com:

A = rand(200,200);
[Q R] = qr(A);
A = (1/2)*Q + eye(200,200);

Se considerarmos o GMRES, que constrói polinômios que realmente minimizam o residual sobre todos os polinômios mônicos de grau , podemos prever facilmente o histórico residual observando o polinômio candidato $n$

P_{n} (z) = (1 - z)^{n}

$P_n (z) = (1-z)^n$

que no nosso caso dá

| P_{n} (z) | = \frac{1}{2^{n}}

$|P_n(z)| = \frac{1}{2^n}$

para no espectro de . $z$ $A$

Agora, se rodarmos o GMRES em um RHS aleatório e compararmos o histórico residual com esse polinômio, eles deverão ser bastante semelhantes (os valores polinomiais candidatos são menores que o residual do GMRES porque ): $\|b\|_2 > 1$

História residual

Reid.Atcheson
fonte

Você poderia esclarecer o que quer dizer com "pequeno no espectro da matriz"?

Paul

Tomado como um polinómio complexo, o polinómio

tem pequeno módulo numa região do plano complexo, que inclui o espectro de

. Imagine um gráfico de contorno sobreposto a um gráfico de dispersão dos valores próprios. Quão pequeno é pequeno? Depende do problema, se

é normal e do lado direito

A idéia básica, porém, é que a sequência de polinômios

procura se tornar progressivamente menor e menor no espectro, de modo que a estimativa residual na minha resposta tenda a

P_{n}

$P_n$

A

$A$

A

$A$

b .

$b.$

(P_{n})

$(P_n)$

0

$0$

precisa saber é o seguinte

@ Reid.Atcheson: Muito bem colocado. Posso recomendar escrever

como

e mencionar que é para matrizes normais?

‖ V ‖ ‖ V^{- 1} ‖

$\|V\|\|V^{-1}\|$

κ (V)

$\kappa(V)$

21412 Jack Poulson

O Laplaciano pré-condicionado pelo SOR ótimo possui um espectro muito semelhante a esta matriz de exemplo. Detalhes aqui: scicomp.stackexchange.com/a/852/119

Jed Brown

A rigor, o CGNE é independente do espectro, pois depende apenas de valores singulares.

Jed Brown

Em normas

Como um adendo à resposta de Reid.Atcheson, gostaria de esclarecer algumas questões sobre normas. Na iteração, o GMRES encontra o polinômio que minimiza a quantidade residual $n^{\mathrm{th}}$ $P_n$ $2$

r_{n} = A x_{n} - b = (P_{n} (A) - 1) b - b = P_{n} (A) b .

$r_n = A x_n - b = \big(P_n(A) - 1 \big)b - b = P_n(A) b .$

Suponha que seja SPD, então induz uma norma e . Então $A$ $A$ $A^{-1}$

\begin{aligned} ‖ r_{n} ‖_{A^{- 1}} & = r_{n}^{T} A^{- 1} r_{n} \\ = (A e_{n})^{T} A^{- 1} A e_{n} \\ = e_{n}^{T} A e_{n} \\ = ‖ e_{n} ‖_{A} \end{aligned}

$\begin{align*} \lVert r_n \rVert_{A^{-1}} &= r_n^T A^{-1} r_n \\ &= (A e_n)^T A^{-1} A e_n \\ &= e_n^T A e_n \\ &= \lVert e_n \rVert_{A} \end{align*}$

onde usamos o erro

e_{n} = x_{n} - x_{*} = x_{n} - A^{- 1} b = A^{- 1} r_{n}

$e_n = x_n - x_* = x_n - A^{-1} b = A^{-1} r_n$

$A$ $A^{-1}$ $A$ $2$ $A^T A$ $A$

Nitidez dos limites de convergência

Finalmente, há literatura interessante sobre os diferentes métodos de Krylov e sutilezas da convergência GMRES, especialmente para operadores não normais.

Nachtigal, Reddy e Trefethen (1992) Com que rapidez são as iterações não simétricas da matriz? (pdf do autor) fornece exemplos de matrizes para as quais um método supera todos os outros por um grande fator (pelo menos a raiz quadrada do tamanho da matriz).
Embree (1999) Qual é a descrição dos limites de convergência do GMRES? fornece uma discussão perspicaz em termos de pseudoespectra, que oferece limites mais nítidos e também se aplica a matrizes não diagonalizáveis.
Embree (2003) A tartaruga e a lebre reiniciam o GMRES (autor pdf)
Greenbaum, Pták e Strakoš (1996) Qualquer curva de convergência não crescente é possível para o GMRES

Jed Brown
fonte

Você parou o excelente livro de Olavi Nevanlinna: books.google.com/…

Matt Knepley 3/12/12

Métodos iterativos em poucas palavras:

$Ax=b$ $C$
$x = x + C b - C A x$ $x = x + Cb- CAx$ $\|I-CA\|<1$ $C$ $C=D^{-1}$ $D$ $A$
$U,V\subset \mathbb{C}^n$ $\tilde x \in U$ $b-A\tilde x$ $V$ $U$ $A$ $V$ $V=U$ $V=AU$

$V$ $\tilde x$ $U$ $U$ em cada iteração, terá a garantia (na aritmética exata) de encontrar a solução após várias etapas finitas.

$U$ $A$ $\tilde x$ .

Isso é bem explicado no livro de Youcef Saad sobre métodos iterativos .

Christian Clason
fonte