Recurrence relation

Original article: wikipedia:Recurrence relation

"Difference equation" redirects here. It is not to be confused with differential equation.

수학에서, 재귀 관계(recurrence relation)는 하나 이상의 초기 항이 주어지면 값의 수열(sequence) 또는 다차원 배열을 재귀적으로(recursively) 정의하는 방정식(equation)입니다: 수열 또는 배열의 각 다음 항은 이전의 항의 함수(function)로써 정의됩니다.

용어 차이 방정식(difference equation)은 때때로 (그리고 이 기사의 목적을 위해) 재귀 관계의 특정 유형을 나타냅니다. 어쨌든, "차이 방정식"은 임의의 재귀 관계를 나타내기 위해서 자주 사용됩니다.

Definition

재귀 관계는 수열(sequence)의 각 원소를 이전 원소의 함수로 표현하는 방정식입니다. 보다 정확하게, 오직 바로 앞의 원소가 포함되는 경우에서, 재귀 관계는 다음 형식을 가집니다:

$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$에 대해, 이것은, 초기 값으로 불리는, 그것의 초기 원소로 $u_{0}$을 갖는 고유한 수열을 정의합니다.

인덱스 1 이상의 항에서 시작하는 수열을 제공하는 것에 대해 정의를 수정하는 것은 쉽습니다.

이것은 일차의 재귀 관계를 정의합니다. 차수 k의 재귀 관계는 다음 형식을 가집니다:

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

여기서 $\varphi :\mathbb {N} \times X^{k}\to X$는 수열의 k 연속적인 원소를 포함하는 함수입니다. 이 경우에서, k 초기 값이 수열을 정의하는 것에 대해 요구됩니다.

Examples

Factorial

팩토리얼(factorial)은 다음 재귀 관계

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

및 초기 조건에 의해 정의됩니다:

$0!=1.$

Logistic map

재귀 관계의 예제는 주어진 상수 r을 갖는 로지스틱 맵(logistic map)입니다:

$x_{n+1}=rx_{n}(1-x_{n}),$

초기 항 x₀가 주어지면 각 후속의 항은 이 관계에 의해 결정됩니다.

재귀 관계를 푸는 것은 닫힌-형식 해(closed-form solution): n의 비-재귀 함수를 얻는 것을 의미합니다.

Fibonacci numbers

피보나치 숫자(Fibonacci number)에 의해 만족되는 차수 2의 재귀는 상수 계수를 갖는 동차 선형 재귀(linear recurrence) 관계의 원형입니다 (아래를 참조하십시오). 피보나치 수열은 다음 초기 조건(initial condition) (씨앗 값)과 함께

$F_{0}=0$

$F_{1}=1.$

다음 재귀 관계에 의해 정의됩니다:

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

명시적으로, 재귀는 다음 방정식들을 산출합니다:

$F_{2}=F_{1}+F_{0}$

$F_{3}=F_{2}+F_{1}$

$F_{4}=F_{3}+F_{2}$.

우리는 다음과 같이 시작하는 피보나치 숫자의 수열을 얻습니다:

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

