568

ОБЗОР МЕТОДОВ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ [ГЛ. 11

дено Уилкинсоном [8]. Основу математического аппарата Уил-
кинсона составил метод эквивалентных возмущений, с помощью
которых получены оценки норм возмущений для всех преобразо-
ваний линейной алгебры и построены оценки норм эквивалентных
возмущений для большого числа методов.

Параллельно с методом эквивалентных возмущений интенсив-
но развивалась статистическая теория анализа ошибок. Результа-
ты, полученные Н. С. Бахваловым [8], В. В. Воеводиным [8],
Г. Д. Ким [8] и др., положили начало исследованию действитель-
ного распределения ошибок округления.

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

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

11.5. Вопросы оптимизации численных методов

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

11.5]          ВОПРОСЫ ОПТИМИЗАЦИИ ЧИСЛЕННЫХ МЕТОДОВ

569

мулированная Н. С. Бахваловым [20], С. М. Никольским [З],
И. Бабушкой и С. Л. Соболевым [20], достаточно хорошо отража-
ет существо поставленной проблемы.

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

К настоящему времени наиболее развитой с точки зрения
теории оптимизации является теория кубатурных формул, раз-
работанная С. Л. Соболевым [1, 20], И. Бабушкой [20]. В их
работах задача оценки кубатурных формул приводится к реше-
нию задачи отыскания минимума линейного функционала ошибок.
Получены оценки ошибки кубатурных формул с правильной ре-
шеткой на классах периодических финитных и бесконечно диф-
ференцируемых функций. Методы исследования существенно ис-
пользуют асимптотические оценки приближений. Теории куба-
турных формул посвящены исследования Н. С. Бахвалова [20]
и И. М. Соболя [18], связанные с оптимальными оценками схо-
димости кубатурных процессов, с методами интегрирования типа
метода Монте-Карло, а также с отысканием наилучших способов
численного интегрирования.

Несколько иной подход к построению кубатурных формул на
основе теоретико-числового анализа, заложенный трудами
И. М. Виноградова [20], развивается в работах Н. М. Коробова
[201, К. К. Фролова [20], где строятся формулы, точные для
конечных тригонометрических полиномов, и даются оценки по-
грешностей на классе периодических функций.

А. Н. Колмогоров [20] ввел в рассмотрение ряд понятий тео-
рии множеств общего характера, позволяющих найти оценку
границы для необходимого числа действий при решении вычисли-
тельных задач. Особое значение такие оценки имеют для направ-
ленного поиска алгоритмов в тех случаях, когда асимптотики
сверху и снизу расходятся. Для линейных дифференциальных
операторов, имеющих вполне непрерывный обратный, им дана
оценка числа необходимых для решения действий. Эта оценка
позволяет находить алгоритмы, асимптотически близкие к опти-
мальным по числу арифметических действий.

Н. С. Бахваловым [20] исследован комплекс алгоритмов реше-
ния задач математической физики конечно-разностными методами.
В частности, им даны оценки снизу количества действий при
решении задачи Дирихле для уравнения Лапласа.

Интересное направление в оптимизации решения задач мате-
матической физики развивается в работах В. И. Лебедева [9].
В качестве основного минимизируемого функционала рассматрп-