Newton_C

Prévia do material em texto

Considere a equac¸a˜o
f(x) = 0, f : D ⊆ ℜ → ℜ.
Supor ξ ∈ D, tal que: f(ξ) = 0 e f ′(ξ) 6= 0.
Supor que a derivada de f esta´ definida e e´ cont´ınua em
um intervalo I que conte´m ξ.
Motivac¸a˜o geome´trica do me´todo de Newton:
dada a aproximac¸a˜o xk, a nova aproximac¸a˜o xk+1
sera´ o zero da reta tangente a` curva em (xk, f(xk)).
1 1.5 2 2.5 3 3.5 4 4.5 5
−5
0
5
10
15
20
25
30
35
40
45
50
x3 − 9*x + 3
2
1 1.5 2 2.5 3 3.5 4 4.5 5
−5
0
5
10
15
20
25
30
35
40
45
50
x3 − 9*x + 3
1 1.5 2 2.5 3 3.5 4 4.5 5
−5
0
5
10
15
20
25
30
35
40
45
50
x3 − 9*x + 3
3
Convergeˆncia do me´todo de Newton
Sejam f , f ′ e f ′′ cont´ınuas num intervalo I que conte´m a raiz ξ
de f . 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 atrave´s
da fo´rmula xk+1 = xk − f(xk)/f
′(xk) convergira´ para a raiz.
Exemplo 1:
f(x) = x3 − 9x+ 3
xk f(xk) f
′(xk)
3 3 18
2.833333333333334 2.453703703703738e-001 1.508333333333334e+001
2.817065684468999 2.245104384343222e-003 1.480757721183837e+001
2.816914065851569 1.942743637073363e-007 1.480501456317726e+001
2.816914052729369 0
Exemplo 2: f ′(x0) ≈ 0.
f(x) = x3 − 9 ∗ x+ 3
x0 = 1.8
f(x0) = −7.368 f
′(x0) = 0.72.
x1 = x0 − f(x0)/f
′(x0)⇒ x1 = 1.8 + 10.2333⇒ x1 = 12.0333
x1 = 12.0333
f(x1) = 1637.14 f
′(x1) = 425.4033.
x2 = x1 − f(x1)/f
′(x1)⇒ x2 = 12.0333− 3.848⇒ x2 = 8.1849
4
1 1.5 2 2.5 3 3.5 4 4.5 5
−5
0
5
10
15
20
25
30
35
40
45
50
x3 − 9*x + 3
O fato de ocorrer f ′(xk) ≈ 0 na˜o implica que a sequeˆncia gerada
pelo me´todo de Newton sera´ divergente.
No exemplo anterior f(x) = x3 − 9x + 3 com x0 = 1.8, se conti-
nuarmos a executar as iterac¸o˜es do me´todo, teremos:
xk f(xk) f
′(xk)
1.800000000000000 -7.367999999999999e+000 7.200000000000006e-001
12.03333333333332 1.637140037037033e+003 4.254033333333326e+002
8.184891375418006 4.776618778769087e+002 1.919773404821762e+002
5.696775451542832 1.366079019653545e+002 8.835975163590311e+001
4.150733283743813 3.715466907896130e+001 4.268576037833610e+001
3.280310249231862 8.774774060096426e+000 2.328130599364680e+001
2.903408108841158 1.344414698368968e+000 1.628933593945376e+001
2.820874683085433 5.876981470251153e-002 1.487200193301702e+001
2.816922974702983 1.320906199957506e-004 1.480516513622850e+001
2.816914052774806 6.726885715124809e-010
Observamos que nas iterac¸o˜es iniciais a sequeˆncia se distancia da
5
raiz, pois, f ′(x0) ≈ 0, pore´m, a partir de x5 ≈ 3.28 a sequeˆncia e´
atra´ıda para a raiz.
Taxa Quadra´tica de Convergeˆncia
Supor que as condic¸o˜es do teorema de convergeˆncia sa˜o satisfeitas
e que a sequeˆncia gerada converge para a raiz ξ.
Demonstra–se que o me´todo de Newton tem taxa quadra´tica de
convergeˆncia, pois verifica a relac¸a˜o:
para k →∞, a sequeˆncia gerada pelo me´todo de Newton converge
para a raiz ξ, enta˜o:
|xk+1 − ξ| < C|xk − ξ|
2
onde C e´ uma constante, real, positiva.
Podemos dizer, que para k → ∞, o nu´mero de d´ıgitos corretos
em xk+1 praticamente dobra em relac¸a˜o a` xk. Este fato pode ser
observado no exemplo 1, comparando o nu´mero de d´ıgitos corretos
de cada aproximac¸a˜o xk com o valor obtido para x4.
6
Crite´rios de Parada para o Me´todo de Newton:
valor de f pro´ximo de zero:
|f(xk)| < tol1;
diferenc¸a entre as duas u´ltimas aproximac¸o˜es pro´ximo de zero:
|xk+1 − xk| < tol2;
nu´mero ma´ximo de iterac¸o˜es;
Algoritmo para o Me´todo de Newton:
Considere a equac¸a˜o f(x) = 0;
a aproximac¸a˜o inicial: x0; as toleraˆncias: tol1 e tol2;
Passo 0: Avaliar f em x0: f0 = f(x0);
se |f0| < tol1, fac¸a x = x0. Parar.
caso contra´rio: k = 0;
Passo 1: Avaliar a derivada de f em x0: dv = f ′(x0);
Passo 2: Fac¸a: x1 = x0− f0/dv;
Passo 3: Avaliar f em x1: f1 = f(x1);
se |f1| < tol1, fac¸a x = x1. Parar.
Passo 4: Se |x1− x0| < tol2, fac¸a x = x1. Parar.
Passo 5: Fac¸a: x0 = x1 e f0 = f1;
Passo 6: Se k = itmax, parar: excedido o nu´mero de iterac¸o˜es.
caso contra´rio: k = k + 1, voltar ao passo 1.
7