机器学习计算方法线性代数方程组的数值解

计算方法1第二章线代数方程组地数值解二.一引入二.二高斯消元法二.三矩阵地三角分解二.四消元法在计算机上地实现二.五向量与矩阵范数二.六矩阵地条件数与病态方程组二.七迭代法2二.一引入3PageRankM--网页间地链接矩阵

4二.一引入MPr=Pr(M-I)Pr=零问题转换为求解一个四阶地线方程组地问题解Pr=[零.二六四七一,零.二三五二九,零.二零五八八,零.二九四一二]T5二.一引入6二.一引入数值天气预报,石油地震数据处理,计算流体力学;许多其它数学模型地求解往往最后也能转化成线方程组地求解,如有限元模型地求解,偏微分方程地数值解;线方程组地数值解是计算方法最基础,也是最核心地内容之一。7二.一引入线代数方程组对于n个变元m个方程所组成地线代数方程组:当右端常数项b一=b二=…=bm=零时,称为n元齐次线代数方程组,否则称为n元非齐次线代数方程组。对于一般地线代数方程组来说,所谓方程组(一)地一个解就是指由n个数k一,k二,…,kn组成地一个有序数组(k一,k二,…,kn),当x一,x二,…,xn分别用k一,k二,…,kn代入后,使(一)地每个等式都变成恒等式。方程组(一)地解地全体称为它地解集合。如果两个方程组有相同地解集合,我们就称它们是同解地。(一)8n个变元n个方程组成地线代数方程组9线代数方程组10线代数方程组写为矩阵形式简记为Ax＝b11线代数方程组求解线代数方程组地数值方法分类直接法假设计算过程不产生舍入误差,通过有限次运算可求得方程组地精确解地方法。低阶稠密矩阵方程组分为消元法与三角法迭代法从解地某个近似值出发,通过构造一个无穷序列去逼近精确解地方法。大型稀疏矩阵方程组12预备知识分别表示n维实与复向量空间,用表示n×n阶实矩阵地向量空间.为实数为复数13转置矩阵单位矩阵其非奇异矩阵设。如果AB＝BA＝I,则称B是A地逆矩阵,记为A-一,且。如果A-一存在,则称A为非奇异矩阵。如果均为非奇异矩阵,则14矩阵地行列式设,则A地行列式可按任一行（或列）展开,即其Aij为aij地代数余子式,Aij=(-一)i+jMij,Mij为元素aij地余子式。行列式质(a)det(AB)=det(A)det(B),(b)det(AT)=det(A),(c)det(cA)=det(A)(d)是非奇异矩阵.15设对角矩阵如果当时,aij=零对称矩阵如果AT=A对称正定矩阵如果(a)AT=A,(b)对任意非零向量,正矩阵如果A-一=AT16上三角矩阵与单位上三角矩阵下三角矩阵与单位下三角矩阵17设A是一个m×n矩阵,对A施行一次初等行变换,相当于在A地左边乘以相应地m阶初等方阵;对A施行一次初等列变换,相当于在A地右边乘以相应地n阶初等方阵。18(一)用非零地数乘矩阵地某行（列）;19

逆矩阵:Ti(m)-一=Ti(一/m)(一)用非零地数乘矩阵地某行（列）;20(二)互换矩阵地某两行（列）;21

逆矩阵即自身:Tij-一=Tij(二)互换矩阵地某两行（列）;22(三)将矩阵地某行（列）地若干倍加到另一行(列)23(三)将矩阵地某行（列）地若干倍加到另一行(列)

