离散数据的最佳直线求解方法

　　一、引　言

　　在实际应用中,我们经常要对仪器仪表进行定标,对传感器的特征曲线进行测定,无论是定标仪器仪表还是测定特征曲线,都不可避免地要将大量的离散数据进行线性拟合,但我们知道,对同一组数据,拟合准则不同,得到的拟合直线也不同。在许多情况下,定标直线的拟合、线性度的计算是以实验点对拟合直线的最大偏差作为考察标准的[1],这时直线拟合显然是在最大偏差准则下进行的。过去由于在此准则下拟合直线计算困难,作为替代,人们采用较易计算的最小二乘法[2,3],但最小二乘法的原则是使实验点与拟合直线的偏差的平方和最小,它并不能保证最大偏差最小,即使直线经平移处理也是如此,这一点可以从后面的例子看到。

　　本文提出的这种直线拟合方法是建立在最大偏差最小准则的基础上,但它避免了复杂的计算,因此它具有实际应用价值,下面我们简述这种算法的原理和应用。

　　二、算法原理

　　我们把实验数据视为X-Y平面上一个有限离散点的集合W,即:

　　这样,问题就归结为对一组离散点集合W,寻找一条直线：

　　使之满足

　　该问题称为离散点的最小最大一次逼近,或称为最佳一致一次逼近,式(1)称为最佳一次逼近多项式或归佳直线,满足式(2)的xi叫作最大偏差点[4]。

　　最佳直线的存在性和唯一性等性质已由Chebyshev定理解决,但求解它却不是件容易的事。绝大部分问题需用迭代方法解决(例如Remes方法),用这种方法解决问题相当费力并且在很大程度上要依赖于研究者的经验和直觉[4]。

　　这里我们将给出一个求解最佳直线的非迭代方法,此方法具有简单、直观、实用的优点。

　　在实际情况中,要定标的实验数据都是一些有限的离散点,下面我们就利用非迭代方法来寻找这些离散点的最佳直线。

　　1.确定特殊边界点集合S

　　我们把平面上的可包围集合W并具有最短周长的一条封闭曲线叫作集合W的边界,在此定义下,W的边界显然是个凸多边形(如图1)。这个凸多边形的顶点P1、P2、…PM(M≤N)叫做特殊边界点,而这些特殊边界点构成了集合S,同时注意到集合S是集合W的子集,即:

　　在边界上可能还有其它的离散点,它们可以称为边界点,但只有位于凸多边形顶点的离散点才是特殊边界点。

　　2.确定最大偏差点集合D′

　　这一步,我们只在集合S内考虑问题,如图2。设Pi、Pi+1是凸多边形一条边的两端点,Pj是距这条边最远的顶点,用Pj、Pi、Pi+1这三点构成一个集合,以Di表示。凸多边形共有M个边,照此方法可构造M个这样的集合,显然,它们都是集合S的子集: