LU和QR法解线性方程组
一、 问题描述
?4?8求解方程组??4??12要求：
1、编写用三角（LU）分解法求解线性方程组； 2、编写用正交三角（QR）分解法求解线性方程组。
275?10??836??61120?12?x1???2??x???7??2?==??, ?x3???7??????x4???3?二、问题分析
求解线性方程组Ax=b，其实质就是把它的系数矩阵A通过各种变换成一个下三角或上三角矩阵，从而简化方程组的求解。因此，在求解线性方程组的过程中，把系数矩阵A变换成上三角或下三角矩阵显得尤为重要，然而矩阵A的变换通常有两种分解方法：LU分解法和QR分解法。
1、LU分解法：
将A分解为一个下三角矩阵L和一个上三角矩阵U，即：A=LU,
?10?l121?其中 L=?????ln1ln22、QR分解法：
?0??u11u12?0u?0?22?， U=??0?0?0???1?0?0?u1n??u2n?? ?????unn?将A分解为一个正交矩阵Q和一个上三角矩阵R,即：A=QR
三、实验原理
1、LU分解法
解Ax=b 的问题就等价于要求解两个三角形方程组：
⑴ Ly=b,求y; ⑵ Ux=y,求x.
设A为非奇异矩阵,且有分解式A=LU, L为单位下三角阵,U为上三角阵。 L,U的元素可以有n步直接计算定出。用直接三角分解法解Ax=b（要求A的所有顺序主子式都不为零）的计算公式：
① uli?ali(i?1,2,?,n),lil?ail/u11 ,i=2,3,…，n. 计算U的第r行，L的第r列元素(i=2,3,…,n)： ② uri?ari??lk?1r?1r?1rkuki ， i=r,r+1,…,n;
③ lir?(air??lk?1ikukr)/urr , i=r+1,…,n,且r≠n.
求解Ly=b，Ux=y的计算公式；
y1?b1, ④
yi?bi??likyk,i?2,3,?n:k?1i?1
xn?yn/unn,⑤
xi?(yi?k?i?1?uikxk)/uii,i?n?1,n?2,?,1.n
2、QR分解法
四、实验步骤
1、LU分解法
1>将矩阵A保存进计算机中，再定义2个空矩阵L，U以便保存求出的三角矩阵的值。 利用公式①，②，③将矩阵A分解为LU，L为单位下三角阵,U为上三角阵。 2>可知计算方法有三层循环。
先通过公式①计算出U矩阵的第一行元素uli 和L矩阵的第一列元素lil。
再根据公式②和③，和上次的出的值，求出矩阵其余的元素，每次都要三次循环，求下一个元素需要上一个结果。 3>先由公式④ ，Ly=b
y1?b1,
yi?bi??likyk,i?2,3,?n:k?1i?1
求出y，因为L为下三角矩阵，所以由第一行开始求y. 4>再由公式⑤，Ux=y
xn?yn/unn,xi?(yi?k?i?1?unikxk)/uii,i?n?1,n?2,?,1.
求出x, 因为U为上三角矩阵，所以由最后一行开始求x. 2、QR分解法
五、程序流程图
1、LU分解法
开始输入系数矩阵A，常数项b及ndet←1K=1,n-1,1调选列主元子程序消i=k+1,n,1元过程aik←aik/akk(即求乘数mik)j=k+1,n,1aik←aij-aik *akjjbi←bi←aik*bkidet←akkdetkbn←bn/am(即求出xn)i=n-1,1,-1s←0j=i+1,n,1s←s+aij*bjjbi←(bi-s)/aijidet←amndet输出b及det结束回代过程
由主程序转来d←akk,p←ki=k+1,n,1≤|aik|>|d|d←aik,p←i选列主元id=0=P=kj=k,n,1=det←0≠返回主程序输出失败标志，|A|=0t←apj,apj←akj,akj←t结束jt←bp,bp←bk,bk←tdet←det返回主程序
2、QR分解法