Közelítő módszerek

Közelítő megoldásnak nevezünk egyes matematikai problémákra olyan formában adott válaszokat, hogy azok az elvárt, ideális megoldástól egy elvárt mértéknél kevésbé térjenek el. Rendszerint rekurzív vagy iteratív módszereket veszünk igénybe ebből a célból, de ez egyáltalán nem kötelező. Azonban utóbbi esetben is mindenképpen kell egy kiindulási érték, amit szintén közelítő megoldásnak vagy 0. közelítésnek nevezünk.

A probléma típusától függően a közelítő módszer realizációja ténylegesen más és más lehet, de általánosan igaz, hogy numerikus matematikai jellegű. Ez algebrai egyenletek esetén kevésbé problémás, azonban differenciálegyenletek esetén, példának okáért, már gondot okozhat, hogy nem egy függvényt, hanem annak csak egyes pontjait, vagy azok közelítését kapjuk meg. Ebből a megoldásfüggvény előállítása általában valamilyen heurisztikus módszer segítségével történhet – ha az egyáltalán zárt alakban előállítható.

Szintén ide tartozik a függvények közelítése egyszerűbb vagy kényelmesebben kezelhető (esetleg ismert) függvények segítségével. Ennek során nem csak a közelítő függvényeket érdemes megadni, de egy lehetséges hibakorlátot is, azaz a valós függvény mennyiben tér el a közelítő függvénytől vagy függvénysorozattól. Ennek leggyakoribb formája a Fourier-sorok alkalmazása.

A közelítő megoldásoknak a számítástechnikai alkalmazásokban van igen jelentős hasznuk, ugyanis az ilyen jellegű eredményeket a kézzel történő számításoknál nagyságrendekkel gyorsabban kaphatjuk meg, és azokból a tényleges megoldás jellemzően kikövetkeztethető, ha egyáltalán szükségünk van ilyenre.

Általános jellemzés

A közelítő megoldások kereséséhez elsőként rögzítenünk kell, hogy mit tekintünk elfogadható közelítésnek. Az elfogadhatósági határt többféleképpen is rögzíthetjük:

1. Mivel a megoldásokat tipikusan tizedestörtként kapjuk, az egymást követő értékek különbsége egyre kisebb helyiértékekig fog nullákat tartalmazni. Az elfogadható hibát megadhatjuk e sorozat minimális hossza formájában, ezt szokás az értékes (tizedes)jegyek számának nevezni. Például az öt értékes jegy pontosság azt jelenti, hogy két egymást követő, egymásból származó közelítés különbsége kisebb, mint 0,00001.
2. Hasonló az előzőhöz, és hasonló elnevezésnek is örvend, ha a közelítő értékre a probléma inverzét alkalmazva, az a várt értékre nézve legyen adott számú tizedesjegyre egyező. A kettő egymástól lényegesen különbözik, hiszen az első esetben feltétel a rekurzió, itt viszont irreleváns.
3. Megadható az is, hogy a várt érték és a kapott érték milyen arányban legyen egymással. Ezt tipikusan százalékérték formájában szokás megadni. A 95%-os pontosság például azt jelenti, hogy a kapott és a várt érték hányadosa nem kisebb, mint 0,95.

A sorozatokkal való közelítések esetén lényeges kérdés az is, hogy az eljárás konvergens-e, és ha igen, milyen „gyors” a konvergencia. Ez utóbbi alatt azt kell érteni, hogy az egymást követő sorozattagok eltérése egymástól vagy a várt értéktől milyen mértékben csökken.

Rekurzió

Bővebben: Rekurzió

Rekurziónak nevezzük a közelítő eljárások során valamely algoritmus ismétlését. Jellemzően ennek során valamely már korábban megállapított közelítő értékből, vagy közelítő értékek halmazából állítunk elő újabb értéket vagy értékhalmazt. A közelítő eljárások során sokszor a rekurziónak is egy speciális esetét, az iterációt alkalmazzuk.

Tipikus rekurziós eljárások az integrálközelítések és az intervallumfelezéses egyenletmegoldások.

Iteráció

Bővebben: Iteráció

Iteráció során egy függvény segítségével állítunk elő egy sorozatot, mégpedig úgy, hogy megadjuk a sorozat induló tagját, majd a sorozat minden tagját az előzőből ezzel a függvénnyel állítjuk elő:

${\displaystyle x_{0}=c}$

${\displaystyle x_{n+1}=f(x_{n})}$.

Iterációt igen könnyű megvalósítani, azonban igen gyorsan számításigényessé válik. Nem mellékes az a tény sem, hogy igen érzékeny a kezdeti feltételekre, különösen, ha több megoldás is létezik a problémára. Ebben az esetben általában nem megjósolható, hogy egy adott kiindulási érték melyikhez fog elvezetni.

A legjellemzőbb képviselője a Newton-féle iteráció.

Megoldhatóság

Mielőtt egy probléma numerikus megoldásába belekezdenénk, feltétlenül érdemes tudni, hogy egyáltalán számíthatunk-e megoldásra. Ez tulajdonképpen problémakörönként változó, egyértelműen elég nehéz válaszolni rá.

Eredet szerint

Egyes esetekben már a probléma eredete megköveteli a megoldás létezését. Ezek tipikusan kísérleti adatokra támaszkodó problémák, esetleg valós folyamatok modelljei, bár utóbbi esetben a modellben a rosszul megválasztott paraméterek esetlegesen irreális eredményt adhatnak.

Egyenletek

Egyenletek megoldása esetén az egyenlet jellege szerint tovább ágazik a megoldhatósági vizsgálat.

Polinom egyenletek

A komplex számok teste feletti polinomoknak az algebra alaptétele miatt biztosan létezik legalább egy gyöke (valójában annyi, ahányad fokú a polinom), úgyhogy a megoldhatósági vizsgálat jelen esetben a szűkebb halmazokra (valós számok, racionális számok) korlátozódik.

Valós számokon dolgozva, mint leggyakoribb eset, a páratlan fokszámú polinomoknak biztosan van gyöke. Ez egyszerűen annak a következménye, hogy minden komplex gyök esetén a gyök konjugáltja is gyök. A páros fokszámú polinomoknak ellenben nem biztosított a gyök létezése. Másodfokú egyenlet esetén a döntés egyszerű, a diszkrimináns felettébb sokat segít. A magasabb fokú polinomoknál egy lehetőség, hogy felbontjuk alacsonyabb fokszámú polinomok szorzatára, majd ezek megoldhatóságát ellenőrizzük. Célszerű ezeket a polinomokat az egyszerűség érdekében főpolinommá alakítani, illetve változócserével hiányos polinommá.

Külön tisztázandó, hogy egy megadott intervallumon van-e megoldás. Egyes módszerek eleve ezzel a feltételezéssel indítanak, itt nem szükséges a megoldhatósági vizsgálat. Egyébként a rendezett polinom segítségével eldönthető az intervallumon belüli megoldás, mivel ez egyet jelent az intervallumon belüli előjelváltásokkal, azaz

${\displaystyle \exists x,y\in {I},f(x)\cdot f(y)\leq 0\Rightarrow \exists z\in \left[x,y\right],f(z)=0.}$

Sőt, ennél még több is mondható: ha találunk olyan ${\displaystyle x_{0},x_{1},\dots x_{n}}$ szigorúan monoton növekvő sorozatot az intervallumban úgy, hogy az egymást követő tagokra a függvény előjelet vált, akkor a megoldások száma legalább ${\displaystyle n}$.

Megint figyelembe kell venni a páros fokszámú polinomokat – elég az ${\displaystyle x^{2}=0}$ egyenletre gondolni, amely tartósan nemnegatív, de van gyöke. Ezeket újfent a szorzattá bontás módszerével vizsgálhatjuk, de most kifejezetten páratlan fokszámú polinomokat keresünk.

Nem polinomiális egyenletek

Ebben az esetben a megoldhatóság vizsgálata lényegesen nehezebb lehet, mint a polinomok esetében. A komplex számok esetében ez nem okoz problémát, minden nemkonstans ${\displaystyle f(x)}$ polinom esetén az ${\displaystyle f(x)=0}$ egyenletnek van komplex gyöke. A valós eset azonban már keményebb dió. Általában igaz az, hogy ha egy intervallumon történik előjelváltás, akkor ott van gyök, azonban ez nem szükséges feltétel itt sem.

