Задача решения системы уравнений :
{ 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}\!,\,\epsilon }
Рассчитывают x → [ j + 1 ] = x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) {\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)} λ [ j ] = a r g m i n λ F ( x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) ) {\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)\right)}
Проверяют условие останова:
если | x → [ j + 1 ] − x → [ j ] | > ϵ {\displaystyle \left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon } j = j + 1 {\displaystyle j=j+1}
иначе x → = x → [ j + 1 ] {\displaystyle {\vec {x}}={\vec {x}}^{[j+1]}} Метод покоординатного спуска Гаусса — Зейделя
править
Этот метод назван по аналогии с методом Гаусса — Зейделя для решения системы линейных уравнений.
Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые λ n {\displaystyle \lambda \quad 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}
иначе 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}
иначе x → k + 1 = x → k j + 1 , k = k + 1 {\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1} 
![{\displaystyle x_{i}^{[0]}(i=1,2,...,n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4b25a205f7b750663ee61f88971b4ce3daa2853)
![{\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95104de24582bce75ff122625cd035365a2b9730)
![{\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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/bad5e13dee0e82f0331bdfe652f52eddfc4973b4)
![{\displaystyle {\vec {x}}^{[k]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/891114e525ed442f68d92da5493231e7a26d88c6)
![{\displaystyle v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4902269299b84b927d12a74db660572b161cb16d)
![{\displaystyle \lambda ^{[j]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d831e318fadde06c6ca72860557cb1f02a033624)
![{\displaystyle F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c888cb044df6085d605b806545a2512b92a50063)
![{\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88b862221083d82b8cbc1a5feadb31e44db8de0f)
![{\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7760fd1ca4bf7978aa9caa66912cada3108aa132)
![{\displaystyle v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afaa3eca5f7f038bb4b3018cb53bab5298f2519c)
![{\displaystyle x_{i}=x_{i}^{[j]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a76c3c6a1c54bcf4291ec9ec0af48980d1e7d34)
![{\displaystyle F(\lambda ^{[j]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb8be0329aaf8fa166e6f8610a15168098e32ff2)
![{\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}}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8009dfb7d5ba0851beba314affe1f6d87432f336)
![{\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/224554dc604defcb7c9227a1776544d39ef3e8a2)
![{\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1cf7d1bc81d622860d29e29dc4ec7b34608d4b1)
![{\displaystyle \left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5e75b06df9f6b1f7d67ceb0fd166371c0c709e7)
![{\displaystyle {\vec {x}}={\vec {x}}^{[j+1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25484a8abf3be57fa22807f00a750d162bc6a501)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f427fd60ea1ab3b9da8d96ca859f19603c372c3)
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db50a71a29deb83109fd16d970472a2ef52b1228)
![{\displaystyle |{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b289a3bb650bce1d33c3cea4305392343b6c0d44)
![{\displaystyle {\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d9461f45b42719380d1344a71194a20665885f3)
![{\displaystyle {\vec {x}}={\vec {x}}_{n}^{[j]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad1a73de98188e9d8d3c85e0cec32ce3dc987d00)
