1. The Idea of Elimination
1.1 Two Equations in Two Unknowns
■ 선형 방정식을 해결하는 체계적인 방법은 '소거법(elimination)'이다.
■ 첫 번째 방정식에 3을 곱해 \( 3x - 6y = 3 \)으로 만든 후, 두 번째 방정식에서 이를 빼면 8y = 8이 되고, 첫 번째 미지수 \( x \)가 두 번째 방정식에서 사라진다.
■ 새로운 두 번째 방정식 \( 8y = 8 \)을 통해 \( y = 1 \)임을 알 수 있으니, \( y = 1 \)을 첫 번째 방정식 \( x -2y = 1 \)에 넣으면 \( x = 3 \)이 되고, 해답은 \( (x, y) = (3, 1) \)이 된다.
■ 소거법(elimination) 과정의 목표는 다음과 같이 상삼각형(upper triangular) 구조를 생성하는 것이다.
■ 이 과정을 통해 먼저, \( y = 1 \) 그리고 \( x = 3 \)처럼 '아래에서 위로' 해답을 구할 수 있다. 이 과정을 'back substitution'이라고 한다.
■ 여기서 중요한 점은 이렇게 구한 해가 다음과 같이 원래 방정식의 해와 동일하다는 것이다.
- 제거 후에도 두 선이 같은 교점에서 만나는 것을 확인할 수 있다.
■ 이 과정에서 '승수(multiplier) 규칙'을 확인할 수 있다. 예를 들어 첫 번째 방정식에 4를 곱한다면, \( x- 2y = 1 \)과 같은 직선이지만, 피벗(pivot)은 4가 된다.
■ 여기서 말하는 피벗(pivot)은 '제거를 수행하는 행에서 first nonzero(첫 번째로 0이 아닌 계수)'이며, multiplier는 '제거할 항목을 피벗으로 나눈 값'이다.
- 0은 절대 피벗으로 허용되지 않는다.
- 위의 첫 번째 방정식에 4배를 곱한 예에서, pivot은 4이고, 제거할 미지수는 \( x \)이므로 multiplier는 3/4가 된다.
■ 새로운 두 번째 방정식 \( 8y = 8 \)은 두 번째 pivot 8로 시작한다. 만약, 세 번째 방정식이 있다면 이를 사용해 \( y \)를 제거하면 된다.
■ 즉, \( n \)개의 방정식을 풀기 위해서는 \( n \)개의 pivot이 필요하며, pivot은 제거 후 삼각형의 대각선 상에 위치하게 된다.
■ 그러나, 이렇게 상삼각형 구조가 생성되도록 pivot을 찾는 과정이 항상 성공하지는 않는다. 예를 들어, 다음과 같이 '해가 없는 경우'이다.
■ 이런 경우 다음과 같이 row picture을 보면 두 직선이 평행하므로, 두 방정식을 만족시키는 \( (x, y) \)가 존재하지 않는 것을 확인할 수 있고, column picture를 보면 어떠한 계수를 열 벡터에 적용해도, 두 열 벡터의 선형 결합으로 [1 11]을 생성할 수 없음을 확인할 수 있다.
■ 다른 경우는 '해가 무수히 많은 경우'이다. 예를 들어, 다음과 같이 두 방정식이 같은 직선을 나타내는 경우 0y = 0이 나온다.
■ 이러한 경우 \( y \)에 어떠한 값을 넣더라도 식은 성립한다. 즉, 어떠한 \( y \)가 와도 \( x = 1 + 2y \)로 결정할 수 있다. 즉, \( x - 2y = 1 \) 위의 모든 점이 해가 될 수 있다.
■ 예외인 경우가 있다. 바로 '피벗 위치에 0이 있는 경우'이다. 소거를 통해 pivot이 0가 되는 zero pivot을 말하는 것이 아닌, 소거법 알고리즘(어떤 방정식에 multiplier를 곱한 뒤, 다른 방정식에서 뺀다.)을 수행하기 전에 피벗 위치에 0이 있는 경우이다.
■ 예를 들어 다음과 같이 첫 번째 피벗 위치에 0이 있다면, 다음과 같이 행을 교환해서 문제를 해결할 수 있다.
1.2 Three Equations in Three Unknowns
■ 이번에는 3 x 3으로 크기를 확장시켜 elimination 패턴을 확인해 보자.
■ 첫 번째 pivot은 2이다. 두 번째와 세 번째 방정식의 미지수 \( x \)를 제거하기 위해서는 첫 번째 방정식에 적용할 multiplier들을 찾아 두 번째 방정식과 세 번째 방정식에서 첫 번째 방정식을 빼야 한다.
■ multiplier는 '제거할 항목을 피벗으로 나눈 값'이므로,
- 첫 번째 방정식에 2를 곱한 방정식을 두 번째 방정식에서 빼고, 첫 번째 방정식에 -1을 곱한 방정식을 세 번째 방정식에서 빼면 된다.
- 이때, -1을 곱하는 이유는 소거법(elimination) 규칙이 'multiplier를 곱하고, 이를 subtract한다.'이기 때문이다.
■ 이 과정을 통해 다음과 같이 \( Ax = b \)를 상삼각 행렬이 들어간 \( Ux = c \)로 바꿀 수 있다.
■ 이때 상삼각 행렬 \( U \)의 대각 원소에는 pivot 2, 1, 4가 위치하게 된다. 특히 pivot 1과 4는 행렬 \( A \)에 숨겨져 있었지만, 소거법을 적용하니 발견된 pivot들이다.
■ 위와 같은 형태로 바꾸면 미지수 \( x, y, z \)를 쉽게 구할 수 있다. 순서를 따지면,
- 1) \( 4z = 8 \rightarrow z = 2 \)
- 2) \( y + z = 4, \quad z = 2 \). 따라서 \( y = 2\)
- 3) \( z = 2, y = 2 \)이므로 \( x = -1 \)
■ 이러한 패턴은 행렬 \( n x n \)까지, 즉 \( n \)개의 방정식 & \( n \)개의 미지수인 경우에도 가능하다. 위의 예시처럼 - 첫 번째 방정식을 이용해 첫 번째 pivot아래를 모두 0으로 만든다.
- 이를 통해 만들어진 새로운 두 번째 방정식을 이용해 두 번째 pivot 아래를 모두 0으로 만든다.
- 이 과정을 계속 반복하여 \( n \)개의 pivot을 모두 찾아 상삼각 행렬 \( U \)를 만들면 된다.
■ 예를 들어 다음과 같이 3개의 방정식, 3개의 미지수가 있을 때
■ 위의 소거법을 이용해 \( A \)에서 상삼각 행렬 \( U \)로 변하는 과정만 보면,
- 첫 번째 pivot은 1이다. 첫 번째 pivot 아래를 모두 0으로 만들기 위해서는 1행에 multiplier 3을 곱해 2행에서 빼주면 되고, 1행에 multiplier 0을 곱해 3행에서 빼주면 된다.
- 그다음, 두 번째 pivot은 2이다. 두 번째 pivot 아래를 모두 0으로 만들기 위해서는 2행에 multiplier 2를 곱해 3행에서 빼주면 된다.
- 이 과정을 통해 행렬 \( A \)는 다음과 같은 상삼각 행렬 \( U \)가 된다.
■ 이렇게 소거의 목적은 행렬 \( A \)에서 \( U \)까지 가는 것이었다.
cf) 위의 예시에서 3행 3열의 원소 1이 -4였다면. 마지막 순간에는 0이 되므로 세 번째 pivot(이 예에서는 마지막 pivot)이 존재하지 않는다. 이런 행렬은 역행렬이 될 수 없다.
■ 위의 과정은 계수 행렬(coefficient matrix) \( A \)이 \( U \)로 변하는 과정이다. 여기에 \( b \)를 붙여 \( b \)가 \( c \)로 변하는 과정을 보자.
cf) 이렇게 위와 같이 일차(linear)연립 방정식에서 계수 행렬 \( A \)과 상수 행렬 \( b \)가 붙은 행렬 \( C = (A \mid B) \)를 확대 행렬(augmented coefficient matrix)이라고 부른다.
■ 이 상태에서 역 대입(back substitution)을 수행하면, 다음과 같은 순서대로
- 1) \( z = -2 \),
- 2) \( z = -2 \)이므로 \( y = 1 \)
- 3) \( z = -2, y = 1 \)이므로 \( x = 2 \)
2. Elimination Using Matrices
■ 이 내용을 배우기 전에, 행렬과 벡터를 곱셈하는 방법에 대해 알아야 한다.
■ 행렬을 어떤 벡터로 곱한 결과는 행렬의 각 열 벡터에 벡터의 각 원소를 곱한 뒤, 이 값들을 모두 더하는. 즉, 행렬의 열 벡터의 선형 결합이다.
- 이렇게 행렬 \( \times \) 열 벡터 = 열 벡터가 된다. 이는 행렬의 각 열을 결합하는 것으로 볼 수 있다.
■ 반대로, 1 x 3인 행 벡터가 앞에 있고 그 뒤에 3 x 3 행렬이 곱해지는 경우 행렬의 행 벡터의 선형 결합이 된다.
- 행 벡터 \( \times \) 행렬 = 행 벡터가 된다. 이는 행렬의 각 행을 결합하는 것으로 볼 수 있다.
■ 이제 다음과 같이 어떤 행렬에 \( A \)를 곱해 \( U \)가 되는 과정을 보자.
■ 위의 3 x 3 소거법 예시에서 첫 번째 단계는, 첫 번째 pivot 아래를 모두 0으로 만들기 위해서 1행에 multiplier 3을 곱해 2행에서 빼주는 과정이었다. 이 과정에 대한 결과를 보면, 다음과 같이 1행과 3행은 \( A \)와 동일하다. 2행에만 특정 연산을 적용했기 때문이다.
■ 그렇다면, 여기서 빈칸 행렬의 1행과 3행은 [1 0 0], [0 0 1]이라는 것을 유추할 수 있다.
- 행 벡터 [1 0 0]과 행렬 \( A \)를 곱해야 \( U \)의 1행이 \( A \)와 그대로 [1 2 1]이 되고
- 행 벡터 [0 0 1]과 행렬 \( A \)를 곱해야 \( U \)의 3행이 \( A \)와 그대로 [0 4 1]이 되기 때문이다.
■ 그렇다면 빈칸 행렬의 2행은? [-3 1 0]이 되어야 [-3+3, -6+8, -3 + 1] = [0, -2, -2]가 된다.
■ 그리고 위의 예시에서 세 번째 방정식에는 아무런 연산을 하지 않았다. 이미 첫 번째 pivot 아래의 계수가 0이었기 때문이다.
■ 이 행렬을 \( E_{21} \)이라고 한다. 21이 붙는 이유는 \( E_{21} \) 행렬이 기존 행렬 \( A \)의 2행 1열의 원소를 소거했기 때문이다.
■ 위의 3 x 3 소거법 예시에서 두 번째 단계는, 두 번째 pivot 아래를 모두 0으로 만들기 위해서 2행에 multiplier 2를 곱해 3행에서 빼주는 과정이었다.
■ 동일한 방식으로 진행하면 \( E_{32} \) 행렬을 구할 수 있다.
■ \( E_{21}, E_{32} \)와 같은 행렬을 elimination matrix라고 부른다.
■ 지금까지 \( A \)에 대해 적용한 과정은 먼저, \( A \)에 \( E_{21} \)을 곱하고, 이 결과에 \( E_{32} \)를 곱했다. 이 결과가 상삼각 행렬 \( U \)가 된 것이다.
■ 여기서 중요한 것은, 행렬의 순서를 바꿀수는 없지만, 곱셈을 하는 순서는 바꿀 수 있다는 것이다. 즉, 다음과 같이 순서를 바꾸면 소거를 한 번에 처리하는 행렬이 만들어진다.
- 위의 과정을 '결합 법칙(associative law)'이라고 한다.
'선형대수' 카테고리의 다른 글
| [개념] 행렬 (3) (0) | 2025.01.18 |
|---|---|
| [개념] 행렬 (2) (0) | 2025.01.18 |
| [개념] 행렬 (1) (0) | 2025.01.17 |
| Solving Linear Equations - (1) Vectors and Linear Equations (0) | 2025.01.17 |
| [개념] 벡터(Vector) (0) | 2025.01.15 |
