5장행렬

이산수학

5장. 행렬

1

이산수학

출처

본 강좌 자료는 이산수학 (2학년 / 3학점/ 3시간 / 이론) 수업에서 사용한 교재 [이산수학 (수학으로 이해하는 디지털 논리), 한빛

아카데미 출판사] 의 내용 등을 출처로 작성하였음을 알리는 바입니다.

2

이산수학

학습 목표

■

행렬을 사용한 연립방정식 의 표현법 이해

■

분석적 방법을 이용한 선형 연립방정식의 해를 구하는 문제 이해

3

이산수학

학습 내용

■

선형 연립방정식의 해를 구하는 문제

◻

역행렬 이용

◻

행렬 이용한 Gauss-Jordan 알고리즘

◻

후진대입법 이용한 Gauss 소거법 알고리즘

■

행렬 연산, 행렬식, 여인수 행렬, 전치행렬, 역행렬, 가우스 행렬, 단위 행렬 등 이해

4

이산수학

행렬의 응용 분야

■

선형대수(Linear Algebra)

■

수치해석(Numerical Analysis)

■

컴퓨터 그래픽(Computer Graphics)

■

네트워크 설계(Network Design)

■

인공지능 (Artificial Intelligence)

■

논리회로 (Digital Logic) 등

5

이산수학

선형 연립방정식의 해법

■

자연과학 또는 사회과학의 여러 현상들을 수학모델링 하면 미분방정식 또는 편 미분방정식 등으로 표현되는데, 이것을 컴퓨터 프로그래밍하기 전에 대부분의 경우 많은 미지수를 가진 선형 또는 비선형 연립방정식으로 표현.

■

선형 연립방정식은 행렬로 표현되며, 이것을 다루는 많은 프로그래밍 패키지들이 존재.

■ 선형 연립방정식은 과학계산에 있어서, 손으로 문제를 풀 수 있는 경우는,

기껏해야 4~5개 정도이며, 미지수가 많아지면, 거의 계산이 불가능.

■

𝑛개의 미지수를 가진 선형 연립방정식 풀이 방법

◻

Gauss-Jordan, Gauss 소거법

◻

적은 오차를 갖는 선형연립방정식의 해를 구하기 위해 수치해석 법

6

이산수학

일차 선형 방정식(first order linear equation)

■

형식 ∶ 𝑎₁𝑥₁+𝑎₂𝑥₂+…+𝑎_𝑛𝑥_𝑛=𝑏

◻

𝑎₁, 𝑎₂, … , 𝑎_𝑛 : 계수(coefficient)

◻

𝑏 ∶ 상수(constant)

◻

𝑥₁, 𝑥₂, … , 𝑥_𝑛 : 미지수(unknown variable)

■

예: 𝑥 + 2𝑦 − 𝑧 = 9 , 𝑥₁−𝑥₂ + 4𝑥₃ = 0 , ¹

3𝑥 = 3𝑦

7

이산수학

𝒎 × 𝒏 행렬 A (Matrix)

■

𝑚 :행의 개수, 𝑛 ∶ 열의 개수

■

정방행렬 ( square matrix)

◻

𝑚 = 𝑛

𝑨 = 𝑎_{𝑖𝑗 𝑚×𝑛} =

𝑎₁₁ 𝑎₁₂ ⋯ 𝑎_1𝑗 ⋯ 𝑎_1𝑛 𝑎₂₁ 𝑎₂₂ ⋯ 𝑎_2𝑗 ⋯ 𝑎_2𝑛

⋮

𝑎_𝑖1 𝑎_𝑖2 ⋯ 𝑎_𝑖𝑗 ⋯ 𝑎_𝑖𝑛

⋮

𝑎_𝑚1 𝑎_𝑚2 ⋯ 𝑎_𝑚𝑗 ⋯ 𝑎_𝑚𝑛

8

이산수학

선형 연립방정식의 𝒎 × 𝒏 행렬식 표현

■ 𝑛 개의 미지수를 갖는 𝑚 개의 선형 연립 방정식의 행렬

■

행렬 𝐵 와 행렬 𝐴 을 함께 결합하여 행렬 표시( 𝐴: 𝐵 , augmented matrix ) 𝑎₁₁𝑥₁ + 𝑎₁₂𝑥₂ +…+ 𝑎_1𝑛𝑥_𝑛 = 𝑏₁

