|
|
(같은 사용자의 중간 판 10개는 보이지 않습니다) |
1번째 줄: |
1번째 줄: |
| =Faà di Bruno's Formula= | | =미분 갈루아 이론= |
| ==진술==
| |
| '''파 디 브루노의 공식'''(Faà di Bruno's Formula)은 [[연쇄법칙]](chain rule)을 고차 미분으로 일반화한 공식이다. 함수 <math>f</math>와 <math>g</math>가 미분가능한 일변수 함수이면 다음이 성립한다:
| |
| : <math>\frac{\mathrm d ^n}{\mathrm dx^n} f(g(x)) = \sum_{\sum_{1\le j \le n} j\cdot m_j = n}\frac{n!}{m_1! m_2! \cdots m_n!} f^{(m_1 + \cdots + m_n)}(g(x)) \prod_{1\le j \le n} \left(\frac{g^{(j)}(x)}{j!} \right)^{m_j}.</math>
| |
| 이를 [[Bell polynomial]]
| |
| : <math>B_{n,k}(x_1, \cdots , x_{n-k+1} ) = \sum_{(j_1 , \cdots , j_{n-k+1})} \frac{n!}{j_1! j_2! \cdots j_{n-k+1}!} \prod_{i=1}^{n-k+1} \left(\frac{x_i}{i!}\right)^{j_i}</math>
| |
| where <math>j_1 + \cdots + j_{n-k+1} = k</math> and <math>j_1 + 2j_2 + \cdots + (n-k+1)j_{n-k+1} = n</math>을 이용하여 간단히(?) 나타내면
| |
| :<math>\frac{\mathrm d ^n}{\mathrm dx^n} f(g(x)) = \sum_{k=1}^n f^{(k)} (g(x)) B_{n,k} \left( g'(x) , \cdots , g^{(n-k+1)}(x)\right)</math>
| |
| 가 된다. 또한, 이를 '조합적'으로 나타내면 다음과 같다:
| |
| :<math>\frac{\mathrm d ^n}{\mathrm dx^n} f(g(x)) = \sum_{\pi \in \Pi }f^{(|\pi|)}(g(x)) \prod_{B\in \pi} g^{(|B|)}(x).</math>
| |
| 이때 <math>\pi</math>는 <math>\{1, \cdots, n\}</math>의 partition이며 <math>\Pi</math>는 그러한 <math>\pi</math>들의 집합이고, <math>B \in \pi</math>는 partition <math>\pi</math>의 한 'block'을 뜻하고, <math>\pi</math>의 cardinality는 'block'의 수, <math>B</math>의 cardinality는 'block' <math>B</math>의 size를 말한다.
| |
|
| |
|
| 위 식에서의 $f^{(\cdot)}(g(x)) \prod (g^{(\cdot)}(x))^\cdot$의 계수들(\textbf{Faà di Bruno coefficients}) $$\frac {n!}{m_1! m_2! \cdots 1!^{m_1} 2!^{m_2}\cdots}$$은 $n=\underbrace{1+\cdots+1}_{m_1} \,+\, \underbrace{2+\cdots+2}_{m_2} \,+\, \underbrace{3+\cdots+3}_{m_3}+\cdots$으로 나누는 partition의 수이며, Bell polynomial에도 나타난다. 참고로, Bell polynomial은 통계학의 \textbf{cumulant}와도 관계가 있다.
| |
|
| |
|
| \subsection{Statement: for Multivariable}
| |
| 위의 $\pi, \; \Pi, \; B$의 정의를 그대로 가져와 쓰면, $y=f(x)$라고 할 때,
| |
| $$\frac{\partial ^n}{\partial x_1 \cdots \partial x_n} g(y) = \sum_{\pi \in \Pi} g^{(|\pi|)}(y) \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}$$
| |
| 이다. 예를 들어 $n=3$이라고 하면
| |
| \begin{align*} {\partial^3 \over \partial x_1\, \partial x_2\, \partial x_3}f(y) & = f'(y){\partial^3 y \over \partial x_1\, \partial x_2\, \partial x_3} \\ & + f''(y) \left( {\partial y \over \partial x_1} \cdot{\partial^2 y \over \partial x_2\, \partial x_3} +{\partial y \over \partial x_2} \cdot{\partial^2 y \over \partial x_1\, \partial x_3} + {\partial y \over \partial x_3} \cdot{\partial^2 y \over \partial x_1\, \partial x_2}\right) \\ & + f'''(y) {\partial y \over \partial x_1} \cdot{\partial y \over \partial x_2} \cdot{\partial y \over \partial x_3} \end{align*}
| |
| 이다.
| |
|
| |
|
| 우리는 이 식을 이용하여 역함수의 $n$-계 도함수의 `linear recurrence'를 얻을 수 있다.
| |
|
| |
|
| \subsection{Proof}
| | <!-- |
| 우리는 다음의 두 가지 point에 집중할 것이다:
| | =람다 계산= |
| \begin{enumerate}[label=\textbf{Pt.\arabic*}]
| | {{학술}} |
| \item $\frac{\partial^n}{\partial x_1 \cdots \partial x_n}$, 즉 모두 독립적인 변수로 미분했을 때의 식. 우변의 계수는 모두 1일 것이다.
| | [[분류:람다 계산]] |
| \item $x_i$들이 모두 구별되지 않을 때. 예를 들면, 만약 $n=3$일 때 $x_2 = x_3$이라면, 다음 두 항은 `중복도 2의' 한 항으로 합쳐지게 된다: $$\frac{\partial y}{\partial x_2}\frac{\partial^2 y}{\partial x_1\partial x_3} + \frac{\partial y}{\partial x_3}\frac{\partial^2 y}{\partial x_1\partial x_2} = 2\frac{\partial y}{\partial x_2}\frac{\partial^2 y}{\partial x_1\partial x_2}.$$ 이런 `중복된 항의 수'를 구하는 데 초점을 둔다.
| | {{넘겨주기 있음|람다 대수|람다 연산|람다 계산법|받침=예}} |
| \end{enumerate}
| |
| 이런 관점에서는, (다른 접근과는 다르게) 모든 변수가 같은 것보다도 independent한 게 오히려 편하고 쉽고 기본적이다.
| |
|
| |
|
| 먼저 다음의 $\{1, \cdots, n+1\}$의 partition을 만드는 inductive한 방법(algorithm)을 생각하자: $\pi_n$를 $\{1, \cdots, n\}$의 partition이라고 할 때,
| | '''람다 계산'''(람다 대수, 람다 연산, 람다 계산법; {{llang|1=en|2=lambda calculus}})은 수리논리학과 이론 컴퓨터과학에서 사용하는 형식 체계(formal system)로, 함수의 정의, 적용, 재귀 등을 치환, 바인딩(binding) 등을 이용하여 추상화한다. [[알론조 처치]]가 1930년대 처음 발표하였다. |
| \begin{enumerate}
| |
| \item $\pi_{n+1} = \pi_n \cup \{\{n+1\}\}$,
| |
| \item $\pi_{n+1} = \pi_n \setminus \{B\} \cup \{B \cup \{n+1\}$ for some $B\in \pi_n$.
| |
| \end{enumerate}
| |
| 이 두 가지 방법으로 모든 $\{1, \cdots , n+1\}$의 partition을 만들 수 있음은 당연하다. 이제 다음을 귀납적으로 보이자: $$\frac{\partial ^n}{\partial x_1 \cdots \partial x_n} f(y) = \sum_{\pi} f^{(|\pi|)}(y) \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}.$$
| |
| 이때, $n\ge 0$이다. 만약 $n=0$이면, 다른 경우와 같이 $\pi$는 $ \{1, \cdots, n\}$의 특정한 non-empty subset들을 모은 것이므로 $\{1, \cdots , n \} = \emptyset$ if $n=0$에서 $\pi$는 아무 원소도 가질 수 없고, 즉 $\pi=\emptyset$으로 보는 것이 타당하다. 이에 따라 $n=0$일 때에 $f(y) = f(y)$로 성립한다.
| |
|
| |
|
| 이제 다음 전개를 보자:
| | == 역사 == |
| \begin{align*} \frac{\partial^{n+1}}{\partial x_1 \cdots \partial x_{n+1}} f(y) &= \frac \partial {\partial x_{n+1}} \sum_{\pi} f^{(|\pi|)}(y) \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}
| | [[라이프니츠]]는 다음과 같은 생각을 가지고 있었다. |
| | * 모든 문제들이 서술될 수 있는 '보편적인(universal) 언어'를 만들어라. |
| | * 위의 언어로 서술된 모든 문제를 해결할 수 있는 방법을 찾아라. |
| | 첫 번째 것은, 만약 수학적인 문제만으로 제한한다면, [[러셀]]과 [[프레게]] 등에 의한 '집합론'의 공리적 서술로 인하여 꽤 만족스러운 결과를 얻었다고 할 수 있다. 하지만 두 번째 것은, 당연히 안 될 것 같지만, 그 증명이 명확하지 않았다. (이는 [[힐베르트]]에 의하여 ''Entscheidungsproblem''로 불리게 된다. 직역하면 ''결정 문제''이다.) 이것은 1930년대에 [[알론조 처치]]와 [[앨런 튜링]]에 의하여 각각 독립적으로 해결되는데, 그 답은 [[처치-튜링 명제]]를 가정할 때<ref>Church-Turing 명제는 다음을 말한다: 알고리듬으로 계산 가능함과 튜링 기계로의 계산 가능성은 동치이다. 이와 동치 명제로, 알고리듬으로 계산 가능함과 lambda calculus로 표현 가능함은 동치이다.)</ref> '''No'''이다. 튜링은 후에 이 두 방법으로의 ''계산 가능성'', 즉 계산 가능한 함수들의 모임이 서로 같음을 보였다. |
| | 람다 계산이 고안된 이후로, 람다 연산에 기반한 ''함수 프로그래밍 언어''(functional programming language)가 만들어졌다. ''Reduction machine''은 이런 functional language의 실행을 위하여 고안되었다. |
|
| |
|
| | | == 이해 == |
| | | Lambda calculus는 함수의 계산을 조금 더 간편하게 나타내는 표기이다. 간단히 말하면, 대수학에서 잊을 만하면 한 번씩 나오는 'evaluation'과 비슷한 개념이라고 할 수 있다. 예를 들어, <math>x</math>에 대한 식 <math>x^2 - \sin x</math>가 있다고 하자. 이는 다음과 같은 함수를 나타내기도 한다: |
| | | :<math>x \mapsto x^2 - \sin x.</math> |
| | | 이 함수를 lambda calculus에서는 |
| | | :<math>\lambda x. x^2 - \sin x</math> |
| | | 로 나타낸다.<ref><math>\lambda x[x \mapsto x^2 - \sin x]</math>로 나타내기도 한다.</ref> 그리고 이 함수의 <math>x=a</math>에서의 함숫값을 |
| \end{document} | | :<math>(\lambda x. x^2 - \sin x)a</math> |
| | 로 나타낸다. 예를 들어 <math>(\lambda x.x^2 - \sin x)\pi = \pi^2 - \sin \pi = \pi^2</math>이다. 이 λ-연산자는 |
| | --> |