MASARYKOVA UNIVERZITA PEDAGOGICKÁ FAKULTA Katedra matematiky Numerické metody pro řešení polynomických rovnic Bakalářská práce Brno 2019 Vedoucí práce: Autor práce: RNDr. Břetislav Fajmon, Ph.D. Iveta Trombiková 2 Bibliografický záznam TROMBIKOVÁ, Iveta Numerické metody pro řešení polynomických rovnic. Brno: Masarykova univerzita, Fakulta pedagogická, Katedra matematiky, 2019. Vedoucí bakalářské práce RNDr. Břetislav Fajmon, Ph.D. Anotace Bakalářská práce s názvem „Numerické metody pro řešení polynomických rovnic“ popisuje základní pojmy z oblasti polynomů a věnuje se vybraným numerickým metodám, jmenovitě metodě půlení intervalu, metodě prosté iterace a Newtonově metodě. Tato práce rovněž obsahuje programy pro jednotlivé numerické metody, díky nimž jsou pak metody porovnány a studenti mohou vidět jejich světlé či stinné stránky. Práce je navíc doplněna o webové aplikace pomáhající při řešení polynomických rovnic. Annotation The bachelor thesis “Numerical Methods for Polynomial Equations” describes basic terms from the field of polynomials and deals with chosen numerical methods, namely the bisection method, the simple iteration method and Newton method. The thesis also contains programmes for the numerical methods, thanks to which are methods compared and students can see their benefits or deficiencies. The thesis is supplemented with additional website’s applications which help to solve polynomial equations. Klíčová slova Polynomy, polynomické rovnice, numerické metody, kořen polynomu, Newtonova metoda, metoda prosté iterace, metoda půlení intervalu. Keywords Polynomials, polynomial equations, numerical methods, a root of the polynomial, Newton method, a simple iteration method, a bisection method. 3 Prohlášení „Prohlašuji, že jsem bakalářskou práci zpracovala samostatně, s využitím pouze citovaných pramenů, dalších informací a zdrojů v souladu s Disciplinárním řádem pro studenty Pedagogické fakulty Masarykovy univerzity a se zákonem č.121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon), ve znění pozdějších předpisů.“ V Brně dne 27. března 2019 Iveta Trombiková 4 Poděkování Velké díky patří mému vedoucímu doktoru Břetislavu Fajmonovi, za jeho vřelý přístup, ochotu a trpělivost, s kterou vedl celou bakalářskou práci. Také bych na tomto místě chtěla poděkovat mé rodině a přátelům za podporu během psaní. 5 Obsah Úvod.............................................................................................................................................. 6 1. POLYNOMY........................................................................................................................ 7 1.1 Základní pojmy ............................................................................................................. 7 1.2 Operace na množině polynomů..................................................................................... 8 1.3 Hodnota a kořen polynomu......................................................................................... 11 1.4 Rozložitelnost, největší společný dělitel..................................................................... 13 1.5 Derivace polynomu..................................................................................................... 18 1.6 Polynomické rovnice................................................................................................... 21 2. NUMERICKÉ METODY................................................................................................... 26 2.1. Metoda půlení intervalu .............................................................................................. 28 2.2. Metoda prosté iterace.................................................................................................. 30 2.3. Newtonova metoda (metoda tečen)............................................................................. 34 3. PROGRAMY A VÝSLEDKY............................................................................................ 39 3.1. Představení programů.................................................................................................. 39 3.2. Porovnání programů a příklady................................................................................... 45 3.3. Shrnutí a doporučení ................................................................................................... 51 Závěr ........................................................................................................................................... 54 Bibliografie ................................................................................................................................. 55 Seznam obrázků .......................................................................................................................... 57 Seznam tabulek ........................................................................................................................... 58 Přílohy......................................................................................................................................... 59 6 Úvod Polynomy jsou jedním ze základních kamenů matematiky a díky svému širokému uplatnění se s nimi setkávají lidé skoro každodenně. Když pomineme základní polynomické rovnice, které řeší snad každý z nás v různých situacích (třeba když si chceme spočítat cenu svého nákupu), tak bez polynomů by se neobešli například stavební inženýři při konstrukci budov, cest či třeba horských drah. Důležité uplatnění však nalezly i při modelování různých situací, například pro odhad ekonomického růstu nebo pro simulaci dopravy. Polynomy jako učební látka je předmětem žáků již na základních školách (při výpočtech jednoduchých polynomických rovnic), ale v celé šíři jsou zájmem hlavně studentů technicky zaměřených vysokých škol. Jelikož je velké procento žáků, kteří se s polynomy a konkrétně také s řešením polynomických rovnic setkají, vznikla tato bakalářské práce, jejímž cílem bylo prozkoumat oblast polynomů, shrnout základní pojmy a vybrat několik metod pro výpočet polynomických rovnic, tyto metody popsat, naimplementovat1 a porovnat jejich rychlost a účinnost. Vše bylo realizováno ve třech kapitolách, které nesou názvy podle svého obsahu. V první kapitole „Polynomy“ jsou shrnuty základní definice a pojmy z oblasti polynomů, mnohdy doplněné o vzorové příklady. Čtenář zde tedy může najít například, co je to stupeň polynomu, derivace polynomu či vysvětlené metody jako je Hornerovo schéma. Druhá kapitola se věnuje vybraným numerickým metodám, které jsou zde vysvětleny, popsány a jejich fungování ukázáno na vzorovém příkladě. Poslední kapitola vysvětluje fungování programů vytvořených pro výpočet jednotlivých numerických metod a také skrze sérii několika příkladů porovnává a vyhodnocuje účinnost těchto metod. Bakalářská práce byla tedy pojata tak, aby pomohla studentům matematiky (či jiných oborů) ve studiu polynomů a usnadnila jim práci při řešení polynomických rovnic. 1 naprogramovat 7 1. POLYNOMY Pro počítání s polynomickými rovnicemi je nutno nejdříve definovat základní pojmy z oblasti polynomů, které jsou uvedeny v následujících podkapitolách. Text je rovněž obohacen ukázkovými příklady, které slouží k lepší ilustraci látky. Materiál k napsání této kapitoly je čerpán z knih: (Horák, 1977), (Rosický, 2000), (Budínová, 2013), částečně také z přednášek předmětu Algebra 3 či výukových internetových zdrojů. 1.1 Základní pojmy Na polynomy můžeme nahlížet dvojím způsobem. Můžeme je brát jako funkce jedné proměnné x nebo je definovat jako posloupnost. Definice 1: Polynomem stupně n rozumíme funkci tvaru 𝑷 𝒏(𝒙) = 𝒂 𝐧 𝒙 𝒏 + 𝒂 𝒏−𝟏 𝒙 𝒏−𝟏 + ⋯ + 𝒂𝒙 + 𝒂 𝟎, kde 𝑎0, 𝑎1, … 𝑎 𝑛 ∈ 𝑅, 𝑎 𝑛 ≠ 0. Prvky 𝑎0, 𝑎1, … 𝑎 𝑛 se nazývají koeficienty polynomu. Člen 𝑎 𝑛 nazýváme řídícím koeficientem polynomu a koeficient 𝑎0 absolutním členem2 polynomu. Polynom, jehož všechny členy jsou rovny nule, nazýváme nulovým polynomem a značíme jej 𝑜̅ = (0,0, … ,0). Polynomu, jehož absolutní člen je roven jedné a ostatní rovny nule, říkáme jednotkový polynom a značíme jej 𝑗̅ = (1,0, … ,0). Poznámka: Nabízí se také varianta definovat polynomy pomocí posloupností jejich koeficientů. Například polynom 𝑓(𝑥) = 3𝑥4 − 2𝑥2 + 15 je možné ztotožnit s posloupností (15, 0, 2, 0, 3) nebo polynom 𝑔(𝑥) = 2𝑥3 + 𝑥2 − 2𝑥 + 1 s posloupností (1, −2, 1, 2). Místo konečných posloupností různých délek však můžeme uvažovat nekonečné posloupnosti o konečném počtu nenulových členů. Množinu takových to posloupnosti, které jsou prvky tělesa3 T označíme T[x] a tuto množinu, pak budeme nazývat množinou polynomů nad tělesem T. Na základní definici polynomu již můžeme stavět další důležité pojmy, jedním z nich je stupeň polynomu. 2 Člen, jenž je pouhým koeficientem, neobsahuje žádné proměnné. 3 Číselným tělesem rozumíme uspořádanou trojici (𝑇, +,∙), kde T je podmnožina množiny komplexních čísel C taková, že 0 ∈ 𝑇, 1 ∈ 𝑇 a platí: 1. ∀𝑥, 𝑦 ∈ 𝑇: 𝑥 + 𝑦 ∈ 𝑇 ⋀ 𝑥 ∙ 𝑦 ∈ 𝑇 (je uzavřená vzhledem k operacím sčítání a násobení) 2. ∀𝑥 ∈ 𝑇: (−1) ∙ 𝑥 ∈ 𝑇 (je uzavřená pro opačné prvky) ∀𝑥 ∈ 𝑇: 𝑥 ≠ 0 ⇒ 1 𝑥 ∈ 𝑇 (je uzavřený na převrácené hodnoty nenulových prvků) 8 Definice 2: Nechť 𝑓 je nenulový polynom nad tělesem T. Pak největší nenulové přirozené číslo 𝑛 v exponentu proměnné x se nazývá stupeň polynomu, značíme 𝑠𝑡(𝑓), když 𝑓 = 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎1 𝑥 + 𝑎0, 𝑎 𝑛 ≠ 0. Polynomy, jež mají stupeň menší než jedna (nulový polynom a polynom stupně nula), se obvykle nazývají konstantními polynomy. Polynomy stupně jedna nazveme polynomy lineárními, stupně dva kvadratickými a stupně tři kubickými. Vyšší stupně polynomu již nemají své specifické názvy. Příklad 1: Určete stupně polynomů 𝑓1(𝑥) = 𝑥3 + 3𝑥2 − 2𝑥, 𝑓2(𝑥) = 12𝑥 a 𝑓3(𝑥) = 0. Řešení: Polynom 𝑓1 = 𝑥3 + 3𝑥2 − 2𝑥 je stupně 3, protože nejvyšší mocnina, která se v polynomu vyskytuje je u 𝑥3 , píšeme tedy 𝑠𝑡(𝑓1) = 3. Polynom 𝑓2 = 12𝑥 má nejvyšší mocninu jedna, proto 𝑠𝑡(𝑓2) = 1. U posledního polynomu 𝑓3 = 0, je nevyšší mocninou nula, proto se jedná o nulový polynom a píšeme 𝑠𝑡(𝑓3) = 0. 1.2 Operace na množině polynomů Už tedy víme, jak polynom vypadá, dále pro něj budeme definovat základní operace. Začneme s operacemi sčítání a násobení. Definice 3: Nechť 𝑓 = (𝑎0, 𝑎1, … ), 𝑔 = (𝑏0, 𝑏1, … ) ∈ T[x]. Pak: Součet 𝑓 + 𝑔 definujeme: 𝑓 + 𝑔 = (𝑎0 + 𝑏0, 𝑎1 + 𝑏1, … ), Součin 𝑓 ∙ 𝑔 definujeme: 𝑓 ∙ 𝑔 = (𝑐0, 𝑐1, 𝑐2, … ), kde 𝑐0 = 𝑎0 𝑏0; 𝑐1 = 𝑎1 𝑏0 + 𝑎0 𝑏1; 𝑐2 = 𝑎2 𝑏0 + 𝑎1 𝑏1 + 𝑎0 𝑏2 atd. Příklad 2: Jsou dány polynomy 𝑓(𝑥) = 𝑥3 + 2𝑥 − 4 a 𝑔(𝑥) = 2𝑥3 + 5, jaký je jejich součet a součin? Řešení: 𝑓 + 𝑔 = (𝑥3 + 2𝑥 − 4) + (2𝑥3 + 5) = 𝑥3 + 2𝑥3 + 2𝑥 − 4 + 5 = 3𝑥3 + 2𝑥 + 1 𝑓 ∙ 𝑔 = (𝑥3 + 2𝑥 − 4) ∙ (2𝑥3 + 5) = = 𝑥3 ∙ 2𝑥3 + 𝑥3 ∙ 5 + 2𝑥 ⋅ 2𝑥3 + 2𝑥 ∙ 5 − 4 ∙ 2𝑥3 − 4 ∙ 5 = = 2𝑥6 + 5𝑥3 + 4𝑥4 + 10𝑥 − 8𝑥3 − 20 = = 2𝑥6 + 4𝑥4 − 3𝑥3 + 10𝑥 − 20 Z výše uvedené definice je zřejmé, že 𝑓 + 𝑔 a 𝑓 ∙ 𝑔 bude taktéž polynom. Z tohoto zjištění plyne Věta 1. 9 Věta 1: (𝑇[𝑥], +,∙) je oborem integrity 4 pro každé těleso T. Definice součtu a součinu nám umožňují dívat se na množinu polynomu jako na vektorový prostor. Věta 2: Nechť 𝑇𝑛[𝑥] je množinou všech polynomů s takto definovanými operacemi sčítání a násoben, pak (𝑇𝑛[𝑥], +,∙) tvoří vektorový prostor dimenze 𝑛 + 1. Ze základních operací ještě chybí definovat dělení. Níže je uvedena definice pro dělení dvou polynomů. Definice 4: Nechť 𝑓, 𝑔 ∈ T[x]. Říkáme, že polynom 𝑔 dělí polynom 𝑓, píšeme 𝑔|𝑓, jestliže existuje polynom h, takový, že: 𝑓 = 𝑔 ∙ ℎ V opačném případě říkáme, že polynom 𝑔 nedělí polynom 𝑓 a píšeme 𝑔 ∤ 𝑓. Z této definice pak plynou následující vlastnosti. Věta 3: Nechť 𝑓, 𝑔 ∈ T[x], 𝑓 ≠ 0, 𝑔 ≠ 0. Pak platí: 1) 𝑓|𝑓. 2) Pro všechna 𝑢, 𝑣 ∈ T[x] a všechna 𝑓1, 𝑓2 ∈ T[x] platí: jestliže 𝑔|𝑓1 ∧ 𝑔|𝑓2, pak také 𝑔|(𝑓1 𝑢 + 𝑓2 𝑣). 3) Nechť ℎ ∈ T[x], pak platí: jestliže ℎ|𝑔 ∧ 𝑔|𝑓, pak také ℎ|𝑓. 4) 𝑔|𝑓 ⇒ 𝑠𝑡 𝑔 ≤ 𝑠𝑡 𝑓. 5) 𝑔|𝑓 ∧ 𝑓|𝑔 ⇔ existuje takový nenulový prvek 𝑐 ∈ 𝑇, že platí 𝑔 = 𝑐𝑓. Je však zřejmé, že dělení není vždy celočíselné, je tedy potřeba definovat dělení polynomu se zbytkem. 4 Oborem integrity je taková struktura (𝑇[𝑥], +,∙), pro kterou platí: 1) (𝑇[𝑥], +) je komutativní grupa, což znamená, že: - je uzavřená k operaci sčítání: ∀𝑥, 𝑦 ∈ 𝑇[𝑥] ∶ 𝑥 + 𝑦 ∈ 𝑇 - platí zde asociativní zákon ∀𝑥, 𝑦, 𝑧 ∈ 𝑇[𝑥]: (𝑥 + 𝑦) + 𝑧 = 𝑥 + (𝑦 + 𝑧) - obsahuje neutrální prvek (v našem případě 0): ∃𝑛 ∈ 𝑇[𝑥]: 𝑛 + 𝑥 = 𝑛 ∧ 𝑥 + 𝑛 = 𝑛, ∀𝑥 ∈ 𝑇[𝑥] - existují v ní prvky inverzní ∀𝑥 ∈ 𝑇[𝑥]: 𝑥 + (−𝑥) = 0 - platí komutativní zákon: ∀𝑥, 𝑦, 𝑧 ∈ 𝑇[𝑥]: 𝑥 ∗ 𝑦 = 𝑦 ∗ 𝑥 2) (𝑇[𝑥], ∙ ) je komutativní monoid, jež je uzavřený k operaci násobení, platí zde asociativní zákon, obsahuje neutrální prvek (zde je to 1) a je komutativní 3) Platí distributivní zákony: ∀𝑥, 𝑦, 𝑧 ∈ 𝑇[𝑥]: 𝑥 ∙ (𝑦 + 𝑧) = (𝑥 ∙ 𝑦) + (𝑥 ∙ 𝑧) ∧ (𝑦 + 𝑥) ∙ 𝑧 = (𝑦 ∙ 𝑧) + (𝑥 ∙ 𝑧) 4) V (𝑇[𝑥], +,∙) neexistují netriviální dělitelé nuly: ∀𝑥, 𝑦 ∈ 𝑇[𝑥]: 𝑥, 𝑦 ≠ 0, pak 𝑥 ∙ 𝑦 ≠ 0 10 Definice 5: Nechť 𝑓, 𝑔 ∈ T[x]. V T[x] lze provést dělení se zbytkem polynomu 𝑓 polynomem 𝑔, jestliže existují polynomy 𝑞, 𝑟 ∈ T[x], takové, že: (1) 𝑓 = 𝑔 ∙ 𝑞 + 𝑟 (2) 𝑠𝑡 (𝑟) < 𝑠𝑡 (𝑔) Polynom 𝑞 se pak nazývá podíl a polynom 𝑟 zbytek tohoto dělení. Z této definice vyplývá, že pro 𝑔 = 0 nelze provést dělení se zbytkem, protože podmínka (2) nebude splněna. Mohou tedy nastat situace, kdy dělení se zbytkem provést nelze, nebo podíl a zbytek nejsou jednoznačně určeny. Aby byla definice úplná doplníme ji o dvě dodatečné věty. Věta 4: Nechť 𝑓, 𝑔 ∈ T[x]. Je-li vedoucí koeficient u polynomu 𝑔 jednotkou tělesa T, pak v T[x] lze provést dělení se zbytkem polynomu 𝑓 polynomem 𝑔. Věta 5: Nechť T je těleso a 𝑔 ∈ T[x] je polynom, jehož vedoucí koeficient je různý od nuly. Pak pro libovolné 𝑓 ∈ T[x] existuje nejvýše jedna dvojce polynomů 𝑞, 𝑟 tak, že 𝑓 = 𝑔 ∙ 𝑞 + 𝑟; 𝑠𝑡(𝑟) < 𝑠𝑡(𝑔). Jak vypadá dělení dvou polynomů je ukázáno na následujícím příkladu. Příklad 3: Jsou dány polynomy: 𝑓(𝑥) = 8𝑥8 + 16𝑥5 + 3𝑥3 − 7; 𝑔(𝑥) = 4𝑥3 + 3, určete jejich podíl. Řešení: (8𝑥8 + 10𝑥4 + 3𝑥3 − 7) ÷ (4𝑥4 + 3) = 2𝑥4 + 1 + 3𝑥3−10 4𝑥4+3 −(8𝑥8 + 6𝑥4 ) 4𝑥4 + 3𝑥3 − 7 −(4𝑥4 + 3) 3𝑥3 − 10 Postup dělení je podobný jako u dělení celých čísel: vydělíme 8𝑥8 ÷ 4𝑥4 = 2𝑥4 , poté zpětně násobíme, 2𝑥4 ∙ 4𝑥4 = 8𝑥8 , 2𝑥4 ∙ 3 = 6𝑥4 , výsledný součin 8𝑥8 + 6𝑥4 následně odečteme od dělence a postupujeme stejným způsobem, dokud není stupeň dělitele větší než stupeň dělence (polynom 3𝑥3 − 10 je stupně 3 a stupeň dělence 𝑠𝑡(𝑔) = 4). Tento polynom je pak zbytkem. 11 1.3 Hodnota a kořen polynomu Pro práci s polynomy jsou důležitými pojmy hodnota a kořen polynomu. Definice 6: Nechť R je okruh a 𝑓 = 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ 𝑎1 𝑥 + 𝑎0 je polynom z R[𝑥], pak 𝑓(𝑐) je hodnota polynomu 𝑓 v bodě c ∈ ℝ jestliže: 𝑎 𝑛 𝑐 𝑛 + 𝑎 𝑛−1 𝑐 𝑛−1 + ⋯ + 𝑎1 𝑐 + 𝑎0 ∈ R Je-li 𝑓(𝑐) = 0, pak se prvek c nazývá kořen polynomu 𝑓. Poznámka: Z toho plyne, že každý prvek c ∈ ℝ je kořenem nulového polynomu, a naopak nenulový polynom stupně nula nemá žádný kořen. Pro hodnotu polynomu platí následující vztahy. Věta 6: Nechť R je okruh, 𝑓, 𝑔 ∈ R[𝑥] a c ∈ R . Pak platí: (1) Když 𝑓 = 𝑔, pak i 𝑓(𝑐) = 𝑔(𝑐) (2) (𝑓 ± 𝑔)(𝑐) = 𝑓(𝑐) ± 𝑔(𝑐) (3) (𝑓 ∙ 𝑔)(𝑐) = 𝑓(𝑐) ∙ 𝑔(𝑐) Příklad 4: Určete hodnotu polynomu 𝑓(𝑥) = 𝑥4 − 2𝑥3 + 3𝑥 − 5 pro 𝑐1 = 1 a 𝑐2 = 2. Řešení: Počítáme-li hodnotu pro 𝑐1 = 1, tak v polynomu 𝑓 jednoduše dosadíme za 𝑥 hodnotu 1. Výsledek je tedy −3. Pro 𝑐2 = 2 postupujeme analogicky a výsledek je 1. 𝑓(1) = 14 − 2 ∙ 13 + 3 ∙ 1 − 5 = −3 𝑓(2) = 24 − 2 ∙ 23 + 3 ∙ 2 − 5 = 1 S pojmem hodnoty polynomu se váže následující věta. Věta 7: Nechť R je okruh, pak c ∈ R je kořenem polynomu 𝑓 ∈ R[𝑥] právě když polynom (𝑥 − 𝑐) | 𝑓. Tato věta pak dává prostor pro definici násobnosti kořene. Definice 7: Nechť R je okruh, 𝑓 ∈ R[𝑥] a 𝑐 je kořenem polynomu 𝑓, pak přirozené číslo 𝑘 se nazývá násobnost kořene 𝑐, když platí: (1) (𝑥 − 𝑐) 𝑘 | 𝑓 (2) (𝑥 − 𝑐) 𝑘+1 ∤ 𝑓 Pro 𝑘 = 1 říkáme kořenu jednoduchý. 12 Například polynom 𝑓(𝑥) = 𝑥3 − 6𝑥2 + 12𝑥 − 8 lze rozložit na součin 𝑓(𝑥) = (𝑥 − 2)(𝑥 − 2)(𝑥 − 2), z čehož plyne, že tento polynom má trojnásobný kořen 𝑥 = 2. Podíváme-li se podrobně na jednotlivé struktury, zjistíme, že množina racionálních čísel ℚ je tělesem, ale ne všechny polynomické rovnice v nich mají řešení. Například polynom 𝑓 = 𝑥2 + 1 má kořeny 𝑘 = ±𝑖, což jsou kořeny, které patří až do tělesa komplexních čísel. Hledáme-li strukturu, v níž má každá polynomická rovnice řešení, musíme definovat algebraicky uzavřené těleso. Definice 8: Těleso T je algebraicky uzavřené právě tehdy, když každý polynom 𝑓 ∈ 𝑇[𝑥] stupně alespoň 1 má v tělese T alespoň jeden kořen. Z tohoto zjištění plyne základní věta algebry. Ta má několik znění, které jsou svým významem ekvivalentní. Níže je uvedeno jedno její znění a ostatní věty jsou vyvozovány jako její důsledky. Věta 8: (Základní věta algebry) Každý polynom s komplexními koeficienty, jehož stupeň je alespoň 1, má alespoň 1 komplexní kořen, tj. ∀𝑓 ∈ ℂ[𝑥] ∃𝑐 ∈ ℂ: 𝑓(𝑐) = 0. Jinými slovy: Těleso komplexních čísel je algebraicky uzavřené (Čechová, 2013). Věta 9: Nechť T je těleso a nenulový polynom 𝑓 ∈ 𝑇[𝑥], pak má tento polynom nejvýše 𝑛 = 𝑠𝑡(𝑓) kořenů, počítá-li se i s jejich násobností (Čechová, 2013). Věta 10: Libovolný polynom stupně 𝑛 ≥ 1 s komplexními koeficienty lze rozložit na součin lineárních polynomů v ℂ[𝑥] (Čechová, 2013). Věta 11: Nechť ℂ je těleso komplexních čísel, polynom 𝑓(𝑥) ∈ ℂ[𝑥] je stupně 𝑛 a jeho kořeny jsou 𝑥1, 𝑥2, … , 𝑥 𝑛. Pak lze tento polynom vyjádřit jako součin normovaných5 polynomů a nenulové konstanty 𝑎 ∈ ℂ: 𝑓(𝑥) = 𝑎(𝑥 − 𝑥1)(𝑥 − 𝑥2) … (𝑥 − 𝑥 𝑛), kde 𝑎 = 𝑎 𝑛 je vedoucí koeficient polynomu 𝑓(𝑥) (Čechová, 2013). 5 Polynom nazýváme normovaným, když se jedná o polynom nenulový a jeho vedoucí koeficient se rovná jedné. 13 1.4 Rozložitelnost, největší společný dělitel Pro práci s polynomy je také důležitý pojem rozložitelnost, resp. nerozložitelnost neboli reducibilita resp. ireducibilita polynomu. Definice 9: Polynom 𝑓 ∈ T[x] je reducibilní nad tělesem T, právě když existují polynomy 𝑔, ℎ ∈ T[x] tak, že platí 𝑓 = 𝑔 ∙ ℎ, 𝑠𝑡(𝑔) ≥ 1, 𝑠𝑡(ℎ) ≥ 1. Definice 10: Polynom 𝑓 ∈ T[x] nazýváme ireducibilní nad tělesem T, právě když 𝑠𝑡(𝑓) ≥ 1a neexistují polynomy 𝑔, ℎ ∈ T[x], tak aby 𝑓 = 𝑔 ∙ ℎ, 𝑠𝑡(𝑔) ≥ 1, 𝑠𝑡(ℎ) ≥ 1. Věta 12: Každý nekonstantní polynom 𝑓 lze nad tělesem T rozložit na součin konstanty a normovaných ireducibilních polynomů. Například polynom 𝑓(𝑥) = 3𝑥3 − 18𝑥2 + 36𝑥 − 24 bychom mohli rozložit na 𝑓(𝑥) = 3 ∙ (𝑥 − 2)(𝑥 − 2)(𝑥 − 2). O reducibilitě nemusíme nutně uvažovat nad tělesem, ale i nad jednoduššími strukturami. Například polynom 𝑓(𝑥) = 𝑥2 − 6𝑥 + 9 je rozložitelný již na množině celých čísel. Jeho rozklad vypadá 𝑓(𝑥) = (𝑥 − 3)(𝑥 − 3) a kořeny tohoto polynomu by byl jeden dvojnásobný kořen 𝑥 = 3, který patří do oboru celých čísel. Naopak polynom 𝑔(𝑥) = 𝑥2 + 2 je rozložitelný až nad tělesem komplexních čísel. Jeho rozklad je 𝑔 (𝑥) = (𝑥 − √2𝑖)(𝑥 + √2𝑖) a kořeny 𝑥1,2 = ±√2𝑖 ∈ ℂ. Výše uvedené poznatky nám teď umožňují definovat jak společného dělitele, tak i největšího společného dělitele dvou polynomů. Definice 11: Polynom ℎ ∈ T[x] je společný dělitel polynomů 𝑓, 𝑔 ∈ T[x] právě tehdy, když platí ℎ|𝑔 ∧ ℎ|𝑓. Definice 12: Nechť 𝑓, 𝑔, 𝑑 ∈ T[x]. Říkáme, že d je největší společný dělitel polynomů 𝑓, 𝑔 (značíme 𝑁𝑆𝐷(𝑓, 𝑔)), když platí: 1. 𝑑 | 𝑓 ∧ 𝑑 | 𝑔. 2. Pro všechny polynomy ℎ ∈ T[x] platí: jestliže ℎ|𝑓 ∧ ℎ|𝑔, pak ℎ|𝑑. Pro výpočet největšího společného dělitele jsou níže uvedeny dvě metody, jednou z nich (tou častější) je Eukleidův algoritmus. 14 Věta 13 (Eukleidův algoritmus): Nechť 𝑓, 𝑔 ∈ T[x] a platí 𝑠𝑡(𝑓) ≥ 𝑠𝑡(𝑔) > 0. Označme 𝑔 = 𝑔0, dělením 𝑓 ÷ 𝑔 vytvoříme posloupnost: 𝑓 = 𝑞1 ∙ 𝑔 + 𝑔1, 𝑠𝑡(𝑔1) < 𝑠𝑡(𝑔0) 𝑔 = 𝑞2 ∙ 𝑔1 + 𝑔2, 𝑠𝑡(𝑔2) < 𝑠𝑡(𝑔1) 𝑔1 = 𝑞3 ∙ 𝑔2 + 𝑔3, 𝑠𝑡(𝑔3) < 𝑠𝑡(𝑔2) … 𝑔 𝑛−3 = 𝑞 𝑛−1 ∙ 𝑔 𝑛−2 + 𝑔 𝑛−1, 𝑠𝑡(𝑔 𝑛−1) < 𝑠𝑡(𝑔 𝑛−2) 𝑔 𝑛−2 = 𝑞 𝑛 ∙ 𝑔 𝑛−1 + 𝑔 𝑛, 𝑠𝑡(𝑔 𝑛) < 𝑠𝑡(𝑔 𝑛−1), 𝑞0, 𝑞1, … , 𝑞 𝑛 ∈ ℝ. Postupujeme dokud 𝑔 𝑛 = 0. Největším společným dělitelem polynomů 𝑓, 𝑔 je pak člen 𝑔 𝑛−1, tedy 𝑁𝑆𝐷(𝑓, 𝑔) nalezneme jako poslední nenulový zbytek v této posloupnosti dělení polynomů. Důkaz: Z poslední rovnice je zřejmé, že 𝑔 𝑛−1|𝑔 𝑛−2, z předposlední rovnice zase, že 𝑔 𝑛−1|𝑔 𝑛−3. Takto postupujeme, až z prvních dvou rovnic dostaneme vztahy 𝑔 𝑛−1|𝑔 a 𝑔 𝑛−1|𝑓, což znamená, že polynom 𝑔 𝑛−1 je společným dělitelem polynomů 𝑓 a 𝑔. Zbývá dokázat, že polynom 𝑔 𝑛−1 je největším společným dělitelem 𝑓 a 𝑔. Zvolme tedy 𝑑 jako společný dělitel obou polynomů, z první rovnice je pak zřejmé, že 𝑑|𝑔1, tím pádem 𝑑|𝑔2 a tak dále, dokud nedojdeme ke vztahu 𝑑|𝑔 𝑛−1. Jelikož každý společný dělitel dělí 𝑔 𝑛−1, je tento polynom největším společným dělitelem 𝑓 a 𝑔. Použití této metody je ukázáno na následujícím příkladu. Příklad 4: Najděte největšího společného dělitele 𝑓(𝑥) = 𝑥4 − 2𝑥3 − 2𝑥2 + 7𝑥 − 6 a 𝑔(𝑥) = 2𝑥3 − 4𝑥2 − 𝑥 + 2. Řešení: Podle definice vydělíme polynom 𝑓(𝑥) polynomem 𝑔(𝑥), protože 𝑠𝑡(𝑓) = 4 a 𝑠𝑡(𝑔) = 3, což znamená, že 𝑠𝑡(𝑓) > 𝑠𝑡(𝑔). Pro následné lepší počítání s polynomy vynásobíme 𝑓(𝑥) ∙ 2. (2𝑥4 − 4𝑥3 − 4𝑥2 + 14𝑥 − 12) ÷ (2𝑥3 − 4𝑥2 − 𝑥 + 2) = 𝑥 + −3𝑥2 + 12𝑥 − 12 2𝑥3 − 4𝑥2 − 𝑥 + 2 −(2𝑥4 − 4𝑥3 − 𝑥2 + 2𝑥) −3𝑥2 + 12𝑥 − 12 Z toho plyne, že 𝑞1(𝑥) = 𝑥, 𝑔1(𝑥) = −3𝑥2 + 12𝑥 − 12, tento polynom můžeme normovat na polynom 𝑔1(𝑥) = 𝑥2 − 4𝑥 + 4, podle definice pokračujeme dělením 𝑔(𝑥) polynomem 𝑔1(𝑥). 15 (2𝑥3 − 4𝑥2 − 𝑥 + 2) ÷ (𝑥2 − 4𝑥 + 4) = 2𝑥 + 4 + 7𝑥 − 14 𝑥2 − 4𝑥 + 4 −(2𝑥3 − 8𝑥2 + 8𝑥) 4𝑥2 − 9𝑥 + 2 −(4𝑥2 − 16𝑥 + 16) 7𝑥 − 14 Pokračujeme analogicky 𝑞2(𝑥) = 2𝑥 + 4, 𝑔2(𝑥) = 7𝑥 − 14. Dělíme 𝑔1(𝑥) normovaným polynomem 𝑔2(𝑥). (𝑥2 − 4𝑥 + 4) ÷ (𝑥 − 2) = 𝑥 − 2 −(𝑥2 − 2𝑥) −2𝑥 + 4 −(−2𝑥 + 4) 0 𝑔3(𝑥) = 0, největším společným dělitelem je tedy polynom 𝑔2(𝑥) = 𝑥 − 2. 𝑁𝑆𝐷(𝑓, 𝑔) = 𝑐 ∙ (𝑥 − 2), kde 𝑐 ∈ ℝ. Poznámka: Polynomy 𝑔1(𝑥), 𝑔2(𝑥), … 𝑔 𝑛(𝑥) normujeme, abychom předešli zbytečném počítáním se zlomky, v čemž se často chybuje. Největší společný dělitel je proto určen jednoznačně, až na vynásobení polynomu číslem 𝑐 z tělesa T. Největšího společného dělitele dvou polynomů je možno také spočítat pomocí rozkladů jednotlivých polynomů na součin, k tomu využijeme Hornerovo schéma. Věta 14 (Hornerovo schéma): Nechť 𝑐 ∈ 𝑇 je libovolné a 𝑓(𝑥), 𝑔(𝑥) ∈ 𝑅[𝑥], 𝑠𝑡(𝑓) = 𝑛 ≥ 1, jsou tvaru: 𝑓(𝑥) = 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎1 𝑥 + 𝑎0, kde 𝑎𝑖 ∈ 𝑅, 𝑎 𝑛 ≠ 0, 𝑔 = 𝑥 − 𝑐. Pak existuje polynom 𝑞, 𝑠𝑡(𝑞) = 𝑛 −1, 𝑞(𝑥) = 𝑏 𝑛−1 𝑥 𝑛−1 + 𝑏 𝑛−2 𝑥 𝑛−2 + ⋯ + 𝑏0, a platí 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎0 = (𝑥 − 𝑐)(b 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑏0) + 𝑓(𝑐) (Fišnarová, 2008). Tuto situaci vepisujeme do tabulky: 𝑎 𝑛 𝑎 𝑛−1 … 𝑎1 𝑎0 c 𝑏 𝑛−1 𝑏 𝑛−2 … 𝑏0 𝑓(𝑐) Tabulka 1: Tabulka pro Hornerovo schéma 16 Důkaz: Roznásobením pravých stran výše uvedených rovnic a jejich úpravami dostaneme následující vztahy: 𝑎 𝑛 = 𝑏 𝑛−1 𝑎 𝑛−1 = 𝑏 𝑛−2 − 𝑐𝑏 𝑛−1 ⇒ 𝑏 𝑛−2 = 𝑐𝑏 𝑛−1 + 𝑎 𝑛−1 𝑎 𝑛−2 = 𝑏 𝑛−3 − 𝑐𝑏 𝑛−2 ⇒ 𝑏 𝑛−3 = 𝑐𝑏 𝑛−2 + 𝑎 𝑛−2 … 𝑎0 = 𝑓(𝑐) − 𝑐𝑏0 ⇒ 𝑓(𝑐) = 𝑐𝑏0 + 𝑎0 Dosadíme-li je za jednotlivé členy 𝑎 𝑛, 𝑎 𝑛−1, 𝑎 𝑛−2, … , 𝑎0 dostaneme: 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎0 = 𝑏 𝑛−1 𝑥 + (𝑏 𝑛−3 − 𝑐𝑏 𝑛−2)𝑥 𝑛−1 + ⋯ + 𝑓(𝑐) − 𝑐𝑏0 Členy na pravé straně roznásobíme 𝑏 𝑛−1 𝑥 + 𝑏 𝑛−3 𝑥 𝑛−1 − 𝑐𝑏 𝑛−2 𝑥 𝑛−1 + ⋯ + 𝑓(𝑐) − 𝑐𝑏0 a následně vytkneme 𝑥 − 𝑐 ⇒ (𝑥 − 𝑐)(𝑏 𝑛−1 𝑥 𝑛−1 + 𝑏 𝑛−2 𝑥 𝑛−2) + ⋯ + 𝑓(𝑐), což dokazuje, že 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎0 = (𝑥 − 𝑐)(𝑏 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑏0) + 𝑓(𝑐) platí. Jak vypadá práce s Hornerovým schématem v praxi, ukážeme na následujícím příkladu. Příklad 5: Určete největšího společného dělitele polynomů 𝑓(𝑥) = 𝑥4 + 5𝑥3 + 7𝑥2 + 5𝑥 + 6 a 𝑔(𝑥) = 𝑥4 − 1. Řešení: Polynomy se snažíme rozložit na součin polynomů nižšího stupně (nejlépe stupně jedna): 𝑓(𝑥) = 𝑥4 + 5𝑥3 + 7𝑥2 + 5𝑥 + 6 1= 𝑎4 5 = 𝑎3 7 = 𝑎2 5 = 𝑎1 6 = 𝑎0 -2 1 = 𝑏3 3 = 𝑏2 1 = 𝑏1 3 = 𝑏0 0 = 𝑓(−2) -3 1 = 𝑑2 0 = 𝑑1 1 = 𝑑0 0 = 𝑓(−3) Tabulka 2: Výpočet kořenu polynomu f(𝑥) = 𝑥4 + 5𝑥3 + 7𝑥2 + 5𝑥 + 6 pomocí Hornerova schématu V Hornerově schématu vycházíme z námi vyjádřených vztahů, které jsou uvedeny výše. První koeficient 𝑎4 (v tomto případě 1) opisujeme 𝑎4 = 𝑏3. Poté námi zvolené číslo 𝑐 = −2 vynásobíme s 𝑏3 a sečteme s koeficientem 𝑎3 = 5, čímž dostaneme člen 𝑏2 = 3, takto postupujeme s dalšími koeficienty. Pokud c ∙ 𝑏0 + 𝑎0 = 0, pak dané číslo c = −2 je kořenem polynom 𝑓(𝑥) a ten lze proto rozložit na součin polynomů (𝑥 + 2)( 𝑥3 + 3𝑥2 + 𝑥 + 2). Další kořeny nalezneme stejným způsobem, vstupní vektor koeficientu nového Hornerova schématu však tvoří polynom 𝑓1(𝑥) = 𝑥3 + 3𝑥2 + 𝑥 + 2, tj. hodnoty 𝑏 𝑛−1, 𝑏 𝑛−2, … , 𝑏0, které jsme právě získali v předešlém kroku. Polynom stupně dvě 17 určený koeficienty 𝑑2, 𝑑1, 𝑑0 obsahuje komplexní kořeny, proto je můžeme vypočítat pomocí Vietových vztahů6 či vzorce pro výpočet kvadratické rovnice7 . Rozklad 𝑓(𝑥) pak má tvar 𝑓(𝑥) = (𝑥 + 2)(𝑥 + 3)(𝑥2 + 1). Vietovy vztahy či vzorec pro kvadratické rovnice lze použít vždy, když se jedná o polynom stupně dva bez ohledu na to, jedná-li se o kořeny komplexní či nikoli. Výpočet je mnohdy rychlejší, protože nemusíme hledat číslo 𝑐. Analogicky pokračujeme s druhým polynomem: 𝑔(𝑥) = 𝑥4 − 1 Rozklad podle Hornerova schématu: 1 0 0 0 -1 1 1 1 1 1 0 -1 1 0 1 0 Tabulka 3: Hledání kořeny polynomu 𝑔(𝑥) = 𝑥4 − 1 pomocí Hornerova schématu V tomto případě lze polynom rozložit také pomocí algebraických vzorců8 . Jeho rozklad vypadá. 𝑔(𝑥) = (𝑥 + 1)(𝑥 − 1)(𝑥2 + 1). Největším společným dělitelem je pak součin všech polynomů, které mají oba polynomy totožné, což je (𝑥2 + 1). Tento polynom je určen jednoznačně až na násobek reálným číslem. 𝑁𝑆𝐷(𝑓, 𝑔) = c ∙ (𝑥2 + 1), c ∈ ℝ Poznámka: Hornerovo schéma lze také využít k hledání koeficientů Taylorova rozvoje9 , když zvolíme 𝑐 = 1. Například pro polynom 𝑓(𝑥) = 𝑥3 − 2𝑥 + 1 vypadá rozklad podle Hornerova schématu následovně: 6 Předpokládáme, že polynom je ve tvaru 𝑎𝑥2 + 𝑏𝑥 + 𝑐. Vietovy vztahy pak vypadají: 𝑥1 + 𝑥2 = − 𝑏 𝑎 ; 𝑥1 ∙ 𝑥2 = 𝑐 𝑎 (Hašek, 2018) 7 Předpokládáme, že polynom je ve tvaru 𝑎𝑥2 + 𝑏𝑥 + 𝑐 kořeny se poté vypočítají pomocí vzorce pro kvadratické rovnice 𝑥1,2 = −𝑏 ± √𝑏2 − 4𝑎𝑐 2𝑎 8 Mezi základní algebraické vzorce patří: (𝐴 + 𝐵)2 = 𝐴2 + 2𝐴𝐵 + 𝐵2 , (𝐴 − 𝐵)2 = 𝐴2 − 2𝐴𝐵 + 𝐵2 , 𝐴2 − 𝐵2 = (𝐴 − 𝐵) ∙ (𝐴 + 𝐵) 9 Nechť 𝑓(𝑥) ∈ 𝑅[𝑥]; 𝑐 ∈ 𝑅. Taylorův polynom o středu 𝑐 polynomu 𝑓 má pak tvar: 𝑓(𝑥) = 𝑎 𝑛(𝑥 − 𝑐) 𝑛 + ⋯ + 𝑎2(𝑥 − 𝑐)2 + 𝑎1(𝑥 − 𝑐) + 𝑎0 A nechť 𝑓 ∈ 𝑅[𝑥], 𝑠𝑡(𝑓) = 𝑛 ≥ 1; nechť 𝑐 ∈ 𝑅. Pak existuje právě jeden Taylorův polynom o středu 𝑐 polynomu 𝑓, a sice: 𝑓(𝑥) = 𝑓(𝑐) + 𝑓′(𝑐) 1! (𝑥 − 𝑐) + 𝑓′′(𝑐) 2! (𝑥 − 𝑐)2 + ⋯ + 𝑓(𝑛) (𝑐) 𝑛! (𝑥 − 𝑐) 𝑛 18 1 0 -2 1 1 1 1 -1 0 1 1 2 1 1 1 3 1 1 Tabulka 4: Vztah mezi Taylorovým rozvojem a Hornerovým schématem pro polynom 𝑓(𝑥) = 𝑥3 − 2𝑥 + 1 𝑐 = 𝑥0 a čísla 0, 1, 3 a 1 jsou koeficienty Taylorova rozvoje, který má tvar: 𝑓(𝑥) = (𝑥 − 1) + 3(𝑥 − 1)2 + (𝑥 − 1)3 1.5 Derivace polynomu Proto, aby bylo možné využít námi zvolené numerické metody pro výpočet polynomických rovnic, je důležité definovat derivaci polynomu. Tu využijeme následně v Newtonově metodě. Definice 13: Nechť 𝑓 ∈ ℝ[𝑥], kde 𝑓 = 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 +. . . +𝑎1 𝑥 + 𝑎0. Derivací polynomu 𝑓 je pak polynom 𝑓′ ∈ ℝ[𝑥] definován vztahem: (1) Když 𝑠𝑡(𝑓) = 0, pak 𝑓′ = 0 (2) Když 𝑠𝑡(𝑓) > 0, pak 𝑓′ = 𝑛 ∙ 𝑎 𝑛 ∙ 𝑥 𝑛−1 + ⋯ + 2𝑎2 𝑥1 + 𝑎1 Pro polynomy a jejich derivace pak platí následující vztahy Věta 15: Nechť 𝑓, 𝑔 ∈ 𝑇[𝑥], pak: (1) 𝑠𝑡(𝑓) = 𝑛 ≥ 1, pak 𝑠𝑡(𝑓′) = 𝑛 − 1 (2) (𝑓 ± 𝑔)′ = 𝑓′ ± 𝑔′ (3) (𝑓1 + ⋯ + 𝑓𝑘)′ = 𝑓1 ′ + ⋯ + 𝑓𝑘′ (4) (𝑓 ∙ 𝑔)′ = 𝑓′ ∙ 𝑔 + 𝑓 ∙ 𝑔′ (5) (𝑓1 ∙ … ∙ 𝑓𝑘)′ = 𝑓1∙ ′ ∙ 𝑓2 ∙ … ∙ 𝑓𝑘 + ⋯ + 𝑓1 ∙ … ∙ 𝑓𝑘−1 ∙ 𝑓𝑘′ (6) (𝑓 𝑘)′ = 𝑘 ∙ 𝑓′ ∙ 𝑓 𝑘−1 , 𝑘 ∈ ℕ Níže jsou uvedeny vztahy mezi kořeny polynomu 𝑓 a kořeny derivovaného polynomu 𝑓′ . Věta 16: Nechť 𝑓 ∈ 𝑇[𝑥], 𝑐 ∈ 𝑇 a 𝑘 ∈ ℕ přičemž 𝑘 ≥ 2. Je-li 𝑐 𝑘-násobným kořenem polynomu 𝑓, pak v polynomu 𝑓′ je 𝑐 (𝑘 − 1)-násobným kořenem. Pokud je 𝑐 jednoduchým kořenem v polynomu 𝑓, pak není kořenem v polynomu 𝑓′. 19 Důkaz: Nechť 𝑓 je polynom stupně 𝑘 a 𝑐 je 𝑘-násobným kořenem polynomu 𝑓, pak podle vztahu (5) ve větě 15 můžeme derivaci toho polynomu zapsat jako: [(𝑥 − 𝑥1)𝑙1(𝑥 − 𝑥2)𝑙2 … (𝑥 − 𝑥 𝑟)𝑙 𝑟(𝑥 − 𝑐) 𝑘]′ = 𝑘 ∙ (𝑥 − 𝑥1)𝑙1(𝑥 − 𝑥2)𝑙2 … (𝑥 − 𝑥 𝑟)𝑙 𝑟(𝑥 − 𝑐) 𝑘−1 + 𝑙1 ∙ (𝑥 − 𝑥1)𝑙1−1(𝑥 − 𝑥2)𝑙2 … (𝑥 − 𝑥 𝑟)𝑙 𝑟(𝑥 − 𝑐) 𝑘 + 𝑙2 ∙ (𝑥 − 𝑥1)𝑙1(𝑥 − 𝑥2)𝑙2−1 … (𝑥 − 𝑥 𝑟)𝑙 𝑟(𝑥 − 𝑐) 𝑘 + ⋯ +𝑙 𝑟 ∙ (𝑥 − 𝑥1)𝑙1(𝑥 − 𝑥2)𝑙2 … (𝑥 − 𝑥 𝑟)𝑙 𝑟−1(𝑥 − 𝑐) 𝑘 . Závorku (𝑥 − 𝑐) 𝑘−1 lze vytknout ze všech členů, ale závorku (𝑥 − 𝑐) 𝑘 už vytknout nelze. Tedy 𝑐 je (𝑘 − 1)-násobným kořenem polynomu 𝑓′. Tuto větu je možno využít při hledání násobných kořenů polynomu. Příklad 6: V polynomu 𝑓 = 𝑥5 − 𝑎𝑥2 − 𝑎𝑥 + 1 určete 𝑎 tak, aby číslo 𝑐 = −1 bylo alespoň dvojnásobným kořenem (Budínová, 2013). Řešení: Nejdříve polynom zderivujeme 𝑓′(𝑥) = 5𝑥4 − 2𝑎𝑥 − 𝑎 a určíme hodnoty v bodě 𝑥 = −1 polynomů 𝑓 a 𝑓′ . 𝑓(−1) = −1 − 𝑎 + 𝑎 + 1 = 0 𝑓′(−1) = 5 + 2𝑎 − 𝑎 = 5 + 𝑎 Nyní řešíme rovnice: 0 = 0 a 5 + 𝑎 = 0, z druhé rovnice nám plyne, že 𝑎 = −5, což znamená, že hledaný polynom má tvar 𝑓 = 𝑥5 + 5𝑥2 + 5𝑥 + 1. Správnost můžeme ověřit tak, že polynom 𝑓 = 𝑥5 + 5𝑥2 + 5𝑥 + 1 vydělíme polynomem (𝑥 + 1)2 , což se rovná 𝑥3 − 2𝑥2 + 3𝑥 + 1 a zbytek je nula, proto je 𝑐 = −1 dvojnásobným kořenem polynomu 𝑓 = 𝑥5 + 5𝑥2 + 5𝑥 + 1. Věta 17: Nechť 𝑓 ∈ ℝ[𝑥], 𝑠𝑡(𝑓) ≥ 1 a 𝑓′ ∈ ℝ[𝑥] je derivací polynomu 𝑓, pak 𝑔 ∈ ℝ[𝑥] je polynom, pro který platí: 𝑓 = 𝑁𝑆𝐷(𝑓, 𝑓′ ) ∙ 𝑔 Kořeny polynomu 𝑔 a polynomu 𝑓 jsou tedy totožné, ale polynom 𝑔 obsahuje pouze kořeny jednoduché. To znamená, vydělíme-li polynom 𝑓 největším společným dělitelem 𝑓 a 𝑓′ dostaneme polynom 𝑔, jenž skýtá stejné kořeny jako 𝑓, ale pouze násobnosti 1, což je velmi užitečné pro hledání kořenů polynomických rovnic, jak je ukázáno na následujícím příkladu. Příklad 7: Najděte kořeny polynomu 𝑓 = 16𝑥4 − 64𝑥3 + 120𝑥2 − 112𝑥 + 49. Řešení: Nejdříve spočítáme derivaci polynomu 𝑓. 𝑓′ = 64𝑥3 − 192𝑥2 + 240𝑥 − 112 20 Následně spočítáme 𝑁𝑆𝐷(𝑓, 𝑓′ ) pomocí Eukleidova algoritmu: (16𝑥4 − 64𝑥3 + 120𝑥2 − 112𝑥 + 49) ÷ ( 64𝑥3 − 192𝑥2 + 240𝑥 − 112) = 1 4 𝑥 − 1 4 + + 12𝑥2 − 24𝑥 + 21 64𝑥3 − 192𝑥2 + 240𝑥 − 112 −(16𝑥4 − 48𝑥3 + 60𝑥2 − 28𝑥) −16𝑥3 + 60𝑥2 − 84𝑥 + 49 −(−16𝑥3 + 48𝑥2 − 60𝑥 + 28) 12𝑥2 − 24𝑥 + 21 Nově vzniklý polynom 𝑝1 = 12𝑥2 − 24𝑥 + 21 můžeme normovat na polynom 𝑝1 = 4𝑥2 − 8𝑥 + 7 a pokračujeme: ( 64𝑥3 − 192𝑥2 + 240𝑥 − 112) ÷ ( 4𝑥2 − 8𝑥 + 7) = 16𝑥 − 16 −(64𝑥3 − 128𝑥2 + 112𝑥) −64𝑥2 + 128𝑥 − 112 −(−64𝑥2 + 128𝑥 − 112) 0 Největším společným dělitelem 𝑓 a 𝑓′ je tedy polynom 𝑔1 = 4𝑥2 − 8𝑥 + 7. 𝑁𝑆𝐷(𝑓, 𝑓′) = 𝑐 ∙ (4𝑥2 − 8𝑥 + 7). Tímto polynomem vydělíme polynom 𝑓. (16𝑥4 − 64𝑥3 + 120𝑥2 − 112𝑥 + 49) ÷ ( 4𝑥2 − 8𝑥 + 7) = 4𝑥2 − 8𝑥 + 7 −(16𝑥4 − 32𝑥3 + 28𝑥2 ) −32𝑥3 + 92𝑥2 − 112𝑥 + 49 −(−32𝑥3 + 64𝑥2 − 56𝑥) 28𝑥2 − 56𝑥 + 49 −(−28𝑥2 − 56𝑥 + 49) 0 Polynom 𝑔 = 4𝑥2 − 8𝑥 + 7 má tedy stejné kořeny jako polynom 𝑓 jenom násobnosti 1. Vypočítáme tedy kořeny polynomu 𝑔 a to buď pomocí Vietových vztahů nebo vzorcem pro výpočet kvadratické rovnice. 𝑥1,2 = 1 ± 𝑖 ∙ √3 2 Kořeny původního polynomu 𝑓 jsou tedy dva komplexně sdružené dvojnásobné kořeny 𝑥1,2 = 1 + 𝑖 ∙ √3 2 a 𝑥3,4 = 1 − 𝑖 ∙ √3 2 . 21 1.6 Polynomické rovnice Veškerá předchozí teorie nám umožňuje přejít k jádru bakalářské práce, a tím je řešení polynomických rovnic. Definice 14 (Algebraická rovnice): Nechť 𝑃𝑛(𝑥) = 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎1 𝑥 + 𝑎0 je polynom stupně 𝑛, kde 𝑎 𝑛 ≠ 0. Algebraickou rovnici stupně 𝑛 rozumíme rovnici ve tvaru 𝑃𝑛(𝑥) = 0, tj. 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎1 𝑥 + 𝑎0 = 0. Řešit algebraické (neboli polynomické) rovnice znamená hledat jejich kořeny 𝜉𝑖. Přičemž v rovnici je tolik kořenů, jaký je stupeň polynomu 𝑃𝑛(𝑥), počítáme-li s jejich násobností (Věta 9). Kořeny polynomických rovnic mohou být jak reálné, tak komplexní, přičemž když jsou všechny 𝑎𝑖 reálná, tak jsou komplexní kořeny vždy komplexně sdružená čísla 𝜉1 = 𝑎 + 𝑏𝑖 a 𝜉2 = 𝑎 − 𝑏𝑖. Hledáme-li pouze racionální kořeny, můžeme použít Hornerovo schéma (Věta 14), přičemž za 𝑐 dosazujeme následující čísla. Věta 18: Nechť polynom 𝑓(𝑥) ∈ 𝑇[𝑥] je tvaru 𝑓 = 𝑎 𝑛 𝑥 𝑛 + 𝑎 𝑛−1 𝑥 𝑛−1 + ⋯ + 𝑎1 𝑥 + 𝑎0, 𝑐 = 𝑝 𝑞 je racionálním kořenem, tak že 𝑝 ∈ ℤ ∧ 𝑝 ≠ 0, 𝑞 ∈ ℕ a platí: (1) Čísla 𝑝 a 𝑞 jsou nesoudělná. (2) 𝑝|𝑎 𝑜 a 𝑞|𝑎 𝑛. Příklad 8: Najděte kořeny polynomu 𝑓(𝑥) = 6𝑥3 + 7𝑥2 − 𝑥 − 2. Řešení: Hledáme čísla 𝑝 a 𝑞, tedy taková, že 𝑝|2 a 𝑞|6. 𝑝 = ±1; ±2 𝑞 = 1; 2; 3; 6 Kořeny rovnice pak mohou být čísla 𝑐 = 𝑝 𝑞 : 𝑐 = ±1; ± 1 2 ; ± 1 3 ; ± 1 6 ; ±2; ± 2 3 Zdali jsou tato čísla kořeny rovnice ověříme pomocí Hornerova schématu. 22 6 7 −1 −2 6 7 −𝟏 −2 1 6 13 12 10 1 6 6 8 1 3 − 35 18 −1 6 1 −2 0 − 1 6 6 6 −2 − 5 3 1 2 6 10 4 0 2 6 19 37 72 − 1 2 6 4 −3 − 1 2 −2 6 −5 9 −20 1 3 6 9 2 − 4 3 2 3 6 11 19 3 20 9 − 1 3 6 5 − 8 3 − 10 9 − 2 3 6 3 −3 0 Tabulka 5: Hornerovo schéma pro výpočet kořenů polynomu 𝑓(𝑥) = 6𝑥3 + 7𝑥2 − 𝑥 − 2 Zjistili jsme, že kořeny rovnice 6𝑥3 + 7𝑥2 − 𝑥 − 2 = 0 jsou 𝑥1 = −1, 𝑥2 = 1 2 , 𝑥3 = − 2 3 . Ve výjimečných případech lze k nalezení kořenů polynomu použít i algebraické vzorce či Vietovy vztahy (viz Příklad 5). Mezi další možné metody, které ještě v této kapitole nebyly zmíněny, jsou vzorce pro kubické a kvartické rovnice (rovnice 3. a 4. stupně). Pro rovnice vyššího řádu, než je čtyři, žádný univerzální vzorec neexistuje10 . Vzorce jsou však již docela složité a užívají se jen zřídka, proto je zde uveden pouze vzorce pro výpočet kubických rovnic, které využívají tzv. Cardanových vzorců. Věta 19: Nechť 𝑎, 𝑏, 𝑐 ∈ 𝑅 a 𝑥3 + 𝑎𝑥2 + 𝑏𝑥 + 𝑐 = 0 je kubická rovnice, pro výpočet jejich kořenů nejdříve zavedeme substituci 𝑥 = 𝑦 − 𝑎 3 , rovnice vypadá: (1) 𝑦3 + 𝑝𝑦 + 𝑞 = 0, kde 𝑝 = 𝑏 − 𝑎2 3 a 𝑞 = 𝑐 + 2𝑎3−9𝑎𝑏 27 . Předpokládejme, že 𝑝 ≠ 0. Dále zavedeme neznámé 𝑢, 𝑣 splňující podmínky 𝑢 + 𝑣 = 𝑦. Dosazením podmínky do původní rovnice nám vznikne: (2) 𝑢3 + 𝑣3 + (3𝑢𝑣 + 𝑝)(𝑢 + 𝑣) + 𝑞 = 0 a abychom anulovali závorku (3𝑢𝑣 + 𝑝), zavedeme 3𝑢𝑣 + 𝑝 = 0. Dostaneme tak vztah 𝑢𝑣 = − 𝑝 3 . Tento vztah umocníme na třetí 𝑢3 ∙ 𝑣3 = 𝑝3 27 a spolu s upraveným vztahem (2) 10 Neexistenci obecného vzorce pro řešení libovolné rovnice stupně vyššího než 4 dokázal Niels Henrik Abel ve svém díle „O algebraických rovnicích“ vydaného roku 1824. 23 𝑢3 + 𝑣3 = −𝑞 na ně můžeme nahlížet jako na Vietovy vzorce pro kořeny 𝑢3 , 𝑣3 kvadratické rovnice. 𝑧2 + 𝑞𝑧 − 𝑝3 27 = 0 Kořeny se budou rovnat: (3) 𝑢3 = − 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 𝑎 𝑣3 = − 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 Diskriminantem rovnice označíme hodnotu 𝐷3 = 𝑞2 4 + 𝑝3 27 . Rovnice tak budou mít devět řešení, ale kořeny jsou pouze ta, která vyhovují podmínce 𝑣 = − 𝑝 3𝑢 . Každá ze tří hodnot 𝑢 tedy odpovídá jedné hodnotě 𝑣. Nechť čísla 𝜀1, 𝜀2 jsou komplexně sdružené kořeny rovnice 𝑥3 − 1 = 0, pak se rovnají 𝜀1,2 = −1 ± √3 2 . Kořeny rovnice (1) tak můžeme zapsat: (4) 𝑦1 = 𝑢 + 𝑣 (5) 𝑦2 = 𝜀1 𝑢 + 𝜀2 𝑣 (6) 𝑦3 = 𝜀2 𝑢 + 𝜀1 𝑣 Po dosazení 𝑢, 𝑣 do výše uvedených vztahů dostaneme: 𝑦1 = √− 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 3 + √− 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 3 𝑦2 = 𝜀1 √− 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 3 + 𝜀2 √− 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 3 𝑦3 = 𝜀2 √− 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 3 + 𝜀1 √− 𝑞 2 ± √ 𝑞2 4 + 𝑝3 27 3 (Slovák, Panák, Bulant, Návrat, & Veselý, 2013) Příklad 9: Určete řešení rovnice 𝑥3 − 9𝑥2 + 36𝑥 − 28 = 0 (Páv, 2010). Řešení: Nejdříve chceme rovnici upravit do tvaru 𝑦3 + 𝑝𝑦 + 𝑞 = 0, proto zavedeme substituci 𝑥 = 𝑦 − 𝑎 3 . V zadání se 𝑎 = −9 , takže substituce má tvar 𝑥 = 𝑦 + 3. (𝑦 + 3)3 − 9 ∙ (𝑦 + 3)2 + 36 ∙ (𝑦 + 3) − 28 = 0 24 𝑦3 + 9𝑦2 + 27𝑦 + 27 − 9𝑦2 − 54𝑦 − 81 + 36𝑦 + 108 − 28 = 0 𝑦3 + 9𝑦 + 26 = 0 Teď si vyjádříme 𝑢 a 𝑣 podle vztahu (3): 𝑢 = √− 26 2 + √ 262 4 + 93 27 3 = √−13 + √132 + 33 3 = √−13 + √196 3 = √−13 + 14 3 = = √1 3 Za 𝑢 si můžeme zvolit přímo číslo 1 a odpovídající 𝑣 poté dostaneme dosazením do podmínky 𝑣 = − 𝑝 3𝑢 : 𝑣 = − 9 3 ∙ 1 = −3 Kořeny rovnice 𝑦3 + 9𝑦 + 26 = 0 se tedy rovnají (podle vztahů (4)-(6)): 𝑦1 = 1 − 3 = −2 𝑦2 = 𝜀1 − 3𝜀2 = 1 + 2𝑖√3 𝑦3 = 1𝜀2 − 3𝜀1 = 1 − 2𝑖√3 Máme-li kořeny námi upravené rovnice, dosadíme do substituce 𝑥 = 𝑦 + 3 a získáme kořeny naší původní rovnice 𝑥3 − 9𝑥2 + 36𝑥 − 28 = 0. 𝑥1 = −2 + 3 = 1 𝑥2 = 1 + 2𝑖√3 + 3 = 4 + 2𝑖√3 𝑥3 = 1 − 2𝑖√3 + 3 = 4 − 2𝑖√3 Můžeme si povšimnout, že komplexní kořeny jsou vždy komplexně sdružená čísla. I přesto, že jsme zde uvedli již řadu metod pro výpočet polynomických rovnic, stále je ještě mnoho případů, kdy nemůžeme kořeny určit, jedním z nich je následující příklad. Příklad 10: Je dán polynom 𝑓(𝑥) = 𝑥6 + 𝑥5 + 4𝑥4 + 3𝑥3 + 5𝑥2 + 2𝑥 + 2. Nalezněte jeho kořeny. Řešení: Nejdříve zkusíme určit, zdali má polynom nějaké násobné kořeny (viz Příklad 7). Po provedení Eukleidova algoritmu dospějeme k závěru, že největším společným dělitelem polynomu 𝑓 = 𝑥6 + 𝑥5 + 4𝑥4 + 3𝑥3 + 5𝑥2 + 2𝑥 + 2 a jeho derivace 𝑓′ = 6𝑥5 + 5𝑥4 + 16𝑥3 + 9𝑥2 + 10𝑥 je jedna, 𝑁𝑆𝐷(𝑓, 𝑓′) = 1, což znamená, že polynom nemá žádné násobné kořeny. Dále zkusíme najít racionální kořeny tohoto polynomu, pomocí Hornerova schématu (Věta 18). 25 1 1 4 3 5 2 2 -1 1 -1 5 -2 7 -5 7 1 1 1 5 8 13 15 17 -2 1 -2 8 -13 31 -60 122 2 1 2 8 19 43 88 178 Tabulka 6: Hornerovo schéma pro výpočet kořenů polynomu 𝑓(𝑥) = 𝑥6 + 𝑥5 + 4𝑥4 + 3𝑥3 + 5𝑥2 + 2𝑥 + 2 Z tabulky je zřejmé, že polynom neobsahuje žádné racionální kořeny, takže kořeny daného polynomu jsou iracionální nebo komplexní čísla. Jelikož je daný polynom stupně 6, nelze na něj uplatnit ani žádný vzorec, protože existují vzorce maximálně pro rovnice 4. stupně. Pro výpočet kořenů tedy musíme použít numerické metody, které jsou rozebrány v následující kapitole. 26 2. NUMERICKÉ METODY V této kapitole se budeme zabývat řešením polynomických rovnic, které často nedokážeme vypočítat žádným jiným způsobem. Zabývejme se však nejprve úvahami, které naleznou reálné kořeny dané polynomické rovnice. Ne vždy je nalezení (zejména iracionálních) kořenů jednoduché a často dokážeme určit pouze jejich přibližnou hodnotu, je proto důležité nejdříve stanovit, v jakém intervalu se kořeny nachází (hledáme právě jeden kořen v daném intervalu). Tento proces se nazývá separace kořenů rovnice. Při hledání jednotlivých kořenů je užitečná následující věta. Věta 20: Je-li funkce 𝑓 spojitá11 na intervalu ⟨𝑎, 𝑏⟩, leží v tomto intervalu alespoň jeden kořen rovnice 𝑓(𝑥) = 0, když platí: 𝑓(𝑎) ∙ 𝑓(𝑏) < 0. Tato věta předpokládá, že funkční hodnoty v krajních bodech daného intervalu mají opačná znaménka, z čehož plyne, že křivka, která je grafem levé strany rovnice 𝑓(𝑥) = 0, někde protíná osu 𝑥. Jinými slovy, hodnota nějakého prvku se rovná 0 a jak je zmíněno v předchozí kapitole, kořenem rovnice je prvek 𝑐 právě tehdy, když 𝑓(𝑐) = 0. Tato věta však nezaručuje nalezení všech kořenů a jejich intervalů. Interval nemusí být totiž vždy zvolen vhodně, a i když věta nebude platit, může se v daném intervalu kořen (či více kořenů) nacházet, jak je vidět na následujícím příkladu. Příklad 11: Nalezněte kořeny polynomu 𝑓(𝑥) = 𝑥2 − 1. Řešení: Najít tyto kořeny znamená vyřešit rovnici 𝑥2 − 1 = 0. Je zřejmé, že polynom bude mít dva kořeny (Věta 9), či jeden dvojnásobný kořen, protože 𝑠𝑡(𝑓) = 2. Kořeny bychom mohli najít rozkladem na součin pomocí algebraických vzorců. 𝑥2 − 1 = 0 (𝑥 − 1)(𝑥 + 1) = 0 Kořeny daného polynomu jsou 𝑥1 = 1, 𝑥2 = −1. Kdybychom se však řídili předchozí větou a zvolili interval 𝐼 = ⟨−2, 2⟩, vyšlo by 𝑓(−2) = 3 a 𝑓(2) = 3. Jejich součin 3 ∙ 3 > 0. Také dvojnásobné kořeny se vymykají pravdivosti této věty. Například graf polynomu 𝑔(𝑥) = 𝑥2 + 2𝑥 + 1 se osy 𝑥 pouze 11 Funkce 𝑓(𝑥) je spojitá v bodě 𝑎, když lim 𝑥→𝑎 𝑓(𝑥) = 𝑓(𝑎). Funkce je spojitá na intervalu 𝐼, právě tehdy když je spojitá v každém bodě tohoto intervalu (Spojitost funkce, 2018). 27 dotkne, ale nenabývá nikde záporných hodnot, tudíž 𝑓(𝑎) ∙ 𝑓(𝑏) ≥ 0, ∀𝑎, 𝑏 ∈ 𝑅. To je ilustrací faktu, že podmínka 𝑓(𝑎) ∙ 𝑓(𝑏) < 0 je u polynomu dostatečná, nikoli nutná pro existenci kořene polynomu 𝑓 na intervalu 〈𝑎, 𝑏〉. Dalším důležitým vodítkem pro nalezení řešení polynomických rovnic je tedy základní znalost vlastností funkcí a zejména nakreslený graf. Kdybychom uplatnili tento postup na předchozí příklad (Příklad 11) a nejdříve nakreslili graf funkce 𝑓 = 𝑥2 − 1 (Obrázek 1), bylo by zřejmé, že námi zvolený interval 𝐼 = ⟨−2, 2⟩ je příliš velký. Navíc bychom v tomto příkladu mohli kořeny rovnice určit z grafu rovnou (graf totiž protíná osu 𝑥 v bodech −1 a 1). V některých případech je možné si úlohu upravit na tvar 𝑓1(𝑥) = 𝑓2(𝑥), kde 𝑓1 a 𝑓2 jsou funkce a řešení úlohy je v místě, kde se grafy obou funkcí protnou. Tento případ je znázorněn na příkladu níže. Příklad 12: Najděte řešení polynomické rovnice 𝑥5 − 𝑥2 − 1 = 0. Řešení: Rovnici si upravíme na tvar 𝑥2 + 1 = 𝑥5 , což znamená, že 𝑓1(𝑥) = 𝑥2 + 1 a 𝑓2(𝑥) = 𝑥5 . Nakreslíme jejich grafy (Obrázek 2). Z grafu vyplývá, že řešením je 𝑥-ová souřadnice průsečíku grafů obou funkcí, tedy 𝑥 ∈ 〈1,2〉. S takto připraveným teoretickým základem již můžeme přistoupit k popisu jednotlivých numerických metod. Pro tuto bakalářskou práci jsou vybrány tři, jmenovitě: metoda půlení intervalu, Newtonova metoda a metoda prosté iterace. Každé zvlášť je níže věnována jedna podkapitola. Materiál pro tuto kapitolu je čerpán z učebního materiálu doktora Fajmona a magistry Růžičkové (2003), knihy Ivany Horové (1999) a knihy Canale a Chapra (2010). Obrázek 1: Graf funkce 𝑓 = 𝑥2 − 1 28 2.1. Metoda půlení intervalu Této metodě se také často přezdívá bisekce a je poměrně jednoduchá. Nejdříve volíme interval ⟨𝑎, 𝑏⟩, pro nějž je daná funkce 𝑓(𝑥) spojitá a musí platit, že 𝑓(𝑎) ∙ 𝑓(𝑏) < 0, což znamená, že obsahuje kořen. Přitom v tomto intervalu musí ležet pouze jeden kořen dané funkce. Tento výchozí interval označme jako ⟨𝑎0, 𝑏0⟩ a „rozpůlíme“ jej. Získáme tak bod 𝑥0 = 𝑎0+𝑏0 2 . Poté vybíráme jednu z následujících podmínek: (1) Je-li 𝑓(𝑎0) ∙ 𝑓(𝑥0) < 0, leží kořen v intervalu ⟨𝑎0, 𝑥0⟩ a položíme 𝑎1 = 𝑎0 a 𝑏1 = 𝑥0. Pro tento interval ⟨𝑎1, 𝑏1⟩ postup opakujeme. (2) Je-li 𝑓(𝑥0) ∙ 𝑓(𝑏0) < 0, leží kořen v intervalu ⟨𝑥0, 𝑏0⟩ a položíme 𝑎1 = 𝑥0 a 𝑏1 = 𝑏0. Postup opakujeme pro interval ⟨𝑎1, 𝑏1⟩. (3) Je-li 𝑓(𝑥0) = 0, je 𝑥0 kořenem rovnice. Metoda bisekce je znázorněna na Obrázku 3. Tímto způsobem nám vznikne posloupnost intervalů: ⟨𝑎0, 𝑏0⟩ ⊃ ⟨𝑎1, 𝑏1⟩ … ⊃ ⟨𝑎 𝑛, 𝑏 𝑛⟩ …, kde, jak je uvedeno výše, platí 𝑓(𝑎 𝑛) ∙ 𝑓(𝑏 𝑛) < 0 a 𝑛 ∈ 𝑁0. V půlení pokračujeme tak dlouho, dokud nenarazíme na kořen rovnice 𝑓(𝑥 𝑛) = 0 nebo se dostatečně nepřiblížíme toleranci 𝜀 a to tak, že pro nějaké 𝑘 platí: 𝑏 𝑘 − 𝑎 𝑘 < 2𝜀 Přibližnou hodnotou námi hledaného kořene je střed posledního nalezeného intervalu. 𝑥 𝑘 = 𝑎 𝑘 + 𝑏 𝑘 2 Obrázek 2: Grafy funkcí 𝑓1(𝑥) = 𝑥2 + 1 (zeleně) a 𝑓2(𝑥) = 𝑥5 (modře) 29 Kořen se tak bude nacházet v posledním intervalu a bude se lišit od své přesné hodnoty nejvýše o polovinu své délky |𝑥 𝑘 − 𝜉| < 𝜀. Metoda půlení intervalu je velmi spolehlivá a lze ji použít vždy. Jediným problémem může být špatné určení intervalu, protože nachází-li se v něm více kořenů, nalezneme pouze jeden z nich. Nutno také dodat, že je tato metoda velmi pomalá, a proto se často využívá pouze k zúžení intervalu. Použití je ukázáno na následujícím příkladu. Příklad 13: Metodou bisekce najděte kořen funkce 𝑓(𝑥) = 𝑥5 − 𝑥2 − 1 s přesností 𝜀 = 0,01. Řešení: Tento příklad jsme řešili již výše (Příklad 12) a určili jsme, že kořen se nachází v intervalu 𝐼 ∈ 〈1; 2〉, máme tedy počáteční interval ⟨𝑎0, 𝑏0⟩. Vypočítáme teď střed 𝑥0 tohoto intervalu. 𝑥0 = 𝑎0 + 𝑏0 2 𝑥0 = 1 + 2 2 ⇒ 𝑥0 = 1,5 Poté spočítáme funkční hodnoty v bodech 𝑎0, 𝑏0 a 𝑥0. 𝑓(𝑎0) = −1, 𝑓(𝑏0) = 27, 𝑓(𝑥0) = 4,34375 Teď musíme ověřit, která z podmínek (1) – (3) platí. Z uvedených hodnot vyplývá, že se jedná o podmínku (1) a to 𝑓(𝑎 𝑘) ∙ 𝑓(𝑥 𝑘) < 0. Položíme tedy 𝑎1 = 1 a 𝑏1 = 1,5 a dále počítáme s intervalem 〈1; 1,5〉. Jelikož máme zvolenou přesnost výsledku, musíme zkontrolovat, zda platí podmínka 𝑏 𝑘 − 𝑎 𝑘 < 2𝜀, což po dosazení hodnot zjistíme, že neplatí 1 > 0,02, proto pokračujeme dále. Interval 〈1; 1,5〉 opět rozpůlíme a postupujeme stejným způsobem. Pro přehlednost můžeme řešení vepisovat do tabulky. Jelikož není Obrázek 3: Ukázka metody půlení intervalu 30 určující přesná funkční hodnota v jednotlivých bodech, stačí pro lepší přehled psát pouze znaménka + a −. k 𝑎 𝑘 𝑏 𝑘 𝑥 𝑘 𝑓(𝑎 𝑘) 𝑓(𝑏 𝑘) 𝑓(𝑥 𝑘) 0 1 2 1,5 − + + 1 1 1,5 1,25 − + + 2 1 1,25 1,125 − + − 3 1,125 1,25 1,1875 − + − 4 1,1875 1,25 1,21875 − + + 5 1,1875 1,21875 1,203125 − + + 6 1,1875 1,203125 1,1953125 Tabulka 7: Hledání kořene polynomu 𝑓(𝑥) = 𝑥5 − 𝑥2 − 1 metodou půlení intervalu Takto pokračujeme až 𝑘 = 6, kde už 𝑏6 − 𝑎6 < 2 ∙ 𝜀, tedy 1,203125 − 1,1875 < 0,02. Kořenem je pak 𝑥6 ≐ 1,195. 2.2. Metoda prosté iterace Iterační metody jsou založeny na řešení ekvivalentní úlohy 𝑥 = 𝑔(𝑥). Funkce 𝑔 se nazývá iterační funkce a místo kořenů původní rovnice hledáme pevný bod funkce 𝑔. Definujme tedy, co je to pevný bod. Definice 15: Číslo 𝜉 se nazývá pevný bod funkce 𝑔(𝑥), jestliže platí 𝑔(𝜉) = 𝜉, tj. bod který funkce 𝑔(𝑥) zobrazí sama na sebe. Tento bod je pak řešením rovnice 𝑔(𝑥) = 𝑥. Z definice vyplývá, že pevný bod funkce 𝑦 = 𝑔(𝑥) je průsečíkem grafu funkce s přímkou 𝑦 = 𝑥. Například funkce 𝑓(𝑥) = 2𝑥 − 2 se protne s přímkou 𝑦 = 𝑥 v bodě Obrázek 4: Graf funkcí 𝑓(𝑥) = 2𝑥 − 2 a 𝑔(𝑥) = 𝑥 31 𝜉 = 2 (Obrázek 4), který je tím pádem pevným bodem funkce 𝑦 = 2𝑥 − 2. Platí tedy podmínka 𝑔(𝜉) = 𝜉 a funkční hodnota v bodě 𝜉 = 2 se rovná 2, 𝑓(2) = 2, bod se zobrazí sám na sebe. Iterační metoda však může často divergovat a k pevnému bodu nemusíme vůbec dojít (Obrázek 5, např. pro iterační funkci 𝑔(𝑥) = 5 2 𝑥 − 2 a počáteční bod 𝑥0 = 1,8). Aby tedy iterační funkce 𝑔(𝑥) konvergovala, musí platit Banachova věta o pevném bodě. Věta 21 (Banachova věta o pevném bodě): Nechť 𝑔(𝑥) je funkce na uzavřeném intervalu ⟨𝑎, 𝑏⟩, která: (1) zobrazuje interval ⟨𝑎, 𝑏⟩ do sebe (2) je diferencovatelná12 na intervalu 〈𝑎, 𝑏〉 a splňuje zde pro nějakou reálnou konstantu 𝐿 ∈ (0,1) nerovnost |𝑔′(𝑥)| < 𝐿 Pak má funkce 𝑔(𝑥) na intervalu ⟨𝑎, 𝑏⟩ jediný pevný bod 𝜉. Je-li 𝑥0 libovolný bod intervalu ⟨𝑎, 𝑏⟩ a definujeme-li posloupnost {𝑥 𝑘} 𝑘=0 ∞ vztahem 𝑥 𝑘+1 = 𝑔(𝑥 𝑘), pak tato posloupnost konverguje k pevnému bodu 𝑥∗. Odhad chyby při aproximaci bodu 𝜉 pomocí členů posloupnosti je |𝑥 𝑘+1 − 𝜉| ≤ 𝐿 1 − 𝐿 |𝑥 𝑘+1 − 𝑥 𝑘| (Mařík, 2012a). 12 Diferencovatelná funkce je taková funkce, která má v daném bodě konečnou derivaci (Bárta, Pražák a kol., 2010) Obrázek 5: Příklad divergence iterační funkce 32 Aplikuje-li se Banachova věta 𝑘-krát na funkci 𝑔(𝑥), nazýváme výsledek 𝑘-tá iterace funkce 𝑔. Například 𝑔(𝑔(𝑥)) je druhá iterace funkce 𝑔. Protože nalezení L a ověření podmínky může být někdy obtížné, omezuje se často funkce na určitý počet kroků a z dosažených výsledků se pak určuje konvergence funkce. K zastavení iterace se používá podmínka |𝑥 𝑘+1 − 𝑥 𝑘| < 𝜀, kde 𝜀 je námi zadaná tolerance. Fungování metody prosté iterace si ukážeme na následujícím příkladu. Příklad 14: Metodou prosté iterace najděte kořen funkce 𝑓(𝑥) = 𝑥5 + 𝑥2 − 3 s přesností 𝜀 = 0,01. Řešení: Z grafu funkce 𝑓(𝑥) = 𝑥5 + 𝑥2 − 3 (Obrázek 6) vyplývá, že kořen bude ležet v intervalu 𝐼 ∈ 〈1; 2〉 nebo přesněji 𝐼 ∈ 〈1; 1,2〉. Hledáme proto vhodnou iterační funkci. Možností, jak zvolit iterační funkci je nekonečně mnoho, například: 𝑥5 = 3 − 𝑥2 ⇒ 𝑥 = ±√3 − 𝑥25 𝑥2 = 3 − 𝑥5 ⇒ 𝑥 = ±√3 − 𝑥5 My budeme počítat hned s prvním vztahem, 𝑔(𝑥) = √3 − 𝑥25 . Aby byla zajištěna konvergence funkce, potřebujeme nejdříve ověřit podmínky z Banachovy věty. Začneme podmínkou (2). Funkci 𝑔(𝑥) zderivujeme a hledáme maximum |𝑔′(𝑥)| na intervalu 𝐼 = 〈1; 1,2〉. 𝑔′(𝑥) = 1 5 (−2𝑥) (3 − 𝑥2) 4 5 |𝑔′(𝑥)| = 1 5 2𝑥 (3 − 𝑥2) 4 5 Abychom našli maximum, funkci ještě jednou zderivujeme a položíme ji rovnou nule. Tak najdeme body podezřelé z extrému (stacionární body). |𝑔′′(𝑥)| = 2 ∙ √(3 − 𝑥2)45 + 16𝑥2 5 ∙ √(3 − 𝑥2) 5 5 ∙ √(3 − 𝑥2)95 = 0 Řešením této rovnice jsou komplexní kořeny (𝑥1,2 = ±𝑖√5), proto funkce |𝑔′(𝑥)| nemá lokální extrémy. Na intervalu 𝐼 = 〈1; 1,2〉 je funkce spojitá, tím pádem svého maxima nabývá v jednom z krajích bodů intervalu (Weierstrassova věta13 ). Dosazením krajních bodů do předpisu funkce |𝑔′(𝑥)| a porovnáním těchto funkčních hodnot zjistíme, že je funkce na tomto intervalu rostoucí, tj. hledané maximum se nachází v bodě 𝑥 = 1,2. 13 Nechť funkce 𝑓(𝑥) je spojitá na uzavřeném intervalu 〈𝑎, 𝑏〉. Potom je na tomto intervalu ohraničená a nabývá zde své největší a nejmenší hodnoty, tj. existují čísla 𝑥1, 𝑥2 ∈ 〈𝑎, 𝑏〉 s vlastností 𝑓(𝑥1) ≤ 𝑓(𝑥) ≤ 𝑓(𝑥2), pro všechna 𝑥 ∈ 〈𝑎, 𝑏〉. (Mařík, 2012b) 33 |𝑔′(1)| = 1 5 2 ∙ 1 (3 − 12) 4 5 = 0,2297 < |𝑔′(1,2)| = 1 5 2 ∙ 1,2 (3 − 1,22) 4 5 = 0,3363 Podmínka (2) tak platí např. pro 𝐿 = 0,4. Dále ověříme Podmínku (1). Funkční hodnoty v krajích bodech jsou 𝑔(1) = 1,148698 a dále 𝑔(1,2) = 1,093012. Tedy samotná funkce 𝑔(𝑥) je klesající a krajní hodnoty se zobrazí do intervalu 〈1; 1,2〉, tudíž tato funkce do tohoto intervalu zobrazuje jakoukoli hodnotu z tohoto intervalu. Celkově Banachova věta platí pro funkci g(x) na intervalu 𝐼 = 〈1; 1,2〉 pro jakékoli 𝑥0 ∈ 〈1; 1,2〉. Budeme tedy aproximovat podle předpisu 𝑔(𝑥) = √3 − 𝑥25 a zvolíme 𝑥0 = 1. V dalším kroku dosadíme počáteční aproximaci do předpisu a vypočítáme 𝑥1, 𝑥1 = √3 − 125 ≐ 1,148698355. 𝑥2 = √3 − 1,148698355 5 ⇒ 𝑥2 ≐ 1,109397785 𝑥3 = √3 − 1,10939778525 ⇒ 𝑥3 ≐ 1,120874995 𝑥4 = √3 − 1,12087499525 ⇒ 𝑥3 ≐ 1,117612697 Výpočet již můžeme zastavit, protože je splněna podmínka |𝑥 𝑘 − 𝑥 𝑘−1| < 𝜀, tedy |1,117612697 − 1,120874995| < 0,01. Hledaným kořenem je 𝑥4 ≐ 1,1176. Podíváme-li se se na grafy funkcí 𝑔(𝑥) = √3 − 𝑥25 a 𝑦 = 𝑥 (Obrázek 6), je vidět, že námi nalezený bod 𝑥4 ≐ 1,1176 odpovídá v grafu bodu A, proto se opravdu jedná o pevný bod funkce. Obrázek 6: Graf funkcí 𝑓(𝑥) = 𝑥5 + 𝑥2 − 3, 𝑔(𝑥) = √3 − 𝑥25 a 𝑦 = 𝑥 34 2.3. Newtonova metoda (metoda tečen) Jelikož je mnohdy těžké určit správnou iterační funkci, zavedla se Newtonova metoda, která je speciálním případem iterační metody a pro svoji účelnost se stala jednou z nejrozšířenějších a nejpoužívanějších numerických metod. Definice 16: Nechť 𝑓 je iterační funkce a rovnice 𝑓(𝑥) = 0 má jednoduchý kořen 𝜉, tj. 𝑓′(𝜉) ≠ 0. Pak pro funkci 𝑔(𝑥) = 𝑥 − 𝑓(𝑥) 𝑓′(𝑥) je 𝜉 pevným bodem a iterační metoda určena touto funkcí ve tvaru 𝑥 𝑘+1 = 𝑥 𝑘 − 𝑓(𝑥 𝑘) 𝑓′(𝑥 𝑘) , 𝑓′(𝑥 𝑘) ≠ 0, 𝑘 = 0,1, … se nazývá Newtonova metoda. Newtonovu metodu můžeme rovněž popsat graficky, díky čemuž můžeme tuto metodu nazvat také metodou tečen (Obrázek 7). Nejdříve si zvolíme počáteční aproximaci kořene 𝑥0 a bodem [𝑥0, 𝑓(𝑥0)] vedeme tečnu ke grafu funkce 𝑓. Průsečík dané tečny s osou 𝑥 označíme 𝑥1 a tímto bodem [𝑥1, 𝑓(𝑥1)] opět vedeme tečnu ke grafu funkce 𝑓, čímž vznikne průsečík 𝑥2. Postup opakujeme, dokud není splněna podmínka |𝑥 𝑘 − 𝑥 𝑘−1| < 𝜀. Kořenem 𝜉 je pak bod 𝑥 𝑘−1. Obrázek 7: Newtonova metoda 35 Newtonovu metodu můžeme také odvodit pomocí Taylorova rozvoje (víc níže), který nám zároveň přiblíží, jakým tempem metoda konverguje. 𝑓(𝑥 𝑘+1) = 𝑓(𝑥 𝑘) + 𝑓′(𝑥 𝑘)(𝑥 𝑘+1 − 𝑥 𝑘) + 𝑓′′(𝜉) 2! (𝑥 𝑘+1 − 𝑥 𝑘)2 , kde 𝜉 leží v intervalu od 𝑥 𝑘 do 𝑥 𝑘+1. Ukončíme-li rozvoj po první derivaci dostaneme rovnici 𝑓(𝑥 𝑘+1) ≅ 𝑓(𝑥 𝑘) + 𝑓′(𝑥 𝑘)(𝑥 𝑘+1 − 𝑥 𝑘) V průsečíku s osou 𝑥 se bude 𝑓(𝑥 𝑘+1) = 0, rovnici tak přepíšeme a následně upravíme do již známého tvaru: 𝑓(𝑥 𝑘) + 𝑓′(𝑥 𝑘)(𝑥 𝑘+1 − 𝑥 𝑘) = 0 𝑥 𝑘+1 = 𝑥 𝑘 − 𝑓(𝑥 𝑘) 𝑓′(𝑥 𝑘) . Taylorův rozvoj může být rovněž použit pro odhad chyby 𝑘-té aproximace kořene získaného Newtonovou metodou. Věta 22: Nechť 𝑥 𝑘 ∈ 𝐼 ∧ 𝜉 ∈ 𝐼 a funkce 𝑓(𝑥) má na tomto intervalu 𝐼 druhou derivaci, pak (1) | 𝜉 − 𝑥 𝑘| ≤ 𝑀 2𝑚 (𝑥 𝑘 − 𝑥 𝑘−1)2 (2) | 𝜉 − 𝑥 𝑘| ≤ 𝑀 2𝑚 (𝜉 − 𝑥 𝑘−1)2 , kde 𝑀 = max |𝑓′′(𝑥)| a 𝑚 = min |𝑓′(𝑥)| pro 𝑥 ∈ 𝐼. Stejně jako iterační metody i Newtonova metoda nemusí vždy konvergovat. Většinou je to zapříčiněno špatnou volbou počáteční aproximace 𝑥0. Uveďme tedy podmínky, které zajišťují konvergenci metody. Věta 23 (Fourierova podmínka): Nechť má rovnice 𝑓(𝑥) = 0 v intervalu 〈𝑎, 𝑏〉 jediný reálný kořen a nechť 𝑓′ , 𝑓′′ mají spojité derivace, které na intervalu 〈𝑎, 𝑏〉 nemění znaménko, přičemž 𝑓′(𝑥) ≠ 0, ∀𝑥 ∈ 〈𝑎, 𝑏〉. Počáteční aproximace 𝑥0 je tedy ten z krajních bodů 𝑎, 𝑏, ve kterém je znaménko funkce stejné jako znaménko 𝑓′′ na intervalu 〈𝑎, 𝑏〉. Newtonova metoda pak bude konvergovat. Příklad 15: Newtonovou metodou najděte kořen funkce 𝑓(𝑥) = 𝑥5 − 𝑥2 − 1 s přesností 𝜀 = 0,01. 36 Řešení: Již víme, že kořen funkce bude ležet v intervalu 𝐼 ∈ 〈1,2〉 (Příklad 12). Teď je třeba správně zvolit počáteční aproximaci 𝑥0. Ověříme tedy Fourierovu podmínku (Věta 23). Nejdříve určíme, jaká jsou znaménka v krajních bodech intervalu. 𝑓(1) = 15 − 12 − 1 ⇒ 𝑓(1) = −1 𝑓(2) = 25 − 22 − 1 ⇒ 𝑓(2) = 27 Dále potřebujeme znaménka porovnat s druhou derivací funkce 𝑓(𝑥), proto funkci dvakrát zderivujeme. 𝑓′(𝑥) = 5𝑥4 − 2𝑥 𝑓′′(𝑥) = 20𝑥3 − 2 Následně opět dosadíme krajní body intervalu a porovnáme získaná znaménka. 𝑓′′(1) = 20 ∙ 13 − 2 ⇒ 𝑓′′(1) = 18 𝑓′′(2) = 20 ∙ 23 − 2 ⇒ 𝑓′′(2) = 158 Za počáteční aproximaci 𝑥0 zvolíme bod 𝑥 = 2, protože znaménka jsou v obou případech kladná a funkce je na intervalu 𝐼 ∈ 〈1,2〉 konvexní. Nyní již můžeme začít počítat, předpis tedy vypadá (Definice 16). 𝑥 𝑘+1 = 𝑥 𝑘 − 𝑥 𝑘 5 − 𝑥 𝑘 2 − 1 5𝑥 𝑘 4 − 2𝑥 𝑘 Dosadíme první aproximaci 𝑥0 = 2 a pak pokračujeme, dokud není splněna podmínka |𝑥 𝑘 − 𝑥 𝑘−1| < 𝜀. 𝑥1 = 2 − 25 − 22 − 1 5 ∙ 24 − 2 ∙ 2 ⇒ 𝑥1 ≐ 1,644737 𝑥2 = 1,645 − 1,6447375 − 1,6447372 − 1 5 ∙ 1,6447374 − 2 ∙ 1,644737 ⇒ 𝑥2 ≐ 1,394561 𝑥3 = 1,395 − 1,3945615 − 1,3945612 − 1 5 ∙ 1,3945614 − 2 ∙ 1,394561 ⇒ 𝑥3 ≐ 1,250053 𝑥4 = 1,250 − 1,2500535 − 1,2500532 − 1 5 ∙ 1,2500534 − 2 ∙ 1,250053 ⇒ 𝑥4 ≐ 1,199608 𝑥5 = 1,2 − 1,1996085 − 1,1996082 − 1 5 ∙ 1,1996084 − 2 ∙ 1,199608 ⇒ 𝑥5 ≐ 1,193926 Jelikož |1,199608 − 1,193926| < 0,01 kořenem je 𝑥5 ≐ 1,1939. Newtonovu metodu můžeme rovněž použít pro výpočet rovnic s komplexními kořeny 𝑓(𝑧) = 0. Je však nutné zvolit počáteční aproximaci 𝑧0 komplexní, abychom došli ke komplexnímu kořenu. K jakému kořenu dojdeme, záleží na počáteční aproximaci 𝑧0. Obarvením komplexní roviny podle zadané počáteční aproximace (toutéž barvou 37 obarvíme ty, jež vedou k nalezení stejného kořene) se vytvoří fraktál14 (Obrázek 8 a 9 (Tišnovský, 2006)). Na konci první kapitoly byl zmíněn příklad (Příklad 10), jež jsme s dosavadní znalostí metod nedokázali vypočítat. Teď však by nalezení jeho kořenů neměl být problém. Příklad 17: Nalezněte kořeny polynomu 𝑓(𝑥) = 𝑥6 + 𝑥5 + 4𝑥4 + 3𝑥3 + 5𝑥2 + 2𝑥 + 2 s přesností 𝜀 = 0,01. Řešení: Již víme, že tento polynom nemá žádné racionální kořeny, takže se bude jednat buďto o kořeny iracionální nebo komplexní. Předpokládejme, že námi hledaný kořen je komplexní číslo, použijeme proto Newtonovu metodu. Nejdříve polynom zderivujeme. 𝑓′(𝑥) = 6𝑥5 + 5𝑥4 + 16𝑥3 + 9𝑥2 + 10𝑥 + 2 Předpis pro 𝑘-tou aproximaci vypadá: 𝑥 𝑘+1 = 𝑥 𝑘 − 𝑥 𝑘 6 + 𝑥 𝑘 5 + 4𝑥 𝑘 4 + 3𝑥 𝑘 3 + 5𝑥 𝑘 2 + 2𝑥 𝑘 + 2 6𝑥 𝑘 5 + 5𝑥 𝑘 4 + 16𝑥 𝑘 3 + 9𝑥 𝑘 2 + 10𝑥 𝑘 + 2 Dále určíme počáteční aproximaci 𝑥0 = 1 + 𝑖. Další aproximace jsou tedy: 𝑥1 = 1 + 𝑖 − (1 + 𝑖)6 + (1 + 𝑖)5 + 4(1 + 𝑖)4 + 3(1 + 𝑖)3 + 5(1 + 𝑖)2 + 2(1 + 𝑖) + 2 6(1 + 𝑖)5 + 5(1 + 𝑖)4 + 16(1 + 𝑖)3 + 9(1 + 𝑖)2 + 10(1 + 𝑖) + 2 𝑥1 = 0,698813 + 0,924332𝑖 𝑥2 = 0,435852 + 0,892621𝑖 𝑥3 = 0,219409 + 0,905221𝑖 𝑥4 = 0,071556 + 0,948134𝑖 14 Fraktál je geometrický útvar, ve kterém se stále opakuje určitý motiv či tvar. Obrázek 8: Newtonova fraktální množina polynomu 𝑧3 − 1 = 0 Obrázek 9: Newtonova fraktální množina polynomu 𝑧8 − 1 = 0 38 𝑥5 = 0,00809 + 0,987446𝑖 𝑥6 = −0,00008 + 0,99549𝑖 Zde zastavíme výpočet, protože |𝑥6 − 𝑥5| < 0,01, tudíž kořenem je 𝑥 ≐ 𝑖. Protože komplexní kořeny jsou vždy komplexně sdružená čísla, je zřejmé, že druhý kořen se bude rovnat 𝑥2 = −𝑖. Další kořeny je možné najít různými způsoby. Můžeme například opět použít Newtonovu metodu, avšak pro jinou počáteční aproximaci. Například při zadání 𝑥0 = 1 + √2𝑖 dostaneme, že dalšími kořeny jsou opět komplexně sdružená čísla 𝑥3,4 = ±√2𝑖. Poté opět můžeme pokračovat Newtonovou metodou nebo vydělíme polynom 𝑓(𝑥) výše vypočítanými kořeny a dostaneme: (𝑥6 + 𝑥5 + 4𝑥4 + 3𝑥3 + 5𝑥2 + 2𝑥 + 2) ÷ [(𝑥2 + 1) ∙ (𝑥2 + 2)] = 𝑥2 + 𝑥 + 1 Tento polynom stupně 2 již lehce spočítáme pomocí vzorce pro výpočet kořenů kvadratické rovnice. 𝑥5,6 = −1 ± √1 − 4 ∙ 1 ∙ 1 2 ∙ 1 ⇒ 𝑥5 = − 1 2 + 𝑖 ∙ √3 2 ; 𝑥6 = − 1 2 − 𝑖 ∙ √3 2 S pomocí numerických metod tedy dokážeme vypočítat kořeny jakéhokoli polynomu. 39 3. PROGRAMY A VÝSLEDKY Pro programování numerických metod existuje několik možností, jako je například MATLAB, jazyk S či jazyk R. MATLAB® je programovací prostředí určeno většinou pro akademickou sféru, programuje se v něm ve stejnojmenném jazyce MATLAB. Tento název vznikl zkrácením slov matrix laboratory („maticová laboratoř“) a je založen na maticích. MATLAB tak dokáže počítat s maticemi, vykreslit 2D či 3D grafy funkcí, vytvořit počítačovou simulaci, analyzovat a interpretovat data či vytvářet nové aplikace. Nejdříve byl využíván pouze pro matematické výpočty, dnes je však rozšířeným jazykem, který se uplatňuje v mnoha sférách. Naproti tomu je jazyk S statistický jazyk. Byl vyvinut v Bellových laboratořích Johnem Chambersem v roce 1976 (Becker, 1994). Jazyk S je i přes několik svých aktualizací dnes již zastaralý a málo používaný. Vyvinul se z něj však jazyk R, jež je určený zejména pro analýzu dat a jejich grafické vykreslení. V základní sestavě obsahuje mnoho statistických funkcí, ale může být použit i k řešení systému lineárních rovnic, maticových výpočtů či psaní vlastních funkcí a skriptů. Vidíme, že jazyk R a MATLAB jsou si v mnoha ohledech podobné, avšak na rozdíl od MATLABu je jazyk R volně dostupný, a proto byl použit pro tuto bakalářskou práci. Programy jsou psány v aplikaci RStudio, jež slouží jako grafické vývojové prostředí pro jazyk R. 3.1. Představení programů V následujících podkapitolách jsou popsány programy pro výpočet numerických metod uvedených v Kapitole 2. Jedná se o programy: „Půlení intervalu“, „Metoda prosté iterace“, „Newtonova metoda pro reálné kořeny“ a „Newtonova metoda pro komplexní kořeny“. Kódy všech programů jsou vloženy do příloh. 3.1.1. Metoda půlení intervalu Kód pro tuto metodu se skládá z několika částí. Ve funkci polynom_vzor (Obrázek 10) je vložen ukázkový polynom. Ten je zde jako příklad pro uživatele, který se seznamuje s fungováním programu. Jeho definování přímo ve zdrojovém kódu programu usnadňuje volání funkce, protože stačí zadat požadovaný interval (stačí do konzole napsat například puleni (1, 2) a program provede půlení vzorového polynomu v intervalu 𝐼 = 〈1,2〉). 40 Obrázek 10: Kód vzorového polynomu Následuje funkce puleni, která implementuje algoritmus metody půlení intervalu. Při zadávaní je možno využít vzorového polynomu, nebo zadat svůj vlastní. Ten zadáváme například ve tvaru: puleni (-2, 0, polynom = x ^ 3 + x - 1). Metodu rovněž můžeme ohraničit na určitý počet kroků (Obrázek 11 a 12), při nastavení i_max = 0, je počet kroků zanedbán a program skončí, až dosáhne zadané (či předdefinované) přesnosti 𝜀 (v programu označeno jako e). Obrázek 11: Zastavení průběhu metody půlení intervalu po určitém počtu kroků a ignorování kroků při nastavení i_max=0 Obrázek 12: Půlení intervalu, příklad na omezený počet kroků Funkce pak kontroluje několik podmínek, než dojde k samotnému půlení. Nejdříve zkontroluje, zdali je interval zadán vzestupně, není-li tomu tak, hodnoty v intervalech vymění (Obrázek 13 a 14). Dále ověřuje, zdali se v intervalu nachází kořen daného polynomu (Obrázek 15 a 16) a také, zda není jeden z krajních bodů kořenem polynomu (Obrázek 17 a 18). Obrázek 13: Kontrola vzestupnosti krajních bodů v intervalu 41 Obrázek 14: Ukázka kontroly a úprava intervalu pro polynom 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 Obrázek 15: Kontrola, zdali je kořen polynomu v daném intervalu Obrázek 16: Kontrola, zda se v intervalu 𝐼 = 〈1,2〉 polynomu 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 nachází kořen Obrázek 17: Kontrola, zda je krajní bod intervalu kořenem polynomu Obrázek 18: Polynom 𝑓(𝑥) = 𝑥3 + 2𝑥2 − 𝑥 − 2 má v krajním bodě 𝑥 = 1 intervalu 𝐼 = 〈0, 1〉 kořen Poté už program provede algoritmus půlení (Obrázek 19 a 20). Ten je realizován cyklem while a provádí půlení, dokud není dosaženo přesnosti 𝜀 nebo určeného počtu kroků, jak je zmíněno výše. Program je také ukončen, když je kořen nalezen přesně, tj. jeho funkční hodnota je rovná nule. To se stává pouze ve výjimečných případech, programy totiž mají problém vypočítat absolutní nulu. Jedním z příkladu, kdy se tato podmínka využívá, je při hledání kořenů polynomů nalezených hned po jednom aproximačním kroku (např. u polynomu 𝑓(𝑥) = 2𝑥 v intervalu 𝐼 = 〈−1,1〉). V těchto případech není dosaženo zadané přesnosti 𝜀 ani počtu kroků (pokud není nastaveno i_max =1). 42 Obrázek 19: Algoritmus půlení 1. část Obrázek 20: Algoritmus půlení 2. část Hodnoty jsou poté vypsány, jak přímo v konzoli, tak i v samostatném souboru pomocí funkce write (Obrázek 21 a 22). Vypisování do souboru poskytuje lepší přehled a umožňuje pracovat s výsledky i po opuštění konzole. Obrázek 21: Funkce write - 1.část Obrázek 22: Funkce write - 2.část Jelikož je soubor ukládán s koncovkou .csv, který je kompatibilní například i s aplikací Excel od firmy Microsoft, bylo nutné přidat do programu ještě funkci n2s (number to string) (Obrázek 23), protože jazyk R odděluje desetinná čísla pomocí tečky a ne čárky, jak je zvykem v České republice. Čísla se tak mnohdy převáděla automaticky na data (1.5 → 1. května). Obrázek 23: Funkce n2s 43 3.1.2. Metoda prosté iterace Stejně jako pro metodu půlení intervalu, tak také v programu pro metodu prosté iterace je uveden vzorový polynom (Obrázek 24), kde je však již vepsána iterační funkce k danému polynomu 𝑓(𝑥) = 𝑥3 + 𝑥 − 1. Obrázek 24: Kód vzorové iterační funkce Jelikož jsou podmínky pro ověřování správnosti intervalu pro tuto metodu docela složité a vyžadovaly by mnoho vstupů od uživatele, nejsou v programu ověřovány. Důležité pro tuto metodu je tedy určení maximálního počtu kroků (Obrázek 11), po kterém se program zastaví a uživatel může z dosažených výsledků rozhodnout, zdali posloupnost aproximací diverguje (Obrázek 25) či konverguje (Obrázek 26). V programu je taktéž možné počítat bez určeného počtu kroků, při nastavení i_max = 0, v takovémto případě by si měl být uživatel jistý, že funkce je konvergentní, jinak se program zacyklí. Obrázek 25: Ukázka divergence posloupnosti aproximací funkce 𝑔(𝑥) = √1 − 𝑥 při zadání 𝑥0 = 0 Obrázek 26: Ukázka konvergence posloupnosti aproximací funkce 𝑔(𝑥) = √1 − 𝑥 při zadání 𝑥0 = 0,5 Aproximace kořene je prováděna opět pomocí cyklu while ve funkci iterace, ve které na rozdíl od puleni zadáváme přímo počáteční aproximaci 𝑥0. Jelikož program nepodporuje odmocniny ze záporných hodnot, je metoda prosté iterace určena pouze pro reálné kořeny (Obrázek 27). 44 Obrázek 27: Ukázka, jak se metoda chová při zadání 𝑥0 = 2, kdy jako další aproximace vychází komplexní číslo Výsledky jsou stejně jako u předchozí metody vypsány do konzole i uloženy do souboru pomocí funkce write. 3.1.3. Newtonova metoda Pro Newtonovu metodu jsou vytvořeny dva programy, pro reálné a komplexní kořeny. Program „Newtonova metoda pro reálné kořeny“ má podobné prvky jako předchozí programy. Jak i ostatní, i tento umožňuje počítat se vzorovým polynomem (Obrázek 10) a rovněž ověřuje některé podmínky: zdali je interval zadán vzestupně (Obrázek 13 a 14), zdali je interval zadán správně (Obrázek 15 a 16) a jestli nejsou krajní hodnoty kořeny polynomu (Obrázek 17 a 18). Princip metody je popsán ve funkci prubeh. Potřebná derivace se počítá automaticky pomocí funkce D (vyjma případu, kdy se jedná o vzorový polynom, zde je již derivace zadána) (Obrázek 28). Zadaný polynom však musí obsahovat proměnnou x, protože funkce D derivuje právě podle této proměnné. Obrázek 28: Derivace polynomu Tělo programu opět tvoří cyklus while, a abychom nemuseli rozlišovat, zda se jedná o funkci rostoucí nebo klesající, převede program funkci automaticky na funkci rostoucí (Obrázek 29) a poté zahájí cyklus. 45 Obrázek 29: Převedení na rostoucí funkci Pro ukončení programu je možno využít požadované přesnosti 𝜀 (je na uživateli, zda se rozhodne využít předdefinovanou přesnost 𝜀 = 0,001 nebo svou vlastní) či metodu ohraničit na určitý počet kroků (automaticky je nastaveno i_max = 1000). Hodnoty se jako i u předchozích programů vypisují přímo do konzole a také do souboru Newton_tabulka.csv. Program „Newtonova metoda pro komplexní kořeny“ je téměř totožný jako pro kořeny reálné, jsou zde však vynechány ověřovací podmínky, protože v komplexní rovině budeme těžko uvažovat interval, na němž bychom podmínky ověřovali. Do programu tedy zadáváme přímo počáteční aproximaci 𝑥0. 3.2. Porovnání programů a příklady Cílem této podkapitoly je porovnat vlastnosti jednotlivých programů (a tím pádem i jimi určených numerických metod). Pozor bude věnován rychlosti metod (kolik je potřeba na určení kořene kroků), zdali se metody ve výsledcích shodují, popřípadě jak se liší od „skutečného kořene“ (lze zkoumat, jedná-li se o racionální kořeny) a jak se s metodou pracuje (je těžké najít interval či počáteční aproximaci či nikoli). Příklad 18: Určete kořen polynomu 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 s přesností 𝜀 = 0,001. Diskuze: Pro programy „Metoda půlení intervalu“ a „Newtonova metoda“ byl kořen počítán v intervalu 𝐼 = 〈0, 1〉, pro program „Metoda prosté iterace“ bylo nutné nejdříve zvolit vhodnou iterační funkci a k ní počáteční aproximaci. Jako iterační funkce byla zvolena 𝑔(𝑥) = √1 − 𝑥 3 s počáteční aproximací 𝑥0 = 0,5. Metoda prosté iterace vypočítala příklad v devatenácti krocích, 𝑥19 = 0,682626670619523, metoda půlení intervalu došla k výsledku v devíti krocích 𝑥9 = 0,6826171875 a Newtonově metodě stačily na výpočet čtyři kroky 𝑥4 = 0,682327803946513. Přehled jednotlivých intervalů a kořenů je ukázán v následující tabulce. 46 Polynom 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 Interval nebo poč. aproximace Počet kroků Kořen Metoda půlení intervalu 𝐼 = 〈0, 1〉 9 0,6826171875 Metoda prosté iterace 𝑥0 = 0,5 19 0,682626670619523 𝑥0 = 0,6 16 Newtonova metoda 𝐼 = 〈0, 1〉 4 0,682327803946513 𝑥0 = 𝑖 5 −0,341164 + 1,161541i 𝑥0 = −𝑖 5 −0,341164 − 1,161541i Tabulka 8: Kořeny polynomu 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 Polynom 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 nemá racionální kořeny, proto nelze uvažovat odchylku od „skutečného“ řešení. Je však vidět, že metody se s výsledkem shodují. Nejpomalejší a také nejpracnější byla metoda prosté iterace. I přes to, že upravíme počáteční aproximaci na 𝑥0 = 0,6 metoda stále potřebuje na výpočet kořene šestnáct kroků, což ji i v tomhle případě činí nejpomalejší. K výpočtu dalších kořenů můžeme využít pouze program „Newtonova metoda pro komplexní kořeny“, protože se jedná o komplexní kořeny. S počáteční aproximací 𝑥0 = 𝑖 dospějeme ke kořenu v pátém kroku 𝑥5 = −0,341164 + 1,161541i, posledním kořenem tedy bude k němu komplexně sdružené číslo 𝑥5̅̅̅ = −0,341164 − 1,161541i, ke kterému v metodě dojdeme opět po pěti krocích při zadání 𝑥0 = −𝑖. Příklad 19: Určete kořen polynomu 𝑓(𝑥) = 𝑥5 − 𝑥3 + 𝑥 − 2 s přesností 𝜀 = 0,001. Diskuze: Pro metodu půlení intervalu a Newtonovu metodu budeme počítat v intervalu 𝐼 = 〈1,2〉, pro metodu prosté iterace je zvolena iterační funkce 𝑔(𝑥) = √𝑥3 − 𝑥 + 2 5 a počáteční aproximace 𝑥0 = 0,5. V tomto příkladě metoda prosté iterace fungovala rychleji a v počtu kroků si může podat ruce s Newtonovu metodou. Půlení intervalu je zde zdlouhavější. Je zajímavé si povšimnout, že při zvětšení intervalu 𝐼 = 〈−10, 10〉 se počet kroků Newtonovy metody zvětší na 13 a půlení intervalu na 14, při ještě větším rozpětí 𝐼 = 〈−20, 20〉 metoda půlení intervalu předběhne Newtonovu metodu o jeden krok, půlení má 15 kroků, Newtonova metoda 16. Naopak při zmenšení intervalu 𝐼 = 〈1; 1,3〉 dospěje Newtonova metoda k výsledku za 3 kroky a půlení intervalu za 8. Iterační metoda při zmenšení intervalu dospěje k výsledku v 5 krocích. I v tomto případě je však docela obtížné najít iterační 47 funkci a zbylé kořeny je možno opět dopočítat pouze Newtonovou metodou, protože se jedná o kořeny komplexní. Polynom 𝑓(𝑥) = 𝑥5 − 𝑥3 + 𝑥 − 2 Interval nebo poč. aproximace Počet kroků Kořen Metoda půlení intervalu 𝐼 = 〈1, 2〉 9 1,206055 𝐼 = 〈1; 1,3〉 8 𝐼 = 〈−10, 10〉 14 𝐼 = 〈−20, 20〉 15 Metoda prosté iterace 𝑥0 = 0,5 6 1,20526034969988 𝑥0 = 1 5 Newtonova metoda 𝐼 = 〈1, 2〉 6 1,205569 𝐼 = 〈1; 1,3〉 3 𝐼 = 〈−10, 10〉 13 𝐼 = 〈−20, 20〉 16 𝑥0 = 𝑖 7 0,5 + 0,8660254i 𝑥0 = −𝑖 7 0,5 − 0,8660254i 𝑥0 = −1 + 𝑖 5 −1,102785 + 0,665457𝑖 𝑥0 = −1 − 𝑖 5 −1,102785 − 0,665457𝑖 Tabulka 9: Kořeny polynomu 𝑓(𝑥) = 𝑥5 − 𝑥3 + 𝑥 − 2 Příklad 20: Určete všechny kořeny polynomu 𝑓(𝑥) = 2𝑥4 − 11𝑥2 + 5. Diskuze: Tento polynom má všechny kořeny reálné a racionální, proto se budeme snažit určit jejich přesnou hodnotu. Z grafu (Obrázek 30) i vzorce je vidět, že funkce je sudá, bude tedy stačit najít pouze dva kořeny a zbylé dva se budou lišit pouze o znaménko. Nejdříve budeme počítat v intervalu 𝐼 = 〈0,5; 1〉, pro Newtonovu metodu a metodu půlení intervalu. Pro Newtonovu metodu totiž nemůžeme stanovit interval 𝐼 = 〈0, 1〉, protože pak bychom ve výpočtu dělili nulou15 , což nelze. Pro metodu prosté iterace budeme počítat s iterační funkci 𝑔(𝑥) = √ 2𝑥4+5 11 a počáteční aproximaci 15 Z grafu funkce je zřejmé, že daná funkce bude na intervalu klesat, proto jako počáteční aproximaci volíme číslo 0, 𝑥0 = 0. Dosadíme-li do předpisu Newtonovy metody pro tento polynom, jistíme, že rovnice nemá řešení. 𝑥 𝑘+1 = 𝑥 𝑘 − 2𝑥 𝑘 4 − 11𝑥 𝑘 2 + 5 8𝑥 𝑘 3 − 22𝑥 𝑘 𝑥1 = 0 − 2 ∙ 0 − 11 ∙ 0 + 5 8 ∙ 0 − 22 ∙ 0 48 𝑥0 = 0,5. V tomto případě chceme dojít k přesnému výsledku, proto jsme nastavili 𝜀 = 0,000000001. Nemůžeme však nastavit 𝜀 = 0, protože programy mají problém nalézt absolutní nulu a mnohdy se mohou i zacyklit. Výpočty pro druhý kořen jsou uvedeny v tabulce, pro metodu prosté iterace však musela být zvolena jiná iterační funkce 𝑔(𝑥) = √ 11𝑥2−5 2 4 . Polynom 𝑓(𝑥) = 𝑥5 − 𝑥3 + 𝑥 − 2 Interval nebo poč. aproximace Počet kroků Výsledek Metoda půlení intervalu 𝐼 = 〈0,5; 1〉 22 0,7071068 𝐼 = 〈1; 3〉 24 2,236068 Metoda prosté iterace 𝑥0 = 0,5 10 0,7071068 𝑥0 = 1 29 2,236068 Newtonova metoda 𝐼 = 〈0,5; 1〉 4 0,7071068 𝐼 = 〈1; 3〉 6 2,236068 Tabulka 10: Kořeny polynomu 𝑓(𝑥) = 𝑥5 − 𝑥3 + 𝑥 − 2 Všechny kořeny daného polynomu budou tedy 𝑥1 = 0,7071068, 𝑥2 = −0,7071068, 𝑥3 = 2,236068, 𝑥4 = −2,236068. Příklad 21: Určete kořeny polynomu 𝑓(𝑥) = 𝑥4 + 3𝑥3 + 4𝑥2 + 3𝑥 + 1. Obrázek 30: Graf funkce 𝑓(𝑥) = 2𝑥4 − 11𝑥2 + 5 49 Diskuze: Z Obrázku 32 je vidět, že nikdy graf funkce neprotne osu x a tím pádem není splněna podmínka 𝑓(𝑎) ∙ 𝑓(𝑏) < 0; ∀𝑎, 𝑏 ∈ ℝ, která je pro programy numerických metod klíčová. Nemůže zde tedy použít programy „Metodu půlení intervalu“ a ani „Newtonova metoda pro reálné kořeny“, protože nesplnění podmínky programy zastaví. Je tak učiněno z důvodu, že uživatel může mnohdy špatně určit interval a program by se pokaždé zacyklil. Můžeme však využít program „Newtonova metoda pro komplexní kořeny“, který tuto podmínku neobsahuje a rovnou počítá se zadanou počáteční aproximací. Polynom 𝑓(𝑥) = 𝑥4 + 3𝑥3 + 4𝑥2 + 3𝑥 + 1 Poč. aproximace Počet kroků Výsledek Newtonova metoda 𝑥0 = 0 15 −1,000081 𝑥0 = 𝑖 7 −0,5 + 0,8660254𝑖 𝑥0 = −𝑖 7 −0,5 − 0,8660254𝑖 Tabulka 11: Kořeny polynomu 𝑓(𝑥) = 𝑥4 + 3𝑥3 + 4𝑥2 + 3𝑥 + 1 Na příklad by šlo však nahlížet i jiným způsobem. Víme, že tento polynom obsahuje buď komplexní nebo násobné kořeny. S násobností kořenů by si poradily metody popsané v Kapitole 1, např. Hornerovo schéma nebo by bylo možné použít Větu 17 a vydělit polynom 𝑁𝑆𝐷(𝑓, 𝑓′). V našem případě 𝑁𝑆𝐷(𝑓, 𝑓′) = (𝑥 + 1), polynom proto můžeme rozložit na součin 𝑓(𝑥) = (𝑥3 + 2𝑥2 + 2𝑥 + 1)(𝑥 + 1) a graf 𝑓2(𝑥) = 𝑥3 + 2𝑥2 + 2𝑥 + 1 už protíná osu x. Pro tento polynom již můžeme využít numerických metod. Počítání však můžeme ještě zjednodušit, jelikož z předchozího řešení je zřejmé, že polynom obsahuje dvojnásobný kořen 𝑥 = −1, polynom 𝑓2(𝑥) tak lze vydělit ještě jednou výrazem (𝑥 + 1) a rozložit tak na 𝑓(𝑥) = (𝑥2 + 𝑥 + 1)(𝑥 + 1)2 . Obrázek 31: Graf funkce 𝑓(𝑥) = 𝑥4 + 3𝑥3 + 4𝑥2 + 3𝑥 + 1 50 Z toho rozkladu je zřejmé, že 𝑓3(𝑥) = 𝑥2 + 𝑥 + 1 má komplexní kořeny, které poté dokážeme určit Newtonovou metodou. Výsledkem budou komplexně sdružené kořeny 𝑥3,4 = −0,5 ± 0,8660254𝑖. Příklad 22: Najděte kořeny polynomu 𝑓(𝑥) = 147𝑥4 + 84𝑥3 − 40𝑥2 − 28𝑥 − 3. Diskuze: Zkusíme hledat kořeny v intervalech 𝐼 = 〈−1, 0〉 a 𝐼 = 〈0, 1〉 pro Newtonovu metodu a metodu půlení intervalu. Pro metodu prosté iterace budeme počítat s iterační funkcí 𝑔(𝑥) = √ −84𝑥3+40𝑥2+28𝑥+3 147 4 a počáteční aproximací 𝑥0 = 0. Polynom 𝑓(𝑥) = 147𝑥4 + 84𝑥3 − 40𝑥2 − 28𝑥 − 3 Interval nebo poč. aproximace Počet kroků Kořen Metoda půlení intervalu 𝐼 = 〈−1, 0〉 22 −0,5773503 𝐼 = 〈−0,8; 0〉 22 −0,1428571 𝐼 = 〈0, 1〉 22 0,5773503 Metoda prosté iterace 𝑥0 = 0 7 0,5773503 Newtonova metoda 𝐼 = 〈−1, 0〉 7 −0,5773503 𝐼 = 〈−0,8; 0〉 5 −0,5773503 𝐼 = 〈0, 1〉 6 0,5773503 Tabulka 12: Kořeny polynomu 𝑓(𝑥) = 147𝑥4 + 84𝑥3 − 40𝑥2 − 28𝑥 − 3 Z výpočtu je zřejmé, že v intervalu 𝐼 = 〈−1, 0〉 leží více kořenů, protože zúžením intervalu nalezneme pro metodu půlení intervalu vždy jiný kořen. Naopak zužováním či zvětšováním intervalu u Newtonovy metody dostaneme vždy stejný kořen. Správné intervaly, v kterých bychom měli kořeny hledat jsou tedy 𝐼1 = 〈−1; −0,5〉, 𝐼2 = 〈−0,5; −0,35〉, 𝐼3 = 〈−0,35; 0〉. Hodnoty intervalu musíme volit právě tímto způsobem, protože Newtonova metoda při zadání některých intervalů (např. 𝐼 = 〈−0,5; −0,3〉) najde kořen úplně mimo daný interval (např 𝑥 = 0,5773503). Níže je upravená tabulka pro metodu půlení intervalu a Newtonovu metodu. 51 Polynom 𝑓(𝑥) = 147𝑥4 + 84𝑥3 − 40𝑥2 − 28𝑥 − 3 Interval Počet kroků Kořen Metoda půlení intervalu 𝐼1 = 〈−1; −0,5〉 21 −0,5773503 𝐼2 = 〈−0,5; −0,35〉 18 −0,4285714 𝐼3 = 〈−0,35; 0〉 18 −0,1428571 𝐼4 = 〈0, 1〉 22 0,5773503 Newtonova metoda 𝐼1 = 〈−1; −0,5〉 7 −0,5773503 𝐼2 = 〈−0,5; −0,35〉 4 −0,4285714 𝐼3 = 〈−0,35; 0〉 4 −0,1428571 𝐼4 = 〈0, 1〉 6 0,5773503 Tabulka 13: Kořeny polynomu 𝑓(𝑥) = 147𝑥4 + 84𝑥3 − 40𝑥2 − 28𝑥 − 3 3.3. Shrnutí a doporučení Z výše uvedených příkladů můžeme vyvodit některé vlastnosti jednotlivých numerických metod. Nejrychlejší metodou (metodou s nejmenším počtem kroků) byla skoro ve všech případech Newtonova metoda. Její účinnost však docela rapidně klesala se zvětšujícím se intervalem. Také je nutno dodat, že v Příkladě 20 a 22 byl problém najít interval, ve kterém bychom mohli kořen hledat, protože pro některé intervaly nebyla splněna Fourierova podmínka a v intervalu 𝐼 = 〈−0,5; 0,5〉 počítala metoda „špatné“ kořeny. Např. pro 𝐼 = 〈0,1; 1〉 našla kořen 𝑥 = 2,236068, který do toho intervalu vůbec nepatří a podobně. U Newtonovy metody je proto důležité dbát na správný výběr intervalu. Co však staví Newtonovu metodu, v tomto případě lépe řečeno program „Newtonova metoda pro komplexní kořeny“, před všechny ostatní je výpočet komplexních kořenů. Velkou výhodou metody půlení intervalu bylo její všestranné využití. Bylo možno ji využít vždy, nehledě na vybraný intervalu. Jediným „zádrhelem“ jsou násobné kořeny. Metoda si poradí, i když se v intervalu nachází více kořenů, ale v takovémto případě najde pouze jeden z nich. Každopádně bychom se měli vyhnout počítání více kořenů v jednom intervalu a měli bychom být schopni vždy najít interval, kde je kořen právě jeden. Největší nevýhodou metody je její zdlouhavost. Někdy se oproti ostatním metodám lišila až o 15 kroků (Příklad 22), což by při ručním počítání určitě zabralo nějaký čas. Největší prodleva byla pozorovatelná na velmi malých intervalech, naopak metoda dobře fungovala ve velkých rozpětích intervalu. V Příkladě 19 byla metoda půlení intervalu dokonce rychlejší než Newtonova metoda. 52 Nejvíce nevyváženou metodou ze všech byla metoda prosté iterace. V některých příkladech se v rychlosti rovnala Newtonově metodě (Příklad 19), jindy zaostávala i za metodou půlení intervalu (Příklad 18). Celkově by se však dala zařadit mezi rychlejší metody výpočtu. Největším problémem u této metody bylo určování iteračních funkcí a počátečních aproximací. Někdy jsme funkci našli hned na první pokus, jindy bylo hledání složitější. Značný problém nalezení iteračních funkcí byl v Příkladu 22. To, že Newtonova byla rychlejší a snadnější pro práci se však dalo předpokládat, jelikož Newtonova metoda je speciálním případem iterační metody. Kdybychom chtěli shrnout nejefektivnější řešení polynomických rovnic, určitě bychom začali s nakreslením grafu, který uživateli ledacos napoví a ukáže mu, jaký interval pro výpočet kořenů zvolit. Doporučením, jak si tuto práci usnadnit je grafický kalkulátor Geogebra (Hohenwarter, 2002), který byl v této bakalářské práci použit k ilustrací všech grafů. Jak je zmíněno výše, z grafu se dá ledacos odhadnout. Vidíme-li, že graf neprotíná osu x (Příklad 21) odhadujeme, že kořeny polynomu jsou buďto násobné nebo komplexní. Výše je zmíněno, jakým způsobem se dá takovýto případ vyřešit. Pro snadnější výpočet však můžeme využít volně dostupných programů na webových stránkách. Derivaci je možné vypočítat v programu „Derivace polynomu“ (je přiložen v Přílohách), jehož princip je ekvivalentní s derivací použitou v programu „Newtonova metoda pro reálné kořeny“ a „Newtonova metoda pro komplexní kořeny“ a je rovněž naimplementován v jazyce R. Největší společný dělitel polynomu a jeho derivace pak můžeme být jednoduše spočítán na webové stránce zabývající se online kalkulačkami (Anton, Polynomial Greatest Common Divisor, 2018). Stránka je sice v angličtině, ale velmi dobře zpracována, takže by neměl být problém se na ni správně orientovat. Jediným problémem by mohlo být zadávání polynomu, který je zde vyobrazen jako posloupnost, např. polynom 𝑓(𝑥) = 𝑥3 − 2𝑥2 + 1 bychom zadali jako (1 − 2 0 1). V dalším kroku dělíme polynom největším společným dělitelem polynomu a jeho derivace. K tomu můžeme opět využít volně dostupných programů. Na internetových stránkách jich existuje celá řada, v této bakalářské práci jsou uvedeny dva. Jeden se nachází již na výše zmíněné stránce (Anton, Polynomial division, 2018). Uživatel si může vybrat, chce-li počítat dělení přesně nebo mu stačí pouze zaokrouhlený výsledek. Stránka taktéž zobrazuje všechny kroky dělení, které jsou doprovázeny slovním popisem. Co však tuto online kalkulačku staví nad ostatní je možnost pracovat i s komplexními čísly. 53 Druhu stránkou je (Wolfram Research, 2018), i tato stránka nabízí přehled jednotlivých kroků dělení, a navíc se polynomy zadávají klasicky, ne jako posloupnosti. Dělení komplexními čísly však není možné provést. Zbavíme-li se násobných kořenů, zbývá využít dostupných numerických metod. Nejjednodušší cestou se jeví použití metody půlení intervalu na zúžení intervalu a poté použití Newtonovy metody. Tím by mělo být dosáhnuto výsledku s nejmenším možným počtem kroků. Pro komplexní kořeny zbývá použít pouze Newtonovu metodu (program „Newtonova metoda pro komplexní kořeny“). Kdybychom však chtěli využít znalostí z Kapitoly 1, je možno najít komplexní kořeny i pomocí Hornerova schématu. 54 Závěr Tato bakalářská práce prozkoumala oblast polynomů a k řešení polynomických rovnic popsala tři numerické metody, a to metodu půlení intervalu, metodu prosté iterace a Newtonovu metodu. Tyto metody byly naprogramovány ve volně dostupném jazyce R a fungování jednotlivých částí programů bylo vysvětleno v poslední kapitole. Jakýkoli uživatel by tedy po přečtení této bakalářské práce neměl mít problém s používáním těchto programů. Poslední kapitola také uvádí 5 příkladů (Příklad 18-23), které pomáhají k následnému porovnávání vybraných numerických metod a tím poukazuje na jejich světlé i stinné stránky. V této kapitole jsou rovněž popsány některé volně dostupné webové aplikace, které usnadňují výpočty potřebné k určení správného výsledku. Například je zde uvedena webová stránka Geogebra, která pomáhá určit správný interval, ve kterém leží kořeny dané polynomické rovnice, nebo různé online kalkulačky, které pomáhají řešit problém s násobnými kořeny polynomů, na něž jsou některé numerické metody krátké. Tato bakalářské práce tak může pomoci studentům k lepšímu pochopení látky polynomů a s pomocí programů by si měli poradit s jakoukoli polynomickou rovnicí. Myslím si, že i když jsou polynomy a numerické metody předmětem již mnoha bakalářských či diplomových prací, každá z nich vrhá světlo pouze na kousek problematiky a tím, že každá práce uchopí tuto látku jinak, je stále ještě dost prostoru pro budoucí práce přijít s něčím novým a unikátním. Studentům, kteří by tedy chtěli na tuto bakalářskou práci navázat, bych doporučila pokračovat ve vytvoření programů, které by mohly více objasnit a usnadnit další výpočty. Zejména bych uvítala program na výpočet Hornerova schématu, pomocí kterého je možné řešit některé polynomické rovnice a zejména pro celočíselné kořeny jsou mnohdy lepší volbou než výše zmíněné numerické metody. Velmi užitečné by bylo i naprogramování např. dělení polynomů či Eukleidův algoritmus pro hledání největšího společného dělitele dvou polynomů, aby se student nemusel spoléhat na webové stránky. 55 Bibliografie Anton. (22. prosinec 2018). Polynomial division. Načteno z Online calculators: https://planetcalc.com/7718/ Anton. (22. prosinec 2018). Polynomial greatest common divisor. Načteno z Online calculators: https://planetcalc.com/7760/ Bárta, T., Pražák, D. a kol. (2010) Jednoznačnost a diferencovatelnost řešení. Načteno z Matematicko-fyzikální fakulta Univerzity Karlova: http://www.karlin.mff.cuni.cz/~barta/pcODR/Kapitola- JednDiferenc/JednoznDifferenc.pdf Becker, R. A. (1994). A Brief History of S. AT&T Bell Laboratories. Budínová, I. (2013). Polynomy . Brno: Masarykova univerzita, Pedagogická fakulta. Čechová, P. (2013). Základní věta algrebry a její důkazy (Diplomová práce). Brno: Masarykova univerzita, Přírodovědecká fakulta. Fajmon, B., & Růžičková, I. (2003). IS-VUT-MAT103. Brno: VUT v Brně, Fakulta elektrotechniky a komunikačních technologií. Fišnarová, S. (22. září 2008). Polynomy a racionální lomené funkce. Načteno z Kiwi.mendelu.cz: http://user.mendelu.cz/fisnarov/zvm/prednasky/polynomy_text.pdf Hašek, R. (5. července 2018). Vietovy vzorce. Načteno z Pedagogická fakulta Jihočeská univerzita v Českých Budějovicích: http://home.pf.jcu.cz/~hasek/Algebra4/ALG4%20046.jpg Hohenwarter, M. (únor 2002). GeoGebra: Ein Softwaresystem für dynamische Geometrie und Algebra der Ebene. Neměcko: Paris Lodron University, Salzubrg, Austria. Načteno z https://www.geogebra.org/ Horák, P. (1977). Polynomy. Brno: Univerzita Jana Evangelisty Purkyně. Horová, I. (1999). Numerické metody. Brno: Masarykova univerzita, Přírodovědecká fakulta. Chapra, S. C., & Canale, R. P. (2010). Mumerical Methods for Engineers. New York: McGraw-Hill. Mařík, R. (31. říjen 2012a). Přibližné řešení rovnic. Načteno z Kiwi.mendelu.cz: http://user.mendelu.cz/marik/mat-web/mat-webse23.html Mařík, R. (31. říjen 2012b). Věty o spojitých funkcích. Načteno z Kiwi.mendelu.cz: http://user.mendelu.cz/marik/mat-web/mat-webse5.html#x10-70005 Páv, D. (2010). Řešení kubických rovnic (Diplomová práce). Liberec: Technická univerzita v Liberci, Fakulta přírodovědně-humanitní a pedagogická. 56 Rosický, J. (2000). Algebra. Brno: Masarykova univerzita, Přírodovědecká fakulta. Slovák, J., Panák, M., Bulant, M., Návrat, A., & Veselý, M. (2013). Matematika drsně a svižně . Brno: Masarykova univerzita. Spojitost funkce (21. červenec 2018). Načteno z Matematika.cz: https://matematika.cz/spojitost-funkce Tišnovský, P. (28. březen 2006). Fraktály v počítačové grafice XXIII. Načteno z Root.cz: https://www.root.cz/clanky/fraktaly-v-pocitacove-grafice-xxiii/#k04 Wolfram Research, I. (22. prosinec 2018). Long Division of Polynomials. Načteno z Essential Mathematica for Students of Science: Tutorial Approach to Mastery of Mathematica -- from Wolfram Library Archive: http://library.wolfram.com/webMathematica/Education/LongDivide.jsp 57 Seznam obrázků: Obrázek 1: Graf funkce 𝑓 = 𝑥2 − 1............................................................................... 27 Obrázek 2: Grafy funkcí 𝑓1(𝑥) = 𝑥2 + 1 (zeleně) a 𝑓2(𝑥) = 𝑥5 (modře) ...................... 28 Obrázek 3: Ukázka metody půlení intervalu .................................................................. 29 Obrázek 4: Graf funkcí 𝑓(𝑥) = 2𝑥 − 2 a 𝑔(𝑥) = 𝑥 ...................................................... 30 Obrázek 5: Příklad divergence iterační funkce............................................................... 31 Obrázek 6: Graf funkcí 𝑓(𝑥) = 𝑥5 + 𝑥2 − 3, 𝑔(𝑥) = √3 − x25 a 𝑦 = 𝑥 ....................... 33 Obrázek 7: Newtonova metoda....................................................................................... 34 Obrázek 8: Newtonova fraktální množina polynomu z3 − 1 = 0.................................. 37 Obrázek 9: Newtonova fraktální množina polynomu 𝑧8 − 1 = 0 ................................. 37 Obrázek 10: Kód vzorového polynomu.......................................................................... 40 Obrázek 11: Zastavení průběhu metody půlení intervalu po určitém počtu kroků a ignorování kroků při nastavení imax = 0 ....................................................................... 40 Obrázek 12: Půlení intervalu, příklad na omezený počet kroků..................................... 40 Obrázek 13: Kontrola vzestupnosti krajních bodů v intervalu ....................................... 40 Obrázek 14: Ukázka kontroly a úprava intervalu pro polynom 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 .... 41 Obrázek 15: Kontrola, zdali je kořen polynomu v daném intervalu............................... 41 Obrázek 16: Kontrola, zda se v intervalu 𝐼 = 〈1, 2〉 polynomu 𝑓(𝑥) = 𝑥3 + 𝑥 − 1 nachází kořen .................................................................................................................. 41 Obrázek 17: Kontrola, zda je krajní bod intervalu kořenem polynomu ......................... 41 Obrázek 18: Polynom 𝑓(𝑥) = 𝑥3 + 2𝑥2 − 𝑥 − 2 má v krajním bodě 𝑥 = 1 intervalu 𝐼 = 〈0, 1〉 kořen............................................................................................................... 41 Obrázek 19: Algoritmus půlení 1. část ........................................................................... 42 Obrázek 20: Algoritmus půlení 2. část ........................................................................... 42 Obrázek 21: Funkce write - 1.část .................................................................................. 42 Obrázek 22: Funkce write - 2.část .................................................................................. 42 Obrázek 23: Funkce n2s ................................................................................................. 42 Obrázek 24: Kód vzorové iterační funkce ...................................................................... 43 Obrázek 25: Ukázka divergence posloupnosti aproximací funkce 𝑔(𝑥) = 1 − 𝑥 při zadání 𝑥0 = 0.................................................................................................................. 43 Obrázek 26: Ukázka konvergence posloupnosti aproximací funkce 𝑔(𝑥) = 1 − 𝑥 při zadání 𝑥0 = 0,5............................................................................................................... 43 Obrázek 27: Ukázka, jak se metoda chová při zadání 𝑥0 = 2, kdy jako další aproximace vychází komplexní číslo ................................................................................................. 44 Obrázek 28: Derivace polynomu .................................................................................... 44 Obrázek 29: Převedení na rostoucí funkci...................................................................... 45 Obrázek 30: Graf funkce 𝑓(𝑥) = 2𝑥4 − 11𝑥2 + 5........................................................ 48 Obrázek 31: Graf funkce 𝑓(𝑥) = 𝑥4 + 3𝑥3 + 4𝑥2 + 3𝑥 + 1........................................ 49 58 Seznam tabulek: Tabulka 1: Tabulka pro Hornerovo schéma ................................................................... 15 Tabulka 2: Výpočet kořenu polynomu 𝑓(𝑥) = 𝑥4 + 5𝑥3 + 7𝑥2 + 5𝑥 + 6 pomocí Hornerova schématu ....................................................................................................... 16 Tabulka 3: Hledání kořeny polynomu 𝑔(𝑥) = 𝑥4 − 1 pomocí Hornerova schématu... 17 Tabulka 4: Vztah mezi Taylorovým rozvojem a Hornerovým schématem pro polynom 𝑓(𝑥) = 𝑥3 − 2𝑥 + 1....................................................................................................... 18 Tabulka 5: Hornerovo schéma pro výpočet kořenů polynomu 𝑓(𝑥) = 6𝑥3 + 7𝑥2 − 𝑥 − 2............................................................................................ 22 Tabulka 6: Hornerovo schéma pro výpočet kořenů polynomu 𝑓(𝑥) = 𝑥6 + 𝑥5 + 4𝑥4 + 3𝑥3 + 5𝑥2 + 2𝑥 + 2............................................................. 25 Tabulka 7: Hledání kořene polynomu 𝑓(𝑥) = 𝑥5 − 𝑥2 − 1 metodou půlení intervalu. 30 Tabulka 8: Kořeny polynomu 𝑓(𝑥) = 𝑥3 + 𝑥 − 1......................................................... 46 Tabulka 9: Kořeny polynomu 𝑓(𝑥) = 𝑥5 − 𝑥3 + 𝑥 − 2................................................ 47 Tabulka 10: Kořeny polynomu 𝑓(𝑥) = 𝑥5 − 𝑥3 + 𝑥 − 2............................................. 48 Tabulka 11: Kořeny polynomu 𝑓(𝑥) = 𝑥4 + 3𝑥3 + 4𝑥2 + 3𝑥 + 1 ............................. 49 Tabulka 12: Kořeny polynomu 𝑓(𝑥) = 147𝑥4 + 84𝑥3 − 40𝑥2 − 28𝑥 − 3................. 50 Tabulka 13: Kořeny polynomu 𝑓(𝑥) = 147𝑥4 + 84𝑥3 − 40𝑥2 − 28𝑥 − 3................. 51 59 Přílohy Program „Půlení intervalu“ #Puleni intervalu #vzorový polynom, počítáme v intervalu I=<0,1> polynom_vzor <- function(x) { return(x ^ 3 + x - 1) } #převedení tečky u desetinných čísel na čárku n2s <- function(n) { format(n, decimal.mark = ",") } #funkce, kde (a,b) = interval, e = přesnost, polynom = námi #zadaný polynom, i_max = maximální počet kroků, při zadání #i_max = 0, nekonečně mnoho kroků puleni <- function(a, b, e = 0.001, polynom = NULL, i_max = 1000) { #převedení zadaného polynomu na výraz (expresssion) exp <- substitute(polynom) #když není zadán žádný polynom, program počítá se vzorovým #polynomem if(is.null(exp)) { pol <- polynom_vzor } #převedení výrazu na funkci else { pol <- function (x) {} body(pol) <- exp } #ověření, zda je interval zadán vzestupně if(a > b) { t <- a a <- b b <- t } #výpočet funkčních hodnot f_a <- pol(a) f_b <- pol(b) i <- 0 #ověření, že v daném intervalu se nachází kořen if(f_a * f_b > 0) { print(paste(sep="", "Máte špatně zadaný interval: ", "f(", n2s(a), ")=", n2s(f_a), ", f(", n2s(b), ")=", n2s(f_b))) return(NA) } 60 #ověření, zdali je jeden z krajích bodů intervalu kořenem #polynomu if(abs(f_a) <= e) { print(paste(sep = "", "Kořenem je ", n2s(a))) return(a) } if(abs(f_b) <= e) { print(paste(sep = "", "Kořenem je ", n2s(b))) return(b) } #vytvoření souboru, kde se uloží vypočítáné hodnoty, #a pojmenování hodnot soubor <- file("Puleni_tabulka.csv", "w") write("krok;a;b;s;f(a);f(b);f(s)", soubor) #cyklus, který provádí půlení, dokud není dosaženo přesnosti e while(abs(a - b) > e) { f_a <- pol(a) f_b <- pol(b) s <- (a + b) / 2 f_s <- pol(s) #ukládání hodnot do souboru write(paste(sep = "", i, ";", n2s(a), ";", n2s(b), ";", n2s(s), ";", n2s(f_a), ";", n2s(f_b), ";", n2s(f_s)), soubor) print(paste(sep = "", i, ": ", "s=", n2s(s))) #ověření, zdali jsme dosáhli určeného počtu kroků i <- i + 1 if(i_max > 0 && i > i_max){ print(paste(sep = "", "Kořen s danou přesností nenalezen", ", počet kroků=", i - 1)) break } #ověření, zda jsem nalezli kořen přesně if(f_s == 0) { print(paste(sep = "", "Kořenem je ", n2s(s))) break } #ověření, s jakým intervalem budeme nadále počítat if(f_a * f_s < 0) { b <- s } else { a <- s } } close(soubor) } 61 Program „Metoda prosté iterace“ #Metoda prosté iterace #vzorový polynom, počáteční hodnota x_0=0,5 polynom_vzor <- function(x) { return((1 - x) ^ (1 / 3)) } #převedení tečky u desetinných čísel na čárku n2s <- function(n) { format(n, decimal.mark = ",") } #funkce, kde x = počáteční aproximace, e = přesnost, #polynom = námi zadaný polynom, i_max = maximální počet kroků, #při zadání i_max = 0, nekonečně mnoho kroků iterace <- function(x, e = 0.001, polynom = NULL, i_max = 1000) { #převedení zadaného polynomu na výraz (expresssion) exp <- substitute(polynom) #když není zadán žádný polynom, program počítá se vzorovým #polynomem if(is.null(exp)) { pol <- polynom_vzor } #převedení výrazu na funkci else { pol <- function (x) {} body(pol) <- exp } #vytvoření souboru, kde se uloží hodnoty, a pojmenování hodnot soubor <- file("Iterace_tabulka.csv", "w") write("krok;x", soubor) write(paste(sep = "", "0;", n2s(x)), soubor) print(paste(sep = "", "x_0: ", n2s(x))) x_k <- pol(x) write(paste(sep = "", "1;", n2s(x_k)), soubor) print(paste(sep = "", "x_1: ", n2s(x_k))) i <- 2 #cyklus, který provádí aproximaci kořene, dokud není dosaženo #přesnosti e while (abs(x_k - x) > e) { x <- x_k x_k <- pol(x) #ukládání hodnot do souboru write(paste(sep = "", i, ";", n2s(x_k)), soubor) 62 print(paste(sep = "", "x_",i,": ", n2s(x_k))) #ověření, zdali jsem dosáhli požadovaného počtu kroků i <- i + 1 if (i_max > 0 && i > i_max) { print(paste(sep = "", "Kořen s danou přesností nenalezen", ", počet kroků=", i - 1)) break } } close(soubor) } Program „Newtonova metoda pro reálné kořeny“ #Newtonova metoda pro reálné kořeny #vzorový polynom, počítáme v intervalu I=<0,1> polynom_vzor <- function(x) { return(x ^ 3 + x - 1) } #derivace vzorového polynomu derivace_vzor <- function(x) { return(3 * x ^ 2 + 1) } #princip Newtonovy metody prubeh <- function(x, pol, der) { return(x - pol(x) / der(x)) } #převedení tečky u desetinných čísel na čárku n2s <- function(n) { format(n, decimal.mark = ",") } #funkce, kde je interval, e = přesnost, polynom = zadaný #polynom, i_max = maximální počet kroků, při zadání i_max = 0, #nekonečně mnoho kroků newton <- function(a, b, e = 0.001, polynom = NULL, i_max = 1000) { #převedení zadaného polynomu na výraz (expresssion) exp <- substitute(polynom) #když není zadán žádný polynom, program počítá se vzorovým #polynomem a jeho derivací if(is.null(exp)) { pol <- polynom_vzor der <- derivace_vzor } #výpočet derivace polynomu a převedení výrazu na funkci else { 63 pol <- function (x) {} body(pol) <- exp derBody <- D(exp, "x") der <- function (x) {} body(der) <- derBody } #ověření, zda je interval zadán vzestupně if(a > b) { t <- a a <- b b <- t } #výpočet funkčních hodnot f_a <- pol(a) f_b <- pol(b) i <- 2 #převedení na rostoucí funkci if(f_a > f_b) { v <- a a <- b b <- v } #vytvoření souboru, kde se uloží vypočítáné hodnoty, #a pojmenování hodnot soubor <- file("Newton_tabulka.csv", "w") write("krok;x", soubor) #ověření, zdali jeden z krajích bodů intervalu není kořenem #polynomu if(abs(f_a) <= e) { print(paste(sep = "", "Kořenem je ", n2s(a))) return(a) } if(abs(f_b) <= e) { print(paste(sep = "", "Kořenem je ", n2s(b))) return(b) } #ověření, že v daném intervalu se nachází kořen if(f_a * f_b > 0) { print(paste(sep="", "Máte špatně zadaný interval: ", "f(", n2s(a), ")=", n2s(f_a), ", f(", n2s(b), ")=", n2s(f_b))) return(NA) } #ukládání hodnot do souboru write(paste(sep = "", 0, ";", n2s(b)), soubor) 64 print(paste(sep = "", "x_0: ", n2s(b))) x <- prubeh(b, pol, der) write(paste(sep = "", 1, ";", n2s(x)), soubor) print(paste(sep = "", "x_1: ", n2s(x))) #cyklus, který provádí aproximaci kořene, dokud není dosaženo #přesnosti e while(abs(x - b) > e) { b <- x x <- prubeh(b, pol, der) #ukládání hodnot do souboru write(paste(sep = "", i, ";", n2s(x)), soubor) print(paste(sep = "", "x_", i, ": ", n2s(x))) #ověření, zdali jsem dosáhli požadovaného počtu kroků i <- i + 1 if(i_max > 0 && i > i_max) { print(paste(sep = "", "Kořen s danou přesností nenalezen",", počet kroků=", i - 1)) break } } close(soubor) } Program „Newtonova metoda pro komplexní kořeny“ #Newtonova metoda pro komplexní kořeny #vzorový polynom, počítáme pro počáteční aproximaxi x_0 = 1+1i polynom_vzor <- function(x) { return(x ^ 6 + x ^ 5 + 4 * x ^ 4 + 3 * x ^ 3 + 5 * x ^ 2 + 2 * x + 2) } #derivace vzorového polynomu derivace_vzor <- function(x) { return(6 * x ^ 5 + 5 * x ^ 4 + 16 * x ^ 3 + 9 * x ^ 2 + 10 * x + 2) } #princip Newtonovy metody prubeh <- function(x, pol, der) { return(x - pol(x) / der(x)) } #převedení tečky u desetinných čísel na čárku n2s <- function(n) { format(n, decimal.mark = ",") } #funkce, kde x je počáteční aproximace, e = přesnost, #polynom = #zadaný polynom, i_max = maximální počet kroků, při #zadání i_max = 0, nekonečně mnoho kroků 65 newton_complex <- function(a, e = 0.001, polynom = NULL, i_max = 1000) { #převedení zadaného polynomu na výraz (expresssion) exp <- substitute(polynom) #když není zadán žádný polynom, program počítá se vzorovým #polynomem a jeho derivací if(is.null(exp)) { pol <- polynom_vzor der <- derivace_vzor } #výpočet derivace polynomu a převedení výrazu na funkci else { pol <- function (x) {} body(pol) <- exp derBody <- D(exp, "x") der <- function (x) {} body(der) <- derBody } f_a <- pol(a) i <- 2 #vytvoření souboru, kde se uloží vypočítáné hodnoty, #a pojmenování hodnot soubor <- file("Newton_komplex_tabulka.csv", "w") write("krok;x", soubor) #ověření, zdali je počáteční aproximace kořenem polynomu if(abs(f_a) <= e) { print(paste(sep = "", "Kořenem je ", n2s(a))) return(a) } #ukládání hodnot do souboru write(paste(sep = "", 0, ";", n2s(a)), soubor) print(paste(sep = "", "x_0: ", n2s(a))) x <- prubeh(a, pol, der) write(paste(sep = "", 1, ";", n2s(x)), soubor) print(paste(sep = "", "x_1: ", n2s(x))) #cyklus, který provádí aproximaci kořene, dokud není dosaženo #přesnosti e while(abs(x - a) > e) { a <- x x <- prubeh(a, pol, der) #ukládání hodnot do souboru write(paste(sep = "", i, ";", n2s(x)), soubor) 66 print(paste(sep = "", "x_", i, ": ", n2s(x))) #ověření, zdali jsem dosáhli požadovaného počtu kroků i <- i + 1 if(i_max > 0 && i > i_max) { print(paste(sep = "", "Kořen s danou přesností nenalezen", ", počet kroků=", i - 1)) break } } close(soubor) } Program „Derivace polynomu“ #Derivace polynomu derivace <- function (polynom) { exp <- substitute(polynom) derBody <- D(exp, "x") der <- function (x) {} body(der) <- derBody return(der) }