𝑎₂₁𝑥₁ + 𝑎₂₂𝑥₂ +…+ 𝑎_2𝑛𝑥_𝑛 = 𝑏₂ ⋮

𝑎_𝑚1𝑥₁ + 𝑎_𝑚2𝑥₂ +…+𝑎_𝑚𝑛𝑥_𝑛 = 𝑏₂ 𝑨 =

𝑎₁₁ ⋯ 𝑎_1𝑛

⋮ ⋱ ⋮

𝑎_𝑚1 ⋯ 𝑎_𝑚𝑛 , 𝒙 = 𝑥₁

⋮

𝑥_𝑚 , 𝑩 = 𝑏₁

⋮ 𝑏_𝑚

, [𝑨: 𝑩] =

𝑎₁₁ ⋯ 𝑎_1𝑛

⋮ ⋱ ⋮

𝑎_𝑚1 ⋯ 𝑎_𝑚𝑛 𝑏₁

⋮ 𝑏₂

9

𝑨𝒙 = 𝑩

이산수학

예제

■

다음 3차 선형 연립방정식을 행렬식으로 표현하시오.

2𝑥₁ + 6𝑥₂ −2𝑥₃ = 7 −3𝑥₁ −3𝑥₂ +𝑥₃ = 0 4𝑥₂ +5𝑥₃ = −1 (풀이)

10

2 6 −2

−3 −3 1

0 4 5

𝑥₁ 𝑥₂

𝑥₃ = 7 0

−1

, [𝑨: 𝑩] = 2 6 −2

−3 −3 1

0 4 5

7 0

−1

이산수학

𝒏 × 𝒏 선형 연립방정식의 해

■ 𝑛 × 𝑛 선형 연립 방정식을 동시에 만족하는 𝑛개의 𝑥 _𝑖 값들의 집합을 이 방정식의 해 : { 𝑥 _𝑖 | 1 ≤ 𝑖 ≤ 𝑛 }

11

𝑎 ₁₁ 𝑥 ₁ + 𝑎 ₁₂ 𝑥 ₂ +…+ 𝑎 _1𝑛 𝑥 _𝑛 = 𝑏 ₁ 𝑎 ₂₁ 𝑥 ₁ + 𝑎 ₂₂ 𝑥 ₂ +…+ 𝑎 _2𝑛 𝑥 _𝑛 = 𝑏 ₂ ⋮

𝑎 _𝑛1 𝑥 ₁ + 𝑎 _𝑛2 𝑥 ₂ +…+𝑎 _𝑛𝑛 𝑥 _𝑛 = 𝑏 ₂

이산수학

행렬의 동치

■

두 행렬의 동치

◻

두 행렬의 행의 개수와 열의 개수가 동일.

◻

각 행렬의 각 위치의 해당 원소의 값이 동일

■

𝑎_𝑖𝑗 = 𝑏_𝑖𝑗, ∀ 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚

𝑎 ₁₁ ⋯ 𝑎 _1𝑚

⋮ ⋱ ⋮

𝑎 _𝑛1 ⋯ 𝑎 _𝑛𝑚

𝑏 ₁₁ ⋯ 𝑏 _1𝑚

⋮ ⋱ ⋮

𝑏 _𝑛1 ⋯ 𝑏 _𝑛𝑚

=

12

이산수학

행렬의 종류(1)

■

영 행렬(zero matrix)

◻

행렬의 모든 원소가 0 인 행렬

■

대각 행렬 (diagonal matrix)

◻

정방행렬에서 대각원소 𝑎₁₁, 𝑎₂₂, … , 𝑎_𝑛𝑛을 제외한 모든 원소가 0인 행렬

■

단위행렬 (Unit Matrix, Identity Matrix)

◻

대각행렬에서 대각원소가 모두 1인 행렬

𝐴=

𝑎₁₁ 0 0

… 0

𝑎₂₂

… 0

… 0

…

……

…0 𝑎_𝑛𝑛

대각행렬, 𝐴=

1 0 0

… 0

1

… 0

… 0…

……

…0 1

단위행렬

13

이산수학

행렬의 종류(2)

■

𝑛 × 𝑚 행렬 𝐴 = [𝑎_𝑖𝑗] 의 전치 행렬 (Transpose matrix)

◻

𝐴^𝑇 =[𝑏_𝑖𝑗]로 표시

