|
|
| 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를 말한다.
| |
|
| |
|
| 위 식에서의 <math>f^{(\cdot)}(g(x)) \prod (g^{(\cdot)}(x))^\cdot</math>의 계수들('''Faà di Bruno coefficients''')
| | '''람다 연산'''(람다 대수, 람다 계산, 람다 계산법; {{llang|1=en|2=lambda calculus}})은 수리논리학과 이론 컴퓨터과학에서 사용하는 형식 체계(formal system)로, 함수의 정의, 적용 등을 치환, 바인딩 등을 이용하여 추상화한다. [[알론조 처치]]가 1930년대 처음 발표하였다. |
| :<math>\frac {n!}{m_1! m_2! \cdots 1!^{m_1} 2!^{m_2}\cdots}</math>
| |
| 은 정수 <math>n</math>을 | |
| :<math>n=\underbrace{1+\cdots+1}_{m_1} \,+\, \underbrace{2+\cdots+2}_{m_2} \,+\, \underbrace{3+\cdots+3}_{m_3}+\cdots</math>
| |
| 으로 나누는 partition의 수이며, Bell polynomial에도 나타난다. 참고로, Bell polynomial은 통계학의 [[누적량]](cumulant)과도 관계가 있다.
| |
|
| |
|
| ==Statement: for Multivariable== | | == 역사 == |
| 위의 <math>\pi, \; \Pi, \; B</math>의 정의를 그대로 가져와 쓰면, <math>y=u(x_1 , x_2 ,\cdots , x_n)</math>라고 할 때,
| | [[라이프니츠]]는 다음과 같은 생각을 가지고 있었다. |
| :<math>\frac{\partial ^n}{\partial x_1 \cdots \partial x_n} f(y) = \sum_{\pi \in \Pi} f^{(|\pi|)}(y) \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}</math>
| | * 모든 문제들이 서술될 수 있는 '보편적인(universal) 언어'를 만들어라. |
| 이다. 예를 들어 <math>n=3</math>이라고 하면
| | * 위의 언어로 서술된 모든 문제를 해결할 수 있는 방법을 찾아라. |
| :<math>\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}</math>
| | 첫 번째 것은, 만약 수학적인 문제만으로 제한한다면, [[러셀]]과 [[프레게]] 등에 의한 '집합론'의 공리적 서술로 인하여 꽤 만족스러운 결과를 얻었다고 할 수 있다. 하지만 두 번째 것은, 당연히 안 될 것 같지만, 그 증명이 명확하지 않았다. (이는 [[힐베르트]]에 의하여 ''Entscheidungsproblem''로 불리게 된다. 직역하면 ''결정 문제''이다.) 이것은 1930년대에 [[알론조 처치]]와 [[앨런 튜링]]에 의하여 각각 독립적으로 해결되는데, 그 답은 [[처치-튜링 명제]]를 가정할 때<ref>Church-Turing 명제는 다음을 말한다: 알고리듬으로 계산 가능함과 튜링 기계로의 계산 가능성은 동치이다. 이와 동치 명제로, 알고리듬으로 계산 가능함과 lambda calculus로 표현 가능함은 동치이다.)</ref> '''No'''이다. 튜링은 후에 이 두 방법으로의 ''계산 가능성'', 즉 계산 가능한 함수들의 모임이 서로 같음을 보였다. |
| 이다.
| | 람다 연산이 고안된 이후로, 람다 연산에 기반한 ''함수 프로그래밍 언어''(functional programming language)가 만들어졌다. ''Reduction machine'은 이런 functional language의 실행을 위하여 고안되었다. |
| | |
| 또한, 변수가 중복된 경우에는 다음과 같다:
| |
| :<math>\partial_\tau f(y) = \sum_{\tau = \bigoplus m_i\tau_i} M f^{(|\tau|)} (y) \prod_{i} \partial_{\tau_i} y</math>
| |
| 이때 <math>\tau= \{ \underbrace{1, \cdots , 1}_{k_1}, \cdots, \underbrace{n, \cdots , n}_{k_n}\}</math>는 multiset이며, <math>\partial_{\tau } = {\partial^{\sum k_i} \over \prod_i \partial x_i^{k_i}}</math>이고, <math>\bigoplus m_i\tau_i</math>는 multiset으로서의 합집합을 나타낸다. 이때 <math>m_i \tau_i = \underbrace{\tau_i \cup \cdots \cup \tau_i}_{m_i}</math>를 말하고 <math>\bigoplus</math>은 <math>\tau_i</math>들이 모두 다름을 말한다. 또한 <math>|\tau|</math>는 <math>\tau = \bigoplus m_i\tau_i</math>로 쪼개었을 때의 partition의 수 <math>\sum m_i</math>를 말하며, multiplicity <math>M</math>는 <math>\tau</math>의 같은 수들을 모두 다르게 보았을 때와 같게 보았을 때의 비율을 말한다. 또한,
| |
| :<math>M = \frac{\prod k_i !}{\prod \tau_i !!^{m_i} \prod m_i !}</math>
| |
| 이 성립한다. 이때 <math>\tau!! = \prod k_i</math>를 말한다.
| |
| | |
| 우리는 이 식을 이용하여 역함수의 <math>n</math>-계 도함수의 'linear recurrence'를 얻을 수 있다.
| |
| | |
| ==Proof==
| |
| 우리는 다음의 두 가지 point에 집중할 것이다:
| |
| *<math>\frac{\partial^n}{\partial x_1 \cdots \partial x_n}</math>, 같은 변수들도 일단 index를 다르게 하고 미분했을 때의 식. 우변의 계수는 모두 1일 것이다.
| |
| *앞의 결과에서 동류항을 정리. 예를 들면, 만약 <math>n=3</math>일 때 <math>x_2 = x_3</math>이라면, 다음 두 항은 '중복도 2의' 한 항으로 합쳐지게 된다:
| |
| ::<math>\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}.</math>
| |
| :이런 '중복된 항의 수'를 구하는 데 초점을 둔다.
| |
| | |
| 먼저 다음의 <math>\{1, \cdots, n+1\}</math>의 partition을 만드는 inductive한 방법(algorithm)을 생각하자: <math>\pi_n</math>를 <math>\{1, \cdots, n\}</math>의 partition이라고 할 때,
| |
| * <math>\pi_{n+1} = \pi_n \cup \{\{n+1\}\}</math>,
| |
| * <math>\pi_{n+1} = \pi_n \setminus \{B\} \cup \{B \cup \{n+1\}\}</math> for some <math>B\in \pi_n</math>.
| |
| | |
| 이 두 가지 방법으로 모든 <math>\{1, \cdots , n+1\}</math>의 partition을 만들 수 있음은 당연하다. 이제 다음을 귀납적으로 보이자:
| |
| :<math>\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}.</math>
| |
| 이때, <math>n\ge 0</math>이다. 만약 <math>n=0</math>이면, 다른 경우와 같이 <math>\pi</math>는 <math>\{1, \cdots, n\}</math>의 특정한 non-empty subset들을 모은 것인데 <math>\{1, \cdots , n \} = \emptyset</math> if <math>n=0</math>에서 <math>\pi</math>는 아무 원소도 가질 수 없고, 즉 <math>\pi=\emptyset</math>으로 보는 것이 타당하다. 이에 따라 <math>n=0</math>일 때에 <math>f(y) = f(y)</math>로 성립한다.
| |
| | |
| 이제 다음 전개를 보자:
| |
| :<math>\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}
| |
| \\= \sum_{\pi} \left[ f^{(|\pi|+1)}(y) \frac {\partial y} {\partial x_{n+1}} \cdot \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}+f^{(|\pi|)}(y) \frac {\partial y} {\partial x_{n+1}} \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}\right]
| |
| \\= \sum_{\pi} \left[ f^{(|\pi|+1)}(y) \frac {\partial y} {\partial x_{n+1}} \cdot \prod_{B\in\pi} \frac{\partial^{|B|}y}{\prod_{j\in B}\partial x_j}+f^{(|\pi|)}(y) \sum_{B\in\pi} \left( \frac{\partial^{|B|+1}y}{\partial x_{n+1}\prod_{j\in B} \partial x_j} \cdot \prod_{B\ne C\in \pi}\frac{\partial^{|C|}y}{\prod_{j\in C} \partial x_j} \right)\right]
| |
| </math>
| |
| 여기서 각각의 partition <math>\pi</math>에 대해, 괄호 안의 두 항은 각각 inductively partition을 만드는 두 방법에 대응된다. 즉 위의 식은 <math>n+1</math>에서의 모든 partition에 대한 sum이 되고, 즉 증명이 완료된다.
| |
| | |
| 이제 중복된 경우의 중복도를 생각해보자. 일단 중복된 변수가 있을 때의 식이
| |
| :<math>\partial_\tau f(y) = \sum_{\tau = \bigoplus m_i\tau_i} M f^{(|\tau|)} (y) \prod_{i} \partial_{\tau_i} y</math>
| |
| 의 형태가 됨은 자명하다. 이제 <math>M</math>에 관한 식만 구하면 된다.
| |
| | |
| 1부터 <math>n</math>까지의 수가 써진 타일이 있다고 생각해보자. <math>i</math> 타일은 <math>k_i</math> 개씩 있고, 즉 총 <math>\sum k_i</math> 개의 타일이 있다. 이를 모은 집합을 <math>\tau</math>라 하고, 이의 분할 <math>\tau = \oplus m_i \tau_i</math>를 상정하자. <!-- 증명 작성중 -->
| |