rozwiąż ukł.równań nieliniowych-pozycja punktu 3D

[jozek]

Witam
Niestety nie mogłem znaleźć odpowiedzi na moje pytanie więc zadaje je tutaj.

Zadanie sprowadza się do obliczenia pozycji użytkownika znajdującego się na powierzchni ziemi (3D) względem satelitów krążących po orbitach wokół Ziemi. Jest to odzwierciedlenie działania systemu GPS czyli znając pozycję 4 lub więcej satelitów w układzie współrzędnych kartezjańskich oraz odległości między satelitami a użytkownikiem należy obliczyć pozycję użytkownika ( Xu, Yu, Zu) oraz odchylenie zegara odbiornika bu. Zadanie wydaje się proste i sprowadza sie do rozwiązania układu 4 lub więcej równań nieliniowych z 4 niewiadomymi. Jak najbardziej wskazana jest przybliżona metoda bo ma być to napisane w jezyku C++ i program będzie to obliczać ( wskazane jest, aby algorytm nie był mocno skomplikowany).
Oto powyższe równiania:




Próbowałem rozwiązać to w sposób zaczerpnięty z ksiązki wg takiej metody, że dokonywana jest linearyzacja równania , podstawia się za niewiadome 0,0,0,0 i otrzymuje jakieś przybliżone rozwiązanie, które znów podstawia się do równań i tak w kółko, aż po kilku lub kilkudziesięciu iteracjach otrzymuje przybliżony wynik (z błedem mniejszym niż 0,01 ).Niestety z tym algorytmem jest coś jest nie tak, bo rozwiązując to na kartce papieru czy też programem wg. takiego algorytmu otrzymuje jakieś bzdurne wyniki .

Byłbym wdzięczy za wszelką pomoc i podpowiedzi.

pozdrawiam
Józio

Ps. Przepraszam jeśli napisałem w złym dziale.


[edit] Pozwoliłem sobie przenieść do Infy, gdyż z tego co rozumiem, twoim zadaniem jest napisać do tego program w C++ - ten dział wydał mi sie bardziej odpowiedni. Pozdrawiam

[ Dodano: Pon Maj 23, 2005 11:06 pm ]
Widzę, że starszna cienizna tutaj .
Czyżby nikt nie miał bladego pojęcia o co chodzi i nie wiedział jak rozwiązać taki układ równań ???

[bisz]

z tego co pamietam z nawigacji to 3 satelity wystarcza do polozenia a czwarta to wysokosci, uzylem programu matlab i funkcji solve dla ukladow nieliniowych, z tym ze oburzyl sie co do 3 niewiadomych i 4 rownan wiec skorzystalem tylko z 3 i o to co otrzymalem:

>> [xu,yu,zu]=solve('sqrt((x1-xu)^2+(y1-yu)^2+(z1-zu)^2)+b=p1','sqrt((x2-xu)^2+(y2-yu)^2+(z2-zu)^2)+b=p2','sqrt((x3-xu)^2+(y3-yu)^2+(z3-zu)^2)+b=p3')

xu =

