Matematika | Analízis » Numerikus alkalmazások

Numerikus alkalmazások Pécs 2003.0515 . Typeset by AMS-TEX – 0– 1 1.Iterációs eljárások 1. ITERÁCIÓS ELJÁRÁSOK 1.1 Metrikus terek Ebben a jegyzetben N := {0, 1, 2, . } a természetes számok halmazát, Z := {n, −n : n ∈ N} az egész számok halmazát jelöli. K-val fogjuk jelölni a valós vagy a komplex számok halmazát, azaz K := R ill. K := C A K halmaz elemeit számoknak, K-beli elemeket felvevő függvényeket számértékű függvényeknek vagy funkcionáloknak nevezzük. Legyen X egy nem üres halmaz és ρ : X × X [0, ∞) egy leképezés. Az (X, ρ) párt metrikus térnek nevezzük, ha az alábbi feltételek teljesülnek: i) ρ(x, y) = 0 (1.1) ⇔ x=y ii) ρ(x, y) = ρ(y, x) (x, y ∈ X), (x, y ∈ X), iii) ρ(x, y)
ρ(x, z) + ρ(y, z) (x, y, z ∈ X). A ρ leképezést metrikának nevezzük. Az ii) tulajdonság alapján azt mondjuk, hogy a metrika szimmetrikus. A iii) feltételt,

utalva annak geometriai tartalmára, háromszög-egyenlőtlenségnek nevezzük. Az X halmaz elemeit pontoknak is szokás nevezni. Az (1.1) iii) alapján egyszerűen adódik a háromszög egyenlőtlenség (1.1) iv) |ρ(x, y) − ρ(x, z)|
ρ(y, z) (x, y, z ∈ X) változata. Nyilvánvaló, hogy bármely Y ⊆ X részhalmaz esetén ρ-nak az Y × Y halmazra vonatkozó leszűkı́tése metrika, és Y ezzel a metrikával metrikus tér. A szóban forgó leszűkı́tést, ha az nem okoz félreértést, szintén a ρ szimbólummal jelöljük. Ezt az (Y, ρ) metrikus teret az (X, ρ) alterének nevezzük. Tetszőleges a ∈ X pontra és r > 0 valós számra a Kr (a) := {x ∈ X | ρ(a, x) < r} , Kr (a) := {x ∈ X | ρ(a, x)
r} halmazokat rendre a középpontú, r sugarú nyı́lt, ill. zárt gömbnek nevezzük Nyı́lt gömb helyett gyakran csak gömböt fogunk ı́rni. 2 1.1 Metrikus terek Valamely H ⊆ X halmaz

komplementerét, azaz az X H halmazt H c -vel, az üres halmazt az ∅ szimbólummal jelöljük. Akkor mondjuk, hogy a G ⊆ X halmaz nyı́lt, ha minden a ∈ G ponthoz létezik olyan r > 0 szám, hogy Kr (a) ⊆ G. Könnyen igazolható, hogy a gömbök nyı́lt halmazok (lásd a 1. feladatot) Nyı́lt halmazok komplementereit zárt halmazoknak nevezzük. Egyszerűen megmutatható, hogy a zárt gömbök zárt halmazt alkotnak (lásd az 1 feladatot) Legyen (xn , n ∈ N) egy X-beli elemekből álló sorozat. Akkor mondjuk, hogy ez a sorozat konvergens, ha létezik olyan a ∈ X pont, hogy (1.2) lim ρ(xn , a) = 0. n∞ A háromszög-egyenlőtlenségből következik, hogy legfeljebb egy olyan a ∈ X létezik, amelyre az (1.2) feltétel teljesül Ezt az a pontot az (xn , n ∈ N) pontsorozat határpontjának, vagy limeszének nevezzük, és ezt az alábbi szimbólumok valamelyikével jelöljük: a = lim xn , xn a (n ∞). n∞ A ρ

metrika folytonos a következő értelemben: Legyen xn , yn ∈ X (n ∈ N) és a, b ∈ X. Ekkor (1.3) lim xn = a, lim yn = b n∞ n∞ ⇒ lim ρ(xn , yn ) = ρ(a, b). n∞ Valóban, (1.1) iv) alapján |ρ(xn , yn ) − ρ(a, b)|
|ρ(xn , yn ) − ρ(a, yn )| + |ρ(a, yn ) − ρ(a, b)|

ρ(xn , a) + ρ(yn , b) 0 (n ∞). Könnyen igazolható, hogy valamely H ⊆ X halmaz akkor és csak akkor zárt, ha bármely H-beli pontokból álló konvergens pontsorozat limesze is H-hoz tartozik. A háromszög-egyenlőtlenség egyszerű következménye, hogy minden X-beli elemekből álló (xn , n ∈ N) konvergens sorozatra fennáll a következő állı́tás: (1.4) ∀ > 0 ∃N ∈ N ∀m, n > N : ρ(xn , xm ) < . Az olyan sorozatot, amelyekre az (1.4) állı́tás teljesül, szabályos sorozatnak vagy Cauchy-sorozatnak nevezzük. Az előző megjegyzés szerint tehát minden konvergens sorozat Cauchy-sorozat, de léteznek

olyan metrikus terek és bennük Cauchy-sorozatok, amelyek nem konvergensek. Például a racionális számok Q halmazán bevezetve a ρ(x, y) := |x − y| (x, y ∈ Q) metrikát nem teljes metrikus teret kapunk. Ha valamely metrikus térben minden Cauchy-sorozat konvergens, akkor a teret teljesnek nevezzük. Fel fogjuk használni azt a jól ismert tényt, hogy a Kn halmazon a ρ(x, y) := (|x1 − y1 |2 + · · · + |xn − yn |2 )1/2 (x = (x1 , . , xn ), y = (y1 , , yn ) ∈ Kn ) 3 1.Iterációs eljárások leképezés metrika és ez a tér teljes. Nyilvánvaló továbbá, hogy teljes metrikus terek zárt alterei teljesek. Metrikus terek teljessége ekvivalens a következő geometriai tulajdonsággal: Egy metrikus tér akkor és csak akkor teljes, ha minden olyan zárt gömbökből álló Hn := Krn (an ) (n ∈ N) sorozatra,
∞ amelyre Hn+1 ⊆ Hn és limn∞ rn = 0 a gömbök közös része nem üres: n=0 Hn = ∅. Legyen νn

∈ N (n ∈ N) egy természetes számokból álló, szigorúan növekedő számsorozat, más szóval tegyük fel, hogy ν0 < ν1 < ν2 < · · · , tekintsünk továbbá egy xn ∈ X (n ∈ N) pontsorozat. Ekkor az xνn (n ∈ N) pontsorozatot az xn (n ∈ N) sorozat részsorozatának nevezzük. Nyilvánvaló, hogy a konvergens pontsorozatok minden részsorozata is konvergens és a részsorozatok határértéke egyenlő az eredeti sorozat határértékével. Akkor mondjuk, hogy a H ⊆ X halmaz korlátos, ha létezik olyan Kr (a) környezet, amely a H halmazt tartalmazza. Bebizonnyı́tható, hogy ha H ⊂ Kn korlátos és zárt halmaz, akkor bármely H elemeiből képzett pontsorozatnak van olyan konvergens részsorozata, amelynek a határértéke is H-hoz tartozik. Ez a tulajdonság szolgál alapul a kompakt halmaz fogalmának értelmezéséhez. Definı́ció. Akkor mondjuk, hogy a K ⊆ X halmazt kom- pakt, ha minden xn

∈ K (n ∈ N) sorozatnak van olyan xνn (n ∈ N) konvergens részsorozata, amelynek határértékére limn∞ xνn ∈ K teljesül. Bebizonyı́tható, hogy Kn térben a kompakt halmazok osztálya egybeeseik a korlátos és zárt halmazok osztályával. Ez az állı́tás nem érvényes minden metrikus térre Nevezetesen megmutatható, hogy minden metrikus térben a kompakt halmazok egyúttal zártak is, van azonban olyan metrikus tér és benne olyan zárt halmaz, amely nem kompakt. Metrikus terek közötti leképezések körében bevezethető a folytonosság fogalma. Legyen (X, ρ) és (Y, σ) két metrikus tér, H az X egy nem üres részhalmaza és f : H Y egy H-n értelmezett függvény. Definı́ció. Akkor mondjuk, hogy az f függvény az a ∈ H pontban folytonos, ha minden xn ∈ H (n ∈ N) H-beli ahoz konvergáló pontsorozat f (xn ) ∈ Y (n ∈ N) képsorozata f (a)-hoz konvegál: xn ∈ H (n ∈ N), lim ρ(xn , a) =

0 ⇒ n∞ lim σ(f (xn ), f (a)) = 0. n∞ Bebizonyı́tható, hogy ha K ⊆ X kompakt halmaz és f : K Y folytonos 4 1.2 Normált és euklideszi terek függvény, akkor a K halmaz f által létesı́tett f (K) := {f (x) : x ∈ K} ⊆ Y képe kompakt. Ennek egyszerű következénye az alábbi állı́tás: Weierstrass-tétel. Kompakt halmazon értelmezett valós függvény értékészletének van legkisebb és legnagyobb eleme. Feladatok 1. Igazoljuk, hogy a Kr (a) gömbök nyı́ltak, a Kr (a) halmazok zártak 2. Legyen X teltszőleges, végtelen elemet tartalmazó halmaz 2.1 Igazoljuk, hogy a  1, ha x = y (x, y ∈ X) ρ(x, y) := 0, ha x = y (x, y ∈ X) utası́tással értelmezett függvény metrika az X téren. 2.2 Mutassuk meg, hogy az xn ∈ X (n ∈ N) sorozat akkor és csak akkor konvergens, ha stacionárius, azaz ∃N ∈ N ∀n ≥ N : xn = xN . 2.3 Igazoljuk, hogy az (X, ρ) tér teljes 2.4 Mutassuk meg, hogy az X

