Algebraic Geodesy and Geoinformatics (eBook)

Joseph L. Awange, Erik W. Grafarend, Béla Paláncz, Piroska Zaletnyik (Autoren)

eBook Download: PDF

2010 | 2nd ed. 2010
XVIII, 377 Seiten
Springer Berlin (Verlag)
978-3-642-12124-1 (ISBN)

Infos

While preparing and teaching 'Introduction to Geodesy I and II' to undergraduate students at Stuttgart University, we noticed a gap which motivated the writing of the present book: Almost every topic that we taught required some skills in algebra, and in particular, computer algebra! From positioning to transformation problems inherent in geodesy and geoinformatics, knowledge of algebra and application of computer algebra software were required. In preparing this book therefore, we have attempted to put together basic concepts of abstract algebra which underpin the techniques for solving algebraic problems. Algebraic computational algorithms useful for solving problems which require exact solutions to nonlinear systems of equations are presented and tested on various problems. Though the present book focuses mainly on the two ?elds, the concepts and techniques presented herein are nonetheless applicable to other ?elds where algebraic computational problems might be encountered. In Engineering for example, network densi?cation and robotics apply resection and intersection techniques which require algebraic solutions. Solution of nonlinear systems of equations is an indispensable task in almost all geosciences such as geodesy, geoinformatics, geophysics (just to mention but a few) as well as robotics. These equations which require exact solutions underpin the operations of ranging, resection, intersection and other techniques that are normally used. Examples of problems that require exact solutions include; • three-dimensional resection problem for determining positions and orientation of sensors, e. g. , camera, theodolites, robots, scanners etc.

Inhalt

