metoda Gaussa-Newtona, dopasowanie parametrow krzywej

[andrej]

Witam

Mam krzywa opisnana funkcja f(x) = a*cosh( (x-p)/a) +q (catenary curve) oraz
punkty (x,y) uzyskane z pewnych pomiarow np. (x0,y0), (x1,y1) ... (xk,yk).

Potrzebuje dopasowac parametry (a, p, q) owej krzywej tak by jak najlepiej
odpowiadaly danym.
Funkcja jest nieliniowa, wiec szukalem wiadomosci w Internecie na ten temat;
znalazlem metode Gaussa-Newton'a (opis np.
http://en.wikipedia.org/wiki/Gauss-Newton_algorithm).

Mam problem z utworzeniem macierzy Jakobiana, jak rozmieszczac wartosci
czesciowych pochodnych w tej macierzy, ile ona bedzie miec wierszy? Tyle co
danych? Najlepiej jesli ktos przedstawilby rownanie macierzowe rozpisane dla
mojego przypadku (te pod slowami "and we compute the update δk by solving the
linear system")

PS
przepraszam za moja ignorancje w dziedzinie matematyki

Pozdrawiam,
andrej

[A.L.]

On Tue, 29 Nov 2005 07:19:59 CST, "andrej"

Post by andrej
Witam
Mam krzywa opisnana funkcja f(x) = a*cosh( (x-p)/a) +q (catenary curve) oraz
punkty (x,y) uzyskane z pewnych pomiarow np. (x0,y0), (x1,y1) ... (xk,yk).
Potrzebuje dopasowac parametry (a, p, q) owej krzywej tak by jak najlepiej
odpowiadaly danym.
Funkcja jest nieliniowa, wiec szukalem wiadomosci w Internecie na ten temat;
znalazlem metode Gaussa-Newton'a (opis np.
http://en.wikipedia.org/wiki/Gauss-Newton_algorithm).

Do regresli nieliniowej nagminnie stosuje sie metode Marquardta.
Zapusc google na Levenberg-Marquardt algorithm

A.L.

[s***@poczta.onet.pl]

Witam

Post by A.L.
Do regresli nieliniowej nagminnie stosuje sie metode Marquardta.
Zapusc google na Levenberg-Marquardt algorithm

OK, OK L-M jest modyfikacja algorytmu Gaussa-Newtona, a skoro nie moge poradzic
sobie z G-N wiec z L-M rowniez nie dam rady ... wzor w L-M jest niemal identyczny;

Przeczeslem caly internet, nie znajdujac jakiegos konkretnego przykladu na
uzycie G-M (pseudokod, przyklad, coklowiek)... no oprocz
http://www2.imm.dtu.dk/courses/02611/nllsq.pdf, np. Example 3.3 co to f(x) i
F(x) w tym przykladzie ? Nie potrafie zakapowac jak tworzonejest te rownanie
macierzowe, jak tworzony jest jakobian ... i gdzie tu miejsce na punkty (dane)?

Pozdrawiam,
andrej

[przezroczystek]

Post by s***@poczta.onet.pl
Przeczeslem caly internet, nie znajdujac jakiegos konkretnego przykladu na
uzycie G-M (pseudokod, przyklad, coklowiek)... no oprocz
http://www2.imm.dtu.dk/courses/02611/nllsq.pdf, np. Example 3.3 co to f(x) i
F(x) w tym przykladzie ? Nie potrafie zakapowac jak tworzonejest te rownanie
macierzowe, jak tworzony jest jakobian ... i gdzie tu miejsce na punkty (dane)?

1)Szukasz funkcj f(x), np. f(x) = a*cos(b*x) + b*sin(a*x)
2)Masz dane eksperymentalne g(x)
3)Przyjmuesz jakieś kryterium błędu, np. minimalizujesz kwadrat
odległości pomiędzy wszystkimi danymi a Twomi wzorem, oznaczasz
go funkcją h:
h = sum ( ( f(x[i]) - g(x[i]) )^2 )
4)Teraz chcesz dopasować parametry a i b w taki sposób, aby
funkcja h (czyli błąd) była jak najmniejsza. Funkcja przyjmuje
tam minimum, gdzie jej pochodne są równe zero. Więc musisz
rozwiązać układ równań:
dh/da = 0
dh/db = 0
Jeśli układ jest liniowy to jest cała filozofia.
5) Jeśli układ nie jest liniowy, to funkcję błędu przybliżasz
szeregiem Taylora do jakiegoś tam wyrazu. W wyniku takiego
przybliżenia wyjdzie Ci wielomian, którego pochodne utworzą
już liniowy układ równań. Jednak aby to uzyskać, trzeba
przybliżać do wielu wyrazów, ilość parametrów rośnie wykładniczo i
nawet w prostym zadaniu szybko stracisz stabilość numeryczną i
braknie pamięci, więc stosuje się najczęściej dwa podejścia:
a) Podczas przybliżania szeregiem Taylora wykorzystuje się
tylko informację o pierwszej pochodnej. Wtenczas iteracyjnie
poszukujesz minimum przeciwnie do znaków pochodnych po
wszystkich parametrach. To są algorytmy typu: największy
spadek, gradienty sprzężone, itd
b) Wykorzystujesz informację o pierwszej i drugiej pochodnej.
Drugie pochodne w rozwinięcu Taylora są do potęgi drugiej.
Wyjdzie Ci równanie stopnia drugiego, wyliczysz jego pochodną i
będziesz wiedział gdzie jest jego minimum. Jednak jest to możliwe
tylko wtedy, gdy w wyniku przybliżenia wzorem Taylora, macierz
drugich pochodnych jest dodatnio określona ( dla przykładu
z jednym parametrem, jest to analogiczne do paraboli z ramionami u
góry, wtenczas można szukać jej minimum ). Żeby nie było takich
kłopotów, stosuje się algorytmy z grupy algorytmów zmiennej
metryki, które przyrostowo uaktualniają macierz drugich pochodnych w
sposób zapewniający ten warunek.

To tak pokrótce... Rozwiąż najpierw jakieś najprostsze zadania, dobieraj
tylko jeden parametr, aby na początku uniknąć rachunków macierzowych...
po prostu potrenuj :)


Powodzenia
Mariusz

[przezroczystek]

Post by s***@poczta.onet.pl
Przeczeslem caly internet, nie znajdujac jakiegos konkretnego przykladu na
uzycie G-M (pseudokod, przyklad, coklowiek)... no oprocz
http://www2.imm.dtu.dk/courses/02611/nllsq.pdf, np. Example 3.3 co to f(x) i
F(x) w tym przykladzie ? Nie potrafie zakapowac jak tworzonejest te rownanie
macierzowe, jak tworzony jest jakobian ... i gdzie tu miejsce na punkty

Np. chcesz dane doświadczalne f(x) wyrazić funkcją: g(x) .
Tworzysz funkcję h = (f(x) - g(x))^2
Będziesz teraz minimalizował funkcję h, zmieniając parametry a i b.
Czyli masz funkcję h(a,b), znasz jej wartość i chesz poszukać
takich liczb pa i pb aby h(a+pa,b+pb) < h(a,b)
Rozwijasz w szereg Taylora h(a+pa,b+pb) =
h(a,b) +
dh/da * pa +
dh/db * pb + 0.5* (
dh/daa * pa * pa +
dh/dbb * pb * pb +
2 * dh/dab * pb * pa )
Aby dowiedzieć się jakie wartości pb i pa dają minimum tego urpszczonego
wzoru, nalezy poszukać pochodnych dh/pa i dh/pb. Wartości: h(a,b), dh/da,
dh/db, dh/daa, dh/dbb i dh/dab wyliczasz z danych zadania i z wyprowadzonych
wozrów na pochodne. Przybliżenie to jest wielomianem, więc pochodne po
pa i pb będą funkcjami liniowymi, dla których możesz rozwiązać układ
równań. Aby uprościć zapis, wyjdzie Ci taki wielomian do minimalizowania:

W = h(a,b) + c1*pa + c2*pb + c3*pa*pa + c4*pb*pb + c5*pa*pb

Liczysz pochodną po pa i po pb:
dW/dpa = c1 + c3*pa + c5*pb
dw/dpb = c2 + c4*pb + c5*pa

przyrównujesz do zera i masz układ liniowych równań:
-c1 = c3*pa + c5*pb
-c2 = c4*pb + c5*pa