halmaz korlátos és zárt de nem kompakt 3. Mutassuk meg, hogy bármely metrikára |ρ(x, z) − ρ(y, z)|
ρ(x, y) (x, y, z ∈ X). 4. Legyenek (Xi , ρi ) (i = 1, 2, , n) metrikus terek és jelölje X ezek Descartes-féle szorzatát. Igazoljuk, hogy az ρ1 (x, y) := ρ1 (x1 , y1 ) + · · · + ρn (xn , yn ) ρ∞ (x, y) := max ρi (xi , yi ) 1
i
n utası́tásokkal két metrikát értelmeztünk az X téren és a szorzattér mindkét metrikára nézve teljes, feltéve, hogy a kiindulásul tekintett terek teljesek. 5 1.Iterációs eljárások 1.2 Normált és euklideszi terek A metrikus terek legfontosabb osztályát a normált terek alkotják. Ezekben a metrikák egy normából származtathatók. Legyen most X egy lineáris tér a K számtestre vonatkozóan, és jelölje θ az X tér nullelemét Az X téren értelmezett X x x ∈ [0, ∞) függvényt normának nevezzük, ha i) x = 0 ⇔ ii) λx = |λ|x

(2.1) (x ∈ X), x=θ (λ ∈ K, x ∈ X), iii) x + y
x + y (x, y ∈ X). Nyilvánvaló, hogy a ρ(x, y) := x − y (x, y ∈ X) (2.2) utası́tással egy metrikát értelmeztünk, amelyet a  ·  norma által indukált metrikának nevezzük. (Lásd az 1 feladatot) Ez a metrika az eltolással szemben invariáns a következő értelemben: (x, y, z ∈ X). ρ(x + z, y + z) = ρ(x, y) Az (X,  · ) párost, ahol X egy lineáris tér és  ·  egy norma X-en, normált térnek nevezzük. Ha ez a tér a norma által indukált metrikára nézve teljes, akkor Banachtérnek nevezzük Az X0 ⊆ X halmazt lineáris altérnek nevezzük, ha x, y ∈ X0 , λ ∈ K ⇒ x + y, λx ∈ X0 . Nyilvánvaló, hogy X0 az eredeti  ·  normával maga is egy lineáris normált tér. Ha X0 az X-nek egy zárt részhalmaza és X teljes, akkor (X0 ,  · ) is teljes. (Lásd a 2 feladatot.) Skaláris szorzattal ellátott lineáris teret

euklideszi térnek nevezzük. Emlékeztetünk arra, hogy az X×X halmaznak egy (x, y) x, y ∈ K leképezését skaláris szorzatnak nevezzük, ha bármely x, x1 , x2 , y ∈ X, λ ∈ K esetén i) (2.3) x, x ≥ 0 , x, x = 0 ⇔ x = θ, ii) x1 + x2 , y = x1 , y + x2 , y , λx, y = λx, y, iii) x, y = y, x. Vezessük be az (2.4) x :=  x, x (x ∈ X) 6 1.3 Fixpont tétel leképezést. Nyilvánvaló, hogy az itt definiált függvény rendelkezik a (21)i) és (21)ii) tulajdonságokkal. Megmutatható, hogy a (23)iii) egyenlőtlenség is fennáll, következésképpen a (28) leképezés valóban norma Ezt a normát a skaláris szorzat által indukált normának nevezzük. Bebizonyı́tható, hogy minden x, y ∈ X elempárra (2.5) i) ii) |x, y|
x y x + y
x + y Az (X, ·, ·) párt, ahol X lineáris tér és ·, · egy skaláris szorzat ezen a téren, euklideszi térnek

nevezük. Ha ez a tér a skaláris szorzat által indukált metrikára nézve teljes, akkor Hilbert-térnek nevezzük. Feladatok 1. Legyen (X,  · ) lineáris normált tér Igazoljuk, hogy ρ(x, y) := x − y (x, y ∈ X) metrika az X téren. 2. Legyen (X,  · ) Banach-tér és X0 ⊆ X zárt, lineáris altér Igazoljuk, hogy ekkor (X0 ,  · ) is Banach-tér. 3. Legyen X = K, ahol K = R vagy K = C Igazoljuk, hogy K lineáris tér önmagára vonatkozóan és az abszolut érték leképezés egy norma ezen a téren. Mutassuk meg, hogy ez a metrikus tér teljes. 5. Mutassuk meg, hogy Kn tér az x, y := x1 y 1 + · · · + xn y n (x = (x1 , · · · , xn ), y = (y1 , · · · , yn ) ∈ Kn ) skaláris szorzattal Hilbert-tér. 1.3 Fixpont-tétel Ebben a pontban egy iterációs eljárást ismertetünk, amely számos numerikus eljárás alapját képezi és különböző tı́pusú egyenletek megoldására is

felhasználható. Bevezető példaként oldjuk meg az (3.1) x = cos x 7 1.Iterációs eljárások egyenletet. Kiindulva az x0 = 0 számból rekurzióval értelmezzük az xn+1 := cos xn (n ∈ N) (3.2) sorozatot. Könnyen belátható (lásd az 1 feladatot), hogy az (xn , n ∈ N) sorozat konvergens és x-szel jelölve határértékét (3.2) alapján határátmenettel (31) adódik Ezt az egyszerű eljárást nemcsak egyenletek, hanem egyenletrendszerek, differenciálés integrálegyenletek megoldására is felhasználhatjuk. Ilyen egyenletekre alkalmazható eljárás megfogalmazásához induljunk ki egy (X, ρ) metrikus térből és egy f : X X leképezésből. Az (31) egyenletben azt az x számot keressük, amelyet a cos függvény önmagába viszi át. Ezzel kapcsolatban bevezetjük az alábbi fogalmat Definı́ció. Az x∗ ∈ X pontot az f : X X leképezés fixpontjának nevezzük, ha f (x∗ ) = x∗ .

(3.3) Nem minden leképezésnek van fixpontja. Van azonban a függvényeknek egy tág osztálya, amelyeknek igen általános feltételek mellett létezik fixpontja Ezzel függ össze az alábbi Definı́ció. Akkor mondjuk, hogy az f : X X leképezés kontrakció, ha létezik olyan 0
η < 1 szám, amellyel minden x, y ∈ X pontpárra fennáll a ρ(f (x), f (y))
ηρ(x, y) (3.4) egyenlőtlenség. Teljes metrikus téren értelmezett kontrakcióknak mindig létezik fixpontja, érvényes ui. a következő állı́tás Fixpont-tétel. Legyen (X, ρ) teljes metrikus tér Ekkor minden f : X X kontrakciónak pontosan egy x∗ fixpontja van. Az x∗ fixpont az (3.5) x0 ∈ X, xn+1 := f (xn ) (n ∈ N) rekurzióval értelmezett pontsorozat határértéke. A konvergencia sebességére érvényes a (3.6) becslés. ρ(xn , x∗ )
ρ(x0 , x1 ) ηn (n ∈ N) 1−η 8 1.4 Newton módszer Gyakran előfordul, hogy egy

leképezés az X térnek csak egy részén, mondjuk az X0 := Kr (x0 ) halmazon kontrakció. Ilyenkor használható a fixpont-tétel következő, módosı́tott, lokális változata. Lokális fixpont tétel. Ha az f : X X leképezés kontrakció a Kr (x0 ) halmazon és ρ(x0 , x1 )
(1 − η)r, (3.7) akkor az (3.5) pontsorozat konvergál az f fixpontjához Megjegyezzük, hogy az (3.9) feltétel minden olyan x0 pontban teljesül, amely elég közel van a fixponthoz. Valóban a metrika és az f függvény folytonossága alapján ρ(x0 , x1 ) = ρ(x0 , f (x0 )) 0, ha x0 x∗ . Feladatok 1. Legyen X := R, ρ(x, y) := |x − y| (x, y ∈ X), f (x) := cos x (n ∈ R) Felhasználva a Lagrange-féle középérték tételt igazoljuk, hogy az f függvény 0 < a < π/2 esetén kontrakció a [−a, a] intervallumon az η := sin a kontrakciós állandóval. Mutassuk meg, hogy x0 = 0.75, r = 03 esetén teljesülnek a lokális

fixpont-tétel feltételei, következésképpen az x0 := 0.75, xn+1 := cos xn (n ∈ N) sorozat konvergál az x = cos(x) egyenlet megoldásához. Adjunk becslést a konvergencia sebességre 1.4 Newton módszer Ebben a pontban iterációs eljárásoknak egy fontos, gyakran használt osztályát ismertetjük. Az algoritmus legegyszerűbb változatát már Newton is használta egyenletek megoldására Azóta kiderült, hogy a módszer alapgondolata általánosabb körülmények között is alkalmazható, többek között egyenletrendszerek, differenciál- és integrálegyenletek megoldására. A legegyszerűbb változat megfogalmazásához induljunk ki egy g : I := [a, b] R differenciálható függvényből és tegyük fel, hogy a g(a) és g(b) számok különböző előjelűek. Ekkor a g függvény valahol felveszi a 0 értéket az I intervallumban Ha ezen túlmenően az g függvény deriváltja nem tűnik el

