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:

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. 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. 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ó

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ó

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ő:

.

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

Sőt, ennél még több is mondható: ha találunk olyan 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 .

Megint figyelembe kell venni a páros fokszámú polinomokat – elég az 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 polinom esetén az 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.

Ha függvény, akkor ezt felfoghatjuk úgy, hogy 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 projektív tér pontjaiként adja a gyököket, így azok között nem tesz különbséget.

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.

Ha alkalmasan választunk az 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,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. ezért legfeljebb másodfokú egyenletek esetén alkalmazunk megoldóképletet.

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

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 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: . Itt az 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 é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 és értékeket. Ekkor a függvényt egy egyenessel tudjuk helyettesíteni, melynek két pontja: és , amikre fel tudjuk írni az egyenest: .Egyszerű koordinátageometriai feladat. Ennek az egyenesnek keressük az x tengellyel való metszéspontját, azaz az esetben az egyenlet megoldását. Ez

Attól függően, hogy 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 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 egyenlet megoldásait! Egyszerű számítással kideríthető, hogy egy gyök a intervallumban található. Innen a közelítés lépései:

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