Matemática Numérica III

1 Sistemas Lineares 1.6 Método GMRES 2 Sistemas Não Lineares

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

1.7 Precondicionamento

Os métodos iterativos vistos neste capítulo estão todos sujeitos a aparesentarem uma convergência lenta, devido a problemas inerentes de aplicações típicas. Precondicionamento é a técnica mais comum para acelerar a convergência nestes casos. A ideia básica é transformar o sistema linear original em um sistema equivalente (chamado de sistema precondicionado) que seja mais favorável para a aplicação de um método iterativo escolhido. De forma geral, o sistema precondicionado é definido como

M^{-1}A\boldsymbol{x}=M^{-1}\boldsymbol{b},

(1.204)

onde $M$ é a matriz de precondicionamento, que deve ser escolhida de forma que o sistema precondicionado seja mais fácil de resolver do que o sistema original. A matriz $M$ deve ser tal que:

•

$M$ seja uma boa aproximação de $A$ , i.e. $M^{-1}A\approx I$ ;
•

$M\boldsymbol{y}=\boldsymbol{c}$ seja fácil de resolver.

Esta última condição vem do fato de que, na prática, não queremos calcular $M^{-1}$ explicitamente, mas sim resolver sistemas lineares $M\boldsymbol{y}=\boldsymbol{c}$ a cada passo do método iterativo.

No Seção 1.3, vimos métodos iterativos simples, baseados nas técnicas de relaxação como o método de Jacobi, o método de Gauss-Seidel, SOR e SSOR. Estes métodos podem ser vistos como métodos de precondicionamento, onde a matriz de precondicionamento $M$ é dada por:

•

Jacobi: $M_{\text{JAC}}=D$ , onde $D$ é a matriz diagonal de $A$ ;
•

Gauss-Seidel: $M_{\text{GS}}=D-L$ , onde $-L$ é a parte estritamente triangular inferior de $A$ ;
•

SOR: $M_{\text{SOR}}=(D-\omega L)$ , onde $\omega$ é o parâmetro de relaxação;
•

SSOR: $M_{\text{SSOR}}=(D-\omega U)D^{-1}(D-\omega L)$ , onde $-U$ é a parte estritamente triangular superior de $A$ .

1.7.1 GMRES precondicionado

O GMRES precondicionado é obtido aplicando o método GMRES ao sistema precondicionado

M^{-1}A\boldsymbol{x}=M^{-1}\boldsymbol{b}.

(1.205)

A implementação do GMRES precondicionado é semelhante à do GMRES básico, com a diferença de que, a cada passo do método, precisamos resolver um sistema linear com a matriz de precondicionamento $M$ . Ou seja, o algoritmo do GMRES precondicionado pode ser descrito como segue.

GMRES precondicionado

1.

Compute $\boldsymbol{r}_{0}=M^{-1}(A\boldsymbol{x}-\boldsymbol{b})$ , $\beta=\|\boldsymbol{r}\|_{0}$ , $\boldsymbol{v}_{1}=\boldsymbol{r}_{0}/\beta$
2.

Para $j=1,2,\dotsc,m$ :
3.

Compute $\boldsymbol{w}=M^{-1}A\boldsymbol{v}_{j}$
4.

Para $i=1,2,\dotsc,j$ :
5.

$h_{i,j}=(\boldsymbol{w},\boldsymbol{v}_{i})$
6.

$\boldsymbol{w}=\boldsymbol{w}-h_{i,j}\boldsymbol{v}_{i}$
7.

$h_{j+1,j}=\|\boldsymbol{w}|$
8.

Se $h_{j+1,j}=0$ , então pare
9.

$\boldsymbol{v}_{j+1}=\boldsymbol{w}/h_{j+1,j}$
10.

Defina $V_{m}=[\boldsymbol{v}_{1},\dotsc,\boldsymbol{v}_{m}]$ , $\bar{H}_{m}=[h_{i,j}]_{i=1,j=1}^{j+1,m}$
11.

Resolva o sistema de mínimos quadrados $\boldsymbol{y}_{m}=\min_{\boldsymbol{y}\in\mathbb{R}^{m}}\|\beta\boldsymbol{e}% _{1}-\bar{H}_{m}\boldsymbol{y}\|_{2}$
12.

Atualize a solução $\boldsymbol{x}_{m}=\boldsymbol{x}^{(0)}+V_{m}\boldsymbol{y}_{m}$
13.

Se $\boldsymbol{x}_{m}$ satisfaz o critério de parada, então pare.

Exemplo 1.7.1.

Consideremos novamente o problema de difusão-advecção 2D do Exemplo 1.6.1. Vamos aplicar o GMRES precondicionado com as matrizes de precondicionamento de Jacobi, Gauss-Seidel, SOR ( $\omega=1.3$ ) e SSOR ( $\omega=1.3$ ).

$n$	GMRES	JAC	GS	SOR	SSOR
11	29	29	14	13	8
21	60	60	35	32	13
41	132	132	80	77	26
81	293	293	174	206	64

Um exemplo de uma implementação Python do GMRES precondicionado segue abaixo.

Código 11: gmres_GS.py

⬇

1from scipy.sparse.linalg import spsolve, gmres, LinearOperator

3# contador de iterações

4niter = 0

5def callback(rk):

6 global niter

7 niter += 1

9def gmres_gs(A, b, x0, M,

10 rtol=1e-5, atol=0.0, maxiter=100000):

12 # M^(-1)

13 Minv_x = lambda x: spsolve(M, x)

14 M_inv = LinearOperator(A.shape, M_x)

16 niter = 0

17 x, info = gmres(A, b, x0, M=M_inv,

18 rtol=rtol, atol=atol, maxiter=maxiter,

19 callback=callback, callback_type='pr_norm')

21 return x, niter, info

Precondicionador ILU

O precondicionador de fatoração incompleta LU é uma técnica popular para precondicionamento de sistemas lineares esparsos. A ideia básica é aproximar a fatoração LU completa de uma matriz $A$ por uma fatoração incompleta, onde apenas alguns elementos da matriz são mantidos, buscando manter a esparsidade da $A$ . Isto resulta em uma matriz de precondicionamento $M$ que é mais fácil de inverter do que a matriz original $A$ , mas ainda captura as propriedades essenciais da matriz.

Exemplo 1.7.2.

Consideremos novamente o problema de difusão-advecção 2D do Exemplo 1.6.1. Vamos aplicar o GMRES com precondicionar ILU.

$n$	GMRES	ILU
11	29	2
21	60	2
41	132	7
81	293	88

1.7.2 Exercícios

Em construção

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Política de uso de dados