Вычисление значений многочлена

К задаче вычисления значения многочлена приводят многие задачи, Например, вычисление значений тригонометрических функций, которое осуществляется путем предварительного разложения функции в степенной ряд с последующим подсчетом усеченной суммы этого ряда (которая представляет из себя многочлен).

Общий вид многочлена:

 

 

Будем предполагать, что все коэффициенты известны и записаны в массив . Значение нужно вычислить в т. .

 

,

Для от 1 до

Конец цикла

Возврат

 

Вычислительная сложность – 3n.

 

Схема Горнера.

 

.

 

Для от до 0

Конец цикла

Возврат

 

Вычислительная сложность – 2n.

Предварительная обработка коэффициентов. Результат можно еще улучшить, если обработать коэффициенты до начала вычислений. Основная идея: выразить многочлен через многочлены меньшей степени. Например, для вычисления можно в цикле выполнить 255 умножений, а можно . Положим

- 7 раз

Для того, чтобы метод предварительной обработки коэффициентов работал, нужно, чтобы многочлен был унимодальным (т.е. ), а степень многочлена на 1 меньше некоторой степени двойки ( для некоторого ). Преимущества описываемого подхода могут оказаться настолько велики, что иногда стоит добавить к многочлену слагаемые, позволяющие его применить, а затем вычесть добавленные значения из окончательного результата. Например, если мы имеем дело с многочленом 30 степени, то нужно прибавить к нему , найти разложение, а затем вычесть из каждого результата вычисления. Алгоритм все равно будет работать быстрее остальных методов.

Многочлен представляется в виде: , где . В обоих многочленах будет вдвое меньше членов, чем в . Для получения нужного результата мы вычислим по отдельности , а затем сделаем одно дополнительное умножение и два сложения. Если при этом правильно выбрать значение , то оба многочлена оказываются унимодальными, причем степень каждого из них позволяет применить к каждому из них ту же самую процедуру. Ее последовательное применение позволяет сэкономить вычисления.

Рассмотрим пример: . Определим . Поскольку степень многочлена равна 7, то . Выберем значение таким образом, чтобы оба многочлена были унимодальными: . Для нашего примера . Теперь мы хотим найти , удовлетворяющие уравнению

 

.

 

Многочлены - это частное и остаток от деления на . Деление с остатком дает:

 

 

На следующем шаге мы можем применить ту же самую процедуру к каждому из многочленов :

 

;

 

В результате:

 

.

 

Для вычисления - одно умножение. Еще одно умножение для .

 

 

Способ Умножения Сложения

Стандартный 13 7

Схема Горнера 7 7

Предварительная обработка 5 10

 

Способ Умножения Сложения

Стандартный 2N-1 N

Схема Горнера N N

Предварительная обработка

 

В последнем алгоритме удалось сэкономить умножений за счет дополнительных сложений по сравнению со схемой Горнера. Во всех существующих вычислительных системах обмен умножений на сложения считается выгодным, поэтому предварительная обработка коэффициентов повышает эффективность.

 

Решение системы линейных алгебраических уравнений

Система уравнений с неизвестными: .

Один из способов решения СЛАУ – метод последовательной подстановки:

 

 

Такая процедура хорошо работает, но здесь производится очень много алгебраических преобразований, в которые легко может вкрастся ошибка. При возрастании числа уравнений и неизвестных время на выполнение этих преобразований быстро растет.

Метод Жордана-Гаусса. СЛАУ можно представить матрицей с строками и столбцами:

 

Со строками матрицы можно выполнить некоторые преобразовавния, которые приведут к следующему результату:

.

Пример.

.

 

Делим первую строку на ее первый элемент, затем подбираем для нее коэффициенты таким образом, чтобы при умножении на коэффициент и сложении с ккакой-либо из оставшихся строк элементы первого столбца обнулялись

 

.

 

Повторим эти действия для второй строки.

 

 

 

Для итерационных методов решения операций меньше, но нужно выполнить условия сходимости итерационного процесса. Рассмотрим метод простой итерации

Вопросы

1. Какие алгоритмы называются численными?
2. Схемы вычисления значения многочлена, их сравнение, преимущества и недостатки каждой.
3. Какие из арифметических операций являются предпочтительными при оценке вычислительной сложности алгоритма? Почему?
4. Методы решения систем линейных алгебраических уравнений, сравнение их вычислительных сложностей.

 

Литература

1. Деммель Дж. Вычислительная линейная алгебра / Дж.Деммель; пер.с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 430 с.
2. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.
3. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.

4. Воеводин В.В. Вычислительные основы линейной алгебры / В.В.Воеводин. — М.: Наука. Гл.ред.физ.-мат.лит., 1977. — 304 с.

Семестровий модуль 2. АНАЛИЗ ПОСЛЕДОВАТЕЛЬНЫХ АЛГОРИТМОВ ДЛЯ ИСПОЛЬЗОВАНИЯ В ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Лекция 8.Граф информационной зависимости реализации алгоритма – основной способ представления алгоритма для выявления внутреннего параллелизма

План