읽기일기

선형대수 (7)


선형대수, George Nakos 지음, 김철언 외 옮김/인터비젼

7. 고유값과 고유벡터

7.1 고유값과 고유벡터

A가 n * n 행렬일 때, n-벡터 v는 A와는 별다른 관계가 없으나, Av가 v에 비례(평행)할 때의 특이한 경우가 있다. 이러한 경우 기하학적으로 v와 Av는 원점을 지나는 같은 직선 위에 있다. 그러한 경우, v를 A의 고유벡터(eigenvector)라 하고 비례상수를 A의 고유값(eigenvalue)라고 한다.

정의

A를 n * n 행렬이라고 하자. 영 아닌 벡터 v가 A의 고유벡터라는 것은 $ Av = \lambda v $를 만족하는 스칼라 $ \lambda $ 가 존재할 때이다. 고유벡터 $v$에 대응하는 스칼라 $ \lambda $를 A의 고유값이라고 한다.

고유벡터의 영 아닌 스칼라 배 또한 고유벡터이다. 이 때, 고유값은 같다.

고유값과 고유벡터의 계산

정리 1

A를 정사각행렬이라고 하자.

  1. 스칼라 $ \lambda $가 A의 고유값이다. $ \Leftrightarrow \det(A- \lambda I) = 0 $
  2. 벡터 v가 고유값 $ \lambda $에 대응하는 고유벡터이다. $ \Leftrightarrow $ v는 연립방정식 $ (A- \lambda I) v = 0 $의 비자명해이다.
  • $ \det(A- \lambda I) = 0 $ : 특성방정식
  • $ \det(A- \lambda I) $ : 차수가 n인 $ \lambda $의 특성다항식
  • $ A - \lambda I $ : 특성행렬
  • $ E_{\lambda} = Null(A- \lambda I) $ : A의 고유공간

알고리즘 고유값, 고유벡터, 고유공간의 기저의 계산

입력: n * n 행렬 A

  1. 특성다항식 $ \det(A - \lambda I) $을 계산
  2. $ \det(A - \lambda I) = 0 $$ \lambda $에 관하여 풀어서 A의 고유값을 구하여라.
  3. 각각의 고유값 $ \lambda_i $에 대하여 확대계수행렬 $ [ A - \lambda_i I : 0 ] $을 완전히 간소화하여 제차연립방정식 $(A- \lambda_i I) v = 0 $을 풀어라. 비자명해가 $ \lambda_i $에 대응하는 A의 고유벡터이다.
  4. 단계 3에서 $ \det(A - \lambda I) = 0 $의 일반해의 자유변수를 계수로 하는 벡터의 일차결합으로 나타내어라. 이 벡터는 $ E_{\lambda_i} $의 기저를 이룬다.
    출력: A의 고유값 $ \lambda_1, \dots, \lambda_i $, 각각의 $ E_{\lambda_i} $에 대한 고유벡터 기저

가역행렬의 고유값

정사각 행렬 A가 가역일 필요충분 조건은,

$$\det(A) \neq = 0 \Leftrightarrow \det(A - 0I) \neq 0$$

정리 2

정사각행렬 A가 가역일 필요충분조건은, A의 고유값이 0이 아닌 것이다.

삼각행렬의 고유값

만약 A가 삼각행렬이면 $ A - \lambda I $도 삼각행렬이다. 따라서,

$$\det(A - \lambda I) = (a_{11} - \lambda)(a_{22} - \lambda)\dots(a_{nm} - \lambda)$$

정리 3

삼각행렬의 고유값은 그것의 대각성분이다.

$ A^kx $의 빠른 계산

n * n 크그의 행렬 A의 $ A^kx $를 계산하고자 할 때, n이나 k가 크면 계산하기아 번거롭다. 이 때 A의 고유값과 고유벡터를 알고 있다면 계산을 수월히 할 수 있다.

x가 고유벡터의 $ v_1, \dots, v_n $의 일차결합이라고 가정한다면,

$$x = c_1 v_1 + \dots + c_n v_n$$

$ A^kx $는 다음과 같이 쓸 수 있다.

$$
Ax = A(c_1 v_1 + \dots + c_n v_n) \\
= c_1 A v_1 + \dots + c_n A v_n \\
= c_1 \lambda_1 v_1 + \dots + c_n \lambda_n v_n
$$

$$A^kx = c_1 \lambda_1^k v_1 + \dots + c_n \lambda_n^k v_n$$

단, x가 A의 일차결합으로 쓸 수 있을 때만이 가능하다.

선형변환의 고유값

