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 algún 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 .
Método
El método de Householder es un algoritmo numérico para resolver la ecuación no lineal 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
comenzando con una suposición inicial x 0 . [1]
Si f es una función continuamente diferenciable d + 1 veces y a es cero de f pero no de su derivada, entonces, en una vecindad de a , las iteraciones x n satisfacen: [ cita requerida ]
- , para algunos
Esto significa que las iteraciones convergen al cero si la suposición inicial es lo suficientemente cercana y que la convergencia tiene el orden d + 1 .
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 en el esfuerzo para d grandes . 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 usando el método de Horner tiene un esfuerzo de evaluaciones polinomiales d + 1 . Dado que n ( d + 1) evaluaciones sobre n iteraciones dan un exponente de error de ( d + 1) n , 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 cayendo después de eso. Según este criterio, el caso d = 2 ( método de Halley ) es el valor óptimo de d .
- Para funciones generales, la evaluación de la derivada usando la aritmética de Taylor de diferenciación automática requiere el equivalente de ( d + 1) ( d + 2) / 2 evaluaciones de funciones. Por tanto, la evaluación de una función reduce el error en un exponente de, cual es para el método de Newton, para el método de Halley y caer hacia 1 o convergencia lineal para los métodos de orden superior.
Motivación
Primer enfoque
Una idea aproximada del método Householder se deriva de la serie geométrica . Deje el verdadero -valued, continuamente diferenciable función f (x) tener un simple cero en x = una , que es una raíz f ( un ) = 0 de una multiplicidad, que es equivalente a. Entonces 1 / f ( x ) tiene una singularidad en una , específicamente un polo simple (también de una multiplicidad), y cerca de un comportamiento de 1 / f ( x ) está dominado por 1 / ( x - una ) . Aproximadamente, uno obtiene
Aquí porque a es un cero simple de f ( x ) . El coeficiente de grado d tiene el valor. Por lo tanto, ahora se puede reconstruir el cero a dividiendo el coeficiente de grado d - 1 por el coeficiente de grado d . Dado que esta serie geométrica es una aproximación a la expansión de Taylor de 1 / f ( x ) , se pueden obtener estimaciones del cero de f ( x ) , ahora sin conocimiento previo de la ubicación de este cero, dividiendo los coeficientes correspondientes del Expansión de Taylor de 1 / f ( x ) o, más generalmente, 1 / f ( b + x ) . De ahí se obtiene, para cualquier entero d , y si existen las derivadas correspondientes,
Segundo enfoque
Suponga 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 :
Por el teorema de König , tenemos:
Esto sugiere que la iteración Householder podría ser una buena iteración convergente. La prueba real de la convergencia también se basa en esta idea.
Los métodos de orden inferior
El método de los jefes de hogar de orden 1 es solo el método de Newton , ya que:
Para el método de Householder de orden 2, se obtiene el método de Halley , ya que las identidades
y
resulta en
En la última línea es 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.
El método de tercer orden se obtiene a partir de la identidad de la derivada de tercer orden de 1 / f
y tiene la formula
y así.
Ejemplo
El primer problema que resolvió Newton con el método de Newton-Raphson-Simpson fue la ecuación polinomial . Observó que debería haber una solución cercana a 2. Reemplazar y = x + 2 transforma la ecuación en
- .
La serie de Taylor de la función recíproca comienza con
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 pedidos, se obtienen los siguientes valores después de un solo paso de iteración: Por ejemplo, en el caso del tercer orden,.
D | x 1 |
---|---|
1 | 0,1 00000000000000000000000000000000 |
2 | 0,094 339622641509433962264150943396 |
3 | 0.09455 8429973238180196253345227475 |
4 | 0.094551 282051282051282051282051282 |
5 | 0.09455148 6538216154140615031261962 |
6 | 0.094551481 438752142436492263099118 |
7 | 0.09455148154 3746895938379484125812 |
8 | 0.0945514815423 36756233561913325371 |
9 | 0.09455148154232 4837086869382419375 |
10 | 0.094551481542326 678478801765822985 |
Como se puede ver, hay un poco más de d lugares 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 77715 77578 .
Calculemos el valores para algún orden más bajo,
Y usando las siguientes relaciones,
- 1er orden;
- Segundo orden;
- 3er orden;
X | 1 ° (Newton) | 2do (Halley) | 3er orden | 4to orden |
---|---|---|---|---|
x 1 | 0. 100000000000000000000000000000000 | 0,094 339622641509433962264150943395 | 0.09455 8429973238180196253345227475 | 0,094551 28205128 |
x 2 | 0.0945 68121104185218165627782724844 | 0.09455148154 0164214717107966227500 | 0.094551481542326591482 567319958483 | |
x 3 | 0.094551481 698199302883823703544266 | 0.094551481542326591482386540579303 | 0.094551481542326591482386540579303 | |
x 4 | 0.0945514815423265914 96064847153714 | 0.094551481542326591482386540579303 | 0.094551481542326591482386540579303 | |
x 5 | 0.094551481542326591482386540579303 | |||
x 6 | 0.094551481542326591482386540579303 |
Derivación
Una derivación exacta de los métodos de Householder comienza con la aproximación de Padé de orden d + 1 de la función, donde se elige la aproximante con numerador lineal . Una vez que se ha logrado esto, la actualización para la siguiente aproximación resulta de calcular el cero único del numerador.
La aproximación de Padé tiene la forma
La función racional tiene un cero en .
Así como el polinomio de Taylor de grado d tiene coeficientes d + 1 que dependen de la función f , la aproximación de Padé también tiene coeficientes d + 1 dependientes de f y sus derivadas. Más precisamente, en cualquier aproximante de Padé, los grados de los polinomios numerador y denominador deben sumarse al orden de la aproximante. Por lo tanto, tiene que aguantar.
Se podría determinar el aproximado de Padé a partir del polinomio de Taylor de f usando 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
tiene que ser igual a la inversa de la función racional deseada, obtenemos después de multiplicar con en el poder la ecuacion
- .
Ahora, resolviendo la última ecuación para el cero del numerador da como resultado
- .
Esto implica la fórmula de iteració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 ) :
con
En particular, d = 1 da el método de Newton sin modificar y d = 2 da el método de Halley.
Referencias
- ^ 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.
- ^ Ostrowski, AM (1966). Solución de ecuaciones y sistemas de ecuaciones . Matemática pura y aplicada. 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.