高斯消去法和因子表分解法

高斯消去法

目前,电力网络方程主要用高斯消去法求解。计算机在电力系统应用的初期,曾经因为内存容量的限制采用过迭代法求解电力网络的线性方程式组。迭代法的致命缺点是存在收敛性问题。因此,自从稀疏技术成功地在电力系统应用之后,迭代法几乎完全为高斯消去法所代替。

高斯消去法求解线性方程式组由消去运算和回代运算两部分组成。消去运算又叫前代运算,可以按行进行,也可以按列进行。同样,回代运算可以按行进行,也可以按列进行。通常采用“消去运算按列进行,回代运算按行进行”的方式较多。

设有n 阶线性方程组AX =B . 其中矩阵A 和向量B 的元素可以是实数或复数。

由于消去运算只对A 和B 进行,因此,为了算法叙述方便,把B 作为第n+1列附在A 之后,形成n ⨯(n +1) 阶增广矩阵:

⎡a 11

⎢a

=[AB ]=⎢21

⎢... ⎢⎣a n 1

a 12a 22... a n 2

... a 1n ... a 2n ... ... ... a nn

b 1⎤⎡a 11

⎢a b 2⎥⎥=⎢21... ⎥⎢... ⎥⎢b n ⎦⎣a n 1

a 12a 22... a n 2

... a 1n ... a 2n ...

... ... a nn

a 1, n +1⎤a 2, n +1⎥⎥ ... ⎥

⎥a n , n +1⎦

为了方便讨论,上式中用a j , n +1替代了b j (j =1, 2,..., n ) 。 按列消去的运算步骤如下: 第一步,消去第一列。

首先,把增广矩阵的第一行规格化为

1 a 12(1) a 13 … a 1, n +1 (1-6) 式中:

(1)

(1)

a 1j

(1)

=

a 1j a 11

(j =2, 3, . . n . +, 1)

然后,用式(1-6)所表示的行消去的第一列对角线以下各元素a 21, a 31,..., a n 1,结果使的第2到第n 行其他元素化为

ai j

(1)

=a i j -a i 1a 1j (j =2, 3, . . n . +, 1; i =2, 3, . . n . ) ,

(1)

式中:上标(1)表示该元素第一次运算的结果。这时矩阵变为1:

⎡1a 12(1) ⎢(1)

a 22⎢A 1=[A 1B 1]=⎢... ⎢(1)

a ⎢n 2⎣

... a 1n

(1)

... a 2n ... ...

(1)

... a nn

(1)

(1)

a 1, n +1⎤

(1) ⎥a 2, n +1⎥

⎥... (1) ⎥a n , n +1⎥⎦

与之对应的方程组是A 1X =B 1, 它与AX =B 同解。矩阵未标出的元素为零,下同。

第二步,消去第二列。

首先,把增广矩阵1的第二行规格化为

0 1a 23 … a 2, n +1 (1-7) 式中:

a 2j

(2)

(2) (2)

=

a 2j a 22

(1) (1)

(j =3, 4, . . n . +, 1)

然后,用式(1-7)所表示的行消去1的第二列对角线以下各元素

a 32, a 42,..., a n 2,

结果使1的第3到n 行其他元素化为

(1) (1) (1)

a ij

(2)

=a ij

(1)

-a i 2a 2j

(1) (2)

(j =3, 4, . . n . +, 1; i =3, 4, . . n . ) ,

式中:上标(2)表示该元素第二次运算的结果。这时矩阵1变为A 2:

⎡1a 12(1)

1⎢

A 2=[A 2B 2]=⎢

⎢⎢⎢⎣

(k -1) (k -1)

a 13

(2) a 23

(2) a 33... (2) a n 3

(1)

... ... ... ... ...

a 1n

(2) a 2n

(2) a 3n ... (2) a nn

(1)

(1)

a 1, n +1⎤

(2) ⎥a 2, n +1⎥

(2)

a 3, n +1⎥

⎥... ⎥(2)

a n , n +1⎥⎦

一般地,在消去第k 列时要做以下的运算:

a kj

(k )

=

a kj a kk

(j =k +1,..., n +1) (1-8)

(k -1

a ij

(k )

=a ij

(k -1)

-a ik ) a kj

(k )

(j =k +1, . . n . +, 1; i =k +1, . . n . ) , (1-9)

经过对矩阵的n 次消去运算,即k 从1依次取到n 按式(1-8),(1-9)运算,使矩阵A 对角线以下的元素全部化为零,从而得到增广矩阵

