数值解和优化问题(01)：对分法, 切线法和割线法
本章介绍两类问题, 数值解问题(即解方程)和优化问题(即查找极小值点), 它们一定程度上很像. 我们默认本章的讨论对象, 即某些一元或多元函数, 在讨论的区间上具有连续导数. 我们不使用特定的公式进行近似估计, 而是从一个初始点开始进行迭代逼近最优解. 本节就要介绍三类迭代求根法.
对分法
给定一个函数\(f(x)\), 如果我们已知它在闭区间\([a,b]\)上连续并且满足\(f(a)f(b)<0\), 那么最直接的求根方法就是 对分法, 也称 二分法.
对分法的流程十分简单, 每次我们将区间二分, 计算中间位置\(c=\displaystyle\frac{a+b}{2}\)的函数值\(f(c)\), 如果它和\(f(a)\)或\(f(b)\)中的某个值异号, 则可以知道两个子区间中存在根的区间, 如是递归, 就能锁定根附近的一个小区间.
对分法的优势十分明显, 如果\(f(x)\)的导数计算不便(尽管存在), 那么对分法作为一种只涉及函数值计算的方法是很便利的; 另外, 很多时候求根过程本身并没有多么费时, 或者不追求收敛速度, 那么对分法也是较好的选择, 它的误差随迭代次数而指数衰减.
Newton-Raphson 法
我们同样考虑一个一元函数\(f(x)\)的根. 假设它有一根\(\xi\), 并且搜索域足够光滑并处在\(\xi\)附近, 使得函数\(f(x)\)可以作 Taylor 展开: \[ f(\xi)=0\ ;\qquad f(\xi)=f(x_0)+f'(x_0)(\xi-x_0)+o(\xi-x_o) \] 抛弃高阶无穷小, 也就是作线性近似,有 \[ \begin{aligned} &\boxed{\xi\approx x_0-\frac{f(x_0)}{f'(x_0)}} \\\text{或者写作 }& \boxed{x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}} \end{aligned} \] 这个表达式就是所谓的 Newton-Raphson 法, 将求得的\(\xi\)值作为下一轮的\(x_0\)进行迭代, 直到误差收敛到想要的范围, 因为涉及且仅涉及一阶导数计算, 又称为 切线法.
切线法的优势在于更快的收敛速度. 令\(\epsilon_i=x_i-\xi\), 有 \[ \epsilon_{i+1}=\epsilon_{i}-\frac{f(x_i)}{f'(x_i)} \] 考虑到后一项的 Taylor 近似公式 \[ \begin{aligned} f(x_i)&=f(\xi)+f'(\xi)\cdot\epsilon_i+o(\epsilon_i)\approx f'(\xi)\cdot\epsilon_i \\ f'(x_i)&=f'(\xi)+f''(\xi)\cdot\epsilon_i + o(\epsilon_i)\approx f'(\xi)+f''(\xi)\cdot\epsilon_i \end{aligned} \] 得到 \[ \epsilon_{i+1}\sim\epsilon_i^2 \] Newton 法也并非没有缺陷. 迭代公式依赖于函数导数, 如果在搜索域内同时存在极值, 使得\(f'(x_i)\)很小, 那么可能造成某一步的位移很大, 误差急剧变大, 慢慢回来是很困难的, 极值点(驻点)对 Newton 法干扰很大.
高阶推广
我们可以作抛物近似, 它给出一个比较复杂的公式: \[ x_{i+1}=x_i-\frac{f(x_i)\pm\sqrt{f'(x_i)^2-2f(x_i)f''(x_i)}}{f''(x_i)} \] 更高阶的推广过于复杂, 而且导数计算不便, 故而不用, 这个二阶推广使用也较少.
多元推广
我们还可以把一元方程推广为多元的方程组. 给定线性独立的方程组 \[ f_k(\vec{x})=0\ ,\qquad k=1,2,\cdots,n \] 其中\(\vec{x}=(x^{(1)},x^{(2)},\cdots,x^{(n)})\). 同样地, 进行 Taylor 展开 \[ \vec{f}(\vec{\xi})=\boldsymbol{0}\ ;\qquad \vec{f}(\vec{\xi})=\vec{f}(\vec{x}_0)+\boldsymbol{\nabla}\vec{f}(\vec{x}_0)\cdot(\vec{\xi}-\vec{x}_0)+o(|\vec{\xi}-\vec{x}_0|) \] 其中\(\boldsymbol{\nabla} \vec{f}(\vec{x}_0)\)自然是个张量, 并且满足 \[ [\boldsymbol{\nabla} \vec{f}(\vec{x}_0)]_{jk}=\frac{\partial f_j(\vec{x})}{\partial x^{(k)}} \] 就是 Jacobi 矩阵. 只要它在搜索域上可逆, 就有<span class="hint--top hint--rounded" aria-label="等价于 Jacobi 行列式非零, 这实际上就是"线性独立"想表达的意思">[1] \[ \vec{x}_{i+1}=\vec{x}_i-[\boldsymbol{\nabla} \vec{f}(\vec{x}_i)]^{-1}\cdot\vec{f}(\vec{x}_i) \] 当维数\(n=1\)时, 退化为一元函数的切线法.
割线法
割线法和切线法类似, 它是导数不太好算时的平替, 我们用割线代替切线: \[ f'(x_i)\approx\frac{f(x_i)-f(x_{i-1})}{x_i-x_{i-1}} \] 那么割线法的迭代公式为 \[ x_{i+1}=x_i-\frac{(x_i-x_{i-1})f(x_i)}{f(x_i)-f(x_{i-1})} \] 这实际上意味着\(x\)能够具有下标\(-1\), 也就是说我们要给定两个初始位置\(x_{-1}\)和\(x_0\). 如果它们之间存在驻点, 割线法同样会失败; 只要正确运用割线法, 其收敛速度略慢于切线法, 但明显快于对分法.
- 等价于 Jacobi 行列式非零, 这实际上就是"线性独立"想表达的意思 ↩︎