◻

행렬 𝐴의 행과 열을 바꾼 𝑚 × 𝑛 행렬

◻

모든 𝑖, 𝑗 에 대하여 전치행렬의 원소 𝑏_𝑖𝑗=𝑎_𝑗𝑖 인 행렬

𝐴 =

𝑎₁₁ 𝑎₂₁ 𝑎₂₁

… 𝑎_𝑛1

𝑎₂₂

… 𝑎_𝑛2

… 𝑎_1𝑚

…

…

…

𝑎_2𝑚

… 𝑎_𝑛𝑚

⇒ 𝐴^𝑇=

𝑏₁₁ 𝑏₂₁ 𝑏₂₁

… 𝑏_𝑚1

𝑏₂₂

… 𝑏_𝑛2

… 𝑏_1𝑛

…

…

…

𝑏_2𝑛

… 𝑏_𝑚𝑛

14

이산수학

행렬의 덧셈연산

■

임의의 두 행렬 𝐴= 𝑎_𝑖𝑗 와 B= 𝑏_𝑖𝑗 의 덧셈 연산

◻

A 행렬의 행의 수 = 𝐵 행렬의 행의 수

◻

A 행렬의 열의 수 = 𝐵 행렬의 열의 수

◻

𝐴 + 𝐵 =[𝑐_𝑖𝑗]=[𝑎_𝑖𝑗 + 𝑏_𝑖𝑗], 모든 𝑖, 𝑗 에 대하여

𝐴 + 𝐵 =

𝑎₁₁ 𝑎₂₁ 𝑎₂₁

… 𝑎_𝑛1

𝑎₂₂

… 𝑎_𝑛2

… 𝑎_1𝑚

…

…

…

𝑎_2𝑚

… 𝑎_𝑛𝑚

+

𝑏₁₁ 𝑏₂₁ 𝑏₂₁

… 𝑏_𝑛1

𝑏₂₂

… 𝑏_𝑛2

… 𝑏_1𝑚

…

…

…

𝑏_2𝑚

… 𝑏_𝑛𝑚 =

𝑐₁₁ 𝑐₂₁ 𝑐₂₁

… 𝑐_𝑛1

𝑐₂₂

… 𝑐_𝑛2

… 𝑐_1𝑚

…

…

…

𝑐_2𝑚

… 𝑐_𝑛𝑚

15

이산수학

행렬의 스칼라곱(scalar product) 연산

■

행렬 𝐴 = 𝑎_𝑖𝑗 의 모든 원소에 실수 𝑘를 곱하는 연산

■

𝐴𝑘 = 𝑘𝐴 =[𝑘𝑎_𝑖𝑗]

𝑘𝐴=𝑘

𝑎₁₁ 𝑎₁₂ 𝑎₂₁

… 𝑎_𝑛1

𝑎₂₂

… 𝑎_𝑛2

… 𝑎_1𝑚

…

…

…

𝑎_2𝑚

… 𝑎_𝑛𝑚

=

𝑘𝑎₁₁ 𝑘𝑎₁₂ 𝑘𝑎₂₁

… 𝑘𝑎_𝑛1

𝑘𝑎₂₂

… 𝑘𝑎_𝑛2

… 𝑘𝑎_1𝑚

…

…

…

𝑘𝑎_2𝑚

… 𝑘𝑎_𝑛𝑚

16

이산수학

행렬의 곱셈 연산

■

𝑚 × 𝑘 행렬 𝐴 = 𝑎_𝑖𝑗 와 𝑙 × 𝑛 행렬 𝐵 = 𝑏_𝑖𝑗 에 대하여 k = 𝑙 일 때, 𝑚 × 𝑛 행렬 𝐴𝐵 = 𝑐_𝑖𝑗 의 각 원소는 다음과 같이 계산한다.

𝐴𝐵=

𝑎₁₁ 𝑎₁₂ 𝑎₂₁

… 𝑎_𝑚1

𝑎₂₂

… 𝑎_𝑚2

… 𝑎_1𝑘

…

…

…

𝑎_2𝑘

… 𝑎_𝑚𝑘

𝑏₁₁ 𝑏₁₂ 𝑏₂₁

… 𝑏_𝑙1

𝑏₂₂

… 𝑏_𝑙2

… 𝑏_1𝑛

…

…

…

𝑏_2𝑛

… 𝑏_𝑙𝑛

=

𝑐₁₁ 𝑐₁₂ 𝑐₂₁

… 𝑐_𝑚1

𝑐₂₂

… 𝑐_𝑚2

… 𝑐_1𝑛

…

…

…

𝑐_2𝑛

… 𝑐_𝑚𝑛

,

𝑐

_𝑖𝑗 = 𝑎_𝑖1𝑏_1𝑗 + 𝑎_𝑖2𝑏_2𝑗 + ⋯ + 𝑎_𝑖𝑘𝑏_𝑘𝑗 = ^𝑘_𝑠=1 𝑎_𝑖𝑠𝑏_𝑠𝑗

17

이산수학

행렬연산의 성질

■

행렬 𝐴 , 𝐵, 𝐶, 𝐼(단위행렬), 0(영행렬)에 대하여 다음과 같은 성질이 성립한다.

덧셈 연산 성질 스칼라곱 연산 성질 곱셈 연산 성질

𝐴 + 𝐵 = 𝐵 + 𝐴 −1 𝐴 = −𝐴 𝐴(𝐵𝐶) = (𝐴𝐵)𝐶 𝐴 + (𝐵 + 𝐶) = (𝐴 + 𝐵) + 𝐶 𝑘 𝐴 + 𝐵 = 𝑘𝐴 + 𝑘𝐵 𝐴(𝐵 + 𝐶) = 𝐴𝐵 + 𝐴𝐶

𝐵 + 𝐶 𝐴 = 𝐵𝐴 + 𝐶𝐴 𝐴 + 𝑂 = 𝑂 + 𝐴 = 𝐴 𝑘 + 𝑙 𝐴 = 𝑘𝐴 + 𝑙𝐴 𝐼𝐴 = 𝐴𝐼 = 𝐴

𝐴 + −𝐴 = −𝐴 + 𝐴 = 0 𝑘𝑙 𝐴 = 𝑘(𝑙𝐴) 𝑘 𝐴𝐵 = 𝑘𝐴 𝐵 = 𝐴(𝑘𝐵)

18

이산수학

예제

■

^행렬 𝐴 , 𝐵, 𝐶가 다음과 같을 때, 행렬 연산을 하시오.

𝐴 = 1 3

4 6 𝐵 = 1 0 2 9 3 8 4 7 5

𝐶 = 0 6 1 3 5 2

(1) 𝐴C (2) 𝐶𝐵 (3) 𝐴² (4) −2C

19

이산수학

행렬식(Determinant)

■

𝑛 × 𝑛 정방행렬 𝐴 = 𝑎_𝑖𝑗 에 대한 행렬식 |𝐴|= det(𝐴 ) =

𝑎₁₁ 𝑎₁₂ 𝑎₂₁

… 𝑎_𝑛1

𝑎₂₂

… 𝑎_𝑛2

𝑎_1𝑗 𝑎₁₂ 𝑎_2𝑗

… 𝑎_𝑛𝑗

𝑎₂₂

… 𝑎_𝑛2

= 𝑎_1𝑗

𝐶

_1𝑗 + 𝑎_2𝑗

𝐶

_2𝑗+…+ 𝑎_𝑛𝑗

𝐶

_𝑛𝑗

(𝑗열을 기준)

◻

여인수(Cofactor) : 𝐶_𝑖𝑗=(−1)^𝑖+𝑗det(𝑴_𝑖𝑗)

◻

소행렬 minor matrix ∶

𝑴

_𝑖𝑗은 정방행렬 A 의 𝑖 행과 𝑗열을 제거해서 얻은 𝑛 − 1 × 𝑛 − 1 행렬

20

이산수학

예제

■

다음 행렬의 행렬식을 계산하시오.

(1) 𝐴 = 3 1

2 −1 (2) 𝐵 = 3 −1 −2

−4 2 1 1 4 −3 (풀이) 1열을 기준으로 전개한다.

(1) det(𝐴)=3× −1 + (−2)×(1) = −3 − 2 = −5

(2) det(𝐵)=(3)(-6-4) + (-1)(-4)(3+8) + (1)(1)(-1+4) =17

21

이산수학

역행렬

■

정방행렬 A 에 대해 𝐴𝐵 = 𝐵𝐴 = 𝐼 를 만족하는 행렬 𝐵 를 역행렬

■

A⁻¹로 표시

