특성 방정식(Characteristic Equation)은 점화식이나 선형 상미분 방정식의 해를 구하기 위해 사용되는 방정식이다. 점화식에서 특성 방정식은 수열의 일반해를 구하는 데 중요한 역할을 한다.
정의
특성 방정식은 동차 점화식의 일반해를 찾기 위해 다음과 같이 정의된다.
- 점화식:
- an + c1an-1 + c2an-2 + ... + ckan-k = 0
이에 대응하는 특성 방정식은 다음과 같다.
- 특성 방정식:
- rk + c1rk-1 + c2rk-2 + ... + ck = 0
여기서,
- an은 점화식의 n번째 항
- c1, c2, ..., ck는 상수 계수
- r은 특성 방정식의 해 (근)
특성 방정식의 근에 따른 해
특성 방정식의 근을 구한 후, 다음과 같이 해를 결정한다.
- 서로 다른 실근 r1, r2, ..., rk이 존재할 경우
- an = A1r1n + A2r2n + ... + Akrkn
- A1, A2, ..., Ak는 초기 조건에 의해 결정됨.
- 중복된 근 r이 m번 존재할 경우
- an = (A1 + A2n + ... + Amnm-1)rn
- 복소근 α ± βi가 존재할 경우
- an = A eαn cos(βn) + B eαn sin(βn)
예제
1. 피보나치 수열
피보나치 수열은 다음과 같은 점화식을 만족한다.
- an = an-1 + an-2
특성 방정식은 다음과 같다.
- r2 - r - 1 = 0
이를 풀면, 근은 다음과 같다.
- r = (1 ± sqrt(5)) / 2
따라서, 일반해는 다음과 같다.
- an = A( (1+sqrt(5))/2 )n + B( (1-sqrt(5))/2 )n
2. 2차 점화식
점화식:
- an - 4an-1 + 4an-2 = 0
특성 방정식:
- r2 - 4r + 4 = 0
이를 풀면, 중근 r = 2가 나온다.
따라서, 일반해는 다음과 같다.
- an = (A + Bn) 2n
특성 방정식의 응용
- 점화식 해법
- 선형 점화식을 푸는 데 사용됨.
- 미분 방정식
- 선형 상미분 방정식의 해를 구하는 데 활용됨.
- 알고리즘 분석
- 분할 정복 알고리즘의 시간 복잡도 분석 (예: 마스터 정리).
같이 보기
참고 문헌
- Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill.