Sol Eq 1Variavel 1pp

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 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
0)()( se ; e 
0)()( se ; e 
11
11
>∗==
<∗==
++
++
nnnnnn
nnnnnn
pfafbbpa
e
pfafpbaa
…,2,1 ,
2
=
−
+= n
ab
ap nnnn …,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 −
−
−
+= )(
)()(
)( 1
01
01
1 px
pp
pfpf
pfy −
−
−
+=
)(
)()(
)(0 12
01
01
1 pp
pp
pfpf
pf −
−
−
+= )(
)()(
)(0 12
01
01
1 pp
pp
pfpf
pf −
−
−
+=
)()(
))((
01
011
12
pfpf
pppf
pp
−
−
−=
)()(
))((
01
011
12
pfpf
pppf
pp
−
−
−=
…,2,1 ;
)()(
))((
1
1
1 =−
−
−=
−
−
+ n
pfpf
pppf
pp
nn
nnn
nn …,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
1
1
−
−
+ −
−
−=
nn
nnn
nn
pfpf
pppf
pp
)()(
)()(
1
11
1
nn
nnnn
n
pfpf
ppfppf
p
−
−
=
−
−−
+
)()(
)()(
1
11
1
nn
nnnn
n
pfpf
ppfppf
p
−
−
=
−
−−
+
por
15
O método da secante
� Exemplo
� Determine a raiz de no 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
−
−
−=+
)()(
))((
1
nn
nnn
nn
afbf
abaf
ap
−
−
−=+
0)()( se ; e 
0)()( se ; e 
1111
1111
>∗==
<∗==
++++
++++
nnnnnn
nnnnnn
pfafbbpa
e
pfafpbaa
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 …+
∆
′′+
∆
′+=∆+
!2
)(
)(
!1
)()()(
2
0
0
0
0000
p
pf
p
pfpfppf
0)()()( 00000 ≅∆∗′+=∆+ ppfpfppf 0)()()( 00000 ≅∆∗′+=∆+ ppfpfppf )(/)( 000 pfpfp ′−=∆ )(/)( 000 pfpfp ′−=∆
001 ppp ∆+= 001 ppp ∆+= )(/)( 0001 pfpfpp ′−= )(/)( 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 −
′′
+−′+==
ξ 2)(
2
)(
))(()()(0 nnnn pp
f
pppfpfpf −
′′
+−′+==
ξ
ξ está entre pn e p
2)(
)(2
)(
)(
)(
)( n
nn
n
n pp
pf
f
pf
pf
pp −
′
′′
−=
′
+−
ξ 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 −
′
′′
−=− +
ξ 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
f
pp −
′
′′
−=− +
ξ
2
1
)(2
n
n
n pp
pf
M
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 geradapelo 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 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 −≤− +
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∆
{ }∞=0nnp p
{ }nq p
{ }np pppppp nnn −−− ++ 21 e ,
n
pp
pp
pp
pp
n
n
n
n
−
−
≈
−
−
+
++
1
21
pp
pp
pp
pp
n
n
n
n
−
−
≈
−
−
+
++
1
21
( ) ( )( )pppppp nnn −−≈− ++ 2
2
1
( ) 222212 1 2 pppppppppp nnnnnn ++−≈+− ++++ ( ) 222212 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∆
( ) 222212 1 2 pppppppppp nnnnnn ++−≈+− ++++
( ) 2 1212 2 ++++ −≈−+ nnnnnn ppppppp( ) 2 1212 2 ++++ −≈−+ nnnnnn ppppppp
nnn
nnn
ppp
ppp
p
+−
−
≈
++
++
12
2
12
2 nnn
nnn
ppp
ppp
p
+−
−
≈
++
++
12
2
12
2
ou
( )
nnn
nn
n
ppp
pp
pp
+−
−
−≈
++
+
12
2
1
2
( )
nnn
nn
n
ppp
pp
pp
+−
−
−≈
++
+
12
2
1
2
( )
nnn
nn
nn
ppp
pp
pq
+−
−
−=
++
+
12
2
1
2
( )
nnn
nn
nn
ppp
pp
pq
+−
−
−=
++
+
12
2
1
2
{ }∞=0nnq
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∆
{ }∞=1nnp )/1cos( npn =
{ }∞=1nnp { }
∞
=1nnq
Note que a seqüência converge 
mais rapidamente para que 
{ }∞=1nnq
{ }∞=1nnp1=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 cpxbpxaxP +−+−= )()()( 2
2
2
))(,( e ))(,()),(,( 221100 pfppfppfp
cppbppapf
cppbppapf
cppbppapf
+−+−=
+−+−=
+−+−=
)()()(
)()()(
)()()(
22
2
222
21
2
211
20
2
200
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
−±
−
=−
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
−+
−=−
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
=
− − − − −
=
− − −
− − − − −
=
− − −
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 62054016)( 234 +++−= xxxxxf
210 e , ppp
0 -0.5,,5.0 210 === 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 5.1 ,0.1,5.0 210 === ppp
25.2 ,0.2,5.2 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
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
Aplicação do MATLAB
� Aspectos gerais
� A função ROOTS é usada para calcular todas as raízes, reais e 
complexas, de um polinômio.
� Para um função qualquer, FZERO é usada para calcular uma raiz 
próxima a aproximação inicial especificada, dentro de uma tolerância 
especificada.
� Cálculo das raízes do polinômio: 62054016)(
234 +++−= xxxxxf 62054016)( 234 +++−= xxxxxf
>> coef=[16 -40 5 20 6] 
coef = 
 16 -40 5 20 6 
>> r=roots(coef) 
r = 
 1.9704 
 1.2417 
 -0.3561 + 0.1628i 
 -0.3561 - 0.1628i 
46
>> x=-1:.1:3; 
>> y=polyval(coef,x); 
>> plot(x,y) 
>> grid 
>> title('Grafico de f(x)') 
>> xlabel('eixo x') 
>> ylabel('eixo y') 
Aplicação do MATLAB
� Aspectos gerais
� Representação gráfica de na 
seqüência do cálculo das raízes.
62054016)( 234 +++−= xxxxxf 62054016)( 234 +++−= xxxxxf
47
Aplicação do Maple
� Aspectos gerais
� Determinar as raízes de .
� Raízes reais:
� Raízes reais e complexas:
62054016)( 234 +++−= xxxxxf 62054016)( 234 +++−= xxxxxf
 fsolve(16*x^4-40*x^3+5*x^2+20*x+6,x); 
,1.241677445 1.970446079 
fsolve(16*x^4-40*x^3+5*x^2+20*x+6,x,complex); 
 − -0.3560617617 0.1627583829 I + -0.3560617617 0.1627583829 I 1.241677445, , ,
1.970446079 
48
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ências destes 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.