Witam

Szukam dobrego metakodu, dobrze okomentowanego do minimalizacji
funkcji odmianami metody zmiennej metryki. Możecie zapodać
jakieś linki?

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:52095b15-41a9-4c5f-94e0-1fe57d038d82@u26g2000yq
u.googlegroups.com...
> Szukam dobrego metakodu, dobrze okomentowanego do minimalizacji
> funkcji odmianami metody zmiennej metryki. Możecie zapodać
> jakieś linki?

Polecam książkę "Metody optymalizacji w języku Fortran", można ją znaleźć w
bibliotece lub używaną trafić tanio na Allegro. Nie wiem o metakodzie ale
mozna znaleźć kod w fortranie lbfgs_um.tar.gz na
http://www.eecs.northwestern.edu/~nocedal/lbfgs.html czy w C:
liblbfgs-1.9.tar.gz na http://www.chokkan.org/software/liblbfgs/
Z polksih pdf np. http://student.agh.edu.pl/~tomash/bfgs.pdf

Pozdrawiam

do góry

On 25 Lip, 17:47, "Borneq" <b...@a...hidden.pl> wrote:
> Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w
wiadomościnews:52095b15-41a9-4c5f-94e0-1fe57d038d82@
u26g2000yqu.googlegroups.com...
>
> > Szukam dobrego metakodu, dobrze okomentowanego do minimalizacji
> > funkcji odmianami metody zmiennej metryki. Możecie zapodać
> > jakieś linki?
>
> Polecam książkę "Metody optymalizacji w języku Fortran", można ją znaleźć w
> bibliotece lub używaną trafić tanio na Allegro. Nie wiem o metakodzie ale
> mozna znaleźć kod w fortranie lbfgs_um.tar.gz
nahttp://www.eecs.northwestern.edu/~nocedal/lbfgs.ht
mlczy w C:
> liblbfgs-1.9.tar.gz nahttp://www.chokkan.org/software/liblbfgs/
> Z polksih pdf np.http://student.agh.edu.pl/~tomash/bfgs.pdft

Dziękuję, rozejrzę się zaraz.

Sam znalazłem coś takiego:
http://optymalizacja.w8.pl/QuasiNewton.html
Przydałoby mi się coś właśnie w takiej formie, ale bardziej
rozbudowane, o większą ilość heurystyk, z opisem najczęstszych
problemów jakie napotyka algorytm i ich rozwiązań. Nie wiem
czy to prawda, ale słyszałem że dobra(!) implementacja tego
algorytmu składa się z kilkudziesięciu tys. linii kod.

Przy okazji mam jeszcze jedno pytanie: jak dokładnie obliczyć
numerycznie pochodną? Jakie są lepsze algorytmy niż:

df/dx = ( f(x + epsilon ) - f(x) ) / epsilon


Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
news:d6d65a27-f4c0-45c7-9e61-e10fcc3d7d8d@l14g2000yq
l.googlegroups.com...
> Przy okazji mam jeszcze jedno pytanie: jak dokładnie obliczyć
> numerycznie pochodną? Jakie są lepsze algorytmy niż:
> df/dx = ( f(x + epsilon ) - f(x) ) / epsilon

Na przykład użycie większej ilości niż dwóch punktów
http://www.zftik.agh.edu.pl/mof/lab/a5.pdf
to dla pochodnej jednej zmiennej

do góry

On 2010-07-25, Mariusz Marszałkowski <m...@g...com> wrote:
[...]
> Przy okazji mam jeszcze jedno pytanie: jak dokładnie obliczyć
> numerycznie pochodną? Jakie są lepsze algorytmy niż:
>
> df/dx = ( f(x + epsilon ) - f(x) ) / epsilon

Dokładnie i numerycznie to oksymoron ;) Natomiast
lepsze wyniki możesz dostawać z

f'(x_0)= \frac{f(x_0+\epsilon)-f(x_0-\epsilon)}{2\epsilon}

