1.2.6 Raízes de Equações – Métodos Abertos – Método de Householder
1. Introdução
Assim como o Método de Newton exige a derivada de primeira ordem e apresenta uma taxa de convergência quadrática; o Método de Halley leva a primeira e segunda derivada e possui convergência cúbica; o Método de Householder é um algoritmo de busca de raízes que permite que as iterações convirjam a uma taxa , uma vez que sejam utilizadas derivadas, onde é a ordem do método.
Por isso, dizemos que o Método de Householder é uma generalização do Método de Newton. Desta forma, esse utiliza a função de iteração de Householder de ordem um, enquanto o Método de Halley utiliza a de ordem dois.
O algoritmo de Householder é muito importante, uma vez que nos fornece um recurso para construirmos funções de iteração com velocidades de aproximação arbitrárias, adaptadas para cada caso necessário. Além disso, a partir desse método é possível criar técnicas cujas raízes sempre serão encontradas, pois as múltiplas derivadas favorecem a convergência absoluta, independente da aproximação inicial.
2. Desenvolvimento do Método
Seja a aproximação de Padé de ordem da função no ponto dada pela função racional:
$$ \left| f \left( x \right) -{\frac {A_{n} \left( x \right) }{B_{m} \left( x \right) } \right| =O \left( \left( x-\alpha \right) ^{v} \right) $$
onde v é tão grande quanto possível. Neste caso, as funções e são polinômios de ordem n e m que também aproximam . Esta é a fórmula de Padé, e que nos permite refinar a aproximação de por polinômios de Taylor sempre que e .
Representando a função através de uma aproximação de Padé de ordem , cujos polinômios e são tais que o numerador seja uma função linear, enquanto o denominador seja um polinômio de Taylor de ordem . Desta forma, temos a seguinte relação:
$$ f \left( x+h \right) ={\frac {a_{0}+h}{b_{0}+b_{1}h+ \cdots + b_{d-1}{h}^{d-1}}+O \left( {h}^{d+1} \right) $$
Note que a função racional tem um zero trivial quando .
Para um polinômio de Taylor que possua coeficientes dependentes de , também temos a aproximação de Padé com coeficientes dependentes de e suas derivadas, com .
Agora vamos aproximar uma função tal que por polinômios de Taylor, tal que $g \left( x \right) = \left( f \left( x \right) \right) ^{-1}$. Com isso, obteremos a seguinte aproximação:
$$ g \left( x+h \right) =g \left( x \right) + \left( {\frac {d}{dx}g \left( x \right) \right) h + \ldots + {\dfrac { \left( {\frac {d^{d-1}{d{x}^{d-1}}g \left( x \right) \right) {h}^{d-1}{ \left( d-1 \right) !}+{\dfrac { \left( {\frac {d^{d}{d{x}^{d}}g \left( x \right) \right) {h}^{d}{d!}+O \left( {h}^{d+1}\right)$$
Multiplicando 3 por , e dividindo tudo por após substituir o erro da série de Taylor na aproximação de Padé, obteremos:
$$ b_{d}={\dfrac {a_{0}{\dfrac {d^{d}{d{x}^{d}}g \left( x \right) }{d!} + {\dfrac {\dfrac {d^{d-1}{d{x}^{d-1}}g \left( x \right) }{ \left( d-1\right)!}$$
Resolvendo a Equação 4 para , temos:
$$ h={\frac {d! {\dfrac {d^{d-1}{d{x}^{d-1}}g \left( x \right)}{ \left( d-1 \right) !\,{\dfrac {d^{d}{d{x}^{d}}g \left( x \right) } = {d \frac {\dfrac {d^{d-1}{d{x}^{d-1}}g \left( x \right) }{\dfrac {d^{d}{d{x}^{d}}g \left( x \right) } $$
A Equação 5 implica na fórmula iterativa:
$$ x_{n+1}=x_{n}+{d \dfrac {\dfrac {d^{d-1}{d{x}^{d-1}}g \left( x \right) }{\dfrac {d^{d}{d{x}^{d}}g \left( x \right) } $$
Como tomamos , a Equação 6 reescrita em termos da função cuja raiz queremos
encontrar fica:
$$ x_{n+1}=x_{n}+{d \dfrac {\dfrac {d^{d-1}{d{x}^{d-1}} \left( \dfrac{1}{f(x)}\right) }{\dfrac {d^{d}{d{x}^{d}}\left( \dfrac{1}{f(x)} \right) } $$
A Equação 7 é a expressão do Método de Householder que gera as funções de iteração para busca de zeros da função , convergindo com taxa . </p>
3. Implicações do Método de Householder
Para as ordens mais baixas do Método de Householder, observamos que as fórmulas iterativas obtidas implicam em expressões de alguns métodos bem conhecidos.
Por exemplo, para a fórmula de Householder de primeira ordem , ou seja, , temos:
$$ x_{n+1}=x_{n}+{\dfrac {1}{f \left( x \right) {\dfrac {d}{dx} \left( \left( f \left( x \right) \right) ^{-1} \right) } = x_{n}-{\frac {f \left( x \right) }{\dfrac {d}{dx}f \left( x \right) } $$
A Expressão 8 é exatamente aquela obtida pelo Método de Newton, por isso ele é considerado o Método de Householder de primeira ordem.
Aplicando uma ordem a mais de derivação em (7), temos que nos fornece:
$$ x_{n+1}=x_{n}+2\,{\frac {\dfrac {d}{dx} \left( \left( f \left( x \right) \right) ^{-1} \right) }{\dfrac {d^{2}{d{x}^{2}} \left( \left( f \left( x \right) \right) ^{-1} \right) } $$
que é exatamente a função de iteração utilizada pelo Método de Halley:
$$ x_{n+1}=x_{n}+2\,{\frac {f \left( x \right) {\dfrac {d}{dx}f \left( x \right) }{-2\, \left( {\dfrac {d}{dx}f \left( x \right) \right) ^{2}+ \left( {\dfrac {d^{2}{d{x}^{2}}f \left( x \right) \right) f \left( x \right) } $$
Para ordens mais altas, obtemos expressões mais complexas, muitas vezes de difícil implementação prática, sendo que o método discutido neste trabalho costuma fornecer maior auxílio no desenvolvimento teórico de outros métodos.
A complexidade das expressões geradas para ordens elevadas do Método de Householder pode ser visualizada já a partir do terceiro grau de derivação. Alguns exemplos:
Ordem3
$$ x_{n+1}=x_{n}+3\,{\dfrac { \left( -2\, \left( {\dfrac {d}{dx}f \left( x \right) \right) ^{2}+ \left( {\dfrac {d^{2}{d{x}^{2}}f \left( x \right) \right) f \left( x \right) \right) f \left( x \right) }{6\, \left( {\dfrac {d}{dx}f \left( x \right) \right) ^{3}- 6\, \left( {\dfrac {d}{dx}f \left( x \right) \right) \left( {\dfrac { d^{2}{d{x}^{2}}f \left( x \right) \right) f \left( x \right) + \left( {\dfrac {d^{3}{d{x}^{3}}f \left( x \right) \right) \left( f \left( x \right) \right) ^{2}} $$
4. Detalhes de Implementação
A natureza do Método de Householder o torna difícil de ser generalizado em uma implementação real, uma vez que obter uma derivada de ordem arbitrária numericamente não é uma tarefa trivial.
Uma abordagem que pode ser usada consiste em utilizar artifícios que aproximem numericamente as derivadas através de interpolações e outras técnicas numéricas. Todavia, este tratamento, na maioria das vezes, não produz um resultado satisfatório. Sendo assim, neste artigo não será apresentado nenhuma implementação deste método. </p>
5. 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/.