Cálculo Numérico

Prévia do material em texto

UVA
Universidade
Veiga de Almeida
Ca´lculo Nume´rico - 2010.01 - 1a Lista de exerc´ıcios
Me´todos Iterativos para Sistemas Lineares
Prof. Fernando Marinho
Sobre Mo´dulos e Normas
Mo´dulos
x ∈ IR, |x| =
{
x, se x ≥ 0
−x, se x < 0
Propriedades
1. |x| ≥ 0, |x| = 0⇔ x = 0
2. |k.x| = |k|.|x|
3. |a+ b| ≤ |a|+ |b|
Normas
Uma func¸a˜o N: IRn(ou Mmxn)−→ IR e´ chamada NORMA se:
1. N(x) = 0⇔ x = 0
2. N(k.x) = |k|.N(x)
3. N(a+ b) ≤ N(a) +N(b)
Exemplos.
Normas para vetores de IRn =

x1
x2
...
xn

1. Norma Euclideana
‖x‖ =
√√√√ n∑
i=1
(xi)2
Numericamente: ∥∥∥∥∥
(
3
−4
)∥∥∥∥∥ = √32 + (−4)2 = 5
1
2. Norma do Ma´ximo
‖x‖ma´x = ma´x1≤i≤n{|xi|}, numericamente:∥∥∥∥∥
(
3
−4
)∥∥∥∥∥
ma´x
= ma´x {|3|, | − 4|} = 4
Obs. Note que
‖x‖ma´x ≤ ‖x‖ ≤
√
n.‖x‖ma´x
Isto implica que quando a norma de um vetor e´ muito pro´xima de zero, na˜o importa
qual das duas estamos considerando.
Norma para matrizes de Mmxn(aij)
Consideraremos a norma do ma´ximo, para A(aij)
‖A‖ma´x = ma´x1≤i≤n

n∑
j=1
|aij|
 .
Numericamente: ∥∥∥∥∥
[
2 −5
−4 1
]∥∥∥∥∥
ma´x
= ma´x{7, 5} = 7
Propriedade
Para A ∈Mm×n e X ∈ IRn,
‖ A.X ‖ma´x≤‖ A ‖ma´x . ‖ X ‖ma´x .
Sobre Progresso˜es Geome´tricas
Uma sequ¨eˆncia de nu´meros da forma a, a.r, a.r2, a.r3, ... e´ chamada Progressa˜o Geome´trica
e podemos escrever a soma de seus n primeiros termos da seguinte forma:
Sn = a+ a.r + a.r
2 + ...+ a.rn−1, logo
r.Sn = a.r + a.r
2 + a.r3 + ...+ a.rn ⇒
Sn − r.Sn = a− a.rn ⇒
Sn =
a.(1− rn)
1− r .
Se r < 1, temos que rn tende a zero, quando n tende a infinito, logo
a+ a.r + a.r2 + a.r3 + ... =
∞∑
i=0
a.ri =
a
1− r .
Exemplos.
2
1.
2 + 2.3 + 2.32 + ...+ 2.38 =
2.(1− 39)
1− 3 = 19682
2.
1 + 1/2 + 1/4 + ... =
1
1− 1/2 = 1
Soluc¸a˜o de Sistemas Lineares por Me´todos Iterativos
Gauss-Jacobi
Dada uma matriz quadrada An×n e um vetor B ∈ IRn, vamos supor que o sistema
linear A.X = B tenha soluc¸a˜o X.
Decompondo a matriz A em uma soma de uma matriz triangular inferior L, uma
matriz diagonal D e uma triangular superior U , temos:
A.X = B ⇒ (L+D + U).X = B ⇒ D.X = B − (L+ U).X
⇒ X = D−1.B −D−1.(L+ U).X.
No Me´todo Gauss-Jacobi, a apartir de uma aproximac¸a˜o inicial X0 para X, criamos
uma sequ¨eˆncia
⇒ Xk+1 = D−1.B −D−1.(L+ U).Xk.
Neste caso, para que as aproximac¸o˜es Xk convirjam para X e´ necessa´rio que
Xk+1 −Xk = −D−1.(L+ U).(Xk −Xk−1),
tenham normas cada vez mais proximas de zero. Assim,
‖ Xk+1 −Xk ‖=‖ −D−1.(L+ U).(Xk −Xk−1) ‖⇒
‖ Xk+1 −Xk ‖≤‖ −D−1.(L+ U) ‖ . ‖ Xk −Xk−1 ‖ .
Fazendo Ek =‖ Xk+1 −Xk ‖, que chamaremos de Erro Indireto, e α =‖ −D−1.(L +
U) ‖, temos
Ek+1 ≤ α.Ek,∀k ≥ 1.
Dessa forma,
E2 ≤ α.E1;
E3 ≤ α.E2 ⇒ E3 ≤ α2.E1;
e assim,
Ek ≤ αk−1.E1.
Da´ı, se α < 1, temos que αk−1 tende a zero e assim Ek tambe´m tende a zero.
3
Teorema 1 Se uma sequeˆncia {Xk} ⊂ IRn satisfaz
∀ε > 0, ∃N ∈ IN / i, j ≥ N ⇒ ‖Xi −Xj‖ < ε,
enta˜o
∃X ∈ IRn / limk→∞Xk = X.
Note que, no nosso caso, Xk sa˜o as aproximac¸o˜es da soluc¸a˜o exata X, e:
i < j, ‖Xi −Xj‖ ≤ ‖Xi −Xi+1 +Xi+1 − ...Xj‖ ≤ αi.E1 + ... + αj−1.E1 ≤ E1.
∞∑
l=0
α
i+l
.
Esta u´ltima expressa˜o tende a zero, se α < 1, quando i tende a infinito.
Crite´rio das Linhas
α = ma´x1≤i≤n

n∑
j=1,j 6=i
|aij|
aii

Note que
‖ Xk −X ‖≤‖ Xk −Xk+1 +Xk+1 −X ‖≤‖ Xk+1 −Xk ‖ + ‖ Xk+1 −X ‖,
‖ Xk −X ‖≤ Ek+1+ ‖ Xk+1 −X ‖,∀k ≥ 1,
‖ Xk −X ‖≤ Ek+1 + Ek+2 + Ek+3 + ...,
‖ Xk −X ‖≤ αk.E1 + αk+1.E1 + ...,
‖ Xk −X ‖≤ E1.
∞∑
i=k
αi = E1.
αk
1− α.
Definimos enta˜o o Erro Direto
ek = ‖X −Xk‖ ≤ E1. α
k
1− α.
Resumo
• Convergeˆncia: α < 1⇒ convergeˆncia
• Iterac¸o˜es: Xk+1 = D−1.B −D−1.(L+ U).Xk
• Erro Indireto: Ek =‖ Xk −Xk−1 ‖≤ αk−1.E1
• Precisa˜o Indireta ε em Xk: Ek < ε
• Erro Direto: ek = ‖X −Xk‖ ≤ E1. α
k
1− α
4
• Precisa˜o Direta ² em Xk: ek < ²
Gauss-Seidel
A.X = B ⇒ (L+D + U).X = B
(L+D).X = B − U.X ⇒ X = (L+D)−1.B − (L+D)−1.U.X
Definimos:
Xk+1 = (L+D)
−1.B − (L+D)−1.U.Xk,
a ana´lise de convergeˆncia depende de β, definido abaixo.
Crite´rio de Sassenfeld
Considerando
β = ma´x1≤i≤n {βi}
β1 =
n∑
j=1,j 6=1
|b1j|
b11
βk =
k−1∑
j=1
|bij|.βj +
n∑
j=k+1
|bij|
bkk
Resumo
• Convergeˆncia: β < 1⇒ convergeˆncia
• Iterac¸o˜es: Xk+1 = (L+D)−1.B − (L+D)−1.U.Xk
• Erro Indireto: Ek =‖ Xk −Xk−1 ‖≤ βk−1.E1
• Precisa˜o Indireta ε em Xk: Ek < ε
• Erro Direto: ek = ‖X −Xk‖ ≤ E1. β
k
1− β
• Precisa˜o Direta ² em Xk: ek < ²
5
Exerc´ıcios
Exerc´ıcio 1 Verifique se o sistema linear abaixo converge pelo Me´todo
de Gauss-Jacobi. Para X0 =

0
0
0
, obtenha uma apro-ximac¸a˜o Xk para
a soluc¸a˜o exata com precisa˜o ε = 0, 2.
10x− 2y + 2z = 42
3x+ 12y + z = −11
2x− y − 10z = −32
Exerc´ıcio 2 Resolva cada sistema linear abaixo utilizando o Me´todo
Iterativo de Gauss-Seidel, com a precisa˜o ε indicada,
X0 =

0
0
0
 verificando inicialmente suas respectivas convergeˆncias uti-
lizando o Crite´rio de Sassenfeld:
a)

