수치해석 (Numerical Analysis)

Presentation on theme: "수치해석 (Numerical Analysis)"— Presentation transcript:

1 수치해석 (Numerical Analysis)
고유치 (Eigenvalues)

2 In this chapter … 고유치(Eigenvalues) 본 장에서는 행렬의 중요한 성질인 고유치(eigenvalues)와 고유 벡터(eigenvectors)에 대해서, 1) 고유치와 고유 벡터의 정의 및 이를 구하는 방법을 배우고, 2) 행렬의 특성 방정식과 이를 이용한 케일리-해밀턴 정리를 알아보며, 3) 파데브-레브리어 알고리즘과 이를 활용하는 방법을 익힌다..

3 We are now … 고유치와 고유 벡터 케일리-해밀턴 정리 파데브-레브리어 알고리즘
Eigenvalues & Eigenvectors 고유치와 고유 벡터 케일리-해밀턴 정리 파데브-레브리어 알고리즘

4 대각 행렬로의 변환 (1/6) Eigenvalues & Eigenvectors 선형 연립 방정식 Ax = b에서, 어떤 정칙 행렬 P가 있어서, 그 행렬이 다음 관계를 만족한다고 하자. 행렬 P를 사용하여 연립 방정식 Ax = b를 정리하면 다음과 같다. 결국, 원래 연립 방정식은 다음 형태로 정리될 수 있다.

5 대각 행렬로의 변환 (2/6) 여기에서, 행렬 가 다음과 같은 대각 행렬의 성질을 만족시킨다고 하자.
Eigenvalues & Eigenvectors 여기에서, 행렬 가 다음과 같은 대각 행렬의 성질을 만족시킨다고 하자. 이와 같은 성질(행렬 가 대각 행렬인 성질)을 만족시키는 행렬 P를 모우들 행렬(modal matrix)이라 하고, 이때 만들어진 대각 행렬 를 스펙트럼 행렬(spectrum matrix)라 한다.

6 대각 행렬로의 변환 (3/6) Eigenvalues & Eigenvectors 상기 식  = P-1AP의 행렬 P를 n개의 n차원 벡터 p1, …, pn으로 표현하면 다음과 같다.

7 대각 행렬로의 변환 (4/6) 결국, 원래 연립 방정식은 다음 형태로 정리될 수 있다.
Eigenvalues & Eigenvectors 결국, 원래 연립 방정식은 다음 형태로 정리될 수 있다. 그 이유는, AP = P가 다음과 다음과 같이 나타나기 때문이다.

8 대각 행렬로의 변환 (5/6) 지금부터는 편의상 pi를 p로, i를 로 나타내기로 한다.
Eigenvalues & Eigenvectors 지금부터는 편의상 pi를 p로, i를 로 나타내기로 한다. Ap = p를 다시 정리하면, 다음과 같다(다음에서, 0는 n차원 벡터이다). 그런데, 여기에서 p는 0가 아니므로, (I – A) = 0가 되어야 한다.  즉, (I – A)가 특이 행렬(singular)이 되어야 하고,  따라서, 그 행렬식은 0이 되어야 한다(다음 식이 성립하여야 한다).

9 대각 행렬로의 변환 (6/6) Eigenvalues & Eigenvectors 그리고, |I – A|는 다음과 같이 에 대한 n차 방정식이 되며, 이 방정식을 행렬 A의 특성 방정식(characteristic equation)이라 한다. 그 이유는 왼편과 같은 과정으로 행렬식이 구해지기 때문이다.

10 고유치의 정의 Eigenvalues & Eigenvectors 정의: 행렬 A의 특성 방정식의 근(해)을 행렬 A의 고유치(eigenvalues)라 정의한다. 즉, 특성 방정식을 아래와 같이 나타냈을 때, 1, 2, …, n을 행렬 A의 고유치라 한다. 정리: 행렬 A의 고유치는 행렬 A의 대각 행렬인 의 대각 원소이다. 즉, 행렬 A의 고유치를 1, 2, …, n이라 하면, 다음이 성립한다.

11 고유치를 구하는 예제 (1/2) 예제) 다음 행렬 A의 고유치를 구하라. 행렬 A의 특성 방정식을 구한다.
Eigenvalues & Eigenvectors 예제) 다음 행렬 A의 고유치를 구하라. 행렬 A의 특성 방정식을 구한다.

