如果说二分法是一位步步为营的谨慎探险家，通用不动点迭代是一匹不知疲倦的耕马，那么 Newton 法 (Newton-Raphson Method) 便是数值分析世界里的超跑。

在前一篇不动点迭代笔记中，我们证明了只要局部导数满足 ∣g′(x∗)∣<1|g'(x^*)| < 1，迭代序列就能线性收敛。这一发现自然引发了一个雄心勃勃的追问：能否刻意设计一个特殊的迭代映射 g(x)g(x)，使其导数在不动点处完全归零，即 g′(x∗)=0g'(x^*) = 0？

一旦 g′(x∗)=0g'(x^*) = 0，Taylor 展开式中的一阶误差项便被彻底抹除。此时误差不再仅仅按固定常数比例缩减，而是发生质的飞跃：每前进一步，误差便被自身平方一次：

∣en+1∣≈C∣en∣2.|e_{n+1}| \approx C |e_n|^2.

这就是令人惊叹的平方收敛 (Quadratic Convergence)：原本仅有 2 位有效数字的粗糙估计，经过 3 步迭代就会暴增至 4 位、8 位乃至 16 位满双精度！这一最优化不动点设计，正是 Newton 法的精髓。

本篇笔记从三个统一的视角解构 Newton 法：

  1. 几何视角：沿着局部切线寻找与 xx 轴的交点；
  2. Taylor 展开：主动舍弃高阶非线性曲率余项；
  3. 压缩映射：严谨确立单根邻域内的局部压缩性与平方收敛阶。

同时，我们也将剖析其在极值点、拐点振荡与分形吸引盆中的经典失效情形，并利用雅可比矩阵将其自然推广至高维非线性方程组。

从切线模型出发

微分学的核心哲学在于：任何光滑曲线在极小尺度下观察，都近似于一条直线。Newton 法正是将这一局部微元思想转化为算法引擎的绝妙范例。

设 ff 在根邻域内充分可导，xnx_n 为当前的数值估计点。函数在点 (xn,f(xn))(x_n, f(x_n)) 处的切线方程为

y=f(xn)+f′(xn)(x−xn).y = f(x_n) + f'(x_n)(x - x_n).

下一步的近似点 xn+1x_{n+1}，被选为该切线与横坐标轴 xx 的交点。令 y=0y = 0 并解出 xx，立得经典的 Newton 更新公式：

xn+1=xn−f(xn)f′(xn),f′(xn)≠0.x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}, \qquad f'(x_n) \neq 0.

这一更新公式亦可由未知真解 x∗x^* 处的二阶 Taylor 展开直接推导：

0=f(x∗)=f(xn)+f′(xn)(x∗−xn)+Rn,Rn=12f′′(ξn)(x∗−xn)2.0 = f(x^*) = f(x_n) + f'(x_n)(x^* - x_n) + R_n, \qquad R_n = \frac{1}{2} f''(\xi_n)(x^*-x_n)^2.

其中的 Lagrange 余项 RnR_n 是精确成立的：它度量了切线模型所遗漏的非线性曲率，并且在数量级上正比于当前误差的平方 (x∗−xn)2(x^* - x_n)^2。Newton 法暂时忽略 RnR_n，把下一步取为仿射线性模型 Mn(x):=f(xn)+f′(xn)(x−xn)M_n(x) := f(x_n) + f'(x_n)(x-x_n) 的零点。若 ff 本身是纯粹的一次线性函数，则 f′′=0f'' = 0 导致 Rn=0R_n = 0，算法仅需单步即可精确命中真解。

定义Newton 迭代

给定初始猜测 x0x_0，Newton 法生成如下数值序列：

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

只要每一步所需的导数值 f′(xn)f'(x_n) 均非零。

例对二次函数走一步

对 f(x)=x2−2f(x) = x^2 - 2，Newton 映射是

