Brachistochrone Problem

1년도 더 된것 같다.
뜻하기 않게 Brachistochrone 문제를 풀 기회가 (부탁을 받아서) 생겨서 여기에 정리해 본다.

문제 정의: 한 점에서 massless particle 이 어떤 path 를 따라 중력의 작용에 의해서 움직인다. 이때, 특정 수평방향 위치까지 가장 빨리 가는 path 를 구하여라. (아래 그림 참조)

사용자 삽입 이미지

문제설정: 시간을 최소화 하는 문제임
먼저, 아래와 같이 간단히 좌표설정을 해야 한다.
사용자 삽입 이미지

Solution: Conservation of mechanical energy 에 의해서 다음과 같은 식을 얻을 수 있다.
사용자 삽입 이미지
이 문제는 T 를 최소화 하는 문제이며, Calculus of Variation 의 전통적인 문제중 하나가 된다. 즉, Euler-Lagrange (EL) 방정식을 아래와 같이 풀면 된다.
사용자 삽입 이미지
그런데, Lagrange L 을 잘 살펴보면, x에 independent 함을 알 수 있고, 이 경우에는 Hamiltonian 이 x 에 대해 일정한 값을 갖게 된다. 이를 이용해서 계속 풀어보면 아래와 같다.
사용자 삽입 이미지
여기서 한가지 생각해 볼 것은, y 는 x 의 함수 (y=y(x)) 이고, 다음과 같은 2개의 조건을 만족시켜야 한다. 즉, y(0)=0이고 y(b)’=0 이다. y(0)=0 는 문제 설정상 원점에서 시작하기 때문에 만족시켜야 하며, y(b)’=0 는 calculus of variation 에서 variable end point 문제의 natural boundary condition 에 의해서 반드시 성립되어야 한다. 이를 analytic 하게 풀면 결과는 cycloid 가 된다. 즉,
사용자 삽입 이미지
여기에 위의 두 조건을 대입하면 다음과 같은 path 를 얻게 된다.
사용자 삽입 이미지

그런데, 이것을 수치적으로 풀려면 어떻게 해야 할까? 즉, 우리는y[1+(y’)2]=C 라는 미분방정식 하나만 가지고 있고, solution 이 cycloid 라는 것을 모르는 상황에서 어떻게 수치적으로 그래프를 얻어낼 수 있을까?
먼저, 위의 두가지 조건을 살펴보자. y(0)=0 이되면 위의 미분방정식 y[1+(y’)2]=C 를 만족시킬 수 없다. 왜냐하면 어떤 수에 0을 곱하면 항상 0이 되기 때문이다. 위 방정식을 만족시키기 위한 유일한 방법은 y’ =∞ 이 되면 된다. 그러므로, path 는 origin 에서 무한대의 기울기를 가질거라는 것을 예상할 수 있다 (위의 analytic solution 의 경우와 일치한다). 그리고, y’(b)=0 이므로, C=y(b) 임을 알 수 있다. 그렇다면, 비록 아직까지 path 를 알지는 못하지만, C와 y(b) 를 사용하여서, 수치적 방법으로 문제를 풀때 solution 을 얻어내는 하나의 criterion 으로 사용하자. 즉, 여러가지 C를 사용해서 미분방정식을 수치적으로 풀고, y(b) 와 C 가 가장 가까워지는 경우의 C 를 찾아내면 문제를 푼것으로 갂주할 수 있다.
수치적으로 문제를 풀기위해서 Matlab 의 ODE45 함수를 사용할 것이다. y 의 초기값은 0 임을 알고 있지만, y’ 의 분모에 y 가 들어가 있기 때문에 수치적으로 문제를 풀때는 y=0 을 사용할 수가 없다. 그러므로 eps 를 y의 초기값으로 둔다.
결과 그래프는 아래와 같다. 약갂의 오차가 발생하지만, 비슷한 결과를 얻을 수 있다. 이때 C 는 0.01 부터 0.001 의 갂격으로 2까지 변화시켰다. y(b)-C 의 오차값도 함께 plot 하였다.

사용자 삽입 이미지

사용자 삽입 이미지

수치적으로 찾은 C 는 1.301 이지만, 해석적으로 찾은 C는 4/π=1.2732 이다. C=4/π 를 대입하여 다시 수치적으로 계산한 결과를 보니 그 결과가 거의 정확히 일치하는 것을 알 수 있다. 0.001 의 갂격이 정확한 값을 찾아내기에는 충분히 미세하지 않는 것이었나보다.

사용자 삽입 이미지


사용자 삽입 이미지

mfile
function Brachistochrone()
clear;clc
global c
dif=[];
b=2;
xspan=[0 b];
y0=eps;
cspan=0.01:0.001:2
n=length(cspan);
for i=1:n
c=cspan(i);
[x,y]=ode45(@myfun,xspan,y0);
dif(i)=abs(y(end)-c);
end
[temp ind]=min(dif);
c=cspan(ind);
% c=4/pi;
[x,y]=ode45(@myfun,xspan,y0);
plot(cspan,dif);grid on;
xlabel('c');ylabel('y(b)-c')
figure;plot(x,-y);hold on;grid on;
theta=0:0.01:pi;
x=b/pi*(theta-sin(theta));
y=b/pi*(1-cos(theta));
plot(x,-y,'r')
xlabel('x (m)');ylabel('-y (m)');
title('Brachistochrone path')
legend('numerical','analytic')
function dy=myfun(t,y)
global c
dy=zeros(1);
dy(1)=sqrt(c/y(1)-1);

Posted by Pilwon Hur

2012/08/29 09:03 2012/08/29 09:03
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/64

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

연구를 하다 보면 가끔식 존재하지 않는 실험데이터를 만들어야 할 때가 있다.
예를 들어 손의 Index finger 에 DIP, PIP, MCP Joint Moment 를 예측하는 2개의 모델이 있다고 가정하자.
이 2개의 모델이 적합한지를 알기 위해서, 그리고 어떤 모델이 더 정확한지를 알기위해서 실험을 하기 전에 먼저 Simulation 을 통해서 결과를 미리 예측할 수 있다.
그런데, 시뮬레이션을 하기 위해서는 어떠한 distribution 을 가지는 Hand Length data 가 필요하다. (마치 subject 를 recruitment 하는 것 처럼).
그럼 이 어떤 distribution 을 가지는 Hand Length data 는 어떻게 구할까?
Literature 에 보면 이미 Hand Length 의 mean 과 standard deviation 은 알려져 있다.
그렇다면 mean 과 standard deviation 을 가지고 아래와 같이 normal distribution 의 curve 를 만들 수 있을 것이다.
사용자 삽입 이미지


