第40卷第10期2015年10月武汉大学学报·信息科学版
Geomatics and Information Science of Wuhan University
Vol.40No.10
Oct.2015
收稿日期:2013-12-
10项目来源:国家自然科学基金资助项目(41274010
)。第一作者:谢建,博士生,主要从事测量平差与测量数据处理研究。E-mail:xiej
ian@csu.edu.cnDOI:10.13203/j.whugis20130764文章编号:1671-8860(2015)10-1344-
05等式约束对病态问题的影响及约束正则化方法
谢 建1 朱建军1
1 中南大学地球科学与信息物理学院,湖南长沙,410083
摘 要:有效利用参数间已知的等式约束信息能够提高最小二乘解的精度,消除秩亏,但是等式约束能否消除或减弱平差模型的病态性尚不明了,
由此提出了一种通过消除部分参数将等式约束病态问题转化为无约束问题的方法。然后分析了等式约束对病态问题的影响,用简单实例证明了加入约束后,系统可能呈现良态或病态,它的性态由原设计阵和等式约束共同决定,并提出了求解等式约束病态问题的诊断-正则化两步方法。最后用一个数值实例验证了该方法的可行性。关键词:等式约束;秩亏;病态;影响分析;正则化中图法分类号:P207.2     文献标志码:A
  大地测量数据处理中,
常出现秩亏和病态等现象。解决秩亏问题的常用方法是增加参数间坐标基准的加权等式约束或参数的加权二次范数最小准则,
求出特定基准下的最小范数最小二乘解[
1]
。解病态问题也是附加参数间的加权二次范数约束,
使观测残差和参数范数间达到平衡而获得稳定的正则化解[2]
。可见,上述不适定问题都
是通过增加约束信息来得到适定的解。这种信息有参数的一次式,
即参数间的线性等式约束,也有参数的二次式,即参数的二次范数。
对于秩亏数为d的无约束平差问题,是附加
d个线性无关的等式约束消除秩亏[1]
。若秩亏问
题本身有s个线性无关的约束,
那么只要添加d-s
个等式约束[3]
。病态问题的正则化准则是对所有的参数施加二次约束,通过压缩解的长度来
减弱最小二乘解的不稳定性。但已有文献对等式约束是否减弱病态性少有研究,侧重于研究含有线性等式约束的病态问题的算法。Sarkar在约束最小二乘解前面乘以一个压缩因子,以减小病
态约束问题的方差[4]
;Jürg
en在约束最小二乘解的基础上,将最小二乘解用Sarkar解代替,解的形式和约束最小二乘解相同,但是计算非常复
杂[5]
;钟震利用椭圆约束的方法得到了约束病态问题的有偏估计[6]
;谢建等用正则化的思想得到
了附等式约束病态问题的正则化解,其形式与附
加椭圆约束的有偏估计相同[
7]
。但是,上述方法是对所有的参数施加二次范数约束,都没有讨论等式约束本身能否消除或者减弱系统的病态性,
以及附加等式约束后模型的病态程度与哪些因素有关。本文首先将等式约束的病态问题通过消除部分参数转化为无约束问题,
分析无约束问题设计阵的病态性,然后给出了等式约束病态问题求解的方法。
1 等式约束对秩亏问题的影响
  经典的测量平差函数模型和随机模型为
[8]
L=AX+Δ(1
)E(L)=AX,D(L)=σ20
P-
1(2)式中,L、Δ分别表示n维观测向量和误差向量;
X为u维参数向量;A为n×u设计矩阵;σ2
0为单位权方差;P为观测权矩阵。根据设计矩阵A的性质,可以分为设计阵良态、秩亏和病态三种情况。下面对前两种情况的求解进行分析。1.1 设计阵A是良态矩阵的最小二乘解
观测方程(1
)相应的误差方程式为[8]
:V=A^X-L
(3
)  当设计阵A是良态矩阵时,
若观测误差服从正态分布,在最小二乘准则φmin(V)=VTPV下,不需增加额外的信息,可以直接得到唯一且稳定的
最小二乘解[
8]
:^XLS=N-1 w(4
)式中,N=ATPA,w=ATPL,
分别表示法方程矩阵
 第40卷第10期谢 建等:等式约束对病态问题的影响及约束正则化方法
