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

作者: Bocchi | 来源:发表于2019-04-01 10:15 被阅读0次

#数值分析读书笔记（4）求非线性方程的数值求解
使用scipy库的root和fsolve函数求解方程
数值分析：非线性方程的求解
非线性方程组求解
数值分析：非线性方程组求解
第二章：Python数据分析简介
10-Python 科学计算_scipy 篇
使用牛顿迭代法求解非线性方程的根
python数值分析——非线性方程迭代求解与Aitken加速
数值计算day2-求解非线性方程

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

#数值分析读书笔记（4）求非线性方程的数值求解
数值分析读书笔记（4）求非线性方程的数值求解 1.关于非线性方程的根的定位以及二分法我们直接介绍二分法将有根区...
使用scipy库的root和fsolve函数求解方程
求解非线性方程使用scipy库的 root, fsolve 函数求解非线性方程。求解传热方程（热辐射+热传导）...
数值分析：非线性方程的求解
1 逐步搜索法连续函数的零点定理：设在区间上连续，且有，说明方程，在区间上至少有一个实数根。依据上面的定理，我...
非线性方程组求解
非线性方程组求解 fsolve() 可以对非线性方程组进行求解，它的基本调用形式为fsolve(func，x0)。...
数值分析：非线性方程组求解
前言非线性方程组，顾名思义就是未知数的幂除了不是1，其他都有可能！线性方程组其实只是非常小的一类，非线性方程组才...
第二章：Python数据分析简介
2.1Scipy求解非线性方程组和数值积分 2.2Matplotlib作图基本代码如果使用的是中文标签，就会发现...
10-Python 科学计算_scipy 篇
课程概要：1、非线性方程组2、数值积分3、常微分方程组 1、非线性方程组 2、数值积分（定积分） 3、常微分方程组
使用牛顿迭代法求解非线性方程的根
牛顿法是一种近似求解非线性方程根的迭代算法。本文简要叙述该算法并使用MATLAB实现该算法求解一元非线性方程和多元...
python数值分析——非线性方程迭代求解与Aitken加速
1实验内容用迭代法求下列方程的根f(x)=x3+2x2+10x-20=0 (x*=1.3688081078213...
数值计算day2-求解非线性方程
上节课介绍了计算机中浮点数的表示方法，数值计算中涉及到的几种误差以及数值方法这门课中的一些数学基础。本节课将介绍如...

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

1 逐步搜索法

2 二分法

2.1 基本思路

2.2 计算步骤

3 不动点迭代法

3.1 基本思路

3.2 收敛定理

3.3 计算步骤

3.4 局部收敛性与收敛阶

3.5 Aitken加速方法

4 牛顿法

4.1 基本思路

4.2 计算步骤

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

5 弦截法

5.1 基本思路

5.2 计算步骤

小结

相关文章

#数值分析读书笔记（4）求非线性方程的数值求解

使用scipy库的root和fsolve函数求解方程

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

非线性方程组求解

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

第二章：Python数据分析简介

10-Python 科学计算_scipy 篇

使用牛顿迭代法求解非线性方程的根

python数值分析——非线性方程迭代求解与Aitken加速

数值计算day2-求解非线性方程

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读