第4节 追赶法.ppt

§4、解三对角方程组的追赶法 小结、三角分解方法的优点 第五章 总 结 * 追赶法是专门用于求解三对角方程组的。这类方程组经常出现于用差分方法或有限元方法求解二阶常微分方程边值问题、热传导问题及三次样条函数插值等问题，三对角方程组Ax＝b的系数矩阵具有如下形式： 设A为一个三对角矩阵，那么它的顺序主子式均不为零的一个充分条件是： 在此条件下，可对A进行三角分解，设 比较矩阵的对应元素，根据矩阵乘法规则，可得到 即对角占优 i-1列 i 行 第3列 i-1列 i -1行 第3列 i-1列 第3列 i -1行 i-1列 于是，由以上结果： 分别得到： 也就是说,用这一组公式可以对三对角矩阵进行三角分解： 　　对于三对角方程组Ax＝b，设A的三角分解为A＝LU，则原方程组等价于 Ly＝b，Ux＝y 由Ly＝b，即 解得 解得 由Ux＝y，即 于是，对于三对角矩阵方程组 Ax=b，如下的两组公式便构成了构成了解三对角方程组的追赶法： 例5-7 用追赶法求解三对角方程组 解 : 首先进行系数矩阵的三角分解 求解方程组Ly＝y，即 得 到 y1＝1/2，y2＝1/3，y3＝1/4，y4＝1 再求解方程组 Ux＝y，即 得 到 x1＝1，x2＝1，x3＝1，x4＝1 当三对角矩阵A满足对角占优条件时，追赶法是数值稳定的。 追赶法具有计算程序简单，存贮少，计算量小的优点。 解三对角方程组Ax＝b的追赶法，用四个一维数组存放方程组数据 { ai，bi， ci， di } , di——常数项。 输入 方程组数据 {ai， bi， ci，di，n} 输出 计算解x＝（x1，x2，…，xn）T 根据以下算法编写程序 1． 2 对于i＝1，2，…，n－1，计算 3 4 5 输出 x1，x2，…，xn 此时，在完成并存贮矩阵L和U后，右端项第改变一次仅需增加 n2 次运算。 1. 当需要求解具有同系数矩阵的一系列方程组 Ax＝bi，i＝1，2，…，m 时，可大节省计算量。 U y =bi L x =y i=1, 2, … ,m 首先对系数矩阵作三角分解 A＝LU，再求解方程组化为： 2. 可以用以求可逆矩阵 A 的逆矩阵 A－1 推得 A Xk＝ e k ，k＝1，2，… ，n 令 A-1 = ( X1 X2 … Xn ), E=(e1 e2 … en ) A( X1 X2 … Xn )= (e1 e2 … en ) 则由 AA-1=E 得到 如果 A=LU, 则有 UYk＝ e k L Xk＝ Y k k＝1，2，… ，n 解出 Xk ，k＝1，2，… ，n，便可求得逆矩阵 3. 可以用以求矩阵 A 的行列式 如果对矩阵 A 作了三角分解 A=LU： 则可以求得行列式的值为 1. 解线性方程组Gauss消去法的计算程序如何实现？可以进行Gauss消去法的条件是什么？ 2. 解线性方程组列主元Gauss消去法的计算程序如何实现？可以进行列主元Gauss消去法的条件是什么？ 3. 解线性方程组的Doolittle三角分解法如何进行?可以进分解的条件是什么？ 4. 解对称正定矩阵方程组的平方根 (Cholesky) 解法如何进行? 5. 如何实现解三对角矩阵方程组的追赶法的计算程序? 如何用该算法进行三次样条函数的构造？ *