Title

以指定最佳向量為下降方向的迭代演算法求解病態線性問題

Translated Titles

Solving the Ill-posed linear Problem by Using the Specified Best Vector as a Descent Direction in Iterative Algorithms

DOI

10.6342/NTU.2012.00442

Authors

黃渝方

Key Words

線性反算問題 ; 病態線性系統 ; 未來錐 ; 最速下降方向及最佳向量的迭代演算法(SOVIA) ; 混合型的最佳迭代演算法 (MOIA) ; 最佳向量迭代演算法(OVIA) ; Linear inverse problems ; Ill-conditioned system ; future cone ; Steepest -descent and the optimal vector iterative algorithm(SOVIA) ; Mixed optimal iterative algorithm (MOIA) ; Optimal vector iterative algorithm(OVIA)

PublicationName

臺灣大學土木工程學研究所學位論文

Volume or Term/Year and Month of Publication

2012年

Academic Degree Category

碩士

Advisor

劉進賢

Content Language

繁體中文

Chinese Abstract

本文的演算法主要概念是在病態線性方程 中引入一個時空流形 且 為單調遞增的正函數,將病態線性方程問題構造成一個在閔式空間的未來錐的模型,利用未來錐模型啟動迭代動力系統,並且藉由最佳向量的概念設計下降方向,本文使用了兩種方法逼近最佳向量 ,第一種方法是考慮下降方向為最速方向及殘差方向的組合 ,其中權重因子 可利用最佳化求得,在此,本文設計了開關系統,能使下降方向不停的在兩種方向中轉換,進而搜尋到問題的解。以此概念發展的兩種演算法分別為最速下降方向及最佳向量的迭代演算法(SOVIA)以及混合型的最佳迭代演算法(MOIA);第二種方法是利用最佳參數 ,在虛數空間中找到一個最佳向量,此演算法稱最佳向量迭代演算法(OVIA).   經由數個正算病態線性問題如: 希爾伯特線性問題、拉普拉斯方程以及反算病態線性問題如:反算熱傳導問題、反算外力問題、柯西反算問題來驗證本文的三種演算法,並且將結果與共軛梯度法、鬆弛的最速下降法、OIA/ODV進行比較。

English Abstract

We define a monotonically increasing function of a time-like variable for solving the ill-conditioned system of linear equations ,and construct a future cone in the Minkowski space, wherein the discrete dynamics of the proposed algorithm is evolved. Then we propose two techniques to approximate the best vector ,and obtain iterative algorithms for solving . The first method is to consider the combination of the descent vector and the weighted residual vector . The parameter is best in the descent vector. In this paper we design a switching system, make the descent direction converted in both directions, and then search for the solution of the problem. The two algorithms that developed with this concept are steepest descent and optimal vector iterative algorithm (SOVIA) and mixed optimal iterative algorithm (MOIA).The second method is to use the best parameter in the imaginary space to find an optimal vector, which is called the an optimal vector iterative algorithm (OVIA).   Finally, the three algorithms are proved by several linear problems such as Hilbert linear problem and Laplace equation, and some linear inverse problems such as the back heat conduction problems, inverse external force problem and the inverse Cauchy problem. The results were compared with the CGM, RSDM, and OIA / ODV.

