수치해석(Numerical Analysis)
선형연립방정식수치해석(Numerical Analysis)
선형연립방정식
In this chapter … In this chapter …
선형
연립
방정식
선형
연립
방정식의
해를
구하는
문제를
다룬다
.
선형
연립
방정식은
다음과
같은
연립
1차
방정식을
의미한다
.
..
..
3231xyxy..1, 0xy
We will cover …
. 선형
연립
방정식의
이해
. 가우스-조단
알고리즘
. 역진
대입법
(후진
대입법
)을
이용한
가우스
소거법
. 가우스-자이달
알고리즘
Page 2
We are now … We are now …
선형
연립
방정식
선형연립방정식의이해
가우스-조단
알고리즘
역진
대입법을
이용한
가우스
소거법
가우스-자이달
알고리즘
Page 3
선형연립방정식의형태선형연립방정식의형태
선형
연립
방정식의
이해
n개의
변수
(x1, x2, ..., xn)을
가지는
m개의
선형
연립
방정식
11112211211222221122
nnnnmmmnnmaxaxaxbaxaxaxbaxaxaxb
....
....
....
m개
방정식들을
만족하는
n개의
xi 값들의
집합을
이
방정식의
해라
한다
.
연립
방정식의
해는
1) 한
개
혹은
여러
개일
수
있고
,
2) 무한히
많을
수도
있으며
(부정),
3) 없을
수도
있다
(불능).
Page 4
선형의존(Linear Dependent) (1/2) 선형의존(Linear Dependent) (1/2)
선형
연립
방정식의
이해
하나의
방정식이
다른
방정식들의
합으로
표현될
수
있으면
, 그
방정식은
다른
방정식들에
대해
선형
의존
(linear dependent)한다고
정의한다
.
만일
m번째
방정식이
다른
방정식들에
대해
선형
의존한다면
, m번째
방
정식은
다음과
같이
표현할
수
있다
.
..
..
..
1122111112212211222211,111,221,112211
mmmnnnnnnmmmmnnmmmaxaxaxkaxaxaxkaxaxaxkaxaxaxbkbkbkb
....
..
.......
.....
....
.....
Page 5
선형의존(Linear Dependent) (2/2) 선형의존(Linear Dependent) (2/2)
선형
연립
방정식의
이해
3원
연립
방정식의
선형
의존
예
...
...
...
1) 12) 2243) 4346xyzxyzxyz
그런데, 다음
관계가
성립하므로
,
..
...........
4342()1(22)21146xyzxyzxyz
상기
예에서
3)번
방정식은
1)번및
2)번
방정식에
선형
의존적이다
.
.
선형
의존인
방정식은
전체
해에
영향을
주지
않으므로
,
무시할
수
있다
. ( 무시하는
것이
좋다
.)
Page 6
불일치(Inconsistent) (1/2) 불일치(Inconsistent) (1/2)
선형
연립
방정식의
이해
한
방정식의
좌변은
다른
방정식들의
좌변의
합으로
표현될
수
있으나
,
그
방정식의
우변은
다른
방정식들의
우변의
합으로
표현할
수
없는
경우
,
이들
방정식은
불일치(inconsistent)한다고
정의한다
.
연립
방정식의
불일치는
다음과
같이
표현할
수
있다
.
..
..
..
1122111112212211222211,111,221,112211
mmmnnnnnnmmmmnnmmmaxaxaxkaxaxaxkaxaxaxkaxaxaxbkbkbkb
....
..
.......
.....
....
.....
Page 7
불일치(Inconsistent) (2/2) 불일치(Inconsistent) (2/2)
선형
연립
방정식의
이해
3원
연립
방정식의
불일치
예
...
...
...
1) 12) 2243) 4347xyzxyzxyz
그런데, 다음
관계가
성립하므로
,
4342()1(22)21147xyzxyzxyz
..
...........
상기의
연립
방정식은
불일치이다
.
.
불일치라면
해당
연립
방정식은
해를
가지지
않는다
. ( 불능)
Page 8
크레이머(Cramer)의법칙(1/6) 크레이머(Cramer)의법칙(1/6)
선형
연립
방정식의
이해
행렬식의
정의
A = [a]가
1 x 1 행렬이면
A의
행렬식은
|A| = a이다(det(A) 라고도
표현
).
A가
n x n 행렬이면, 소행렬(minor) Mij는
행렬
A의
i행과
j열을
소거하여
얻은
(n-1)x(n-1) 부분행렬의
행렬식이다.
Mij와
관련된
여인자(cofactor) Aij는
Aij = (-1)i+jMij이다.
n x n 행렬
A의
행렬식은
또는
11(1), where is one index in [1,]
nncjcjcjcjcjjjAaAaMcn.
..
.....
11(1), where is one index in [1,]
nniciciciciciiAaAaMcn.
..
.....
이다.
Page 9
크레이머(Cramer)의법칙(2/6) 크레이머(Cramer)의법칙(2/6)
선형
연립
방정식의
이해
행렬식
예제
...
..
...
...
....
..
.....
2130427034156680A
........
.
.
.....
...
.................
..
...
............
.............................
...............
.441414242434344444134343434343421300055(1)5542766827474252(1)368686610(2)876532421524niiiijijAaAaAaAaAaAaAaAAMM
...
...............
(12)
10(26)5(8)15(12)2604018040풀이: 네번째열(j=4)을사용하여전개한다.
Page 10
크레이머(Cramer)의법칙(3/6) 크레이머(Cramer)의법칙(3/6)
선형
연립
방정식의
이해
크래이머의
법칙
: n원
일차
연립
방정식
....
....
....
11112211211222221122
nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb
의
해는
다음과
같이
구할
수
있다
.
.iiAxA
|A|는
행렬
A의
행렬식인데
… A는
뭐고
.. Ai는
뭐지
?
Page 11
크레이머(Cramer)의법칙(4/6) 크레이머(Cramer)의법칙(4/6)
선형
연립
방정식의
이해
다음과
같은
n원
일차
연립
방정식이
있을
때
,
....
....
....
11112211211222221122
nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb
A와
Ai 는
각각
다음과
같이
정의한다
.
..
..
...
..
..
....
111212122212nnnnnnaaaaaaAaaa
..
..
..
..
..
...
..
..
....
111,111,11212,122,121,12,1iiniininnininnaabaaaabaaAaabaa
Page 12
크레이머(Cramer)의법칙(5/6) 크레이머(Cramer)의법칙(5/6)
선형
연립
방정식의
이해
크레이머
법칙의
적용
예제
...
...
...
1231231232342612510xxxxxxxxx
...
..
....
.....
2311211125A
...
..
....
.....
143162110125A
...
..
...
..
..
22411611105A
..
..
....
.....
323412611210A
실제
계산을
수행해
보세요
…
...312123, ,
AAAxxxAAA
Page 13
We are now … We are now …
선형
연립
방정식
선형
연립
방정식의
이해
가우스-조단알고리즘
역진
대입법을
이용한
가우스
소거법
가우스-자이달
알고리즘
Page 14
연립방정식의풀이예제(1/2) 연립방정식의풀이예제(1/2)
Gauss-Jordan Algorithm
다음과
같은
3원
1차
연립
방정식이
있다고
하자
.
...
...
...
123123123(1) 2411(2) 2523(3) 48xxxxxxxxx
방정식에
대한
곱셈
및
덧셈을
통하여
다음과
같이
해를
구할
수
있다
.
...
....
....
1232323(1) 2411(2) 619(3) 91536xxxxxxx......2(1)(2), 4(1)(3).....2(2)(1), 9(2)(3)
...
....
...
13233(1) 1649(2) 619(3) 69207xxxxx
Page 15
Gauss-Jordan Algorithm
연립방정식의풀이예제(2/2)
.....2(2)(1), 9(2)(3)
...
....
...
13233(1) 1649(2) 619(3) 69207xxxxx
166(3)(1), (3)(2)
6969
.....
.
..
...
123(1) 1(2) 1(3) 69207xxx....1231,1,3xxx
이와
같이
방정식에
대한
상수
곱셈
및
방정식
간의
덧셈으로
해를
구하는
방식이
가우스
-조던
방법이다
.
Page 16
가우스-조단방법의개념(1/4) 가우스-조단방법의개념(1/4)
Gauss-Jordan Algorithm
방정식에
대한
상수
곱셈
, 방정식들간의
덧셈을
통하여
동치인
새로운
방
정식을
만들
수
있다
.
가우스-조던
방법은
이러한
성질을
사용하여
연립
방정식을
해결한다
.
n원
1차
연립
방정식에
대한
가우스
-조단
방법은
다음과
같다
.
1) 다음과
같은
연립
방정식에서
,
....
....
....
11112211211222221122(1)
(2)
()
nnnnnnnnnnaxaxaxbaxaxaxbnaxaxaxb
Page 17
가우스-조단방법의개념(2/4) 가우스-조단방법의개념(2/4)
Gauss-Jordan Algorithm
2) 첫
번째
식에
얼마를
곱하여
다른
식과
덧셈을
하여
, 다른
방정식들에서
첫
번째
변수를
제거한다
.
....
...
...
(1)(1)(1)(1)
12111211(1)(1)(1)
22222(1)(1)(1)
22(1)
(2)
()
nnnnnnnnnaxaxaxbaxaxbnaxaxb
.........31121111111(1)(2),(1)(3),,(1)()naaanaaa
..
..
..
...
...
......
(1)(0)(1)(0)
(1)
(0)(0)
(1)(0)(0)(1)(0)(0)1111(0)(0)
1111, 10 1,1
, 1,2ijijiiijiiijijjiiaabbiaijaaaaabbbijaa
Page 18
가우스-조단방법의개념(3/4) 가우스-조단방법의개념(3/4)
Gauss-Jordan Algorithm
3) 두
번째
식에
얼마를
곱하여
다른
식과
덧셈을
하여
, 다른
방정식들에서
두
번째
변수를
제거한다
.
...
...
...
(2)(2)(2)
11111(2)(2)(2)
22222(2)(2)
(1)
(2)
()
nnnnnnnnaxaxbaxaxbnaxb
.........
(1)(1)(1)
32212(1)(1)(1)
222222(2)(1),(2)(3),,(2)()naaanaaa
..
..
..
.....
...
......
(2)(1)(2)(1)
(2)
(1)(1)
(2)(1)(1)(2)(1)(1)2222(1)(1)
2222, 2,20 2,2
, 2,3ijijiiijiiijijjiiaabbijnaijaaaaabbbijaa
Page 19
가우스-조단방법의개념(4/4) 가우스-조단방법의개념(4/4)
Gauss-Jordan Algorithm
4) 작업을
반복하면
결국
각
방정식의
좌변에는
하나의
변수만이
남게
된다
.
..
..
..
.
.
.
(1)(1)
1111(1)(1)
2222(1)(1)
(1)
(2)
()
nnnnnnnnnnaxbaxbnaxb
5) 결국
해는
다음과
같이
구할
수
있다
.
...
...
..
(1)(1)(1)
1212(1)(1)(1)
1122=,,,
nnnnnnnnnnbbbxxxaaa
상기
작업에서
각
단계를
피봇
주기
(pivot cycle) 이라
하고
, 각
단계에서
선택되는
방정식을
피봇
방정식
(pivot equation) 이라
한다
.
Page 20
가우스-조단방법의예제(1/2) 가우스-조단방법의예제(1/2)
Gauss-Jordan Algorithm
.........2(1)(2), 4(1)(3),2(1)(4)
.....
....
....
....
1234123412341234(1) 1(2) 2 6(3) 4 0(4) 2 2xxxxxxxxxxxxxxxx
.....
...
...
...
1234234234234(1) 1(2) 33 8(3) 533 4(4) 3 3 4xxxxxxxxxxxxx........1(2)(1), 5(2)(3),3(2)(4)
....
...
....
....
1342343434(1) 2 2 7(2) 3 3 8(3) 1212 36(4) 8 6 20xxxxxxxxxx
.......
238(3)(1), (3)(2),(3)(4)
121212
Page 21
가우스-조단방법의예제(2/2) 가우스-조단방법의예제(2/2)
Gauss-Jordan Algorithm
..
...
....
..
1424344(1) 0 1(2) 0 1(3) 121236(4) 2 4xxxxxxx
.......
238(3)(1), (3)(2),(3)(4)
121212
......
0012(4)(1), (4)(2),(4)(3)
222
.
..
...
..
1234(1) 1(2) 1(3) 12 12(4) 2 4xxxx......12341,1,1,2xxxx
Page 22
선형의존과가우스-조단선형의존과가우스-조단
Gauss-Jordan Algorithm
선형
의존적인
방정식이
있는
경우
, 가우스-조단을
수행하는
과정에서
자
연스럽게
사라진다
. (방정식을
확인해
볼
것
)
..
....
..
123123123(1)+24(2)33
(3)353=11xxxxxxxxx
..
..
.
123221(1)+227(2)5
27(3)=52xxxxx
..
.
1329(1)
710(2)
7(3)0=0xxx
Page 23
불일치와가우스-조단불일치와가우스-조단
Gauss-Jordan Algorithm
불일치가
있는
경우
, 가우스-조단
방법에서는
진리
값이
거짓인
명제가
발생한다. ( 불능) (방정식을
확인해
볼
것
)
..
....
..
123123123(1)2+24(2)33
(3)353=8xxxxxxxxx
..
.
1329(1)
710(2)
7(3)5=2xxx
Page 24
부정과가우스-조단부정과가우스-조단
Gauss-Jordan Algorithm
n원
연립
방정식에서
방정식의
개수가
n보다
작으면
, 일반적으로
여러
개
의근
(혹은
무수한
근
)이
존재할
수
있다
. ( 부정)
.
...
...
1212234(1)+ 2(2)3
(3)= 0xxxxxxx
..
.
...
12341(1)
25(2)
25(3)=
2xxxx
Page 25
가우스-조단알고리즘가우스-조단알고리즘
Gauss-Jordan Algorithm
procedure gauss-jordan(aij, bi: real numbers, n: integer)
{ aij are coefficients. (1 .i,j .n)}
{ bi are results. (1 .i .n)}
{ n is # of variables. (we assume that # of variables = # of equations.}
for k := 1 to n // pivot cycle
for i := 1 to n // i-th equation
begin
c := aik/akk;
for j := k to n
begin
if i = k then aij := aij, bi := bi; {actually, this line is not required.}
else if (i .k) and (j = k) then aij := 0;
else if (i .k) and (j > k) then aij := aij .c.akj;
end
if i .k then bi := bi .c.bk;
end ..
..
..
.....
...
......
(2)(1)(2)(1)
(2)
(1)(1)
(2)(1)(1)(2)(1)(1)2222(1)(1)
2222, 2,20 2,2
, 2,3ijijiiijiiijijjiiaabbijnaijaaaaabbbijaa
Page 26
가우스-조단프로그램(1/3) 가우스-조단프로그램(1/3)
Gauss-Jordan Algorithm
입력을
파일에서
받아들이며
, 각
피봇
주기별로
결과를
출력한다
.
Page 27
가우스-조단프로그램(2/3) 가우스-조단프로그램(2/3)
Gauss-Jordan Algorithm
Page 28
가우스-조단프로그램(3/3) 가우스-조단프로그램(3/3)
Gauss-Jordan Algorithm
Page 29
가우스-조단프로그램실행결과I (1/2) 가우스-조단프로그램실행결과I (1/2)
Gauss-Jordan Algorithm
사용한
연립
방정식
...
...
...
123123123(1) 2411(2) 2523(3) 48xxxxxxxxx
입력
파일
구성
Page 30
가우스-조단프로그램실행결과I (2/2) 가우스-조단프로그램실행결과I (2/2)
Gauss-Jordan Algorithm
Page 31
가우스-조단프로그램실행결과II (1/2) 가우스-조단프로그램실행결과II (1/2)
Gauss-Jordan Algorithm
사용한
연립
방정식
...
....
.....
......
124134123412342 2423246302082525231434xxxxxxxxxxxxxx
입력
파일
구성
Page 32
가우스-조단프로그램실행결과II (2/2) 가우스-조단프로그램실행결과II (2/2)
Gauss-Jordan Algorithm
Page 33
가우스-조단프로그램실행결과III (1/2) 가우스-조단프로그램실행결과III (1/2)
Gauss-Jordan Algorithm
사용한
연립
방정식
.....
....
......
....
.....
12345134523451235123452 37222534563xxxxxxxxxxxxxxxxxxxxxx
입력
파일
구성
Page 34
Algorithm
Page 35
-
가우스-조단프로그램실행결과III (2/2)
We are now … We are now …
Back substitution
선형
연립
방정식의
이해
가우스-조단
알고리즘
역진대입법을이용한가우스소거법
가우스-자이달
알고리즘
Page 36
역진대입법의동기및삼각화개념역진대입법의동기및삼각화개념
Back substitution
가우스-조던의
문제점
: n개의
변수를
갖는
n개의
방정식을
풀고자
할
경
우, 일반적으로
n 2의
연산
(곱셈, 덧셈
등
)이
필요하다
.
삼각화의
의미
: 연립
방정식을
궁극적으로
다음과
같은
삼각형
형태로
나
타내는
방식을
의미한다
.
...
..
.
123233242
=7xxxxxx
역진
대입법
: 삼각화된
연립
방정식을
마지막
방정식에서
시작하여
차례
로
대입하여
모든
변수의
해를
구하는
방식을
의미한다
.
Page 37
역진대입법(Back Substitution) 개념(1/2) 역진대입법(Back Substitution) 개념(1/2)
Back substitution
이
방법은
실제
우리가
“대입법”이라고
알고
있는
방법이다
.
(역진) 대입법을
사용한
연립
방정식
풀이
예제
.....
....
....
....
12341234123412341264022xxxxxxxxxxxxxxxx....12341xxxx
.....
...
...
...
123423423423413385334334xxxxxxxxxxxxx....234338xxx
Page 38
역진대입법(Back Substitution) 개념(2/2) 역진대입법(Back Substitution) 개념(2/2)
Back substitution
.....
...
....
....
1234234343413381212368620xxxxxxxxxxx..343xx
.....
...
....
..
1234234344133812123624xxxxxxxxxx......12341,1,1,2xxxx
Page 39
역진대입법알고리즘및프로그램역진대입법알고리즘및프로그램
Back substitution
가우스-조단
방법을
수정하여
알고리즘
및
프로그램을
만들
수
있다
.
Page 40
We are now … We are now …
Gauss-Seidal Algorithm
선형
연립
방정식의
이해
가우스-조단
알고리즘
역진
대입법을
이용한
가우스
소거법
가우스-자이달알고리즘
Page 41
가우스-자이달방법의동기(1/2) 가우스-자이달방법의동기(1/2)
Gauss-Seidal Algorithm
가우스-조단
방법
등은
방정식의
개수가
수십
개인
작은
연립
일차
방정
식에서
상당히
정확한
해를
제공한다
.
반면에, 미지수
(변수)의
개수가
수백
~수천
개
이상인
연립
방정식의
경우
,
1) 산술
연산의
수가
많아
계산
시간이
많이
걸리고
,
2) 개별
연산에서
발생하는
오차가
누적되어
상당히
부정확한
해를
구하게
된다는
결함이
있다
.
Page 42
가우스-자이달방법의동기(2/2) 가우스-자이달방법의동기(2/2)
Gauss-Seidal Algorithm
가우스-자이달
방법과
같은
반복
계산법은
미지수가
많은
연립
방정식의
해를
구하기
위한
방법으로서
,
1) 허용되는
오차를
조절함으로써
산술
연산의
수를
조정할
수
있으며
,
2) 이를
통해
실질적으로는
오차가
적은
해를
빠르게
구할
수
있다
.
반복
계산법의
종류
.
자코비(Jacobi) 반복
계산법
.
가우스-자이달
반복
계산법
.
SOR(Successive OverRelaxation) 법
Page 43
가우스-자이달방법의직관적설명가우스-자이달방법의직관적설명
Gauss-Seidal Algorithm
지금까지의
방법은
분석적
방법을
컴퓨터에
적용한
것이라
할
수
있다
.
반면에, 가우스-자이달
방법은
수치해석적
방법이다
. 즉,
1) 해를
계산
초기에
임의로
가정하고
,
2) 다음
단계에서
이전
해를
사용하여
더
나은
해를
구성하고
,
3) 상기
2)의
과정을
반복하여
원하는
수준의
해를
찾아낸다
.
가우스-자이달
방법은
반복을
통하여
해를
구해내므로
, 반복
계산법
(iteration method) 에
해당한다
.
Page 44
가우스-자이달방법의예제(1/2) 가우스-자이달방법의예제(1/2)
Gauss-Seidal Algorithm
다음
연립
방정식을
가우스
-자이달
방법으로
해결한다
.
...
....
.....
123123123423.0240.3240.8xxxxxxxxx
초기값을
할당한다
.
(당연한
이야기지만
, 초기값이
해에
가까울
수록
방정식이
빨리
풀린다
.)
첫
번째
방정식에서
첫
번째
변수를
제외한
다른
변수에
현재
해를
대입하
여
첫
번째
변수의
값을
구한다
.
.............(1)(0)(0)
123113231211.544xxx
Page 45
가우스-자이달방법의예제(2/2) 가우스-자이달방법의예제(2/2)
Gauss-Seidal Algorithm
두
번째
방정식에서
두
번째
변수를
제외한
다른
변수에
현재
해를
대입하
여
두
번째
변수의
값을
구한다
.
.............(1)(1)(0)
213110.320.321.511.07544xxx
세
번째
방정식에서
세
번째
변수를
제외한
다른
변수에
현재
해를
대입하
여
세
번째
변수의
값을
구한다
.
...............(1)(1)(1)
312110.820.81.521.0750.712544xxx
다시
처음으로
돌아가서
원하는
정확도를
얻을
때까지
상기
과정을
반복
한다. 일반적으로
정확도는
다음과
같이
정의한다
.
.
.
.
...
.()(1)
1nppiiixxen
Page 46
가우스-자이달방법의계산식가우스-자이달방법의계산식
Gauss-Seidal Algorithm
가우스-자이달
방법의
해를
계산하는
식은
다음과
같다
.
.
.
...
..
......
..
..
..
1()()(1)
111inpppijijiijjiijjixaxaxba
.............(1)(0)(0)
123113231211.544xxx
.............(1)(1)(0)
213110.320.321.511.07544xxx
...............(1)(1)(1)
312110.820.81.521.0750.712544xxx
Page 47
가우스-자이달알고리즘가우스-자이달알고리즘
Gauss-Seidal Algorithm
procedure gauss-seidal(aij, bi, xi, .: real numbers, n: integer)
{ aij are coefficients(1 .i,j .n), bi are results(1 .i .n), xi are initial values(1 .i .n).}
{ .is a user-specified tolerance.}
{ n is # of variables. (we assume that # of variables = # of equations.}
e := .;
while (e > .) begin
for i := 1 to n
begin
end
end
.
.
...
..
......
..
..
..
1()()(1)
111:;
inpppijijiijjiijjixaxaxba
.
.
.
.
.()(1)
1;
nppiiixxen
Page 48
가우스-자이달프로그램(1/4) 가우스-자이달프로그램(1/4)
Gauss-Seidal Algorithm
Page 49
가우스-자이달프로그램(2/4) 가우스-자이달프로그램(2/4)
Gauss-Seidal Algorithm
.
.
...
..
......
..
..
..
1()()(1)
111:;
inpppijijiijjiijjixaxaxba
Page 50
가우스-자이달프로그램(3/4) 가우스-자이달프로그램(3/4)
Gauss-Seidal Algorithm
Page 51
가우스-자이달프로그램(4/4) 가우스-자이달프로그램(4/4)
Gauss-Seidal Algorithm
.
.
.
.
.()(1)
1;
nppiiixxen
Page 52
가우스-자이달프로그램실행결과I(1/2) 가우스-자이달프로그램실행결과I(1/2)
Gauss-Seidal Algorithm
사용한
연립
방정식
...
....
.....
1231231234 23240.3240.8xxxxxxxxx
초기
해
입력
파일
구성
Page 53
가우스-자이달프로그램실행결과I(2/2) 가우스-자이달프로그램실행결과I(2/2)
Gauss-Seidal Algorithm
Page 54
가우스-자이달프로그램실행결과II(1/2) 가우스-자이달프로그램실행결과II(1/2)
Gauss-Seidal Algorithm
사용한
연립
방정식
초기
해
...
.....
.....
...
1231234123423410 2611325210113815xxxxxxxxxxxxxx
입력
파일
구성
Page 55
가우스-자이달프로그램실행결과II(2/2) 가우스-자이달프로그램실행결과II(2/2)
Gauss-Seidal Algorithm
가우스-자이달
알고리즘의
경우
, 방정식의
종류
,
초기
해의
값에
따라서
발산하는
경우가
많이
발생한다
.
Page 56