Numerické metody
Jiří Zelinka jaro 2015
Jiří Zelinka
•0 0.0 1/12
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
<flP^ ■= -O^O
Jin Zelinka        Numerické metody 2/12
Osnova
• Řešení nelineárních rovnic
• Polynomy
• Řešení soustav lineárních rovnic - přímé metody
• Řešení soustav lineárních rovnic - iterační metody
• Řešení soustav nelineárních rovnic
Předpoklady
• Lineární algebra
• Diferenciální počet v R (Rn)
• Integrální počet v IR
Jiří Zelinka
Numerické metody
Chyby
x: přesná hodnota, x: aproximace x x — x: absolutní chyba aproximace x |x — x| < a: odhad absolutní chyby
ÍĽ^Ĺ: relativní chyba
I ^—^ I < ô: odhad relativní chyby
Jiří Zelinka
•0 0.0 4/12
Motivační příklad
Pro kružnici k\ o poloměru r sestrojte kružnici k^ se středem na kružnici k\ tak, aby oblast ohraničena oběma kružnicemi měla poloviční obsah než vnitřek kružnice k\.
Jiří Zelinka        Numerické metody 5/12
Ú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 6/12
Řešení nelineárních rovnic
Řešíme rovnici f(x) = 0 na uzavřeném intervalu / = [a,b], pro reálnou spojitou funkci f,£- řešení rovnice,
Iteračníproces: vytváříme posloupnost (xk)^Q, xk —> £. (x/()^0 - iterační posloupnost.
Metoda půlení intervalu - bisekce
Odhad absolutní chyby v /r-tém kroku:
\xk - £| < 2JhT
Jiří Zelinka        Numerické metody 7/12
Metoda pevného bodu, prostá iterační metoda
• Tato metoda se používá pro rovnici x = g(x)
• Funkce g je spojitá na / = [a, b]
• Řešení £ této rovnice nazýváme pevným bodem funkce g
Iterační proces
a Zvolíme x0 g / a položíme xi = g(x0)
• Obecně xk+1 = g(xk)
a Funkce g se nazývá iterační funkce
Jiří Zelinka        Numerické metody 8/12
Geometrická interpretace
Pevný bod £ je průsečík grafu funkce g a přímky y = x.
<fll^ -E -O^O
Jiří Zelinka        Numerické metody 9/12
Existence pevného bodu
Věta: Jestliže spojitá funkce g zobrazuje interval / do sebe, tj. pro každé x g / platí g(x) e I, pak na intervalu / existuje alespoň jeden pevný bod £ funkce g.
Jednoznačnost pevného bodu
Definice Funkce g zobrazující interval / do sebe se nazývá kontrakce na /, jestliže existuje taková konstanta L (Lipschitzova konstanta), 0 < L < 1, že pro každé x,y E I platí
\g{*)-g{y)\ < L\*-y\-
Banachova věta o pevném bodě
Jestliže g je kontrakce na /, pak g má na tomto intervalu jediný pevný bod a iterační posloupnost definovaná vztahem xk+i = g{xk) konverguje k pevnému bodu funkce g pro
libovolné x0. <n> <a>
Jiří Zelinka        Numerické metody
10/12
Odhad chyby
Věta: Nechť g je kontrakce s Lipschitzovou konstantou L na I a x0 g / je libovolné. Pak pro iterační posloupnost definovanou vztahem xk+1 = g(xk) platí odhad
M - £1 < *—r lxo ~ xil
<fll^ š -o^o
Jiří Zelinka        Numerické metody 11 /12
Určení konstanty L pomocí derivace
Lagrangeova věta o střední hodnotě:
g{*) - g(y) = g'M ■ (x - y)
Bod /i leží mezi x a y.
Pokud pro každé x g / platí |g'(x)| < L < 1 a g zobrazuje / do sebe, je g kontrakce na /.
L = max |g'(x)|
Jiří Zelinka        Numerické metody 12 /12