점화식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 점화식의 정의 및 기본 개념
3. 점화식의 종류
4. 점화식의 해법
5. 점화식의 응용
6. 점화식과 미분 방정식의 관계
참조

1. 개요

점화식은 수열의 각 항을 이전 항들의 함수로 나타내는 방정식으로, 수열의 규칙성을 정의하는 데 사용된다. 1차 및 k차 점화식으로 분류되며, 피보나치 수열이 대표적인 예시이다. 점화식은 인접 2항, 3항 간의 관계를 나타내는 형태로 구분되며, 선형, 상수 계수, 비선형 점화식 등 다양한 종류가 존재한다. 점화식은 특성 방정식, 생성 함수, 선형대수학, Z 변환 등을 활용하여 해를 구할 수 있으며, 수학적 생물학, 컴퓨터 과학, 디지털 신호 처리, 경제학 등 다양한 분야에서 응용된다. 특히 알고리즘 분석에서 시간 복잡도를 나타내는 데 중요한 역할을 하며, 미분 방정식을 수치적으로 풀 때 점화식이 활용되기도 한다.

2. 점화식의 정의 및 기본 개념

점화식은 수열의 각 항을 이전 항(들)의 함수로 나타내는 방정식이다. 예를 들어, ''a''_''n''+1 = ''f''(''a''_''n'') 와 같이 인접 2항간의 관계를 나타내는 점화식이나, ''a''_''n''+2 = ''f''(''a''_''n''+1, ''a''_''n'') 처럼 인접 3항간의 관계를 나타내는 점화식을 생각할 수 있다.^[1]

점화 관계는 좀 더 정확히 표현하면, 바로 앞의 항만 관련된 경우 다음과 같은 형태를 띈다.

: $u_n=\varphi(n, u_{n-1})\quad\text{for}\quad n>0,$

여기서 $\varphi:\mathbb N\times X \to X$ 는 함수이며, X는 수열의 원소가 속해야 하는 집합이다. $u_0\in X$ 를 첫 번째 항으로 하는 유일한 수열을 정의하며, 이를 ''초깃값''이라고 한다.^[1]

1 이상의 인덱스 항부터 시작하는 수열을 얻도록 정의를 수정하는 것은 어렵지 않다.

이것은 ''1차'' 점화 관계를 정의한다. ''k차'' 점화 관계는 다음과 같은 형태를 가진다.

: $u_n=\varphi(n, u_{n-1}, u_{n-2}, \ldots, u_{n-k})\quad\text{for}\quad n\ge k,$

여기서 $\varphi: \mathbb N\times X^k \to X$ 는 수열의 k개의 연속된 항을 포함하는 함수이다. 이 경우, 수열을 정의하기 위해 k개의 초깃값이 필요하다.

팩토리얼은 다음과 같은 점화식으로 정의된다.

: $n!=n\cdot (n-1)!\quad\text{for}\quad n>0,$

그리고 초기 조건은

: $0!=1.$

이는 차수가 1이고 간단한 다항식(n에 대한)인 ''선형 점화 관계(linear recurrence)''의 한 예시이다. 여기서 n은 유일한 계수이다.

피보나치 수열은 선형 점화식

: $F_{n} = F_{n-1}+F_{n-2}$

에 초기값 $F_0:=0,\ F_1:=1$ 을 주어 얻을 수 있다.

이 점화식은 양수로 쓰면 $F_2=F_1+F_0,\ F_3=F_2+F_1,\ F_4=F_3+F_2,\dots$ 와 같은 무한 개의 식과 같다.

이렇게 얻어진 피보나치 수열의 처음 몇 항을 쓰면

: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

와 같다.

3. 점화식의 종류

점화식은 여러 종류로 나눌 수 있으며, 각 종류에 따라 다른 해법이 존재한다.

인접 2항간 점화식: 수열 ''a''_''n''^영어이 변수가 하나인 함수 ''f''에 의해 ''a''_''n''+1 = ''f''(''a''_''n'') 형태로 나타내어지는 점화식이다.
인접 2항간 선형 점화식: 함수 ''f''가 일차식인 경우, 즉 ''a''_''n''+1 = ''p''(''n'') · ''a''_''n'' + ''q''(''n'') (선형 점화식) 형태이다.
인접 3항간 점화식: 수열 {''a''_''n''}에서 ''a''_''n''+2 = ''f''(''a''_''n''+1, ''a''_''n'')와 같이 인접한 세 항 사이의 관계를 나타내는 점화식이다.
인접 3항간 선형 점화식: 함수 f가 일차식인 경우, 즉 a_(n+2) = p(n) * a_(n+1) + q(n) * a_n + r(n) 형태의 점화식이다.
상수 계수 선형 점화식: 모든 계수가 상수인 선형 점화식이다. 특성 방정식을 이용하여 일반항을 구할 수 있다.
수열의 합을 포함하는 경우: 점화식 내에 그 수열의 합이 들어있는 경우, 적절한 변형을 통해 인접한 몇 개의 항을 포함하는 점화식으로 바꾼다.
비선형 점화식: 일반적으로 풀이법이 알려져 있지 않지만, 몇몇 특수한 경우에는 해를 구할 수 있다. 예를 들어 로지스틱 맵과 같은 경우가 있다.
역수를 이용하는 경우: $p a_n a_{n+1} = q a_n - r a_{n+1}$ 형태의 점화식은 양변을 $a_n a_{n+1}$ 으로 나누어 해결한다.
로그를 이용하는 경우: $a_{n+1} = 4a_n^2$ 와 같이 주어진 경우 양변에 로그를 취하여 선형 점화식으로 변환하여 해결한다.
주기형: $a_{n+1} = - \frac{1}{a_n + 1}$ 과 같이 주어진 점화식은 몇몇 값을 대입하여 주기를 파악하여 해결한다.

