第四章线性方程组和非线性方程组的迭代法.ppt

* 第三章 矩阵的初等变换与线性方程组 一,矩阵的初等变换 第四章 线性方程组和非线性方程组的迭代法 第一节 引言 是一个向量序列, 定义: 与第二章单个方程的想法类似,我们按某种方式构造一个序列, 使这个序列 收敛到精确解. 由于方程组的解是一个向量,所以现在要构造的是一个向量序 列,而且还涉及向量序列的收敛问题. 则称向量序列收敛,记为 * 定义: 是一个向量, 是一个实值函数,记为 如果这个函数满足下列三条: 范数是绝对值概念的一种推广 则称 为 的范数,上述三个条件又称范数公理. 三种常用的向量范数: * 定理: 定义:A是n阶方阵, 是A的一个非负实值函数,记为 则称 为 的范数. 三种常用的矩阵范数: 如果满足下列范数公理 称列范数 称行范数 * 定义: A是n阶方阵, x是n维列向量，如果满足 则称这种矩阵范数和向量范数是相容的。这样的矩阵范 数称为矩阵的自然范数。 上述三种常用的矩阵范数都是自然范数。 定义: A是n阶方阵，A的特征值为： 称为A的谱半径。 定理：对任意方阵A必有 * 第二节 迭代法的基本概念和收敛条件 线性方程组的迭代法的基本思想与第二章单个方程的迭代法类似 首先将f (x) = Ax – b = 0转化为等价的方程组 x = Bx+d，这里B是 一个常数矩阵，称为迭代矩阵，x是一个常向量。 对于给定的初始向量 ，由迭代格式： 定义1(初等变换) 就可以构造出一个向量序列 使之收敛于方程组的精确解。 线性方程组迭代法的收敛定理： 定理:对于方程组x=Bx+d,如果 则有以下结论: 该方程组有唯一解; 对于任意给定的初始向量 ,由上述迭代格式 构造的向量序列 收敛于方程的精确解 ; 有误差估计式: * 注意：这个定理的条件是收敛的充分条件,不是充要条件. 与单个方程的结论类似 越小,收敛越快. 矩阵的等价 定理:由上述迭代格式构造的序列收敛的 同理, 越小,收敛越快. 充要条件 * 第三节 解线性方程组的迭代法 取初值: 行最简形,标准形,等价类 一 Jacobi迭代法 先看一个例子: * 由此可得到Jacobi迭代法: 行最简形,标准形,等价类 Jacobi迭代法的一般形式 在实际计算时常常采用其分量形式: * 二,初等矩阵 定义4(初等矩阵) 由上述迭代矩阵的结构可以看出,对于Jacobi 迭代的收敛问题有比较简单的判别法: 如果方程组的系数矩阵A是严格主对角占优的,则Jacobi 迭代法对于任意的初始向量都是收敛的. 这个条件等价于 　 * 取初值: 行最简形,标准形,等价类 二 Gauss-Seidel迭代法 把Jacobi迭代稍做改进得: Gauss-Seidel迭代法是充分利用了有效信息,以改善 计算效果 Jacobi 迭代需要两套储存单元, 而G-S迭代只需一套储存单元. * 行最简形,标准形,等价类 G-S迭代法的一般形式 其分量形式: * 对于G-S 迭代的收敛问题也有比较简单的判别法: 如果方程组的系数矩阵A是严格主对角占优的,则 G-S 迭代法对于任意的初始向量都是收敛的. 如果方程组的系数矩阵正定, 则 G-S 迭代法对于任意的初始向量都是收敛的. 注意:上述条件都是收敛的充分条件 * 行最简形,标准形,等价类 三 松弛迭代法 这是在G-S迭代基础上的一种加速方法,它分为迭代和加速两个过程 迭代: 加速: * 第四节 解非线性方程组的迭代法 一 一般迭代法 与单个非线性方程迭代法类似,先化为等价的方程组 * 由此就可以建立一个迭代格式: 一般迭代法的收敛条件与单个方程迭代法的收敛条件很类似 称为迭代向量函数 * Th1 定理 设D是n 维空间的一个连通区域,若迭代向量函数g(x) 满足: (1) (2)g(x)的所有一阶偏导数在D上连续,且一阶偏导数矩阵的范数小于1,即: 则对于任意给定的D中的初始向量,该迭代法都收敛于方程组的 精确解.且范数越小收敛越快. * Th5及推论 二 Seidel迭代法 Seidel迭代法是一般迭代法的一种改进,其迭代格式为: 一般地 * 利用初等变换求逆矩阵 第五节 矩阵的条件数和病态方程 组的处理 * 例 由此可见方