Многочлен Уилкинсона
Многочлен Уилкинсона — классический пример в вычислительной математике, демонстрирующий высокую чувствительность корней многочлена к малым изменениям его коэффициентов. Этот полином был использован Джеймсом Харди Уилкинсоном в 1963 году для иллюстрации трудностей, возникающих при численном решении алгебраических уравнений: нули функции могут резко изменяться даже при незначительных погрешностях в коэффициентах.
Стандартный многочлен Уилкинсона определяется как произведение: Иногда под этим термином понимают и другие полиномы, фигурирующие в работах Уилкинсона по анализу устойчивости.
Предпосылки создания[править | править код]
Полином возник в ходе исследований алгоритмов поиска корней многочленов вида В численном анализе важно понимать, насколько хорошо обусловлена задача вычисления корней по заданным коэффициентам. Идеальным случаем является ситуация, когда малые вариации коэффициентов приводят к малым изменениям корней. Однако для многочлена Уилкинсона это условие не выполняется.
Задача становится плохо обусловленной при наличии кратных корней. Например, полином имеет кратный нуль в точке 0. Его возмущённая версия при малом имеет корни , которые значительно удалены от нуля.
Можно ожидать, что плохая обусловленность также проявляется при наличии близко расположенных корней. Однако Уилкинсон показал, что задача может быть крайне неустойчивой даже для полинома с хорошо разделёнными корнями, используя в качестве примера .
В 1984 году учёный так охарактеризовал своё открытие:
«Лично для себя я считаю это самым травмирующим опытом в моей карьере специалиста по численным методам.»
Многочлен Уилкинсона часто приводят как аргумент против вычисления собственных значений матрицы через поиск корней её характеристического полинома. Использование коэффициентов в качестве промежуточного шага может привести к крайне плохо обусловленной задаче, даже если исходная проблема была устойчивой.
Устойчивость многочлена Уилкинсона[править | править код]
Многочлен имеет 20 очевидных корней, расположенных в точках от 1 до 20. Несмотря на их кажущуюся изолированность, полином остаётся очень плохо обусловленным.
После раскрытия скобок получается следующая запись:
Если коэффициент при уменьшить с −210 на величину (примерно ), то есть до −210,0000001192, то значение падает с 0 до , а корень смещается примерно к 20,8. Корни и сливаются в кратный корень около 18,62, который при дальнейшем увеличении возмущения распадается на пару комплексно-сопряжённых корней . В результате 20 корней (с точностью до пяти знаков) принимают значения:
Некоторые корни претерпевают значительные изменения, несмотря на мизерную поправку к коэффициенту и изначально большое расстояние между корнями. Как показал Уилкинсон в анализе устойчивости, такое поведение объясняется тем, что для некоторых корней (например, ) существуют другие корни , которые являются «близкими» в том смысле, что много меньше .
Учёный выбрал возмущение , потому что его компьютер Pilot ACE использовал 30-битные числа с плавающей запятой. На этой машине числа −210 и −210 − 2−23 представлялись одним и тем же значением, то есть была неизбежной ошибкой округления для коэффициента около −210. Анализ возмущений показывает, что 30 бит точности недостаточно для корректного разделения корней многочлена Уилкинсона.
Анализ устойчивости[править | править код]
Рассмотрим полином с корнями . Добавим малое возмущение , где — некоторый многочлен, и исследуем, как изменятся корни . В первом приближении скорость их смещения определяется производной: Малая величина производной свидетельствует об устойчивости корня, большая — о высокой чувствительности. В частности, если является кратным корнем, знаменатель обращается в ноль, производная не определена, и корни становятся чрезвычайно неустойчивыми.
При малых положение возмущённого корня можно описать степенным рядом: Проблемы возникают, когда превышает радиус сходимости этого ряда, который определяется наименьшим значением , при котором корень становится кратным. Грубую оценку радиуса можно получить, взяв половину расстояния от до ближайшего корня и разделив на упомянутую производную.
Для многочлена Уилкинсона 20-й степени корни равны , а в качестве рассмотрим . Тогда производная принимает вид: Из этой формулы видно, что корень будет менее устойчив, если существует много корней , близких к нему в том смысле, что расстояние мало по сравнению с .
Пример 1. Для корня производная равна и очень мала. Этот корень устойчив даже при значительных возмущениях, поскольку все остальные корни удалены от него на расстояния 1, 2, …, 19, которые больше, чем . Например, при корень смещается с 1 примерно до 0,99999991779380, что близко к предсказанию линейной теории: . Аналогично, другие малые корни полинома Уилкинсона мало чувствительны к изменениям.
Пример 2. Для корня производная равна , то есть очень велика, что указывает на высокую чувствительность. Многие другие корни находятся близко к , поскольку расстояния до них (1, 2, …, 19) меньше . При возмущении линейное приближение даёт значение , которое сильно отличается от истинного смещённого корня (~20,84). Для корня ситуация ещё более показательна: возмущённый корень становится комплексным, в то время как линейное (и все последующие) приближения остаются вещественными. Это связано с тем, что величина превышает радиус сходимости соответствующего степенного ряда (примерно ), поэтому линейная теория неприменима. Для меньших возмущений, например , линейное приближение 19,9569… оказывается близко к истинному корню 19,9509…
На первый взгляд корни и кажутся симметричными, поскольку оба находятся на концах цепочки корней и имеют одинаковый набор расстояний до остальных корней. Однако анализ показывает, что это сходство обманчиво: корень менее устойчив, чем , в раз.
Второй пример Уилкинсона[править | править код]
Другим примером, рассмотренным Уилкинсоном, служит полином Его двадцать корней образуют геометрическую прогрессию. В этом случае отношения не могут быть большими. Следовательно, корни данного многочлена устойчивы к существенным относительным изменениям коэффициентов.
Влияние выбора базиса[править | править код]
Стандартная запись полинома использует базис мономов. Представление многочлена в другом базисе может улучшить обусловленность задачи поиска корней. Например, в базисе интерполяционных полиномов Лагранжа малое изменение одного или нескольких коэффициентов не обязательно вызывает сильное смещение корней. Базисные полиномы для узлов 0, 1, 2, …, 20 имеют вид:
Любой многочлен степени не выше 20 можно выразить в этом базисе:
Для многочлена Уилкинсона получаем:
В силу свойств базиса Лагранжа изменение коэффициента не влияет на корни полинома. Изменение же других коэффициентов (изначально нулевых) приводит лишь к незначительным сдвигам корней. Таким образом, в базисе Лагранжа многочлен Уилкинсона становится хорошо обусловленным.
Примечания[править | править код]
Литература[править | править код]
Ссылки[править | править код]
Уилкинсон впервые рассмотрел этот многочлен в работе:
- 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.