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

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

В. а. х., зависящие от особенностей ВМ, в частности, сложившиеся в практике числ. решения задач прикладной математики. Такие в. а. будем отождествлять с программой на ВМ.

Пусть в. а. А (X) предназначены для решения задач Р (У) на ВМ С (Z). Здесь X, У, Z — конечные мн-ва (векторы) параметров, от которых существенно зависят соотв. А, Р, С. Среди компонент X могут быть числа итераций, степени аппроксимаций, порядки выполнения последовательности операций и т. п. В число компонент Y могут входить данные об априорных свойствах решений рассматриваемых задач, напр., константы, ограничивающие значения ряда производных от искомых ф-ций, данные о точности задания исходных величин и т. п. Вектор Z может содержать к-во разрядов ячеек памяти ВМ, общее к-во ячеек памяти, среднее время бессбойной работы, времена выполнения и др. параметры для всех операций ВМ. Важное значение на практике имеют следующие характеристики в. а., задач и ВМ: Т (X, Y, Z) — общее время, необходимое для реализации в. а. А при решении задачи Р на ВМ С; М (X, Y, Z) — необходимая память ВМ; Е (X, У, Z) — полная абс. погрешность решения задачи Р на ВМ С в. коэфф. технико-экономической эффективности. Дадим объяснение введенных характеристик. Общее время Т — отрезок времени от постановки задачи Р (Y) до ее решения в. а. А (X) на ВМ С (Z). Можно положить где время разработки или выбора в. а. время программирования и трансляции в. а. А и время реализации в. а. А на ВМ С. При известных наборе операций ВМ С и значении вектора в котором время выполнения операции на ВМ С, искомое время где операций при реализации в. а. А на ВМ С. На практике при оценке нередко учитывают лишь основные по и времени выполнения операции ВМ; при этом учитываемые операции приводят к одной стандартной операции (обычно операции сложения) или средней по времени (для арифм. операций).

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

Пусть решением задачи Р является элемент R пространства абстрактного Q с метрикой и пусть конечномерный вектор R является результатом реализации в. а. А на ВМ С при

решении задачи Р. Обозначим через интерпретатор . Тогда

где решение той же или регуляризованной задачи с прибл. входными данными, результат применения в. а. А к решению этой задачи. Первое слагаемое в оценке Е обозначает погр. за счет неточности исходных данных, второе — погрешность в. а., а третье — погр. в результате реализации в. а. на ВМ.

Одной из интерпретаций показателя является прибыль G (X, У, Z) на единицу затрат W (X, У, Z) от решения задачи Р на ВМ . В свою очередь, где стоимость единицы времени , где S — доход от решения задачи Р на ВМ С в. а. А. Таким образом,

Доход S зависит от погр. решения задачи. Одной из простейших моделей математических S может быть , где вещественные константы.

Допустим, что ВМ С (Z) фиксирована. Тогда Т, М, Е и зависят лишь от X и Y. Удобно считать Y случайной величиной и говорить о различных вероятностных характеристиках величины Т, М, Е и которые также будут характеристиками в. а. А и будут зависеть лишь от X. Обозначим через любую из характеристик и через — плотности распределения соотв. У и Я. Важными характеристиками в. а. А (X) являются математические ожидания Мн (X) и дисперсии DH (X):

где D — область возможных значений У. Нередко на практике применяется т. н. мажорантная характеристика в. а. . Показатель и его вероятностные характеристики являются примерами целевых функционалов , минимизация которых по X с учетом необходимых ограничений на Т, М и Е дает в идеальных условиях оптимизацию в. а. В действительности вместо Т, М, Е и а будем иметь лишь некоторые их оценки и сравнивать в. а. в соответствии с теорией статистических решений можно будет лишь на основании значений некоторой ф-ции риска , где — т. н. ф-ция потерь, , с учетом X всех необходимых ограничений. Для любых двух в. будем писать если они удовлетворяют требуемым ограничениям и Оптимальным в. а. на заданном мн-ве в. a. будет в. для которого с учетом всех необходимых ограничений. Примерами ф-ции риска могут быть заданная ф-ция дисперсии и матем. ожидания от погр. сама дисперсия или ее оценка, вероятность где заданная ф-ция, и т. д. Указанные примеры и определение носят формальный характер, т. к. в действительности ф-ция риска должна быть эффективной для использования и учитывать потери от замены некоторого идеального критерия его оценкой, напр., от замены матем. ожидания его оценкой в определении . Весьма общие способы построения эффективной ф-ции риска дает игр теория.

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

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

Лит.: Глушков В. М. Введение в кибернетику. К., 1964 [библиогр. с. 319—322]; Лебедев В. И. Об итерационном -методе. «Журнал вычислительной математики и математической физики», 1967, т. 7, Mi 6; Иванов В. В. Статистическое моделирование характеристик вычислительных алгоритмов. В кн.: Статистическое моделирование и аппаратура. М.. 1970. В. В. Иванов.