羅 興 錢佳威

(江西財(cái)經(jīng)大學(xué)軟件與通信工程學(xué)院 江西 南昌 330032)

?

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

羅 興 錢佳威

(江西財(cái)經(jīng)大學(xué)軟件與通信工程學(xué)院 江西 南昌 330032)

針對(duì)ACM數(shù)值計(jì)算分析類的防AK試題，一般可以利用克拉默法則最佳平方逼近、高斯消元最佳平方逼近、Hilbert矩陣Cholesky分解平方逼近和切比雪夫多項(xiàng)式正交等方法求解。以第39屆ACM-ICPC西安邀請(qǐng)賽的一道防AK題為例，對(duì)這幾種典型算法進(jìn)行實(shí)驗(yàn)分析，并在反復(fù)實(shí)驗(yàn)中對(duì)算法參數(shù)進(jìn)行修正，然后進(jìn)行質(zhì)量與效率的分析。測(cè)試結(jié)果表明，高精度高斯消元最佳平方逼近解法求解ACM數(shù)值計(jì)算分析類的防AK試題，優(yōu)于克拉默法則最佳平方逼近、普通高斯消元最佳平方逼近和Hilbert矩陣Cholesky分解平方逼近，是解決數(shù)值計(jì)算分析類問(wèn)題的一種有效方法。

數(shù)值計(jì)算分析 ACM-ICPC 最佳平方逼近 算法 Hilbert矩陣

0 引 言

1 預(yù)備計(jì)算數(shù)學(xué)知識(shí)

1.1 函數(shù)的p-范數(shù)下的距離(L^p空間)

1.2 最佳一致逼近

1.3 最佳平方逼近函數(shù)

1.4 正交多項(xiàng)式

1.5 克拉默法則

含有n個(gè)未知數(shù)x1,x2,…,xn的n個(gè)線性方程的方程組:

與二、三元線性方程組類似，它的解可以用n階行列式不等于零，即：

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

其中Dj(j=1,2,…,n)是把系數(shù)行列式D中第j列的元素用方程組右端的常數(shù)項(xiàng)代替后所得到的n階行列式，即[5]:

1.6 高斯消元法解方程

若用初等行變換將增廣矩陣(AB)化為(CD)，則AX=B與CX=D是同解方程組。所以我們可以用初等行變換把增廣矩陣轉(zhuǎn)換為行階梯陣，然后回代求出方程的解[6]。

1.7 Hilbert矩陣的行列式值遞推關(guān)系

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

det(H1)=1

1.8 切比雪夫正交多項(xiàng)式法

1.9 最佳平方元逼近方法

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

第一步利用前面的權(quán)函數(shù)為1時(shí)建立法方程：

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

在對(duì)于非正交基的情況下，需要用多種方法來(lái)解方程。

1.10 基于Cholesky法解方程

2 原問(wèn)題的模型化解分析

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

參考上述1.8節(jié)有如下步驟：

(2) 列出法方程為：

2.2 正交多項(xiàng)式法

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

3 原問(wèn)題的多種解法及其分析

3.1 最佳平方逼近原理的法方程推導(dǎo)

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

證明如下：

3.2 基于切比雪夫正交多項(xiàng)式解法

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

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

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

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

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

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

4 實(shí)驗(yàn)數(shù)據(jù)分析

數(shù)據(jù)分析一：高斯消元法的最佳平方逼近解法實(shí)驗(yàn)得出如下數(shù)據(jù)(精確定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

略去部分?jǐn)?shù)據(jù)

Time = 31 ms

N=49

a0=0.9999966116019126567946264201524917677909

448251223809396

a1=1.0082998895844076840339140654323540177602

496445702108691

略去部分?jǐn)?shù)據(jù)

Time = 790 ms

數(shù)據(jù)分析二：

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

數(shù)據(jù)分析三：

(1) 基于切比雪夫正交多項(xiàng)式解法在試題允許的時(shí)間內(nèi)只能計(jì)算出14項(xiàng)以內(nèi)的系數(shù)值；

(2) 基于克拉默法則的最佳平方逼近解法在試題允許的時(shí)間內(nèi)只能計(jì)算出6項(xiàng)以內(nèi)的系數(shù)值；

(3) 基于希爾伯特矩陣下Cholesky分解解法在試題允許的時(shí)間內(nèi)只能計(jì)算出13項(xiàng)以內(nèi)的系數(shù)值；

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

5 結(jié) 語(yǔ)

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

[1] 周民強(qiáng).實(shí)變函數(shù)論[M].北京:北京大學(xué)出版社,2008.

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

[3] 黃鐸,陳蘭平,王風(fēng).數(shù)值分析[M].北京:科學(xué)出版社,2000.

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

[5] 同濟(jì)大學(xué)數(shù)學(xué)系.線性代數(shù)[M].北京:高等教育出版社,2011.

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

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

[8] 趙金偉.基于正交多項(xiàng)式核函數(shù)方法[J].計(jì)算機(jī)技術(shù)與發(fā)展,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。羅興，本科生，主研領(lǐng)域：軟件工程。錢佳威，本科生。

TP301.6

A

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