제 3장. 연립 방정식의 해법 행렬과 방정식의 행렬 표현 소거법 행렬식과 역 행렬 노름과 조건수 반복법

Presentation on theme: "제 3장. 연립 방정식의 해법 행렬과 방정식의 행렬 표현 소거법 행렬식과 역 행렬 노름과 조건수 반복법"— Presentation transcript:

1 제 3장. 연립 방정식의 해법 행렬과 방정식의 행렬 표현 소거법 행렬식과 역 행렬 노름과 조건수 반복법
비선형 연립 방정식의 해법

2 1. 행렬과 방정식의 표현 연립 방정식을 동시에 만족하는 값 x1, x2,..,xn을 구하는 문제를 다룬다.
연립 방정식의 종류 선형 연립 방정식 비 선형 연립 방정식

3 1. 행렬과 방정식의 표현(cont.) 행렬의 종류(교재 P.80~83참조)
행렬(행의 수 n, 열의 수 m, n  m), 정방 행렬 (n  n) 행 벡터(n = 1), 열 벡터(m = 1) 대각 행렬 단위 행렬 전치 행렬(AT), 대칭 행렬(AT =A) 삼각 행렬 ; 상삼각, 하삼각 교대 행렬(AT = -A) 트레이스

4 1. 행렬과 방정식의 표현(cont.) 행렬의 기본 연산 법칙 행렬의 상등 행렬의 합과 차 행렬의 곱
3중 대각 행렬과 역 행렬(교재 p.85참조)

5 1. 행렬과 방정식의 표현(cont.) 연립 방정식의 행렬 표현

6 2. 소거법 방정식을 결합하여 미지수를 소거한다. 선형 연립 방정식의 해를 구하는 방법 비선형 연립 방정식의 해법
행렬식과 Cramer 공식 미지수 소거법 Gauss 소거법 Gauss-Jordan 소거법 LU 분해법과 역 행렬 특수 행렬과 반복법 비선형 연립 방정식의 해법

7 2. 소거법(cont.) 주요 용어 : 선형 연립방정식의 연산 법칙 :
피벗 원소 (pivot element) : 소거시키는 기준이 되는 대각선의 원소. 피벗 행(pivot row) : 피벗 원소가 속해있는 행. 선형 연립방정식의 연산 법칙 : 확대 행렬의 어떤 행에도 상수를 곱할 수 있다. 하나의 행에 어떤 수를 곱하여 , 다른 행에 더할 수 있다. 어떤 두 행의 위치를 바꿀 수 있다.

8 2.1 Gauss 소거법 전진 소거와 후진 대입 기법을 사용 연립 방정식이 커지면, 계산시간이 3배로 증가
계수 행렬을 상 삼각 행렬로 변환하여, 역 대입 연립 방정식이 커지면, 계산시간이 3배로 증가 대부분의 노력은 소거 단계에 있다 소거법의 문제점 0으로 나누는 경우  피벗화 반올림 오차  더 많은 유효숫자 사용 불량 조건 시스템

9 2.1 Gauss 소거법(cont.) 1. 행렬의 표현 2. 확대 행렬 A|B 생성

10 2.1 Gauss 소거법(cont.) 3. 전진 소거하여 상 삼각 행렬로 만든다.
3R2+(-1)R1R2 7R3+4R2R3 4. 제일 먼저 x3를 구하고, x2, x1을 차례로 전진 대입

11 2.1 Gauss 소거법(cont.) 문제점 소거와 후진 대입하는 동안 0으로 나누어지는 경우와 계수가 0에 매우 근접해 있을 경우가 발생. 피벗화로 부분적으로 해결 완전 피벗화 : 계수 행렬 중 절대 값이 제일 큰 요소를 찾아 피벗 원소로 택하는 방법. 바뀐 열이 x의 차수를 변화 시키기 때문에 프로그램을 복잡하게 만들게 되므로 잘 사용되지 않는다. 부분 피벗화 : 한 개의 열 내에서만 제일 큰 원소를 찾아 피벗 원소로 택하는 방법.

