Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






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




Пример 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.


mylektsii.ru - Мои Лекции - 2015-2017 год. (0.013 сек.)