当前位置：首页 > news >正文

数值分析—非线性方程的数值解

news 文章来源：https://blog.csdn.net/weixin_46763552/article/details/144357592 2025/1/1 21:18:29

研究背景

形如 $x - t an x = 0$ 、 $xlnx+e^{-x^2}+sinx=0$ 等称为非线性方程，自变量之间并非简单的线性关系，这种问题我们无法通过其结构求解，需要其他的逼近方式，本章将基于该问题介绍两种方法——二分法，迭代法。

二分法

预备知识

零点定理：
若 $f(x)\in[a,b]$ 且 $f (a) f (b) < 0$ ，则 $f (x)$ 在 $(a, b)$ 内至少有一个零点，若 $f (x)$ 为单调函数，则 $f (x)$ 有唯一零点。

重根判别方法：
设 $f (x)$ 在 $x$ 有n阶导数，则 $x$ 为 $f (x) = 0$ 的m重根的充要条件为：
$f(x)=f'(x)=f^{m-1}(x)=0且f^m(x)!=0$ 。

求实根的二分法

基本思想为：
将有根区间一分为二，等分为两个区间，判断根再哪一个更小的区间，舍去无根的小区间，再把有根的小区间等分，如此重复，直到找到满足精度的近似根。

算法流程：
取终点 $x_0=\frac{a+b}{2}$ ，若 $f(x_0)=0,x_0$ 为所求，否则计算 $f(a)f(x_0)$ 的符号， $> 0$ 取区间 $x_0,b]$ ， $< 0$ 取 $a,x_0]$ ，重复上述过程，无穷多次后即为精确解 $\lim_{k \to \infty}x_k=x$ ，但计算中不可能迭代无穷多次，也不可能得知精确解，故一般采用前后两次迭代逼近的程度来衡量， $|x_k-x_{k-1}|\le\frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}$ ，取精度 $\frac{b-a}{2^{k+1}}<\varepsilon$ ，迭代步数为 $k>\frac{ln(b-a)-ln2\varepsilon}{ln2}$

例题：二分法求 $f(x)=x^2-x-1=0$ 的正根，要求误差不超过0.05。
解：
设 $f(x)=x^2-x-1,f(1)=-1<0,f(2)=1>0$ ，故有根区间为 $[- 1, 2]$ ，该函数在区间内单调， $k>\frac{-ln0.1}{ln2}=\frac{10}{ln2}=3.3$ ，取步长k=4，求其根表示为：

k	$a_k$	$b_k$	$x_k$	f(x)符号
0	1	2	1.5	-
1	1.5	2	1.75	+
2	1.5	1.75	1.625	+
3	1.5	1.625	1.5625	-
4	1.5625	1.625	1.59375

答：根为1.59375。

该方法实现简单，普及性高，对方程只要求其连续即可，但收敛速度缓慢，下面介绍一种加速收敛的方法—迭代法。

迭代法

基本思想

$f (x) = 0 <=> x = g (x)$ ， $g (x)$ 为迭代函数， $x_{k+1}=g(x_k)$ ，给定 $x_0$ 可计算 $x_1....x_n$ ，若该数列收敛，则称迭代法 $x_{k+1}=g(x_k)$ 收敛，否则发散。

若 $x^*$ 满足 $x^*=g(x^*)$ 则称 $x^*$ 为 $g (x)$ 的不动点。
若 $\lim_{k \to \infty}x_k=x^*，g(x)$ 连续， $x^*=\lim_{k \to \infty}x_{k+1}=\lim_{k \to \infty}g(x_k)=g(\lim_{k \to \infty}x_k)=g(x^*)$

该过程重点在于：
1，如果构造 $g (x)$
2， $g (x)$ 满足何种条件能保证数列 ${x_n}$ 收敛
3，收敛速度如何衡量

该方法的几何意义为以直代曲，用切线零点代替曲线零点，不断逼近坐标轴的过程。

迭代格式的适定性与收敛性

定义：如果 $x_0\in[a,b]$ ，若按 $x_{k+1}=g(x_k)$ 生成的序列 ${x_k}\in[a,b]$ ，则称迭代格式是适定的，适定性是迭代格式能够继续下去的重要条件。

例如：求 $xe^{x}-1=0$ 在 $x = 0.5$ 附近的根。
解: $x=e^{-x}$ ，构造迭代格式 $x_{k+1}=e^{-x_k},x_0=0.5$ ,可继续迭代
$e^x=\frac{1}{x},x=-lnx$ ，构造 $x_{k+1}=-lnx_k,x_0=0.5,x_4<0$ 时终止

