Apostila Métodos Numéricos Cap. 02

Prévia do material em texto

5 
 
BII – Resolução Numérica de Sistemas Lineares 
 
BII.1 – Definições 
 
Um sistema de equações lineares é um sistema do tipo: 
 
⎪⎪⎩
⎪⎪⎨
⎧
=+++
=+++
=+++
nnnnnn
nn
nn
n
bxaxaxa
bxaxaxa
bxaxaxa
S
...
...
...
2211
22222121
11212111
M , (2.1) 
 
que pode ser expresso em forma de equação: 
 
∑
=
==
n
j
ijij bxaSn
1
, i = 1, 2, ..., n, (2.2) 
 
ou ainda sob a forma matricial: 
 
bxA =⋅ , (2.3) 
 
onde, 
 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
nnnn
n
n
aaa
aaa
aaa
A
...
...
...
21
22221
11211
MMM , ⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
nx
x
x
x M
2
1
 e 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
nb
b
b
b M
2
1
 
 
A matriz aumentada ou matriz completa ou expandida do sistema é definida 
como: 
 
[ ]bA
b
b
b
aaa
aaa
aaa
B
nnnn
n
n
|
|
|
|
|
...
...
...
3
2
1
21
22221
11211
=
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
= MMMM (2.4) 
 
 
Define-se x como vetor solução aproximada de B, onde: 
 
6 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
nx
x
x
x M
2
1
 
 
Classificação dos sistemas lineares quanto ao número de soluções: 
 
7 
BII.2 – Métodos diretos 
 
São métodos que determinam a solução de um sistema linear com um número 
finito de operações aritméticas. 
 
BII.2.1 – Método de Eliminação de Gauss 
 
Este método consiste na transformação de um sistema linear original em um 
sistema linear equivalente com matriz dos coeficientes do tipo triangular superior, que 
tem solução imediata. 
Uma matriz triangular superior do tipo n × n, com elementos ajj ≠ 0 pode ser 
definida como: 
 
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=
=+
=++
=+++
=++++
−−−−−
nnnn
nnnnnnn
nn
nn
nn
n
bxa
bxaxa
bxaxa
bxaxaxa
bxaxaxaxa
S
1,111,1
33333
22323222
11313212111
...
...
...
M (2.5) 
 
onde, 
 
n
n
n a
bx = , 
1,1
,11
1
−−
−−
−
−
=
nn
nnnn
n a
xab
x , ..., 
11
13132121
1
...
a
xaxaxabx nn−−−−= 
 
Portanto, a solução do sistema é dada por: 
 
n
n
n a
bx = e 
kk
n
kj
jkjk
k a
xab
x
∑
+=
−
=
1 (2.6) 
 
Para obtermos o sistema linear equivalente, podemos realizar as seguintes 
operações: 
 
 trocar ou permutar duas equações de lugar; 
 multiplicar um equação por um constante ≠ 0; 
 adicionar um múltiplo de uma equação em outra. 
 
Denomina-se: 
 
