Algoritmus a függvény nullájának megtalálásához
Egy algoritmust Zérushely egy függvény egy numerikus módszer , vagy egy algoritmust megállapításának közelítő értéket egy x kielégíti f ( x ) = 0 , egy adott funkció f . Itt x egy valós szám az úgynevezett zéró az f vagy ha f polinomiális, gyökere az f .
Ha x vektor, akkor az x megtalálásának algoritmusait , amelyek f ( x ) = 0 , általában "egyenletrendszer numerikus megoldásának algoritmusainak" nevezzük. Ezek az algoritmusok a függvény nullájának megállapítására szolgáló algoritmusok általánosításai, és lineáris vagy nemlineáris egyenletekre is alkalmazhatók . A nullák keresésére szolgáló algoritmusok (mint Newton módszere ) általánosíthatók a nemlineáris egyenletek rendszereinek numerikus felbontására.
A függvény nulláinak megtalálásához szükséges algoritmusokat numerikus analízissel tanulmányozzuk .
Specifikus algoritmusok
Kettősség
A dichotómiás módszer a legegyszerűbb algoritmus a folytonos függvény nulláinak megkeresésére : kezdjen két olyan a és b ponttal, amelyek körülveszik a függvény nulla értékét , és minden egyes iterációnál válassza ki a két intervallum egyikét [ a , c ] vagy [ c , b ] , c = ( a + b ) / 2 pedig a középpontját egy és b . Az algoritmus az [ a , b ] nulla értékű részintervallumának megválasztásán alapul . A legtöbb esetben a dichotómiás módszer garantálja a nullához való konvergenciát, ha a funkció folyamatos . Haladása a kutatásban meglehetősen lassú, mivel a konvergencia sebessége lineáris. Ezen algoritmus egyik sajátossága, hogy előre meg lehet tudni az egyenlet gyökerének kívánt pontossággal történő meghatározásához szükséges iterációk számát.
Newton-Raphson
A Newton módszer , más néven Newton-Raphson, tegyük fel, hogy f jelentése a C osztályú 1 . Az f függvényt a függvény deriváltjának felhasználásával „linearizáljuk” az aktuális hozzávetőleges nulla értékre. Ez megadja az ismétlődési összefüggést :
Newton módszere nem biztos, hogy konvergál, ha a kezdeti érték túl messze van a nullától. Ha azonban konvergál, akkor sokkal gyorsabb, mint a dichotómiás módszer (konvergencia sebessége kvadratikus ). Könnyen általánosítható a magasabb dimenziók problémáira.
Metsző
Ha a függvény deriváltját Newton módszerében véges különbség váltja fel , akkor megkapjuk a szekáns metódust . Az ismétlődő kapcsolatot használja:
.
Ez a módszer nem igényli a derivált számítását, de a konvergencia sebességének lassabb, mint Newtoné (1,618 nagyságrendű). Mivel azonban iterációnként csak funkciófelmérést igényel, általában gyorsabb, mint Newton módszere. 1-nél nagyobb dimenzióban való általánosítása Broyden (en) módszere .
Regula falsi
A hamis helyzet módszer, más néven regula falsi módszer , hasonló a dichotómiás módszerhez. Az intervallumot azonban nem mindegyik iterációnál két egyenlő részre vágja, hanem egy pontra, amelyet a szekáns módszer képlete ad meg. Ez a módszer örökli a dichotómiás módszer robusztusságát és a szekáns módszer „szuper-lineáris” komplexitását.
Muller módszere
A szekáns módszer kiértékeli az f függvény gyökerét lineáris interpolációval történő közelítéssel . Az eljárás Muller értékeli a gyökér által másodfokú interpolációs használatával számított utolsó három pontot. Gyorsabban konvergál, mint a szekán módszer (a konvergencia sorrendje 1,84). Minden iterációhoz négyzetgyök értékelése szükséges. A módszer sajátossága, hogy az iterált x n kifejezés összetetté válhat .
Inverz másodfokú interpoláció
A Müller-módszer hátránya elkerülhető az f reciprok bijekciójának interpolálásával , ami inverz kvadratikus interpolációs módszerhez vezet . Ismételten a konvergencia aszimptotikusan gyorsabb, mint a szekáns módszer, de gyakran rosszul viselkedik, ha az iterációk nincsenek közel a nullához.
Brent módszer
A Brent-módszer a dichotómiás módszer, a szekáns módszer és az inverz kvadratikus interpoláció kombinációja. Minden egyes iterációnál ez a módszer eldönti, hogy a három módszer közül melyik a legvalószínűbb, hogy megközelíti a nullát, és végrehajt egy lépést ezzel a módszerrel. Ez egy robusztus és gyors módszert eredményez, amely nagyon népszerű és nagyra értékelt.
Konjugált gradiens
Egyéb algoritmusok
Más nulla keresési algoritmus a következő:
- fix pont módszer : az egyenlet f ( x ) = 0 átformáljuk formájában x = g ( x ) , ahol a g úgy választjuk meg, hogy bármely sorrendben ( x n ) által adott x n +1 = g ( x n ) konvergál egy n értéke f .
A polinom gyökereinek megkeresése
Különös figyelmet fordítottak a speciális esetben, ha f egy polinom függvény . Természetesen az előző szakaszban leírt módszerek használhatók. Különösen könnyű meghatározni egy polinom származékát, és Newton módszere nagyon jó jelölt. De lehet olyan módszert választani, amely kihasználja azt a tényt, hogy f polinom.
Az egyik lehetőség, hogy fontolja meg a társa mátrix társított polinom. Tudva, hogy ennek a mátrixnak a sajátértékei egybeesnek a polinom gyökeivel, akkor bármelyik sajátérték-kereső algoritmust felhasználhatjuk a kezdeti polinom gyökereinek közelítő értékeinek megkeresésére, például az iterált teljesítmény-módszerre .
Egy másik lehetőség Laguerre módszerének alkalmazása , amely bizonyos körülmények között minden bizonnyal az egyik gyökér (a globális konvergencia) felé konvergál. A konvergencia sebessége köbös az egyszerű gyökerek esetében.
Ha a polinomnak racionális együtthatói vannak, és ha csak racionális gyökereket keresünk, akkor Ruffini módszere használható.
A kutatási probléma hozzávetőleges értékeinek gyökerei minden esetben rossz állapotúak lehetnek, amint azt Wilkinson (in) polinomok mutatják .
Hivatkozások
(fr) Ez a cikk részben vagy teljesen kivenni a Wikipedia cikket angolul című „ gyökkereső algoritmus ” ( lásd a szerzők listáját ) .Lásd is
Kapcsolódó cikkek
- Algoritmus a pozitív valós n-edik gyökének kiszámításához .
- Kör az elválasztási módszer
- Dandelin-Gräffe módszer (en)
- Sturm tétele