12 고유치를 구하는 예제 (2/2) 다음 과정에 의해서 행렬 A의 특성 방정식을 계산할 수 있다.
Eigenvalues & Eigenvectors 다음 과정에 의해서 행렬 A의 특성 방정식을 계산할 수 있다. 결국, 행렬 A의 고유치는 다음과 같다.

13 고유치의 성질 Eigenvalues & Eigenvectors 행렬 A의 고유치가 0가 되기 위한 필요충분조건은 A가 (정칙 행렬이 아닌) 특이 행렬(singular matrix)인 것이다. 임의의 실수 k에 대해, 행렬 kA의 고유치는 원래 행렬 A의 고유치의 k배에 해당하는 값이다. 행렬 A와 이의 전치(transpose) 행렬 AT의 고유치는 동일하다. 행렬 A의 역행렬 A-1의 고유치는 A의 고유치의 역수와 같다. 행렬 Ak의 고유치는 A의 고유치의 k 제곱과 같다. 대각 행렬의 고유치는 그 대각 원소들이다. 행렬 A의 고유치들의 합은 trace(A)가 된다. 행렬 A의 고유치들의 곱은 행렬 A의 행렬식이 된다.

14 고유 벡터의 정의 Eigenvalues & Eigenvectors 정의: 행렬 A에 대한 n개의 고유치(1, 2, …, n)에 대해서 각기 다음 식을 만족하는 벡터 pi(p1, p2, …, pn)를 행렬 A의 고유 벡터라 정의한다. (하기 식은 앞서 고유치를 유도하는 과정에서 얻은 식과 동일함)

15 고유 벡터를 구하는 예제 (1/2) 다음 행렬에 대한 고유 벡터를 구하라.
Eigenvalues & Eigenvectors 다음 행렬에 대한 고유 벡터를 구하라. 앞서 행렬 A의 고유치를 1=1, 2=-2, 3=3으로 구했으므로, 우선 고유치 1에 대해서 식을 전개하면 다음과 같다.

16 고유 벡터를 구하는 예제 (2/2) Eigenvalues & Eigenvectors 그런데, 세 번째 식이 첫 번째와 두 번째 식에 선형 의존이다. 따라서, 다음 두 식으로 나타낼 수 있다. 상기 두 식을 만족하는 p1i은 무수히 많으므로, 임의로 p11 = 2로 두면, 왼편과 같은 고유 벡터를 얻을 수 있다. 마찬가지 방법으로, 다른 고유치에 대해서도 같은 방식을 적용하면, 다음과 같이 고유 벡터를 얻을 수 있다.

17 고유 벡터의 성질 임의의 실수 k에 대해서, 행렬 kA의 고유 벡터들은 행렬 A의 고유 벡터와 동일하다.
Eigenvalues & Eigenvectors 임의의 실수 k에 대해서, 행렬 kA의 고유 벡터들은 행렬 A의 고유 벡터와 동일하다. 행렬 A-1의 고유 벡터들은 행렬 A의 고유 벡터들과 같다. 서로 다른 고유치에 해당하는 고유 벡터들은 서로 선형 독립이다. (i.e., pi  kpj if i  j) 실수를 원소로 하는 행렬 A의 고유 벡터들 중에 복소수가 있으면, 그들은 서로 켤레 복소수의 관계를 가진다.

18 닮은 변환 (Similarity Transformation) (1/2)
Eigenvalues & Eigenvectors (앞서 살펴본 바와 같이) 행렬 A와 이의 스펙트럼 행렬 는 다음 관계가 성립한다. 상기와 같은 관계가 성립할 때, 행렬 A와 는 닮았다(similar)고 한다. 정의: 행렬 A와 B 사이에 모으들 행렬 P가 존재하여 B=P-1AP의 관계를 만족하면 행렬 A와 B는 닮았다(similar)고 정의한다.

19 닮은 변환 (Similarity Transformation) (2/2)
Eigenvalues & Eigenvectors 만일, 행렬 A와 B가 서로 닮았다고 하면, 다음 관계들이 성립한다. 1. P-1(A2)P = B2 2. P-1(An)P = Bn 3. P-1(A-1)P = B-1 4. trace(B) = trace(A) 5. |B| = |A| 6. 행렬 B의 고유치는 행렬 A의 고유치와 동일하다.

