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

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

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 ima dvostruki koren pri x=0. Međutim, polinom (perturbacija veličine ) ima korene na ± √, što je mnogo veće od kada je 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 да илуструјемо ову тачку (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[1]

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.[2]

Kondicioniranje Vilkinsonovog polinoma[уреди | уреди извор]

Vilkinsonov polinom

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

Ako je koeficijent smanjen sa -210 na do -210.0000001192, onda se polinomna vrijednost w (20) smanjuje od 0 do = -6.25 × , 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)

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 (kao takav =15) ima mnogo korena koji su "bliski" u smislu da je manjo od

Wilkinson je izabrao perturbaciju od jer njegov Pilot ACE računar ima 30-bitne sigurnosne značke sa plutajućim tačkama, tako da su brojevi oko njih 210, bila je greška u prvom bitu položaj koji nije zastupljen u računaru. Dva stvarna broja -210 i -210- , predstavljaju isti broj sa plutajućim tačkama, što znači 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

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

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

Reference[уреди | уреди извор]

  1. ^ Wilkinson, James H. (1984)."Perfidni polinom". U ed. Gene H. Golub. Studije u numeričkoj analizi. Matematičko udruženje Amerike. стр. 3.
  2. ^ Trefethen, Lloyd N.; Bau, David (1997), Numerical Linear Algebra, SIAM

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

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: