2017 I. félév

Interpoláció és approximáció 2016/2017 I. félév Prof.Dr. Galántai Aurél ÓE NIK Alkalmazott Informatikai Intézet 2016-09-10

2

Tartalomjegyzék

1. Interpoláció 1.1. A lineáris interpoláció . . . . . . . . . . . 1.1.1. Lagrange-interpoláció . . . . . . . . 1.1.2. Trigonometrikus interpoláció . . . . 1.1.3. Exponenciális interpoláció . . . . . 1.1.4. Racionális törtfüggvény interpoláció 1.1.5. További interpoláció típusok . . . . 1.1.6. Többdimenziós interpoláció . . . . 1.2. A Lagrange-féle interpoláció hibája . . . . 1.3. Az Hermite-interpoláció hibája . . . . . . . 1.4. A Lagrange interpoláció konvergenciája . . 1.4.1. Negatív eredmények . . . . . . . . 1.4.2. Numerikus stabilitás . . . . . . . . 1.5. Feladatok . . . . . . . . . . . . . . . . . . 2. Spline interpoláció 2.1. Harmadfokú szplájn interpoláció 2.2. Konvergencia eredmények . . . 2.3. Variációs tulajdonságok . . . . 2.4. Feladatok . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

3. Függvények legjobb egyenletes közelítése 3.1. Legjobb egyenletes approximáció polinomokkal . . . . . . . . . . . . . . . . 3.1.1. Weierstrass tétele és a legjobb approximáció rendje . . . . . . . . . 3.1.2. A legjobb approximáció Csebisev-féle jellemzése és következményei. 3.1.3. Remez algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. A Stone-Weierstrass tétel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . .

. . . . . .

. . . . . . . . . . . . .

. . . .

. . . . . .

. . . . . . . . . . . . .

5 5 7 11 13 14 15 17 21 24 25 30 32 33

. . . .

37 37 45 56 57

. . . . . .

61 65 66 72 78 80 81

4. Racionális approximáció, Padé approximáció 85 4.1. A Padé-approximáció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.2. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5. Alkalmazások: elemi függvények kiszámítási módjai 91 5.1. Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 TARTALOMJEGYZÉK

3

6. Függvények legkisebb négyzetes közelítése 6.1. Közelítések Csebisev polinomokkal . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Approximáció Hilbert-terekben . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3. Klasszikus Fourier-sorok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

95 100 102 112

TARTALOMJEGYZÉK

1. fejezet Interpoláció Az interpoláció feladatát a következ½oképpen fogalmazhatjuk meg. Ismerjük egy y = f (x) (f : R ! R) függvény a x 1 < x 2 < : : : < xn b (1.1) pontokban felvett értékeit, az (1.2)

yi = f (xi ) (i = 1; : : : ; n)

függvényértékeket. Az f (x) függvényt, amely lehet ismert, vagy akár ismeretlen is, egy olyan, általában könnyen számítható h (x) függvénnyel közelítjük (vagy helyettesítjük), amelyre fennáll, hogy yi = h (xi ) (i = 1; : : : ; n): (1.3) Az fxi gni=1 pontokat interpolációs alappontoknak, az (1.3) feltételt interpolációs feltételnek nevezzük. Az interpolációs feltétel teljesülése esetén azt reméljük, hogy a h (x) = h (x; fxi gni=1 ; fyi gni=1 ) interpoláló függvény az (xi ; xi+1 ) intervallumokban jól közelíti az f (x) függvényt. A h(x) függvény megválasztásától függ½oen beszélünk különböz½o típusú interpolációkról. Ha a h(x) függvénnyel f (x)-et az (x1 ; xn ) intervallumon kívül közelítjük, akkor extrapolációról beszélünk.

1.1. A lineáris interpoláció Legyen f 2 C [a; b]. Lineáris interpoláció esetén a h (x) függvény alakja h(x) = a1 '1 (x) + a2 '2 (x) + : : : + an 'n (x) =

n X

ai 'i (x);

(1.4)

i=1

INTERPOLÁCIÓ

5

ahol a 'i 2 C [a; b] (i = 1; 2; : : : ; n) bázisfüggvények adottak. Az ismeretlen a1 ; : : : ; an együtthatókat az interpolációs feltételb½ol határozhatjuk meg. Ekkor teljesülnie kell az alábbi n feltételnek a1 '1 (x1 ) + a2 '2 (x1 ) + : : : + an 'n (x1 ) = y1 ; .. .. .. (1.5) . . . a1 '1 (xn ) + a2 '2 (xn ) + : : : + an 'n (xn ) = yn ; amely lineáris egyenletrendszer 2 '1 (x1 ) 6 .. 4 .

az ismeretlen a1 ; : : : ; an együtthatókra nézve. Ezt átírhatjuk a 32 3 2 3 '2 (x1 ) 'n (x1 ) a1 y1 7 6 .. 7 6 .. 7 .. .. 54 . 5 = 4 . 5 . .

'1 (xn ) '2 (xn )

'n (xn )

an

yn

alakba. Jelölje az együtthatómátrixot

B = ['j (xi )]ni;j=1

(1.6)

és legyen a = [a1 ; : : : ; an ]T ;

y = [y1 ; : : : ; yn ]T :

(1.7)

A fenti feltétel tömör formában (1.8)

Ba = y:

Ha det(B) 6= 0, akkor az egyenletrendszernek pontosan egy megoldása van: a = B 1 y. Ha azt is megköveteljük, hogy minden y jobboldal esetén pontosan egy megoldás legyen, akkor a det (B) 6= 0 feltétel szükséges és elégséges. [Tegyük fel, hogy adott y-ra van két különböz½o megoldás Ba = y = Be a. Ekkor B (a e a) = 0 és a e a 6= 0, ami pontosan akkor lehetséges, ha det (B) = 0. ] Nem minden f'i (x)gni=1 függvényrendszer és x1 < x2 < : : : < xn alappontrendszer esetén van megoldása a lineáris interpolációs feladatnak. Példa. Legyen '1 (x) = 1, '2 (x) = x2 , x1 = 1, x2 = 1. Ekkor B=

1 ( 1)2 1 1

;

det(B) = 0:

De…níció: A 'i 2 C [a; b] (i = 1; 2; : : : ; n) függvényrendszert unisolvensnek nevezük az [a; b] intervallumon, ha tetsz½oleges fxi gni=1 [a; b] esetén, ahol xi 6= xj ( i 6= j), fennáll, hogy det ['j (xi )]ni;j=1 6= 0:

(1.9)

Unisolvens függvényrendszerrel de…niált lineáris interpolációs feladat megoldása egyértelm½u. A gyakorlatban sokféle unisolvens f'i (x)gni=1 függvényrendszert (interpoláció típust) alkalmaznak. 6

INTERPOLÁCIÓ

A lineáris interpoláció stabilitása Tegyük fel, hogy az yi = f (xi ) függvényértékek hibával terheltek, azaz helyettük az yi + yi (i = 1; 2; : : : ; n) perturbált értékek ismertek. Ekkor a Ba = y lineáris egyenletrendszer helyett a B (a + a) = y + y perturbált egyenletrendszert oldjuk meg, ahol a = [ a1 ; a2 ; : : : ; an ]T és y = [ y1 ; y2 ; : : : ; yn ]T hibavektorok. Igazolható, hogy y 6= 0 esetén az a interpolációs együttható vektor relatív hibájára fennáll a k ak k yk cond(B) (1.10) kak kyk egyenl½otlenség, ahol ahol cond(B) = kBk kB 1 k a B mátrix ún. kondíciószáma. P A perturbáció miatt a h (x) helyett a e h (x) = ni=1 (ai + ai ) 'i (x) értéket számoljuk. A két mennyiség eltérésére fenáll, hogy h (x)

e h (x)

m X i=1

j ai j j'i (x)j

max j'i (x)j k ak i

max j'i (x)j cond (B) kak i

k yk ; kyk

ami jelzi, hogy nagy kondiciószám esetén probléma lehet az elérhet½o pontossággal. A lineáris interpolációs feladat mátrixa sok esetben rosszul kondicionált. Ilyenkor speciális technikákat vagy más típusú interpolációt kell használni.

1.1.1. Lagrange-interpoláció Az egyik legfontosabb interpoláció típus, amelyet '1 (x) = 1; '2 (x) = x; : : : ; 'n (x) = xn

1

függvényrendszer de…niál. Ekkor az interpolációs feladat mátrixa 2 3 1 x1 : : : xn1 1 6 .. 7 V (x1 ; x2 ; : : : xn ) = 4 ... ... . 5 n 1 1 x n : : : xn

(1.11)

(1.12)

az ún. Vandermonde-féle mátrix, amely a

det(V (x1 ; x2 ; : : : xn )) =

Y

(xj

xi )

1 i<j n

A LINEÁRIS INTERPOLÁCIÓ

7

összefüggés és xi 6= xj (i 6= j) miatt nemszinguláris. Tehát a Lagrange-féle interpolációs feladatnak egyértelm½u megoldása van (a f'i (x)gni=1 bázis unisolvens). Tyrtyshnikov (1994) igazolta, hogy tetsz½oleges valós x1 ; : : : ; xn (xi 6= xj ) esetén p cond2 (V (x1 ; x2 ; : : : xn )) 2n 2 = n: (1.13) Ha minden j-re jxj j

1 vagy jxj j

1, akkor

cond2 (V (x1 ; x2 ; : : : xn ))

2n 2 :

(1.14)

Beckermann (2000) igazolta, hogy cond2 (V (x1 ; x2 ; : : : xn ))

p

2 1+

p

n 1

2

p = n + 1:

(1.15)

A Lagrange-féle interpolációs polinom létezését és egyértelm½uségét az általános kereteken belül már beláttuk. A feladat szokásos megfogalmazása a következ½o. Adottak az x1 < x2 < : : : < xn alappontok és az yi = f (xi ) (i = 1; : : : ; n) függvényértékek. Határozzuk meg azt a legfeljebb (n 1)-edfokú p(x) = a0 + a1 x + : : : + an 1 xn

1

(1.16)

polinomot, amelyre teljesül a (1.17)

yi = p(xi ) (i = 1; : : : ; n) interpolációs feltétel. Az interpolációs polinom többféle ekvivalens alakban is felírható. Lagrange-féle el½oállítás. Legyen li (x) =

n Y

x xi k=1;k6=i

xk xk

Különösen fontos a

(1.18)

(i = 1; : : : ; n)

az i-edik Lagrange-féle alappolinom. Ekkor az interpolációs polinom el½oáll p(x) =

n X

(1.19)

yi li (x)

i=1

alakban. Ennek igazolására vegyük észre, hogy li (x) pontosan (n (n 1)-ed fokú, 1; i = j li (xj ) = ij = 0; i 6= j (

ij

1)-ed fokú, p (x) legfeljebb (1.20)

a Kronecker delta jelölés) és p(xj ) =

n X

yi li (xj ) = yj lj (xj ) = yj

(j = 1; : : : ; n):

(1.21)

i=1

8

INTERPOLÁCIÓ

Kérdés: Miért egyértelm½u az interpolációs polinom? Állítás: Ha az f interpolált függvény legfeljebb n 1-ed fokú polinom, akkor f (x)

(1.22)

p (x) ;

azaz a legfeljebb n 1-ed fokú polinomfüggvény Lagrange interpolációja el½oállítja az interpolált polinomot. Bizonyítás: f (x) p (x) legfeljebb n 1-ed fokú polinom, amelynek n különböz½o gyöke van: f (xi ) p (xi ) = 0 (i = 1: : : : ; n). Ez csak akkor lehet, ha f (x) p (x) 0. Ha az alappontokra teljesül, hogy xi = x1 + (i

1) h

(1.23)

(h > 0; i = 1; : : : ; n) ;

akkor ekvidisztans (egyenköz½u) alappontokról (csomópontokról) beszélünk. Az x1 = 1, x2 = 0, x3 = 1 és x4 = 2 ekvidisztans alappontokra támaszkodó harmadfokú Lagrange-féle interpolációs alap polinomokat mutatja a következ½o ábra:

1s t Lagra nge funda m ental pol y nom i al

2th Lagra nge funda m ental pol y nom i al

1.2

1.2

1

1

0.8 0.8 0.6

y

y

0.6 0.4

0.4 0.2 0.2 0

0

-0 .2 -1

-0 .2

-0 .5

0

0.5

1

1.5

-0 .4 -1

2

-0 .5

0

X

0.5

1

1.5

2

1.5

2

X

3rd Lagra nge funda m ental pol y nom i al


1.2

1.2

1

1

0.8 0.8 0.6

y

y

0.6 0.4

0.4 0.2 0.2 0

0

-0 .2

-0 .4 -1

-0 .5

0

0.5 X

1

1.5

2

-0 .2 -1

-0 .5

0

0.5

1

X

Lagrange alappolinomok ekvidisztans alappontok esetén Az x1 = 1, x2 = 0:25, x3 = 1:25 és x4 = 2 nem egyenköz½u alappontokra támaszkodó harmadfokú Lagrange-féle interpolációs alap polinomok pedig a következ½oképpen néznek ki: A LINEÁRIS INTERPOLÁCIÓ

9

1s t Lagra nge funda m ental pol y nom i al


1

1

0.8

0.8

0.6

0.6

y

1.2

y

1.2

0.4

0.4

0.2

0.2

0

0

-0 .2 -1

-0 .2 -1

-0 .5

0

0.5

1

1.5

2

-0 .5

0

X

0.5

1

1.5

2

1.5

2

X

3rd Lagra nge funda m ental pol y nom i al


1

1

0.8

0.8

0.6

0.6

y

1.2

y

1.2

0.4

0.4

0.2

0.2

0

0

-0 .2 -1

-0 .2 -1

-0 .5

0

0.5

1

1.5

2

-0 .5

X

0

0.5

1

X

Lagrange alappolinomok nem ekvidisztans alappontok esetén Megjegyzések, észrevételek 1. A Lagrange-féle interpolációs alakból láthatjuk, hogy akkor is érvényes, ha az alappontokra nem teljesül az x1 < x2 < < xn feltétel. Ezt a megkötést alapvet½oen kényelmi szempontokból használjuk. 2. A Lagrange interpoláció változatlan formában érvényes a komplex számsíkon a komplex függvények esetén is. Itt értelemszer½uen az xi 6= xj (i 6= j) feltételt kötjük ki az alappontokra. 3. Tegyük fel, hogy a x1 < x2 < < xn < b és x 2 [a; b]. Az [a; b] intervallumot (y 2 [ 1; 1]) leképezéssel. transzformáljuk a [ 1; 1] intervallumba az x = b 2 a y + a+b 2 Legyen 1 t1 < t2 < < tn 1 és xi = b 2 a ti + a+b . Az i-edik Lagrange alappolinom 2 ekkor n Y x li (x) = x j=1 i

=

j6=i n Y

y t j=1 i

Y xj = xj j=1 n

b a y 2 b a t 2 i

+ a+b 2 + a+b 2

b a t 2 j b a t 2 j

+ a+b 2 + a+b 2

j6=i

tj : tj

j6=i

10

INTERPOLÁCIÓ

Tehát az alappolinomok értéke az alappontok és x (illetve y) relatív pozíciójától függ csak.

1.1.2. Trigonometrikus interpoláció Legyen n = 2m + 1 és 0

x1 < x 2 <

(1.24)

< x2m+1 < 2

A trigonometrikus interpolációt a '1 (x) = 1; '2` (x) = sin (`x) ; '2`+1 (x) = cos (`x)

(1.25)

(` = 1; : : : ; m)

függvényrendszer de…niálja. Ennek megfelel½oen a trigonometrikus interpoláció alakja a0 X h (x) = + (a` cos (`x) + b` sin (`x)) : 2 `=1 m

(1.26)

Lemma: A h (x) polinomnak legfeljebb 2m gyöke van a [0; 2 ) intervallumban. Bizonyítás: Tegyük fel, hogy h (x)-nek 2m + 1 gyöke van [0; 2 )-ben, amelyek 0 ; trigonometrikus polinom átírható komplex alakba az

1 ; : : : ; 2m .

A

eìx = cos (`x) + i sin (`x) Euler formula segítségével. Minthogy cos (`x) =

ei`x + e 2

i`x

;

sin (`x) =

ei`x

e 2i

i`x

;

azért a z = eix helyettesítéssel és rendezéssel kapjuk, hogy h (x) =

m X

`= m

c` ei`x =

m X

c` z ` :

`= m

P m+k A h (x) = 0, ha z = ei j (j = 0; 1; : : : ; 2m). A z m h (x) = m polinom legfeljebb 2m`= m c` z rend½u, amelynek legalább 2m + 1 gyöke van. Ez csak az azonosan zérus polinom esetén lehetséges. Azt hogy a fenti trigonometrikus interpolációs feladatnak egy megoldása van, a lemma alapján könnyen igazolhatjuk. Legyenek y1 ; : : : ; y2m+1 tetsz½oleges interpolált értékek. Az interpolációs probléma az a0 , a1 , . . . , am , b1 , . . . , bm ismeretlenekre egy 2m + 1 ismeretlenes lineáris egyenletrendszert de…niál a 3 2 1 cos (x ) : : : cos (mx ) sin (x ) : : : sin (mx ) 1 1 1 1 2 7 6 7 6 6 1 7 cos (x ) : : : cos (mx ) sin (x ) : : : sin (mx ) 2 2 2 2 7 6 2 7 6 .. .. .. .. .. 4 . 5 . . . . 1 cos (x2m+1 ) : : : cos (mx2m+1 ) sin (x2m+1 ) : : : sin (mx2m+1 ) 2 A LINEÁRIS INTERPOLÁCIÓ

11

együttható mátrixszal. Ez a mátrix nem szinguláris. Ha ugyanis az lenne, akkor az y1 = y2 = = y2m+1 = 0 interpolációs feladatra több megoldás is lenne. Azonban az interpolációs feladat bármely megoldását adó h (x) trigonometrikus polinomnak 2m + 1 gyöke lenne, ami ellent mond a lemmának. Tehát a fenti mátrix nemszinguláris és az interpolációs feladatnak 2m+1 pontosan egy megoldása van minden fyi gi=1 érték halmazra. A trigonometrikus interpolációnak is van a Lagrange-féle interpolációs polinomhoz hasonló el½oállítása. A (1.24) feltétel mellett legyen tj (x) =

n Y sin

k=1 k6=j

sin

x xk 2 xj xk 2

(1.27)

(j = 1; : : : ; n) :

Ezekre fennáll, hogy tj (xi ) =

1; 0;

=

ij

ha i = j ha i = 6 j

(1.28)

Megmutatható (lásd pl. Natanszon könyvét), hogy a trigonometrikus intepolációs feladat egyetlen megoldása el½oáll a n X yk tk (x) (1.29) h (x) = k=1

alakban. Ezt az el½oállítást a trigonometrikus interpoláció Gauss formulájának nevezzük. Az xk = 2 (kn 1) ekvidisztans alappontok esetén igazolható, hogy tj (x) =

x xj 2 x x n sin 2 j

sin n

(1.30)

:

A továbbiakban az egyszer½uség kedvéért tegyük fel, hogy az interpolációs alappontok ekvidisztansak (egyenköz½uek) és xk =

2 (k 1) n

Az

ei`xk + e i(n `)xk ei`xk ; sin (`xk ) = 2 el½oállításokat h (x)-be behelyettesítve kapjuk, hogy cos (`xk ) =

a0 X ei`xk + e h (xk ) = + a` 2 2 `=1 m

illetve

12

a0 X + h (xk ) = 2 `=1 m

a`

ib` 2

(1.31)

(k = 1; : : : ; 2m + 1):

i(n `)xk

+ b`

ei`xk +

ei`xk

a` + ib` e 2

e i(n 2i

`)xk

:

e i(n 2i

`)xk

i(n `)xk

;

;

INTERPOLÁCIÓ

ami átírható a h (xk ) =

0

+

2m X

j i !k

(1.32)

j=1

alakba, ahol !k = eixk . Az interpolációs feladat ekkor átmegy a

0

+

2m X

j i !k

= yk

(k = 1; 2; : : : ; 2m + 1)

j=1

lineáris egyenletrendszerbe, amelynek mátrixa a V (!1 ; : : : ; !2m+1 ) Vandermonde mátrix. Minthogy !i 6= !j (i 6= j), a rendszernek egyértelm½u megoldása van (az alapfüggvény rendszer unisolvens). Az (1.32) el½oállítást fázispolinomnak nevezik. Végül megjegyezzük, hogy a trigonometrikus interpolációnak is több változata van (lásd pl. Natanszon könyvét).

1.1.3. Exponenciális interpoláció Az exponenciális interpolációt a 'j (x) = e

jx

(j = 1; : : : ; n;

1

<

2

< ::: <

n)

(1.33)

függvényrendszer de…niálja és alakja u (x) =

m X

aj e

jx

:

(1.34)

j=1

Tegyük fel, hogy az interpolációs pontokra is teljesül, hogy x1 < x 2 <

< xn :

(1.35)

Az yi = u (xi ) (i = 1; 2; : : : ; n) interpolációs feltételb½ol kapjuk a (1.36)

Ba = y egyenletrendszert, ahol B= e

j xi

n i;j=1

:

(1.37)

Ezt a mátrixot általánosított Vandermonde mátrixnak is nevezik. Megmutatható, hogy B nemszinguláris (det (B) 6= 0 igazolását lásd pl. Gantmacher [20] II. kötet p. 99, vagy [21], pp. 441-442). Mi az egyszer½ubb xi = x1 + (i 1) h (h > 0, i = 1; : : : ; n) esetet vizsgáljuk, amelynek megoldása Gaspard Riche de Prony (1755–1839) A LINEÁRIS INTERPOLÁCIÓ

13

munkásságán alapul. Ekkor az interpolációs feltétel átírható az yi = = =

n X

j=1 n X j=1 n X

aj e

j (x1 +(i

aj e

j x1

1)h)

e

jh

i 1

i 1 j j

j=1

alakba, ahol

j

=

je

j x1

és

j

=e

jh

n X

(j = 1; : : : ; n). A kapott

i 1 j j

= yi

(i = 1; : : : ; n)

j=1

egyenletrendszer lineáris, ha a j -k és az xi alappontok ismertek. A rendszer együttható mátrixa V ( 1 ; : : : ; n ) nemszinguláris (det (V ) 6= 0). Ezért pontosan egy ( 1 ; : : : ; n ) megoldása van, amelyb½ol egyszer½uen adódnak a keresett aj együthatók. Ha a j -k nem ismertek, akkor a probléma lényegesen nehezebb mivel egy nemlineáris egyenletrendszert kell megoldani közelít½o módszerekkel. A részleteket illet½oen lásd pld. Hildebrand [24] könyvét. Az exponenciális interpolációt számos alkalmazási területen használják.

1.1.4. Racionális törtfüggvény interpoláció Az interpoláció típust a 'i (x) = 14

1 ai + x

(i = 1; : : : ; n; 0 < a1 < : : : < an )

(1.38) INTERPOLÁCIÓ

függvényrendszer de…niálja, ahol teljesül, hogy x+ai 6= 0, ha x 2 [a; b]. Az interpolációs feladat mátrixa a n 1 C= (1.39) xi + aj i;j=1 Cauchy mátrix, amelyre fennáll, hogy Q det (C) =

Tehát a függvényrendszer unisolvens.

1 i<j n

Q

(xj

1 i;j

xi ) (aj ai ) 6= 0: n (xi + aj )

(1.40)

1.1.5. További interpoláció típusok Az interpolációs feladatot a komplex számsíkon és többdimenziós terekben is vizsgáljuk. Komplex Lagrange interpoláció A komplex számsíkon a Lagrange interpolációs feladat lényegében változtatás nélkül m½uködik. Az interpolációs csomópontokra az x1 < x2 < < xn kikötés helyett értelemszer½uen csak az xi 6= xj (i 6= j) feltételt tudjuk kiróni. Hermite interpoláció A Lagrange interpoláció általánosítása az Hermite-féle interpolációs feladat, amely az interpolációs csomópontokban a deriváltakra is megkötést tartalmaz. A legáltalánosabb Hermite-féle interpolációs feladatot a következ½oképpen fogalmazhatjuk meg: Legyenek fxi gni=1 páronként különböz½o valós vagy komplex számok. Keressük azt a legfeljebb N -ed fokú H (x) polinomot, amelyre a következ½ok teljesülnek: f (k) (x1 ) = y1k = H (k) (x1 ) ; f (k) (x2 ) = y2k = H (k) (x2 ) ; .. .

k = 0; 1; : : : ; m1 k = 0; 1; : : : ; m2

1; 1;

f (k) (xn ) = ynk = H (k) (xn ) ;

k = 0; 1; : : : ; mn

1;

(1.41)

és N = m1 + m2 +

+ mn

1:

(1.42)

Az f függvénynek és deriváltjainak az interpolációs csomópontokban el½oírt fyik g értékeit ismertnek tételezzük fel. A Hermite-féle interpolációs feladatnak van megoldása és pedig pontosan egy. A megoldás konstrukciója megtalálható például Natanszon [38] könyvében. Vegyük észre, hogy a Hermite-féle interpolációs feladat speciális esetként magában foglalja a Lagrange-féle interpolációt (m1 = : : : = mn = 1) és az un. Taylor-polinom is, amennyiben csak egy interpolációs pontunk van (n = 1). A LINEÁRIS INTERPOLÁCIÓ

15

Az Hermite-féle interpolációs feladat fontos speciális esete az m1 = m2 = eset. Legyen f (xi ) = yi és f 0 (xi ) = yi0 (i = 1; 2; : : : ; n), l (x) =

n Y

(x

n Y x lk (x) = x j=1 k

xi ) ;

j=1

= mn = 2

xj : xj

j6=k

Ekkor a feladat megoldása H (x) =

n X

yk 1

k=1

l00 (xk ) (x l0 (xk )

Igazolás: H (x) fokszáma legfeljebb 2n 0

H (x) =

n X

+

xk )

(x) +

n X

0

yk (x

xk ) lk2 (x) :

(1.43)

k=1

1, H (xi ) = yi , l00 (xk ) (x l0 (xk )

l00 (xk ) 2 l (x) + 1 l0 (xk ) k

yk

k=1

n X

lk2

0

xk ) 2lk (x) lk0 (x) +

xk ) lk (x) lk0 (x) ;

yk lk2 (x) + 2 (x

k=1

l00 (xi ) + 2li0 (xi ) + yi0 : 0 l (xi ) Q 0 xj ), l (xi ) = nj=1; j6=i (xi xj ) és

H 0 (xi ) = yi Mivel l0 (x) =

Pn Qn i=1

j=1; j6=i