gN(x)=x−x2−22x=12(x+2x),x≠0.g_N(x) = x - \frac{x^2-2}{2x} = \frac{1}{2}\Bigl(x + \frac{2}{x}\Bigr), \qquad x \neq 0.

从 x0=3/2x_0 = 3/2 出发得到 x1=17/12x_1 = 17/12。这只演示更新规则。收敛断言仍需要假设和证明。

这个交互图需要启用 JavaScript。

定义 Newton 映射 gN(x)=x−f(x)/f′(x)g_N(x) = x - f(x)/f'(x)。则 xn+1=gN(xn)x_{n+1} = g_N(x_n)。在 f′(x)≠0f'(x) \neq 0 的点上，

gN(x)=x⟺f(x)=0.g_N(x) = x \quad\Longleftrightarrow\quad f(x) = 0.

只要映射有定义，ff 的根就是 gNg_N 的不动点。f′(x)≠0f'(x) \neq 0 对更新和这组等价都必要。代数等价并不能证明迭代收敛。

牛顿切线与二分括区。牛顿法沿局部切线寻找零点，二分法则持续保留函数值异号的区间。

牛顿切线与二分括区。牛顿法沿局部切线寻找零点，二分法则持续保留函数值异号的区间。

牛顿法沿局部切线寻找零点，二分法则持续保留函数值异号的区间。

局部收敛

定理局部压缩定理

设 gg 在闭区间 [a,b][a,b] 上连续、在内部可导，且 g([a,b])⊆[a,b]g([a,b]) \subseteq [a,b]，并存在常数 0≤L<10 \le L < 1 使内部每点满足 ∣g′(x)∣≤L|g'(x)| \le L。则 gg 在 [a,b][a,b] 上有唯一不动点，并且对每个 x0∈[a,b]x_0 \in [a,b]，迭代 xn+1=g(xn)x_{n+1} = g(x_n) 留在 [a,b][a,b] 里并收敛到该不动点。

完整证明见闭区间上的不动点定理。本处的导数界通过中值定理给出那里的 Lipschitz 条件，其余假设完全一致。

导数界通过中值定理给出压缩估计。自映射让所有迭代留在估计可用的区域里。

定理Newton 法的局部收敛

设 f∈C2[a,b]f \in C^2[a,b]，x∗∈(a,b)x^* \in (a,b) 是单根，即 f(x∗)=0f(x^*) = 0 且 f′(x∗)≠0f'(x^*) \neq 0。则存在 δ>0\delta > 0，使得对每个初值 x0∈[x∗−δ,x∗+δ]x_0 \in [x^*-\delta, x^*+\delta]，Newton 法生成良定义的序列并收敛到 x∗x^*。

根的存在性在此处是前置假设：x∗x^* 是已知的。在验证了压缩性与自映射条件后，局部压缩定理表明 gNg_N 在 [x∗−δ,x∗+δ][x^*-\delta, x^*+\delta] 上存在唯一不动点；而 x∗x^* 本身已是不动点，因此该唯一不动点必为 x∗x^*。在这一局部区间之外，原函数完全可能存在其他根。

收敛性证明依赖两条基础的连续性引理：

引理非零值附近不变成零

设 h ⁣:[a,b]→Rh \colon [a,b] \to \mathbb{R} 在 p∈(a,b)p \in (a,b) 连续。若 h(p)≠0h(p) \neq 0，则存在 δ>0\delta > 0，使 [p−δ,p+δ]⊆[a,b][p-\delta, p+\delta] \subseteq [a,b]，并且该区间上处处 h(x)≠0h(x) \neq 0。

证明

