tjm08第7章解线性方程组的迭代法(全).pptVIP

数值计算方法B 第7章 解线性方程组的迭代法 7．1解线性方程组的误差分析 7．1．1向量和矩阵的范数 7．2雅可比迭代法与高斯－塞德尔迭代法 7．2．1雅可比迭代法 7．2．2高斯－塞德尔迭代法 7．2．3迭代法的收敛条件及误差估计 5、若A、B同阶，则有 向量和矩阵序列的收敛性 例：讨论 的幂序列的收敛性。 另外，易知A的两个特征值 一、构造方法（以3阶方程组Ax=y为例） 令 由此构造迭代格式： 例：用Jacobi迭代法解下面的线性方程组 取初始向量 （第1步） 计算 X(1) = BjX(0) +f （第2步） 计算 X(2) = BjX(1) +f …………………………… （k+1步） 计算 X(k+1) = BjX(k) +f 当||X(k+1)-X(k)||∞ ? 时，停止计算。 1、 对Jacobi迭代法的改进 为加速迭代，不妨取 Gauss-Seidel迭代法的算法参见P160。 这种迭代法称为高斯—赛德尔迭代法。 3、高斯—赛德尔迭代法的矩阵变换 例：用高斯-赛德尔迭代法求解下面的方程组 ，另外 任取初始向量x(0)=(0, 0, 0)T , 计算 x(1)=(2.5, 2.090909, 1.227272)T , …, x(5)=(2.99984, 2.000072, 1.000061)T 已知准确解向量 x*=(3, 2, 1 )T ，则 注意：迭代矩阵B的范数小于1只是收敛的充分条件，当迭代矩阵B的某范数||B||r≥1时，并不能确定B是收敛还是发散，如下面的矩阵： II）A为按列严格对角占优阵，即： 证明I）： 设Jacobi迭代矩阵为B=(bij)n×n， 其中bij=-aij/aii，i≠j；bii=0。 则矩阵B的行范数为： 二、 Gauss-Seidel迭代法的收敛条件 代替 ，即 （3）计算 时， 已在(2)中求出 为加速迭代，不妨取 代替 ，即 即 一般地，对 n 阶线性方程组，当计算 时， 以 、 、 、 取代Jacobi迭代计 算式中的 、 、 、 ，以加速迭代。 即： 高斯—赛德尔迭代法相当于如下矩阵变换： A=D-L-U AX=y ? (D-L-U)X=y ? (D-L)X-UX=y ? (D-L)X=UX+y ? (D-L)-1(D-L)X=(D-L)-1UX+ (D-L)-1y ? X=(D-L)-1UX+ (D-L)-1y 令：S = (D-L)-1U ，f = (D-L)-1y ，则有 X=BgX+f ? X(k+1)=BgX(k) +f Bg—— 高斯-赛德尔迭代矩阵。 解：先写出 D-L、U 矩阵： 下面再求出Gauss-Seidel迭代矩阵S和f ： 迭代次数为5，即已满足精度要求。可以验证采用Jacobi迭代法须迭代10次。 一、Jacobi迭代法的收敛条件 1）定理 对任何初始向量X(0) 和常数项f，由迭代格式 X(k+1) =BX(k) +f （k=0,1,2,…）生成的向量序列{X(k)}收敛的充分必要条件是： 7．2．3迭代法的收敛条件及误差估计 2）推论：因矩阵任意范数||B||p? ?(B)，当矩阵的某范数||B||1、||B||2、||B||∞小于1时，B收敛。 行、列范数：||B||∞=1.0、||B||1=1.1 而其特征值?1=0.9、?2=0.8 故?(B)=|?1|=0.91，B应为收敛。 3）若线性方程组AX=y的系数矩阵A满足下列条件之一，则Jacobi迭代收敛： I）A为按行严格对角占优阵，即： 故Jacobi迭代收敛。 例如下面的线性方程组： |a11|=52+1=3；|a22|=4|-1|+2=3； |a33|=102+|-3|=5 系数矩阵为行对角优阵，故Jacobi迭代收敛。 （1）收敛的充分必要条件，对迭代矩阵S 有 （2）收敛的充分条件：迭代矩阵S的某范数1 （3）若方程组AX=y的系数矩阵A为按行或列对角占优矩阵则Gauss-Seidel迭代一定收敛。 （4）若方程组AX=y的系数矩阵A为正定阵则Gauss-Seidel迭代一定收敛 注意：若Jacobi迭代和Gauss-Seidel迭代都收敛，则后者一般比前者收敛更快（但并非一定如此）；前者收敛，后者不一定收敛。 * tjm * tjm 7．1解线性方程组的误差分析 一、向量和矩阵的范数及矩阵的谱半径 向量长度的概念： （1）平面向量（二维向量）： 其长度即从原点到点(x,y)之间的距离： （2）空间向量（三维向量）： （3）n维空间向量： 其长度即从原点到点(x,y,z)之间的距离： 其长度即从原点到