Алгебра

Схема Горнера

Схема Горнера - способ деления многочлена
anxn + an-1xn-1 + an-2xn-2 + ... + a1x + a0   на бином   x - a.

Чтобы выполнить деление составляется таблица:

an an-1 an-2 ... a1 a0
a

В верхней строке выставляются коэффициенты исходного многочлена. В первой ячейке второй строки ставится число a. Во второй строке пишутся коэффициенты полученного многочлена, которые считаются так:

an an-1 an-2 ... a1 a0
a bn-1 bn-2 bn-3 ... b0 r

bn-1 = an
bn-2 = abn-1 + an-1
bn-3 = abn-2 + an-2
b0 = ab1 + a1
r (остаток от деления) = ab0 + a0

Таким образом можно деление превратить в сумму:

(anxn + an-1xn-1 + an-2xn-2 + ... + a1x + a0)/(x - a) = bn-1xn-1 + bn-2xn-2 + ... + b1x + b0 + r/(x - a)

Если r = 0, то исходный многочлен можно разложить на множители:

anxn + an-1xn-1 + an-2xn-2 + ... + a1x + a0 = (x - a)(bn-1xn-1 + bn-2xn-2 + ... + b1x + b0)

Применение схемы Горнера проще всего понять на примерах

Комментарии

comments powered by HyperComments