Estágio do processo: fase em que se elimina a variável xk das equações k + 1, k + 2,..., n. 
)(k
ija : coeficiente da linha i e da coluna j ao final do k-ésimo estágio. 
)(k
ib : termo independente ou i-ésimo elemento do vetor constante no final do estágio k. 
8 
)(k
iL : i-ésima linha da matriz expandida ao final do estágio k. 
aii: pivô de eliminação. 
mij: multiplicador de eliminação. 
 
Seja a matriz expandida: 
 
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
=
)0(
)0(
2
)0(
1
)0()0(
2
)0(
1
)0(
2
)0(
22
)0(
21
)0(
1
)0(
12
)0(
11
|
|
|
|
...
...
...
nnnnn
n
n
b
b
b
aaa
aaa
aaa
B
MMMM
, onde 
0)0(11
)0(
)0(
≠
=
=
a
bb
aa
ii
ijij
 
 
Estágio 1: eliminação de x1 das equações i = 2, 3, ..., n. 
 
Pivô: 0)0(11 ≠a 
Multiplicador: )0(
11
)0(
1
1 a
am ii = 
Eliminação: 1
)0(
1
)0()1(
iii mLLL −← , i = 2, 3, ..., n. 
 
Ao final do estágio 1, obtém-se: 
 
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
=
)1(
)1(
2
)1(
1
)1()1(
2
)1(
2
)1(
22
)1(
1
)1(
12
)1(
11
|
|
|
|
...0
...0
...
nnnn
n
n
b
b
b
aa
aa
aaa
B
MMMM
, onde 
njbmbb
niamaa
bb
aa
iii
jiijij
jj
,...,1,
,...,2,
)0(
11
)0()1(
)0(
11
)0()1(
)0(
1
)1(
1
)0(
1
)1(
1
=−=
=−=
=
=
 
 
Estágio 2: eliminação de x2 das equações i = 3, 4, ..., n. 
 
Pivô: 0)1(22 ≠a 
Multiplicador: )1(
22
)1(
2
2 a
am ii = 
Eliminação: 2
)1(
2
)1()2(
iii mLLL −← , i = 3, 4, ..., n. 
 
Ao final do estágio 2, obtém-se: 
 
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
)2(
)2(
3
)2(
2
)2(
1
)2()2(
3
)2(
3
)2(
33
)2(
2
)2(
23
)2(
22
)2(
1
)2(
13
)2(
12
)2(
11
|
|
|
|
|
...00
...00
...0
...
nnnn
n
n
n
b
b
b
b
aa
aa
aaa
aaaa
B
MMMMM
, onde 
nibmbb
njniamaa
ibb
niijiaa
iii
jiijij
ii
ijij
,...,3,
,...2,,...,3,
2,1,
,...,1,,2,1,
)1(
22
)1()2(
)1(
22
)1()2(
)1()2(
)1()2(
=−=
==−=
==
+===
 
 
Seguindo o raciocínio análogo, procede-se até o estágio n – 1, e a matriz ao final 
desse estágio será: 
9 
 
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
−
−
−
−
−
−−
−−−
−−−−
)1(
)1(
3
)1(
2
)1(
1
)1(
)1(
3
)1(
33
)1(
2
)1(
23
)1(
22
)1(
1
)1(
13
)1(
12
)1(
11
|
|
|
|
|
...000
...00
...0
...
n
n
n
n
n
n
nn
n
n
n
n
n
nn
n
n
nnn
b
b
b
b
a
aa
aaa
aaaa
B
MMMMM
, 
 
onde o sistema linear )1()1( −− = nn bxA é triangular superior e equivalente ao sistema 
bAx = . 
 
Exemplo: 
Encontrar a solução do sistema abaixo pelo método da eliminação de Gauss. 
 
⎪⎩
⎪⎨
⎧
=−+
=++
=++
3234
22
1423
321
321
321
xxx
xxx
xxx
 
 
10 
Exemplo: 
Encontrar a solução do sistema abaixo pelo método da eliminação de Gauss. 
 
⎪⎩
⎪⎨
⎧
−=+−
=−+
=−+
132
3344
532
321
321
321
xxx
xxx
xxx
 
 
11 
BII.2.1.1 – Estratégia de pivoteamento parcial 
 
O método de Gauss poderá falhar quando um pivô for nulo, pois, neste caso não será 
possível calcular os multiplicadores mij usados na eliminação. A estratégia de 
pivoteamento parcial consiste em: 
 
 no início do estágio k, escolher para pivô o elemento de maior módulo da matriz 
A; 
 trocar linhas de posição se for necessário. 
 
Exemplo: 
 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
−
−−
−
=⇒
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
−−
−
−
=
150420
63010
77530
51123
150420
77530
63010
51123
)1()1( BB 
 
 
BII.2.1.2 – Estratégia de pivoteamento completo 
 
Nesta estratégia, o elemento de maior módulo entre todos os elementos da matriz A é 
escolhido para pivô. No exemplo anterior, esse elemento seria 7)1(34 =a . Dessa forma, 
 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
−−
−
=
152400
61030
73570
52113
)1(B 
 
Exemplo: 
Resolver o sistema abaixo pelo método de eliminação de Gauss. Em seguida, resolver 
aplicando a estratégia de pivoteamento parcial (considerar 3 casas decimais). Comparar 
os dois resultados. 
 
⎩⎨
⎧
=+
=+
622
520002,0
21
21
xx
xx
 
 
12 
 
 
Algoritmo 2.1 – Solução de um sistema triangular superior 
 
 
13 
BII.2.2 – Método de Jordam 
 
É uma extensão do método de eliminação de Gauss onde os coeficientes aij 
acima da diagonal principal da matriz A também são eliminados. 
 A partir de um sistema do tipo. 
 
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
nnnnnn
n
n
n
b
b
b
b
aaaa
aaaa
aaaa
aaaa
B
|
|
|
|
|
...
...
...
...
3
2
1
)2(
321
3333231
2232221
1131211
MMMMM
, 
 
obtém-se um sistema equivalente do tipo: 
 
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
=
)(
)(
3
)(
2
)(
1
)()(
3
)(
33
)(
22
)(
11
|
|
|
|
|
...00
0...00
0...00
0...00
k
n
k
k
k
k
nn
k
n
k
k
k
b
b
b
b
aa
a
a
a
B
MMMMM
 
 
Exemplo: 
Resolver o sistema abaixo pelo método de Jordam. 
⎪⎩
⎪⎨
⎧
−=−−
=−−
=++
1
02
42
321
321
321
xxx
xxx
xxx
 
14 
BII.3 – Métodos Iterativos 
 
BII.3.1 – Introdução 
 
Os métodos iterativos consistem em calcular uma seqüência de soluções x(k), 
partindo-se de um “chute” inicial x(0), que se aproxime do vetor solução x , até que a 
diferença (erro) entre os vetores x(k+1) e x(k) seja menor do que uma dada precisão. 
 Para isso, transforma-se o sistema original Ax = b em um sistema equivalente da 
forma x = F·x + d. A partir de uma aproximação inicial x(0), determina-se a seqüência de 
soluções dada por: 
 
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
=
)0(
)0(
2
)0(
1
)0(
nx
x
x
x → chute inicial 
 
dxFx
dxFx
dxFx
kk +⋅=
+⋅=
+⋅=
− )1()(
)1()2(
)0()1(
M
 → seqüência de aproximações sucessivas 
 
BII.3.2 – Testes de parada 
 
 O processo iterativo é repetido até que o valor de x(k) esteja suficientemente 
próximo de x(k – 1). Mede-se, então, a distância entre x(k) e x(k – 1) dada por: 
 
( ) ( ) ( 1)k k k
i id máx x x ε−= − < , 1 ≤ i ≤ n (2.7) 
 
 
Assim, dada uma precisão ε, o vetor x(k) será escolhido como solução 
aproximada da solução exata x , se d(k) < ε. Computacionalmente, utiliza-se, também, 
como teste de parada um número máximo de iterações. 
 
BII.3.3– Método de Jacobi 
 
Seja o sistema 
 
⎪⎪⎩
⎪⎪⎨
⎧
=+++
=+++
=+++
nnnnnn
nn
nn
n
bxaxaxa
bxaxaxa
bxaxaxa
S
...
...
...
2211
22222121
11212111
M 
15 
 
Supondo aii ≠ 0, explicita-se xi na i-ésima equação, i = 1, 2, ..., n. Assim, 
 
( )
( )
( )
( ) ( ) ( ) ( )
1 12 2 13 3 1( 1)
1
11
( ) ( ) ( ) ( )
2 21 1 23 3 2( 1)
2
22
( ) ( ) ( ) ( )
1 1 2 2 , 1 1( 1)
...
...
...
k k k k
n nk
k k k k
n nk
k k k k
n n n n n nk
n
nn
b a x a x a x
x
a
b a x a x a x
x
a
b a x a x a x
x
a
+
+
− −+
⎧⎪ − + + +⎪⎪ =⎪⎪⎪⎪⎪⎪ − + + +⎪⎪ =⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪ − + + +⎪⎪ =⎪⎪⎪⎪⎩
M
 (2.8) 
 
Reescrevendo-se o sistema na forma x = F·x + d, tem-se: 
 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
nx
x
x
x M
2
1
, 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
−−−
−−−
−−−
=
0///
//0/
///0
321
22222232221
11111131112
L
MLMMM
L
L
nnnnnnnnn
n
n
aaaaaa
aaaaaa
aaaaaa
F , 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
nnn ab
ab
ab
d
/
/
/
222
111
M 
 
Exemplo: 
Resolver o sistema abaixo pelo método de Jacobi, considerando-se ε < 10–2 ou k > 10. 
 
⎩⎨
⎧
=+
=−
32
12
21
21
xx
xx
 
 
16 
 
 
Algoritmo 2.2 – Método de Jacobi 
17 
BII.3.4 – Método de Gauss-Seidel 
 
 Da mesma forma que no método de Jacobi, o sistema linear Ax = b é escrito na 
forma equivalente x = F·x + d. O processo consiste em, sendo x(0) o chute inicial, 
calcular x(1), x(2), ..., x(k) por: 
 
( )
( )
( )
( ) ( ) ( ) ( )
1 12 2 13 3 1( 1)
1
11
( ) ( 1) ( ) ( )
2 21 1 23 3 2( 1)
2
22
( ) ( 1) ( 1) ( )
3 31 1 32 2 3( 1)
3
33
( ) ( 1) ( 1) (
1 1 2 2 , 1 1( 1)
...
...
...
...
k k k k
n nk
k k k k
n nk
k k k k
n nk
k k k k
n n n n n nk
n
b a x a x a x
x
a
b a x a x a x
x
a
b a x a x a x
x
a
b a x a x a x
x
+
+
+
+ +
+
+ +
− −+
− + + +=
− + + +=
− + + +=
− + + +=
M
( ))
nna
⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩
 (2.9) 
 
 Portanto, no processo iterativo de Gauss-Seidel, no momento de se calcular 1+kix , 
usamos todos os valores 11
+kx , 12
+kx , ..., 11
+
−
k
ix que já foram calculados. A vantagem deste 
método é que sua convergência é muito mais rápida. 
 Uma outra maneira de se representar o sistema acima é dada por: 
 
⎥⎦
⎤⎢⎣
⎡
++= ∑∑
+=
−
=
++
n
ij
k
jij
i
j
k
jiji
k
i xFxFdx
1
1
1
11 , i = 1, 2, ..., n e k = 0, 1, 2, ... (2.10) 
 
Exemplo: 
Resolver o sistema abaixo pelo método de Gauss-Seidel, considerando-se ε < 10–2 ou 
k > 10. 
 
⎩⎨
⎧
=+
=−
32
12
21
21
xx
xx
 
18 
 
 
Algoritmo 2.3 – Método de Gauss-Seidel 
 
19 
BII.3.5 – Convergência dos métodos iterativos 
 
Dado o sistema Ax = b é possível obter um sistema equivalente do tipo 
x = F·x + d que é resolvido por meio de x(k + 1) = F·x(k) + d. No entanto, como verificar 
se esse sistema converge? 
 
BII.3.5.1 – Critério das linhas 
 
 É condição suficiente para que a iteração definida em x(k + 1) = F·x(k) + d convirja 
que: 
 
∑
≠
=
>
n
ij
j
ijii aa
1
, i = 1, 2, ..., n (2.11) 
 
BII.3.5.2 – Critério das colunas 
 
 É condição suficiente para que a iteração definida em x(k + 1) = F·x(k) + d convirja 
que: 
 
∑
≠
=
>
n
ji
i
ijjj aa
1
, j = 1, 2, ..., n (2.12) 
 
BII.3.5.3 – Critério de Sassenfeld 
 
 É condição suficiente para que a iteração definida em x(k + 1) = F·x(k) + d convirja 
que os elementos de F, fij, satisfaça a igualdade: 
 
1
1
<≤∑
=
Lf
n
j
ij , i = 1, 2, ..., n (2.13) 
 
 Neste critério, qualquer que seja a aproximação inicial x(0), verificar se o 
resultado da aplicação desse método em cada linha é limitado por algum número L e se 
este número é menor do que 1. 
 
20 
Exemplo: 
Estudar a convergência do sistema abaixo, aplicando-se os três métodos vistos 
anteriormente. 
 
⎪⎪⎩
⎪⎪⎨
⎧
=−−−
=−+−
−=−+−
=−−
01035
036
5592
1024
432
431
421
321
xxx
xxx
xxx
xxx
 
 
 
	I – Erros
	I.1 – Tipos de erros
	I.2 – Exatidão ( precisão
	I.3 – Erros durante a descrição dos problemas
	I.3.1 – Erros na fase de modelagem
	I.3.2 – Erros na fase de resolução
	I.4 – Propagação de erros
	I.5 – Aritmética de ponto flutuante
	II – Resolução Numérica de Sistemas Lineares
	II.1 – Definições
	II.2 – Métodos diretos
	II.2.1 – Método de Eliminação de Gauss
	II.2.1.1 – Estratégia de pivoteamento parcial
	II.2.1.2 – Estratégia de pivoteamento completo
	II.2.2 – Método de Jordam
	II.3 – Métodos Iterativos
	II.3.1 – Introdução
	II.3.2 – Testes de parada
	II.3.3 – Método de Jacobi
	II.3.4 – Método de Gauss-Seidel
	II.3.5 – Convergência dos métodos iterativos
	II.3.5.1 – Critério das linhas
	II.3.5.2 – Critério das colunas
	II.3.5.3 – Critério de Sassenfeld
	III – Cálculo Numérico de Raízes de Equações
	III.1 – Introdução
	III.2 – Isolamento de raízes
	III.3 – Refinamento
	III.3.1 – Critérios de parada
	III.3.2 – Método da bissecção
	III.3.3 – Método da posição falsa
	III.3.4 – Método da posição falsa modificado
	III.3.5 – Método iterativo linear (MIL)
	III.3.6 – Método de Newton-Raphson (N-R)
	III.3.7 – Método da secante
	IV – Interpolação
	IV.1 – Introdução
	IV.2 – Interpolação polinomial
	IV.3 – Formas de obtenção do polinômio interpolador
	IV.3.1 – Resolução do sistema linear
	IV.3.2 – Forma de Lagrange
	IV.3.3 – Forma de Newton
	IV.3.4 – Forma de Newton-Gregory
	IV.3.5 – Erro na interpolação
	V – Integração Numérica
	V.1 – Introdução
	V.2 – Fórmulas de Newton-Cotes
	V.2.1 – Regra dos retângulos
	V.2.2 – Regra dos trapézios
	V.2.2.1 – Fórmula simples
	V.2.2.2 – Erro de trucamento da fórmula simples
	V.2.2.3 – Fórmula composta
	V.2.2.4 – Erro de truncamento da forma composta
	V.2.3 – Primeira regra de Simpson
	V.2.3.1 – Fórmula simples
	V.2.3.2 – Erro de truncamento da fórmula simples
	V.2.3.3 – Fórmula composta
	V.2.3.4 – Erro de trucamento da formula composta
	V.2.4 – Segunda regra de Simpson
	V.2.4.1 – Fórmula simples
	V.2.4.2 – Erro de truncamento da fórmula simples
	V.2.4.3 – Fórmula composta
	V.2.4.4 – Erro de truncamento da fórmula composta
	V.2.5 – Extrapolação de Richardson
	V.2.5.1 – Extrapolação de Richardson para a regra dos trapézios
	V.2.5.2 – Extrapolação de Richardson para as regras de Simpson
	V.3 – Fórmulas de Quadratura Gaussiana
	VI – Resolução Numérica de equações diferenciais ordinárias
	VI.1 – Introdução
	VI.2 – Método de Euler
	VI.3 – Métodos de Runge-Kutta
	VI.3.1 – Métodos de Runge-Kutta de 1ª ordem
	VI.3.2 – Métodos de Runge-Kutta de 2ª ordem
	VI.3.3 – Métodos de Runge-Kutta de 3ª e 4ª ordens
	VI.4 – Outros métodos de resolução numérica de EDO
	VI.4.1 – Método de Adams-Bashforth de passo dois
	VI.4.2 – Método de Adams-Bashforth de passo quatro