각 점화식의 종류에 따라 해법이 달라지므로, 주어진 점화식의 형태를 파악하는 것이 중요하다.

3. 1. 인접 2항간 점화식

수열 ''a''_''n''^영어이 변수가 하나인 함수 ''f''에 의해 ''a''_''n''+1 = ''f''(''a''_''n'') 형태로 나타내어지는 점화식을 인접 2항간 점화식이라고 한다. 인접 2항간 점화식 중 ''f''가 일차식인 ''a''_''n''+1 = ''p''(''n'') · ''a''_''n'' + ''q''(''n'') (''p'', ''q''는 ''n''의 함수) 형태를 선형 점화식이라고 한다.

3. 1. 1. 인접 2항간 선형 점화식

함수 ''f''가 일차식인 경우, 즉 ''a''_''n''+1 = ''p''(''n'') · ''a''_''n'' + ''q''(''n'') 형태의 점화식을 linear|선형^영어 점화식이라고 한다. 계수 ''p''(''n''), ''q''(''n'')이 상수인 경우 등차수열 또는 등비수열로 변환하여 일반항을 구할 수 있다.

''p'' = 1 일 때, 점화식은 ''a''_''n''+1 = ''a''_''n'' + ''q''이며, 이것은 등차수열을 나타낸다.

''p'' ≠ 1 일 때, 점화식 ''a''_''n''+1 = ''p'' · ''a''_''n'' + ''q''의 특성방정식 ''x'' = ''px'' + ''q''의 근을 α라고 하면, 점화식은 ''a''_''n''+1 - α = ''p''(''a''_''n'' - α)으로 변형할 수 있다. 이것은 일반항이 ''b''_''n'' = ''a''_''n'' - α로 정의되는 수열 {''b''_''n''}이 공비가 ''p''인 등비수열이 된다는 뜻이며, ''b''_''n''을 ''n''의 식으로 쓸 수 있다. 다시, ''a''_''n'' = ''b''_''n'' + α이므로, 이것도 ''n''의 식으로 표현 가능하다.

계수가 상수가 아닌 경우, 변형을 통해 해결 가능한 형태로 바꾸어야 한다. 몇몇 특수한 경우에 풀이법이 잘 알려져 있다.^[3]

팩토리얼은 다음과 같은 점화식으로 정의된다.

:

n!=n\cdot (n-1)!\quad\text{for}\quad n>0,

그리고 초기 조건은 다음과 같다.

:

0!=1.

이는 차수가 1이고 간단한 다항식에 대한 선형 점화 관계(linear recurrence)의 한 예시이다. 여기서

n

은 유일한 계수이다.

가변 계수를 갖는 일반적인 1차 비동차 선형 점화 관계의 경우:

:

a_{n+1} = f_n a_n + g_n, \qquad f_n \neq 0,

이를 해결하는 방법은 다음과 같다.

:

a_{n+1} - f_n a_n = g_n

:

\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{f_n a_n}{\prod_{k=0}^n f_k} = \frac{g_n}{\prod_{k=0}^n f_k}

:

\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{a_n}{\prod_{k=0}^{n-1} f_k} = \frac{g_n}{\prod_{k=0}^n f_k}

다음과 같이 정의한다.

:

A_n = \frac{a_n}{\prod_{k=0}^{n-1} f_k},

그러면,

:

A_{n+1} - A_n = \frac{g_n}{\prod_{k=0}^n f_k}

:

\sum_{m=0}^{n-1}(A_{m+1} - A_m) = A_n - A_0 = \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}

:

\frac{a_n}{\prod_{k=0}^{n-1} f_k} = A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}

:

a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right)

3. 2. 인접 3항간 점화식

수열 {''a''_''n''}에서 ''a''_''n''+2 = ''f''(''a''_''n''+1, ''a''_''n'')와 같이 인접한 세 항 사이의 관계를 나타내는 점화식을 인접 3항간 점화식이라고 한다.

이항 계수

\tbinom{n}{k}

는

n

개의 원소에서

k

개를 선택하는 경우의 수를 나타내며, 다음과 같은 점화 관계를 갖는다.

:

\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

(단,

\tbinom{n}{0}=\tbinom{n}{n}=1

)

이 공식을 사용하면 파스칼의 삼각형을 만들 수 있다. 이항 계수는 다음 공식으로도 계산할 수 있다.

:

\binom{n}{k}=\frac{n!}{k!(n-k)!}

또 다른 방법으로, 이항 계수는 다음과 같은 1차원 점화식을 통해 계산할 수도 있다.

:

\binom n k = \binom n{k-1}(n-k+1)/k

(단,

\binom n 0 =1

)

3. 2. 1. 인접 3항간 선형 점화식

함수 f가 일차식인 경우, 즉 a_(n+2) = p(n) * a_(n+1) + q(n) * a_n + r(n) 형태의 점화식을 인접 3항간 선형 점화식이라고 한다. 여기서 p(n), q(n), r(n)은 n에 대한 함수이다.^[8]

계수가 상수가 아닌 경우에는 각각의 점화식에 따라 다양한 기법을 적용해야 한다. 양변을 적절한 수로 나누는 등의 시도를 해 볼 수 있다.

피보나치 수가 만족하는 2차 점화식은 상수 계수를 갖는 동차 선형 점화식의 전형적인 예이다. 피보나치 수열은 점화식 F_n = F_(n-1) + F_(n-2)와 초기 조건 F_0 = 0, F_1 = 1로 정의된다. 이 점화식은 비네 공식을 통해 해결할 수 있으며, 특성 다항식 t^2 = t + 1의 두 근의 거듭제곱을 포함한다.

3. 3. 상수 계수 선형 점화식

상수 계수 선형 점화식은 모든 계수가 상수인 선형 점화식이다. 이러한 점화식은 특성 방정식을 이용하여 일반항을 구할 수 있다.^[2]

계수 ''p'', ''q''가 상수인 2항간 점화식, 즉,

: ''a''_''n''+1 = ''p'' · ''a''_''n'' + ''q'' (p, q는 n에 관계하지 않는 상수)

에서 ''p'' = 1 이면 등차수열이 된다. ''p'' ≠ 1 이면 특성방정식 ''x'' = ''px'' + ''q''의 근 α를 이용하여

:''a''_''n''+1 - α = ''p'' (''a''_''n'' - α)

로 변형할 수 있다. 이는 수열 {''b''_''n''} (''b''_''n'' = ''a''_''n'' - α)이 공비가 ''p''인 등비수열이 된다는 의미이며, 따라서 ''b''_''n''과 ''a''_''n''을 ''n''의 식으로 표현할 수 있다.

일반적으로, 계수가 모두 상수인 선형 점화식

:

a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}

은 특성 방정식

:

x^d = c_1 x^{d-1} + \cdots + c_{d-1}x^1 + c_d

의 해를 구하여 일반항을 구한다.

피보나치 수는 상수 계수를 갖는 동차 선형 점화식의 대표적인 예시이다. 피보나치 수열은 점화식

F_n = F_{n-1}+F_{n-2}

와 초기 조건

F_0 = 0

,

F_1 = 1

로 정의된다. 이 점화식은 비네 공식을 통해 일반항을 구할 수 있으며, 생성 함수는 유리 함수

\frac{t}{1-t-t^2}

이다.

정수 계수 ''d''차 선형 동차 점화식은 일반적으로

:

a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}

형태로 표현되며, ''d''개의 계수 ''c''_''i''는 상수이다. 이 점화식을 만족하는 수열을 '''선형 귀납 수열'''이라 하며, 초깃값 ''a''₀, ..., ''a''_''d''-1에 의해 유일하게 결정된다.

이러한 선형 점화식의 특성 다항식

:

p(t):= t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d}

의 ''d''개의 근은 점화식을 만족하는 수열을 구하는 데 중요한 역할을 한다. 선형 재귀 수열은 생성 함수가 유리 함수가 되는 수열로 특징지어진다.

3. 3. 1. 선형대수학을 이용한 해법

선형대수학을 이용하면 초기항을 고유기저로 표현하고, 조르당 표준형을 이용하여 일반항을 구할 수 있다. 수열의 초기항을 다음과 같이 고유기저로 표현한다고 가정하자.

:

\begin{bmatrix}a_0\\\vdots\\a_{d-1}\end{bmatrix} = b_1v_1 + \cdots + b_dv_d

이 경우 조르당 표준형을 이용하여 일반항을 구할 수 있다.

:

\begin{bmatrix}a_n\\\vdots\\a_{n+(d-1)}\end{bmatrix}= C^n\begin{bmatrix}a_0\\\vdots\\a_{d-1}\end{bmatrix}= C^n(b_1v_1 + \cdots + b_dv_d)= \lambda_1^nb_1v_1 + \cdots + \lambda_d^n b_dv_d

만약 행렬이 대각화되지 않으면 해법은 좀 더 복잡해진다.

피보나치 수의 점화식을 행렬로 표현하면 다음과 같다.

:

\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix} \begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}

그러므로 일반항은 다음과 같이 표현된다.

:

\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1} \begin{bmatrix}F_{2}\\F_{1}\end{bmatrix}

이 행렬은 다음과 같이 대각화된다. 특성방정식

x^2 - x - 1 =0

의 두 해를

\alpha, \beta

라고 하면, 이 두 값이 고윳값이므로

:

