第3章-线性代数方程组的解法课件

第三章第三章 线性代数方程组的解法线性代数方程组的解法引言引言高斯消去法高斯消去法高斯列主元消去法高斯列主元消去法矩阵分解法矩阵分解法向量和矩阵范数向量和矩阵范数解线性代数方程组的迭代法解线性代数方程组的迭代法 第一节 引言q 快速、高效地求解线性方程组是数值线性代数研究中快速、高效地求解线性方程组是数值线性代数研究中的的核心问题核心问题，也是目前科学计算中的，也是目前科学计算中的重大研究课题之一重大研究课题之一。q 各种各样的科学和工程问题，往往最终都要归结为求各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。解一个线性方程组。q 线性方程组的数值解法有：线性方程组的数值解法有：直接法直接法和和迭代法迭代法。直接法直接法：在假定没有舍入误差的情况下，经过有限次在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；运算可以求得方程组的精确解；(快速有效快速有效)迭代法迭代法：从一个初始向量出发，按照一定的迭代格从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列式，构造出一个趋向于真解的无穷序列(节省内存节省内存)。高斯消去法是解线性方程组最常用的方法之一，高斯消去法是解线性方程组最常用的方法之一，它的基本思想是通过它的基本思想是通过逐步消元逐步消元，把方程组化为系数矩，把方程组化为系数矩阵为阵为三角形矩阵三角形矩阵的同解方程组，然后用的同解方程组，然后用回代法回代法解此三解此三角形方程组可得方程组的解。角形方程组可得方程组的解。第二节 高斯消去法我们知道，下面有我们知道，下面有3 3种方程的解我们可以直接求出：种方程的解我们可以直接求出：上三角上三角下三角消元法消元法就是对方程组做些等价的变换，变为我们已知的就是对方程组做些等价的变换，变为我们已知的3种类型种类型之一，而后求根。之一，而后求根。对方程组，作如下的变换，解不变对方程组，作如下的变换，解不变交换两个方程的次序交换两个方程的次序一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0的数的数一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0数，加到另一个方程数，加到另一个方程因此，对应的对增广矩阵因此，对应的对增广矩阵(A,bA,b)，作如下的变换，解不变。，作如下的变换，解不变。交换矩阵的两行交换矩阵的两行某一行乘以一个非某一行乘以一个非0 0的数的数某一行乘以一个非某一行乘以一个非0 0数，加到另一行数，加到另一行举例（一）解：q 例：直接法解线性方程组例：直接法解线性方程组高斯消去法的主要思路：高斯消去法的主要思路：将系数矩阵将系数矩阵 A 经过经过消元过程消元过程化为上三角矩阵，然后化为上三角矩阵，然后回代回代求解。求解。考虑考虑 一般一般n 阶线性方程组：阶线性方程组：矩阵形式矩阵形式=即即:相当于第相当于第i i个方程个方程-第一个方程第一个方程数数新的第新的第i i方程方程同解！第一方程不动！同解！第一方程不动！一、一、Gauss Gauss 消去法计算过程消去法计算过程第一步消元：消元：消元：上述消元过程除第一个方程不变以外上述消元过程除第一个方程不变以外,第第22第第 n n 个方程全消去了变量个方程全消去了变量 1 1，而系数和常数项全得到新值：，而系数和常数项全得到新值：每步消元，先计算系数，然后计算矩阵新元素及右端项每步消元，先计算系数，然后计算矩阵新元素及右端项系数矩阵与常数项：讨论第讨论第K次消元，得到消元公式次消元，得到消元公式第第K次消元目的：次消元目的：aik(k)=0 (i=k+1.n),设设akk(k)0 ,为使为使aik(k)=0 (i=k+1.n）选取适当因子选取适当因子M使使 aik(k)-M akk(k)=0 可求可求出出 M=aik(k)/akk(k)第第i个方程其他系数的变化个方程其他系数的变化为为（Ri -M.Rk )aij(k+1)=aij(k)M.akj(k)(i=k+1.n,j=k+1.n+1)所以，第所以，第K次消元时（后）（次消元时（后）（K=1.n-1)消元因子：消元因子：M=aik(k)/akk(k)(i=k+1,n）系数变化：系数变化：aij(k+1)=aij(k)（i k)aij(k+1)=aij(k)-M.akj(k)(ik,j=k+1n+1)最后得到：A(n)|b(n)(n-1 次消元后）其增广矩阵为：回代：回代：Xn=ann+1(n)/ann(n)编程时，编程时，为节省内存为节省内存将将Xn放在放在a nn+1(n)同理同理X i 放在放在 a in+1(i)第第i次回代次回代公式公式（i=n-1.1)Xi(即即a in+1(i)=(a in+1(i)-）/aii(i)二、算法描述二、算法描述1、消元、消元 对对k=1.n-1 消元因子：消元因子：C=aik(k)/akk(k)(i=k+1.n）系数变化：系数变化：aij(k+1)=aij(k)（i k)aij(k+1)=aij(k)-C.akj(k)(i k ,j=k+1,n+1)2、回代、回代第第 i次回代公式次回代公式（i=n,n-1.1)Xi(即即a in+1(i)=(a in+1(i)-）/aii(i)三、特点三、特点1、优点：、优点：公式简明，容易程序化公式简明，容易程序化2、缺点：、缺点：第第k次消元时，次消元时，必须必须 a kk 0,且当且当 a kk 0 时时 ，误差很大，误差很大，数值不稳定数值不稳定(p35 N-S图）图）第三节第三节 GAUSS列主元消去法列主元消去法一、高斯消去法的缺点一、高斯消去法的缺点 在简单的高斯消去法中，如果遇到在简单的高斯消去法中，如果遇到 a（k）kk=0,则消去过程就会中断，如果则消去过程就会中断，如果a（k）kk 0，但其绝对值很小时，在高斯消去法中，因为但其绝对值很小时，在高斯消去法中，因为M=aik(k)/akk(k)，所以不是因为所以不是因为M数值过大，数值过大，就是舍入误差过大，与实际的解相差很远。就是舍入误差过大，与实际的解相差很远。零主元或小主元问题零主元或小主元问题例如：求解下列方程组例如：求解下列方程组 此方程组的准确解为：此方程组的准确解为：x1=10.00；x2=1.00下面采用高斯消去法解方程组（取四位有效数字），下面采用高斯消去法解方程组（取四位有效数字），消元后得消元后得-1043x2=-1044，则，则x2=1.001.将将x2代入第一个方程中，得代入第一个方程中，得 x1=-9.713显而易见，利用高斯消去法得到的结果与精确解相差太悬殊了显而易见，利用高斯消去法得到的结果与精确解相差太悬殊了从求解过程可以看出，在第一种解法中，乘以的系数为从求解过程可以看出，在第一种解法中，乘以的系数为m=5.291/0.0030如果将两个方程如果将两个方程互换，互换，再采用高斯消去法解方程组再采用高斯消去法解方程组消元后得消元后得59.14x2=59.14，则，则x2=1.000 将将x2代入第一个方程中，得代入第一个方程中，得 x1=10.000此时，利用高斯消去法得到的结果与精确解一致。此时，利用高斯消去法得到的结果与精确解一致。从求解过程可以看出，在第一种解法中，乘以的系数为从求解过程可以看出，在第一种解法中，乘以的系数为m=5.291/0.0030，第二种解法中，乘以的系数为，第二种解法中，乘以的系数为m=0.0030/5.291。我们希望。我们希望m尽量小，希望主元尽可能大，尽量小，希望主元尽可能大，就有了列主元消去法（按列）。就有了列主元消去法（按列）。二、列主元消去法二、列主元消去法 1、选主元再消元、选主元再消元 在每一步消元之前，即第在每一步消元之前，即第k次消元时次消元时，在第在第k列上列上选取绝对值最大选取绝对值最大的元素为主元素的元素为主元素 ai0k(最大最大值在值在i0行上）行上）若若|a i0k|p 则则 p|aik|i0i2、换行换行 a kj ai0j (j=kn)3、消元：消元：同同Gausss4、回代回代:同同Gausss （p175)取四位有效数字计算。解 中-18为主元,交换和得 例例1 用列主元素消去法解方程组用列主元素消去法解方程组 +12/18,+1/18得 第二列消元时,主元为1.167,交换方程和得 +1/1.167得 回代求得 x1=1.000,x2=2.000,x3=3.001方程组的实际解 x1=1,x2=2 ,x3=3四、四、高斯高斯约当消去法约当消去法 前面所述的消去法均要进行两个过程,即消元过程和回代过程。但对消元过程稍加改变可以把方程组化为对角形 此时求解就不要回代了。这种无回代过程的主元素消去法称为 高斯约当(Jordan)消去法。特别是方程组还可化为 显然等号右端即为方程组的解。对于n阶线性方程组,其增广矩阵为 首先把主元素(按列选主元或全选主元)调换到主对角线上,并化为1,再将主元素所在列的其它元素消为0练习：1、用GAUSS消去法解方程组 2x1+x2+x3=4 x1+3x2+2x3=6 x1+2x2 +2x3 =52、用GAUSS列主元消去法解方程组 2x1+x2+2x3=5 5x1-x2 +x3=8 x1-3x2 -4x3 =-43、用GAUSS列主元消去法解方程组 -3x1 +2x2+6x3=4 10 x1-7x2 =7 5x1 -x2 +5x3=6第四节第四节 矩阵分解法（直接法）矩阵分解法（直接法）复习、基本概念复习、基本概念1、顺序主子式（、顺序主子式（P40定义定义1）n*n 阶矩阵阶矩阵 A的左上角的左上角 P*P 阶子矩阵的行列式阶子矩阵的行列式 P=称为称为A的的P阶顺序主子式阶顺序主子式2、正定矩阵、正定矩阵特征值都大于特征值都大于0(或各阶顺序主子式都大于或各阶顺序主子式都大于0)的实矩阵的实矩阵(如何求特征值？）如何求特征值？）解特征多项式解特征多项式|E-A|=03.矩阵相乘公式矩阵相乘公式C mn=A mkB kn A的第的第 i行行 (ai1 ai2.aik)B的第的第j列列 （b1j b2jbkj)cij=(ai1b1j +ai2b2j+.aikbkj)=思考思考:下面矩阵左乘的结果下面矩阵左乘的结果?设设 li1=ai1(1)/a11(1)=结果为:M=-为第为第2次消元后的结果次消元后的结果?2第四节第四节 矩阵分解法（直接法）矩阵分解法（直接法）一、三角分解法一、三角分解法 从从矩矩阵阵的的初初等等变变换换来来看看,前前面面讲讲的的高高斯斯消消去去法法和和列列主主元元消消去去法法来来解解方方程程，实实际际是是通通过过一一系系列列的的初初等等变变换换将将方方程程组组的的系系数数矩矩阵阵A化化为为三三角角矩矩阵阵，其其每每一一步步的的消消元元过过程程相相当当于于对对增增广广矩矩阵阵(A,b)作作一一次次初初等等变变换换。下下面面将将上上述述这这种种方方程程组组的的消消去去过过程程通通过过矩矩阵阵分分解解来来实实现。现。在消去第一列中的在消去第一列中的ai1(i=2,3,n)时时,左乘的矩阵为左乘的矩阵为令：令：在消去第一列中的在消去第一列中的a ai1i1(i=2,3,n)(i=2,3,n)时时,左乘的矩阵为左乘的矩阵为2在消去第二列中的在消去第二列中的ai2(i=2,3,n)时时,左乘的矩阵为左乘的矩阵为这样就把这样就把A A化为一个上三角矩阵化为一个上三角矩阵U U，即，即根据得得A=LU 称为矩阵称为矩阵A的的LU分解或三角分解。分解或三角分解。把把A分解为一个单位下三角阵分解为一个单位下三角阵L和一个上三角阵的乘积，和一个上三角阵的乘积，称为称为A的的LU分解分解，也叫，也叫Doolittle（杜利特尔）分解。（杜利特尔）分解。一般的，如果能把系数矩阵分解为一般的，如果能把系数矩阵分解为A=LU，其中，其中L为为单位单位下三角阵下三角阵，U为为非奇异上三角阵非奇异上三角阵，那么方程，那么方程Ax=b可化为可化为 LUx=b 令令Ux=y，则有，则有Ly=b，这样原方程组转化为先解下三角，这样原方程组转化为先解下三角方程组方程组Ly=b，求出，求出y，再解上三角方程组，再解上三角方程组Ux=y求出求出x。即:a11 a12 .a1n 1 u11 u12.u1iu1n a21 a22a2n l21 1 u22.u2iu2n ar1 ar2 a rn lr1 lr2 1(lrr)uii .u in.an1 a n2 a nn l n1 l n2.1 unn =正正如如高高斯斯消消去去法法中中的的消消元元过过程程不不一一定定能能进进行行到到底那样，一个矩阵也不一定能进行底那样，一个矩阵也不一定能进行LU分解。分解。由下面讨论能进行由下面讨论能进行LU分解的条件。分解的条件。定理定理1：(p40)n x n阶矩阵有唯一阶矩阵有唯一LU分解的充分必要条件是分解的充分必要条件是 矩矩 阵阵A的各阶顺序主子式都不等于的各阶顺序主子式都不等于0。证明略。证明略。我们关心的是如何进行我们关心的是如何进行LU分解，即如何把分解，即如何把LU求求出来。设出来。设A的各阶顺序主子式都不等于的各阶顺序主子式都不等于0，并设，并设L=(lij),U=(uij)。由A=LU知：a11 a12 a1na21 a22 a2n ar1 ar2 arn an1 an2 annlr1 lr2 lr3U=先计算先计算U的第一行，的第一行，L的第一列元素，有矩阵乘法知的第一列元素，有矩阵乘法知 a1j=u1j(j=1,2,n)ai1=li1u11(i=2,3,n)得到得到 u1j=a1j(j=1,2,n)li1=ai1/u11(i=2,3,n)类似的由类似的由A的第二（的第二（r）行元素，计算）行元素，计算U的第二（的第二（r）行，由行，由A的第二（的第二（r）列元素计算）列元素计算L的第二（的第二（r）列）列元素。元素。一般的计算一般的计算U的第的第r行，行，L的第的第r列元素的方法设计考列元素的方法设计考虑虑A的第的第r行，第行，第r列元素，由矩阵乘法知：列元素，由矩阵乘法知：由由得到得到由由得到得到按公式将按公式将A进行进行LU分解后，此时分解后，此时 AX=b LUx=b 令令Ux=y，则，则Ly=b，方程组，方程组Ax=b化为下列两个等价的方化为下列两个等价的方程组程组 Ly=b Ux=y y1 b1 y2 =b2 .yn bn y1 =b1 l21y1+y2 =b2 li1y1+li2 y2+.Lii-1yi-1+y i =bi .ln1y1+ln2 y2+yn =bn可以计算 yi(下三角方程组)再带入 UX=Yx1 y1 x2 =y2 xn yn同理，可求：同理，可求：x n=y n/u n n注意计算顺序u11 u12 u13.u1nl21l31.ln1第一步计算u22 u23 u2nl32.ln2第二步计算.unn第n步计算L U计算的紧凑格式计算的紧凑格式例例3 用杜利特尔分解方法求解下列方程组的解用杜利特尔分解方法求解下列方程组的解：12 -121 -3 634 7/3 -8 解：利用上面3-19计算公式 可求得 再由再由Ly=b求出求出y后根据后根据Ux=y 最后求得原方程组的解为最后求得原方程组的解为 从从上上面面的的讨讨论论我我们们可可以以看看到到,用用LU分分解解方方法法解解线线性性方方程程组组,就就是是将将其其化化为为依依次次求求解解下下面面两两个个三三角角形形方程组方程组:Ly=b Ux=y 显显 然然 求求 解解 Ly=bLy=b的的 过过 程程 即即 为为 消消 元元 过过 程程,它它 只只 不不 过过 是是 对对 LUxLUx=b=b 两端左乘两端左乘L L-1-1而得而得,即即 UxUx=L=L-1-1 b=y b=y 而而求求解解UxUx=y=y的的过过程程即即为为回回代代过过程程。因因此此三三角角分分解解方方法实质上还是高斯消去法。法实质上还是高斯消去法。二、解对称正定的平方根法二、解对称正定的平方根法 在工程计算中，常遇到方程组的系数矩阵是在工程计算中，常遇到方程组的系数矩阵是对称正对称正定矩阵定矩阵，由于对称正定的性质，它的三角分解的形，由于对称正定的性质，它的三角分解的形式有着特殊性，因此，其计算量以及在计算机中的式有着特殊性，因此，其计算量以及在计算机中的存储量可大大减少。存储量可大大减少。二、解对称正定的平方根法二、解对称正定的平方根法定理定理2：若若 n阶方阵阶方阵A对称正定对称正定，则存在唯一的对角元，则存在唯一的对角元素为素为正正的的下三角下三角阵阵L，使，使A=LLT(Cholesky分解）分解）证明略证明略a11 a12 a1na21 a22 a2n ar1 ar2 arn an1 an2 ann由由a11=l211，得，得l11=考虑第一行元素，考虑第一行元素，a1j=l11lj1,j=2,3,n，得得lj1=a1j/l11这样就计算出这样就计算出L的第一列，的第一列，LT的第一行的第一行考虑第二列的下三角元素，考虑第二列的下三角元素，由由a22=l221+l222，得到，得到由由ai2=li1l21+li2l22,得到得到 li2=（ai2-li1l21）/l22,i=3,n这样就计算出这样就计算出L的第二列，的第二列，LT的第二行的第二行一般的一般的由上面的推导可求出按行计算公式:对对i=1,2,n将将A分解后，即分解后，即A=LLT，代入，代入 Ax=b，得，得 LLTx=b将其化为下列与原方程组等价的两个方程组将其化为下列与原方程组等价的两个方程组 Ly=b LTx=y然后回代，求出然后回代，求出y与与x。此时此时 AX=b LLTX=b 令令 LTX=Y 则则AX=b 等价于等价于 LY=b LTX=Y=由 LY=b得l11y1 =b1l21y1+l22y2 =b2.li1y1+li2y2+liiyi =biln1y1+li2y2+l nnyn =bn解之得:yi=(bi-)/l ii (i=1,.n)l11x1+l21x2+.l n1xn=y1 l22x2+.l n2xn=y2.liixi+l nixn=yi l nnxn =yn解之得：解之得：xi=(y i -)/l ii (i=n,.,1)再代入 LTX=Y例例 1：用平方根法求：用平方根法求 4x1+2x2 +4x3=4 2x1+10 x2+5x3=11 4x1+5x2 +21x3=-9 例例 1：用平方根法求：用平方根法求 4x1+2x2 +4x3=4 2x1+10 x2+5x3=11 4x1+5x2 +21x3=-9解解:系数矩阵系数矩阵:4 2 4 l11 l 11 l21 l31 2 10 5 =l21 l22 l 22 l32 4 5 21 l31 l32 l33 l 33 例例2 用用LLT分解方法解线性方程组分解方法解线性方程组 取四位小数计算。取四位小数计算。解用公式解用公式(326)依次计算依次计算由式由式(327)求得求得 y11.3416,y2-0.4474,y31.7320再由式再由式(327)求得原方程组的解为求得原方程组的解为 x10.9993,x20.9989,x30.9999实际上实际上,原方程组的准确解为原方程组的准确解为 x1=1,x2=1,x3=1例3：已知方程组 Ax=f,其中 2 -1 b 0 A=-1 2 a f=1 b -1 2 0试问参数a和b满足什么条件时 ，可选用平方根法求解该方程组。三、解三对角阵的追赶法三、解三对角阵的追赶法解三对角方程组的追赶解三对角方程组的追赶法（法（Thomas算法）算法）基本思想：基本思想：AX=F =若若A为对角占优为对角占优 即即|b1|c1|bi|ai|+|ci|i=2,.n-1 ai.ci 0|bn|an|则则A可以可以写成：写成：A=LU 即即 对比法求得对比法求得pi与与qi的递推公式：的递推公式：p1=a1 a1=p1*1q1=c1/p1 c1=p1*q1对于对于i=2,3,n 行计算行计算pi=ai-bi*qi-1 ai=bi*qi-1+piqi=ci/piAX=F 即 LUX=F 可写成由 LY=F知 =由矩阵乘法可求 将（3.29)代入可得 i=2,.n求出yi后再由 UX=Y 即 =同样根据矩阵乘法求 (3.32)i=n-1,.1 第五节第五节 向量和矩阵的范数向量和矩阵的范数在数值分析中，经常要分析解向量的误差，比较误在数值分析中，经常要分析解向量的误差，比较误差向量的差向量的“大小大小”，那么怎么定义向量的大小，那么怎么定义向量的大小，并进行比较呢？这可以对向量按一定的法则取一并进行比较呢？这可以对向量按一定的法则取一个非负实数，作为它的个非负实数，作为它的“长度长度”，然后以其长度，然后以其长度为标准进行比较，这就是数值方法中广泛应用的为标准进行比较，这就是数值方法中广泛应用的范数的概念。范数的概念。第五节第五节 向量和矩阵的范数向量和矩阵的范数一、向量的一、向量的范数范数定义定义1:若向量若向量xRn 即即x=(x1,x2.xn)T,定义某个实数值函定义某个实数值函数数 N(X)=|X|，若满足以下三个条件：若满足以下三个条件：(1)|X|0 当且仅当当且仅当X=0时，时，|X|=0 正定性正定性 (2)|C.X|=|C|.|X|C为任意常数为任意常数 齐次性齐次性 (3)|X+Y|X|+|Y|三角不等式三角不等式则称则称N(X)是是R 上的一个向量范数上的一个向量范数 或模。或模。2、常用的向量范数、常用的向量范数1-范数|X|1 =2-范数|X|2=()1/2 -范数|X|=max|xi|1=i=np-范数|X|p=()1/p例2 已知向量 X=（1,-2,3)T求|X|1，|X|2，|X|要求要求:会计算向量的范数会计算向量的范数3、向量范数的性质、向量范数的性质(1)设设 x,y Rn 则则|x|-|y|=|x-y|证：证：|x|=|(x-y)+y|=|x-y|+|y|所以所以|x|-|y|=|x-y|同理同理|y|-|x|=-|x-y|所以：所以：|x|-|y|=|x-y|（2）设设|x|与与|x|是是R n上任意两种向量范数，上任意两种向量范数，则存在正常数则存在正常数m和和M 使一切使一切 x Rn 有有 m|x|=|x|=M|x|如：如：|X|=|X|1 时时)x(k)x*=（x1(k)-x1*,x2(k)-x2*,xn(k)-xn*）T xi(k)-xi*xi(k)-xi*-0|x(k)x*|0 由范数的等价性知由范数的等价性知，存在，存在M，m 0 使得使得 m|x(k)x*|x(k)x*|M|x(k)x*|说明：说明：看向量看向量x(k)是否收敛于向量是否收敛于向量x*，就要看，就要看|x(k)x*|是否收敛于是否收敛于0。二、矩阵的范数二、矩阵的范数1、定义定义4 若矩阵若矩阵AR n n 的某个非负实值函数的某个非负实值函数N(A)=|A|满足满足 (1)|A|0 当且仅当当且仅当A=0时，时，|A|=0 正定性正定性 (2)|C.A|=|C|.|A|C为任意常数为任意常数 齐次性齐次性 (3)|A+B|A|+|B|三角不等式三角不等式 (4)|AB|A|B|相容性相容性 则称则称N(A)是是R n n 上的一个矩阵范上的一个矩阵范数数 或模。或模。在在数数值值计计算算中中,为为了了进进行行某某种种估估计计,常常常常要要比比较较不不同同向向量量的的范范数数,向向量量有有时时以以Ax的的形形式式出出现现,其其中中A为为nn阶矩阵阶矩阵 A=(aij)nn 这就需要寻求这就需要寻求x和和Ax之间的某种之间的某种关系关系定义定义5 设设XRn ，AR nn，且给出一种向量范数，且给出一种向量范数|X|，则称则称 为为矩阵矩阵A的算子范数的算子范数。说明说明:|AX|A|.|X|常用公式常用公式由向量范数诱导出的矩阵范数，即矩阵范数和向量范数的由向量范数诱导出的矩阵范数，即矩阵范数和向量范数的关系。关系。A的行范数|A|=max 1=i=n2、常用的矩阵范数、常用的矩阵范数A的列范数|A|1 =max 1=j=n A的2范数|A|2 =A的p范数|A|p =()1/2例3 已知 A=-1 3 0 2 计算A的1，2，范数要求要求:会计算矩阵的范数会计算矩阵的范数定义定义6 谱半径谱半径 设设 AR n n 的特征值的特征值为为i(i=1,2.n)称称 (A)=max|i|为为A的的谱半径谱半径 1in 那么那么,谱半径和范数之间是什么关系呢谱半径和范数之间是什么关系呢?定理定理4：特征值上界定理：特征值上界定理设设 A R n n,则则(A)|A|，即即A的谱半径不超过的谱半径不超过A的任何一种范数。的任何一种范数。证明：证明：设设是是A的任一特征值的任一特征值，x为相应的特征向量，为相应的特征向量，则则 AX=x|x|=|x|=|AX|b+b）此时，解为此时，解为 X+X,则有则有 A(X+X)=b+b 据据 AX=b 得得 AX=b X=A-1 b|X|=|A-1|b|由由 b=AX 知知|b|A+A）此时此时(A+A)(X+X)=b 由由 AX=b知知 (A+A)X=-AX 即即 A X=-A(X+X)|X|=|A-1 A(X+X)|=|A-1|A|(|X|+|X|)整理得整理得(1-|A-1|A|)|X|=|A-1|A|X|当当|A-1|A|1时时 有：有：变形为：变形为：3)A,b都有扰动 A，b,解为X+X 由此我们可知由此我们可知：A或或b有扰动时有扰动时 ,解的相对误差的上解的相对误差的上界随界随|A-1|A|的增大而增大的增大而增大，也即，也即|A-1|A|标志标志着方程组解的敏感程度。并且完全是由着方程组解的敏感程度。并且完全是由系数矩阵系数矩阵A的特性所决定的。的特性所决定的。定义定义7 设设 A为非奇异为非奇异阵，阵，称称Cond(A)=|A-1|A|为为矩阵矩阵A的条件数的条件数由此可知，方程组由此可知，方程组AX=b 的病态程度可由的病态程度可由系数矩阵系数矩阵A的条件的条件数数Cond(A)来刻画，来刻画，其值越大，方程组其值越大，方程组的病态就越严重。的病态就越严重。常用的条件数有：常用的条件数有：(1)Cond(A)=|A-1|A|(2)Cond(A)2=|A-1|2|A|2 =当当A为对称为对称正定正定时时 Cond(A)2=|1|/|n|,其中其中 1，n为矩阵为矩阵A的最的最大和最小特征值大和最小特征值 例例:求矩阵求矩阵A的条件数的条件数 逆阵的求法逆阵的求法A-1=A*/|A|A*为为A的伴随矩阵的伴随矩阵判断以 为系数矩阵的方程组是病态还是良态。1、常用的向量范数、常用的向量范数1-范数|X|1 =2-范数|X|2=()1/2 -范数|X|=max|xi|1=i=n复习A的行范数的行范数|A|=max 1=i=n2、常用的矩阵范数、常用的矩阵范数:A的列范数的列范数|A|1 =max 1=j时，时，由于x*满足方程 X*=CX*+dxi*=ci1x 1*+ci2x2*+ciixi*.cinxn*+dixi(k)=ci1x 1(k-1)+ci2x2(k-1)+ciixi(k-1).cinxn(k-1)+dixi(k)-xi*=ci1(x 1(k-1)-x 1*)+ci2(x2(k-1)-x 2)+.+cin(xn(k-1)-x n*)|xi(k)-xi*|=|ci1|x 1(k-1)-x 1*|+|ci2|x2(k-1)-x 2*|+.+|cin|xn(k-1)-x n*|=(|ci1|+|ci2|+|cin|).所以 因为0时，证得k-0。k-1充分条件充分条件2 在迭代格式中，若在迭代格式中，若则雅可比迭代格式收敛。则雅可比迭代格式收敛。充分条件充分条件3 在迭代格式中，若在迭代格式中，若则雅可比迭代格式收敛。则雅可比迭代格式收敛。汇总充分条件汇总充分条件1，2，3，只要迭代矩阵至少有一种范数，只要迭代矩阵至少有一种范数1，则雅可，则雅可比迭代格式收敛。比迭代格式收敛。迭代收敛格式，什么时候终止？迭代收敛格式，什么时候终止？每次迭代后判断每次迭代后判断|xi(k+1)-xik|=|xi(k)|是否成立，是否成立，如果成立，可停止迭代。如果成立，可停止迭代。由Jacobi迭代公式 xi(k+1)=+di (i=1,.,n k=0,1,2.)，在迭代的每一步计算过程中，是用在迭代的每一步计算过程中，是用x（k)的全部分量的全部分量来来求求x(k+1)的所有分量，的所有分量，显然，在计算显然，在计算第第i个分量个分量xi(k+1)时，已经计算出的最新分量时，已经计算出的最新分量 x 1(k+1),.x i-1(k+1)没有被利用，没有被利用，对这些最新计算出的分量加以利用，也对这些最新计算出的分量加以利用，也即在即在Jacobi迭代中用迭代中用:x1(k+1),.x i-1(k+1）来来代替代替x1(k),.x i-1(k）所得公式即为所得公式即为Gauss-seidel迭代。迭代。二、二、Gauss-Seidel迭代法及其收敛条件迭代法及其收敛条件1、迭代公式、迭代公式 Xi(k+1)=+di (i=1,2.,n)(3-41)其中其中 cij=-aij/aii (i=1,.,n,j=1,.,n,ji)cii=0 di=bi/aii 2、迭代格式的收敛条件、迭代格式的收敛条件充分条件充分条件1 在迭代格式中，若在迭代格式中，若则高斯则高斯-赛德尔迭代格式对任意初始值赛德尔迭代格式对任意初始值x(0)和和d都是收敛的都是收敛的。充分条件充分条件2 在迭代格式中，若在迭代格式中，若则高斯则高斯-赛德尔迭代格式收敛。赛德尔迭代格式收敛。汇总充分条件汇总充分条件1，2，只要迭代矩阵至少有一种范数，只要迭代矩阵至少有一种范数1，则高斯则高斯-赛德尔迭代格式收敛。赛德尔迭代格式收敛。迭代收敛格式，什么时候终止？每次迭代后判断迭代收敛格式，什么时候终止？每次迭代后判断|xi(k+1)-xik|=|xi(k)|(i=1,2.,n)则则称称A为为严格对角占优矩阵。严格对角占优矩阵。定理定理4:方程组方程组Ax=b，其中，其中A为为n阶阶严格对角占优矩阵严格对角占优矩阵时，一定存在时，一定存在收敛收敛的雅可比迭代和高斯的雅可比迭代和高斯-赛德尔迭赛德尔迭代格式。代格式。证明。证明。总结：总结：Jacobi迭代收敛条件迭代收敛条件充分条件充分条件(1):方程组方程组 AX=b的的系数矩阵系数矩阵A为为 严格对角占优阵严格对角占优阵充分条件充分条件(2):迭代矩阵至少存在一种矩阵范数迭代矩阵至少存在一种矩阵范数|.|,使使|C|1充要条件充要条件(3)：迭代矩阵的谱半径：迭代矩阵的谱半径(C)1总结：总结：高斯高斯-赛德尔迭代收敛条件赛德尔迭代收敛条件充分条件充分条件1:方程组方程组 AX=b 的系数矩阵的系数矩阵A对称正定对称正定充分条件充分条件2:方程组方程组 AX=b 的系数矩阵的系数矩阵A严格对角占优严格对角占优充分条件充分条件3：迭代矩阵迭代矩阵C的的范数范数|C|1充要条件充要条件 4：迭代矩阵迭代矩阵C的的谱半径谱半径(C)1例例1:已知已知：8x1-3x2+2x3=20 4x1+11x2-x3=33 6x1+3x2+12x3=36写出写出 jacobi迭代格式，判断其收敛性迭代格式，判断其收敛性解解:由原方程可得jacobi迭代公式x1(k+1)=3/8 x2(k)-2/8 x3(k)+20/8x2(k+1)=-4/11 x1(k)+1/11 x3(k+33/11x3(k+1)=-6/12 x1(k)3/12 x2(k)+36/12因为系数矩阵对角占优因为系数矩阵对角占优,所以所以,该迭代公式收敛该迭代公式收敛例例2：设有方程组设有方程组 X=CX+d ,考察用迭代法考察用迭代法 X(k+1)=CX(k)+d 求解方程的收敛性求解方程的收敛性其中 C=0.9 0 d=1 0.3 0.8 2例例3：将例：将例1改写成改写成Gauss-seidel迭代迭代 x1(k+1)=3/8 x2(k)-2/8 x3(k)+20/8x2(k+1)=-4/11 x1(k+1)+1/11 x3(k)+33/11x3(k+1)=-6/12 x1(k+1)3/12 x2(k+1)+36/128x1-3x2+2x3=204x1+11x2-x3=33 6x1+3x2+12x3=36例例4 用高斯用高斯-赛德尔迭代法解方程组赛德尔迭代法解方程组 解解 将原方程组写成等价形式并构造赛德尔迭代公式将原方程组写成等价形式并构造赛德尔迭代公式开始迭代开始迭代.对比上面简单迭代对比上面简单迭代,显然显然Gauss-seidel收敛较快收敛较快 !下表是下表是jacobi迭代迭代(简单迭代简单迭代)的结果的结果3.收敛性收敛性充分条件充分条件1:方程组方程组 AX=b 的系数矩阵的系数矩阵A对称正定对称正定充分条件充分条件2:方程组方程组 AX=b 的系数矩阵的系数矩阵A严格对角占优严格对角占优充分条件充分条件3：迭代矩阵迭代矩阵G的的范数范数|G|1充要条件充要条件 4：迭代矩阵迭代矩阵G的的谱半径谱半径(G)1例例5：考查用：考查用Gauss-seidel解下列方程组的收敛性解下列方程组的收敛性 5x1-x2-x3=3 x1+6x2-x3=6 x1+x2+3x3=5 解:系数矩阵为：5 -1 -1 1 6 -1 1 1 3 x1(k+1)=1/5 x2(k)+1/5 x3(k)+3/5x2(k+1)=-1/6 x1(k+1)+1/6 x3(k)+1x3(k+1)=-1/3 x1(k+1)1/3 x2(k+1)+5/3是严格对角占优阵是严格对角占优阵,所以所以Gauss-seidel迭代收敛迭代收敛收敛的收敛的Gauss-seidel迭代公式为迭代公式为:例例6 已知方程组已知方程组:试写出收敛的试写出收敛的jacobi和和Gauss-Seidel迭代格式迭代格式解解:由于直接分离由于直接分离x1,x2,x3不满足收敛条件不满足收敛条件,因此首先将方程组因此首先将方程组变形为变形为练习练习1.已知方程组 AX=b其中 A=1 2 b=1 0.3 1 2(1)讨论用jacobi迭代和Gauss-seidel的收敛性的收敛性(2)若有若有 x(k+1)=x(k)+(Ax(k)+b)则取什么取什么值,该迭代公式收迭代公式收敛?