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

 

오늘은 지난 게시물에 이어서 ((A))((x)) ((=)) ((b))를 풀어야하는 상황에서 ((A))가 ((n)) x ((n)) 정방행렬일 때 이를 푸는 과정에 대해서 마저 다뤄보겠습니다. 

---

 

Part 1에서는 문제에 대한 접근 전략을 소개해드렸습니다. 바로 ((A))((x)) = ((b))의 ((A))를 더 계산하기 쉬운 ((U))꼴로 바꿀 것이라는 접근 전략입니다. 이를 LU factorization이라고 합니다. Upper triangular matrix인 ((U))꼴과 문제 에 대한 접근 전략을 다시 한 번 더 보시려면 아래의 part 1 게시물을 참고하시면 되겠습니다.

 

https://jaehoonstudy.tistory.com/11

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

 

---

 

Elementary Row Operations(기본 행연산)

 

먼저 행렬의 기본 행 연산에 대해서 알아보겠습니다. 우리는 다음과 같은 기본 행 연산을 이용해서 ((A))를 ((U))꼴로 만들 것입니다.

단, ((k))는 0이 아닌 스칼라값입니다.

 

• 서로 다른 두 행을 바꾼다.
• 한 행에 ((k))배를 한다.
• 한 행에 다른 행의 ((k))배를 더한다.

우리가 보통 연립방정식을 풀 때 앞에 있는 상수를 같게 만들어주기 위해 어떤 수를 곱해주고, 가감법으로 다른 식에 더하거나 빼서 변수를 없애 연립방정식을 푸는 전략을 취하는데, 그것의 개념이라고 생각하시면 될 것 같습니다.

 

---

 

Gaussian Elimination(가우스 소거법) - U of LU factorization

 

이제 본격적으로 ((A))를 ((U))로 만들어보겠습니다. 이를 위해서는 Gaussian Elimination(가우스 소거법)을 해주어야 합니다. 위에서 다루었던 기본 행연산들을 연속적으로 적용하여 행렬의 왼쪽 아래 항들이 최대한 모두 0이 되도록 해볼 것입니다. 

 

이 연산들을 이용하면, 행렬은 항상 Row echelon form의 형태를 한 Upper triangular matrix로 만들 수 있습니다. Row echelon form은 잠깐 뒤로 미뤄두고, Gaussian Elimination이 어떻게 이루어지는지 예시를 통해 한 번 알아보도록 하겠습니다.

 

 

 

A가 다음과 같은 행렬이라고 해보겠습니다. 우리의 목표는 ((U)), 즉 왼쪽 아래부분이 전부 0이 되었으면 합니다. 그럼 행렬의 맨 처음인, 왼쪽 맨 위 원소이자 첫 pivot인 2 아래에 있는 4를 없애보겠습니다.

 

Pivot은 특정 계산(가우스 소거법, 단순 알고리즘 등)을 수행하기 위한 임의의 알고리즘에 의해 먼저 선택된 행렬의 성분입니다. 

 

4를 없애기 위해 "첫 행에 곱하기 2"를 해서 밑에서 빼보겠습니다.

 

 

4에서 2x2를 뺐으니 0, 11에서 3x2를 뺐으니 5, 14에서 4x2를 뺐으니 6이 나오는 것을 볼 수 있습니다. 

 

여전히 왼쪽 주대각선 아래에는 2와 8이 남아있으니, 마저 없애보도록 하겠습니다. 다음은 왼쪽 맨 아래의 2를 없애보겠습니다. 이를 위해 "첫 행에 곱하기 1"을 해서 마지막 행에서 한 번 빼주겠습니다. 

 

 

2에서 2x1을 뺐으니 0, 8에서 3x1을 뺐으니 5, 17에서 4x1을 뺐으니 13이 나오는 것을 볼 수 있습니다.

 

마지막으로 왼쪽 주대각선 아래에는 5가 남아있습니다. 그런데 5 바로 위를 보면 같은 5가 있는 것을 볼 수 있습니다.

