1.2.5 Raízes de Equações — Métodos Abertos — Método de Steffensen
1. Introdução </p>
O Método de Steffensen é uma técnica de busca de raízes de funções muito semelhante ao Método de Newton-Raphson, onde substitui a derivada da função por uma aproximação.
Como todos métodos abertos são formas variantes do Método do Ponto Fixo, abordagem utilizada por Johan Frederik Steffensen consiste em aplicar este método para encontrar uma aproximação para a derivada da função.
O Método de Steffensen, assim como o de Newton, também possui convergência quadrática, uma vez que utiliza o a fórmula de aceleração de Aitken para convergir à esta taxa usando o Ponto Fixo. </p>
2. O Processo Delta-quadrado de Aitken
Um processo iterativo que converge linearmente possui a seguinte forma:
$$\alpha-x_{i+1}=C_{i} \left( \alpha-x_{i} \right) $$
| onde . Contudo, quando $$\left | C_{i} \right | =C $$ temos que o erro assintótico é constante. Se neste processo a convergência se manter estável próximo à raiz, então a próxima iteração terá a mesma forma. Ou seja: |
$$ \alpha-x_{i+2}=C_{i} \left( \alpha-x_{i+1} \right) $$
Tratando estas expressões como um sistema linear, temos que:
$$ \alpha-x_{i+2}=C \left( \alpha-x_{i+1} \right) $$
$$ \alpha-x_{i+1}=C \left( \alpha-x_{i} \right) $$
Substituindo uma expressão na outra, obteremos:
$$ {\dfrac {\alpha-x_{i+2}}{\alpha-x_{i+1}}={\dfrac {\alpha-x_{i+1}}{\alpha-x_{i}} $$
logo, resolvendo alfa:
$$ \alpha={\dfrac {x_{i}x_{i+2}-{x_{i+1}}^{2}{x_{i+2}-2\,x_{i+1}+x_{i}}$$
A expressão acima é conhecida como “Fórmula de Aitken” e é utilizada para acelerar a convergência da sequência linear dos elementos de , e o processo de obtenção dela é conhecido como “processo delta-quadrado de Aitken”[1]. </p>
3. Desenvolvimento do Método de Laguerre (sec3)
Como uma raiz de uma função é um valor tal que , para uma função com derivada contínua, vamos supor que ela satisfaça a seguinte condição:
$$ -1 < {\dfrac {d}{dx}f \left( x \right) < 0 [/latex]
Note que esta suposição é pouco adequada, pois nem sempre é possível usarmos uma estimativa inicial próxima o suficiente da raiz para que a aproximação atinja a condição em é verdadeira. Sendo assim, poderia haver casos em que o método convergiria rápido, enquanto haveria outros casos em que ele demoraria demasiadamente.
Sendo assim, vamos tomar a definição de derivada:
[latex] {\dfrac {d}{dx}f \left( x \right) ={\dfrac {f \left( x+\Delta\,x \right) -f \left( x \right) }{\Delta\,x} $$
por conveniência, tomamos na Equação 8,
$$ {\dfrac {d}{dx}f \left( x \right) ={\dfrac {f \left( x+h \right) -f \left( x \right) }{h} $$
Para atingirmos a condição requerida no começo desta seção, usamos o intervalo em tal que
$$ h=f \left( x \right) $$
Note que esta aproximação é aplicada sucessivas vezes no processo iterativo é o Método do Ponto Fixo. Como dito na introdução deste artigo, usamos este método para aproximar a derivada da função:
$$ {\dfrac {d}{dx}f \left( x_{i} \right) ={\dfrac {f \left( x_{i}+h \right) -f \left( x_{i} \right) }{h} = {\dfrac {f \left( x_{i}+f \left( x_{i}\right) \right) -f \left( x_{i} \right) }{f \left( x_{i} \right) } $$
Pelo método de Newton-Raphson, temos:
$$ x_{i+1}=x_{i}-{\dfrac {f \left( x_{i} \right) }{\dfrac {d}{dx}f \left( x_{i} \right) }$$
Aplicando a aproximação da derivada na expressão acima, obtemos:
$$ x_{i+1}=x_{i}-{\dfrac { \left( f \left( x_{i} \right) \right) ^{2}{f \left( x_{i}+f \left( x_{i} \right) \right) -f \left( x_{i} \right) }$$
$$ x_{i+2}=x_{i+1}-{\dfrac { \left( f \left( x_{i+1} \right) \right) ^{2}{f \left( x_{i+1}+f \left( x_{i+1} \right) \right) -f \left( x_{i+1}\right) } $$
Para evitar o problema da convergência citado, usaremos o processo do Delta-quadrado, demonstrado na Seção 2:
$$ \alpha={\dfrac {x_{i}x_{i+2}-{x_{i+1}}^{2}{x_{i+2}-2\,x_{i+1}+x_{i}} $$
O processo de Aitken aplicado às Equações 13 e 14 nos fornece uma nova aproximação tal que
$$ x_{i+3} = \alpha={\dfrac {x_{i}x_{i+2}-{x_{i+1}}^{2}{x_{i+2}-2\,x_{i+1}+x_{i}} $$
</p>
4. Implementação
def Steffensen(f, x0=1.0, errto=0.001, imax=100):
"""
Return the root of a function (using the Steffensen Method)
Steffensen(f, x0=1.0, errto=0.001, imax=100)
* f: Function where find the roots
* x0: next point (estimative)
* errto: tolerated error
* imax: max of iterations allowed
return: the root next x0
Author: Pedro Garcia <sawp @sawp.com.br>
see: http://www.sawp.com.br
License: Creative Commons
<http ://creativecommons.org/licenses/by-nc-nd/2.5/br/>
Dec 2009
"""
errno = errto + 1
iterCount = 0
x2 = 0
while errno > errto and iterCount < imax:
h1 = f(x0)
t1 = f(x0 + h1)
if fabs(t1 - h1) != 0:
x1 = x0 - h1*h1/(t1 - h1)
else:
x2 = x0
break
h2 = f(x1)
t2 = f(x1 + h2)
if fabs(t2 - h2) != 0:
x2 = x1 - h2*h2/(t2 - h2)
else:
break
# try Aitkens optimization
if (x2 - 2*x1 + x0) != 0:
alpha = (x0*x2 - x1*x1)/(x2 - 2*x1 + x0)
C1 = fabs((alpha - x1)/(alpha - x0))
C2 = fabs((alpha - x2)/(alpha - x1))
if (C1 < 1) and (C2 < 1):
x2 = alpha
iterCount += 1
if x2 != 0:
errno = fabs((x2-x0)/x2)
x0 = x2
return x2
</sawp></div>
Note que no código acima o delta-quadrado só é usado sob certas condições. Isto se dá porque nem sempre é possível utilizar o processo, uma vez que ele requer que a constante C obedeça à certas condições, mencionadas na Seção 2.
Outro fator a ser observado neste código, que não foi mencionado no desenvolvimento do texto, é a inserção das variáveis t1 e t2 , que servem para avaliar a variação da aproximação em torno de um ponto. Quando esta variação é muito pequena, podemos tomar como sendo o limite naquele ponto.
Um exemplo da utilização desta função pode ser encontrado em: http://www.sawp.com.br/code/rootfind/steffensen.py
</p>
5. Conclusão
Como visto, o Método de Steffensen utiliza uma aproximação numérica para a derivada e a aplica no método de Newton. O resultado disto é uma fórmula que também possui convergência quadrática, mas que não requer a função derivada, sendo uma opção muito mais abrangente ao ser programada. O ponto fraco deste método está na estimativa inicial. Assim como no método do Ponto Fixo, pode ocorrer da sequência não convergir ao longo da execução, devido à suposição de que $$h=f(x) $$ . Para tentar evitar este comportamento, aplicamos a Fórmula de Aitken no programa. Contudo, para iterações onde a ordem de convergência é maior que um, ela não deveria ser usada, pois ela surge de uma suposição de que a sequência é linear.
Caso seja necessário implementar aceleração de convergência para sequências não-lineares, uma bibliografia a ser consultada é “Iterative Methods for Solution of Equations’‘[2].
</p> </p>
6. Copyright
Este documento é disponível sob a licença Creative Commons. As regras dos direitos de cópia deste conteúdo estão acessíveis em http://creativecommons.org/licenses/by-nc-nd/2.5/br/.
</center>