Lobačevského-Greffeova metoda

Lobachevského-Greffeova metoda je účinný algoritmus pro hledání kořenů polynomu . Někdy nazývané jmény objevitelů „Metoda Lobačevského-Greffe-Dandelina“ nebo „Metoda Dandelin-Lobačevského-Greffe“.

Ve srovnání s jinými algoritmy pro řešení stejného problému (např. Newtonova metoda ) má tato metoda několik výhod. Zjištění, kde přibližně kořeny jsou a kolik z nich je složitých , nevyžaduje předběžnou práci – výsledkem této metody jsou všechny skutečné kořeny a s určitou úpravou i složité.

Nevýhodami metody je absence souběžné kontroly chyb při ručním počítání a obtížnost posouzení správnosti výsledku. Přesnost metody se může ukázat jako nízká kvůli numerické nestabilitě, tedy rychlému hromadění chyb v průběhu výpočtů [1] . Navíc metoda konverguje pomalu, pokud má polynom kořeny, které jsou stejné nebo velmi blízké v absolutní hodnotě (například +4 a -4) [2] .

Historie

Argumenty blízké myšlence této metody vyjádřili již v 17. století Newton (v „ Universal Aritmetic “) a Waring v „Analytical Etudes“ [3] . První shrnutí myšlenky publikoval francouzský matematik Germinal Dandelin v roce 1826 [4] . Tato monografie zůstala bez povšimnutí. O osm let později podobnou myšlenku prosadil a podrobněji rozvinul N. I. Lobačevskij ve své učebnici Algebra aneb výpočet konečných (1834), ale ani jeho práce nevzbudila pozornost vědecké komunity [5] .

V roce 1836 vyhlásila Berlínská akademie věd soutěž na vývoj vhodné metody pro nalezení komplexních kořenů polynomu. Mezi oceněnými byl i článek švýcarského profesora Carla Greffe „ Die Auflösung der höheren numerischen Gleichungen “ (1837). Greffe podrobně nastínil metodu s četnými příklady. Později tento algoritmus poněkud vylepšili Johann Encke ( 1841) a Emmanuel Carvalho [ 6[(1896) ] ) .

Odůvodnění

Uvažujme polynom stupně , jehož kořeny (zatím neznámé) budou označeny : $n$ $p(x)$ $x_{1};\ x_{2}\cdots \ x_{n}$

p(x)=(x-x_{1})(x-x_{2})\cdots (x-x_{n})

Předpokládejme dočasně, že všechny kořeny tohoto polynomu jsou reálné a odlišné (neexistují žádné vícenásobné kořeny). Označme polynom, jehož kořeny se rovnají čtvercům odmocnin : $q(x)$ $p(x)$

q(x)=(x-x_{1}^{2})(x-x_{2}^{2})\cdots (x-x_{n}^{2}).

Jeho koeficienty lze vypočítat následovně. Protože dostáváme: $x^{2}-x_{k}^{2}=(x-x_{k})(x+x_{k}),$

q(x^{2})=(x^{2}-x_{1}^{2})(x^{2}-x_{2}^{2})\cdots (x^{ 2}-x_{n}^{2})=(-1)^{n}\,p(x)p(-x).

Označíme-li koeficienty příslušně : $p(x),q(x)$ ${\displaystyle a_{k}=a_{\;k}^{0},a_{\;k}^{1))$

p(x)=x^{n}+a_{\;1}^{0}x^{n-1}+\cdots +a_{\;n-1}^{0}x+a_ {\;n}^{0},

q(x)=x^{n}+a_{\;1}^{1}x^{n-1}+\cdots +a_{\;n-1}^{1}x+a_ {\;n}^{1},

pak koeficienty obou polynomů souvisí vzorcem:

a_{\;k}^{1}=(-1)^{k}\,(a_{\;k}^{0})^{2}+2\sum _{j=1} ^{k}(-1)^{j}\,a_{\;kj}^{0}a_{\;k+j}^{0},

kde se připouští, že při nebo $a_{\;j}^{0}=0$ $j<0$ $j>n,a_{\;0}^{0}=a_{\;0}^{1}=1.$

Opakováním tohoto postupu dostatečným počtem opakování dostaneme polynom s jedním kořenem mnohem větším než ostatní, jeden z ostatních kořenů také ostře vyčnívá ve velikosti atd. čtvercové poměry koeficientů předchozího polynomu [7] .

