03_Resolucao_de_Equacoes_Nao_lineares_v4

Prévia do material em texto

1
Computação Científica II
(EEL7031)
Resolução de Equações Não-lineares
(polinômios e equações transcendentais)
2
Objetivo Geral
 Objetivos
 Estudar o problema de determinar, por métodos numéricos, as 
raízes de polinômios e equações transcendentais. 
 Tópicos principais
 Introdução.
 O método da bissecção
 O método da secante.
 O método da posição falsa
 O método de Newton.
 Análise de erros e aceleração da convergência.
 O método de Müller.
 Análise dos métodos e de software.
3
Introdução
 Problema de interesse
 Dado uma função determinar a existência e o valor de: 
 Histórico
 Os primeiros estudos datam do Século IX, realizados por matemáticos 
árabes que difundiram a utilização do sistema decimal e do zero na 
escrita de números.
 Em 1746, D’Alembert enunciou o Teorema Fundamental da Álgebra, 
demonstrado por Gauss em 1799, que estabelece: “toda a equação 
polinomial de grau n possui exatamente n raízes”.
 O matemático Niels Abel, em 1824, provou que as equações de 
quinto grau ou superior não podem ser resolvidas por radicais e 
combinações de coeficientes.
 A partir destes resultados e até os dias atuais, os métodos de cálculo 
