数值分析：非线性方程的求解

1 逐步搜索法

连续函数的零点定理：设 $f(x)$ 在区间 $[a,b]$ 上连续，且有 $f(a)f(b)<0$ ，说明方程 $f(x)=0$ ，在区间 $[a,b]$ 上至少有一个实数根 $x^*$ 。

依据上面的定理，我们可以设计以下算法：
我们从左端点 $x_0=a$ 出发，按某一个预定的步长 $h$ ，如取 $h=(b-a)/n$ （n 为正整数），向右迈进。考虑节点 $x_1=x_0+h$ 处的函数值，有3种可能：

节点 $x_1$ 的函数值与左端点 $a$ 的函数值同号，即 $f(x_1)f(a)>0$ ；
这时，我们无法判断 $a$ 与 $x_1$ 之间是否有方程的实根，因此我们继续向右迈步，每跨一步进行一次根的搜索。
$f(x_1)=0$
这时， $x_1$ 便是方程的一个实根
节点 $x_1$ 的函数值与左端点 $a$ 的函数值异号，即 $f(x_1)f(a)<0$ ；
这时，节点 $x_1$ 与 $a$ 之间必有方程的一个实根。

我们可以证明，必存在某节点 $x_k$ 处的函数值异号，则在 $x_{k-1}$ 与 $x_k$ 必存在一个实根。此时可取 $\frac{x_{k-1}+x_{k}}{2}$ 作为初始近似值。根的搜索到此结束。这种根的搜索方法称为逐步搜索法

2 二分法

优点：条件简单
缺点：收敛速度慢、不易求偶数重根

2.1 基本思路

考察有根区间 $[a,b]$ ，取中点 $x_0=\frac{a+b}2$ 将它分成两半，假设中点 $x_0$ 不是 $f(x)$ 的零点，然后检查 $f(x_0)$ 与 $f(a)$ 是否同号。
如果确定是同号，说明所求的根 $x^*$ 在 $x_0$ 的右侧，这时令 $a_1=x_0,b_1=b$ ；否则 $x^*$ 必在 $x_0$ 的左侧。
这时令 $a_1=a,b_1=x_0$ 。不管出现哪种情况 $[a_1,b_1]$ 的长度均为 $[a,b]$ 长度的一半。

对于压缩了的有根区间 $[a_1,b_1]$ 又可施行同样的手段，如此反复二分下去，即可得出一系列有根区间
$[a,b]\supset[a_1,b_1]\supset[a_2,b_2]\supset...\supset[a_k,b_k]\supset...$ 其中每个区间都是前一个的一半，因此 $k\to\infty$ 时 $[a_k,b_k]$ 的长度
$\lim\limits_{k\to\infty}b_k-a_k=\lim\limits_{k\to\infty}\frac{b-a}{2^k}=0$ 因此这些区间必定最终收敛于 $x^*$ ，由于我们不能也不必无限做下去，因此，我们选取第 $k$ 次二分后的中点 $x_k=\frac{a_k+b_k}{2}$ 作为根的近似值。误差为： $|x^*-x_k| \le \frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}$

给定精确度求解二分次数时，利用公式求解即可！！

2.2 计算步骤

（1）输入有根区间端点 $a,b$ 及预先给定的精度 $\varepsilon$
（2）计算 $x=\frac{a+b}2$
（3）若 $f(a)f(x)$ 同号，则令 $a=x$ ，转向下一步；否则令 $b=x$ ，转向下一步。
（4）若 $b-a<\varepsilon$ ，则输出方程满足精度要求的根 $x$ ，否则转向步骤 (2)

3 不动点迭代法

优点：算法简单，对任意初值都能得到同样的结果
缺点：迭代格式选取需要考虑收敛性

3.1 基本思路

已知方程 $f(x)=0$ 在区间 $[a,b]$ 内有唯一的根 $x^*$ ，将上式改写成等价的形式 $x=\varphi(x)$ ，取 $x_0 \in [a,b]$ ，用递推公式 $x_{k+1}=\varphi(x_k),(k=0,1,...)$ ，可以得到序列 $x_0,x_1,...$ 。
如果当 $k\to\infty$ 时，序列 $\{x_k\}$ 有极限 $\lim\limits_{k\to\infty}x_k=x^*$ ，则称迭代法 收敛于 $x^*$ ，且 $x^*=\varphi(x^*)$ 。否则称迭代法发散。
若迭代法收敛，称 $\varphi(x)$ 为 迭代函数， $x_{k+1}=\varphi(x_k)$ 为 迭代格式， $\{x_k\}$ 为 迭代序列。

3.2 收敛定理