az I intervallumon, akkor az g függvény szigorúan monoton növő, következésképpen pontosan egy olyan x∗ ∈ (a, b) 9 1.Iterációs eljárások létezik, amelyre g(x∗ ) = 0 (4.1) teljesül. Newton gondolatmenetét követve rekurzióval egy x∗ -hoz konvergáló sorozatot szerkesztünk. Az xn ismeretében xn+1 -et a következőképpen kapjuk: Húzzuk meg a g függvény grafikonjának az érintőjét az Pn := (xn , g(xn )) pontban. Jelölje xn+1 az érintő és az X tengely metszéspontjának x-koordinátáját. Az xn -ből kiindulva xn+1 egyszerűen kiszámı́tható. A Pn ponton áthaladó érintő iránytangense a g függvény xn helyen vett deriváltjával egyenlő. Ezt felhasználva az érintő egyenlete felı́rható (4.2) y − g(xn ) = g  (xn )(x − xn ) (x ∈ R) alakban. Minthogy (xn+1 , 0) az érintő egy pontja, azért kielégı́ti a (42) egyenletet: 0 − g(xn ) = g  (xn )(xn+1 − xn ).

Innen rendezés után xn+1 -re (4.3) xn+1 = xn − g(xn ) (n ∈ N) g  (xn ) adódik. Ezt az iterációs eljárást Newton-módszernek nevezik Bevezetve az (4.4) f (x) := x − g(x) (x ∈ I) g  (x) függvényt a (4.3) eljárás felı́rható (4.5) xn+1 = xn − g(xn ) = f (xn ) (n ∈ N) g  (xn ) alakban, következésképpen erre is alkalmazhatók az előző pont eredményei. Könnyen belátható, hogy az x∗ ∈ I pontosan akkor fixpontja az f -nek, ha a g-nek zérushelye. Valóban az g(x∗ ) ∗ ∗ ∗ x = f (x ) = x −  ∗ g (x ) feltétel ekvivalens a g(x∗ ) = 0 egyenlettel. Az előző pontban megmutattuk, hogy a konvergens (xn , n ∈ N) sorozat határértéke f -nek fixpontja, következésképpen g-nek zérushelye. Számos, könnyen ellenőrizhető feltétellel garantálható a (43) sorozat konvergenciája Tegyük fel például, hogy g(a) < 0 < g(b), g  (x) > 0 (x ∈ [a, b]) továbbá g konvex

függvény. Ekkor g szigorúan monoton növő, s ezért g-nek pontosan egy x∗ zérushelye van. A konvexitásból következik, hogy bármely x∗ -nál nagyobb x0 -ból kiindulva monoton fogyó, következésképpen konvergens sorozatot kapunk Valóban ilyenkor 10 1.4 Newton módszer x∗ < xn <= b, és a többi feltételből g(xn ) > 0 és g  (xn ) > 0 következik. Innen (43) alapján nyilvánvaló, hogy xn+1 = xn − g(xn ) < xn (n ∈ N), g  (xn ) azaz a szóban forgó sorozat monoton fogyó, s ezért konvergens. A lehetséges eseteket összefoglalva a következő állı́tást kapjuk: Newton iteráció. Tegyük fel, hogy a kétszer differenciálható g : [a, b] R függvényre (4.6) g(a)g(b) < 0, g  (x) = 0, g  (x) = 0 (x ∈ [a, b]) teljesül. Ekkor egyetlen olyan x∗ ∈ (a, b) létezik, amelyre g(x∗ ) = 0 Legyen x0 = a vagy x0 = b aszerint, hogy g(a)g  (a) > 0 vagy g(b)g  (b) > 0.

Ekkor a (43) rekurzióval értelmezett sorozat konvergál a g zérushelyéhez Az eljárás konvergencia sebessége az f függvény (4.7) f  (x) = 1 − [g  (x)]2 − g(x)g  (x) g(x)g  (x) = (x ∈ I) [g  (x)]2 [g  (x)]2 deriváltjával kapcsolatos. Felhasználva a Taylor formulát a Newton-módszer hibájára egy jól használható becslést adhatunk. A (47) egyenlőség alapján f  (x∗ ) = 0 Ebből a feltételből következik, hogy a Newton módszer másodrendben konvergens. Definı́ció. Akkor mondjuk, hogy az (xn , n ∈ N) sorozat másodrendben konvergens az x∗ -hoz, ha létezik olyan K > 0 szám, hogy (4.8) |xn+1 − x∗ |
K|xn − x∗ |2 (n ∈ N). Eltekintve az f speciális alakjától tegyük fel, hogy az f : [a, b] R kétszer folytonosan differenciálható függvénynek az x∗ fixpontja és az f deriváltja eltűnik ebben a pontban: (4.9) f (x∗ ) = x∗ , f  (x∗ ) = 0. Ekkor az xn+1 = f (xn )

(n ∈ N) iterációval értelmezett sorozatra érvényes a (4.8) hibabecslés, ahol K = maxa
x
b |f  (x)|/2. Az x∗ pontban felı́rva a Taylor formulát másodfokú maradéktaggal (4.9) alapján 1 1 f (x) = f (x∗ ) + f  (x∗ )(x − x∗ ) + f  (ξ)(x − x∗ )2 = x∗ + f  (ξ)(x − x∗ )2 2 2 11 1.Iterációs eljárások adódik, ahol ξ egy x és x∗ közé eső szám. Ezt az egyenlőséget x = xn esetén felı́rva xn+1 − x∗ = f (xn ) − x∗ = adódik, ahonnan (4.8) következik Példaként oldjuk meg a 1  f (ξn )(xn − x∗ )2 2 g(x) := x2 − a = 0 egyenletet, ahol a >√0 adott pozitı́v szám. A négyzetgyök értelmezése alapján ennek pozitı́v megoldása a a szám. A g a [0, ∞) intervallumon szigorúan monoton növő, konvex függvény, amelyre tetszőleges x0 > 0 kezdeti értékből kiindulva a Newton-iteráció másodrendben √ konvergens. Az a = 2 esetben az x0 = 2 kezdeti

feltételből kiindulva a következő, 2-höz konvergáló sorozatot kapjuk: x0 = 2.0000000000000 x1 = 1.5000000000000 x2 = 1.4166666666666 x3 = 1.4142156862745 x4 = 1.4142135623746 x5 = 1.4142135623731 A kiı́rásban vastag betűkkel jeleztük a pontos jegyeket. Látható, hogy a másodrendű konvergenciával összhangban az első tagtól kezdve a pontos jegyek száma lépésenként megduplázódik. 1.5 Fraktálok A fixpont-tételt felhasználva érdekes geometriai alakzatokat, ún. fraktálokat konstruálhatunk Ebben az alkalmazásban az alapul tekintett metrikus tér elemei valamely metrikus tér kompakt részhalmazai, a távolságot pedig az ún. Hausdorff-féle metrikával értelmezzük  az X kompakt részhalmazainak Induljunk ki egy (X, ρ) metrikus térből és legyen X összessége: (5.1)  := {A ⊆ X : A kompakt, A = ∅}. X  A Haussdorff-metrika értelmezéséhez jelölje ρ(a, A) az a ∈ X pontnak a A ∈ X

kompakt halmaztól vett távolságot: ρ(a, A) := min{ρ(a, x) : x ∈ A}. 12 1.5 Fraktálok Minthogy |ρ(a, x) − ρ(a, y)|
ρ(x, y) (a, x, y ∈ X), azért az X x ρ(a, x) ∈ [0, ∞) leképezés (egyenletesen) folytonos. A Weierstrasstétel alapján létezik a ρ(a, A) minimum Nyilvánvaló, hogy ρ(a, A) = 0, akkor és csak akkor, ha a ∈ A. Könnyen igazolható, hogy a halmaztól vett távolságra |ρ(x, A) − ρ(y, A)|
ρ(x, y) (x, y ∈ X), (5.2) következésképpen az X x ρ(x, A) ∈ R+ függvény is (egyenletesen) folytonos. ∗ Valóban, legyen y ∈ A olyan pont, amelyre ρ(y, y ∗ ) = ρ(y, A). Ekkor a halmaztól vett távolság értelmezése és a háromszög-egyenlőtlenség alapján ρ(x, A)
ρ(x, y ∗ )
ρ(x, y) + ρ(y, y ∗ ) = ρ(x, y) + ρ(y, A), ahonnan ρ(x, A) − ρ(y, A)
ρ(x, y) (x, y ∈ X) következik. Innen, valamint az x és y szerepcseréjével adódó egyenlőtlenségből a (52)

