It's just like pok

1. 방정식의 근 : 대수적 방법과 Iterative Method

방정식(Equation) 으로부터 근을 구할때 '근의 공식'등이 존재하는 경우 일반해가 있다고 하는데, 이러한 해를 대수적 해라고 한다. 만일 대수적인 해가 존재할 경우 근을 구하는 방식은 매우 쉽다. - 단지 공식에 넣으면 된다!

Iterative Method는 근을 구하는 또 다른 방법이다. 이 방법은 근에 근접하는 값을 만들어내는 알고리듬이 있고 이 알고리듬을 반복하여 근과의 차이 (tolerrence 혹은 error)가 얼마 이하가 되면 반복을 멈추어 근을 구하는 방법이다. 유명한 Iterative Method 중에는 Newton-Raphson 방법이 있고 Gauss-Seidel Method의 모티브가 되는 Simple Fixed-point Iteration Method가 있다.


2. Simple Fixed-point Iteration Method

Simple Fixed-point Iteration Method는 개념이 사실 단순하다.

f(x) = 0

이라는 방정식의 근을 구한다고 하자. 위의 방정식 양변에 x를 더하여 f(x) + x = x 라는 새로운 식을 만들고 g(x) = f(x) + x 라고 하면 우리가 구하는 식은

g(x) = x

라는 식의 방정식이고 이것은 그래프적으로

y = g(x)라는 그래프와 y = x 라는 그래프의 교점

임을 알수 있다.


위 그림에서 f(x) = sqrt(x) - x = 0 을 구하는게 원래 목적이었다면 g(x) = sqrt(x)라고 하고 g(x) = x의 해를 구하는것과 f(x) = 0 의 해를 구하는게 같음을 알 수 있다.

이제부터가 이 방법의 재미난 점인데, 그림과 같이 x(i+1) = g( x(i) ) 라고 하고 i를 증가하면 x(i+1)이 y=g(x)와 y=x의 교점에 다가감을 알수 있다. 그리하여 x의 sequence가 Cauchy Criterion을 만족하면 (즉 어떤 i 가 있어서 |x(i+1) - x(i)| < tolerance) 그때의 x(i+1)를 해라고 할수 있게 된다.

위 내용을 Octave(matlab) 코드로 짜보면 다음과 같다.

(Language : perl)

g = inline( 'sqrt(x)', 'x' );
tol = 1.0e-7;

i = 1;
x(i) = 0.2;
while true
    x(i+1) = g( x(i) );
    if( abs(x(i+1) - x(i)) < tol )
        break;
    end
    i = i + 1;
end
i, x(i+1)

그러면, 24번만에 해를 도출해 낸걸 알수 있다
(i=24, ans=1.0000 뭐 이런 비슷한 값을 출력한다.)

물론 항상 해에 접근하는것은 아니고 '수렴조건'이 있는데, 그것은 |g'(x)| < 1 이다.


3. Gauss-Seidel Method

Gauss-Seidel Method는 Simple Fixed-point 방법과 매우 유사하다. 다른 점은 방정식이

1. multicomponent 인 경우
2. linear system 인 경우

인데, 간단히 말하면 '연립 일차방정식'의 경우에 해를 '반복적'으로 구하는 방법이다.

Applied Numerical Methods with MATLAB 이라는 책에 있는 예제인

3x - 0.1y - 0.2z = 7.85
0.1x - 7y - 0.3z = -19.3
0.3x - 0.2y + 10z = 71.4

의 해를 Gauss-Seidel Method로 구하는 matlab 코드를 보면,

(Language : perl)

% from 3x - 0.1y - 0.2z = 7.85
% x = (7.85 + 0.1y + 0.2z)/3
f = inline('(7.85 + 0.1*y + 0.2*z)/3', 'y', 'z');

% from 0.1x - 7y - 0.3z = -19.3
% y = (-19.3 - 0.1x + 0.3z)/7
g = inline('(-19.3 - 0.1*x + 0.3*z)/7', 'x', 'z');

% from 0.3x - 0.2y + 10z = 71.4
% z = (71.4 - 0.3x + 0.2y)/10
h = inline('(71.4 - 0.3*x + 0.2*y)/10', 'x', 'y');

