Вычисление значений многочленов

Вычисление значений многочленов

    Займемся общим многочленом вида:
p(x) = a_nxⁿ + a_n-1x^n-1 + a_n-2x^n-2 + ... + a₂x² + a₁x + a₀.     Мы будем предполагать, что все коэффициенты a_n, ..., a₀ известны, постоянны и записаны в массив. Это означает, что единственным входным данным для вычисления многочлена служит значение x, а результатом программы должно быть значение многочлена в точке x.
    Стандартный алгоритм вычисления прямолинеен:

Evaluate(x)
x		точка, в которой вычисляется значение многочлена
	  
result = a[0] + a[1]*x
xPower = x
for i = 2 to n do
	xPower = xPower*x
	result = result + a[i]*xPower
end for
return result

    Этот алгоритм совершенно прозрачен и его анализ очевиден. В цикле for содержится два умножения, которые выполняются n - 1 раз. Кроме того, одно умножение выполняется перед циклом, поэтому общее число умножений равно 2n - 1. В цикле выполняется также одно сложение, и одно сложение выполняется перед циклом, поэтому общее число сложений равно n.

Схема Горнера     Вычисление по схеме Горнера оказывается более эффективным, причем оно не очень усложняется. Эта схема основывается на следующем представлении многочлена:
p(x) = (( ... ((a_nx + a_n-1)x + a_n-2)x + ... + a₂)x + a₁)x + a₀.     Вы можете легко проверить, что это представление задает тот же многочлен, что и выше. Соответствующий алгоритм выглядит так:

HornersMethod(x)
x		точка, в которой вычисляется значение многочлена

for i = n - 1 down to 0 do
	result = result*x
	result = result + a[i]
end for
return result

    Цикл выполняется n раз, причем внутри цикла есть одно умножение и одно сложение. Поэтому вычисление по схеме Горнера требует n умножениё и n сложений - двукратное уменьшение числа умножений по сравнению со стандартным алгоритмом.

Предварительная обработка коэффициентов     Результат можно даже улучшить, если обработать коэффициенты многочлена до начала работы алгоритма. Основная идея состоит в том, чтобы выразить многочлен через многочлены меньшей степени. Например, для вычисления значения x²⁵⁶ можно воспользоваться таким же циклом, как и в функции Evaluate в начале этой статьи; в результате будет выполнено 255 умножений. Альтернативный подход состоит в том, чтобы положить result = x*x, а затем семь раз выполнить операцию result = result*result. После первого выполнения переменная result будет содержать x⁴, после второго x⁸, после третьего x¹⁶, после четвертого x³², после пятого x⁶⁴, после шестого x¹²⁸, и после седьмого x²⁵⁶.
    Для того, чтобы метод предварительной обработки коэффициентов работал, нужно, чтобы многочлен был унимодальным (то есть старший коэффициент a_n должен равняться 1) , а степень многочлена должна быть на единицу меньше некоторой степени двойки (n = 2^k - 1 для некоторого k > 1). В таком случае многочлен можно представить в виде: p(x) = (x^j + b)q(x) + r(x),      где j = 2^k-1.     (1)     В обоих многочленах q и r будет вдвое меньше членов, чем в p. Для получения нужного результата мы вычислим по отдельности q(x) и r(x), а затем сделаем одно дополнительное умножение и два сложения. Если при этом правильно выбрать значение b, то оба многочлена q и r оказываются унимодальными, причем степень каждого из них позволяет применить к каждому из них ту же самую процедуру. Мы увидим, что ее последовательное применение позволяет сэкономить вычисления.
    Вместо того, чтобы вести речь о многочленах общего вида, обратимся к примеру. Рассмотрим многочлен: p(x) = x⁷ + 4x⁶ - 8x⁴ + 6x³ + 9x² + 2x - 3.     Определим сначала множитель x^j + b в уравнении (1). Степень многочлена p равна 7, то есть 2³ - 1, поэтому k = 3. Отсюда вытекает, что j = 2² = 4. Выберем значение b таким образом, чтобы оба многочлена q и r были унимодальными. Для этого нужно посмотреть на коэффициенты a_j-1 в p и положить b = a_j-1 - 1. В нашем случае это означает, что b = a₃ - 1 = 5. Теперь мы хотим найти значения q и r, удовлетворяющие уравнению: x⁷ + 4x⁶ - 8x⁴ + 6x³ + 9x² + 2x - 3 = (x⁴ + 5)q(x) + r(x).     Многочлены q и r совпадают соответственно с частным и остатком от деления p на x⁴ + 5. Деление с остатком дает: p(x) = (x⁴ + 5)(x³ + 4x² + 0x + 8) + (x³ - 11x² + 2x - 37).     На следующем шаге мы можем применить ту же самую процедуру к каждому из многочленов q и r: q(x) = (x² - 1)(x + 4) + (x + 12),    r(x) = (x² + 1)(x - 11) + (x - 26).     В результате получаем: p(x) = (x⁴ + 5)((x² - 1)(x + 4) + (x + 12)) + ((x² + 1)(x - 11) + (x - 26)).     Посмотрев на этот многочлен, мы видим, что для вычисления x² требуется одно умножение; еще одно умножение необходимо для подсчета x⁴ = x²*x². Помимо этих двух умножений в вычислении правой части равенства участвуют еще три умножения. Кроме того, выполняется 10 операций сложения. В таблице 1 приведены сравнительные результаты анализа этого метода и других методов вычисления. Экономия не выглядит значительной, однако это объясняется тем, что мы рассматриваем лишь частный случай. Общую формулу для сложности можно вывести, внимательно изучив процедуру. Заметим прежде всего, что в равенстве (1) участвуют одно умножение и два сложения. Поэтому для числа умножений M = M(k) и числа сложений A = A(k) мы получаем следующий набор рекуррентных соотношений:

M(1) = 0	A(1) = 0
M(k) = 2M(k - 1) + 1 при k > 1	A(k) = 2A(k - 1) + 2 при k > 1.

Таблица 1. Число операций при вычислении значения многочлена степени 7

Способ	Умножения	Сложения
Стандартный	13	7
Схема Горнера	7	7
Предварительная обработка	5	10

Решая эти соотношения, мы заключаем, что число умножений приблизительно равно N/2, а число сложений приблизительно равно (3N - 1)/2. Неучтенными, однако, остались умножения, необходимые для подсчета последовательности значений x², x⁴, x⁸, ..., x^2k-1; на это требуется дополнительно k - 1 умножение. Поэтому общее число умножений приблизительно равно N/2 + log₂N.

Таблица 2. Число операций при вычислении значения многочлена степени N

Способ	Умножения	Сложения
Стандартный	2N - 1	N
Схема Горнера	N	N
Предварительная обработка	N/2 + log₂N	(3N - 1)/2

В таблице 2 приведены результаты сравнительного анализа стандартного алгоритма, схемы Горнера и алгоритма с предварительной обработкой коэффициентов. При сравнении последних двух алгоритмов видно, что нам удалось сэкономить N/2 - log₂N умножений, но за счет дополнительных (N - 1)/2 сложений. Во всех существующих вычислительных системах обмен умножений на сложения считается выгодным, поэтому предварительная обработка коэффициентов повышает эффективность.

Сайт управляется системой uCoz