Preface to the first edition 5
Preface to the second edition 9
Foreword 11
Contents 12
Introduction 18
Motivation 18
Modern challenges 18
Facing the challenges 19
Concluding remarks 22
Part I Algebraic symbolic and numeric methods 23
Basics of ring theory 24
Some applications to geodesy and geoinformatics 24
Numbers from operational perspective 24
Number rings 28
Concluding remarks 31
Basics of polynomial theory 32
Polynomial equations 32
Polynomial rings 33
Polynomial objects as rings 33
Operations ``addition'' and ``multiplication'' 35
Factoring polynomials 36
Polynomial roots 36
Minimal polynomials 37
Univariate polynomials with real coefficients 38
Quadratic polynomials 38
Cubic polynomials 40
Quartic polynomials 41
Methods for investigating roots 42
Logarithmic and contour plots on complex plane 42
Isograph simulator 44
Application of inverse series 44
Computation of zeros of polynomial systems 45
Concluding remarks 47
Groebner basis 48
The origin 48
Basics of Groebner basis 49
Buchberger algorithm 55
Mathematica computation of Groebner basis 60
Maple computation of Groebner basis 61
Concluding remarks 62
Polynomial resultants 63
Resultants: An alternative to Groebner basis 63
Sylvester resultants 63
Multipolynomial resultants 65
F. Macaulay formulation: 66
B. Sturmfels' formulation 68
The Dixon resultant 69
Basic concepts 69
Formulation of the Dixon resultant 70
Dixon's generalization of the Cayley-Bézoutmethod 71
Improved Dixon resultant - Kapur-Saxena-Yang method 72
Heuristic methods to accelerate the Dixon resultant 73
Early discovery of factors: the EDF method 74
Concluding remarks 75
Linear homotpy 77
Introductory remarks 77
Background to homotopy 77
Definition and basic concepts 78
Solving nonlinear equations via homotopy 79
Tracing homotopy path as initial value problem 83
Types of linear homotopy 85
Fixed point homotopy 85
Newton homotopy 85
Start system for polynomial systems 86
Concluding remarks 90
Solutions of Overdetermined Systems 92
Estimating geodetic and geoinformatics unknowns 92
Algebraic LEast Square Solution (ALESS) 93
Transforming overdetermined systems to determined 93
Solving the determined system 95
Gauss-Jacobi combinatorial algorithm 97
Combinatorial approach: the origin 97
Linear and nonlinear Gauss-Markov models 100
Gauss-Jacobi combinatorial formulation 101
Combinatorial solution of nonlinear Gauss-Markov model 105
Construction of minimal combinatorial subsets 105
Optimization of combinatorial solutions 106
The Gauss-Jacobi combinatorial algorithm 110
Concluding remarks 111
Extended Newton-Raphson method 113
Introductory remarks 113
The standard Newton-Raphson approach 114
Examples of limitations of the standard approach 114
Overdetermined polynomial systems 114
Overdetermined non-polynomial system 116
Determined polynomial system 117
Underdetermined polynomial system 118
Extending the Newton-Raphson approach using pseudoinverse 119
Applications of the Extended Newton-Raphson method 120
Concluding remarks 122
Procrustes solution 123
Motivation 123
Procrustes: Origin and applications 124
Procrustes and the magic bed 124
Multidimensional scaling 126
Applications of Procrustes in medicine 126
Gene recognition 126
Identification of malaria parasites 127
Partial procrustes solution 128
Conventional formulation 128
Partial derivative formulation 130
The General Procrustes solution 131
Extended general Procrustes solution 142
Mild anisotropy in scaling 142
Strong anisotropy in scalling 143
Weighted Procrustes transformation 145
Concluding remarks 147
Part II Applications to geodesy and geoinformatics 148
LPS-GNSS orientations and vertical deflections 149
Introductory remarks 149
Positioning systems 150
Global positioning system (GPS) 151
Local positioning systems (LPS) 152
Local datum choice in an LPS 3-D network 152
Relationship between global and local level reference frames 154
Observation equations 155
Three-dimensional orientation problem 156
Procrustes solution of the orientation problem 157
Determination of vertical deflection 159
Example: Test network Stuttgart Central 160
Concluding remarks 163
Cartesian to ellipsoidal mapping 164
Introductory remarks 164
Mapping topographical points onto reference ellipsoid 164
Mapping geometry 167
Minimum distance mapping 169
Grafarend-Lohse's mapping of T2-3muEa,a,b2 172
Groebner basis' mapping of T2-3muEa,a,b2 173
Extended Newton-Raphson's mapping of T2-3muEa,a,b2 175
Concluding remarks 180
Positioning by ranging 181
Applications of distances 181
Ranging by global navigation satellite system (GNSS) 182
The pseudo-ranging four-points problem 182
Sturmfels' approach 185
Groebner basis approach 187
Ranging to more than four GPS satellites 189
Extended Newton-Raphson solution 193
Homotopy solution of GPS N-point problem 195
Least squares versus Gauss-Jacobi combinatorial 197
Ranging by local positioning systems (LPS) 199
Planar ranging 200
Conventional approach 200
Sylvester resultants approach 201
Reduced Groebner basis approach 202
Planar ranging to more than two known stations 206
ALESS solution of overdetermined planar ranging problem 208
Three-dimensional ranging 211
Closed form three-dimensional ranging 211
Conventional approaches 212
Solution by elimination approach-2 213
Groebner basis approach 214
Polynomial resultants approach 215
N-point three-dimensional ranging 219
ALESS solution 220
Extended Newton-Raphson's solution 223
Concluding remarks 224
Positioning by resection methods 225
Resection problem and its importance 225
Geodetic resection 228
Planar resection 228
Conventional analytical solution 228
Groebner basis approach 230
Sturmfels' resultant approach 231
Three-dimensional resection 234
Exact solution 234
Solution of Grunert's distance equations 234
Groebner basis solution of Grunert's equations 236
Polynomial resultants' solution of Grunert's distance equations 238
Linear homotopy solution 241
Grafarend-Lohse-Schaffrin approach 245
3d-resection to more than three known stations 248
Photogrammetric resection 252
Grafarend-Shan Möbius photogrammetric resection 253
Algebraic photogrammetric resection 254
Concluding remarks 256
Positioning by intersection methods 257
Intersection problem and its importance 257
Geodetic intersection 258
Planar intersection 258
Conventional solution 258
reduced Groebner basis solution 259
Three-dimensional intersection 262
Closed form solution 262
Conventional solution 263
Reduced Groebner basis solution 263
Sturmfels' resultants solution 264
Intersection to more than three known stations 267
Photogrammetric intersection 269
Grafarend-Shan Möbius approach 270
Commutative algebraic approaches 271
Concluding remarks 271
GNSS environmental monitoring 272
Satellite environmental monitoring 272
GNSS remote sensing 276
Space borne GNSS meteorology 276
Ground based GNSS meteorology 278
Refraction (bending) angles 280
Transformation of trigonometric equations to algebraic 281
Algebraic determination of bending angles 283
Application of Groebner basis 283
Sylvester resultants solution 284
Algebraic analysis of some CHAMP data 285
Concluding remarks 293
Algebraic diagnosis of outliers 295
Outliers in observation samples 295
Algebraic diagnosis of outliers 296
Outlier diagnosis in planar ranging 298
Diagnosis of multipath error in GNSS positioning 302
Concluding remarks 306
Datum transformation problems 308
The 7-parameter datum transformation and its importance 308
Algebraic solution of the 7-parameter transformation problem 310
Groebner basis transformation 310
Dixon resultant solution 314
Gauss-Jacobi combinatorial transformation 318
The 9-parameter (affine) datum transformation 323
Algebraic solution of the 9-parameter transformation 325
The 3-point affine transformation problem 325
Simplifications for the symbolic solution 325
Symbolic solution with Dixon resultant 326
Symbolic solution with reduced Groebner basis 328
The N-points problem 330
ALESS approach to overdetermined cases 332
Homotopy solution of the ALESS-determinedmodel 334
Procrustes solution 338
Concluding remark 342
Appendix 344
Appendix A-1: Definitions 344
Appendix A-2: C. F. Gauss combinatorial approach 345
Appendix A-3: Linear homotopy 348
Appendix A-4: Determined system of the 9-parameter transformation N point problem 349
References 353
Index 374