(x

li (x) =

l0

l (x) ; (xi ) (x xi )

az i-edik Lagrange alappolinom deriváltjára kapjuk, hogy l0 (x) (x xi ) l (x) : l0 (xi ) (x xi )2

li0 (x) =

A L’Hospital szabály alkalmazásával kapjuk, hogy li0 (xi ) = lim li0 (x) = lim x!xi

x!xi

l00 (xi ) l00 (x) (x xi ) + l0 (x) l0 (x) = ; 2l0 (xi ) (x xi ) 2l0 (xi )

amb½ol, következik, hogy H 0 (xi ) = yi0 . A most vizsgált Hermite interpoláció speciális esete a Fejér Lipót-féle (un. Hermite-Fejér) interpoláció, amely olyan, legfeljebb 2n 1 rend½u H2n 1 (x) polinom, amely kielégíti a H2n

1

(xk ) = f (xk ) ;

0 H2n

1

(xk ) = 0

(i = 1; : : : ; n)

feltételeket. A fenti (1.43) el½oállítás alapján H2n

1 (x) =

n X k=1

16

yk 1

l00 (xk ) (x l0 (xk )

xk ) lk2 (x) :

(1.44)

INTERPOLÁCIÓ

Birkho¤ interpoláció Az Hermite-féle interpolációhoz hasonló a Birkho¤, vagy hézagos (lacunary) interpoláció, amely adott ci;k adatokhoz olyan legfeljebb n-ed fokú Pn polinomot keres, amelyre teljesül, hogy Pn(k) (xi ) = ci;k

(n + 1 egyenlet) :

(1.45)

Az Hermite interpoláció esetén minden egyes xi csomópont esetén az el½oírt deriváltak egy hézagmentes 0; 1; : : : ; mi 1 sorozatot alkotnak. A Birkho¤-féle esetben az el½oírt deriváltak sorozam tában lehetnek hézagok. Itt de…niálnak egy un. E = [ei;k ]n; i=1; k=0 interpolációs mátrixot, ahol ei;k = 1, ha az (i; k) pár szerepel a (1.45) feltételek között és ei;k = 0, ha nem. Itt a nagy kérdés az, hogy milyen E mátrixok esetén van megoldás, és mikor nem. A Birkho¤-interpolációval itt nem foglalkozunk, de megjegyezzük, hogy bonyolult elmélete és számos esetben fontos alkalmazásai vannak (lásd pl. [33]).

1.1.6. Többdimenziós interpoláció Az interpolációs feladatot többdimenziós terekben vizsgáljuk. A többváltozós esetben azonban lényeges nehézségek vannak, amit a következ½o két példa és Haar Alfréd eredménye is mutat. Példa: Tekintsük az f (x; y) = x2 függvényt és interpoláljuk a (0; 0), (0; 2), ( 1; 1) és (1; 1) pontokra támaszkodó p (x; y) = a + bx + cy + dxy alakú kétváltozós polinommal. Az alappontokban felírva az interpolációs feltételt, kapjuk a következ½o lineáris egyenletrendszert: p (0; 0) = p (0; 2) = p ( 1; 1) = p (1; 1) =

a a + 2c a b+c d a+b+c+d

=0 =0 =1 =1

Az els½o két egyenletb½ol kapjuk, hogy a = c = 0. Az utolsó két egyenletb½ol kapjuk, hogy b + d = 1 és b + d = 1, ami ellentmondás. Tehát a feladatnak nincs megoldása. Példa: Legyen most f (x; y) = x3 és interpoláljuk a (0; 0), (0; 2), ( 1; 1) és (1; 1) pontokra támaszkodó p (x; y) = a + bx + cy + dxy alakú kétváltozós polinommal. Ekkor az interpolációs egyenletrendszer p (0; 0) = a =0 p (0; 2) = a + 2c =0 p ( 1; 1) = a b + c d = 1 p (1; 1) = a + b + c + d = 1: Ennek végtelen sok megoldása van, mert a b + d = 1 egyenletre redukálódik. Tehát a p (x; y) = (1

d) x + dxy

függvények bármelyike kielégíti az interpolációs feladatot. Az x3 és a 0:5x + 0:5xy függvényeket mutatja a következ½o ábra: A LINEÁRIS INTERPOLÁCIÓ

17

1.5 1.0 0.5

z

0.0 -0.5 -1.0 -1.5 0.0

-1.0 0.5

-0.5 1.0

y

0.0 1.5

0.5 2.0

x

1.0

Legyen '1 ; : : : ; 'n az S ponthalmazon értelmezett függvény, x1 ; : : : ; xn 2 S tetsz½oleges egymástól páronként különböz½o pontok. A lineáris interpolációs feladat yi = f (xi ) =

n X

aj 'j (xi ) ;

i = 1; : : : ; n;

(1.46)

j=1

akkor és csak akkor oldható meg ("tetsz½oleges" f és fxi gni=1 esetén), ha det ['j (xi )]ni;j=1 6= 0:

(1.47)

De…níció: Tegyük fel, hogy a '1 ; : : : ; 'n függvények az S ponthalmazon értelmezett valós függvények. A f'i gni=1 függvényrendszert unisolvens az S halmazon, ha minden x1 ; : : : ; xn 2 S egymástól páronként különböz½o pont esetén fennáll, hogy det ['j (xi )]ni;j=1 6= 0:

(1.48)

Példa: Az f1; x2 g rendszer unisolvens [0; 1]-en, de nem az [ 1; 1]-en. Egyváltozós esetben nagyon sok unisolvens (vagy Csebisev) rendszer létezik. A többváltozós esetben azonban nem ez a helyzet, amint azt Haar Alfréd következ½o eredménye is mutatja. Tétel: Legyen S Rn és n 2. Tegyük fel, hogy az S halmaznak van egy p bels½o pontja. Ha '1 ; '2 ; : : : ; 'n az S halmazon értelmezett és folytonos függvény p egy környezetében, akkor ezek nem alkothatnak unisolvens függvényrendszert. Bizonyítás: Legyen U S egy p középpontú gömb, amelynek olyan kicsi a sugara, hogy a 'i függvények folytonosak U -ban. Válasszunk ki n páronként különböz½o p1 ; p2 ; : : : ; pn 2 U pontot. Tegyük fel, hogy det ['j (pi )]ni;j=1 6= 0 (ellenkez½o esetben a rendszer nem unisolvens). Tartsuk a 18

INTERPOLÁCIÓ

p3 ; p4 ; : : : ; pn pontot …xen és cseréljük fel egymással a p1 és p2 pontokat. Minthogy az U dimenziója legalább 2, a két pont felcserélését meg tudjuk úgy oldani, hogy a mozgatáskor p1 és p2 sem egymással, sem a többi ponttal nem érintkezik. A p1 és p2 pont felcserélése a determináns két sorának felcserélését okozza, ami a determináns el½ojelének ellenkez½ojére váltását jelenti. A pontok folytonos mozgatása miatt a determináns is folytonos és ezért a Bolzano tétel szerint fel kell, hogy vegye a 0 értéket. A Haar tétel ellenére, számos speciális és az alkalmazásokban fontos szerepet betölt½o többváltozós interpoláció típus létezik. Ezeknek gazdag irodalma van. Itt most két speciális megoldást ismertetünk röviden. Ha az interpolációs alappontok speciális módon helyezkednek el, akkor az egyváltozós interpoláció feladatát könnyen kiterjeszthetjük. Legyen f : R2 ! R tipusú függvény, f(xi ; yk ) : 1 i n, 1 k mg R2 az interpolációs pontok halmaza, x1 < x 2 < < x n ; y1 < y 2 < < ym ; yik = f (xi ; yk ) (i = 1; : : : ; n, k = 1; : : : ; m) pedig az interpolációs pontokban megadott függvényértékek. Az interpolációs alappontok egy szabályos rácsot alkotnak a síkon. Az interpolációs feladat olyan legfeljebb n + m 2-ed fokú kétváltozós p (x; y) polinom megadása, amelyre teljesül, hogy f (xi ; yk ) = p (xi ; yk ) (i = 1; : : : ; n; k = 1; : : : ; m): (1.49) Jelölje aj (x) az fxi gni=1 alappontokhoz, bj (y) pedig az fyk gm k=1 alappontokhoz tartozó j-edik egyváltozós Lagrange-féle alappolinomot! Ekkor az interpolációs feladat megoldása felírható a következ½o un. tenzorszorzat alakban: p (x; y) =

n X m X

f (xi ; yk ) ai (x) bk (y) :

(1.50)

i=1 k=1

Minthogy ai (x) foka n 1, bk (y) foka m 1, a p (x; y) foka legfeljebb n + m Másrészt az ai (xj ) = ij és bk (y` ) = k` összefüggés miatt teljesül, hogy p (xj ; y` ) =

n X m X

2 lehet.

f (xi ; yk ) ai (xj ) bk (y` ) = f (xj ; y` ) :

i=1 k=1

A radiális bázisfüggvény interpoláció egy tipikusan 20. századi konstrukció a többváltozós interpolációs feladat egyfajta megoldására. Legyen az Rd , d 1 és f : ! R. Legyen X = fxi gni=1 egymástól páronként különböz½o pontok halmaza. Ha n 2, d 2 és legalább egy bels½o pontot tartalmaz, akkor Haar tétele szerint nincs olyan n dimenziós folytonos függvény halmaz, amely egyértelm½u interpolációs függvényt állít el½o (tartalmaz) minden f és minden a feltételnek megfelel½o - X ponthalmaz esetén. Ennek következtében az interpolációs függvényeknek az X halmaztól kell függeni (mint pl. az el½oz½o tenzorszorzat esetben is). Legyen : [0; 1) ! R egy rögzített egyváltozós függvény. Az f függvényt interpoláló függvényt n X sf (x) = kx xj k2 (1.51) j j=1

A LINEÁRIS INTERPOLÁCIÓ

19

alakban keressük. Az

1; : : : ;

sf (xk ) =

együtthatókat az

n

n X

kxk

j

j=1

xj k2 = f (xk )

(1.52)

k = 1; : : : ; n

intepolációs feltételekb½ol (lineáris egyenletrendszerb½ol) lehet meghatározni, feltéve, hogy az 2

6 A = 4 ...

x1 k2 )

(kx1

..

.

.. .

x1 k2 )

(kxn

xn k2 )

(kx1

xn k2 )

(kxn

3 7 5

(1.53)

szimmetrikus együttható mátrix nemszinguláris. p Micchelli (1986) igazolta, hogy a (r) = 1 + r2 (és sok más) függvény esetén B nemszinguláris. Ezt az eredményt kés½obb újabb függvényekre is igazolták. Egy sor függvényre a fenti interpolációs függvényt - különféle okokból - kiegészítik polinomokkal. Jelölje Pqd a d változós, legfeljebb q fokú valós polinomok halmazát (alterét) és tegyük fel, hogy p1 ; : : : ; pQ ezek bázisa. Ekkor a módosított interpolációs függvény

sf (x) =

n X

Q X

kxk

x j k2 +

(xj ) = 0;

1

`

=

y 0

j

j=1

` p`

(1.54)

(x)

`=1

amelyhez hozzáteszik az n X

j p`

(1.55)

Q

j=1

mellékfeltételeket. Az interpolációs feltételekb½ol az A P PT 0

speciális szerkezet½u lineáris egyenletrendszer adódik, ahol y = [f (x1 ) ; : : : ; f (xn )]T és 2

p1 (x1 ) 6 .. T ... P =4 . pQ (x1 )

(1.56) =[

1; : : :

3 p1 (xn ) 7 .. 5: . pQ (xn )

T n] ,

= [ 1;

2; : : : ;

Q ],

(1.57)

amelynek megoldhatóságával itt nem foglalkozunk és az irodalomra utalunk (pl. Buhmann [6] , Wendland [61]). 20

INTERPOLÁCIÓ

1.2. A Lagrange-féle interpoláció hibája Adottak az x1 < x2 < : : : < xn alappontok és az yi = f (xi ) (i = 1; : : : ; n) függvényértékek. Legyen n Y x xk li (x) = (i = 1; : : : ; n) (1.58) xi xk k=1;k6=i és

p(x) =

n X

(1.59)

yi li (x):

i=1

A Lagrange-féle interpolációs polinom hibájára vonatkozik a következ½o Tétel (Cauchy). Ha f 2 C n [a; b], [x1 ; xn ] [a; b] és x 2 [a; b], akkor f (x)

p(x) =

f (n) ( x ) (x n!

x1 )(x

x2 )

(x

xn );

(1.60)

ahol x = (x) az x és az x1 ; xn pontok által kifeszített intervallumban van. Bizonyítás. Ha van i; hogy x = xi , akkor állításunk triviális. Egyébként legyen l(x) = (x x1 )(x x2 ) : : : (x xn ) és tekintsük a következ½o segédfüggvényt: W (t) = f (t)

p(t)

[f (x)

p(x)]

l(t) : l(x)

(1.61)

A W (t) 2 C n [a; b] függvénynek van n + 1 gyökhelye: x; x1 ; : : : ; xn . A Rolle–tétel miatt W (t) bármely két gyökhelye között a W 0 (t) deriváltfüggvénynek zérushelye van. Ezért W 0 (t)-nek legalább n zérushelye van. Hasonlóképpen okoskodva belátható, hogy W 00 (t)-nek legalább n 1, W (3) (t)-nek legalább n 2 zérushelye van, és így tovább. Végül W (n) (t)-nek is van legalább egy zérushelye, amit jelöljön x . Minthogy p(n) (t) 0 és l(n) (t) n!, azért W (n) ( x ) = f (n) ( x )

[f (x)

p(x)]

n! = 0; l(x)

(1.62)

ahonnan átrendezéssel kapjuk a tétel állítását. Következmény. Ha f (n) (x) Mn ( x 2 [a; b]), akkor jf (x)

p(x)j

Mn (b n!

a)n

(x 2 [a; b]) :

(1.63)

Konkrét n esetén széls½oértékszámítással élesebb becslés is levezethet½o. Példa. Hány ekvidisztáns alappontban kell megadnunk a sin x függvény táblázatát a 0; 2 intervallumon ahhoz, hogy a közbüls½o pontokban lineáris Lagrange-interpolációt használva az elkövetett hiba legfeljebb " = 10 4 legyen? Legyen h = xi+1 xi = = (2n) és Cauchytétel következménye alapján keressünk olyan h-t keresünk, amelyre M2 h2 =2 10 4 : Mivel A LAGRANGE-FÉLE INTERPOLÁCIÓ HIBÁJA

21

ph 2

(sin x)00 = sin x; M2 = 1. A következik. Ha a hibakorlátot az jf (x)

=

p

M2 max j(x 2

p(x)j

10

2(2n)

2

xi )(x

becslésb½ol közvetlenül vezetjük le, akkor j(x muma h2 =4, és ekkor az élesebb,

egyenl½otlenségb½ol n >

xi+1 )j

xi ) (x

100 p 2 2

111:07

(x 2 (xi ; xi+1 ))

xi+1 )j = y (h

M2 h2 jf (x) p(x)j 8 h p hibabecslést kapjuk. Ez alapján kapjuk, hogy 2 2 = 2p2(2n) 55:536.

y) (0 < y < h) maxi-

(1.64) 10 2 , ahonnan n >

100 p 4 2

Példa. Közelítsük másodfokú Lagrange interpolációval az f (x) = cos( 2 x) függvényt a [ 1; 1]ben az x1 = 1; x2 = 0; x3 = 1 pontokra támaszkodva! Minthogy f (x1 ) = f (x3 ) = 0 és 1) = 1 x2 és a közelítés hibája f (x2 ) = 1, p (x) = 1 (x+1)(x (0+1)(0 1) jf (x)

p(x)j

M3 max j(x + 1)x(x 3! 1 x 1

1)j ;

ahol M3 = max-1 x 1 jf 000 (x)j = 3 =8: Az j(x + 1)x(x 1)j függvény páros, ezért p p elég csak a [0; 1]-en nézni a maximumát. Ezt pedig az x = 1= 3 pontban éri el és értéke 92 3. Tehát 2p 3 8 6 9 3

jf (x)

p(x)j

0:248 63:

A helyzet azonban ennél jobb, amint azt a következ½o ábra is mutatja: cos(pi*x/2) fuggveny Lagrange-interpolacio hibaja 0

-0.01

y

-0.02

-0.03

-0.04

-0.05

-0.06

22

-1

-0.8

-0.6

-0.4

-0.2

0 X

0.2

0.4

0.6

0.8

1

INTERPOLÁCIÓ

Q Az l (x) = ni=1 (x xi ) polinom l0 (x) deriváltjának pontosan n 1 gyöke van az (xi 1 ; xi ) intervallumokban (i = 2; : : : ; n), amelyek egyúttal jl (x)j helyi maximum pontjai. Tegyük fel, hogy a = x1 , xi = x1 +(i 1) h (i = 2; : : : ; n 1), xn = b és h = (b a) = (n 1). Ekkor a következ½ok igazak: (i) jl (x)j az intervallum (a + b) =2 közepére nézve szimmetrikus; (ii) jl (x

h)j > jl (x)j minden x < (a + b) =2, x 6= xi esetén.

Az (i) állítás igazolásához elég meggondolnunk, hogy jl (x)j az x pontnak az xi alappontoktól vett távolságainak szorzata, az x = a+b + t pont xi pontoktól vett távolságainak halmaza 2 a+b megegyezik az x = 2 t pont xi pontoktól vett távolságainak halmazával. Az (ii) esetben jl (x

h)j =

jl (x)j jx jx aj

b

hj > jl (x)j ;

mert x < (a + b) =2 esetén jx b hj > (b a) =2 > jx aj. Következmény: Az n = 2 esetben az jl (x)j-nek egy abszolut maximuma van az x = (a + b) =2 esetben. Az n 3 esetben jl (x)j-nek két - az (a + b) =2 pontra szimmetrikus - abszolut maximum helye van az (a; a + h) és (b h; b) intervallumokban. Az abszolut minimumokat befoglaló intervallumok hossza tovább csökkenthet½o h=2-re (A.Pica, 2004). Legyen most [a; b] = [ 1; 1] és tekintsük a Tn (x) = cos (n arccos x)

(1.65)

függvényt, amely az ún. n-edik Csebisev-polinom. T0 (x) = 1, T1 (x) = x és Tk+1 (x) = 2Tk (x) x

Tk

1

(x) :

(1.66)

A Tn (x) polinom gyökei a [ 1; 1] intervallumba esnek. Nevezetesen xj = cos

2j 1 2n

(j = 1; : : : ; n) :

(1.67)

A rekurzió alapján Tn (x) f½oegyütthatója 2n 1 (n 1). Ezért Tn (x) = 2n 1 (x x1 ) (x xn ). Ha Tn (x) gyökeit választjuk a Lagrange interpoláció alappontjainak (Csebisev alappontok), akkor l (x) = 2 (n 1) Tn (x) : (1.68) Mivel max jTn (x)j = 1, max jl (x)j = 2 (n 1) . Igazolható, hogy ennél jobb eredményt elérni nem lehet az x1 ; : : : ; xn pontok semmilyen más elhelyezése esetén sem. Transzformáljuk most a Csebisev alappontokat tetsz½oleges [a; b] intervallumba: a+b a b + cos 2 2

2j 1 2n

A LAGRANGE-FÉLE INTERPOLÁCIÓ HIBÁJA

(j = 1; : : : ; n) :

(1.69) 23

Ekkor max jl (x)j = 2

(n 1)

b a n 2

jf (x)

=2

b a n 4

p(x)j

2

és az interpoláció hibája

Mn b a n ( ) n! 4

(x 2 [a; b]) ;

(1.70)

ami lényegesen jobb mint a korábbi (1.63) becslés. A komplex számokon értelmezett Lagrange-interpoláció esetén f : C ! C, fzi gni=1 p (z) =

n X

(z 2 C) ;

f (zi ) li (z)

i=1

ahol li (z) =

n Y z z j=1 i

zj zj

(i = 1; : : : ; n):

C, (1.71)

(1.72)

j6=i

Ekkor a Cauchy-féle hiba kifejezés helyett a következ½ot használhatjuk. Tétel (Hermite): Tegyük fel, hogy f : C ! C analitikus a T C zárt és összefügg½o tartományon, CT T a T belsejében fekv½o egyszer½u, zárt és rekti…kálható görbe, amelynek a z1 ; z2 ; : : : ; zn egymástól páronként különböz½o interpolációs alappontok a belsejében ( int(CT )) fekszenek. Ekkor Z l (z) f (t) 1 dt (z 2 int (CT )) ; (1.73) f (z) p (z) = 2 i CT l (t) t z ahol l (z) =

n Y

(z

zj ) :

(1.74)

j=1

1.3. Az Hermite-interpoláció hibája A (1.41)-(1.42) Hermite-féle interpoláció esetén a Cauchy-féle hiba kifejezéshez hasonló eredményt lehet igazolni. Tétel: Tegyük fel, hogy f 2 C N +1 [a; b], [x1 ; xn ] [a; b] és x 2 [a; b]. Ekkor f (x)

f (N +1) ( x ) (x x1 )m1 (x x2 )m2 (x xn )mn ; n! = (x) az x és az x1 ; xn pontok által kifeszített intervallumban van. f (x)

ahol

24

x

H (x) =

H(x) =

INTERPOLÁCIÓ

1.4. A Lagrange interpoláció konvergenciája A Lagrange interpoláció hibájára vonatkozó Cauchy-féle tétel következményeként kaptuk, hogy a x1 < x 2 < < xn b, f 2 C n [a; b] és f (n) (x) Mn (x 2 [a; b]) esetén jf (x)

Mn (b n!

p (x)j

a)n :

Ha feltételezzük, hogy f végtelen sokszor di¤erenciálható az [a; b] intervallumon és minden n esetén f (n) (x) M (x 2 [a; b]) (1.75) teljesül, akkor

Az n! s

p

jf (x)

M (b n!

p (x)j

a)n :

2 n (n=e)n Stirling-formula alapján a jobboldalra teljesül, hogy M (b n!

M M (b a)n p a)n s p n = 2 n (n=e) 2 n

(b

a) e n

n

!0

(n ! +1) :

Tehát ekkor az f függvényt az interpolációs polinom tetsz½oleges el½oírt pontossággal megközelíti az egész [a; b] intervallumon, ha n elég nagy (más szóval a "konvergencia" egyenletes). Tekintsük az [a; b] intervallumbeli interpolációs pontoknak az alábbi végtelen alsó háromszög elrendezését (1) x1 (2) (2) x1 x2 (3) (3) (3) X: x1 x2 x3 (1.76) .. . (n)

(n)

x1 .. .

x2

(n)

:::

xn

ahol minden n = 1; 2; : : : indexre fennáll, hogy a

(n)

(n)

< x(n) n

x1 < x 2 <

b:

(1.77)

Az adott f függvényt interpoláljuk az X i-edik sorának alappontjain. Az eredményt jelölje pi (x) =

i X

(i)

f xj

(i)

lj (x) ;

(1.78)

j=1

ahol (i) lj

(x) =

i Y

k=1

x (i)

xj

A LAGRANGE INTERPOLÁCIÓ KONVERGENCIÁJA

(i)

xk

:

(1.79)

xk 25

De…niáljuk a C [a; b] függénytéren a következ½o Csebisev, vagy maximum normát: kgkC = max jg (x)j

(g 2 C [a; b]) :

a x b

(1.80)

Azt vizsgáljuk, hogy adott f függvényhez van-e olyan X alappont sorozat, hogy a hozzárendelt p0 (x) ; p1 (x) ; : : : ; pn (x) ; : : : interpolációs polinom sorozatra teljesül-e kpn f kC ! 0 (n ! 1). Lebesgue idevágó eredményének kimondásához szükségünk van két további fogalomra. A k X (k) lj (x) (1.81) k (X; x) = j=1

függvényt Lebesgue függvénynek, a k

(X) = max

k

a x b

(1.82)

(X; x)

függvényt pedig Lebesgue konstansnak nevezzük. Legyen Pn a legfeljebb n-edfokú valós polinomok halmaza. Kés½obb igazoljuk, hogy minden f 2 C [a; b] esetén létezik olyan p (x) 2 Pn polinom (f legjobb egyenletes polinom approximációja), amelyre fennáll, hogy En (f ) = kf

p kC

kf

pkC ;

p (x) 2 Pn :

(1.83)

Az En (f ) mennyiség az f függvény legjobb n-ed fokú polinom közelítésének hibája a Csebisev normában. Tétel (Lebesgue): kf pn kC (1 + n (X)) En 1 (f ) : (1.84) Bizonyítás: Jelölje qn 2 Pn 1 az f (x)-et legjobban approximáló polinomot, legyen x 2 [a; b] és tekintsük az alábbi azonosságot: f (x)

pn (x) = f (x)

qn (x) + qn (x)

pn (x) ;

ahonnan jf (x)

pn (x)j

jf (x)

qn (x)j + jqn (x)

pn (x)j

következik. Felhasználjuk, hogy pn (x) =

n X

(n)

f xj

(n)

lj (x)

j=1

és qn (x) =

n X

(n)

q xj

(n)

lj (x) :

j=1

26

INTERPOLÁCIÓ

Ezért jqn (x)

pn (x)j =

n X

j=1 n X

(n)

q xj

(n)

(n)

f xj

(n)

q xj

(n)

lj (x) (n)

f xj

lj (x)

j=1

En

1

(f )

n

(X; x)

és jf (x)

pn (x)j

(1 + (1 +

(X; x)) En 1 (f ) n (X)) En 1 (f ) ;

n

amivel az állítást igazoltuk. Weierstrass eredménye alapján En (f ) ! 0 (lásd kés½obbi fejezetben). Ezért az utolsó két becslésb½ol láthatjuk, hogy n (X; x) En 1 (f ) ! 0 esetén pn (x) ! f (x), és n (X) En 1 (f ) ! 0 esetén kf pn k ! 0. A tétel alapján arra következtethetünk, hogy n (X), illetve n (X) En 1 (f ) viselkedése befolyásolja az interpoláció sorozat konvergenciáját. A következ½okben a n (X) Lebesgue konstans viselkedését vizsgáljuk. A n (X;hx) Lebesgue folytonos az legfeljebb n 1-ed fokú i [a; h b] intervallumon, i i h i h függvény (n) (n) (n) (n) (n) (n) polinom az a; x1 , x1 ; x2 ,: : :, xn 1 ; xn , xn ; b részintervallumokon. További tulajdonságai: i = 1; : : : ; n; (1.85) n (X; xi ) = 1; n

(X; x)

x 2 [a; b] :

1;

(1.86)

Az els½o tulajdonság triviális. A második tulajdonság igazolása: az 1 = azonosságból kapjuk, hogy 1=

n X

(n)

lj (x)

j=1

n X

(n)

lj (x) =

n

Pn

(n) j=1 lj

(x) (x 2 [a; b])

(X; x) :

j=1

(n)

(n)

Minthogy az lj (x) alappolinomok értéke csak x és az xi alappontok relatív poziciójától függ, a továbbiakban feltehetjük, hogy [a; b] = [ 1; 1]. Tekintsük a n (X; x) Lebesgue függvényt a [ 1; 1] intervallumon néhány n értékre az (n)

E : xi

=

1+

2 (i n

1) 1

(i = 1; 2; : : : ; n)

ekvidisztans felosztás sorozaton. A LAGRANGE INTERPOLÁCIÓ KONVERGENCIÁJA

27

10

Lebesguefunction

4

y

n=5 n=10 n=20

10

3

10

2

10

1

10

0

-1

-0.8

-0.6

-0.4

-0.2

0 X

0.2

0.4

0.6

0.8

1

Lebesgue függvény ekvidisztans felosztáson Az ábra az y tengely irányában logaritmikus. Meg…gyelhet½o a n (E; x) extrém növekedése, illetve nem túl nagy n értékre a Lagrange-féle interpoláció numerikus pontatlansága (az intervallum széleken a lokális minimumok nem érik el a tényleges 1 értéket). A Lebesgue függvény a nem ekvidisztans (n)

T : xi

=

cos

(2i

1) 2n

(1.87)

(i = 1; 2; : : : ; n)

un. Csebisev alappontokon (a Tn (x) Csebisev polinom gyökein) lényegesen kevésbé n½o, amint azt a következ½o ábra is mutatja. Lebesguefunction

3

n=5 n=10 n=20

2.8

2.6

2.4

y

2.2

2

1.8

1.6

1.4

1.2

1 -1

28

-0.8

-0.6

-0.4

-0.2

0 X

0.2

0.4

0.6

0.8

1

INTERPOLÁCIÓ

Lebesgue függvény Csebisev pontokon A Lebesgue konstans értékét sok szerz½o vizsgálta. A teljesség igénye nélkül felsorolunk néhány fontos idevágó eredményt: Faber (1914) :

n

(X) >

log pn 8

Erd½os (1961):

n

(X) >

2 log n

Bernstein (1918): Berman (1963): Turetskii (1940):

n n

(T ) <

(T ) < n

(E)

2

(n

2);

+ c, ahol c konstans;

4

log n + 8; p log n + 4 2;

2n en log n

(n ! 1).

Az eredményekb½ol látható, hogy a Csebisev alappontok esetén a Lebesgue konstans viselkedése közel optimális. Optimálisnak azt az esetet tekintjük, amikor a Lebesgue konstans minimális. Legyen 1 x1 < < xn 1 egy tetsz½oleges felosztás. Bernstein 1931-ben azt sejtette, hogy a max

1 x 1

m X k=1

jlk (x)j

(1.88)

P Lebesgue konstans értéke akkor minimális, ha a m k=1 jlk (x)j Lebesgue függvény maximumai egyenl½ok. Erd½os Pál azt kés½obb azt sejtette, hogy a helyi maximumok legkisebbike akkor a legnagyobb, amikor ezek a maximumok egyenl½ok. A Bernstein-Erd½os sejtést kés½obb több lépésben Kilgore (1977, 1978), Kilgore és Cheney (1976), valamint De Boor és Pinkus (1978) igazolták. Jackson igazolta, hogy amennyiben f 2 C [a; b] k-szor folytonosan di¤erenciálható, akkor Ak (b a)k ck (n) ; nk

En (f )

(1.89)

ahol Ak csak k-tól függ½o állandó és ck (n) ! 0, ha n ! 1. Ha ezt az eredményt kombináljuk a Lebesgue-tétellel és a fenti Lebesgue konstans becslésekkel, akkor kapjuk, hogy a T Csebisev alappontokon de…niált interpolációs sorozat esetén kf

pn kC

(1 +

(f ) p Ak (b a)k 2 ck (n) : 1 + log n + 4 2 nk n

(T )) En

1

(1.90) (1.91)

Mivel k 1 esetén log n=nk ! 0, igazoltuk, hogy a Csebisev alappontokon de…niált interpolációs eljárás már egyszer folytonosan di¤erenciálható függvények esetén is egyenletesen konvergens. A LAGRANGE INTERPOLÁCIÓ KONVERGENCIÁJA

29

1.4.1. Negatív eredmények Az interpolációs eljárás konvergenciájára vonatkozó Lebesgue-féle tétel csak elégséges feltételt ad. A tényleges helyzet ennél lényegesen bonyolultabb, amint azt a sok idevágó eredményb½ol idézett alábbi eredmények is mutatnak. Tétel (Bernstein): Az f (x) = jxj függvényhez tartozó, az (n)

E : xi

=

1+

2 (i n

1) 1

(i = 1; 2; : : : ; n)

ekvidisztans felosztás sorozaton de…niált fpn (x)g1 n=1 Lagrange interpolációs polinomsorozat a [ 1; 1] szakasz minden olyan pontjában divergál, amely különbözik a 0, 1, 1 pontoktól. A következ½o ábra az jxj függvényt és a Lagrange interpolációs polinomot mutatja be néhány n értékre. abs(x) fuggveny Lagrange-interpolacioja 1.5

1

0.5

y

0

-0.5

-1

abs(x) n=5 n=10 n=20

-1.5

-2

-2.5

-1

-0.8

-0.6

-0.4

-0.2

0 X

0.2

0.4

0.6

0.8

1

A Csebisev alappontok esetén a Lebesgue konstans növekedése log n nagyságrend½u, ami közel optimális. Grünwald Géza és Marcinkiewicz egymástól függetlenül igazolta a következ½o eredményt. Tétel: Létezik olyan f 2 C [ 1; 1] függvény, hogy a T Csebisev pontokon de…niált fpn (x)gm i=1 Lagrange interpolációs polinomsorozat divergál a ( 1; 1) intervallum valamennyi pontjában. Érdemes megjegyezni, hogy más interpolációs eljárások esetén ez a szituáció nem feltétlenül lép fel. Tétel (Fejér): Legyen f 2 C [ 1; 1] és tekintsük a T Csebisev pontokon de…niált Hermite– Fejér féle H2n 1 (x) interpoláció sorozatot. Ekkor teljesül, hogy H2n 1 (x) ! f (x) egyenletesen a [ 1; 1] intervallumban. Az interpolációs eljárások konvergenciájával kapcsolatos nehézségeket jól jellemzi a következ½o Runge-féle példa is. 30

INTERPOLÁCIÓ

1 Ábrázoljuk az f (x) = 1+x 5; 5] intervallumon és n különböz½o értékeire (n = 2 függvényt a [ 5; 10; 20; : : :) az f (x) függvényhez és az xi = 5 + 10 ni 11 (i = 1; : : : ; n) alappontokhoz tartozó Lagrange-féle interpolációs polinomot! Runge fuggveny Lagrange-interpolacioja 9 Runge n=5 n=10 n=20

8

7

6

5

y

4

3

2

1

0

-1 -5

-4

-3

-2

-1

0 X

1

2

3

4

5

Az ábrán láthatjuk, hogy az intervallum szélein divergencia lép fel (lásd pl. de Villiers [16], Example 3.1.3). Ha most ugyanezt megcsináljuk a [ 3; 3] intervallumon, akkor a következ½o ábrához jutunk. Runge fuggveny Lagrange-interpolacioja 1.2 Runge n=5 n=10 n=20

1

0.8

y

0.6

0.4

0.2

0

-0.2

-3

-2

-1

0 X

1

2

3

Itt már az eltérések sokkal kisebbek és valójában az interpoláció konvergál az jxj 3:63 intervallumon. Ha most a [ 5; 5] intervallumon a Csebisev pontokat vesszük alapul (pontosabban ezek lineáris transzformáltjait a [ 5; 5]-be), akkor a következ½o képet kapjuk. A LAGRANGE INTERPOLÁCIÓ KONVERGENCIÁJA

31

Runge fuggveny Lagrange-interpolacioja 1.2

1

Runge n=5 n=10 n=20

0.8

y

0.6

0.4

0.2

0

-0.2

-5

-4

-3

-2

-1

0 X

1

2

3

4

5

Ez már lényegesen jobb képet mutat, és valójában az interpoláció a Csebisev pontokon egyenletesen konvergál (amint az következik (1.91)-ból is). A Runge-féle példa által mutatott jelenség (a Bernstein-féle negatív eredményhez hasonlóan) az ekvidisztans felosztás sorozatokon értelmezett Lagrange interpolációhoz kapcsolódik. 1 A példa azért is érdekes mert az 1+x 2 függvény analitikus a valós számegyenesen. A komplex 1 számokon értelmezett 1+x2 függvénynek a i helyen lév½o szingularitása okozza a divergenciát az jxj 3:63 intervallumon kívül. A jelenség részletes magyarázatára nézve lásd Davis [12], vagy Epperson [17] munkáját.

1.4.2. Numerikus stabilitás Az interpolációs eljárásoktól általában azt várjuk, hogy a pontok számának növelése esetén a közelítés hibája csökken. Az el½oz½o fejezetben láttuk, hogy ez nem minden esetben van így. A Lagrange-interpoláció esetén a kerekítési hibák hatásán túlmen½oen numerikus instabilitás is felléphet nagy n-ek esetén. Ennek illusztrálására tegyük fel, hogy az yi = f (xi ) függvényértékeket "i hibával ismerjük (i = 1; : : : ; n). Ekkor az elméleti p(x) =

n X

f (xi )li (x)

i=1

Lagrange-interpolációs polinom helyett a perturbált p~(x) =

n X

(f (xi ) + "i )li (x)

i=1

32

INTERPOLÁCIÓ

polinommal számolunk. A kett½o eltérésére teljesül, hogy

(p (x)) = j~ p(x)

p(x)j =

max j"i j

1 i n

n X

n X

"i li (x)

i=1

n X i=1

i=1

jli (x)j =

j"i j jli (x)j

max j"i j

1 i n

n

(X; x) :

Ez a becslés pontos, mert az "i =sign(li (x)) " választással egyenl½oség lép fel. A Lebesgue konstansra ismert eredmények alapján a (p (x)) perturbációs hiba nagy lehet bizonyos alappontválasztásokra, ill. nagy n értékekre. A divergencia tulajdonságok és a numerikus instabilitás miatt sok esetben más típusú interpolációs technikákat használunk. A polinomiális interpoláció el½onyeit ½orzi meg a spline interpoláció, amellyel külön fejezetben foglalkozunk.

1.5. Feladatok 1. Legyen x = [x1 ; : : : ; xn ] és y = [y1 ; : : : ; yn ]! Oldjuk meg a következ½o lineáris interpolációs problémákat egy olyan Matlab programmal, amely a Matlab beépített lineáris egyenlet megoldóját használja! (A) x = [0; 1; 2; : : : ; 7], y = [0; 1; 0; 1; 0; 1; 0; 1], 'i (x) = sin(ix) (i = 1; : : : ; 8) (B) x = [1; 2; 4; 8], y = [0:5; 0:3; 0:1; 0:05], 'i (x) = e (C) xi =

i 1 2 , 10

yi =

1 , 1+i2

2

x

x

'i (x) 2 1; x; x ; e ; e ;

ix

;

1 1+x

i

2 f0; 1; 2; 3g (i = 1; : : : ; 6).

Rajzoljuk ki az interpolált és interpoláló függvényeket! 2. Mi az

1 1+x2

függvény n-edik deriváltja? Adjon rá becslést a [ 5; 5] intervallumon!

3. Az alábbi bázisfüggvény családok rosszul kondicionáltak. Két paraméterük van: és a függvények száma. Határozzuk meg experimentálisan, hogy hogyan függ a rosszul kondícionáltság az paramétert½ol, illetve a bázisfüggvények számától! (a) 'j (x) = e

x=j

(b) 'j (x) = e

xj

(c) 'j (x) =

1 , +jx

, j = 1; : : : ; n

, j = 1; : : : ; n j = 1; : : : ; n

(d) 'j (x) = log (1 +

j x),

j = 1; : : : ; n:

4. Az interpoláció pontosságának ellen½orzésére számítsuk ki az alábbi polinomok pe (x) Lagrange FELADATOK

33

interpolációs polinomjait és a megadott pontokban ellen½orizzük a p (x) p (x) 1 + x + x2 + x3 2 3 1 + x2 + x6 + x24 + Q6 (x j) Qj=1 20 (x j) Qj=1 20 (x 2 j ) Pj=1 20 j j=1 x =j!

x4 120

interpolációs pontok 1; 2; 3; 4 1; 0:5; 1; 2; 3:5 0; 1; 2; 3; 4; 5; 0; 1; 2; : : : ; 19 0, 2 j (j = 1; 2; : : : ; 19) 0:1j (j = 0; 1; : : : ; 19)

pe (x) különbséget!

ellen½orz½o pontok 1:5; 3:5 0; 1:5; 5:0 6; 7 15:5; 16:5; 20 2 20 ; 0:3; 1:0 1:0; 0; 0:25; 2:0

Írjunk Matlab programot a számítások elvégzésére, ábrázoljuk gra…kusan az eredményeket és próbáljuk értelmezni az eredményeket! 5. Vizsgáljuk meg az interpolációs alappontok megválasztásának hatását a [0; 1] intervallumon! Használjunk három féle alappontrendszert: az ekvidisztans, a Csebisev és az xi =

1 1 + arcsin 2

2i n

1

;

i = 0; 1; : : : ; n

inverz színusz pontokat. A három alappont rendszeren számítsa ki a Lagrange-féle interpolációs polinomot alábbi függvényekre n = 1; 2; 3; 5; 6; 10; 15 esetén. Becsülje a maximális hibát a [0; 1] intervallumon! Ábrázolja a hibafüggvényeket és becsülje meg a hiba konvergenciáját az n függvényében! Elemezze az alappont választás hatékonyságát! (a) ex 1 (b) 1+x 2 1 (c) 1+40x 2 (d) (x 0:5)2 sign(x 0:5) (e) p jx 0:5j (f) 1 x2 (g) 1 arcsin (2x 1). 6. Ellen½orizzük, hogy a megadott intervallumon a következ½o függvényrendszerek unisolvensek-e! függvények 1; x2 ; x4 1; x2 ; x4 1; x2 ; x3 1= (1 + x) ; 1= (x + 2) ; 1= (x + 3) 1; ex ; e2x

intervallum [0; 1] [ 1; 1] [ 1; 1] [0; 1] [0; 1]

7. Jelölje V (x1 ; x2 ; : : : ; xn ) a Vandermonde determinánst! Igazoljuk, hogy V (1; 2; : : : ; n) = 1!2!3! n! 8. Van-e olyan Rp parabola, amely felveszi az el½ore megadott p (0), p00 (0), p000 (0) értékeket? És 1 olyan, amelyre 1 p (x) dx, p (0) és p0 (0) értéke el½ore adott? 9. Adjon meg olyan legfeljebb harmadfokú p polinomot, amelyre p (0) = 1, p (1) = 3, p0 ( 1) = 4, p0 (0) = 0! Egyértelm½u-e a megoldás? 34

INTERPOLÁCIÓ

10. Mutassuk meg, hogy nem mindig tudunk találni olyan r (x) = (A + Bx) = (1 + Cx) alakú függvényt, amely átmegy 3 olyan ponton, amelynek abszcisszái páronként különböz½ok! 11. Lehet-e f (x) = A + BeCx alakú görbét illeszteni az f (0) = 0, f (1) = 1, f (2) = 21 adatokhoz? 12. Megoldható-e mindig az r (0) = f (0), r0 (0) = f 0 (0), r00 (0) = f 00 (0) interpolációs probléma, alakú? ha r (x) = A+Bx 1+Cx 13. Igazoljuk, hogy ha az a0 +a1 cos x+ +an cos nx trigonometrikus polinom n+1 különböz½o 0

x0 < x 1 <

< xn <

pontban elt½unik, akkor azonosan zérus! 14. Igazoljuk, hogy ha az b1 sin x + + bn sin nx trigonometrikus polinom n különböz½o 0 < x1 <

< xn <

pontban elt½unik, akkor azonosan zérus! 15. Tekintsük azt az n-edfokú pn (x) polinomot, amely megegyezik ex -el a 0; n1 ; n2 ; : : : nn 1 ; 1 pontokban! Milyen nagy legyen n, hogy teljesüljön az jex pn (x)j 10 6 (x 2 [0; 1]) feltétel? 2 k (k = 0; 1; : : : ; 10) pontokban! 16. Legyen f (x) = ex és interpoláljuk a függvényt az xk = 10 Becsüljük meg a Lagrange-interpoláció hibáját azpx = 1=20 pontban! p 17. Ismételjük meg az el½oz½o feladatot az f (x) = 9 + x függvénnyel! 1 18. Interpoláljuk az f (x) = x sin x függvényt az x0 = 1, x1 = 21 ; : : : ; xn = n+1 pontokon! Konvergál-e a pn Lagrange interpolációs polinom sorozat és mihez? 19. Számítsuk ki az xj = j 2 (j = 0; 1; 2; 3) alappontokhoz tartozó V (x0 ; x1 ; x2 ; x3 ) Vandermonde mátrix inverzét és ennek segítségével állítsuk el½o az yj = j (j = 0; 1; 2; 3) interpolációs feltételt kielégít½o Lagrange-interpolációs polinomot! p 20. Az f (x) = 1= x függvény esetén találjunk olyan 2 19 ; 1 pontot, amelyre f 91 ; 14 ; 1 = 1 00 f ( )! 2 21. Legyen f (x) = ln (x + 2) (x 2 [0; 2]) és pn (x) jelölje a n felosztáshoz tartozó Lagrange interpolációs polinomot, ahol 1

= f1; 2g ;

2

=

1 3 ; 1; 2 2

:

Határozzuk meg n = 1; 2 esetén a Lagrange interpoláció hibáját és adjunk rá fels½o becslést! Vizsgáljuk a becslés jóságát a tényleges hibához hasonlítva! 22. Számítsuk ki a p2 (x) Lagrange interpolációs polinomhoz tartozó Lebesgue konstanst, ha [a; b] = [0; 4] és az alappontok f1; 2; 4g! 23. Legyen x0 = t, x1 = t, ahol 0 < t 1. Igazoljuk, hogy a lineáris interpolációhoz tartozó Lebesgue függvény a következ½o: 8 1 x t; < x=t; 1; t < x t; 1 (x) = : x=t; t < x 1. FELADATOK

35

24. Igazoljuk, hogy k > 1 esetén f [x1 ; : : : ; xk ] =

k X i=1

Qk

f (xi )

j=1; j6=i

(xi

xj )

és a segítségével vezessük le a következ½o formulát:

f (x) = f [x1 ] + f [x1 ; x2 ] (x x1 ) + f [x1 ; x2 ; x3 ] (x x1 ) (x x2 ) + + f [x1 ; x2 ; : : : ; xn ] (x x1 ) (x x2 ) (x xk 1 ) + E (x) ; ahol E (x) = f [x1 ; : : : ; xn ; x]

n Y

(x

xi ) :

i=1

P 25. (Bernstein, 1931) Legyen 1 x 0 < x1 < x2 1 és 2 = max 1 x 1 2k=0 jlk (x)j a hozzátartozó Lebesgue konstans! Igazoljuk, 2 minimuma 5=4, amelyet akkor ér el, ha x0 = p 2 x2 2 és x1 = 0. Mutassuk meg azt is, hogy ha x0 ; x1 és x2 a T3 gyökei, akkor 2 = 5=3! 3 Vagyis a Csebisev-alappontok általában nem a n globális minimum helyei. 1 26. Igazoljuk, hogy f (x) = 1+x 2 egyenletesen folytonos az egész számegyesen!

36

INTERPOLÁCIÓ

2. fejezet Spline interpoláció A spline interpoláció alapötlete az adott függvény szakaszonkénti közelítése simasági feltételekkel kiegészítve. Az els½o cikket Schoenberg (1946) írta. Sokolniko¤ 1956-ban megállapította a kapcsolatot a spline és rúd elmélet között. További jelent½os fejleszt½ok: Schoenberg, Whitney (1949, 1953). Majd Ahlberg, Nilson, Walsh (1964, 1965) akik 1967-ben kiadták els½o spline monográ…át. A szplájnoknak ma már nagyon sok típusa és alkalmazási területe ismert. Mi itt csak a klasszikus egyváltozós harmadfokú szplájnokkal foglalkozunk az Ahlberg, Nilson és Walsh nyomán. A továbbiakra nézve az irodalomra utalunk.

2.1. Harmadfokú szplájn interpoláció Legyen adott az [a; b] intervallum egy :

a = x 0 < x 1 < x 2 < : : : < xn = b

(2.1)

felosztása, valamint az xi alappontokhoz tartozó Y :

yi = f (xi )

(i = 0; : : : ; n)

(2.2)

függvényértékek. Jelölje hi+1 = xi+1 xi a részintervallumok hosszát (i = 0; : : : ; n 1). Olyan S(x) (S (x) vagy S (Y ; x) módon is jelölt) függvényt keresünk, amely kielégíti a következ½o feltételeket: (i) S 2 C 2 [a; b]; (ii) S(x) = Si (x) (x 2 [xi ; xi+1 ]), ahol Si (x) legfeljebb harmadfokú polinom (i = 0; : : : ; n 1); (iii) S(xi ) = yi (i = 0; : : : ; n). Az S (x) (S (x)) függényt harmadfokú interpoláló szplájnnak nevezzük. Egy harmadfokú polinomot 4 együttható határoz meg. Miután n intervallum van, ez n darab harmadfokú polinomot és 4n ismeretlen együtthatót jelent. SPLINE INTERPOLÁCIÓ

37

Si+1(x)

S0(x)

Sn-1(x)

Si(x)

. . . y0

. . . yn

yi+1

a=x0

x1

Az (i)-(iii) feltételek 4n

. . .

xi

xi+1

xi+2

. . .

xn-1

xn=b

2 egyenletet határoznak meg, a következ½oképpen:

S (xi ) = yi (i = 0; 1; : : : ; n) [n + 1 egyenlet], Si

1

(xi ) = Si (xi ) (i = 1; : : : ; n

1) [n

1 egyenlet],

Si0

1

(xi ) = Si0 (xi ) (i = 1; : : : ; n

1) [n

1 egyenlet],

Si00 2 (xi ) = Si00 (xi ) (i = 1; : : : ; n

1) [n

1 egyenlet].

Ez összesen 4n 2 egyenlet. A feladat teljes "meghatározottságához" kell még két további feltétel. A szokásos plusz feltételek a következ½ok: (a) S 00 (a) = 0, S 00 (b) = 0; (b) S (k) (a) = S (k) (b), k = 0; 1; 2; (c) S 0 (a) = ya0 , S 0 (b) = yb0 . Az (a) esetben a szplájnt természetes szplájnnak nevezzük, a (b) esetben pedig periodikusnak. A szplájn, azaz a szakaszonkénti polinomok együtthatóit meghatározó lineáris egyenletrendszert többféle módon is le lehet vezetni: (1) Az Si (x) = ai + bi (x xi ) + ci (x xi )2 + di (x xi )3 (x 2 [xi ; xi+1 ]) felírásból közvetlenül; (2) Az ismeretlen Si00 (xi ) = Mi (i = 0; 1; : : : ; n) "momentum" értékek segítségével; (3) Az ismeretlen Si0 (xi ) (i = 0; 1; : : : ; n) deriváltértékek segítségével. Az egyes levezetések között elvi különbség nincs és a kapott eredmény szükségképpen ugyanaz lesz. Itt a (2) megoldást követjük, amelynek a geometriai tartalma az, hogy a szplájn második deriváltja egy folytonos töröttvonal, amelynek töréspontjai az (xi ; Mi ) pontok. S''i+1(x)

S''0(x) S''i(x)

. . . M0

a=x0 38

S''n-1(x) . . . Mn

Mi+1

x1

. . .

xi

xi+1

xi+2

. . .

xn-1

xn=b

SPLINE INTERPOLÁCIÓ

Az [xi ; xi+1 ] szakaszon xi+1 x x xi + Mi+1 : hi+1 hi+1

(2.3)

(xi+1 x)2 (x xi )2 + Mi+1 + Ai 2hi+1 2hi+1

(2.4)

Si00 (x) = Mi Ezt kétszer integráljuk és kapjuk, hogy Si0 (x) =

Mi

és (x xi )3 (xi+1 x)3 + Mi+1 + Ai (x Si (x) = Mi 6hi+1 6hi+1

(x 2 [xi ; xi+1 ]) ;

xi ) + Bi

(2.5)

ahol Ai és Bi az integrálási konstansok. Az S (xi ) = yi és S (xi+1 ) = yi+1 feltételeket felírva kapjuk, hogy S (xi ) = Mi S (xi+1 ) = Mi+1

h2i+1 + Bi = yi ; 6

h2i+1 + Ai hi+1 + Bi = yi+1 : 6

Innen azonnal kapjuk, hogy Bi = yi

Mi

h2i+1 6

(2.6)

és h2i+1 Mi+1 6 2 h Mi i+1 6

1

yi+1 Bi hi+1 1 = yi+1 yi hi+1 yi+1 yi hi+1 = (Mi+1 hi+1 6

Ai =

Mi+1

h2i+1 6 (2.7)

Mi ) :

Az Ai és Bi ismeretében a (2.5) formulát az alábbi szimmetrikus alakban írhatjuk fel: Mi h2i+1 (xi+1 x)3 (x xi )3 Si (x) = Mi + Mi+1 + yi 6hi+1 6hi+1 6 2 Mi+1 hi+1 x xi (x 2 [xi ; xi+1 ]) : + yi+1 6 hi+1

xi+1 x hi+1 (2.8)

Amennyiben az Mi "momentumok" ismertek, az S (x) értékét már könnyen számíthatjuk. Ha a szplájnt az Mi momentumok kifejezéseként az S (x) = Si (x) =

i

+

i

(x

xi ) +

HARMADFOKÚ SZPLÁJN INTERPOLÁCIÓ

i

(x

xi )2 +

i

(x

xi )3

(x 2 [xi ; xi+1 ])

(2.9) 39

(Taylor-polinom) alakban akarjuk látni, akkor vagy direkt behelyettesítést alkalmazunk az (2.5) képletben és rendezünk, vagy néhány egyszer½u trükköt alkalmazunk. Ez utóbbi esetben az együtthatók meghatározása a következ½o. Az interpolációs feltétel alapján S (xi ) =

S 0 (xi ) =

i

=

"

i

= yi ;

(x xi )2 (xi+1 x)2 + Mi+1 + Ai Mi 2hi+1 2hi+1

hi+1 yi+1 yi hi+1 + (Mi+1 2 hi+1 6 yi+1 yi hi+1 = (Mi+1 + 2Mi ) : hi+1 6 =

S 000 (xi ) = 6 i =

Mi

i

x=xi

Mi )

Mi

S 00 (xi ) = 2

#

= Mi ; 1

hi+1

+ Mi+1

1 hi+1

:

Az utolsó egyenlet jobboldala (2.5) harmadik deriváltja. Tehát kaptuk, hogy i i

i

i

(2.10)

= yi ; yi+1 yi hi+1 = (Mi+1 + 2Mi ) hi+1 6 1 = Mi ; 2 1 = (Mi+1 Mi ) : 6hi+1

(2.11) (2.12) (2.13)

Ezután már csak az n + 1 darab ismeretlen Mi "momentum" értékét kell meghatároznunk. Ehhez felhasználjuk az els½o deriváltak folytonosságát, pontosabban az Si0 1 (xi ) = Si0 (xi ) feltételt (i = 1; : : : ; n 1). Minthogy Si0

1

(xi ) =

"

Mi

(xi 1

x)2 2hi

+ Mi

(x

hi yi yi 1 hi = Mi + (Mi 2 hi 6 hi hi yi yi 1 = M i 1 + Mi + 6 3 hi 40

xi 1 )2 + Ai 2hi

1

#

x=xi

Mi 1 )


és "

Si0 (xi ) =

hi+1 yi+1 yi hi+1 + (Mi+1 2 hi+1 6 hi+1 hi+1 yi+1 yi Mi Mi+1 + ; 3 6 hi+1

=

Mi

= azért a

(xi+1 x)2 (x xi )2 Mi + Mi+1 + Ai 2hi+1 2hi+1

felosztás bels½o pontjaiban (i = 1; : : : ; n hi Mi 6

1

hi yi yi Mi + 3 hi

+

1

=

#

x=xi

Mi )

1) fennáll, hogy

hi+1 Mi 3

hi+1 yi+1 yi Mi+1 + : 6 hi+1

Ez átrendezve kapjuk az hi Mi 6

1

+

hi + hi+1 hi+1 yi+1 yi Mi + Mi+1 = 3 6 hi+1

alakú n 1 lineáris egyenletet (i = 1; : : : ; n momentumokat meg tudjuk határozni. Az (a) esetben ez a két egyenlet: S 00 (a) = M0 = 0;

yi

yi

1

hi

(2.14)

1). Kell még két további egyenlet, hogy a

S 00 (b) = Mn = 0:

(a-1)

A (b) periodikus szplájn (S (k) (a) = S (k) (b), k = 0; 1; 2) esetén az S 00 (a) = S 00 (b) = M0

(b-1)

(tkp. M0 = Mn ) feltétel eggyel csökkenti az ismeretlenek számát. A (2.9) el½oállítás alapján S00 (x0 ) =

y1

y0

h1 y1 y0 (M1 + 2M0 ) = 6 h1

h1

h1 (M1 + 2Mn ) : 6

A (2.4) formula alapján pedig Sn0

1 (xn ) =

Mn

(xn

xn )2

1

+ Mn

(xn

xn 1 )2 + An 2hn

2hn yn yn 1 hn hn = Mn + (Mn 2 hn 6 yn yn 1 hn = + (2Mn + Mn 1 ) hn 6

1

Mn 1 )

Innen az S 0 (a) = S 0 (b) feltétel alapján kapjuk a h1 hn M1 + Mn 6 6

1

+

h1 hn + 3 3

HARMADFOKÚ SZPLÁJN INTERPOLÁCIÓ

Mn =

yn

yn hn

1

y1

y0 h1

(b-2) 41

egyenletet. A (c) esetben az S 0 (a) = és

y1

y0 h1

yn

S 0 (b) =

h1 (M1 + 2M0 ) = ya0 6

yn

1

hn

hn (2Mn + Mn 1 ) = yb0 6

+

feltételekb½ol két további egyenletet h1 h1 y1 y0 M0 + M1 = 3 6 h1 és

hn Mn 6

1

hn Mn = yb0 3

+

ya0

yn

yn

(c-1) 1

(c-2)

hn

kapunk. A (2.14) egyenletet megszorozzuk a 6= (hi + hi+1 ) mennyiséggel hi Mi hi + hi+1

yi+1 yi hi+1

hi+1 6 Mi+1 = hi + hi+1 hi + hi+1

+ 2Mi +

1

yi

yi

1

hi

és bevezetjük a hi ; hi + hi+1 6 di = hi + hi+1

i

=

mennyiségeket (i = 1; : : : ; n i Mi 1

=1

i

yi+1 yi hi+1

i

hi+1 ; hi + hi+1 yi yi 1 hi

(2.15)

=

(2.16)

1). Ekkor az (2.14) egyenlet alakja + 2Mi +

i Mi+1

= di

(i = 1; : : : ; n

(2.17)

1) :

Az (a) feltételek (természetes szplájn) esetén, amikor is M0 = Mn = 0 és csak n 1 ismeretlenünk van, az (2.17) lineáris egyenletrendszer megoldása adja a szplájn Mi "együtthatóit". Ekkor a lineáris egyenletrendszer alakja: 2M1 + 1 M2 +2M2 2 M1 ...

+ 2 M3 ... n 2 Mn 3

Ez mátrix alakban

2 6 6 6 6 6 4

42

2 2

0

2 .. .

... +2Mn 1 + n 2 Mn +2Mn 1 n 1 Mn 2

0

1 2

..

= d1 = d2 .. .

.

..

n 2

2

n 2

n 1

2

.

32

3

M1 M2 .. .

76 76 76 76 76 5 4 Mn Mn

2 1

2

1

= dn = dn 3

d1 d2 .. .

7 6 7 6 7 6 7=6 7 6 5 4 dn dn

2 1

7 7 7 7: 7 5

(a-2) 2 1

(a-3)


A (c) feltételek esetén a (c-1)-(c-2) egyenletek átírhatók az 2M0 + M1 =

6 h1

y1

6 hn

yb0

y0

ya0

yn

yn

h1

és Mn

1

+ 2Mn =

1

hn

alakba, ahonnan a 0

= 1;

n

= 1;

6 y1 y0 ya0 ; h1 h1 yn yn 1 6 dn = yb0 hn hn

(2.18)

d0 =

(2.19)

jelölésekkel a (c) tipusú szplájnt meghatározó 2M0 + 0 M1 +2M1 1 M0 ...

+ 1 M2 ... n 1 Mn 1

n + 1 ismeretlenes lineáris 2 2 6 1 6 6 6 6 4 0

= d0 = d1 .. .

... +2Mn n Mn

1 1

(c-3)

+ n 1 Mn = dn 1 +2Mn = dn

egyenletrendszert kapjuk, amelynek mátrix alakja 32 3 2 3 M0 d0 0 0 7 6 M1 7 6 d1 7 2 1 76 7 6 7 7 6 .. 7 6 .. 7 .. .. .. = 76 . 7 6 . 7: . . . 76 7 6 7 4 dn 1 5 2 n 1 n 1 5 4 Mn 1 5 2 Mn dn n

(c-4)

Az eddig megkapott két lineáris rendszer mátrixa hasonló, un. tridiagonális mátrix. A (b) periodikus szplájn esetén a (b-2) egyenlet átírható h1 M1 + 2Mn h1 + hn

1

+

hn 6 Mn = h1 + hn h1 + hn

yn

yn

y1

1

hn

y0 h1

alakba, ahonnan a n

=

h1 ; h1 + hn

n

=1

n

=

hn ; h1 + hn

dn =

6 h1 + hn

yn

yn hn

1

y1

y0 h1

jelölésekkel a periodikus szplájnt de…niáló n ismeretlenes lineáris egyenletrendszer alakja (az HARMADFOKÚ SZPLÁJN INTERPOLÁCIÓ

43

M0 = Mn …gyelembevételével): 2M1 + 1 M2 +2M2 + 2 M3 2 M1 ... ... .. .

+ 1 Mn ... ..

n

. 1 Mn

..

2

n M1

Az egyenletrendszer mátrix alakban 2 2 1 6 2 2 2 6 6 . . .. . . 6 . . . 6 4 2 n 1 n

= d1 = d2 .. . .. . = dn 1 = dn

n

. +2Mn 1 + n Mn 1

32

1

n 1

2

M1 M2 .. .

76 76 76 76 76 5 4 Mn 1 Mn

n 1 Mn

2Mn

3

2

d1 d2 .. .

7 6 7 6 7 6 7=6 7 6 5 4 dn 1 dn

3

7 7 7 7: 7 5

(b-3)

(b-4)

Az eddigeket összegezve megállapíthatjuk, hogy az (a), (b) és (c) típusú szplájnok esetén a szplájnok együtthatóit lineáris egyenletrendszerek megoldásával kaphatjuk meg. A következ½okben megmutatjuk, hogy a kapott lineáris egyenletrendszerek mindig egyértelm½uen megoldhatók. Ehhez szükségünk van a következ½o eredményre. Tétel (Gersgorin). Legyen A = [aij ]ni;j=1 2 Cn n , ri =

n X

j=1; j6=i

jaij j

(i = 1; : : : ; n)

(2.20)

aii j

ri g

(2.21)

és Di = fz 2 Cj jz Ekkor az A mátrix minden

(i = 1; : : : ; n) :

sajátértékére fennáll, hogy 2 [ni=1 Di :

(2.22)

Bizonyítás. Legyen v = [v1 ; : : : ; vn ]T a -hoz tartozó sajátvektor, i pedig az az index, amelyre fennáll, hogy kvk1 = jvi j > 0. Az Av = v egyenletrendszer i-edik egyenlete vi = aii vi +

n X

aij vj ;

j=1;j6=i

ahonnan átrendezéssel j vi 44

aii vi j = j

aii j jvi j

n X

j=1; j6=i

aij vj

n X

j=1; j6=i

jaij j jvi j SPLINE INTERPOLÁCIÓ

adódik. Mindkét oldalt jvi j-vel elosztva kapjuk, hogy j

aii j

ri :

Minthogy minden sajátérték benne van valamelyik Di körlemezben, az összes sajátérték benne van az egyesítésükben. Tétel: Az (a-3), (c-4) és (b-4) lineáris egyenletrendszerek nemszingulárisak az [a; b] intervallum tetsz½oleges partíciója esetén. Bizonyítás: Az összes mátrix esetén aii = 2 (8i). Az (a-3) mátrix esetén r1 = 1 < 1, ri = 2) és rn 1 = n 1 < 1. A Gersgorin tétel szerint az összes sajátérték a i + i = 1 (i = 2; : : : ; n jz 2j 1 komplex körlemezben van. Tehát nem lehet zérus sajátérték és a mátrix nemszinguláris. Ugyanez az okfejtés igaz a (c-4) mátrixra is és a (b-4) mátrixra is. Az utóbbi esetben r1 = 1 és rn = 1. Egy A mátrixot diagonálisan dominánsnak nevezünk, ha minden i esetén fennáll, hogy jaii j >

X j6=i

jaij j

(1

i

n) :

(2.23)

Az (a-3), (c-4) és (b-4) egyenletrendszerek mátrixai diagonálisan dominánsak. Ezért az egyenletrendszerek a Gauss-eliminációval f½oelemkiválasztás nélkül, numerikusan stabil módon oldhatók meg. Az (a) és (c) esetekben a lineáris egyenletrendszer mátrixa tridiagonális, amelyet a Gaussmódszer un. sávos változatával O (n) aritmetikai m½uvelettel lehet megoldani. A (b-4) mátrix az ún. bordázott mátrixok körébe tartozik. Erre hatékony megoldó algoritmusok léteznek.

2.2. Konvergencia eredmények A szplájnok igen kedvez½o - az alkalmazásokban is igen fontos - approximációs tulajdonságokkal rendelkeznek. A konvergencia bizonyítás el½ott szükségünk van néhány fogalomra. De…níció. Az f : Rn ! R függvényt vektornormának nevezzük, ha f (x) 0 (8x 2 Rn ) ; f (x) = 0 , x = 0; f ( x) = j j f (x) (8x 2 Rn ; 8 2 R) ; f (x + y) f (x) + f (y) (8x; y 2 Rn ) :

KONVERGENCIA EREDMÉNYEK

(2.24) (2.25) (2.26)

45

A vektornorma szokásos jelölése: kxk. A fontosabb vektornormák: n X

kxk1 =

i=1

jxi j ;

n X

kxk2 =

x2i

i=1

(2.27)

! 21

kxk1 = max jxi j n

(2.28)

(maximum norma):

1 i n

De…níció. Az f : Rn

(euklideszi norma);

(2.29)

! R függvényt mátrixnormának nevezzük, ha f (A)

8A 2 Rn

0

;

8A 2 Rn

f ( A) = j j f (A)

f (A + B)

n

f (A) + f (B)

f (A) = 0 , A = 0; n

; 8 2R ;

8A; B 2 R

n n

(2.30) (2.31) (2.32)

:

A mátrixnorma szokásos jelölése: kAk. A leggyakrabban használt mátrixnormák: kAk1 = max

1 j n

n X i=1

jaij j

(oszlopösszeg norma) ; 1

kAk2 = fAT A legnagyobb sajátértékeg 2 kAk1 = max

1 i n

kAkF =

n X j=1

n X n X i=1 j=1

jaij j

a2ij

! 21

(2.33)

(spektrálnorma) ;

(2.34)

(sorösszeg norma) ;

(2.35)

(Frobenius norma) :

(2.36)

A mátrixnormáknak két fontos osztályát emeljük ki. De…níció. A k:kM : Rn n ! R mátrixnormát a k:kV : Rn ! R vektornorma által indukált mátrixnormának nevezzük, ha kAkM = max fkAxkV : kxkV = 1g = max x6=0

kAxkV : kxkV

(2.37)

Könnyen igazolható, hogy kAk1 az kxk1 , kAk2 az kxk2 , kAk1 pedig az kxk1 vektornorma által indukált mátrixnorma. Tétel. Indukált mátrixnormában kABk kAk kBk ( 8A; B 2 Rn n ). Az indukált normákhoz hasonló (de velük nem azonos) fogalom a következ½o. 46


1.13 De…níció. A k:kM : Rn n ! R mátrixnorma kompatibilis a k:kV : Rn ! R vektornormával, ha kAxkV kAkM kxkV . Az kAkF Frobenius norma kompatibilis a kxk2 vektornormával. Az indukált mátrixnormák az ½oket indukáló vektornormákkal kompatibilisek. Az (a-3), (c-4) és (b-4) egyenletrendszerek együttható mátrixai nemszingulárisak és diagonálisan dominánsak. Jelölje B akármelyiket a három mátrix közül. A következ½okben becslést adunk B 1 sorösszeg normájára. Legyen y = Bx és kxk1 = jxk j. Ekkor kyk1 = kBxk1 = max i

n X

n X j=1

bkj xj = bkk +

j=1

X

jbkk j

!

i

X

bkj

j6=k

xj kxk1 xk

jbkj j kxk1

j6=k

min jbii j

bij xj

X j6=i

!

jbij j kxk1 ;

amib½ol következik, hogy B

1 1

= max y6=0

kxk1 kB 1 yk1 = max x6=0 kBxk kyk1 1

1 mini jbii j

Az (a-2) egyenlet mátrixa esetén X

jb11 j

j6=1

jbii j jbn

1;n 1 j

a (c-4) esetben

X

X

j6=n 1

j6=i

jb1j j = 2

1

1;j j

=2

n 1

X

jbij j = 1 (i = 0; : : : ; n);

jbii j

X

jbij j = 1 (i = 1; : : : ; n);

a (b-4) esetben pedig

amib½ol a

j6=i

B KONVERGENCIA EREDMÉNYEK

1 1

1

jbij j

2);

> 1;

jbii j

j6=i

j6=i

:

> 1;

jbij j = 1 (i = 2; : : : ; n

jbn

P

(2.38) 47

korlát következik mindhárom mátrix esetén. De…níció: Legyen f 2 C [a; b]. Az f függvény folytonossági modulusának nevezzük a [0; b a] intervallumon értelmezett ! ( ) = max jf (y) f (x)j (2.39) a x y b y x

függvényt. Az f függvényre való utalásként szokás az ! (f ; ) jelölést is használni. Tétel: Legyen f 2 C [a; b]. Az ! folytonossági modulus a következ½o tulajdonságokkal rendelkezik: (i) ! (0) = 0; (ii) Ha 0 < 1 < 2 , akkor ! ( 1 ) ! ( 2 ) (monotonitás); (iii) ! ( 1 + 2 ) ! ( 1 ) + ! ( 2 ) (szubadditivitás); (iv) ! (n ) n! ( ); (v) ! 2 C [0; b a]. Bizonyítás: (i) triviális. y x x 1 ) y 2 miatt (ii) is triviális. Az (iii) bizonyításához vegyük észre, hogy 0 y x esetén jf (y) f (x)j ! ( 1 ) ! ( 1 ) + ! ( 2 ). Másrészt, ha 1 x (x + 1 ) 1 < y 1 + 2 , akkor x + 1 < y és y 2 . Mivel jf (x)

f (y)j

jf (x) f (x + 1 )j + jf (x + ! ( 1 ) + ! (y (x + 1 )) ! ( 1) + ! ( 2) ;

1)

f (y)j

az (iii) következik. az (iv) tulajdonság a szubadditivitás triviális következménye. Az (ii) és (iii) tulajdonságok miatt 0 ! ( + 1) ! ( ) ! ( 1) : Az f egyenletes folytonossága miatt lim 1 !0 ! ( 1 ) = 0 és ezért ! folytonos a pontban. A de…níció alapján triviális a következ½o Állítás: (i) Ha f 2 C [a; b] di¤erenciálható és jf 0 (x)j K, akkor ! (f ; ) K ; (i) Ha jf (x) f (y)j L jx yj ( x; y 2 [a; b]) valamilyen 0 < 1 konstanssal, akkor ! (f ; ) L . A következ½okben becslést adunk az (a-3), (c-4) és (b-4) egyenletrendszerek megoldásaira. Ezek BM = D alakúak, ahol B, M = [: : : ; Mi ; : : :]T és D = [: : : ; di ; : : :]T az (a), (b) és (c) esetnek megfelel½oen változnak. Azonban jMi j

kM k1 = B 1 D

1

kDk1

miatt elég egy fels½o korlátot adnunk a di mennyiségek maximumára. Legyen a felosztás normája k k = maxi hi és tegyük fel, hogy az [a; b] intervallum felosztása olyan, hogy egy rögzített 1 számmal fennáll a maxi hi k k = mini hi mini hi

(2.40)

egyenl½otlenség. 48


Az i = 1; : : : ; n

1 esetben di =

Mármost jyi

yi 1 j

6 hi + hi+1

! (f ; k k), jyi+1

yi+1 yi hi+1 yi j

yi

1

:

hi

! (f ; k k) és 6 2 ! (f ; k k) : k k2

6 ! (f ; k k) (mini hi )2

jdi j

yi

(2.41)

A periodikus szplájn esetén dn =

6 h1 + hn

yn

yn

y1

1

hn

y0 h1

:

Itt az el½oz½o becslés érvényes: jdn j A (c) tipusú szplájn esetén d0 =

6 h1

y1

y0 h1

6 2 ! (f ; k k) : k k2 ya0 ;

dn =

6 hn

yb0

(b-5)

yn

yn

1

hn

:

Ha ya0 = f 0 (x0 ) és yb0 = f 0 (xn ), akkor d0 és dn (pontosabban ezek hatodrésze) az f 00 közelítései az x0 , illetve xn pontban. Egyébként pedig a következ½o becsléseket adhatjuk: jd0 j

6 2 0 2 (! (f ; k k) + k k jya j) ; k k

Vizsgáljuk az S (x)

Si (x)

jdn j

6 2 0 2 (! (f ; k k) + k k jyb j) : k k

(c-5)

f (x) eltérést az [xi ; xi+1 ] intervallumban! A (2.8) el½oállítás alapján (xi+1 x)3 (x xi )3 + Mi+1 + yi 6hi+1 6hi+1 Mi+1 h2i+1 x xi + yi+1 f (x) ; 6 hi+1

f (x) = Mi

Mi h2i+1 6

xi+1 x hi+1 (2.42)

ami átírható az Si (x)

f (x) = Mi

x) (xi+1 x)2 h2i+1 (x + Mi+1 6hi+1 xi+1 x x xi f (x)) + (yi+1 f (x)) hi+1 hi+1

(xi+1

+ (yi

xi ) (x xi )2 6hi+1

h2i+1 (2.43)

alakba. Innen az x 2 [xi ; xi+1 ] értékekre az jSi (x)

f (x)j

1 kM k h2i+1 + 2! (f ; k k) 3


1 kDk k k2 + 2! (f ; k k) 3 49

becslést kapjuk. Az (a) természetes szplájn esetén kDk jSi (x)

f (x)j

2

6 2 ! k k2 2

(f ; k k) és így

! (f ; k k) + 2! (f ; k k) :

(a-4)

A (b-5) becslés miatt ugyanez a becslés érvényes a periodikus szplájn esetén is. 2 A (c) tipusú szplájn esetén a (c-5) becslés miatt kDk k6 k2 (! (f ; k k) + k k max fjya0 j ; jyb0 jg) és így jSi (x) f (x)j 2 2 (! (f ; k k) + k k max fjya0 j ; jyb0 jg) + 2! (f ; k k) : (c-6) Tétel: Tegyük fel, hogy f 2 C [a; b] és n

:

(n)

(n)

(n)

a = x0 < x1 < x2 < : : : < x(n) n = b

az [a; b] intervallum olyan felosztás sorozata, amelyre egy rögzített hogy k nk : (n) (n) min xi+1 xi

(2.44) 1 konstanssal teljesül, (2.45)

Ekkor az (a), (b) és (c) tipusú szplájnok bármelyikére teljesül, hogy x 2 [a; b] esetén S

n

(x) ! f (x)

(k

nk

! 0)

egyenletesen. Ha f Lipschitz az [a; b] intervallumon ( 0 < L jx yj ( x; y 2 [a; b]), akkor konvergencia sebessége jf (x)

S

n

(x)j

KL k

nk

(k

nk

(2.46) 1), azaz jf (x) 1) :

f (y)j

(2.47)

Bizonyítás: Az (a) és (b) szplájn esetén jSi (x) f (x)j 2 2 ! (f ; k k)+2! (f ; k k), amib½ol a (2.46) állítás következik ! (f ; ) ! 0 ( ! 0) miatt. A (c) szplájn esetén ugyanez az jSi (x) f (x)j 2 2 (! (f ; k k) + k k max fjya0 j ; jyb0 jg) + 2! (f ; k k) becslésb½ol következik. Ha f Lipschitz , akkor az (a) és (b) esetben a (2.47) állítás az ! (f ; ) L tulajdonság miatt minden n felosztásra igaz. A (c) szplájn esetében fel kell, hogy tegyük a k n k 1 feltételt, mert ekkor k nk k nk . Miel½ott további konvergencia tételeket mondanánk ki, megjegyezzük, hogy a most bizonyított tétel önmagában még nem túl er½os, annak ellenére, hogy a Lagrange interpoláció esetén ilyen eremény nincs (v.ö. Bernstein, Grünwald-Marcinkiewicz tételekkel). Legyen f 2 C [a; b], : a = x0 < x1 < x2 < : : : < xn = b egy felosztás, Y : yi = f (xi ) (i = 0; : : : ; n) pedig az interpolálandó függvény értékek. Az els½o fokú Se (x) interpoláló szplájnt a következ½oképpen de…niáljuk: (i) Se 2 C [a; b];

(ii) Se (x) = Sei (x) (x 2 [xi ; xi+1 ]), ahol Sei (x) legfeljebb els½ofokú polinom (i = 0; 1; : : : ; n

50

1);


(iii) Se (xi ) = yi (i = 0; 1; : : : ; n).

Ennek a feladatnak egyetlen megoldása van, éspedig az (xi ; yi ) pontokat összeköt½o töröttvonal, amelynek képlete: xi+1 x x xi Sei (x) = yi + yi+1 hi+1 hi+1

(x 2 [xi ; xi+1 ] ; i = 0; 1; : : : ; n

(2.48)

1) :

Mármost felírhatjuk, hogy Sei (x)

f (x) = (yi

ahonnan azonnal az

f (x))

Sei (x)

xi+1 x + (yi+1 hi+1

f (x)

f (x))

x xi ; hi+1

2! (f ; k k)

becslést kapjuk (amit már korábban láttunk részbecslésként is). Ebb½ol az el½oz½o tétel két konvergencia eredménye azonnal kijön a n felosztás sorozatra vonatkozó minden megszorítás nélkül. Sima függvények esetén azonban f deriváltjait Se deriváltjai nem közelítik. Ezt egy igen lényeges különbségnek tekinthetjük. Tétel: Tegyük fel, hogy f 2 C 1 [a; b] és n

(n)

(n)

(n)

a = x0 < x1 < x2 < : : : < xn(n) = b

:



A (b) tipusú - periodikus - szplájn esetén tegyük még fel, hogy f 0 (a) = f 0 (b), a (c) tipusú szplájn esetén pedig tegyük fel, hogy S 0 (a) = f 0 (a) és S 0 (b) = f 0 (b). Ekkor az (a), (b) és (c) tipusú szplájnok bármelyikéhez vannak olyan olyan K1 ; K2 > 0 konstansok, hogy x 2 [a; b] esetén jf (x)

S

n

K1 k

(x)j

nk !

(f 0 ; k

n k)

(2.51)

és f 0 (x)

S 0 n (x)

K2 ! (f 0 ; k

n k) :

(2.52)

Ha f 0 Lipschitz az [a; b] intervallumon ( 0 < 1), azaz jf 0 (x) ( x; y 2 [a; b]), akkor jf (x) S n (x)j K1 k n k1+

f 0 (y)j

L jx

yj (2.53)

és f 0 (x)

S 0 n (x)

K3 k

nk

(2.54)

:

Bizonyítás: Az állítások igazolásához a di értékeket újra becsüljük. Az i = 1; : : : ; n di =

6 hi + hi+1


yi+1 yi hi+1

yi

yi hi

1

1 esetben

: 51

Minthogy yi+1

yi = f 0 ( i ) hi+1 ( i 2 [xi ; xi+1 ]), di =

és

6 (f 0 ( i ) hi + hi+1

3 ! (f 0 ; 2 k k) k k

jdi j A periodikus szplájn esetén

dn =

6 h1 + hn

yn

yn

f0 (

i 1 ))

6 ! (f 0 ; k k) : k k y1

1

hn

y0

;

h1

amelyre f 0 (a) = f 0 (b) és dn =

6 ((f 0 ( h1 + hn

miatt a jdi j

f 0 (b)) + (f 0 (a)

n 1)

f 0 ( 0 )))

6 ! (f 0 ; k k) k k

becslés érvényes. A (c) tipusú szplájn esetén d0 =

6 h1

y1

y0 h1

ya0 ;

dn =

6 hn

dn =

6 (f 0 (b) hn

yb0

yn

yn

1

hn

;

amib½ol az ya0 = f 0 (a) és yb0 = f 0 (b) feltételek és d0 =

6 0 (f ( 0 ) h1

miatt a jd0 j

f 0 (a)) ;

6 ! (f 0 ; k k) ; k k

jdn j

f0 (

n 1 ))

6 ! (f 0 ; k k) k k

becslések adódnak. Az [xi ; xi+1 ] intervallumon az

Si0

(x)

(xi+1 x)2 (x xi )2 yi+1 yi hi+1 + Mi+1 + (Mi+1 Mi ) f (x) = Mi 2hi+1 2hi+1 hi+1 6 Mi Mi+1 yi+1 yi = h2i+1 3 (xi+1 x)2 + 3 (x xi )2 h2i+1 + 6hi+1 6hi+1 hi+1 0

f 0 (x) f 0 (x)

összefüggés alapján kapjuk, hogy jSi0 (x) 52

f 0 (x)j

2 kM k k k + jf 0 ( i ) 3

f 0 (x)j : SPLINE INTERPOLÁCIÓ

Így végül az kM k1

6 ! k k

kDk1

jSi0 (x)

(f 0 ; k k) becslés alapján kapjuk, hogy f 0 (x)j

(4 + 1) ! (f 0 ; k k) ;

amib½ol a tétel (2.52) állítása már következik. Az interpolációs tulajdonság miatt Z x S (x) f (x) = [f 0 (x) S 0 (x)] dx xi

amib½ol kapjuk a (2.51) állítást: jS (x)

f (x)j =

Z

Z

x 0

S (x)] dx

nk !

0

[f (x)

0

xi

xi

K3 k

x

(f ; k k) :

jf 0 (x)

S 0 (x)j dx

A tétel többi állítása a folytonossági modulus tulajdonságából következik. f 2 C 1 [a; b] esetén f Lipschitz 1-es függvény, mondjuk az L konstanssal, és ezért (2.47)-b½ol jf (x) S n (x)j K1 L k n k következik. A most bizonyított Tétel ennél er½osebbet állít. Tétel: Tegyük fel, hogy f 2 C 2 [a; b] és n

(n)

(n)

(n)

a = x0 < x1 < x2 < : : : < x(n) n = b

:



Ha a (c) tipusú szplájn kielégíti az S 0 (a) = f 0 (a) és S 0 (b) = f 0 (b) feltételt, akkor van olyan olyan K > 0 konstans, hogy x 2 [a; b] esetén f (p) (x) Ha f 00 Lipschitz

S

(p) n

(x)

Kk

2 p nk

az [a; b] intervallumon ( 0 < f (p) (x)

S

(p) n

Bizonyítás: Becslést adunk az Mi 1; : : : ; n 1 esetén

(x)

KL k

! (f 00 ; k

n k)

(2.57)

1) az L Lipschitz konstanssal, akkor 2 p+ nk

f 00 (xi ) eltérésre.

1 di = 6f [xi 1 ; xi ; xi+1 ] = f 00 ( i ) 2

(p = 0; 1; 2) :

(2.58)

Már korábban megjegyeztük, hogy i =

( i 2 (xi 1 ; xi+1 )):

Az y1 = y0 + f 0 (x0 ) h1 + 12 f 00 ( 0 ) h21 ( 0 2 (x0 ; x1 )) és yn = yn ( n 2 (xn 1 ; xn )) képleteket felhasználva kapjuk, hogy KONVERGENCIA EREDMÉNYEK

(p = 0; 1; 2) :

1

+ f 0 (xn 1 ) hn + 12 f 00 ( n ) h2n

53

d0 = és dn =

y1

6 h1

6 hn

y0

ya0

h1 yn

yb0

yn

= 3f 00 ( 0 )

1

= 3f 00 ( n ) :

hn

Jelölje B a (c-4) egyenlet mátrixát ( 0 = 1 = n ), M = [M0 ; M1 ; : : : ; Mn 1 ; Mn ]T , D = [d0 ; d1 ; : : : ; dn 1 ; dn ]T és legyen F = [f 00 (x0 ) ; f 00 (x1 ) ; : : : ; f 00 (xn 1 ) ; f 00 (xn )]T . Vizsgáljuk az alábbi mennyiséget: 2 00 3 2 00 3 f ( 0) 2f (x0 ) + 0 f 00 (x1 ) 6 f 00 ( 1 ) 7 6 1 f 00 (x0 ) + 2f 00 (x1 ) + 1 f 00 (x2 ) 7 7 6 . 7 6 . 6 . 7 6 . 7 6 . 7 6 . 7 BM BF = D BF = 3 6 00 7 6 7: 00 00 00 f (x ) + 2f (x ) + f (x ) f ( ) 6 7 6 i i i 1 i i i+1 7 6 . 7 6 . 7 4 .. 5 4 .. 5 00 00 f 00 ( n ) n f (xn 1 ) + 2f (xn ) Ez átírható a

BM

2

2 (f 00 ( 0 ) f 00 (x0 )) + 0 (f 00 ( 0 ) 00 f 00 (x0 )) + 2 (f 00 ( 1 ) 1 (f ( 1 ) .. .

f 00 (x1 )) f 00 (x1 )) +

00 6 1 (f ( 1 ) 6 6 6 BF = 6 6 i (f 00 ( i ) f 00 (xi 1 )) + 2 (f 00 ( i ) f 00 (xi )) + i (f 00 ( i ) 6 . 4 .. 00 f 00 (xn 1 )) + 2 (f 00 ( n ) f 00 (xn )) n (f ( n 1 )

7 7 7 7 7 f 00 (xi+1 )) 7 7 5

f 00 (x2 ))

alakba, ahonnan kapjuk, hogy j2 (f 00 ( 0 ) j

i

(f 00 ( i )

f 00 (x0 )) +

0

f 00 (xi 1 )) + 2 (f 00 ( i )

(f 00 ( 0 )

f 00 (xi )) +

f 00 (x1 ))j

3! (f 00 ; k

(f 00 ( i )

f 00 (xi+1 ))j

i

3

n k) ;

3! (f 00 ; 2 k n k) 6! (f 00 ; k n k)

és Mármost M

j

n

(f 00 (

F =B kM

n 1) 1

f 00 (xn 1 )) + 2 (f 00 ( n )

F k1

B

f 00 (x) = (Mi = (Mi + (Mi+1

54

3! (f 00 ; k

BF ) és ezért

(BM

1 1

Az [xi ; xi+1 ] szakaszon tekintsük az S 00 (x) Si00 (x)

f 00 (xn ))j

kBM

BF k1

6! (f 00 ; k

f 00 (x) különbséget xi+1 x + (Mi+1 f 00 (x)) hi+1

f 00 (xi ) + f 00 (xi )

n k) :

n k) :

f 00 (x))

x xi hi+1

xi+1 x hi+1 x xi f 00 (x)) ; hi+1

f 00 (x))

f 00 (xi+1 ) + f 00 (xi+1 )


ahonnan az jSi00 (x)

f 00 (x)j

7! (f 00 ; k

n k)

(2.59)

becslést kapjuk. Az S (xi ) = yi interpolációs tulajdonság miatt S (xi ) f (xi ) = 0 és S (xi+1 ) f (xi+1 ) = 0. A Rolle-tétel miatt létezik olyan 2 [xi ; xi+1 ] pont, hogy S 0 ( ) f 0 ( ) = 0. Ezért 0

jS (x)

f (x)j =

Z

f (x)j =

Z

0

amib½ol jS (x)

x

[S 00 (t)

f 00 (t)] dt

7k

nk !

x

[S 0 (t)

f 0 (t)] dt

xi

7k

nk

2

(f 00 ; k

! (f 00 ; k

n k) ;

n k) :

(2.60)

(2.61)

Az állítás többi része triviálisan következik a folytonossági modulus tulajdonságából. Vegyük észre, hogy f 2 C 3 [a; b] esetén a konvergencia rendje O k n k3 . A most bemutatott konvergencia tételeken túlmen½oen számos más - sok esetben ki…nomultabb - konvergencia tétel létezik, nemcsak a most vizsgált esetekre, hanem a mellékfeltételek különböz½o módosításaival de…niált hasonló szplájnokra is. Ezekkel itt nem foglalkozunk, de jelzésként megjegyezzük, hogy f 2 C 4 [a; b] esetén a szpline interpoláció sebessége tovább n½ohet. A következ½o idevágó "csúcs" eredményt idézzük, némi egyszer½usítéssel. Tétel (Hall-Meyer, 1976): Tegyük fel, hogy f 2 C 4 [a; b] és n

:

(n)

(n)

(n)

a = x0 < x1 < x2 < : : : < xn(n) = b



Ha a (c) tipusú szplájn kielégíti az S 0 (a) = f 0 (a) és S 0 (b) = f 0 (b) feltételt, akkor vannak olyan olyan Kp > 0 konstansok ( p = 0; 1; 2; 3), hogy x 2 [a; b] esetén f (p) (x)

S

(p) n

(x)

Kp k

4 p nk

(p = 0; 1; 2; 3) :

(2.64)

A harmadfokú szplájnon kívül nagyszámú egy és többváltozós szplájnt fejlesztettek ki, ill. használnak. Ezekre nézve az irodalomra hivatkozunk. A szplájnok approximációs tulajdonságai összehasonlíthatók a klasszikus polinom approximáció tulajdonságaival (pl. Jackson tételekkel). KONVERGENCIA EREDMÉNYEK

55

2.3. Variációs tulajdonságok A szplájnoknak …gyelemre méltó variációs tulajdonságai vannak. Az els½o ilyen fontos tulajdonság a minimum norma tulajdonság, amelyet Holladay fedezett fel 1957-ben. Ez sok alkalmazásban szerepet játszik. (Pl. adatsimítás, Wahba [58]). Tétel (Holladay, 1957): Legyen : a = x0 < x1 < x2 < : : : < xn = b és Y = fyi : i = 0; : : : ; ng adott. Minden olyan f 2 C 2 [a; b] függvényre, amelyre f (xi ) = yi ( i = 0; 1; : : : ; n), az S (Y ; x) természetes szplájn minimalizálja a Z b

a

2

jf 00 (x)j dx

(2.65)

funkcionált. Igaz továbbá, hogy az S (Y ; x) az egyetlen lehetséges függvény amely ezt a funkcionált minimalizálja. Bizonyítás: f 2 C 2 [a; b] és f (xi ) = yi miatt Rb a

=

=

jf 00 (x) Rb

S 00 (y; x)j2 dx

a

jf 00 (x)j2 dx

2

Rb

jf 00 (x)j2 dx

2

a

Rb a

Rb a

Rb

f 00 (x) S 00 (Y ; x) dx + [f 00 (x)

a

jS 00 (Y ; x)j2 dx

S 00 (Y ; x)] S 00 (Y ; x) dx

A jobb oldal középs½o kifejezése felírható az Z

b 00

[f (x)

00

00

S (Y ; x)] S (Y ; x) dx =

a

n Z X

a

jS 00 (Y ; x)j2 dx:

xi

[f 00 (x)

xi

i=1

Rb

S 00 (Y ; x)] S 00 (Y ; x) dx

1

alakban. Parciális integrálással kapjuk az S 000 (Y ; x) szakaszonkénti konstans voltának és az yi = f (xi ) = S (Y ; xi ) interpolációs kikötés …gyelembevételével, hogy R xi [f 00 (x) S 00 (Y ; x)] S 00 (Y ; x) dx xi 1 = [f 0 (x)

S 0 (Y ; x)] S 00 (Y ; x) jxxii

1

= [f 0 (x)

S 0 (Y ; x)] S 00 (Y ; x) jxxii

1

= [f 0 (x)

S 0 (Y ; x)] S 00 (Y ; x) jxxii

1

Az [f 0 (x)

R xi xi

1

[f 0 (x)

[f (x)

S (Y ; x)] S 000 (Y ; x) jxxii

1

:

S 0 (Y ; x)] S 00 (Y ; x) folytonossága és S (Y ; x) tipusa miatt Z

a

b 00

[f (x)

00

00

S (Y ; x)] S (Y ; x) dx =

n X i=1 0

[f 0 (x)

= [f (x) 56

S 0 (Y ; x)] S 000 (Y ; x) dx

S 0 (Y ; x)] S 00 (Y ; x) jxxii

1

S 0 (Y ; x)] S 00 (Y ; x) jba = 0: SPLINE INTERPOLÁCIÓ

Kaptuk tehát, hogy a természetes szplájnnal fennáll az Z

a

b

2

00

jf (x)j dx

Z

a

b

2

00

jS (Y ; x)j dx =

Z

a

b

jf 00 (x)

2

S 00 (y; x)j dx

(2.66)

azonosság. A jobboldal pozitív, kivéve az S 00 (y; x) = f 00 (x) esetet, azaz, ha S (Y ; x) = f (x) + Ax+B, amely az S (Y ; xi ) = f (xi ) feltételek miatt f (x)-re redukálódik [Axi +B = 0 = Axj +B (i 6= j)) A = 0 ) B = 0]. Az (2.66) relációt els½o integrál összefüggésnek nevezik.

2.4. Feladatok 1. Oldjuk meg a Lagrange interpolációnál elemzett Runge példát természetes szplájn függvényekkel is! Hasonlítsuk össze a kapott eredményt a Lagrange-interpolációval kapottal! 2. Hasonlítsuk össze a Lagrange interpoláció és a szplájn interpoláció hatékonyságát a következ½o függvényekre az intervallum ekvidisztans felosztásán, illetve Csebisev pontokon az alappontok száma szerint! f (x) [a; b] 10x e [0; 3] min fjxj ; jx 2jg [ 1; 3] cos (1 + x2 ) [0; 3] (x 1)=x e [0; 3] sin (x) [0; 1] Ábrázoljuk is a függvényeket! 3. Vizsgáljuk meg az interpolációs alappontok megválasztásának hatását a [0; 1] intervallumon! Használjunk három féle alappontrendszert: az ekvidisztans, a Csebisev és az xi =

1 1 + arcsin 2

2i n

1

;

i = 0; 1; : : : ; n

inverz színusz pontokat. A három alappont rendszeren számítsa ki a természetes szplájn függvényeket az alábbi függvényekre n = 1; 2; 3; 5; 6; 10; 15 esetén. Becsülje a maximális hibát a [0; 1] intervallumon! Ábrázolja a hibafüggvényeket és becsülje meg a hiba konvergenciáját az n függvényében! Elemezze az alappont választás hatékonyságát! (a) ex 1 (b) 1+x 2 1 (c) 1+40x2 (d) (x 0:5)2 sign(x 0:5) (e) p jx 0:5j (f) 1 x2 FELADATOK

57

(g) 1 arcsin (2x 1). 4. Vizsgáljuk meg az alábbi adathalmazra a Lagrange-interpoláció és a szplájn interpoláció hatékonyságát különböz½o alappontszám (n = 6; 9; 13) esetén. Hogyan válasszuk ki az interpolációs alappontokat? Mi a helyzet más fajta, pl. Hermite-Fejér interpoláció esetén? i 1 2 3 4 5 6 7 8 9 10 11 12

xi 10:0 10:2 10:4 10:6 10:8 11:0 11:2 11:4 11:6 11:8 11:89 11:96

yi 0:42 0:48 0:51 0:52 0:53 0:55 0:58 0:61 0:65 0:74 0:91 1:29

i 13 14 15 16 17 18 19 20 21 22 23 24

xi 12:0 12:04 12:08 12:12 12:16 12:20 12:28 12:36 12:44 12:50 13:0 14:0

yi 1:52 1:87 2:35 2:89 3:40 3:83 4:27 4:53 4:62 4:64 4:64 4:64

Ábrázoljuk az adathalmazt és az interpoláló függvényeket! 5. Jelölje LipK azon C [a; b]-beli f függvények halmazát, amelyre fennáll, hogy jf (x)

f (y)j

K jx

yj

(x; y 2 [a; b]) ;

ahol > 0 és 0 < K < 1 konstans. Igazoljuk a következ½oket: (a) LipK C [a; b]; (b) p Ha > 1, akkor LipK csak a konstans függvényeket tartalmazza; (c) x 2Lip1 (1=2) és sin x 2Lip1 1 a [0; 1] intervallumon; (d) Lip = [K>0 LipK a C [a; b] altere; (e) Lip1 tartalmazza az összes polinomot; (f) Ha f 2Lip valamely > 0 értékre, akkor f 2Lip minden 0 < < esetén; (g) Adott 0 < < 1 esetén mutassuk meg, hogy x 2Lip1 , de x 2Lip = , ha > . 6. A folytonos f : [a; b] ! R függvényt poligonálisnak nevezzük, ha létezik véges sok a = x1 < x1 < < xn = b pont (alappont, csomópont, töréspont, stb.), hogy f lineáris függvény az [xk 1 ; xk ] intervallumokon (k = 1; 2; : : : ; n). Rögzítsük az egymástól különböz½o xk pontokat és jelöljük Sn -el azokat a poligonális függvényeket, amelyeknek a rögzített xi pontok a töréspontjai. (a) Igazoljuk, hogy Sn lineáris vektortér és dimenziója n + 1, amelyet a '0 (x) = 1 és a 'k+1 (x) = jx xk j + (x xk ) függvények feszítenek ki (k = 0; 1; : : : ; n 1)! [segítség: Írjuk fel Pn a h 2 Sn függvényt a h (x) = c0 + k=1 'k (x) alakban. Igazoljuk, hogy a jobboldal szintén Sn P eleme és mutassuk meg, hogy a h (x0 ) = c0 , h (xk ) = c0 + 2 ki=1 ci (xk xk 1 ) (k = 1; : : : ; n) egyenletrendszer egyértelm½uen megoldható!] Pn 1 (b) Igazoljuk, hogy Sn minden eleme felírható i=1 ai jx xi j + bc + d alakban, valamilyen a1 ; : : : ; an 1 , b és d konstansokkal! 58


7. Legyen f periódikus és integrálható függvény és de…niáljuk f mozgó átlagát az Z x+h 1 fh (x) = f (t) dt 2h x h el½oírással! Igazoljuk, hogy (a) fh (x) periódikus (b) Ha f 2 C n , akkor fh 2 C n+1 (c) ! (fh ; ) ! (f ; ) (fh simább mint f ) (d) Ha f elég sima, akkor fh (x)0 = (f 0 )h . 8. Legyen f; g 2Lip az [a; b] intervallumon! Igazoljuk, hogy f g 2Lip ! 9. Kielégit-e valamilyen Lipschitz feltételt az x log x függvény a [0; 1] intervallumon?

FELADATOK

59

60


3. fejezet Függvények legjobb egyenletes közelítése Legyen az f 2 C [a; b] függvény adott, amelyet egy G = Ga 2 C [a; b] n-paraméteres függvénnyel közelítünk, ahol a = [a1 ; : : : ; an ]T 2 , Rn adott paraméter halmaz. A függvényközelítés jóságát az e = f Ga hibafüggvény normájával mérjük. De…níció: k:k : C [a; b] ! R függvény a C [a; b] függvényhalmazon értelmezett norma, ha minden f; g 2 C [a; b] esetén fennáll, hogy (i) kf k 0, kf k = 0 , f (x) = 0, 8x 2 [a; b] (ii) k f k = j j kf k, 2 R (iii) kf + gk kf k + kgk. Állítás: jkf k

kgkj

kf

(3.1)

gk :

A C [a; b] halmaz a függvények összeadására és valós számmal való szorzására nézve lineáris (végtelen dimenziós) vektortér, amelyen számos normát értelmezhetünk. A kf kC = max jf (x)j

(3.2)

x2[a;b]

normát egyenletes, vagy Csebisev normának nevezzük. A kf kp =

Z

1=p

b

a

p

jf (x)j dx

(3.3)

normát pedig Lp -normának nevezzük, ahol p 1 valós szám. Egy normával ellátott lineáris V vektorteret normált térnek nevezünk. A d (v; w) = kv wk mennyiség ekkor egy távolságot de…niál a V halmazon. De…níció: A V normált tér normáját szigorúan konvexnek nevezzük, ha minden v1 6= v2 , kv1 k = 1 és kv2 k = 1 esetén k 1 v1 +

2 v2 k

<1

( 1;

2

> 0;

1

+

2

= 1) :

(3.4)

A de…níció azt jelenti, hogy a B = fv : kvk 1g zárt egységgömb határa nem tartalmaz nyilt egyenes szakaszt. Néha magát a teret nevezik szigorúan konvexnek. FÜGGVÉNYEK LEGJOBB EGYENLETES KÖZELíTÉSE

61

Példa: p > 1 esetén az Lp -norma szigorúan konvex. Példa: Az L1 -norma (p = 1) nem szigorúan konvex. Legyen f1 (x) = 32 x2 , f2 (x) = és C [a; b] = C [ 1; 1]. Ekkor kf1 k1 =

Z

1 1

jf1 (x)j dx = 1;

de f1 + f2 2

1

3 = 8

Z

kf2 k1 =

Z

x2 )

1

jf2 (x)j dx = 1

1

x2 + 1 dx = 1: 1

= max 1 C

(1

1

Példa: A Csebisev norma nem szigorúan konvex. Legyen f1 (x) = 1 C [a; b] = C [ 1; 1]. kf1 kC = kf2 kC = 1 és f1 + f2 2

3 4

1 x 1

x2 , f2 (x) = 1

x4 és

x2 + x4 = 1: 2

A legjobb függvényközelítés (approximáció) problémáját általánosan a következ½oképpen fogalmazhatjuk meg. Adott norma esetén keressük azt az a 2 paramétervektort (Ga közelít½o függvényt), amelyre fennáll, hogy kf

Ga k

kf

Ga k ;

8a 2 :

(3.5)

A Ga (x) függvényt az f függvény legjobb approximációjának (közelítésének) nevezzük. A Csebisev norma esetén legjobb egyenletes, vagy Csebisev approximációról beszélünk. A probléma megoldása az f függvényt½ol, az Ga függvényt½ol és az adott normától függ. Lineáris approximációról beszélünk, ha Ga (x) =

n X

ai 'i (x) ;

(3.6)

i=1

ahol f'i gni=1 C [a; b] adott bázisfüggvények. Feltételezzük, hogy a '1 ; : : : ; 'n bázisfüggvények lineárisan függetlenek. Ez azt jelenti, hogy n X i=1

ci 'i (x) = 0, 8x 2 [a; b]

(3.7)

esetén szükségképpen teljesül, hogy c1 = : : : = cn = 0. Igaz a következ½o Tétel: Ha f'i gni=1 CP [a; b] lineárisan függetlenek, akkor minden f 2 C [a; b] esetén létezik legjobban közelít½o Ga = ni=1 ai 'i függvény. Pn Bizonyítás: Legyen e ( ) = e ( 1 ; : : : ; n ) = kf 0 és inf e ( ) kf k. i=1 i 'i k. e ( )

62

FÜGGVÉNYEK LEGJOBB EGYENLETES KÖZELíTÉSE

Az e ( ) folytonos (n-változós valós) függvény, mert je ( )

e ( )j =

n X

f f

i 'i

i=1 n X

=

(

f

i 'i

i=1

n X

!

i ) 'i

i

i=1

max j i

Legyen G ( ) = k

Pn

i=1

i 'i k.

ij

i

n X

n X i=1

i 'i

i=1

n X

f

i 'i

i=1

!

!

k'i k :

Az el½oz½o argument alapján ez is folytonos, továbbá homogén, azaz G(

) = j jG( ):

(3.8)

P A f 2 Rn : ni=1 2i = 1g halmaz korlátos és zárt, ezért G ( )-nak van egy véges m m > 0, mert a 'i függvények lineárisan függetlenek. Tetsz½oleges 6= 0 esetén ! !1=2 !1=2 n n X X 2 2 G( ) = G Pn m : i i 2 1=2 ( i=1 i ) i=1 i=1 | {z }

0 minimuma.

(3.9)

m

Legyen

= inf e ( )

0 és R = ( + 1 + kf k) =m. Ha n X

e( ) = f

m

n X i=1

> mR

2 i

!1=2

kf k =

Ezért e ( ) globális minimuma a korlátos és zárt Weierstrass-tétel szerint fel is vesz.

i=1

n X

i 'i

i=1

Pn

i 'i

i=1

2 i

> R2 , akkor kf k

kf k + 1: Pn

i=1

(3.10) R2 gömbön belül van, amelyet a

2 i

P A most bizonyított tételben lényeges, hogy a ni=1 i 'i alakú approximáló függvények a C [a; b] tér egy véges n-dimenziós alterét alkotják. Ez a végesség egy lényeges kikötés. Tegyük fel ugyanis, hogy W C 0; 12 olyan altér, amely az összes polinomot tartalmazza. Megmutatjuk, hogy az f (x) = 1= (1 x) függvényhez nincs olyan p 2 W polinom, amelyre igaz, hogy kf p kC kf pkC (p 2 W ). Vegyük észre, hogy minden " > 0 számhoz van olyan N , hogy 1 1

x

1+x+

+ xN

=

xN +1 1 x


2

N

< ";

0

x

1 : 2 63

Ezért, ha lenne legjobb aproximáció, mondjuk, p , akkor teljesülnie kellene az feltételnek, ami ellentmondás, mert 1= (1 x) nem polinom.

1 1 x

p

C

=0

Tegyük fel, hogy van két legjobb approximációnk, azaz n X

e( ) = f

i 'i

=

n X

= f

i=1

Tetsz½oleges 0 <

i 'i

= e( ):

i=1

< 1 esetén fennáll, hogy f

n X

(

i

+ (1

)

i=1

=

f f

n X

i=1 n X

i 'i

i 'i

!

i ) 'i

+ (1

) f

i 'i

i=1

+ (1

) f

i=1

= :

n X

n X

!

i 'i

i=1

Az + (1 ) együtthatók nem adhatnak jobb approximációt, ezért itt egyenl½oség áll fenn. Tétel: A legjobb lineáris approximációk halmaza konvex. Tétel: Szigorúan konvex norma esetén a legjobb lineáris approximáció egyértelm½u. Bizonyítás: Legyen és két különböz½o legjobb lineáris approximáció paraméter vektora, e ( ) = e ( ) = és legyenek ! ! n n X X f1 = f f2 = f i 'i = ; i 'i = : i=1

i=1

Ekkor kf1 k = kf2 k = 1 és a szigorú konvexitás miatt n X

1 f1 + f2 = f 2

i=1

i

+ 2

i

'i < 1:

Ámde ez azt jelentené, hogy f

n X i=1

i

+ 2

i

'i < ;

ami ellentmondás. A most bizonyított eredményekb½ol azonnal következik a legjobb approximáció létezése az alábbi két esetben: (a) Polinom approximáció: 'i (x) = xi

1

(i = 1; : : : ; n);

(b) Trigonometrikus approximáció: [a; b] = [0; 2 ], '1 (x) = 1, '2` (x) = sin (`x) ; '2`+1 (x) = cos (`x) (` = 1; : : : ; m). 64


3.1. Legjobb egyenletes approximáció polinomokkal Vizsgáljuk most folytonos függvények legjobb polinom approximációját a Csebisev-norma esetén. Legyen Pn a legfeljebb n-edfokú polinomok halmaza. Minden n-ed fokú p (x) = a0 + a1 x + : : : + an xn 2 Pn polinom el½oáll p (x) =

n X

(3.11)

ai 'i (x)

i=0

alakban, ahol 'i (x) = xi (i = 0; : : : ; n). Minthogy a f'i (x)gni=0 függvények lineárisan függetlenek, a p (x) 2 Pn legjobb egyenletes polinom approximáció létezik, azaz fennáll, hogy En (f ) = kf

p kC

kf

pkC ;

p (x) 2 Pn :

(3.12)

Az En (f ) mennyiség az f függvény legjobb n-ed fokú polinom közelítésének hibája a Csebisev normában, amelyre fennáll, hogy En+1 (f )

En (f ) :

(3.13)

A legjobb egyenletes közelítés tulajdonképpen azt jelenti, hogy az f p eltérésfüggvény maximuma a p (x) legjobb approximációs polinomra a legkisebb. A legjobb Csebisev approximációval kapcsolatban több probléma azonnal felmerül: En (f ) ! 0? Ha En (f ) ! 0, akkor milyen sebességgel? p (x) unicitása? p (x) meghatározása. A Csebisev norma nem szigorúan konvex, ezért a korábbi unicitási tételb½ol nem következik p unicitása. Az En (f ) ! 0 tulajdonságot Weierstrass igazolta 1885-ben mind a polinomok, mind pedig a trigonometrikus polinomok esetére. Az En (f ) ! 0 konvergencia sebességének alapvet½o jellemzéseit D. Jackson adta 1912-ben. A legjobb approximáció unicitását Csebisev, De La Vallée Poussin igazolták. A bizonyítás képezi az alapját a p (x)-et meghatározó algoritmusoknak. Példa: f 2 C [a; b] és legyen n = 0. Keressük tehát a legjobban közelít½o konstans függvényt. Legyen M = maxx2[a;b] f (x) és m = minx2[a;b] f (x). Legyen a0 = (m + M ) =2. Ez a keresett legjobban közelít½o konstans, amelyre E0 (f ) = (M m) =2. LEGJOBB EGYENLETES APPROXIMÁCIÓ POLINOMOKKAL

65

Példa: Legyen f 2 C 2 [a; b] és tegyük fel, hogy f (x) konvex, azaz f 00 (x) 0 (x 2 [a; b]). Határozzuk meg az (a; f (a)) és (b; f (b)) pontokat összeköt½o szel½ot, valamint a görbe ezzel párhuzamos c pontbeli érint½ojét (a < c < b). Az f (x) görbe ezen két párhuzamos egyenes között van. Tekintsük azt a velük párhuzamos egyenest, amely a két egyenest½ol pontosan egyenl½o távolságra van! Ez lesz az f (x) függvény legjobban approximáló els½ofokú polinomja.

3.1.1. Weierstrass tétele és a legjobb approximáció rendje Kimondjuk Weierstrass polinomokra vonatkozó tételét, azt Bernstein módszerével igazoljuk és az approximáció rendjét jellemezzük. Végül kimondjuk a Bernstein módszer áltlánosítását jelent½o Bohman-Korovkin tételt. Tétel (Weierstrass, 1885): Legyen f 2 C [a; b] adott. Minden > 0 esetén létezik egy p (x) polinom, hogy kf pkC < . 66


A tétel következménye, hogy En (f ) ! 0;

(n ! 1) :

(3.14)

A tételnek sok bizonyítása van. Mi itt N.S. Bernstein (1912) igazolását követjük, amely konstruktív, relatíve egyszer½u és fontos általánosítási lehet½oségekhez vezet. A tételt az általánosság megszorítása nélkül a C [0; 1] függvényekre igazoljuk. De…níció: Legyen n m x (1 m

In;m (x) =

x)n

m

;

0

m

(3.15)

n.

Az f 2 C [0; 1] függvény n-edik Bernstein polinomját a Bn (x) = Bn (f ; x) =

n X

m In;m (x) n

f

m=0

(3.16)

el½oírás de…niálja. Az In;m (x) pontosan n-ed fokú, Bn (x) legfeljebb n-ed fokú polinom. Vegyük észre, hogy In;m (x) 0. Lemma: Igazak a következ½o azonosságok: n X

In;m (x) = 1;

(3.17)

mIn;m (x) = nx;

(3.18)

m=0 n X

m=0 n X

(nx

m)2 In;m (x) = nx (1

(3.19)

x) :

m=0

Bizonyítás: Igaz a következ½o azonosság: y

[e + (1

n

x)] =

n X

m=0

n my e (1 m

x)n

m

:

Az ey = x választás azonnal adja a (3.17) azonosságot. Deriváljuk mindkét oldalt y szerint y

y

ne ([e + (1

n 1

x)])

=

n X

m=0

m

n my e (1 m

x)n

m

:

Az ey = x helyettesítéssel kapjuk a (3.18) azonosságot. Az utóbbit y szerint ismét deriválva kapjuk, hogy y

y

ne ([e + (1

n 1

x)])

+ n (n

2y

y

1) e ([e + (1

n 2

x)])

=

n X

m=0

LEGJOBB EGYENLETES APPROXIMÁCIÓ POLINOMOKKAL

m2

n my e (1 m

x)n

m

: 67

Ismét az ey = x választással kapjuk, hogy 2

nx + n (n

1) x =

n X

m

2

m=0

n m x (1 m

n m

x)

=

n X

m2 In;m (x) :

m=0n

Ha ehhez mindkét oldalon hozzádjuk a (3.17) egyenlet n2 x2 -szeresét, valamint a (3.18) egyenlet 2nx-szeresét, akkor a (3.19) azonosságot kapjuk. Tétel: Legyen f 2 C [0; 1]. Ekkor Bn (x) ! f (x) ( n ! 1) egyenletesen a [0; 1] intervallumon. Bizonyítás: Adott " > 0 számhoz van olyan > 0, hogy jf (x1 ) f (x2 )j < ", ha jx1 x2 j < . De…níció szerint f (x)

Bn (x) =

n h X

f (x)

m i In;m (x) = S1 + S2 ; n

f

m=0

ahol

X

S1 =

m n

m : jx

és

X

S2 =

m n

m : jx

j<

j

f (x)

m i In;m (x) f n

f (x)

m i f In;m (x) : n

h h

Legyen M = kf kC . Ekkor kapjuk, hogy jS1 j

X

"

m : jx

m n

In;m (x)

n X

"

In;m (x) = "

m=0

j<

és jS2 j

X

2M

m : jx

2M n2 2

n X

In;m (x)

m n

2M

j

(nx

X

m : jx

m n

j

(nx m)2 In;m (x) n2 2

m)2 In;m (x)

m=0

2M nx (1 n2 2 M : 2n 2

x)

Tehát jf (x)

Bn (x)j

jS1 j + jS2 j

"+

M : 2n 2

Ha az n > M= (2" 2 ), akkor jf (x) 68

Bn (x)j

2":


Ezzel a tételt igazoltuk. A Bernstein polinomok konvergenciájának a sebességére adunk becslést, ami egyúttal a legjobb approximáció mértékére is ad egy fels½o becslést. Lemma: f 2 C [a; b], > 0 és > 0. Ekkor ! ( ) (1 + ) ! ( ). Bizonyítás: Legyen n 1 < n. Ekkor ! ( ) ! (n ) n! ( ) ( + 1) ! ( ). Tétel: f 2 C [0; 1] esetén 1 3 : (3.20) ! f; p kf Bn (f )k 2 n Bizonyítás: De…níció szerint jf (x)

n X

Bn (x)j =

f (x)

m=0 n X

m=0 n X

f (x)

Minthogy x m = n a következ½oképpen:

, ahol

jf (x)

=

Bn (x)j

m n

n x

1 p n

!

1 p n

!

m n

f m n

In;m (x) In;m (x)

In;m (x) :

!

x

és

p = 1= n, az egyenl½otlenség láncot folytathatjuk

m=0

p

m n

f

n X

1+

p

n x

m=0

"

n p X 1+ n x m=0

m n

In;m (x)

# m In;m (x) : n

A Cauchy-Schwarz egyenl½otlenség alapján kapjuk, hogy n X

m=0

x

n X m x In;m (x) = n m=0 " n X m=0

m [In;m (x)]1=2 [In;m (x)]1=2 n #1=2 " n #1=2 X m 2 x In;m (x) In;m (x) : n m=0

Itt a jobboldali szorzat második tagja 1 ((3.17) miatt). A szorzat els½o tagja (3.19) miatt 1 . Tehát amelynek maximuma 4n n X

m=0

és jf (x)

Bn (x)j

!

x

m In;m (x) n 1 p n

1+

p

x(1 x) , n

1 p 2 n 1 n p 2 n


3 = ! 2

1 p n

: 69

A tételb½ol azonnal következik, hogy a C [0; 1] téren 3 1 ! f; p 2 n

En (f ) Ha f 2 C [0; 1] és Lipschitz akkor

(0 <

(3.21)

:

1), azaz jf (x)

K jx

f (y)j

yj (x; y 2 [0; 1]),

1 3 K p : 2 ( n)

En (f )

(3.22)

A Bernstein polinomok approximációja lassú és a kapott eredménynél nagyobb sebességet általában nem is tudnak. Legyen f (x) = x 12 . Ekkor f Lipschitz 1 a K = 1 konstanssal és ezért kf Legyen most x = 1=2. Ekkor Bn

n 1 1 X m = n 2 2 m=0 n

1 2

1 f; 2

1 2

Bn kC

3 p . 2 n

n : m

Tegyük fel, hogy n páros szám. Ekkor n X m n m=0

n m

1 2

és Bn f ;

1 2

=2

n=2 X

1 2

m=0

f

1 2

=

m n 1

2n+1

n n=2

n m

=

1 n 2 n=2

1 > n 2

1=2

:

Ez mutatja, hogy a Bernstein polinomokkal elérhet½o sebesség általános becslése nagyságrendileg pontos. A (3.17)-(3.19) összefüggések átírhatók a Bn (1; x) = 1;

Bn (x; x) = x;

Bn x2 ; x = x2 +

1 x (1 n

x)

(3.23)

formákba. Az utóbbi esetben Bn x2 ; x

x2 =

x (1 x) ; n

ami egy jobb O (1=n)-rend½u konvergencia sebességet jelent. Sima f függvényekre lényegében ez a sebesség igazolható és ennél jobb nincs is. Pontosabban a következ½o igaz (Lorenz [34]). Tétel: Ha f 2 C 1 [0; 1], akkor kf

70

Bn (f )k

3 1 p ! f 0; p 4 n n

:

(3.24)


Ha f 0 Lipschitz 1-es függvény, akkor kf Bn (f )k C=n. Ez már nem javítható az f magasabb rend½u deriváltjainak feltevése mellett sem (lásd pl. Lorenz [34]). Tétel (Voronovsky): Legyen f korlátos [0; 1]-en és legyen x0 2 [0; 1] olyan pont, amelyben f 00 (x0 ) létezik. Akkor lim n [Bn (f ; x0 )

n!1

1 f (x0 )] = x0 (1 2

x0 ) f 00 (x0 ) :

(3.25)

A legjobb Csebisev approximáció mértékét pontosabban jellemzi a D. Jackson-tól származó alábbi két tétel. Tétel (Jackson, 1912): Ha f 2 C [a; b], akkor En (f )

6! f ;

b

a 2n

(3.26)

:

Tétel (Jackson, 1912): Ha f 2 C k [a; b], akkor En (f )

Ak (b a)k b ! f (k) ; k n 2n

a 2k

;

(3.27)

ahol Ak csak k-tól függ½o állandó. További hasonló tételek az irodalomban találhatók. Itt csak a következ½oket jegyezzük meg. Ha f (k) (x) Lipschitz , akkor Ek; (b a)k+ ; (3.28) En (f ) nk+ 1 . ahol Ek; a k-tól, -tól és f (k) -tól függ½o állandó. Ezt azt jelenti, hogy ekkor En (f ) = O nk+ Bernstein igazolta, hogy ha egy f függvényre En (f ) = O

1 nk+

(3.29)

teljesül < 1 értékkel, akkor f az [a; b] intervallum minden bels½o pontjában k-szor di¤erenciálható és a k-adik derivált az (a; b) minden zárt bels½o részintervallumában eleget tesz egy kitev½oj½u Lipschitz feltételnek. = 1 esetén az állítás nem igaz. Hasonló un. megfordítási tételek az irodalomban találhatók. A most idézett eredmények is mutatják, hogy a Bernstein polinomokkal kapott approximáció konvergenciája lassú. A Bernstein-féle közelítés nagy el½onye azonban, hogy egyszer½u és konstruktív, amelyet számos formában kiterjesztettek, ill. alkalmaznak (lásd pl. Gal [19], Lorenz [34]). Van azonban még egy ezeknél is fontosabb és igen meglep½o tulajdonsága, amelyet 1952 körül fedezett fel Korovkin és t½ole függetlenül Bohman. A Bernstein közelítés lényegében egy f ! Bn (f ) hozzárendelés a következ½o tulajdonságokkal: Bn ( f + g) = Bn (f ) + Bn (g) ( ; 2 R) ; Bn (f ) 0; ha f (x) 0 (x 2 [0; 1]) : LEGJOBB EGYENLETES APPROXIMÁCIÓ POLINOMOKKAL

(3.30) (3.31) 71

Tehát Bn : C [0; 1] ! C [0; 1] egy pozitív lineáris leképezés. Igaz a következ½o Lemma: Ha a T : C [a; b] ! C [a; b] leképezés pozitív és lineáris, akkor folytonos is. Bizonyítás: Ha egy lineáris leképezés pozitív, akkor monoton is: f g ) T (f ) T (g). Minden f 2 C [a; b] esetén f; f jf j ) T (f ) ; T (f ) T (jf j) ; azaz jT (f )j

T (jf j). Minthogy jf j

kf kC 1, ahol 1 az 1 konstans függvényt jelöli, azért

jT (f )j

T (jf j)

kf kC T (1)

és kT (f )kC

kf kC T (1)

A T operátor linearitása miatt T Lipschizes: kT (f )

T (g)k = kT (f

(f 2 C [a; b]) :

g)k

T (1) kf

gk :

Tehát T folytonos. Tétel (Bohman-Korovkin): Legyen Tn : C [0; 1] ! C [0; 1] pozitív lineáris leképezések sorozata, amelyre teljesül, hogy Tn (f ) ! f egyenletesen az f0 (x) = 1, f1 (x) = x és f3 (x) = x2 függvények mindegyikén. Ekkor Tn (f ) ! f egyenletesen minden f 2 C [0; 1] függvényre. A tétel bizonyítása hasonló a Bernstein tétel igazolásához (lásd pl. Cheney [10]). Példa: Legyen f 2 C [0; 1] és Ln (f ) 2 C [0; 1] pedig az xk = k=n (k = 0; 1; : : : ; n) pontokban az f (x) függvényt interpoláló törött vonal (els½ofokú interpoláló szplájn). Ln (f ) lineáris a [(k 1) =n; k=n] részintervallumokon, Ln (f ) nk = f nk . Igazoljuk (ismét), hogy Ln (f ) ! f egyenletesen. Ln (1) = 1, Ln (x) = x. Az f (x) = x2 esetén csak azt kell meggondolnunk, hogy a [(k 1) =n; k=n] részintervallumon Ln (x) és x2 eltérésének maximuma k n

2

k

1 n

2

=

2 2k 1 < 2 n n

és ezért Ln (x2 ) ! x2 egyenletesen. A Bohman-Korovkin tétel alapján az egyenletes konvergencia következik.

3.1.2. A legjobb approximáció Csebisev-féle jellemzése és következményei. A fejezetben kimondjuk Csebisev-tételét a legjobb polinom approximáció jellemzésér½ol és unicitásáról. Ez a jellemzés adja a legjobban approximáló polinomot el½oállító Remez tipusú algoritmusok elvi alapját. Tétel (Csebisev): Ha p (x) 2 Pn az f függvényt legjobban közelít½o polinom, akkor létezik n + 2 számú xk pont, hogy: a x1 < x2 < : : : < xn+2 b (3.32) és f (xk ) 72

p (xk ) = ( 1)k En (f )

(k = 1; : : : ; n + 2) ;

(3.33)


vagy f (xk )

p (xk ) = ( 1)k+1 En (f )

(3.34)

(k = 1; : : : ; n + 2) :

Bizonyítás: Az állítás azt jelenti, hogy az e (x) = f (x) p (x) függvény az [a; b] intervallumban legalább n + 2 pontban felveszi a minimumát és a maximumát olymódon, hogy maximum után minimum, minimum után pedig maximum következik. A tételt több lépésben igazoljuk. 1) Feltehet½o, hogy En (f ) 6= 0, mert En (f ) = 0 esetén tetsz½oleges n + 2 különböz½o, a (3.32) feltételnek megfelel½o pontra igaz az állítás. 2) jej 2 C [a; b], maxa x b je (x)j = En (f ) miatt van olyan x1 2 [a; b] pont, amelyre je (x1 )j = En (f ). 3) Tegyük fel, hogy f (x1 ) p (x1 ) = En (f ) : (3.35) A másik eset tárgyalása hasonlóan megy. Igazoljuk, hogy van olyan x2 2 [a; b] pont, hogy f (x2 )

