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

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

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

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

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

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

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

P(x) = ((...((a_nx + a_{n - 1})x + a_{n - 2})x +... + a₀),

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

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

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

Дата добавления: 2015-09-06