Numerické metody

Uˇcebn´ı ex y ysok´ych ˇskol
NUMERICK´
E METODY
doc. RND . Libo ˇ
Ce m´ak, CSc.
RND . Rudol Hla iˇcka, CSc.
©
doc. RND . Libo ˇ
Ce m´ak, CSc., RND . Rudol Hla iˇcka, CSc., 2025
Ta o publikace podl´eh´a licenci C ea i e Commons
U ed’ e au o a — Neuˇz´ı ej e d´ılo kome ˇcnˇe — Nezp aco ´a ej e 4.0 Mezin´a odn´ı
ISBN 978-80-214-6322-6
Tiˇs ˇen´e sk ip um Nume ick´e me ody au o ˚u doc. RND . Libo a ˇ
Ce m´aka, CSc. a RND . Rudol a Hla iˇcky, CSc. yˇslo
oce 2016. Od oku 2024 je snahou Fakul y s ojn´ıho inˇzen´y s ´ı VUT B nˇe pos upn´e zpˇ ´ıs upˇno ´an´ı uˇcebn´ıch ex ˚u
s uden ˚um elek onick´e e zi Digi ´aln´ı kniho nˇe VUT. Z PDF e ze sk ip z oku 2016 zniklo o o e-sk ip um.
ediˇcn´ı ada FSI VUT, ´uno 2025
Obsah
1´
U od do p oblema iky nume ick´ych me od 6
1.1 Chyby nume ick´ych ´ypoˇc ech . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Rep ezen ace ˇc´ısel poˇc´ı aˇci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Podm´ınˇenos ´uloh a algo i m˚u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 C iˇcen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2ˇ
Reˇsen´ı sous a line´a n´ıch o nic 16
2.1 Pˇ ´ım´e me ody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 Gausso a eliminaˇcn´ı me oda . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 V´ybˇe hla n´ıho p ku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.3 Vli zaok ouhlo ac´ıch chyb . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.4 Podm´ınˇenos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 I e aˇcn´ı me ody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3 C iˇcen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Ap oximace unkc´ı 41
3.1 In e polace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1 In e polace polynomem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.2 In e polaˇcn´ı splajny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.3 In e polace unkc´ı ´ıce p omˇenn´ych . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Me oda nejmenˇs´ıch ˇc e c˚u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3 C iˇcen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4 Nume ick´y ´ypoˇce de i ace a in eg ´alu 63
4.1 Nume ick´e de i o ´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Richa dsono a ex apolace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 Nume ick´e in eg o ´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.1 Z´akladn´ı o mule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.2 Sloˇzen´e o mule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3.3 Doplˇnuj´ıc´ı pozna ky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.4 C iˇcen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5ˇ
Reˇsen´ı neline´a n´ıch o nic 79
5.1 U ˇcen´ı poˇc´a eˇcn´ı ap oximace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2 Zpˇ esˇnuj´ıc´ı me ody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3 Sous a y neline´a n´ıch o nic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.4 C iˇcen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6 Op imalizace 97
6.1 Jedno ozmˇe n´a minimalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Minimalizace unkce ´ıce p omˇenn´ych . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3 C iˇcen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Li e a u a 110
4
Pˇ edmlu a
Ta o sk ip a jsou u ˇcena s uden ˚um p n´ıho oˇcn´ıku Fakul y s ojn´ıho inˇzen´y s ´ı VUT
B nˇe p o s udium pˇ edmˇe u Nume ick´e me ody I. Sk ip a jsou ˇeno ´ana adiˇcn´ım ´ema ˚um
nume ick´e ma ema iky: zd oj˚um chyb a jejich ˇs´ıˇ en´ı, ˇ eˇsen´ı sous a line´a n´ıch o nic, ap oximaci
unkc´ı, nume ick´emu de i o ´an´ı a in eg o ´an´ı, ˇ eˇsen´ı neline´a n´ıch o nic a minimalizaci unkc´ı.
Pˇ edpokl´ad´a se, ˇze ˇc en´aˇ sk ip m´a z´akladn´ı znalos i z line´a n´ı algeb y, z di e enci´aln´ıho
a in eg ´aln´ıho poˇc u unkc´ı jedn´e p omˇenn´e a z p og amo ´an´ı. Funkce ´ıce p omˇenn´ych se
om o ex u ysky uj´ı jen ods a c´ıch 3.1.3, 4.3.3, 5.3 a 6.2 a k pochopen´ı zde p ob´ı an´e
l´a ky pos aˇc´ı znalos i p ˚ubˇeˇznˇe z´ısk´a an´e pa alelnˇe p ob´ıhaj´ıc´ım ku zu MATEMATIKA II,
ˇeno an´em pˇ e ´aˇznˇe di e enci´aln´ımu a in eg ´aln´ımu poˇc u unkc´ı ´ıce p omˇenn´ych.
Do sk ip a jsme ke kaˇzd´emu ´ema u zaˇ adili klasick´e me ody, s anda dnˇe u ´adˇen´e kaˇzd´em
´u odn´ım ku zu nume ick´e ma ema iky, k e ´e slouˇz´ı pˇ ede ˇs´ım k pochopen´ı a ilus aci dan´e
p oblema iky. Klasick´e me ody jsou dnes jiˇz ˇcas o pˇ ekon´any e ek i nˇejˇs´ımi pos upy. Po ´ıˇz
s mode n´ımi, souˇcasnos i pouˇz´ı an´ymi algo i my, je ˇsak om, ˇze b´y aj´ı ˇcas o pomˇe nˇe
kompliko an´e, akˇze po ozumˇe jim neb´y ´a snadn´e. Pˇ es o se alespoˇn o nˇek e ´ych mode n´ıch
algo i mech om o ex u s uˇcnˇe zmiˇnujeme.
Vˇe ˇsinu me od jsme se pokusili zd˚u odni , p ecizn´ımu dokazo ´an´ı jsme se ˇsak ´umyslnˇe
yh´ybali. U nˇek e ´ych zen´ı u ´ad´ıme li e ´a n´ı zd oj, nˇemˇz lze naj´ı odpo ´ıdaj´ıc´ı ys ˇe len´ı.
Jde-li ˇsak o zen´ı na olik bˇeˇzn´e, ˇze ho lze naj´ı p ak icky jak´ekoli z´akladn´ı uˇcebnici nume-
ick´ych me od, pak li e ´a n´ı zd oj neu ´ad´ıme.
ˇ
Reˇsen´e pˇ ´ıklady jsme olili ak, aby pom´ahaly pochopi a pouˇz´ı a nˇekdy ponˇekud ˇeˇzko
s a i eln´e o mule a pos upy.
Sk ip a obsahuj´ı celou ˇ adu algo i m˚u, ˇ eˇsen´ych pˇ ´ıklad˚u a ´uloh k samos a n´emu p oc iˇcen´ı.
Vˇe ˇsina ´uloh se d´a jen ˇeˇzko z l´adnou bez yuˇzi ´ı poˇc´ı aˇce. P o o se pˇ edpokl´ad´a, ˇze s uden i
si nˇek e ´e algo i my sami MATLABu nap og amuj´ı.
Pˇ i zp aco ´an´ı sk ip jsme ych´azeli z os ˇedˇcen´ych uˇcebnic nume ick´e ma ema iky, jak´ymi
jsou napˇ . knihy [3], [22], ale ak´e z mode nˇejˇs´ıch knih [17], [7], [11] a [15]. Z l´aˇs ˇe poslednˇe
ci o an´a kniha Mole o a, k e ´a je olnˇe ke s aˇzen´ı na In e ne u, byla p o n´as elkou inspi ac´ı.
Pokud jde o ˇcesk´e zd oje, nej ´ıce podnˇe ˚u jsme ˇce pali z knih [19], [14], [8]. Mode n´ı ˇcesky psan´a
monog a ie nume ick´ych me od souˇcasnos i nen´ı k dispozici. K omˇe ´yˇse u eden´ych knih lze
ˇsak ˇceˇs inˇe ˇc´ıs ak´e [20], yb an´e kapi oly ˇeno an´e nume ick´ym me od´am [21] a [23].
Dou ´ame, ˇze se V´am, mil´y ˇc en´aˇ i, nume ick´e me ody zal´ıb´ı, a ˇze je dok´aˇze e pozdˇeji e ek i nˇe
yuˇz´ı pˇ i ˇ eˇsen´ı konk ´e n´ıch echnick´ych p obl´em˚u. Mˇej e ale p os´ım poˇ ´ad na zˇ e eli, ˇze o, co
se o nume ick´ych me od´ach om o ex u doz ´ı e, je op a du jen nap os ´y z´aklad. Zby ek je uˇz
na V´as, zd oj˚u in o mac´ı je dos a ek, zejm´ena d´ıky In e ne u. Z´akladn´ı o ien ace nume ick´ych
me od´ach V´am pak umoˇzn´ı k ali iko anˇe pouˇz´ı a nepˇ ebe n´e mnoˇzs ´ı p og am˚u, a
’uˇz olnˇe
dos upn´ych na In e ne u nebo p og am˚u kome ˇcn´ıch. A o se m˚uˇze hodi .
B no, lis opad 2016 Libo ˇ
Ce m´ak
Rudol Hla iˇcka
5

1. ´
U od do p oblema iky nume ick´ych me od
Pˇ i ˇ eˇsen´ı p obl´em˚u e´aln´eho s ˇe a se s ´ale ˇcas ˇeji se k´a ´ame s po ˇ ebou popsa
zkoumanou sku eˇcnos pomoc´ı ˇe ohodn´eho ma ema ick´eho modelu a en pak uspokoji ˇe
yˇ eˇsi . ˇ
Zijeme dobˇe poˇc´ı aˇc˚u a ak je pˇ i ozen´e, ˇze k ealizaci ma ema ick´eho modelu
poˇc´ı aˇc yuˇzijeme. Poˇc´ı aˇce um´ı p aco a elmi ychle s in o macemi k´odo an´ymi pomoc´ı
ˇc´ısel. A p ´a ˇe zde je m´ıs o p o nume ickou ma ema iku ( angliˇc inˇe nume ical analysis )
jakoˇz o ˇedn´ı discipl´ınu, k e ´a y ´ıj´ı a analyzuje me ody, jejichˇz echnologick´ym j´ad em
jsou manipulace s ˇc´ısly. V posledn´ıch le ech se anglicky psan´e li e a uˇ e m´ıs o e m´ınu
nume ical analysis s ´ale ˇcas ˇeji pouˇz´ı ´a e m´ın scien i ic compu ing (odpo ´ıdaj´ıc´ı ˇcesk´y
e m´ın n´am bohuˇzel nen´ı zn´am).
Kdyˇz chceme me odami nume ick´e ma ema iky yˇ eˇsi dan´y p obl´em popsan´y obec-
n´ym ma ema ick´ym modelem, mus´ıme ako ´y model nejdˇ ´ı e digi alizo a , o jes o -
mulo a ho e a u nume ick´e ´ulohy, jej´ıˇz s upn´ı i ´ys upn´ı da a jsou ˇc´ısla. Nume ick´a
me oda je pos up ˇ eˇsen´ı nume ick´e ´ulohy. Pˇ esn´y popis k ok˚u ealizuj´ıc´ıch nume ickou
me odu oznaˇcujeme jako algo i mus nume ick´e me ody. Lze ho yj´adˇ i jako posloupnos
akc´ı (p o edi eln´ych na poˇc´ı aˇci), k e ´e k dan´emu (pˇ esnˇe speci iko an´emu koneˇcn´emu)
soubo u s upn´ıch ˇc´ısel jednoznaˇcnˇe pˇ iˇ ad´ı odpo ´ıdaj´ıc´ı (pˇ esnˇe speci iko an´y koneˇcn´y)
soubo ´ys upn´ıch ˇc´ısel.
Pˇ ´ıp a a ozs´ahl´ych soubo ˚u s upn´ıch da b´y ´a oznaˇco ´ana jako p ep ocessing. Roz-
sah soubo u ´ysledn´ych ´udaj˚u je ˇcas o oh omn´y, p o ˇclo ˇeka nes a i eln´y, a p o o je ˇ eba
´ysledky hodnˇe zpˇ ´ıs upni ak, aby je zada a el ´ypoˇc u byl ˚ubec schopen yhodno i .
Me od´am, k e ´e o p o ´adˇej´ı, se ˇ ´ık´a pos p ocessing. Jednou z o em pos p ocessingu je
izualizace ´ysledk˚u.
Jako pˇ ´ıklad p obl´emu ze ˇzi o a u aˇzujme pˇ edpo ˇed’poˇcas´ı. Pohyb zduchu a -
mos ´eˇ e do edeme alespoˇn pˇ ibliˇznˇe popsa pomoc´ı sous a pa ci´aln´ıch di e enci´aln´ıch
o nic a hodn´ych doplˇnuj´ıc´ıch podm´ınek. Me odami nume ick´e ma ema iky dok´aˇzeme
y o o nice pˇ ibliˇznˇe ˇ eˇsi . Po ˇ ebn´a s upn´ı da a se z´ısk´a aj´ı pomoc´ı d uˇzic a pozemn´ıch
me eo ologick´ych s ano iˇs
’. V´ysledky nume ick´ych ´ypoˇc ˚u zp aco an´e do animo an´ych
me eo ologick´ych map pak sledujeme ele izn´ı pˇ edpo ˇedi poˇcas´ı.
Pˇ i ˇ eˇsen´ı e´aln´ych p obl´em˚u ´emˇeˇ nikdy nez´ısk´ame pˇ esn´e ˇ eˇsen´ı, mus´ıme se spokoji
jen s ˇ eˇsen´ım pˇ ibliˇzn´ym, k e ´e je za ´ıˇzeno chybami. Naˇs´ım c´ılem je o ganizo a ´ypoˇce
ak, aby celko ´a chyba byla co nejmenˇs´ı.
Pˇ ede ˇs´ım se mus´ıme y a o a h ub´ych lidsk´ych chyb, k e ´e ypl´y aj´ı z nepochopen´ı
p obl´emu a z nepozo nos i nebo nedbalos i ˇclo ˇeka pˇ i jeho ˇ eˇsen´ı.
Chyba ma ema ick´eho modelu. Pˇ i y ´aˇ en´ı ma ema ick´eho modelu e´aln´eho p o-
bl´emu p o ´ad´ıme ˇzdy jis ´e idealizace. Rozd´ıl mezi ˇ eˇsen´ım idealizo an´eho p obl´emu
a ˇ eˇsen´ım p obl´emu e´aln´eho naz´y ´ame chybou ma ema ick´eho modelu. Do ´e o ka ego ie
chyb zah nujeme ak´e chyby e s upn´ıch ´udaj´ıch.
Pˇ ´ıklad. M´ame u ˇci po ch zemsk´eho pl´aˇs ˇe. K ´ypoˇc u pouˇzijeme zo ec S= 4π 2p o
po ch koule o polomˇe u . Chyba modelu spoˇc´ı ´a pˇ edpokladu, ˇze Zemˇe je koule.
Chyba nume ick´e me ody. Jes liˇze k ˇ eˇsen´ı (nume ick´e) ´ulohy pouˇzijeme nume ickou
me odu, k e ´a n´am neposky ne pˇ esn´e ( eo e ick´e) ˇ eˇsen´ı dan´e ´ulohy, pak chybu, k e ´e
se dopus ´ıme, naz´y ´ame chybou nume ick´e me ody. D˚uleˇzi ou souˇc´as ´ı n´a hu nume ick´e
6
me ody je odhad chyby nume ick´e me ody.
Pˇ ´ıklad. M´ame spoˇc´ı a hodno u unkce sin 1 seˇc en´ım koneˇcn´eho poˇc u ˇclen˚u Taylo o y
ˇ ady
sin x=x−x3
3! +x5
5! −x7
7! +x9
9! −···+ (−1)nx2n+1
(2n+ 1)! +···
p o x= 1. Je zn´amo, ˇze seˇc en´ım p n´ıch ˇ ´ı ˇclen˚u ˇ ady se dopus ´ıme chyby elikos i
nej ´yˇse 1/7!, obecnˇe seˇc en´ım p n´ıch nˇclen˚u se dopus ´ıme chyby nej ´yˇse 1/(2n+ 1)!.
Zaok ouhlo ac´ı chyby. Pˇ i p ´aci na poˇc´ı aˇci m˚uˇzeme k ep ezen aci ˇc´ısel pouˇz´ı jen
koneˇcn´y poˇce ci e . P acujeme p o o s pˇ ibliˇzn´ymi hodno ami ˇc´ısel, k e ´e dos aneme
zaok ouhlen´ım pˇ esn´ych hodno . Zaok ouhlo ac´ı chyby znikaj´ı uˇz pˇ i kl´ad´an´ı da do
poˇc´ı aˇce, dalˇs´ı pak znikaj´ı pˇ i ˇc´ıseln´ych ´ypoˇc ech. Pˇ i ˇspa nˇe o ganizo an´em ´ypoˇc u
m˚uˇze doj´ı d˚usledku nah omadˇen´ı zaok ouhlo ac´ıch chyb k nap os ´emu znehodnocen´ı
´ysledku, iz pˇ ´ıklad 1.7.
Pˇ ´ıklad. ˇ
C´ıslo πneum´ıme do poˇc´ı aˇce loˇzi pˇ esnˇe. Tak´e ´ysledek ope ace, pˇ i n´ıˇz ˇc´ıslo 2
dˇel´ıme ˇc´ıslem 3, nezob az´ıme na s anda dn´ım poˇc´ı aˇci p acuj´ıc´ım s bin´a n´ımi ˇc´ısly pˇ esnˇe.
Je ˇ eba m´ı na pamˇe i, ˇze pˇ i ˇ eˇsen´ı e´aln´eho p obl´emu ys upuj´ı ob ykle ˇsechny
chyby souˇcasnˇe.
1.1. Chyby nume ick´ych ´ypoˇc ech
Absolu n´ı a ela i n´ı chyba. Ve ´ypoˇc ech jsme ˇcas o nuceni nah adi pˇ esn´e ˇc´ıslo x
pˇ ibliˇzn´ym ˇc´ıslem ˜x.ˇ
C´ıslo ˜xpo om naz´y ´ame ap oximac´ı ˇc´ısla x. Rozd´ıl ˜x−x= ∆x
naz´y ´ame absolu n´ı chybou ap oximace ˜xa ˇc´ıslo
∆x
x=˜x−x
x, x 6= 0 ,
naz´y ´ame ela i n´ı chybou ap oximace ˜x. P o |∆x| ≤ εse pouˇz´ı ´a ak´e symbolick´y z´apis
˜x=x±εa m´ın´ı se ´ım, ˇze x−ε≤˜x≤x+ε. Podobnˇe se p o |∆x/x| ≤ δpouˇz´ı ´a z´apis
˜x=x(1 ±δ). Absolu n´ı hodno a ela i n´ı chyby se ˇcas o u ´ad´ı p ocen ech.
Nyn´ı posoud´ıme chybu, k e ´e se dopus ´ıme pˇ i ´ypoˇc u hodno y (x1, x2,...,xn)
unkce , kdyˇz pˇ esn´e hodno y xinah ad´ıme pˇ ibliˇzn´ymi hodno ami ˜xi=xi+ ∆xi.
Z Taylo o a oz oje (˜
x) okolo bodu xdos aneme
(˜
x) = (x) +
n
X
i=1
∆xi
∂ (x)
∂xi
+1
2
n
X
i,j=1
∆xi∆xj
∂2 (x)
∂xi∂xj
+···.
Po aˇzujeme-li souˇciny chyb ∆xi∆xjza mal´e, m´ame p o absolu n´ı chybu
|∆ (x)|:= | (˜
x)− (x)|.
=
n
X
i=1
∂ (x)
∂xi
∆xi≤
n
X
i=1 
∂ (x)
∂xi·|∆xi|(1.1)
7
a p o chybu ela i n´ı

∆ (x)
(x).
=
n
X
i=1
xi
(x)
∂ (x)
∂xi
∆xi
xi≤
n
X
i=1 
xi
(x)
∂ (x)
∂xi·
∆xi
xi.(1.2)
Pˇ i p ak ick´ych odhadech se hodno a unkce a hodno y jej´ıch de i ac´ı ∂ /∂xina p a ´ych
s an´ach pˇ ibliˇzn´ych ne o nos ´ı (1.2) a (1.1) poˇc´ı aj´ı bodˇe ˜
x.
Chyby z´akladn´ıch a i me ick´ych ope ac´ı. Z ol´ıme-li (x, y) = x±y, dos aneme p o
absolu n´ı a ela i n´ı chybu souˇc u a ozd´ılu
∆(x±y).
= ∆x±∆y , ∆(x±y)
x±y
.
=x
x±y
∆x
x±y
x±y
∆y
y.(1.3)
P o yj´adˇ en´ı chyby souˇcinu ol´ıme (x, y) = xy a obd ˇz´ıme
∆(xy).
=y∆x+x∆y , ∆(xy)
xy
.
=∆x
x+∆y
y(1.4)
a p o chybu pod´ılu dos aneme olbou (x, y) = x/y
∆x
y.
=1
y∆x−x
y2∆y , ∆(x/y)
x/y
.
=∆x
x−∆y
y.(1.5)
Vˇsimnˇe e si, ˇze ela i n´ı chyba souˇc u esp. ozd´ılu m˚uˇze b´y ´y aznˇe ˇe ˇs´ı neˇz ela i n´ı
chyby ope and˚u pˇ ´ıpadˇe, kdyˇz |x±y|je pods a nˇe menˇs´ı neˇz |x|nebo |y|. Pˇ i dˇelen´ı
mal´ym ˇc´ıslem je (d´ıky d uh´e mocninˇe y e jmeno a eli) ´yznamn´a chyba absolu n´ı.
Pla n´e dekadick´e ci y. Nech
’˜xje ap oximace ˇc´ısla x, k e ou zapiˇsme mocninn´em
dekadick´em oz oji jako
˜x=±[d1·10e+d2·10e−1+···+dk·10e+1−k+dk+1 ·10e−k+...], d16= 0 .
ˇ
Rekneme, ˇze k− ´a dekadick´a ci a dkap oximace ˜xje pla n´a, jes liˇze
|˜x−x| ≤ 5·10e−k,(1.6)
j. kdyˇz se ˜xliˇs´ı od xnej ´yˇse o 5 jedno ek ˇ ´adu pˇ ´ısluˇsn´eho n´asleduj´ıc´ı ci ˇ e. Pla ´ı-li
ne o nos (1.6) p o k≤p, ale p o k=p+ 1 uˇz nepla ´ı, ˇ ´ık´ame, ˇze ˜xm´a ppla n´ych ci e .
ˇ
C´ıslo ˜x=±d1,d2d3. . . dp·10e, k e ´e m´a ˇsech pci e pla n´ych, je sp ´a nˇe zaok ouhlenou
hodno ou ˇc´ısla x.
Pla n´a dese inn´a m´ıs a. ˇ
Rekneme, ˇze ap oximace ˜xˇc´ısla xm´a k- ´e dese inn´e m´ıs o
pla n´e, jes liˇze
|˜x−x| ≤ 5·10−k−1,(1.7)
j. kdyˇz se ˜xliˇs´ı od xnej ´yˇse o 5 jedno ek ˇ ´adu pˇ ´ısluˇsn´eho n´asleduj´ıc´ımu dese inn´emu
m´ıs u. Pla ´ı-li ne o nos (1.7) p o k≤p, ale p o k=p+ 1 uˇz nepla ´ı, ˇ ´ık´ame, ˇze ˜x
m´a ppla n´ych dese inn´ych m´ıs . Ve sp ´a nˇe zaok ouhlen´em ˇc´ısle je edy kaˇzd´e dese inn´e
m´ıs o pla n´e.
V n´asleduj´ıc´ı abulce u ´ad´ıme nˇekolik pˇ ´ıklad˚u:
8
x˜xpla n´e ci y pla n´a dese inn´a m´ıs a
284 290 1 −
−45,8472 −45,798 3 1
100,002 99,9973 4 2
99,9973 100,002 5 2
−0,003728 −0,0041 1 3
1,841 ·10−62,5·10−60 5
Pˇ i odeˇc´ı ´an´ı d ou bl´ızk´ych ˇc´ısel doch´az´ı ke z ´a ˇe pla n´ych ci e , jak o om s ˇedˇc´ı
Pˇ ´ıklad 1.1. Je-li
x= 4,998949 ·101,˜x= 4,999 ·101,|∆x|= 5,10 ·10−4,
∆x
x.
= 1,020 ·10−5,
y= 5,001848 ·101,˜y= 5,002 ·101,|∆y|= 1,52 ·10−3,
∆y
y.
= 3,039 ·10−5,
pak p o ozd´ıly z=y−x, ˜z= ˜y−˜xdos ´a ´ame
z= 2,899 ·10−2,˜z= 3 ·10−2,|∆z|= 1,01 ·10−3,
∆z
z.
= 3,484 ·10−2,
akˇze ˜zm´a jen jednu pla nou ci u, za ´ımco ˜xi ˜ymaj´ı ˇc yˇ i pla n´e ci y. 
Pˇ ´ıklad 1.2. Nech
’x= 1,3262 ±5·10−5,y=−6,5347 ±5·10−5,z= 13,235 ±5·10−4.
M´ame u ˇci ap oximaci unkˇcn´ı hodno y =xy/z, absolu n´ı a ela i n´ı chybu a poˇce
pla n´ych ci e ´ysledku.
Spoˇc eme ˜
= ˜x˜y/˜z=−6,548031 ...·10−1.Podle (1.1) pak pˇ ibliˇznˇe pla ´ı

∆
˜
≤
˜y
˜z∆x+
˜x
˜z∆y+
˜x˜y
˜z2∆z
˜x˜y
˜z
−1
=
∆x
˜x+
∆y
˜y+
∆z
˜z.
= 8,31 ·10−5.
Od ud |∆ |.
= 8,31 ·10−5·|˜
|.
= 5,44 ·10−5<5·10−1−3, akˇze (se ˇ emi pla n´ymi ci ami)
=−0,6548 ±0,0001. 
1.2. Rep ezen ace ˇc´ısel poˇc´ı aˇci
Re´aln´a ˇc´ısla jsou poˇc´ı aˇc´ıch ep ezen o ´ana sys ´emu ˇc´ısel s pohybli ou ˇ ´ado ou
ˇc´a kou ( angliˇc inˇe loa ing poin numbe s). Z´akladn´ı myˇslenka je podobn´a semiloga i -
mick´emu z´apisu ( angliˇc inˇe scien i ic no a ion), nˇemˇz napˇ . ˇc´ıslo 245700 p´ıˇseme jako
2,457·105a ˇc´ıslo 0,0005768 jako 5,768·10−4. V om o o m´a u se dese inn´a ˇc´a ka pohybuje
( doslo n´em pˇ ekladu pla e) z´a islos i na dekadick´em exponen u. Fo m´alnˇe lze sys ´em
Fno malizo an´ych ˇc´ısel pohybli ´e ˇ ´ado ´e ˇc´a ky cha ak e izo a ˇc yˇ mi cel´ymi ˇc´ısly:
βz´aklad ˇc´ıseln´e sous a y (β≥2),
ppˇ esnos (p≥1),
[L , U] ozsah exponen u (L < 0< U).
9
2. ˇ
Reˇsen´ı sous a line´a n´ıch o nic
Jednou z nejˇcas ˇeji se ysky uj´ıc´ıch ´uloh ´ypoˇce n´ı p axe je ´uloha yˇ eˇsi sous a u
line´a n´ıch o nic. Tako ´e sous a y b´y aj´ı ˇcas o elmi ozs´ahl´e, souˇcasn´a ´ypoˇce n´ı ech-
nika umoˇzˇnuje pˇ ija eln´ych ˇcasech yˇ eˇsi sous a y s nˇekolika mili´ony nezn´am´ych. Me-
ody ˇ eˇsen´ı dˇel´ıme na pˇ ´ım´e a i e aˇcn´ı. Pˇ ´ım´e me ody jsou ako ´e me ody, k e ´e dodaj´ı
koneˇcn´em poˇc u k ok˚u pˇ esn´e ˇ eˇsen´ı za pˇ edpokladu, ˇze ´ypoˇce p ob´ıh´a bez zaok ouh-
lo ac´ıch chyb, edy zcela pˇ esnˇe. I e aˇcn´ı me ody posky nou jen ˇ eˇsen´ı pˇ ibliˇzn´e. To ale
˚ubec ne ad´ı, pokud je pˇ ibliˇzn´e ˇ eˇsen´ı dos a eˇcnˇe dob ou ap oximac´ı ˇ eˇsen´ı pˇ esn´eho.
Poˇce k ok˚u i e aˇcn´ı me ody z´a is´ı na poˇzado an´e pˇ esnos i.
Budeme se edy zab´y a ˇ eˇsen´ım sous a y line´a n´ıch o nic
a11 x1+a12 x2+··· +a1nxn=b1,
a21 x1+a22 x2+··· +a2nxn=b2,
.
.
..
.
.
an1x1+an2x2+··· +ann xn=bn.
(2.1)
Sous a u (2.1) m˚uˇzeme ps´a e a u
n
X
j=1
aijxj=bi, i = 1,2,...,n, (2.2)
nebo ma ico ´em a u
Ax =b,(2.3)
kde
A=




a11 a12 ··· a1n
a21 a22 ··· a2n
.
.
..
.
..
.
..
.
.
an1an2··· ann




,x=




x1
x2
.
.
.
xn




,b=




b1
b2
.
.
.
bn




.
Ma ici Anaz´y ´ame ma ic´ı sous a y,bje ek o p a ´e s any ax ek o nezn´am´ych.
Budeme pˇ edpokl´ada , ˇze ma ice sous a y je egul´a n´ı, akˇze ˇ eˇsen´a sous a a m´a jedin´e
ˇ eˇsen´ı.
2.1. Pˇ ´ım´e me ody
2.1.1. Gausso a eliminaˇcn´ı me oda
Z´akladn´ı pˇ ´ımou me odou ˇ eˇsen´ı sous a line´a n´ıch o nic je Gausso a eliminaˇcn´ı
me oda, s uˇcnˇe GEM. Skl´ad´a se ze d ou ˇc´as ´ı. V pˇ ´ım´em chodu GEM se sous a a (2.1)
pˇ e ede na ek i alen n´ı sous a u
Ux =c,(2.4)
16

kde Uje z . ho n´ı oj´uheln´ıko ´a ma ice, coˇz je ma ice, k e ´a m´a pod hla n´ı diagon´alou
ˇsechny p ky nulo ´e, j. U={uij}n
i,j=1 auij = 0 p o i > j,
U=









u11 u12 u13 ··· u1,n−1u1n
0u22 u23 ··· u2,n−1u2n
0 0 u33 ··· u3,n−1u3n
.
.
..
.
..
.
..
.
..
.
..
.
.
0 0 ··· 0un−1,n−1un−1,n
0 0 0 ··· 0unn