állı́tást kapjuk. A  ρ(B, A) := max{ρ(x, A) : x ∈ B} (A, B ∈ X) (5.3) függvény nem szimmetrikus az A és B változókban. Ebből kiindulva azonban már egyszerűen értelmezhető az alábbi metrika. Definı́ció. A (5.4)  ρ(A, B) := max{ρ(A, B), ρ(B, A)} (A, B ∈ X) számot a A és B kompakt halmaz Hausdorff-távolságának nevezzük. Megadható a Haussdorf-féle távolságnak egy másik, fentivel ekvivalens értelmezése. Ehhez vezessük be az A ⊆ X halmaz r sugarú környezetét: Kr (A) :=  Kr (a) (r > 0). a∈A  halmazra értelmezzük a Ennek felhasználásával tetszőleges A, B ∈ X (5.5) χ(A, B) := inf{r > 0 : A ⊆ Kr (B)} 13 1.Iterációs eljárások számot. Nyilvánvaló, hogy a (55) értelmezésben szereplő halmaz nem üres Bebizonyı́tjuk a következő állı́tás: Tétel. Bármely A, B ∈ X halmazra ρ(A, B) = χ(A, B), következésképpen a Hausdorff-féle

távolságra (5.6)  ρ(A, B) := max{χ(A, B), χ(B, A)} (A, B ∈ X) teljesül. Megmutatható, hogy a Hausdorff-távolság metrika a kompakt halmazok terén.  leképezés egy metrika a X  Tétel. A ρ̂(A, B) (A, B ∈ X) téren. Az X halmazon értelmezett f : X X függvény természetes módon terjeszthető  halmazon értelmezett függvénnyé. Nevezetesen, tetszőleges A ⊆ X halmazra ki az X jelölje f (A) := {f (a) : a ∈ A} az A halmaz f függvény által létesı́tett képét. Több pont-pont függvényből kiindulva is lehet természetes módon halmaz-halmaz leképezést értelmezni. Ezzel kapcsolatos az alábbi fogalom Definı́ció. Legyenek fi : X X (i = 1, 2, · · · , n) az X térnek önmagába való leképezései. Ekkor az (5.7) f(A) := n  fi (A) (A ⊆ X) i=1 utası́tással értelmezett leképezést az (fi , i = 1, · · · , n) függvények által generált Hutchinson-leképezésnek

nevezzük. A továbbiakban feltesszük, hogy a kiindulásul szolgáló fi : X X függvények folytonosak és az f leképezést leszűkı́tjük a kompakt halmazok osztályára. Minthogy kompakt halmazok folytonos képe kompakt és véges sok kompakt halmaz egyesı́tése is  halmazt önmagába képezi. kompakt, ezért ilyenkor az f függvény az X Speciálisan, ha az fi : X X (i = 1, · · · , n) függvények kontrakciók, akkor az f leképezés is az. Ezzel kapcsolatos az alábbi állı́tás: 14 1.5 Fraktálok Tétel. Tegyük fel, hogy az fi : X X (i = 1, · · · , n) leképezések kontrakciók a ηi < 1 (i = 1, · · · , n) kontrakciós  X  állandókkal. Ekkor az ezek által generált f : X Hutchinson-leképezés is kontrakció, azaz (5.8)  ρ(f(A), f(B))
η ρ(A, B) (A, B ∈ X), ahol η := max{ηi : i = 1, · · · , n}.  ρ) tér is az. A ρ metrikában Megmutatatható, hogy ha (X, ρ) teljes,

