?
线性代数方程：
? 设线性代数方程组具有如下特征：
?? 算法框架
(1)设置线性代数方程组的初值X=(x1，…，xn-1 ，xn)；
(2)构造迭代方程xi=gi (X)? ?(i=1,…,n-1,n)及精度求解方法；
(3)达到迭代次数或精度结束迭代。
?
?【例3-8】求下列解线性方程组的解
?? 计算模型
?
?
| 算法设计与描述 | |
输入： | |
输出： | |
| Jacobi (x[],k) { ? ? ? ? i <- k; ? ? ? ? while (i) ? ? ? ? { ? ? ? ? ? ? ? ? x11 <- ( 20+3*x[2]-2*x[3])/8; ? ? ? ? ? ? ? ? x12?<- ( 33-4*x[1]-x[3])/11; ? ? ? ? ? ? ? ? x13?<- ( 36-6*x[1]-3*x[2])/12; ? ? ? ? ? ? ? ? x[1]?<- x11; x[2] <- x12 ;x[3] <- x13 ; ? ? ? ? ? ? ? ? i <- i-1 ; ? ? ? ? } ? ? ? ? output(x[]); } | 时间复杂度分析 由于计算模型已列出，ρ(B)=0.3592， R(B)=-lnρ(B)=1.02276，于是有 k≥(5ln10)/ 1.02276=11.2567， 则实际k可取12次可达到要求。 运行结果分析 Jacobi算法: k=12，结果: 2.999988 2.000008 1.000014 k=16，结果: 3.000000 2.000000 1.000000 Gauss_Seidel 算法: k=12， 结果: 3.000000 2.000000 1.000000 |
| Gauss_Seidel (x[],k) { ? ? ? ? i <- k; ? ? ? ? while ( i ) ? ? ? ? { ? ? ? ? ? ? ? ? x[1]?<- ( 20+3*x[2]-2*x[3])/8; ? ? ? ? ? ? ? ? x[2]?<- ( 33-4*x[1]-x[3])/11; ? ? ? ? ? ? ? ? x[3]?<- ( 36-6*x[1]-3*x[2])/12; ? ? ? ? ? ? ? ? i <- i-1 ; ? ? ? ? } ? ? ? ? output(x[]); } |