牛顿法求解方程的根和最优化问题

比眉伴天荒 2022-12-25 13:53 138阅读 0赞

## 1. 牛顿法求解方程的零点 ##

利用牛顿法可以迭代求解方程的根：

首先利用泰勒公式，在![x=x\_0][x_x_0]处进行一阶展开

![f(x) = f(x\_0) + \\dot f(x\_0)(x-x\_0)][f_x_ _ f_x_0_ _ _dot f_x_0_x-x_0]

欲求解方程的根，即令![f(x)=0][f_x_0]，可得：

![f(x\_0) + (x - x\_0)\\dot f(x\_0) = 0][f_x_0_ _ _x - x_0_dot f_x_0_ _ 0]

通过上述等式，进一步求解![x=x\_0][x_x_0]处下一个迭代步的临近点

![x = x\_1 = x\_0 - \\frac\{f(x\_0)\}\{\\dot f(x\_0)\}][x _ x_1 _ x_0 - _frac_f_x_0_dot f_x_0]

迭代求解公式：

![x\_\{n+1\} = x\_n - \\frac\{f(x\_n)\}\{\\dot f(x\_n)\}][x_n_1_ _ x_n - _frac_f_x_n_dot f_x_n]

## 2. 牛顿法求解最优化问题 ##

欲求解![\\dot f = 0][dot f _ 0]的根，需要将![f(x)][f_x]在目标点![x=x\_n][x_x_n]处二阶泰勒展开：

![f(x) = f(x\_n) + \\dot f(x\_n)(x - x\_n) + \\frac\{\\ddot f(x\_n)\}\{2\}(x - x\_n)^2][f_x_ _ f_x_n_ _ _dot f_x_n_x - x_n_ _ _frac_ddot f_x_n_2_x - x_n_2]

由于需要求解![\\dot f = 0][dot f _ 0]的根，所以需要对上式进行求导：

![\\dot f(x) = \\dot f(x\_n) + \\ddot f(x\_n)(x - x\_n) = 0][dot f_x_ _ _dot f_x_n_ _ _ddot f_x_n_x - x_n_ _ 0]

最终类似于求解方程零点，推导出牛顿法求解最优化问题的迭代公式：

![x\_\{n + 1\} = x\_n - \\frac\{\\dot f(x\_n)\}\{\\ddot f(x\_n)\}, n = 0,1,2...][x_n _ 1_ _ x_n - _frac_dot f_x_n_ddot f_x_n_ n _ 0_1_2...]

## 3. 牛顿法求解高维优化问题 ##

![x\_\{n+1\} = x\_n-H^\{-1\}(x\_n)\\nabla f(x\_n), n\\geq 0][x_n_1_ _ x_n-H_-1_x_n_nabla f_x_n_ n_geq 0]

其中H表示海塞矩阵，![\\nabla f(x\_n)][nabla f_x_n]表示![f(x\_n)][f_x_n]的梯度

[x_x_0]: https://private.codecogs.com/gif.latex?x%3Dx_0
[f_x_ _ f_x_0_ _ _dot f_x_0_x-x_0]: https://private.codecogs.com/gif.latex?f%28x%29%20%3D%20f%28x_0%29%20&plus;%20%5Cdot%20f%28x_0%29%28x-x_0%29
[f_x_0]: https://private.codecogs.com/gif.latex?f%28x%29%3D0
[f_x_0_ _ _x - x_0_dot f_x_0_ _ 0]: https://private.codecogs.com/gif.latex?f%28x_0%29%20&plus;%20%28x%20-%20x_0%29%5Cdot%20f%28x_0%29%20%3D%200
[x _ x_1 _ x_0 - _frac_f_x_0_dot f_x_0]: https://private.codecogs.com/gif.latex?x%20%3D%20x_1%20%3D%20x_0%20-%20%5Cfrac%7Bf%28x_0%29%7D%7B%5Cdot%20f%28x_0%29%7D
[x_n_1_ _ x_n - _frac_f_x_n_dot f_x_n]: https://private.codecogs.com/gif.latex?x_%7Bn&plus;1%7D%20%3D%20x_n%20-%20%5Cfrac%7Bf%28x_n%29%7D%7B%5Cdot%20f%28x_n%29%7D
[dot f _ 0]: https://private.codecogs.com/gif.latex?%5Cdot%20f%20%3D%200
[f_x]: https://private.codecogs.com/gif.latex?f%28x%29
[x_x_n]: https://private.codecogs.com/gif.latex?x%3Dx_n
[f_x_ _ f_x_n_ _ _dot f_x_n_x - x_n_ _ _frac_ddot f_x_n_2_x - x_n_2]: https://private.codecogs.com/gif.latex?f%28x%29%20%3D%20f%28x_n%29%20&plus;%20%5Cdot%20f%28x_n%29%28x%20-%20x_n%29%20&plus;%20%5Cfrac%7B%5Cddot%20f%28x_n%29%7D%7B2%7D%28x%20-%20x_n%29%5E2
[dot f_x_ _ _dot f_x_n_ _ _ddot f_x_n_x - x_n_ _ 0]: https://private.codecogs.com/gif.latex?%5Cdot%20f%28x%29%20%3D%20%5Cdot%20f%28x_n%29%20&plus;%20%5Cddot%20f%28x_n%29%28x%20-%20x_n%29%20%3D%200
[x_n _ 1_ _ x_n - _frac_dot f_x_n_ddot f_x_n_ n _ 0_1_2...]: https://private.codecogs.com/gif.latex?x_%7Bn%20&plus;%201%7D%20%3D%20x_n%20-%20%5Cfrac%7B%5Cdot%20f%28x_n%29%7D%7B%5Cddot%20f%28x_n%29%7D%2C%20n%20%3D%200%2C1%2C2...
[x_n_1_ _ x_n-H_-1_x_n_nabla f_x_n_ n_geq 0]: https://private.codecogs.com/gif.latex?x_%7Bn&plus;1%7D%20%3D%20x_n-H%5E%7B-1%7D%28x_n%29%5Cnabla%20f%28x_n%29%2C%20n%5Cgeq%200
[nabla f_x_n]: https://private.codecogs.com/gif.latex?%5Cnabla%20f%28x_n%29
[f_x_n]: https://private.codecogs.com/gif.latex?f%28x_n%29