Laguerres metod

I numerisk analys är Laguerres metod en rotsökningsalgoritm som är skräddarsydd för polynom . Med andra ord kan Laguerres metod användas för att numeriskt lösa ekvationen p ( x ) = 0 för ett givet polynom p ( x ) . En av de mest användbara egenskaperna hos denna metod är att den, från omfattande empiriska studier, är mycket nära att vara en "säker" metod, vilket innebär att den nästan garanterat alltid konvergerar till någon rot av polynomet, oavsett vad initial gissning är vald. För datorberäkning är dock mer effektiva metoder kända, med vilka man garanterat kan hitta alla rötter (se Root-finding-algoritmen § Rötter av polynom ) eller alla reella rötter (se Real-root-isolation ).

Denna metod är uppkallad efter Edmond Laguerre , en fransk matematiker.

Definition

Algoritmen för Laguerre-metoden för att hitta en rot av ett polynom p ( x ) av grad n är:

• Välj en första gissning x ₀
• För k = 0, 1, 2, …
  • Om $p(x_{k})$ är mycket liten, lämna loopen
  • Beräkna $G={\frac {p'(x_{k})}{p(x_{k})}}$
  • Beräkna $H=G^{2}-{\frac {p''(x_{k})}{p(x_{k}) }}$
  • Beräkna $a={\frac {n}{G\pm {\sqrt {(n-1)(nH-G^{2} )}}}}$ , där tecknet är valt för att ge nämnaren med det större absoluta värdet, för att undvika katastrofal annullering .
  • Ställ in $x_{k+1}=x_{k}-a$
• Upprepa tills a är tillräckligt liten eller om det maximala antalet iterationer har uppnåtts.

Om en rot har hittats kan motsvarande linjära faktor tas bort från p . Detta deflationssteg minskar graden av polynomet med ett, så att man till slut kan hitta approximationer för alla rötter av p . Observera dock att deflation kan leda till ungefärliga faktorer som skiljer sig väsentligt från motsvarande exakta faktorer. Detta fel är minst om rötterna hittas i storleksordningen av ökande storlek.

Härledning

Grundsatsen för algebra säger att varje n :e grads polynom $p$ kan skrivas i formen

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

så att $x_{k}$ där $(k=1,2,...,n)$ är polynomets rötter. Om vi ​​tar den naturliga logaritmen för båda sidor, finner vi det

$\ln |p(x)|=\ln |C|+\ln |x-x_{1}|+\ln |x-x_{2}|+\cdots +\ln |x-x_{ n}|.$

Beteckna derivatan med

$G={\frac {d}{dx}}\ln |p(x)|={\frac {1 }{x-x_{1}}}+{\frac {1}{x-x_{2}}}+\cdots +{\frac {1}{x-x_{n}}},$

och den negerade andraderivatan av

$H=-{\frac {d^{2}}{dx^{2}}}\ln |p(x)|={\frac {1}{(x-x_{1})^{ 2}}}+{\frac {1}{(x-x_{2})^{2}}}+\cdots +{\frac {1}{(x-x_{n})^{2}} }.$

Vi gör sedan vad Acton kallar en 'drastisk uppsättning antaganden', att roten vi letar efter, säg, $x_{1}$ är ett visst avstånd från vår gissning $x$ , och alla andra rötter är samlade en bit bort. Om vi ​​betecknar dessa avstånd med

$a=x-x_{1}\,$

och

$b=x-x_{i},\quad i=2,3,\ldots ,n$

då kan vår ekvation för $G$ skrivas som

$G={\frac {1}{a}}+{\frac {n-1}{b}}$

och uttrycket för $H$ blir

$H={\frac {1}{a^{2}}}+{\frac {n-1}{b^{2}}}.$

När vi löser dessa ekvationer för $a$ finner vi det

$a={\frac {n}{G\pm {\sqrt {(n-1)(nH-G^{2}) }}}}$ ,

där kvadratroten ur ett komplext tal väljs för att producera ett större absolutvärde av nämnaren, eller motsvarande, för att uppfylla:

$\operatorname {Re} \,({\overline {G}}{\sqrt {(n-1)(nH-G^ {2})}}\,)>0$ ,

där Re betecknar den reella delen av ett komplext tal, och G är det komplexa konjugatet av G ; eller

$a={ \frac {p(x)}{p'(x)}}\cdot \left({\frac {1}{n}}+{\frac {n-1}{n}}\,{\sqrt { 1-{\frac {n}{n-1}}\,{\frac {p(x)p''(x)}{p'(x)^{2}}}}}\right)^{ -1}$ ,

