4. Numerické řešení rovnice o jedné neznámé Tento učební text byl podpořen z Operačního programu Praha - Adaptabilita
Barbora Batíková
Mějme rovnici f (x) = 0,
(R)
kde f je funkce jedné reálné proměnné, která je spojitá na jistém intervalu J. Kořen rovnice (R) neboli nulový bod funkce f je bod c ∈ J takový, že f (c) = 0. Numerické řešení rovnice: Numerické řešení rovnice (R) rozdělíme do dvou kroků: (1) Separace kořenů neboli určení uzavřených intervalů, které obsahují právě jeden kořen. (2) Určení kořenů s předem danou přesností.
Výpočet hodnot mnohočlenu, Hornerovo schéma Hornerovo schéma budeme používat při numerickém řešení algebraických rovnic. Dává návod pro rychlé zjištění hodnoty polynomu v daném bodě. Uvažujme polynom n. stupně: P (x) = a0 xn + a1 xn−1 + ... + an−1 x + an ,
kde a1 , a2 , ..., an ∈ R, a0 6= 0.
Vypočteme hodnotu polynomu P v bodě c neboli P (c): P (c) = a0 cn + a1 cn−1 + ... + an−1 c + an = (((a0 c + a1 )c + a2 )c + ... + an−1 )c + an . Označme b0 = a0 , b1 = b0 c + a 1 , b2 = b1 c + a 2 , ... ... bn = bn−1 c + an . Platí: : P (x) = Q(x) (x − c) + bn , kde Q(x) = b0 xn−1 + b1 xn−2 + ... + bn−2 x + bn−1 . Výsledky budeme postupně zapisovat do tabulky: Hornerovo schéma: a0 c b0
a1
a2
...
an
b0 c
b1 c
...
bn−1 c
b1
b2
...
bn = P (c)
Příklad 1A: Vypočteme hodnotu polynomu P (x) = 2x3 + 3x2 − 5x − 6 v bodě c = 5. Hornerovo schéma má tvar 2 5 2
3
−5
−6
10
65
300
13
60
294 = P (5)
Hodnota polynomu v bodě 5 je 294.
2
Navíc platí P (x) = 2x3 + 3x2 − 5x − 6 = (2x2 + 13x + 60)(x − 5) + 294. Příklad 1B: Vypočteme hodnotu polynomu P (x) = 2x3 + 3x2 − 5x − 6 v bodě c = 4. MATLAB - polynomy Polynomy se zadávají pomocí vektoru jejich koeficientů, např. polynom p(x) = 4x3 − 5x2 + 2x − 1 bude zadán jako vektor p = [4, −5, 2, −1]. Pro vyčíslení hodnoty polynomu v bodě x existuje příkaz y = polyval(p, x). Pokud je proměnná x vektor, pak se polynom vyčíslí ve všech jeho složkách.
Separace kořenů, Bolzanova věta Bolzanova věta: Je-li funkce f spojitá v intervalu ha, bi a f (a)f (b) < 0, pak uvnitř intervalu leží alespoň jeden kořen rovnice (R). P o z n á m k a : Pokud navíc existuje uvnitř intervalu derivace a nemění tam znaménko, funkce je tudíž v tomto intervalu rostoucí nebo klesající, je kořen jediný. P o z n á m k a : Algebraická rovnice f (x) = a0 xn + a1 xn−1 + ... + an−1 x + an = 0, má nejvýše n reálných různých kořenů. Stačí najít n intervalů, ve kterých f nemění znaménko. P o z n á m k a : Má-li funkce f spojitou derivaci, pro separování kořenů rovnice (R) určíme hodnoty v krajních bodech definičního oboru a v nulových bodech derivace, pokud je lze vypočítat. Příklad 2A: Separujme kořeny algebraické rovnice f (x) = 2x3 + 3x2 − 12x − 6 = 0. V tomto případě lze jednoduše určit nulové body první derivace: f ′ (x) = 6x2 + 6x − 12 = 6(x − 1)(x + 2) = 0
odtud
x1 = −2, x2 = 1.
Pomocí Hornerova schématu určíme hodnoty v těchto bodech: 2 −2 2
3
−12
−6
−4
2
20
−1
−10
14 = f (−2)
2 1 2
3
−12
−6
2
5
−7
5
−7
−13 = f (1)
Rovnice má nejvýše tři kořeny, neboť jde o algebraickou rovnici 3.stupně. Protože
lim f (x) =
x→−∞
−∞, lim f (x) = ∞, jsou kořeny v intervalech (−∞, −2), (−2, 1), (1, ∞). Kořeny jsou právě tři. Pro x→∞ upřesnění intervalů zkusíme vypočítat funkční hodnoty funkce f v několika dalších bodech, např. f (−4) = −38, f (−3) = 3, f (−1) = 7, f (0) = −6, f (2) = −2, f (3) = 39. Kořeny leží v intervalech, ve kterých dochází ke změně znaménka, tedy v intervalech (−4, −3), (−1, 0), (2, 3). Příklad 2B: Separujme kořeny algebraické rovnice f (x) = x3 + 3x2 − 24x + 10 = 0. Příklad 2C: Separujme kořeny algebraické rovnice f (x) = x4 − 4x + 10 = 0. Příklad 3A: Separujme kořeny rovnice f (x) = ex − x − 2 = 0. I v tomto případě lze jednoduše určit nulové body první derivace:
3
f ′ (x) = ex − 1 = 0 neboli
ex = 1 = e0
odtud
x = 0.
0
Funkční hodnota v tomto bodě je f (0) = e − 0 − 2 = −1. Protože lim f (x) = ∞, jsou kořeny v intervalech (−∞, 0), (0, ∞). V každém z těchto intervalů x→±∞
derivace nemění znaménko, proto v každém z nich je právě jeden kořen, kořeny jsou tedy právě dva. Pro upřesnění intervalů zkusíme vypočítat funkční hodnoty funkce f v několika dalších bodech, např. f (−2) =
1 1 > 0, f (−1) = − 1 < 0, f (1) = e − 3 < 0, f (2) = e2 − 4 > 0. e2 e
Kořeny leží v intervalech, ve kterých dochází ke změně znaménka, tedy v (−2, −1), (1, 2). Příklad 3B: Separujme kořeny rovnice f (x) = ex + x = 0.
Metoda půlení intervalu Tato metoda je jednou z metod vedoucí k nalezení kořenu rovnice (R) v jistém intervalu. Nechť funkce f je spojitá v intervalu ha, bi, f (a)f (b) < 0 a rovnice f (x) = 0 má v intervalu ha, bi právě jeden kořen c. Metoda půlení intervalu: a+b (1) Vypočteme f . 2 (2) a+b a+b = 0, pak c = . Pokud f 2 2 a+b a+b a+b 6= 0, pak vybereme ten z intervalů a, , , b , ve kterém mají Pokud f 2 2 2 funkční hodnoty v krajních bodech opačná znaménka a opět ho rozpůlíme. Buď po konečném počtu kroků získáme kořen rovnice, nebo posloupnost intervalů han , bn i, pro b−a které bn − an = n . 2 b−a Odhad chyby: 0 < c − an < n . 2 bn − a n s Výsledkem po konečném počtu půlení n je buď přesná hodnota c, nebo c ≈ an+1 = 2 b−a chybou menší než n+1 . 2 Příklad 4A: Metodou půlení intervalu určeme kořen rovnice f (x) = 2x3 + 3x2 − 12x − 6 = 0 v intervalu (−1, 0), n = 4. V Příkladu 2 jsme určili, že v daném intervalu je právě jeden kořen. Funkční hodnoty v krajních bodech jsou f (−1) = 7 > 0, f (0) = −6 < 0. −1 + 0 = −0, 5 Pro n = 1 vypočteme střed intervalu 2 a hodnotu funkce f (−0, 5) = 0, 5 > 0. Vybereme interval, ve kterém dochází ke změně znaménka, tedy (−0, 5; 0). −0, 5 + 0 Pro n = 2 vypočteme střed intervalu = −0, 25 2 a hodnotu funkce f (−0, 25) = −2, 84375 < 0. Vybereme interval, ve kterém dochází ke změně znaménka, tedy (−0, 5; −0, 25).
4
−0, 5 − 0, 25 = −0, 375 2 a hodnotu funkce f (−0, 375) = −1, 18359375 < 0. Vybereme interval, ve kterém dochází ke změně znaménka, tedy (−0, 5; −0, 375). −0, 5 − 0, 375 Pro n = 4 vypočteme střed intervalu = −0, 4375 2 a hodnotu funkce f (−0, 4375) = −0, 34326171875 < 0. Vybereme interval, ve kterém dochází ke změně znaménka, tedy (−0, 5; −0, 4375). −0, 5 − 0, 4375 Určíme přibližnou hodnotu kořene rovnice c = = −0, 46875 s chybou menší než 2 1 0 − (−1) = = 0, 03125. 5 2 32 Pro n = 3 vypočteme střed intervalu
Příklad 4B: Metodou půlení intervalu určeme kořen rovnice f (x) = x3 + 3x2 − 24x + 10 = 0 v intervalu (0, 1), n = 3.
Metoda tětiv (regula falsi) Tato matoda je obdobou metody půlení intervalů. Rozdíl je v tom, že interval nebudeme na −f (a) , tedy poloviny. Pokud f (a) < 0 a f (b) > 0, rozdělíme interval v poměru f (b) b−a . x1 = a − f (a) f (b) − f (a) Pokud f (x1 ) = 0, proces ukončíme. V opačném případě vybereme ten z intervalů ha, x1 i, hx1 , bi, v kterém funkční hodnoty v krajních bodech mají opačné znaménko, a proces opakujeme. Pokud druhá derivace funkce nemění v intervalu znaménko a je-li v intervalu jediný kořen, tato metoda konverguje. Pomocí věty o střední hodnotě, viz např. Z.Horský, Učebnice matematiky pro posluchače VŠE, Věta 13,2, lze stanovit odhad chyby této metody. |f (xn )| Odhad chyby: |xn − c| ≤ , kde m = min |f ′ |, c je přesné řešení rovnice. m ha,bi Příklad RS: Metodou tětiv určeme kořen rovnice f (x) = x3 + 3x2 − 24x + 10 = 0 v intervalu (0, 1), n = 2.
Newtonova metoda (tečen) Nechť f ′′ je spojitá v intervalu ha, bi, f ′′ a f ′ tam nemění znaménko a f (a)f (b) < 0. Pak rovnice f (x) = 0 má v intervalu ha, bi právě jeden kořen c. Nechť navíc f (b) a f ′′ (b) mají stejné znaménko. Nechť např. f (b) a f ′′ (b) jsou kladné, viz obr. 4.1, funkce f je rostoucí a konvexní. Rovnice tečny funkce f procházející bodem [b, f (b)] je tvaru y = f (b)+f ′ (b)(x−b). Průsečík tečny s osou x bude mezi body a, b. Průsečík vypočteme dosazením y = 0 do rovnice tečny 0 = f (b) + f ′ (b)(x − b) odtud x = f (b) b− ′ . f (b)
5
Obr. 4.1 Pokud f (b) a f ′′ (b) jsou záporné, funkce f je klesající a konkávní. Průsečík tečny s osou x bude také mezi body a, b. Newtonova metoda : f (b) . f ′ (b) f (x1 ) . (2) Vypočteme x2 = x1 − ′ f (x1 ) ... f (xn−1 ) . (n) Vypočteme xn = xn−1 − ′ f (xn−1 ) (1) Vypočteme x1 = b −
Pomocí věty o střední hodnotě, viz např. Z.Horský, Učebnice matematiky pro posluchače VŠE, Věta 13,2, lze stanovit odhad chyby této metody. |f (xn )| Odhad chyby: |xn − c| ≤ , kde m = min |f ′ |. m ha,bi Pokud f (b) a f ′′ (b) nemají stejné znaménko, pak f (a) a f ′′ (a) mají stejné znaménko. Povedeme f (a) tečnu z bodu a [a, f (a)] v (1) vypočteme x1 = a − ′ . Další postup bude stejný. f (a) Příklad 5A: Newtonovou metodou určeme přibližně kořen rovnice f (x) = 2x3 + 3x2 − 12x − 6 = 0 v intervalu h−4, −3i , n = 2. Určíme funkční hodnoty v krajních bodech f (−4) = −38 < 0, f (−3) = 3 > 0 a derivaci f ′ (x) = 6x2 + 6x − 12 = 6(x + 2)(x − 1), která je v daném intervalu kladná. Navíc je klesající, protože druhá derivace je záporná. Minimální hodnotou funkce |f ′ | v daném intervalu je |f ′ (−3)| = f ′ (−3) = 24. Druhá derivace f ′′ (x) = 12x + 6 je v intervalu h−4, −3i záporná. Aby měla stejné znaménko jako funkční hodnota v krajním bodě, který budeme dosazovat do vzorce pro x1 , vybereme krajní bod −4. Pro n = 1 vypočteme −38 f (−4) = −4 − ≈ −3, 366667, x1 = −4 − ′ f (−4) 60 f (−3, 366667) ≈ −7, 915249, f ′ (−3, 366667) ≈ 35, 806678. Pro n = 2 vypočteme f (−3, 366667) ≈ −3, 145612, x2 ≈ −3, 366667 − ′ f (−3, 366667) f (−3, 145612) ≈ −0, 818899. |f (−3, 145612)| 0, 818899 Chyba je menší než = ≈ 0, 034121. 24 24 Příklad 5B: Newtonovou metodou určeme přibližně kořen rovnice f (x) = x3 + 3x2 − 24x + 10 = 0 v intervalu h0, 1i , n = 2.
6
Kombinovaná metoda Tato metoda je kombinací metody tětiv (sečen) a tečen. Nechť např. f (b) a f ′′ (b) jsou kladné, viz obr. 4.1, funkce f je rostoucí a konvexní v daném intervalu. Označíme-li (sn ) posloupnost aproximací získaných metodou regula falsi, (tn ) posloupnost aproximací získaných Newtonovou metodou, c přesné řešení rovnice, pak pro všechna n platí: s n < c < tn . Chyba je menší než rozdíl tn − sn . Příklad K: Kombinovanou metodou určeme přibližně kořen rovnice f (x) = x3 + 3x2 − 24x + 10 = 0 v intervalu h0, 1i , n = 2.
Iterační metoda Řešme rovnici x = h(x).
(IR)
Platí: : Mějme reálnou funkci jedné reálné proměnné h definovanou v uzavřeném intervalu J, která zobrazuje J do J. Nechť existuje konstanta α ∈ (0, 1) taková, že |h′ (x)| ≤ α pro všechna x ∈ J. Pak existuje právě jedno c ∈ J takové, že c = h(c) neboli c je kořen rovnice (IR) v J. Pro libovolné x0 ∈ R definujme posloupnost (xn ) rekurentně: xn+1 = h(xn ). αn |x0 − x1 |. Pak c = lim xn a platí |xn − c| ≤ n→∞ 1−α P o z n á m k a : Předchozí tvrzení plyne z Banachovy věty o pevném bodě. Poslední vzorec určuje odhad chyby iterační metody. Příklad 6A: Iterační metodou odhadneme kořen rovnice f (x) = x3 − 1, 2x + 0, 2 = 0 v intervalu h0; 0, 5i, n = 3. Rovnici upravíme na tvar h(x) = Zderivujeme h′ (x) =
x3 + 0, 2 = x. 1, 2
3x2 . Funkce h′ je v daném intervalu kladná a rostoucí, největší hodnoty nabývá 1, 2
v krajním bodě 0, 5. 3 · 0, 52 Platí |h′ (x)| ≤ = 0, 625 < 0, 7 = α < 1 pro všechna x ∈ h0; 0, 5i. 1, 2 Předpoklady předchozí věty jsou splněny. Zvolme x0 = 0, 03 + 0, 2 ≈ 0, 166667, x1 = h(0) = 1, 2 0, 1666673 + 0, 2 x2 = h(0, 166667) = ≈ 0, 170525, 1, 2 0, 1705253 + 0, 2 ≈ 0, 170799. x3 = h(0, 170525) = 1, 2 3 0, 7 Chyba je nejvýše · |0, 166667 − 0| ≈ 0, 190556. 1 − 0, 7
Příklad 6B: Iterační metodou odhadneme kořen rovnice f (x) = x4 − 4x + 10 = 0 v intervalu h0, 1; 0, 5i, n = 2.
7
Příklad 6C: Iterační metodou odhadneme kořen rovnice f (x) = x3 + 10x − 15 = 0 v intervalu h1; 1, 5i, n = 2. MATLAB - kořeny polynomu Pro určení kořenů polynomu existuje příkaz r = roots(p). Pro určení kořenů funkce jedné proměnné existuje příkaz x = f zero(f un, x0 ), kde f un je zadaná funkce, x0 je počáteční hodnota.
Odhady mezí a počtu kořenů Při řešení obtížnějších rovnice je někdy potřeba blíže specifikovat interval, ve kterém se nacházejí kořeny algebraické rovnice, či odhadnout počet kořenů v zadaných intervalech. Uvažujme algebraickou rovnici n-tého stupně P (x) = a0 xn + a1 xn−1 + ... + an−1 x + an ,
kde a1 , a2 , ..., an ∈ R, a0 6= 0.
(AR)
Tato rovnice má v oboru komplexních čísel právě n kořenů, počítáme-li každý kořen s jeho násobností. Mac Laurinovo pravidlo. Označme A = max{|a1 |, |a2 |, ..., |an |}. Pak pro všechny kořeny c rovnice (AR) platí |c| < M = 1 +
A . |a0 |
Pokud a0 > 0 a označíme-li A = max{|ak |; ak < 0}, pak je M horní mezí množiny kořenů rovnice (AR). Je-li M horní mez množiny kořenů rovnice P (−x) = 0, je číslo −M dolní mezí množiny kořenů rovnice (AR). Newtonova metoda. Pokud a0 > 0, c > 0 a P (c) ≥ 0, P ′ (c) ≥ 0, P ′′ (c) ≥ 0, ..., P (n) (c) ≥ 0, pak číslo c je horní mezí množiny kořenů rovnice (AR). Příklad 7A: Určeme horní a dolní mez množiny kořenů rovnice f (x) = x3 + 3x2 − 24x + 10 = 0. Příklad 7B: Určeme horní a dolní mez množiny kořenů rovnice f (x) = x2 + 2x − 1 = 0. Budanova-Fourierova věta. Rovnice (AR) má v intervalu (a, b), kde P (a), P ′ (a), ..., P (n) (a), P (b), P ′ (b), ..., P (n) (b) 6= 0, nejvýše tolik kořenů, o kolik je v posloupnosti (P (a), P ′ (a), P ′′ (a), ..., P (n) (a)) více znaménkových změn než v posloupnosti(P (b), P ′ (b), P ′′ (b), ..., P (n) (b)). Příklad 7C: Určeme počet kořenů rovnice f (x) = x3 + 3x2 − 24x + 10 = 0 v intervalu h0, 1i.
8