재귀는 특성 다항식 t² = t + 1의 두 근의 거듭제곱을 포함하는, 비네의 공식(Binet's formula)을 산출하는 아래에 설명된 방법으로 해결될 수 있습니다; 수열의 생성 함수(generating function)는 다음 유리 함수(rational function)입니다:

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

Binomial coefficients

다차원 재귀 관계의 간단한 예제는 이항 계수(binomial coefficient) ${\tbinom {n}{k}}$에 의해 주어지며, 이것은 n 원소의 집합에서 k원소를 선택하는 방법의 숫자를 셉니다. 그들은 기본 경우 ${\tbinom {n}{0}}={\tbinom {n}{n}}=1$와 함께, 다음 재귀 관계에 의해 계산될 수 있습니다:

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

모든 이항 계수의 값을 계산하기 위해서 이 공식을 사용하는 것은 파스칼의 삼각형(Pascal's triangle)이라고 불리는 무한 배열을 생성합니다. 같은 값은 재귀가 아닌 다른 공식으로 역시 직접 계산될 수 있지만, 그것은 계산에 대한 단지 덧셈이 아니고 곱셈을 요구합니다: ${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$

Relationship to difference equations narrowly defined

실수의 순서화 수열(sequence) $\left\{a_{n}\right\}_{n=1}^{\infty }$이 주어지면: 일차 차이(first difference) $\Delta (a_{n})$는 다음으로 정의됩니다:

$\Delta (a_{n})=a_{n+1}-a_{n}$

이차 차이(second difference) $\Delta ^{2}(a_{n})$는 다음으로 정의됩니다:

$\Delta ^{2}(a_{n})=\Delta (a_{n+1})-\Delta (a_{n})$,

이것은 다음으로 간단히 될 수 있습니다:

$\Delta ^{2}(a_{n})=a_{n+2}-2a_{n+1}+a_{n}$

보다 일반적으로: $\Delta ^{k}(a_{n})$으로 쓰이는 수열 a_n의 k^차 차이는 다음으로 재귀적으로 정의됩니다:

$\Delta ^{k}(a_{n})=\Delta ^{k-1}(a_{n+1})-\Delta ^{k-1}(a_{n})=\sum _{t=0}^{k}{\binom {k}{t}}(-1)^{t}a_{n+k-t}$

(수열과 그의 차이는 이항 변환(binomial transform)에 의해 관계됩니다.) 차이 방정식(difference equation)의 보다 제한적인 정의는 a_n과 k^차 차이로 구성된 방정식입니다. (널리 사용되는 더 넓은 정의는 "차이 방정식"을 "재귀 관계"와 동의어로 취급합니다. 예를 들어 유리 차이 방정식(rational difference equation) 및 행렬 차이 방정식(matrix difference equation)을 참조하십시오.)

실제로, 그것은 다음으로 쉽게 보입니다,

$a_{n+k}={k \choose 0}a_{n}+{k \choose 1}\Delta (a_{n})+\cdots +{k \choose k}\Delta ^{k}(a_{n})$

따라서, 차이 방정식은 a_n, a_n-1, a_n-2 등등 (또는 동등하게 a_n, a_n+1, a_n+2 등등)을 포함하는 방정식으로 정의될 수 있습니다.

차이 방정식은 재귀의 매우 공통적인 형식이므로, 일부 저자는 두 용어를 서로 교환-가능하게 사용합니다. 예를 들어, 차이 방정식

$3\Delta ^{2}(a_{n})+2\Delta (a_{n})+7a_{n}=0$

은 다음 재귀 관계와 동등합니다:

$3a_{n+2}=4a_{n+1}-8a_{n}$.

따라서 우리는 많은 재귀 관계를 차이 방정식으로 다시-표현하고, 그런-다음 보통의 미분 방정식(ordinary differential equations)을 푸는 방법과 유사하게, 차이 방정식을 풂으로써 해결할 수 있습니다. 어쨌든, 아커만 숫자(Ackermann number)는 차이 방정식에 매핑되지 않는 재귀 관계의 예제이며, 미분 방정식에 대한 해의 훨씬 적은 점이 있습니다.

미분 방정식(differential equations)의 이론과 함께 차이 방정식의 이론의 통합에 대해 시간 스케일 미적분학(time scale calculus)을 참조하십시오.

합계 방정식(Summation equation)은 미분 방정식과 관련된 적분 방정식(integral equation)으로 차이 방정식과 관련됩니다.

From sequences to grids

단일-변수 또는 일-차원 재귀 관계는 수열 (즉, 일-차원 격자에 정의된 함수)에 대한 것입니다. 여러-변수 또는 n-차원 재귀 관계는 n-차원 격자에 대한 것입니다. n-격자에 정의된 함수는 부분 차이 방정식(partial difference equations)과 함께 역시 연구될 수 있습니다.

Solving

Solving homogeneous linear recurrence relations with constant coefficients

Main articles: Constant-recursive sequence and Linear difference equation

Roots of the characteristic polynomial

상수 계수를 갖는 차수-d 동차 선형 재귀는 다음과 같은 형식의 방정식입니다:

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},$

여기서 (모든 i에 대해) d 계수 c_i는 상수이고, $c_{d}\neq 0$입니다.

상수-재귀적 수열(constant-recursive sequence)은 이 형식의 재귀를 만족시키는 수열입니다. 이 재귀에 대한 해에 대해 d 자유도(degrees of freedom)가 있습니다. 즉, 초기 값 $a_{0},\dots ,a_{d-1}$은 임의의 값으로 취할 수 있지만 그런-다음 재귀는 고유하게 수열을 결정합니다.

같은 계수는 특성 다항식(characteristic polynomial) (역시 "보조 다항식")을 산출합니다:

$p(t)=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}$

그의 d 근은 재귀를 만족시키는 수열을 찾아-내고 이해하는 것에 중대한 역할을 합니다. 만약 근 r₁, r₂, ...가 모두 구별되면, 재귀에 대한 각 해는 다음 형식을 취합니다:

$a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},$

여기서 계수 k_i는 재귀의 초기 조건에 맞추기 위해 결정됩니다. 같은 근이 여러 번 발생하면, 같은 근의 두 번째 및 이후 발생에 해당하는 이 수식에서 항은 n의 거듭제곱을 증가함으로써 곱해집니다. 예를 들어, 만약 특성 다항식이, 세 번 발생하는 같은 근 r을 갖는, (x−r)³으로 인수화될 수 있으면, 해는 다음 형식을 취해야 합니다:

$a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.$

