实验一 解线性方程组的直接方法
1 实验目的
① 掌握列主元高斯消去法的基本思路和步骤;
② 掌握用 LU 分解法和 Cholskey 分解法求解线性方程组;
③ 培养编程与上机调试能力?
④ 能用线性方程求解实际问题.
2 实验内容
2.1 高斯列主元素消去法
设有方程组 Ax b = ,设 A 是可逆矩阵。高斯消去法的基本思想就是将矩阵的初等行变 换作用于方程组的增广矩阵 [ ] B A b = M ,将其中的A 变换成一个上三角矩阵,然后求解这个 三角形方程组. 为避免小主元做除数,在高斯消去法中加入选列主元过程,便成为高斯列主 元素消去法.
算法:
1. 输入 n 阶系数矩阵和右端项并形成增广矩阵 A, 控制精度 EPS?
2. 消元过程:
for k=1,2,…n-1
2.1 求m 使 |} {| max | | ik n
i k mk a a £ £ = ? 2.2 if k m 1 , then 交换 k 行和 m 行?
2.3 if EPS a kk £ |
| , then 输出 Gauss 消去法失败的信息, 停止计算? 2.4 for i=k+1,k+2,…,n do
2.4.1 :/ = ik ik kk a a a ?
2.4.2 for j=k+1,k+2,…n+1 do
: ij ij ik kj a a a a =- ?
3. 回代过程(解上三角方程组):
3.1 if EPS a nn £ |
| , then 输出 det(A)=0 的信息, 停止计算? 3.2 ,1 :/ n n n nn x a a + = ?
3.3 for i=n-1,n-1,…,1 do
置 ,1 1 :()/ n
i i n ij j ii j i x a a x a + =+ =-
? ; 4. 输出解 x .
2.2 LU(Doolittle)分解法
设矩阵 n n ij a A ′ = ) ( 的各阶顺序主子式均不为零,则A 可惟一分解为
LU
A = 其中 L 为单位下三角矩阵,U 为上三角矩阵,从而可通过求解 b Ly = 及 y Ux = 得到 b Ax = 的解.
算法:
1. 输入 n 阶系数矩阵和右端项形成增广矩阵 A, 控制精度 EPS?
2. for r =1,2,…,n do
2.1 计算U 的第r 行元素
for i=r,r+1,…,n+1 do
1
1 : - = =- ? r ri ri rk ki k a a a a ;
2.2 如果 EPS a rr £ |
| , 则输出 A 分解失败信息, 停止计算? 2.3 如果 r≠n, 则计算L 的第r 列元素:
for i= r+1, r+2,…,n do
1
1 :() r ir ir ik kr rr k a a a a a - = =- ? ?
3. 解方程 Ux = y :
3.1 ,1, :/ n n n n n
x a a + = 3.2 for k = n-1,n-2,…,1 do
,1 1 :()/ n
k k n ki i kk
i k x a a x a + =+ =- ? (这里规定 0 0 1 = ?= k ki rk a
a )
2.3 平方根(Choleskey 分解)法
设矩阵 n n ij a A ′ = ) ( 对称正定,则A 可惟一分解为
T LL
A = 其中L 为具有正对角元素的下三角矩阵, 从而可通过求解 b Ly = 及 y x L T
= 得到 b Ax = 的 解.
算法:
1. 输入 n 阶系数矩阵 A, 右端项 b?
2. 作 A 的 Cholesky 分解:
for j=1,2,…n do
2.1 如果 j>1
则 for i= j,j+1,j+2,…,n do
1
1 : j ij ij ik jk
k a a a a - = =-× ? 2.2 : jj jj
a a = 2.3 for i= j+1, j+2,…,n do
:/ ij ij jj
a a a = 3. 解 Ly=b:
3.1 1111 :/ y b a
= 3.2 for i=2,3,…,n do
1
1 :()/ i i i ik k ii k y b a y a
- = =- ? 4. 解 L T x = y:
4.1 :/ n n nn x y a
= 4.2 for i=n-1,n-1,…,1 do
1 :()/ n
i i ki k ii k i x y a x a
=+ =- ? 3. 实验任务
1.分别用列主元 Gauss 消去法、Doolittle 分解法解方程组
1234 1234 1234 1234 42212 2105224 25940 4241442
x x x x x x x x x x x x
x x x x +-+= ì ? +++= ? í
-++-= ? ? +-+= ? 2.一个油漆公司将一些不受欢迎的油漆颜色加以混合, 得到受欢迎的油漆颜色,每种 油漆都含四种基本的色素。下表列出了四种不受欢迎的油漆颜色的组成: 色素成分 油漆编号
A B C D 1
80 0 16 4 2
0 80 20 0 3
30 10 60 0 4 10 10 72 8
期望得到的颜色是 40%的色素 A ,27%的色素 B ,31%的色素 C 和 2%的色素 D ,要得到一 加仑这种颜色的油漆,需要表中四种颜料各多少
3. 用 Gauss 列主元素消去法或其他方法求下列方程组的解
(1) 1 2 3 4 1078732 756523 8610933 7
591031 x x x x éù éùéù êú êúêú êú êúêú = êú êúêú êú êúêú ???? ?? (2) 1 2 3 4 1078
732.1 756522.9 8610933.1 7591030.9 x x x x éù éùéù êú êúêú êú êúêú = êú êúêú êú êúêú ???? ?? (3) 1 2 3 4 10.007.008.107.2032 7.08 5.04 6.00 5.0023 8.00 5.989.899.0033 6.99
4.999.009.9831 x x x x éù éùéù ê
ú êúêú êú êúêú = êú êúêú êú êúêú ???? ?? 比较计算结果, 你有哪些启示?
4. 分别用Doolittle 和 Cholesky 分解法求解方程组 Ax b = ,其中
1142310 150812 , 404582468 2881848 3124439114 A b -- éùéù êúêú --- êúêú êúêú == êúêú -êúêú êúêú - ???? .