数值计算方法笔记02——方程求根

参考教材：孙志忠, 吴宏伟, 等. 计算方法与实习[M]. 第五版. 南京: 东南大学出版社, 2011:17-49.

零点定理： $f(x)\in C[a,b], \text{单调}, f(a)f(b)<0, \text{则} f(X)=0 \text{在} (a,b) \text{有唯一根}$

方程求根的步骤：

求根的隔离区间
将根精确化

根的隔离区间求法：画草图；多项式函数交点横坐标；试算；函数单调性等

二分法

基本思想：用对分区间的方法根据分点处函数 $f(x)$ 的符号逐步将有根区间缩小，使在足够小的区间内，方程仅有一个根。

使用条件： $f(x)$ 连续、单调、区间端点函数值异号
优点：计算简单，方法可靠
缺点：收敛慢，不能求复根
结论：一般不单独使用，而常用于提供初值的求解

对于给定精度 $\varepsilon$ ，若取 $k$ 使得 $\frac{1}{2^{k+1}}(b-a)\le\varepsilon$ ，则 $|x_k-x^*|\le\varepsilon$

$k\ge\frac{\ln (b-a)-\ln\varepsilon}{\ln2}-1$

function x = divide(a, b, f, e)
    fa = feval(f, a);
    fb = feval(f, b);
    if fa * fb > 0 
        error('函数在两端点必须异号');
    elseif fa == 0 
        x = a;
        return;
    elseif fb == 0
        x = b;
        return;
    end
    x = (b + a) / 2;
    while b - a > 2 * e 
        fx = feval(f, x);
        if fx == 0
            return
        elseif fx * fa < 0
            b = x;
            fb = fx;
        elseif fx * fb < 0
            a = x;
            fa = fx;
        else
            error('???');
        end
        x = (b + a) / 2;
    end
end

迭代法

$f(x)=0$ 改写为 $x=\varphi(x)$ ，$f, \varphi$ 连续（ $\varphi(x)$ 称为迭代函数）