피보나치 숫자(Fibonacci number)뿐만 아니라, 다른 상수-재귀적 수열은 뤼카 숫자(Lucas number)와 뤼카 수열(Lucas sequence), 야콥스탈 숫자(Jacobsthal number), 펠 숫자(Pell number) 및 보다 일반적으로 펠의 방정식(Pell's equation)에 대한 해를 포함합니다.

차수 1에 대해, 재귀

$a_{n}=ra_{n-1}$

는 a₀ = 1을 갖는 해 a_n = rⁿ를 가지고 보다 일반적인 해는 a₀ = k을 갖는 a_n = krⁿ입니다. 영과 같게 되는 특성 다항식 (특성 방정식(characteristic equation))은 단순히 t − r = 0입니다.

고차원의 그러한 재귀 관계에 대한 해는 시스템적인 방법으로 발견되며, 종종 t = r이 특성 다항식의 근일 때 a_n = rⁿ이 정확하게 재귀에 대해 해라는 사실을 사용합니다. 이것은 직접적으로 또는 생성 함수(generating function) (형식적 거듭제곱 급수(formal power series)) 또는 행렬을 사용하여 접근될 수 있습니다.

다음 형식의 재귀 관계, 예를 들어, 생각해 보십시오:

$a_{n}=Aa_{n-1}+Ba_{n-2}.$

언제 그것이 a_n = rⁿ과 같은 일반적인 형식의 해를 가집니까? 재귀 관계에서 이 추측 (가설 풀이(ansatz))을 치환하면, 우리는 다음 식

$r^{n}=Ar^{n-1}+Br^{n-2}$

은 모든 n > 1에 대해 반드시 참임을 발견합니다.

rⁿ⁻²를 통해 나누면, 우리는 모든 이들 방정식은 같은 것으로 줄어드는 것을 얻습니다:

$r^{2}=Ar+B,$

$r^{2}-Ar-B=0,$

이것은 재귀 관계의 특성 방정식입니다. 두 근 λ₁, λ₂를 얻기 위한 r에 대해 풀면: 이들 근은 특성 방정식의 특성 근(characteristic root) 또는 고윳값(eigenvalues)으로 알려져 있습니다. 다른 해는 근의 본성에 따라 얻습니다: 만약 이들 근이 구별되면, 우리는 다음과 같은 일반 해를 가집니다:

$a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}$

반면에 만약 그들이 동일하면 (A² + 4B = 0일 때), 우리는 다음을 가집니다:

$a_{n}=C\lambda ^{n}+Dn\lambda ^{n}$

이것이 가장 일반적인 해입니다; 두 상수 C와 D는 특정 해를 생성하기 위해 두 개의 주어진 초기 조건 a₀와 a₁을 기반으로 선택됩니다.

복소수 고윳값의 경우에서 (이것은 해 매개변수 C와 D에 대해 복소수 값을 역시 야기합니다), 복소수의 사용은 삼각법 형식에서 해를 다시-작성함으로써 제거될 수 있습니다. 이 경우에서 우리는 $\lambda _{1},\lambda _{2}=\alpha \pm \beta i$와 같이 고윳값을 쓸 수 있습니다. 그런 다음 그것은 다음 식

$a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}$

이 다음 식

$a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\delta )$

으로 다시-쓸 수 있다는 것을 보여줄 수 있으며, 여기서

${\begin{array}{lcl}M={\sqrt {\alpha ^{2}+\beta ^{2}}}&\cos(\theta )={\tfrac {\alpha }{M}}&\sin(\theta )={\tfrac {\beta }{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2}}}&\cos(\delta )={\tfrac {E}{G}}&\sin(\delta )={\tfrac {F}{G}}\end{array}}$

여기서 E와 F (또는 동등하게, G와 δ)는 초기 조건에 의존하는 실수 상수입니다. 다음을 사용하면

$\lambda _{1}+\lambda _{2}=2\alpha =A,$

$\lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,$

우리는 위에서 주어진 해를 다음과 같이 단순화할 수 있습니다:

$a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),$

여기서 a₁와 a₂는 초기 조건이고

${\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}-Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{aligned}}$

이런 방법에서 λ₁와 λ₂에 대해 풀 필요가 없습니다.

모든 경우에서—실수 구별되는 고윳값, 실수 중복되는 고윳값, 및 복소수 켤레 고윳값—방정식이 안정적(stable)인 것 (즉, 변수 a는 고정된 값 [구체적으로, 영]에 대해 수렴하는 것)과 양쪽 고윳값이 절댓값(absolute value)에서 일보다 작은 것은 필요충분 조건입니다. 이 이-차 경우에서, 고윳값에 대한 이 조건은 |A| < 1 − B < 2와 동등하게 보일 수 있으며, 이것은 |B| < 1 및 |A| < 1 − B와 동등합니다.

위의 예제에서 방정식은 동차(homogeneous)였고, 그것에서 상수항은 없습니다. 만약 우리가 상수항 K를 갖는 다음과 같은 비-동차 재귀로 시작하면

$b_{n}=Ab_{n-1}+Bb_{n-2}+K$,

이것은 다음으로 동차 형식으로 변환될 수 있습니다: 정상 상태(steady state)는 b_n = b_n−1 = b_n−2 = b*을 설정하여

$b^{*}={\frac {K}{1-A-B}}$

을 얻음으로써 발견될 수 있습니다.

그런-다음 비-동차 재귀는 다음으로 재귀 형식으로 다시-쓸 수 있습니다:

$[b_{n}-b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}],$

이것은 위에서와 같이 구할 수 있습니다.

이-차 경우에 대해 고윳값의 관점에서 위에서 언급된 안정성 조건은 일반적인 n^번째-차수 경우에 대해 유효하게 남습니다: 방정식이 안정적인 것과 특성 방정식의 모든 고윳값이 절댓값에서 일보다 작은 것과 필요충분 조건입니다.

차수 d의 상수 계수를 갖는 동차 선형 재귀 관계가 주어지면, p(t)를 각 c_i가 원래 재귀 관계 각 c_i에 해당하는 것을 만족하는 (위의 일반적인 형태를 참조하십시오) 특성 다항식(characteristic polynomial) (역시 "보조 다항식")

$t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}=0$

이라고 놓습니다. λ는 중복도(multiplicity) r을 가지는 p(t)의 근이라고 가정합니다. 이것은 (t−λ)^r가 p(t)를 나누는 것을 말합니다. 다음 두 가지 속성은 유지됩니다:

1. r 수열 $\lambda ^{n},n\lambda ^{n},n^{2}\lambda ^{n},\dots ,n^{r-1}\lambda ^{n}$의 각각은 재귀 관계를 만족시킵니다.
2. 재귀 관계를 만족시키는 임의의 수열은 λ가 p(t)의 모든 구별되는 근에 걸쳐 변할 때 부분 1에서 구성되는 해의 선형 조합으로 고유하게 쓸 수 있습니다.

이 정리의 결과로, 상수 계수를 갖는 동차 선형 재귀 관계는 다음 방식으로 해결될 수 있습니다:

1. 특성 방정식 p(t)를 찾습니다.

2. 중복도를 세어서 p(t)의 근을 찾습니다.

3. 미지수 계수 b_i와 함께 (위의 정리에서 보이는 것처럼 중복도를 세어서) 모든 근의 선형 조합으로 a_n을 씁니다.

$a_{n}=\left(b_{1}\lambda _{1}^{n}+b_{2}n\lambda _{1}^{n}+b_{3}n^{2}\lambda _{1}^{n}+\cdots +b_{r}n^{r-1}\lambda _{1}^{n}\right)+\cdots +\left(b_{d-q+1}\lambda _{*}^{n}+\cdots +b_{d}n^{q-1}\lambda _{*}^{n}\right)$

이것은 원래 재귀 관계에 대한 일반적인 해입니다. (q는 λ_*의 중복도입니다)

4. 부분 3으로부터 각 $a_{0},a_{1},\dots ,a_{d}$와 (n = 0, ..., d에서 반복 관계의 일반 해를 대입해서) 원래 재귀 관계로부터 알려진 값 $a_{0},a_{1},\dots ,a_{d}$를 같게 합니다. 어쨌든, 사용된 원래 재귀 관계로부터 값 a_n은 보통 연속적이지 않아도 됩니다: 예외적인 경우를 제외하고, 그들의 단지 d가 필요됩니다 (즉, 차수 3의 원래 동차 선형 재귀 관계에 대해, 우리는 값 a₀, a₁, a₄를 사용할 수 있습니다). 이 과정은 d 미지수를 갖는 d 방정식의 선형 시스템을 생성할 것입니다. 일반 해의 미지수 계수 $b_{1},b_{2},\dots ,b_{d}$에 대해 이들 방정식을 해결하는 것과 이들 값을 일반 해에 다시 대입하는 것은 원래 재귀 관계의 초기 조건 (마찬가지로 원래 재귀 관계의 후속의 값 $a_{0},a_{1},a_{2},\dots$)에 맞는 원래 재귀 관계에 대한 특별한 해를 생성할 것입니다.

선형 미분 방정식(differential equations)을 푸는 방법은 위의 방법과 유사합니다—상수 계수를 갖는 선형 미분 방정식에 대해 "지능형 추측"(가설-풀이(ansatz))은 e^λx이며, 여기서 λ는 추측을 미분 방정식에 치환함으로써 결정됩니다.

이것은 우연의 일치가 아닙니다. 선형 미분 방정식에 대한 해의 테일러 급수(Taylor series)를 고려하면 다음과 같습니다:

$\sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}$

이것은 급수의 계수가 점 a에서 평가된 f(x)의 n^번째 도함수에 의해 주어진다는 것임을 알 수 있습니다. 미분 방정식은 이들 계수와 관련된 선형 차이 방정식을 제공합니다.

이 동치는 선형 미분 방정식의 거듭제곱 급수 해에서 계수에 대해 재귀 관계를 신속하게 풀기 위해 사용될 수 있습니다.

(영에서 첫 번째 항을 곱하는 다항식이 비-영인 방정식에 대해) 엄지의 규칙은 다음과 같습니다:

$y^{[k]}\to f[n+k]$

그리고 보다 일반적으로

$x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f[n+k-m]$

예제: 방정식의 테일러 급수 계수에 대해 재귀 관계:

$(x^{2}+3x-4)y^{[3]}-(3x+1)y^{[2]}+2y=0$

는 다음으로 주어집니다:

$n(n-1)f[n+1]+3nf[n+2]-4f[n+3]-3nf[n+1]-f[n+2]+2f[n]=0$

또는

$-4f[n+3]+2nf[n+2]+n(n-4)f[n+1]+2f[n]=0.$

이 예제는 통상적으로 미분 방정식 수업에서 가르치는 거듭제곱 급수 해 방법을 사용하여 일반적으로 해결된 문제가 훨씬 쉽게 해결될 수 있는 방법을 보여줍니다.

예제: 미분 방정식

$ay''+by'+cy=0$

은 다음 해를 가집니다:

$y=e^{ax}.$

미분 방정식을 테일러 계수의 차이 방정식으로의 변환은 다음입니다:

$af[n+2]+bf[n+1]+cf[n]=0.$

0에서 평가된 e^ax의 n번째 도함수가 aⁿ임을 쉽게 알 수 있습니다.

Solving via linear algebra

차수 n의 선형적으로 재귀적 수열 y

$y_{n+k}-c_{n-1}y_{n-1+k}-c_{n-2}y_{n-2+k}+\cdots -c_{0}y_{k}=0$

는 다음과 동일합니다:

