Схема на Хорнер за полиноми

Полиномите обикновено се записват във вида

$f(x)=\sum_{k=0}^{n} a_k x^k$

или, член по член,

$f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n,$

където реалните числа $a_0, a_1, \dots, a_n$ са коефициентите на полинома, а $x$ е променливата.

Когато ${a_n\ne 0},$ казваме, че полиномът е от $n$-та степен, т.е. ${\deg f(x)=n},$ където $n$ е най-високата степен на променливата.

Как работи схемата на Хорнер

Схемата на Хорнер (наричана още правило на Хорнер или метод на Хорнер) е алгоритъм, който улеснява намирането на стойността на полинома $f(x)$ при дадено ${x=x_0}.$ Полиномът се записва като верига от вложени един в друг изрази от първа степен. За всеки от тях са нужни най-много едно умножение и едно събиране, а резултатът от всяка стъпка се използва в следващата. Със същите пресмятания полиномът се дели на ${x-x_0},$ затова в англоезичната литература методът се нарича и синтетично деление.

За да обясним това, нека запишем стойността на полинома при $x_0$ в общия му вид:

$f(x_0)=a_0+a_1x_0+a_2x_0^2+\dots+a_nx_0^n$

Като изнасяме последователно $x_0$ пред скоби, получаваме записа

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+\dots+{x_0(a_{n-1}+a_nx_0)\dots)))}$

Алгоритъмът пресмята изразите в скобите един по един, като започва от най-вътрешните скоби и продължава към външните.

Стъпките са следните:

1. Полагаме ${k=n}.$
2. Полагаме ${b_k=a_k}.$
3. Пресмятаме ${b_{k-1}=a_{k-1}+x_0b_k}.$
4. Намаляваме $k$ с $1.$
5. Ако ${k\ge 1},$ връщаме се към стъпка 3; в противен случай спираме.

Последното получено число е стойността на полинома: ${b_0=f(x_0)}.$

Да вземем например полином от пета степен:

$f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5$

Стойността му при ${x=x_0}$ намираме, като го преобразуваме във вида

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+{x_0(a_4+a_5x_0))))}$

Стъпките на алгоритъма могат да се запишат в таблица:

$k$	$b_k$
$5$	${b_5=a_5}$
$4$	${b_4=a_4+x_0b_5}$
$3$	${b_3=a_3+x_0b_4}$
$2$	${b_2=a_2+x_0b_3}$
$1$	${b_1=a_1+x_0b_2}$
$0$	${b_0=a_0+x_0b_1}$

Пример. Намерете стойността на полинома ${f(x)=x^4+3x^3+5x^2+7x+9}$ при ${x=2}.$

Решение. Полиномът е от четвърта степен, затова ${n=4}.$ Тук ${x_0=2},$ а коефициентите са ${a_4=1},$ ${a_3=3},$ ${a_2=5},$ ${a_1=7}$ и ${a_0=9}.$

$k$	Стъпка	Резултат
$4$	${b_4=1}$	$1$
$3$	${b_3=3+2\cdot 1}$	$5$
$2$	${b_2=5+2\cdot 5}$	$15$
$1$	${b_1=7+2\cdot 15}$	$37$
$0$	${b_0=9+2\cdot 37}$	$83$

Следователно ${f(2)=83}.$

Схемата на Хорнер като таблица

На практика се записват само числата, в таблица с три реда. Тази таблица също се нарича схема на Хорнер. В първия ред са коефициентите на полинома, вляво стои числото $x_0,$ а третият ред се попълва отляво надясно:

$\begin{array}{c|cccc|c} & a_n & a_{n-1} & \cdots & a_1 & a_0 \\ x_0 & & x_0b_n & \cdots & x_0b_2 & x_0b_1 \\ \hline & b_n & b_{n-1} & \cdots & b_1 & b_0\end{array}$

1. В първия ред записваме коефициентите по намаляващите степени на $x.$ Ако някоя степен липсва, на нейното място пишем $0.$
2. Преписваме първия коефициент в третия ред: ${b_n=a_n}.$
3. Умножаваме току-що записаното число по $x_0$ и пишем произведението във втория ред на следващата колона.
4. Събираме двете числа в тази колона и записваме сбора под тях, в третия ред.
5. Повтаряме стъпки 3 и 4, докато попълним и последната колона.

За полинома ${x^4+3x^3+5x^2+7x+9}$ и ${x_0=2}$ от примера по-горе схемата изглежда така:

$\begin{array}{r|rrrr|r} & 1 & 3 & 5 & 7 & 9 \\ 2 & & 2 & 10 & 30 & 74 \\ \hline & 1 & 5 & 15 & 37 & 83\end{array}$