akkor a (X, konvergens halmazsorozat hatáértéke a halmazműveletek és a halmazok lezárásának segı́tségével explicit alakban adható meg. Nevezetesen (5.9) lim An = n∞ ∞  ∞  Am . n=0 m=n Bebizonyı́tjuk a következő állı́tás.  ρ) Tétel. Legyen (X, ρ) teljes metrikus tér Ekkor az (X, metrikus tér is teljes.  ρ) térben A mondottakból következik, hogy (X, ρ) teljes metrikus tér esetén a (X, is alkalmazható a fixpont-tétel. Speciálisan kontrakciós leképezések Hutchinson függvényének van fixpontja és az iterációs eljárás határértékeként származtatható 15 2. Függvények közelı́tése 2. FÜGGVÉNYEK KÖZELÍTÉSE Ebben a fejezetben néhány függvények közelı́tésére szolgáló eljárást ismertetünk. Ezzel összefüggésben a következő kérdések vethetők fel: 1. Milyen függvényosztályból választjuk a közelı́tésre

használt függvényeket 2. Milyen értelembem közelı́tünk Másként fogalmazva, hogyan mérjük az adott és a közelı́tő függvények eltérését. A közelı́tésre (idegen szóval:approximációra) szolgáló függvényosztály kiválasztásánál az egyik legfontosabb szempont, hogy annak elemei egyszerűen megadhatók és a függvények értékei könnyen kiszámı́thatók legyenek. Az egyszerűnek tekintett függvények osztálya a numerikus matematika története során állandón bővült, a rendelkezésre álló számı́tástechnikai lehetőségektől és a felhasználástól függően. Az egyik leggyakrabban használt, közelı́tésre szolgáló függvények az algebrai polinomok. Periódikus függvények approximációjára trigonometrikus polinomokat szokás használni. Széles körben alkalmazzák a szakaszonként polinomokból összerakott függvényeket, az ún. spline

függvényeket A második szemponttal kapcsolatban is felsorolunk néhány eljárást, amelyekkel ebben a fejezetben részletesen is foglalkozunk. Ha valamely (többször differenciálható) függvényt egy adott szám kis környezetében kı́vánjuk approximálni polinommal, akkor célszerű a függvény Taylor-polinomjait használni. Ha azt kı́vánjuk meg, hogy az adott és a közelı́tő függvény értékei előı́rt pontokban megegyezzenek, akkor interpolációt alkalmazunk. Gyakran két függvény eltérését valamilyen normával mérjük Skaláris szorzat által indukált normából kiindulva egy igen gyakran használt approximációs eljárást, a legkisebb négyzetek módszerét kapjuk. A maximum normát alapul véve az egyenletes approximáció kérdésköréhez jutunk. 1. Algebrai polinomok Függvények közelı́tésére leggyakrabban polinomokat használnak. Jelölje K = R a valós vagy K = C

a komplex számok halmazát. Kiindulva az n ∈ N természetes számból és az a0 , a1 , · · · , an (valós vagy komplex) számokból vezessük a (1.1) P (x) := a0 + a1 x + · · · + an xn (x ∈ K) 16 1. Algebrai polinomok függvényt. A P függvényt n-edfokú polinomnak, az a0 , a1 , · · · , an számokat a P együtthatóinak, az an számot a P fő együtthatójának nevezzük. Ha a P fő együtthatója nem nulla, akkor azt mondjuk, hogy P pontosan n-ed fokú Az n-ed fokú polinomok osztályát a Pn , a polinomok halmazát a P szimbólummal fogjuk jelölni: P := ∪∞ n=0 Pn . A P függvényosztály lineáris teret alkot a függvények körében szokásos összeadás és a számmal való szorzás műveletére nézve. A P térnek Pn egy (n + 1) dimenziós altere. Ennek a (1.2) h0 (x) := 1, h1 (x) := x, · · · , hn (x) := xn (x ∈ K) polinomok egy bázisát alkotják, azaz minden P ∈ Pn n-edfokú polinom

egyértelműen állı́tható elő ezek lineáris kombinációjaként. A P tér nullvektora a θ(x) := 0 (x ∈ K) (azonosan 0) polinom. A nulladfokú polinomok P0 halmaza azonos a konstans függvények összességével. Az α ∈ K számot a P polinom gyökének vagy zérushelyének nevezzük, ha P (α) = 0. A numerikus matematika egyik alapfeladata a különböző tı́pusú egyenletek és egyenlet rendszerek megoldása. Ez a feladat visszavezethető függvények zérushelyeinek kiszámı́tására. Az algebra alaptételének következményeként minden legalább elsőfokú (1.1) alakú, komplex együtthatós polinom esetén létezik olyan (nem feltétlenül egymástól különböző) z1 , z2 , · · · , zn ∈ C komplex szám, amelyekkel a P polinom felı́rható (1.3) P (z) = an (z − z1 )(z − z2 ) · · · (z − zn ) (z ∈ C) alakban. Ezt az előállı́tást a P gyöktényezős alakjának nevezzük

Ebből az előállı́tásból nyilvánvalóan következik, hogy P (z1 ) = P (z2 ) = · · · = P (zn ) = 0, vagyis a gyöktényezős alakban szereplő z1 , · · · , zn számok a P polinom gyökei, továbbá a P -nek nem létezik ezektől a számoktól különböző gyöke. Speciálisan, ha valamely n-edfokú polinomnak n-nél több gyöke van, akkor a polinom a θ nulla polinommal egyenlő. Előfordulhat, hogy valós egyűthatós polinomnak nincs valós gyöke. Ilyen pl a P (x) := x2 + 1 (x ∈ R) polinom. A valós számok halmazának kibővı́tésével és a komplex számok bevezetésével olyan számtesthez jutunk, amelyben a P (z) = 0 egyenletnek mindig van megoldása. Elsősorban ez indokolja a komplex számok használatát Az ilyen tı́pusú egyenletek megoldásával az későbbi fejezetben foglalkozunk. Az (1.1) polinom helyettesı́tési értékei a definı́ció alapján az összeadás és szorzás

műveletét felhasználva közvetlenül kiszámı́thatók. Hatékonyabb (kevesebb műveletet igénylő) algoritmust kapunk, ha a P következő előállı́tásából indulunk ki: P (z) = a0 + z(a1 + z(a2 + · · · + z(an−1 + an z) · · · )) (z ∈ C). Ezt felhasználva a P (z) értékét a következő (fordı́tott irányú) rekurzióval (az ún. Horner-féle algoritmussal) számithatjuk ki: (1.5) Pn := an Pk−1 := ak−1 + zPk (k = n, n − 1, · · · , 1) P (z) = P0 . 17 2. Függvények közelı́tése Az osztás műveletét is felhasználva kibővı́thetjük a polinomok osztályát, bevezetve a polinomok hányadosaként adódó függvényeket: R := {R = P : P, Q ∈ P, Q = θ}. Q Az R függvényosztály elemeit racionális függvényeknek nevezzük. A Q(x) = 1 (x ∈ K) választás esetén az R függvény egy polinom, következésképpen R a polinomok halmazát (valódi) részhalmazként

tartalmazza. Mivel a Q = θ polinomnak csak véges sok gyöke van, azért a racionális függvények véges sok pont kivételével az egész K halmazon értelmezve vannak. Valós és komplex együtthatós polinomok és racionális függvények ábrázolására, a komplex aritmetika és a Horner-algoritmus bemutatására szolgál a POLINOMOK nevű program. 2. Taylor polinomok A többször differenciálható függvényeket értelmezési tartományuk valamely a pontjának környezetében gyakra közelı́tjük (x − a) hatványai szerint haladó Tn (x) := a0 + a1 (x − a) + a2 (x − a)2 + · · · + an (x − a)n (x ∈ R) (2.1) alakú polinomokkal. A Tn polinom ak együtthatói kifejezhetők a Tn polinom a helyen vett deriváltjaival, nevezetesen (k) Tn (a) ak = k! (2.2) (k = 0, 1, · · · , n), (0) ahol Tn (a) := Tn (a) és 0! := 1. Valóba, a (21) definı́cióban x = a helyettesı́tés után Tn (a) = a0 adódik. A

(21)-ben szereplő függvényeknek véve a deriváltját azt kapjuk, hogy Tn (x) := a1 + 2 a2 (x − a) + · · · + n an (x − a)n−1 (x ∈ R). Innen az x = a helyettesı́tés után Tn (a) = a1 következik. Ezt az eljárást folytatva tekintsük a (2.1) alatti függvények k-adik deriváltját: Tn(k) (x) = k! ak + (k + 1)k · · · 2 (x − a) + · · · + n(n − 1) · · · (n − k + 1) (x − a)n−k . Véve az a helyen a függvények értékeit a bizonyı́tandó (2.2) egyenlőséget kapjuk Kiindulva a (2.2) képletből bevezetjük a következő fogalmat: 18 2. Taylor polinomok Definı́ció. Tegyük fel, hogy az f : (a − r, a + r) R függvény n-szer differenciálható az a pontban. A (2.3) (Tn f )(x) := n  f (k) (a) k=0 k! (x − a)k (x ∈ R) polinomot az f függvény a-hoz tartozó n-edik Taylor-polinomjának nevezzük. A (2.2) formulákat az f függvény Tn := Tn f Taylor polinomjára alkalmazva azt kapjuk,

hogy az f függvény és a Tn Taylor polinom deriváltjai az a pontban az n-edik rendig bezárólag megegyeznek: Tn(k) (a) = f (k) (a) (k = 0, 1, 2, · · · , n). Könnyű belátni, hogy ez a tulajdonság jellemzi a Taylor polinomokat. Ha a függvény (n + 1)-szer differenciálható, akkor az f és Tn f eltérése egy jól használható alakban állı́tható elő. Ezzel kapcsolatos a Taylor formula. Tegyük fel, hogy az I := (a − r, a + r) intervallumon értelmezett f függvény (n + 1)-szer differenciálható. Ekkor minden x ∈ I ponthoz létezik olyan ξ ∈ I pont, hogy az f és Tn f különbsége felı́rható f (x) − (Tn f )(x) = (2.4) f (n+1) (ξ) (x − a)n+1 (n + 1)! alakban. Ha az f (n+1) függvény korlátos az I intervallumon, azaz ha létezik olyan K > 0 szám, hogy |f (n+1) (x)|
K (2.5) (x ∈ I), akkor (2.4) alapján fennáll az (2.6) K|x − a|n+1 (x ∈ I) |f (x) − (Tn f )(x)|
(n + 1)! becslés.

Ilyenkor annál kisebb a hiba, minél közelebb van az x pont az a-hoz Speciálisan, ha f akárhányszor differenciálható és a (2.5) feltétel (egy n-től független) K állandóval fennáll, akkor a szóban forgó eltérés I-re vonatkozó szuprémumára f − Tn f 
K(2r)n+1 (n + 1)! 19 2. Függvények közelı́tése becslés adódik, következésképpen lim f − Tn f  = 0. n∞ Ezek a becslések alkalmazhatók pl. a sin, cos, exp függvényekre 3. Interpolációs eljárások Ebben a pontban egy nagyon elterjedt approximációs eljárással, az interpolációval foglalkozunk. Az ezzel kapcsolatos feladat megfogalmazásához induljunk ki egy f : I = [a, b] R függvényből. Legyen F egy I-n értelmezett függvényekből álló (kitüntetett, egyszerűnek tekintett) függvényosztály, amelynek elemeivel az f -et közelı́teni kı́vánjuk. Rögzı́tsünk egy n + 1 pontból álló (3.1) a
x0

< x1 < · · · < xn
b pontrendszert. Határozzuk meg azt (vagy azokat) az F-hez tartozó P függvény(eke)t, amelyekre a (3.2) P (x0 ) = f (x0 ), P (x1 ) = f (x1 ), · · · P (xn ) = f (xn ) interpolációs feltétel teljesül. A (31) számokat az interpolációs eljárás csomópontjainak nevezzük A most megfogalmazott interpolációs feladattal kapcsolatban a következő kérdéseket szokás felvetni: 1. 2. 3. 4. Egyáltalán létezik-e a (3.2) feladatnak megoldása (az egzisztencia kérdése) A feladatnak egy vagy több megoldása van (az unicitás kérdése). A megoldás előállı́tására szolgáló algoritmus leı́rása. A közelı́tés hibájának becslése. Ebben a pontban polinom interpolációval foglalkozunk, azaz az F = P függvényosztályt vesszük alapul. A 2 kérdésre válaszolva először megmutatjuk, hogy a (32) feladatnak az n-edfokú polinomok körében (azaz F = Pn esetén)

legfeljebb egy megoldása lehet. Valóban tegyük fel, hogy a P1 , P2 ∈ Pn polinomok mindegyike kielégı́ti a (32) feltételt. Ekkor a két polinom R := P1 − P2 ∈ Pn különbsége eltünik az x0 , x1 , · · · , xn pontokban, azaz az n-edfokú R polinomnak n + 1 gyöke van. Innen következik, hogy R = θ a nulla polinom, következésképpen P1 = P2 . Az interpolációs polinomok előállátásához Lagrange gondolatmenetét követve a Pn térnek egy olyan új 0 , 1 , · · · , n bázisát vezetjük be, amely eleget tesz az  0, ha i = k, (3.3) k (xi ) = 1, ha i = k 20 3. Interpolációs eljárások feltételnek. Az k ∈ Pn polinom a (3.3) feltétel alapján könnyen előállı́tható Valóban, mivel e feltétel szerint az xj (j = k) számok az k -nak gyökei, azért ez a polinom n  k (x) = ck (x − xj ) j=0,j=k alakú. Az k (xk ) = 1 feltétel alapján kiszámı́tva a ck értékét, az előállı́tást

kapjuk: (3.4) k (x) = n  j=0,j=k x − xj xk − xj k -ra a következő (k = 0, 1, · · · , n, x ∈ R). A (3.4) polinomokat Lagrange-féle alappolinomoknak nevezzük Ezeket felhasználva a (32) feltételt kielégı́tő polinom felı́rható (3.5) Pn (x) = f (x0 ) 0 (x) + · · · + f (xk ) k (x) + · · · + f (xn ) n (x) (x ∈ R) alakban. Könnyen ellenőrizhető, hogy ez az n-edfokú polinom valóban kielégı́ti a (32) feltételt. Minthogy (33) alapján a (35) összegnek az i-edik tagját kivéve minden tagja 0 értéket vesz fel az xi helyen és az i-edik tag értéke az xi helyen f (xi ), ezért Pn valóban kielégı́ti a (3.2) feltételt Rögzı́tve a csomópontokat, minden f : [a, b] R függvényhez pontosan egy Pn ∈ Pn polinom létezik, emely eleget tesz a (3.1) feltételnek Ezt a polinomot kifejezve az f függvénnyel való kapcsolatát Pn helyett gyakran az Ln f szimbólummal jelöljük. A (3.4) és (35)

előállı́tások alkalmasak az interpoláló polinom helyettesı́tési értékeinek kiszámı́tására Az f és Pn eltérését előállı́thatjuk az f függvény deriváltjának segı́tségével. Ezzel kapcsolatos a következő Hiba formula. Tegyük fel, hogy az f függvény n + 1-szer differenciálható. Ekkor minden x ∈ I ponthoz létezik olyan ξ ∈ I hely, hogy az f és a Pn eltérése az x pontban felı́rható (3.6) f (n+1) (ξ) f (x) − (Ln f )(x) = (x − x0 )(x − x1 ) · · · (x − xn ) (n + 1)! alakban. Tegyük fel, hogy az f függvény akárhányszor differenciálható és deriváltjainak abszolút értékei egy közös korlát alatt maradnak, azaz létezik olyan K > 0 szám, hogy (3.7) |f (n) (x)|
K (x ∈ I, n = 0, 1, 2, · · · ). 21 2. Függvények közelı́tése Ilyenkor a függvény és az interpoláló polinom eltérésére a következő becslés adható: |f (x) −

(Ln f )(x)|
(3.8) K(b − a)n+1 (x ∈ I, n = 0, 1, 2, · · · ). (n + 1)! Könnyen belátható, hogy a jobb oldalon álló sorozat tart 0-hoz, ha n ∞. A (38) becslés pl. fennáll a sin, cos, exp függvényekre Ezekre a függvényekre a Pn interpolációs polinomok tartananak a függvényhez, ha n ∞, bármilyen [a, b]-beli csomópont rendszert választva. 5. Bernstein polinomok, Beziér görbék Az interpolációs polinomok nem öröklik a közelı́tett függvény monotonitását, konvexitását, stb. Ebben a pontban olyan approximációs eljárást ismertetünk, amely amellett, hogy egyenletes közelı́tésre használható, megtartja az közelı́tett függvény bizonyos geometriai tulajdonságait. Ezt az eljárást S Bernstein vezette be 1912-ben függvények közelı́tésére. Az 1970-es évektől kezdődően Beziér francia mérnök munkássága nyomán ezek alkalmazása széles körben elterjedtek a

műszaki tervezésben. A Bernstein polinomok értelmezéséhez induljunk ki az n  n k n−k (a + b) = a b k n (a, b ∈ R, n ∈ N) k=0 binomiális azonosságból, ahol (4.1) n 0 n k := 1 (n ∈ N), := n(n − 1) · · · (n − k + 1) (k, n = 1, 2, · · · ) 1 · 2···k a binomiális együtthatókat jelöli. A binomiális együtthatók értelmezése alapján nyilvánvaló, hogy nn = 1, nk = 0 (k > n), továbbá a binomiális együtthatókra érvényes a következő rekurziós formula: (4.2) n n + k k+1 = n+1 k+1 (n, k ∈ N). Valóban egyszerű számolással n n + k k+1 n(n − 1) · · · (n − k + 1) n − k 1+ = 1 · 2···k k+1 n(n − 1) · · · (n − k + 1) n + 1 n+1 = = 1 · 2···k k+1 k+1 = 22 4. Bernstein polinomok, Beziér görbék adódik. A binomiális együtthatókat szokás az alábbi, ún Pascal-féle háromszög formájában elhelyezni: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 . Ennek alapján a

(4.2) rekurzió a következőképpen interpretálható: a sémában lévő bármely szám a felette álló két szám összegével egyenlő. A binomiális együtthtatók akár a (4.1) definı́ció, akár a (42) rekurziós formulák alapján kiszámı́thatók A binomiális tételt az a = x, b = 1 − x esetben alkalmazva az n  n k x (1 − x)n−k (x ∈ R) 1= k k=0 azonosságot kapjuk. Ennek az összegnek az (4.3) Nk,n (x) := n k x (1 − x)n−k k (n, k ∈ N, x ∈ R) tagjai a Pn tér egy bázisát alkotják. Ezeket a polinomokat Bernstein-féle alappolinomoknak nevezzük A (43) értelmezés alapján (4.4) Nk,n (x) ≥ 0 (n, k ∈ N, x ∈ [0, 1]), N0,n (0) = 1, Nk,n (0) = 0 (k = 1, 2, · · · , n), Nn,n (1) = 1, Nk,n (1) = 0 (k = 0, 1, · · · , n − 1). Kiindulva valamely f : [0, 1] R függvényből bevezetjük az f függvény (4.5) (Bn f )(x) := Bn (x) := n  k=0 k Nk,n (x) f n (x ∈ R, n = 1, 2, · · · )

Bernstein polinomjait. Az alappolinomok (44) tulajdonságából (4.6) (Bn f )(0) = f (0), (Bn f )(1) = f (1) következik. Ez másként szólva azt jelenti, hogy Bn f interpolál a [0, 1] intervallum végpontjaiban (44) alapján nyilvánvaló, hogy f ≥0 ⇒ Bf ≥ 0. 23 2. Függvények közelı́tése Ennek alapján azt szoktuk mondani, hogy a Bn f pozitı́v operátor. A folytonos függvények tetszőleges pontossággal egyenletesen közelı́thetők Bernstein polinomjaikkal. Ezzel kapcsolatos a következő Approximációs tétel. Legyen f a [0, 1] intervallumon értelmezett folytonos függvény. Ekkor minden  > 0 számhoz létezik olyan N ∈ N szám, hogy minden x ∈ [0, 1] pontban minden n ≥ N indexre |f (x) − (Bn f )(x)| <  teljesül. Ez az állı́tás a már korábban bevezetett g := maxx∈[0,1] |g(x)| maximum normát használva átfogalmazható a következő formában: lim f − Bn f  = 0. n∞

Differenciálható függvény esetén a konvergenci sebességre az alábbi becslés adható: f − Bn f 
3f   √ (n = 1, 2, · · · ). 2 n A Bernstein-féle polinomok alaktartó tulajdonságai a Bn függvények deriváltjaira vonatkozó alábbi azonosságból következnek. Az (n − 1)-edfokú Bn polinom felı́rható a Pn−1 tér Nk,n−1 (k = 0, 1, · · · , n − 1) bázisa segı́tségével: (4.7) Bn (x) =n n−1  k=0 k  k + 1 −f Nk,n−1 (x) (n ∈ N, x ∈ R). f n n Valóban, az Nn,k polinom deriváltja a szorzatfüggvény deriválási szabálya alapján egyszerű átalakı́tás után előállı́tható a következő alakban: n k−1 n k x (1 − x)n−k − (n − k) x (1 − x)n−k−1 = k k n−1 k n − 1 k−1 (1 − x)n−1−(k−1) − n x (1 − x)n−1−k = =n x k k−1  = n Nk−1,n−1 (x) − Nk,n−1 (x) .  Nk,n (x) = k Ezt felhasználva (4.5)-ből tagonkénti differenciálással Bn

= n  k  Nk,n = f n k=0 n  =n k=0 n  k k Nk−1,n−1 − n Nk,n−1 f f n n k=0 24 4. Bernstein polinomok, Beziér görbék adódik. Az első összegben a nulladik tag, a második összegben az n-edik tag 0 Ezt figyelembe véve és az első összegben k helyett (k + 1)-et ı́rva a (4.7) bizonyı́tandó azonosságot kapjuk. A most bemutatott bizonyı́tást Bn helyett Bn -re megismételve a Bernstein polinomok második deriváltjára a következő előállı́tást kapjuk: (4.8) Bn (x) = n(n − 1) n−2  f k=0 k + 1 k  k + 2 − 2f +f Nk,n−2 (x) n n n (n ∈ N, x ∈ R). A (4.7) és (48) azonosságokból közvetlenül adódik az alábbi Tétel. i) Ha az f : [0, 1] R függvény monoton növő (fogyó), akkor ennek Bn f (n = 1, 2, · · · ) Bernstein polinomjai is monoton növők (fogyók). ii) Ha az f függvény konvex (konkáv), akkor Bn f is konvex (konkáv).   k+1 k Valóban, ha f monoton

