ОПТИМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ

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

Теоретич. постановка вопроса об О. в. а. имеет следующее основание. При выборе метода решения задачи исследователь ориентируется на нек-рые ее свойства и выбирает алгоритм решения в зависимости от них, причем алгоритм будет применимым и при решении других задач, обладающих этими свойствами. Поэтому при теоретич. исследовании алгоритмов вводят в рассмотрение нек-рый класс задач Р, обладающих определенными свойствами. При выборе метода решения исследователь располагает иек-рым множеством Мметодов решения. При применении метода тк решению задачи ррешение будет получено с нек-рой погрешностью 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]).

В практике численного интегрирования активные алгоритмы типа алгоритмов интегрирования с автоматич. выбором шага (см. [10]) показали свое превосходство над пассивными алгоритмами. Это подтверждает общепринятую точку зрения о том, что формальная схема О. в. а. зачастую не охватывает специфики реальных задач. При решении задач оптимизации (в частности, задач минимизации) пассивные алгоритмы практически не употребляются (см. [12], [13]). Выше за единицу трудоемкости алгоритма неявно принимается трудоемкость вычисления одного значения функции из нек-рого класса F. Возможны и другие подходы к оценке оптимальности характеристик алгоритма. Напр., за единицу трудоемкости принимается трудоемкость вычисления нек-рого функционала l(f).из множества функционалов L(f). В этом случае оценка снизу трудоемкости алгоритмов производится с помощью теории поперечников (см. [14], [15]). Трудоемкость алгоритма складывается не только из трудоемкости получения информации об исходных данных, но и из трудоемкости обработки полученной информации. В настоящее время, по-видимому, нельзя привести примеров классов реальных вычислительных задач, где бы были получены оценки снизу трудоемкости алгоритмов, отличные от информационных оценок рассматриваемого типа. Однако для ряда задач невычислительного характера такого типа оценки известны (см. Алгоритма сложность).

В случае, когда исследование проблемы О. в. а. имеет своей целью решение задач на ЭВМ, проблема О. в. а. приобретает дополнительные оттенки, связанные с устойчивостью алгоритма к вычислительной погрешности, с ограничением на объем разных видов используемой памяти (см. Вычислительный алгоритм). Выше задача О. в. а. рассматривалась как задача О. в. а. на классах задач. Существенный интерес для практики представляет задача О. в. а. на конкретной задаче (см. [10], [16]). Постановка проблемы оптимизации (см. [16]) заключается в следующем. Дифференциальное уравнение интегрируется методом Рунге - Кутта с переменным шагом. Производится оценка главного члена оценки погрешности. Затем эта оценка оптимизируется по распределению узлов интегрирования (при общем заданном числе узлов). Такой подход к проблеме оптимизации оказал существенное влияние на развитие теории и практики активных алгоритмов численного интегрирования.

Лит.:[11 Никольский С. М., Квадратурные формулы, 3 изд., М., 1979; [2] Колмогоров А. Н., "Докл. АН СССР", 1956, т. 108, № 3, с. 385-88;[3] Колмогоров А. Н., Тихомиров В. М., "Успехи матем. наук", 1959, т. 14, в. 2, с. 3-86; [4] Витушкин А. Г., Оценка сложности задачи табулирования, М., 1959; [5] Бабушка И., Соболеве. Л., "Aplikace mat.", 19B5, t. 10, s. 96-129; [6] Бахвалов Н. С., там же, 1968, t. 13, s. 27-38: [7] его же, в кн.: Международный конгресс математиков в Ницце. 1970. Доклады советских математиков, М., 1972, с. 27-33; [8] его же, в кн.: Численные методы решения дифференциальных и интегральных уравнений и квадратурные формулы, М., 1964, с. 3-63; [9] его же, "Матем. заметки", 1972, т. 12, в. 6, с. 655-64; [10] его же, Численные методы, 2 изд., М., 1975; [11] его же, "Ж. вычислит, матем. и матем. физ.", 1971, т. 11, № 4, с. 1014-18; [12] Уайлд Д.- Д ж ., Методы поиска экстремума, пер. с англ., М., 1967; [13] Васильев Ф. П., Численные методы решения экстремальных задач, М., 1980; [14] Оганесян Л. А., Руховец Л. А., Вариационно-разностные методы решения эллиптических уравнений, Ер., 1979; [15] Тихомиров В. М., Некоторые вопросы теории приближений, М., 1976; [16] Тихонов А. Н., Горбунов А. Д., "Ж. вычислит, матем. и матем. физ.", 1964, т. 4, № 2, с. 232-41. Н. С. Бахвалов.