Eigendecomposition of a matrix

Original article: w:Eigendecomposition of a matrix

선형 대수(linear algebra)에서, 고유분해(eigendecomposition)는 정식의 형식(canonical form)으로 행렬의 인수분해이며, 이로써 행렬은 고윳값과 고유벡터의 관점에서 표현됩니다. 대각화-가능 행렬(diagonalizable matrices)만 이 방법으로 인수화될 수 있습니다. 인수화되는 행렬이 정규(normal) 또는 실수 대칭 행렬이면, 그 분해는 스펙트럼 정리(spectral theorem)에서 파생된, "스펙트럼 분해"라고 불립니다.

Fundamental theory of matrix eigenvectors and eigenvalues

Main article: Eigenvalue, eigenvector and eigenspace

차원 N의 (비-영) 벡터 v는 만약 그것이 일부 스칼라 λ에 대해 다음 형식의 선형 방정식을 만족시키면 정사각 N × N 행렬 A의 고유벡터입니다:

$\mathbf {A} \mathbf {v} =\lambda \mathbf {v}$

그런-다음 λ는 v에 대응하는 고윳값이라고 불립니다. 기하학적으로 말하면, A의 고유벡터는 A가 단순히 늘이거나 줄어드는 벡터이고, 그것들이 늘어나거나 줄어드는 총양이 고윳값입니다. 위의 방정식은 고윳값 방정식 또는 고윳값 문제라고 불립니다.

이것은 고윳값에 대한 방정식을 생성합니다:

$p\left(\lambda \right)=\det \left(\mathbf {A} -\lambda \mathbf {I} \right)=0.$

우리는 p(λ)를 특성 다항식(characteristic polynomial)이라고 부르고, 특성 방정식이라고 불리는 방정식은 미지수 λ에서 N차 다항식입니다. 이 방정식은 1 ≤ N_λ ≤ N인 N_λ 구별되는 해를 가집니다. 해, 즉 고윳값의 집합은 A의 스펙트럼(spectrum)이라고 불립니다.

만약 스칼라의 필드가 대수적으로 닫혀 있으면, p를 다음과 같이 인수화(factor)할 수 있습니다:

$p\left(\lambda \right)=\left(\lambda -\lambda _{1}\right)^{n_{1}}\left(\lambda -\lambda _{2}\right)^{n_{2}}\cdots \left(\lambda -\lambda _{N_{\lambda }}\right)^{n_{N_{\lambda }}}=0.$

정수 n_i는 고윳값 λ_i의 대수적 중복도(algebraic multiplicity)라고 이름-짓습니다. 대수적 중복도의 합해서 N입니다: ${\textstyle \sum _{i=1}^{N_{\lambda }}{n_{i}}=N.}$

각 고윳값 λ_i에 대해, 다음과 같은 특정 고윳값 방정식을 가집니다:

$\left(\mathbf {A} -\lambda _{i}\mathbf {I} \right)\mathbf {v} =0.$

각 고윳값 방정식에 대해 1 ≤ m_i ≤ n_i 선형적으로 독립(linearly independent) 해가 있습니다. m_i 해 (영 벡터를 제공하는 것 제외)의 선형 조합은 고윳값 λ_i와 결합된 고유벡터입니다. 정수 m_i는 λ_i의 기하적 중복도(geometric multiplicity)라고 이름-짓습니다. 대수적 중복도 n_i와 기하적 중복도 m_i는 같을 수도 있고 같지 않을 수도 있지만, 항상 m_i ≤ n_i라는 점을 명심하는 것이 중요합니다. 가장 간단한 경우는 물론 m_i = n_i = 1일 때입니다. 선형적으로 독립 고유벡터의 총 개수, N_v는 기하적 중복도를 합함으로써 계산될 수 있습니다:

$\sum _{i=1}^{N_{\lambda }}{m_{i}}=N_{\mathbf {v} }.$

고유벡터는 i-번째 고윳값에 대한 j-번째 고유벡터인 v_ij와 함께 이중 인덱스를 사용하여 고윳값에 의해 인덱싱될 수 있습니다. 고유벡터는 k = 1, 2, ..., N_v를 갖는 단일 인덱스 v_k의 더 간단한 표기법을 사용하여 인덱싱될 수도 있습니다.

Eigendecomposition of a matrix

A를 n개의 선형적으로 독립 고유벡터 q_i (여기서 i = 1, ..., n)를 갖는 정사각 n × n 행렬이라고 놓습니다. 그런-다음 A는 다음과 같이 인수화될 수 있습니다:

$\mathbf {A} =\mathbf {Q} \mathbf {\Lambda } \mathbf {Q} ^{-1}$

여기서 Q는 i-번째 열이 A의 고유벡터인 정사각 n × n 행렬이고, Λ는 대각 원소가 해당하는 고윳값, Λ_ii = λ_i인 대각 행렬(diagonal matrix)입니다. 대각화-가능 행렬(diagonalizable matrices)만 이 방법으로 인수화될 수 있음에 주목하십시오. 예를 들어, 결함-있는 행렬(defective matrix) $\left[{\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right]$ (이는 전단 행렬)은 대각화될 수 없습니다.

n 고유벡터 q_i는 보통 정규화되지만, 그럴 필요는 없습니다. n 고유 벡터, v_i의 비-정규화된 집합도 Q의 열로 사용될 수 있습니다. 이는 Q에서 고유벡터의 크기가 Q⁻¹의 존재에 의한 분해에서 취소된다는 점에 주목함으로써 이해될 수 있습니다. 만약 고윳값 λ_i 중 하나가 하나보다 많은 선형적으로 독립 고유벡터를 가지면 (즉, λ_i의 기하적 중복도가 1보다 크면), 이 고윳값 λ_i에 대한 이들 고유벡터는 서로 직교하도록 선택될 수 있습니다; 어쨌든, 만약 두 개의 고유벡터가 두 개의 다른 고윳값에 속하면, 그것들은 서로 직교하는 것이 불가능할 수 있습니다 (아래 예제 참조). 한 가지 특별한 경우는 A가 정규 행렬이면, 스펙트럼 정리에 의해 직교정규 기저 {q_i}에서 A를 항상 대각화할 수 있다는 것입니다.

분해는 고유벡터의 기본 속성에서 파생될 수 있습니다:

${\begin{aligned}\mathbf {A} \mathbf {v} &=\lambda \mathbf {v} \\\mathbf {A} \mathbf {Q} &=\mathbf {Q} \mathbf {\Lambda } \\\mathbf {A} &=\mathbf {Q} \mathbf {\Lambda } \mathbf {Q} ^{-1}.\end{aligned}}$

비-영 고윳값을 갖는 선형적으로 독립 고유벡터 q_i는 x ∈ Cⁿ에 대해 모든 가능한 곱 Ax에 대한 기저 (반드시 직교정규일 필요는 없음)를 형성하며, 이는 해당 행렬 변환(matrix transformation)의 이미지 (또는 치역)와 같고, 역시 행렬 A의 열 공간(column space)과 같습니다. 비-영 고윳값을 갖는 선형적으로 독립 벡터 q_i의 숫자는 행렬 A의 랭크(rank)와 같고, 해당 행렬 변환의 이미지 (또는 치역) 차원과 같고, 마찬가지로 및 열 공간과도 같습니다.

비-영 고윳값을 갖는 선형적으로 독립 벡터 q_i는 행렬 변환 A의 널 공간(null space, 커널이라고도 함)에 대한 기저 (직교정규로 선택될 수 있음)를 형성합니다.

Example

다음과 같은 2 × 2 실수 행렬 A는

$\mathbf {A} ={\begin{bmatrix}1&0\\1&3\\\end{bmatrix}}$

다음과 같은 비-특이 행렬 B의 곱셈을 통해 대각 행렬로 분해될 수 있습니다:

$\mathbf {B} ={\begin{bmatrix}a&b\\c&d\end{bmatrix}}\in \mathbb {R} ^{2\times 2}.$

그런-다음 일부 실수 대각 행렬 $\left[{\begin{smallmatrix}x&0\\0&y\end{smallmatrix}}\right]$에 대해,

${\begin{bmatrix}a&b\\c&d\end{bmatrix}}^{-1}{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}a&b\\c&d\end{bmatrix}}={\begin{bmatrix}x&0\\0&y\end{bmatrix}}.$

방정식의 양쪽 변의 왼쪽에 B를 곱하면:

${\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}a&b\\c&d\end{bmatrix}}={\begin{bmatrix}a&b\\c&d\end{bmatrix}}{\begin{bmatrix}x&0\\0&y\end{bmatrix}}.$

위의 방정식은 두 개의 연립 방정식(simultaneous equations)으로 분해될 수 있습니다:

${\begin{cases}{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}a\\c\end{bmatrix}}={\begin{bmatrix}ax\\cx\end{bmatrix}}\\{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}b\\d\end{bmatrix}}={\begin{bmatrix}by\\dy\end{bmatrix}}\end{cases}}.$

고윳값(eigenvalues) x와 y를 인수로 묶으면:

${\begin{cases}{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}a\\c\end{bmatrix}}=x{\begin{bmatrix}a\\c\end{bmatrix}}\\{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}b\\d\end{bmatrix}}=y{\begin{bmatrix}b\\d\end{bmatrix}}\end{cases}}$

다음이라고 놓고,

$\mathbf {a} ={\begin{bmatrix}a\\c\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}b\\d\end{bmatrix}},$

이것은 다음과 같은 두 개의 벡터 방정식을 제공합니다:

${\begin{cases}\mathbf {A} \mathbf {a} =x\mathbf {a} \\\mathbf {A} \mathbf {b} =y\mathbf {b} \end{cases}}$

그리고 고윳값으로 두 개의 해를 포함하는 단일 벡터 방정식으로 나타낼 수 있습니다:

$\mathbf {A} \mathbf {u} =\lambda \mathbf {u}$

여기서 λ는 두 개의 고윳값 x와 y를 나타내고, u는 벡터 a와 b를 나타냅니다.

λu를 왼쪽 변으로 이동하고 u를 인수로 묶어 내면

$(\mathbf {A} -\lambda \mathbf {I} )\mathbf {u} =\mathbf {0}$

B가 비-특이이기 때문에, u가 비-영이라는 것이 필수입니다. 그러므로,

$\det(\mathbf {A} -\lambda \mathbf {I} )=0$

따라서

$(1-\lambda )(3-\lambda )=0$

이는 행렬 A에 대한 고윳값의 해를 λ = 1 또는 λ = 3으로 제공하고, A의 고유분해에서 얻은 결과 대각 행렬은 $\left[{\begin{smallmatrix}1&0\\0&3\end{smallmatrix}}\right]$입니다.

위의 연립 방정식에 해를 다시 대입하여

${\begin{cases}{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}a\\c\end{bmatrix}}=1{\begin{bmatrix}a\\c\end{bmatrix}}\\{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}b\\d\end{bmatrix}}=3{\begin{bmatrix}b\\d\end{bmatrix}}\end{cases}}$

방정식을 풀면, 다음을 가집니다:

$a=-2c\quad {\text{and}}\quad b=0,\qquad c,d\in \mathbb {R} .$

따라서 A의 고유분해에 필요한 행렬 B는 다음과 같습니다:

$\mathbf {B} ={\begin{bmatrix}-2c&0\\c&d\end{bmatrix}},\qquad c,d\in \mathbb {R} ,$

즉:

${\begin{bmatrix}-2c&0\\c&d\end{bmatrix}}^{-1}{\begin{bmatrix}1&0\\1&3\end{bmatrix}}{\begin{bmatrix}-2c&0\\c&d\end{bmatrix}}={\begin{bmatrix}1&0\\0&3\end{bmatrix}},\qquad c,d\in \mathbb {R}$

Matrix inverse via eigendecomposition

Main article: Inverse matrix

만약 행렬 A가 고유분해될 수 있고 고윳값 중 어떤 것도 영이 아니면, A는 역-가능(invertible)이고 그것의 역은 다음과 같이 제공됩니다:

$\mathbf {A} ^{-1}=\mathbf {Q} \mathbf {\Lambda } ^{-1}\mathbf {Q} ^{-1}$

만약 $\mathbf {A}$가 대칭 행렬이면, $\mathbf {Q}$는 $\mathbf {A}$의 고유벡터로부터 형성되기 때문에, $\mathbf {Q}$는 직교 행렬(orthogonal matrix)임을 보장하며, 따라서 $\mathbf {Q} ^{-1}=\mathbf {Q} ^{\mathrm {T} }$입니다. 게다가, Λ는 대각 행렬(diagonal matrix)이기 때문에, 그 역은 쉽게 계산될 수 있습니다:

$\left[\Lambda ^{-1}\right]_{ii}={\frac {1}{\lambda _{i}}}$

Practical implications

고유분해가 측정된 실제 데이터의 행렬에 사용되면, 그 역(inverse)은 모든 고윳값이 위의 형식에서 수정되지 않게 사용될 때 덜 유효할 수 있습니다. 이것은 고윳값이 상대적으로 작아질수록, 반전에 대한 기여도가 크기 때문입니다. 0에 가깝거나 측정 시스템의 "잡음"에 있는 것들은 과도한 영향을 미치고 역을 사용하여 해(검출)를 방해할 수 있습니다.

두 가지 완화 방안이 제안되어 왔습니다: 작거나 영 고윳값을 잘라내는 것, 및 가장 낮은 신뢰할 수 고윳값을 그것 아래에 있는 고윳값으로 확장하는 것입니다. 잡음에 의해 지배될 때 고윳값을 롤 오프(roll off)하기 위한 통계적으로 동기 부여되지만 편향된 방법인 티크호노프 조절(Tikhonov regularization)을 참조하십시오.

첫 번째 완화 방법은 원래 행렬의 성긴 표본과 유사하여, 가치 있는 것으로 고려되는 않는 구성 요소를 제거합니다. 어쨌든, 해 또는 검출 과정이 잡음 수준에 가까우면, 잘라내기를 수행하면 원하는 해에 영향을 미치는 구성 요소가 제거할 수 있습니다.

두 번째 완화 방법은 더 낮은 값이 반전에 훨씬 덜 영향을 미치지만, 여전히 기여하도록, 잡음 근처의 해를 계속 찾을 수 있음을 만족하는 고윳값을 확장합니다.

신뢰할 수 있는 고윳값은 극단적으로 유사하고 낮은 값의 고윳값이 측정 잡음 (대부분의 시스템에서 낮은 것으로 가정됨)을 잘 나타낸다고 가정함으로써 찾을 수 있습니다.

만약 고윳값이 값에 의해 랭크-정렬된 것이면, 신뢰할 수 있는 고윳값은 정렬된 고윳값의 라플라스(Laplacian)의 최소화에 의해 찾을 수 있습니다:

$\min \left|\nabla ^{2}\lambda _{\mathrm {s} }\right|$

여기서 고윳값은 정렬됨을 나타내기 위해 s를 아래-첨자로 붙입니다. 최소화의 위치는 가장 낮은 신뢰할 수 있는 고윳값입니다. 측정 시스템에서, 이 신뢰할 수 있는 고윳값의 제곱근은 시스템 구성 요소에 걸쳐 평균 잡음입니다.

Functional calculus

고유분해는 행렬의 거듭제곱 급수(power series)를 훨씬 더 쉽게 계산하는 것을 허용합니다. 만약 f (x)가 다음과 같이 주어지면

$f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots$

다음임을 압니다:

$f\!\left(\mathbf {A} \right)=\mathbf {Q} \,f\!\left(\mathbf {\Lambda } \right)\mathbf {Q} ^{-1}$

Λ가 대각 행렬(diagonal matrix)이기 때문에, Λ의 함수는 계산하기 매우 쉽습니다:

$\left[f\left(\mathbf {\Lambda } \right)\right]_{ii}=f\left(\lambda _{i}\right)$

f (Λ)의 비-대각 원소는 영입니다; 즉, f (Λ)도 대각 행렬입니다. 그러므로, f (A)를 계산하는 것은 각 고윳값에 대한 단지 함수를 계산하는 것으로 축소됩니다.

유사한 기법이 위로부터 다음을 사용하여 정칙 함수형 미적분(holomorphic functional calculus)과 함께 더 일반적으로 작동합니다:

$\mathbf {A} ^{-1}=\mathbf {Q} \mathbf {\Lambda } ^{-1}\mathbf {Q} ^{-1}$

다시 한번, 다음임을 찾습니다:

$\left[f\left(\mathbf {\Lambda } \right)\right]_{ii}=f\left(\lambda _{i}\right)$

Examples

${\begin{aligned}\mathbf {A} ^{2}&=\left(\mathbf {Q} \mathbf {\Lambda } \mathbf {Q} ^{-1}\right)\left(\mathbf {Q} \mathbf {\Lambda } \mathbf {Q} ^{-1}\right)=\mathbf {Q} \mathbf {\Lambda } \left(\mathbf {Q} ^{-1}\mathbf {Q} \right)\mathbf {\Lambda } \mathbf {Q} ^{-1}=\mathbf {Q} \mathbf {\Lambda } ^{2}\mathbf {Q} ^{-1}\\\mathbf {A} ^{n}&=\mathbf {Q} \mathbf {\Lambda } ^{n}\mathbf {Q} ^{-1}\\\exp \mathbf {A} &=\mathbf {Q} \exp(\mathbf {\Lambda } )\mathbf {Q} ^{-1}\end{aligned}}$

이는 함수 $f(x)=x^{2},\;f(x)=x^{n},\;f(x)=\exp {x}$에 대한 예제입니다. 게다가, $\exp {\mathbf {A} }$는 행렬 지수(matrix exponential)입니다.

Decomposition for special matrices

Main article: Spectral theorem

Subsets of important classes of matrices

A가 정규 또는 실수 대칭 행렬이면, 그 분해는 스펙트럼 정리에서 파생된 "스펙트럼 분해"라고 불립니다.

Normal matrices

복소-정사각 행렬 A가 정규 (A^*A = AA^*임을 의미, 여기서 A^*은 켤레 전치)인 것과 다음과 같이 분해될 수 있는 것은 필요충분 조건입니다:

$\mathbf {A} =\mathbf {U} \mathbf {\Lambda } \mathbf {U} ^{*}$

여기서 U는 유니태리 행렬(unitary matrix) (U^* = U⁻¹를 의미)이고 Λ = diag(λ₁, ..., λ_n)는 대각 행렬(diagonal matrix)입니다. U의 열 u₁, ..., u_n은 직교정규 기저(orthonormal basis)를 형성하고 해당 고윳값 λ₁, ..., λ_n을 갖는 A의 고유벡터입니다.

만약 A가 에르미트 행렬 (A = A*)로 제한되면, Λ는 실수 값 엔트리만 가집니다. 만약 A가 유니태리 행렬로 제한되면, Λ는 복소수 단위 원, 즉, |λ_i| = 1의 모든 값을 취합니다.

Real symmetric matrices

특별한 경우로, 모든 각 n × n 실수 대칭 행렬에 대해, 고윳값은 실수이고 고유벡터는 실수 및 직교정규(orthonormal)로 선택될 수 있습니다. 따라서 실수 대칭 행렬 A는 다음과 같이 분해될 수 있습니다:

$\mathbf {A} =\mathbf {Q} \mathbf {\Lambda } \mathbf {Q} ^{\mathsf {T}}$

여기서 Q는 그 열이 실수, A의 직교정규 고유벡터인 직교 행렬(orthogonal matrix)이고, Λ는 그 엔트리가 A의 고윳값인 대각 행렬입니다.

Useful facts

Useful facts regarding eigenvalues

• 고윳값의 곱은 A의 행렬식(determinant)과 같습니다: $$\det \left(\mathbf {A} \right)=\prod _{i=1}^{N_{\lambda }}{\lambda _{i}^{n_{i}}}$$ 각 고윳값은 거듭제곱 n_i, 대수적 중복도(algebraic multiplicity)가 올려짐에 주목하십시오.
• 고윳값의 합은 A의 대각합(trace)과 같습니다: $$\operatorname {tr} \left(\mathbf {A} \right)=\sum _{i=1}^{N_{\lambda }}{{n_{i}}\lambda _{i}}$$ 각 고윳값은 n_i, 대수적 중복도(algebraic multiplicity)가 곱해짐에 주목하십시오.
• 만약 A의 고윳값이 λ_i이고, A가 역가능이면, A⁻¹의 고윳값은 간단히 λ⁻¹
  _i입니다.
• 만약 A의 고윳값이 λ_i이면, f (A)의 고윳값은 임의의 정칙 함수(holomorphic function) f에 대해 간단히 f (λ_i)입니다.

Useful facts regarding eigenvectors

• 만약 A가 에르미트(Hermitian)이고 완전한-랭크이면, 고유벡터의 기저는 서로 직교(orthogonal)이도록 선택될 수 있습니다. 고윳값은 실수입니다.
• A⁻¹의 고유벡터는 A의 고유벡터와 같습니다.
• 고유벡터는 오직 곱셈 상수까지 정의됩니다. 즉, 만약 Av = λv이면 cv는 임의의 스칼라 c ≠ 0에 대한 고유벡터이기도 합니다. 특히, −v와 (임의의 θ에 대해) e^iθv도 고유벡터입니다.
• 퇴화 고윳값 (하나보다 많은 고유벡터를 가지는 고윳값)의 경우에서, 고유벡터는 선형 변환의 추가적인 자유도를 가집니다. 다시 말해, (퇴화 부분공간에서) 고윳값을 공유하는 고유벡터의 임의의 선형 (직교정규) 조합은 (부분공간에서) 자체 고유벡터입니다.

Useful facts regarding eigendecomposition

• A가 고유분해될 수 있는 것과 선형적으로 독립 고유벡터의 개수, N_v은 고유벡터의 차원과 같은 것: N_v = N은 필요충분 조건입니다.
• 만약 스칼라의 필드는 대수적으로 닫혀 있고 p(λ)가 반복된 근을 가지지 않으면, 즉, $N_{\lambda }=N$이면, A는 고유분해될 수 있습니다.
• 명제 "A가 고유분해될 수 있음"은 A가 역을 가짐을 의미하지는 않는데, 왜냐하면 일부 고윳값이 영이 될 수 있으며, 이는 역가능이 아니기 때문입니다.
• 명제 "A가 역을 가짐"은 A가 고유분해될 수 있음을 의미하지 않습니다. 반대예제는 $\left[{\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right]$이며, 이는 역가능 결함-있는 행렬(defective matrix)입니다.

Useful facts regarding matrix inverse

• A가 반전될 수 있는 것과 모든 고윳값이 비-영인 것은 필요충분(iff) 조건입니다: $$\lambda _{i}\neq 0\quad \forall \,i$$
• 만약 λ_i ≠ 0이고 N_v = N이면, 역은 다음에 의해 제공됩니다 $$\mathbf {A} ^{-1}=\mathbf {Q} \mathbf {\Lambda } ^{-1}\mathbf {Q} ^{-1}$$

Numerical computations

Further information: eigenvalue algorithm

Numerical computation of eigenvalues

주어진 행렬의 고윳값을 계산한다고 가정합니다. 만약 행렬이 작으면, 특성 다항식(characteristic polynomial)을 사용하여 기호적으로 계산할 수 있습니다. 어쨌든, 이것은 종종 더 큰 행렬에서는 불가능하며, 이 경우에서 수치적 방법(numerical method)을 사용해야 합니다.

실제로, 큰 행렬의 고윳값은 특성 다항식을 사용하여 계산되지 않습니다. 다항식을 계산하는 것은 그 자체로 비용이 많이 들고, 고차 다항식의 정확한 (기호적) 근은 계산하고 표현하기 어려울 수 있습니다: 아벨–루피니 정리(Abel–Ruffini theorem)는 고차 (5차 이상) 다항식의 근이 일반적으로 n-번째 근을 사용하여 간단하게 표현될 수 없음을 의미합니다. 그러므로, 고유벡터와 고윳값을 찾는 일반적인 알고리듬은 반복적(iterative)입니다.

뉴턴의 방법(Newton's method)과 같이 다항식의 근을 근사화하기 위한 반복 수치적 알고리듬이 존재하지만, 일반적으로 특성 다항식을 계산하고 그런-다음 이들 방법을 적용하는 것은 비실용적입니다. 한 가지 이유는 특성 다항식 계수의 작은 반-올림 오차(round-off errors)가 고윳값과 고유벡터에서 큰 오차로 이어질 수 있다는 것입니다: 근은 계수의 조건이 극단적으로 나쁜-조건된(ill-conditioned) 함수입니다.

간단하고 정확한 반복 방법은 거듭제곱 방법(power method)입니다: 무작위(random) 벡터 v가 선택되고 단위 벡터(unit vectors)의 수열이 다음과 같이 계산됩니다:

${\frac {\mathbf {A} \mathbf {v} }{\left\|\mathbf {A} \mathbf {v} \right\|}},{\frac {\mathbf {A} ^{2}\mathbf {v} }{\left\|\mathbf {A} ^{2}\mathbf {v} \right\|}},{\frac {\mathbf {A} ^{3}\mathbf {v} }{\left\|\mathbf {A} ^{3}\mathbf {v} \right\|}},\ldots$

이 수열(sequence)은 거의 항상(almost always) 가장 큰 크기의 고윳값에 해당하는 고유벡터로 수렴하며, v가 고유벡터 기저에서 이 고유벡터의 비-영 구성 요소를 가진다는 조건으로 합니다 (그리고 역시 가장 큰 크기의 고윳값이 하나만 있다는 조건으로 합니다). 이 간단한 알고리듬은 일부 실제 응용에서 유용합니다; 예를 들어 Google은 이를 사용하여 검색 엔진에서 문서의 페이지 순위를 계산합니다. 역시, 거듭제곱 방법은 많은 더 정교한 알고리듬의 출발점입니다. 예를 들어, 수열에서 마지막 벡터만 유지하는 것이 아니라 수열에서 모든 벡터의 스팬(span)을 살펴봄으로써, 고유벡터에 대해 더 나은 (더 빠른 수렴) 근사를 얻을 수 있고, 이 아이디어는 아르놀디 반복(Arnoldi iteration)의 기초입니다. 대안적으로, 중요한 QR 알고리듬도 거듭제곱 방법의 미묘한 변환을 기반으로 합니다.

Numerical computation of eigenvectors

한 번 고윳값이 계산되면, 고유벡터는 다음 방정식을 풂으로써 계산될 수 있습니다:

$\left(\mathbf {A} -\lambda _{i}\mathbf {I} \right)\mathbf {v} _{i,j}=\mathbf {0}$

이때 행렬 방정식을 푸는 데 가우스 소거법(Gaussian elimination) 또는 임의의 다른 방법을 사용합니다.

어쨌든, 실제 큰-스케일 고윳값 방법에서, 고유벡터는 보통 고윳값 계산의 부산물로 다른 방법에서 계산됩니다. 거듭제곱 반복(power iteration)에서, 예를 들어, 고유벡터는 실제로 고윳값 (전형적으로 고유벡터의 레일리 몫(Rayleigh quotient)으로 계산됨)보다 먼저 계산됩니다. 에르미트 행렬 (또는 임의의 정규 행렬)에 대한 QR 알고리듬에서, 직교정규 고유벡터는 알고리듬에서 단계로부터 Q 행렬의 곱으로 얻습니다. (보다 일반적인 행렬에 대해, QR 알고리듬은 슈어 분해(Schur decomposition)를 먼저 생성하며, 이로부터 역대입(backsubstitution) 절차를 통해 고유벡터를 얻을 수 있습니다.) 에르미트 행렬에 대해, 분할-과-정복 고윳값 알고리듬(Divide-and-conquer eigenvalue algorithm)이 만약 고유벡터와 고윳값 둘 다가 필요하면 QR 알고리듬보다 더 효율적입니다.

Additional topics

Generalized eigenspaces

고윳값의 기하적 중복도는 결합된 고유공간의 차원, λI − A의 널공간(nullspace)으로 설명될 수 있음을 상기하십시오. 대수적 중복도는 역시 차원으로 생각할 수 있습니다: 그것은 임의의 충분하게 큰 k에 대한 행렬 (λI − A)^k의 널공간인 결합된 일반화된 고유공간(generalized eigenspace) (첫 번째 의미)의 차원입니다. 즉, 그것은 일반화된 고유벡터 (첫 번째 의미)의 공간이며, 여기서 일반화된 고유벡터는 λI − A가 충분하게 여러번 연속적으로 적용되면 결국 0이 되는 임의의 벡터입니다. 임의의 고유벡터는 일반화된 고유벡터이고, 따라서 각 고유공간은 결합된 일반화된 고유공간에 포함됩니다. 이것은 기하적 중복도가 대수적 중복도보다 항상 작거나 같다는 쉬운 증명을 제공합니다.

이 사용법은 아래에 설명된 일반화된 고윳값 문제(generalized eigenvalue problem)와 혼동해서는 안 됩니다.

Conjugate eigenvector

켤레 고유벡터(conjugate eigenvector 또는 coneigenvector)는 그것의 켤레의 스칼라 배수로 변환한 후 전송되는 벡터이며, 여기서 스칼라는 선형 변환의 켤레 고윳값(conjugate eigenvalue 또는 coneigenvalue)라고 불립니다. 켤레 고유벡터와 켤레 고윳값은 본질적으로 일반 고유벡터와 고윳값과 같은 정보와 의미를 나타내지만, 대안적인 좌표 시스템이 사용될 때 발생합니다. 해당 방정식은 다음과 같습니다:

$\mathbf {A} \mathbf {v} =\lambda \mathbf {v} ^{*}.$

예를 들어, 간섭성 전자기 산란 이론에서, 선형 변환 A는 산란 물체에 의해 수행되는 동작을 나타내고, 고유벡터는 전자기 파동의 편광 상태를 나타냅니다. 광학에서, 좌표 시스템은 전방 산란 정렬(Forward Scattering Alignment, FSA)로 알려진 파동의 관점에서 정의되고, 정규 고윳값 방정식을 생성하고, 반면 레이더에서, 좌표 시스템은 후방 산란 정렬(Back Scattering Alignment, BSA)로 알려진 레이더 관점에서 정의되고, 켤레 고윳값 방정식을 생성합니다.

Generalized eigenvalue problem

일반화된 고윳값 문제 (두 번째 의미)는 다음을 준수하는 (비-영) 벡터 v를 찾는 문제입니다:

$\mathbf {A} \mathbf {v} =\lambda \mathbf {B} \mathbf {v}$

여기서 A와 B는 행렬입니다. 만약 v가 어떤 λ와 함께 이 방정식을 따른다면, 우리는 v를 (두 번째 의미에서) A와 B의 일반화된 고유벡터라고 부르고, λ는 일반화된 고유벡터 v에 해당하는 (두 번째 의미에서) A와 B의 일반화된 고윳값이라고 부릅니다. λ의 가능한 값은 다음 방정식을 따라야 합니다:

$\det(\mathbf {A} -\lambda \mathbf {B} )=0.$

만약 n 선형적으로 독립 벡터 {v₁, …, v_n}가 모든 각 i ∈ {1, …, n}에 대해, Av_i = λ_iBv_i임을 만족하도록 구할 수 있으면, 우리는 다음임을 만족하는 행렬 P와 D를 정의합니다:

$P={\begin{bmatrix}|&&|\\\mathbf {v} _{1}&\cdots &\mathbf {v} _{n}\\|&&|\end{bmatrix}}\equiv {\begin{bmatrix}(\mathbf {v} _{1})_{1}&\cdots &(\mathbf {v} _{n})_{1}\\\vdots &&\vdots \\(\mathbf {v} _{1})_{n}&\cdots &(\mathbf {v} _{n})_{n}\end{bmatrix}}$

$(D)_{ij}={\begin{cases}\lambda _{i},&{\text{if }}i=j\\0,&{\text{otherwise}}\end{cases}}$

그런-다음 다음과 등식이 유지됩니다:

$\mathbf {A} =\mathbf {B} \mathbf {P} \mathbf {D} \mathbf {P} ^{-1}$

그리고 증명은 다음과 같습니다:

$\mathbf {A} \mathbf {P} =\mathbf {A} {\begin{bmatrix}|&&|\\\mathbf {v} _{1}&\cdots &\mathbf {v} _{n}\\|&&|\end{bmatrix}}={\begin{bmatrix}|&&|\\A\mathbf {v} _{1}&\cdots &A\mathbf {v} _{n}\\|&&|\end{bmatrix}}={\begin{bmatrix}|&&|\\\lambda _{1}B\mathbf {v} _{1}&\cdots &\lambda _{n}B\mathbf {v} _{n}\\|&&|\end{bmatrix}}={\begin{bmatrix}|&&|\\B\mathbf {v} _{1}&\cdots &B\mathbf {v} _{n}\\|&&|\end{bmatrix}}\mathbf {D} =\mathbf {B} \mathbf {P} \mathbf {D}$

그리고 P가 역가능이기 때문에, 방정식의 오른쪽에 역을 곱하여, 증명을 마칩니다.

형식 A − λB의 행렬의 집합은, 여기서 λ는 복소수이며, 연필(pencil)이라고 불립니다; 행렬 연필(matrix pencil)이라는 용어는 행렬의 쌍 (A, B)을 참조할 수도 있습니다.

만약 B가 역가능이면, 원래 문제는 다음 형식으로 쓸 수 있습니다:

$\mathbf {B} ^{-1}\mathbf {A} \mathbf {v} =\lambda \mathbf {v}$

이는 표준 고윳값 문제입니다. 어쨌든, 대부분의 상황에서 반전을 수행하지 않고, 원래 설명한 대로 일반화된 고윳값 문제를 해결하는 것이 좋습니다. 이것은 A와 B가 에르미트 행렬(Hermitian matrices)이면 특히 중요한데, 왜냐하면 이 경우에서 B⁻¹A는 일반적으로 에르미트가 아니고 해의 중요한 속성이 더 이상 명확하지 않기 때문입니다.

만약 A와 B가 둘 다 대칭 또는 에르미트이고, B가 역시 야수-한정 행렬(positive-definite matrix)이면, 고윳값 λ_i는 실수이고 구별되는 고윳값을 갖는 고유벡터 v₁과 v₂는 B-직교 (v₁^*Bv₂ = 0)입니다. 이 경우에서, 고유벡터는 위에 정의된 행렬 P가 다음임을 만족하고 일반화된 고유벡터의 기저(basis)가 존재 (이는 결함-있는 문제가 아님)하도록 선택될 수 있습니다:

$\mathbf {P} ^{*}\mathbf {B} \mathbf {P} =\mathbf {I}$ or $\mathbf {P} \mathbf {P} ^{*}\mathbf {B} =\mathbf {I}$,

이 경우는 때때로 에르미트 한정 연필(Hermitian definite pencil) 또는 한정 연필(definite pencil)이라고 불립니다.

See also

• Eigenvalue perturbation
• Frobenius covariant
• Householder transformation
• Jordan normal form
• List of matrices
• Matrix decomposition
• Singular value decomposition
• Sylvester's formula

References

• Franklin, Joel N. (1968). Matrix Theory. Dover Publications. ISBN 978-0-486-41179-8.
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins University Press, ISBN 978-0-8018-5414-9
• Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. ISBN 978-0-521-38632-6.
• Horn, Roger A.; Johnson, Charles R. (1991). Topics in Matrix Analysis. Cambridge University Press. ISBN 978-0-521-46713-1.
• Kreyszig, Erwin (1972), Advanced Engineering Mathematics (3rd ed.), New York: Wiley, ISBN 978-0-471-50728-4
• Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd ed.), New York: Wiley, LCCN 76091646
• Strang, G. (1998). Introduction to Linear Algebra (3rd ed.). Wellesley-Cambridge Press. ISBN 978-0-9614088-5-5.

External links

• Interactive program & tutorial of Spectral Decomposition.