Iteração de ponto fixo.
Em análise numérica , iteração de ponto fixo é um método de se calcular pontos fixos de funções . Ponto fixo de dada função
f
{\textstyle f}
é o número
x
∗
{\textstyle x^{*}}
que quando aplicado na função resulta nele mesmo, i.e.
f
(
x
∗
)
=
x
∗
{\textstyle f(x^{*})=x^{*}}
. Dada uma aproximação inicial
x
0
{\textstyle x_{0}}
para
x
∗
{\displaystyle x^{*}}
, o método consiste em iterar sucessivamente a função dada sobre
x
0
{\textstyle x_{0}}
. Ou seja, constrói-se a sequência
x
n
+
1
=
f
n
+
1
(
x
0
)
=
f
n
(
f
(
x
0
)
)
{\textstyle x_{n+1}=f^{n+1}(x_{0})=f^{n}(f(x_{0}))}
sendo cada
x
n
{\textstyle x_{n}}
uma nova aproximação do ponto fixo
x
∗
{\textstyle x^{*}}
. Uma importante aplicação deste método aparece no cálculo numérico de soluções de equações de uma variável real.[ 1]
Ilustração do método.
Seja
f
:
[
a
,
b
]
⊂
R
→
[
a
,
b
]
{\textstyle f:[a,b]\subset \mathbb {R} \to [a,b]}
uma função com um único ponto fixo
x
∗
∈
[
a
,
b
]
{\textstyle x^{*}\in [a,b]}
, o qual buscamos determinar. A iteração do ponto fixo consiste em construirmos a sequência recursiva :[ 1]
x
n
+
1
=
f
(
x
n
)
,
n
=
0
,
1
,
2
,
…
,
{\displaystyle x_{n+1}=f(x_{n}),\quad n=0,1,2,\ldots ,}
sendo
x
0
∈
[
a
,
b
]
{\textstyle x_{0}\in [a,b]}
uma aproximação inicial de
x
∗
{\textstyle x^{*}}
. Para certas funções, tem-se que a sequência
(
x
n
)
n
{\displaystyle (x_{n})_{n}}
converge para o ponto fixo
x
∗
{\textstyle x^{*}}
. Por exemplo, o teorema da convergência enunciado abaixo, garante que a convergência do método do ponto fixo para contrações.
Existem diversas maneiras de usar o método para obter a raiz de uma função
f
(
x
)
{\textstyle f(x)}
. A ideia fundamental é reescrever a equação
f
(
x
)
=
0
{\textstyle f(x)=0}
em uma equação equivalente da forma:
g
(
x
)
=
x
{\displaystyle g(x)=x}
i.e., em um problema de ponto fixo. Se
g
(
x
)
{\textstyle g(x)}
é uma função para a qual o método do ponto fixo converge, então a sequência:
x
n
+
1
=
g
(
x
n
)
,
n
=
0
,
1
,
…
,
{\displaystyle x_{n+1}=g(x_{n}),\quad n=0,1,\ldots ,}
com
x
0
{\textstyle x_{0}}
uma aproximação inicial da solução, converge para o ponto fixo
x
∗
{\textstyle x^{*}}
da função
g
{\textstyle g}
. Notemos que o ponto fixo
x
∗
{\textstyle x^{*}}
é também solução da equação
f
(
x
)
=
0
{\displaystyle f(x)=0}
.[ 1]
Há muitas maneiras de manipular uma equação de forma a utilizar o método do ponto fixo. É importante observar que, apesar da simplicidade do método, este pode não convergir dependendo da função (veja, abaixo, o Teorema da Convergência para condições suficientes de convergência). No seguinte exemplo, buscamos mostrar este fato.
Buscaremos aproximar a solução da equação
x
e
x
=
10
{\textstyle xe^{x}=10}
usando o método do ponto fixo. Notemos que essa equação é equivalente a
x
=
10
e
−
x
{\displaystyle x=10e^{-x}}
e
x
=
l
n
(
10
x
)
{\displaystyle x=ln\left({10 \over x}\right)}
.
Ao efetuarmos o processo iterativo para a primeira equação, i.e.
x
n
+
1
=
10
e
−
x
n
{\textstyle x_{n+1}=10e^{-x_{n}}}
, com
x
0
=
1
{\displaystyle x_{0}=1}
, obtemos a seguinte sequência:
x
0
=
1
{\displaystyle x_{0}=1}
x
1
=
10
e
−
1
=
3.6787944
{\displaystyle x_{1}=10e^{-1}=3.6787944}
x
2
=
10
e
−
3.6787944
=
0.2525340
{\displaystyle x_{2}=10e^{-3.6787944}=0.2525340}
x
3
=
10
e
−
0.2525340
=
7.7682979
{\displaystyle x_{3}=10e^{-0.2525340}=7.7682979}
x
4
=
10
e
−
7.7682979
=
0.0042293
{\displaystyle x_{4}=10e^{-7.7682979}=0.0042293}
x
5
=
10
e
−
0.0042293
=
9.9577961
{\displaystyle x_{5}=10e^{-0.0042293}=9.9577961}
E quando realizamos o processo com a outra equação, i.e.
x
n
+
1
=
l
n
(
10
x
n
)
{\displaystyle x_{n+1}=ln\left({10 \over x_{n}}\right)}
, e novamente iniciarmos o processo com
x
0
=
1
{\displaystyle x_{0}=1}
, a nova sequência se da por:
x
0
=
1
{\displaystyle x_{0}=1}
x
1
=
l
n
(
10
1
)
=
2.3025851
{\displaystyle x_{1}=ln\left({10 \over 1}\right)=2.3025851}
x
2
=
l
n
(
10
2.3025851
)
=
1.4685526
{\displaystyle x_{2}=ln\left({10 \over 2.3025851}\right)=1.4685526}
x
3
=
l
n
(
10
1.4685526
)
=
1.9183078
{\displaystyle x_{3}=ln\left({10 \over 1.4685526}\right)=1.9183078}
x
4
=
l
n
(
10
1.9183078
)
=
1.6511417
{\displaystyle x_{4}=ln\left({10 \over 1.9183078}\right)=1.6511417}
.
{\displaystyle .}
.
{\displaystyle .}
.
{\displaystyle .}
x
10
=
1.7421335
{\displaystyle x_{10}=1.7421335}
x
20
=
1.7455151
{\displaystyle x_{20}=1.7455151}
x
30
=
1.745528
{\displaystyle x_{30}=1.745528}
x
31
=
1.745528
{\displaystyle x_{31}=1.745528}
O teste realizado com as duas equações indica que, apesar delas serem equivalentes, a primeira não é convergente enquanto a segunda equação converge para o valor de
1.745528
{\displaystyle 1.745528}
(que é a solução aproximada de
x
e
x
=
10
{\textstyle xe^{x}=10}
). As condições para que uma equação convirja para o valor de ponto fixo estão contidas no teorema de convergência.
iteração do ponto fixo
x
n
+
1
=
cos
(
x
n
)
{\displaystyle x_{n+1}=\cos(x_{n})}
com valor inicial
x
1
=
−
1.
{\displaystyle x_{1}=-1.}
Seja
f
:
[
a
,
b
]
→
[
a
,
b
]
{\textstyle f:[a,b]\rightarrow [a,b]}
uma função contração , i.e. uma função que satisfaça:
|
f
(
x
)
−
f
(
y
)
|
≤
α
|
x
−
y
|
,
α
<
1
,
∀
x
,
y
∈
[
a
,
b
]
.
{\displaystyle |f(x)-f(y)|\leq \alpha |x-y|,\quad \alpha <1,\quad \forall x,y\in [a,b].}
Então, existe um único ponto
x
∗
{\textstyle x^{*}}
pertencente ao intervalo
[
a
,
b
]
{\displaystyle [a,b]}
tal que
f
(
x
∗
)
=
x
∗
{\textstyle f(x^{*})=x^{*}}
. Além disso, para qualquer
x
0
∈
[
a
,
b
]
{\displaystyle x_{0}\in [a,b]}
, a sequência
(
x
n
)
n
{\displaystyle (x_{n})_{n}}
dada por:
x
n
+
1
=
f
(
x
n
)
,
n
=
0
,
1
,
2
,
…
,
{\displaystyle x_{n+1}=f(x_{n}),\quad n=0,1,2,\ldots ,}
converge para
x
∗
{\textstyle x^{*}}
quando
n
→
∞
{\displaystyle n\to \infty }
.
Demonstração:
Existência. Caso
f
(
a
)
=
a
{\displaystyle f(a)=a}
ou
f
(
b
)
=
b
{\displaystyle f(b)=b}
o ponto fixo existe nos extremos. Caso contrário, então
f
(
a
)
>
a
{\displaystyle f(a)>a}
e
f
(
b
)
<
b
{\displaystyle f(b)<b}
. Neste caso, seja:
h
(
x
)
=
f
(
x
)
−
x
{\displaystyle h(x)=f(x)-x}
Como
f
{\displaystyle f}
é uma função contínua ,
h
{\displaystyle h}
também é. Notemos que:
h
(
a
)
=
f
(
a
)
−
a
>
0
{\displaystyle h(a)=f(a)-a>0}
e
h
(
b
)
=
f
(
b
)
−
b
<
0
{\displaystyle h(b)=f(b)-b<0}
ou seja,
h
{\displaystyle h}
troca de sinal no intervalo
[
a
,
b
]
{\displaystyle [a,b]}
. Logo, pelo Teorema do valor intermediário , garantimos a existência de um ponto
x
∗
∈
(
a
,
b
)
{\displaystyle x^{*}\in (a,b)}
tal que
h
(
x
∗
)
=
0
{\displaystyle h(x^{*})=0}
. Esse valor
x
∗
{\displaystyle x^{*}}
é um ponto fixo de
f
{\displaystyle f}
, uma vez que
h
(
x
∗
)
=
f
(
x
∗
)
−
x
∗
=
x
∗
−
x
∗
=
0
{\displaystyle h(x^{*})=f(x^{*})-x^{*}=x^{*}-x^{*}=0}
Unicidade. Suponhamos que
x
∗
{\displaystyle x^{*}}
e
x
∗
∗
{\displaystyle x^{**}}
sejam pontos fixos distintos de
f
{\displaystyle f}
. Então:
|
x
∗
−
x
∗
∗
|
=
|
f
(
x
∗
)
−
f
(
x
∗
∗
)
|
≤
α
|
x
∗
−
x
∗
∗
|
⇒
α
≥
1
{\displaystyle |x^{*}-x^{**}|=|f(x^{*})-f(x^{**})|\leq \alpha |x^{*}-x^{**}|\Rightarrow \alpha \geq 1}
o que é uma contradição.
Convergência. Seja
(
x
n
)
n
{\displaystyle (x_{n})_{n}}
a sequência iterada
x
n
+
1
=
f
(
x
n
)
{\displaystyle x_{n+1}=f(x_{n})}
com
x
0
∈
[
a
,
b
]
{\displaystyle x_{0}\in [a,b]}
e
x
∗
{\displaystyle x^{*}}
o ponto fixo de
f
{\displaystyle f}
. Então, temos:
|
x
n
+
1
−
x
∗
|
=
|
f
(
x
n
)
−
f
(
x
∗
)
|
≤
α
|
x
n
−
x
∗
|
,
n
=
1
,
2
,
…
{\displaystyle |x_{n+1}-x^{*}|=|f(x_{n})-f(x^{*})|\leq \alpha |x_{n}-x^{*}|,\quad n=1,2,\ldots }
Isso implica que:
|
x
n
+
1
−
x
∗
|
≤
α
n
|
x
1
−
x
∗
|
,
n
=
1
,
2
,
…
{\displaystyle |x_{n+1}-x^{*}|\leq \alpha ^{n}|x_{1}-x^{*}|,\quad n=1,2,\ldots }
Como
0
≤
α
<
1
{\displaystyle 0\leq \alpha <1}
, temos que
x
n
→
x
∗
{\displaystyle x_{n}\to x^{*}}
quando
n
→
∞
{\displaystyle n\to \infty }
.
Isso completa a demostração.
A desigualdade estrita
α
<
1
{\textstyle \alpha <1}
é necessária.
A condição
f
(
[
a
,
b
]
)
⊂
[
a
,
b
]
{\textstyle f([a,b])\subset [a,b]}
é necessária.
Determinar os pontos fixos de uma função
f
(
x
)
{\textstyle f(x)}
é determinar a interseção entre as curvas
y
=
f
(
x
)
{\textstyle y=f(x)}
e
y
=
x
{\textstyle y=x}
.
A condição
|
f
(
x
)
−
f
(
y
)
|
≤
α
|
x
−
y
|
{\textstyle |f(x)-f(y)|\leq \alpha |x-y|}
é satisfeita sempre que
|
f
′
(
x
)
|
≤
α
<
1
{\displaystyle |f'(x)|\leq \alpha <1}
para todo
x
{\textstyle x}
, pois:
|
f
(
x
)
−
f
(
y
)
|
=
|
∫
x
y
f
′
(
s
)
d
s
|
≤
∫
x
y
α
d
s
=
α
|
x
−
y
|
,
(
x
<
y
)
{\displaystyle |f(x)-f(y)|=\left|{\int _{x}^{y}}{f'(s)}ds\right|\leq {\int _{x}^{y}}{\alpha }ds=\alpha |x-y|,\quad (x<y)}
.
Seja
f
:
[
a
,
b
]
{\displaystyle f:[a,b]}
uma função
C
0
[
a
,
b
]
{\displaystyle C^{0}[a,b]}
e
x
∗
∈
(
a
,
b
)
{\displaystyle x^{*}\in (a,b)}
um ponto fixo de
f
{\displaystyle f}
. É dito que
x
∗
{\displaystyle x^{*}}
é um ponto fixo estável caso exista uma região
(
x
∗
−
Δ
x
,
x
∗
+
Δ
x
)
{\displaystyle (x^{*}-\Delta x,x^{*}+\Delta x)}
chamada de bacia de atração tal que
x
(
n
+
1
)
=
f
(
x
(
n
)
)
{\displaystyle x^{(n+1)}=f(x^{(n)})}
é convergente sempre que
x
(
0
)
∈
(
x
∗
−
Δ
x
,
x
∗
+
Δ
x
)
{\displaystyle x^{(0)}\in (x^{*}-\Delta x,x^{*}+\Delta x)}
.
Se
f
∈
[
a
,
b
]
{\displaystyle f\in [a,b]}
e
|
f
′
(
x
∗
)
|
{\displaystyle |f'(x^{*})|}
<
1
{\displaystyle 1}
, então
x
∗
{\displaystyle x^{*}}
é estável. Se
|
f
′
(
x
∗
)
|
{\displaystyle |f'(x^{*})|}
>
1
{\displaystyle 1}
é instável e o teste é inconclusivo caso
|
f
′
(
x
∗
)
|
=
1
{\displaystyle |f'(x^{*})|=1}
.
Considerando o problema de encontrar a solução da equação
c
o
s
(
x
)
=
x
{\displaystyle cos(x)=x}
analisando a equação como ponto fixo da função
f
(
x
)
=
c
o
s
(
x
)
{\displaystyle f(x)=cos(x)}
. A demonstração do Teorema do ponto fixo pode ser aplicado na função com o intervalo
[
a
,
b
]
=
[
1
/
2
,
1
]
{\displaystyle [a,b]=[1/2,1]}
.
Para provar que
f
(
[
1
/
2
,
1
]
)
⊂
[
1
/
2
,
1
]
{\displaystyle f([1/2,1])\subset [1/2,1]}
basta analisar que
f
(
x
)
{\displaystyle f(x)}
é decrescente no intervalo:
0
,
54
{\displaystyle 0,54}
<
c
o
s
(
1
)
≤
c
o
s
(
x
)
≤
c
o
s
(
1
/
2
)
{\displaystyle cos(1)\leq cos(x)\leq cos(1/2)}
<
0
,
88
{\displaystyle 0,88}
f
(
[
1
/
2
,
1
]
)
⊂
[
1
/
2
,
1
]
{\displaystyle f([1/2,1])\subset [1/2,1]}
é verdade pois
[
0.54
,
0.88
]
⊂
[
1
/
2
,
1
]
{\displaystyle [0.54,0.88]\subset [1/2,1]}
.
Agora para provar
|
f
(
x
)
−
f
(
y
)
|
≤
α
|
x
−
y
|
,
α
{\displaystyle |f(x)-f(y)|\leq \alpha |x-y|,\alpha }
<
1
{\displaystyle 1}
observamos que
f
′
(
x
)
=
−
s
e
n
(
x
)
{\displaystyle f'(x)=-sen(x)}
, dessa forma temos a estimativa :
−
0
,
85
{\displaystyle -0,85}
<
−
s
e
n
(
1
)
≤
−
s
e
n
(
x
)
≤
−
s
e
n
(
1
/
2
)
{\displaystyle -sen(1)\leq -sen(x)\leq -sen(1/2)}
<
−
0
,
47
{\displaystyle -0,47}
Assim temos que
|
f
′
(
x
)
|
{\displaystyle |f'(x)|}
<
0
,
85
{\displaystyle 0,85}
e dessa forma
α
=
0
,
85
{\displaystyle \alpha =0,85}
<
1.
{\displaystyle 1.}
Agora observamos o processo numérico da sequência fazendo
x
(
n
+
1
)
=
c
o
s
(
x
(
n
)
)
{\displaystyle x^{(n+1)}=cos(x^{(n)})}
, iniciando com
x
(
0
)
=
1
{\displaystyle x^{(0)}=1}
, obtemos a sequência:
x
(
1
)
=
c
o
s
(
x
(
0
)
)
=
c
o
s
(
1
)
=
0
,
5403023
{\displaystyle x^{(1)}=cos(x^{(0)})=cos(1)=0,5403023}
x
(
2
)
=
c
o
s
(
x
(
1
)
)
=
c
o
s
(
0
,
5403023
)
=
0
,
8575532
{\displaystyle x^{(2)}=cos(x^{(1)})=cos(0,5403023)=0,8575532}
x
(
3
)
=
c
o
s
(
x
(
2
)
)
=
c
o
s
(
0
,
8575532
)
=
0
,
6542898
{\displaystyle x^{(3)}=cos(x^{(2)})=cos(0,8575532)=0,6542898}
x
(
4
)
=
c
o
s
(
x
(
3
)
)
=
c
o
s
(
0
,
6542898
)
=
0
,
7934804
{\displaystyle x^{(4)}=cos(x^{(3)})=cos(0,6542898)=0,7934804}
x
(
5
)
=
c
o
s
(
x
(
4
)
)
=
c
o
s
(
0
,
7934804
)
=
0
,
7013688
{\displaystyle x^{(5)}=cos(x^{(4)})=cos(0,7934804)=0,7013688}
.
{\displaystyle .}
.
{\displaystyle .}
.
{\displaystyle .}
x
(
11
)
=
c
o
s
(
x
(
10
)
)
=
c
o
s
(
0
,
7442374
)
=
0
,
7356047
{\displaystyle x^{(11)}=cos(x^{(10)})=cos(0,7442374)=0,7356047}
x
(
12
)
=
c
o
s
(
x
(
11
)
)
=
c
o
s
(
0
,
7356047
)
=
0
,
7414251
{\displaystyle x^{(12)}=cos(x^{(11)})=cos(0,7356047)=0,7414251}
x
(
13
)
=
c
o
s
(
x
(
12
)
)
=
c
o
s
(
0
,
7414251
)
=
0
,
7375069
{\displaystyle x^{(13)}=cos(x^{(12)})=cos(0,7414251)=0,7375069}
.
{\displaystyle .}
.
{\displaystyle .}
.
{\displaystyle .}
x
(
41
)
=
c
o
s
(
x
(
40
)
)
=
c
o
s
(
0
,
7390852
)
=
0
,
7390851
{\displaystyle x^{(41)}=cos(x^{(40)})=cos(0,7390852)=0,7390851}
x
(
42
)
=
c
o
s
(
x
(
41
)
)
=
c
o
s
(
0
,
7390851
)
=
0
,
7390851
{\displaystyle x^{(42)}=cos(x^{(41)})=cos(0,7390851)=0,7390851}
x
(
43
)
=
c
o
s
(
x
(
42
)
)
=
c
o
s
(
0
,
7390851
)
=
0
,
7390851
{\displaystyle x^{(43)}=cos(x^{(42)})=cos(0,7390851)=0,7390851}
Verificamos que a sequência converge para o ponto fixo
x
=
0
,
7390851
{\displaystyle x=0,7390851}
.
Consideremos uma função
f
(
x
)
{\displaystyle f(x)}
com um ponto fixo em
x
∗
=
f
(
x
∗
)
{\displaystyle x^{*}=f(x^{*})}
e observamos o processo iterativo:
x
(
n
+
1
)
=
f
(
x
(
n
)
)
{\displaystyle x^{(n+1)}=f(x^{(n)})}
x
(
0
)
=
x
{\displaystyle x^{(0)}=x}
Sendo possível a função
f
(
x
)
{\displaystyle f(x)}
ser aproximada por seu polinômio de Taylor em torno do seu ponto fixo
x
∗
{\displaystyle x^{*}}
, obteremos:
f
(
x
)
=
f
(
x
∗
)
+
(
x
−
x
∗
)
f
′
(
x
∗
)
+
O
(
(
x
−
x
∗
)
2
)
,
n
≥
0
{\displaystyle f(x)=f(x^{*})+(x-x^{*})f'(x*)+O((x-x^{*})^{2}),n\geq 0}
f
(
x
)
=
x
∗
+
(
x
−
x
∗
)
f
′
(
x
∗
)
+
O
(
(
x
−
x
∗
)
2
)
{\displaystyle f(x)=x^{*}+(x-x^{*})f'(x*)+O((x-x^{*})^{2})}
f
(
x
)
{\displaystyle f(x)}
≈
x
∗
+
(
x
−
x
∗
)
f
′
(
x
∗
)
{\displaystyle x^{*}+(x-x^{*})f'(x^{*})}
Substituindo o polinômio de Taylor da função na relação de recorrência obteremos:
x
(
n
+
1
)
=
f
(
x
(
n
)
)
{\displaystyle x^{(n+1)}=f(x^{(n)})}
≈
x
∗
+
(
x
−
x
∗
)
f
′
(
x
∗
)
{\displaystyle x^{*}+(x-x^{*})f'(x^{*})}
Dessa forma:
(
x
(
n
+
1
)
−
x
∗
)
{\displaystyle (x^{(n+1)}-x^{*})}
≈
(
x
(
n
)
−
x
∗
)
f
′
(
x
∗
)
{\displaystyle (x^{(n)}-x^{*})f'(x^{*})}
Aplicando módulos de ambos os lados, obtemos:
|
x
(
n
+
1
)
−
x
∗
|
{\displaystyle |x^{(n+1)}-x^{*}|}
≈
|
x
(
n
)
−
x
∗
|
|
f
′
(
x
∗
)
|
{\displaystyle |x^{(n)}-x^{*}||f'(x^{*})|}
Podemos obter algumas conclusões através desta relação:
Se
|
f
′
(
x
)
|
{\displaystyle |f'(x)|}
<
1
{\displaystyle 1}
a distância entre
x
(
n
)
{\displaystyle x^{(n)}}
e o ponto fixo
x
∗
{\displaystyle x^{*}}
está diminuindo a cada passo.
Se
|
f
′
(
x
)
|
{\displaystyle |f'(x)|}
>
1
{\displaystyle 1}
a distância entre
x
(
n
)
{\displaystyle x^{(n)}}
e o ponto fixo
x
∗
{\displaystyle x^{*}}
está aumentando a cada passo.
Se
|
f
′
(
x
)
|
=
1
{\displaystyle |f'(x)|=1}
a aproximação de primeira ordem não é suficiente para comprender o comportamento da sequência.
Ao utilizar este método na prática, o valor do ponto fixo
x
∗
{\displaystyle x^{*}}
normalmente não é conhecido. Por conseguinte , o erro €
=
|
x
(
n
)
−
x
∗
|
{\displaystyle =|x^{(n)}-x^{*}|}
precisa ser calculado tendo como referência os valores obtidos para
x
(
n
)
{\displaystyle x^{(n)}}
. Uma ferramenta frequentemente usada para estudar a evolução da diferença entre dois elementos da sequência é:
Δ
n
=
|
x
(
n
+
1
)
−
x
(
n
)
|
{\displaystyle \Delta _{n}=|x^{(n+1)}-x^{(n)}|}
observando que
x
∗
=
lim
n
→
∞
x
(
n
)
{\displaystyle x^{*}=\lim _{n\to \infty }x^{(n)}}
x
∗
−
x
(
N
)
=
(
x
(
N
+
1
)
−
x
(
N
)
)
+
(
x
(
N
+
2
)
−
x
(
N
+
1
)
)
+
(
x
(
N
+
3
)
−
x
(
N
+
2
)
)
+
.
.
.
{\displaystyle x^{*}-x^{(N)}=(x^{(N+1)}-x^{(N)})+(x^{(N+2)}-x^{(N+1)})+(x^{(N+3)}-x^{(N+2)})+...}
=
∑
k
=
0
∞
(
x
(
N
+
k
+
1
)
−
x
(
N
+
k
)
)
{\displaystyle =\sum _{k=0}^{\infty }(x^{(N+k+1)}-x^{(N+k)})}
Usando também as expressões:
x
(
n
+
1
)
{\displaystyle x^{(n+1)}}
≈
x
∗
+
(
x
(
n
)
−
x
∗
)
f
′
(
x
∗
)
{\displaystyle x^{*}+(x^{(n)}-x^{*})f'(x^{*})}
x
(
n
)
{\displaystyle x^{(n)}}
≈
x
∗
+
(
x
(
n
−
1
)
−
x
∗
)
f
′
(
x
∗
)
{\displaystyle x^{*}+(x^{(n-1)}-x^{*})f'(x^{*})}
Subtraindo uma expressão da outra:
x
(
n
+
1
)
−
x
(
n
)
{\displaystyle x^{(n+1)}-x^{(n)}}
≈
(
x
(
n
)
−
x
(
n
−
1
)
)
f
′
(
x
∗
)
{\displaystyle (x^{(n)}-x^{(n-1)})f'(x^{*})}
Dessa maneira:
x
(
N
+
k
+
1
)
−
x
(
N
+
k
)
{\displaystyle x^{(N+k+1)}-x^{(N+k)}}
≈
(
x
(
N
+
1
)
−
x
(
N
)
)
(
f
′
(
x
∗
)
)
k
{\displaystyle (x^{(N+1)}-x^{(N)})(f'(x^{*}))^{k}}
E obtemos:
x
∗
−
x
(
N
)
=
{\displaystyle x^{*}-x^{(N)}=}
∑
k
=
0
∞
(
x
(
N
+
k
+
1
)
−
x
(
N
+
k
)
)
{\displaystyle \sum _{k=0}^{\infty }(x^{(N+k+1)}-x^{(N+k)})}
x
∗
−
x
(
N
)
{\displaystyle x^{*}-x^{(N)}}
≈
∑
k
=
0
∞
(
x
(
N
+
1
)
−
x
(
N
)
)
(
f
′
(
x
∗
)
)
k
{\displaystyle \sum _{k=0}^{\infty }(x^{(N+1)}-x^{(N)})(f'(x^{*}))^{k}}
x
∗
−
x
(
N
)
{\displaystyle x^{*}-x^{(N)}}
≈
(
x
(
N
+
1
)
−
x
(
N
)
)
{\displaystyle (x^{(N+1)}-x^{(N)})}
(
1
1
−
f
′
(
x
∗
)
)
,
{\displaystyle \left({1 \over 1-f'(x^{*})}\right),}
|
f
′
(
x
∗
)
|
{\displaystyle |f'(x^{*})|}
<
1
{\displaystyle 1}
Aplicando o módulo, obtemos:
|
x
∗
−
x
(
n
)
|
{\displaystyle |x^{*}-x^{(n)}|}
≈
|
x
(
N
+
1
)
−
x
(
N
)
|
{\displaystyle |x^{(N+1)}-x^{(N)}|}
(
1
1
−
f
′
(
x
∗
)
)
{\displaystyle \left({1 \over 1-f'(x^{*})}\right)}
€N ≈
(
Δ
N
1
−
f
′
(
x
∗
)
)
{\displaystyle \left({\Delta _{N} \over 1-f'(x^{*})}\right)}
Ao analisarmos a relação
x
(
n
+
1
)
−
x
(
n
)
{\displaystyle x^{(n+1)}-x{(n)}}
≈
(
x
(
n
)
−
x
(
n
−
1
)
)
f
′
(
x
∗
)
{\displaystyle (x^{(n)}-x^{(n-1)})f'(x^{*})}
, podemos concluir:
Quando
f
′
(
x
∗
)
{\displaystyle f'(x^{*})}
<
0
{\displaystyle 0}
, o esquema é alternante e o erro €N pode ser estimado diretamente da diferença
Δ
N
.
{\displaystyle \Delta _{N}.}
Quando
f
′
(
x
∗
)
{\displaystyle f'(x^{*})}
>
0
{\displaystyle 0}
, o esquema é monótono e
(
1
1
−
f
′
(
x
∗
)
)
{\displaystyle \left({1 \over 1-f'(x^{*})}\right)}
>
1
{\displaystyle 1}
, pelo que o erro €N é maior que a diferença
Δ
N
{\displaystyle \Delta _{N}}
. A relação será tão mais importante quanto mais próximo da unidade for
f
′
(
x
∗
)
{\displaystyle f'(x^{*})}
, ou seja, quando mais lenta for a convergência.
Como
f
′
(
x
∗
)
{\displaystyle f'(x^{*})}
≈
(
x
(
n
+
1
)
−
x
(
n
)
x
(
n
)
−
x
(
n
−
1
)
)
{\displaystyle \left({x^{(n+1)}-x^{(n)} \over x^{(n)}-x^{(n-1)}}\right)}
, temos
|
f
′
(
x
∗
)
|
{\displaystyle |f'(x^{*})|}
≈
(
Δ
N
Δ
N
−
1
)
{\displaystyle \left({\frac {\Delta _{N}}{\Delta _{N-1}}}\right)}
E obtemos
€N ≈
(
Δ
N
1
−
Δ
N
−
1
)
{\displaystyle \left({\frac {\Delta _{N}}{1-\Delta _{N-1}}}\right)}
Obs: Deve-se exigir que
Δ
N
{\displaystyle \Delta _{N}}
<
Δ
N
−
1
{\displaystyle \Delta _{N-1}}
Referências