Textauszug

"1 Introduction (p. 1-2)

1-1 Motivation

A potential answer to modern challenges faced by geodesists and geoinformatics (see, e.g., Sect. 1-3), lies in the application of algebraic computational techniques. The present book provides an in-depth look at algebraic computational methods and combines them with special local and global numerical methods like the Extended Newton-Raphson and the Homotopy continuation method to provide smooth and efficient solutions to real life-size problems often encountered in geodesy and geoinformatics, but which cannot be adequately solved by algebraic methods alone.

Algebra has been widely applied in fields such as robotics for kinematic modelling, in engineering for o set surface construction, in computer science for automated theorem proving, and in Computer Aided Design (CAD). The most wellknown application of algebra in geodesy could perhaps be the use of Legendre polynomials in spherical harmonic expansion studies. More recent applications of algebra in geodesy are shown in the works of Biagi and Sanso [77], Awange [14], Awange and Grafarend [41], and Lannes and Durand [259], the latter proposing a new approach to di erential GPS based on algebraic graph theory. The present book is divided into two parts.

Part I focuses on the algebraic and numerical methods and presents powerful tools for solving algebraic computational problems inherent in geodesy and geoinformatics. The algebraic methods are presented with numerous examples of their applicability in practice. Part I can therefore be skipped by readers with an advanced knowledge in algebraic methods, and who are more interested in the applications of the methods which are presented in part II.

1-2 Modern challenges

In daily geodetic and geoinformatic operations, nonlinear equations are encountered in many situations, thus necessitating the need for developing efficient and reliable computational tools. Advances in computer technology have also propelled the development of precise and accurate measuring devices capable of collecting large amount of data. Such advances and improvements have brought new challenges to practitioners in fields of geosciences and engineering, which include:

• Handling in an efficient and manageable way the nonlinear systems of equations that relate observations to unknowns. These nonlinear systems of equations whose exact (algebraic) solutions have mostly been difficult to solve, e.g., the transformation problem presented in Chap. 17 have been a thorn in the side of users. In cases where the number of observations n and the number of unknowns m are equal, i.e., n = m, the unknown parameters may be obtained by solving explicitly (in a closed form) nonlinear systems of equations."

Produkt-Details

• Erscheint lt. Verlag: 27.5.2010
• Zusatzinfo: XVIII, 377 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Naturwissenschaften ► Geowissenschaften ► Geografie / Kartografie
• Themenwelt: Naturwissenschaften ► Geowissenschaften ► Geologie
• Themenwelt: Technik
• Schlagworte: algebraic computations • Computer Algebra • Engineering • Geodesy • geoinformatics • GIS • Photogrammetry • Robotics • Surveying
• ISBN-10: 3-642-12124-1 / 3642121241
• ISBN-13: 978-3-642-12124-1 / 9783642121241