Полином Уилкинсона - Wilkinsons polynomial

График полинома Уилкинсона

Участок сигн (ш(Икс)) журнал (1 + -ш(Икс)-)

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

Многочлен равен

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

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

Фон

Многочлен Уилкинсона возник при изучении алгоритмов нахождения корней многочлена.

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

При численном анализе естественным вопросом является вопрос о том, существует ли проблема нахождения корней п из коэффициентов c_я является хорошо кондиционированный. То есть мы надеемся, что небольшое изменение коэффициентов приведет к небольшому изменению корней. К сожалению, здесь дело обстоит иначе.

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

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

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

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

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

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

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

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

явно имеет 20 корней, расположенных в Икс = 1, 2, ..., 20. Эти корни далеко друг от друга. Однако многочлен по-прежнему очень плохо обусловлен.

Раскладывая полином, находим

${\displaystyle {\begin{aligned}w(x)={}&x^{20}-210x^{19}+20615x^{18}-1256850x^{17}[phone]x^{16}\\&{}-1672280820x^{15}[phone]x^{14}-756111184500x^{13}\\&{}[phone]x^{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}}}$

Если коэффициент Икс¹⁹ уменьшено с −210 на 2⁻²³ до −210.0000001192, то значение полинома ш(20) уменьшается от 0 до −2⁻²³20¹⁹ = −6.25×10¹⁷, а корень в Икс = 20 увеличивается до Икс ≈ 20,8. Корни в Икс = 18 и Икс = 19 входят в двойной корень при Икс ≈ 18,62, который превращается в пару комплексно сопряженных корней при Икс ≈ 19.5 ± 1.9я при дальнейшем увеличении возмущения. 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⁻²³ потому что его Пилотный ACE компьютер был 30-битным плавающая точка значения, поэтому для чисел около 210, 2⁻²³ была ошибка в первой битовой позиции, не представленной в компьютере. Два действительных числа, −210 и −210 - 2⁻²³, представлены одним и тем же числом с плавающей запятой, что означает, что 2⁻²³ это неизбежный ошибка представления реального коэффициента, близкого к -210, числом с плавающей запятой на этом компьютере. Анализ возмущений показывает, что 30-битный коэффициент точность недостаточно для разделения корней многочлена Уилкинсона.

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

Предположим, что мы возмущаем многочлен п(Икс) = Π (Икс − α_j) с корнями α_j добавив небольшое кратное т·c(Икс) полинома c(Икс), и спросите, как это влияет на корни α_j. В первом порядке изменение корней будет контролироваться производной

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

Когда производная большая, корни будут менее устойчивыми при вариациях т, и наоборот, если эта производная мала, корни будут устойчивыми. В частности, если α_j кратный корень, то знаменатель обращается в нуль. В этом случае α_j обычно не дифференцируема по т (пока не c там может исчезнуть), и корни будут крайне неустойчивыми.

Для малых значений т возмущенный корень дается разложением в степенной ряд по т

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

и ждут проблем, когда |т| больше, чем радиус сходимости этого степенного ряда, который задается наименьшим значением |т| такой, что корень α_j становится множественным. Очень грубая оценка этого радиуса занимает половину расстояния от α_j до ближайшего корня и делится на производную, указанную выше.

В примере полинома Уилкинсона степени 20 корни задаются формулой α_j = j за j = 1, ..., 20 и c(Икс) равно Икс¹⁹.Поэтому производная дается формулой

${\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}}.\,\!}$

Это показывает, что корень α_j будет менее устойчивым, если корней много α_k близко к α_j, в том смысле, что расстояние | α_j - α_k| между ними меньше, чем | α_j|.

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

Пример. С другой стороны, для рута α₂₀ = 20 производная равна −20¹⁹/ 19! который огромен (около 43000000), поэтому этот корень очень чувствителен к небольшим изменениям в т. Другие корни β близки к α₂₀, в том смысле, что |β − α₂₀| = 1, 2, 3, ..., 19 меньше |α₂₀| = 20. Для т = −2 ^− 23 приближение первого порядка 20 -т·20¹⁹/ 19! = 25,137 ... до возмущенного корня 20,84 ... ужасно; это еще более очевидно для корня α₁₉ где возмущенный корень имеет большую мнимую часть, но приближение первого порядка (и в этом отношении все приближения более высокого порядка) являются действительными. Причина такого расхождения в том, что |т| ≈ 0,000000119 больше, чем радиус сходимости упомянутого выше степенного ряда (который составляет около 0,0000000029, что несколько меньше значения 0,00000001, полученного по грубой оценке), поэтому линеаризованная теория неприменима. Для такого значения, как т = 0,000000001, что значительно меньше этого радиуса сходимости, приближение первого порядка 19,9569 ... достаточно близко к корню 19,9509 ...

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

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

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

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

Двадцать нулей этого многочлена находятся в геометрической прогрессии с общим отношением 2, и, следовательно, частное

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

не может быть большим. Действительно, нули ш₂ довольно устойчивы к большим относительный изменения коэффициентов.

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

Расширение

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

выражает полином в определенном базисе, а именно в базисе одночленов. Если многочлен выражен в другом базисе, то проблема нахождения его корней может перестать быть плохо обусловленной. Например, в Форма Лагранжа небольшое изменение одного (или нескольких) коэффициентов не должно слишком сильно изменять корни. Действительно, базисные многочлены для интерполяции в точках 0, 1, 2, ..., 20 равны

${\displaystyle \ell _{k}(x)=\prod _{i\in \{0,\ldots ,20\}\setminus \{k\}}{\frac {x-i}{k-i}},\qquad {\text{for}}\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{with}}\quad d_{0}=(20!),\,d_{1}=d_{2}=\cdots =d_{20}=0.}$

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

Примечания

1. Уилкинсон, Джеймс Х. (1984). «Вероломный полином». В Джине Х. Голуб (ред.). Исследования в области численного анализа. Математическая ассоциация Америки. п. 3. ISBN  978-0-88385-126-5.
2. Trefethen, Lloyd N .; Бау, Дэвид (1997), Числовая линейная алгебра, СИАМ

Рекомендации

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

• Дж. Х. Уилкинсон (1959). Вычисление нулей плохо обусловленных многочленов. Часть I. Numerische Mathematik 1:150–166.
• Дж. Х. Уилкинсон (1963). Ошибки округления в алгебраических процессах. Энглвуд Клиффс, Нью-Джерси: Прентис Холл.

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

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

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

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

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

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