i = 1;
tol = 1.0e-7;
x(i)=0; y(i)=0; z(i)=0;
while true
    x(i+1) = f( y(i), z(i) );
    y(i+1) = g( x(i+1), z(i) );
    z(i+1) = h( x(i+1), y(i+1) );

    if( abs(max( [x(i+1)-x(i) y(i+1)-y(i) z(i+1)-z(i)] )) < tol )
        break;
    end
    i = i + 1;
end
i, x=x(i+1), y=y(i+1), z=z(i+1)

만일

x(i+1) = f( y(i), z(i) );
y(i+1) = g( x(i+1), z(i) );
z(i+1) = h( x(i+1), y(i+1) );

부분이

x(i+1) = f( y(i), z(i) );
y(i+1) = g( x(i), z(i) );
z(i+1) = h( x(i), y(i) );

가 되면, 즉 현재 루프에서 적용된것값을 적용되자마자 써먹는게 아니고 루프를 다 돌고 사용한다면, 그 방법을
Jacobi iterative method 라고 한다.

Simple fixed-point iterative method처럼 Gauss-Seidel도 수렴조건이 있는데, 연립일차 방정식을 matrix로 나타냈을때 그 matrix가 'diagonal dominant' 하면 된다.

수학 이야기 Octave, 수학

Octave(이하 옥타브)는 Matlab에 대응하는 오픈소스 프로그램이다.

최근 학교에서 Matlab을 이용한 수치해석이나 확률과정 개론을 배운다.
그런데 Matlab은 고가의 소프트웨어라서 집에서는 오픈소스 프로그램인 옥타브를 사용한다.

이 글은 3.2 버전에 맞춰 작성되었다.
옥타브 3.0버전에서 고민하던 문제들이 3.2버전에서 단박에 풀려서 3.2버전을 사용하기를 강력히 추천한다.

먼저 옥타브는 커맨드라인 프로그램이다. 그래서 옥타브가 아쉽다기보다는 윈도용 커맨드라인 환경이 아쉬운 경우가 종종있다. 가장 아쉬웠던것은 글꼴이었고, 옥타브 3.0버전에서는 '삐'거리던 스피커음도 불만이었다.

먼저 커맨드라인 글꼴바꾸기
http://smallvoid.com/article/winnt-cmd-add-font.html

내경우에는 HKEY_LOCAL_MACHINE \SOFTWARE \Microsoft \Windows NT \CurrentVersion \Console \TrueTypeFont 에서 나눔코딩고딕을 콘솔 폰트로 설정해서 사용하고 있다.



그리고 커맨드라인에서 PC스피커 (bell service) 끄는 방법.
http://superuser.com/questions/10575/turning-off-the-cmd-window-beep-sound
커맨드라인에서 벨을 끄는 방법은 여러가지 있는데 내가 사용했던 방법은 아래와 같다.

net start beep

그런데 이것은 재부팅때마다 재설정을 해야했고, 다음은 재부팅마다 재설정을 할 필요가 없게 만드는 커맨드다.

sc config beep start= disabled

이 방법 말고도 '장치관리자'를 통해 beep 을 제거하는 방법이 있다. 제어판의 장치관리자를 실행한후에 보기 - 숨김 장치 표시 를 해서 beep 장치를 '사용안함'으로 설정하는 방식이다.


다행히도 옥타브 3.2버전의 less는 '삐'거리는 소리 대신에 윈도 효과음을 사용하고 그것도 똑똑히 사용해서 더이상 저 설정이 필요없게 되었다.

나는 cygwin의 bin 디렉토리에 path가 걸려있어서 자주사용하는 프로그램들은 그곳에 배치스크립트를 작성해 넣어둔다. 옥타브의 경우는 cygwin/bin/octave.bat 파일로 넣어두어사용하며 그 내용은 다음과 같다.

cd C:\Users\pok\Documents\workspace\Octave
"C:\Octave\3.2.2_gcc-4.3.0\bin\octave-3.2.2.exe"
rem start C:\Users\pok\Documents\Utils\Console2\Console.exe -c C:\Users\pok\Documents\Utils\Console2\console_octave.xml

저렇게 하면 내 'workspace'가 pwd(present working directory, current working directory라 하여 cwd라고도 한다)로 설정되어 .m 파일등을 작성할때 편리하다.

