수치해석(Numerical Analysis) 선형연립방정식수치해석(Numerical Analysis) 선형연립방정식

수치해석(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