Általában az ilyen egyenleteket valamilyen módon polinomokkal közelítjük már eleve, ebben az esetben a megoldhatóságot visszavezettük az előző esetre. Egészen értelmes eljárás kifejezetten páratlan fokszámú polinommal közelíteni az ott elhangzottak okán.

Egyenletrendszerek

Egyenletrendszerek megoldhatósága lényegesen izgalmasabb probléma, mint az egyenleteké, különösen nemlineáris esetben.

Lineáris egyenletrendszerek

A lineáris egyenletrendszerek numerikus megoldása, megoldhatósága gyakorlatilag lezárt terület, a megoldás közelítés nélkül is megkapható.

Nemlineáris egyenletrendszerek

Több lehetőség is van a megoldhatóság vizsgálatára.

1. Ha ${\displaystyle f(x):\mathbf {R} ^{n}\to \mathbf {R} ^{n}}$ függvény, akkor ezt felfoghatjuk úgy, hogy ${\displaystyle n}$ darab felület közös metszéspontját keressük (ha van ilyen). Erre nézvést az algebrai geometriában használt Bézout-tétel ad felvilágosítást. A tétel egyetlen hátulütője, hogy a ${\displaystyle \mathbf {P} ^{n}}$ projektív tér pontjaiként adja a gyököket, így azok között nem tesz különbséget.

1. Ha az egyenletrendszert a megoldás környezetében kontrakcióvá tudjuk tenni, akkor segítségünkre lehet Banach fixponttétele. A számítás elvégezhetőségéhez feltétlenül szükséges a vizsgált tér végessége.

1. Ha alkalmasan választunk az ${\displaystyle f(x)}$ függvényhez funkcionált, akkor ennek minimumhelyeinek létezését is vizsgálhatjuk.

Egyenletek megoldása

Az egyenletek megoldása során tulajdonképpen zérushelyeket keresünk. Közelítő megoldásokra akkor van szükségünk jellemzően, ha az adott egyenlet nem alakítható át legfeljebb negyedfokú polinommá. A gyakorlatban azonban már a harmadfokú egyenleteknek is eléggé sok számolást igényel az algebrai megoldása,^[1] ezért legfeljebb másodfokú egyenletek esetén alkalmazunk megoldóképletet.

Minden egyenlet a mérlegelv segítségével az

${\displaystyle f(x)=0}$

alakra hozható, eme egyenlet gyökeit igyekszünk megkeresni. Minden esetben feltételezzük, hogy a függvény legalább egy intervallum felett folytonos, vagy folytonossá tehető, ellenkező esetben ugyanis elképzelhető, hogy egyáltalán nincs megoldás, vagy, ami sokkal kellemetlenebb esemény, a közelítő sorozat csak véges sok tagra értelmezhető. A gyökök létezésére vonatkozólag az előző szakasz meggondolásai irányadóak.

Az egyenletek közelítő értékeinek megtalálása geometriailag is interpretálható, ilyen módon ráadásul egyszerűbb esetekben szemléletesebb is. Minden esetben az ${\displaystyle f}$ függvény ívét igyekszünk valamilyen módon egyenessel közelíteni, majd az egyenes tengelymetszetét tekintjük közelítő megoldásnak. Ez megfeleltethető egy lineáris egyenlet megoldásának, ami tipikusan egyszerű feladat.

Ugyan elméletileg bármilyen egyenlet megoldására alkalmasak az ismertetett módszerek, a gyakorlatban azonban csak polinomiális esetekben alkalmazzuk őket a könnyű számíthatóság során. Ez különösen számítógépes megvalósítások esetén lényeges, ugyanis ekkor a nem polinomiális függvényeket is polinomokkal (általában a függvény #Taylor-polinomjával helyettesítjük.

Intervallumfelosztás

Az intervallumfelezés alapja az a tétel, mely szerint ha egy intervallumon folytonos függvény az intervallum végpontjaiban különböző előjelű, akkor van olyan érték az intervallumban, ahol a függvény helyettesítési értéke 0. Röviden:

${\displaystyle f\in {\mathcal {C}}\left(\left[a;b\right]\right)\wedge f(a)f(b)<0\Rightarrow \exists x\in \left[a;b\right]:f(x)=0}$.

Itt ${\displaystyle {\mathcal {C}}\left(\left[a;b\right]\right)}$ az ${\displaystyle \left[a;b\right]}$ intervallumon folytonos függvények halmaza.

Az eljárás során a függvény intervallum-végpontokban felvett értékeire egyenest fektetünk, majd ennek az egyenesnek a tengelymetszetét keressük. Az így kapott ${\displaystyle x}$ érték biztosan jobb közelítés, mint az eredeti intervallum végpontjai. Ebben a pontban kettéválasztjuk az intervallumot, majd a két rész-intervallum közül az választjuk ki, amelyikre az előbbi feltétel érvényes, és erre megismételjük az eljárást. Mint látható, ez egy tipikus rekurziós eljárás. A konvergenciáját a Cantor-féle közösrész-tétel biztosítja. Az elnevezést az indokolja, hogy az intervallumot az egyenes metszéspontja két részre osztja, ezek közül azt a részt tartjuk meg, amiben az egyenlet gyöke található.

Vegye fel a függvény az intervallum végpontjaiban az ${\displaystyle f\left(a\right)}$ és ${\displaystyle f\left(b\right)}$ értékeket. Ekkor a függvényt egy egyenessel tudjuk helyettesíteni, melynek két pontja:

${\displaystyle P\left(a,f\left(a\right)\right)}$ és ${\displaystyle Q\left(b,f\left(b\right)\right)}$,

amikre fel tudjuk írni az egyenest:

${\displaystyle a\cdot f\left(b\right)-b\cdot f\left(a\right)=\left(a-b\right)y-\left(f\left(b\right)-f\left(a\right)\right)x}$.^[2]

Ennek az egyenesnek keressük az x tengellyel való metszéspontját, azaz az ${\displaystyle y=0}$ esetben az egyenlet megoldását. Ez

${\displaystyle x={\frac {b\cdot f\left(a\right)-a\cdot f\left(b\right)}{f\left(a\right)-f\left(b\right)}}.}$

Attól függően, hogy ${\displaystyle f\left(x\right)}$ milyen előjelű, az intervallum megfelelő végpontját x-szel helyettesíthetjük, és az eljárást rekurzívan megismételhetjük. Felmerülhet, mint probléma, hogy e húr minden esetben az intervallumon belül metszi-e az x-tengelyt. Ezt két egyenlőtlenség megoldásával láthatjuk be korrektül, de szemléletesen is kikövetkeztethető. A ${\displaystyle {\vec {PQ}}}$ szakaszt ugyanis ha az x-tengelyre vetítjük úgy, hogy a szakasz végpontjai az intervallum végpontjaira essenek, akkor a köztes pontok képei a kép köztes pontjaira esnek.

Példa

Keressük a ${\displaystyle 3x^{2}-4x-1=0}$ egyenlet megoldásait! Egyszerű számítással kideríthető, hogy egy gyök a ${\displaystyle \left[1;2\right]}$ intervallumban található. Innen a közelítés lépései:

${\displaystyle a}$	${\displaystyle f(a)}$	${\displaystyle b}$	${\displaystyle f(b)}$	${\displaystyle x={\frac {a\cdot f(b)-b\cdot f(a)}{f(b)-f(a)}}}$	${\displaystyle f(x)}$
${\displaystyle 1}$	${\displaystyle -2}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 1,4}$	${\displaystyle -0,72}$
${\displaystyle 1,4}$	${\displaystyle -0,72}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 1,516129}$	${\displaystyle -0,168574}$
${\displaystyle 1,516129}$	${\displaystyle -0,168574}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 1,541871}$	${\displaystyle -0,035381}$
${\displaystyle 1,541871}$	${\displaystyle -0,035381}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 1.613101}$	${\displaystyle .353878}$
${\displaystyle 1,541871}$	${\displaystyle -0,035381}$	${\displaystyle 1,613101}$	${\displaystyle .353878}$	${\displaystyle 1.548345}$	${\displaystyle -0,001261}$
${\displaystyle 1.548345}$	${\displaystyle -0,001261}$	${\displaystyle 1,613101}$	${\displaystyle .353878}$	${\displaystyle 1.548574}$	${\displaystyle -.000046}$
${\displaystyle 1.548574}$	${\displaystyle -0,000046}$	${\displaystyle 1,613101}$	${\displaystyle .353878}$	${\displaystyle 1.548582}$	${\displaystyle -0,000007}$