아래 주석(rem) 되어 있는것은 cosole2라는 꽤 훌륭한 cmd 대체 프로그램을 이용할때인데, 이놈이 한글입력이 되지 않아 현재는 사용하지 않는다.

3.0버전에서는 사용자 디렉토리 밑에 무조건 'octave'라는 폴더를 만들어버려서 프로그램실행 창에서 'octave'라고 치면 그 디렉토리가 열렸다. 3.2버전에서는 그런만행을 하지 않아 꼭 octave.bat이라고 칠 필요없이 octave라고만 쳐도 되서 편리하다.

다음은 내 local home directory에 있는 .octaverc 파일의 내용.

addpath('C:\Users\pok\Documents\workspace\Octave');
edit("EDITOR", "C:\\Users\\pok\\Documents\\Utils\\Vim\\vim72\\gvim.exe %s -c cd C:\\Users\\pok\\Documents\\workspace\\Octave -c \"30vs .\" -c \"wincmd w\"");
edit("HOME", "C:\\Users\\pok\\Documents\\workspace\\Octave");
edit("LICENSE", "BSD");
#set(0,'defaulttextfontname', 'Malgun Gothic');

path에 내가 '.m'파일들을 모아놓고 있는 C:\Users\pok\Documents\workspace\Octave 를 추가했고
"EDITOR"에는 주로 사용하는 에디터인 vim 을 .m 파일들을 나열하여 열리게 설정하였다. "LICENSE"는 새로 만드는 .m 함수의 라이센스를 어떤걸로 할건지 여부를 정하는것은 기본은 GPL이고 나는 BSD로 라이센스를 변경했다.

3.0 버전에 plot의 기본글꼴 설정이 구리구리하여 set을 이용하여 기본글꼴을 설정했는데, 3.2버전에서는 wgnuplot에서 설정하고 저장할수 있게 바뀌었다.

멀티플랫폼/실행환경 Octave, 수학

초월수라는것은 다항식에서 정의되는 개념이고 다음과 같은 상황에서 쓰인다.

π는 유리수계수 다항식에 대해 초월적인 수(transcendental number, 초월수) 이다.

이것의 의미를 들여다보면 유리수 계수로 이루어진 어떠한 n차 방정식의 해도 π가 될수 없다는 말이다.

반면에 유리수 계수의 n차 방정식의 해가 되는 수를 대수적수(algebraic number)라고 한다. 예를들면 i는 x^2 + 1=0의 해이므로 대수적이다.