12 2.2 Gauss-Jordan 소거법 미지수를 소거할 때 다른 모든 방정식에서 소거하고, 모든 행들은 피벗 요소로 나누어 정규화 된다. 소거한 후에는 단위 행렬이 되므로 후진 대입할 필요가 없다. Gauss 소거법 보다 약 50% 더 연산 작업을 수행해야 하므로, Gauss 소거법이 선형 연립 방정식의 해를 얻기 위해 선호되는 방법이다.

13 2.2 Gauss-Jordan 소거법(cont.)
3R2+(-1)R1R2 3R2+(-2)R1R3

14 2.3 LU 분해법 AX = B에서 우변 B를 소거에 포함시키지 않는다 0으로 나누는 것을 피하기 위하여 피벗화 요구
해를 구하기 위한 두 단계 LU 분해 단계 : AX = B  LUX = B (L은 하삼각 행렬, U는 상삼각행렬) 대입 단계 : LD = B를 사용하여, 전진 대입으로 D를 구한다 UX = D를 이용하여 후진 대입으로 X를 구한다

15 2.3 LU 분해법 (cont.) Crout 분해법 Cholesky 분해법 Doolittle 분해법
l11= u11, l22 = u22 , …, lnn = unn Doolittle 분해법 대각 요소가 1인 행렬 L를 사용

16 2.3.1 Crout 분해 행렬을 행과 열에 따라 쓰면서 L과 U를 만든다

17 2.3.1 Crout 분해(cont.) 1열의 비교 2열의 비교 1행의 비교

18 2.3.1 Crout 분해(cont.) 3열,4열의 비교

19 2.3.1 Crout 분해(cont.) 정리된 일반식 특히,

20 2.3.2 예제 예제 3.5 : 교재 p.105 LU 분해법 알고리즘 : 교재 p.106 LU 분해법을 사용한 역행렬 구하기

21 3. 행렬식과 역 행렬 행렬식 Cramer공식을 수행하거나, 행렬의 불량 조건을 평가하는데 사용된다.
행렬과 달리 행렬식은 하나의 수치 값이다.

22 3. 행렬식과 역 행렬(cont.) Cramer 공식 방정식의 수가 적을 때 사용할 수 있는 기법
각 미지수를 두개의 행렬식을 사용해서 분수 형태로 표현한다. 여기서 분모는 행렬식 D이고, 분자는 D의 요소 중에서 미지수를 갖는 계수의 열 위치에 상수 b1, b2, …, bn으로 대체하여 얻은 행렬식

23 3. 행렬식과 역 행렬(cont.) Cramer 공식(cont.) AX = B로 부터 직접 x를 구하는 방법이다.
예를 들어, i = 1이면

24 3. 행렬식과 역 행렬(cont.) 역 행렬 역 행렬 구하기 행렬 A가 정방 행렬이면, A의 역 행렬인 A-1 이 존재한다.
A A-1 = I 역 행렬 구하기 행렬 A와 단위 행렬 I를 확대 행렬로 만들고, Gauss-Jordan의 방법을 적용하여 A 의 자리가 단위 행렬이 되도록 하면 I 의 자리에서 변화된 값이 역 행렬이 된다

25 3. 행렬식과 역 행렬(cont.)

26 4. 크기(norm)와 조건수 노름 혹은 크기(norm)은 벡터와 행렬과 같은 다중 성분 수학적 개체의 길이 또는 크기의 척도를 제공하는 값이다. x z y a b c

27 4. 크기와 조건수 (cont.) Norm : (p.116 참조) Euclidian norm :
열 norm(1-norm) : 각 열 원소의 절대값을 합한 것 중에 최대값 행 norm(-norm) : 각 행 원소의 절대값을 합한 것 중 최대값

28 4. 크기와 조건수 (cont.) Norm의 특성 : (p.115 참조) ||A|| 0 , 단 A=0인 경우에 ||A||=0
||kA|| = k ||A|| , 단 k는 임의의 상수 ||A+B||  ||A|| + ||B|| ||AB||  ||A|| ||B||

