Numerické metody
E 3011
Jan Böhm
RECETOX
March 29, 2023
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 1 / 16
Co nás dnes čeká
1 Babylónská odmocnina
2 Newtonova metoda
3
4 Test
5
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 2 / 16
Babylónská odmocnina
Odvození
Máme číslo x a chceme spočítat
√
S. Jak na to?
1 Nejprve si tipneme. Označíme x0 jako tip.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 3 / 16
Babylónská odmocnina
Odvození
Máme číslo x a chceme spočítat
√
S. Jak na to?
1 Nejprve si tipneme. Označíme x0 jako tip.
2 Asi jsme se netrefili přesně, označíme jako chybu. Platí
S = (x0 + )2
= x2
0 + 2x0 + 2
≈0
≈ x2
0 + 2x0
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 3 / 16
Babylónská odmocnina
Odvození
Máme číslo x a chceme spočítat
√
S. Jak na to?
1 Nejprve si tipneme. Označíme x0 jako tip.
2 Asi jsme se netrefili přesně, označíme jako chybu. Platí
S = (x0 + )2
= x2
0 + 2x0 + 2
≈0
≈ x2
0 + 2x0
3 Spočítáme, jak velké chyby jsme se dopustili =
S−x2
0
2x0
.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 3 / 16
Babylónská odmocnina
Odvození
Máme číslo x a chceme spočítat
√
S. Jak na to?
1 Nejprve si tipneme. Označíme x0 jako tip.
2 Asi jsme se netrefili přesně, označíme jako chybu. Platí
S = (x0 + )2
= x2
0 + 2x0 + 2
≈0
≈ x2
0 + 2x0
3 Spočítáme, jak velké chyby jsme se dopustili =
S−x2
0
2x0
.
4 Opravíme náš původní odhad:
x1 = x0 + = x0 +
S − x2
0
2x0
=
x2
0 + S
2x0
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 3 / 16
Babylónská odmocnina
Odvození
Máme číslo x a chceme spočítat
√
S. Jak na to?
1 Nejprve si tipneme. Označíme x0 jako tip.
2 Asi jsme se netrefili přesně, označíme jako chybu. Platí
S = (x0 + )2
= x2
0 + 2x0 + 2
≈0
≈ x2
0 + 2x0
3 Spočítáme, jak velké chyby jsme se dopustili =
S−x2
0
2x0
.
4 Opravíme náš původní odhad:
x1 = x0 + = x0 +
S − x2
0
2x0
=
x2
0 + S
2x0
5 Vesele iterujeme.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 3 / 16
Babylónská odmocnina
Implementace
Implementujte funkci sqrt(S, tol = 0.001), která spočítá babylónskou
odmocninu čísla S. Rekurentní formule je:
xn =
S
2 pro n = 0,
x2
n−1+S
2xn−1
jinak.
Stop kritérium je |xn − xn−1| < tol.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 4 / 16
Co nás dnes čeká
1 Babylónská odmocnina
2 Newtonova metoda
3
4 Test
5
🍕
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 5 / 16
Newtonova metoda
Odvození
Řešíme (přibližně) rovnici f (x) = 0, kde f je hezká funkce.
1 Začneme tak, že si řešení tipneme: x0
2 Lokálně nahradíme funkci f (x) přímkou a najdeme místo, kde tato
přímka protíná osu x. Toto místo označíme jako x1.
3 Iterujeme dle chuti.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 6 / 16
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 7 / 16
Newtonova metoda - odvození
Matematika
Chceme z n-tého odhadu xn kořene r rovnice f (x) = 0 udělat přesnější,
(n + 1)-odhad xn+1.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 8 / 16
Newtonova metoda - odvození
Matematika
Chceme z n-tého odhadu xn kořene r rovnice f (x) = 0 udělat přesnější,
(n + 1)-odhad xn+1.
1 V okolí xn nahradíme f přímkou (Taylorův polynom 1. stupně, lol).
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 8 / 16
Newtonova metoda - odvození
Matematika
Chceme z n-tého odhadu xn kořene r rovnice f (x) = 0 udělat přesnější,
(n + 1)-odhad xn+1.
1 V okolí xn nahradíme f přímkou (Taylorův polynom 1. stupně, lol).
2 Rovnice přímky (y − yk) = f (xk)(x − xk).
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 8 / 16
Newtonova metoda - odvození
Matematika
Chceme z n-tého odhadu xn kořene r rovnice f (x) = 0 udělat přesnější,
(n + 1)-odhad xn+1.
1 V okolí xn nahradíme f přímkou (Taylorův polynom 1. stupně, lol).
2 Rovnice přímky (y − yk) = f (xk)(x − xk).
3 My chceme takové xk+1, že y = 0. Navíc yk = f (xk).
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 8 / 16
Newtonova metoda - odvození
Matematika
Chceme z n-tého odhadu xn kořene r rovnice f (x) = 0 udělat přesnější,
(n + 1)-odhad xn+1.
1 V okolí xn nahradíme f přímkou (Taylorův polynom 1. stupně, lol).
2 Rovnice přímky (y − yk) = f (xk)(x − xk).
3 My chceme takové xk+1, že y = 0. Navíc yk = f (xk).
4
−f (xk) = f (xk)(xk+1 − xk) → xk+1 = xk −
f (xk)
f (xk)
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 8 / 16
Newtonova metoda - odvození
Matematika
Chceme z n-tého odhadu xn kořene r rovnice f (x) = 0 udělat přesnější,
(n + 1)-odhad xn+1.
1 V okolí xn nahradíme f přímkou (Taylorův polynom 1. stupně, lol).
2 Rovnice přímky (y − yk) = f (xk)(x − xk).
3 My chceme takové xk+1, že y = 0. Navíc yk = f (xk).
4
−f (xk) = f (xk)(xk+1 − xk) → xk+1 = xk −
f (xk)
f (xk)
Stačí zvolit počáteční odhad x0 a vymyslet, kdy přestat iterovat.
Nějaký problém?
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 8 / 16
Intermezzo - derivace
Derivace
Ne všechny funkce jdou hezky derivovat. Ale snad by šlo aspoň přibližně
odhadnout hodnotu derivace funkce v nějakém bodě f (x).
Definice derivace f (x) = limh→0
f (x+h)−f (x)
h .
derivative(f, x, tol = 0.001)
Napište funkci derivative(f, x, tol = 0.001), která spočítá
přibližnou hodnotu derivace funkce f v bodě x s přesností tol.
Využijte definice derivace výše. Začněte s nějakou rozumnou hodnotou h a
tuto hodnotu zmenšujte, dokud změna v hodnotě odhadu derivace
neklesne pod požadovanou toleranci.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 9 / 16
Newtonova metoda - implementace
newton(f, x0, tol = 0.001)
Napište funkci newton(f, x0, tol = 0.001), která spočítá přibližný
kořen rovnice f(x)=0 v okolí bodu x(0) s přesností tol.
Pro samotný výpočet použijte iterativní vztah
xk+1 = xk −
f (xk)
f (xk)
,
derivaci již spočítat umíte.
S iterováním přestaňte, jakmile rozdíl mezi předchozím a novým odhadem
je menší, než tol.
1 def myFun(x):
2 return math.cos(x)-x
3
4 print(newton(myFun, 1))
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 10 / 16
Co nás dnes čeká
1 Babylónská odmocnina
2 Newtonova metoda
3
4 Test
5
🍕
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 11 / 16
int(f, a, b, dx = 0.001)
Napište funkci int(f, a, b, dx = 0.001), která počítá přibližně
integrál
b
a f (x)dx
Vyberte si libovolnou metodu, kterou chcete implementovat –
obdélníkovou (levou, pravou, střední, dolní-horní odhad), lichoběžníkovou,
nebo klidně nějakou úplně jinou.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 12 / 16
Co nás dnes čeká
1 Babylónská odmocnina
2 Newtonova metoda
3
4 Test
5
🍕
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 13 / 16
Test
Test
S využitím vašich funkcí s přesností na 6 desetinných míst zodpovězte na
následující otázky:
1 Vyčíslete
√
408849
2 Jaký je kořen funkce sin(log2
(x)) okolo bodu x = 5?
3 Polynom 4x5 + 0x4 + 8x3 + 8x2 + 4x + 9 má jen jeden reálný kořen.
Najděte jej.
4 Spočítejte
1
0 2x3ex2
dx.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 14 / 16
Co nás dnes čeká
1 Babylónská odmocnina
2 Newtonova metoda
3
4 Test
5
🍕
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 15 / 16
Takeaways
Po tomto cvičení byste měli mít připravené funkce
sqrt(S, tol = 0.001) pro výpočet odmocniny
derivative(f, x, tol = 0.001), která spočítá přibližnou
hodnotu derivace funkce f v bodě x
newton(f, x0, tol = 0.001) pro numerický výpočet řešení
rovnice f(x)=0 poblíž x0.
int(f, a, b, dx = 0.001), která numericky integruje funkci f na
intervalu (a,b) s krokem dx.
Tyto funkce si přidejte do své ”knihovny” functions.py.
Po tomto cvičení byste měli umět:
Implementovat další numerické metody pro řešení nelineárních rovnic
jedné proměnné.
Využívat své funkce pro řešení daných problémů a pokud to problém
vyžaduje, funkci upravit.
Jan Böhm (RECETOX) Cvičení VI March 29, 2023 16 / 16