Polinomio de Wilkinson

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 perturbaciones en los coeficientes del polinomio.

El polinomio es A veces, el término polinomio de Wilkinson también se utiliza para referirse a otros polinomios que aparecen en la discusión de Wilkinson. $w(x)=\prod _{i=1}^{20}(xi)=(x-1)(x-2)\cdots (x-20).$

Fondo

El polinomio de Wilkinson surgió en el estudio de algoritmos para hallar las raíces de un polinomio. En el análisis numérico, es natural preguntarse si el problema de hallar 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 conduzca a un pequeño cambio en las raíces. Desafortunadamente, este no es el caso aquí. $p(x)=\sum _{i=0}^{n}c_{i}x^{i}.$

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 $\pm\sqrt ε$ , que es mucho más grande que $ε$ cuando $ε$ es pequeño.

Por lo tanto, es natural esperar que el mal condicionamiento también ocurra cuando el polinomio tiene ceros muy próximos. Sin embargo, el problema también puede estar extremadamente mal condicionado para polinomios con ceros bien separados. Wilkinson utilizó 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 utiliza a menudo para ilustrar lo indeseable que resulta calcular de manera ingenua 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 utilizar los coeficientes como un paso intermedio puede introducir un mal condicionamiento extremo incluso si el problema original estaba bien condicionado. ^[2]

Condicionamiento del polinomio de Wilkinson

El polinomio de Wilkinson tiene claramente 20 raíces, ubicadas en $x$ $= 1, 2, ..., 20.$ Estas raíces están muy separadas. Sin embargo, el polinomio sigue estando muy mal condicionado. $w(x)=\prod _{i=1}^{20}(xi)=(x-1)(x-2)\cdots (x-20)$

Desarrollando el polinomio, se encuentra ${\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 el coeficiente de x ¹⁹ se reduce de −210 en 2 ⁻²³ hasta −210.0000001192, entonces el valor del polinomio w (20) disminuye de 0 a −2 ⁻²³ 20 ¹⁹ = −6.25×10 ¹⁷ , y la raíz en $x = 20$ crece hasta $x \approx 20.8$ . Las raíces en $x = 18$ y $x = 19$ colisionan en una raíz doble en $x \approx 18.62$ que se convierte en un par de raíces conjugadas complejas en $x \approx 19.5 \pm 1.9 i$ a medida que la perturbación aumenta aún más. Las 20 raíces se convierten (a 5 decimales) ${\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 minúsculo y las raíces originales parecen muy espaciadas. Wilkinson demostró mediante el análisis de estabilidad que se analiza 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 "cerca" en el sentido de que | α − β | es más pequeño que | α |.

Wilkinson eligió la perturbación de 2 ⁻²³ porque su computadora Pilot ACE tenía mantisas de punto flotante de 30 bits , por lo que para números alrededor de 210, 2 ⁻²³ era un error en la primera posición de bit no representada en la computadora. Los dos números reales, −210 y −210 − 2 ⁻²³ , están representados por el mismo número de punto flotante, lo que significa que 2 ⁻²³ es el error inevitable al representar un coeficiente real cercano a −210 por un número de punto flotante en esa computadora. 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

Supongamos que perturbamos un polinomio $p (x) = Π (x - α j)$ con raíces $α j$ añadiendo un múltiplo pequeño $t \cdot c (x)$ de un polinomio $c (x)$ , y preguntamos cómo afecta esto a las raíces $α j$ . En primer orden, el cambio en las raíces estará controlado por la derivada Cuando la derivada es pequeña, las raíces serán más estables bajo variaciones de $t$ , y a la inversa, si esta derivada es grande, las raíces serán inestables. En particular, si $α$ $j$ es una raíz múltiple, entonces el denominador se anula. En este caso, α _j normalmente no es diferenciable con respecto a $t$ (a menos que $c$ se anule allí), y las raíces serán extremadamente inestables. ${d\alpha _{j} \over dt}=-{c(\alpha _{j}) \over p^{\prime }(\alpha _{j})}.$

Para valores pequeños de $t,$ la raíz perturbada está dada por la expansión de la serie de potencias en $t$ y se esperan problemas cuando | t | es mayor que el radio de convergencia de esta serie de potencias, que está dado por el valor más pequeño de | t | tal que la raíz $α$ $j$ se vuelve múltiple. Una estimación muy burda para este radio toma la mitad de la distancia desde $α$ $j$ hasta la raíz más cercana y la divide por la derivada anterior. $\alpha _{j}+{d\alpha _{j} \over dt}t+{d^{2}\alpha _{j} \over dt^{2}}{t^{2} \over 2!}+\cdots$

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 ¹⁹ . Por lo tanto, 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 ellas es menor que |α _j |. ${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}}.\,\!$

Ejemplo . Para la raíz α ₁ = 1, la derivada es igual a 1/19!, que es muy pequeña; 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). De manera similar, las otras raíces pequeñas del polinomio de Wilkinson son insensibles a los cambios en t .

Ejemplo . Por otra parte, 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 β son 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 terrible; Esto es aún más obvio para la raíz α ₁₉ , donde la raíz perturbada tiene una parte imaginaria grande, pero la aproximación de primer orden (y, en realidad, 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 cruda), por lo que la teoría linealizada no se aplica. Para un valor como t = 0,000000001 que es significativamente menor 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 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 desde otras raíces. Sin embargo, el análisis anterior muestra 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 ¹⁹ = 52428800000000000000000000.

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. $w_{2}(x)=\prod _{i=1}^{20}(x-2^{-i})=(x-2^{-1})(x-2^{-2})\cdots (x-2^{-20}).$ $\alpha _{j} \over \alpha _{j}-\alpha _{k}$

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 ser un problema mal condicionado. Por ejemplo, en una forma de Lagrange , un pequeño cambio en uno (o varios) coeficientes no tiene por qué cambiar demasiado las raíces. De hecho, los polinomios base para la interpolación en los puntos 0, 1, 2, ..., 20 son $p(x)=\sum _{i=0}^{n}c_{i}x^{i}$ $\ell _{k}(x)=\prod _{i=0,\ldots ,20 \atop i\neq k}{\frac {x-i}{k-i}},\qquad {\text{for}}\quad k=0,\ldots ,20.$

Todo polinomio (de grado 20 o menor) puede expresarse en esta base: $p(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x).$

Para el polinomio de Wilkinson, encontramos $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 $ℓ 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 en análisis numérico . Asociación Matemática de Estados Unidos. p. 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 condicionados. 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 los libros de texto estándar sobre 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). Entornos de raíces de un polinomio. Matemáticas de la computación 47 (175): 265–273.
JH Wilkinson (1984). El polinomio pérfido. Estudios en análisis numérico , ed. por GH Golub, págs. 1–28. (Estudios en matemáticas, vol. 24). Washington, DC: Asociación Matemática de Estados Unidos.

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

Ray Buvel, Polinomios y funciones racionales, parte del Manual del usuario de la calculadora RPN (para Python), recuperado el 29 de julio de 2006.

[1] Wilkinson, James H. (1984). "El polinomio pérfido". En Gene H. Golub (ed.). Estudios en análisis numérico . Asociación Matemática de Estados Unidos. p. 3. ISBN 978-0-88385-126-5.

[TrefethenBau-2] Trefethen, Lloyd N.; Bau, David (1997), Álgebra lineal numérica , SIAM