글
안장점 찾기는 매우 흥미로운 주제이다. 왜냐하면, 내 졸업논문 주제가 안장점 찾기 알고리즘을 비교하는 것이기 때문이다. 다른 사람에게는 흥미롭지 않을지도 모르지만 어쨌든 찾아보자.
우선, 안장점이 뭔가에 대해서 알아야 한다. R이 위치를 나타내는 벡터라 치고, f(R)=z인 어떤 그래프가 있을 때, 안장점은 R의 어떤 방향으로는 극대값이고 다른 어떤 방향으로는 극소값을 갖는 지점이다. 어떤 방향으로 극대값인데 그 방향으로도 극소값을 갖는다면 그건 그 방향으로 상수함수니까 별로 중요하지 않다. 이 안장점을 찾아야 하는 이유는, 내가 졸업논문에 안장점 찾기 알고리즘을 쓰기로 했기 때문만이 아니라, 여러가지 물리적인 현상을 컴퓨터를 이용해 계산하는데 있어 안장점이 중요한 역할을 하기 때문이다. 어떤 물리적인 계가 항상 바닥 상태에만 있다면 그 물리계를 나타내는 상태 함수를 찾아낸 후, 그 상태함수의 극소값을 다 찾아내면 된다. 극소값을 찾아내는 문제는 고등학생이면 다 알다시피 미분해서 0되는 지점을 찾아내는 것이다. 그런데, 미분해서 0이 된다고 다 극소값은 아니다. 물론, 미분해서 0이 되는 지점을 다 찾아낸 후, 그 지점 각각이 극소값인지 극대값인지 아무것도 아닌지 알아내는 것은 매우 쉽다. 그런데 항상 바닥상태에만 있다면 아무 일도 일어나지 않을 것이고, 아무 일도 일어나지 않는 세계는 우리가 사는 세상이 아니다. 알다시피 매일 사건이 터지는 곳이 바로 현실이다. 즉, 바닥상태에서 다른 곳으로 움직이는 것을 예측해야만 하는데, 물리적인 계는 다른 곳으로 움직일 때에도 웬만하면 가장 에너지가 낮은 곳으로 움직이려고 하기 때문에 에너지가 가장 낮은 경로를 따라서 움직인다. 다만, 바닥상태는 아니니까 한쪽으로는 점점 위로 올라가는 것이다. 한없이 올라갈 수는 없으므로 언젠가는 다른 바닥상태에 도착할 것이다. 즉, A에서 B로 가는 방향인데 가면 갈수록 점점 올라가긴 한다. 하지만 원래 가는 방향이 아닌 다른 방향으로 가면 더 힘들다. (극소점) 그리고 바닥에서 다른 바닥으로 가는 거니까, 올라가다가 언젠가는 내려가야 하고, 따라서 어딘가에서는 극대값을 갖는다. 바로 이 지점, 극소값이면서 극대값을 갖는 지점이 안장점이다.
우리가 관심을 갖고 있는 물리적인 계가 여기서 저기로 움직일 때 어느 곳을 통해서 가는지 알아내려면 안장점을 알아내야 한다. 이것이 안장점이 흥미로운 이유다. 물론 내가 졸업논문에 쓰기로 했으니까 더더욱 흥미로운 주제가 된다. 만약 이 주제가 흥미롭지 않다면, 당신은 내가 아니라는 것이 증명될 뿐이다.
아무튼 원래 문제는 극소값이 아니라 안장점이므로.
안장점은 어떤 방향으로는 극대값이고 다른 방향으로는 극소값이 되는 지점이기 때문에, 그 지점에서 함수를 한번 미분하면 0이다. 고등학생이라면 ... 다 아는 얘기니까 하는 거지만, ... 두번 미분했을 때 그 값이 음수라면 위로 볼록한 부분이고 양수라면 아래로 볼록한 부분이다. 두번 미분했을 때 0이라면 끔찍한 일이 벌어진다. 평평하다. -_-;
안장점의 예
http://www.google.com/images?um=1&hl=ko&client=ubuntu&channel=fs&biw=1276&bih=713&tbs=isch%3A1&sa=1&q=saddle+point&aq=f&aqi=&aql=&oq=&gs_rfai=
어쨌든 안장점인지 아닌지 알아내기 위해서는 이게 오목하지도 않고 볼록하지도 않다는 걸 확인해야 하므로 항상 두번 미분해야 한다. 그런데, y=f(x)같이 1차원에서 1차원으로 가는 함수면 과학자들이 고민하지도 않을 것이다. 과학자들이 풀고 있는 문제는 임의의 n차원에서 n이 300000000000000000000000정도 되는 경우에 안장점을 어떻게 찾을 것인가 하는 문제이다 물론 이건 너무 복잡하니까 이보다 10억배 정도 쉬운 문제인 n=300000000000000 차원 정도에서 풀려고 하는데 그래도 복잡하니까 다시 1000만배 정도 쉬운 문제인 n=30000000차원 정도의 문제를 풀려고 한다. 물론 사람이 계산할 순 없다. 돈 아무리 많이 줘도 이짓은 못하겠다. (옛날엔 했다. 케플러가 살던 시절에는.) 그럼, 여기서 2차 도함수를 계산한다면, 1차 미분한 각각의 함수의 1차미분이니까, 다시 계산해야 하는 수가 900000000000000개가 된다. 하지만 이건 안장점을 알고 있는 경우에 그 점에서 계산해야 하는 수의 개수이고, 어디있는지 모르면 그 안장점을 찾아 헤매이면서 모든 점에서 다 해봐야 안다. 즉, 이건 컴퓨터조차 파업할만한 문제다. (파업하는 컴퓨터가 있다면 그 컴퓨터는 고장났거나, 미래에서 왔을 것이다.)
그래서 컴퓨터에게 삽질을 떠넘기고 그 사이에 편히 쉬면서 좀 더 유용한 일을 하려는 전산물리학자들은 두번 미분 할 필요 없이 한번만 미분해서 문제를 해결하는 방법을 찾아내기 시작했다. 그것이 내 졸업논문에서 다루려고 하는 Stability Boundary Method와 Dimer Method와 Nudged Elastic Band Method이다.
자, 일단 여기까지. 각각의 알고리즘에 대한 자세한 설명은 다음 기회에...
우선, 안장점이 뭔가에 대해서 알아야 한다. R이 위치를 나타내는 벡터라 치고, f(R)=z인 어떤 그래프가 있을 때, 안장점은 R의 어떤 방향으로는 극대값이고 다른 어떤 방향으로는 극소값을 갖는 지점이다. 어떤 방향으로 극대값인데 그 방향으로도 극소값을 갖는다면 그건 그 방향으로 상수함수니까 별로 중요하지 않다. 이 안장점을 찾아야 하는 이유는, 내가 졸업논문에 안장점 찾기 알고리즘을 쓰기로 했기 때문만이 아니라, 여러가지 물리적인 현상을 컴퓨터를 이용해 계산하는데 있어 안장점이 중요한 역할을 하기 때문이다. 어떤 물리적인 계가 항상 바닥 상태에만 있다면 그 물리계를 나타내는 상태 함수를 찾아낸 후, 그 상태함수의 극소값을 다 찾아내면 된다. 극소값을 찾아내는 문제는 고등학생이면 다 알다시피 미분해서 0되는 지점을 찾아내는 것이다. 그런데, 미분해서 0이 된다고 다 극소값은 아니다. 물론, 미분해서 0이 되는 지점을 다 찾아낸 후, 그 지점 각각이 극소값인지 극대값인지 아무것도 아닌지 알아내는 것은 매우 쉽다. 그런데 항상 바닥상태에만 있다면 아무 일도 일어나지 않을 것이고, 아무 일도 일어나지 않는 세계는 우리가 사는 세상이 아니다. 알다시피 매일 사건이 터지는 곳이 바로 현실이다. 즉, 바닥상태에서 다른 곳으로 움직이는 것을 예측해야만 하는데, 물리적인 계는 다른 곳으로 움직일 때에도 웬만하면 가장 에너지가 낮은 곳으로 움직이려고 하기 때문에 에너지가 가장 낮은 경로를 따라서 움직인다. 다만, 바닥상태는 아니니까 한쪽으로는 점점 위로 올라가는 것이다. 한없이 올라갈 수는 없으므로 언젠가는 다른 바닥상태에 도착할 것이다. 즉, A에서 B로 가는 방향인데 가면 갈수록 점점 올라가긴 한다. 하지만 원래 가는 방향이 아닌 다른 방향으로 가면 더 힘들다. (극소점) 그리고 바닥에서 다른 바닥으로 가는 거니까, 올라가다가 언젠가는 내려가야 하고, 따라서 어딘가에서는 극대값을 갖는다. 바로 이 지점, 극소값이면서 극대값을 갖는 지점이 안장점이다.
우리가 관심을 갖고 있는 물리적인 계가 여기서 저기로 움직일 때 어느 곳을 통해서 가는지 알아내려면 안장점을 알아내야 한다. 이것이 안장점이 흥미로운 이유다. 물론 내가 졸업논문에 쓰기로 했으니까 더더욱 흥미로운 주제가 된다. 만약 이 주제가 흥미롭지 않다면, 당신은 내가 아니라는 것이 증명될 뿐이다.
아무튼 원래 문제는 극소값이 아니라 안장점이므로.
안장점은 어떤 방향으로는 극대값이고 다른 방향으로는 극소값이 되는 지점이기 때문에, 그 지점에서 함수를 한번 미분하면 0이다. 고등학생이라면 ... 다 아는 얘기니까 하는 거지만, ... 두번 미분했을 때 그 값이 음수라면 위로 볼록한 부분이고 양수라면 아래로 볼록한 부분이다. 두번 미분했을 때 0이라면 끔찍한 일이 벌어진다. 평평하다. -_-;
안장점의 예
http://www.google.com/images?um=1&hl=ko&client=ubuntu&channel=fs&biw=1276&bih=713&tbs=isch%3A1&sa=1&q=saddle+point&aq=f&aqi=&aql=&oq=&gs_rfai=
어쨌든 안장점인지 아닌지 알아내기 위해서는 이게 오목하지도 않고 볼록하지도 않다는 걸 확인해야 하므로 항상 두번 미분해야 한다. 그런데, y=f(x)같이 1차원에서 1차원으로 가는 함수면 과학자들이 고민하지도 않을 것이다. 과학자들이 풀고 있는 문제는 임의의 n차원에서 n이 300000000000000000000000정도 되는 경우에 안장점을 어떻게 찾을 것인가 하는 문제이다 물론 이건 너무 복잡하니까 이보다 10억배 정도 쉬운 문제인 n=300000000000000 차원 정도에서 풀려고 하는데 그래도 복잡하니까 다시 1000만배 정도 쉬운 문제인 n=30000000차원 정도의 문제를 풀려고 한다. 물론 사람이 계산할 순 없다. 돈 아무리 많이 줘도 이짓은 못하겠다. (옛날엔 했다. 케플러가 살던 시절에는.) 그럼, 여기서 2차 도함수를 계산한다면, 1차 미분한 각각의 함수의 1차미분이니까, 다시 계산해야 하는 수가 900000000000000개가 된다. 하지만 이건 안장점을 알고 있는 경우에 그 점에서 계산해야 하는 수의 개수이고, 어디있는지 모르면 그 안장점을 찾아 헤매이면서 모든 점에서 다 해봐야 안다. 즉, 이건 컴퓨터조차 파업할만한 문제다. (파업하는 컴퓨터가 있다면 그 컴퓨터는 고장났거나, 미래에서 왔을 것이다.)
그래서 컴퓨터에게 삽질을 떠넘기고 그 사이에 편히 쉬면서 좀 더 유용한 일을 하려는 전산물리학자들은 두번 미분 할 필요 없이 한번만 미분해서 문제를 해결하는 방법을 찾아내기 시작했다. 그것이 내 졸업논문에서 다루려고 하는 Stability Boundary Method와 Dimer Method와 Nudged Elastic Band Method이다.
자, 일단 여기까지. 각각의 알고리즘에 대한 자세한 설명은 다음 기회에...
RECENT COMMENT