그런데, 이 normal distribution curve 를 가지고 실제의 Hand Length data 의 sample 은 어떻게 만들어 낼까?
의외로 간단하다.
CDF (Cumulative Distribution Function) 를 사용하는 것이다. CDF 를 사용하는 이유는 CDF 가 one-to-one 이기 때문에 Inverse function 이 존재하기 때문이다.
사용자 삽입 이미지

CDF 의 inverse function 을 구했다면, 원하는 distribution 을 가지는 data sample 을 얻어내는 것은 아주 쉽다. Uniform distribution 을 갖는 random sample 을 사용하면 된다.
사용자 삽입 이미지

Normal distribution 뿐 아니라 어떠한 distribution 도 사용할 수 있다.

아래는 실제로 Matlab 을 사용한 결과이다.
Matlab 의 "norminv" 함수는 Normal distribution 의 CDF 의 Inverse function 의 값을 return 하는 함수이다.

x=rand(1000,1); % 1000 개의 Uniform distribution sample
y=norminv(x,7.41,0.36); % Inverse CDF 를 사용한 Normal distribution 을 갖는 sample data
figure(1);
hist(x,50) % Uniform distribution 의 Histogram (확인용)
figure(2);
hist(y,50) % 위의 방법으로 얻어낸 Normal distribution 의 Histogram (확인용)

사용자 삽입 이미지

사용자 삽입 이미지


참 쉽죠잉? ㅋㅋ

Posted by Pilwon Hur

2011/12/21 02:22 2011/12/21 02:22
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/63

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

시편 50:21-23

네가 이 일을 행하여도 내가 잠잠하였더니 네가 나를 너와 같은 줄로 생각하였도다 그러나 내가 너를 책망하여 네 죄를 네 눈 앞에 낱낱이 드러내리라 하시는도다

하나님을 잊어버린 너희여 이제 이를 생각하라 그렇지 아니하면 내가 너희를 찢으리니 건질 자 없으리라

감사로 제사를 드리는 자가 나를 영화롭게 하나니 그의 행위를 옳게 하는 자에게 내가 하나님의 구원을 보이리라

Posted by Pilwon Hur

2010/10/06 09:10 2010/10/06 09:10
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/62

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

2008년인가 At&t (그때 당시 Cingular) 에서 2년짜리 계약폰인 Sony Ericsson w580i 를 공짜로 받았다.
핸드폰이지만, walkman 과 같은 기능을 하기 때문에 mp3, mp4 혹은 라디오를 많이 듣고 다녔다.
얼마전에 교회의 어떤 집사님이 $15 을 추가로 내고 데이터 무제한 기능을 사용하면서 인터넷을 사용한다고 하셨다.
평소에 아이폰을 사용하면서 이메일이나 간단한 인터넷을 사용하는 친구들을 주위에서 많이 봐왔기 때문에 나도 내 핸드폰으로 인터넷을 사용하는 것에 관심이 가게 되었다.
핸드폰으로 인터넷을 사용하는 용도를 따져보니 이메일, 은행잔고확인, 단어찾기, 뉴스, 날씨, 간단한 구글검색 등이었다.
이메일은 절반이상이 한글로 되어 있고, 뉴스는 대부분 한글이다.
문제는 Sony Ericsson w580i 는 한글을 지원하지 않는다는 것이다.
그래서 내 핸드폰에 한글을 추가하는 방법을 찾아보았고, 결론적으로 성공했다.

USB Flash Driver 를 먼저 설치한다.
CS++ 라는 툴을 다운로드 받은 후 실행한다.
핸드폰의 전원을 끈다.
이때 SIM 카드와 SD 카드는 빼놓는다.
핸드폰의 c 버튼을 누르면서 USB 케이블을 연결한다.
접속에 성공하면 핸드폰의 정보가 CS++ 프로그램의 왼쪽 패널에 보여진다.
오른쪽 패널의 FSX 를 클릭한다.
tga->preset->system->font 에 들어가보면 fonts.xml 과 거기에 사용된 폰트파일인 sans-xxxxxxx.ttf 파일이 들어있다.
인터넷에서 한글폰트를 구한다.
컴퓨터에 내장되어 있는 맑은고딕 폰트의 경우 다른폰트 (굴림 등등) 들보다 훨씬 더 용량이 작지만 그래도 4MB 정도이다. 핸드폰에 기본으로 내장되어 있는 sans-xxxxxxx.ttf 는 250KB 정도밖에 안된다. 그래서 인터넷에서 용량이 작은 한글폰트를 구한다.
fonts.xml 를 한번 열어보면 대충 어떤식으로 되어 있는지 알것이다.
여기서 조심해야 할 것이 있는데, 새로 다운로드 받은 한글폰트의 이름을 sans-xxxxxxx.ttf 로 바꿔야 한다.
난 처음에 이것을 모르고 한글폰트의 이름을 그대로 쓰고, fonts.xml 안의 내용을 한글폰트 이름으로 수정해서 CS++ 를 통해서 업로드 했었는데, 핸드폰이 인식을 못했다.

Posted by Pilwon Hur

2010/06/30 01:36 2010/06/30 01:36
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/61

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

Rubik Cube

1. 첫번째 면의 십자가 모양을 맞춘다. 이때 옆면가지 같이 맞춰야 한다.
십자가 모양을 맞추다가 원하는 색깔이 하나만 빚나가 있을 때는 다음과 같이 한다.
Fi U Li Ui
2. 첫번째 면의 모서리를 맞춘다.
Ri Di R D
3. 뒤집어서 옆면들의 오른쪽 또는 왼쪽을 맞춘다.
왼쪽을 맞추기 위해서는
Ui Li U L U F Ui Fi
오른족을 맞추기 위해서는
U R Ui Ri Ui Fi U F
4. 윗면에 십자가 모양을 맞춘다.
F R U Ri Ui Fi
참고로, 십자가의 왼쪽과 가운데는 고정이고
십자가의 오른쪽은 위로
십자가의 아래쪽의 옆 (앞쪽 면)에 있는 것은 오른쪽으로
십자가의 위쪽 옆 (뒤쪽 면)에 있는 것은 아래로 온다.
5. 윗면 십자가와 옆면의 색깔을 맞춘다.
R U Ri U R U U Ri
이때 윗면과 옆면의 색깔을 하나만 맞춰라. 그런 후에 이 알고리즘을 사용하면 된다.
참고로, 하나만 맞춰진 색깔이 앞면에 있다고 가정하면, 오른쪽은 뒤로, 뒤는 왼쪽으로, 왼쪽은 오른쪽으로 간다. 즉, 반시계 방향으로 움직인다 (앞면은 안움직이고 고정).
6. 모서리 맞춰라.
U R Ui Li U Ri Ui L (몸 반대쪽 두번, 몸 쪽 두번)
오른쪽 아래에 있는 모서리는 바뀌지 않는다. 그리고 나머지 모서리들은 모두 반시계방향으로 움직인다.
그러므로, 맞는 모서리를 오른쪽 아래에 두고 시작해라.
7. 모서리의 orientation 맞춰라
Ri Di R D

