数值线性代数课程设计

数值线性代数课程设计线性方程组的直接解法

数理学院 09405011班 0940501120 沈骁摘要：如何利用电子计算机来快速、有效的求解线性方程组的问题是数值线性代数的核心问题。本文将主要介绍解线性方程组的基本的直接法——高斯消去法，平方根法，并用实例来验证此方法的有效性。

关键字：高斯消去法，顺序消去法，选主元消去法，平方根法，消元过程，回代过程, 主元数和乘数

引言：因为各种各样的科学与工程问题往往最终都要归结为一个线性方程组的求解问题。本文在比较着几个方法的基础上，通过一道实例来得到最方便最有效的方法。

基本原理：工程计算和科学研究中的许多问题，最终归结为线性代数方程组的求解。求解的方法也有很多，如高斯消去法（顺序消去法，选主元消去法），平方根法。高斯消去法是目前求解中小规模线性方程组最常用的方法；平方根法是求解对称正定线性方程组最常用的方法之一。为了更快速、更方便的求解线性方程组，下面我们比较一下这几种方法哪种更好。

一、高斯（Causs ）消去法就是逐步消去变元的

系数，将原方程组A x =b 化为系数矩阵为三角形的等价方程组U x =d ，然后求解系数矩阵为三角形的方程组而得出原方程组解的方法。把逐步消元去变元的系数，将方程组化为以系数矩阵为三角形的等价方程组的过程称为小院过程；把求系数矩阵为三角形的方程组解的过程称为回代过程。最初求解方程组的高斯消去法也称为顺序消去法，它由消元过程和回代过程组成。顺序消去法 1．消元过程

考虑一般方程组，为了推导过程方便，记系数矩

阵A 的元素a (0)

ij 为a ij ，右端向量b 的元素b i 记为a (0)

i , n +1，于是方程组

⎧a 11x 1+a 12x 2+ +a 1n x n =b ⎪

1⎪a 21x 1+a 22x 2+ +a ⎨

2n x n =b 2

（1.1⎪

）成为⎪⎩a n 1x 1

+a n 2x 2+ +a nn x n =b

n ⎧⎪a (0)(0)+ +a (0)(0)

11x 1+a 12x 21n x n =a 1n +1⎪(0

)(0)(0⎨

a )a (0)21x 1+a 22x 2+ +a 2n x n =2n +1

假设⎪

⎪⎩a (0)(0)(0)(n 1x 1

+a n 2x 2+ +a 0)nn x n =a nn +1(0)

(0) 11

≠0，将第1个方程乘以(-

a i 1a

(0) ) 加到第i 个

方程(2≤i ≤n ) , 得到第1个导出方程组

⎧a (0) (0) (0) (0) ⎪11x 1+a 12x 2+ a 1n x n =a 1n +1⎪

⎨

a (1)(1)=a (1)

22x 2+ a 2n x n 2n +1其中：⎪

⎪⎩

a (1)+ a (1)(1)n 2x 2nn x n =a nn +1

(0) a

(1)(0) i 1

(0)

a a (0)

a 1j ，2≤i ≤n ，2≤j ≤n +1。

(0) 由于因子

a i 1

a (0)

不止一次地用到，常

记为l (1)

i ,1。再假设a 22≠0，由第1个导出方程组(1)的第2个方程乘以(-

a i 2

a (1)

) 加到第i 个方程

(3≤i ≤n ) ，得到第2个导出方程组

⎧⎪

a (0)+a (0)(0)+a (0)(0)11x 112x 2+a 13x 3+ 1n x n =a 1n +1⎪a (1)x (1)(1)(1)⎪222+a 23x 3+ +a 2n x n =a 2n +1⎨a (2)a (2)(2)⎪

33x 3+ +3n x n =a 3n +1类似⎪

⎪⎩

a (2)(2)n 3x 3+ +a nn x (2)n =a nn +1(1)地记：l a i 2

i 2=a (1)

，则第2个导出方程组的元素

(1)

a (0)

=a (1)

a (i 2) ij -

(1)a (1)(1)(1)

2j =a ij -l i 2a 2j ，3≤i ≤n ，

3≤j ≤n +1。重复上述过程n -1次，得到n -1个导出方程组

⎧⎪

a (0)+a (0)(0)(0)(0)11x 112x 2+a 13x 3+ +a 1n x n =a 1n +1⎪a (1)(1)+ +a (1)(1)⎪22x 2+a 23x 32n x n =a 2n +1⎨a (2)x (2)(2)⎪

333+ +a 3n x n =a 3n +1⎪

