数值分析6.ppt

1 前一章中介绍了解线性代数方程组的的直接法 直接法是经过有限次运算后可求得方程组精确解的方法 不计舍入误差 迭代法 从解的某个近似值出发 通过构造一个无穷序列去逼近精确解的方法 一般有限步内得不到精确解 高斯消去法 LU分解法的乘除次数为 当n较大时 计算量相当大 直接法只适应于低阶方程组 对于高阶稀疏方程组 用迭代法较好 P128 2 迭代法要解决的主要问题如下 1 如何构造迭代格式 2 构造的格式所产生的序列在什么情况下收敛 3 如果收敛 收敛的速率如何 4 近似解的误差估计 迭代方程 迭代格式 方程 迭代初值 收敛 如何构造迭代方程 P128 收敛速率 误差 3 6 1几种常用的迭代法格式 6 1 1 雅克比 Jacobi 迭代法 简单迭代法 若 i 1 2 n L U D Jacobi迭代阵 迭代方程 迭代格式 P129 4 当取定初始向量后 则一定是 6 3 的解 当然也是原方程Ax b的解 此时称Jacobi迭代关于初始向量收敛 若它收敛于 上式便产生一个向量序列 P129 迭代格式也可写成下标变量形式 5 若k M 则k k 1 将x赋值给y 转 否则 输出求解失败信息 停机 Jacobi迭代算法 输入A b 初始向量y 容许误差 容许最大迭代次数M 置k 1 形成迭代矩阵B 存放在A中 对i 1 2 n循环 若 则打印 求解失败 停机 否则 对j 1 2 n计算 迭代对i 1 2 n计算 若输出x k 停机 否则 P130 6 6 1 2高斯 赛得尔 Gauss Seidel 迭代法 P130 Jacobi迭代法 Gauss Seidel迭代阵 G S迭代法 只存一组向量即可 6 8 7 迭代格式也可写成下标变量形式 8 若k M 则k k 1 将x赋值给y 转 否则 输出求解失败信息 停机 Seidel迭代算法 输入A b 初始向量y 容许误差 容许最大迭代次数M 形成迭代矩阵B 存放在A中 对i 1 2 n循环 若 则打印 求解失败 停机 否则 对j 1 2 n计算 迭代对i 1 2 n计算 若输出x k 停机 否则 P131 置k 1 对i 1 2 n 9 6 1 3超松驰 SOR 法 加速 6 10 是松驰因子 Gauss Seidel迭代 中间值 松弛法可以看作是Seidel迭代法的加速 Seidel迭代是松弛法的特例 1G S迭代 0 w 2松弛迭代 P131 迭代 10 迭代格式 6 10 还可改写为 P131 132 6 9 即 6 11 称为松弛法的迭代矩阵 J2008 0 29 11 若k M 则k k 1 将x赋值给y 转 否则 输出求解失败信息 停机 松弛迭代法算法 输入A b 初始向量y 松弛因子 容许误差 容许最大迭代次数M 形成迭代矩阵B 存放在A中 对i 1 2 n循环 若 则打印 求解失败 停机 否则 对j 1 2 n计算 迭代对i 1 2 n计算 若输出x k 停机 否则 P132 置k 1 对i 1 2 n 12 6 2迭代法收敛性理论P132 任意选取初始向量 利用迭代格式 6 5 构造向量序列 向量序列是否一定收敛呢 例1方程组 的准确解是 收敛性与迭代矩阵有关 先看两个例子 13 把方程改写成 P133 取x 0 0 0 0 T 利用Jacobi迭代 计算结果如下 表6 1 从表中我们看到 近似解向量序列收敛 且收敛到准确解 14 例2下面方程组的准确解是 P133 取x 0 0 0 0 T 利用Jacobi迭代 计算结果如下 表6 2 从表中看到 此迭代发散 可以证明 除x 0 1 1 1 T以外 无论选什么初值都不会收敛 从上面两个例子看出 迭代序列收敛是有条件的 下面给出迭代法收敛性基本理论 15 定理1 对任意初始向量x 0 及常向量F 迭代格式 4 8 定理2 若迭代矩阵 的某种范数 收敛的充分必要条件是迭代矩阵B的谱半径 确定的迭代法对任意初值x 0 均收敛于方程组 x Bx F的唯一解x 则 4 8 迭代法的收敛条件 迭代法的误差估计 定理6 2 设x 是方程组Ax b的同解方程x Bx F的准确解 若迭代公式中迭代矩阵B的某种范数 则有 P133 16 定义1如果矩阵的每一行中 不在主对角线上的所有元素绝对值之和小于主对角线上元素的绝对值 即 则称矩阵A按行严格对角占优 定理3若线性方程组Ax b的系数矩阵A按行严格对角占优 则雅克比迭代法和高斯 赛得尔迭代法对任意给定初值均收敛 P136 类似地 也有按列严格对角占优 17 定理1证明先证必要性 假设收敛到 即 则有 令 则 对任何初始向量 0 要使向量序列收敛于零向量 必须 P134 由定理5 10即知 18 Why 充分性 假设 则非奇异 从而方程组有唯一解 在具体问题中 谱半径往往很难计算 但由于所以有时可以用来作为的一种估计 当时迭代一定收敛 不过这只是充分条件 记解为 于是 6 11 仍成立 由 6 12 出定理证毕 19 定理6 2证明 由迭代格式得 注意到 从而 故 P134 20 6 2 1三种迭代法迭代矩阵的谱半径与系数矩阵A的关系 6 2 1 1Jacobi迭代 Jacobi迭代的迭代矩阵 得 所以 上式写成分量形式为 即 P136 21 由定理6 1我们知 6 1 1 2Seidel迭代 Seidel迭代的迭代矩阵 由 定理6 3Jacobi迭代收敛的充分必要条件是行列式 6 13 的所有根 i 1 2 n 的绝对值 复数理解为模 小于1 P135 所以 22 写成分量的形式为 6 2 1 3松弛迭代 SOR迭代 对于松弛迭代 P135 Seidel迭代收敛的充分必要条件是行列式 6 14 的所有根 i 1 2 n 的绝对值小于1 定理6 4 由 我们得 23 注意到 得 写成分量形式为 松弛迭代收敛的充分必要条件是行列式 6 15 的所有根 i 1 2 n 的绝对值小于1 定理6 5 24 定义6 1 不可约 如果矩阵A不能通过行交换和相应的列交换变成为 其中A11 A22为方阵 则称A为不可约 定义6 对角优势 若矩阵满足 且至少有一个i值 上式中不等号严格成立 则称矩阵A具有对角优势 又称为弱对角占优 特别地 若所有的i值上式中不等号严格成立 则称矩阵A具有强对角占优 P136 对于一些特定的系数矩阵A 有一些特定的判别方法 为了说明方便起见 我们先引进一些概念 25 若A是强对角占优 或者A弱对角占优且不可约 则detA 0 A矩阵不可约的充分必要条件是A矩阵对应的邻接图是一个强连通图 P136 矩阵不可约与矩阵对应的邻接图有一个必然的联系 定理6 6 定理6 7 定理6 8 2 若松弛因子 满足0 1 则松弛迭代一定收敛 1 Jacobi迭代 Seidel迭代一定收敛 若A是强对角占优 或者A弱对角占优且不可约 则 26 松弛法收敛的必要条件是0 2 因为松弛法收敛 故有 由矩阵的特征值的性质可知 其中是矩阵的n个特征值 而 所以 P136 定理6 9 证明 27 上述定理说明 对于任何系数矩阵A 若要松弛法收敛 其松弛因子 0 2 然而 当松弛因子满足条件0 2时 并不是对所有系数矩阵A松弛法均收敛 还应满足一定条件 定理6 10 若矩阵A对称且对角线元素均为正实数 则当0 2时 松弛法收敛的充分必要条件是A正定 P137 松弛迭代法的收敛速度与松弛因子 有关 我们来看一个例子 28 取初始向量x 0 1 1 1 T 用SOR方法求解方程组 例6 3 P137 使 该方程组的精确解为x 3 4 5 解SOR方法的迭代公式为 P138 29 P138 分别取 1 8 1 22 迭代结果如表6 3 表6 4 30 P138 31 P138 32 33 使松弛法收敛最快的松弛因子叫最优松弛因子 记为 opt 对于某些特殊类型的矩阵 可以证明最优松弛因子为 其中是迭代矩阵的谱半径 对一般的矩阵 即使是正定对称矩阵 目前尚无法确定 opt的理论值 实际计算时 大部分由经验或通过试算来确定 opt的一个近似值 P138 从上表我们可以看到 在相同的初始条件下 1 8时SOR方法迭代了65步 而 1 22时SOR方法仅迭代了11次 34 定理6 11 P139 设1 A为分块三对角阵 且 2 Jacobi迭代的迭代矩阵 的特征值为实值 且 则 1 当时 SOR迭代收敛 2 SOR法最优松弛因子 35 P139第6章学习与思考题作业2 3 36 EX2 1 构造Jacobi迭代 Seidel迭代格式 2 讨论Jacobi迭代 Seidel迭代的收敛性 解 P139 艰难计算 37 2 讨论Jacobi迭代 Seidel迭代的收敛性 所以Jacobi迭代收敛 所以Seidel迭代收敛 注 Seidel迭代 收敛性 Seidel迭代收敛