Posted by Pilwon Hur

2010/05/13 01:04 2010/05/13 01:04
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/59

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

Game Theory

직접 작성

Game Theory 의 아주 간단한 예를 하나 만들어보았다.

A와 B가 서로 간단한 게임을 한다. A 는 $5 혹은 $20 를 선택할 수 있고, B 는 A 가 선택하는 것을 맞추는 게임이다. 만약 B 가 A 가 선택한 것을 맞추면 그 돈을 갖게 되고, 틀리게 되면 B 는 A 에게 $12 를 줘야 한다. 이것을 Table 로 만들면 다음과 같아진다.
사용자 삽입 이미지
이 Table 을 A 의 Payoff Table 이라고 한다. 즉, 이 규칙에 의해서 A 는 돈을 지급받게 되는 것이다.
그런데, 어떻게 하면 A 혹은 B 가 가장 이득을 보는 게임을 할 수 있을까?
머리속에 떠오르는 몇가지 생각들이 있을 것이다. 예를 들어, A 는 50:50 의 비율로 $5 와 $20 를 선택할 수도 있고, 그에 대해서 B 는 50:50 의 비율로 $5 와 $20 를 예측할 수 있다. 혹은 A 가 약간의 변칙을 줘서 30:70 의 비율로 $5 와 $20 를 선택할 수도 있다. 이러한 것을 전략 (Strategy) 라고 한다. 어떠한 전략을 세울 지라도 A 와 B 의 목표는 단 하나 존재한다. A 의 목표는 최대한 돈을 많이 따는 것이고, B 의 목표는 손실을 최소화 하는 것이다.

전략을 세울 때에는 공격적으로 세울 수도 있고, 방어적으로 세울 수도 있다. 보통 Robust Control 에서 사용하는 전략은 Worst Case 에 대해서도 어느정도의 이득을 얻을 수 있도록 전략을 세운다. 그러므로, 여기서도 Worst Case Scenario 에 대해서 생각을 하고 그것을 최적화하는 방법으로 가는 것이 타당하다.

A 의 Worst Case Scenario: A 가 벌 수 있는 최소한의 돈
B 의 Worst Case Scenario: B 가 잃어버릴 수 있는 최대한의 손실

그렇다면, A 는 자신이 벌 수 있는 최소한의 돈을 극대화 (그 극대화 된 값을 w 라고 하자) 시키려고 노력할 것이고, 그에 해당하는 전략을 세우려고 할 것이다. 왜냐하면, 그러한 전략 (만약 존재한다면) 을 사용하기만 하면, A 는 자신이 벌 수 있는 돈은 아무리 못 벌어도 w 이상은 항상 벌 수 있기 때문이다.

마찬가지로, B 는 자신이 최악의 경우에 볼수 있는 손실을 최소화 (이 최소화 된 값을 w 라고 하자. 여기서 마찬가지로 w 를 사용하는 이유는 최적회된 결과에서는 두 값이 같아지기 때문이다) 하려고 할 것이고, 그에 해당하는 전략을 세우려고 할 것이다. 왜냐하면, 그러한 전략 (만약 존재한다면) 을 사용하기만 하면, B 는 자신이 아무리 돈을 많이 잃는다고 할 지라도 w 보다 더 많이 잃지는 않을 것이 보장되기 때문이다.

그럼, 이제 전략을 어떻게 세워야 하는지에 대해서 살펴보자. A 가 항상 $5 을 선택할 수도 있다. 만약 B 가 이 전략을 알아차리고 $5 을 예측하게 된다면 B 는 $5 을 얻게 되는 것이다. 이렇게 A 처럼 정해져 있는 전략을 사용하는 것을 Pure Strategy 라고 한다. B 처럼 상황에 맞게 바꾸는 전략을 Mixed Strategy 라고 한다. 일반적으로 Mixed Strategy 가 더 좋은 결과를 준다. Mixed Strategy 는 특정한 Event 에 따라 반응하는 것이기도 하지만, 여기서는 조금 더 쉽게 생각해서 Probability Distribution 에 따라서 행동하는 것으로 생각해 보자. 즉, 주어진 Probability Distribution 에 따라서 Random 하게 돈을 선택하는 방법을 고려해 보자.

A 가 돈을 선택하는 Probability Distribution 을 p=[p1 p2]' 라고 하자. 그리고, B 가 돈을 예측하는 Probability Distribution 을 q=[q1 q2]' 라고 하자. 그렇다면 A 와 B 는 각각 자신들의 목표에 의해서 다음과 같은 조건식을 가지게 된다.
사용자 삽입 이미지
사용자 삽입 이미지
여기서 A={aij} 는 위의 Payoff Table 의 값을 말한다.
위의 첫번째 constraint 가 말하는 의미는 다음과 같다. 즉, A 의 minimum gain 은 w 보다는 항상 크다. 두번째 constraint 의 의미는, A 의 maximum loss 는 w 보다 항상 작다.

A 는 w 를 최대화 시키려고 할 것이다. 그래야만 더 많은 돈을 벌 수 있는 것이 보장이 된다.
B 는 w 를 최소화 하려고 할 것이다. 그래야만 손실이 더 적어지는 것이 보장이 된다.

이에 따라 다음과 같이 문제를 set up 할 수 있다.
A 에 대해서는
사용자 삽입 이미지

그리고, B 에 대해서는
사용자 삽입 이미지

와 같다.

