A Diagonalisation Algorithm And Its Application In .

Journal of Global Positioning Systems (2003)Vol. 2, No. 1: 35-41A Diagonalisation Algorithm and Its Application in Ambiguity SearchGuochang XuGeoForschungsZentrum Potsdam (GFZ), Dept. 1, Telegrafenberg, 14473 Potsdam, GermanyReceived: 5 March 2002 / Accepted: 22 July 2002Abstract. A diagonalisation algorithm of the leastsquares normal equation is proposed in this paper. Theequivalent observation equations related to thediagonalised normal equations are also derived in detail.For the equivalent observation equations and their normalequations, the related equivalent ambiguity search criteriaare outlined. Theoretical application of the proposedalgorithm in ambiguity search is briefly summarised.Using this algorithm, the ambiguity search turns out to bea search in a diagonal space so that the search can bedone very quickly. Numerical examples to illustrate thediagonalisation process of the normal equation andobservation equation are also given.Key words: GPS, Ambiguity Search, DiagonalisationAlgorithm, Adjustment, Equivalent Equations1 IntroductionIt is well known that the ambiguity resolution is a keyproblem, which has to be solved in GPS static andkinematic precise positioning. Some well-derivedambiguity fixing and searching algorithms have beenpublished during the last decades. A search process isusually needed in the most methods. Generally speaking,the search is an intensive computing and time consumingprocess. Therefore some optimal algorithms have beencreated to reduce the search area and to accelerate thesearch process (e.g. Euler and Landau, 1992; Han andRizos, 1997; Teunissen, 1995). Using the well-knownleast squares ambiguity search criterion for searching inambiguity domain, most modifications are directly basedon the used criterion, e.g. via decomposition (fastmethod, e.g. Euler and Landau, 1992) or de-correlation(LAMBDA method, e.g. Teunissen, 1995). Alternatively,we will first try to work on equivalently diagonalisednormal equations (and observation equations), and thenuse the related equivalent ambiguity search criteria forthe equivalent problems. In this way the search processturns out to be a search in a diagonal space so that thetime consuming on the search is negligible. This methodis originally derived for the so-called general criterion(Xu, 2003) used in KSGSoft (Kinematic/Static GPSSoftware) (Xu et al., 1998); however, it may be directlyused for the least squares ambiguity search criterion, too.2 A Diagonalisation Algorithm of Least SquaresNormal EquationIn least squares adjustment the unknowns can be dividedinto two groups and then solved in a block-wise manner.In practice, sometimes only one group of unknowns is ofinterest, the other group, called nuisance parameters, isbetter to be eliminated, for example because of the largesize. The nuisance parameters can be eliminated blockwisely to obtain an equivalently eliminated normalequation system of the interested unknowns. Using theelimination process twice for the two groups ofunknowns respectively, the normal equation can bediagonalised. The algorithm can be outlined as follows.Linearized observation equation system can berepresented by (Cui et al., 1982; Gotthardt, 1978; Zhou etal., 1997):V L ( A1 X A2 ) 1 , X2 P(1)where L is the observational vector of dimension m, A1and A2 are coefficient matrices of dimension m (n r) andm r, X1 and X2 are unknown vectors of dimension n-r andr, V is residual vector of dimension m, n and m arenumbers of total unknowns and observationsrespectively, P is a symmetric and definite weight matrixof dimension m m. For un-correlated observation vectorL, P is a diagonal matrix.Least squares normal equation of (1) can be formed thenby

Journal of Global Positioning Systems36( A1A2 )T P ( A1 X A2 ) 1 ( A1 X2 A2 )T PL .(2)By denoting A1T PA1 AT PA 2 1A1T PA2 M 11 A2T PA2 M 21W1 A1T PL ,M 2' X 2 B2'M 12 MM 22 Q12 Q Inv ( M ) Q 11QQ22 21(3)(4)From the first equation of (4), one hasX 1 Inv ( M 11 )(W1 M 12 X 2 )Set X1 into the second equation of (4), one gets anequivalently eliminated normal equation of X2M 2 X 2 B2 ,(5)whereM 2 M 22 M 21 Inv ( M 11 ) M 12B2 W2 M 21 Inv ( M 11 )W1(6)Set X2 into the first equation of (4), one gets anequivalently eliminated normal equation of X1(7)(8)0 X 1 B1 ,M 2 X 2 B2 (9) 1 T A2T P( E A1 M 11A1 P ) A2 1 TB2 A2T PL A2T PA1 M 11A1 PL(13) 1 T A2T P ( E A1 M 11A1 P ) L 1 TJ A1 M 11A1 P 1 T 1 TJ 2 ( A1 M 11A1 P )( A1 M 11A1 P ) 1 T 1 T A1 M 11A1 PA1 M 11A1 P 1 T A1 M 11A1 P Jwhere (e.g. Cui et al., 1982; Gotthardt, 1978)Q11 Inv ( M 1 ), Q22 Inv ( M 2 ).3 The Forming of Equivalent Observation Equationsthen one has the properties ofCombining (5) and (7), one has M1 0Of course one may also diagonalise the X1 related normalequation (7) if necessary. To be emphasized is that thenormal equation system (12) is equivalent to the normalequation system (9) and (4). Through the diagonalisationprocess (12) is a diagonal equation system of X1 and X2.The sub-equation of X2 is a diagonal sub-equation. Afully diagonalisation of the normal equation is indeednearly the same as a Gauss-Jordan algorithm to eliminatethe non-diagonal elements of the normal matrix of thenormal equation and to solve the equation. The propertyof (12) could be very useful for many adjustmentapplications.where E is an identity matrix. Denoting (cf. Wang et al.,1988; Xu and Qian, 1986; Zhou, 1985)whereB1 W1 M 12 Inv ( M 22 )W2(12) 1 TM 2 A2T PA2 A2T PA1 M 11A1 PA2X 2 Inv ( M 22 )(W2 M 21 X 1 ) .M 1 M 11 M 12 Inv ( M 22 ) M 210 X 1 B1 .M 2' X 2 B2′ Using the notations of (3), (6) can be rewritten asSimilarly, from the second equation of (4), one hasM 1 X 1 B1 ,B2' is a vector. Then (9) turns out to have a form of M1 0W2 A2T PLM 12 X 1 W1 .M 22 X 2 W2 (11)where M 2' is a diagonal matrix, r is the dimension of X2,the normal equation system (2) is written as M 11 M 21The diagonalisation process can be repeated r 1 times onthe normal equation (5) (or the second equation of (9)), sothat Equation (5) can be fully diagonalised and can berepresented by(10)It is obvious that (4) and (9) are two equivalent normalequations. The solutions of the both equations areidentical. Furthermore, Eq. (9) is a diagonalised normalequation related to the X1 and X2. So we call the processof computing (6) and (8) to form (5) and (7) (i.e. (9)) adiagonalisation process of the normal equation (4).( E J )( E J ) E 2 2 EJ J 2 E 2J J E J(14)