Последното число в третия ред е стойността на полинома: ${f(2)=83}.$

Деление на полином на двучлен от първа степен

Третият ред на схемата дава не само стойността $f(x_0).$

За проверка разкриваме скобите в дясната страна. Коефициентът пред $x^n$ е ${b_n=a_n},$ а коефициентът пред всяка по-ниска степен $x^k$ е ${b_k-x_0b_{k+1}},$ което е равно на $a_k,$ защото ${b_k=a_k+x_0b_{k+1}}.$

Ако в равенството положим ${x=x_0},$ отново получаваме ${f(x_0)=b_0}.$ Това е теоремата на Безу: остатъкът при деление на полинома $f(x)$ на ${x-x_0}$ е равен на $f(x_0).$

В примера по-горе третият ред е $1,$ $5,$ $15,$ $37$ и $83,$ затова частното е ${x^3+5x^2+15x+37},$ а остатъкът е $83$:

${x^4+3x^3+5x^2+7x+9}={(x-2)(x^3+5x^2+15x+37)}+83$

Пример. Разделете ${f(x)=2x^4-3x^2+5x-7}$ на ${x+2}.$

Решение. Тъй като ${x+2=x-(-2)},$ имаме ${x_0=-2}.$ В полинома няма член с $x^3,$ затова коефициентът пред $x^3$ е $0$ и първият ред е $2,$ $0,$ $-3,$ $5,$ $-7.$

$\begin{array}{r|rrrr|r} & 2 & 0 & -3 & 5 & -7 \\ -2 & & -4 & 8 & -10 & 10 \\ \hline & 2 & -4 & 5 & -5 & 3\end{array}$

Частното е ${2x^3-4x^2+5x-5},$ а остатъкът е $3$:

${2x^4-3x^2+5x-7}={(x+2)(2x^3-4x^2+5x-5)}+3$

Проверка с теоремата на Безу: ${f(-2)}={2\cdot 16-3\cdot 4+5\cdot(-2)-7}={32-12-10-7}={3}.$

Корени и разлагане на множители

Ако остатъкът $b_0$ е $0,$ то ${f(x_0)=0}.$ Числото $x_0$ е корен на полинома и полиномът се дели на ${x-x_0}$ без остатък:

$f(x)=(x-x_0)\,q(x)$

Затова схемата на Хорнер е удобна при разлагане на множители. Ако полином с цели коефициенти има цял корен, този корен е делител на свободния член $a_0.$ Проверяваме делителите на $a_0$ един по един, а схемата на Хорнер всеки път показва дали числото е корен и веднага дава частното. Ако последното число в третия ред не е $0,$ числото не е корен и проверяваме следващия делител.

Пример. Разложете на множители полинома ${x^3-6x^2+11x-6}.$

Решение. Делителите на свободния член са $\pm 1,$ $\pm 2,$ $\pm 3$ и $\pm 6.$ Започваме с ${x_0=1}$:

$\begin{array}{r|rrr|r} & 1 & -6 & 11 & -6 \\ 1 & & 1 & -5 & 6 \\ \hline & 1 & -5 & 6 & 0\end{array}$

Остатъкът е $0,$ значи $1$ е корен и ${x^3-6x^2+11x-6}={(x-1)(x^2-5x+6)}.$ Продължаваме с частното ${x^2-5x+6}$ и ${x_0=2}$:

$\begin{array}{r|rr|r} & 1 & -5 & 6 \\ 2 & & 2 & -6 \\ \hline & 1 & -3 & 0\end{array}$

Остатъкът отново е $0,$ затова ${x^2-5x+6}={(x-2)(x-3)}.$ Следователно

${x^3-6x^2+11x-6}={(x-1)(x-2)(x-3)}$

Рационалните корени се търсят по същия начин: ако несъкратимата дроб $\frac{p}{q}$ е корен на полином с цели коефициенти, то $p$ дели $a_0,$ а $q$ дели старшия коефициент $a_n.$

Повече за целите и рационалните корени има в урока Уравнения от по-висока степен.

Делител от вида mx + n

Със схемата на Хорнер можем да делим и на всеки полином от първа степен ${mx+n}.$ Коренът му е ${x_0=-\frac{n}{m}}$ и ${mx+n=m(x-x_0)},$ затова

$f(x)={(x-x_0)\,q(x)+b_0}={(mx+n)\cdot\frac{q(x)}{m}+b_0}$

Попълваме схемата за $x_0$ и след това делим коефициентите на частното на $m.$ Остатъкът не се променя.

Пример. Разделете ${3x^3-5x^2+2x+3}$ на ${2x-1}.$

