11. aceleracao convergencia

Prévia do material em texto

Estudo da Convergência do Método de Newton-Raphson
Considere a equação 
f x( ) 0=
onde x pertence ao intervalo [a,b] que contém uma única raiz isolada de f.
Para saber a priori se a seqüência gerada pelas iteradas φk do método de Newton converge para a raiz, usamos o
teorema da convexidade, que garante condições necessárias para a convergência. Nos exemplos seguintes
mostramos 3 situações onde a convergência é observada, para a função f(x) que possui 3 raízes reais simples. 
f x( ) x pi−( ) x 2+( )⋅ x 1−( )⋅:=
0
50
50
f x( )
x
A função φ do método de Newton é dada pela equação φ x( ) x f x( )
x
f x( )d
d
−=
para função f(x),
f x( ) x3 1 pi−( ) x2⋅+ 2 pi+( ) x⋅− 2 pi⋅+:=
x
f x( )d
d
3 x2⋅ 2 1 pi−( ) x⋅⋅ 2− pi−+→
portanto 
φ x( ) x x
3 1 pi−( ) x2⋅+ 2 pi+( ) x⋅− 2 pi⋅+
3 x2⋅ 2 1 pi−( ) x⋅⋅ 2− pi−+
−








:=
4 2 0 2 4
10
5
5
10
Função Fi_Newton
φ x( )
y
y
y
x pi, 1, 2−,
4 2 0 2 4
1
0.5
0.5
1
Derivada da Fi_Newton
x
φ x( )d
d
y
y
y
x pi, 1, 2−,
Estudo 1: tipo de seqüência crescente, decrescente, oscilante
A expressão da função φ que gera as iteradas do método de Newton é única, mas a convergência para cada uma
das raízes pode ser diferente, pois depende do sinal da derivada de φ(x). 
CASO 1: Seqüência crescente ou decrescente: se o chute inicial e os demais valores de xk obtidos estiverem
contidos num intervalo onde 
x
φd
d
 é POSITIVA.
CASO 1: Seqüência oscilante ou alternada: se o chute inicial e os demais valores de xk obtidos estiverem
contidos num intervalo onde 
x
φd
d
 é NEGATIVA.
Exemplificando os CASOS 1 e 2 
CASO 1: seqüência decrescente para a raiz z1 = pi
chute inicial: x0 5.0:=
k 0 6..:= xk 1+ xk
xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+
3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )−
−:=
Neste caso a derivada da função φ é POSITIVA e a
seqüência gerada é DECRESCENTE.
x
5
3.92583111
3.36581355
3.16853365
3.14205955
3.1415928
3.14159265
3.14159265






















=
CASO 2: seqüência alternada ou oscilante para a raiz z1 = pi
chute inicial: x0 2.5:=
k 0 6..:= xk 1+ xk
xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+
3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )−
−:=
Neste caso a derivada da função φ é NEGATIVA e a
seqüência gerada é OSCILANTE.
x
2.5
3.99313357
3.3962246
3.17546795
3.14232566
3.14159301
3.14159265
3.14159265






















=
CASO 2: seqüência alternada ou oscilante para a raiz z2 = 1
chute inicial: x0 1.8:=
k 0 6..:= xk 1+ xk
xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+
3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )−
−:=
Neste caso a derivada da função φ é NEGATIVA e a
seqüência gerada é OSCILANTE.
x
1.8
0.49753536
1.005665
0.99999565
1
1
1
1






















=
CASO ?: seqüência oscilante e depois crescente para a raiz z2 = 1
chute inicial: x0 1.6:=
k 0 6..:= xk 1+ xk
xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+
3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )−
−:=
Neste caso a derivada da função φ é NEGATIVA no chute
inicial, o que implica no valor x1 menor que a raiz, mas para
valores menores que a raiz, a derivada da φ é positiva, o que
torna a seqüência crescente para or valores xk, com k>1, até
a convergência.
Neste caso deve se dizer que a seqüência é crescente!
 