.
Ve zpˇe n´em chodu se pak ˇ eˇs´ı sous a a (2.4). P o oˇze Aje egul´a n´ı, je ak´e U egul´a n´ı,
coˇz znamen´a, ˇze diagon´aln´ı p ky uii 6= 0, i= 1,2,...,n. D´ıky omu ypoˇc eme z posledn´ı
o nice xn, z pˇ edposledn´ı xn−1a d. aˇz nakonec z p n´ı o nice ypoˇc eme x1.
Pˇ ´ım´y chod GEM. P o usnadnˇen´ı popisu pˇ ´ım´eho chodu GEM poloˇz´ıme A(0) =A,
b(0) =b, p ky ma ice ma ice A(0) oznaˇc´ıme a(0)
ij ≡aij a p ky ek o u b(0) oznaˇc´ıme
b(0)
i≡bi. Pˇ ´ım´y chod GEM popisuje n´asleduj´ıc´ı
algo i mus GEMz (z´akladn´ı, bez ´ybˇe u hla n´ıho p ku):
o k:= 1 o n−1do
begin
A(k):= A(k−1) ;b(k):= b(k−1) ;
o i:= k+ 1 o ndo
begin
mik := a(k)
ik /a(k)
kk ;
o j:= k+ 1 o ndo a(k)
ij := a(k)
ij −mika(k)
kj ;
b(k)
i:= b(k)
i−mikb(k)
k;
end
end
Pˇ ´ım´y chod m´a n−1 k ok˚u. V k- ´em k oku se sous a a o nic A(k−1)x=b(k−1) ans-
o muje na sous a u A(k)x=b(k). P n´ıch k o nic se uˇz nemˇen´ı. Ta o sku eˇcnos je al-
go i mu GEMz yj´adˇ ena pˇ ´ıkazy A(k):= A(k−1) ab(k):= b(k−1). Smyslem ans o mace
je ylouˇci nezn´amou xkz o nic i > k, j. ynulo a poddiagon´aln´ı koe icien y k- ´em
sloupci ma ice A(k). Dos´ahneme oho ak, ˇze od i- ´e o nice odeˇc eme mik n´asobek k- ´e
o nice. Mul iplik´a o y mik musej´ı zajis i , aby pozici (i, k) ma ice A(k) znikla nula:
a(k)
ik −mika(k)
kk = 0 =⇒mik =a(k)
ik /a(k)
kk .
ˇ
C´ıslo a(k)
kk se naz´y ´a hla n´ı p ek nebo ak´e pi o . Pˇ i ´ypoˇc u mul iplik´a o u mik m˚uˇze al-
go i mus GEMz zha a o a pˇ ´ıpadˇe, ˇze a(k)
kk = 0. Tomu o p obl´emu bychom se mohli y-
hnou , kdybychom k- ou o nici p ohodili s nˇek e ou z dalˇs´ıch o nic, k e ´a m´a u p omˇenn´e
xknenulo ´y koe icien . Pos up zaloˇzen´y na ´e o myˇslence se naz´y ´a GEM s ´ybˇe em
hla n´ıho p ku. Pod obnˇe se j´ım budeme zab´y a n´asleduj´ıc´ım ods a ci. GEMz je edy
algo i mus GEM bez ´ybˇe u hla n´ıho p ku.
17
V om o ods a ci budeme pˇ edpokl´ada , ˇze Aje ako ´a ma ice sous a y, p o k e ou
jsou ˇsechny hla n´ı p ky a(k)
kk nenulo ´e.
P og amo ´an´ı. P ky ma ic A(k)ucho ´a ´ame d ou ozmˇe n´em poli Aa p ky ek o ˚u
b(k) jedno ozmˇe n´em poli b. Pˇ ´ıkazy A(k):= A(k−1) ab(k):= b(k−1) se p o o e sku eˇc-
nos i nep o ´adˇej´ı. P o oˇze pozici (i, k) pole A znikne nula, lze p ek A(i,k) yuˇz´ı p o
uskladnˇen´ı mul iplik´a o u mik.
LU ozklad. Po ukonˇcen´ı pˇ ´ım´eho chodu je ho n´ı oj´uheln´ıko ´a ma ice U o nici (2.4)
u ˇcena diagon´aln´ımi a naddiagon´aln´ımi p ky ma ice A(n−1), j.
uij := 0 p o j= 1,2,...,i−1,
a(n−1)
ij p o j=i, i + 1,...,n, i= 1,2,...,n. (2.5)
Vek o c (2.4) je ans o mo anou p a ou s anou b(n−1), j.
ci:= b(n−1)
i, i = 1,2,...,n. (2.6)
Mul iplik´a o y mij z pˇ ´ım´eho chodu um´ıs ´ıme do doln´ı oj´uheln´ıko ´e ma ice L={ℓij}n
i,j=1,
ℓij = 0 p o j > i,
L=









ℓ11 0 0 ··· 0 0
ℓ21 ℓ22 0··· 0 0
ℓ31 ℓ32 ℓ33 ··· 0 0
.
.
..
.
..
.
..
.
..
.
..
.
.
ℓn−1,1ℓn−1,2ℓn−1,3. . . ℓn−1,n−10
ℓn1ℓn2ℓn3··· ℓn,n−1ℓnn









,
de ino an´e pˇ edpisem
ℓik := 


0 p o i= 1,2,...,k−1,
1 p o i=k ,
mik p o i=k+ 1, k + 2,...,n,
k= 1,2,...,n. (2.7)
D´a se uk´aza , ˇze pla ´ı
A=LU .(2.8)
Vyj´adˇ en´ı ma ice Ajako souˇcinu doln´ı oj´uheln´ıko ´e ma ice La ho n´ı oj´uheln´ıko ´e
ma ice Use naz´y ´a LU ozklad ma ice A. Ten je moˇzn´e pouˇz´ı k pozdˇejˇs´ımu ˇ eˇsen´ı sou-
s a y o nic se s ejnou ma ic´ı sous a y A, a ˇsak s jinou p a ou s anou. To je uˇzi eˇcn´e
zejm´ena pˇ i ˇ eˇsen´ı posloupnos i ´uloh Axi=bi, kdy se no ´a p a ´a s ana bim˚uˇze ses a i
aˇz po ´e, co se yˇ eˇsily pˇ edchoz´ı sous a y Axk=bkp o k < i.
Ukaˇzme si, jak lze sous a u LUx =be ek i nˇe yˇ eˇsi . Kdyˇz si oznaˇc´ıme Ux =y,
id´ıme, ˇze yje ˇ eˇsen´ı sous a y Ly =b. U ˇc´ıme edy nejdˇ ´ı e yjako ˇ eˇsen´ı sous a y
Ly =ba pak xjako ˇ eˇsen´ı sous a y Ux =y, j.
Ly =b,Ux =y.(2.9)
18
Zˇ ejmˇe y=b(n−1) je ans o mo an´a p a ´a s ana z´ıskan´a algo i mem GEMz.
Sous a u Ly =b yˇ eˇs´ıme snadno, z p n´ı o nice ypoˇc´ı ´ame y1, ze d uh´e o nice
y2a d. aˇz nakonec z posledn´ı o nice ypoˇc´ı ´ame yn. Sous a u Ux =yˇ eˇs´ıme pozp´a ku,
j. z posledn´ı o nice ypoˇc eme xn, z pˇ edposledn´ı xn−1a d. aˇz nakonec z p n´ı o nice
ypoˇc eme x1.
Pˇ i ˇ eˇsen´ı sous a o nic b´y ´a LU ozklad oznaˇco ´an ak´e jako eliminace nebo pˇ ´ım´y
chod a ´ypoˇce ˇ eˇsen´ı podle (2.9) b´y ´a oznaˇco ´an jako zpˇe n´y chod.
Kdy lze algo i mus GEMz pouˇz´ı ? Jak jsme jiˇz u edli, slab´ym m´ıs em algo i mu
GEMz m˚uˇze b´y ´ypoˇce mul iplik´a o u mik, nebo
’obecnˇe nelze ylouˇci , ˇze p ˚ubˇehu
eliminace znikne a(k)
kk = 0. V aplikac´ıch se ˇsak pomˇe nˇe ˇcas o ˇ eˇs´ı sous a y o nic, p o
k e ´e nulo ´y pi o algo i mu GEMz zniknou nem˚uˇze. Abychom ako ´e sous a y mohli
popsa , za edeme si nˇekolik no ´ych pojm˚u.
ˇ
Rekneme, ˇze ma ice A={aij}n
i,j=1 je yze diagon´alnˇe dominan n´ı, jes liˇze
|aii|>
n
X
j= 1
j6=i
|aij|, i = 1,2,...,n, (2.10)
nebo-li slo y, kaˇzd´em ˇ ´adku je absolu n´ı hodno a diagon´aln´ıho p ku ˇe ˇs´ı neˇz souˇce
absolu n´ıch hodno zb´y aj´ıc´ıch p k˚u oho o ˇ ´adku. I kdyˇz ma ice Asous a y o nic
Ax =bdiagon´alnˇe dominan n´ı nen´ı, lze nˇekdy hodn´ym pˇ eskl´ad´an´ım o nic doc´ıli
oho, ˇze ma ice ˆ
A ak o znikl´e ek i alen n´ı sous a y o nic ˆ
Ax =ˆ
buˇz diagon´alnˇe
dominan n´ı je.
V aplikac´ıch se ak´e pomˇe nˇe ˇcas o se k´a ´ame s z . pozi i nˇe de ini n´ımi ma icemi.
Tako ´e ma ice lze speci iko a pomoc´ı ˇ ady na z´ajem ek i alen n´ıch de inic. Jednu z nich
si ed’u edeme: ˇ ekneme, ˇze ma ice A={aij}n
i,j=1 je pozi i nˇe de ini n´ı, jes liˇze je syme-
ick´a a p o kaˇzd´y nenulo ´y sloupco ´y ek o x= (x1, x2,...,xn)Tpla ´ı
xTAx =
n
X
i,j=1
xiaijxj>0.(2.11)
O ˇeˇ i pˇ ´ımo u o podm´ınku nen´ı snadn´e. Je-li ˇsak A egul´a n´ı, pak z (2.11) okamˇzi ˇe
plyne, ˇze ATAje pozi i nˇe de ini n´ı. (Dokaˇz e o!) Vyn´asob´ıme-li edy sous a u o nic
Ax =bzle a ma ic´ı AT, dos aneme ek i alen n´ı sous a u ATAx =ATbs pozi i nˇe
de ini n´ı ma ic´ı sous a y. Ten o pos up se ˇsak p o p ak ick´e ˇ eˇsen´ı sous a o nic nehod´ı
(ope ace ATA yˇzaduje elk´y objem ´ypoˇc ˚u, u i e aˇcn´ıch me od se na ´ıc ´yznamnˇe
zho ˇsuje ychlos kon e gence).
Pˇ i ˇ eˇsen´ı konk ´e n´ıch p ak ick´ych ´uloh b´y ´a ob ykle uˇz pˇ edem zn´amo (z po ahy
ˇ eˇsen´eho p obl´emu a ze zp˚usobu jeho disk e izace), zda ma ice znikaj´ıc´ıch sous a li-
ne´a n´ıch o nic jsou ( esp. nejsou) pozi i nˇe de ini n´ı. U ed’me si ˇsak pˇ es o alespoˇn
jednu ˇcas o u ´adˇenou (nu nou a pos aˇcuj´ıc´ı) podm´ınku pozi i n´ı de ini nos i, zn´amou
jako
Syl es e o o k i ´e ium. ˇ
C e co ´a syme ick´a ma ice A={aij}n
i,j=1 je pozi i nˇe de i-
ni n´ı, p ´a ˇe kdyˇz jsou kladn´e de e minan y ˇsech hla n´ıch oho ´ych subma ic {aij}k
i,j=1,
19
k= 1,2,...,n, j. kdyˇz pla ´ı
a11 >0,a11 a12
a21 a22>0,
a11 a12 a13
a21 a22 a23
a31 a32 a33>0, . . . , 
a11 . . . a1n
.
.
..
.
.
an1. . . ann

>0.
D´a se uk´aza , ˇze algo i mus GEMz lze pouˇz´ı p o ˇ eˇsen´ı sous a , jejichˇz ma ice je bud’ o
yze diagon´alnˇe dominan n´ı nebo pozi i nˇe de ini n´ı.´
Uspˇeˇsn´e pouˇzi ´ı algo i mu GEMz lze
za uˇci ak´e p o dalˇs´ı ypy ma ic, k e ´e se pˇ i ˇ eˇsen´ı p ak ick´ych ´uloh ˇcas o ysky uj´ı ( iz
napˇ . [4], [13]).
V´ypoˇc o ´a n´a oˇcnos GEM. Pˇ ´ım´y chod GEM yˇzaduje 1
3n3+O(n2) ope ac´ı n´asobi-
c´ıch ( j. n´asoben´ı nebo dˇelen´ı) a 1
3n3+O(n2) ope ac´ı sˇc´ı ac´ıch ( j. sˇc´ı ´an´ı nebo odeˇc´ı ´an´ı).
Symbolem O(n2) jsme pˇ i om yj´adˇ ili ˇ ´ado ˇe m´enˇe ´yznamn´y poˇce ope ac´ı ˇ ´adu n2
( a u α2n2+α1n+α0, kde α2,α1,α0jsou ˇc´ısla nez´a isl´a na n). ˇ
Clen 1
3n3sou is´ı s ans-
o mac´ı ma ice sous a y. Poˇce ope ac´ı sou isej´ıc´ıch s ans o mac´ı p a ´e s any je o ˇ ´ad
niˇzˇs´ı a je edy zah nu do ˇclenu O(n2).
Zpˇe n´y chod GEM je ´ypoˇce nˇe pods a nˇe m´enˇe n´a oˇcn´y. ˇ
Reˇsen´ı sous a y o nic
s oj´uheln´ıko ou ma ic´ı yˇzaduje 1
2n2+O(n) ope ac´ı n´asobic´ıch a 1
2n2+O(n) ope ac´ı
sˇc´ı ac´ıch. Pˇ i om O(n) ep ezen uje poˇce ope ac´ı ˇ ´adu n( a u α1n+α0, kde α1,α0jsou
ˇc´ısla nez´a isl´a na n). GEM zpˇe n´y chod, j. ´ypoˇce xze sous a y (2.4), p o o yˇzaduje
1
2n2+O(n) ope ac´ı a LU zpˇe n´y chod, j. ´ypoˇce yaxze sous a (2.9), yˇzaduje
d ojn´asobn´y poˇce ope ac´ı, j. n2+O(n).
P o elk´y poˇce o nic, j. p o elk´e n, p o o m˚uˇzeme di , ˇze eliminace yˇzaduje
pˇ ibliˇznˇe 1
3n3ope ac´ı a GEM esp. LU zpˇe n´y chod pˇ ibliˇznˇe 1
2n2 esp. n2ope ac´ı (n´asobi-
c´ıch a s ejnˇe ak sˇc´ı ac´ıch).
Cholesk´eho ozklad. Pozi i nˇe de ini n´ı ma ici Alze yj´adˇ i e a u
A=LLT,(2.12)
kde Lje doln´ı oj´uheln´ıko ´a ma ice, jej´ıˇz nenulo ´e p ky jsou pos upnˇe p o k= 1,2,...,n
u ˇceny pˇ edpisem
ℓkk =
u
u
akk −
k−1
X
j=1
ℓ2
kj ,(2.13)
ℓik =1
ℓkk aik −
k−1
X
j=1
ℓijℓkj!, i =k+ 1, k + 2,...,n.
Sous a u o nic ˇ eˇs´ıme podle (2.9) p o U=LT. Vyj´adˇ en´ı ma ice A e a u (2.12)
se naz´y ´a Cholesk´eho ozklad ma ice A. Cholesk´eho ozklad yˇzaduje pˇ ibliˇznˇe polo iˇcn´ı
´ypoˇc o ´e n´aklady op o i obecn´emu LU ozkladu, edy pˇ ibliˇznˇe 1
6n3ope ac´ı n´asobic´ıch
a zh uba s ejn´y poˇce ope ac´ı sˇc´ı ac´ıch ( ´ypoˇce odmocnin nem´a na celko ´y poˇce ope ac´ı
pods a n´y li ). Cholesk´eho algo i mus (2.13) lze pouˇz´ı k e ek i n´ımu posouzen´ı pozi i n´ı
de ini nos i ma ice A: je-li Asyme ick´a a pla ´ı-li akk −Pk−1
j=1 ℓ2
kj >0 p o k= 1,2,...,n,
pak Aje pozi i nˇe de ini n´ı. V MATLABu lze p o Cholesk´eho ozklad pouˇz´ı unkci chol.
20
2.1.2. V´ybˇe hla n´ıho p ku
Zaˇcneme pˇ ´ıkladem.
Pˇ ´ıklad 2.1. M´ame yˇ eˇsi sous a u o nic


10 −7 0
−3 2,099 6
5−1,1 4,8


x1
x2
x3
=

7
3,901
5,9

na hypo e ick´em poˇc´ı aˇci, k e ´y p acuje dekadick´e sous a ˇe s pˇe im´ıs nou man isou.
Pˇ esn´e ˇ eˇsen´ı je
x=

0
−1
1
.
V p n´ım k oku eliminujeme poddiagon´aln´ı p ky p n´ım sloupci a dos aneme


10 −7 0
0−0,001 6
0 2,4 4,8


x1
x2
x3
=

7
6,001
2,4
.
P ek pozici (2,2) je e s o n´an´ı s os a n´ımi p ky ma ice mal´y. Pˇ es o pok aˇcujme
eliminaci. V dalˇs´ım k oku je ˇ eba ke ˇ e ´ımu ˇ ´adku pˇ iˇc´ıs ˇ ´adek d uh´y n´asoben´y 2400:
(4,8 + 6 ·2400) ·x3= 2,4 + 6,001 ·2400 .
Na le ´e s anˇe je koe icien 4,8+6·2400 = 14404,8 zaok ouhlen na 14405. Na p a ´e s anˇe
´ysledek n´asoben´ı 6,001 ·2400 = 14402,4 nelze zob azi pˇ esnˇe, mus´ı b´y zaok ouhlen na
14402. K omu se pak pˇ iˇc e 2,4 a zno u dojde k zaok ouhlen´ı. Posledn´ı o nice ak nabude
a u
14405 x3= 14404 .
Zpˇe n´y chod zaˇcne ´ypoˇc em
x3=14404
14 405
.
= 0,99993 .
Pˇ esn´y ´ysledek je x3= 1. Zd´a se, ˇze chyba nen´ı nijak ´aˇzn´a. Bohuˇzel, x2je ˇ eba u ˇci
z o nice
−0,001 x2+ 6 ·0,99993 = 6,001,
coˇz d´a ´a, po zaok ouhlen´ı 6 ·0,99993 .
= 5,9996,
x2=0,0014
−0,001 =−1,4.
Nakonec ypoˇc eme x1z p n´ı o nice
10x1−7·(−1,4) = 7
21

a dos aneme x1=−0,28. M´ıs o pˇ esn´eho ˇ eˇsen´ı xjsme dos ali pˇ ibliˇzn´e ˇ eˇsen´ı
˜
x=
−0,28
−1,4
0,99993
.
Kde znikl p obl´em? Nedoˇslo k ˇz´adn´emu h omadˇen´ı chyb zp˚usoben´emu p o ´adˇen´ım
is´ıc˚u ope ac´ı. Ma ice sous a y nen´ı bl´ızk´a ma ici singul´a n´ı. Po ´ıˇz je jinde, p˚usob´ı ji mal´y
pi o e d uh´em k oku eliminace. T´ım znikne mul iplik´a o −2400 a d˚usledku oho
m´a posledn´ı o nice koe icien y zh uba 1000 k ´a ˇe ˇs´ı neˇz koe icien y p˚u odn´ı o nice.
Zaok ouhlo ac´ı chyby, k e ´e jsou mal´e zhledem k ˇem o elk´ym koe icien ˚um, jsou nepˇ i-
ja eln´e p o koe icien y p˚u odn´ı ma ice a ak´e p o samo n´e ˇ eˇsen´ı.
Snadno se p o ˇeˇ ´ı, ˇze kdyˇz d uhou a ˇ e ´ı o nici p ohod´ıme, ne zniknou ˇz´adn´e elk´e
mul iplik´a o y a ´ysledek je zcela pˇ esn´y. Ukazuje se, ˇze o pla ´ı obecnˇe: jes liˇze jsou
absolu n´ı hodno y mul iplik´a o ˚u menˇs´ı nebo nej ´yˇse o ny 1, pak je nume icky spoˇc en´e
ˇ eˇsen´ı yho uj´ıc´ı. 
ˇ
C´as eˇcn´y ´ybˇe hla n´ıho p ku je modi ikace GEM zajiˇs
’uj´ıc´ı, aby absolu n´ı hodno a
mul iplik´a o ˚u byla menˇs´ı nebo o na jedn´e. V k- ´em k oku eliminace se jako pi o yb´ı ´a
p ek s nej ˇe ˇs´ı absolu n´ı hodno ou za ´ım neelimino an´e ˇc´as i k- ´eho sloupce ma ice
A(k−1), j. mezi p ky a(k−1)
ik p o i≥k. Nech
’ edy je ako ´y ˇ ´adko ´y index, p o k e ´y
|a(k−1)
k |= max
k≤i≤n|a(k−1)
ik |.(2.14)
Pak p ohod´ıme k- ou a - ou o nici. Ze sous a y o nic A(k−1)x=b(k−1) ak dos ane-
me sous a u A(k)x=b(k), pˇ iˇcemˇz A(k)z´ısk´ame p ohozen´ım k- ´eho a - ´eho ˇ ´adku ma ice
A(k−1) a podobnˇe b(k)z´ısk´ame p ohozen´ım k- ´eho a - ´eho p ku ek o u b(k−1). Pod-
diagon´aln´ı p ky k- ´em sloupci ma ice A(k)eliminujeme s ejnˇe jako algo i mu GEMz.
ˇ
Reˇsen´ı sous a y line´a n´ıch o nic s ˇc´as eˇcn´ym ´ybˇe em hla n´ıch p k˚u MATLABu
dos aneme pomoc´ı pˇ ´ıkazu x=A b.

















a(k−1)
11 a(k−1)
12 ··· a(k−1)
1k
··· a(k−1)
1n
0a(k−1)
22 ··· a(k−1)
2k
··· a(k−1)
2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· a(k−1)
kk
··· a(k−1)
kn
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· a(k−1)
k
··· a(k−1)
n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· a(k−1)
nk
··· a(k−1)
nn


































x1
x2
.
.
.
xk
.
.
.
x
.
.
.
xn

















=

















b(k−1)
1
b(k−1)
2.
.
.
b(k−1)
k
.
.
.
b(k−1)
.
.
.
b(k−1)
n

















Ob . 2.1: GEM s ˇc´as eˇcn´ym ´ybˇe em hla n´ıho p ku ( k ouˇzku)
´
Upln´y ´ybˇe hla n´ıho p ku je pos up, k e ´y m˚uˇze absolu n´ı hodno y mul iplik´a o ˚u
zmenˇsi jeˇs ˇe ´y aznˇeji. Dociluje se oho ´ım, ˇze k- ´em k oku eliminace se jako pi o
yb´ı ´a p ek s nej ˇe ˇs´ı absolu n´ı hodno ou dosud neelimino an´e ˇc´as i ma ice A(k−1), j.
22
ˇ ´adc´ıch i≥ka sloupc´ıch j≥k. Nech
’ edy je ˇ ´adko ´y a ssloupco ´y index yb an´y
ak, ˇze
|a(k−1)
s |= max
k≤i,j≤n|a(k−1)
ij |.(2.15)
Pak p ohod´ıme k- ou a - ou o nici a k- ou a s- ou nezn´amou. Ze sous a y o nic























a(k−1)
11 a(k−1)
12 ··· a(k−1)
1k
··· a(k−1)
1 ···a(k−1)
1s···a(k−1)
1n
0a(k−1)
22 ··· a(k−1)
2k
··· a(k−1)
2 ···a(k−1)
2s···a(k−1)
2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· a(k−1)
kk
··· a(k−1)
k
···a(k−1)
ks
···a(k−1)
kn
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· a(k−1)
k
··· a(k−1)
···a(k−1)
s ···a(k−1)
n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· a(k−1)
sk
··· a(k−1)
s ···a(k−1)
ss ···a(k−1)
sn
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· a(k−1)
nk
··· a(k−1)
n ···a(k−1)
ns ···a(k−1)
nn














































x(k−1)
1
x(k−1)
2
.
.
.
x(k−1)
k
.
.
.
x(k−1)
.
.
.
x(k−1)
s
.
.
.
x(k−1)
n























=























b(k−1)
1
b(k−1)
2.
.
.
b(k−1)
k
.
.
.
b(k−1)
.
.
.
b(k−1)
s
.
.
.
b(k−1)
n























Ob . 2.2: GEM s ´upln´ym ´ybˇe em hla n´ıho p ku ( k ouˇzku)
A(k−1)x(k−1) =b(k−1) dos aneme sous a u A(k)x(k)=b(k), pˇ iˇcemˇz A(k)z´ısk´ame p o-
hozen´ım k- ´eho a - ´eho ˇ ´adku a k- ´eho a s- ´eho sloupce ma ice A(k−1),b(k)z´ısk´ame
p ohozen´ım k- ´eho a - ´eho p ku ek o u b(k−1) ax(k)z´ısk´ame p ohozen´ım k- ´eho
as- ´eho p ku ek o u x(k−1). Pˇ i om x(0) =xje p˚u odn´ı ek o nezn´am´ych. P oha-
zo ´an´ı p omˇenn´ych egis ujeme e ek o u p= (p1, p2,...,pn)T. Na poˇc´a ku poloˇz´ıme
pi=ia pˇ i kaˇzd´em p ohozen´ı p omˇenn´ych p ohod´ıme ak´e odpo ´ıdaj´ıc´ı p ky ek o u p.
Po ukonˇcen´ı pˇ ´ım´eho chodu je i- ´a sloˇzka ek o u x(n−1) o na pi- ´e sloˇzce p˚u odn´ıho
ek o u x. Ve zpˇe n´em chodu ypoˇc eme x(n−1) a pomoc´ı ek o u pu ˇc´ıme x.
ˇ
C´as eˇcn´y nebo ´upln´y ´ybˇe hla n´ıho p ku? Vˇe ˇsinou se pouˇz´ı ´a jen ˇc´as eˇcn´y
´ybˇe hla n´ıho p ku. P axe i eo ie po zuje, ˇze i ˇc´as eˇcn´y ´ybˇe hla n´ıch p k˚u s aˇc´ı
k omu, aby zaok ouhlo ac´ı chyby z˚us aly dos a eˇcnˇe mal´e a neznehodno ily ´ysledn´e
ˇ eˇsen´ı. Dalˇs´ım d˚u odem, p oˇc ˇc´as eˇcn´emu ´ybˇe u hla n´ıch p k˚u d´a ´ame pˇ ednos , je o,
ˇze jeho ealizace yˇzaduje ´y aznˇe menˇs´ı poˇce ope ac´ı neˇz ´ybˇe ´upln´y.
LU ozklad s ˇc´as eˇcn´ym ´ybˇe em hla n´ıho p ku je s anda dn´ı u ina dos upn´a
kaˇzd´e kniho nˇe p og am˚u p o nume ick´e ˇ eˇsen´ı ´uloh line´a n´ı algeb y ( MATLABu iz
unkce lu). Vs upn´ım pa ame em je ma ice A. V´ys upn´ı pa ame y jsou ˇ i: doln´ı oj-
´uheln´ıko ´a ma ice L(s jedniˇckami na hla n´ı diagon´ale), ho n´ı oj´uheln´ıko ´a ma ice U
a z . pe mu aˇcn´ı ma ice P, pˇ iˇcemˇz
LU =PA .(2.16)
Pˇ i om pe mu aˇcn´ı ma ice je ako ´a ma ice, k e ´a znikne z jedno ko ´e ma ice nˇejak´ym
p oh´azen´ım jej´ıch ˇ ´adk˚u. N´asleduje popis algo i mu p o LU ozklad ma ice As ˇc´as eˇcn´ym
´ybˇe em hla n´ıch p k˚u.
23
Algo i mus LUp (s ˇc´as eˇcn´ym ´ybˇe em hla n´ıho p ku)
1) Poloˇz´ıme A(0) =A,P(0) =I.
2) Pos upnˇe p o k= 1,2,...,n−1 p o ´ad´ıme
2a) U ˇc´ıme index pi o n´ıho ˇ ´adku, iz (2.14).
2b) P ohod´ıme ˇ ´adky ka ma ici A(k−1) a ak o z´ıskanou ma ici oznaˇc´ıme jako
A(k). P ohod´ıme o nˇeˇz ˇ ´adky ka ma ici P(k−1) a ak o z´ıskanou ma ici
oznaˇc´ıme jako P(k).
2c) Up a ´ıme ma ici A(k) ak, ˇze eliminujeme poddiagon´aln´ı p ky k- ´em sloupci,
j. pos upnˇe p o i=k+ 1, k + 2,...,n poˇc´ı ´ame
mik := a(k)
ik /a(k)
kk ,
a(k)
ij := a(k)
ij −mika(k)
kj p o j=k+ 1, k + 2,...,n,
a(k)
ik := mik .
Do anulo an´ych pozic (i, k) ma ice A(k) edy ukl´ad´ame mul iplik´a o y mik.
3) Doln´ı oj´uheln´ıko ou ma ici Lses oj´ıme ak, ˇze do hla n´ı diagon´aly d´ame jedniˇcky
a poddiagon´aln´ı p ky pˇ e ezmeme z ´ysledn´e ma ice A(n−1). Ho n´ı oj´uheln´ıko ou
ma ici Udos aneme z diagon´aln´ıch a naddiagon´aln´ıch p k˚u ´ysledn´e ma ice A(n−1).
Pe mu aˇcn´ı ma ice Pje o na ´ysledn´e pe mu aˇcn´ı ma ici P(n−1).
Po z´ısk´an´ı ma ic L,UaP yˇ eˇs´ıme uˇz sous a u o nic Ax =bsnadno. Zˇ ejmˇe
PAx =Pb =⇒LUx =Pb .
P o o nejdˇ ´ı e u ˇc´ıme ek o z=Pb, j. p ky ek o u bp a ´e s any p oh´az´ıme s ejnˇe,
jako jsme p ohazo ali ˇ ´adky ma ic A(k−1) aP(k−1) algo i mu LUp. Oznaˇc´ıme-li Ux =y,
id´ıme, ˇze yje ˇ eˇsen´ı sous a y Ly =z. Vyˇ eˇsen´ım ´e o sous a y dos aneme y. Zb´y ´a
jeˇs ˇe yˇ eˇsi sous a u Ux =ya ˇ eˇsen´ı xje nalezeno. Sh neme-li o, poˇc´ı ´ame pos upnˇe
z,yaxz o nic
z=Pb ,Ly =z,Ux =y.(2.17)
Ucho ´a a his o ii p ohazo ´an´ı ˇ ´adk˚u ma ici Pje zˇ ejm´e pl´y ´an´ı pamˇe
’o ´ym
m´ıs em, ˇzdy
’z celko ´eho poˇc u n2p k˚u ma ice Pje jich pouze nnenulo ´ych. P o o
m´ıs o s ma ic´ı Ps aˇc´ı p aco a jen s ek o em ˇ ´adko ´ych pe mu ac´ı p.
Na zaˇc´a ku poloˇz´ıme p(0) = (1,2,...,n)Ta e zby ku algo i mu pak p ohazujeme
p ky ek o u p(k−1). Ma ice Pbyla zapo ˇ eb´ı jen p o ses a en´ı ek o u z. To ale dok´aˇzeme
s pomoc´ı ek o u p ak´e: do i- ´e sloˇzky ek o u z loˇz´ıme pi- ou sloˇzku ek o u b, po-
s upnˇe p o i= 1,2,...,n.
Pˇ ´ıklad 2.2. P o edeme LU ozklad ma ice
A=



