570 [ГЛ. 11

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

вается цена алгоритма и энтропия. С помощью этого метода
рассмотрены некоторые задачи теории переноса.

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

Изучению теории вычислительных процессов и их оптимиза-
ции посвящено значительное число исследований Бабушки [20],
Дальквиста [20], Хенричи [3] и др. Бабушка, Витасек и Прагер
[3] ввели понятие (^-последовательностей вычислительных про-
цессов, которое отражает тот факт, что при увеличении длины
последовательности вычислений точность вычислений должна уве-
личиваться по степенному закону., На основе теории (^-последо-
вательностей было введено понятие локальной и глобальной
устойчивости численных процессов, которое позволило провести
анализ большого круга реальных алгоритмов вычислительной
математики.

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

11.6. Методы оптимизации

С задачами на связанный экстремум человечество знакомо
с глубокой древности. История развития этой области знаний
в рамках математики может быть разделена, конечно, весьма
условно, на ряд этапов. Сначала рассматривались отдельные за-
дачи, главным образом геометрического происхождения, причем
среди них имеются весьма знаменитые, не потерявшие своего
значения до наших дней. Например, решение изопериметриче-
ской задачи было известно еще древним грекам (Зенодор). Общий
метод решения аналитических задач на связанный максимум или
минимум принадлежит Лагранжу. Наличие техники множителей
Лагранжа позволяет многие задачи решать стандартным путем,
не подвергая их порой весьма сложному индивидуальному иссле-
дованию. Однако при этом решаются лишь задачи на гладких
многообразиях. Границы многообразии, то есть ограничения типа
неравенств, должны исследоваться отдельно.

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

И.6] 571

МЕТОДЫ ОПТИМИЗАЦИИ

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

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

Впервые наиболее важные результаты были получены в теории
систем, обеспечивающих минимальное время регулирования.

В 1952—1955 гг. главным образом в работах Фельдбаума были
заложены основы теории оптимальных по быстродействию про-
цессов для линейных систем.

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

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

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