Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




18.04.2021


18.04.2021


18.04.2021


18.04.2021


18.04.2021





Яндекс.Метрика

Метод Гаусса (оптимизация)

20.03.2022

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

Описание

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

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

x → 0 k + 1 = x → k {displaystyle {vec {x}}_{0}^{k+1}={vec {x}}_{k}}
{ x → 1 k + 1 = x → 0 k + 1 + λ 1 e → 1 , λ 1 = arg ⁡ min λ f ( x → 0 k + 1 + λ 1 e → 1 ) … x → n k + 1 = x → n − 1 k + 1 + λ n e → n , λ n = arg ⁡ min λ f ( x → n − 1 k + 1 + λ n e → n ) {displaystyle left{{egin{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}} ight.} ,

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

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

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

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

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

| | x → k + 1 − x → k | | < ε {displaystyle ||{vec {x}}_{k+1}-{vec {x}}_{k}||<varepsilon } .

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