Вычисление многочленов — от Ньютона до наших дней
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
µ число операций схемы Горнера равно 2n1).
Возьмём любую индивидуальную схему для конкретного многочлена степени n и заменим в ней все числа буквами b1, b2, ...; при этом получим схему, удовлетворяющую всем требованиям определения 6.
Пример. Схема многочлена (в) из 3 после замены чисел 1, 1 буквами b1, b2 превращается в схему p(x) = (xn+1 b1) : (x b2), представляющую все многочлены вида
f(x) = xn + axn1 + a2xn2 + ... + an1x + an
(при b1 = an+1, b2 = a) и только их.
После такой замены из всех сверхэкономных индивидуальных схем получится лишь конечное число разных схем (см. упражнение 6), каждая из которых представляет, согласно 9, лишь ничтожную часть многочленов степени n.
Итак, многочлены, которые могут быть вычислены быстрее, чем за Ѕ(n1) (Ч,:)-операций или n1 (+,)-операций, исключение из общего правила. Тем не менее, при построении схемы для конкретного многочлена стуит использовать его особенности, если они бросаются в глаза.
Примечания
1. Чтобы упростить выкладки, мы ограничимся многочленами с единичным коэффициентом при старшем члене (a0 = 1); там, где это будет необходимо, мы поясним, как поступать в общем случае (a0 ? 1). назад к тексту
2. Если a0 ? 1, то мы положим p1 = a0x + a1 (число умножений при этом возрастает на единицу). назад к тексту
3. Читается: плюс-минус-операции, умножить-разделить-операции. назад к тексту
4. Под формулой обычно понимают набор арифметических операций, корней, степеней. Вы, наверное, знаете, что Э.Галуа и Н.Абель, гениальные (и оба очень рано умершие) математики XIXвека, доказали, что для нахождения корней многочленов пятой и более высоких степеней таких общих формул не существует (см. Квант, 1973, №10, с.312). назад к тексту
5. Одно комплексное сложение это два действительных, одно комплексное умножение четыре(!) умножения и два сложения. назад к тексту
6. Чтобы иметь возможность сравнивать схемы, разумно для обозначения их параметров использовать буквы, например, из последовательности b1, b2, ..., bk, ...; понятно, что тогда схемы, отличающиеся лишь названиями параметров, считаются одинаковыми.
Список литературы
Для подготовки данной работы были использованы материалы с сайта