⎡1a 12(1) ⎢

1⎢

A n =[A n B n ]=⎢

⎢⎢⎢⎣

a 13

(2) a 231

(1)

... a 1n

(2)

... a 2n

(3)

... a 3n ... ...

1

(1)

(1)

a 1, n +1⎤

(2) ⎥a 2, n +1⎥

(3)

a 3, n +1⎥ (1-10)

⎥... ⎥(n )

a n , n +1⎥⎦

与之对应的方程组是A n X =B n ,即

(1) (1) (1) (1)

x 1+a 12x 2+a 13x 3+... +a 1n x n =a 1, n +1⎫

⎪(2) (2) (2)

⎪x 2+a 23x 3+... +a 2n x n =a 2, n +1

⎪⎪(3(3)

x 3+... +a 3n ) x n =a 3, n +1⎬ (1-11)

⎪... ⎪

(n ) ⎪x n =a n , n +1

⎪⎭

它与原方程组AX =B 同解。

现在来讨论按行回代过程。对于方程组(1-11),回代运算自下而上进行。首先由第n 个方程可知

(n )

x n =a n , n +1

然后将x n 代入第n-1个方程,解出

x n -1=a n -1, n +1

(n -1)

-a n -1, n

(n -1)

x n

再将x n -1和x n 代入第n-2个方程,可解出x n -2。一般地,把已求出的

x i +1, x i +2,..., x n 代入第i 个方程,即可求出

x i =a i , n +1-

(i )

j =i +1

∑a i j x j (i=n,…,2,1) (1-12)

(i )

n

式(1-12)就是按行回代的一般公式。 因子表和三角分解法

在实际计算中,经常遇到这种情况:对于方程组需要多次求解,每次仅改变其常数项B ,而系数矩阵A 是不变的。这时,为了提高计算速度,可以利用因子表求解。

因子表可以理解为高斯消去法解线性方程组的过程中对常数项B 全部运算的一种记录表格。如前所述,高斯消去法分为消去过程和回代过程。回代过程的运算由对系数矩阵进行消去运算后得到的上三角矩阵元素确定,见式(1-10)。为了对常数项进行消去运算(又叫前代过程),还必须记录消去过程运算所需要的运算因子。消去过程中的运算又分为规格化运算和消去运算,以按列消去过程

为列,由式(1-8)、(1-9)可知,消去过程中对常数项B 中的第i 个元素b i (即

a i , n +1)的运算包括

b i

(i )

=

b i

(i -1) (i -1)

a ii

(i=1,2,…,n ) (1-13)

b i

(k )

=b i

(k -1)

-a ik

(k -1)

b k

(k )

(k=1,2,…,i-1) (1-14)

(1)

i -2

将上式中的运算因子a i 1, a i 2,..., a i , i -1及a ii

(i -1)

逐行放在下三角部分,和式

(1-10)的上三角矩阵元素合在一起,就得到了因子表

a 11

a 21a 31a 41... a n 1

a 12

(1) a 22a 32

(1) (1)

(1)

a 13

(2) a 23a 33

(2) (2)

(1)

a 14

(2) a 24a 34

(3) (3)

(1)

... ... ... ... ...

a 1n

(2) a 2n a 3n

(3) (4)

(1)

a 42... a n 2

a 43... a n 3

a 44... a n 4

a 4n ...

(1) (2) (3)

... a nn

(n -1)

其中下三角元素用来对常数项B 进行消去(前代)运算,上三角元素用来进行消去回代运算。因子表也可以表示为如下形式: d 11u 12u 13u 14... u 1n l 21d 22u 23u 24... u 2n l 31l 32d 33u 34... u 3n

(1-15)

l 41l 42l 43d 44... u 4n ... ... ... ... ... ... l n 1l n 2l n 3l n 4... d nn

式中:

d ii =a ii

(i -1)

(i )