⎪⎩

a (n -1)(n nn x -1)n =a nn +1（1.2）其中第k 个导出方程组的元素的递推关

系是l a (k -1) ik

ik =

a (k -1)

，a (k )

-1)

=a (k ij

-l (k -1)

ik a kj

（1.3）

(1≤k ≤n -1, k +1≤i ≤n , k +1≤j ≤n +1) 。由

于上述消元过程只是将原方程组的系数矩阵和右端进行初等变换，因此，第n -1个导出方程组与原方程组等价，即通过消元过程将方程组（1.1）化成了等价的上三角方程组（1.2）。由第k 个导出方程组的计算公式（1.3），容易得到消元过程所需要的乘法和加法次数为

n -1

S n 2

11=

∑

(n -k )(n -k +1) =

k =1

(n -1) n -1

除法次数为S n (n -1) 12=∑(n -k ) =

k =1

2. 回代过程

回代过程就是求等价三角形方程组（1.2）的解。只要a (k -1)

≠0(k =1, 2, , n ) ，就可以最

后一个方程得到x n 的值，再从第n -1个方程得

x n -1的值。在一般情形，可求得x i 的回代递推公

式

⎧(n -⎪

x a 1)

nn +1

n =(n -1) , ⎪⎪a nn

⎨n (i -⎪

(x 1) i -∑a (i -1)

ij x j ) ⎪⎪x j =i +1

⎩

i =a i -1

, i =n -1, n -2, ,1. ii （1.4）由公式（1.4）可知，回代过程需要n 次除法，其乘法和加法的次数同为

1+2+ +(n -1) =1

n (n -1) 。所以回代过程

需S 11

21=2n (n -1) 次加法，S 22=2

n (n +1) 次

乘、除法。

3. 顺序消去法的运算次数与计算步骤

由消元过程和回代过程的运算次数可知，顺序消去法的加法次数为

S 1=S 11+S 21=

n (2n +3n -5) ，乘除法次数

为S 12

2=S 11+S 12+S 22=

(n +3n -1) 。消元过

程在编程上机运算时，需采用三重循环，即对于k =1, 2, , n -1, i =k +1, k +2, , n , 计算

l a (k -1) ik

kk =

a (k -1)

；对于j =k +1, k +2, , n +1计算kk

a (k )

=a (k -1)

-l ik a (k -1)

。回代过程只需要二重循

(n -1)

环，即计算x +1n =

a nn a

(n -1) ，对于

i =n -1, n -2, ,1, s =0; 对于j =i +1, i +2, , n , 计算S =S +a (i -1)

ij x j ,

x a (i -1)

in +1-S i =

a (i -1) .

4. 主元数和乘数

由顺序消去法的推导过程可知，无论是消元过程

还是回代过程的都不需要对未知元作真正的运算，

A x =b 的系数矩阵的元素和

而仅需要对方程组

右端作运算。因此，在实际运算中，总是将方程组的系数矩阵和右端合在一起，记成增广矩阵(A , b ) 。

由消元过程（1.3）可以看到，元素a (k -1)

kk 为“主

元素“，另外，在消元过程中不止一次用到数l ik ，这个数称为消元过程的乘数。二．平方根法

平方根法又叫Cholesky 分解法，是求解对称线性方程组最常用的方法之一。对于一般方阵，为了消除L U 分解的局限性和误差的过分积累，而采用了选主元的方法。但对于对称正定矩阵而言，选主元却是完全不必要的。

设A ∈R n ⨯n 是对称正定的，即A 满足A T =A 而且x T Ax >0对一切的非零向量x ∈R n

成立. 此时, 由定理容易推出 Cholesky分解定理：若

A ∈R n ⨯n

对称正定，则存在一个对角元均为正数的下三角阵L ∈R n ⨯n , 求得A =LL T . 上式中的L 称作A 的Cholesky 因子。

若线性方程组的系数矩阵是对称正定的，则我们自然可按如下的步骤求其解：（1）求A 的

Cholesky 分解：A =LL T ;(2)求解Ly =b 得y ；（3）求解L T

x =y 得x 。

实验：1. 用高斯（Causs ）消去法求解下面的84阶方程组⎡61⎤⎡x ⎢1⎤⎡7⎤

⎥⎢⎢861⎥⎢

x ⎥⎢⎥2⎥⎢15⎥⎢8

61⎥⎢x ⎢⎢3⎥⎢15⎥

⎥⎥⎢⎥⎢

⎥⎢

⎥=⎢ ⎥。 ⎢⎥⎢⎢8

61x 82⎥⎢⎢8

61⎥⎢

⎥⎢15⎥

⎥⎥⎢x 83⎥⎢15⎥⎢⎣

6⎥⎦⎢⎣x 84⎥⎦⎢⎣14⎥⎦

解：n =10 A =identity (n )

i =1 n A i , i =6 i =1 n -1 A i , i +1=1

i =2 n A i , i -1=8

b 1=7 i =2 n -1 b i =15 b n =14

M =lu (A )

P =subm atrix (M ,1, n ,1, n ) L =subm atrix (M ,1, n , n +1, 2n )

U =subm atrix (M ,1, n , 2⋅n +1, 3⋅n )

y =lsolve (L , P ⋅b ) x =lsolve (U , y )

⎛1

47⎫A = 2

5.92⎪ ⎪ ⎝

10⎪⎭

⎛1

00⎫

UI =Gauss 2(A ) (U I

1) = 2

10⎪ ⎪ ⎝32.381

1⎪⎭

⎛147

⎫U I 2= 0

-2.1-12⎪ ⎪

⎝

17.571⎪⎭

⎛1

⎫U =Gauss (A , b ) U =

-2.1-12⎪ ⎪

⎝

17.571⎪⎭M =GaussLU (A ) L =M 1 U =M 2

⎛100⎫⎛147

⎫

L = 2

10⎪ ⎪ U =

0-2.1-12⎪⎪

⎝

32.381

1⎪⎭ ⎝

17.571⎪⎭

⎛0

00⎫A -LU =

00⎪ ⎪ ⎝

0⎪⎭

2. 用你编写的程序求解对称求解对称正定方程组

A x =b ，其中b 随机的选取，系数矩阵为100⎡101⎤⎢⎥⎢1101⎥⎢1101⎥阶⎢ ⎥⎢⎥。 ⎢⎢1101⎥⎢1101⎥

⎥

⎢⎣110⎥⎦

i =1 n

A i , i =10解: n =5 i =1 n -1 A i , i +1=1 b i =rnd (1)

i =2 n

A i , i -1=1

L =cholesky (A )

y =lsolve (L , b )

x =lsolve (L T

, y )

改进的平方根方法：

⎛3.1620.316000

⎫

03.1460.31800

⎪⎪L T

3.1460.3180⎪

003.1460.318⎪ ⎪⎝

000

3.146⎪⎭

D T

i , i =(L ) i , i

i =1 n L =L ⋅D

-1

D =D ⋅D ⎛0

0000⎫

00000⎪⎪M T

1M 2M 1

-A = 0

0000⎪ 00000⎪ ⎪⎝

0⎪⎭

结论：通过用两种方法对题目的求解，我们得到高斯消去法适合用于中小规模线性方程的求解，它一般用于系数矩阵稠密而又没有任何特殊结构的线性方程组，由它改进后得到的选主元消去法是目前计算机上常用的有效方法；而对于一般方

阵，为了消除L U 分解的局限性和误差的过分积累，而采用了选主元的方法。但对于对称正定矩阵而言，选主元却是完全不必要的。通过上面两道题目的解答让我们对求解线性方程组的求法也有了具体的深刻的了解，更好的认识到了高斯（Causs ）消元法和平方根法所适合的范围，也知道了这两种方法各有各的优点。因此在我们做题时应该综合考虑各种因素来确定我们所要用的方法。这样才能使题目得到最方便、最有效的解答。参考文献：

徐树方高立张平文《数值线性代数》北京大学出版社 11页至10页

朱方生李大美李素贞《计算方法》武汉大学出版社 44页至86页

徐世良《数值分析与算法》机械工业出版社 36页至44页

数值线性代数课程设计线性方程组的直接解法

关键字：高斯消去法，顺序消去法，选主元消去法，平方根法，消元过程，回代过程, 主元数和乘数

一、高斯（Causs ）消去法就是逐步消去变元的

考虑一般方程组，为了推导过程方便，记系数矩

阵A 的元素a (0)

ij 为a ij ，右端向量b 的元素b i 记为a (0)

i , n +1，于是方程组

⎧a 11x 1+a 12x 2+ +a 1n x n =b ⎪

1⎪a 21x 1+a 22x 2+ +a ⎨

2n x n =b 2

（1.1⎪

）成为⎪⎩a n 1x 1

+a n 2x 2+ +a nn x n =b

n ⎧⎪a (0)(0)+ +a (0)(0)

11x 1+a 12x 21n x n =a 1n +1⎪(0

)(0)(0⎨

a )a (0)21x 1+a 22x 2+ +a 2n x n =2n +1

假设⎪

⎪⎩a (0)(0)(0)(n 1x 1

+a n 2x 2+ +a 0)nn x n =a nn +1(0)

(0) 11

≠0，将第1个方程乘以(-

a i 1a

(0) ) 加到第i 个

方程(2≤i ≤n ) , 得到第1个导出方程组

⎧a (0) (0) (0) (0) ⎪11x 1+a 12x 2+ a 1n x n =a 1n +1⎪

⎨

a (1)(1)=a (1)

22x 2+ a 2n x n 2n +1其中：⎪

⎪⎩

a (1)+ a (1)(1)n 2x 2nn x n =a nn +1

(0) a

(1)(0) i 1

(0)

a a (0)

a 1j ，2≤i ≤n ，2≤j ≤n +1。

(0) 由于因子

a i 1

a (0)

不止一次地用到，常

记为l (1)

i ,1。再假设a 22≠0，由第1个导出方程组(1)的第2个方程乘以(-

a i 2

a (1)

) 加到第i 个方程

(3≤i ≤n ) ，得到第2个导出方程组

⎧⎪

a (0)+a (0)(0)+a (0)(0)11x 112x 2+a 13x 3+ 1n x n =a 1n +1⎪a (1)x (1)(1)(1)⎪222+a 23x 3+ +a 2n x n =a 2n +1⎨a (2)a (2)(2)⎪

33x 3+ +3n x n =a 3n +1类似⎪

⎪⎩

a (2)(2)n 3x 3+ +a nn x (2)n =a nn +1(1)地记：l a i 2

i 2=a (1)

，则第2个导出方程组的元素

(1)

a (0)

=a (1)

a (i 2) ij -

(1)a (1)(1)(1)

2j =a ij -l i 2a 2j ，3≤i ≤n ，

3≤j ≤n +1。重复上述过程n -1次，得到n -1个导出方程组

⎧⎪

a (0)+a (0)(0)(0)(0)11x 112x 2+a 13x 3+ +a 1n x n =a 1n +1⎪a (1)(1)+ +a (1)(1)⎪22x 2+a 23x 32n x n =a 2n +1⎨a (2)x (2)(2)⎪

333+ +a 3n x n =a 3n +1⎪

⎪⎩

a (n -1)(n nn x -1)n =a nn +1（1.2）其中第k 个导出方程组的元素的递推关

系是l a (k -1) ik

ik =

a (k -1)

，a (k )

-1)