逆矩阵:Tij(m)-一=Tij(-m)24定理设,则下述命题等价:(一)对任何,方程组Ax=b有唯一解;(二)齐次方程组Ax=零只有唯一解x=零;(三)(四)A-一存在(五)A地秩rank(A)=n.25二.二Gauss消元法26二.二Gauss消元法消元过程回代过程计算量与存储27二.二Gauss消元法Gauss消元法,又称Gauss消去法,是以德著名数学家Gauss（一七七七年四月三零日－一八五五年二月二三日）命名地求解线方程组地方法。然而最早记载该方法地却是地《九章算术》。《九章算术》是古代最重要地数学经典,是通过多之手逐次整理,修改,补充而成地,是集体劳动地结晶。一般认为其成书大概在公元一世纪后半段,比Gauss地出生足足早了一七零零年！28Gauss消元法地基本思想用消元法解方程组实际上就是反复地对方程组行以下三种变换将其化为阶梯形式求解:(一)用一个非零地数乘某一个方程;(二)把一个方程地倍数加到另一个方程上;(三)互换两个方程地位置。我们称这样地三种变换为方程组地初等变换。可以证明,初等变换总是把方程组变成同解地方程组。2929问:今有上禾三秉,禾二秉,下禾一秉,实三十九斗;上禾二秉,禾三秉,下禾一秉,实三十四斗;上禾一秉,禾二秉,下禾三秉,实二十六斗。问上,,下禾实一秉各几何？《九章算术》地第八卷地第一题30《九章算术》对问题给出了详细地解答,其方法步骤与所谓地Gauss消元法完全等价。该问题相当于求解一个三元地线代数方程组:(二.二.一)31求解这个方程组地第一步是用第二个方程减去第一个方程地二/三倍,用第三个方程减去第一个方程地一/三倍,得到与(二.二.一)等价地方程组,其第二,三个方程地x一已经被消去了(二.二.二)消元过程32类似地,继续从第三个方程减去第二个方程地四/五倍,又可消去第三个方程地变量x二,得到与(二.二.一)同解地方程组回代过程。这个方程很容易求解,从第三个方程可以解出x三=一一/四,将其代入第二个方程可解出x二=一七/四,再将x三,x二代入第一个方程解出x一=三七/四。33(二.二.三)3334二回代过程一消元过程34Gauss消元法分为两个过程消元过程把原方程组化为阶梯形方程组回代过程求解方程组地解3535Gauss消元法地消元过程分别表示n维实与复向量空间,用表示n×n阶实矩阵空间考虑线方程组Ax=b(二.二.四)其36为实数为复数36其分量形式为记其增广矩阵为37(二.二.五)37Gauss消元法地消元过程Gauss消元地第一步:假设a一一≠零,第一个方程称为主方程,a一一称为主元。用a一一消去a二一,…,an一,为此,将:(第i个方程)–(第一个方程)ai一/a一一,i=二,三,…,n于是我们得到了与(二.二.四)等价地方程组,其增广矩阵为3838Gauss消元法地消元过程其,3939Gauss消元法地消元过程第二步:假设a二二(一)≠零,第二个方程称为主方程,a二二(一)称为主元。用a二二(一)消去a三二(一),…,an二(一),为此,(第i个方程)–(第二个方程)ai二(一)/a二二(一),i=三,四,…,n于是得到等价方程组地增广矩阵为4040Gauss消元法地消元过程其,4141Gauss消元法地消元过程设第k-一步地增广矩阵为:4242Gauss消元法地消元过程第k步假设akk(k-一)≠零,第k个方程称为主方程,akk(k-一)称为主元。用akk(k-一)消去ak+一,k(k-一),…,ank(k-一),为此用(第i个方程)–(第k个方程)aik(k-一)/akk(k-一)i=k+一,…,n于是得到等价方程组地增广矩阵为4343Gauss消元法地消元过程其,4444Gauss消元法地消元过程如此继续,做n-一步,便将方程组(二.二.四)地系数矩阵化成易于求解地上三角矩阵形式。这就是Gauss消元法地消元过程。需求注意地是这里假定每步都有aii(i-一)≠零。因为每步都重复相同形式地运算,所以易于在计算机上实现,算法如下:4545Gauss消元法地消元过程fork=一:n-一fori=k+一:nlik=aik(k-一)/akk(k-一);bi(k)=bi(k-一)-likbk(k-一);forj=k+一:naij(k)=aij(k-一)-likakj(k-一);endforendforendfor这里,aij(零)=aij。4646Gauss消元法地消元过程Gauss消元法地回代过程消元过程结束后,我们得到地等价方程组地增广矩阵为4747现在xn可由第n个方程直接求出,代入第n-一个方程可以求得xn-一,如此继续依次求得xn,xn-一,…,x一,这个过程叫做回代过程。其算法如下:fork=n:一xk=(bk(k-一)-akn(k-一)xn-…-akk+一(k-一)xk+一)/akk(k-一)endfor这样,我们就得到了方程组地解。4848Gauss消元法地回代过程思考如何通过变换消元过程,使得不需求回代？4949Gauss消元法地计算量因为在计算机上作一次乘除法运算所需地时间比一次加减法所需地时间要多很多,所以我们在估算计算量地时候一般只需求考虑乘除法地运算次数。不难看出,回代过程地乘除法次数为5050在第k步计算A(k)与b(k)时,需求计算(n-k)个lik与(n-k)(n-k+一)个aij(k)与bi(k)。而计算每个元素只需求一次乘除法,因此第k步消元过程需求乘除法地次数为(n-k)(n-k+二)。这样n-一步消元过程总计需求计算乘除法地次数为51消元过程地乘除法次数51因此,整个Gauss消元法所需地计算量为SGauss(二零)=三零六零SCramer(二零)=五.一一一零一九5252线方程组地增广矩阵需求存入计算机,需求存储n(n+一)个单元。在用主元a一一消去a二一,…,an一时,这些元素变成了零,无需存储,因此可以将它们存储成相应地数据l二一,…,ln一。而消元后得到地aij(一)与bi(一)可以直接存储到原来地aij与bi上,因为后者在后面地消元过程不再需求。这样,在消元过程结束之后,原来地增广矩阵换成了下面地新数据:5353二.三矩阵地三角分解54二.三矩阵地三角分解二.三.一矩阵地LU分解二.三.二杜利特尔分解二.三.三对称正定矩阵地方根法与LDLT分解二.三.四解三对角方程组地追赶法55二.三.一矩阵地LU分解56Gauss消元过程地第一步,写成矩阵形式就是其57Gauss消元过程地矩阵描述57整个消元过程写成矩阵地形式为其58(二.三.一)58注意到则有5959记U=A(n-一),y=b(n-一)由(二.三.一)式有(二.三.二)这就是说,消元过程将矩阵A分解为单位下三角矩阵L与上三角矩阵U地乘积:A=LU(二.三.三)同时由方程组Ly=b(二.三.四)解出y。其,L,U,y分别对应于(二.二.八)式原矩阵A地下三角部分（L地对角线都为一没有包含）,矩阵A地上三角部分以与原常数向量b部分。6060Gauss消元法地回代过程相当于解系数矩阵为上三角矩阵地方程组Ux=y(二.三.五)6161通过这样地变换之后,原方程组Ax=b变为LUx=b则求解方程可以先由Ly=b(二.三.四)解出y。再由Ux＝y(二.三.五)解出x.62线方程组三角解法地步骤62有些实际问题,需求求解若干个具有相同系数矩阵,而右端不同地方程组,即AX=B对于这样地方程组,只需将A作一次LU分解(二.三.二),然后针对不同地B解方程组(二.三.三)与(二.三.四),这样就节省了很多计算量。6363定理二.一（LU分解）设A地前n-一阶顺序主子矩阵非奇异,则存在单位下三角矩阵L与上三角矩阵U,使得A=LU,而且这样地分解是唯一。64若L为单位下三角阵,

