Polinomio de Wilkinson

Gráfica de un polinomio de Wilkinson

Gráfica de sgn(w(x)) log(1 + -w(x)-)

En análisis numérico, un polinomio de Wilkinson es un tipo de polinomio específico utilizado por James H. Wilkinson en 1963 para ilustrar la dificultad de encontrar las raíces de un polinomio, dado que su ubicación puede ser muy sensible a pequeñas variaciones en los coeficientes del propio polinomio.

La expresión del polinomio es:

$w(x)=\prod _{i=1}^{20}(x-i)=(x-1)(x-2)\cdots (x-20).$

A veces, el término polinomio de Wilkinson también se usa para referirse a otros polinomios que aparecen en los análisis realizados por Wilkinson.

Antecedentes

El polinomio de Wilkinson surgió en el estudio de algoritmos para encontrar las raíces de un polinomio

$p(x)=\sum _{i=0}^{n}c_{i}x^{i}.$

Es una cuestión natural en el análisis numérico preguntar si el problema de encontrar las raíces de un polinomio p a partir de sus coeficientes c_i es una tarea bien condicionada. Es decir, que un pequeño cambio en los coeficientes implique un pequeño cambio en las raíces. Desafortunadamente, este no es el caso analizado por Wilkinson.

El problema está mal condicionado cuando el polinomio tiene una raíz múltiple. Por ejemplo, el polinomio x² tiene una raíz doble en  x = 0. Sin embargo, el polinomio x² − ε (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 que le causó este descubrimiento:

"Personalmente, la considero la experiencia más traumática de mi carrera como analista numérico".​

El polinomio de Wilkinson se usa a menudo para ilustrar lo indeseable de calcular ingenuamente los autovalores 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 condicionamiento extremo incluso si el problema original estaba bien condicionado.​

Condicionado del polinomio de Wilkinson

El polinomio de Wilkinson

$w(x)=\prod _{i=1}^{20}(x-i)=(x-1)(x-2)\cdots (x-20)$

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 condicionado.

Ampliando el polinomio, se encuentra que

${\begin{aligned}w(x)={}&x^{20}-210x^{19}+20615x^{18}-1256850x^{17}+53327946x^{16}\\&{}-1672280820x^{15}+40171771630x^{14}-756111184500x^{13}\\&{}+11310276995381x^{12}-135585182899530x^{11}\\&{}+1307535010540395x^{10}-10142299865511450x^{9}\\&{}+63030812099294896x^{8}-311333643161390640x^{7}\\&{}+1206647803780373360x^{6}-3599979517947607200x^{5}\\&{}+8037811822645051776x^{4}-12870931245150988800x^{3}\\&{}+13803759753640704000x^{2}-8752948036761600000x\\&{}+2432902008176640000.\end{aligned}}$

Si se modifica en una pequeña cantidad el coeficiente de x¹⁹, cambiándolo de −210 a −210.0000001192 (=-210-2⁻²³), entonces el valor polinomial w(20) disminuye de 0 a −2⁻²³20¹⁹ =−6.25×10¹⁷, y la raíz en x =20 crece hasta x ≈20.8. Las raíces en x =18 y x =19 se encuentran con una raíz doble en x≈18.62, que se convierte en un par de raíces conjugadas complejas en x≈19.5 ± 1.9i a medida que la perturbación aumenta aún más. Las 20 raíces se convierten (con 5 decimales) en:

${\begin{array}{rrrrr}1.00000&2.00000&3.00000&4.00000&5.00000\\[8pt]6.00001&6.99970&8.00727&8.91725&20.84691\\[8pt]10.09527\pm {}&11.79363\pm {}&13.99236\pm {}&16.73074\pm {}&19.50244\pm {}\\[-3pt]0.64350i&1.65233i&2.51883i&2.81262i&1.94033i\end{array}}$

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 demostró 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 son "cerradas" en el sentido de que |α - β| es más pequeño que |α|.

Wilkinson eligió la perturbación de 2⁻²³ porque su computadora Pilot ACE usaba números de coma flotante con una mantisa de 30 bits, por lo que para números de alrededor de 210, al añadir 2⁻²³ se alcanzaba la primera posición de bit no representable por la computadora. Los dos números reales, −210 y −210−2⁻²³, están representados por el mismo número de coma flotante, lo que significa que 2⁻²³ era el error "inevitable" al representar un coeficiente real cercano a −210 mediante un número de coma flotante en su computadora. El análisis de perturbación demuestra que manejar los coeficientes con precisión de 30 bits es insuficiente para separar las raíces del polinomio de Wilkinson.

Análisis de estabilidad

Supóngase que se perturba un polinomio p(x) = Π(x − α_j) con raíces α_j agregando un pequeño múltiplo t·c(x) de un polinomio c(x), y véase cómo afecta esto a las raíces α_j. En una primera aproximación, el cambio en las raíces será controlado por la derivada

${d\alpha _{j} \over dt}=-{c(\alpha _{j}) \over p^{\prime }(\alpha _{j})}.$

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 aquí), 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

