Numerikus analízis

Országok listájaHungaryNyíregyházi FőiskolaTermészettudományi Főiskolai KarProgramozó matematikusZáróvizsgaNumerikus analízis

04 Numerikus analízis
(KülönbözQ módszerek egyenlet közelítQ megoldására. Interpolációk. Legkisebb négyzetek módszere. Numerikus integrálási eljárások. Függvényközelítések.)

A numerikus analízis olyan HYPERLINK "http://hu.wikipedia.org/wiki/Algoritmus" \o "Algoritmus" algoritmusokkal foglalkozik, melyek folytonos (tehát nem diszkrét) matematikai feladatokat oldanak meg. A számítógépek elterjedése elQtt a numerikus számításokat kézzel végezték, a HYPERLINK "http://hu.wikipedia.org/wiki/Huszadik_sz%C3%A1zad" \o "Huszadik század" huszadik század közepétQl azonban fokozatosan számítógépek váltották fel ezt a módszert.
KözelítQ módszerek egyenlet közelítQ megoldására
Adott az f(x) = 0 meoldásra váró egyenlet. Amennyiben az f függvény egyetlen független változóval rendelkezik, az egyenlet egy dimenziós, és a feladat megkeresni az egyenlet gyökeit. Egy gyök létezése nem jelenti, hogy analitikus módon (képlettel) megoldható. Analitikus módszer esetén a legtöbb esetben megtalálható a pontos gyök. Ilyenkor numerikus módszerhez folyamodunk, és egy megközelítQ gyököt keresünk.
Intervallum-felezés
Legyen f(x) az a függvény, amelynek a gyökét szeretnénk meghatározni. Legyen (a,b) intervallumban folytonos, és a két végpontban a függvényértékek ellentétes elQjelqek. Ekkor az f(x) függvény az y=0 egyenest legalább egyszer, de az biztos, hogy páratlan sokszor metszi.
A keresés során az [a,b] intervallumot fogjuk szqkíteni úgy, hogy a két végpontot közelítjük egymáshoz.
Legyen  QUOTE  az intervallum felezQpontja. Ebben a pontban megnézzük a függvény értékét, és ha ez 0, akkor megállunk. Ha nem, akkor azt kell megvizsgálnunk, hogy f(c) elQjele f(a) vagy f(b) elQjelével egyezik-e meg. Amelyikkel megegyezik, azt cseréljük le c-re, és folytatjuk amíg f(c)=0 lesz.
Valójában azt vizsgáljuk, hogy f(c) abszolútértéke kisebb-e mint egy nagyon kicsi, nullához közeli szám (µ). Erre azért van szükség, mert lebegQpontos számábrázolás esetén két számról nem feltétlenül lehet megállapítani, hogy egyenlQek-e vagy sem.

Húrmódszer
A keresési elv hasonló az intervalumfelezéshez. Az eltérés az új, szqkebb intervallum meghatározásásnak elvében lesz.
Legyen f(x) az a függvény, amelynek a gyökét szeretnénk meghatározni. Legyen (a,b) intervallumban folytonos, és a két végpontban a függvényértékek ellentétes elQjelqek. Kössük össze egy egyenesel a végpontokhoz tartozó függvényértékeket, ez lesz a húr. Legyen c aza pont ahol a húr az x tengelyt metszi. Számítsuk ki a függvény értékét ebben a pontban. Az új keresési intervallumot ezután az f(c) érték elQjelének függvényében kapjuk meg. Természetesen a ciklus itt is addig fut amíg f(c) érték nullává nem válik (Azaz f(c)<µ).

Newton  módszer (ÉrintQmódszer)
Ez, a felezQ módszernél gyorsabban konvergáló módszer, szükségessé teszi a tanulmányozott függvény deriváltjának, f (x) ismeretét. Ugyanakkor egyetlen x0 pontból indulunk ki. Az x1 pontot úgy határozzuk meg, hogy az x0 pontban a függvényhez húzott érintQt meghosszabbítjuk, amíg az az x tengelyt metszi. Az x1 metszépont már közelebb fekszik a gyökhöz mint az x0. Az x1 értékét felhasználva az elQbbiekhez hasonlóan járunk el újabb és újabb a gyökhöz egyre közelebb esQ x2, x3, & xn pontokat kapva. A Newton módszer legnagyobb hátránya más módszerekkel szemben, hogy szükségessé teszi a függvény deriváltjának az ismeretét, ami a legtöbb gyakorlati alkalmazás esetén nem áll rendelkezésre. [numerikus1.pdf]

