平方根法解线性方程组

第三章解线性代数方程组的直接法3.1高斯消元法3.2矩阵的三角分解3.3解三对角方程组的追赶法3.4平方根法和改进的平方根法3.5线性代数方程组的性态自然科学和工程计算中的很多问题的解决常常归结为求解线性方程组。如三次样条插值函数问题、用最小二乘远离确定拟合曲线、求解微分方程的数值解等，最终都要转化为求解线性方程组。求解线性方程组可采用：直接法——经有限步算术运算可求得方程组的精确解的方法（若计算过程无舍入误差）。已知的直接解法是克莱姆法则(Gramer)。迭代法——构造某种迭代格式，用其极限过程去逐步逼近线性方程组精确解的方法。设线性方程组为或写成矩阵形式或简单地记为:11112211211222221122(3.1)nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb1112111212222212(3.2)nnnnnnnnaaaxbaaaxbaaaxbTT1212,(),(,,),(,,).ijnnnnAxbAaxxxxbbbb3.1高斯消去法3.1.1三角形方程组的解★对角形方程组若aii≠0,则xi=bi/aii,i=1,2,…,n。运算量O(n)。11112222222(3.3)naxbaxbaxb★下三角方程组111121122221122112233(3.4)iiiiiinnnnnnnlxblxlxblxlxlxblxlxlxlxb11122,11111Fromthequation,()/,1,2,,.iiiiiiiiiiiijjjiiiijjiijilxblxlxlxblxxblxlin运算量：因为计算xi需要i次乘法和除法，所以★上三角方程组2(1)12().2nnnOn11112213311,111,111,1(3.5)nniiiiiiinninnnnnnnnnnnuxuxuxuxbuxuxuxbuxuxbuxb•运算量：因为计算xi需要n-i次乘法和1次除法，即n–i+1次乘除，所以,1111Fromthequation()/,/,1,2,,2,1.niiiiiiiinniijjjinnnnniiijjiijiiuxbuxuxbuxxbuxbuxuinn1121(1)(1)().2njniinjnnnijOn3.1.2高斯消元法与列主元消元法消元法的基本思想就是通过对方程组作初等变换，把一般形式的线性方程组化为等价的易于求解的三角方程组。★高斯消元法（GaussianElimination）高斯消元法是一种古老的求解线性方程组的方法，它就是通过一系列的初等变换（消元），把线性方程组（3.1）化为等价的上三角方程组（3.5），然后通过回代方法求出原方程组的解。111111111112211(1)(1)(1)22222(1)(1)(1)22Assume0,setting/,2,3,,,thenth1st,2,3,,,wehaveiiinnnnnnnnnamaainiminaxaxaxbaxaxbaxaxb(1)(1)1111(3.6)where,,,2,3,,.ijijjiiiiaaambbbmijn11112211211222221122(3.1)nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb重复上述过程，可以得到与（3.1）等价的上三角方程组：(1)(1)(1)22222211112212311(1)(1)(1)(1)22222322(2)333For(3.6),assume0,setting/,3,4,,,th2nd,wehaveiinnnnamaainiaxaxaxaxbaxaxaxbax(2)(2)33(2)(2)(2)33(3.7)nnnnnnnaxbaxaxb(2)(1)(1)(2)(1)(1)2222where,,,3,4,,.ijijjiiiiaaambbbmijn或写成矩阵形式A(n-1)x=b(n-1),其中，11112212311(1)(1)(1)(1)22222322(2)(2)(2)33333(1)(1)nnnnnnnnnnnnaxaxaxaxbaxaxaxbaxaxbaxb(3.8)11121311(1)(1)(1)(1)222322(1)(1)(2)(2)(2)3333(1)(1),.nnnnnnnnnnaaaabaaabAbaabab约定由（3.8）逐个回代，可得（3.1）的解(0)(0),,for1,2,,1,wehaveijijiiaabbkn()(1)(1)(1)(1)()(1)(1)(1)(1)/*,,1,,(3.9)/*,1,,.kkkkkijijikkkkjkkkkkiiikkkkaaaaaijknbbaabikn(1)(1)(1)(1)(1)1/(3.10)/,1,,2,1nnnnnnniiiiiijjiijixbaxbaxain★高斯消元法算法：1.输入数据：n,A,b2.消元过程：FOR1TO1{FOR1TO{/FOR1TO{}ENDFOR:}ikkkijijkjiikknikntaajknaatajbbtbENDFOR}ENDFORik3.回代求解4.输出方程组的解FORTO1{FOR1TO{}/}iijjiiiinsbjinssaxxsa12,,,.nxxx★高斯消元法运算量：•消元过程：乘：除：•回代过程：•运算量：221(1)(1)(2)32211(1)(1)(1),31(1)(2)21(1);(forrightitem)2nnkknnnnkkkknnnnnn1(1)(2)21(1)2nnnn112(1)(multiply)(divide)(1).2nnnn322311135(1)(1)(1)322326().nnnnnnnnnOn★高斯消元法的局限性：1.在高斯消元过程中，我们假定了对角元素由于每次消元时是按未知量的自然顺序进行的，而顺序消元不改变A的主子式的值，因此高斯消元法可行的充分必要条件为A的各阶主子式不为零。实际上只要detA≠0，方程组就有解。2.即使高斯消元法可行，如果很小，运算中用它作分母会导致其它元素数量计的严重增长和舍入误差的扩散。(1)0,kkka(1)kkka例3.1解方程组精确解为：x1=1/3，x2=2/3。计算去5位有效数字。解顺序消元：交换方程的顺序：经高斯消元：12120.00033.00002.00011.00001.00001.0000xxxx121220.00033.00002.00010.66679999.06666.00xxxxx12121.00001.00001.00000.00033.00002.0001xxxx122211.00001.00001.00000.66672.99971.99980.3333xxxxx★列主元消元法•高斯消元过程中的称为主元素。•如果在一列中选取按模最大的元素作为主元素，将其调换到主干方程位置再做消元，则称为列主元消元法。具体地第一步,先在第1列选出绝对值最大的元素,交换第1行和第m行的所有元素，再做消元操作。第二步，对每个k=1，2，…，n做消元前，选出中绝对值最大的元素，对k行和m行交换后，再作消元。(1)0(1,2,,)kkkakn11max||||,imiinaa(1)(1)(1)1,||,||,,||kkkkkkknkaaa(1),||kmka★列主元消元法算法列主元消元法与高斯消元法相比，只是增加了选列主元和交换两个方程（即两行元素）的过程。因此在高斯消元法的算法中增加选主元和交换过程即可。•选主元：FOR1TO1{||,FOR1TOIF||THEN{;||}FORTO(exchange,){;;}kkukukkvkvmvmvkknsamkuknasmusavknkmtaaaattb;;}kmmbbbt3.2矩阵的三角分解用矩阵相乘来解释高斯消元过程，取n=4。记(3.1)化为方程组(3.6)的过程，即等价于L1A=A(1),L1b=b(1),即211111131411000100,where/,2,3,4.010001iilLlaaill(1)(1),AxbAxb记(3.6)化为方程组(3.7)的过程等价于L2A(1)=A(2),L2b(1)=b(2),即111213141111213141(1)(1)(1)(1)222324221222324221(1)(1)(1)(1)313233343313233343(1)(1)(1)(1)4142434444142434441000010001000010aaaabaaaabaaabaaaablaaaablaaabaaaablaaab(1)(1)22222324210000100,where/,3,4.010001iiLlaaill(1)(1)(2)(2),AxbAxb记111213141111213141(1)(1)(1)(1)(1)(1)(1)(1)22232422223242(1)(1)(1)(1)(2)(2)(2)32323334333343(1)(1)(1)(1)(2)4242434444341000000100010000001000aaaabaaaabaaabaaablaaabaablaaabaa(2)(2)44b(2)(2)34343334310000100,where/.0010001Llaal(2)(2)(3)(3)(2)(3)(2)(3)33,equalto,.i.e.AxbAxbLAALbb因此其中，111213141111213141(1)(1)(1)(1)(1)(1)(1)(1)22232422223242(2)(2)(2)(2)(2)(2)3334333343(2)(2)(2)(3)(3)434344444410000001000010000000100000aaaabaaaabaaabaaabaabaablaabab(,).Ab(2)(1)3323211111321123,,ALALLALLLAALLLALLLALU111123111213132434142100010001000010010001000010010010001001001LLLLllllll2131324341422131324142431000100