본문 바로가기

Linear algebra

 (4)
60. Strassen's Algorithm 스트라센 알고리즘(Strassen's Algorithm)은 행렬 곱셈을 $\Theta(n^3)$보다 빠른 시간에 하는 알고리즘이며 카라츠바 알고리즘과 유사하게 분할 정복을 이용하여 시간복잡도를 줄인다. 크기가 $n \times n$인 두 행렬 $A$와 $B$가 존재하고, $A$와 $B$의 곱이 행렬 $C$일 때 스트라센 알고리즘의 작동 방식은 다음과 같다. 먼저 각 행렬을 $4$등분해서 다음과 같이 나눈다. $$A = \begin{bmatrix} A_{1, 1} & A_{1, 2} \\ A_{2, 1} & A_{2, 2} \end{bmatrix}, B = \begin{bmatrix} B_{1, 1} & B_{1, 2} \\ B_{2, 1} & B_{2, 2} \end{bmatrix}, C = \begin..
59. Gaussian Elimination 가우스 소거법(Gaussian Elimination)은 연립일차방정식의 해를 구할 때 사용되는 행렬 연산이며, 그밖에도 다양한 방법으로 응용이 가능하다. 가우스 소거법은 행렬에 다음과 같은 세 가지 연산을 수행한다. 첫 번째 연산을 두 번째 연산과 세 번째 연산의 조합으로 대체할 수 있기 때문에 두 가지 연산이라고 해도 상관없지만 편의상 세 가지로 구분했다.$i$행과 $j$행을 서로 바꾼다.$i$행의 각 성분에 $0$이 아닌 실수 $k$를 곱한다.$i$행에 $j$행을 더한다.가우스 소거법의 목표는 행렬의 랭크와 독립이 아닌 열 사이의 상관관계를 유지하면서 행렬을 행사다리꼴로 만드는 것이다. 이와 관련하여 다음 용어들을 알아 두는 것이 좋다.피벗(Pivot, Leading Entry)은 각 행에서 처음으로..
58. Rank of Matrix 행렬의 랭크를 쉽게 이해하기 위해서는 벡터의 독립에 대해서 알 필요가 있다. 두 벡터 $\vec{u}, \vec{v}$가 다음과 같은 조건을 만족할 경우 서로 독립(Independence)이라고 한다.$$a\vec{u}+b\vec{v}=\vec{0} \to a=b=0$$이것을 다르게 해석하면 두 개의 벡터가 독립일 때 그 벡터들을 이용해서 공간 내의 모든 좌표를 나타낼 수 있는 $2$차원 공간이 존재한다는 의미가 된다. 이와 비슷하게 $n$개의 벡터 $\vec{v_1}, \vec{v_2}, \ldots \vec{v_n}$가 다음과 같은 조건을 만족할 경우 서로 독립이라고 한다.$$a_1\vec{v_1}+a_2\vec{v_2}+\ldots+a_n\vec{v_n}=\vec{0} \to a_1=a_2=\ldo..
57. Matrices 이번 글에서는 선형대수학(Linear Algebra)에 대한 내용을 다룬다. 선형대수학은 덧셈과 곱셈을 통한 변화에 초점을 두는 수학의 한 분야이며, 적절한 표현을 이용하여 선형방정식의 해를 구하는 것을 핵심으로 하고 있다. 선형대수학에서 중요하게 다뤄지는 개념으로 행렬(Matrices)과 벡터(Vectors)가 존재하는데, 벡터에 관한 자세한 내용은 카테고리 G에서 다루고 여기서는 행렬에 관한 내용 위주로 다루기로 한다. 행렬은 수나 식을 직사각형 모양으로 배열한 것으로 행(Row, 가로줄)의 수가 $n$, 열(Column, 세로줄)의 수가 $m$인 경우 $n \times m$ 행렬이라고 한다. 또한 각각의 수나 식을 행렬의 성분(Entry)이라고 하고, 각각의 행을 행벡터(Row Vector), 각각..

티스토리툴바