Método do Ponto Fixo - Parte II, Método de Newton Raphson, Método das Secantes, Método da Posição Falsa

Prévia do material em texto

Me´todo do Ponto Fixo - Parte II
Me´todo de Newton-Raphson
Me´todo das Secantes
Me´todo da Posic¸a˜o Falsa
Ca´lculo Nume´rico - Turma D - Semana 3
29 de Marc¸o de 2016
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 1 / 32
Suma´rio da Aula
1 Erro de aproximac¸a˜o no MPF
2 Me´todo de Newton ou das Tangentes
3 Me´todo das Secantes e Me´todo da Posic¸a˜o Falsa
4 Convergeˆncia do Me´todo de Newton-Raphson
5 To´picos Especiais
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 2 / 32
Erro de aproximac¸a˜o no MPF
No encontro anterior, listamos condic¸o˜es para que o MPF convergisse:
Teorema 1
Seja c uma raiz isolada de f (x) = 0 no intervalo I = [a, b] e seja g tal que
g(c) = c . Suponha que
a g e g ′ sa˜o cont´ınuas em I ;
b |g ′(x)| ≤ k < 1 para algum k
c x0 ∈ I e para todo n, xn+1 = g(xn) ∈ I
Enta˜o a sequeˆncia {xn}∞n=0 converge para c
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 3 / 32
Como consequeˆncia, temos o:
Corola´rio 1
Sob as condic¸o˜es do teorema anterior, se c e´ o ponto fixo de g em
I = [a, b], enta˜o o erro ao aproximar c por xn e´ limitado por
(i) |xn − c| ≤ knmax{x0 − a, b − x0}
(ii) |xn − c| ≤ kn1−k |x1 − x0|
Demonstrac¸a˜o (i). Segue-se do teorema anterior:
|xn − c | ≤ k|xn−1 − c | ≤ k2|xn−2 − c | ≤ . . . ≤ kn|x0 − c|
Temos c ∈ I , e e´ claro que |x0 − c | ≤ max{|x0 − a|, |x0 − b|}. Assim:
|xn − c | ≤ kn|x0 − c | ≤ knmax{|x0 − a|, |x0 − b|}
�
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 4 / 32
Como consequeˆncia, temos o:
Corola´rio 1
Sob as condic¸o˜es do teorema anterior, se c e´ o ponto fixo de g em
I = [a, b], enta˜o o erro ao aproximar c por xn e´ limitado por
(i) |xn − c| ≤ knmax{x0 − a, b − x0}
(ii) |xn − c| ≤ kn1−k |x1 − x0|
Demonstrac¸a˜o (i). Segue-se do teorema anterior:
|xn − c | ≤ k|xn−1 − c | ≤ k2|xn−2 − c | ≤ . . . ≤ kn|x0 − c|
Temos c ∈ I , e e´ claro que |x0 − c | ≤ max{|x0 − a|, |x0 − b|}. Assim:
|xn − c | ≤ kn|x0 − c | ≤ knmax{|x0 − a|, |x0 − b|}
�
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 4 / 32
Demonstrac¸a˜o (ii). Repita o procedimento usado para |xn − c | no
Teorema agora para |xn+1 − xn|:
|xn+1 − xn| ≤ |g(xn)− g(xn+1)|︸ ︷︷ ︸
definic¸a˜o
≤ k |xn − xn−1| ≤ . . . ≤ kn|x1 − x0|
Para m > n ≥ 1 podemos escrever
|xm − xn| = |xm + (xm−1 − xm−1)︸ ︷︷ ︸
0
+ . . .+ (xn+1 − xn+1)︸ ︷︷ ︸
0
−xn|
= |(xm − xm−1) + (xm−1 − xm−2) + . . .+ (xn+1 − xn)|
Agora, observamos a desigualdade triangular generalizada
|a1 + a2 + . . .+ an| ≤ |a1|+ |a2|+ . . .+ |an|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 5 / 32
Demonstrac¸a˜o (ii). Repita o procedimento usado para |xn − c | no
Teorema agora para |xn+1 − xn|:
|xn+1 − xn| ≤ |g(xn)− g(xn+1)|︸ ︷︷ ︸
definic¸a˜o
≤ k |xn − xn−1| ≤ . . . ≤ kn|x1 − x0|
Para m > n ≥ 1 podemos escrever
|xm − xn| = |xm + (xm−1 − xm−1)︸ ︷︷ ︸
0
+ . . .+ (xn+1 − xn+1)︸ ︷︷ ︸
0
−xn|
= |(xm − xm−1) + (xm−1 − xm−2) + . . .+ (xn+1 − xn)|
Agora, observamos a desigualdade triangular generalizada
|a1 + a2 + . . .+ an| ≤ |a1|+ |a2|+ . . .+ |an|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 5 / 32
Demonstrac¸a˜o (ii). Repita o procedimento usado para |xn − c | no
Teorema agora para |xn+1 − xn|:
|xn+1 − xn| ≤ |g(xn)− g(xn+1)|︸ ︷︷ ︸
definic¸a˜o
≤ k |xn − xn−1| ≤ . . . ≤ kn|x1 − x0|
Para m > n ≥ 1 podemos escrever
|xm − xn| = |xm + (xm−1 − xm−1)︸ ︷︷ ︸
0
+ . . .+ (xn+1 − xn+1)︸ ︷︷ ︸
0
−xn|
= |(xm − xm−1) + (xm−1 − xm−2) + . . .+ (xn+1 − xn)|
Agora, observamos a desigualdade triangular generalizada
|a1 + a2 + . . .+ an| ≤ |a1|+ |a2|+ . . .+ |an|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 5 / 32
E obtemos
|xm − xn| ≤ |xm − xm−1|+ |xm−1 − xm−2|+ . . .+ |xn+1 − xn|
Para qualquer q ≥ 1 temos |xq − xq−1| ≤ kq−1|x1 − x0| donde
|xm − xn| ≤ km−1|x1 − x0|+ km−2|x1 − x0|+ . . .+ kn|x1 − x0|
≤ kn|x1 − x0| (km−n−1 + km−n−2 + . . .+ k + 1)︸ ︷︷ ︸∑m−n−1
i=0 k
i
E´ sabido que lim xm = c quando m→∞ enta˜o lim|c − xm| = 0 e como
|xm − xn| = |(xm − c) + (c − xn)|
temos que |c − xn| = lim
m→∞ |xm − xn|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 6 / 32
E obtemos
|xm − xn| ≤ |xm − xm−1|+ |xm−1 − xm−2|+ . . .+ |xn+1 − xn|
Para qualquer q ≥ 1 temos |xq − xq−1| ≤ kq−1|x1 − x0| donde
|xm − xn| ≤ km−1|x1 − x0|+ km−2|x1 − x0|+ . . .+ kn|x1 − x0|
≤ kn|x1 − x0| (km−n−1 + km−n−2 + . . .+ k + 1)︸ ︷︷ ︸∑m−n−1
i=0 k
i
E´ sabido que lim xm = c quando m→∞ enta˜o lim|c − xm| = 0 e como
|xm − xn| = |(xm − c) + (c − xn)|
temos que |c − xn| = lim
m→∞ |xm − xn|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 6 / 32
E obtemos
|xm − xn| ≤ |xm − xm−1|+ |xm−1 − xm−2|+ . . .+ |xn+1 − xn|
Para qualquer q ≥ 1 temos |xq − xq−1| ≤ kq−1|x1 − x0| donde
|xm − xn| ≤ km−1|x1 − x0|+ km−2|x1 − x0|+ . . .+ kn|x1 − x0|
≤ kn|x1 − x0| (km−n−1 + km−n−2 + . . .+ k + 1)︸ ︷︷ ︸∑m−n−1
i=0 k
i
E´ sabido que lim xm = c quando m→∞ enta˜o lim|c − xm| = 0 e como
|xm − xn| = |(xm − c) + (c − xn)|
temos que |c − xn| = lim
m→∞ |xm − xn|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 6 / 32
E obtemos
|xm − xn| ≤ |xm − xm−1|+ |xm−1 − xm−2|+ . . .+ |xn+1 − xn|
Para qualquer q ≥ 1 temos |xq − xq−1| ≤ kq−1|x1 − x0| donde
|xm − xn| ≤ km−1|x1 − x0|+ km−2|x1 − x0|+ . . .+ kn|x1 − x0|
≤ kn|x1 − x0| (km−n−1 + km−n−2 + . . .+ k + 1)︸ ︷︷ ︸∑m−n−1
i=0 k
i
E´ sabido que lim xm = c quando m→∞ enta˜o lim|c − xm| = 0 e como
|xm − xn| = |(xm − c) + (c − xn)|
temos que |c − xn| = lim
m→∞ |xm − xn|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 6 / 32
Enta˜o,
|c − xn| = lim
m→∞ |xm − xn| ≤ limm→∞ k
n|x1 − x0|
m−n−1∑
i=0
k i
≤ kn|x1 − x0|
∞∑
i=0
k i
Agora,
∑∞
i=0 k
i e´ a soma infinita dos termos de uma PG com raza˜o k < 1,
donde
∞∑
i=0
k i =
1
1− k o que implica que
|xn − c | ≤ k
n
1− k |p1 − p0|
�
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 7 / 32
Concluso˜es do Corola´rio:
|xn − c | ≤ k
n
1− k |p1 − p0|
implica que
Quanto menor for k menos iterac¸o˜es sa˜o necessa´rias para aproximar
xn de c .
Para uma dada precisa˜o ε e´ possivel estimar o nu´mero m´ınimo de
iterac¸o˜es para atingi-la, fazendo-se
kn
1− k |p1 − p0| < ε ou k
nmax{x0 − a, b − x0} ≤ ε
Nos exemplos |g ′1(x)| ≤ 0, 84 e |g ′3(x)| ≤ 0, 79 e g3 convergiu mais
rapidamente.Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 8 / 32
Concluso˜es do Corola´rio:
|xn − c | ≤ k
n
1− k |p1 − p0|
implica que
Quanto menor for k menos iterac¸o˜es sa˜o necessa´rias para aproximar
xn de c .
Para uma dada precisa˜o ε e´ possivel estimar o nu´mero m´ınimo de
iterac¸o˜es para atingi-la, fazendo-se
kn
1− k |p1 − p0| < ε ou k
nmax{x0 − a, b − x0} ≤ ε
Nos exemplos |g ′1(x)| ≤ 0, 84 e |g ′3(x)| ≤ 0, 79 e g3 convergiu mais
rapidamente.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 8 / 32
Concluso˜es do Corola´rio:
|xn − c | ≤ k
n
1− k |p1 − p0|
implica que
Quanto menor for k menos iterac¸o˜es sa˜o necessa´rias para aproximar
xn de c .
Para uma dada precisa˜o ε e´ possivel estimar o nu´mero m´ınimo de
iterac¸o˜es para atingi-la, fazendo-se
kn
1− k |p1 − p0| < ε ou k
nmax{x0 − a, b − x0} ≤ ε
Nos exemplos |g ′1(x)| ≤ 0, 84 e |g ′3(x)| ≤ 0, 79 e g3 convergiu mais
rapidamente.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 8 / 32
Me´todo de Newton-Raphson ou das Tangentes
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 9 / 32
Motivac¸a˜o Geome´trica
Suponha que f tem uma raiz c de f (x) = 0 num intervalo I.
Se f for deriva´vel em I , enta˜o existe reta tangente Tx ao gra´fico de f
para todo x ∈ I
Dado x0 ∈ I , e´ poss´ıvel que a reta tangente Tx0 perfure o eixo x , de
modo que o ponto de intersec¸a˜o x1 fique pro´ximo de c
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 10 / 32
Motivac¸a˜o Geome´trica
Suponha que f tem uma raiz c de f (x) = 0 num intervalo I.
Se f for deriva´vel em I , enta˜o existe reta tangente Tx ao gra´fico de f
para todo x ∈ I
Dado x0 ∈ I , e´ poss´ıvel que a reta tangente Tx0 perfure o eixo x , de
modo que o ponto de intersec¸a˜o x1 fique pro´ximo de c
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 10 / 32
A equac¸a˜o da reta tangente Tx0 e´
y − f (x0) = f ′(x0)(x − x0)
O ponto de intersec¸a˜o x1 com o eixo x e´ obtido fazendo-se y = 0 acima,
donde
0− f (x0) = f ′(x0)(x1 − x0) =⇒ x1 = x0 − f (x0)
f ′(x0)
Se repetirmos o racioc´ınio para x1 teremos que
x2 = x1 − f (x1)
f ′(x1)
De modo que, no caso geral:
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 11 / 32
A equac¸a˜o da reta tangente Tx0 e´
y − f (x0) = f ′(x0)(x − x0)
O ponto de intersec¸a˜o x1 com o eixo x e´ obtido fazendo-se y = 0 acima,
donde
0− f (x0) = f ′(x0)(x1 − x0) =⇒ x1 = x0 − f (x0)
f ′(x0)
Se repetirmos o racioc´ınio para x1 teremos que
x2 = x1 − f (x1)
f ′(x1)
De modo que, no caso geral:
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 11 / 32
A equac¸a˜o da reta tangente Tx0 e´
y − f (x0) = f ′(x0)(x − x0)
O ponto de intersec¸a˜o x1 com o eixo x e´ obtido fazendo-se y = 0 acima,
donde
0− f (x0) = f ′(x0)(x1 − x0) =⇒ x1 = x0 − f (x0)
f ′(x0)
Se repetirmos o racioc´ınio para x1 teremos que
x2 = x1 − f (x1)
f ′(x1)
De modo que, no caso geral:
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 11 / 32
A equac¸a˜o da reta tangente Tx0 e´
y − f (x0) = f ′(x0)(x − x0)
O ponto de intersec¸a˜o x1 com o eixo x e´ obtido fazendo-se y = 0 acima,
donde
0− f (x0) = f ′(x0)(x1 − x0) =⇒ x1 = x0 − f (x0)
f ′(x0)
Se repetirmos o racioc´ınio para x1 teremos que
x2 = x1 − f (x1)
f ′(x1)
De modo que, no caso geral:
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 11 / 32
xn+1 = xn − f (xn)
f ′(xn)
Assim, registramos:
Definic¸a˜o 1
O Me´todo de Newton produz uma sequeˆncia {xn}∞k=0 definida por
x0 = tentativa inicial
xn+1 = xn − f (xn)
f ′(xn)
para todo n ≥ 1, onde xn e´ a aproximac¸a˜o para c na n-e´sima iterac¸a˜o
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 12 / 32
xn+1 = xn − f (xn)
f ′(xn)
Assim, registramos:
Definic¸a˜o 1
O Me´todo de Newton produz uma sequeˆncia {xn}∞k=0 definida por
x0 = tentativa inicial
xn+1 = xn − f (xn)
f ′(xn)
para todo n ≥ 1, onde xn e´ a aproximac¸a˜o para c na n-e´sima iterac¸a˜o
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 12 / 32
Exemplo: Calcular a raiz de f (x) = cosx − x usando x0 = pi4 com o
(a) Me´todo do Ponto Fixo (b) Me´todo de Newton.
(a) Podemos escolher g(x) = cos x como func¸a˜o auxiliar. Com
x0 =
pi
4
∼= 0.7853981635, o resultado esta´ listado abaixo a` esquerda.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 13 / 32
(b) Com f (x) = cos x − x , vamos precisar de f ′(x) = − sin x − 1. A
sequeˆncia iterativa sera´
xn+1 = xn − f (xn)
f ′(xn)
⇒ xn+1 = xn − cos(xn)− xn− sin(xn)− 1
Por exemplo:
x1 = x0− cos(x0)− x0− sin(x0)− 1 = 0, 7853981635−
cos(0, 7853981635)− 0, 7853981635
− sin(0, 7853981635)− 1
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 14 / 32
Me´todo das Secantes e Me´todo da Posic¸a˜o Falsa
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 15 / 32
Motivac¸a˜o Geome´trica
O Me´todo das Secantes e´ inspirado no Me´todo de Newton, pore´m a
intersec¸a˜o com o eixo x e´ dada por retas secantes, ao inve´s de tangentes
Suponha que f tem uma raiz c ∈ I . Escolha x0 e x1 em I . A reta secante
que liga os pontos (x0, f (x0)) e (x1, f (x1)) interceptara´ o eixo x em x = x2
que deve ser um valor pro´ximo de c
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 16 / 32
Motivac¸a˜o Geome´trica
O Me´todo das Secantes e´ inspirado no Me´todo de Newton, pore´m a
intersec¸a˜o com o eixo x e´ dada por retas secantes, ao inve´s de tangentes
Suponha que f tem uma raiz c ∈ I . Escolha x0 e x1 em I . A reta secante
que liga os pontos (x0, f (x0)) e (x1, f (x1)) interceptara´ o eixo x em x = x2
que deve ser um valor pro´ximo de c
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 16 / 32
Descric¸a˜o do me´todo.
Para xn−1 temos, por definic¸a˜o
f ′(xn−1) = lim
x→xn−1
f (x)− f (xn−1)
x − xn−1
que e´ o coeficiente angular da reta tangente Txn−1
Quando xn−1 esta´ proximo de xn−2 o coeficiente de Txn−1e´
aproximadamente o coeficiente da reta secante que liga os pontos
(xn−1, f (xn−1)) e (xn−2, f (xn−2)) .
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 17 / 32
Descric¸a˜o do me´todo.
Para xn−1 temos, por definic¸a˜o
f ′(xn−1) = lim
x→xn−1
f (x)− f (xn−1)
x − xn−1
que e´ o coeficiente angular da reta tangente Txn−1
Quando xn−1 esta´ proximo de xn−2 o coeficiente de Txn−1 e´
aproximadamente o coeficiente da reta secante que liga os pontos
(xn−1, f (xn−1)) e (xn−2, f (xn−2)) .
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 17 / 32
Enta˜o podemos aproximar
f ′(xn−1) ∼= f (xn−1)− f (xn−2)
xn−1 − xn−2
E substituir na iterac¸a˜o de Newton, obtendo
xn = xn−1 − f (xn−1)(xn−1 − xn−2)
f (xn−1)− f (xn−2)
para todo n ≥ 2.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 18 / 32
Enta˜o podemos aproximar
f ′(xn−1) ∼= f (xn−1)− f (xn−2)
xn−1 − xn−2
E substituir na iterac¸a˜o de Newton, obtendo
xn = xn−1 − f (xn−1)(xn−1 − xn−2)
f (xn−1)− f (xn−2)
para todo n ≥ 2.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 18 / 32
Enta˜o podemos aproximar
f ′(xn−1) ∼= f (xn−1)− f (xn−2)
xn−1 − xn−2
E substituir na iterac¸a˜o de Newton, obtendo
xn = xn−1 − f (xn−1)(xn−1 − xn−2)
f (xn−1)− f (xn−2)
para todo n ≥ 2.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 18 / 32
Definic¸a˜o 2
O Me´todo das Secantes produz uma sequeˆncia {xn}∞n=0 definida por
x0, x1 = tentativas iniciais
xn = xn−1 − f (xn−1)(xn−1 − xn−2)
f (xn−1)− f (xn−2)
para todo n ≥ 1, onde xn e´ a aproximac¸a˜o para a raiz c na n-e´sima
iterac¸a˜o
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 19 / 32
Me´todo da Posic¸a˜o Falsa ou Regula Falsi
Semelhante ao Me´todo da Bissec¸a˜o, contudo, o ponto me´dio ck de cada
iterac¸a˜o e´ determinado pelo Me´todo das Secantes. Essa combinac¸a˜o
garante que a raiz sempre esteja entre iteradas sucessivas.
Definic¸a˜o 3
Dado o intervalo [a, b] tal que f (a)f (b) < 0. O Me´todo da Posic¸a˜o
Falsa produz uma sequeˆncia {cn}∞n=0, com
cn = bn − f (bn)(bn − an)
f (bn)− f (an) =
bnf (an)− anf (bn)
f (an)− f (bn)
onde [an, bn] e´ escolhido atrave´s do Me´todo da Bissec¸a˜o.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 20 / 32
Algoritmo 2. Me´todo Regula Falsi
ENTRADAS: x0, x1 - aproximac¸o˜es iniciais; TOL - toleraˆncia; N0 - nu´mero
ma´ximo de iterac¸o˜es
SAIDA: Aproximac¸a˜o da raiz xn ou mensagem de erro
Passo 1 i := 2;
q0 = f (x0);
q1 = f (x1);
Passo 2 Enquanto i ≤ N0, fac¸a Passo 3 ate´ Passo 7
Passo 3 c := x1 − q1(x1 − x0)/(q1 − q0);
Passo 4 Se |c − x1| < TOL enta˜o
Escreva(xn);
Pare.
Passo 5 i := i + 1; q := f (c);
Passo 6 Se q · q1 < 0 enta˜o x0 := x1; q0 := q1
Passo 7 x1 := c ; q1 := q
Passo 8 Escreva(”Processamento encerrado apo´s n0=”, n0, ”interac¸o˜es”); FIM.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 21 / 32
Exemplo Use o Me´todo da Posic¸a˜o Falsa para encontrar a raiz de
f (x) = x sin x − 1 = 0 no intervalo [0, 2]
O Regula Falsi e´ similar ao Me´todo da Bissec¸a˜o. Comec¸amos com a0 = 0
e b0 = 2, pois
f (a0) = −1 < 0 e f (b0) = 0, 81849485 > 0
Por sua vez, o ponto me´dio c0 e´ escolhico pelo Me´todo das Secantes:
c0 = b0 − f (a0)(b0 − a0)
f (b0)− f (a0)
c0 = 2− −1(2− 0)
0, 81849485− (−1) = 1, 09975017
Ale´m disso f (c0) = −0, 02001921 < 0, o que implica que a1 := c0 e
b1 := b0.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 22 / 32
A aplicac¸a˜o final do me´todo deve resultar na tabela abaixo:
n an f (an) bn f (bn) cn f (cn)
0 0 (-) 2 (+) 1,09975017 (-)0,02001921
1 1,09975017 (-) 2 (+) 1,12124074 (+)0,0983461
2 1,09975017 (-) 1,12124074 (+) 1,11416120 (+)0,00983461
3 1,09975017 (-) 1,11416120 (+) 1,11415714 (+)0,00000000
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 23 / 32
Convergeˆncia do Me´todo de Newton
Teorema 2 (Teorema de Newton-Raphson)
Suponha que f tenha uma raiz c ∈ I = [a, b] e que f ′ e f ′′ sa˜o cont´ınuas
em I . Se f ′(c) 6= 0, enta˜o existe δ > 0 tal que a sequencia {xn}∞n=0
definida pela iterac¸a˜o
xn = g(xn−1) = xn−1 − f (xn−1)
f ′(xn−1)
para n = 1, 2, . . .
converge para c para qualquer valor inicial x0, desde que x0 ∈ [c − δ, c + δ]
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 24 / 32
Estrate´gia da demonstrac¸a˜o: Garantir que a func¸a˜o auxiliar g = g(x)
na iterac¸a˜o xn = g(xn−1) = xn−1 − f (xn−1)f ′(xn−1) satisfaz as condic¸o˜es de
convergeˆncia do MPF em algum intervalo [c − δ, c + δ] ao redor de c . Ou
seja:
g e g ′ cont´ınuas em [c − δ, c + δ]
|g ′(x)| ≤ k < 1 para x ∈ [c − δ, c + δ]
xn = g(xn−1) ∈ [c − δ, c + δ] para todo n
Continuidade de g e g ′ em I . Temos que estudar a func¸a˜o
g(x) = x − f (x)
f ′(x)
que e´ cont´ınua, desde que f ′(x) 6= 0, pois, por hipo´tese, f ′ e´ cont´ınua em
I . Ale´m disso, g(c) = c , implicando que Me´todo de Newton reduz-se a
encontrar o ponto fixo c de g .
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 25 / 32
Estrate´gia da demonstrac¸a˜o: Garantir que a func¸a˜o auxiliar g = g(x)
na iterac¸a˜o xn = g(xn−1) = xn−1 − f (xn−1)f ′(xn−1) satisfaz as condic¸o˜es de
convergeˆncia do MPF em algum intervalo [c − δ, c + δ] ao redor de c . Ou
seja:
g e g ′ cont´ınuas em [c − δ, c + δ]
|g ′(x)| ≤ k < 1 para x ∈ [c − δ, c + δ]
xn = g(xn−1) ∈ [c − δ, c + δ] para todo n
Continuidade de g e g ′ em I . Temos que estudar a func¸a˜o
g(x) = x − f (x)
f ′(x)
que e´ cont´ınua, desde que f ′(x) 6= 0, pois, por hipo´tese, f ′ e´ cont´ınua em
I . Ale´m disso, g(c) = c , implicando que Me´todo de Newton reduz-se a
encontrar o ponto fixo c de g .
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 25 / 32
Agora
g ′(x) = 1− f
′(x)f ′(x)− f (x)f ′′(x)
(f ′(x))2
=
f (x)f ′′(x)
(f ′(x))2
e´ cont´ınua, desde que f ′(x) 6= 0, pois f ′ e f ′′(x) tambe´m sa˜o cont´ınuas em
I
Existeˆncia de k < 1 e δ > 0. Por hipo´tese, f (c) = 0 e assim g ′(c) = 0
na equac¸a˜o acima. Certamente, f na˜o e´ uma func¸a˜o constante, e
portanto, g ′ na˜o pode ser totalmente nula em I .
Logo, pro´ximos de c teremos 0 6= g ′(x) ∼= 0.
Em outras palavras, existem δ > 0 e k < 1 tais que
|g ′(x)| < k < 1
para todo x ∈ [c − δ, c + δ]
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 26 / 32
Agorag ′(x) = 1− f
′(x)f ′(x)− f (x)f ′′(x)
(f ′(x))2
=
f (x)f ′′(x)
(f ′(x))2
e´ cont´ınua, desde que f ′(x) 6= 0, pois f ′ e f ′′(x) tambe´m sa˜o cont´ınuas em
I
Existeˆncia de k < 1 e δ > 0. Por hipo´tese, f (c) = 0 e assim g ′(c) = 0
na equac¸a˜o acima. Certamente, f na˜o e´ uma func¸a˜o constante, e
portanto, g ′ na˜o pode ser totalmente nula em I .
Logo, pro´ximos de c teremos 0 6= g ′(x) ∼= 0.
Em outras palavras, existem δ > 0 e k < 1 tais que
|g ′(x)| < k < 1
para todo x ∈ [c − δ, c + δ]
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 26 / 32
Agora
g ′(x) = 1− f
′(x)f ′(x)− f (x)f ′′(x)
(f ′(x))2
=
f (x)f ′′(x)
(f ′(x))2
e´ cont´ınua, desde que f ′(x) 6= 0, pois f ′ e f ′′(x) tambe´m sa˜o cont´ınuas em
I
Existeˆncia de k < 1 e δ > 0. Por hipo´tese, f (c) = 0 e assim g ′(c) = 0
na equac¸a˜o acima. Certamente, f na˜o e´ uma func¸a˜o constante, e
portanto, g ′ na˜o pode ser totalmente nula em I .
Logo, pro´ximos de c teremos 0 6= g ′(x) ∼= 0.
Em outras palavras, existem δ > 0 e k < 1 tais que
|g ′(x)| < k < 1
para todo x ∈ [c − δ, c + δ]
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 26 / 32
Agora
g ′(x) = 1− f
′(x)f ′(x)− f (x)f ′′(x)
(f ′(x))2
=
f (x)f ′′(x)
(f ′(x))2
e´ cont´ınua, desde que f ′(x) 6= 0, pois f ′ e f ′′(x) tambe´m sa˜o cont´ınuas em
I
Existeˆncia de k < 1 e δ > 0. Por hipo´tese, f (c) = 0 e assim g ′(c) = 0
na equac¸a˜o acima. Certamente, f na˜o e´ uma func¸a˜o constante, e
portanto, g ′ na˜o pode ser totalmente nula em I .
Logo, pro´ximos de c teremos 0 6= g ′(x) ∼= 0.
Em outras palavras, existem δ > 0 e k < 1 tais que
|g ′(x)| < k < 1
para todo x ∈ [c − δ, c + δ]
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 26 / 32
g leva [c − δ, c + δ] para [c − δ, c + δ] Aqui verificaremos que dado
x ∈ [c − δ, c + δ], teremos g(x) ∈ [c − δ, c + δ]. Primeiro:
x ∈ [c − δ, c + δ]⇔ |x − p| ≤ δ
Enta˜o, temos que garantir que
|g(x)− c| ≤ δ
pois isso implica que g(x) ∈ [c − δ, c + δ].
Temos, g(c) = c e da´ı
|g(x)− c | = |g(x)− g(c)|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 27 / 32
g leva [c − δ, c + δ] para [c − δ, c + δ] Aqui verificaremos que dado
x ∈ [c − δ, c + δ], teremos g(x) ∈ [c − δ, c + δ]. Primeiro:
x ∈ [c − δ, c + δ]⇔ |x − p| ≤ δ
Enta˜o, temos que garantir que
|g(x)− c| ≤ δ
pois isso implica que g(x) ∈ [c − δ, c + δ]. Temos, g(c) = c e da´ı
|g(x)− c | = |g(x)− g(c)|
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 27 / 32
Pelo TVM, existe ξ ∈ (c, x) ou ξ ∈ (x , c) tal que:
|g(x)− g(c)| = |g ′(ξ)||x − c| ≤ k |x − c | < |x − c|︸ ︷︷ ︸
k<1
Como |g(x)− c| ≤ |x − c | ≤ δ, temos que
g(x) ∈ [c − δ, c + δ]
para todo x ∈ [c − δ, c + δ], o que encerra a demonstrac¸a˜o. �
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 28 / 32
To´picos Especiais
1. Velocidade de Convergeˆncia. Dado um me´todo iterativo {xn}∞n=0
que converge para uma raiz c de f (x) = 0. Para cada n, considere o erro
En = xn − c
Definic¸a˜o 4
Se existirem constantes A > 0 e R > 0 tais que
lim
n→∞
|xn+1 − c |
|xn − c |R limn→∞
|En+1|
|En|R = A
Dizemos que a {xn}∞n=1} converge para c com raio de convergeˆncia R e
erro assinto´tico A.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 29 / 32
Em particular, Se R = 1 dizemos que a convergeˆncia e´ linear
Se R = 2 dizemos que a convergeˆncia e´ quadra´tica
Se c e´ uma raiz simples de f , isto e´, f (c) = 0 mas f ′(c) 6= 0, podemos
demonstrar as sequintes relac¸o˜es
Me´todo Relac¸a˜o entre erros Convergeˆncia
Bissec¸a˜o |En+1| ∼= 12 |En| R = 1 (Linear)
Ponto Fixo |En+1| ∼= A|En| R = 1 (Linear)
Regula Falsi |En+1| ∼= A|En| R = 1 (Linear)
Secantes |En+1| ∼= A|En|1,618 R ∼= 1, 618
Newton-Raphson |En+1| ∼= A|En|2 R = 2 (quadra´tica)
Observac¸a˜o: Se a raiz c tem multiplicidade M enta˜o tanto o Me´todo de
Newton quanto o das Secantes convergem linearmente.
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 30 / 32
Podemos estabelecer os valores da taxa de convergeˆncia A:
Me´todo do Ponto Fixo
A = |g ′(c)|
Me´todo de Newton (raiz simples)
A =
|f ′′(c)|
2|f ′(c)|
Me´todo de Newton (raiz de multiplicidade M)
A =
M − 1
M
Me´todo das Secantes (raiz simples)
A =
∣∣∣∣ f ′′(c)2f ′(c)
∣∣∣∣0,618
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 31 / 32
Convergeˆncia linear do MPF para g(x) = x + cos x − sin x . Observe que c = pi4 e´
o ponto fixo e a taxa tende para A = |g ′(c)| = |1− sin(pi4 )− cos(pi4 )| ∼= 0, 414
Ca´lculo Nume´rico - Turma D - Semana 3 Me´todo do Ponto Fixo - Parte II Me´todo de Newton-Raphson Me´todo das Secantes Me´todo da Posic¸a˜o Falsa29 de Marc¸o de 2016 32 / 32
	Erro de aproximação no MPF
	Método de Newton ou das Tangentes
	Método das Secantes e Método da Posição Falsa
	Convergência do Método de Newton-Raphson
	Tópicos Especiais