Polünoomi juurte lahendaja

Polünoomi juurte leidmise matemaatilised alused

Polünoomi juurte leidmine on algebras ja arvutusmeetodites üks põhilisi ülesandeid. Sõltuvalt polünoomi astmest ja kordajatest võib juurte leidmiseks kasutada kas täpseid analüütilisi valemeid või arvulisi ligikaudseid meetodeid.

Matemaatiliselt on erinevus analüütilise ja arvulise lahendamise vahel põhimõtteline. Madalama astme polünoomide puhul on olemas kindlad algebralised valemid. Näiteks 1. astme võrrandi puhul kasutatakse otsest lineaarset lahendust. Ruutvõrrandite (2. aste) ning kolmanda ja neljanda astme võrrandite jaoks on samuti olemas täpsed valemid, mis väljendavad juuri kordajate juurjuurimiste kaudu.

Alates 5. astme polünoomidest tõestab aga Abeli-Ruffini teoreem, et üldist algebralist lahendusvalemit ei ole olemas. See tähendab, et kõrgema astme polünoomide juuri on võimatu leida lõpliku arvu aritmeetiliste tehete ja juurimiste abil. Sellistel puhkudel tuleb appi võtta arvulised ligikaudsed meetodid, mis koonduvad reaalsete ja komplekssete lahendite suunas iteratiivselt.

Ehrlich–Aberth iteratsioonimeetod

Kõrgema astme polünoomide (astmega 2 kuni 20) lahendamiseks kasutab see tööriist Ehrlich–Aberth iteratsioonimeetodit. Erinevalt näiteks Newtoni meetodist, mis otsib ühte juurt korraga ja vajab teiste juurte leidmiseks polünoomi jagamist (deflatsiooni), värskendab Ehrlich–Aberth meetod kõiki juurte algatseid üheaegselt.

Sünkroonne juurte värskendamine toimub järgmiselt:

1. Algoritm alustab deterministlikest komplekssete algatsete komplektidest, mis on jaotatud komplekstasandil spetsiaalse raadiusega ringjoonele.
2. Igas iteratsioonis korrigeeritakse igat algatset, võttes arvesse nii polünoomi väärtust, selle tuletist kui ka teiste praeguste juurekandidaatide asukohti. See hoiab ära olukorra, kus mitu algatset koondub sama juure suunas.
3. Polünoomi ja selle tuletise tõhusaks ja stabiilseks väärtustamiseks igas punktis kasutatakse Horneri meetodit. See skeem vähendab aritmeetiliste tehete arvu ja minimeerib ümardamisvigu.

Juurte tundlikkus ja kordsus

Arvulisel juurte leidmisel on kriitiliseks teguriks polünoomi tundlikkus kordajate väikeste muutuste suhtes. Seda nähtust kirjeldab Wilkinson polünoom, mis näitab, et isegi minimaalne muutus ühes kordajas võib nihutada juurte asukohti komplekstasandil drastiliselt.

Eriti tundlikud on kordsed juured. Kordse juure puhul on nii polünoom ise kui ka selle tuletis (või mitu tuletist) nullis võrdsed nulliga. See muudab korrektsioonisammu matemaatiliselt nõrgaks, kuna tuletisega jagamine läheneb määramatusele. Seetõttu võivad pisikesed kordajate muutused või arvutuslikud ümardamisvead jagada ühe teoreetiliselt kordse juure mitmeks lähedaseks, kuid eraldiseisvaks juureks. Tööriist rühmitab juured kordseteks alles siis, kui nende arvulised väärtused ühtivad väga tihedalt.

Kuidas tööriist arvutab ja kontrollib tulemusi

Kogu arvutusprotsess toimub otse kasutaja veebibrauseris; sisestatud andmeid ja polünoome ei laadita kunagi välistesse serveritesse. Arvutusprotsess koosneb järgmistest sammudest:

1. Standardkuju koondamine: Sisestatud avaldisest koondatakse liikmed standardkujule.
2. Normaliseerimine: Jagage iga kordaja pealiikme kordajaga ‹leading›. See taandab polünoomi pealiikme kordaja üheks.
3. Skaalamine: Skaalake juureotsingut teguriga R = ‹scale›, et esialgsed algatsed jääksid stabiilsesse vahemikku. See hoiab ära arvulise ülevoolu või alavoolu.
4. Itereerimine: Värskendage kõiki juure algatseid koos, kuni korrektsioon on alla ‹tolerance›; selles käituses tehti ‹iterations› iteratsiooni.
5. Verifitseerimine: Asendage iga juur tagasi polünoomi; suurim normaliseeritud jääk on ‹residual›.

