皮带传动效率:解线性方程组的杜里特尔分解法的实验的实验报告

2.2 三角分解法
2.2.1 杜里特尔分解法
求解线性代数议程组的三角分解法,起源于高斯消去法的矩阵形式.
高斯消去法消去过程中,将变换后增广矩阵的第k行-c倍加于第i行,相当于左乘初等矩陈
它们都是单位下三角矩阵,即对角元全为1,对角线上方元素全为零的矩阵.因此不选主元的高斯消去法消去过程,实质是增广矩陈 被左乘一系列倍加矩阵,变成上三角形矩阵 ,即
此式称为高斯消去法的矩阵形式.由此显然
注意
是将单位矩阵 的第
行倍数加于第 行, ,将第一行的倍数加于第 行, ,
第二行,可见 是单位下三角矩阵.故
这说明,高斯消去法的消去过程,实质上是把系数矩阵 分解为
单位下三角矩阵 与上三角矩阵 的乘积,并且求解议程组
的过程.回代过程就是求解上三角形方程组
矩阵 和 也可直接算出.事实上,比较等式 两
边等 行,第 列元素可知
注意 是单位下三角矩阵, 便知
从而
同样,因 为上三角阵, 知
可见
公式(2-2)和(2-3)就是计算 和 各元素的计算公式.
实际计算时 的对角元 不必存放, 和 中
肯定为零的元素也不必存放,因此 的 可共同存放在增广
矩阵 的位置:
此时公式(2-2),(2-3)表明, 或 都是原始矩阵 对
应元素,减去同行左边 的元素与同列上边 的元素乘积;只是对 的元素,然后需除以 的对角元.计算顺序,通常先算 的第 行,再算 的第 列;也可先算 的第 列,再算 的第 行, 如图2—1所示:
图2—1 计算顺序
例2—1 分解 ,并解方程组 ,其中
解 按计算公式(2-2)和(2-3)
详细计算过程如下(下文不再写出):
从而
回代(解方程组 ),得
分解 且 为单位下三角阵, 为上三角阵,称为杜里
特尔Dolittlse)分解.利用杜里特尔分解求解方程组 或 ,
相当于解两个三角形方程组
解下三角方程组 可以在分解 时同时完成(如例2—1),
也可独立完成.这是因为,把 写成分量形式,就是
由此可见,
用杜里特尔分解求解方程组(2-1),所需乘除次数与高斯消
去法完全一样.其中分解 需 次,解 需
次,解 需 次,共计 次.
它们都是单位下三角矩阵,即对角全为1,对角线上方元素全为零的矩阵.因此不选主元的高斯消去过程,实质是增广矩阵 被左乘一系列倍加矩阵,变成上三角形矩阵 ,即
此式称为高斯消去法的矩阵形式.由此显然
注意 是将单位矩阵
三角分解法常用于求解系数矩阵都是 的若干方程式组
这是因为,一旦完成分解 ,只需再解 个三角形方程组
解这种三角形方程组每组只需 次乘除法,远比重复使用高斯消
去法节省工作量.
为保证三角分解顺序,稳定进行,与高斯消去法一样,也可选
主元.常用列主元法.
2.2.2 克洛特分解法
当矩阵 可作杜里特尔分解 时,令 为 对角元构
成的对角阵
则
再算第 行;或者先算第 行,再算第 列, 如图
2—2所示.克洛特分解法的用法及运算量与杜里特尔分解法相同.
例2—2 用克洛特分解法求解方程组
解
得
解 ,得解 .解毕.
为保证克洛特分解法顺利,稳定进行,也可采用列主元法.求解
步骤如下:
对 做
计算结束时 的第 列就是解
注意:例2—2中系数矩阵对称: ,此时 就是 各列除
以对角元所得矩阵的转置矩阵.一般来说 对称且可作克洛
特分解 ,记 的对角元构成的对角阵为 , 各列除以对角元构成的单位下三角矩阵为 ,则
可见 , ,说明 都是 各列除以对角元所得矩阵的
转置矩阵;说明对称矩阵 可分解为 或 .因此 可
由 直接求出,而不必再按公式(2—4)第二式重复计算.这样分解
可以节省 次乘法,即节约大约一半的运算量.
也可不存储.
2.2.3 追赶法
追赶法适于求解对角方程组 ,这里
其实质是高斯消去法,三角分解法的应用.事实上,将 作克特分解
则易知
回代得
.
按照这些公式次数求解 的方法就称追赶法,其中算 称追,回代称赶,共需乘除法次数为 ,远比一般方程组的高斯消去法或三角分解法节省运算量.实际问题提出的三对角方程组往往严格对角占优,因此不用选主元,就可保证顺利,稳定进行.
2.2.4 平方根法
平方根法适于求解 对称正定的方程组 .此时 的各
阶顺序主子式 ,保证了主元大于零,保证了 可作克特分解
而且 的对角元 (也就是主元)全为正数.所以令
,则
再记 为 ,则上式表明.对称正定矩阵 可分解为 ,
即下三角矩阵及其转置矩阵的乘积,利用比较法可得 元素计算公式:
利用这种分解方程组 称为平方根法或乔列斯基(cholesky)分解法.
跟前种分解法一样,求解下三角方程组 可在分解 的同时进行.
例2—3 用平方根法求解例2—2方程组.
解
故知
解
解毕
平方根法求解方程组 ,需做 次乘除法和
次开方,比考虑到 对称的克洛特分解法节省 次乘除法但增加
次开方.为避免开主,有人提出了改进平方根法,不过它其实就是
考虑到 对称的克洛特分解法,如2.2.2节最后一段所述.