수치해석(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
크레이머(Cramer)의법칙(6/6) 크레이머(Cramer)의법칙(6/6)
선형
연립
방정식의
이해
크레이머
법칙
적용의
문제점
:
일반적으로, n x n 행렬의
행렬식을
계산하려면
, O(n!)의
곱셈
(나눗셈)과
덧셈(뺄셈) 연산이
필요하다
.
.
변수가
적은
경우에는
처리가
가능하나
, 변수가
많아지면
(컴퓨터를
사용
해서도) 처리가
매우
어렵다
.
Page 14
복소수방정식(1/5) 복소수방정식(1/5)
선형
연립
방정식의
이해
지금까지
다룬
연립
방정식에
있어서
, 모든
계수는
실수라
가정하였다
.
그러나, 보다
일반화하면
연립
방정식의
계수는
복소수이다
.
예를
들어
, 다음
연립
방정식에서
aij 및
bi 복소수인
경우이다
.
....
....
....
11112211211222221122
nnnnmmmnnmasasasbasasasbasasasb
.....
......
1212(34)(2)48(12)(64)12isisiisisi
복소수
계수를
갖는
연립
방정식의
경우
, 해도
또한
복소수이다
.
Page 15
복소수방정식(2/5) 복소수방정식(2/5)
선형
연립
방정식의
이해
복소수의
성질
: 실수부와
허수부가
서로
독립적이기
때문에
서로
분리해
서
다룰
수
있다
.
다음은
이러한
독립성을
보여주는
복소수
덧셈과
곱셈의
예를
나타낸다
.
따라서, 연립
방정식의
각
계수를
실수부와
허수부로
구분하여
나타낸다
.
....
....
..
ijijijiiiiiiaibisxyi
Page 16
복소수방정식(3/5) 복소수방정식(3/5)
선형
연립
방정식의
이해
원래
방정식을
실수부
및
허수부로
분리한
표기법으로
기술한다
.
....
....
..
ijijijiiiiiiaibisxyi
....
....
....
11112211211222221122
nnnnmmmnnmasasasbasasasbasasasb
...................
...................
...........
1111111212221111212111222222222211112222()()()()()()
()()()()()()
()()()()(
nnnnnnnnmmmmixyiixyiixyiiixyiixyiixyiiixyiixyi........)()mnmnnnmmixyii
Page 17
복소수방정식(4/5) 복소수방정식(4/5)
선형
연립
방정식의
이해
실수부와
허수부를
분리하여
실수
계수만을
가지는
연립
방정식을
구성
한다. .결과적으로, 원래의2배의방정식이만들어진다.
..............
..............
..............
..............
...
1111111221221111111111221221112112112222222222112112222222221111
nnnnnnnnnnnnnnnnmmxyxyxyyxyxyxxyxyxyyxyxxxxy...........
..............
222211112222mmmnnmnnmmmmmmnnmnnmxyxyyxyxxy
변경한
후에는
실계수
연립
방정식
알고리즘을
사용하여
해를
찾는다
.
Page 18
복소수방정식(5/5) 복소수방정식(5/5)
선형
연립
방정식의
이해
복소수
방정식을
실계수
방정식으로
변경하는
예제
.....
......
1212(34)(2)48(12)(64)12isisiisisi
11221122112211223424342826412642xyxyyxxyxyxyyxyx
....
....
.....
......
Page 19
We are now … We are now …
선형
연립
방정식
선형
연립
방정식의
이해
가우스-조단알고리즘
역진
대입법을
이용한
가우스
소거법
가우스-자이달
알고리즘
Page 20
연립방정식의풀이예제(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 21
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 22
가우스-조단방법의개념(1/4) 가우스-조단방법의개념(1/4)
Gauss-Jordan Algorithm
방정식에
대한
상수
곱셈
, 방정식들간의
덧셈을
통하여
동치인
새로운
방
정식을
만들
수
있다
.
가우스-조던
방법은
이러한
성질을
사용하여
연립
방정식을
해결한다
.
n원
1차
연립
방정식에
대한
가우스
-조단
방법은
다음과
같다
.
1) 다음과
같은
연립
방정식에서
,
....
....
....
11112211211222221122(1)
(2)
()
nnnnnnnnnnaxaxaxbaxaxaxbnaxaxaxb
Page 23
가우스-조단방법의개념(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 24
가우스-조단방법의개념(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교재p. 107 의수식에는오류가많습니다.
강의TP의내용을참조하시기바랍니다.
Page 25
가우스-조단방법의개념(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 26
가우스-조단방법의예제(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 27
가우스-조단방법의예제(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 28
선형의존과가우스-조단선형의존과가우스-조단
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 29
불일치와가우스-조단불일치와가우스-조단
Gauss-Jordan Algorithm
불일치가
있는
경우
, 가우스-조단
방법에서는
진리
값이
거짓인
명제가
발생한다. ( 불능) (방정식을
확인해
볼
것
)
..
....
..
123123123(1)2+24(2)33
(3)353=8xxxxxxxxx
..
.
1329(1)
710(2)
7(3)5=2xxx
Page 30
부정과가우스-조단부정과가우스-조단
Gauss-Jordan Algorithm
n원
연립
방정식에서
방정식의
개수가
n보다
작으면
, 일반적으로
여러
개
의근
(혹은
무수한
근
)이
존재할
수
있다
. ( 부정)
.
...
...
1212234(1)+ 2(2)3
(3)= 0xxxxxxx
..
.
...
12341(1)
25(2)
25(3)=
2xxxx
Page 31
가우스-조단알고리즘가우스-조단알고리즘
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 32
가우스-조단프로그램(1/3) 가우스-조단프로그램(1/3)
Gauss-Jordan Algorithm
입력을
파일에서
받아들이며
, 각
피봇
주기별로
결과를
출력한다
.
Page 33
가우스-조단프로그램(2/3) 가우스-조단프로그램(2/3)
Gauss-Jordan Algorithm
Page 34
가우스-조단프로그램(3/3) 가우스-조단프로그램(3/3)
Gauss-Jordan Algorithm
Page 35
가우스-조단프로그램실행결과I (1/2) 가우스-조단프로그램실행결과I (1/2)
Gauss-Jordan Algorithm
사용한
연립
방정식
...
...
...
123123123(1) 2411(2) 2523(3) 48xxxxxxxxx
입력
파일
구성
Page 36
가우스-조단프로그램실행결과I (2/2) 가우스-조단프로그램실행결과I (2/2)
Gauss-Jordan Algorithm
Page 37
가우스-조단프로그램실행결과II (1/2) 가우스-조단프로그램실행결과II (1/2)
Gauss-Jordan Algorithm
사용한
연립
방정식
...
....
.....
......
124134123412342 2423246302082525231434xxxxxxxxxxxxxx
입력
파일
구성
Page 38
가우스-조단프로그램실행결과II (2/2) 가우스-조단프로그램실행결과II (2/2)
Gauss-Jordan Algorithm
Page 39
가우스-조단프로그램실행결과III (1/2) 가우스-조단프로그램실행결과III (1/2)
Gauss-Jordan Algorithm
사용한
연립
방정식
.....
....
......
....
.....
12345134523451235123452 37222534563xxxxxxxxxxxxxxxxxxxxxx
입력
파일
구성
Page 40
Algorithm
Page 41
-
가우스-조단프로그램실행결과III (2/2)
We are now … We are now …
Back substitution
선형
연립
방정식의
이해
가우스-조단
알고리즘
역진대입법을이용한가우스소거법
가우스-자이달
알고리즘
Page 42
역진대입법의동기및삼각화개념역진대입법의동기및삼각화개념
Back substitution
가우스-조던의
문제점
: n개의
변수를
갖는
n개의
방정식을
풀고자
할
경
우, 일반적으로
n 2의
연산
(곱셈, 덧셈
등
)이
필요하다
.
삼각화의
의미
: 연립
방정식을
궁극적으로
다음과
같은
삼각형
형태로
나
타내는
방식을
의미한다
.
...
..
.
123233242
=7xxxxxx
역진
대입법
: 삼각화된
연립
방정식을
마지막
방정식에서
시작하여
차례
로
대입하여
모든
변수의
해를
구하는
방식을
의미한다
.
Page 43
역진대입법(Back Substitution) 개념(1/2) 역진대입법(Back Substitution) 개념(1/2)
Back substitution
이
방법은
실제
우리가
“대입법”이라고
알고
있는
방법이다
.
(역진) 대입법을
사용한
연립
방정식
풀이
예제
.....
....
....
....
12341234123412341264022xxxxxxxxxxxxxxxx....12341xxxx
.....
...
...
...
123423423423413385334334xxxxxxxxxxxxx....234338xxx
Page 44
역진대입법(Back Substitution) 개념(2/2) 역진대입법(Back Substitution) 개념(2/2)
Back substitution
.....
...
....
....
1234234343413381212368620xxxxxxxxxxx..343xx
.....
...
....
..
1234234344133812123624xxxxxxxxxx......12341,1,1,2xxxx
Page 45
역진대입법알고리즘및프로그램역진대입법알고리즘및프로그램
Back substitution
가우스-조단
방법을
수정하여
알고리즘
및
프로그램을
만들
수
있다
.
Page 46
오차방정식.동기오차방정식.동기
Back substitution
컴퓨터는
수를
표현하는
한계에
의하여
원하는
정확도의
답을
얻을
수
없
는
경우가
있다
.
즉, 컴퓨터는
실수
연산에
대해
유효숫자
만을
다루기
때문에
, 연산이
누
적될
수록
오차가
커지게
된다
.
컴퓨터에서
오차가
발생하는
실제
예제
Page 47
오차방정식.개념(1/3) 오차방정식.개념(1/3)
Back substitution
오차가
발생한
경우
, 오차들을
위한
방정식을
새롭게
만들어
더욱
정확한
해를
구하는
방식이다
.
다음
연립
방정식
....
....
....
11112211211222221122
nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb
을풀어서나온해가
와같다고하자
.
12(,,,)eeenxxx
그런데, 상기
해는
실제
해가
아니라
오차를
포함할
수
있다
.
Page 48
오차방정식.개념(2/3) 오차방정식.개념(2/3)
Back substitution
오차를
포함한
해
을
원래의
연립
방정식에
대입하면
, 다
음과
같이
새로운
bie 값을
구할
수
있다
.
12(,,,)eeenxxx
11112211211222221122
eeeenneeeenneeeennnnnnaxaxaxbaxaxaxbaxaxaxb
....
....
....
실제해
와오차를포함한해의차이를다음과같이둔다
.
12(,,,)nxxx
......
......
......
111111222222,
,
,
eeeeeennnnnnxxxbbbxxxbbbxxxbbb
Page 49
오차방정식.개념(3/3) 오차방정식.개념(3/3)
Back substitution
원래
방정식에서
새로운
방정식을
빼고
, 이를
.xi를
사용하여
나타낸다
.
........
........
........
11112211211222221122
nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb
상기
새로운
연립
방정식을
풀어서
.xi의
해를
구하고
, 이를
사용하여
실
제해
(실은
오차가
더욱
줄어들어
실제
해에
가까워진
해
)를
구한다
.
...
...
...
111222
eeennnxxxxxxxxx
Page 50
오차방정식.예제(1/3) 오차방정식.예제(1/3)
Back substitution
1) 다음과
같은
연립
방정식이
있다고
하자
.
....
....
....
1231231230.040.011.011.060.020.031.001.010.010.020.010.02xxxxxxxxx
2) 이
방정식의
실제
해는
다음과
같다
.
3) 만일, 컴퓨터가
세
개의
유효
숫자만
다루고
나머지를
버린다면
,
다음과
같이
오차를
포함한
해가
나올
것이다
.
...1231.00, 1.14, 0.996eeexxx
Page 51
오차방정식.예제(2/3) 오차방정식.예제(2/3)
Back substitution
4) 오차를
포함한
해를
원래
방정식에
대입하여
계산한다
.
.......
.......
.......
0.041.000.011.141.010.9961.057360.021.000.031.141.000.9961.01020.011.000.021.140.010.9960.02276
5) 세
개의
숫자만이
유효하므로
, 결과
값을
다음과
같이
구할
수
있다
.
...1231.06, 1.01, 0.0228eeebbb
Page 52
오차방정식.예제(3/3) 오차방정식.예제(3/3)
Back substitution
6) 앞서
방정식
1)에서
5)를
서로
빼서
오차로
구성된
연립
방정식을
만든다
.
.......
........
........
1231231230.040.011.010.002640.020.031.000.0002000.010.020.010.00276xxxxxxxxx
7) 오차로
구성된
방정식을
(컴퓨터로) 풀면
다음
해를
구할
수
있다
.
8) 오차
변수의
해를
원래
방정식에
대입하여
좀
더
나은
해를
구한다
.
....
....
....
1112223331.0281.0840.998eeexxxxxxxxx
Page 53
We are now … We are now …
Gauss-Seidal Algorithm
선형
연립
방정식의
이해
가우스-조단
알고리즘
역진
대입법을
이용한
가우스
소거법
가우스-자이달알고리즘
Page 54
가우스-자이달방법의동기(1/2) 가우스-자이달방법의동기(1/2)
Gauss-Seidal Algorithm
가우스-조단
방법
등은
방정식의
개수가
수십
개인
작은
연립
일차
방정
식에서
상당히
정확한
해를
제공한다
.
반면에, 미지수
(변수)의
개수가
수백
~수천
개
이상인
연립
방정식의
경우
,
1) 산술
연산의
수가
많아
계산
시간이
많이
걸리고
,
2) 개별
연산에서
발생하는
오차가
누적되어
상당히
부정확한
해를
구하게
된다는
결함이
있다
.
Page 55
가우스-자이달방법의동기(2/2) 가우스-자이달방법의동기(2/2)
Gauss-Seidal Algorithm
가우스-자이달
방법과
같은
반복
계산법은
미지수가
많은
연립
방정식의
해를
구하기
위한
방법으로서
,
1) 허용되는
오차를
조절함으로써
산술
연산의
수를
조정할
수
있으며
,
2) 이를
통해
실질적으로는
오차가
적은
해를
빠르게
구할
수
있다
.
반복
계산법의
종류
.
자코비(Jacobi) 반복
계산법
.
가우스-자이달
반복
계산법
.
SOR(Successive OverRelaxation) 법
Page 56
가우스-자이달방법의직관적설명가우스-자이달방법의직관적설명
Gauss-Seidal Algorithm
지금까지의
방법은
분석적
방법을
컴퓨터에
적용한
것이라
할
수
있다
.
반면에, 가우스-자이달
방법은
수치해석적
방법이다
. 즉,
1) 해를
계산
초기에
임의로
가정하고
,
2) 다음
단계에서
이전
해를
사용하여
더
나은
해를
구성하고
,
3) 상기
2)의
과정을
반복하여
원하는
수준의
해를
찾아낸다
.
가우스-자이달
방법은
반복을
통하여
해를
구해내므로
, 반복
계산법
(iteration method) 에
해당한다
.
Page 57
가우스-자이달방법의예제(1/2) 가우스-자이달방법의예제(1/2)
Gauss-Seidal Algorithm
다음
연립
방정식을
가우스
-자이달
방법으로
해결한다
.
...
....
.....
123123123423.0240.3240.8xxxxxxxxx
초기값을
할당한다
.
(당연한
이야기지만
, 초기값이
해에
가까울
수록
방정식이
빨리
풀린다
.)
첫
번째
방정식에서
첫
번째
변수를
제외한
다른
변수에
현재
해를
대입하
여
첫
번째
변수의
값을
구한다
.
.............(1)(0)(0)
123113231211.544xxx
Page 58
가우스-자이달방법의예제(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 59
가우스-자이달방법의계산식가우스-자이달방법의계산식
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 60
가우스-자이달알고리즘가우스-자이달알고리즘
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 61
가우스-자이달프로그램(1/4) 가우스-자이달프로그램(1/4)
Gauss-Seidal Algorithm
Page 62
가우스-자이달프로그램(2/4) 가우스-자이달프로그램(2/4)
Gauss-Seidal Algorithm
.
.
...
..
......
..
..
..
1()()(1)
111:;
inpppijijiijjiijjixaxaxba
Page 63
가우스-자이달프로그램(3/4) 가우스-자이달프로그램(3/4)
Gauss-Seidal Algorithm
Page 64
가우스-자이달프로그램(4/4) 가우스-자이달프로그램(4/4)
Gauss-Seidal Algorithm
.
.
.
.
.()(1)
1;
nppiiixxen
Page 65
가우스-자이달프로그램실행결과I(1/2) 가우스-자이달프로그램실행결과I(1/2)
Gauss-Seidal Algorithm
사용한
연립
방정식
...
....
.....
1231231234 23240.3240.8xxxxxxxxx
초기
해
입력
파일
구성
Page 66
가우스-자이달프로그램실행결과I(2/2) 가우스-자이달프로그램실행결과I(2/2)
Gauss-Seidal Algorithm
Page 67
가우스-자이달프로그램실행결과II(1/2) 가우스-자이달프로그램실행결과II(1/2)
Gauss-Seidal Algorithm
사용한
연립
방정식
초기
해
...
.....
.....
...
1231234123423410 2611325210113815xxxxxxxxxxxxxx
입력
파일
구성
Page 68
가우스-자이달프로그램실행결과II(2/2) 가우스-자이달프로그램실행결과II(2/2)
Gauss-Seidal Algorithm
가우스-자이달
알고리즘의
경우
, 방정식의
종류
, 초기
해의
값에
따라서
발산하는
경우가
많이
발생한다
. 또한, 현재는
컴퓨터
성능의
획기적
개선으로
인하여
,가우
스-자이달
방법보다는
정확한
해를
구하는
가우스
-조던
방법이
더욱
바람직하다
.
Page 69