초월적이든 대수적이든간에 방정식의 해를 포함하는 field를 만들어 낼수 있다는 이론(Kronecker's Theorem) 이 있다. 예를들면 i를 포함하는 필드는 Q(i) = { a + bi | a, b는 유리수 } 이다. 이때의 Q(i)를 Q의 확대체(extension field) 라 한다.

Q(i)를 잘 살펴보면 1과 i를 base로 가지는, Q위의 벡터공간임을 알수 있다. 또한 이러한 경우 Q위의 Q(i)의 차원이 (기저의 갯수인) 2임도 알수 있고 이러한 관계를 [ Q(i) : Q ] = 2 라고 표현하고 Q위의 확대체 Q(i)의 차수(degree) 가 2 라고 읽는다.

이러한 이론이 어떤식으로 쓰이는지 재미있는 예가 있다.

작도를 통해 만들질수는 있는 수 c 가 있다고 하면, [ Q(c) : Q ] = 2의 거듭제곱 꼴 이어야하는데 60도(2π/3)의 3등분의 cosine 값은 8x^3 - 6x - 1 = 0의 근이고(드모르간의 정리를 이용한다) 이 근을 t라고 하면 이 t를 포함하는 Q위의 필드 Q(t) 의 degree가 3이기 때문에 ( [ Q(t) : Q ] = 3 ) 60도는 자와 컴퍼스를 가지고 3등분 할수 없다.

.....사실은 이번 기말고사에 나온 cos(rπ) (r은 유리수) 가 대수적수임을 증명하는 문제를 풀어서(!) 자랑하려고(!!) 쓰기 시작했는데.. 이정도 정리도 힘에 부친다. -_- [ Q(c) : Q ] 가 2의 거듭제곱꼴이어야 하는 이유는 컴퍼스를 이용해 만든 원과 직선의 방정식의 교점이 이차방정식이기 때문인데 힘들므로 생략.. 후후..

수학 이야기 수학

기본적인 극한증명인데..  처음배울때는 멍했는데 다시보니 기발하다.

'lim(x->a) f(x) = L' 임을 증명하라을 말로 풀어보면 이렇다.
x가 a에 충분히 가까이 갈때 f(x) 가 L에 가까이감을 증명하라.

1. 임의의 엡실론과 델타를 가정한다.
2. | x - a | < (델타) -> | f(x) - L | < (엡실론)
3. 임의의 엡실론에 대해 만족하는 델타가 존재한다.

2번을 다시 말로 풀어보면 이렇다. x와 a의 차가 충분히 작은 델타가 존재하면 f(x)와 L의 차가 충분히 작은 엡실론이 존재한다. 이럴때, 모든(every) 엡실론에 대해 델타가 존재하는것을 보이면 된다. (즉, 엡실론이 존재한다고 가정하고 그에따른 델타가 항상 존재하는것을 보이면, 엡실론이 존재한다는 가정은 참이되고, 따라서 엡실론과의 거리로 구할수 있는  L이 존재함도 참이다.)

참으로 기발하다.

이렇게 증명된 여러 lim를 가지고 다른 정리들도 유도해낸다. 예를들면 lim(x->a) f(x) = L이 존재하고 lim(x->a) g(x) = M 이면 limx(x->a) f(x)-g(x) = L - M 임도 위의 엡실론-델타로 구할수 있다.(물론 - 뿐만 아니라 +, x, / 등도 성립하고 그것도 많은 수학자들이 엡실론-델타를 이용해 증명해놨다.)

수학 이야기 극한, 수학

배우고자하는 학문에 쉽게 접근하는 방법중의 하나가 역사적으로 접근하는것이다. 수학에 대해 한참 알고싶을때 - 물론 지금도 매우 알고싶다 - 샀던 책이 '수학사'이고, 논술준비 차원에서 철학에 대한 공부를 하기 위해 샀던책이 '(한권으로 보는) 서양철학사 100장면'이다.

 수학사는 경문사에서 출판한 '경문수학산책' 시리즈중에 하나인데, 개인적으로 두권으로 나누어져 출판된 수학의 역사라는 책보다 이책이 좀더 나은것 같다. 수학의 역사에 대해 세기별로 잘 나누어 당시에 발명된 - 혹은 잘 정리된 - 개념과 그 개념과 연관된 당대 수학자를 중심으로 설명되어 있다. 700쪽도 안되는 책이다보니 각각의 분과에 대한 자세한 설명은 안나와있지만, 이러한 개념이 왜 생겨나게 되었는지, 어떤 경로를 통해 발전하였는지 잘 요약되어 있다.

책 내용중에 기억에 남는부분 몇가지.
우선, 로그의 역사. 로그는 17세기에 네이피어라는 사람에 의한 발명되었는데, 삼각함수에서 부터 영감을 얻어 만들어졌다고 한다. (그래서 초기의 로그는 기하학적이라고 말한다.)  로그의 목표는 분명했다. 큰수에 대한 계산을 빨리 하기 위한것. 그런데, 로그함수는 지수함수보다 먼저 개발되었다. 즉, 큰수가 지수함수로 부터 생긴것은 아니라는것. 로그는 케플러의 법칙 이후에 천문학에서 커다란 숫자를 다루게 되었고, 그것을 편리하게 하기위해 고안된 발명품이다. 지수함수는 스테빈에 의해 개발된 지수기호가 발명되고 나서 라이프니치에 의해 17세기 말에 발견되었다. 지수함수보다 로그함수가 먼저 발견된건 재미있는 사실이다.

다른 하나는 수학의 위기. 이 책에서는 수학 역사에는 3차례의 큰 위기가 있다고 한다. 하나는 무리수의 발견, 다른 하나는 미/적분에서 모호한 무한소 개념, 마지막으로 집합론에서 발견된 모순이라고 하며, 현재 세대는 마지막 위기속에서 수학을 발전시키고 있다는것.


 삶과 죽음. 이는 곧 생활과학과 종교로 발전했고 생활과학은 기하학으로, 종교는 문학으로 발전을 한다. 그리고 그러한 문학에서 철학을 탄생했다고 이 책의 저자는 말한다.

철학은 곧 합리화의 과정이다. 때로는 만물의 근원은 물이라며 합리화하고 때로는 신이기 때문이라며 합리화한다. 철학은 그렇게 발전한다.

(한권으로 보는) 서양철학사 100장면이라는 책은 이러한 철학의 발전 - 혹은 변화 - 과정을 100개의 작은 부분으로 나누어 역사적으로 살펴본다. 이러한 탐색을 통해 왜 고대 그리스/로마의 학문들을 중세시대 이후 유럽이 아라비아로부터 역수입 하게 되었는지, 왜 토인비는 역사를 도전과 응전이라는 법칙으로 설명하려 했는지 어렴풋이 알수 있다.

책에서 재미있었던 부분은 역사철학. 철학에서 역사를 고찰하는것은 매우 중요하다고 생각했는데, 의외로 역사철학의 발전은 더디었다. 아우구스티누스가 최초의 중요한 역사철학자라고 소개하는데, 그는 역사의 종교로 일컬어지는 기독교 사상가였고, 그로인해 역사의식이 투철했다고 소개한다. 그리고 한참후에 헤겔의 등장을 시작으로 역사철학이 본격적으로 발전했다고 한다. 나는 사실 헤겔이 주장하는 '역사의 발전은 자유의 확산'이라는 말에 크게 동의하지는 않지만, 역사에 발전이라는 의미를 부여한것에 대해서는 흥미롭다.

수학사나 철학의 역사에 관한 책을 읽고 있노라면 고상하다는듯 - 혹은 밥맛 없다는듯 - 쳐다본다. 하지만 이러한 역사는 힙합의 역사를 알아가는것이나 영화를 통해 사건의 전개를 보는것과 크게 다를것이 없다. 어떻게 흘러갔는지 알아보는 일은 재미있는 일이다.

책 이야기 수학, 역사, 책, 철학

엄청나게 오해하고 있었던부분. 까먹지 않도록 적어본다.

행벡터를 쓰는 DX에서 변환행렬(World Transform/Local Transform) 의 행이 축(기저벡터, basis vector) 이다.

뭣때문에 오해했는지는 몰라도(아마, 행벡터니까, 열이 축이어야 골고루-_- 곱해진다고 착각했나보다) 이런 오해를 하고도 이제껏 엔진을 만들고 있었다니...-_- 좀 그렇다. 앵무새처럼 암기하고 있는 방향이 _21, _22, _23인것은 DX의 2번째 행이 y축이고 y축이 보통 방향이기 때문이다.

n차 공간에서 좌표는 n개의 기저 벡터들의 일차결합으로 표현된다. (그래서 벡터공간 V의 차원(dimension)을 기저의 개수로 정의하고 dim V로 표시한다.) 예를들면, A라는 좌표는, A1 ~ An까지의 기저벡터에 대해 A = k1A1 + k2A2 + ... + knAn의 일차결함으로 표현될수 있고( A1, A2, ... An이 열벡터 - 기본적으로 수학에서 쓰는 벡터 - 라면 A를 열벡터 A1, A2, ... An에 의해 생성된 부분공간 - spanned subspace - 라고 부른다.) 이를 행렬로 나타내면 다음과 같다.

A의 한 원소 C에 대해

c1       (a11, a21, ... am1       ( k1
c2       a12, a22, ... am2           k2
c3  =   a13, a23, ... am3           k3
...        ...   ...                        ...
cn       a1n, a2n, ... amn)        kn )

그래서 열벡터를 쓰는 이경우, 행렬에서의 하나의 열인 a11,a12,...a1n이 하나의 기저벡터(축)이 되고 반대로, 행벡터를 사용하는 DX에서는 행이 하나의 축이 되는 것이다.

_21, _22, _23은 방향이라는 것보다 행벡터에서 행이 축 이 좀더 외우기 쉽지 아니한가! (...아닌가...-_- 일차결합에 대해서는 위키페디아에 자세히 나와있다.)

수학 이야기 선형대수, 수학

학점이 워낙 안좋아서 후달렸는데, 수학과 이중전공 신청이 받아들여졌다.
(사실 정원에 훨씬 미달인 사람들이 지원을 하긴 했지만... 내 학점이 정말 가관인지라...)

일단, 컴플랙스였던 미적분학을 어느정도 훈련하고, 듣고 싶었던 해석학을 들어야겠다.
음... 아마 대충 아래와 같은 과목을 듣게될듯.

해석학1
선형대수1
미적분학과 행렬 및 연습
다변수 미적분학과 연습
기하학개론
알고리즘

한꺼번에 너무 몰아듣는것 아닌가 쪼매 걱정도 되지만.. 열심앞에 장사없지 아니한가!
좋아. 가는거야!

일상 이야기 수학, 주저리, 학교수업

지난 수요일(07.9.19) 나이스하게도 지능로봇수업이 오일러 세미나로 대체되었다. 듣고싶어했던 것인데 무척 좋은기분과 그냥 인터넷에 공지올린걸로 허무하게 구멍나버린 수업 - 수업준비물도 잘 챙겼었단 말이다! - 의 짜증난 기분을 동시에 느끼며 세미나장으로 갔다. (가면서 느낀건데, 돈을 많이 처발라서 그런지 건물들이 좋기는 하더라 )

강의는 스위스의 제네바대 수학과 교수님이라는 바너 교수님께서 오일러의 업적중에서 재미난 부분과 JPEG/MPEG와의 연계된 설명들을 하고 스위스 대사관이라는 분의 스위스자랑(?) 그리고 기념품증정 추첨(진짜 받고 싶었는데...흑, 못받았다.)으로 끝났다.

바너 교수님의 강의는 재미있었다. 사실 클라인의 에를랑겐 프로그램에 푹 빠져있었는데, 오일러 수학도 아주아주 매혹적으로 보이게끔, 설명을 잘 해주셨다. 격의 없어보이는 몸짓과 행동들, 그리고 배낭.. 정말 멋진 교수님 같다.

카메라를 가져갈껄 무지 후회한다. '오늘을 잡아라!'를 내 삶의 모토로 한후, 오늘을 기록하는게 참 좋은짓같다고 생각하는고 있는거랑 기록을 위한 오늘을 지양하는거랑의 충돌이 마음속에 있긴 하지만, 역시 기분좋은 순간을 카메라로 기록하는것은 잘하는 짓 같다.

오일러 수학. 수학이랑 이중전공을 하면 열심히 배워보고 싶은 부분이다.

일상 이야기 수학, 오일러

동차좌표는 해석기하학에서 나온 개념인데, "열"을 추가해 표현과 변환을 쉽게 하고자 나온 개념이다. 해석기하학은 도형등의 실체적 개념을 좌표를 도입하여 실수화해서 실수의 대수적 계산능력을 이용하려 했다. 좌표란 점/선을 표현할 수 있는 도구이고, 실체적인(쉽게 받아들일수 있는) 좌표의 표현력을 늘리기 위해 동차좌표라는 개념이 등장했다.

동차좌표를 아주 쉽게 받아들일수 있는 표를 Florida Atlantic University의 한 강좌페이지에서 찾아볼수 있는데, 필요한 부분만 발췌하면 아래와 같다.

inhomogeneous coordinate	homogeneous coordinates
0	(0,1)
-7/3	(7,-3)
∞	(1,0)
not a point	(0,0)

inhomogeneous coordinates	homogeneous coordinates
(5,-7/3)	(5,-7/3,1)
(∞,0)	(1,0,0)
(0,∞)	(0,1,0)
(2,3/4)	(8,3,4)
(-3∞,2∞)	(-3,2,0)

예를 들어 점을 표현하는 2차원 점 좌표계에서 x축을 나타내기 위해 일반적으로 수가 아닌 기호를 써서(∞,0)로 나타내지만, 동차좌표를 이용해 (1,0,0) 으로 나타내면 x축이라는 직선을 모두 수로만 나타낼수 있다.

컴퓨터 그래픽스는 본질적으로 3차원 점 좌표에 관심을 가지는 분야이고 3차원 점좌표에대해 변환을 쉽게 하기 위해 4x4 행렬과 4개의 원소로 구성된 열백터를 사용하며, 이 열백터는 3차원 점에 대한 동차좌표이다. 그리고 이러한 동차좌표표현을 통해 이동변환(Translation)과 투영변환(Projection)을 쉽게 할 수 있다.

수학 이야기 게임개발, 수학