그런데, Linear Programming 의 관점에서 봤을 때는 위의 problem setting 이 바람직한 setting 은 아니다. 왜냐하면 w 라는 변수가 objective function 에도 들어가 있고, constraint 의 우변에도 들어가 있기 때문이다. LP의 standard form 으로 나타내기 위해서는 constraint 의 우변은 항상 nonnegative constant 이어야 한다. 그러므로, 약간의 trick 을 사용해 보자. 즉, constraint 을 w 로 나눠주면 constraint 의 우변은 1 이 되므로 문제가 해결된다.
즉, A에 대해서는
사용자 삽입 이미지
그리고, B 에 대해서는
사용자 삽입 이미지

그리고, w, u, v 가 다음과 같은 관계가 있는 것을 확인할 수 있다.
사용자 삽입 이미지
사용자 삽입 이미지

그러므로, Objective function 을 다음과 같이 바꾸어도 문제가 없다.
사용자 삽입 이미지
사용자 삽입 이미지


이제 어느정도 완성이 되었다. 실제로 위의 문제는 아래와 같은 LP 문제가 된다.
A 에 대해서는
사용자 삽입 이미지
그리고, B에 대해서는
사용자 삽입 이미지


그런데, 문제를 조금만 잘 살펴보면 이 2가지 최적화 문제는 서로 Dual 관계에 있는 것을 확인할 수 있다.
즉, 둘 중에 하나만 풀어도 같은 답을 얻을 수 있다.
의미상으로 보면, Optimal 인 경우, A가 최소한으로 받을 수 있는 수익을 최대화 하는 것은 B가 최악의 경우에 발생하는 손실을 최소화 하는 것과 같다.
이것은 Nash Equilibrium 과도 같은 의미이다. 이 상태에서는 A 나 B 가 자신의 전략을 변경하더라도 결코 이득을 얻을 수 없다.



그럼 실제로 이 문제를 풀어보자.
위에서 A matrix 가 음수값을 가지는데, 문제를 쉽게 풀기 위해서 21을 더해서 모두 양수가 되게 만들자. (von Neuman 이 이 문제를 증명할 때 nonnegativity 를 가정했다.)
w=21+w1
그럼, A matrix 는 다음과 같아진다.
사용자 삽입 이미지

LP 문제를 setup 하면 다음과 같아진다.
사용자 삽입 이미지

이 문제를 풀기위해서는 Simplex 방법을 사용하든지 아니면 변수가 2개뿐이므로 그래프를 그려서 풀수도 있다.
이렇게 해서 찾은 u1 과 u2 는 다음과 같다.
u1 = 0.0298229
u2 = 0.0158434
u1 + u2 = 1/w = 0.0456664
w = 21.8979381

p1 = u1 * w = 0.653060018
p2 = u2 * w = 0.346937792

w1 = w - 21 = 0.8979381


마찬가지 방법으로 v1 과 v2 도 풀어보면 u1 과 u2 와 같은 결과가 나온다. (물론 이것은 A matrix 가 symmetric 이기 때문에 발생한 결과이고, 두 경우 모두 w 는 같아야 한다.)
여기서 보면 w1 값이 0보다 크므로 A 가 유리한 게임이다.
즉 A 가 65:35 의 비율로 $5 과 $20 을 선택을 하면 A 는 매 게임마다 최소한 $0.898 을 따는 것이다. 여기서 최소한 이라는 말을 사용했다. 즉, 이것보다 더 많이 딸수도 있다는 뜻이다. 그것은 B 의 전략에 달려있다. B 도 마찬가지로 65:35 의 비율 (이 비율은 v1, v2 에서 가져온 것이다) 로 예측을 한다면 B 는 매 게임마다 $0.898 만 잃을 것이다. 만약 다른 전략 (예를 들어 50:50 나 90:10 등) 을 사용하면 B 는 더 많은 돈을 평균적으로 잃게 될 것이고, 그만큼 A 는 더 많은 돈을 따게 되는 것이다.

다음은 이것을 실제로 Simulation 해 볼 것이다.
Monte Carlo 방법을 사용할 것인데, 그것은 다음 글에서 하도록 한다.

Posted by Pilwon Hur

2010/05/12 23:46 2010/05/12 23:46
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/58

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

실해석학을 공부하는 우리들의 자세



절대.....완전 공감하는 글....
이글을 읽으면서 왜 이렇게 위로가 되는지.........

======================================================================

analysis.jpg

(해석학과는 관계없지만...언젠가 수업시간에 교수님이 보여주신 그림. 절대 동감.)


1. 생각을 비워라

여태껏 갖고 있던 생각을 모두 내려놓아야 한다.

우리가 기존에 갖고 있던 수 체계에 대한 생각과 수의 연산 및 극한에 관한 모든 개념은 실해석학의 세계로 들어오는 순간 내려놓아야 한다.

그래야 실해석학이 내려주는 수많은 지식들을 습득할 수 있다.


2. 절대 의문점을 제기하지 말라.

왜  ε 값을 상황에 따라 쓸데없이 다르게 주냐는 등의 의문점 따위는 시작부터 접는 것이 좋다. 실해석학의 절대성 앞에서는 아무런 의문이 필요없다. 그저 순종하고 외우는 수 밖에는 없는 것이다.


3. 사소한 것 하나도 그냥 지나쳐서는 안된다.

실수의 대소 관계는 딱 세가지다. a>b,a=b,a<b

아, 너무 당연하지 않는가? 그러나 이런거 절대 지나쳐서는 안된다.

이게 그 유명한 trichotomy law

이걸 지나치는 순간, 당신의 고득점은 홀랑 하늘로 날아가버린다.

a+(-a)=0 이 된다는 것은 초등학생도 알고 당신의 노모와 조모도 아실 것이다.

당신도 물론 알고 있다. 그러나 그런 당연한 것들은 실해석학의 기초

쪼잔해지더라도 꼭 집고 넘어가야한다.


4. 암기의 달인이 되어야 한다.

증명하면서 그것을 이해하려 하지 말라. 이해하려다가는 낭패보기 십상

이해는 금물, 오로지 실해석학의 세계에서는 암기가 중요하다.

증명을 이해하다가 증명 하나 가지고 한 달 넘게 갈 수도 있다.

그러면 당신의 학점은 날아갈 것이다.

우선 외워라. 이해는 언젠가 될 것이다.

그 날이 안올지도 모르지만 증명과 공리는 무조건 모조리 외워라.




이상은 수학을 먼저 공부한 선배들이 전해준 말......

타고난 천재도 버벅대는  ε, δ 앞에서 범재들은 잠잠할지어다.


증명을 이해하려했던 내가 바보였다.

외워라. 그것만이 살길!


Posted by Pilwon Hur

2009/02/26 05:07 2009/02/26 05:07
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/57

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

Double pendulum