"두 번째 행에 곱하기 1"을 해서 마지막 행에서 한 번 빼주겠습니다.

 

 

 

이렇게 연산 결과 행렬의 주대각선 아래 성분들이 모두 0이 되었고, 위쪽만 차있는 Upper triangle matrix가 된 것을 볼 수 있습니다.

 

---

 

Row echelon form(행사다리꼴)

 

Row echelon form은 간단히 REF로 표기하기도 합니다. 먼저 leading entry의 뜻을 알아야합니다. leading entry란, 행렬의 각 행을 왼쪽에서부터 읽었을 때, 처음으로 0이 아닌 성분을 뜻합니다. 

 

 

여기서 각 행의 leading entry는 각각 2, 5, 5인 것을 알 수 있습니다. 

 

Row echelon form은 다음과 같은 조건들을 만족하는 행렬을 뜻합니다.

 

• 성분이 모두 0인 행은 모두 최하단에 위치한다(성분이 모두 0인 행이 없어도 되고, 많아도 된다).
• 행들의 leading entry를 비교했을 때, 어떤 행보다 위에 있는 행의 leading entry는 항상 더 왼쪽에 있어야 한다.

우리의 최종 ((U))를 확인해보면, 

 

leading entry들인 2, 5, 7이 계단식으로, 행이 아래로 갈수록 leading entry들이 오른쪽으로 밀려나는 형태인 것을 볼 수가 있습니다. 조건을 만족하므로 우리의 ((U))는 row echelon form입니다.

 

---

 

L of LU factorization

 

자, 이제 우리의 ((U))를 구했습니다. 그런데 혹시 기억나시나요? 우리의 접근 전략의 이름은 LU factorization이었습니다. Factorization은 말그대로 행렬을 분해하는 것입니다. 그렇다면 이를 직역하면 ((A))를 ((L))과 ((U))로 분해한다는 뜻입니다. ((U))는 구했는데, ((L))은 어떻게 구할까요?

 

혹시 눈치채신 분들이 있을지 모르겠지만, 제가 가우스 소거법의 과정을 짚어가며 설명드릴 때 ""로 강조표시를 한 부분이 있습니다. 

 

 

바로 우리가 행 연산을 했던 과정들과 곱해준 ((k)) 상수들입니다. 이들이 바로 ((L))을 구성합니다.

 

((L))을 구성하는 방법은, 우리가 위에서 말로 해준 "2행 - 1행x2" , "3행 - 1행x1", "3행 - 2행 x1" 들을 수학적 방식으로, 일련의 행렬 간의 곱하기 연산들로 표현하는 것입니다. 먼저 다음을 보시겠습니다.

 

우리가 이전에 다루었던, 행렬 간 곱셈을 연산하는 4가지 방법 중에 3번째로 다룬 방법입니다. 앞의 행렬의 성분들을 뒤 행렬의 행들의 linear combination으로 해석하여 곱셈을 하는 방법입니다.

 

다시 보고싶으시다면 https://jaehoonstudy.tistory.com/7 을 참조하시면 되겠습니다.

행렬의 곱셈(Matrix-Matrix Multiplication)

 

이 방법을 쓸 겁니다. 하나하나 차근차근 설명해보겠습니다. 우선 곱셈이 어떻게 작동하는지 보기 위해 Identity matrix와 연산했을 때 어떻게 되는지 보도록 하겠습니다. 

 

((\begin{bmatrix}
1 & 0 & 0\\ 
0 & 1 & 0\\ 
0 & 0 & 1
\end{bmatrix})) ((\begin{bmatrix}
2 & 3 & 4\\ 
4 & 11 & 14\\ 
2 & 8 & 17
\end{bmatrix}))

 

앞이 Identity matrix이고, 뒤가 계속 다루고 있는 우리의 ((A))입니다. Identity matrix ((I))는 이를 어떤 행렬과 곱해도 그 행렬이 그대로 나온다는 성질을 가지고 있습니다. 이 연산을 행렬의 곱셈 중 3번째 관점인 뒤 행렬들의 행들의 조합으로 해석하고 계산을 한다면, 

 

1 x A의 1행 + 0 x A의 2행 + 0 x A의 3행 → 결과 행렬의 1행
0 x A의 1행 + 1 x A의 2행 + 0 x A의 3행 → 결과 행렬의 2행
0 x A의 1행 + 0 x A의 2행 + 1 x A의 3행 → 결과 행렬의 3행

 

 

이렇게 됩니다. 볼드체의 구조대로 Identity matrix가 있음을 볼 수 있습니다. 그렇다면, 우리가 처음에 한 가우스 소거법의 과정인 "첫 행에 곱하기 2를 해서 두 번째 행에서 빼준다"는 어떻게 행렬로 나타낼 수 있을까요? 

 

일단 최종적으로 두 번째 행에서 빼주는 것이기 때문에 두 번째 행에 변화가 가해지는 것입니다. 그러므로 두 번째 행이 결과적으로 바뀌어야겠죠. 위에서 결과 행렬의 2행에 영향을 미치는 부분은 0 1 0 이 부분입니다. 일단 나머지는 지금 건드릴 필요가 없죠. 그대로 ((A))이면 되기 때문에 Identity matrix의 형태로 놔둘것입니다. 그러면 Identity matrix의 0 1 0 두 번째 행 부분을 바꿔봐야겠다는 결론이 나옵니다.

 

((\begin{bmatrix}
1 & 0 & 0\\ 
? & ? & ?\\ 
0 & 0 & 1
\end{bmatrix}))

 

자 이제 위의 ? 부분에서 할 일은 ((A))의 첫 행에 곱하기 2를 해서 두 번째 행에서 빼준다 입니다. 그런데 아까 0 1 0 이었을 때 위 계산방식을 살펴보면, (0 x A의 1행) + (1 x A의 2행) + (0 x A의 3행) → (결과 행렬의 2행) 이런 식으로 작동합니다. 

 

또한, 첫 행에 곱하기 2를 해서 두 번째 행에서 빼준다 = 첫 행에 -2배를 해서 두 번째 행에 더한다 라는 뜻과 동일합니다. 그렇다면 1행에 -2배를 하고, 2행은 더하기 위해 존재해야하니 x 1을 하고, 3행은 영향을 끼치면 안되니까 x 0을 해줘야합니다. 이를 그대로 수식으로 풀면,

 

(-2 x A의 1행) + (1 x A의 2행) + (0 x A의 3행) → (결과 행렬의 2행)

 

이렇게 됩니다. 그렇다면 A에 가하는 첫 번째 행렬 연산은 바로 다음과 같이 될 것입니다.

 

((\begin{bmatrix}
1 & 0 & 0\\ 
-2 & 1 & 0\\ 
0 & 0 & 1
\end{bmatrix}))

 

두 번째 연산인 "첫 행에 곱하기 1을 해서 마지막 행에서 한 번 빼주겠습니다" 는 어떻게 처리해야할까요?

위의 방법과 동일합니다. 이번에는 최종적으로 마지막 행에서 한 번 빼주겠습니다 라고 나와있기 때문에 마지막 행인 3행에 변화를 가해야겠죠? 

 

1 x A의 1행 + 0 x A의 2행 + 0 x A의 3행 → 결과 행렬의 1행
0 x A의 1행 + 1 x A의 2행 + 0 x A의 3행 → 결과 행렬의 2행
0 x A의 1행 + 0 x A의 2행 + 1 x A의 3행 → 결과 행렬의 3행

 

결과 행렬의 3행에 영향을 미치는 부분은 0 0 1 이 부분이므로 여기를 건드려야한다는 생각이 들 것입니다. 

 

((\begin{bmatrix}
1 & 0 & 0\\ 
0 & 1 & 0\\ 
? & ? & ?
\end{bmatrix}))

 