Topic Category 工學院 > 土木工程學研究所
工程學 > 土木與建築工程
Reference
  1. [2] S. Kubo, “Inverse Problems Related to the Mechanics and Fracture of Solids and Structures,” Jsme International Journal Series I-Solid Mechanics Strength of Materials, vol. 31, pp. 157-166, Apr 1988..
    連結:
  2. [4] M. Hirsch, and S. Smale, “ On algorithms for solving f (x) = 0, “Communications
    連結:
  3. on Pure and Applied Mathematics, Vol. 32, pp. 281-312,1979.
    連結:
  4. [5] C. S. Liu and S. N. Atluri, “A novel time integration method for solving a large system of non-linear algebraic equations,” CMES, vol. 31, pp. 71-83, Jul 2008.
    連結:
  5. [6] C. S. Liu, W. C. Yeih, C. L. Kuo, and S. N. Atluri, “A Scalar Homotopy Method for Solving an Over/Under-Determined System of Non-Linear Algebraic Equations,” CMES, vol. 53, pp. 47-71, Nov 2009
    連結:
  6. [7] C. Y. Ku, W. C. Yeih, and C. S. Liu, “Solving Non-Linear Algebraic Equations by a Scalar Newton-homotopy Continuation Method,” International Journal of Nonlinear Sciences and Numerical Simulation, vol. 11, pp. 435-450, Jun 2010.
    連結:
  7. [9] C. S. Liu, and S. N. Atluri, “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, vol. 80, no. 3-4, pp. 275-298, Oct, 2011.
    連結:
  8. [10] C. S. Liu, and S. N. Atluri, “An Iterative Algorithm for Solving a System of Nonlinear Algebraic Equations, F(x)=0, Using the System of ODEs with an Optimum in ,” CMES, vol. 73, no. 4, pp. 395-431, Mar, 2011
    連結:
  9. [11] C. S. Liu, and C. L. Kuo, “A Dynamical Tikhonov Regularization Method for Solving Nonlinear Ill-Posed Problems,” CMES, vol. 76, no. 2, pp. 109-132, Jun, 2011.
    連結:
  10. [14] C. S. Liu, “Cone of non-linear dynamical system and group preserving schemes,” International Journal of Non-Linear Mechanics, vol. 36, no. 7, pp. 1047-1068, Oct, 2001.
    連結:
  11. [15] C. S. Liu, “A Jordan algebra and dynamic system with associator as vector field,” International Journal of Non-Linear Mechanics, vol. 35, no. 3, pp. 421-429, May, 2000.
    連結:
  12. [16] V. D. Kupradze,and M. A. Alexidze, The method of functional equations for the approximate solution of certain boundary value problems, USSR Comput Math Math Phys. 4 (1964) 82-126
    連結:
  13. [17] M. Hanke and J. Nagy, “Inverse Toeplitz preconditioners for ill-posed problems,” Linear Algebra and Its Applications, vol. 284, pp. 137-156, Nov 15 1998.
    連結:
  14. [18] M. Hanke, “Accelerated Landweber Iterations for the Solution of Ill-Posed Equations,” Numerische Mathematik, vol. 60, pp. 341-373, 1991.
    連結:
  15. [19] C. S. Liu, “Improving the ill-conditioning of the method of fundamental solutions for 2D Laplace equation,” CMES, vol. 28, pp. 77-93, May 2008.
    連結:
  16. [20] H. Akaike, “On a Successive Transformation of Probability-Distribution and Its Application to the Analysis of the Optimum Gradient-Method,” Annals of the Institute of Statistical Mathematics, vol. 11, no. 1, pp. 1-16, 1959.
    連結:
  17. [21] G. E. Forsythe, “On Asymptotic Directions Ofs-Dimensional Optimum Gradient Method,” Numerische Mathematik, vol. 11, no. 1, pp. 57-&, 1968.
    連結:
  18. [1] A. N. Tikhonov and V. I. A. Arsenin, Solutions of ill-posed problems. Washington
  19. New York: Winston ; distributed solely by Halsted Press, 1977.
  20. [3] C. S. Liu, “A Highly Accurate Multi-Scale Full/Half-Order Polynomial Interpolation,” CMC, vol. 25, pp. 239-263, Oct 2011.
  21. [8] C. S. Liu, “A Revision of Relaxed Steepest Descent Method from the Dynamics on an Invariant Manifold, “ CMES, vol. 80, no. 1, pp. 57-86, Oct, 2011.
  22. [12] U. M. Ascher, K. van den Doel, H. Huang et al., “Gradient Descent and Fast Artificial Time Integration,” Esaim-Mathematical Modelling and Numerical Analysis-Modelisation Mathematique Et Analyse Numerique, vol. 43, no. 4, pp. 689-708, Jul-Aug, 2009.
  23. [13] C. S. Liu, and C. W. Chang, “Novel Methods for Solving Severely Ill-Posed Linear Equations System,” Journal of Marine Science and Technology-Taiwan, vol. 17, no. 3, pp. 216-227, Sep, 2009.
  24. [22] J. Nocedal, A. Sartenaer, and C. Y. Zhu, “On the behavior of the gradient norm in the steepest descent method,” Computational Optimization and Applications, vol. 22, no. 1, pp. 5-35, Apr, 2002.