Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
6. el˝oad´as Line´aris algebra numerikus m´ odszerei
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
LNM, f¨ uggv´ eny
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A Gauss-Jordan elimin´ aci´ o, m´ atrixinvert´ al´ as
Gauss-Jordan m´odszer Ugyanazzal a technik´aval, mint ahogy a k-adik oszlopban az akk alatti elemeket kinull´aztuk, a f¨ ol¨ otte l´ev˝ o elemeket is z´eruss´a lehet tenni. Azaz az elimin´aci´ os f´azisban k minden ´ert´ek´ere az i ciklusv´altoz´ot nemcsak k + 1-t˝ ol n-ig, hanem 1-t˝ ol n-ig futtathatjuk, kiv´eve az i = k esetet. (Ez annak felel meg, mintha az xk -nak az k-adik egyenletb˝ ol val´ o kifejez´ese ut´an azt az ¨osszes t¨obbibe behelyettes´ıten´enk.) Az I. f´ azis v´egeredm´enye ´ıgy egy diagon´alm´atrix´ u egyenletrendszer, vagyis a II. f´ azis ekkor csup´an az xi = bi /aii (i = 1, 2, . . . , n) utas´ıt´asokb´ ol ´all (amiket menet k¨ozben, egy-egy oszlop teljes kinull´az´asa ut´an – vagy m´eg el˝ otte – azonnal is megtehet¨ unk). Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A Gauss-Jordan elimin´ aci´ o, m´ atrixinvert´ al´ as
Persze, szekvenci´alisan v´egrehajtva ez a m´ odszer nem el˝ony¨os, hiszen jelent˝osen megn˝ o a m˝ uveletek sz´ama. Ha viszont csak azut´an kezd¨ unk a f˝ o´atl´ o f¨ ol¨ otti elemek null´az´as´aval foglalkozni, miut´an kialak´ıtottuk a fels˝ o h´aromsz¨ ogm´atrixot, ´es ezt a null´az´ast a k = n, n − 1, . . . , 2 sorrendben v´egezz¨ uk (teh´at az oszlopok szerint visszafel´e haladva), akkor az A m´atrix elemeihez m´ar nem kell hozz´any´ ulni. Ugyanis az i-edik sor −lik -szor a k-adik sor (i = 1, 2, . . . , k − 1) elv´egz´ese sor´an a k-adik sorban az akk elem kiv´etel´evel minden elem (elvileg) m´ar 0. A k-adik oszlopba sem kell a 0-´at be´ırni. A II. f´ azis u ´gy tekinti, hogy ott z´erus ´all. A f˝ o´atl´ o f¨ ol¨otti elemek null´az´asa teh´at nem m´as, mint a m´ar t´argyalt Gauss-m´odszer II. f´ azisa.
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A Gauss-Jordan elimin´ aci´ o, m´ atrixinvert´ al´ as
Az algoritmus t¨obb, de ugyanolyan egy¨ utthat´ o m´atrix´ u Ax = bj n (bj ∈ R , j = 1, 2, . . . , m) egyenletrendszert oldjon meg. F˝ o´ atl´ o alatti null´ az´ as (I. f´ azis):
1 2 3 4 5 6 7 8
Legyen B = [b1 , b2 , . . . , bm ] Legyen A = [A, B], azaz kib˝ ov´ıtj¨ uk az A-t a jobboldali b vektorokkal FOR k ← 1 TO n-1 DO // Hat´arozzuk meg a t indexet, hogy |atk | = maxk≤i≤n |aik |. IF k 6= t cser´elj¨ uk fel a k-adik ´es t-edik sort FOR i ← k + 1 TO n DO lik = aik /akk FOR j ← k + 1 TO n + m DO aij = aij − lik akj
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
A Gauss-Jordan elimin´ aci´ o, m´ atrixinvert´ al´ as
F˝ o´ atl´ o f¨ ol¨ otti null´ az´ as (II. f´ azis): 1 2 3 4 5 6 7 8 9
FOR k ← n DOWNTO 2 DO FOR i ← 1 TO k − 1 DO lik = Aik /Akk FOR j ← n + 1 TO n + m DO aij = aij − lik akj FOR j ← n + 1 TO n + m DO xk,j−n = akj /akk FOR j ← n + 1 TO n + m DO x1,j−n = a1j /a11
V´ egeredm´ eny: [x1 , x2 , . . . , xm ] = X
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
LNM, f¨ uggv´ eny
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A Gauss-Jordan elimin´ aci´ o, m´ atrixinvert´ al´ as
Megjegyz´es Fenti algoritmus alkalmas m´atrixinvert´al´asra. K¨ onnyen bel´athat´o ugyanis, hogy az Ax = ei egyenletrendszer megold´asa ´eppen az inverz m´atrix i-edik oszlopvektora. Ha az algoritmusban B az egys´egm´atrix, akkor a v´egeredm´eny: X = A−1 .
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, egyenes eset
Legyen N ∈ N ´es adottak az x1 , x2 , . . . , xN ∈ R alappontok ´es az y1 , y2 , . . . , yN ∈ R f¨ uggv´eny´ert´ekek (pl. m´er´esi eredm´enyek). Keress¨ uk azt az egyenest y = a0 + a1 x, melyre a N X
[yi − (a0 + a1 xi )]2
i=0
kifejez´es minim´alis. A fenti felt´etelnek eleget tev˝ o egyenest az (xi , yi ) i = i, . . . , N, ´ert´ekeket n´egyzetesen legjobban k¨ ozel´ıt˝ o egyenesnek nevezz¨ uk.
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
A legkisebb n´ egyzetek m´ odszere, egyenes eset
A feladat megold´as´ahoz az F (a0 , a1 ) =
N X
yi − (a0 + a1 xi )
2
: R2 → R
i=1
f¨ uggv´enyt kell minimaliz´alnunk. A t¨ obbv´altoz´ os f¨ uggv´enyek sz´els˝o´ert´ek´er˝ol tanultak szerint az Fa00 (a0 , a1 ) = 0 ´es Fa01 (a0 , a1 ) = 0 felt´etelnek eleget tev˝ o a0 , a1 -et keress¨ uk. A parci´alis deriv´altakra N X
2[yi − (a0 + a1 xi )] = 0
i=1 N X
2[yi − (a0 + a1 xi )]xi = 0
i=1 Line´ aris algebra numerikus m´ odszerei
egyenletrendszert kapjuk.
6. el˝ oad´ as
LNM, f¨ uggv´ eny
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
A legkisebb n´ egyzetek m´ odszere, egyenes eset
Ezt az egyenletrendszert az al´abbi alakban ´ırhatjuk: N X
yi − Na0 −
i=1 N X
N X
a1 xi = 0
i=1
xi yi −
i=1
N X
a0 xi −
i=1
N X
a1 xi2 = 0
i=1
amelyb˝ol ad´odik, hogy Na0 +
N X
! xi
a1 =
i=1 N X i=1 Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
! xi
a0 +
N X i=1
N X
yi
i=1
! xi2
a1 =
N X i=1
xi yi
LNM, f¨ uggv´ eny
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, egyenes eset
Vezess¨ uk be a 1 x1 1 x2 A= . . .. ..
k¨ovetkez˝ o jel¨ ol´eseket: ∈ RN×2 ,
b=
y1 y2 .. .
∈ RN ,
a=
a0 a1
yN
1 xN Ekkor N AT A = N X xi i=1
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
N X i=1 N X i=1
xi xi2
N X
yi i=1 AT b = N X xi yi i=1
∈ R2 .
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, egyenes eset
´Igy az egyenletrendszer AT Aa = AT b alakban ´ırhat´o. A det(AT A) = 0 csak akkor teljes¨ ulhet, ha x1 = x2 = . . . = xN (´erdektelen eset). Teh´at feltehetj¨ uk, hogy det(AT A) 6= 0. Ekkor az egyenletrendszer egy´ertelm˝ uen megoldhat´ o. P´eld´aul az AT A invert´alhat´o, ´ıgy a = (AT A)−1 AT b.
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, polinom eset
Legyen n, N ∈ N u ´gy, hogy n << N, adottak az x1 , x2 , . . . , xN ∈ R alappontok ´es az y1 , y2 , . . . , yN ∈ R f¨ uggv´eny´ert´ekek (pl. m´er´esi n X eredm´enyek). Keress¨ uk azt a Pn (x) = aj x j polinomot, melyre a j=0 N X
(yj − Pn (xi ))2
j=0
kifejez´es minim´alis. A fenti felt´etelnek eleget tev˝ o Pn polinomot az (xi , yi ) i = i, . . . , N, ´ert´ekeket n´egyzetesen legjobban k¨ ozel´ıt˝o n-ed fok´ u polinomnak nevezz¨ uk. Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, polinom eset
A feladat megold´as´ahoz az
F (a0 , a1 , . . . , an ) =
n X i=1
yi −
n X
2 aj xij : Rn+1 → R
j=0
f¨ uggv´enyt kell minimaliz´alnunk. A t¨ obbv´altoz´ os f¨ uggv´enyek sz´els˝o´ert´ek´er˝ol tanultak szerint az F 0 (a0 , a1 , . . . , an ) = 0 felt´etelnek eleget tev˝o aj -ket keress¨ uk. A parci´alis deriv´altakra N X ∂Pn ∂F (a0 , a1 , . . . , an ) = 2(yi − Pn (xi )) − (xi ) = 0 ∂aj ∂aj i=1
(j = 0, 1, . . . , n). Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, polinom eset
N X i=1
Mivel
N
X ∂Pn ∂Pn Pn (xi ) (xi ) = yi (xi ) ∂aj ∂aj
(j = 0, 1, . . . , n).
i=1
∂Pn (xi ) = (xi )j , a fenti egyenlet a k¨ ovetkez˝o alakba ´ırhat´o: ∂aj N X i=1
(xi )
j
n X k=0
k
ak (xi ) =
n X k=0
ak
N X i=1
(xi )
j+k
=
N X
yi (xi )j
i=1
(j = 0, 1, . . . , n). Ezzel ak -kra egy line´aris egyenletrendszert kaptunk (n + 1 darab egyenlet, n + 1 darab ismeretlennel).
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
A legkisebb n´ egyzetek m´ odszere, polinom eset
Vezess¨ uk be a k¨ovetkez˝ o jel¨ ol´eseket: 1 x1 . . . x1n 1 x2 . . . x n 2 A= . . . . . ... .. .. 1 xN b=
y1 y2 .. .
. . . xNn
∈ RN×(n+1) ,
∈ RN ,
a=
an
yN Ekkor az egyenletrendszer AT Aa = AT b alakban ´ırhat´o. Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
a0 a1 .. .
∈ Rn+1 .
LNM, f¨ uggv´ eny
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Az f f¨ uggv´eny helyettes´ıt´es´ere (k¨ ozel´ıt´es´ere) a sz´ oba j¨ohet˝o, el˝ore r¨ogz´ıtett H f¨ uggv´enyoszt´alyb´ ol azt a h ∈ H f¨ uggv´enyt keress¨ uk, amely az kf − hk → min, h∈H felt´eteles sz´els˝o´ert´ek feladat megold´asa. Tulajdonk´eppen minden h ∈ H tekinthet˝o k¨ozel´ıt´esnek, ez´ert a feladatot kiel´eg´ıt˝o f¨ uggv´enyt szok´as legjobb approxim´aci´ onak nevezni.
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
F¨ uggv´enyek [a, b] intervallumon val´ o legkisebb n´egyzetes k¨ozel´ıt´es´er˝ol akkor besz´el¨ unk, ha a norma diszkr´et esetben (a ≤ x1 < x2 < . . . < xm ≤ b) kf k2 =
m X
!1 2
f 2 (xi ) w (xi )
,
i=1
folytonos esetben pedig Z kf k2 =
b 2
f (x) w (x) dx
21 ,
a
ahol a r¨ogz´ıtett w (x) s´ ulyf¨ uggv´enyre diszkr´etn´el a w (xi ) > 0 (i = 1, 2, . . . m), folytonosn´al pedig a w (x) ∈ C [a, b], w (x) > 0, ∀x ∈ [a, b] teljes¨ ul´es´et megk¨ ovetelj¨ uk. Fontos speci´alis eset a w (x) ≡ 1. Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Line´aris eset Legyen a H f¨ uggv´enyhalmaz olyan, hogy ismert φi : [a, b] → R(i = 1, . . . , n) f¨ uggv´enyek valamennyi line´aris kombin´aci´ oj´at tartalmazza, teh´at a h (x) f¨ uggv´eny alakja h(x) = a1 φ1 (x) + a2 φ2 (x) + . . . + an φn (x) =
n X
ai φi (x).
i=1
A φi f¨ uggv´enyeket alapf¨ uggv´ enyeknek vagy m´ask´eppen b´ azisf¨ uggv´ enyeknek nevezz¨ uk.
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Diszkr´et, lie´aris eset Fontos k´erd´es az approxim´aci´ os feladat megold´as´anak l´etez´ese ´es egy´ertelm˝ us´ege. Line´aris approxim´aci´ ora igaz az al´abbi ´all´ıt´as. T´etel Ha {φi }ni=1 ⊂ C [a, b] line´arisan f¨ uggetlenek, akkor b´armilyen norm´aban ´ e s minden f ∈ C [a, b] eset´en l´etezik legjobban k¨ozel´ıt˝o Pn h(x) = i=1 ai φi (x) f¨ uggv´eny.
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Diszkr´et, line´aris eset Legyen F = F (a0 , a1 . . . , an ). Ekkor meg kell oldani a F =
m X
2 → min f (xi ) − a1 φ1 (xi ) + . . . + aj φj (xi ) + . . . + an φn (xi )
i=i
sz´els˝o´ert´ekfeladatot. Ennek megold´asa pedig
∂F = 0, ∂aj
(j = 1, 2, . . . , n), vagyis a −2
m X
[f (xi ) − (a1 φ1 (xi ) + . . . + aj φj (xi ) + . . . + an φn (xi )] φj (xi ) = 0
i=i
line´aris egyenletrendszer megold´asa. (Az egyenlet teljes¨ ul´ese az approxim´aci´os feladat megold´as´anak m´ar eml´ıtett egy´ertelm˝ u l´etez´ese miatt elegend˝ o.) Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Diszkr´et, line´aris eset Egyszer˝ us´ıt´es ´es a szok´asos alakra val´ o rendez´es ut´an kapjuk, hogy a1
m X
φ1 (xi )φj (xi ) + . . . + an
m X
i=i
φn (xi )φj (xi ) =
i=i
(j = 1, 2, . . . , n). Vezess¨ uk be az hu, v i =
m X i=i
jel¨ol´est.
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
u(xi )v (xi )w (xi )
m X i=i
f (xi )φj (xi )
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Diszkr´et, line´aris eset Ezzel az egyenletrendszer alakja a k¨ ovetkez˝ o: a1 hφ1 , φ1 i + a1 hφ2 , φ1 i + . . . + an hφn , φ1 i = hf , φ1 i a1 hφ1 , φ2 i + a1 hφ2 , φ2 i + . . . + an hφn , φ2 i = hf , φ2 i .. . a1 hφ1 , φn i + a1 hφ2 , φn i + . . . + an hφn , φn i = hf , φn i
Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
LNM, f¨ uggv´ eny
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Megjegyz´esek A hu, v i =
m X
u(xi )v (xi )w (xi )
i=i
o¨sszef¨ ugg´essel egy skal´aris szorzatot defini´altunk a diszkr´et pontokon ´ertelmezett f¨ uggv´enyek k¨ oz¨ ott. Ez k´et Rn -beli vektornak a szorzata (ha w (x) ≡ 1). Az egyenletrendszer az u ´gynevezett norm´alegyenletrendszer. A G = [hφj , φi i]ni,j=1 , a = [a1 , . . . , an ]T ´es a b = [hf , φ1 i , . . . , hf , φn i]T jel¨ ol´esekkel t¨ om¨ orebben: Ga = b. A G ∈ Rn×n m´atrixot Gram-m´atrixnak nevezz¨ uk. Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
Gauss-Jordan m´ odszer
Legkisebb n´ egyzetek m´ odszere, egyenes
LNM, polinom
LNM, f¨ uggv´ eny
A legkisebb n´ egyzetek m´ odszere, tetsz˝ oleges f¨ uggv´ eny eset
Diszkr´et, line´aris eset m×n , a = [a , . . . , a ]T ∈ Rn , Legyen A = [φj (xi )]m,n 1 n i,j=1 ∈ R
b = y = [y1 , . . . , ym ]T ∈ Rm ´es m > n. Keres¨ unk olyan a∗ param´etervektort, amely az Aa − b hib´at valamilyen norm´aban minimaliz´alja. Ha l´etezik a Aa = b egyenletnek megold´asa, akkor a minimumfeladat egyen´ert´ek˝ u vele. Az euklideszi norm´aban megfogalmazott kAa − bk2 → min . minimumfeladat megold´asa az al´abbi t´etel: T´etel Az a ∈ R n akkor ´es csak akkor megold´asa a feladatnak, ha AT Aa = AT b. Line´ aris algebra numerikus m´ odszerei 6. el˝ oad´ as
