Método do Gradiente Conjugado Precondicionado

Ir para a teoria do método

Resolução de \(Ax = b\) com Gradiente Conjugado Precondicionado

O sistema deve satisfazer: \(A \in \mathbb{R}^{n \times n}\) simétrica (\(A = A^T\)) e definida positiva (\(x^T A x > 0,\ \forall x \neq 0\)).

Parâmetros do Sistema

Recomendado: \(n \leq 10\) para verificação automática.
Ex: identidade para CG clássico; diagonal de \(A\) para Jacobi.

Teoria Matemática Rigorosa

1. Formulação Variacional

Dado \(A \in \mathbb{R}^{n \times n}\) simétrica e definida positiva, e \(b \in \mathbb{R}^n\), o sistema linear

\[ Ax = b\]

é equivalente ao problema de minimização do funcional quadrático

\[ \phi(x) = \frac{1}{2} x^T A x - b^T x.\]

O gradiente é \(\nabla \phi(x) = Ax - b\), e o ponto crítico satisfaz \(\nabla \phi(x) = 0 \iff Ax = b\).

2. Direções \(A\)-Conjugadas

Um conjunto de vetores \(\{p_0, p_1, \dots, p_{k}\}\) é dito \(A\)-conjugado se

\[ p_i^T A p_j = 0 \quad \text{para todo } i \neq j.\]

Se \(A\) é definida positiva, vetores \(A\)-conjugados são linearmente independentes. O método CG constrói tais direções iterativamente.

3. Algoritmo do Gradiente Conjugado Precondicionado (PCG)

Entrada: \(A = A^T \succ 0\), \(b\), \(M^{-1} \approx A^{-1}\), \(x_0\), \(\varepsilon > 0\), \(k_{\max}\)

  1. \(r_0 \gets b - A x_0\)
  2. \(z_0 \gets M^{-1} r_0\)
  3. \(p_0 \gets z_0\)
  4. \(k \gets 0\)
  5. Enquanto \(\|r_k\|_2 \geq \varepsilon\) e \(k < k_{\max}\):
    • \(\alpha_k \gets \dfrac{r_k^T z_k}{p_k^T A p_k}\)
    • \(x_{k+1} \gets x_k + \alpha_k p_k\)
    • \(r_{k+1} \gets r_k - \alpha_k A p_k\)
    • \(z_{k+1} \gets M^{-1} r_{k+1}\)
    • \(\beta_k \gets \dfrac{r_{k+1}^T z_{k+1}}{r_k^T z_k}\)
    • \(p_{k+1} \gets z_{k+1} + \beta_k p_k\)
    • \(k \gets k + 1\)

Saída: \(x_k\)

Propriedade fundamental: os resíduos são ortogonais: \(r_i^T r_j = 0\) para \(i \neq j\), e as direções são \(A\)-conjugadas.

4. Convergência Finita e Análise Espectral

Em aritmética exata, o CG converge em no máximo \(n\) iterações. A taxa de convergência depende do número de condição \(\kappa(A) = \lambda_{\max}/\lambda_{\min}\):

\[\|x - x_k\|_A \leq 2 \left( \frac{\sqrt{\kappa(A)} - 1}{\sqrt{\kappa(A)} + 1} \right)^k \|x - x_0\|_A,\]

onde \(\|v\|_A = \sqrt{v^T A v}\). Com precondicionamento, substitui-se \(\kappa(A)\) por \(\kappa(M^{-1}A)\).

O ideal é \(\kappa(M^{-1}A) \approx 1\), o que implica convergência em poucas iterações.

5. Precondicionadores

Um bom precondicionador \(M\) deve satisfazer:

  • \(M \approx A\)
  • \(M^{-1}v\) é barato de computar
  • \(\kappa(M^{-1}A) \ll \kappa(A)\)

Exemplos clássicos:

  • Jacobi: \(M = \mathrm{diag}(A)\)
  • SSOR: \(M = (D + \omega L) D^{-1} (D + \omega L)^T\)
  • ILU(0): fatoração LU incompleta
  • Cholesky Incompleto (IC): \(M = LL^T\) preservando esparsidade

6. Referências Fundamentais

Hestenes, M. R.; Stiefel, E. Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 1952.

Saad, Y. Iterative Methods for Sparse Linear Systems. 2nd ed., SIAM, 2003.

Greenbaum, A. Iterative Methods for Solving Linear Systems. SIAM, 1997.

Nocedal, J.; Wright, S. Numerical Optimization. Springer, 2006. (Cap. 5)

Exemplos com Verificação Automática

Todos os exemplos abaixo satisfazem \(A = A^T \succ 0\).

Pré-Condicionador Cholesky Incompleto

Matriz de Exemplo para Cholesky Incompleto

Matriz \(A\):
\[ A = \begin{bmatrix} 0.2 & 0.1 & 1.0 & 1.0 & 0.0 \\ 0.1 & 4.0 & -1.0 & 1.0 & -1.0 \\ 1.0 & -1.0 & 60.0 & 0.0 & -2.0 \\ 1.0 & 1.0 & 0.0 & 8.0 & 4.0 \\ 0.0 & -1.0 & -2.0 & 4.0 & 700.0 \end{bmatrix} \]
Vetor \(b\):
\[ b = \begin{bmatrix} 1.0 \\ 2.0 \\ 3.0 \\ 4.0 \\ 5.0 \end{bmatrix} \]
// Os resultados aparecerão aqui... Clique nos botões acima para executar os testes.

Teoria do Cholesky Incompleto

Para uma matriz simétrica positiva definida \(A\), a fatoração de Cholesky incompleta (IC(0)) calcula uma matriz triangular inferior \(L\) tal que:

\[ A \approx LL^T \]

onde \(L\) preserva o padrão de esparsidade de \(A\).

Algoritmo IC(0):

\[ \begin{aligned} &\text{Para } i = 1 \text{ até } n: \\ &\quad L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2} \\ &\quad \text{Para } j = i+1 \text{ até } n: \\ &\quad\quad \text{Se } A_{ji} \neq 0 \text{ então} \\ &\quad\quad\quad L_{ji} = \frac{A_{ji} - \sum_{k=1}^{i-1} L_{jk}L_{ik}}{L_{ii}} \end{aligned} \]

Vantagens do IC(0):