首页 Math 计算方法

# 二分法

区间 [ak,bk][a_k,b_k] 的长度为

bk−ak=12k(b−a)b_k-a_k=\frac{1}{2^k}(b-a)

二分后取有根区间 [ak,bk][a_k,b_k] 的中点 xk=12(ak+bk)x_k=\frac{1}{2}(a_k+b_k) 作为 f(x)=0f(x)=0 的根的近似值

误差为

∣x∗−xk∣≤12(bk−ak)=bk+1−ak+1=12k+1(b−a)|x^*-x_k|\leq \frac{1}{2}(b_k-a_k)=b_{k+1}-a_{k+1}=\frac{1}{2^{k+1}}(b-a)

# 迭代法

设迭代函数 φ(x)\varphi(x) 连续，那么，当选取 x0x_0 后，若产生的序列 {xn}{\{x_n\}} 收敛，则一定收敛到 x∗x^* 上

证明

设 xn+1=φ(xn)x_{n+1}=\varphi(x_n) ，且 lim⁡n→∞xn+1=xˉ\lim\limits_{n\to \infty}x_{n+1}=\bar x，所以

lim⁡n→∞xn+1=lim⁡n→∞φ(xn)\lim_{n\to \infty} x_{n+1}=\lim_{n\to \infty}\varphi(x_n)

又因为 φ(x)\varphi(x) 连续，所以

lim⁡n→∞xn+1=φ(lim⁡n→∞xn)xˉ=φ(xˉ)\lim_{n\to\infty}x_{n+1}=\varphi(\lim_{n\to\infty}x_n)\\ \bar x=\varphi(\bar x)

因此 xˉ\bar x 是方程 x=φ(x)x=\varphi(x) 的根

设迭代函数 φ(x)\varphi(x) 在 [a,b][a,b] 上具有连续的一阶导数，且

  • 当 x∈[a,b]x\in [a,b]，a≤φ(x)≤ba\leq \varphi(x)\leq b
  • 存在正数 L<1L<1，对任意 x∈[a,b]x\in [a,b]，有 ∣φ′(x)∣≤L<1|\varphi'(x)|\leq L<1 成立，则 φ(x)\varphi(x) 在 [a,b][a,b] 上有唯一解 x∗x^*，且对任意初始近似值 x0∈[a,b]x_0\in[a,b]，迭代过程 xk+1=φ(xk)(0,1,2,...)x_{k+1}=\varphi(x_k)(0,1,2,...) 收敛，且 lim⁡h→∞xk=x∗\lim\limits_{h\to\infty}x_k=x^*
证明

证明 x∗x^* 存在性：

因为在 [a,b][a,b] 存在 φ′(x)\varphi'(x)，所以 φ(x)\varphi(x) 连续

作函数

g(x)=x−φ(x)g(x)=x-\varphi(x)

则 g(x)g(x) 在 [a,b][a,b] 上连续

因为

g(a)=a−φ(a)≤0g(b)=b−φ(b)≥0g(a)=a-\varphi(a)\leq 0\\ g(b)=b-\varphi(b)\geq 0

所以必存在 x∗∈[a,b]x^*\in[a,b]，使

g(x∗)=0g(x^*)=0

即

x∗=φ(x∗)x^*=\varphi(x^*)

证明 x∗x^* 的唯一性：

若在 [a,b][a,b] 上另有 xˉ∗\bar x^* 也满足 xˉ∗=φ(xˉ∗)\bar x^*=\varphi(\bar x^*)，则由微分中值定理

x∗−xˉ∗=φ(x∗)−φ(xˉ∗)=φ′(ξ)(x∗−xˉ∗)x^*-\bar x^*=\varphi(x^*)-\varphi(\bar x^*)=\varphi'(\xi)(x^*-\bar x^*)

即