$y_{n}=c_{n-1}y_{n-1}+c_{n-2}y_{n-2}+\cdots +c_{0}y_{0}.$

종류 $y_{n-k}=y_{n-k}$의 n−1 항등식으로 확장되면, n-번째 차수 방정식은 n 일-차 선형 방정식의 행렬 차이 방정식(matrix difference equation) 시스템으로 변환됩니다:

${\vec {y}}_{n}={\begin{bmatrix}y_{n}\\y_{n-1}\\\vdots \\\vdots \\y_{1}\end{bmatrix}}={\begin{bmatrix}c_{n-1}&c_{n-2}&\cdots &\cdots &c_{0}\\1&0&\cdots &\cdots &0\\0&\ddots &\ddots &&\vdots \\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &0&1&0\end{bmatrix}}{\begin{bmatrix}y_{n-1}\\y_{n-2}\\\vdots \\\vdots \\y_{0}\end{bmatrix}}=C\ {\vec {y}}_{n-1}=C^{n}{\vec {y}}_{0}.$

벡터 ${\vec {y}}_{n}$은 초기 상태 벡터, $y_{0}$에 대한 동반 행렬(companion matrix), C의 n 적용에 의해 계산될 수 있음을 관찰합니다. 그것에 의하여, 찾은 수열 y의 n-번째 엔트리는 ${\vec {y}}_{n},y_{n}={\vec {y}}_{n}[n]$의 최상위 성분입니다.

${\vec {y}}_{n}=C^{n}\,{\vec {y}}_{0}=c_{1}\,\lambda _{1}^{n}\,{\vec {e}}_{1}+c_{2}\,\lambda _{2}^{n}\,{\vec {e}}_{2}+\cdots +c_{n}\,\lambda _{n}^{n}\,{\vec {e}}_{n}$을 고윳값, $\lambda _{1},\lambda _{2},\ldots ,\lambda _{n}$, 및 고유벡터, ${\vec {e}}_{1},{\vec {e}}_{2},\ldots ,{\vec {e}}_{n}$로 분해하는, 고윳값-분해(Eigendecomposition)는 ${\vec {y}}_{n}$을 계산하기 위해 사용됩니다. 시스템 C는 모든 각 고유 벡터, e를 단순히 그의 성분을 λ배 스케일링함으로써 시간-이동시킨다는 중요한 사실 덕분에,

$C\,{\vec {e}}_{i}=\lambda _{i}{\vec {e}}_{i}=C{\begin{bmatrix}e_{i,n}\\e_{i,n-1}\\\vdots \\e_{i,1}\end{bmatrix}}={\begin{bmatrix}\lambda _{i}\,e_{i,n}\\\lambda _{i}\,e_{i,n-1}\\\vdots \\\lambda _{i}\,e_{i,1}\end{bmatrix}}$

즉, 고유 벡터, e의 시간-이동된 버전은 λ배 더 큰 성분을 가지며, 고유-벡터 성분은 λ의 거듭제곱, ${\vec {e}}_{i}={\begin{bmatrix}\lambda _{i}^{n-1}&\cdots &\lambda _{i}^{2}&\lambda _{i}&1\end{bmatrix}}^{T}$이고, 따라서 반복되는 동차 선형 방정식 해는 지수 함수의 조합, ${\vec {y}}_{n}=\sum _{1}^{n}{c_{i}\,\lambda _{i}^{n}\,{\vec {e}}_{i}}$입니다. 성분 $c_{i}$는 초기 조건에서 결정될 수 있습니다:

${\vec {y}}_{0}={\begin{bmatrix}y_{0}\\y_{-1}\\\vdots \\y_{-n+1}\end{bmatrix}}=\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{0}\,{\vec {e}}_{i}}={\begin{bmatrix}{\vec {e}}_{1}&{\vec {e}}_{2}&\cdots &{\vec {e}}_{n}\end{bmatrix}}\,{\begin{bmatrix}c_{1}\\c_{2}\\\cdots \\c_{n}\end{bmatrix}}=E\,{\begin{bmatrix}c_{1}\\c_{2}\\\cdots \\c_{n}\end{bmatrix}}$

계수에 대해 풀면,

${\begin{bmatrix}c_{1}\\c_{2}\\\cdots \\c_{n}\end{bmatrix}}=E^{-1}{\vec {y}}_{0}={\begin{bmatrix}\lambda _{1}^{n-1}&\lambda _{2}^{n-1}&\cdots &\lambda _{n}^{n-1}\\\vdots &\vdots &\ddots &\vdots \\\lambda _{1}&\lambda _{2}&\cdots &\lambda _{n}\\1&1&\cdots &1\end{bmatrix}}^{-1}\,{\begin{bmatrix}y_{0}\\y_{-1}\\\vdots \\y_{-n+1}\end{bmatrix}}.$

이것은, 필연적으로 초기 조건이 아닌, 임의의 경계 조건 $\underbrace {y_{a},y_{b},\ldots } _{\text{n}}$과 함께 역시 작동합니다,

${\begin{bmatrix}y_{a}\\y_{b}\\\vdots \end{bmatrix}}={\begin{bmatrix}{\vec {y}}_{a}[n]\\{\vec {y}}_{b}[n]\\\vdots \end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{a}\,{\vec {e}}_{i}[n]}\\\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{b}\,{\vec {e}}_{i}[n]}\\\vdots \end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{a}\,\lambda _{i}^{n-1}}\\\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{b}\,\lambda _{i}^{n-1}}\\\vdots \end{bmatrix}}=$

