Raízes de equações não lineares
4251
0011 0010
1 – Introdução1.1 – Localização das raízes1.2 – Refinamento
2 – Método da bissecção2.1 – Interpretação geométrica2.2 – Algoritmo2.3 – Estimativa do número de iterações 2.4 – Estudo da convergência
3 – Método da corda falsa3.1 – Interpretação geométrica
4251
0011 0010
3.1 – Interpretação geométrica3.2 – Algoritmo3.4 – Majorante para o erro absoluto de uma estimativa3.3 – Estudo da convergência
4 – Método de Newton–Raphson (MNR)4.1 – Abordagem analítica4.2 – Interpretação geométrica4.3 – Algoritmo4.4 – Estudo da convergência
5 – Método da secante
1. Introdução
4251
0011 0010
Pretendemos estudar alguns métodos iterativos que nos permitem obter raízes reais (aproximadas) de uma equação não linear
onde é uma função real de variável real.
Exemplos de equações não-lineares:
( ) ,0=xf
f
,07321
24 =++ xx
4251
0011 0010
( ) .04cos
,0
,032
2
14
=+
=−
=+
−
−
xe
xe
xx
x
x
Definição. Se é uma função real de variável real e
, então dizemos que é um zero da função
ou que é uma raíz da equação
Graficamente, os zeros reais de são as abcissas dos pontos de
f
( ) 0=rf r f
( ) .0=xf
f
r
4251
0011 0010
Graficamente, os zeros reais de são as abcissas dos pontos de intersecção do gráfico de com o eixo dos x.
f
f
Não existem fórmulas resolventes para a generalidade das equações, pelo que é necessário recorrer a outros métodos, chamados métodos iterativos.
Um método iterativo é uma sequência de instruções que são executadas passo a passo, algumas das quais são repetidas em ciclos; cada ciclo recebe o nome de iteração.Estas iterações utilizam valores obtidos em iterações anteriores
4251
0011 0010
Estas iterações utilizam valores obtidos em iterações anteriorespara encontrar uma nova aproximação para a raíz.
Um processo iterativo para calcular as raízes de uma equação pode ser dividido em duas fases:
1º Localização das raízes
Consiste em obter um intervalo que contém uma única raiz
2º Refinamento
Escolhida uma aproximação inicial no intervalo melhorá-
.r
( ) ,0=xf
[ ]ba,
[ ]ba,
4251
0011 0010
Escolhida uma aproximação inicial no intervalo melhorá-la sucessivamente por um processo iterativo (usando a aproximação anterior) até obter uma aproximação para a raíz dentro de uma precisão ε prefixada.
[ ]ba,
1.1 Localização das raízes
Nesta fase é feita uma análise gráfica e teórica da função.
Análise Gráfica
Esta análise pode ser feita através de um dos seguintes processos:
(i) Esboçar o gráfico da função f e localizar as abcissas dos pontos de intersecção do gráfico com o eixo dos x.
4251
0011 0010
Exemplo: 39)( 3 +−= xxxf
-4 -3 -2 -1 0 1 2 3 4-30
-20
-10
0
10
20
30
40
1r 2r 3r
]3,2[
]1,0[
]3,4[
3
2
1
∈
∈
−−∈
r
r
r
(ii) A partir da equação f (x) = 0, obter a equação equivalente g(x) = h(x),
esboçar os gráficos de g(x) e h(x) no mesmo eixo Cartesianoe localizar as abcissas dos pontos de intersecção dos dois gráficos.
).()(0)( rhrgrf =⇔=
Exemplo
0)( =−= − xexf x
Resolução6
7
8
g
4251
0011 0010
Resolução
Logo
xxh
exg
ex
x
x
=
=
=−
−
)(
)(
]1,0[∈r
-2 -1 0 1 2 3 4-2
-1
0
1
2
3
4
5
h
g
r
Análise Teórica
Teorema (Corolário do teorema de Bolzano). Seja f uma função contínua no intervalo [a, b]. Se f (a) f (b) <0, então existe pelo menos um tal que f (r) = 0.
Graficamente
r r ra
y
( )bar ,∈
4251
0011 0010
1r 2r
y
x
1r 2r 3ra b x
ba
Teorema de Rolle. Se f é contínua em [a, b], diferenciável em (a,b)
e f(a) = f(b) = 0, então existe tal que f’(c)=0.
Portanto, sob as hipóteses do teorema anterior, se f’(x) existir e não mudar de sinal em [a, b], então existe uma única raíz nesse intervalo.
Graficamente
y y
),( bac ∈
4251
0011 0010
xa b xa b
],[,0)(' baxxf ∈∀> ],[,0)(' baxxf ∈∀<
Podemos aplicar este teorema atribuindo valores a x e analisando o sinal de f (x).
Exemplo ( ) 393 +−= xxxf
x -10 -5 -3 -1 0 1 2 3 4
f(x) - - + + + - - + +
4251
0011 0010
- Analisando a mudança de sinal, podemos concluir que existe pelo menos uma raíz dentro dos intervalos indicados.
- A derivada não muda de sinal em cada um dos intervalos, portanto cada raíz é única no intervalo.
f(x) - - + + + - - + +
93)(' 2 −= xxf
Observação
Se f (a) f (b) > 0 então podem existir ou não raízes no intervalo [a,b].
Graficamente
x
y
a b
4251
0011 0010
y
x
y
x
x
a b1r 2rb1r
a b
a
1.2 Refinamento
Esta fase implica a resolução de vários problemas:
• Escolher uma aproximação inicial para a raiz
• Construir uma fórmula de recorrência que permite obter sucessivamente novas aproximações a partir da anterior.Obtemos assim uma sucessão de aproximações da solução .
kx
,...,, 210 xxx
0x
r
.r
4251
0011 0010
solução . A cada aproximação corresponde o erro absoluto
e o erro relativo
• Estudar a convergência da sucessão.Obviamente estamos interessados em que o método iterativoseja convergente; ou seja, deve verificar-se que
ou
rxe kk −=
.r
rxk −
r
rxkk
=∞→
lim .0lim =∞→ k
ke
• Estudar a velocidade de convergência.Definição. Se para um dado método iterativo existirem constantes e
tais que
dizemos que é a ordem de convergência do método e a constante de erro assimptótico do método relativamente ao zero da função.
A expressão nesta definição costuma por vezes escrever-se na forma assimptótica
quando
0>c
,lim1
ce
ep
k
k
k=
−∞→
cp
p
kk cee 1−≈ .∞→k
1≥p
r
4251
0011 0010
Se , a convergência diz-se linear.
Se , a convergência diz-se supralinear.
Se , a convergência diz-se quadrática
Quanto maior for a ordem de convergência, mais rápida è, em geral, a velocidade de convergência do processo. A constante de erro assimptótico, normalmente, só é considerada quando se comparam processos iterativos com a mesma ordem de convergência. Aqui, quanto menor for a constante de erro assimptótico mais rápida é a convergência do processo.
1=p
21 << p
2=p
yε<− || k rx
ε<− || rx k
ε<|)(| kxf
É impraticável realizar um número infinito de iterações; é necessário parar num determinado termo Dizemos que o valor de xk é raíz aproximada com precisão se:(i)(ii)Nem sempre é possível ter as duas condições satisfeitas simultaneamente:
ε>− || k rx
.kx
•
ε
y
4251
0011 0010
r kx
y
xr
kx x
ε>|)(| k
k
xfε
ε
<
>−
|)(|
||
k
k
xf
rx y
Como não conhecemos o valor da raíz r para aplicar o teste usamos frequentemente a estimativa
do erro absoluto para o critério de paragem.
Critérios de paragem alternativos:
ε<− −1kk xx
,ε<− rxkε<− −1kk xx
•
4251
0011 0010Impondo um número máximo de iterações
ε<− −
k
kk
x
xx 1
( ) ε<kxf
•
•
•
2. Método da bissecção
4251
0011 0010
Condições para aplicação:
A função deve ser contínua no intervalo [a, b], onde contém uma única raíz.
O objectivo deste método é reduzir a amplitude do intervalo inicial que contém a raiz até que seu comprimento seja
4251
0011 0010
inicial que contém a raiz até que seu comprimento seja menor que a precisão desejada, usando para isso sucessivas divisões a meio do intervalo [a, b].
y
x
2.1 – Interpretação Geométrica
ra0 b0x0a1 b1x1a2 b2x2a3 b3
4251
0011 0010
Iteração 1:
x0 = (a0 + b0)
2f (x0) > 0
⇒a1 = a0
b1 = x0
r ∈ [a1 , b1]
Iteração 2:
x1 = (a1 + b1)
2f (x1) < 0
⇒a2 = x1
b2 = b1
r ∈ [a2 , b2]
Iteração 3:
x2 = (a2 + b2)
2f (x2) < 0
⇒a3 = x2
b3 = b2
r ∈ [a3 , b3]
2.2 Algoritmo do método da bissecção
Seja f contínua em [a, b] , com uma única raíz neste intervalo.
1. Dados iniciais:
- intervalo inicial [a, b]- precisão
2. Se , então escolha para r qualquer FIM ]. ,[ bax∈
3. k = 0
ε
ε<−ba
4251
0011 0010
3. k = 0
4.2
baxk
+=
5. Se , faça Vá para o passo 7 0)()( >kxfaf .kxa =
6. kxb =
7. Se , escolha para r qualquer FIM].,[ bax∈
8. k = k +1. Volte ao passo 4
ε<−ba
2.3 Estimativa do número de iterações
0a 0b
1a 1b
200
110
ababrx
−=−≤−
Dada uma precisão e um intervalo [a, b], vamos determinar quantas
iterações, no mínimo, terão que ser efectuadas pelo método da bissecção
para que
ε
.ε<− rxk
0x
1x
4251
0011 0010
2110 abrx =−≤−
2a2b
2
0011221 22
abababrx
−=
−=−≤−
3a 3b
30022
332 22
abababrx
−=
−=−≤−
100
11 22 +++
−=
−=−≤−
k
kkkkk
abababrx
M
1+ka 1+kb
M
2x
Vamos determinar o menor inteiro k tal que :ε<− rxk
εε 00100 2
abab k −>⇒<
− ++
100
2 +
−≤−
kk
abrx
Então
Sabemos que
4251
0011 0010
.,12log
log)log( 00 Ζkab
k ∈−−−
>⇒ε
εε
12
2k>⇒<
+
( )
−>+⇒
ε00log2log1
abk
2.4 Convergência do método da bissecção
A convergência do método da bissecção é quase linear:
2
11lim ≈−
−+
∞→ rx
rx
k
k
k
4251
0011 0010
3. Método da corda falsa
4251
0011 0010
Condições para aplicação:
A função f deve ser contínua no intervalo , onde contém uma única raíz r.
No método da corda falsa, a função f é substituída pela recta que passa pelos pontos e .
É muito semelhante ao método da bissecção, só que em vez de determinar o ponto
( )( )afa, ( )( )bfb,l
[ ]ba,
4251
0011 0010
É muito semelhante ao método da bissecção, só que em vez de determinar o ponto médio do intervalo é determinado um ponto tal que
que é a abcissa do ponto de intersecção da recta com o eixo dos x .
O intervalo é então substituído pelo intervalo limitado por c e pelo extremo ou , em que a função tem sinal contrário a O processo repete-se agora para este novo intervalo (que contém a raiz) e assim sucessivamente até atingir a precisão desejada.
)()(
))((
afbf
abbfbc
−−
−=
l
a[ ]ba,
[ ]ba,
b ( ).cf
c
y
•
3.1 Interpretação geométrica
0l
4251
0011 0010
a b0x x1x
•
1l•
•
3.2 Algoritmo do método da corda falsa
Seja f contínua em [a, b], com uma única raíz neste intervalo.
1. Dados iniciais:
- intervalo inicial [a, b]- precisões
2. k = 0
( ) ab −−=
21 ,εε
4251
0011 0010
3. ( )( ) ( )afbf
abbfbxk −
−−=
5.
8. k = k +1. Volte ao passo 3
7 passo o para Vá . faça ,0)()( Se kk xaxfaf =>
kxb =
4. Se , faça . FIM1|)(| ε<kxf kxr =
6.
FIM . faça , Se 2 kxrab =<− ε7.
3.3 Majorante para o erro absoluto de uma estimativa
( ) { }.,max kkkkkka xbaxrxxe −−≤−=
3.4 Ordem de convergência do método da corda falsa
rx −
4251
0011 0010
crx
rx
k
k
k=
−
−
−∞→
1
lim
onde
com e pelo que a convergência dométodo da corda falsa é linear.
( )( )
0'
'1 >−=
εf
rfc
( )ba,∈ε ( ) ( ),'' εfrf <
4. Método de 5ewton Raphson
4251
0011 0010
Seja uma função com derivadas contínuas até à segunda ordem no intervalo , e para todo
Seja r a única raíz da equação nesse intervalo.
Pela fórmula de Taylor, se [ ],,bax ∈
[ ]ba, ( ) 0' ≠xf ( ).,bax ∈
( ) 0=xf
( ) ( ) 0<bfaf
f
4.1 Abordagem analítica
4251
0011 0010
Pela fórmula de Taylor, se
para algum entre e .
[ ],,0 bax ∈
( ) ( ) ( ) ( ) ( ) ( )!2
''' 2
0000
ξfxrxfxrxfrf −+−+=
ξ r0x
Como e ,
Se r está próximo de , o termo
( )( )
( ) ( )( )0
20
0
00 '2
''
' xf
fxr
xf
xfxr
ξ−+−=
0x
( ) ( )( )
20 '2
''
xf
fxr
ξ−
( ) 0=rf ( ) 0' 0 ≠xf
4251
0011 0010
é pequeno em valor absoluto e podemos escrever
( )( )0
0 '2 xfxr −
( )( )
.' 0
00
xf
xfxr −≈
Deste modo
é uma estimativa para a raíz r.
Pondo
( )( )0
001 ' xf
xfxx −=
( )( )
112 ' xf
xfxx −=
4251
0011 0010
temos outra estimativa para a raíz r.
Este procedimento pode repetir-se e obtemos assim uma sucessão
de valores aproximados da raíz r.
,...,, 210 xxx
( )112 ' xf
A partir de uma aproximação inicial gera-se uma sucessão
de aproximações sucessivas da raíz r através do processo iterativo dado por
0x
,...,, 210 xxx
4251
0011 0010
iterativo dado por
( )( )
,' 1
11
−
−− −=
k
k
kkxf
xfxx ,...2,1=k
4.2 Interpretação Geométrica
1Ly
f
Dado o ponto , traçamos a recta , tangente à curva nesse ponto, dada por e a abcissa do ponto de intersecção desta recta com o eixo dos x dá-nos uma aproximacão da raíz.
))(,( ii xfxiL
))((')()( iiii xxxfxfxL −+=
1+ix
4251
0011 0010
0x 1x2x xr0L
•
•
•
4.3 Algoritmo do M5R
Consideremos a equação f(x)=0.
1. Dados iniciais:
- aproximação inicial 0x
- precisões 21 ,εε
2. Se , faça . FIM 10 |)(| ε<xf 0xr =
3. k = 1)(xf
4251
0011 0010
4.)('
)(
1
11
−
−− −=
k
k
kkxf
xfxx
5.FIM . faça
|| seou
|)(| Se
21
1k
kk
kxr
xx
xf=
<−
<
− ε
ε
6. k = k + 1. Volte ao passo 4
4.4 Estudo da Convergência do M5R
Teorema. Seja f uma função que verifica as condições:
(i) f tem derivadas contínuas até à segunda ordem num intervalo
(ii) ;
(iii) para todo ;
( ) ( ) 0<bfaf
( ) 0' ≠xf [ ]bax ,∈
[ ]
[ ] ;,ba
4251
0011 0010
(iv) não muda de sinal no intervalo
(v) para algum
Então a sucessão
gerada pelo MNR, converge para a única raíz de
em .
''f
,...,, 210 xxx
( ) 0=xf
[ ]bax ,0 ∈( ) ( ) 0'' 00 >xfxf
[ ] ;,ba
[ ]ba,
Teorema. Seja f uma função que verifica as condições:
(i) f tem derivadas contínuas até à segunda ordem num intervalo
(ii) ;
(iii) para todo ;
( ) ( ) 0<bfaf
( ) 0' ≠xf [ ]bax ,∈
[ ] ;,ba
4251
0011 0010
(iv) não muda de sinal no intervalo
(v) e
Então a sucessão gerada pelo MNR, converge para a única raíz de em , para qualquer valor inicial
''f
( ) 0=xf
[ ] ;,bax∈
[ ]ba,
( )( )
abaf
af−≤
'( )( )
.'
abbf
bf−≤
[ ] .,0 bax ∈
Ordem de convergência do M5R
0lim2
1-
>=−
−∞→
crx
rx
k
k
k
2
1 rxcrx kk −≈− −
Assim, para k suficientemente grande,
4251
0011 0010
1 rxcrx kk −≈− −
O erro da iteração do MNR é proporcional ao quadrado do erro da iteração anterior. Por isso, a convergência é quadrática.
5. Método da secante
4251
0011 0010
A desvantagem que o método de Newton-Raphson apresenta ao ser necessário calcular a derivada da função (em certos problemas pode consumir muito tempo computacional) pode ser contornada pelo método da secante.
No método da secante, a derivada é substituída por:
( ) ( ) ( ).' 21
1−−
− −−
≈ kkk
xx
xfxfxf
4251
0011 0010
Consequentemente, substituindo na fórmula iterativa do método de Newton-Raphson, obtemos a fórmula iterativa do método da secante:
( ) .'21
1−−
− −≈
kk
kxx
xf
( )( )( ) ( )
,...3,2,21
2111 =
−−
−=−−
−−−− k
xfxf
xxxfxx
kk
kkkkk
Esta transformação faz com que seja necessário mais uma aproximação inicial para aproximar a primeira derivada.
Os critérios de convergência são os mesmos do método de Newton-Raphson, à excepção da última condição que pode ser adaptada para a escolha de duas estimativas iniciais:
Se e( )
abaf
−≤( )
,abbf
−≤
4251
0011 0010
Se e
então quaisquer podem ser utilizados para iniciar o método.
Por outro lado, se existirem tais que
e , então esses valores podem ser estimativas iniciais.
( )( )
abaf
af−≤
'
( )( )
,'
abbf
bf−≤
[ ]baxx ,, 10 ∈
[ ]baxx ,, 10 ∈
0)('')( 00 >xfxf 0)('')( 11 >xfxf
A ordem de convergência do método da secante é
.618.12
51≈
+=p
4251
0011 0010
f
r x
y
Interpretação geométrica
x xx
4251
0011 0010
r x
•
A partir de duas aproximações , a aproximação
é obtida como sendo a abcissa do ponto de intersecção
do eixo dos x e da recta que passa pelos pontos
12, −− kk xxkx
( )( ) ( )( ).,,, 2211 −−−− kkkk xfxxfx
•
2−kx 1−kxkx