Graph topology and Types of residual equations for geometric leveling
rri	• •	p	• j • •	Vi	i
Teorija grafov in tipi enačb popravkov v geometričnem nivelmanu
Milivoj Vulic1 , Miha Grudnik2
'Faculty of Natural Science and Engineering, University of Ljubljana, Aškerčeva cesta 12, SI-1000 Ljubljana, Slovenia; E-mail: milivoj.vulic@ntf.uni-lj.si 2 Calcit, Kamnik, Slovenia; E-mail: miha.grudnik@calcit.si
Received: November 20, 2006 Accepted: December 10, 2006
Abstract: In the article graph topology and types of residual equation for geometric leveling are shown. Graph topology tells what is graph and how is formed. The edges in the graph tell us how bench marks are connected between each other and how many edges there is. In third chapter formulas for adjustment by parameter variation for geometric leveling are shown. It is shown, how directly from graphof leveling network incidence matrix A can be formed and what it represents. Like for the matrix A it is presented how to form matrix of normal equation n directly from the graph too. By the condition, that for all measures the mean error is equal to m=m2= = m.
Izvleček: V članku je na kratko opisana topologija grafa in tipi enačb popravkov za geometrični nivelman. Topologija grafa nam govori o tem, kaj je graf in kako je sestavljen. Povezave v grafu nam povedo, kako so reperji med seboj povezani in koliko je teh povezav. V tretjem poglavju so prikazane enačbe za posredno izravnavo geometričnega nivelmana. Prikazano je kako se direktno iz grafa nivelmanske mreže zapiše incidenčna matrika A in kaj nam ta matrika predstavlja. Prav tako je prikazan tudi postopek direktnega zapisa matrike normalnih enačb n direktno iz grafa pod pogojem, da so vsi pogreški meritev enaki m=m2= = ml.
Key words: topology, adjustment, leveling, observation equation, incidence matrix ,loop, bench mark (point)
Ključne besede: topologija, izravnava, nivelman, enačbe popravkov, incidenčna matrika, zanka, reper
Graph topology
Figure 1. shows the marked points A, B, C and D. In our case all four points are connected by edges (edge is oriented link). We will use the expression edge for these connections, to simplify our communications. At the same time we would like to
stress that we are not interested in the form of edges (straight or curved). For us it is important only whether the two given bench marks are connected or not. When they are connected more than ones we speak about multiple connections. Some of the connections on the Figure 1. are marked with an arrow. We speak about oriented edges.
d
Figure 1. Marked points A, B, C and D Slika 1. Označene točke A, B, C in D
Others are the so called un oriented edges. At the leveling network we will deal only with oriented edges. The bench mark can be connected by a close line (loop), as shown on the figure. It is the so called loop. Such loop in leveling network has no influence on adjustment, even when the loop consists of more bench marks. All the edges between two nodes, which they connect, can be presented by only one edge or loop.
d
O
O	o
a	c
O b
Figure 2. Nullgraph Slika 2. Nični graf
Now we search only for the name of the whole picture. We will call it graph. We have to point out that edges AC and BC intersects each other. The intersect point is the fictive point, which in fact is not a point of the graph, but appears only because of drawing the graph (as a graph - drawing effect).
Connections in graph
Let u be number of points in the graph and n number of edges. We will try to find out their relation. Let us mention that these two numbers are independent. If we know u it does not mean that n is known too. Two cases are imposed to us by themselves. First graph without edge n=0 (called nullgraph). The second one represents so called "full graph" in which each bench mark is linked to each other. In that case we are interested in number of edges of the fullgraph. Each of the u bench marks can be connected to (u-1) number of bench marks. Together it represents u (u—1) edges. At the same time we counted
d
Figure 3. Fullgraph Slika 3. Polni graf
each edge twice (forward and backward). That's why the number must be devided by two.
At the end the maximal number of edges in a fullgraph is n = — • u(u — 1)
The nullgraph, where the number of edges is n=0 and a fullgraph, wherethe number of edges
is n = — • 4(4 — 1) = 6 are shown in Figure 2 and 3.
Formulas for adjustment by parameter variation
The best results adjustment by parameter variation are given by the method of least squares (MLS), based on equation (1). This method gives most probable values of unknowns, close to real values. The sum of all residuals, multiplied with correspondent weight, are minimised as shown in equation(l):
® = vTPv = min
(1)
^ = [Vj
Mm] 0
11 ml
0 0
1/wi«JLv«j
= mm
(2)
The residuals are:
v = A- x + 1	(3)
n;1 n;u u;1 n;1
and
v T = (x TAT +1T)	(4)
Where values present:
v	vector of residuals,
A	incidence matrix,
x	vector of unknown parameters,
l	vector of absolutes terms.
Matrix A is an incidence matrix for the graph, which is in leveling equal to de-
sign matrix, showing geometry of leveling network, with elements (-1, +1 in 0).
Where:
— 1 means, that the edge leaves the node
(beginning of the edge), 1 means, that edge enters the node (end
of the edge), 0 means, that node does not take part in the edge.
Graph consists of nodes and edges. There is u nodes - unknowns (points for which we would like to find the heigh ). The edge between nodes I and J, when we measure the heigh diferences is X;—Xj . In the network
node 1
edge 1
edge 2
node 3
Figure 4. Graph with n=6 edges and u= 4 nodes Slika 4. Graf z n=6 povezav in u= 4 vozlišči
graph all the measured edges betwen nodes I and J are substituted by a single equivalent edge IJ. Figure 3 shows the graph with n=6 edges and u= 4 nodes.
Forming A from the leveling
NETWORK GRAPH
From the Figure 3 could be written the incidence matrix A for the graph. It has the row for each edge and coulmn for each node. In our case the matrix is of the dimension 6x4, what means, that it has 6 rows and 4 columns. That matrix shows which nodes are connected to which edges. Input values -1 and +1 in the first row of the matrix show the data of the first edge. Row values are values of the edges while column values present values for nodes. Each row has two elements, which are equal to +1 and -1 all the other are equal to 0. For example, the edge 1 goes from the node 1 to the node 2, therefore a11= —1 and a12= 1 . On that basis we can write down incidence matrix A directly from the graph. Figure 4 shows
incidence matrix A of the network graph on Figure 3.
-1	1	0	0
-1	0	1	0
0	-1	1	0
-1	0	0	1
0	-1	0	1
0	0	-1	1
Figure 4: Incidence matrix A Slika 4: Incidencna matrika A
This occurs as incidence matrix in case when all points (bench marks) are free, what means that no haigh is known. When the height of any point is known, then we have to cancel a coulmn from the matrix. The matrix includes all information of the graph and is therefore called "fullgraph", in which no edge is missing (the fullgraph consists
of n = 1 • u(u — 1) edges). If we delete an
edge from the graph we have to delete a row from the matrix at the same time.
Adjustment depend on the sort and form of the geodetic network, they may difere when already are in the linear format shape size or not. When functions are not linear we have to linearise them by Taylor's series. In geometric leveling is these functions are linear:
The observation equation are:
Li = Li + Vi = Xs — Xz	(5)
Where values present:
A
Li adjusted measure size,
X s denoting end point of adjusted height of the measurement line ,
XZ denoting starting point of adjusted height,
Vj - residual of L;.
Equations, correspondent to the graph on Figure 3:
V! + L1 = X2 - X! =- X! + X2 (6)
V2 + L2 = X3 - X1 = - X1........+ X3
V3 + L3 = X3 - X2 =.......- X 2 + X3
V4 + L4 = X4 — Xi = — Xi..................+ X4
v5 + L5 = X4 — X2 =........— X2.........+ X 4
v6 + l6 = x 4 — x3 =.................— x3 + x4
We have to introduce approximate height values:
XS — XS + XS XZ — X0 + XZ
The equation (5) reads:
v, + L — X0 - X0 + (xs - XZ )
and the residuals are:
vi — X S - X Z - Li + X0 - XZ
vi — X S — X Z — 1
(7)
(8)
(9)
(10) (11)
vt=l-xs-l ■JCz+(Xs0-X°-Z,.) (12)
v-v-'
k
It causes, that the vector of free article is equal to:
l^Xl+Xl-L,	(13)
respectively:
l,=AX0-L,
(14)
Observation equations, which correspond to the graph on Figure 3 are:
Vj =l-x2-l-x, +{Xq2 -X*-L,)
h
v2=l-x3-l ■x.+iXl-XÎ-L,)
v3 =l-x3-l-x2 +(X30 -X20 -Z3)
v4 = 1 • x4 -1 • x1 + (X4° -X° -L4)
v5=l-x4-l •x2+(X4°-X2°-Z5)
v6=l-x4-l-x3+(X40-X3°-Z6) 15)
We can present the equation (16) in two different ways: Dimension of the matrix matrix = matrix .
v = A■ x + l
n;1 n;u u;1 n;1
rows x columns (16)
Vi"		"-1	1	0	0"			V
V2		-1	0	1	0	*1		h
V3		0	-1	1	0	*2	+	h
	=							h
