2020-04-25

第五章非线性方程的求根

对于非线性方程
$f(x)=0$
中的 $f(x)$ 是 $n$ 次多项式 $f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$ 时，称为代数方程；否则称为超越方程，如 $f(x)=xe^x-1=0,f(x)=x\sin x-\frac{1}{2}=0$ 。

对 $n\ge 5$ 的代数方程和超越方程，没有通用的求根公式，一般用数值分析的方法做近似计算。

5.1 二分法

例子
判别方程 $x^3-3x+1=0$ 的实根存在区间，要求区间长度不大于 1，并求出最小正跟的近似值，误差限 $\varepsilon =10^{-3}$ 。

解

由于方程时 3 次代数方程，故其根的个数不超过 3 个。由下表可知根的存在区间为（-2，-1），（0，1），（1，2）。
$\begin{array}{l|c|c|c|c|r}x &-2&-1&0&1&2\\ \hline f(x)&-1&3&1&-1&3\end{array}$

在区间（0，1）内做二分法迭代，求得最小正跟的近似值为 0.347。

二分法的优点是方法和计算简单，对函数的性质要求不高，只需连续即可。缺点是收敛速度慢，不能求偶数重根。实际应用中常用来判别根的存在区间。

5.2 不动点迭代法

不动点与不动点迭代法

设方程 $f(x)=0$ 可以转化为等价的形式 $x=g(x)$ ，从某个初值 $x_0$ 出发，令 $x_{k+1}=g(x_k),k=0,1,2,\cdots$
得到序列 $\{x_k\}$ ，当 $g(x)$ 连续，且序列 $\{x_k\}$ 收敛于 $\alpha$
时，有
$\lim_{k\rightarrow\infty}x_{k+1}=\lim_{k\rightarrow\infty}g(x_k)=g(\lim_{k\rightarrow\infty}x_k)$
即有 $\alpha=g(\alpha)$ ，所以 $\alpha$ 是方程 $f(x)=0$ 的根。

称上述函数 $g(x)$ 为迭代函数，称 $\alpha$ 是它的一个不动点，构造迭代公式的方法称为不动点迭代法。

例子用不动点迭代方法，求方程 $x^3+4x^2-10=0$ 在（1，2）内的近似根。

解设 $f(x)=x^3+4x^2-10$ ， $f(x)$ 在[1,2]上连续，且 $f(1)=-5<0;f(2)=14>0$ ，由零点定理知，方程在（1，2）内至少存在一实根。

采用迭代公式 $x_{k+1}=g(x_k)=x_k-x_k^3-4x_k^2+10$ ，取初始近似值 $x_0=1.5$ ，迭代后计算结果为： $x_4=1.03\times 10^8$ ，不收敛。

采用迭代公式 $x_{k+1}=g(x_k)=x_k-\frac{x_k^3+4x_k^2-10}{3x_k^2+8x_k}$ ，取初始近似值 $x_0=1.5$ ，迭代后计算结果为： $x_3=1.36523001$ ，收敛。

不动点迭代法的收敛性

求解非线性方程根的不动点迭代法常常只具有局部的收敛性，即当初始值 $x_0$ 充分接近于根 $\alpha$ 时，迭代法产生的序列 $\{x_k\}$ 才可能收敛于根 $\alpha$ 。

若存在常数 $L>0$ ，使得 $|g(x_1)-g(x_2)|\le L |x_1-x_2|, \forall x_1,x_2 \in [a,b]$ ，则称函数 $g(x)$ 在 $[a,b]$ 上满足 Lipschitz 条件， L 称为 Lipschitz 常数。

定理
对迭代方程 $x=g(x)$ ，若迭代函数 $g(x)$ 满足
1）当 $x\in [a,b]$ 时，有 $g(x)\in [a,b]$ ；
2） $g(x)$ 在 $[a,b]$ 上满足 Lipschitz 条件，且 $L<1$ 。
则有：
1） $x=g(x)$ 在 $(a,b)$ 内存在唯一的根 $\alpha$ ;

对 $\forall x_0\in [a,b]$ ，迭代公式 $x_{k+1}=g(x_k)$ 均收敛，且 $\lim_{k\rightarrow\infty}x_{k}=\alpha$
$|\alpha-x_k|\le \frac{L^k}{1-L}|x_1-x_0|$
$|\alpha-x_k|\le \frac{L}{1-L}|x_k-x_{k-1}|$

迭代法的收敛速度

收敛速度是衡量迭代方法好坏的重要标志，常用收敛的阶来刻画。

记迭代公式的第 $k$ 次迭代误差为 $\varepsilon _k=\alpha -x_k$ ，并假设迭代公式是收敛的，若存在实数 $p\ge 1$ 使得
$\lim_{k\rightarrow\infty}\frac{|\varepsilon_{k+1}|}{|\varepsilon_k|^p}=C \ne 0$
则称迭代公式是 p 阶收敛的， C 称为渐近误差常数。

若 $p=1,C<1$ ，称迭代公式为线性收敛；若 $p=2$ ，称迭代公式为二阶收敛；若 $1<p<2$ ，或 $p=1,C=0$ ，称迭代公式为超线性收敛。

收敛阶为 p 的意义是迭代结果的误差与迭代前误差的 p 次方是同阶无穷小；高阶方法比低阶方法收敛快很多，同阶方法中渐近误差常数小的收敛较快。

对迭代公式 $x_{k+1}=g(x_k)$ ，若 $g^{(p)}(x)$ 在根 $\alpha$ 的邻域内连续，且
$g'(\alpha)=g''(\alpha)=\cdots=g^{(p-1)})(\alpha)=0$
则迭代公式在根 $\alpha$ 的领域内至少是 p 阶收敛的（p 是正整数）；若还有 $g^{(p)}(\alpha)\ne 0$ ，则迭代公式在根 $\alpha$ 的邻域内是 p 阶收敛的。