이번 학기 TAM212 (Introduction to Dynamics) TA 를 하면서 나름대로 재미있는 시간을 보내었다. 학생들은 학생들대로 필요한 내용들을 나에게서 부터 배웠고, 나도 학생들과 대화하면서 재미있는 시간들을 보내었다. 이제까지 수많은 과외들을 해 왔지만, 실제로 매주 3시간씩 학생들 앞에서 강의 및 토론을 한다는 것은 새로운 경험이었고, 나 또한 학생들로 부터 무언가를 배울 수 있는 시간이었다. 평상시에는 수업시간에 그렇게 큰 준비를 하지 않고 들어간다. 그만큼 수업 내용이 나에게 편하다고나 할까. 그런데, 이제 다음 주이면 기말고사 전이기 때문에 내가 가지는 거의 마지막 또는 2주 정도 되는 것 같다. 그래서 평소에는 하지 않던, 수업시간에 학생들에게 무엇을 가르칠까를 생각해 보았다. "학생들이 이 수업을 듣고 나서 기억에 남는 것은 무엇일까?" 아마도 지금까지라면 "짜증나는 수업", "시험과 숙제가 너무 어려웠던 수업", "이번 학기에 듣는 다른 모든 수업들 다 합쳐도 이 과목보다는 쉬울거야…", "뭔가 힘들긴 했는데, 학기가 끝나고 나니까 뭘 했는지 기억이 나지 않는 수업?" 등등….


뭔가를 보여줘야 겠다는 생각이 들었다. 단순히 숙제문제에서 벗어나서 여기서 배운 것들로 무엇을 할 수 있는지 보여줘야겠다는 생각이 들었다. 일상생활에서 볼 수 있는거나 쉽게 이해할 만한 시스템이 있을까 생각을 해 보았다. 순간, 떠오른 예가 double pendulum 이었다 (한국말로 하면 복진자 인가? 어감이 약간 이상함..ㅋㅋ). Double pendulum 의 움직임은 단순해 보이지만, 사실은 그 움직임 자체가 Chaos 를 가지고 있다. 아래의 그림을 보자. 가운데에 pin joint 가 있고, 파란색 막대기가 수평으로 누워 있다. 이 막대기는 그림상으로는 하나의 막대기로 보이지만, 사실은 2개의 막대기가 서로 나란히 누워 있고, 그 끝이 pin joint로 연결되어서, 마치 하나인 것 처럼 보일 뿐이다. 현재 중력이 아래 방향으로 작용하고 있다면, 이 2개의 막대기의 운동은 어떻게 될까?


그 결과는 저 아래에서 확인하도록 하고, 글을 계속 진행해 나가도록 하자.


운동방정식을 새우는 과정 자체는 아주 단순하다. Newton 법칙과 Euler 법칙을 각각의 rigid body 에 적용시켜서 운동방정식을 유도해 내면 된다. 아래는 Free body diagram 을 나타낸 것이다.





6개의 운동방정식과 4개의 kinematic equation 을 얻어낼 수 있고, 모르는 변수가 총 10개 이므로 이 방정식을 analytical 하게 풀어 낼 수 있다. 그 결과는 어떨까? Mathematica 로 풀어보면, 거의 A4 용지 3페이지에 달하는 solution 을 얻어낼 수 있다. 다시한번 FullSimplify 라는 명령어로 10분 이상 단순화 작업을 하더라도 A4 용지 1페이지 분량의 Solution 을 아래와 같이 얻게 된다. 일단, 시작부터 심상치 않은 듯 하다. 단순한 막대기 2개의 움직임이 이렇게 복잡한 운동방정식을 가질지 예상을 못했을 것이며, 또한 식 자체도 아주 심하게 highly nonlinear 이다. 별로 좋은 상황은 아닌듯 하다.



복잡하기는 하지만, 그래도 내가 힘든 것은 아니다. 계산은 컴퓨터가 해 주니까. 그럼 그 다음 단계는 무엇인가? 이제 Simulation 을 해야 한다. 적절한 시간 간격을 주고, 그 시간동안 double pendulum 의 움직임이 어떻게 될 것인가를 실제 실험을 거치지 않고 컴퓨터로 미리 알아보는 것이다 (너무 쉬운 내용을 쓰나? 아무튼, 이 글의 초첨은 학부 2,3,4 학년 이니까 뭐…..패스…). 이것은 Analytical 하게 찾아내기가 거의 불가능 하다. 앞의 과정에서 얻어낸 운동방정식은 사실 미분방정식이다. 만약 이 미분방정식이 단순히 Linear 이고, 변수들이 uncouple 되어 있다면, analytical 하게 풀어볼 시도라도 한번 해 볼 수 있지만, 위에서 보듯이, 운동방정식은 highly coupled nonlinear 이다. 그러므로, analytical 하게 푸는 것은 일찌감치 포기하고, numerical 하게 푸는 것이 정신 건강상 좋다.


그럼, 이제 위의 운동방정식을 1st order state equation 형태로 바꾸자. 일반적으로 다음과 같다.

 
사용자 삽입 이미지

(1)


이 예제의 경우 4개의 state 가 존재한다. 즉, 이다. 그리고, 입력 로 사용되었다.

위 운동방정식을 1st order state equation 형태로 바꾸면 다음과 같다.

 

(2)



여기서 는 위의 운동방정식에 나와 있다 (엄청 복잡해서 타이핑할 엄두가 안남). 이렇게, 시스템이 1st order state equation 으로 나타나면, 이제 Simulation 은 아주 쉽다. Matlab 의 ode45 (사실, Mathematica 에서는 어떻게 하는지 잘 모름) 를 사용하면 된다. 내가 원하는 time interval 에 내가 관심있는 initial condition 을 주면 된다. Double pendulum 이 수평으로 높여 있고, 초기 속도는 모두 0 이라고 가정할 경우, 즉 pendulum 을 수평 상태에서 가만히 놓았을 경우의 Simulation 결과를 아래에 나타내었다. Animation 은 Flash 를 사용하였다.

Get Adobe Flash player

이걸로, double pendulum 이라는 놈의 자연현상을 비슷하게 재현해 보았다. 그런데, 사실 이것에서 그치면 별로 큰 의미가 없다. 그냥 "아~ 그렇구나…그래서 어쩌라고?" 라는 반응이 아주 자연스럽게 나올 것이다. 한단계 더 나아가서 생각해 보자. 한단계 더 나아간다고 해도, 사실 그것들은 우리가 일상생활에서 아무런 생각없이 하는 행동 중 하나에 지나지 않을 수도 있다. 예를 들어, 아래의 동영상을 보면, 무슨 말을 하는지 이해할 것이다. 어릴 때 우산 같은 긴 물건들을 손으로 균형잡던 경험들이 대부분 있을테니까.

즉, 이제부터 이야기 할 것은 control 이다. Control 이란 무엇일까? 이렇게 질문해 놓고도, 한마디로 대답하기 힘들다는 것을 잘 안다. 하지만, 대략적으로, 대부분의 사람들이 고개를 끄덕일 수 있을 정도의, "뭐 그것도 말은 되는군" 정도의 설명을 하자면 다음과 같다. 한마디로, 어떤 물체를 내가 원하는 용도로 쓰기 위함이다. 물론, 그렇게 하기 위해서는 그 어떤 물체에 대한 현상 (Dynamics) 을 잘 이해하고, 어떻게 그 물체를 조작 (Control) 하면 내가 원하는 행동을 하게 할 수 있는지를 알고 있어야 한다. 잠깐 다른 소리 하나 하면, 여기서 이야기 했듯이 Control 의 목적은 내가 원하는 뭔가를 하기 위함 즉, 실제적으로 그 물체를 어디엔가 써먹기 (application) 위함이다. 근데, Control 을 잘 하기 위해서 너무나 깊은 수학적 배경이 필요하고, Application 보다는 Theory 쪽으로 가는 것 같다. 물론, Control 을 조금 더 잘 하기 위한 노력인 것은 알겠지만, 약간은 주객이 전도된 듯 하다.


그럼, 이제 본론으로 들어가서, 실제적으로 Double pendulum 을 Control 해 보자. 우리의 목적은 앞에서 본 동영상과 같이, 두개의 pendulum 을 수직으로 세우는 것이다. 물론 동영상에서 나오는 것은 single pendulum 이고, double pendulum 보다는 훨씬 더 간단하다. 그렇다면 어떻게 하면 이렇게 복잡한 double pendulum 을 수직으로 세울 수 있을까? 일단 우리에게 주어진 입력, 즉 우리가 control 할 수 있는 것은 천장에 붙어있는 pin joint에 연결된 모터 하나 이다. 두개의 pendulum 사이에 연결된 pin joint 에는 모터가 없다.


어떤 controller 를 사용하는 것이 좋을까? 어떤 상황이든, Linear Control 을 사용하는 것이 가장 좋다. 왜냐하면 linear control 은 이미 거의 완벽한 수준으로 이론이 정립되어 있고, 웬만한 수준에서는 거의 대부분 이해하고 있다고 생각하기 때문이다. 하지만, 앞에서도 보았지만, double pendulum 은 너무도 심하게 nonlinear 이다. 그래서 Linear control 을 사용하기 힘들것 같다. 하지만, 그렇다 하더라도 Linear control 의 장점을 쉽게 버리지는 못한다. 그래서, 보통은 equilibrium point 주변에 대해서는 linear control 을 사용한다. 왜냐하면 equilibrium point 주변에서의 아주 미세한 움직임에 대해서는 어떠한 nonlinear system 이라 할지라도 locally linear system 으로 움직이기 때문이다 (Taylor approximation 을 생각해 보면 된다). 그럼, equilibrium point 주변에서는 linear control 을 쓰기로 하자. 당연히 필요한 것은 equilibrium point 에 대해서 double pendulum 을 Linearization 하는 것이다. 이것은 조금 뒤에 이야기 하도록 하자.


그럼, equilibrium point 주변이 아닌 곳에서는 어떻게 할까? 예를 들어 아래 그림과 같이 pendulum 이 초기 상태로 놓여있다면, linear control 은 사용할 수가 없다.



아래에 있는 pendulum 을 수직위치까지 갖다 놓는 mechanism 이 필요하다. 이것을 보통 swing-up control 이라고 한다. 간단하게 search 를 해보니까 몇몇 swing-up control 방법들이 이미 논문으로 나와 있는 것 같다. 여기서는 내가 사용하기 편하고 이미 잘 알고 있는 optimal control 을 사용할 것이다. 물론, 오랜만에 간단하게 optical control 내용을 정리하려는 의미도 있다.


아무튼, 대략적인 control skim 은 다음과 같다. Optimal control 을 사용해서 아래로 처져있는 pendulum 을 equilibrium point 근처까지 올려놓는다. 그 다음, linear control 로 전환하여서 stability 를 보장받을 수 있다. 또한, 이렇게 하는 다른 이유중에 하나는, optimal control 은 open loop control 이고, linear control 은 보통 feedback control 이기 때문이다.


그럼, 먼저 optimal control 부터 design 해 보자. 일반적인 setting 을 보자.

일반적으로 nonlinear 이고, 쉽게 하기 위해서 time invariant system 이라고 가정하자. 그러면, System 은 아래와 같이 주어진다.

 

(3)


내가 원하는 control 은 다음을 성립하는 것이다.

 

(4)


여기서 는 final state 값에 대한 penalty 를 줘서 최종적으로 state 가 내가 원하는 state (여기서는 equilibrium point) 로 최대한 가까이 가도록 하는 것이다. 는 시작부터 끝날 때 까지 state 와 control effort (또는 입력, 전기비용, 모터의 파워 등등) 를 penalty 로 준 것이다. 여기서 를 잘 정해주면 state 값과 control effort 를 적절하게 사용하면서 원하는 결과를 얻을 수 있다.


여기까지, optimal control 의 일반적인 이야기를 했고, 위의 optimal control 을 어떻게 푸는가는 또 다른 이야기이다. 다르다기 보다는, 위의 조건을 만족시키기 위한 의 necessary condition 을 유도해 내는 것이 상당히 복잡하고, 약간의 수학적 지식이 필요하므로, 여기서는 생략하겠다는 뜻이다. 참고로, 위 식에서의 optimization 은 단순한 몇몇의 constant parameter 를 찾는 것이 아니라, 일정한 시간 동안 내가 원하는 performance 를 낼 수 있는 control 의 sequence, 즉 function 을 찾는 것이다. 다른 말로 하면 Functional space 를 다루게 된다.


그럼, 는 어떻게 찾을까? 이제부터는 조금 더 세부적인 내용이므로, 잘 모르겠으면, "그렇구나" 하고 넘어가는 것이 더 좋을 듯 하다. 아무튼, 를 찾기 위해서는 먼저 Hamiltonian,을 먼저 정의해야 한다. 는 다음과 같이 정의한다.

 