növő, akkor f n − f n ≥ 0 (k = 0, 1, · · · , n − 1), következésképpen (4.4) alapján Bn (x) ≥ 0 (x ∈ [0, 1]) Innen már nyilvánvaló, hogy Bn monoton növő.    k+1 k Ha f konvex, akkor a f k+2 − 2f + f n n n ≥ 0 (k = 0, 1, · · · , n − 2) és ı́gy (4.8) alapján Bn (x) ≥ 0 (x ∈ [0, 1]), következésképpen Bn konvex A zárójeles állı́tások hasonlóan igazolhatók. Gyakran előfordul, hogy paraméteres alakban adott sı́k- vagy térgörbéket közelı́tünk olyan görbékkel, amelyek koordináta függvényei polinomok. Ilyen célra szolgálnak a Bezier görbék alábbi változatai. Legyen φ : I := [0, 1] Rd (d = 2, 3) egy sı́k- vagy térgörbe paraméteres előállı́tása és vezessük be a Φn (t) := n  k=0 φ k Nk,n (t) (t ∈ [0, 1]) n fügvényt. Az ı́gy értelmezett Φn : I Rd függvény d = 2 esetben egy sı́k-, d = 3 esetben pedig egy térgörbe paraméteres

előállı́tásának tekinthető. Ezeket Beziergörbéknek nevezzük A fentiek mintájára értelmezhetők a kétváltozós Bernstein polinomok, ill. a Bezier felületek. Induljunk ki az I 2 := [0, 1] × [0, 1] egységnégyzeten értelmezett f : I 2 R folytonos, kétváltozós függvényből és minden m, n = 1, 2, · · · esetén vezessük be a (4.9) Bm,n (x, y) := (Bm,n f )(x, y) := n m   k=0 =0  k Nk,m (x)N,m (y) f , m n ((x, y) ∈ I 2 ) 25 2. Függvények közelı́tése kétváltozós polinomokat. A Bm,n f (m, n = 1, 2 · · · ) polinomokat az f függvény kétváltozós Bernstein-polinomjainak nevezzük Az értelmezés és (44) lapján nyilvánvaló, hogy Bm,n (0, 0) = f (0, 0), Bm,n (1, 0) = f (1, 0), Bm,n (0, 1) = f (0, 1), Bm,n (1, 1) = f (1, 1), vagyis a Bm,n polinomok az I 2 egységnégyzet négy csúcsában interpolálnak. A (4.9) definı́cióban a számértékű f függvény helyett egy f : I

