Завдання рішення системи рівнянь :
{ f 1 ( x 1 , x 2 , … , x n ) = 0 … f n ( x 1 , x 2 , … , x n ) = 0 {\displaystyle \left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n}(x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.} (1)
з n {\displaystyle n} x 1 , x 2 , … , x n {\displaystyle x_{1},x_{2},\ldots ,x_{n}} еквівалентна задачі мінімізації функції
F ( x 1 , x 2 , … , x n ) ≡ ∑ i = 1 n | f i ( x 1 , x 2 , . . . , x n ) | 2 {\displaystyle F(x_{1},x_{2},\ldots ,x_{n})\equiv \sum _{i=1}^{n}|f_{i}(x_{1},x_{2},...,x_{n})|^{2}} (2)
або якій-небудь іншій зростаючій функції від абсолютних величин | f i | {\displaystyle |f_{i}|} нев'язок (помилок) f i = f i ( x 1 , x 2 , … , x n ) {\displaystyle f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})} , i = 1 , 2 , … , n {\displaystyle i=1,2,\ldots ,n} . Завдання знаходження мінімуму (або максимуму) функції n {\displaystyle n} змінних і сама по собі має велике практичне значення.
Для вирішення цієї задачі ітераційними методами починають з довільних значень x i [ 0 ] ( i = 1 , 2 , . . . , n ) {\displaystyle x_{i}^{[0]}(i=1,2,...,n)} і будують послідовні наближення:
x → [ j + 1 ] = x → [ j ] + λ [ j ] v → [ j ] {\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}}
або покоординатно:
x i [ j + 1 ] = x i [ j ] + λ [ j ] v i [ j ] , i = 1 , 2 , … , n , j = 0 , 1 , 2 , … {\displaystyle x_{i}^{[j+1]}=x_{i}^{[j]}+\lambda ^{[j]}v_{i}^{[j]},\quad i=1,2,\ldots ,n,\quad j=0,1,2,\ldots } (3)
які зводяться до деякого рішенням x → [ k ] {\displaystyle {\vec {x}}^{[k]}} при j → ∞ {\displaystyle {j\to \infty }} .
Різні методи відрізняються вибором «напрямку» для чергового кроку, тобто вибором відносин
v 1 [ j ] : v 2 [ j ] : … : v n [ j ] {\displaystyle v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}} .
Величина кроку (відстань, на яку треба піднятися в заданому напрямку в пошуках екстремуму) визначається значенням параметра λ [ j ] {\displaystyle \lambda ^{[j]}} , який мінімізує величину F ( x 1 [ j + 1 ] , x 2 [ j + 1 ] , … , x n [ j + 1 ] ) {\displaystyle F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})} як функцію від λ [ j ] {\displaystyle \lambda ^{[j]}} . Цю функцію зазвичай апроксимують її розкладанням у ряд Тейлора або інтерполяційним многочленом з трьох-п'яти вибраних значень λ [ j ] {\displaystyle \lambda ^{[j]}} . Останній метод застосуємо для знаходження max і min таблично заданої функції F ( x 1 , x 2 , . . . , x n ) . {\displaystyle F(x_{1},x_{2},...,x_{n}).}
Основна ідея методів полягає в тому, щоб йти в напрямку найшвидшого спуску, а це напрямок задається антиградієнтом − ∇ F {\displaystyle -\nabla F} :
x → [ j + 1 ] = x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) {\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})}
де λ [ j ] {\displaystyle \lambda ^{[j]}} вибирається:
сталою, в цьому випадку метод може розходитися; дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число; якнайскорішим спуском: λ [ j ] = a r g m i n λ F ( x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) ) {\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))} Вибирають v i [ j ] = − ∂ F ∂ x i {\displaystyle v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i}}}} , де всі похідні обчислюються при x i = x i [ j ] {\displaystyle x_{i}=x_{i}^{[j]}} , і зменшують довжину кроку λ [ j ] {\displaystyle \lambda ^{[j]}} по мірі наближення до мінімуму функції F {\displaystyle F} .
Для аналітичних функцій F {\displaystyle F} і малих значень f i {\displaystyle f_{i}} тейлорівський розклад F ( λ [ j ] ) {\displaystyle F(\lambda ^{[j]})} дозволяє вибрати оптимальну величину кроку
λ [ j ] = ∑ k = 1 n ( ∂ F ∂ x k ) 2 ∑ k = 1 n ∑ h = 1 n ∂ 2 F ∂ x k d x h ∂ F ∂ x k ∂ F ∂ x h {\displaystyle \lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\partial F}{\partial x_{k}}})^{2}}{\sum _{k=1}^{n}\sum _{h=1}^{n}{\frac {\partial ^{2}F}{\partial x_{k}dx_{h}}}{\frac {\partial F}{\partial x_{k}}}{\frac {\partial F}{\partial x_{h}}}}}} (5)
де всі похідні обчислюються при x i = x i [ j ] {\displaystyle x_{i}=x_{i}^{[j]}} . Параболічна інтерполяція функції F ( λ [ j ] ) {\displaystyle F(\lambda ^{[j]})} може виявитися більш зручною.
Алгоритм Задаються початкове наближення і точність розрахунку x → 0 , ϵ {\displaystyle {\vec {x}}^{0},\quad \epsilon } Розраховують x → [ j + 1 ] = x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) {\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})} , де λ [ j ] = a r g m i n λ F ( x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) ) {\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))} Перевіряють умову зупинки :Якщо | x → [ j + 1 ] − x → [ j ] | > ϵ {\displaystyle |{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}|>\epsilon } , то j = j + 1 {\displaystyle j=j+1} і перехід до кроку 2. Інакше x → = x → [ j + 1 ] {\displaystyle {\vec {x}}={\vec {x}}^{[j+1]}} і зупинка.
Метод покоординатного спуску Гауса — Зейделя Цей метод названий за аналогією з методом Гауса — Зейделя для розв'язання системи лінійних рівнянь.Покращує попередній метод за рахунок того, що на черговій ітерації спуск здійснюється поступово уздовж кожної з координат, однак тепер необхідно обчислювати нові λ n {\displaystyle \lambda n} раз за один крок.
Алгоритм Задаються початкове наближення і точність розрахунку x → 0 0 , ε {\displaystyle {\vec {x}}_{0}^{0},\quad \varepsilon } Розраховують { x → 1 [ j ] = x → 0 [ j ] − λ 1 [ j ] ∂ F ( x → 0 [ j ] ) ∂ x 1 e → 1 … x → n [ j ] = x → n − 1 [ j ] − λ n [ j ] ∂ F ( x → n − 1 [ j ] ) ∂ x n e → n {\displaystyle \left\{{\begin{array}{lcr}{\vec {x}}_{1}^{[j]}&=&{\vec {x}}_{0}^{[j]}-\lambda _{1}^{[j]}{\frac {\partial F({\vec {x}}_{0}^{[j]})}{\partial x_{1}}}{\vec {e}}_{1}\\\ldots &&\\{\vec {x}}_{n}^{[j]}&=&{\vec {x}}_{n-1}^{[j]}-\lambda _{n}^{[j]}{\frac {\partial F({\vec {x}}_{n-1}^{[j]})}{\partial x_{n}}}{\vec {e}}_{n}\end{array}}\right.} , де λ i [ j ] = a r g m i n λ F ( x → i − 1 [ j ] − λ [ j ] ∂ F ( x → i − 1 [ j ] ) ∂ x i e → i ) {\displaystyle \lambda _{i}^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}_{i-1}^{[j]}-\lambda ^{[j]}{\frac {\partial F({\vec {x}}_{i-1}^{[j]})}{\partial x_{i}}}{\vec {e}}_{i}\right)} Перевірють умову зупинки:Якщо | x → n [ j ] − x → 0 [ j ] | > ε {\displaystyle |{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon } , то x → 0 [ j + 1 ] = x → n [ j ] , j = j + 1 {\displaystyle {\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1} і перехід до кроку 2. Інакше x → = x → n [ j ] {\displaystyle {\vec {x}}={\vec {x}}_{n}^{[j]}} і зупинка.
Метод спряжених градієнтів Метод спряжених градієнтів ґрунтується на поняттях прямого методу багатовимірної оптимізації — методу спряжених напрямів.
Застосування методу до квадратичних функцій R n {\displaystyle \mathbb {R} ^{n}} визначає мінімум за n {\displaystyle n} кроків.
Алгоритм Задаються початковим наближенням і похибкою: x → 0 , ε , k = 0 {\displaystyle {\vec {x}}_{0},\quad \varepsilon ,\quad k=0} Розраховують початковий напрямок: j = 0 , S → k j = − ∇ f ( x → k ) , x → k j = x → k {\displaystyle j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_{k}^{j}={\vec {x}}_{k}} x → k j + 1 = x → k j + λ S → k j , λ = arg min λ f ( x → k j + λ S → k j ) , S → k j + 1 = − ∇ f ( x → k j + 1 ) + ω S → k j , ω = | | ∇ f ( x → k j + 1 ) | | 2 | | ∇ f ( x → k j ) | | 2 {\displaystyle {\vec {x}}_{k}^{j+1}={\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j},\quad \lambda =\arg \min _{\lambda }f({\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j}),\quad {\vec {S}}_{k}^{j+1}=-\nabla f({\vec {x}}_{k}^{j+1})+\omega {\vec {S}}_{k}^{j},\quad \omega ={\frac {||\nabla f({\vec {x}}_{k}^{j+1})||^{2}}{||\nabla f({\vec {x}}_{k}^{j})||^{2}}}} Якщо | | S → k j + 1 | | < ε {\displaystyle ||{\vec {S}}_{k}^{j+1}||<\varepsilon } або | | x → k j + 1 − x → k j | | < ε {\displaystyle ||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon } , то x → = x → k j + 1 {\displaystyle {\vec {x}}={\vec {x}}_{k}^{j+1}} і зупинка. Інакшеякщо ( j + 1 ) < n {\displaystyle (j+1)<n} , то j = j + 1 {\displaystyle j=j+1} і перехід до 3; x → k + 1 = x → k j + 1 , k = k + 1 {\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1} і перехід до 2.