2. előadás
5
Alkalmazzuk az egyváltozós esetben a legkisebb négyzetek módszerét. Legyen a mérések száma n, y (n ≠ 0). f(x, a)
yi yn
y1
x1
xi
xn
n
x
F (a ) = ∑ ( f ( xi , a ) − yi )
2
→ Min!
1 n 2 ∑ ( f ( xi , a ) − y i ) n i =1
⇔
i =1
→ Min!
a=?
a=?
A két kritérium ekvivalens egymással, hiszen ha az F függvénynek az a paramétervektor helyen minimuma van, akkor a helyen a nemzérus konstansszorosának is minimuma van. A regresszióanalízisnél a második kifejezés használata a gyakoribb. Ezt a felírást lehet általánosítani, mégpedig úgy, hogy ha az 1/n-t bevisszük a ∑ mögé, akkor az alábbi megfogalmazással élhetünk: ha a mérésszám véges n, és a lehetséges mérési helyeket x1, x2,…, xi, …, xn sorozat jelöli ki, továbbá xi ≠ xj, ha i ≠ j, és minden egyes xi-nek ugyanakkora az előfordulási valószínűsége,
akkor
egy
klasszikus
valószínűségi
problémával
állunk
szemben.
(A
valószínűségszámítás körében a kocka-dobás esete egy ilyen dolog. Véges sok elemi esemény van, és minden elemi eseménynek ugyanakkora a bekövetkezési valószínűsége. ) Tehát minden xi esetén a bekövetkezési valószínűség:
pi = 1/n.
Teljesül természetesen: n
∑p i =1
i
1 1 1 = + + ... + = 1 n n n n db
n
1
∑ n ( f (x , a ) − y ) i =1
2
i
i
→ Min! ⇒
n
∑ p ( f (x , a ) − y ) i =1
2
i
i
i
→ Min!
a=? n
∑p i =1
i
=1
pi = p j
( pi ≥ 0 )
(1 ≤ i ≤ n;
1 ≤ j ≤ n)
2. előadás
6
Ha nem kötjük ki, hogy a pi-értékek azonosak, azonban teljesítik azt, hogy az összegük 1-gyel egyenlő, akkor az előbbieknél általánosabb formulát kapunk. Ez már egy valószínűségi megközelítése a regresszióanalízisnek. Mivel minden egyes xi pontnak, mint mérési helynek van egy pi ≥ 0 bekövetkezési valószínűsége, a kritériumban ezzel a valószínűséggel súlyozzuk az xi-hez tartozó eltérés négyzetét.
[
F (a ) = M ( f ( xi , a ) − yi )
2
]
→ Min!
a=? Keressük azt az a paramétervektort, amely mellett az analitikusan adott f(x, a) függvényt a fenti kritériumba helyettesítve a négyzetes várható érték minimális lesz. A probléma tehát egy F(a) = F(a1, a2, …,ak) függvény minimumhelyének megkeresése.
Szélsőérték-számítás (ismétlés) y
f(x)
δ
x*
x’
δ
x0
x1
x2
x3
x4
x
Nem kell, hogy differenciálható legyen a függvény ahhoz, hogy minimum helyet, illetve maximum helyet meghatározzunk. Def.: Az f(x) függvénynek az x0 helyen lokális minimuma van, ha ∃ (létezik) az x0-nak egy δ sugarú környezete úgy, hogy ha x ∈ [x0 – δ, x0 + δ] ⇒ f(x) ≥ f(x0). pl.: x*, x0, x2, x4 – lokális minimum helyek A lokális minimum helyek között az az abszolút minimum hely, amely helyen a függvény a legkisebb értéket veszi fel (feltéve, hogy van legkisebb függvényérték). Pl.: a fenti esetben az x* az abszolút minimum hely. x’, x1, x3 – lokális maximum helyek
( x ∈ [x0 – δ1, x0 + δ1] ⇒ f(x) ≤ f(x1) )
2. előadás
7
Ha az f(x) legalább kétszer differenciálható egyváltozós valós függvény, akkor szükséges és elégséges feltétel a lokális szélsőérték létezéséhez, hogy f’(x1) = 0 (a függvény x1 pontjához húzott érintő meredeksége 0); és f”(x1) > 0
⇒
x1 helyen lokális minimum van.
⇒
x2 helyen lokális maximum van.
f’(x2) = 0; és
vagy
f”(x2) < 0
Ha f(x) 2n-szer differenciálható valós egyváltozós függvény és f’(x0) = 0, f”(x0) = 0, …, f(2n-1)(x0) = 0, de f(2n)(x0) ≠ 0, akkor ha f(2n)(x0) > 0 ⇒
x0 helyen lokális minimum hely van,
ha f(2n)(x0) < 0 ⇒
x0 helyen lokális maximum hely van.
Elégséges feltétel n-változós valós függvény lokális szélsőértékeinek létezésére Adott az f(x1, x2, …,xn) n-változós valós függvény, és a p0(x10, x20, …,xn0) pont. Ahhoz, hogy f-nek biztosan legyen szélsőértéke a p0 pontban, az alábbiaknak kell teljesülnie: (1.) f’x1(p0) = 0, f’x2(p0) = 0, …, f’xn(p0) = 0 (2.) Tekintve az alábbi függvénydeterminánsokat
f x′1′x1 ( p0 ) f x′′2 x1 ( p0 ) f x′′3 x1 ( p0 ) M
f x′′n x1 ( p0 )
D1
f x′1′x 2 ( p0 ) f x′′2 x 2 ( p0 )
D2
D3
f x′′3 x 2 ( p0 )
f x′1′x3 ( p0 ) K f x′′2 x3 ( p0 ) K f x′′3 x3 ( p0 ) K
f x′1′x n ( p0 ) f x′′2 x n ( p0 )
f x′′n x 2 ( p0 )
f x′′n x3 ( p0 ) K
f x′′n x n ( p0 )
Dn
f x′′3 x n ( p0 )
ahol D1, D2, D3, …, Dn – sarokdeterminánsok Biztosan van lokális szélsőérték p0 pontban, ha a sarokdeterminánsok a p0 pontban vagy mind pozitívak:
D1
D2
D3 K Dn
⊕
⊕
⊕
K
⊕
⇒ a p0 helyen lokális minimum van.
Vagy negatív, pozitív, negatív, stb módon váltakozó értékűek: lokális maximum van. Ezek elégséges, de nem szükséges feltételek.
D1 D2 D3 K Dn
− ⊕ −
−
⇒ a p0 helyen
2. előadás
8
Szélsőérték-számítás néhány numerikus módszere
1. Gauss-Seidel algoritmus z
a
c
y0
d
y
x0 nívóvonalak
x1 x
b
y0
(x0, y0)
x0
x2 x1
x
y1
(x2, y1) (x1, y0)
(x1, y1)
y
2. előadás
9
A szemléltetés kétváltozós valós függvény esetében lehetséges. A módszer lényege, hogy adott egy felületünk, és ennek akarjuk megkeresni a minimum helyét. A felületbe belemetszünk az y-z síkkal párhuzamosan, majd megkeressük ennek a metszékgörbének a minimum helyét. Ez lesz pl. x0. Megkeressük azt a nívóvonalat, amelyet az x0 érint, és ebben a pontban szintén elmetsszük a felületet, de most az x-z síkkal párhuzamosan. Itt is megkeressük a felületi görbén a minimum helyet (y0), és meghatározzuk az ehhez tartozó nívóvonalat, majd ismét az y-z síkkal párhuzamosan metszünk… Miért jó ez a módszer? →
Mindig egyváltozós fv-t vizsgálunk, és nem kell feltétlenül deriválni!
n-változós esete: f(x1, x2, x3, …, xn) függvényt vizsgáljuk. n-1 változó le van rögzítve, és mindig egy változót változtatunk. f(x1, x20, x30, …, xn0)
→
x10 , ahol f(p0) minimális.
f(x10, x2, x30, …, xn0)
→
x21
f(x10, x21, x3, …, xn0)
→
x31
→
xn1
le vannak rögzítve
: f(x10, x21, x31, …, xn)
És ezután kezdődik a ciklus elölről. Akkor legyen vége, ha p0, p1, …, pk – pontok esetén pk-1 , pk < δ , tehát a pk-1 és a pk pontok távolsága kisebb egy megadott δ értéknél, vagy f(pk-1) – f(pk) < ε, tehát a pk-1 és a pk pontok függvényértékeinek különbsége kisebb egy megadott ε értéknél.
2. Véletlen optimumkereső módszer c a
y
d T1
A felületen felveszünk 5 db pontot a megadott
p1
T2
p5 p5’
p1’
p2 p3
p4
b p2’
kiszámoljuk T3
tartományban,
T1 a
hozzájuk
és
tartozó
függvényértékeket. f(p1), f(p2), f(p3), f(p4), f(p5)
p4’
Kiválasztjuk a legkisebb értéket közülük
p3’
(most
legyen
p4)
és
a
következő
intervallumot (T2) úgy vesszük fel, hogy x
ez a pont legyen a közepén.
2. előadás
10
Most ebben az új intervallumban generálunk ismét 5 db pontot. f(p1’), f(p2’), f(p3’), f(p4’), f(p5’)
→
itt f(p3’) a minimális
Akkor p3’ lesz az új téglalap (T3) középpontja, és ismét generálunk 5 pontot. Egy bizonyos eset után elkezdjük finomítani az intervallumokat, tehát felezzük, majd kezdjük „elölről”. Bizonyos lépésszám után mindig feleződni fog a téglatartomány, míg egyszer annyira beszűkül, hogy leáll az algoritmus. Ez egy véletlen kereső algoritmus, ez akkor jó, ha eléggé szabálytalan a felület, sok különböző helyen rendelkezik minimummal.
.
3. előadás
11
2. Véletlen optimumkereső módszer A felületen – bizonyos alapsíkbeli intervallum fölött – felveszünk néhány véletlen pontot. Ezek az alapsíkon szintén véletlen pontok lesznek. Majd a felületen, a pontok közül megkeressük a legkisebb értéket – ha minimumot keresünk (ha maximumot keresünk, akkor a legnagyobbat keressük meg). Majd az intervallumunkat eltoljuk úgy, hogy a legkisebb (vagy legnagyobb) értékhez tartozó pont legyen az új tartományunk középpontja. Itt újabb pontokat veszünk fel, majd az előzőekhez hasonlóan járunk el. Bizonyos lépésszámonként finomítjuk az intervallumunkat, így egyre jobban beszűkül az a tartomány, ahol az abszolút minimumot, illetve maximumot keressük. Példa
f ( x, y ) = x 2 +
1 x + ey
2
y0 = 1
f ( x, y 0 ) = x 2 +
1 x + e y0
2
y0 = 1
F (x ) = x 2 +
1 x+e
f ( x0 , y ) = x0 + 2
→ x0 1
x0 + e y
2
→ y1
.
3. előadás
12
3. Gradiens-módszer z
z = f(x, y)
P skalár-vektor függvény →
f(x, y) = f(r)
grad f(r)
r = xi + yj
f(r) = f(x, y)
r G’
P’
y
grad f
x
A grad f vektor az alapsíkra levetített szintgörbe P’ pontjához húzott érintőjére merőleges vektor. Az f(x, y) = f(r) skalár-vektor függvényből kiindulva a függvény tetszőleges felületi pontjához tartozó legnagyobb növekedés irányát adja meg a grad f vektor. A grad f vektor úgy határozható meg, hogy kell képezni az f függvénynek az x szerinti parciális deriváltját, valamint kell képezni az f függvénynek az y szerinti parciális deriváltját. grad f = f’x(x, y)i + f’y(x, y)j = [f’x, f’y]
kétváltozós eset
A grad f vektor az alapsíkban (x, y) elhelyezkedő nívógörbe r vektorhoz tartozó érintőjére merőleges vektor. Háromváltozós eset : [f’x, f’y, f’z] n-változós eset: f(x1, x2, …, xn) →
grad f = [f’1, f’2, …, f’n]
A –grad f a legnagyobb csökkenés irányát jelöli ki. A függvény gradiense csak akkor létezik, ha bármely változó szerint parciálisan differenciálható.
.
3. előadás
13
y r0
grad f(r0)
r1 r2
-h0 grad f(r0)
Minimum számítás!
r3 -h1 grad f(r1) -h2 grad f(r2)
g0 g1
g2
x
r 1 = r 0 − h0 grad f (r 0 ) r 2 = r 1 − h1 grad f (r 1 ) M r k +1 = r k − hk grad f (r k )
k = 0, 1, …, n
Kérdés: h0, h1, …, hk lépésközök meghatározása Ha minimumot keresünk, akkor h0, h1, …, hk negatív, ha maximumot keresünk, akkor h0, h1, …, hk pozitív. Miért igaz, hogy a gradiens vektor a legnagyobb változás irányába mutat?
① A kétváltozós függvény differenciálható az (x, y) pontban, ha létezik f’x(x, y) és f’y(x, y), továbbá f(x+h, y+k) – f(x, y) = h*f’x(x, y) + k*f’y(x, y) + h*ε1(h, k) + k*ε2(h, k) lim ε1(h, k) = ε2(h, k) = 0 h→0 k→0
.
3. előadás
14
② Iránymenti derivált z = f(x, y) a = a*i b = b*j e = a*i + b*j f(P)
e = cosα*i + sinα*j f(P0)
iránymenti derivált: y
P a
x
α
e
d
P0
f 'e =
lim
P → P0
f (P ) − f (P0 ) d (P, P0 )
e
b e = 1 Az ① és a ② pontot alkalmazva: az alapsíkon az e egyenes egyenlete: x = x0 + at
e
d=
y = y0 + bt
f ' e = lim
P → P0
(x − x0 )2 + ( y − y0 )2 =
=1
f (x, y ) − f (x0 , y 0 )
= lim
t a2 + b2
t→0
f ( x 0 + at , y 0 + bt ) − f ( x 0 , y 0 ) = t
alkalmazva az ①-et
= lim
a 2t 2 + b 2t 2 = t a 2 + b 2 = t
0
at * f ' x ( x 0 , y 0 ) + bt * f ' y ( x 0 , y 0 ) + at ε 1 + bt ε 2 t
t→0
0
= a * f ' x (x0 , y 0 ) + b * f ' y (x0 , y 0 )
Ez szavakban kifejezve azt jelenti, hogy az e egységvektor menti iránymenti derivált a P0 pontban úgy számolható ki, hogy kiszámoljuk a gradiens vektor koordinátáit (ezek a parciális deriváltak x és y szerint), és rendre megszorozzuk az egységvektor koordinátáival (a és b), azaz ez egy skaláris szorzat. Általános iránymenti derivált:
f 'e ( x0 , y 0 ) = e ∗ grad f ( x0 , y0 ) Két vektor skaláris szorzata: az abszolútértékük megszorozva a közbezárt szögükkel, tehát
f 'e = e ∗ grad f ( x0 , y0 ) ∗ cos β =1
Abszolútértéke maximális, ha β=0° vagy β=180° minimális, ha β=90°
.
3. előadás
15
Tehát az iránymenti derivált értéke akkor maximális, ha az egységvektor irány megegyezik a gradiens irányával.
Regresszióanalízis F(a) = M[(f(xi, a) – yi)2] a=?
→
Min!
a = [a1, a2, …, ak]
y yi
ei
yn
y1
en
f(x, a)
e1
x1
xi
∂F (a ) =0 ∂a j
xn
x
(j = 1, 2, …, k)
[
]
∂ ∂Fa ∂ 2 ( f ( x, a ) − y )2 = 0 = M ( f ( x, a ) − y ) = M ∂a j ∂a j ∂a j
∂f ( x, a ) M 2( f ( x, a ) − y ) ∗ =0 ∂a j
:2
∂f ( x, a ) ∂f ( x, a ) −y M f ( x, a ) ∗ =0 ∂a j ∂a j ∂f ( x, a ) ∂f ( x, a ) M f ( x, a ) ∗ − M y =0 ∂a j ∂a j ∂f ∂f Mf = M y ∂a j ∂a j
(j = 1, 2, …, k)
Tehát akkor minimális, ha a görbe pont ráilleszkedik a pontjainkra.