定理一：设 $g(x)\in[a,b]$ ，且满足如下条件：
1,任意 $x\in[a,b]$ ，总有 $g(x)\in[a,b]$
2,存在 $L\in[0,1],使|g(x)-g(y)|\le L|x-y|，x，y为[a,b]内的任意数$
则 $g (x)$ 在 $[a, b]$ 上存在唯一不动点 $x^*$ 对任意 $x\in[a,b]$ 迭代法适定且收敛，但该条件很不好证明，故多采用定义二。

定理二：若 $g(x)\in[a,b]$ 且满足如下条件：
1，任意 $x\in[a,b]，有g(x)\le[a,b]$
2，存在 $0\le L\le1，使对任意x\in[a,b]有|g'(x)|\le L$ ，该定理用导数代替了验证过程。
则 $x_{k+1}=g(x_k)\le\frac{L^k}{1-L}|x-x_0|$

注：
1，不等式为停机标准， $|x_{k+1}-x_k|<\varepsilon$ 时， $|x^*-x^k|\le\frac{\varepsilon}{1-L}$
2，先验估计，用于估计达到 $\varepsilon$ 精度所需迭代的步数为
$\frac{L^k}{1-L}|x_1-x_0|<\varepsilon$ ，从而 $k>\frac{ln(\frac{-(1-L)\varepsilon }{(x_1-x_0)})}{lnL}$
3，L越小收敛速度越快。

局部收敛性与收敛阶

定义： $x^*为g(x)$ 的不动点，对 $\delta>0,称N(x^*,\delta)=[x^*-\delta,x^*+\delta]$ 为 $x^*$ 的一个邻域，若存在一个邻域使对任意 $x\in N(x^*,\delta)$ 按 $x_{k+1}=g(x_k)$ 生成的 ${x_k}\in N(x^*,\delta)$ 且 $\lim_{x \to \infty}x_k=x^*$ ，则称迭代格式具有迭代收敛性。
即在邻域内无穷次迭代后能获得精确解。

定理一：设 $g (x) 在 x = g (x)$ 的根 $x^*$ 邻域内有连续的一阶导数，且 $g'(x^*)|<1$ ，迭代法具有局部收敛性。
注：实际使用时往往用 $g'(x_0)|<1$ 代替

n阶导数<1收敛，则收敛阶为n。

例题：迭代函数 $g(x)=x+c(x^2-3)$ ，讨论1，写出迭代格式，产生 ${k}$ 收敛于 $\sqrt{3}$ ，问c应为何值？2，c为何值时收敛速度最快？
解：1，迭代格式 $x_{k+1}=g(x_k)=x_k+c(x_k^2-3)，g'(x)=1+2cx，|g'(\sqrt{3})|=|1+2\sqrt{3}c|<1=>-\frac{\sqrt{3}}{2}<c<0$
2， $g'(\sqrt{3})=0,1+2\sqrt{3}c=0,c=-\frac{\sqrt{3}}{6}$ 收敛最快

Newton迭代法

基本思想：满足一般理论的特殊迭代法， $f (x) = 0$ 先假设 $x_k$ 为 $f (x) = 0$ 的近似根， $f'(x_k)!=0$ ，将 $f (x)$ 在 $x_k$ 处作Taylor展开， $f(x)\approx f(x_k)+f'(x_k)(x-x_k)+\frac{f''(\xi)}{2!}(x-x_k)^2$ ，舍去余项后 $f(x)\approx f(x_k)+f'(x_k)(x-x_k)$ ， $f(x_k)+f'(x_k)(x-x_k)=0$ ，故 $x=x_k-\frac{f(x_k)}{f'(x_k)}$ ，不动点带入获得迭代函数 $g(x)=x-\frac{f(x)}{f'(x)}$ 。

该方法的几何意义是以直代曲，沿曲线方向不断作切线，和x轴的交点作为下一次切线起点，形成一个不断逼近 $x^*$ 的数列。

例题：Newton迭代法求 $f(x)=x^3+2x-6$ 在1.5附近的根。
解： $f'(x)=3x^2+2$ ，Newton迭代公式 $x_{k+1}=x_k-\frac{x_k^3+2x_k-6}{3x_k^2+2}$ ，取 $x_0=1.5$ 迭代运算， $x_1=1.4571429，x_2=1.4561647$
可以看到Newton迭代法的收敛速度还是比较快的。

Newton迭代法的收敛性与收敛阶

局部收敛性定理：
设 $x^*$ 为 $f (x) = 0$ 的单根，即 $f(x^*)=0,f'(x^*)!=0$ ，则Newton迭代格式 $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ 至少二阶收敛。

非局部收敛性定理：
设 $f(x)\in c^2[a,b]$ 且满足如下条件：
1， $f (a) f (b) < 0$
2， $f'(x)!=0,任意x\in [a,b]$
3， $x\in[a,b]时，有f'(x)不变号$
4， $任意x_0\in[a,b],使f(x_0)f''(x_0)>0$
则由Newton迭代格式确定的 ${x_k}$ 收敛于 $f (x) = 0$ 在 $[a, b]$ 有唯一根 $x^*$

