高斯消去法
目前,电力网络方程主要用高斯消去法求解。计算机在电力系统应用的初期,曾经因为内存容量的限制采用过迭代法求解电力网络的线性方程式组。迭代法的致命缺点是存在收敛性问题。因此,自从稀疏技术成功地在电力系统应用之后,迭代法几乎完全为高斯消去法所代替。
高斯消去法求解线性方程式组由消去运算和回代运算两部分组成。消去运算又叫前代运算,可以按行进行,也可以按列进行。同样,回代运算可以按行进行,也可以按列进行。通常采用“消去运算按列进行,回代运算按行进行”的方式较多。
设有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.