\begin{bmatrix}1&1\\1&0\end{bmatrix} = \begin{bmatrix}\alpha & \beta\\1&1\end{bmatrix}\begin{bmatrix}\alpha & 0\\0&\beta\end{bmatrix}\begin{bmatrix}\alpha & \beta\\1&1\end{bmatrix}^{-1}

따라서 일반항은 다음과 같이 정리되며, 다항방정식을 이용한 풀이와 동일한 결과를 얻는다.

:

\begin{bmatrix}F_{n+1}\\F_n\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1} \begin{bmatrix}F_{2}\\F_{1}\end{bmatrix} = \begin{bmatrix}\alpha & \beta\\1&1\end{bmatrix}\begin{bmatrix}\alpha^{n-1} & 0\\0&\beta^{n-1}\end{bmatrix}\begin{bmatrix}\alpha & \beta\\1&1\end{bmatrix}^{-1} \begin{bmatrix}F_{2}\\F_{1}\end{bmatrix}

선형 점화식 ''T''_''n'' = ''c''_''d''-1''T''_''n''-1 + ''c''_''d''-2''T''_''n''-2 + … + ''c''₀''T''_''n''-''d''가 주어졌을 때, 특성 다항식의 동반 행렬의 전치는 다음과 같다.

:

\begin{pmatrix}0 & 1 & 0 & \cdots & 0\\0 & 0 & 1 & \cdots & 0\\\vdots & \vdots & \vdots & \ddots & \vdots\\0 & 0 & 0 & \cdots & 1\\

c_0 & -c_1 & -c_2 & \cdots & -c_{d-1}

\end{pmatrix}

이를 ''C''라고 하면, 다음이 성립한다.

:

\begin{pmatrix}a_n\\ \vdots\\ a_{n+(d-1)}\end{pmatrix} = C^n \begin{pmatrix} a_0 \\ \vdots \\ a_{d-1} \end{pmatrix}

고유값 λ₁, ..., λ_''d''에 대응하는 고유 기저 ''v''₁, ..., ''v''_''d''를 정하고, 선형 재귀 수열의 초기값을 고유 벡터의 선형 결합으로 나타내면 다음과 같다.

:

\begin{pmatrix} a_0 \\ \vdots \\ a_{d-1} \end{pmatrix} = b_1v_1 + \cdots + b_dv_d

따라서, 다음을 얻는다.

:

\begin{pmatrix} a_n \\ \vdots \\ a_{n+(d-1)}\end{pmatrix} = C^n \begin{pmatrix} a_0 \\ \vdots \\ a_{d-1}\end{pmatrix} = C^n (b_1v_1 + \cdots + b_dv_d) = \lambda_1^nb_1v_1 + \cdots + \lambda_d^n b_dv_d

3. 3. 2. Z 변환을 이용한 해법

Z 변환은 적분 변환의 일종으로, 어떤 종류의 차분 방정식, 특히 상수 계수 선형 차분 방정식을 푸는 데 사용될 수 있다. Z 변환을 사용하면 대수적 조작이 용이해져 해를 더 쉽게 구할 수 있다. 직접 해를 구하기 어려운 경우에도, 적절한 적분 변환을 선택하면 문제를 쉽게 해결할 수 있는 경우가 있다.

3. 4. 수열의 합을 포함하는 경우

점화식 내에 그 수열의 합이 들어있는 경우, 적절한 변형을 하여 인접한 몇 개의 항을 포함하는 점화식으로 바꾸어 준다.^[3] 예를 들어, 다음과 같은 점화식이 주어졌다고 하자.

:

a_1 + a_2 + a_3 + \cdots + a_n = f(n)a_n

이 경우, 다음과 같이 인접 2항간의 점화식으로 변형할 수 있다.

:

f(n-1)a_{n-1} + a_n = f(n)a_n

수열

\{a_n\}

의

n

째 항까지의 총합을

S_n

이라 하면,

S_n - S_{n-1} = a_n

임을 이용하여 인접 2항간의 점화식으로 변형할 수도 있다.

가변 계수를 갖는 일반적인 1차 비동차 선형 점화 관계의 경우:

:

a_{n+1} = f_n a_n + g_n, \qquad f_n \neq 0,

이를 해결하는 방법은 다음과 같다.^[3]

:

a_{n+1} - f_n a_n = g_n

:

\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{f_n a_n}{\prod_{k=0}^n f_k} = \frac{g_n}{\prod_{k=0}^n f_k}

:

\frac{a_{n+1}}{\prod_{k=0}^n f_k} - \frac{a_n}{\prod_{k=0}^{n-1} f_k} = \frac{g_n}{\prod_{k=0}^n f_k}

여기서 다음과 같이 정의한다.

:

A_n = \frac{a_n}{\prod_{k=0}^{n-1} f_k},

그러면

:

A_{n+1} - A_n = \frac{g_n}{\prod_{k=0}^n f_k}

:

\sum_{m=0}^{n-1}(A_{m+1} - A_m) = A_n - A_0 = \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}

:

\frac{a_n}{\prod_{k=0}^{n-1} f_k} = A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}

:

a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(A_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right)

만약

a_{n+1} = (1 + h f_{nh}) a_n + hg_{nh}

에 이 공식을 적용하고

