Solving ill-conditioned linear equations using simulated annealing method

Document Type : Research Paper

Author

UnDepartment of industrial engineering, University of Guilan, Rudsar, Iraniversity? ?of Guilan

Abstract

The purpose of this paper is to using the Simulated Annealing method to solving a linear equations system which have an ill-conditioned coefficients matrix. A linear equation system is called ill-conditioned if its condition number be large. By using a matrix scaling, the linear equation system transforms into a linear equation system with less condition number. Matrix balancing is performed by Simulated Annealing algorithm. The efficiency of this method is investigated by numerical examples. Numerical results show that Simulated Annealing can reduce the condition number of equations.

Keywords


[1] M. C. Trosset , What is Simulated Annealing, Optimization and Engineering, 2 (2001), 201–203.
[2] C. Blum and A. Roli, Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison, ACM Computing Surveys, 35 (2003), 268–308.
[3] F. Glover and G. Kochenberger, Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell (2002).
[4] R. Sinkhorn, A relationship between arbitrary positive matrices and stochastic matrices, Annals of Mathematical Statistics, 35 (1964), 876–879.
[5] F. L. Bauer, Optimally scaled matrices. Numerische Mathematik, 5 (1963), 73–87.
[6] D. R Braatz and M. Morari, Minimizing the Euclidean Condition Number. SIAM Journal on Control and Optimization,
32 (1994), 1763–1768.
[7] P. A. Businger, Matrices Which Can Be Optimally Scaled. Numerische Mathe-matik , 12 (1968), 346–348.
[8] Ch. Chin-Chieh and P. Ch. John An Approximate Equation for the Condition Numbers of Well-scaled Matrices. Proceedings of The 2008 IAJC-IJME Interna-tional Conference.
[9] G. A. Watson, An Algorithm for Optimal. Scaling of Matrices. IMA J. Numer.Anal , 11 (1991), 481–492.