解三对角线性方程组的追赶法-《数值计算方法（第3版）》

在一些实际问题中，如用三次样条函数的插值问题，解常微分方程边值问题等，最后都导出解三对角线性方程组Ax ＝f，即

其中，A 满足条件：当｜i－j｜＞1 时，aij ＝0，且

①｜b1 ｜＞｜c1 ｜＞0

③｜bn ｜＞｜an ｜＞0

对于具有条件（7.17）的方程组Ax ＝f，我们介绍下述的追赶法求解。 追赶法具有计算量少，方法简单，算法稳定等特点。

定理7.4　设有三对角线性方程组Ax ＝f，且A 满足条件（7.17），则A 为非奇异矩阵。

证　用归纳法证明。 显然，当n ＝2 时有

现设定理对n－1 阶满足条件（7.17）的三对角阵成立，求证对满足条件（7.17）的n 阶三对角阵定理亦成立。 由b1≠0 和消去法，有

显然，det（A）＝b1det（B），其中

且有

于是，由归纳法假定有det（B）≠0，故det（A）≠0。

定理7.5　设Ax ＝f，其中A 为满足条件（7.17）的三对角阵，则A 的所有顺序主子式都不为零，即det（Ak）≠0（k ＝1，2，…，n）。

证　由于A 是满足条件（7.17）的n 阶三对角阵，因此，A 的任一个顺序主子式矩阵Ak 是满足条件（7.17）的k 阶三对角阵，由定理7.4 知det（Ak）≠0（k ＝1，2，…，n）。(www.xing528.com)

根据定理7.5，可用矩阵的三角分解法求解方程组（7.16）。 于是当系数矩阵A 满足条件（7.17）时，由定理7.2 知，可以证明A 存在唯一的杜利特尔分解。 设

由矩阵乘法，可得计算待定系数｛ui｝，｛li｝，｛ri｝的计算公式，即根据矩阵乘法规则，比较上式两端得

如果ui≠0（i＝1，2，…，n－1），则解得

即

当矩阵A 按式（7.18）进行三角分解后，求解方程组Ax ＝f（7.16）等价于求解两个三角形方程组：

1）Ly ＝f，求y；　2）Ux ＝y，求x。于是，得到解（7.16）的追赶法公式：

①计算｛ui｝，｛li｝的递推公式

②求解Ly ＝f 的递推公式

③求解Ux ＝y 的递推公式

将计算待定系数l2→l3→…→ln 和u2→u3→…→un，以及方程组的解y1→y2→…→yn 的过程称为追的过程；计算方程组的解xn→xn－1→…x2→x1 的过程称为赶的过程。

追赶法公式实际上就是把高斯消去法用到求解Ax ＝f 方程组（7.16）上去的结果。 由于A特别简单，使得求解的计算量比较小。

例7.5　用追赶法解方程组