Xu : A Diagonalisation Algorithm and Its Applications in Ambiguity Search[P( E J )]T(4) and (9) are equivalent, so (22) is an equivalentobservation equation of (1). To be emphasised is that theequivalent observation equation (22) is a kind of diagonalequation of X1 and X2. This property is a direct derivationof the diagonal property of the normal equation (9). (E J T )P P P 1 T ( A1 M 11A1 P ) T 1 T PA1 M 11A1 PP P( E J )i.e., matrices J and (E-J) are idempotent and (E-J)TP issymmetric, orJ 2 J,(E J )2 E J(15)T( E J ) P P( E J )Using above derived properties, (13) can be rewritten as:M2 A2T P ( E J ) A2 A2T P ( E J )( E J ) A2(16) A2T ( E J ) T P( E J ) A2B2 A2T P( E J )L A2TT( E J ) PLA2T ( E J ) T P ( E J ) A2 X 2 (17)T( E J ) PLSimilarly, we may repeat above process r 1 times to theobservation equation of X2 (i.e. (18)) step by step and therelated equivalent observation equation can be formed asU 2' L' D2' X 2 ,P' .(23)where D2' is a diagonal matrix, P ' is a diagonal matrixof P, L' is a vector of L, U 2' is a residual vector whichhas the same property as V in (1). Then (22) turns out tohave a form of U 1 L D1 ' ' U 2 L 00 X 1 ,D2' X 2 P 0 ' . 0 P (24)(24) is equivalent to (22). Similarly, (12) is the normalequation of the observation equation (24).then the normal equation (5) can be rewritten asA2T37Numerical examples are given in the appendix toillustrate the diagonalisation process of the normalequation and observation equation.Eq. (17) is the least squares normal equation of thefollowing linear observation equationU 2 L ( E J ) A2 X 2 ,P.(18)where L and P are original observation vector and weightmatrix of (1), U2 is a residual vector which has the sameproperty as V in (1). Eq. (5) is the least squares normalequation of the equivalently eliminated observationequation (18).Similarly, let 1 TI A2 M 22A2 P ,(19)then Eq. (7) is the least squares normal equation of thefollowing linear observation equationU1 L ( E I ) A1 X 1 ,P.(20)Again U1 is a residual vector which has the same propertyas V in (1). DenoteD1 ( E I ) A1 , D2 ( E J ) A2 ,(21)Eq. (18) and (20) can be written together as U1 L D1 U 2 L 00 X 1 ,D2 X 2 P 00 .P (22)Eq. (22) is derived from the normal equation (9),therefore, it is true inversely, i.e. (9) is the least squaresnormal equation of observation equation (22). Becausethe normal equations of (1) and (22) are (4) and (9), and4 Equivalent Ambiguity Search CriteriaSuppose GPS observation equation is (1) and its leastsquares normal equation is (4), where X2 N (N is theambiguity sub-vector) and X1 Y (Y is the rest unknownsub-vector). The least squares ambiguity search (LSAS)criterion (e.g., Teunissen, 1995; Leick, 1995; HofmannWellenhof et al., 1997; Euler and Landau, 1992; Han andRizos, 1997) isδ (dN ) ( N 0 N ) Inv(Q22 )( N 0 N ) ,(25)where N0 is the float solution of the ambiguity sub-vector,dN N0 – N. The ambiguity search is a process to findout a vector N in the searching area so that the value ofδ(dN) reaches the minimum. The general criterion is (Xu, 2003)δ (dX ) ( X 0 X )T Inv (Q )( X 0 X ) ,(26)where X (Y N)T, X0 (Y0 N0)T, dX X0 – X, index 0denotes the float solution. The search in ambiguitydomain is a process to find out a vector X (includes N inthe searching area and Y computed) so that the value ofδ(dX) reaches the minimum. The optimal property of thiscriterion is obvious (Xu, 2003).For the equivalent observation equation (22), the relatedleast squares normal equation is (9). The related leastsquares ambiguity search (LSAS) criterion remains the