(5)



여기서 는 Lagrange multiplier 이다. 왜냐하면 system dynamics 인 가 하나의 equality constraint 로 취급되기 때문이다. 역시 여기서 주의하여 볼 것은 보통의 optimization 과는 다르게, Lagrange multiplier 가 constant 가 아니라 시간의 함수라는 점이다. 눈치빠른 사람은 에 포함이 안되어 있는 것을 느꼈을 것이다. 는 boundary condition 으로 사용될 것이므로, 조금 뒤에 나온다.


그렇다면, 로 되기 위한 necessary condition 은 무엇인가? 유도과정은 앞에서 설명했듯이 생략하도록 하고 결과만 보면 다음과 같다.

 

(6)

(7)

(8)



이다. 위 3가지 조건은 항상 성립되어야 하고, boundary condition 의 종류에 따라 아래의 조건을 성립해야 한다.

 

(9)


이 결과를 우리 예제에 적용해 보자. 우리의 final state 는 이미 정해져 있다. 이다. 하지만, final time 는 정해져 있지 않다. 그러므로, Eq (9) 에서 이고, 는 모든 임의의 숫자이므로, boundary condition 은 아래와 같아진다.

 

(10)


이제, 우리의 가 무엇인지만 알면 문제는 어느정도 풀릴 것 같다. 는 설계자의 고유권한이므로, 특별한 지침이 없다면 내 마음대로 정해도 된다. 물론, 그 설계자의 insight 에 따라서 성능이 달라지겠지만. 이번 예에서는 다음과 같이 정했다.

 

(11)


(12)


Eq (11) 에서 보듯이 가 시간의 함수가 아니므로 Eq (10) 은 아래와 같이 간단해 진다.

 

(13)


한가지 더 추가하면, Eq (3) 과 Eq (12) 에서 Hamiltonian 가 시간의 함수가 아니고, final time 이 정해져 있지 않으므로, Pontryagin 의 증명에 의해서

 

,

(14)


이다.


수식이 너무 많이 나오니까 무슨 소리 하는지 잘 모를 수도 있을것 같다. 더 간단히 설명하려니까 내 머리가 아프고, 그래서 그냥 계속 진행하는 것이 좋을 듯 하다. 그러면, 위의 식들을 어떻게 써먹어야 하나?