Problemem jest warunek wklęsłości - jeśli druga pochodna jest wypukła, ( ramiona
przybliżenia parabolicznego na dole ) to nie obliczony wektor korekty [pa,pb]
nie zaprowadzi Cię do minimum. Wtenczas możesz zastosować tylko rozwinięcie
do do dwóch pierwszych członów Taylora ( do pierwszej pochodnej )
h(a+pa,b+pb) = h(a,b) + dh/da*pa + dh/db*pb. Wtenczas pochodna h/pa = dh/da i
h/pb = dh/db. Cały czas szukasz wartości zerowych dla pochodnych, więc jak
pochodna jest dodatnia, to odejmujesz, jak ujemna, to dodajesz. Możesz np.
przyjąć pa = -u*dh/da i pb = -u*dh/db, gdzie u będzie jakąś małą liczbą, tak
żeby do minimum przybliżać się z pewnym małym krokiem.

Innym sposobem jest zastosowanie algorymu zmiennej metryki, aby uniknąć
problemu ujemnego określenia macierzy drugich pochodnych.


To tyle...
pozdrawiam
Mariusz

[przezroczystek]

Post by andrej
Witam
Mam krzywa opisnana funkcja f(x) = a*cosh( (x-p)/a) +q (catenary curve) oraz
punkty (x,y) uzyskane z pewnych pomiarow np. (x0,y0), (x1,y1) ... (xk,yk).
Potrzebuje dopasowac parametry (a, p, q) owej krzywej tak by jak najlepiej
odpowiadaly danym.
Funkcja jest nieliniowa, wiec szukalem wiadomosci w Internecie na ten temat;
znalazlem metode Gaussa-Newton'a (opis np.
http://en.wikipedia.org/wiki/Gauss-Newton_algorithm).
Mam problem z utworzeniem macierzy Jakobiana, jak rozmieszczac wartosci
czesciowych pochodnych w tej macierzy, ile ona bedzie miec wierszy? Tyle co
danych? Najlepiej jesli ktos przedstawilby rownanie macierzowe rozpisane dla
mojego przypadku (te pod slowami "and we compute the update &#948;k by solving the
linear system")

Ale uważaj, bo metoda Newtona jest metodą raczej teoretyczną, gdyż wymaga
dodatniego określenia macierzy drugich pochodnych. Uprość ją do metody
wykorzystujących informację tylko o pierwszych pochodnych, albo
zastosuj algorytm zmiennej metryki, który zapewnia takie dodatnie
określenie macierzy drugich pochodnych. Ja bym takie prose
zadanie (tylko trzy parametry) próbował zoptymalozować jakąś metodą
bezgradientową, np. symulowane wyżarzanie, metoda Hooka-Jeevesa,
Gaussa-Seidela, itd.


Pozdrawiam
Mariusz

[thrunduil]

Post by andrej
Mam krzywa opisnana funkcja f(x) = a*cosh( (x-p)/a) +q (catenary curve) oraz
punkty (x,y) uzyskane z pewnych pomiarow np. (x0,y0), (x1,y1) ... (xk,yk).
Potrzebuje dopasowac parametry (a, p, q) owej krzywej tak by jak najlepiej
odpowiadaly danym.

a w czym chcesz to zrobic?
samodzielne kodowanie gausa-newtona, ktory dziala to nie jest takie
trywialne zadanie
standardowe algorytmy dostepne w matlabie/octave powinny ten problem
rozwiazac bez problemu
nawet bez znajomosci jacobianu.

[Wlodzimierz Holsztynski]

Post by andrej
Mam krzywa opisnana funkcja f(x) = a*cosh( (x-p)/a) +q (catenary curve) oraz
punkty (x,y) uzyskane z pewnych pomiarow np. (x0,y0), (x1,y1) ... (xk,yk).
Potrzebuje dopasowac parametry (a, p, q) owej krzywej tak by jak najlepiej
odpowiadaly danym.

Mozna w duchu Gaussa i Legrende'a minimalizowac
blad kwadrastowy, czyli funkcje:

err : R^3 --> [0;oo)

dana wzorem:

err(a p q) := Suma ( (f(x_j) - y_j)^2 : j=0...k )

Poniewaz dla wielkich wartosci |(a p q)| err jest wielki
(dazy do oo, gdy |(a p q)| --> oo), to globalne
minimum err jest tez lokalnym, a wiec mozna
je znalezc rozpatrujac punkty (a p q) dla ktorych
wszystkie trzy pochodne czastkowe sa zero.

W danym przypadku z latwoscia znajdziemy
wartosc q = q(a p), przyrownujac pochodna
czastkowa po q do zera. Dostaniemy rownanie
liniowe wzgledem q.

Podstawiajac, problem redukujemy do dwoch
zmiennych a p:

Err(a p) := err(a p q(a p))

Musze poprzestac na tym kroczku i konczyc,
pedze,

******
Wlodzimierz Holsztynski