Graphics Programming
중간값 정리로 함수의 해 근사값 구하기 본문
중간값 정리 - 위키피디아
http://ko.wikipedia.org/wiki/%EC%A4%91%EA%B0%84%EA%B0%92_%EC%A0%95%EB%A6%AC
뉴턴법으로 어떻게 구해보려고 쇼를 하다가 미적분학 강의 때 중간값 정리 보고 '아.. -_-' 하며 구현했다.
함수 f:R->R 이 해를 구하려는 구간 내에서 연속이다고 가정한다. 그러면 f(a)와 f(b)의 부호가 다를 경우 그 사이에 f(c) = 0인 지점이 반드시 있는데 c가 바로 방정식 f(x) = 0의 해다.
그러니 정의역에서 해를 구할 구간을 적당히 잡고 적당한 간격으로 함숫값을 추출해서 바로 전에 추출한 함숫값과 부호가 다르면 그 구간에서 이진 분할을 하든 열 조각으로 쪼개든 하여 범위를 점점 좁혀나가면 해의 근사값을 얻을 수 있다.
실시간으로 해를 구하기 위해 쓸 것이냐, 시간은 얼마나 걸리든 모든 해를 최대한 정확하게 구하는 데 쓸 것이냐에 따라 해를 구할 범위와 추출 간격을 조정하면 되겠다. 가령 두 해가 너무 가까워 한 해밖에 구하지 못할 것이 염려되는 경우 간격을 좁히고 시간을 더 투자할 수도 있고, 게임에서 실시간으로 발사 위치를 구하는 것이라면 두 해 중 뭘 쓰든 티가 안 나니까 하나 얻은 것을 그대로 쓰면 된다.
package codeonwort.math {
// 일변수 실함수의 [t0, t1] 내 모든 해의 근사치를 구한다.
public function rootsOfRealFuncWithSingleVar(f:Function, t0:Number=0, t1:Number=1, step:Number=0.01):Array {
var prev_sgn:int = 0
var sgn:int = 0 // (-1, 0, 1) -> (음수, 0, 양수)
var val:Number
var roots:Array = []
for(var t:Number=t0; t<=t1; t+=step){
val = f(t)
sgn = sign(val)
if(sgn == 0){
roots.push(t)
}else if(sgn == -prev_sgn){
roots.push(find(t-step, t))
}
prev_sgn = sgn
}
function find(t0:Number, t1:Number, cnt:int=5):Number {
var mid:Number = .5 * (t0 + t1)
if(cnt == 0) return mid
else if(sign(f(t0)) == sign(f(mid))){
return find(mid, t1, cnt - 1)
}else return find(t0, mid, cnt - 1)
}
return roots
}
}
f(x) = 0이 아니라 f(x) = k의 해를 구하고 싶다면 위의 코드를 좀 손보거나 g(x) = f(x) - k = 0의 해를 구한다.
아래 플래시는 위 함수를 이용하여 6차 베지어 곡선과 선분의 교점을 구한다.
