Вычисление значения многочлена в точке — одна из простейших задач классического программирования.
При проведении различного рода вычислений часто приходится определять значения полиномов при заданных значениях аргументов.
Часто приближенное вычисление функций сводится к вычислению аппроксимирующих многочленов.
Среднестатистического читателя Хабрахабра нельзя назвать неопытным в использовании всяких извращений.
Каждый второй скажет, что полином нужно вычислять с помощью Правило Горнера .
Но всегда есть маленькое «но», всегда ли схема Горнера самая эффективная? 
Моя цель — не точно описать алгоритмы вычисления полиномов, а лишь показать, что в некоторых случаях можно (необходимо) применять схемы, отличные от правил Горнера.
Для тех, кому интересен материал, в конце статьи есть список литературы, к которой можно обратиться для более детального изучения вопроса.
Кроме того, иногда становится обидно, что имена наших российских математиков остаются малоизвестными.
Кроме того, мне просто приятно рассказывать о работе наших математиков.
Схема Горнера 
Правило Горнера стало очень широко использоваться при вычислении значений многочленов.
Метод назван в честь британского математика Уильяма Джорджа Хорнера.
В соответствии с этим правилом полином n-й степени имеет вид:
представлен в виде
Значение полинома вычисляется в порядке, указанном в скобках.
Что у нас есть? Чтобы оценить полином
по схеме Горнера необходимо произвести n умножений и n-k сложений (здесь k — число коэффициентов многочлена, равное 0).
Если
, то будет n-1 умножений.
Можно показать, что для вычисления полиномов общего вида невозможно построить более экономичную по числу операций схему, чем схема Горнера.
Наибольшая привлекательность схемы Горнера — простота алгоритма вычисления значения многочлена.
Исключения При вычислении полиномов специального вида может потребоваться меньше операций, чем при использовании универсальной схемы Горнера.
Например, вычисление степени
по схеме Горнера означает последовательное умножение n множителей и требует n-1 умножения.
Однако каждый первый читатель скажет, что для расчета, например,
нужно рассчитывать последовательно
,
,
, т.е.
выполнить всего 3 умножения вместо 7. Есть ли что-то еще, ведь схема Горнера самая экономичная? На самом деле все решает объем расчетов.
Если вам нужно вычислить одно значение многочлена, то ничего лучше схемы Горнера не придумано.
Но если значения многочлена вычисляются во многих точках, то появляется возможность сэкономить большое количество операций умножения за счет предварительных вычислений, выполняемых ровно один раз.
Это может значительно ускорить работу программы.
В некоторых случаях для получения полиномиальных значений целесообразно использовать двухэтапные схемы.
На первом этапе действия производятся только над коэффициентами многочлена; он преобразуется в специальную форму.
На втором этапе для заданных значений аргумента вычисляется значение самого полинома.
В этом случае может оказаться, что количество операций, выполняемых на втором этапе, будет меньше, чем при расчетах по схеме Горнера.
Еще раз отмечу, что подобные методы расчета уместны при вычислении значений многочлена
для большого количества значений x. Выигрыш получается за счет того, что первый этап для полинома выполняется только один раз.
Примером может служить вычисление элементарных функций, где аппроксимирующий полином готовится заранее.
В дальнейших обсуждениях, говоря о количестве операций по вычислению
, буду иметь в виду сложность второго этапа расчетов.
Схема Дж.
Тодта для полиномов 6-й степени
Имеем следующий полином:
Для расчетов мы используем следующие вспомогательные полиномы:
,
,
.
Шансы
определяются методом неопределенных коэффициентов исходя из условия
.
Из последнего условия составим систему уравнений, приравнивающую коэффициенты равных степеней многочленов.
Саму систему я здесь описывать не буду.
Но она легко решается методом замены, и в этом случае приходится решать квадратные уравнения.
Коэффициенты могут оказаться сложными, но если коэффициенты окажутся действительными, то для вычислений потребуется три умножения и семь сложений вместо пяти умножений и шести сложений по схеме Горнера.
Нет необходимости говорить об универсальности этой схемы, но читатель может ясно оценить сокращение количества операций по сравнению со схемой Горнера.
Схема Ю.
Л.
Кеткова 
Наконец-то я добрался до наших математиков.
Ю.
Л.
Кетков дал общее представление полинома n-й степени для n> 5, которое всегда приводит к вещественным выражениям и требует умножения [(n+1)/2]+[n/4] и сложения n+1 для вычисления полинома n-й степени.
.
Например, при n=2k схема Кеткова сводится к поиску многочленов:
Где
,
когда k четно, и
,
, если k нечетно (k> 2).
Все неизвестные коэффициенты находятся из равенства
.
В работах Кеткова дан метод решения результирующих систем, всегда дающий действительные коэффициенты.
.
Схемы В.
Я.
Пана 
?.
Белага в своих работах он дал строгое доказательство невозможности построения схемы вычисления произвольных многочленов n-й степени, используя на втором этапе менее чем [(n+1)/2]+1 умножений и n сложений.
В.
Я.
Пан работал над задачами оптимального расчета полиномов.
В частности, он предложил несколько схем вычисления действительных многочленов, которые очень близко подошли к оценкам ?.
Белаги.
Приведу некоторые схемы Пана для действительных многочленов.
1. Схема вычисления многочленов четвертой степени.
Учитывая полином
.
Давайте представим
как:
Где
2. Схема расчета
,
.
Построение вспомогательных полиномов
,
,
:
, s=1,2,…,k.
Для вычисления значения многочлена воспользуемся следующими выражениями:
, в
,
, в
,
, в
,
, в
,
Данная схема на втором этапе требует
умножение и
добавление.
Особенность этой схемы в том, что коэффициенты
всегда существовать, когда
и действительные коэффициенты исходного многочлена.
У В.
Я.
Пан существуют и другие схемы вычисления полиномов, в том числе комплексные.
Заключение Подводя итог сказанному, отмечу, что расчет одного или нескольких значений полинома, несомненно, должен осуществляться по схеме Горнера.
Однако если количество значений полиномов, которые необходимо вычислить, велико, а производительность очень важна, то имеет смысл рассмотреть возможность использования специальных методов расчета полиномов.
Некоторые читатели скажут, что возиться с другими схемами, кроме схемы Хорнера, сложно, утомительно и не стоит заморачиваться.
Однако в реальной жизни встречаются задачи, в которых нужно вычислить просто огромное количество значений многочленов больших степеней (например, их вычисление может занять месяцы), а уменьшение количества умножений вдвое даст существенный результат. выигрыш во времени, даже если вам придется потратить пару дней на реализацию конкретной схемы расчета полиномов.
Литература
- Кетков Ю.
Л.
Об одном способе вычисления полиномов на математических машинах.
// Новости вузов.
Радиофизика, вып.
1., № 4, 1958 г.
- В.
Я.
Пан, “Расчет полиномов с использованием схем с предварительной обработкой коэффициентов и программы автоматического поиска параметров”, Ж.
в.
Вычисл.
математика.
и математика.
Физ.
, 2:1 (1962), 133–140.
- В.
Я.
Пан, “О методах вычисления значений многочленов”, Успехи матем.
Наук, 21:1(127) (1966), 103–134
- В.
Я.
Пан, “О вычислении многочленов пятой и седьмой степени с действительными коэффициентами”, Ж.
вычисл.
Вычисл.
математика.
и математика.
Физ.
, 5:1 (1965), 116–118.
- Пан В.
Я.
Некоторые схемы вычисления значений многочленов с действительными коэффициентами.
Проблемы кибернетики.
Том.
5. М.
: Наука, 1961, 17–29.
- Белага?.
Д.
О вычислении значений многочлена от одной переменной с предварительной обработкой коэффициентов.
Проблемы кибернетики.
Том.
5. М.
: Физматгиз, 1961, 7–15.
-
Конкурс Разработчиков Rails-Ninja
19 Oct, 24 -
Камера В Помощь Маркетологу?
19 Oct, 24 -
Веб-Архив Для Evernote
19 Oct, 24 -
Выпущен Tizen Sdk Для Носимых Устройств
19 Oct, 24
