NotasAulaENG1714 2 MarcioCarvalho

Prévia do material em texto

CÁLCULO DE RAIZ DE EQUAÇÃO
 Necessidade de determinar a raiz de uma equação em diversos problemas de engenharia, isto é, determinar x, tal que:
0)( xf
Algumas equações mais simples possuem solução analítica, como 
3 e 2065
10202
2 

xxxx
xx
 Na maioria dos casos (equação não-linear), as raizes da equação não podem ser determinadas analiticamente 
 Deve-se utilizar procedimentos iterativos para determinar a(s) raiz(es)
MÉTODO DE PICARD
)(0)(0)( **
)(
***
*
xgxxgxxf
xf
 
x* é raiz da equação f(x) = 0
PROCEDIMENTO ITERATIVO
)(
)1()(
)1()(
)1()(
)0(
 :Raiz )(
1 repetir , Enquanto
)(1
 :inicial Chute
i
ii
ii
ii
x
xgx
ii
xx
xgx
i
x







x
)(xg
x
*x RAIZ)0(x )( )0(
)1(
xg
x )2(x
)( )0(xg )( )1(xg
0 xex
xx exgex   )(
EXEMPLO 1: RESOLVER

69220.0)(
36788.0)(
1
36788.0)1()2(
1)0()1(
)0(





exgx
exgx
x
n xn g(xn)0 1 0.367881 0.36788 0.692202 0.69220 0.500473 0.50047 0.606244 0.60624 0.545405 0.54540 0.579616 0.57961 0.560127 0.56012 0.571148 0.57114 0.564889 0.56488 0.5684310 0.56843 0.5664111 0.56641 0.56756. . .20 0.56714 0.56714
01x
12)(12  xxgxx
EXEMPLO 2: RESOLVER

6.018.02)( 8.019.02)(
9.0
)1()2(
)0()1(
)0(



xgx
xgx
x
n x n g ( x n )0 0 . 9 0 . 81 0 . 8 0 . 62 0 . 6 0 . 23 0 . 2 - 0 . 6
Processo iterativo diverge
PORQUE ???
x)(xg
x
*x RAIZ
)0(x)( )0(
)1(
xg
x)2(x
)( )0(xg )( )1(xg
DIVERGE
x
)(xg
x
*x RAIZ
)0(x )( )0(
)1(
xg
x)2(x
)( )0(xg
)( )1(xg
CONVERVE OSCILANDO
OSCILANDO CONVERGE0)(1 MENTEMONOTONICA CONVERGE1)(0
DIVERGE1)(



xg
xg
xg
MÉTODO DE BISSEÇÃO
 SE f(x) É UMA FUNÇÃO CONTÍNUA E f(a).f(b) < 0A RAIZ DE f(x) PERTENCE AO INTERVALO (a,b)
MÉTODO DE BISSEÇÃO CRIA UMA SEQUENCIA DE INTERVALOSCADE VEZ MENOR QUE CONTENHA A RAIZ 
)(xf
x
*x
0a 0b
),( 00 ba
),( 11 ba
1m 2m
 
 
i
iii
ii
ii
ii
ii
ii
ii
i
i
m
bam
ii
mb
aa
mfaf
bb
ma
bfmf
mf
bam
i
bfafba
 :Raiz 21
1end
 then0)()( ifend
 then0)()( if do ,)( While
211
0)()( que tal e Escolher 
11
1
1
1
1
00
0000
















0sin2
2


 xxEXEMPLO 3: RESOLVER
i ai-1 f(ai-1) bi-1 f(bi-1) mi f(mi)1 1.5 <0 2 >0 1.75 <02 1.75 2 1.875 <03 1.875 2 1.9375 >04 1.875 1.9375 1.90625 <05 1.90625 1.9375 1.9219
 CONVERGÊNCIA EXTREMAMENTE LENTA
 CONVERGÊNCIA MELHORA USANDO VALORES DE f(x)NO CÁLCULO DE mi
)()( )()( 11 1111   

ii
iiii
i bfaf
bfaafb
m
MÉTODO DE NEWTON-RAPHSON (DE NEWTON))(xf
x*x
)0(x)1(x)2(x
)( )(
)()(tan
1
1
i
i
ii
i
ii
i
xf
xfxx
xf
xx
xf





PROCEDIMENTO ITERATIVO
)1(
)()1(
)(
)(
)(
)0(
 :Raiz 1
)( )(
do ,)( While0
 :inicial Chute

 




i
ii
i
i
i
x
ii
xxx
xf
xf
x
xf
i
x

0sin2
2


 xxEXEMPLO 4: RESOLVER
i xi f(xi) f’(bi) x0 1.5 0.434995 -0.67926 0.640391 2.14039 -0.30319 -1.60948 -0.188382 1.95201 -0.02437 -1.34805 -0.018083 1.93393 -0.00023 -1.32217 -0.000184 1.93375 0.000005 -1.32191
 CONVERGÊNCIA RÁPIDA
 O TAMANHO DO PASSO DIMINUI A CADA ITERAÇÃODE UM FATOR DE 10
0 xexEXEMPLO 5: RESOLVER
i xi f(xi) f’(bi) x0 0.01234
PROPRIEDADE DE CONVERGÊNCIA
Vamos supor que  é uma raiz simples de f(x): 0)( e 0)(   ff
Obter uma estimativa de erro para a aproximação xn do Método de Newton
  nn x
Expandindo f(x) em série de Taylor em x=xn com um passo - xn 
 
)( )(21lim)( )(21
)(
)()(21)( )(
)(
)()(21)()( )(
),();()(21)()()(0
0)()(
22121
2
1
2
2
1









 f
f
xf
f
xf
fx
xf
xfx
xf
fx
x
xf
xf
xfxxfxxf
fxxf
n
n
n
xn
nn
n
n
n
x
n
n
n
n
n
n
n
n
nnnnn
nn
n
n



















)( )(21 ff 
 Quando perto da solução, o erro cai quadraticamente:
854423 101010   
PROBLEMAS COM O MÉTODO DE NEWTON
 O chute inicial deve estar suficientemente próximo da solução
)(xf
x*x
)0(x )1(x
)(xf
x
)0(x)1(x
 O processo iterativo passa por umponto de máximo ou mínimo local
*x
 O processo iterativo pode entrar em um ciclo que não converge
)(xf
x*x
)0(x
)1(x
 Os problemas com o Método de Newton podem ser resolvidos comum chute inicial perto da solução
 Combinar um método com convergência global boa (mas lenta) como método de Newton (convergência global ruim, mas extremamenterápido quando perto da solução)
MÉTODO DA SECANTE
 O cálculo da derivada f ’(x) pode ser muito complicado ou caro computacionalmente
Aproximar a derivada por:
1
1)()()(




ii
ii
xx
xfxfxf
PROCEDIMENTO ITERATIVO
)1(
)()1(
)1()(
)1()()(
)(
)1()0(
 :Raiz 1
)()()(
do ,)( While1
 e :inicial Chute










i
ii
ii
ii
i
i
x
ii
xxx
xfxf
xx
xfx
xf
i
xx

INTERPRETAÇÃO GEOMÉTRICA
)(xf
x*x
)0(x)1(x)2(x
 Necessita de 2 chutes iniciais
 Convergência não é quadrática
0sin2
2


 xxEXEMPLO 6: RESOLVER
i xi f(xi) x0 1.0 -0.591471 2.0 0.090702345
Escreva uma rotina no SciLab para cálculo de raiz de funções usando os métodos de Bisseção e Newton.O programa principal deve fazer as seguintes tarefas:
Utilize o programa desenvolvido para determinar a raiz das equações abaixo.
(a) (b)1)( 2  xxf xexxf 21)( 
Exercício
Script Principal
Método da Bisseção
Método de Newton
�
M
aior parte do tem
po de um
a sim
ulação por elem
entos finitos,
diferenças finitas ou outro m
étodo num
érico é gasto na 
resolução do sistem
a de equações obtido com
 a discretização
�
N
ecessidade de m
étodos robustos e rápidos
SO
LU
Ç
Ã
O
 D
E SISTEM
A D
E EQ
U
A
Ç
Õ
ES
�
A
 solução de um
 sistem
a de equações é necessária na grande m
aioria
dos problem
as de engenharia
Problem
as de interpolação e ajuste de curvas
Solução de equações diferenciais -sim
ulação de problem
as de engenharia
SISTEMA DE n EQUAÇÕES E n INCÓNITAS
�
�
�
�
�
����
����
����
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
�
�
�
�
2211
22222121
11212111
� Se os coeficientes aij são constantes, o sistema é dito linear
� O sistema acima pode ser representado na forma de matriz:
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
nnnnannnn
nn
nn
nn
b
b
b
b
x
x
x
x
aaaa
aaaa
aaaa
aaaa
��
�
����
�
�
�
3
2
1
3
2
1
21
3133231
2122221
1111211
bAx �
MÉTODOS DE SOLUÇÃO
�MÉTODOS DIRETOS
A solução exata (a menos de erros de truncamento do computador)
é determinada após um número finito de operações
Requer mais memória de armazenamento
Mais robusto
Mais rápido 
�MÉTODOS ITERATIVOS
Fornece uma sequência de soluções aproximadas que convergem
quando o número de passos tende a infinito
Menor necessidade de memória de armazenamento
Problemas de convergência
MÉTODOS DIRETOS
SISTEMAS TRIANGULARES
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
�
�
�
�
nnnn
nn
nn
nn
b
bb
b
x
x
x
x
u
uu
uuu
uuuu
��
�
����
�
�
�
3
2
1
3
2
1
313
21222
1111211
000
00
0
Se niuii ,,2,1,0 ��� as incógnitas podem ser facilmente calculadas
ii
n
ik
kkii
i
nn
nnnn
nnnnnnnn
nn
n
n
u
xub
x
u
xub
xbxuxu
u
bx
�
��
��
��
������
�
�
�
����
�
1
,
1,1
,11
11,111,1
 :i linha
; :1-n linha
; :n linha
�
RETROSUBSTITUIÇÃO
Se a matriz for triangular inferior:
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
�
� nnnnannnn b
b
b
b
x
x
x
x
llll
ll
ll
l
��
�
����
�
�
�
3
2
1
3
2
1
21
3231
2221
11
00
00
000
A solução é calculada da seguinte forma:
ii
i
ik
kkii
i l
xlb
x
l
xlb
xbxlxl
l
bx
�
�
�
�
�
�
����
�
1
,
22
11,22
2222,211,2
11
1
1
 :i linha
; :2 linha
; :1 linha
�
SUBSTITUIÇÃO A FRENTE
NÚMERO DE OPERAÇÕES: �
�
������
n
i
nnnnin
1
2
2
1
)1(
2
1
)1(
ELIMINAÇÃO GAUSSIANA
�
�
�
�
�
����
����
����
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
�
�
�
�
2211
22222121
11212111
� Eliminar as variáveis de uma maneira sistemática até obter um 
sistema triangular, de fácil solução
Eliminar x1 das (n-1) úlimas equações
Se
�
�
�
�
�
��
�
�
�
�
��
�
�
��
�
�
����
�
�
��
�
�
�����
�
�
��
�
�
��
��
�
�
��
�
�
����
�
�
��
�
�
�����
�
�
��
�
�
����
�
�
��
�
�
�
����
1
11
1
1
11
1
212
11
1
21
1
11
21
21
11
21
2212
11
21
221
0
11
11
21
21
11212111
0 b
a
abxa
a
aaxa
a
aax
b
a
abxa
a
aaxa
a
aaxa
a
aa
bxaxaxa
n
nnn
n
nn
n
n
nnn
nn
�
�
�
�� ��� ��
�
011 �a
Eliminar x2 das (n-2) últimas equações
Se
Após o primeiro passo, o sistema fica sendo:
�
�
�
��
�
�
���
���
����
)2()2(
2
)2(
2
)2(
2
)2(
22
)2(
22
11212111
nnnnn
nn
nn
bxaxa
bxaxa
bxaxaxa
�
�
�
� Onde
nibmbb
niamaa
ni
a
am
iii
jiijij
i
i
,,3,2;
,,3,2;
,,3,2;
11
)2(
11
)2(
11
1
1
�
�
�
���
���
��
0)2(22 �a
�
�
�
�
��
�
�
�
���
���
����
�����
)3()3(
3
)3(
3
)3(
3
)3(
33
)3(
33
)2(
2
)2(
23
)2(
232
)2(
22
11313212111
nnnnn
nn
nn
nn
bxaxa
bxaxa
bxaxaxa
bxaxaxaxa
�
�
�
�
�
nibmbb
niamaa
ni
a
am
iii
jiijij
i
i
,,4,3;
,,4,3;
,,4,3;
)2(
22
)2()3(
)2(
22
)2()3(
)2(
22
)2(
2
2
�
�
�
���
���
��
E assim por diante, até obter um sistema da forma
�
�
�
�
��
�
�
�
�
���
����
�����
)()(
)3(
3
)3(
33
)3(
33
)2(
2
)2(
23
)2(
232
)2(
22
)1(
1
)1(
13
)1(
132
)1(
121
)1(
11
n
nn
n
nn
nn
nn
nn
bxa
bxaxa
bxaxaxa
bxaxaxaxa
�
�
�
�
O SISTEMA TRIANGULAR PODE SER FACILMENTE RESOLVIDO
ATRAVÉS DE UMA RETROSUBSTITUIÇÃO
� Os elementos são denominados de Pivots
� O lado direito do sistema de equações é modificado da mesma forma
que os coeficientes das equações
� Melhor tratar o sistema na forma matricial, com o lado direito do sistema
sendo a coluna n+1 da matriz, conforme mostrado a seguir
)1(
1,1
)2(
22
)1(
11 ,,,
�
��
n
nnaaa �
�
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
nnnannnn
nn
nn
nn
b
b
b
b
aaaa
aaaa
aaaa
aaaa
�
�
����
�
�
�
3
2
1
21
3133231
2122221
1111211niba ki
k
ni ,,2,1,
)()(
1, ����
end
end
end
1,1For 
,1For 
1,1For 
)()()1(
)(
)(
k
kjik
k
ij
k
ij
k
kk
k
ik
ik
amaa
nkj
a
am
nki
nk
��
���
�
��
��
�
end
end
*
,1For 
0
1,1,For 
)(
)(
1,
)(
i
ii
i
ni
i
k
i
ik
a
suma
x
xasumsum
nik
sum
ni
�
�
��
��
�
��
�
ALGORÍTMO
ELIMINAÇÃO RETROSUBSTITUIÇÃO
� O maior custo computacional ocorre no processo de eliminação
� Supor que o tempo de cada operação seja de 1 microsegundo
O tempo em segundos de cada parte do algoritmo é mostrado abaixo
st 610��
NÚMERO DE OPERAÇÕES:
�
�
�
����
1
1
3
3
1)1)((
n
k
nknkn �
�
����
n
i
nnni
1
2
2
1
2
1 )1()1(
ELIMINAÇÃO RETROSUBSTITUIÇÃO
n Eliminação Retrosubstituição
10 0.0050 s 0.0008 s
100 5 s 0.075 s
1000 5000 s 7.5 s
PIVOTAMENTO
�
�
	
�
�
�
�
��
�
�
�
���
���
���
1221
2211
1111
122
22
1
321
321
321
xxx
xxx
xxx
RESOLVER O SISTEMA POR ELMINAÇÃO GAUSSIANA
Sistema não singular, e a solução é: 1321 ���� xxx
Após o primeiro passo na eliminação, a matriz fica sendo:
0
0110
1100
1111
)2(
22 ��
�
�
	
�
�
�
a
A eliminação não pode continuar pelo procedimento normal.
Uma solução seria trocar a posição das linhas 2 e 3, o que já fornece a matriz triangular
�
�
	
�
�
�
�
��
�
�
�
���
���
���
1221
220001.11
1111
122
220001.1
1
321
321
321
xxx
xxx
xxx
OUTRO EXEMPLO: RESOLVER O SISTEMA POR ELMINAÇÃO GAUSSIANA
Sistema não singular, e a solução é: 0001.1 e 1 321 ���� xxx
O sistema triangular obtido após a eliminação sem troca de linhas é:
�
�
	
�
�
�
10000999900
110001.00
1111
O processo de retrosubstituição usando uma precisão de 3 casas decimais fornece:
000.1,0 ,0 321 ��� xxx
Se as linhas 2 e 3 fossem trocadas durante o processo de eliminação, a solução 
também usando uma precisão de 3 casas decimais seria
000.1,000.1 ,000.1 321 ���� xxx Resultado correto usando uma 
precisão de 3 casas decimais
Resultado incorreto
� Para evitar falha catastrófica (divisão por zero) ou resultados errados
é necessário fazer uma escolha criteriosa dos PIVOTS usados na eliminação
PIVOTAMENTO PARCIAL
PIVOTAMENTO COMPLETO
PIVOTAMENTO PARCIAL
No passo k do processo de eliminação
k
r
k
rk
nikaa
r
k
ik
k
rk
 e linhasTrocar 
,max
que talinteiromenor o como Escolher 
)()(
�
���
�
PIVOTAMENTO COMPLETO
No passo k do processo de eliminação
k
r
k
skrk
njikaa
sr
k
ij
k
rs
 e colunas e , e linhasTrocar 
,,max
que talinteiros menores os como e Escolher 
)()(
�
���
�
s
� A Eliminação Gaussiana deve ser feita sempre com PIVOTAMENTO
para garantir estabilidade do método
� Na grande maioria dos casos, PIVOTAMENTO PARCIAL é suficiente
e deve ser usada no lugar de PIVOTAMENTO COMPLETO
� PIVOTAMENTO COMPLETO não é muito usado devido ao grande
tempo computacional gasto no processo de busca do pivot.
� PIVOTAMENTO não é necessário em dois casos particulares
MATRIZ DIAGONAL DOMINANTE
MATRIZ SIMÉTRICA E POSITIVA-DEFINIDA
�
�
�
��
n
ij
j
ijii niaa
1
.,,2,1, �
0xAxxAA ����� ,0 e)( Tjiij
T aa
DECOMPOSIÇÃO LU
� Muitas vezes o mesmo sistema é resolvido com 
diferentes termos independente (lado direito do sistema)
� Pode-se evitar o processo repetido de eliminação gaussiana através
de uma decomposição da matriz A
� Todo matriz não singular pode ser decomposta como o produto de uma matriz
triangular inferior L e uma matriz triangular superior U
� A decomposição não é única.
�;; 2211 bAxbAx ��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
��
� nn
n
n
n
nnnn u
uu
uuu
uuuu
lll
ll
l
000
00
0
;
1
01
001
0001
; 333
22322
1131211
1,21
3231
21
�
�
�
�
�
�
�
�
�
�
ULLUA
� A matriz L corresponde aos coeficientes mik da eliminação gaussiana e a matriz
U corresponde a matriz triangular superior obtida na eliminação gaussiana
� Uma vez feita a decomposição, a solução do sistema fica reduzida a solução
de dois sistemas triangulares:
	
yUxbLy
bUxL
y
��
��
 depois e Resolver 
Sistema triangular inferior
Sistema triangular superior
MÉTODO DE CHOLESKI
� Matriz simétrica, positiva-definida
� Escolher L e U de forma que TLU �
nki
m
mma
m
mam
mumu
kk
k
p
kpipik
ik
k
p
kpkkkk
kppkkkkk
,,1,
 e 
1
1
2/1
1
1
2
���
�
�
��
�
�
��
�
�
��
��
�
�
�
�
�
�
MATRIZES DE BANDA
� Matrizes onde os elementos diferentes de zero estão localizados em
uma banda centrada na diagonal principal da matriz
� As matrizes obtidas em resolução de um problema de valor de contorno
são geralmente de banda, daí a importância do estudo deste tipo de matriz
0
0
p
q qjipijaij ����� ou se 0
1 :Matriz da Banda ��� qpw
� A estrutura de banda não é perdida, se não forem realizadas nenhuma
troca de linhas ou coluna (pivotamento parcial ou completo)
� As matrizes L e U serão matrizes de banda.
jipiju
qjiijm
ij
ij
����
����
ou se 0
ou se 0
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
aaa
aaaa
aaaa
aaam
aam
uu
aaa
aaaa
aaaa
aaaa
aaa
aa
'''
''
 passo 1
EXEMPLO
� Sem pivotamento
A estrutura de banda não é perdida
� Com pivotamento (troca linha 1 e 3)
A estrutura de banda é perdida
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
aaa
aaaa
aaaa
aaam
aaam
uuuu
aaa
aaaa
aaaa
aa
aaa
aaaa
'''
'''
 passo 1
� Os algoritmos devem ser escritos levando em conta a estrutura da matriz
� Grande economia de tempo computacional
MATRIZ TRIDIAGONAL
� Matriz de banda com p = q = 1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
���
nn
nnn
ab
cab
cab
ca
�
�
�
�
00
0
0
00
111
222
11
� Decomposição LU da matriz triagonal:
��� ���� ��
�
�
�
�
��� ���� ��
�
�
�
�
�
�
�
�
UL
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
������
n
nn
n
n
nn
nnn c
c
c
ab
cab
cab
ca
�
�
�
�
 
 
 
000
00
00
00
100
010
001
0001
00
0
0
00
11
22
11
1
2
111
222
11
nkcaba kkkk
k
k
k ,,3,2;,, 1
1
11 ������ �
�
 �
�
 �
� A solução do sistema é feita através de uma resolução de sistemas triangulares
1,2,,1,1;,
,,3,2;,
1
111
�
�
���
�
��
����
�
�
nnixcgxgx
nigfgfg
i
iii
i
n
n
n
iiii
��
 
ANÁLISE DE ERRO DA DECOMPOSIÇÃO LU
� Considere o sistema bAx �
� Asolução do sistema sempre apresenta algum erro devido a 
erros de truncamento que ocorrem durante o processo
� Denominar solução obtida como
� Definir vetor resíduo como
x
xAbR ��
xx0R ��� Solução calculada é a solução exata
� Espera-se que quando o vetor resíduo seja próximo a zero, 
a solução calculada seja próxima da solução exata
� Isto nem sempre é verdade !
Considere o exemplo �
�
��
�
���
�
��
�
�� 1440.0
8642.0 e 1441.02161.0
8648.02969.1 bA
Solução exata: �
�
��
�
�
�� 0000.2
0000.2x
Solução obtida:
�
�
�
�
�
����
�
��
�
�
���
��
�
���
�
��
�
����
��
�
��
�
�
��
�
�
8
8
10
10
4870.0
9911.0
1441.02161.0
8648.02969.1
1440.0
8642.0
4870.0
9911.0
xAbR
x
Apesar do vetor resíduo ser muito pequeno, a solução obtida
não é muito distante da solução exata
Este problema pode ser explicado analisando-se o processo
de eliminação gaussiana
4870.0
101440000154.01440.08642.0
2969.1
2161.0
1440.0
101440999923.01441.08648.0
2969.1
2161.0
1441.0
)2(
22
)2(
2
2
8
1
11
21
2
)2(
2
8
12
11
21
22
)2(
22
����
���!����
���!����
�
�
a
bx
b
a
abb
a
a
aaa
Processo de eliminação gaussiana
� Uma pequena variação no elemento 0.1441 causa uma 
grande variação no elemento e consequentemente em )2(22a 2x
� Para uma análise da precisão da eliminação gaussianda,
é necessário usar o conceito de norma de vetores e matrizes
NORMA DE VETOR E MATRIZ
� Escalar não negativo que em algum sentido mede a 
magnitude de um vetor ou matriz
� Norma p de um vetor
" # $%����� pxxx ppnppp 1,
/1
21 �x
Norma Euclideana: p=2
Norma do máximo: p=infinito
" # 2/1222212 nxxx ���� �x
ini
x
��$
�
1
maxx
� Propriedades de uma Norma 
yxyx
xx
0xx0xx
���
�
����
escalar ,
 se ,0 e se ,0
���
� Norma de uma Matriz
x
Ax
A
0x�
� max
Para Norma do máximo, pode-se mostrar que
Relação entre a norma de um vetor e de uma matriz:
�
�
��$
�
n
j
ijni
a
1
1
maxA
xAAx �
ANÁLISE DE PERTURBAÇÃO
� Analisar o efeito de pequenas perturbações 
na matriz A e vetor b na solução x
" #
A
A
AA
xx
x
xxAAx
xxAAxxxAxAbxxAA
bAxbAxbbxxA
bAxbAx
A
11
11
1
&
&
&
&&&
&&&&&&&&
&&&&&&
�����
)(
1 )(0)()(
)()(
K
��
�
��
�
�
�
���
�����������
�������
���
b
b
A
x
x
xAbAxb
&&
)( Como K�����
Se o condicionamento da matriz for alto, pequenas perturbações
na matriz A e no vetor b provacam grandes perturbações na solução
A Matriz é dita mal-condicionada e a solução do problema torna-se imprecisa
Condicionamento da matriz 
� Para determinar o condionamento de uma matriz é necessário calcular
a norma da matriz inversa, que normalmente não é conhecida
� No exemplo anterior:
dacondiciona-mal Matriz 103.3)(
1671.2)8648.02969.1(
10513.110)2161.02969.1(
2969.12161.0
8648.01441.010
8
881
81
�!��
���
!�!���
�
�
��
�
�
�
�!�
�
�
A
A
A
A
K
Escreva uma rotina MatLab para solução de um sistema linear sem pivotamento e uma outra com 
pivotamento parcial. Escreva um programa principal que realize as seguintes operações:
1. Defina a matrix A e o vetor b do sistema linear Ax = b, onde
2. Chame a função para solução do sistema sem pivotamento
3. Chame a função para solução do sistema com pivotamento
Explique o que ocorreu.
�
�
�
	
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
��
�
�
139
120
119
;
212.1411.6
71.1203.3
141.1203.3
bA
Exercício 1
Modifique a rotina desenvolvida de forma a resolver o sistema linear Ax = b, onde
Observe que a solução exata do sistema é 
Exercício 2
ܣ௜௝ ൌ
ଵ
௜ା௝ାଵ ܾ௜ ൌ෍
௝ୀଵ
௡
ܣ௜௝
ݔ௜ ൌ ͳ
MÉTODOS ITERATIVOS
Fornece uma sequência de soluções aproximadas que convergem
quando o número de passos tende a infinito
Usado para matrizes esparsas e grandes 
Menor necessidade de memória de armazenamento
Eliminação Gaussiana “enche” a matriz
Problemas de convergência
xx
xxxx
�
����
$�
)(
)()2()1()0(
lim k
k
k�
Chute inicial
No Método de Jacobi, a sequência de aproximações é obtida por:
ni
a
bxa
x
ii
i
n
ij
j
k
jij
k
i ,,2,1 para,
1
)(
)1( ��
��
�
�
�
�
�
MÉTODO DE JACOBI
Osistema de equações pode ser escrito como
ni
a
bxa
xbxaxa
nibxa
ii
i
n
ij
j
jij
i
n
ij
j
ijijiii
i
n
j
jij
,,2,1 para,
,,2,1 para,
1
1
1
�
�
�
��
����
��
�
�
�
�
�
�
�
�
MÉTODO DE GAUSS-SEIDEL
No método de Jacobi, os novos valores de x só são usados no próximo passo
No método de Gauss-Seidel, os novos valores de x são usados 
a medida que eles são obtidos
ni
a
bxaxa
xbxaxaxa
nibxa
ii
i
n
ij
jij
i
j
jij
ii
n
ij
jijiii
i
j
jij
i
n
j
jij
,,2,1 para,
,,2,1 para,
1
1
1
1
1
1
1
�
�
�
���
�����
��
��
��
�
��
�
�
��
�
�
�
Para j<1, os novos valores de 
xj já foram calculados
No Método de Gauss-Seidel, a sequência de aproximações é obtida por:
ni
a
bxaxa
x
ii
i
n
ij
k
jij
i
j
k
jij
k
i ,,2,1 para,
1
)(
1
1
)1(
)1( ��
���
�
��
��
�
�
�
�
EXEMPLO: Resolver Ax = b
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
��
��
��
�
1
0
2
1
;
4110
1401
1041
0114
bA
�
�
�
�
�
�
�
�
�
�
�
0
0
0
0
 :inicial Chute )0(x
���
�!�!��!��
�
��������
)2(
2
)2(
1
)1(
4
)1(
3
)1(
2
)1(
1
;375.0
4
125.0)0.0(0.0)1(5.0)1(
25.0
4
1
;0.0
4
0
;5.0
4
2
;25.0
4
1
xx
xxxx
MÉTODO DE JACOBI
k X1
(k) X2
(k) X3
(k) X4
(k)
0 0.0 0.0 0.0 0.0
1 0.25 0.5 0.0 0.25
2 0.375 0.625 0.125 0.375
3 0.4375 0.6875 0.1875 0.4375
8 0.49805 0.74793 0.24793 0.49805
MÉTODO DE GAUSS-SEIDEL
40625.0
4
10625.0)1(5625.0)1(
;0625.0
4
025.0)1(
;5625.0
4
225.0)1(
;25.0
4
1
)1(
4
)1(
3
)1(
2
)1(
1
�
�!��!��
��
�!��
�
�
�!��
���
xx
xx
k X1
(k) X2
(k) X3
(k) X4
(k)
0 0.0 0.0 0.0 0.0
1 0.25 0.5625 0.0625 0.40625
2 0.40625 0.70312 0.20312 0.47656
3 0.47656 0.73828 0.23828 0.49854
5 0.49854 0.74927 0.24927 0.49963
De um modo geral, os dois métodos podem ser escritos como
Os diferentes métodos possuem diferentes formas para matriz B e o vetor c.
cxBx ��� )()1( kk
Uma matriz A pode ser decomposta na soma de três matrizes:
Diagonal + Triangular Superior + Triangular Inferior
)( UILDA ���
� O Método de Jacobi pode ser escrito como:
" # bDxULx 1)()1(
1
)(
)1( ,,2,1 para, ���
�
� ������
��
�
�
kk
ii
i
n
ij
j
k
jij
k
i nia
bxa
x �
� O Método de Gauss-Seidel pode ser escrito como:
bDUxLxx 1)()1()1(
1
)(
1
1
)1(
)1( ,,2,1 para,
���
��
�
�
�
�
����
��
���
�
��
kkk
ii
i
n
ij
k
jij
i
j
k
jij
k
i nia
bxaxa
x �
" # ULIB 1����GS
" #ULB ���J
ANÁLISE DE CONVERGÊNCIA
cxBx ��� )()1( kk
Se x é solução do sistema Ax = b : cxBx ��
O erro de cada aproximação x(k) é obtido pela subtração das equações 
)()()( )0(1)1(2)()1( xxBxxBxxBxx �������� ��� kkkk �
Vamos supor que B tenha n autovetores linearmente independentes. Esses
n vetores formam uma base do espaço vetorial. Qualquer vetor pode
ser escrito como uma combinação linear dos autovetores.
n
n
uuu ,,, :sAutovetore
,,, :sAutovalore
21
21
�
� '''
n
k
nn
kkk
nnn
nn
nn
uuuxx
uuuxx
BuBuBuxxBxx
uuuxx
1
1
1
1
'�'�'�
'�'�'�
���
���
�����
������
��������
�����
�
�
�
�
�
22211
)(
22211
)1(
221
)0()1(
221
)0(
)(
O processo iterativo converge somente se somente se 1B %)((
� Raio Espectral de B: 1)(max)(
1
%�
��
BB ini '(
Os autovalores de B não são conhecidos e esta condição não é facilmente
aplicada. Uma condição suficiente que pode ser aplicada é que
para o processo iterativo convergir: 1%B
A taxa de convergência é dada por " #)(log10 B(��R
MÉTODO DE JACOBI
" #ULB ���J 0, ���� ii
ii
ij
ij bjia
a
b �
�
�
��
�
n
ij
j ii
ij
niJ a
a
1
1
maxB
Se B for diagonal-dominante Converge Processo1 �%JB
MÉTODO DE GAUSS-SEIDEL
" # ULIB 1����GS xByx
y
B
x GS
n
ij
j
GS �� �
�
� $
$
�
,max
1
0
dominante diagonalfor se converge Processo
1
max
, onde,
1
1
11
1
1
11
AB
xyy
y
�
�
�
�����
�����
��$
�
���
$$$
��
�
��
$
��
���
i
i
niGS
i
j ii
ij
i
n
ij ii
ij
ikkk
n
ij
jkj
i
j
jkj
n
j
jkjkk
s
r
a
a
s
a
a
rrsy
xbybxbyy
MÉTODO SOR (SUCCESSIVE OVERRELAXATION)
� Modificação do Método de Gauss-Seidel para melhorar a taxa de convergência
ii
i
n
ij
k
jij
i
j
k
jij
k
i
k
i
k
i
k
i
ii
k
iii
ii
i
k
iii
n
ij
k
jij
i
j
k
jij
ii
i
n
ij
k
jij
i
j
k
jij
k
i
a
bxaxa
rrxx
a
xa
a
bxaxaxa
a
bxaxa
x
���
���
�
����
�
���
�
��
����
�
�
�
�
�
��
�
�
�
��
�
�
�
�
)(
1
1
)1(
)()()()1(
)(
)(
1
)(
1
1
)1(
1
)(
1
1
)1(
)1(
 onde,
)()()1( SOR ki
k
i
k
i rxx )���
� )*++Parâmetro de Relaxação
, -
20
)1()( 1
%%
���� �
)
)))) UILIB
Resolva o sistema linear Ax = b utilizando os métodos de Jacobi e Gauss-Seidel
Observe que a solução exata do sistema é 
Exercício 3
ܣ௜௝ ൌ
ଵ
௜ା௝ାଵ ܾ௜ ൌ෍
௝ୀଵ
௡
ܣ௜௝
ݔ௜ ൌ ͳ
Solução de Sistema de Equações Não-Linear
Método de Picard:
1. Chute inicial;
2. Calcular coeficientes da matriz usando o valor atual das incógnitas;
3. Resolver o sistema de equações e determinar o novo valor das
incógnitas;
• Comparar solução atual com anterior;
• Se não covergiu, voltar para 2.
, -)0()0(3)0(2)0(1)0( ,,,, Nuuuuc ��
" #)(kcAA �
" #" # fcAc kk 1)()1( �� �
Convergência Ruim
)(xAA
bAx
�
�
Método de Newton:
Generalização do Método de Newton para 1 equação não-linear
" # " # " # " #
" # " # " #
" #
" #xf
xfx
xfxxfxxf
xfxxfxxfxxf
.
��
.����
�..�.���
/
//
///
0
2 �
PROCEDIMENTO ITERATIVO
)1(
)()1(
)(
)(
)(
)0(
 :Raiz
1
)(
)(
do ,)( While
0
 :inicial Chute
�
�
��
/��
.
��/
�
�
i
ii
i
i
i
x
ii
xxx
xf
xf
x
xf
i
x
0
�
�
�
�
��
�
�
�
�
�
�
�
0),,,,(
0),,,,(
0),,,,(
0),,,,(
321
3213
3212
3211
NN
N
N
N
xxxxf
xxxxf
xxxxf
xxxxf
�
�
�
�
�
Sistema a ser resolvido:
Expansão por série de Taylor até termos de primeira ordem de cada equação:
N
N
NNN
NN
NNN
N
N
N
NN
N
N
N
NN
x
x
fx
x
fx
x
fxxxf
xxxxxxf
x
x
fx
x
fx
x
fxxxf
xxxxxxf
x
x
fx
x
fx
x
fxxxf
xxxxxxf
///
///
///
///
///
///
1
1
��
1
1
�
1
1
�
�����
1
1
��
1
1
�
1
1
�
�����
1
1
��
1
1
�
1
1
�
�����
��
�
�
��
�
��
�
2
2
1
1
21
2211
2
2
2
2
1
1
2
212
22112
1
2
2
1
1
1
1
211
22111
),,,(
0),,,(
),,,(
0),,,(
),,,(
0),,,(
N
N
NNN
NN
N
N
N
N
N
N
x
x
fx
x
fx
x
fxxxf
x
x
fx
x
fx
x
fxxxf
x
x
fx
x
fx
x
fxxxf
///
///
///
1
1
��
1
1
�
1
1
��
1
1
��
1
1
�
1
1
��
1
1
��
1
1
�
1
1
��
��
�
��
��
2
2
1
1
21
2
2
2
2
1
1
2
212
1
2
2
1
1
1
1
211
),,,(
),,,(
),,,(
	
fJx
f
f
f
x
xx
x
f
x
f
x
f
x
f
x
f
x
f
x
f
x
f
x
f
f
N
x
N
J
N
NNN
N
N
1
2
1
2
1
21
2
2
2
1
2
1
2
1
1
1
��
�
�
�
�
	
�
�
�
�
�
��
�
�
�
�
	
�
�
�
�
�
�
�
�
�
�
�
�
�
	
�
�
�
�
�
�
�
�
�
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
/
/
/
/
/
�
���
�
���� ����� ��
�
�
�
�Sistema em
Forma matricial
Matrix Jacobiana
j
i
ij x
fJ
1
1
�
PROCEDIMENTO ITERATIVO
" #
)1(
)()1(
1
)(
)0(
 :Raiz
1
do , While
0
 :inicial Chute
�
�
�
��
��
��
�
�
i
ii
i
c
ii
xcc
fJx
cf
i
c
/
/
0
Solução de um sistema linear
Convergência Quadrática
Exemplo: Resolver o sistema abaixo pelo 
(a) método de Picard e
(b) método de Newton
��
�
�
�
��
��
54
32
2
2
yxx
yxy
	raiz17
	sistema17p