Global Homotopy Continuation 방식을 이용한 비선형 방정식의 해법

한경택; 이강주; 윤인섭; 김화용

HWAHAK KONGHAK, Vol.30, No.1, 34-45, February, 1992

Export Citation

Global Homotopy Continuation 방식을 이용한 비선형 방정식의 해법

Application of Global Homotopy Continuation Method to Solutions of Nonlinear Equations

한경택, 이강주, 윤인섭, 김화용

초록

비선형 방정식의 해를 구하기 위한 강력하고 효율적인 Global Homotopy Continuation 알고리듬을 구현하였다. 기존의 알고리듬을 조합적으로 평가하였으며 이를 근거로 새로운 알고리듬을 제시하였으며 비교적 비선형성이 크고 다중해를 갖는 예제에 대하여 성능 평가를 행하였다. 알고리듬의 가장 큰 특징으로는 해곡선 이탈을 방지할 수 있는 기법과 함께 곡률의 근사식에 기본한 비교적 간단한 적분간격 제어와 신축성있는 수렴정의를 들 수 있다. 알고리듬은 지금까지의 것보다 해곡선 추적성능이 강력하고 우수하였으며 해고선의 이탈을 쉽게 감지해냄으로써 허용가능한 최대의 적분간격으로 효율적으로 해를 구현할 수 있었다. 또한 이를 이용하여 Newton Homotopy의 성질을 파악한 결과 해곡선은 시작점의 선정에 의하여 척도의 변화(scaling)를 보였으며 해곡선의 형태는 임계점을 전후로 완전히 다른 형태를 보임을 알 수 있었다.

An improved Homotopy continuation algorithm for solving nonlinear equations has been devel-oped. The improvement in this algorithm is that in addition to the stepsize control based on approximate curvature of solution path, a technique for preventing the segment jumping is incorporated into stepsize control for the robust path tracking. The flexible convergence criteria based on the determinant of augmented Jacobian is incorporated into the algorithm and it yields more robust and efficient continuation algorithm. The algorithm is tested on several small, but highly nonlinear problems and the results are documented. Also, the characteristics of Newton Homotopy path on selection of starting point have been investigated.

[References]

Allgower E, Georg K, SIAM Rev., 22, 28 (1980)
Choi SH, Ph.D. Dissertation, Univ. of Missourri-Rolla (1990)
Davidenko D, Dokl. Akad. Nauk USSR, 88, 601 (1953)
DenHeijer C, Rheinboldt WC, SIAM J. Numer. Anal., 18, 925 (1981)
Deuflhard P, Nmer. Math., 33, 115 (1979)
Dold A, Eckmann B, "Lecture Note in Mathmatics-Numerical 6. Solution of Nonlinear Equations," Springer-Verlag, New York (1981)
Kubicek M, Marek M, "Computation Methods in Bifurcation Theory and Dissipative Structures," Springer-Verlag, New York (1983)
Kubicek M, Holodniok M, Numer. Funct. Anal. Optimiz, 3, 223 (1981)
Kuno M, Seader JD, Ind. Eng. Chem. Res., 27, 1320 (1988)
Rheinholdt WC, "Numerical Analysis of Parameterized Nolinear Equations," John Wiley & Sons, New York (1986)
Rheinboldt WC, Burkardt JV, ACM Trans. Math. Soft., 9, 215 (1983)
Rheinboldt WC, SIAM J. Numer. Anal., 17, 221 (1980)
Rion WL, Brunt VV, Comput. Chem. Eng., 14, 889 (1990)
Seader JD, "Recent Developments in Methods for Finding All Solutions to General Systems of Nonlinear Equations," in Proc. of Conf. on Foundations of Computer Aided Process Design (1989)
Shacham M, "Recent Developments in Solution Techniques of Systems of Nonlinear Equations," in Proc. of Conf. on Foundations of Computer Aided Process Design (1984)
Seydel R, Hlavacek V, Chem. Eng. Sci., 42, 1281 (1987)
Watson LT, Billups SC, Morgan AP, ACM Trans. Math. Soft., 13, 281 (1987)
Wayburn TL, "A Review of Continuation Methods and Their Application to Separation Problems," in CAST Newsletter, Summer (1989)
고홍철, 박사학위논문, 서울대학교 (1989)

[Referenced By]

[1] Allgower E, Georg K, SIAM Rev., 22, 28 (1980)

[2] Choi SH, Ph.D. Dissertation, Univ. of Missourri-Rolla (1990)

[3] Davidenko D, Dokl. Akad. Nauk USSR, 88, 601 (1953)

[4] DenHeijer C, Rheinboldt WC, SIAM J. Numer. Anal., 18, 925 (1981)

[5] Deuflhard P, Nmer. Math., 33, 115 (1979)

[6] Dold A, Eckmann B, "Lecture Note in Mathmatics-Numerical 6. Solution of Nonlinear Equations," Springer-Verlag, New York (1981)

[7] Kubicek M, Marek M, "Computation Methods in Bifurcation Theory and Dissipative Structures," Springer-Verlag, New York (1983)

[8] Kubicek M, Holodniok M, Numer. Funct. Anal. Optimiz, 3, 223 (1981)

[9] Kuno M, Seader JD, Ind. Eng. Chem. Res., 27, 1320 (1988)

[10] Rheinholdt WC, "Numerical Analysis of Parameterized Nolinear Equations," John Wiley & Sons, New York (1986)

[11] Rheinboldt WC, Burkardt JV, ACM Trans. Math. Soft., 9, 215 (1983)

[12] Rheinboldt WC, SIAM J. Numer. Anal., 17, 221 (1980)

[13] Rion WL, Brunt VV, Comput. Chem. Eng., 14, 889 (1990)

[14] Seader JD, "Recent Developments in Methods for Finding All Solutions to General Systems of Nonlinear Equations," in Proc. of Conf. on Foundations of Computer Aided Process Design (1989)

[15] Shacham M, "Recent Developments in Solution Techniques of Systems of Nonlinear Equations," in Proc. of Conf. on Foundations of Computer Aided Process Design (1984)

[16] Seydel R, Hlavacek V, Chem. Eng. Sci., 42, 1281 (1987)

[17] Watson LT, Billups SC, Morgan AP, ACM Trans. Math. Soft., 13, 281 (1987)

[18] Wayburn TL, "A Review of Continuation Methods and Their Application to Separation Problems," in CAST Newsletter, Summer (1989)

[19] 고홍철, 박사학위논문, 서울대학교 (1989)