高斯-赛德尔迭代法的算法及程序设计

题 目 ： 高斯-赛德尔迭代法的算法及程序设计摘 要本 文 通 过 理 论 与 实 例 对 线 性 方 程 组 的 解 法 、 收 敛 性 及 误 差 分 析 进 行 了 探 讨 .在对 线 性 方 程 组 数 值 解 法 的 讨 论 下 用 到 了 高 斯 -赛 德 尔 迭 代 法 ， 进 一 步 研 究 和 总 结了 高 斯 -赛 德 尔 迭 代 法 的 理 论 与 应 用 ， 使 我 们 在 分 析 问 题 与 编 辑 程 序 时 能 更 好 的把 握 对 高 斯 -赛 德 尔 迭 代 法 的 应 用 关键词 Gauss-Seidel 迭 代 法 ； 收 敛 性 ； 误 差 分 析 ； 流 程 图 ； Mathematica 编程 目录第一章 高斯-赛德尔迭代法 ................................................1§1.1 高斯-赛德尔迭代法的提出 .......................................1§1.1.1 高斯-赛德尔迭代法的思想理论 ..............................1§1.1.2 高斯-赛德尔迭代法的定 义及表达形 式 ........................2§1.2 高斯-赛德尔迭代法的收敛性 .....................................1§1.3 高斯-赛德尔迭代法的 误差分析 ...................................1第二章 高斯-赛德尔迭代法的程序设计..................................... 1§2.1 高斯-赛德尔迭代法在上机中的应用 ...............................1§2.1.1 高斯-赛德 尔迭代法的流程图 ................................1§2.1.2 高斯-赛德尔迭代法的源程序 ................................1参考文献 ...............................................................22附录 ...................................................................231第一章 高斯-赛德尔迭代法考 虑 线 性 方 程 组 Axb其 中 为 非 奇 异 矩 阵 ， 对 于 由 工 程 技 术 中 产 生 的 大 型 稀 疏 矩 阵 方 程 组 （ 的 阶A A数 很 大 但 零 元 素 很 多 ） ,利 用 迭 代 法 求 解 线 性 方 程 组 是 合 适 的 .在 计 算n Axb机 内 存 和 运 算 两 方 面 ， 迭 代 法 通 常 都 可 利 用 中 有 大 量 零 元 素 的 特 点 .本 章 将 介 绍 迭 代 法 中 的 高 斯 -赛 德 尔 法 的 思 想 理 论 、 收 敛 性 及 误 差 分 析 .§1.1 高斯-赛德尔迭代法的提出§1.1.1 高斯-赛德尔迭代法的思想理论在研究雅可比迭代法时，计算 时，已得 （这些分别为1kix(1)()(1)2,,kkixx的第 k+1 次近似） ，Gauss-Seidel 迭代法认为在计算时启用新值，从而121,ix产生.1(1) ()()1(i nkkki jijjixbaxx具体原理如下图所示构造迭代(1)()0kkxBf产生向量序列 (0)(1)()kxx fAx图 1.1 基本迭代原理2§1.1.2 高斯-赛德尔迭代法的定义及表达形式定义 1.1 我们注意到在雅可比迭代法中并没有对新算出的分量 ，1kx， ，12kx进行充分利用．不妨设想，在迭代收敛的条件下，我们把1kix(1)()()()121311()()()()22222(1)()()()12,1kkkknkkkkkkkknnnnxaxaxbxaxaxb     式中第一个方程算出的 立即投入到第二个方程中，代替 进行计算，当 算1k ()k12kx出后代替 马上投入到第三个方程中计算，依次进行下去，这样也许会得到更好()2kx的收敛效果．根据这种思路建立的一种新的迭代格式，我们称为高斯-赛德尔（Gauss-Seidel）迭代公式，高斯=赛德尔迭代法的分量形式：(1)()()()121311()()()()2 2222(1)(1)(1)(1)2,kkkknkkkkkkkknnnnxaxaxbxaxaxb     高斯-赛德尔迭代法的矩阵形式：(1)(),0,)kkBf其中，1()DLU 1()fLb称为高斯-赛德尔迭代矩阵， 称为高斯-赛德尔迭代常量..B f§1.2 高斯-赛德尔迭代法的收敛性3根据上节所述，高斯-赛德尔迭代法的迭代格式为（1-1）(1)(),0,12)kkxBf其中， .DLU1()fLb本节要讨论的问题就是任意选取初始值 ，利用迭代格式(1-1)得到的向量序(0)x列 是否一定收敛，如果收敛的话需要满足什么条件？()kx下面我们给出一般迭代收敛的条件:定理1.2 简单迭代法(1-1)收敛的充分必要条件是迭代矩阵 的谱半B径 ．()1B定理1.3 若迭代矩阵 的某种范数 则（1-2-1）确定的迭代法对任意初值B1均收敛于方程组 的唯一解 。