Przy czym należy dodać, że polepszenie dokładności nie wynika tutaj z
jakiegoś wpływu na obliczenia numeryczne, ale z wyeliminowania błędu
(przybliżenia) rzędu \epsilon^2 .

MK

do góry

On 25 Lip, 21:53, Marcin Konopka <d...@n...abc> wrote:
> On 2010-07-25, Mariusz Marszałkowski <m...@g...com> wrote:
> [...]
>
> > Przy okazji mam jeszcze jedno pytanie: jak dokładnie obliczyć
> > numerycznie pochodną? Jakie są lepsze algorytmy niż:
>
> > df/dx = ( f(x + epsilon ) - f(x) ) / epsilon
>
> Dokładnie i numerycznie to oksymoron ;) Natomiast
> lepsze wyniki możesz dostawać z
>
> f'(x_0)= \frac{f(x_0+\epsilon)-f(x_0-\epsilon)}{2\epsilon}
>
> Przy czym należy dodać, że polepszenie dokładności nie wynika tutaj z
> jakiegoś wpływu na obliczenia numeryczne, ale z wyeliminowania błędu
> (przybliżenia) rzędu \epsilon^2 .

Dziękuję za odpowiedź. Metoda którą przedstawiłeś zwie się chyba
pochodną centralną.

A jakby tak policzyć kilka razy i aproksymować wielomianem?

Np pięć razy:
step[5] = { -2 , -1 , 0 , +1 , +2 }
f_i'( x + step_i ) = ( f( x + step_i + epsilon ) - f( x +
step_i ) ) / epsilon

Następnie zrobić aproksymację f'(x) = axx + bx + c i odczytać wartość
dla x = 0.

Co sądzicie?

Pozdrawiam

do góry

On 26 Lip, 00:01, Mariusz Marszałkowski <m...@g...com> wrote:
> On 25 Lip, 21:53, Marcin Konopka <d...@n...abc> wrote:
>
>
>
>
>
> > On 2010-07-25, Mariusz Marszałkowski <m...@g...com> wrote:
> > [...]
>
> > > Przy okazji mam jeszcze jedno pytanie: jak dokładnie obliczyć
> > > numerycznie pochodną? Jakie są lepsze algorytmy niż:
>
> > > df/dx = ( f(x + epsilon ) - f(x) ) / epsilon
>
> > Dokładnie i numerycznie to oksymoron ;) Natomiast
> > lepsze wyniki możesz dostawać z
>
> > f'(x_0)= \frac{f(x_0+\epsilon)-f(x_0-\epsilon)}{2\epsilon}
>
> > Przy czym należy dodać, że polepszenie dokładności nie wynika tutaj z
> > jakiegoś wpływu na obliczenia numeryczne, ale z wyeliminowania błędu
> > (przybliżenia) rzędu \epsilon^2 .
>
> Dziękuję za odpowiedź. Metoda którą przedstawiłeś zwie się chyba
> pochodną centralną.
>
> A jakby tak policzyć kilka razy i aproksymować wielomianem?
>
> Np pięć razy:
> step[5] = { -2 , -1 , 0 , +1 , +2 }
>  f_i'( x + step_i ) = ( f( x + step_i + epsilon ) - f( x +
> step_i ) ) / epsilon
>
> Następnie zrobić aproksymację f'(x) = axx + bx + c i odczytać wartość
> dla x = 0.
>
> Co sądzicie?
>
> Pozdrawiam

A co Ci da aproksymacja wielomianem w 5-ciu punktach? To że wielomian
będzie miał te same wartości w tych 5-ciu punktach. Jeśli użyjesz tych
samych punktów do wyliczenia pochodnej to Ci wyjdzie to samo co bez
aproksymacji. A jak użyjesz innych punktów- no cóż, dostaniesz coś
innego, tylko nie bardzo wiadomo co.

do góry

