Article

Article title THE USE OF CLIPPING OPERATIONS WHEN SOLVING NORMAL SYSTEMS OF EQUATIONS
Authors V. N. Lutay, N. S. Khusainov
Section SECTION IV. COMPUTER SCIENCE AND ELECTRONICS
Month, Year 07, 2017 @en
Index UDC 519.61
DOI
Abstract The paper considers a method for increasing the stability of solutions of systems of normal equations. Such systems of linear algebraic equations are widely used in processing experimental results for calculating regression coefficients, estimating and identifying control system parameters and in other applied problems in which the method of least squares is used. The most common method for solving them is the method of square roots (the Cholesky method), which transforms the square symmetric matrix of the system of equations to the product of two triangular matrices. It refers to direct algorithms for solving SLAE and is the most economical among them. At the same time, there are systems of normal equations for which the square root method can not be used. These are systems with an ill-conditioned matrix of coefficients, i.e. such in which a small change in the free coefficients leads to significant changes in the solution. When solving them, the calculation can fail because of the appearance of a negative subordinate expression. This circumstance narrows down the scope of the method of Cholesky and compels us to use other direct and iterative algorithms with greater laboriousness. As a way to prevent the process of computation from disrupting the work, it is proposed to use the operation of clipping the least significant digits of the product (square) of two numbers in the calculation of the radicand expression. The introduction of an operation that is non-standard for a computational scheme leads to the appearance of errors in the expansion of the matrix into triangular factors. The solution obtained is an approximate solution of the original system or, what is the same, the exact solution of the system in which some of the diagonal terms of the original matrix are increased. The values of the expansion errors can be determined in the course of the calculations and used to obtain an exact solution of the original system, for which a number of additional operations are required. The paper presents the results of experiments with the known Hilbert matrix, which is often used as a test in testing the effectiveness of computational procedures.

Download PDF

Keywords Normal equations; Cholesky method; ill-conditioned system of equations; clipping of the least significant bits.
References 1. Kabanov S.A. Optimizatsiya dinamiki sistem pri deystvii vozmushcheniy [Optimization of system dynamics under the action of disturbances]. Moscow: Fizmatlit, 2008, 200 p.
2. Shebshaevich V.S., Dmitriev P.P., Ivantsevich N.V. i dr. Setevye sputnikovye radionavigatsionnye sistemy [Network satellite navigation system], ed. by V.S. Shebshaevicha. 2nd ed. Moscow: Radio i svyaz', 1993, 408 p.
3. Azarskov V.N., Zhitetskiy L.S. Parametricheskaya identifikatsiya mnogosvyaznogo staticheskogo ob"ekta v zamknutom konture upravleniya: spetsial'nyy sluchay [Parametric identification of multivariable static object in a closed control loop: special case], Trudy XII Vserossiyskoe soveshchanie po problemam upravleniya VSPU-201. Moskva 16-19 iyunya 2014 g. [Proceedings of XII all-Russian meeting on control problems VCPU-201. Moscow, 16-19 June, 2014], pp. 2764-2776.
4. Gubanov V.S. Obobshchennyy metod naimen'shikh kvadratov: monografiya [The generalized least squares method: monograph]. Saint Petersburg: Nauka, 1997, 318 p.
5. Dorf R., Bishop R. Sovremennye sistemy upravleniya [Modern control system]. Moscow: Laboratoriya bazovykh znaniy, 2002, 832 p.
6. Gaydyshev I. Analiz i obrabotka dannykh. Spetsial'nyy spravochnik [Analysis and data processing. A special Handbook]. Saint Petersburg: Piter, 2001, 750 p.
7. Voevodin V.V., Kuznetsov Yu.A. Matritsy i vychisleniya [Matrix and calculations]. Moscow: Nauka. Glavnaya redaktsiya fiziko-matematicheskoy literatury, 1984, 320 p.
8. Golub Dzh., Van Loun Ch. Matrichnye vychisleniya [Matrix calculations]: translation from english. Moscow: Mir, 1999, 548 p.
9. Gorbachenko V.I. Vychislitel'naya lineynaya algebra s primerami na MATLAB [Computational linear algebra with examples in MATLAB]. Saint Petersburg: BKhV-Peterburg, 2011, 320 p.
10. Uilkinson Dzh. Algebraicheskaya problema sobstvennykh znacheniy [The algebraic problem of eigenvalues]. Moscow: Izd˗vo Nauka. Glavnaya redaktsiya fiziko˗matematicheskoy literatury, 1970, 565 p.
11. Knut D.E. Iskusstvo programmirovaniya. T. 2. Poluchislennye algoritmy – The Art of Computer Programming [The art of computer programming. Vol. 2. Polycycline algorithms The Art of Computer Programming]. Moscow: Vil'yams, 2001.
12. Balandin M.Yu., Shurygina E.P. Metody resheniya SLAU bol'shoy razmernosti [Methods of solving systems of linear equations of large dimension.]. Novosibirsk: Izd-vo NGTU, 2000, 70 p.
13. Il'in V.P. Metody nepolnoy faktorizatsii dlya resheniya algebraicheskikh system [Methods of incomplete factorization for the solution of algebraic systems]. Moscow: Fizmatlit, 1995, 284 p.
14. Saad Y. Iterative Methods for Sparse Linear Systems. New York: PWS Publ., 1996.
15. Stone H.L. Iterative Solution of Implicit Approximations of Multidimensional Partial Differential Equations, SIAM Journal on Numerical Analysis, 1968, No. 5 (3), pp. 530-558.
16. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods of solving ill-posed problems]. Moscow: Nauka. Glavnaya redaktsiya fiziko-matematicheskoy literatury, 1979, 285 p.
17. Intel MKL PARDISO solver. Available at: https://software.intel.com/en-us/mkl-developer-reference-fortran-intel-mkl-pardiso-parallel-direct-sparse-solver-interface (accessed 09 November 2017).
18. Lutay V.N., Khusainov N.S. Compensation of the computation errors in solving equation in navigation systems, International journal of applied engineering research, 2016, Vol. 11,
pp. 11555-11559. ISSN 0073-4562.
19. Forsayt Dzh., Moller K. Chislennoe reshenie sistem lineynykh algebraicheskikh uravneniy [Numerical solution of systems of linear algebraic equations]. Moscow: Mir, 1969, 164 p.
20. Maystrenko A.V., Svetlakov A.A., Cherepanov A.A. Issledovanie svoystv matritsy Gil'berta i prichin ee plokhoy obuslovlennosti [The study of the properties of the matrix Hilbert, and the reasons for its poor conditioning], Omskiy nauchnyy vestnik [Omsk scientific Bulletin], 2011, No. 3 (103), pp. 265-269.

Comments are closed.