Skripta pracovní verze

Kapitola 1
e„en nelineÆrn ch rovnic
PłedpoklÆdejme, e f je funkce (płesn ji reÆlnÆ funkce jednØ reÆlnØ pro-
m nnØ). ReÆlnØ Ł slo nazveme kołenem (nulov m bodem) tØto funkce,
jestli e f( ) = 0.
HledÆn kołenø (nulov ch bodø) funkce f tedy znamenÆ hledÆn Ł sel x,
pro n
f(x) = 0: (1.1)
Prvn m krokem \łe„en rovnice" (1.1) je hledÆn intervalø, v nich le
v dy prÆv jeden kołen tØto rovnice - tzv. separace kołenø a druh m urŁen
kołene, nebo alespo jeho aproximace.
Proto e v poŁet płesnØ hodnoty kołene je mo n jen za v jimeŁn ch
podm nek (napł. u polynomu stupn 2 nebo 3, u vy„„ ch nelze...) budeme se
zab vat płibli n m v poŁtem hodnot kołenø funkce f.
1.1 Metoda pølen intervalu (bisekce)
Tato metoda se op rÆ o jednu ze zÆkladn ch v t diferenciÆln ho poŁtu funkc
jednØ prom nnØ, tzv. Bolzanovu v tu:
V ta 1.1 Nech» je funkce f spojitÆ na uzavłenØm intervalu [a;b] a v krajn ch
bodech tohoto intervalu nab vÆ hodnot s opaŁn mi znamØnky. Pak uvnitł
intervalu [a;b] le nulov bod funkce f.
PłedpoklÆdejme nyn , e jsme na„li interval [a;b] na n m je uva ovanÆ
funkce spojitÆ a f(a) f(b) < 0. Podle płedchoz v ty existuje c2(a;b) tak,
e f(c) = 0 a pro zjednodu„en płedpoklÆdejme, e je jedin .
1
Postup metody pølen intervalu (bisekce)
1. krok: rozd l me interval [a;b] na poloviny a vypoŁteme f(a+b2 )
pokud f(a+b2 ) = 0 (pł p. s po adovanou płesnost ), mÆme łe„en
(aproximaci łe„en ) c = a+b2
pokud f(a) f(a+b2 ) < 0 oznaŁ me a1 = a, b1 = a+b2 , v opaŁnØm
pł pad vol me a1 = a+b2 , b1 = b
2. krok: postup opakujeme na intervalu [a1;b1] s t m, e pł p. dal„ d lŁ
interval oznaŁ me [a2;b2] atd.
Złejm tak po koneŁn mnoha kroc ch najdeme aproximaci hledanØho
nulovØho bodu s po adovanou płesnost , nebo» pro intervaly [ak;bk] a hledan
kołen plat :
[a;b] [a1;b1] ::: [a1;b1] [a1;b1] :::
a a a1 ::: ak ; bk ::: b1 b,
płiŁem bk ak = 1=2(bk 1 ak 1) = ::: = 1=2k(b a);k = 1;2;::: a proto
lim
k!+1
(bk ak) = 0
a
lim
k!+1
bk = lim
k!+1
ak = :
PoznÆmky
1. Z uvedenØho postupu plyne, e Ł slo ck = ak+bk2 , z skanØ v k-tØm kroku
(c1 = a+b2 ), aproximuje hledan kołen s płesnost 12k+1 (b a).
2. Je-li > 0 po adovanÆ płesnost aproximace, pak kritØriem pro zasta-
ven v poŁtu mø e b t podm nka

ck+1 ck
ck

