크라메르 공식 편집하기

'''크라메르 공식'''(Cramer's Rule) 혹은 '''크래머의 공식/법칙'''은 유일한 해를 가진 연립 일차방정식 <math>A\mathbf{x}=\mathbf{b}</math>의 해를 [[행렬식]]의 비를 이용해서 구하는 공식이다. 스위스 제네바 출신 수학자 가브리엘 크라메르(Gabriel Cramer, 1704-1752)의 이름을 딴 공식이다.

== 설명 ==

n개의 미지수를 가진 n개의 일차연립방정식 <math>Ax=b</math>가 있다고 하자. 이 때 <math>x=(x_1,\cdots ,x_n)^T</math>라 두자. 이제 <math>B_k</math>를 A에서 k번째 열벡터를 b로 바꾼 행렬이라고 두면,
:<math> x_k \det(A) = \det{B_k}</math>
가 성립하는데, 이를 '''크래머의 법칙'''이라 부른다. 여기서 특히 A가 가역행렬이면, 위 식은
:<math> x_k= \frac{\det{B_k}}{\det{A}}</math>
로 나타난다. 따라서 크래머의 법칙은 연립방정식의 해가 어떻게 나오는지 명시적으로 알려준다. 허나 행렬식 계산이 무지 어렵기 때문에 별 쓸모는 없다.

크래머의 법칙을 쓰면 역행렬의 성분이 어떻게 나타나는지도 정확히 알 수 있다. 가령, A의 역행렬의 (i,j)번째 성분 <math>c_{i,j}</math>를 알고 싶다고 하자. 그러면 아래 연립방정식
:<math> A\begin{bmatrix} c_{1,j} \\ \vdots \\ c_{n,j} \end{bmatrix} = \mathbf{e}_j</math>
를 풀면 된다. 그런데 크래머의 법칙에 따르면 이 방정식의 해는 
:<math> c_{i,j} \det{A}= \det 
\begin{pmatrix}
a_{1,1} & \cdots & 0 & \cdots & a_{1,n} \\
\vdots & \ddots & \vdots & \ddots & \vdots\\
a_{j,1} & \cdots & 1 & \cdots & a_{j,n} \\
\vdots & \ddots & \vdots & \ddots & \vdots\\
a_{n,1} & \cdots & 0 & \cdots & a_{n,n} \\
\end{pmatrix}
</math>
가 되는데, 위 행렬식은 계산해보면 <math>(-1)^{i+j}\det(A(j,i))</math>가 된다! 따라서
:<math> c_{i,j} =\frac{(-1)^{i+j}\det(A(j,i))}{\det{A}} </math>
를 얻는다.

== 효율성 ==
A가 n×n행렬일 때 <math>A\mathbf{x}=\mathbf{b}</math>에 대해서 곱셈 횟수는 대략 <math>\mathcal{O}(n^3)</math> A의 행렬식을 구하기 위해서는 A를 사다리꼴 행렬(Row Echelon Form)으로 만드는 과정이 가장 효율적이다. 사다리꼴 행렬로 만들 때 1행부터 n행까지 각각 상수 <math>a_1, \cdots, a_n </math>만큼 곱해서 0이 아닌 모든 A의 1열의 숫자를 모두 1로 맞추어준다. 이 때 위한 상수를 곱하는 횟수는 최대 행렬 A의 전체의 원소의 개수인 n<sup>2</sup>이다. 한편 A의 각 행에 곱해준 상수 <math>a_1, \cdots, a_n </math>의 역수들을 곱해서 새로운 상수 <math>b_1</math>을 구한다. 그 다음에 각 행에서 1행의 숫자를 빼주어서 1행 1열을 제외한 다른 숫자는 모두 0으로 맞추어줘도 행렬식은 변하지 않으니 1행 1열을 제외한 나머지 1열의 원소가 모두 0이면서 행렬식이 <math>|A'|=a_1 \cdots a_n \cdot |A|</math>안 행렬 A'을 만들 수 있다. 이제 이 변형된 행렬 A'에 대해서 2X2 부터 nXn까지 원소부분 (n-1)X(n-1) 행렬에 대해서도 반복적으로 해준다. A에서 A'을 만들 때 숫자를 n<sup>2</sup>+n만큼 곱한 것을 확인할 수 있고, 마찬가지로 상대각행렬(upper triangluar matrix)로 만들 때 최대 <math>\sum_i=1^n (i^2 + i) = \frac{n(n+1)(n+2)}{3} </math>만큼의 숫자를 곱해야 하는 것을 확인할 수 있다.

예시 : 3X3 행렬에서 역행렬 구하기

<math>\mathrm{det}A=\begin{vmatrix}{1} & {2} & 3 \\ 2& 3& 5 \\ -1&0&2 \end{vmatrix} = 1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 1& 3/2& 5/2 \\ 1& 0& -2 \end{vmatrix} </math><br />
<math>1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 0& -1/2& 1/2 \\ 0& -2& -5 \end{vmatrix}=(-2)\cdot (-1/2)\cdot 1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 0& 1& 1 \\ 0& 1& 5/2 \end{vmatrix}</math> 
<math>= (-2)\cdot (-1/2)\cdot 1\cdot 2\cdot (-1) \begin{vmatrix}1& 2& 3 \\ 0& 1& 1 \\ 0& 0& 3/2 \end{vmatrix} = (3/2)\cdot(-2)\cdot(-1/2) \cdot 1 \cdot 2 \cdot (-1) =-3</math><br />

크라메르 공식은 A와 i행(i=1,...n)을 b로 대체한 행렬 A<sub>i</sub>의 행렬식을 구해야 하기 때문에 거기에 (n+1)을 곱한 횟수. 다시 말해 <math>\frac{n^4}{3} + \mathcal{O}(n^3)</math>만큼의 곱셈을 해주어야 한다.

반면에 가우스 소거법은 첨가행렬(augmented matrix) <math>[A|\mathbf{b}]</math>에 대해 사다리꼴 행렬로 만든 뒤 뒤쪽부터 치환(Back Substitution)하면서 해를 구하는 방식이다. 치환하면서 해를 구할 때는 대략 <math>\mathcal{O}(n^2)</math>만큼의 곱셈만 소모되므로 첨가행렬의 사다리꼴로 만드는데 들어가는 숫자 곱셈횟수인 대략 <math>\frac{n^3}{3} + \mathcal{O}(n^2)</math> 만큼의 연산만 하면 된다. 즉 가우스 소거법에 비해 효율이 좋지 않다.

==용도 ==
{{빈 문단}}

{{각주}}
{{문서 가져옴|행렬식|412667|일부}}
[[분류:선형대수학]]