Metoda Durand – Kerner - Durand–Kerner method
tento článek má nejasný styl citace.Listopad 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v numerická analýza, Weierstrassova metoda nebo Metoda Durand – Kerner, objeveno uživatelem Karl Weierstrass v roce 1891 a znovuobjevený nezávisle Durandem v roce 1960 a Kernerem v roce 1966, je a algoritmus hledání kořenů k řešení polynomiální rovnice.[1] Jinými slovy lze metodu použít k numerickému řešení rovnice
- F(X) = 0,
kde F je daný polynom, který lze považovat za zmenšený tak, že hlavní koeficient je 1.
Vysvětlení
Toto vysvětlení zohledňuje rovnice stupeň čtyři. Je snadno zobecnitelný na jiné stupně.
Nechť polynom F být definován
pro všechny X.
Známá čísla A, b, C, d jsou koeficienty.
Nechte (komplexní) čísla P, Q, R, S být kořeny tohoto polynomu F.
Pak
pro všechny X. Hodnotu lze izolovat P z této rovnice:
Pokud se tedy použije jako pevný bod opakování
je silně stabilní v každém počátečním bodě X0 ≠ Q, R, Sdoručí po jedné iteraci root P = X1.
Kromě toho, pokud jeden nahradí nuly Q, R a Saproximacemi q ≈ Q, r ≈ R, s ≈ S, takový, že q, r, s se nerovnají P, pak Pje stále pevným bodem narušené iterace pevného bodu
od té doby
Všimněte si, že jmenovatel se stále liší od nuly. Tato iterace s pevným bodem je a mapování kontrakcí pro X kolem P.
Klíčem k této metodě je nyní kombinace iterace s pevným bodem pro P s podobnými iteracemi pro Q, R, S do simultánní iterace pro všechny kořeny.
Inicializovat p, q, r, s:
- p0 := (0.4 + 0.9i)0,
- q0 := (0.4 + 0.9i)1,
- r0 := (0.4 + 0.9i)2,
- s0 := (0.4 + 0.9i)3.
Na výběru 0,4 + 0,9 není nic zvláštníhoi kromě toho, že to není ani reálné číslo ani a kořen jednoty.
Proveďte náhrady za n = 1, 2, 3, ...:
Opakujte iteraci, dokud nebudou čísla p, q, r, sv podstatě se přestanou měnit vzhledem k požadované přesnosti. Poté mají hodnoty P, Q, R, S v určitém pořadí a ve zvolené přesnosti. Takže problém je vyřešen.
Všimněte si, že komplexní číslo musí být použita aritmetika a že kořeny se nalézají současně, nikoli po jednom.
Variace
Tento iterační postup, jako Gauss – Seidelova metoda pro lineární rovnice počítá po jednom čísle na základě již vypočítaných čísel. Varianta tohoto postupu, jako Jacobiho metoda, spočítá vektor aproximací kořenů najednou. Obě varianty jsou efektivní algoritmy hledání kořenů.
Dalo by se také zvolit počáteční hodnoty pro p, q, r, snějakým jiným postupem, i když náhodně, ale takovým způsobem
- jsou uvnitř nějakého ne příliš velkého kruhu obsahujícího také kořeny F(X), např. kruh kolem počátku s poloměrem , (kde 1, A, b, C, d jsou koeficienty F(X))
a to
- nejsou si příliš blízcí,
což se může stále více stávat problémem, protože se zvyšuje stupeň polynomu.
Pokud jsou koeficienty skutečné a polynom má lichý stupeň, pak musí mít alespoň jeden skutečný kořen. Chcete-li to najít, použijte skutečnou hodnotu p0 jako počáteční odhad a provedení q0 a r0, atd., komplexní konjugát páry. Pak iterace zachová tyto vlastnosti; to je pn vždy bude skutečný a qn a rnatd. budou vždy konjugovány. Tímto způsobem pn se sblíží ke skutečnému kořenu P. Případně proveďte všechny počáteční odhady skutečné; zůstanou tak.
Příklad
Tento příklad pochází z reference 1992. Vyřešená rovnice je X3 − 3X2 + 3X − 5 = 0. První 4 iterace se pohybují p, q, r zdánlivě chaoticky, ale pak jsou kořeny umístěny na 1 desetinné místo. Po iteračním čísle 5 máme 4 správná desetinná místa a následné iterační číslo 6 potvrzuje, že vypočítané kořeny jsou pevné. Toto obecné chování je pro metodu charakteristické. Všimněte si také, že v tomto příkladu jsou kořeny použity, jakmile jsou vypočítány v každé iteraci. Jinými slovy, výpočet každého druhého sloupce používá hodnotu předchozích vypočítaných sloupců.
to. - č. p q r 0 +1,0000 + 0,0000i +0,4000 + 0,9000i −0,6500 + 0,7200i 1 +1,3608 + 2,0222i -0,3658 + 2,4838i −2,3858 - 0,0284i 2 +2,6597 + 2,7137i +0,5977 + 0,8225i -0,6320-1,6716i 3 +2 2704 + 0,3880i +0,1312 + 1,3128i +0,2821 - 1,5015i 4 +2,5428 - 0,0153i +0,2044 + 1,3716i +0,2056 - 1,3721i 5 +2,5874 + 0,0000i +0,2063 + 1,3747i +0,2063 - 1,3747i 6 +2,5874 + 0,0000i +0,2063 + 1,3747i +0,2063 - 1,3747i
Všimněte si, že rovnice má jeden skutečný kořen a jeden pár komplexních konjugovaných kořenů a že součet kořenů je 3.
Odvození metody pomocí Newtonovy metody
Pro každého n-tuple komplexních čísel, existuje přesně jeden monický polynom stupně n který je má jako své nuly (zachování multiplicity). Tento polynom je dán vynásobením všech odpovídajících lineárních faktorů, tj
Tento polynom má koeficienty, které závisí na předepsaných nulách,
Tyto koeficienty jsou až do znaménka elementární symetrické polynomy stupňů 1, ..., č.
Najít všechny kořeny daného polynomu s vektorem koeficientu současně je to stejné jako najít vektor řešení v systému
Metoda Durand – Kerner se získá jako vícerozměrná Newtonova metoda aplikován na tento systém. Je algebraicky pohodlnější zacházet s těmito identitami koeficientů jako s identitou odpovídajících polynomů, . V Newtonově metodě člověk vypadá, vzhledem k počátečnímu vektoru , pro přírůstkový vektor takhle je v přírůstku spokojen až do podmínek druhého a vyššího řádu. Pro tohle řeší identitu
Pokud jsou čísla jsou po dvou různé, pak polynomy z hlediska pravé strany tvoří základ n-rozměrný prostor polynomů s maximálním stupněm n - 1. Tedy řešení k přírůstkové rovnici v tomto případě existuje. Souřadnice přírůstku jsou jednoduše získány vyhodnocením přírůstkové rovnice
v bodech , jehož výsledkem je
- , to je
Zahrnutí kořenů prostřednictvím kruhů Gerschgorin
V kvocientový kroužek (algebra) z zbytkové třídy modulo ƒ (X), násobení X definuje endomorfismus který má nuly ƒ (X) tak jako vlastní čísla s odpovídajícími multiplicitami. Při výběru základu je operátor násobení reprezentován maticí koeficientu A, doprovodná matice z ƒ (X) z tohoto důvodu.
Protože každý polynom lze zmenšit modulo ƒ (X) na polynom stupně n - 1 nebo nižší, prostor tříd reziduí lze identifikovat pomocí prostoru polynomů stupně ohraničeného n - 1. Lze vzít z konkrétního problému Lagrangeova interpolace jako soubor n polynomy
kde jsou párově různá komplexní čísla. Funkce jádra pro Lagrangeovu interpolaci jsou .
Pro operátor násobení aplikovaný na základní polynomy se získá z Lagrangeovy interpolace
, |
kde jsou opět aktualizace Weierstrass.
Doprovodná matice ƒ (X) je tedy
Z transponovaného maticového případu Gershgorinova věta o kruhu z toho vyplývá, že všechny vlastní hodnoty A, tedy všechny kořeny ƒ (X), jsou obsaženy ve spojení disků s poloměrem .
Tady jeden má , takže centra jsou další iterace Weierstrassovy iterace a poloměry což jsou násobky aktualizací Weierstrass. Pokud kořeny ƒ (X) jsou všechny dobře izolované (vzhledem k přesnosti výpočtu) a body jsou dostatečně blízké aproximaci těchto kořenů, pak se všechny disky stanou disjunktními, takže každý obsahuje přesně jednu nulu. Středové body kruhů budou lepšími aproximacemi nul.
Každá matice konjugátu z A je také doprovodnou maticí ƒ (X). Výběr T jako diagonální matice opouští strukturu A neměnný. Kořen blízko je obsažen v jakémkoli izolovaném kruhu se středem bez ohledu na T. Volba optimální diagonální matice T každý index vede k lepším odhadům (viz ref. Petkovic et al. 1995).
Výsledky konvergence
Spojení mezi Taylorovou řadou a Newtonovou metodou naznačuje, že vzdálenost od k příslušnému kořenu je řádu , pokud je kořen dobře izolován od blízkých kořenů a aproximace je dostatečně blízko kořene. Takže jakmile je aproximace blízko, Newtonova metoda konverguje kvadraticky; to znamená, že chyba je čtvercová s každým krokem (což výrazně sníží chybu, jakmile je menší než 1). V případě metody Durand – Kerner je konvergence kvadratická, pokud jde o vektor je blízko nějaké permutace vektoru kořenů F.
Pro závěr lineární konvergence existuje konkrétnější výsledek (viz ref. Petkovic et al. 1995). Pokud je počáteční vektor a jeho vektor Weierstrassových aktualizací uspokojuje nerovnost
pak tato nerovnost platí také pro všechny iterace, všechny inkluzní disky jsou disjunktní a lineární konvergence s kontrakčním faktorem 1/2. Dále mohou být v tomto případě inkluzní disky vybrány jako
každý obsahuje přesně jednu nulu F.
Selhání obecné konvergence
Metoda Weierstrass / Durand-Kerner není obecně konvergentní: jinými slovy, není pravda, že pro každý polynom je sada počátečních vektorů, které nakonec konvergují ke kořenům, otevřená a hustá. Ve skutečnosti existují otevřené sady polynomů, které mají otevřené sady počátečních vektorů, které konvergují k jiným periodickým cyklům než kořenům (viz Reinke et al.)
Reference
- ^ Petković, Miodrag (1989). Iterační metody pro současné zahrnutí polynomiálních nul. Berlin [u.a.]: Springer. 31–32. ISBN 978-3-540-51485-5.
- Weierstraß, Karl (1891). „Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen“. Sitzungsberichte der königlich preussischen Akademie der Wissenschaften zu Berlin.
- Durand, E. (1960). "Rovnice du typu F(X) = 0: Racines d'un polynome ". In Masson; et al. (Eds.). Řešení Numériques des Equations Algébriques. 1.
- Kerner, Immo O. (1966). „Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen“. Numerische Mathematik. 8: 290–294. doi:10.1007 / BF02162564.
- Prešić, Marica (1980). "Věta o konvergenci pro metodu pro současné stanovení všech nul polynomu" (PDF). Publikace de l'Institut Mathématique. Nouvelle Série. 28 (42): 158–168.
- Petkovic, M.S., Carstensen, C. a Trajkovic, M. (1995). "Weierstrassův vzorec a metody hledání nuly". Numerische Mathematik. 69: 353–372. CiteSeerX 10.1.1.53.7516.CS1 maint: více jmen: seznam autorů (odkaz)
- Bo Jacoby, Nulpunkter pro polynomy, CAE-nyt (časopis pro Dansk CAE Gruppe [dánská skupina CAE]), 1988.
- Agnethe Knudsen, Numeriske Metoder (poznámky k přednášce), Københavns Teknikum.
- Bo Jacoby, Číselný kód ligninger„Bygningsstatiske meddelelser (Vydala Dánská společnost pro strukturní vědu a inženýrství) svazek 63 č. 3–4, 1992, s. 83–105.
- Gourdon, Xavier (1996). Combinatoire, Algorithmique et Geometrie des Polynomes. Paříž: École Polytechnique. Archivovány od originál dne 2006-10-28. Citováno 2006-08-22.
- Victor Pan (Květen 2002): Jednorozměrné hledání kořenů polynomů s nižší přesností výpočtu a vyššími rychlostmi konvergence. Technická zpráva, City University of New York
- Neumaier, Arnold (2003). „Uzavírací shluky nul polynomů“. Journal of Computational and Applied Mathematics. 156: 389. doi:10.1016 / S0377-0427 (03) 00380-7.
- Jan Verschelde, Metoda Weierstrass (také známá jako metoda Durand – Kerner), 2003.
- Bernhard Reinke, Dierk Schleicher a Michael Stoll, ``Vyhledávač kořenů Weierstrass není obecně konvergentní, 2020
externí odkazy
- Ada Generic_Roots pomocí metody Durand – Kerner - an open-source implementace v Ada
- Polynomiální kořeny - an open-source implementace v Jáva
- Extrakce kořenů z polynomů: metoda Durand – Kerner - obsahuje a Applet Java demonstrace