Вилкинсонов полином

У нумеричкој анализи, Вилкинсонов полином је специфицан је специфичан полином који је коришћен од стране Јамес Х. Wилкинсон 1963. године да илуструје потескоце при проналажењу корена полинома: локација корена може бити веома осјетљива на пертурбације у коефицијентима полинома.

Полином је

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

Понекад, термин Вилкинсоновог полинома се такође користи да се односи на неке друге полиноме који се појављују у Вилкинсоновој дискусији.

Позадина

Вилкинсонов полином је настао у проучавању алгоритама за проналажење корена полинома

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

То је природно питање у нумеричкој анализи да се запита да ли је проблем проналаска корена п од коефицијента ц,је добро опремљен .То јест, надамо се да ће мала промјена у коефицијентима довести до мале промјене у коријенима. Нажалост, овде није случај.

Проблем је лоше условљен када полином има више корена. На пример, полином $x^{2}$ има двоструки корен при x=0. Међутим, полином $x^{2}-\varepsilon$ (пертурбација величине $\varepsilon$) има корене на ± √$\varepsilon$, што је много веће од $\varepsilon$ када је $\varepsilon$ мали.

Због тога је природно очекивати да се лоше стање такође дешава када полином има нуле који су веома близу. Међутим, проблем може бити изузетно лоше условљен и за полиноме са добро одвојеним нулама.Вилкинсон је користио полином $w(x)$ да илуструјемо ову тачку (Wилкинсон 1963).

Године 1984. описао је лични утицај овог открића:

Говорећи за себе, сматрам га најтрауматичним искуством у каријери као нумеричком аналитичару

Вилкинсонов полином често се користи да илуструје непожељност наивног рачунарства сопствене вредности матрице прво израчунавајући коефицијенте матрице карактеристични полином и потом проналазе своје корене, јер коришћење коефицијента као међуперирајући корак може увести екстремно лоше стање чак и ако је изворни проблем добро условљен.

Кондиционирање Вилкинсоновог полинома

Вилкинсонов полином

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

јасно има 20 корена, лоцираних на x= 1, 2, ..., 20. Ови корени су далеко раздвојени. Међутим, полином је и даље веома лоше условљен.

Проширује полином, наћи ћете

$w(x)=x^{20}-210x^{19}+20615x^{18}-1256580x^{17}+53327946x^{16}$

$-1672280820x^{15}+40171771630x^{14}-756111184500x^{13}$

$+11310276995381x^{12}-135585182899530x^{11}$

$+1307535010540395x^{10}-10142299865511450x^{9}$

$+63030812099294896x^{8}-311333643161390640x^{7}$

$+1206647803780373360x^{6}-35999795179447607200x^{5}$

$+8037811822645051776x^{4}-12870931245150988800x^{3}$

$+13803759753640704000x^{2}-8752948037671600000x^{}$

$+2432902008176640000$

Ако је коефицијент $x^{19}$ смањен са -210 на до -210.0000001192, онда се полиномна вриједност w (20) смањује од 0 до $-2^{-23}$$20^{19}$= -6.25 × $10^{17}$, а коријен код к = 20 прераст у x ≈ 20.8. Корени на x = 18 и x = 19 удружују се у двоструки корен у x ≈ 18,62 који се претвара у пар сложених коњугираних корена на x ≈ 19,5 ± 1,9и док се пертурбација даље повећава. 20 корена постаје (до 5 децимала)

$1.00000$ $2.00000$ $3.00000$ $4.00000$ $5.00000$

$6.00001$ $6.99970$ $8.00727$ $8.91725$ $20.84691$

$10.09527\pm$ $11.79363\pm$ $13.99236\pm$ $16.73074\pm$ $19.50244\pm$

$0.64350i$ $1.65233i$ $2.51883i$ $2.81262i$ $1.94033i$

Неки корени су веома расељени, иако је промјена коефицијента мала и оригинални корени изгледају широко размакнути .Wилкинсон је показао анализом стабилности која је размотрена у следећем одељку да је ово понашање везано за чињеницу да су неки корени $\alpha$ (као такав $\alpha$=15) има много корена $\beta$ који су "блиски" у смислу да $|\alpha -\beta |$ је мањо од $|\alpha |$

Wилкинсон је изабрао пертурбацију од $2^{-23}$ јер његов Пилот АЦЕ рачунар има 30-битне сигурносне значке са плутајућим тачкама, тако да су бројеви око њих 210,$2^{-23}$ била је грешка у првом биту положај који није заступљен у рачунару. Два стварна броја -210 и -210-$2^{-23}$ , представљају исти број са плутајућим тачкама, што значи $2^{-23}$ је неизбежна грешка у представљању стварног коефицијента близу -210 бројем пливајуће тачке на том рачунару.Анализа пертурбације показује да је 30-битна коефицијентна прецизност недовољна за одвајање корена Вилкинсоновог полинома.

Други пример Вилкинсона

Други пример који Вилкинсон разматра јесте

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

Двадесет нула овог полинома су у геометријској прогресији са заједничким односом 2, а тиме и количник

${\frac {ai}{ai-ak}}$

не може бити велика. Заиста, нуле w2 су прилично стабилне за велике релативне промене у коефицијентима.

Литература

• Ј. Х. Вилкинсон (1959). Евалуација нула лоших полинома. Парт I. Нумерисцхе Матхематик 1: 150-166.
• Ј. Х. Вилкинсон (1963). Заокруживање грешака у алгебарским процесима. Енглевоод Цлиффс, Нев Јерсеи: Прентице Халл.

То се помиње у стандардним уџбеницима у нумеричкој анализи, нпр

• Ф. С. Ацтон, Нумеричке методе које раде. ISBN 978-0-88385-450-1.,, пп. 201.

Остале референце:

• Роналд Г. Мосиер (јул 1986). Роот сусједства полинома. Математика рачунања 47 (175): 265-273.
• Ј. Х. Вилкинсон (1984). Перфидни полином. Студије у нумеричкој анализи, ед. Г. Х. Голуб, пп. 1–28. (Студије математике, вол. 24). Васхингтон, D.C .: Матхематицал Ассоциатион оф Америца.

А хигх-прецисион нумерицал цомпутатион ис пресентед ин:

• Раи Бувел, полиноми и рационалне функције, дио корисничког приручника РПН калкулатора (за Питхон), преузето 29. јула 2006. године.