$={\begin{bmatrix}\sum {c_{i}\,\lambda _{i}^{a+n-1}}\\\sum {c_{i}\,\lambda _{i}^{b+n-1}}\\\vdots \end{bmatrix}}={\begin{bmatrix}\lambda _{1}^{a+n-1}&\lambda _{2}^{a+n-1}&\cdots &\lambda _{n}^{a+n-1}\\\lambda _{1}^{b+n-1}&\lambda _{2}^{b+n-1}&\cdots &\lambda _{n}^{b+n-1}\\\vdots &\vdots &\ddots &\vdots \end{bmatrix}}\,{\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{n}\end{bmatrix}}.$

이 설명은 실제로 위의 일반적인 방법과 다르지 않으며, 어쨌든, 그것은 보다 간결합니다. 그것은 역시 다음과 같은 상황에 대해 잘 작동합니다:

${\begin{cases}a_{n}=a_{n-1}-b_{n-1}\\b_{n}=2a_{n-1}+b_{n-1}.\end{cases}}$

여기서 여러 연결된 재귀가 있습니다.

Solving with z-transforms

특정 차분 방정식 - 특히 선형 상수 계수(linear constant coefficient) 차이 방정식은 z-변환(z-transform)을 사용하여 풀 수 있습니다. z-변환은 보다 편리한 대수적 조작과 보다 간단한 해로 이어지는 적분 변환(integral transform)의 클래스입니다. 직접 해를 얻는 것이 거의 불가능한 경우도 있지만, 신중하게 선택된 적분 변환을 통해 문제를 해결하는 것은 간단합니다.

Solving non-homogeneous linear recurrence relations with constant coefficients

만약 재귀가 비-동차이면, 특정 해는 미결정 계수의 방법(method of undetermined coefficients)으로 찾을 수 있고 그 해는 동차 및 특정 해의 합입니다. 비-동차 재귀를 푸는 또 다른 방법은 기호적 미분화의 방법입니다. 예를 들어, 다음 재귀를 생각해 보십시오:

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

이것은 비-동차 재귀입니다. 만약 우리가 n ↦ n+1로 대체하면, 우리는 다음 재귀를 얻습니다:

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

이 방정식으로부터 원래 방정식을 빼면 다음을 산출합니다:

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

또는 동등하게

$a_{n+2}=2a_{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)$

여기서 $\lambda _{0},\lambda _{1},\dots ,\lambda _{k-1}$는 상수 계수이고 p(n)이 비-동차성이며, 만약 p(n)이 차수 r을 가진 다항식이면, 이 비-동차 재귀는 r번 기호적 미분하는 방법을 적용함으로써 동차 재귀로 줄일 수 있습니다.

만약 다음

$P(x)=\sum _{n=0}^{\infty }p_{n}x^{n}$

이 비-동차성의 생성하는 함수이면, 상수 계수 c_i를 갖는 비-동차 재귀

$a_{n}=\sum _{i=1}^{s}c_{i}a_{n-i}+p_{n},\quad n\geq n_{r},$

의 생성하는 함수

$A(x)=\sum _{n=0}^{\infty }a(n)x^{n}$

는 다음으로부터 유도됩니다:

$\left(1-\sum _{i=1}^{s}c_{i}x^{i}\right)A(x)=P(x)+\sum _{n=0}^{n_{r}-1}[a_{n}-p_{n}]x^{n}-\sum _{i=1}^{s}c_{i}x^{i}\sum _{n=0}^{n_{r}-i-1}a_{n}x^{n}.$

만약 P(x)가 유리 생성하는 함수이면, A(x)는 역시 하나입니다. 위에서 논의된 경우는, 여기서 p_n = K는 상수이며, P(x) = K/(1−x)와 함께, 이 공식의 한 예제로 나타납니다. 또 다른 예제, 선형 비-동차성을 갖는 재귀 $a_{n}=10a_{n-1}+n$은 분열 숫자(schizophrenic number)의 정의에서 발생합니다. 동차 재귀의 해는 p = P = 0로 통합됩니다.

Solving first-order non-homogeneous recurrence relations with variable coefficients

게다가, 변수 계수를 갖는 일반적인 일-차 비-동차 선형 재귀 관계에 대해:

$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)$

만약 우리가 수식을 $a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}$에 적용하고 극한 h→0을 취하면, 우리는 변수 계수를 갖는 일-차 선형 미분 방정식(linear differential equation)에 대해 공식을 얻습니다; 합은 적분이 되고, 곱은 적분의 지수 함수가 됩니다.

Solving general homogeneous linear recurrence relations

많은 동차 선형 재귀 관계는 일반화된 초-기하 급수(generalized hypergeometric series)를 수단으로 해결될 수 있습니다. 이것들의 특별한 경우는 직교 다항식(orthogonal polynomials), 및 많은 특수 함수(special function)에 대해 재귀 관계로 이어집니다. 예를 들어, 다음에 대한 해는

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

다음에 의해 제공됩니다:

$J_{n}=J_{n}(z),$

베젤 함수(Bessel function)입니다. 반면에,

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

는 다음에 의해 해결됩니다:

$M_{n}=M(n,b;z)$