−0,4−0,95 −0,4−7,34
0,5−0,3 2,15 −2,45
−2 4 1 −3
−1 5,5 2,5 3,5



.
24
V p n´ım sloupci najdeme jako pi o a ˇc´ıslo −2 e ˇ e ´ım ˇ ´adku. P o o p ohod´ıme p n´ı
a ˇ e ´ı ˇ ´adek. Pak eliminujeme poddiagon´aln´ı p ky p n´ım sloupci a na jejich m´ıs a
zap´ıˇseme pouˇzi ´e mul iplik´a o y. P ohozen´ı ˇ ´adk˚u yznaˇc´ıme ak´e pe mu aˇcn´ım ek o u.
Tak dos aneme
A(1) =



−2 4 1 −3
−0,25 0,7 2,4−3,2
0,2−1,75 −0,6−6,74
0,5 3,5 2 5



,p(1) =



3
2
1
4




P n´ı ˇ ´adek se uˇz mˇeni nebude. Ve d uh´em k oku najdeme pi o a e d uh´em sloupci. Je
o ˇc´ıslo 3,5 e ˇc ´em ˇ ´adku. P o o p ohod´ıme d uh´y a ˇc ´y ˇ ´adek jak ma ici A(1) ak
e ek o u p(1). Pak eliminujeme p ky pozic´ıch (3,2) a (4,2) a na jejich m´ıs a zap´ıˇseme
pouˇzi ´e mul iplik´a o y. V´ysledkem je
A(2) =



−2 4 1 −3
0,5 3,5 2 5
0,2−0,5 0,4−4,24
−0,25 0,2 2 −4,2



,p(2) =



3
4
1
2



.
P n´ı d a ˇ ´adky uˇz z˚us anou bez zmˇeny. Pi o e ˇ e ´ım sloupci je ˇc´ıslo 2 e ˇc ´em ˇ ´adku.
P ohod´ıme edy ˇ e ´ı a ˇc ´y ˇ ´adek ma ici A(2) i e ek o u p(2). Pak eliminujeme p ek
pozici (4,3) a na jeho m´ıs o loˇz´ıme pouˇzi ´y mul iplik´a o . Tak dos aneme
A(3) =



−2 4 1 −3
0,5 3,5 2 5
−0,25 0,2 2 −4,2
0,2−0,5 0,2−3,4



,p(3) =



3
4
2
1



.
Dos ali jsme edy
L=



1 0 0 0
0,5 1 0 0
−0,25 0,2 1 0
0,2−0,5 0,2 1



,U=



−2 4 1 −3
0 3,5 2 5
0 0 2 −4,2
0 0 0 −3,4



.
Pe mu aˇcn´ı ek o p=p(3). Pokud bychom ch ˇeli y oˇ i pe mu aˇcn´ı ma ici P, s aˇc´ı
z´ı jedno ko ou ma ici a pˇ euspoˇ ´ada ji ak, ˇze p˚u odnˇe pi- ´y ˇ ´adek se s ane ˇ ´adkem
i- ´ym. Kdyˇz o p o edeme, dos aneme p o pe mu aˇcn´ı ek o
p=



3
4
2
1



pe mu aˇcn´ı ma ici P=



0010
0001
0100
1000



.
Snadno se o ˇeˇ ´ı, ˇze LU =PA.
Ukaˇzme si jeˇs ˇe ˇ eˇsen´ı sous a y o nic p o olenou p a ou s anu. Z olme ˇ eba
b=



−13,14
2,15
9
27,5



,pak z=



9
27,5
2,15
−13,14



,
25
Symbolem Ojsme si pˇ i om oznaˇcili nulo ou ma ici, j. ma ici, jej´ıˇz ˇsechny p ky jsou
o ny nule. Poznamenejme, ˇze obecnˇe je no ma ˇc e co ´e ma ice de ino ´ana jako e´aln´a
unkce splˇnuj´ıc´ı jen p n´ı ˇc yˇ i z ´yˇse u eden´ych podm´ınek.
Pˇ ´ıklad 2.4. Sous a a o nic Ax =b, kde
A=1 10
10 101,b=11
111,m´a ˇ eˇsen´ı x=1
1.
Pouˇzijeme l∞-no mu a spoˇc eme kbk∞= 111, kxk∞= 1 . Kdyˇz p a ou s anu zmˇen´ıme
na
˜
b=11,11
110,89,dos aneme ˇ eˇsen´ı ˜
x=13,21
−0,21.
Oznaˇc´ıme-li ∆b=˜
b−b, ∆x=˜
x−x, pak k∆bk∞= 0,11 a k∆xk∞= 12,21. Vid´ıme, ˇze
pomˇe nˇe mal´a zmˇena p a ´e s any zcela zmˇenila ˇ eˇsen´ı. Rela i n´ı zmˇeny jsou
k∆bk∞
kbk∞
= 9,909 ·10−4,k∆xk∞
kxk∞
= 12,21 .
Podle (2.21) m˚uˇzeme odhadnou ˇc´ıslo podm´ınˇenos i
κ(A)≥12,21
9,909 ·10−4= 12321.
Ve sku eˇcnos i je ba ∆bz oleno ak, ˇze κ(A) = 12321. To se snadno o ˇeˇ ´ı, nebo
’
A−1=101 −10
−10 1, akˇze kA−1k∞= 111 = kAk∞aκ(A) = 1112= 12321.
Ukaˇzme si jeˇs ˇe, ˇze z ah (2.21) pla ´ı jako o nos :
k˜
x−xk∞
kxk∞
=12,21
1= 11120,11
111 =κ(A)k∆bk∞
kbk∞
= 111 ·k∆bk∞= 111 ·k k∞,
kde =b−A˜
xje eziduum. 
K u ˇcen´ı κ(A) po ˇ ebujeme zn´a kA−1k. A ˇsak ´ypoˇce A−1 yˇzaduje pˇ ibliˇznˇe ˇ ik ´a
olik p ´ace jako cel´e ˇ eˇsen´ı sous a y o nic. Naˇs ˇes ´ı pˇ esnou hodno u κ(A) ob ykle
nepo ˇ ebujeme, ys aˇc´ıme s dos a eˇcnˇe dob ´ym odhadem κ(A). Spolehli ´e a pomˇe nˇe
elmi ychl´e odhady ˇc´ısla podm´ınˇenos i ma ic pa ˇ ´ı souˇcasn´e dobˇe ke s anda dn´ımu
yba en´ı p og am˚u p o ˇ eˇsen´ı sous a line´a n´ıch o nic. Jes liˇze p og am zjis ´ı, ˇze ˇc´ıslo
podm´ınˇenos i je pˇ ´ıliˇs elk´e, yd´a a o ´an´ı nebo dokonce ´ypoˇce pˇ e uˇs´ı.
Sh nu ´ı. Sous a a line´a n´ıch o nic je dobˇ e (ˇspa nˇe) podm´ınˇen´a, p ´a ˇe kdyˇz je ma ice
sous a y dobˇ e (ˇspa nˇe) podm´ınˇen´a. Podm´ınˇenos ma ice sous a y Amˇeˇ ´ıme pomoc´ı ˇc´ısla
podm´ınˇenos i κ(A)≥1. Je-li ˇc´ıslo κ(A) mal´e, je ma ice Adobˇ e podm´ınˇen´a. V opaˇcn´em
pˇ ´ıpadˇe, j. kdyˇz κ(A)≫1, je ma ice Aˇspa nˇe podm´ınˇen´a. ˇ
Spa nˇe podm´ınˇenou sous a u
o nic lze ob ykle jen elmi ob ´ıˇznˇe ˇ eˇsi . Pomoci m˚uˇze ´ypoˇce s ´ıcem´ıs nou man isou
32

(je hodn´e pouˇz´ı d ojn´asobnou nebo jeˇs ˇe ˇe ˇs´ı pˇ esnos ). Exis uj´ı ˇsak ´yjimky: je-li
napˇ ´ıklad Adiagon´aln´ı ma ice, e k e ´e aii = 10i, pak je κ(A) = 10n−1, coˇz je p o elk´e
n elk´e ˇc´ıslo, a pˇ es o ˇ eˇsen´ı xi= 10−ibiz´ısk´ame bez p obl´em˚u p o libo olnˇe elk´y poˇce
o nic.
Pˇ edpokl´adejme, ˇze ma ice sous a y je dobˇ e podm´ınˇen´a. Pak je GEM s ˇc´as eˇcn´ym
(nebo ´upln´ym) ´ybˇe em hla n´ıho p ku dobˇ e podm´ınˇen´y algo i mus: p o oˇze elikos
mul iplik´a o ˚u nepˇ esahuje jedniˇcku, znikaj´ıc´ı zaok ouhlo ac´ı chyby se dalˇs´ım ´ypoˇc-
em nezesiluj´ı. Kdyˇz naopak ´ybˇe hla n´ıch p k˚u nep o ´ad´ıme, m˚uˇzeme dos a mul i-
plik´a o y, jejichˇz absolu n´ı hodno a je ˇe ˇs´ı neˇz jedna, coˇz m´a za n´asledek z ˇe ˇso ´an´ı
dˇ ´ı e znikl´ych zaok ouhlo ac´ıch chyb. GEM bez ´ybˇe u hla n´ıch p k˚u je edy obecnˇe
ˇspa nˇe podm´ınˇen´y algo i mus. V´yjimku z oho o p a idla pˇ eds a uje ˇ eˇsen´ı sous a se
speci´aln´ı ma ic´ı sous a y, napˇ . kdyˇz je ma ice sous a y os ˇ e diagon´alnˇe dominan n´ı nebo
pozi i nˇe de ini n´ı, pak je i GEM bez ´ybˇe u hla n´ıch p k˚u dobˇ e podm´ınˇen´y algo i mus.
2.2. I e aˇcn´ı me ody
Mnoho p ak ick´ych p obl´em˚u yˇzaduje ˇ eˇsen´ı ozs´ahl´ych sous a line´a n´ıch o nic
Ax =b, nichˇz ma ice Aje naˇs ˇes ´ı ˇ ´ıdk´a, j. m´a ela i nˇe m´alo nenulo ´ych p k˚u. S an-
da dn´ı eliminaˇcn´ı me ody s udo an´e pˇ edchoz´ı kapi ole 2.1 nejsou p o ˇ eˇsen´ı ako ´ych
sous a hodn´e, nebo
’ p ˚ubˇehu eliminace doch´az´ı pos upnˇe k zaplˇno ´an´ı p˚u odnˇe ne-
nulo ´ych pozic ma ici sous a y, coˇz ede k elk´ym n´a ok˚um na poˇce a i me ick´ych
ope ac´ı a klade ak´e ysok´e n´a oky na pamˇe
’poˇc´ı aˇce.
To je d˚u od, p oˇc se p o ˇ eˇsen´ı ako ´ych sous a pouˇz´ı aj´ı i e aˇcn´ı me ody. Z ol´ı se
poˇc´a eˇcn´ı ek o x0a gene uje se posloupnos ek o ˚u x0→x1→x2..., k e ´a kon e guje
k hledan´emu ˇ eˇsen´ı x. Spoleˇcn´ym ysem ˇsech i e aˇcn´ıch me od je ak , ˇze kaˇzd´y jedno li ´y
i e aˇcn´ı k ok xk→xk+1 yˇzaduje objem ´ypoˇc ˚u s o na eln´y s n´asoben´ım ma ice A
ek o em, coˇz je p o ˇ ´ıdk´e ma ice objem ne elk´y (pokud je kaˇzd´em ˇ ´adku ma ice A
ˇ ´adu nnej ´yˇse mnenulo ´ych p k˚u, jde o nm ope ac´ı n´asoben´ı a sˇc´ı ´an´ı). Pˇ ija eln´y
objem ´ypoˇc ˚u lze p o o dos´ahnou i p o pomˇe nˇe elk´y poˇce i e ac´ı.
Na obhajobu pˇ ´ım´ych me od je ˇsak ˇ eba doda , ˇze p o sous a y s ˇ ´ıdk´ymi ma icemi
exis uj´ı ak´e elmi e ek i n´ı algo i my eliminaˇcn´ıho ypu. Pˇ es o, p o ex ´emnˇe ozs´ahl´e
sous a y o nic se speci´aln´ı s uk u ou ma ice sous a y jsou hodnˇe z olen´e i e aˇcn´ı me-
ody e ek i nˇejˇs´ı a jsou ˇcas o jedinou p ak icky ealizo a elnou me odou ˇ eˇsen´ı.
Kon e gence. Vˇe ˇsina klasick´ych i e aˇcn´ıch me od ych´az´ı z ozkladu ma ice sous a y
A=M−N,kde Mje egul´a n´ı ma ice. Pak je posloupnos xkde ino ´ana pˇ edpisem
Mxk+1 =Nxk+b,(2.26)
pˇ iˇcemˇz poˇc´a eˇcn´ı ap oximace x0je dan´a.
ˇ
Rekneme, ˇze i e aˇcn´ı me oda kon e guje, a p´ıˇseme xk→x, kdyˇz ˇc´ıseln´a posloupnos
kxk−xk → 0. Oznaˇcme ek=xk−xchybu k- ´e i e aci. P o oˇze Mx =Nx +b,
dos aneme
M(xk+1 −x) = N(xk−x) nebo-li ek+1 =M−1Nek.
33
Oznaˇc´ıme-li T=M−1N, pak pomoc´ı (2.24) dos ´a ´ame
kek+1k ≤ kTk·kekk ≤ kTk2·kek−1k ≤ ··· ≤ kTkk+1 ·ke0k.
Kon e gence i e aˇcn´ı me ody z libo oln´eho s a o ac´ıho ek o u p o o jis ˇe nas ane, kdyˇz
kTk<1,kde T=M−1Nje i e aˇcn´ı ma ice. (2.27)
Podm´ınka (2.27) se neo ˇeˇ uje snadno, a p o o si u konk ´e n´ıch me od u edeme jin´e
pos aˇcuj´ıc´ı podm´ınky kon e gence.
K i ´e ia p o ukonˇcen´ı i e ac´ı. Jde o o, jak ozhodnou , zda xk+1 je uˇz dos a eˇcnˇe
dob ´a ap oximace ˇ eˇsen´ı x.ˇ
Reˇsen´ı xnezn´ame, akˇze se bez nˇej mus´ıme obej´ı . Nab´ız´ı se
zkouma elikos zmˇeny xk+1 −xknebo elikos ezidua k+1 =b−Axk+1. Pos upuje
se ak, ˇze uˇzi a el zad´a mal´e kladn´e ˇc´ıslo εjako poˇzado anou pˇ esnos a kaˇzd´em k oku
me ody se es uje, zda je uˇz splnˇena napˇ . jedna z n´asleduj´ıc´ıch podm´ınek
1. kxk+1 −xkk ≤ εkxkk,
2. k k+1k ≤ ε(kAk·kxk+1k+kbk) ,
3. k k+1k ≤ εk 0k.
Je-li podm´ınka na ukonˇcen´ı i e ac´ı splnˇena, ´ypoˇce pˇ e uˇs´ıme a xk+1 po aˇzujeme za
pˇ ibliˇznou hodno u ˇ eˇsen´ı x.
Jacobio a me oda. Pˇ edpokl´adejme, ˇze A=L+D+U, kde Dje diagon´aln´ı ma ice,
k e ´a m´a s ejnou diagon´alu jako A, a kde L esp. Uje yze doln´ı esp. ho n´ı oj´uheln´ıko ´a
ˇc´as A, j.
D=




a11 0··· 0
0a22 0
.
.
.....
.
.
0 0 ··· ann




,
L=




0··· ··· 0
a21 0 0
.
.
........
.
.
an1··· an,n−10




,U=




0a12 ··· a1n
.
.
........
.
.
0 0 an−1,n
0··· ··· 0




.
Nejjednoduˇsˇs´ı ozklad Ados aneme p o M=DaN=−(L+U). Me oda (2.27) je pak
a u
Dxk+1 =b−(L+U)xk(2.28)
a je zn´ama jako Jacobio a me oda. Sous a a (2.28) s diagon´aln´ı ma ic´ı se ˇ eˇs´ı snadno.
Zap´ıˇseme-li (2.28) po sloˇzk´ach (sloˇzky ek o u xkjsou znaˇceny x(k)
i, podobnˇe p o xk+1),
dos aneme
x(k+1)
i=1
aii bi−
n
X
j= 1
j6=i
aij x(k)
j!, i = 1,2,...,n.
34
Anal´yzou las nos ´ı i e aˇcn´ı ma ice T=−D−1(L+U) lze dok´aza , ˇze
Jacobio a me oda kon e guje, kdyˇz Aje yze diagon´alnˇe dominan n´ı.
Gausso a-Seidelo a me oda. Vˇsimnˇe e si, ˇze Jacobio a me oda pouˇz´ı ´a xkk ´ypoˇc u
ˇsech sloˇzek xk+1. P o oˇze (alespoˇn na s´e io ´ych poˇc´ı aˇc´ıch) p ky ek o u xk+1 poˇc´ı ´ame
pos upnˇe jeden za d uh´ym, znikl pˇ i ozen´y n´apad yuˇz´ı ihned y sloˇzky xk+1, k e ´e jsou
uˇz k dispozici. Tak dos ´a ´ame Gausso u-Seidelo u me odu:
x(k+1)
i=1
aii bi−
i−1
X
j=1
aij x(k+1)
j−
n
X
j=i+1
aij x(k)
j!, i = 1,2,...,n.
Vyj´adˇ ´ıme-li u o me odu ma ico ´em a u, m´ame
(D+L)xk+1 =b−Uxk.
Je dok´az´ano, ˇze
Gausso a-Seidelo a me oda kon e guje, kdyˇz Aje yze diagon´alnˇe dominan n´ı nebo pozi-
i nˇe de ini n´ı.
Pozn´amky. N´asleduje nˇekolik pozna k˚u o z´ajemn´em z ahu Jacobio y a Gausso y-
Seidelo y me ody.
1. Kon e gence Gausso y-Seidelo y me ody je p o mnoh´e ma ice A ychlejˇs´ı neˇz kon-
e gence Jacobio y me ody. Tak je omu ˇ eba pˇ ´ıpadˇe, kdyˇz Aje yze diagon´alnˇe
dominan n´ı.
2. Exis uj´ı ma ice, p o k e ´e Gausso a-Seidelo a me oda kon e guje a Jacobio a me-
oda nekon e guje a naopak, p o k e ´e kon e guje Jacobio a me oda a Gausso a-
Seidelo a me oda nekon e guje.
3. Jacobio a me oda umoˇzˇnuje pa aleln´ı ´ypoˇce ( ˇsechny sloˇzky x(k+1)
imohou b´y
poˇc´ı ´any souˇcasnˇe, kaˇzd´a na jin´em p oceso u), za ´ımco Gausso a-Seidelo a me oda
je ze s ´e pods a y sek enˇcn´ı (x(k+1)
ilze ypoˇc´ı a aˇz po ´e, co byly spoˇc eny ˇsechny
sloˇzky x(k+1)
jp o j < i). P o speci´aln´ı ypy ma ic Ajsou ˇsak yp aco ´any pos upy
umoˇzˇnuj´ıc´ı pa alelizo a i Gausso u-Seidelo u me odu.
Relaxaˇcn´ı me ody. Bezp os ˇ ednˇe po ´e, co jsme z´akladn´ı me odou (Jacobio ou nebo
Gausso ou-Seidelo ou) spoˇce li i- ou sloˇzku x(k+1)
i, p o edeme jej´ı modi ikaci
x(k+1)
i:= (1 −ω)x(k)
i+ωx(k+1)
i,
kde ω > 0 je z . elaxaˇcn´ı pa ame . Vol´ıme ho ak, abychom ylepˇsili kon e genci
z´akladn´ı me ody. P o ω= 1 dos ´a ´ame p˚u odn´ı me odu. Z ol´ıme-li ω < 1, ho oˇ ´ıme
odoln´ı elaxaci, pˇ ´ıpadˇe ω > 1 jde o ho n´ı elaxaci. E ek i n´ı olba elaxaˇcn´ıho pa a-
me u ωz´a is´ı na z olen´e z´akladn´ı me odˇe a na ma ici sous a y A.
P ak ick´e zkuˇsenos i po zuj´ı, ˇze doln´ı elaxace m˚uˇze zajis i kon e genci pˇ ´ıpadˇe,
kdyˇz z´akladn´ı me oda nekon e guje. Vhodnou olbou elaxaˇcn´ıho pa ame u lze ychlos
35
kon e gence p˚u odn´ı me ody pods a nˇe z ychli . P o z olenou me odu a speci´aln´ı a
ma ice Ajsou zn´amy zo ce p o op im´aln´ı hodno u ωop elaxaˇcn´ıho pa ame u. Ty o
zo ce ˇsak maj´ı ´yznam sp´ıˇse eo e ick´y, nebo
’ ´ypoˇce podle nich je pˇ ´ıliˇs n´a oˇcn´y.
P o o se p acuje s p omˇenn´ym elaxaˇcn´ım ak o em, k- ´e i e aci s ωk, a jeho hodno a
se kaˇzd´e i e aci zpˇ esˇnuje ak, aby se pos upnˇe bl´ıˇzila k op im´aln´ımu ωop . Konk ´e n´ı
me ody lze naj´ı e specializo an´e li e a uˇ e.
Relaxace Jacobio y me ody. D´a se uk´aza , ˇze kdyˇz kon e guje Jacobio a me oda, ak
kon e guje ak´e elaxo an´a Jacobio a me oda p o 0 < ω ≤1.
Relaxace Gausso y-Seidelo y me ody je li e a uˇ e zn´ama jako SOR me oda (podle
anglick´eho Successi e O e Relaxa ion). O kon e genci SOR me ody m´ame zejm´ena n´asleduj´ıc´ı
pozna ky:
1. Pokud SOR me oda kon e guje, pak je 0 < ω < 2.
2. SOR me oda kon e guje, kdyˇz Aje yze diagon´alnˇe dominan n´ı a 0 < ω ≤1.
3. SOR me oda kon e guje, kdyˇz Aje pozi i nˇe de ini n´ı a 0 < ω < 2.
SOR me oda zapsan´a po sloˇzk´ach je a u
x(k+1)
i=ω
aii bi−
i−1
X
j=1
aij x(k+1)
j−
n
X
j=i+1
aij x(k)
j!+ (1 −ω)x(k)
i, i = 1,2,...,n,
a SOR ma ico ˇe je
(ω−1D+L)xk+1 =b−((1 −ω−1)D+U)xk.
Kdyˇz e sloˇzko ´em z´apisu SOR me ody na p a ´e s anˇe m´ıs o x(k+1)
jp´ıˇseme x(k)
j, dos a-
neme elaxaci Jacobio y me ody oznaˇco anou jako JOR me oda, ma ico ˇe
ω−1Dxk+1 =b−(L+ (1 −ω−1)D+U)xk.
Pˇ ´ıklad 2.5. Velk´e ˇ ´ıdk´e ma ice znikaj´ı pˇ i nume ick´em ˇ eˇsen´ı pa ci´aln´ıch di e enci´aln´ıch
o nic. MATLAB m´a e s ´e gale ii pˇ ´ıklady ako ´ych ma ic. Pˇ ´ıkazem
K = galle y(’poisson’,n)
ygene ujeme ma ici, jej´ıˇz s uk u u nyn´ı pop´ıˇseme. 1
1Pa ci´aln´ı di e enci´aln´ı o nice jsou nezby n´e p o modelo ´an´ı echnick´ych p obl´em˚u. Pˇ i ˇ eˇsen´ı Di-
ichle o y ´ulohy p o Poissono u o nici na ˇc e ci Ω = (0, l)×(0, l),
−∂2u(x, y)
∂x2−∂2u(x, y)
∂y2= (x, y) Ω a u(x, y) = g(x, y) na h anici ∂Ω ,
( unkce agjsou dan´e, nezn´am´a je unkce u) me odou s´ı ´ı znik´a sous a a line´a n´ıch o nic s ma ic´ı
sous a y Ku aˇzo anou om o pˇ ´ıkladu 2.5.
36
Ma ice Kje bloko ˇe ˇ ´ıdiagon´aln´ı, p o de ˇe o nic ypad´a ak o














4−1 0 −1 0 0 0 0 0
−1 4 −1 0 −1 0 0 0 0
0−1 4 0 0 −1 0 0 0
−1 0 0 4 −1 0 −1 0 0
0−1 0 −1 4 −1 0 −1 0
0 0 −1 0 −1 4 0 0 −1
000−1 0 0 4 −1 0
0 0 0 0 −1 0 −1 4 −1
00000−1 0 −1 4














.
Obecnˇe je Ksloˇzena z ˇc e co ´ych subma ic ˇ ´adu n( z . blok˚u) B,−I,O, k e ´e jsou
e ˇc e co ´e ma ici ˇ ´adu n2 ozm´ıs ˇeny e ˇ ech diagon´al´ach
K=










B−I O ··· O O
−I B −I··· O O
O−I B ··· O O
.
.
..
.
..
.
.....
.
..
.
.
O O O ··· B−I
O O O ··· −I B










.
Ma ice Ije jedno ko ´a ma ice, Oje ˇc e co ´a ma ice s nulo ´ymi p ky a Bje ˇ ´ıdiagon´aln´ı
ma ice
B=









4−1 0 ··· 0 0
−1 4 −1··· 0 0
0−1 0 ··· 0 0
.
.
..
.
..
.
.....
.
..
.
.
0 0 0 ··· 4−1
0 0 0 ··· −1 4









.
Na ma ici Kse ˇcas o es uje ´uˇcinnos nume ick´ych me od p o ˇ eˇsen´ı sous a line´a n´ıch
o nic s ˇ ´ıdkou ma ic´ı. Na ob ´azku 2.3 je idˇe z´a islos poˇc u i e ac´ı (po ˇ ebn´ych p o
dosaˇzen´ı z olen´e pˇ esnos i) na poˇc u o nic n2. Pˇ i me odˇe SOR bylo z oleno op im´aln´ı ω.
Pozn´amka. I e aˇcn´ı me ody, se k e ´ymi jsme se sezn´amili, b´y aj´ı oznaˇco ´any jako kla-
sick´e i e aˇcn´ı me ody. V souˇcasnos i se pouˇz´ı aj´ı uˇz jen zˇ ´ıdka. Do uˇcebn´ıho ex u jsme
je zaˇ adili hla nˇe p o o, ˇze jsou pomˇe nˇe jednoduch´e a pˇ i om na nich lze dobˇ e uk´aza ,
jak i e aˇcn´ı me ody unguj´ı.
Na d uh´e s anˇe me ody, k e ´e se sku eˇcnˇe pouˇz´ı aj´ı, jsou pomˇe nˇe sloˇzi ´e k pocho-
pen´ı, akˇze je om o z´akladn´ım ku zu nelze dos dobˇ e ys ˇe li . Spokoj´ıme se edy
s kons a o ´an´ım, ˇze exis uje znaˇcn´e mnoˇzs ´ı ´ykonn´ych i e aˇcn´ıch me od, iz napˇ . [13].
Tak ˇ eba p o sous a y s pozi i nˇe de ini n´ı ma ic´ı pa ˇ ´ı mezi nejpopul´a nˇejˇs´ı me oda
sd uˇzen´ych g adien ˚u (s uˇcnˇe CG podle anglick´eho conjuga e g adien ), MATLABu
37

iz unkce pcg. Z´akladn´ı e ze ´e o me ody je s uˇcnˇe pops´ana kapi ole 6.2, iz ak´e
c iˇcen´ı 6.7. P o sous a y s nesyme ickou ma ic´ı je si uace kompliko anˇejˇs´ı, jednoznaˇcn´y
a o i mezi me odami p o jejich ˇ eˇsen´ı neexis uje. Jednou z mnoha pouˇz´ı an´ych me od
je zobecnˇen´a me oda minim´aln´ıch ezidu´ı (s uˇcnˇe GMRES podle anglick´eho gene alized
minimal esidual), MATLABu iz unkce gm es.
0 100 200 300 400 500 600 700
0
200
400
600
800
1000
1200
1400
1600
Ro nic
I e ací
Jacobi
Gauss−Seidel
Op imální SOR
Ob . 2.3: S o n´an´ı klasick´ych i e aˇcn´ıch me od
2.3. C iˇcen´ı
2.1. Me odou GEMz a GEM s ˇc´as eˇcn´ym ´ybˇe em hla n´ıho p ku (GEMpp) ˇ eˇs e o nice
a)
x+ 2y+ 3z= 6
2x+ 4y+ 5z= 11
7x+ 8y+ 9y= 24
b)10−15x+y= 1 + 10−15
x+ 1011y= 1 + 1011
[ a) GEMz selˇze, GEMpp najde ˇ eˇsen´ı (1 1 1)T; b) GEMz spoˇc e (0,888 1)T, GEMpp d´a ´a (1 1)T. ]
2.2. Od od’ e (p o n= 3) zo ce (2.13).
[LLT=

l11 0 0
l21 l22 0
l31 l32 l33



l11 l21 l31
0l22 l32
0 0 l33

=

l2
11 l11l21 l11l31
l21l11 l2
21 +l2
22 l21l31 +l22l32
l31l11 l31l21 +l32l22 l2
31 +l2
32 +l2
33

,
LLT=A⇒l11 =√a11, l21 =a21/l11, l31 =a31/l11, l22 =pa22 −l2
21, . . . ]
2.3. Pomoc´ı Cholesk´eho ozkladu ˇ eˇs e sous a y o nic Axi=bi,i= 1,2,3, kde
A=

2 1 2
1 2 2
2 2 3
,b1=

1
−1
0
,b2=

0
−1
−1
.
38
[L.
=

1,414214 0 0
0,707107 1,224745 0
1,414214 0,816497 0,577350
,x1=

1
−1
0
,x2=

1
0
−1
.]
2.4. ˇ
Reˇs e sous a y o nic Axi=bi,i= 1,2,3, kde
A=

1−1 1
2−1 1
1 1 2
,b1=
−1
0
0
,b2=

1
2
7
,b3= 2x2−x1.
[ P o ed’ e LU ozklad PA =LU, kde L=

1 0 0
0,5 1 0
0,5−0,33 1
,U=

2−1 1
0 1,5 1,5
0 0 1
,
P=

0 1 0
0 0 1
1 0 0
.Nejdˇ ´ı e z´ısk´ame x1,x2, ses a ´ıme b3a opˇe LU ozkladem spoˇc eme x3:
x1=

1
1
−1
,x2=

1
2
2
,b3=

1
3
5
,x3=

1
1,66
0,66
.]
2.5. Spoˇc ˇe e ˇc´ıslo podm´ınˇenos i ma ice sous a y Aze c iˇcen´ı 2.1 b).
[κ(A).
= 1022 no mˇe k·k∞. ]
2.6. Spoˇc ˇe e de e minan ma ice Aze c iˇcen´ı 2.4 pouˇzi ´ım LU ozkladu.
[|A|= (−1)2|U|= 2 ·1,5·1 = 3. ]
2.7. Spoˇc ˇe e in e zn´ı ma ici k ma ici Aze c iˇcen´ı 2.4.
[A−1=
−1 1 0
−1 0,33 0,33
1−0,66 0,33
. ]
2.8. Nap og amuj e me odu GEMz a up a e ji ak, aby bylo moˇzn´e oli elnˇe zapnou / ypnou ˇc´as eˇcn´y
´ybˇe hla n´ıho p ku (GEMpp).
2.9. Nap og amuj e ´ypoˇce ek o o ´ych a ma ico ´ych no em.
2.10. Nap og amuj e ˇ eˇsen´ı sous a s ˇ ´ıdiagon´aln´ı ma ic´ı. P ky ma ice d ˇz e pamˇe i poˇc´ı aˇce ´uspo -
n´em o m´a u napˇ . jako ˇ i ek o y (jedno ozmˇe n´a pole). Jak ypad´a ans o mo an´a ma ice e
A:= LU
a ma ice LaUz´ıskan´e LU ozkladem ma ice
A=



100 12 0 0
21 100 23 0
0 32 100 34
0 0 43 100



?
[e
A.
=



100 12 0 0
0,21 97,48 23 0
0 0,3283 92,4497 34
0 0 0,4651 84,186



,
L.
=



1 0 0 0
0,21 1 0 0
0 0,3283 1 0
0 0 0,4651 1



,U.
=



100 12 0 0
0 97,48 23 0
0 0 92,4497 34
0 0 0 84,186



. ]
39
2.11. Nap og amuj e (a) Jacobio u a (b) Gauss-Seidelo u i e aˇcn´ı me odu. Jak ypad´a ek o x5p o
sous a u o nic 
−194
−4−4 15
33 −3−1


x1
x2
x3
=

29
33
24
,
kdyˇz nejdˇ ´ı e o nice sous a y hodnˇe pˇ e o n´a e ( ak, aby ma ice sous a y byla yze diagon´alnˇe domi-
nan n´ı) a kdyˇz jako poˇc´a eˇcn´ı ap oximaci z ol´ı e ek o x0= (0,0,0)T?
[ (a) x5.
= (0,995405; 2,007110; 2,986472)T, (b) x5.
= (1,000144; 1,999887; 3,000008)T. ]
2.12. O ˇeˇ e, ˇze p o sous a u o nic


1 1 1
1 2 2
1 2 3


x1
x2
x3
=

3
5
6

pla ´ı: (a) ma ici sous a y nelze ˇz´adn´ym pˇ e o n´an´ım ˇ ´adk˚u up a i ak, aby byla yze diagon´alnˇe domi-
nan n´ı; (b) Jacobio a me oda nekon e guje (pouˇzij e poˇc´ı aˇc); (c) ma ice sous a y je pozi i nˇe de ini n´ı
(pouˇzij e Syl es e o o k i e ium); (d) Gausso a-Seidelo a me oda kon e guje (pouˇzij e poˇc´ı aˇc).
2.13. O ˇeˇ e, ˇze p o sous a u o nic


1 1 2
1 2 2
2 2 3


x1
x2
x3
=

4
5
7

pla ´ı: (a) ma ici sous a y nelze ˇz´adn´ym pˇ e o n´an´ım ˇ ´adk˚u up a i ak, aby byla yze diagon´alnˇe domi-
nan n´ı; (b) Jacobio a me oda nekon e guje (pouˇzij e poˇc´ı aˇc); (c) ma ice sous a y nen´ı pozi i nˇe de ini n´ı
(pouˇzij e Syl es e o o k i e ium); (d) Gausso a-Seidelo a me oda nekon e guje (pouˇzij e poˇc´ı aˇc).
2.14. Up a e sous a u ze c iˇcen´ı 2.13 na a ATAx =ATbs pozi i nˇe de ini n´ı ma ic´ı sous a y.
Jako poˇc´a eˇcn´ı ap oximaci z ol e ek o x0= (0,0,0)Ta ˇ eˇs e Gausso ou-Seidelo ou me odou. Pouˇzij e
poˇc´ı aˇc a pozo uj e pomalou kon e genci k ˇ eˇsen´ı. Kolik i e ac´ı je ˇ eba k dosaˇzen´ı pˇ esnos i ε= 10−6,
pouˇzijeme-li k ukonˇcen´ı ´ypoˇc u podm´ınku kxk+1 −xkk∞≤εkxkk∞? Kon e guje Jacobio a me oda?
[ATA=

6 7 10
7 9 12
10 12 17
,ATb=

23
28
39
,k+ 1 = 681. Jacobio a me oda nekon e guje.]
2.15. Nap og amuj e Jacobio u elaxaˇcn´ı me odu (s uˇcnˇe JOR) a Gausso u-Seidelo u elaxaˇcn´ı me odu
SOR. P acuj e se sous a ami
(i)10 3
2 20x1
x2=10
2,(ii)3 2
2 3x1
x2=5
5,
poˇc´a eˇcn´ı i e aci z ol e x0= (0,0)T. (a) Jak ypadaj´ı ek o y x5 znikaj´ıc´ı pˇ i ˇ eˇsen´ı sous a y (i)
me odou JOR a SOR, kdyˇz pouˇzijeme elaxaˇcn´ı pa ame ω= 0,5? (b) Expe imen ´alnˇe najdˇe e pˇ ibliˇznou
op im´aln´ı hodno u ωop p o me odu SOR a sous a u (ii). P o nalezen´e ωop , a ak´e p o ω= 0,5, u ˇce e
nejmenˇs´ı poˇce k ok˚u, pˇ i k e ´em je splnˇena podm´ınka kxk+1 −xkk∞≤10−6kxkk∞. N´a od: pomoc´ı
p og amu mˇeˇn e ωod 1 s k okem 0,01 do 1,99 a u ˇce e pˇ ´ıpad, kdy yjde knejmenˇs´ı.
[ (a) JOR: x5.
= (0,9592; 0,0166)T, SOR: x5.
= (0,9640; 0,0083)T;
(b) p o ωop .
= 1,15 je k+ 1 = 10, p o ω= 0,5 je k+ 1 = 50. ]
40
3. Ap oximace unkc´ı
Ap oximo a unkci (x) znamen´a nah adi ji unkc´ı ϕ(x), k e ´a je k (x) jis ´em
smyslu bl´ızk´a. P´ıˇseme ϕ(x)≈ (x). Budeme se zab´y a d ˇema z´akladn´ımi ypy ap oxi-
mace, a o in e polac´ı a me odou nejmenˇs´ıch ˇc e c˚u.
In e polace je ako ´a ap oximace, pˇ i n´ıˇz ϕ(x) nab´y ´a zadan´ych bodech xipˇ edepsan´ych
hodno yi= (xi). Nˇekdy na ´ıc ˇz´ad´ame, aby unkce ϕa mˇely bodech xi ak´e
s ejn´e de i ace. In e polaci je ˇeno ´an ods a ec 3.1.
Me oda nejmenˇs´ıch ˇc e c˚u je ako ´a ap oximace, pˇ i n´ıˇz ϕ(x) p okl´ad´ame mezi zada-
n´ymi body [xi, yi] ak, aby zd´alenos unkc´ı aϕbyla jis ´em smyslu minim´aln´ı.
Je pˇ i om cha ak e is ick´e, ˇze unkce ϕbody [xi, yi] nep och´az´ı. Me oda nejmenˇs´ıch
ˇc e c˚u je yloˇzena ods a ci 3.2.
Ap oximaci ϕ(x) pouˇzijeme k pˇ ibliˇzn´emu ´ypoˇc u hodno unkce (x), ˇ eba pˇ i y-
k eslo ´an´ı ϕ≈ . Je ˇz´adouc´ı, aby ´ypoˇce ϕ(x) byl jednoduch´y. P o o se ϕˇcas o hled´a
e a u polynomu.
Obecnˇe, ϕ(x) se pouˇz´ı ´a k ˇ eˇsen´ı ´uloh, nichˇz ys upuje unkce , k e ou je ´uˇceln´e
nebo dokonce nezby n´e nah adi jej´ı hodnou ap oximac´ı ϕ. Jako pˇ ´ıklad u ed’me ´ypoˇce
de i ace nebo u ˇci ´eho in eg ´alu: ′(x) nah ad´ıme pomoc´ı ϕ′(x) a Rb
a (x) dxnah ad´ıme
pomoc´ı Rb
aϕ(x) dx.
3.1. In e polace
In e polaˇcn´ı unkci ϕ(x) yb´ı ´ame z hodn´e ˇ ´ıdy unkc´ı. Omez´ıme se na d a nejbˇeˇznˇejˇs´ı
pˇ ´ıpady:
a) ϕ(x) je polynom;
b) ϕ(x) je po ˇc´as ech polynom, na kaˇzd´em subin e alu obecnˇe jin´y.
3.1.1. In e polace polynomem
Pˇ edpokl´adejme, ˇze jsou d´any na z´ajem ˚uzn´e body
x0, x1,...,xn, xi6=xjp o i6=j ,
ˇ ´ık´ame jim ak´e uzly in e polace, a kaˇzd´em z nich je pˇ edeps´ana hodno a yi. Hled´ame
in e polaˇcn´ı polynom Pn(x) s upnˇe nej ´yˇse n, k e ´y splˇnuje in e polaˇcn´ı podm´ınky
Pn(xi) = yi, i = 0,1,...,n. (3.1)
Exis enci in e polaˇcn´ıho polynomu dok´aˇzeme ak, ˇze ho zkons uujeme.
Lag ange˚u a in e polaˇcn´ıho polynomu m´a yj´adˇ en´ı
Pn(x) = y0ℓ0(x) + y1ℓ1(x) + ···+ynℓn(x) =
n
X
i=0
yiℓi(x),(3.2)
41
3.1.2. In e polaˇcn´ı splajny
Jes liˇze chceme in e polo a unkci (x) na pomˇe nˇe dlouh´em in e alu ha, bi, mus´ıme
ˇz´ada splnˇen´ı in e polaˇcn´ıch podm´ınek dos a eˇcnˇe elk´em poˇc u bod˚u. Pokud bude in-
e polan em polynom, mus´ı b´y ysok´eho s upnˇe a o, jak ´ıme, ob ykle ede k elk´ym
chyb´am mezi uzly. Tudy p o o ces a ne ede. Lepˇs´ı je ozdˇeli in e al ha, bina ˇ adu
menˇs´ıch subin e al˚u a na kaˇzd´em z nich ses oji in e polaˇcn´ı polynom niˇzˇs´ıho s upnˇe.
Pˇ edpokl´adejme, ˇze
a=x0< x1<···< xi−1< xi< xi+1 <···< xn−1< xn=b(3.14)
je dˇelen´ı in e alu ha, bi. V kaˇzd´em uzlu xije pˇ edeps´ana hodno a yiin e polan u. D´elku
i- ´eho in e alu hxi−1, xiioznaˇc´ıme hia d´elku nejdelˇs´ıho in e alu h, j.
hi=xi−xi−1, i = 1,2, . . . , n , h = max
1≤i≤nhi.(3.15)
Hledan´y po ˇc´as ech polynomick´y in e polan budeme znaˇci S(x) a naz eme ho in e -
polaˇcn´ım splajnem. Na kaˇzd´em in e alu hxi−1, xiije S(x) polynom, jehoˇz pˇ ´ısluˇsnos
ki- ´emu in e alu yznaˇc´ıme indexem i, j.
S(x) je na in e alu hxi−1, xiipolynom Si(x).
K yj´adˇ en´ı polynomu Si(x) s ´yhodou pouˇzijeme lok´aln´ı p omˇennou
s=x−xi−1.
Budeme ak´e pouˇz´ı a p n´ı pomˇe nou di e enci
δi=yi−yi−1
xi−xi−1
=yi−yi−1
hi
.
Line´a n´ı in e polaˇcn´ı splajn (d´ale jen line´a n´ı splajn) je o nejjednoduˇsˇs´ı, co n´as
napadne: kaˇzd´e d a sousedn´ı body [xi−1, yi−1] a [xi, yi] spoj´ıme ´useˇckou. Zˇ ejmˇe
Si(x) = yi−1+yi−yi−1
xi−xi−1
(x−xi−1) = yi−1+sδi(3.16)
je line´a n´ı in e polaˇcn´ı polynom p och´azej´ıc´ı body [xi−1, yi−1] a [xi, yi]. Line´a n´ı splajn
S(x) je spoji ´a unkce, de i ace S′(x) je ˇsak e ni ˇ n´ıch uzlech obecnˇe nespoji ´a.
Jes liˇze yi= (xi), i= 0,1,...,n, a ∈C2ha, bi, pak p o chybu in e polace pla ´ı
| (x)−S(x)| ≤ Ch2,(3.17)
kde x∈ ha, bije libo oln´e a Cje kons an a nez´a isl´a na h.
P o dos a eˇcnˇe mnoho uzl˚u lze uˇcini chybu libo olnˇe malou. Napˇ ´ıklad pˇ i yk es-
lo ´an´ı na ob azo ku moni o u s ozliˇsen´ım 1920 x 1080 bod˚u jis ˇe s aˇc´ı pouˇz´ı 1920 in-
e polaˇcn´ıch uzl˚u k z´ısk´an´ı k ali n´ıho g a u in e polo an´e unkce. Moˇzn´a bychom byli
spokojeni, i kdybychom z olili m´enˇe uzl˚u, a ˇsak pˇ i pos upn´em sniˇzo ´an´ı poˇc u uzl˚u by
nu nˇe nas al okamˇzik, kdy by n´as jiˇz zaˇcaly uˇsi os ´e h any g a u S(x) in e polaˇcn´ıch
48

uzlech. Pokud bychom souˇcasnˇe yk eslo ali ak´e unkci (x), pak by n´am zaˇcaly adi
ak´e idi eln´e odchylky in e polan u S(x) od in e polo an´e unkce (x) mezi uzly in e -
polace.
Pˇ esnˇejˇs´ı in e polan bychom mohli ses oji ak, ˇze bychom na in e alech hx0, xki,
hxk, x2ki,... ap oximo ali (x) pomoc´ı in e polaˇcn´ıch polynom˚u s upnˇe (nej ´yˇse) k > 1.
Chyba in e polace by om pˇ ´ıpadˇe byla ´umˇe n´a hk+1, de i ace uzlech xk, x2k,...
by ˇsak z˚us aly nespoji ´e. Velk´e kale nem´a smysl pouˇz´ı a , jinak bychom zase mohli
dos a elk´e chyby mezi uzly in e polace a byli bychom zpˇe si uaci, k e ´e jsme se p ´a ˇe
in e polac´ı po ˇc´as ech ch ˇeli yhnou .
Velmi popul´a n´ı je ap oximace po ˇc´as ech kubick´ym polynomem, k e ´a je nejen spoji ´a,
ale m´a ak´e spoji ´e p n´ı nebo dokonce i d uh´e de i ace. Popisu ako ´ych ap oximac´ı se
budeme ˇeno a n´asleduj´ıc´ıch ods a c´ıch.
He mi ˚u kubick´y in e polaˇcn´ı splajn (d´ale jen He mi ˚u kubick´y splajn) hled´ame
jako unkci S(x), k e ´a
a) je in e alu ha, bispoji ´a spolu se s ou p n´ı de i ac´ı, j. S∈C1ha, bi,
b) splˇnuje in e polaˇcn´ı podm´ınky
S(xi) = yi, S′(xi) = di, i = 0,1,...,n, (3.18)
kde yi,dijsou pˇ edepsan´e unkˇcn´ı hodno y a de i ace,
c) je na kaˇzd´em in e alu hxi−1, xii,i= 1,2,...,n, polynom ˇ e ´ıho s upnˇe.
Si(x) je edy kubick´y He mi ˚u polynom jednoznaˇcnˇe u ˇcen´y podm´ınkami
Si(xi−1) = yi−1, S′
i(xi−1) = di−1,
Si(xi) = yi, S′
i(xi) = di.
Snadno o ˇeˇ ´ıme, ˇze y o podm´ınky jsou splnˇeny p o
Si(x) = yi−1+sdi−1+s23δi−2di−1−di
hi
+s3di−1−2δi+di
h2
i
.(3.19)
Funkce S(x) je spoji ´a spolu se s ou p n´ı de i ac´ı, d uh´a de i ace uˇz obecnˇe spoji ´a nen´ı.
Jes liˇze yi= (xi), di= ′(xi), i= 0,1,...,n, a ∈C4ha, bi, pak p o chybu in e po-
lace pla ´ı
| (x)−S(x)| ≤ Ch4,(3.20)
kde x∈ ha, bije libo oln´e a Cje kons an a nez´a isl´a na h.
Pokud de i ace dinejsou k dispozici, mus´ıme je ypoˇc´ı a pomoc´ı hodnˇe z olen´ych
doda eˇcn´ych podm´ınek.
Kubick´y in e polaˇcn´ı splajn (d´ale jen kubick´y splajn). Smˇe nice di e ni ˇ n´ıch uzlech
m˚uˇzeme u ˇci ak, ˇze poˇzadujeme, aby splajn S∈C2ha, bi, j. aby pla ilo
S′′
i(xi) = S′′
i+1(xi), i = 1,2,...,n−1.(3.21)
49
De i o ´an´ım (3.19) dos aneme
S′′
i(x) = (6hi−12s)δi+ (6s−4hi)di−1+ (6s−2hi)di
h2
i
.
P o x=xije s=hi, akˇze
S′′
i(xi) = −6δi+ 2di−1+ 4di
hi
.
P o x=xi−1je s= 0 a
S′′
i(xi−1) = 6δi−4di−1−2di
hi
.
Kdyˇz posledn´ım zo ci z ˇe ˇs´ıme index io jedniˇcku, dos aneme
S′′
i+1(xi) = 6δi+1 −4di−2di+1
hi+1
.
Dosazen´ım do (3.21) ak dos aneme o nice
hi+1di−1+ 2(hi+1 +hi)di+hidi+1 = 3(hi+1δi+hiδi+1), i = 1,2,...,n−1.(3.22)
Jes liˇze pˇ edep´ıˇseme ok ajo ´e podm´ınky
S′(a) = da, S′(b) = db,(3.23)
pak sous a ˇe (3.22) dosad´ıme p n´ı o nici d0:= daa ˇclen h2dapˇ e edeme na p a ou
s anu, a posledn´ı o nici dosad´ıme dn:= dba ˇclen hn−1dbpˇ e edeme na p a ou s anu.
Sous a u pak ˇ eˇs´ıme a z´ısk´ame zb´y aj´ıc´ı smˇe nice di, i = 1,2,...,n−1. Ma ice sous a y je
ˇ ´ıdiagon´aln´ı, diagon´alnˇe dominan n´ı, akˇze sous a u lze snadno yˇ eˇsi GEM up a enou
p o sous a y s ˇ ´ıdiagon´aln´ı ma ic´ı. V MATLABu lze p o ´ypoˇce kubick´eho splajnu
pouˇz´ı unkci spline.
Jes liˇze yi= (xi), i= 0,1,...,n,d0= ′(x0), dn= ′(xn), a kdyˇz ∈C4ha, bi, pak
p o chybu in e polace opˇe pla ´ı (3.20).
Ob ´azek 3.3 po zuje, ˇze pomoc´ı kubick´eho splajnu lze p o da a s ejn´a jako pˇ ´ıkladu
3.4 dos a zcela yho uj´ıc´ı ap oximaci Rungeo y unkce.
Kubick´y splajn m´a pozo uhodnou ex em´aln´ı las nos , k e ou si ed’pop´ıˇseme. Ozna-
ˇc´ıme
V={ ∈C2ha, bi| (xi) = yi, i = 0,1,...,n, ′(x0) = d0, ′(xn) = dn}
mnoˇzinu ˇsech unkc´ı, k e ´e maj´ı in e alu ha, bispoji ou d uhou de i aci, p och´azej´ı
zadan´ymi body [xi, yi], i= 0,1,...,n, a k ajn´ıch bodech a=x0axn=bjejich de i ace
nab´y aj´ı pˇ edepsan´ych hodno d0adn. Pak Rb
a[ ′′(x)]2dxnab´y ´a na mnoˇzinˇe unkc´ı V
s ´e nejmenˇs´ı hodno y p o kubick´y splajn S(x), j. pla ´ı
Zb
a
[S′′(x)]2dx= min
∈VZb
a
[ ′′(x)]2dx .
50
−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1
0
0.2
0.4
0.6
0.8
1Kubický splajn
1/(1+25x2)
Ob . 3.3: Ap oximace Rungeo y unkce kubick´ym splajnem
Ta o las nos m´a zaj´ıma ou in e p e aci mechanice. Je o iˇz zn´amo, ˇze ohybo ´a
ene gie homogenn´ıho izo opn´ıho p u u, jehoˇz s ˇ ednico ´a ˇc´a a m´a o nici y= (x),
x∈ ha, bi, m´a pˇ ibliˇznˇe hodno u E( ) = cRb
a[ ′′(x)]2dx, kde cje hodn´a kons an a.
A d´ale je ak´e zn´amo, ˇze p u , k e ´y je donucen p och´aze pe n´ymi in e polaˇcn´ımi body
[xi, yi], zaujme pozici s minim´aln´ı ene gi´ı. Ex em´aln´ı las nos edy d´ı, ˇze kubick´y
splajn ap oximuje s ˇ ednico ou ˇc´a u ako ´eho p u u.
Jes liˇze smˇe nice daadb k ajn´ıch bodech in e alu ha, binezn´ame, os ˇedˇcil se po-
s up, oznaˇco an´y anglicky psan´e li e a uˇ e jako no a kno . Myˇslenka je jednoduch´a:
poˇzadujeme, aby splajn byl jednoduch´ym polynomem ˇ e ´ıho s upnˇe na p n´ıch d ou in-
e alech, j. p o x0≤x≤x2, a na posledn´ıch d ou in e alech, j. p o xn−2≤x≤xn.
V uzlech x1axn−1 edy uˇz nedoch´az´ı k napojo ´an´ı d ou ˚uzn´ych polynom˚u, j. uzel x1
axn−1uˇz nen´ı kno , ˇcesky uzel splajnu, od ud n´aze pos upu no a kno .
Polynomy S1(x) a S2(x) maj´ı bodˇe x1spoleˇcnou unkˇcn´ı hodno u y1, s ejnou p n´ı
de i aci d1a podle (3.21) ak´e s ejnou d uhou de i aci. Aby oba polynomy byly o oˇzn´e
s aˇc´ı, kdyˇz budou m´ı bodˇe x1 ak´e s ejnou ˇ e ´ı de i aci. S ejnou ´u ahu lze p o ´es
bodˇe xn−1. Dos ´a ´ame ak ok ajo ´e podm´ınky
S′′′
1(x1) = S′′′
2(x1), S′′′
n−1(xn−1) = S′′′
n(xn−1).(3.24)
Kdyˇz pomoc´ı (3.19) yj´adˇ ´ıme podm´ınku S′′′
1(x1) = S′′′
2(x1) a up a ´ıme ji pomoc´ı p n´ı
o nice sous a y (3.22), dos aneme o nici
h2d0+ (h2+h1)d1= [(3h1+ 2h2)h2δ1+h2
1δ2]/(h1+h2).(3.25)
Podobnˇe zp acujeme ak´e podm´ınku S′′′
n−1(xn−1) = S′′′
n(xn−1) a dos aneme o nici
(hn+hn−1)dn−1+hn−1dn= [h2
nδn−1+ (2hn−1+ 3hn)hn−1δn]/(hn−1+hn).(3.26)
51
Nezn´am´e d0, d1,...,dnpak dos aneme jako ˇ eˇsen´ı sous a y o nic, z nichˇz p n´ı je o nice
(3.25), pak n´asleduje n−1 o nic (3.22) a nakonec pˇ ijde jeˇs ˇe o nice (3.26). Pouˇzijeme
opˇe GEM up a enou p o sous a y s ˇ ´ıdiagon´aln´ı ma ic´ı.
Je-li ap oximo an´a unkce pe iodick´a s pe iodou b−a, je pˇ i ozen´e poˇzado a , aby ap o-
ximuj´ıc´ı splajn byl o nˇeˇz pe iodick´y s ou ´eˇz pe iodou. Je-li edy Spe iodick´y kubick´y
splajn s pe iodou b−a, pak na in e alu hb, b +h1inab´y ´a s ejn´ych hodno jako na
in e alu ha, a +h1i. Jes liˇze oznaˇc´ıme hn+1 =h1,xn+1 =xn+hn+1,S(xn+1) = yn+1
aS′(xn+1) = dn+1, pak mus´ı pla i yn=y0,dn=d0,yn+1 =y1adn+1 =d1. Spoji os
S′′ bodˇe xnznamen´a, ˇze o nice (3.22) pla ´ı ak´e p o i=n. Pe iodick´y kubick´y splajn
je edy u ˇcen, pokud ypoˇc eme d1, d2,...,dnz o nic (3.22) p o i= 1,2,...,ns ´ım, ˇze
p n´ı z nich, j. p o i= 1, m´ıs o d0p´ıˇseme dn, posledn´ı z nich , j. p o i=n, m´ıs o
dn+1 p´ıˇseme d1a poloˇz´ıme hn+1 =h1,δn+1 =δ1.
Sh nu ´ı. Kubick´y in e polaˇcn´ı splajn S(x) je unkce, k e ´a
a) je in e alu ha, bispoji ´a spolu se s ou p n´ı a d uhou de i ac´ı, j. S∈C2ha, bi,
b) splˇnuje in e polaˇcn´ı podm´ınky S(xi) = yi,i= 0,1,...,n, kde yijsou pˇ edepsan´e
unkˇcn´ı hodno y,
c) je na kaˇzd´em in e alu hxi−1, xiipolynom ˇ e ´ıho s upnˇe,
d) splˇnuje ok ajo ´e podm´ınky (3.23) nebo (3.24) nebo je pe iodick´a s pe iodou b−a.
Pˇ ´ıklad 3.6. Oblouk [x( ), y( )] ≡[cos , sin ], ∈ h0, π/2i, budeme ap oximo a kˇ i kou
[Sx( ), Sy( )], kde Sx( ) esp. Sy( ) jsou kubick´e splajny unkc´ı cos esp. sin na in e alu
h0, π/2i. In e al h0, π/2i ozdˇel´ıme na ns ejn´ych d´ılk˚u, akˇze i=πi/(2n). Oznaˇc´ıme
dx
i= [Sx]′( i), dy
i= [Sy]′( i). P o oˇze x′( ) = −sin ,y′( ) = cos , poloˇz´ıme
dx
0=−sin 0 = 0 , dx
n=−sin(π/2) = −1, dy
0= cos 0 = 1 , dy
n= cos(π/2) = 0 .
V dalˇs´ım budeme u aˇzo a n= 3. Sous a u o nic (3.22) ses a ´ıme z l´aˇs
’p o x-o ou
a z l´aˇs
’p o y-o ou sloˇzku. Ma ice obou sous a je s ejn´a, p a ´e s any jsou ˇsak ˚uzn´e.
Na dalˇs´ım ˇ ´adku je u edena sous a a o nic se d ˇema p a ´ymi s anami a jej´ı ˇ eˇsen´ı:
1
6π1 4 1 0
0 1 4 1



0 1
dx
1dy
1
dx
2dy
2
−1 0



= 3 −1
2
1
2√3
−1
2√31
2=⇒dy
1=−dx
2
.
= 0,865537,
dy
2=−dx
1
.
= 0,499813.
Sx
i( ) a Sy
i( ) u ˇc´ıme podle (3.19). Napˇ ´ıklad p o ∈ hπ/6, π/3idos aneme
Sx
2( ).
= 0,8660 −0,4998( −1
6π)−0,4431( −1
6π)2+ 0,1195( −1
6π)3,
Sy
2( ).
= 0,5000 + 0,8655( −1
6π)−0,2554( −1
6π)2−0,1195( −1
6π)3.
Kons ukce kubick´eho in e polaˇcn´ıho splajnu uˇzi ´ım d uh´ych de i ac´ı. Snadno
o ˇeˇ ´ıme, ˇze kubick´y polynom
Si(x) = yi−1+s6δi−2hiMi−1−hiMi
6+s2Mi−1
2+s3Mi−Mi−1
6hi
.(3.27)
52
splˇnuje podm´ınky
Si(xi−1) = yi−1, S′′
i(xi−1) = Mi−1,
Si(xi) = yi, S′′
i(xi) = Mi.
Funkce S(x), k e ´a je na kaˇzd´em in e alu hxi−1, xiide ino ´ana pˇ edpisem (3.27), p o o
zˇ ejmˇe splˇnuje podm´ınky S(xi) = yi,S′′(xi) = Mi,i= 0,1,...,n.S(x) je edy na
in e alu ha, bispoji ´a a m´a nˇem spoji ou d uhou de i aci. Abychom dos ali kubick´y
splajn, mus´ı m´ı S(x) ha, bispoji ou ak´e p n´ı de i aci. P o oˇze nespoji os S′(x) m˚uˇze
nas a jedinˇe e ni ˇ n´ıch uzlech, s aˇc´ı poˇzado a
S′
i(xi) = S′
i+1(xi), i = 1,2,...,n−1.(3.28)
Vyj´adˇ ´ıme-li (3.28) pomoc´ı (3.27), dos aneme o nice
hiMi−1+ 2(hi+hi+1)Mi+hi+1Mi+1 = 6(δi+1 −δi), i = 1,2,...,n−1.(3.29)
Kdyˇz z ol´ıme ok ajo ´e podm´ınky
S′′(a) = Ma, S′′(b) = Mb,(3.30)
dosad´ıme je do (3.29), sous a u o nic yˇ eˇs´ıme a z´ısk´ame Mi,i= 1,2,...,n−1. Vˇsimnˇe e
si, ˇze ma ice sous a y (3.29) je syme ick´a. Je samozˇ ejmˇe moˇzn´e u aˇzo a ak´e jin´e ypy
ok ajo ´ych podm´ınek, napˇ . (3.23) nebo (3.24).
Kubick´y splajn s las nos ´ı S′′(a) = S′′(b) = 0 se naz´y ´a pˇ i ozen´y kubick´y splajn.
Je zn´amo, ˇze pˇ i ozen´y kubick´y splajn ap oximuje p ˚uhyb p os ˇe podepˇ en´eho nosn´ıku
p och´azej´ıc´ıho body [xi, yi]. Mimaj´ı ´yznam ohybo ´ych momen ˚u uzlech [xi, yi].
3.1.3. In e polace unkc´ı ´ıce p omˇenn´ych
Omez´ıme se na pˇ ´ıpad, kdy je unkce d ou p omˇenn´ych de ino an´a oblas i Ω.
In e polace po ˇc´as ech line´a n´ı. Pˇ edpokl´adejme, ˇze Ω je mnoho´uheln´ık. Oblas Ω
iangulujeme, j. yj´adˇ ´ıme ji jako sjednocen´ı oj´uheln´ık˚u T1, T2,...,Tm, z nichˇz kaˇzd´e
d a ˚uzn´e bud’ o nemaj´ı ˇz´adn´y spoleˇcn´y bod nebo maj´ı spoleˇcn´y chol popˇ ´ıpadˇe maj´ı
spoleˇcnou s anu. Mnoˇzinu T={Tk}m
k=1 ˇsech ako ´ych oj´uheln´ık˚u naz´y ´ame ian-
gulac´ı oblas i Ω. V choly oj´uheln´ık˚u iangulace oznaˇc´ıme P1= [x1, y1], P2= [x2, y2],
...,Pn= [xn, yn] a naz eme je uzly iangulace. Pˇ edpokl´adejme, ˇze kaˇzd´em uzlu Pije
pˇ edeps´ana hodno a i= (xi, yi) in e polo an´e unkce .
Po ˇc´as ech line´a n´ım in e polan em unkce na oblas i Ω ozum´ıme unkci S, k e ´a
je Ω spoji ´a, splˇnuje in e polaˇcn´ı podm´ınky S(xi, yi) = i,i= 1,2,...,n, a k e ´a je na
kaˇzd´em oj´uheln´ıku Tk∈Tline´a n´ı. Na Tkje edy z=S(x, y)≡Sk(x, y) o nice o iny
u ˇcen´e hodno ami unkce e cholech Tk. Pˇ ipomeˇnme, ˇze o nice o iny p och´azej´ıc´ı
body [xa, ya, za], [xb, yb, zb] a [xc, yc, zc] m˚uˇze b´y yj´adˇ ena e a u

