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

高斯消去法目前，电力网络方程主要用高斯消去法求解。计算机在电力系统应用的初期，曾经因为内存容量的限制采用过迭代法求解电力网络的线性方程式组。迭代法的致命缺点是存在收敛性问题。因此，自从稀疏技术成功地在电力系统应用之后，迭代法几乎完全为高斯消去法所代替。高斯消去法求解线性方程式组由消去运算和回代运算两部分组成。消去运算又叫前代运算，可以按行进行，也可以按列进行。同样，回代运算可以按行进行，也可以按列进行。通常采用“消去运算按列进行，回代运算按行进行”的方式较多。设有n阶线性方程组BAX.其中矩阵A和向量B的元素可以是实数或复数。由于消去运算只对A和B进行，因此，为了算法叙述方便，把B作为第n+1列附在A之后，形成)1(nn阶增广矩阵：1,211222221111121121222221111211..................,...,...........................nnnnnnnnnnnnnnnnnaaaaaaaaaaaabaaabaaabaaaABA为了方便讨论，上式中用1,nja替代了),...,2,1(njbj。按列消去的运算步骤如下：第一步，消去第一列。首先，把增广矩阵A的第一行规格化为1)1(12a)1(13a…)1(1,1na（1-6）式中：111)1(1aaajj)1,...,3,2(nj然后，用式（1-6）所表示的行消去A的第一列对角线以下各元素13121,...,,naaa，结果使A的第2到第n行其他元素化为)1(11)1(jijijaaaai),...,3,2;1,...,3,2(ninj式中：上标（1）表示该元素第一次运算的结果。这时矩阵A变为1A：)1(1,)1()1(2)1(1,2)1(2)1(22)1(1,1)1(1)1(12111.....................1][nnnnnnnnnaaaaaaaaaBAA与之对应的方程组是11BXA,它与BAX同解。矩阵未标出的元素为零，下同。第二步，消去第二列。首先，把增广矩阵1A的第二行规格化为01)2(23a…)2(1,2na（1-7）式中：)1(22)1(2)2(2aaajj)1,...,4,3(nj然后，用式（1-7）所表示的行消去1A的第二列对角线以下各元素)1(2)1(42)1(32,...,,naaa，结果使1A的第3到n行其他元素化为)2(2)1(2)1()2(jiijijaaaa),...,4,3;1,...,4,3(ninj式中：上标（2）表示该元素第二次运算的结果。这时矩阵1A变为2A：)2(1,)2()2(3)2(1,3)2(3)2(33)2(1,2)2(2)2(23)1(1,1)1(1)1(13)1(12222.....................1...1][nnnnnnnnnnnaaaaaaaaaaaaaBAA一般地，在消去第k列时要做以下的运算：)1()1()(kkkkkjkkjaaa)1,...,1(nkj（1-8）)(1()1()()kkjkikkijkijaaaa),...,1;1,...,1(nkinkj（1-9）经过对矩阵A的n次消去运算，即k从1依次取到n按式（1-8），（1-9）运算，使矩阵A对角线以下的元素全部化为零，从而得到增广矩阵)(1,)3(1,3)3(3)2(1,2)2(2)2(23)1(1,1)1(1)1(13)1(121............1...1...1][nnnnnnnnnnnnaaaaaaaaaaBAA（1-10）与之对应的方程组是nnBXA，即)(1,)3(1,33(33)2(1,2)2(23)2(232)1(1,1)1(13)1(132)1(121...).........nnnnnnnnnnnnnaxaxaxaxaxaxaxaxaxax（1-11）它与原方程组BAX同解。现在来讨论按行回代过程。对于方程组（1-11），回代运算自下而上进行。首先由第n个方程可知)(1,nnnnax然后将nx代入第n-1个方程，解出nnnnnnnnxaax)1(,1)1(1,11再将1nx和nx代入第n-2个方程，可解出2nx。一般地，把已求出的niixxx,...,,21代入第i个方程，即可求出nijjijiiniixaax1)()(1,（i=n,…,2,1）(1-12)式(1-12)就是按行回代的一般公式。因子表和三角分解法在实际计算中，经常遇到这种情况：对于方程组需要多次求解，每次仅改变其常数项B，而系数矩阵A是不变的。这时，为了提高计算速度，可以利用因子表求解。因子表可以理解为高斯消去法解线性方程组的过程中对常数项B全部运算的一种记录表格。如前所述，高斯消去法分为消去过程和回代过程。回代过程的运算由对系数矩阵进行消去运算后得到的上三角矩阵元素确定，见式（1-10）。为了对常数项进行消去运算（又叫前代过程），还必须记录消去过程运算所需要的运算因子。消去过程中的运算又分为规格化运算和消去运算，以按列消去过程为列，由式（1-8）、（1-9）可知，消去过程中对常数项B中的第i个元素ib（即1,nia）的运算包括)1()1()(iiiiiiiabb（i=1,2,…,n）（1-13）)()1()1()(kkkikkikibabb(k=1,2,…,i-1)（1-14）将上式中的运算因子21,)1(21,...,,iiiiiaaa及)1(iiia逐行放在下三角部分，和式（1-10）的上三角矩阵元素合在一起，就得到了因子表)1()3(4)2(3)1(21)4(4)3(44)2(43)1(4241)3(3)3(34)2(33)1(3231)2(2)2(24)2(23)1(2221)1(1)1(14)1(13)1(1211.................................nnnnnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaaa其中下三角元素用来对常数项B进行消去（前代）运算，上三角元素用来进行消去回代运算。因子表也可以表示为如下形式：nnnnnnnnnndlllludllluudlluuudluuuud.................................4321444434241334333231224232221114131211（1-15）式中：)1(iiiiiad)(iijijau（ij）)1(iijijal(ji)不难看出，因子表中下三角部分的元素就是系数矩阵在消去过程中曾用以进行运算的元素，因此只要把它们保留在原来的位置，并把对角元素取倒数就可以得到因子表的下三角部分。而因子表中上三角部分的元素就是系数矩阵在消去过程完成后的结果。对于方程组，需要多次求解，每次仅改变其常数项B而系数矩阵A是不变的情况，应首先对其系数矩阵A进行消去运算，形成因子表。有了因子表，就可以对不同的常数项B求解。这时，可以直接应用因子表中的元素，用下面的公式代替式（1-13）、（1-14），进行消去运算：iiiiiidbb/)1()()()1()(kkikkikiblbb（i=k+1,…,n）用以下公式代替式(1-12)进行回代运算：)(nnnbxnijjjiiiixubx1)(参考文献王锡凡主编,方万良,杜正春.现代电力系统分析［M］.北京:科学出版社,2003.