Навигация
Небольшие оптимизации для произведений многочленов
34976
знаков
0
таблиц
3
изображения
3.3 Небольшие оптимизации для произведений многочленов
В принципе вычисление произведения двух многочленов степеней n и m соответственно требует (n +1)( m +1) элементарных перемножений. Алгоритм оптимизации возведения в квадрат состоит просто в применении формулы квадрата суммы:
что даёт n +1 умножений для первого члена и n( n +1)/2 – для второго, или в целом (n +1)( n +2)/2 умножений, что близко к половине предусмотренных умножений, когда n большое.
Для произведения двух многочленов первой степени P = aX + b и Q = cX + d достаточно легко находим формулы U = ac, W = bd, V = (a + b)(c + d) и PQ = =UX2 + (V – U – W)X +W, в которых появляются только три элементарных умножения, но четыре сложения. Можно рекурсивно применить этот процесс для умножения двух многочленов P и Q степени 2l – 1, представляя их в виде и применяя предыдущие формулы для вычисления PQ в зависимости от A, B, C и D, где каждое произведение AB, CD и (A + B)(C + D) вычисляется с помощью рекурсивного применения данного метода (это метод Карацубы). Всё это даёт мультипликативную сложность M(2l) и аддитивную сложность A(2l) такие, что:
M(2l) = 3M(2l – 1),…, M(2) = 3M(1), M(1) = 1,
A(2l) = 3A(2l – 1) + 3*2l,…, A(2) = 3A(1) + 6, A(1) = 1.
В этой последней формуле член 3*2l представляет собой число элементарных сложений, необходимых, чтобы сделать два сложения многочленов степени 2l – 1 – 1 (a + b и c + d) и два вычитания многочленов степени 2l – 1 (U – V – W). Суммируя каждое из этих выражений, находим для n, являющегося степенью двойки:
M(n) = nlog3/log2 » n1,585 и A(2) =7 nlog3/log2 – 6n.
К сожалению, этот принцип остаётся теоретическим, и на его основе нужно построить итерационный алгоритм, чтобы получить разумную эффективность (цена управления рекурсией очень велика).
3.4 Вычисление многочленов
Рассмотрим общую задачу вычисления многочлена n-й степени
u(x) = unxn + un – 1xn – 1 + ... + u1x + u0, un ¹ 0, (1)
3.4.1 Схема Горнера
u(x) = (…(unx + un – 1)x + …)x + u0. (2)
Весь этот процесс требует n умножений и n сложений.
Было предложено несколько обобщений схемы Горнера. Посмотрим сначала, как вычисляется в случае, когда – комплексное число, а коэффициенты вещественны. Комплексное сложение и умножение можно очевидным образом свести к последовательности обычных операций над вещественными числами:
вещественное + комплексное требует 1 сложение,
комплексное + комплексное требует 2 сложения,
вещественное * комплексное требует 2 умножения,
комплексное * комплексное требует 4 умножения и 2 сложения
или 3 умножения и 5 сложений.
Следовательно, схема Горнера (2) требует 4n – 2 умножений и 3n – 2 сложений или 3n – 1 умножений и 6n – 5 сложений для вычисления u(z), когда z комплексное. Вот другая процедура для вычисления u(x + iy):
a1 = un, b1 = un – 1, r = x + x, s = x2 + y2; (3)
aj = bj – 1 + raj –1, bj = un – j – saj –1, 1 < j £ n.
Легко доказать индукцией по n, что u(z) = zan + bn. Эта схема требует 2n + 2 умножений и 2n + 1 сложений, так что при n ³ 3 она лучше схемы Горнера.
Рассмотрим процесс деления многочлена u(x) на многочлен x – x0. В результате такого деления мы получаем u(x) = (x – x0)q(x) + r(x); здесь deg(r) < 1, поэтому r(x) есть постоянная, не зависящая от x и u(x0) = 0*q(x0) + r = r. Анализ этого процесса деления показывает, что вычисления почти те же самые, что в схеме Горнера для определения u(x0). Аналогично, когда мы делим u(z) на многочлен (z – z0)(z – z0) = z2 – 2x0z + x02 + y02, то соответствующие вычисления эквивалентны процедуре (3); мы получаем
u(z) = (z – z0)(z – z0)q(z) + anz + bn;
следовательно,
u(z0) = anz0 + bn.
Вообще, когда мы делим u(x) на, f(x) получая u(x) = f(x) q(x) + r(x), то из равенства f(x0) = 0 следует u(x0) = r(x0); это наблюдение ведёт к дальнейшим обобщениям правила Горнера. Мы можем положить, например, f(x) = x2 – x02; это даст нам схему Горнера «второго порядка»
u(x) = (…(u2ën/2 û x2 + u2ën/2 û – 2)x2 + u0 +
+((….u2én/2 ù - 1 x2 + u2én/2 ù - 3)x2 + … +)x2u1)x. (4)
Похожие работы
... системам линейных алгебраических уравнений с более чем одной неизвестной; MATLAB решает такие уравнения без вычисле-ния обратной матрицы. Хотя это и не является стандартным математическим обозначением, система MATLAB использует терминологию, связанную с обычным делением в одномерном случае, для описания общего случая решения совместной системы нескольких линейных уравнений. Два символа деления / ...
... Writeln(‘Федеральное агентство по образованию'); GoToXY(22,3); Writeln('Тульский государственный университет'); GoToXY(28,4); Writeln('КАФЕДРА РАДИОЭЛЕКТРОНИКИ'); GoToXY(14,8); Writeln('Интерполяция функции одной переменной методом Ньютона.'); GoToXY(27,9); Writeln('Построение графика полинома.'); GoToXY(34,12); Writeln('Вариант #7'); GoToXY(24,17); Writeln('Студент гр. 220371 ...
... должны быть прямоугольными. 5. Полиномы По степени применимости, по разнообразию и качеству соответствующих команд скалярные полиномы – следующие за матрицами математические объекты в MATLAB'е. Полином p(x)=anxn+an-1xn-1+...+a0 задается вектором-строкой p из чисел an, an-1, ... , a0, т.е. коэффициентами, расположенными в порядке убывания показателя степени. Его степень n задавать не ...
... порядке); конструктор (создает объект и инициализирует его состояние); деструктор (разрушает объект и освобождает занимаемую им память). В чистых объектно-ориентированных языках программирования операции могут объявляться только как методы – элементы классов, экземплярами которых являются объекты. Гибридные языки позволяют писать операции как свободные подпрограммы (вне классов). В общем ...
0 комментариев