Вычислительный алгоритм
Вычисли́тельный алгори́тм, одно из основных понятий вычислительной математики, последовательность действий, которая, начиная с заданных исходных данных, за конечное число шагов приводит к искомому результату.
Простейшими примерами вычислительного алгоритма являются правила сложения, вычитания, умножения и деления. Под вычислительным алгоритмом часто также понимают последовательность инструкций (последовательность арифметических действий и условных операторов), которые могут быть однозначным образом реализованы в виде программы на вычислительной машине. Арифметическое выражение, как правило, не определяет однозначно вычислительный алгоритм, поскольку оно иногда допускает различный порядок выполнения операций, что для вычислительного алгоритма может оказаться существенным. Например, при вычислении суммы чисел вида от до на вычислительной машине с плавающей запятой существенным является порядок суммирования чисел. Результаты при прямом и обратном порядках суммирования отличаются друг от друга. Это связано с тем, что вычисления производятся с округлениями; при прямом порядке суммирования имеют место существенно бо́льшие округления и, соответственно, большее накопление погрешности округлений (см. также Компьютерная арифметика).
Вычислительный алгоритм должен удовлетворять некоторым необходимым требованиям. Наиболее важное из них – устойчивость. Это требование означает, что малым изменениям начальных данных и малым погрешностям округления должно соответствовать малое изменение результата выполнения алгоритма.
Предъявляются также требования к арифметической сложности вычислительного алгоритма – количеству элементарных операций, необходимых для его выполнения. В качестве примера можно привести вычисление выражения где и – квадратные матрицы размерности а – вектор размерности Приведённое выражение не определяет вычислительный алгоритм, поскольку не определён порядок действий. Выбор различных последовательностей операций приводит к двум алгоритмам и для первого из которых арифметическая сложность есть а для второго – Арифметическая сложность вычислительного алгоритма является одним из основных критериев его качества. В случае использования многопроцессорной техники и параллельных вычислений критерий качества вычислительного алгоритма меняется.