Многочлен Уилкинсона

График многочлена Уилкинсона

График ${\displaystyle \operatorname {sgn}(w(x))\ln(1+|w(x)|)}$

Многочлен Уилкинсона — многочлен, который использовал Джеймс Харди Уилкинсон в 1963 году, чтобы проиллюстрировать трудность нахождения корней многочлена положение корней, так как решение может быть очень чувствительным к малым изменениям коэффициентов многочлена.

Иногда термин многочлен Уилкинсона используется также для других многочленов, возникающих в обсуждениях Уилкинсона.

Многочлен Уилкинсона возник при изучении алгоритмов для поиска корней многочлена ${\displaystyle p(x)=\sum _{i=0}^{n}c_{i}x^{i}.}$ В численном анализе закономерно возникает вопрос, насколько хорошо обусловлена задача нахождения корней многочлена p по его коэффициентам c_i. Иными словами, мы надеемся, что небольшое изменение коэффициентов приведет к небольшому изменению корней. К сожалению, в данном случае это не так.

Задача плохо обусловлена, если имеет кратный корень. Например, многочлен x² имеет кратный корень x = 0. Однако, многочлен x² − ε (возмущение на величину ε) имеет корни ±√ε, которые много больше, чем ε, если ε мало.

Поэтому естественно ожидать, что плохо обусловленная задача возникает также, если многочлен имеет очень близкие корни. Однако задача может оказаться крайне плохо обусловленной для многочлена с хорошо разделёнными корнями. Уилкинсон использовал многочлен w(x), чтобы проиллюстрировать это^[1].

В 1984 году, он описал личное впечатление этого открытия:

Говоря за себя, я считаю это самым травмирующим опытом в моей карьере специалиста по численным методам.^[2]

Многочлен Уилкинсона часто используется для иллюстрации нежелательности вычисления собственных значений матриц путём сначала вычисления коэффициентов характеристического многочлена матрицы и поиска затем его корней, поскольку использование коэффициентов как промежуточного шага может привести к крайне плохо обусловленной задаче, даже если исходная задача была хорошо обусловлена^[3].

Многочлен Уилкинсона $${\displaystyle w(x)=\prod _{i=1}^{20}(x-i)=(x-1)(x-2)\cdots (x-20)}$$ имеет очевидно 20 корней со значениями x = 1, 2, ..., 20. Эти корни достаточно далеко расположены друг от друга. Однако, многочлен остаётся очень плохо обусловленным.

Раскрыв скобки, получим $${\displaystyle {\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}}}$$

Если коэффициент x¹⁹ уменьшен со значения −210 на 2⁻²³ до −210,0000001192, то значение многочлена w(20) уменьшается с 0 до ${\displaystyle -2^{-23}20^{19}=-6{,}25\times 10^{17}}$, а корень x = 20 увеличивается до ${\displaystyle x\approx 20{,}8}$. Корни x = 18 и x = 19 объединяются в кратный корень ${\displaystyle x\approx 18{,}62}$, который превращается в пару комплексных сопряжённых корней ${\displaystyle x\approx 19{,}5\pm 1{,}9i}$ при дальнейшем увеличении. 20 корней переходят в (с точностью до 5 знаков) $${\displaystyle {\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}}}$$

Некоторые корни сильно смещаются, даже несмотря на незначительное изменение коэффициента и кажущееся широкое расстояние между исходными корнями. Уилкинсон показал с помощью анализа устойчивости, описанного ниже, что это поведение связано с тем, что некоторые корни α (такие как α = 15) имеют несколько корней β, которые «близки» в смысле, что |α − β| меньше  |α|.

Уилкинсон выбрал отклонение 2⁻²³, поскольку его компьютер Pilot ACE имел числа с плавающей запятой с 30-битной мантиссой. Два вещественных числа −210 и −210 − 2⁻²³ в машине представляются одним и тем же плавающим числом, что означает, что 2⁻²³ является неизбежной ошибкой в представлении вещественного коэффициента около −210 числом с плавающей точкой на этом компьютере. Анализ возмущений показывает, что 30-битная точность коэффициентов недостаточна для разделения корней многочлена Уилкинсона.