Решение. Коренът на делителя е ${x_0=\frac12}.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 3 & -5 & 2 & 3 \\ \dfrac12 & & \dfrac32 & -\dfrac74 & \dfrac18 \\ \hline & 3 & -\dfrac72 & \dfrac14 & \dfrac{25}{8}\end{array}$

При деление на ${x-\frac12}$ частното е ${3x^2-\frac72x+\frac14},$ а остатъкът е $\frac{25}{8}.$ Делим коефициентите на частното на $2$:

${3x^3-5x^2+2x+3}={(2x-1)\left(\frac32x^2-\frac74x+\frac18\right)}+\frac{25}{8}$

Когато делителят е от втора или по-висока степен, прилагаме общия алгоритъм за деление на полиноми.

Защо да използваме схемата на Хорнер?

Обикновено намираме стойността на полином, като заместим променливата с даденото число и извършим пресмятанията. За целта можем да използваме или да напишем компютърна програма, а това става необходимо, когато работим със сложни полиноми от висока степен.

Начинът, по който компютърът решава една задача, зависи главно от това как вие като програмист му я описвате. Програмата може да пресмята стойността на полинома чрез директно заместване или по схемата на Хорнер. Единствената разлика между двата подхода е скоростта, с която компютърът стига до отговора.

Предимството на схемата на Хорнер е, че намалява броя на умноженията. При директно заместване, ако всяка степен се пресмята отначало, за члена $a_kx^k$ са нужни $k$ умножения, затова за полином от степен $n$ те са общо ${1+2+\dots+n}={\frac{n(n+1)}{2}}.$ Схемата на Хорнер изисква само $n$ умножения и $n$ събирания. За полином от десета степен това са $10$ умножения вместо $55.$ И при двата начина събиранията са $n,$ така че цялата икономия е в умноженията и при полиноми от висока степен програма, която използва схемата на Хорнер, работи значително по-бързо.

Упражнения

Решете задачите със схемата на Хорнер и след това отворете отговорите. Всяка стъпка можете да проверите и с калкулатора по-горе.

1. Намерете $f(3)$ за полинома ${f(x)=2x^3-5x^2+x-7}.$

$\begin{array}{r|rrr|r} & 2 & -5 & 1 & -7 \\ 3 & & 6 & 3 & 12 \\ \hline & 2 & 1 & 4 & 5\end{array}$

${f(3)=5}.$

2. Разделете ${x^4-2x^3+4x-5}$ на ${x-1}.$

Няма член с $x^2,$ затова първият ред е $1,$ $-2,$ $0,$ $4,$ $-5.$

$\begin{array}{r|rrrr|r} & 1 & -2 & 0 & 4 & -5 \\ 1 & & 1 & -1 & -1 & 3 \\ \hline & 1 & -1 & -1 & 3 & -2\end{array}$

Частното е ${x^3-x^2-x+3},$ а остатъкът е $-2.$

3. Намерете остатъка при делението на ${f(x)=x^5-3x^2+2}$ на ${x+1}.$

Тук ${x_0=-1},$ а първият ред е $1,$ $0,$ $0,$ $-3,$ $0,$ $2.$

$\begin{array}{r|rrrrr|r} & 1 & 0 & 0 & -3 & 0 & 2 \\ -1 & & -1 & 1 & -1 & 4 & -4 \\ \hline & 1 & -1 & 1 & -4 & 4 & -2\end{array}$

Остатъкът е $-2.$ Проверка: ${f(-1)}={-1-3+2}={-2}.$

4. Докажете, че $-2$ е корен на ${3x^3+7x^2-4},$ и разложете полинома на множители.

Няма член с $x,$ затова първият ред е $3,$ $7,$ $0,$ $-4.$

$\begin{array}{r|rrr|r} & 3 & 7 & 0 & -4 \\ -2 & & -6 & -2 & 4 \\ \hline & 3 & 1 & -2 & 0\end{array}$

Остатъкът е $0,$ значи $-2$ е корен и ${3x^3+7x^2-4}={(x+2)(3x^2+x-2)}.$ Корените на ${3x^2+x-2}$ са $-1$ и $\frac23,$ затова ${3x^3+7x^2-4}={(x+2)(x+1)(3x-2)}.$

5. Разделете ${4x^3-3x+5}$ на ${2x+1}.$

Тук ${x_0=-\frac12},$ а първият ред е $4,$ $0,$ $-3,$ $5.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 4 & 0 & -3 & 5 \\ -\dfrac12 & & -2 & 1 & 1 \\ \hline & 4 & -2 & -2 & 6\end{array}$

При деление на ${x+\frac12}$ частното е ${4x^2-2x-2},$ а остатъкът е $6.$ Като разделим коефициентите на частното на $2,$ получаваме ${4x^3-3x+5}={(2x+1)(2x^2-x-1)}+6.$