On 27 Lip, 19:32, nightwatch77 <r...@g...com> wrote:
> On 26 Lip, 00:01, Mariusz Marszałkowski <m...@g...com> wrote:
>
>
>
> > On 25 Lip, 21:53, Marcin Konopka <d...@n...abc> wrote:
>
> > > On 2010-07-25, Mariusz Marszałkowski <m...@g...com> wrote:
> > > [...]
>
> > > > Przy okazji mam jeszcze jedno pytanie: jak dokładnie obliczyć
> > > > numerycznie pochodną? Jakie są lepsze algorytmy niż:
>
> > > > df/dx = ( f(x + epsilon ) - f(x) ) / epsilon
>
> > > Dokładnie i numerycznie to oksymoron ;) Natomiast
> > > lepsze wyniki możesz dostawać z
>
> > > f'(x_0)= \frac{f(x_0+\epsilon)-f(x_0-\epsilon)}{2\epsilon}
>
> > > Przy czym należy dodać, że polepszenie dokładności nie wynika tutaj z
> > > jakiegoś wpływu na obliczenia numeryczne, ale z wyeliminowania błędu
> > > (przybliżenia) rzędu \epsilon^2 .
>
> > Dziękuję za odpowiedź. Metoda którą przedstawiłeś zwie się chyba
> > pochodną centralną.
>
> > A jakby tak policzyć kilka razy i aproksymować wielomianem?
>
> > Np pięć razy:
> > step[5] = { -2 , -1 , 0 , +1 , +2 }
> >  f_i'( x + step_i ) = ( f( x + step_i + epsilon ) - f( x +
> > step_i ) ) / epsilon
>
> > Następnie zrobić aproksymację f'(x) = axx + bx + c i odczytać wartość
> > dla x = 0.
>
> > Co sądzicie?
>
> > Pozdrawiam
>
> A co Ci da aproksymacja wielomianem w 5-ciu punktach?
Chyba nic nie da. A aproksymacja/interpolacja funkcji wielomianem i
później pochodna wielomianu z wzoru analitycznego coś pomoże?

Pozdrawiam

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
grup
dyskusyjnych:ad4f3a7f-1422-41ed-aff2-388857f2b1d0@t1
1g2000vbj.googlegroups.com...
> Chyba nic nie da. A aproksymacja/interpolacja funkcji wielomianem i
> później pochodna wielomianu z wzoru analitycznego coś pomoże?

Dobrej zabawy, potrzebna tylko Mathematica, tu jest wielomian Lagrange, ale
można dawać co sie chce, byle interpolowało (i w tym właśnie jest cały
dowcip, że nie jest to bynajmniej trywialne, o czym niestety zapomina
zdecydowana większość podręczników). Pierwszy parametr to liczba punktów,
drugi to stopień pochodnej.