10x− 2y + 2z = 42
3x+ 12y + z = −11
2x− y − 10z = −32
, ε = 0, 2
b)

8x− 2y + z = 12
3x+ 6y + z = 10
2x− y − 5z = 31
, ε = 0, 1
c

15x− 3y + z = 5
3x+ 16y + z = 8
2x− y − 15z = 11
, ε = 4.10−4
d

5x− 30y + z = 7
30x+ 6y + z = 8
2x− y − 20z = 11
, ε = 10−4
e

15x− 3y + z − w = 5
3x+ 16y + z + w = 4
2x− y − 20z − 2w = 11
x− 3y + z − 18w = 9
, ε = 10−4
6
Exerc´ıcio 3 Observe que no item d acima, se houver uma comutac¸a˜o
nas duas primeiras equac¸o˜es, o crite´rio de Sassenfeld sera´ satisfeito, o
que mostra que havera´ convergeˆncia. Aplique enta˜o Gauss-Seidel, com
o mesmo X0 e precisa˜o ε = 10
−4.
Exerc´ıcio 4 No exerc´ıcio 1, quantas iterac¸o˜es sa˜o necessa´rias para que
o erro ek = E1.
αk
1− α seja menor igual a 10
−4?
Exerc´ıcio 5 Quantas iterac¸o˜es, pelo Me´todo Gauss-Jacobi, sa˜o necessa´rias
para que o sistema