x−xay−yaz−za
xb−xayb−yazb−za
xc−xayc−yazc−za= 0 .
53

Vypoˇc´ı a hodno u z=S(x, y) p o (x, y)∈Ω je snadn´e: u ˇc´ıme oj´uheln´ık Tk, nˇemˇz
bod [x, y] leˇz´ı, a ypoˇc eme z=Sk(x, y).
Chyba in e polace je ´ım menˇs´ı, ˇc´ım jemnˇejˇs´ı iangulaci z ol´ıme. Kdyˇz ∈C2(Ω)
( j. kdyˇz je Ω spoji ´a spolu se s ´ymi p n´ımi a d uh´ymi pa ci´aln´ımi de i acemi), pak
| (x, y)−S(x, y)| ≤ Ch2,
kde hje nejdelˇs´ı s ana oj´uheln´ık˚u iangulace a Cje kons an a nez´a isl´a na h.
In e polace po ˇc´as ech biline´a n´ı. Pˇ edpokl´adejme, ˇze Ω = ha, bi×hc, dije obd´eln´ık.
Pomoc´ı dˇelen´ı a=x0< x1<···< xn=b,c=y0< y1<···< ym=d ozloˇz´ıme
´ychoz´ı obd´eln´ık Ω na menˇs´ı obd´eln´ıky Rij ={(x, y)|xi−1≤x≤xi, yj−1≤y≤yj},
i= 1,2,...,n,j= 1,2,...,m. Pˇ edpokl´adejme, ˇze uzlech [xi, yj] jsou pˇ edeps´any
hodno y ij = (xi, yj) unkce .
Na obd´eln´ıku Rij de inujeme unkci
Sij(x, y) = i−1,j−1
xi−x
xi−xi−1
yj−y
yj−yj−1
+ i,j−1
x−xi−1
xi−xi−1
yj−y
yj−yj−1
+
+ i−1,j
xi−x
xi−xi−1
y−yj−1
yj−yj−1
+ ij
x−xi−1
xi−xi−1
y−yj−1
yj−yj−1
.
Funkce Sij je biline´a n´ı , j. p o pe n´e x=Cje Sij(C, y) line´a n´ı unkce p omˇenn´e ya p o
pe n´e y=Dje Sij(x, D) line´a n´ı unkce p omˇenn´e x. Funkce Sij je in e polan unkce
na obd´eln´ıku Rij , j. Sij nab´y ´a e cholech [xi−1, yj−1], [xi, yj−1], [xi, yj] a [xi−1, yj]
s ejn´ych hodno jako unkce , jak se snadno pˇ es ˇedˇc´ıme.
Na Ω de inujeme unkci Spˇ edpisem S(x, y) = Sij(x, y) p o (x, y)∈Rij,i= 1,2,...,n,
j= 1,2,...,m. P o oˇze S(xi, yj) = ij,i= 0,1,...,n,j= 0,1,...,m, ˇ ekneme, ˇze Sje
po ˇc´as ech biline´a n´ı in e polan unkce na obd´eln´ıku Ω. Snadno o ˇeˇ ´ıme, ˇze Sje Ω
spoji ´a (s aˇc´ı si u ˇedomi , ˇze Sij, a edy ak´e S, je na kaˇzd´e s anˇe obd´eln´ıka Rij line´a n´ı
unkce jednoznaˇcnˇe u ˇcena pomoc´ı hodno unkce konco ´ych bodech ´e o s any).
Kdyˇz ∈C2(Ω), pak p o chybu in e polace pla ´ı odhad
|S(x, y)− (x, y)| ≤ C(h2+k2),kde h= max
1≤i≤n(xi−xi−1), k = max
1≤j≤m(yj−yj−1)
aCje kons an a nez´a isl´a na h,k.
3.2. Me oda nejmenˇs´ıch ˇc e c˚u
oznaˇcuje pos up p o pˇ ibliˇzn´e ˇ eˇsen´ı pˇ eu ˇcen´ych nebo nepˇ esnˇe zadan´ych sous a o nic,
zaloˇzen´y na minimalizaci k ad ´a ˚u jejich ezidu´ı.
P okl´ad´an´ı da kˇ i kami je ´yznamn´a skupina ´uloh, k e ´e lze me odou nejmenˇs´ıch
ˇc e c˚u ˇ eˇsi ( anglicky psan´e li e a uˇ e se p o y o aplikace pouˇz´ı ´a oznaˇcen´ı cu e
i ing). Popiˇsme si, o co ako ´ych ´uloh´ach jde.
54
Nech
’ je nez´a isle p omˇenn´a, napˇ ´ıklad ˇcas, a y( ) je nezn´am´a unkce p omˇenn´e ,
k e ou chceme ap oximo a . Pˇ edpokl´adejme, ˇze jsme p o edli mpozo o ´an´ı, pˇ i nichˇz
byly hodno y ypˇ ibliˇznˇe zmˇeˇ eny p o u ˇci ´e (na z´ajem ˚uzn´e) hodno y , akˇze
yi≈y( i), i = 1,2,...,m,
kde symbol ≈ yjadˇ uje pˇ ibliˇznou o nos . Naˇs´ım z´amˇe em je modelo a y( ) line´a n´ı
kombinac´ı nb´azo ´ych unkc´ı p o nˇejak´e n≤m:
y( )≈x1ϕ1( ) + x2ϕ2( ) + ···+xnϕn( ) =: Rn( ).
Funkce Rn( ) se e s a is ice naz´y ´a line´a n´ı eg esn´ı unkce. B´azo ´e unkce na hujeme
podle oˇcek´a an´eho p ˚ubˇehu nezn´am´e unkce y( ), u ˇci se maj´ı pa ame y x1, x2,...,xn,
a o ak, aby
yi≈Rn( i), i = 1,2,...,m, ma ico ˇe y≈Ax,
kde y= (y1, y2,...,ym)Tjsou namˇeˇ en´a da a, x= (x1, x2,...,xn)Tje ek o nezn´am´ych
pa ame ˚u a Aje ak z an´a n´a ho ´a ma ice,
A=






ϕ1( 1)ϕ2( 1). . . ϕn( 1)
ϕ1( 2)ϕ2( 2). . . ϕn( 2)
.
.
..
.
..
.
.
ϕ1( m)ϕ2( m). . . ϕn( m)






≡(ϕ1,ϕ2,...,ϕn).
Vek o ϕi= (ϕi( 1), ϕi( 2),...ϕi( m))T,i= 1,2,...,n, je i- ´y sloupec ma ice A.
Rezidua jsou ozd´ıly mezi pozo o ´an´ımi yia modelo an´ymi hodno ami Rn( i):
i=yi−Rn( i) = yi−
n
X
j=1
ϕj( i)xj≡yi−
n
X
j=1
aijxj, i = 1,2,...,m,
kde aij =ϕj( i). V ma ico ´em z´apisu
=y−Ax .(3.31)
Pa ame y xichceme u ˇci ak, aby ezidua byla co nejmenˇs´ı. Me odu nejmenˇs´ıch ˇc e c˚u
dos aneme, kdyˇz minimalizujeme souˇce ˇc e c˚u ezidu´ı:
k k2
2=
m
X
i=1
2
i→min .(3.32)
Nˇekdy se pouˇz´ı ´a ak´e ´aˇzen´a me oda nejmenˇs´ıch ˇc e c˚u: kdyˇz jsou nˇek e ´a pozo o ´an´ı
´yznamnˇejˇs´ı neˇz os a n´ı, m˚uˇzeme jedno li ´ym pozo o ´an´ım pˇ isoudi ´ahy wi>0 a mini-
malizo a souˇce ´aˇzen´ych ˇc e c˚u ezidu´ı
k k2
2,w =
m
X
i=1
wi 2
i→min .
55
i=yi−Rn ( i )
1
2
2
2
i−1
2
i
2
i+1
2
m
2
Σi=1
m i
2 → min
1
y1
2
y2
i−1
yi−1
i
yi
i+1
yi+1
m
ym
Ob . 3.4: P incip me ody nejmenˇs´ıch ˇc e c˚u
Je-li napˇ ´ıklad chyba i- ´eho pozo o ´an´ı pˇ ibliˇznˇe o na ei, z ol´ıme wi= 1/ei.
No m´aln´ı sous a a o nic. Oznaˇcme F(x) = ky−Axk2
2≡ k k2
2.ˇ
Reˇsen´ı minimalizaˇcn´ı
´ulohy (3.32) mus´ı splˇno a nu nou podm´ınku p o ex ´em:
∂F(x)
∂xk
=∂
∂xk
m
X
i=1 yi−
n
X
j=1
aijxj!2
= 0 , k = 1,2,...,n.
Kdyˇz p o edeme naznaˇcen´e de i o ´an´ı, dos aneme
∂F(x)
∂xk
= 2
m
X
i=1 yi−
n
X
j=1
aijxj!(−aik) = 0,
a od ud
n
X
j=1 m
X
i=1
aikaij!xj=
m
X
i=1
aikyi, k = 1,2,...,n,
coˇz lze zapsa ma ico ˇe jako
ATAx =ATy.(3.33)
Sous a a line´a n´ıch o nic (3.33) je zn´ama jako no m´aln´ı sous a a o nic. Kdyˇz jsou
sloupce ma ice Aline´a nˇe nez´a isl´e, je ma ice G:= ATApozi i nˇe de ini n´ı, akˇze ˇ eˇsen´ı
x∗no m´aln´ı sous a y o nic minimalizuje F(x)≡ k k2
2a je edy ˇ eˇsen´ım ´ulohy (3.32):
ky−Ax∗k2
2= min
x∈Rnky−Axk2
2nebo-li x∗= a gmin
x∈Rnky−Axk2
2.
56
Vyj´adˇ ´ıme-li no m´aln´ı sous a u o nic pomoc´ı ek o ˚u ϕi, dos aneme






(ϕ1,ϕ1) (ϕ1,ϕ2)... (ϕ1,ϕn)
(ϕ2,ϕ1) (ϕ2,ϕ2)... (ϕ2,ϕn)
.
.
..
.
.... .
.
.
(ϕn,ϕ1) (ϕn,ϕ2) (ϕn,ϕn)












x1
x2
.
.
.
xn






=





(ϕ1,y)
(ϕ2,y)
.
.
.
(ϕn,y)






,(3.34)
kde
(ϕk,ϕj) =
m
X
i=1
ϕk( i)ϕj( i) a (ϕk,y) =
m
X
i=1
ϕk( i)yi
jsou skal´a n´ı souˇciny ek o ˚u ϕk,ϕjaϕk,y. Ma ice Gsous a y (3.34) se naz´y ´a G amo a
ma ice sous a y ek o ˚u {ϕj}n
j=1.
Pˇ i n´a hu ap oximace Rn( ) bychom mˇeli yb´ı a unkce ϕi( ) ak, aby sloupce ϕi
ma ice Abyly line´a nˇe nez´a isl´e. V opaˇcn´em pˇ ´ıpadˇe, jak se d´a uk´aza , m´a ´uloha (3.32)
nekoneˇcnˇe mnoho ˇ eˇsen´ı, coˇz je zˇ ejmˇe neˇz´adouc´ı.
U ed’me si d a ´yznamn´e speci´aln´ı pˇ ´ıpady, p o k e ´e jsou sloupce ma ice Aline´a nˇe
nez´a isl´e (d˚ukaz lze naj´ı napˇ . [1]):
a) p o n=N+ 1 ol´ıme ϕj( ) = j−1,j= 1,2,...,N + 1;
b) p o n= 2N+ 1 ol´ıme
ϕ1( ) = 1, ϕ2k( ) = cos kπ
L , ϕ2k+1( ) = sin kπ
L , k = 1,2,...,N,
a ˇcasy pozo o ´an´ı i yb´ı ´ame z in e aluhc, c + 2L), kde L > 0, clibo oln´e.
Ap oximace Rn( ) je pˇ ´ıpadˇe a) algeb aick´y polynom s upnˇe Na pˇ ´ıpadˇe b) igono-
me ick´y polynom s upnˇe N.
Kdyˇz je m=na ma ice Aje egul´a n´ı, pak x∗=A−1ya =o, j. Rn( i) = yi,
i= 1,2,...,m. Pokud jsou ˇsak namˇeˇ en´a da a yiza ´ıˇzena chybami, pak nen´ı ´uˇceln´e,
aby unkce Rn( ) y o chyby kop´ı o ala. Naopak, aby Rn( ) ˇe ohodnˇe ys iho ala ( e-
kons uo ala) nezn´amou unkci y( ), je ˇz´adouc´ı, aby Rn( ) namˇeˇ en´a da a y o n´a ala
( yhlazo ala). To je ale moˇzn´e jen ehdy, kdyˇz poˇce pozo o ´an´ı mje ´y aznˇe ˇe ˇs´ı neˇz
poˇce nn´a ho ´ych pa ame ˚u, j. p o m≫n.
Pˇ ´ıklad 3.7. P o da a pˇ edepsan´a abulkou
i0 0,5 1 1,5 2 2,5 3
yi3,57 2,99 2,62 2,33 2,22 2,10 2,05
u ˇc´ıme ap oximaci R2( ) = x1+x2e− me odou nejmenˇs´ıch ˇc e c˚u. Zˇ ejmˇe ϕ1( ) = 1
aϕ2( ) = e− . No m´aln´ı sous a a o nic je a u




7
P
i=1
1·1
7
P
i=1
1·e− i
7
P
i=1
e− i·1
7
P
i=1
e− i·e− i







x1
x2



=



7
P
i=1
1·yi
7
P
i=1
e− i·yi



.
57
′(x) = (x+h)− (x−h)
2h−1
6h2 ′′′(ξ),(4.3b)
′(x) = 3 (x)−4 (x−h) + (x−2h)
2h+1
3h2 ′′′(ξ).(4.3c)
U ed’me jeˇs ˇe nejzn´amˇejˇs´ı o muli ′′(x1).
=P′′
2(x1) p o ´ypoˇce d uh´e de i ace. Ro nos
′′(x) = (x+h)−2 (x) + (x−h)
h2−1
12h2 (4)(ξ).(4.4)
o ˇeˇ ´ıme uˇzi ´ım Taylo o a oz oje (x±h) okolo x.
Fo mule ze zo ce (4.2a) je zn´ama jako p n´ı di e ence pˇ ed (dopˇ edn´a di e ence)
a o mule ze zo ce (4.2b) jako p n´ı di e ence zad (zpˇe n´a di e ence). Fo mule ze zo ce
(4.3b) b´y ´a oznaˇco ´ana jako p n´ı cen ´aln´ı di e ence a o mule ze zo ce (4.4) jako d uh´a
cen ´aln´ı di e ence.
Nume ick´y ´ypoˇce pa ci´aln´ı de i ace nepˇ eds a uje ˇz´adn´y no ´y p obl´em: de i uje-
me-li podle p omˇenn´e xi, os a n´ıch p omˇenn´ych xj6=xisi ne ˇs´ım´ame a nˇek e ou z ´yˇse
u eden´ych o mul´ı aplikujeme jen na xi. Tak ˇ eba pomoc´ı dopˇ edn´e di e ence (4.2a)
dos aneme
∂ (x1, x2)
∂x2≈ (x1, x2+h)− (x1, x2)
h.
Podm´ınˇenos nume ick´eho ´ypoˇc u de i ace. Ve zo c´ıch (4.2) – (4.4) jsme u edli
ˇzdy o muli (jako p n´ı sˇc´ı anec na p a ´e s anˇe) a jej´ı disk e izaˇcn´ı chybu (jako d uh´y
sˇc´ı anec). Pˇ i nume ick´em ´ypoˇc u de i ace h aj´ı ´yznamnou oli ak´e zaok ouhlo ac´ı
chyby, a o jak hodno ´ach unkce ( j. e s upn´ıch da ech), ak pˇ i yhodnocen´ı
o mule ( j. pˇ i ´ypoˇc u). Uk´aˇzeme si o p o o muli ze zo ce (4.2a).
Ve sku eˇcnos i za pˇ ibliˇznou hodno u de i ace ′(x) po aˇzujeme ´y az
˜
′(x) := ˜
(x+h)−˜
(x)
h=[ (x+h) + ε1]−[ (x) + ε0]
h= ′(x)+ 1
2h ′′(ξ)+ ε1−ε0
h,
kde ε1 esp. ε0je zaok ouhlo ac´ı chyba, k e ´e se dopus ´ıme pˇ i ´ypoˇc u (x+h) esp.
(x). Tedy
′(x) = ˜
(x+h)−˜
(x)
h+Ed+E ,
kde Ed:= −1
2h ′′(ξ) je disk e izaˇcn´ı chyba aE := −(ε1−ε0)/h je chyba zaok ouhlo ac´ı.
Cho ´an´ı obou chyb je p o h→0 diame ´alnˇe odliˇsn´e: za ´ımco |Ed| → 0, |E | → ∞. P o
mal´a hse edy zˇ ejmˇe jedn´a o ˇspa nˇe podm´ınˇenou ´ulohu: mal´e zmˇeny ε0, ε1 e s upn´ıch
da ech y olaj´ı elkou zmˇenu E a n´aslednˇe ak´e ´ysledku ˜
′(x).
Kdyˇz p o jednoduchos zanedb´ame zaok ouhlo ac´ı chyby znikaj´ıc´ı pˇ i yˇc´ıslen´ı o -
mule [ ˜
(x+h)−˜
(x)]/h, dos ´a ´ame p o celko ou chybu E=Ed+E odhad
|E| ≤ |Ed|+|E | ≤ 1
2hM2+ 2 ε
h≡g(h),
64

kde M2≥ | ′′(ξ)|aε≥max(|ε1|,|ε2)|). Minimalizac´ı unkce g(h) obd ˇz´ıme op im´aln´ı
d´elku k oku
hop = 2 ε
M2
,p o k e ou |Eop |=g(hop ) = 2pεM2.
Pˇ edpokl´adejme, ˇze hodno y (x) i (x+h) dok´aˇzeme ypoˇc´ı a s ela i n´ı chybou
o nou pˇ ibliˇznˇe ˇc´ıslu δ, akˇze ε≈M0δ, kde M0≈max(| (x0)|,| (x0+h)|). P o M0≈M2
je hop ≈2√δa|Eop | ≈ 2M0√δ. Poˇc´ı ´ame-li edy napˇ . e d ojn´asobn´e pˇ esnos i a pokud
δ≈10−16, pak hop ≈2·10−8. Jes liˇze na ´ıc | ′(x)| ≈ M0, pak |Eop | ≈ 2| ′(x)|√δ, a o
znamen´a, ˇze elikos ela i n´ı chyby de i ace ˜
′(x) je ˇ ´ado ˇe o na d uh´e odmocninˇe
elikos i ela i n´ı chyby unkˇcn´ıch hodno . To n´as op a ˇnuje k zen´ı: pˇ i pˇ ibliˇzn´em
´ypoˇc u de i ace o mul´ı dopˇ edn´e (nebo zpˇe n´e) di e ence doch´az´ı pˇ i op im´aln´ı olbˇe
k oku ke z ´a ˇe pˇ ibliˇznˇe polo iny pla n´ych ci e .
0 0.2 0.5 1 1.5 2
x 10−7
0
0.5
1
1.5
2x 10−7
h
g(h)
[hop ,Eop ]
Ob . 4.1: Chyba nume ick´e de i ace: p o g(h) = 1
2h+ 2 ·10−16/h je hop = 2 ·10−8=Eop
Podobn´e cho ´an´ı ykazuj´ı i os a n´ı o mule nume ick´eho de i o ´an´ı, j. p o k ok h
bl´ızk´y hop je nume ick´y ´ypoˇce de i ace ˇspa nˇe podm´ınˇen´a ´uloha: nepa n´e zmenˇsen´ı
k oku y ol´a znaˇcn´y n´a us chyby, iz ob . 4.1.
4.2. Richa dsono a ex apolace
Pˇ ibliˇzn´y ´ypoˇce de i ace lze e ek i nˇe zpˇ esni echnikou zn´amou jako Richa dsono a
ex apolace. Je o uni e z´aln´ı pos up umoˇzˇnuj´ıc´ı pomoc´ı z´akladn´ı me ody niˇzˇs´ı pˇ esnos i
y ´aˇ e me ody yˇsˇs´ı pˇ esnos i. Ukaˇzme si, jak se o dˇel´a.
Pˇ edpokl´adejme, ˇze z´akladn´ı me oda je ep ezen o ´ana unkc´ı F(h) pa ame u h. Me-
odou Fum´ıme ypoˇc´ı a hodno u F(h) p o mal´a h > 0. Naˇs´ım c´ılem je co nejpˇ esnˇeji
ap oximo a hodno u F(0), k e ou ˇsak pˇ ´ımo z o mule Fu ˇci neum´ıme.
65
Pˇ edpokl´adejme, ˇze unkce F(h) m˚uˇze b´y zaps´ana e a u mocninn´eho oz oje
F(h) = a0+a1h2+a2h4+a3h6+... (4.5)
Konk ´e n´ı o mule Fje zkoum´ana pˇ ´ıkladu 4.1, iz (4.14), pˇ ´ıkladu 4.5 a e c iˇcen´ı
4.2, iz (4.30). P o mal´e hje F(h) jis ˇe dob ou ap oximac´ı F(0) = a0. Pokus´ıme se naj´ı
lepˇs´ı ap oximaci a0. Zaˇcneme ´ım, ˇze ypoˇc eme F(h
2). Podle (4.5) pla ´ı
Fh
2=a0+a1h
22
+a2h
24
+a3h
26
+... (4.6)
Nej ˇe ˇs´ı chybu e ´y azu a0−F(h) i a0−F(h
2) pˇ eds a uje ˇclen obsahuj´ıc´ı d uhou mocni-
nu h. Zba ´ıme se ho ak, ˇze od ˇc yˇ n´asobku o nice (4.6) odeˇc eme o nici (4.5) a ´ysledek
dˇel´ıme ˇ emi. Tak dos aneme
F2(h) := 4F(h
2)−F(h)
3=a0+a(2)
2h4+a(2)
3h6+... (4.7)
Snadno o ˇeˇ ´ıme, ˇze |a(2)
j|<|aj|,j= 2,3,....F2(h) je p o o lepˇs´ı ap oximace a0neˇz F(h)
nebo
’a0−F2(h) zaˇc´ın´a aˇz ˇc ou mocninou h. Dos ali jsme edy me odu F2, k e ´a je
(p o dos i mal´a h) lepˇs´ı neˇz p˚u odn´ı me oda F. P o oˇze F2(h)≈F(0) je spoˇc ena pomoc´ı
hodno unkce Fp o hah
2, pˇ eds a uje F2(h)ex apolaci unkce Fdo nuly (o ˇeˇ e, ˇze
F2(h) = P1(0), kde P1( ) je line´a n´ı in e polaˇcn´ı polynom p och´azej´ıc´ı body [(h
2)2, F(h
2)]
a [h2, F(h)]).
Podobn´ym pos upem ods an´ıme z F2(h) ˇclen obsahuj´ıc´ı ˇc ou mocninu ha z´ısk´ame
jeˇs ˇe lepˇs´ı ap oximaci F(0). Nejp e ypoˇc eme F2(h
2). Podle (4.7) pla ´ı
F2h
2=a0+a(2)
2h
24
+a(2)
3h
26
+... (4.8)
Ro nici (4.8) n´asob´ıme 16, odeˇc eme (4.7) a ´ysledek dˇel´ıme 15. Tak dos aneme me odu
F3, k e ´a je p o z olen´e hde ino ´ana pˇ edpisem
F3(h) := 16F2(h
2)−F2(h)
15 =a0+a(3)
3h6+... (4.9)
pˇ iˇcemˇz |a(3)
j|<|a(2)
j|<|aj|,j= 3,4,.... Vˇsimnˇe e si, abychom mohli ypoˇc´ı a F2(h
2),
mus´ıme nejdˇ ´ı e u ˇci F(h
4).
Tak o m˚uˇzeme pok aˇco a a z´ısk´a a s ´ale lepˇs´ı me ody, p o k e ´e
Fi+1(h) = 4iFi(h
2)−Fi(h)
4i−1=a0+a(i+1)
i+1 h2i+2 +. . . , i = 1,2,... (4.10)
a kde F1(h) = F(h). P o koe icien y oz oje pˇ i om pla ´ı |a(i+1)
j|<|aj|,j=i+1, i+2,....
P o oˇze Fi(h)−F(0) = a(i)
ih2i+..., ˇ ekneme, ˇze Fi(h) je ap oximace F(0) ˇ ´adu h2i.
66
V´ypoˇce lze pˇ ehlednˇe uspoˇ ´ada do abulky
F1(h)
F1(h
2)F2(h)
F1(h
4)F2(h
2)F3(h)
F1(h
8)F2(h
4)F3(h
2)F4(h)
F1(h
16 )F2(h
8)F3(h
4)F4(h
2)F5(h)
.
.
..
.
..
.
..
.
..
.
....
⇐⇒
T00
T10 T11
T20 T21 T22
T30 T31 T32 T33
T40 T41 T42 T43 T44
.
.
..
.
..
.
..
.
..
.
....
Tab. 4.1 Richa dsono a ex apolace, Tsi =Fi+1(h/2s−i)
Tabulku yplˇnujeme po ˇ ´adc´ıch. P ky abulky oznaˇc´ıme jako Tsi, kde s= 0,1,...
je ˇ ´adko ´y index a i= 0,1,...s je index sloupco ´y. P ek Ts0 p n´ım sloupci abulky
ypoˇc eme pomoc´ı z´akladn´ı me ody F=F1,
Ts0=F(h/2s), s = 0,1,... , (4.11)
a dalˇs´ı p ky om o ˇ ´adku poˇc´ı ´ame e shodˇe s (4.10) podle pˇ edpisu
Tsi := 4iTs,i−1−Ts−1,i−1
4i−1=Ts,i−1+Ts,i−1−Ts−1,i−1
4i−1, i = 1,2,...,s. (4.12)
V´ypoˇce ukonˇc´ıme a Tsi po aˇzujeme za dos a eˇcnˇe pˇ esnou ap oximaci F(0), pokud
|Tsi −Ts,i−1|<max(ε |Tsi|, εa),(4.13)
kde ε je poˇzado an´a ela i n´ı pˇ esnos a εapoˇzado an´a pˇ esnos absolu n´ı.
Pˇ ´ıklad 4.1. Richa dsono u ex apolaci pouˇzijeme p o zpˇ esnˇen´ı ´ypoˇc u de i ace podle
o mule (4.3b). Jes liˇze m´a unkce dos a eˇcn´y poˇce spoji ´ych de i ac´ı, pak
F(h) := (x+h)− (x−h)
2h= ′(x) + (3)(x)
3! h2+ (5)(x)
5! h4+. . . , (4.14)
akˇze F(h) je a u (4.5).
Poˇc´ı ejme de i aci unkce (x) = cos xp o x= 1. Z ol´ıme napˇ . h= 0,8 a ´ypoˇce
ukonˇc´ıme, kdyˇz bude splnˇena podm´ınka (4.13) p o ε =εa= 10−5. V n´asleduj´ıc´ı abulce
znaˇc´ıme hs=h/2s, p ky Ts0poˇc´ı ´ame ze z ahu
Ts0=cos(1 + hs)−cos(1 −hs)
2hs
,
p ky Ts1aTs2 dalˇs´ıch sloupc´ıch poˇc´ı ´ame podle (4.12). ˇ
C´ısla abulce jsou zaok ouh-
lena na 6 ci e . P o oˇze |T32 −T31|<10−5, po aˇzujeme T32 =−0,841471 za pˇ ibliˇznou
hodno u ′(1). Pˇ esn´a hodno a ′(1) = −sin(1) .
=−0,84147098, akˇze T32 m´a ˇsechny
67
s hsTs0Ts1Ts2
0 0,8−0,754543
1 0,4−0,819211 −0,840766
2 0,2−0,835872 −0,841426 −0,841470
3 0,1−0,840069 −0,841468 −0,841471
ci y pla n´e. 
Pozn´amka. Richa dsono u ex apolaci lze apliko a na z´akladn´ı me odu F ak´e pˇ ´ıpadˇe,
kdyˇz m´a unkce F(h) obecn´y oz oj
F(h) = a0+a1hp1+a2hp2+a3hp3+... (4.5’)
kde 1 ≤p1< p2< p3< . . . jsou pˇ i ozen´a ˇc´ısla. Pˇ esnˇejˇs´ı me odu Fi+1 om pˇ ´ıpadˇe
de inujeme pˇ edpisem
Fi+1(h) = 2piFi(h
2)−Fi(h)
2pi−1=a0+a(i+1)
i+1 hpi+1 +. . . , i = 1,2,... , (4.10’)
aTsi poˇc´ı ´ame podle
Tsi := 2piTs,i−1−Ts−1,i−1
2pi−1=Ts,i−1+Ts,i−1−Ts−1,i−1
2pi−1, i = 1,2,...,s. (4.12’)
P o oˇze Fi(h)−F(0) = a(i)
ihpi+..., ˇ ekneme, ˇzeFi(h) je ap oximace F(0) ˇ ´adu hpi. P o
pi= 2idos aneme dˇ ´ı e u aˇzo an´y pˇ ´ıpad, iz (4.5), (4.10) a (4.12). 
Pˇ ´ıklad 4.2. Richa dsono ou ex apolac´ı zpˇ esn´ıme ´ypoˇce de i ace podle o mule (4.2a).
Z Taylo o y ˇe y dos aneme
F(h) := (x+h)− (x)
h= ′(x) + (2)(x)
2! h+ (3)(x)
3! h2+. . . , (4.15)
coˇz odpo ´ıd´a (4.5’) p o pi=i. Poˇc´ı a budeme s ejnou ´ulohu jako pˇ ´ıkladu 4.1. Ten-
ok ´a poˇzado anou pˇ esnos dos´ahneme aˇz p o T44. Richa dsono a ex apolace je m´enˇe
s hsTs0Ts1Ts2Ts3Ts4
0 0,8−0,959381
1 0,4−0,925838 −0,892295
2 0,2−0,889723 −0,853608 −0,840712
3 0,1−0,867062 −0,844401 −0,841332 −0,841421
4 0,05 −0,854625 −0,842188 −0,841451 −0,841468 −0,841471
´uˇcinn´a: za ´ımco p o o muli (4.3b) je T32 ap oximace ˇ ´adu h6, p o o muli (4.2a) je T44
ap oximace ˇ ´adu h5a k dosaˇzen´ı poˇzado an´e pˇ esnos i bylo ˇ eba z oli menˇs´ı hs.
68
4.3. Nume ick´e in eg o ´an´ı
C´ılem oho o ods a ce je pˇ ibliˇzn´y ´ypoˇce in eg ´alu I( ) := Rb
a (x) dx. Exis uje
nˇekolik d˚u od˚u, p oˇc en o in eg ´al nepoˇc´ı ´ame pˇ esnˇe, napˇ ´ıklad
a) in eg ´al I( ) neum´ıme spoˇc´ı a analy ick´ymi me odami;
b) analy ick´y ´ypoˇce je pˇ ´ıliˇs p acn´y;
c) unkce (x) je d´ana jen abulkou.
Za pˇ ibliˇznou hodno u in eg ´alu I( ) po aˇzujeme in eg ´al Q( ) := I(ϕ), kde ϕ(x) je
hodn´a ap oximace unkce (x). Pˇ edpis Q( ) p o pˇ ibliˇzn´y ´ypoˇce in eg ´alu se naz´y ´a
k ad a u n´ı o mule. Rozd´ıl I( )−Q( ) oznaˇc´ıme R( ) a naz eme (disk e izaˇcn´ı) chybou
k ad a u n´ı o mule, edy
I( ) = Q( ) + R( ).
ˇ
Rekneme, ˇze k ad a u n´ı o mule je ˇ ´adu , kdyˇz in eg uje pˇ esnˇe polynomy s upnˇe
a polynomy s upnˇe + 1 uˇz pˇ esnˇe nein eg uje, j. kdyˇz R(xk) = 0 p o k= 0,1,..., ,
aR(x +1)6= 0.
ˇ
R´ad o mule s aˇc´ı o ˇeˇ i na in e alu ha, bi=h0,1i. Sku eˇcnˇe, pomoc´ı ans o mace
x=a+ (b−a) dos aneme Rb
axkdx= (b−a)R1
0g( ) d , kde g( ) = (a+ (b−a))kje polynom
s upnˇe k p omˇenn´e . P o o kdyˇz o mule in eg uje pˇ esnˇe polynomy s upnˇe k≤ na
in e alu h0,1i, in eg uje pˇ esnˇe ak´e polynomy s upnˇe na in e alu ha, bi.
4.3.1. Z´akladn´ı o mule
dos aneme in eg ac´ı in e polaˇcn´ıho polynomu.
Obd´eln´ıko ´a o mule. Kdyˇz P0(x) = (1
2(a+b)) je polynom s upnˇe 0, j. kons an a
o n´a hodno ˇe unkce e s ˇ edu 1
2(a+b) in e alu ha, bi, pak odpo ´ıdaj´ıc´ı o mule
QM( ) := Zb
a
P0(x) dx= (b−a) a+b
2.(4.16)
N´aze o mule yjadˇ uje sku eˇcnos , ˇze p o (1
2(a+b)) >0 je QM( ) obsah obd´eln´ıka
o s an´ach d´elky b−aa (1
2(a+b)). Obd´eln´ıko ´a o mule (4.16) se anglicky psan´e
li e a uˇ e oznaˇcuje jako midpoin ule, od ud index M. Obd´eln´ıko ´a o mule je ˇ ´adu 1:
na in e alu h0,1ije QM(1) = 1 = I(1), QM(x) = 1
2=I(x) a QM(x2) = 1
46=1
3=I(x2).
P o chybu RM( ) obd´eln´ıko ´e o mule lze za pˇ edpokladu, ˇze ∈C2ha, bi, od odi
RM( ) = 1
24 ′′(ξ)(b−a)3,kde ξ∈(a, b) (4.17)
je nˇejak´y (bl´ıˇze neu ˇcen´y) bod in e alu (a, b).
Lichobˇeˇzn´ıko ´a o mule. Jako P1(x) oznaˇc´ıme line´a n´ı polynom p och´azej´ıc´ı body
[a, (a)] a [b, (b)]. In eg ac´ı P1(x) na in e alu ha, biobd ˇz´ıme
QT( ) := Zb
a
P1(x) dx=b−a
2[ (a) + (b)] .(4.18)
69

