Vilkinsonov polinom

U numeričkoj analizi, Vilkinsonov polinom je specifican je specifičan polinom koji je korišćen od strane James H. Wilkinson 1963. godine da ilustruje poteskoce pri pronalaženju korena polinoma: lokacija korena može biti veoma osjetljiva na perturbacije u koeficijentima polinoma.

Polinom je

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

Ponekad, termin Vilkinsonovog polinoma se takođe koristi da se odnosi na neke druge polinome koji se pojavljuju u Vilkinsonovoj diskusiji.

Pozadina

Vilkinsonov polinom je nastao u proučavanju algoritama za pronalaženje korena polinoma

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

To je prirodno pitanje u numeričkoj analizi da se zapita da li je problem pronalaska korena p od koeficijenta c,je dobro opremljen .To jest, nadamo se da će mala promjena u koeficijentima dovesti do male promjene u korijenima. Nažalost, ovde nije slučaj.

Problem je loše uslovljen kada polinom ima više korena. Na primer, polinom $x^2$ ima dvostruki koren pri x=0. Međutim, polinom $x^2-\epsilon$ (perturbacija veličine $\epsilon$) ima korene na ± √$\epsilon$, što je mnogo veće od $\epsilon$ kada je $\epsilon$ mali.

Zbog toga je prirodno očekivati da se loše stanje takođe dešava kada polinom ima nule koji su veoma blizu. Međutim, problem može biti izuzetno loše uslovljen i za polinome sa dobro odvojenim nulama.Vilkinson je koristio polinom $w(x)$ да илуструјемо ову тачку (Wilkinson 1963).

Godine 1984. opisao je lični uticaj ovog otkrića:

Govoreći za sebe, smatram ga najtraumatičnim iskustvom u karijeri kao numeričkom analitičaru

Vilkinsonov polinom često se koristi da ilustruje nepoželjnost naivnog računarstva sopstvene vrednosti matrice prvo izračunavajući koeficijente matrice karakteristični polinom i potom pronalaze svoje korene, jer korišćenje koeficijenta kao međuperirajući korak može uvesti ekstremno loše stanje čak i ako je izvorni problem dobro uslovljen.

Kondicioniranje Vilkinsonovog polinoma

Vilkinsonov polinom

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

jasno ima 20 korena, lociranih na x= 1, 2, ..., 20. Ovi koreni su daleko razdvojeni. Međutim, polinom je i dalje veoma loše uslovljen.

Proširuje polinom, naći ćete

$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$

Ako je koeficijent $x^{19}$ smanjen sa -210 na do -210.0000001192, onda se polinomna vrijednost w (20) smanjuje od 0 do $-2^{-23}$$20^{19}$= -6.25 × $10^{17}$, a korijen kod k = 20 prerast u x ≈ 20.8. Koreni na x = 18 i x = 19 udružuju se u dvostruki koren u x ≈ 18,62 koji se pretvara u par složenih konjugiranih korena na x ≈ 19,5 ± 1,9i dok se perturbacija dalje povećava. 20 korena postaje (do 5 decimala)

$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$

Neki koreni su veoma raseljeni, iako je promjena koeficijenta mala i originalni koreni izgledaju široko razmaknuti .Wilkinson je pokazao analizom stabilnosti koja je razmotrena u sledećem odeljku da je ovo ponašanje vezano za činjenicu da su neki koreni $\alpha$ (kao takav $\alpha$=15) ima mnogo korena $\beta$ koji su "bliski" u smislu da $|\alpha -\beta |$ je manjo od $|\alpha |$

Wilkinson je izabrao perturbaciju od $2^{-23}$ jer njegov Pilot ACE računar ima 30-bitne sigurnosne značke sa plutajućim tačkama, tako da su brojevi oko njih 210,$2^{-23}$ bila je greška u prvom bitu položaj koji nije zastupljen u računaru. Dva stvarna broja -210 i -210-$2^{-23}$ , predstavljaju isti broj sa plutajućim tačkama, što znači $2^{-23}$ je neizbežna greška u predstavljanju stvarnog koeficijenta blizu -210 brojem plivajuće tačke na tom računaru.Analiza perturbacije pokazuje da je 30-bitna koeficijentna preciznost nedovoljna za odvajanje korena Vilkinsonovog polinoma.

Drugi primer Vilkinsona

Drugi primer koji Vilkinson razmatra jeste

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

Dvadeset nula ovog polinoma su u geometrijskoj progresiji sa zajedničkim odnosom 2, a time i količnik

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

ne može biti velika. Zaista, nule w2 su prilično stabilne za velike relativne promene u koeficijentima.

Literatura

• J. H. Vilkinson (1959). Evaluacija nula loših polinoma. Part I. Numerische Mathematik 1: 150-166.
• J. H. Vilkinson (1963). Zaokruživanje grešaka u algebarskim procesima. Englevood Cliffs, Nev Jersei: Prentice Hall.

To se pominje u standardnim udžbenicima u numeričkoj analizi, npr

• F. S. Acton, Numeričke metode koje rade. Шаблон:Page,, pp. 201.

Ostale reference:

• Ronald G. Mosier (jul 1986). Root susjedstva polinoma. Matematika računanja 47 (175): 265-273.
• J. H. Vilkinson (1984). Perfidni polinom. Studije u numeričkoj analizi, ed. G. H. Golub, pp. 1–28. (Studije matematike, vol. 24). Vashington, D.C .: Mathematical Association of America.

A high-precision numerical computation is presented in:

• Rai Buvel, polinomi i racionalne funkcije, dio korisničkog priručnika RPN kalkulatora (za Pithon), preuzeto 29. jula 2006. godine.