定理 1（全局收敛定理） 设迭代函数 $\varphi(x)$ 在 $[a,b]$ 上有连续一阶导数，且
（1）当 $x\in[a,b]$ 时， $a\le\varphi(x)\le b$ ；
（2）存在正数 $q<1$ （ $q$ 为利普希茨常数）,使对任意 $x\in[a,b]$ ，有 $|\varphi{'}(x)|\le q<1$ ;
则方程 $x=\varphi(x)$ 在区间上存在唯一的根 $x^*$ ，且对任意初值 $x_0\in[a,b]$ ，由迭代格式 $x_{k+1}=\varphi(x_k)$ 在区间上存在唯一的根 $x^*$ ，且对任意初值 $x_0\in[a,b]$ ，有迭代格式所确定的序列 $\{x_k\}$ 收敛于 $x^*$

推论如果 $|\varphi'(x)>1|$ ，则迭代格式 $x_{k+1}=\varphi(x_k)$ 所确定的序列 $\{x_k\}$ ，对任意初值 $x_0\in[a,b]$ 发散

定理 2 设 $\varphi(x) \in C[a,b]$ 满足定理1中的两个条件1，则对任意 $x_0\in [a,b]$ 由迭代式 $x_{k+1}=\varphi(x_k)$ 得到的迭代序列 $\{x_k\}$ 收敛到 $\varphi(x)$ 的不动点 $x^*$ ，并有误差估计 $|x_k-x^*| \leq \frac{L^k}{1-L} |x_1-x_0|$ 不难推导出（后验误差估计法） $|x^*-x_k|\leq\frac{1}{1-L}|x_{k+1}-x_k|$

注：先验误差估计不用计算 $x_k$ 的值，如误差定理推导迭代次数。而后验误差估计需要计算相关的近似值

3.3 计算步骤

（对于迭代过程 $x_{k+1}=\varphi(x_k)$ ）
（1）选取初始近似值 $x_0$ ，精确度 $\varepsilon$ ；
（2）由方程 $f(x)=0$ 确定迭代函数 $\varphi(x)$
（3）按照迭代格式 $x_{k+1}=\varphi(x_k)$ 计算 $x_1=\varphi(x_0)$
（4）如果 $|x_1-x_0| \le \varepsilon$ ，则停止计算否则用 $x_1$ 代替 $x_0$ 重复（3）和（4）

3.4 局部收敛性与收敛阶

定义 1 设 $\varphi(x)$ 有不动点 $x^*$ ，如果存在 $x^*$ 的某个邻域 $R:|x-x^*|\le \delta$ ，对任意 $x_0 \in R$ ，迭代法 $x_{k+1}=\varphi(x)$ 产生的序列 $\{x_k\} \subset R$ ，且收敛到 $x^*$ ，则称迭代法 $x_{k+1}=\varphi(x)$ 局部收敛

定理 3（局部收敛定理） 设迭代函数 $\varphi(x)$ 在 $x^*$ 的邻域上有连续一阶导数，且有 $|\varphi{'}(x)|<1$ ;则称迭代格式 $x_{k+1}=\varphi(x_k)$ 在根 $x^*$ 的邻域上具有 局部收敛性。

定义 2 设迭代过程 $x_{k+1}=\varphi(x_k)$ 收敛于方程 $x=\varphi(x)$ 的根 $x^*$ ，如果当 $k \to \infty$ 时迭代误差 $e^k=x_k-x^*$ 满足渐进关系式
$\frac{e_{k+1}}{e_k^p} \to C\mbox{，常数}C \neq 0$ 则称该迭代过程是 $p$ 阶收敛 的。特别的， $p=1(|C|<1)$ 时称为 线性收敛 ， $p>1$ 时称为 超线性收敛， $p=2$ 时称为 平方收敛

定理 4 对于迭代过程 $x_{k+1}=\varphi(x_k)$ 及正整数 $p$ ，如果 $\varphi^{(p)}(x)$ 在所求根 $x^*$ 的邻域连续，且
$\varphi'(x^*)=\varphi''(x^*)=...=\varphi^{p-1}(x^*)\mbox{，}\varphi^{p}(x^*) \neq 0$ 则该迭代过程在点 $x^*$ 的邻域内时 $p$ 阶收敛的

3.5 Aitken加速方法

$x'_{k+1}=x_k-\frac{(x_{k+1}-x_k)^2}{x_k-2x_{k+1}+x_{k+2}}$

4 牛顿法

优点：收敛速度快
缺点：对初值的选取要求较高

4.1 基本思路

对于非线性方程 $f(x)=0$ ，设 $x_0$ 是一个初始近似根（可由逐步搜索法确定）
，函数 $f(x)$ 在 $x_0$ 处的泰勒展开为
$f(x)=f(x_0)+f'(x_0)(x-x_0)+...+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n$
用一阶泰勒展开近似 $f(x)$ ，即有
$f(x) \approx f(x_0)+f'(x_0)(x-x_0)$
于是，方程 $f(x)$ 在点 $x_0$ 附近可近似表示为 $f(x_0)+f'(x_0)(x-x_0)=0$ ，将它的根 $x_1=x_0-\frac{f(x_0)}{f'(x_0)}$ 作为原方程 $f(x)$ 的一个近似新根。重复上述过程得迭代格式 $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ 这个方法叫做 牛顿迭代法，简称 牛顿法。

4.2 计算步骤

（1）选取初始近似值 $x_0$ ，允许误差 $\varepsilon_1,\varepsilon_2$ ，计算 $f_0=f(x_0),f_0'=f'(x_0)$ ；
（2）按公式 $x_1=x_0-\frac{f_0}{f'_0}$ 迭代一次，得到新的近似值 $x_1$ ，计算 $f_1=f(x_1),f'_1=f'(x_1)$ ；
（3）如果 $x_1$ 满足 $|\delta|<\varepsilon_1$ 或 $|f_1|<\varepsilon_2$ ，则终止迭代格式，以 $x_1$ 作为所求的根；否则转步骤4。其中
$\delta=\left\{ \begin{aligned} & |x_1-x_0| ,\mbox{当}|x_1|<C \\ & \frac{|x_1-x_0|}{x_1} ,\mbox{当}|x_1| \geq C\\ \end{aligned} \right.$ 其中 $C$ 是取绝对值误差或相对误差的控制常数，一般可取 $C=1$
（4）如果迭代次数达到预先指定的次数 $N$ ，或者 $f/_1=0$ ，则方法失败；否则以 $(x_1,f_1,f'_1)$ 代替 $(x_0,f_0,f'_0)$ 转步骤（2）继续迭代

4.3 简化牛顿法与牛顿下山法

简化牛顿法
也称平行弦法。其迭代公式为 $x_{k+1}=x_k-Cf(x_k),C\neq 0,k=0,1,...$ 迭代函数 $\varphi(x)=x-Cf(x)$ ，一般取 $C=\frac{1}{f'(x_0)}$
牛顿下山法
牛顿法收敛性依赖初值 $x_0$ 的选取。若 $x_0$ 偏离所求根 $x^*$ 较远，则牛顿法可能发散。
为了防止出现发散的情况，我们对迭代过程再附加一项要求，即具有单调性： $|f(x_{k+1})|<|f(x_k)|$ 满足这项要求的方法称为下山法。
我们将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度。我们对迭代法的计算结果 $x’_{k+1}=x_k-\frac{f(x_k)}{f’(x_k)}$ 与前一项的近似值 $x_k$ 的适当加权平均作为新的改进值 $x_{k+1}=\lambda x’_{k+1}+(1-\lambda)x_k$ 其中 $\lambda(0<\lambda\le 1)$ 称为下山因子，上式可写为 $x_{k+1}=x_k-\lambda \frac{f(x_k)}{f’(x_k)}$ 称为 牛顿下山法。选择下山因子从 $\lambda=1$ 开始，逐次将 $\lambda$ 减半进行试算，直到能使得下降条件成立为止，再开始牛顿迭代即可求得近似解。

5 弦截法

优点：计算量比牛顿法小
缺点：收敛速度较牛顿法稍慢

5.1 基本思路

设 $x_k,x_{k-1}$ 是 $f(x)=0$ 的近似根，我们利用 $f(x_k),f(x_{k+1})$ 构造一次插值多项式 $p_1(x)$ ，并用 $p_1(x)=0$ 的根作为 $f(x)=0$ 的心近似根，由于 $p_1(x)=f(x_k)+\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}(x-x_k)$ 因此有 $x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1})$ 这样导出的公式可看作牛顿法 $x_{k+1}=x_k-\frac{f(x)}{f’(x_k)}$ 中的导数 $f’(x)$ 用差商 $\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}$ 取代的结果

5.2 计算步骤

求解步骤与牛顿法类似，需要注意的是使用这种方法必须先给出两个初始值 $x_0,x_1$

小结

Aitken加速方法：可将一阶方法加速至二阶
牛顿法：二阶收敛
牛顿下山法：克服了需要选取较好初值的问题
弦截法：插值计算方法，不用计算导数，而且具有超线性收敛
抛物线法（未介绍）：插值计算方法，比弦截法快，超线性收敛

最后编辑于：2019.06.02 16:11:02

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