20 고유 벡터의 계산 - 개념 Eigenvalues & Eigenvectors (앞서 언급한 바와 같이) 행렬 A가 nxn 행렬인 경우, 미지수 n개의 선형 연립 방정식을 풀면 고유 벡터를 계산할 수 있다. 선형 연립 방정식은 가우스-조던 방식 등을 사용하여 풀 수 있다. 그런데, 몇몇 경우에는 선형 의존 관계에 의하여, 임의의 값을 대입한 후 고유 벡터를 계산해야 한다.  다음의 예제 참조

21 고유 벡터의 계산 – 예제 I (1/2) 다음 행렬 A에 대해서 고유치를 계산하라.
Eigenvalues & Eigenvectors 다음 행렬 A에 대해서 고유치를 계산하라. 앞서 행렬 A의 고유치를 1=1, 2=-2, 3=3으로 구했다. 이번에는 고유치 -2에 대해서 식을 전개하면 다음과 같다.

22 고유 벡터의 계산 – 예제 I (2/2) 가우스-조단 방식을 사용하면, 다음 식을 얻을 수 있다.
Eigenvalues & Eigenvectors 가우스-조단 방식을 사용하면, 다음 식을 얻을 수 있다. p22에 1을 대입하여 나머지 값을 구하면 다음과 같이 고유 벡터를 구할 수 있다.

23 고유 벡터의 계산 – 예제 II (1/2) (중근 예제 1) 다음 행렬 A에 대해서 고유치를 계산하라.
Eigenvalues & Eigenvectors (중근 예제 1) 다음 행렬 A에 대해서 고유치를 계산하라. 행렬 A의 특성 방정식을 구하여 풀면 다음과 같다. 중근인 고유치(-3)에 대해서 고유 벡터를 구하는 방정식은 다음과 같다.

24 고유 벡터의 계산 – 예제 II (2/2) 가우스-조단 방식을 사용하여 방정식을 풀면 다음과 같다.
Eigenvalues & Eigenvectors 가우스-조단 방식을 사용하여 방정식을 풀면 다음과 같다. 이 경우, (중근임에도 불구하고) 서로 독립인 고유 벡터는 하나만 나온다. 예를 들어, p13=1이라 하면, p11=0.167, p12=0.833이 된다.)  결국, 이 경우는 고유 벡터를 (세 개가 아닌) 두 개밖에 구할 수 없으므로,정칙 행렬(nonsingular matrix)인 모우들 행렬 P를 구할 수 없다

25 고유 벡터의 계산 – 예제 III (1/3) (중근 예제 2) 다음 행렬 A에 대해서 고유치를 계산하라.
Eigenvalues & Eigenvectors (중근 예제 2) 다음 행렬 A에 대해서 고유치를 계산하라. 행렬 A의 특성 방정식을 구하여 풀면 다음과 같다. 중근인 고유치(2)에 대해서 고유 벡터를 구하는 방정식은 다음과 같다.

26 고유 벡터의 계산 – 예제 III (2/3) 가우스-조단 방식을 사용하여 방정식을 풀면 다음과 같다.
Eigenvalues & Eigenvectors 가우스-조단 방식을 사용하여 방정식을 풀면 다음과 같다. 이 경우, 첫 번째 식을 만족하는 여러 개의 고유 벡터를 구할 수 있다. 이 중에서 두 개의 고유 벡터를 구하면 다음과 같다.

27 고유 벡터의 계산 – 예제 III (3/3) 나머지 고유치(1)에 대해서 고유 벡터를 구하면 다음과 같다.
Eigenvalues & Eigenvectors 나머지 고유치(1)에 대해서 고유 벡터를 구하면 다음과 같다. 결국, 다음과 같이 행렬 A의 모우들 행렬을 구할 수 있다. 그리고, 이때의 스펙트럼 행렬 는 다음과 같다.

28 고유 벡터의 계산 – 예제 IV (1/3) (해가 복소수인 경우) 다음 행렬 A에 대해서 고유치를 계산하라.
Eigenvalues & Eigenvectors (해가 복소수인 경우) 다음 행렬 A에 대해서 고유치를 계산하라. 행렬 A의 특성 방정식을 구하여 풀면 다음과 같다. 첫 번째 고유치(-1+2i)에 대한 고유 벡터를 구하는 방정식은 다음과 같다.

29 고유 벡터의 계산 – 예제 IV (2/3) 실수부와 허수부로 나누어 정리하면 다음과 같다.
Eigenvalues & Eigenvectors 실수부와 허수부로 나누어 정리하면 다음과 같다. 가우스-조던 방식을 이용하여 방정식을 풀면 다음과 같다.

