定位零点
数值根是满足 的数 的近似值。仅给出迭代公式并不能保证收敛:必须说明起点及 所满足的条件。不同方法在进展有保证与速度快之间作出取舍;而函数值很小是否有意义,还取决于逆问题在局部的敏感程度。
定义 6.1.1
(变号夹根区间)
设 在 上连续。若 ,即 与 都不为零且异号,则称 为 的夹根区间。
介值定理保证夹根区间内至少有一个根。二分法在 处计算 ,若 则停止,否则保留端点异号的半区间,它同样是夹根区间。
命题 6.1.2
(二分法误差界)
设 是 的夹根区间, 是 次对半分割后保留的区间,其中 (若某个中点恰为根,方法在该处停止)。则 含有根,长度为 ,其中点到 内至少一个根的距离不超过 。
证明
(对半分割仍保持夹根)
每个保留的半区间端点异号,故由归纳法 是夹根区间,介值定理在其中给出一个根。每一步长度减半,得 。长为 的区间内任一点到中点的距离至多为 ,所以 内的根与其中点相距不超过 。
这些条件保证存在根和误差界,并不保证根唯一;如果 严格单调,则至多有一个根。
例题 6.1.3
(二分法三步逼近 2 的平方根)
对 上的 ,,。第一个中点 处 ,故保留 。第二个中点 处 ,保留 。第三个中点是 ,,下一个区间为 。两次对半分割后,中点 与根的距离不超过 ;实际上 ,。三次对半分割后,中点 的误差界为 ,实际误差约为 。
常见错误
(没有变号不代表没有根)
偶重根不一定伴随符号改变,无法单凭变号检测。对 上的 ,,所以 不是夹根区间,但 确实是根。变号测试是存在根的充分条件,而不是必要条件。
不动点迭代
将方程改写为 ,并迭代 。只有当所选改写在讨论的定义域上建立了等价关系, 的不动点才是 的根。压缩映射定理给出一个实用的充分条件。
定义 6.1.4
(区间上的不动点与压缩映射)
设 ,。若 ,则 称为 的不动点。若 ,且对所有 都有 (其中 ),则称 是 上以 为常数的压缩映射。
定理 6.1.5
(区间上的压缩映射定理)
设 是 上以 为常数的压缩映射。则 中有唯一不动点 ,从 内任意初值开始的迭代都收敛到它。此外,,且 。
证明
(几何级数尾和与 Cauchy 序列)
迭代点始终留在 中,相邻两项之差满足 。求几何级数尾和可知迭代序列为 Cauchy 序列。由 的完备性和 的闭性,它收敛到某个 。Lipschitz 不等式保证 连续,因此 。若 是另一不动点,则 迫使二者相等。将压缩不等式直接用于 和 得到第一个界;求尾和得到第二个界。
若 在 上连续、在内部可微,则当 时,中值定理给出所需 Lipschitz 界。但区间映回自身是另一项独立条件。
反例模式
导数很小但区间不被映回自身
命题:若在 上 ,则 在 中有不动点。取 上的 。此时 ,但 ,,所以 把 映到其外部。方程 的解为 ,因此 内没有不动点。即使是导数为一的 ,在任何区间上也没有不动点。修正方法是加上 ,压缩映射定理除 Lipschitz 界外还需要这个条件。
用相邻步长得到误差界
定理的第一个估计含有未知的 。要得到可以实际计算的估计,可把剩余步长相加。
命题 6.1.6
(可计算的不动点误差界)
在 上的压缩条件下,对 ,
证明
(把剩余步长相加)
反复应用压缩不等式,得 ,其中 。先用三角不等式估计 ,再令 ,便得到几何级数尾和,即第一式。对第二式,写出 ,然后将最后一项移到左边。
第二式使用的是不动点残差 ;除非知道它与原方程残差 的关系,否则不能直接用后者代替。
例题 6.1.7
(平方根的可计算误差保证)
对 ,在 上取 。由于 位于 , 递增,且 。它以 为压缩常数,区间内唯一不动点为 。从 出发得到 、。第一个界保证
这个界偏保守:实际误差约为 。但得到保证时并不需要知道根的小数展开。这里假设精确算术;舍入后的步长和近似的 本身不自动构成严格的机器级包围。
为什么小步长还需要压缩常数
当 接近一时, 很大。若已证明 ,步长 对当前误差只给出 的界。
常见错误
(小步长不等于小误差)
仅凭 很小就停止,并不构成保证。 处处有 的步长,却没有不动点。满足压缩条件时,可在 低于指定绝对容差时停止;否则这个测试没有同样的保证。需要严格的计算机证明时,还要单独处理舍入误差。
局部吸引与排斥
当起点不确定时,整个区间映回自身很有用。在已知不动点 附近,还可使用局部判据。
命题 6.1.8
(局部吸引与排斥)
设 在 的邻域内连续可微,且 。
- 若 ,则存在 周围的闭区间 , 把它映回自身且在其上为压缩映射; 内每个起点都收敛到 。
- 若 ,则对所有 都有 的迭代不可能收敛到 。
证明
(导数在不动点的连续性)
设 。由连续性,存在闭区间 ,其上 。中值定理给出,对 ,,所以 ;对 内任意两点作同样估计,可知 在 上为压缩映射。由压缩映射定理得第一部分。
设 。连续性给出 周围较小的区间 ,其上 ,于是由中值定理,对 有 。若 ,从某个下标 起各项都留在 内,于是 ,且 。这些距离不断增大,与 矛盾。
排斥部分并未说明离开区间后迭代会去哪里。
例题 6.1.9
(不动点处导数等于一)
时不能由此判定收敛或发散。以 、 为例:当 时,,且 ,故符号不变而绝对值递减;绝对值收敛到某个 ,并满足 ,所以 。相反, 对每个非零起点有 ,绝对值递增,不可能趋于零。两者在零处导数都等于一,不动点都是 。
快速检查
(在 上取 ,从 开始。证明区间不变,计算 ,用最近一步估计 ,并与实际误差比较。)
先求出不动点。
解答 · 答案
,且 。唯一不动点是 ;、。误差界为 ,恰好等于实际误差。这一例中的等号不代表一般的界就是精确误差公式。
Newton 方法
在 处将 线性化,并令切线近似为零,得到
其中要求 。在单根附近,Newton 方法可以比二分法快得多;但更新可能离开原区间,也可能遇到零导数。
定义 6.1.10
(单根与二次收敛)
若可微函数 的根 满足 ,则称 为单根。若存在常数 ,使得对所有充分大的 都有 ,则称序列 二次收敛。
例题 6.1.11
(Newton 迭代逼近 2 的平方根)
对 ,从 出发,更新式为 。因此 ,。误差依次为 、、。比值 与 保持有界,与二次收敛的预测一致;正确的位数大约每步加倍。验算:,,所以 的残差为 。
概念视角分析
把 Newton 法看作不动点迭代
Newton 更新就是 的不动点迭代,其不动点正是 的根。当 并且 时,求导得 ,它在单根处为零。于是局部吸引定理适用,而且在 附近收缩常数可以取得任意小,这解释了为什么 Newton 法的收敛比任何线性速度都快。对于 ,,而 。
定理 6.1.12
(Newton 方法的局部二次收敛)
设 在根 的某个邻域上属于 , 且 。当起点充分接近 时,Newton 迭代有定义并收敛到 ,而且存在常数 ,使 。
证明
(Taylor 余项与缩小的邻域)
缩小邻域为 周围的闭区间,使其上 且 。从 向 应用 Taylor 定理,得到 。因此下一步误差的绝对值至多为 ,其中 。取半径 使 的初始邻域,每一步都有 ;迭代点始终留在邻域内且误差按几何速度下降,平方误差界于是每一步都适用。
证明透视
每个条件用在哪里
两个常数来源不同。 加上 的连续性,在整个区间上给出下界 ,使更新式中的除法有意义,并控制 。 条件给出 Taylor 余项所需的上界 。证明中不易察觉的一步是半径的选取:单凭平方误差界,不能阻止下一个迭代点跑出度量 和 的区间。要求 把平方不等式变成 ,这样迭代点才留在区间内,归纳得以完成。若去掉 ,就不存在正数 ,论证也得不到常数 。
单根条件很重要:对 ,Newton 更新为 ;非零初值只有线性收敛。不好的起点即使在有单根时也可能失败。
反例模式
每一步都有定义却不收敛
命题:若每一步都有 ,则 Newton 方法收敛到某个根。取 、。此时 ,,故 。接着 ,,故 。迭代永远在 之间循环,两点的导数都不为零,函数值 和 也从不为零。实根约在 。修正方法是采用定理的局部条件:只有起点充分接近单根时才有收敛保证。
下方演示从 开始,这是上面由 算出的第一个 Newton 迭代值。独立的二分法从宽度为 的 开始,要使中点误差界小于 需九次二分;下面第一道练习的初始宽度是 ,需要十次。双周期与零导数案例说明 Newton 步骤本身不是夹根证书。
缩小的根包围区间能认证其中点
比较根的包围区间与独立 Newton 序列,准确计算已保留的二分次数、检查下一次切线提案,并分清已证误差界、小残差与重复的存储数值。
两个序列各有自己的状态
I_k 是经 k 次中点符号测试后保留的区间。目前中点 m_k 会为显示而计算,但尚未用它再二分。Newton 独立要求 k 次更新;若更早停止,完成次数就停在该值。更改案例会重设 k,更改容限则保留目前状态。
f(x)=x²−2; I0=[1,2]; Newton x0=3/2.
目前包围区间与 Newton 切线
垂直阴影带是 I_k,短虚线标示其中点,空心菱形位于 (m_k,f(m_k))。实心圆是目前 Newton 点 (x,f(x)),长虚线为切线;导数为零时切线是水平线。只有流程仍继续时,轴上的 × 才标示下一提案;停止后不再显示提案。曲线仅用采样绘图,认证来自精确区间运算与表格。极窄阴影带可能小于一像素。
目前保留区间 I_k: [1,2]; 目前中点 m_k: 3/2; Newton 迭代值 x: 1.500000; 流程状态: 继续.
| 保留二分次数 k | 目前保留区间 I_k | 目前中点 m_k | 精确 f(m_k) | 已认证中点误差界 |
|---|---|---|---|---|
| 0 | [1,2] | 3/2 | 1/4 | 1/2 |
| Newton 已完成更新次数 | Newton 迭代值 x | Newton 残差 |f(x)|,仅供演示 | x 处导数 | 下一次切线提案 | 流程状态 |
|---|---|---|---|---|---|
| 0 | 1.500000 | 0.250000 | 3.000000 | 1.416667 | 继续 |
二分表用精确分数显示。对这些明确乘加多项式,k≤12 的二进有理端点与中点计算所需有效二进位少于 53;专项核对另以整数运算验证每个符号与值。Newton 使用普通 Number 算术及四舍五入标签,并非一般的经过验证的符号 Newton 求解器。
已显示 Newton 下一提案。二分认证属于 m_k,没有套用到此 Newton 迭代值。
- 目前区间宽度
- 1
- 已认证中点误差界
- 1/2
- 容限 τ
- 1/1000
- 首次足够的保留二分次数
- 9
- 宽度界已认证所需容限
- 尚未
- Newton 已完成更新次数
- 0
- 流程状态
- 继续
k=0; 目前中点 m_k: 3/2; 已认证中点误差界: 1/2. 此宽度界尚未认证所需容限。实际中点误差可能已更小,并未证明实际精度不达标。 Newton 已完成更新次数: 0; 流程状态: 继续.
哪一项陈述提供误差认证?
两个多项式都连续。x²−2 在 [1,2] 端点异号,导数 2x≥2,因此根唯一。x³−2x+2 在 [−2,−1] 的端点值为 −2、3,导数 3x²−2≥1,同样只有一根。异号要配合连续性才能保证存在,单靠符号也不是检测所有根的一般方法。
二分法用已测中点替换同号端点,保留异号区间并将宽度减半。初始宽度为一,I_k 宽度是 2⁻ᵏ,目前中点与区间内根的距离至多 2⁻ᵏ⁻¹。τ=1/d 时,精确充分条件为 d≤2^(k+1),d=10、100、1000 分别需 k=3、6、9。k=0 的初始中点已有 1/2 界;计算它本身不算一次已保留二分。
对 x²−2,首四个已测中点为 3/2、5/4、11/8、23/16,值为 1/4、−7/16、−7/64、17/256。四次二分后保留 [11/8,23/16],下一中点是 45/32,误差至多 1/32。九次二分给第十个中点,界为 1/1024<1/1000。此为最坏情况包围界,并非声称实际误差恰好等于它。
Newton 解切线方程 f(x)+f'(x)(t−x)=0,在 f'(x)≠0 时得 N(x)=x−f(x)/f'(x)。对 x²−2,有 N(x)=(x+2/x)/2,从 3/2 起得到 17/12、577/408。x>0 时的精确恒等式 N(x)−√2=(x−√2)²/(2x) 解释快速改善。一般的局部二次界需要导数远离零、f'' 有界,且迭代留在相应邻域。任意起点未必满足;本图三次式有精确 0→1→0 周期,零导数案例则没有 Newton 提案。
残差是函数值,不是距离。g(x)=10⁻¹²(x−1) 在 x=0 的残差为 10⁻¹²,根误差却为一。|x−α|≤|f(x)|/μ 需要到根的整段路径上 |f'|≥μ>0,并非只在所示点成立。四舍五入的零或重复浮点数同样不是精确根证明。此处区间认证基于连续性、唯一性及有限二进有理计算的精确符号,没有转移到区间外的 Newton 点。
即时检查:保留九次二分后,获认证的是第九还是第十个中点?
是第十个;如果原中点编号为 m0,就是 m9。九次更新保留宽度 1/512 的 I9,其中点的界是 1/1024。如果只测 m0 至 m8,目前区间会不同,不能因此将 m8 称为具有该界的中点。
三个固定案例、最多 12 次二分及三个容限。Newton 遇到零导数或存储值重复就停止,不暗中切换二分。不实现带保护的混合算法、任意函数验证、精确 Newton 运算或真实误差神谕;本课讨论残差、步长与夹根区间;并未推导带保护的混合算法。
常见错误
(残差小不等于根误差小)
若在 与根 之间有 ,中值定理给出 。当 很小时此界可能很大: 在零处的残差为 ,根误差却为一。稳健实现应按合适尺度检查残差,并检查步长和迭代次数上限;若同时维持端点异号的区间,还可获得独立的误差保证。浮点舍入最终可能阻止任一测试值继续下降。
练习与解答
快速检查
(初始区间长度为 。二分多少次可保证中点误差不超过 ?)
使用中点误差界 。
解答 · 答案
中点误差至多为 。由于 而 ,十次足够,且是此界所能保证的最小次数。
快速检查
(验证 把 映到自身且在其上为压缩映射,并找出该区间内的不动点。)
求 的最小值和 的取值范围。
解答 · 答案
,且 在区间内的最小值为 ;故 ,区间映回自身。此外, 从 递增到 ,所以其绝对值至多为 。正的不动点满足 。
快速检查
(对 应用 Newton 方法,求非零迭代点的收敛因子。)
化简 。
解答 · 答案
当 时,,故线性收敛,因子为 。