Предположим, что мы возмущаем многочлен ${\displaystyle p(x)=\prod (x-\alpha _{j})}$ с корнями ${\displaystyle \alpha _{j}}$ путём добавления многочлена ${\displaystyle c(x)}$ с небольшим коэффициентом ${\displaystyle t\cdot c(x)}$, и спросим, как это повлияет на корни ${\displaystyle \alpha _{j}}$. В первом приближении изменение корней будет контролироваться производной $${\displaystyle {d\alpha _{j} \over dt}=-{c(\alpha _{j}) \over p^{\prime }(\alpha _{j})}.}$$ Если производная мала, корни будут более устойчивы к изменению t, и наоборот, если производная велика, корни будут неустойчивы. В частности, если ${\displaystyle \alpha _{j}}$ является кратным корнем, то знаменатель обращается в ноль. В этом случае, α_j обычно не дифференцируема по t (если только c случайно не обращается в ноль в этой точке), и корни будут чрезвычайно неустойчивы.

Для малых значений t возмущённый корень задаётся разложением в степенной ряд по t $${\displaystyle \alpha _{j}+{d\alpha _{j} \over dt}t+{d^{2}\alpha _{j} \over dt^{2}}{t^{2} \over 2!}+\cdots }$$ и следует ожидать проблемы, когда |t| больше радиуса сходимости этого степенного ряда, который определяется наименьшим значением |t|, при котором корень ${\displaystyle \alpha _{j}}$ становится кратным. Очень грубая оценка этого радиуса получается как половина расстояния от ${\displaystyle \alpha _{j}}$ до ближайшего корня с последующим делением на упомянутую выше производную.

На примере многочлена Уилкинсона степени 20, корни задаются как ${\displaystyle \alpha _{j}=j}$ для j = 1, ..., 20, и c(x) равно x¹⁹. Так что производная задаётся формулой $${\displaystyle {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}}.\,\!}$$ Это показывает, что корень ${\displaystyle \alpha _{j}}$ будет менее устойчивым, если имеется много корней ${\displaystyle \alpha _{k}}$ близких к ${\displaystyle \alpha _{j}}$, в том смысле, что расстояние ${\displaystyle |\alpha _{j}-\alpha _{k}|}$ между ними меньше |α_j|.

Пример. Для корня ${\displaystyle \alpha _{1}=1}$ производная равна 1/19!, и эта величина очень мала. Этот корень устойчив даже при больших значениях t. Это потому, что все другие корни β далеки от него, в том смысле, что ${\displaystyle |\alpha _{1}-\beta |=1,2,3,\dots ,19}$ больше, чем ${\displaystyle \alpha _{1}=1}$. Например, даже если t имеет значение –10000000000, корень ${\displaystyle \alpha _{1}}$ изменяется только с 1 до примерно 0,99999991779380 (что очень близко приближению первого порядка 1 + t/19! ≈ 0,99999991779365). Аналогично, другие малые корни многочлена Уилкинсона нечувствительны к изменениям t.

Пример. С другой стороны, для корня ${\displaystyle \alpha _{20}=20}$, производная равна ${\displaystyle -{\tfrac {20^{19}}{19!}}}$, что очень велико (около 43000000), так что корень очень чувствителен к малым изменениям t. Другие корни β близки к α₂₀, в смысле, что |β − α₂₀| = 1, 2, 3, ..., 19 меньше ${\displaystyle |\alpha _{20}|=20}$. Для t = −2⁻²³, приближение первого порядка ${\displaystyle 20-{\tfrac {20^{19}t}{19!}}=25{,}137\cdots }$ для возмущённого корня 20,84... ужасно. И это даже более очевидно для корня α₁₉, где возмущённый корень имеет большую мнимую часть, но приближение первого порядка (как и все приближения более высоких порядков) является действительным. Причина такого расхождения заключается в том, что |t| ≈ 0,000000119 больше радиуса сходимости степенного ряда, упомянутого выше, (который составляет около 0,0000000029, несколько меньше 0,00000001, полученного грубой оценкой) поэтому линейная теория неприменима. Для значения, такого как t = 0,000000001, которое значительно меньше этого радиуса сходимости, приближение первого порядка 19,9569... оказывается достаточно близким к корню 19,9509...