2 R3 tı́pusú függvényt véve Bezier felületek paraméteres előállı́tását kapjuk. 5. Ortogonalizáció Ebben és a következő pontban olyan approximációs feladatokkal foglalkozunk, amelyekben elemek távolságát az euklideszi tér normájával mérjük. Kiindulva valamely  (X, ·, ·) valós vagy komplex euklideszi térből jelölje f  := f, f  (f ∈ X) a skaláris szorzatból származtatott normát és θ a tér nullvektorát. Rögzı́tsük az X tér egy lineárisan független elemből álló f1 , f2 , · · · , fn vektorrendszerét és jelölje Xn az ezek által kifeszı́tett alteret: (5.1) Xn := {λ1 f1 + λ2 f2 + · · · + λn fn : λ1 , λ2 , · · · , λn ∈ K}. Ezt az alteret a Xn = L{f1 , f2 , · · · , fn } szimbólummal fogjuk jelölni. Euklideszi terekben értelmezhető a merőlegesség fogalma. Akkor mondjuk, hogy az f és g X-beli vektor egymásra merőleges, más szóval

ortogonális, ha skaláris szorzatuk 0: f, g = 0. Ha létezik olyan λ szám, hogy f = λg, akkor azt mondjuk, hogy az f és g vektorok párhuzamosak. Az 1 normájú elemeket normált vektoroknal nevezzük Nyilvánvaló, hogy bármely nullvektortól különböző vektort megszorozva normájának reciprokával egységvektort kapunk. Az (5.2) f0 := 1 f f  vektort az f irányába mutató egységvektornak nevezzük. Ha az e1 , e2 , · · · , en rendszer vektorai páronként merőleges egymásra és normáltak, akkor azt mondjuk, hogy a szóban forgó rendszer ortonormált. Ezzel összefüggésben bevezetjük az ún Kronecker-féle szimbólumot:  0, ha k = , (5.3) δk := 1, ha k = . Nyilvánvaló, hogy az e1 , e2 , · · · , en rendszer pontosan akkor ortonormált, ha (5.4) ek , e  = δk (0
k,
n). 26 5. Ortogonalizáció Az ortonormált rendszerek lineárisan függetlenek. Valóban tegyük fel, hogy λ1 e1 + ·

· · + λk ek + · · · + λn en = θ. Mindkét oldalt az ek vektorral skalárisan szorozva (5.4) alapján λk ek , ek  = λk = 0 (k = 1, 2, · · · , n) következik. Jelölje Xn := L{e1 , e2 , · · · , en } az e1 , e2 , · · · , en rendszer lineáris burkát. Az Xn altér minden x vektora egyértelműen ı́rható fel (5.5) x = x1 e1 + · · · + xk ek + · · · + xn en alakban. Az x1 , x2 , · · · , xn ∈ K számokat az x vektornak a szóban forgó ortonormált rendszerre vonatkozó koordinátáinak nevezük. Az (55) előállı́tásból mindkét oldalt ek -val skalárisan szorozva az xk koordinátákra az (5.6) xk = x, ek  (k = 1, 2, · · · , n) előállı́tás adódik. Többek között a koordinátáknak ez az egyszerű kiszámı́tási módja is indokolja az ortonormált bázisok használatát. Az alábbiakban egy eljárást ismertetünk, amellyel alterekben ortonormált bázisok szerkeszthetők. Kiindulva az

f1 , f2 , · · · , fn ∈ X lineárisan független vektorrendszerből olyan e1 , e2 , · · · , en ∈ X ortonormált rendszert konstruálunk, amelyre (5.7) L{f1 , · · · , fk } = L{e1 , · · · , ek } (k = 1, 2, · · · , n) teljesül. Rekurziót alkalmazva k = 1 esetén legyen e1 := 1 f1 . f1  Ekkor (5.7) a k = 1 esetben fennáll Legyen m < n. Tegyük fel, hogy az e1 , e2 , · · · , em ortonormált rendszert már értelmeztük és erre k = 1, 2, · · · , m esetén fennáll (57) A normáltság feltételét egyelőre figyelmen kı́vül hagyva keressük az em+1 -gyel párhuzamos m+1 vektort (5.8) m+1 = fm+1 − (λ1 e1 + · · · + λk ek + · · · + λm em ) alakban. Az a feltétel, hogy az e1 , · · · , em vektorok merőlegesek m+1 -re azzal ekvivalens, hogy 0 = m+1 , ek  = fm+1 , ek  − λk (k = 1, 2, · · · , m). Ennek alapján értelmezve a (5.9) λk := fm+1 , ek  (k = 1, 2, · · · , m) 27 2.

Függvények közelı́tése számokat és az m+1 vektort az e1 , e2 , · · · , em elemekre merőleges vektort kapunk. Az L{e1 , e2 , · · · , em } = L{f1 , f2 , · · · , fm } indukciós feltételből (5.8) alapján következik, hogy m+1 előállı́tható az f1 , · · · , fm , fm+1 lineáris kombinációjaként, ahol az fm+1 együtthatója nem nulla. Mivel a most emlitett függvények lineárisan függetlenek, azért a szóban forgó lineáris kombinációra m+1 = θ teljesül. A normálás után kapott em+1 := m+1 /m+1  vektor szintén merőleges az e1 , · · · , em vektorokra és előállı́tható az f1 , · · · , fm , fm+1 lineáris kombinációjaként. Az (58) alapján nyilvánvaló, hogy fm+1 előállı́tható az e1 , · · · , em , em+1 lineáris kombinációjaként. Ez utóbbi két megjegyzésből következik, hogy (5.7) k = m + 1 esetén is fennáll Összefoglalva a most ismertetett

Schmidt-féle ortogonalizációs eljárást, a következőt kapjuk. Tétel. Legyen f1 , f2 , · · · , fn ∈ X egy lineárisan független rendszer. Ekkor létezik olyan e1 , e2 , · · · , en ortonormált rendszer, amelyre (5.7) teljesül Az ortonormált rendszer az (5.8) rekurzióval értelmezhető, ahol a λk együtthatók (5.9) alapján számı́thatók és em+1 = m+1 /m+1  6. QR felbontás Ebben a pontban a Schmidt-fél ortogonalizációs eljárást az X = Rn n-dimenziós valós euklideszi térben alkalmazzuk, ahol n = 1, 2, · · · egy rögzı́tett szám. Az X tér vektorai rendezett valós szám n-esek: X := {x = (x1 , x2 , · · · , xn ) : x1 , x2 , · · · , xn ∈ R}. Az X téren a skaláris szorzat az (6.1) x, y := x1 y1 + x2 y2 + · · · + xn yn formulával értelmezzük. Nyilvánvaló, hogy az e1 := (1, 0, · · · , 0), e2 := (0, 1, · · · , 0), · · · , en := (0, 0, · · · , 1) vektorok egy ortonormált

bázist alkotnak. Ezt a Rn tér kanonikus bázisának nevezzük Az ortogonalizációs eljárást arra fogjuk felhasználni, hogy a reguláris mátrixokat speciális mátrixok, nevezetesen ortogonális és felső háromszög mátrix szorzataként állı́tsuk elő. Akkor mondjuk, hogy az Q ∈ Rn×n négyzetes mátrix ortogonális, ha oszlopvektorai ortonormált rendszert alkotnak a (61) skaláris szorzatra nézve Ha az R ∈ Rn×n mátrix főátlója felett álló tagjai 0-val egyenlők, akkor felső háromszög mátrixnak nevezzük. Az ortogonális mátrixokat Q-val, a felső háromszög mátrixokat R-rel szokás jelölni, és erre utal a pont cı́me is. 28 6. QR felbontás Kiindulva az b1 , b2 , · · · , bn ∈ X lineárisan független vektorokból a Schmidth-féle ortogonalizációs eljárás alkalmazásával olyan u1 , u2 , · · · , un ortonormált rendszert kapunk, amelyre L{b1 , · · · , bk } = L{u1 , ·

· · , uk } (k = 1, 2, · · · , n) teljesül. Innen következik, hogy minden k
n esetén léteznek olyan λk1 , · · · , λkk számok, hogy a bk vektor előállı́tható bk = λk1 u1 + · · · + λkk uk (k = 1, 2, · · · , n) alakban, továbbá az ortogonalizációs eljárásból következik, hogy λkk = 0 . A bk vektor j-edik (kanonikus) koordinátáit bkj -vel, az uk -ét ukj -vel jelölve és a most kapott vektor egyenlőségeket koordinátákra átı́rva bkj = λk1 u1j + · · · + λkk ukj (6.2) (k = 1, 2, · · · , n) adódik. A jobb oldalon álló összeg két mátrix szorzatának kj-edik tagjaként fogható fel. Nevezetesen vezessük be az  b11  b21 B :=   . b11 b22 . . bn1 bn2   b1n u11 b2n   u21  . , U := .   . .  bnn un1 ··· ··· ··· ··· u11 u22 . . un2 ··· ··· ··· ···  u1n u2n  .  .  unn mátrixokat, valaminta a  λ11  λ21 Λ := 

 . 0 λ22 . . λn1 λn2 ··· ··· ··· ···  0 0  .  .  λnn alsó háromszög mátrixot. Az A mátrixnak az b1 , · · · , bn , az U -nak az u1 , · · · , un vektorok a sorvektorai. A mátrixszorzás szabálya alapján a (62) egyenlőség átı́rható (6.3) B = ΛU alakba. Áttérve az itt szereplő mátrixok A := B ∗ , Q := U ∗ , R := Λ∗ transzponáltjaira az (6.4) A = QR 29 2. Függvények közelı́tése felbontást kapjuk, ahol Q ortogonális, R felső hárszög mátrix. Megjegyezzük, hogy az A oszlopvektorai azonosak a B sorvektoraival, azaz a b1 , · · · , bn vektorokkal, továbbá az R főátlójának nincs 0 tagja, következésképpen detR = 0. Összefoglalva a mondottakat a következő eljárást kapjuk. QR felbontás. Legyen A ∈ Rn×n egy reguláris mátrix Alkalmazzuk ennek (lineárisan független) oszlopvektoraira a Schmidt-féle ortogonalizációs eljárást. Ekkor

