지난 포스팅(#디지털 영상 처리를 활용하는 분야의 예시)에서 전자기 스펙트럼(Electromagnetic Spectrum)을 잠깐 다루었다. 이번 포스팅에서 이를 좀 더 자세히 살펴보자.
- 전자기 스펙트럼(Electromagnetic Spectrum):
1666년 아이작 뉴턴(Issaac Newton)은 햇빛이 단순히 흰색 빛이 아니라 연속적인 컬러스펙트럼으로 구성된다는 것을 프리즘을 통과했을 때 보라색부터 빨간색까지 연속적인 컬러 스펙트럼이 만들어지는 현상을 통해 발견하였다. 아래 그림과 같이 이 보라색부터 빨간색까지의 범위를 가시광선이라 하는데, 우리 눈에 보이는 영역을 의미한다. 그림에 보여지는 것과 같이 이 가시광선 영역은 전체 전자기 스펙트럼에서 아주 작은 부분에 해당한다. 우측 끝엔 라디오(Radio)파가 위치해 있고 가시광선 역역에 비해 파장이 수십억배 길다. 반대로 좌측 끝엔 감마선(Gamma Ray)이 있으며 가시광선에 비해 파장이 수백만배 짧다. 아래 그림을 참고하자.
전자기 스펙트럼은 파장(wavelength), 주파수(frequency) 로 표현된다. 이러한 파장과 주파수의 관계는 아래 식과 같이 표현된다. 람다는 파장을, 주파수는 v, c는 광속을 각각 의미한다.
전자기 스펙트럼의 에너지는 주파수에 특정 상수를 곱하여 표현하는데, 아래 식과 같다.
여기서 h는 Plank's 상수이다. Plank's상수는 입자의 에너지와 진동수의 비를 나타낸 상수로써 h=E/f로 정의 된다. 양자역학의 기본 상수 중 하나이다. (출처: 위키백과)
각 요소의 단위는 다음과 같다.
전자기파는 사인파(sinusoidal waves)를 람다(lambda)길이 만큼의 파장으로 전파시키는 것으로 볼 수 있다. 혹은 질량이 없는 입자(particles)들의 흐름(stream)으로써 wave형태의 패턴으로 빛의 속도로 움직이는 것으로 생각할 수도 있다.
람다(lambda)는 사인파의 주기를 뜻하는 것으로 사인파는 똑같은 패턴의 신호가 주기적으로 나타나는 형태이다. 즉 처음 나타난 패턴의 한 점이 다시 나오기까지 걸리는 시간을 의미한다.
각 무질량 입자(massless particles)들은 어느 정도의 에너지 덩어리를 가지고 있는데, 각 덩어리 에너지를 우리는 광자(photon)라 부른다. 에너지에 대한 얘기를 해보자면 에너지는 식(2)에 정의되어 있는데, 에너지는 주파수에 비례함을 식(2)로부터 알 수 있다. 즉 주파수(frequency)가 높을 수록(주파수가 높으면 주기는 짧아짐) 광자가 더 많은 에너지를 갖게 된다. 따라서 라디오파는 가장 낮은 에너지를 가지고, 적외선(infrared), 가시광선(visible), 자외선(ultraviolet), X선(X-ray), 감마선 순으로 높은 에너지를 갖는다. 이를 통해 우리는 왜 감마선이 인체 조직에 위험한지를 알 수 있다. 높은 에너지를 가진 감마선이 인체를 투과하며 조직을 파괴하거나 변형시키는 등 인체에 위험을 초래할 수 있다.
- 가시광선(Visible Ray):
빛은 우리 눈에 감지가 되는 특수한 형태의 전자기 방사(electromagnetic radiation)이다. 우리 눈에 보이는 빛 영역인 가시광선은 위 그림에서 색깔로 처리되어 확대하여 나타나 있다. 가시광선 영역은 파장의 길이가 약 0.43μm(보라색) ~ 0.79μm(빨간색)에 걸쳐 분포해 있다. 에너지가 강한 순서대로(주파수가 높고 파장이 짧은 순서) 나열해보면 보라, 파랑, 초록, 노랑, 오렌지색, 그리고 빨간색의 순으로 분포하며, 색의 변화는 연속적으로 변한다. 무지개 색을 떠올리면 쉽게 연상이 될 것이다.
인간은 눈으로 어떤 물체의 형태와 색깔을 인지할 수 있는데, 이러한 물체의 색깔은 물체가 반사하는 고유의 특성에 따라 인식된다. 쉽게 말해 물체의 표면 특성에 따라 전자기 스펙트럼의 영역에서 반사하는 정도가 다른 것이다. 예를 들어 초록색 공이 있다고 가정했을 때, 이 물체가 초록색으로 보이는 것은 공의 몸체가 500~570 nm 파장 영역의 빛을 주로 반사하는 반면, 다른 파장의 빛에너지는 대부분 흡수하기 때문이다. 위 그림에 보이는 사과가 빨갛게 보이는 까닭도 같은 이유에서다. 모든 파장의 빛을 고르게 반사하는 물체는 흰색으로 보인다.
- 단색광(monochromatic light):
색깔이 없는 빛을 우리는 단색광(monochromatic light)이라 한다. 이러한 단색광이 가지는 유일한 속성은 바로 빛의 밝기 강도(intensity)이다. 단색광은 우리 눈에 검은색에서 점차적으로 회색, 그리고 흰색으로 변하는 것으로 인식되기 때문에 보통 gray level이라는 용어가 이 단색광의 밝기 강도를 나타내기 위해 사용된다. 결국 intensity와 gray level은 같은 의미이다. 이렇게 검은색에서 회색, 그리고 흰색으로 변하는 범위를 우리는 gray scale이라고 하며, 이러한 gray scale을 사용하는 흑백 이미지를 gray scale image라고 부른다.
- 유색광(chromatic light):
유색광은 전자기 스펙트럼에서 대략 0.43μm(보라색) ~ 0.79μm(빨간색) 파장의 영역에서 분포한다. 유색광은 주파수와 함께 다음의 세 가지 요소들로 설명될 수 있다.
복사휘도(Radiance): 광원으로부터 흐르는 에너지의 실제 총량. 보통 와트(W, watts) 단위로 측정됨
발광휘도(Luminance): 관찰자가 감지할 수 있는 광원으로부터 흐르는 에너지의 양. 루멘스(lm, lumens) 단위로 측정됨
명도(Brightness): 인간이 느끼는 주관적인 빛의 밝기. 정확히 측정하기는 어렵다. 컬러 정보의 느낌을 기술하는데에 있어 핵심 요소임
위의 말을 토대로 판단해보자면 복사 휘도와 발광 휘도의 개념이 조금 헷갈릴 것이다. 이와 관련된 예를 들어보자.
어떤 광원으로부터 얼마간의 적외선(infrared)이 방출되었다. 이 광원으로부터 나온 빛은 얼마의 에너지, 즉 복사휘도(Radiance) 에너지를 가지고 있다. 그러나 관찰자는 이를 감지할 수 없었다. 이때의 발광휘도(Luminance)는 거의 제로에 가깝다. 즉 복사휘도와 발광휘도를 나누는 기준은 관찰자(사람)가 감지할 수 있느냐 없느냐에 달려있는 것이다. 정리하자면 복사휘도는 방출한 빛 에너지의 실제 총량을, 발광휘도는 관찰자를 기준으로 관찰자가 감지할 수 있는 빛 에너지의 총량을 나타내는 것이다.
- X선과 감마선(X-rays and Gamma radiation):
가시광선에 이어서 전자기 스펙트럼에서 높은 에너지를 가지는 영역을 살펴보자. 좌측 끝에는 X선(X-rays)과 감마선(gamma radiation)이 위치해 있다. 감마선은 의료, 우주, 원자력환경에서 중요한 역할을 한다. X선도 Hard(High energy)와 Soft(Low energy)의 경우로 나눌 수 있는데, Hard의 경우 산업현장에서, Soft의 경우 의료 분야에서 흉부나 치과 치료를 위한 이미지를 촬영하는데 사용된다.
이 밖에도 전자레인지에 사용되는 마이크로파(Microwaves), TV와 라디오에 사용되는 라디오파(radio wave)등이 있다.
비록 대부분의 이미지들이 전자기파에 의해 방출되는 에너지에 의해 형성된다곤 하지만, 어떤 이미지를 형성하기 위한 방법은 이것이 전부가 아니다. 예를 들면 물체로부터 반사되는 소리로부터 이미지를 형성하는 초음파 이미지(ultrasonic images)가 있다. 또한 전자현미경(electron microscopy)의 전자빔(electron beams)에 의해 형성된 이미지, 그래픽스(graphics)에 의해 합성된 이미지 등도 이러한 예 중 하나 이다.
지난 포스팅의 마지막 부분에 우리는 치환행렬(Permutation matrix)과 전치(Transpose)에 대해 간략히 언급하였다. 이번 포스팅의 서두에선 이에 대해 좀 더 이야기해보고 마무리 짓도록 하자.
1. Permutations
이전 포스팅에서 언급했듯이 치환 행렬(Permutation matrix)은 행 교환(row exchange)을 수행하는 행렬이다. 그렇다면 이러한 치환 행렬은 언제 필요할까? 우리는 지금까지 행렬의 소거를 하는 과정에서 행 교환이 필요없는 경우를 가정하고 소거를 진행하였다. 하지만 항상 완벽한 행렬만 존재할 수는 없기 때문에 반드시 행 교환이 필요할 때가 있다. 바로 pivot이 0인 경우다. 소거 과정에서 pivot이 0이 되는 경우에 행 교환이 필요하며 이때 사용되는 행렬이 바로 치환 행렬이다. 이러한 치환은 한 번이 될 수도, 혹은 여러 번이 필요할 수도 있다. 그때 마다 필요한 치환 행렬을 곱해서 행 교환을 해서 소거를 완료하는 것이다.
A=LU Decomposition을 살펴보자. 우선 A=LU의 형태는 아래와 같을 것이다. 지금까지 가졌던 가정은 A는 행 교환이 필요 없는 완벽한 행렬이라는 것이다. 따라서 P행렬도 필요 없었고, 여기서의 P행렬은 단위행렬이 될 것이다. 행 교환이 필요 없기 때문에 단위 행렬을 곱해서 행을 그대로 둔 채 소거를 해 나간다.
여기서 잠깐 실질적인 이야기를 해보자. 그렇다면 실제로 MATLAB과 같은 프로그램에서 이러한 소거 연산을 어떻게 수행할까? MATLAB에선 소거 연산을 수행할 때 우리가 체크하는 것과 같이 pivot이 0인지를 체크한다. 그런데 MATLAB은 여기서 한 가지 더 체크를 하는 것이 있다. 바로 pivot의 값이 충분히 큰지를 검사한다. 만약 pivot값이 0에 가깝다면 수치적으로(numerically) 좋지 않다. 대수적으론 이러한 과정이 필요하지 않지만, 수치 정확도(numerical accuracy)가 좋지 않아서 계산 결과가 좋지 않을 수 있다. 따라서 0에 가까운 pivot이 있을 경우 MATLAB은 행 교환 연산을 수행한다.
어쨋든 A=LU Decomposition을 할 때 행 교환이 필요한 경우 식이 아래와 같이 된다.
여기서 P는 행 교환 연산을 수행하는 치환행렬이고, 위 식은 어떤 invertible A에도 적용이 된다. 사실 대부분의 경우 행 교환이 필요하지 않는데, 가끔씩 행 교환이 필요한 경우 위와 같이 P행렬을 통해 행 교환 및 소거를 수행한다.
지난 포스팅(lecture 4)에서 언급했듯이 P행렬은 단위행렬에서 각 행을 서로 교환한 조합이다. 이를 다시 한 번 상기시키자면 아래 식과 같다.
단위 행렬도 하나의 치환 행렬에 포함되며 P12는 단위 행렬에서 row1과 row2를 교환한 행렬을 뜻한다. 자세한 사항은 lecture 4의 마지막 부분을 참고하자.
이러한 치환 행렬의 조합은 n!(factorial)만큼 된다. 즉 n=3일 때, 3x2x1=6가지 조합이 나올 수 있는 것이다.
치환 행렬은 편리한 속성이 두 가지 있다.
첫 번째는 모든 P행렬은 invertible하다. 즉 역행렬이 존재한다. (역행렬이 존재하는 단위행렬에서 행만 바꿨으므로 당연히...)
두 번째는 P행렬의 역행렬은 전치(Transpose)행렬과 같다. 즉 아래 식을 만족한다. (이 속성은 굉장히 편리하다)
2. Transpose
전치(Transpose)는 지난 포스팅에서도 잠깐 언급했지만, 좀 더 자세히 살펴보도록 하자. 일단 무작정 전치라는 연산을 한 번 해보자. 아래 행렬을 보자.
왼쪽의 3x2 행렬을 전치 했더니 오른쪽의 2x3형태의 행렬이 됐다. 쉽게 생각하면 행렬의 전치는 뒤집기다. 대각선을 축으로 180도 뒤집었다고 생각하면 된다. 그런데 행렬의 차원을 보니 row의 차원이 column차원으로, column의 차원이 row의 차원으로 변한 것을 볼 수 있다. 즉 row와 column이 바뀐 것으로 생각하면 된다. 이에 대한 정의를 아래와 같이 쓸 수 있다.
i는 row의 인덱스, j는 column의 인덱스인데 전치를 하면 이 두 인덱스가 바뀌게 된다. 즉 식 (6)에서 2를 보면 전치를 하기 전엔 A(2,1)이었지만, 전치를 한 후엔 A(1,2)의 자리로 간 것을 볼 수 있다.
3. 대칭 행렬(Symmetric Matrix)
이번에 알아볼 행렬의 형태는 특별한 형태이면서도 어떻게 보면 최고의 행렬 형태라고도 볼 수 있다. 바로 대칭 행렬(Symmetric Matrix)인데, 이 행렬이 가지고 있는 특성 때문에 다양한 곳에 응용된다.
이름 그대로 이 행렬의 특성은 대칭이라는 것이다. 즉 전치(Transpose)를 해서 행렬을 뒤집어도 원래 행렬과 같은 특성을 가진다. 아래 예를 보자.
식(8)의 행렬 A는 대칭 행렬이다. 일단 대각(diagonal) 원소를 보자. 대각 원소는 diag(3, 2, 4)인데, 이 대각 원소를 기준으로 상삼각(Upper triangular)과 하삼각(Lower Triangular) 부분이 같은 것을 알 수 있다. 따라서 전치를 통해 행렬을 대각 원소를 중심축으로 뒤집어도 그 결과는 같으며 차원 또한 변함이 없다.
그렇다면 우리는 이러한 대칭 행렬을 언제, 어떻게 구할 수 있을 까? 식 (6)의 R행렬을 다시 보자.
위의 R행렬은 대칭 행렬과는 거리가 많이 멀어보인다. R의 전치 행렬도 마찬가지다. 둘 다 직사각형 모양이다. 하지만! 우리는 이렇게 대칭 행렬과는 거리가 아주 멀어 보이는 행렬을 가지고 대칭 행렬을 얻을 수 있다. 바로 저 둘을 곱하면 된다. 실제로 한 번 해보자.
R행렬을 R의 전치 행렬과 곱했더니 우측의 S행렬이 나왔다. S행렬을 보면 대각 원소들을 기준으로 대칭인것을 한 눈에 알 수 있다. 이렇듯 어떤 행렬을 자신의 전치 행렬과 곱한 결과가 대칭 행렬이 나오는 이유는 다음과 같다. 자신과 똑같은 행렬을 단지 뒤집어서 곱했기 때문에 똑같은 원소 끼리의 곱이 반복될 수 밖에 없다. 아래의 연산 순서를 보자.
식 (10)은 식 (9)의 곱셈 과정을 순차적으로 나열한 것이다. 이를 보면 두 번째 연산과 네 번째 연산이 같은 원소끼리의 곱이 반복됨을 알 수 있다. 이렇게 같은 원소끼리 반복되는 연산은 대각 원소를 제외한 모든 원소에서 발생한다. 이러한 연산은 결코 우연이 아니라 필연적으로 일어날 수 밖에 없는 것이다. 결론적으로 아래의 정의를 얻을 수 있다.
어떤 임의의 행렬 A와 그의 전치 행렬(Transpose)을 곱하면 항상 대칭 행렬(Symmetric Matrix)을 얻는다!
위 정의를 수식으로 증명하자면 아래와 같다. 어떤 행렬이 대칭 행렬인지를 알기 위해선, 전치를 해 봤을 때 원래의 행렬과 같으면 우리는 이 행렬이 대칭 행렬인지를 알 수 있다.
전치의 전치는? 당연히 원래의 행렬일 것이다. 결과를 보라. 전치를 하기 전의 행렬과 같은 것을 알 수 있다. 위의 중요한 정의를 잘 기억해두자.
3. 마치며
이번 포스팅에선 치환 행렬(Permutation Matrix)과 전치(Transposes), 그리고 대칭 행렬(Symmetric Matrix)에 대해 알아보았다. 치환 행렬은 어떤 행렬의 왼쪽에 곱해져서 행 교환(row exchange)연산을 수행하고 전치는 row와 column의 index를 바꾸는 연산이다. 쉽게 말해 행렬을 대각선을 기준축으로 180도 회전시키는 것이다. 마지막으로 대칭 행렬에 대해 알아보았고, 대칭 행렬은 대각 원소를 기준으로 상삼각행렬과 하삼각행렬의 원소가 같은 행렬이며 전치 행렬이 원래 자기 자신과 같은 행렬임을 알았다. 또한 임의의 rectangular행렬 A에 대해 A의 전치 행렬에 A를 다시 곱하면 항상 대칭 행렬이 나옴을 알 수 있었다. 다음 포스팅에선 벡터 공간(Vector Spaces)에 대해 공부해 보도록 하자.
이번 포스팅에선 A=LU 분해(LU Decomposition)에 대해 알아보겠다. (LU Factorization이라고도 불린다. 그러나 앞으로 LU Decomposition이라 표현하겠다)
쉽게 말해 어떤 행렬 A가 있을 때, 이를 하삼각 행렬(Lower triangular matrix)과 상삼각 행렬(Upper triangular matrix)의 곱으로 분해하여 나타내는 것을 의미한다. A=LU에서 L과 U는 바로 Lower와 Upper의 처음 이니셜만 따서 표현한 것이다.
LU Decomposition은 가우스 소거(Gauss Elimination)에 의한 Elimination 행렬 형태로 볼 수 있으며, 때때로 치환행렬(permutation matrix, ※Lecture 2 참조)을 포함하기도 한다. 컴퓨터는 square 형태의 선형 방정식을 계산할 때 이 LU Decomposition을 사용하며, 역행렬(Inverse Matrix)을 계산하거나 행렬식(determinant)을 계산할 때 필요한 주요 과정이다.
1. 행렬곱셈의 Inverse
LU Decomposition을 알아보기 전에 먼저 행렬곱셈의 Inverse에 대해 잠깐 살펴보고 가도록 하자. LU Decomposition의 이해를 돕기 위함이다.
어떤 행렬 A가 있고 그의 역행렬을 알고 있을 때, 우리는 이 역행렬을 곱하면 단위행렬이 되는 것을 알고 있다. 이때 역행렬을 A의 왼쪽, 혹은 오른쪽에 곱해도 그 결과는 같다.
그렇다면 아래와 같이 non-singular이고 정방행렬(square matrix)인 A와 B가 있다고 가정하자. 이 두 행렬의 곱셈 AB의 뒤에 역행렬을 곱해 단위 행렬(Identity matrix)을 얻고자 할 때, 우리는 빈 칸에 들어갈 역행렬을 어떻게 곱해야 하는가? 식(1)과 같이 역행렬을 순서대로 곱해야 하는가?
정답은 반대의 순서로 역행렬을 곱해줘야 한다. 즉 B의 역행렬을 먼저 곱해주고 그 다음 A의 역행렬을 곱해줘야 한다. 아래 식 (3)-1을 보자. B와 B의 역행렬이 먼저 곱해져서 단위 행렬이 만들어진다. 이때 단위 행렬은 어디에 곱해도 결과는 변하지 않으므로 무시해도 된다. 결국 A와 A의 역행렬과의 곱이 되고 답은 단위행렬이 만들어진다. 식 (3)-2와 같이 순서가 바뀌어도 결과는 마찬가지다.
결국 단위행렬을 만들기위해 역행렬을 곱해줄 때에는 각 행렬의 역행렬이 본래 자신의 행렬과 붙을 수 있게, 즉 원래 행렬 곱셈의 반대 순서로 역행렬을 곱해주면 된다.
- Transpose:
이번엔 행렬 곱셈에 대한 전치(Transpose)에 대해 알아보자. 이후에 더 자세히 다루겠지만 transpose라는 것은 row의 원소들이 column이 되고, column의 원소들이 row의 원소가 되는 것이다. 쉽게 말해 식(4)와 같이 대각선을 중심축으로 행렬을 180도 돌려서 뒤집는 것이다.
그렇다면 행렬 곱셈에 이러한 transpose를 적용하면 어떻게 될까? 아래와 같이 정방행렬인 A와 A의 역행렬을 곱해서 단위 행렬을 만드는 식이 있을 때, 이 식을 transpose시켰다고 했을 때 결과는 식(5)의 마지막 줄과 같이 행렬 곱셈의 순서가 뒤바뀌게 된다.
우변의 I는 그대로 I가 되고 좌변의 A와 A inverse는 곱하는 순서가 반대로 된다.
또한 식(5)의 마지막 줄에서 A의 역행렬의 transpose는 => A의 transpose의 역행렬로 바꿔 쓸 수 있다. 단 이 규칙은 각각의 단일 행렬에 대해서만 적용된다. 식 (6)을 참고하자.
2. LU Decomposition
- What and why Decomposition?:
Decomposition(Factorization)이라는 것은 말 그대로 분해하는 것을 의미한다. 쉽게 말해 어떤 시스템 혹은 데이터를 표현한 행렬 A를 인수분해 한다는 뜻이다. 우리가 중고등학교때 배우던 그 인수분해처럼 말이다. 위키 사전에는 이 행렬 분해(Matrix Decomposition)의 정의를 다음과 같이 정리하였다.
선형대수에서 Matrix Decomposition은 어떤 행렬(Matrix)을 여러 행렬들의 곱으로 표현하는 것을 의미한다.
그렇다면 이러한 Matrix Decomposition은 왜 하는 것일까? 그 해답은 바로 우리가 중학교때 배웠던 인수분해를 하는 이유와 같은 맥락이다. 우리가 어떤 방정식을 인수분해 하는 이유는 바로 그 방정식의 해를 구하기 위해서다. 혹은 해를 좀 더 쉽게 구하기 위해서, 방정식을 좀 더 알아보기 쉽게 하기 위해서, 특수한 상황에서 문제를 풀기 쉽게 하도록 하기 위해서 등이다.
Matrix Decomposition도 마찬가지이다. (http://www.ece.northwestern.edu/~mya671/files/Matrix_YM_.pdf) 에선 Matrix Decomposition의 목적을 크게 두 가지라고 하였다. 첫 번째는 계산의 편리함(computational convenience), 두 번째는 분석적 용이성(analytic simplicity)을 위함이다. 결국 Matrix Decomposition을 하는 이유는 계산을 좀 더 편리하게 하고 어려운 문제를 쉽게 풀기위해, 시스템 행렬을 단순화시켜 표현하여 분석을 용이하게 하기 위함이다.
행렬 분해는 다양한 방법들이 존재한다. SVD(Singular Value Decomposition), QR Decomposition 등등 다양한 방법들이 존재하며, 각 방법들은 각자 고유의 분해 특성들을 가지며 다양한 문제를 푸는데 사용된다. 여기서 우리는 행렬 분해 방법들 중 가장 기본적인 형태인 LU Decomposition에 대해 알아보자.
- LU Decomposition(Factorization):
어떤 행렬 A가 있고 이 행렬은 역행렬을 가질 수 있는 정방행렬이고, 역행렬을 구하기 위해 소거를 하는 과정에서 Row exchange도 필요 없는 아주 좋은 형태의 행렬이 있다고 가정해보자.
우리는 A에 소거법을 적용해서 최종적으로 U행렬을 만드는 것을 지난 포스팅(Lecture 2)에서 배웠다. 여기서 우리는 A와 U사이의 연결 고리를 알아야 한다. 즉 A가 U와 어떻게 연결이 되는지 말이다. 식으로부터 짐작하신 분들도 있겠지만, 바로 L행렬이 이 연결고리가 된다.
이 연결고리인 L행렬이 어떻게 만들어 지는지 실제 계산을 통해 알아보자.
아래와 같이 2x2크기인 비 특이행렬(non-singular Matrix) A가 있다.
자 이제 A행렬을 소거하여 만들어지는 상삼각행렬(Upper Triangular Matrix)인 U행렬을 만들기 위해 E21행렬을 만들어보자. (E21은 A의 row2, column1의 원소인 8을 제거하기 위한 Elementary or Elimination Matrix라는 의미다)
E21행렬은 어떻게 만드는가? 일단 A에서 pivot은 2이다. 이 pivot의 column에서 바로 아래에 있는 원소 8을 제거해야 하는데 바로 위의 pivot인 2와 딱 4배 차이가 난다. 따라서 row1[2 1]에 4를 곱한다음 row2[8 7]에서 row1을 뺀 결과값을 row2에 대입하면 될 것이다. 즉 아래 식과 같다.
그렇다면 이렇게 되기 위해선 E21행렬의 원소들이 어떻게 배치되어야 할까?
pivot이 있는 A의 row1은 그대로 유지되어야 한다. E21의 row1은 그렇다면 1*[2 1] + 0*[8 7]이므로 [1 0]이 되어야 한다.
E21의 row2는 어떻게 되어야 할까? -4*[2 1] + 1*[8 7] 이므로 [-4 1]이 되어야 할 것이다. 결국 식 (9)와 같이 E21이 만들어 질 것이다.
(※소거와 관련된 내용은 Lecture 2참고)
자 이렇게 만들고 보니 처음에 구하고자 했던 A=LU와는 다른 형태지만 어떤 처리를 하면 뭔가 나올 것만 같다. 눈치 채셨는가?
그렇다. 그것은 바로 좌변과 우변의 왼쪽에 E21의 역행렬을 각각 곱해주면 될 것이다. 즉
결국 소거행렬(Elimination Matrix) E21의 역행렬이 L행렬인 것이다. 이때 L은 하삼각행렬(Lower Triangular Matrix)의 형태를 띄게 된다.
이제 E21역행렬을 구하면 된다. E21의 역행렬은? 바로 -4의 부호만 +로 바꿔주면 된다. 역행렬이라는 것이 곱해서 단위행렬을 만들어야 하기 때문이란 것을 안다면 쉽게 유추할 수 있다. 방금 전 E21을 만들 때와 같이 -4를 소거하여 0으로 만들 방법을 생각하면 쉽게 만들 수 있다.
이렇게 구한 E21의 역행렬은 결국 L이 되고 L과 U를 실제로 곱해보면 A가 나오는 것을 확인할 수 있다. 식 (11)은 A=LU를 나타낸 것이다.
- LDU Decomposition:
어떤 경우에 이 Pivot들만 따로 떼어서 분해해야 하고 싶을 때도 있다. U행렬은 대각선으로 두 개의 pivot인 2와 3을 가지고 있다. 첫 번째 pivot이 2, 두 번째 pivot이 3이다. 만약 이 pivot들만 따로 분리하여 행렬을 만들고 싶을 때 우리는 다음과 같이 할 수 있다.
U행렬에서 각 pivot이 속해있는 row를 해당 pivot으로 나누어준다. 그 결과값을 새로운 U의 각 row에 넣고 pivot들만 대각선으로 나열되어 있는 행렬을 써주면 된다. 즉 아래 그림과 같이 하면 된다.
연산 자체가 간단하기 때문에 따로 부연설명은 하지 않겠다.
이렇게 해서 만들어진 행렬의 조합을 우리는 LDU Decomposition Matrix라 한다. 여기서 D는 Diagonal Matrix의 뜻이며 대각선 방향의 원소만 가지고 있는 대각 행렬을 의미한다. 왼쪽엔 하삼각행렬(Lower Triangular Matrix), 가운데는 Pivot들만 있는 대각행렬(Diagonal Matrix), 우측엔 상삼각행렬(Upper Triangular Matrix)이 위치해있는 형태이다.
- 3x3 case:
이제 3x3크기의 3차원 행렬을 생각해보자. 3x3크기의 행렬 A가 있다고 가정해보자. 이 행렬을 소거하기 위해 먼저 곱해야 할 E행렬은 E21일 것이다. 그 다음으로 E31, E32순으로 곱해서 소거를 해야 한다는 것을 이미 배웠다. 이때 Row exchange는 필요 없는 이상적인 경우로 가정한다. 이를 식으로 나타내면 아래와 같을 것이다.
그 다음 단계는 왼쪽의 E행렬들을 없애서 A=의 꼴로 만들어야 한다. 식 (10)을 참고하여 식 (13)의 왼쪽에 E32, E31, E21순으로 역행렬들을 곱하여 아래와 같은 식으로 만들어준다. 결국 식의 우변은 E21*E31*E32의 역행렬들의 곱이 L이 된다.
우리는 식 (13)에 각 E의 역행렬들을 곱하여 식 (14)의 A=LU형태의 식을 만들었다. 즉 행렬 A와 U간의 연결고리인 L을 만들어 낸 것인데, 사실 (13)의 앞에 곱해진 E도 A와 U의 연결고리라고 볼 수 있다. 결국 U를 만들기위한 방법은 E와 L 두 가지가 있는 셈인데, 결론적으로 보면 이 두 가지 방법중 L이 더 좋은 형태라고 볼 수 있다.
다시말하면
의 형태보다
의 형태가 더 좋은 형태이다.
지금부터 왜 두 번째 형태가 더 나은지 설명하겠다.
위에서 살펴봤던 2x2인 경우에는 E행렬이 단 한개라서 별다른 문제는 없다. 그러나 3x3은 다르다. 다음 A행렬을 보자.
Linear Algebra Lecture 2를 참고하여 A 소거법을 적용해보자. 결과는 아래 식 (16)과 같아진다. 여기서 E31은 단위행렬이 되는데, 이렇게 되면 E31은 곱셈에서 무시해도 무방하다. 참고로 소거법의 특성상 E행렬들은 언제나 하삼각행렬의 형태이다. 이렇게 나오는 이유는 소거 과정에서 pivot의 row는 소거하지 않기 때문에 이와 같은 형태가 나오는 것이다.
어쨋든 E행렬을 살펴보자. E32의 -5, E21의 -2는 E행렬에서 각자의 위치에 그대로 위치해있고 E행렬의 row3, column1의 자리에 10이라는 새로운 숫자가 생겨났다. 이것이 의미하는 것이 무엇일까? (-5와 -2는 소거 과정에서 pivot row에 곱해지는 multiplier임을 기억하자.)
그 다음으로 L을 살펴보자. E21 역행렬의 2, E32 역행렬의 5가 L에서 각자 위치에 그대로 위치해 있고 따로 추가되는 숫자는 없다. 이것이 의미하는것이 무엇일까?
행렬 E를 A에 곱하게 되면 E의 10은 A의 row1에 곱해지게 된다. 즉 10이라는 숫자가 A의 row1에 커다란 영향을 미친다는 것이다. 물론 답은 U가 그대로 나오게 된다. 그러나 그 연산 과정에서 A에 뭔가 큰 영향을 미치게 된다.
반면 L의 경우엔 따로 추가되는 숫자 없이 2와 5가 각자의 자리에 위치한 상태로 L이 계산된다. 즉 10과 같이 뭔가 방해를 하는 숫자를 만들어내지 않는다는 것이다. EA=U와 달리 A=LU는 A를 신경쓰지 않아도 되는 것이다. 결국 A와 U의 연결고리로써 E보다는 L이 좀 더 나은 표현이다.
정리하자면..
A=LU Decomposition에서
만약 행 교환(row exchanges)이 없다면, 소거에 사용되는 multiplier들은 L행렬의 각자 위치에 그대로 들어간다.
- Permutations:
지난 포스팅에서 잠깐 다룬적이 있던 치환행렬(Permutation Matrix)을 다시 살펴보자. 지금까지는 행 교환(row exchanges)이 필요 없는 경우를 가정하고 LU Decomposition을 설명했다. 그러나 행 교환이 필요한 경우가 반드시 생긴다. 이렇게 행 교환이 필요한 경우 사용하는 방법이 치환행렬을 곱해주는 것이다.
3x3 치환행렬을 살펴보자.
비록 아무런 변화가 없긴 하지만 단위행렬도 치환행렬의 한 종류이다. n=3인 정방행렬일 때 치환행렬의 종류는 어떤 것들이 있을까?
먼저 P12를 생각해볼 수 있다. P는 Permutation의 P를 따온 것이고 12는 row1와 row2를 교환한다는 뜻이다.
P13, P23을 어렵지않게 생각할 수 있는데, 이것 말고도 조합이 더 있다. 아래 식 (16)을 보자.
P23에 P13을 곱한 행렬, 그리고 P23에 P12를 곱한 행렬을 생각할 수 있다. 각 치환 행렬을 row로 봤을 때, 각 row가 단위 행렬과 비교해서 몇 번째 줄에 위치했는지를 살펴보면 어느 row로 바뀌는지 쉽게 유추할 수 있다.
이러한 치환 행렬의 조합의 개수는 어떻게 계산할 수 있을까? 바로 n!(factorial)로 계산한다. 즉 n=3일 경우, 3x2x1=6가지의 조합이 나오는 것이다.
치환 행렬은 앞서 말했듯 row를 바꿔주는 역할을 하는 것이다. 그렇다면 다시 원래대로 되돌려 놓으려면 어떻게 해야 할까? 바로 역행렬을 곱해주면 되는데, 사실 원래 행렬과 역행렬은 같다. 왜냐하면 P12가 row1과 row2를 바꾸는 치환 행렬일 때 다시 원래대로 돌려 놓으려면 똑같이 row1과 row2를 바꿔주면 되기 때문에 다시 P12를 곱해주면 된다. 실제 계산해봐도 같은 결과가 나오는데, 이는 치환 행렬 자체가 대각 원소들을 기준으로 좌우가 대칭이기 때문이다. 이런 좌우 대칭인 경우 역행렬은 전치(Transpose)로 구할 수 있다.
또한 P13P23은 P12P23과 역행렬 혹은 전치 관계인 것을 알 수 있다.
우리는 행 교환이 필요한 A=LU Decomposition을 할 때 이러한 치환 행렬을 곱하여 PA=LU와 같은 꼴로 Decomposition을 할 수 있다.
3. MATLAB 활용법
LU Decomposition을 MATLAB을 이용해 간단히 구할 수 있다. 아래는 위의 식 (15)를 MATLAB으로 구현한 코드이다.
위 코드를 실행시키면 아래와 같은 결과가 나온다.
위 결과에서 ans는 앞에서 계산한 L과 U를 곱하여 나온 결과 행렬이다. 원래의 A행렬과 똑같이 나오는 것을 볼 수 있다.
MATLAB에서는 LU Decomposition을 위한 함수를 제공한다. 아래 코드는 MATLAB에서 제공하는 함수를 이용해 LU Decomposition을 수행하는 코드이다.
함수 이름은 lu()이고 괄호안에 Decomposition을 할 함수를 파라미터로 넣으면 된다. 이때 좌변에 대괄호를 이용하여 출력 인수들을 정의해 줘야 한다. 첫 번째 방법은 L과 U만 출력 인수로 정의해준 것이다. 이에 대한 결과는 아래와 같다.
결과를 보면 L의 경우 하삼각행렬 형태가 아닐 것이다. 왜 이렇게 나오는지에 대해서 이해하기 위해선 우선 다음의 정의를 이해해야 한다. 선형 시스템(Linear System)의 표현은 유일하지 않다. 아래 식을 보자.
위의 식에서 첫 번째 식과 두 번째 식은 완전히 똑같은 시스템을 표현하고 있다. 여기서 좌변의 행렬의 행이 바뀌면 우변의 결과 벡터도 똑같은 순서로 행이 교환된다는 것을 기억하자.
위의 개념을 생각했을 때, LU Decomposition은 사실 일반적으로PA=LU와 같이 표현할 수 있다. 여기서 P는 치환 행렬(Permutation Matrix)를 의미한다. MATLAB에서 [L U] = lu(A)와 같이 L과 U만 출력인수로 정할 경우, L은 아래 식과 같이 정의 되어 나오는 것이다.
즉 [L U] = lu(A)로 구한 L은 사실은 P'L인 것이다. 이는 L과 U를 곱했을 때 원래의 A행렬 형태가 나오도록 만들기 위해 치환 행렬을 L에 미리 곱해준 것이라 생각하면 된다. ans는 lu()함수로 구한 L과 U를 곱해서 나온 결과이고 원래의 A와 정확히 일치하는 것을 볼 수 있다.
출력 인수를 [L U P] = lu(A)와 같이 L, U, P 세 개로 정의할 경우, L은 우리가 생각하는 하삼각행렬의 형태, 즉 P의 역행렬이 곱해지지 않은 형태로 L이 계산된다. 아래는 이에 대한 결과이다.
L은 하삼각행렬, U는 상삼각행렬, P는 치환행렬이다. 즉 PA=LU형태로 계산 결과가 나오는 것이다. 이렇게 계산된 결과값을 이용해서 PA와 LU를 실제로 비교해보자. 정확히 같은 값이 나오는 것을 알 수 있다.
그런데 우리가 손으로 계산한 결과들과는 실제로 값이 다르다. 이는 내부 계산과정에서 수치적으로 최적화된 계산 알고리즘을 통해 Decomposition을 하기 때문에 알고리즘마다 값이 약간씩 다르게 나올 수 있다. 어쨋든 결과적으로는 맞게 분해가 된 것이 맞다.
MATLAB에서 제공하는 LU Decomposition함수는 이 외에도 다양한 파라미터들을 설정할 수 있다. 자세한 내용이 궁금하다면 구글에 검색을 해보거나 help명령어, 혹은 MATLAB 스크립트의 lu()함수에 마우스 커서를 놓고 Ctrl+D를 누르면 상세한 도움말을 볼 수 있다.
4. 마치며
이번 포스팅에선 어떤 시스템 행렬 A를 L(Lower Triangular Matrix)과 U(Upper Triangular Matrix)로 분해(Decomposition)하는 방법을 배웠다. 이를 통해 A와 U사이의 관계를 이어주는 L행렬을 정의할 수 있었고 L과 소거 행렬 E와의 관계를 확인할 수 있었다. 또한 Row exchange가 필요한 경우 사용되는 치환행렬(Permutation Matrix)을 공부했고 이에 대한 전치(Transpose)도 공부하였다. 다음 포스팅에선 이 치환 행렬과 전치에 대해 좀 더 알아보도록 하자.
