方程与方程组的迭代解法PPT课件.ppt

引言 1 6 1方程求根法 试探法与二分法迭代法及其收敛条件迭代法收敛速度加速收敛技术牛顿迭代法弦割法 2 6 1 1试探法和二分法 理论依据 3 试探法 4 二分法 区间平分法 5 于是 6 求方程f x 0的根的二分法算法 7 例题 例设方程解 取h 0 1 扫描得 又即在有唯一根 8 有根区间 1 300000000 1 400000000 1 300000000 1 350000000 1 300000000 1 325000000 1 312500000 1 325000000 1 318750000 1 325000000 1 321875000 1 325000000 1 323437500 1 325000000 1 324218750 1 325000000 1 324609375 1 325000000 x 1 32480f 3 6990 10 4 9 6 1 2迭代法及收敛性 对于有时可以写成形式 如 10 迭代法及收敛性 考察方程 这种方程是隐式方程 因而不能直接求出它的根 但如果给出根的某个猜测值 代入中的右端得到 再以为一个猜测值 代入的右端得反复迭代得 11 迭代法及收敛性 若收敛 即故是的一个根 12 迭代法的几何意义 交点的横坐标 y x 13 简单迭代法 将变为另一种等价形式 选取的某一近似值 则按递推关系产生迭代序列 这种方法称为简单迭代法 14 例题 15 例题 精确到小数点后五位 16 例题 但如果由建立迭代公式仍取 则有 显然结果越来越大 是发散序列 17 迭代法的收敛性 18 迭代收敛定理 证明 不失一般性 不妨设否则为方程的根 首先证明根的存在性令 19 迭代收敛定理 则 即由条件2 是上的连续函数所以是上的连续函数 故由零点定理在上至少有一根 20 迭代收敛定理 再证根的唯一性设有均为方程的根则因为0 L 1 所以只可能 即根是唯一的 21 迭代收敛定理 最后证迭代序列的收敛性与n无关 而0 L 1即 22 迭代收敛定理 误差估计若满足定理条件 则这是事后估计 也就是停机标准 L越小 收敛速度越快 这是事前估计 选取n 预先估计迭代次数 23 24 例题 例证明函数在区间 1 2 上满足迭代收敛条件 证明 25 例题 26 例题 若取迭代函数 不满足收敛定理 故不能确定收敛到方程的根 27 简单迭代收敛情况的几何解释 28 6 1 3迭代收敛速度 迭代法收敛的阶定义设序列收敛到 若有实数和非零常数C 使得其中 则称该序列是p阶收敛的 C称为渐进常数 29 迭代法收敛的阶 当p 1时 称为线性收敛 当p 1时 称为超线性收敛 当p 2时 称为平方收敛或二次收敛 迭代法p阶收敛的充要条件是 迭代函数满足 30 6 1 4加速收敛技术 31 32 6 1 5Newton迭代法 33 Newton迭代法 去掉的二次项 有 即以x1代替x0重复以上的过程 继续下去得 34 2019 12 28 35 Newton迭代法 36 Newton迭代法几何解释 几何意义 37 例用牛顿法求的近似解 解 由零点定理 38 例题 例用Newton法计算解 39 Newton迭代法算法框图 40 Newton迭代法算法 41 Newton迭代法收敛性 定理设函数 且满足若初值满足时 由Newton法产生的序列收敛到在 a b 上的唯一根 42 Newton迭代法收敛性 证明 根的存在性根的唯一性 43 Newton迭代法收敛性 收敛性 44 Newton迭代法收敛性 45 Newton迭代法收敛性 46 Newton迭代法收敛性 推论在定理条件下 Newton迭代法具有平方收敛速度 47 Newton迭代法的变形 48 6 2 4弦截法 Newton迭代法有一个较强的要求是且存在 因此 用弦的斜率近似的替代 49 弦截法 令y 0 解得弦与x轴的交点是坐标x2 50 弦截法 51 弦截法的几何解释 52 弦截法收敛定理 53 6 2线性方程组迭代解法 迭代法适用于系数矩阵为稀疏矩阵的方程组 基本迭代法基本迭代法的收敛条件 54 6 2 1基本迭代法 Jacobi迭代法 55 56 6 2 1基本迭代法 Seidel迭代法 57 58 6 2 1基本迭代法 SOR迭代法 59 6 2 2基本迭代法收敛条件 60 迭代收敛定理 61 例6 4判断求解AX b的三种迭代法是否收敛 其中A为 62 63 2 A对称正定 但 2D A 0 说明2D A不正定 故Jacobi迭代发散 0 2时SOR迭代收敛 3 A为严格对角占优矩阵 故Jacobi迭