数值分析方法 课件 第五章 非线性方程的数值解法

数值分析方法面向“四新”人才培养普通高等教育系列教材第五章非线性方程的数值解法目录/Contents5.1-1非线性方程的近似求根

5.2非线性方程组的数值解

5.3非线性方程近似求根计算机实验

5.1-2非线性方程的迭代法的加速引言

在科学研究和工程设计中，经常会遇到一类求解非线性方程：方程的根，亦称为函数的零点.一般地，若为多项式，称方程

为n次代数方程，当n＞1时，方程显然是非线性的；而称三角方程、指数方程、对数方程等为超越方程.通常

3次以上的代数方程或超越方程，很难甚至无法求得精确解，数值解法可以借助于计算机完成求解.

求非线性方程的根的方法分为两步：计算根的近似值

确定方程的有根区间:由零点定理设，且，则方程在区间上至少有一个根。如果在上恒正或恒负，则此根唯一。5.1非线性方程的近似求根5.1.1二分法二分法的基本思想是将有根区间二等分，通过判断的符号，逐步对半缩小有根区间，直至有根区间缩小到容许误差范围之内，然后取区间的中点为根的近似值.第一步令计算有根区间的中点

若

，则为有根区间，否则为有根区间，记新的有根区间为，则第二步对重复上述做法得，设所求的根为，则取为的近似解.且有误差估计式：对于预先给定的精度，只要，即便有，这时就是满足精度要求的近似值.求方程f(x)=0的根的二分法算法python实现可以编写函数bisection来实现二分算法，代码如下：defbisection(f,a,b,ep=1e-8):#首先判断搜索区间是否包括所求根

iff(a)*f(b)>0:raiseException("区间端点处函数值符号不应相同！")#进入迭代

whileTrue:x0=(a+b)/2iff(x0)==0:returnx0iff(x0)*f(a)<0:b=x0else:a=x0ifabs(b-a)<ep:returnx0.例5.1.1证明方程在区间[1.0,1.5]内有且只有一个实根，且使用二分法求误差不超过0.005根至少迭代6次.解：因为，所以方程的有根区间为[1.0,1.5],对给定的误差不超过0.005，有故只要迭代n=6次便能达到所要求的精度.任取初值，代入中的右端得到

，再以为初值代入方程（1），得到，反复迭代得如下数列：5.1.2不动点迭代法非线性方程的等价方程（1）其中为x的连续函数.方程（1）的解称为函数的不动点.

（2）称式(2)为求解非线性方程的不动点迭代法，称为迭代函数.

若收敛，即则得是的一个根迭代法的几何意义

交点的横坐标解：由

建立迭代

计算结果如下:

例5.1.1试用迭代法求方程在区间(1，2)内的实根。格式k=0,1,2,3…….精确到小数点后五位但如果由建立迭代公式仍取，则有，,显然结果越来越大，是发散序列.迭代函数满足什么条件，才能保证迭代过程

是收敛的？迭代法的收敛性定理5.1（压缩映像原理）设迭代函数在闭区间上满足以下两个条件：（1）对任意的（2）在上满足Lipschitz条件：即存在常数L，是对有且Lipschitz常数;压缩映像原理则（1）在上存在唯一解；（2）对，由产生的序列收敛于，即；（4）（误差事后估计式）（误差事前估计式）（3）证明：（1）首先证明不动点的存在性.构造函数则由连续函数介值条件，存在，使得

（3）由Lipschitz条件及递推关系得

所以压缩映像原理在应用中定理5.1的条件保证了迭代格式收敛，但Lipschitz条件验证起来有时稍显困难，事实上，比Lipschitz条件更强的条件是在(a，b)内可导，且，Lipschitz常数L可取的最大值.区间[a,b]上的收敛性称为全局收敛性不动点迭代法的局部收敛性敛的.

证毕的迭代结果谢谢数值分析方法主编

李冬果李林高磊面向“四新”人才培养普通高等教育系列教材第五章非线性方程的数值解法目录/Contents5.1-1非线性方程的近似求根

5.2非线性方程组的数值解

5.3非线性方程近似求根计算机实验

5.1-2非线性方程的迭代法的加速5.1.3迭代法的加速(1)(2)(3)

,称为Aitken加速法.

Aitken加速：比收敛得略快。将视为新的初值，重复上述步骤xyy=xy=

(x)x*x0P(x0,x1)x1x2P(x1,x2)P(,)

Steffensen迭代格式几何解释：

斯蒂芬森加速可使原本不收敛的迭代改进到收敛.

几何意义：xyx*x0Newton迭代法收敛性(4)例牛顿法求方程在附近的一个根.

设取迭代初值，用牛顿法公式计算迭代3次得到的结果有6位有效数字.取这个结果反而比更偏离了所求的根.x*x0

x0

x0保证函数值稳定下降满足这项要求的算法称下山法.牛顿法的计算结果前一步的近似值作加权平均得其中称为下山因子，此迭代格式称为牛顿下山法.xkxk+1下山因子的选取从开始，逐次将减半进行试算，直到能使下降条件成立为止.

通过逐次取半进行试算，当时可求得当时求得

，不满足条件此时有

，而显然

.

由作为初始值计算时,均能使下山条件成立.计算结果：

即为的近似.（2）计算较困难.（1）每步迭代要计算及.缺点1、

弦截法

设是的近似根，利用

构造一次插值多项式，并用的根作为新的近似根.由有

牛顿公式中的导数用差商取代的结果.(5)几何意义

曲线上横坐标为的点分别记为，则弦线的斜率等于差商值,其方程为求得的实际上是弦线与轴交点的横坐标.这种算法因此而称为弦截法.弦截法与Newton法的区别

弦截法在求时要用到前面两步的结果，称为多点迭代法.