0)Xxf*x特殊线性方程组迭代法的收敛性定理：定理1.4 设对于方程组 ,若系数矩阵 是严格对角占优矩阵，则AbA（1） 非奇异. A（2）Gauss-Seidel迭代法收敛.定理1.5 若系数矩阵 对称正定，则Gauss-Seidel迭代公式收敛.例1.1 已知方程组，1231x用Gauss-Seidel迭代法解此方程组的收敛性.方程组的系数矩阵，12A所以有， ，1D012L021U11()00GBU=23，det()02GIB4得 1230,故 ，因此 Gauss-Seidel 迭代法不收敛.()21B§1.3 高斯-赛德尔迭代法的误差分析科学计算的主要过程是：对给定的实际问题建立数学模型，通过已获得的有关基本数据，建立近似数值方法，设计算法编制程序，最后上机进行数值计算得到数值结果.其大致过程如下图：模型误差否是 验证结果的正确性与合理性结束 得到数值结果 上机计算舍入误差设置算法编制程序科学计算方法数学模型实际问题截断误差观测误差截断误差图 1.2 误差分析表定义 1.2 假设某一量的标准值为 近似解为 ，则 与 之差叫做近似解 的x*x*xx绝对误差（简称误差） ，记为 ，即()*定义 1.3 绝对误差与准确值之比 *(),0ix称为 的相对误差.*x定理 1.6 设 是方程组 的同解方程 的准确解，若迭代公式*xAxbxBf中迭代矩阵 的某种范数 ，则有(1)()kkBfB1q1） )1()(*)(1kkXqX52） )0()1(*)( XqXKk 第二章 高斯-赛德尔迭代法的程序设计第二章 高斯-赛德尔迭代法的程序设计 20 世 纪 50 年 代 是 用 数 字 计 算 机 求 解 电 力 系统 潮 流 问 题 的 开 始 阶 段 ， 人 们 普 通 采 用 以 节 点 导 纳 矩 阵 为 基 础 的 高 斯 -赛 德 尔迭 代 法 .此 方 法 原 理 简 单 ， 占 用 内 存 量 较 小 ， 编 程 容 易 实 现 ， 特 别 是 对 于 配 网 潮流 有 其 独 特 优 势 .但 是 此 算 法 也 有 着 其 致 命 缺 点 那 就 是 收 敛 速 度 比 较 慢 ， 尤 其 是随 着 电 力 系 统 的 发 展 。

网 络 中 的 节 点 增 多 ， 这 个 问 题 将 会 更 加 突 出 .本 章 将 研究高斯-赛德尔迭代法的流程图及程序应用.§2.1 高斯-赛德尔迭代法在上机中的应用§2.1.1 高斯-赛德尔迭代法的流程图在实际应用中，有时需解决的问题中运算很复杂且运算量也很大，这时我们就需要借助计算机的帮助解决实际问题，即利用高斯-赛德尔迭代法在 C 语言中的编程实现.高斯-赛德尔迭代法在计算机中的主要实现过程如下图所示6是输入 ,系数矩阵 ，矩阵 ，精度 ，循环nAB次数 Max，输出精度控制 prefor(z=0,z z>i?输出结果否图 2.3 高斯- 赛德尔迭代法流程图§2.1.2 高斯-赛德尔迭代法在计算机中的应用在 C 语言环境中解线性方程组的问题需要进行程序编辑，如果解决每一个线性方程组都需要重新编辑程序,就没体现计算机语言的简便性，所以需要一个程序使其对大多数问题都适用.例 2.1 设方程组 的系数矩阵的对角线元素 ， 为迭代次数Axb(1,2)in M容许的最大值， 为容许误差1 取初始向量令 k=0.2 对 i=1,2,…,n 计算 3 如果则输出结束；否则执行 44 如果则不收敛，终止程序；否则，转 2源程序：#include #include 7#define N 600void main(){int i;double x[4];double c[4][5]={10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,11,25};void GaussSeidel(double *,int,double[]);GaussSeidel(c[0],4,x);for(i=0;iN){printf("迭代发散 n\n");return;}}}输出结果8结果分析：从输出结果可以看出此方程组的迭代次数为 1，此时能得到精确结果是x[0]=-1.467391,x [1]=-2.358696,x[2] =0.657609,x[3] =2.842391从结果和原有知识可以知道其系数矩阵是严格对角占优的。

所以此迭代解法有很好的收敛性.参考文献[1] 贺俐、陈桂兴.计算方法[M].武汉水利电力大学出版社.1998-8-1[2] 袁慰平等.计算方法与实习[M].东南大学出版社.2000-7-1[3] 徐士良.数值方法与计算机实现[M].清华大学出版社.2006-2-1[4] 李炳钊.数值分析基础[M].上海:同济大学出版,1998. [5] 张光澄. 实用数值分析[M].四川:四川大学出版,2004. [6] 刘春凤.应用数值分析[M].北京: 冶金工业出版社,20059附录 C 语言编程源程序#include #include #include #include #define N 3main(){int i,j,k,s;float a[N][N]={0},L[N][N]={0},U[N][N]={0},sigma1,sigma2;for(i=0;i