A STABLE METHOD FOR FINDING NORMAL D-PSEUDOSOLUTIONS OF SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS WITH APPROXIMATE DATA AND MEASURES OF THEIR INCONSISTENCY

DOI: 10.47026/1810-1909-2024-2-54-66

УДК 519.612.4

519.852.6

Alexander Yu. IVANITSKIY, Mikhail V. KISELEV, Marina V. VASILKOVA, Vladimir V. EJOV

Key words

D-pseudosolutions, measures of inconsistency, Fredholm integral equations of the first kind in engineering problems, pointwise residual method, estimate of approximate solutions

Abstract

The research purpose is to develop and fully mathematically justify a stable method for finding a normal D-pseudosolution of inconsistency systems of linear algebraic equations with approximate data.

Materials and methods. The paper uses an analogue of the Weirstrass theorem from the theory of optimization methods and the concept of norms in finite-dimensional spaces and extended version of Hoffman’s lemma to determine the distance from an arbitrary point to a polyhedron.

Research results. The article proposes an ideologically simple, reliable and stable method – the pointwise residual method for finding D-pseudosolutions and measures of inconsistency of systems of linear algebraic equations, obtained during the approximation of Fredholm integral equations of the first kind, which describe a number of engineering tasks. To use this method, it is enough to know information of approximate data and estimates of their error. The convergence theorem of the method is proved and estimate of the convergence rate of the method of the same order as that of setting errors in the initial data is obtained. The method is optimal in order.

Conclusions. A new stable method for numerically finding a normal D-pseudosolution of systems of linear algebraic equations with approximate data in the absence of information about their solvability is proposed. This method is nonparametric and requires one time solving an optimization problem with piecewise linear constraints, and in some cases solving a quadratic programming problem.

References

1. Babenko V.N. O strukture otsenok blizosti psevdoreshenii iskhodnoi i vozmushchennykh sistem lineinykh algebraicheskikh uravnenii [On the structure of estimates of the proximity of pseudo-solutions of the initial and perturbed systems of linear alrebraic systems]. Computational Mathematics and Mathematical Physics (Zn. Vychisl. Mat. and Mat. Fiz.), 2019, vol. 59, no. 9, pp. 1459–1481.
2. Vasylyev F.P. Metody optimizatsii [Optimization Methods]. Moscow, Faktorial Press Publ., 2002, 412 p.
3. Vasylyev F.P., Ivanitskiy A.Yu. Lineinoe programmirovanie [Linear Programming]. Moscow, MCCME Publ., 2020, 412 p.
4. Galba E.F., Sergienko I.V. Metody vychisleniya vzveshennykh psevdoobratnykh matrits i vzveshennykh normal’nykh psevdore-shenii s vyrozhdennymi vesami [Methods for Computing Weighted Pseudoinverses and Weighted Normal Pseudosolutions with Singular Weights]. Cybernetics and System Analysis, 2018, vol. 54, no. 3, pp. 1347–1363.
5. Ivanitskiy A.Yu. Ustoichivye metody dlya resheniya sistem lineinykh uravnenii i neravenstv s interval’nymi koeffitsientami: dis. … kand. fiz.-mat. nauk [Stable Methods for Solving Systems of Linear Equations and Tnequalities with Interval Coefficients: Diss.], Moscow, 1988, 133 p.
6. Ivanitskiy A.Yu. Otsenka skorosti skhodimosti metoda potochechnoi nevyazki dlya resheniya nesovmestnykh sistem lineinykh algebraicheskikh uravnenii. Metody i algoritmy v chislennom analize [Estimation of speed of convergence of pointwise residual method for solving inconsistency systems of linear alrebraic equations. Methods and Algorithms of Numerical Analysis]. Moscow, Moscow University Publ., 1990, pp. 46–53.
7. Ivanitskiy A.Yu., Vasylyev F.P., Morozov V.A. Metod potochechnoi nevyazki dlya resheniya nekotorykh zadach lineinoi algebry i lineinogo pro-grammirovaniya [Pointwise residual methods for solving some problems of linear algebraic and linear programming]. Computational Mathematics and Mathematical Physics (Zn. Vychisl. Mat. and Mat. Fiz.), 1998, vol. 38, no. 7, pp. 1140–1459.
8. Ivanitskiy A.Yu., Morozov V.A. and Karmazin V.N. Metod potochechnoi nevyazki dlya resheniya nesovmestnykh sistem i neravenstv s priblizhennymi dannymi [Pointwise discrepansy method for solution of inconsistency systems of equations and inequalities with approximate data]. Fundamental and Applied Mathematics, 1998, no. 3, pp. 937–945.
9. Leonov A.S. Metod minimal’noi psevdoobratnoi matritsy dlya resheniya nekorrektnykh zadach lineinoi algebry [Method of a minimum pseudoinverse matix for a solution of Ill-posed problems of linear algebra]. Doklady Akademii nauk USSR, 1985, vol. 285, no. 1, pp. 36–40.
10. Leonov A.S. Metod minimal’noi psevdoobratnoi matritsy: teoriya i chislennaya realizatsiya [Method of a minimum pseudoinverse matix: the theory and numerical realization]. Computational Mathematics and Mathematical Physics (Zn. Vychisl. Mat. and Mat. Fiz.), 1991, vol. 31, no. 10, pp. 1427–1443.
11. Leonov A.S. Ekstraoptimal’nye metody resheniya nekorrektno postavlennykh zadach: obzor teorii i primery [Extra-Optimal Methods for solving Ill-posed Problems: Survey of theory an Examples]. Computational Mathematics and Mathematical Physics (Zn. Vychisl. Mat. and Mat. Fiz.), 2020, vol. 60, no. 6, pp. 985–1012.
12. Morozov V.A. O psevdoresheniyakh [On pseudo-solutions]. Computational and Mathematical Physics (Zn. Vychisl. Mat. and Mat. Fiz.), 1969, vol. 9, no. 6, pp. 196–203.
13. Tikhonov A.N. O reshenii nekorrektno postavlennykh zadach i metode regulyarizatsii [On the solution of Incorrectly Posed problems and the regularization method]. Doklady Akademii nauk USSR, 1963, vol. 151, no. 3, pp. 501–504.
14. Bjorck A. Numerical Methods for Least Squares Problem. SIAM, Philadelphia, 1996, 425 p.
15. Demmel J.W. Applied Numerical Linear Algebra. SIAM, Philadelphia, 1997, 419 p.
16. Forsythe G.E., Malcolm M.A., Moler C.B. Computer Methods for Mathematical Computations. Prentice Hall, Inc., Englewood Cliffs, N.J., 1997, 270 p.
17. Hoffman A. On Approximate Solutions of System of Linear Inequalities. of Research of the Nat. Bureau of Stanfords, 1952, no. 4, pp. 263–265.
18. Ivanitskiy A.Yu., Vasil’ev F.P., Morozov V.A. Pointwise residual methods for solving systems of linear alrebraic equations and inequalities. Ill-posed problems in Natural Sciences. VSP/TVP, Tokyo, 1992, pp. 33–43.
19. Lawson C.L., Hanson R.J. Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, 1974, 340 p.
20. Mechenov A.S. Pseudosolutions of Linear Functional Equations, Springer, 2005, 238 p.
21. Morozov V.A. Methods for Solving Incorrectly Posed Problems, Springer-Verlag, New York, Berlin, Heidelberg, Tokyo, 1984, 257 p.
22. Panyukov A.P., Golodov Y.A. Computing Best Possible Pseudosolutions to Interval Linear Systems of Equations. Reliable Computing, 2018, vol. 19(6), pp. 215–228.
23. Wedin P.-A. Perturbation Theory for Pseudo-Inverses. BIT Numerical Mathematics, 1973, vol. 13, pp. 217–232.
24. Shary S.P. Interval Regularization for Imprecise Linear Algebraic Equations. In: Int. Conf. «Computational and Applied Mathematics 2017» (CAM 2017). Novosibirsk, 2017.
25. Vasylyev F.P., Ivanitskiy A.Yu. In-Depth Analysis of Linear Programming, Kluwer Academic Publishers. Dodrecht, Boston, London, 2001, 312 p.
26. Watkins D.S. Fundamental of Matrix Computations. John Willey, Sons, Inc., New York, 2015, 635 p.

Information about the authors

Alexander Yu. Ivanitskiy – Candidate of Physical and Mathematical Sciences, Professor, Dean of the Faculty of Applied Mathematics, Physics and Information Technology, Chuvash State University, Russia, Cheboksary (ivanitskiy@hotmail.com).

Mikhail V. Kiselev – Candidate of Technical Sciences, Head of the Neuromorphic Computing Laboratory, Chuvash State University, Russia, Cheboksary (mikhail.kiselev@kaspersky.com).

Marina V. Vasilkova – Head of the Center for the Development of Modern Competencies of Children «House of Scientific Collaboration named by S.A. Abrukov», Chuvash State University, Russia, Cheboksary (vasilkovam@mail.ru).

Vladimir V. Ejov – Doctor of Physical and Mathematical Sciences, Professor, Flinders University of South Australia, Australia, Adelaida; Moscow State University, Russia, Moscow (ejovvl@gmail.com).

For citations

Ivanitskiy A.Yu., Kiselev M.V., Vasilkova M.V., Ejov V.V. STABLE METHOD FOR FINDING NORMAL D-PSEUDOSOLUTIONS OF SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS WITH APPROXIMATE DATA AND MEASURES OF THEIR INCONSISTENCY. Vestnik Chuvashskogo universiteta, 2024, no. 2, pp. 54–66. DOI: 10.47026/1810-1909-2024-2-54-66 (in Russian).

Download the full article