Алгоритм Вычислительный

АЛГОРИТМ ВЫЧИСЛИТЕЛЬНЫЙ одно из основных понятий вычислительной математики, последовательность действий, которая, начиная с заданных исходных данных, за конечное число шагов приводит к искомому результату.

Простейшими примерами алгоритма вычислительного  являются правила сложения, вычитания, умножения и деления. Под алгоритмом вычислительным  часто также понимают последовательность инструкций (последовательность арифметических действий и условных операторов), которые могут быть однозначным образом реализованы в виде программы на вычислительной машине. Арифметическое выражение, как правило, не определяет однозначно алгоритм вычислительный, поскольку оно иногда допускает различный порядок выполнения операций, что для алгоритма вычислительного  может оказаться существенным. Например, при вычислении суммы чисел вида n-2 от 1 до 1 000 000 на вычислительной машине с плавающей запятой существенным является порядок суммирования чисел. Результаты при прямом и обратном порядках суммирования отличаются друг от друга. Это связано с тем, что вычисления производятся с округлениями; при прямом порядке суммирования имеют место существенно большие округления и, соответственно, большее накопление погрешности округлений.

Реклама

Алгоритм вычислительный  должен удовлетворять некоторым необходимым требованиям. Наиболее важное из них - устойчивость. Это требование означает, что малым изменениям начальных данных и малым погрешностям округления должно соответствовать малое изменение результата выполнения алгоритма.

Предъявляются также требования к арифметической сложности алгоритма вычислительного  - количеству элементарных операций, необходимых для его выполнения. В качестве примера можно привести вычисление выражения АВх, где А и В - квадратные матрицы размерности n х n, а х вектор размерности n. Приведённое выражение не определяет алгоритм вычислительный, поскольку не определён порядок действий. Выбор различных последовательностей операций приводит к двум алгоритмам А(Вх) и (АВ)х, для первого из которых арифметическая сложность есть 0(n2), а для второго - 0(n3). Арифметическая сложность алгоритма вычислительного  является одним из основных критериев его качества. В случае использования многопроцессорной техники и параллельных вычислений критерий качества алгоритма вычислительного  меняется.

Лит.: Кнут Д. Искусство программирования. Основные алгоритмы. М. и др., 2000. Т. 1; Воеводин В. В. Параллельные вычисления. СПб., 2002.   

Г.  М. Кобельков.

Связанные статьи