Numerické metody
Jiří Zelinka
jaro 2019
Jiří Zelinka Numerické metody 1 / 19
Literatura
Horová I., Zelinka J.: Numrické metody, 2. rozšířené
vydání, MU, 2004
Ralston A.: Základy numerické matematiky, Academia,
1978
Vitásek E.: Numerické metody, SNTL, 1987
Mathews, J.H., Fink, K.D.: Numerical methods using
MATLAB, Pearson Prentice Hall, 2003
Stoer, J., Bulirsch R.: Introduction to Numerical Analysis,
Spriger, 1992
Jiří Zelinka Numerické metody 2 / 19
Osnova
Řešení nelineárních rovnic
Polynomy
Řešení soustav lineárních rovnic – iterační metody
Řešení soustav nelineárních rovnic
Řešení soustav lineárních rovnic – přímé metody
Předpoklady
Lineární algebra
Diferenciální počet v R (Rn
)
Integrální počet v R
Jiří Zelinka Numerické metody 3 / 19
Chyby
x: přesná hodnota, ˜x: aproximace x
x − ˜x: absolutní chyba ˜x, |˜x − x| ≤ α: odhad absolutní chyby
x−˜x
x
: relativní chyba, x−˜x
x
≤ δ: odhad relativní chyby
Řekneme, že aproximace ˜x čísla x má s platných cifer, jestliže
s je největší celé nezáporné číslo takové, že platí
x − ˜x
x
≤ 5.10−s
.
Nechť x je reálné číslo, které má obecně nekonečné dekadické
vyjádření. Číslo x(d)
, které má d desetinných míst, je správně
zaokrouhlenou hodnotou čísla x, platí-li
|x − x(d)
| ≤
1
2
10−d
.
Ve správně zaokrouhleném čísle jsou všechny cifry platné.
Jiří Zelinka Numerické metody 4 / 19
Podmíněnost úloh
Řekneme, že korektní úloha je dobře podmíněna, jestliže malá
změna ve vstupních datech vyvolá malou změnu výstupu. Je-li
y + ∆y resp. y výstupní hodnota odpovídající vstupním datům
x + ∆x resp. x, potom číslo
Cp =
∆y
y
∆x
x
=
|relativní chyba na výstupu|
|relativní chyba na vstupu|
nazýváme číslem podmíněnosti úlohy. Je-li Cp ≈ 1, je úloha
velmi dobře podmíněna. Pro velká Cp (> 100) je úloha špatně
podmíněna.
Jiří Zelinka Numerické metody 5 / 19
Typické špatně podmíněné úlohy:
dělení malým číslem
odečítání dvou přibližně stejných čísel
zvětšování chyby v iteračním výpočtu
An = n · An−1
Jiří Zelinka Numerické metody 6 / 19
Celková chyba výpočtu
Daný
problém
Matematická
formulace
Numerická
metoda
Algoritmus- - Y
= F(x1, . . . , xn) y = f (x1, . . . , xn) ˜y = ˜f (˜x1, . . . , ˜xn)
Y − y: chyba metody
f (x1, x2, . . . , xn) − f (˜x1, . . . , ˜xn): chyba primární
f (˜x1, . . . , ˜xn) − ˜f (˜x1, . . . , ˜xn): chyba sekundární
Odhad primární chyby:
|f (x1, . . . , xn) − f (˜x1, . . . , ˜xn)| ≤
n
i=1
Ai αi ,
kde
Ai = sup
∂f
∂xi
(x1, . . . , xn) , i = 1, . . . , n.
Jiří Zelinka Numerické metody 7 / 19
Symbolika O, o
f – funkce definovaná v okolí B(a) bodu a ∈ −∞, ∞
g – funkce nenulová v prstencovém okolí bodu a
f (x) = O(g(x)) pro x → a ∃K : |f (x)| ≤ K|g(x)| v B(a).
Význam: funkce f se v okolí bodu a chová „podobně“ jako
funkce g.
f (x) = o(g(x)) pro x → a lim
x→a
|f (x)|
|g(x)|
= 0 .
Význam: funkce f konverguje v bodě a k nule „rychleji “ než
funkce g.
Jiří Zelinka Numerické metody 8 / 19
Podobně
an = O(bn) nebo an = o(bn) pro n → ∞ ,
kde an, bn jsou prvky posloupností.
Dodatek „pro x → a“ se často vynechává, pokud je jasné,
o které a se jedná. Např. an = O(1/n), f (h) = o(h3
).
Příklad:
an = O(1): ohraničená posloupnost
f (h) = o(1): funkce mající v 0 nulovou limitu
Jiří Zelinka Numerické metody 9 / 19
Taylorův rozvoj
f (x + h) = f (x) + f (x)h +
f (ξ)
2
h2
f (x+h) = f (x)+f (x)h+O(h2
), f (x+h) = f (x)+f (x)h+o(h)
Početní pravidla:
O(g) + O(g) = O(g)
o(g) + o(g) = o(g)
O(g1) · O(g2) = O(g1 · g2)
O(g1) · o(g2) = o(g1 · g2)
o(g) = O(g)
Jiří Zelinka Numerické metody 10 / 19
Řešení nelineárních rovnic
Motivační příklad
Pro kružnici k1 o poloměru r sestrojte kružnici k2 se středem
na kružnici k1 tak, aby oblast ohraničena oběma kružnicemi
měla poloviční obsah než vnitřek kružnice k1.
r x
k1
k2
Jiří Zelinka Numerické metody 11 / 19
Úloha ze starého Egypta
Stojíš před stěnou, za kterou je studna Lotosu jako kruh
Slunce. Vedle studny je položen jeden kámen, jedno dláto a
dva stvoly třtiny. Jeden stvol je dlouhý tři míry, druhý je
dlouhý dvě míry. Stvoly (opřené ve stabilní poloze v diametrálně
protilehlých bodech na okraji dna) se kříží na povrchu vody ve
studni Lotosu a ten povrch je jednu míru nade dnem. Kdo určí
velikost nejdelší délky, kterou lze umístit do dna studny
Lotosu, ten si vezme oba stvoly a bude knězem boha Ra.
Jiří Zelinka Numerické metody 12 / 19
Řešení nelineárních rovnic
Řešíme rovnici f (x) = 0 na uzavřeném intervalu I = [a, b],
pro reálnou spojitou funkci f , ξ – řešení rovnice,
Iterační proces: vytváříme posloupnost (xk)∞
k=0, xk → ξ.
(xk)∞
k=0 – iterační posloupnost.
Metoda půlení intervalu – bisekce
f (a) · f (b) ≤ 0, a0 = a, b0 = b, položíme x0 = (a0 + b0)/2.
Pokud f (a0) · f (x0) ≤ 0 volíme
a1 = a0, b1 = x0, jinak
a1 = x0, b1 = b0,
tedy ξ ∈ [a1, b1].
Jiří Zelinka Numerické metody 13 / 19
Obecně: známe ak, bk, f (ak) · f (bk) ≤ 0, tedy ξ ∈ [ak, bk],
položíme xk = (ak + bk)/2.
Pokud f (ak) · f (xk) ≤ 0 volíme
ak+1 = ak, bk+1 = xk, jinak
ak+1 = xk, bk+1 = bk,
tedy ξ ∈ [ak+1, bk+1].
Odhad absolutní chyby v k-tém kroku:
|xk − ξ| ≤
b − a
2k+1
Algoritmus končí, pokud je absolutní chyba dostatečně malá.
Jiří Zelinka Numerické metody 14 / 19
Metoda pevného bodu, prostá iterační metoda
Tato metoda se používá pro rovnici x = g(x)
Funkce g je spojitá na I = [a, b]
Řešení ξ této rovnice nazýváme pevným bodem funkce
g
Iterační proces
Zvolíme x0 ∈ I a položíme x1 = g(x0)
Obecně xk+1 = g(xk)
Funkce g se nazývá iterační funkce
Jiří Zelinka Numerické metody 15 / 19
Geometrická interpretace
Pevný bod ξ je průsečík grafu funkce g a přímky y = x.
0 0.2 0.4 0.6 0.8 1 1.2 1.4
0
0.2
0.4
0.6
0.8
1
1.2
1.4
g(x)
y=x
ξ
Jiří Zelinka Numerické metody 16 / 19
Existence pevného bodu
Věta: Jestliže spojitá funkce g zobrazuje interval I do sebe,
tj. pro každé x ∈ I platí g(x) ∈ I, pak na intervalu I existuje
alespoň jeden pevný bod ξ funkce g.
Jednoznačnost pevného bodu
Definice Funkce g zobrazující interval I do sebe se nazývá
kontrakce na I, jestliže existuje taková konstanta L
(Lipschitzova konstanta), 0 ≤ L < 1, že pro každé x, y ∈ I
platí
|g(x) − g(y)| ≤ L|x − y|.
Banachova věta o pevném bodě
Jestliže g je kontrakce na I, pak g má na tomto intervalu
jediný pevný bod a iterační posloupnost definovaná vztahem
xk+1 = g(xk) konverguje k pevnému bodu funkce g pro
libovolné x0 ∈ I.
Jiří Zelinka Numerické metody 17 / 19
Odhad chyby
Věta: Nechť g je kontrakce s Lipschitzovou konstantou L na I
a x0 ∈ I je libovolné. Pak pro iterační posloupnost definovanou
vztahem xk+1 = g(xk) platí odhad
|xk − ξ| ≤
Lk
1 − L
|x0 − x1|
Jiří Zelinka Numerické metody 18 / 19
Určení konstanty L pomocí derivace
Lagrangeova věta o střední hodnotě:
g(x) − g(y) = g (µ) · (x − y)
Bod µ leží mezi x a y.
Pokud pro každé x ∈ I platí |g (x)| ≤ L < 1 a g zobrazuje I
do sebe, je g kontrakce na I.
L = max
x∈I
|g (x)|
Jiří Zelinka Numerické metody 19 / 19