h \to 0

의 극한을 취하면, 가변 계수를 갖는 1차 선형 미분 방정식에 대한 공식을 얻게 된다. 이 때 합은 적분이 되고, 곱은 적분의 지수 함수가 된다.

3. 5. 비선형 점화식

일반적으로 비선형 점화식은 풀이법이 알려져 있지 않지만, 몇몇 특수한 경우에는 해를 구할 수 있다. 예를 들어 로지스틱 맵과 같이 정의되는 점화식이 있다.

:

x_{n+1} = r x_n (1 - x_n),

여기서

r

은 주어진 상수이다. 이 수열의 동작은

r

값에 따라 크게 달라지지만, 초기 조건

x_0

이 변하더라도 안정적인 특징을 보인다.

다음과 같은 비선형 1차 점화식을 생각해 보자.

:

x_n=f(x_{n-1}).

이 점화식은

x^*

에 충분히 가까운 점에서 고정점

x^*

로 수렴하는, 국소적으로 안정한 상태가 될 수 있다. 이는

x^*

근방에서

f

의 기울기가 절댓값에서 단위보다 작을 때, 즉

:

| f' (x^*) | < 1.

일 때 가능하다.

비선형 점화식은 여러 개의 고정점을 가질 수 있으며, 일부는 국소적으로 안정하고 다른 일부는 불안정할 수 있다. 연속적인 ''f''에 대해 두 개의 인접한 고정점은 모두 국소적으로 안정할 수 없다.

비선형 점화 관계는

k > 1

에 대해 주기

k

의 사이클을 가질 수 있다. 이러한 사이클은 합성 함수

:

g(x) := f \circ f \circ \cdots \circ f(x)

가 국소적으로 안정하다면 안정적이다. (

f

는

k

번 나타난다.)

:

| g' (x^*) | < 1,

여기서

x^*

는 사이클상의 임의의 점이다.

카오스적 점화 관계에서 변수

x

는 경계가 있는 영역에 머물지만, 고정점이나 매력적인 사이클로 수렴하지 않는다. 이 경우 방정식의 모든 고정점 또는 사이클은 불안정하다. 로지스틱 맵, 이진 변환, 텐트 맵 등이 카오스적 점화 관계의 예시이다.

비제차 점화식의 경우, 특수해는 미정 계수법으로 구할 수 있으며, 일반해는 대응하는 제차 점화식의 일반해와 앞서 얻은 특수해의 합으로 구할 수 있다. 비제차 점화식을 푸는 다른 방법으로는 기호 미분이 있다. 예를 들어 다음과 같은 점화식을 생각해 보자.

:

a_{n+1} = a_{n} + 1

''n''을 ''n'' + 1 로 치환하면,

:

a_{n+2} = a_{n+1} + 1

을 얻는다. 원래 점화식에서 변변 빼서 정리하면,

:

a_{n+2} = 2 a_{n+1} - a_{n}

을 얻을 수 있다. 이것은 제차 점화식이므로, 이미 알려진 방법으로 풀 수 있다.

일반적으로, 선형 점화식이

:

a_{n+k} = \lambda_{k-1} a_{n+k-1} + \lambda_{k-2} a_{n+k-2} + \cdots + \lambda_1 a_{n+1} + \lambda_0 a_{n} + p(n)

형태이고, ''P''(''n'')이 ''r''-차 다항식이면, 기호 미분 방법을 ''r'' 회 적용하여 비제차 점화식을 제차 점화식으로 바꿀 수 있다.

3. 5. 1. 역수를 이용하는 경우

p a_n a_{n+1} = q a_n - r a_{n+1}

형태로 주어진 점화식은 양변을

a_n a_{n+1}

으로 나누어 수열 {1/

a_n

}이 선형 점화식이 되도록 변환할 수 있다.^[1] 이 선형 점화식의 일반항을 구하여 문제를 해결한다.

1차 유리 차분 방정식은

w_{t+1} = \tfrac{aw_t+b}{cw_t+d}

형태를 갖는다.^[2] 이 방정식은

w_t

를 다른 변수

x_t

의 비선형 변환으로 표현하여 풀 수 있으며, 이때

x_t

는 선형적으로 변화한다.^[2]

x_t

에 대한 선형 차분 방정식을 표준 방법을 사용하여 풀 수 있다.^[2]

3. 5. 2. 로그를 이용하는 경우

점화식이

a_{n+1} = 4a_n^2

와 같이 주어진 경우 양변에 밑이 2인 로그를 취하면

\log_2 a_{n+1} = 2 \log_2 a_n + 2

와 같이 변형되어 수열

\{\log a_n\}

이 선형 점화식을 가짐을 알 수 있다. 따라서 선형 점화식을 풀면 쉽게 해결할 수 있다.

3. 5. 3. 점화식의 역수를 이용하는 경우

점화식에서

a_{n+1} = \frac{2a_n}{a_n + 2}

와 같이 주어진 경우 양변의 역수를 취하면 수열 {1/

a_n

}이 선형 점화식을 가짐을 알 수 있다. 이 점화식을 풀면 쉽게 일반항을 구할 수 있다.

