Вычисление значений полиномов по схеме Горнера

После построения аппроксимирующего полинома наступает этап работы с ним. И здесь важно уметь как можно экономичнее вычислять значение такого полинома для различных значений аргумента x=x.

На первый взгляд, наиболее естественный способ – провести n– 1 умножений, найдя степени x. Затем, выполнив еще n умножений и n сложений, получить P_n (x). Итого 3 n– 1 действий.

Другой способ, называемый схемой Горнера, состоит в перезаписи полинома в виде

P_n (x) = a ₀ + x (a ₁ + x (a ₂ +... + x (a_{n –2} + x (a_{n –1} + xa_n )) ...).

Эта запись легко программируется. Поиск P_n (x) организуется следующим способом:

b_n = a_n; b_{n –1} = a_{n –1} + x b_n; b_{n –2} = a_{n –2} + x b_{n –1} ;...

b ₁ = a ₁ + x b ₂; b ₀ = a ₀ + x b ₁ = P_n (x).

Этот способ реализуется за n умножений и n сложений, итого 2 n действий[2].

Он весьма экономичен при реализации на ЭВМ, т.к. в памяти необходимо хранить только коэффициенты а_к и одну промежуточную величину b.

Схема счета вручную очень наглядна и имеет вид:

а_n a_{n –1} a_{n –2} ... a ₀ x

+ x b_n x b_{n –1} ... x b ₁

b_n = a_n b_{n –1} b_{n –2} ... b ₀ = P_n (x).

Пример 1. Вычислить P ₃ = 6 x ³ – 47 x ² + 12 x + 27 при х= 8.

6 -47 12 27 8

+ 48 8 160

6 1 20 187 = P ₃(8).

Схему Горнера удобно применять для проведения замены х = у + x в полиномах P_n (x).

Известно, что всегда можно полином n -ой степени поделить на бином х–x, в общем случае с остатком, т.е.

P_n (x) = (b_n x^{n –1} + b_{n –1} x^{n –2} +... +b ₁)(x – x) + b ₀,

где, очевидно, b ₀ = P_n (x).

C другой стороны, если произвести в P_n (x) замену x = y + x, то, раскрыв скобки и сгруппировав подобные, получим:

P_n (y+x) = A_n yⁿ + A_{n –1} y^{n –1} +... + A ₁ y + A ₀ =

= (A_n y^{n –1} + A_{n –1} y^{n –2} +... + A ₁) y + A ₀.