IZ ZNANOSTI IN STROKE 
UDK (UDC) 52833:528.14:528.181 
IZ AGEODETS H 
v 
REZ Z RAZCEPOM PO 
SI LARNI VREDN STI 
Tomaž Ambrožič, mag. Goran Turk 
FNT-Oddelek za montanistiko, FAGG-Oddelek za 
gradbeništvo, Ljubljana 
Prispelo za objavo: 1.6.1994 
Izvleček 
V članku sta prikazani dve metodi za reševanje sistemov 
enačb popravkovpo metodi najmanjših kvadratov: klasična 
metoda z nonnalnirni enačbami in novejši razcep po 
singularnih vrednostih. Izračun neznank za razcep po 
singularnih vrednostih je izpeljan v celoti. Podane so 
prednosti in pomanjkljivosti obeh metod. 
Ključne besede: geodetske mreže, izravnanje, normalne 
enačbe, razcep po singularnih vrednostih 
Abstract 
The least square problem may be solved by two different 
methods: by the traditional method of normal equations, 
or by a relatively new singular value decomposition method. 
The singular value decomposition method is described in 
detail. Advantages and shortcomings of both methods are 
discussed. 
Keywords: adjustment, normal equations, singular value 
decomposition, surveying networks 
UVOD 
v 
e v 18. stoletju so za optimalno rešitev enačb popravkov vpeljali metodo 
najmanjših kvadratov. Rešitev po metodi najmanjših kvadratov pa lahko 
izračunamo na različne načine: 
o z normalnimi enačbami 
o z ortogonalnimi razcepi 
- Householderjeva transformacija 
- QR razcep 
- razcep po singularnih vrednostih in drugi. 
V nadaljevanju si bomo ogledali metodo z normalnimi enačbami in podrobno predstavili razcep po singularnih vrednostih. 
Geodetski vestnik 38 (1994) 2 
METODA NAJMANJŠIH KVADRATOV 
pri izravnavi geodetskih mrež tvorimo sistem linearnih enačb popravkov (Feil 1989) 
Ai = ! 
kjer je: 
A 
X -
1,:,:.l 
11X l 
n -
u -
matrika koeficientov enačb popravkov 
vektor neznank 
vektor opazovanj 
število merjenj (enačb) m 
število neznank. 
(1) 
Sistem (1) je predoločen, ker je število enačb večje od števila neznank. Ta sistem 
nima rešitve. Problem rešimo tako, da uporabimo metodo najmanjših kvadratov, ki jo 
je prvi predstavil Gauss leta 1796. Zapišimo vsoto kvadratov popravkov opazovanj 
n n n 
2 A 2 2 
s = S(x) = I, vi = I, ( Ij -- IJ = I, (AXj -- i) 
i=l i=l i=l 
Če predpostavimo, da so opazovanja slučajne spremenljivke, porazdeljene z 
normalno porazdelitvijo, izračunamo najbolj verjetne vrednosti neznank po metodi 
najmanjših kvadratov. To dokažemo z metodo največje podobnosti (Maximum 
likelihood) (Press et al. 1992). Takrat iščemo minimum funkcije . 
SCHREIBERJEVO PRAVILO 
(2) 
Vsaka enačba popravkov ima utež, ki je pozitivna po definiciji. Praktično bi bilo, če bi imele vse enačbe popravkov utež enako ena. Zahtevi zadostimo, če 
namesto enačb popravkov tvorimo ekvivalentne enačbe popravkov (Mihailovic 1981). 
Te lahko tvorimo na več načinov. Najpogosteje uporabljamo Schreiberjeva pravila. 
Tretje pravilo pravi, da enačbo popravkov 
v = ax + by + ... + ut + f z utežjo p (3a) 
zamenjamo z ekvivalentno enačbo 
v' = qv = qax + qby + ... + qut + qf z utežjo p/q2. (3b) 
Če naj imajo vse enačbe popravkov utež enako ena, izračunamo vrednost faktorja q, 
s katerim moramo pomnožiti koeficiente leve in desne strani posamezne enačbe (3a), 
po enačbi: 
%2 = 1 • q = 'P 
Pogoj me\ode najmanjših kvadratov S(x) := vTPv = min. tako zapišemo kot 
S(x) == v'1v' = min., kar bomo upoštevali v nadaljnjem izvajanju. 
Geodetski vestnik 38 (1994) 2 
IZRAČUN REŠITEV PO METODI NAJMANJŠIH KVADRATOV Z NORlVlALNIMJI 
ENAČBAMI 
ajbolj razširjen način za izračun rešitve problema po metodi najmanjših 
kvadratov so normalne enačbe, ki jih izpeljemo v posredni izravnavi z 
odvajanjem enačb popravkov po neznankah x. Rešitev je 
kjer je: 
N matrika koeficientov normalnih enačb ( det(N) * O) m 
n - vektor desne strani normalnih enačb .. 
1/ X J 
V normalnih enačbah ( 4) upoštevamo ekvivalentne enačbe (3b ). Neznanke x in 
njihovo natarnfoost ocene izračunamo z znanimi algoritmi za reševanje sistemov 
linearnih enačb (Bohte 1985). 
IZRAČUN REŠITEV PO NllETODI NAJMANJŠIH KVADRATOV Z RAZCEPOM SVD-JA 
(4) 
Od začetka sedemdesetih let se vedno bolj uveljavljajo tako imenovani ortogonalni razcepi za izračun neznank x po metodi najmanjših kvadratov. 
Ogledali si bomo razcep po singularnih vrednostih ali na kratko razcep SVD-ja (angl. 
Singular Value Decomposition) (Golub 1989, Press et al. 1992). Slabo pogojenih 
sistemov (1) ne rešujemo z metodo normalnih enačb, ker se lahko rešitve precej 
razlikujejo od točnih. S to metodo tudi ne moremo rešiti singularnih sistemov, ki jih 
dobimo pri izravnavi prostih mrež. Zahteva po izravnavi prostih mrež pa se često 
pojavlja. V teh primerih lahko uporabimo razcep SVD-ja. 
Iz enačb popravkov ne tvorimo normalnih enačb, ampak razcepimo (ekvivalentno) matriko koeficientov enačb popravkov A v: 
A = uwvT 
' 
kjer so: 
U in V - kvadratni ortogonalni matriki in 
W = diag(wi) - pravokotna diagonalna matrika singularnih vrednosti. 
Za ortogonalni matriki U in V velja: 
uTu = uuT = I in yTy = VVT = I. 
(5) 
(6) 
Najprej poglejmo, kako izračunamo neznanke x, če imamo nesingularen sistem (4). 
Če vektor popravkov opazovanj v ( enačba (2)) pomnožimo z ortogonalno matriko, se 
norma llvll; ne spremeni: 
Geodetski vestnik 38 (1994) 2 
s (x) = llu T Ax - u TI II; 
s (x) llu TAvv Tx - u T1 II; 
s (x) = llwv Tx - u T1 II; 
li n 
S(x) = I, (wt vI 
i=l 
T J2 x - ui 1 + r (uI 1J 
i=u+l 
(7) 
V enačbi (7) so: 
Wi - diagonalni členi matrike W, 
Ui in Vi - stolpci pripadajočih matrik U in V. 
Prvi člen na desni strani ynačbe (7) je lahko nič ali različen od nič, drugi člen pa je 
vedno večji od nič. Ker želimo poiskati minimum funkcije S, moramo postaviti pogoj, 
da je prvi člen enak nič: · 
li 
~ (wi vI x - uI I J2 = O. 
1=1 
Vsota kvadratov je enaka nič le, če so vsi členi vsote enaki nič. Zato je: 
T 
T A U; l 
v. x = -- za i = 1 , ... , u. 
1 Wi 
Enačbo (8) zapišimo v matrični obliki: 
vTx = w-1 uT1 
' 
kjer je: 
u 
w 
podmatrika matrike U in 
kvadratna diagonalna podmatrika matrike W. 
Ker je W kvadratna diagonalna matrika, izračunamo njeno inverzno matriko z 
naslednjim izrazom: 
(8) 
(9) 
w-1 = diag [:i) za i = 1, ... , u. . (10) 
Wi ::;1: O za i = 1, ... , u, saj smo predpostavili, da rešujemo nesingularen sistem. 
Končni izraz za izračun neznank x dobimo, če v enačbi (9) upoštevamo ortogonalnost 
matrike V (6): 
(11) 
Geodetski vestnik 38 (1994) 2 
Izračun neznank x po enačbi (11) je ekvivalenten računu po metodi z normalnimi enačbami. To dokažemo, če matriko A razcepimo, podobno kot v enačbi (5), na 
matrike U, V in W: 
Preuredimo normalne enačbe ( 4) v naslednjo obliko: 
x = (A TA )-l A T l. 
(12) 
(13) 
Enačbo (12) vstavimo v enačbo (13) in upoštevamo lastnosti matrik U, V in W(6): 
x = (VWUTUWVT)-l VWUTI 
x = ( V W W V T )-l V W U T 1 
x = vw-1w-1vTvwuT1 
x = V w-l U TL (14) 
Vidimo, da sta enačbi (11) in (14) enaki. Dokazali smo torej, da je vektor neznank x 
enak, če ga računamo z metodo normalnih enačb ali z razcepom SVD-ja. -
Sedaj poglejmo, kako izračunamo neznanke x, če je sistem (4) singularen. V tem primeru je vsaj en člen na diagonali v matriki W enak nič. Zato ne moremo 
uporabiti enačbe (10) pri izračunu neznank x. Vendar bomo dokazali, da dobimo 
rešitev po metodi najmanjših kvadratov, če postavimo, da so diagonalni členi l/wi 
enaki nič za vse Wi enake nič ali pri stalno pogojenem sistemu skoraj enake nič. 
Vrstice in stolpce razporedimo tako, da vse matrike razdelimo na dva dela: enega, ki 
pripada vrednostim Wi * O in drugega, ki pripada vrednostim Wi = O. Število od nič 
različnih singularnih vrednosti je rang matrike A in ga označimo z r. Izpeljavo 
začnemo enako kot v primeru nesingularnih vrednosti. V enačbi (7) se spremeni le 
meja za seštevanje: 
, r 
S(x) = I, (wiv} x -
i=l 
T )2 
"i 1 
Minimum funkcije dobimo, če postavimo pogoj, da je prvi člen enak nič: 
r 
L (wi v} x - u} 1 )2 = O ali 
i=l 
v~ x = 
1 
za = 1 , ... , r. 
Geodetski vestnik 38 (1994) 2 
Če želimo uporabiti enačbo (14) za izračun neznank x, mora veljati, da je 
T UT J 
v. x = - 1 - = O za i = r + 1, ... , u, 
1 Wi 
kar je ekvivalentno pogoju, ki smo ga želeli dokazati: 
l - = O za i = r + 1 , ... , u. 
Wi 
Dokazali srno torej, da dobimo rezultat po metodi najmanjših kvadratov tudi v 
primeru singularnega sistema, ki ga z normalnimi enačbami ne moremo rešiti. 
ZAKLJUČEK 
Slaba stran metode normalnih enačb je, da je pri slabo pogojenem sistemu (1) nestaoilna. To pomeni, da že majhne spremembe v sistemu povzročijo velike 
spremembe v rešitvi. V tem primeru rešitev ni točno izračunana. V izravnavah 
prostih mrež, kjer imamo premalo danih količin, pa je sistem ( 4) singularen. To 
pomeni, da lahko proste mreže izravnamo le, če vpeljemo dodatne pogoje med 
neznankami ali pa računamo z razcepom SVD-ja. Vpeljevanje teh pogojev je 
programersko precej zahtevno, medtem ko za rešitev z razcepom SVD-ja ne 
potrebujemo nobenega dodatnega dela. Programi, s katerimi izračunamo razcep 
SVD-ja, so objavljeni in jih lahko uporabimo (Press et al. 1992). 
Slaba stran razcepa SVD-ja je, da potrebujemo za razcep bistveno več računalniškega pomnilnika, saj moramo imeti v pomnilniku shranjeno celotno 
matriko A in matrike U, V ter W. Do sedaj še ni znanih algoritmov, ki bi pri razcepu 
SVD-ja varčno shranjevali elemente matrik. Pri reševanju po metodi normalnih 
enačb je taka na primer metoda "skyline" (Ambrožič et al. 1993). Reševanje 
problema po metodi najmanjših kvadratov z razcepom SVD-ja zahteva tudi več 
računskega časa v primerjavi z metodo normalnih enačb. V literaturi (Golub 1989) 
podajajo število računskih operacij ("flop"). Z normalnimi enačbami potrebujemo 
(un2 + n3/3) operacij, z razcepom SVD-ja pa (2un2 + 2n\ Z razcepom SVD-ja 
lahko zelo hitro odkrijemo vse napake merjenj, saj moramo le preveriti, kateri 
popravki so po izravnavi izredno veliki. Za te meritve lahko zatrdimo, da so napačne 
in jih moramo popraviti ali izločiti. 
ačunalniški program GeM (Ambrožič 1988) smo priredili tako, da lahko 
izravnamo poljubne mreže v ravnini z normalnimi enačbami ali pa z razcepom 
SVD-ja. Rezultatov izravnave, dobljenih po različnih poteh, ne navajamo, ker so v 
obeh primerih enaki. 
Literatura: 
Ambrožič, T., 1988, Izdelava programa za izravnavo ravninske mreže za ATARI in IBM, 
Diplomska naloga, FAGG, Ljubljana. 
Ambrožič, T. et al., 1993, Uporaba metode "skyline" v izravnavi geodetskih mrež, Geodetski vestnik 
(37), Ljubljana, štev. 2, 115-119. 
Bohte, Z., 1985, Numerične metode, Društvo matematikov, fizikov in astronomov SRS, Zveza za 
tehnično kulturo Slovenije, Ljubljana. 
Feil, L., 1989, ·Teorija pogrešaka i račun izjednačenja, Prvi dio, Geodetski fakultet Sveučilišta u 
Zagrebu, Zagreb. 
Geodetski vestnik 38 (1994) 2 
Golub, G.H. et al., 1989, Matrix Computations, 2nd Edition, Johns Hopkins University Press, 
Baltimore, USA. 
Mihailovic, 1981, Geodezija JI, I deo, Gradevinska knjiga, Beograd. 
Press, H.P. et al., 1992, Numerical Recipes in Fortran, 2nd Edition, Cambridge University Press, 
Cambridge, USA. 
Recenzija: mag. Bojan Stopar 
profdr. Ranko Todorovič 
Geodetski vestnik 38 (1994) 2