Математическая энциклопедия - вычислительный алгоритм

точно определенное указание действий над данными, позволяющее с помощью цифровой вычислительной машины дискретного действия преобразовать за конечное количество операций нек-рый массив данных (входные данные) в другой массив данных (выходные данные). В. а. реализуется в виде вычислительного процесса, т. е. в виде дискретно распределенной во времени конечной последовательности состояний реальной ЭВМ, имеющей, в отличие от абстрактной вычислительной машины, ограниченные скорость выполнения операций, разрядность чисел и объем памяти.

При заданных ЭВМ и В. а. вычислительный процесс является строго детерминированным, т. е. заданным входным данным отвечают вполне определенным образом: последовательность операций ЭВМ; последовательность состояний ЭВМ; выходные данные. В. а. является линейным, если последовательность операций ЭВМ не зависит от входных данных, и нелинейным -в противном случае.

Объектом операций ЭВМ являются данные, представляемые в виде машинных слов, интерпретируемых как машинные числа, машинные команды и т. п. Машинные числа обычно составляют конечное ограниченное множество Мчисел, размещенных в машинном интервале [ А, А]и записанных в машинной разрядной сетке при заданном основании нек-рое натуральное число, А - наибольшее машинное число (машинная бесконечность). Как следствие, машинные числа имеют ограничение по числу значащих цифр и по абсолютной величине. Конкретная ЭВМ может оперировать с различными множествами М, соответствующими различным основаниям, разрядным сеткам и машинным интервалам.

Машинная команда есть машинное слово, к-рое содержит информацию об операции, напр, арифметической, и ее оперантах (объектах, над к-рыми производится операция, и результате операции). Арифметич. операция над парой машинных чисел может вывести результат из совокупности Мпо двум причинам: вследствие превышения допустимого числа значащих цифр; вследствие превышения допустимой величины машинного числа. В первом случае применяется операция округления, к-рая возвращает результат действия в множество М, но делает само действие приближенным и приводит к потере точности. Второй случай приводит к аварийной остановке ЭВМ (АВОСТ, или "аварийный останов").

Композиция арифметич. операции, примененной к паре машинных чисел, и операции округления называется кваз и операцией. Множество Мвместе с определенной над ним совокупностью квазиопераций образует замкнутую систему N, однако, в отличие от поля действительных чисел, Nне образует поля. Система Nзависит от выбора ЭВМ.

Реальный В. а. складывается из двух частей:

а) абстрактного (или собственно) В. а., к-рый применяется к математич. объектам (элементам конечномерных векторных пространств, полей, алгебраич. систем, функциональных пространств и т. д.), не связан с конкретной ЭВМ и может записываться в общепринятых математич. терминах или ча каком-либо алгоритмич. языке;

б) программы, т. е. совокупности машинных команд, описывающих В. а., к-рая организует реализацию вычислительного процесса в конкретной ЭВМ.

Первая часть В. а. является исходной и переходит во вторую часть с помощью различных методов программирования. В. а. содержит ряд управляющих параметров, к-рые остаются неопределенными в первой части и фиксируются в программе, полностью определяя вычислительный процесс, обеспечивая адаптацию его первой части к конкретной ЭВМ.

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

Помимо свойства точности, В. а. должен обладать свойством устойчивости. Устойчивость В. а. определяется как свойство В. а., позволяющее судить о скорости накопления суммарной вычислительной погрешности. Имеется градация устойчивости (соответственно неустойчивости), основанная на измерении исходной ошибки округления и суммарной вычислительной погрешности в различных нормах. В тех случаях, когда В. а. сводится к последовательности линейных рекуррентных соотношений, устойчивость В. а. определяется в терминах норм конечномерных матриц в конечномерных векторных пространствах. Свойство устойчивости определяется как структурой абстрактного В. а., так и влиянием ошибок округления. Так, устойчивость итерационного процесса xⁿ⁺¹=Anxⁿ+bn, где матрица А п также вычисляется, будет зависеть от влияния ошибок округления в коэффициентах матрицы на ее норму. Ошибки округления, входя в коэффициенты различных уравнений и операторов, вносят возмущения в математич. модель абстрактного В. а. и в этом смысле могут интерпретироваться так же, как и ошибки модели. Чем лучше свойства устойчивости абстрактного В. а., тем меньше, при заданном абстрактном В. а., результаты вычислений зависят от выбора ЭВМ и эквивалентных представлений абстрактного В. а.