切线法在计算时只用到前一步的值,故称之为单点迭代.

例5.1.8用Newton迭代法和弦截法解方程

取作为开始值，解弦截法的收敛速度也是相当快的Newton迭代格式为：弦截法迭代格式为：——密勒（Müller）法2、

抛物线法

设已知方程的三个近似根，以这三点为节点构造二次

几何上，这种方法的基本思想是用抛物线与轴的交点作为所求根的近似位置，如图.插值多项式，

的一个零点作为新的近似根。并适当选取插值多项式其中，有两个零点：

式中

问题是该如何确定.

假定在三个近似根中，更接近所求的根，为了保证精度，选较接近的一个值作为新的近似根.

为此，只要取根式前的符号与的符号相同.

例5.1.9用抛物线法求解方程计算得

取初始值

解故

代入式中求得

在一定条件下可以证明：谢谢数值分析方法主编

李冬果李林高磊面向“四新”人才培养普通高等教育系列教材第五章非线性方程的数值解法目录/Contents5.1-1非线性方程的近似求根

5.2非线性方程组的数值解

5.3非线性方程近似求根计算机实验

5.1-2非线性方程的迭代法的加速5.2非线性方程组的数值解非线性方程组的数值解法在实际问题中有广泛的应用，特别是在许多工程问题、经济学问题、数学建模、动力学问题等方面，经常会遇到求解如下多元非线性方程组：（1）方程组（1）可表示成向量方程（1）（2）

通常非线性方程组（1）的数值解法主要包括两种方法：

区间迭代法和不动点算法1.不动点迭代法把方程组(2)改写成下面便于迭代的等价形式：（3）连续函数.则的不动点，是迭代函数即满足)(),(****xxxxxGG=的是自变量,,,21xxxnL收敛，若由此生成的序列是连续的,即且)(,),(),()(21xxxxnGGKGG的解。是方程组从而*x（2）且有误差估计式（5）定理的证明较为复杂，我们将略去其证明。例5.2.1设有非线性方程组（6）把它写成等价形式

由此构造不动点迭代法公式（7）解从而取初始点，由迭代公式（7）计算结果如表，可见迭代收敛到方程的解2.Newton迭代法对于非线性方程组，也可以构造于一元方程的Newton迭代法。

在用多元函数泰勒展开，并取其线性部分，则可表示为令上式右端为零，得到线性方程组（8）（9）若矩阵非奇异，则由使（8）右端为零的向量作为新的一个近似值，记为，于是得到Newton迭代格式（10）如果写成一般不动点迭代的形式，则Newton迭代函数为

（11）事实上，在实际计算过程中由于矩阵的逆求解十分耗时，因此通常通过求解线性方程组来替代.如第k步可令先解线性方程组其中包括了计算向量及Jacobi矩阵.例5.2.2用Newton法解例5.2.1的方程组解

对该方程组有取初始向量，解方程组，即求出后，。同理计算结果如表，可见迭代4次可得精确解，显然Newton法的收敛速度比例5.2.1中的迭代法要快的多。k0123400.800.9917872210.9999752291.0000000000.880.9917117370.9999685241.00000000例5.2.3用牛顿法解方程组解先计算Jacobi矩阵由Newton迭代格式（10）得取初始值，则迭代6次可得精度为

=10-6的解

(3.000000，2.645751)T.解线性方程组例5.2.4用修正牛顿法解方程组在附近的解.解先计算Jacobi矩阵从出发计算解线性方程组，即，得于是得新的近似值为反复迭代结果如下：修正牛顿法的每一步迭代所用的计算时间较少，但迭代的收敛速度减低.为了提高收敛速度，可以在求出后，引入修正因子

i(

i为大于1的正数)，对求出的新解采用进行修正.3.最速下降法最速下降法又称梯度法.由著名数学家Cauchy于1847年提出.该方法是求解n元函数无约束最小化问题的一种重要解析方法，用于求解实系数非线性方程组(1)的一组根.该方法使用函数的梯度（一阶导数）或Hesse矩阵（二阶导数）对算法进行优化.即在射线进行搜索，（14）最速下降法计算步骤如下：例5.2.5用最速下降法求解问题：取初始值为.解(1)目标函数的梯度函数为由得令

，(2)从初始值出发进行一维搜索：t为最优步长，则有（3）从出发进行第二次迭代，计算令，则有故（4）进一步从出发进行第三次迭代，计算，令，则有此时，达到要求的精度，所以问题的最优解为谢谢数值分析方法主编

李冬果李林高磊面向“四新”人才培养普通高等教育系列教材第五章非线性方程的数值解法目录/Contents5.1-1非线性方程的近似求根

5.2非线性方程组的数值解

5.3非线性方程近似求根计算机实验

5.1-2非线性方程的迭代法的加速5.3非线性方程近似求根计算机实验根据5.1.1节的介绍可以知道，二分法是一种搜索算法，算法需要计算函数在搜索区域中点处的函数值，并将其与端点值进行比较和替换，从而达到缩小搜索区间的目的，将这一操作迭代进行，直到搜索区间的大小小于给定的阈值，即可以得到符合精度要求的近似解。由此，可以编写函数bisection来实现二分算法。1.二分法算法实现例解2.Newton法算法实现牛顿算法是一种迭代算法，需要首先需要定义函数function1和它的导函数dfunction1。function1=lambdax:x**3-x-1

dfunction1=lambdax:3*x**2–1将函数及其导函数代入牛顿法函数，定义初值为1.0，其他参数采用默认值，即：x2=newton_method(function1,dfunction1,1.0)得到方程近似解为1.67169988。3.非线性方程组的牛顿迭代法

importnumpyasnp

fromscipyimportlinalgasla

defnewton_equations(fun,