< ;
nebo
jck+1 ckj< ;
nebo
jf(ck)j< :
3. Płedpoklad metody (spojitost f a vlastnost znamØnek funkŁn ch hod-
not v krajn ch bodech uva ovanØho intervalu) jsou nezbytnØ!
2
Pł klad 1.1 Metodou bisekce najd te kołen funkce f(x) = x3 x 1 le c
v intervalu [1;2].
n an bn bn an
0 1,000000 2,000000 1,000000
1 1,000000 1,500000 0,500000
2 1,250000 1,500000 0,250000
3 1,250000 1,375000 0,125000
4 1,312500 1,375000 0,062500
5 1,312500 1,343750 0,031250
6 1,312500 1,328125 0,015625
7 1,320312 1,328125 0,007812
1.2 IteraŁn metody
IteraŁn metody hledÆn kołenø rovnice 1.1, tj. f(x) = 0, jsou zalo eny na
vyjÆdłen œlohy œlohou jinou, ale s n ekvivalentn .
K rovnici (1.1) płiła me rovnici
x = q(x) (1.2)
takovou, e kołen rovnice (1.1) vyhovuje i rovnici (1.2) a naopak. Płitom
q je op t funkce (płesn ji reÆlnÆ funkce reÆlnØ prom nnØ).
¨ slo , pro n = q( ) (tj. je łe„en m rovnice 1.2) naz vÆme pevn
bod funkce g.
O existenci a pł padn jednoznaŁnosti pevnØho bodu funkce g plat :
V ta 1.2 Nech» g je spojitou funkc zobrazuj c uzavłen interval [a;b] do
sebe. Pak mÆ g alespo jeden pevn bod.
Je-li nav c g kontraktivn (tj. jg(x) g(y)j qjx yj pro ka dØ x;y 2
[a;b] a q2[0;1)), pak q mÆ v intervalu [a;b] jedin pevn bod.
PoznÆmka
Jestli e mÆ funkce g na intervalu [a;b] 1.derivaci v absolutn hodnot ohrani-
Łenou Ł slem q, tj.jg;(x)j q pro8x2[a;b] a q2[0;1), pak je g kontraktivn
na [a;b].
Pł klad 1.2 Funkce g(x) = 3 x mÆ na intervalu [0;1] pevn bod, nebo»
i) je na tomto intervalu spojitÆ a klesaj c (g;(x) = 3 x ln 3 < 0)
ii) zobrazuje interval [0;1] do sebe g(1) = 13 g(x) 1 = g(0)
3
Tento pevn bod je jedin , i kdy g nen na tomto intervalu kontraktivn
(jg;(x)j= 3 x ln 3 a pro x = 0 je jg;(0)j= ln 3 > 1; jednoznaŁnost pevnØho
bodu je døsledkem monotonie g).
PoznÆmky
1. e„it rovnici (1.2), tj. x = g(x), geometricky znamenÆ hledat prøseŁ ky
pł mky o rovnici y = x s kłivkou o rovnici y = g(x).
2. Pro pł klad 1.2 to znamenÆ:
ObrÆzek 1.1: g(x) = 3 x
1.3 Metoda prostØ iterace
PłedpoklÆdejme, e funkce g je spojitÆ a zobrazuje interval [a;b] do sebe
a oznaŁme x0 2 [a;b] libovoln bod (tzv. poŁÆteŁn aproximace). Pak
posloupnost
n
x(k)
o1
k=1 de novanou formul
xk+1 = g(x(k));k = 1;2;::: (1.3)
naz vÆme posloupnost iterac , funkcig iteraŁn funkc a postup (1.3)
iteraŁn metodou nebo metodou prostØ iterace.
4
PoznÆmky
1. IteraŁn metoda (1.3) je tzv. jednokrokovÆ iteraŁn metoda x(k+1) zÆvis
pouze na xk, tj. jednØ płedchoz iteraci
2. Jestli e
x(k+1) = g(x(k);x(k 1):::;x(k l+1));k = 1;2;::: (l 2)
mluv me o l-krokovØ metod . K urŁen a porovnÆvÆn rychlosti konvergence
iteraŁn ch metod slou tzv. łÆd iteraŁn metody:
Je-li hledan pevn bod funkce q a x(k) jeho k-tÆ aproximace, oznaŁme
lk = x(k) (k = 1;2;:::)
tzv. chybou k-tØ iterace. PłedpoklÆdejme, e metoda (1.3) konverguje, tj.
limk!+1xk = .
Existuje-li Ł slo p 1 takovØ, e
lim
k!+1

x(k+1)


jx(k) j =

l(k+1)



l(k)

p
= C6= 0
ł kÆme, e danÆ iteraŁn metoda je łÆdu p pro bod (konstanta C se naz vÆ
asymptotickÆ konstanta chyby).
V ta 1.3 Nech» jsou spln ny płedpoklady V ty1.2. Pak pro libovolnou po-
ŁÆteŁn aproximaci x2 [a;b] je posloupnost
n
x(k+1)
o1
k=1;x
k+1 = g(xk);k =
1;2;::: konvergentn a limk!+1xk = je pevn bod funkce g.
PoznÆmky
1. Za płedpokladø V ty 1.2 je łÆd iteraŁn metody alespo p 1
2.
x(k) qk
1 q

x(0) x(1)

;k = 0;1;:::
a proto pro q bl zkØ 0 (bl zkØ 1) je konvergence rychlØ (pomalØ) a v „e
uvedenØ nerovnosti lze pou t jako kriterium k zastaven v poŁtu
3. Nejsou-li spln ny podm nky V ty 1.2, mø e metoda jak divergovat, tak
oscilovat (iterace vytvÆł cyklus).
5
1.4 Newtonova metoda
Volbou
g(x) = x f(x)f0(x)
za płedpokladu, e funkce f mÆ na intervalu [a;b] nenulovou derivaci, obdr-
me tzv. Newtonovou iteraŁn metodou (neboli metodou teŁen):
x(k+1) = x(k) f(x
(k))
f0(x(k));k = 1;2;::: (1.4)
V ta 1.4 PłedpoklÆdejme, e funkce f mÆ na intervalu [a;b] spojitou 2.deri-
vaci a pro kołen 2 [a;b] rovnice f(x) = 0 je f0( ) 6= 0.Pak existuje > 0
tak, e posloupnost
n
x(k)
o1
k=1 generovanÆ Newtonovou metodou konverguje k
bodu pro ka dou poŁÆteŁn aproximaci x(0)2[ ; + ]\[a;b]
PoznÆmka
V døsledku V ty 1.4 Newtonova metoda je druhØho łÆdu pro jednoduch
kołen .
Pł klad 1.3 Newtonovou metodou nalezneme kołen funkce f(x) = x3 x 1
na intervalu [a;b]:
k xk f(xk)
0 2 2,000000
1 1;54 1,145755071
2 1,359614916 0,153704934
3 1,325801345 0,004624917
4 1,324719049 0,000004658
5 1,324717957 2;2204 16
PoznÆmky
a) Jsou-li spln ny płedpoklady V ty 1.4, pak

x(k+1)

M2m(x(k) )2
a
x(k+1) M
2m(x
(k+1) x(k))2
6
kde
M = maxfjf00(x)j: x2[ ; + ]\[a;b]g
a
m = minfjf0(x)j: x2[ ; + ]\[a;b]g
b) Newtonova metoda po aduje stanoven poŁÆteŁn aproximace x0 bl zko
od oŁekÆvanØho łe„en . NevhodnÆ volba x0 mø e vØst ke zcela chybn m
v sledkøm.
Pł klad 1.4 Hledejme Newtonovou metodou k Ł slu a Ł slo 1=a, tj. łe„me
rovnici f(x) = 1=x a = 0.
Złejm g(x) = x(2 ax) a napł. pro a = 10 le kołen v intervalu I =
[10 2;1] nebo» f(10 2)I(1) < 0. DÆle f0(x) = 1x2 < 0 na I, tj. kołen funkce
je na I jedin a f00(x) = 2x3 > 0 na I. Proto zvolme x0 = 10 2.
Proto:
x(0) = 0;01
x(1) = 0;019
x(2) = 0;03439
x(3) = 0;08147
...
x(7) = 0:099882
tedy x(k)! = 0:1
Płi volb x(0) = 1 v„ak:
x(0) = 1 x(1) = 8
x(2) = 656
x(3) = 4304672
...
Pł klad 1.5 e„te rovnici arctan(x) = 0. Je złejmØ, e kołen 2[a;b];a<
0;b> 0, nebo» arctan(a) < 0, arctan(b) > 0. DÆle
f0(x) = 11 +x2;f00(x) = 2x(1 +x2)
V me, e kołen = 0, ale vy„etłeme tento pł pad podrobn ji. Prvn deri-
vace je stÆle kladnÆ, druhÆ derivace m n znamØnko v bod 0. IteraŁn funkce
pro Newtonovu metodu je tvaru
g(x) = x (1 +x2) arctan(x)
7
ObrÆzek 1.2: f(x)=arcgt(x)
a Newtonova iteraŁn metoda
xk+1 = xk (1 + (xk)2) arctan(xk):
Zvolme poŁÆteŁn aproximaci x0 = 1;5. V slednØ iterace jsou
k xk f(xk)
1 1,5 0,982793723
2 -1,6940796 -1,037546359
3 2,321126961 1,164002042
4 -5,114087837 -1,377694529
Złejm tato posloupnost nekonverguje ke kołenu = 0. Døvodem je fakt,
e g0 = 2 arctan(x) a na intervalu [ 1;5; 1;5] tedy nen spln na podm nka
kontraktivnosti

