Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems
We consider discrete linear Chebyshev approximation problems in which the unknown parameters of linear function are fitted by minimizing the least maximum absolute deviation of errors. Such problems find application in the solution of overdetermined systems of linear equations that appear in many pr...
Main Author: | |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2020-12-01
|
Series: | Mathematics |
Subjects: | |
Online Access: | https://www.mdpi.com/2227-7390/8/12/2210 |
_version_ | 1797544848162553856 |
---|---|
author | Nikolai Krivulin |
author_facet | Nikolai Krivulin |
author_sort | Nikolai Krivulin |
collection | DOAJ |
description | We consider discrete linear Chebyshev approximation problems in which the unknown parameters of linear function are fitted by minimizing the least maximum absolute deviation of errors. Such problems find application in the solution of overdetermined systems of linear equations that appear in many practical contexts. The least maximum absolute deviation estimator is used in regression analysis in statistics when the distribution of errors has bounded support. To derive a direct solution of the problem, we propose an algebraic approach based on a parameter elimination technique. As a key component of the approach, an elimination lemma is proved to handle the problem by reducing it to a problem with one parameter eliminated, together with a box constraint imposed on this parameter. We demonstrate the application of the lemma to the direct solution of linear regression problems with one and two parameters. We develop a procedure to solve multidimensional approximation (multiple linear regression) problems in a finite number of steps. The procedure follows a method that comprises two phases: backward elimination and forward substitution of parameters. We describe the main components of the procedure and estimate its computational complexity. We implement symbolic computations in MATLAB to obtain exact solutions for two numerical examples. |
first_indexed | 2024-03-10T14:06:21Z |
format | Article |
id | doaj.art-e6b2cb21668a4f87a41ed6216f8dfde9 |
institution | Directory Open Access Journal |
issn | 2227-7390 |
language | English |
last_indexed | 2024-03-10T14:06:21Z |
publishDate | 2020-12-01 |
publisher | MDPI AG |
record_format | Article |
series | Mathematics |
spelling | doaj.art-e6b2cb21668a4f87a41ed6216f8dfde92023-11-21T00:37:37ZengMDPI AGMathematics2227-73902020-12-01812221010.3390/math8122210Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation ProblemsNikolai Krivulin0Faculty of Mthematics and Mechanics, St. Petersburg State University, Universitetskaya Emb. 7/9, 199034 St. Petersburg, RussiaWe consider discrete linear Chebyshev approximation problems in which the unknown parameters of linear function are fitted by minimizing the least maximum absolute deviation of errors. Such problems find application in the solution of overdetermined systems of linear equations that appear in many practical contexts. The least maximum absolute deviation estimator is used in regression analysis in statistics when the distribution of errors has bounded support. To derive a direct solution of the problem, we propose an algebraic approach based on a parameter elimination technique. As a key component of the approach, an elimination lemma is proved to handle the problem by reducing it to a problem with one parameter eliminated, together with a box constraint imposed on this parameter. We demonstrate the application of the lemma to the direct solution of linear regression problems with one and two parameters. We develop a procedure to solve multidimensional approximation (multiple linear regression) problems in a finite number of steps. The procedure follows a method that comprises two phases: backward elimination and forward substitution of parameters. We describe the main components of the procedure and estimate its computational complexity. We implement symbolic computations in MATLAB to obtain exact solutions for two numerical examples.https://www.mdpi.com/2227-7390/8/12/2210discrete linear Chebyshev approximationminimax problemvariable eliminationdirect solutionmultiple linear regressionleast maximum absolute deviation estimator |
spellingShingle | Nikolai Krivulin Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems Mathematics discrete linear Chebyshev approximation minimax problem variable elimination direct solution multiple linear regression least maximum absolute deviation estimator |
title | Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems |
title_full | Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems |
title_fullStr | Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems |
title_full_unstemmed | Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems |
title_short | Using Parameter Elimination to Solve Discrete Linear Chebyshev Approximation Problems |
title_sort | using parameter elimination to solve discrete linear chebyshev approximation problems |
topic | discrete linear Chebyshev approximation minimax problem variable elimination direct solution multiple linear regression least maximum absolute deviation estimator |
url | https://www.mdpi.com/2227-7390/8/12/2210 |
work_keys_str_mv | AT nikolaikrivulin usingparametereliminationtosolvediscretelinearchebyshevapproximationproblems |