Bulirsch–Stoer-algoritmus

A Bulirsch–Stoer-algoritmus egy eljárás a numerikus analízisben, amely három elméletet egyesít – a Richardson-extrapolációt, a racionális függvények extrapolációjának felhasználását a Richardson-féle alkalmazásokban és a módosított középpont módszerét – a közönséges differenciálegyenletek nagy pontosságú és viszonylag kevés számítással járó megoldására. Roland Bulirsch és Josef Stoer után kapta a nevét. Olykor még Gragg–Bulirsch–Stoer-algoritmusnak is nevezik, mert a módosított középpont hibafüggvényének módszerét William B. Gragg dolgozta ki.

Alapelvek

Richardson extrapolációi felfoghatók numerikus számításként, aminek a pontossága függ a h lépésköztől mint egy h lépésköz analitikus függvénye numerikus számítás különböző h értékekkel egy analitikus függvénysorba helyezve a kapott pontokat, és megoldva a függvénysort h=0 esetén, így próbálva egy megközelítő értéket kapni végtelen sok lépésben.

Bulirsch és Stoer rájöttek, hogy valós függvény használata függvénysorként a Richardson-extrapolációhoz, a numerikus integrálás kiváló a polinom függvényekhez, mert a valós függvény képes jól megközelíteni a keresett pontokat, mivel van elég ereje a nevezőben számot adva. Egy polinom interpoláció vagy extrapoláció jobb eredményt ad ha a közelítő pólusok kívül esnek az ismert adatok köréből, a valós függvény interpoláció vagy extrapoláció képes nagy pontosságú eredményt adni, függetlenül a közelítő értéktől.

A módosított középpont módszer egy másodrendű módszer, és ebből adódóan a negyedrendű Runge-Kutta-módszer alárendeltje. Azonban az előnye, hogy csak egy derivált kiszámítását igényli lépésenként, és ezt Gragg fedezte fel. A módosított középpont hibájának lépéshossza H a teljes n-ből, igy a lépéshossz h=H/n és h erősorozatba fejtve, csak h erőit tartalmazza. Ez nagyon használatos a Bulirsch–Stoer-módszerben, ami a pontosságot két fokkal növeli, míg a különböző eredmény próbálkozás meghaladja a H intervallumot a lépések növelésével.