Como estabelecer que um método iterativo para grandes sistemas lineares é convergente na prática?

Na ciência computacional, freqüentemente encontramos grandes sistemas lineares que somos obrigados a resolver por alguns meios (eficientes), por exemplo, por métodos diretos ou iterativos. Se focarmos neste último, como podemos estabelecer que um método iterativo para resolver grandes sistemas lineares é convergente na prática?

Está claro que podemos fazer análises de tentativa e erro (cf. Por que meu solucionador de iterações linear não está convergindo? ) E confiar em métodos iterativos que garantem a convergência por provas ou que tenham uma boa base de experiência (por exemplo, métodos do subespaço de Krylov, como CG e GMRES para sistemas simétricos e não simétricos, respectivamente).

Mas, o que pode ser feito para estabelecer convergência na prática? e o que é feito?

Para muitas equações diferenciais parciais que surgem na natureza, particularmente com fortes não linearidades ou anisotropias, a escolha de um pré-condicionador apropriado pode ter um grande efeito sobre se o método iterativo converge rapidamente, lentamente ou de modo algum. Exemplos de problemas que são conhecidos por terem pré-condicionadores rápidos e eficazes incluem equações diferenciais parciais fortemente elípticas, nas quais o método multigrid frequentemente alcança rápida convergência. Há vários testes que se pode usar para avaliar a convergência; aqui vou usar a funcionalidade do PETSc como exemplo, pois é provavelmente a biblioteca mais antiga e mais madura para resolver iterativamente sistemas esparsos de equações lineares (e não lineares).

O PETSc usa um objeto chamado KSPMonitor para monitorar o progresso de um solucionador iterativo e decidir se o solucionador convergiu ou divergiu. O monitor usa quatro critérios diferentes para decidir se deve parar. Mais detalhes sobre a discussão aqui podem ser encontrados na página de manual do KSPGetConvergedReason () .

Assumimos notoriamente que o usuário está resolvendo o seguinte sistema de equações para : Chamamos o palpite atual e definimos o residual base no estilo de pré-condicionamento:A x = b x $x$

1. Pré-condicionamento à Esquerda$\left(P^{-1}(Ax − b) \right)$ R =P - 1 (A x -b)

   $$\hat{r}=P^{-1}(A\hat{x}-b)$$

2. Pré-condicionamento Não / Direito$\left(AP^{-1}Px = b \right)$ R =A x -b

   $$\hat{r}=A\hat{x}-b$$

Critérios de convergência

1. Tolerância absoluta - O critério de tolerância absoluta é atendido quando a norma do resíduo é menor que a constante predefinida : $a_{tol}$ $$\|\hat{r}\| \le a_{tol}$$
2. Tolerância relativa - O critério de tolerância relativa é atendido quando a norma do resíduo é menor que a norma do lado direito por um fator da constante predefinida : ‖ r ‖ ≤ r t o l ⋅ ‖ b $r_{tol}$ $$\|\hat{r}\| \le r_{tol}\cdot \|b\|$$
3. Outros critérios - A solução iterativa também pode convergir devido à detecção de um pequeno passo ou curvatura negativa.

Critérios de divergência

1. Iterações máximas - O número de iterações que um solucionador pode realizar é limitado pelas iterações máximas. Se nenhum dos outros critérios tiver sido atendido quando o número máximo de iterações for atingido, o monitor retornará como divergente.

2. NaN residual - Se em algum momento o residual for avaliado para NaN, o solucionador retornará como divergente.

3. Divergência da norma residual O monitor retorna como divergente se a qualquer momento a norma do resíduo for maior que a norma do lado direito por um fator da constante predefinida : ‖ r ‖ ≥ d t o l ⋅ ‖ b $d_{tol}$

   $$\|\hat{r}\| \ge d_{tol}\cdot \|b\|$$

4. Divisão do solucionador O próprio método de Krylov pode sinalizar divergências se detectar uma matriz ou pré-condicionador singular.