Schema lui Horner

Schema lui Horner (sau regula lui Horner , metoda lui Horner, metoda lui Ruffini-Horner ) este un algoritm de calcul al valorii unui polinom , scris ca o sumă de monomii (monoame), pentru o valoare dată a unei variabile. Metoda lui Horner vă permite să găsiți rădăcinile polinomului [1] , precum și să calculați derivatele polinomului la un punct dat. Schema lui Horner este, de asemenea, un algoritm simplu pentru împărțirea unui polinom într-un binom de forma . Metoda poartă numele lui William George Horner , cu toate acestea, Paolo Ruffini a fost cu 15 ani înaintea lui Horner, iar această metodă era cunoscută de chinezi încă din secolul al XIII-lea. $xc$

Descrierea algoritmului

Dat un polinom

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

Să fie necesar să se calculeze valoarea acestui polinom pentru o valoare fixă a . Reprezentăm polinomul sub următoarea 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 )).

Să definim următoarea secvență:

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

Valoarea dorită este . Să arătăm că așa este. $P(x_{0})$ $b_{0}$

Înlocuiți în notația rezultată și calculați valoarea expresiei, pornind de la parantezele interioare. Pentru a face acest lucru, vom înlocui subexpresiile prin : $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{aliniat}}

Folosind schema lui Horner pentru a împărți un polinom la un binom

La împărțirea unui polinom la , se obține un polinom cu rest (vezi teorema lui Bézout ). $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$

Mai mult, coeficienții polinomului rezultat satisfac relațiile recurente

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

În același mod, puteți determina multiplicitatea rădăcinilor (utilizați schema lui Horner pentru noul polinom). De asemenea, schema poate fi folosită pentru a găsi coeficienții în extinderea unui polinom în puteri : $(xc)$

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

Schema lui Horner poate fi folosită pentru a găsi derivate ale unui polinom:

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

Exemple de utilizare

Calculați pentru Folosind diviziunea sintetică: $f(x)=2x^{3}-6x^{2}+2x-1$ $x=3.$

x ₀│ x ³ x ² x ¹ x ⁰ 3 │ 2 −6 2 −1 │ 6 0 6 └── cameră Descărcați ── 2 0 2 5

Aici, prima linie conține valoarea și coeficienții polinomului. $x_{0}$

Valorile (pe coloane) din al treilea rând corespund sumei valorilor primului și celui de-al doilea rând ( ), iar valorile celui de-al doilea rând corespund produsului lui x și valoarea din al treilea rând al coloanei precedente ( ). $b_{n-1}=a_{n-1}+b_{n}x_{0}$ $b_{n}x_{0)$

De exemplu, dacă vedem că - valorile din al treilea rând. Deci diviziunea sintetică se bazează pe metoda lui Horner. $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$

Împărțiți la : $x^{3}-6x^{2}+11x-6$ $x-2$

2 │ 1 -6 11 -6 │ 2 −8 6 └── cameră Descărcați ── 1 −4 3 0

Polinom nou . $x^{2}-4x+3$

Lasă și . Împărțiți folosind metoda lui Horner. $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

A treia linie este suma primelor două împărțită la doi. Fiecare valoare din al doilea rând se potrivește cu valoarea din al treilea rând din coloana anterioară. Răspunsul diviziei:

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

De asemenea, folosind schema lui Horner, puteți calcula valoarea unui număr într-un calcul pozițional.

Note

↑ Dacă un polinom întreg are rădăcini întregi, atunci acestea se vor găsi printre divizorii termenului liber. Kurosh A. G. § 57. Rădăcini raționale ale polinoamelor întregi // Curs de algebră superioară . - Știința. - Moscova, 1968. Arhivat 18 octombrie 2013 la Wayback Machine

Vezi și

Literatură

Levitin A. V. Capitolul 6. Metoda de transformare: schema lui Horner și exponențierea // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 284-291. — 576 p. — ISBN 978-5-8459-0987-9
Volkov EA § 2. Calculul valorilor unui polinom. Schema lui Horner // Metode numerice. - Manual. indemnizație pentru universități. — Ed. a II-a, corectată. - M. : Nauka, 1987. - 248 p.
S. B. Gashkov. § 14. Schema lui Horner și translația dintr-un sistem pozițional în altul // Sisteme numerice și aplicarea lor . - M. : MTSNMO , 2004. - S. 37-39. - (Biblioteca „Educația matematică”). — ISBN 5-94057-146-8 .

Link -uri

Schema lui Horner
Calculul polinoamelor multivariate este o generalizare a schemei lui Horner pentru cazul unui polinom în mai multe variabile.
Metoda lui Horner într-un domeniu complex