El método del jefe de familia

Class of mathematical root-finding algorithm

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 cierto orden d + 1 . Cada uno de estos métodos se caracteriza por el número d , que se conoce como 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 .

Método

El método del amo de casa es un algoritmo numérico para resolver la ecuación f ( x ) = 0 . En este caso, la función f tiene que ser función de una variable real. El método consta de 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 suposición inicial x ₀ . ^[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 una vecindad de a , las iteraciones x _n satisfacen: ^{[ cita necesaria ]}

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

Esto significa que las iteraciones convergen a cero si la estimación inicial es lo suficientemente cercana y que la convergencia tiene orden d + 1 o mejor. Además, cuando está lo suficientemente cerca de a , suele ocurrir que para algunos . En particular, ${\displaystyle x_{n+1}-a\approx C(x_{n}-a)^{d+1}}$ ${\displaystyle 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 a 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 d grande . El índice de Ostrowski expresa la reducción de errores en el número de evaluaciones de funciones 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 polinómicas. Dado que n ( d + 1) evaluaciones en n iteraciones dan un exponente de error de ( d + 1) ⁿ , el exponente para la evaluación de una función es , numéricamente, 1,4142 , 1,4422 , 1,4142 , 1,3797 para d = 1, 2, 3, 4 , y caer después de eso. Según este criterio, el caso d =2 ( método de Halley ) es el valor óptimo de d . ${\displaystyle {\sqrt[{d+1}]{d+1}}}$
• Para funciones generales, la evaluación de derivadas utilizando la aritmética de Taylor de diferenciación automática requiere el equivalente de evaluaciones de funciones ( d + 1)( d + 2)/2 . Por lo tanto, la evaluación de una función reduce el error en un exponente de , que es para el método de Newton, para el método de Halley y cae 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}}\approx 1.2599}$ ${\displaystyle {\sqrt[{6}]{3}}\approx 1.2009}$

Motivación

Primer enfoque

Supongamos que f es analítica en una vecindad de a y f ( a ) = 0 . Entonces f tiene una serie de Taylor en a y su término constante es cero. Debido a que 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. Debido a que 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 ${\displaystyle \sum _{k=0}^{+\infty }{\frac {c_{k}(x-a)^{k}}{k!}}}$

$${\displaystyle {\frac {1}{f}}={\frac {c_{0}}{x-a}}+\sum _{k=1}^{+\infty }{\frac {c_{k}(x-a)^{k-1}}{k~(k-1)!}}\,.}$$

dk = 1, ..., d

$${\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)\,,}$$

notación O grande

$${\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)\,.}$$

afxda ${\displaystyle x+d~{\frac {(1/f)^{(d-1)}}{(1/f)^{(d)}}}}$

Segundo enfoque

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.

Los métodos de orden inferior.

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}}}}$

resulta en

${\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, está 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 simple de Newton. ${\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.

Ejemplo

El primer problema resuelto por Newton con el método de Newton-Raphson-Simpson fue la ecuación polinómica . Observó que debería haber una solución cercana a 2. Reemplazar y = x + 2 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 esta última serie de potencias . Para los primeros pedidos 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 correctos 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 77 715 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 usando 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 })}$

Derivación

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 la aproximante 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 dependientes de f y sus derivadas. Más precisamente, en cualquier aproximante de Padé, los grados de los polinomios del numerador y del denominador deben sumarse al orden del aproximante. Por tanto, hay que aguantar. ${\displaystyle b_{d}=0}$

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

${\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, obtenemos después de multiplicar por 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, resolver la última ecuación para el cero del numerador da como resultado ${\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})}}}$.

Relación con el método de Newton

El método del amo de casa 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 modificaciones y d = 2 da el método de Halley.

Referencias

1. Jefe de familia, Alston Scott (1970). "El tratamiento numérico de una única ecuación no lineal ". McGraw-Hill. pag. 169.ISBN​ 0-07-030465-3.
2. Ostrowski, AM (1966). Solución de Ecuaciones y Sistemas de Ecuaciones . Matemática Pura y Aplicada. vol. 9 (Segunda ed.). Nueva York: Academic Press.

enlaces externos

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