[ xu+(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]
[ xu+(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]
[ xu+(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]
[ xu+(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]
[ xu-(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]
[ xu-(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]
[ xu-(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]
[ xu-(-y1^2+2*y1*yu-yu^2-z1^2+2*z1*zu-zu^2+b^2-2*b*p1+p1^2)^(1/2)]


yu =

[ xu+(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]
[ xu+(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]
[ xu-(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]
[ xu-(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]
[ xu+(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]
[ xu+(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]
[ xu-(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]
[ xu-(-y2^2+2*y2*yu-yu^2-z2^2+2*z2*zu-zu^2+b^2-2*b*p2+p2^2)^(1/2)]


zu =

[ xu+(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]
[ xu-(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]
[ xu+(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]
[ xu-(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]
[ xu+(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]
[ xu-(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]
[ xu+(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]
[ xu-(-y3^2+2*y3*yu-yu^2-z3^2+2*z3*zu-zu^2+b^2-2*b*p3+p3^2)^(1/2)]

>>

moze to ci sie przyda
chociaz widze ze rozwiazanie sa wzajemnie iod siebie zalezne wiec pewnie nie o to bedize tobie chodzilo... musze poznac doglebniej funkcje solve

[jozek]

To są 4 równania i 4 niewiadome : x,y,z, bu (a nie 3 niewiadome).

Teoretycznie do wynaczenia pozycji 3D (3 wymiarowej) potrzeba 3 satelitów jednak w rzeczywistości "technicznej" potrzeba ich 4. Bo odległość od satelity to tak naprawdę nie jest dokładnie znana, bo zegar satelity i odbiornika nie jest idealnie zsynchronizowany i nigdy nie będzie. Tą odległość znamy w przybliżeniu a w równaniach należy zatem uwzględnić bład zegara bu a więc potrzebujemy conamniej 4 satelitów do obliczenia pozycji. W praktyce jeżeli odbiornik odbiera np. 7 sygnałów satelitów wykorzystuje je wszystkie do obliczenia pozycji lub wybiera wg odpowiedniego algorymu 4 "najlepsze" spośród nich.


Czy ktoś wie ile jest możliwych rozwiązań takiego ukł. równań ??
Należy to sobie wyobrazić jako 4 okręgi w układzie 3 wymiarowym.

[lagesag]

Witam. O ile się nie mylę, satelity krążą wokół Ziemi w jednej płaszczyźnie (płaszczyźnie równika). Można więc obrać prostokątny układ współrzędnych XYZO, gdzie oś Z przechodzi przez oś obrotu ziemi. Wtedy współrzędne statelitów:
\(\displaystyle{ z_{1}=z_{2}=z_{3}=z_{4}=0}\)
Przyjmuję też, że błędy są mniejesze od pomiarów odległości. Przy tych dwóch założeniach układ równań przyjmuje postać (1):
\(\displaystyle{ (\rho_{1}-b_{u})^{2}=(x_{1}-x_{u})^{2}+(y_{1}-y_{u})^{2}+z_{u}^{2}\\(\rho_{2}-b_{u})^{2}=(x_{2}-x_{u})^{2}+(y_{2}-y_{u})^{2}+z_{u}^{2}\\(\rho_{3}-b_{u})^{2}=(x_{3}-x_{u})^{2}+(y_{3}-y_{u})^{2}+z_{u}^{2}\\(\rho_{4}-b_{u})^{2}=(x_{4}-x_{u})^{2}+(y_{4}-y_{u})^{2}+z_{u}^{2}}\)
Równania te można odjąć stronami, np.: od pierwszego drugie, od trzeciego czwarte i od drugiego trzecie. W ten sposób po uproszczeniu powstanie układ równań (2):
\(\displaystyle{ 2(x_{2}-x_{1})x_{u}+2(y_{2}-y_{1})y_{u}+2(\rho_{1}-\rho_{2})b_{u}=(\rho_{1}^2-\rho_{2}^{2}+x_{2}^{2}-x_{1}^{2}+y_{2}^{2}-y_{1}^2)\\2(x_{4}-x_{3})x_{u}+2(y_{4}-y_{3})y_{u}+2(\rho_{3}-\rho_{4})b_{u}=(\rho_{3}^2-\rho_{4}^{2}+x_{4}^{2}-x_{3}^{2}+y_{4}^{2}-y_{3}^2)\\2(x_{1}-x_{3})x_{u}+2(y_{1}-y_{3})y_{u}+2(\rho_{3}-\rho_{1})b_{u}=(\rho_{3}^2-\rho_{1}^{2}+x_{1}^{2}-x_{3}^{2}+y_{1}^{2}-y_{3}^2)}\)
Układ ten można rozwiązać metodą wyznaczników. Następnie wartość \(\displaystyle{ z_{u}}\) trzeba wyznaczyć z jednego z równań układu (1). Dziubanie tego po kolei jest oczywiście makabrycznie skomplikowane, ale od czego jest c++? Wynika z tego, że zadany układ równań będzie miał dwie możliwe czwórki rozwiązań. Zgadzałoby się to z obrazowaniem równań jako czterech okręgów w przestrzeni 3D (choć nie za bardzo widzę te okręgi w równaniach) - układ czterech okręgów może mieć maksymalnie dwa rozwiązania (wszystkie okęgi mają wtedy wspólną cięciwę).

Oczywiście nie jestem pewien czy to rozumowanie jest prawidłowe, więc przyda się weryfikacja. Nie wiem zresztą na ile problem jest aktualny. Pozdrawiam.

[jozek]

Witam. O ile się nie mylę, satelity krążą wokół Ziemi w jednej płaszczyźnie (płaszczyźnie równika).

To się myslisz i to bardzo . Nie wchodząc w szczegóły techniczne, gdyby satelity krążyły w płaszczyźnie równika nie byłoby sensu wogóle tworzenie systemu GPS, a w najlepszym wypadku obliczenie pozycji byłoby możliweo tylko w pobliżu równika i to z dość dużym błedem .

A tak na marginesie to problem juz rozgryzłem sam, bo zanim doczekałem się jakiejkolwiek odpowiedzi mineło trochę czasu.
Problem został rozwiązany w sposób o którym pisałem w pierwszym poście. W metodzie tamtej (z ksiązki) był jednak mały błąd, ale go znalazłem i teraz już program działa.
Ta metoda jest stosunkowo szybka i w miarę nieskomplikowana, bo pamiętajmy, że takie obliczenia muszą być dokonane w odbiorniku GPS który posiada dość prosty procek i nie za wiele pamięci, a zatem algorytm nie może byc specjalnie złożony obliczeniowo.

[lagesag]

No tak. Lekka zaćma. Ale jednak orbity te leżą zawsze w płaszczyźnie największego przekroju kuli? Tak czy owak kropka.

[jozek]

Nie wchodząc w szczegóły konstelacja składa się z 24 satelitów. Satelity są umieszczone na 6 stałych orbitach kołowych na wysokości ok 20000 km nad ziemskim równikiem. Płaszczyzny orbit satelitów są rozłożone równomiernie co 60 st długości geograficznej, aby pokrywały całkowicie kąt pełny 360st. Czas obiegu satelity wokół Ziemi wynosi w przybliżeniu 12h, a nachylenie płaszczyzny orbity do płaszczyzny równika wynosi ok.55st.
Wzajemne położenie satelitów dobrano tak, aby zapewnić w każdym punkcie Ziemi widoczność jak największej ilości. Orbity są tak położone, że w dowolnym punkcie globu z praawdopodobieństwem 99,4% widocznych jest 6 do 10 satelitów, a więc więcej niż jest wymagane do obliczenia pozycji.
Po szczegóły i rysunki odsyłam do internetu