Horners plan

Horners skema (eller Horners regel, Horners metode , Ruffini-Horners metode ) er en algoritme til at beregne værdien af et polynomium , skrevet som summen af monomer (monomier), for en given værdi af en variabel. Horners metode giver dig mulighed for at finde rødderne til polynomiet [1] , samt beregne afledte af polynomiet på et givet punkt. Horners skema er også en simpel algoritme til at dividere et polynomium i et binomium af formen . Metoden er opkaldt efter William George Horner , dog var Paolo Ruffini 15 år foran Horner, og denne metode var kendt af kineserne allerede i det 13. århundrede. $xc$

Beskrivelse af algoritmen

Givet et polynomium

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} .

Lad det være nødvendigt at beregne værdien af dette polynomium for en fast værdi på . Vi repræsenterer polynomiet i følgende 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 )).

Lad os definere følgende rækkefølge:

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}.

Den ønskede værdi er . Lad os vise, at det er sådan. $P(x_{0})$ $b_{0}$

Sæt ind i den resulterende notation og beregn værdien af udtrykket, startende fra de indre parenteser. For at gøre dette vil vi erstatte underudtryk gennem : $P(x)$ $x = x_0$ $b_{i}$

{\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}}

Brug af Horners skema til at dividere et polynomium med et binomium

Når man dividerer et polynomium med , får man et polynomium med en rest (se Bézouts sætning ). $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$

Desuden opfylder koefficienterne for det resulterende polynomium de tilbagevendende relationer

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

På samme måde kan du bestemme røddernes multiplicitet (brug Horners skema for det nye polynomium). Skemaet kan også bruges til at finde koefficienterne i udvidelsen af et polynomium i potenser : $(xc)$

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

Horners skema kan bruges til at finde afledte af et polynomium:

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

Eksempler på brug

Beregn for brug af 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 └──── den eptemeomtseskabelse ── 2 0 2 5

Her indeholder den første linje værdien og koefficienterne for polynomiet. $x_{0}$

Værdierne (efter kolonner) i tredje række svarer til summen af værdierne i første og anden række ( ), og værdierne i anden række svarer til produktet af x og værdien i tredje række i forrige kolonne ( ). $b_{n-1}=a_{n-1}+b_{n}x_{0}$ ${\displaystyle b_{n}x_{0))$

For eksempel, hvis vi ser det - værdierne i tredje række. Så syntetisk opdeling er baseret på Horners metode. $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$

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

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

Nyt polynomium . $x^{2}-4x+3$

Lad og . Opdel ved at bruge Horners metode. $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 linje er summen af de to første divideret med to. Hver værdi i den anden række matcher værdien i den tredje række i den forrige kolonne. Afdelingens svar:

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

Ved hjælp af Horners skema kan du også beregne værdien af et tal i en positionsberegning.

Noter

↑ Hvis et heltalspolynomium har heltalsrødder, vil de blive fundet blandt divisorerne i det frie led. Kurosh A. G. § 57. Rationelle rødder af heltalspolynomier // Forløb af højere algebra . - Videnskaben. - Moskva, 1968. Arkiveret 18. oktober 2013 på Wayback Machine

Se også

Litteratur

Levitin A. V. Kapitel 6. Transformationsmetode: Horners skema og eksponentiering // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 284-291. — 576 s. — ISBN 978-5-8459-0987-9
Volkov EA § 2. Beregning af værdierne af et polynomium. Horners skema // Numeriske metoder. - Lærebog. tilskud til universiteter. — 2. udg., rettet. - M. : Nauka, 1987. - 248 s.
S. B. Gashkov. § 14. Horners skema og oversættelse fra et positionssystem til et andet // Talsystemer og deres anvendelse . - M. : MTSNMO , 2004. - S. 37-39. - (Bibliotek "Matematisk Uddannelse"). — ISBN 5-94057-146-8 .