数值分析 第5章 解线性方程组的直接方法

数理学院SCHOOLOFMATHEMATICSANDPHYSICS5.1引言与预备知识5.2高斯消去法5.3高斯主元素消去法5.4矩阵三角分解法5.5向量和矩阵的范数5.6误差分析Ch5解线性方程组的直接方法在自然科学和工程技术中有很多问题的解决常常归结为解线性代数方程组．如三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程的边值问题等都导致求解线性代数方程组，而这些方程组的系数矩阵大致分为两种，一种是低阶稠密矩阵，另一种是大型稀疏矩阵。关于线性方程组的数值解法一般有两类：1.直接法2.迭代法§5.1引言与预备知识5.1.1引言本章讨论n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.........................................................22112222212111212111（5.1）的直接解法。方程组(5.1)的矩阵形式为Ax=b其中nn2n1nn22221n11211a...aa............a...aaa...aaAn21x...xx,xn21b...bb,b若矩阵A非奇异,即det(A)≠0,则方程组(2.1)有唯一解。所谓直接解法是指，若不考虑计算过程中的舍入误差，经过有限次算术运算就能求出线性方程组的精确解的方法。但由于实际计算中舍入误差的存在，用直接解法一般也只能求出方程组的近似解。Cramer法则是一种不实用的直接法，本章将介绍几种实用的直接法。5.1.2预备知识mnmmnijnmaaaaaaaaaaARA2124222111211)(M行n列矩阵.nnxxxxRx21n维列向量.列。同理的第为其中iAa，aaaAin),,,(21行的第为iAbbbATiTmT,1矩阵的基本运算:(1)矩阵的加法是非奇异矩阵AAdRARcAccAcRAAAbnnnnnT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的全体特征值称为A的谱，记作记即}.,,,{)(),(21nAA称为A的谱半径.|,|max)(1iniA(1.2)由式(1.1)知,λ可使齐次方程组0)(xAI有非零解,故系数行列式,0)det(AI记0)det()(111212222111211nnnnnnnnnncccaaaaaaaaaAIp)(p称为矩阵Ａ的特征多项式，方程(1.3)称为Ａ的特征方程．(1.3)在复数域中有n个根,,,,21n故).())(()(21np由行列式(1.3)展开可知：ActrAacnnnnniiindet)1()1(,211211nnijRaA的n个特征值故n,,,21是它的特征方程(1.3)的几个根,并有.,det1121niiniiinatrAA(1.4)(1.5)A的迹.A的特征值λ和特征向量x还有以下性质:(1)AT与A有相同的特征值λ及相同的特征向量x.(2)若A非奇异，则A-1的特征值为λ-1,特征向量为x.(3)相似矩阵B=S-1AS有相同的特征多项式.例1求242422221A的特征值及谱半径.解:A的特征方程为,0)7()2(28243242422221)det(223AI故A的特征值为7,2321A的谱半径为.7)(A5.1.4特殊矩阵Ｔ－１＝Ａ如果Ａ正交矩阵）对任意非零向量，（）如果（对称正定矩阵如果Ｃ设Ａ埃尔米特矩阵　如果对称矩阵　时，如果当上海森伯格阵时，如果当上三角矩阵时，如果当三对角矩阵时，如果当对角矩阵)8(.0),(,)7()(,)6(.)5(.01)4(.0)3(.01||)2(.0)1(.)(AxxxAxRxbAAaAAAAAAajiajiajiajiRaATnTTHHnnTijijijijnnij到的矩阵。由初等置换阵的乘积得置换阵Ｉ，Ｉ列），得到的矩阵记为列与第第行（或交换行与第由单位矩阵Ｉ交换第初等置换阵。如果设酉矩阵)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即的顺序主子式都大于零的特征值其中正定阵也是对称则的顺序主子阵为记也是对称正定阵为非奇异矩阵，且定理3..),,,2,1(0),,,2,1(0det为对称正定矩阵则的特征值或）（为对称矩阵，如果设AniAnkARAiknn定理4(Jordan标准型)设A为n阶矩阵,则存在一个非奇异矩阵P使得)()()(22111rrJJJApP其中:）块。为若当（且JordannnrinJriiinniiiiiii.),,,2,1(1111(1)当A的若当标准型中所有若当块Ji均为一阶时,此标准型变成对角矩阵.）。，，，（阵其若当标准型必为对角的特征值各不相同，则如果ndiagA21)2(求解bxA高斯消去法(逐次消去法)及消去法和矩阵三角分解之间的关系：§5.2高斯消去法,,,22112222212111212111nnnnnnnnbxaxaxabxaxaxabxaxaxann,2121212222111211nnnnnnnnbbbxxxaaaaaaaaa或例2用消去法解方程组12254632132321xxxxxxxx解第1步.将方程(2.2)乘上-2加到方程(2.4)上,消去未知数x1,得到(2.2)(2.3)(2.4).11432xx第2步.将方程(2.3)加到方程(2.5)上去,消去方程(2.5)中的x2,得到与原方程组等价的三角形方程组62546332321xxxxxx解为:Tx)3,2,1(*首先举一个简单的例子来说明消去法的基本思想.上述过程相当于6562001401111156140140111156122140111)|(bA332331*)2(rrrrrr思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=消元记,)()1()1(nnijaAA)1()1(1)1(...nbbbbStep1：设，计算因子0)1(11a)...,,2(/)1(11)1(11niaamii将增广矩阵/*augmentedmatrix*/第i行mi1第1行，得到)1(1)1(1)1(12)1(11...baaan)2(A)2(b)...,,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij其中Stepk：设，计算因子且计算0)(kkka)...,,1(/)()(nkiaamkkkkikik)...,,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij回代)()(/nnnnnnabx)1...,,1()(1)()(niaxabxiiinijjiijiii注意1：只要A非奇异，即A1存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。共进行？步)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaan1注意2:设Ax=b,其中A为非奇异矩阵,如果,011a由于A为非奇异矩阵,所以A的第一列一定有元素不等于零.例如计算。斯消去法照样可以进行矩阵。继续这过程，高阶非奇异右下角矩阵为时然后进行消元计算，这）位置，调到（将于是交换两行元素（）（111),,02111nAarraiii定理5设Ax=b,其中nnRA(1)如果),,,2,1(0)(nkakkk则可通过高斯消去法将Ax=b约化为等价的三角形线性方程组(2.10),且计算公式为:)...,,1(/)()(nkiaamkkkkikik①消元计算(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的所有顺序主子式/*determinantofleadingprincipalsubmatrices*/Di≠0(i=1,2,…,k).即.,,2,1,0,01111111kiaaaaDaDiiiii(2.12)推论如果A的顺序主子式Dk≠0(k=1,2,…,n-1),则.,,3,2,/1)(1)1(11nkDDaDakkkkk§5.2.2三角分解法/*MatrixFactorization*/高斯消元法的矩阵形式/*MatrixFormofG.E.*/：Step1:)0(/111111aaamii记L1=1...11121nmm，则][)1()1(1bAL)1(1)1(1)1(11...baan)2(A)2(bStepn1:)()2(2)1(1)()2(2)2(22)1(1)1(12)1(11121..................nnnnnnnnnbbbaaaaaabALLL其中Lk=1...11,,1knkkmm1kL1...11,,