取 ε=∣h(p)∣/2>0\varepsilon = |h(p)|/2 > 0。连续性给出 ρ>0\rho > 0，使 ∣x−p∣<ρ|x-p| < \rho 蕴含 ∣h(x)−h(p)∣<∣h(p)∣/2|h(x)-h(p)| < |h(p)|/2。因为 p∈(a,b)p \in (a,b)，数 δ=12min⁡(ρ,p−a,b−p)\delta = \tfrac{1}{2}\min(\rho, p-a, b-p) 为正，且满足 [p−δ,p+δ]⊆[a,b][p-\delta,p+\delta] \subseteq [a,b] 以及 δ<ρ\delta < \rho。若 xx 落在该区间，反向三角不等式给出 ∣h(x)∣≥∣h(p)∣−∣h(x)−h(p)∣>∣h(p)∣/2>0|h(x)| \ge |h(p)| - |h(x)-h(p)| > |h(p)|/2 > 0。

引理零点附近可以任意小

设 h ⁣:[a,b]→Rh \colon [a,b] \to \mathbb{R} 在 p∈(a,b)p \in (a,b) 连续且 h(p)=0h(p) = 0。则对每个 K>0K > 0，存在 δ>0\delta > 0，使 [p−δ,p+δ]⊆[a,b][p-\delta,p+\delta] \subseteq [a,b]，并且该区间上 ∣h(x)∣≤K|h(x)| \le K。

证明

固定 K>0K > 0。用 ε=K\varepsilon = K 的连续性给出 ρ>0\rho > 0，使 ∣x−p∣<ρ|x-p| < \rho 蕴含 ∣h(x)∣<K|h(x)| < K。取 δ=12min⁡(ρ,p−a,b−p)>0\delta = \tfrac{1}{2}\min(\rho, p-a, b-p) > 0。则闭区间上 ∣x−p∣≤δ<ρ|x-p| \le \delta < \rho，故 ∣h(x)∣≤K|h(x)| \le K。

故意取更小的半径 δ<ρ\delta < \rho：连续性给的是 ∣x−p∣<ρ|x-p| < \rho，而引理需要闭区间 ∣x−p∣≤δ|x-p| \le \delta。把第一条用在 h=f′h = f'，把第二条用在 h=gN′h = g_N'，并取 K=L<1K = L < 1。

证明

第一步。 因为 f∈C2[a,b]f \in C^2[a,b]，f′f' 连续，且 f′(x∗)≠0f'(x^*) \neq 0。非零引理用于 h=f′h = f'、p=x∗p = x^*，给出 δ0>0\delta_0 > 0，使 I0=[x∗−δ0,x∗+δ0]⊆[a,b]I_0 = [x^*-\delta_0, x^*+\delta_0] \subseteq [a,b] 且 f′f' 在 I0I_0 上不为零。于是 g:=gNg := g_N 在整个 I0I_0 上有定义。

第二步。 在 I0I_0 上求导得到

g′(x)=f(x)f′′(x)(f′(x))2.g'(x) = \frac{f(x)f''(x)}{(f'(x))^2}.

由 f(x∗)=0f(x^*) = 0 得 g′(x∗)=0g'(x^*) = 0。任取 0<L<10 < L < 1。小值引理用于 h=g′h = g'、K=LK = L，给出半径 δ>0\delta > 0，使 I=[x∗−δ,x∗+δ]⊆I0I = [x^*-\delta, x^*+\delta] \subseteq I_0 且 ∣g′(x)∣≤L|g'(x)| \le L 在 II 上成立。于是 gg 在 II 上压缩。

第三步。 根条件给出 g(x∗)=x∗g(x^*) = x^*。设 x∈Ix \in I。若 x=x∗x = x^*，则 g(x)∈Ig(x) \in I。否则中值定理给出介于 xx 与 x∗x^* 之间、因而也在 II 里的 ξ\xi，且

∣g(x)−x∗∣=∣g′(ξ)∣ ∣x−x∗∣≤Lδ<δ.|g(x) - x^*| = |g'(\xi)|\,|x-x^*| \le L\delta < \delta.

因此 g(I)⊆Ig(I) \subseteq I。