Láthatólag elég gyorsan, hat lépésben elég közel jutottunk a helyes gyökhöz.

Intervallumfelezéses eljárás

Az eljárás elve hasonló az intervallumfelosztáséhoz. azonban itt az osztópontot a függvénytől függetlenül határozzuk meg. Tulajdonképpen arról van szó, hogy ha az ${\displaystyle x_{1}}$ és ${\displaystyle x_{2}}$ számok közül az egyik felül, a másik alulbecsli az egyenlet gyökét, akkor

${\displaystyle x_{3}={\frac {x_{1}+x_{2}}{2}}}$

jobb közelítés. Ezt megismételhetjük, ha ${\displaystyle f\left(x_{3}\right)}$ értékétől függően ${\displaystyle x_{1}}$-et vagy ${\displaystyle x_{2}}$-t helyettesítjük vele. Könnyű megvalósítása és kicsi számolásigénye miatt kedvelt eljárás, azonban lassan konvergál, különösen, ha a zérushely valamelyik végpont közelében van.

Mivel a módszer megint egymást tartalmazó intervallum-láncot hoz létre, a konvergenciát itt is a Cantor-féle közösrész-tétel biztosítja.

Példa

Keressük meg az ${\displaystyle 2x^{2}-3x-1=0}$ egyenlet megoldásait! Egyszerűen kideríthető, hogy az egyik gyök a ${\displaystyle \left[1;2\right]}$ intervallumban van. Ez alapján az egyenlet megoldására jobb közelítés az ${\displaystyle x=1,5}$. A közelítés lépései:

${\displaystyle a}$	${\displaystyle b}$	${\displaystyle x={\frac {a+b}{2}}}$	${\displaystyle 2x^{2}-3x-1}$
${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 1,5}$	${\displaystyle -1}$
${\displaystyle 1,5}$	${\displaystyle 2}$	${\displaystyle 1,75}$	${\displaystyle -0,125}$
${\displaystyle 1,75}$	${\displaystyle 2}$	${\displaystyle 1,875}$	${\displaystyle 0,40625}$
${\displaystyle 1,75}$	${\displaystyle 1,875}$	${\displaystyle 1.8125}$	${\displaystyle 0,1328125}$
${\displaystyle 1,75}$	${\displaystyle 1,8125}$	${\displaystyle 1,78125}$	${\displaystyle 0,001953125}$
${\displaystyle 1,75}$	${\displaystyle 1,78125}$	${\displaystyle 1.765625}$	${\displaystyle -0,06201171875}$
${\displaystyle 1.765625}$	${\displaystyle 1,78125}$	${\displaystyle 1.7734375}$	${\displaystyle -0,0301513671875}$
${\displaystyle 1.7734375}$	${\displaystyle 1,78125}$	${\displaystyle 1.77734375}$	${\displaystyle -0,014129638671875}$
${\displaystyle 1.77734375}$	${\displaystyle 1,78125}$	${\displaystyle 1.779296875}$	${\displaystyle -0,00609588623046875000}$

Mint látható, valóban elég lassú a közelítés, kilenc lépésben is csak két tizedesjegy pontossággal sikerült megközelíteni a zérushelyet.

Húrmódszer

Az intervallumfelosztásos módszerhez hasonló eljárás, azonban annál némileg hatékonyabb, mivel a függvényt töröttvonallal közelítjük. Ennek megfelelően nem kell, hogy a kiindulási intervallumon vegye fel a zérushelyét a függvény, az azonban igen, hogy folytonos legyen. Lényegében a #Newton-iteráció véges megfelelője.

Az eljárás lényege, hogy a függvény két pontjára húrt illesztünk, majd ennek a húrnak a tengelymetszetét használjuk, mint közelítő értéket. Ha pedig erre vesszük a függvény helyettesítési értékét, akkor a közelítő töröttvonal következő szakaszát is megkapjuk. Az eljárás nagy előnye a gyors konvergencia és a könnyű megvalósíthatóság, utóbbi miatt szívesebben is alkalmazzák, mint a Newton-iterációt.

Ha adott az ${\displaystyle \left(x_{0},f\left(x_{0}\right)\right)}$ és az ${\displaystyle \left(x_{1},f\left(x_{1}\right)\right)}$ pont a függvényhez, akkor rájuk fektetett egyenes egyenletéből a metszéspont meghatározható, a következő összefüggésre vezet:

${\displaystyle x=f\left(x_{0}\right){\frac {x_{0}-x_{1}}{f\left(x_{1}\right)-f\left(x_{0}\right)}}+x_{0}}$

Ebből a rekurzív összefüggést is megadhatjuk:

${\displaystyle x_{n}=f\left(x_{n-2}\right){\frac {x_{n-2}-x_{n-1}}{f\left(x_{n-1}\right)-f\left(x_{n-2}\right)}}+x_{n-2}}$

A használata kényelmesebb, mint az intervallum-osztásos módszereké, mert nem szükséges előzetes becslést adni a zérushelyre. Egyedül az okozhat kényelmetlenséget, ha a húr meredeksége a nulla környékére esik, mivel ekkor nem vagy nagyon messzi értékeknél lesz a metszéspont, és lelassul, esetleg megáll a közelítés. Ennek elkerülésére ebben az esetben a két metszéspont egyikét a számtani közepükkel helyettesítjük.

Példa

Közelítsük a ${\displaystyle x^{3}-x^{2}+x-1=0}$ egyenlet valós gyökét négy tizedesjegy pontossággal!

${\displaystyle x_{n-2}}$	${\displaystyle f\left(x_{n-2}\right)}$	${\displaystyle x_{n-1}}$	${\displaystyle f\left(x_{n-1}\right)}$	${\displaystyle x_{n}}$
${\displaystyle 2,0000}$	${\displaystyle 5,0000}$	${\displaystyle 3,0000}$	${\displaystyle 20,0000}$	${\displaystyle 1,6667}$
${\displaystyle 3,0000}$	${\displaystyle 20,0000}$	${\displaystyle 1,6667}$	${\displaystyle 2,5185}$	${\displaystyle 1,4746}$
${\displaystyle 1,6667}$	${\displaystyle 2,5185}$	${\displaystyle 1,4746}$	${\displaystyle 1,5065}$	${\displaystyle 1,1886}$
${\displaystyle 1,4746}$	${\displaystyle 1,5065}$	${\displaystyle 1,1886}$	${\displaystyle 0,4551}$	${\displaystyle 1,0648}$
${\displaystyle 1,1886}$	${\displaystyle 0,4551}$	${\displaystyle 1,0648}$	${\displaystyle 0,1384}$	${\displaystyle 1,0108}$
${\displaystyle 1,0648}$	${\displaystyle 0,1384}$	${\displaystyle 1,0108}$	${\displaystyle 0,0218}$	${\displaystyle 1,0007}$
${\displaystyle 1,0108}$	${\displaystyle 0,0218}$	${\displaystyle 1,0007}$	${\displaystyle 0,0013}$	${\displaystyle 1,0000}$

Mint láthatjuk, elég gyorsan, mindössze hét lépésben elértük a kitűzött pontosságot. Sőt, ha pontosabban számolunk, itt 5, a következő lépésben 8 tizedesjegy pontossággal kapjuk meg a közelítést.

Newton-iteráció

A Newton-iteráció által létrehozott Julia-halmaz.^[3]

A Newton-iteráció során a függvényt egy pontjában az érintője segítségével közelítjük. Ehhez a függvény deriváltjának ismeretére van szükség.

Ha adott az ${\displaystyle y=f\left(x\right)}$ függvény, akkor egy kiválasztott ${\displaystyle x_{0}}$ abszcisszájú pontban az érintő egyenlete