简化后的Newton法：
该迭代法主要的计算量来自导数，故简化后采用 $x_{k+1}=x-\frac{f(x)}{C}$ 用常数C代替之， $C=f'(x_0)$ ，该方法使用固定点的导数作为常数来代替后续导数计算，固然简化了计算，但收敛速度也随之下降。

求重根的Newton法

设 $x^*$ 为 $f (x) = 0$ 的重根， $f(x^*)=f'(x^*)=...=f^{n+1}(x^*)=0$ 且 $f^n(x^*)!=0$ ， $f(x)=(x-x^*)A(x)$ ，显然 $A(x^*)!=0$ 。

Newton迭代法 $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}，g(x)=x-\frac{f(x)}{f'(x)}，g'(x^*)<1$ 收敛， $g'(x)=\frac{f(x)f''(x)}{[f'(x)]^2}$ ，故 $g'(x^*)=\frac{f(x^*)f''(x^*)}{[f'(x^*)]^2}=\lim_{x\to x^* \frac{g(x)-g(x^*)}{x-x^*}}$ ，最后很复杂，一同操作后得证 $g'(x^*)=1-\frac{1}{m}$

例题： $x^3-3x^2+4=0$ ，试用Newton迭代法求 $x^*=2$ ，并证明收敛性，求收敛阶。
解： $f(x)=x^3-3x^2+4，f'(x)=3x^2-6x，x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}=x_k-\frac{x_k^3-3x_k^2+4}{3x_k^2-6x_k}$ ，则 $g(x)=x-\frac{x^3-3x^2+4}{3x^2-6x}$ ，若 $∣ g^{'} (2) ∣ < 1$ 收敛， $x^*=2$ 为 $f (x)$ 的二重根，根据 $1-\frac{1}{m}=>|g'(2)|=\frac{1}{2}<1$ 故收敛且线性收敛。

Newton法改进

1， $f (x) = 0$ 的重根 $x^*$ 的重数m已知，则可得到 $x_{k+1}=x_k-m\frac{f(x_k)}{f'(x_k)}，g(x)=x-m\frac{f(x)}{f'(x)}，g'(x^*)=1-m\frac{1}{m}=0$ ，故至少平方收敛。

2， $f (x) = 0$ 的重根 $x^*$ 的重数m未知，令 $u(x)=\frac{f(x)}{f'(x)}$ ，若 $x^*$ 为 $f (x)$ 的m重根， $x^*$ 为 $f^{'} (x)$ 的m-1重根， $x^*$ 必为 $u (x)$ 的单根，只需构造 $u (x) = 0$ 的单根Newton法， $x_{k+1}=x_k-\frac{u(x_k)}{u'(x_k)},u'(x)=\frac{[f'(x)]^2-f(x)f'(x)}{[f'(x)]^2},x_{k+1}=x_k-\frac{f(x_k)f'(x_k)}{[f'(x_k)]^2-f(x_k)f''(x_k)}$ ，至少平方收敛。

例题1：设 $f(x)=x^4-6x^2+8x-3$ ，求 $x_1=3,x_2=1$ 的二阶局部收敛的Newton法。
解：首先判断单根还是重根， $f'(x)=4x^3-12x+8,x_1=3,f(-3)=0,f'(-3)!=0$ ，所以 $x_1=3$ 为单根，用二阶收敛的呢我同法， $x_{k+1}=x_k-\frac{x_k^4-6x_k^2+8x_k-3}{4x_k^3-12x_k+8}$ 。
$x_2=1,f(1)=0,f'(1)=0,f''(1)=0,f'''(1)!=0$ ，所以 $x_2=1$ 为三重根，方法同上，二阶收敛的Newton法 $x_{k+1}=x_k-3\frac{x_k^4-6x_k^2+8x_k-3}{4x_k^3-12x_k+8}$ 。

总结

本章介绍了非线性方程的数值解法，二分法实现简单，但收敛很慢，迭代法主要是Newton迭代法，用泰勒公式近似方程，着重分析其收敛性和收敛阶，该章公式很多很杂，大量篇幅在于分析性质而非单纯计算，到整理完毕整体也没消化完，还需后面补足，大致为：确定适定性，分析收敛性，写出迭代格式，计算收敛阶。

这也是数值分析的最后一章，我们依次介绍了误差分析的方法、线性方程组的数值解法、函数插值的预测法、数值积分的近似计算法和本章非线性方程的数值解法，这些方法我们以后未必能用得到，但通过对这些方法学习，我们如果能体会这种逼近和代替的思想也是很大的收获，现实世界的很多问题我们没法精确求解分析，构造相近的情景再解决也算是曲线救国了。