На первый взгляд корни α₁ = 1 и α₂₀ = 20 многочлена Уилкинсона кажутся похожими, поскольку они находятся на противоположных концах симметричной линии корней и имеют одинаковый набор расстояний 1, 2, 3, ..., 19 от других корней. Однако приведённый выше анализ показывает, что такая похожесть вводит в заблуждение: корень α₂₀ = 20 менее устойчив, чем α₁ = 1 (к малым возмущениям в коэффициенте при x¹⁹) на множитель 20¹⁹ = 5242880000000000000000000.

Вторым примером, который рассматривал Уилкинсон, является $${\displaystyle w_{2}(x)=\prod _{i=1}^{20}(x-2^{-i})=(x-2^{-1})(x-2^{-2})\cdots (x-2^{-20}).}$$ Двадцать корней этого многочлена являются геометрической прогрессией, и, следовательно, частное $${\displaystyle \alpha _{j} \over \alpha _{j}-\alpha _{k}}$$ Не может быть большим. Действительно, корни w₂ довольно устойчивы к большим относительным изменениям коэффициентов.

Разложение $${\displaystyle p(x)=\sum _{i=0}^{n}c_{i}x^{i}}$$ представлен в определённом базисом, а именно в базисе одночленов. Если многочлен представлен в другом базисе, задача нахождения его корней может перестать быть плохо обусловленной. Например, в форме Лагранжа, небольшое изменение одного (или нескольких) коэффициентов не обязательно приведёт к сильному изменению корней. Действительно, базисные полиномы для интерполяции в точках 0, 1, 2, ..., 20 являются $${\displaystyle \ell _{k}(x)=\prod _{i=0,\ldots ,20 \atop i\neq k}{\frac {x-i}{k-i}},\qquad {\text{для}}\quad k=0,\ldots ,20.}$$

Любой многочлен (степени 20 или меньше) можно выразить в этом базисе: $${\displaystyle p(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x).}$$

Для многочлена Уилкинсона мы находим $${\displaystyle w(x)=(20!)\ell _{0}(x)=\sum _{i=0}^{20}d_{i}\ell _{i}(x)\quad {\text{с}}\quad d_{0}=(20!),\,d_{1}=d_{2}=\cdots =d_{20}=0.}$$

Если задано определение базисного многочлена Лагранжа ℓ₀(x), изменение коэффициента d₀ не приведёт к изменению корней w. Изменение же других коэффициентов (все они равны нулю) лишь слегка изменит корни. Поэтому многочлен Уилкинсона в этом базисе хорошо обусловлен.

Уилкинсон обсуждал «свой» многочлен в книге

• J. H. Wilkinson (1959). The evaluation of the zeros of ill-conditioned polynomials. Part I. Numerische Mathematik 1:150–166.

Она упомянута в стандартных учебниках по методам вычислений, как например

• F. S. Acton, Numerical methods that work, ISBN 978-0-88385-450-1, p. 201.

Другие ссылки:

• Ronald G. Mosier (July 1986). Root neighborhoods of a polynomial. Mathematics of Computation 47(175):265–273.
• J. H. Wilkinson (1984). The perfidious polynomial. Studies in Numerical Analysis, ed. by G. H. Golub, pp. 1–28. (Studies in Mathematics, vol. 24). Washington, D.C.: Mathematical Association of America.

Вычисления двойной точности представлены в:

• Ray Buvel, Polynomials And Rational Functions, part of the RPN Calculator User Manual (for Python), retrieved on 29 July 2006.