Представить многочлен в виде степени

Вычисление значений многочленов
    Займемся общим многочленом вида: p(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a2x2 + a1x + a0.    Мы будем предполагать, что все коэффициенты an, ..., a0 известны, постоянны и записаны в массив. Это означает, что единственным входным данным для вычисления многочлена служит значение 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*xPower
end for
return result

    Этот алгоритм совершенно прозрачен и его анализ очевиден. В цикле for содержится два умножения, которые выполняются n - 1 раз. Кроме того, одно умножение выполняется перед циклом, поэтому общее число умножений равно 2n - 1. В цикле выполняется также одно сложение, и одно сложение выполняется перед циклом, поэтому общее число сложений равно n.     Вычисление по схеме Горнера оказывается более эффективным, причем оно не очень усложняется. Эта схема основывается на следующем представлении многочлена: p(x) = (( ... ((anx + an-1)x + an-2)x + ... + a2)x + a1)x + a0.    Вы можете легко проверить, что это представление задает тот же многочлен, что и выше. Соответствующий алгоритм выглядит так:

Схема Горнера
HornersMethod(x)
x		точка, в которой вычисляется значение многочлена
for i = n - 1 down to 0 do
	result = result*x
	result = result + a
end for
return result
    Цикл выполняется n раз, причем внутри цикла есть одно умножение и одно сложение. Поэтому вычисление по схеме Горнера требует n умножениё и n сложений - двукратное уменьшение числа умножений по сравнению со стандартным алгоритмом. Предварительная обработка коэффициентов     Результат можно даже улучшить, если обработать коэффициенты многочлена до начала работы алгоритма. Основная идея состоит в том, чтобы выразить многочлен через многочлены меньшей степени. Например, для вычисления значения x256 можно воспользоваться таким же циклом, как и в функции Evaluate в начале этой статьи; в результате будет выполнено 255 умножений. Альтернативный подход состоит в том, чтобы положить result = x*x, а затем семь раз выполнить операцию result = result*result. После первого выполнения переменная result будет содержать x4, после второго x8, после третьего x16, после четвертого x32, после пятого x64, после шестого x128, и после седьмого x256.
    Для того, чтобы метод предварительной обработки коэффициентов работал, нужно, чтобы многочлен был унимодальным (то есть старший коэффициент an должен равняться 1) , а степень многочлена должна быть на единицу меньше некоторой степени двойки (n = 2k - 1 для некоторого k > 1). В таком случае многочлен можно представить в виде: p(x) = (xj + b)q(x) + r(x),      где j = 2k-1.     (1)     В обоих многочленах q и r будет вдвое меньше членов, чем в p. Для получения нужного результата мы вычислим по отдельности q(x) и r(x), а затем сделаем одно дополнительное умножение и два сложения. Если при этом правильно выбрать значение b, то оба многочлена q и r оказываются унимодальными, причем степень каждого из них позволяет применить к каждому из них ту же самую процедуру. Мы увидим, что ее последовательное применение позволяет сэкономить вычисления.
    Вместо того, чтобы вести речь о многочленах общего вида, обратимся к примеру. Рассмотрим многочлен: p(x) = x7 + 4x6 - 8x4 + 6x3 + 9x2 + 2x - 3.     Определим сначала множитель xj + b в уравнении (1). Степень многочлена p равна 7, то есть 23 - 1, поэтому k = 3. Отсюда вытекает, что j = 22 = 4. Выберем значение b таким образом, чтобы оба многочлена q и r были унимодальными. Для этого нужно посмотреть на коэффициенты aj-1 в p и положить b = aj-1 - 1. В нашем случае это означает, что b = a3 - 1 = 5. Теперь мы хотим найти значения q и r, удовлетворяющие уравнению: x7 + 4x6 - 8x4 + 6x3 + 9x2 + 2x - 3 = (x4 + 5)q(x) + r(x).     Многочлены q и r совпадают соответственно с частным и остатком от деления p на x4 + 5. Деление с остатком дает: p(x) = (x4 + 5)(x3 + 4x2 + 0x + 8) + (x3 - 11x2 + 2x - 37).     На следующем шаге мы можем применить ту же самую процедуру к каждому из многочленов q и r: q(x) = (x2 - 1)(x + 4) + (x + 12),    r(x) = (x2 + 1)(x - 11) + (x - 26).     В результате получаем: p(x) = (x4 + 5)((x2 - 1)(x + 4) + (x + 12)) + ((x2 + 1)(x - 11) + (x - 26)).     Посмотрев на этот многочлен, мы видим, что для вычисления x2 требуется одно умножение; еще одно умножение необходимо для подсчета x4 = x2*x2. Помимо этих двух умножений в вычислении правой части равенства участвуют еще три умножения. Кроме того, выполняется 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. Неучтенными, однако, остались умножения, необходимые для подсчета последовательности значений x2, x4, x8, ..., x2k-1; на это требуется дополнительно k - 1 умножение. Поэтому общее число умножений приблизительно равно N/2 + log2N.
Таблица 2. Число операций при вычислении значения многочлена степени N
Способ
Умножения
Сложения
Стандартный
2N - 1
N
Схема Горнера
N
N
Предварительная обработка
N/2 + log2N
(3N - 1)/2


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

Хотите получать самые актуальные новости сайта на свои мобильные устройства? Подписывайтесь на нас в Яндекс Дзен! 


Подпишитесь на канал «Женский журнал Судьба» @destinyrubot в Telegram: https://telegram.me/destinyrubot

Комментарии (0)

добавить комментарий

Добавить комментарий

показать все комментарии
Информация

Посетители, находящиеся в группе Гость, не могут оставлять комментарии к данной публикации.

Пожалуйста, авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий.