基于高斯消元法下的最佳平方逼近算法效率分析
——以一道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矩陣的行列式值遞推關系

Hilbert矩陣的特性：Hilbert矩陣是非奇異的對稱正定矩陣,對Hilbert矩陣的興趣主要在于它是嚴重病態的,其條件數隨n增加而快速增大[7]，其中可以推出希爾伯特矩陣是存在一般的遞推式，其行列式遞推關系式子如下：

det(H1)=1

1.8 切比雪夫正交多項式法

1.9 最佳平方元逼近方法

已知內積空間C[a,b]，si∈C[a,b],i=0,1,2,…,n是一個函數S的一組基函數,對給定f(x)于內積空間內。可以使用由S空間內的一組基作為最佳平方逼近元來逼近f(x)。又因為，最佳平方逼近元與其逼近函數之間的差值函數必須與空間內所有基底均正交，也就引出法方程。

第一步利用前面的權函數為1時建立法方程：

第二步解方程，若S空間下的基底為一組正交基則直接可以得出：

在對于非正交基的情況下，需要用多種方法來解方程。

1.10 基于Cholesky法解方程

2 原問題的模型化解分析

2.1 利用普通最佳平方逼近法(包括克拉默和高斯消元法)

參考上述1.8節有如下步驟：

(2) 列出法方程為：

2.2 正交多項式法

在進行法方程解決時可以采取一些變換使得問題更加容易解決，例如正交化的方法，參考上面切比雪夫多項式概要解法，有如下步驟：

3 原問題的多種解法及其分析

3.1 最佳平方逼近原理的法方程推導

原問題與上述模型化解分析后的問題相比還有一個更特殊的情況，其法方程系數矩陣為希爾伯特矩陣(該矩陣是一個病態矩陣)。由于精度丟失嚴重，也就是說在用高斯消元法時必須要超過50位(大概是65～75位)的高精度地保留每一個系數。

證明如下：

3.2 基于切比雪夫正交多項式解法

3.3 基于克拉默法則的最佳平方逼近解法

在處理線性方程組候，如1.5節，利用克拉默法則處理，對系數矩陣D高精度保存，約為65～75位精度。求出其行列式的值(可用初等變換或者遞歸降次法)，接著分別求出：

3.4 基于高斯消元法的最佳平方逼近解法

在求解線性方程組時，如1.6節，利用高斯消元法處理，對增廣矩陣高精度保存，約為65～75位精度。對該矩陣進行初等行變換，使得該矩陣每一行只有至多三個非零系數。并且呈階梯狀，然后用值進行回代解出xi,i=0,1,2,…,n。這種方法的時間復雜度為O(n3logn)，主要時間消耗取決于高斯消元法的解步驟。

3.5 基于希爾伯特矩陣下的Cholesky分解最佳平方逼近解法

從1.7節與1.10節可知，希爾伯特矩陣在Cholesky分解后的行列式求解直接對角元素求解，所以在求行列式D上面，速度遠快于克拉默法則下的逼近算法，并且求逆矩陣有很快的方法，最后就是兩次矩陣乘以向量計算。在速度上面接近于正交多項式法。

4 實驗數據分析

數據分析一：高斯消元法的最佳平方逼近解法實驗得出如下數據(精確定50位從a0到aN的值):1，5，11，49。

N=1

a0=0.8731273138361809414411498854106499910289

883747998382999

a1=1.6903090292457285878382751718840250134565

174378002425502

Time = 0 ms

N=5

a0=0.9999975939486582685846763425946823321929

666903704104120

a1=1.0000998014733356176039702748826807813478

983478455885884

a2=0.4990191752274595967912934050764328896781

377014278964404

a3=0.1704895390402274037395388939937569965983

870278785847299

a4=0.0348011156854306817682964311699413924928

142869551933373

a5=0.0138720048045378305279050793524077040967

542874206272326

Time = 16 ms

N=11

a0=0.9999999999999987463423319146710162243966

416742831149886

a1=1.0000000000001949307430616128638689626054

795315828574704

a2=0.4999999999925241103946606592514405054594

937593838801533

a3=0.1666666667906898665617204147849644463615

430318949024408

a4=0.0416666655567319300955711299291532518750

378322723241546

略去部分數據

Time = 31 ms

N=49

a0=0.9999966116019126567946264201524917677909

448251223809396

a1=1.0082998895844076840339140654323540177602

496445702108691

略去部分數據

Time = 790 ms

數據分析二：

表1 不同算法的耗時分析比較(試題允許時間：5 000 ms)

數據分析三：

(1) 基于切比雪夫正交多項式解法在試題允許的時間內只能計算出14項以內的系數值；

(2) 基于克拉默法則的最佳平方逼近解法在試題允許的時間內只能計算出6項以內的系數值；

(3) 基于希爾伯特矩陣下Cholesky分解解法在試題允許的時間內只能計算出13項以內的系數值；

(4) 基于高斯消元法的最佳平方逼近解法在試題允許的時間內可輕松計算出試題所要求的系數值。

5 結 語

對于此高精度問題，由于Java引入BigDecimal數據類型，保留高精度計算不再成為一件很難的事情了。在這種情況下，基于高斯消元法的最佳平方逼近解法的效率和精度上要快于和大于希爾伯特矩陣Cholesky分解法，同時也要遠快于和大于基于克拉默法則的最佳平方逼近解法。在精度丟失這一塊要小于希爾伯特矩陣Cholesky分解法，由高精度數據類型的引入，從權衡計算效率和精度而言，高斯消元法的最佳平方逼近還是優于希爾伯特矩陣Cholesky分解法。所以，最優化的解法是基于高精度的高斯消元法的最佳平方逼近解法。而這些不同算法的差距主要體現在求解法方程時所使用的解線性方程組的方式。

[1] 周民強.實變函數論[M].北京:北京大學出版社,2008.

[2] 李國林.切比雪夫最佳一致逼近法及誤差函數特性研究[J].西華師范大學學報(自然科學版),2007,28(3):253-256.

[3] 黃鐸,陳蘭平,王風.數值分析[M].北京:科學出版社,2000.

[4] 劉田,談進.正交多項式逼近下非線性趨勢序列單位根檢驗[J].統計研究,2011,28(4):99-105.

[5] 同濟大學數學系.線性代數[M].北京:高等教育出版社,2011.

[6] 李漢霖.高斯消元法及其在信息學中的應用[J].科技論壇,2015(16):85-86.

[7] 李燕.關于系數矩陣為Hilbert矩陣的線性方程組的思考[J].新疆大學學報(自然科學版),2005,22(2):165-167.

[8] 趙金偉.基于正交多項式核函數方法[J].計算機技術與發展,2012,22(5):177-179.

EFFICIENCYANALYSISOFOPTIMALSQUAREAPPROXIMATIONALGORITHMBASEDONGAUSSIANELIMINATIONMETHOD:ANEXAMPLEOFQUESTIONABOUTACM

Luo Xing Qian Jiawei
(SchoolofSoftwareandCommunicationEngineering,JiangxiUniversityofFinanceandEconomics,Nanchang330032,Jiangxi,China)

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 Xi'an 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.

Numerical calculation analysis ACM-ICPC Best square approaching Algorithm Hilbert matrix

2016-11-30。羅興，本科生，主研領域：軟件工程。錢佳威，本科生。

TP301.6

A

10.3969/j.issn.1000-386x.2017.08.052