数值分析-第5章-解线性方程组的直接方法课件.ppt

1、数理学院数理学院SCHOOL OF MATHEMATICS AND PHYSICS5.1 引言与预备知识引言与预备知识5.2 高斯消去法高斯消去法5.3 高斯主元素消去法高斯主元素消去法5.4 矩阵三角分解法矩阵三角分解法5.5 向量和矩阵的范数向量和矩阵的范数5.6 误差分析误差分析Ch5 解线性方程组的直接方法解线性方程组的直接方法 在自然科学和工程技术中有很多问题的解决常常归结为解在自然科学和工程技术中有很多问题的解决常常归结为解线性代数方程组如三次样条函数问题，用最小二乘法求实验线性代数方程组如三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有数

2、据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程的边值问题等都导致求解限元方法解常微分方程、偏微分方程的边值问题等都导致求解线性代数方程组，而这些方程组的系数矩阵大致分为两种，一线性代数方程组，而这些方程组的系数矩阵大致分为两种，一种是低阶稠密矩阵，另一种是大型稀疏矩阵。种是低阶稠密矩阵，另一种是大型稀疏矩阵。关于线性方程组的数值解法一般有两类：关于线性方程组的数值解法一般有两类：1.直接法直接法2.迭代法迭代法5.1引言与预备知识引言与预备知识5.1.1 引言引言 本章讨论本章讨论n元线性方程组元线性方程组nnnnnnnnnnbxaxaxabxaxaxab

3、xaxaxa.22112222212111212111（5.1）的直接解法。方程组的直接解法。方程组(5.1)的矩阵形式为的矩阵形式为 A Ax=b=b其中其中 nn2n1nn22221n11211a.aa.a.aaa.aaAn21x.xx,xn21b.bb,b若矩阵若矩阵A A非奇异非奇异,即即det(A A)0,则方程组则方程组(2.1)有唯一解。有唯一解。所谓直接解法是指，若不考虑计算过程中的舍入误差，所谓直接解法是指，若不考虑计算过程中的舍入误差，经过有限次算术运算就能求出线性方程组的精确解的方法。经过有限次算术运算就能求出线性方程组的精确解的方法。但由于实际计算中舍入误差的存在，用直

