프로그램을 하면서 수학적인 부분이 필요하다는 생각을 들었지만, 체계적으로 공부해 보아야지 하는 계기가 되었던듯 싶습니다.( 이제 공부를 해야 하지만요 ^^ )
많은 분들이 설명에 대한 부분을 기재해 놓으셨기 때문에 그 내용을 기반으로 구현부분을 구성해 보겠습니다.
예를 들어 좌표 (1,1), (2,4) 의 두 포인트만 있다고 가정해 보겠습니다.
x 좌표가 3일 때 y 값은 아마도 선형으로 생각할 때 7일 것입니다.
이 부분을 라그랑주 보간법으로 구성해 보면
x1 = 1, y1 = 1, x2 = 2 , y2 = 4
구하고자 하는 값이 y, x = 3 이라고 선언하고 보면 다음과 같은 수식이 만들어 집니다.
y = (x- x2)/(x1-x2)*y1+(x-x1)/(x2-x1)*y2 입니다.
값은 대입하면
(3-2)/(1-2)*1+(3-1)/(2-1)*4 = 7 입니다. y = 7 로 우리가 생각한것과 동일한 결과를 보여 줍니다.
이때 세번째 포인트를 (3,9) 라고 가정해 보면 어떤 결과가 나올까요?
이때 x = 4라 하고 y 값을 구한다면요?
예제의 좌표는 y = x^2 의 값으로 구성된 포인트 입니다. 1차 함수로는 그 값을 확인할 수 없습니다.
알고 있는 예상 값은 y = 16 입니다.
라그랑주의 수식을 그대로 대입해 보겠습니다. (이번에는 기호 없이 수치를 대입합니다.)
(4-2)*(4-3)/(1-2)*(1-3)*1+(4-1)*(4-3)/(2-1)*(2-3)*4+(4-1)*(4-2)/(3-1)*(3-2)*9 의 값입니다. 16 입니다.
위 의 내용을 프로그램으로 만든 부분이 아래의 내용입니다.
public static double executeLagrange(List<Double> xList, List<Double> yList, double xValue) {
double result = Double.NaN;
if ( xList == null || yList == null || xList.size() <= 2 || xList.size() != yList.size() ) {
return result;
}
int size = xList.size();
result = 0.0;
for ( int i = 0; i < size; i++ ) {
double dm = 1.0;
double ds = 1.0;
for ( int j = 0; j < size; j++ ) {
if ( i != j ) {
ds *= (xValue-xList.get(j));
dm *= (xList.get(i)-xList.get(j));
}
}
result += (ds/dm)*yList.get(i);
}
return result;
}
분모에 시작하는 값이 분자에는 올 수 없다는 부분만 고려하면 그리 어렵지 않게 메소드화 할 수 있습니다.
이제 주어진 값을 가지고 x위치의 y값을 가져오는 것은 해결 할 수 있습니다.
그럼 연속적인 라인값을 보고자 할 때 위의 계산을 반복해서 보아야 할까요?
가능하기는 하지만 해당 내용을 수식으로 보고자 할 경우가 더 많을것 같습니다.
결국 계수를 추출하는 방법이 필요하게 됩니다.
좌표의 갯수 - 1 이 차수가 되기 때문에 가로 세로가 같은 행렬을 구성해서 문제를 해결할 수도 있습니다.
여기서는 라그랑주 보간법의 분모와 분자를 분리해서 차수에 따라 1,2,3,4 ... 등의 값일때 구성될 수 있는 일종의 매트릭스를 찾는 방법으로 계수를 찾아 보았습니다.
일단 주어진 좌표에 따라 2차 수식이면 3개의 좌표가 있을테니 x값이 1, 2, 3 일 때의 y 값을 가져옵니다.
1,2,3,4 ... 확장되는 영역은 차수에 따라 고정되기때문에 그 규칙만을 확인하면 될것 같습니다.
위에서 계산한 2차식을 기준으로 간단한 예를 보면 다음과 같습니다.
분자
(x-2)*(x-3) = x^2 -5x + 6
(x-1)*(x-3) = x^2 -4x + 3
(x-1)*(x-2) = x^2 -3x + 2
분모
(1-2)*(1-3) = 2
(2-1)*(2-3) = -1
(3-1)*(3-2) = 2
처음은 1로 시작됩니다. 다음은 차수에 따라 -2, -5, -9, -14 ... 네 차이는 3, 4, 5 입니다.
중간은 전차수의 시작값*(-현차수)+(전차수 시작 다음값) 을 확인할 수 있습니다.
마직막 값은 전차수 마지막값*(-현차수) 의 규칙을 확인하였습니다.
다음은 그에 대한 코드 입니다.
private static List<List<Double>> getLagrangeRatioRecursive(List<List<Double>> calcList, int n) {
List<List<Double>> result = new ArrayList<List<Double>>();
List<Double> inList = null;
if (calcList == null ){
inList = new ArrayList<Double>();
inList.add(-2.0);
result.add(inList);
inList = new ArrayList<Double>();
inList.add(-1.0);
result.add(inList);
if ( n <= 2 ) {
for ( int i = 1; i <= n; i++ ) {
double no = 1.0;
for ( int j = 1; j <= n; j++ ) {
if ( i != j ) {
no *= (i-j);
}
}
result.get(i-1).add(0,1.0);
result.get(i-1).add(0,no);
}
return result;
} else {
return getLagrangeRatioRecursive(result,n);
}
}
int size = calcList.size();
int nSize = size+1;
int inSize = 0;
double d = 0.0;
for ( int i = 0; i < size; i++ ) {
inSize = calcList.get(i).size();
inList = new ArrayList<Double>();
d = calcList.get(i).get(0)-nSize;
inList.add(d);
for ( int j = 1; j < inSize; j++ ) {
d = ((calcList.get(i).get(j-1)*(0.0-nSize))+calcList.get(i).get(j));
inList.add(d);
}
d = calcList.get(i).get(inSize-1)*(0.0-nSize);
inList.add(d);
result.add(inList);
}
inList = new ArrayList<Double>();
inList.add(calcList.get(size-1).get(0)-size);
for ( int j = 1; j < inSize; j++ ) {
d = ((calcList.get(size-1).get(j-1)*(0.0-size))+calcList.get(size-1).get(j));
inList.add(d);
}
d = calcList.get(size-1).get(inSize-1)*(0.0-size);
inList.add(d);
result.add(inList);
if ( n > nSize ) {
return getLagrangeRatioRecursive(result,n);
} else {
for ( int i = 1; i <= n; i++ ) {
double no = 1.0;
for ( int j = 1; j <= n; j++ ) {
if ( i != j ) {
no *= (i-j);
}
}
result.get(i-1).add(0,1.0);
result.get(i-1).add(0,no);
}
return result;
}
}
다음은 실제로 테스트 코드 입니다.
List<Double> xList = new ArrayList<Double>();
List<Double> yList = new ArrayList<Double>();
double a = 2.0;
double b = -3.4;
double c = 4.5;
double d = -5.6;
double e = 6.7;
for ( int i = 1; i <= 5; i++ ) {
xList.add(i*1.0);
yList.add(Math.pow(i,4)*a + Math.pow(i,3)*b + Math.pow(i,2)*c + i*d + e);
}
List<Double> ccList = new ArrayList<Double>();
List<List<Double>> calcList = getLagrangeRatioRecursive(null,5);
for ( int i =0, size = calcList.size(); i < size ; i++ ) {
for ( int t = 1; t < calcList.get(i).size(); t++ ) {
double rt = calcList.get(i).get(t)/calcList.get(i).get(0);
if ( ccList.size() < t ) {
ccList.add(rt*yList.get(i));
} else {
ccList.set(t-1,ccList.get(t-1)+rt*yList.get(i));
}
}
}
System.out.println ( " RESULT : " + ccList );
아래는 결과 내용입니다.
RESULT : [2.0, -3.400000000000148, 4.500000000000227, -5.600000000000591, 6.700000000000159]
지금 구현한 방법은 차수가 커지거나, 계수가 아주 미세하거나 할 경우 부동소수점의 오류에 의해 약간 부정확한 데이터를 출력시킬 수 있습니다.
하지만 매번 상수값을 계산 하는 것이 아니라 보다 정밀한 데이터형으로(BigDecimal) 차수에 대한 상수를 메모리에 로딩하여 처리하면 편할것 같아서 구현해 보았습니다.
물론 에러 혹은 오류나 예외처리등은 검토하지 않았습니다.
행렬로 값을 구한다면
2차식의 경우 (3개의 좌표)
x1^0 x1^1 x1^2 y1
x2^0 x2^1 x2^2 y2
x3^0 x3^1 x3^2 y3
의 행렬식으로 값을 구해 올 수도 있습니다.
다항식에 좌표-1 개의 차수가 아닌 경우에는 행렬방식이 더 유용할 수도 있습니다.
댓글 없음:
댓글 쓰기