Megjegyzés:
Az ún. módosított Newton módszer kevésbé munkaigényes, igaz kevésbé hatásos is: itt a függvény görbéjét az (xn, F(xn)) ponton áthaladó F (x0) iránytangensq egyenessel helyettesítjük:
xn+1 = xn  F(xn)/F (x0) (n = 0, 1, 2, & )
Interpolációk
Az y=f(x) függvény értékkészlete legyen ismert az x0, x1, & , xn pontsorozaton, azaz y0=f(x0), y1=f(x1), & , yn=f(xn). Az x0, x1, & , xn pontsorozatot a továbbiakban interpolációs alappontoknak nevezzük.
Az interpoláció célja, hogy olyan függvényt határozzunk meg, amely az [x0; xn] intervallumban közelítQleg megadja az alappontoktól eltérQ helyeken is a függvényértékeket.
Az eljárás lényege az, hogy az f(x) függvényt olyan F(x) függvénnyel közelítjük, amely az (xi;yi) (i=0,1, & , n) pontokban, az ún. kollokációs pontokban megegyezik f(x)-szel, azaz F(xi)=f(xi)  QUOTE  yi (i=0,1, & , n).
Az F(x) függvény elQállítására szolgáló eljárást interpolációnak, az F(x) függvényt pedig interpolációs függvénynek nevezzük.
Interpolációról beszélünk, ha az x melyben az F(x) értéket kívánjuk megbecsülni a megadott pontok által meghatározott intervallumon belül helyezkedik el, azaz x  QUOTE  (x1, xn).
Extrapolációval van dolgunk, ha az f(x) függvényt az intervallum határain túl próbáljuk megközelíteni.
Az interplációs módszereket több szempont szerint is osztályozhatjuk. Ha a keresett függvény megközelítésénél használt függvények típusát tekintjük, megkülönböztethetjük a következQ interpolációs módszereket:
Polinomiális: a megközelítQ függvények polinomok. Ez a módszer messze a legelterjedtebb.
Trigonometrikus: a szinuszos és koszinuszos függvények seg\ ^ b † ” –

<
>
Š
Œ
0

2

P

R

ã î :bâä,.\^lnprtvF ˆŠ¨ªVXšüõüîüæâæîæüæâæîæüÚüÚüÔÐÉÐÉо·ª·¾ÐŒ…ŒÐŒ…Œ

hyx°h¾
h¾
jhôIþhôIþU†*j²hôIþhôIþEHïÿUjhôIþhôIþEHïÿU

hôIþhôIþjhôIþhôIþU

hyx°h Ih I
hyx°PJh4whyx°6hq4jhq4U

h4whyx°

hyx°hwhyx°*,\ ^ æ

H
:b~Nªšž¶¢ÂƎ"’"l$õððèãèÞèèèèÒÞèèÒÍż³
ÆØ
gdS5„Ä^„ÄgdS5 $a$gdS5gdS5
$„Ä`„Äa$gdS5gdyx°gdyx° $a$gdyx°gdyx° $¤a$gdyx° šœž¶ ¢ÂÄÆêö8:@Bnp€‚º¼--p-r-Ú-Ü-è-ê-¶ ¸ ¾ À Ê Ì j"Œ"Ž""’"¶"¸"çÝ×ÓÏÓ϶ݰ©Ï°¢š¢Ï¢š¢Ï¢š¢Ï¢š¢š¢š¢š¢š¢š¢Ï¢wpw

hyx°hS5hS5CJOJQJ0j¹ÈhôIþhôIþCJOJQJUmHnHtH uh»hS5H*

hž hS5

haUÀhS5
hS5PJ0jtähôIþhôIþCJOJQJUmHnHtH uhS5h¾

hyx°PJhyx°CJOJQJ0jd!hôIþhôIþCJOJQJUmHnHtH u,¸"ê"ì"„#†##’#À#Â#$ $($*$6$8$D$F$l$†$ˆ$Ž$’$š$œ$ì$î$ð$ö$ø$%%2%4%<%>%F%H%P%R%f%h%p%r%~%€%‚%ˆ%Š%–%˜%œ%Ô%

&®&°&õëäÜäÜäÜäÜäÜäÜäÜäØÔÌÁ·Á̬Ÿ¬Ÿ¬ŸÌ•Ì•Ì•Ì•Ì•Ì•Ì¬Ÿ¬Ÿ¬Ÿ¬ÌÁ̋hXW`6B*phhXW`B*H*phh˜
hXW`B*H*phh˜
hXW`B*phhXW`B*]phhXW`6B*]phhXW`B*phhyx°hCOËh»hS5H*