자 이제 위의 ? 부분에서 할 일은 ((A))의 첫 행에 곱하기 1를 해서 마지막 행에서 빼준다 입니다. 그런데 아까 0 0 1 이었을 때 위 계산방식을 살펴보면, (0 x A의 1행) + (0 x A의 2행) + (1 x A의 3행) → (결과 행렬의 3행) 이런 식으로 작동합니다.

 

Identity matrix는 결과 행렬의 3행을 결정하는 위치에서, A의 3행만 남기고 나머지는 0으로 다 지워버리는 것이죠. 

 

그렇다면 여기도 마찬가지로 첫 행에 곱하기 1을 해서 3행에서 빼준다 = 첫 행에 곱하기 -1을 해서 3행에 더해준다 와 동치입니다. 그렇다면 1행에 x -1를 하고, 2행은 영향을 끼치면 안되니까 지우기 위해  x 0을 하고, 3행은 더하기 위해 존재해야하니 x 1을 해줘야합니다. 이를 그대로 수식으로 풀면,

 

(-1 x A의 1행) + (0 x A의 2행) + (1 x A의 3행) → (결과 행렬의 3행)

 

이렇게 됩니다. 그렇다면 A에 가하는 두 번째 행렬 연산은 바로 다음과 같이 될 것입니다.

 

((\begin{bmatrix}
1 & 0 & 0\\ 
-2 & 1 & 0\\ 
-1 & 0 & 1
\end{bmatrix}))

 

 

 

세 번째 연산인 "두 번째 행에 곱하기 1을 해서 마지막 행에서 한 번 빼주겠습니다" 도 마찬가지로 진행됩니다. 최종적으로 마지막 행에서 빼는 것이므로 마지막 행을 결정하는 자리인 3행에 변화를 가해주어야 합니다.

 

1 x A의 1행 + 0 x A의 2행 + 0 x A의 3행 → 결과 행렬의 1행

0 x A의 1행 + 1 x A의 2행 + 0 x A의 3행 → 결과 행렬의 2행

0 x A의 1행 + 0 x A의 2행 + 1 x A의 3행 → 결과 행렬의 3행

 

결과 행렬의 3행에 영향을 미치는 부분은 0 0 1 이 부분이므로 여기를 건드려야 합니다.

 

((\begin{bmatrix}
1 & 0 & 0\\ 
0 & 1 & 0\\ 
? & ? & ?
\end{bmatrix}))

 

똑같이 2행에 곱하기 1을 해서 3행에서 빼주는 것 = 2행에 -1을 곱하고 3행에 더하는 것 입니다.

영향을 끼치면 안되는 1행은 x 0, 2행은 x -1, 3행은 더하기 위해 존재해야하니 x 1로,

 

(0 x A의 1행) + (-1 x A의 2행) + (1 x A의 3행) → (결과 행렬의 3행)

 

이므로, A에 가하는 세 번째 연산은 다음과 같이 됩니다.

 

((\begin{bmatrix}
1 & 0 & 0\\ 
-2 & 1 & 0\\ 
0 & -1 & 1
\end{bmatrix}))

 

이렇게 우리는 말로 풀었던 가우스 소거법 과정을 일련의 행렬 연산의 과정으로 나타낼 수 있었습니다. 우리의 3번의 연산 결과를 하나의 수식으로 표현해보면 다음과 같습니다.

 

 

 

 

이 3번의 순차적인 연산들이(왼쪽에서부터 각각 첫 번째 연산, 두 번째 연산, 세 번째 연산입니다) 바로 ((L))을 구성하는 친구들입니다. 

하지만 지금의 형태는 ((L))((A)) = ((U)) 형태입니다. 우리는 이걸 ((A)) = ((L))((U))로 바꾸고 싶습니다. 바꾸는 과정은 다음과 같습니다.

 

 

 

우선  ((L^{-1})) 이 부분을 설명해보자면, 연산을 반대로 취하는 것입니다. ((A))의 행들을 가지고 -2배하고 더해준 것의 결과가 ((U))입니다. 그러니까 이제는 ((U))의 행들의 결과를 2배해서 더해주면 (정확히 반대로) ((A))가 나온다는 사고과정입니다. 이는 많은 것을 할 필요없이 연산을 그대로 반대만 해주면 되므로 부호와 순서만 바꿔주면 됩니다.