4、接解法一般但由于实际计算中舍入误差的存在，用直接解法一般也只能求出方程组的近似解。也只能求出方程组的近似解。Cramer法则是一种不实用的直接法，本章将介绍几种法则是一种不实用的直接法，本章将介绍几种实用的直接法。实用的直接法。5.1.2 预备知识预备知识mnmmnijnmaaaaaaaaaaARA2124222111211)(M行行n列矩阵列矩阵.nnxxxxRx21n维列向量维列向量.列。同理的第为其中iAa，aaaAin),(21行行的第的第为为iAbbbATiTmT,1 矩阵的基本运算矩阵的基本运算:(1)矩阵的加法矩阵的加法是非奇异矩阵是非奇异矩阵AAdRARcAccAcRAAAbn

5、nnnnT 0)det()(.,),det()det()(),det()det()(7)矩阵的行列式矩阵的行列式 行列式性质行列式性质:(a)det(AB)=det(A)det(B)(6)非奇异矩阵非奇异矩阵(5)单位矩阵单位矩阵(4)转置矩阵转置矩阵(3)矩阵与矩阵的乘法矩阵与矩阵的乘法(2)矩阵与标量的乘法矩阵与标量的乘法5.1.3矩阵特征值与谱半径矩阵特征值与谱半径定义定义1设设,nnijRaA若存在一个数若存在一个数(实数或复数实数或复数)和非零向量和非零向量,),(21nTnRxxxx使使,xAx(1.1)则称则称为为A的特征值的特征值,x为为A对应对应的特征向量的特征向量,A的全体

6、特征值称为的全体特征值称为A的谱，记作的谱，记作记即.,)(),(21nAA称为称为A的谱半径的谱半径.|,|max)(1iniA(1.2)由式由式(1.1)知知,可使齐次方程组可使齐次方程组0)(xAI有非零解有非零解,故系数行列式故系数行列式,0)det(AI记记0)det()(111212222111211nnnnnnnnnncccaaaaaaaaaAIp)(p称为矩阵的特征多项式，方程称为矩阵的特征多项式，方程(1.3)称为的特征方程称为的特征方程(1.3)在复数域中有在复数域中有n个根个根,21n故故).()()(21np由行列式由行列式(1.3)展开可知：展开可知：ActrAacn

7、nnnniiindet)1()1(,211211nnijRaA的的n个特征值个特征值 故故n,21是它的特征是它的特征方程方程(1.3)的几个根的几个根,并有并有.,det1121niiniiinatrAA(1.4)(1.5)A的迹的迹.A的特征值的特征值和特征向量和特征向量x还有以下性质还有以下性质:(1)AT与与A有相同的特征值有相同的特征值 及相同的特征向量及相同的特征向量x.(2)若若A非奇异，则非奇异，则A-1的特征值为的特征值为-1,特征向量为特征向量为x.(3)相似矩阵相似矩阵 B=S-1AS有相同的特征多项式有相同的特征多项式.例例1 求求242422221A的特征值及谱半径的

8、特征值及谱半径.解解:A的特征方程为的特征方程为,0)7()2(28243242422221)det(223AI故故A的特征值为的特征值为7,2321A的谱半径为的谱半径为.7)(A5.1.4 特殊矩阵特殊矩阵如果正交矩阵）对任意非零向量，（）如果（对称正定矩阵如果设埃尔米特矩阵如果对称矩阵时，如果当上海森伯格阵时，如果当上三角矩阵时，如果当三对角矩阵时，如果当对角矩阵)8(.0),(,)7()(,)6(.)5(.01)4(.0)3(.01|)2(.0)1(.)(AxxxAxRxbAAaAAAAAAajiajiajiajiRaATnTTHHnnTijijijijnnij到的矩阵。由初等置换阵的

9、乘积得置换阵，列），得到的矩阵记为列与第第行（或交换行与第由单位矩阵交换第初等置换阵。如果设酉矩阵)11()10(,)9(1BAIAAjijiAACAijijijHnn定理定理1.，则下述命题等价：设nnRA.)()5(.)4(.0)det()3(.00)2(.)1(1nArankAAAxAxbAxRbn的秩存在只有唯一解齐次方程组有唯一解，方程组对任何定理定理2.为对称正定阵，则：设nnRA).,2,1(0)det(,)4(),2,1(0)3(),2,1(,),2,1(,)2(.)1(11111nkAAniAnkaaaaAnkAAAAAkikkkkkkk即的顺序主子式都大于零的特征值其中正定

10、阵也是对称则的顺序主子阵为记也是对称正定阵为非奇异矩阵，且定理定理3.),2,1(0),2,1(0det为对称正定矩阵则的特征值或）（为对称矩阵，如果设AniAnkARAiknn定理定理4(Jordan标准型标准型)设设A为为n阶矩阵阶矩阵,则存在一个非奇异矩阵则存在一个非奇异矩阵P使得使得)()()(22111rrJJJApP其中其中:）块。为若当（且JordannnrinJriiinniiiiiii.),2,1(1111(1)当当A的若当标准型中所有若当块的若当标准型中所有若当块Ji均为一阶时均为一阶时,此标准型变成此标准型变成对角矩阵对角矩阵.）。，（阵其若当标准型必为对角的特征值各不相

11、同，则如果ndiagA21)2(求解求解bxA 高斯消去法高斯消去法(逐次消去法逐次消去法)及消去法和矩阵三角分解之及消去法和矩阵三角分解之间的关系：间的关系：5.2 高斯消去法高斯消去法,22112222212111212111nnnnnnnnbxaxaxabxaxaxabxaxaxann,2121212222111211nnnnnnnnbbbxxxaaaaaaaaa或例例2 用消去法解方程组用消去法解方程组 12254632132321xxxxxxxx解解 第第1步步.将方程将方程(2.2)乘上乘上-2加到方程加到方程(2.4)上上,消去未知数消去未知数x1,得到得到(2.2)(2.3)(

12、2.4).11432 xx第第2步步.将方程将方程(2.3)加到方程加到方程(2.5)上去上去,消去方程消去方程(2.5)中的中的x2,得到与原方程组等价的三角形方程组得到与原方程组等价的三角形方程组62546332321xxxxxx解为解为:Tx)3,2,1(*首先举一个简单的例子来说明消去法的基本思想首先举一个简单的例子来说明消去法的基本思想.上述过程相当于上述过程相当于 6562001401111156140140111156122140111)|(bA332331*)2(rrrrrr 思思路路首先将首先将A化为上三角阵化为上三角阵 /*upper-triangular matrix*/

13、，再回代求解再回代求解 /*backward substitution*/。=消元消元记记,)()1()1(nnijaAA )1()1(1)1(.nbbbbStep 1：设设 ，计算因子，计算因子0)1(11 a).,2(/)1(11)1(11niaamii将增广矩阵将增广矩阵/*augmented matrix*/第第 i 行行 mi1 第第1 1行行，得到，得到)1(1)1(1)1(12)1(11.baaan)2(A)2(b).,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij 其中其中Step k：设设 ，计算因子，计算因子且计算且计算0)(kk

14、ka).,1(/)()(nkiaamkkkkikik ).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij回代回代)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii只要只要 A 非奇异，即非奇异，即 A 1 存在，则可通过逐次消元存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。及行交换，将方程组化为三角形方程组，求出唯一解。共进行共进行？步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaan 1注意注意2:设

