基于高斯消元法下的最佳平方逼近算法效率分析——以一道ACM试题为例

EFFICIENCY ANALYSIS OF OPTIMAL SQUARE APPROXIMATION ALGORITHM BASED ON GAUSSIAN ELIMINATION METHOD:AN EXAMPLE OF QUESTION ABOUT ACM

针对ACM数值计算分析类的防AK试题,一般可以利用克拉默法则最佳平方逼近、高斯消元最佳平方逼近、Hilbert矩阵Cholesky分解平方逼近和切比雪夫多项式正交等方法求解。以第39届ACM-ICPC西安邀请赛的一道防AK题为例,对这几种典型算法进行实验分析,并在反复实验中对算法参数进行修正,然后进行质量与效率的分析。测试结果表明,高精度高斯消元最佳平方逼近解法求解ACM数值计算分析类的防AK试题,优于克拉默法则最佳平方逼近、普通高斯消元最佳平方逼近和Hilbert矩阵Cholesky分解平方逼近,是解决数值计算分析类问题的一种有效方法。

Aiming at the anti-AK problem of ACM numerical analysis, we generally use the best square approaching based on Cramer Rule, the best squared approaching of the Gaussian elimination, the square approaching under Cholesky decomposition of the Hilbert matrix and the Chebyshev polynomial Orthogonal method solution. In this article, we take an anti-AK problem in the 39th ACM-ICPC Xian Invitational Tournament as an example to analyze the typical algorithms and modify the algorithm parameters in repeated experiments. The test results showed that the best squared approximation of the Gaussian elimination method was an effective method to solve anti-AK problem of ACM numerical analysis, which is better than the best square approximation of the ordinary Gaussian elimination and the square approximation of the Cholesky factorization of the Hilbert matrix.