和右端项。
1.2 设计阵A秩亏时的自由网平差解
当平差系统缺乏必要的基准条件时,设计阵
的秩小于待估参数的个数,即R(A)=t<u。在最
小二乘准则下,法方程矩阵求逆不唯一,具有无穷
多组解。一般是对参数附加约束信息,得到在某
种参考基准或准则下的最优解。一般附加如下s
个(s=u-t)等式约束条件[1]:
STPx^X=0(5)
式中,S是法矩阵N的s个零特征值所对应的线
性无关的特征向量所构成的矩阵;Px称为基准
权,反映了不同的基准约束。在最小二乘准则下,
可以得到秩亏自由网平差的解为[1]:
^X
RD=(N+P
xSSTPx
)-1 w(6)
  等式约束条件(5)给平差问题提供了必要的基准条件,从而得到了该基准约束下的最小二乘解,但添加的约束条件的个数应等于或大于秩亏数才能得到唯一的解[3]。
2 等式约束对病态问题的影响
  当设计阵A良态时,它的列向量间线性无关;秩亏时,它的列向量间存在线性相关性,若秩亏数为s,那么其中的s列向量可以表示成其他各列的线性组合。而病态矩阵是介于良态矩阵和秩亏矩阵之间的一种,它的列向量间存在近似的线性相关性,线性模型在最小二乘准则下,病态性与复共线性是等价的[9]。方程的病态会引起最小二乘解的不稳定性,一般是对解向量的范数进行限定,使参数估值的长度处于一定的范围。常用的求解病态问题的方法是附加参数的最小范数条件,构成Tikhonov正则化准则[2]:
φmin(^X)=VTPV+α^XTR^X(7)  对式(7)求极小,得到相应的正则化解为:
^X
R=
(N+αR)-1 w(8)  可以证明,对于病态法方程矩阵,附加适当的对角矩阵,可以显著降低法方程的病态,得到的正则化解是最小二乘解的压缩有偏估计[1,10]。无约束情况下,病态问题最
小二乘解的长度不受限制,使解对误差扰动很敏感。增加解的范数约束(7)可以改善法方程矩阵的性质,得到均方误差意义下更优的解。这说明病态问题中对所有参数施加二次约束是可以减弱或消除法方程的病态性的。§1.2的分析表明,附加等式约束能消除秩亏,下面分析给病态问题增加参数间的一次等式约束条件能否减弱方程的病态性。
等式约束病态问题的函数模型表示为[4-6]:
n×1
=A
n×u
u×1
-L
n×1
,C
s×u
u×1
-W
s×1
=0
s×1
(9)  这里假设约束条件相容且线性无关,若约束关系中不包含某些参数,则可以使约束矩阵中对应于该参数的列为零向量。常用的解模型(9)的方法是采用准则函数(7),得到如下形式的等式约束正则化解[6,7]:
^X
R=
(N-1
r-N-1rCTN-1ccCN-1r
)w+N-1
rCTN-1ccW
(10)
式中,Nr=N+αR;Ncc=CN-1
rCT
。可见上述方法是对所有参数进行正则化,没有考虑等式约束本身能否减弱或消除病态性。为了便于分析,先将等式约束平差模型转变成一个无约束平差模型[11]。可以在s个约束条件中消去其中任意s个参数,剩下的t=u-s个参数可由这s个参数表达。式(9)中对参数分类后的等价形式为[1
1]:
n×1
=A1
n×t
X1
t×1
+A2
n×s
X2
s×1
-L
n×1
(11)
C1
s×t
X1
t×1
+C2
s×s
X2
s×1
-W
s×1
=0
s×1
(12)式中,A=A1A
[]
;C=C
1C
[]
X=
[XT
1XT2
]T,由式(12)可以得到:
X2=-C-12C1X1+C-12W(13)  代入式(11),即得:
V=BX1-f(14)
式中,B=A1-A2C-1
2C1
;f=L-A
2C-1
2W
新的设计矩阵B是原有的病态设计阵A和良态约束阵C的子矩阵的线性组合,它的性质由原设计阵的病态性、参数的约束个数及约束的形式共同决定,有可能呈病态或良态。对每个不同的实际测量问题,等式约束是由先验信息或者经验知识获得,随问题的不同而不同。在对参数分组时,没有特定的标准,因此系数阵B的病态性难以从数学上给出直接的证明过程。也就是说,在A1、A2、C1、C2均不定的情况下,难以直接计算B矩阵的行列式、条件数、特征值或条件指标等反映病态程度的指标。这里可以用两个极端的例子来说明等式约束对法方程矩阵病态性的影响。
1)当有s=u-1个参数间的约束条件,即转
换后的无约束平差模型只有t=1个参数时,由B的表达式易知,B是一个n维向量,式(14)相当于仅含一个参数的平差模型,它的最小二乘解为:
^X
1=N-11BTPf
(15)式中,N1=BTPB是一常数,总可以求得稳定的凯利逆,从而这一约束消除了法方程的病态性。
由式(15)得到^X1的估值以后,代入式(13)可以得到其他参数的估值。
2)当附加如下的约束条件时:
^X
2=d
(16)
武汉大学学报·信息科学版2015年10月
式中,d表示s×1维常数向量。这种情况实际上是已知某部分参数的值,求剩余t个参数的估值。容易知道,C1是一个s×t的全零矩阵。此时,模型(11)、(12)等价于:
V=A1X1+A2d-L(17)即B=A1,B的性质完全由A1所决定。设矩阵A用列向量表示为:
A1=[α1,…,αt],A2=[αt+1,…,αt+s]
式中,αi(i=1,2,…,t+s)为n维列向量。若A病态,则一定存在不全为0的常数ki(i=1,2,…,t+s),使得:
k1α1+…+ktαt+…+kt+sαt+s≈0(18)成立。那么A1是否病态又分为如下几种情况:1)存在不全为0的常数ki(i=1,2,…,t),使得k1α1+…+ktαt≈0,当且仅当kt+1=kt+2=…=kt+s=0时,才有kt+1αt+1+…+kt+sαt+s=0成立。也就是说,矩阵的复共线性仅存在于前面t列,后面的s列线性无关,A1的病态性和A完全一致,即cond(A1)=cond(A)。即附加式(17)所示的约束条件完全不能减弱新的误差方程(14)的病态性,需要求正则化解。
正则化的约束条件2)跟情形1)完全相反,矩阵的复共线性仅存在于后面s列,而前面t列线性无关,那么A1是一个良态矩阵,设条件数为M。附加式(17)这一约束条件后,可以直接按照普通最小二乘法求解。
3)除去情形1)和情形2)以外的情况,这时,不仅子矩阵A1的列向量间存在复共线性,子矩阵A
2的列向量间也存在复共线性,或者A1和A2的列向量间互相存在近似线性相关关系。由于情形1)、2)分别是两种极端情况,那么A1的病态性处于两种情形之间,即M<cond(A1)<cond(A)。
从以上两例可以看出,线性消元后,新模型(14)的系数阵是否病态不仅与原设计矩阵A本身的性质有关,而且与约束矩阵有关。随着以上两个因素发生变化,新模型设计阵B可能是良态或病态,且病态程度不会比原设计阵A的性质更差,满足如下关系:1≤cond(B)≤cond(A)。
3 等式约束病态问题的正则化解
  对于附有等式约束的病态模型,可以根据式