행렬 A로 정의되는 선형변환 $ T: V \rightarrow V $의 고유값과 고유벡터 또한 생각할 수 있다. 만약 이러한 변환에서 어떤 스칼라 $ \lambda $$ T(v) = \lambda v $일 때, 이것을 선형변환의 고유값과 고유벡터라고 할 수 있다.

정리 4

V를 유한차원 벡터공간이라 하자. $ T: v \rightarrow V $가 선형변환으로 V의 적당한 기저 $B = \{ v_1, \dots, v_n \} $를 갖는다고 하자. 그러면,

$$T(v) = \lambda v \Leftrightarrow A[v]_B = \lambda[v]_B$$

이다. 따라서,

  1. $ \lambda $가 T의 고유값일 필요충분조건은 그것이 A의 고유값일 때이다.
  2. v가 T의 고유벡터일 필요충분조건은 $ [v]_B $가 A의 고유벡터일 때이다.

7.2 대각화

대각행렬은 계산이 쉬워 선호된다. 따라서 대각행렬로 변환한 뒤 계산을 시도하기도 한다.
하지만 정사각행렬이라고 모두 대각화 할 수 있는 것은 아니며, 행렬 A를 대각화시키는 행렬 P와 D는 일의적이 아니다.

정사각행렬의 대각화

정리 5: 대각화 판정법

A를 n * n 행렬이라고 하자.

  1. A가 대각화가능일 필요충분조건은 그것이 n개의 일차독립인 고유벡터를 갖는다.
  2. 만약 A가 $ P^{-1}AP = D $를 만족하는 대각화가능행렬이면, P의 열은 A의 고유벡터이고 D의 대각성분은 대응하는 고유값이다.
  3. 만약 $ \{ v_1, \dots, v_n \} $가 대응하는 고유값이 $ \lambda_1, \dots, \lambda_n $인 A의 일차독립인 고유벡터이면 A는
    $ P = \big[ v_1, v_2, \dots, v_n \big] $$ D = \big[ \lambda_{n} \big] $에 의해 대각화될 수 있다.

정리 6

n * n 행렬 A가 대각화가능일 필요충분조건은 $ R^n$이 A의 고유벡터로 되어있는 기저를 가질 때이다.

정리 7

$ \lambda_1, \dots, \lambda_l $을 n * n 크기의 행렬 A의 임의의 서로 다른 고유값이라고 하자.

  1. 임의의 대응하는 고유벡터 $v_1, \dots, v_l $은 일차독립이다.
  2. 만약 $B_1, \dots, B_l$가 대응하는 고유공간의 기저이면, $ B = B_1 \cup \dots \cup B_l $은 일차독립이다.
  3. l을 A의 모든 서로 다른 고유값의 수라고 하자. 그러면 A가 대각화 가능일 필요충분조건은 B는 n의 원소를 가질 때이다.

정리 8

n개의 서로 다른 고유값을 가지는 임의의 n * n 행렬 A는 대각화가능이다.

정리 9

A가 대각화 가능일 필요충분조건은 각각의 고유값에 댛여 기하적 중복도와 대수적 중복도가 일치할 때이다.

알고리즘: 대각화 과정

입력 n * n 행렬 A

  1. A의 모든 고유공간에 대하여 기저 $B_1, \dots, B_l$ 를 계산하여라. 합집합 $ B = B_1 \cup \dots \cup B_l $를 형성하여라.
  2. 만약 B가 원소를 n보다 적게 가지면 A는 대각화가능이 아니다.
  3. 만약 B가 원소를 n개 가지면 A는 대각화가능이다.
  4. B의 원소를 열로 하는 P와 대응하는 고유값을 대각성분으로 하는 D에 의해 A는 대각화 가능이된다.
    출력: P와 D는 A를 대각화 한다.

대각화가능 행렬의 거듭제곱

정리 10

만약 A가 P와 D에 의해 대각화된다면, $k = 0, 1, 2, \dots $에 대하여 $ A^k = PD^k P^{-1} $이다. 더욱이 A가 가역이면, 음수인 k에 대해서도 성립한다.

변수의 중요한 변경

A를 P와 D에 의해 대각화되는 대각화 가능행렬이라고 하자. 행렬방정식 $ Ax = b $를 풀고자 할 때,
만약 $x = Py \Leftrightarrow y = P^{-1}x $로 대체하고, $ A= P D P^{-1} $로 대체하면,

$$Ax = b \\ P^{-1}Ax = P^{-1}b \\ P^{-1}APP^{-1}x = P^{-1}b \\ P^{-1}APy = Pb \\ Dy = P^{-1}b$$

인 방정식을 얻는다. 마지막 식은 대각행렬인 성질 때문에 y에 관하여 풀기가 쉬워진다.

