Método de Newton-Raphson para Cálculo Numérico

Prévia do material em texto

GEX114 - Ca´lculo Nume´rico
Profa.Dra.Amanda Castro Oliveira
Departamento de Cieˆncias Exatas - DEX/UFLA
amanda@dex.ufla.br
Aula 10 - Cap.2- 2.4.4 Me´todo de Newton-Raphson-MNR
No estudo do MPF, vimos que:
i) uma das condic¸o˜es de convergeˆncia e´ que
|φ′(x)| ≤ M < 1 ∀x ∈ I , onde I = [a, b] e´ o
intervalo centrado na raiz;
ii) a convergeˆncia do me´todo sera´ mais ra´pida
quanto menor for |φ′(δ)|
lim
k→∞
ek+1
ek
= φ′(δ) = C , e |C | < 1 pois |φ′(x)| satisfaz a`s
hipo´teses do teorema 2.2.
2.4.4 Me´todo de Newton-Raphson-MNR
O me´todo de Newton-Raphson e´ um me´todo iterativo do tipo
MPF cujo objetivo e´ acelerar a convergeˆncia do MPF e para
isto ele:
Escolhe uma func¸a˜o de iterac¸a˜o |φ(x)| tal que |φ′(δ)| = 0.
Neste caso, para x ≈ δ, temos que |φ′(δ)| ≈ 0 e portanto
|φ′(x)| < 1 e a convergeˆncia e´ garantida.
Desde que |φ(x)| e |φ′(x)| sejam func¸o˜es cont´ınuas em I .
2.4.4 Me´todo de Newton-Raphson-MNR
Dada a equac¸a˜o f (x) = 0, partindo da forma geral para φ(x)
exigimos que φ′(δ) = 0 temos que:
φ(x) = x + A(x)f (x)⇒
enta˜o
φ′(x) = 1 + A′(x)f (x) + A(x)f ′(x)
φ′(δ) = 1 + A′(δ)f (δ) + A(δ)f ′(δ)
como f (δ) = 0
φ′(δ) = 1 + A(δ)f ′(δ)
Assim, φ′(δ) = 0⇔ 1 + A(δ)f ′(δ) = 0
A(δ) =
−1
f ′(δ)
.
Supondo que f ′(δ) 6= 0
2.4.4 Me´todo de Newton-Raphson-MNR
Logo, dada a equac¸a˜o f (x) = 0, a func¸a˜o de iterac¸a˜o do me´todo
de Newton-Raphson sera´:
φ(x) = x − f (x)
f ′(x)
que e´ tal que φ′(δ) = 0, pois
φ′(x) = 1− [f
′(x)]2 − f (x)f ′′(x)
[f ′(x)]2
=
f (x)f ′′(x)
[f ′(x)]2
e, como f (δ) = 0, φ′(δ) = 0(desde que f ′(δ) 6= 0).
2.4.4 Me´todo de Newton-Raphson-MNR
Assim, escolhido x0 adequadamente atrave´s dos me´todos da Fase
I, a sequeˆncia {xk} determinada por:
xk+1 = xk − f (xk)
f ′(xk)
,
com k = 0, 1, 2, · · · convergira´ para a raiz procurada δ.
2.4.4 Me´todo de Newton-Raphson-MNR- Interpretac¸a˜o
Geome´trica
2.4.4 Me´todo de Newton-Raphson-MNR- Interpretac¸a˜o
Geome´trica
Seja a curva f (x) e dado o ponto (xk , f (xk)) no plano
cartesiano, trac¸amos a reta Nk(x) tangente a` f (x) neste
ponto.
A equac¸a˜o desta reta e´ dada por:
Nk(x) = f (xk) + f
′(xk)(x − xk).
Nk(x) e´ uma aproximac¸a˜o linear para a func¸a˜o f (x) na
vizinhanc¸a de xk .
A aproximac¸a˜o para a raiz e´ o ponto em que esta reta Nk(x)
corta o eixo x .
Nk(x) = 0⇔ x = xk − f (xk)
f ′(xk)
fazemos xk+1 = x .
2.4.4 Me´todo de Newton-Raphson-MNR- Algoritmo
Considere a equac¸a˜o f (x) = 0, assegure-se de que f (x), f ′(x) e
f ′′(x) sejam func¸o˜es cont´ınuas num intervalo I que conte´m a raiz δ
de f (x) = 0.
1 Dados iniciais: x0 e a precisa˜o �.
2 Se |f (x0)| < �, enta˜o x¯ = x0 e´ a raiz procurada e o processo
terminou.
3 k = 1
4 x1 = x0 − f (x0)f ′(x0)
5 Se |f (x1)| < � ou
|x1 − x0| < �
enta˜o x¯ = x1 e´ a raiz procurada e o processo terminou.
6 x0 = x1
7 k = k + 1 volte ao passo 4.
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.1: Seja a equac¸a˜o f (x) = x2 + x − 6 = 0, a raiz δ2 = 2 e
x0 = 1.5 com φ(x) = x − f (x)f ′(x) = x − x
2+x−6
2x+1 , com � = 10
−5 :
xi+1 φ(xi ) xi − x
2
i +xi−6
2xi+1
=
x1 φ(x0) 1.5− (1.5)
2+(1.5)−6
2(1.5)+1 2.0625
x2 φ(x1) 2.0625− (2.0625)
2+(2.0625)−6
2(2.0625)+1 2.00076
x3 φ(x2) 2.00076− (2.00076)
2+(2.00076)−6
2(2.00076)+1 2.00000
Aqui trabalhando com cinco casas decimais vemos que
x¯ = x3 = δ2. No MPF precisamos de pelo menos 5 iterac¸o˜es para
obtermos x5 = 2.00048.
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.1: Seja a equac¸a˜o f (x) = x2 + x − 6 = 0, a raiz δ2 = 2 e
x0 = 1.5 com φ(x) = x − f (x)f ′(x) = x − x
2+x−6
2x+1 , com � = 10
−5 :
xi+1 φ(xi ) xi − x
2
i +xi−6
2xi+1
=
x1 φ(x0) 1.5− (1.5)
2+(1.5)−6
2(1.5)+1 2.0625
x2 φ(x1) 2.0625− (2.0625)
2+(2.0625)−6
2(2.0625)+1 2.00076
x3 φ(x2) 2.00076− (2.00076)
2+(2.00076)−6
2(2.00076)+1 2.00000
Aqui trabalhando com cinco casas decimais vemos que
x¯ = x3 = δ2. No MPF precisamos de pelo menos 5 iterac¸o˜es para
obtermos x5 = 2.00048.
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.1: Seja a equac¸a˜o f (x) = x2 + x − 6 = 0, a raiz δ2 = 2 e
x0 = 1.5 com φ(x) = x − f (x)f ′(x) = x − x
2+x−6
2x+1 , com � = 10
−5 :
xi+1 φ(xi ) xi − x
2
i +xi−6
2xi+1
=
x1 φ(x0) 1.5− (1.5)
2+(1.5)−6
2(1.5)+1 2.0625
x2 φ(x1) 2.0625− (2.0625)
2+(2.0625)−6
2(2.0625)+1 2.00076
x3 φ(x2) 2.00076− (2.00076)
2+(2.00076)−6
2(2.00076)+1 2.00000
Aqui trabalhando com cinco casas decimais vemos que
x¯ = x3 = δ2. No MPF precisamos de pelo menos 5 iterac¸o˜es para
obtermos x5 = 2.00048.
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.1: Seja a equac¸a˜o f (x) = x2 + x − 6 = 0, a raiz δ2 = 2 e
x0 = 1.5 com φ(x) = x − f (x)f ′(x) = x − x
2+x−6
2x+1 , com � = 10
−5 :
xi+1 φ(xi ) xi − x
2
i +xi−6
2xi+1
=
x1 φ(x0) 1.5− (1.5)
2+(1.5)−6
2(1.5)+1 2.0625
x2 φ(x1) 2.0625− (2.0625)
2+(2.0625)−6
2(2.0625)+1 2.00076
x3 φ(x2) 2.00076− (2.00076)
2+(2.00076)−6
2(2.00076)+1 2.00000
Aqui trabalhando com cinco casas decimais vemos que
x¯ = x3 = δ2. No MPF precisamos de pelo menos 5 iterac¸o˜es para
obtermos x5 = 2.00048.
2.4.4 Me´todo de Newton-Raphson-MNR
2.4.4 Me´todo de Newton-Raphson-MNR
2.4.4 Me´todo de Newton-Raphson-MNR
2.4.4 Me´todo de Newton-Raphson-MNR
Teorema 2.3:
Sejam f (x), f ′(x) e f ′′(x) func¸o˜es cont´ınuas num intervalo I que
conte´m a raiz δ de f (x) = 0. Supor que f ′(δ) 6= 0. Enta˜o, existe
um intervalo I¯ ⊂ I , contendo a raiz δ, tal que, se x0 ∈ I¯ , a
sequeˆncia {xk} gerada pela fo´rmula recursiva xk+1 = xk − f (xk )f ′(xk )
convergira´ para a raiz.
O MNR tambe´m e´ conhecido como sendo o me´todo das
Tangentes;
Exigimos que f ′(xk) 6= 0 ∀k. Se f ′(xk) = 0 e f (xk) 6= 0 a reta
tangente a` f (x) em x = xk e´ paralela ao eixo das abscissas e
xk+1 e´ indefinido.
Pore´m, se f ′(δ) = 0 e f ′(xk) 6= 0 o me´todo esta´ bem definido,
embora a convergeˆncia seja bem mais lenta.
2.4.4 Me´todo de Newton-Raphson-MNR
Teorema 2.3:
Sejam f (x), f ′(x) e f ′′(x) func¸o˜es cont´ınuas num intervalo I que
conte´m a raiz δ de f (x) = 0. Supor que f ′(δ) 6= 0. Enta˜o, existe
um intervalo I¯ ⊂ I , contendo a raiz δ, tal que, se x0 ∈ I¯ , a
sequeˆncia {xk} gerada pela fo´rmula recursiva xk+1 = xk − f (xk )f ′(xk )
convergira´ para a raiz.
O MNR tambe´m e´ conhecido como sendo o me´todo das
Tangentes;
Exigimos que f ′(xk) 6= 0 ∀k. Se f ′(xk) = 0 e f (xk) 6= 0 a reta
tangente a` f (x) em x = xk e´ paralela ao eixo das abscissas e
xk+1 e´ indefinido.
Pore´m, se f ′(δ) = 0 e f ′(xk) 6= 0 o me´todo esta´ bem definido,
embora a convergeˆncia seja bem mais lenta.
2.4.4 Me´todo de Newton-Raphson-MNR
Uma escolha cuidadosa da aproximac¸a˜o inicial e´, em geral,
essencial para o bom desempenho do me´todo de Newton.
Consideremos a func¸a˜o f (x) = x3 − 9x + 3 cujas ra´ızes esta˜o
em δ1 ∈ [−4,−3], δ2 ∈ [0, 1] e δ3 ∈ [2, 3]. Tomemos x0 = 1.5,
a sequeˆncia gerada pelo MNR e´ a seguinte:
2.4.4 Me´todo de Newton-Raphson-MNR
i xi f (xi )
1 −1.6666667 0.1337037 ∗ 102
2 18.3888889 0.6055725 ∗ 104
3 12.3660104 0.1782694 ∗ 104
4 8.4023067 0.5205716 ∗ 103
5 5.83533816 0.1491821 ∗ 103
6 4.23387355 0.4079022 ∗ 102
7 3.2291096 0.9784511 ∗ 10
8 2.91733893 0.1573032 ∗ 10
9 2.82219167 0.7837065 ∗ 10−1
10 2.81692988 0.2342695 ∗ 10−3
2.4.4 Me´todo de Newton-Raphson-MNR
De in´ıcio ha´ uma divergeˆncia da regia˜o onde esta˜o as ra´ızes,
mas a partir de x7, os valores aproximam-se cada vez mais de
δ3.
Este fato ocorre pois escolhemos x0 = 1.5 que esta´ bem
pro´ximo de
√
3 que e´ um dos pontos onde f ′(x) = 0
O me´todo de Newton tem convergeˆncia quadra´tica.
Apo´s as primeiras iterac¸o˜es a quantidade de d´ıgitos corretos
em cada iterac¸a˜o comec¸a a duplicar de uma iterac¸a˜o para a
outra.
2.4.4Me´todo de Newton-Raphson-MNR
Ex.3 Seja f (x) = x3 − 20 = 0 encontre a raiz positiva desta
equac¸a˜o pelo MNR. Tomemos x0 = 3 Aqui xk+1 = xk − x
3
k−20
3x2k
enta˜o
i xi (xi )
3
0 3 27
1 2.7407407 20.6
2 2.7146696 20.0056
3 2.7144176 19.9999996
4 2.7144176 19.9999996
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.3 Seja f (x) = x3 − 20 = 0 encontre a raiz positiva desta
equac¸a˜o pelo MNR. Tomemos x0 = 3 Aqui xk+1 = xk − x
3
k−20
3x2k
enta˜o
i xi (xi )
3
0 3 27
1 2.7407407 20.6
2 2.7146696 20.0056
3 2.7144176 19.9999996
4 2.7144176 19.9999996
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.3 Seja f (x) = x3 − 20 = 0 encontre a raiz positiva desta
equac¸a˜o pelo MNR. Tomemos x0 = 3 Aqui xk+1 = xk − x
3
k−20
3x2k
enta˜o
i xi (xi )
3
0 3 27
1 2.7407407 20.6
2 2.7146696 20.0056
3 2.7144176 19.9999996
4 2.7144176 19.9999996
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.3 Seja f (x) = x3 − 20 = 0 encontre a raiz positiva desta
equac¸a˜o pelo MNR. Tomemos x0 = 3 Aqui xk+1 = xk − x
3
k−20
3x2k
enta˜o
i xi (xi )
3
0 3 27
1 2.7407407 20.6
2 2.7146696 20.0056
3 2.7144176 19.9999996
4 2.7144176 19.9999996
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.3 Seja f (x) = x3 − 20 = 0 encontre a raiz positiva desta
equac¸a˜o pelo MNR. Tomemos x0 = 3 Aqui xk+1 = xk − x
3
k−20
3x2k
enta˜o
i xi (xi )
3
0 3 27
1 2.7407407 20.6
2 2.7146696 20.0056
3 2.7144176 19.9999996
4 2.7144176 19.9999996
2.4.4 Me´todo de Newton-Raphson-MNR
Ex.3 Seja f (x) = x3 − 20 = 0 encontre a raiz positiva desta
equac¸a˜o pelo MNR. Tomemos x0 = 3 Aqui xk+1 = xk − x
3
k−20
3x2k
enta˜o
i xi (xi )
3
0 3 27
1 2.7407407 20.6
2 2.7146696 20.0056
3 2.7144176 19.9999996
4 2.7144176 19.9999996
Comparando com os demais me´todos que ja´ estudamos, qual e´ a
maior dificuldade do me´todo de Newton-Raphson?
Pro´xima aula
Me´todo da Secante e exemplos
Por hoje e´ so´ pessoal!!
Este material e´ inteiramente baseado na bibliografia do curso,
principalmente no livro texto :RUGIERO, M. A.G; LOPES,V
Ca´lculo Nume´rico: Aspectos teo´ricos e computacionais, Editora
McGraw-Hill.1997. Sites consultados acessados em 24/03/2011:
CASTILHO, J. E., Apostila de Ca´lculo Nume´rico,
http://www.castilho.prof.ufu.br, UFU, 2002
http://www.alunos.eel.usp.br/numerico/notas.html
Colli, E., Asano, H. C,Ca´lculo Nume´rico — Fundamentos e
Aplicac¸o˜es-Departamento de Matema´tica Aplicada – IME-USP,
2009
Este material na˜o substitui a bibliografia.