Calculo Numerico
35 pág.

Calculo Numerico


DisciplinaCálculo Numérico12.102 materiais248.303 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