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

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

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

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

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

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

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

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

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

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

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

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

гдо yj, SNчисла, . Последовательно вычисляют

f(P1), Р 2 = Ф 2 (Р 1; f(P1)), f(Р 2), Р 3 = Ф 3 (Р 1, Р 2; f(P1), f(P2)),..., f(PN).и полагают

I(f) SN(P1, ..., PN; f(P1), ..., f(PN).

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