In[1]:= diff[m_, n_] := Module[{},
D[InterpolatingPolynomial[Table[{x[0] + j h, y[j]}, {j, 0, m}], t], {t,
n}] // FullSimplify]

In[2]:= diff[1, 1]
Out[2]= (-y[0] + y[1])/h

In[3]:= diff[2, 2]
Out[3]= (y[0] - 2 y[1] + y[2])/h^2

In[4]:= diff[3, 1]
Out[4]= (1/(6 h^3))(-3 (t - x[0])^2 (y[0] - 3 y[1] + 3 y[2] - y[3]) + 6 h
(t - x[0]) (2 y[0] - 5 y[1] + 4 y[2] - y[3]) + h^2 (-11 y[0] + 18 y[1] - 9
y[2] + 2 y[3]))

slawek

P.S. Jak ktoś lubi - 12-punktowy wzorek na pierwszą pochodną. Milusi.

In[5]:= diff[12, 1]

Out[5]= (1/(239500800 h^12))(6 (t - x[0])^11 (y[0] - 12 y[1] +
66 y[2] - 220 y[3] + 495 y[4] - 792 y[5] + 924 y[6] - 792 y[7] +
495 y[8] - 220 y[9] + 66 y[10] - 12 y[11] + y[12]) -
33 h (t - x[0])^10 (13 y[0] - 154 y[1] + 836 y[2] - 2750 y[3] +
6105 y[4] - 9636 y[5] + 11088 y[6] - 9372 y[7] + 5775 y[8] -
2530 y[9] + 748 y[10] - 134 y[11] + 11 y[12]) -
1485 h^3 (t - x[0])^8 (169 y[0] - 1932 y[1] + 10128 y[2] -
32196 y[3] + 69129 y[4] - 105624 y[5] + 117768 y[6] -
96552 y[7] + 57771 y[8] - 24604 y[9] + 7080 y[10] - 1236 y[11] +
99 y[12]) +
55 h^2 (t - x[0])^9 (247 y[0] - 2880 y[1] + 15390 y[2] -
49840 y[3] + 108945 y[4] - 169344 y[5] + 191940 y[6] -
159840 y[7] + 97065 y[8] - 41920 y[9] + 12222 y[10] -
2160 y[11] + 175 y[12]) +
132 h^4 (t - x[0])^7 (22711 y[0] - 253212 y[1] + 1296366 y[2] -
4030540 y[3] + 8476785 y[4] - 12705912 y[5] + 13918884 y[6] -
11228472 y[7] + 6620265 y[8] - 2782060 y[9] + 790926 y[10] -
136572 y[11] + 10831 y[12]) -
693 h^5 (t - x[0])^6 (34983 y[0] - 377594 y[1] + 1876756 y[2] -
5680990 y[3] + 11665395 y[4] - 17118276 y[5] + 18405408 y[6] -
14606652 y[7] + 8489565 y[8] - 3523170 y[9] + 990668 y[10] -
169414 y[11] + 13321 y[12]) -
825 h^7 (t - x[0])^4 (624455 y[0] - 6084008 y[1] + 27722152 y[2] -
78076984 y[3] + 151151631 y[4] - 211459728 y[5] +
218717352 y[6] - 168168048 y[7] + 95221749 y[8] -
38664776 y[9] + 10673648 y[10] - 1796824 y[11] + 139381 y[12]) +
288 h^10 (t - x[0]) (6706804 y[0] - 41976720 y[1] +
142878780 y[2] - 337836400 y[3] + 587250675 y[4] -
764853408 y[5] + 752145240 y[6] - 557076960 y[7] +
306489150 y[8] - 121646800 y[9] + 32966604 y[10] -
5465520 y[11] + 418555 y[12]) -
396 h^9 (t - x[0])^2 (5356117 y[0] - 42005376 y[1] +
163511064 y[2] - 413694720 y[3] + 745259265 y[4] -
992058624 y[5] + 989989392 y[6] - 740994048 y[7] +
410915295 y[8] - 164103040 y[9] + 44692632 y[10] -
7439616 y[11] + 571659 y[12]) +
33 h^6 (t - x[0])^5 (4090021 y[0] - 42283560 y[1] +
202378170 y[2] - 593031160 y[3] + 1184651955 y[4] -
1698651792 y[5] + 1791395340 y[6] - 1398858480 y[7] +
802063035 y[8] - 329051080 y[9] + 91621146 y[10] -
15536280 y[11] + 1212685 y[12]) +
88 h^8 (t - x[0])^3 (14936519 y[0] - 133608168 y[1] +
569977974 y[2] - 1529302040 y[3] + 2859027975 y[4] -
3899983248 y[5] + 3959062716 y[6] - 3000900528 y[7] +
1680271965 y[8] - 676161800 y[9] + 185286654 y[10] -
31000248 y[11] + 2392229 y[12]) -
8640 h^11 (86021 y[0] - 332640 y[1] + 914760 y[2] - 2032800 y[3] +
3430350 y[4] - 4390848 y[5] + 4268880 y[6] - 3136320 y[7] +
7 (245025 y[8] - 96800 y[9] + 26136 y[10] - 4320 y[11] +
330 y[12])))

do góry

Użytkownik "slawek" <s...@h...pl> napisał w wiadomości grup
dyskusyjnych:4c4f5d44$0$19168$6...@n...neostrad
a.pl...
> P.S. Jak ktoś lubi - 12-punktowy wzorek na pierwszą pochodną. Milusi.

13-punktowy, 1+12

slawek

do góry