Editing Global Positioning System (section)

== Navigation equations ==
{{Further|GNSS positioning calculation}}
{{See also|Pseudorange}}

=== Problem statement ===
The receiver uses messages received from satellites to determine the satellite positions and time sent. The ''x, y,'' and ''z'' components of satellite position and the time sent (''s'') are designated as [''x<sub>i</sub>, y<sub>i</sub>, z<sub>i</sub>, s<sub>i</sub>''] where the subscript ''i'' denotes the satellite and has the value 1, 2, ..., ''n'', where ''n''&nbsp;≥&nbsp;4. When the time of message reception indicated by the on-board receiver clock is <math>\tilde{t}_i</math>, the true reception time is <math>t_i = \tilde{t}_i - b</math>, where ''b'' is the receiver's clock bias from the much more accurate GPS clocks employed by the satellites. The receiver clock bias is the same for all received satellite signals (assuming the satellite clocks are all perfectly synchronized). The message's transit time is <math>\tilde{t}_i - b - s_i</math>, where ''s<sub>i</sub>'' is the satellite time. Assuming the message traveled at [[Speed of light|the speed of light]], ''c'', the distance traveled is <math>\left(\tilde{t}_i - b - s_i\right) c</math>.

For n satellites, the equations to satisfy are:
:<math>d_i = \left( \tilde{t}_i - b - s_i \right)c, \; i=1,2,\dots,n</math>
where ''d<sub>i</sub>'' is the geometric distance or range between receiver and satellite ''i'' (the values without subscripts are the ''x, y,'' and ''z'' components of receiver position):
:<math>d_i = \sqrt{(x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2}</math>
Defining ''pseudoranges'' as <math> p_i = \left ( \tilde{t}_i - s_i \right )c</math>, we see they are biased versions of the true range:
:<math>p_i = d_i + bc, \;i=1,2,...,n</math> .<ref name=GPS_BASICS_Blewitt>section 4 beginning on page 15 [http://www.nbmg.unr.edu/staff/pdfs/Blewitt%20Basics%20of%20gps.pdf Geoffrey Blewitt: Basics of the GPS Technique] {{Webarchive|url=https://web.archive.org/web/20130922064413/http://www.nbmg.unr.edu/staff/pdfs/Blewitt%20Basics%20of%20gps.pdf |date=September 22, 2013 }}</ref><ref name=Bancroft>{{cite web|url=http://www.macalester.edu/~halverson/math36/GPS.pdf|archive-url=https://web.archive.org/web/20110719232148/http://www.macalester.edu/~halverson/math36/GPS.pdf|archive-date=July 19, 2011|title=Global Positioning Systems|access-date=October 15, 2010}}</ref>
Since the equations have four unknowns [''x, y, z, b'']—the three components of GPS receiver position and the clock bias—signals from at least four satellites are necessary to attempt solving these equations. They can be solved by algebraic or numerical methods. Existence and uniqueness of GPS solutions are discussed by Abell and Chaffee.<ref name="Abel1" /> When ''n'' is greater than four, this system is [[Overdetermined system|overdetermined]] and a [[Mean|fitting method]] must be used.

The amount of error in the results varies with the received satellites' locations in the sky, since certain configurations (when the received satellites are close together in the sky) cause larger errors. Receivers usually calculate a running estimate of the error in the calculated position. This is done by multiplying the basic resolution of the receiver by quantities called the [[Dilution of precision (navigation)|geometric dilution of position]] (GDOP) factors, calculated from the relative sky directions of the satellites used.<ref>{{cite web|url=http://www.colorado.edu/geography/gcraft/notes/gps/gps.html#Gdop|title=Geometric Dilution of Precision (GDOP) and Visibility|first=Peter H.|last=Dana|publisher=University of Colorado at Boulder|access-date=July 7, 2008|archive-url=https://web.archive.org/web/20050823013233/http://www.colorado.edu/geography/gcraft/notes/gps/gps.html#Gdop|archive-date=August 23, 2005}}</ref> The receiver location is expressed in a specific coordinate system, such as latitude and longitude using the [[WGS 84]] [[datum (geodesy)|geodetic datum]] or a country-specific system.<ref>{{cite web |author=Dana |first=Peter H. |title=Receiver Position, Velocity, and Time |url=http://www.colorado.edu/geography/gcraft/notes/gps/gps.html#PosVelTime |archive-url=https://web.archive.org/web/20050823013233/http://www.colorado.edu/geography/gcraft/notes/gps/gps.html#PosVelTime |archive-date=August 23, 2005 |access-date=July 7, 2008 |publisher=University of Colorado at Boulder}}</ref>

=== Geometric interpretation ===
The GPS equations can be solved by numerical and analytical methods. Geometrical interpretations can enhance the understanding of these solution methods.

==== Spheres ====
[[File:2D Trilat Scenario 2019-0116.jpg|thumb|2-D Cartesian true-range multilateration (trilateration) scenario]]

The measured ranges, called pseudoranges, contain clock errors. In a simplified idealization in which the ranges are synchronized, these true ranges represent the radii of spheres, each centered on one of the transmitting satellites. The solution for the position of the receiver is then at the intersection of the surfaces of these spheres; see [[trilateration]] (more generally, true-range multilateration). Signals from at minimum three satellites are required, and their three spheres would typically intersect at two points.<ref>{{cite web|url=http://www.math.nus.edu.sg/aslaksen/gem-projects/hm/0203-1-10-instruments/modern.htm|title=Modern navigation|work=math.nus.edu.sg|access-date=December 4, 2018|archive-url=https://web.archive.org/web/20171226024421/http://www.math.nus.edu.sg/aslaksen/gem-projects/hm/0203-1-10-instruments/modern.htm|archive-date=December 26, 2017}}</ref> One of the points is the location of the receiver, and the other moves rapidly in successive measurements and would not usually be on Earth's surface.

In practice, there are many sources of inaccuracy besides clock bias, including random errors as well as the potential for precision loss from subtracting numbers close to each other if the centers of the spheres are relatively close together. This means that the position calculated from three satellites alone is unlikely to be accurate enough. Data from more satellites can help because of the tendency for random errors to cancel out and also by giving a larger spread between the sphere centers. But at the same time, more spheres will not generally intersect at one point. Therefore, a near intersection gets computed, typically via least squares. The more signals available, the better the approximation is likely to be.

==== Hyperboloids ====
[[File:Hyperbolic Navigation.svg|thumb|219x219px|Three satellites (labeled as "stations" A, B, C) have known locations. The true times it takes for a radio signal to travel from each satellite to the receiver are unknown, but the true time differences are known. Then, each time difference locates the receiver on a branch of a hyperbola focused on the satellites. The receiver is then located at one of the two intersections.]]

If the pseudorange between the receiver and satellite ''i'' and the pseudorange between the receiver and satellite ''j'' are subtracted, {{nowrap|1=''p<sub>i</sub>'' − ''p<sub>j</sub>''}}, the common receiver clock bias (''b'') cancels out, resulting in a difference of distances {{nowrap|1=''d<sub>i</sub>'' − ''d<sub>j</sub>''}}. The locus of points having a constant difference in distance to two points (here, two satellites) is a [[hyperbola]] on a plane and a [[hyperboloid of revolution]] (more specifically, a [[two-sheeted hyperboloid]]) in 3D space (see [[Multilateration]]). Thus, from four pseudorange measurements, the receiver can be placed at the intersection of the surfaces of three hyperboloids each with [[Focus (geometry)|foci]] at a pair of satellites. With additional satellites, the multiple intersections are not necessarily unique, and a best-fitting solution is sought instead.<ref name="Abel1" /><ref name="Fang" /><ref>{{cite book |last1=Strang |first1=Gilbert |url=https://books.google.com/books?id=MjNwWUY8jx4C&pg=PA449 |title=Linear Algebra, Geodesy, and GPS |last2=Borre |first2=Kai |publisher=SIAM |year=1997 |isbn=978-0-9614088-6-2 |pages=448–449 |access-date=May 22, 2018 |archive-url=https://web.archive.org/web/20211010021202/https://books.google.com/books?id=MjNwWUY8jx4C&pg=PA449 |archive-date=October 10, 2021 |url-status=live}}</ref><ref>{{cite book |author=Holme |first=Audun |url=https://books.google.com/books?id=zXwQGo8jyHUC&pg=PA338 |title=Geometry: Our Cultural Heritage |publisher=Springer Science & Business Media |year=2010 |isbn=978-3-642-14441-7 |page=338 |access-date=May 22, 2018 |archive-url=https://web.archive.org/web/20211010021203/https://books.google.com/books?id=zXwQGo8jyHUC&pg=PA338 |archive-date=October 10, 2021 |url-status=live}}</ref><ref name="HWLW">{{cite book |last1=Hofmann-Wellenhof |first1=B. |url=https://books.google.com/books?id=losWr9UDRasC&pg=PA36 |title=Navigation |last2=Legat |first2=K. |last3=Wieser |first3=M. |publisher=Springer Science & Business Media |year=2003 |isbn=978-3-211-00828-7 |page=36 |access-date=May 22, 2018 |archive-url=https://web.archive.org/web/20211010021203/https://books.google.com/books?id=losWr9UDRasC&pg=PA36 |archive-date=October 10, 2021 |url-status=live}}</ref><ref name="Groves2013">{{cite book |last=Groves |first=P. D. |url=https://books.google.com/books?id=t94fAgAAQBAJ |title=Principles of GNSS, Inertial, and Multisensor Integrated Navigation Systems, Second Edition |publisher=Artech House |year=2013 |isbn=978-1-60807-005-3 |series=GNSS/GPS |page= |access-date=February 19, 2021 |archive-url=https://web.archive.org/web/20210315202930/https://books.google.com/books?id=t94fAgAAQBAJ |archive-date=March 15, 2021 |url-status=live}}</ref>

==== Inscribed sphere ====
[[File:Descartes Circles.svg|thumb|A smaller circle ({{color|red|'''red'''}}) inscribed and tangent to other circles ({{color|black|'''black'''}}), that need not necessarily be mutually tangent]]

The receiver position can be interpreted as the center of an [[inscribed sphere]] (insphere) of radius ''bc'', given by the receiver clock bias ''b'' (scaled by the speed of light ''c''). The insphere location is such that it touches other spheres. The [[Circumscribed sphere|circumscribing spheres]] are centered at the GPS satellites, whose radii equal the measured pseudoranges ''p''<sub>i</sub>. This configuration is distinct from the one described above, in which the spheres' radii were the unbiased or geometric ranges ''d''<sub>i</sub>.<ref name=HWLW />{{rp|36–37}}<ref name="Hoshen 1996">{{cite journal |author=Hoshen |first=J. |year=1996 |title=The GPS Equations and the Problem of Apollonius |journal=IEEE Transactions on Aerospace and Electronic Systems |volume=32 |issue=3 |pages=1116–1124 |bibcode=1996ITAES..32.1116H |doi=10.1109/7.532270 |s2cid=30190437}}</ref>

==== Hypercones ====
The clock in the receiver is usually not of the same quality as the ones in the satellites and will not be accurately synchronized to them. This produces [[pseudorange]]s with large differences compared to the true distances to the satellites. Therefore, in practice, the time difference between the receiver clock and the satellite time is defined as an unknown clock bias ''b''. The equations are then solved simultaneously for the receiver position and the clock bias. The solution space [''x, y, z, b''] can be seen as a four-dimensional [[spacetime]], and signals from at minimum four satellites are needed. In that case each of the equations describes a [[hypercone]] (or spherical cone),<ref>{{cite journal|title=GPS Solutions: Closed Forms, Critical and Special Configurations of P4P | doi=10.1007/PL00012897 | volume=5|issue=3 |journal=GPS Solutions|pages=29–41 | last1 = Grafarend | first1 = Erik W.|year=2002 | bibcode=2002GPSS....5...29G | s2cid=121336108 }}</ref> with the cusp located at the satellite, and the base a sphere around the satellite. The receiver is at the intersection of four or more of such hypercones.

=== Solution methods ===

==== Least squares ====
When more than four satellites are available, the calculation can use the four best, or more than four simultaneously (up to all visible satellites), depending on the number of receiver channels, processing capability, and [[Dilution of precision (GPS)|geometric dilution of precision]] (GDOP).

Using more than four involves an over-determined system of equations with no unique solution; such a system can be solved by a [[least-squares]] or weighted least squares method.<ref name=GPS_BASICS_Blewitt />

:<math>\left( \hat{x},\hat{y},\hat{z},\hat{b} \right) = \underset{\left( x,y,z,b \right)}{\arg \min} \sum_i \left( \sqrt{(x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2} + bc - p_i \right)^2</math>

==== Iterative ====
Both the equations for four satellites, or the least squares equations for more than four, are non-linear and need special solution methods. A common approach is by iteration on a linearized form of the equations, such as the [[Gauss–Newton algorithm]].

The GPS was initially developed assuming use of a numerical least-squares solution method—i.e., before closed-form solutions were found.

==== Closed-form ====
One closed-form solution to the above set of equations was developed by S. Bancroft.<ref name=Bancroft /><ref name=Bancroft1985>{{cite journal |last1=Bancroft |first1=S. |date=January 1985 |title=An Algebraic Solution of the GPS Equations |journal=IEEE Transactions on Aerospace and Electronic Systems |volume=AES-21 |issue=1 |pages=56–59 |doi=10.1109/TAES.1985.310538 |bibcode=1985ITAES..21...56B|s2cid=24431129 }}</ref> Its properties are well known;<ref name="Abel1" /><ref name="Fang" /><ref name="Chaffee">Chaffee, J. and Abel, J., "On the Exact Solutions of Pseudorange Equations", ''IEEE Transactions on Aerospace and Electronic Systems'', vol:30, no:4, pp: 1021–1030, 1994</ref> in particular, proponents claim it is superior in low-[[geometric dilution of precision|GDOP]] situations, compared to iterative least squares methods.<ref name=Bancroft1985 />

Bancroft's method is algebraic, as opposed to numerical, and can be used for four or more satellites. When four satellites are used, the key steps are inversion of a 4x4 matrix and solution of a single-variable quadratic equation. Bancroft's method provides one or two solutions for the unknown quantities. When there are two (usually the case), only one is a near-Earth sensible solution.<ref name=Bancroft />

When a receiver uses more than four satellites for a solution, Bancroft uses the [[generalized inverse]] (i.e., the pseudoinverse) to find a solution. A case has been made that iterative methods, such as the Gauss–Newton algorithm approach for solving over-determined [[non-linear least squares]] problems, generally provide more accurate solutions.<ref name="Sirola2010">{{cite conference |last1=Sirola |first1=Niilo |date=March 2010 |title=Closed-form algorithms in mobile positioning: Myths and misconceptions |book-title=7th Workshop on Positioning Navigation and Communication |conference=WPNC 2010 |pages=38–44 |doi=10.1109/WPNC.2010.5653789|citeseerx=10.1.1.966.9430 }}</ref>

Leick et al. (2015) states that "Bancroft's (1985) solution is a very early, if not the first, closed-form solution."<ref>{{cite book|title=GNSS Positioning Approaches – GPS Satellite Surveying, Fourth Edition – Leick |publisher= Wiley Online Library|doi=10.1002/9781119018612.ch6|pages=257–399|chapter = GNSS Positioning Approaches|year = 2015|isbn = 9781119018612}}</ref>
Other closed-form solutions were published afterwards,<ref name="Kleus">Alfred Kleusberg, "Analytical GPS Navigation Solution", ''University of Stuttgart Research Compendium'', 1994.</ref><ref name="Oszczak">Oszczak, B., "New Algorithm for GNSS Positioning Using System of Linear Equations", ''Proceedings of the 26th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS+ 2013)'', Nashville, Tennessee, September 2013, pp. 3560–3563.</ref> although their adoption in practice is unclear.

=== Error sources and analysis ===
{{Main|Error analysis for the Global Positioning System}}

GPS error analysis examines error sources in GPS results and the expected size of those errors. GPS makes corrections for receiver clock errors and other effects, but some residual errors remain uncorrected. Error sources include signal arrival time measurements, numerical calculations, atmospheric effects (ionospheric/tropospheric delays), [[ephemeris]] and clock data, multipath signals, and natural and artificial interference. Magnitude of residual errors from these sources depends on geometric dilution of precision. Artificial errors may result from jamming devices and threaten ships and aircraft<ref>Attewill, Fred. (February 13, 2013) [http://metro.co.uk/2013/02/13/vehicles-that-use-gps-jammers-are-big-threat-to-aircraft-3474922/ Vehicles that use GPS jammers are big threat to aircraft] {{Webarchive|url=https://web.archive.org/web/20130216014922/http://metro.co.uk/2013/02/13/vehicles-that-use-gps-jammers-are-big-threat-to-aircraft-3474922/ |date=February 16, 2013 }}. Metro.co.uk. Retrieved on August 2, 2013.</ref> or from intentional signal degradation through selective availability, which limited accuracy to ≈ {{cvt|6-12|m||-1|}}, but has been switched off since May 1, 2000.<ref>{{cite web
 | url = http://www.gps.gov/systems/gps/modernization/sa/faq/
 | title = Frequently Asked Questions About Selective Availability
 | publisher = National Coordination Office for Space-Based Positioning, Navigation, and Timing (PNT)
 | quote = Selective Availability ended a few minutes past midnight EDT after the end of May 1, 2000. The change occurred simultaneously across the entire satellite constellation.
 | date = October 2001
 | access-date = June 13, 2015
| archive-url = https://web.archive.org/web/20150616044948/http://www.gps.gov/systems/gps/modernization/sa/faq/
 | archive-date = June 16, 2015
| url-status = live
 }}</ref><ref>{{Cite web|url=https://blackboard.vuw.ac.nz/bbcswebdav/pid-1444805-dt-content-rid-2193398_1/courses/2014.1.ESCI203/Esci203_2014_GPS_1.pdf|title=Blackboard}}</ref>