선형변환의 대각화

정리 11

$ T: V \rightarrow V $를 유한차원 벡터공간 V의 선형변환이라고 한다면,

  1. T가 대각화가능일 필요충분조건은 V가 T의 고유벡터의 기저를 가질 대이다.
  2. T가 대각화가능일 필요충분조건은 V의 임의의 기저에 관한 T의 행렬이 대각화가능할 때이다.
  3. 만약 T가 B에 의해 대각화가능이엇다면, B의 벡터는 T의 고유벡터이다.

7.3 고유값과 고유벡터의 근사

특성다항식을 이용하여 고유값과 고유벡터를 계산하였지만 이 방법은 실제로 사용하기에는 너무 번거로운 방법이다. 따라서 거듭제곱방법, 역거듭제곱방법을 이용하여 고유값과 고유벡터를 근사하는 방법을 알아보도록 하자.

거듭제곱방법

임의의 n-벡터 x가 존재한다고 하자. $ A^k x $를 생각해보았을 때, k가 증가할 수록 점점 A의 고유벡터에 평행하게 될 것이다. A의 고유값이 $ \lambda_1, \dots, \lambda_n $이라고 한다면 우세한 고유값은 그 절대값이 큰 고유값을 의미한다.

정리 12

A를 기본 고유벡터가 $ v_1, \dots, v_n $이고 대응하는 고유값은 $ \lambda_1, \dots, \lambda_n $이며, 우세한 고유값이 $ \lambda_1 $이라고 하자.
어떤 벡터 x를 $ v_i $ 의 일차결합
$ x = c_1 v_1 + \dots + c_n v_n, c_1 \neq 0 $ 으로 표현한다면, k가 커졌을 때 $ A^k x $의 스칼라배는 $ v_1$의 스칼라 배에 근접한다. 특히 $ A^k x $의 방향은 $v_1$의 방향에 근접한다.

이를 이용한 알고리즘을 살펴보자.

알고리즘 1: 거듭제곱 방법 - 최대성분 1

A를 우세한 고유값이 있는 n * n 대각화가능 행렬이라고 하자. 임의의 벡터 $ x_0 $로부터 시작하여 k번 반복한다.
입력 : $ A, x_0, k $

  1. $ l_0 $을 가장 큰 절대값의 $ x_0 $의 성분이라고 하자.
  2. $ y_0 = (1/l_0) x_0 $ 으로 계산한다.
  3. $ i = 1, \dots, k $에 대하여
    1. $ x_i = A y_{i-1} $를 계산한다.
    2. $ l_i $을 가장 큰 절대값의 $ x_i $의 성분이라고 하자.
    3. $ y_i = (1 / l_i) x_i $를 계산한다.

출력: $ y_k, l_k$
대부분의 $ x_0 $에 대하여 $l_k, y_k$는 우세한 고유값과 그 고유벡터이다.

Rayleigh 몫(또하는 Rayleigh-Ritz 방법)

Rayleigh의 몫이란, A가 주어졌을 때 다음 식을 만족하는 x를 말한다.

$$r(x) = \frac{x^T A x}{x^T x}$$

만약 x가 고유벡터라면 $ x^T A x = x^T \lambda x = \lambda (x^T x) $가 되므로 이것을 이용한다.

$ x_0 $ 를 정규화시킨 벡터를 $ y_ 0 $ 라고 하자. $ x_1 = A y_0 $ 라고 하자. 그러면 Rayleigth식은 아래처럼 계산된다.

$$r(y_0) = \frac{y_0^T A y_0}{y_0^T y_0 = 1} = y_0 \cdot x_1$$

알고리즘 2: Rayleigh 몫, 또는 Rayleigh-Ritz 방법

A를 우세한 고유값이 있는 n * n 대각화가능 행렬이라고 하자. 임의의 벡터 $ x_0 $로부터 시작하여 k번 반복한다.
입력 : $ A, x_0, k $

  1. $ i = 1, \dots, k $에 대하여
    1. $ y_i = (1 / ||x_i||) x_i $
    2. $ x_{i+1} = A y_i $
    3. $ r_i = y_i \cdot x_{i+1} $

출력: $ y_k, r_k$
대부분의 $ x_0 $에 대하여 $r_k, y_k$는 우세한 고유값과 그 고유벡터이다.

원점이동

앞의 방법을 이용하여 가장 우세한 고유값을 계산하였다. 이제 이것을 이용하여 가장 우세하지 않은 고유값을 계산해보도록 하자.

만약 $ \lambda $가 고유벡터 v에 해당하는 고유값이라면 임의의 스칼라 c에 대해 다음 식을 만족한다.

