BSU bulletin. Mathematics, Informatics
, EXACT ALGORITHMS FOR IMPLEMENTATION OF THE LEAST ABSOLUTE DEVIATIONS METHOD BASED ON THE DESCENT THROUGH THE NODAL STRAIGHT LINES // BSU bulletin. Mathematics, Informatics. - 2017. №4. . - С. 21-32.
EXACT ALGORITHMS FOR IMPLEMENTATION OF THE LEAST ABSOLUTE DEVIATIONS METHOD BASED ON THE DESCENT THROUGH THE NODAL STRAIGHT LINES
Работа выполнена при финансовой поддержке гранта РФФИ, проект № 17-01-00315а.
Algorithms for the exact solution of the problem of estimating the parame- ters of linear regression models by the least absolute deviations method are described. They are based on the descent through the nodal straight lines. The proposed algorithms include common descent, descent with the use of sparse matrices and descend with the use of sparse matrices and taking into considera- tion its directions. These algorithms significantly outperform the best-known brute-force search and can be effectively used in practice. The computational complexity of the descent algorithm for nodal straight lines is assessed. The scheme of the algorithm is provided. We have carried out a comparative analy- sis of the proposed algorithm based on descent through the nodal straight lines and Waisfeld approximate algorithm by Monte Carlo method of statistical test- ing. The examples of practical implementation of the proposed algorithms are described.
the least absolute deviations method; linear regression model; algorithm; nodal point; nodal straight line; hyperplane; computational complex- ity.
List of references: