[Numerical Analysis][C] 가우스-조단 방법에 의한 역행렬 구하기
COM2010. 11. 14. 00:21 |기본행렬에 대한 복습부터 해보자.
기본행렬은 단위행렬에 단 한번의 기본연산을 행하여 만든 행렬을 말하는 데, 그것은 보통 리플레이스먼트, 멀티플리케이션, 인터체인지 이렇게 세가지를 말한다. 그것이 행연산일 경우 좌곱(Left Multiplication)으로, 열연산일 경우 우곱(Right Multiplication)으로 해줘야 제 기능을 한다.
어떠한 스퀘어 메이트릭스 M 에 유한번의 기본 행 연산을 수행하여 단위행렬 E 가 되었다고 하자.
각 기본행 연산을 나타내는 기본행렬을 E1, E2 , ... , En 이라고 쓰면, En ... E2 E1 M = E 와 같이 되었다는 말이다.
( En ... E2 E1 ) M = E 이므로, En ... E2 E1 는 M 의 역행렬이다. 단위행렬은 곱하나 마나 이므로, En ... E2 E1 E 라고 쓸 수 있다.
결과적으로, A 에 무슨짓을 해서 단위행렬이 되었을때, 그 짓을 단위행렬에다가 그대로 수행하면, 곧 M 의 역행렬이 된다는 말이 된다.
얼추 이런식으로 하는걸 가우스-조단 방법이라고 부른다. 물론, 사소한 차이에 따라 이름이나 버전이 좀 다른거 같다. 큰 차이는 없다. 정말 사소한 차이다. 근데, 수치에서는 이런 아주 사소한 차이가, 에러의 오더를 바꿔놓기도 하기 때문에, 나름 중요성이 있을수 있지만, 여기서는 에러에 대한 이야기는 안하니까 그런건 관심밖이 된다.
이제 주어진 정방행렬 M 에 대해서 기본행연산을 수행하여 단위행렬로 만드는 짓을 하는데, 같은 짓을 단위행렬에 똑같이 해줘야 하므로, 그냥 두 행렬을 하나로 합쳐서 작업을 하면 편하다. 보통 augmented matrix 라고 부른다.
M 과 E 를 나란히 붙여놓은 상태에서, 행연산을 하면, M 과 E 에 동시에 작용하기 때문에, M 에 하는 행연산을 자연스럽게 단위행렬에 수행해줄수 있다.
M 를 단위행렬로 만들기 위해서는 M 의 대각선 성분이 모두 1 이고, 나머지는 0 이 되도록 연산을 해줘야 하므로, 소거 과정중 M 의 대각선 성분이 0 이 될 경우, 다른행와 로우 인터체인지를 해줘야 한다. 이를 pivoting 이라고 한다. ( 참고로, 각 행의 0 아닌 리딩 엘레멘트를 pivot 이라고 한다. )
암튼, 그러고 나서, 각 행을 pivot 으로 나눠주면 ( = 로우 멀티플리케이션) , 대각선 성분은 1 이 될 것이다.
나머지 원소를 0 으로 만드는 것은 피벗을 1로 만든 상태에서 로우 리플레이스먼트를 다른 모든행에 작용함으로써 쉽게 가능하다.
또는, 피벗 아랫쪽만 0 으로 보내서 upper triangle matrix 를 만든다음에, 맨 아랫 행부터 윗쪽으로 상삼각 부분을 0 으로 보내되 된다.
이렇게 아래서 부터 연쇄적으로 한방에 터는 것을 back-substitution 이라고 한다.
이론적으로는 이것으로 충분하지만, 실제적으로 수치적인 부분에 있어서는 오차를 줄이는 문제가 상당히 중요하므로, 로우 인터체인지를 할때, 가능한한 대각선 성분의 절대값이 큰 값이 되도록 하는것이 권장되는데, 이유는 큰값으로 나눌때 수치적인 오차가 더 작게 발생하기 때문이다.
* 알고리듬의 개념적 이해.
간단히 3 x 3 에 대해 그림으로 이해해보자.
첫번째 스텝은 피버팅으로 로우 인터체인지를 사용한다. 두번째 스텝은 로우 멀티플리케이션, 세번째 스텝은 로우 리플레이스먼트 이다.
이것이 하나의 싸이클이다. 이러한 싸이클을 행의 수만큼 해야한다.
두번째 싸이클에서는 2,2 가 피벗이 되도록 피버팅을 하고 ( 즉, 2,2 아래쪽에 대해 절대값이 가장큰 녀석을 골라 대각선에 오도록 행교환을 한다.)
그리고 나서, 두번째 행을 그 값으로 나눠주면 2,2 성분이 1 이 된다. 이제 그것으로 2열의 나머지 성분들을 모두 0 으로 만든다.
이런식으로 n 차 행렬에 대해 n 싸이클을 반복하면 된다.
* C 로 구현
첨부파일 :
inverse.exe위의 알고리듬을 이해했다면, 이것은 사람이 하는일을 그냥 기계가 대신하도록 만든것이다.
다음의 프로그램은 위에서 설명한 것을 고대로 옮긴것이다.
프로그램을 실행하고, 정방 행렬의 사이즈를 입력한다.
그리고 원소를 입력한다.
화면에서와 같이 스페이스바로 구분하면서 넣어도 되고, Tab 키로 띄면서 넣어도 된다. 그냥 계속 엔터로 구분하며 넣어도 된다.
다 입력하면, 행렬을 한번 정돈해서 보여주고, 오그멘티드 행렬을 보여준후에, 위에서 말한 과정으로 역행렬을 구해준다.
각 싸이클에는 세 덩어리의 오그멘티드 메이트릭스가 나오는데, 차례대로 위 그림에서 말하는 스텝1 , 스텝2 , 스텝3 를 보여준다.
대강 이런식이다.
주의: 에러처리 전혀 없음.