${\displaystyle y-f\left(x_{0}\right)=f'\left(x_{0}\right)\left(x-x_{0}\right)}$.

Ennek az egyenesnek kell meghatározni a tengelymetszetét, amikor is ${\displaystyle y=0}$, így kapjuk:

${\displaystyle x=x_{0}-{\frac {f\left(x_{0}\right)}{f'\left(x_{0}\right)}}}$.

Ebből az iteráció már egyszerűen, rekurzív ismétlésként adódik:

${\displaystyle x_{n+1}=x_{n}-{\frac {f\left(x_{n}\right)}{f'\left(x_{n}\right)}}}$.

A Newton-iteráció a leggyorsabban konvergáló általános közelítő módszer, hátránya, hogy nem minden esetben mondható meg, hogy több zérushely esetén melyiket kaphatjuk meg. Mi több, ha megjelöljük azokat a pontokat, amikből kiindulva egy adott gyökhöz konvergálunk, akkor jellemzően fraktálokat kapunk eredményül, bár ez már pusztán a módszer iteratív mivoltából is sejthető. Ez különösen igaz a komplex síkon vizsgálódva.

A realizáció során a legnagyobb problémát az egyes pontokban a differenciálhányados meghatározása jelenti, éppen emiatt inkább a húrmódszert szokás használni helyette. A másik jellegzetes probléma, hogy sok esetben a függvény helyettesítési értékét is csak közelítőleg ismerjük, ilyenek például az exponenciális függvények, emiatt a Newton-iterációt leginkább polinomok zérushelyeinek keresésére használják.

Példa

Határozzuk meg a 13 köbgyökét! Ez annyit tesz, hogy az

${\displaystyle x^{3}-13=0}$

egyenletet igyekszünk megoldani. Ennek egy valós gyöke van, ezért valós függvények esetén nem kell foglalkoznunk azzal, hogy melyik gyököt kapjuk meg, komplex számokon azonban ez gondot jelenthet.

Az egyenlet bal oldalának deriváltfüggvénye:

${\displaystyle f'\left(x\right)=3x^{2}}$

ez minden pontban folytonos és véges. A sorozat iterációs formája:

${\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}^{3}-13}{3x_{n}^{2}}}={\frac {2x_{n}^{3}+13}{3x_{n}^{2}}}}$

amiből tetszőleges ${\displaystyle x_{0}}$ esetén megkapjuk az egyetlen valós gyököt. A lépések csökkentése miatt azonban érdemes egy olyan értéktől elindulni, aminek a második hatványa megközelítőleg 13. A példánkban ez legyen a 2, mivel ${\displaystyle 2^{3}=8\approx 13}$.

${\displaystyle n}$	${\displaystyle x_{n}}$	${\displaystyle x_{n}^{3}}$
0	${\displaystyle 2}$	${\displaystyle 8}$
1	${\displaystyle 2,41666666666666666666}$	${\displaystyle 14,11400462962962962962}$
2	${\displaystyle 2,35308495177698507068}$	${\displaystyle 13,02905206226310003674}$
3	${\displaystyle 2,35133598927373461071}$	${\displaystyle 13,00002158799190549781}$
4	${\displaystyle 2,35133468772147794793}$	${\displaystyle 13,00000000001194975726}$
5	${\displaystyle 2,35133468772075748950}$	${\displaystyle 13,00000000000000000000}$

Szemmel láthatóan rettentő gyorsan, az értékes tizedesjegyek számának exponenciális növekedésével konvergál az iteráció, gyakorlatilag öt lépésben 20 tizedesjegy pontosságot érhettünk el.

Egyenletrendszerek megoldása

Az egyenletrendszerek megoldása során, akárcsak a egyenletek esetén, a lineáris esetben explicit módon meghatározható a megoldás létezése és maga a megoldás is, ezért itt a közelítő megoldásokkal nem foglalkozunk. A nemlineáris egyenletek egyes esetekben ugyan linearizálhatóak, azonban sokszor még ebben az esetben is értelmes megoldás lehet inkább közelítő módszereket alkalmazni, különösen, mert ezek megint csak algoritmizálhatóak, így az embernél hatékonyabban számoló eszközökre bízhatjuk magunkat.

Magára a megoldhatóságra vonatkozólag három különböző szemlélet is létezik:

1. Ha az egyenleteket, mint görbéket vagy felületeket fogjuk fel, akkor az algebrai geometriából ismert Bézout-tétel ad felvilágosítást mind a megoldhatóságról, mind a megoldások számáról.
2. Egy alkalmasan választott funkcionál esetén a megoldhatóság egyenértékű eme funkcionál szélsőértékeinek létezésével.
3. Az egyenletrendszert átalakíthatjuk leképezéssé, ekkor fixpont tételek, leggyakrabban a Banach-féle fixpont tétel segítségével dönthetjük el a problémát.

Az utóbbi esetben a számítás elvégzéséhez szükséges a véges dimenziós mivolta a függvénytérnek.

Newton-iteráció egyenletrendszerekre

A nemlineáris egyenletrendszerek megoldása során szinte kizárólagosan alkalmazott módszer, ugyanis rendkívül gyors konvergencia jellemzi, és mindössze első deriváltakat tartalmaz. Általában már ezek kinyerése sem egyszerű feladat, nemhogy a magasabb rendűeké. Az alkalmazáshoz az egydimenziós eset deriváltját általánosítjuk. Írjuk az egyenletrendszert

${\displaystyle {\vec {f}}\left({\vec {x}}\right)={\vec {0}}}$

alakba, ekkor az egydimenzióshoz hasonló alakot kapunk. Ennek deriváltja a Jacobi-mátrix:

${\displaystyle {\vec {f}}'=\left(f_{ij}\right)=\left({\frac {\partial f_{i}}{\partial x_{j}}}\right)}$

Mivel általában a vektortereken nem értelmezett az osztás, ezért a newtoni eljárást kissé más alakban kell felírnunk:

${\displaystyle {\vec {f}}'\left({\vec {x}}_{m}\right)\delta {\vec {x}}=-{\vec {f}}\left({\vec {x}}_{m}\right)}$

${\displaystyle {\vec {x}}_{m+1}={\vec {x}}_{m}+\delta {\vec {x}}}$

Az első egyenletrendszer lineáris, így ${\displaystyle \delta {\vec {x}}}$ meghatározása egyszerű (aránylag).^[4] Bizonyítható, hogy a módszer másodrendben konvergál.

Függvények közelítése

Ugyan általában kevéssé érdekes feladat, azonban egyes esetekben szükségünk lehet némely függvények meghatározott helyen felvett helyettesítési értékére, vagy magának a függvénynek a közelítésére. Ez legtöbbször csak köztes lépés valamely számítás során, ilyen például az egyenletek megoldása. A számítógépes alkalmazások során is a nem polinomiális függvényeket valamilyen közelítő polinommal helyettesítjük, ezeket általában a kiválasztott programnyelv matematikai függvénykönyvtárai tartalmazzák.

A függvények adott pontbeli helyettesítési értékének kiszámítása történhet a közelítő polinomok segítségével is, de erre általában a Newton-iterációt alkalmazzák. Ehhez a függvény inverzével kifejezzük a független változót, és az így kapott egyenletet igyekszünk megoldani. Sok esetben azonban az inverz függvényt is az itt ismertetett közelítő függvények segítségével számítjuk ki.

Ha a teljes függvényt kívánjuk közelíteni, azt általában függvénysorokkal tesszük. A gyakorlatban ez leginkább a függvények számítógépes közelítését jelenti. Ebben az esetben egy olyan különleges problémával találkozunk, hogy a számítógép által megvalósítható műveletek (összeadás, szorzás, stb..) segítségével az eredeti függvényt minél pontosabban közelíthessük. Ez vagy magas fokú függvényekkel, vagy a vizsgált tartomány szűkítésével érhető el. A modern alkalmazások általában a kettőt öszvér módon használják: a teljes tartományt kis részhalmazokra bontják, és ezeken közelítenek magas fokú polinomokkal.

Hiba az optimális polinom és log(x) közt (piros) és a Csebisev approximáció és log(x) (kék) a [2,4] intervallumon. A függőleges vonalak ${\displaystyle 10^{-5}}$ távolsággal vannak behúzva. Az optimális polinom maximum hibája ${\displaystyle 6,07x10^{-5}}$

Hiba az optimális polinom és exp(x) közt (piros) és a Csebisev approximáció és exp(x) (kék) a [-1,1] intervallumon. A függőleges vonalak ${\displaystyle 10^{-5}}$ távolsággal vannak behúzva. Az optimális polinom maximum hibája ${\displaystyle 5,47x10^{-4}}$

Optimális polinomok

Első lépésként meg kell határoznunk azt a tartományt, ami felett a függvényt közelíteni fogjuk, valamint a közelítő polinom fokát. Ezután magát a polinomot úgy választjuk, hogy a minimalizáljuk a lehető legrosszabb eset hibáját. A cél tehát ${\displaystyle |P(x)-f(x)|}$ értékének minimalizálása, ahol ${\displaystyle P(x)}$ a közelítés, ${\displaystyle f(x)}$ pedig a közelítendő függvény. Szép függvények esetén létezik egy N-edfokú polinom, melynek hibagörbéje +${\displaystyle \varepsilon }$ és -${\displaystyle \varepsilon }$ közt oszcillál összesen N+2-szer, ${\displaystyle \varepsilon }$-ra korlátozva a lehető legnagyobb hibát. Egy N-ed fokú polinom képes N+1 görbén lévő pontot interpolálni. Egy ilyen polinom mindig optimális. Lehetséges olyan mesterséges függvények előállítása, melyekre nem létezik ilyen polinom, viszont ezek a gyakorlatban ritkán fordulnak elő.

Nézzük például jobb oldalt a ${\displaystyle \log(x)}$ és ${\displaystyle \exp(x)}$ közelítését N=4 esetén. A piros grafikon pontosan +${\displaystyle \varepsilon }$ és -${\displaystyle \varepsilon }$ között oszcillál. Vegyük észre, hogy a szélsőértékek száma N+2, azaz 6. Két szélsőértéket az intervallum végpontjain találunk, a grafikon két szélén.

'>P(x)-f(x) hibafüggvénye (piros) és jobb polinommal való közelítése (kék)

Ennek általános bizonyítása végett tegyük fel, hogy P egy N-ed fokú polinom az előzőleg tárgyalt tulajdonságokkal, azaz létrehoz egy N+2 szélsőértékkel rendelkező hibafüggvényt, melyeknek azonos a magnitúdója és váltakozó előjelűek. A piros grafikon mutatja, hogyan nézhetne ki egy ilyen függvény N=4 esetén.

Tegyük fel, hogy ${\displaystyle Q(x)}$ (melynek hibafüggvényét kékkel jelöljük) egy másik N-ed fokú polinom, mely ${\displaystyle f}$-nek jobb közelítése, mint ${\displaystyle P}$. Bővebben: ${\displaystyle Q}$ közelebb van ${\displaystyle f}$-hez mint ${\displaystyle P}$ minden ${\displaystyle x_{i}}$ esetén, ahol egy ${\displaystyle P-f}$ szélsőérték lép fel. Azaz

${\displaystyle |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|}$

Ahol P-f-nek maximuma van x_i-ben, ott

${\displaystyle Q(x_{i})-f(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=P(x_{i})-f(x_{i}),}$

Ahol P-f-nek minimuma van x_i-ben, ott

${\displaystyle f(x_{i})-Q(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=f(x_{i})-P(x_{i}).}$

Amint tehát a grafikonon látszik, ${\displaystyle \left[P(x)-f(x)\right]-\left[Q(x)-f(x)\right]}$-nek alternálnia kell előjelben ${\displaystyle x_{i}}$ N+2 értéke esetén. Viszont ${\displaystyle \left[P(x)-f(x)\right]-\left[Q(x)-f(x)\right]}$ egyszerűsödik ${\displaystyle P(x)-Q(x)}$-szá, ami egy N-ed fokú polinom. Ez a függvény legalább N+1-szer vált előjelet, tehát a Bolzano–Darboux-tételnek megfelelően N+1 zérushelye van, amely lehetetlen N-ed fokú polinom esetén.

Taylor-polinomok

A Taylor-polinom egy függvény Taylor-sorának részsorozata. Mint ilyen, a függvény egy közelítő polinomja, segítségével a függvényértékek igen jól becsülhetőek, általában számítógépes rendszerekben nyernek alkalmazást. Sok esetben, ha egy egyenlet nem kezelhető, a Taylor-polinomok segítségével igen jó becsléseket adhatunk rájuk, amik révén a polinomokra alkalmazott módszereket is felhasználhatjuk az egyenlet megoldásában.

Ha ismert valamely értékre a függvény helyettesítési értéke, akkor ennek környezetében a Taylor-polinom közelíti a függvényt. A közelítés annál jobb, minél több taggal közelítünk, és annál rosszabb, minél távolabb vagyunk az ismert ponttól. A polinom:

${\displaystyle \sum _{i=1}^{n}{\frac {\left(\mathrm {D} ^{n}f\right)\left(x_{0}\right)}{n!}}\left(x-x_{0}\right)^{n}}$, ahol ${\displaystyle \mathrm {D} }$ a differenciáloperátor.

Mint látható, a polinom ismeretéhez elengedhetetlen a függvény ${\displaystyle x_{0}}$-beli differenciálhányadosainak ismerete, ami esetleg megnehezítheti a polinom kiszámítását. Ennek okán rendszerint olyan ${\displaystyle x_{0}}$ értéket igyekszünk választani, hogy lehetőleg minél több differenciálhányados értéke legyen ismert, ugyanakkor a polinom se legyen túlzottan bonyolult.

Néhány függvény Taylor-polinomja

A polinomfüggvények Taylor-polinomjai önmaguk, ezeket külön nem soroljuk fel.

Függvény	${\displaystyle x_{0}}$	${\displaystyle n}$		Megjegyzések
${\displaystyle e^{x}}$	${\displaystyle 0}$	${\displaystyle 4}$	${\displaystyle 1+x+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}+{\frac {x^{4}}{24}}}$
${\displaystyle \sin x}$	${\displaystyle 0}$	${\displaystyle 7}$	${\displaystyle x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}$	Csak az első periódusban jó.
${\displaystyle \cos x}$	${\displaystyle 0}$	${\displaystyle 6}$	${\displaystyle 1-{\frac {x^{2}}{2}}+{\frac {x^{4}}{24}}-{\frac {x^{6}}{720}}}$	Akárcsak a szinusz, csak az első periódusban közelít.
${\displaystyle \ln x}$	${\displaystyle 1}$	${\displaystyle 4}$	${\displaystyle \left(x-1\right)-{\frac {\left(x-1\right)^{2}}{2}}+{\frac {\left(x-1\right)^{3}}{3}}-{\frac {\left(x-1\right)^{4}}{4}}}$

Bernstein-polinomok

A Bernstein-polinomok a Csebisev-tétel következményeként állíthatóak elő. A polinomok sorozata egyenletesen konvergál a függvényhez. Használatuk egyetlen hátulütője, hogy racionális pontokban ismernünk kell a függvény helyettesítési értékét. Igazából a jelentőségük inkább elméleti, a folytonos függvényekre vonatkozó egyes tételek bizonyítása során jelentkezik hasznosságuk.

Az ${\displaystyle f\left(x\right)}$ függvény n-edik Bernstein-polinomjának konkrét alakja:

${\displaystyle B_{n}\left(f\left(x\right)\right)=\sum _{i=0}^{n}f\left({\frac {i}{n}}\right){\dbinom {i}{n}}x^{i}\left(1-x\right)^{n-i}}$

Csebisev approximáció

Az optimális polinomot nagyon jól közelíthetjük, ha kifejtjük az adott függvényt Csebisev polinomok szerint és ezt követően levágjuk a kifejtést a kívánt foknál. Ez az eljárás hasonlít a sor Fourier-sorok általi függvényközelítéshez, Csebisev polinomokat használva trigonometrikus függvények helyett.

Ha kiszámoljuk egy függvény Csebisev kifejtés által keletkező tagoknak együtthatóit:

${\displaystyle f(x)\sim \sum _{i=0}^{\infty }c_{i}T_{i}(x)}$

és utána levágjuk a sorozatot a ${\displaystyle T_{n}}$-edik tag után, egy N-ed fokú f(x)-et közelítő polinomhoz jutunk.

Ez a polinom azért közel optimális, mert gyorsan konvergáló sorú függvények esetén, ha elvágjuk a sort valamelyik tagjánál, az elvágás által keletkező hiba nagyon közel van a levágást követő taghoz. Azaz a levágást követő tag dominálja az összes hátralévő tagot. Ugyanez igaz, ha a kifejtés a Csebisev polinomoknak megfelelően történik. Ha egy Csebisev kifejtést ${\displaystyle T_{n}}$-nél vágjuk le, a hiba ${\displaystyle T_{n+1}}$ többszöröseként fog előállni. A Csebisev polinomoknak megvan az a tulajdonságuk, hogy +1 és -1 között oszcillálnak a [-1, 1] intervallumon. ${\displaystyle T_{n+1}}$-nek N+2 szélsőértéke van, azaz közel van az optimális N-ed fokú polinomhoz.

A fenti grafikonokon a kék közelítés néha jobb, mint a piros függvény, néha pedig rosszabb, melyek szerint nem teljesen az optimális polinom. Vegyük észre, hogy a különbség enyhébb az exp függvény esetén, mely egy sokkal gyorsabban konvergáló hatványsor, mint a log függvény.

Remez algoritmusa

A Remez algoritmus segítségével előállíthatunk egy P(x) optimális polinomot egy adott f(x) függvény közelítésére egy adott intervallumon. Egy iteratív algoritmus, mely egy N+2 szélsőértékű függvény polinomjához konvergál. A fenti tétel alapján ez a polinom optimális.

Remez algoritmusa kihasználja azt a tényt, hogy előállítható egy N-ed fokú polinom, mely adott N+2 pont esetén alternáló szélsőértékekhez vezet.

Adott N+2 ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$ ... ${\displaystyle x_{n+2}}$ pont esetén (ahol ${\displaystyle x_{1}}$ és ${\displaystyle x_{n+2}}$ feltehetően a közelítendő intervallum végpontjai) a következő egyenlőségeket kell megoldani:

${\displaystyle P(x_{1})-f(x_{1})=+\varepsilon \,}$

${\displaystyle P(x_{2})-f(x_{2})=-\varepsilon \,}$

${\displaystyle P(x_{3})-f(x_{3})=+\varepsilon \,}$

${\displaystyle \vdots }$

${\displaystyle P(x_{n+2})-f(x_{n+2})=\pm \varepsilon .\,}$

A jobb oldali értékek előjele váltakozik, azaz

${\displaystyle P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}...P_{n}x_{1}^{n}-f(x_{1})=+\varepsilon \,}$

${\displaystyle P_{0}+P_{1}x_{2}+P_{2}x_{2}^{2}+P_{3}x_{2}^{3}...P_{n}x_{2}^{n}-f(x_{2})=-\varepsilon \,}$

${\displaystyle \vdots }$

Mivel ${\displaystyle x_{1}}$ ... ${\displaystyle x_{n+2}}$ adottak voltak, minden hatványuk ismert és ${\displaystyle f(x_{1})}$ ... ${\displaystyle f(x_{n+2})}$ szintén ismert. Ez azt jelenti, hogy a fenti egyenletek csupán n+2 lineáris egyenlet n+2 változóval: ${\displaystyle P_{0}}$, ${\displaystyle P_{1}}$ ... ${\displaystyle P_{n}}$, and ${\displaystyle \varepsilon }$.

Az adott ${\displaystyle x_{1}}$ ... ${\displaystyle x_{n+2}}$ pontok segítségével megoldható ez az egyenletrendszer és előállítható a P polinom és ${\displaystyle \varepsilon }$.

Az alábbi grafikon szemlélteti ezt az eljárást, előállítva egy 4-ed fokú polinomot az ${\displaystyle e^{x}}$ [-1, 1] intervallumon való közelítésére. Az adott pontok a -1; -0,7; -0,1; +0,4; +0,9; és 1. Azok értéke zölddel van ábrázolva. ${\displaystyle \varepsilon }$ értéke 4,43 x 10⁻⁴

A polinom hibája Remez algoritmusának első lépése segítségével előállítva, ${\displaystyle e^{x}}$-et becsülve a [-1,1] intervallumon. A függőleges vonalak ${\displaystyle 10^{-4}}$ távolsággal vannak behúzva.

Vegyük észre, hogy a hiba-görbe valóban nem veszi föl ${\displaystyle \pm \varepsilon }$ értéket az adott 6 pontban, beszámítva a végpontokat, melyek nem szélsőértékek. Ha a 4 belső pont szélsőérték lett volna (azaz a ${\displaystyle P(x)-f(x)}$-nek minimuma vagy maximuma lett volna e helyeken), a polinom optimális lenne.

Remez algoritmusának második lépése az adott pontokat a lehető legközelebb vinni oda, ahol a hibafüggvénynek a valóságos lokális minimuma vagy maximuma van. Például ha a grafikont tekintjük, látjuk, hogy a -0,1 pontnak valahol a -0,28 környezetében kellett volna lennie. Az algoritmusban ezt a Newton-módszer egyszeri alkalmazása segítségével érjük el. Mivel a ${\displaystyle P(x)-f(x)}$ első és második deriváltjai ismertek, kiszámolható, hogy közelítően milyen messze kell egy adott pontot mozgatni, hogy a derivált nulla legyen.

Egy polinom deriváltjainak kiszámítása egyszerű. Szükséges kiszámolni ${\displaystyle f(x)}$ első és második deriváltjait. Remez algoritmusának feltétele, hogy képesek legyünk kiszámolni ${\displaystyle f(x)}$, ${\displaystyle f'(x)}$ és ${\displaystyle f''(x)}$-et nagyon nagy pontossággal. Az algoritmus kivitelezésének pontossága felül kell múlja az elvárt eredmény pontosságát.

Miután elmozgattuk a pontokat, megismételjük a lineáris egyenletrendszerre vonatkozó részt, új polinomot kapva és a Newton-módszer segítségével újonnan mozgatjuk a pontokat. Ezt a módszert ismételjük addig, mígnem az eredmény az elvárt pontossághoz konvergál. Az algoritmus nagyon gyorsan konvergál; szép függvények esetén kvadratikusan – ha az adott pontok ${\displaystyle 10^{-15}}$-nél közelebb vannak a helyes értéktől, közel ${\displaystyle 10^{-30}}$ távol lesznek az algoritmus következő körében.

Remez algoritmusát tipikusan a ${\displaystyle T_{n}}$ Csebisev polinom szélsőértékeit adott pontokként használva kezdjük el, hisz a végső hibafüggvény hasonlítani fog ahhoz a polinomhoz.

Integrálás

Bővebben: Integrál

Az egyik leggyakoribb közelítési probléma különböző határozott integrálok értékének kiszámolása. Ez különböző okok miatt lehet problémás, leggyakrabban a primitív függvény nehéz meghatározása vagy pedig annak véges alakjának hiánya miatt. Ennek megoldására többféle módszert is kidolgoztak, ezek különböző mértékben konvergálnak.

Minden esetben arról van szó, hogy a függvény görbéjét valamilyen töröttvonallal vagy egyszerűen számítható ívekkel közelítjük, és az így kapott összeggel közelítjük a függvény határozott integrálját. Természetesen ehhez az intervallumot fel kell osztani, ez szoros összefüggésben van a közelítés hibájával.

Minden esetben valamely ${\displaystyle \left[a;b\right]}$ intervallum felett kíséreljük meg megállapítani a függvény integrálját, ennek érdekében az intervallumban felveszünk ${\displaystyle n}$ darab értéket úgy, hogy azok láncot alkossanak, azaz ${\displaystyle \forall k<n:x_{k}<x_{k+1}}$, valamint az első és utolsó osztásköz az intervallum két végpontja legyen, azaz ${\displaystyle x_{0}=a}$ és ${\displaystyle x_{n}=b}$.

A legtöbb függvény esetében ráadásul a helyettesítési értékeket sem tudjuk számítani, csak valamilyen módszerrel becsülni, ez további bizonytalanságot ad az integrál közelítéséhez.

Téglalap-közelítés

Ez a becslési eljárás igazából a Riemann-integrál definíciójának alkalmazása. A függvény görbéjét egy lépcsőzetes függvénnyel közelítjük, ennek a területe könnyen számolható. Attól függően, hogy a beosztás melyik oldalán vesszük fel a "lépcsőt", beszélünk alsó és felső közelítésről. Általában a kettőt együtt alkalmazzák, hogy a valós értéket minél pontosabban lehessen megbecsülni, azonban még így is igen finom beosztás kell a jó becsléshez, különösen, ha a függvény erősen változó (például ilyen az exponenciális függvény).^[5]

A közelítés konvergenciáját a Riemann-integrálra vonatkozó tételek biztosítják, ezek egyben tartalmazzák azon tulajdonságokat is, amelyeknek teljesülniük kell a függvényekre. Általában azonban elmondhatjuk, hogy a gyakorlatban előforduló függvényekre, habár igen erős feltételekről van szó, ezek teljes egészében teljesülnek.

Alsó közelítés

Az intervallum felosztásánál az ${\displaystyle \left[x_{k};x_{k+1}\right]}$ osztásközre ${\displaystyle f\left(x_{k}\right)}$ magasságú téglalapot emelünk. Ennek területe ${\displaystyle f\left(x_{k}\right)\left(x_{k+1}-x_{k}\right)}$. Ha az összes osztásközre összegzünk, akkor a függvény integrálját alulról becsüljük:

${\displaystyle s_{n}=\sum _{k=0}^{n-1}f\left(x_{k}\right)\left(x_{k+1}-x_{k}\right)\approx \int \limits _{a}^{b}f}$

Felső közelítés

Az intervallum felosztásánál az ${\displaystyle \left[x_{k};x_{k+1}\right]}$ osztásközre ${\displaystyle f\left(x_{k+1}\right)}$ magasságú téglalapot emelünk. Ekkor a téglalap területe ${\displaystyle f\left(x_{k+1}\right)\left(x_{k+1}-x_{k}\right)}$, amiket összegezve kapjuk a felső integrálközelítő összeget:

${\displaystyle S_{n}=\sum _{k=0}^{n-1}f\left(x_{k+1}\right)\left(x_{k+1}-x_{k}\right)\approx \int \limits _{a}^{b}f}$

Trapéz-módszer

Hasonló a téglalap-közelítéshez, azonban a függvény ívét nem lépcsős függvénnyel, hanem töröttvonallal közelítjük. Ekkor a beosztások feletti közelítő négyszög egy trapéz lesz, melynek magassága ${\displaystyle x_{i}-x_{i-1}}$, az alapjai pedig a felvett függvényértékek. A trapéz területe innen már számítható:

${\displaystyle t_{i}={\frac {f\left(x_{i-1}\right)+f\left(x_{i}\right)}{2}}\left(x_{i}-x_{i-1}\right)}$

amit már összegezhetünk, így a határozott integrál közelítésére a következő összeget nyerjük:

${\displaystyle \int \limits _{a}^{b}f\approx \sum _{i=1}^{n}t_{i}=\sum _{i=1}^{n}{\frac {f\left(x_{i-1}\right)+f\left(x_{i}\right)}{2}}\left(x_{i}-x_{i-1}\right)}$

A formula lényegesen jobban közelíti a területet, mint a téglalap-eljárás, és lényegesen nem számításigényesebb, ezért szívesebben használják.

Simpson-formula

Bővebben: Simpson-módszer

A Simpson-formula esetén nem töröttvonallal, hanem parabolákkal közelítjük a függvény ívét. Ezek, mint egyszerű görbék, jobban közelítik ugyanis a függvények ívét. A másodfokú függvény meghatározásához azonban három pont kell, ebből kettő triviálisan adott: az osztásköz alsó és felső végpontja. A harmadik pontnak a legcélszerűbb választás az osztásköz felezőpontja. Így a Simpson-formula a következő alakot ölti:

${\displaystyle M_{i}={\frac {x_{i+1}-x_{i}}{6}}\left(f\left(x_{i}\right)+4f\left({\frac {x_{i}+x_{i+1}}{2}}\right)+f\left(x_{i+1}\right)\right)}$

A függvény integrálját tehát a következő összeggel közelíthetjük:

${\displaystyle \int \limits _{a}^{b}f\approx \sum _{i=0}^{n}M_{i}=\sum _{i=0}^{n}{\frac {x_{i+1}-x_{i}}{6}}\left(f\left(x_{i}\right)+4f\left({\frac {x_{i}+x_{i+1}}{2}}\right)+f\left(x_{i+1}\right)\right)}$

Még jobb közelítés az ún. háromnyolcados formula,^[6] amihez azonban már négy pontot kell felvenni, ebből kettő a két végpont, a másik kettő pedig a két harmadolópont:

${\displaystyle \int \limits _{a}^{b}f\approx \sum _{i=0}^{n-1}{\frac {x_{i+1}-x_{i}}{8}}\left(f\left(x_{i}\right)+3f\left({\frac {2x_{i}+x_{i+1}}{3}}\right)+3f\left({\frac {x_{i}+2x_{i+1}}{3}}\right)+f\left(x_{i+1}\right)\right)}$

Az egyes módszerek összehasonlítása

Közelítsük a ${\displaystyle \int \limits _{2}^{5}2^{x}\mathrm {d} x}$ integrált!

Beosztás	Alsó téglalap	Felső téglalap	Trapéz	Simpson
5	32,5760332146733	49,3760332146733	40,9760332146733	40,395878605680075
10	36,34091725792838	44,74091725792839	40,540917257928385	40,39548733687002
100	39,97691674347999	40,81691674347999	40,39691674348	40,3954611475135
1000	40,35347570098068	40,437475700980634	40,39547570098072	40,395461144891236
5000	40,38706172713465	40,40386172713443	40,39546172713457	40,39546114489098

A pontos érték ${\displaystyle {\frac {28}{\log 2}}\approx 40,39546114489097540649}$, ezt szemmel láthatólag a Simpson-módszer a legerősebben, a téglalap módszer a legkevésbé közelíti meg.

Differenciálegyenletek megoldása

Bővebben: Differenciálegyenlet

A differenciálegyenletek megoldása során nem mindig van lehetőség a megoldás direkt megtalálására, ebben az esetben az itt ismertetett módszerek egy hatványsorozatok formájában közelítik a tényleges megoldást. Ezeknek a fő előnye, hogy nem csak akkor adnak közelítő megoldást, ha nincs ismert módszer a pontos megoldás meghatározására, hanem akkor is, ha a megoldás nem írható fel véges formában (zárt alakban).

Mindegyik módszer esetében egy konkrét függvényt, a differenciálegyenlet egy partikuláris megoldását kapjuk meg, mivel az alkalmazásuknak előfeltétele valamilyen peremfeltétel megadása. A megoldhatósággal ritkán szükséges foglalkozni, a gyakorlati problémák során előálló differenciálegyenletek az erre vonatkozó feltételeket ritkán nem teljesítik.

Mindegyik itt ismertetett módszer feltételezi, hogy a differenciálegyenlet felírható

${\displaystyle \mathrm {D} y=f\left(x,y\right)}$

formában. Ezekben az esetekben a megoldást a peremfeltétel és az ${\displaystyle f}$ függvény segítségével közelítjük.

Taylor-polinomok

Mivel a differenciálegyenletek az ismeretlen függvény deriváltjait tartalmazzák, az első kézenfekvő ötlet, hogy a Taylor-sorokat használjuk közelítésre. Annál is inkább, mert a peremérték-probléma esetén legalább egy pont adott. Ebből pedig az első deriváltat is meg tudjuk határozni ugyanitt a differenciálegyenletből:

${\displaystyle \mathrm {D} y\left(x_{0}\right)=f\left(x_{0},y\left(x_{0}\right)\right)}$

Ha a differenciálegyenletet deriváljuk, akkor a második deriváltat is megkapjuk:

${\displaystyle \mathrm {D} ^{2}y=\mathrm {D} f={\frac {\partial f}{\partial x}}+{\frac {\partial f}{\partial y}}\mathrm {D} y}$

amiben szerepel az ismeretlen függvény első deriváltja, aminek értékét már ismerjük. Ezekből a Taylor-polinom együtthatóit kapjuk meg sorban egymás után, ha a meglévő értékeket behelyettesítjük, azok ugyanis pont a deriváltak adott pontban felvett értékei.

A módszer előnye nyilvánvaló, mindössze egyetlen ismert függvényt kell tudnunk deriválni, és ennek a helyettesítési értékeit meghatározni, így kapunk egy közelítő hatványsort. A Taylor-sorokról pedig bizonyított, hogy előállítják a megfelelő függvényt, tehát az így kapott polinom egy jó közelítő függvény. Egyetlen hátulütője a módszernek, hogy ha a jobb oldalon olyan függvény áll, aminek a helyettesítési értéke (esetleg a deriváltjaié) csak közelítőleg számolható ki, akkor esetleg a kapott sor esetleg nem konvergál elégséges mértékben. Az ilyen és ehhez hasonló problémák vizsgálata is közrejátszott a dinamikus rendszerek és a káoszelmélet létrejöttében.

Picard-iteráció

Ha a differenciálegyenletet integráljuk, akkor a jobb oldalnak egy primitív függvényét kapjuk. Erre vonatkozólag ismert a következő összefüggés:

${\displaystyle F\left(x\right)-C=\int \limits _{C}^{x}f\mathrm {d} t}$

Ezt figyelembe véve egy közelítő megoldást kapunk úgy, hogy a peremfeltételt mint integrációs konstanst vesszük figyelembe, és így integrálunk:

${\displaystyle y_{\mathrm {app} }=y\left(x_{0}\right)+\int \limits _{x_{0}}^{x}f\left(t,y\left(x_{0}\right)\right)\mathrm {d} t}$

Ezt természetesen figyelembe vehetjük újra, mint a kezdetinél jobb közelítést, így iterációs módon közelíthetjük meg a differenciálegyenlet megoldását. Ha az ${\displaystyle f}$ függvény polinomiális, akkor a megoldást hatványsor formájában kapjuk meg. A Picard-iterációs közelítés alakja tehát:

${\displaystyle y_{0}\left(x_{0}\right)=p}$

${\displaystyle y_{n}=y_{0}\left(x_{0}\right)+\int \limits _{x_{0}}^{x}f\left(t,y_{n-1}\left(x_{0}\right)\right)\mathrm {d} t}$

Runge-Kutta-módszer

Bővebben: Runge–Kutta-módszer

A Picard-iteráció esetén a fő problémát az integrál kiszámítása jelenti, érthető módon ezt igyekszünk elkerülni, illetve erre is közelítő módszereket alkalmazni. Ezt elkerülendő Carl Runge dolgozott ki közelítést, majd ezt Martin Kutta javította meg. Használatához rögzítenünk kell egy ${\displaystyle h}$ lépésközt, ami egyben a közelítés hibahatárát is jelenti.^[7] A kezdetiérték-problémát felírva a módszer a következő formát ölti:

${\displaystyle y\left(x_{0}\right)=y_{0}}$

${\displaystyle x_{n}=x_{0}+nh}$

${\displaystyle y_{n+1}=y_{n}+{\frac {h\left(a_{n}+2b_{n}+2c_{n}+d_{n}\right)}{6}}}$

${\displaystyle a_{n}=f\left(x_{n},y_{n}\right)}$

${\displaystyle b_{n}=f\left(x_{n}+{\frac {1}{2}}h,y_{n}+{\frac {1}{2}}ha_{n}\right)}$

${\displaystyle c_{n}=f\left(x_{n}+{\frac {1}{2}}h,y_{n}+{\frac {1}{2}}hb_{n}\right)}$

${\displaystyle d_{n}=f\left(x_{n}+h,y_{n}+hc_{n}\right)}$

Érdekességek

Egyes esetekben egészen érdekes és meglepő módon is közelíthetjük a várt értékeket.

1. Biológiai gyökkeresés: Lényegében a genetikus algoritmusok egy kreatív alkalmazása, erre utal a neve is. Választunk egy kiindulási pontot, majd ebből néhány, kissé eltérő pontot generálunk véletlenszerűen, és ezek közül azt tartjuk meg, ami legközelebb van a gyökhöz. A közelítés sztochasztikusan fog konvergálni, ellenben bármilyen egyenlet(rendszer) esetén működik.
2. Vegyészintegrál: A vegyészek sok mérés eredményét papíron, diagramként kapják meg, amiknek kicsit nehéz az integrálját akár csak becsülni is. Ugyanakkor rendkívül pontos mérlegekkel is rendelkeznek, e kettőt elegyítik össze. A függvényt az adott intervallumban ábrázolják egy papíron, és az így kapott síkidomot kivágják, majd lemérik. Ezután kivágnak egy ismert területű síkidomot is ugyanabból a papírból, és azt is lemérik. A két tömeg hányadosa nagyjából megegyezik a területek hányadosával.
3. Monte Carlo integrálás: Egy adott, ${\displaystyle \left(x,y\right)}$ pontról könnyű eldönteni, hogy a függvény által meghatározott görbe felett vagy alatt van-e. Éppen ezért az integrálási intervallumon a függvényt egy téglalappal lefedjük. Ezután a téglalapban elkezdünk véletlenszerűen kijelölni pontokat. Annak valószínűsége, hogy egy pont a függvény görbéje alatt van, geometriai, azaz a függvény integrálja és a téglalap területének hányadosával egyenlő. Sok pont esetén a valószínűség jól becsülhető, a téglalap területe ismert, így az integrál is jól közelíthető.

Jegyzetek

1. A harmadfokú egyenletet megoldó Cardano-képletben köbgyök- és négyzetgyökvonás van, melyeket hasonló iterációval (Newton-módszerrel) számítunk ki, mint amivel az eredeti egyenletet oldjuk meg.
2. Egyszerű koordinátageometriai feladat.
3. Az ábrát a ${\displaystyle z^{3}-1=0}$ egyenlet megoldásainak közelítéséből állította elő a készítő.
4. Maga a módszer alkalmazható természetesen a lineáris egyenletrendszerekre is, azonban könnyen belátható, hogy ez egyenértékű az eredeti rendszerrel.
5. Az itt említett két kőözelítés mellett még egy harmadikat is szoktak használni, amikor a téglalap magasságát az intervallum közepén felvett függvényérték adja meg. Ezzel jobb becslést kaphatunk.
6. Kissé misztikusnak tűnhet, mivel a képletben nincsen 3 a számlálóban, azonban eredetileg, ha az osztópontok távolságát ${\displaystyle h}$-val jelöljük, akkor a harmadolópontok távolságával számolva az összeg szorzótényezője ${\displaystyle {\frac {3h}{8}}}$ lesz.
7. A módszert negyedrendű jelzővel szokták ellátni, kiemelve a Runge-Kotta-módszerek családjából, mivel ${\displaystyle h}$-ban negyedik rendben (azaz negyedik hatványkitevővel) közelíti a pontos megoldást.

Források

• A. F. Timan, Theory of approximation of functions of a real variable, 1963 ISBN 048667830X
• Bárczy Barnabás: Integrálszámítás, 2000, Műszaki Könyvkiadó, ISBN 963-16-3061-7
• Bronstein-Szemengyajev: Matematika kézikönyv, 2000, TypoTeX Kiadó, ISBN 963-9132-59-4
• C. Hastings, Jr. Approximations for Digital Computers, Princeton University Press, 1955.
• E. Remes [Remez], Sur le calcul effectif des polynomes d'approximation de Tschebyscheff 1934 C. R. Acad. Sci., Paris, 199, 337-340,
• Fritz Reinhardt, Heinrich Soeder: SH Atlasz – Matematika, 1993, Springer-Verlag, ISBN 963-7775-60-9
• J. F. Hart, E. W. Cheney, C. L. Lawson, H. J. Maehly, C. K. Mesztenyi, J. R. Rice, H. C. Thacher Jr., C. Witzgall, Computer Approximations, Wiley, 1968, Lib. Cong. 67-23326.
• K.-G. Steffens, The History of Approximation Theory: From Euler to Bernstein Birkhäuser, Boston 2006 ISBN 0817643532
• Kristóf János: Az analízis elemei, 1995, ELTE, egyetemi tankönyv
• L. Fox and I.B. Parker. "Chebyshev Polynomials in Numerical Analysis." Oxford University Press London, 1968.
• N. I. Achiezer (Akhiezer), Theory of approximation, Translated by Charles J. Hyman Frederick Ungar Publishing Co., New York 1956 x+307 pp.
• Rimán János: Matematikai analízis, 1998, EKTF Líceum Kiadó, ISBN 963 7752 55 2
• Scharnitzky Viktor: Differenciálegyenletek (Bolyai könyvek sorozat), 1975, Műszaki Könyvkiadó, ISBN 963-10-0527-5
• Stoyan Gisbert, Takó Galina: Numerikus módszerek I-II, 1993, ELTE-TypoTeX, egyetemi tankönyv
• T. Erdélyi, "Extensions of the Bloch-Pólya theorem on the number of distinct realzeros of polynomials", Journal de th ́eorie des nombres de Bordeaux 20 (2008), 281–287.
• T. Erdélyi, "The Remez inequality for linear combinations of shifted Gaussians", Math. Proc. Cambridge Phil. Soc. 146 (2009), 523–530.
• W. J. Cody Jr., W. Waite, Software Manual for the Elementary Functions, Prentice-Hall, 1980, ISBN 0-13-822064-6.

Kapcsolódó szócikkek

• Differenciálegyenlet
• Egyenlet
• Egyenletrendszer
• Függvények
• Integrál
• Konvergencia

Fordítás

• Ez a szócikk részben vagy egészben az Approximation theory című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Külső hivatkozások

• History of Approximation Theory (HAT) Archiválva 2019. szeptember 18-i dátummal a Wayback Machine-ben
• Surveys in Approximation Theory (SAT) Archiválva 2019. szeptember 18-i dátummal a Wayback Machine-ben

• Matematikaportál • összefoglaló, színes tartalomajánló lap