일단, Algebraic equation 인 Eq (8) 을 성립시키는 를 찾는다. 그리고 이것을 Differential equation 인 Eq (6), Eq (7) 에 대입한다. 이렇게 대입한 후에 얻은 Differential equation 을 Reduced Differential Equation (RDE, 주의…Riccati DE 아님…) 라고 하자. 그러면 unknown 의 갯수는 가 n 개 이고, 가 n개, 그리고 final time 1 개를 합쳐서 총 2n+1 개가 된다. 그리고, RDE 가 모두 2n 개이고, boundary condition 1 개가 있으므로 RDE 를 풀 수 있을 것 같아 보인다. 의 initial condition 은 라고 하자. [하지만, 의 initial condition 을 알지 못하므로, 사실상 풀 수가 없다. 그렇다고 가만히 있을 수는 없지. RDE 와 Eq (13) 을 성립시키고, 를 만족시키는 의 initial condition 과 를 찾아주는 optimization 을 한번 더 해주면 된다.


그렇게 해서 나온 의 initial condition 과 를 Matlab 의 ode45에 대입하고, 다시 RDE 를 풀면 를 시간의 함수 (sequence) 로 얻어낼 수 있다. 이렇게 얻은 를 Eq (8) 에서 얻은 에 대입하면 를 얻을 수 있다. 이제 를 얻었으므로 이것과 을 Matlab 의 ode45 에 대입하여 Eq (3) 을 풀면 가 equilibrium point 에 근접하게 된다. 이제 남은 것은 control 을 linear control 로 바꾼 뒤에 stabilize 시키면 된다.


이제 Linear controller 를 설계해 보자. 먼저, 저 위에 있는 nonlinear 운동방정식을 equilibrium point 근처에서 linearization 해야 한다. Linearization 결과로 Eq (3) 은 아래와 같은 식으로 변형된다.

 

, where

and

(15)




Linear controller 에서 사용할 는 LQR 을 사용하여 구하도록 하자.

 

(16)


Riccati equation 을 풀어주는 K 를 찾아주면 되며, Matlab 의 lqr 이라는 함수를 쓰면 자동으로 찾아준다. 그 결과 는 다음과 같은 형태를 갖는다.

 

(16)


결과적으로, state feedback 이 된다.


이제, 다 된것 같다. Linear controller 로 변환되는 시점을 조금 넉넉하게 잡아서 로 두었다.


아래는 그 결과를 Animation 으로 보여준 것이다.
첫번째 두개는 Optimal control 과 linear control 을 함께 사용한 결과이고, 마지막 것은 단순히 Linear control 만 사용한 것이다.

Get Adobe Flash player

얼핏 보기에는 마지막 번째의 control 이 좋아보인다. 마지막 것은 linear control 만 사용한 것이므로, 사실상 말이 안되는 control 이다. 왜냐하면 swing-up phase 에서는 Linearized system 이 double pendulum 을 제대로 나타낼 수 없으며, 그 결과는 사실상 틀린 것이기 때문이다. 또한, Linear control 은 오차가 크면 큰 만큼 더 큰 command input 을 주기 때문에 엄청나게 큰 입력을 모터에 주게 된다. 그 결과 pendulum 이 갑자기 위로 올라가게 되고, 우연히 equilibrium point 에 가까이 가게 되어서 control 이 되는 것이다. 그리고, linear control 이 만들어내는 출력은 현실적으로 불가능한, 즉 모터가 감당할 수 없는 출력이기 때문에, linear control 만 사용하는 것은 적절치 않다.
첫번째나 두번째와 같이 swing-up phase 에서 optimal control 이나 다른 nonlinear control 사용해야만 모터가 감당할 수 있는 출력을 만들 수 있으며, 첫번째와 같이 한번 정도 흔들어 주는 control  입력이 가능하게 된다.

Posted by Pilwon Hur

2008/11/27 11:51 2008/11/27 11:51
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/56

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

http://www.math.uaa.alaska.edu/~afkjm/techteach/?q=node/52
에서 퍼 옴...



Pen Attention - highlights your pen cursor for giving presentations

04/18/2008 - 00:26
Etc/GMT

Update 5/10/08:An updated version of this program is available that fixes the bugs described in this post.

I've been using my Tablet PC to deliver lectures for years, and I love having the ability to record lectures, mark-up PowerPoint, and write by hand using OneNote. However, it's always bothered me that the pen cursor is a tiny little dot. An example is shown below from OneNote:

In that image, the cursor is right below the number "2" but it's REALLY hard for my class to see on a projector since it's a teensie weensy dot. The problem is that I like to use the pen to "point" at things as I give the lecture, but it doesn't help if the class can't see it. To remedy this, I've been using the eraser mode of the pen while in hover mode to "point" at things I want to talk about. It works, but is a little klunky.

After lots of searching around for ways to change the pen cursor to no avail, I finally (after 5 years!) got the idea to make my own program to highlight the cursor. A few afternoons of hacking later, and the result is PenAttention v1.0. This program draws a circle highlight, pencil, or pointer at the location of the pen, when the pen is detected on the screen:

The class can easily see the location of the pen. One drawback of this mode is that it's a little more distracting to write, but doesn't seem too bad so far and I think I'll get used to it. Using the pencil or pointer mode is a bit less distracting:

The program itself installs into the system tray. Tapping on the icon or clicking on it with the pen brings up a context menu that lets you pick which type of pointer you want for the pen:

The program is free and requires .NET 2.0 or higher and Windows XP Tablet or Windows Vista with a tablet pen. So far I've only tested it on machines with Wacom pens. I've tested this on about four personal machines and it seems to work, but please send me feedback if you have problems or if there are improvements that you would like to see.

To download the installer for this program click the link below:
PenAttention-v1.01-setup.exe

IMPORTANT: If the program installs but the highlight doesn't follow your pen, try installing this Microsoft redistributable update for C++:
http://www.microsoft.com/downloads/details.aspx?familyid=200B2FD9-AE1A-4...

If you are interested in the C++ and C# source code, see below:
PenAttention-v1.01-src.zip

UPDATE 4/21/08: I updated the program to version 1.01. It fixes a bug in Vista when in Internet Explorer where the cursor isn't visible unless UAC or Protected Mode is disabled, and fixes a bug that prevented the cursor from being displayed in XP Tablet.

Posted by Pilwon Hur

2008/11/14 11:34 2008/11/14 11:34
Response
0 Trackbacks , 0 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/54

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

카오스를 이용해서 간단하게 난수(random number) 생성하기

직접 작성

난수(random number) 는 일상의 보이지 않는 곳에서 의외로 많이 쓰이고 있다. 예를 들어 플래시 게임에서 배경으로 자주 등장하는 흩날리는 눈(snow)이나 윌리를 찾아라 에서 처럼 군중들의 움직임을 나타내기 위해서 난수를 사용하기도 한다. 어떤 컨트롤 모델에서 외부에서 작용하는 외란을 시뮬레이션 상으로 구현하기 위해서 난수를 사용하기도 하며, 은행에서 보안카드에 입력하기 위한 카드의 순번을 난수로 생성기도 한다. 아무튼 난수는 여기 저기서 많이 사용하며, 난수를 생성하는 방법도 여러가지이다.

여기서는 정말 간단하게 난수를 생성하는 방법을 말하고자 한다. 결론부터 이야기 하면 카오스(Chaos) 를 이용하는 것이다. 카오스는 보통 다음과 같이 2가지로 특징 지어진다.

  1. Sensitive dependence on initial condition

  2. Trajectory is dense

먼저 Sensitive dependence on initial condition 란, 모든 카오스 시스템은 초기값(initial condition) 에 아주 민감하게 반응한다는 의미이다. 초기값이 아주 조금만 바뀌어도 그 결과에 따른 time series 값은 아주 달라진다. 예전에 한창 유행했던 나비효과라는 것도 이런 이유와 관련이 있다. 두번째로, Trajectory is dense 란 궤적(Trajectory) 이 모든 state 를 다 방문한다는 의미이다. 물론, 여기서 중복은 하나도 되지 않는다. 중복이 일어나게 되면 그 시스템은 카오스가 아니라 주기 운동(periodic motion) 을 하게 된다. 중복이 하나도 일어나지 않는다는 말 자체가 이상하게 느껴질 뿐 아니라 컴퓨터를 통해서 시뮬레이션 (10만번 이상 iteration)을 하면 중복이 일어나는 것 처럼 보이는 이유는 해상도(resolution) 가 낮고, 정밀도(precision) 의 제한이 있기 때문이다.

결국 이 두가지 성질을 이용하면 난수를 생성할 수 있을 거라는 것은 어려운 생각이 아니다. 그렇다면 어떠한 카오스 시스템을 이용할까? 가장 쉬운 경우는 Logistic map 이다.

(1)


아래의 Bifurcation diagram 을 살펴보면

r 이 4가 될때 Xn 은 [0 1] 의 범위에서 완벽한 카오스가 된다.

그러므로 적당한 초기값 X0 를 주고 Eq. (1) 에 recursive 하게 대입을 하면 거기서 나오는 Xn 값이 난수가 된다. 초기값으로는 보통 현재의 시간값을 seed로 주게 된다.

물론 이렇게 구한 난수는 약간 문제가 있다. Perron-Frobenius operator 에 의해서 distribution 의 변화를 보면 invariant distribution 을 구할 수 있다. 초기 distribution 을 uniform distribution 이라고 가정하면 Logistic map 에 의해서 매 iteration 마다 변화되는 distribution 은 궁극적으로 다음의 invariant distribution 으로 바뀐다.

이고, 여기서

는 invariant distribution 이고, P 는 Perron-Frobenius operator 이다. 이제, 앞에서 말한 문제점이란 바로 f*(x) 가 uniform distribution 이 아니라 U 자 모양의 distribution 이라는 점이다. 그러므로, [0 1] 사이의 숫자들이 모두 골고루 나오는 것이 아니라 양 극단으로 갈수록 더 많은 확률로 숫자들이 나온다는 것이다. 이것은 그렇게 좋은 난수 발생기는 되지 못한다. 하지만, 이러한 방법으로 난수를 발생할 수 있다는 것을 설명한 것에 의의를 둔다.

지금 Espresso Royale 에 앉아 있다.ㅋㅋ

Posted by Pilwon Hur

2008/10/12 15:10 2008/10/12 15:10
Response
0 Trackbacks , 1 Comments
RSS :
http://pilwonhur.net/tc/pilwonhur/rss/response/53

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

« Previous : 1 : 2 : 3 : 4 : 5 : ... 6 : Next »