第四步。 在 II 上，gg 满足局部压缩定理。从 II 出发的每条 Newton 序列都良定义，并收敛到唯一不动点，而这个不动点只能是 x∗x^*。这是局部结论：定理只断言充分靠近的初值会收敛。

逻辑蕴含是单向的：上述假设是保证局部收敛的充分条件而非必要条件。常见的认知误区包括：把充分条件误当作必要条件；将单点导数 g′(x∗)=0g'(x^*) = 0 误认为是全域上的全局压缩；以及在导数极小或为零（f′(xn)≈0f'(x_n) \approx 0）的病态区域强行更新。

收敛阶

定义收敛阶

设 xk→x∗x_k \to x^*。若存在常数 c>0c > 0 和 k0k_0，使

∣x∗−xk+1∣≤c∣x∗−xk∣p对一切 k≥k0|x^* - x_{k+1}| \le c |x^* - x_k|^p \qquad \text{对一切 } k \ge k_0

成立，就称序列以至少 p≥1p \ge 1 阶收敛。若存在最大的这样的指数，就称它为收敛阶。p=2p=2 给出至少二次收敛。p=1p=1 若要给出线性收缩，还需可以取 c<1c<1；任意 c>0c>0 的界也容许次线性收敛。

单侧误差界确立的是收敛阶“至少为 pp”，并不要求计算出精确的渐近常数。更高的阶数 pp 意味着一旦迭代点进入局部收敛区，误差将以极快的速率急剧衰减。

命题一阶导数分类

设 xk+1=g(xk)x_{k+1} = g(x_k) 收敛到 x∗x^* 且不在有限步到达，并设 gg 在 x∗x^* 可导。则 g(x∗)=x∗g(x^*) = x^*，且

∣xk+1−x∗∣∣xk−x∗∣→∣g′(x∗)∣.\frac{|x_{k+1}-x^*|}{|x_k-x^*|} \to |g'(x^*)|.

因此 0<∣g′(x∗)∣<10 < |g'(x^*)| < 1 给出线性收敛，g′(x∗)=0g'(x^*) = 0 给出超线性收敛，∣g′(x∗)∣=1|g'(x^*)| = 1 得不出结论。

证明

可导蕴含连续，在 xk+1=g(xk)x_{k+1} = g(x_k) 里取极限得 g(x∗)=x∗g(x^*) = x^*。再用导数定义得到上述比值极限。若该极限大于 11，不在有限步终止的序列就不可能收敛到 x∗x^*。

命题高阶导数检验

设 p≥2p \ge 2 为正整数，gg 在 x∗x^* 附近属于 CpC^p，且 xk+1=g(xk)→x∗x_{k+1} = g(x_k) \to x^*，同时对 0<n<p0 < n < p 有 g(n)(x∗)=0g^{(n)}(x^*) = 0。则迭代至少 pp 阶。若 g(p)(x∗)≠0g^{(p)}(x^*) \neq 0 且迭代不在有限步终止，则精确阶是 pp，渐近常数是 ∣g(p)(x∗)∣/p!|g^{(p)}(x^*)|/p!。

证明

Taylor 定理给出介于 xkx_k 与 x∗x^* 之间的 ξk\xi_k，使 xk+1−x∗=g(p)(ξk)(xk−x∗)p/p!x_{k+1}-x^* = g^{(p)}(\xi_k)(x_k-x^*)^p / p!。因为 ξk→x∗\xi_k \to x^*，g(p)g^{(p)} 的连续性既给出至少 pp 阶的界，又在 g(p)(x∗)≠0g^{(p)}(x^*) \neq 0 时给出所述常数。

推论Newton 法的二次收敛

若 ff 在单根 x∗x^* 附近属于 C2C^2，则 Newton 映射满足 gN′(x∗)=0g_N'(x^*) = 0。因此在局部收敛定理的局部区里，Newton 法至少二阶。

证明