p (x2 ) =

(3.36)

En (f ) :

Ha ugyanis ilyen nem volna, akkor fennállna (En (f ) >)

m = min (f (x) a x b

Ekkor a q (x) = p (x) +

p (x)) >

En (f ) :

1 (En (f ) + m) 2

(3.37)

polinom legfeljebb n-ed fokú és egyrészt f (x)

q (x) = f (x) p (x) | {z }

1 (En (f ) + m) 2

1 (En (f ) 2

m)

1 (En (f ) + m) = 2

1 (En (f ) 2

m) :

En (f )

másrészt f (x)

q (x) = f (x) p (x) | {z } m

Azaz kapjuk, hogy

max jf (x)

a x b

q (x)j

1 (En (f ) 2

m) < En (f ) ;

ami ellentmond annak, hogy kf (x) q (x)kC En (f ) lehet csak. Tehát van olyan x2 pont, amelyre (3.36) teljesül. 4) e (x) = f (x) p (x) egyenletesen folytonos [a; b]-n. Ezért létezik olyan > 0 szám, hogy jx1 x2 j < esetén je (x1 ) e (x2 )j En (f ) =2: Osszuk fel az [a; b] intervallumot egymásutáni zárt intervallumokkal, amelyek hossza legfeljebb . Jelölje I1 ; I2 ; : : : ; Im azokat az intervallumokat (Ij = [ j ; j ]), amelyekben je (x)j eléri a maximumát, En (f )-et. Ha x 2 Ij és e (x ) = En (f ), akkor minden x 2 Ij esetén e (x) En (f ) =2. Ha x 2 Ij és e (x ) = En (f ), akkor minden x 2 Ij esetén e (x) En (f ) =2. Ez azt jelenti, LEGJOBB EGYENLETES APPROXIMÁCIÓ POLINOMOKKAL