g0

q < 1. Uva ujme nyn interval [ 0;75; 0;75]. Funkce
g zobrazuje tento interval do sebe a

g0

q < 1 na tomto intervalu. Podle
v ty 1.4 posloupnost urŁenÆ iteraŁn metodou bude konvergovat pro ka dou
poŁÆteŁn aproximaci x0 = 0;75. Posloupnost iterac
8
k xk f(xk)
1 0,75 0,643501109
2 -0,255470482 -0,250120688
3 0,010974374 0,010973934
4 8;81125 10 7 8;81125 10 7
konverguje k bodu = 0.
9
Kapitola 2
Kołeny polynomø
Polynomem Pn = Pn(x) stupn n rozum me funkci
Pn(x) = a0xn +a1xn 1 +:::+an 1x+an (2.1)
kde a0;:::;an2R jsou tzv. koe cienty polynomu P, a06= 0 a x je prom nnÆ.
¨ slo (reÆlnØ nebo komplexn ) nazveme kołenem nebo nulov m bo-
dem polynomu Pn, jestli e
Pn( ) = 0:
Ze zÆkladn ch tvrzen teorie polynomø plyne, e
V ta 2.1 Polynom Pn stupn n s reÆln mi koe cienty mÆ prÆv n kołenø,
poŁ taje v to kołeny reÆlnØ i komplexn vŁetn jejich nÆsobnost .
2.1 Hranice kołenø a jejich separace
OznaŁme
A = maxfja1j;:::;janjg;
B = maxfja0j;:::;jan 1jg
V ta 2.2 Nech» a0an6= 0. Pak pro v„echny kołeny k polynomu Pn plat
1
1 + Bjanj j kj 1 +
A
ja0j (2.2)
Pł klad 2.1 UrŁeme hranice kołenø polynomu
P(x) = x6 2x5 + 8x4 + 3x3 x2 +x 10:
10
A = max(2;8;3;1;1;10) = 10
B = max(1;2;8;3;1;1) = 8
5
9 =
1
1 + 810 j kj 1 +
10
1 = 11
PoznÆmka
Hranice kołenø k polynom Pn lze urŁit takØ s pomoc jin ch odhadø:
a)
j kj max
8
<
:1;
nX
j=1

aj
a0


9
=
;
j kj 2max
(
a1
a0

;
s


a2
a0

; 3
s


a3
a0

;:::; n
s


an
a0


)
j kj max

an
a0

;1 +

an 12
a0

;:::;1 +

a1
a0



:
b) v„echny reÆlnØ kołeny polynomu Pn s an > 0 le v intervalu

Aa
n
1; Aa
n
+ 1

kde
A = maxfjaij: i = 0;:::;ng
Zpłesn n poŁtu kladn ch a zÆporn ch kołenø polynomu P obsahuje
V ta 2.3 (Descartes). PoŁet kladn ch kołenø polynomu P (poŁ tÆno s nÆ-
sobnost ) je roven poŁtu znamØnkov ch zm n v posloupnosti koe cientø a0,:::,an
nebo o sudØ Ł slo men„ . Jsou-li v„echny koe cienty a0;:::;an røznØ od nuly,
pak poŁet zÆporn ch kołenø je roven poŁtu zachovÆn znamØnek v tØto po-
sloupnosti nebo o sudØ Ł slo men„ .
Pł klad 2.2 Odhadn te poŁet kladn ch a zÆporn ch kołenø polynomu
P(x) = x6 2x5 + 8x4 + 3x3 x2 +x 10
Posloupnost koe cientø: 1; 2;8;3; 1;1 10
PoŁet kladn ch kołenø: 5 nebo 3 ne