■

AA⁻¹= A⁻¹𝐴 = 𝐼

■

det(A) ≠ 0

■

만일 역행렬이 존재하면 유일하게 하나 존재한다.

■

행렬 A을 가역행렬(invertible matrix) 또는 정칙행렬(nonsingular matrix)이라 한다.

22

이산수학

행렬식을 이용한 역행렬 계산

■

행렬 𝑨 가 정칙행렬인 경우 행렬식 𝒅𝒆𝒕(𝑨) ≠0 이다.

𝑨^−𝟏= ^𝟏

𝒅𝒆𝒕(𝑨) 𝑪_𝒊𝒋 ^𝑻

◻

𝑪_𝒊𝒋 ^𝑻 : 여인수 행렬 𝑪_𝒊𝒋 에 대한 전치행렬

◻

𝑪_𝒊𝒋

=(−𝟏)

^𝒊+𝒋𝐝𝐞𝐭(𝑴_𝒊𝒋

)

23

이산수학

예제

■

다음 행렬 A = 1 −1 2 2 1 −3

4 1 1

의 역행렬을 구하시오.

(풀이) 1열 기준으로 전개

(1) det 𝐴 = 𝑎₁₁𝐶₁₁ + 𝑎₁₂𝐶₁₂ + 𝑎₁₃𝐶₁₃ = 𝐶₁₁ − 𝐶₁₂ + 2𝐶₁₃