3. 5. 4. 주기형의 경우

a_{n+1} = - \frac{1}{a_n + 1}, \;a_n \ne -1

과 같이 주어진 점화식은 n에 대한 식으로 표현하기 어렵다. 그러나 몇몇 값을 대입해보면 이 수열은 주기적으로 같은 값이 반복됨을 알 수 있다. 즉,

a, -\frac{1}{a+1}, -\frac{a+1}{a}

이 세 수가 반복되어 나타난다.

4. 점화식의 해법

비선형 1차 점화식 $x_n=f(x_{n-1})$ 은 $x^*$ 근방에서 $f$ 의 기울기 절댓값이 1보다 작을 때, 즉 $| f' (x^*) | < 1$ 일 때 국소적으로 안정하다. 이는 $x^*$ 에 충분히 가까운 점에서 고정점 $x^*$ 로 수렴한다는 의미이다. 비선형 점화식은 여러 개의 고정점을 가질 수 있으며, 일부는 안정하고 다른 일부는 불안정할 수 있다. 연속적인 ''f''에 대해 두 개의 인접한 고정점은 모두 국소적으로 안정할 수 없다.

주기 $k > 1$ 의 사이클은 합성 함수 $g(x) := f \circ f \circ \cdots \circ f(x)$ ( $f$ 는 $k$ 번 나타남)가 $| g' (x^*) | < 1,$ ( $x^*$ 는 사이클상의 임의의 점)을 만족하면 안정적이다. 카오스적 점화 관계에서 변수 $x$ 는 경계가 있는 영역에 머물지만 고정점이나 매력적인 사이클로 수렴하지 않으며, 방정식의 모든 고정점 또는 사이클은 불안정하다. 로지스틱 맵, 이진 변환, 텐트 맵을 참고하라.

1계 점화식 $a_{n}=r a_{n-1}$ 은 초기값 ''a''₀ = 1에 대해 ''a''_''n'' = ''r''^''n''을 해로 가지며, 일반적으로 ''a''₀ = ''k''로 설정하면 일반해 ''a''_''n'' = ''kr''^''n''을 얻는다. 이 점화식의 특성 방정식은 ''t'' − ''r'' = 0이다.

고계 점화식의 해는 ''a''_''n'' = ''r''^''n''이 특성 다항식의 근 ''t'' = ''r''에 대한 점화식의 해라는 사실을 이용하여 구할 수 있다. 예를 들어, $a_{n}=Aa_{n-1}+Ba_{n-2}$ 형태의 점화식은 특성 방정식 ''r''² − ''Ar'' − ''B'' = 0으로 간략화할 수 있다. 이 방정식을 ''r''에 대해 풀면 두 개의 특성근(고유값) λ₁, λ₂를 얻는다.

두 특성근이 서로 다르면 일반해는 $a_n = C\lambda_1^n+D\lambda_2^n$ 이고, 중근이면 $a_n = C\lambda^n+Dn\lambda^n$ 이다. 특성근이 복소수인 경우, 삼각함수를 이용하여 복소수를 사용하지 않는 형태로 나타낼 수 있다.^[11]

2계 점화식의 안정성 조건은 |''A''| < 1 − ''B'' < 2와 동치이며^[12], 이는 일반적인 ''n''-계 점화식에도 적용된다. 즉, 점화식의 해가 안정적이기 위한 필요충분조건은 특성 다항식의 모든 근의 절댓값이 1보다 작은 것이다.

상수항 ''K''를 포함하는 비제차 점화식 $b_{n}=Ab_{n-1}+Bb_{n-2}+K \,$ 는 고정점 $b^{*} = \frac{K}{1-A-B}$ 를 이용하여 제차 점화식 $[b_{n}-b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}]$ 로 변환하여 풀 수 있다.

상태 벡터 ''x'', 전이 행렬 ''A''를 갖는 1차 행렬 계수 차분 방정식 $[x_t - x^*] = A[x_{t-1}-x^*]$ 에서 ''x''가 정상 상태 벡터 ''x''^∗에 점근적으로 수렴하기 위한 필요충분조건은 ''A''의 모든 고유값의 절댓값이 1보다 작은 것이다.

4. 1. 생성 함수를 이용한 해법

생성함수를 이용하여 수열의 일반항을 찾는 것이 가능한 경우가 있다.

a_1 = 0

이고 점화식이

a_{n+1} = 2a_n + 1

과 같이 주어진 수열을 생각해보자. 이 수열을 계수로 갖는 다항식

A(x) = \sum_{n=1}^{\infty} a_n x^n

은 다음 등식을 만족해야 한다.

:

\frac{A(x)}{x} = 2A(x) + \sum_{n=1}^{\infty} x^n = 2A(x) + \frac{x}{1-x}

그러므로

A(x)

를 구할 수 있고 이를 다시 부분분수로 분해하여 무한급수로 표현한다.

:

A(x) = \frac{x^2}{(1-x)(1-2x)} ={x} \left(\frac{1}{1-2x} - \frac{1}{1-x}\right) = \sum (2^{n-1} -1)x^n

a_0 = 1

이고 점화식이

a_{n+1} = 2a_n + n

