Skripta pracovní verze

bo 1
PoŁet zÆporn ch kołenø: 1
11
PoznÆmka
Postup, kte vede ke konstrukci intervalø v ka dØm z nich le prÆv jeden
nulov bod polynomu Pn se naz vÆ separace kołenø:
Jednou z mo nost je pou it tzv. Bolzanovy v ty op raj c se o vlastnosti
spojitØ funkce s hodnotami s opaŁn mi znamØnky v krajn ch bodech uva-
ovanØho intervalu (viz. tØ metoda bisekce - kap.1.1). Podle n rozd l me
płedchoz mi odhady hranice kołenø z skan interval napł. body o celoŁ sel-
n ch souładnic ch a zkoumÆme znamØnkovØ zm ny v krajn ch bodech t chto
intervalø. V intervalech, v jejich krajn ch bodech mÆ polynom Pn hodnoty s
opaŁn mi znamØnky le kołen tohoto polynomu. Pokud tak v„echny reÆlnØ
kołeny nez skÆme, provedeme zjemn n d len , napł klad pølen m a postup
opakujeme (pozor ma kołeny nÆsobnØ, zejmØna se sudou nÆsobnost !).
Pł klad 2.3 Separujeme reÆlnØ kołeny polynomu P5(x) = x5 2x4 13x3 +
14x2 + 24x 1 v intervalu [ 3;5] płiŁem v me, e tento polynom mÆ 3 nebo
1 kladn a 2 nebo 0 zÆporn ch kołenø. S pou it m Hornerova schematu pro
v poŁet hodnot polynomu obdr me:
1 -2 -13 14 24 -1
-3 1 -5 2 8 0 -1
-2 1 -4 -5 24 -24 47
-1 1 -3 -10 24 0 -1
0
1 1 -1 -14 0 24 23
2 1 0 -13 -12 0 -1
3 1 1 -10 -16 -24 73
4 1 22 -5 -6 0 -1
5 1 3 2 24 144 719
x12( 3; 2) x22( 2; 1) x32(0;1) x42(1;2) x52(4;5)
2.2 UrŁen kołenø
PłedpoklÆdejme nyn , e znÆme poŁet reÆln ch kołenø polynomu Pn i inter-
valy, v nich jsou separovÆny.
Aproximaci jednotliv ch kołenø mø eme provØst napł. metodou bisekce
- viz. kap.1.1, nebo n e uveden mi iteraŁn mi metodami.
a) Newtonova metoda
12
Je-lix(0) poŁÆteŁn aproximace z intervalu separace a dostateŁn bl zkÆ
hledanØmu kołenu, pak posloupnost
x(k+1) = x(k) Pn(x
(k))
P0n(x(k));k = 1;2;::: (2.3)
v n hodnoty Pn a P0n (tj. derivace polynomu Pn) poŁ tÆme s v hodou
s pomoc Hornerova schØmatu, konverguje k hledanØmu kołenu.
PoznÆmky
1. Newtonova metoda (2.3) jako to zvlÆ„tn pł pad Newtonovy me-
tody kap.1.1 b) konverguje kvadraticky
2. Le -li poŁÆteŁn aproximace x0 pł li„ daleko od hledanØho kołene,
lze metodu modi kovat a t m konvergenci zrychlit:
x(k+1) = x(k) 2Pn(x
(k))
P0n(x(k));k = 1;2;::: (2.4)
(tzv.zdvojenÆ metoda).
b) Laquerrova metoda
Tato metoda
{ nevy aduje płedb nou separaci kołenø (v dy konverguje k n kte-
rØmu z kołenø)
{ lze ji pou t i k aproximaci komplexn ch kołenø:
x(k+1)i = x(k)i n
p(xki )
r
(n 1)
h
nq(x(k)i p2(x(k)i )
i; (2.5)
kde
p(x) = P
0
n(x)
Pn(x);q(x) =
(P0n(x))2 Pn(x)P00n(x)
P2n(x)
P0n(x) a P00n(x) jsou 1. a 2. derivace polynomu Pn a znamØnko +
nebo ve jmenovateli zlomku v (2.5) se vybere tak, aby absolutn
hodnota jmenovatele byla v t„ .
13
PoznÆmka
Aproximace v„ech kołenø xi polynomu Pn z skÆme vhodn mi volbami poŁÆ-
teŁn ch aproximac (co nejbl e oŁekÆvanØmu kołenu).
Pł klad 2.4 U it m Laquerrovy metody hledejme kołeny polynomu P3(x) =
x3 +x2 +x+ 1
1. volbou x0 = 1 a a pomoc Hornerova schematu
P3(1) = 4;P03(1) = 6;P003 (1) = 8
odtud pak p(1) = 3=2;q(1) = 1=4 a tedy
x(1)1 = 1 3
3=2
q
2(3=4 9=4)
= ::: = 1=7(1 + 4p3i) :=
:= 0;142857 + 0;989743i
a dÆle
p(x(1)1 ) = 4(30 p3i);q(x(1)1 ) = 16(769 + 60p3i);x(2)1 =
= 0;000166 + 0;999999i
2. volbou x(0)2 = 0 postupn
x(1)2 = 0;333333 0;942808i
x(2)2 = 0;142544 0;845623i
x(3)2 = 0;000589 0;999942i
3. volbou x(0)3 = 3 postupn
x(1)3 = 0;692307
x(2)3 = 1;012420
x(3)3 = 1;000000:
Płitom kołeny jsou i, i, 1.
14
PoznÆmky
1. Proto e s ka d m komplexn m kołenem polynomu Pn je kołenem i Ł slo
komplexn sdru enØ, staŁ proces aproximace pro dvojici komplexn ch
kołenø jeden. Pro v poŁet meziv sledkø je v hodnØ v konkrØtn situaci
pravou stranu formule 2.5 upravit. V na„em pł kladu 2.4 pak
x(k+1)i = R(x(k)i);k = 1;2;:::;
kde
R(x) = x 3(x
2 +x2 +x+ 1)
3x2 + 2x+ 1
q
8(x2 + 4x+ 1)
15
Kapitola 3
e„en systØmø nelineÆrn ch
rovnic
Hledejme łe„en systØmu m obecn nelineÆrn ch rovnic o m neznÆm ch
x1;:::;xm:
f1(x1;:::;xm) = 0
... ...
fm(x1;:::;xm) = 0 (3.1)
UspołÆdanou m-tici Ł sel (x0;1;:::;x0m) nazveme łe„en m tohoto sys-
tØmu, jestli e Ł sla x01;:::;x0m vyhovuj rovnic m (3.1)
OznaŁ me-li F = (f1;:::;fm)T, x = (x1;:::;xm), 0 = (0;:::;0)T a x0 =
(x01;:::;x0m) pak systØm (3.1) lze zapsat ve vektorovØm tvaru
F(x) = 0 (3.2)
a jeho łe„en m je x02Rm takovØ, e F(x0) = 0.
Analogicky s kapitolou 1 płiład me k systØmu (3.1) systØm
x1 = g1(x1;:::;xm)
... ...
xm = gm(x1;:::;xm) (3.3)
resp:x = G(x)
tak, aby łe„en x0 systØmu (3.1) vyhovovalo i systØmu (3.3) a naopak. e„en
systØmu (3.3) płitom naz vÆme pevn bod zobrazen G.
16
3.1 IteraŁn metody
Volbou funkc g1;:::;gm z skÆme røznØ metody pro v poŁet łe„en , płiŁem
bude-li płidru en iteraŁn proces ve tvaru
x(k+1) = G(xk;xk 1;:::;xk l+1) (3.4)
ł kÆme, e iteraŁn proces je l-krokov .
3.2 Metoda prostØ iterace
Z Banachovy v ty o kontrakci, z tzv. principu pevnØho bodu zobrazen G
plyne
V ta 3.1 Nech» zobrazen G = (g1;:::;gm)T : Rm!Rm je kontrakce, tj.
(G(x);G(y)) q (x;y) pro kadx;y2Rm;
kde x = (x1;:::;xm);y = (y1;:::;ym); (x;y) = maxfjxi yij: i = 1;:::;mg
je vzdÆlenost v prostoru Rm a q2[0;1) konstanta.
Pak pro ka dou poŁÆteŁn aproximaci x0 = (x01;:::;x0m)2Rm je posloup-
nost
n
x(k)
o1
k=0 R
m de novanÆ vzorcem (3.4), tj.
x(k+1) = G(xk);k = 0;1;:::
konvergentn a jej limita limk!+1x(k) = x0 je pevn bod zobrazen G.
PoznÆmky
1. K napln n podm nky kontraktivnosti zobrazen G za płedpokladu spo-
jitosti 1. parciÆln ch derivac v„ech komponent g1;:::;gm zobrazen G
alespo v n jakØm okol o(x0) płedpoklÆdanØho łe„en x0 staŁ , aby pro
i;j = 1;:::;m

@gi(x)@x
j



q
mvo(x0);
kde q2[0;1) a souŁasn je tłeba vybrat x02o(x0).
2. Płedchoz podm nku lze naplnit, jestli e v n jakØm okol o(x0) płedpo-
klÆdanØho łe„en x0 plat
max
8<
:
mX
j=1



@gi
@xj


: i = 1:::;m
9=
; q< 1:
17
3. pokud vybereme poŁÆteŁn aproximaci x0 pł li„ daleko od płedpo-
klÆdanØho łe„en x0, mø e iteraŁn proces divergovat a nebo oscilovat.
Pł klad 3.1 e„me systØm nelineÆrn ch rovnic
x21 2x1 x2 + 1=2 = 0
x21 + 4x22 4 = 0:
Z geometrickØho nÆzoru na œlohu - jednÆ se o v poŁet prøseŁ kø dvou kłivek
dan ch t mito rovnicemi (prvn je parabola, druhÆ elipsa) - plyne, e œloha
mÆ dv łe„en : Toho vyu ijeme ke konstrukci vhodn ch funkc q1 a q2 nejdł ve
ObrÆzek 3.1: Soustava nelineÆrn ch rovnic
pro pł pad łe„en s x1 < 0 a x2 > 0:
g1(x1;x2) = x
2
1 x2 + 0;5
2
g2(x1;x2) = x
2
1 4x
2
2 + 8x2 + 4
8 :
Postupn dostaneme:
18
x11 = g1(x01;x02) = 0;25 x12 = g2(x01;x02) = 1
x21 = g1(x11;x12) = 0;21875 x22 = g2(x11;x12) = 0;9921875
... ...
x81 = g1(x71;x72) = 0;2222145 x82 = g2(x71;x72) = 0;9938084
x91 = g1(x81;x82) = 0;2222146 x92 = g2(x81;x82) = 0;9938084
Pokud bychom cht li naj t druh prøseŁ k, museli bychom zm nit iteraŁn
funkce, abychom zajistili konvergenci. Mo nÆ volba je napł.:
x1 = g1(x1;x2) = x
2
1 + 4x1 +x2 0;5
2
x2 = g2(x1;x2) = x
2
1 + 4x
2
2 + 11x2 + 4
11
3.3 Newtonova metoda
Polo me
G(x) = x J 1F (x)F(x);
Kde J 1F (x) je matice inverzn k tzv. Jacobiov matici zobrazen F =
(f1;:::;fm)
JF(x) =
0
BB
B@
@f1(x)
@x1 :::
@f1(x)
@xm.
.. ...
@fm(x)
@x1 :::
@fm(x)
@xm
1
CC
CA
Za płedpokladu, e JF(x) je v n jakØm okol o(x0) płedpoklÆdanØho łe„en
x0 regulÆrn a se spojit mi prvky, pak Newtonovou iteraŁn metodou pro
łe„en sytØmu (3.1) rozum me iteraŁn proces
x(k+1) = x(k) J 1F (x(k))F(x(k)); k = 0;1;::: (3.5)
V ta 3.2 Je-li JF(x) regulÆrn matice se spojit mi prvky v n jakØm okol
o(x0) łe„en x0 systØmu (3.1), pro v„echna x2o(x0) existuje konstanta K
takovÆ, e
J 1(x)

K
a funkce f1;:::;fm maj v o(x0) spojitØ 2.parciÆln derivace, pak pro po-
ŁÆteŁn aproximaci x(0) 2 o(x0) posloupnost
n
x(k)
o1
k=0 urŁenÆ NewtonovouiteraŁn metodou konverguje k łe„en x
0, tj. limk!+1 = x0.
19
PoznÆmky
1. Æd metody je 2.
2. IteraŁn proce lze zapsat ve tvaru systØmu lineÆrn ch rovnic, v hodn j-
„ m pro v poŁet:
JF(x(k)) k = F(xk);
v n m k = x(k+1) x(k): Pak x(k+1) = x(k) + k;k = 0;1;:::.
Pł klad 3.2 pro nalezen 2.łe„en v pł kladu 3.1 (s x1 > 0 a x2 > 0) s
pou it m Newtonovy iteraŁn metody je
F(x1;x2) =
x2
1 2x1 x2 + 1=2
x2 + 4x22 4
!
;
JF(x1;x2) =
2x
1 2 1
2x1 8x2
!
:
Zvolme poŁÆteŁn aproximaci (x01;x02) = (2; 0;25), tak e
F(2; 0;25) =
0;25
0;25
!
; JF(2; 0;25) =
2;0 1;0
4;0 2;0
!
:
e„ me tedy systØm
2;0 1;0
4;0 2;0
!
1
2
!
=
0;25
0;25
!
e„en je 1 = 0:09375; 2 = 0::625 tj.
x1 =
2;0 0:09375
0;25 + 0:0625
!
=
1:90625
0;3125
!
:
Dal„ m postupem dostaneme
x2 =
1:900691
0:311213
!
; x3 =
1:900677
0:311219
!
; x4 =
1:900677
0:311219
!
20
Kapitola 4
e„en lineÆrn ch systØmø
Hledejme łe„en systØmø lineÆrn ch rovnic
a11x1 +a12x2 +:::+a1nxn = b1
...
an1x1 +an2x2 +:::+annxn = bn
(4.1)
kde aij a bi (i;j = 1;:::;n) jsou reÆlnØ konstanty a x1;:::;xn neznÆmØ.
Płi oznaŁen
A =
0
BB
@
a11 ::: a1n
... ...
an1 ::: ann
1
CC
A; b = (bb;:::;bn)T; x = (x1;:::;xn)T
lze systØm (ro5.1) płepsat ve tvaru
Ax = b (4.2)
Z obecnØ teorie lineÆrn ch systØmø płipome me
V ta 4.1 SystØm (4.1) mÆ jedinØ łe„en , prÆv kdy matice A je regulÆrn
(tj. mÆ determinant jAj røzn od nuly).
V ta 4.2 SystØm (4.1) mÆ alespo jedno łe„en , jestli e hodnost matice A
je rovna hodnosti roz„ łenØ matice systØmu, tj. Ajb (tzv. Frobeniova v ta).
PoznÆmky
1. Celkov poŁet operac nÆsoben v GEM je
1=6(2n3 + 3n2 5n) + 1=2(n2 +n) n
3
3
21
a sŁ tÆn a odeŁ tÆn
1=3(2n3 + 3n2 5n) n
3
3
je złejmØ, e poŁet aritmetick ch operac velmi rychle roste s rostouc m
n. Tento fakt ukazuje pro n kterÆ n nÆsleduj c tabulka
n nÆsoben /d len sŁ tÆn /odeŁ tÆn
3 17 11
5 65 50
10 430 375
50 44150 42875
100 343300 338250
2. V pł pad , e pod diagonÆlou vyb ran prvek ars nemø e b t nenu-
lov , v metod nelze pokraŁovat. problØm lze odstranit vhodnou v -
m nou poład rovnic. Pak lze dosÆhnout toho, e pro œpravy vyb ranØ
prvky (tzv. pivoty) jsou nenulovØ. nav c je lze s v hodou volit tak, aby
jejich absolutn hodnoty byly co nejv t„ .
3. Dal„ problØmy nastÆvaj v pł padech, kdy absolutn hodnota pivota
je bl zkÆ nule (viz. tØ odstavec b).
4. Celkov poŁet operac podstatn klesne, je-li matice A speciÆln , napł.
symetrickÆ, pozitivn de nitn , pÆsovÆ, :::
5. GEM se vyu vÆ i pro konstrukce łe„en inverzn ch matic a v poŁet
determinantø.
4.1 Pł mØ metody
Hlavn my„lenka nejznÆm j„ pł mØ metody pro łe„en systØmø lineÆrn ch rov-
nic, tzv. Gaussovy eliminaŁn metody, je płeveden pøvodn ho systØmu
(4.1) vhodn mi œpravami na systØm s horn trojœheln kovou matic . ten pak
vede snadno k łe„en . Postup aplikujeme na roz„ łenou matici systØmu:
(Ajb) =
0
BB
BB
@
a11 ::: a1n
a21 ::: a2n
... ...
an1 ::: ann





b1
b2
...
bn
1
CC
CC
A
tzv. ekvivalentn mi œpravami:
22
(i) urŁ me prvek ar16= 0; r = 1;:::;n
(ii) vym n