2_Equaaes pptx

Prévia do material em texto

Raízes de equações não lineares
1 – Introdução
1.1 – Localização das raízes
1.2 – Refinamento
2 – Método da bissecção
2.1 – Interpretação geométrica
2.2 –Algoritmo
2.3 – Estimativa do número de iterações 
2.4 – Estudo da convergência
3 – Método da corda falsa
3.1 – Interpretação geométrica
3.2 –Algoritmo
3.4 – Limite superior do erro absoluto de uma aproximação
3.3 – Estudo da convergência
4 – Método de Newton–Raphson (MNR)
4.1 –Abordagem analítica
4.2 – Interpretação geométrica
4.3 –Algoritmo
4.4 – Estudo da convergência
5 – Método da secante
1. Introdução
Pretende-se estudar alguns métodos iterativos que 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
  .04cos
,0
,03
,0732
2
2
1
4
24






xe
xe
xx
xx
x
x
Definição. Se é uma função real de variável real e 
é um número real tal que , então dizemos que é um zero 
real da função ou que é uma raiz da equação
Graficamente, os zeros reais de são as abcissas dos pontos de 
interseção do gráfico de com o eixo dos .
f
  0rf r
f   .0xf
f
r
f
r
x
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
para encontrar uma nova aproximação para a raiz.
A determinação das raízes de uma equação por um método 
numérico envolve duas fases:
1º Localização das raizes
Consiste em obter um intervalo que contém uma única raiz
da equação
2º Refinamento
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 raiz 
com uma precisão ε prefixada.
r
  0xf
 ba,
 ba,
  .0xf
1.1 Localização das raizes
Nesta fase é feita uma análise gráfica e teórica da função. 
Análise Gráfica
Pode ser feita através de um dos seguintes processos:
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
(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.
(ii) A partir da equação f (x) = 0, obter uma equação equivalente 
g(x) = h(x), esboçar os gráficos de g(x) e h(x) no mesmo eixo Cartesiano
e localizar as abcissas dos pontos de intersecção dos dois gráficos.
).()(0)( rhrgrf 
Exemplo
xexf x  )(
Logo
xxh
exg
exexxf
x
xx





)(
)(
00)(
]1,0[r
-2 -1 0 1 2 3 4
-2
-1
0
1
2
3
4
5
6
7
8
hg
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
1r 2r
y
x
1r 2r 3ra b
y
x
 bar ,
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 no máximo uma raiz nesse intervalo.
Graficamente
y
xa b
y
xa b
],[,0)(' baxxf  ],[,0)(' baxxf 
),( bac
Podemos aplicar estes teoremas atribuindo valores a x e analisando o 
sinal de f (x).
Exemplo
• Analisando a mudança de sinal, pode concluir-e que existe pelo
menos uma raiz dentro dos intervalos indicados. 
• A derivada não muda de sinal em cada um dos 
intervalos, portanto cada raiz é única no intervalo.
  393  xxxf
x -10 -5 -3 -1 0 1 2 3 4
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
y
x
y
x
x
y
a b1r 2r b1r
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.
Obtem-se assim uma sucessão de aproximações da 
solução .
A cada aproximação corresponde o erro absoluto e o erro 
relativo
• Estudar a convergência da sucessão.
É claro que o método iterativo deve ser convergente; ou seja, 
deve verificar-se que ou
kx
,...,, 210 xxx
0x
rxk 
.
r
rxk 
r
rxk
k


lim .0lim 

rxk
k
.r
kx
• Estudar a velocidade de convergência.
Definição. Se para um dado método iterativo existirem constantes e
tais que diz-se que é a ordem de convergência do método 
e que é 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 
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 só é 
considerada quando se comparam processos iterativos com a mesma ordem de 
convergência. Nesse caso, quanto menor for a constante de erro assimptótico 
mais rápida é a convergência do processo. 
0c
,lim
1
c
rx
rx
p
k
k
k





p
p
kk rxcrx  1 .k
1p
21  p
1p
2p
c r
r kx
y
x
r
kx x




|)(|
||
k
k
xf
rx
 || rxk |)(| kxf
É impraticável realizar um número infinito de iterações; é 
necessário parar num determinado termo 
Diz-se que o valor de xk é raiz aproximada com precisão se:
ou .
Nem sempre é possível ter as duas condições satisfeitas 
simultaneamente:




|)(|
||
k
k
xf
rx
.kx

y
Como não se conhece o valor da raiz r para aplicar o teste 
utiliza-se frequentemente a estimativa 
do erro absoluto para o critério de paragem.
Critérios de paragem alternativos:
Impondo um número máximo de iterações

 
k
kk
x
xx 1
 1kk xx
  kxf
, rxk 1 kk xx




2. Método da bissecção
Condições para aplicação:
A função deve ser contínua no intervalo [a, b], onde 
contém uma única raiz r.
O objetivo deste método é reduzir a amplitude do intervalo 
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
Iteração 1
2.1 – Interpretação Geométrica
ra0=a b0=bx0
x0 = a0 + b0
2
f (a0) f (x0) < 0
a1 = a0
b1 = x0
r  a1 , b1]
Iteração 2
x1 = a1 + b1
2
x1
f (b1) f (x1) < 0
a2 = x1
b2 = b1
r  a2 , b2]
 
