비동차 점화식
IT 위키
비동차 점화식(Non-Homogeneous Recurrence Relation)은 동차 점화식과 달리, 점화식의 오른쪽에 상수항 또는 독립적인 함수가 포함되는 점화식을 의미한다. 즉, 항들이 이전 항들의 선형 결합뿐만 아니라 추가적인 항을 포함하는 경우이다.
1 정의[편집 | 원본 편집]
비동차 점화식은 일반적으로 다음과 같이 표현된다.
- an + c1an-1 + c2an-2 + ... + ckan-k = f(n)
여기서,
- an은 점화식의 n번째 항
- c1, c2, ..., ck는 상수 계수
- f(n)은 0이 아닌 독립적인 함수 (예: 다항식, 지수 함수, 삼각 함수 등)
2 비동차 점화식의 해법[편집 | 원본 편집]
비동차 점화식의 해는 일반해 = 동차해 + 특수해의 형태로 구할 수 있다.
2.1 1. 동차해 (Homogeneous Solution)[편집 | 원본 편집]
- f(n) = 0일 때의 해를 먼저 구한다.
- 동차 점화식의 특성 방정식을 이용하여 일반해를 구한다.
2.2 2. 특수해 (Particular Solution)[편집 | 원본 편집]
- f(n)의 형태에 따라 특정한 해를 찾는다.
- 일반적으로 f(n)의 형태에 따라 다음과 같은 가정이 사용된다.
| f(n) | 특수해의 형태 |
|---|---|
| C (상수) | A |
| Cn | An + B |
| Cn² | An² + Bn + C |
| C rⁿ | A rⁿ |
| C sin(n), C cos(n) | A sin(n) + B cos(n) |
3 예제[편집 | 원본 편집]
3.1 1. f(n)이 상수인 경우[편집 | 원본 편집]
점화식:
- an - 3an-1 = 5
1단계: 동차해 구하기 특성 방정식:
- r - 3 = 0
- r = 3
따라서, 동차해는 다음과 같다.
- an(h) = A 3n
2단계: 특수해 구하기 f(n) = 5이므로, 특수해를 다음과 같이 가정한다.
- an(p) = C
이를 점화식에 대입하면,
- C - 3C = 5 → C = -5/2
따라서, 최종 해는 다음과 같다.
- an = A 3n - 5/2
3.2 2. f(n)이 다항식인 경우[편집 | 원본 편집]
점화식:
- an - an-1 = n
1단계: 동차해 구하기 특성 방정식:
- r - 1 = 0
- r = 1
따라서, 동차해는 다음과 같다.
- an(h) = A 1n = A
2단계: 특수해 구하기 f(n) = n이므로, 특수해를 다음과 같이 가정한다.
- an(p) = Cn + D
이를 점화식에 대입하면,
- (Cn + D) - (C(n-1) + D) = n
- Cn + D - Cn + C - D = n
- C = 1
따라서, 최종 해는 다음과 같다.
- an = A + n
4 비동차 점화식의 응용[편집 | 원본 편집]
- 알고리즘 분석
- 분할 정복 알고리즘의 시간 복잡도 분석 (예: 마스터 정리).
- 수열 및 조합론
- 파스칼의 삼각형 및 조합 점화식에서 활용.
- 물리학 및 공학
- 차분 방정식을 이용한 동역학 모델링.
5 같이 보기[편집 | 원본 편집]
6 참고 문헌[편집 | 원본 편집]
- Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill.