그렇게 ((L))들을 하나로 합치면, 다음과 같이 LU factorization이 완성되는 것입니다.

 

---

 

해를 바로 구하는 방법(Using Augmented matrix)

 

이번에는 LU로 분해하는 것이 아니라 그냥 바로 해를 구하는 방법에 대해서 보도록 하겠습니다. 바로 Augmented matrix를 이용하는 방식입니다. Augmented matrix란 첨가행렬로, 뒤에 상수항들을 덧붙이는 행렬입니다.

 

그럼 뒤에 뭘 붙일까요? 우리의 식이 ((A))((x)) ((=)) ((b)) 라고 할 때, 뒤의 ((b))를 extra column으로 붙여버리는 것입니다. 그리고 이렇게 증강된 행렬에 위에서 우리가 한 Elimination(소거법)을 그대로 적용하여 backsubstitution으로 해를 구하는 것입니다. 예시를 보면서 설명해보겠습니다. 

 

 

 

우리가 계속 보던 행렬 ((A)) 뒤에 b가 extra column 형태로 붙은 형태입니다. 이 상태에서 ((A))에 그대로 Gaussian eliminiation을 해줍니다. 위에서 우리가 했던 그대로 ((U))꼴로 만들어줍니다. 다만, 계산은 옆의 열인 b에게도 동시에 적용됩니다. 예를 들면, 처음에 우리가 첫 번째 행에 x 2를 하여 두 번째 행에서 빼주었으면, 19에 x 2를 하여 55에서 똑같이 빼주는 것입니다.

 

 

 

그 후 ((7))((x₃)) ((=)) ((14)) 라는 점을 이용해서 계속해서 backsubstitution(part 1 참조)으로 변수들의 값을 구해나가면, 결과적으로 우리의 해인 ((x))를 구할 수 있습니다.

 

---

 

가우스 소거법이 안 통할 때(Permutation matrix)

 

 

가우스 소거법을 이용해서 왼쪽 아래들을 0으로 만들어 ((U))꼴로 만드려는 시도가 잘 되지 않을 때도 있습니다. 바로 값이 0인 pivot들이 있을 때입니다. 이럴 때에는 Permutation matrix P를 곱해주어 행들의 위치를 바꿔주는 전략을 취합니다.

 

무슨 뜻인지 한 번 보겠습니다.

 

 

 

지금 상황을 보면 1행에 뭔가를 곱해서 밑에 3을 없애주어야 하는데 첫 시작부터 0, 즉 zero pivot이 나와버려서 아무것도 할 수 없는 상황입니다. 그래서 이럴 때는 zero pivot을 막기 위해 1행과 2행의 위치를 바꿔주는 선택을 하게 됩니다.

 

그 기능을 해주는게 바로 Permutation matrix, P입니다. 아까 ((L))을 만들 때의 계산에서 보셨던 것처럼 같은 계산인데요, 더욱 간단하게 짚으면,

 

((P))의 1행의 0 1 은 결과 행렬의 1행 값을 결정하는데, 뒤에 오는 행렬의 1행 값은 없애버리고(0배) 2행 값만 그대로 남겨(1배) 뒷 행렬의 2행 값을 결과 행렬의 1행에 써주겠다는 뜻입니다.

마찬가지로 ((P))의 2행의 1 0 은 결과 행렬의 2행 값을 결정하는데, 뒤에 오는 행렬의 1행 값은 그대로 남기고(1배) 2행 값은 없애(0배)뒷 행렬의 1행 값을 결과 행렬의 2행에 써주겠다는 뜻입니다.

 

Identity matrix(아무 변화도 주지 않는)의 1행이 1 0, 2행이 0 1 인것과 딱 반대로 여기는 1행이 0 1, 2행이 1 0 이렇게 뒤집어졌습니다. 1행과 2행을 반대로 놓겠다는 뜻이죠.

 