합류 초기하 급수(confluent hypergeometric series)입니다. 다항식 계수를 갖는 선형 차이 방정식의 해인 수열은 P-재귀(P-recursive)라고 불립니다. 이들 특정 재귀 방정식에 대해, 다항식(polynomial), 유리식(rational) 또는 초-기하적(hypergeometric) 해을 찾는 알고리듬이 알려져 있습니다.

Solving first-order rational difference equations

Main article: Rational difference equation

일-차 유리 차이 방정식은 형식 $w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}$을 가집니다. 그러한 방정식은 $w_{t}$를 자체로 선형적으로 진화하는 또 다른 변수 $x_{t}$의 비선형 변환으로 씀으로써 해결될 수 있습니다. 그런-다음 표준 방법은 $x_{t}$에서 선형 차이 방정식을 풀기 위해 사용될 수 있습니다.

Stability

Stability of linear higher-order recurrences

차수 d의 선형 재귀,

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},$

는 다음 특성 방정식(characteristic equation)을 가집니다:

$\lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.$

재귀는 안정적(stable)이며, 반복이 점근적으로 고정된 값에 수렴하는 것과 고윳값(eigenvalues) (즉, 특성 방정식의 근)이 실수이든 복소수이든 모두 절댓값이 단위(unity)보다 작은 것은 필요충분 조건임을 의미합니다.

Stability of linear first-order matrix recurrences

Main article: Matrix difference equation

상태 벡터 x와 전이 행렬 A를 갖는 일-차 행렬 차이 방정식에서

$[x_{t}-x^{*}]=A[x_{t-1}-x^{*}]$,

x가 정상 상태 벡터 x*에 점근적으로 수렴하는 것과 전이 행렬 A의 모든 고윳값 (실수이든 또는 복소수이든)이 1보다 적은 절댓값(absolute value)을 가지는 것은 필요충분 조건입니다.

Stability of nonlinear first-order recurrences

다음 비-선형 일-차 재귀를 생각해 보십시오:

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

이 재귀는 지역적으로 안정(locally stable)이며, 만약, x*의 이웃에서 f의 기울기가 절댓값에서 단위(unity)보다 작은 것, 즉, 다음이면:

$|f'(x^{*})|<1$,

그것이 x*에 충분히 근접한 점으로부터 고정된 점 x*에 수렴(converges)함을 의미합니다.

비-선형 재귀는 여러 고정된 점을 가질 수 있으며, 이 경우에서 일부 고정된 점이 지역적으로 안정일 수 있고 다른 일부는 지역적으로 불안정일 수 있습니다; 연속 f에 대해, 두 인접한 고정된 것은 절대 둘 다 지역적으로 안정일 수 없습니다.

비선형 재귀 관계는 k > 1에 대해 기간 k의 주기를 가질 수 있습니다. 그러한 주기는 안정이며, 만약 k번 나타나는 f를 갖는 합성 함수

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

가 같은 기준:

$|g'(x^{*})|<1$

에 따라, 여기서 x*는 주기에서 임의의 점이며, 지역적으로 안정이면, 그것은 양의 측정의 초기 조건의 집합을 끌어당김을 의미합니다.

혼돈(chaotic) 재귀 관계에서, 변수 x는 경계진 영역에 머무르지만 고정점에 수렴하지 않거나 주기를 끌어당기지 않습니다. 방정식의 임의의 고정점 또는 주기는 불안정입니다. 로지스틱 맵(logistic map), 이원적 변환(dyadic transformation) 및 텐트 맵(tent map)을 역시 참조하십시오.

Relationship to differential equations

보통의 미분 방정식(ordinary differential equation)을 수치적으로(numerically) 풀 때, 우리는 전형적으로 재귀 관계에 부딪힙니다. 예를 들어, 오일러의 방법(Euler's method)과 단계 크기 h와 함께 초기값 문제(initial value problem)를 해결할 때

$y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},$

우리는 재귀

$\,y_{n+1}=y_{n}+hf(t_{n},y_{n})$

에 의해 값

$y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots$

을 계산합니다.

선형 일-차 미분 방정식의 시스템은 이산화(discretization) 기사에서 보여준 방법을 사용하여 정확하게 해석적으로 이산화될 수 있습니다.

Applications

Biology

가장 잘 알려진 차이 방정식 중 일부는 모집단(population) 역학을 모델링하려는 시도에서 그들의 기원을 가집니다. 예를 들어, 피보나치 숫자(Fibonacci number)는 토끼 모집단의 성장에 대해 모델로 한 때 사용되었습니다.

로지스틱 맵(logistic map)은 인구 증가를 모델링하기 위해 직접 또는 모집단 역학(population dynamics)의 보다 상세한 모델에 대해 출발점으로 사용됩니다. 이 문맥에서, 결합시키는 차이 방정식은 종종 두 개 이상의 모집단의 상호 작용을 모델링하기 위해 사용됩니다. 예를 들어, 숙주-기생충(parasite) 상호 작용에 대해 니콜슨-베일리(Nicholson-Bailey) 모델은 다음으로 제공됩니다:

$N_{t+1}=\lambda N_{t}e^{-aP_{t}}$

$P_{t+1}=N_{t}(1-e^{-aP_{t}}),$

여기서 N_t와 P_t는 각각 시간 t에서 숙주와 기생충을 나타냅니다.