Kasutusjuhised ja sisestusreeglid

Tööriist toetab kahte sisestusrežiimi:

• Lahtikirjutatud avaldis ("Lahtikirjutatud avaldis"): Ühe muutujaga võrrand või avaldis, kus liikmed võivad asuda võrdusmärgi mõlemal poolel.
• Kordajate loend ("Kordajate loend"): Mõõtmeteta reaalarvud, mis on eraldatud komade, tühikute või reavahetustega, alates kõrgeimast astmest kuni vabaliikmeni.

Sisestuse piirangud ja reeglid

• Polünoomi aste peab olema vahemikus 1 kuni 20.
• Kordajad peavad olema reaalarvud, mille absoluutväärtus on |kordaja| ≤ 1e100. Lubatud on ka murrud.
• Sisendteksti pikkus on piiratud 600 märgiga.
• Kuvatavate kümnendkohtade arv peab olema vahemikus 4 kuni 12. Suurem täpsusaste muudab algoritmi peatamistesti rangemaks, kuid ei suuda parandada algsetes kordajates juba kaotatud täpsust.

Võimalikud veateated ja hoiatused

Kui sisestatud andmed ei vasta reeglitele, kuvab süsteem vastava veateate:

• Tühja sisendi korral: "Sisestage polünoomavaldis või kordajate loend."
• Liiga pika sisendi puhul: "Hoidke sisend alla 600 märgi."
• Vigase vormingu korral: "See ei ole lahtikirjutatud ühe muutujaga polünoom. Proovige kuju x^5 - x = 0 või sisestage selle kordajad."
• Sulgude kasutamisel: "Kirjutage sulud enne lahti, et igal astmel oleks selge kordaja."
• Mitme muutuja puhul: "Kasutage ainult ühte muutujat."
• Vigaste astmete puhul: "Kasutage täisarvulisi astmeid vahemikus 0 kuni 20."
• Vigase kordaja sisestamisel: "Iga kordaja peab olema reaalarv, näiteks −2.5, 3/4 või 1e-6."
• Nulliga jagamisel murrus: "Murru nimetaja ei tohi olla 0."
• Liiga suurte väärtuste puhul: "Kordaja või vaheskaala on väljaspool toetatud lõplikku vahemikku. Muutke polünoomi skaalat ja proovige uuesti."
• Vale täpsusastme valimisel: "Valige vahemikus 4 kuni 12 kümnendkohta."

Erijuhul, kui sisestatakse nullist erinev konstant, kuvatakse teade: "Nullist erinev konstant ei võrdu kunagi nulliga, seega pole sellel polünoomil juuri." Kui sisestatakse nullpolünoom, kuvatakse teade: "Iga kompleksarv on nullpolünoomi juur."

Korduma kippuvad küsimused

Kas need on täpsed juured?

Ei. Välja arvatud lineaarse võrrandi puhul, on kuvatavad juured arvulised ligikaudsed väärtused. Kõrgematel kui 4. astme võrranditel puudub üldine lahendusvalem juurtes ning isegi madalama astme valemid võivad keeruliste kordajate puhul täpsust kaotada. Kasutage ligikaudsuse hindamiseks jääki ja tundlikkuse hoiatust; kui vajate 2. astme võrrandi jaoks täpseid murde või juuri, kasutage ruutvõrrandi kalkulaatorit.

Mida ma saan sisestada?

Kasutage reaalarvulisi mõõtmeteta kordajaid ja ühte muutujat täisarvuliste astmetega kuni 20. Avaldis peab olema juba lahti kirjutatud, kuid liikmed võivad olla suvalises järjekorras või asuda võrdusmärgi mõlemal poolel. Kordajate loend algab kõrgeimast astmest kuni vabaliikmeni ja peav puuduvate astmete kohal sisaldama nulle.

Kuidas leitakse kõrgema astme juuri?

Lahendaja alustab mitmest deterministlikust komplekssete algatsete komplektist ja parandab korraga kõiki algatseid Ehrlich–Aberth värskendusega. Horneri meetod väärtustab polünoomi ja selle tuletist tõhusalt ning iga tagastatud juur asendatakse tagasi algsesse polünoomi, et teha skaalast sõltumatu jäägi kontroll.

Miks on kordsed juured vähem stabiilsed?

Kordse juure puhul on nii polünoom kui ka selle tuletis null. See nõrgendab korrektsioonisammu, mistõttu võivad pisikesed kordajate muutused jagada ühe kordse juure mitmeks lähedaseks juureks. Lahendaja rühmitab juured alles siis, kui nende arvväärtused ühtivad tihedalt, ja hoiab kordsuse nähtavana.