((\begin{bmatrix}
1 & 0\\ 
0 & 1
\end{bmatrix})) ((\rightarrow)) ((\begin{bmatrix}
0 & 1\\ 
1 & 0
\end{bmatrix}))

 

이렇게 보시면 더욱 잘 보일겁니다. 

 

예시를 한 번 더 보겠습니다.

 

 

 

첫 번째 행렬에서 최대한 소거법을 한 결과, 두 번째 행렬이 되었습니다. 그런데 ((U))를 만들기 위해서는 밑에 2가 마저 지워져야합니다. 그런데 두 번째 행은 바로 위에 0이라 어떤 수를 곱해도 2를 지울 수 없고, 첫 번째 행으로는 2는 지워지나 3행의 맨 마지막에 다른 수가 또 생기게 됩니다. 이렇게 불가능한 상황에서 두 번째 행과 세 번째 행의 위치를 바꾸는 것입니다. 

 

P를 한 번 구성해봅시다. 

 

항상 생각할 때 Identity matrix, 일단 기본적인 아무것도 안 바꿔지는 상황에서 생각을 출발시키면 좋습니다. 3 x 3 Identity matrix를 떠올려보면, 

 

((\begin{bmatrix}
1 & 0 & 0\\ 
0 & 1 & 0\\ 
0 & 0 & 1
\end{bmatrix}))

 

이렇게 입니다. 우리의 목표는 "2행과 3행의 위치를 바꾸는 것"입니다. 2행과 3행을 볼까요?

 

Identity의 2행을 보면, 0 1 0, 즉 1행 지우고 2행 살리고 3행 지우고 를 결과행렬 2행에 쓰겠다는 것입니다.

Identity의 3행을 보면, 0 0 1, 즉 1행 지우고 2행 지우고 3행 살리고 를 결과행렬 3행에 쓰겠다는 것입니다.

 

우리는 2행 자리에 3행을 쓰고 싶고, 3행 자리에 2행을 쓰고 싶습니다.

 

그렇다면,

 

0 0 1, 즉 1행 지우고 2행 지우고 3행 살리고 를 결과행렬 2행에 쓰면,

0 1 0, 즉 1행 지우고 2행 살리고 3행 지우고 를 결과행렬 3행에 쓰면 될 것입니다.

 

결과적으로, 우리의 Permutation matrix P는, 

 

((\begin{bmatrix}
1 & 0 & 0\\ 
0 & 0 & 1\\ 
0 & 1 & 0
\end{bmatrix}))

 

가 될 것이고,

((A))에 Permutation matrix P를 곱한 형태는 이렇게 될 것입니다. 이게 ((PA))이고, 이를 ((LU))로 분해하면 되는 것입니다. 

 

---

 

 

오늘은 LU factorization에 대해서, 특히 행렬 연산을 최대한 직관적으로 풀어서 설명해보았습니다. 약간 말이 길어지긴 했는데, 이해가 잘 되셨으면 좋겠습니다. 분명히 기억하고 있으셔야 할 것은, 지금 하는 LU factorization은 ((A))((x)) ((=)) ((b)) (where A is n x n) 상황에서 쓰이는 방법이라는 것입니다. 좀 더 정확히 말씀드리면, 

 

 

 

왜 LU factorization을 하는가?

 

((A))((x)) ((=)) ((b))를 ((A))가 ((n)) x ((n))일 때 풀건데,

 

1. ((A))가 ((n)) x ((n))이고
2. ((A))가 invertible할 때 (invertible하지 않으면 echelon form이 나오지 않음)

 

다음과 같은 조건을 만족할 때 쓰이는 방법입니다. 막 계산법도 머리에 넣어야되고 어렵고 할 텐데, 이렇게 큰 그림을 그리며 어떤 상황에서 이렇게 다루는 방법들이 쓰이는지 파악하는 식으로 공부하면 좋을 것 같습니다. 앞으로도 이렇게 경우를 잘 나눠가며 포스팅하는 식으로 해보겠습니다.