Глава 7. Решение систем нелинейных уравнений и задач оптимизации

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

при условиях

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

Системы уравнений

которые мы будем также обозначать

возникают в случае многих задач указанных выше типов; например, в гл. 10 будет идти речь о подобных системах, возникающих при решении краевых задач.

Задачи минимизации функции и решения системы уравнений сводятся ДРУГ к другу. Если при

то решение системы равносильно минимизации функции

С другой стороны, пусть достигается в точке X, внутренней по отношению к G, и функция Ф дифференцируема в этой точке. Тогда точка минимума является решением системы уравнений

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

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

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

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

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

На примере решения системы линейных уравнений было также видно, Что сведение этой задачи к задаче нахождения минимума функционала приводит к конструированию новых методов решения исходной задачи.