Lobachevsky-Greffe metode

Lobachevsky-Greffe-metoden er en effektiv algoritme til at finde rødderne til et polynomium . Nogle gange kaldet ved opdagernes navne "Lobachevsky-Greffe-Dandelin-metoden" eller "Dandelin-Lobachevsky-Greffe-metoden".

Sammenlignet med andre algoritmer til at løse det samme problem (for eksempel Newtons metode ) har denne metode flere fordele. Det kræver ikke forarbejde at finde ud af, hvor rødderne tilnærmelsesvis er, og hvor mange af dem, der er komplekse - denne metode resulterer i alle rigtige rødder, og med en vis modifikation også komplekse.

Ulemperne ved metoden er manglen på samtidig kontrol af fejl ved manuel optælling og vanskeligheden ved at vurdere nøjagtigheden af resultatet. Metodens nøjagtighed kan vise sig at være lav på grund af numerisk ustabilitet, det vil sige den hurtige akkumulering af fejl i løbet af beregninger [1] . Derudover konvergerer metoden langsomt, hvis polynomiet har rødder, der er lige store eller meget tæt på i absolut værdi (for eksempel +4 og -4) [2] .

Historie

Argumenter tæt på ideen om denne metode blev udtrykt tilbage i det 17. århundrede af Newton (i " Universal Arithmetic ") og Waring i "Analytiske Etuder" [3] . Det første resumé af ideen blev udgivet af den franske matematiker Germinal Dandelin i 1826 [4] . Denne erindringsbog gik ubemærket hen. Otte år senere fremsatte og udviklede N. I. Lobachevsky en lignende idé mere detaljeret i sin lærebog Algebra or the Calculation of Finites (1834), men hans arbejde tiltrak heller ikke det videnskabelige samfunds opmærksomhed [5] .

I 1836 annoncerede Berlins Videnskabsakademi en konkurrence for at udvikle en bekvem metode til at finde de komplekse rødder af et polynomium. Blandt vinderne var en artikel af den schweiziske professor Carl Greffe " Die Auflösung der höheren numerischen Gleichungen " (1837). Greffe skitserede metoden i detaljer med talrige eksempler. Senere blev denne algoritme en smule forbedret af Johann Encke ( 1841) og Emmanuel Carvalho [ ).[6](1896) ”, 1924) [3] .

Begrundelse

Overvej et polynomium af grad , hvis rødder (indtil videre ukendt) vil blive betegnet med : $n$ $p(x)$ $x_{1};\ x_{2}\cdots \ x_{n}$

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

Lad os midlertidigt antage, at alle rødder af dette polynomium er reelle og distinkte (der er ingen multiple rødder). Lad os betegne polynomiet, hvis rødder er lig med kvadraterne af rødderne : $q(x)$ $p(x)$

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

Dens koefficienter kan beregnes som følger. Fordi 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).

Hvis vi betegner koefficienterne med henholdsvis: $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},

så er koefficienterne for begge polynomier forbundet med formlen:

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

hvor det accepteres, at ved hhv $a_{\;j}^{0}=0$ $j<0$ $j>n,a_{\;0}^{0}=a_{\;0}^{1}=1.$

Ved at gentage denne procedure et tilstrækkeligt antal gange får vi et polynomium med en rod meget større end de andre, en af de andre rødder skiller sig også skarpt ud i størrelsen osv. kvadrerede forhold mellem koefficienterne for det forrige polynomium [7] .

Som et resultat, i Vieta-formlerne for det sidste polynomium : $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}.

alle monomialer, bortset fra én, er forsvindende små i hver identitet, og Vieta-systemet reducerer til simple lineære ligheder [7] :

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

For at vende tilbage til de oprindelige ukendte , er det fortsat at udtrække fra rødderne af den tilsvarende grad og vælge tegn for de opnåede rødder. For at bestemme tegnet kan du bruge en grov substitution eller Vieta-formler. $x_k$ $y_{k}$

Med manuel optælling er det praktisk at udføre alle beregninger med et flydende komma , der adskiller mantissen og eksponenten. Det anbefales ofte, at de opnåede resultater forfines yderligere (for eksempel ved Newtons metode ).

Ansøgning

Algoritmen beskrevet ovenfor fungerer bedst til ligninger, hvis rødder alle er reelle (så er polynomiets koefficienter også reelle). Der opstår vanskeligheder, hvis polynomiet har flere rødder, så du bør slippe af med dem før brug. Standardproceduren for dette er som følger. Vi finder den største fælles divisor for det oprindelige polynomium og dets afledte . Hvis graden er større end nul, skal metoden anvendes på kvotienten at dividere med (denne kvotient har aldrig flere rødder). $d(x)$ $p(x)$ $p'(x)$ $d(x)$ $p(x)$ $d(x)$

Hvis y har komplekse rødder, er metoden også anvendelig, men inkluderer nogle komplikationer, beskrevet i litteraturen nedenfor. $p(x)$

Se også

Numerisk løsning af ligninger

Litteratur

Berezin I. S. , Zhidkov N. P. Beregningsmetoder. - M. : Fizmatlit, 1960. - T. 2. - S. 103-128. — 620 s.
B. P. Demidovich , I. A. Maron, Fundamentals of Computational Mathematics. - Ed. 2. - M. : Fizmatlit, 1963. - S. 176-195. — 660 s.
Lobachevsky N. I. Algebra eller endelige beregninger, Poln. saml. soch., v. 4, M. - P., 1948.
Lobachevsky-metoden // Matematisk encyklopædi (i 5 bind). - M . : Soviet Encyclopedia , 1982. - T. 3.

Noter

↑ Encyclopedia of Mathematics, 1982 .
↑ Fundamentals of Computational Mathematics, 1963 , s. 177-178..
↑ 1 2 Yushkevich A.P. , Bashmakova I.G. "Algebra or calculation of finite" af N.I. Lobachevsky // Historisk og matematisk forskning . - M. - L .: GITTL, 1949. - Nr. 2 . - S. 126-127. .
↑ Dandelin, G. P. Recherches sur la résolution des equations numériques Arkiveret 14. august 2018 på Wayback Machine . Nouveaux mémoires de l'Académie Royale des Sciences et Belles-Lettres de Bruxelles (1826). Bind 3, side 7.
↑ Læser om matematikkens historie. Aritmetik og algebra. Talteori. Geometri / Udg. A. P. Yushkevich . - M . : Uddannelse, 1976. - S. 85-86. — 318 s.
↑ Méthode pratique pour la résolution numérique complète des equations algébriques et transcendantes. Nony, Paris 1896, Arkiv .
↑ 1 2 Beregningsmetoder, 1960 , s. 103-105..