MNC-Métodos_Iterativos
11 pág.

MNC-Métodos_Iterativos


DisciplinaCálculo Numérico Computacional164 materiais1.320 seguidores
Pré-visualização3 páginas
48 
_________________________________________________________________________________________________________________________ 
 
_________________________________________________________________________________________________________________________ 
Métodos Numéricos Computacionais \u2013 2012 
Profa. Adriana Cherri Profa. Andréa Vianna Prof. Antonio Balbo Profa Edméa Baptista 
1.2 Métodos iterativos para solução de sistemas lineares 
 
Métodos iterativos são aqueles que se baseiam na construção de sequências de aproximações. 
A cada passo, os valores calculados anteriormente são utilizados para reforçar a aproximação de 
modo que o resultado obtido geralmente é aproximado. 
 
 
Pré \u2013 requisitos para os métodos iterativos 
 
Normas de vetores 
 
Chama-se norma de um vetor x, 
x
, qualquer função definida num espaço vetorial E, com 
valores em \u211d, satisfazendo as seguintes condições: 
 
N1) 
x
\uf0b3
 0 e 
x
= 0 se e somente se x = 0. 
 
N2) 
x\uf06c
= \uf0e7\uf06c \uf0e7 
x
 para todo escalar\uf06c. 
 
N3) 
yx \uf02b
 
\uf0a3
 
yx \uf02b
 (desigualdade triangular). 
 
Como exemplos de normas no \u211dn temos: 
 
a) 
E
x
 = 
\uf0e5
\uf03d
n
i
ix
1
2
, b) 
\uf0a5
x
 = 
ni\uf0a3\uf0a31
max
\uf0fa xi\uf0fa , c) 
1
x
 = 
\uf0e5
\uf03d
n
i
x
1
i || 
 
 
Exemplo: 
 
x \uf03d
\uf02d
\uf02d
\uf0e6
\uf0e8
\uf0e7
\uf0e7
\uf0e7
\uf0e7
\uf0e7
\uf0e7
\uf0f6
\uf0f8
\uf0f7
\uf0f7
\uf0f7
\uf0f7
\uf0f7
\uf0f7
1
10
3
4
20
. Obter 
E
x
, 
\uf0a5
x
 e 
1
x
. 
 
x E \uf03d
 
x \uf0a5
= 
x 1
= 
 
Definição: Dada uma sequência de vetores x
(k) \uf0ce E, dizemos que a sequência {x(k)} converge para 
x\uf0ce E 
0)( \uf0ae\uf02dxx k
, quando k \uf0ae \uf0a5. 
 
 49 
_________________________________________________________________________________________________________________________ 
 
_________________________________________________________________________________________________________________________ 
Métodos Numéricos Computacionais \u2013 2012 
Profa. Adriana Cherri Profa. Andréa Vianna Prof. Antonio Balbo Profa Edméa Baptista 
 
Norma de matrizes 
 
O conjunto das matrizes (n × n), com as operações de soma de matrizes e produto de um 
escalar por uma matriz forma um espaço vetorial E de dimensão n
2
. 
Podemos então falar em norma de uma matriz A 
\uf0ce
 E. 
 
Algumas normas de matrizes: 
a)
\uf0e5
\uf03d
\uf0a3\uf0a3\uf0a5
\uf03d
n
j
ij
ni
aA
1
1
max
 (norma linha) 
b) 
\uf0e5
\uf03d
\uf0a3\uf0a3
\uf03d
n
i
ij
nj
aA
1
11
max
 (norma coluna) 
c) 
A aE ij
i j
n
\uf03d
\uf03d
\uf0e5 2
1,
 (norma euclidiana) 
 
Exemplo de cálculo de normas: 
 
Seja: 
 A=
3 2 1
6 3 4
1 2 1
\uf02d
\uf02d
\uf0e6
\uf0e8
\uf0e7
\uf0e7
\uf0e7
\uf0f6
\uf0f8
\uf0f7
\uf0f7
\uf0f7
 
 
A
\uf0a5
\uf03d
 
 
1
A \uf03d
 
 
 
E
A \uf03d
= 
 
 
Definição: Normas consistentes 
 
