数值计算方法21(1)52

iiijjijiilxlbx11nnnnnnaaaaaaaaaA212222111211bAxni,,3,2第二章解线性方程组的直接法2iiijjijiilxlbx11nnnnnnaaaaaaaaaA212222111211bAxni,,3,22.1直接法与三角形方程组求解§2.2Gauss消去法§第二章解线性方程组的直接法2.3Gauss列主元消去法§2.4直接三角分解法§2.5平方根法§2.6追赶法(Thomas法)§3本章要点线性方程组的解法类型之一:直接解法主要归结为三角形方程组的求解包括一般线性方程组的Gauss消去法、Gauss列主元法、对称正定方程组的平方根法、三对角方程组的追赶法等涉及到一些三角分解：主要有Doolittle分解、Crout分解、Cholesky分解等本章作业4Gauss消去法对于线性方程组bAxnnnnnnaaaaaaaaaA212222111211nxxxx21nbbbb21其中系数矩阵未知量向量常数项------------(1)5根据Cramer(克莱姆)法则,若0)det(A有唯一解则方程组bAxdeterminantal||)det(AA行列式的记号6(1)(1)(1)(1)111211(1)(1)(1)(1)212222(1)(1)(1)(1)12nnnnnnnaaabaaabaaab(1)(1)(1)(1)111211(2)(2)(2)2222(2)(2)(2)200nnnnnnaaabaabaab11,2,,iiilllmin(1)(1)(1)(1)11112211(1)(1)(1)(1)21122222(1)(1)(1)(1)1122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb(1)(1)(1)(1)11112211(1)(2)(2)(2)21122222(1)(2)(2)(2)1122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb7(1)(1)(1)(1)111211(2)(2)(2)2222()()()()()()nnkkkkkknkkkknknnnaaabaabaabaab(1)(1)(1)(1)111211(2)(2)(2)2222()()nnnnnnnaaabaabab,1,,iikiklllmikn(1)(1)(1)(1)111211(2)(2)(2)2222(2)(2)(2)200nnnnnnaaabaabaab22,3,,iiilllmin(1)(1)(1)(1)11112211(2)(2)(2)22222()()nnnnnnnnnnaxaxaxbaxaxbaxb8共计n-1次消元，其中第k次消元的结果：()()()(),1()()()()1,1,11,1()()()(),,1kkkkkkkkknkkkkkkkkkknkkkkknknknnnaaabaaabaaab()()()(),1(1)(1)(1)1,11,1(1)(1)(1),100kkkkkkkkknkkkkkkknkkkknknnnaaabaabaab公式为：,1,,iikiklllmikn(1)()(),1,,1kkkijijkjikaaamjkn()()kikikkkkama9()()(1)()()1:11:1:1kikikkkkiikikkkkijijkjikforknforiknforjknamaklllmaaamendendend第次消元所有公式汇总（数值方法）：10通过前面系列公式，将原方程组变成下面等价方程组(1)(1)(1)(1)11112211(2)(2)(2)22222()()nnnnnnnnnnaxaxaxbaxaxbaxb最后回代求解，公式为：()()()11(),,1,,1nkkkkkjjkjkkkxbaxknna11考虑计算机的存储和运算方式，建立数组(1,1)(1,2)(1,)(1,1)(2,1)(2,2)(2,)(2,1)(,1)(,2)(,)(,1)aaananaaananaananannann前面公式中的可换成()kija(,),(,1)aijain()kib经过k-1步消元后，矩阵a变为12(1,1)(1,2)(1,)(1,1)(2,2)(2,)(2,1)(,)(,)(,)(,)(,)(,1)aaananaananakkaknannankannann第k步消元前，先选主元、换行。即数值方法变为k=1:n-1选主元，换行if新主元≠0消元else输出无解、结束end13选主元的算法：令p为主元素所在行，pv为主元素值,(,)1:(,)(,),pkpvakkforqknifaqkpvpvaqkpqendend除回代以为的程序如下：141:1,(,)1:(,)(,),1:1:1(,)(,)(,)(,)(,)(,)ikforknpkpvakkforqknifaqkpvpvaqkpqendendpkforiknforjknaikmakkaijaijakjmikendendend15二、Gauss消去法的运算量计算机作乘除运算所耗时间要远远多于加减运算且在一个算法中，加减运算和乘除运算次数大体相当故在衡量一个算法的运算量时只需统计乘除的运算次数步消元时作第k乘法次数：次)1)((knkn除法次数：次)(kn数为步消元乘除法运算总次作第k次)2)((knkn16总次数为步消元需作乘除法运算完成全部1n11)2)((nkknkn652323nnn全部回代过程需作乘除法的总次数为niin1)1(222nn于是Gauss消去法的乘除法运算总的次数为MD3323nnn)(323nOn数级17很大时当n3323nnnMD33n时如20nGauss消去法乘除法约为2700次而如果用Cramer法则的乘除法运算次数约为20)120)(120(!2020109或2700)120(用行列式定义用行列式性质