Calculo Numerico
267 pág.

Calculo Numerico


DisciplinaCálculo Numérico16.815 materiais273.848 seguidores
Pré-visualização35 páginas
sa\u2dco ineficientes. A te´cnica iterativa para resolver um sistema linear
Ax = b de n×n elementos, sera´ proposto da seguinte forma: parte-se de uma aprox-
imac¸a\u2dco inicial x0 e enta\u2dco constro´i-se consecutivamente os vetores x1, x2, ..., ate´ que
a condic¸a\u2dco de converge\u2c6ncia
|xk\u2212xk\u22121|
xk
< \u1eb seja satisfeita.
4Matriz do sistema Ax = b
66 Cap´\u131tulo 3 - Sistemas Lineares e na\u2dco -Lineares
O primeiro me´todo iterativo para soluc¸a\u2dco de sistemas lineares indicado e´ o de
Jacobi.
3.2.1 Me´todo de Jacobi: Me´todo dos deslocamentos simulta\u2c6neos
Considere o sistema\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
a11x1 + a12x2 + · · ·+ a1nxn = b1
a21x1 + a22x2 + · · ·+ a2nxn = b2
...
...
...
an1x1 + an2x2 + · · · + annxn = bn
e exigindo que aii 6= 0, i = 1, 2, . . . , n, isola-se o vetor X mediante a separac¸a\u2dco do
elemento diagonal, conforme\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
x1 =
b1
a11
\u2212 1
a11
(a12x2 + a13x3 + · · · + a1nxn)
x2 =
b2
a22
\u2212 1
a22
(a21x1 + a23x3 + · · · + a2nxn)
...
...
...
xn =
bn
ann
\u2212 1
ann
(an1x1 + an2x2 + · · ·+ ann\u22121xn\u22121)
Assim, tem-se X = CX +D, onde
C =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
0 \u2212a12
a11
\u2212a13
a11
. . . \u2212a1n
a11
\u2212a21
a22
0 \u2212a23
a22
. . . \u2212a2n
a22
...
...
...
...
\u2212an1
ann
\u2212an2
ann
\u2212an3
ann
. . . 0
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb
e D =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
b1
a11
b2
a22
...
bn
ann
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb
Fund. de Ca´lculo Nume´rico para Engenheiros 67
O me´todo de Jacobi corresponde a resolver\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
x
(k+1)
1 =
1
a11
(b1 \u2212 a12x(k)2 \u2212 a13x(k)3 \u2212 · · · \u2212 a1nx(k)n )
x
(k+1)
2 =
1
a22
(b2 \u2212 a21x(k)1 \u2212 a23x(k)3 \u2212 · · · \u2212 a2nx(k)n )
...
x
(k+1)
n =
1
ann
(bn \u2212 an1x(k)1 \u2212 an2x(k)2 \u2212 · · · \u2212 ann\u22121x(k)n\u22121)
(3.1)
ate´ que um crite´rio de converge\u2c6ncia seja satisfeito.
Exemplo 3.6: Resolver o sistema pelo me´todo de Jacobi\uf8f1\uf8f4\uf8f2\uf8f4\uf8f3
10x1 + x2 + x3 = 12
x1 + 10x2 + x3 = 12
x1 + x2 + 10x3 = 12
Soluc¸~ao: A soluc¸a\u2dco deste sistema e´ x1 = x2 = x3 = 1. Para resolve\u2c6-lo pelo
me´todo de Jacobi, ele deve ser disposto na forma (3.1), ou seja, ja´ dividindo todas
as linha por 10 \uf8f1\uf8f4\uf8f2\uf8f4\uf8f3
x
(k+1)
1 = 1, 2\u2212 0, 1x(k)2 \u2212 0, 1x(k)3
x
(k+1)
2 = 1, 2\u2212 0, 1x(k)1 \u2212 0, 1x(k)3
x
(k+1)
3 = 1, 2\u2212 0, 1x(k)1 \u2212 0, 1x(k)2
Seguindo o procedimento ja´ descrito e iniciando o processo iterativo com X(0)
T
=
[0 0 0], sa\u2dco obtidas as aproximac¸o\u2dces sucessivas apresentadas na tabela 3.2. Este
me´todo e´ normalmente empregado para sistemas de pequeno porte; da ordem 101
ou 102.
Uma simples modificac¸a\u2dco do me´todo de Jacobi conduz ao me´todo de Gauss-Seidel.
68 Cap´\u131tulo 3 - Sistemas Lineares e na\u2dco -Lineares
Tabela 3.2: Me´todo de Jacobi
k x
(k)
1 x
(k)
2 x
(k)
3
0 0 0 0
1 1,2 1,2 1,2
2 0,96 0,96 0,96
3 1,008 1,008 1,008
4 0,9984 0,9984 0,9984
5 1,00032 1,00032 1,00032
3.2.2 Me´todo de Gauss-Seidel: Me´todo dos deslocamentos
sucessivos
Neste me´todo, o sistema Ax = b e´ escrito na forma equivalente X = CXm + D
por separac¸a\u2dco dos elementos da diagonal.
A expressa\u2dco resultante corresponde a
\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
x
(k+1)
1 =
1
a11
(b1 \u2212 a12x(k)2 \u2212 a13x(k)3 \u2212 · · · \u2212 a1nx(k)n )
x
(k+1)
2 =
1
a22
(b2 \u2212 a21x(k+1)1 \u2212 a23x(k)3 \u2212 · · · \u2212 a2nx(k)n )
x
(k+1)
3 =
1
a33
(b3 \u2212 a31x(k+1)1 \u2212 a32x(k+1)2 \u2212 a34x(k)4 \u2212 · · · \u2212 a3nx(k)n )
...
x
(k+1)
n =
1
ann
(bn \u2212 an1x(k+1)1 \u2212 an2x(k+1)2 \u2212 · · · \u2212 ann\u22121x(k+1)n\u22121 )
Desta forma, no momento de se calcular x
(k+1)
j usa-se todos os valores x
(k+1)
1 , . . . , x
(k+1)
j\u22121
ja´ obtidos e os valores x
(k)
j+1, . . . , x
(k)
n restantes.
Fund. de Ca´lculo Nume´rico para Engenheiros 69
Exemplo 3.7: Considerando o mesmo sistema do exemplo 3.6, o conjunto de
equac¸o\u2dces pode ser escrito, para este caso, conforme\uf8f1\uf8f4\uf8f2\uf8f4\uf8f3
x
(k+1)
1 = 1, 2\u2212 0, 1x(k)2 \u2212 0, 1x(k)3
x
(k+1)
2 = 1, 2\u2212 0, 1x(k+1)1 \u2212 0, 1x(k)3
x
(k+1)
3 = 1, 2\u2212 0, 1x(k+1)1 \u2212 0, 1x(k+1)2
As aproximac¸o\u2dces sucessivas sa\u2dco indicadas na tabela 3.3:
Tabela 3.3: Me´todo de Gauss-Seidel
k x
(k)
1 x
(k)
2 x
(k)
3
0 0 0 0
1 1,2 1,08 0,972
2 0,9948 1,0033 1,0002
3 0,9996 1,0000 1,0000
Observa-se que as iterac¸o\u2dces esta\u2dco convergindo mais rapidamente com a utilizac¸a\u2dco
do me´todo de Gauss-Seidel do que com Jacobi.
3.2.3 Me´todo das sobre/sub-relaxac¸o\u2dces sucessivas - SOR/SUR
Dado um sistema Ax = b, sendo A \u2208 \u211cnxn, os me´todos SOR/SUR sa\u2dco te´cnica de
acelerac¸a\u2dco de converge\u2c6ncia para o me´todo de Gauss-Seidel, Jacobi, etc.
Para cada linha i (i = 1, ..., n) a iterac¸a\u2dco do me´todo SOR e´ dada por:
x
(k+1)
SOR = (1\u2212 w)x(k)SOR + wx(k+1)GS
onde w e´ o para\u2c6metro sobre-relaxac¸a\u2dco e x
(k+1)
GS e´ o valor de x obtido na iterac¸a\u2dco de
Gauss-Seidel em (k + 1).
70 Cap´\u131tulo 3 - Sistemas Lineares e na\u2dco -Lineares
Assim, para cada i, calcula-se
x
(k+1)
i = (1\u2212 w)x(k)i +
w
aii
\uf8eb\uf8edbi \u2212 i\u22121\u2211
j=1
aijx
(k+1)
j \u2212
n\u2211
j=i+1
aijx
(k)
j
\uf8f6\uf8f8
Observe que se:
\u2022 0 < w < 1 \u21d2 Me´todo de Sub-relaxac¸a\u2dco Sucessiva (SUR);
\u2022 w = 1 \u21d2 Me´todo de Gauss-Seidel (GS);
\u2022 1 < w < 2 \u21d2 Me´todo da Sobre-relaxac¸a\u2dco Sucessiva (SOR).
Observe ainda que:
\u2022 a escolha do melhor valor de w na\u2dco e´ o´bvia; 2/3 e´ uma boa estimativa para SUR
e 4/3 para o SOR.
\u2022 o custo computacional do me´todo SOR/SUR e´ proporcional a n2;
\u2022 o me´todo SOR/SUR converge se e somente se 0 < w < 2.
Pode-se colocar o me´todo SOR na notac¸a\u2dco matricial conforme:
x(k + 1) = (1 + w)D\u22121[b\u2212 Lx(k + 1)\u2212 Ux(k)\u2212 wx(k)]
onde
L =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
0 0 0 ... 0
a21 0 0 ... 0
a31 a32 0 ... 0
...
. . .
...
an1 an2 . . . an\u22121 0
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb
, D =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
a11 0 0 ... 0
0 a22 0 ... 0
0 0 a33 ... 0
...
. . .
...
0 0 . . . 0 ann
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb
Fund. de Ca´lculo Nume´rico para Engenheiros 71
e
U =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
0 a12 a13 a14 ... a1n
0 0 a23 a24 ... a2n
0 0 0 a34 ... a3n
...
. . .
. . .
...
0 0 . . . 0 0
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb
Note que o sistema converge se
\u2016[I + (1 + w)D\u22121L]\u22121.[w + (1 + w)D\u22121U ]\u2016 \u2264 1
que corresponde a uma condic¸a\u2dco de diagonal domina\u2c6ncia, a ser discutida posterior-
mente.
Exemplo 3.8: Dado o sistema{
10x \u2212 9 y = 1
\u22129x + 10 y = 1
Resolver por SOR com w = 1.5 ate´ \u2016ei\u2016\u221e5 \u2264 10\u22122, sendo (x0, y0) = (0, 0).
Soluc¸~ao: Discretizando o sistema dado tem-se{
xn+1 = (1\u2212 w)xn + w[(9yn + 1)/10]
yn+1 = (1\u2212w)yn + w[(9xn+1 + 1)/10]
Reescrevendo este sistema, obte´m-se as correc¸o\u2dces geradas por Gauss-Seidel da
seguinte forma {
xn+1 = xn + w[(9yn + 1)/10 \u2212 xn]
yn+1 = yn + w[(9xn+1 + 1)/10 \u2212 yn]
72 Cap´\u131tulo 3 - Sistemas Lineares e na\u2dco -Lineares
Tabela 3.4: Me´todo SOR
i xi yi
0 0 0
1 0,150 0,353
2 0,552 0,719
3 0,845 0,931
4 0,984 1,026
5 1,025 1,028
6 1,025 1,019
7 1,014 1,001
8 1,005 1,003
Sendo w = 1.5, resulta a tabela de dados 3.4.
Note que \u2016e8\u2016\u221e < 1.10\u22124. Graficamente, as iterac¸o\u2dces podem ser representadas
para o me´todo de Gauss-Seidel com relaxac¸a\u2dco segundo Fig. 3.1.
Figura 3.1: Representac¸a\u2dco esquema´tica do me´todo SOR.
5Corresponde a avaliac¸a\u2dco do erro relativo a k-e´sima iterac¸a\u2dco
Fund. de Ca´lculo Nume´rico para Engenheiros 73
3.2.4 Converge\u2c6ncia de me´todos iterativos
A converge\u2c6ncia de um me´todo iterativo nem sempre e´ garantida. Por isso, e´
necessa´rio verificar alguns crite´rios que, quando satisfeitos, garantem a converge\u2c6ncia
do me´todo.
Crite´rio das linhas: Uma matriz An×n apresenta bom condicionamento se
| aii | > | ai1 |+ | ai2 |+ · · ·+ | ain | para i = 1, 2, . . . , n
Isto significa que em cada linha da matriz a magnitude do coeficiente da diagonal
deve ser maior do que a soma dos demais coeficientes da linha.
Exemplo 3.9: A matriz \uf8ee\uf8ef\uf8f0 4 \u22121 14 \u22128 1
\u22122 1 5
\uf8f9\uf8fa\uf8fb
apresenta esta propriedade, pois
Na linha 1: | 4 | > | \u2212 1 |+ | 1 |
Na linha 2: | \u2212 8 | > | 4 |+ | 1 |
Na linha 3: | 5 | > | \u2212 2 |+ | 1 |
Entretanto, a matriz \uf8ee\uf8ef\uf8f0\u22122 1 54 \u22128 1