15、设Ax=b,其中其中A为非奇异矩阵为非奇异矩阵,如果如果,011 a由于由于A为非奇异矩阵为非奇异矩阵,所以所以A的第一列一定有元素不等于零的第一列一定有元素不等于零.例如例如计算。斯消去法照样可以进行矩阵。继续这过程，高阶非奇异右下角矩阵为时然后进行消元计算，这）位置，调到（将于是交换两行元素（）（111),02111nAarraiii定理定理5 设设Ax=b,其中其中nnRA(1)如果如果),2,1(0)(nkakkk则可通过高斯消去法将则可通过高斯消去法将Ax=b约化为等价的三角形线性方程组约化为等价的三角形线性方程组(2.10),且计算公式为且计算公式为:).,1(/)()(nkiaa

16、mkkkkikik消元计算消元计算(k=1,2,n-1)nkibmbbnkjiamaakkikkikikkjikkijkij.,1,.,1,)()()1()()()1(回代计算回代计算)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii(2)如果如果A为非奇异矩阵为非奇异矩阵,则可通过高斯消去法则可通过高斯消去法(及交换两行的初等及交换两行的初等变换变换)将方程组将方程组Ax=b约化为方程组约化为方程组(2.10).定理定理6 约化的主元素约化的主元素aii(i)0(i=1,2,k)的充要条件是矩阵的充要条件是矩阵A的所有的所有顺序主子式顺序主子式/

17、*determinant of leading principal submatrices*/Di0(i=1,2,k).即即.,2,1,0,01111111kiaaaaDaDiiiii(2.12)推论推论 如果如果A的顺序主子式的顺序主子式Dk0(k=1,2,n-1),则则.,3,2,/1)(1)1(11nkDDaDakkkkk5.2.2 三角分解法三角分解法 /*Matrix Factorization*/高斯消元法的矩阵形式高斯消元法的矩阵形式 /*Matrix Form of G.E.*/：Step 1:)0(/111111 aaamii记记 L1=1.11121nmm ，则，则)1()

