2016년 6월 18일 (토) 14:52 판

Faà di Bruno's Formula

진술

파 디 브루노의 공식(Faà di Bruno's Formula)은 연쇄법칙(chain rule)을 고차 미분으로 일반화한 공식이다. 함수 [math]\displaystyle{ f }[/math]와 [math]\displaystyle{ g }[/math]가 미분가능한 일변수 함수이면 다음이 성립한다:

[math]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ j_1 + \cdots + j_{n-k+1} = k }[/math] and [math]\displaystyle{ j_1 + 2j_2 + \cdots + (n-k+1)j_{n-k+1} = n }[/math]을 이용하여 간단히(?) 나타내면

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \pi }[/math]는 [math]\displaystyle{ \{1, \cdots, n\} }[/math]의 partition이며 [math]\displaystyle{ \Pi }[/math]는 그러한 [math]\displaystyle{ \pi }[/math]들의 집합이고, [math]\displaystyle{ B \in \pi }[/math]는 partition [math]\displaystyle{ \pi }[/math]의 한 'block'을 뜻하고, [math]\displaystyle{ \pi }[/math]의 cardinality는 'block'의 수, [math]\displaystyle{ B }[/math]의 cardinality는 'block' [math]\displaystyle{ 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이라고 할 때, \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}

@@ 1번째 줄: / 1번째 줄: @@
-\documentclass[12pt,a4paper]{article}
+=Faà di Bruno's Formula=
-\usepackage{amsfonts,amsmath,amsthm,latexsym,amssymb,kotex,mathrsfs,enumitem,mathtools}
+==진술==
-\usepackage{graphicx}
+'''파 디 브루노의 공식'''(Faà di Bruno's Formula)은 [[연쇄법칙]](chain rule)을 고차 미분으로 일반화한 공식이다. 함수 <math>f</math>와 <math>g</math>가 미분가능한 일변수 함수이면 다음이 성립한다:
-\usepackage[onehalfspacing]{setspace}
+: <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>
-\allowdisplaybreaks
+이를 [[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>
-\newtheorem{theorem}{Theorem}
+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>을 이용하여 간단히(?) 나타내면
-\newtheorem{definition}[theorem]{Definition}
+:<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>
-\newtheorem{lemma}[theorem]{Lemma}
+가 된다. 또한, 이를 '조합적'으로 나타내면 다음과 같다:
-\newtheorem{corollary}[theorem]{Corollary}
+:<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>
-\newtheorem{proposition}[theorem]{Proposition}
+이때 <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를 말한다.
-\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}
-\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}와도 관계가 있다.

사용자:CrMT/연습장/2: 두 판 사이의 차이

2016년 6월 18일 (토) 14:52 판

Faà di Bruno's Formula

진술