Potrzebuje algorytmu monte carlo dla reszt kwadratowych.

Algorytm ten słuzy do generacji liczb przypadkowych zgodnych z zadanym rozkładem. Niech X = (x1; : : : ; xd) bedzie połozeniem punktu w d-wymiarowej przestrzeni. Zadanie polega na generacji ciagu punktów: X0;X1; : : : ;Xi; : : : ;Xd (18.1) rozłozonych zgodnie z zadanym rozkładem o funkcji wagowej w(X) (zakładamy unormowanie). Idea algorytmu opiera sie na bładzeniu przypadkowym, które mozna zrealizowac w przypadkowej wedrówce. W pewnej chwili wedrowiec znajduje sie w punkcie Xi ciagu (18.1). Generacja kolejnego punktu Xi+1 polega na wykonaniu próbnego kroku do nowego punktu Xt. Ten nowy punkt mozna wybrac zgodnie z rozkładem jednorodnym wewnatrz d-wymiarowego szescianu o boku ± zbudowanego wokół punktu Xi. Obliczamy r = w(Xt) w(Xi) (18.2) Jezeli: (i) r > 1 – nowy punkt jest akceptowany : Xi+1 = Xt. (ii) r < 1 – nowy punkt jest akceptowany z prawdopodobienstwem r, czyli generujemy liczbe losowa % zgodnie z rozkładem jednorodnym w przedziale [0; 1]. Jezeli (a) r > % to Xt jest zaakceptowany : Xi+1 = Xt. 2 Rozdział 18. Algorytmy Monte Carlo (b) inaczej – Xt jest odrzucany : Xi+1 = Xi. Po wyznaczeniu punktu Xi+1 dokonujemy kolejnego próbnego kroku z punktu Xi+1 i generujemy Xi+2, itd. Uwagi: (1) Optymalna wartosc kroku próbnego ± – taka aby około połowy próbnych kroków zostało zaakceptowanych. (2) Punkt startowy X0 Teoretycznie – przypadkowy Praktycznie – dokonujemy pewnej liczby kroków poczatkowych według algorytmu Metropolisa i jako punkt startowy X0 wybieramy ten punkt, dla którego wartosc funkcji w(X0) jest duza (chociaz niekoniecznie najwieksza). Proces ten nazywamy termalizacja. Chyba lepiej się nie da,możliwe że nie zrozumiałem pytania.