30x− y + z = 7
x+ 15y + z = 8
x− y − 10z = 9
atinja erro ek = E1.
αk
1− α menor
igual a 10−4?
Exerc´ıcio 6 E pelo Me´todo Gauss-Seidel?
Exerc´ıcio 7 Resolva o sistema linear abaixo com X0 vetor nulo, pelo
Me´todo Gauss-Seidel, com precisa˜o indireta ε = 7.10−3
15x− y = −3
6y + z − v = 10
2x− 8z + u = 1
−2y + 9u+ v = −4
x− y + 10v = 2
Exerc´ıcio 8 Quantas iterac¸o˜es sa˜o necessa´rias para obtermos, com
quatro casas decimais, precisa˜o indireta ε = 0, 0000(< 0, 00005 =
5.10−5)? Utilize todas as casas decimais que puder.
Exerc´ıcio 9 Quantas iterac¸o˜es sa˜o necessa´rias para obtermos, com
quatro casas decimais, a soluc¸a˜o exata, ou seja, precisa˜o direta ² =
0, 0000? Utilize todas as casas decimais que puder.
Exerc´ıcio 10 Lembrando que
‖X‖ma´x ≤ ‖X‖ ≤
√
n.‖X‖ma´x,
e que ‖Xk −X‖ma´x < 0, 00005, mostre que ‖Xk −X‖ < 0, 00011180
7
Respostas
1. X4 =

2, 9592
−1, 9900
3, 9959
, com erro indireto E4 = 0, 1152
2. a) X3 =

2, 9995
−1, 9993
3, 9998
, com erro indireto E3 = 0, 0402
b) X3 =

2, 5386
1, 3140
−5, 4474
, com erro indireto E3 = 0, 0905
c) X4 =

0, 4711
0, 4555
−0, 7009
, com erro indireto E3 = 0, 0003
d) Na˜o converge por este me´todo (o que na˜o implica que diverge!).
e) 5 iterac¸o˜es
3. X4 =

0, 2971
−0, 2341
−0, 5086

4. 13
5. 6
6. 4
7. X3 =

−0, 0826
1, 7569
−1, 1577
−0, 0968
0, 3840

8. 5
9. 10
8