数值方法非线性方程的近似解法

《数值方法非线性方程的近似解法》由会员分享，可在线阅读，更多相关《数值方法非线性方程的近似解法（65页珍藏版）》请在金锄头文库上搜索。

1、第二章 非线性方程的近 似解法第二章 非线性方程的近 似解法2.0 简介 2.1 二分法（对分法） 2.2 简单迭代法 2.3 Newton迭代法2.0 简介求解非线性方程 f(x)=0 一、问题困难：方程的解难以用公式表达。例如:1)多项式方程：需要一定精度的近似解！2)超越方程:方程 的解 称为方程 的根或称为 的零点。二、概念方程可能有多个实根，我们只能逐个求出来。二、概念设在区间a,b上方程有一个根，则称该区间 为方程的一个有根区间。若在区间a,b上方 程只有一个根，则称该区间为方程隔根区间。Remark：若能把有根区间不断缩小，则可以得出根 的近似值。三、根的隔离基于函数f(x)的连

2、续性质，常用的根的隔离的方 法有：描图法与逐步搜索法。 1、描图法：画出y=f(x)的简图，从曲线与x轴交点 的位置确定出隔根区间，或者将方程等价变形为 g1(x)=g2(x)，画出函数y= g1(x)和y=g2(x)的简图， 从两条曲线交点的横坐标的位置确定隔根区间。 2、逐步搜索法：先确定方程f(x)=0的所有实根所在 区间a,b，再按照选定的步长 （n为正整 数），取点xk=a+kh(k=0,1,n)，逐步计算函数值f(xk)，依据函数值异号以及实根的个数确定隔根区 间。必要时可调整步长h，总可把隔根区间全部找出 。三、根的隔离三、根的隔离问题：扫描间距？2.1 二分法（对分法）关于求解

3、算法:算法多样：比如刚才的逐步搜索法考虑因素：1稳定性； 2收敛性； 32.1 二分法（对分法）一、算法设 在a,b上连续，f(a)f(b)0f (a) f (b)=0f (a) =0打印b, k打印a, k结束是是是否否否m=(a+b)/2|a-b|0打印m, ka=mb=m结束k=K+1是是否否输入 k = 0算法(二分法) 2.2 迭代法即序列 的极限 为 的根。当 连续时，有或 。 即 一、迭代法 1.基本思想：令方程 ,将其变成一个等价的方程 ,构造 , 称为迭代数列，或迭代过程。称为迭代函数,称为迭代公式因此，我们可以通过求迭代数列的极限的方法来 求得方程f(x)=0的根。Rema

4、rk：可以通过不同的途径将f(x)=0化为 x=(x)的形式，从而构造不同的迭代公式，得到不同的迭代序列。在所有这些构造的迭代公式中 形成的序列中，有的序列是收敛的，而有些是发 散的。问题：如何选取合适的迭代函数(x) ？(x)应满足什么条件，序列xk收敛？怎样加速序列xk的收敛？xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p12.迭代法的收敛定理（2）对任意初值x0a,b由迭代公式则有:定理1.（全局收敛定理）设方程 ，如果满足（3）存在常数01称为超线性收敛；p

5、2称为平方收敛（二次收敛）。 p 越大，收敛速度越 快；反之，p越小，收敛速度就越慢。因此，迭代法的 收敛阶是对迭代法收敛速度的一种度量。（ C称为渐近误差常数）定义：设 收敛于 ，令迭代误差，如果存在实数 及非零正常数C使得则称该迭代过程以及该迭代式是p阶收敛的，也 称相应的迭代法是p阶方法。1.迭代-加速公式记 ，则由微分中值定理有三、迭代法的加速其中在xk与x*之间。假定 在根x*附近变化不大，可设 ，由 迭代收敛条件有 ，故上式可写为：整理为：得到迭代加速公式上式说明，把 作为根的近似值时，其绝对误差大 致为 。如果把该误差值作为对 的一种补偿，便可以得到更好的近似值记Remark3：

6、该方法的缺点是需估计 的近似值。Remark1：该迭代法对原迭代式的各近似值 在根x*的两侧往复地趋于x*时较为有效。在 这种情况下，不但能加快新序列的收敛，还 能有效地防止死循环的出现。Remark2：若序列xk单调趋于x*时，上式 不能起到加速收敛的作用。xyy = xx*y=(x)x0p0x1p12埃特金（Aitken）加速方法记用平均变化率代替迭代加速公式中的 ，于是有则从上式可以看出，第二项是对 的一种补偿。因此可以得下述Aitken加速方法： Remark：因为迭代过程xk+1= (xk)总是在根x*附近 进行，因此用平均变化率代替迭代加速公式中 的是有意义的。记对于埃特金（Ait

7、ken）加速方法有如下的定理：定理3：如果由迭代公式xk+1= (xk)产生的数列xk 满足： （1）收敛于根x*；（2）则由埃特金（Aitken）加速公式产生的数列 比数列xk较快的收敛于根x*，即取前两项近似代替 得近似 的线性方程一、Newton迭代法1.牛顿法的基本思想同Newton-Raphson公式2.3 Newton迭代法设 是 的一个近似根，则基本思想：将非线性方程转化为线性方程来求解。由 知 是 处 的切线 与 轴交点的横坐标，故Newton法的几何意义是逐次用切线代替曲线， 求切线与横坐标轴的交点。 Newton法亦称为切线法。（如下图）设 ,令解为 得显然是 的同解方程。

8、 上式称为 的Newton迭代法，对应的方程x* x0x1x2xyf(x)Newton迭代法逼近过程证明：只需证满足迭代法局部收敛定理的两个条件。2.局部收敛性及条件（1）（2）知，(x)在x*的邻域可导。定理（Newton迭代法局部收敛性）：设 为 的 根，如果：（1）函数f(x)在 的邻域具有连续的二阶 导数；（2）在 的邻域 。则存在 的某个邻域 ，对于任意的初始 值x0S，由Newton迭代公式产生的数列收敛于根 。由迭代函数 得: 根据连续函数的性质，一定存在x*的某个 邻域 ，对于任意的xS ，有Remark：上述定理对于初值x0的要求比较 高，只有当初值选的充分靠近时，才能 保证

9、序列收敛。证毕显然又有3.非局部收敛性 定理（Newton迭代法的非局部收敛性）：设x*是 方程f(x)=0在隔根区间a,b内的根，如果满足（2）取 使（1）对于xa,b， 连续且不变号； 则由Newton迭代公式产生的数列收敛于根x*。Remark：定理的几何解释见下图。满足定理条 件的情况只有4种。yx0aby=f(x)x0(a )x0取靠近b一侧yx0a by=f(x ) x0(b )x0取靠近a一侧yx0aby=f(x )x0(c)x0取靠近a一侧yx0a by=f(x ) x0(d )x0取靠近b一侧证明：仅就图(c)的情况进行证明。此时，有要证 ，应证数列xk单调递增上有界。（1）

10、用数学归纳法证明数列上有界，即证xk0，则可以保证 Newton迭代法的收敛性。 二、迭代法的收敛阶若01称为超线性收敛；p 2称为平方收敛（二次收敛）。p 越大，收敛速度越快 ；反之，p越小，收敛速度就越慢。因此，迭代法的收 敛阶是对迭代法收敛速度的一种度量。（ C称为渐近误差常数）定义：设 收敛于 ，令迭代误差，如果存在实数 及非零正常数C使得则称该迭代过程以及该迭代式是p阶收敛的，也 称相应的迭代法是p阶方法。定理：（1）在迭代法的局部收敛定理的条件下， 即x*是方程 的根，满足迭代函数 在x* 的邻域内可导，且在根x*的某个邻域 内，对于任意xS，有 ，则迭代 法是线性收敛的。（2）由

11、Newton迭代公式xk+1= (xk)产生的数列xk 若满足Newton迭代法的非局部收敛定理，则 Newton迭代法是平方收敛的。证明：（1）因为迭代函数(x)在根x*的邻域 内可导，故由Lagrange中值定理有其中在xk与x*之间。由 知，迭代法是线性收敛的。（2）由Newton迭代法的非局部收敛定理证明过程知，即因为 在邻域内不变号，故 有 即Newton迭代法是平方收敛的。证毕三、牛顿迭代法的变形Newton迭代优点：格式构造容易；迭代收敛速度快；Newton迭代缺点：对初值的选取比较敏感，要求初值充分接近真解；对重根收敛速度较慢；当函数复杂时，导数计算工作量大1牛顿下山法 牛顿迭

12、代法依赖于x0（1）敏感度高；（2）对重根收敛慢；2. 牛顿下山法：修正（1）选取下山因子；（4）计算f (xk+1)，并比较 与 的大小，分以下二种情况：1）若 ，则当 时，取x*xk+1，计算过程结束; 当 时，则把xk+1作为新的xk值，并重复回到（3）。1牛顿下山法 牛顿下山法计算步骤可归纳如下：（1）选取初始近似值x0；（2）取下山因子 = 1；（3）计算当； 且 , 则将下山因子缩小一半，取/2代入，并转向（3）重复计算。 xk+1加上一个适当选定的小正数，2）若 ，则当且 ，取x* xk，计算过程结束；否则若，而 时，则把即取xk+1+作为新的xk值，并转向（3）重复计算；例5：求方程f (x) = x3 x 1 = 0 的根kxk010.611/251.14063211.36681311.32628411.32472牛顿下山法的计算结果：2针对重根情形的加速算法设 是方程的m 重根，并且存在函数 ，使得 可见，此时牛顿迭代法仅为线性收敛法1：令法2：为加速收敛，可以采取如下两种方法：3、 单点弦截法 ： 牛顿法一步要计算 f 和 f ，相当于2个函数值。现用 f 的值近似 f :x0x1切线 割线 切线斜率 割线斜率x24、 双点弦截法 ：切线斜率 割线斜率需要2个初值 x0 和 x1 。x0x1x2