计算方法44(精品·公开课件).pptVIP

4.4 特殊线性方程组的解法 4.4.1 解三对角方程组的追赶法 在三次样条插值问题和常微分方程边值问题的 数值方法中，都要求解对角占优的三对角线性方程 组 其中： 并且A满足 称A为对角占优的三对角线矩阵。 可以验证，(4.4.2)式中的A可以分解为二对角线的 下三角矩阵L和二对角的上三角阵U的乘积。当 L 的对 角线元素为1时，属于Doolittle分解。当U的对角 线 元 素为1时，属于Crout分解。以下对A作Crout分解. 令 对照(4.4.2)式中的A和(4.4.4)式中的L,U，利用矩阵的 乘法，得: 从(4.4.5)解出 可见，对A的分解只需求 且按 的递推过程进行，形象地称为“追”的过程 这样，解方程组(4.4.1)就化为求 令 则 。 解方程组 ，即 得： 解方程组 即 得 形象地称回代求解过程（4.4.8）为“赶”的过程， 由公式(4.4.6)（4.4.7）(4.4.8)求解方程组(4.4.1)的方 法称为追赶法。 不过，从计算 的公式(4.4.7)可以看出，只要算 出 和 就可以计算 ，所以可将计(4.4.7)归于“追” 的过程，即求L,U,Y可以组织在一个循环中，下图是追赶法的算法框图。 当系数矩阵A满足条件(4.4.3)时，用数学归纳法可 以证明 由于 有界，且 在数量级上与A的元素相 当，因此，即使不选主元，追赶法在一般情况下也是 数值稳定的。又因为 所以(4.4.1)的解存 在且惟一。 追赶法的计算量为5n-4次乘除法，可用4个 一 维 数组存放 。共占用4n-2个单元，在计算 过程中 依次覆盖掉 最后， 覆盖 掉 ，所以，追赶法具有计算量小，占用内 存 单元 少的特点。 4.4.2 解对称正定方程组的平方根法 利用有限元方法解结构力学问题时，最后归结为 求解一个线性代数方程组，其系数矩阵大多是对称正 定矩阵。所谓平方根法，就是利用系数矩阵具有对称 正定的性质，将直接三角分解法进行简化而得到的一 种有效方法. 设A是n阶实矩阵，所谓A是对称的，即 。所 谓A是正定矩阵，即对于任意n 维 非零 列 向 量 , 恒有 。对称矩阵A具有 许 多 性质，其中，一 个很重要的性质是：若A对称正定，则A的各阶顺序主 子式均大于零。 定理4.4.1 （乔立斯基（cholesky）分解定理） 若A是实对称正定矩阵，则存在非奇 异 的 下三角 阵L，使得 ，若限定L的主对角线元 素 取 正 值, 则这种分解是唯一的。 证明：设 将 直接利用矩阵乘法，得： 由上式可逐行求出矩阵L的元素 计算公式为 (4.4.9) 设 分别为A,L的k阶顺序主子式，则有 所以 由于A对称正定，则 故有 又 ，所以 全为非零 实数，因此(4.4.9)式的计算不会中断，如果限定 则按(4.4.9)式计算，可惟一地确定矩阵L。证毕。 由定理4.4.1对称正定方程组Ax=b可化为求解两个 三角形方程组 及 由 得： 由 得： 由于(4.4.9)式中含有开方运算，所以利用(4.4.9) (4.4.10) (4.4.11)解对称正定方程组的方法称为平方根 法。 平方根法的乘除法计算量为