解三基于交线方程组的追赶法.pptVIP

§7 解三对交线方程组的追赶法 三对角线 方程组 优点： 1. 计算量小（仅5n-4次乘除法运算）. 本节介绍该类方程组中的特例及该种方程组的解法：追赶法. 三次样条插值问题中得到的三转弯方程组(8.9)、(8.10)、(8.11)及三弯矩方程组(8.19)或(8.20) 用差分法解二阶线性常微分方程边值问题，若用三点插值格式得到的方程组 解法： 追赶法 2. 方法简单，存贮量小. 3. 数值稳定（对舍入误差来说）. 一、理论基础 三对角线方程组的一般形式 若A满足条件： 称为对角占优矩阵. 以下研究在（7.2）成立的条件下（7.1）的解法. §7 解三对交线方程组的追赶法 证明 由高斯消去法 定理15 奇异矩阵. 满足(7.2)的方程组(7.1) 的系数矩阵A为非 用归纳法证明， 对 时有 为满足(7.2)的三对角阵，则 假设定理对 成立，下证对n定理亦成立. 则由归纳法假设 定理16 证明 B为n-1阶三对角阵且满足 (7.2): 即A为非奇异矩阵. 其中A为满足（7.2）的三对角阵，则A的 所有顺序主子式都不为零，即 主子阵Ak亦是满足（7. 2）的k阶三对角阵，由定理15，则有 由A是满足（7. 2）的n阶三对角阵，因此A的任一个顺序 B 二、追赶法 设A为满足(7.2) 的n阶三对角阵 ， A=LU —杜里特尔分解 L′为下三角阵，U为单位上三角阵. A=L′U—Cront分解 A=LDR (一般三角分解) (追赶分解法) (平方根法) 即有 则有唯一三角分解A=L′U. 由矩阵乘法 ， 得 解（7.1）的追赶法计算公式 （1）分解计算公式( ) （2）求解 逆推公式 （3）求解 逆推公式 1次 1次 n-1次 计算次数 2(n-2)次 3(n-1)次 1.将计算 的过程称为 2.乘除法的次数：6n-6次. 说明 追的过程，计算方程组解 过程称为赶的过程. 若令 ，则计算量为 (6n-6)-(n-2)次，即5n-4次, 计算量小,但增加了计算机的内存，两者各有利弊.这实际上也是 但此时需贮存 ，尽管 衡量一种计算方法好坏的标准：两者兼顾. 设有三对角线方程组 ，其中A满足（7.2）式， (1)要证 , 只要证 , 而此式中含有 定理17 则由追赶法计算公式得到 满足： 分析 ，因此可用归纳法证明. (2)、(3) 用三角不等式即可得证. 证明 事实上， 三、数值稳定性 由定理17说明追赶法计算公式中不会出现中间结果数量 说明 级巨大增长和相应的舍入误差的严重累积，即追赶法计算公式对 于舍入误差是稳定的. 1. 计算量小，仅5n-4次乘除法运算； 优点 2. 数值稳定. 只需用3个一维数组分别存贮A的3条线元素 ， 上述定理有条件 如果有某 存贮方法 此外还需要用两组工作单元保存{ }，{ }或{ }. 特例 则3对角线方程组 可化分为两个低阶方程组，例：以四阶 方阵A为例， 于是，解 化为解两个方程组： 注 实际上，条件（7.2）是充分的，但并非完全必要，三对 角线上不能有零元素，条件太苛刻，条件可以作适当改变，使追 赶法还可行 . 即具有严格对角优势的三对角线方程组均可用追赶法 . 理解解三对角线方程组的解法.