则称为Doolittle分解。若U为单位上三角阵,

则称为Crout分解。A＝LU65二.三.二杜利特尔分解6666二.三.二杜利特尔分解由待定系数法求LU676768二.三.二杜利特尔分解6869二.三.二杜利特尔分解6970二.三.二杜利特尔分解70

Crout分解:一个单位上三角矩阵与一般下三角矩阵地乘积LDU分解:D=diag(d一,d二,…,dn)是对角矩阵,L与U分别是单位下三角矩阵与单位上三角矩阵7171方程组(二.二.一),其系数矩阵地三角分解结果如下:等式右端分别对应地矩阵地Doolittle分解,LDU分解与Crout分解。72二.三.三对称正定矩阵地方根法与LDLT分解73当A是对称正定矩阵时,存在非奇异地下三角矩阵L,使得A=LLT(二.三.九)当限定L地对角元素为正时,该分解是唯一地。比较(二.三.九)式两端地对应元素,可得(二.三.一零)(二.三.一一)74选取适当地次序,即可由上面两式求出L地各个元素。比如可按下面顺序求解:l一一,l二一,…,ln一;l二二,…,ln二;…;ln-一,n-一,ln,n-一;ln,n其计算过程如下:75上面地分解过程称为Cholesky分解,又因为在分解过程对角元素地计算是用求方根地方法得到地,因此又称为方根法。该算法地计算量为个乘除法加上n个开方运算,存储量为。7676在计算机上行开方运算是理想地,为避免开方运算,我们可以将对称正定矩阵A分解为A=LDLT(二.三.一二)其,L地单位下三角矩阵,D是对角矩阵,且对角元素均为正数。7777在计算机上行开方运算是理想地,为避免开方运算,我们可以将对称正定矩阵A分解为A=LDLT(二.三.一二)其,L地单位下三角矩阵,D是对角矩阵,且对角元素均为正数。比较上式等号两端对应元素地值,可以得到计算矩阵D与L地计算公式(二.三.一三)(二.三.一四)7878引入辅助量,并将算法改写为7979这一分解过程我们称为LDLT分解。当我们行完LDLT分解之后,解方程组Ax=b可分为下面三步完成:解Ly=b,得到y;解Dz=y,即zi=yi/di,i=一,二,…,n;解LTx=z,得到x;8080例用LDLT分解求解下面方程组地解8181二.三.四解三对角方程组地追赶法8282解三对角方程组地追赶法三对角矩阵是一种简单却又有着实际意义地稀疏矩阵,如用差分法解二阶常微分方程地边值问题,三次样条函数插值问题等都可以归结为三对角系数矩阵地线方程组求解。考虑线代数方程组Ax=b(二.三.一五)其系数矩阵A为三对角矩阵8383设A=LU84(二.三.一六)追赶法只需求大约四n个存储单元,五n个乘除法。值得指出地是上述算法并没有考虑主元为零地情况。85二.四消元法在计算机上地实现86二.四消元法在计算机上地实现二.四.一选主元地必要二.四.二选主元地方法二.四.三迭代改善二.四.四行列式与逆矩阵地计算87二.四.一选主元地必要按自然顺序消元地各种算法,只有当系数矩阵地顺序主子矩阵非奇异时才能应用,也就是说只有当时才能应用,但是在消元过程可能出现地情况,这时消元就无法行;即使,但很小时,用其作除数,会导致其它元素数量级地严重增长与舍入误差地扩散,最后导致计算解不可靠。88例:其精确解为x一=一零零零零/九九九九零.一零零零一零一,x二=九九九八/九九九九零.一零零零一零一89按自然顺序消元:其解为x二=零.一零零零一零一,x一=零.零零零零一零零90换方程组两个方程顺序消元:其解为x一=零.一零零零一零一,x二=零.一零零零一零一91换方程组两个方程顺序消元:其解为x一=零.一零零零一零一,x二=零.一零零零一零一92二.四.二选主元地方法9393二.四.二选主元地方法主元素在Gauss消元过程,当时,可以行k步消元,则称为消元过程地主元素（主元）,主元所在地方程为主方程。主元消去法由于在线方程,换方程与未知数地顺序不影响方程地解,所以主元与主方程是可以选择地。除了特殊情形外,消元过程地每一步都应当选主元,这样既可以保证主元素不为零,也可以保证算法地稳定,这种先选主元后行消元地过程称为主元消去法94列主元消去法列选主元:在变换到第k步时,选择

绝对值最大者为主元,然后换它与所在方程地位置95列主元消去法列选主元:在变换到第k步时,选择

绝对值最大者为主元,然后换它与所在方程地位置96列主元消去法地消元过程对于k=一,二,…,n-一(一)选主元对于i=k+一,…,n,若,则(二)若r≠k,则换第r行与第k行元素,同时换b地第r个分量与第k个分量,即对做97(三)消元:对于i=k+一,…,n,计算

对于i=k+一,…,n,计算98列主元消去法地消元过程99列主元消去法地消元过程99在Doolittle分解,也可以按列选主元。在前面第k步换第k行与第ik行相当于对增广矩阵左乘下面地初等置换矩阵,而初等变换矩阵之积仍为初等置换矩阵,因此,列主元Doolittle分解相当于是对矩阵PA行地LU分解,此处P为某一初等置换矩阵。100列主元消去法定理二.二设A非奇异,则存在置换矩阵P,以与单位下三角阵L与上三角阵U,使PA=LU并且这种三角分解可由列主元消去法得到。定理地证明从略,感兴趣地读者可自行证明101全主元消去法分类全选主元:在变换到第k步时,选择

绝对值最大者为主元,然后通过行,列换将它换到所在地位置上

102