Solving ((A))((x)) ((=)) ((b)) (When ((n)) x ((n))) - part 1

 

 

 

오늘은 ((A))((x)) = ((b))를 풀어야하는 상황에서 ((A))가 ((n)) x ((n)) 꼴의 정방행렬일 때 이를 푸는 방법에 대해서 다뤄볼 예정입니다.

 

두 개의 파트로 나누어서 다뤄볼 것인데, part 1에서는 문제에 대한 접근 전략을, part 2에서는 이를 이용해 문제를 해결하는 과정을 다뤄볼 것입니다.

 

Solving ((A))((x)) = ((b)) (When A is n x n))

---

 

Triangular Matrix

 

Triangular matrix, 즉 삼각행렬은 행렬의 주 대각선 성분 위쪽 또는 아래쪽의 성분들이 모두 0인 행렬을 말합니다.

 

위쪽이 모두 0이면 아래쪽에만 숫자들이 있으니 Lower triangular matrix,

아래쪽이 모두 0이면 위쪽에만 숫자들이 있으니 Upper triangular matrix라고 합니다.

 

예시를 볼까요?

 

L for Lower triangular matrix

 

이렇게 ((l))들 빼고 나머지가 모두 0인, 행렬의 가장 가운데의 대각선(주대각선) 밑으로만 숫자가 차있는 경우에는 Lower triangular matrix라고 합니다. 대문자 ((L))로 표기합니다.

 

U for Upper triangular matrix

 

이렇게 ((u))들 빼고 나머지가 전부 0인, 행렬의 가장 가운데의 대각선(주대각선) 위로만 숫자가 차있는 경우에는 Upper triangular matrix라고 합니다. 대문자 ((U))로 표기합니다.

 

---

 

 

Backsubstitution(후방대입법)

 

선형대수학의 목적은 선형방정식들을 푸는 것이고, 이는 ((A))((x)) = ((b))의 해를 구하는 것입니다. 하지만, 이전 역행렬 게시물에서 언급하였듯이, 보통은 해를 ((x)) = ((A^{-1}))((b))로 풀지만, ((A^{-1}))를 구하는 것이 computationally inefficient하다고 하였습니다. 

 

그러면, 만약에 우리에게 주어진 문제인 ((A))((x)) = ((b)) 상황에서, ((A))가 Upper triangle matrix, 즉 ((U))의 꼴을 하고 있다면 어떻게 될까요?

 

여기서 Backsubstitution이 등장합니다. Backsubstitution은 간단하게 말씀드리면 "밑에서부터 대입한다" 입니다. 무슨 뜻인지 예시와 함께 같이 보겠습니다.

 

 

우리가 풀어야하는 선형방정식들이 이렇게 주어져있다고 해보겠습니다. 이 형태는 어떤 방정식들일까요?

 

((2x₁)) + ((3x₂)) + ((4x₃)) = ((19))
((0x₁)) + ((5x₂)) + ((6x₃)) = ((17))
((0x₁)) + ((0x₂)) + ((7x₃)) = ((14))

 

 

바로 이런 방정식들을 행렬로 표현해놓은 것입니다. 실제로 행렬 x 벡터 연산을 해보면 연산이 동일한 과정으로 수행되는 것을 알 수 있습니다. 그런데 지금 보시면 Upper triangle matrix의 선천적인 특징으로 인해 밑에 숫자들이 0인 것을 볼 수 있습니다. 그러면 없어지겠죠.

 

 

없어진 후 결과를 다시 한 번 써보도록 하겠습니다.

 

((2x₁)) + ((3x₂)) + ((4x₃)) = ((19))
((0)) + ((5x₂)) + ((6x₃)) = ((17))
((0)) + ((0)) + ((7x₃)) = ((14))

 

 

다시 써볼까요?

 

((2x₁)) + ((3x₂)) + ((4x₃)) = ((19))
((5x₂)) + ((6x₃)) = ((17))
((7x₃)) = ((14))

 

 

가장 마지막으로 다시 쓴 식을 보면, ((7x₃)) = ((14)) 입니다. 우리는 ((x₃)) = ((2)) 라는 사실을 매우 쉽게 알 수 있습니다. Upper triangle matrix의 특성 때문입니다. 마지막 변수 빼고 다 0이니까요. 마지막 변수 ((x₃)) 을 그냥 알려주는 셈입니다.

 

그렇다면 그대로 위에 대입해보겠습니다. 바로 위를 보면 또 ((x₁))은 없고, ((x₂))랑 우리가 이미 알고 있는 ((x₃)) 만으로 이루어진 식이 하나 있습니다. 이것도 거져먹기죠. 이미 ((x₃)) = ((2))니까 6 x 2 = 12, 그러므로 5((x₂))가 5가 되어야합니다. ((x₂)) = ((1)) 이라는 것을 또 한 번에 매우 쉽게 알 수 있습니다.

 

벌써 3개의 변수 중에 2개의 변수 값을 거져먹었으므로 ((x₁))도 바로 알 수 있습니다.

2((x₁)) + 3 + 8 = 19니까, ((x₁)) = 4 이렇게 구해지네요. 

 

 

이렇게 우리에게 주어진 선형대수 문제인 ((A))((x)) = ((b)) 에서 ((A))가 ((U))라면, 즉 ((U))((x)) = ((c)) 꼴이라면 ((A))에 대한 "역행렬을 구하지 않고도" 매우 쉽게, 그냥 값을 대입하는 것만으로도 해를 구할 수 있습니다. 이제 우리가 취할 전략에 대해서 좀 감이 오시나요?

 

 

우리는 ((A))를 ((U))꼴로 바꿀 것입니다. 

 

 

part 2에서는 이를 어떻게 바꾸는지, LU factorization에 대해서 다뤄보도록 하겠습니다.