적분차이 방정식(Integrodifference equation)은 공간 생태학(ecology)에 중요한 재귀 관계의 한 형식입니다. 이들과 다른 차이 방정식은 특히 단일-개체(univoltine) 모집단을 모델링하는 것에 적합합니다.

Computer science

재귀 관계는 알고리듬의 분석(analysis of algorithms)에서 역시 기본적으로 중요합니다. 만약 알고리듬(algorithm)이 문제를 더 작은 부분-문제 (분할 및 정복(divide and conquer))로 나눌 수 있도록 설계되면, 실행 시간은 재귀 관계로 설명됩니다.

간단한 예제는, 최악의 경우에서, 알고리듬이 $n$ 원소를 가진 순서화된 벡터에서 원소를 찾는 데 걸리는 시간입니다.

소박한 알고리듬은 한 번에 한 원소 씩 왼쪽에서 오른쪽으로 검색할 것입니다. 최악의 가능한 시나리오는 요구된 원소가 마지막 원소일 때이므로, 비교 횟수는 $n$입니다.

더 나은 알고리듬은 이진 검색(binary search)이라고 불립니다. 어쨌든, 그것은 순서화된 벡터를 요구합니다. 먼저 원소가 벡터의 가운데에 있는지 확인할 것입니다. 만약 있지 않으면, 중간 원소가 찾는 원소보다 큰지 작은지 확인할 것입니다. 이 시점에서, 벡터의 절반은 버려지고, 알고리듬은 나머지 절반에서 다시 실행될 수 있습니다. 비교 횟수는 다음에 의해 제공될 것입니다:

$c_{1}=1$

$c_{n}=1+c_{n/2}$

이것의 시간 복잡도(time complexity)는 $O(\log _{2}(n))$일 것입니다.

Digital signal processing

디지털 신호 처리(digital signal processing)에서, 재귀 관계는 한 번에 출력이 미래 입력이 되는 시스템에서 피드백을 모델링할 수 있습니다. 그들은 따라서 무한 임펄스 응답(infinite impulse response, 줄여서 IIR) 디지털 필터(digital filter)에서 발생합니다.

예를 들어, 지연 T의 "피드포워드" IIR 빗 필터(comb filter)에 대해 방정식은 다음입니다:

$y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T}$

여기서 $x_{t}$는 시간 t에서 입력, $y_{t}$는 시간 t에서 출력이고, α는 얼마나 지연된 신호가 출력으로 피드백되는지를 제어합니다. 이것으로부터 우리는 다음임을 알 수 있습니다:

$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})$

등등.

Economics

재귀 관계, 특히 선형 재귀 관계는 이론적 및 경험적 경제학 모두에서 광범위하게 사용됩니다. 특히, 거시-경제학에서 우리는 일부 에이전트의 행동이 지연된 변수에 의존하는 다양한 경제 부문 (금융 부문, 상품 부문, 노동 시장 등)의 모델을 개발할 수 있습니다. 모델은 그런-다음 외인성(exogenous) 변수 및 지연된 내인성(endogenous) 변수의 관점에서 핵심 변수 (이자율, 실질 GDP, 등)의 현재 값에 대해 해결할 것입니다. 시간 급수 해석학(time series analysis)을 역시 참조하십시오.

See also

• Holonomic sequences
• Iterated function
• Orthogonal polynomials
• Recursion
• Recursion (computer science)
• Lagged Fibonacci generator
• Master theorem (analysis of algorithms)
• Circle points segments proof
• Continued fraction
• Time scale calculus
• Integrodifference equation
• Combinatorial principles
• Infinite impulse response
• Multiplicative calculus

References

• Batchelder, Paul M. (1967). An introduction to linear difference equations. Dover Publications.
• Miller, Kenneth S. (1968). Linear difference equations. W. A. Benjamin.
• Fillmore, Jay P.; Marx, Morris L. (1968). "Linear recursive sequences". SIAM Rev. Vol. 10, no. 3. pp. 324–353. JSTOR 2027658.
• Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 4: Recurrences, pp. 62–90.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Welsey. ISBN 0-201-55802-5.
• Enders, Walter (2010). Applied Econometric Times Series (3 ed.). Archived from the original on 2014-11-10. {{cite book}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help)
• Cull, Paul; Flahive, Mary; Robson, Robbie (2005). Difference Equations: From Rabbits to Chaos. Springer. ISBN 0-387-23234-6. chapter 7.
• Jacques, Ian (2006). Mathematics for Economics and Business (Fifth ed.). Prentice Hall. pp. 551–568. ISBN 0-273-70195-9. Chapter 9.1: Difference Equations.
• Minh, Tang; Van To, Tan (2006). "Using generating functions to solve linear inhomogeneous recurrence equations" (PDF). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06. pp. 399–404.
• Polyanin, Andrei D. "Difference and Functional Equations: Exact Solutions". at EqWorld - The World of Mathematical Equations.
• Polyanin, Andrei D. "Difference and Functional Equations: Methods". at EqWorld - The World of Mathematical Equations.
• Wang, Xiang-Sheng; Wong, Roderick (2012). "Asymptotics of orthogonal polynomials via recurrence relations". Anal. Appl. 10 (2): 215–235. arXiv:1101.4371. doi:10.1142/S0219530512500108.

External links

• "Recurrence relation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Recurrence Equation". MathWorld.
• "OEIS Index Rec". OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)