Полином Уилкинсона

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

Полином Иногда термин «полином Уилкинсона» также используется для обозначения некоторых других полиномов, появляющихся в рассуждениях Уилкинсона. $w(x)=\prod _{i=1}^{20}(xi)=(x-1)(x-2)\cdots (x-20).$

Фон

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

Задача плохо обусловлена, когда многочлен имеет кратный корень. Например, многочлен $x 2$ имеет двойной корень при $x = 0.$ Однако многочлен $x 2 - ε$ (возмущение размера ε ) имеет корни при $\pm\sqrt ε$ , что намного больше $ε,$ когда $ε$ мало.

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

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

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

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

Обусловливание полинома Уилкинсона

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

Раскрывая многочлен, находим ${\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 до −2 ⁻²³ 20 ¹⁹ = −6.25×10 ¹⁷ , а корень при $x = 20$ вырастет до $x \approx 20.8$ . Корни при $x = 18$ и $x = 19$ сталкиваются в двойной корень при $x \approx 18.62$ , который превращается в пару комплексно-сопряженных корней при $x \approx 19.5 \pm 1.9 i$ по мере дальнейшего увеличения возмущения. 20 корней становятся (до 5 десятичных знаков) ${\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, 2 ⁻²³ было ошибкой в первой битовой позиции, не представленной в компьютере. Два действительных числа, −210 и −210 − 2 ⁻²³ , представлены одним и тем же числом с плавающей точкой, что означает, что 2 ⁻²³ является неизбежной ошибкой при представлении действительного коэффициента, близкого к −210, числом с плавающей точкой на этом компьютере. Анализ возмущения показывает, что точность 30-битного коэффициента недостаточна для разделения корней многочлена Уилкинсона.

Анализ устойчивости

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

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

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

Пример . Для корня α ₁ = 1 производная равна 1/19!, что очень мало; этот корень устойчив даже при больших изменениях t . Это потому, что все остальные корни β далеки от него, в том смысле, что | α ₁ − β | = 1, 2, 3, ..., 19 больше, чем | α ₁ | = 1. Например, даже если t столь же велико, как –10000000000, корень α ₁ изменяется только от 1 до примерно 0,99999991779380 (что очень близко к приближению первого порядка 1 + t /19! ≈ 0,99999991779365). Аналогично, другие малые корни многочлена Уилкинсона нечувствительны к изменениям t .

Пример . С другой стороны, для корня α ₂₀ = 20 производная равна −20 ¹⁹ /19! что огромно (около 43000000), поэтому этот корень очень чувствителен к небольшим изменениям t . Другие корни β близки к α ₂₀ , в том смысле, что | β − α ₂₀ | = 1, 2, 3, ..., 19 меньше, чем | α ₂₀ | = 20. Для t = −2 ^{− 23} приближение первого порядка 20 − t ·20 ¹⁹ /19! = 25,137... к возмущенному корню 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 ¹⁹ = 52428800000000000000000000.

Второй пример Уилкинсона

Второй пример, рассмотренный Уилкинсоном, — Двадцать нулей этого многочлена находятся в геометрической прогрессии с общим отношением 2, и, следовательно, частное не может быть большим. Действительно, нули $w$ $2$ довольно устойчивы к большим относительным изменениям коэффициентов. $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}$

Эффект основы

Разложение выражает полином в определенном базисе, а именно в базисе мономов. Если полином выражается в другом базисе, то задача нахождения его корней может перестать быть плохо обусловленной. Например, в форме Лагранжа небольшое изменение одного (или нескольких) коэффициентов не должно слишком сильно менять корни. Действительно, базисные полиномы для интерполяции в точках 0, 1, 2, ..., 20 имеют вид $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.$

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

Для полинома Уилкинсона находим $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.$

Учитывая определение базисного полинома Лагранжа $ℓ 0 (x)$ , изменение коэффициента $d 0$ не приведет к изменению корней $w$ . Однако возмущение других коэффициентов (все равные нулю) немного изменит корни. Поэтому полином Уилкинсона хорошо обусловлен в этом базисе.

Примечания

^ Уилкинсон, Джеймс Х. (1984). "Коварный многочлен". В Gene H. Golub (ред.). Исследования по численному анализу . Математическая ассоциация Америки. стр. 3. ISBN 978-0-88385-126-5.
^ Трефетен, Ллойд Н.; Бау, Дэвид (1997), Численная линейная алгебра , SIAM

Ссылки

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

JH Wilkinson (1959). Оценка нулей плохо обусловленных многочленов. Часть I. Numerische Mathematik 1 :150–166.
JH Wilkinson (1963). Ошибки округления в алгебраических процессах . Englewood Cliffs, Нью-Джерси: Prentice Hall.

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

Ф.С. Эктон, Численные методы, которые работают , ISBN 978-0-88385-450-1 , стр. 201.

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

Рональд Г. Мосье (июль 1986 г.). Корневые окрестности многочлена. Математика вычислений 47 (175):265–273.
JH Wilkinson (1984). Коварный многочлен. Исследования по численному анализу , под ред. GH Golub, стр. 1–28. (Исследования по математике, т. 24). Вашингтон, округ Колумбия: Математическая ассоциация Америки.

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

Рэй Бувел, «Многочлены и рациональные функции», часть руководства пользователя калькулятора RPN (для Python), получено 29 июля 2006 г.

[1] Уилкинсон, Джеймс Х. (1984). "Коварный многочлен". В Gene H. Golub (ред.). Исследования по численному анализу . Математическая ассоциация Америки. стр. 3. ISBN 978-0-88385-126-5.

[TrefethenBau-2] Трефетен, Ллойд Н.; Бау, Дэвид (1997), Численная линейная алгебра , SIAM