The paper is in line with research, that was founded and developed in the papers of I.I. Eremin, V.V. Vasin, L.D.Popov, E.A. Berdnikova, I.M. Sokolinskaya, A.V. Ershova, E.A. Nurminskii and others. The main result is a new version of the Fej´er-type mapping constructed for finding a non-negative solution to a system of linear algebraic equations. This mapping combines the operation of orthogonal projection onto a linear space of solutions to a system of linear algebraic equations and the operation of projection onto a non-negative orthant, without using the traditional positive slice operation, but instead using an elementwise operation of calculating the absolute value. The global linear convergence of the obtained algorithm is proved and its asymptotic constant is estimated. Computational experiments demonstrate significantly faster convergence of the studied mapping compared to the mapping using the positive slice operation. A description of the algorithm, its theoretical justification and the results of computational experiments are presented.
Keywords: Fejér-type processes, systems of linear equations and inequalities
Received May 9, 2025
Revised June 9, 2025
Accepted June 16, 2025
Published online June 26, 2025
Funding Agency. The results of section 7 were obtained at the Institute of Problems in Mechanical Engineering of the Russian Academy of Sciences, funded by the Russian Science Foundation (project no. 23-41-00060).
Vladimir Ivanovich Erokhin, Dr. Phys.-Math. Sci., Prof., Mozhayskii Military-Space Academy, St. Petersburg, 197198 Russia, e-mail: erohin_v_i@mail.ru
Grigoriy Shalikovich Tamasyan, Cand. Sci. (Phys.-Math.), Mozhayskii Military-Space Academy, St. Petersburg, 197198 Russia; Institute for Problems in Mechanical Engineering of the Russian Academy of Sciences, St. Petersburg, 198178 Russia, e-mail: grigoriytamasjan@mail.ru
Nikolay Anatolievich Stepenko, Cand. Sci. (Phys.-Math.), St. Petersburg State University, St. Petersburg, 199034 Russia, e-mail: nick_st@mail.ru
REFERENCES
1. Erokhin V.I., Laptev A.Y., Lisitsyn N.V. Reconciliation of material balance of a large petroleum refinery in conditions of incomplete data. J. Comput. Syst. Sci. Int., 2010, vol. 49, no. 2, pp. 295–305. https://doi.org/10.1134/S1064230710020140
2. Kuzichkin N., Erohin V., Lisitsyn N. Reconcilitation of experimental data for balance calculation in chemical-technological systems. Adv. Chem. Engin. Res., 2013, vol. 2, no. 4, pp. 98–105.
3. Dennis-J.E. Jr., Schnabel R.B. Numerical methods for unconstrained optimization and nonlinear equations. London, Englewood Cliffs, 1983, 378 p. ISBN-10: 0136272169 . Translated to Russian under the title Chislennyye metody bezuslovnoy optimizatsii i resheniya nelineynykh uravneniy, Moscow, Mir Publ., 1988, 440 p. ISBN: 5-03-001102-1 .
4. Albert A. Regression and the Moor—Penrose pseudoinverse. London, New York, Academic Press, 1972, 180 p. Translated to Russian under the title Regressiya, psevdoinversiya i rekurrentnoye otsenivaniye, Moscow, Nauka Publ., 1977, 224 p.
5. Golub G.H., Van Loan Ch.F. Matrix computations, 3rd edt. Baltimore, London, the John Hopkins Univ. Press, 1996, 728 p. ISBN-10: 0801854148 . Translated to Russian under the title Matrichnyye vychisleniya, Moscow, Mir Publ., 1999, 548 p. ISBN: 5-03-002406-9 .
6. Lawson Ch.L. Solving least squares problems. New Jersey, Englewood Cliffs, Prentice-Hall, Inc., 1974, 340 p. Translated to Russian under the title Chislennoye resheniye zadach metoda naimen’shikh kvadratov, Moscow, Nauka Publ., 1986, 232 p.
7. Demyanov V.F., Vasiliev L.V. Nedifferentsiruyemaya optimizatsiya [Nondifferentiable optimization]. Moscow, Nauka Publ., 1981, 384 p.
8. Dem’yanov V.F., Rubinov A.M. Osnovy negladkogo analiza i kvazidifferentsial’noye ischisleniye [Fundamentals of nonsmooth analysis and quasidifferential calculus]. Moscow, Nauka Publ., 1990, 432 p. ISBN: 5-02-014241-7 .
9. Eremin I.I. Generalization of the relaxation method of Motzkin — Agmon. Uspekhi Mat. Nauk, 1965, vol. 20, no. 2(122), pp. 183–187 (in Russian).
10. Eremin I.I., Mazurov V.D. Nestatsionarnye protsessy matematicheskogo programmirovaniya [Nonstationary processes of mathematical programming]. Moscow, Nauka Publ., 1979, 288 p.
11. Vasin V.V., Ageev A.L. Ill-posed problems with a priori information, Utrecht, VSP, 1995, 255 с. ISBN: 906764191X . Original Russian text was published in Vasin V. V., Ageev A. L. Nekorrektnye zadachi s apriornoi informatsiei, Yekaterinburg, Ural Publ. House “Nauka”, 1993, 264 p. ISBN: 5-7691-0390-6 .
12. Eremin I.I. Theory of linear optimization. Berlin, Walter de Gruyter, 2002, 248 p. ISBN: 906764353X . Original Russian text was published in Eremin I. I. Teoriya lineinoi optimizatsii, Yekaterinburg, Izd-vo UrO RAN, 1998, 247 p.
13. Vasin V.V., Eremin I.I. Operators and iterative processes of Fejér type. Theory and applications, Berlin, NY, Walter de Gruyter, 2009, 155 p. ISBN: 3110218186 . Original Russian text was published in Vasin V. V., Eremin I. I. Operatory i iteratsionnye protsessy feierovskogo tipa. Teoriya i prilojeniya, Izhevsk, Regul. Khaot. Dinamika, 2005, 200 p. ISBN: 5-93972-427-2 .
14. Eremin I.I. Feyyerovskiye metody dlya zadach vypukloy i lineynoy optimizatsii [Fejer methods for problems of convex and linear optimization]. Chelyabinsk, Izd. tsentr YuUrGU, 2009, 199 p. ISBN: 978-5-696-04003-5 .
15. Eremin I.I., Popov L.D. Fejér processes in theory and practice: recent results. Russian Math. (Iz. VUZ), 2009, vol. 53, no. 1, pp. 36–55.
16. Vasin V.V. Iterative FejДer processes in ill-posed problems. Comput. Math. Math. Phys., 2020, vol. 60, no. 6, pp. 938–949. https://doi.org/10.1134/S0965542520060111
17. Vasin V.V. Solving nonlinear inverse problems based on the regularized modified Gauss — Newton method. Dokl. Math., 2022, vol. 105, no. 3, pp. 175–177. https://doi.org/10.1134/S1064562422030103
18. Vasin V.V. Fejér-type iterative processes in the constrained quadratic minimization problem. Proc. Steklov Inst. Math., 2023, vol. 323, suppl. 1, pp. S305–S320. https://doi.org/10.1134/S008154382306024X
19. Berdnikova E.A., Popov L.D. On the application of decomposition in the implementation of Fejér methods for solving large systems of linear inequalities on the MVS-100. Algoritmy i Prog. Sredstva Paral. Vych.: sb. nauch. trudov, Yekaterinburg, IMM UrO RAN, 2000, vol. 4, pp. 51–62 (in Russian).
20. Eremin I.I., Popov L.D. Parallel Fejér methods for strongly structured systems of linear inequalities and equations. Algoritmy i Prog. Sredstva Paral. Vych.: sb. nauch. trudov, Yekaterinburg, IMM UrO RAN, 2000, vol. 6, pp. 57–82 (in Russian).
21. Eremin I.I., Sokolinskaya I.M. Fejér iterative processes for improper linear programming problems. Mat. Struktury i modelirovaniye, 2002, vol. 9, pp. 1–17 (in Russian).
22. Berdnikova E.A., Eremin I.I., Popov L.D. Distributed FejДer processes for systems of linear inequalities and problems of linear programming. Automat. Remote Control, 2004, vol. 65, no. 2, pp. 168–183. https://doi.org/10.1023/B:AURC.0000014714.97496.79
23. Ershova A.V., Sokolinskaya I.M. A parallel algorithm for solving strong separability problem on the basis of Fejér mappings. Vych. Metody Prog., 2011, vol. 12, no. 4, pp. 423–434 (in Russian).
24. Nurminski E.A. Fejér algorithms with an adaptive step. Comput. Math. Math. Phys., 2011, vol. 51, no. 5, pp. 741–750. https://doi.org/10.1134/S0965542511050137
25. Golikov A.I., Evtushenko Yu.G. Theorems on alternatives and their application to numerical methods. Comput. Math. Math. Phys. 2003, vol. 43, no. 3, pp. 338–358.
26. Ashmanov S.A., Timokhov A.V. Teoriya optimizatsii v zadachakh i uprazhneniyakh [Optimization theory in problems and exercises]. Moscow, Nauka Publ., 1991, 448 p. ISBN: 5-02-014253’0 .
27. Vasil’ev F.P., Ivanitskii A.Yu. Linejnoe programmirovanie [Linear programming]. Moscow, MCNMO, 2020, 412 p. ISBN: 978-5-4439-1359-9 .
Cite this article as: V.I. Erokhin, G.Sh. Tamasyan, N.A. Stepenko. An accelerated Fejér-type process for finding a non-negative solution to a system of linear algebraic equations. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol.31, no. 3, pp.121–137
