第7章 解方程组

第 七 章  解 方 程 组 的 数 值 方 法 §1 引  言 在自然科学和工程技术中有很多问题的解决归结为求解线性方程组或者非线性方程组的数学问题。例如，电学中网络问题，用最小二乘法求实验数据的曲线拟合问题，三次样条的插值问题，用有限元素法计算结构力学中一些问题或用差分法解椭圆型偏微分方程边值问题等等。 在工程实际问题中产生的线性方程组，其系数矩阵大致有两种，一种是低阶稠密矩阵（这种矩阵的全部元素都存贮在计算机的存贮器中）；另一类是大型稀疏矩阵（此类矩阵阶数高，但零元素较多）。 本章§2一§6介绍求解线性方程组的直接法。目前这种方法是计算机上解低阶稠密矩阵的有效方法。§8将介绍计算机上解大型稀疏矩阵方程组的迭代法。 §2 高 斯 消 去 法 高斯消去法是一个古老的求解线性方法组的方法，但由它改进得到的选主元的高斯消去法则是目前计算机上常用的解低阶稠密矩阵方程组的有效方法。 例1  用高斯消去法解方程组 （2.1） 解  第1步：将（2.1）的第一个方程分别乘上（ ）和（ ），并分别加到第二、第三个方程上去，则得到与原方程组等价的方程组 （2.2） 第 2步 ： 将（2.2）的第二个方程乘上2加到第三个方程，消去其中的未知数 ，又得到与原方程组等价的三角形方程组 （2.3） 最后由上述方程组，用回代的方法，即可求得原方程组的解为： 若用矩阵来描述消去法的约化过程，即为 这种求解过程，称为具有回代的高斯消去法。  从这个例子看出，用高斯消去法解方程组的基本思想是用矩阵行的初等变换将系数矩阵A约化为具有简单形式的矩阵（上三角形矩阵，单位矩阵等），而三角形方程组是很容易解的。 下面讨论求解一般线性方程组的高斯消去法。设有n个未知数的线性方程组                      （2.4） 引进记号    ， ， （2.4）可用矩阵形式 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示                （2.5） 且为了下面讨论方便， 记 ， 。假设A为非奇异矩阵（即设 ） 。 第1步 ：设 计算乘数 ， 用 乘上（2.4）第一个方程，加到第 个方程上去 即施行行的初等变换 ， ，消去第2个方程 ～ 第 n个方程的未知数 ，得到（2.4）的等价方程组 （2.6） 记为 其中（2.6）式中右上角标为（2）的元素为这一步需要计算的元素，计算 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 为 第 k步 ： 继续上述消去过程，设第1步 ～ 第k— l步计算已经完成，得到与原方程组等价的方程组 （2.7） 记为  现进行第 步消元计算，设 ，计算乘数 ， 用 乘（2.7）的第 个方程，加到第 个方程上去 ，消去第 个方程 的未知数 ，得到与原方程组等价的方程组（略），简记为  其中  元素计算公式为： （2.8） 与 前 行元素相同， 与 前 个元素相同。 最后，重复上述约化过程，即 且设 ，共完成 步消元计算，得到与原方程组（2.4）等价的三角形方程组 （2.9） 用回代的方法，即可求得（2.9）的解，计算公式为 ，                     （2.10） 元素 称为约化的主元素。将（2.4）约化为（2.9）的过程称为消元过程，（2.9）求解过程（2.10）称为回代过程，由消元过程和回代过程求解线性方程组的方法称为高斯消去法。 定理1（高斯消去法）设 ，其中 。如果约化的主元素 ，则可通过高斯消去法（不进行交换两行的初等交换）将方程组 约化为三角形矩阵方程组（2.9）且消元和求解公式为 消元计算 ， 回代计算 ， 如果A为非奇异矩阵时，但可能有某 在第 列存在有元素 ，于是可能通过交换 的第 k行和第 行元素将 调到 位置，然后再进行消元计算。于是，在A为非奇异矩阵时，只要引进行交换，则高斯消去法可将 约化为三角形方程组（2.9），且通过回代即可求得方程组的解。 高斯消去法计算量： （1）消元计算： 第 k步 。 计算乘数：需要作 次除法运算； 消元： 需作 次乘法运算； 计算 ：需作 次乘法运算； 于是完成全部消元计算共需要作 次乘除法运算。 （2） 回代计算：共需要作 次乘除法运算。 于是，用高斯消去法解 （其中 ）的计算量为共需作 次乘除法运算。 下面比较用高斯消去法和用克莱姆（Cramer）法则解20阶方程组的计算量。 表 7-l 方 法 高斯消去法 Cramer法则 计算量 3060次乘除法 约5 次乘法       如果计算工作是在每秒作 次乘除法计算机上进行，那末用高斯消去法解20阶方程组约需要0.03秒 时间即可完成，而用克莱姆法则大约需 小时完成（大约相当于 年）。由此可知克莱姆法则完全不适用在计算机上求解高维方程组。 在电子计算机上用高斯消去法解低阶稠密矩阵线性方程组时要注意几点： （1） 要用一个二维数组 存放系数矩阵A的元素，用一 维数组 存放常数项b分量。 （2）需要输入的数据 。 （3）约化的中间结果 元素冲掉A元素， 冲掉b，乘数 冲 掉 。例如，计算 1． ， ； 2．       ； 3． 。 （4）在高斯消去法中一般要引进行交换。 （5）如果不存在 ，使 ，要输出方程没有唯一解的信息。 §3  选 主 元 素 的 高 斯 消 去 法 用高斯消去法解 时，其中设A为非奇异矩阵可能出现对 的情况，这时必须进行带行交换的高斯消去法。但在实际计算中即使 但其绝对值很小时，用 作除数，会导致中间结果矩阵 元素数量级严重增长和舍入误差的扩散，使得最后的计算结果不可靠。 例2  设有方程组 解  该方程组的精确解为 。但直接用高斯消去法求解却得到一个很坏的结果： 。下面用具有行交换的高斯消去法（避免小主元）求解。 回代求解得 。对于用具有舍入的3位浮点数进行运算，这是一个很好的计算结果。 直接用高斯消去法计算失败的原因，是用了一个绝对值很小的数作除数，乘数很大，引起约化中间结果数量级严重增长，再舍入就使得计算结果不可靠了。 这个例子告诉我们，在采用高斯消去法解方程组时，小主元可能导致计算失败，故在消去法中应避免采用绝对值很小的主元素。对一般矩阵方程组，需要引进选主元的技巧，即在高斯消去法的每一步应该在系数矩阵或消元后的低阶矩阵中选取绝对值最大的元素作为主元素，保持乘数 ，以便减少计算过程中舍入误差对计算解的影响。 这个例子还告诉我们，对同一数值问题，用不同的计算方法，得到的结果的精度大不一样，一个计算方法，如果用此方法的计算过程中舍入误差得到控制，对计算结果影响较小，称此方法为数值稳定的；否则，如果用此计算方法的计算过程中舍入误差增长迅速，计算结果受舍入误差影响较大，则称此方法为数值不稳定。因此，我们解数值问题时，应选择和使用数值稳定的计算方法。 3.1 完全主元素消去法 设有线性方组 ，其中A为非奇异矩阵。方程组的增广矩阵为 第1步( ) ：首先在 A中选主元素，即选择 使 再交换 的第1行与第 行元素，交换A的第1列与第 列元素，将 调到（l,1）位置（交换后增广阵为简单起见仍记为 ）。然后，进行消元计算。 第k步：继续上述过程，设已完成第1步到第 k— l步计算， 约化为下述形式： 第 k步 选 主 元 区 域 于是第k步计算： 对于k= l，2，… ，n—l做到（3） （1）选主元素：选取 ，使 （2）如果 ，则交换 第 k行与第 行元素；如果 ，则交换A的第k列与第 列元素。 （3）消元计算： （4）回代求解 经过上面的过程，即从第1步到n— 1步完成选主元，交换两行，交换两列，消元计算，原方程组约化为 其中 为未知数 调换后的次序。回代求解 3.2 列主元素消去法 完全主元消去法是解低阶稠密矩阵方程组的有效方法，但完全主元素方法在选主元时要花费一定的计算机时间，现介绍一种在实际计算中常用的部分选主元（即列主元）消去法。列主元消去法即是每次选主元时，仅依次按列选取绝对值最大的元素作为主元素，且仅交换两行，再进行消元计算。 设列主元素消去法已经完成第1步到第 k— l步的按列选主元，交换两行，消元计算得到与原方程组等价的方程组 ，其中为简单起见，增广矩阵的元素仍记为 ，即 第 k步 选 主 元 区 域 于是第k步计算如下： 对于k= l，2，…，n—l做到（4） （1）按列选主元：即选取 ，使 （2）如果 ，则A为奇异矩阵，停止计算 （3）如果 ，则交换 第 k行与第 行元素 （4）消元计算： （5）回代求解 计算解 在常数项b(n)内得到。 例3  用列主元素消去法解方程组 解  用4为有效数字计算如下： 经回代求解得 . §4  矩 阵 的 三 角 分 解 现用矩阵理论来研究高斯消去。消元的一步等价于用一个单位下三角矩阵左乘前一步约化得到的矩阵。先说明在消元过程中，系数矩阵 是如何经矩阵运算约化为上三角矩阵 的。设 ， 若 ，令 ， ， 施行第一步消元，得到 若 ，令 ， ， 施行第二步消元，得到 如此下去，施行第n-1步消元，得到 由此可见，在顺序高斯消去法的过程中，系数矩阵 经过一系列单位下三角矩阵的左乘运算约化为上三角矩阵 ，即 （4.1） 其中 ， 记    ， ，                    （4.2） 容易验证 则由（4.1）知                （4.3） 其中 分别为单位下三角矩阵和上三角矩阵。 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 上述讨论，得到下述重要定理。 定理2（矩阵的三角分解）设 。 如果A的顺序主子式 ， 则A可分解为一个单位下三角阵与一个上三角阵的乘积，即 ，且分解是唯一的。 证明（略）。 称矩阵的三角分解 为杜利特尔（Doolittle）分解。 注：在定理2条件下，同样可有三角分解 ，其中 分别为下三角矩阵和单位上三角矩阵。称矩阵的这种分解为克劳特（Crout）分解。 例4 利用三角分解方法解方程组 解  进行三角分解 求解 ，即 ，得到 再求解 ，即 ，得到 . §5  解三对角线方程组的追赶法 在一些实际问题中，如用三次样条函数的插值问题，用差分法解二阶线性常微分方程边值问题等，最后都导致解三对角线方程组 ，即 (5.1) 其中 满足条件 （1） （2） ， （3）                                               （5.2） 对于具有条件（5.2）的方程组（5.1），我们介绍下述的追赶法求解。追赶法具有计算量少，方法简单，算法稳定等特点。 定理3  设有三对角线方程组 ，且 满足条件（5.2），则 为非奇异矩阵。 证  用归纳法证明，显然，对n＝2时有 现设定理对n－1阶满足条件（5.2）的三对角阵成立，求证对满足条件（5.2）的n阶三对角阵定理亦成立。由 和消去法，有 显然， ，其中 ， 且有 于是由归纳法假定有 ，故 . 定理4 设 ，其中 为满足条件（5.2）的三对角阵，则 的所有顺序主子式都不为零，即  . 证  由于 是满足（5.2）的n阶三对角阵，因此， 的任一个顺序主子式阵 ，亦是满足（5.2）的k阶三对角阵，由定理3知 。于是，由矩阵的三角分解定理得 ，即    . 由矩阵乘法，可得计算待定系数 的计算公式，即 ① ， ， ； ② ， ； ③ ， 于是，得到解（5.1）的追赶法公式。 （1） 分解计算公式 求解 求解（1） 求 （2） 求 （2） 求解 的递推公式 （3） 求解 的递推公式 将计算 及 的过程称为追的过程，计算方程组解 过程称为赶的过程，追赶法解 ，仅需要5n－4次乘除运算。 例5  用追赶法解方程组 解  （1）计算 （2）计算 （3）求解计算 . §6  解对称正定矩阵方程组的平方根法 在工程技术问题中，例如用有限元方法解结构力学中问题时，常常需要求解具有对称正定矩阵方程组，对于这种具有特殊性质系数矩阵，利用矩阵的三角分解法求解就得到解对称正定矩阵方程组的平方根法，平方根是解对称正定矩阵方程组的有效方法，目前在计算机上被广泛应用。 设有方程组 （6.1） 其中，A ，若A满足下述条件，称A为对称正定矩阵。 （1） A对称，即 （2） 对任意非零向量 ，则有 。且对称正定矩阵A具有性质： a) 设A为对称正定阵，则A的顺序主子式都大于零，即 b) A的特征值 。 由设A为对称正定矩阵，则A有三角分解 （6.2） 其中 ， 由设 ，于是 ， 为单位下三角阵， 为上三角阵，由矩阵三角分解的唯一性，则 ，从而对称正定矩阵A有唯一分解式 （6.3） 由（6.2）式可知 ， 又因为 ，故 。于是，对角阵D还可以分解 为 代入（6.3）式，则有 其中 为下三角阵。 定理5  （对称正定阵的三角分解） 设A为n阶对称正定矩阵，则有三角分解（且唯一）： （1） ，其中L为单位下三角阵，D为对角阵，或 （2） ，其中，L为下三角阵且当限定L的对角元素为正时，这种分解是唯一的，这种矩阵分解称为乔来斯金（Cholesky）分解。 下面推导实现分解计算 的递推公式，及求解公式。 设有 ，其中 为对称正定矩阵，于是有三角分解 其中 。 由矩阵乘法，则有L的第1列元素 ， ， 同理，可确定L的第j列元素 。 由此求得解对称正定矩阵方程组的平方根法计算公式。 （一） 分解计算 （1） ， ； （2）对于 （二）求解计算 （3） 求解 （4） 求解 注  平方根法仅需要计算L与D，因此平方根法的计算量约为 次乘除法运算，大约为一般高斯消去法计算量的一半。 由分解公式有 （6.4） （6.4）式说明解 的平方根法所得的中间数据 是有界的，即 数量级不会增长。因此，虽然解对称正定矩阵方程组的平方根法没有进行选主元素，但平方根法是数值稳定的。 因为A为对称正定矩阵，因此，电算时只需要用一维数组存贮A的对角线以下元素，即 用一维数组按行存贮： 且矩阵A的元素 在一维数组中表示为： 计算得到L元素存放在A的对应位置。 例6  用平方根法解方程组 解  精确解 （1） 分解计算 （2） 求解两个三角形方程组，求解 ， 得到 求解 ，即得 的解 . §7  向量和矩阵的范数\ 为了对方程组的计算解进行误差分析，为了讨论迭代法的收敛性，需要对 （n维列向量空间）中向量及 中矩阵引进某种度量，即引进向量或矩阵的范数概念。 中向量范数是 中向量长度概念的推广。 定义1  （向量范数）如果向量 的某个实值函数 满足条件 （1） 正定条件： 且 向量。 （2） 齐次性： ， 为实数。 （3） 三角不等式： ，对任意向量 。 称 是 上的一个向量范数（或向量的模）。 （4） 利用三角不等式可推得（见图7-1）        图7-1 定义2    设 ，定义 上三种常用的向量范数 （1）向量的“1”范数          （2）向量的“ ”范数        （3）向量的“2”范数          容易验证，上述定义的向量 函数 （ 满足定义1的3个条件，因此， 是 上向量的范数。 例7  设 计算 ， ， 解    ＝ 定义3  （向量序列的极限） 设 为向量序列，记 及 。如果n个数列极限存在且 则称 收敛于 ，且记为 。 定理6  设 是 中一向量序列，且 ，则 是 （当 ） 证    只就 证明。 显然有： （当 时） 定义 4  （矩阵的范数） 如果矩阵 的某个非负实值函数 满足上述条件 （1） 正定性：  ，且 矩阵。 （2） 齐次性：  ， 为实数； （3） 三角不等式：  ，对任意矩阵 ； （4） ，称 是 上一个矩阵范数（或称为模）。 大多数应用问题，矩阵和向量是有关系的，下面借助于向量范数来定义矩阵范数。 定义5  （矩阵的算子范数） 设 ， ，且给出一种向量范数 ，相应的定义一个矩阵的非负函数 。即 （最大比值）            （7.1） 显然，由（7.1）式对任意 ， 有 （7.2） 且容易验证 满足矩阵范数条件（1）—（4），所以 是 上矩阵的范数，下面验证条件（3）成立。事实上，利用向量范数的三角不等式及（7.2）有 设 ，故有 ， 于是        下面给出 时向量范数，来推导矩阵算子范数 计算公式。 定理7  （矩阵范数计算公式） 设 ， ，则 （1） 对应 （称为A的列范数）； （2） 对应 （称为A的行范数）。 证  只证（2），同理可证（1）。 设 且设 ，引进记号 ， 于是 即对任何非零向量 ， 下面说明存在 ，使比值 。 事实上，选取向量 为 且有 ， 第 个分量为 故    即      例8  设 计算 ， 解    ， §8  解线性方程组的迭代法 前面我们介绍了解线性方程组的直接法（例如选主元的高斯消去法等），但是对于工程技术中产生的大型稀疏矩阵方程组，则利用迭代法求解是合适的，迭代法在计算机内存和运算两方面通常都是可利用A中有大量零元素的特点。 设有方程组 ，其中A为非奇异阵。解方程组的迭代法，首先需要将 转化为一个等价方程组 （8.1） 任取初始值 按下述逐次代入方法构造向量序列 ： （8.2） 其中B与 无关，称此迭代法为一阶定常迭代法，如果 ，则称此迭代法收敛且 为（8.1）解。事实上，在（8.2）式两边取极限即知。 例9  设有方程组 或简记 解  精确解 首先将 转化为等价方程组 或写为 迭代公式：初始向量 计算结果如下表： 表7-2 0.6000 1.0473 0.9326 0.0 2.2727 1.7159 2.0533 0.0 -1.100 -0.8052 -1.0493 0.0 1.8750 0.8852 1.1309           1.0152 0.9890 1.0032 0.9981 1.9637 2.0114 1.9922 2.0023 -0.9681 -1.0103 -0.9945 -1.0020 0.9739 1.0214 0.9944 1.0036           且有误差 从此例可看出，由迭代法产生的向量序列 逐次逼近方程组的精确解，但是，并不是对任何一个方程组（8.1），由迭代法产生的向量序列 都收敛。 设有方程组 ，   或               （8.3） 其中A为非奇异矩阵，且 将A写为： （8.4） 现将A分裂为 ，于是方程组（8.3）等价于方程组 （8.5） 其中M为可选择的一个非奇异矩阵，应选择M使 容易求解。 对应于方程（8.5）可构造一个迭代过程： （8.6） 8.1  雅可比迭代法 选取M＝D，于是N＝M－A＝（L＋U），方程（8.3）转化为等价方程组 于是得到雅可比迭代公式： （8.7） J称为Jacobi迭代法的迭代矩阵。 Jacobi迭代公式的分量形式： 引进记号： 为第 次近似，由（8.7）式可写为 或 （8.8） Jacobi迭代法公式简单，由公式（8.7）或（8.8）可知，每迭代一次只需要计算一次矩阵与向量的乘法，例9的迭代法就是解 的Jacobi迭代法。电算时Jacobi方法需要两组工作单元用来保存 及 且可用 来控制迭代终止。由迭代法计算公式可知，迭代法一个重要特点是计算过程中原来矩阵A数据始终不变。 8.2  高斯—塞德尔迭代法 在（8.5）式中选取M＝D－L（下三角矩阵），于是N＝M－A＝U。 方程（8.3）转化为等价方程组 于是得到高斯—塞德尔（G—S）迭代公式： （8.9） G称为G—S迭代法的迭代矩阵。 G—S迭代法的分量形式： 记 ，公式（8.9）可写成 或 （8.10） G－S迭代法每迭代一次只需计算一次矩阵与向量的乘法。但G－S迭代法比Jacobi迭代法有一个明显的优点，就是电算时仅需一组工作单元用来保存 分量（或 分量）。当计算出 就冲掉旧分量 。从G－S迭代公式（8.10）可看出在 的一步迭代中，计算分量 时利用了已经计算出的最新分量 。因此G－S迭代法可看作是Jacobi迭代法的一种修正。 例10  用G—S迭代法解例9方程组。 解  G－S迭代公式（结果如下表） 表 7-3 0.0 0.6000 1.030 1.0065 1.0009 1.0001 0.0 2.3272 2.037 2.0036 2.0003 2.0000 0.0 -0.9873 -1.014 -1.0025 -1.0003 -1.0000 0.0 0.8789 0.9844 0.9983 0.9999 1.0000               且  从此例看出，G－S迭代比Jacobi迭代法收敛快（初始向量相同，达到同样精度，所需要迭代次数少）。但这个结论对 的矩阵A满足某些条件时才是对的，甚至有这样的方程组，用Jacobi方法是收敛的，而用G－S迭代发却是发散的。 8.3  解线性方程组的超松弛迭代法 逐次超松弛迭代（Successive Over － Relaxation），简称 SOR方法是G－S迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一，它有着广泛的应用。 设有方程组  ， ，且 ，A为非奇异矩阵。分裂A为A＝D－L－U。 设已知第k次近似 及第 次近似的分量 ，首先用G－S迭代法计算一个辅助量 ： （8.11） 再由 的第 个分量 与 加权平均，定义 ： （8.12a） 将（8.11）代入（8.12 ），得到解 的SOR方法： （8.13a） 或写成 在SOR方法（8.11）中取 ＝1，则SOR方法就是G－S迭代法，当松弛因子 满足 时，迭代法（8.13a）称为低松弛方法。当 时迭代法（8.13a）称为超松弛方法。 SOR方法每迭代一次主要计算量时计算一次矩阵乘向量。电算时可用 来控制迭代，且这时SOR方法只需一组工作单元 存放 或 。也可用剩余向量 来控制迭代终止。 例11  用SOR方法解方程组 解  精确解 取初始向量 ，SOR迭代公式： （1）松弛因子 ＝1.3计算结果为： 且 迭代次数 。 （2）当取 ＝1.0时，初始向量相同，达到同样精度，所需迭代次数 。 （3）当取 ＝1.7时，初始向量相同，达到同样精度，则需迭代次数 。 对于此例，最佳松弛因子是 ＝1.3，即达到同样精度 ，所需要迭代次数最少。由此可知，利用SOR方法解线性方程时，松弛因子选择得较好，常常会使SOR迭代收敛大大加速。我们指出，解 ，SOR方法收敛的必要条件是： 。 8.4  迭代法的收敛性 由上面讨论可知，解 的Jacobi迭代法，G－S迭代法，SOR迭代法，都是一阶定常迭代法。下面讨论其收敛条件。 定理8  如果 ，则 为非奇异阵，且有估计 ,（ 是矩阵的算子范数）. 证  反证法，如果 ，则齐次方程组 有非零解 ，即 ，于是有 故  ，此与假设矛盾。 由 知  ，于是 所以  定理9  （迭代法收敛的充分条件） 设有方程组 为由迭代法 （ 为任意选取初始向量）产生的向量序列。 如果迭代矩阵 有某一种范数 ，则 （1） 收敛于方程组 唯一解 ； （2） ； （3）有误差估计 。 证  由定理8可知方程组 有唯一解 ，即 满足方程组 (8.12b) 引进误差向量： 于是由迭代公式减去(8.12b),即得误差 的递推公式 （8.13b） 反复利用递推公式(8.13),即得 （8.14b） 于是   （当 时），（ ） 证（2），显然，由迭代公式及(8.13b)有 （*） 及    于是  即      反复利用（*）式，即得(3)。 下面再介绍几个常用的判别方法。 定义6  （严格对角占优阵）设 ，如果 满足条件 ，    即 的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称 为严格对角占优阵。 定理10  如果 为严格对角占优阵，则 为非奇异矩阵。 证  用反证法。若 ，则 有非零解，记为 。且记 ，于是由 的第t个方程              得到 即                与假设矛盾。 定理11  设 。 如果 为严格对角占优阵，则解 的Jacobi方法，G－S迭代法都收敛且G－S迭代法收敛比Jacobi方法为快。 证  略。 定理12 （1）设 其中A为对称正定阵； （2） ； 则解 的SOR方法收敛。 例12  试考察用Jacobi方法，G－S迭代法解下面方程组的收敛性 解   由于 为严格对角占优阵，于是由定理11可知解 的Jacobi迭代法，G－S迭代法均收敛。 §9  病态方程组和迭代改善法 9.1 病态方程组 考虑线性方程组                               （9.1） 假设 为非奇异矩阵， 为方程组的解。在应用问题归结为求解方程组Ax＝b时，其系数矩阵A和b可能有某些观测误差，或者A，b是计算的结果，从而包含有舍入误差。下面我们研究数据A或b的误差对方程组解x的影响。 例13  设有方程组 其解 ，现考虑常数项有微小的误差，即 ，其中 ，得到一个扰动方程组 其解为            此例说明，方程组常数项分量只有微小变化（1/100），而方程组的解有较大的变化。也就是说这个方程组的解对于问题的数据b很灵敏。这样的方程组就是病态方程组。 下面我们找出能用来刻画方程组病态性质的量。首先考查常数项b的微小误差对解的影响。设A是精确的，b有误差（或扰动） ，显然，方程组 的解与x有差别记为 ，即有  即      ，（由设Ax＝b≠0） 于是                                （9.2） 另一方面，由Ax＝b≠0，则有 或                                            （9.3） 由（9.2）式及（9.3）即得： 定理13 （b扰动对解的影响） （1）Ax＝b≠0，x为精确解，A为非奇异矩阵； （2）且设 则有 （9.4） （9.4）说明，当b有一相对误差时，引起Ax＝b解的变化。（9.4）给出了引起解相对误差的一个上界，且引起的解的相对误差可能是常数项相对误差的‖ ‖‖ ‖倍。因此，引起的解的相对误差的大小与数‖ ‖‖ ‖大小有关。 下面考查A扰动对Ax＝b解x的影响。 设A有微小误差（扰动） ，即 ，b是精确的，记 的解为 ，即 由于 ，上式即                （9.5） 设‖ ‖‖ ‖ ,则由定理8， 为非奇异阵且有 ‖ ‖≤               （9.6） 由（9.5） 利用（9.6），则 （9.7） 定理14  （A扰动对解的影响） （1） 设 ，其中A为非奇异矩阵，x为精确解； （2） 设 ，且设 则A的微小误差引起解的相对误差有估计式（9.7），且（9.7）说明，如果 ‖ ‖‖ ‖数愈大，A的微小相对误差可能引起解的相对误差就愈大，因而 ‖ ‖‖ ‖数的大小刻画了方程组的解对问题数据A（或b）的灵敏程度。 定义1 （矩阵的条件数）设A为非奇异矩阵，称 Cond ＝‖ ‖ ‖ ‖ 为矩阵A的条件数（其中 取 或1或2）。 定义2 （病态方程组）设 ，其中A为非奇异矩阵，如果Cond （相对大的条件数），则称 为病态方程组，如果Cond（A）相对的小，称 为良态方程组。A的条件数愈大，方程组病态愈严重。 注：（1）方程组的病态性质是方程组本身的特征。对于病态的方程组用一般的计算方法不容易求得较精确的解。且方程组病态愈严重，求解愈困难。 （2）对任何非奇异矩阵A，都有 Cond ＝‖ ‖ ‖ ‖ ≥‖ ‖ ＝‖I‖ ＝1 9.2  迭代改善法 设有方程组 ，其中 为非奇异阵，且若方程组不过分病态，又设用高斯消去法（或部分选主元消去法）求得计算解 （精度不高），我们希望获得方程组高精度的解，一般可采用下述的迭代改善法，用来改善 的精度。 设 为用高斯法求得的计算解，计算剩余向量 （9.8） 求解                                            （9.9） 且计算                                      （9.10） 显然，如果计算 及 没有误差，则 是方程组 的精确解。 但实际计算时，由于有舍入误差，因此我们得到 是一个近似解（要求用双精度计算 ）。 对 重复上述过程（9.8）－（9.10），就求得 及 ， ，即可求得方程组的一个近似解序列 。当 不是过分病态时，通常 很快收敛到方程组的解 。 例14  用迭代改善法解 解  方程组精确解 ＝ 且有 ， 于是  因此，方程组为病态方程组。 （1）用高斯消去法解 （用具有舍入的4为浮点数进行计算）且实现 分解，即  （2） 计算 。 求解 ，或求解 （3） 计算 。 求解      （4） 计算 。 求解      习题七 1、分别用高斯消去法，列主元素消去法解下述方程组： （用具有舍入的4位浮点数进行运算）并比较计算结果. 2、设A为对称矩阵，且 ，经高斯消去法第一步A约化为 试证明 （1） 亦是对称阵； （2）若A为对称正定，则 亦是对称正定。 3、设 其中U为上三角阵或下三角阵，试计算解 乘除法次数。 4、用平方根法解方程组 5、用追赶法解方程组 6、画出用追赶法解三对角阵方程组的框图。 7、设 ， 试计算 ， ， ， ， ， 。 8、求证 9、证明单位矩阵的算子范数 10、设有方程组 （a） 用Jacobi方法迭代3次； （b） 用G—S迭代法迭代3次，并检查两个方法的收敛性（真解为 取 ）。 11、画出用G－S迭代法解 的框图。 12、用SOR方法（分别取 ＝1.0， ＝0.9， ＝1.1）解方程组 （要求当 时迭代终止）。