$$(A - cI) v = Av - cv = (\lambda -c) v$$

행렬 $ A - cI $는 고유값 $ \lambda - c $와 대응하는 고유벡터 v를 가진다. 만약 $ \lambda_1, \dots, \lambda_n $가 A의 고유값이면,$ 0, \dots, \lambda_n - \lambda_1 $$ B = A \lambda_1 I $의 고유값이 된다.

따라서 앞의 방법으로 A의 우세한 고유값 $ \lambda_1 $ 을 구한 뒤, B의 고유값을 구하면 이는 A의 우세한 고유값과 가장 차이가 많이 나는 고유값을 구한 것이 된다. 여기에 다시 $ \lambda_1 $을 더해줌으로써 가장 먼 고유값을 구할 수 있다.

역 거듭제곱 방법

만약 $ \lambda, v $가 행렬 A의 고유값과 고유벡터라고 한다면, $ \lambda^{-1} $$ A^{-1}$ 에서 고유벡터 v를 갖는 고유값이다.

알고리즘 3: 역 거듭제곱 방법

입력: $A, x_0, k $
$ i =0 , \dots, k-1 $에 대하여

  1. $ y_i = (1/ ||x_i||) x_i $
  2. 연립방정식 $ Az = y_i $를 z에 대해 푼다.
  3. $ x_{i+1} = z $으로 놓는다.
  4. $r_i = y_i \cdot x_{i+1} $
    출력: $y_{k-1}, r_{k-1} $
    대부분의 $ x_0 $에 대하여 $r^{-1}_k$는 원점에 가장 가까운 A의 고유값에 근사하고, $ y_k$는 대응하는 그 고유벡터이다.

변경된 역 거듭제곱 방법

만약 임의의 수 $\mu $가 다른 고유값보다 고유값 $\lambda $에 가장 가깝다면, $1/(\lambda - \mu)$$(A - \mu I)^{-1}$의 우세한 고유값이다.

알고리즘 4: 변경된 역 거듭제곱 방법

입력: $A, x_0, k $, 고유값에 대한 초기 추정값 $ \mu $
$ i =0 , \dots, k-1 $에 대하여

  1. $ y_i = (1/ ||x_i||) x_i $
  2. 연립방정식 $ (A - \mu I)z = y_i $를 z에 대해 푼다.
  3. $ x_{i+1} = z $으로 놓는다.
  4. $r_i = y_i \cdot x_{i+1} $
    출력: $y_{k-1}, r_{k-1} $
    대부분의 $ x_0 $에 대하여 $\mu + r^{-1}_k$는 원점에 가장 가까운 A의 고육밧에 근사하고, $ y_k$는 대응하는 그 고유벡터이다.

7.4 동역학계의 응용

이산 동역학계

동역학계 또는 차분 방정식은 시간에 의존하는 벡터 양 $x(t)$에 관한 방정식이다. 여기서 시간 변수는 정수이고 $ x(t) $$x_t$로 쓴다. 1계 이산 제차 동역학계는 $x_{k+1} = A x_k $ 인 꼴의 벡터방정식이다. 이를 반복하여 $ x_0 $으로부터 $ x_k $의 상태를 계산할 수 있다.

정리 13

A를 일차독립인 고유벡터가 $ v_1, \dots, v_n $이고 대응하는 고유값이 $ \lambda_1, \dots, \lambda_n $이라면, 동역합계 $ x_{k+1} = A x_k $의 해는 다음으로 주어진다.

$$x_k = c_1 \lambda_1^k v_1 + \dots + c_n \lambda_n^k v_n$$

여기서 계수 $ c_1, \dots, c_n $$ x = c_1 v_1+ \dots + c_n v_n $ 을 만족한다.

동역학계의 오랜기간의 상태

앞에서 살펴본 것과 같이 동역학계가 오랜기간동안 지속되면 가장 우세한 고유값에 해당하는 고유벡터에 근접하는 방향을 갖는다.

유인자, 반발자, 안장점

만약 모든 고유값이 1보다 작은 절대값을 가지면, 동역학계의 모든 자취는 원점에 근접한다. 그 원점을 유인자(attractor)라고 한다. $ x_k = c_1 \lambda_1^k v_1 + \dots + c_n \lambda_n^k v_n $의 각 고유값이 1보다 작으므로 영으로 수렴하게 되는 것이다.

모든 고유값이 1보다 크면 모든 자취는 원정메서 떨어지게 된다. 그 원점을 반발자(repeller)라고 한다.

만약 어떤 자취는 원점을 향하여 움직이고 어떤 것은 원점에서 떨어져서 움직이면, 원점을 안장점(saddle point)라고 한다.


Add a Comment Trackback