5.3 Newton 迭代法

Newton 迭代法的构造思想

将函数 $f(x)$ 在近似值 $x_k$ 处进行一阶泰勒展开，略去高阶无穷小项，故有迭代公式
$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} \quad\quad {f'(x_k)\ne 0}$

Newton 法的几何意义是用点 $(x_k,f(x_k))$ 处的切线与 $x$ 轴交点处的横坐标作为近似值 $x_{k+1}$ 。

Newton 法的收敛速度

Newton 法的迭代函数 $g(x)=x-\frac{f(x)}{f'(x)}$ ，由 $g'(\alpha)=\frac{f(\alpha)f''(\alpha)}{(f'(\alpha))^2}=0\quad\quad (f'(\alpha)\ne 0)$ ，当 $f'(\alpha)\ne0$ 时， Newton 法至少是二阶收敛的。

例子
用 Newton 法求 $x\sin x=0.5$ 在 0.7 附近的根，误差限 $\varepsilon=10^{-7}$ 。

解
$f(x)=x\sin x-0.5, f'(x)=\sin x + x\cos x, x_0=0.7$
$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}=x_k-\frac{x_k\sin x_k-0.5}{\sin x_k+x_k \cos x_k}, k=0,1,2,\cdots$
计算结果如下表：
$\begin{array}{l|c|c|c|c|c} k&0&1&2&3&4\\ x_k&0.7000000&0.7415796&0.7408412&0.7408410&0.7408410 \end{array}$

简化 Newton 法

迭代公式为： $x_{k+1}=x_k-\frac{f(x_k)}{C}$ ，其中 C 为一常数，常取 $C=f'(x_0)$ 。

简化 Newton 法只有线性收敛性。

例子
用简化 Newton 法求 $x\sin x=0.5$ 在 0.7 附近的根，误差限 $\varepsilon=10^{-7}$ 。

解
$f'(x_0) = 1.179607$
$x_{k+1} = x_k-\frac{f(x_k)}{f'(x_0)}=x_k-\frac{x_k\sin x_k-0.5}{1.179607},k=0,1,2,\cdots$
计算结果如下表：
$\begin{array}{l|c|c|c|c|c|c} k&0&1&2&3&4&5&6\\ x_k&0.7000000&0.7415796&0.7408144&0.7408419&0.7408409&0.7408410&0.7408410 \end{array}$

Newton 下山法

迭代公式 $x_{k+1}=x_k-\lambda_k\frac{f(x_k)}{f'(x_k)},k=0,1,2,\cdots$
其中 $0<\lambda_k\le 1$ ，且满足下山条件：
$|f(x_{k+1})|<|f(x_k)|$

称 $\lambda_k$ 为下山因子。下山因子的选取常用逐步搜索法，先取 $\lambda_k=1$ ，判断下山条件是否成立，若不成立则将 $\lambda_k$ 缩小一半，直到下山条件成立为止。

割线法

Newton 迭代法需要求函数的导数，当求导数有困难时，用差商近似代替微商有迭代公式：
$x_{k+1}=x_k-\frac{x_k-x_{k-1}}{f(x_k)-f(x_{x-1})}f(x_k),\quad k=1,2,3,\cdots$

该方法具有超线性收敛性。收敛阶为黄金分割数 0.618。

例子
用割线法求 $x\sin x=0.5$ 在 0.7 附近的根，取 $x_0=0.5,x_1=1$ ，误差限 $\varepsilon=10^{-7}$ 。

解
$x_{k+1}=x_k-\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k),\quad k=1,2,3,\cdots$
计算结果如下表：
$\begin{array}{l|c|c|c|c|c} k&0&1&2&3&4&5\\ x_k&0.5&1.0&0.7162723&0.7389835&0.7408598&0.7408409\\ x_{k+1}&1.0&0.7162723&0.7389835&0.7408598&0.740840&0.7408410 \end{array}$

5.4 Aitken 加速方法与重根迭代法

Aitken 加速方法
重根的迭代

5.5 非线性方程组求根

设有方程组
$\begin{cases} f_1(x_1,x_2,\cdots,x_n)&=0\\ f_2(x_1,x_2,\cdots,x_n)&=0\\ \cdots\cdots\cdots\cdots\\ f_n(x_1,x_2,\cdots,x_n)&=0\\ \end{cases}$
只要其中有一个是非线性函数，就称为是非线性方程组。

不动点迭代法

例子
求解非线性方程组
$\begin{cases} 3x_1-\cos(x_2x_3)-\frac{1}{2}=0\\ x^2_1-81(x_2+0.1)^2+\sin x_3+1.06=0\\ e^{-x_1x_2}+20x_3+\frac{10\pi -3}{3}=0 \end{cases}$

解
迭代公式为：
$\begin{cases} x_1^{(k+1)}=\frac{1}{3}\cos(x_2^{(k)}x_3^{(k)})+\frac{1}{6}\\ x_2^{(k+1)}=\frac{1}{9}\sqrt{(x_1^{(k)})^2+\sin x_3^{(k)}+1.06}-0.1\\ x_3^{(k+1)}=-\frac{1}{20}e^{-x_1^{(k)}x_2^{(k)}}-\frac{10\pi-3}{60} \end{cases}$

取初值 $x^{(0)}=(0.1,0.1,-0.1)^T$ ，迭代求得 $\alpha=(0.5,0.00000002,-0.52359877)^T$

Newton 迭代法

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,723评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,080评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,604评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,440评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,431评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,499评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,893评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,541评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,751评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,547评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,619评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,320评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,890评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,896评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,137评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,796评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,335评论 2赞 342