[8] Ao resolver um sistema linear
por um método direto, vários problemas podem implicar a obtenção de uma solução
, apenas aproximada para
. Vamos chamar
o resíduo associado a
. Note que
. Se
fosse resolvido sem erro, então
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
solução aproximada de
seja uma solução aproximada de
, melhor que
. Com
calculamos o novo resíduo
e continuamos o processo. Na realidade repetir o processo quantas vezes quisermos, o que nos fornece o seguinte algoritmo:
Para
Calcular o resíduo,
(dupla precisão)
Determinar
, solução de
Corrigir a solução,
.
Se max
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.
Calcular o resíduo,
Determinar
Corrigir a solução,
Se max
(a) Justifique porque devemos usar a fatoração LU neste caso para resolver os sistemas envolvidos.
(b) Neste caso, não devemos sobrepor
Passo 1
Então, o enunciado fala sobre o método de refinamento iterativo de uma solução aproximada
de um sistema linear
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:
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
em cada iteração?
- Custo de refatorar do zero: cada eliminação de Gauss direta custa
. - 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ó. - Depois, para cada novo
gerado pelo refinamento, resolvemos:
i)por substituição para frente ( ),
ii)por substituição para trás ( ). - 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
?
- Para calcular o resíduo
em dupla precisão a cada iteração, precisamos do original. - Se a gente tivesse destruído
colocando nele os coeficientes de e , não conseguiríamos reavaliar com a matriz exata. - Além disso, o refinamento depende de medir com precisão
: qualquer erro adicional em empobrece o refinamento. - 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.
(b) Não podemos sobrescrever