[8] Ao resolver um sistema linear A x=b por um método direto, vários problemas podem implicar a obtenção de uma solução x0, apenas aproximada para x. Vamos chamar r0=b-A x0 o resíduo associado a x0. Note que A e=r0. Se x=e+x0 fosse resolvido sem erro, então A x=b seria a solução do sistema. Isto não acontece, mas esta observação pode ser usada como base para um processo iterativo para o “refinamento” da solução aproximada.
É razoável supormos que x0 solução aproximada de x1 seja uma solução aproximada de r1=b-A x1, melhor que i=1,2, ldots, N. Com r=b-A x calculamos o novo resíduo e e continuamos o processo. Na realidade repetir o processo quantas vezes quisermos, o que nos fornece o seguinte algoritmo:
Para A e=r
Calcular o resíduo, x=x+e (dupla precisão)
Determinar mid ri<, solução de L
Corrigir a solução, U.
Se max A tol ou tol, fim.
(a) Justifique porque devemos usar a fatoração LU neste caso para resolver os sistemas envolvidos.
(b) Neste caso, não devemos sobrepor e em . Justifique.

Passo 1

Então, o enunciado fala sobre o método de refinamento iterativo de uma solução aproximada A x = b, de um sistema linear
r0 = b - A x0
A gente define o resíduo
e resolve para corrigir , obtendo . Repetimos (calcula resíduo, resolve , corrige ) até o resíduo ou a correção serem menores que a tolerância.
Conteúdo: métodos diretos em Álgebra Linear Numérica (fatoração LU, resolução de sistemas por substituições) e refinamento iterativo.
O que vamos precisar:
  • Saber que se vamos resolver várias vezes com o mesmo , é eficiente usar uma fatoração (LU) e, a cada passo, apenas fazer substituições para cada novo .
  • Entender por que não podemos sobrescrever pelos fatores e (precisamos de intacto para recalcular o resíduo em precisão dupla).

Passo 2

(a) Por que usar fatoração LU para resolver A = L,U em cada iteração?
  1. Custo de refatorar do zero: cada eliminação de Gauss direta custa .
  2. Como em cada iteração só muda o vetor direito , mas a matriz é a mesma, basta fazer uma única fatoração (talvez com pivotamento parcial), que custa uma vez só.
  3. Depois, para cada novo gerado pelo refinamento, resolvemos:
    i) por substituição para frente ( ),
    ii) por substituição para trás ( ).
  4. Assim, cada iteração fica custando só em vez de , o que é muito mais rápido quando o número de iterações é razoável.

Passo 3

(b) Por que não sobrepor e em ?
  1. Para calcular o resíduo em dupla precisão a cada iteração, precisamos do original.
  2. Se a gente tivesse destruído colocando nele os coeficientes de e , não conseguiríamos reavaliar com a matriz exata.
  3. Além disso, o refinamento depende de medir com precisão : qualquer erro adicional em empobrece o refinamento.
  4. Logo, guardamos o completo em uma área de memória separada e armazenamos e também em áreas separadas (ou num único bloco, mas sem destruir a cópia de ).

Resposta

(a) Usamos fatoração LU porque estamos resolvendo várias vezes com a mesma matriz . Fatorar uma única vez custa e reaproveitar os fatores em cada iteração custa só .
(b) Não podemos sobrescrever pelos fatores e pois precisamos do original para computar o resíduo em dupla precisão e garantir a eficácia do refinamento.

Exercícios relacionados