가우스 / 가우스-조던 소거법

본 포스팅은 University of California Davis ENG 006: Engineering Problem Solving에서 제공하는 ZyBooks의 내용을 바탕으로 작성하였습니다.

Prerequisites

이번 포스팅의 내용을 더 잘 이해하기 위해선 아래의 내용에 대해 알고 오시는 것이 좋습니다.

Introduction

기본 행렬 편과 LU 분해 편을 통해서 우리는 행렬 형태를 이용해 연립 방정식을 풀 수 있다는 것을 확인했다. 이때 핵심적인 역할을 하는 것이 기초적인 행 연산(elementary row operations)에 대응하는 기본 행렬들 (주로 라고 씀) 이었다.

즉, 우리의 목표는 아래와 같이 기본 행 연산들을 수행함으로써 와 같이 변경해주는 것이다.

여기서 는 상삼각행렬(upper triangular matrix)이다.

만약 와 같은 형태로 바꿔줄 수 있다면 우리는 back-substitution을 이용해 미지수 을 수월하게 구해낼 수 있게 된다는 것을 공부하였다.


그림 1. 기본 행 연산을 통해 상삼각행렬을 얻는 과정

LU 분해 에서는 위와 같은 방법을 적용할 때 행렬 형태의 정방 행렬(square matrix)였다.

그런데, 꼭 행렬 가 정방 행렬이어야지만 위와 같은 방식의 row operation을 해줄 수 있는 것은 아니다.

다시 말해, 식의 개수보다 변수의 개수가 많은 경우도 있을 수 있고, 변수의 개수보다 식의 개수가 많은 경우에 대해서도 위와 같은 상삼각행렬 비슷한 것을 남길 수 있지 않을까?

또, 상삼각행렬의 꼴이 아니라 대각성분 위에 남아있는 숫자들도 모두 row operation을 취해줌으로써 소거해버리면 어떻게 될까?

LU 분해와 REF, RREF

※ REF는 Row-Echelon Form을 줄인 말이고, RREF는 Reduced Row-Echelon Form을 줄인 말입니다.

정방행렬이 아닌 직사각행렬(rectangular matrix)에 대해 row operation을 취해줌으로써 우리가 얻어야 하는 결과물은 마치 LU 분해를 수행해서 상삼각행렬(upper triangular matrix)를 얻은 것과 같은 형태일 수 있다.

대략적으로는 아래와 같은 모습을 띄고 있는 것이라고 말할 수 있다.


그림 2. 직사각 행렬에 대해 row operation을 수행해 얻고자 기대하는 결과물

그림 2와 같은 행렬을 우리는 row-echelon matrix 혹은 주어진 행렬의 row-echelon form이라고 한다. 한국말로는 사다리꼴 행렬이라고 부른다. (이 단어만은 한국어 표현이 잘못되었다고 생각해 row-echelon matrix라고 부르도록 하겠다.) 그림 2에서 삼각형(▲)과 하이픈(-)은 모두 0이 아닌 원소들을 의미한다. 또, 0이 아닌 행의 선행 계수인 삼각형(▲)을 특별히 피벗(pivot)이라고 이름 붙였고, pivot이 포함된 열(column)을 pivot column이라고 부른다.

용어를 어느정도 파악했을테니 row-echelon matrix가 갖는 특성을 글로 정리하자면 다음과 같다.

  • 0이 아닌 모든 행은 모두 0 행 위에 있다 (즉, 모두 0 행은 행렬의 맨 아래에 있음).
  • 0이 아닌 행의 선행 계수는 항상 위 행의 0이 아닌 첫 번째 항목의 오른쪽에 있다.
  • 피벗 아래의 모든 열 항목은 0이다.

글로 써둔 것을 보면 헷갈리지만 아래와 같은 계단 형태를 띄고 있는 형태의 행렬이라는 것을 의미한다.


그림 3. row-echelon matrix는 계단 형태의 행렬이며 각 계단의 끄트머리에 발을 딛고 올라갈 부분을 pivot이라고 부른다.

다시 말해 row-echelon matrix는 직사각행렬 에 대해 row operation을 수행한 결과로 얻어지는 행렬로 상삼각행렬과 유사한 형태와 기능을 갖는 행렬이다. 그리고 위에서 언급한 세 가지 특성을 가져야 한다. 따라서, row operation을 수행해주면서 해당 형태를 갖게끔 행교환을 계속 수행해줌으로써 얻을 수 있게 된다.

그리고 만약 여기서 scaling을 통해 pivot들을 모두 1로 만들고, pivot 위의 숫자들도 모두 0으로 만들어줄 수도 있을 것이다. 가령, 그림 3의 형태의 row-echelon form에 대해 다음과 같이 변형시킬 수 있다.


그림 4. row-echelon form에서 pivot 을 모두 1로 scaling 해주고 pivot 위의 값들도 모두 0으로 만들어주면 reduced-row echelon form이 된다.

Echelon이라는 단어의 번역에 대해서

Row-echelon 행렬은 한국말로는 사다리꼴 행렬이라고 번역한다.

이 번역은 아주 잘못된 번역의 좋은 예시로 볼 수 있을 것 같다. 그리고 이런 오역으로 인해 학생들이 row-echelon 행렬을 이해하는데 더 어려움을 가중할 것 같다.

우리가 보통 수학에서 사다리꼴이라고 하면 아래와 같은 도형을 생각하기 쉽다.


그림 5. 사다리꼴 도형의 형태

그런데 ‘사다리꼴’ 이 말하는 사다리(ladder)의 형태를 말하는 것이다. 즉,


그림 6. 그냥 사다리

왜냐면 echelon이라는 영어 단어가 ‘사다리’라는 뜻을 갖는 영단어에서 유래되었기 때문인 것으로 보인다. 하지만 여기서 row-echelon form이라는 뜻에서 echelon은 step-like architecture를 의미하는 것으로 보아야 타당하다.

다시 말하면, 행렬의 하단부에 0이 쏠려있다보니 그 0들의 형태가 마치 계단 형태인 것 처럼 보인다는 의미에서 echelon이라는 단어를 썼다고 보는 것이 더 낫다. 그리고 그래야 맥락에 맞지 않아 보이는 pivot이라는 용어도 단어의 이용 의도를 조금더 파악할 수 있게 된다.

REF & RREF의 형태 예시: 눈으로 구별해보세요.

Row-echelon 행렬의 개념은 처음 접하게 되면 어리둥절할 수 있다.

글로 써진 row-echelon 행렬의 특징이 쉽게 와닿긴 어렵기 때문이다. 그래서 몇 가지 예시를 가지고 row-echelon 행렬인지의 여부를 확인해보자.

REF는 Row-Echelon Form, RREF는 Reduced Row-Echelon Form을 각각 의미한다.

아래의 행렬은 REF이라고 할 수 있다.

여기서 ‘-‘는 0이 아닌 숫자를 의미한다.

아래의 행렬은 또 REF이라고 할 수 있다. 꼭 첫번째 행의 첫번째 값이 non-zero term이 되어야 한다는 요구 조건은 없다.

그런데, 아래의 행렬은 REF이 아니다. 0으로만 구성된 행은 가장 아래에 위치해야 한다는 법칙을 어긴 것이기 때문이다.

또, 아래와 같은 꼴의 행렬도 REF이 아니다. 세 가지 특성 중 두 번째를 어겼기 때문이다. 다시 말해 두번째 행의 0이 아닌 선행 계수가 첫 번째 행의 0이 아닌 선행 계수보다 왼쪽에 위치하기 때문이다.

또 아래와 같은 행렬도 REF이 아니다. 두 번째 pivot인 4가 포함되어 있는 2열을 보면 pivot인 4 아래의 모든 항이 0으로 표시되어 있지 않기 때문이다.

아래의 행렬은 RREF이라고 할 수 있다.

