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

数值分析NumericalAnalysis第五章解线性代数方程组的直接法郑州大学研究生课程（2011-2012学年第一学期）2/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis第五章解线性代数方程组的直接法§5.1引言§5.2高斯消去法§5.3主元素高斯消去法§5.4三角分解法§5.5对称正定矩阵的平方根法§5.6三对角方程组的追赶法§5.7范数与误差分析3/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.1引言自然科学和工程计算中的很多问题的解决常常归结为求解线性方程组。如三次样条插值函数问题、用最小二乘远离确定拟合曲线、求解微分方程的数值解等，最终都要转化为求解线性方程组。4/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.1引言从微观的薛定谔方程、分子动力学方程到宏观的结构计算、工程力学中弹塑性方程、热弹性方程组，数值求解方法包括差分法及有限元方法等。这些离散方法最终的结果是常化为线性方程组的求解。5/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.1引言快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重大研究课题之一。各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。6/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.1引言系数矩阵的分类第一类：低阶稠密方程组，即系数矩阵的阶数不高，含零元素很少，在线性代数等课程学习中通常见到的，都属这类方程组；第二类：高阶稀疏方程组，系数矩阵的阶数很高，如几百阶、甚至成千上万阶，其中零元素成片分布，数量上绝对占优。7/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.1引言线性方程组的数值解法有：直接法和迭代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。8/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.1引言35det()0,det()(1,2,,)det()1(1)!30,2.3810iiAAxinAnnnnnnn如果线性方程组的系数行列式不为零，即则该方程组有唯一解。由克莱姆(cramer)法则，其解为这种方法需要计算个阶行列式并作次除法，而每个阶行列式计算需作次乘法，计算量十分惊人。如需次乘法。可见其n在理论上是绝对正确，但在较大时，在实际计算中确实不可行的。9/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.1引言解：例：直接法解线性方程组1231231232222334463xxxxxxxxx1222(,)23344163Ab61121702128006178921122200131x23871xx1232222xxx10/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.2高斯消去法高斯消去法的主要思路：将系数矩阵A化为上三角矩阵，然后回代求解。nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb11112211211222221122.........考虑n阶线性方程组：=11/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis1112111212222212nnnnnnnnaaaxbaaaxbaaaxbTT1212,(),(,,),(,,).ijnnnnAxbAaxxxxbbbb记为其中§5.2高斯消去法12/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis→→11bbaa)(ii)(ijij,统一记号：(1)(1)T(1)(1)(1)ijX=(1)(1)=[],=n1bA(,...,)abAbb:原方程)(→)(:0≠111121)1(11新第二行（第一行）第二行若aaa)()()(→)()(111131新第三行第一行第三行aa)()()n(naa)()(n行新第（第一行）行第→)(11111§5.2高斯消去法13/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis(1)(1)(1)(1)(1)11112213311(2)(2)(2)(2)22223322(2)(2)(2)(2)32233333(2)(2)2233nnnnnnnnaxaxaxaxbaxaxaxbaxaxaxbaxax(2)(2)nnnnaxb上述消元过程除第一个方程不变以外,第2到第n个方程全消去了变量x1，而系数和常数项全得到新值：§5.2高斯消去法14/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis依次将增广矩阵的第i行+mi1第1行，得)1(1)1(1)1(12)1(11...baaan(2)Ab(2)记(1)1(1)(1)(1)(1)(),ijnnnbAaAbbb，即(1)(1),ijijiiaabb(1)110a(1)(1)1111(2,...,)iiianma设，计算(2)(1)(1)11(2)(1)(1)11ijijijiiiaamabbmb其中(,2,...,)ijn§5.2高斯消去法---第一步消元---15/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysisbbbbaaaaaaaAnnnnnn)2()2(2)1(1(2))2()2(2)2(2)2(22)1(1)1(12)1(11)2(00，其中22xbA（）（）得到新同解方程组：21111111111()()()()()ijijijiiaamamaaz§5.2高斯消去法16/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.2Gauss消去法(2)220a第二步消元：若，对除第一行第一列外的子阵作上计算：3222234,()()()iii,,,nijbbbm(3)(2)(2)(2)(2)i22i2222ijijjiaamamaa00000)3()3(3)2(2)1(1(3))3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)3(bbbbbaaaaaaaaaaaAnnnnnnn，17/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis依次将上述矩阵的第i行+mi2第2行，得(3)(2)(2)22(3)(2)(2)22ijijijiiiaamabbmb其中(,3,...,)ijn(2)(2)2222(3,...,)iiianma设，计算(2)220a)1(1)1(1)1(12)1(11...baaanA(3)b(3)(2)(2)(2)2222...naab§5.2高斯消去法18/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis第k步：消去第k列依此类推，直到第n-1步，原方程化为()()(1,...,)kkikikkkmakain设，计算()0kkka(1)(1)(1)(1)1112111(2)(2)(2)22222()()nnnnnnnnaaabxxaabxba计算(1)()()(1)()()kkkijijikkjkkkiiikkaamabbmb(i，j=k+1,…,n)§5.2高斯消去法19/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.2Gauss消去法消去过程算法11()()1(k)(k)(k)(k)(k)ijijkjikkk(k)(k)(k)(k)(k)iikikkkki,jnaaaaabbbaa（）11(1),1;,,1;0,k1in,1jk;(k)(k)ijij(k)(k)iikijikjnikjnaabba，1,2,,n1.k20/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.2Gauss消去法回代过程算法abx)n(nn)n(nn=()()()1()in1,n2,,1.niiiiiijjiijixbaxa(1)(1)(1)(1)111111()()()(1)(1)(1)11111iinniiiiiiinninnnnnnnnnnaxaxaxbaxaxbaxaxb()()nnnnnnaxb21/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis乘除运算量：由于计算机中做乘除运算的时间远远超过做加减运算时间，故估计运算量时，往往只估计乘除的次数。第k步：消去第k列()()(1,...,)kkikikkkmakain设，计算()0kkka计算(1)()()(1)()()kkkijijikkjkkkiiikkaamabbmb(i=k+1,…,n)回代求解：()()nnnnnnxba()()()1()niiiiiijjiijixbaxa(i=k+1,…,n)n–k次(n–k)2次n–k次n(n+1)/2次高斯消去法总的乘除运算量为：3233nnn22/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis顺序Gauss消去法的评价★相对Cramer法则而言，顺序Gauss消去法大大减少了计算量。★此方法的使用条件要求每一步消去的时候主元素成立，否则无法进行下去。(),0(1,2,...,1)kkkakn§5.2高斯消去法3()On23/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis§5.2高斯消去法定理5.2.11110,Da11110(1,2,,).iiiiiaaDikaa高斯约化的主元素的充要条件是矩阵A的顺序主子式()0(1,2,,)iiiaik0(1,2,,)iDik24/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis定理5.2.2若矩阵A对称正定，则01,2,,kkkakn推论5.2.1如果的顺序主子式A),1,,2,1(0nkDk,1)1(11Da则).,,3,2(/1)(nkDDakkkkk§5.2高斯消去法25/130郑州大学研究生2011-2012学年课程数值分析NumericalAnalysis★高斯消元法的局限性1.在高斯消元过程中，我们假定了对角元素由于每次消元时是按未知量的自然顺序进行的，而顺序消元不改变A的主子式的值，因此高斯消元法可行的充分必要条件为A的各阶主子式不为零。2.即使高斯消元法可行，如果很小，运算中用它作分母会导致其它元素数量级的严重增长和舍入误差的扩散。()0,kkka()kkka§