a (a+b)/2 b a b a (a+b)/2 b
Ob . 4.2: Obd´eln´ıko ´a, lichobˇeˇzn´ıko ´a a Simpsono a o mule
N´aze o mule yjadˇ uje sku eˇcnos , ˇze p o (a)>0, (b)>0 je QT( ) obsah li-
chobˇeˇzn´ıka, jehoˇz o nobˇeˇzn´e s any maj´ı d´elky (a), (b) a jehoˇz ´yˇska je o na b−a. In-
dex Tje p n´ı p´ısmeno anglick´eho sl˚u ka apezoid, ˇcesky lichobˇeˇzn´ık. Lichobˇeˇzn´ıko ´a o -
mule je ˇ ´adu 1: line´a n´ı polynom in eg uje pˇ esnˇe, k ad a ick´y nikoli . Kdyˇz ∈C2ha, bi,
pak p o chybu lichobˇeˇzn´ıko ´e o mule pla ´ı
RT( ) = −1
12 ′′(ξ)(b−a)3,kde ξ∈(a, b).(4.19)
Vˇsimnˇe e si:
a) Pokud se d uh´a de i ace ′′(x) unkce (x) na in e alu ha, bipˇ ´ıliˇs nemˇen´ı, pak je
absolu n´ı hodno a |RT( )|chyby lichobˇeˇzn´ıko ´e omule pˇ ibliˇznˇe d ak ´a ˇe ˇs´ı neˇz
absolu n´ı hodno a |RM( )|chyby o mule obd´eln´ıko ´e.
b) Pokud d uh´a de i ace ′′(x) unkce (x) nemˇen´ı na in e alu ha, biznam´enko, j. je-
li unkce (x) poˇ ´ad kon exn´ı nebo konk´a n´ı, pak znam´enko chyby lichobˇeˇzn´ıko ´e
o mule je opaˇcn´e neˇz znam´enko chyby o mule obd´eln´ıko ´e. Za ˇech o okolnos ´ı
pˇ esn´a hodno a I( ) in eg ´alu leˇz´ı in e alu, jehoˇz k ajn´ı body jsou hodno y
QM( ) a QT( ).
Simpsono a o mule. In eg ac´ı k ad a ick´eho in e polaˇcn´ıho polynomu P2(x) p och´a-
zej´ıc´ıho body [a, (a)], [1
2(a+b), (1
2(a+b))] a [b, (b)] dos aneme
QS( ) = Zb
a
P2(x) dx=b−a
6 (a) + 4 a+b
2+ (b).(4.20)
Simpsono a o mule je ˇ ´adu 3. O ˇeˇ e! (S aˇc´ı po o na QS(xk) a I(xk) na in e alu h0,1i
pos upnˇe p o k= 0,1,2,3,4.) Kdyˇz ∈C4ha, bi, p o chybu pla ´ı
RS( ) = −1
90 (4)(ξ)b−a
25
,kde ξ∈(a, b).(4.21)
Booleo a o mule znikne in eg ac´ı in e polaˇcn´ıho polynomu P4(x), jehoˇz uzly jsou,
k omˇe konco ´ych bod˚u a,b, ak´e s ˇ ed 1
2(a+b) in e alu ha, bia body a+1
4(b−a)
70
ab−1
4(b−a) leˇz´ıc´ı jedn´e ˇc inˇe a e ˇ ech ˇc in´ach in e alu ha, bi. Booleo a
o mule
QB( ) = b−a
90 7 (a) + 32 3a+b
4+ 12 a+b
2+ 32 a+ 3b
4+ 7 (b)
je ˇ ´adu 5 (o ˇeˇ e!). Pokud ∈C6ha, bi, p o chybu pla ´ı
RB( ) = −8
945 (6)(ξ)b−a
47
,kde ξ∈(a, b).
4.3.2. Sloˇzen´e o mule
Abychom dos ali dos a eˇcnˇe pˇ esnou ap oximaci in eg ´alu I( ), ozdˇel´ıme in e al
ha, bina k a ˇs´ı podin e aly a na kaˇzd´em z nich pouˇzijeme nˇek e ou ze z´akladn´ıch o -
mul´ı. Omez´ıme se na pˇ ´ıpad, kdy z´akladn´ı o mule na podin e alech jsou ˇzdy s ejn´e, a o
bud’ o obd´eln´ıko ´e nebo lichobˇeˇzn´ıko ´e nebo Simpsono y (ses a en´ı sloˇzen´e Booleo y o -
mule ponech´a ´ame ˇc en´aˇ i jako c iˇcen´ı). Budeme u aˇzo a o nomˇe n´e (= ek idis an n´ı)
dˇelen´ı
a=x0< x1<···< xn=b, kde xi=a+ih,h= (b−a)/n ai= 0,1,...,n. (4.22)
Sloˇzenou o muli na dˇelen´ı (4.22) budeme znaˇci pomoc´ı ho n´ıho indexu n. D´elka hse
naz´y ´a k ok dˇelen´ı.
Sloˇzenou obd´eln´ıko ou o muli dos aneme souˇc em jednoduch´ych obd´eln´ıko ´ych o -
mul´ı h (xi−1+1
2h) na podin e alech hxi−1, xii. V´ysledkem je sloˇzen´a o mule
Qn
M( ) := h x0+1
2h+ x1+1
2h+···+ xn−1+1
2h.(4.23)
Chybu Rn
M( ) dos aneme jako souˇce d´ılˇc´ıch chyb 1
24 ′′(ξi)h3na hxi−1, xii:
Rn
M( ) = 1
24h3 ′′(ξ1) + 1
24h3 ′′(ξ2) + ···+1
24h3 ′′(ξn) =
1
24h2b−a
n[ ′′(ξ1) + ′′(ξ2) + ···+ ′′(ξn)] .
Ze spoji os i ′′ plyne, ˇze a i me ick´y p ˚umˇe [ ′′(ξ1) + ′′(ξ2) + ···+ ′′(ξn)]/n d uh´ych
de i ac´ı je o en d uh´e de i aci ′′(ξ) nˇejak´em bodˇe ξ∈(a, b). P o chybu Rn
M( ) sloˇzen´e
obd´eln´ıko ´e o mule edy pla ´ı
Rn
M( ) = b−a
24 ′′(ξ)h2,kde ξ∈(a, b).(4.24)
Sloˇzen´a lichobˇeˇzn´ıko ´a o mule znikne souˇc em jednoduch´ych lichobˇeˇzn´ıko ´ych o -
mul´ı 1
2h[ (xi−1) + (xi)] na podin e alech hxi−1, xii. V´ysledkem je o mule
Qn
T( ) := h1
2 (x0) + (x1) + ···+ (xn−1) + 1
2 (xn).(4.25)
71
x0x1x2xi−1 xixi+1 xn
x0x1x2xi−1 xixi+1 xn
Ob . 4.3: Sloˇzen´a obd´eln´ıko ´a a lichobˇeˇzn´ıko ´a o mule
Chybu Rn
T( ) dos aneme jako souˇce chyb −1
12 ′′(ξi)h3na podin e alech hxi−1, xii. Po
jednoduch´e ´up a ˇe obd ˇz´ıme
Rn
T( ) = −b−a
12 ′′(ξ)h2,kde ξ∈(a, b).(4.26)
V MATLABu lze pouˇz´ı unkci apz.
Sloˇzenou Simpsono u o muli dos aneme p o sud´y poˇce nd´ılk˚u ak, ˇze seˇc eme
jednoduch´e Simpsono y o mule na in e alech hx0, x2i,hx2, x4i,...,hxn−2, xnid´elky 2h:
Qn
S( ) :=2h
6[ (x0) + 4 (x1) + (x2)] + 2h
6[ (x2) + 4 (x3) + (x4)] + ···+
2h
6[ (xn−4) + 4 (xn−3) + (xn−2)] + 2h
6[ (xn−2) + 4 (xn−1) + (xn)] .
Od ud edy
Qn
S( ) := h
3[ (x0)+4 (x1)+2 (x2)+4 (x3)+···+2 (xn−2)+4 (xn−1)+ (xn)] .(4.27)
72
Chyba Rn
S( ) je souˇc em chyb na podin e alech:
Rn
S( ) = −1
90h5 (4)(ξ2)−1
90h5 (4)(ξ4)−...−1
90h5 (4)(ξn) =
−1
90h4b−a
22
n (4)(ξ2) + (4)(ξ4) + ···+ (4)(ξn).
Kdyˇz a i me ick´y p ˚umˇe ˇc ´ych de i ac´ı ( j. ´y az e sloˇzen´e z´a o ce) nah ad´ıme ˇcle-
nem (4)(ξ), dos aneme
Rn
S( ) = −b−a
180 (4)(ξ)h4,kde ξ∈(a, b).(4.28)
Jak dos´ahnou poˇzado an´e pˇ esnos i. Vy s ´a ´a o ´azka jak zajis i , aby chyba, k e ´e
se pˇ i nume ick´em ´ypoˇc u in eg ´alu dopus ´ıme, byla menˇs´ı neˇz zadan´a ole ance ε. Ve
zo c´ıch (4.24), (4.26) a (4.28) bohuˇzel ys upuje bl´ıˇze neu ˇcen´e ˇc´ıslo ξ, o nˇemˇz ´ıme jen
o, ˇze leˇz´ı nˇekde in e alu (a, b). Kdyˇz oznaˇc´ıme
M2= max
x∈ha,bi| ′′(x)|, M4= max
x∈ha,bi| (4)(x)|,
pak chyby m˚uˇzeme odhadnou podle z ahu
|Rn
M( )| ≤ b−a
24 M2h2p o sloˇzenou obd´eln´ıko ou o muli, (4.24’)
|Rn
T( )| ≤ b−a
12 M2h2p o sloˇzenou lichobˇeˇzn´ıko ou o muli, (4.26’)
|Rn
S( )| ≤ b−a
180 M4h4p o sloˇzenou Simpsono u o muli. (4.28’)
Poˇce d´ılk˚u n= (b−a)/h pak lze u ˇci ak, aby |Rn
M( )| ≤ εpopˇ . |Rn
T( )| ≤ εnebo
|Rn
S( )| ≤ ε. Tak o s ano en´y poˇce d´ılk˚u je ˇsak zp a idla pˇ ehnanˇe elk´y. To je d˚usledek
oho, ˇze jsme odhadech chyb nah adili de i aci bl´ıˇze neu ˇcen´em bodˇe maximem ´e o
de i ace na cel´em in e alu ha, bi.
Pˇ ´ıklad 4.3. U ˇceme poˇce d´ılk˚u n ak, abychom ypoˇc´ı ali Rπ/2
0excos xdxs chybou
nej ´yˇse 10−4pomoc´ı sloˇzen´e obd´eln´ıko ´e, lichobˇeˇzn´ıko ´e a Simpsono y o mule. Pˇ esn´a
hodno a Rπ/2
0excos xdx=1
2ex(cos x+ sin x)π/2
0
.
= 1,905239.
P o (x) = excos xje ′′(x) = −2exsin xa edy M2≤2eπ/2. V pˇ ´ıpadˇe obd´eln´ıko ´e
o mule pomoc´ı (4.24’) od od´ıme:
|Rn
M( )| ≤ π/2
24 2eπ/2π/2
n2
≤10−4=⇒n≥125 .
P o edeme-li ´ypoˇce s ´ım o npodle (4.23), dos aneme Q125
M( ).
= 1,905277, akˇze
sku eˇcn´a chyba je asi 3,8·10−5. Ces ou pokus˚u se uk´azalo, ˇze p o dosaˇzen´ı poˇzado an´e
ole ance s aˇc´ı z´ı n= 78.
73
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2
−6
−4
−2
0
2
4
x
y
y = 4sinx−x3−1
Ob . 5.1: G a unkce 4 sin x−x3−1
S ˇ ed xk+1 in e alu (ak, bk) ap oximuje koˇ en x∗s chybou
|xk+1 −x∗| ≤ 1
2(bk−ak) = 2−k−1(b0−a0).(5.2)
P o k→ ∞ zˇ ejmˇe |Ik| → 0 a xk→x∗.
Pˇ ´ıklad 5.2. Me odu bisekce aplikujeme na o nici z pˇ ´ıkladu 5.1. Jako poˇc´a eˇcn´ı z o-
k akbkxk+1 (xk+1)
0 1 2 1,5<0
1 1 1,5 1,25 >0
2 1,25 1,5 1,375 >0
3 1,375 1,5 1,4375 <0
4 1,375 1,4375 1,40625 >0
5 1,40625 1,4375 1,421875
l´ıme in e al (a0, b0) = (1,2). Pˇ ipomeˇn-
me, ˇze (1) >0, (2) <0. P o o ak´e
(ak)≥0, (bk)≤0 p o kaˇzd´e k. Posloup-
nos in e al˚u zaznamen´a ´ame do abul-
ky. Po pˇe i k oc´ıch m´a in e al (a5, b5)
d´elku 2−5= 0,03125 a x6= 1,421875
ap oximuje koˇ en s chybou nepˇ esahuj´ıc´ı
2−6= 0,015625. 
Me oda bisekce kon e guje pomalu: p o oˇze 10−1.
= 2−3,32, zpˇ esnˇen´ı o jednu dekadic-
kou ci u yˇzaduje p ˚umˇe u 3,32 k oku. Vˇsimnˇe e si, ˇze ychlos kon e gence yj´adˇ en´a
z ahem (5.2) ˚ubec nez´a is´ı na unkci (x). To p o o, ˇze jsme yuˇz´ı ali pouze znam´enka
unkˇcn´ıch hodno . Kdyˇz y o hodno y (a pˇ ´ıpadnˇe ak´e hodno y de i ac´ı (x)) yuˇzijeme
e ek i nˇeji, m˚uˇzeme dos´ahnou pods a nˇe ychlejˇs´ı kon e gence. Tako ´e zpˇ esˇnuj´ıc´ı me o-
dy ˇsak kon e guj´ı pouze ehdy, kdyˇz p o nˇe z ol´ıme dos a eˇcnˇe dob ou poˇc´a eˇcn´ı ap o-
ximaci. Vhodn´a poˇc´a eˇcn´ı ap oximace b´y ´a ˇcas o u ˇcena p ´a ˇe me odou bisekce.
5.2. Zpˇ esˇnuj´ıc´ı me ody
Snad nejzn´amˇejˇs´ı mezi nimi je
New ono a me oda nebo-li me oda eˇcen. Jak je u i e aˇcn´ıch me od z ykem, yjdeme
z poˇc´a eˇcn´ı ap oximace x0a pos upnˇe poˇc´ı ´ame x1, x2,... zp˚usobem, k e ´y si ed’ ys ˇe -
l´ıme.
Pˇ edpokl´adejme, ˇze zn´ame xka m´ame u ˇci lepˇs´ı ap oximaci xk+1. Udˇel´ame o ak, ˇze
bodem [xk, (xk)] edeme eˇcnu ke kˇ i ce y= (x) a p ˚useˇc´ık eˇcny s osou xpo aˇzujeme
80

za xk+1. Do o nice eˇcny
y= (xk) + ′(xk)(x−xk)
edy dosad´ıme y:= 0, ypoˇc eme xa poloˇz´ıme xk+1 := x. Tak dos aneme pˇ edpis
xk+1 =xk− (xk)
′(xk).(5.3)
V´ypoˇce ukonˇc´ıme a xk+1 po aˇzujeme za dos a eˇcnˇe pˇ esnou ap oximaci koˇ ene, pokud
|xk+1 −xk| ≤ ε , pˇ ´ıpadnˇe |xk+1 −xk| ≤ ε|xk|nebo | (xk+1)| ≤ ε , (5.4)
kde εje poˇzado an´a pˇ esnos . T´ım sice nen´ı za uˇceno, ˇze ak´e |xk+1 −x∗| ≤ ε, je o ale
ob ykl´y zp˚usob, pomoc´ı nˇehoˇz i e ace ukonˇc´ıme. Ta o z . s op k i ´e ia jsou hodn´a i p o
dalˇs´ı me ody, k e ´e om o ods a ci u edeme.
x0
x1
x2
x3
(x)
y=0
[xi, (xi)]
(y−yi)/(x−xi) = ’(xi)
Ob . 5.2: New ono a me oda
Pˇ ´ıklad 5.3. New ono ou me odou u ˇc´ıme kladn´y koˇ en o nice z pˇ ´ıkladu 5.1. Z ol´ıme
x0= 2. V´ypoˇce ukonˇc´ıme, kdyˇz | (xk)|<10−5. Posledn´ı sloupec yˇzaduje znalos pˇ es-
k xk (xk) ′(xk) (xk)/ ′(xk)xk−x∗
0 2 −5,362810 −13,66459 0,392460 0,563550
1 1,607540 −1,156877 −7,899490 0,146450 0,171089
2 1,461090 −0,143158 −5,966406 0,023994 0,024640
3 1,437096 −0,003653 −5,662524 0,000645 0,000646
4 1,436451 −0,000003 0,000000
n´eho ˇ eˇsen´ı. To z´ısk´ame p o eden´ım jeˇs ˇe jednoho k oku New ono y me ody. D´a se uk´a-
za , ˇze x∗.
=x5= 1,43645032 m´a ˇsechny ci y pla n´e. Poˇzado an´a pˇ esnos byla edy
dosaˇzena e ˇc ´em k oku, x4.
= 1,43645 m´a ˇsechny ci y pla n´e. 
81
Kon e gence New ono y me ody. Nech
’ek=xk−x∗je chyba k- ´em k oku.
Uk´aˇzeme si, jak sou is´ı s chybou ek+1 k oku n´asleduj´ıc´ım. Z Taylo o a oz oje (x∗)
okolo xkdos aneme
0 = (x∗) = (xk) + (x∗−xk) ′(xk) + 1
2(x∗−xk)2 ′′(ξ),
kde ξje nˇejak´y bl´ıˇze neu ˇcen´y bod in e alu, jehoˇz k ajn´ı body jsou xkax∗. Kdyˇz o nici
dˇel´ıme ′(xk), dos aneme
−1
2(x∗−xk)2 ′′(ξ)
′(xk)= (xk)
′(xk)+ (x∗−xk) = x∗−xk− (xk)
′(xk)=x∗−xk+1 ,
akˇze m´ame
ek+1 =1
2
′′(ξ)
′(xk)e2
k,(5.5)
a kdyˇz xk→x∗, pak
ek+1
e2
k−→ C , kde C=1
2
′′(x∗)
′(x∗).
P o oˇze chyba ek+1 je ´umˇe n´a d uh´e mocninˇe chyby ek, ˇ ´ık´ame, ˇze New ono a me oda
kon e guje k ad a icky nebo ak´e, ˇze je d uh´eho ˇ ´adu. U ed’me si pˇ esnˇejˇs´ı de inici:
Nech
’x0, x1, x2,... je posloupnos , k e ´a kon e guje k x∗aek=xk−x∗. Kdyˇz exis uje
ˇc´ıslo pa kons an a C6= 0 ako ´a, ˇze
lim
k→∞ |ek+1|
|ek|p=C , (5.6)
pak pse naz´y ´a ˇ ´ad kon e gence posloupnos i a Cje chybo ´a kons an a. Speci´alnˇe ˇ ´ık´ame,
ˇze
kon e gence je
line´a n´ı,
supe line´a n´ı,
k ad a ick´a,
kdyˇz
p= 1 aC < 1,
p > 1,
p= 2 .
ˇ
Rekneme, ˇze dan´a me oda je ˇ ´adu p, jes liˇze ˇsechny kon e gen n´ı posloupnos i z´ıskan´e
ou o me odou maj´ı ˇ ´ad kon e gence ˇe ˇs´ı nebo o n´y pa nejm´enˇe jedna z ˇech o posloup-
nos ´ı m´a ˇ ´ad kon e gence o n´y pˇ esnˇe p.
V bl´ızkos i koˇ ene pla ´ı: ˇc´ım yˇsˇs´ı ˇ ´ad p, ´ım ychlejˇs´ı kon e gence, nebo
’
|ek+1| ≈ C|ek|p,
akˇze kdyˇz |ek|je mal´e, pak |ek+1|je ´ım menˇs´ı, ˇc´ım je p ˇe ˇs´ı.
V´ıme uˇz, ˇze kdyˇz New ono a me oda kon e guje, pak ychlos kon e gence xk→x∗
je alespoˇn k ad a ick´a (p o nˇek e ´e unkce m˚uˇze b´y i yˇsˇs´ı). Zb´y ´a jeˇs ˇe zodpo ˇedˇe
o ´azku, za jak´ych podm´ınek je za uˇceno, ˇze kon e gence ˚ubec nas ane. Ukaˇzme si o.
82
Pˇ edpokl´adejme, ˇze nˇejak´em okol´ı Ikoˇ ene pla ´ı
1
2
′′(y)
′(x)≤mp o ˇsechna x, y ∈I .
Kdyˇz xk∈I, pak z (5.5) plyne |ek+1| ≤ m|ek|2nebo-li |mek+1| ≤ |mek|2. Opako ´an´ım
´e o ´u ahy dos aneme
|mek+1| ≤ |mek|2≤ |mek−1|4≤ |mek−2|8≤ |mek−3|16 ≤ ··· ≤ |me0| ,kde = 2k+1.
Kdyˇz pla ´ı |me0|<1, pak jis ˇe |ek+1| → 0 a edy xk+1 →x∗. Dok´azali jsme edy, ˇze
New ono a me oda ˇzdy kon e guje za pˇ edpokladu, ˇze poˇc´a eˇcn´ı ap oximaci z ol´ıme dos a-
eˇcnˇe bl´ızko ke koˇ enu.
Dob ou poˇc´a eˇcn´ı ap oximaci x0m˚uˇzeme z´ıska napˇ . me odou bisekce. Vhodn´ym
spojen´ım me ody bisekce a New ono y me ody lze ses oji kombino anou me odu, k e ´a
ˇzdy kon e guje, iz napˇ . p ocedu a sa e [18]. V bl´ızkos i koˇ ene se pˇ i om upla n´ı
jen New ono a me oda, akˇze kon e gence je ychl´a.
Pomoc´ı n´aˇc ku snadno o ˇeˇ ´ıme, ˇze New ono a me oda kon e guje, kdyˇz jsou splnˇeny
z . Fou ie o y podm´ınky:
a) ∈C2ha, bia pˇ i om (a) (b)<0;
b) ′a ′′ nemˇen´ı na in e alu ha, biznam´enko a ′(x)6= 0 p o kaˇzd´e x∈ ha, bi;
c) jako x0 ol´ıme en z bod˚u a, b, nˇemˇz je (x0) ′′(x0)>0.
P ak ick´y ´yznam ˇsak Fou ie o y podm´ınky nemaj´ı, nebo
’p o elk´e b−aob ykle y o
podm´ınky bud’ o nepla ´ı nebo je neum´ıme snadno o ˇeˇ i .
Me oda seˇcen. V kaˇzd´em k oku New ono y me ody mus´ıme poˇc´ı a hodno u (xk) a de-
i aci ′(xk). Kdyˇz zo ec p o ´ypoˇce de i ace nem´ame k dispozici, nebo kdyˇz n´aklady
spojen´e s ´ypoˇc em de i ace jsou ysok´e, m˚uˇzeme de i aci ap oximo a pod´ılem
′(xk)≈ (xk)− (xk−1)
xk−xk−1
.
Tak dos aneme me odu seˇcen: zad´ame d ˇe poˇc´a eˇcn´ı ap oximace x0,x1a poˇc´ı ´ame
x2, x3,... podle pˇ edpisu
xk+1 =xk−xk−xk−1
(xk)− (xk−1) (xk).(5.7)
N´aze me ody ych´az´ı z jej´ı geome ick´e in e p e ace: xk+1 je x-o ´a souˇ adnice p ˚useˇc´ıku
pˇ ´ımky p och´azej´ıc´ı body [xk−1, (xk−1)] a [xk, (xk)] s osou x:
y= (xk) + (xk)− (xk−1)
xk−xk−1
(x−xk) = 0 =⇒x=xk+1 .
P o oˇze a o pˇ ´ımka p o ´ın´a g a unkce , je o seˇcna, od ud me oda seˇcen.
83
x0
x1
x2
x3
x4
(x)
y=0
[xi, (xi)]
(y−yi)/(x−xi) = (yi−yi−1)/(xi−xi−1)
Ob . 5.3: Me oda seˇcen
Vˇsimnˇe e si, ˇze kaˇzd´em k oku yˇc´ıslujeme hodno u unkce jen jednou: ypoˇc eme
(xk), hodno u (xk−1) pˇ e ezmeme z pˇ edchoz´ıho k oku.
D´a se od odi , ˇze ychlos kon e gence me ody seˇcen je ˇ ´adu p=1
2(1 + √5) ≈1,618,
edy ponˇekud niˇzˇs´ı neˇz u New ono y me ody. ˇ
C´ıslo τ= (√5−1)/2≈0,618 je z . pomˇe
zla ´eho ˇ ezu. To o magick´e ˇc´ıslo se zno u obje ´ı ods a ci 6.1, kde si o nˇem ˇ ekneme
ochu ´ıc ( iz pozn´amka o zla ´em ˇ ezu).
Pˇ ´ıklad 5.4. Me odou seˇcen u ˇc´ıme kladn´y koˇ en o nice z pˇ ´ıkladu 5.1. Z ol´ıme x0= 1,
k xk (xk)xk−x∗
0 1 1,365884 −0,436450
1 2 −5,362810 0,563550
2 1,202994 0,991513 −0,233456
3 1,327357 0,543420 −0,109094
4 1,478177 −0,246970 0,041726
5 1,431051 0,030349 −0,005400
6 1,436208 0,001370 −0,000242
7 1,436452 −0,000008 0,000001
x1= 2. V´ypoˇce ukonˇc´ıme, kdyˇz bude
| (xk)|<10−5. Aˇz do ˇc ´eho k oku
( ´ypoˇce x5) je kon e gence pomˇe nˇe po-
mal´a. Tep e posledn´ıch d ou k oc´ıch se
plnˇe upla nila ychl´a kon e gence me ody
seˇcen. 
Me oda seˇcen za uˇcenˇe kon e guje, pokud z ol´ıme s a o ac´ı hodno y x0ax1dos a-
eˇcnˇe bl´ızko ke koˇ enu x∗. To lze zajis i napˇ . me odou bisekce. Dalˇs´ı me odou, jak z´ıska
dob ´e s a o ac´ı ap oximace, je a ian a me ody seˇcen zn´am´a jako
Me oda egula alsi. Poˇc´a eˇcn´ı ap oximace x0ax1se ol´ı ak, aby (x0) (x1)<0. No ´a
ap oximace xk+1 se opˇe z´ısk´a jako p ˚useˇc´ık seˇcny s osou x. Seˇcna ˇsak en ok ´a spojuje
bod [xk, (xk)] s bodem [xℓ, (xℓ)], kde ℓje nej ˇe ˇs´ı index, p o k e ´y (xk) (xℓ)<0.
V´ypoˇce edy p ob´ıh´a podle zo ce
xk+1 =xk−xk−xℓ
(xk)− (xℓ) (xk), k = 1,2,.... (5.8)
84
Pˇ i om p o k= 1 je ℓ= 0, a po ´ypoˇc u xk+1 u ˇc´ıme index ℓ ak o:
kdyˇz (xk+1) (xℓ)>0, pak ℓ=k, opaˇcn´em pˇ ´ıpadˇe se ℓnemˇen´ı.
V´yhodou me ody egula alsi je o, ˇze podobnˇe jako me oda bisekce ˇzdy kon e guje:
in e al Ik, jehoˇz konco ´e body jsou xkaxℓ, obsahuje koˇ en. Na ozd´ıl od me ody bisekce
ˇsak d´elka in e alu Iknekon e guje k nule. Rychlos kon e gence me ody egula alsi je
jen line´a n´ı. Me odu egula alsi (podobnˇe jako me odu bisekce) p o o pouˇz´ı ´ame pouze
p o z´ısk´an´ı dob ´e poˇc´a eˇcn´ı ap oximace, pak pˇ ech´az´ıme na ychlejˇs´ı me odu.
x0
x1
x2
x3
x4
Ob . 5.4: Regula alsi
Pˇ ´ıklad 5.5. Me odou egula alsi u ˇc´ıme kladn´y koˇ en o nice z pˇ ´ıkladu 5.1. Z ol´ıme
k ℓ xℓxk (xk)xk−x∗
0 1 1,365884 −0,436450
1 0 1 2 −5,362810 0,563550
2 1 2 1,202994 0,991513 −0,233456
3 1 2 1,327357 0,543420 −0,109094
4 1 2 1,389245 0,253012 −0,047205
5 1 2 1,416762 0,108896 −0,019688
6 1 2 1,428369 0,045283 −0,008081
7 1 2 1,433156 0,018561 −0,003295
.
.
.
15 1 2 1,436448 0,000014 −0,000002
16 1 2 1,436449 0,000006 −0,000001
x0= 1, x1= 2. Z abulky je idˇe ,
ˇze poˇc´ınaje d uh´ym k okem je
xℓ= 2. D´ale je zˇ ejm´e, ˇze do ˇc -
´eho k oku je pˇ esnos me ody e-
gula alsi s o na eln´a s pˇ esnos ´ı
me ody seˇcen, iz pˇ ´ıklad 5.4.
V n´asleduj´ıc´ıch k oc´ıch je uˇz ale
pa n´a line´a n´ı kon e gence, pod-
m´ınka | (xk)|<10−5je splnˇena
aˇz p o x16. Vˇsimnˇe e si: d´elka in-
e al˚u Ik= (xk,2), k≥2, kon-
e guje k ˇc´ıslu x−x∗.
= 0,563550.