(12)先选取任意s个参数,将其表达成另外t个参数的线性组合,然后组成形如式(14)的无约束误差方程式。为了确定新的误差方程设计阵是否病态,可以采用病态问题诊断的一系列方法,如行列式法、方差因子扩大法和条件数法[12]、条件指标-方差分解比法[13]、特征分析法[14]等。
这里采用文献[12]所给出的条件数法来判断新的设计阵是否病态。当条件数小于100时,可以认为没有病态;当条件数处于100~1 000之间,认为具有中等病态性;当条件数大于1 000
时,认为病态性严重。对于没有病态性的设计阵,可以直接运用最小二乘法求解t个已选参数,代入式(13)求消去的参数。对于具有病态设计阵的方程(14),采用Tikhonov正则化方法求解:
^X
1=
(N
1+αR
)-1 BTPL(19)其中,N1=BTPB为转换后的法矩阵;R为描述函数光滑性的正则化矩阵,本文取R为单位阵,这里只对剩余参数进行正则化;α为正则化因子,常用的正则化因子选取方法有岭迹法[1]、GCV(generalized cross validation)法[15]、L曲线法[16,17]、Helmert方差分量估计法[18]、均方误差极小法[19]。这里采用均方误差极小化方法确定正则化因子。^X1的均方误差为[19]:
MSE(^X1)=trace(σ20N-1R-ασ20N-2R+
α2 N-1RXXTN-1R)(20)其中,trace(·)表示矩阵的求迹;NR=N1+αR。式(20)中含有参数真值X,在求解时是未知的。均方误差极小化求解的具体实现过程是:首先计算最小二乘解,将其作为近似真值代入均方误差表达式(20)中,用最优化方法求均方误差极小时的正则化因子,得到新的正则化估值;然后将新的估值作为真值,用同样的方法求解极小化问题,直到最后两次解的差值小于给定的阈值后停止迭代。
4 算例分析
采用文献[17]的算例,在这个算例中,有10个观测值,5个未知数,其真值为X=[1 1 1 1 1],观测噪声Δ~(0,1),由随机发生器生成,观测值由L=AX+Δ生成。各观测值等精度,权矩阵为单位阵。系数矩阵A如下:
A=
2.0-2.0-2.0-1.0-1.0 1.0 3.0 5.0 4.0 4.0-5.0 4.0 1.0 2.5 3.2 1.0 7.0-1.0 2.0 3.01.0 1.0 1.0 4.0 4.0-3.0-3.0-2.0-2.0-2.01.0-1.05-1.0-0.5-0.5 0.4 1.5 2.5 2.01 2.0-9.5 8.5 2.4 7.0 8.4 0.49 12.7-3.0 3.0 5.熿
6431
 第40卷第10期谢 建等:等式约束对病态问题的影响及约束正则化方法
  它的条件数为cond(ATA)=1.289 2×105,严重病态。分别附加如下的约束条件,分析不同的约束条件对消除或减弱方程病态性的影响,并计算各种情形下的解:①Xi+Xi+1=2,i=1;
②Xi+Xi+1=2,i=1,2;③Xi+Xi+1=2,i=1,2,3;④Xi+Xi+1=2,i=1,2,3,4。
对4种不同的等式约束条件,其约束个数分别为1、2、3、4个,那么被消去参数的个数与约束的个数相同。消去这些参数后,剩余的参数个数分别为4、3、2、1个,在求均方误差项时,分别求得4种约束情形下剩余参数的均方误差。由于被消去参数的个数不同,所以不能同等地比较各种情形下的均方误差。由于是模拟计算已知真值的大小,可以计算真误差,表1中真误差的平方和随着约束的增加而显著减小。
表1 不同约束条件下病态问题的计算结果
Tab.1 Results of the Ill-posed Problems with Different Constraints
X1X2X3X4X5cond(N1)MSE(^Xk)‖X-^X‖
真值1 1 1 1 1-0.00000.0000无约束最小二乘解-0.418 4 13.095 5 4.250 2 4.843 8-4.958 3 1.28×105 320.882 5 209.151 8无约束正则化解(α=1.43)1.523 6 0.448 2 1.086 8 0.784 3 1.328 3 1.28×105 0.673 5 0.740 5约束①(α=1.27)1.437 1 0.562 9 1.114 6 0.952 6 1.271 9 8.51×104 0.149 9 0.471 4约束②(α=0)1.234 9 
0.765 1 1.234 9 1.499 8 1.173 3 35.285 7 0.078 3 0.443 6约束③(α=0)1.121 9 0.878 1 1.121 9 0.878 1 1.119 8 12.55 0.022 2 0.073 8约束④(α=0)1.119 1 0.880 9 1.119 1 0.880 9 1.119 1 1 0.024 8 0.070 9
  从以上算例可以看出,增加约束能减弱或者消除法方程的病态性。随着约束条件的增加,新的平差系统的病态性逐渐减弱,当约束条件增加到2个时,法方程的条件数已经低于100的阈值,病态性完全消除了,此时可以直接采用最小二乘进行平差计算。