30 고유 벡터의 계산 – 예제 IV (3/3) 다음과 같이 두 미지수를 왼편과 같이 임의의 값으로 정해 준다.
Eigenvalues & Eigenvectors 다음과 같이 두 미지수를 왼편과 같이 임의의 값으로 정해 준다. 나머지 값들에 대해서 풀면, 왼편과 같다. 결국, 첫 번째 고유 벡터는 왼편과 같다. 두 번째 고유 벡터는 첫 번째의 켤례 복소수에 해당하므로, 왼편과 같이 구할 수 있다.

31 We are now … 고유치와 고유 벡터 케일리-해밀턴 정리 파데브-레브리어 알고리즘
Cayley-Hamilton Theorem 고유치와 고유 벡터 케일리-해밀턴 정리 파데브-레브리어 알고리즘

32 행렬의 제곱승에 대한 정의 Cayley-Hamilton Theorem

33 케일리-해밀턴의 정리 케일리-해밀턴의 정리: 임의의 정방 행렬 A의 특성 방정식이 다음과 같이 주어진다면,
Cayley-Hamilton Theorem 케일리-해밀턴의 정리: 임의의 정방 행렬 A의 특성 방정식이 다음과 같이 주어진다면, 다음과 같이 행렬 A에 대한 방정식이 성립한다. (  A) 케일리-해밀턴의 정리에 따르면, 정방 행렬의 고차 제곱들은 그 이하 차수를 가지는 제곱들의 선형 조합으로 나타낼 수 있다.

34 케일리-해밀턴 정리의 예제 (1/2) 정방 행렬 A가 다음과 같이 주어졌다고 하자. 행렬의 특성 방정식을 구하면 다음과 같다.
Cayley-Hamilton Theorem 정방 행렬 A가 다음과 같이 주어졌다고 하자. 행렬의 특성 방정식을 구하면 다음과 같다. 케일리-해밀턴 정리를 사용하면 다음의 행렬 방정식을 구할 수 있다.

35 케일리-해밀턴 정리의 예제 (2/2) Cayley-Hamilton Theorem 계속 적용해 보면, An(n  3)은 A2 이하 차수를 가지는 항들의 선형 조합으로 나타낼 수 있다.

36 역행렬 구하기 케일리-해밀턴 방정식의 양변에 A의 역행렬을 곱해 전개한다. 결국, A의 역행렬은 다음과 같이 구할 수 있다.
Cayley-Hamilton Theorem 케일리-해밀턴 방정식의 양변에 A의 역행렬을 곱해 전개한다. 결국, A의 역행렬은 다음과 같이 구할 수 있다.

37 We are now … 고유치와 고유 벡터 케일리-해밀턴 정리 파데브-레브리어 알고리즘
Faddeev-Leverrier Algorithm 고유치와 고유 벡터 케일리-해밀턴 정리 파데브-레브리어 알고리즘

38 파데브-레브리어 알고리즘 개요 (1/3) Faddeev-Leverrier Algorithm 파데브-레브리어 알고리즘은 특성 방정식의 계수인 i를 구할 수 있는 효율적인 알고리즘이다. 또한, 이를 사용하면 행렬의 역행렬을 손쉽게 구할 수 있다. 행렬 A의 특성 방정식이 다음과 같이 주어진다고 가정하자. 즉, 행렬 A에 대해 다음의 방정식이 성립한다.

39 파데브-레브리어 알고리즘 개요 (2/3) 그러면, 다음의 파데브-레브리어 방법에 의해 특성 방정식의 계수 들을 구할 수 있다.
Faddeev-Leverrier Algorithm 그러면, 다음의 파데브-레브리어 방법에 의해 특성 방정식의 계수 들을 구할 수 있다.

40 파데브-레브리어 알고리즘 개요 (3/3) 덧붙여, 행렬 A의 역행렬을 다음과 같이 구할 수 있다.
Faddeev-Leverrier Algorithm 덧붙여, 행렬 A의 역행렬을 다음과 같이 구할 수 있다. 파데브-레브리어 알고리즘의 자세한 증명 과정은 다음을 참조한다. Faddeeva, V. N., “Computation Methods of Linear Algebra,” (translated from the Russian by Benster, C. D.), Dover Publications Inc., N.Y., 1959.