S e enseno a me oda se ˇ ´ıd´ı pˇ edpisem
xk+1 =xk− (xk)
dk
,kde dk= (xk+ (xk)) − (xk)
(xk)(5.9)
85

je speci´alnˇe spoˇc en´a ap oximace ′(xk) pˇ ipom´ınaj´ıc´ı dopˇ ednou di e enci:
′(xk)≈dk= (xk+hk)− (xk)
hk
,kde hk= (xk).
V kaˇzd´em k oku se unkce yhodnocuje d ak ´a : k omˇe hk= (xk) se poˇc´ı ´a jeˇs ˇe ak´e
(xk+hk). Op o i me odˇe seˇcen je u jedno yhodnocen´ı unkce na ´ıc. Na d uh´e s anˇe
lze uk´aza , ˇze ychlos kon e gence S e enseno y me ody je s ejn´a jako u New ono y
me ody, edy k ad a ick´a.
Me oda in e zn´ı k ad a ick´e in e polace. Me oda seˇcen pouˇz´ı ´a d a pˇ edchoz´ı body
k z´ısk´an´ı dalˇs´ıho, p oˇc edy nepouˇz´ı ˇ i?
Body [xk−2, (xk−2)], [xk−1, (xk−1)] a [xk, (xk)] m˚uˇzeme p oloˇzi pa abolu P2(x)
a hleda jej´ı p ˚useˇc´ık s osou x. Za dalˇs´ı ap oximaci xk+1 pak z ol´ıme en z koˇ en˚u polynomu
P2(x), k e ´y je bl´ıˇz k pˇ edchoz´ı ap oximaci xk. Na om o p incipu je zaloˇzena M˝ulle o a
me oda. Po ´ıˇz je om, ˇze pa abola nemus´ı x-o ou osu p o nou , nebo
’k ad a ick´a unkce
P2(x) nemus´ı m´ı e´aln´e koˇ eny. V´ypoˇce je p o o ˇ eba p o ´adˇe komplexn´ı a i me ice,
a o i pˇ ´ıpadˇe, ˇze o nice (x) = 0 m´a jen e´aln´e koˇ eny.
M´ıs o pa aboly p omˇenn´e xm˚uˇzeme ˇ emi body p oloˇzi pa abolu Q2(y) p omˇen-
n´e y, u ˇcenou in e polaˇcn´ımi podm´ınkami
Q2( (xk−2)) = xk−2, Q2( (xk−1)) = xk−1, Q2( (xk)) = xk.
Jsou-li hodno y (xk−2), (xk−1) a (xk) na z´ajem ˚uzn´e, pa abola Q2(y) exis uje a p o ´ı-
n´a osu x jedin´em bodˇe. Klademe edy xk+1 =Q2(0). Ta o me oda je zn´ama jako me oda
in e zn´ı k ad a ick´e in e polace. Jej´ı kon e gence je supe line´a n´ı ˇ ´adu p≈1,839, iz [7].
B en o a me oda. Me oda in e zn´ı k ad a ick´e in e polace spolu s me odou seˇcen a me-
odou bisekce jsou z´akladem popul´a n´ı B en o y me ody, iz napˇ . [15], d´ale ak´e p og am
zb en [18] nebo unkce ze o MATLABu.
Pˇ ednos ´ı B en o y me ody je o, ˇze nepouˇz´ı ´a de i ace unkce , je spolehli ´a, j.
za uˇcenˇe kon e guje ke koˇ enu, a po nˇekolika poˇc´a eˇcn´ıch k oc´ıch se chyba ychle zmenˇsuje,
nebo
’ ychlos kon e gence je supe line´a n´ı.
S a o ac´ı body x0ax1je ˇ eba z oli ak, aby (x0) (x1)<0. Ap oximace x2se u ˇc´ı
me odou seˇcen. Nech
’(a1, b1) je in e al, jehoˇz konco ´e body jsou x0ax1. Pak zˇ ejmˇe
x2∈(a1, b1). Dalˇs´ı ap oximaci x3budeme hleda k a ˇs´ım in e alu (a2, b2)⊂(a1, b1),
jehoˇz jeden konco ´y bod je x2a d uh´y je en z bod˚u a1,b1, nˇemˇz m´a unkce opaˇcn´e
znam´enko neˇz x2, akˇze (a2) (b2)<0a(a2, b2) obsahuje koˇ en.
Pˇ i ´ypoˇc u x3, x4,... B en o a me oda pouˇz´ı ´a jednu ze ˇ ´ı z´akladn´ıch me od ak, aby
no ´a ap oximace xk+1 ∈(ak, bk). D´ale se ybe e in e al (ak+1, bk+1)⊂(ak, bk) obsahuj´ıc´ı
koˇ en. Jedn´ım z jeho konco ´ych bod˚u je xk+1, d uh´ym je en z bod˚u ak,bk, nˇemˇz m´a
unkce znam´enko opaˇcn´e neˇz xk+1. Pˇ i ´ypoˇc u xk+1 se pˇ ednos nˇe pouˇzije me oda
in e zn´ı k ad a ick´e in e polace, pokud ak o z´ıskan´a ap oximace nen´ı dos a eˇcnˇe dob ´a,
zkus´ı se me oda seˇcen, a kdyˇz ani a nezabe e, pouˇzije se jako z´ach ana me oda bisekce.
Pod obnˇejˇs´ı popis B en o y me ody je u eden napˇ . [15], [18].
Pˇ ´ıklad 5.6. Budeme hleda kladn´y koˇ en o nice z pˇ ´ıkladu 5.1 a po o n´ame jedno li ´e
me ody podle poˇc u pk k ok˚u a poˇc u p yhodnocen´ı unkce (u New ono y me ody
86
do p zah neme ak´e poˇce yhodnocen´ı de i ace ′). P o ´ypoˇce B en o ou me odou
jsme pouˇzili up a en´y p og am ze o x, iz [15].
V´ypoˇce jsme zah´ajili ak o:
me odˇe bisekce poˇc´a eˇcn´ı in-
e al (a0, b0) = (1,2), New-
ono ˇe a S e enseno ˇe me odˇe
x0= 2, os a n´ıch me od´ach
x0= 1 a x1= 2. Pouˇzili
jsme s op k i ´e ium | (xk)|< ε.
V abulce jsou u edeny hodno y
pk/p p o nˇekolik ole anc´ı ε.
ε10−310−610−910−12 10−15
bisekce 9/11 19/21 29/31 39/41 49/51
egula alsi 10/12 17/19 25/27 33/35 40/42
seˇcny 6/8 7/9 8/10 8/10 9/11
New on 4/8 5/10 5/10 6/12 6/12
S e ensen 4/8 5/10 6/12 6/12 7/14
B en 6/7 7/8 7/8 8/9 8/9
Nejmenˇs´ı pk m´a New ono a me oda, nejmenˇs´ı p B en o a me oda. Z ´ypisu o p ˚ubˇehu
´ypoˇc u B en o ou me odou ypl´y ´a, ˇze se ani jednou nepouˇzila bisekce, p o o ak sk ˇel´y
´ysledek. 
Pozn´amka (O me odˇe p os ´e i e ace). Pˇ edpokl´adejme, ˇze unkce g∈Cha, bisplˇnuje y o
d ˇe podm´ınky:
(α)g(x)∈ ha, bi ∀x∈ ha, bi,
(β) exis uje ˇc´ıslo q, 0 ≤q < 1, ako ´e, ˇze |g(x)−g(y)| ≤ q|x−y| ∀x, y ∈ ha, bi.
Pak o nice x=g(x) m´a ha, bijedin´e ˇ eˇsen´ı x∗aposloupnos pos upn´ych ap oximac´ı
xk+1 =g(xk), k= 0,1,..., kon e guje k x∗p o kaˇzd´e x0∈ ha, bi. Bod x∗=g(x∗) se
naz´y ´a pe n´y bod unkce g(zob azuje x∗na sebe). N´asleduje n´aˇc d˚ukazu.
1) Exis ence. Z podm´ınky (α) plyne g(a)≥a,g(b)≤b, od ud (a−g(a))·(b−g(b)) ≤0,
akˇze ha, bileˇz´ı koˇ en o nice x−g(x) = 0.
2) Jednoznaˇcnos . Nech
’p o x∗, y∗∈ ha, bipla ´ı x∗=g(x∗), y∗=g(y∗). Podle (β)
|x∗−y∗|=|g(x∗)−g(y∗)| ≤ q|x∗−y∗|, coˇz je moˇzn´e jedinˇe kdyˇz x∗=y∗.
3) Kon e gence. Podle (β) je |xk−x∗|=|g(xk−1)−g(x∗)| ≤ q|xk−1−x∗|. Opako ´an´ım
´e o ´u ahy dos aneme nakonec |xk−x∗| ≤ qk|x0−x∗| → 0 p o k→ ∞, akˇze
xk→x∗.
M´ıs o podm´ınky (β) m˚uˇzeme p o g∈C1ha, bipouˇz´ı silnˇejˇs´ı podm´ınku
(β′)|g′(x)| ≤ q < 1∀x∈ ha, bi.
Podle ˇe y o s ˇ edn´ı hodno ˇe o iˇz g(x)−g(y) = g′(ξ)(x−y), kde ξleˇz´ı mezi xay, akˇze
p o x, y ∈ ha, bipodle (β′) je |g(x)−g(y)|=|g′(ξ)|·|x−y| ≤ q|x−y|, j. pla ´ı (β).
Vˇsimnˇe e si, ˇze p o ha, bi=hx∗−δ, x∗+δije pla nos podm´ınky (α) d˚usledkem pla -
nos i podm´ınky (β): |g(x)−x∗|=|g(x)−g(x∗)| ≤ q|x−x∗|<|x−x∗|, j. kdyˇz |x−x∗| ≤ δ,
pak ak´e |g(x)−x∗| ≤ δ.
Pˇ ibliˇzn´y ´ypoˇce koˇ ene x∗ o nice x=g(x) podle o mule xk+1 =g(xk) se naz´y ´a
me oda p os ´e i e ace nebo ak´e me oda pos upn´ych ap oximac´ı. Podm´ınky (α) a (β) nebo
(β′) jsou pos aˇcuj´ıc´ı p o kon e genci ´e o me ody.
87
Vhodnou ´up a ou o nice (x) = 0 na a x=g(x) m˚uˇzeme dos a ˇ adu ˚uzn´ych
konk ´e n´ıch me od. Tak ˇ eba p o g(x) = x− (x)/ ′(x) dos aneme New ono u me odu.
Rychlos kon e gence posloupnos i pos upn´ych ap oximac´ı {xk}∞
k=0 z´a is´ı na cho ´an´ı
unkce g bodˇe x∗. Jsou-li splnˇeny podm´ınky (α) a (β) nebo (β′), a m´a-li gdos a eˇcn´y
poˇce spoji ´ych de i ac´ı, daj´ı se dok´aza n´asleduj´ıc´ı zen´ı.
•Pokud g′(x∗)6= 0, je ˇ ´ad kon e gence o en jedn´e a pla ´ı |xk+1 −x∗| ≤ q|xk−x∗|.
•Pokud g′(x∗) = 0 a g′′(x∗)6= 0, je ˇ ´ad kon e gence o en d ˇema.
•Obecnˇe, pokud jsou de i ace g(s)(x∗) = 0, s= 1,2,..., −1, a g( )(x∗)6= 0, kon e -
gence je ˇ ´adu .
P o New ono u me odu g′(x) = (x) ′′(x)/( ′(x))2, j. g′(x∗) = 0, akˇze kon e gence
xk→x∗je ˇ ´adu alespoˇn d a (coˇz po zuje n´am jiˇz zn´am´y ´ysledek).
D´a se ak´e dok´aza , ˇze kdyˇz |g′(x∗)|>1, pak p o x06=x∗posloupnos pos upn´ych
ap oximac´ı k x∗kon e go a nem˚uˇze. 
Pˇ ´ıklad 5.7. Neline´a n´ı o nice (x) = x2−2x−3 = 0 m´a koˇ eny x∗=−1 a x∗= 3.
P ozkoum´ame kon e genci ke koˇ enu x∗= 3 p o nˇekolik i e aˇcn´ıch unkc´ı g.
1. g(x) = (x2−3)/2, g′(x) = x,|g′(3)|= 3, p o x06= 3 kon e gence nenas ane.
2. g(x) = √2x+ 3, g′(x) = 1/√2x+ 3, |g′(3)|= 1/3, line´a n´ı kon e gence nas ane napˇ .
p o libo oln´e x0z in e alu h2,4i, nebo
’ nˇem |g′(x)| ≤ 1/√7.
3. g(x) = 2 + 3/x,g′(x) = −3/x2,|g′(3)|= 1/3, line´a n´ı kon e gence nas ane napˇ . p o
libo oln´e x0z in e alu h2,4i, nebo
’ nˇem |g′(x)| ≤ 3/4.
4. g(x) = (x2+3)/(2x−2), g′(x) = 2(x2−2x−3)/(2x−2)2,g′(3) = 0, g′′(3) = 1/2, k ad-
a ick´a kon e gence nas ane napˇ . p o x0z in e alu h2,5; 3,5i, nˇemˇz |g′(x)|<0,39,
jak snadno zjis ´ıme. O ˇeˇ e, ˇze a o i e aˇcn´ı unkce odpo ´ıd´a New ono ˇe me odˇe. 
Pozn´amka (O n´asobn´ych koˇ enech). ˇ
Rekneme, ˇze koˇ en x∗ o nice (x) = 0 m´a n´asob-
nos q, jes liˇze unkce g(x) = (x)/(x−x∗)qje bodˇe x∗de ino ´ana a koˇ en nˇem uˇz
nem´a, j. kdyˇz 0 <|g(x∗)|<∞. Jes liˇze m´a unkce (x) okol´ı koˇ ene x∗spoji ´e de i ace
aˇz do ˇ ´adu q ˇce nˇe, pak (j)(x∗) = 0, j= 0,1,...,q−1.
Nˇek e ´e z doposud u eden´ych me od lze pouˇz´ı ak´e p o nalezen´ı n´asobn´ych koˇ en˚u,
kon e gence ˇsak b´y ´a pomalejˇs´ı. Tak ˇ eba New ono a me oda kon e guje jen line´a nˇe
s chybo ou kons an ou C= (q−1)/q.
Kdyˇz oˇcek´a ´ame, ˇze o nice (x) = 0 m˚uˇze m´ı n´asobn´e koˇ eny, je hodn´e yuˇz´ı
oho, ˇze unkce u(x) = (x)/ ′(x) m´a pouze jednoduch´e koˇ eny. M´ıs o o nice (x) = 0
edy ˇ eˇs´ıme o nici u(x) = 0. 
Pozn´amka (O dosaˇzi eln´e pˇ esnos i). Nech
’xkje ap oximace jednoduch´eho koˇ ene o -
nice (x) = 0. Pomoc´ı ˇe y o s ˇ edn´ı hodno ˇe dos aneme
(xk) = (xk)− (x∗) = ′(ξ)(xk−x∗),
kde ξje nˇejak´y bod leˇz´ıc´ı mezi xkax∗. Pˇ edpokl´adejme, ˇze pˇ i ´ypoˇc ech p acujeme jen
s pˇ ibliˇzn´ymi hodno ami ˜
(xk) = (xk) + δk, pˇ iˇcemˇz |δk| ≤ δ. Pak nejlepˇs´ı ´ysledek,
88
k e ´eho m˚uˇzeme dos´ahnou , je ˜
(xk) = 0. V om pˇ ´ıpadˇe | (xk)| ≤ δ, akˇze
|xk−x∗|=| (xk)|
| ′(ξ)|≤δ
| ′(ξ)|≈δ
| ′(x∗)|=: ε∗
x,
pokud se ′ bl´ızkos i koˇ ene pˇ ´ıliˇs nemˇen´ı. Vypoˇc´ı a x∗s menˇs´ı chybou neˇz ε∗
xnelze.
P o o se ε∗
xnaz´y ´a dosaˇzi eln´a pˇ esnos koˇ ene x∗. Vˇsimnˇe e si: kdyˇz je elikos smˇe nice
| ′(x∗)| koˇ enu x∗mal´a, je dosaˇzi eln´a pˇ esnos ε∗
x elk´a, iz ob . 5.5. V ako ´em pˇ ´ıpadˇe
je ´ypoˇce koˇ ene x∗ˇspa nˇe podm´ınˇen´y p obl´em: mal´a zmˇena y ol´a elkou zmˇenu x∗.
x*−ε*
xx*+ε*
x
(x)
y=0
Ob . 5.5: Dosaˇzi eln´a pˇ esnos koˇ ene
Podobn´a ´u aha p o koˇ en n´asobnos i qd´a ´a dosaˇzi elnou pˇ esnos
ε∗
x=δ·q!
(q)(x∗)1/q
.
Exponen 1/q je pˇ ´ıˇcinou oho, ˇze ´ypoˇce n´asobn´eho koˇ ene je obecnˇe ˇspa nˇe podm´ınˇen´a
´uloha. Tak ˇ eba p o (x) = xqje x∗= 0 koˇ en n´asobnos i qaε∗
x=δ1/q. P o q= 15
aδ= 10−15 dos aneme ε∗
x= 0,1! 
Pozn´amka (O koˇ enech polynom˚u). Polynom pn(x) s upnˇe nm´a nobecnˇe komlexn´ıch
koˇ en˚u. P o ´ypoˇce jednoduch´ych e´aln´ych koˇ en˚u unkce (x) = pn(x) lze pouˇz´ı li-
bo olnou z dosud u eden´ych me od. O om, jak se ypoˇ ´ada s pˇ ´ıpadn´ymi n´asobn´ymi
koˇ eny, pojedn´a ´a ´yˇse u eden´a pozn´amka. P o ´ypoˇce komplexn´ıch koˇ en˚u lze pouˇz´ı
napˇ . New ono u me odu, n´ıˇz jako poˇc´a eˇcn´ı ap oximaci ol´ıme komplexn´ı ˇc´ıslo.
Pokud n´as zaj´ımaj´ı ˇsechny koˇ eny polynomu, ak po nalezen´ı e´aln´eho koˇ ene x∗
polynom pn(x) dˇel´ıme ˇclenem x−x∗. Tak dos aneme polynom pn−1(x) = pn(x)/(x−x∗)
s upnˇe n−1 a d´ale hled´ame jeho koˇ eny. Kdyˇz je x∗komplexn´ı koˇ en, pak je koˇ enem
ak´e komplexnˇe sd uˇzen´e ˇc´ıslo ¯x∗. V om pˇ ´ıpadˇe dˇel´ıme pn(x) k ad a ick´ym polynomem
(x−x∗)(x−¯x∗), jehoˇz koe icien y jsou e´aln´a ˇc´ısla. Tak dos aneme polynom pn−2(x)
s upnˇe n−2 s e´aln´ymi koe icien y a pok aˇcujeme hled´an´ım jeho koˇ en˚u.
P o ´ypoˇce koˇ en˚u polynom˚u jsou na ˇzeny ak´e speci´aln´ı, elmi e ek i n´ı me ody,
o nichˇz lze z´ıska in o mace napˇ . [22]. 
5.3. Sous a y neline´a n´ıch o nic
Mnoh´e z me od u ˇcen´ych p o ˇ eˇsen´ı jedn´e neline´a n´ı o nice lze zobecni na ˇ eˇsen´ı
sous a neline´a n´ıch o nic. Bohuˇzel o nepla ´ı p o me odu bisekce ani p o me odu egula
89
5.4. C iˇcen´ı
5.1. K jak´emu ˇc´ıslu kon e guje posloupnos i e ac´ı, de ino an´a ak o
x0= 1, xk+1 =1
2xk+1
xk
.
Zd˚u odnˇe e kon e genci!
[ lim
k→∞ xk=√2,i e aˇcn´ı pˇ edpis je New ono a me oda p o o nici x2−2 = 0. ]
5.2. Me odou seˇcen a eˇcen spoˇc ˇe e ˇ eˇsen´ı d´ale u eden´ych o nic na 6 pla n´ych dese inn´ych ci e pˇ esnˇe.
Po o nej e poˇce i e ac´ı nu n´ych k dosaˇzen´ı poˇzado an´e pˇ esnos i. (a) x−e−x= 0, x0= 0,5, x1= 0,6;
(b) x−cos x= 0, x0= 0,5, x1= 0,6; (c) x3+ 4x2−10 = 0, x0= 1,5, x1= 1,6. (x1pouˇzij e jen me odˇe
seˇcen.)
[ (a) 0,567143 (b) 0,739085 (c) 1,365230.]
5.3. (a) Nap og amuj e hled´an´ı znam´enko ´e zmˇeny. Vs upem je unkce (x), in e al ha, bia pˇ i ozen´e
ˇc´ıslo n. P og am ozdˇel´ı in e al ha, bina ns ejn´ych d´ılk˚u. V dˇelic´ıch bodech xi,i= 0,1,...,n, spoˇc e
(xi) a ´a ´ı seznam subin e al˚u (xk, xk+1), nichˇz pla ´ı (xk) (xk+1)<0.
(b) Nap og amuj e me odu p˚ulen´ı in e alu. Vs upem bude unkce (x), in e al ha, bia poˇzado an´a
d´elka d=|bk−ak| ´ysledn´eho in e alu hak, bki.
(c) P opoj e (a) s (b); dos ane e n´as oj p o hled´an´ı k ali n´ıch poˇc´a eˇcn´ıch ap oximac´ı.
(d) Nap og amuj e me odu seˇcen a eˇcen ˇce nˇe es o ´an´ı poˇzado an´e pˇ esnos i ε. Poˇc´a eˇcn´ı ap oximaci
u ˇce e pomoc´ı (c) jako x0= (ak+bk)/2.
5.4. Jak´e ´ysledky pˇ inese p og am ze c iˇcen´ı 5.3 p o s upn´ı da a:
(a) (x) = x3+ 5x2−10, ha, bi=h−5,3i,n= 5, d= 0,1, ε= 10−6?
(b) (x) = x5+ 2x4−x3−2x2+ 0,1, ha, bi=h−3,3i,n= 5, d= 0,1, ε= 10−6?
(c) (x) = x5+ 2x4−x3−2x2+ 0,1, ha, bi=h−3,3i,n= 10, d= 0,1, ε= 10−6?
[ (a) Najde ˇsechny koˇ eny x∗
1
.
=−4,507903, x∗
2
.
=−1,755640, x∗
3
.
= 1,263543;
(b) najde jen koˇ eny x∗
1
.
=−2,008176, x∗
2
.
=−0,945472, x∗
3
.
= 0,982479;
(c) najde ˇsechny koˇ eny x∗
1
.
=−2,008176, x∗
2
.
=−0,945472, x∗
3
.
= 0,982479,
x∗
4
.
=−0,246397, x∗
5
.
= 0,217566.]
5.5. O ˇeˇ e, ˇze New ono a me oda p o (x) = (x−1)2kon e guje k x∗= 1 jen line´a nˇe.
[xk+1 −1 = 1
2(xk−1). ]
5.6. Hledej e koˇ en o nice (x) := x2+ lnx−10/x = 0 na in e alu I=h1,4ime odou p os ´e i e ace.
Zkoumej e na poˇc´ı aˇci kon e genci p o i e aˇcn´ı unkce (a) g(x) = e10/x−x2, (b) g(x) = 10/(x2+ lnx),
(c) g(x) = p10/x −lnx, (d) g(x) = 3
√10 −xlnx. Poˇc´a eˇcn´ı i e aci x0z ol e ˇzdy e s ˇ edu in e alu,
j. x0= 2,5. O ˇeˇ e, ˇze (x) = 0 ⇐⇒ x=g(x) a odhadnˇe e q= max
x∈I|g′(x)|. Jsou ´ysledky souladu
s ˇe ou o kon e genci?
[ (a) nekon e guje, q.
= 9,72 ·104; (b) nekon e guje, q.
= 30; (c) kon e guje, q.
= 1,74; (d) kon e guje
ychleji, q.
= 0,57. ]
5.7. New ono ou me odou ˇ eˇs e sous a y o nic na 6 dese inn´ych ci e pˇ esnˇe.
(a) 2 cos(xy) = 1
2 sin(x+y) = 1 (b) 2 cos(xy)−sin x= 0
2xsin y−3ysin x=−1(c) x2y−exy =−2
ln(x+ 1)y−y2/x = 0
Jako s a o ac´ı hodno y pouˇzij e (a) x0= 2,5, y0= 0,25; (b) x0= 1, y0= 1; (c) x0= 1, y0= 1.
Bl´ızkos koˇ ene o ˇeˇ e g a icky.
[ (a) x∗.
= 2,125254, y∗.
= 0,492740; (b) x∗.
= 1,023402, y∗.
= 1,103856; (c) x∗.
= 1,256558, y∗.
= 1,022638.]
96

