Вычисление значений функций. Вычисление значений многочлена. Схема Горнера.

Пусть необходимо вычислить значение алгебраического многочлена

(5.1)

где (a ₀, a ₁, ¼, a_n - числовые коэффициенты, n – степень многочлена) при фиксированном x = с.

Поступим следующим образом. Найдем с помощью (п – 1) операций умножения значения степени с, т.е. с ², с ³, ¼, с^п. Затем в соответствии с (5.1) выполним еще по п операций умножения и сложения. Таким образом, для нахождения Р_п (с) в общем случае потребуется (3 п – 1) операций.

Однако более экономным путем вычислений оказывается следующий путь. Многочлен можно представить не в виде (5.1), а в виде

(5.2)

В этом случае вычисление состоит из последовательного нахождения величин:

(5.3)

Нетрудно посчитать, что данная последовательность вычислений состоит из п операций умножения и п операций сложения, т.е. всего из 2 п арифметических операций. Нет других способов нахождения значений многочленов при фиксированных х за меньшее число арифметических операций, чем 2 п. (При необходимости можно доказать). Описанный способ называется схемой Горнера.

Кроме уменьшения числа операций данная схема хороша еще тем, что благодаря цикличности вычислений при использовании ЭВМ требуется запоминание только одной промежуточной величины b_i или cb_i.

При ручных вычислениях также удобно пользоваться схемой Горнера. При этом обычно пользуются таблицей вида:

Таблица 5.1

Пример. Вычислить при х = -1, 5 значение многочлена.

Таблица 5.2

Решение.

При вычислении многочленов только с четными или только с нечетными показателями степеней х используются методы упрощения. Пусть n = 2 k (т.е. P_n (x) - четная функция) и , тогда его можно представить в виде

, (5.4)

Пусть теперь n = 2 k + 1, т.е. многочлен является нечетной функцией

Здесь P_n (x) надо представить в виде:

(5.5)

Соответственно, здесь таблица 5.1 будет выглядеть немного по-другому.