$\alpha _{j}+{d\alpha _{j} \over dt}t+{d^{2}\alpha _{j} \over dt^{2}}{t^{2} \over 2!}+\cdots$

y son de esperar 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| de modo 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 a la raíz más cercana y dividido 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 a x¹⁹. Entonces, la derivada viene dada por

${d\alpha _{j} \over dt}=-{\alpha _{j}^{19} \over \prod _{k\neq j}(\alpha _{j}-\alpha _{k})}=-\prod _{k\neq j}{\alpha _{j} \over \alpha _{j}-\alpha _{k}}.\,\!$

Esto demuestra que la raíz α_j será menos estable si hay muchas raíces α_k cerca de α_j, en el sentido de que la distancia |α_j − α_k| entre ellos es menor que |α_j|.

Ejemplo. Para la raíz α₁ = 1, la derivada es igual a 1/19!, que es un número 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 ella, en el sentido de que |α₁ − β| = 1, 2, 3, ..., 19 es mayor que |α₁| = 1. Por ejemplo, incluso si t es tan grande como –10000000000, la raíz α₁ solo cambia de 1 a aproximadamente 0,99999991779380 (que está muy cerca de la aproximación de primer orden 1 + t/19! ≈ 0.99999991779365). Del mismo modo, 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 α₂₀ = 20, la derivada es igual a −20¹⁹/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 cercanas a α₂₀, en el sentido de que |β − α₂₀| = 1, 2, 3, ..., 19 es menor que |α₂₀| = 20. Para t = −2 ^− 23 la aproximación de primer orden 20 − t·20¹⁹/19! = 25.137 ... a la raíz perturbada 20.84 ... es muy deficiente; esto es aún más obvio para la raíz α₁₉, 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 potencias 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 y α₂₀ = 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 demuestra que esto es extremadamente engañoso: la raíz α₂₀ = 20 es menos estable que α₁ = 1 (a pequeñas perturbaciones en el coeficiente de x¹⁹) por un factor de 20¹⁹ = 5242880000000000000000000.

Segundo ejemplo de Wilkinson

El segundo ejemplo considerado por Wilkinson es

$w_{2}(x)=\prod _{i=1}^{20}(x-2^{-i})=(x-2^{-1})(x-2^{-2})\cdots (x-2^{-20}).$

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

$\alpha _{j} \over \alpha _{j}-\alpha _{k}$

no puede ser grande. De hecho, los ceros de w₂ son bastante estables a grandes cambios relativos en los coeficientes.

Efecto de la base

La expansión

$p(x)=\sum _{i=0}^{n}c_{i}x^{i}$

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 implica modificaciones demasiado grandes en las raíces. De hecho, los polinomios base para la interpolación en los puntos 0, 1, 2, ..., 20 son

$\ell _{k}(x)=\prod _{i\in \{0,\ldots ,20\}\setminus \{k\}}{\frac {x-i}{k-i}},\qquad {\text{for}}\quad k=0,\ldots ,20.$

Cada polinomio (de grado 20 o menos) se puede expresar en esta base:

$p(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x).$

Para el polinomio de Wilkinson, se tiene que

$w(x)=(20!)\ell _{0}(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x)\quad {\text{with}}\quad d_{0}=(20!),\,d_{1}=d_{2}=\cdots =d_{20}=0.$

Dada la definición del polinomio de base de Lagrange ℓ₀ (x), un cambio en el coeficiente d₀ 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.

Publicaciones

Wilkinson discutió "su" polinomio en

• J. H. Wilkinson (1959). "The evaluation of the zeros of ill-conditioned polynomials. Part I." (La evaluación de los ceros de polinomios mal condicionados. Parte I.)Numerische Mathematik 1:150-166.
• J. H. Wilkinson (1963). "Rounding Errors in Algebraic Processes" (Errores de redondeo en procesos algebraicos). Englewood Cliffs, Nueva Jersey: Prentice Hall.

Bibliografía

El trabajo de Wilkinson se menciona en libros de texto estándar de análisis numérico, como:

• F. S. Acton, "Numerical methods that work" (Métodos numéricos que funcionan), ISBN 978-0-88385-450-1, p. 201.

Otras referencias:

• Ronald G. Mosier (julio de 1986). "Root neighborhoods of a polynomial" (Raíces vecinas de un polinomio). Mathematics of Computation (Matemáticas de la Computación) 47 (175): 265-273.
• J. H. Wilkinson (1984). El polinomio pérfido. "Estudios en análisis numérico", ed. por G. H. Golub, págs. 1–28. (Estudios de Matemáticas, vol. 24). Washington, D.C.: Asociación Matemática de América.

Se presenta un cálculo numérico de alta precisión en:

• Ray Buvel, Polinomios y funciones racionales, parte del RPN Calculator User Manual (para Python), consultado el 29 de julio de 2006.

• Datos: Q2613931