直線擬合算法

摘要：不管是平面直線擬合，還是空間直線擬合，直線擬合的應(yīng)用范圍都很廣泛。文章對兩種不同維度的直線擬合算法進(jìn)行了綜合介紹。其中空間直線擬合根據(jù)最佳平方逼近原理和最速下降法以及所給離散點的均值求得，并通過試驗驗證了此算法運算結(jié)果的正確性。該算法因為同時考慮了x、y、z不同方向的誤差，所以準(zhǔn)確度較高；同時因為采用了最速下降法，所以精確度可以任取，運算速度較快。

關(guān)鍵詞：空間直線；平面直線；擬合

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2009)04-0864-04

The Linear Fitting Algorithm

XU Hai-tao， GAO Cai-xia

(China University of Mining Technology， Beijing 100083， China)

Abstract: No matter the fitting of plane linear or space linear， the application area of linear fitting is very widely.The paper will comprehensively introduction these two different dimension linear fitting. On the basis of the principle of the least-squares approximation and steepest descent method and the average of the given discrete points， the space linear fitting can obtained， at the same time through a test proved the algorithm is correct. Because the algorithm simultaneously considered the errors of x， y， z direction ，so it has the high degree of accuracy ; meanwhile the algorithm adopted steepest descent method， so its precision can arbitrary get and the speed of calculation is faster.

Key words: space linear; plane linear; the fitting

1 引言

直線擬合作為一種基本的數(shù)學(xué)算法，在不同的學(xué)科領(lǐng)域發(fā)揮著巨大的作用。文章首先概要介紹二維平面直線的擬合，然后詳細(xì)介紹三維空間直線的擬合算法，并進(jìn)行測試。

2 二維平面直線擬合

設(shè)P1，P2 PN是平面上的N個離散點，求取這些點的擬合直線f(x)=ax+b只需采用最小二乘法即可。即計算偏差的平方和

■為最小。具體運算步驟如下：

1) 對上式的a，b分別求偏導(dǎo)，因為所求M為極值，所以偏導(dǎo)函數(shù)要等于零：

■

2) 將括號內(nèi)各項進(jìn)行整理合并，并把未知數(shù)a，b分離出來，便得

■

3) 解方程組，得

■

即得平面直線擬合方程f(x)=ax+b

3三維空間直線擬合

設(shè)空間內(nèi)方向向量為s=(m，n，p)，且過(x0，y0，z0)點的直線方程為

■

當(dāng)點(xi，yi，zi)不在直線上時，分別記其在x方向、y方向、z方向的誤差為εi1，εi2，εi3。作為最佳擬合直線，必須同時考慮這三個方向的誤差，根據(jù)最佳平方逼近原理，最佳直線應(yīng)滿足：

■（1）

最小。因為各測量點在x方向、y方向、z方向的誤差εi1、εi2、εi3服從正態(tài)分布，所以最佳直線應(yīng)滿足：

■ （2）

據(jù)此，我們在約束條件（1）（2）下，求由離散點(xi，yi，zi)i=1，2……N所確定的最佳直線。因為

{x-x0，y-y0，z-z0}×{m，n，p}=0

即

■

故而，有

■

對于第i個測量點(xi，yi，zi)，則有

■

εi1，εi2，εi3分別是(xi，yi，zi)在x、y、z方向的誤差，方程組（I）減去（II），得

■

方程組（III）對i作和，有

■

化簡可得

■

由約束條件（2）則得

■

由方程組（II）

■

■

相類似，有

■

故

■

此時上式是只含有m，n，p的三元二次方程式，可以利用非線性方程組一組實根的最速下降法進(jìn)行計算。以任意可能的一組數(shù)為初始值，逐步迭代，在迭代次數(shù)允許范圍內(nèi)，直到滿足所給精度 ，即可求得使（1）式最小的(m，n，p)。

關(guān)于最速下降法求函數(shù)方程組

fi(x1，x2，…，xN)=0，i=1，2，…，N

的一組實根算法為：

1) 定義目標(biāo)函數(shù)為

■

2) 選取一組初值x1，x2，…，xN。

3) 計算目標(biāo)函數(shù)值

■

4) 若F<ε，則X=(x1，x2，…，xN)T即為方程的一組實根，過程結(jié)束；否則繼續(xù)。

5) 計算目標(biāo)函數(shù)在(x1，x2，…，xN)的偏導(dǎo)數(shù)

■

再計算

■

6) 計算

■

其中λ=F/D。

重復(fù)步驟2)~5)，直到滿足精度要求為止。針對空間直線擬合算法，此時方程組的個數(shù)為一個，未知數(shù)的個數(shù)為三個。

在上述過程中，如果D=0，則說明遇到了目標(biāo)函數(shù)的局部極值點，此時可改變初值再試一試。

此時方向向量(m，n，p)便可求得，又因為直線過點

■

所以直線

■

即可求得。

4 試驗測試

根據(jù)上述算法進(jìn)行C++編程，并對試驗數(shù)據(jù)進(jìn)行測試，測試數(shù)據(jù)如表1，迭代次數(shù)為5000，精度為0.0001。

通過計算可得方向向量為（0.0208776，0.0329005，0.0430876），且過點（10.91，16.77，22.87），所以擬合直線方程為：

■

5 結(jié)束語

文章詳細(xì)介紹了平面和空間離散點的直線擬合算法，并對空間直線擬合算法進(jìn)行了改進(jìn)，在提高準(zhǔn)確度的前提下控制了精確度。盡管如此，該算法還存在一定的缺陷，比如隨著迭代次數(shù)的增加和精度要求的提高，系統(tǒng)的計算量將不斷增大，會影響其運算效率。

參考文獻(xiàn)：

[1] 同濟大學(xué)應(yīng)用數(shù)學(xué)系.高等數(shù)學(xué)[M].5版.北京:高等教育出版社，2005:67-71.

[2] 何渝.計算機常用數(shù)值算法與程序（C++版）[M].北京:人民郵電出版社，2003.

[3] 杜明芳.空間直線擬合[J].北京印刷學(xué)院學(xué)報，1996，4(2).