där kvadratroten ur ett komplext tal är vald att ha en icke-negativ reell del.

För små värden på p ( x ) skiljer sig denna formel från förskjutningen av tredje ordningens Halleys metod genom ett fel O ( p ( x ) ³ ) , så konvergens nära en rot kommer också att vara kubisk.

Observera att även om den "drastiska uppsättningen av antaganden" inte fungerar för ett visst polynom p ( x ) , kan p ( x ) omvandlas till ett relaterat polynom r för vilket antagandena är korrekta, t.ex. genom att flytta ursprunget mot ett lämpligt komplext tal w , vilket ger q ( x ) = p ( x − w ) , för att ge distinkta rötter distinkta storlekar vid behov (vilket det blir om vissa rötter är komplexa konjugat), och sedan få r från q ( x ) genom att upprepade gånger att tillämpa rotkvadreringstransformationen som används i Graeffes metod tillräckligt många gånger för att göra de mindre rötterna betydligt mindre än den största roten (och så, grupperade i jämförelse); den ungefärliga roten från Graeffes metod kan sedan användas för att starta den nya iterationen för Laguerres metod på r . En ungefärlig rot för p ( x ) kan då erhållas direkt från den för r .

Om vi ​​gör det starkare antagandet att termerna i G som motsvarar rötterna x _i , i = 2, 3, …, n är försumbart små i jämförelse med termen som motsvarar roten x ₁ , leder detta till Newtons metod .

Egenskaper

Attraktionszoner enligt Laguerres metod för polynom x^4 + 2*x^3 + 3*x^2 + 4*x + 1

Om x är en enkel rot av polynomet p ( x ) så konvergerar Laguerres metod kubiskt närhelst den initiala gissningen x ₀ är tillräckligt nära roten x . Å andra sidan, om x är en multipelrot är konvergensen endast linjär. Detta erhålls med påföljden att beräkna värden för polynomet och dess första och andra derivator i varje steg av iterationen.

En stor fördel med Laguerres metod är att den nästan garanterat konvergerar till någon rot av polynomet oavsett var den initiala approximationen väljs . Detta i motsats till andra metoder som Newton-Raphson-metoden som kanske misslyckas med att konvergera för dåligt valda initiala gissningar. Det kan till och med konvergera till en komplex rot av polynomet, eftersom kvadratroten som tas vid beräkningen av a ovan kan vara av ett negativt tal. Detta kan anses vara en fördel eller ett ansvar beroende på vilken applikation metoden används för. Empiriska bevis har visat att konvergensfel är extremt sällsynt, vilket gör detta till en bra kandidat för en generell polynomrotsökningsalgoritm. Men med tanke på den ganska begränsade teoretiska förståelsen av algoritmen är många numeriska analytiker tveksamma till att använda den som sådan, och föredrar bättre förstådda metoder som Jenkins– Traub-algoritmen , för vilken mer solid teori har utvecklats. Ändå är algoritmen ganska enkel att använda jämfört med dessa andra "säkra" metoder, lätt nog att användas för hand eller med hjälp av en fickkalkylator när en automatisk dator inte är tillgänglig. Den hastighet med vilken metoden konvergerar gör att man endast mycket sällan behöver beräkna mer än ett fåtal iterationer för att få hög noggrannhet.

•   Acton, Forman S. (1970). Numeriska metoder som fungerar . Harper & Row. ISBN 0-88385-450-3 .
• Goedecker, S. (1994). "Anmärkning om algoritmer för att hitta rötter till polynom". SIAM J. Sci. Comput . 15 (5): 1059–1063. doi : 10.1137/0915064 .
• Mekwi, Wankere R. (2001). "Iterativa metoder för rötter av polynom" . Magisteruppsats, University of Oxford . Arkiverad från originalet 2012-12-23.
• Pan, VY (1997). "Lösa en polynomekvation: lite historia och senaste framsteg". SIAM Rev. 39 (2): 187–220. doi : 10.1137/S0036144595288554 .
•   Tryck, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Avsnitt 9.5.3. Laguerres metod" . Numeriska recept: The Art of Scientific Computing (3:e upplagan). New York: Cambridge University Press. ISBN 978-0-521-88068-8 .
•   Ralston, Anthony; Rabinowitz, Philip (1978). En första kurs i numerisk analys . McGraw-Hill. ISBN 0-07-051158-6 .