5 结 语
对于附有等式约束的病态问题,通过消除部分参数的方法将其转变为一个无约束病态问题。在新的观测方程中,用计算实例分析了设计阵的病态性,并指出新的设计阵可能是病态的,也有可能是良态的,取决于原设计矩阵和约束矩阵的性质。它的条件数介于原设计阵的条件数和1之间。利用条件数法来判断新的设计阵的病态程度,对于仍然呈病态的模型,采用Tikhonov正则化方法求解参数,正则化因子由均方误差极小化方法确定。然后利用约束条件式得到剩余参数的估值。数值实验证明本文提出的方法是有效的、可行的。
参 考 文 献
[1] Cui Xizhang.Generalized Surveying Adjustment[M].Wuhan:Wuhan University Press,2001:163-
170(崔希璋.广义测量平差[M].武汉:武汉大学
出版社,2001:163-170)
[2] Tikhonov A N.Regularization of Ill-posed Problem[J].Dokl Akad Nauk SSSR,1963,151(1):49-
52
[3] Xie Jian,Zhu Jianjun.A New Approach to Con-strained Rank-deficient Free Network Adjustment
[J].Engineering of Surveying and Mapping,2009,18(2):9-11(谢建,朱建军.约束秩亏网平差
的一种新算法[J].测绘工程,2009,18(2):9-11)[4] Sarkar N.A New Estimator Combining the RidgeRegression and the Restricted Least Squares Meth-
ods of Estimation[J].Comm Statist Theory Meth-
ods,1992,21(7):1 987-2 000
[5] Jürgen G.Restricted Ridge Estimation[J].Statis-tics &Probabilities Letters,2003,65(1):57-64[6] Zhong Zhen.Study on the Restricted Biased Esti-mation in the Linear Model[D].Chongqing:Chongqing University,2005(钟震.线性模型中的
约束型有偏估计的研究[D].重庆:重庆大学,2005)
[7] Xie Jian,Zhu Jianjun.A Regularized Solution andStatistical Properties in Ill-posed Problems with E-
quality Constraints[J].Geomatics and Information
Science of Wuhan University,2013,38(12):1 440-
1 444(谢建,朱建军.等式约束病态模型的正则化
解及其统计性质[J].武汉大学学报·信息科学版,2013,38(12):1 440-1 444)
[8] Group of Adjustment Discipline in School of Geode-sy and Geomatics of Wuhan University.Error The-
ory and Foundation of Surveying Adjustment[M].
Wuhan:Wuhan University Press,2003(武汉大学测
绘学院测量平差学科组.误差理论与测量平差基础
[M].武汉:武汉大学出版社,2003)
[9] Guo Jianfeng.Diagnosis and Processing of Ill-pos-
7431
武汉大学学报·信息科学版2015年10月
edness in Adjustment Model[M].Zhengzhou:In-formation Engineering University,2002(郭建锋.测量平差系统病态性的诊断与处理[D].郑州:信息工程大学,2002
)[10]Zhang 
Jinhuai.Parameter Estimation of LinearModels and Its Improvement[M].Changsha:Na-tional University of Defense Technology,1992(张金槐.线性模型参数估计及其改进[M].长沙:国防科技大学出版社,1992
)[11]Yu Zongchou.The Uniformity Theory 
of Estima-tion of Variance-Covariance Components[J].ActaGeodaetica et Cartographica Sinica,1991,20(3):161-171(於宗俦.方差-协方差分量估计的统一理论[J].测绘学报,1991,20(3):161-
171)[12]Chen Xiru,Wang 
Songgui.Modern Regression A-nalysis[M].Hefei:Anhui Education Press,1987(陈希孺,王松桂.近代回归分析[M].合肥:安徽教育出版社,1987
)[13]Gui Qingming,Yao Shaowen,Gu Yong
wei,et al.A New Method to Diagnose Multicollinearity Basedon Condition Index and Variance DecompositionProportion(CIVDP)[J].Acta Geodaetica et Carto-grap
hica Sinica,2006,35(3):210-214(归庆明,姚绍文,
顾勇为,等.诊断复共线性的条件指标-方差分解比法[J].测绘学报,2006,35(3):210-214)[14]Golub G H,Heath M,Wahba 
G.GeneralizedCross-Validation as a Method for Choosing 
a GoodRidge Parameter[J].Techno Metrics,1979,21(2):215-
223[15]Han Songhui,Du Lan,Gui Qingming
,et al.Charac-teristics Analysis Approach for Multicollinearity Diag-nosis and Its Applications in Orbit Determination ofGEO Satellites[J].Acta Geodaetica et CartographicaSinica,2013,42(1):19-26(韩松辉,杜兰,归庆明,等.诊断复共线性的特征分析法及其在GEO定轨中的应用[J].测绘学报,2013,42(1):19-
26)[16]Hansen P C.Analy
sis of Discrete Ill-posed Prob-lems by Means of the L-curve[J].SIAM Review,1992,34(4):561-
580[17]Wang Zhenjie.Determining 
the Ridge Parameter ina Ridge Estimation Using 
L-curve Method[J].Geo-matics and Information Science of Wuhan Univer-sity,2004,29(3):235-238(王振杰.用L-曲线法确定岭估计中的岭参数[J].武汉大学学报·信息科学版,2004,29(3):235-
238)[18]Zhu Jianjun,Tian Yumiao,Tao Xiaojing
,et al.U-nited Expression and Solution of Adjustment Crite-ria with Parameters[J].Acta Geodaetica et Carto-grap
hica Sinica,2012,41(1):8-13(朱建军,田玉淼,陶肖静,等.带准则
参数的平差准则及其统一与解算[J].测绘学报,2012,41(1):8-
13)[19]Xu Peiliang.Determination of Surface Gravity 
A-nomalies Using 
Gradiometric Observables[J].Geo-phy
s J Int,1992,110(2):321-332Influence of Equality 
Constraints on Ill-conditioned Problems andConstrained Reg
ularization MethodXIE Jian1
 ZHU Jianj
un11 Department of Geosciences and Info-physics,Central South University,Chang
sha 410083,ChinaAbstract:The accuracy 
of least square estimation can be improved and the rank deficient problem canbe eliminated by using equality constraints properly.However,the influence of equality constraints inan ill-conditioned problem is not clear.Therefore,a method to transform the equality-constrained ill-posed to unconstrained problem by eliminating 
apart of the parameters is proposed in this paper.Wefirstly analyzed the influence of equality constraints on an ill-posed problem.Subsequently,the newsystem with equality constraints was verified by means of an example as either ill-conditioned or notdepending on the original design matrix and equality constraint
s.We finally propose a diagnosis-regu-larization two-step approach to solve the equality-constrained ill-posed problem and validate its feasi-bility 
with a simulated data experiment.Key 
words:equality constraints;rank deficient;ill-condition;influence analysis;regularizationFirst author:XIE Jian,PhD candidate,specializes in surveying adjustment and modern surveying data processing.E-mail:xiejian@csu.edu.cnFoundation supp
ort:The National Natural Science Foundation of China,No.41274010.8
431

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。