|
|
| (같은 사용자의 중간 판 11개는 보이지 않습니다) |
| 1번째 줄: |
1번째 줄: |
| \documentclass[12pt,a4paper]{article}
| | =미분 갈루아 이론= |
| \usepackage{amsfonts,amsmath,amsthm,latexsym,amssymb,kotex,mathrsfs,enumitem,mathtools}
| |
| \usepackage{graphicx}
| |
| \usepackage[onehalfspacing]{setspace}
| |
| \allowdisplaybreaks
| |
|
| |
|
| \newtheorem{theorem}{Theorem}
| |
| \newtheorem{definition}[theorem]{Definition}
| |
| \newtheorem{lemma}[theorem]{Lemma}
| |
| \newtheorem{corollary}[theorem]{Corollary}
| |
| \newtheorem{proposition}[theorem]{Proposition}
| |
|
| |
|
| \usepackage[hmargin=1in,vmargin=.5in]{geometry}
| |
| \begin{document}
| |
| \title{General Leibniz Rule And Faà Di Bruno's Formula}
| |
| \author{$\sum_{1\le k \le 10} \sum_{1\le j \le k} jk$}
| |
| \date{20160204}
| |
| \maketitle
| |
| \section{General Leibniz Rule}
| |
| \subsection{Statement}
| |
| \textbf{일반화된 Leibniz 규칙}(generalized Leibniz rule)은 곱의 미분법을 일반화한 정리이다. $u, \; v$가 $t$에 대한 $n$-차 미분가능 일변수 함수이면 다음이 성립한다:
| |
| $$(uv)^{(n)} = \sum_{k=0}^n \binom{n}{k} u^{(k)} v^{(n-k)}.$$
| |
| 더욱 일반적으로, $t$에 대한 $n$-차 미분가능한 일변수 함수 $u_1, \cdots, u_\ell$에 대하여 다음이 성립한다:
| |
| $$\left(\prod_{i=1}^\ell u_i \right)^{(n)} = \sum_{\sum_j k_j = n} \binom{n}{k_1, \cdots, k_\ell} \prod_{i=1}^\ell {u_i}^{(k_i)}.$$
| |
|
| |
|
| \subsubsection{Proof}
| |
| 증명은 귀납법으로써 한다. $n=0$일 때엔 당연히 성립하며($\because \binom 0 {0, \cdots, 0} = 1$), $n=m$일 때를 가정하자. 그러면 $n=m+1$일 때,
| |
| \begin{align*} \left(\prod_{i=1}^\ell u_i \right)^{(m+1)} &= \frac{\mathrm d}{\mathrm dt} \left(\prod_{i=1}^\ell u_i \right)^{(m)} \\ &= \frac{\mathrm d}{\mathrm dt}\sum_{\sum_j k_j = m} \binom{m}{k_1, \cdots, k_\ell} \prod_{i=1}^\ell {u_i}^{(k_i)} \\ &= \sum_{\sum_j k_j = m} \frac{m!}{k_1 ! \cdots k_\ell !} \frac{\mathrm d}{\mathrm dt} \prod_{i=1}^\ell {u_i}^{(k_i)} \\ &= \sum_{\sum_j k_j = m} \binom{m}{k_1, \cdots, k_\ell} \sum_{i=1}^\ell {u_i}^{(k_i + 1)} \prod_{1\le j \le \ell, \; j\ne i} {u_j} ^ {(k_j)} \\ &= \sum_{i=1}^\ell \sum_{\sum_j k_j = m} \binom{m}{k_1, \cdots, k_\ell} {u_i}^{(k_i + 1)} \prod_{1\le j \le \ell, \; j\ne i} {u_j} ^ {(k_j)} \\ &= \sum_{i=1}^\ell \sum_{\sum_{j\ne i} k_j + (k_i + 1) = m+1} \binom{m}{k_1, \cdots, k_\ell} {u_i}^{(k_i + 1)} \prod_{1\le j \le \ell, \; j\ne i} {u_j} ^ {(k_j)} \\ &= \sum_{i=1}^\ell \sum_{\sum_{j} {\hat k_j} = m + 1} \binom{m}{\hat k_1, \cdots, \hat k_{i-1}, \hat k_i - 1, \hat k_{i+1}, \cdots, \hat k_\ell} \prod_{j=1}^\ell {u_j} ^ {(\hat k_j)} \\ &= \sum_{\sum_{j} {\hat k_j} = m + 1} \sum_{i=1}^\ell \binom{m}{\hat k_1, \cdots, \hat k_{i-1}, \hat k_i - 1, \hat k_{i+1}, \cdots, \hat k_\ell} \prod_{j=1}^\ell {u_j} ^ {(\hat k_j)} \\ &= \sum_{\sum_{j} {\hat k_j} = m + 1} \binom{m+1}{\hat k_1, \cdots, \hat k_\ell} \prod_{j=1}^\ell {u_j} ^ {(\hat k_j)}.\end{align*}
| |
| (where $\hat k_j = k_j \text{ when }j\ne i, \; \hat k_i = k_i + 1$)으로 성립한다. 마지막 부분은 다항계수 항등식으로 자명하다.
| |
|
| |
|
| \subsection{Generalization for Multivariable Calculus}
| | <!-- |
| 다변수 함수의 경우에는 미분 연산자를 편미분 연산자로만 바꾸면 된다. 즉,
| | =람다 계산= |
| $$\partial^\alpha (fg) = \sum_{0\le \beta \le \alpha} \binom \alpha \beta (\partial ^\beta f)(\partial ^{\alpha - \beta} g).$$
| | {{학술}} |
| (양변에 $\partial ^\alpha t$는 생략.)
| | [[분류:람다 계산]] |
| | {{넘겨주기 있음|람다 대수|람다 연산|람다 계산법|받침=예}} |
|
| |
|
| \section{Faà di Bruno's Formula}
| | '''람다 계산'''(람다 대수, 람다 연산, 람다 계산법; {{llang|1=en|2=lambda calculus}})은 수리논리학과 이론 컴퓨터과학에서 사용하는 형식 체계(formal system)로, 함수의 정의, 적용, 재귀 등을 치환, 바인딩(binding) 등을 이용하여 추상화한다. [[알론조 처치]]가 1930년대 처음 발표하였다. |
| \subsection{Statement}
| |
| \textbf{Faà di Bruno 공식}은 chain rule을 고차 미분으로 일반화한 공식이다. 함수 $f$와 $g$가 미분가능한 일변수 함수이면 다음이 성립한다:
| |
| $$\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}.$$
| |
| 이를 \textbf{Bell polynomial} $$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}$$ where $j_1 + \cdots + j_{n-k+1} = k$ and $j_1 + 2j_2 + \cdots + (n-k+1)j_{n-k+1} = n$을 이용하여 간단히(?) 나타내면
| |
| $$\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)$$
| |
| 가 된다. 또한, 이를 `조합적'으로 나타내면 다음과 같다: | |
| $$\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),$$
| |
| 이때 $\pi$는 $\{1, \cdots, n\}$의 partition들이며 $\Pi$는 그러한 $\pi$들의 집합이고, $B \in \pi$는 partition $\pi$의 한 `block'을 뜻하고, $\pi$의 cardinality는 `block'의 수, $B$의 cardinality는 `block' $B$의 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}와도 관계가 있다.
| | == 역사 == |
| | [[라이프니츠]]는 다음과 같은 생각을 가지고 있었다. |
| | * 모든 문제들이 서술될 수 있는 '보편적인(universal) 언어'를 만들어라. |
| | * 위의 언어로 서술된 모든 문제를 해결할 수 있는 방법을 찾아라. |
| | 첫 번째 것은, 만약 수학적인 문제만으로 제한한다면, [[러셀]]과 [[프레게]] 등에 의한 '집합론'의 공리적 서술로 인하여 꽤 만족스러운 결과를 얻었다고 할 수 있다. 하지만 두 번째 것은, 당연히 안 될 것 같지만, 그 증명이 명확하지 않았다. (이는 [[힐베르트]]에 의하여 ''Entscheidungsproblem''로 불리게 된다. 직역하면 ''결정 문제''이다.) 이것은 1930년대에 [[알론조 처치]]와 [[앨런 튜링]]에 의하여 각각 독립적으로 해결되는데, 그 답은 [[처치-튜링 명제]]를 가정할 때<ref>Church-Turing 명제는 다음을 말한다: 알고리듬으로 계산 가능함과 튜링 기계로의 계산 가능성은 동치이다. 이와 동치 명제로, 알고리듬으로 계산 가능함과 lambda calculus로 표현 가능함은 동치이다.)</ref> '''No'''이다. 튜링은 후에 이 두 방법으로의 ''계산 가능성'', 즉 계산 가능한 함수들의 모임이 서로 같음을 보였다. |
| | 람다 계산이 고안된 이후로, 람다 연산에 기반한 ''함수 프로그래밍 언어''(functional programming language)가 만들어졌다. ''Reduction machine''은 이런 functional language의 실행을 위하여 고안되었다. |
|
| |
|
| \subsection{Statement: for Multivariable}
| | == 이해 == |
| 위의 $\pi, \; \Pi, \; B$의 정의를 그대로 가져와 쓰면, $y=f(x)$라고 할 때,
| | Lambda calculus는 함수의 계산을 조금 더 간편하게 나타내는 표기이다. 간단히 말하면, 대수학에서 잊을 만하면 한 번씩 나오는 'evaluation'과 비슷한 개념이라고 할 수 있다. 예를 들어, <math>x</math>에 대한 식 <math>x^2 - \sin x</math>가 있다고 하자. 이는 다음과 같은 함수를 나타내기도 한다: |
| $$\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}$$
| | :<math>x \mapsto x^2 - \sin x.</math> |
| 이다. 예를 들어 $n=3$이라고 하면
| | 이 함수를 lambda calculus에서는 |
| \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>\lambda x. x^2 - \sin x</math> |
| 이다.
| | 로 나타낸다.<ref><math>\lambda x[x \mapsto x^2 - \sin x]</math>로 나타내기도 한다.</ref> 그리고 이 함수의 <math>x=a</math>에서의 함숫값을 |
| | | :<math>(\lambda x. x^2 - \sin x)a</math> |
| 우리는 이 식을 이용하여 역함수의 $n$-계 도함수의 `linear recurrence'를 얻을 수 있다.
| | 로 나타낸다. 예를 들어 <math>(\lambda x.x^2 - \sin x)\pi = \pi^2 - \sin \pi = \pi^2</math>이다. 이 λ-연산자는 |
| | | --> |
| \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이라고 할 때,
| |
| \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}
| |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| \end{document}
| |