Dada uma norma no \u211dn e uma norma de matrizes dizemos que elas são consistentes se, para 
qualquer x, 
xAAx \uf0a3
 
 
 
 50 
_________________________________________________________________________________________________________________________ 
 
_________________________________________________________________________________________________________________________ 
Métodos Numéricos Computacionais \u2013 2012 
Profa. Adriana Cherri Profa. Andréa Vianna Prof. Antonio Balbo Profa Edméa Baptista 
Métodos iterativos 
 
Um método iterativo para calcular a solução de um sistema Ax = b (det(A) \u2260 0) é denominado 
iterativo quando fornece uma sequência de soluções aproximadas, sendo que cada solução 
aproximada é obtida pela anterior. 
 De modo geral, a construção do método iterativo considera a transformação do sistema 
original Ax = b para a forma equivalente x = Bx +g e posteriormente, a partir dessa nova forma e de 
uma solução aproximada inicial x
(0)
, determinamos uma sequência de soluções aproximadas 
considerando o processo iterativo: 
 
x
(k+1)
 = Bx
(k)
 + g, k = 0, 1, 2, ... 
 
em que B é a matriz iterativa (n × n) e g é o vetor (n × 1). 
 
Método de Jacobi-Richardson 
 
Considere o sistema de equações lineares 
 
11 1 12 2 1n 1
21 1 22 2 2n 2
n1 1 n2 2 nn n
n
n
n
a x a x a x b
a x a x a x b
a x a x a x b
\uf02b \uf02b \uf02b \uf03d\uf0ec
\uf0ef \uf02b \uf02b \uf02b \uf03d\uf0ef
\uf0ed
\uf0ef
\uf0ef \uf02b \uf02b \uf02b \uf03d\uf0ee
\uf04c
\uf04c
\uf04d \uf04d \uf04f \uf04d \uf04d
\uf04c
 
 
em que a matriz A (det(A)\u22600) do sistema linear pode ser escrita como a soma de três matrizes: A = 
L+D+R. 
 
Escolhemos L, D e R de modo que L só tenha elementos abaixo da diagonal D só tenha 
elementos na diagonal R só tenha elementos acima da diagonal. 
 
lij = 
\uf0ee
\uf0ed
\uf0ec
\uf0a3
\uf03e
ji
jiaij
,0
, dij = 
\uf0ee
\uf0ed
\uf0ec
\uf0b9
\uf03d
ji
jiaij
,0
, rij = 
\uf0ee
\uf0ed
\uf0ec
\uf0b3
\uf03c
ji
jiaij
,0
, 
 
Exemplo (3x3) 
 
 
\ud835\udc4e11 \ud835\udc4e12 \ud835\udc4e13
\ud835\udc4e21 \ud835\udc4e22 \ud835\udc4e23
\ud835\udc4e31 \ud835\udc4e32 \ud835\udc4e33
 
 
\ud835\udc34
= 
0 0 0
\ud835\udc4e21 0 0
\ud835\udc4e31 \ud835\udc4e32 0
 
 
\ud835\udc3f
+ 
\ud835\udc4e11 0 0
0 \ud835\udc4e22 0
0 0 \ud835\udc4e33
 
 
\ud835\udc37
+ 
0 \ud835\udc4e12 \ud835\udc4e13
0 0 \ud835\udc4e23
0 0 0
 
 
\ud835\udc45
 
 
Supondo det(D) \u2260 0 (aii \u2260 0, i=1,...n) e dividindo cada linha pelo elemento da diagonal, 
temos: 
 
 
 51 
_________________________________________________________________________________________________________________________ 
 
