第五章方程组-矩阵三角分解3

1、基本的三角分解法(Doolittle法),0)(knnijDaAn的顺序主子式阶方阵若nk,,2,1即存在且唯一分解的则由上节可知,,LUALUAnnnknknkkknkaaaaaaaaaA11111111111nknkmmm)()()()1(1)1(1)1(11nnnkknkkknkaaaaaaLU1．直接三角分解法第3节矩阵三角分解法11111nrnrlllnnrnrrnruuuuuu1111nnnrnrnrrrnraaaaaaaaaA111111上式可记为为的第一行元素根据矩阵的乘法原理jaA1,njuajj,,2,111为素行元素主对角线以右元的第),,(nrjarArjrkkjrkrjula1nr,,2,1nrj,,11111,1nrnrlllnnrnrrnruuuuuu1111nnnrnrnrrrnraaaaaaaaaA111111同样,由为素列元素主对角线以下元的第可知),,1(nriarAirrkkrikirula11,,2,1nrnri,,11111,1,ularii时显然ni,,3,2综合以上分析,有njuajj,,2,111rkkjrkrjula1nr,,2,1nrj,,rkkrikirula11,,2,1nrnri,,11111ulaiini,,3,2因此可以推导出ju1ja1nj,,2,1U的第一行1111ualiini,,3,2L的第一列rjrkkjrkrjuula111rrirrkkrikirulula11------(1)------(2)11rkkjrkrjrjulaunr,,2,1nrj,,U的第r行rrrkkrikiriruulal111,,2,1nrnri,,1L的第r列------(3)------(4)称上述(1)~(4)式所表示的分解过程为Doolittle分解.)4(~)1(,,,式的表达式请找出类似于解分则称之为表示为单位上三角阵角阵表示为下三中的为上三角阵，如果将为单位下三角阵中分解的CroutULLUAULLUADoolittleA思考对于线性方程组bAx系数矩阵非奇异,经过Doolittle分解后LUA线性方程组可化为下面两个三角形方程组bLyyUx为中间未知量向量y1111321323121nnnllllllLnnnnnnnnuuuuuuuuuuU,11,1,22322,1131211:,的解不难得到的知识由第一节三角形方程组bLy11by11rjjrjrrylbynr,,3,212122ylby的解的解便得到因此再由bAxyUxnnnnuyxrrnrjjrjrruxuyx11,2,,2,1nnr1111321323121nnnllllllLnnnnnnnnuuuuuuuuuu,11,1,22322,1131211ju1ja11111ualii上述解线性方程组的方法称为直接三角分解法的Doolittle法例.用Doolittle法解方程组1391444321131243301024321xxxx72510解:由Doolittle分解14131211uuuu30102Tlll4131211T25.05.112423220uuu5.812110Tll423210T11/611/310343300uu11/211/300Tl43100T910044000u4000得解,bLyTyyyy4321T1611/17201011rkkjrkrjrjulaurrrkkrikiriruulal1111rjjrjrrylby11by得解,yUxTxxxx4321T4321nnnnuyxrrnrjjrjrruxuyx1Doolittle法在计算机上实现是比较容易的但如果按上述流程运算仍需要较大的存储空间:都需要单独的存储空间yULxbA,,,,,式可知的计算过程而从)4(~)1(,ijijul的存储位置即不再需要后的第一行求出)1(11jauUjj的存储位置即不再需要后的第一列求出)2(11ialLii的存储位置即不再需要后行的第求出)(rjaurUrjrj的存储位置即不再需要后列的第求出)1(rialrLirir因此可按下列方法存储数据:nrrjuarjrj,,2,1),(1,,2,1),1(nrrilairir有如下特点：时解三角形方程组同样,,bLy的存储位置即不再需要后求出11by的存储位置即不再需要后求出)2(ibyiiniybii,,2,1,空出的存储位置的存储可以使用因此)1(ibyii直接三角分解的Doolittle法可以用以下过程表示:432144434241343332312423222114131211bbbbaaaaaaaaaaaaaaaa4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaa存储单元(位置)4321444342413433323124232221141312111bbbyaaalaaalaaaluuuur4321444342413433323124232221141312112bbyyaallaalluuuluuuur4321444342413433323124232221141312113byyyallluulluuuluuuur4321444342413433323124232221141312114yyyyullluulluuuluuuuryUL,,可知从上式最后一个矩阵中yUx然后解线性方程组紧凑格式的Doolittle法例.用紧凑格式的Doolittle法解方程组(例1)解:4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaaA7251013914443211312433010272510139142432211312423301021rju1ja11111ualii11rkkjrkrjrjulaurrrkkrikiriruulal1111by11rjjrjrrylby72201013911624311321217121123301022r11rkkjrkrjrjulaurrrkkrikiriruulal11711172010139116211211311321217121123301023r11rjjrjrrylby11by161117201049116211211311321217121123301024rLxU43214911621121131132121712112330102yUx解4321xxxxx4321所以y2、列主元Doolittle分解11rkkjrkrjrjulaurrrkkrikiriruulal11在Doolittle法(包括紧凑格式)中,会反复用到公式)(rrrrraGaussu法的顺序主元相当于显然法的顺序主元为仍然称Doolittleurr仍有可能为小主元做除数为此,我们也要考虑在算法中加入选取列主元我们下面介绍紧凑格式的Doolittle列主元法然后分解并进行换行者作为最大将,,||111uai4535251544434241343332312423222114131211aaaaaaaaaaaaaaaaaaaa432144434241343332312423222114131211bbbyaaalaaalaaaluuuu432144434241343332312423222114131211bbyyaallaalluuuluuuu大作主元不一定绝对值最由于12212222ulau4,3,2,1212iSulaiii因此比较然后分解最大的行与第二行交换将,)4,3,2(||iSi分解换行,符号因换行只代表存储位置,与原数值可能有差异依此类推列主元Doolittle法步骤:第一步:||max||,111iniiiiSSaS设比较公式分解然后按行交换将第一行与第Doolittlei,1||max||,11inirirkkrikiriSSulaSr设比较公式分解然后按行交换行与第将第Doolittleirr,:步第r:步第n而直接分解故不需选主元因为只有,,11nkknnknnnulaSrrrSu则rriiruSl也交换与同时rirSS例.用列主元Doolittle法解线性方程组141294642311321xxx解:141294642311*4211321SSSr31rr141311642294分解141314164212944521232SSr32rr41164213141294rirrSurriiruSl分解4431652212545412943r分解51643145221254541294yyUx解回代54151245221254541294x321xxxx541512所以原方程组的解为思考试用列主元Doolittle法解矩阵方程BAXnnnnnnaaaaaaaaaA212222111211nmnnmmxxxxxxxxxX212222111211