41 특성 방정식 구하기 - 알고리즘 procedure char_eq(aij: real numbers, n: integer)
Faddeev-Leverrier Algorithm procedure char_eq(aij: real numbers, n: integer) { [aij] is an nxn matrix. (1  i,j  n)} { n is # of columns(= # of rows).} [bij] := [aij]; n1 := trace([bij]); for k := 2 to n begin [bij] := [aij]([bij] + nk+1[iij]); nk := (1/k)trace([bij]); end return k for every k in between 1 and n;

42 특성 방정식 구하기 – 프로그램 (1/4) Faddeev-Leverrier Algorithm

43 특성 방정식 구하기 – 프로그램 (2/4) Faddeev-Leverrier Algorithm

44 특성 방정식 구하기 – 프로그램 (3/4) Faddeev-Leverrier Algorithm

45 특성 방정식 구하기 – 프로그램 (4/4) Faddeev-Leverrier Algorithm

46 특성 방정식 구하기 – 실행 결과 I (1/2) Faddeev-Leverrier Algorithm 사용한 행렬 입력 파일 구성

47 특성 방정식 구하기 – 실행 결과 I (2/2) 실행 결과 구해진 특성 방정식
Faddeev-Leverrier Algorithm 실행 결과 구해진 특성 방정식

48 특성 방정식 구하기 – 실행 결과 II (1/2) 사용한 행렬 (교재에서 사용한 행렬) 입력 파일 구성
Faddeev-Leverrier Algorithm 사용한 행렬 (교재에서 사용한 행렬) 입력 파일 구성

49 특성 방정식 구하기 – 실행 결과 II (2/2) 실행 결과 구해진 특성 방정식
Faddeev-Leverrier Algorithm 실행 결과 구해진 특성 방정식

50 특성 방정식 구하기 – 실행 결과 III (1/2) 사용한 행렬 (4 x 4 행렬) 입력 파일 구성
Faddeev-Leverrier Algorithm 사용한 행렬 (4 x 4 행렬) 입력 파일 구성

51 특성 방정식 구하기 – 실행 결과 III (2/2) 실행 결과 구해진 특성 방정식
Faddeev-Leverrier Algorithm 실행 결과 구해진 특성 방정식

52 역행렬 구하기 - 알고리즘 procedure char_inv(aij: real numbers, n: integer)
Faddeev-Leverrier Algorithm procedure char_inv(aij: real numbers, n: integer) { [aij] is an nxn matrix. (1  i,j  n)} { n is # of columns(= # of rows).} [bij] := [aij]; n1 := trace([bij]); for k := 2 to n begin [bij] := [aij]([bij] + nk+1[iij]); nk := (1/k)trace([bij]); if k = n1 then [cij] = [bij]; end [rij] := (1/0)([cij]+1[iij]); return [rij];

53 역행렬 구하기 – 프로그램 (1/5) Faddeev-Leverrier Algorithm

54 역행렬 구하기 – 프로그램 (2/5) Faddeev-Leverrier Algorithm

55 역행렬 구하기 – 프로그램 (3/5) Faddeev-Leverrier Algorithm

56 역행렬 구하기 – 프로그램 (4/5) Faddeev-Leverrier Algorithm

57 역행렬 구하기 – 프로그램 (5/5) Faddeev-Leverrier Algorithm

58 역행렬 구하기 – 실행 결과 I (1/2) Faddeev-Leverrier Algorithm 사용한 행렬 입력 파일 구성

59 역행렬 구하기 – 실행 결과 I (2/2) Faddeev-Leverrier Algorithm 실행 결과

60 역행렬 구하기 – 실행 결과 II (1/2) 사용한 행렬 (교재에서 사용한 행렬) 입력 파일 구성
Faddeev-Leverrier Algorithm 사용한 행렬 (교재에서 사용한 행렬) 입력 파일 구성

61 역행렬 구하기 – 실행 결과 II (2/2) Faddeev-Leverrier Algorithm 실행 결과

62 역행렬 구하기 – 실행 결과 III (1/2) 사용한 행렬 (4 x 4 행렬) 입력 파일 구성
Faddeev-Leverrier Algorithm 사용한 행렬 (4 x 4 행렬) 입력 파일 구성

63 역행렬 구하기 – 실행 결과 III (2/2) Faddeev-Leverrier Algorithm 실행 결과