Horners plan

Horners schema (eller Horners regel, Horners metod , Ruffini-Horners metod ) är en algoritm för att beräkna värdet av ett polynom , skrivet som summan av monomer (monom), för ett givet värde av en variabel. Horners metod låter dig hitta rötterna till polynomet [1] , samt beräkna derivatorna av polynomet vid en given punkt. Horners schema är också en enkel algoritm för att dela upp ett polynom i ett binomium av formen . Metoden är uppkallad efter William George Horner , dock var Paolo Ruffini 15 år före Horner, och denna metod var känd för kineserna redan på 1200-talet. $xc$

Beskrivning av algoritmen

Givet ett polynom

P(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n}x^{n },\quad a_{i}\in \mathbb {R} .

Låt det krävas att beräkna värdet av detta polynom för ett fast värde på . Vi representerar polynomet i följande form: $x = x_0$ $P(x)$

P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots )).

Låt oss definiera följande sekvens:

b_{n}=a_{n},

b_{n-1}=a_{n-1}+b_{n}x_{0},

…

b_{i}=a_{i}+b_{i+1}x_{0},

…

b_{0}=a_{0}+b_{1}x_{0}.

Det önskade värdet är . Låt oss visa att det är så. $P(x_{0})$ $b_{0}$

Ersätt i den resulterande notationen och beräkna värdet på uttrycket, med början från de inre parenteserna. För att göra detta kommer vi att ersätta underuttryck genom : $P(x)$ $x = x_0$ $bi}$

{\begin{aligned}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}( a_{n-1}+a_{n}x_{0})\dots ))=\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+ \cdots x_{0}b_{n-1}\dots ))=\\&~~\vdots \\&=a_{0}+x_{0}b_{1}=\\&=b_{0} .\end{aligned}}

Använder Horners schema för att dividera ett polynom med ett binomial

När man dividerar ett polynom med , får man ett polynom med en rest (se Bézouts sats ). $a_{0}x^{n}+a_{1}x^{{n-1}}+\cdots +a_{{n-1}}x+a_{n}$ $xc$ $b_{0}x^{{n-1}}+b_{1}x^{{n-2}}+\cdots +b_{{n-2}}x+b_{{n-1}}$ $b_n$

Dessutom uppfyller koefficienterna för det resulterande polynomet de återkommande relationerna

b_{0}=a_{0},\quad b_{k}=a_{k}+cb_{k-1}.

På samma sätt kan du bestämma rötternas multiplicitet (använd Horners schema för det nya polynomet). Dessutom kan schemat användas för att hitta koefficienterna i expansionen av ett polynom i potenser : $(xc)$

P(x)=b_{n}+b_{n-1}(xc)+b_{n-2}(xc)^{2}+\cdots +b_{0}(xc)^{n }.

Horners schema kan användas för att hitta derivator av ett polynom:

P^{(k)}(c)=k!b_{nk}.

Användningsexempel

Beräkna för att använda syntetisk division: $f(x)=2x^{3}-6x^{2}+2x-1$ $x=3.$

x ₀│ x ³ x ² x ¹ x ⁰ 3 │ 2 −6 2 −1 │ 6 0 6 └───otter ── 2 0 2 5

Här innehåller den första raden värdet och koefficienterna för polynomet. $x_{0}$

Värdena (efter kolumner) i den tredje raden motsvarar summan av värdena på den första och andra raden ( ), och värdena på den andra raden motsvarar produkten av x och värdet i tredje raden i föregående kolumn ( ). ${\displaystyle b_{n-1}=a_{n-1}+b_{n}x_{0))$ ${\displaystyle b_{n}x_{0))$

Till exempel, om vi ser det - värdena i den tredje raden. Så syntetisk division bygger på Horners metod. $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$

Dela med : $x^{3}-6x^{2}+11x-6$ $x-2$

2 │ 1 -6 11 -6 │ 2 −8 6 └───otter ── 1 −4 3 0

Nytt polynom . $x^{2}-4x+3$

Låt och . Dela med hjälp av Horners metod. $f_{1}(x)=4x^{4}-6x^{3}+3x-5$ $f_{2}(x)=2x-1$ $f_1(x)$ $f_{2}\,(x)$

2 │ 4 -6 0 3 │ -5 ────┼───────────────────────────────── 1 │ 2 −2 −1 │ 1 └─────────────────────────────── 2 −2 −1 1 │ −4

Den tredje raden är summan av de två första dividerat med två. Varje värde i den andra raden matchar värdet i den tredje raden i föregående kolumn. Avdelningens svar:

{\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x -ett}}.

Med hjälp av Horners schema kan du också beräkna värdet på ett tal i en positionskalkyl.

Anteckningar

↑ Om ett heltalspolynom har heltalsrötter, kommer de att finnas bland divisorerna för den fria termen. Kurosh A. G. § 57. Rationella rötter av heltalspolynom // Course of Higher Algebra . - Vetenskapen. - Moskva, 1968. Arkiverad 18 oktober 2013 på Wayback Machine

Se även

Litteratur

Levitin A. V. Kapitel 6. Transformationsmetod: Horners schema och exponentiering // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 284-291. — 576 sid. — ISBN 978-5-8459-0987-9
Volkov EA § 2. Beräkning av värdena för ett polynom. Horners schema // Numeriska metoder. - Lärobok. ersättning för universitet. — 2:a uppl., rättad. - M. : Nauka, 1987. - 248 sid.
S. B. Gashkov. § 14. Horners schema och översättning från ett positionssystem till ett annat // Nummersystem och deras tillämpning . - M. : MTSNMO , 2004. - S. 37-39. - (Biblioteket "Matematisk utbildning"). — ISBN 5-94057-146-8 .

Länkar

Horners plan
Beräkning av multivariata polynom är en generalisering av Horners schema för fallet med ett polynom i flera variabler.
Horners metod inom ett komplext område