直線擬合算法

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

關鍵詞：空間直線；平面直線；擬合

中圖分類號：TP312文獻標識碼：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 引言

直線擬合作為一種基本的數學算法，在不同的學科領域發揮著巨大的作用。文章首先概要介紹二維平面直線的擬合，然后詳細介紹三維空間直線的擬合算法，并進行測試。

2 二維平面直線擬合

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

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

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

■

2) 將括號內各項進行整理合并，并把未知數a，b分離出來，便得

■

3) 解方程組，得

■

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

3三維空間直線擬合

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

■

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

■（1）

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

■ （2）

據此，我們在約束條件（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的三元二次方程式，可以利用非線性方程組一組實根的最速下降法進行計算。以任意可能的一組數為初始值，逐步迭代，在迭代次數允許范圍內，直到滿足所給精度 ，即可求得使（1）式最小的(m，n，p)。

關于最速下降法求函數方程組

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

的一組實根算法為：

1) 定義目標函數為

■

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

3) 計算目標函數值

■

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

5) 計算目標函數在(x1，x2，…，xN)的偏導數

■

再計算

■

6) 計算

■

其中λ=F/D。

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

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

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

■

所以直線

■

即可求得。

4 試驗測試

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

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

■

5 結束語

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

參考文獻：

[1] 同濟大學應用數學系.高等數學[M].5版.北京:高等教育出版社，2005:67-71.

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

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