从一个方程到多个方程
“夹逼法与牛顿法”一课用切线代替 ,解单个方程 。许多问题有多个未知数及同样多个方程,例如两条曲线的交点。同一想法依然适用:在当前点用最佳线性近似取代映射,并解所得的线性方程组。新增的计算成分是每步要解一个线性方程组,所以本单元也用到消元法与分解各单元。我们证明局部二次收敛定理,并说明各假设如何失效。
定义
定义 2.5.1
(雅可比矩阵与牛顿步)
设 在开集 上连续可微,分量为 。其雅可比(Jacobi)矩阵为 ,元素 。根是满足 的点 。 在 处的线性近似为 。牛顿(Newton)法令此近似为零:
此步恰在 非奇异时有定义;实际上从不显式求 ,而是解方程组,例如用带主元的 LU 分解。当 ,这就是熟悉的 。全篇 表示向量范数及其诱导的矩阵范数。
局部二次收敛
引理 2.5.2
(受扰动可逆矩阵的逆)
设 可逆且 ,则 可逆,且
证明
(提出未扰动的矩阵)
令 ,则 。级数 依范数收敛;裂项求和 表明其和为 ,范数至多为 。由于 ,乘积 正是 的逆,其范数至多为 。
定理 2.5.3
(牛顿法的局部二次收敛)
设 连续可微,, 非奇异,记 。假设在球 上雅可比矩阵满足 Lipschitz 条件:。令 。若 ,则每个 都非奇异,所有迭代点留在球内,且
特别地,,且为二次收敛。
证明
(线性化误差对照一致的逆矩阵界)
设 ,。首先 ,所以 ,且 。由 Neumann 级数(扰动)引理, 可逆,且 。设 为牛顿更新,则
沿线段用微积分基本定理,,所以方括号等于 ,其范数至多为 。因此 。由于 ,有 ,故 。每一步都可重复此论证,误差趋于 。
证明透视
一个半径承担两个任务
证明的关键,是把新误差写成 作用于线性化误差。方括号 正是切线模型的偏差,Lipschitz 条件使它成为二次量 。球是凸集,所以由 到 的线段留在该条件成立的范围内。 非奇异只通过 使用,而引理把它转成根附近的一致界 。
半径 承担两个任务:它使 ,引理因而适用;又使 ,新误差至多为旧误差的一半。第二个任务把 留在球内,同一估计才可在下一步再次使用,归纳因而闭合。若 奇异, 没有定义,也不存在这样的半径;下面根处雅可比矩阵奇异的例子表明,二次收敛此时确实丧失。
有两点重要。二次收敛表示迭代点足够接近后,正确数字的位数每步大约翻倍。其次,定理是局部的:对任意初始点它没有说明任何事。
例题
例题 2.5.4
(圆与双曲线)
解 ,它有根 。这里 ,行列式为 。从 开始。
第 1 步。 ,,行列式为 。解 :,即 。故 。
第 2 步。 ,,求解得 。
以最大范数度量,误差为 ,下一个迭代点约为 :迭代点足够接近后,正确数字的位数每步大约翻倍,与定理一致。
例题 2.5.5
(根处雅可比矩阵奇异)
对 ,唯一的根是 ,该处 奇异。第一个分量的牛顿步为 ,第二个分量一步便精确。因此第一个坐标每次只减半:收敛是线性而非二次。单个方程的重根也出现同样的损失。
例题 2.5.6
(用标量情形验算)
取 ,,,步 为 。由 :,,故 。然后 ,,,与 相差约 。误差 再次显示正确数字位数翻倍。
常见错误与细微之处
- 收敛是局部的,可能收敛到另一个根。 圆与双曲线的方程组有四个根:、、、,到达哪一个取决于初始点。
- 定理要求根处雅可比矩阵非奇异,且雅可比矩阵满足 Lipschitz 条件。 缺少这些条件,收敛可能是线性的,甚至失败。
- 成本。 每步需要 、 及一次分解,稠密 方程组约需 次运算。
常见错误
(以为牛顿步总是存在)
对圆与双曲线, 在直线 上为零。在 ,雅可比矩阵为 ,是奇异的;由于 ,方程 无解,牛顿步没有定义。实现必须检测奇异或接近奇异的分解,而不是除以极小的主元。
常见错误
(把小残差当作小误差)
对 ,唯一的根是 ,。在 ,残差范数为 ,误差范数却是一。只有当 不大时, 小才表示误差小。
常见错误
(对雅可比矩阵求逆而非解方程组)
牛顿步只需解 。对稠密矩阵,带主元的 LU 分解约需 次运算,而构造 约需其三倍,且通常徒增舍入误差。
反例模式
牛顿法并非全局收敛
一个诱人的读法是:只要根是单根,牛顿法从任何起点都收敛。取 、,唯一的根是 ,且 。从 出发,迭代 给出 、、,迭代点发散。这与定理并不矛盾:此处 ,而 在 取最大值 ,所以定理只保证 时收敛。全局收敛需要线搜索或区间等保障措施。
习题
快速检查
(对 从 作两步牛顿迭代,并与根 比较。)
第一个方程是线性的,所以每一步都保持 。
解答 · 答案
。在 :,。解 与 ,得 ,,,。在 :,。解 与 :,,。故 。到 的最大范数误差由 降至 ,再降至 。
快速检查
(对 及 ,求 并解释为什么收敛是线性的。)
两个分量互不相关。
解答 · 答案
两个分量互不牵连。 给出第一个坐标 ,第二个坐标当 时 (一步便精确,因 )。故 时 。误差每步减半,是比值为 的线性收敛;根处雅可比矩阵奇异,所以定理不适用。
快速检查
(对 ( 非奇异),证明牛顿法从任何 出发都一步到达解。)
的雅可比矩阵是 。
解答 · 答案
此时 ,。该步解 ,得 ,,即精确解。
快速检查
(对 ,估计用 LU 分解解稠密雅可比方程组时,一步牛顿迭代的运算次数,取 。)
代入 。
解答 · 答案
次运算,另加计算 、 及三角求解()的低阶项。