Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Экономичность вычислительного метода

Читайте также:
  1. Алгоритм венгерского метода
  2. Влияние выбора вычислительного алгоритма на результаты вычислений
  3. ИНФОРМАЦИОННО - ВЫЧИСЛИТЕЛЬНОГО) ЦЕНТРА 1 страница
  4. ИНФОРМАЦИОННО - ВЫЧИСЛИТЕЛЬНОГО) ЦЕНТРА 2 страница
  5. ИНФОРМАЦИОННО - ВЫЧИСЛИТЕЛЬНОГО) ЦЕНТРА 3 страница
  6. ИНФОРМАЦИОННО - ВЫЧИСЛИТЕЛЬНОГО) ЦЕНТРА 4 страница
  7. Нет такого метода, программы или методики, которые могут восполнить отсутствие любви к неверующим.

Пример 3.3.1 Пусть требуется вычислить сумму S = 1 + x + x2 + … + x1023 при 0 < x < 1. Для последовательного вычисления необходимо проделать 1022 умножения, а затем столько же сложений.

Однако если заметить, что

то количество арифметических действий значительно уменьшается; в частности, для вычисления x1024 требуется всего 10 умножений:

Пример 3.3.2 Вычисления значений многочленов. Если вычислять значение многочлена P(x) = a0 + a1x + a2x2 + … + anxn "в лоб", т.е. вычислять значения каждого члена и суммировать, то окажется, что необходимо выполнить (n2 + [n/2]) умножений и n сложений. Кроме того, такой способ вычислений может привести к накоплению ошибок округления при вычислениях с плавающей точкой.

Его очевидным улучшением является вычисление каждого члена последовательным умножением на x. Такой алгоритм требует (2n - 1) умножение и n сложений.

Еще более экономичным алгоритмом является хорошо известная в алгебре схема Горнера:

P(x) = ((...((anx + an - 1)x + an - 2)x + ... + a0),

требующая n операций сложения и n операций умножения. Этот метод был известен в средние века в Китае под названием Тянь-Юань и был заново открыт в Европе в начале XIX века англичанином Горнером и итальянцем Руффини.

Пример 3.3.3 Рассмотрим систему линейных алгебраических уравнений (СЛАУ) вида , с трехдиагональной матрицей

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


Дата добавления: 2015-09-06; просмотров: 36 | Нарушение авторских прав


Читайте в этой же книге: Представление целых чисел | Специфические особенности вычислительной математики | Обусловленность задачи |
<== предыдущая страница | следующая страница ==>
Влияние выбора вычислительного алгоритма на результаты вычислений| Погрешность метода

mybiblioteka.su - 2015-2018 год. (0.005 сек.)