그러나 아래의 행렬은 RREF이 아니다. pivot의 정의 상 2행 2열의 4는 2행의 pivot인데, RREF라면 pivot이 모두 1이 되어야 하기 때문이다.

만약 여기서 2행에 1/4를 모두 곱해주면 RREF이 된다.

REF & RREF 직접 구해보기

손으로 REf, RREF 구하기

아래의 행렬 에 대해 elementary row operation을 수행해 row-echelon matrix를 얻어보자.

다음과 같은 row operation들을 수행하자.

그러면 다음과 같은 행렬을 얻을 수 있게 된다.

여기까지만 구하면 이것이 행렬 의 row-echelon form이다.

여기서 2행에 1/4를 곱해주고 3행에 1/2를 곱해주자.

즉,

연산을 취해주면 다음과 같이 행렬이 수정된다.

여기서 pivot 위의 값들도 모두 0으로 만들어주기 위해 아래와 같은 두 개의 행연산을 취해주자.

그러면 최종적으로 다음과 같은 행렬을 얻을 수 있게 된다.

이것이 행렬 A의 reduced-row echelon form이다.

MATLAB에서 REF, RREF 구하기

MATLAB이나 여타 선형대수학을 위한 계산 도구를 통해 주어진 행렬의 Row Echelon Form(REF) 혹은 Reduced Row Echelon Form(RREF)를 계산할 수 있다.

그런데, REF는 유일하게 결정되지는 않는다. 가령, 어떤 행렬의 REF을 구할 때 pivot 값을 약분해주지 않더라도 여전히 REF로 볼 수 있다.

가령 아래와 같은 행렬 에 대해,

REF 중 하나는 다음과 같은 것일 수 있다.

그런데, 가령 2번 행에 1/2를 곱해주더라도 여전히 REF의 꼴임을 알 수 있다.

그래서 REF는 유일하게 결정되지는 않지만 MATLAB에서는 LU분해에 사용되는 lu 함수를 이용해 REF 유사한 것을 얻을 수 있게 된다.

MATLAB에서 아래와 같이 커맨드를 입력해보면,

A = [1, 1, 2, 3, 4; 2, 6, 4, 6, 2; 3, 3, 8, 12, 17]

[~, ref_A]=lu(A);

아래와 같이 REF를 얻을 수 있다.

원래 ref_A는 LU 분해를 통해 얻은 상삼각행렬(upper triangular matrix)이 들어오는 자리.

ref는 유일하게 결정되지 않아서 손으로 푼 REF 결과와 MATLAB의 LU 분해 결과는 다를 수 있다.

rref_A = rref(A);


그림 7. MATLAB으로 구한 행렬 A의 Row-Echelon Form

반면 RREF는 pivot을 약분해주고 pivot 위의 원소들도 모두 소거해주기 때문에 유일하게 결정된다.

MATLAB에서는 rref()라는 함수를 이용해 RREF를 구할 수 있다.


그림 8. MATLAB으로 구한 행렬 A의 Reduced Row-Echelon Form

REF와 RREF의 쓸모

RREF: 역행렬의 계산

에서 벡터가 여러 종류일 때, 한꺼번에 해 들을 구할 수 있다.

가령, 아래와 같이 세 가지 경우의 솔루션을 얻고자 한다고 하자.

그러면 각각의 경우에 대해서 세 번의 계산을 할 것이 아니라 다음과 같이 augmented matrix를 구성하고 가우스-조던 소거를 수행하면 한번에 세 가지 방정식을 다 풀어낼 수 있게 된다.

이것은 다시 말해 다음과 같은 행렬 문제를 푸는 것과 다르지 않다.

그럼 만약 이렇게 augmented matrix를 쓸 수 있다는 점을 응용해 augmented matrix를 다음과 같이 설정하면 어떨까?

즉, 라는 행렬은 라는 행렬 뒤에 곱해져서 결과로써 단위 행렬을 출력해주어야 한다.