Výsledkem je, že ve vzorcích Vieta pro poslední polynom : $q(y)$

a_{\;1}^{k}=-(y_{1}+y_{2}+\cdots +y_{n});\ a_{\;2}^{k}=y_{1 }y_{2}+y_{1}y_{3}+\cdots +y_{n-1}y_{n};\ \tečky a_{\;n}^{k}=(-1)^{n }y_{1}y_{2}\cdots y_{n}.

všechny monomiály, kromě jednoho, jsou v každé identitě mizející malé a systém Vieta se redukuje na jednoduché lineární rovnosti [7] :

y_{1}\přibližně -a_{{\;1}}^{k},\;y_{2}\přibližně -a_{{\;2}}^{k}/a_{{\;1}} ^{k},\;\tečky \;y_{n}\přibližně -a_{{\;n}}^{k}/a_{{\;n-1}}^{k}.

Pro návrat k původním neznámým zbývá extrahovat z kořenů odpovídajícího stupně a vybrat znaménka pro získané kořeny. K určení znaménka můžete použít hrubou substituci nebo vzorce Vieta. $x_k$ $y_{k}$

Při ručním počítání je vhodné provádět všechny výpočty s plovoucí desetinnou čárkou , oddělující mantisu a exponent. Často se doporučuje získané výsledky dále zpřesnit (například Newtonovou metodou ).

Aplikace

Algoritmus popsaný výše funguje nejlépe pro rovnice, jejichž kořeny jsou všechny reálné (pak jsou reálné i koeficienty polynomu). Potíže nastávají, pokud má polynom více kořenů, takže byste se jich měli před použitím zbavit. Standardní postup je následující. Najdeme největšího společného dělitele pro původní polynom a jeho derivaci . Pokud je stupeň větší než nula, měla by být metoda aplikována na podíl dělení ( tento podíl nikdy nemá více kořenů). $d(x)$ $p(x)$ $p'(x)$ $d(x)$ $p(x)$ $d(x)$

Pokud má y komplexní kořeny, je metoda také použitelná, ale zahrnuje některé komplikace, podrobně popsané v literatuře níže. $p(x)$

Viz také

Numerické řešení rovnic

Literatura

Berezin I. S. , Zhidkov N. P. Výpočtové metody. - M. : Fizmatlit, 1960. - T. 2. - S. 103-128. — 620 str.
B. P. Demidovich , I. A. Maron, Základy výpočetní matematiky. - Ed. 2. - M. : Fizmatlit, 1963. - S. 176-195. — 660 s.
Lobačevskij N. I. Algebra nebo konečné výpočty, Poln. kol. soch., v. 4, M. - P., 1948.
Lobačevského metoda // Matematická encyklopedie (v 5 svazcích). - M . : Sovětská encyklopedie , 1982. - T. 3.

Odkazy

Metoda Brudna A. L. Lobačevského .// Kvant. č. 4 (1989), str. 51-53.
Weisstein, Eric W. Graeffe's Method (anglicky) na webových stránkách Wolfram MathWorld .
Modul pro Graeffeovu metodu od Johna H. Mathewse

Poznámky

↑ Encyklopedie matematiky, 1982 .
↑ Základy výpočetní matematiky, 1963 , str. 177-178..
↑ 1 2 Yushkevich A.P. , Bashmakova I.G. "Algebra nebo výpočet konečných" od N.I. Lobačevského // Historický a matematický výzkum . - M. - L .: GITTL, 1949. - č. 2 . - S. 126-127. .
↑ Dandelin, G. P. Recherches sur la résolution des équations numériques Archivováno 14. srpna 2018 na Wayback Machine . Nouveaux mémoires de l'Académie Royale des Sciences et Belles-Lettres de Bruxelles (1826). Svazek 3, strana 7.
↑ Čítanka o dějinách matematiky. Aritmetika a algebra. Teorie čísel. Geometrie / Ed. A. P. Juškevič . - M . : Vzdělávání, 1976. - S. 85-86. — 318 s.
↑ Metoda pratique pour la résolution numérique complète des équations algébriques et transcendantes. Nony, Paříž 1896, Archiv .
↑ 1 2 Metody výpočtu, 1960 , s. 103-105..