二分法
求解 f(x)=0,首先取一段区间 [a,b],若 f(a)f(b)≤0,说明 [a,b] 区间上存在零点。通过不断地把函数零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值。
假设 a0=a,b0=b,第 k 步迭代的零点区间为 [ak,bk],近似解为 xk=2ak+bk,精确解为 x∗∈[ak,bk]。则 ∣xk−x∗∣=2ak+bk−x∗≤2bk−ak=22bk−1−ak−1=⋯=2k+1b0−a0=2k+1b−a,对于给定的精度 ε,可估计二分法所需的步数 2k+1b−a≤ε,即 k≥log2εb−a−1,取 k=⌈log2εb−a⌉−1。
这里并不打算花费过多笔墨介绍二分法,二分法原理简单,其用途不仅仅于求解非线性方程;二分法在算法竞赛中也有广泛的应用,许多具有单调性的讨论都可用二分法解决。
试值法
由于二分法收敛速度相对较慢,因此试值法对他进行了改进。
若在区间 [a,b] 上有 f(a)f(b)<0,则考虑经过 (a,f(a)) 和 (b,f(b)) 的割线与 x 轴的交点 (c,0) 为更好的近似值。割线方程为 y−f(b)=b−af(b)−f(a)(x−b),令 y=0 得 c=b−f(b)−f(a)f(b)(b−a)。
若 f(a)f(c)<0,则在 [a,c] 内有一个零点;若 f(b)f(c)<0,则 [c,b] 内有一个零点。
不动点迭代
对于非线性方程 f(x)=0,将其等价变换为 x=g(x),g 的不动点 x∗ 就是 f(x)=0 的解。从一个初始值 x0 出发,令 xk+1=g(xk),不断迭代;若 {xk} 收敛,即存在 x∗ 使得 k→∞limxk=x∗;根据迭代数列的产生方式, k→∞limxk+1=k→∞limg(xk),可知 x∗=g(x∗),x∗ 就是 g 的不动点。
不动点存在性
设 g∈C[a,b]。如果对于所有 x∈[a,b],映射 y=g(x) 的范围满足 y∈[a,b],则函数 g 在 [a,b] 内有一个不动点;此外,设 g′(x) 定义在 (a,b) 内,且对于所有 x∈(a,b),存在常数 0≤K<1,使得 ∣g′(x)∣≤K<1,则函数 g 在 [a,b] 内有唯一的不动点。
证明 取 f(x)=g(x)−x,故 f(a)=g(a)−a≥0,f(b)=g(b)−b≤0,所以 [a,b] 上存在 f 的零点,即 [a,b] 上存在 g 的不动点。假设在 [a,b] 上有两个不动点 P1,P2,根据中值定理,存在 ξ∈(a,b),g′(ξ)=P1−P2g(P1)−g(P2)=1,这与 ∣g′(x)∣<1 矛盾,故存在唯一不动点。
收敛阶
不动点迭代中,若迭代数列收敛,且对于真实值 x∗ 有 g(x∗)=0。则 ek+1=xk+1−x∗=g(xk)−g(x∗),由中值定理,存在 ξ∈(min(xk,x∗),max(xk,x∗)) 使得g′(ξ)=xk−x∗g(xk)−g(x∗),故 ek+1=g′(ξ)⋅ek。于是 k→∞lim∣ekek+1∣=g′(x∗)=0,不动点迭代是线性收敛的。