다시 말해 행렬은 행렬의 역행렬이다.

즉, 위의 augmented matrix에 대해 가우스-조던 행렬 소거를 적용해 reduced-row echelon matrix로 만들어주면 다음과 같다.

그러므로 의 역행렬을 다음과 같이 계산할 수 있는 것이다.

행동치 관계를 통한 솔루션 계산

연립방정식의 해를 구할 때는 방정식에 상수배를 취해주거나, 방정식 끼리 더해주거나, 방정식의 순서를 바꿔주는 과정을 통해 해를 얻을 수 있다.

그리고, 기본 행렬 편에서 보았던 것 처럼 연립방정식에 적용하던 테크닉들을 행렬 연산으로 옮겨놓은 것이

row operation이다. row operation은 행렬의 한 행을 상수배해주는 것, 행렬의 행 끼리 더해주는 것, 그리고 행의 순서를 바꿔주는 세 가지 테크닉을 의미한다.

연립방정식의 해를 구할 때 상수배, 방정식 끼리 더 해주기, 순서 바꿔주기를 해주어도 해에는 변함이 없는 것 처럼 row-operation을 수행해주어도 해는 여전히 동일하게 유지된다.

그러니까 원래 행렬을 , 그 행렬의 REF를 , RREF를 이라고 하면 , , 의 해는 모두 동일하다.

(이 때, 혹은 로 바꿔주면서 우항의 벡터 가 변형된 것이다.)

조금 어려운 말로 하면 은 모두 행동치(row-equivalent)이다.

다른 말로 하면 row operation을 수행해주더라도 row space의 변화는 없다고 할 수 있다. 하지만 column space에는 변화가 생긴다.

예를 들어 아래와 같은 연립방정식을 푼다고 생각해보자.

그것은 아래와 같은 행렬식을 푸는 것과 같다고 할 수 있다.

그런데, REF를 구해서 의 꼴로 만들어준 다음 해를 구해도 마찬가지 위 방정식의 해와 동일한 해를 구할 수 있다.

그리고 RREF를 구해서 의 꼴로 만들어준 다음 해를 구해도 마찬가지 해를 구할 수 있다.

해를 구하기에 가장 쉬워보이는 방정식은 이고

임을 쉽게 알 수 있다.

행 벡터의 선형 독립 / 종속 판별

임의의 벡터 , 에 대해 두 벡터가 선형 독립인지 판별하기 위해선 다음과 같은 과정을 수행해볼 수 있다.

과 같은 식을 생각했을 때, 0이 아닌 , 를 가지고 위 식이 성립할 수 있다면 두 벡터 는 선형독립이 아니다. 다른 말로는 선형 종속이라고 한다.

다시 말해, 위 식을 다시 정리하면,

가 될텐데, 위 식을 만족할만한 0이 아닌 , 가 존재한다는 뜻이 되므로 는 상수배라는 의미이다.

반대로 <p align = "center"> </p>을 만족할 수 있는 , 오직 0만 가능하다면 는 선형 독립이라고 한다.

어떤 행렬의 Row-Echelon Form 혹은 Reduced Row-Echelon Form을 구하는 것은 row operation을 통해 수행하는 것이다.

이 때, 만약 row operation을 통해서 어떤 행이 all zero 가 된다면, all zero가 된 행은 다른 행들의 선형조합으로 얻어낼 수 있는 행이었다는 뜻이 된다.

다시 말해, 그 행은 다른 행들과 선형 종속이라는 의미이다.

가령 아래와 같은 행렬 를 생각해보자.

이 식을 잘 보면 세 번째 행은 다음과 같이 row operation 해주면 all-zero로 소거할 수 있다.


그림 9. 다른 행에 선형 종속인 행은 row operation을 통해 소거할 수 있다.

다시 말해 의 선형결합으로 표현해줄 수 있다.

행렬의 rank 계산

free variable이 어떤 것인지 확인

non-zero row, pivot column, free column

complete solution을 구하기 위해 필요한 과정