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

罗 兴 钱佳威

(江西财经大学软件与通信工程学院 江西 南昌 330032)



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

罗 兴 钱佳威

(江西财经大学软件与通信工程学院 江西 南昌 330032)

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

数值计算分析 ACM-ICPC 最佳平方逼近 算法 Hilbert矩阵

0 引 言

1 预备计算数学知识

1.1 函数的p-范数下的距离(L^p空间)

1.2 最佳一致逼近

1.3 最佳平方逼近函数

1.4 正交多项式

1.5 克拉默法则

含有n个未知数x1,x2,…,xn的n个线性方程的方程组:

与二、三元线性方程组类似，它的解可以用n阶行列式不等于零，即：

那么，上述方程组有唯一解：

其中Dj(j=1,2,…,n)是把系数行列式D中第j列的元素用方程组右端的常数项代替后所得到的n阶行列式，即[5]:

1.6 高斯消元法解方程

若用初等行变换将增广矩阵(AB)化为(CD)，则AX=B与CX=D是同解方程组。所以我们可以用初等行变换把增广矩阵转换为行阶梯阵，然后回代求出方程的解[6]。

1.7 Hilbert矩阵……