Полином Уилкинсона - Википедия - 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 {align} w (x) = {} & x ^ {20} -210x ^ {19} + 20615x ^ {18} -1256850x ^ {17} + 53327946x ^ {16} & {} -1672280820x ^ {15} + 40171771630x ^ {14} -756111184500x ^ {13} & {} + 11310276995381x ^ {12} -135585182899530x ^ {11} & {} + 1307535010540395x ^ {10} ^511422998 9} & {} + 63030812099294896x ^ {8} -311333643161390640x ^ {7} & {} + 1206647803780373360x ^ {6} -3599979517947607200x ^ {5} & {} + 8037811822881251776x ^ 945811822645051776x ^9 {3} & {} + 13803759753640704000x ^ {2} -8752948036761600000x & {} + 2432902008176640000. end {align}}}$

Если коэффициент Икс¹⁹ уменьшено с −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} более 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 {xi} {ki}}, 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₀ не приведет к изменению корней ш. Однако изменение других коэффициентов (все равны нулю) немного изменит корни. Следовательно, многочлен Уилкинсона хорошо обусловлен в этом базисе.

Примечания

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

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

• Дж. Х. Уилкинсон (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 г.