=a (k ij

-l (k -1)

ik a kj

（1.3）

(1≤k ≤n -1, k +1≤i ≤n , k +1≤j ≤n +1) 。由

n -1

S n 2

11=

∑

(n -k )(n -k +1) =

k =1

(n -1) n -1

除法次数为S n (n -1) 12=∑(n -k ) =

k =1

2. 回代过程

回代过程就是求等价三角形方程组（1.2）的解。只要a (k -1)

≠0(k =1, 2, , n ) ，就可以最

后一个方程得到x n 的值，再从第n -1个方程得

x n -1的值。在一般情形，可求得x i 的回代递推公

式

⎧(n -⎪

x a 1)

nn +1

n =(n -1) , ⎪⎪a nn

⎨n (i -⎪

(x 1) i -∑a (i -1)

ij x j ) ⎪⎪x j =i +1

⎩

i =a i -1

, i =n -1, n -2, ,1. ii （1.4）由公式（1.4）可知，回代过程需要n 次除法，其乘法和加法的次数同为

1+2+ +(n -1) =1

n (n -1) 。所以回代过程

需S 11

21=2n (n -1) 次加法，S 22=2

n (n +1) 次

乘、除法。

3. 顺序消去法的运算次数与计算步骤

由消元过程和回代过程的运算次数可知，顺序消去法的加法次数为

S 1=S 11+S 21=

n (2n +3n -5) ，乘除法次数

为S 12

2=S 11+S 12+S 22=

(n +3n -1) 。消元过

程在编程上机运算时，需采用三重循环，即对于k =1, 2, , n -1, i =k +1, k +2, , n , 计算

l a (k -1) ik

kk =

a (k -1)

；对于j =k +1, k +2, , n +1计算kk

a (k )

=a (k -1)

-l ik a (k -1)

。回代过程只需要二重循

(n -1)

环，即计算x +1n =

a nn a

(n -1) ，对于

i =n -1, n -2, ,1, s =0; 对于j =i +1, i +2, , n , 计算S =S +a (i -1)

ij x j ,

x a (i -1)

in +1-S i =

a (i -1) .

4. 主元数和乘数

由顺序消去法的推导过程可知，无论是消元过程

还是回代过程的都不需要对未知元作真正的运算，

A x =b 的系数矩阵的元素和

而仅需要对方程组

右端作运算。因此，在实际运算中，总是将方程组的系数矩阵和右端合在一起，记成增广矩阵(A , b ) 。

由消元过程（1.3）可以看到，元素a (k -1)

kk 为“主

元素“，另外，在消元过程中不止一次用到数l ik ，这个数称为消元过程的乘数。二．平方根法

设A ∈R n ⨯n 是对称正定的，即A 满足A T =A 而且x T Ax >0对一切的非零向量x ∈R n

成立. 此时, 由定理容易推出 Cholesky分解定理：若

A ∈R n ⨯n

对称正定，则存在一个对角元均为正数的下三角阵L ∈R n ⨯n , 求得A =LL T . 上式中的L 称作A 的Cholesky 因子。

若线性方程组的系数矩阵是对称正定的，则我们自然可按如下的步骤求其解：（1）求A 的

Cholesky 分解：A =LL T ;(2)求解Ly =b 得y ；（3）求解L T

x =y 得x 。

实验：1. 用高斯（Causs ）消去法求解下面的84阶方程组⎡61⎤⎡x ⎢1⎤⎡7⎤

⎥⎢⎢861⎥⎢

x ⎥⎢⎥2⎥⎢15⎥⎢8

61⎥⎢x ⎢⎢3⎥⎢15⎥

⎥⎥⎢⎥⎢

⎥⎢

⎥=⎢ ⎥。 ⎢⎥⎢⎢8

61x 82⎥⎢⎢8

61⎥⎢

⎥⎢15⎥

⎥⎥⎢x 83⎥⎢15⎥⎢⎣

6⎥⎦⎢⎣x 84⎥⎦⎢⎣14⎥⎦

解：n =10 A =identity (n )

i =1 n A i , i =6 i =1 n -1 A i , i +1=1

i =2 n A i , i -1=8

b 1=7 i =2 n -1 b i =15 b n =14

M =lu (A )

P =subm atrix (M ,1, n ,1, n ) L =subm atrix (M ,1, n , n +1, 2n )

U =subm atrix (M ,1, n , 2⋅n +1, 3⋅n )

y =lsolve (L , P ⋅b ) x =lsolve (U , y )

⎛1

47⎫A = 2

5.92⎪ ⎪ ⎝

10⎪⎭

⎛1

00⎫

UI =Gauss 2(A ) (U I

1) = 2

10⎪ ⎪ ⎝32.381

1⎪⎭

⎛147

⎫U I 2= 0

-2.1-12⎪ ⎪

⎝

17.571⎪⎭

⎛1

⎫U =Gauss (A , b ) U =

-2.1-12⎪ ⎪

⎝

17.571⎪⎭M =GaussLU (A ) L =M 1 U =M 2

⎛100⎫⎛147

⎫

L = 2

10⎪ ⎪ U =

0-2.1-12⎪⎪

⎝

32.381

1⎪⎭ ⎝

17.571⎪⎭

⎛0

00⎫A -LU =

00⎪ ⎪ ⎝

0⎪⎭

2. 用你编写的程序求解对称求解对称正定方程组

A x =b ，其中b 随机的选取，系数矩阵为100⎡101⎤⎢⎥⎢1101⎥⎢1101⎥阶⎢ ⎥⎢⎥。 ⎢⎢1101⎥⎢1101⎥

⎥

⎢⎣110⎥⎦

i =1 n

A i , i =10解: n =5 i =1 n -1 A i , i +1=1 b i =rnd (1)

i =2 n

A i , i -1=1

L =cholesky (A )

y =lsolve (L , b )

x =lsolve (L T

, y )

改进的平方根方法：

⎛3.1620.316000

⎫

03.1460.31800

⎪⎪L T

3.1460.3180⎪

003.1460.318⎪ ⎪⎝

000

3.146⎪⎭

D T

i , i =(L ) i , i

i =1 n L =L ⋅D

-1

D =D ⋅D ⎛0

0000⎫

00000⎪⎪M T

1M 2M 1

-A = 0

0000⎪ 00000⎪ ⎪⎝

0⎪⎭

徐树方高立张平文《数值线性代数》北京大学出版社 11页至10页

朱方生李大美李素贞《计算方法》武汉大学出版社 44页至86页

徐世良《数值分析与算法》机械工业出版社 36页至44页

数值线性代数课程设计

相关文章