과 같이 주어진 수열을 생각해보자. 그런데

\frac{d}{dx}\sum x^n = \sum nx^{n-1}

이라는 사실을 이용하여

\sum nx^{n-1} = \frac{d}{dx}\frac{1}{1-x} = \frac{1}{(1-x)^2}

임을 알 수 있으므로, 이 수열을 계수로 갖는 다항식

A(x)

은 다음 등식을 만족해야 함을 알 수 있다.

:

\frac{A(x)-1}{x} = 2A(x) + \frac{x}{(1-x)^2}

마찬가지로 부분분수로 분해하여 무한급수로 표현한다.

:

A(x) = \frac{1-2x+2x^2}{(1-x)^2 (1-2x)} = \frac{-1}{(1-x)^2} + \frac{2}{1-2x} = \sum (2^{n+1} -n -1)x^n

n

번째 피보나치 수를 계수로 갖는 다항식

F(x)

는 정의에 의해 다음을 만족해야 함을 즉시 알 수 있다.

:

\frac{F(x)-x}{x} = F(x) + xF(x)

그러므로 다음을 얻는다.

:

F(x) = \frac{x}{1-x-x^2}

방정식

1-x-x^2 =0

의 두 근을

r_1 , r_2

라고 하면 다음과 같이 부분분수로 분해된다.

:

F(x) = \frac{1}{r_1 - r_2} \left(\frac{1}{1-xr_1} - \frac{1}{1-xr_2}\right)

이것을 무한급수로 표현하면 일반항을 얻을 수 있다.

4. 2. 일반적인 동차 선형 점화식의 해법

일부 동차 선형 점화식은 일반화된 초기하 급수를 사용하여 풀 수 있다. 이들의 특수한 경우는 직교 다항식 및 많은 특수 함수에 대한 점화식을 유도한다. 예를 들어,

:

J_{n+1}=\frac{2n}{z}J_n-J_{n-1}

의 해는

:

J_n=J_n(z),

인 베셀 함수로 주어지고,

:

(b-n)M_{n-1} +(2n-b+z)M_n - nM_{n+1}=0

의 해는

:

M_n=M(n,b;z)

인 합류형 초기하 급수로 주어진다.

4. 3. 1차 유리 차분 방정식의 해법

1차 유리 차분 방정식은

w_{t+1} = \tfrac{aw_t+b}{cw_t+d}

형태를 갖는다. 이러한 방정식은

w_t

를 다른 변수

x_t

의 비선형 변환으로 표현하여 풀 수 있는데, 이때

x_t

는 선형적으로 변화한다. 그런 다음 표준 방법을 사용하여

x_t

에 대한 선형 차분 방정식을 풀 수 있다. 자세한 내용은 유리 차분 방정식을 참고하면 된다.

5. 점화식의 응용

점화식은 여러 분야에서 활용된다.

'''수학적 생물학'''

피보나치 수는 한때 토끼 개체 수 증가를 모델링하는 데 사용되었다. 로지스틱 맵은 개체 수 증가를 직접 모델링하거나, 개체 수 역학에 대한 더 상세한 모델의 시작점으로 사용된다.

'''컴퓨터 과학'''

알고리즘 분석에서 점화식은 근본적으로 중요하다.^[4]^[5] 알고리즘이 문제를 더 작은 하위 문제로 분해하도록 설계된다면(분할 정복), 그 실행 시간은 점화식으로 설명된다.

'''디지털 신호 처리'''

디지털 신호 처리에서 점화식은 특정 시점의 출력이 새로운 시점의 입력이 되는 시스템의 피드백을 모델링할 수 있다. 따라서 무한 임펄스 응답(IIR) 디지털 필터에서 발생한다.

'''경제학'''

시계열 분석 및 동시 방정식 모형에서 점화식이 사용된다. 점화 관계, 특히 선형 점화 관계는 이론 경제학 및 실증 경제학에서 광범위하게 사용된다.^[6]^[7]

5. 1. 수학적 생물학

피보나치 수는 한때 토끼 개체수의 증가를 모델링하는 데 사용되었다. 로지스틱 맵은 개체수 증가를 직접 모델링하거나, 개체수 역학에 대한 보다 상세한 모델의 시작점으로 사용된다.

숙주-기생충 상호 작용에 대한 니콜슨-베일리 모델은 다음과 같이 주어진다.

:

N_{t+1} = \lambda N_t e^{-aP_t}

:

P_{t+1} = N_t(1-e^{-aP_t}),

여기서

N_t

는 시간

t

에서 숙주를 나타내고,

P_t

는 기생충을 나타낸다.

적분차분 방정식은 공간 생태학에 중요한 재귀 관계의 한 형태이다. 이것들과 다른 차분 방정식들은 특히 단대성 개체군을 모델링하는 데 적합하다.

5. 2. 컴퓨터 과학

알고리즘 분석에서 점화식은 근본적으로 중요하다.^[4]^[5] 알고리즘이 문제를 더 작은 하위 문제로 분해하도록 설계된다면(분할 정복), 그 실행 시간은 점화식으로 설명된다.

n