仅由一阶导数为零只能推出超线性收敛，因此这里直接使用 C2C^2 条件。在 xkx_k 处展开得

0=f(x∗)=f(xk)+f′(xk)(x∗−xk)+12f′′(ξk)(x∗−xk)2.0=f(x^*)=f(x_k)+f'(x_k)(x^*-x_k)+\tfrac12f''(\xi_k)(x^*-x_k)^2.

代入 Newton 更新，得到

∣xk+1−x∗∣=∣f′′(ξk)2f′(xk)∣∣xk−x∗∣2.|x_{k+1}-x^*|=\left|\frac{f''(\xi_k)}{2f'(x_k)}\right||x_k-x^*|^2.

连续性使局部分子有界、分母远离零，因而给出统一的二次误差界，无须假设 Newton 映射本身二次可微。

对有限重数 m>1m>1 的根，写 f(x)=(x−x∗)mh(x)f(x)=(x-x^*)^m h(x)，其中 h(x∗)≠0h(x^*)\ne0，且 hh 局部属于 C1C^1。代入 Newton 更新得

gN(x)−x∗=(x−x∗)(1−h(x)mh(x)+(x−x∗)h′(x)).g_N(x)-x^*=(x-x^*)\left(1-\frac{h(x)}{mh(x)+(x-x^*)h'(x)}\right).

括号内因子趋于 1−1/m∈(0,1)1-1/m\in(0,1)，故不在有限步终止的局部迭代为线性收敛。这个结论依赖有限重数结构；仅仅导数为零不能推出收敛。

停机准则

定理压缩映射的后验界

设 xk+1=g(xk)x_{k+1} = g(x_k) 有不动点 x∗x^*，且 gg 在包含相关迭代的区间上是压缩，压缩因子 0≤λ<10 \le \lambda < 1。则

∣x∗−xk+1∣≤λ1−λ ∣xk+1−xk∣.|x^* - x_{k+1}| \le \frac{\lambda}{1-\lambda}\, |x_{k+1}-x_k|.
证明

令 ek=∣x∗−xk∣e_k = |x^*-x_k|。压缩估计给出 ek+1≤λeke_{k+1} \le \lambda e_k。由反向三角不等式，∣xk+1−xk∣≥ek−ek+1≥(1−λ)ek|x_{k+1}-x_k| \ge e_k - e_{k+1} \ge (1-\lambda)e_k。再与 ek+1≤λeke_{k+1} \le \lambda e_k 合起来即得。

当 0<λ<10 < \lambda < 1 时，只在 ∣xk+1−xk∣<1−λλε|x_{k+1}-x_k| < \frac{1-\lambda}{\lambda}\varepsilon 之后停机。定理于是保证 ∣x∗−xk+1∣<ε|x^*-x_{k+1}| < \varepsilon。这条规则需要 λ\lambda 的一个有效上界。

定理超线性区里的步长

设 xk→x∗x_k \to x^* 且至少 p>1p > 1 阶，并假定迭代不在有限步到达 x∗x^*。令 ek=∣x∗−xk∣e_k = |x^*-x_k|，且对充分大的 kk 有 ek+1≤cekpe_{k+1} \le c e_k^p。则

ek+1ek→0,∣xk+1−xk∣ek→1,ek+1∣xk+1−xk∣→0.\frac{e_{k+1}}{e_k} \to 0, \qquad \frac{|x_{k+1}-x_k|}{e_k} \to 1, \qquad \frac{e_{k+1}}{|x_{k+1}-x_k|} \to 0.
证明

把阶估计除以 eke_k，得到 0≤ek+1/ek≤cekp−1→00 \le e_{k+1}/e_k \le c e_k^{p-1} \to 0。三角与反向三角不等式给出 ek−ek+1≤∣xk+1−xk∣≤ek+ek+1e_k - e_{k+1} \le |x_{k+1}-x_k| \le e_k + e_{k+1}。除以 eke_k 并用夹逼定理得到中间那个极限，再把第一个商除掉它得到最后一个。

在超线性区，∣x∗−xk∣≈∣xk+1−xk∣|x^*-x_k| \approx |x_{k+1}-x_k|，而下一步的误差比刚走的步长短得多。实用检验 ∣xk+1−xk∣<ε|x_{k+1}-x_k| < \varepsilon 因此是保守的渐近代理，不是全局证书，除非另有局部信息。

非线性方程组

定义Jacobian 矩阵

设 F⃗ ⁣:Ω⊂Rn→Rn\vec{F} \colon \Omega \subset \mathbb{R}^n \to \mathbb{R}^n 在开集 Ω\Omega 上可导，状态为 x⃗=(x1,…,xn)T\vec{x} = (x_1,\dots,x_n)^T，残差为 F⃗(x⃗)=(F1(x⃗),…,Fn(x⃗))T\vec{F}(\vec{x}) = (F_1(\vec{x}),\dots,F_n(\vec{x}))^T。它的 Jacobian 矩阵 DF⃗(x⃗)D\vec{F}(\vec{x}) 是一阶偏导数组成的 n×nn \times n 矩阵，(i,j)(i,j) 元是 ∂Fi/∂xj\partial F_i / \partial x_j。

命题非线性方程组的 Newton 迭代

设 α⃗∈Ω\vec{\alpha} \in \Omega 是精确根，F⃗(α⃗)=0⃗\vec{F}(\vec{\alpha}) = \vec{0}。设 x⃗k∈Ω\vec{x}_k \in \Omega 是当前近似，且 DF⃗(x⃗k)D\vec{F}(\vec{x}_k) 非奇异。下一步 Newton 迭代由求解

DF⃗(x⃗k) s⃗k=−F⃗(x⃗k),x⃗k+1=x⃗k+s⃗kD\vec{F}(\vec{x}_k)\, \vec{s}_k = -\vec{F}(\vec{x}_k), \qquad \vec{x}_{k+1} = \vec{x}_k + \vec{s}_k

得到。等价地，x⃗k+1=x⃗k−[DF⃗(x⃗k)]−1F⃗(x⃗k)\vec{x}_{k+1} = \vec{x}_k - [D\vec{F}(\vec{x}_k)]^{-1}\vec{F}(\vec{x}_k)，但应当解线性方程组，而不是去求 Jacobian 的逆。

证明

各分量在 x⃗k\vec{x}_k 处作 Taylor 展开、再在根处求值，叠成

0⃗=F⃗(x⃗k)+DF⃗(x⃗k)(α⃗−x⃗k)+r⃗k,\vec{0} = \vec{F}(\vec{x}_k) + D\vec{F}(\vec{x}_k)(\vec{\alpha}-\vec{x}_k) + \vec{r}_k,

可微性给出的余项是 o(∥α⃗−x⃗k∥)o(\|\vec{\alpha}-\vec{x}_k\|)。Jacobian 局部 Lipschitz 时，例如满足 C2C^2 正则性，才能加强为二次余项。丢掉余项，定义仿射模型 M⃗k(x⃗):=F⃗(x⃗k)+DF⃗(x⃗k)(x⃗−x⃗k)\vec{M}_k(\vec{x}) := \vec{F}(\vec{x}_k) + D\vec{F}(\vec{x}_k)(\vec{x}-\vec{x}_k)。下一步取成这个模型的精确根，整理即得所述线性方程组。

定理方程组的局部二次收敛

设 F⃗\vec{F} 在根 α⃗\vec{\alpha} 附近属于 C2C^2，且 DF⃗(α⃗)D\vec{F}(\vec{\alpha}) 非奇异。则存在 α⃗\vec{\alpha} 的一个邻域，使得每个充分靠近的 x⃗0\vec{x}_0 都生成良定义的 Newton 迭代，并满足 ∥α⃗−x⃗k+1∥≤c∥α⃗−x⃗k∥2\|\vec{\alpha}-\vec{x}_{k+1}\| \le c \|\vec{\alpha}-\vec{x}_k\|^2，其中 c>0c > 0。

证明

令 e⃗k=x⃗k−α⃗\vec{e}_k = \vec{x}_k - \vec{\alpha}。Taylor 定理给出 0⃗=F⃗(x⃗k)−DF⃗(x⃗k)e⃗k+r⃗k\vec{0} = \vec{F}(\vec{x}_k) - D\vec{F}(\vec{x}_k)\vec{e}_k + \vec{r}_k，局部地 ∥r⃗k∥≤M∥e⃗k∥2\|\vec{r}_k\| \le M \|\vec{e}_k\|^2。附近的 Jacobian 保持非奇异，逆一致有界，范数至多 BB。代入 Newton 步得到 e⃗k+1=[DF⃗(x⃗k)]−1r⃗k\vec{e}_{k+1} = [D\vec{F}(\vec{x}_k)]^{-1}\vec{r}_k，从而 ∥e⃗k+1∥≤BM∥e⃗k∥2\|\vec{e}_{k+1}\| \le BM \|\vec{e}_k\|^2。

统一逆界也需验证。令 J∗=DF(α)J_*=DF(\alpha)，缩小球邻域，使 H=J∗−1(DF(x)−J∗)H=J_*^{-1}(DF(x)-J_*) 的范数至多为 1/21/2。收敛矩阵几何级数 ∑j≥0(−H)j\sum_{j\ge0}(-H)^j 是 I+HI+H 的逆：先乘有限部分和，再令剩余幂趋零即可。因此整个球内都有 ∥DF(x)−1∥≤2∥J∗−1∥\|DF(x)^{-1}\|\le2\|J_*^{-1}\|。进一步缩小半径 δ\delta，使 BMδ≤1/2BM\delta\le1/2，二次界便保证每步仍在球内且误差至少减半，证明整个序列良定义并收敛。余项界则由沿根与当前点间线段积分局部 Lipschitz 的 Jacobian 得到。

多维非线性系统 Newton 法的标准求解四步法：

  1. 建立残差方程组 F⃗(x⃗)=0⃗\vec{F}(\vec{x}) = \vec{0}。
  2. 计算 Jacobian 矩阵 DF⃗(x⃗)D\vec{F}(\vec{x}) 并核验其在当前点的非奇异性（det⁡DF⃗≠0\det D\vec{F} \neq 0）。
  3. 求解线性方程组 DF⃗(x⃗k)s⃗k=−F⃗(x⃗k)D\vec{F}(\vec{x}_k)\vec{s}_k = -\vec{F}(\vec{x}_k) 获得更新步长 s⃗k\vec{s}_k。
  4. 执行状态更新 x⃗k+1=x⃗k+s⃗k\vec{x}_{k+1} = \vec{x}_k + \vec{s}_k，并同步检验步长范数 ∥s⃗k∥\|\vec{s}_k\| 与残差范数 ∥F⃗(x⃗k+1)∥\|\vec{F}(\vec{x}_{k+1})\|。
例平面两连杆机械臂

平面机械臂有杆长 L1,L2>0L_1, L_2 > 0 和关节角 θ1,θ2\theta_1, \theta_2。给定目标 (xd,yd)(x_d, y_d)，求使第二杆末端落到该点的关节角。令 r=xd2+yd2r = \sqrt{x_d^2 + y_d^2}。目标可到达，仅当 ∣L1−L2∣≤r≤L1+L2|L_1-L_2| \le r \le L_1+L_2。

把两杆分解到水平和竖直方向：

x(θ1,θ2)=L1cos⁡θ1+L2cos⁡(θ1+θ2),y(θ1,θ2)=L1sin⁡θ1+L2sin⁡(θ1+θ2).\begin{aligned} x(\theta_1,\theta_2) &= L_1 \cos\theta_1 + L_2 \cos(\theta_1+\theta_2), \\ y(\theta_1,\theta_2) &= L_1 \sin\theta_1 + L_2 \sin(\theta_1+\theta_2). \end{aligned}

残差是 F⃗(θ⃗)=0⃗\vec{F}(\vec{\theta}) = \vec{0}，其中

F1=L1cos⁡θ1+L2cos⁡(θ1+θ2)−xd,F2=L1sin⁡θ1+L2sin⁡(θ1+θ2)−yd.\begin{aligned} F_1 &= L_1 \cos\theta_1 + L_2 \cos(\theta_1+\theta_2) - x_d, \\ F_2 &= L_1 \sin\theta_1 + L_2 \sin(\theta_1+\theta_2) - y_d. \end{aligned}

求导得到

DF⃗(θ⃗)=(−L1sin⁡θ1−L2sin⁡(θ1+θ2)−L2sin⁡(θ1+θ2)L1cos⁡θ1+L2cos⁡(θ1+θ2)L2cos⁡(θ1+θ2)).D\vec{F}(\vec{\theta}) = \begin{pmatrix} -L_1\sin\theta_1 - L_2\sin(\theta_1+\theta_2) & -L_2\sin(\theta_1+\theta_2) \\ L_1\cos\theta_1 + L_2\cos(\theta_1+\theta_2) & L_2\cos(\theta_1+\theta_2) \end{pmatrix}.

短展开给出 det⁡DF⃗(θ⃗)=L1L2sin⁡θ2\det D\vec{F}(\vec{\theta}) = L_1 L_2 \sin\theta_2。Jacobian 可逆当且仅当 sin⁡θ2≠0\sin\theta_2 \neq 0。奇异情形包括完全伸直或完全折叠。

取 L1=1L_1 = 1、L2=0.7L_2 = 0.7、目标 (1.2,0.5)(1.2, 0.5)、初值 θ⃗(0)=(0.3,0.2)T\vec{\theta}^{(0)} = (0.3, 0.2)^T，每一步 Newton 解 DF⃗(θ⃗(k))s⃗k=−F⃗(θ⃗(k))D\vec{F}(\vec{\theta}^{(k)})\vec{s}_k = -\vec{F}(\vec{\theta}^{(k)})，再更新 θ⃗(k+1)=θ⃗(k)+s⃗k\vec{\theta}^{(k+1)} = \vec{\theta}^{(k)} + \vec{s}_k。

割线法与试位法

两种方法都用割线与 xx 轴的交点。割线法保留最新两点，是开方法。试位法保留变号区间，因而带括号。这一区别解释了为什么割线法局部通常更快，而试位法整体更稳。

定义割线法

从两个初值 x0x_0、x1x_1 出发，把 Newton 法里的导数换成最近两点的差分斜率：

xn+1=xn−f(xn)xn−xn−1f(xn)−f(xn−1).x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n)-f(x_{n-1})}.

方法不保持括号。在单根附近的通常局部假设下，阶是 p=(1+5)/2≈1.618p = (1+\sqrt{5})/2 \approx 1.618。前两次函数求值之后，每新一步只需一次新的函数求值，不必求导。

定义试位法

从满足 f(a)f(b)<0f(a)f(b) < 0 的区间 [a,b][a,b] 出发。过两端点的割线与 xx 轴交于

c=b−f(b)b−af(b)−f(a).c = b - f(b)\frac{b-a}{f(b)-f(a)}.

若 f(a)f(c)<0f(a)f(c) < 0，用 cc 替换 bb；否则用 cc 替换 aa。变号括号始终保持。方法至少线性收敛，起初常常比二分快，但当一个端点许多步都不动时可能停滞。

下一篇从解 f(x)=0f(x) = 0 转到用多项式去贴合采样数据：多项式插值。本页属于计算数学阅读路径。