a (62)-ben értelmezett Λ és U mátrixok R := Λ∗ és Q := U ∗ transzponáltajival fennáll a (6.4) QR-felbontás A (6.4) felbontás jól alkalmazható az (6.5) Ax = b lineáris egyenletrendszer megoldására. Felhasználva a (64) felbontást és bevezetve az y := Rx jelölést a (6.5) egyenletrendszerből az alábbi két egyenletrendszert kapjuk: Ax = Q(Rx) = Qy = b, Rx = y. Minthogy a Q ortogonális mátrix inverze Q∗ , azért az első egyenlet megoldása közvetlenül előállı́tható: y = Q∗ b. A második egyenlet részletesen felı́rva r1,1 x1 + · · · + r1,n−1 xn−1 + r1,n xn = y1 . . rn−1,n−1 xn−1 + rn−1,n xn = yn−1 rn,n xn = yn adódik. Az utolsó egyenletből xn kiszámı́tható Ennek ismeretében az utolsó előtti egyenletet felhasználva kiszámı́thatjuk xn−1 -et. Ezt az eljárást folytatva végül eljutunk az első egyenlethez, ahonnan x1 meghatározható. 7. Approximáció euklideszi

terekben A legjobb approximáció problémája euklideszi terekben geometriai feladat formájában is megfogalmazható. Tekintsünk egy sı́kot és egy rajta kı́vül lévő pontot a háromdimenziós euklideszi térben és határozzuk meg a sı́knak az adott ponthoz legközelebb eső pontját. Ismeretes, hogy a minimumot szolgáltató pont az adott pontnak a sı́kra eső merőleges vetülete. 30 7. Approximáció euklideszi terekben Ez a feladat tetszőleges (X, ·, ·) euklideszi térben megoldható. Legyen X ⊂ X egy n dimenziós lineáris altér. A Schmidt-féle ortogonalizációs eljárást alkalmazva az X altérben mindig felvehető egy e1 , e2 , · · · , en ortonormált bázis. Tetszőleges f ∈ X vektornak az X altérre vonatkozó vetületét a következőképpen értelmezzük. Definı́ció. Legyen f ∈ X és e1 , e2 , · · · , en az X altérnek egy ortonormált bázisa. A (7.1) P f := f, e1 e1 +

f, e2 e2 + · · · + f, en en X-beli elemet az f vektor X altérbe eső merőleges vetületének nevezzük. Könnyen ellenőrizhető,hogy az f ⊥ := f − P f vektor merőleges az X altér minden h elemére: f − P f, h = 0 (7.2) (h ∈ X). Először megmutatjuk, hogy az f ⊥ vektor merőleges az ek (k = 1, · · · , n) vektorok mindegyikére. Valóban, mivel az e1 , · · · , en rendszer ortonormált, azért f ⊥ , ek  = f, ek  − n  f, ej ej , ek  = f, ek  − f, ek  = 0. j=1 Az X altér minden eleme a szóban forgó ortonormált vektorok lineáris kombinációja. Mivel f ⊥ a bázis minden elemére ortogonális, azért ezek lineáris kombinációjára, következésképpen az X altér minden vektorára ortogonális. Ezek után egyszerűen igazolható a következő Tétel. Az X altérnek az f ∈ X ponthoz legközelebb eső pontja az f -nek X altérre vett P f merőleges vetülete, azaz (7.3)  

min f − g : g ∈ X = f − P f . Valóban tetszőleges g ∈ X elemből kiindulva tekintsük az f − g = f − P f + (P f − g) = f ⊥ + h felbontást, ahol h := P f − g ∈ X és f ⊥ merőleges az X tér minden elemére, következésképpen h-ra is. Ezt felhasználva f − g2 = f ⊥ + h2 = f ⊥ + h, f ⊥ + h = f ⊥ , f ⊥  + f ⊥ , h + h, f ⊥  + h, h = = f ⊥ 2 + h2 ≥ f − P f 2 31 2. Függvények közelı́tése következik, amivel a (7.3) egyenlőtlenséget igazoltuk Bebizonyı́tható, hogy P f a (7.3) minimum feladat egyetlen megoldása A minimumot szolgáltató P f vetületet anélkül is meghatározható, hogy az X-ben ortogonális bázist vennénk fel. Legyen f1 , f2 , · · · , fn az X egy tetszőleges bázisa Ekkor a P f ∈ X vetület felı́rható ezek lineáris kombinációjaként: (7.4) Pf = n  λj fj . j=1 Mivel f − P f merőleges az Xn tér minden elemére, azért

f − P f, fj  = 0 (j = 1, · · · , n). Ezt felhasználva (74) alapján a P f együtthatóira a következő lineáris egyenletrendszert kapjuk: (7.5) λ1 f1 , f1  + λ2 f2 , f1  + · · · + λn fn , f1  = f, f1  λ1 f1 , f2  + λ2 f2 , f2  + · · · + λn fn , f2  = f, f2  . . λ1 f1 , fn  + λ2 f2 , fn  + · · · + λn fn , fn  = f, fn  Bebizonyı́tható, hogy ha az f1 , f2 , · · · , fn rendszer lineárisan független, akkor a (7.5) egyenletrendszer determinánsa nem 0, következésképpen egyértlműen megoldható. 8. A legkisebb négyzetek módszere A legkisebb négyzetek módszerét a következő feladat kapcsán mutatjuk be. Tegyük fel, hogy egy fizikai mennyiség időbeli változása a g(t) = pt + q (t ∈ [a, b]) lineáris függvénnyel ı́rható le. A fizikai mennyiség t1 , t2 , · · · , tN időpontokban mért értékei legyenek x1 , x2 , · · · , xN . A mérési adatok alapján

határozzuk meg a p, q együtthatók értékét. Mivel a mérési adatok a legtöbb esetben pontatlanok, azért általában nincs olyan g elsőfokú polinom, amelynek grafikonja áthalad a (tj , xj ) (j = 1, 2, · · · , N ) pontokon. Ezért a lineáris függvények közül azt szokás választani, amelyre a mért időpontokban a hibák N  F (p, q) := |g(tj ) − xj |2 j=1 négyzetösszege minimális. A kétváltozós F függvény minimuma az analı́zisben megismert módszerrel meghatározható. Az előző pont eredményeit felhasználva a feladatot sokkal általánosabb feltételek mellet is megoldhatjuk Ehhez bevezetjük a következő euklideszi teret. Rögzı́tsünk egy T := {t1 , t2 , · · · , tN } ⊂ R ponthalmazt és jelölje X a T -n értelmezett valós függvények összességét. Az X vektortér az  (8.1) f, g := f (t)g(t) (f, g ∈ X) t∈T 32 8. A legkisebb négyzetek módszere skaláris

szorzattal euklideszi tér. A skaláris szorzat által indukált norma négyzete ebben az esetben f 2 = f, f  = (8.2) N  |f (tj )|2 j=1  alakú. Az ek (t) := 1, ha t = tk , 0, ha t ∈ T, t = tk (k = 1, 2, · · · , N ) függvényrendszer ortonormált bázis az X téren. Legyen f1 , f2 , · · · , fn ∈ X egy lineárisan független függvényrendszer és jelölje Xn ezek lineáris burkát. A bevezetőben emlı́tett feladatot általánosı́tva adott xj := f (tj ) (j = 1, 2, · · · , N ) függvényértékek esetén határozzuk meg az Xn altérnek azt a g elemét, amelyre N  |xj − g(tj )|2 = f − g2 j=1 minimális. Ha n = 2 és X2 = P1 = L{h0 , h1 } az elsőfokú polinomok halmaza, akkor speciális esetként a bevezetőben emlı́tett feladatot kapjuk. Az előző pontban igazolt tétel szerint a minimumot az f függvény X2 -re vett P f = ph1 +qh0 vetülete szolgáltatja. Ennek p, q együtthatóira fennáll a qh0

, h0  + ph1 , h0  = f, h0  qh0 , h1  + ph1 , h1  = f, h1  egyenletrendszert. Ennek megoldásaként adódó elsőfokú függvényt szokás lineáris regressziónak nevezni