18、1(1bAL)1(1)1(1)1(11.baan)2(A)2(bStep n 1:)()2(2)1(1)()2(2)2(22)1(1)1(12)1(11121.nnnnnnnnnbbbaaaaaabALLL其中其中 Lk=1.11,1knkkmm 1kL1.11,1knkkmm 111211.nLLL111jiM,记为记为L单位下三角阵单位下三角阵/*unitary lower-triangular matrix*/记记 U=)()2(2)2(22)1(1)1(12)1(11.nnnnnaaaaaaLUA 定理定理7 若若A的所有顺序主子式的所有顺序主子式/*determinant of le

19、ading principal submatrices*/均不为均不为0，则，则 A 的的 LU 分解唯一（其分解唯一（其中中 L 为为单位单位下三角阵）。下三角阵）。证明：证明：由由1中定理可知，中定理可知，LU 分解存在。下面证明唯一性。分解存在。下面证明唯一性。若不唯一，则可设若不唯一，则可设 A=L1U1=L2U2，推出，推出121111UULL211122211LLUULLUpper-triangularLower-triangularWith diagonal entries 1I L 为一般下三角阵而为一般下三角阵而 U 为为单位单位上三角阵的分解称为上三角阵的分解称为Crout

20、 分解分解。实际上只要考虑实际上只要考虑 A*的的 LU 分解，即分解，即 ，则，则 即是即是 A 的的 Crout 分解。分解。ULA*LUA 121UU例例3 对于例对于例2,系数矩阵系数矩阵 122140111A由高斯消去法由高斯消去法,LUAmmm 200140111112010001,1,2,0323121故故5.3.1 列主元消去法列主元消去法:在顺序消元过程中在顺序消元过程中,只要只要即可进行计算即可进行计算,)1,2,1(0)(nkakkk但如果但如果|)(kkka很小很小,则将导致舍入误差增长则将导致舍入误差增长,使解的误差很大使解的误差很大.例例4 用用Gauss 消去法求

21、解方程组消去法求解方程组232120001.02121xxxx5.3 高斯主元素消去法高斯主元素消去法解解:因因099997.3,00001.021故方程有唯一解故方程有唯一解,且精确解为且精确解为Tx)49998750.0,25001875.0(*若用若用Gauss消去法取四位有效数字计算消去法取四位有效数字计算,可得解可得解Tx)5000.0,0000.0(*xx与比较比较,误差很大误差很大,若将两个方程互换为若将两个方程互换为120001.02322121xxxx用用Gauss消去法取四位有效数字计算消去法取四位有效数字计算,可得解可得解Tx)5000.0,2500.0(本例表明通过行交

22、换可避免舍入误差增长本例表明通过行交换可避免舍入误差增长,这就是列主元消这就是列主元消去法的基本思想去法的基本思想.其计算步骤如下其计算步骤如下:第第1步步，在，在)()1()1(ijaAA中的第中的第1列选主元，即列选主元，即 1111|,|max|1iaainii行为主元行为主元,若若,11i将|)1()1(bA的第的第i1行与第行与第1行互换，再按消元行互换，再按消元公式计算得到公式计算得到|)2()2(bA假定上述过程已进行假定上述过程已进行(k-1)步，得到步，得到|)()(kkbA第第k步，在步，在)(kA中的第中的第k列选主元，即列选主元，即|,|max|)()(kiknikkk

23、iaak若若,kik则在则在|)()(kkbA中将中将ik行与第行与第k行互换，再按消元行互换，再按消元公式计算得到公式计算得到|)1()1(kkbA对对k=1,2,n-1,重复以上过程则得重复以上过程则得|)()(nnbA如果某个如果某个k出现主元出现主元），或0(0|)(kkka方程没有唯一解或严重病态，否则可由方程没有唯一解或严重病态，否则可由(3.2.4)求得解求得解.则表明则表明detA=0，它也表明当非奇异时，存在排列矩阵它也表明当非奇异时，存在排列矩阵(若干初等排列矩阵若干初等排列矩阵的乘积的乘积),使使PA=LU,其中其中L为单位下三角矩阵为单位下三角矩阵,其元素其元素|lij

24、|=1,U为为上三角矩阵上三角矩阵.ULILILIAUAAILILILnniiiniininnn112211)(111212111121121上述每步行交换后再消元相当于上述每步行交换后再消元相当于1,2,1,|)1()1()()(1nkbAbAILkkkkkikk其中其中1kL是指标为是指标为k的初等下三角矩阵的初等下三角矩阵,kikI为初等排列矩阵为初等排列矩阵kik时时,IIkik表示不换行表示不换行,经过经过(n-1)步换行与消元步换行与消元,A化为上三角矩阵化为上三角矩阵.UAn)(即即:解解:例例5用列主元消去法解用列主元消去法解x=b,其中其中4178.745625.5996.3

25、3816.1078125.014.022002.0|bA4.022002.03816.1078125.014178.745625.5996.3|bA消元消元47471.00010.161077.0040371.00020.20028.204178.745625.5996.3|)2()2(bA消元消元35159.039047.00040371.00020.20028.204178.745625.5996.3|)3()3(bA消元结束由回代公式求得解消元结束由回代公式求得解Tx)90043.0,69850.0,92730.1(此例的精确解为此例的精确解为Tx)900423.0,698496.0,9

26、300.1(*可见结果精度较高若不选列主元可见结果精度较高若不选列主元auss消去法，求得解消去法，求得解Tx)88888.0,68695.0,930.1(，误差较大，误差较大除列主元消去法外，还有一种消去法，是在的所有元素除列主元消去法外，还有一种消去法，是在的所有元素aij中中选主元，称为全主元消去法因计算量较大且应用列主元已能选主元，称为全主元消去法因计算量较大且应用列主元已能满足实际要求，故不再讨论目前很多数学软件库都有列主元满足实际要求，故不再讨论目前很多数学软件库都有列主元消去法，可直接调用消去法，可直接调用注注:为了减少计算的舍入误差为了减少计算的舍入误差,使用消去法通常都要选主

27、元使用消去法通常都要选主元.目前最目前最常用的是列主元消去法常用的是列主元消去法,也就是每步消元之前选主元也就是每步消元之前选主元,当当A=(aij)第一步选第一步选A中第中第1列的主元列的主元,即即max|ai1|=ai1.然后将然后将i1行与第行行与第行互换，再进行消元，以后每步消元做法类似，先选主元，再消互换，再进行消元，以后每步消元做法类似，先选主元，再消元元5.3.2 高斯若当消去法高斯若当消去法消去对角线上方和下方的元素消去对角线上方和下方的元素.假设已经完成假设已经完成k-1步步,得到与方程得到与方程Ax=b等价的方程组等价的方程组1111,1,11111)()(11),(knn

28、nnkkkknkkkknkkkknkkkbaabaabaabaabA 高斯消去法有很多变形高斯消去法有很多变形,有的是高斯消去法的改进、改写，有的是高斯消去法的改进、改写，有的是用于某一类特殊性质矩阵的高斯消去法的简化。有的是用于某一类特殊性质矩阵的高斯消去法的简化。5.3.1 直接三角分解法直接三角分解法.将高斯消去法改写为紧凑形式将高斯消去法改写为紧凑形式,可以直接从可以直接从A的元素得到计算的元素得到计算L,U元素的递推公式元素的递推公式,而不需要任何中间步骤而不需要任何中间步骤,这就是所谓直接三角这就是所谓直接三角分解法分解法.一旦实现一旦实现A的的LU分解分解,那么求解那么求解Ax=

29、b的问题就等价于求解两的问题就等价于求解两个三角形方程组个三角形方程组 (1)Ly=b,求求y;(2)Ux=y,求求x.yUxbLybLUx.4 矩阵矩阵三角分解法三角分解法 /*Matrix Factorization*/.不选主元的三角分解法不选主元的三角分解法 设设A为非奇异矩阵为非奇异矩阵,且有分解式且有分解式A=LU,其中其中L为单位下三为单位下三角角,U为上三角即为上三角即 nnnnnnnnuuullaaaa.1.11.1111211111 L,U元素可以由元素可以由n步直接计算定出步直接计算定出,其中第其中第r步定出步定出U的第的第r行行和和L的第的第r列元素列元素.由上式有由上

30、式有:.1),2(/1),2,1(1111111111列元素列元素的第的第得得行元素；行元素；的第的第得得LniualulaUniuaiiiiii 故故),1,(11nrriulaukirkrkriri 同样有同样有:rrirrkkriknkkrikirululula 111 设已经定出设已经定出U的第的第1行到第行到第r-1行元素与行元素与L的第的第1列到第列到第r-1列列元素元素.利用矩阵乘法利用矩阵乘法(注意当注意当rk时时,lrk=0),有有rikirkrkkinkrkriuulula 111得得irl通过比较法直接导出通过比较法直接导出L 和和 U 的计算公式。的计算公式。思思路路

31、nnnnnnnnuuullaaaa.1.11.1111211111 ),min(1jikjkkiul jia固定固定 r:对对 i=r,r+1,n 有有rikirkrkriuula11lii=1),1,(11nrriulaukirkrkriria将将 r，i 对换，对对换，对 r=i,i+1,n 有有iijikiikjkjiulula 11);,1(/)(11nrnriuulalrrikkrikirir且b结论结论:用直接三角分解法解用直接三角分解法解Ax=b(要求要求A的所有顺序主子式都不等的所有顺序主子式都不等于于0)的计算公式如下的计算公式如下.Step 1:u1i=a1i;li1=ai

32、1/u11;(i=2,n)计算计算U的第的第r行行,L的第的第r列元素列元素(r=2,3,，n）Step 2:),1,(11nrriulaukirkrkriri);,1(/)(11nrnriuulalrrrkkrikirir且求解求解Ly=b,Ux=y 的计算公式：的计算公式：Step 3:Step 4:1111);,3,2(ikkikiiniylbybyStep 5:nikiikikiinnnnnniuxuyxuyx1).1,2,1(/)(;/例例5 用直接三角分解法解用直接三角分解法解201814513252321321xxx解解 用分解公式计算得用分解公式计算得.240041032115

33、3012001LUA求解求解.)3,2,1(,)72,10,14(,)72,10,14(,)20,18,14(TTTTxUxyLy得得2.选主元的三角分解法选主元的三角分解法 当当urr=0时计算中断，或者当时计算中断，或者当urr绝对值很小时，按分解公式计绝对值很小时，按分解公式计算可能引起舍入误差的积累。算可能引起舍入误差的积累。但如果但如果A非奇异，可以通过交换非奇异，可以通过交换A的行实现矩阵的行实现矩阵A的的LU分解，分解，因此可采用与列主元消去法类似的方法，将直接三角分解法修改因此可采用与列主元消去法类似的方法，将直接三角分解法修改为（部分）选主元的三角分解法。为（部分）选主元的三

34、角分解法。设第设第r-1步分解已完成，这时有步分解已完成，这时有nnnrrnnnrnrrrrrrnrrrrrrrnrrnrraalllaallluuulluuuuluuuuuA1,2,11,21,1,11,12,11,1221,22221111,11211第第r步分解需用到（步分解需用到（3.2）及（）及（3.3）式，为避免用小的数）式，为避免用小的数urr做除数，引进量做除数，引进量11).,1,(rkkrikirinrriulas于是有：于是有：).,1(/,nrisslsuriirrrr取取|maxirinirss 交换交换A的的r行与行与ir行元素，将行元素，将irs调到调到(r,r)

35、位置位置(将（将（i，j）位置的新元素仍记为）位置的新元素仍记为lij 及及 aii),于是有于是有|lir|1时时,aij=0,且：且：.0|)();1,3,2(0,|,|)(;0|)(11 nniiiiiabcnicacabbcba nnnnnnnfffxxxbacbacbacb212111122211Step 1:对对 A 作作Crout 分解分解 111121nnnA 直接比较等式两边直接比较等式两边的元素，可得到计的元素，可得到计算公式。算公式。).1,3,2(),2(,111111 nicnirbracbiiiiiiiii 为下三角，为单位上三角为下三角，为单位上三角注意当注意当j

36、=1时有时有对对j=2，3，n求得求得L的元素的元素，这就是，这就是A的的Cholesky分解，然后再解两个三角方程组，得分解，然后再解两个三角方程组，得这就是对称正定方程组的平方根法这就是对称正定方程组的平方根法 另外，由于另外，由于 故有故有这表明分解过程中矩阵这表明分解过程中矩阵L中元素中元素因此平方根法计算是数值稳定的因此平方根法计算是数值稳定的.11111111,lalalii ijlnilylbylbyiiikkiki,3,2,/)(,/111111 1,1,/)(,/1 nilxlyxlyxjjknikkiiinnnn的数量级不增长，的数量级不增长，),2,1(0),2,1(12

37、njlnjaljjjjjkjk 而而jkljjnjjknknjal 111max|maxStep 2:追追即解即解fyL,111 fy ),.,2()()(111nibyafyrfyiiiiiiiiiii Step 3:赶赶即解即解 ：yxU)1,.,1(,1 nixyxyxiiiinn xyUxyfLyfLUx，求，求求求,求解求解xf等价于等价于Step:计算计算 i 的递推公式的递推公式)/(,/1111 iiiiiabcbc 将计算系数将计算系数nnyyy 21121及及 为追的过程为追的过程将计算方程组的解将计算方程组的解11xxxnn 为赶的过程为赶的过程定理：定理：设有三对角线方

38、程组设有三对角线方程组xf，其中满足对角占优的条件，其中满足对角占优的条件，则为非奇异矩阵且追赶法计算公式中的则为非奇异矩阵且追赶法计算公式中的 ii ,满足：|);1,2(|02);1,2,1(1|01nnnnniiiiiiiababniababcni 。定理定理 若若 A 为为对角占优对角占优/*diagonally dominant*/的三对角的三对角阵，且满足阵，且满足 ，则追赶，则追赶法可解以法可解以 A 为系数矩阵的方程组。为系数矩阵的方程组。0,0,0|,0|11 iinncaabcb如果如果 A 是是严格严格对角占优阵，则不要求三对角线上的对角占优阵，则不要求三对角线上的所有元

39、素非零。所有元素非零。根据不等式根据不等式 可知：分解过程中，矩阵元素不会过分增大，算法可知：分解过程中，矩阵元素不会过分增大，算法保证稳定。保证稳定。运算量为运算量为 O(6n)。|,1|1iiiiiiiiabbab 5.5.1 内积与向量范数内积与向量范数为了研究方程组为了研究方程组Ax=b解的误差和迭代法收敛性，需对向量解的误差和迭代法收敛性，需对向量 nRx 及矩阵及矩阵 nnRA 的的大小大小引进一种度量，就要定义范数，引进一种度量，就要定义范数，它是向量它是向量长度长度概念的直接推广，通常用概念的直接推广，通常用 nR表示表示n维实向量维实向量空间，空间，nC表示表示n维复向量空间

40、维复向量空间.定义定义2 设设).(),(,),(2121nnTnTnCRyyyyxxxx或或 将实数将实数）或复数或复数iniiTiniiHyxxyyxyxxyyx 11),(),(称为向量称为向量x,y的数量积的数量积.非负实数非负实数，或或21122122112212)|(),(|()(),(|niiniixxxxxxxx称为向量称为向量x的欧氏范数或的欧氏范数或2-范数范数.5.5 向量和矩阵范数向量和矩阵范数定理定理12设设),(,nnCRyx或或 则内积有以下性质：则内积有以下性质：时成立；时成立；当且仅当当且仅当0,0),(xxx(1)(2)为复数为复数，为实数（或为实数（或 )

41、,(),().,(),(yxyxyxyx (3),(),()(,(),(xyyxxyyx或（或（(4);,(),(),(2121yxyxyxx (5)(柯西柯西-施瓦茨不等式施瓦茨不等式),|),(|22yxyx 等式当且仅当等式当且仅当x与与y线性相关时成立线性相关时成立;(6)三角不等式三角不等式,|222yxyx 定义定义3(向量范数向量范数)如果向量如果向量)C(nnRx或或 的某个实值函数的某个实值函数|,|)(xxN 满足条件满足条件:三角不等式），三角不等式），）（），），或或）（），），时等号成立（正定条件时等号成立（正定条件当且仅当当且仅当(|3(,|20,0|)1(yxyx

42、CRxxxx 则称则称.|)(上上的的一一个个向向量量范范数数是是nRxxN 对于对于,)(|2/1122 niixx由内积性质可知它满足定义由内积性质可知它满足定义2的三个条件，的三个条件，故它是一种向量范数故它是一种向量范数.此外还有以下几种常用的向量范数此外还有以下几种常用的向量范数.范数）范数）称为称为 (|max|1inixx范数）范数）称为称为 1(|11niixx容易验证容易验证 1|xx及及 均满足定义均满足定义2的三个条件的三个条件.更一般的还可定义更一般的还可定义pnipipxx/11)(|但只有但只有p=1,2,时的三种范数是常用的向量范数时的三种范数是常用的向量范数.例

43、如给定例如给定,)3,2,1(Tx 则可求出则可求出 3|,14|,6|21 xxx定理定理14设设|)(xxN 是是nR则则N(x)是向量是向量x的分量的分量 上任一种向量范数，上任一种向量范数，nxxx,21的连续函数的连续函数.定理定理15(向量范数的等价性向量范数的等价性)设设 tS|与与是是nR上任意两种向量范数，则存在常数上任意两种向量范数，则存在常数,021 cc使使.|21StSxcxxc 5.5.2 矩阵范数矩阵范数 矩阵矩阵nnijRaA )(可看成可看成nn维向量，如果直接将向量维向量，如果直接将向量的的2-范数用于矩阵范数用于矩阵A，则可定义，则可定义2/11,2)(|

44、)(njiijFaAAF称为矩阵称为矩阵A的的Frobenius范数，简称范数，简称F-范数范数.它显然满足向它显然满足向量范数的三条性质，但由于矩阵还有乘法运算，因此矩阵量范数的三条性质，但由于矩阵还有乘法运算，因此矩阵范数的定义中应增加新条件范数的定义中应增加新条件.定义定义4 如果如果 nnijRaA )(的某个非负实函数的某个非负实函数N(A)，记作，记作A，满足条件：满足条件：;,|,|)4(;,(|3;,|20,0|)1(nnnnRBABAABRBABABARAAAA 三角不等式），三角不等式），）（）（），），时等号成立（正定条件时等号成立（正定条件当且仅当当且仅当 则称则称.|

45、)(上上的的一一个个向向量量范范数数是是nnRAAN 显然显然 FA|满足定义中的四个条件满足定义中的四个条件,(3)，(4)两条均可由两条均可由Cauchy-Schwarz不等式证明，故不等式证明，故 FA|是一种矩阵范数是一种矩阵范数.除矩阵自身的运算外，在解方程中矩阵乘向量的运算即除矩阵自身的运算外，在解方程中矩阵乘向量的运算即Ax，也是必不可少的也是必不可少的.因此要求所引进的范数应满足条件：因此要求所引进的范数应满足条件：|xAAx 上式称为相容性条件上式称为相容性条件.为使引进的矩阵范数满足条件为使引进的矩阵范数满足条件(4.5)，我们给出以下定义我们给出以下定义.(4.5)定义定

46、义6(矩阵的算子范数矩阵的算子范数)设设,nnnRARxnvnnnRxRARx是|,当给定向量范数当给定向量范数 v|时可定义时可定义 vxvvxvAxxAxAv|max|max|1|0称为矩阵的算子范数或从属范数称为矩阵的算子范数或从属范数.(4.6)定理定理17 设设 上的一种向量范数，上的一种向量范数，则由则由(4.6)定义的定义的vA|是一种矩阵范数，且满足相容性条件是一种矩阵范数，且满足相容性条件|xAAx 证明证明 因因 nvRA是|中有界闭集中有界闭集1|,),(|1vTnxxxxxD上的连续函数，故上的连续函数，故 vA|在在D上有最大值，即上有最大值，即 Dx 0使使,|ma

47、x|1|0vvxvAAxAxv而对而对 vnxxxxRx|,0,令故故DxxAxxAxAxvvvvv,|所以所以 vvvvxvxAxxAxA|max|0从而当从而当|0 xAAxx 时成立，而成立，而x=0时时显然也成立显然也成立.|xAAx 定理定理17 设设,nnnRARx则则)(|max|11的行范数AaAnjijni)(|max|111的列范数AaAniijnj)2()(|2范数的AAAAT这里这里)(为矩阵的谱半径为矩阵的谱半径.例例7 已知已知.|,|,|,|,432112AAAAAF求解解.6|,477.530|,7|1AAAF043020141410)det(,20141410

48、2AAIAATT465.5866.29|,22115212A从定理可以看出，计算从定理可以看出，计算 1|AA及较容易，而计算 2|A时因为要求时因为要求 AAT的特征值，所以较为困难的特征值，所以较为困难.但当但当A对称时，有对称时，有).()()()()(|max2maxmax22AAAAAAAATT定理定理19.|2）（为对称矩阵，则如果AARAnn定理定理18 对任何对任何|,nnRA为任一种从属范数则为任一种从属范数则|,|)(AA 反之，对任意反之，对任意0，至少存在一种从属范数，至少存在一种从属范数,|使使.)(|AA证明证明:设设 为为A的特征值，则的特征值，则,Ax,0 xx

49、使由由|xAxxAAx及得得.|max)(|AAA即BIBRBnn则,1|,非奇异，且非奇异，且|11|)(|1BBI证明证明用反证法用反证法.假定假定(I+B)奇异，则齐次方程奇异，则齐次方程 0)(xBI有非零解有非零解 使即0,0 xRxn1|0000 xBxBxx故而而 1|max|000 xBxxBxBx与B1的假设矛盾，故(I+B)非奇异.又又，即IBIBBIIBIBI111)()(,)(得得，11)()(BIBIBI取范数取范数，|)(|1|)(|11BIBBI得得|11|)(|1BBI定理定理20设设 5.6.1矩阵条件数与扰动方程组误差界矩阵条件数与扰动方程组误差界在解方程组

50、在解方程组Ax=b时，由于各种原因，时，由于各种原因，A或或b往往有往往有误差，从而使得解也产生误差误差，从而使得解也产生误差.例例8 方程组方程组 0001.880001.626221xx的准确解为的准确解为 Tx)1,1(*,当当A与与b有微小变化时，如变为方程有微小变化时，如变为方程 0002.889999.526221xx则准确解为则准确解为,)2,10(Tx 它表明它表明A,b的微小扰动引起方程解的微小扰动引起方程解x的很大的很大变化，这就是病态方程变化，这就是病态方程.5.6 误差分析与病态方程组误差分析与病态方程组定义定义7 求解线性方程组求解线性方程组Ax=b时，若时，若A或或