6. Op imalizace
Op imalizaˇcn´ı ´ulohy se zab´y aj´ı ´ybˇe em nejlepˇs´ıch ˇ eˇsen´ı z dan´e mnoˇziny moˇzn´ych
ˇ eˇsen´ı. Ma ema icky m˚uˇzeme op imalizaˇcn´ı ´ulohu o mulo a jako nalezen´ı p ku x∗∈M
ako ´eho, ˇze p o libo oln´y p ek x∈Mpla ´ı
(x∗)≤ (x)∀x∈M , (6.1)
kde :M7→ Rje minimalizo an´a (nˇekdy se ak´e ˇ ´ık´a ´uˇcelo ´a nebo c´ılo ´a nebo k i e i´aln´ı)
unkce aMje mnoˇzina pˇ ´ıpus n´ych ˇ eˇsen´ı. Jes liˇze pˇ ´ıpus n´ym ˇ eˇsen´ım m˚uˇze b´y kaˇzd´y
bod x= (x1, x2,...,xn)Tn- ozmˇe n´eho Euklido a p os o u Rn, j. M=Rn, ho oˇ ´ıme
onepodm´ınˇen´e op imalizaci. O unkci budeme pˇ edpokl´ada , ˇze je spoji ´a (pˇ ´ıpadnˇe i se
s ´ymi p n´ımi a dalˇs´ımi de i acemi).
Op imalizaˇcn´ı ´uloha (6.1) se naz´y ´a ´ulohou glob´aln´ı op imalizace. My se ´e o kapi ole
omez´ıme na jednoduˇsˇs´ı ´ulohu lok´aln´ı op imalizace spoˇc´ı aj´ıc´ı nalezen´ı lok´aln´ıho minima,
j. p ku x∗∈M ako ´eho, ˇze pla ´ı
(x∗)≤ (x)∀x∈M∩O(x∗),(6.2)
kde O(x∗) je nˇejak´e okol´ı bodu x∗.
Pod obnˇeji si ˇsimneme d ou speci´aln´ıch ´uloh: ods a ci 6.1 se sezn´am´ıme s me odami
p o minimalizaci unkce jedn´e p omˇenn´e na in e alu ha, bia ods a ci 6.2 se budeme
ˇeno a me od´am nepodm´ınˇen´e minimalizace unkce ´ıce p omˇenn´ych.
Pozn´amka. U ˇcen´ı maxima unkce g(x) m˚uˇzeme pˇ e ´es na ´ulohu u ˇcen´ı minima unkce
(x) = −g(x). 
6.1. Jedno ozmˇe n´a minimalizace
V om o ods a ci u edeme me ody p o pˇ ibliˇzn´e u ˇcen´ı bodu x∗lok´aln´ıho minima
unkce (x) na in e alu ha, bi. Jes liˇze je unkce na in e alu ha, biunimod´aln´ı, j.
kdyˇz m´a in e alu ha, bijedin´e minimum, pak ho (d´ale u eden´ymi me odami pˇ ibliˇznˇe)
najdeme. Pokud ˇsak m´a unkce na in e alu ha, bi ´ıce lok´aln´ıch minim, najdeme jedno
z nich.
In e alo ou bisekci pouˇz´ı nem˚uˇzeme: i kdyˇz zn´ame (a), (b) a ((a+b)/2), ne-
dok´aˇzeme ozhodnou , e k e ´e polo inˇe in e alu ha, biminimum leˇz´ı.
Pouˇz´ı lze in e alo ou isekci. Nech
’h= (b−a)/3, akˇze u=a+ha =b−hdˇel´ı
in e al na ˇ i s ejn´e ˇc´as i. Pˇ edpokl´adejme, ˇze (u)< ( ). Pak minimum jis ˇe leˇz´ı le o
od , akˇze bnah ad´ıme pomoc´ı . T´ım se d´elka in e alu (obsahuj´ıc´ıho minimum) zk ´a ´ı
na d ˇe ˇ e iny s ´e p˚u odn´ı d´elky. Bod use ˇsak s ane s ˇ edem no ´eho in e alu a nebude
p o o dalˇs´ım k oku yuˇzi eln´y. Funkci edy mus´ıme yhodnoco a kaˇzd´em k oku
d ak ´a . To je nee ek i n´ı.
Me oda zla ´eho ˇ ezu je zaloˇzena na ˇsiko nˇejˇs´ım ´ybˇe u dˇelic´ıch bod˚u ua . Nech
’
h=(b−a), kde je ˇc´ıslo o nˇeco ˇe ˇs´ı neˇz 1/3, jehoˇz pˇ esnou hodno u ep e u ˇc´ıme.
Pak body u=a+ha =b−hdˇel´ı in e al ha, bina ˇ i nes ejn´e ˇc´as i. V p n´ım k oku
yhodno ´ıme (u) a ( ). Pˇ edpokl´adejme, ˇze (u)< ( ). Pak ´ıme, ˇze minimum je
97
mezi aa . Nah ad´ıme bpomoc´ı a p oces opakujeme. Kdyˇz z ol´ıme sp ´a nou hodno u
, bod ubude e sp ´a n´e pozici pouˇzi eln´e pˇ ´ıˇs ´ım k oku. Po p n´ım k oku se ak
unkce bude yhodnoco a kaˇzd´em k oku uˇz jen jednou.
Jak edy z oli ? Tak, aby bod uh ´al eduko an´em in e alu ha, is ejnou oli jako
bod p˚u odn´ım in e alu ha, bi, j. aby pomˇe d´elky in e alu ha, uik d´elce in e alu
ha, ibyl s ejn´y jako pomˇe d´elky in e alu ha, ik d´elce in e alu ha, bi,
u−a
−a= −a
b−a⇐⇒ 
1−=1−
1⇐⇒ 2−3+ 1 = 0 .
Vyho uj´ıc´ı ˇ eˇsen´ı je
= (3 −√5)/2≈0,382,kde τ= 1 −= (√5−1)/2≈0,618
je ˇc´ıslo zn´am´e jako pomˇe zla ´eho ˇ ezu.
a bu
ρ(b−a)
ρ(b−a)
(1−ρ)(b−a) (1−ρ)(b−a)
Ob . 6.1: Zla ´y ˇ ez
Pozn´amka (O zla ´em ˇ ezu). ˇ
R´ık´ame, ˇze bod dˇel´ı in e al pomˇe u zla ´eho ˇ ezu, kdyˇz
d a no ˇe znikl´e subin e aly maj´ı u o las nos : pomˇe d´elky k a ˇs´ıho subin e alu
k d´elce delˇs´ıho subin e alu je s ejn´y jako pomˇe d´elky delˇs´ıho subin e alu k d´elce cel´eho
in e alu. Z ´yˇse u eden´e kons ukce je zˇ ejm´e, ˇze bod u(ale ak´e bod ) dˇel´ı in e al
ha, bi pomˇe u zla ´eho ˇ ezu.
Pˇ ipomeˇnme si, ˇze s ˇc´ıslem τjsme se se kali jiˇz kapi ole 5.2, kde jsme u edli, ˇze
ychlos kon e gence me ody seˇcen p= 1 + τ.
= 1,618. 
Za ´ım jsme pˇ edpokl´adali, ˇze (u)< ( ). V opaˇcn´em pˇ ´ıpadˇe, j. kdyˇz (u)≥ ( ),
leˇz´ı minimum in e alu hu, bi, akˇze anah ad´ıme pomoc´ı u. Snadno o ˇeˇ ´ıme, ˇze e-
duko an´em in e alu hu, bibude m´ı s ejnou oli jako mˇelo u p˚u odn´ım in e alu
ha, bi, akˇze hodno u unkce na eduko an´em in e alu opˇe s aˇc´ı poˇc´ı a jen jednou.
D´elka eduko an´eho in e alu je τ-k ´a menˇs´ı neˇz d´elka p˚u odn´ıho in e alu. Z ´ycho-
z´ıho in e aluha0, b0i=ha, bi ak pos upnˇe ses oj´ıme in e aly ha1, b1i ⊃ ha2, b2i ⊃ ...,
k e ´e obsahuj´ı minimum a jejichˇz d´elka je kaˇzd´em k oku eduko ´ana ak o em τ. Na
´ychoz´ım in e alu ha0, b0iu ˇc´ıme u0=a+(b−a), 0=b−(b−a) a ypoˇc eme
(u0), ( 0). In e al hak+1, bk+1i,k= 0,1,..., dos aneme pomoc´ı ak,bk,uk, ka jiˇz
dˇ ´ı e ypoˇc en´ych hodno (uk), ( k) ak o:
1) kdyˇz (uk)< ( k), pak
ak+1 := ak,bk+1 := k, k+1 := uk,uk+1 := ak+1 +bk+1 − k+1
a ypoˇc eme (uk+1);
2) opaˇcn´em pˇ ´ıpadˇe, j. kdyˇz (uk)≥ ( k), p o edeme
ak+1 := uk,bk+1 := bk,uk+1 := k, k+1 := ak+1 +bk+1 −uk+1
98
a ypoˇc eme ( k+1).
akbk
uk k
ak+1 bk+1
akbk
uk k
ak+1 bk+1
Ob . 6.2: Me oda zla ´eho ˇ ezu
Po kk oc´ıch leˇz´ı minimum in e alu Ik:= hak, bkid´elky
|Ik|=bk−ak=τ(bk−1−ak−1) = ···=τk(b0−a0).
S ˇ ed xk+1 in e alu hak, bkiap oximuje minimum x∗s chybou
|xk+1 −x∗| ≤ 1
2(bk−ak) = 1
2τk(b0−a0).(6.3)
P o k→ ∞ zˇ ejmˇe |Ik| → 0 a xk→x∗.
Kon e gence me ody zla ´eho ˇ ezu je pomˇe nˇe pomal´a. P o o je bl´ızkos i minima
´uˇceln´e pˇ ej´ı na ychleji kon e gen n´ı me odu. Jednou z moˇznos ´ı je me oda k ad a ick´e
in e polace, s n´ıˇz se ak´e sezn´am´ıme. Pˇ ed ´ım ale
Pˇ ´ıklad 6.1. Me odou zla ´eho ˇ ezu u ˇc´ıme minimum unkce (x) = x4−3x3+x+7. Jako
poˇc´a eˇcn´ı z ol´ıme in e al ha0, b0i=h1,3i. V´ypoˇce p o edeme s pˇ esnos ´ı ε= 10−3, j.
kdyˇz bk−ak<2ε, poloˇz´ıme xk+1 = (ak+bk)/2. V´ypoˇce je zaznamen´an n´asleduj´ıc´ı abul-
ce. Pod ˇzen´ım jsou yznaˇceny y ni ˇ n´ı body, nichˇz se poˇc´ı ´a hodno a ´uˇcelo ´e unkce.
k akuk kbk (uk) ( k)
0 1,0000 1,7639 2,2361 3,0000 1,979900 ≥0,695048
1 1,7639 2,2361 2,5279 3,0000 0,695048 <1,901312
2 1,7639 2,0557 2,2361 2,5279 0,852324 ≥0,695048
3 2,0557 2,2361 2,3475 2,5279 0,695048 <0,906510
4 2,0557 2,1672 2,2361 2,3475 0,690296 <0,695048
5 2,0557 2,1246 2,1672 2,2361 0,729249 ≥0,690296
.
.
.
14 2,1973 2,1982 2,1988 2,1997 0,681572 <0,681575
15 2,1973 2,1988
Poˇzado an´a pˇ esnos je dosaˇzena p o k= 15, akˇze (po zaok ouhlen´ı na 3 dese inn´e ci y)
x16 .
= 2,198. Hodno a ´uˇcelo ´e unkce se poˇc´ı ´a celkem 16-k ´a . P o oˇze pˇ esn´a hodno a
x∗.
= 2,198266, m´a x16 := 2,198 ˇsechny ci y pla n´e. 
99
Me oda k ad a ick´e in e polace. Pˇ edpokl´adejme, ˇze minimum leˇz´ı in e alu hak, bki,
a ˇze nˇejak´em jeho ni ˇ n´ım bodˇe ckhodno a unkce nepˇ es´ahne hodno y (ak), (bk)
k ajn´ıch bodech ak,bk, j. ˇze
p o ak< ck< bkpla ´ı (ck)≤min{ (ak); (bk)}.(6.4)
Body [ak, (ak)], [ck, (ck)] a [bk, (bk)] p oloˇz´ıme pa abolu P2(x) (k ad a ick´y in e -
polaˇcn´ı polynom) a bod xk+1 jej´ıho minima po aˇzujeme za dalˇs´ı ap oximaci x∗. Vzo ec
p o ´ypoˇce xk+1 dos aneme ˇ eˇsen´ım line´a n´ı o nice P′
2(xk+1) = 0. D´a se uk´aza , ˇze
xk+1 =ck−1
2
(ck−ak)2[ (ck)− (bk)] −(ck−bk)2[ (ck)− (ak)]
(ck−ak)[ (ck)− (bk)] −(ck−bk)[ (ck)− (ak)] .(6.5)
Z (6.4) plyne, ˇze xk+1 ∈(ak, bk). Kdyˇz n´ahodou xk+1 =ck, loˇz´ıme do xk+1 jin´y ni ˇ n´ı bod
in e alu hak, bki. S ´ım o slab´ym m´ıs em me ody k ad a ick´e in e polace (a s dalˇs´ımi, zde
nezm´ınˇen´ymi nedos a ky) se ´uspˇeˇsnˇe y o n´a ´a B en o a me oda. S uˇcn´a zm´ınka o n´ı
je u edena n´asleduj´ıc´ım ex u.
Z bod˚u ak,bk,ckaxk+1 pak ybe eme no ´y in e al (ak+1, bk+1) obsahuj´ıc´ı mini-
mum a bod ck+1 splˇnuj´ıc´ı podm´ınku (6.4), en ok ´a p o index k+ 1. Pos upujeme podle
n´asleduj´ıc´ıch p a idel:
A : xk+1 < cka (xk+1)< (ck) =⇒ak+1 =ak,ck+1 =xk+1,bk+1 =ck,
B : xk+1 < cka (xk+1)≥ (ck) =⇒ak+1 =xk+1,ck+1 =ck,bk+1 =bk,
C : ck< xk+1 a (ck)< (xk+1) =⇒ak+1 =ak,ck+1 =ck,bk+1 =xk+1,
D : ck< xk+1 a (ck)≥ (xk+1) =⇒ak+1 =ck,ck+1 =xk+1,bk+1 =bk.
akbk
xk+1 ck
ak+1 ck+1 bk+1
A
akbk
xk+1 ck
ak+1 ck+1 bk+1
B
akbk
ckxk+1
ak+1 ck+1 bk+1
C
akbk
ckxk+1
ak+1 ck+1 bk+1
D
Ob . 6.3: Me oda k ad a ick´e in e polace
V´ypoˇce ukonˇc´ıme a xk+1 po aˇzujeme za dos a eˇcnˇe dob ou ap oximaci minima x∗,
kdyˇz je splnˇeno nˇek e ´e ze s op k i e i´ı
|xk+1 −xk|< ε , |xk+1 −xk|< ε|xk|,| (xk)− (xk+1)|< ε , | (xk)− (xk+1)|< ε| (xk)|,
100
kde εje pˇ edepsan´a ole ance.
V´ypoˇce xk+1,k= 0,1,..., yˇzaduje k+ 3 yhodnocen´ı ´uˇcelo ´e unkce: (a0), (c0),
(b0) a d´ale (xi), i= 1,2,...,k.
Pokud me oda k ad a ick´e in e polace kon e guje, pak je ychlos jej´ı kon e gence
supe line´a n´ı ˇ ´adu p≈1,324, iz [7].
Pˇ ´ıklad 6.2. Minimum unkce (x) = x4−3x3+x+7 u ˇc´ıme me odou k ad a ick´e in e -
polace. V´ypoˇce ukonˇc´ıme, kdyˇz |xk+1 −xk|<10−5. V´ypoˇce je zaznamen´an n´asleduj´ıc´ı
abulce. V posledn´ım sloupci je u edeno, k e ´y z pˇ ´ıpad˚u A,B,C,D nas ´a ´a, a pod ˇzen´ım
a0= 2,000000 x1= 2,204918 < c0= 2,500000 b0= 3,000000 (x1)< (c0) =⇒A
a1= 2,000000 x2= 2,180689 < c1= 2,204918 b1= 2,500000 (x2)≥ (c1) =⇒B
a2= 2,180689 x3= 2,197322 < c2= 2,204918 b2= 2,500000 (x3)< (c2) =⇒A
a3= 2,180689 c3= 2,197322 < x4= 2,198232 b3= 2,204918 (c3)≥ (x4) =⇒D
a4= 2,197322 c4= 2,198232 < x5= 2,198264 b4= 2,204918 (c4)≥ (x5) =⇒D
a5= 2,198232 c5= 2,198264 < x6= 2,198265 b5= 2,204918
jsou (pos upnˇe zle a dop a a) yznaˇceny body ak+1 < ck+1 < bk+1. Z abulky je zˇ ejm´e, ˇze
poˇzado an´a pˇ esnos byla dosaˇzena p o x6.
= 2,19827 ( ˇsechny ci y jsou pla n´e). Hodno a
´uˇcelo ´e unkce se poˇc´ı ala celkem 8-k ´a . 
B en o a me oda je kombino an´a me oda, k e ´a sobˇe spojuje spolehli os me ody
zla ´eho ˇ ezu a ychlou kon e genci me ody k ad a ick´e in e polace. Popis B en o y me-
ody lze naj´ı napˇ . [18], iz unkce b en , nebo [15], iz unkce min x. B en ˚u algo-
i mus je ak´e z´akladem unkce minbnd p o jedno ozmˇe nou minimalizaci MATLABu.
6.2. Minimalizace unkce ´ıce p omˇenn´ych
Nelde o a-Meado a me oda zn´am´a ak´e jako me oda simplex˚u je popul´a n´ı me oda
nepouˇz´ı aj´ıc´ı de i ace ´uˇcelo ´e unkce. Pa ˇ ´ı mezi z . kompa a i n´ı me ody, coˇz jsou me-
ody, k e ´e hledaj´ı minimum ´uˇcelo ´e unkce po o n´a ´an´ım jej´ıch hodno u ˇci ´ych y-
b an´ych bodech p os o u Rn. V pˇ ´ıpadˇe me ody simplex˚u jsou yb an´ymi body
choly simplexu (p o n= 2 oj´uheln´ıka, p o n= 3 ˇc yˇ s ˇenu).
Hla n´ı myˇslenka jednoho k oku me ody je jednoduch´a: mezi choly x0,x1,...,xnsim-
plexu ybe eme nejho ˇs´ı chol xw( angliˇc inˇe wo s ), nˇemˇz ´uˇcelo ´a unkce nab´y ´a
nej ˇe ˇs´ı hodno u, a nah ad´ıme ho lepˇs´ım cholem ˆ
x, nˇemˇz je hodno a ´uˇcelo ´e unkce
menˇs´ı.
V chol ˆ
xhled´ame na polopˇ ´ımce, k e ´a ych´az´ı z nejho ˇs´ıho cholu xwa p och´az´ı
ˇeˇziˇs ˇem ¯
xzb´y aj´ıc´ıch chol˚u. Nejlepˇs´ı z nich oznaˇc´ıme xb( angliˇc inˇe bes ), j. xbje
en z chol˚u x0,x1,...,xn, nˇemˇz ´uˇcelo ´a unkce nab´y ´a nejmenˇs´ı hodno u.
P n´ı pokus, jak yb a ˆ
x, oznaˇcujeme jako e lexi: bod x =¯
x+ (¯
x−xw), je ob az
bodu xw e s ˇ edo ´e soumˇe nos i se s ˇ edem ¯
x. Kdyˇz je (x )< (xb), pak o znamen´a, ˇze
pokles hodno na polopˇ ´ımce xw¯
xje znaˇcn´y, a p o o zkus´ıme pos oupi po ´e o polopˇ ´ımce
jeˇs ˇe d´al, do bodu xe=¯
x+2(¯
x−xw). V´ybˇe bodu xeb´y ´a oznaˇco ´an jako expanze. Kdyˇz
(xe)< (xb), pak ˆ
x=xe, j. nejho ˇs´ı chol xwnah ad´ıme bodem xe.
101

Jes liˇze (xe)≥ (xb), zkus´ıme pouˇz´ı alespoˇn bod x . Podm´ınkou p o jeho zaˇ azen´ı
do simplexu je splnˇen´ı podm´ınky (x )< (xg) p o nˇek e ´y chol xgjin´y neˇz nejho ˇs´ı,
j. p o xg6=xw(index gpˇ ipom´ın´a anglick´e sl˚u ko good). Pokud ako ´a podm´ınka pla ´ı,
be eme ˆ
x=x m´ıs o p˚u odn´ıho xw.
1
2
3
4
5
6
7
8
xb
xg
xw
x
xe
xce
xci
xb
xg
xw
0)
1)
2)
3)
4)
5)
Ob . 6.4: Nelde o a-Meado a me oda: 0) o igin´aln´ı oj´uheln´ık, 1) expanze, 2) e lexe, 3) nˇejˇs´ı
kon akce, 4) ni ˇ n´ı kon akce, 5) edukce
Kdyˇz ne yho uje xeani x , zkus´ıme naj´ı bod ˆ
xna ´useˇcce s konco ´ymi body xw,x
ak, aby (ˆ
x)<min{ (xw); (x )}. Konk ´e nˇe pos upujeme ak o:
a) pokud (x )< (xw), zkus´ıme bod xce =1
2(¯
x+x ) (leˇz´ı bl´ıˇze k bodu x ),
a kdyˇz (xce)< (x ), pak ˆ
x=xce, akˇze p o edeme xw:= xce.
b) jes liˇze (x )≥ (xw), zkus´ıme bod xci =1
2(¯
x+xw) (leˇz´ı bl´ıˇze k bodu xw),
a pokud (xci)< (xw), pak ˆ
x=xci, j. p o edeme xw:= xci.
V´ybˇe bodu xce esp. xci oznaˇcujeme jako kon akci ( doln´ım indexu: p´ısmeno c
pˇ ipom´ın´a anglick´e slo o con ac ion, p´ısmeno eanglick´e slo o ex e nal (xce leˇz´ı nˇe
p˚u odn´ıho simplexu) a p´ısmeno ipˇ ipom´ın´a anglick´e slo o in e nal (xci leˇz´ı u ni ˇ p˚u odn´ıho
simplexu)).
Kdyˇz ne yho uje xe,x ,xce ani xci, usoud´ıme, ˇze chol xb, nˇemˇz ´uˇcelo ´a unkce
nab´y ´a s ´e nejmenˇs´ı hodno y, je bl´ızko minima. P o o p o edeme edukci simplexu: chol
102
xb simplexu z˚us ane a zb´y aj´ıc´ı choly xise posunou do s ˇ ed˚u ´useˇcek xbxi. Simplex
se edy s ´ahne k nejlepˇs´ımu cholu xb.
T ans o maci simplexu, pˇ eds a uj´ıc´ı jeden k ok Nelde o y-Meado y me ody, pop´ıˇseme
pˇe i bodech ak o:
1) expanze : (x )< (xb) a na ´ıc (xe)< (xb) =⇒xw:= xe
2) e lexe : (x )< (xg) p o nˇejak´y chol xg6=xw=⇒xw:= x
3) nˇejˇs´ı kon akce : (x )< (xw) a na ´ıc (xce)< (x ) =⇒xw:= xce
4) ni ˇ n´ı kon akce : (x )≥ (xw) a na ´ıc (xci)< (xw) =⇒xw:= xci
5) edukce : xi:= 1
2(xb+xi) p o ˇsechna xi6=xb
Body 1 aˇz 5 p och´az´ıme pos upnˇe sho a dol˚u. Kdyˇz nˇek e ´a z podm´ınek bodech
1 aˇz 4 nen´ı splnˇena, pˇ ejdeme na n´asleduj´ıc´ı bod. Kdyˇz splnˇena je, p o edeme n´ah adu
xwpodle pˇ ´ıkazu za ˇsipkou a ans o mace je ho o a. Nen´ı-li splnˇena podm´ınka ˇz´adn´em
z bod˚u 1 aˇz 4, p o edeme edukci podle bodu 5.
Na zaˇc´a ku ´ypoˇc u je d´ana poˇc´a eˇcn´ı ap oximace x0= (x(0)
1, x(0)
2,...,x(0)
n)Ta mal´e
ˇc´ıslo δ. Dalˇs´ı choly xis a o ac´ıho simplexu od od´ıme z cholu x0 ak, ˇze k jeho i- ´e
sloˇzce x(0)
ipˇ iˇc eme ˇc´ıslo δ, j. xi= (x(0)
1,...,x(0)
i+δ,...,x(0)
n)T,i= 1,2,...,n.
Simplex opako anˇe ans o mujeme. V´ypoˇce ukonˇc´ıme a chol xbpo aˇzujeme za
dos a eˇcnˇe dob ou ap oximaci minima x∗, pokud jsou choly simplexu na z´ajem dos i
bl´ızko a unkˇcn´ı hodno y nich se m´alo liˇs´ı, j. kdyˇz p o zadan´e ole ance ε1,ε2pla ´ı
kxi−xbk< ε1a souˇcasnˇe | (xi)− (xb)|< ε2p o kaˇzd´y chol xi6=xb.(6.6)
Nelde o a-Meado a me oda je heu is ick´a me oda (heu is ick´y nebo-li obje o ac´ı je
ako ´y pos up, k e ´y je zaloˇzen nejenom na logick´em u aˇzo ´an´ı a zkuˇsenos ech, ale ak´e
na pozo o ´an´ı a expe imen o ´an´ı). Me oda je hodn´a p o minimalizaci unkc´ı menˇs´ıho
poˇc u p omˇenn´ych, ˇ eknˇeme p o n≤10. Pˇ es oˇze o kon e genci me ody je oho zn´amo
jen elmi m´alo, p axe ho oˇ ´ı jej´ı p ospˇech: me oda je aˇz pˇ ek api ˇe ´uspˇeˇsn´a. P o o
je po aˇzo ´ana za me odu spolehli ou nebo-li obus n´ı. Pods a nou ne ´yhodou me ody
je o, ˇze je pomal´a, zejm´ena bl´ızkos i minima. Dalˇs´ı minus pˇ eds a uje elk´y objem
´ypoˇc ˚u. Pˇ es o nejde o m ou me odu, coˇz je zˇ ejm´e napˇ . z oho, ˇze je implemen o ´ana
MATLABu jako unkce minsea ch.
Pˇ ´ıklad 6.3. Funkce (x, y) = 70 [(x−2)4+(x−2y)2] nab´y ´a minima p o x∗= 2, y∗= 1.
V´ypoˇce p o edeme me odou Nelde a-Meada, n´ıˇz z ol´ıme x0= (2,1; 0,7)Taδ= 0,1.
V´ypoˇc y jsou p o ´adˇeny pˇ esnˇe, do abulky 6.1 ˇsak (k ˚uli ´uspoˇ e m´ıs a) zapisujeme
hodno y zaok ouhlen´e na d ˇe dese inn´a m´ıs a. P o kaˇzd´y bod zapisujeme e sloupci pod
sebou x-o ou souˇ adnici, y-o ou souˇ adnici a unkˇcn´ı hodno u. V ´ameˇcku u ´ad´ıme no ˇe
u ˇcen´y lepˇs´ı bod ˆ
x(a unkˇcn´ı hodno u nˇem). P o ε1= 10−4aε2= 10−8 ´ypoˇce konˇc´ı
po 47 k oc´ıch a xb.
= (1,999953; 0,999976)T.
Me oda nej ˇe ˇs´ıho sp´adu je z´akladn´ı minimalizaˇcn´ı me oda, k e ´a pouˇz´ı ´a de i ace
´uˇcelo ´e unkce. Tako ´e me ody se naz´y aj´ı g adien n´ı.
Zaˇcneme ´ım, ˇze si ys ˇe l´ıme obecn´y p incip sp´ado ´e me ody. Pˇ edpokl´adejme edy,
ˇze jsme bodu xka chceme se dos a bl´ıˇze k minimu. Z ol´ıme smˇe dk, nˇemˇz unkce
103
k ok yp xwxgxb¯
x x xexce xci
1 expanze
2,20
0,70
44,91
2,10
0,70
34,31
2,10
0,80
17,51
2,10
0,75
−
2,00
0,80
11,20
1,90
0,85
2,81
2 e lexe
2,10
0,70
34,31
2,10
0,80
17,51
1,90
0,85
2,81
2,00
0,82
−
1,90
0,95
0,01
1,80
1,08
8,69
3 nˇejˇs´ı
kon akce
2,10
0,80
17,51
1,90
0,85
2,81
1,90
0,95
0,01
1,90
0,90
−
1,70
1,00
6,87
1,80
0,95
0,81
4 ni ˇ n´ı
kon akce
1,90
0,85
2,81
1,80
0,95
0,81
1,90
0,95
0,01
1,85
0,95
−
1,80
1,05
6,41
1,88
0,90
0,41
Tab. 6.1: Pˇ ´ıklad 6.3
kles´a, a na polopˇ ´ımce xk+λdk,λ≥0, ybe eme bod
xk+1 =xk+λkdk,(6.7)
nˇemˇz (xk+1)< (xk). Smˇe o ´y ek o dknaz´y ´ame sp´ado ´y ( e smˇe u dkhodno a
´uˇcelo ´e unkce pad´a dol˚u), od ud sp´ado ´a me oda. ˇ
C´ıslo λkse naz´y ´a pa ame d´elky
k oku (je-li dkjedno ko ´y ek o , j. kdyˇz kdkk2= 1, pak λk=kxk+1 −xkk2je zd´alenos
bod˚u xkaxk+1, j. λkje d´elka k oku). λkdos aneme minimalizac´ı unkce ϕ(λ) = (xk+
λdk) p o λ≥0. Minimum λk unkce ϕ(λ) u ˇc´ıme pˇ ibliˇznˇe pomoc´ı nˇekolika m´alo k ok˚u
hodn´e me ody jedno ozmˇe n´e minimalizace (pˇ esn´a minimalizace je zby eˇcn´y pˇ epych,
nebo
’p os ˇ ednic ´ım λku ˇcujeme jen mezi ´ysledek xk+1 na ces ˇe k minimu x∗). U ˇcen´ı
λk edy yj´adˇ ´ıme z´apisem
λk.
= a gmin
λ>0
ϕ(λ),kde ϕ(λ) = (xk+λdk).(6.8)
Nyn´ı se ˇenujme uˇz las n´ı me odˇe nej ˇe ˇs´ıho sp´adu. Je zn´amo, ˇze unkce (x) nej-
ychleji kles´a e smˇe u z´apo n´eho g adien u. Oznaˇc´ıme-li edy g adien jako
g(x)≡ ∇ (x) = ∂ (x)
∂x1
,∂ (x)
∂x2
,...,∂ (x)
∂xnT
,
pak me odˇe nej ˇe ˇs´ıho sp´adu ol´ıme jako sp´ado ´y ek o
dk=−g(xk).(6.9)
V´ypoˇce ukonˇc´ıme a xk+1 po aˇzujeme za uspokoji ou ap oximaci minima x∗, kdyˇz
kg(xk+1)k< ε , (6.10)
104
x3
x2
x1
x0
Ob . 6.5: P incip sp´ado ´ych me od
kde εje pˇ edepsan´a ole ance (pˇ ipomeˇnme, ˇze minimu g(x∗) = o).
V poˇc´a eˇcn´ı ´azi ´ypoˇc u, kdyˇz jsme od minima jeˇs ˇe dos i daleko, doch´az´ı ob ykle
k pomˇe nˇe ychl´emu poklesu hodno ´uˇcelo ´e unkce. Za o bl´ızkos i minima je kon e -
gence pomal´a, jen line´a n´ı, j. pla ´ı kxk+1 −x∗k ≤ Ckxk−x∗k, kde kons an a Cje sice
menˇs´ı neˇz jedna, ale ˇcas o jen nepa nˇe.
Cik-cak e ek . Pokud λk ypoˇc eme pˇ esnˇe, m´a unkce ϕ(λ) bodˇe λkminimum, a p o o
0 = ϕ′(λk) =
n
X
i=1
∂ (xk+1)
∂xi
d(k)
i=−
n
X
i=1
d(k+1)
id(k)
i=−dT
k+1dk,
j. smˇe o ´e ek o y dk+1 adkjsou na z´ajem kolm´e. Uk´aˇzeme si, ˇze p ´a ˇe a o las nos
m˚uˇze b´y pˇ ´ıˇcinou elmi pomal´e kon e gence.
P o jednoduchos pˇ edpokl´adejme, ˇze minimalizujeme unkci d ou p omˇenn´ych. V om
pˇ ´ıpadˇe si m˚uˇzeme ypomoci jednoduchou pˇ eds a ou: nach´az´ıme se e ´enu a chceme
naj´ı nejniˇzˇs´ı bod, j. dno nˇejak´e p ohlubnˇe. Pˇ edpokl´adejme, ˇze p ohlubeˇn m´a a po-
dlouhl´e zahnu ´e okle. Me oda nej ˇe ˇs´ıho sp´adu n´as nasmˇe uje z poˇc´a eˇcn´ıho s ano iˇs ˇe
x0dol˚u kolmo k s e nici (x) = (x0). Ses upujeme ak dlouho, dokud e ´en kles´a.
V nejniˇzˇs´ım m´ıs ˇe je dalˇs´ı s ano iˇs ˇe x1. Zde se zas a ´ıme, o oˇc´ıme se o 90 s upˇn˚u
a ses upujeme zno u dol˚u (kolmo k s e nici (x) = (x1)) do dalˇs´ıho s ano iˇs ˇe x2
a d. Je zˇ ejm´e, ˇze zd´alenos i mezi jedno li ´ymi s ano iˇs i se budou pos upnˇe zk aco-
a . V bl´ızkos i minima bude naˇse pu o ´an´ı p˚usobi smˇeˇsnˇe: m´ıs o abychom do nˇej doˇsli
nˇekolika m´alo k oky, budeme se k nˇemu sp´ıˇse pl´ıˇzi neˇz bl´ıˇzi po ase oˇ en´e ˇc´ım d´al
105