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

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

наз. погрешностью метода тна классе задач Р, а

- оптимальной на классе Роценкой погрешности методов из множества М. Если существует метод такой, что

то этот метод наз. оптимальным. Такая схема рассмотрения проблемы О. в. а., восходящая к А. Н. Колмогорову [2], изучает множество задач вычисления интеграла

при условии - множество всевозможных квадратур ,

каждая квадратура задается совокупностью 2N чисел C_j и х _j. Задача о минимальном количестве информации (см. [2], [3]), необходимой для запоминания функции из данного класса с требуемой точностью, также может быть уложена в эту схему. Рассматривается [4] более сложная постановка проблемы, где трудоемкость реализации алгоритма в определенном смысле увязывается с объемом используемой памяти. Оптимальные алгоритмы построены для незначительного числа задач типа [1].

Однако для большого числа вычислительных задач построены методы, по своим асимптотич. характеристикам близкие к оптимальным (см. [5]-[8]).

Исследование характеристик оптимальных на классах вычислительных алгоритмов решения задач (см. [5], [7]) складывается из двух частей: построение конкретных методов решения с возможно лучшими характеристиками и получение оценок снизу характеристик вычислительных алгоритмов (см. [2]-[4], [9]). По существу первая часть вопроса является основной проблемой теории численных методов и в большинстве случаев рассматривается независимо от проблемы оптимизации. Получение оценок снизу обычно сводится к оценке снизу e-энтропии или поперечников соответствующих пространств; иногда оно проводится независимо, но с использованием техники, аналогичной технике получения указанных оценок.

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

где веса С _j и P_j из области W определения f задаются заранее. Активные алгоритмы вычисления интеграла укладываются в следующую схему: задается точка . и функции

гдо y_j, S_N- числа, . Последовательно вычисляют

f(P₁), Р ₂ = Ф ₂ (Р ₁; f(P₁)), f(Р ₂), Р ₃ = Ф ₃ (Р ₁, Р ₂; f(P₁), f(P₂)),..., f(P_N).и полагают

I(f) S_N(P₁, ..., P_N; f(P₁), ..., f(P_N).

В случае выпуклых классов подинтегральных функций, центрально симметричных относительно функции , оптимальная оценка на классе пассивных алгоритмов совпадает с оптимальной оценкой на классе активных алгоритмов (см. [10], [11]).