Question

三对角方程组的追赶法 用追赶法解方程组例题

Answer 1

2013-2014（1）专业课程实践论文

题目：三对角方程组的追赶法

一、算法理论

在一些实际问题中，例如解常微分方程边值问题，解热传导方程以及船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线方程组

⎛b 1c 1⎫⎛x 1⎫⎛

⎪⎪ a b c x 2 22⎪2⎪ ⎪ ⎪= ⎪⎪

a b c x n -1n -1n -1⎪n -1⎪

⎪⎪a n b n ⎭⎝x n ⎭ ⎝⎝

f 1⎫

⎪f 2⎪ ⎪， ⎪f n -1⎪f n ⎪⎭

简记为Ax =f 。

求解Ax =f ：等价于解两个三角形方程组

Ly =f , 求y ；Ux =y , 求x . 从而得到解三对角线方程组的追赶法公式：

(1)计算{βi }的递推公式

β1=c 1/b 1, βi =c i /(b i -a i βi ), i =2,3, , n -1; (2) 解Ly =f

y 1=f 1/b 1, y i =(f i -a i y i -1)/(b i -a i βi -1), i =2,3, , n ;

(3)解Ux =y

x n =y n , x i =y i -βi x i +1, i =n -1, n -2, 2,1.

我们将计算系数

β1→β2→ →βn -1及y 1→y 2→ →y n 的过程称为追的过程， 将计算方程组的解

x n →x n -1→ →x 1的过程称为赶的过程。

#include #include #include #define N 20

double a[N], b[N], c[N-1], f[N], r[N]; int n; int i;

void LUDecompose(); // LU分解 void backSubs(); // 回代 void main() {

printf("请输入方程的维数n ＝"); scanf("%d",&n); getchar(); if(n>N||n

printf("\n输入下三角元素\n"); printf("输入%d个a 值: ", n-1); for (i=1; i

printf("\n输入主对角线元素\n"); printf("输入%d个b 值: ", n); for (i=0; i

printf("\n输入上三角元素\n"); printf("输入%d个c 值: ", n-1); for (i=0; i

printf("\n输入%d个方程组右端项: \n", n); for (i=0; i

LUDecompose(); backSubs();

printf("\n线性方程组的解为: \n"); for (i=0; i

printf("x%d=%lf\n", i+1, f[i]); }

void LUDecompose(){ //α被b 取代, β被c 取代, 以节省存储空间 c[0]=c[0]/b[0]; for(i=1;i

r[i]=a[i];

b[i]=b[i]-r[i]*c[i-1]; }

void backSubs(){ // y被f 取代, x也被f 取代, 以节省存储空间 f[0]=f[0]/b[0]; for(i=1; i=0;i--) f[i]=f[i]-c[i]*f[i+1]; }

四、 算法实现

例1．用该程序计算三对角线方程组

00⎫⎛2－10⎛1⎫

⎪ ⎪－12－100 ⎪ 0⎪

A ＝ 0－12－10⎪， b = 0⎪计算其方程组的解。

⎪ ⎪00－12－1 ⎪ 0⎪ 0 0⎪00－12⎪⎝⎭⎝⎭

解：运行程序

（1） 显示出 请输入方程组的维数：n=5，回车。

（2） 显示出 请输入下三角元素 输入4个a 值：-1 -1 -1 -1，回车。 （3） 显示出 请输入主对角线元素 输入5个b 值：2 2 2 2 2 ，回车。 （4） 显示出 请输入上三角元素 输入4个c 值：-1 -1 -1 -1，回车。 （5） 显示出 请输入5个方程组右端顶：1 0 0 0 0，回车。

⎧0.833333⎪0.666667⎪⎪

其解为⎨0.500000

⎪0.333333⎪⎪⎩0.166667

上机运行截图

例2．用该程序计算三对角线方程组

⎛3 1A ＝ 0

0 0⎝

1000⎫⎛1⎫

⎪ ⎪

3100⎪ 1⎪

1310⎪， b = 0⎪计算其方程组的解。

⎪ ⎪

0131⎪ 0⎪

0⎪0013⎪⎭⎝⎭

解：运行程序

（1）显示出 请输入方程组的维数：n=5.，回车。

（2）显示出 请输入下三角元素 输入4个a 值：1 1 1 1，回车。 （3）显示出 请输入主对角线元素 输入5个b 值：3 3 3 3 3 ，回车。 （4）显示出 请输入上三角元素 输入4个c 值：1 1 1 1，回车。 （5）显示出 请输入5个方程组右端顶：1 1 0 0 0，回车。

⎧0.236111

⎪0.291667⎪⎪

其解为⎨-0.111111

⎪0.041167⎪⎪⎩-0.013889上机运行截图