|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 정의
함수 [math(f)]의 차분(finite difference)은 [math(\Delta f)] 혹은 [math(\Delta[f])]로 표기하며 다음과 같이 정의한다.[math(\Delta f(x) = f(x+1) - f(x))]
필요에 따라 다음과 같은 정의를 사용한다.
-
앞 차분(forward difference)
[math(\Delta_h f(x) = f(x+h) - f(x))]
-
뒤 차분(backward difference)
[math(\nabla_h f(x) = f(x) - f(x-h) = \Delta_h f(x-h))]
-
가운데 차분(central difference)
[math(\delta_h f(x) = f \left( x + \dfrac{h}{2} \right) - f \left( x - \dfrac{h}{2} \right) = \Delta_\frac{h}{2} f(x) + \nabla_\frac{h}{2} f(x))]
2. 차분의 계산 법칙
[math(f)], [math(g)]를 함수, [math(a)], [math(b)]를 상수라 하자.-
상수의 차분
[math(\Delta a = 0)]
-
선형성
[math(\Delta(af + bg) = a \Delta f + b \Delta g)]
이상의 두 법칙은 [math(\Delta)] 대신 [math(\nabla)]와 [math(\delta)]에 대해서도 성립한다.
-
곱의 차분
[math(\Delta (fg) = f \Delta g + g \Delta f + \Delta f \, \Delta g)]
[math(\nabla (fg) = f \nabla g + g \nabla f - \nabla f \, \nabla g)]
-
몫의 차분
[math(\displaystyle \Delta\frac{f}{g} = \frac{g \Delta f - f \Delta g}{g(g + \Delta g)})]
[math(\displaystyle \nabla\frac{f}{g} = \frac{g \nabla f - f \nabla g}{g(g - \nabla g)})]
-
합과의 관계
[math(\displaystyle \sum_{n=a}^{b} \Delta f(n) = f(b + 1) - f(a))]
[math(\displaystyle \sum_{n=a}^{b} \nabla f(n) = f(b) - f(a - 1))]
3. 미분법과 차분
이산적인 세계(정수)에서의 미분으로 우리가 알고 있는 미분과는 유사하다. 양의 정수 [math(n)]에 대하여 [math(x)]의 내림차순 차례곱( 하강 계승) [math(x^{\underline{n}})]은 다음과 같이 정의되는데,[math(\displaystyle x^{\underline{n}} = \prod_{k=0}^{n-1} (x-k) = x(x-1)\cdots(x-(n-1)))]
차분하면 [math(\Delta x^{\underline{n}} = nx^{\underline{n-1}} = nx(x-1)(x-2)\cdots(x-(n-2)))]가 된다. 이는 다항식의 미분 [math((x^n)' = nx^{n-1})]과 유사하다.
이뿐만 아니라, 상술했듯이 연속적인 세계를 설명하는 연산이 미분, 이산적인 세계를 설명하는 연산이 차분이라면 미분의 역연산인 적분도 이산적인 세계에 대응될 거라 생각할 수 있을 텐데, 그것은 다름아닌 시그마이다. 이것은 어찌보면 당연한게, 고등학교 미적분 과목을 이수했다면 알겠지만 그 유명한 구분구적법이 다음과 같이 나타내진다.
[math(\displaystyle \lim_{x \to \infty}\sum_{k=1}^{n}f(x_{k})\Delta_\frac{b-a}{n} x=\int_{a}^{b}f(x)dx)]
여기서 좌변은 이산적인 세계의 시그마이고, (구분구적법이 애초에 구간을 이산적으로 쪼개는 것이므로), 우변이 연속적인 세계의 정적분이다.
이렇게 직관적으로 이해하는 것도 좋지만, 앞에서 보았던 내림 차례곱을 써서 대표적인 미분과 차분의 관계식을 유도해 보자. 먼저, 미분에서의 지수함수 [math(e^x)]는 차분에서 어떻게 변환되는지를 알아보려고 한다.
[math(f(x)=e^x)]라 하면, 이를 미분하면 [math(f'(x)=e^x)]로 같은 결과가 나온다. 이에 대응하여 차분을 해도 변하지 않는 함수를 [math(E(x))]라 하자. 즉, [math(\Delta E(x) = E(x))]이다. 이제 [math(E(x))]를 구해보자. 차분의 정의에 의해 좌변은 [math(E(x+1)-E(x)=E(x))]이므로 [math(E(x+1)=2E(x))]라는 점화식이 나오며, 이것의 해는 [math(E(x)=2^x)]이다.
이제 적분과 시그마의 관계를 살펴 보자. 이 둘의 관계는 훨씬 눈에 잘 보일 것이다. 이번에는 예로 적분에서의 로그함수 [math(\ln x)]는 어떻게 표현되는지 알아보자. [math(f(x)=\ln x)]라 하면 [math(f'(x)=x^{-1})]가 된다. 이에 대응하여 [math(\displaystyle \Delta L(x) = x^{\underline{-1}})]를 만족시키는 함수 [math(L(x))]를 찾아보자.
다시 한 번 내림 차례곱의 정의를 생각해 보면, 양의 정수 n에 대해 [math(\displaystyle x^{\underline{n}}= (x-0)(x-1)(x-2) ... (x-(n-1)))]로 내림 차례곱을 정의했었는데, 이것을 지수의 확장 비슷하게 '양의 정수 [math(n)]' 이란 조건을 '임의의 정수 [math(n)]'으로 바꿔보자.
[math(x^{\underline{3}} = (x-0)(x-1)(x-2))]
[math(x^{\underline{2}} = (x-0)(x-1))]
[math(x^{\underline{1}} = (x-0))]
이 방식대로 0 이하 지수를 정의하려면
[math(\displaystyle x^{\underline{0}} = 1)]
[math(\displaystyle x^{\underline{-1}} = 1/(x+1))]
[math(\displaystyle x^{\underline{-2}} = 1/(x+1)(x+2))]
와 같이 정하는 게 자연스럽다.[1]
따라서 [math(\displaystyle \Delta L(x) = 1/(x+1))]이고, 차분 연산자의 정의에 의해 [math(\displaystyle L(x+1)-L(x) = 1/(x+1))]이 성립한다. 이것은 그 유명한 리만 제타 함수에 1을 대입했을 때에 나오는 무한급수의 점화식과 완전히 일치한다. 즉, [math(\displaystyle L(x)=\sum_{k=1}^{x}\frac{1}{k})] 임이 도출된다.
잘 따라왔다면 알겠지만 적분과 시그마는 계산 과정만 다를 뿐 결과는 완전히 똑같다. 이는 구분구적법의 관점에서 적분은 미적분의 기본정리를 이용해서 연속적으로 계산한 것이고, 시그마는 구분구적법에 의거해 하나하나씩 이산적으로 쌓고, 그 값에 리미트를 취함으로서 결론적으로 같은 값을 내는 것이라 볼 수 있기 때문이다.
지금까지 유도한 것들은 무엇을 의미하는지 묻는다면, 이것은 미분과 차분의, 연속적인 관점에서의 자연로그와 이산적인 관점에서의 조화수가 대응함을 입증하는 아주 좋은 예시라고 답할 수 있을 것이다. 물론 일부의 예시만으로는 증명이 될 수 없지만, 위 내용들을 다 이해했다면 임의의 함수를 써 보며 확인할 수 있을 것이다.
위 내용들이 잘 이해가 안 된다면 유키 히로시의 수학 걸 6장, 8장을 참조할 것.
4. 미분과 차분
실수 집합 [math(\mathbb{R})]의 부분집합에서 정의된 미분가능한 함수 [math(f)]의 도함수 [math(f')]은 다음과 같이 정의된다.[math(f'(x) = \displaystyle \lim_{h \to 0} \frac{f(x+h)-f(x)}{h})]
이때 [math(\dfrac{f(x+h)-f(x)}{h} = \dfrac{\Delta_h f(x)}{h})]이므로 [math(f')]을 다음과 같이 근사할 수 있다.
[math(f'(x) \approx \dfrac{\Delta_h f(x)}{h})]
이때 오차는 little-o notation을 사용하면 [math(h \to 0)]일 때 [math(o(h))]가 된다.
[math(\dfrac{\Delta_h f(x)}{h} - f'(x) \in o(h))]
따라서 [math(h)]가 충분히 작을 경우 [math(\Delta_h f(x_0))]로부터 [math(f'(x_0))]를 [math(o(h))]의 오차로 근사할 수 있다. 이를 반복적으로 사용하면 간단한 일계 미분방정식을 수치적으로 풀 수 있으며, 이를 오일러의 방법(Euler's method)라고 한다.
뒤 차분, 가운데 차분에 대해서도 이와 비슷하게 근사할 수 있다.
[math(\dfrac{\nabla_h f(x)}{h} - f'(x) \in o(h))]
[math(\dfrac{\delta_h f(x)}{h} - f'(x) \in o(h^2))]
[1]
이렇게 해도 수학적으로 오류가 없는지에 대한 증명은 지수의 확장 증명에 버금갈 정도로 복잡하므로 생략.