73

hogy ezekben az intervallumokban e (x) el½ojele állandó. Mivel van köztük pozitív és negatív el½ojel½u intervallum, azt kell igazolnunk, hogy kiválaszthatunk n + 2 intervallumot, hogy köztük legyen n + 1 darab el½ojelváltás. Azt fogjuk kimutatni, hogy ha kevesebb mint n + 1 el½ojelváltás van, akkor találhatunk egy polinomot, amelynek az f -t½ol való eltérése kisebb mint En (f ). 5) Az egyszer½uség kedvéért tegyük fel, hogy az I1 -ben e (x) el½ojele pozitív (a másik eset tárgyalása hasonló). Csoportosítsuk az egymást követ½o Ij intervallumokat e (x) el½ojele szerint: csoport 1 2 3 .. . k

intervallum I1 ; I2 ; : : : ; Ij1 Ij1 +1 ; Ij1 +2 ; : : : ; Ij2 Ij2 +1 ; Ij2 +2 ; : : : ; Ij3 .. . Ijk

1 +1

; Ijk

1 +2

el½ojel pozitív el½ojel [e (x) > 0] negatív el½ojel [e (x) < 0] pozitív el½ojel .. .

; : : : ; Ijk

A fenti táblázatban Ijk = Im . A táblázat k 1 el½ojelválást mutat az Ij` és Ij` +1 intervallumok között. Tegyük fel, hogy k 1 < n + 1, vagy k < n + 2. Az Ij` és Ij` +1 intervallumok nem lehetnek szomszédosak, mert e (x) ellenkez½o el½ojel½u a két intervallumban (nem beszélve arról, hogy a két intervallumbeli függvényértékek távolsága legalább En (f )). Tehát a Bolzano tétel miatt létezik olyan j` < x` < j` +1 szám, ahol e (x` ) = 0 (` = 1; : : : ; k 1) 6) De…niáljuk a q (x) = (x1 x) (x2 x) (xk 1 x) polinomot! q (x) legfeljebb n-ed fokú, q (x) = 0 , x = xi . Az 1: csoport intervallumai felett q (x) > 0, a 2: csoport intervallumai felett q (x) < 0, a 3. csoport intervallumai felett q (x) > 0 és így tovább. Általában igaz, hogy sign(q (x)) =sign(e (x)), ha x 2 Ij , valamely j-re. 7) Legyen J az [a; b] n [m i=1 Ji halmaz lezárása. Ekkor igaz (a konstrukció miatt), hogy max je (x)j = En0 < En (f ) : x2J

Legyen 0< Vegyük észre, hogy jq (x)j =

<

En (f ) En0 : 2 kqkC

(En (f ) En0 ) jq (x)j 2 kqkC

En (f ) 2

En0

:

8) Vizsgáljuk az f (x) és p (x) + q (x) eltérését! Legyen x 2 [m i=1 Ji ! Ekkor a sign (e (x)) = sign (q (x)) összefüggés miatt kapjuk, hogy sign(e (x)) > 0 esetén En (f ) <

En (f ) 2

En0

q (x) < f (x) p (x) | {z }

q (x) < En (f ) ;

e(x)

74


míg sign(e (x)) < 0 esetén En0

En (f ) 2

q (x) < jq (x)j

En (f ) < e (x)

< En (f ) :

Az x 2 J értékekre kapjuk, hogy egyrészt e (x)

En0 +

q (x)

En0

En (f ) 2

=

En (f ) + En0 < En (f ) ; 2

másrészt pedig En (f ) <

En (f ) + En0 = 2

En0

En (f ) 2

En0

e (x)

q (x) :

Tehát minden x 2 [a; b] esetén jf (x)

p (x)

q (x)j < En (f ) ;

ami ellentmondás. Tehát kell, hogy legyen legalább n + 1 el½ojelváltás. Ezzel a tételt igazoltuk. Következmény: Ha van n+1 olyan xj pontunk, ahol e (xj ) = 0, akkor Lagrange-interpolációval el½oállíthatjuk a legjobban approximáló polinomot. Márpedig a fenti tétel szerint van, csak éppen meg kellene ½oket határozni, ami nem egyszer½u. Tétel: Legyen f 2 C [a; b]. Az f függvényt legjobban approximáló p 2 Pn polinom egyértelm½u. Bizonyítás: Tegyük fel, hogy van két legjobban approximáló polinom p; q 2 Pn , p 6= q. Ekkor 1 (p + q) is legjobban approximáló polinom, mert 2 f (x)

1 (p (x) + q (x)) 2

1 jf (x) p (x)j + {z } 2| En (f )

1 jf (x) q (x)j {z } 2|

En (f ) :

En (f )

Mármost Csebisev el½obbi tétele miatt van n + 2 darab különböz½o xk pont, hogy 1 (p (xk ) + q (xk )) = 2

f (xk ) Ez csak akkor lehetséges, ha jf (xk ) f (xk )

p (xk )j = jf (xk )

p (xk ) = f (xk )

En (f ) :

q (xk )j = En (f ) és

q (xk ) =

En (f ) :

Ebb½ol viszont következik, hogy p (xk ) = q (xk ) teljesül n + 2 helyen, ami csak akkor lehetséges, ha p (x) q (x). Tétel (Ch. del la Vallée-Poussin): Legyen f 2 C [a; b], q 2 Pn és tegyük fel, hogy létezik n + 2 darab xk pont, hogy a x1 < x 2 < < xn+2 b (3.38) és sign (f (xk )

q (xk )) = ( 1)k

(k = 1; 2; : : : ; n + 2) ;


(3.39) 75

vagy sign (f (xk )

q (xk )) = ( 1)k+1

(k = 1; 2; : : : ; n + 2) ;

(3.40)

teljesül, akkor En (f )

min jf (xk )

q (xk )j :

min jf (xk )

q (xk )j

1 k n+2

(3.41)

Bizonyítás: Tegyük fel, hogy En (f ) <

1 k n+2

és jelöljük p (x)-el az f -et legjobban approximáló polinomot, amire teljesül, hogy jf (x)

p (x)j

(x 2 [a; b]) :

En (f )

Tehát minden xk pontban sign (p (xk )

q (xk )) = sign ([f (xk ) q (xk )] [f (xk ) = sign (f (xk ) q (xk )) :

p (xk )])

Tehát vagy q (xk )) = ( 1)k

sign (p (xk )

(k = 1; 2; : : : ; n + 2) ;

vagy sign (p (xk )

q (xk )) = ( 1)k+1

(k = 1; 2; : : : ; n + 2) :

Eszerint xk és xk+1 között van egy olyan yk pont, amelyre p (yk ) = q (yk ) De ez azt jelenti, hogy p (x)

(k = 1; 2; : : : ; n + 1) :

q (x), ami ellentmondás. Tehát a tétel állítása helyes.

Tétel: Tegyük fel, hogy f 2 C [a; b], p 2 Pn és létezik n + 2 darab xk pont úgy, hogy a

x1 < x 2 <

< xn+2

(3.42)

b

és f (xk )

p (xk ) = ( 1)k kf

pkC

(k = 1; 2; : : : ; n + 2)

vagy f (xk )

p (xk ) = ( 1)k+1 kf

pkC

(k = 1; 2; : : : ; n + 2)

(3.43)

teljesül. Akkor p az f legjobb approximációja. Bizonyítás: Az állítás az el½oz½o tételb½ol kövekezik, mert kf

pkC

En (f )

min jf (xk )

1 k n+2

p (xk )j = kf

pkC :

Az eddigi tételek zömét a következ½o tételben is szokás összefoglalni. 76


Tétel (Csebisev, de la Vallée-Poussin): A p (x) 2 Pn polinom akkor és csak akkor a legjobban közelít½o polinom, ha létezik n + 2 pont: a x1 < x2 < : : : < xn+2 b; úgy, hogy jf (xi ) f (xi )

p (xi )j = kf

p (xi ) =

p kC

[f (xi+1 )

(3.44)

(i = 1; : : : ; n + 2) ;

p (xi+1 )]

(3.45)

(i = 1; : : : ; n + 1) :

fxi gn+2 i=1

A tételbeli pontokat alternáló ponthalmaznak nevezzük. Vegyük észre, hogy a fejezet bevezet½o két példájában éppen az alternáló ponthalmazokat határoztuk meg. A Csebisev-féle jellemzés kiterjeszthet½o más normákra és általánosabb bázisfügvényekre is. Ezekkel itt nem foglalkozunk. A Csebisev-tételt felhasználva igazolhatjuk a következ½o eredményt az En (f ) mértékér½ol. Tétel: Ha f 2 C n+1 [ 1; 1] és p 2 Pn az ½ot legjobban approximáló polinom, akkor En (f ) = kf

pkC =

1 f (n+1) ( ) ; 2n (n + 1)!

(3.46)

ahol 2 ( 1; 1). Bizonyítás: A p legjobban approximáló polinom el½oállítható valamely x0 ; x1 ; : : : ; xn 2 [ 1; 1] alappontokon de…niált Lagrange interpolációs polinomként. A Cauchy-féle hiba tétel alapján f (x) ahol

x

p (x) = (x

x0 ) (x

x1 )

(x

2 ( 1; 1). Ezért kf

pkC

k(x

x0 ) (x

x1 )

(x

xn )kC

k(x

x0 ) (x

xn )

f (n+1) ( x ) ; (n + 1)!

minx2[

f (n+1) (x) : (n + 1)! 1;1]

Igazolható, hogy k(x

x0 ) (x

x1 )

(x

xn )kC

x1 )

(x

xn )kC =

1 ; 2n

ahol xj a Tn+1 (x) Csebisev polinom gyökét jelöli. Ezért kf

pkC

1 minx2[ 1;1] f (n+1) (x) : 2n (n + 1)!

Ha most p (x) jelöli az f függvény Tn+1 (x) gyökein de…niált Lagrange interpolációs polinomját, akkor maxx2[ 1;1] f (n+1) (x) kf p kC k(x x0 ) (x x1 ) (x xn )kC (n + 1)! (n+1) (x) 1 maxx2[ 1;1] f : n 2 (n + 1)! Az 1 minx2[ 1;1] f (n+1) (x) 1 maxx2[ 1;1] f (n+1) (x) kf pkC kf p kC 2n (n + 1)! 2n (n + 1)! (n+1) egyenl½otlenség és f folytonossága miatt az állítás innen már következik. LEGJOBB EGYENLETES APPROXIMÁCIÓ POLINOMOKKAL

77

3.1.3. Remez algoritmusok A Csebisev-féle geometriai jellemzés lehet½ové teszi a legjobban approximáló polinom meghatározását. A következ½okben megismerjük Remez algoritmusait, amelyek alapját képezik a ma is használatos eljárásoknak. Számos algoritmus kiindulópontja a legjobb approximációs feladat megoldása egy véges ponthalmazon. Legyen Xm = fxi gm i=1 véges ponthalmaz az [a; b] intervallumban. A p (x) 2 Pn polinom az f (x) függvény diszkrét legjobb approximácója, ha En (f; Xm ) = max jf (x) x2Xm

p (x)j

max jf (x)

x2Xm

p (x)j ;

p 2 Pn :

(3.47)

Igazolható, hogy m n + 2 esetén létezik pontosan egy legjobb approximáció és (legalább) egy Xn+2 Xm alternáló ponthalmaz úgy, hogy f (xj )

p (xj ) = ( 1)j sEn (f; Xm ) ;

xj 2 Xn+2 , j = 1; : : : ; n + 2, s =

1:

(3.48)

Ha m = n+2, akkor az alternáló tulajdonság alapján könnyen meghatározhatjuk a legjobban approximáló polinomot, ui. p (x) együtthatói és az sEn (f; Xn+2 ) mennyiség kielégítik a n X

ai xij + ( 1)j sEn (f; Xn+2 ) = f (xj )

(j = 1; : : : ; n + 2)

(3.49)

i=0

lineáris egyenletrendszert. Az m > n + 2 esetben a legjobban közelít½o polinom meghatározása többféleképpen is lehetséges. Az En (f; Xm ) = max En (f; Xn+2 ) (3.50) Xn+2 Xm

összefüggés alapján kiválasztjuk az összes Xn+2 Xm részhalmazt, ezekre meghatározzuk a legjobban approximáló polinomot,ill. a legjobb approximáció mértékét, az En (f; Xn+2 )-t. Az Xm halmazon legjobban approximáló polinomot, ill. Xn+2 alappontrendszert azon Xn+2 alappontrendszer határozza meg, amelyre fennáll max

Xn+2 Xm

En (f; Xn+2 ) = En f; Xn+2 :

(3.51)

Ha ezt a maximumot több Xn+2 alappontrendszer is eléri, akkor tetszés szerint lehet közülük választani. m Tekintettel arra, hogy n+2 különböz½o eset van, a diszkrét approximációs feladat fenti megoldása sok számítást igényelhet. A lineáris programozási eljárást javasolják a fenti feladat megoldására. Legyen = max jf (x) x2Xm

78

p (x)j :


Ez ekvivalens az

n X

f (xj )

ai xij

(j = 1; : : : ; m)

i=0

feltétellel. Az approximációs feladat tehát átmegy a ! min Pn i + Pi=0 ai xj f (xj ) (j = 1; : : : ; m) n i a x f (xj ) (j = 1; : : : ; m) i=0 i j

lineáris programozási feladatba, amelynek megoldására rendkívül hatékony eljárások és programok ismeretesek. Remez els½o algoritmusa Az f 2 C [a; b] függvény [a; b] intervallumbeli (nem diszkrét) approximálása úgy történik, hogy az [a; b] intervallumot felosztjuk az xk = a + k

b

a

(k = 0; : : : ; N ) N pontokkal és erre meghatározzuk a legjobban közelít½o diszkrét polinom approximációt. Megmutatható, hogy ha N elég nagy, akkor a diszkrét polinom approximáció jól közelíti az elméletileg legjobb polinom approximációt. Gyakorlati célokra a Remez eljárás gyorsabb konvergenciájú változatait használják. Remez második algoritmusa (i) Legyen x0 ; x1 ; : : : ; xn+1 2 [a; b] tetsz½oleges páronként különböz½o pont; (ii) Oldjuk meg az a0 + a1 x0 + a2 x20 + a0 + a1 x1 + a2 x21 + a0 + a1 x2 + a2 x22 + .. .

+ an xn0 + an xn1 + an xn2

a0 + a1 xn+1 + a2 x2n+1 +

f (x0 ) f (x1 ) f (x2 )

+ an xnn+1

= = = .. .

+" " +" .. .

f (xn+1 ) = ( 1)n+1 "

lineáris egyenletrendszert az a0 ; a1 ; : : : ; an és " ismeretlenekre. A rendszer megoldása a p (x) = a0 + a1 x + + an xn polinomot de…niálja. (iii) Határozzuk meg a p (x) f (x) függvény [a; b] intervallumbeli yi széls½oértékhelyeit, majd ezekkel az (i) pontbeli xi -ket helyettesítve ismételjük meg a (2) lépést! Az eljárás konvergens. Az eljárás kvadratikus konvergenciáját 1960-ban Veidinger László igazolta. A gyakorlatban a kezd½o xi pontokként az xi =

a+b b a + cos 2 2

i n+1

(i = 0; 1; : : : ; n + 1)

Csebisev alappontokat javasolják. Az eljárás hatékony implementálásához további megfontolások szükségesek. A Remez algoritmusok kiterjeszthet½ok más esetekre is. LEGJOBB EGYENLETES APPROXIMÁCIÓ POLINOMOKKAL

79

3.2. A Stone-Weierstrass tétel A Weierstrass-tétel azt mondja ki, hogy a polinomok halmaza s½ur½u a C [a; b] térben. A StoneWeierstrass tétel(ek) a Weierstrass-tétel messzemen½o általánosítása(i). A tételt a C [0; 1] függvényekre és a Csebisev normára mondjuk ki, de tetsz½oleges [a; b] korlátos és zárt intervallum, vagy akár metrikus terekben is kimondható. De…níció: A C [0; 1] vektor tér tetsz½oleges A lineáris alterét (rész)algebrának nevezzük, ha minden f; g 2 A esetén f g 2 A is teljesül. Példa: C [0; 1] algebra, a polinomok halmaza algebra. Az A halmaz lezárását A jelöli. A az A halmaz limeszpontjait jelöli. Ha A algebra, akkor A is az. Tétel (Stone-Weierstrass, 1937): Legyen A C [0; 1] részalgebra, amelyre a következ½ok teljesülnek: (a) A tartalmazza a konstans függvényeket; (b) A elválasztja [0; 1] pontjait, azaz minden x; y 2 [0; 1] és x 6= y esetén van olyan f 2 A, hogy f (x) 6= f (y). Ekkor A s½ur½u C [0; 1]-ben, azaz A = C [0; 1]. Bizonyítás: A tétel igazolását több lépésben végezzük el. (1) A Weierstrass-tétel miatt (lásd pl. Bernstein-féle bizonyítást) minden " > 0 esetén van olyan p polinom, hogy jp (t) jtjj < " minden t 2 [ 1; 1]. 1. Adott " > 0 esetén létezik (2) Ha f 2 A, akkor jf j 2 A. Feltehetjük, hogy kf kC p polinom, hogy jp (t) jtjj < " (t 2 [ 1; 1]). Ekkor viszont jp (f (u)) jf (u)jj < " minden u 2 [0; 1] esetén. Tehát kp (f ) jf jkC < ". De p (f ) 2 A és jf j 2 A. (3) Ha f; g 2 A, akkor max ff; gg 2 A és min ff; gg 2 A. Az állítás a f + g jf gj f + g jf gj + ; min ff; gg = 2 2 2 2 összefüggésekb½ol és A algebra voltából következik. (4) Az (a) és (b) feltételekb½ol következik, hogy x; y 2 [0; 1], x 6= y esetén tetsz½oleges számokhoz mindig van olyan hxy 2 A, amelyre max ff; gg =

hxy (x) = ;

és

hxy (y) = :

A (b) feltevés szerint van g 2 A, hogy g (x) 6= g (y). Ekkor a hxy (t) =

g (t) g (x)

g (y) g (x) + g (y) g (x)

g (t) = g (t) + g (y)

2A

függvény megfelel a kívánalmaknak (az (a) feltétel miatt). (5) Legyen f 2 C [0; 1] és " > 0 tetsz½oleges. Tetsz½oleges x; y 2 [0; 1], x 6= y esetén van olyan hxy (z) 2 A, hogy " hxy (x) = f (x) + 2 " hxy (y) = f (y) : 2 80


Minden x 6= y esetén legyen Uxy = fz 2 [0; 1] : hxy (z) < f (z) + "g : Az f és hxy folytonossága miatt Uxy [0; 1] nyílt halmaz. x; y 2 Uxy miatt [y2[0;1]nfxg Uxy = [0; 1]. A Heine-Borel tétel kimondja, hogy egy korlátos és zárt ponthalmazt bármilyen módon is fedjük be végtelen sok nyílt halmazzal, ezek közül mindig kiválasztható véges sok, amelyek a halmazt szintén befedik. Esetünkben tehát van véges sok y1 ; y2 ; : : : ; yn 2 [0; 1] pont, hogy [ni=1 Uxyi = [0; 1]. A (3) lépés szerint gx = mini hx;yi 2 A. A konstrukció miatt " gx (x) = f (x) + : 2

Minden x 2 [0; 1] esetén legyen Vx = fz 2 [0; 1] : gx (z) > f (x)g ; ahol gx az el½obb de…niált függvény. Az f és gx folytonossága miatt Vx nyílt halmaz, és x 2 Vx . Ezért [x2[0;1] Vx = [0; 1] és létezik véges sok x1 ; x2 ; : : : ; xn 2 [0; 1] pont, hogy [ni=1 Vxi = [0; 1]. Legyen g (z) = max gxi (z) 2 A: i

A konstrukció miatt g > f . Másrészt a gx (x) < f (x) + " miatt g < f + ". A tétel néhány alkalmazása: a) A [0; 1]-en végtelen sokszor di¤erenciálható függvények s½ur½uek C [0; 1]-ben. b) A trigonometrikus polinomok s½ur½uek C [0; 2 ]-n (Weierstrass 2. tétele).

3.3. Feladatok 1. Határozza meg az f (x) = ex (x 2 [0; 1]) legjobban közelít½o els½ofokú polinomját! 2. Határozza meg az f (x) = jxj függvényt legjobban approximáló másodfokú polinomot az X5 = 1; 21 ; 0; 12 ; 1 ponthalmazon (p (x) = x2 + 81 ). 3. A Pn C [a; b] altér dimenziója n + 1. Miért? 4. Igazoljuk, hogy LipK a C [a; b] zárt részhalmaza a Csebisev normában. P 5. Legyen a p (x) = a0 + a1 x + + an xn 2 Pn polinom normája kpk1 = nk=0 jak j. Igazoljuk, hogy léteznek olyan 0 < An ; Bn < 1 konstansok, hogy An kpk1

kpkC

Bn kpk1 :

Függ-e An és Bn an n-t½ol? És az [a; b] intervallumtól? 6. Tegyük fel, hogy f 2 C 2 [a; b] és f 00 (x) > 0 (x 2 [a; b]). Igazoljuk, hogy f legjobb els½ofokú polinom approximációja a0 + a1 x, ahol a0 = f 0 (c), a1 = [f (a) + f (c) + f 0 (c) (a + c)] =2, ahol c az f 0 (c) = (f (b) f (a)) = (b a) egyenlet egyetlen megoldása! FELADATOK

81

7. Igazoljuk, hogy f; g 2 C [a; b] esetén kf gkC kf kC kgkCp ! 8. p Határozzuk meg a (c1 ; c2 ) = max0 x 1 jc1 x + c2 xj függény minimumát! Mennyi E1 ( x) értéke? P 9. Legyen az L operátor alakja (Lf ) (x) = ni=1 f (xi ) gi (x), ahol a x1 < x2 < xn b és gi 2 C [a; b]. Igazoljuk, hogy L akkor és csak akkor monoton, ha gi (x) 0 (x 2 [a; b]) teljesül minden i-re! 10. Igazoljuk, hogy a Hermite-Fejér interpolációs operátor akkor és csak akkor monoton a C [ 1; 1]-en, ha az xi interpolációs alap pontokra teljesül, hogy 1 1

xi

2

n X j=1 j6=i

1 xi

1 : 1 + xi

xj

11. A C [a; b]-n értelmezett L operátort nemnegatívnak nevezzük, ha minden f 0 esetén Lf 0. Igazoljuk, hogy lineáris operátorok esetén a nemnegativitás és a monotonitás ekvivalensek! 12. Igazoljuk, hogy kBn (f )kC kf kC ! 13. (Painlevé, 1898). Igazoljuk, hogy ha f; f 0 2 C [a; b], akkor minden " > 0 esetén van olyan p polinom, hogy kf pkC < " és kf 0 p0 k < "! 14. Legyen fn0 (x) = 1 és fnm (x) = x x

1 n

x

2 n

x

m

1 n

(m

1) :

Igazoljuk, hogy Bn (fnm ) (x) = fnm (1)P xm ! n 15. Legyen E (f ) = minc1 ;c2 ;:::;cn kf i=1 ci 'i k! Igazoljuk a következ½oket! (a) E ( f ) = j j E (f ); (b) E (f + g) E (f ) + E (g);P (c) E (f + g) = E (f ), ha g = nj=1 j 'j ; (d) E folytonos; (f) E (f ) kf k; P (g) E (f + g) ! 1, ha ! 1 és g 6= nj=1 j 'j . Melyik tulajdonsághoz kell, hogy f'j gnj=1 unisolvens legyen? 16. A Jackson tétel felhasználásával adjon becslést En (f ) értékére, ha f (x) = jxj! 17. Igazoljuk, hogy Lip a C [a; b] lineáris altere, amely zárt a következ½o m½uveletekre: (f _ g) (x) = max (f (x) ; g (x)) (f ^ g) = min (f (x) ; g (x)) jf j (x) = jf (x)j (f g) (x) = f (x) g (x) : 18. Igaz-e, hogy minden C [a; b]-beli f függvény kielégít egy jf (x) f (y)j A jx yj ( > 0) alakú Lipschitz feltételt? 19. De…niáljuk az fn (x) = n1 sin (nx) függvénysorozatot a [0; 2 ]intervallumon! Hova konvergál egyenletesen fn ? Mit tudunk mondani az fn0 sorozatról? Konvergál (limn fn )-hez? 82


20. Legyen f 2 C 1 [a; b]. Igazoljuk, hogyR ha a p (x) polinom az f 0 függvényt " > 0 pontosságx gal approximálja [a; b]-n, akkor q (x) = a p (t) dt + f (a) olyan polinom, amely f -et (b a) " pontossággal approximálja az [a; b] intervallumon! q p 1 21. Hasonlítsuk össze B4 x; 2 értékét 12 -el! 22. Igazoljuk Voronovsky tételét az f (x) = ex esetben direkt számítással! 23. Oldjuk meg a max0 x 1 jex ax bj = min feladatot! 24. Oldjuk meg a mina max0 x 1 jx4 axj feladatot! Egyértelm½u-e a megoldás? 25. Legyen f (x) = 0, ha 1 x 0 és f (x) = 1, ha 0 < x 1. Határozzuk meg a min

g2C[ 1;1]

max jf (x) 1 x 1

g (x)j

kifejezés értékét! R1 26. Elemezzük a max 1 x 1 j1 f (x)j = min feladatot, ahol f 2 C [ 1; 1] kielégíti a 1 f (x) dx = 0 mellékfeltételt! p 27. Igazoljuk, hogy a 1 + x2 legjobb els½ofokú polinom approximációja a [0; 1] intervallumon 0:955 + 0:414x! p 28. Mi a 1 + x3 függvény legjobb lineáris approximációja [0; 1]-en? 29. Elemezzük a mina;b max0 x 1 jx a sin bxj feladatot! 30. Határozzuk meg a min max x3 + ax2 + bx + c a;b;c2R

1 x 1

feladat megoldását! 31. Az f (x) = tan x (x 2 0; 4 ) függvényhez keressük meg a legalacsonyabb fokú Bernstein polinomot, amelyre teljesül, hogy max jtan x

0 x

Bn (x)j <

=4

1 : 10

Erre az n értékre, adjuk meg konkrétan a polinomot is! 9 32. Igaz, vagy hamis, hogy a p (x) = (e 1) x + 10 polinomra teljesül, hogy max jex

0 x 1

p (x)j

max jex

0 x 1

p (x)j

(p 2 P1 )?

33. Számítsuk ki az alábbi mimimum értékeket és a megfelel½o optimális els½ofokú polinomokat: p min max jex p (x)j ; min max x p (x) : p2P1 0 x 1

p2P1 0 x 1

34. Határozzuk meg a következ½o minimum értéket és a hozzátartozó min max x3 + x + ; 2R 0 x 1

és

értékekeket:

:

35. Határozzuk meg az f (x) = x2 (x + 1) (2x 1) (x 2) függvényt az [ 1; 2] intervallumon legjobban egyenletesen approximáló p4 (x) polinomot és az eltérés Csebisev normáját! FELADATOK

83

36. Határozzuk meg az f (x) = jx + 1j függvényt a [ 2; 2] intervallumon legjobban egyenletesen közelít½o p2 (x) polinomot és az eltérés Csebisev normáját! 37. Legyen f (x) = ex (x 2 [ 1; 1]). Igazoljuk, hogy e 12 n (n + 1)!

En (f )

e2 n (n + 1)!

és hasonlítsuk ezt össze ex Taylor sorának részösszegeivel! 38. Igazoljuk, hogy a tan x függvény [ =4; =4] intervallumon vett legjobb 13-ad fokú egyenletes approximációs polinomja 1:00000014609x + 0:333324808x3 + 0:13347672x5 + 0:0529139x7 + 0:0257829x9 + 0:0013562x11 + 0:010269x13 ; amelynek abszolut hibája 8 10 9 ! Ábrázoljuk is a két függvényt, illetve a hibafüggvényt! 39. Igazoljuk, hogy az (x x0 ) (x x1 ) függvény deriváltjának pontosan egy zérushelye van az [x0 ; x1 ] intervallum középpontjában és határozzuk meg a max j(x

x0 x x1

x0 ) (x

x1 )j

értékét! 40. Határozzuk meg jxj legjobb legfeljebb harmadfokú polinom approximációját a [ 1; 1] intervallumon? ( 81 + x2 ?) 41. Legyen pn 2 Pn a sin 2x függvényt a [ 1; 1] intervallumon legjobban approximáló polinom. Igazoljuk, hogy 0 < sin

x 2

n+1

pn (x)

C

4

2 : (n + 1)!

42. Legyen ax + b az 1=x függvényt az [ ; ] intervallumon (0 < < ) legjobban approximáló polinom! Igazoljuk, hogy 2 1 1 1 1 p +p ; b= a= 2 és

2

Igazoljuk, hogy a maximális hiba az m;

1 1 1 1 p p = . x 2 p pontokban van! és az

84


max ax + b x

4. fejezet Racionális approximáció, Padé approximáció Legyen R (m; n) mindazon r (x) = p (x) =q (x) alakú racionális törtfüggvények halmaza, ahol p (x) 2 Pm , q (x) 2 Pn és a p(x) és q (x) polinomoknak nincs közös zérushelyük. Az f 2 C [a; b] függvények a0 + a1 x + : : : + am x m (4.1) r (x) = b0 + b1 x + : : : + bn x n alakú legjobb approximációját keressük Csebisev normában. Jegyezzük meg, hogy a polinom közelítésekt½ol eltér½oen R (m; n) nem részhalmaza C [a; b]-nek. Igazak a következ½o eredmények. Tétel: Ha f 2 C [a; b], akkor létezik legjobb egyenletes racionális approximáció, azaz olyan r (x) 2 R (m; n) racionális törtfüggvény, hogy kf

r kC

kf

De…níció: Az a x1 < x2 < : : : < xN alternáló pontoknak nevezzük, ha

rkC ;

r (x) 2 R (m; n) :

b pontokat (az f (x)

(4.2)

r (x) hibafüggvényre nézve)

jf (xj ) r (xj )j = kf rkC (j = 1; : : : ; N ) f (xj ) r (xj ) = [f (xj+1 ) r (xj+1 )] (j = 1; : : : ; N

1)

:

(4.3)

Tétel: Legyen adott f (x) 2 C [a; b]. Az r (x) = p (x) =q (x) 2 R (m; n) racionális törtfüggvény akkor és csak akkor az f függvény legjobb egyenletes approximációja, ha az f (x) r (x) függvénynek létezik egy N = 2 + max fn + @p; m + @qg pontból álló alternáló ponthalmaza ( @p a p (x) fokszáma, @q a q (x) fokszáma). Tétel: A legjobb egyenletes racionális approximáció egyértelm½u. A racionális törtfüggvények sok esetben a polinomoknál lényegesen jobb approximációt szolgáltatnak. Ezért széles körben használják speciális függvények kiszámítására. Legyen Em;n = Em;n (f; [a; b]) = kf r kC a legjobb racionális approximáció hibája. Newman (1964) igazolta, hogy n > 4 és f (x) = jxj esetén En;n (f; [ 1; 1])

3e

RACIONÁLIS APPROXIMÁCIÓ, PADÉ APPROXIMÁCIÓ

p

n

;

(4.4) 85

ha n páros és En+1;n

1

(f; [ 1; 1])

3e

p

n

(4.5)

;

ha n páratlan. Polinomok esetén En (f ) > c=n, ahol c konstans. Minthogy elég nagy n-re p 3e n c=n, az jxj függvény racionális approximációjának hibája lényegesen kisebb, mint a polinom approximációé. Ezt az eredményt Turán Pál és Szüsz Péter kiterjesztette a [ 1; 1] intervallumon szakaszonként analitikus (és egyébként folytonos) függvényekre. A legjobb racionális approximációt a Remez-módszer általánosításaival lehet meghatározni. Ezekkel itt nem foglalkozunk.

4.1. A Padé-approximáció Függvények Padé-approximációja egy racionális közelít½o függvény, amelyet az x = 0 pont környezetében sorfejtés segítségével de…nálunk. A Padé-approximáció általában nem azonos a legjobb racionális approximációval. Tegyük fel, hogy az f függvénynek létezik az x = 0 körüliTaylor-sora 1 X f (x) = cj xj (4.6) j=0

és legyen

Rmk (x) =

p (x) ; q (x)

(4.7)

ahol p (x) = a0 + a1 x + : : : + am xm ; q (x) = b0 + b1 x + : : : + bk xk és b0 6= 0. Az általánosság megszorítása nélkül feltehetjük, hogy bk = 1. Vizsgáljuk az Pm Pk P1 j j j j=0 aj x j=0 bj x j=0 cj x p (x) (4.8) f (x) = Pk j q (x) j=0 bj x

különbséget. El½oírjuk, hogy az eltérés mértéke f (x)

p (x) = O xm+k+1 q (x)

legyen. Ezt úgy lehet elérni, hogy teljesül ! k ! 1 X X cj xj bj x j j=0

j=0

m X

j

aj x =

j=0

(4.9)

1 X

dj xj :

(4.10)

j=m+k+1

Tehát a baloldalon x els½o m + k + 1 hatványának együtthatója el kell hogy t½unjön. Minthogy 0 1 ! k ! minft;kg 1 1 X X X X @ cj xj bj x j = c t i bi A x t ; j=0

86

j=0

t=0

i=0


az els½o m + k + 1 együttható akkor lesz zérus, ha minft;kg

X

c t i b i = at

(4.11)

(t = 0; : : : ; m) ;

i=0

minft;kg

X

c t i bi = 0

(4.12)

(t = m + 1; : : : ; m + k) :

i=0

Ha ennek az egyenletrendszernek van megoldása, akkor Rm;k (x) az f függvény (m; k) index½u Padé-féle approximációja. Noha a Padé-approximáció általában nem azonos a legjobb racionális közelít½o függvénnyel, sok esetben igen jó közelítést szolgáltat az x = 0 pont egy környezetében (tehát lokálisan, mint a Taylor-sor). Példa: Legyen f (x) = 1 21 x + 13 x2 + : : : és m = k = 1. Ekkor b0 = 1, c0 = 1, c1 = 12 , c3 = 13 és a vonatkozó egyenletrendszer c0 b0 = 1 = a0 ; 1 + b 1 = a1 ; c 1 b0 + c 0 b1 = 2 1 1 b1 = 0: c 2 b0 + c 1 b1 = 3 2 Ennek megoldása a0 = 1, a1 =

1 6

és b1 = 23 . Tehát az f függvény (1; 1) index½u Padé közelítése R11 (x) =

1 + 16 x ; 1 + 23 x

amelynek hibája O (x3 ). Az ex függvény Padé approximációi igen fontosak egy sor más területen, például implicit Runge-Kutta módszerek stabilitásánál is. Az ex Padé-approximációja (Padé, 1892) felírható a következ½o általános alakban (is): Pm (m+k j)!m! j j=0 j!(m j)! x : (4.13) Rmk (x) = Pk (m+k j)!k! j j=0 j!(k j)! ( x) Az ex els½o néhány Padé-approximációja: R22 (x) = R31 (x) =

12 + 6x + x2 ; 12 6x + x2

24 + 18x + 6x2 + x3 ; 24 6x

R13 (x) =

24

R33 (x) =

24 + 6x 18x + 6x2

x3

;

120 + 60x + 12x2 + x3 : 120 60x + 12x2 x3

(4.14) (4.15)

Példa: Összehasonlítjuk az ex függvény néhány, a [0; 1] intervallumon vett közelítését. Az ex másodfokú legjobb egyenletes polinom közelítése p (x) = 1:008934 + 0:855897x + 0:844519x2 ; A PADÉ-APPROXIMÁCIÓ

87

ahol az együtthatók pontossága 10 6 . A további közelítések: az R22 (x) =

12 + 6x + x2 12 6x + x2

Padé-approximáció, a 1 q (x) = 1 + x + x2 2 másodfokú Taylor-polinom és az x1 = 0, x2 = 12 , x3 = 1 alappontokra támaszkodó Lagrange-féle interpolációs polinom r (x) = 1 + 0:876604x + 0:841679x2 : Az egyes közelítések el½ojeles hibafüggvényét (ex -közelítés) mutatja az ábra.

a p p r o x im a tio n e r r o r s to e x p ( x ) 0 .3 C hebys hev Pa d e T a y lo r Lagrange 0 .2 5

0 .2

0 .1 5

0 .1

0 .0 5

0

- 0 .0 5 0

0 .1

0 .2

0 .3

0 .4

0 .5

0 .6

0 .7

0 .8

0 .9

1

y

Itt látható, hogy a legjobb közelítést a Padé-approximáció adja (jex R22 (x)j 3:996 3 10 ). A Padé-féle közelítés hibája n½o, amint x távolodik nullától. A Taylor polinom adja a legrosszabb eredményt (jex q (x)j 0:2182 és hibája n½o, amint x távolodik az origótól. A Csebisev-féle polinomközelítésre fennáll, hogy jex p (x)j 8:934 10 3 . A hibafüggvényen a 4 alternáló pont leolvasható. A Lagrange-féle interpolációs polinom közelítésének hibája: jex r (x)j 1:4421 10 2 . Vegyük észre, hogy r (x) együtthatói igen közel vannak p (x) megfelel½o együtthatóihoz. Az r (x) esetén azonban csak 2 alternáló pont van. 88


4.2. Feladatok 1. Az f (x) = ex függvény (2; 2) index½u Padé-féle közelítése R22 (x) =

12 + 6x + x2 : 12 6x + x2

Igazoljuk, hogy ez tényleg a (2; 2) index½u Padé-approximáció! Mekkora a maximális hibája a [ 1; 1] és a [ 3; 3] intervallumon? Ábrázoljuk a hibafüggvényt! 2. Igazoljuk, hogy nem minden C [ 1; 1]-beli függvényhez létezik ax= (b jxj + c) alakú legjobb racionális approximáció. [segítség: legyen f szakaszonként lineáris függvény, úgy, hogy f ( 1) = f (1) = 0 és f (1=2) = f ( 1=2) = 1.] 3. Igazoljuk, hogy nem mindig van legjobb racionális approximáció, ha az kf k = maxi jf (xi )j félnormát használjuk! [segítség: legyen x0 = 0, x1 = 1, f (x0 ) = 1, f (x1 ) = 0, r (x) = a= (bx + c).] 4. Vezessük le a 60x 7x3 sin x 60 + 3x2 Padé-approximációt és becsüljük meg a hibáját! p 3 5. Határozzuk meg a x + 8 függvény (2; 2)-rend½u Padé-approximációját és becsüljük a hibáját! 6. Igazoljuk, hogy ha P=Q az ex klasszikus (n; n)-rend½u Padé approximációja az x = 0 pontban, akkor Q (x) = P ( x)! 7. Igazoljuk, hogy a tan x függvény [ =4; =4] intervallumon vett legjobb egyenletes racionális approximációja harmadfokú számlálóval és negyedfokú nevez½ovel a 0:9999999328x 0:095875045x3 1 0:429209672x2 + 0:009743234x4 függvény, amelynek abszolut hibája 7 10 9 ! Ábrázoljuk is a két függvényt, illetve a hibafüggvényt! Hány m½uvelet kell a fügvényérték kiszámításához, szemben a 13-ad fokú polinom közelítés m½uveletszámával? 8. Határozzuk meg Remez algoritmusával az 1= (1 + x2 ) függvényt p a [ 1; 1] p intervallumon legjobban approximáló legfeljebb harmadfokú polinomot az 1; 21 2; 0; 21 2; 1 alappontokból kindulva! 9. Igazoljuk, a 2= (x + 2) függvény [ 1; 1]-beli legjobb els½ofokú polinom approximációja p hogy 1 1 p (x) = 2 2 4 x és adjuk meg a maximális hibát! 10. Határozzuk meg f (x) = x3 legjobb R (1; 1)-beli racionális approximációját a [ 1; 1] intervallumon!

FELADATOK

89

90


5. fejezet Alkalmazások: elemi függvények kiszámítási módjai Az elemi függvények kiszámítására számos módszer ismeretes. Lényeges szempont az algoritmus megbízhatósága, pontossága, numerikus stabilitása és végrehajtásának gyorsasága, ideje. A leggyakrabban használt technikák között megemlíthetjük a Taylor-sorfejtést, a Padé-approximációt, a legjobb egyenletes approximációkat, iteratív módszereket és ezek különféle kombinációit. Egyes közelítési technikák kihasználják a függvények különféle speciális (pl. periódikus) tulajdonságait is. A ma használt eljárások már olyan gyorsak, hogy a számítási id½ok összevethet½ok a multiplikatív m½uveletek számítási idejével. Néhány ismert algoritmust a technikák illusztrálására bemutatunk. ln 2 , akkor a következ½o (3; 3) index½u Padé1. ex számítása racionális törttel: Ha jxj 2 9 közelítés 9 10 pontosságot biztosít: exp (x) 2.

p

(5.1)

x számítása Newton-iterációval: yk+1 =

ahol y0

120 + 60x + 12x2 + x3 : 120 60x + 12x2 x3

p

1 2

yk +

x yk

;

(5.2)

k = 0; 1; : : :

x. Az iteráció hibájára fennáll, hogy p

p 2 j x yk j = 2 jyk j

p 2 ( x y0 ) p 2 x

p 2 x

p

2k+1

x y0 p x yk+1 : (5.3) 2 x p p Az eljárás rendkívül gyorsan (kvadratikusan) konvergál, ha jy0 xj < 2 x. Ha ez utóbbi feltétel nem teljesül, akkor az eljárás eleinte lineárisan konvergál, majd begyorsul. Az iterációs eljárás részletes elemzését a kés½obbiekben végezzük el. Egy tetsz½oleges x > 0 szám négyzetgyökének tényleges kiszámítása a következ½ oképpen p p 1 2m m történhet. A szám felírható az x = 2 X alakban, ahol X 1. Ezért x = 2 X. 4 p 1 A x függvényt az 4 ; 1 intervallumon közelítjük. Például az egyenletesen legjobban közelít½o ALKALMAZÁSOK: ELEMI FÜGGVÉNYEK KISZÁMíTÁSI MÓDJAI

91

p 1 els½ofokú polinom p (x) = 17 + 23 x. Ennek maximális eltérése x-t½ol 48 . A (5.2) iterációt ezzel 48 17 2 az y0 = 48 + 3 x értékkel kezdjük. 3. Az IEEE lebeg½opontos aritmetikai szabványt kielégít½o és a matematikai koprocesszort kihasználó eljárás ex kiszámítására a következ½o: 2 2 intervallumra úgy, hogy fennálljon i. Redukáljuk az x értéket a log 64 ; log 64 x = (32m + j) log ii. Approximáljuk az exp (R)

2 + R; 32

jRj

log

2 : 64

(5.4)

1 értéket a p (R) polinommal, ahol

p (t) = t + a1 t2 + : : : + an tn+1 :

(5.5)

iii. Rekonstruáljuk exp (x)-et az exp (x) = 2m 2j=32 + 2j=32 p (R)

(5.6)

képlettel. Az algoritmus gyors végrehajtásának érdekében a 2j=32 értékek nagy pontossággal táblázatolva vannak. 4. A 2x (0 < x < 1) kiszámítása CORDIC iterációval. Legyen ck = log2 1 + 2 k (k = 1; 2; : : :). Legyen x0 = x és képezzük a következ½o sorozatot: és ci

xi+1 = xi xi+1 = xi Ekkor

x

2 =

i+1

és 1 Y

= 0, ha xi < ci+1 , ci+1 : i+1 = 1, ha xi

1+2

k

k

;

k=1

és x

2

n Y

1+2

k

k

"n = 22

;

n

1

(ln 2) 2

n

.

k=1

A CORDIC eljárások a most bemutatotthoz hasonló jelleg½u iteratív algoritmusok, amelyeket koprocesszorokban, ill. tudományos kalkulátorokban használnak. Az eljárások alapötlete Henry Briggst½ol (1561-1631) származik. Végül megjegyezzük, hogy a sz½ukebb intervallumra való visszavezetések általában pontosságvesztést okoznak. A szabványos eljárások ezt kezelik.

5.1. Feladatok 1. ekintsük az alábbi logaritmus sorfejtéseket: log (1 + x) = x 92

x2 x3 + 2 3

x4 x5 + 4 5

:::

ALKALMAZÁSOK: ELEMI FÜGGVÉNYEK KISZÁMíTÁSI MÓDJAI

log

1+x 1 x

x3 x5 x7 =2 x+ + + + ::: : 3 5 7

(a) Az els½o kifejtéssel számoljuk ki log 2 értékét és numerikusan becsüljük a konvergencia sebességét. (b) A második sorral számoljuk ki log 2 értékét (x = 1=3) és numerikusan becsüljük a konvergencia sebességét.

FELADATOK

93

94

ALKALMAZÁSOK: ELEMI FÜGGVÉNYEK KISZÁMíTÁSI MÓDJAI

6. fejezet Függvények legkisebb négyzetes közelítése Függvények legkisebb négyzetes közelítésér½ol, approximációjáról akkor beszélünk, ha a C [a; b] halmazon értelmezett (L2 vagy L2 ) norma a következ½o

kf k2 =

Z

1 2

b

f 2 (x) w (x) dx

;

(6.1)

a

ahol a w (x) 2 C [a; b] rögzített súlyfüggvényr½ol kikötjük, hogy w (x) > 0, 8x 2 [a; b]. Fontos speciális eset: w (x) 1. Diszkrét legkisebb négyzetes közelítésr½ol beszélünk, ha a (diszkrét L2 -, vagy l2 -) norma a következ½o

kf k2 =

m X

! 12

f 2 (xi ) w (xi )

i=1

;

(6.2)

ahol a x1 < x2 < : : : < xm b adott pontok, a w (x) súlyfüggvény pedig kielégíti a m w (xi ) > 0, xi 2 Xm = fxi gi=1 feltételeket. Az L2 -, ill. l2 -norma jelentése más mint a Csebisev-normáé. Ennek illusztrálására tekintsük a [0; 1] intervallumon adott f1 (x) = 1, f2 (x) = 1 + 0:5 sin (6 x) és f3 (x) = 1 + 10e 100x függvények FÜGGVÉNYEK LEGKISEBB NÉGYZETES KÖZELíTÉSE

95

y

10 7.9433 6.3096 5.0119 3.9811 3.1623 2.5119 1.9953 1.5849 1.2589 1 0.79433 0.63096 0.50119 0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

x

Csebisev- és L2 -normáit a w (x) = 1 súlyfüggvénnyel: k:kC 1 1:5 11

f1 (x) f2 (x) f3 (x)

k:k2 1 1:0606 1:3038

Látható, hogy nagy függvényérték változás er½osen megváltoztatja a Csebisev-normát, míg az átlag jelleg½u L2 -normát alig. Ez a tulajdonság motiválja az L2 -approximáció (ill. Fouriersorfejtés) felhasználását is. Igaz a következ½o n Tétel: Legyen f 2 C [a; C [a; b] lineárisan független. Létezik Pnb] adott. Legyen f'i (x)gi=1 î 'i (x) legjobban közelít½o függvény, amelyre pontosan egy FA^ (x) = i=1 a f

n X i=1

a ^ i 'i

f

n X

ai '

i=1

2

:

(6.3)

2

A legjobb approximáció létezése következik a lineáris approximáció létezésére vonatkozó tételb½ol. Az egyértelm½uség a k:k2 norma egy tulajdonságából (szigorú konvexitásából) következik. Megjegyezzük, hogy analóg tétel igaz a diszkrét l2 -norma esetén is. Az L2 - vagy l2P -norma esetén könnyen meghatározhatjuk a legjobb approximáció a î együtn thatóit. Az kf a ' k = min feladat ekvivalens az i=1 i i 2 f

n X i=1

96

2

ai ' i

= min

(6.4)

2

FÜGGVÉNYEK LEGKISEBB NÉGYZETES KÖZELíTÉSE

feladattal. Eszerint az n-változós valós R (a1 ; : : : ; an ) =

Z

b

f (x)

a

n X

!2

aj 'j (x)

j=1

w (x) dx

(6.5)

függvény egyetlen minimumát kell meghatároznunk. Az [^ a1 ; : : : ; a ^n ]T minimumhely, ha kielégíti a rR = 0, azaz a @R (a1 ; : : : ; an ) = 0 (i = 1; : : : ; n) (6.6) @ai stacionárius egyenletrendszert. Az ai paraméter szerint deriválva kapjuk: ! Z b n X @R (a1 ; : : : ; an ) f (x) aj 'j (x) 'i (x) w (x) dx = 0: (6.7) = 2 @ai a j=1 Innen átrendezéssel kapjuk, hogy Z b Z b n X aj 'j (x) 'i (x) w (x) dx = f (x) 'i (x) w (x) dx (i = 1; : : : ; n): j=1

a

(6.8)

a

Vezessük be az hf; gi =

Z

b

f; g 2 C [a; b]

f (x) g (x) w (x) dx;

a

(6.9)

(skalárszorzat) jelölést. Ekkor a fenti egyenletrendszer alakja n X j=1

amely felírható a tömörebb

aj h'j ; 'i i = hf; 'i i (i = 1; : : : ; n); | {z } | {z }

(6.10)

ci

gij

(6.11)

Ga = c alakban, ahol a = [a1 ; : : : ; an ]T , G = [gij ]ni;j=1 , c = [c1 ; : : : ; cn ]T . A G = [h'j ; 'i i]ni;j=1 mátrixot Gram-mátrixnak nevezzük. Példa: Legyen a = 0, b = 1, w (x) 1 és 'i (x) = xi R1 xi+j 2 , gij = 0 xi+j 2 dx = 1= (i + j 1) és G=

1 i+j

(6.12) 1

(i = 1; : : : ; n). Ekkor 'i (x) 'j (x) =

n

1

;

(6.13)

i;j=1

ami nem más mint az ún. Hilbert-mátrix, amely rosszul kondicionált. Így a legkisebb négyzetes feladat megoldása reménytelen. A járható út a f'i gni=1 függvényrendszer ügyes megválasztásában rejlik. Vezessük be a következ½o fogalmakat. FÜGGVÉNYEK LEGKISEBB NÉGYZETES KÖZELíTÉSE

97

De…níció: A f'i gni=1

C [a; b] függvényrendszer ortogonális, ha h'i ; 'j i = 0;

i 6= j:

A rendszer ortonormált, ha még teljesül a h'i ; 'i i = 1 ( i = 1; : : : ; n) összefüggés is. Tétel: Tegyük fel, hogy a f'i (x)gni=1Prendszer ortonormált. Ekkor az f 2 C [a; b] függvény legjobb L2 -approximációja felírható a ni=1 hf; 'i i 'i alakban. Bizonyítás: Ortonormált rendszer esetén a Gram-mátrix azonos az egységmátrixszal és ai = hf; 'i i

(6.14)

(i = 1; : : : ; n):

Az egyértelm½u legjobb (legkisebb) négyzetes approximáció tehát felírható az n X i=1

hf; 'i i 'i

(6.15)

alakban. Legyen f' g1 C [a; b] egy ortonormált függvényrendszer. Az f 2 C [a; b] függvényi=1 Pi1 'i végtelen sort az f függvény (absztrakt, formális) Fourier-sorának hez rendelt i=1 hf; 'i i P 1 nevezzük. Jelölése: f i=1 hf; 'i i 'i . Eszerint az (6.15) kifejezés, amely f legjobb L2 approximációját adja meg, nem más mint az f (x) függvény Fourier-sorának els½o n-tagja. Nevezetes ortonormált függvényrendszerek a következ½ok. 1. C [ ; ], w (x) = 1 esetén 1 1 1 1 1 p ; p cos x; p sin x; p cos 2x; p sin 2x; : : : 2 ortonormált függvényhalmaz. p 2. C [ 1; 1], w (x) = 1= 1

x2 esetén r 1 2 p T0 ; Tn (x)

(6.16)

(6.17)

(n = 1; 2; : : :)

ortonormált függvényhalmaz, ahol (6.18)

Tn (x) = cos (n arccos x) az ún. n-edik Csebisev-polinom. Az els½o néhány Csebisev-polinom: T0 (x) = 1; T1 (x) = x; T2 (x) = 2x2 3. C [ 1; 1], w (x)

98

1 esetén r r 1 2n + 1 P0 ; Pn (x) 2 2

1; T3 (x) = 4x3

(n = 1; 2; : : :)

3x:

(6.19)

(6.20)


ortonormált függvényhalmaz, ahol 1 dn Pn (x) = n x2 n 2 n! dx

1

n

(6.21)

az ún. n-edik Legendre-polinom. Az els½o néhány Legendre-polinom: 3 P0 (x) = 1; P1 (x) = x, P2 (x) = x2 2

1 5 ; P3 (x) = x3 2 2

3 x: 2

(6.22)

Ha rendelkezésünkre áll egy ortonormált f'i (x)gni=1 függvényrendszer, akkor a legkisebb négyzetes approximáció meghatározásához (elvileg) csak az hf; 'i i ún. Fourier-együtthatókat kell kiszámolnunk. Ortogonális függvény rendszereket a Gram-Schmidt eljárással lehet meghatározni. Tétel (Gram-Schmidt eljárás): Legyen fgi gni=1 C [a; b] tetsz½oleges lineárisan független függvényrendszer ( n 2) és h ; i tetsz½oleges skalárszorzat. Legyen (6.23)

'1 = g1 ; j 1

'j+1 = gj

X hgj ; 'k i 'k ; h' k ; 'k i k=1

j = 2; : : : ; n

(6.24)

1:

A f'j gnj=1 függvényrendszer ortogonális és L (g1 ; : : : ; gn ) = L ('1 ; : : : ; 'n ). Ortonormált rendszert a 'j = (h'j ; 'j i)1=2 normalizálással kaphatunk. A Gram-Schmidt eljárás numerikusan nem stabil. Helyette az alábbi háromtagú rekurziót használjuk. Legyen hx' e0 ; ' e0 i ; (6.25) ' e0 (x) 1; ' e1 (x) x h' e0 ; ' e0 i és ' ek+1 (x) = (x ek (x) ek 1 (x) (k = 1; 2; :::; n 1); (6.26) k) ' k'

ahol

k

=

hx' ek ; ' ek i ; h' ek ; ' ek i

k

=

h' ek ; ' ek i h' ek 1 ; ' ek 1 i

(k = 1; 2; :::; n

Ekkor a f' ei (x)gni=0 polinomrendszer ortogonális, amelyb½ol a 'n (x) =

1

h' en ; ' en i1=2

' en (x)

(n = 0; 1; : : :)

1):

(6.27)

(6.28)

normálással kapjuk a f'i (x)gni=0 ortonormált polinomrendszert.

Ha az f i ; i gni=0 együtthatók és az a î = hf; 'i i (i = 0; : : : ; n) Fourier-együtthatók ismertek, akkor ortonormált polinomok esetén az f (x)

n X

a î 'i (x)

(6.29)

i=0


99

közelítés egy x pontbeli helyettesítési értékét célszer½uen a háromtagú rekurzióval számítjuk ki. Az eddigiekhez hasonló állítások vezethet½ok le a diszkrét esetben is, ha de…niáljuk a hf; gi = skalárszorzatot, ahol xi 2 Xm = fxi gm i=1

m X

(6.30)

f (xi ) g (xi ) w (xi )

i=1

[a; b] adott véges ponthalmaz.

6.1. Közelítések Csebisev polinomokkal A Csebisev polinomok, ill. a Csebisev polinomok szerinti Fourier sorfejtések különösen fontos szerepet játszanak különféle numerikus problémák megoldásában és nemcsak az L2 -approximációs feladatnál. Ezekre az alkalmazásokra egész elméleteket, technikákat és programrendszereket dolgoztak ki (lásd pl. Snyder [53], Fox, Parlett [18], Mason, Handscomb [35], Gil, Segura, Temme [22], Trefethen [57]). Ennek a "népszer½uségnek" az egyik fontos oka az hogy a Csebisev polinomok jól viselkednek a [ 1; 1] intervallumon. Pontosabban igaz a következ½o. Tétel: A Tbn (x) = 21 n Tn (x) (normalizált) Csebisev polinom az f 0 függvény legjobb egyenletes approximációja a [ 1; 1] intervallumon az 1 f½oegyütthatójú n-ed fokú polinomok között és Tbn = 21 n .. C Bizonyítás: Tegyük fel, hogy w (x) 6= Tbn (x) egy 1 f½oegyütthatójú n-ed fokú polinom, amelyre jw (x)j < 21 n (x 2 [ 1; 1]). Jelölje az n-edfokú Csebisev polinom széls½oértékhelyeit 1 = x0 < x1 < < xn = 1. y

1.0 0.8 0.6 0.4 0.2

-1.0

-0.8

-0.6

-0.4

-0.2

0.2

0.4

0.6

-0.2

0.8

1.0

x

-0.4 -0.6 -0.8 -1.0

T5 (x) = cos (5 arccos x) és 2 4 T5 (x) Az extremális pontokban Tbn (xi ) = ( 1)i+1 21 n (i = 0; 1; : : : ; n), illetve jw (xi )j < 21 n . A Tbn (x) w (x) polinom legfeljebb (n 1)-ed fokú, azonban Tbn (xi ) w (xi ) el½ojele megegyezik Tbn (xi ) 100


el½ojelével. Minthogy n el½ojelváltás van, a legfeljebb (n 1)-ed fokú Tbn (x) w (x) polinomnak n-gyöke van, ami ellentmondás. Megjegyezzük, hogy az [a; b] intervallum esetén a normalizált Csebisev polinom maximuma 1 2n 2 (b a)n . Egy f 2 C [ 1; 1] függvény Csebisev polinomok szerinti formális kifejtését a X 1 cj Tj (x) f (x) = c0 + 2 j=1 1

képlet adja, ahol cj = Példa: Legyen f (x) =

p

1

2

Z

1

f (x) Tj (x)

1

(1

2

=

dx

(j = 0; 1; : : :) :

(6.32)

x2 . Ekkor c0 =

cj =

x2 )1=2

(6.31)

Z

Z

1

p

1 1

2

Z

1 1

p 1 p 1

x2 4 dx = ; x2

1 x2 Tj (x) p dx = 1 x2

cos (j arccos x) dx =

Z

1

Tj (x) dx

Z

1

cos (j ) sin d

0

1

Z 1 = [sin ((j + 1) ) sin (j 1) ] d 2 0 1 cos ((j 1) ) cos ((j + 1) ) = 2 j 1 j+1 " # 0 j 1 j+1 1 ( 1) 1 ( 1) 1 = 2 j 1 j+1 ( 1)j + 1 = j2 1 p Ha j páratlan, akkor cj = 0. Eszerint 1 p

1

x2

(j

1) :

x2 formális Csebisev sora 4

1 4 X T2j (x) : 2 4j 1 j=1

Példa: Az ex közelítése a Csebisev sor els½o 5 tagjával

q (x) = 1:266066 + 1:130318T1 (x) + 0:271495T2 (x) + 0:044337T3 (x) + 0:005474T4 (x) : A Csebisev sor segítségével a Padé approximációhoz hasonló racionális közelítéseket lehet képezni. Legyen Pm j=0 aj Tj (x) Tmk (x) = Pk ; (6.33) j=0 bj Tj (x) KÖZELíTÉSEK CSEBISEV POLINOMOKKAL

101

ahol az aj és bj együtthatókat úgy határozzuk meg, hogy az

f (x)

Tmk (x) =

1 c 2 0

+

P1

j=1 cj Tj

(x)

Pk

Pk

j=0 bj Tj

j=0 bj Tj

Pm

(x)

j=0

(x)

aj Tj (x) (6.34)

különbség jobboldalán a számlálóból a Tj (x) a j = 0; 1; : : : ; N index½u tagok elt½unjenek, azaz teljesüljön ! k ! 1 m 1 X X X X 1 c0 + cj Tj (x) bj Tj (x) aj Tj (x) = hj Tj (x) : (6.35) 2 j=1 j=0 j=0 j=N +1 A feltétel baloldala a Ti+j (x) + Tji

jj

(x) = 2Ti (x) Tj (x)

azonosság alkalmazásával az 1 XX 1 X bi cj Ti+j (x) + Tji c0 bj Tj (x) + 2 j=0 2 j=1 i=0 m

1

k

jj

(x)

m X

aj Tj (x) =

j=0

1 X

hj Tj (x)

j=N +1

alakra hozható. Ebb½ol pedig az 1X a0 = bi c i ; 2 i=0 k

1X bi cjr 2 i=0

(6.36)

k

ar =

ij

+ cr+i

(r = 1; : : : ; N )

(6.37)

egyenletrendszert kapjuk, ahol de…níció szerint ar = 0, ha r > m. Példa: Az ex függvény (2; 2) index½u racionális Csebisev közelítése (számlálóban, nevez½oben xhatványok szerint kifejtve): T22 (x) =

1:0000205 + 0:5019781x + 0:0826200x2 1:0 0:4976173x + 0:0806064x2

6.2. Approximáció Hilbert-terekben A fejezet bevezetésében foglaltakat nézzük meg egy kissé általánosabb környezetben. De…níció: Legyen X egy lineáris vektortér. Az X teret pre-Hilbert, vagy bels½o szorzat térnek nevezzük, ha minden x; y 2 X elempárjához hozzá van rendelve egy hx; yi valós vagy komplex szám úgy, hogy 102


(i) hx; yi = hy; xi, (ii) hx + y; zi = hx; zi + hy; zi, (iii) h x; yi = hx; yi, (iv) hx; xi 0, és hx; xi = 0 , x = 0.

p Állítás: Az kxk = hx; xi el½oírás normát de…niál az X vektortéren. Az állítás igazolásához szükségünk van a következ½o eredményre. Lemma (Cauchy-Schwarz egyenl½otlenség): Ha X bels½o szorzat tér, akkor a fenti norma jelöléssel igaz, hogy jhx; yij kxk kyk (x; y 2 X) : Bizonyítás: Ha y = 0, akkor hx; 0i = hx; 0i miatt hx; 0i = 0 és az állítás igaz.Tegyük fel, hogy y 6= 0 és tetsz½oleges skalár. Ekkor fennáll, hogy 0

hx

y; x

yi = hx; xi

= hx; xi + j j2 hy; yi

h y; xi

= hx; xi + j j2 hy; yi Válasszuk a

h y; xi

h y; xi

hx; yi + h

y;

yi

2 Re ( hy; xi) :

= hx; yi = hy; yi értéket! Ekkor azt kapjuk, hogy 0

jhx; yij2 hx; xi + hy; yi = hx; xi

jhx; yij2 ; hy; yi

2 Re

hx; yi hy; xi hy; yi

ahonnan a Lemma állítása már következik. Az egyenl½otlenséget szokás Cauchy-Bunyakovszkij-Schwarz egyenl½otlenségnek is nevezni. Az Állítás bizonyítása: (a) kxk

(c)

0, kxk = 0 , x = 0; (b) q q p p k xk = h x; xi = hx; xi = h x; xi =

hx; xi =

q

j j2 hx; xi;

kx + yk2 = hx + y; x + yi = hx; xi + hx; yi + hy; xi + hy; yi kxk2 + 2 kxk kyk + kyk2 = (kxk + kyk)2 :

De…níció: Normával ellátott lineáris vektorteret normált térnek nevezzük. Példák: Rn , C [a; b], bels½o szorzat terek a skalárszorzat által indukált normával. Állítás: Ha X bels½o szorzat tér, akkor kx + yk2 + kx

yk2 = 2 kxk2 + 2 kyk2

APPROXIMÁCIÓ HILBERT-TEREKBEN

(x; y 2 X) :

(6.38) 103

Bizonyítás: De…níció alapján hx + y; x + yi + hx

yi = hx; xi + hx; yi + hy; xi + hy; yi + hx; xi

y; x

hx; yi

hy; xi + hy; yi :

A most igazolt reláció nem minden normált térben teljesül. Legyen X = C [0; 1], x (t) = 1, y (t) = t2 . Ekkor kxkC = 1, kykC = 1, kx + yk2C = 4 és kx yk2C = 1. Tehát 5 = kx + yk2C + kx

yk2C 6= 2 kxk2C + 2 kyk2C = 4;

amib½ol következik, hogy C [0; 1] nem bels½o szorzat tér. A skalárszorzat segítségével jellemzést adhatunk vektorok lineáris függetlenségére. Tétel: Legyen X bels½o szorzat tér, xi 2 X ( i = 1; : : : ; n). Az x1 ; x2 ; : : : ; xn vektorok akkor és csak akkor lineárisan függetlenek, ha a bel½olük képezett G = G (x1 ; : : : ; xn ) = [hxj ; xi i]ni;j=1

(6.39)

Gram-mátrix determinánsa nem zérus. Bizonyítás: Az állitással ekvivalens megfogalmazás: Az x1 ; : : : ; xn vektorok pontosan akkor linárisan összefügg½ok, ha a Gram determináns zérus. Ez utóbbit igazoljuk. Ha x1 ; : : : ; xn lineárisan összefügg½o, akkor léteznek olyan nem csupa zérus 1 ; : : : ; n számok, hogy n X

i xi

= 0:

i=1

Ezt a 0 vektort skalárisan megszorozva egymásután az x1 ; : : : ; xn vektorokkal kapjuk a következ½o homogén lineáris egyenletrendszert: hx1 ; x1 i + 1 hx1 ; x2 i +

1

1

hx1 ; xn i +

hx2 ; x1 i + 2 hx2 ; x2 i +

hxn ; x1 i = 0; n hxn ; x2 i = 0; .. . + n hxn ; xn i = 0: + +

2

2

hx2 ; xn i +

n

A feltevés szerint 1 ; : : : ; n nem triviális megoldás, ami csak akkor lehet, ha az egyenletrendszer mátrixának determinánsa 0. Fordítva, ha a rendszer mátrixának (a Gram mátrixnak) a determinánsa 0, akkor van nem triviális megoldás 1 ; : : : ; n . Igazoljuk, hogy ekkor ni=1 i xi = 0. Képezzük a következ½o mennyiséget: * n + n n n X X X X x ; x = i i j j i j hxi ; xj i i=1

j=1

=

j=1 i=1 n n X X j

j=1

104

|i=1

i

hxi ; xj i = 0;

{z

=0

}


P ahonnan ni=1 i xi = 0 következik. De…níció: Legyen X bels½o szorzat tér az h ; i skalárszorzattal. Az x; y 2 X vektorok ortogonálisak, ha hx; yi = 0. Állítás: Legyen X bels½o szorzat tér és az fxi gni=1 X ( xi 6= 0) vektorok páronként orton gonálisak. Ekkor az fxi gi=1 vektorok lineárisan függetlenek. Bizonyítás: A G (x1 ; x2 ; : : : ; xn ) Gram mátrix diagonális, amelynek átlójában a nemzérus hxi ; xi i értékek állnak. Tehát det (G) 6= 0 és így a vektorok lineárisan függetlenek. Lineárisan független vektorokból a már ismertetett Gram-Schmidt eljárással lehet ortogonális rendszert el½oállítani. Tétel (Gram-Schmidt eljárás): Legyen X bels½o szorzat tér, fzi gni=1 X tetsz½oleges lineárisan független vektorok ( n 2). Legyen (6.40)

x1 = z1 ; xj+1 = zj

j 1 X hzj ; xk i xk ; hx k ; xk i k=1

j = 2; : : : ; n

1:

(6.41)

A fxj gnj=1 vektorok ortogonálisak és L (z1 ; : : : ; zn ) = L (x1 ; : : : ; xn ). De…níció: Legyen X bels½o szorzat X véges vagy végtelen ortonormált rendszer. P tér, fxi g hy; x i x sort az y (formális) Fourier-sorának nevezzük Legyen y 2 X tetsz½oleges. A 1 i i i=1 (Ha a sorozat véges, akkor véges összeget használunk). Az hy; xi i konstansokat az y Fourier együtthatóinak nevezzük. Ismételten megjegyezzük, hogy szokás az y

1 X i=1

hy; xi i xi

(6.42)

jelölést is használni. Ha az x1 ; x2 ; : : : (xi 6= 0) sorozat ortogonális, de nem ortonormált, akkor az xi = (i = 1; 2; : : :) sorozat már az és y 2 X Fourier-sora felírható az y

1 X

y;

i=1

xi kxi k

X hy; xi i xi = xi kxi k hx ; x i i i i=1 1

xi kxi k

(6.43)

alakban. Véges dimenziós terek esetén egy elem Fourier sora el½oállíja az elemet. Tétel: Legyen z1 ; :P : : ; zn 2 X független és jelölje x1 ; : : : ; xn a bel½olük el½oállított ortonormalizált rendszert. Ha y = ni=1 ai zi , akkor y=

n X i=1


hy; xi i xi :

(6.44) 105

Pk Bizonyítás: A Gram-Schmidt eljárást …gyelembe véve írhatjuk, hogy zk = i=1 1; 2; : : : ; n). Ezért ! ! n n k n n n X X X X X X y= ak zk = ak = ai ik xk = ck xk : ki xi k=1

Mármost 1

k

i=1

k=1

k=1

i=k

ki xi

(k =

k=1

n esetén hy; xk i =

* n X

c k x k ; xk

k=1

+

= ck hxk ; xk i = ck ;

amib½ol az állítás következik. Pn j Példa: Ha qn (x) = j=0 knj x , knn 6= 1 olyan polinomok, amelyek ortonormáltak a h ; i skalárszorzat szerint, akkor tetsz½oleges p 2 Pn el½oállítható a p (x) =

n X k=0

hp; qk i qk (x)

(6.45)

formában. Tétel: Legyen X bels½o szorzat tér, fxi gni=1 X ortonormált rendszert és y 2 X tetsz½oleges. Ekkor n n X X y hy; xi i xi y (6.46) i xi i=1

i=1

tetsz½oleges a1 ; a2 ; : : : ; an konstansok esetén. Bizonyítás: * 2 n n X X y ai x i = y ai x i ; y i=1

i=1

= hy; yi = hy; yi +

n X i=1

n X

i=1 n X i=1

= hy; yi

i=1

Pn 2 Ez azt jelenti, hogy ky i=1 ai xi k (i = 1; 2; : : : ; n) feltételre érhet½o el. 106

ai x i

i=1

ai hxi ; yi

i=1

jhy; xi ij + kyk2

i=1 n X i=1

n X 2

+

n X

ai hxi ; yi

hxi ; yi hy; xi i n X

n X

ai hy; xi i + ai hy; xi i +

n X n X i=1 j=1 n X i=1

ij

z }| { ai aj hxi ; xj i

jai j2

hxi ; yi hy; xi i n X i=1

Pn

i=1

jai

hy; xi ij2 :

jhy; xi ij2 és a minimum az ai = hy; xi i


Itt most valójában y legjobb legkisebb négyzetes lineáris approximációját is el½oállítottuk Pn 2 1=2 általános bels½o szorzat terekben. Az approximáció hibáját a kyk2 kifejezés i=1 jhy; xi ij adja meg. Következmény (Bessel egyenl½otlenség): Ha fxi gni=1 X ortonormált rendszer az X bels½o szorzat térben, akkor n X jhy; xi ij2 kyk2 : (6.47) i=1

Pn Pn 2 2 2 Bizonyítás: Az állítás a 0 minai ky i=1 ai xi k = kyk i=1 jhy; xi ij összefüggésb½ol következik. Következmény: Ha fxi g1 X végtelen ortonormált rendszer az X bels½o szorzat térben, i=1 akkor 1 X jhy; xi ij2 kyk2 : (6.48) i=1

Az utóbbi következményb½ol az is következik, hogy limi!1 hy; xi i = 0. De…níció: Az X normált tér véges vagy végtelen fxi g elem halmazát zártnak nevezzük, ha minden x 2 X elemet tetsz½oleges pontossággal megközelíthetünk az fxi g vektorok véges lineáris kombinációjával. Másképpen fogalmazva, az fxi g elemhalmaz zárt, ha minden x 2 X és " > 0 esetén léteznek olyan a1 ; : : : ; an konstansok, hogy x

n X

ai x i

":

(6.49)

i=1

Példa: Az Rn vagy Cn térben bármely n darab lineárisan független vektor zárt. Példa: C [a; b], kf kC = maxa x b jf (x)j. A Weierstrass-tétel miatt az f1; x; x2 ; : : :g elemhalmaz zárt C [a; b]-ben. 1=2 Rb Példa: C [a; b], kf k = a jf (x)j2 dx . A Weierstrass-tétel miatt az f1; x; x2 ; : : :g elemhalmaz zárt C [a; b]-ben. Rb Példa: L [a; b], kf k = a jf (x)j dx. Az f1; x; x2 ; : : :g elemhalmaz zárt L [a; b]-ben. De…níció: Legyen X normált tér az kk normával. Az fxi g1 X sorozat (normában) i=1 konvergál az x 2 X elemhez, ha lim kx xi k = 0: (6.50) i!1

Ha a norma de…níciójában integrál szerepel, akkor középértékben való konvergenciáról beszélünk. Ez különbözik a függvényterek más típusú konvergenciáitól (pontonkénti, egyenletes, stb.). 1=2 R1 1=2 . Példa: Legyen X = C [ 1; 1], kf k = (f (x))2 dx . Legyen továbbá fn (x) = 1+nn2 x2 1 Ekkor Z 1 n 2 2 k0 fn k = dx = arctan n2 ! 0; 2 x2 1 + n n 1 de fn (0) ! 1.


107

De…níció: Legyen X normált tér és S X. Az S halmaz S lezárását az S halmaz konvergens sorozatainak limeszpontjai alkotják. Nyilvánvalóan S S. Ha S = S akkor az S halmazt zártnak nevezzük. Az S halmaz s½ur½u X-ben; ha S = X. Az X teret szeparábilisnak nevezzük, ha van benne egy megszámlálható számosságú s½ur½u halmaz. De…níció: Legyen X normált tér. Az fxi g1 X sorozat Cauchy-sorozat, minden " > 0 i=1 számhoz létezik egy N (") > 0 egész szám, hogy kxn

xm k

N (") .

", m; n

(6.51)

Az X teret teljesnek nevezzük, ha minden Cauchy-sorozatának van határértéke az X halmazban, azaz létezik x 2 X, hogy lim kxn xk = 0: (6.52) n!1

A teljes normált teret Banach-térnek nevezzük. Ha a norma skalárszorzatból származik, akkor a teret Hilbert-térnek nevezzük. Példa: Rn , Cn . Példa: X = C [a; b], kf kC = maxa x b jf (x)j. Ez a tér teljes. Ha maxa x b jfn (x) fm (x)j " (m; n N (")), akkor az ffm (x)g egyenletesen konvergens az [a; b] halmazon és van olyan f 2 C [a; b] függvény, amelyre jf (x)

fn (x)j

";

a

Ebb½ol következik, hogy fn ! f normában. R1 Példa: X = C [ 1; 1] az kf k = jf (x)j2 dx 1 8 <

1; nx; fn (x) = : 1;

és

f (x) = Mármost kf Tehát limn!1 kf mert Ha most kg

2

fn k =

Z

1;

1;

0

( 1

N 0 (") :

b; n

1=2

1 n

normával nem teljes. Legyen 1

x 1 x n x 1

1 0<x

2

nx) dx +

x 1

Z

1 n

1 n

0

1=n

(1

nx)2 dx =

0

1=n

2 : 3n

fn k = 0. De nem konvergálhat normában egy folytonos g függvényhez, kf

gk = kf

fn + fn

gk

kf

fn k + kg

fn k :

fn k ! 0 is teljesülne, akkor kf gk = 0 szükségképpen fennállna. Ámde az Z 0 Z 1 2 2 kf gk = (1 + g (x)) dx + (g (x) 1)2 dx = 0 1

feltételb½ol következik, hogy g (x) = ellentmondás. 108

x

0

1, ha

1 < x < 0 és g (x) = 1, ha 0 < x < 1, ami


A következ½o tétel az ortonormált (Fourier) sorfejtések alaptételének tekinthet½o. Tétel: Legyen fxi g1 i=1 ortonormált rendszer az X bels½o szorzat térben. Tekintsük a következ½o állításokat: (a) Az fxi g1 i=1 rendszer zárt X-ben. (b) Minden y 2 X elem Fourier sora normában konvergál y-hoz, azaz lim y

n!1

n X k=1

hy; xk i xk = 0:

(6.53)

(c) Minden y 2 X esetén fennáll az 2

kyk = hy; yi =

1 X k=1

jhy; yk ij2 :

(6.54)

a Parseval egyenl½oség. (c’) Minden x; y 2 X esetén fennáll a kiterjesztett hx; yi =

1 X n=1

hx; xn i hxn ; yi

(6.55)

kiterjesztett Parseval egyenl½oség. (d) Nincs az fxi g1 i=1 rendszert tartalmazó szigorúan b½ovebb ortonormált rendszer X-ben. 1 (e) Az fxi gi=1 rendszer teljes abban az értelemben, hogy y 2 X és hy; xi i = 0 (i = 1; 2; : : :) esetén y = 0. (f) Az X elemeit egyértelm½uen meghatározzák a Fourier-együtthattóik, azaz hw; xi i = hy; xi i (i = 1; 2; : : :) esetén w = y. A hét állítás között fennáll a következ½o kapcsolat rendszer: (a) , (b) , (c) , (c’) ) (d) , (e) , (f).

(6.56)

Ha X teljes bels½o szorzat (azaz Hilbert) tér, akkor (d))(c) és mind a hét állítás ekvivalens: (a) , (b) , (c) , (c’) , (d) , (e) , (f).

(6.57)

Bizonyítás: Tegyük fel (a)-t. Fennáll y

n X k=1

hy; xk i xk

y

n X

ak x k ;

(6.58)

k=1

amelynek jobboldala (a) miatt tetsz½oleges " > 0 értéknél kisebbé tehet½o. Ha (b) áll fenn, akkor az y elemet közelíthetjük a Fourier sorfejtés szegmenseivel, tehát fxi gni=1 zárt. Vagyis (a),(b). Az xi -k ortogonalitása miatt * + n n n X X X x hx; xk i xk ; y hy; xk i xk = hx; yi hx; xk i hy; xk i : k=1

k=1


k=1

109

A Cauchy-Schwarz egyenl½otlenség alapján hx; yi

n X k=1

hx; xk i hy; xk i

x

n X k=1

hx; xk i xk

y

n X k=1

hy; xk i xk :

Ha (b) fennáll, akkor a két jobboldali tag tart zérushoz, amib½ol (c’) következik. Az x = y választással (c’)-b½ol (c) következik. A 0

min y ai

n X

2

ai x i

i=1

2

= kyk

n X i=1

jhy; xi ij2

összefüggés alapján (c)-b½ol következik (b) és így (a),(b),(c),(c’). Tegyük fel (a)-t és azt hogy fxi g1 i=1 [ fwg (w 6= xi ) rendszer szintén ortonormált. Ez szintén zárt az X-ben. Az (a),(c) implikáció miatt egyidej½uleg fennállnak a 2

kwk = kwk2 =

1 X

k=1 1 X k=1

jhw; xk ij2 + jhw; wij2 ; jhw; xk ij2

relációk, amib½ol hw; wi = 0 következik. Ez azonban ellentmond a kwk = 1 feltételnek. Tehát (a))(d). Tegyük fel, hogy van olyan y 2 X (y 6= 0) elem, hogy hy; xi i = 0 (i = 1; 2; : : :). Ekkor 1 fxi g1 i=1 [ fy= kykg egy szigorúan b½ovebb ortonormált rendszer lenne. Ha volna egy fxi gi=1 [ fwg (w 6= xi ) szigorúan b½ovebb ortonormált rendszer, akkor nem teljesülne az (e) teljességi feltétel sem, mert hw; xi i = 0 (i = 1; 2; : : :) és w 6= 0 lenne. Tehát (d),(e). Tegyük fel, hogy hw; xi i = hy; xi i (i = 1; 2; : : :). Ekkor hw y; xi i = 0 (i = 1; 2; : : :). Ha feltesszük az (e) feltételt, akkor w y = 0 következik. Vagyis (e))(f). Ha (e) hamis volna, akkor volna olyan z 6= 0, hogy hz; xi i = 0 (i = 1; 2; : : :). Ekkor bármilyen y 2 X esetén fennállna hy; xi i = hy + z; xi i (i = 1; 2; : : :). Vagyis y és y + z két különböz½o elem lenne ugyanazzal a Fourier-együtthatókkal és (f) is hamis lenne. Ha (f) hamis, akkor volna két w 6= y elem, amelyre hw; xi i = hy; xi i minden i-e. Ebb½ol hw y; xi i = 0 (i = 1; 2; : : :) és w y 6= 0 következne és (e) is hamis lenne. Tehát (f))(e). Ezzel az els½o állítás láncot igazoltuk. Tegyük most fel, hogy X teljes (azaz Hilbert-tér). Pn Igazoljuk, hogy (f))(b), amib½ol a második állítás lánc már következik. Legyen w 2 X, s = sm = n k=1 hw; xk i xk . Az n > m esetben sn Pn k=m+1 hw; xk i xk és n X ksn sm k2 = jhw; xk ij2 k=m+1

P1

2

A Bessel-egyenl½otlenség P miatt k=1 jhw; xk ij < 1. Eért minden " > 0 számhoz létezik N (") egész szám, hogy nk=m+1 jhw; xk ij2 ", minden m; n N (") esetén. Tehát az fsn g sorozat Cauchy-sorozat és X teljessége miatt van s 2 X határértéke, azaz lim ks

n!1

110

sn k = 0:

(6.59)


Legyen t rögzített és n

t. Ekkor hs

sn ; xt i = hs; xt i

hsn ; xt i = hs; xt i

hw; xt i :

A Cauchy-Schwarz egyenl½otleség alapján jhs; xt i

hw; xt ij = jhs

sn ; xt ij

ks

sn k kxt k = ks

sn k :

A (6.59) határérték reláció alapján kapjuk, hogy hs; xt i = hw; xt i

(t = 1; 2; : : :) :

Az (f) feltevése esetén ebb½ol s = w következik és (6.59) miatt lim w

n!1

n X k=1

hw; xk i xk = 0:

Ez pedig pontosan a (b) feltétel. Véges fxi g rendszer esetén az állítások értelemszer½u módosításokkal értend½ok. Az (e) feltételben megfogalmazott teljességi tulajdonságot tetsz½oleges halmazokra is ki lehet terjeszteni. De…níció: Az S X halmaz az X bels½o szorzat térben teljes, ha hy; xi = 0

(8x 2 X)

(6.60)

esetén y = 0. Rb Példa: Legyen X = C [a; b] és hf; gi = a f (x) g (x) dx. Adott f 2 C [a; b] és " > 0 esetén léteznek olyan ai konstansok, hogy jf (x)

(a0 + a1 x +

+ an xn )j

"

(x 2 [a; b]) :

Innen kapjuk, hogy Z

b

(f (x)

(a0 + a1 x +

+ an xn ))2 dx

"2 (b

a) ;

a

amib½ol következik, hogy az 1; x; x2 ; : : : hatványok zárt halmazt alkotnak X-ben. Az (a)-(f) állítások fennállnak ha xi -k gyanánt Legendre polinomokat használunk. Speciálisan kaphatjuk, hogy ha f 2 C [a; b] és Z b f (x) xn dx = 0 (n = 0; 1; 2; : : :) ; a

akkor f (x) 0. Rb Példa: Legyen X = L2 [a; b] és hf; gi = a f (x) g (x) dx. Az 1; x; x2 ; : : : hatványok teljesek X-ben. APPROXIMÁCIÓ HILBERT-TEREKBEN

111

P1 1 Tétel: Legyen X Hilbert tér és fak g1 k=1 legyen olyan, hogy k=1 jak j < 1. Legyen fxk gk=1 egy teljes ortonormált rendszer X-ben. Ekkor van olyan y 2 X, hogy hy; xk i = ak

(k = 1; 2; : : :) : (6.61) P P P Bizonyítás: Legyen sn = nk=1 ak xk . Ekkor ksn sm k2 = nk=m+1 jak j2 . Minthogy 1 k=1 jak j < 1, fsn g egy Cauchy-sorozat és van egy y 2 X határértéke úgy, hogy limn!1 ky sn k = 0. Rögzített k és n k esetén ky

sn k = ky

sn k kxk k

jhy

sn ; xk ij = jhy; xk i

hsn ; xk ij = jhy; xk i

ak j :

Az n ! 1 határátmenetb½ol kapjuk, hogy hy; xk i = ak . Számos fontos Hilbert-tér van. Ezek közül kett½ot említünk meg. P 2 1 Tétel: Jelölje `2 az 1 ja j i < 1 feltételnek eleget tev½o fai gi=1 sorozatok halmazát, az i=1 ha; bi =

1 X

1 (a = fai g1 i=1 ; b = fbi gi=1 )

ai b i

i=1

(6.62)

pedig a rajta értelmezett skalárszorzatot. Az `2 tér Hilbert tér. Tétel: Jelölje L2 [a; b] az [a; b] intervallumon értelmezett olyan f függvény halmazát, amely mérhet½o és amelyre jf (x)j2 integrálható. Legyen hf; gi = a skalárszorzat és kf k =

Z

b

f (x) g (x)dx

(6.63)

a

Z

a

b

1=2

jf (x)j2 dx

(6.64)

a skalárszorzatból származó norma. Ekkor L2 [a; b] Hilbert-tér. 2 ; ]-ben. Tétel: Az f1; cos nx; sin nxg1 n=1 függvényrendszer teljes L [

6.3. Klasszikus Fourier-sorok

Jean Baptiste Joseph Fourier (1768-1830) 112


A

1 1 1 1 1 p ; p cos x; p sin x; p cos 2x; p sin 2x; : : : (6.65) 2 trigonometrikus függvényrendszer ortonormált és teljes az L2 [ ; ] függvénytérben. Ezért tetsz½oleges f 2 L2 [ ; ] függvény esetén az f Fourier-sora az L2 -normában konvergál és írhatjuk (L2 -ben), hogy a0 X f (x) = + (ak cos kx + bk sin kx) ; 2 k=1 1

ahol

Z

1

ak = és bk =

1

Példa: Legyen

(6.66)

f (x) cos (kx) dx

(k = 0; 1; 2; : : :)

(6.67)

f (x) sin (kx) dx

(k = 1; 2; : : :) :

(6.68)

Z

f (x) =

1; 1;

ha ha 0 < x

x<0

A függvénynek szakadása van az x = 0 pontban. Minthogy f (x) páratlan, a Fourier-sora 1 X

bn sin nx

n=1

alakú (lásd kés½obb), ahol bn = = =

1 1 1

Z

f (x) sin (nx) dx

Z

0

( 1) sin (nx) dx +

Minthogy cos (n ) = ( 1)n , bn = f (x) =

+

n

1 (1 n 2 = (1 n

4

(1) sin (nx) dx

0

h cos nx i0

=

Z

h cos nx i n 0

cos ( n )

cos n + 1)

cos (n )) : 2 n

(1

( 1)n ) és

sin x +

1 1 sin 3x + sin 5x + 3 5

:

Az alábbi ábra az f (x) függvényt és a Fourier-sor els½o n-tagjának összegét mutatja az n = 1; 3; 7 értékekre: KLASSZIKUS FOURIER-SOROK

113

sgn(x) Fourier kozelitese 1.5

1

0.5 sgn(x) n=1 n=3 n=7 0

-0.5

-1

-1.5 -5

-4

-3

-2

-1

0

1

2

3

4

5

A továbbiakban legyen a Fourier-sor n-edik részösszege a0 X + (ak cos kx + bk sin kx) : 2 k=1 n

sn (f ) (x) =

(6.69)

Az eddig tanultak szerint sn (f ) ! f az L2 tér normájában, kf és

2

sn (f )k = kf k

2

a20 2

a20 X 2 ak + b2k + 2 k=1

n X

a2k + b2k

(6.70)

k=1

n

kf k2 :

Felmerül a kérdés, hogy sn (f ) tart-e az f függvényhez pontonként? A válasz nemleges, s½ot adott pontban sn (f ) még divergálhat is. Az ortogonális-, vagy Fourier-sorok elméletének egyik legfontosabb kérdése a Fourier sor pontonkénti konvergenciája. Ezzel itt nem foglalkozunk, mert más tárgy foglalkozik vele részletesen. Azonban igazoljuk a következ½o egyszer½u tételt. Tétel: Tegyük fel, hogy f 2 C 2 [ ; ] és f (i) ( ) = f (i) ( ) (i = 0; 1). Ekkor az f Fouriersora egyenletesen és abszolút módon konvergál f -hez. Bizonyítás: Becsüljük az együtthatók növekedését! Z Z sin kx 1 ak = f (x) cos (kx) dx = f (x) f 0 (x) sin (kx) dx k k Z 1 f 0 (x) sin (kx) dx: = k 114


Integráljunk ismét parciálisan: Z kak = f 0 (x) sin (kx) dx = Z 1 f 00 (x) cos (kx) dx: = k

cos kx f (x) k 0

1 + k

Z

f 00 (x) cos (kx) dx

Innen következik, hogy 1 k2

jak j

Z

1 k2

00

f (x) cos (kx) dx

Z

2 kf 00 kC kf kC dx = : k2 00

Hasonló becslést kaphatunk a bk együtthatókra is. Ezért a0 X + (ak cos kx + bk sin kx) 2 k=1

X a0 + (jak j + jbk j) 2 k=1

1

1

C

1 X 1 < 1: 2 k k=1

P Ezért a Fourier-sor egyenletesen és abszolut konvergens egy g (x) = a20 + 1 k=1 (ak cos kx + bk sin kx) függvényhez. Ámde g-nek ugyanazok a Fourier-együtthatói mint f -nek. Ezért f = g. A most igazolt tétel segítségével becslést adhatunk a trigonometrikus polinomokkal történ½o legjobb approximáció nagyságrendjére. Tétel: Tegyük fel, hogy f 00 2 C [ ; ] és f (i) ( ) = f (i) ( ) (i = 0; 1; 2). Ha En (f ) = min max ck ; dk

x

n X

f (x)

(ck cos kx + dk sin kx) ;

(6.71)

k=0

akkor

konstans : n Bizonyítás: Legyen sn (f ) az f Fourier-sorának n-edik részösszege. Ekkor En (f )

En (f )

max jf (x) x

sn (f )j = max x

1 X

k=n+1

(6.72)

Z 1 1 X 1 C 1
ami bizonyítandó volt. Megjegyezzük, hogy Jackson idevágó tétele ennél er½osebb. Bizonyítás nélkül idézzük a következ½o eredményt. Tétel: Tegyük fel, hogy f 2 C [ 1; 1] kétszer folytonosan di¤erenciálható. Ekkor f felírható egyenletes és abszolut konvergens Csebisev-sorként, azaz f (x) =

1 X

ak Tk (x) ,

(6.73)

k=0

ahol

P1

k=0

jak j < 1.

KLASSZIKUS FOURIER-SOROK

115

116


Irodalomjegyzék [1] Achieser, N.I.: Theory of Approximation, Frederick Ungar Publishing Co., New York, 1956 [2] Ahlberg, J.H., Nilson, E.N., Walsh, J.L.: The Theory of Splines and Their Applications, Academic Press, 1967 [3] Baker, G.A.: Essentials of Padé Approximants, Academic Press, 1975 [4] Bojanov, B.D., Hakopian, H.A., Sahakian, A.A.: Spline Functions and Multivariate Interpolations, Springer, 1993 [5] Bultheel. A., van Barel, M.: Linear Algebra, Rational Approximation and Orthogonal Polynomials, North-Holland, 1997 [6] Buhmann, M.D.: Radial Basis Functions, Theory and Implementations, Cambridge University Press, 2004 [7] Burkill, J.G.: Lectures on Approximation by Polynomials, Tata Institute of Fundamental Research, Bombay, 1959 [8] Bustamante, J.: Algebraic Approximation: A Guide to Past and Current Solutions, Birkhauser, 2012 [9] Carothers, N.L.: A Short Course on Approximation Theory, Department of Mathematics and Statistics, Bowling Green State University [10] Cheney, E.W.: Introduction to Approximation Theory, AMS Chelsea Publishing, AMS, 2000 [11] Chui, C.K.: Multivariate Splines, SIAM, 1988 [12] Davis, P.J.: Interpolation and Approximations, Dover Publications, Inc., 1975 [13] de Boor, C.: A Practical Guide to Splines, Revised Edition, Springer, 2001 [14] de Boor, C.: Spline Toolbox For Use with MATLAB, The MathWorks, 2003 [15] de Boor, C., Höllig, K., Riemenschneider, S.: Box Splines, Springer, 1993 [16] de Villiers, J.: Mathematics of Approximation, Atlantis Press, 2012 [17] Epperson, J.F.: On the Runge example, The American Mathematical Monthly, 94, 4, 1987, 329–341 IRODALOMJEGYZÉK

117

[18] Fox, L., Parker, I.B.: Chebyshev Polynomials in Numerical Analysis, Oxford University Press, 1968 [19] Gal, S.G.: Approximation by Complex Bernstein and Convolution Type Operators, World Scienti…c, 2009 [20] Gantmacher, F.R.: The Theory of Matrices I-II, AMS Chelsea Publishing, AMS, 2010, 2009 [21] Gantmacher, F.R.: Matrizentheorie, VEB Deutscher Verlag der Wissenschaften, Berlin, 1986 [22] Gil, A., Segura, J., Temme, N.M.: Numerical Methods for Special Functions, SIAM, 2007 [23] Handscomb, D.C.(ed.): Methods of Numerical Approximation, Pergamon Press, 1966 [24] Hildebrand, F.B.: Introduction to Numerical Analysis, 2nd edition, Dover, 1987 [25] Isaacson, E., Keller, H.B.: Analysis of Numerical Methods, Dover, 1994 [26] Kis O.: Számítási módszerek II., Tankönyvkiadó, Budapest, 1970 [27] Knott, G.D.: Interpolating Cubic Splines, Birkhauser, 2000 [28] Korneichuk, N.P.: Splines in Aproximation Theory, oroszul, Nauka, Moszkva, 1984 [29] Kounchev, O.: Multivariate Polysplines: Applications to Numerical and Wavelet Analysis, Academic Press, 2001 [30] Kowalski, M.A., Sikorski, K.A., Stenger, F.: Selected Topics in Approximation and Computation, Oxford University Press, 1995 [31] Kvasov, B.I.: Methods of Shape-Preserving Spline Approximation, World Scienti…c, 2000 [32] Lorentz, G.G.: Approximation of Functions, Holt, Rinehart and Winston, 1966 [33] Lorentz, G.G., Jetter, K., Riemenschneider, S.D.: Birkho¤ Interpolation, Encyclopedia of Mathematics and Its Applications, Vol. 19, Addison-Wesley, 1983 [34] Lorentz, G.G.: Bernstein Polynomials, Chelsea Publishing Company, New York, 1986 [35] Mason, J.C., Handscomb, D.C.: Chebyshev Polnomials, Chapman&Hall/CRC, 2003 [36] Mastroianni, G., Milovanovic, G.V.: Interpolation Processes: Basic Theory and Applications, Springer, 2008 [37] Meinardus, G.: Approximation of Functions: Theory and Numerical Methods, Springer, 1967 [38] Natanszon, I.P.: Konstruktív függvénytan, Akadémiai Kiadó, 1952 118

IRODALOMJEGYZÉK

[39] Natanson, I.P.: Constructive Function Theory, Vol. I, Uniform Approximations, Frederick Ungar Publishing Co., New York, 1964 [40] Natanson, I.P.: Constructive Function Theory, Vol. II, Approximation in Mean, Frederick Ungar Publishing Co., New York, 1965 [41] Natanson, I.P.: Constructive Function Theory, Vol. III, Interpolation and Approximation Quadratures, Frederick Ungar Publishing Co., New York, 1965 [42] Nürnberger, G.: Approximation by Spline Functions, Springer, 1989 [43] Phillips, G.M.: Interpolation and Approximation by Polynomials, Springer, 2003 [44] Prenter, P.M.: Splines and Variational Methods, Wiley, 1975 [45] Rice, J.R.: The Approximation of Functions, Vol. I., Linear Theory, Addison-Wesley, 1964 [46] Rice, J.R.: The Approximation of Functions, Vol. II., Nonlinear and Multivariate Theory, Addison-Wesley, 1969 [47] Rivlin, T.J.: An Introduction to the Approximation of Functions, Blaisdell Publishing Company, 1969 [48] Rivlin, T.J.: The Chebyshev Polynomials, Wiley, 1974 [49] Schultz, M.H.: Spline Analysis, Prentice-Hall, Inc., 1973 [50] Schumaker, L.L.: Spline Functions: Basic Theory, 3rd edition, Cambridge University Press, 2007 [51] Shikin, E.V., Plis, A.I.: Handbook on Splines for the User, CRC Press, 1995 [52] Stechkin, S.B., Subbotin, Yu.N.: Splines in Numerical Mathematics, Nauka, Moszkva, 1976 [53] Snyder, M.A.: Chebyshev Methods in Numerical Approximation, Prentice-Hall, Inc., 1966 [54] Ste¤ens, K.-G.: The History of Approximation Theory, Birkhauser, 2006 [55] Szabados J., Vértesi P.: Interpolation of Functions, World Scienti…c, 1990 [56] Sz½okefalvi-Nagy Béla: Valós függvények és függvénysorok, 3-ik kiadás, Tankönyvkiadó, 1965 [57] Trefethen, N.: Approximation Theory and Approximation Practice, University of Oxford, June, 2011 [58] Wahba, G.: Spline Models for Observational Data, SIAM, 1990 [59] Wang, R.-H.: Multivariate Spline Functions and Their Applications, Springer, 2001 IRODALOMJEGYZÉK

119

[60] Wang, Y.: Smoothing Splines: Methods and Applications, CRC Press, 2011 [61] Wendland, H.: Scattered Data Approximation, Cambridge University Press, 2005

120

IRODALOMJEGYZÉK

2017 I. félév

Recommend Documents