Convergência de Métodos Iterativos

Prévia do material em texto

130 Cálculo Numérico
Agora, suponhamos que ρ(T ) < 1 e seja 0 < ε < 1 − ρ(T ). Então, existe
1 ≤ p ≤ ∞ tal que (veja [8], Teorema 3, página 12):
‖T‖p ≤ ρ(T ) + ε < 1. (4.237)
Assim, temos:
lim
k→∞
‖T k‖p ≤ lim
k→∞
‖T‖mp = 0. (4.238)
Da equivalência entre as normas segue a recíproca.
Observação 4.7.1. Observamos que:
lim
k→∞
‖T k‖p = 0, ,1 ≤ p ≤ ∞,⇔ lim
k→∞
tkij = 0, 1 ≤ i,j ≤ n. (4.239)
Lema 4.7.2. Se ρ(T ) < 1, então existe (I − T )−1 e:
(I − T )−1 =
∞∑
k=0
T k. (4.240)
Demonstração. Primeiramente, provamos a existência de (I − T )−1. Seja λ um
autovalor de T e x um autovetor associado, isto é, Tx = λx. Então, (I − T )x =
(1 − λ)x. Além disso, temos |λ| < ρ(T ) < 1, logo (1 − λ) 6= 0, o que garante que
(I−T ) é não singular. Agora, mostramos que (I−T )−1 admite a expansão acima.
Do Lema 4.7.1 e da Observação 4.7.1 temos:
(I − T )
∞∑
k=0
T k = lim
m→∞
(I − T )
m∑
k=0
T k = lim
m→∞
(I − Tm+1) = I, (4.241)
o que mostra que (I − T )−1 =
∞∑
k=0
T k.
Teorema 4.7.1. A sequência recursiva {x(k)}k∈N dada por:
x(k+1) = Tx(k) + c (4.242)
converge para solução de x = Tx + c para qualquer escolha de x(1) se, e somente
se, ρ(T ) < 1.
Demonstração. Primeiramente, assumimos que ρ(T ) < 1. Observamos que:
x(k+1) = Tx(k) + c = T (Tx(k−1) + c) + c (4.243)
= T 2x(k−1) + (I + T )c (4.244)
... (4.245)
= T (k)x(1) +
(∑k−1
k=0 T
k
)
c. (4.246)
Licença CC-BY-SA-3.0. Contato: reamat@ufrgs.br
https://creativecommons.org/licenses/by-sa/3.0/
reamat@ufrgs.br
4.7. MÉTODOS ITERATIVOS PARA SISTEMAS LINEARES 131
Daí, do Lema 4.7.1 e do Lema 4.7.2 temos:
lim
k→∞
x(k) = (I − T )(−1)c. (4.247)
Ora, se x∗ é a solução de x = Tx+ c, então (I −T )x∗ = c, isto é, x∗ = (I −T )−1c.
Logo, temos demonstrado que x(k) converge para a solução de x = Tx + c, para
qualquer escolha de x(1).
Agora, suponhamos que x(k) converge para x∗ solução de x = Tx + c, para
qualquer escolha de x(1). Seja, então, y um vetor arbitrário e x(1) = x∗ − y.
Observamos que:
x∗ − x(k+1) = (Tx∗ + c)− (Tx(k) + c) (4.248)
= T (x∗ − x(k)) (4.249)
... (4.250)
= T (k)(x∗ − x(1)) = T (k)y. (4.251)
Logo, para qualquer 1 ≤ p ≤ ∞, temos, :
0 = lim
k→∞
x∗ − x(k+1) = lim
k→∞
T (k)y. (4.252)
Como y é arbitrário, da Observação 4.7.1 temos lim
k→∞
‖T (k)‖p = 0, 1 ≤ p ≤ ∞.
Então, o Lema 4.7.1 garante que ρ(T ) < 1.
Observação 4.7.2. Pode-se mostrar que tais métodos iterativos tem taxa de con-
vergência super linear com:
‖x(k+1) − x∗‖ ≈ ρ(T )k‖x(1) − x∗‖. (4.253)
Para mais detalhes, veja [8], pág. 61-64.
Exemplo 4.7.7. Mostre que, para qualquer escolha da aproximação inicial, ambos
os métodos de Jacobi e Gauss-Seidel são convergentes quando aplicados ao sistema
linear dado no Exemplo 4.7.4.
Solução. Do Teorema 4.7.1, vemos que é necessário e suficiente que ρ(TJ) < 1 e
ρ(TG) < 1. Computando estes raios espectrais, obtemos ρ(TJ) ≈ 0,32 e ρ(TG) ≈
0,13. Isto mostra que ambos os métodos serão convergentes. ♦
Condição suficiente
Uma condição suficiente porém não necessária para que os métodos de Gauss-
Seidel e Jacobi convirjam é a que a matriz seja estritamente diagonal domi-
nante.
Licença CC-BY-SA-3.0. Contato: reamat@ufrgs.br
https://creativecommons.org/licenses/by-sa/3.0/
reamat@ufrgs.br