u ij =a ij (i

l ij =a ij

(i -1)

(j

不难看出,因子表中下三角部分的元素就是系数矩阵在消去过程中曾用以进行运算的元素,因此只要把它们保留在原来的位置,并把对角元素取倒数就可以得到因子表的下三角部分。而因子表中上三角部分的元素就是系数矩阵在消去过程完成后的结果。

对于方程组,需要多次求解,每次仅改变其常数项B 而系数矩阵A 是不变的情况,应首先对其系数矩阵A 进行消去运算,形成因子表。有了因子表,就可以对不同的常数项B 求解。这时,可以直接应用因子表中的元素,用下面的公式代替式(1-13)、(1-14),进行消去运算:

b i b i

(i )

=b i

(i -1)

/d ii -l ik b k

(k )

(k )

=b i

(k -1)

(i=k+1,…,n )

用以下公式代替式(1-12)进行回代运算:

x n =b n x i =b i

(n )

(i )

-

j =i +1

∑u

n

i j

x j

参考文献

王锡凡主编, 方万良, 杜正春. 现代电力系统分析[M ]. 北京:科学出版社, 2003.

高斯消去法

目前,电力网络方程主要用高斯消去法求解。计算机在电力系统应用的初期,曾经因为内存容量的限制采用过迭代法求解电力网络的线性方程式组。迭代法的致命缺点是存在收敛性问题。因此,自从稀疏技术成功地在电力系统应用之后,迭代法几乎完全为高斯消去法所代替。

高斯消去法求解线性方程式组由消去运算和回代运算两部分组成。消去运算又叫前代运算,可以按行进行,也可以按列进行。同样,回代运算可以按行进行,也可以按列进行。通常采用“消去运算按列进行,回代运算按行进行”的方式较多。

设有n 阶线性方程组AX =B . 其中矩阵A 和向量B 的元素可以是实数或复数。

由于消去运算只对A 和B 进行,因此,为了算法叙述方便,把B 作为第n+1列附在A 之后,形成n ⨯(n +1) 阶增广矩阵:

⎡a 11

⎢a

=[AB ]=⎢21

⎢... ⎢⎣a n 1

a 12a 22... a n 2

... a 1n ... a 2n ... ... ... a nn

b 1⎤⎡a 11

⎢a b 2⎥⎥=⎢21... ⎥⎢... ⎥⎢b n ⎦⎣a n 1

a 12a 22... a n 2

... a 1n ... a 2n ...

... ... a nn

a 1, n +1⎤a 2, n +1⎥⎥ ... ⎥

⎥a n , n +1⎦

为了方便讨论,上式中用a j , n +1替代了b j (j =1, 2,..., n ) 。 按列消去的运算步骤如下: 第一步,消去第一列。

首先,把增广矩阵的第一行规格化为

1 a 12(1) a 13 … a 1, n +1 (1-6) 式中:

(1)

(1)

a 1j

(1)

=

a 1j a 11

(j =2, 3, . . n . +, 1)

然后,用式(1-6)所表示的行消去的第一列对角线以下各元素a 21, a 31,..., a n 1,结果使的第2到第n 行其他元素化为

ai j

(1)

=a i j -a i 1a 1j (j =2, 3, . . n . +, 1; i =2, 3, . . n . ) ,

(1)

式中:上标(1)表示该元素第一次运算的结果。这时矩阵变为1:

⎡1a 12(1) ⎢(1)

a 22⎢A 1=[A 1B 1]=⎢... ⎢(1)

a ⎢n 2⎣

... a 1n

(1)

... a 2n ... ...

(1)

... a nn

(1)

(1)

a 1, n +1⎤

(1) ⎥a 2, n +1⎥

⎥... (1) ⎥a n , n +1⎥⎦

与之对应的方程组是A 1X =B 1, 它与AX =B 同解。矩阵未标出的元素为零,下同。

第二步,消去第二列。

首先,把增广矩阵1的第二行规格化为

0 1a 23 … a 2, n +1 (1-7) 式中:

a 2j

(2)

(2) (2)

=

a 2j a 22

(1) (1)

(j =3, 4, . . n . +, 1)

然后,用式(1-7)所表示的行消去1的第二列对角线以下各元素

a 32, a 42,..., a n 2,

结果使1的第3到n 行其他元素化为

(1) (1) (1)

a ij

(2)

=a ij

(1)

-a i 2a 2j

(1) (2)

(j =3, 4, . . n . +, 1; i =3, 4, . . n . ) ,

式中:上标(2)表示该元素第二次运算的结果。这时矩阵1变为A 2:

⎡1a 12(1)

1⎢

A 2=[A 2B 2]=⎢

⎢⎢⎢⎣

(k -1) (k -1)

a 13

(2) a 23

(2) a 33... (2) a n 3

(1)

... ... ... ... ...

a 1n

(2) a 2n

(2) a 3n ... (2) a nn

(1)

(1)

a 1, n +1⎤

(2) ⎥a 2, n +1⎥

(2)

a 3, n +1⎥

⎥... ⎥(2)

a n , n +1⎥⎦

一般地,在消去第k 列时要做以下的运算:

a kj

(k )

=

a kj a kk

(j =k +1,..., n +1) (1-8)

(k -1

a ij

(k )

=a ij

(k -1)

-a ik ) a kj

(k )

(j =k +1, . . n . +, 1; i =k +1, . . n . ) , (1-9)

经过对矩阵的n 次消去运算,即k 从1依次取到n 按式(1-8),(1-9)运算,使矩阵A 对角线以下的元素全部化为零,从而得到增广矩阵

⎡1a 12(1) ⎢

1⎢

A n =[A n B n ]=⎢

⎢⎢⎢⎣

a 13

(2) a 231

(1)

... a 1n

(2)

... a 2n

(3)

... a 3n ... ...

1

(1)

(1)

a 1, n +1⎤

(2) ⎥a 2, n +1⎥

(3)

a 3, n +1⎥ (1-10)

⎥... ⎥(n )

a n , n +1⎥⎦

与之对应的方程组是A n X =B n ,即

(1) (1) (1) (1)

x 1+a 12x 2+a 13x 3+... +a 1n x n =a 1, n +1⎫

⎪(2) (2) (2)

⎪x 2+a 23x 3+... +a 2n x n =a 2, n +1

⎪⎪(3(3)

x 3+... +a 3n ) x n =a 3, n +1⎬ (1-11)

⎪... ⎪

(n ) ⎪x n =a n , n +1

⎪⎭

它与原方程组AX =B 同解。

现在来讨论按行回代过程。对于方程组(1-11),回代运算自下而上进行。首先由第n 个方程可知

(n )

x n =a n , n +1

然后将x n 代入第n-1个方程,解出

x n -1=a n -1, n +1

(n -1)

-a n -1, n

(n -1)

x n

再将x n -1和x n 代入第n-2个方程,可解出x n -2。一般地,把已求出的

x i +1, x i +2,..., x n 代入第i 个方程,即可求出

x i =a i , n +1-

(i )

j =i +1

∑a i j x j (i=n,…,2,1) (1-12)

(i )

n

式(1-12)就是按行回代的一般公式。 因子表和三角分解法

在实际计算中,经常遇到这种情况:对于方程组需要多次求解,每次仅改变其常数项B ,而系数矩阵A 是不变的。这时,为了提高计算速度,可以利用因子表求解。

因子表可以理解为高斯消去法解线性方程组的过程中对常数项B 全部运算的一种记录表格。如前所述,高斯消去法分为消去过程和回代过程。回代过程的运算由对系数矩阵进行消去运算后得到的上三角矩阵元素确定,见式(1-10)。为了对常数项进行消去运算(又叫前代过程),还必须记录消去过程运算所需要的运算因子。消去过程中的运算又分为规格化运算和消去运算,以按列消去过程

为列,由式(1-8)、(1-9)可知,消去过程中对常数项B 中的第i 个元素b i (即

a i , n +1)的运算包括

b i

(i )

=

b i

(i -1) (i -1)

a ii

(i=1,2,…,n ) (1-13)

b i

(k )

=b i

(k -1)

-a ik

(k -1)

b k

(k )

(k=1,2,…,i-1) (1-14)

(1)

i -2

将上式中的运算因子a i 1, a i 2,..., a i , i -1及a ii

(i -1)

逐行放在下三角部分,和式

(1-10)的上三角矩阵元素合在一起,就得到了因子表

a 11

a 21a 31a 41... a n 1

a 12

(1) a 22a 32

(1) (1)

(1)

a 13

(2) a 23a 33

(2) (2)

(1)

a 14

(2) a 24a 34

(3) (3)

(1)

... ... ... ... ...

a 1n

(2) a 2n a 3n

(3) (4)

(1)

a 42... a n 2

a 43... a n 3

a 44... a n 4

a 4n ...

(1) (2) (3)

... a nn

(n -1)

其中下三角元素用来对常数项B 进行消去(前代)运算,上三角元素用来进行消去回代运算。因子表也可以表示为如下形式: d 11u 12u 13u 14... u 1n l 21d 22u 23u 24... u 2n l 31l 32d 33u 34... u 3n

(1-15)

l 41l 42l 43d 44... u 4n ... ... ... ... ... ... l n 1l n 2l n 3l n 4... d nn

式中:

d ii =a ii

(i -1)

(i )

u ij =a ij (i

l ij =a ij

(i -1)

(j

不难看出,因子表中下三角部分的元素就是系数矩阵在消去过程中曾用以进行运算的元素,因此只要把它们保留在原来的位置,并把对角元素取倒数就可以得到因子表的下三角部分。而因子表中上三角部分的元素就是系数矩阵在消去过程完成后的结果。

对于方程组,需要多次求解,每次仅改变其常数项B 而系数矩阵A 是不变的情况,应首先对其系数矩阵A 进行消去运算,形成因子表。有了因子表,就可以对不同的常数项B 求解。这时,可以直接应用因子表中的元素,用下面的公式代替式(1-13)、(1-14),进行消去运算:

b i b i

(i )

=b i

(i -1)

/d ii -l ik b k

(k )

(k )

=b i

(k -1)

(i=k+1,…,n )

用以下公式代替式(1-12)进行回代运算:

x n =b n x i =b i

(n )

(i )

-

j =i +1

∑u

n

i j

x j

参考文献

王锡凡主编, 方万良, 杜正春. 现代电力系统分析[M ]. 北京:科学出版社, 2003.


相关文章

  • 数值线性代数课程设计
  • 数值线性代数课程设计 线性方程组的直接解法 数理学院 09405011班 0940501120 沈骁 摘要:如何利用电子计算机来快速.有效的求解线性方程组的问题是数值线性代数的核心问题.本文将主要介绍解线性方程组的基本的直接法--高斯消去法 ...查看


  • 用matlab解线性方程组
  • 用matlab解线性方程组 2008-04-12 17:00 一.高斯消去法 1.顺序高斯消去法 直接编写命令文件 a=[] d=[]' [n,n]=size(a); c=n+1 a(:,c)=d; for k=1:n-1 a(k+1:n, ...查看


  • 第1章 解线性代数方程组的直接法
  • 第一章 解线性代数方程组的直接法 1.1 引 言 在自然科学与社会科学的研究中,常常需要求解线性代数方程组,如实验数据的曲线.曲面的拟合和用差分法或有限元法解偏微分方程等都要用到线性代数方程组的求解.由于从不同的问题导出的线性代数方程组的系 ...查看


  • LU分解求线性方程组的解
  • LU分解是矩阵分解的一种,可以将一个矩阵分解为一个上三角矩阵和一个下三角矩阵的乘积. LU分解可以用来求逆矩阵,解线性方程组等.本文将介绍LU分解求线性方程组的解. 1.定义 如果A是一个方阵,A的LU分解是将A分解成如下形式: 其中L,U ...查看


  • 高斯消元法 1
  • 求解线性方程组的直接解法 5.1 Gauss 消去法 ① 三角方程组 先举一个简单的例子来说明消去法的基本思想. 例1. 用消去法解方程组 (1)⎧x 1+x 2+x 3=6, ⎪ (2) ⎨4x 2-x 3=5, ⎪2x -2x +x = ...查看


  • 4.线性方程组
  • 第4章 线性方程组的数值解法 1 4.1 预备知识 4.1.1 线性方程组的数值解法 线性方程组的数值解法一般有两类: 1. 直接法(消元法) 经过有限步算术运算,求得方程组精确解的方法.但实 际计算中由于舍入误差的存在和影响,这种方法只能 ...查看


  • 潮流计算的相关问题2011
  • §4.5牛顿-拉夫逊法计算潮流有关问题 1. ΔX 2. 3. 多值解 对于非线性方程组,解的可能性有: •有实际意义的解 •有解,但在实际中无意义 (PV 节点或平衡节点的无功功率超过允许值,平衡节点的有功功率超过允许值:节点的电压过高或 ...查看


  • 近世代数复习题
  • 近世代数复习思考题 一.基本概念与基本常识的记忆 (一)填空题 1. 剩余类加群Z 12有_________个生成元. 2.设群G 的元a 的阶是n ,则a 的阶是________. 3. 6阶循环群有_________个子群. 4.设群G ...查看


  • 近世代数复习题 1
  • 近世代数复习思考题 一.基本概念与基本常识的记忆 (一)填空题 1. 剩余类加群Z 12有_________个生成元. 2.设群G 的元a 的阶是n ,则a k 的阶是________. 3. 6阶循环群有_________个子群. 4.设 ...查看


热门内容