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, 수학

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

π는 유리수계수 다항식에 대해 초월적인 수(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의 거듭제곱꼴이어야 하는 이유는 컴퍼스를 이용해 만든 원과 직선의 방정식의 교점이 이차방정식이기 때문인데 힘들므로 생략.. 후후..

수학 이야기 수학

집합론에서 ordered pairs의 집합(클래스)를 그래프라고 부른다. 즉, U x V 의 임의의 subclass를 그래프라고 한다. 그래프는 관계표현에 편리하며 몇가지 재미있는 속성과 연산을 가지며 정의역과 치역의 개념을 가진다.
the domain of G : the class of all "first components" of elments of G
the range of G : the class of all "second components" of elements of G


(요거는, y exists such that
G has element, (x,y)
라고 읽는다)


Indexed family는 사실 매우 어려운 개념이다. 왜냐하면 index set이 finite set 이 아닐수 있을뿐만 아니라, countable 하지도 않을수 있기 때문이다. 셀수도 없는 집합을 이용하여 index(첨수?)를 한다. 어렵다. -_-;;;

Indexed family 는 집합을 또 다른 집합과 관계지어 만든다. 이때 이렇게 해서 만들어진 집합을 family((indexed family of set ) 혹은 collection이라고 하고 첨수를 매기는데 쓰이는 집합(index를 하는데 쓰이는 집합)을 index set라고 한다. 여기서 indexed family의 원소를 나타내는데 그래프가 유용하게 사용된다. Pinter의 집합론에 다음과 같은 정의(Indexed family of classes의 formal definition라고 나와있다)와 예가 나와있다.

수학 이야기 집합론

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

'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, / 등도 성립하고 그것도 많은 수학자들이 엡실론-델타를 이용해 증명해놨다.)

수학 이야기 극한, 수학

최근에 어째서 행벡터에서 열이 축인가 헷갈렸는지 알게되었다.

툴에서 카메라를 이동시키는 코드가 있었는데, 이 코드는 카메라를 x축 상으로 움직일때 (LookAt으로 만들어지는)View Matrix에서 _11, _21, _31을 가져왔었다. 그걸보고 햇병아리때 '오, 축은 열인갑다'라고 생각했었고 그게 머리속에 각인되어서 쭉 행벡터의 열이 축인줄 알았나 보다.

View Matrix는 좌표계 변환의 일종이고, 좌표계 변환은 Affine 변환의 일종이며, Affine변환에서 축들의 평행성은 유지되고 역은 전치된다. 그래서 카메라 좌표계의 _11, _12, _13이 전치되어 있는 View Matrix에서 _11, _21, _31을 가져오는 것이다.

행벡터는 행이 축이라는것을 실제적으로 보여주는 간단한 예가 있다.

                                 ( a11, a12, a13
(x', y', z') = (1,0,0) *    a21, a22, a23
                                   a31, a32, a33 )

기존의 x축의 기저를 어떤 Affine 변환을 해서 새로운 축 x', y', z'를 얻었다고 하자.
계산을 해보면,

(x', y', z') = ( 1*a11 + 0*a21 + 0*a31, 1*a12 + 0*a22 + 0*a32, 1*a13 + 0*a23 + 0*a33)
(x', y', z') = (a11, a12, a13)

이 되어 행벡터는 행이 축이라는것을 계산적으로 보여준다.

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

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

행벡터를 쓰는 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은 방향이라는 것보다 행벡터에서 행이 축 이 좀더 외우기 쉽지 아니한가! (...아닌가...-_- 일차결합에 대해서는 위키페디아에 자세히 나와있다.)

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

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

동차좌표를 아주 쉽게 받아들일수 있는 표를 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)을 쉽게 할 수 있다.

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