_________________________________________________________________________________________________________________________ 
Métodos Numéricos Computacionais \u2013 2012 
Profa. Adriana Cherri Profa. Andréa Vianna Prof. Antonio Balbo Profa Edméa Baptista 
 
 
1
\ud835\udc4e12
\ud835\udc4e11 
\ud835\udc4e13
\ud835\udc4e11 
\ud835\udc4e21
\ud835\udc4e22 1
\ud835\udc4e23
\ud835\udc4e22 
\ud835\udc4e31
\ud835\udc4e33 
\ud835\udc4e32
\ud835\udc4e33 1 
 
 
\ud835\udc34\u2217
= 
0 0 0
\ud835\udc4e21
\u2217 0 0
\ud835\udc4e31
\u2217 \ud835\udc4e32
\u2217 0
 
 
\ud835\udc3f\u2217
+ 
1 0 0
0 1 0
0 0 1
 
 
\ud835\udc3c
+ 
0 \ud835\udc4e12
\u2217 \ud835\udc4e13
\u2217
0 0 \ud835\udc4e23
\u2217
0 0 0
 
 
\ud835\udc45\u2217
 
 
A construção da matriz A* foi exemplificada para o caso 3 × 3, porém, essa construção é 
válida para qualquer dimensão. Obviamente, os elementos bi do vetor b também são divididos pelo 
elemento aii. 
 
No caso geral temos: 
 
\uf0ef
\uf0ee
\uf0ef
\uf0ed
\uf0ec
\uf0a3
\uf03e\uf03d
\uf03d
\uf02a
ji
ji
a
a
a
l
ii
ij
ij
ij
,0
,* 
\uf0ef
\uf0ee
\uf0ef
\uf0ed
\uf0ec
\uf0b3
\uf03c\uf03d
\uf03d
\uf02a
ji
ji
a
a
a
r
ii
ij
ij
ij
,0
,* 
ii
i
i
a
b
b \uf03d\uf02a
 
 
e o sistema linear é reescrito como: 
 
(L
*
 + I + R
*
)x = b
*
 
x = \ud835\udc4f\u2217 
\ud835\udc54
\u2212 (\ud835\udc3f\u2217 + \ud835\udc45\u2217) 
\ud835\udc35
\ud835\udc65 
 
O método iterativo de Jacobi-Richardson fica: 
 
\ud835\udc65(\ud835\udc58+1) = \ud835\udc4f\u2217 \u2212 (\ud835\udc3f\u2217 + \ud835\udc45\u2217)\ud835\udc65(\ud835\udc58) 
 
Desta forma, dado o sistema linear, o Método de Jacobi consiste na determinação de uma 
sequência de aproximantes de índice k: 
... 3, 2, 1, k , ..., , , )()(2
)(
1 \uf03d
k
n
kk xxx
 a partir de valores iniciais 
... 3, 2, 1, k , ..., , , )0()0(2
)0(
1 \uf03dnxxx 
e através do processo definido por: 
 
\uf0ef
\uf0ef
\uf0ee
\uf0ef
\uf0ef
\uf0ed
\uf0ec
\uf02d\uf02d\uf02d\uf03d
\uf02d\uf02d\uf02d\uf03d
\uf02d\uf02d\uf02d\uf03d
\uf02d
\uf02b
\uf02b
\uf02b
nn
k
n
k
n
k
n
k
n
kk
k
n
kk
axxbx
axxbx
axxbx
/).a.a(
/).a.a(
/).a....a(
)(
11-nn,
)(
1n1
)1(
22
)(
1n
)(
1212
)1(
2
11
)(
1n
)(
2121
)1(
1
\uf04c
\uf04d\uf04f\uf04d\uf04d\uf04d
\uf04c
 
 
Critério de convergência do método de Jacobi: 
 
\uf0a7 
1max
1
\uf03c\uf0e5
\uf0b9
\uf03d
ij
j ii
ij
i a
a (Critério das Linhas) 
\uf0a7 
1max
1
\uf03c\uf0e5
\uf0b9
\uf03d
ji
i jj
ij
j a
a (Critério das Colunas) 
 52 
_________________________________________________________________________________________________________________________ 
 
_________________________________________________________________________________________________________________________ 
Métodos Numéricos Computacionais \u2013 2012 
Profa. Adriana Cherri Profa. Andréa Vianna Prof. Antonio Balbo Profa Edméa Baptista 
Critério de parada: 
 
 O método iterativo de Jacobi-Richardson para quando: 
 
| \ud835\udc65 \ud835\udc58+1 \u2212 \ud835\udc65 \ud835\udc58 |\u221e
| \ud835\udc65 \ud835\udc58+1 |\u221e
< \ud835\udf00 
 
sendo 
\uf065
 um valor pré-estabelecido para a precisão. 
 
OBS: 
 
\uf0b7 Se a matriz for estritamente diagonal dominante (isto é, em