El método del jefe de familia

En matemáticas , y más específicamente en análisis numérico , los métodos de Householder son una clase de algoritmos de búsqueda de raíces que se utilizan para funciones de una variable real con derivadas continuas hasta un cierto orden d + 1. Cada uno de estos métodos se caracteriza por el número d , que se conoce como el orden del método. El algoritmo es iterativo y tiene una tasa de convergencia de d + 1 .

Estos métodos llevan el nombre del matemático estadounidense Alston Scott Householder .

El método de Householder es un algoritmo numérico para resolver la ecuación f ( x ) = 0 . En este caso, la función f tiene que ser una función de una variable real. El método consiste en una secuencia de iteraciones

${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$

comenzando con una estimación inicial x _0. ^[1 ]

Si f es una función d + 1 veces continuamente diferenciable y a es un cero de f pero no de su derivada, entonces, en un entorno de a , las iteraciones x _n satisfacen: ^{[ cita requerida ]}

${\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{d+1}}$, para algunos${\displaystyle K>0.\!}$

Esto significa que las iteraciones convergen al cero si la estimación inicial es lo suficientemente cercana y que la convergencia tiene un orden d + 1 o mejor. Además, cuando está lo suficientemente cerca de a , es común que para algún . En particular, ${\displaystyle x_{n+1}-a\approx C(x_{n}-a)^{d+1}}$${\estilo de visualización C\neq 0}$

• si d + 1 es par y C > 0 entonces la convergencia a a será a partir de valores mayores que a ;
• si d + 1 es par y C < 0 entonces la convergencia a a será a partir de valores menores que a ;
• si d + 1 es impar y C > 0 entonces la convergencia a a será desde el lado donde comienza; y
• Si d + 1 es impar y C < 0 entonces la convergencia hacia a alternará lados.

A pesar de su orden de convergencia, estos métodos no se utilizan ampliamente porque la ganancia en precisión no es proporcional al aumento del esfuerzo para valores grandes de d . El índice de Ostrowski expresa la reducción del error en el número de evaluaciones de la función en lugar del recuento de iteraciones. ^[2]

• Para polinomios, la evaluación de las primeras d derivadas de f en x _n utilizando el método de Horner tiene un esfuerzo de d + 1 evaluaciones de polinomios. Dado que n ( d + 1) evaluaciones en n iteraciones dan un exponente de error de ( d + 1) ⁿ , el exponente para una evaluación de función es , numéricamente 1.4142 , 1.4422 , 1.4142 , 1.3797 para d = 1, 2, 3, 4 y siguientes. Por este criterio, el caso d = 2 ( método de Halley ) es el valor óptimo de d .${\displaystyle {\sqrt[{d+1}]{d+1}}}$
• Para las funciones generales, la evaluación de la derivada mediante la aritmética de Taylor de la diferenciación automática requiere el equivalente de ( d + 1)( d + 2)/2 evaluaciones de funciones. De este modo, una evaluación de función reduce el error en un exponente de , que es para el método de Newton, para el método de Halley y disminuye hacia 1 o la convergencia lineal para los métodos de orden superior.${\displaystyle {\sqrt[{\frac {(d+1)(d+2)}{2}}]{d+1}}}$${\displaystyle {\sqrt[{3}]{2}}\aproximadamente 1,2599}$${\displaystyle {\sqrt[{6}]{3}}\aproximadamente 1,2009}$

Supóngase que f es analítica en un entorno de a y f ( a ) = 0 . Entonces f tiene una serie de Taylor en a y su término constante es cero. Como este término constante es cero, la función f ( x ) / ( x − a ) tendrá una serie de Taylor en a y, cuando f ′ ( a ) ≠ 0 , su término constante no será cero. Como ese término constante no es cero, se deduce que el recíproco ( x − a ) / f ( x ) tiene una serie de Taylor en a , que escribiremos como y su término constante c ₀ no será cero. Usando esa serie de Taylor podemos escribir Cuando calculamos su d -ésima derivada, notamos que los términos para k = 1, ..., d se desvanecen convenientemente: usando la notación O mayúscula . Por lo tanto, obtenemos que la razón Si a es el cero de f que está más cerca de x , entonces el segundo factor tiende a 1 cuando d tiende a infinito y tiende a a . ${\displaystyle \sum_{k=0}^{+\infty} {\frac {c_{k}(xa)^{k}}{k!}}}$$${\displaystyle {\frac {1}{f}}={\frac {c_{0}}{xa}}+\sum _{k=1}^{+\infty }{\frac {c_{k}(xa)^{k-1}}{k~(k-1)!}}\,.}$$$${\displaystyle \left({\frac {1}{f}}\right)^{(d)}={\frac {(-1)^{d}d!~c_{0}}{(x-a)^{d+1}}}+\sum _{k=d+1}^{+\infty }{\frac {c_{k}(x-a)^{k-d-1}}{k~(k-d-1)!}}}$$ $${\displaystyle ={\frac {(-1)^{d}d!~c_{0}}{(x-a)^{d+1}}}\left(1+{\frac {1}{(-1)^{d}d!~c_{0}}}\sum _{k=d+1}^{+\infty }{\frac {c_{k}(x-a)^{k}}{k~(k-d-1)!}}\right)}$$ $${\displaystyle ={\frac {(-1)^{d}d!~c_{0}}{(x-a)^{d+1}}}\left(1+{\mathcal {O}}\left((x-a)^{d+1}\right)\right)\,,}$$$${\displaystyle d~{\frac {(1/f)^{(d-1)}}{(1/f)^{(d)}}}=d~{\frac {(-1)^{d-1}(d-1)!~c_{0}}{(-1)^{d}d!~c_{0}}}(x-a)\left({\frac {1+{\mathcal {O}}\left((x-a)^{d}\right)}{1+{\mathcal {O}}\left((x-a)^{d+1}\right)}}\right)}$$ $${\displaystyle =-(x-a)\left(1+{\mathcal {O}}\left((x-a)^{d}\right)\right)\,.}$$${\displaystyle x+d~{\frac {(1/f)^{(d-1)}}{(1/f)^{(d)}}}}$

Supongamos que x = a es una raíz simple. Entonces, cerca de x = a , (1/ f )( x ) es una función meromórfica . Supongamos que tenemos la expansión de Taylor :

${\displaystyle (1/f)(x)=\sum _{d=0}^{\infty }{\frac {(1/f)^{(d)}(b)}{d!}}(x-b)^{d}}$

alrededor de un punto b que está más cerca de a que de cualquier otro cero de f . Por el teorema de König , tenemos:

${\displaystyle a-b=\lim _{d\rightarrow \infty }{\frac {\frac {(1/f)^{(d-1)}(b)}{(d-1)!}}{\frac {(1/f)^{(d)}(b)}{d!}}}=d{\frac {(1/f)^{(d-1)}(b)}{(1/f)^{(d)}(b)}}.}$

Estos sugieren que la iteración de Householder podría ser una buena iteración convergente. La prueba real de la convergencia también se basa en estas ideas.

El método de Householder de orden 1 es simplemente el método de Newton , ya que:

${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+1\,{\frac {\left(1/f\right)(x_{n})}{\left(1/f\right)^{(1)}(x_{n})}}\\[.7em]=&x_{n}+{\frac {1}{f(x_{n})}}\cdot \left({\frac {-f'(x_{n})}{f(x_{n})^{2}}}\right)^{-1}\\[.7em]=&x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\end{array}}}$

Para el método de Householder de orden 2 se obtiene el método de Halley , ya que las identidades

${\displaystyle \textstyle (1/f)'(x)=-{\frac {f'(x)}{f(x)^{2}}}\ }$

y

${\displaystyle \textstyle \ (1/f)''(x)=-{\frac {f''(x)}{f(x)^{2}}}+2{\frac {f'(x)^{2}}{f(x)^{3}}}}$

producir

${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+2\,{\frac {\left(1/f\right)'(x_{n})}{\left(1/f\right)''(x_{n})}}\\[1em]=&x_{n}+{\frac {-2f(x_{n})\,f'(x_{n})}{-f(x_{n})f''(x_{n})+2f'(x_{n})^{2}}}\\[1em]=&x_{n}-{\frac {f(x_{n})f'(x_{n})}{f'(x_{n})^{2}-{\tfrac {1}{2}}f(x_{n})f''(x_{n})}}\\[1em]=&x_{n}+h_{n}\;{\frac {1}{1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}}.\end{array}}}$

En la última línea se encuentra la actualización de la iteración de Newton en el punto . Esta línea se agregó para demostrar dónde radica la diferencia con el método de Newton simple. ${\displaystyle h_{n}=-{\tfrac {f(x_{n})}{f'(x_{n})}}}$${\displaystyle x_{n}}$

El método de tercer orden se obtiene a partir de la identidad de la derivada de tercer orden de 1/ f

${\displaystyle \textstyle (1/f)'''(x)=-{\frac {f'''(x)}{f(x)^{2}}}+6{\frac {f'(x)\,f''(x)}{f(x)^{3}}}-6{\frac {f'(x)^{3}}{f(x)^{4}}}}$

y tiene la fórmula

${\displaystyle {\begin{array}{rl}x_{n+1}=&x_{n}+3\,{\frac {\left(1/f\right)''(x_{n})}{\left(1/f\right)'''(x_{n})}}\\[1em]=&x_{n}-{\frac {6f(x_{n})\,f'(x_{n})^{2}-3f(x_{n})^{2}f''(x_{n})}{6f'(x_{n})^{3}-6f(x_{n})f'(x_{n})\,f''(x_{n})+f(x_{n})^{2}\,f'''(x_{n})}}\\[1em]=&x_{n}+h_{n}{\frac {1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}{1+(f''/f')(x_{n})\,h_{n}+{\frac {1}{6}}(f'''/f')(x_{n})\,h_{n}^{2}}}\end{array}}}$

etcétera.

El primer problema que Newton resolvió con el método Newton-Raphson-Simpson fue la ecuación polinómica . Observó que debería haber una solución cercana a 2. Reemplazando y = x + 2 se transforma la ecuación en ${\displaystyle y^{3}-2y-5=0}$

${\displaystyle 0=f(x)=-1+10x+6x^{2}+x^{3}}$.

La serie de Taylor de la función recíproca comienza con

${\displaystyle {\begin{array}{rl}1/f(x)=&-1-10\,x-106\,x^{2}-1121\,x^{3}-11856\,x^{4}-125392\,x^{5}\\&-1326177\,x^{6}-14025978\,x^{7}-148342234\,x^{8}-1568904385\,x^{9}\\&-16593123232\,x^{10}+O(x^{11})\end{array}}}$

El resultado de aplicar los métodos de Householder de varios órdenes en x = 0 también se obtiene dividiendo los coeficientes vecinos de la última serie de potencias . Para los primeros órdenes se obtienen los siguientes valores después de un solo paso de iteración: Por ejemplo, en el caso del tercer orden, . ${\displaystyle x_{1}=0.0+106/1121=0.09455842997324}$

Como se puede ver, hay un poco más de d decimales correctas para cada orden d. Los primeros cien dígitos de la solución correcta son 0,09455 14815 42326 59148 23865 40579 30296 38573 06105 62823 91803 04128 52904 53121 89983 48366 71462 67281 77715 77578 .

Calculemos los valores para algún orden más bajo, ${\displaystyle x_{2},x_{3},x_{4}}$

${\displaystyle f=-1+10x+6x^{2}+x^{3}}$

${\displaystyle f^{\prime }=10+12x+3x^{2}}$

${\displaystyle f^{\prime \prime }=12+6x}$

${\displaystyle f^{\prime \prime \prime }=6}$

Y utilizando las siguientes relaciones,

1er orden;${\displaystyle x_{i+1}=x_{i}-f(x_{i})/f^{\prime }(x_{i})}$

2do orden;${\displaystyle x_{i+1}=x_{i}-2ff^{\prime }/(2{f^{\prime }}^{2}-ff^{\prime \prime })}$

3er orden;${\displaystyle x_{i+1}=x_{i}-(6f{f^{\prime }}^{2}-3f^{2}f^{\prime \prime })/(6{f^{\prime }}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}$

Una derivación exacta de los métodos de Householder parte de la aproximación de Padé de orden d +1 de la función, donde se elige el aproximador con numerador lineal . Una vez logrado esto, la actualización para la siguiente aproximación resulta del cálculo del cero único del numerador.

La aproximación de Padé tiene la forma

${\displaystyle f(x+h)={\frac {a_{0}+h}{b_{0}+b_{1}h+\cdots +b_{d-1}h^{d-1}}}+O(h^{d+1}).}$

La función racional tiene un cero en . ${\displaystyle h=-a_{0}}$

Así como el polinomio de Taylor de grado d tiene d + 1 coeficientes que dependen de la función f , la aproximación de Padé también tiene d + 1 coeficientes que dependen de f y sus derivadas. Más precisamente, en cualquier aproximación de Padé, los grados de los polinomios del numerador y del denominador tienen que sumar el orden de la aproximación. Por lo tanto, tiene que cumplirse. ${\displaystyle b_{d}=0}$

Se podría determinar la aproximación de Padé a partir del polinomio de Taylor de f utilizando el algoritmo de Euclides . Sin embargo, a partir del polinomio de Taylor de 1/ f es más corto y conduce directamente a la fórmula dada. Dado que

${\displaystyle (1/f)(x+h)=(1/f)(x)+(1/f)'(x)h+\cdots +(1/f)^{(d-1)}(x){\frac {h^{d-1}}{(d-1)!}}+(1/f)^{(d)}(x){\frac {h^{d}}{d!}}+O(h^{d+1})}$

tiene que ser igual a la inversa de la función racional deseada, que obtenemos después de multiplicar con en la potencia la ecuación ${\displaystyle a_{0}+h}$${\displaystyle h^{d}}$

${\displaystyle 0=b_{d}=a_{0}(1/f)^{(d)}(x){\frac {1}{d!}}+(1/f)^{(d-1)}(x){\frac {1}{(d-1)!}}}$.

Ahora, al resolver la última ecuación para el cero del numerador, obtenemos ${\displaystyle h=-a_{0}}$

${\displaystyle {\begin{aligned}h&=-a_{0}={\frac {{\frac {1}{(d-1)!}}(1/f)^{(d-1)}(x)}{{\frac {1}{d!}}(1/f)^{(d)}(x)}}\\&=d\,{\frac {(1/f)^{(d-1)}(x)}{(1/f)^{(d)}(x)}}\end{aligned}}}$.

Esto implica la fórmula de iteración

${\displaystyle x_{n+1}=x_{n}+d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{n})}}}$.

El método de Householder aplicado a la función de valor real f ( x ) es el mismo que el método de Newton aplicado a la función g ( x ) :

${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}$

con

${\displaystyle g(x)=\left|(1/f)^{(d-1)}\right|^{-1/d}\,.}$

En particular, d = 1 da el método de Newton sin modificar y d = 2 da el método de Halley.

• Pascal Sebah y Xavier Gourdon (2001). "El método de Newton y la iteración de alto orden". Nota : utilice la versión PostScript de este enlace; la versión del sitio web no está compilada correctamente.