이산수학_역행렬

소개글

이산수학_역행렬에 대한 보고서 자료입니다.

목차

목 차

Ⅰ. 역행렬을 구하는 방법과 프로그램 2


Ⅰ-1. 문제 분석 3


Ⅰ-2. 소스 코드 8


Ⅰ-3. 결 과 26


Ⅰ-4. 결 론 32

본문내용

R E P O R T
과목명
:
이산수학
학과
:
컴퓨터학부B
담당교수
:
박두순 교수님
학번
:
20064367
이름
:
강대명
제출일
:
2010년 06월 05일
목 차
Ⅰ. 역행렬을 구하는 방법과 프로그램2
Ⅰ-1. 문제 분석3
Ⅰ-2. 소스 코드 8
Ⅰ-3. 결 과26
Ⅰ-4. 결 론32
Ⅰ-1. 문제 분석
가우스 소거법(Gaussian Elimination Method)
- 등식의 양변에 0이 아닌 어떤 수를 곱하거나 나누어도 등식은 성립한다.
- 연립방정식의 한 식을 다른 식과 가감하여 얻어진 새로운 식도 등식이 성립한다.
- 소거법은 연립방정식에 이 성질을 이용하여 미지수의 개수를 단계적으로 줄여 나가는 방법이다.
- 미지수란
방정식에서 구하려고 하는 수.
예를들어
2x₁+ x₂- 3x₃= 1 - ①
4x₁+ x₂- 2x₃= 4 - ②
3x₁+ 2x₂- x₃= 6 - ③
라고 하면 2x₁+ x₂- 3x₃= 1를 사용해서 차근차근 ②,③과 대입하여 단계적으로 줄여간다.
예> -2 * (2x₁+ x₂- 3x₃= 1) - ①
4x₁+ x₂- 2x₃= 4 - ②
---------------------------
- x₂+4x₃= 2 - ④
이런 방식으로① ,③도 줄이면
- x₂+4x₃= 2
- x₂-7x₃= -9
-------------------
11x₃= -11
∴ x₃= 1
그다음엔 후진대입을 사용하여 ④에서 - x₂+4x₃= 2 -> - x₂+4= 2 - > - x₂= -2
∴ x₂= 2
∴ x ₁= 1, x₂= 2 , x₃= 1
- 피벗팅(pivoting)
근을 구하기 위한 후진 대입 과정에서 대각요소로 나누는 작업이 필요하다. 이때 만약 대각 요소의 값이 '0'이라면 계산이 불가능하게 되고 또한 '0'에 가까운 값이라면 그 계산 결과는 부정확하게 된다.
- 대각요소란
정사각행렬에서 주대각선의 위에 있는 원소를 말한다. 즉, 행과 렬의 값이 같은 위치에 있는 원소이다.
가우스 조르단 법(Gauss Jordan Method)
가우스 조르단법은 가우스 소거법을 응용한 것으로서 대각요소만을 남기고 다른 요소들을 모두 소거하여 근을 구하는 방법이다.
특히, 대각요소의 크기를 '1'로 변환시킨 경우에는 상수항 벡터가 구하는 근이 된다.
① 주어진 연립방정식
↓
② 변형된 연립방정식
1x₁+0x₂+0x₃= a₁₄
0x₁+1x₂+0x₃= a₂₄
0x₁+0x₂+1x₃= a₃₄
③ 근
x₁= a₁₄
x₂= a₂₄
x₃= a₃₄
행의 수와 열의 수가 서로 같은 행렬을 정방행렬이라고 하고 정방행렬 중에서 대각요소들은 모두 '1'이고 나머지 요소들은 모두 '0'인 행렬을 단위행렬이라고 한다.
가우스 조르단법은 처음 주어진 계수 행렬을 단위행렬로 변환시키면 우변항 벡터는 근 벡터로 된다는 원리를 이용한 것이다.
소행렬식과 여인수 전개를 통한 역행렬 구하기
- 소행렬식과 여인수
에서 이 포함되는 행과 열을 제외한 나머지 원소들만으로 된 행렬식을 에 대한 소행렬식이라 부르고 기호로 이라 쓴다. 한편 이 포함되는 행과 열의 원소를 모두 0이라 하고 의 자리에 1을 넣은 행렬식을 여인수라 정의하고 이라 하자.
일반적으로 와 의 관계는 (4)와 같다.
(1)을 전개하면 (5)가 된다. (5)를 로 각각 묶어 정리한 것이 (6)이다.
- 여인수전개
(6)을 소행렬식을 이용해 표현한 것이 (7)이다.
(8)을 의 제1행에 대한 여인수 전개라 한다. 여인수 전개는 어떤 행(혹은 열)에 대해서도 성립한다.
3행3열까지의 행렬식은 사러스 법칙으로 비교적 쉽게 풀 수 있지만, 4행4열 이상은 직접 푸는 것이 꽤 어렵다. 따라서 n차 행렬식을 여인수 전개를 통해 n개의 (n-1)차 행렬식으로 분해하여 푼다. 이때 행렬식의 성질을 이용 하여 특정 행(혹은 열)에 0을 많이 만든 후 그 행을 중심으로 여인수 전개하면 계산량을 줄일 수 있다.
Ⅰ-2. 소스 코드 - 가우스 소거법
Ⅰ-2. 소스 코드 - 가우스 조르단법
Ⅰ-2. 소스 코드 - 소행렬식과 여인수 전개를 이용
Ⅰ-3. 결 과 - 가우스 소거법

Ⅰ-3. 결 과 - 가우스 조르단 법
- n값은 4로 하고 행렬의 원소들은 위의 가우스 소거법에서 사용한 원소들을 그대로 데이터파일에 저장함.
<데이터파일>
<실행결과>
- 역행렬을 구하는 과정
- 최종결과
Ⅰ-3. 결 과 - 소행렬식과 여인수 전개를 이용
- n x n 행렬에서 n의 값은 4로 하였고 각각의 원소들은 위에서 사용한 행렬의 원소들을 그대로 사용하였다.
- 최종실행결과
Ⅰ-4. 결 론
일단 결론을 작성하기에 앞서 위의 프로그램 소스들은 여러 수치해석 책에서 발췌하였음을 명시한다. 이번 리포트가 요구한 사항인 여러 가지 방법을 사용하여 n x n행렬의 역행렬을 구하고 n값을 2부터 1000까지 하였을 때 각각의 방법마다 오차가 생기는 지를 관찰하는 것이었으나, 구현된 3가지 방법의 프로그램에 똑같은 100만개의 원소를 빠르게 입력할 마땅한 방법이 없어서 마땅히 관찰할 수가 없었다. 그리하여 n값을 4로 하여 실험해 보았지만 숫자가 작아서인지 3가지 방법 모두 큰 오차가 발생한 것 같지는 않았다. 1000 x 1000행렬에 대해 실험을 못한 부분은 마땅히 아쉬운 점이며, 그나마 3가지 프로그램 모두 n값으로 1000입력하였을 때 오버플로를 발생시키지 않는 것으로 봐서는 프로그램은 잘 구현된 것 같아 그나마 다행인 것 같다.

키워드

역행렬,   이산수학,   가우스,   가우스조르단,   컴퓨터,   프로그램