aula-zeros-slides

Prévia do material em texto

Cálculo Numérico
Solução aproximada de equações de uma variável
Prof. Daniel G. Alfaro Vigo
dgalfaro@dcc.ufrj.br
Departamento de Ciência da Computação
IM – UFRJ
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Parte I
Localização de zeros e Método da
bissecção
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Motivação: Queda de um paraquedista
Sob algumas hipóteses simplificadoras podemos considerar que a
velocidade de um paraquedista em queda livre satisfaz a equação
v(t) =
g
k
(
1− e−kt
)
onde g = 9, 81 m/s2 é a aceleração da gravidade e k > 0 é um
coeficiente (com unidade 1/s) relacionado com a resistência do
paraquedas.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Motivação: Queda de um paraquedista
Conhecendo que um paraquedista em queda livre após 5 s tinha
uma velocidade de 10m/s, queremos saber qual é o valor do
coeficiente k correspondente?
Para isso devemos resolver a equação
10 =
9, 81
k
(
1− e−5k
)
⇓
10− 9, 81
k
(
1− e−5k
)
= 0 .
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Motivação: Queda de um paraquedista
Ou seja, devemos determinar um zero da função
f (x) = 10− 9, 81
x
(
1− e−5x
)
.
-2.5 0 2.5 5 7.5 10 12.5 15 17.5 20
-5
5
10
y = f(x)=10-9,81 ( 1-e¯⁵ˣ )/x
zero de f
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Motivação: Queda de um paraquedista
Se tentarmos isolar a incógnita k na equação
10 =
9, 81
k
(
1− e−5k
)
,
infelizmente não conseguiremos!
Isso não é de se surpreender, mesmo para funções polinomiais não
existem fórmulas gerais para determinar seus zeros (Teorema de
Abel-Ruffini).
Alternativa prática
Determinar uma solução aproximada com o ńıvel de precisão
prefixado.
Mas, começemos por uma questão mais simples ...
Onde procurar pela solução da equação?
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
http://pt.wikipedia.org/wiki/Teorema_de_Abel-Ruffini
http://pt.wikipedia.org/wiki/Teorema_de_Abel-Ruffini
Localização de zeros: Teorema de Bolzano
Teorema 1 [Teorema de Bolzano]
Seja f uma função cont́ınua no intervalo [a, b]. Se f (a) e f (b)
possuem sinais diferentes (ou seja f (a)f (b) < 0), então existe um
número c ∈ (a, b) tal que f (c) = 0 .
-1 -0.5 0 0.5 1
-1.6
-0.8
0.8
1.6
a bc
Aqui f(c)=0
f(x)=2x^3-x^2+x-1
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Localização de zeros
Observações sobre o teorema de Bolzano
Simples de aplicar.
Indica uma condição apenas suficiente, mas a situação é
muito geral!
Garante a existência de pelo menos um zero, infelizmente não
há garantia de unicidade.
Teorema 2 (sobre a unicidade)
Se além das condições do Teorema 1, a função é diferenciável no
intervalo (a, b) e sua derivada não muda de sinal nesse intervalo
(ou seja f ′(x) > 0 ou < 0 para todo x ∈ (a, b) ), então existe um
único número c ∈ (a, b) tal que
f (c) = 0.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Localização de zeros: Exemplo
f (x) = 10− 9, 81
x
(
1− e−5x
)
⇒ f (0, 5) < 0, f (1, 5) > 0.
f ′(x) =
9, 81
x2
(
1− e−5x
)
− 49, 05e
−5x
x
> 0, 0, 5 < x < 1, 5.
Pelo Teorema, existe um único zero no intervalo [0, 5, 1, 5]!
-1 0 1 2 3 4 5 6 7 8 9
-5
5
10
y = f(x)=10-9,81 (1-e¯⁵ˣ )/x
y = f' (x)=-9,81 (1-e¯⁵ˣ )/x² - 49,05 e¯⁵ˣ/x
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Método da bissecção
A função satisfaz as hipóteses do Teorema de Bolzano.
Dividimos o intervalo inicial pela metade para determinar um
novo intervalo (umas das metades do inicial) em que está
contido um zero da função e repetimos esse processo para
cada novo intervalo, até obtermos uma boa aproximação.
Formalizando
Começamos com k = 1, [a1, b1] = [a, b] e repetimos o
seguinte processo.
Dado o intervalo [ak , bk ], definimos pk =
ak+bk
2 = ak +
bk−ak
2
1 Se f (pk) = 0 ⇒ pk é um zero da função!
2 Se f (ak)f (pk) < 0 ⇒ novo intervalo [ak+1, bk+1] = [ak , pk ]
3 Se f (pk)f (bk) < 0 ⇒ novo intervalo [ak+1, bk+1] = [pk , bk ]
(Escolhemos o intervalo onde f muda de sinal nos extremos.)
Paramos quando o erro seja pequeno o suficiente.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Método da bissecção
Qual será a qualidade da aproximação pk?
Se c ∈ (ak , bk) é um zero de f e pk = ak+bk2 então
|c − pk | ≤ max{pk − ak , bk − pk} ⇒ |c − pk | ≤ bk−ak2
Assim se queremos uma aproximação com erro (absoluto) menor
que um � > 0 prefixado podemos que usar o seguinte critério de
parada.
Critério de parada
Na iteração k-ésima o erro será pequeno o suficiente (menor que �)
quando
bk − ak
2
< �
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Método da bissecção
Quantas iterações precisamos fazer para chegar em uma
aproximação pk com a qualidade desejada?
Queremos que o erro absoluto seja menor que um � > 0 prefixado,
ou seja
|c − pk | < �.
É suficiente que bk−ak2 < �, por outro lado
bk−ak
2 =
b−a
2k
. Logo
b − a
2k
< � ⇒ k >
log(b−a� )
log 2
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Algoritmo: Método da bissecção
Considere f cont́ınua no intervalo [a, b] e tal que f (a)f (b) < 0.
Entradas: a, b; tol (tolerância); Niter (número máximo de
iterações)
Sáıda: p (valor aproximado) ou mensagem de erro
1 Faça k = 1; fa = f (a)
2 Enquanto k ≤ Niter , execute os passos 3–6
3 Faça p = a + (b − a)/2; fp = f (p)
4 Se fp = 0 ou (b − a)/2 < tol então
SAIDA: p; PARE
5 Se fa · fp > 0 então
Faça a = p; fa = fp
senão
Faça b = p;
6 Faça k = k + 1
7 SAIDA: ‘o método falhou após Niter iterações’; FIM
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método da bissecção
O seguinte resultado representa a justifica matemática desse
método.
Teorema 3 [Convergência do método da bissecção]
Seja f uma função cont́ınua no intervalo [a, b] tal que f (a) e f (b)
possuem sinais diferentes, então quando aplicamos o método da
bissecção podemos obter um zero de f após um número finito de
passos ou as sequências de números ak , bk e pk tais que
limk→∞ ak = limk→∞ bk = limk→∞ pk = c ∈ (a, b) e f (c) = 0.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: queda de um paraquedista
Para estudar a queda de um paraquedista consideramos um
modelo simplificado, em que o movimento é na vertical.
Gravidade FG e a resistência do ar FR .
FG = mg onde m é a massa do paraquedista
e g = 9, 81 m/s2 é a aceleração da
gravidade.
Para FR consideramos o modelo linear
FR = −cv
onde v é a velocidade e c é o coeficiente de
arrasto (kg/s).
Da segunda lei de Newton obtemos
m
dv
dt
= FG − FR ⇒
dv
dt
= g − c
m
v
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda de um paraquedista
Considerando v(0) = v0 a solução para essa EDO é
v(t) = v0 + (
g
k
− v0)
(
1− e−kt
)
, onde k = c/m.
Problema: Determinar k com uma tolerância tol = 0, 1 sabendo
que o paraquedas abriu quando a velocidade do paraquedista era
de 40m/s e após 5 s ele tinha uma velocidade de 10m/s.
Solução: Neste caso devemos resolver a equação
f (x) = 30 +
(
9, 81
x
− 40
)(
1− e−5x
)
= 0.
Notando que limx→0+ f (x) = 79, 05, podemos considerar
f (0) = 79, 05 e assim f será cont́ınua em [0,+∞). Por outro lado
como f (2) = −5, 093..., pelo T. de Bolzano conclúımos que existe
pelo menos uma solução no intervalo (0, 2).
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda de um paraquedista
Aplicando o método da bissecção.
f (p) = 0 ou b−a2 < tol? NÃO, f (a)f (p) > 0? SIM ⇒ p → a
f (p) = 0 ou b−a2 < tol? NÃO, f (a)f (p) > 0? NÃO ⇒ p → b
f (p) = 0 ou b−a2 < tol? NÃO, f (a)f (p)> 0? NÃO ⇒ p → b
f (p) = 0 ou b−a2 < tol? NÃO, f (a)f (p) > 0? NÃO ⇒ p → b
f (p) = 0 ou b−a2 < tol? SIM! Aproximação: x ≈ p = 1, 0625
k a b p = a+b2 f (a) f (p)
b−a
2 < tol
1 0 2 1 79, 05 0, 0134 1 > 0, 1
2 1 2 1, 5 0, 0134 −3, 4415 0, 5 > 0, 1
3 1 1, 5 1, 25 0, 0134 −2, 0899 0, 25 > 0, 1
4 1 1, 25 1, 125 0, 0134 −1, 1672 0, 125 > 0, 1
5 1 1, 125 1, 0625 0, 0134 −0, 6154 0, 0625 < 0, 1
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Parte II
Método do ponto fixo
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Motivação
No primeiro problema do paraquedista queremos resolver a equação
f (x) = 10− 9, 81
x
(
1− e−5x
)
= 0
Essa equação pode ser re-escrita na forma
10− 9, 81
x
(
1− e−5x
)
= 0 ⇒ x = 0, 981
(
1− e−5x
)
Dessa forma o zero que estamos procurando, coincide com o
número c tal que g(c) = c onde g(x) = 0, 981
(
1− e−5x
)
.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Ponto fixo
-0.25 0 0.25 0.5 0.75 1 1.25 1.5 1.75 2 2.25
0.5
1
1.5 y=x
y = 9,81 (1-exp(-5x))
c = g(c)
c
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Ponto fixo
Definição de ponto fixo
Seja g uma função definida no intervalo [a, b], um número
c ∈ [a, b] tal que g(c) = c é chamado de ponto fixo de g .
Temos os seguintes resultados.
Teorema 4 [Existência e unicidade do ponto fixo]
Seja g uma função cont́ınua no intervalo [a, b].
a) Se a ≤ g(x) ≤ b para todo x ∈ [a, b], então existe pelo menos
um ponto fixo de g em [a, b].
b) Se além disso, g é diferenciável em (a, b) e existe uma
constante positiva κ < 1 tal que |g ′(x)| ≤ κ para todo x ∈ (a, b)
então o ponto fixo é único.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Método do ponto fixo
Para obter aproximações do ponto fixo c de g a partir de uma
aproximação inicial p0 constrúımos novas aproximações fazendo
pn+1 = g(pn), n ≥ 0.
A função g é chamada de função de iteração.
0 0.2 0.4 0.6 0.8 1
0
0.2
0.4
0.6
0.8
1
1.2
Iterações de ponto fixo
 
 
p0 p1 p2 p3
y=g(x)
y=x
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Algoritmo: Método do ponto fixo
Aproxima um ponto fixo de g a partir do chute inicial p0.
Entradas: p0 (aproximação inicial); tol (tolerância); Niter (número
máximo de iterações)
Sáıda: p (valor aproximado) ou mensagem de erro
1 Faça k = 1
2 Enquanto k ≤ Niter , execute os passos 3–6
3 Faça p = g(p0)
4 Se |p − p0| < tol , então
SAIDA: p; PARE
5 Faça p0 = p
6 Faça k = k + 1
7 SAIDA: ‘o método falhou após Niter iterações’; FIM
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método do ponto fixo
Teorema 5 [Convergência do método do ponto fixo]
Seja g uma função cont́ınua no intervalo [a, b], tal que
a ≤ g(x) ≤ b para todo x ∈ [a, b]. Suponha adicionalmente que g
é diferenciável em (a, b) e existe uma constante positiva κ < 1 tal
que |g ′(x)| ≤ κ para todo x ∈ (a, b), então para qualquer
p0 ∈ [a, b] a sequência pn definida por
pn+1 = g(pn), n ≥ 0
converge para o único ponto fixo c da função g em [a, b].
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método do ponto fixo (cont)
Corolário [Qualidade da aproximação]
Nessas condições, o erro na aproximação pn satisfaz as limitantes
|c − pn| ≤
κ
1− κ
|pn − pn−1|,
|c − pn| ≤
κn
1− κ
|p1 − p0|,
|c − pn| ≤ κn max{p0 − a, b − p0}.
Se κ for conhecido garantimos que |c − pn| < � quando
|pn − pn−1| <
(1− κ)�
κ
.
Critério de parada
Na prática, quando não conhecemos κ, usamos a condição
|pn − pn−1| < �tol .
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método do ponto fixo (cont)
Suponha que κ < 1 é conhecido. Para garantir que |c − pn| < � é
suficiente escolher n de forma que
κn
1− κ
|p1 − p0| < � ⇒ n > log
(
|p1 − p0|
(1− κ)�
)
/ log(κ−1)
ou alternativamente
κn max{p0 − a, b − p0} < �
⇓
n > log
(
max{p0 − a, b − p0}
�
)
/ log(κ−1)
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método do ponto fixo (cont)
Essas fórmulas são semelhantes àquela do caso do método da
bissecção mas com κ−1 no lugar de 2. Assim um método de ponto
fixo com κ < 1/2 em geral vai convergir mais rápido que o método
da bissecção.
Obsevações:
Se o valor de κ se aproxima de zero o número de iterações
diminui. Quanto menor o valor de κ tanto mais rápida será a
convergência!
O fator κ nos ajuda a comparar a velocidade de convergência
de diferentes métodos de ponto fixo, e vai nos guiar na
construção de um método de ponto fixo muito eficiente.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método do ponto fixo (cont)
Para aplicar o teorema de convergência acima devem ser satisfeitas
duas condições de caráter global, ou seja relacionadas com todo o
intervalo [a, b] ou (a, b), a saber
g([a, b]) ⊂ [a, b]
|g ′(x)| ≤ κ < 1, ∀x ∈ (a, b).
Apresentamos um resultado de convergência local que nos será
muito útil.
Teorema 6 [Convergência local do método do ponto fixo]
Seja g uma função com primeira derivada cont́ınua no intervalo
[a, b]. Se c ∈ (a, b) é um ponto fixo de g e |g ′(c)| < 1, então
existe δ > 0 tal que para qualquer p0 ∈ [c − δ, c + δ] a sequência
pn definida por
pn+1 = g(pn), n ≥ 0
converge para o ponto fixo c .
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista
Nesse problema temos g(x) = 0, 981
(
1− e−5x
)
. Observamos que
g(0.5) = 0.9004746 > 0.5 e g(1.5) = 0.9804574 < 1.5.
Além disso g ′(x) = 4.905 e−5x > 0, por isso a função é crescente e
temos que
0.25 ≤ g(x) ≤ 1.5 ∀x ∈ [0.5, 1.5]
⇒ Existe pelo menos um ponto fixo em [0.5, 1.5] .
Ainda, sabemos que a função g ′(x) também é decrescente e
g ′(0.5) = 0.4026269, portanto
|g ′(x)| ≤ κ = 0.4026269 ∀x ∈ [0.5, 1.5]
⇒ Dessa forma existe um único ponto fixo em [0.5, 1.5] .
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista (cont.)
Consideramos �tol = 10
−5 e p0 = 0.5
n (iteração) pn (aproximação) |pn − pn−1| (erro)
0 0.5 −−
1 0.9004746163499552 4.005e − 01
2 0.9701279054026780 6.965e − 02
3 0.9733252713902726 3.197e − 03
4 0.9734469904282078 1.217e − 04
5 0.9734515857550120 4.595e − 06
Usando �tol = 10
−16 em 13 iterações obtemos
pn = 0.9734517659925497.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista (cont.)
Para esse caso considerando κ = |g ′(0.5)| = 0.4026269 e
� = 10−16 obtemos que
niter > log
(
�
max{p0 − a, b − p0}
)
/ log κ ≈ 40.5.
Essa previsão é muito pessimista!
Se por outro lado escolhemos κ = |g ′(0.9)| = 0.0544896 obtemos
niter > 12.7,
que está bem mais próximo do que foi observado!
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Parte III
Método de Newton-Raphson
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Procurando um bom método de ponto fixo
Considere a equação f (x) = 0, e suponha que ela possui uma
solução c isolada.
Qualquer equivalência
f (x) = 0 ⇐⇒ g(x) = x
nos leva a um método de ponto fixo (alguns podem não
convergir!).
Para um método do ponto fixo ter uma convergência bem
rápida, o ideal seria que κ = 0.
Essa situação corresponde ao caso especial quando o gráfico
de g(x) é uma reta horizontal.
Vamos exigir apenas que κ fique muito próximo de zero em
uma vizinhança do ponto fixo c .
Uma forma bastante natural de garantir isto é exigindo que
g ′(c) = 0.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Procurando um bom método de ponto fixo (cont.)
Vamos procurar a função g na forma
g(x) = x + a(x)f(x).
Observe que
g(c) = c + a(c)f (c) = c + a(c) · 0 ⇒ g(c) = c .
Considerando g ′(c) = 0 obtemos
g ′(x) = 1 + a′(x)f (x) + a(x)f ′(x) ⇒ g ′(c) = 1 + a(c)f ′(c)
logo
a(c) = − 1
f ′(c)
.
Definindo
a(x) = − 1
f ′(x)
satisfazemos a exigência!
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Método de Newton-Raphson
Obtemos então o método de Newton-Raphson
pn+1 = pn −
f (pn)
f ′(pn)
, n ≥ 0
Observações
Método para achar aproximações de um zero da função f .
Representa um método de ponto fixo com g(x) = x − f (x)f ′(x) .
É preciso de um chute inicial p0 para iniciar as iterações.
A derivada f ′(pn) não pode ser zero. Na prática, se for muito
próxima de zero teremos problemas com a convergência.
As vezes é chamado apenas de método de Newton ou método
da tangente.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Interpretação geométrica
A interseção com o eixo x da reta tangente à curva y = f (x) em
x = pn, nos dá a nova aproximação pn+1.
0.25 0.5 0.75 1
-0.5
-0.25
0.25
0.5
p0
p1
p2
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Algoritmo: Método de Newton
Aproxima um zero de f a partir do chute inicial p0.
Entradas: p0 (aproximação inicial); tol (tolerância); Niter (número
máximo de iterações)
Sáıda: p (valor aproximado) ou mensagem de erro
1 Faça k = 1
2 Enquanto k ≤ Niter , execute os passos 3–6
3 Faça p = p0 − f (p0)/f ′(p0)
4 Se |p − p0| < tol , então
SAIDA: p; PARE
5 Faça p0 = p
6 Faça k = k + 1
7 SAIDA: ‘o método falhou após Niter iterações’; FIM
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método de Newton
Teorema 6 [Convergência do método de Newton]
Seja f uma função com duas derivadas cont́ınuas no intervalo
[a, b]. Suponha que c ∈ (a, b) é um zero de f tal que f ′(c) 6= 0.
Então existe δ > 0 tal que para qualquer chute inicial p0 no
intervalo [c − δ, c + δ] a sequência pn definida por
pn+1 = pn −
f (pn)
f ′(pn)
, n ≥ 0
converge para c .
Observações
O Teorema, garante a convergência quando escolhemos o chute
inicial p0 suficientemente próximo de c . Nesse sentido dizemos
que a convergência do método é local.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista
Lembramos que temos que resolver a equação
f (x) = 10− 9, 81
x
(
1− e−5x
)
= 0.
Como
f ′(x) =
9, 81
x2
(
1− e−5x
)
− 49, 05 e
−5x
x
,
chegamos no método
pn+1 = pn −
10− 9,81pn
(
1− e−5pn
)
9,81
p2n
(1− e−5pn)− 49,05 e−5pnpn
, n ≥ 0.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista (cont.)
Consideramos �tol = 10
−16 e p0 = 0.5
n (iteração) pn (aproximação) |pn − pn−1| (erro)
0 0.5 −−
1 0.7863964997280066 2.864e − 01
2 0.9420268360016844 1.556e − 01
3 0.9725387355540107 3.051e − 02
4 0.9734509914831646 9.123e − 04
5 0.9734517659919923 7.745e − 07
6 0.9734517659925498 5.574e − 13
7 0.9734517659925498 0.000e + 00
⇒ Usando este método precisamos de apenas 6 iterações!
Realmente a convergência é muito rápida.
⇒ Praticamente a cada iteração o número de casas decimais
exatas é dobrado.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Vantagens e desvantagens do método de Newton
O método pode ser generalizado para o caso de sistemas de
equações (não lineares).
Em geral, converge muito rapidamente quando a aproximação
inicial é boa.
A função deve ser duas vezes diferenciável.
É preciso calcular a primeira derivada da função em cada
iteração, se o cálculo for muito complicado podemos perder
em eficiência computacional.
Na prática, se f ′(c) for muito pequena podemos ter
problemas de convergência e precisão.
⇒ Nas aplicações podemos obter um bom chute inicial, fazendo
algumas iterações preliminares pelo método da bissecção.
⇒ O método pode ser modificado para se evitar o cálculo da
primeira derivada.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Parte IV
Método da secante
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Metodo da secante
Substituindo no método de Newton a aproximação
f ′(pn) ≈ f (pn)−f (pn−1)pn−pn−1 para a derivada, chegamos no Método da
secante
pn+1 = pn −
f (pn)(pn − pn−1)
f (pn)− f (pn−1)
, n ≥ 1.
Para iniciar as iterações precisamos de duas aproximações
iniciais p0 e p1.
Não é um método do tipo ponto fixo.
Converge um pouco mais devagar que o método de Newton.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Interpretação geométrica
A interseção com o eixo x da reta secante à curva y = f (x)
passando pelos pontos (pn−1, f (pn−1)) e (pn, f (pn)), nos dá a nova
aproximação pn+1.
-0.25 0 0.25 0.5 0.75 1 1.25
-0.75
-0.5
-0.25
0.25
0.5
p0 p1
p2
p3
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Algoritmo: Método da secante
Aproxima um zero de f a partir das aproximações iniciais p0 e p1.
Entradas: p0 e p1 (aproximações iniciais); tol (tolerância); Niter
(número máximo de iterações)
Sáıda: p (valor aproximado) ou mensagem de erro
1 Faça k = 1
2 Enquanto k ≤ Niter , execute os passos 3–6
3 Faça p = p1 − f (p1)(p1 − p0)/(f (p1)− f (p0))
4 Se |p − p1| < tol , então
SAIDA: p; PARE
5 Faça p0 = p1, p1 = p
6 Faça k = k + 1
7 SAIDA: ‘o método falhou após Niter iterações’; FIM
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Convergência do método da secante
Teorema 7 [Convergência do método da secante]
Seja f uma função com duas derivadas cont́ınuas no intervalo
[a, b]. Suponha que c ∈ (a, b) é um zero de f tal que f ′(c) 6= 0.
Então existe δ > 0 tal que para quaisquer chutes iniciais p0 e p1 no
intervalo [c − δ, c + δ] a sequência pn definida por
pn+1 = pn −
f (pn)(pn − pn−1)
f (pn)− f (pn−1)
, n ≥ 1
converge para c .
Observação
A convergência do método está garantida localmente, ou seja as
aproximações iniciais devem ser suficientemente boas.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista
Lembramos que temos que resolver a equação
f (x) = 10− 9, 81
x
(
1− e−5x
)
= 0.
Assim o método da secante fica na forma
pn+1 = pn −
(pn − pn−1)
(
10− 9,81pn
(
1− e−5pn
))
9,81
pn−1
(1− e−5pn−1)− 9,81pn (1− e
−5pn)
, n ≥ 1.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista (cont.)
Consideramos �tol = 10
−16, p0 = 0.5 e p1 = 1.5
n (iteração) pn (aproximação) |pn − pn−1| (erro)
0 0.5 −−
1 1.5 −−
2 1.1981099873448335 3.019e − 01
3 0.8589113540130435 3.392e − 01
4 0.9974737928975070 1.386e − 01
5 0.9759880456381438 2.149e − 02
6 0.9733950369357137 2.593e − 03
7 0.9734518997149746 5.686e − 05
8 0.9734517659995986 1.337e − 07
9 0.9734517659925496 7.049e − 12
10 0.9734517659925498 2.220e − 16
11 0.9734517659925498 0.000e + 00
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Exemplo: Queda livre do paraquedista (cont.)
Observações:
⇒ Usando este método precisamos de 9 iterações para chegar
no resultado.
⇒ Se comporta um pouco pior que o método de Newton mas
ainda melhor que o método do ponto fixo.
⇒ Praticamente a cada iteração o número de casas decimais
exatas cresce mais ou menos em 50%.
Como podemos comparar os métodos estudados de uma forma
mais geral e quantitativa?
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Parte V
Ordem de convergência
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Ordem de convergência
É uma forma de medir a eficiência do método avaliando o quanto
as aproximações melhoram a cada iteração realizada.
Definição de ordem de convergência
Considere uma sequênciade números pn (n ≥ 0) que converge
para c e tal que pn 6= c .
A sequência tem ordem de convergência q = 1, se
lim
n→∞
|c − pn+1|
|c − pn|
= C1, com 0 < C1 < 1.
A tem ordem de convergência q > 1, se
lim
n→∞
|c − pn+1|
|c − pn|q
= Cq, com Cq > 0.
A constante Cq é chamada de constante assintótica do erro.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Ordem de convergência (cont.)
Observações:
⇒ Se as sequências geradas por um determinado método, em
geral, possuem ordem de convergência q então dizemos que o
método converge com ordem q.
⇒ No caso q = 1, dizemos que o método (a sequência) converge
linearmente, e se q = 2 falamos em convergência quadrática.
⇒ Se limn→∞ |c−pn+1||c−pn|q = 0, dizemos que a ordem de
convergência é melhor do que q.
⇒ Para n grande temos que
|c − pn+1|
|c − pn|q
≈ Cq ⇒ log(|c − pn+1|) ≈ q log(|c − pn|) + logCq,
em uma escala logaŕıtmica o gráfico se aproxima de uma reta! (Ou
seja, os pontos (log(|c − pn|)), log(|c − pn+1|) se aproximam de
uma reta.) A inclinação da reta é dada pela ordem q.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Comportamento do erro
Gráfico dos erros (em escala logaŕıtmica), usando os métodos do
ponto fixo, de Newton e da secante, quando resolvemos o
problema da queda livre do paraquedista.
Compare a inclinação das retas para cada método.
10−20 10−15 10−10 10−5 100
10−16
10−14
10−12
10−10
10−8
10−6
10−4
10−2
100
|c−pn|
|c
−p
n+
1|
 
 
M. secante
M. ponto fixo
M. Newton
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Ordem de convergência teórica
O resutado observado corresponde ao seguinte teorema.
Teorema [sobre a ordem de convergência]
O método do ponto fixo pn+1 = g(pn) converge linearmente
com a constante assintôtica C1 = |g ′(c)| onde c é o ponto
fixo de g .
O método de Newton pn+1 = pn − f (pn)/f ′(pn) possui
convergência quadrática (q = 2) com a constante assintótica
C2 =
|f ′′(c)|
2|f ′(c)| onde c é o zero de f .
O método da secante
pn+1 = pn − f (pn)(pn − pn−1)/(f (pn)− f (pn−1) tem ordem
de convergência q = 1+
√
5
2 ≈ 1.618.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Conclusões
O método da bissecção é o mais simples de todos os métodos
estudados e funciona sob condições bastante gerais.
Os outros métodos (do ponto fixo, de Newton e da secante)
precisam de funções regulares (diferenciáveis), apresentam
restrições nas derivadas para garantir a convergência e
convergem apenas localmente (ou seja, precisam de boas
aproximações iniciais).
O método de Newton possui ordem de convergência
quadrática, superando em velocidade aos outros métodos.
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações
Em uma Galáxia muito distante ...
D.G. Alfaro – www.dcc.ufrj.br/∼dgalfaro Solução aproximada de equações