2.2 Algoritmo do método da bisseção
1. Dados iniciais:
- função 
- intervalo 
- precisão
2.
3. 
4. Se faça . FIM
5. Se então faça e . Vá para o passo 7. 
6. e 
7. . Vá para o passo 3. 

] ,[ ba
bbaak kk  ,,0
2
kk
k
ba
x


kxr 
    ,0kk xfaf
kk xa 1 kk bb 1
kk aa 1 kk xb 1
1 kk
|)(| kxf
f
2.3 Estimativa do número de iterações
aa 0 bb 0
1a 1b
2
00
110
ab
abrx


2a 2b
2
0011
221
22
abab
abrx




3a 3b
3
0022
332
22
abab
abrx




1
00
11
22 





k
kk
kkk
abab
abrx

1ka 1kb

Quantas iterações do métododa bisseção são necessárias para 
garantir um erro absoluto inferior a um certo valor pré-fixado?
1
2log
log)log( 00 


ab
k
 


1
00
2k
k
ab
rx
  




 


00log2log1
ab
k

0012
abk  
Pretende-se encontrar o menor inteiro k que verifica a condição 
. rxk
2.4 Convergência do método da bisseção
A convergência do método da bisseção é linear: 
2
1
1
lim 


 rx
rx
k
k
k
3. Método da corda falsa
Condições para aplicação:
A função f deve ser contínua no intervalo , onde contém uma única raiz r.
Sejam e . 
No método da corda falsa, considera-se a recta que passa pelos pontos 
e .
A primeira estimativa da raíz r é a abcissa do ponto de interseção da recta 
com o eixo dos x :
O intervalo é então substituído pelo intervalo limitado por 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é se atingir a precisão desejada.
  00 , afa
.
)()(
))((
00
000
00
afbf
abbf
bx



0
 0xf
 ba,
  00 , bfb
aa 0 bb 0
0x 0
 00 ,ba 0x
0a 0b
0x x
y
1x


3.1 Interpretação geométrica
0
1


0a 0b
3.2 Algoritmo do método da corda falsa
1. Dados iniciais:
- função 
- intervalo [a, b]
- precisão
2. k = 0, 
3. 
4. Se , faça . FIM
5. Se então Vá para o passo 7. 
6.
7. k = k +1. Vá para o passo 3
 
   kk
kk
kkk
afbf
ab
bfbx




|)(| kxf
kxr 
    ,0kk xfaf .1 kk xb 
kkkk bbxa   11 , 
bbaa kk  ,
,1 kk aa 
f
3.3 Majorante para o erro absoluto de uma estimativa
 .,max kkkkkk xbaxrxx 
3.4 Ordem de convergência do método da corda falsa
para algum pelo que tem ordem de convergência linear. 
c
rx
rx
k
k
k





1
lim
,0c
4. Método de Newton Raphson
Seja uma função contínua com derivadas contínuas até à segunda
ordem no intervalo , e para todo 
Seja r a única raiz da equação nesse intervalo.
Pela fórmula de Taylor, se
para algum entre e . 
 ,,0 bax 
         
 
!2
''
'
2
0000
f
xrxfxrxfrf 
 ba,   0' xf  .,bax
  0xf
    0bfaf
f
4.1 Abordagem analítica
 r
0x
Como e , 
Se r está próximo de , o termo 
é pequeno em valor absoluto e tem-se então que
 
 
 
 
 0
2
0
0
0
0
'2
''
' xf
f
xr
xf
xf
xr


0x
 
 
 0
2
0
'2
''
xf
f
xr


 
 
.
' 0
0
0
xf
xf
xr 
  0rf   0' 0 xf
Deste modo
é uma estimativa para a raiz r.
Pondo
tem-se outra estimativa para a raiz r. 
Este procedimento pode repetir-se e obtém-se assim uma 
sucessão de valores aproximados da raiz r.
 
 0
0
01
' xf
xf
xx 
,...,, 210 xxx
 
 1
1
12
' xf
xf
xx 
A partir de uma aproximação inicial gera-se uma sucessão 
de aproximações sucessivas da raiz r através
do processo iterativo dado por 
0x
,...,, 210 xxx
 
 
,
' 1
1
1


 
k
k
kk
xf
xf
xx ,...2,1k
4.2 Interpretação Geométrica
0x 1x2x
y
x
f 
r
Dado o ponto , traça-se a reta , tangente à curva 
nesse ponto, dada por . A abcissa do 
ponto de interseção desta reta com o eixo dos x fornece uma 
aproximacão da raiz. 
))(,( ii xfx i
))((')()( iiii xxxfxfx 
1ix
1
0



4.3 Algoritmo do MNR
Considere-se a equação
1. Dados iniciais:
- aproximação inicial
- precisão 
2. Se , seja FIM
3.
4.
5. Se , seja 
6. k = k + 1. Vá para o passo 4
0x

|)(| 0xf
)('
)(
1
1
1


 
k
k
kk
xf
xf
xx
|)(| kxf
.0)( xf
.0xr 
1k
kxr 
4.4 Estudo da Convergência do MNR
Teorema. Seja f uma função que verifica as condições:
(i) f é contínua e tem derivadas contínuas até à segunda ordem 
no intervalo 
(ii) ;
(iii) para todo ;
(iv) não muda de sinal no intervalo 
(v) e , ou
existe tal que .
Então a sucessão gerada pelo MNR, converge
para a única raiz de em .
    0bfaf
  0' xf
''f
 bax ,
  0xf
    0'' 00 xfxf
 ;,ba
 ba,
 ;,ba
 
 
ab
af
af

'
 
 
ab
bf
bf

'
 bax ,0 
,...,, 210 xxx
Nota. A condição (v) do teorema anterior serve para escolher o 
valor inicial.
No primeiro caso, qualquer serve. 
No segundo caso, já é indicada uma estimativa para o valor 
inicial. 
 bax ,0 
Ordem de convergência do MNR
0lim
2
1-




c
rx
rx
k
k
k
2
1 rxcrx kk  
Assim, para suficientemente grande,
A convergência é, portanto, quadrática. 
k
5. Método da secante
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: 
Consequentemente, fazendo esta substituição na fórmula iterativa do 
método de Newton-Raphson, obtem-se a fórmula iterativa do método da 
secante:
   
.
21
21




kk
kk
xx
xfxf
  
   
,...3,2,
21
211
1 





 k
xfxf
xxxf
xx
kk
kkk
kk
 1' kxf
f
r x
y
Interpretação geométrica
A partir de duas aproximações a aproximação
é obtida como sendo a abcissa do ponto de interseção
do eixo dos x e da reta que passa pelos pontos
12 ,  kk xx kx
     .,,, 2211  kkkk xfxxfx
2kx 1kxkx


k
k
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
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. 
 
 
ab
af
af

'
 
 
,
'
ab
bf
bf

 baxx ,, 10 
 baxx ,, 10 
0)('')( 00 xfxf 0)('')( 11 xfxf
A ordem de convergência do método da secante é 
.618.1
2
51


p