Metoda půlení - Bisection method

v matematika, metoda půlení je metoda hledání kořenů to platí pro všechny spojité funkce pro které jeden zná dvě hodnoty s opačnými znaménky. Metoda se skládá z opakovaně půlení the interval definováno těmito hodnotami a poté výběrem podintervalu, ve kterém funkce mění znaménko, a proto musí obsahovat a vykořenit. Je to velmi jednoduchá a robustní metoda, ale je také relativně pomalá. Z tohoto důvodu se často používá k získání hrubé aproximace řešení, které se poté použije jako výchozí bod pro rychlejší konvergující metody.[1] Metoda se také nazývá poloviční interval metoda,[2] the metoda binárního vyhledávání,[3] nebo dichotomická metoda.[4]
Pro polynomy, existují podrobnější metody pro testování existence kořene v intervalu (Descartova vláda znamení, Sturmova věta, Budanova věta ). Umožňují rozšíření metody půlení na efektivní algoritmy pro nalezení všech skutečných kořenů polynomu; vidět Skutečná kořenová izolace.
Metoda
Metoda je použitelná pro numerické řešení rovnice F(X) = 0 pro nemovitý proměnná X, kde F je spojitá funkce definované v intervalu [A, b] a kde F(A) a F(b) mají opačné znaky. V tomto případě A a b se říká, že držák kořen, protože tím, že věta o střední hodnotě, spojitá funkce F musí mít alespoň jeden kořen v intervalu (A, b).
V každém kroku metoda rozdělí interval na dva výpočtem středového bodu C = (A+b) / 2 intervalu a hodnoty funkce F(C) v tomto bodě. Ledaže C je sám kořen (což je velmi nepravděpodobné, ale možné), nyní existují pouze dvě možnosti: buď F(A) a F(C) mít opačné znaménka a držet kořen, nebo F(C) a F(b) mít opačné znaménka a držet kořen.[5] Metoda vybere jako nový interval, který se použije v dalším kroku, subinterval, který je zaručeně závorka. Tímto způsobem interval, který obsahuje nulu F se v každém kroku zmenší o 50%. Proces pokračuje, dokud není interval dostatečně malý.
Výslovně, pokud F(A) a F(C) mají opačné znaky, pak se nastaví metoda C jako nová hodnota pro b, a pokud F(b) a F(C) mají opačné znaky než sady metod C jako nový A. (Li F(C) = 0 potom C může být bráno jako řešení a proces se zastaví.) V obou případech nový F(A) a F(b) mají opačné znaky, takže metoda je použitelná pro tento menší interval.[6]
Iterační úkoly
Vstupem pro metodu je spojitá funkce F, interval [A, b] a hodnoty funkcí F(A) a F(b). Hodnoty funkcí mají opačné znaménko (v intervalu je alespoň jeden křížení nuly). Každá iterace provádí tyto kroky:
- Vypočítat C, střed intervalu, C = A + b/2.
- Vypočítejte hodnotu funkce ve středu, F(C).
- Pokud je konvergence uspokojivá (tj. C - A je dostatečně malý nebo |F(C) | je dostatečně malý), návrat C a přestat iterovat.
- Prozkoumejte znamení F(C) a vyměňte buď (A, F(A)) nebo (b, F(b)) s (C, F(C)), aby v novém intervalu došlo k přechodu nuly.
Při implementaci metody v počítači mohou nastat problémy s konečnou přesností, takže často existují další testy konvergence nebo limity počtu iterací. Ačkoli F je spojitá, konečná přesnost může vyloučit, že hodnota funkce bude někdy nulová. Zvažte například F(X) = X - π; nikdy nebude konečné znázornění X to dává nulu. Navíc rozdíl mezi A a b je omezena přesností s plovoucí desetinnou čárkou; tj. jako rozdíl mezi A a b klesá, v určitém okamžiku střed [A, b] bude numericky shodný s (s přesností na plovoucí desetinnou čárku) A nebo b..
Algoritmus
Metoda může být napsána v pseudo kód jak následuje:[7]
VSTUP: Funkce F, hodnoty koncových bodů A, btolerance TOL, maximální iterace NMAXPODMÍNKY: A < b, buď F(A) <0 a F(b)> 0 nebo F(A)> 0 a F(b) < 0VÝSTUP: hodnota, která se liší od kořene F(X) = 0 o méně než TOL N ← 1zatímco N ≤ NMAX dělat // omezit iterace, aby se zabránilo nekonečné smyčce C ← (A + b)/2 // nový střed -li F(C) = 0 nebo (b – A)/2 < TOL pak // řešení nalezeno Výstup(C) Stop skončit, pokud N ← N + 1 // čítač kroků přírůstku -li podepsat(F(C)) = podepsat (F(A)) pak A ← C jiný b ← C // nový intervalskončit chvíliVýstup („Metoda se nezdařila.“) // překročen maximální počet kroků
Příklad: Hledání kořene polynomu
Předpokládejme, že k nalezení kořene polynomu je použita metoda půlení
Nejprve dvě čísla a musí být nalezeny tak a mít opačné znaky. U výše uvedené funkce a splňovat toto kritérium,
a
Protože je funkce spojitá, musí být v intervalu [1, 2] kořen.
V první iteraci jsou koncové body intervalu, který je v závorkách kořen a , takže střed je
Hodnota funkce ve středu je . Protože je negativní, je nahrazen pro další iteraci to zajistíme a mít opačné znaky. Jak to pokračuje, interval mezi a bude čím dál menší, sbíhající se na kořen funkce. Podívejte se na to v následující tabulce.
Opakování | ||||
---|---|---|---|---|
1 | 1 | 2 | 1.5 | −0.125 |
2 | 1.5 | 2 | 1.75 | 1.6093750 |
3 | 1.5 | 1.75 | 1.625 | 0.6660156 |
4 | 1.5 | 1.625 | 1.5625 | 0.2521973 |
5 | 1.5 | 1.5625 | 1.5312500 | 0.0591125 |
6 | 1.5 | 1.5312500 | 1.5156250 | −0.0340538 |
7 | 1.5156250 | 1.5312500 | 1.5234375 | 0.0122504 |
8 | 1.5156250 | 1.5234375 | 1.5195313 | −0.0109712 |
9 | 1.5195313 | 1.5234375 | 1.5214844 | 0.0006222 |
10 | 1.5195313 | 1.5214844 | 1.5205078 | −0.0051789 |
11 | 1.5205078 | 1.5214844 | 1.5209961 | −0.0022794 |
12 | 1.5209961 | 1.5214844 | 1.5212402 | −0.0008289 |
13 | 1.5212402 | 1.5214844 | 1.5213623 | −0.0001034 |
14 | 1.5213623 | 1.5214844 | 1.5214233 | 0.0002594 |
15 | 1.5213623 | 1.5214233 | 1.5213928 | 0.0000780 |
Po 13 iteracích je zřejmé, že existuje konvergence k přibližně 1,521: kořen polynomu.
Analýza
Je zaručeno, že metoda konverguje do kořenového adresáře F -li F je spojitá funkce na intervalu [A, b] a F(A) a F(b) mají opačné znaky. The absolutní chyba je v každém kroku na polovinu, takže metoda konverguje lineárně, což je poměrně pomalé.
Konkrétně pokud C1 = A+b/2 je střed počátečního intervalu a Cn je střed intervalu v nkrok, pak rozdíl mezi Cn a řešení C je ohraničen[8]
Tento vzorec lze použít k určení předem horní hranice počtu iterací, které metoda bisekce potřebuje ke konvergenci na kořen v rámci určité tolerance. n iterací potřebných k dosažení požadované tolerance ε (tj. chyba zaručená maximálně ε), je omezena
kde je počáteční velikost závorky a požadovanou velikost držáku
Viz také
- Algoritmus binárního vyhledávání
- Lehmer – Schurův algoritmus, zobecnění metody půlení v komplexní rovině
- Vnořené intervaly
Reference
- ^ Burden & Faires 1985, str. 31
- ^ „Archivovaná kopie“. Archivovány od originál dne 19. 05. 2013. Citováno 2013-11-07.CS1 maint: archivovaná kopie jako titul (odkaz)
- ^ Burden & Faires 1985, str. 28
- ^ „Dichotomická metoda - encyklopedie matematiky“. www.encyclopediaofmath.org. Citováno 2015-12-21.
- ^ Pokud má funkce stejné znaménko v koncových bodech intervalu, koncové body mohou, ale nemusí, obsahovat kořenové závorky funkce.
- ^ Burden & Faires 1985, str. 28 pro sekci
- ^ Burden & Faires 1985, str. 29. Tato verze přepočítává hodnoty funkcí při každé iteraci, místo aby je přenášela na další iterace.
- ^ Burden & Faires 1985, str. 31, Věta 2.1
- Burden, Richard L .; Faires, J. Douglas (1985), „2.1 Algoritmus půlení“, Numerická analýza (3. vyd.), PWS Publishers, ISBN 0-87150-857-5
Další čtení
- Corliss, George (1977), „Jaký kořen najde algoritmus půlení?“, Recenze SIAM, 19 (2): 325–327, doi:10.1137/1019044, ISSN 1095-7200
- Kaw, autar; Kalu, Egwu (2008), Numerické metody s aplikacemi (1. vyd.), Archivovány od originál dne 13. 4. 2009
externí odkazy
- Weisstein, Eric W. „Bisection“. MathWorld.
- Metoda půlení Poznámky, PPT, Mathcad, Maple, Matlab, Mathematica od Holistický institut numerických metod