가우스 소거법 (Gaussian Elimination)
18 Feb 2020 | Linear-Algebra
이 포스트는 한양대 이상화 교수님의 선형대수 강의 를 바탕으로 작성되었습니다.
Gaussian Elimination
이번 시간에는 선형 연립방정식의 해를 구하는 가우스 소거법(Gaussian elimination)에 대해서 알아보겠습니다. 사실 가우스 소거법을 몰라도 연립방정식의 해는 구할 수 있습니다. 가장 간단한 형태의 연립방정식을 예로 들어보겠습니다.
\[\begin{cases}\begin{aligned}
x + 2y = 3 \qquad \cdots 1\\
4x + 5y = 6 \qquad\cdots 2
\end{aligned}\end{cases}\]
위 식에서 $x, y$의 해는 중등 과정에서 배운 가감법과 대입법을 통해서도 구할 수 있습니다. 가감법을 사용하려면 식 $1$을 $4$배 해준 뒤 식 $2$를 빼주어 $y=2$ 를 구하고 이를 아무 식에나 대입하여 $x=-1$ 을 구합니다. 대입법을 사용하려면 식 식 $1$ 을 $x = 3-2y$ 처럼 한 문자에 대하여 정리한 뒤에 식 $2$ 에 식을 대입하여 $y=2$ 를 구하고 이를 아무 식에나 대입하여 $x=-1$ 을 구합니다.
둘 중 어느 방법을 사용하든 이 방법은 $x + 2y = 3$ 과 $4x + 5y = 6$ 의 두 직선의 교점을 구하는 관점에서 풀고 있습니다. 만약 미지수의 개수가 3개로 늘어난다면 평면의 교선을 구하는 관점에서 풀게 되지요. 하지만 선형대수학에서 연립방정식의 풀이를 이런 관점으로 바라보는 것이 좋은 방법은 아닙니다. 이런 관점에서는 미지수와 식의 개수가 늘어날수록 직선, 평면 혹은 그 이상의 초평면이 식의 개수만큼 만나는(Intersect) 공간을 상상해야 합니다. 하지만 사람의 머리로 3차원 이상을 상상하기란 쉬운 일이 아닙니다.
그래서 선형대수학에서는 다른 관점으로 연립방정식을 바라봅니다. 이 방식은 다음과 같습니다. 먼저, 미지수의 계수에 해당하는 열벡터를 만들어 이를 미지수만큼 스칼라곱하여 더합니다. 이 때, 등호 오른쪽 열벡터까지 다다르는 미지수의 조합을 찾습니다. 위에서 사용했던 예시를 벡터를 사용하여 나타내면 이렇게 바꾸어 볼 수 있습니다.
\[\left[\begin{array}{c} 1 \\ 4 \end{array} \right]x + \left[\begin{array}{c} 2 \\ 5 \end{array} \right]y = \left[\begin{array}{c} 3 \\ 6 \end{array} \right]\]
즉 벡터 $(1,4)^T$와 $(2,5)^T$를 각각 $x,y$ 배 해주어 곱합니다. 물론 이 방법도 벡터의 차원수가 높아지면 상상하기 어려운 것은 매한가지이지만, 만나는 부분을 찾는 것은 아니기에 조금 더 상상하기 쉽습니다. 그렇기 때문에 고차원의 벡터를 다루는 선형대수학에서는 보다 해의 의미를 찾기 쉬운 아래의 관점을 사용합니다.
Gaussian Elimination
가우스 소거법도 이런 방법을 사용하여 연립방정식을 푸는 방법입니다. 아래와 같이 미지수 3개와 식 3개로 구성된 연립방정식이 있습니다.
\[\begin{align}
\begin{cases} 2u + v + w &= 5 \qquad \cdots 1\\ 4u - 6v &= -2 \quad \cdots 2\\ -2u + 7v + 2w &= 9 \qquad \cdots 3 \end{cases}
\end{align}\]
연립방정식을 각 벡터의 합으로 보기로 했으므로 이를 행렬식으로 만들어 보겠습니다. 위 식을 행렬로 나타내면 아래와 같이 나타낼 수 있습니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{array} \right]\left[\begin{array}{c} u \\ v \\ w \end{array} \right] = \left[\begin{array}{c} 5 \\ -2 \\ 9 \end{array} \right]\]
가우스 소거법은 가장 왼쪽 행렬을 상삼각행렬(Uppert triangular matrix, $U$)로 만드는 과정부터 시작합니다. 상삼각 행렬이란 행렬의 대각 성분(Diagonal elements)을 기준으로 왼쪽 아래 성분이 모두 $0$ 인 행렬입니다. 상삼각행렬을 만드는 방법은 가감법을 사용하여 연립방정식을 푸는 방법과 유사합니다. $1$번째 행에 적절한 수를 곱한 뒤 나머지 각 행과 더하거나 빼주어 각 1열의 성분을 0으로 만듭니다. 위 식에서는 $1$ 번째 행을 2배 해준 뒤에 $2$ 번째 행에서 이를 빼줌으로써 1열의 성분을 0으로 만들 수 있습니다. 마찬가지로 $1$ 번째 행에서 $3$ 번째 행을 더해주어 3행 1열의 성분도 0으로 만들 수 있습니다. 이 계산을 수행하면 아래와 같은 결과가 나오게 됩니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 8 & 3 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{c} 5 \\ -12 \\ 14 \end{array} \right]\]
다음에는 $3$ 번째 행 2열 성분을 0으로 만들어 줄 차례입니다. 위 행렬의 $2$ 번째 식과 $3$ 번째 식을 더해주면 아래와 같이 미지수 왼쪽에 있는 행렬을 상삼각행렬로 만들 수 있습니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -12 \\ 2 \end{array} \right]\]
이제는 모든 미지수의 값을 구할 수 있게 되었습니다. 마지막 행으로부터 $w = 2$ 이니 이 값을 $2$ 번째 행에 대입하여 $u=1$ 을 구하고, 두 값을 $1$ 번째 행에 대입하여 $u=1$ 을 구하면 됩니다. 이렇게 왼쪽에 있는 행렬을 상삼각행렬로 만드는 과정을 가우스 소거법이라고 합니다. 여기서 대각 성분에 해당하는 $2, -8, 1$을 피봇(Pivot)이라고 합니다. 만약 계산하면서 피봇 자리에 $0$이 등장하는 경우에는 그 열의 성분이 $0$이 아닌 다른 행과 바꾸어 다시 소거 계산하면 되는데 이렇게 바꿔주는 과정을 피봇팅(Pivoting)이라고 합니다. 예시처럼 모든 피봇이 $0$이 아니면 연립방정식에 특정한 해(Unique solution)이 존재하는 경우에 해당합니다. 반대로 그렇지 않은 연립방정식은 해가 없거나(No solution) 무한한 해(Infinite solution)를 가집니다.
LU Factorization (Decomposition)
LU분해법(LU Factorization, LU Decomposition)은 가우스 소거법을 사용하여 특정한 행렬을 하삼각 행렬과 상삼각 행렬의 곱으로 분해하는 방법입니다. 위에서 가우스 소거를 했던 예시를 통해 LU분해법에 대해 알아보겠습니다. LU 분해법은 이름에서도 유추할 수 있듯, 특정한 행렬을 하삼각행렬(Lower triangular matrix, $L$)과 상삼각행렬의 곱으로 분해하는 것입니다. 위에서 사용했던 예시를 가져와서 이 행렬이 어떻게 분해되는지를 알아보겠습니다. 처음의 행렬은 다음과 같았습니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 &2 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -2 \\ 9 \end{array} \right]\]
가우스 소거법에서 $\enclose{circle}{1}$ 번째 행을 제외한 행의 1열 성분을 모두 0으로 만들기 위해서 $2$ 번째 행에서 $1$ 번째 행을 두 배 해준 것을 빼주었고, $3$ 번째 행에서는 $1$ 번째 행과 더해주었습니다. 이 과정을 행렬 곱으로 나타내면 아래와 같은 행렬식이 나오게 됩니다.
\[\begin{aligned}
&\left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 &2 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -12 \\ 14 \end{array} \right] \\
\because &\left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 &2 \end{array} \right] = \left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 8 & 3 \end{array} \right]
\end{aligned}\]
마찬가지로 가우스 소거법에서 $1$ 번째 행과 $2$ 번째 행을 제외한 행의 2열 성분을 모두 0으로 만들기 위해서 계산한 행렬의 $2$ 번째 행과 $3$ 번째 행을 더해주었습니다. 이 과정을 행렬 곱으로 나타내면 아래와 같은 행렬식이 나오게 됩니다.
\[\begin{aligned}
&\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array} \right]
\left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -12 \\ 14 \end{array} \right]
\\
\because &\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array} \right]
\left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{array} \right] = \left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 0 & 1 \end{array} \right]
\end{aligned}\]
전체 과정에서 기존 행렬 $A$ 왼쪽에 새로 만들어진 두 하삼각행렬을 원래의 행렬과 가까운 것부터 $L_1, L_2$ 라고 해보겠습니다. 이제 기호를 사용하면 위 수식에서 $\because$ 이하의 식을 다음과 같이 간단하게 나타낼 수 있습니다.
\[L_2 L_1 A = U\]
왼쪽에는 $A$만 남을 수 있도록 $L_2, L_1$의 역행렬을 각각 양변의 왼쪽에 곱해주겠습니다. 그러면 식이 다음과 같이 변하게 됩니다.
\[\begin{aligned}
L_1^{-1}L_2^{-1}L_2 L_1 A &= L_1^{-1}L_2^{-1}U \\
A &= L_1^{-1}L_2^{-1}U
\end{aligned}\]
여기서 두 역행렬의 곱 $L_1^{-1}L_2^{-1}$는 항상 하삼각행렬 $L$이 나오게 됩니다. 그렇기 때문에 위 식을 정리하면 $A = LU$ 로 나타낼 수 있으며 이를 LU분해법이라고 합니다. 특정한 행렬 $A$에 대해 LU분해법으로 등장하는 $L, U$ 행렬 쌍은 오직 하나이며 $A$가 달라지면 $L,U$도 각각 달라집니다. 이런 이유에서 특정한 정방행렬 $A$에 대하여 LU분해법은 일대일대응(Unique)이라고 할 수 있습니다.
이 포스트는 한양대 이상화 교수님의 선형대수 강의 를 바탕으로 작성되었습니다.
Gaussian Elimination
이번 시간에는 선형 연립방정식의 해를 구하는 가우스 소거법(Gaussian elimination)에 대해서 알아보겠습니다. 사실 가우스 소거법을 몰라도 연립방정식의 해는 구할 수 있습니다. 가장 간단한 형태의 연립방정식을 예로 들어보겠습니다.
\[\begin{cases}\begin{aligned} x + 2y = 3 \qquad \cdots 1\\ 4x + 5y = 6 \qquad\cdots 2 \end{aligned}\end{cases}\]위 식에서 $x, y$의 해는 중등 과정에서 배운 가감법과 대입법을 통해서도 구할 수 있습니다. 가감법을 사용하려면 식 $1$을 $4$배 해준 뒤 식 $2$를 빼주어 $y=2$ 를 구하고 이를 아무 식에나 대입하여 $x=-1$ 을 구합니다. 대입법을 사용하려면 식 식 $1$ 을 $x = 3-2y$ 처럼 한 문자에 대하여 정리한 뒤에 식 $2$ 에 식을 대입하여 $y=2$ 를 구하고 이를 아무 식에나 대입하여 $x=-1$ 을 구합니다.
둘 중 어느 방법을 사용하든 이 방법은 $x + 2y = 3$ 과 $4x + 5y = 6$ 의 두 직선의 교점을 구하는 관점에서 풀고 있습니다. 만약 미지수의 개수가 3개로 늘어난다면 평면의 교선을 구하는 관점에서 풀게 되지요. 하지만 선형대수학에서 연립방정식의 풀이를 이런 관점으로 바라보는 것이 좋은 방법은 아닙니다. 이런 관점에서는 미지수와 식의 개수가 늘어날수록 직선, 평면 혹은 그 이상의 초평면이 식의 개수만큼 만나는(Intersect) 공간을 상상해야 합니다. 하지만 사람의 머리로 3차원 이상을 상상하기란 쉬운 일이 아닙니다.
그래서 선형대수학에서는 다른 관점으로 연립방정식을 바라봅니다. 이 방식은 다음과 같습니다. 먼저, 미지수의 계수에 해당하는 열벡터를 만들어 이를 미지수만큼 스칼라곱하여 더합니다. 이 때, 등호 오른쪽 열벡터까지 다다르는 미지수의 조합을 찾습니다. 위에서 사용했던 예시를 벡터를 사용하여 나타내면 이렇게 바꾸어 볼 수 있습니다.
\[\left[\begin{array}{c} 1 \\ 4 \end{array} \right]x + \left[\begin{array}{c} 2 \\ 5 \end{array} \right]y = \left[\begin{array}{c} 3 \\ 6 \end{array} \right]\]즉 벡터 $(1,4)^T$와 $(2,5)^T$를 각각 $x,y$ 배 해주어 곱합니다. 물론 이 방법도 벡터의 차원수가 높아지면 상상하기 어려운 것은 매한가지이지만, 만나는 부분을 찾는 것은 아니기에 조금 더 상상하기 쉽습니다. 그렇기 때문에 고차원의 벡터를 다루는 선형대수학에서는 보다 해의 의미를 찾기 쉬운 아래의 관점을 사용합니다.
Gaussian Elimination
가우스 소거법도 이런 방법을 사용하여 연립방정식을 푸는 방법입니다. 아래와 같이 미지수 3개와 식 3개로 구성된 연립방정식이 있습니다.
\[\begin{align} \begin{cases} 2u + v + w &= 5 \qquad \cdots 1\\ 4u - 6v &= -2 \quad \cdots 2\\ -2u + 7v + 2w &= 9 \qquad \cdots 3 \end{cases} \end{align}\]연립방정식을 각 벡터의 합으로 보기로 했으므로 이를 행렬식으로 만들어 보겠습니다. 위 식을 행렬로 나타내면 아래와 같이 나타낼 수 있습니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{array} \right]\left[\begin{array}{c} u \\ v \\ w \end{array} \right] = \left[\begin{array}{c} 5 \\ -2 \\ 9 \end{array} \right]\]가우스 소거법은 가장 왼쪽 행렬을 상삼각행렬(Uppert triangular matrix, $U$)로 만드는 과정부터 시작합니다. 상삼각 행렬이란 행렬의 대각 성분(Diagonal elements)을 기준으로 왼쪽 아래 성분이 모두 $0$ 인 행렬입니다. 상삼각행렬을 만드는 방법은 가감법을 사용하여 연립방정식을 푸는 방법과 유사합니다. $1$번째 행에 적절한 수를 곱한 뒤 나머지 각 행과 더하거나 빼주어 각 1열의 성분을 0으로 만듭니다. 위 식에서는 $1$ 번째 행을 2배 해준 뒤에 $2$ 번째 행에서 이를 빼줌으로써 1열의 성분을 0으로 만들 수 있습니다. 마찬가지로 $1$ 번째 행에서 $3$ 번째 행을 더해주어 3행 1열의 성분도 0으로 만들 수 있습니다. 이 계산을 수행하면 아래와 같은 결과가 나오게 됩니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 8 & 3 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{c} 5 \\ -12 \\ 14 \end{array} \right]\]다음에는 $3$ 번째 행 2열 성분을 0으로 만들어 줄 차례입니다. 위 행렬의 $2$ 번째 식과 $3$ 번째 식을 더해주면 아래와 같이 미지수 왼쪽에 있는 행렬을 상삼각행렬로 만들 수 있습니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -12 \\ 2 \end{array} \right]\]이제는 모든 미지수의 값을 구할 수 있게 되었습니다. 마지막 행으로부터 $w = 2$ 이니 이 값을 $2$ 번째 행에 대입하여 $u=1$ 을 구하고, 두 값을 $1$ 번째 행에 대입하여 $u=1$ 을 구하면 됩니다. 이렇게 왼쪽에 있는 행렬을 상삼각행렬로 만드는 과정을 가우스 소거법이라고 합니다. 여기서 대각 성분에 해당하는 $2, -8, 1$을 피봇(Pivot)이라고 합니다. 만약 계산하면서 피봇 자리에 $0$이 등장하는 경우에는 그 열의 성분이 $0$이 아닌 다른 행과 바꾸어 다시 소거 계산하면 되는데 이렇게 바꿔주는 과정을 피봇팅(Pivoting)이라고 합니다. 예시처럼 모든 피봇이 $0$이 아니면 연립방정식에 특정한 해(Unique solution)이 존재하는 경우에 해당합니다. 반대로 그렇지 않은 연립방정식은 해가 없거나(No solution) 무한한 해(Infinite solution)를 가집니다.
LU Factorization (Decomposition)
LU분해법(LU Factorization, LU Decomposition)은 가우스 소거법을 사용하여 특정한 행렬을 하삼각 행렬과 상삼각 행렬의 곱으로 분해하는 방법입니다. 위에서 가우스 소거를 했던 예시를 통해 LU분해법에 대해 알아보겠습니다. LU 분해법은 이름에서도 유추할 수 있듯, 특정한 행렬을 하삼각행렬(Lower triangular matrix, $L$)과 상삼각행렬의 곱으로 분해하는 것입니다. 위에서 사용했던 예시를 가져와서 이 행렬이 어떻게 분해되는지를 알아보겠습니다. 처음의 행렬은 다음과 같았습니다.
\[\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 &2 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -2 \\ 9 \end{array} \right]\]가우스 소거법에서 $\enclose{circle}{1}$ 번째 행을 제외한 행의 1열 성분을 모두 0으로 만들기 위해서 $2$ 번째 행에서 $1$ 번째 행을 두 배 해준 것을 빼주었고, $3$ 번째 행에서는 $1$ 번째 행과 더해주었습니다. 이 과정을 행렬 곱으로 나타내면 아래와 같은 행렬식이 나오게 됩니다.
\[\begin{aligned} &\left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 &2 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -12 \\ 14 \end{array} \right] \\ \because &\left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 &2 \end{array} \right] = \left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 8 & 3 \end{array} \right] \end{aligned}\]마찬가지로 가우스 소거법에서 $1$ 번째 행과 $2$ 번째 행을 제외한 행의 2열 성분을 모두 0으로 만들기 위해서 계산한 행렬의 $2$ 번째 행과 $3$ 번째 행을 더해주었습니다. 이 과정을 행렬 곱으로 나타내면 아래와 같은 행렬식이 나오게 됩니다.
\[\begin{aligned} &\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array} \right] \left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{array} \right]\left[\begin{array}{ccc} u \\ v \\w \end{array} \right] = \left[\begin{array}{ccc} 5 \\ -12 \\ 14 \end{array} \right] \\ \because &\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array} \right] \left[\begin{array}{ccc} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right]\left[\begin{array}{ccc} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{array} \right] = \left[\begin{array}{ccc} 2 & 1 & 1 \\ 0 & -8 & -2 \\ 0 & 0 & 1 \end{array} \right] \end{aligned}\]전체 과정에서 기존 행렬 $A$ 왼쪽에 새로 만들어진 두 하삼각행렬을 원래의 행렬과 가까운 것부터 $L_1, L_2$ 라고 해보겠습니다. 이제 기호를 사용하면 위 수식에서 $\because$ 이하의 식을 다음과 같이 간단하게 나타낼 수 있습니다.
\[L_2 L_1 A = U\]왼쪽에는 $A$만 남을 수 있도록 $L_2, L_1$의 역행렬을 각각 양변의 왼쪽에 곱해주겠습니다. 그러면 식이 다음과 같이 변하게 됩니다.
\[\begin{aligned} L_1^{-1}L_2^{-1}L_2 L_1 A &= L_1^{-1}L_2^{-1}U \\ A &= L_1^{-1}L_2^{-1}U \end{aligned}\]여기서 두 역행렬의 곱 $L_1^{-1}L_2^{-1}$는 항상 하삼각행렬 $L$이 나오게 됩니다. 그렇기 때문에 위 식을 정리하면 $A = LU$ 로 나타낼 수 있으며 이를 LU분해법이라고 합니다. 특정한 행렬 $A$에 대해 LU분해법으로 등장하는 $L, U$ 행렬 쌍은 오직 하나이며 $A$가 달라지면 $L,U$도 각각 달라집니다. 이런 이유에서 특정한 정방행렬 $A$에 대하여 LU분해법은 일대일대응(Unique)이라고 할 수 있습니다.
Comments