数值分析学习课件教学课件PPT教案解线性方程组的直接法

1、iiijjijiilxlbx11nnnnnnaaaaaaaaaa212222111211bax ni, 3 ,2第二章 解线性方程组的直接法2.1 消元过程与矩阵的三角分解消元过程与矩阵的三角分解1.3 基本的三角分解法(doolittle法),0)(knnijdaan的顺序主子式阶方阵若nk,2 , 1,alualu则 的分解存在且唯一 即nnnknknkkknkaaaaaaaaaa11111111111nknkmmm)()()()1(1)1(1)1(11nnnkknkkknkaaaaaalu11111nrnrlllnnrnrrnruuuuuu1111nnnrnrnrrrnraaaaaaaa

2、aa111111上式可记为为的第一行元素根据矩阵的乘法原理jaa1,njuajj,2 , 111为素行元素主对角线以右元的第),(nrjararjrkkjrkrjula1nr,2 , 1nrj,11111,1nrnrlllnnrnrrnruuuuuu1111nnnrnrnrrrnraaaaaaaaaa111111同样,由为素列元素主对角线以下元的第可知), 1(nriarairrkkrikirula11,2 , 1nrnri, 1 1111,1,ularii 时显然ni,3 ,2综合以上分析,有njuajj,2 , 111rkkjrkrjula1nr, 2 , 1nrj,rkkrikirula

3、11, 2 , 1nrnri, 11111ulaiini, 3 , 2 因此可以推导出ju1ja1nj,2 , 1u的第一行1111ualiini, 3 ,2l的第一列rjrkkjrkrjuula111rrirrkkrikirulula11-(1)-(2)11rkkjrkrjrjulaunr,2 , 1nrj,u的第r行rrrkkrikiriruulal111,2 , 1nrnri, 1 l的第r列-(3)-(4)称上述称上述(1) (4)式所表示的分解过程为式所表示的分解过程为doolittle分解分解.)4() 1 (,式的表达式请找出类似于解分则称之为表示为单位上三角阵角阵表示为下三中的

4、为上三角阵，如果将为单位下三角阵中分解的croutulluaulluadoolittlea思考对于线性方程组bax 系数矩阵非奇异,经过doolittle分解后lua 线性方程组可化为下面两个三角形方程组bly yux 为中间未知量向量y1111321323121nnnlllllllnnnnnnnnuuuuuuuuuuu,11,1,22322,1131211:,的解不难得到的知识由第一节三角形方程组bly 11by 11rjjrjrrylbynr, 3 ,212122ylby的解的解便得到因此再由baxyuxnnnnuyx rrnrjjrjrruxuyx11 ,2 ,2, 1nnr111132

5、1323121nnnlllllllnnnnnnnnuuuuuuuuuu,11,1,22322,1131211ju1ja11111ualii上述解线性方程组的方法称为上述解线性方程组的方法称为直接三角分解法的直接三角分解法的 doolittle法法例1. 用doolittle法解方程组1391444321131243301024321xxxx72510解:由doolittle分解14131211uuuu30102tlll4131211t25 . 05 . 112423220uuu5 . 812110tll423210t11/611/310343300uu11/211/300tl43100t910

6、044000u4000得解, bly tyyyy4321t1611/17201011rkkjrkrjrjulaurrrkkrikiriruulal1111rrrrjjjybl y11yb得解, yux txxxx4321t4321nnnnuyx rrnrjjrjrruxuyx1doolittle法在计算机上实现是比较容易的iiijjijiilxlbx11nnnnnnaaaaaaaaaa212222111211bax ni, 3 ,2第二章 解线性方程组的直接法 2.2 gauss列主元列主元消去法消去法2.2 gauss列主元列主元消去法消去法例1.用gauss消去法解线性方程组(用3位十进制

7、浮点数计算）210001. 02121xxxx解: 本方程组的精度较高的解为tx)00010001. 1 ,99989999. 0(* 用gauss消去法求解(用3位十进制浮点数计算)一、gauss列主元消去法的引入),(baa21111000100. 01000021m441000. 111000. 101000100. 0999900. 1,00. 021xx回代后得到与精确解相比,该结果相当糟糕究其原因,在求行乘数时用了很小的数0.0001作除数主元),(baa121000100. 011 0001. 021m00.1200.1011如果在求解时将1,2行交换,即0.999900. 1,

8、00. 121xx回代后得到这是一个相当不错的结果),(baa 例2.解线性方程组(用8位十进制尾数的浮点数计算)321643. 5072. 12623. 4712. 3132103218xxx解:这个方程组和例1一样,若用gauss消去法计算会有小数作除数的现象,若采用换行的技巧,则可避免321643. 5072. 12623. 4712. 3132108行交换因此的列元素为绝对值最大很小3 , 1,2,10138a 31rr1233210623. 4712. 31643. 5072. 12883121105 . 05 . 0mm101 . 05 . 03103 . 0102 . 00101

9、8015. 0103176. 00643. 5072. 12绝对值最大不需换行92722629. 032m54138685. 05 . 031041555186. 0001018015. 0103176. 00643. 5072. 12),()1()1(ba),()2()2(ba),()3()3(ba)3()3(3333abx 经过回代后可得)1(113)1(132)1(12)1(11axaxabx54138685. 01041555186. 039257367. 0)2(223)2(23)2(22axabx103176. 01018015. 05 . 03x05088607. 0491058

10、20. 0事实上,方程组的准确解为tx)367257384. 0 ,050886075. 0,491058227. 0(*例例2所用的方法是在所用的方法是在gauss消去法的基消去法的基础上础上,利用换行避免小主元作除数利用换行避免小主元作除数,该该方法称为方法称为gauss列主元消去法列主元消去法iiijjijiilxlbx11nnnnnnaaaaaaaaaa212222111211bax ni, 3 ,2第二章 解线性方程组的直接法 2.4 平方根法平方根法 2.4 平方根法平方根法一、对称正定矩阵的三角分解(cholesky分解)det0,1,2,kaakn 且且 的的顺顺序序主主子子式

11、式为对称正定矩阵阶矩阵若anaaat,0)det(则)(分解或分解可以进行因此doolittlelua记为ula为上三角阵为单位下三角阵其中ul,-(1)kkkulakadetkiiiu11kkuldetdetnk,2 , 10kadetkkkiiiuu11kkkuadet1kku1detdetkkaa0)1det(0a记kkkulakula,阶顺序主子式的任意且对于nk,2 , 1以上nnnnnuuuuuuuuuuu333223221131211nnuuuu33221111111,1,1222222311111131112nnnnnnuuuuuuuuuuuu1 du因此),(2211nnuu

12、udiagd1duu 12121uddula12121uddl22211),(nnuuudiagdiagonal:对角)(12121uddllu 21dll 为非奇异下三角阵121udu 为非奇异上三角阵并且都是正数的主对角元，为的主对角元和且21dul-(2)-(3)唯一由于ula唯一12121uddla 唯一lua aaat,为对称正定阵而ttlua)(因此ttlulu所以ttluul,综合以上分析,为对称正定矩阵阶矩阵若an则有tlla -(4)-(5)定理1. (cholesky分解),al设为 对 称 正 定 矩 阵 则 一 定 存 在 一 个 主对 角 元 全 是 正 数 的 下

13、三 角 阵使 得tlla 且该分解式唯一这种关于对称正定矩阵的分解称为cholesky分解nnnrnrrrlllllll1111nnnrnrnrrrnraaaaaaaaaa111111设jiijaa irararl列元素的第考察列已求出的第假设,11nnnrnrrrllllll1111nnnrnrnrrrnraaaaaaaaa111111nnnrrrnrllllll1111111111lla112121lla1111llaiini,2 , 1可以求出的第一列元素1illrkrkrkrrlla12112rrrkrkllrkrkikirlla1rrirrkrkikllll11nrri, 1,-(6

14、)-(7)-(8)的元素的计算公式式可得由l)8()6(1111al1111laliini,3 ,2112rkrkrrrrlalnr,2 rrrkrkikirirlllal11nri, 1 二、对称正定线性方程组的解法bax 线性方程组阶对称正定矩阵为其中na使得的下三角阵则存在主对角元为正数,ltlla -(10)-(11)则线性方程组(10)可化为两个三角形方程组bly yxltbxllt)(-(12)-(13)bly 解. 1nnniniiilllllll11111111lby iiikkikiilylby11ni, 3 ,2-(14)yxlt解. 2nnniiinitlllllll11

15、11nnnnlyx iinikkkiiilxlyx1-(15)对称正定方程组的平方根法1 ,2 , 1 ni例1.用平方根法解对称正定方程组91096858137576321xxx解:a先分解系数矩阵6858137576a667651111la1111iiall121rrrrrrkklal11ririkrkkirrralllltll 分解296131742529lbly 其次解6676591091111lby 692212122lylby62969*71017433321333lylbykkk29101111lby iiikkikiilylby11296131742529( , )l b 即t

16、yyyy),(321t)2910,1743,69(yxlt最后解291017436929251741362965676nnnnlyx iinikkkiiilxlyx13333lyx 1132111lxlyxkkk22233222lxlyx11(, )tly txxxx),(321所以原方程组的解为t)2 , 1, 1(思考本例中出现了大量的根式运算),(2211nnuuudiagd2121dd),(2211nnuuudiagd原因为分解的因此不作tllaula考虑改变分解方式1dulldutldl?分解矩阵的这种分解称为对称正定tldl请求解例1.三、平方根法的数值稳定性用平方根法求解对称正定

17、方程组时不需选取主元tlla 由可知rkrkrkrrlla1rkrkl12因此rrrkal2|不会放大得以控制中间量,rklnr,2 , 1rk,2 , 1平方根法是数值稳定的iiijjijiilxlbx11nnnnnnaaaaaaaaaa212222111211bax ni, 3 ,2第二章 解线性方程组的直接法 2.5 追赶法追赶法 2.5 追赶法追赶法对角占优矩阵:满足若矩阵nnijaa)(nijjijiiaa1|ni,2 , 1.为严格对角占优矩阵则称a满足若矩阵nnijaa)(nijjijiiaa1|ni,2 , 1.为弱对角占优矩阵则称a有一类方程组,在今后要学习的插值问题和边值问

18、题中有着重要的作用,即三对角线方程组,其形式为:nnnnnbacbacbacba11122211nxxxx21fax 其中nffff21,a称为三对角线矩阵-(1)以下以doolittle分解导出三对角线性方程组的解法设lua nnnnnbacbacbacba11122211111132nllllnnnucucucuu112211二对角阵11rkkjrkrjrjulaurrrkkrikiriruulal11ju1ja11111ualii11bu 1iiiual1iiiiclbuni,2 lu可得 和 的元素的计算公式可得 和 的元素的计算公式fly 解)1(nnfffflll321321111),(fl11fy 1iiiiylfyni,3 ,2得方程组可化为求解两个三角形解三对角线方程组fax fly yux yux 解)2(nnnucucucu112211nxxx21nyyy21nnnuyx iiiiiuxcyx11 ,2 , 1 ni得例1.用追赶法解三对角线性方程组010131132132134321xxxx解:11bu 1iiiual1iiiiclbu11fy 1iiiiylfytaaaa),(432设t)1 ,2 ,2(tbbbbb),(4321t)3 , 3 , 3 , 3(tfffff),(4321t)0 , 1 ,0 , 1(tccc