Полином Уилкинсона - Wilkinson's polynomial

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

Полином равен

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

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

Фон

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

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

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

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

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

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

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

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

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

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

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

явно имеет 20 корней, расположенных в точках x = 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 {} + 8037811822881251776x ^950811822645051776x ^9 {3} \\ & {} + 13803759753640704000x ^ {2} -8752948036761600000x \\ & {} + 2432902008176640000. \ end {align}}}$

Если коэффициент при x ¹⁹ уменьшается с −210 на 2 ⁻²³ до −210,0000001192, то значение полинома w (20) уменьшается с 0 до −2 ⁻²³ 20 ¹⁹  = −6,25 × 10 ¹⁷ , а корень при x  = 20 увеличивается до x  ≈ 20,8. Корни при x  = 18 и x  = 19 сталкиваются в двойной корень при x ≈ 18,62, который превращается в пару комплексно сопряженных корней при x ≈ 19,5 ± 1,9 i при дальнейшем увеличении возмущения. 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 ^-23 , потому что его пилот ACE компьютер имел 30-бит с плавающей точкой significands , так что для чисел около 210, 2 ^-23 была ошибка в первом положении бита не представлены на компьютере. Два действительных числа, −210 и −210-2 ⁻²³ , представлены одним и тем же числом с плавающей запятой, что означает, что 2 ⁻²³ - это неизбежная ошибка при представлении реального коэффициента, близкого к −210, числом с плавающей запятой на этом компьютер. Анализ возмущений показывает, что 30-битной точности коэффициента недостаточно для разделения корней полинома Уилкинсона.

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

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

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

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

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

${\ 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 ( x ) равно x ¹⁹ . Таким образом, производная дается формулой

${\ 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! который очень маленький; этот корень стабилен даже при больших изменениях t . Это потому, что все другие корни β очень далеки от него в том смысле, что | α ₁  -  β | = 1, 2, 3, ..., 19 больше, чем | α ₁ | = 1. Например, даже если t достигает –10000000000, корень α ₁ изменяется только от 1 до примерно 0,99999991779380 (что очень близко к приближению первого порядка 1 +  t / 19! ≈ 0,99999991779365). Точно так же другие малые корни полинома Уилкинсона нечувствительны к изменениям  t .

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

На первый взгляд корни α ₁ = 1 и α ₂₀ = 20 полинома Уилкинсона кажутся похожими, поскольку они находятся на противоположных концах симметричной линии корней и имеют одинаковый набор расстояний 1, 2, 3, .. ., 19 от других корней. Однако приведенный выше анализ показывает, что это грубое заблуждение: корень α ₂₀ = 20 менее устойчив, чем α ₁ = 1 (к небольшим возмущениям в коэффициенте x ¹⁹ ) в 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}}$

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

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

Расширение

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

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

Примечания

использованная литература

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

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

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

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

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

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

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

• Ray Buvel, Polynomials And Rational Functions , часть Руководства пользователя RPN Calculator (для Python), получено 29 июля 2006 г.