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

11

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?

Allan P. Engsig-Karup
fonte
1
Ótima pergunta! Quando você diz 'estabelecer convergência', você quer dizer 'estabelecer que a solução está convergindo' ou 'estabelecer que a convergência acontecerá'? Eu sei, por exemplo, que o objeto PETSc KSP possui algumas técnicas padrão para testar a convergência (a norma de erro está diminuindo, número máximo de iterações). Esse é o tipo de resposta que você está procurando?
Aron Ahmadia
@aron: Eu acho que será interessante ver respostas abordando ambos os problemas.
Allan P. Engsig-Karup

Respostas:

6

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 rx

Ax=b

x^r^
  1. Pré-condicionamento à Esquerda(P1(Axb)) R =P - 1 (A x -b)

    r^=P1(Ax^b)
  2. Pré-condicionamento Não / Direito(AP1Px=b) R =A x -b

    r^=Ax^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 : atol
    r^atol
  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 :rr t o lb rtol
    r^rtolb
  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 : rd t o lb dtol

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

Aron Ahmadia
fonte