29 4. 크기와 조건수(cont.) 크기를 사용하여 조건수를 정의할 수 있다. Cond[A] =
행렬 조건수를 사용한 크기의 오차에 관한 식

30 4. 크기와 조건수(cont.) 불량 조건을 갖는 대표적 예 : Hilbert 행렬 33 Hilbert 행렬의 경우 :

31 4.1 반복적인 정제 연립 방정식이 불량 조건일 경우 직접법을 사용하여 구해진 해 X(0) 는 오차가 크다.
이런 경우, 직접법을 반복적으로 적용해서 참값에 가까운 해를 구할 수 있다. 연립 방정식 AX = B에서 직접법으로 구한 근사해 X(0)를 대입하면, AX(0) = B(0) 가 된다.

32 4.1 반복적인 정제(cont.) p.120 : 예제

33 5. 특수 행렬과 반복법 계수 행렬이 0을 많이 포함한 경우에 소거법 보다 빨리 근을 구할 수 있는 방법.
초기 가정 값을 선정하여 정제된 추정 해를 얻기 위하여 반복. 큰 연립 방정식에 적합하고, 오차는 반복 횟수로 조정할 수 있음. Jacobi 반복법 Gauss-Seidel 반복법 이완법

34 5.1 Jacobi 반복법 계수가 제일 큰 미지수가 좌변에 오도록 각 식을 정리하여 반복식의 형태로 만든다.
시작점을 x1 = x2 = x3 = 0을 취해서 반복식에 대입하여 새로운 x1 , x2 , x3 값을 얻고, 이 과정을 반복한다.

35 5.2 Gauss-Seidel 반복법 Jacobi 반복법 보다 수렴 속도가 훨씬 빠르고, 새로운 x값이 즉시 사용됨.
만약 해가 수렴하고 있다면 가장 유효한 추정 값을 채택할 수 있기 때문에 선호하는 방법. 참값에 충분히 가깝게 수렴할 때까지 반복. 종료 판정 기준 :

36 *반복법의 비교 Gauss-Seidel 반복법 Jacobi 반복법

37 5.3 이완법 Gauss-Seidel 법에서 수렴을 향상 시키기 위하여 약간의 변형을 한 방법이다.
각각의 새로운 x값을 구한 후에 x 값은 이전과 현재의 반복으로 구한 결과의 가중 평균으로 수정된다. 이것을 이완이라고 한다.

38 5.3 이완법(cont.) 이완과정을 반복하여 잔차가 모두 0이 되는 시점에서 계산을 중지하게 되고, x 의 시작 값과 이완에 의해 증감된 값을 모두 더하면 해를 구할 수 있다. 수렴 속도는 매우 빠르지만, 프로그램이 어렵다.

39 5.3 이완법(cont.)

40 5.3 이완법(cont.)

41 5.3 이완법(cont.)

42 5.3 이완법(cont.)

43 6. 비선형 연립 방정식의 해법 대수 및 초월 함수를 포함한 비선형 연립 방정식의 해를 구하는 것은 어렵다.
비선형 방정식을 풀기위한 개 구간법을 확장하면, 이들 연립 방정식의 해를 구할 수 있다. 비선형 연립 방정식의 해법 1차 반복법(고정점 반복법) Newton-Raphson법

44 6.1 고정점 반복법 수렴 조건을 만족하는 반복식을 구하여, 초기 가정 값을 대입한다. 수렴조건 :
수렴조건이 너무나 엄격하기 때문에 고정점 반복법은 실제로 거의 사용되지 않는다.

45 6.2 Newton-Raphson 방법 주어진 한 쌍의 연립 방정식을 (x0, y0)를 기준으로 하여 Taylor급수 전개하여 제 1차 미분계수를 포함하는 항을 취한다. h와 k는 Cramer 공식을 사용하여 구할 수 있다.

46 * 편미분의 계산 x가 극히 작다고 생각하여, 근사값으로 표현하면,