WikiSort.ru - Программирование

Метод Гаусса^[1] — прямой метод решения задач многомерной оптимизации.

Описание

Пусть необходимо найти минимум действительнозначной функции ${\displaystyle f({\vec {x}})\to \min _{{\vec {x}}\in \mathbb {R} ^{n}}}$ , а ${\displaystyle {\vec {x}}_{0}}$  — начальное приближение.

Суть метода заключается в том, чтобы на каждой итерации по очереди минимизировать функцию вдоль каждой из координат, то есть:

${\displaystyle {\vec {x}}_{0}^{k+1}={\vec {x}}_{k}}$

${\displaystyle \left\{{\begin{array}{rl}{\vec {x}}_{1}^{k+1}={\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1},&\lambda _{1}=\arg \min _{\lambda }f({\vec {x}}_{0}^{k+1}+\lambda _{1}{\vec {e}}_{1})\\\ldots &\\{\vec {x}}_{n}^{k+1}={\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n},&\lambda _{n}=\arg \min _{\lambda }f({\vec {x}}_{n-1}^{k+1}+\lambda _{n}{\vec {e}}_{n})\end{array}}\right.}$ ,

где ${\displaystyle {\vec {e}}_{1},\ldots ,{\vec {e}}_{n}}$  — ортонормированный базис в рассматриваемом пространстве.

Таким образом метод как бы «поднимется» по координатам, используя на шагах одной итерации для вычисления следующей координаты точки приближения все предыдущие значения координат, вычисленные на той же итерации, в этом и состоит схожесть с одноимённым методом решения СЛАУ.

При завершении итерации, точка, полученная на последнем шаге этой итерации, берётся в качестве следующего приближения:

${\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{n}^{k+1}}$ .

Процедура продолжается до тех пор, пока не будет достигнута заданная точность ${\displaystyle \varepsilon }$ , то есть пока:

${\displaystyle ||{\vec {x}}_{k+1}-{\vec {x}}_{k}||<\varepsilon }$ .

Улучшением данного метода является метод покоординатного спуска Гаусса - Зейделя.

Примечания

Литература

• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

См. также

• Методы оптимизации
  • Метод покоординатного спуска Гаусса — Зейделя
  • Алгоритм Гаусса — Ньютона
• Линейная алгебра
  • Метод Гаусса
  • Метод Гаусса — Зейделя решения системы линейных уравнений