V4		-1	0	0	1	*3		
v5		0	-1	0	1			h
V6_		0	0	-1	1_			h
(17)
and
v = A- x + A- X0 - L
n;1 n;u u;1 n;u u;1 n;1
(18)
V1		-1	1	0	0			-1	1	0	0			A
V2		-1	0	1	0	V		-1	0	1	0			L2
V3 V4	=	0 -1	-1 0	1 0	0 1	*3	+	0 -1	-1 0	1 0	0 1		-	¿3 ¿4
V5		0	-1	0	1			0	-1	0	1			L5
V6.		0	0	-1	1			0	0	-1	1			A
(19)
As known height can not be determined only from height differences. One or more of the heights X; must be known. (Then the corresponding known X; should be deleted from A it's colum i ).
Therefore we have to exclude each known height from the list of unknown heights. What means, that in incidential matrix A have to exclude each known height. As already mentioned the column in matrix represents a point (bench mark). Let's presume that in the previous graph the first
point is known. It means that it's height is determined. Therefore we have to delete the first column from the matrix A at gives us a new shape.
A=
1	0	0
0	1	0
-1	1	0
0	0	1
-1	0	1
0	-1	1
(20)
Since matrix A is changed, the whole observation equation in matrix - matric form changes into following form:
V1		" 1	0	0"			V
V2		0	1	0			h
					x2		
V3		-1	1	0		+	h
	=				X,		
V4		0	0	1	J		h
					X4		
V5		-1	0	1			h
		0	-1	1_			Je.
(21)
As matrix A is alreday fixed we have to form a weighting matrix P. Elements for that matrix are given with following equations. This matrix is diagonal andincludes the following articles.
Qt
cofactor matrix of measured values, which in our case are P = Q-
1
p t = —y when mean square errors are given,
m,
J_ 1
p t = — at equable ground (differences between separate standing rooms are constant),respectively:
p j = — at no equable ground (differences between separate standing rooms ni are not constant).
Where:
p i measure weight, ml mean square error,
d t difference between two measured points (bench marks), n number of standing rooms between two measured points (bench marks).
P =
Mm]	0	0	0	0	0
0	\lm]	0	0	0	0
0	0	Mm]	0	0	0
0	0	0	Mm]	0	0
0	0	0	0	Mm]	0
0	0	0	0	0	Mm,
(22)
(23)
(24)
(25)
n;n
n;n
When all elements, that correspond to (MLS) are available, we can transfer normal equation from the
equation (1) (® = VT Pv = min).
We insert equations (3), (17), and (22) into equation (1) and get the following expression. O = (xtAt + IT )P{Ax + I) = xtAtPAx + ItPAx + xTATPI + ITPI	(27)
We differentiate that expression and make it null. We get extreme point for the function. In our case we need the minimum point.
0 = dO) = dxTATPAx + xTATPAdx + dxTATPI + ITPAdx 0 = dO) = 2dxTATPAx + 2dxTATPI 0 = dxT(ATPAx+ATPI)
-V-J
AtPAx+AtPI=0
Settling the previous expression we get normal equations. ATPAx + ATP = 0
N = AT P A = At Q— A
u;u u;n n;n n;u u;n n n\u
n = At PI = At Q— I
u;1 u;n n;nn;1 u;n n n;1
Where:
N matrix of normal equations n vector of free elements for normal equations
Record N = A PA = A Qtl A in matrix form:
(28)
(29)
(30)
(31)
(32)
(33)
N =
10-10-1 0 0 110 0-1 0 0 0 1 1 1
Mm]	0	0	0	0	0 "	' 1	0	0
0	Mm)	0	0	0	0	0	1	0
0	0	Mm)	0	0	0	-1	1	0
0	0	0	Mm)	0	0	0	0	1
0	0	0	0	Mm)	0	-1	0	1
0	0	0	0	0	Mm)	0	-1	1
(34)
Forming N from the levelling
NETWORK GRAPH
Matrix for normal equation N we can also put down directly from the graph, under the condition, that for all measures the mean error is equal to m1=m2= = mt ! Along the diagonal of the matrix we put down how many edgess has each node (in our case the node 1 has three edges, that's why we will put number 3 as the first element of the diagonal). Since we know N is a simetric matrix, we will put it's elements (articles) above the diagonal. With element (article) -1 we describe, that two separate bench marks are connected between (direction of the arrows is not important), with 0 we point out that there is no edge between them.
Further is presented the matrix N , put down directly from the graph on the Figure 5. In our case the height of the first node is a priori defined, therefore for the further calculation we have to eliminate shaded part, representing that node. Number from 1 to 4 (in the row and column) represent names of nodes in graph.
Matrix N is positively defined det (N) >0.
n;n
Matrix N is simetrical:
N =
	1	2	3	4
1	3	-1	-1	-1
2		3	-1	-1
3			3	-1
4				3
Direct record of the simetric matrix N for the graph on the Figure 5.
nude 1
Figure 5. Direct record of the simetric matrix N Slika 5. Direktni zapis simetrične matrike N
Record n = A1 PIU= ATQU1I in matrix form
	"1	0	-1	0	-1	0
n =	0	1	1	0	0	-1
	0	0	01	1	1	1
in shortened form: Nx +n = 0
Nx = -n
N-1Nx = -N-1n x = - N~ln O = N-1
xx
Respectively: x = -Q n
xx
1/ mf	0	0	0	0	0 "	'fx		
0	1/ mf	0	0	0	0	fi		
0	0	1 /mf	0	0	0	/3		
0	0	0	1 /mf	0	0	/4		
0	0	0	0	1/ mf	0	/5		
0	0	0	0	0	1/ mf	fs		(35)
	(36)	mn	mean error		of adjusted sizes			
	(37)		= moyj	i =»W 9 a			VI	(46)
(38)
(39)
m
mean error of residuals.
(40)
(41)
Equations for calculating estimated accuracy a posteriori:
m0 = .
m
\vTPv
n-u
(42)
mediate error of weight unit
n — u number of supernumerary measurement
m. = m

m
mean error of unknown sizes
mVi = mo
(43)
(44)
(45)
Conclusion
In the article graph topology and types of residual equation for geometric leveling are shown. Graph topology tells what is graph and how is formed. The edges in the graph tell us how bench marks are connected beet-wen each other and how many edges there is. It is also shown that we can reduce the leveling network only to the nodes, because » so called » loops (links that start and finish at the same point) dont have any influence to the adjustment.
In third chapter formulas for adjustment by parameter variation for geometric leveling are shown. It is shown, how directly from graph of leveling network incidence matrix A can be formed and what is represents. Matrix A is the incidence matrix for the graph and represent the same as design matrix in leveling. Design matrix represents geometry of the leveling network. Despite that we can estimate the design of the network also with
the number of the edges that are realised between nodes from the full graph. Like for the matrix A it is represented how to form matrix of normal equation N directly from the graph. By the condition, that for all measures the mean error is equal to m1=m2=^=ml .
Zaključek
Teorija grafov in tipi enačb popravkov v geometričnem nivelmanu
V članku je na kratko opisana topologija grafa in tipi enačb popravkov za geometrični nivelman. Topologija grafa nam govori o tem, kaj je graf in kako je sestavljen. Povezave v grafu nam povedo, kako so reperji med seboj povezani in koliko jih je. Razvidno je tudi, da lahko nivelmanske mreže zreduci-
ramo samo na vozlišča, saj tako imenovane zanke (povezave ki se začnejo in končajo v isti točki) na izravnavo nimajo vpliva.
V tretjem poglavju so prikazane enačbe za posredno izravnavo geometričnega ni-velmana. Prikazano je kako se direktno iz grafa nivelmanske mreže zapiše incidenčna matrika A in kaj nam ta matrika predstavlja. Matrika A je incidenčna matrika za graf, ki je v nivelmanu isto kot design matrika. Design matrika nam podaja geometrijo nivelmanske mreže. Design mreže lahko ocenjujemo tudi s tem, koliko povezav je realiziranih med vozlišči od polnega grafa. Prav tako je prikazan tudi postopek direktnega zapisa matrike normalnih enačb N direktno iz grafa pod pogojem, da so vsi pogreški meritev enaki m1=m2=...=ml.
References
Bajc Drago, Pisanski Tomaž (1985): Najnujnejše o grafih. Ljubljana: Društvo matematikov in fizikov.
Mihailovič K., Vračarič K. (1985): Geodezija III. Gradevinski Fakultet Beograd, Beograd.
Strang Gilbert, Borre Kai (1997): Linear algebra, Geodesy and GPS. Wellesley: Wellesley- Cambridge Press.
Vulič Milivoj (2004): Izbrana poglavja iz izravnalnega računa (zapiski s predavanj), Ljubljana.