$\left\{\begin{array}{l} x_{n+1}=\varphi(x_n)\\ \text{取定初值} x_0 \end{array}\right.$

则产生数列 $x_1, x_2, \cdots, x_n, x_{n+1}, \cdots$ （迭代序列）

若迭代序列收敛，设极限为 $x^*$ ，则 $\lim_{n\rightarrow\infty}x_{n+1}=\lim_{n\rightarrow\infty}\varphi(x_n)$

所以 $x^*=\varphi(x^*)$

设 $\varphi(x)$ 在 $[a,b]$ 上具有一阶连续的导数且满足

当 $a\le x\le b$ 时， $a\le\varphi(x)\le b$
$\forall x\in[a,b], |\varphi’(x)|\le L\lt1$ ， $L$ 为常数

则：

$x=\varphi(x)$ 在 $[a,b]$ 有唯一根 $x^*$
$\forall x_0\in[a,b], x_{n+1}=\varphi(x_n)$ 收敛到 $x^*$
$|x_k-x^*|\le\frac{L}{1-L}|x_k-x_{k-1}|,k=1,2,\cdots$ （事后误差估计式）
$|x_k-x^*|\le\frac{L^k}{1-L}|x_1-x_0|, k=1,2,\cdots$ （事前误差估计式）
$\lim_{k\rightarrow\infty}\frac{x_{k+1}-x^*}{x_k-x^*}=\varphi’(x^*)$ （渐近误差估计式）

证明见 P23-P24

编程停机判断

设定初值 $x_0$ 由 $x_{k+1}=\varphi(x_k)$ 计算，当 $|x_k-x_{k-1}|\le \varepsilon$ （事后误差估计）时， $|x_k-x^*|\le\frac{L}{1-L}\varepsilon$ 。此时可停机，取 $x_k$ 为近似值。

为了确保误差满足条件，可在连续两次迭代结果都满足所给精度时才停机

设方程在区间 $[a,b]$ 内有根 $x^*$ ，且当 $x\in[a,b]$ 时， $|\varphi’(x)|\ge1$ ，则对任意初始值 $x_0\in[a,b] \land x_0\ne x^*$ ，迭代产生的迭代序列发散。

迭代法的局部收敛性

对于方程 $x=\varphi(x)$ ，若在 $x^*$ 的某个邻域 $S$ 内，对任意初值 $x_0\in S$ ，迭代格式 $x_{k+1}=\varphi(x_k)(k=0,1,2,\cdots)$ 都收敛，则称该迭代格式在 $x^*$ 附近是局部收敛的

设方程 $x=\varphi(x)$ 有根 $x^*$ ，且在 $x^*$ 的某个邻域内 $\varphi(x)$ 存在一阶连续导数，则

当 $|\varphi’(x^*)|\lt1$ 时，迭代局部收敛
当 $|\varphi’(x^*)|\gt1$ 时，迭代发散

这个定理对初值 $x_0$ 的要求较高。如果已知 $x^*$ 的大概位置， $x_0$ 为 $x^*$ 的一个较好的近似值，则可用 $\varphi(x_0)$ 代替 $\varphi(x^*)$ ，然后应用定理判断迭代的局部敛散性。

迭代法的收敛速度

设序列 $\{x_k\}$ 收敛于 $x^*$ ，并记 $e_k=x_k-x^*$ 。如果存在非零常数 $c$ 和正常数 $p$ ，使得 $\lim_{k\rightarrow\infty}\frac{e_{k+1}}{e_k^p}=c$ ，则称序列是 $p$ 阶收敛的。

$p$ 的大小反映了序列收敛速度的快慢。 $p$ 越大，则收敛的越快。当 $p=1$ 且 $0\lt|c|\lt1$ 时，称为线性收敛；当 $p\gt1$ 时，称为超线性收敛。特别地，当 $p=2$ 时，称为平方收敛。

如果一个迭代格式产生的迭代序列是 $p$ 阶收敛的，则称该迭代格式是 $p$ 阶收敛的。

由 $\lim_{k\rightarrow\infty}\frac{x_{k+1}-x^*}{x_k-x^*}=\varphi’(x^*)$ 知，简单迭代法是线性收敛的。

若 $\varphi(x)$ 在 $x^*$ 的某个邻域内有 $p(p\ge1)$ 阶导数，且 $\left\{\begin{array}{l}
\varphi(x^*)=x^*&\\
\varphi^{(k)}(x^*)=0&k=1,2,\cdots,p-1\\
\varphi^{(p)}(x^*)\ne0&
\end{array}\right.$ ，则对一个任意靠近 $x^*$ 的初始值 $x_0$ ，迭代公式 $x_{k+1}=\varphi(x_k)$ 是 $p$ 阶收敛的，且有 $\lim_{k\rightarrow\infty}\frac{x_{k+1}-x^*}{(x_k-x^*)^p}=\frac{\varphi^{(p)}(x^*)}{p!}$ 。如果 $p=1$ ，要求 $|\varphi’(x^*)|\lt1$

埃特金(Aitken)加速法

简单迭代法的收敛速度与迭代函数 $\varphi(x)$ 有关。在许多情况下，可以由 $\varphi(x)$ 构造一个新的迭代函数 $\varPhi(x)$ ，使得

方程 $x=\varPhi(x)$ 和 $x=\varphi(x)$ 具有相同的根 $x^*$
迭代公式 $x_{k+1}=\varPhi(x_k)$ 产生的迭代序列收敛于 $x^*$ 的阶高于由式 $x_{k+1}=\varphi(x_k)$ 产生的迭代序列收敛于 $x^*$ 的阶。

由迭代格式 $x_{k+1}=\varphi(x_k)$ 产生收敛较快的迭代格式 $x_{k+1}=\varPhi(x_k)$ 的方法通常称为加速方法。

设迭代格式 $x_{k+1}=\varphi(x_k)$ 是收敛的，由定理有

$\lim_{k\rightarrow\infty}\frac{x_{k+1}-x^*}{x_k-x^*}=\varphi'(x^*)$

因而当 $k$ 适当大时，有

$\frac{x_{k+2}-x^*}{x_{k+1}-x^*}\approx\frac{x_{k+1}-x^*}{x_k-x^*}$

由此解出

$\begin{aligned} x^*&\approx\frac{x_kx_{k+2}-x_{k+1}^2}{x_{k+2}-2x_{k+1}+x_k}\\ &=\frac{x_k\varphi(\varphi(x_k))-\varphi^2(x_k)}{\varphi(\varphi(x_k))-2\varphi(x_k)+x_k}\\ \end{aligned}$

把上式右端值作为 $\varPhi(x_k)$ ，得到新的迭代格式 $x_{k+1}=\varPhi(x_k)=\frac{x_k\varphi(\varphi(x_k))-\varphi^2(x_k)}{\varphi(\varphi(x_k))-2\varphi(x_k)+x_k}$

$\begin{aligned} \lim_{x\rightarrow x^*}\varPhi(x)&=\lim_{x\rightarrow x^*}\frac{x\varphi(\varphi(x))-\varphi^2(x)}{\varphi(\varphi(x))-2\varphi(x)+x}\\ &=\lim_{x\rightarrow x^*}\frac{\varphi(\varphi(x))+x\varphi'(\varphi(x))\varphi'(x)-2\varphi(x)\varphi'(x)}{\varphi'(\varphi(x))\varphi'(x)-2\varphi'(x)+1}\\ &=\frac{\varphi(\varphi(x^*))+x^*\varphi'(\varphi(x^*))\varphi'(x^*)-2\varphi(x^*)\varphi'(x^*)}{\varphi'(\varphi(x^*))\varphi'(x^*)-2\varphi'(x^*)+1}\\ &=\frac{x^*+x^*\varphi'(x^*)\varphi'(x^*)-2x^*\varphi'(x^*)}{\varphi'(x^*)\varphi'(x^*)-2\varphi'(x^*)+1}\\ &=x^* \end{aligned}$

设在 $x^*$ 附近 $\varphi(x)$ 有 $(p+1)$ 阶连续导数，则对一个充分靠近 $x^*$ 的初始值 $x_0$ ：

如果 $x_{k+1}=\varphi(x_k)$ 是线性收敛的，则 $x_{k+1}=\varPhi(x_k)$ 是二阶收敛的。
如果 $x_{k+1}=\varphi(x_k)$ 是 $p(p\ge2)$ 阶收敛的，则 $x_{k+1}=\varPhi(x_k)$ 是 $(2p-1)$ 阶收敛的。

证明略

牛顿法

$f(x)\approx f(x_k)+f’(x_k)(x-x_k)$

则 $f(x)=0$ 可以近似看作 $f(x_k)+f’(x_k)(x-x_k)=0$

所以有迭代公式 $x_{k+1}=x_k-\frac{f(x_k)}{f’(x_k)}$

牛顿法也称切线法

局部收敛性

可证明，牛顿法对单根至少是二阶局部收敛的；对重根是一阶局部收敛的。

即：牛顿法不论对单根还是重根均是局部收敛的。只要初值足够靠近精确解，牛顿迭代序列均收敛于精确解。

证明略（P32）

大范围收敛性

设函数 $f(x)$ 在区间 $[a, b]$ 上存在二阶连续导数，且满足条件：

$f(a)f(b)\lt0$
$\forall x\in[a, b], f’(x)\ne0$
$\forall x\in[a,b], f’’(x)\text{保号}$
$a-\frac{f(a)}{f’(a)}\le b, b-\frac{f(b)}{f’(b)}\ge a$

则对任意初值 $x_0\in[a, b]$ ，由牛顿迭代产生的序列二阶收敛到方程 $f(x)=0$ 在 $[a,b]$ 上的唯一根。

前两个条件保证了唯一根的存在，第三个条件保证了 $f(x)$ 在 $[a, b]$ 内上凸或下凸，条件四保证了 $x_k\in[a, b]$ 时 $x_{k+1}\in[a, b]$ ，迭代过程可一直进行下去。

牛顿法改进

设 $f(x)=0$ 有 $m(m\ge2)$ 重根，则 $x_{k+1}=x_k-m\frac{f(x_k)}{f’(x_k)}$ 至少是二阶收敛

割线法

为了避免导数，可以用差商代替导数。

$x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1})$

可能是VCode的博客

不能吃！/工作联系vcodechina@gmail.com/私人联系vcode28629@qq.com