Matematika (a fyzika) schovaná za GPS Michal Bulant Masarykova univerzita Prírodovedecká fakulta Ustav matematiky a statistiky Brno, 26. února 2014 Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Irno, 26. února 2014 1/25 Global Positioning system • minimálně 27 satelitů (24 aktivních - jsou po 4 rovnoměrně rozmístěny na 6 orbitálních drahách, 3 záložní), v tuto chvíli 32 aktivních, viz http://www.navcen.uscg.gov/?Do=constellationStatus • výška cca 19 300 km na povrchem Země, cca 2 oběhy denně • z každého místa na Zemi viditelných 4-12 satelitů • od 1. května 2000 zrušeno umělé zkreslování dat (SA - selective availability) Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Irno, 26. února 2014 2 / 25 Jak to vlastně funguje? Cheap GPS ... Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Irno, 26. února 2014 3 / 25 Výpočet pozice - úvod Satelity obíhající (nejde o stacionárni družice) Zemi vysílají zprávy obsahující: • čas vyslání zprávy, • polohu satelitu, • systémovou informaci o stavu a (přibližné) pozici ostatních satelitů. Z těchto informací chce příjemce (GPS přijímač) odvodit informaci o své poloze. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Irno, 26. února 2014 4 / 25 Prijímač na základě polohové a časové informace [x/,y,-, z,-, ry] od alespoň 3(4) satelitu vypočte svoji zdanlivou vzdálenost r, od jednotlivých vysílačů (pseudorange) za předpokladu, že se signál šíří rychlostí světla (odhadněte, jak dlouho letí signál). Vypočtená vzdálenost od satelitu spolu s jeho polohou při vyslání signálu udává sféru (povrch koule), na níž přijímač leží. Průsečíkem takových dvou sfér je pak kružnice, obsahující daný bod. Výpočet pozice - pokračovaní Průsečíkem třetí sféry s touto kružnicí jsou pak (obvykle) 2 body. Výslednou pozici je pak možné určit jako: • ten z průsečíků, který je blíže povrchu Země (v obvyklém případě GPS přijímače v autě či v ruce) • ten z průsečíků, který je blíže čtvrté sféře - v tomto případě je rovněž možné pomocí GPS určit nadmořskou výšku, v níž se přijímač pohybuje. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Irno, 26. února 2014 6 / 25 Konečně slíbená matematika Pro zjednodušení výpočtů je možné bez újmy na obecnosti zvolit kartézskou soustavu souřadnic tak, že středy sfér (tj. pozice vysílajících satelitů) jsou v rovině xy (tj. z = 0), jeden ze středů dále umístíme v počátku a druhý na ose x. Uvažujme tedy tři sféry se středy v bodech [0, 0, 0], [u, 0, 0], [v, w, 0] a poloměry r\, r2, r% a dostaneme tak pro hledanou pozici [x,y,z] rovnice x2+y2+z2 = r2 {x-u)2+y2+z2 = r2 (x - v)2 + (y - w)2 + z2 = rf Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Irno, 26. února 2014 7 / 25 Konečně slíbená matematika x2+y2+z2 = r2 {x-u)2+y2+z2 = r2 (x - v)2 + (y - w)2 + z2 = rf Odečtením 2. rovnice od první a snadnou úpravou dostaneme x = jjj(r2 — r| + u2), odkud po dosazení za x do první rovnice dostaneme vztah (r2 - r2 + u2)2 y2 + z2. 1 4u2 Podmínkou pro řešitelnost (tj. pro to, že se první dvě sféry vůbec protínají) je 2ur\ > r2 — r| + u2, neboli r| > (u — r\)2, či r\ + r2 > u > r\ — r2 (tuto podmínku lze samozřejmě takřka ihned vidět z obrázku). Při splnění odvozené podmínky již vypočteme i souřadnici y pomocí dosazení do třetí rovnice. Souřadnici z pak lze dopočítat např. jako z = ±w r2 — x2 — y2. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Irno, 26. února 2014 8 / 25 Jak ale počítat prakticky odmocniny? V důsledku je třeba řešit nelineární soustavu rovnic o více neznámých - již jsme ukázali jeden způsob, jakým ji lze převést na postupné řešení rovnic o jedné neznámé. Newton-Raphsonova metoda je iterativní metoda na hledání kořenů reálných funkcí (obecně více proměnných). Newtonova metoda tečen S touto metodou přišel Newton kolem roku 1670 a vysvětlil ji na příkladu rovnice (viz též tato ukázka) x3 - 2x - 5 = 0. Jeden z kořenů je blízko 2, položil tedy x = 2 + p a dosazením do rovnice dostal vztah pro p: p3 + 6p2 + lOp - 1 = 0. Protože je ale p malé, je možné zanedbat členy p3,6p2, odkud p = To samozřejmě není přesné řešení, jde ale o další zpřesnění, můžeme nyní psát x = 2,1 + q, dostat tak další aproximaci x = 2,0946 atd. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Brno, 26. února 2014 9 / 25 Jak ale počítat prakticky odmocniny? Ukažme zde pro ilustraci použití této metody pro odvození elegantního postupu výpočtu druhé odmocniny (tento postup je znám jako Babylónská metoda či jako Heronův vzorec1). O Mějme dánu diferencovatelnou funkci f(x) a aproximaci jejího kořene x0. O Postupně počítejme další iterace pomocí vztahu xn+\ = xn — fS?"\. T (Xn) Pro výpočet druhé odmocniny z a (tj. hledání kořene funkce f(x) = x2 — a) tak dostáváme iterační postup xn+\ = \{xn + ^-). Tato metoda se dá analogicky použít při optimalizaci, kde místo kořene hledáme řešení rovnice f'{x) = 0. 1To samozřejmě neznamená, že Newton měl něco společného s dávnými Babyloňany, jeho metoda je obecnější. ichal Bulant (PřF MU) latematika (a fyzika) schovaná za GPS irno, 26. února 2014 10 / 25 Příklad Vypočtěme 7Í2 s x0 = 3: xx = ^±4, x2 = 7/2+224/7 = 97/28 « 3,46429, přitom 7l2 « 3,46410. Analýza efektivity Newtonovy metody Pomocí Taylorovy věty lze v nějakém okolí x„ psát f (X) = f(xn) + f'(xn)(x - X„) + ^VX* - X„)2, kde a je mezi x„ a x. Protože hledáme x splňující f(x) = 0, lze po vydělení f'(xn) vztah upravit na ^ + íx-x)--^íx-x)2 a tedy x - xn+i 2/r'(x„) (x - xny Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 11 / 25 Newtonova metoda - příklad, kdy nefunguje Efektivnost odmocňování V našem konkrétním případě funkce f(x) = x2 — a tak dostáváme (f>(x) = 2x, f"{x) = 2) X ~ Xn+l 4x„ (x - xný a je tedy vidět, že chyba \x — x„| se pro vhodná x (obvykle) rychle zmenšuje. Příklad Příkladem funkce, jejíž kořen tato metoda nenajde, ani když začneme sebeblíže, je f(x) = tfx. Zde totiž dostaneme 1/3 1 .-2/3 -2xn 3X" lichal Bulant (PřF ľ i/latematika (a fyzika) scho1 Zobecnění na případ více proměnných Zobecnění na (např.) k rovnic o k neznámých je relativně přímočaré: Xn+l = X„ - JfÍXhY1 ■ F(xn), kde Jp je Jacobián zobrazení F. Výpočet jeho inverze je ale časově velmi náročná operace, proto se často místo toho využívá • řešení příslušné soustavy lineárních rovnic, • výpočet zobecněné inverze, při více než k rovnicích metoda nej menších čtverců • metoda sdružených gradientů pro řešení příslušné soustavy, • různých tzv. Avaz/-n ewto n o vs kých metod, využívajících pouze přibližného Hessiánu (např. BFGS) - viz např. http://demonstrations.wolfram.com/ MinimizingTheRosenbrockFunction/. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 13 / 25 Fyzika a praxe nám to trochu (no ... dost) zkomplikuje Do ideálního stavu ukázaného dříve se nám ale vloudí více či méně závažné chyby: O Satelity disponují vysoce přesnými atomovými hodinami, to ale naše kapesní GPSka neumí (stála by řádově milióny). O Šíří se signál skutečně rychlostí světla i při průchodu ionosférou? O Signál se odráží od různých terénních překážek, budov apod. 0 Do hry velmi zásadně vstupuje i speciální a obecná teorie relativity. Sekunda je podle soustavy SI definována jako doba trvání 9192631 770 period záření, odpovídající přechodu mezi dvěma hladinami velmi jemné struktury základního stavu atomu 133 Cs. [Wiki] Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Brno, 26. února 2014 14 / 25 Zdroje chyb GPS Error Source Typical or Maximum Error Ionosphere 10 Meters Troposphere 1 Meter Satellite Clock Synchronization 1 Meter Electronic Noise 2 Meters Multipath Error 0.5 Meters Satellite Position (Ephemeris) 1 Meter Intentional Degradation 0 Meters Net RMS error 10 Meters Typical Geometric Error (GDOP) 4 Final RMS error (Net x GDOP) 40 meters Actual Typical Error 10 meters Zdroj: http://www.pdhcenter.com/courses/1116/1116content.htm Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 15 / 25 Jak se vyrovnat s chybami - hodiny v přijímači S nepřesností levných hodin v GPS přijímači se vyrovnáme poměrně snadno - k tomu nám slouží právě čtvrtý (a případně další) satelit, který jsme dosud ve výpočtech nepoužili. V praxi tak dostáváme čtyři nebo více rovnic o čtyřech neznámých (x,y,z, error). Na obrázku je pro zjednodušení ukázán 2D případ, kde hodiny v přijímači jsou zpožděny o 0,5 s. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 16 / 25 Jak se vyrovnat s chybami - hodiny v přijímači Pokud je vidět více než čtyři satelity, máme tzv. přeurčený systém rovnic a do hry vstupuje možnost vybrat si z několika možností tu nejlepší -v takovém případě se poloha aproximuje pomocí metody nej menších čtverců. Metoda slouží k rekonstrukci funkce f z hodnot fo,..., fn naměřených v uzlových bodech 3q, ..., a„ . Tuto rekonstrukci hledáme vzhledem k danému modelu - dané posloupnosti funkcí (obecně více proměnných) go{x),gm{x),... - ve tvaru m j=0 Cílem je při tom minimalizovat součet čtverců n J2ifi ~ ym{3i))2- Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 17 / 25 Aproximace metodou nejmenších čtverců Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Ukažme si použití této metody v nejjednodušším případě, kdy máme dáno n bodů ([xi, yi],..., [x„, yn\) a hledáme přímku, která nejlépe vystihuje rozložení těchto bodů. Hledáme tedy funkci tvaru f(x) = a • x + b s neznámými a, b G M tak, aby hodnota X>(*/)-y/)2 byla minimální. S využitím diferenciálního počtu lze snadno odvodit následující tvrzení. Věta Mezi přímkami tvaru f[x) = a • x + b má nejmenší součet čtverců vzdáleností funkčních hodnot v bodech x\,..., x„ od hodnot y funkce splňující a ^ x; + b ■ n = ^ y; Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 19 / 25 Metoda nejmenších čtverců - příklad Příklad Metodou nejmenších čtverců určete regresní přímku odpovídající naměřeným datům: X i 2 3 4 y 1,5 1,6 2,1 3,0 Řešení Data je vhodné seřadit v tabulce podle schématu: X y xy X2 1 1,5 1,5 1 2 1,6 3,2 4 3 2,1 6,3 9 4 3 12 16 10 8,2 23 30 Odtud 30a + 10b = 23,10a + 4b = 8,2, a tedy a = 0,5, b = 0,8. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 20 / 25 Jak se vyrovnat s chybami - teorie relativity GPS ukazuje jeden z nej praktičtějších důsledků teorie relativity - pokud bychom ji nevzali v potaz, bude metoda GPS prakticky nepoužitelná. Atomové hodiny pracují s přesností na nanosekundy (ns = 10~9 s), abychom byli schopni zaručit přesnost zjištění pozice na cca 10 m, je třeba umět určit přesnost času vysílače s přesností cca 30 ns. Přitom se satelity vzhledem k Zemi pohybují rychlostí cca 14 000 km/h. • Do hry tak vstupuje speciální teorie relativity, neboť přijímač a vysílač jsou vůči sobě v pohybu, dochází ke zpomalení hodin vysílače oproti pozorovateli (dilatace času) o ~ 2-(34io5)2 ~ 10 10> tj- as' o 7,7/xs/den. • Další ještě významnější efekt představuje obecná teorie relativity, která implikuje, že hodiny poblíž masivního objektu (Země) jdou pomaleji než hodiny vzdálenější (díky většímu zakřivení prostoročasu). Z povrchu Země vidíme tedy satelitní hodiny jdoucí rychleji než tytéž hodiny umístěné na Zemi o cca 45/xs za den. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 21 / 25 Jak se vyrovnat s chybami - teorie relativity a Nezapočítáním teorie relativity bychom tak dostali chybu v řádu 38/xs za den, což v důsledku znamená cca 10km chybu v určení pozice. • Tato chyba je opravena umělým zpomalením atomových hodin umístěných v satelitech oproti hodinám na Zemi (10,22999999543 MHz oproti 10,23 MHz). Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 22 / 25 Diferenciální GPS Jedno z mnoha možných vylepšení je založeno na myšlence, že relativně blízké přijímače podléhají analogických atmosférickým chybám. Díky pevným stanicím - např. world DGPS database, U.S. Coast Guard NavCen. CZEPOS (VUT/TUBO)- u nichž je s vysokou přesností známa poloha a které vysílají rozdíl mezi touto polohou a polohou vypočtenou na základě informací ze satelitů, je možné u špicových DGPS přístrojů dosáhnout přesnosti v řádu centimetrů. Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 23 / 25 Příklad na závěr Příklad V tabulce jsou uvedena skutečná data z několika satelitů - geocentrické souřadnice jsou uvedeny v metrech, čas přenosu signálu v nanosekundách. Vaším úkolem je s využitím vhodného SW (např OpenOffice Calc, vhodný programovací jazyk, apod.) určit: O geocentrické souřadnice místa pozorovatele, O popsat skutečné místo na Zemi, kde se pozorovatel nacházel (?!). C. sat. x [m] y M z [m] dt [ns] 1 14177553.47 -18814768.09 12243866.38 70446329.64 2 15097199.81 -4636088.67 21326706.55 75142197.81 3 23460342.33 -9433518.58 8174941.25 78968497.2 4 -8206488.95 -18217989.14 17605231.99 69887173.01 5 1399988.07 -17563734.90 19705591.18 67231182.38 6 6995655.48 -23537808.26 -9927906.48 80796265.09 Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS irno, 26. února 2014 24 / 25 Použitá literatura • Wikipedia, The Free Encyclopedia, www.wikipedia.org. • Neil Ashby, Relativity and the Global Positioning System. Physics Today, May 2002. Děkuji za pozornost! Michal Bulant (PřF MU) Matematika (a fyzika) schovaná za GPS Brno, 26. února 2014 25 / 25