Перейти к содержанию

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

Статья из Авикипедии. Энциклопедии

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

Стандартный многочлен Уилкинсона определяется как произведение: w(x)=∏i=120(x−i)=(x−1)(x−2)⋯(x−20). Иногда под этим термином понимают и другие полиномы, фигурирующие в работах Уилкинсона по анализу устойчивости.

Предпосылки создания[править | править код]

Полином возник в ходе исследований алгоритмов поиска корней многочленов вида p(x)=∑i=0ncixi. В численном анализе важно понимать, насколько хорошо обусловлена задача вычисления корней по заданным коэффициентам. Идеальным случаем является ситуация, когда малые вариации коэффициентов приводят к малым изменениям корней. Однако для многочлена Уилкинсона это условие не выполняется.

Задача становится плохо обусловленной при наличии кратных корней. Например, полином x2 имеет кратный нуль в точке 0. Его возмущённая версия x2−ε при малом ε имеет корни ±ε, которые значительно удалены от нуля.

Можно ожидать, что плохая обусловленность также проявляется при наличии близко расположенных корней. Однако Уилкинсон показал, что задача может быть крайне неустойчивой даже для полинома с хорошо разделёнными корнями, используя в качестве примера w(x).

В 1984 году учёный так охарактеризовал своё открытие:

«Лично для себя я считаю это самым травмирующим опытом в моей карьере специалиста по численным методам.»

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

Устойчивость многочлена Уилкинсона[править | править код]

Многочлен w(x)=∏i=120(x−i)=(x−1)(x−2)⋯(x−20) имеет 20 очевидных корней, расположенных в точках от 1 до 20. Несмотря на их кажущуюся изолированность, полином остаётся очень плохо обусловленным.

После раскрытия скобок получается следующая запись: w(x)=x20−210x19+20615x18−1256850x17+53327946x16−1672280820x15+40171771630x14−756111184500x13+11310276995381x12−135585182899530x11+1307535010540395x10−10142299865511450x9+63030812099294896x8−311333643161390640x7+1206647803780373360x6−3599979517947607200x5+8037811822645051776x4−12870931245150988800x3+13803759753640704000x2−8752948036761600000x+2432902008176640000.

Если коэффициент при x19 уменьшить с −210 на величину 2−23 (примерно 1,192×10−7), то есть до −210,0000001192, то значение w(20) падает с 0 до −2−23⋅2019≈−6,25×1017, а корень x=20 смещается примерно к 20,8. Корни x=18 и x=19 сливаются в кратный корень около 18,62, который при дальнейшем увеличении возмущения распадается на пару комплексно-сопряжённых корней 19,5±1,9i. В результате 20 корней (с точностью до пяти знаков) принимают значения: 1,000002,000003,000004,000005,000006,000016,999708,007278,9172520,8469110,09527±11,79363±13,99236±16,73074±19,50244±0,64350i1,65233i2,51883i2,81262i1,94033i

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

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

Анализ устойчивости[править | править код]

Рассмотрим полином p(x)=∏(x−αj) с корнями αj. Добавим малое возмущение t⋅c(x), где c(x) — некоторый многочлен, и исследуем, как изменятся корни αj. В первом приближении скорость их смещения определяется производной: dαjdt=−c(αj)p′(αj). Малая величина производной свидетельствует об устойчивости корня, большая — о высокой чувствительности. В частности, если αj является кратным корнем, знаменатель обращается в ноль, производная не определена, и корни становятся чрезвычайно неустойчивыми.

При малых t положение возмущённого корня можно описать степенным рядом: αj+dαjdtt+d2αjdt2t22!+⋯ Проблемы возникают, когда |t| превышает радиус сходимости этого ряда, который определяется наименьшим значением |t|, при котором корень αj становится кратным. Грубую оценку радиуса можно получить, взяв половину расстояния от αj до ближайшего корня и разделив на упомянутую производную.

Для многочлена Уилкинсона 20-й степени корни равны αj=j, а в качестве c(x) рассмотрим x19. Тогда производная принимает вид: dαjdt=−αj19∏k≠j(αj−αk)=−∏k≠jαjαj−αk. Из этой формулы видно, что корень αj будет менее устойчив, если существует много корней αk, близких к нему в том смысле, что расстояние |αj−αk| мало по сравнению с |αj|.

Пример 1. Для корня α1=1 производная равна 1/19! и очень мала. Этот корень устойчив даже при значительных возмущениях, поскольку все остальные корни удалены от него на расстояния 1, 2, …, 19, которые больше, чем |α1|=1. Например, при t=−1010 корень смещается с 1 примерно до 0,99999991779380, что близко к предсказанию линейной теории: 1+t/19!≈0,99999991779365. Аналогично, другие малые корни полинома Уилкинсона мало чувствительны к изменениям.

Пример 2. Для корня α20=20 производная равна −201919!≈−4,3×107, то есть очень велика, что указывает на высокую чувствительность. Многие другие корни находятся близко к α20, поскольку расстояния до них (1, 2, …, 19) меньше |α20|=20. При возмущении t=−2−23 линейное приближение даёт значение 20−2019t19!≈25,137, которое сильно отличается от истинного смещённого корня (~20,84). Для корня α19 ситуация ещё более показательна: возмущённый корень становится комплексным, в то время как линейное (и все последующие) приближения остаются вещественными. Это связано с тем, что величина |t|≈1,19×10−7 превышает радиус сходимости соответствующего степенного ряда (примерно 2,9×10−9), поэтому линейная теория неприменима. Для меньших возмущений, например t=10−9, линейное приближение 19,9569… оказывается близко к истинному корню 19,9509…

На первый взгляд корни α1=1 и α20=20 кажутся симметричными, поскольку оба находятся на концах цепочки корней и имеют одинаковый набор расстояний до остальных корней. Однако анализ показывает, что это сходство обманчиво: корень α20=20 менее устойчив, чем α1=1, в 2019≈5,24×1024 раз.

Второй пример Уилкинсона[править | править код]

Другим примером, рассмотренным Уилкинсоном, служит полином w2(x)=∏i=120(x−2−i)=(x−2−1)(x−2−2)⋯(x−2−20). Его двадцать корней образуют геометрическую прогрессию. В этом случае отношения αjαj−αk не могут быть большими. Следовательно, корни данного многочлена устойчивы к существенным относительным изменениям коэффициентов.

Влияние выбора базиса[править | править код]

Стандартная запись полинома p(x)=∑i=0ncixi использует базис мономов. Представление многочлена в другом базисе может улучшить обусловленность задачи поиска корней. Например, в базисе интерполяционных полиномов Лагранжа малое изменение одного или нескольких коэффициентов не обязательно вызывает сильное смещение корней. Базисные полиномы для узлов 0, 1, 2, …, 20 имеют вид: ℓk(x)=∏i=0,…,20i≠kx−ik−i,дляk=0,…,20.

Любой многочлен степени не выше 20 можно выразить в этом базисе: p(x)=∑i=020diℓi(x).

Для многочлена Уилкинсона получаем: w(x)=(20!)ℓ0(x)=∑i=020diℓi(x)сd0=(20!),d1=d2=⋯=d20=0.

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

Примечания[править | править код]

Литература[править | править код]

Ссылки[править | править код]

Уилкинсон впервые рассмотрел этот многочлен в работе:

  • 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, , p. 201.

Другие источники:

  • Ronald G. Mosier (July 1986). Root neighborhoods of a polynomial. Mathematics of Computation 47(175):265–273.
  • J. H. Wilkinson (1984). 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, , часть RPN Calculator User Manual (для Python), получено 29 июля 2006.

Ссылки[править | править код]