第6章 逐次逼近法.pptVIP

第六章 逐次逼近法 非线性方程的迭代解法 6.1对分法 6.2 迭代法 6.3 Newton迭代法 6.4 弦截法 6.5 非线性方程组的Newton迭代法 While(|a-b|eps) x=(a+b)/2 f(x) 若(|f(x)|eps) x为解 若f(x)*f(b)0 修正区间为[x,b] 若f(a)*f(x)0 修正区间为[a,x] End while 每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求一个根，使用条件限制较大 算法 ?2 x x* 不能保证 x 的精度 f (x) = 0 x = g (x) 等价变换 f (x) 的根 g (x) 的不动点 思路 从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), …, xk+1 = g(xk), … 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。 迭代法的基本步骤如下： 1、给出方程的局部等价形式 2、取合适的初值，产生迭代序列 3、求极限 易知，该值为方程的根 一定收敛吗？ x y y = x x* y=g(x) x0 p0 x1 p1 ? x y y = x x* y=g(x) x0 p0 x1 p1 ? 若满足： 1、 2、 可导，且存在正数L1，使得对任意的x，有 则有： 1、存在唯一的点 2、 迭代收敛，且有误差估计 定理 ①存在唯一性 ② 做辅助函数 ，则有 所以，存在点 若 ，则有： 又， 则 所以，任意的初值都收敛 证明： ③误差估计 由p的任意性，令 证毕 构造满足定理条件的等价形式一般难于做到。要构造收敛迭代格式有两个要素： 1、等价形式 2、初值选取 下面我们开始介绍若干种迭代法的构造方法 将f(x)在初值处作Taylor展开 取线性部分作为f(x)的近似，有： 若 ，则有 记为 类似，我们可以得到 x y x* x0 这样一直下去，我们可以得到迭代序列 Newton迭代的等价方程为： 所以 若f(x)在a处为单根，则 所以，迭代格式收敛 收敛速度 函数在a处作Taylor展开 若a为p重根，取迭代格式为： 即 Newton迭代收敛速度快，格式简单，应用广泛 例 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求?=10-5. 解 Newton迭代格式为 0000-0000.0000000003 0.0000000003 0.5 00000 1 2 3 4 |xk-xk-1| ?(xk) xk k 注：Newton’s Method 收敛性依赖于x0 的选取。 x* x0 ? x0 ? x0 * 赣南师范学院数学与计算机科学学院 直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3 数量级，存储量为n2量级，这在n比较小的时候还比较合适（n400），但是对于现 在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵往往是系数矩阵 就是这些矩阵含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时 间和存储单元。因此我们有必要引入一类新的方法：迭代法。 迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一 个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根 对方程组 做等价变换 如：令 ，则 则，我们可以构造序列 若 同时： 所以，序列收敛 与初值的选取无关 定义6.1：（收敛矩阵） 定理： 矩阵G为收敛矩阵，当且仅当G的谱半径1 由 知，若有某种范数 则，迭代收敛 6.1 Jacobi迭代 格式很简单： Jacobi迭代算法 1、输入系数矩阵A和向量b，初始值X0和误差控制eps 2、算出D,L,U 3、%Jacobi.m Function y=Jacobi(A,b,X0) D=diag(diag(A)); L=-tri(A,-1); U=-triu(A,1); B=D\(L+U); F=D\b; Y=B*X0+F; N=1; While(norm(y-x0)eps) X0=y; y=B*x0+f;n=n+1; End y 4、输出解y 迭代矩阵 记 易知，Jacobi迭代有 收敛条件 迭代格式收敛的充要