hyx°hS5hS5CJOJQJ hyx°hS50JPJ6l$ˆ$ &v'6)*Ò*9+Ø,Š-=˜>A

CÒD

EHÎH IÆMÈMêMNQúèààààØØÍÍÍÅÅÅÀÅÅÀÅÅÅÅgd}sÖ $a$gd[3¨
$
&
Fa$gdöWN $a$gdöWN $a$gdw$-D7$MÆ
ÿÿÿÿa$gdwgdCOË°&²&¸&º&´'¾'((*(.(0(4(6(T(V(z(¦(Ú(Ü(à(â(ä(ì(î(ð(ô(ö()))
)

) ))) )˜)º)ê)***7*;*ôêôâ×âÏâÅâÅâÏâ×âÏâêôâêô⵪ªµâêôâ×â×â{pâhXW`hXW`B*phhCOË!jhôIþhôIþB*Uph†*jNhôIþhôIþEH÷ÿUjshôIþhôIþEH÷ÿUhôIþhôIþB*phjhôIþhôIþB*UphhXW`B*H*phhwB*phhXW`6B*]phhXW`B*phhXW`6B*phhXW`6B*H*ph*;*º*»*Â*Ã*Ä*Å*Æ*Ç*Ê*Ë*Î*Ï*Ñ*Ò*û*ü*2+8+9+,Ö,Ø,-ˆ-Š-þ-< ==\=–>˜>ª?¬?°?÷çÜÏÜç±÷¤÷¤÷™Ž†Ž÷{w†ow†hwf†hw†hbZbh[3¨h[3¨H*h[3¨U

höWNhöWNh%3-B*phhöWNhðŸhyx°B*phhöWNB*phhðŸhðŸB*phhXW`hyx°B*phhðŸhðŸB*H*ph!jhôIþhôIþB*Uph†*j@-hôIþhôIþEH÷ÿUj)-hôIþhôIþEH÷ÿUhôIþhôIþB*phjhôIþhôIþB*UphhðŸB*ph#ítségével is interpolálhatunk. FQleg interpolációval egybekötött Fourier módszerek alkalmazásának szükségessége esetén válik hasznossá.
Racionális: egyes függvények nem közelíthetQk jól meg polinomokkal, viszont sikeresen használhatjuk a racionális függvények bQvebb osztályát. Racionális függvény alatt két polinom arányát értjük.
A polinom interpoláció a lineáris interpoláció egy általános fajtája. Egy y=p(x) polinom meghatározását jelenti, mely keresztül megy a (x1,y1), (x2,y2),& ,(xn,yn) pontokon. Tehát adott n db pont ahol az egyes xi értékek mind különbözQk, minden p(xi)=yi, (i eleme 0..n) és a polinom fokszáma legfeljebb n-1 lesz.
A Lagrange polinomoknál minden alappontban egy mérési eredményünk van (ami lehet valódi mérés eredménye, de lehet kiszámított függvényérték is) és megköveteljük azt, hogy a függvényt közelítQ polinom a megadott alappontban a megadott értéket vegye fel.
A Taylor polinomok esetében egy pontban a deriváltak értékét adjuk meg (illetve mérjük, ha ilyen mérést meg tudunk valósítani) és olyan polinomot konstruálunk, amelynek deriváltjai az adott pontban a megadott derivált értékek.
Legkisebb négyzetek módszere
Adott egy adatpontokból álló halmaz, amelyek mérési értékeket tartalmaznak. Ezekhez a pontokhoz kell egy paraméterekkel felírható görbét illeszteni, olymódon, hogy a valós és becsült értékek közti eltérés a lehetQ legkisebb legyen. A görbe paramétereinek meghatározása numerikus módszerrel történik, úgy hogy a görbe és az adatpontok távolsága (az eltérések négyzete) minimális legyen.
 HYPERLINK "http://upload.wikimedia.org/wikipedia/commons/9/94/Linear_least_squares2.png" 
Numerikus integrálási eljárások
Az automatizált számítástechnika megjelentével a numerikus integrálás (kvadratúrák) is egy módszerré váltak a többi numerikus módszer között. Alapjában véve a numerikus integrálás az I =  QUOTE  típusú kifejezés kiértékelése, melyben az f(x) függvény és az integrálási határok adottak. Ideális esetben az integrál felírható mint I = F(a)  F(b), ahol F(x) az f(x) primitívje. Ha ezt megtehetjük, akkor a feladat már nem is numerikus, de mivel a gyakorlati esetek döntQ többségében az említett primitív függvény analitikus formában nem írható fel, csak numerikusan tudjuk megközelíteni a feladatot.

Téglalap módszer
A függvénygörbe alatti területet kis téglalapokkal közelítjük. Az intervallumot, melyen a területet számítjuk, felosztjuk sok kisebb intervallumra, és ezeken az intervallumokon vesszük a közelítQ téglalapokat. Ennek során a téglalapok magasságát az intervallumok bal oldali végpontjai határozzák meg. Minél kisebbek az intervallumok, annál pontosabban közelvtjük a görbe alatti területet a közelítQ téglalapok területének összegével.
Legyen n az intervallumok száma az integrálási tartoményban, a és b az integrálási tartomány két végpontja. Így egy kis intervallum hossza:  QUOTE  , a közelítQ összeg pedig:

Ahol xi az aktuális intervallum bal oldali végpontja, f(xi) pedig az itt vett fügvényérték.

Trapéz módszer
Ez jobb közelítést ad az elQzQnél, mivel a kis intervallumokon a függvényt nem téglalappal, hanem a görbéhez jobban simuló trapézzal közelíti. Figyelembe vesszük az intervallumok jobb és bal oldali végpontjait is: az ezen pontokhoz tartozó értékeket egyenes szakasszal kötjük össze, és így közelítjük a köztes területet.
Legyen n az intervallumok száma az integrálási tartoményban, a és b az integrálási tartomány két végpontja. Így egy kis intervallum hossza:  QUOTE  , az i-edik intervallumban lévQ trapéz területe:

A közelítQ összeg pedig ezen ti-k összege:

Függvényközelítések
Azzal a kérdéssel foglalkozik, hogy a diszkrét pontokban adott függvényekhez hogyan lehet jól kezelhetQ, az adott pontokra minél jobban illeszkedQ függvényeket konstruálni.
A legkönnyebben kezelhetQ és a legkedvezQbb analitikus tulajdonságokat követQ függvények a véges fokszámú polinomok, így a gyakorlati esetek nagy részében polinom közelítésekkel dolgozunk. Az adott pontokra való jó illeszkedésük szempontjából a polinomokkal való közelítések két típusát különböztetjük meg:
Interpoláció
A legkisebb négyzetek módszere
Az interpolációs polinomok az alappontokban ugyanazokat az értékeket veszik fel, mint az adott függvény, a legkisebb négyzetek és a Csebisev-féle közelítés módszerével nyert polinomok az alappontokban az adott függvényértékeknek csak közelítését adják.









 PAGE \* MERGEFORMAT 1

Hasonló témájú dokumentumok

Hozzászólások

03.04/1 1. félév 15 16 2. előadás 2009. május 21. algoritmusok anyagszerk ásványtan bce biotermékek elektro élet épszerk v eupol felvilágosodás filmtörténet fogyasztás föld gábor géptan görögország gyakorlat gyökerek hallás hálótervezés házi dolgozat humán intézményi gyakorlat jogi alapismeretek kérdések és válaszok kiadott kiállítás kollokvium kosztolányi mechanika mechanikai példatár motiváció órai dia pedagógia példák petőfi pr prácser tamás szerves tanenbaum természetföldrajz török vizsga vizsgatételek