das n raízes de um polinômio de grau n são voltados aos métodos 
iterativos.
:f
0)( que tal xfx
4
Introdução
 Características dos métodos iterativos
 Os métodos iterativos são constituídos por 4 partes principais:
 Estimativa inicial: uma ou mais aproximações para a raiz 
desejada.
 Atualização: uma fórmula que atualize a solução aproximada.
 Critério de parada: uma forma de estabelecer quando parar o 
processo iterativo em qualquer caso.
 Estimador de exatidão: está associado ao critério de parada e 
provê uma estimativa do erro cometido.
5
Introdução
 Critérios de parada
 Há 4 critérios básicos de parada de métodos iterativos:
 Tolerância relativa na variável:
 Tolerância absoluta na função:
 Número de DSE:
 Número máximo de iterações permitido: 
 Comentários
 O segundo critério é, sempre que possível, preferido em relação 
ao primeiro por ser mais confiável.
 O terceiro critério fornece uma idéia mais clara da exatidão 
obtida.
1
1 
 
i
ii
x
xx
2)( ixf
kxxDSE ii  ),( 1
maxn
6
O método da bissecção
 Elementos básicos
 Usado para determinar uma solução 
para no intervalo ,
supondo:
 uma função contínua;
 .
 corta o eixo x em pelo menos 
um ponto no intervalo .
0)()(  bfaf
)(xf
0)( xf  ba,
)(xf
 ba,
 Algoritmo geral
 Calcular no ponto médio de : 
 Se escolhe-se um novo intervalo de modo que 
tenha sinais opostos nas extremidades ou
 Repetir os passos anteriores até atingir a precisão desejada.
)(xf  ba,
2/)( bap 
0)( pxf
)(xf
0)()(  pxfaf
0)()(  pxfbf
7
O método da bissecção
 Algoritmo geral
 Um intervalo contendo uma aproximação para a raiz 
de é construído de um intervalo contendo a 
raiz, como segue: 
 Calcule: 
 Então, faça:
],[ 11  nn ba
0)( xf
],[ nn ba
0)()( se ; e 
0)()( se ; e 
11
11




nnnnnn
nnnnnn
pfafbbpa
e
pfafpbaa
,2,1 ,
2


 n
ab
ap nnnn
8
O método da bissecção
 Algoritmo
 
 
 
)(*5.0 5.2 
Fim.p/ vá,, saída :então 
 5.1 
 e e Enquanto 5.
Fim.p/ vá,"inadequado intervalo" 
 saída ,0 Se .4
 e )( ),( Faça .3
1 , , Faça .2
)0)()(|,,f(x),b,(a, dadosEntrar .1
1
max22
11
11
max21
iii
ii
iii
ba
ba
baba
bap
ba
abaSe
niff
a,b
ff
ffbffaff
ibbaa
bfafn










 
 
 
Pare. :Fim 7.
" " saída , Se .8
Fimp/ vá," " saída , Se 7.
iterações em exatidão aatingiu Não" 
 saída , Se .6
1 4.5 
)( , 
)( , 
:senão 
)( , 
)( , 
:então 
0)( Se 5.3 
12
12
max
max
11
11
11
11















ib
ia
ibii
iaii
ibii
iaii
ai
bpf
apf
n
ni
ii
bffbb
affpa
bffpb
affaa
fpf


9
O método da bissecção
 Exemplo
 Determine a raiz de no intervalo 
0104)( 23  xxxf  2,1
10
O método da bissecção
 Análise de convergência
 Para cada passo do método, o comprimento do intervalo conhecido é 
divido por 2. Então, pode-se escrever:
 Assim, pode-se determinar um limite para o número necessário de 
iterações para assegurar uma determinada tolerância TOL, ou seja:
 Seja p a raiz de f(x) e seja o erro na iteração j. Uma vez que
 Logo: 
nn
ab
pp
2


TOL
ab
n


2
n
TOL
ab
2
 




 

TOL
ab
n 2log
jj ppE 
0)()( ,
2
1
1
1 

 

 jj
jj
j pfpf
pp
p
2
1
2
1
1 


j
jj
j
E
EE
E
2
1
lim
1



j
j
j
E
E
O método da bissecção tem 
convergência linear
11
O método da bissecção
 Comentários
 Teoricamente, o método é seguro e converge em um número fixo de 
iterações, tanto menor quanto menor for o intervalo [a,b]. Contudo, 
poderão ocorrer dificuldades para:
 Identificar a existência de raízes em um intervalo [a,b] qualquer, ao 
longo do processo iterativo, se ocorrer um erro de arredondamento, 
mesmo que pequeno, no momento em que se avalia o sinal da função 
nos extremos ou no ponto médio de [a,b].
 encontrar um intervalo inicial para funções que possuam raízes de 
multiplicidade par ou muito próximas, tais como aquelas ilustradas nas 
figuras abaixo.
12
O método da secante
 Elementos básicos
 Definir um intervalo e os pontos 
 Construir a linha reta definida pelos pontos acima - secante de f(x).
 Escolher como solução a interseção da reta com o eixo x
 Repetir o procedimentos sucessivamente para os intervalos 
   )(, e )(, 1100 pfppfp
))(,( 11 pfp
))(,( 00 pfp
],[ 01 pp
],[,],,[ ],,[ 12312 nn pppppp 
13
O método da secante
 Formulação matemática
 A equação da linha secante através 
de é:
 A intersecção com o eixo x em (p2,0) 
satisfaz:
 Generalizando, resulta:
))(,( e ))(,( 1100 pfppfp
)(
)()(
)( 1
01
01
1 px
pp
pfpf
pfy 



)(
)()(
)(0 12
01
01
1 pp
pp
pfpf
pf 



)()(
))((
01
011
12
pfpf
pppf
pp



,2,1 ;
)()(
))((
1
1
1 





 n
pfpf
pppf
pp
nn
nnn
nn
A interseção da secante com o eixo x poderá ocorrer fora do 
intervalo de interesse e, por isso, o método nem sempre converge. 
14
O método da secante
 Critérios de parada
 Tolerância de convergência:
 Limite máximo de iterações: 
TOLpp nn  1
maxnn 
 Advertência
 Embora algebricamente equivalente recomenda-se, para se evitar 
cancelamentos subtrativos, não substituir a equação de iteração
)()(
))((
1
1
1






nn
nnn
nn
pfpf
pppf
pp
)()(
)()(
1
11
1
nn
nnnn
n
pfpf
ppfppf
p






por
15
O método da secante
 Exemplo
 Determine a raiz deno intervalo 
0104)( 23  xxxf  2,1
Note que o resultado final foi obtido com 6 iterações, aproximadamente 
a metade do número de iterações realizadas pelo método da bissecção.
16
O método da posição falsa
 Elementos básicos
 Sob as mesmas condições iniciais do método da bisseção, particionar 
o intervalo [a,b] na interseção da reta que une os pontos definidos a 
seguir, com o eixo x.
 Pontos iniciais: 
 Define-se então a solução p2 e um novo intervalo conforme a variação 
do sinal de f(x).
   )(, e )(, bfbafa
0pa 
1pb 
Método da secante Método da posição falsa
))(,( afa
))(,( bfb
1pb 
17
O método da posição falsa
 Passos principais
 Com a1=a e b1=b, a aproximação p2 é 
dada por:
 Calcule: 
 Seguir o procedimento para p4,...,pn
)()(
))((
11
111
12
afbf
abaf
ap



2212
12
 e :faça
 ,0)()( Se
pbaa
afpf


1222
12
 e :faça
 ,0)()( Se
bbpa
bfpf


)()(
))((
22
222
23
afbf
abaf
ap



01 pa 
11 pb 
))(,( 11 bfb
))(,( 11 afa
18
O método da posição falsa
 Algoritmo geral
 Um intervalo , contendo uma aproximação para 
a raiz de , é encontrada de um intervalo contendo a 
raiz calculando-se:
 Então faça:
)()(
))((
1
nn
nnn
nn
afbf
abaf
ap



0)()( se ; e 
0)()( se ; e 
1111
1111




nnnnnn
nnnnnn
pfafbbpa
e
pfafpbaa
1 para ],,[ 11  nba nn
0)( xf
],[ nn ba
Embora aparentemente superior, o método da posição falsa 
converge mais lentamente que o método da secante.
19
O método da posição falsa
 Exemplo
 Determine a raiz de no intervalo 
0104)( 23  xxxf  2,1
20
O método de Newton
 Elementos básicos
 Sejam f(x),f’(x) e f’’(x) contínuas em [a,b] e 
p o único zero de f(x) em [a,b].
 Escolher uma solução inicial po para p
 Fazer uma expansão em série de Taylor 
para
 Tomando-se 2 termos das série, resulta:
 Obter: 
 Obter aproximações subseqüentes para p
de modo similar.
0)()( 00  ppfxf





!2
)(
)(
!1
)()()(
2
0
0
0
0000
p
pf
p
pfpfppf
0)()()( 00000  ppfpfppf )(/)( 000 pfpfp 
001 ppp  )(/)( 0001 pfpfpp 
21
O método de Newton
 Algoritmo geral
 A aproximação para uma raiz de é calculada da 
aproximação usando-se a equação:
,2,1 ;
)(
)(
1 

 n
pf
pf
pp
n
n
nn
1np 0)( xf
np
22
O método de Newton
 Exemplo
 Determine a raiz de no intervalo 
0104)( 23  xxxf  2,1
)(
)(
1
n
n
nn
pf
pf
pp


23
O método de Newton
 Análise de convergência
 Considere p ser uma solução para e que f’’ existe em um 
intervalo contendo p e a aproximação pn. Expandindo f em série de 
Taylor para pn e calculando para x = p, resulta:
 Conseqüentemente, se , obtém-se:
 Substituindo-se na equação acima, resulta: 
2)(
2
)(
))(()()(0 nnnn pp
f
pppfpfpf 


ξ está entre pn e p
2)(
)(2
)(
)(
)(
)( n
nn
n
n pp
pf
f
pf
pf
pp 






)(
)(
1
n
n
nn
pf
pf
pp


2
1 )(
)(2
)(
)( n
n
n pp
pf
f
pp 


 

0)( xf
0)(  npf
24
O método de Newton
 Análise de convergência (cont.)
 Se existir uma constante positiva M tal que em um 
intervalo em torno de p, e se pn estiver neste intervalo, pode-se 
reescrever
 Como:
 Comentários
 O erro da (n+1)ésima aproximação é limitado por 
aproximadamente o quadrado do erro da (n)ésima aproximação
 O método de Newton converge quadraticamente se e 
se p0 é suficientemente próximo de p.
2
1 )(
)(2
)(
)( n
n
n pp
pf
f
pp 


 

2
1
)(2
n
n
n pp
pf
M
pp 

 
Mxf  )(
1 npp
npp 
0)(  npf
25
O método de Newton
 Situações de dificuldades para o método de Newton
 Os gráficos abaixo ilustram situações em que ocorrem dificuldades 
para a convergência do método de Newton 
Caso 1 Caso 2
Caso 3
26
O Método da Iteração Linear - MIL
 Elementos gerais
 Seja uma função contínua em , intervalo que contém 
uma raiz de . O MIL consiste em:
 transformar em ;
 tomar um valor inicial para ;
gerar uma seqüência de aproximações para pela 
relação , pois a função é tal que se e 
somente se 
 Uma função que satisfaz a condição acima é chamada de 
função de iteração para a equação . 
 A técnica descrita transforma o problema de resolver no 
problema de encontrar um ponto fixo de 
 Exemplo:
)(xf  ba,
0)( xf )(xx 
0xx 
 kx
)(1 kk xx 

)(x 0)( f
 )(
0)( xf
0)( xf
)(x
0)( xf
)(x
06)( 2  xxxf 26)( xxx 
27
O Método da Iteração Linear - MIL
 Análise Ilustrativa da 
convergência
 Considere uma equação 
qualquer: 
 Em geral podem ser 
definidas várias funções de 
iteração:
 Opção 1:
 Opção 2:
0)( xf
)(1 xx 
)(2 xx 
)(2 xx 
)(1 xx 
y
y
   kxk quando 
   kxk quando 
28
O Método da Iteração Linear - MIL
 Análise Ilustrativa da 
convergência (cont.)
 Equação:
 Opção 3:
 Opção 4:
0)( xf
)(3 xx 
)(4 xx 
)(3 xx 
)(4 xx 
  para converge não kx
  para converge não kx
y
y
Note que nem todas as funções de 
iteração geram seqüências 
convergentes para a raiz de f(x)=0
29
O Método da Iteração Linear - MIL
 Análise formal de convergência 
 Seja uma raiz da equação , isolada num intervalo [a,b], 
centrado em .
 Seja uma função de iteração para 
 Se:
 e são contínuas em [a,b]; 
 e;
 .
então a seqüência gerada pelo processo iterativo 
converge para .
 0)( xf

)(x 0)( xf
)(x )(x
 baxMx ,,1)( 
 bax ,0 
 kx )(1 kk xx 

30
O Método da Iteração Linear - MIL
 Exemplo numérico 1:
 Considere a equação ,
 Aplicar o método MIL com e
 Análise das condições de convergência
06)( 2  xxxf 2 e 3 21  
26)( xx  5.10 x

4609.3475)003906.59(6)(
003906.59)0625.8(6)(
0625.875.36)(
75.35.16)(
2
34
2
23
2
12
2
01




xx
xx
xx
xx




26)( xx  xx 2)( 
e
 em contínuas são )( e )( xx 
2
1
2
1
121)(  xxx
Não existe um intervalo [a,b] centrado em ξ=2, tal que
],[,1)( baxx 
31
O Método da Iteração Linear - MIL
 Exemplo numérico 2:
 Considere a equação ,
 Aplicar o método MIL com e 
 Análise das condições de convergência
06)( 2  xxxf 2 e 3 21  
xx  6)( 5.10 x

00048.299809.16)(
99809.100763.26)(
00763.296944.16)(
96944.112132.26)(
12132.25.16)(
45
34
23
12
01




xx
xx
xx
xx
xx





75.51
62
1
1)( 

 x
x
x
Atendidas as 
condições do teorema
32
Análise de erro e Aceleração de Convergência
 Convergência linear
 Um método que produz uma seqüência de aproximações que 
converge para um número , converge linearmente se, para um 
valor elevado de , existe uma constante , tal que:
 np
 p
 n
10  M
nn ppMpp  1
 Convergência quadrática
 Um método que produz uma seqüência de aproximações que 
converge para um número , converge quadraticamente se, para 
um valor elevado de , existe uma constante , tal que:
 np
 p
 n
M0
2
1 nn ppMpp  
33
Análise de erro e Aceleração de Convergência
 Exemplo
 Suponha que converge linearmente para , converge 
quadraticamente para e suponha para ambos os 
casos. Então, tem-se: 
 np  0p
 
0
0
3
0
2
23
0
2
012
001
.)5.0(
.)5.0(.)5.0(5.0
.)5.0().5.0(5.0
).5.0(
pp
pppMp
pppMp
ppMp
n
n 




5.0M
 npˆ
 0p  
 
nn
pp
pppMp
pppMp
ppMp
n
2
0
12
8
0
7
24
0
32
23
4
0
3
22
0
2
12
2
0
2
01
ˆ.)5.0(ˆ
.)5.0(ˆ.)5.0(5.0ˆˆ
ˆ.)5.0(ˆ5.05.0ˆˆ
ˆ).5.0(ˆˆ





34
Análise de erro e Aceleração de Convergência
 Exemplo numérico
 A tabela abaixo ilustra a velocidade relativa de convergência para zero 
destes limites de erro, supondo 
1ˆ00  pp
Observe-se que a convergência quadrática atingiu precisão de 10-38 em sete 
termos, enquanto que a convergência linear necessitaria de 126 termos.
35
Análise de erro e Aceleração de Convergência
 O método de Aitken 
 É uma técnica que pode ser usada para acelerar a convergência de 
uma seqüência linearmente convergente, independente de sua 
origem ou aplicação.
 Suponha uma seqüência convergente com limite . Para 
construir uma seqüência que converge mais rapidamente para 
do que , assume-se que tenham o 
mesmo sinal e que seja suficientemente maior que: 
Então:
2
 
0nn
p
p
 nq
p
 np
pppppp nnn   21 e ,
n
pp
pp
pp
pp
n
n
n
n







1
21
    pppppp nnn   2
2
1
  222
2
1
2
1 2 pppppppppp nnnnnn  
36
Análise de erro e Aceleração de Convergência
 O método de Aitken (cont.)
 Da expressão , tem-se: 
 Resolvendo para p resulta: 
 Define-se, então a seqüência , onde 
também converge para p, e, em geral, mais rapidamente.
2
  222
2
1
2
1 2 pppppppppp nnnnnn  
  2 1212 2   nnnnnn ppppppp
nnn
nnn
ppp
ppp
p





12
2
12
2
ou
 
nnn
nn
n
ppp
pp
pp





12
2
1
2
 
nnn
nn
nn
ppp
pp
pq





12
2
1
2
 
0nn
q
37
Análise de erro e Aceleração de Convergência
 O método de Aitken - Exemplo
 A seqüência onde converge linearmente para 
p = 1. Os primeiros termos de e são dados na tabela 
abaixo: 
2
 
1nn
p )/1cos( npn 
 
1nn
p  
1nn
q
Note que a seqüência converge 
mais rapidamente para que 
 
1nn
q
 
1nn
p1p
38
O Método de Müller
 Aspectos gerais
 Há um número significativo de problemas em que os métodos da 
secante, posição falsa e Newton não apresentam resultados 
satisfatórios.
 Na maioria dos casos, os resultados insatisfatórios ocorrem quando 
a função e sua derivada estão simultaneamente próximas de zero.
 Estes métodos não podem ser usados para o cálculo de raízes 
complexas, a menos que a aproximação inicial seja um número 
complexo com parte imaginária não-nula.
 O método de Müller, proposto em 1956, é uma generalização do 
método da secante, ao substituir a reta que passa por duas 
aproximações prévias, por uma parábola que passa por três 
aproximações prévias.
 Por suas características, o método de Müller também fornece raízes 
complexas de polinômios.
39
O Método de Müller
 Elementos principais
 O método de Müller utiliza o zero de uma 
parábola, formada usando três aproximações 
prévias, para determinar a próxima 
aproximação, conforme ilustrado na figura b.
 Considere o polinômio quadrático abaixo, que 
passa por .
 As constantes a,b e c são determinadas das 
seguintes condições:
cpxbpxaxP  )()()( 2
2
2
))(,( e ))(,()),(,( 221100 pfppfppfp
cppbppapf
cppbppapf
cppbppapf



)()()(
)()()(
)()()(
22
2
222
21
2
211
20
2
200
Secante
Parábola

0p

1p

2p

3p
40
O Método de Müller
 Determinação da intersecção
 A raiz de é 
determinada pela equação abaixo, em vez da 
tradicional “fórmula de Bahskara”, visando 
diminuir os erros de arredondamento. 
 O sinal do radical é definido em conformidade 
com a opção de maior magnitude do 
denominador, visando evitar a subtração de 
números de magnitudes próximas, sendo p3
selecionado como a raiz de P(x) mais próxima 
de p2. .
0)()()( 2
2
2  cpxbpxaxP
acbb
c
pp
4
2
2
23


 
0p

1p

2p

3p
41
O Método de Müller
 Algoritmo 
 Dadas as aproximações iniciais , determine: . 
onde:
 Então, continue o processo iterativo com substituindo
 O método calcula aproximações para raízes complexas, desde que 
seja usado aritmética complexa, quando o radical 
acbbsignb
c
pp
4)(
2
2
23


210 e , ppp
2
2 2
0 2 1 2 1 2 0 2
0 2 1 2 0 1
1 2 0 2 0 2 1 2
0 2 1 2 0 1
( )
( ) [ ( ) ( )] ( ) [ ( ) ( )]
( )( )( )
( )[ ( ) ( )] ( )[ ( ) ( )]
( )( )( )
c f p
p p f p f p p p f p f p
b
p p p p p p
p p f p f p p p f p f p
a
p p p p p p

    

  
    

  
321 e , ppp
210 e , ppp
042  acb
42
O Método de Müller
 Exemplo
 Considere o polinômio . 
 Use o método de Müller e determine raízes deste polinômio para três 
diferentes condições iniciais para , com tolerância de 
precisão de 10-5.
 Caso 1: 
62054016)( 234  xxxxxf
210 e , ppp
0 -0.5,,5.0 210  ppp
*
1p
43
O Método de Müller
 Exemplo (cont.)
 Caso 2:
 Caso 3:
 Portanto: as raízes do polinômio 
são:
5.1 ,0.1,5.0 210  ppp
25.2 ,0.2,5.2 210  ppp
*
2p
*
3p
97044.1
24168.1
162758.0356062.0
*
3
*
2
*
1



p
p
ip
44
O Método de Müller
 Comentários finais
 O método de Müller pode ser utilizado para determinar as raízes de 
polinômios com uma variedade de condições iniciais.
 A técnica geralmente converge para qualquer escolha de condição 
inicial.
 Pacotes computacionais de uso geral que empregam o método de 
Müller exigem somente uma aproximação inicial por raiz ou, 
opcionalmente, podem gerar esta aproximação inicial. O método de Müller é mais eficiente que o método da secante, mas não 
tão eficiente quanto o método de Newton. Contudo, a facilidade de 
implementação e a maior segurança de que a raiz será encontrada 
quando se utiliza o método de Müller podem ser mais relevantes. 
 Qualquer um dos métodos, secante, Newton e Müller, convergem 
rapidamente, uma vez que uma razoável aproximação inicial seja 
especificada. Tal condição poderá ser determinada usando-se os 
métodos da bissecção ou posição falsa.
45
Conclusões
 Resolução da equação f(x) = 0, onde f é uma função contínua.
 Se [a,b] é um intervalo em que f(a) e f(b) tem sinais opostos, então os 
métodos da bissecção e o método da posição falsa convergem. Contudo 
a convergência de ambos os métodos pode ser lenta.
 Convergência rápida pode ser obtida usando-se os métodos da secante 
e de Newton, porém, são necessárias condições iniciais relativamente 
próximas à raiz.
 Os métodos da bissecção e da posição falsa podem ser utilizados como 
métodos de partida para os métodos da secante e de Newton.
 O método de Müller apresenta convergência rápida sem restrições para 
a condição inicial, porém não tão rápida quanto o método de Newton.
 O método de Müller apresenta a vantagem adicional de permitir o 
cálculo de raízes complexas, sendo comumente empregado em pacotes 
computacionais.
 Existem métodos de alta ordem para a determinação de raízes de 
polinômios, tais como: Laguerre, Jenkins-Traub e Brent.