从标量切线到线性方程组
设 ,我们要求 。仅有一个分量的残差很小并不够:所有方程都必须同时成立。在当前估计 附近,线性化给出
其中 是由偏导数组成的 Jacobian 矩阵。
定义 6.3.1
(Newton 步)
当 可逆时,Newton 步 是线性方程组
的解。
实现时应求解线性方程组,而不是显式计算 。直接求解通常比显式构造逆矩阵更省计算,且具有较好的后向误差性质。两种做法都不能消除病态 Jacobian 带来的敏感性,因此计算出的步长仍可能不准确。矩阵奇异时,线性方程可能无解或有多个解,因此 (1) 并不自动有定义。
例题 6.3.2
(圆与直线)
考虑
两个解分别是 ,其中两坐标同号。若某次迭代位于直线上,即 且 ,则 (1) 的第二行迫使步长两分量相等,第一行再给出
从 开始,、,已接近 。这是一个真正的向量 Newton 计算,只因对称性而化成一维。只要第一步有解,即使起点不在直线上,第二行也会使下一迭代点恰好落在直线上。不同起点可能收敛到另一个根。令 且 ,精确误差恒等式 显示出该根附近的二次行为。
二次收敛究竟需要什么假设
使用欧氏(Euclidean)范数及其诱导矩阵范数,并记 为半径 的闭球。
定义 6.3.3
(Lipschitz Jacobian)
若对所有 都有
称 Jacobian 在 上具有 Lipschitz 常数 。
需要两个事实:Jacobian 在根附近保持可逆,而且其逆保持有界。
引理 6.3.4
(根附近的 Jacobian 保持可逆)
设 在 上以常数 Lipschitz 连续, 可逆,并令 。若 ,则对每个 ,矩阵 可逆,且 。
证明
(扰动 Jacobian 的 Neumann 级数)
令 、、。则 。当 时,级数 收敛到 ,所以 可逆,且 。由于 , 可逆,并且 ,其范数至多为 。
定理 6.3.5
(局部二次收敛)
设 在包含闭球 的开集上连续可微,,并且 在该球上以常数 Lipschitz 连续。假定 可逆,记 ,并选
对每个 ,每一步精确 Newton 迭代都有定义,所有迭代点留在球内,且
因此 ,且第一条界给出至少二次收敛。这里假设线性方程精确求解。另一个情形是球内 为常矩阵():一次精确迭代即到根,此时不使用上面的半径公式。所选的正 半径只是充分界,并未声称最优。线性方程组非精确求解或舍入会加入扰动,(2) 不必原样成立。
证明
(积分余项与归纳)
设 ,。由引理, 可逆且 。从 到 的线段包含在球内,沿线段应用微积分基本定理可得
令 ,减去 并提出 ,得到
Lipschitz 条件将被积向量的范数界为 。由引理,
又因 ,该值至多为 。归纳可知所有迭代点留在球内并收敛;第一条不等式证明了 (2)。若 ,积分公式直接化为 ,所以 。
证明透视
显式二次误差界来自哪里?
可逆给出常数 ;Lipschitz 常数用了两次,一次在引理中使 保持接近 ,一次在积分余项中。关键一步是把 写成 Jacobian 沿通向根的线段的积分。在 中,Newton 步已把一阶项恰好抵消,只剩下 的变化乘以 ,这提供了误差的平方。证明得以收尾,是因为 把二次界变成减半,使下一个迭代点仍在球内。若 不可逆,常数 就不存在;对 ,误差只是减半。定理是局部的:它没有找到未知的根,也没有证明任意起点都会进入这个球。
例题 6.3.6
(在标量方程上检验误差界)
对 ,有 、根 、、,所以 ,且 。起点 的误差 。Newton 步为 ,得 、、。误差约为 、、。比值 约为 、、,都不超过 ,与 (2) 一致,并趋向 。正确的位数大致每步翻倍。
定理没有排除的失败方式
反例模式
起点的 Jacobian 奇异
在圆与直线的例子中, 处 Jacobian 的第一行为零,但 的第一分量为 。因此 Newton 线性方程组无解。两个根处的 Jacobian 虽然可逆,却不能保证每个起点都能计算第一步。
例题 6.3.7
(奇异的根只给出线性收敛)
即使每一步都有定义,重根附近的收敛仍可能很慢。对 ,Jacobian 为 ,若 ,任意 都产生 。从 出发,迭代点依次为 。根 处的 Jacobian 奇异, 方向误差每次只减半,所以定理中“ 可逆”这一假设不能去掉。
所以,对实际方程组,仅凭步长或残差决定停止,需要考虑尺度和条件数。阻尼或线搜索可能帮助避免不良步长,但对任意方程组都不能无条件保证全局收敛。
常见错误
(因为残差小就停止)
没有适当的逆或条件数界时,残差小不一定意味着误差小: 在 处残差为 ,但到根的距离为一。
常见错误
(把局部定理当成全局保证)
定理只涉及 内的起点,并且需要已知根和 Lipschitz Jacobian。它没有证明任意初始猜测都会收敛,也没有证明根存在;圆与直线的例子中就有一个起点连第一步也不存在。
练习与解答
练习 6.3.8
(计算 在 处的 Jacobian 并解出 Newton 步。)
基础
解答(3)
- 1
在 处计算 和
- 2
解 Newton 方程组
取 ,第一行给出 ,所以 。
依据: 第二行给出 ,所以两个分量相等。
- 3
得出下一个迭代点
。验算:,残差远小于 。
快速检查
(对 ,为何 时到 的收敛不是二次的?)
计算两次迭代。
解答 · 答案
,第一步后 。 始终为 ,但二次收敛界会迫使这一比值趋于零;根处 Jacobian 奇异。
快速检查
(定理中若 、,且 ,给出一个允许的正半径。)
比较 与 。
解答 · 答案
此时 ,所以 是允许的,任何更小的正半径也是。
快速检查
(为什么仅凭 ,不能对所有方程组给出统一的到根距离界?)
试试 。
解答 · 答案
对函数族 , 处残差随 趋于零,而到根的距离一直为一。
快速检查
(局部定理是否证明所有起点都收敛?指出它在根附近需要的一个条件。)
看一看假设清单。
解答 · 答案
否。定理的一个假设是 可逆;它还要求 满足 Lipschitz 界,且起点足够接近根。对于球外任意起点,定理没有给出结论。