(x∗−xˉ∗)[1−φ′(ξ)]=0(x^*-\bar x^*)[1-\varphi'(\xi)]=0

因为 φ(ξ)<1\varphi(\xi)<1

所以只能是

x∗=xˉ∗x^*=\bar x^*

证明收敛性：

由中值定理

x∗−xk+1=φ(x∗)−φ(xk)=φ′(ξ)(x∗−xk)x^*-x_{k+1}=\varphi(x^*)-\varphi(x_k)=\varphi'(\xi)(x^*-x_k)

因为

φ′(ξ)≤L\varphi'(\xi)\leq L

所以

∣x∗−xk+1∣≤L∣x∗−xk∣|x^*-x_{k+1}|\leq L|x^*-x_k|

由归纳法可知

∣x∗−xk∣≤Lk∣x∗−x0∣|x^*-x_k|\leq L^k|x^*-x_0|

因为 L<1L<1

所以

lim⁡k→∞∣x∗−xk∣≤lim⁡k→∞Lk∣x∗−x0∣=0\lim_{k\to\infty}|x^*-x_k|\leq \lim_{k\to\infty} L^k|x^*-x_0|=0

即

lim⁡k→∞xk=x∗\lim_{k\to\infty}x_k=x^*

在上述定理的条件下，由误差估计式

∣x∗−xk∣≤11−L∣xk+1−xk∣−−①∣x∗−xk∣≤Lk1−L∣x1−x0∣−−②|x^*-x_k|\leq \frac{1}{1-L}|x_{k+1}-x_k|--①\\ |x^*-x_k|\leq \frac{L^k}{1-L}|x_1-x_0|--②

证明

证明①

∣xk+1−xk∣=∣x∗−xk−(x∗−xk+1)∣≥∣x∗−xk∣−∣x∗−xk+1∣≥(1−L)∣x∗−xk∣\begin{aligned} |x_{k+1}-x_k|&=|x^*-x_k-(x^*-x_{k+1})|\\ &\geq |x^*-x_k|-|x^*-x_{k+1}|\\ &\geq (1-L)|x^*-x_k| \end{aligned}

∣x∗−xk∣≤11−L∣xk+1−xk∣|x^*-x_k|\leq \frac{1}{1-L}|x_{k+1}-x_k|

证明②

∣xk+1−xk∣=∣φ(xk)−φ(xk−1)∣=∣φ′(ξ)(xk−xk−1)∣≤L∣xk−xk−1∣\begin{aligned} |x_{k+1}-x_k|&=|\varphi(x_k)-\varphi(x_{k-1})|\\ &=|\varphi'(\xi)(x_k-x_{k-1})|\\ &\leq L|x_k-x_{k-1}| \end{aligned}

所以递推可得

∣x∗−xk∣≤11−L∣xk+1−xk∣≤Lk1−L∣x1−x0∣|x^*-x_k|\leq \frac{1}{1-L}|x_{k+1}-x_k|\leq \frac{L^k}{1-L}|x_1-x_0|

# 局部收敛性

如果存在领域 Δ:∣x−x∗∣≤δ\Delta:|x-x^*|\leq \delta，迭代过程对于任意初值 x0∈Δx_0\in \Delta 均收敛，那么这种在根的邻近具有的收敛性称为局部收敛性

设 φ(x)\varphi(x) 在 x=φ(x)x=\varphi(x) 的根 x∗x^* 邻近有连续的一阶导数，且

φ′(x∗)<1\varphi'(x^*)<1

则迭代过程 xk+1=φ(xk)x_{k+1}=\varphi(x_k) 具有局部收敛性

# 迭代的收敛速度

设序列 {xk}{\{x_k\}} 是收敛于方程 f(x)=0f(x)=0 的根 x∗x^* 的迭代序列，即 x∗=lim⁡k→∞xkx^*=\lim\limits_{k\to\infty}x_k。εk=xk−x∗(k=0,1,2,...,)\varepsilon_k=x_k-x^*(k=0,1,2,...,) 表示各步的迭代误差

若有某个实数 pp 和非零常数 CC，使得

lim⁡k→∞εk+1εkp=C,C≠0\lim_{k\to\infty}\frac{\varepsilon_{k+1}}{\varepsilon_k^p}=C,C\neq 0

则称序列 {xk}{\{x_k\}} 是 pp 阶收敛的

对于迭代过程 xk+1=φ(xk)x_{k+1}=\varphi(x_k)，如果迭代函数 φ(x)\varphi(x) 在所求根 x∗x^* 的邻近有连续的二阶导数，且

∣φ′(x∗)∣<1|\varphi'(x^*)|<1

则有

  1. 当 φ′(x∗)≠0\varphi'(x^*)\neq 0 时，迭代过程为线性收敛
  2. 当 φ′(x∗)=0\varphi'(x^*)=0，而 φ′′(x∗)≠0\varphi''(x^*)\neq 0 时，迭代过程为平方收敛
  3. 当 φ′(x∗)=0,φ′′(x∗)=0,...,φ(p−1)(x∗)=0\varphi'(x^*)=0,\varphi''(x^*)=0,...,\varphi^{(p-1)}(x^*)=0，而 φ(p)≠0\varphi^{(p)}\neq 0 时，迭代过程为 pp 阶收敛
证明

利用泰勒展开，因为一直到 φ(p−1)(x∗)=0\varphi^{(p-1)}(x^*)=0，所以

φ(xk)=φ(x∗)+φ(p)p!(xk−x∗)p\varphi(x_k)=\varphi(x^*)+\frac{\varphi^{(p)}}{p!}(x_k-x^*)^p

化简可得

xk+1−x∗=φ(p)p!(xk−x∗)p⇒εk+1εk→φ(p)p!x_{k+1}-x^*=\frac{\varphi^{(p)}}{p!}(x_k-x^*)^p\\ \Rightarrow \frac{\varepsilon_{k+1}}{\varepsilon{k}}\to \frac{\varphi^{(p)}}{p!}

# 收敛过程的加速

假定 φ′(x)\varphi '(x) 在求根范围内变化不大，令

∣φ′(x)∣≈∣a∣|\varphi'(x)|\approx|a|

如果仅用迭代法

x~k+1=φ(xk)\tilde x_{k+1}=\varphi(x_k)

将误差加上之后

xk+1=x~k+1+a1−a(x~k+1−xk)x_{k+1}=\tilde x_{k+1}+\frac{a}{1-a}(\tilde x_{k+1}-x_k)

# Aitken 加速

因为上述方法要求 φ′(x)\varphi'(x) ，在实际操作中比较麻烦，所以引入 Atiken 加速方法

首先进行两次迭代

xn+1(1)=φ(xn)→x∗−xn+1(1)≈a(x∗−xn)−−①xn+1(2)=φ(xn+1(1))→x∗−xn+1(2)≈a(x∗−xn+1(1))−−②x_{n+1}^{(1)}=\varphi(x_n)\rightarrow x^*-x_{n+1}^{(1)}\approx a(x^*-x_n)--①\\ x_{n+1}^{(2)}=\varphi(x_{n+1}^{(1)})\rightarrow x^*-x_{n+1}^{(2)}\approx a(x^*-x_{n+1}^{(1)})--②

用①式除以②式，整理可得

xk+1=xk+1(2)−(xk+1(2)−xk+1(1))2xk+1(2)−2xk+1(1)+xkx_{k+1}=x_{k+1}^{(2)}-\frac{(x_{k+1}^{(2)}-x_{k+1}^{(1)})^2}{x_{k+1}^{(2)}-2x_{k+1}^{(1)}+x_k}

# 牛顿迭代法

根据一阶泰勒展开

f(x0)+f′(x0)(x−x0)=0f(x_0)+f'(x_0)(x-x_0)=0

设 f′(x0)≠0f'(x_0)\neq 0

那么方程的解为

x=x0−f(x0)f′(x0)x=x_0-\frac{f(x_0)}{f'(x_0)}

迭代方程是

φ(x)=x−f(x0)f′(x0)\varphi(x)=x-\frac{f(x_0)}{f'(x_0)}

# 牛顿法的收敛性

因为

φ′(x)=f(x)⋅f′′(x)[f′(x)]2\varphi'(x)=\frac{f(x)\cdot f''(x)}{[f'(x)]^2}

因为 f(x∗)=0f(x^*)=0，所以

φ′(x)=0\varphi'(x)=0

牛顿法至少是平方收敛

# 几何意义

过曲线 y=f(x)y=f(x) 上对应点 (xk,f(xk))(x_k,f(x_k)) 作切线，其切线方程为

y−f(xk)=f′(xk)(x−xk)y-f(x_k)=f'(x_k)(x-x_k)

此切线方程和 xx 轴的交点，即 x∗x^* 新的近似值 xk+1x_{k+1} 满足方程

f(xk)+f′(xk)(x−xk)=0f(x_k)+f'(x_k)(x-x_k)=0

# 初值的选取

∣f′(x0)∣2>∣f′′(x0)2∣∣f(x0)∣|f'(x_0)|^2>|\frac{f''(x_0)}{2}||f(x_0)|

证明

因为牛顿迭代法只是要求局部收敛，所以对于初值的选取是有要求的

显然对于初值 x0x_0 ，如果 f′(x0)f'(x_0) 非常小，那么它是不能最终迭代到根节点的。例如，对于 f(x0)=0f(x_0)=0 显然就是不可取的

那么我们该如何量化这个初值的选取呢？

我们令 ε1=x1−x,ε0=x0−x\varepsilon_1=x_1-x,\varepsilon_0=x_0-x，分别代表 x1x_1 和 x2x_2 的迭代误差

那么我们显然，需要要求 ∣ε1∣<∣ε0∣|\varepsilon_1|<|\varepsilon_0|

x1=x0−f(x0)f′(x0)x1−x=x0−x−f(x0)f′(x0)ε1=ε0−f(x0)f′(x0)x_1=x_0-\frac{f(x_0)}{f'(x_0)}\\ x_1-x=x_0-x-\frac{f(x_0)}{f'(x_0)}\\ \varepsilon_1=\varepsilon_0-\frac{f(x_0)}{f'(x_0)}

所以

ε1ε0=x0+f′(x0)(x−x0)f′(x0)(x0−x)\frac{\varepsilon_1}{\varepsilon_0}=\frac{x_0+f'(x_0)(x-x_0)}{f'(x_0)(x_0-x)}

f(x)=f(x0)+f′(x0)(x−x0)+12f′′(ξ)(x−x0)2f(x)=f(x0)+f′(η)(x−x0)f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2}f''(\xi)(x-x_0)^2\\ f(x)=f(x_0)+f'(\eta)(x-x_0)

带入得

ε1ε0=f′′(ξ)f(x0)2f′(x0)f′(η)\frac{\varepsilon_1}{\varepsilon_0}=\frac{f''(\xi)f(x_0)}{2f'(x_0)f'(\eta)}

近似可看成

ε1ε0=f′′(x0)f(x0)2f′(x0)2\frac{\varepsilon_1}{\varepsilon_0}=\frac{f''(x_0)f(x_0)}{2f'(x_0)^2}

因为要求 ∣ε1∣<∣ε0∣|\varepsilon_1|<|\varepsilon_0|

所以

ε1ε0=f′′(x0)f(x0)2f′(x0)2<1\frac{\varepsilon_1}{\varepsilon_0}=\frac{f''(x_0)f(x_0)}{2f'(x_0)^2}<1