개의 원소를 가진 정렬된 벡터에서, 최악의 경우 특정 원소를 찾는 데 걸리는 시간을 나타내는 간단한 예가 있다.

단순한 알고리즘은 왼쪽에서 오른쪽으로 한 번에 하나의 원소를 검색한다. 최악의 시나리오는 원하는 원소가 마지막 원소일 때이므로, 비교 횟수는

n

이다.

더 나은 알고리즘은 이진 탐색이다. 이 알고리즘은 정렬된 벡터가 필요하다. 먼저 원소가 벡터의 중앙에 있는지 확인한다. 그렇지 않다면, 중앙 원소가 찾는 원소보다 큰지 작은지 확인한다. 이 시점에서 벡터의 절반을 버릴 수 있으며, 알고리즘을 나머지 절반에 대해 다시 실행할 수 있다. 비교 횟수는 다음과 같다.

:

c_1=1

:

c_n=1+c_{n/2}

시간 복잡도는

O(\log_2(n))

이다.

5. 3. 디지털 신호 처리

디지털 신호 처리에서 점화식은 특정 시점의 출력이 새로운 시점의 입력이 되는 시스템의 피드백을 모델링할 수 있다. 따라서 무한 임펄스 응답(IIR) 디지털 필터에서 발생한다.

예를 들어, 지연

T

를 갖는 "피드포워드" IIR 콤 필터의 방정식은 다음과 같다.

:

y_t = (1 - \alpha) x_t + \alpha y_{t - T},

여기서

x_t

는 시간

t

에서의 입력,

y_t

는 시간

t

에서의 출력이며,

\alpha

는 지연된 신호가 출력에 얼마나 피드백되는지를 제어한다. 이로부터 다음을 알 수 있다.

:

y_t = (1 - \alpha) x_t + \alpha ((1-\alpha) x_{t-T} + \alpha y_{t - 2T})

:

y_t = (1 - \alpha) x_t + (\alpha-\alpha^2) x_{t-T}  + \alpha^2 y_{t - 2T}

5. 4. 경제학

시계열 분석 및 동시 방정식 모형 참조

점화 관계, 특히 선형 점화 관계는 이론 경제학 및 실증 경제학에서 광범위하게 사용된다.^[6]^[7] 특히 거시 경제학에서는 일부 경제 주체의 행동이 지연 변수에 의존하는 경제의 다양한 광범위한 부문(금융 부문, 재화 부문, 노동 시장 등)의 모형을 개발할 수 있다. 그러면 이 모형은 다른 변수의 과거 및 현재 값에 따라 주요 변수(예: 이자율, 실질 GDP 등)의 현재 값을 구하는 데 사용된다.

점화식, 특히 선형 점화식은 이론 경제학과 실증 경제학 모두에서 널리 사용된다.^[13] 특히 거시 경제학에서는 에이전트의 활동이 지연 변수에 의존하는 경제의 다양한 광범위한 분야(금융 부문, 상품 부문, 노동 시장 등)의 모델이 전개되고 있다. 따라서 이 모델은 외생 변수나 지연 외생 변수를 사용하여 (금리나 실질 GDP 등의) 핵심 변수의 현재 값에 관해 풀릴 필요가 있다.

6. 점화식과 미분 방정식의 관계

상미분 방정식을 수치적으로 풀 때, 전형적으로 점화식(점화 관계)이 발생한다.^[1] 예를 들어, 초깃값 문제

: $y'(t) = f(t,y(t)),\quad y(t_0)=y_0$

를 오일러 방법으로 풀 때, 시점 간격을 ''h''라고 하면,

: $y_0=y(t_0),\quad y_1=y(t_0+h),\quad y_2=y(t_0+2h),\quad \ldots$

의 값을 다음 점화식으로부터 계산한다.^[1]

: $y_{n+1} = y_n + hf(t_n,y_n)$

1계 선형 방정식계는 이산화에 제시된 방법 등을 이용하여 해석적으로 이산화할 수 있다.^[1]

시간 척도 미분 적분학을 참조하면, 차분 방정식 이론과 미분 방정식 이론의 통합에 대해 알 수 있다.

참조

_[1] 서적 Basic Algebra 2 ""
_[2] 서적 Partial difference equations https://books.google[...] CRC Press
_[3] 웹사이트 Archived copy http://faculty.pccu.[...] 2010-10-19
_[4] 서적 Introduction to Algorithms MIT Press
_[5] 서적 An Introduction to the Analysis of Algorithms Addison-Wesley
_[6] 서적 Recursive Methods in Economic Dynamics https://books.google[...] Harvard University Press
_[7] 서적 Recursive Macroeconomic Theory https://archive.org/[...] MIT Press
_[8] 서적 The Fibonacci Sequence and Beyond CreateSpace
_[9] 웹사이트 Discussion on s http://www.numerican[...]
_[10] 서적 Partial difference equations https://books.google[...] CRC Press
_[11] 서적 Fundamental Methods of Mathematical Economics McGraw-Hill
_[12] 간행물 On the asymptotic stability of a class of linear difference equations 1996-02
_[13] 서적 Dynamic Macroeconomic Theory Harvard University Press

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com