용어 정리
- Characteristic Equation - 특성 방정식
Characteristic Equation 에 대해
- characteristic equation 은 eigenvalue 와 밀접한 관련이 있는 equation 이다.
- 주어진 $A$ 행렬의 eigenvalue 를 구할 때 $(A - \lambda I)\mathbf{x} = \mathbf{0}$ 를 이용한다.
- $A$ 가 eigenvalue를 갖고 있으려면 $A\mathbf{x} = 0$ 에서 nontrivial solution 을 갖고 있어야 한다. 이는 $A$ 가 not invertible 을 의미하고 $\mbox{det}(A) = 0$ 이 되어야 한다.
- 이를 통해 2차방정식의 해를 구하면, eigenvalue 는 3, -7 인것을 확인할 수 있다.
A scalar $\lambda$ is an eigenvalue of an $n \times n$ matrix $A$ if and only if $\lambda$ satisfies the characteristic equation
\[\mbox{det}(A - \lambda I) = 0\]
- characteristic equation 은 $ \mbox{det}(A - \lambda I) = 0 $ 을 의미한다.
- $\lambda$ 가 characteristic equation 을 만족하면 $\lambda$ 는 행렬 $A$ 의 eigenvalue 이다.
- 예시 문제
- 행렬 A 의 characteristic equation 을 찾아라.
- $A$ 는 upper triangular matrix 이다.
- 따라서 diagonal term들이 eigenvalue 이다.
- $A$ 의 det 는 diagonal term 들의 곱이다.
\(\mbox{det}(A - \lambda I) = \mbox{det} \begin{bmatrix} 5 - \lambda & -2 & 6 & -1 \\\ 0 & 3 - \lambda & -8 & 0 \\\ 0 & 0 & 5 - \lambda & 4 \\\ 0 & 0 & 0 & 1 - \lambda \end{bmatrix}\) \(= (5 - \lambda)(3 - \lambda)(5 - \lambda)(1 - \lambda) = (\lambda -5)^2 (\lambda - 3)(\lambda - 1) = 0\)
\[\lambda^4 - 14\lambda^3 + 68\lambda^2 - 130\lambda + 75 = 0\]- 여기서, eigenvalue 는 5, 3, 1 이 된다.
- eigenvalue 5 는 multiplicity 2 를 갖는다고도 한다.
Similarity - 유사도
- n차 방정식에서 eigenvalue를 찾는 것은 쉽지 않기 때문에 similarity 를 주로 이용한다.
- $ A = PBP^{-1}$ 가 성립할 때, $A$ 는 $B$ 에 similar 하다고 표현한다.
- similarity transformation 은 $ A = P^{-1}AP $ 로 변환되는 transformation 을 의미한다.
- eigenvalue 를 찾는 방법중 하나는 similar 한 matrix 를 찾아서 eigenvalue 를 찾는것이다.
Theorem3.
If $n \times n$ matrices $A$ and $B$ are similar, then they have the same characteristic polynimial and hence the same eigenvalues (with the samce multiplicities).
- A 와 B가 similar 이고 동일한 characteristic polynomial 을 갖고 있으면 두 행렬은 동일한 eigenvalue 를 갖는다.
- eigenvalue 는 동일하지만, eigen vector 와 eigen space 는 보통 다르다.
- 증명
Numerical Notes
There is no analytic formula or finite algorithm to solve the characteristic equation for $n \ge 5$ .
특수해를 제외하고는 해가 명시적이지 않다. 즉 n 이 5 이상인 행렬 부터는 eigenvalue 를 찾기가 매우 힘들다
The characteristic polynomial is given in the following form
\[(\lambda - \lambda _1)(\lambda - \lambda _2) \dots (\lambda - \lambda _n)\]after computing the eigenvalues first
eigenvalue 인 $\lambda _1 , \dots , \lambda _n$ 들을 먼저 구한 뒤, characteristic polynomial 을 구할 수 있다.
QR algorithm is commonly used for estimating the eigenvalues.
보통 eigenvalue 를 “추정” 하는데에는 QR 알고리즘을 사용한다. 추정한다는 뜻은 에러가 존재할 수도 있다는 뜻이다. 이것은 보통 수치해석적 방법론으로 풀며 공학적으로는 Power Method, Inverse Power Method 등을 사용한다.
- QR 알고리즘 맛보기
If $A = QR$ with $Q$ is invertible, then $A$ is similar to $A_1 = RQ$
- A = QR 의 형태로 factorization 을 했을 때, Q 가 invertible 하다면 행렬 A 는 RQ 와 similar 하다.
- 증명하려면 우선, 다음과 같은 성질을 지녀야한다.
- 알고리즘을 반복 수행을 실행한다.
- $A = Q_1R_1$ , $A_1 = R_1Q_1$ 여기서 $A_1$ 을 다시 QR factorization 을 실행
- $A_1 = Q_2R_2$ , $A_2 = R_2Q_2$ … 이것을 계속 반복수행을 한다.
- 충분히 많은 k 번을 수행했을 때
- $A_k$ converges to a triangular matrix (under certain conditions) - Wilkinson Shift 를 통해 항상 converge 하다는 것을 확인가능.
- 특정 조건하에 무한히 많은 k번의 QR 알고리즘을 수행한다면, $A_k$ 는 triangular matrix 에 converge 한다. (현실적으로 무한히 수행이 불가능하므로 충분한 특정 횟수만큼 k 번 실행)
- 위에서 구한 $A_1, \dots , A_k$ 는 similar 하기 때문에 eigenvalue 는 같다!
여기서 $A_k$ 는 triangular matrix 에 converge 하므로, $A_k$ 의 diagonal term 들은 eigenvalue 들이고, 이말인즉슨 similar한 $A$ 의 diagonal term 들 역시 eigenvalue 라는 말이다.
- 사실 QR algorithm 도 상당히 무겁고 오래걸린다. $n^3$ 정도..