1、第四章解线性代数方程组的迭代法 4.1向量和矩阵序列的极限 4.3几种常用的迭代法4.2迭代法的基本理论2022/6/2614.向量和矩阵序列的极限一.极限的概念Remark：上面的收敛性实际上和范数的选择无关。（范数的等价性） 1.向量序列收敛 则称 收敛于 。记为：设是中的向量序列，若有向量，使定义：2022/6/262 设 是 中的矩阵序列， 若有 ，使 ，则称 收敛于 ，记为 .矩阵序列收敛Remark：上面的收敛性也和范数的选择无关。定义：2022/6/263二.序列收敛的等价条件 设 ， 则 的充要条件是：1.向量序列收敛的等价定理2022/6/264证明：充分性 由范数的等价性，
2、即序列收敛的等价条件（续）2022/6/265必要性由等价性知：有即即序列收敛的等价条件（续）证毕2022/6/2662.矩阵序列收敛的等价定理即故 由矩阵范数的等价性，有即证明：充分性，则 ， 设 ， 则 的充要条件 是序列收敛的等价条件（续）2022/6/267即也即故 .向量序列、矩阵序列的收敛性等价于按分量、按元 素的收敛性。 .对向量序列和矩阵序列，按范数或者按分量元素收敛，都可以转化为数列的收敛。必要性： 由矩阵范数的等价性，有即 ,序列收敛的等价条件（续）Remark证毕2022/6/268序列收敛的等价条件（续）定理 的充要条件是证明 必要性是显然的,现证充分性。取为第i个单位
3、坐标向量,则，这意味的第i列元素的极限为零,取,则充分性得证.2022/6/269三.引理 证明：任何矩阵B总相似于它的Jordan标准型，即存 在可逆阵P，使 其中设 ，则 的充要条件是 ，其中 叫做矩阵B的谱半径。称为Jordan块。 为B的特征值 的重数， .2022/6/2610由归纳法可证显然 由，则续2022/6/2611 即从而 其中 ， 时，不难看出 的充要条件为故续证毕2022/6/26124.迭代法的基本理论迭代法的一般格式为若，即，称为单步迭代法。若为线性的，即，称为单步线性迭代法，称为迭代矩阵。若，与k无关，即,k=0,1,，称为单步定常线性迭代法，或者叫简单迭代法。本
4、章主要讨论简单迭代。因为计算 一般要用到前面多步的值故称为多步迭代法。2022/6/2613一.简单迭代法的构造将该方程组等价变形为构造简单迭代格式，。若收敛于确定的向量，则就是方程组的解。此时称简单迭代法，关于初始向量收敛。设要求解的线性方程组为 ，其中 为非奇异矩阵， 为向量。2022/6/2614变形为的方式不唯一。当收敛时，只要充分大，则可用作为的近似值。同一个简单迭代法可以关于某一个收敛，而关于另外不收敛。 如果对初始向量 ， ，则称此简单迭对任意，均有.代法关于初始向量收敛。一般谈及收敛，是指简单迭代法的构造（续）2022/6/2615二.简单迭代法的收敛性和收敛速度a.b.迭代矩
5、阵的谱半径1.收敛的充要条件 定理1.简单迭代法 ， ，对 任意初始向量 都收敛的充要条件是：简单迭代法为.故设 有唯一解 ，2022/6/2616作为 ，证明： 必要性：用 表示 的（i,j）元素，简单迭代对 任意初始向量 有 .设 不趋 于零，则必有位置（p,q）使 不趋于零。取第q个单位向量 a.充分性： ，则由知对于任意初始向量，。收敛的充要条件（续）2022/6/2617 即向量 的第q个元素不趋于零，从而 与 矛盾。则有：收敛的充要条件（续）b.由上节引理可以直接证明。证毕2022/6/2618 是判定收敛的根本法则。 时，有可能存在某个初始向量 使简 单迭代法收敛。收敛的充要条件
6、（续）Remark2022/6/2619 2.收敛的充分条件引理：由矩阵范数的定义，有即对任意矩阵，有特征向量，则 。证明：事实上，设为B的任一特征值， 为相应于 的从而有显然有向量，使得 为非零矩阵。用 右乘上式，可得证毕2022/6/2620b.c.a.简单迭代格式关于任意初始向量 收敛. 定理2.设方程组 有唯一解 ，其简单迭数要求与用到的向量范数相容），则代法为，若（用到的矩阵范收敛的充分条件（续）2022/6/2621b.由，相减，得： 故 故又由，相减得：证明：敛基本定理，简单迭代格式对任意收敛。a.由 且 ，故 ，由迭代收收敛的充分条件（续）2022/6/2622从而由从而有由即
7、收敛的充分条件（续）2022/6/2623.c.由及即收敛的充分条件（续）证毕2022/6/2624 3.收敛速度由定理2可见，若 且 越小，则 收敛到解的速度越快。实际上，可以确切地说，谱半径 相对于1来说越小，则 的收敛速度越快。由 和 还可得到若要求迭代k次后所产生的误差缩小为初始误差的10m倍，即则只需2022/6/2625收敛速度（续）可以证明， ，则存在从属于矩阵范数 ，使 。因而上面的条件可以近似代替为故为了达到所提出的精度，上式给出了大约所需要的迭代次数。当误差压缩量10m确定后，这个次数主要由分母所刻划的。越大，则迭代次数越少，收敛越快。一般将定义为简单迭代法的收敛速度。20
8、22/6/2626三.高斯塞德尔（Gauss-Seidel）迭代将B分解为设有简单迭代法,k=0,1,则将其修改为k=0,1,i=1,2,n上式称为由简单迭代法导出的Gauss-Seidel迭代法。它的分量形式为2022/6/2627Gauss-Seidel迭代收敛的充要条件为1.迭代收敛的充要条件与简单迭代法相应的Gauss-Seidel迭代可化为2.迭代收敛的充分条件若 或 ，则Gauss-Seidel迭代 关于任意的初始向量 收敛。若 ，则对于任意初始向量 ,Gauss-Seidel迭代收敛。 2022/6/2628的分量形式相减有记证明： 由k=0,1,迭代收敛的充分条件（续）仅以 为
9、例。2022/6/2629有上式对i=1,2,n都成立，故有使有即注意： 即迭代收敛的充分条件（续）所以。记2022/6/2630故当k 时，则故由序列收敛的等价性定理，知即对任意的 都成立。迭代收敛的充分条件（续）Remark：当 或 时，简单迭代法与相应的Gauss-Seidel迭代法同时关于任意初始向量收敛。证毕其中显然，c 1，从而有2022/6/26314.3几种常用的迭代法一.Jacobi迭代法1.迭代格式设有n阶方程组其中系数矩阵非奇异，且 ，i=1,2，n将上式变形为2022/6/2632Jacobi迭代法的迭代格式（续）建立迭代格式上面的迭代式称为雅可比（Jacobi）迭代格
10、式。用矩阵形式来表示方程组的迭代法 设det(A)，且2022/6/2633Jacobi迭代法的迭代格式（续）雅可比迭代式成为：则令则得记A=D+L+U 2022/6/2634a.充要条件：Jacobi方法关于任意初始向量 都收敛 的充要条件是 。2.收敛条件b.充分条件：（II）设系数矩阵严格对角占优，则Jacobi迭代法关于任意初始向量 收敛。（I）若 则Jacobi方法关于任意初始向量 都 收敛。即（按行）,（i=1,2,n）2022/6/2635由严格对角占优矩阵的定义有（按行） i=1,2,n 即证明：因此Jacobi迭代法对任意初始向量收敛。定义：设，若 （i=1,2,n）且其中至
11、少有一个严格不等式成立，则称A为按行弱对角占优。Jacobi迭代法的收敛条件（续）证毕2022/6/2636则称A为可约矩阵。以n阶单位矩阵In的n个列向量 为列构成n阶矩阵 称为置换矩阵. 是1，2，,n的一个排列。若可找到置换矩阵P，使A呈换化为 ，其中 是方阵，则称A为不可约矩阵。定义：设，若A不能经过行置换与相应的列置（III）设A为弱对角占优矩阵且不可约矩阵，则Jacobi迭代法关于任意初始向量收敛。Jacobi迭代法的收敛条件（续）2022/6/2637二.与Jacobi迭代法相应的Gauss-Seidel法1.迭代格式其迭代式为矩阵形式为2022/6/2638因 ,故 存在，于是
12、Gauss-Seidel 迭代式为称为Gauss-Seidel迭代法的迭代矩阵。则得令迭代格式（续）Remark1:今后若无特殊说明，凡谈到Gauss-Seidel迭代法（简称G-S迭代法），均指与Jacobi迭代法相应的Gauss-Seidel迭代法。Remark2:并不是任何时候Gauss-Seidel迭代法都比Jacobi迭代法收敛快。甚至也有Jacobi法收敛而Gauss-Seidel迭代法不收敛的例子。2022/6/26392.收条件a.充要条件：收的充要条件是：G-S法关于任意初始向量都b.充分条件：关于任意初始向量收。系数矩格角占，G-S方法A不可弱角占矩，G-S迭代法关于任意初
13、始向量收。A称正定矩，G-S迭代法关于任意初始向量收。若，G-S方法关于任意初始向量都收。2022/6/2640三.逐次超松弛迭代法（SOR法-SuccessiveOverRelaxation）1.迭代公式 将G-S迭代格式改写为：并记一般地，残量 。 2022/6/2641矩阵形式:将迭代格式改写由矩阵分解成ADLU这就是逐次超松驰迭代法（SOR方法)， 称为松驰因子。SOR方法的计算公式也常写为：逐次超松弛迭代法的迭代格式（续）Remark：可见，SOR方法的得到的可以看成是G-S方法的结果与的加权平均。2022/6/2642则相应的矩阵形式为故故SOR方法的矩阵形式为其中称为SOR方法的
14、迭代矩阵。即逐次超松弛迭代法的迭代格式（续）2022/6/26432.SOR方法的收敛性SOR方法收敛设 的特征值为即由 的特征多项式的模与系数的关系知：证：A.充要条件：SOR法关于任意初始向量 都收敛的充要条件是 。B.必要条件：设解 的SOR方法关于任意初始向量 都收敛，则02。2022/6/2644即 而即故02。SOR方法的收敛性（续）证毕2022/6/2645即在复空间 中考虑内积即设 为对应 的 的特征向量，即SOR方法的收敛性（续）C.充分条件：若A对称正定，且02，则SOR法关于任意初始向量 收敛（此时，02对称正定为充要条件）。证：2022/6/2646又记所以因为SOR方
15、法的收敛性（续）2022/6/2647当0 2时，则有即 ，故SOR方法收敛。SOR方法的收敛性（续）证毕2022/6/2648SOR方法的收敛性（续）Remark：能使SOR方法收敛最快的松弛因子叫做最佳松弛因子，记为opt。对某些特殊类型的矩阵，可以建立SOR方法最佳松弛因子理论。例如，对于具有对称正定，或严格对角占优或弱对角占优且不可约等性质的矩阵A的线性方程组，可以建立最佳松弛因子其中(J)为解Axb的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定opt并不容易，实际计算时一般都是根据试算的情况确定opt的一个近似值。2022/6/2649四.数值算例取 ，用迭代方法求解如下的方程组，使得 。求解2022/6/26504.如果 ,则用此判断法比用 方便。Remark：使用迭代法求解线代数方程组需注意的问题3.在迭代格式 中，若 是病态阵，那么一般迭代法得不到好的结果。1.迭代法的收敛性与初始向量的选取无关。但初始向量的选取对迭代的工作量有重大影响。2.在使用实用误差估计式 停止迭代时，要选的恰当。5.对某些方程组，有时可适当作些变形，以使得迭代法收敛。2022/6/2651
