루트 격리 (root isolation)
위 다항식의 실수 근을 구하는 알고리즘을 짜려면 어떻게 해야할까? 뉴턴 방법이나 이분 매칭 등을 써서 그 값을 구할 수 있지만 위와 같이 실근이 2개 이상인 경우 모든 실근을 구하는 방법은 꽤 고민이 된다.
그런데 이때, 만약 위 방정식의 실근이 구간 [-1.5, -1.0] , [-0.5, 0], [1.0, 1.5] 에 하나씩 있다는 정보가 주어진다면? 각 구간에 이분 매칭 혹은 뉴턴 방법을 사용한다면 매우 쉽게 모든 실근을 구할 수 있을 것이다. 이렇게 루트가 하나만 있는 구간을 구하는 것을 루트 격리(root isolation)라고 한다.
루트 격리는 여러 방법이 있는데 그 중 하나가 스트룸 정리이다.
스트룸 정리(Strum's theorem)
스트룸 정리 (Strum's theorem)는 n차 다항식에서 어떤 구간에 실근(real roots)이 몇 개 있는지를 알아내는 방법을 제공한다. 이를 위해 스트룸 함수로 구성된 스트룸 체인(시퀀스)를 사용한다. 어떤 함수 $f(x)$에 대한 스트룸 함수 $f$는 다음과 같이 쓸 수 있다.
$f_n$은 $f_{n-2}$를 $f_{n-1}$로 나눈 나머지에 -1을 곱한 것이다.
그럼 이걸 어떻게 써먹나? 예를 보면 이해하기 쉽다.
위에서 언급한 다항식이 있다.
위 다항식의 스트룸 시퀀스를 구하면 다음과 같다.
이제 $x$가 (-2, 0, 2)일 때 각 스트룸 함수값의 부호와 $d(x)$ 값을 알아보자. d는 스트룸 시퀀스에서 함수값의 부호가 바뀐 횟수이다. (0은 무시한다.)
$x$가 -2일때는 부호가 3번 바뀌었으므로 (-1 -> 1, 1 -> -1, -1 -> 1) d의 값은 3이다.
자, 그럼 이 d값들을 어떻게 활용하는가?
$d(-2) - d(0) = 2$ 이다. 이것은 (-2,0]사이에 실근이 2개가 존재한다는 뜻이다.
마찬가지로 $d(0)-d(2)=1$ 이므로 (0,1]사이에는 실근이 하나 존재한다. 같은 방법으로 (-2,2]사이에는 실근이 3개 존재한다는 것을 알 수 있다. 그러나 (-2,0] 구간에 근이 두 개 이므로 루트 격리를 하지는 못했다. 따라서 저 구간을 반으로 나눈다면,
이제 (-2,-1] , (-1, 0], (0, 2] 구간에 루트가 하나씩 존재한다는 것을 알 수 있다.
우리가 근을 구하고자 했던 다항식의 그래프를 보면 루트 격리가 성공적임을 확인할 수 있다.
참고 :
'수학 > 이론' 카테고리의 다른 글
한 점과 가장 가까운 곡선 위의 점 구하기 (0) | 2021.09.04 |
---|---|
다항식의 근 구하기 (0) | 2021.08.29 |