- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Zjednodušená ukázka:
Stáhnout celý tento materiál1
Deflnice: Matice, vektor
Matice typu (m;n) m¶a m •r¶adk”u a n sloupc”u. Sloupcov¶y n-rozm•ern¶y vektor je matice typu (n;1).
A =
0
BB
BB
@
a1;1 a1;2 ::: a1;n
a2;1 a2;2 ::: ...
... ... ... ...
am;1 ::: ::: am;n
1
CC
CC
A
~x =
0
BB
B@
x1
x2
...
xn
1
CC
CA
A = (ai;j) i = 1;:::;m ; j = 1;:::;n
Deflnice: Norma matice, vektoru
† •R¶adkov¶a norma
kAkm = max
i
nX
j=1
jai;jj k~xkm = max
i
jxij
† Sloupcov¶a norma
kAk‘ = max
j
mX
i=1
jai;jj k~xk‘ =
nX
i=1
jxij
† Euklidovsk¶a norma
kAkE =
ˆ mX
i=1
nX
j=1
jai;jj2
!1
2
k~xkE =
ˆ nX
i=1
jxij2
!1
2
Deflnice: Vlastn¶‡ •c¶‡slo
Necht’ A je •ctvercov¶a matice. Potom ka•zd¶e ‚ 2C pro kter¶e plat¶‡
A~x = ‚~x ~x 6=~0
se naz¶yv¶a vlastn¶‡ •c¶‡slo matice A a ~x je pak jemu p•r¶‡slu•sn¶y vlastn¶‡ vektor.
Deflnice: Charakteristick¶y polynom
Charakteristick¶y polynom •ctvercov¶e matice A stupn•e n je deflnov¶an vztahem
pA(‚) = det(A¡‚I) = (¡1)n‚n +b1‚n¡1 +:::+bn¡1‚+bn
kde I = diag(1) je jednotkov¶a matice stupn•e n.
V•eta: Vlastn¶‡ •c¶‡sla matice A jsou ko•reny jej¶‡ho charakteristick¶eho polynomu.
‚i 2 (A) () det(A¡‚I) = 0
Deflnice: Spektrum matice
Spektrum matice A je mno•zina v•sech vlastn¶‡ch •c¶‡sel t¶eto matice.
(A) =f‚i 2C : A~x = ‚i~x; i = 1;:::;ng
Deflnice: Spektr¶aln¶‡ polom•er matice
Spektr¶aln¶‡ polom•er matice je deflnov¶an jako absolutn¶‡ hodnota nejv•et•s¶‡ho vlastn¶‡ho •c¶‡sla.
‰(A) = max
i
fj‚ij2 (A) ; i = 1;:::;ng
Preliminary version { June 1, 2001 { 11:17
2
Deflnice: Itera•cn¶‡ metoda
Metoda pro generaci posloupnosti vektor”u ~x(k), kter¶e konverguj¶‡ k •re•sen¶‡ ~x⁄ soustavy rovnic A~x = ~b.
Obecnou itera•cn¶‡ metodu lze zapsat ve tvaru
~x(k+1) = Fk(~x(k);~x(k¡1);:::;~x(0))
Ve speci¶aln¶‡m p•r¶‡pad•e kdy je zobrazen¶‡ F line¶arn¶‡ a u•z¶‡v¶a pouze hodnoty z p•redchoz¶‡ iterace ~x(k), jedn¶a
se o line¶arn¶‡ jednokrokovou metodu. Ka•zd¶a takov¶a metoda m”uze b¶yt p•reps¶ana do tvaru
~x(k+1) = U~x(k) +~v
Matice U je tzv. itera•cn¶‡ matice p•r¶‡slu•sn¶a dan¶e itera•cn¶‡ metod•e.
V•eta: Nutn¶a a posta•cuj¶‡c¶‡ podm¶‡nka konvergence
Line¶arn¶‡ jednokrokov¶a metoda ~x(k+1) = U~x(k)+~v konverguje pro libovonou volbu po•c¶ate•cn¶‡ aproximace
~x(0) pr¶av•e tehdy, kdy•z je spektr¶aln¶‡ polom•er itera•cn¶‡ matice U men•s¶‡ ne•z jedna.
lim
k!1
~x(k) = ~x⁄ 8 ~x(0) 2Rn () ‰(U) < 1
V•eta: Posta•cuj¶‡c¶‡ podm¶‡nka konvergence
Necht’ n•ekter¶a z norem itera•cn¶‡ matice U je men•s¶‡ ne•z jedna, potom itera•cn¶‡ metoda konverguje pro
libovonou volbu po•c¶ate•cn¶‡ aproximace ~x(0).
kUk < 1 ) lim
k!1
~x(k) = ~x⁄ 8 ~x(0) 2Rn
Nav¶‡c plat¶‡ n¶asleduj¶‡c¶‡ odhad chyby (v t¶e•ze norm•e)
k~x(k) ¡~x(⁄)k • kUk1¡kUkk~x(k) ¡~x(k¡1)k
k~x(k) ¡~x(⁄)k • kUk
k
1¡kUkk~x
(1) ¡~x(0)k
Deflnice: Itera•cn¶‡ metody
Je d¶ana sostava rovnic A~x =~b. Necht’ matice A je rozlo•zena n¶asleduj¶‡c¶‡m zp”usobem
A = L + D + P
kde L je ost•re doln¶‡ troj¶uheln¶‡kov¶a matice, D je diagon¶aln¶‡ matice a P je ost•re horn¶‡ troj¶uheln¶‡kov¶a
matice. Jednotkovou matici ozna•c¶‡me I.
Potom m”u•zeme zapsat jednotliv¶e varianty obecn¶e line¶arn¶‡ jednokrokov¶e metody ~x(k+1) = U~x(k) +~v,
resp. r”uzn¶e jim p•r¶‡slu•sn¶e itera•cn¶‡ matice U v n¶asleduj¶‡c¶‡m tvaru:
† Prost¶a itera•cn¶‡ metoda
~x(k+1) = UPI~x(k) +~vPI kde UPI = (I¡A) ~vPI =~b
† Jacobiho metoda
~x(k+1) = UJ~x(k) +~vJ kde UJ =¡D¡1(L + P) ~vJ = D¡1~b
† Gauss-Seidelova metoda
~x(k+1) = UG~x(k) +~vG kde UG =¡(D + L)¡1P ~vG = (D + L)¡1~b
Preliminary version { June 1, 2001 { 11:17
3
Deflnice: Diagon¶aln•e dominantn¶‡ matice (•r¶adkov•e)
Matici A nazveme ost•re diagon¶aln•e dominantn¶‡, pokud plat¶‡
jai;ij >
X
j6=i
jai;jj i = 1;:::;n
V•eta: Posta•cuj¶‡c¶‡ podm¶‡nka konvergence Jacobiho metody
Je d¶ana soustava A~x =~b. Pokud je matice A ost•re diagon¶aln•e dominantn¶‡, potom Jacobiho metoda
konverguje pro libovonou volbu po•c¶ate•cn¶‡ aproximace ~x(0).
jai;ij >
X
j6=i
jai;jj i;j = 1;:::;n =) lim
k!1
~x(k) = ~x⁄ 8 ~x(0) 2Rn
Lemma: Vlastn¶‡ •c¶‡sla itera•cn¶‡ matice UJ
det(UJ ¡‚I) = 0 () det(L +‚D + P) = 0
Deflnice: Pozitivn•e deflnitn¶‡ matice
Matici A nazveme pozitivn•e deflnitn¶‡, pokud jsou v•sechny jej¶‡ hlavn¶‡ minory kladn¶e
a1;1 > 0;det
a
1;1 a1;2
a2;1 a2;2
¶
> 0;:::;det(A) > 0
V•eta: Posta•cuj¶‡c¶‡ podm¶‡nka konvergence Gauss-Seidelovy metody
Je d¶ana soustava A~x =~b. Pokud je spl•nena n•ekter¶a z n¶asleduj¶‡ch podm¶‡nek pro matici A
(a) matice A je ost•re diagon¶aln•e dominantn¶‡
(b) matice A je symetrick¶a a pozitivn•e deflnitn¶‡
potom Gauss-Seidelova metoda konverguje pro libovonou volbu po•c¶ate•cn¶‡ aproximace ~x(0).
Lemma: Vlastn¶‡ •c¶‡sla itera•cn¶‡ matice UG
det(UG ¡‚I) = 0 () det(‚L +‚D + P) = 0
Preliminary version { June 1, 2001 { 11:17
4
Motivace: Newtonova itera•cn¶‡ metoda v R1
Hledejme •re•sen¶‡ rovnice f(x) = 0, kde f : R1 7¡! R1 je (re¶aln¶a, obecn•e neline¶arn¶‡) funkce jedn¶e
(re¶aln¶e) prom•enn¶e.
y=f(x)
x x x x* (k+2) (k+1) (k)O
f(x )
f(x )
f(x )
(k)
(k+1)
(k+2)
y
x
Na z¶aklad•e v¶y•se uveden¶eho schematick¶eho zn¶azorn•en¶‡ lze odvodit n¶asleduj¶‡c¶‡ itera•cn¶‡ proces - Newtonovu
metodu
f(x(k))
x(k) ¡x(k+1) = f
0(x(k)) =) x(k+1) = x(k) ¡
‡
f0(x(k))
·¡1
f(x(k))
Aby m•el tento v¶yraz smysl je t•reba zajistit aby f0(x(k))6= 0.
Roz•s¶‡•ren¶‡: Newtonova itera•cn¶‡ metoda v Rn
Hledejme •re•sen¶‡ rovnice ~f(~x) =~0, kde ~f : Rn 7¡!Rn je n-rozm•ern¶a vektorov¶a funkce n prom•enn¶ych.
Rozpisem po slo•zk¶ach z¶‡sk¶ame n¶asleduj¶‡c¶‡ soustavu
f1(x1;x2;:::;xn) = 0
f2(x1;x2;:::;xn) = 0
...
fn(x1;x2;:::;xn) = 0
Na z¶aklad•e analogie s jednorozm•ern¶ym p•r¶‡padem lze odvodit n¶asleduj¶‡c¶‡ (n-rozm•ern¶e) zobecn•en¶‡
Newtonovy metody
x(k+1) = x(k) ¡
‡
f0(x(k))
·¡1
f(x(k)) =) ~x(k+1) = ~x(k) ¡
‡~
f0(~x(k))
·¡1 ~
f(~x(k))
Aby m•el tento v¶yraz smysl je t•reba zajistit aby det
‡~
f0(~x(k))
·
6= 0.
Symbolem ~f0(~x(k)) zna•c¶‡me Jacobiho matici zobrazen¶‡ ~f(~x(k)), tj.
~f0(x(k)) =
0
BB
BB
B@
@f1
@x1
@f1
@x2 :::
@f1
@xn
@f2
@x1
@f2
@x2 :::
...
... ... ... ...
@fn
@x1 ::: :::
@fn
@xn
1
CC
CC
CA
Preliminary version { June 1, 2001 { 11:17
5
Deflnice: Kubick¶y interpola•cn¶‡ spline
Je d¶ana mno•zina uzl”u xi 2 ha;bi ‰ R tak, •ze a = x0 < x1 < ::: < xk = b. D¶ale pak m•ejme ke
ka•zd¶emu xi i = 0;:::;k hodnotu yi 2R.
Kubick¶y interpola•cn¶‡ spline s(x) je funkce deflnovan¶a n¶asledovn•e
(a) s(x)2C2(ha;bi)
(b) s(x) = ai(x¡xi)3 +bi(x¡xi)2 +ci(x¡xi)+di pro x 2hxi;xi+1i
(c) s(xi) = yi
Pozn¶amka: Koeflcienty kubick¶eho interpola•cn¶‡ho splinu
Na z¶aklad•e v¶y•se uveden¶e deflnice lze odvodit n¶asleduj¶‡c¶‡ vztahy pro koeflcienty kubick¶eho interpola•cn¶‡ho
splinu.
ai = 16hi (s00i+1 ¡s00i )
bi = s00i2
ci = 1hi (yi+1 ¡yi)¡ hi6 (s00i+1 +2s00i )
di = yi
9>
>=
>>
;
i = 0;1;:::;k¡1
Nezn¶am¶e hodnoty s00i i = 0;:::;k ur•c¶‡me ze soustavy rovnic
hi¡1s00i¡1 +2(hi¡1 +hi)s00i +his00i+1 = 6h
i
(yi+1 ¡yi)¡ 6h
i¡1
(yi ¡yi¡1) i = 1;:::;k¡1
Tuto soustavu k¡1 rovnic pro k +1 nezn¶am¶ych je nutn¶e pro jednozna•cnou •re•sitelnost doplnit dv•ema
okrajov¶ymi podm¶‡nkami. Funkce z¶‡skan¶a v p•r¶‡pad•e volby s00(a) = s00(b) = 0 se naz¶yv¶a p•rirozen¶y kubick¶y
interpola•cn¶‡ spline.
Preliminary version { June 1, 2001 { 11:17
6
¶Uloha: Aproximace metodou nejmen•s¶‡ch •ctverc”u
Je d¶ana mno•zina uzl”u xi 2 ha;bi ‰ R (ne nutn•e od sebe r”uzn¶ych) a d¶ale pak m•ejme ke ka•zd¶emu
xi i = 1;:::;k p•ri•razenou hodnotu yi 2R.
C¶‡lem je naj¶‡t funkci f(x) (z p•redem vhodn•e zvolen¶eho prostoru funkc¶‡) tak, aby co nejl¶epe aproximovala
danou tabulku hodnot [xi;yi].
† Funkce f(x) obvykle vyb¶‡r¶ame z n•ejak¶eho kone•cn•edimenzion¶aln¶‡ho podprostoru funkc¶‡ s jednoduchou
strukturou. Nej•cast•eji pou•z¶‡van¶e jsou nap•r:
Algebraick¶e polynomy nejv¶y•se stupn•e n f(x) = a0 +a1x1 +:::+anxn
Trigonometrick¶e polynomy nejv¶y•se stupn•e n f(x) = a02 +Pnj=1(aj cos(jx)+bj sin(jx))
Zobecn•en¶e polynomy nejv¶y•se stupn•e n f(x) = Pnj=1 ajgj(x) kde gj(x) jsou b¶azov¶e funkce
† M•e•r¶‡tkem "kvality" aproximace je v¶yraz, je•z by vhodn¶ym zp”usobem vyj¶ad•ril pojem "vzd¶alenost funkce
f(x) od dan¶e mno•ziny bod”u [xi;yi]". Takov¶ymto m•e•r¶‡tkem je v p•r¶‡pad•e metody nejmen•s¶‡ch •ctverc”u
kvadratick¶a odchylka deflnovan¶a pro danou tabulku hodnot v¶yrazem –2(f) =Pki=1(f(xi)¡yi)2
•Re•sen¶‡: Aproximace algebraick¶ymi polynomy
1. Volba prostoru funkc¶‡ f(x) ¡! Algebraick¶e polynomy nejv¶y•se stupn•e n
f(x) = pn(x) =Pnj=0 ajxj = a0 +a1x1 +:::+anxn
2. Z¶apis kvadratick¶e odchylky ¡! –2(f) =Pki=1(f(xi)¡yi)2
–2(pn(x)) =Pki=1(Pnj=0 ajxji ¡yi)2 =Pki=1(a0 +a1xi +:::+anxni ¡yi)2
3. Nalezen¶‡ minima kvadratick¶e odchylky
Kvadratick¶a odchylka je funkc¶‡ hledan¶ych koeflcient”u aj; naopak hodnoty xi;yi jsou zad¶any.
Nutn¶e podm¶‡nky pro lok¶aln¶‡ minimum –2(pn(x)) proto jsou:
@(–2(pn))
@aj = 0)
8>
><
>>
:
Pk
i=1(a0 +a1xi
Vloženo: 25.04.2009
Velikost: 187,91 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2024 unium.cz