以臨界向量為下降方向解代數方程式之全局最佳演算法

The Globally Optimal Iterative Algorithm with Critical Vector as a Descent Direction to Solve Algebraic Equations

徐佳柔(Chia-Jou Hsu)

指導教授 ： 劉進賢

國立臺灣大學/工學院/土木工程學研究所/碩士(2012年)

https://doi.org/10.6342/NTU.2012.02851

摘要

本文結合了最速下降法、純量同倫及光錐的結構發展出一全局最佳演算法(Globally Optimal Iterative Algorithm)，由預先設定之參數(ϒ、ac) 確定其解的存在並考慮臨界情形(判別式為零)推導出一重要參數 後，分別使用臨界向量u=R+αcr及u=BTF+αcF為下降方向求解線性及非線性代數方程式問題。
本演算法於求解線性代數方程式時展現了良好的效益，其準確性甚至高於共軛梯度法(Conjugate Gradient method)及OIA/ODV; 此外，此方法用於求解非線性代數方程式時也展現了良好了成果，除了良好的效益之外，於求解達芬方程式(Duffing equation)時也有極佳的準確性。
其演算過程除了有效避免了雅可比矩陣(Jacobian matrix)之反矩陣計算，不同於牛頓法，其迭代過程不需擔心出現發散之情形，對於初始猜值的敏感度也明顯低於牛頓法。

關鍵字

最速下降法 ； 純量同倫 ； 光錐 ； 代數方程式 ； 全局最佳演算法 ； 牛頓法 ； 共軛梯度法 ； OIA/ODV

並列摘要

It has always been of interest to solve algebraic equations used for describing physical and engineering issues. By using the concepts of the Steepest Descent method, the scalar homotopy method and the structure of light cone, we have developed a novel algorithm with preset parameters ϒ(0≤ϒ<1),ac (ac>1) and the critical parameter αc in the driving vector u=R+αcr and u=BTF+αcF as a descent direction. Due to the criticality of αc, we believe that by using this algorithm, the globally optimal solution can be obtained. It is so call the Globally Optimal Iterative Algorithm (GOIA).
The GOIA has performed both great efficiency and accuracy when it is used for solving algebraic equations. Moreover, by using the GOIA, one can successfully avoid the calculation of the inverse Jacobian matrix which is required when use the Newton’s method instead.

並列關鍵字

algebraic equations ； Steepest Descent method ； scalar homotopy method ； light cone ； Globally Optimal Iterative Algorithm (GOIA) ； Newton’s method

參考文獻

[1] Liu, C.-S.; S. N. Atluri (2011): "An Iterative Method Using an Optimal Descent Vector, for Solving an Ill-Conditioned System Bx=b, Better and Faster than the Conjugate Gradient Method." CMES: Computer Modeling in Engineering & Sciences 80(4): 275-298.

[5] Davidenko, D. (1953): "On a new method of numerical solution of systems of nonlinear equations" Doklady Akad. Nauk SSSR 88: 601-604.

[10] Ku, C.-Y., Yeih, W.-C.; Liu, C.-S. (2010): "Solving Non-Linear Algebraic Equations by a Scalar Newton-homotopy Continuation Method." International Journal of Nonlinear Sciences & Numerical Simulation 11: 435-450.

[18] Park, C.-H.; Shim, H.-T. (2005): "What Is The Homotopy Method For A System Of Nonlinear Equations (Survey) ?" Appl. Math. & Computing 17: 689-700.

[19] Wayburns, T. L.; Seader, J. D. (1987): "Homotopy Continuation Methods For Computer-Aided Process Design." compur. &em. &gag 11(1): 7-25.