ВЫЧИСЛИТЕЛЬНЫЙ АЛГОРИТМ

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

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

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

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

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

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

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

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

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

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

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

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

При построении В. а. характерна тенденция к контролю точности. Контроль точности может косвенно осуществляться за счет увеличения устойчивости и порядка аппроксимации В. а., изменения параметров В. а. (внутренняя сходимость), сравнения двух численных решений одной и той же задачи, соответствующих различным В. а., применения тестов и т. д. Прямой контроль точности осуществляется в том случае, когда удается полупить двусторонние оценки (или, по крайней мере, односторонние оценки) результата вычислений. Теоретич. оценки такого рода не всегда возможны и эффективны, т. к. не всегда дают достаточно точные границы отклонения численного решения от точного. Получил распространение интервальный анализ, к-рый дает возможность в процессе вычислений строить доверительные границы для вычисляемых величин.

Различия в результатах абстрактного и реального В. а. определяются довольно сложными связями между их параметрами. Так, в абстрактном В. а. для сходящегося итерационного процесса точность ε, вообще говоря, тем больше, нем больше число итераций n. В случае реального В. а. эта ситуация может измениться вследствие влияния ошибок округления и, начиная с нек-рого момента, разность между n-й итерацией и тонным решением может потерять тенденцию к убыванию.

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

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

Н. Н. Яненко.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.