Категория
Информатика
Тип
контрольная работа
Страницы
7 стр.
Дата
30.06.2013
Формат файла
.html — Html-документ
Архив
730986.zip — 4.42 kb
  • korrektirujushhie-kody-linejnye-gruppovye-kody-kod-xjemminga_730986_1.html — 21.76 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо



Текст работы

10. Алгоритм Горнера:


Произвольный полином степени N:


.


Представим полином p(z) в виде


.


Вычисление начнем с произведения , затем суммы , далее произведения и т.д. Метод Горнера требует не более N операций умножения и N операций сложения.

Пример: пусть дан полином p(z) степени


N = 4: p(z) = 4z4 - 2z3 + 3z2 + z - 5.

P (z) = (4z3 - 2z2 + 3z + 1)z - 5 = ((4z2 - 2z + 3)z + 1)z - 5 = (((4z - 2)z +

+ 3) z + 1)z - 5.


Пусть


z = -1: 4·z = 4·(-1) = -4, -4 - 2 = -6, -6·z = -6·(-1) = 6, 6 + 3 = 9, 9·z = 9·(-1)

= -9, -9 + 1 = -8, -8·z= = -8·(-1) = 8, 8 - 5 = 3.


Мультипликативная сложность = 4, аддитивная = 4. Если бы полином считался прямо, то мультипликативная сложность составила бы 6 операций.

Вычисление полинома в точках с помощью алгоритма «разделяй и властвуй»:

Пусть необходимо вычислить полином в нескольких точках а 1 , а 2 , …, а k , k ? N. Положим сначала

z = a 1 . Тогда можно записать


p(z) = (z - a 1 ) q(z) + r(z),


где q(z) и r(z) - частное и остаток от деления p(z) на (z - a 1 ). Этот результат можно распространить на большее число точек. Рассмотрим произведение и запишем p(z) = m(z) q(z) + r(z). В точке z = a i полином m(z) равен нулю, поэтому p(a i ) = r(a i ). Теперь вычисление полинома p(z) свелось к вычислению полинома r(z), степень которого меньше.

Этот подход можно использовать для построения алгоритма вычисления полинома степени N - 1 в N точках. Положим N = 2 l . Разделим N точек на две половины и образуем полиномы


и .


Разделим p(z) на m 1 (z) и m 2 (z). При этом получим остатки r 1 (z) и r 2 (z) степени N/2. Теперь осталось вычислить эти остатки в N/2 точках. Для вычисления остатков можно воспользоваться аналогичным приемом, повторяя его многократно.

Пример: Пусть требуется вычислить полином


p(z) = 4z 3 - 2z 2 - 2z + 1 в точках z, равных -2, 2, 1, -1.


Образуем


m 1 (z) = (z + 2)(z - 2) = z 2 - 4, m 2 (z) = (z - 1)(z + 1) = z 2 - 1


После деления p(z) на m 1 (z) и m 2 (z) получим остатки


r 1 (z) = 14z - 7, r 2 (z) = 2z - 1


Далее остатки следует поделить на соответствующие образующие части полиномов m 1 (z) и m 2 (z):


r 1 (z)/(z + 2) = -35 ? p(-2) = -35


Аналогично получим




Ваше мнение



CAPTCHA