= −1 ¹⁺¹ det 𝑀₁₁ − (−1)¹⁺²det (𝑀₁₂)+2(−1)¹⁺³det (𝑀₁₃ = 1 −3

1 1 + 2 −3

4 1 + 2 2 1

4 1 = 1 ∙ 1 − −3 ∙ 1 + 2 ∙ 1 − −3 ∙ 4 + 2 2 ∙ 1 − 1 ∙ 4 = 14. ∴ det 𝐴 ≠0 즉, 정칙행렬이다.

24

이산수학

(2) 여인수 계산

𝐶₁₁ = −1 ¹⁺¹ det 𝑀₁₁ = 1 −3

1 1 = 1 ∙ 1 − (−3) ∙ 1 = 4 𝐶₁₂= −1 ¹⁺²det 𝑀₁₂ = − 2 −3

4 1 = − 2 ∙ 1 − −3 ∙ 4 = −14 𝐶₁₃ = −1 ¹⁺³det 𝑀₁₃ = 2 14 1 = 2 ∙ 1 − 1 ∙ 4 = 2

𝐶₂₁ = −1 ²⁺¹ det 𝑀₂₁ = − −1 21 1 = −((−1)1 ∙ 1 − 2 ∙ 1) =3 𝐶₂₂ = −1 ²⁺²det 𝑀₂₂ = 1 24 1 = 1 ∙ 1 − 2 ∙ 4 = −7

𝐶₂₃ = −1 ²⁺³det 𝑀₂₃ = − 1 −14 1 = − 1 ∙ 1 − −1 ∙ 4 = −5 𝐶₃₁ = −1 ³⁺¹det 𝑀₃₁ = −1 2

1 −3 = (−1) ∙ (−3) − 2 ∙ 1 = 1 𝐶₃₂ = −1 ³⁺²det 𝑀₃₂ = − 1 2

2 −3 = − 1 ∙ (−3) − 2 ∙ 2 = 7 𝐶₃₃ = −1 ³⁺³det 𝑀₃₃ = 1 −12 1 = 1 ∙ 1 − (−1) ∙ 2 = 3 (3) 여인수 행렬의 전치행렬을 이용한 역행렬 계산

𝐶_𝑖𝑗 = 4 −14 −2 3 −7 −5

1 7 3

, 𝐶_𝒊𝒋 ^𝑻= 4 3 1

−14 −7 7

−2 −5 3

∴ 𝐴⁻¹ = ¹

14

4 3 1

−14 −7 7

−2 −5 3

= 2/7 3/14 1/14

−1 −1/2 1/2

−1/7 −5/14 3/14

25

이산수학

1차 선형연립방정식의 해법(1)

■

1차 선형연립방정식 𝑨𝒙 = 𝑩의 계수행렬 𝑨가 정칙행렬인 경우 연립방정식의 해는 다음과 같다.

𝒙 = 𝑨^−𝟏 𝑩

26

𝑨 =

𝑎₁₁ ⋯ 𝑎_1𝑛

⋮ ⋱ ⋮

𝑎_𝑛1 ⋯ 𝑎_𝑛𝑛 , 𝒙 = 𝑥₁

⋮

𝑥_𝑛 , 𝑩 = 𝑏₁

⋮ 𝑏_𝑛

이산수학

문제

■

1차 선형연립 방정식에 대하여 역행렬을 구하여 해를 구하라.

𝑥₁+ 𝑥₂ + 2𝑥₃ = 9 2𝑥₁+ 4𝑥₂ − 3𝑥₃ = 1 3𝑥₁+ 6𝑥₂ − 5𝑥₃ = 0

27

이산수학

1차 선형연립방정식의 해법(2)

■

Gauss-Jordan 알고리즘

■

기본 행 연산을 사용하여 augmented matrix [𝑨: 𝑩]의 계수행렬 𝑨 부분을 대각행렬로 만들어 연립방정식의 해를 구하는 방법

■

선형 방정식이 미지수 한 개만을 갖도록 다른 미지수 소거

28

[𝑨: 𝑩] =

𝑎₁₁ ⋯ 𝑎_1𝑛

⋮ ⋱ ⋮

𝑎_𝑛1 ⋯ 𝑎_𝑛𝑛 𝑏₁

⋮ 𝑏_𝑛

이산수학

기본 행 연산(elementary row operation)의 정의

■

주어진 행렬에 대한 다음과 같은 연산을 기본 행 연산.

◻ 행

의 순서를 바꾸기

◻ 행

에 임의의 상수 k 곱하기

◻ 행

에 다른 행을 k 곱하여 더하기

29

이산수학

기본 행 연산을 사용하여 대각행렬로 만들기

1. 𝑎₁₁ 을 제외하고, 첫 번째 열에 남아 있는 다른 원소들을 0으로 만든다.

(즉, 다른 방정식에서 미지수 𝑥₁을 소거)

2. 𝑎₂₂ 을 제외하고, 두 번째 열에 남아 있는 다른 원소들을 0으로 만든다.

(즉, 다른 방정식에서 미지수 𝑥₂을 소거)

3. 위의 과정을 남아있는 나머지 열에 대하여 반복한다. 즉, 𝑎_𝑗𝑗 을 제외하고, 𝑗 번째 열에 남아 있는 다른 원소들을 0으로 만든다. (즉, 다른 방정식에서 미지수 𝑥_𝑗을 소거)

30

이산수학

예제

■

연립 1차 방정식을 Gauss-Jordan방법으로 해를 구하라.

𝑥₁+ 𝑥₂+ 2𝑥₃ = 9 2𝑥₁+ 4𝑥₂ − 3𝑥₃ = 1 3𝑥₁+ 6𝑥₂ − 5𝑥₃ = 0 (풀이) Let 𝐴: 𝐵 = 1 1 2

2 4 −3 3 6 −5

9 1 0

① 2행 ← 1행 ×(−2)+2행 : 1 1 2 0 2 −7 3 6 −5

9

−17 0

② 3행 ← 1행 ×(−3)+3행 : 1 1 2 0 2 −7 0 3 −11

9

−17

−18

31

이산수학

③ 1행 ← 2행 ×(−

¹₂

)+1행 : 1 0

¹¹₂

0 2 −7 0 3 −11

35

−17

2

−27

④ 3행 ← 2행 ×(−

³₂

)+3행 :

1 0

¹¹₂

0 2 −7 0 0 −

¹₂

35

−17

2

−

³₂

⑤ 1행 ← 3행 ×(11)+1행 :

1 0 0 0 2 −7 0 0 −

¹₂

1

−17

−

³₂

⑥ 2행 ← 3행 ×(−14)+2행 :

1 0 0 0 2 0

0 0 −

¹₂

1 4

−

³₂

⑦ −

¹₂

𝑥

₃

= −

³₂

, 2 𝑥

₂

= 4, 1𝑥

₁

= 1 ∴ 𝑥

₁

=3, 𝑥

₂

=2, 𝑥

₃

= 1

32

이산수학

Gauss-Jordan 알고리즘 단점

■

𝑛 × 𝑛 1 차 선 형 연 립 방 정 식 의 해 를 구 하 기 위 해 , 𝑂(𝑛² ) 의 곱셈연산이 필요.

■

대안: 가우스 소거법 알고리즘

◻

가 우 스 행 렬 (Gauss matrix): 연 립 방 정 식 을 상 삼 각 형 (upper triangle) 형태로 표현

◻

후진대입법(backward substitution): 삼각화된 연립방정식을 마지막 방정식에서 시작하여 차례로 대입하여 모든 미지수의 해를 구하는 방식

33

이산수학

프로그래밍 문제

■

Gauss-Jordan 알고리즘을 이용하여 1차 선형연립방정식의 해를 구하는 프로그램 작성하기

■요구조건

:

◻

Input 데이터 : 프로그램 실행 중에 행렬의 크기와 Augmented matrix 데이터를 입력 받기

◻

Output 데이터:

1.

출력 예시처럼 입력 정보와 해를 출력하기

2.

프로그램의 running time 계산하기

34

이산수학

1차 선형연립방정식의 해법(3)

■

Gauss 소거법 알고리즘

■

기본 행 연산을 사용하여 augmented matrix의 계수행렬 부분을 상삼각 행렬(upper triangular matrix)로 만들고 미지수를 유도하기 위해 후진 대입법을 사용하여 연립방정식의 해를 구하는 방법

■

계수행렬의 대각원소를 기준으로 아래쪽 원소들은 모두 0으로 만든 후 위쪽 원소들은 계수들로 남겨놓으며, 마지막 방정식에서 하나의 미지수만 남을 때까지 위의 소거 과정을 수행하여 다음과 같은 형태의 첨가행렬로 변환

𝑎₁₁ 𝑎₁₂ 0

… 0

𝑎₂₂

… 0

… 𝑎_1𝑛

…

…

…

𝑎_2𝑛

… 𝑎_𝑛𝑛

𝑏₁ 𝑏₂ 𝑏…_𝑛

35

이산수학

예제

■ 다음 연립 1차 방정식을 가우스 소거법으로 해를 구하라.

𝑥

₁

+ 𝑥

₂

+ 2𝑥

₃

= 9 2𝑥

₁

+ 4𝑥

₂

− 3𝑥

₃

= 1 3𝑥

₁

+ 6𝑥

₂

− 5𝑥

₃

= 0 (풀이) [𝑨: 𝑩]= 1 1 2

2 4 −3 3 6 −5

9 1 0

⇒

① 2행 ← 1행 ×(−1)+2행 : 1 1 2 0 2 −7 3 6 −5

9

−17 0

② 3행 ← 1행 ×(−3)+3행 : 1 1 2 0 2 −7 0 3 −11

9

−17 27

③ 3행 ← 2행 ×(−

³₂

)+3행 :

1 1 2 0 2 −7 0 0 −

¹

2

9

−17

−

³

2

𝑥

₁

+ 𝑥

₂

+2𝑥

₃

= 9 2𝑥

₂

− 7𝑥

₃

= − 17

−

¹₂

𝑥

₃

= −

³₂

∴ 𝑥

₁

= 1, 𝑥

₂

= 2, 𝑥

₃

= 3

36

이산수학

프로그래밍 문제

■

Gauss-Jordan 알고리즘과 Gauss 소거법을 이용하여 1차 선형연립방정식의 해를 구하는 프로그램 작성하기

■

요구조건:

◻

Input 데이터 : 프로그램 실행 중에 행렬의 크기와 Augmented matrix 데이터를 입력 받기

◻

Output 데이터:

1.

출력 예시처럼 입력 정보와 해를 출력하기

2.

프로그램의 running time 계산하기

37

이산수학

Gauss 소거법 알고리즘의 단점

■

방정식의 개수가 수십 개인 작은 연립 일차 방정식에서 상당히 정확한 해를 제공한다.

■

미지수의 개수가 수백~수천 개 이상인 연립 방정식에서는 1) 산술 연산의 수가 많아 계산 시간이 많이 걸린다.

2) 개별 연산에서 발생하는 오차가 누적되어 상당히 부정확한 해를 구하게 된다.

■

대안 : 반복 계산법

1) 허용되는 오차를 조절함으로써 산술 연산의 수를 조정할 수 있다.

2) 이를 통해 실질적으로는 오차가 적은 해를 빠르게 구할 수 있다.

3) 반복 계산법의 종류: Jacobi 법, Gauss-Seidal법, SOR법

38