【導(dǎo)讀】ofNewton’smethod[4].

　　

【正文】 得的結(jié)果 只會偏離形成的原則， 但是 后續(xù)的解決方案的精度將提高。這是我們 所說的按照內(nèi)存原則進(jìn)行節(jié)點(diǎn)排序和精確度之間是有矛盾的。 3 使用部分消元法和完全消元法所產(chǎn)生的精確度差異 對于解決 系統(tǒng)的線性代數(shù)方程組 ， 完全消元法在數(shù)值上比部分消元法更可取 。 當(dāng)系統(tǒng)系數(shù)變廣 時 ，解的精度 幾乎不可能受 舍入誤差 的 影響 ，因此把排序?qū)τ?解決方案的準(zhǔn)確性的順序 考慮在內(nèi)是 必要的。 圖 1有 著 四個節(jié)點(diǎn)的網(wǎng)絡(luò)樣 本的 直流模型 外文翻譯（譯文） 16 以 圖 1所示的 有 著 四個節(jié)點(diǎn)的網(wǎng)絡(luò)樣 本的 直流模型 為例。 節(jié)點(diǎn) 1是已知電壓相角擺動節(jié)點(diǎn) 。節(jié)點(diǎn) 24負(fù)荷節(jié)點(diǎn)。按照原來的節(jié)點(diǎn)數(shù)量，直流 潮流 方程是： 為了 模擬計算機(jī)數(shù)值計算操作， 我們用四個有效數(shù)字來解決這個問題 。 沒有 消 元 地 對 公 式 （ 1 ） 執(zhí) 行 高 斯 消 元 得 到 的 解 為[ θ2,θ3,θ4]T=[,]T ， 其 與 精 確 解 [θ2, θ3,θ4]T=[,]的部分元素不同，通過完全消元法可以得到一個更加精確的解： [θ2,θ3, θ4]T=[,]，并且 行和列的交匯處 的 節(jié)點(diǎn)的 排序 是 3,2,4 。所以這是一個 為了獲得更高精確度的一個更加合理的方案 。 4 節(jié)點(diǎn)排序?qū)εｎD 拉夫遜潮流計算方法的表現(xiàn)形式的影響 圖 2有 著六 個節(jié)點(diǎn)的網(wǎng)絡(luò)樣 本的 直流模型 在 上述分析的基礎(chǔ)上，對節(jié)點(diǎn)重新排序的 方案 將不僅影響到內(nèi)存的要求，外文翻譯（譯文） 17 而且影響到 求解線性方程組 時 解的精度。因此，牛頓 – 拉夫遜潮流方法的 性能將隨著 節(jié)點(diǎn)排序的變化而 不同。 在 本節(jié) 中 將 把三種不同的排序方案 應(yīng)用到如圖2 所示 的 6 個節(jié)點(diǎn)的網(wǎng)絡(luò)， 以便對它們對潮流計算中 解的精度 、 收斂速度 、 計算量和內(nèi)存 需求量進(jìn)行比較 。表四所示的 是性能的 細(xì)節(jié)。 A 目的一：盡可能地節(jié)省內(nèi)存 目前，以減少 最小優(yōu)化 和節(jié)省內(nèi)存節(jié)點(diǎn) ，有各種各樣的方案應(yīng)用于近優(yōu)化的節(jié)點(diǎn)排序 。 這種方案 所需要的唯一信息是描述網(wǎng)絡(luò)節(jié)點(diǎn)分支連接模式 的 一個表。 對 減少網(wǎng)絡(luò)的導(dǎo)納矩陣 有著 最佳 效果的排序 也是相關(guān)的雅可比矩陣表 的 最優(yōu)的因素。 在 編程的復(fù)雜性和最優(yōu)性之間 不同的方案可以達(dá)成不同的妥協(xié) 。在本文中，我們關(guān)注的編號的 結(jié)果 是如何 影響計算性能。編程效率是超出了目前的工作范圍。為了節(jié)省內(nèi)存， 在這一部分中，提出了與 [2]中提出的 第三種方案類似 一個動態(tài)節(jié)點(diǎn)排序方案 。該算法的執(zhí)行步驟如下。 方案一 a 定義其中一個節(jié)點(diǎn)度為一 。如果一個以上的節(jié)點(diǎn)符合這個標(biāo)準(zhǔn)， 選擇最原始的節(jié)點(diǎn) 。如果沒有任何節(jié)點(diǎn) 符合要求 ，啟動步驟 b ； b 當(dāng)這個節(jié)點(diǎn)被淘汰，編號那些沒有等效的分支節(jié)點(diǎn)可以被引入的節(jié)點(diǎn)。 如果一個以上的節(jié)點(diǎn)符合這個標(biāo)準(zhǔn)， 選擇最原始的節(jié)點(diǎn) 。如果我們不能 啟動步驟 a和步驟 b，打開步驟 c ； c 當(dāng)這個節(jié)點(diǎn)被淘汰，編號那些有最少分支的節(jié)點(diǎn)。 如 果 不止一個 節(jié)點(diǎn)可以引入最少的分支 節(jié)點(diǎn) ， 給那個最大節(jié)點(diǎn)度的節(jié)點(diǎn)編號 。 一旦在上述步驟 中 某個節(jié)點(diǎn) 被 編號，更新相關(guān)節(jié)點(diǎn) 度 和拓?fù)湫畔ⅰＶ钡剿械墓?jié)點(diǎn) 都 編 上 號，節(jié)點(diǎn)編號 就完成了 。 表 1 用方案一給節(jié)點(diǎn)再排序 新節(jié)點(diǎn)號碼 舊節(jié)點(diǎn)號碼 1 1 2 3 外文翻譯（譯文） 18 3 2 4 4 5 6 6 5 緊跟著方案一之后， 6 節(jié)點(diǎn)網(wǎng)絡(luò)的節(jié)點(diǎn)編號次序如表 1 所示。 在求解線性方程組的過程 中 ，沒 有引進(jìn)最小填充，所以表格的 因素 和 雅可比矩陣將有完全一致的結(jié)構(gòu)。所以 表格的 因素的內(nèi)存 需求 是 的，這 個 與該雅可比矩陣相同。通常情況下， 通過 四五 次牛頓 拉夫遜 迭代方法 就可以得到解 。 可是 這個例子所需的迭代 次數(shù) 是三十三 次 ，因?yàn)樾∽杩?分支 所造成的 病態(tài)性 。 在 每次迭代期間 前后 替代 的過程中需要 123次乘法運(yùn)算 ， 整個解答過程需要 7456次乘法運(yùn)算 。 B 目的二：用完全迭代法改善精確度 考慮到 完全消元法在數(shù)值上比部分消元法更可取 ，在本節(jié) 中 ， 為了 提高解決線性方程組 的 準(zhǔn)確性 而 采用 完全消元法 ，旨在減少迭代次數(shù)。這里涉及到大量的對角線子矩陣行列式的節(jié)點(diǎn) 以便 安排在前面。 在某種程度上 ，導(dǎo)納矩陣的主對角線上的 入口模數(shù) 可 以 表明雅可比矩陣的主對角線上的子矩陣的行列式的幅度。為 方便起見，我們利用導(dǎo)納矩陣確定數(shù)字的順序 。 方案二 a 形成節(jié)點(diǎn)導(dǎo)納矩陣 ； b 用完全消元法 因式分解節(jié)點(diǎn)導(dǎo)納矩陣。記錄節(jié)點(diǎn)的當(dāng)前位置上的變化 ； c 根據(jù)因式分解的節(jié)點(diǎn)的最終位置 確定節(jié)點(diǎn) 的新編號； 表 1 用方案二給節(jié)點(diǎn)再排序 新節(jié)點(diǎn)號碼 舊節(jié)點(diǎn)號碼 1 6 2 4 外文翻譯（譯文） 19 3 2 4 5 5 3 6 1 執(zhí)行方案二，完整 消元法可以再 沒有行和列 交匯的情況下自動 進(jìn)行。 對應(yīng)這些節(jié)點(diǎn)的 主對角線 的入口模數(shù)通過 總結(jié)更多的分支參數(shù) 而變得更大 ，因此，節(jié) 點(diǎn) 度 越 大 的 往往首先被編號。因此，該 方案的 的結(jié)果可能 與 稀疏矩陣方 法和許多 引入的最小填充 下形成的節(jié)點(diǎn)編號的原則 相異 。 6 節(jié)點(diǎn)網(wǎng)絡(luò)的節(jié)點(diǎn)編號次序如表 2 所示 。將產(chǎn)生 6 個 最小填充 ， 所以在一次迭代中前后替代過程中將花費(fèi) 更多的內(nèi)存（ ）和更多的操作（ 321個乘法運(yùn)算） ，所需的迭代總數(shù)減少到十三 次 ，這表明線性方程組的計算精度 通過 完全消元法得以提高 。最后， 由于迭代次數(shù)的減少 乘法運(yùn)算的 次數(shù) 減少到 5573次。 C 目的三：保持稀疏性的同時提高精確度 在 系統(tǒng)中只存在一個小的阻抗分支，所以相應(yīng) 于 節(jié)點(diǎn) 4 和節(jié)點(diǎn) 6 的 只有四個條目（子矩陣）是非常大的導(dǎo)納矩陣（雅可比矩陣）。在提出替 代的過程中，一旦節(jié)點(diǎn) 4和節(jié)點(diǎn) 6被 消除，其余元素組成的子矩陣能保持良好的數(shù)值穩(wěn)定性 ，并且 其余節(jié)點(diǎn)的編號不會 對解決方案的精確度產(chǎn)生影響 。 把 準(zhǔn)確性和稀疏 性都考慮 在內(nèi) ，我們 把 4 節(jié)點(diǎn) 編為 1 號 ，然后 按照目的一的方法給其他節(jié)點(diǎn)編號 。這就是我們 所說的 6 個節(jié)點(diǎn) 網(wǎng)絡(luò)的方案三 。 6 節(jié)點(diǎn)網(wǎng)絡(luò)的節(jié)點(diǎn)編號次序如表 3所示。 由于 在系統(tǒng)中 只 存在 一個小的阻抗分支， 并且 它連接到 節(jié)點(diǎn)度為 1 的 節(jié)點(diǎn)4。 方案三 將符合 目的一的 要求。因此， 最小填充的數(shù)目 ，內(nèi)存 需求 和分解所需的操作 次數(shù) 與方案一相同 。為了保證收斂性，只需要 9 次迭代 ，導(dǎo)致 計算量大大減少（ 僅 2107 次 乘法運(yùn)算）。迭代次數(shù)的減少表明，使用 方案三可以使 線性方程組 得到更加精確的求解 。經(jīng)過分析和比較，原因如下： 與 節(jié)點(diǎn) 4 有關(guān)的 對角線元素 比節(jié)點(diǎn) 6 小一點(diǎn) ，因此 首先 消除節(jié)點(diǎn) 4 不會降低精確度。該 方案 能夠滿足 完全消元法 。 外文翻譯（譯文） 20 方案三的更 少 的 操作 次數(shù) 減少計算器浮點(diǎn)數(shù)的舍入誤差。尤其 注意的是 ，如果 首先 消除節(jié)點(diǎn) 6，非常小的值可能被添加到節(jié)點(diǎn) 2和節(jié)點(diǎn) 5的節(jié)點(diǎn)元素 ，這將導(dǎo)致嚴(yán)重的舍入誤差。 然而 ，如果 首先 消除節(jié)點(diǎn) 4，一個相當(dāng)大的值將被添加到節(jié)點(diǎn) 6的對角線元素 上 ， 產(chǎn)生的新值 在正常范圍內(nèi)。 表 3用方案二給節(jié)點(diǎn)再排序 新節(jié)點(diǎn)號碼 舊節(jié)點(diǎn)號 碼 1 4 2 1 3 3 4 5 5 6 6 2 表 4用不同節(jié)點(diǎn)排序方案的進(jìn)行牛頓潮流計算的性能比較 方案一 方案二 方案三 內(nèi)存（ Kb） 最小填充數(shù) 0 6 0 迭代次數(shù) 33 13 9 分解計算數(shù)目 123 321 123 總的計算次數(shù) 7459 5573 2107 a 這里“操作次數(shù)”只代表乘法次數(shù)因?yàn)槌朔ㄗ詈臅r。 5 結(jié)論 理論分析和數(shù)值計算結(jié)果表明 ：在潮流計算中考慮節(jié)點(diǎn)排序是十分必要的。如果節(jié)點(diǎn)排序算法 合理地考慮內(nèi)存和精確度 ，潮流 計算性能 可以進(jìn)一步 改善。外文翻譯（譯文） 21 本文的基本結(jié)論如下： 對于 良好 的電力系統(tǒng)， 節(jié)點(diǎn)排序?qū)Τ绷饔嬎憔_度的影響是可以忽略的 。更重要的是，我們的注意力 應(yīng)該 集中在保持稀疏 性以 以節(jié)省內(nèi)存 需求 和計算操作 上 。 對于 病態(tài) 的電力系統(tǒng)， 為了 加快收斂速度 ，在節(jié)點(diǎn)排序算法中必須考慮精確度 。在此基礎(chǔ)上，如果同時 要保證 稀疏 性 ， 為了 減少浮點(diǎn)計算精度 的需求，我們應(yīng)該獲得更多的精確度 。 6 參考文獻(xiàn) [1] Allen J. Wood and Bruce F. Wollenberg, ―Power Generation, Operation and Cotrol (Second Edition),‖ Tsinghuo University Press, 2020. [2] W. F. Tinney and J. W. Walker. ―Direct solutions of sparse work equations by optimally ordered triangular factorization,‖ Proceedings of the IEEE, vol. 55, , pp. 18011809, November 1967. [3] K. M. Sambarapu and S. M. Halpin, ―Sparse matrix techniques in power systems,‖ ThirtyNinth Southeastern Symposium on System Theory, March 2020. [4] W. F. Tinney and C. E. Hart, ―Power flow solution by Newton39。s Method,‖ IEEE Transactions on Power Apparatus and Systems, Vol. PAS86, No. 11, pp. 14491460, November 1967. [5] W. F. Tinney, V. Brandwajn, and S. M. Chan, ―Sparse vector methods,‖ IEEE Transactions on Power Apparatus and Systems, Vol. PAS104, , pp. 295301, February 1985. [6] R. Betancourt, ―An efficient heuristic ordering algorithm for partial matrix refactorization,‖ IEEE Transactions on Power Systems, Vol. 3, No. 3, pp. 11811187, August 1988. [7] A. Gomez and . Franquelo. ―An efficient ordering algorithm to improve sparse vector methods,‖ IEEE Transactions on Power Systems, Vol. 3, No. 4, pp. 外文翻譯（譯文） 22 15381544, November 1988. [8] B. Stott, ―Review of loadflow calculation methods,‖ Proceedings of the IEEE, Vol. 62, No. 7, pp. 916929, July 1974. [9] X. W. Chang and C. C. Paige, ―On the sensitivity of the LU factorization,‖ BIT, Vol. 38, No. 3, pp. 486501, 1998. [10] . Businger, ―Monitoring the numerical stability of Gaussian elimination,‖ Numer. Math, Vol. 16, pp. 360361, 1971. [11] Paola Favati, Mauro Leoncini, and Angeles Martinez, ―On the robustness of gaussian elimination with partial pivoting,‖ BIT, Vol. 40, , , 2020