x
1.6
0.82825492
0.99770957
0.9999993
1
1
1
1






















=
Estas observações servem como base para definir como fazer a aceleração da convergência do método de
Newton ou de qualquer método cujas iterações sejam construídas a partir de uma função de iteração, da qual
sabemos a priori que a seqüência gerada converge para a raiz.
Cálculo de zeros de uma função com PRECISÃO PRÉ-FIXADA δδδδ. 
Seja f(x) = 0 e φ(xk)= xk+1, k = 0,1,2,3 a seqüência das iteradas pelo método das aproximações sucessivas
obtidas a partir do chute inicial x0.Apenas observando os valores de xk, para k = 1,2,3, é possível identificar se a
seqüência é crescente/decrescente ou oscilante.
É obvio que o ideal é determinar o sinal de 
x
φ x( )d
d
 para identificar o tipo de seqüência, como foi mostrado no
início desse Capítulo, mas calcular a derivada da função φ não é uma tarefa fácil e em geral, os valores
calculados das 3 primeiras iteradas definem de forma adequada o tipo de seqüência.
Portanto, depois de indetificar o tipo de seqüência é possível introduzir a aceleração da convergência
seqüência 
oscilante 
⇔ a raiz α está contida nos intervalos definidos por duas iteradas consecutivas
(Figura 1) 
Figura 1 
seqüência 
monótona 
crescente
⇔ a raiz α está sempre à direita das iteradas (Figura 2) 
Figura 2 
seqüência 
monótona 
decrescente
⇔ a raiz α está sempre à esquerda das iteradas (Figura 3) 
Figura 3 
Aceleração da convergência para seqüências oscilantes
seqüência 
oscilante ⇔ a raiz α está contida nos intervalos definidos por duas iteradas consecutivas
Neste caso a raiz aproximada ξn pode ser escolhida como o ponto médio entre duas iteradas consecutivas
ξn
x
n
x
n 1−+
2
=
E o erro εn será no máximo εn
x
n
x
n 1−−
2
=
LOGO, O PROCESSO ITERATIVO DEVE SER REPETIDO ENQUANTO εn δ≤ 
Aceleração da convergência para seqüências crescentes
seqüência 
monótona 
crescente
⇔ a raiz α está sempre à direita das iteradas 
Como a seqüência é crescente, se α é o valor exato, então x
n 1− xn≤ α≤
conseqüentemente, x
n
φ x
n( )≤ α≤
então, calculando φ no ponto (x
n
+2δ) teremos x
n
2δ+ φ x
n
2δ+( )≤ , enquanto xn 2δ+ α≤
LOGO, O PROCESSO ITERATIVO DEVE SER REPETIDO ENQUANTO x
n
2δ+ α≤
.
QUANDO x
n
2δ+ α> SABEMOS QUE A RAIZ α ESTÁ CONTIDA NO INTERVALO [x
n
, x
n
+2δ].
Neste caso a raiz aproximada ξn pode ser escolhida como ξn xn δ+=
E o erro εn será certamente εn xn α− δ≤=
Aceleração da convergência para seqüências decrescentes
seqüência 
monótona 
decrescente
⇔ a raiz α está sempre à esquerda das iteradas 
Como a seqüência é crescente, se α é o valor exato, então x
n 1− xn≥ α≥
conseqüentemente, x
n
φ x
n( )≥ α≥
então, calculando φ no ponto (x
n
- 2δ) teremos x
n
2δ− φ x
n
2δ−( )≥ , enquanto 
x
n
2δ− α≥
LOGO, O PROCESSO ITERATIVO DEVE SER REPETIDO ENQUANTO x
n
2δ− α≥ .
QUANDO x
n
2δ− α< SABEMOS QUE A RAIZ α ESTÁ CONTIDA NO INTERVALO [x
n
-2δ, x
n
].
Neste caso a raiz aproximada ξn pode ser escolhida como ξn xn δ−=
E o erro εn será certamente εn xn α− δ≤=