最近学习数学建模学到了牛顿迭代。
牛顿迭代是一种求方程近似根的方法，我们平常用来求近似根的方法通常是二分，但是二分只适用于单调的情况。如果是二次函数，就需要先找到极值左右两边各两个大于0或者小于0的情况，但是牛顿迭代只需从负无穷和正无穷开始迭代即可。
牛顿迭代的具体操作如下:选择点 x 0 x_0 x0理论上应该满足 f ′ ( x 0 ) ≠ 0 f'(x_0)\ne 0 f′(x0)=0，我们令 x 1 x_1 x1满足 f ( x 0 ) + f ′ ( x 0 ) ( x 1 − x 0 ) = 0 f(x_0)+f'(x_0)(x_1-x_0)=0 f(x0)+f′(x0)(x1−x0)=0，即 x 1 = x 0 − f ( x 0 ) f ′ ( x 0 ) x_1=x_0-\frac{f(x_0)}{f'(x_0)} x1=x0−f′(x0)f(x0)，然后一次迭代，每一次迭代都会于精确解的误差变为一半（书上这样说的，但应该只有比较接近精确解的时候才成立，比如函数 y = ln x y=\ln x y=lnx，如果你取一个比较大的点，那么就会迭代到一个负数）。
现在考虑多个变量的牛顿迭代，我们只需要把多个变量看成一个向量，然后按照一维的形式求解，具体求解的时候需要用到偏导数等多个内容。
有n个函数 f 1 , f 2 , . . . , f n f_1,f_2,...,f_n f1,f2,...,fn，有n个未知量 x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1,x2,...,xn，满足
{ f 1 ( x 1 , x 2 , . . . , x n ) = 0 f 2 ( x 1 , x 2 , . . . , x n ) = 0 . . . f n ( x 1 , x 2 , . . . , x n ) = 0 \begin{cases} f_1(x_1,x_2,...,x_n)=0 \\ f_2(x_1,x_2,...,x_n)=0 \\ ... \\ f_n(x_1,x_2,...,x_n)=0 \end{cases} ⎩ ⎨ ⎧f1(x1,x2,...,xn)=0f2(x1,x2,...,xn)=0...fn(x1,x2,...,xn)=0
我们采用向量来表示，设 x = ( x 1 , x 2 , . . . , x n ) T , F ( x ) = ( f 1 ( x ) , f 2 ( x ) , . . . , f n ( x ) ) x=(x_1,x_2,...,x_n)^T,F(x)=(f_1(x),f_2(x),...,f_n(x)) x=(x1,x2,...,xn)T,F(x)=(f1(x),f2(x),...,fn(x))
设 A A A为 x = x ( 0 ) x=x(0) x=x(0)处的偏导数矩阵，有
A = [ ∂ f 1 ∂ x 1 ⋯ ∂ f 1 ∂ x n ⋮ ⋱ ⋮ ∂ f n ∂ x 1 ⋯ ∂ f n ∂ x n ] A=\begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \cdots & \frac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \cdots & \frac{\partial f_n}{\partial x_n} \end{bmatrix} A= ∂x1∂f1⋮∂x1∂fn⋯⋱⋯∂xn∂f1⋮∂xn∂fn
于是有 x ( 1 ) = x ( 0 ) − A − 1 F ( x ( 0 ) ) x(1)=x(0)-A^{-1}F(x(0)) x(1)=x(0)−A−1F(x(0))
具体到二维，有
q = ∂ F ∂ x ( x n − 1 , y n − 1 ) . r = ∂ F ∂ y ( x n − 1 , y n − 1 ) . s = ∂ G ∂ x ( x n − 1 , y n − 1 ) . t = ∂ G ∂ y ( x n − 1 , y n − 1 ) . u = − F ( x n − 1 , y n − 1 ) v = − G ( x n − 1 , y n − 1 ) D = q t − r s x n = x n − 1 + ( u t − v r ) / D y n = y n − 1 + ( q v − s u ) / D q=\frac{\partial F}{\partial x(x_{n-1},y_{n-1})} \\ .\\ r=\frac{\partial F}{\partial y(x_{n-1},y_{n-1})} \\ . \\ s=\frac{\partial G}{\partial x(x_{n-1},y_{n-1})} \\ .\\ t=\frac{\partial G}{\partial y(x_{n-1},y_{n-1})} \\ . \\ u=-F(x_{n-1},y_{n-1})\\ v=-G(x_{n-1},y_{n-1}) \\ D=qt-rs \\ x_n=x_{n-1}+(ut-vr)/D\\ y_n=y_{n-1}+(qv-su)/D q=∂x(xn−1,yn−1)∂F.r=∂y(xn−1,yn−1)∂F.s=∂x(xn−1,yn−1)∂G.t=∂y(xn−1,yn−1)∂G.u=−F(xn−1,yn−1)v=−G(xn−1,yn−1)D=qt−rsxn=xn−1+(ut−vr)/Dyn=yn−1+(qv−su)/D