Lobachevsky-Greffe-metoden

Lobachevsky-Greffe-metoden är en effektiv algoritm för att hitta rötterna till ett polynom . Kallas ibland med upptäckarnas namn "The Lobachevsky-Greffe-Dandelin Method" eller "The Dandelin-Lobachevsky-Greffe Method".

Jämfört med andra algoritmer för att lösa samma problem (till exempel Newtons metod ) har denna metod flera fördelar. Det kräver inget förarbete för att ta reda på var rötterna är ungefär och hur många av dem som är komplexa - denna metod resulterar i alla verkliga rötter, och med viss modifiering, även komplexa.

Nackdelarna med metoden är bristen på samtidig kontroll av fel vid manuell räkning och svårigheten att bedöma resultatets riktighet. Metodens noggrannhet kan visa sig vara låg på grund av numerisk instabilitet, det vill säga den snabba ackumuleringen av fel under beräkningsförloppet [1] . Dessutom konvergerar metoden långsamt om polynomet har rötter som är lika eller mycket nära i absolut värde (till exempel +4 och -4) [2] .

Historik

Argument nära idén om denna metod uttrycktes redan på 1600-talet av Newton (i " Universal Arithmetic ") och Waring i "Analytiska etuder" [3] . Den första sammanfattningen av idén publicerades av den franske matematikern Germinal Dandelin 1826 [4] . Denna memoarbok gick obemärkt förbi. Åtta år senare presenterade och utvecklade N. I. Lobachevsky en liknande idé mer i detalj i sin lärobok Algebra or the Calculation of Finites (1834), men hans arbete väckte inte heller det vetenskapliga samfundets uppmärksamhet [5] .

1836 utlyste Berlins vetenskapsakademi en tävling för att utveckla en bekväm metod för att hitta de komplexa rötterna till ett polynom. Bland vinnarna fanns en artikel av den schweiziske professorn Carl Greffe " Die Auflösung der höheren numerischen Gleichungen " (1837). Greffe beskrev metoden i detalj, med många exempel. Senare förbättrades denna algoritm något av Johann Encke ( 1841) och Emmanuel Carvalho [ ).[6](1896) ”, 1924) [3] .

Motivering

Betrakta ett polynom av grad , vars rötter (hittills okänd) kommer att betecknas med : $n$ $p(x)$ $x_{1};\ x_{2}\cdots \ x_{n}$

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

Låt oss tillfälligt anta att alla rötter i detta polynom är reella och distinkta (det finns inga multipla rötter). Låt oss beteckna polynomet vars rötter är lika med kvadraterna på rötterna : $q(x)$ $p(x)$

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

Dess koefficienter kan beräknas enligt följande. För vi får: $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).

Om vi betecknar koefficienterna med respektive: $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},

då är koefficienterna för båda polynomen relaterade med formeln:

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

där det accepteras att vid eller $a_{\;j}^{0}=0$ $j<0$ $j>n,a_{\;0}^{0}=a_{\;0}^{1}=1.$

Upprepa denna procedur ett tillräckligt antal gånger, får vi ett polynom med en rot mycket större än de andra, en av de andra rötterna sticker också ut kraftigt i storlek, etc. kvadratiska förhållanden av koefficienterna för det föregående polynomet [7] .

Som ett resultat, i Vieta-formlerna för det sista polynomet : $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};\ \dots a_{\;n}^{k}=(-1)^{n }y_{1}y_{2}\cdots y_{n}.

alla monomialer, utom en, är försvinnande små i varje identitet, och Vieta-systemet reducerar till enkla linjära likheter [7] :

y_{1}\approx -a_{{\;1}}^{k},\;y_{2}\approx -a_{{\;2}}^{k}/a_{{\;1}} ^{k},\;\dots \;y_{n}\approx -a_{{\;n}}^{k}/a_{{\;n-1}}^{k}.

För att återgå till de ursprungliga okända , återstår det att extrahera från rötterna i motsvarande grad och välja tecken för de erhållna rötterna. För att bestämma tecknet kan du använda en grov substitution eller Vieta-formler. $x_k$ $y_{k}$

Med manuell räkning är det bekvämt att utföra alla beräkningar med en flyttal , separera mantissan och exponenten. Det rekommenderas ofta att de erhållna resultaten förfinas ytterligare (till exempel med Newtons metod ).

Applikation

Algoritmen som beskrivs ovan fungerar bäst för ekvationer vars rötter alla är reella (då är polynomets koefficienter också reella). Svårigheter uppstår om polynomet har flera rötter, så du bör bli av med dem innan användning. Standardproceduren för detta är följande. Vi hittar den största gemensamma divisorn för det ursprungliga polynomet och dess derivata . Om graden är större än noll bör metoden tillämpas på kvoten att dividera med (denna kvot har aldrig flera rötter). $d(x)$ $p(x)$ $p'(x)$ $d(x)$ $p(x)$ $d(x)$

Om y har komplexa rötter är metoden också tillämpbar, men inkluderar några komplikationer, detaljerade i litteraturen nedan. $p(x)$

Se även

Numerisk lösning av ekvationer

Litteratur

Berezin I. S. , Zhidkov N. P. Beräkningsmetoder. - M. : Fizmatlit, 1960. - T. 2. - S. 103-128. — 620 sid.
B. P. Demidovich , I. A. Maron, Grunderna för beräkningsmatematik. - Ed. 2:a. - M. : Fizmatlit, 1963. - S. 176-195. — 660 sid.
Lobachevsky N. I. Algebra or Finite Calculations, Poln. coll. soch., v. 4, M. - P., 1948.
Lobachevsky-metoden // Matematisk uppslagsverk (i 5 volymer). - M . : Soviet Encyclopedia , 1982. - T. 3.

Länkar

Brudno A. L. Lobachevskys metod .// Kvant. nr 4 (1989), sid. 51-53.
Weisstein, Eric W. Graeffe's Method (engelska) på Wolfram MathWorld- webbplatsen .
Modul för Graeffes metod av John H. Mathews

Anteckningar

↑ Encyclopedia of Mathematics, 1982 .
↑ Fundamentals of Computational Mathematics, 1963 , sid. 177-178..
↑ 1 2 Yushkevich A.P. , Bashmakova I.G. "Algebra or calculation of finite" av N.I. Lobachevsky // Historisk och matematisk forskning . - M. - L .: GITTL, 1949. - Nr 2 . - S. 126-127. .
↑ Dandelin, G. P. Recherches sur la résolution des equations numériques Arkiverad 14 augusti 2018 på Wayback Machine . Nouveaux mémoires de l'Académie Royale des Sciences et Belles-Lettres de Bruxelles (1826). Volym 3, sida 7.
↑ Läsare om matematikens historia. Aritmetik och algebra. Talteori. Geometri / Ed. A. P. Jusjkevitj . - M . : Utbildning, 1976. - S. 85-86. — 318 sid.
↑ Méthode pratique pour la résolution numérique complète des équations algébriques et transcendantes. Nony, Paris 1896, Arkiv .
↑ 1 2 Beräkningsmetoder, 1960 , sid. 103-105..