En análisis numérico , el polinomio de Wilkinson es un polinomio específico que fue utilizado por James H. Wilkinson en 1963 para ilustrar una dificultad al encontrar la raíz de un polinomio: la ubicación de las raíces puede ser muy sensible a las perturbaciones en los coeficientes del polinomio.
El polinomio es
A veces, el término polinomio de Wilkinson también se usa para referirse a otros polinomios que aparecen en la discusión de Wilkinson.
Fondo
El polinomio de Wilkinson surgió en el estudio de algoritmos para encontrar las raíces de un polinomio
Es una cuestión natural en el análisis numérico preguntarse si el problema de encontrar las raíces de p a partir de los coeficientes c i está bien condicionado . Es decir, esperamos que un pequeño cambio en los coeficientes lleve a un pequeño cambio en las raíces. Desafortunadamente, este no es el caso aquí.
El problema está mal condicionado cuando el polinomio tiene una raíz múltiple. Por ejemplo, el polinomio x 2 tiene una raíz doble en x = 0. Sin embargo, el polinomio x 2 - ε (una perturbación de tamaño ε ) tiene raíces en ± √ ε , que es mucho más grande que ε cuando ε es pequeño.
Por lo tanto, es natural esperar que también ocurra un mal condicionamiento cuando el polinomio tiene ceros que están muy cerca. Sin embargo, el problema también puede estar extremadamente mal condicionado para polinomios con ceros bien separados. Wilkinson usó el polinomio w ( x ) para ilustrar este punto (Wilkinson 1963).
En 1984, describió el impacto personal de este descubrimiento:
- Hablando por mí mismo, lo considero la experiencia más traumática de mi carrera como analista numérico. [1]
El polinomio de Wilkinson se usa a menudo para ilustrar lo indeseable de calcular ingenuamente los valores propios de una matriz calculando primero los coeficientes del polinomio característico de la matriz y luego encontrando sus raíces, ya que usar los coeficientes como un paso intermedio puede introducir un mal acondicionamiento extremo incluso si el El problema original estaba bien condicionado. [2]
Condicionamiento del polinomio de Wilkinson
Polinomio de Wilkinson
claramente tiene 20 raíces, ubicadas en x = 1, 2, ..., 20. Estas raíces están muy separadas. Sin embargo, el polinomio todavía está muy mal acondicionado.
Ampliando el polinomio, se encuentra
Si el coeficiente de x 19 se reduce de −210 en 2 −23 a −210,0000001192, entonces el valor del polinomio w (20) disminuye de 0 a −2 −23 20 19 = −6,25 × 10 17 , y la raíz en x = 20 crece ax ≈ 20,8. Las raíces en x = 18 yx = 19 chocan en una raíz doble en x ≈ 18.62 que se convierte en un par de raíces conjugadas complejas en x ≈ 19.5 ± 1.9 i a medida que la perturbación aumenta más. Las 20 raíces se convierten (a 5 decimales)
Algunas de las raíces están muy desplazadas, aunque el cambio en el coeficiente es pequeño y las raíces originales parecen estar muy espaciadas. Wilkinson mostró mediante el análisis de estabilidad discutido en la siguiente sección que este comportamiento está relacionado con el hecho de que algunas raíces α (como α = 15) tienen muchas raíces β que están "cercanas" en el sentido de que | α - β | es menor que | α |.
Wilkinson eligió la perturbación de 2 −23 porque su computadora Pilot ACE tenía significados de coma flotante de 30 bits , por lo que para números alrededor de 210, 2 −23 fue un error en la primera posición de bit no representada en la computadora. Los dos números reales, −210 y −210-2 −23 , están representados por el mismo número de coma flotante, lo que significa que 2 −23 es el error inevitable al representar un coeficiente real cercano a −210 por un número de coma flotante en ese ordenador. El análisis de perturbación muestra que la precisión del coeficiente de 30 bits es insuficiente para separar las raíces del polinomio de Wilkinson.
Análisis de estabilidad
Suponga que perturbamos un polinomio p ( x ) = Π ( x - α j ) con raíces α j sumando un pequeño múltiplo t · c ( x ) de un polinomio c ( x ), y preguntemos cómo afecta esto a las raíces α j . A primer orden, el cambio en las raíces será controlado por la derivada
Cuando la derivada es grande, las raíces serán menos estables bajo variaciones de t y, a la inversa, si esta derivada es pequeña, las raíces serán estables. En particular, si α j es una raíz múltiple, el denominador desaparece. En este caso, α j generalmente no es diferenciable con respecto a t (a menos que c desaparezca allí), y las raíces serán extremadamente inestables.
Para valores pequeños de t, la raíz perturbada está dada por la expansión de la serie de potencias en t
y uno espera problemas cuando | t | es mayor que el radio de convergencia de esta serie de potencias, que viene dado por el valor más pequeño de | t | tal que la raíz α j se vuelva múltiple. Una estimación muy burda de este radio toma la mitad de la distancia desde α j hasta la raíz más cercana y divide por la derivada anterior.
En el ejemplo del polinomio de Wilkinson de grado 20, las raíces están dadas por α j = j para j = 1, ..., 20, y c ( x ) es igual ax 19 . Entonces la derivada está dada por
Esto muestra que la raíz α j será menos estable si hay muchas raíces α k cercanas a α j , en el sentido de que la distancia | α j - α k | entre ellos es menor que | α j |.
Ejemplo . Para la raíz α 1 = 1, ¡la derivada es igual a 1/19! que es muy pequeño; esta raíz es estable incluso para grandes cambios en t . Esto se debe a que todas las demás raíces β están muy lejos de él, en el sentido de que | α 1 - β | = 1, 2, 3, ..., 19 es mayor que | α 1 | = 1. Por ejemplo, incluso si t es tan grande como –10000000000, la raíz α 1 solo cambia de 1 a aproximadamente 0,99999991779380 (que está muy cerca de la aproximación de primer orden 1 + t / 19! ≈ 0,99999991779365). De manera similar, las otras raíces pequeñas del polinomio de Wilkinson son insensibles a los cambios en t .
Ejemplo . Por otro lado, para la raíz alpha 20 = 20, el IS derivada igual a -20 19 /19! que es enorme (alrededor de 43000000), por lo que esta raíz es muy sensible a pequeños cambios en t . Las otras raíces β están cerca de α 20 , en el sentido de que | β - α 20 | = 1, 2, 3, ..., 19 es menor que | α 20 | = 20. Para t = -2 - 23 el primer orden de aproximación 20 - t · 20 19 /19! = 25.137 ... a la raíz perturbada 20.84 ... es terrible; esto es aún más obvio para la raíz α 19 donde la raíz perturbada tiene una gran parte imaginaria pero la aproximación de primer orden (y para el caso todas las aproximaciones de orden superior) son reales. La razón de esta discrepancia es que | t | ≈ 0.000000119 es mayor que el radio de convergencia de la serie de potencia mencionada anteriormente (que es aproximadamente 0.0000000029, algo menor que el valor 0.00000001 dado por la estimación bruta) por lo que la teoría linealizada no se aplica. Para un valor como t = 0.000000001 que es significativamente más pequeño que este radio de convergencia, la aproximación de primer orden 19.9569 ... está razonablemente cerca de la raíz 19.9509 ...
A primera vista, las raíces α 1 = 1 y α 20 = 20 del polinomio de Wilkinson parecen ser similares, ya que están en extremos opuestos de una línea simétrica de raíces y tienen el mismo conjunto de distancias 1, 2, 3, .. ., 19 de otras raíces. Sin embargo, el análisis anterior muestra que esto es extremadamente engañoso: la raíz α 20 = 20 es menos estable que α 1 = 1 (para pequeñas perturbaciones en el coeficiente de x 19 ) por un factor de 20 19 = 5242880000000000000000000.
El segundo ejemplo de Wilkinson
El segundo ejemplo considerado por Wilkinson es
Los veinte ceros de este polinomio están en una progresión geométrica con razón común 2, y por lo tanto el cociente
no puede ser grande. De hecho, los ceros de w 2 son bastante estables a grandes cambios relativos en los coeficientes.
El efecto de la base
La expansión
expresa el polinomio en una base particular, a saber, la de los monomios. Si el polinomio se expresa en otra base, entonces el problema de encontrar sus raíces puede dejar de estar mal condicionado. Por ejemplo, en una forma de Lagrange , un pequeño cambio en uno (o varios) coeficientes no necesita cambiar demasiado las raíces. De hecho, los polinomios base para la interpolación en los puntos 0, 1, 2, ..., 20 son
Cada polinomio (de grado 20 o menos) se puede expresar en esta base:
Para el polinomio de Wilkinson, encontramos
Dada la definición del polinomio de base de Lagrange ℓ 0 ( x ), un cambio en el coeficiente d 0 no producirá ningún cambio en las raíces de w . Sin embargo, una perturbación en los otros coeficientes (todos iguales a cero) cambiará ligeramente las raíces. Por lo tanto, el polinomio de Wilkinson está bien condicionado en esta base.
Notas
- ^ Wilkinson, James H. (1984). "El polinomio pérfido". En Gene H. Golub (ed.). Estudios de Análisis Numérico . Asociación Matemática de América. pag. 3. ISBN 978-0-88385-126-5.
- ^ Trefethen, Lloyd N .; Bau, David (1997), Álgebra lineal numérica , SIAM
Referencias
Wilkinson discutió "su" polinomio en
- JH Wilkinson (1959). La evaluación de los ceros de polinomios mal acondicionados. Parte I. Numerische Mathematik 1 : 150-166.
- JH Wilkinson (1963). Errores de redondeo en procesos algebraicos . Englewood Cliffs, Nueva Jersey: Prentice Hall.
Se menciona en libros de texto estándar en análisis numérico, como
- FS Acton, métodos numéricos que funcionan , ISBN 978-0-88385-450-1 , pág. 201.
Otras referencias:
- Ronald G. Mosier (julio de 1986). Vecindarios raíz de un polinomio. Matemáticas de la computación 47 (175): 265-273.
- JH Wilkinson (1984). El polinomio pérfido. Estudios de análisis numérico , ed. por GH Golub, págs. 1–28. (Estudios de Matemáticas, vol. 24). Washington, DC: Asociación Matemática de América.
Se presenta un cálculo numérico de alta precisión en:
- Ray Buvel, Polynomials And Rational Functions , parte del RPN Calculator User Manual (para Python), recuperado el 29 de julio de 2006.