Trị riêng và vector riêng

Bài 1: QR decomposition
Bài 2: Trị riêng và vector riêng
Bài 3: Bài toán tìm trị riêng
Bài 4: Thuật toán QR

Trị riêng (eigenvalue) và vector riêng (eigenvector) là những vấn đề hết sức cơ bản trong Đại số tuyến tính. Bài này sẽ nhắc lại về khái niệm trị riêng, vector riêng cùng một số kết quả liên quan. Những kiến thức này là cơ bản và sẽ được sử dụng nhiều trong các bài tiếp theo. Cuối bài sẽ đề cập đến một số phương pháp phân tích ma trận bao gồm phân tích trị riêng (eigendecomposition), chéo hóa (diagonalization) và phân tích Schur. Phân tích Schur là nền tảng của các thuật toán tính trị riêng của ma trận.

1. Trị riêng và vector riêng

Cho A \in \mathbb{C}^{m\times m} là ma trận vuông. Một vector x \in \mathbb{C}^m, x \neq 0  gọi là vector riêng của A, và \lambda \in \mathbb{C}  là trị riêng tương ứng, nếu

\displaystyle Ax = \lambda x.               (1)

Dễ thấy rằng nếu x là vector riêng của A với trị riêng \lambda, thì với mọi giá trị vô hướng \alpha \neq 0 ta có \alpha x cũng là vector riêng của A ứng với trị riêng \lambda. Hơn thế nữa, mọi tổ hợp tuyến tính của các vector riêng, ứng với trị riêng \lambda, cũng tạo thành vector riêng của A ứng với trị riêng đó. Tất cả những vector riêng có cùng trị riêng, cùng với vector 0, tạo thành không gian riêng (eigenspace), kí hiệu E_\lambda. Nói cách khác, E_\lambda cũng chính là không gian nghiệm (nullspace) của phương trình \left(\lambda I - A\right)x = 0. Nhận xét rằng không gian E_\lambda là không gian con của \mathbb{C}^m.

Ý tưởng ở đây là đôi khi tác động của ma trận A lên không gian con nào đó của \mathbb{C}^m (trong trường hợp này là E_\lambda) có thể biểu diễn đơn giản bằng một phép nhân vô hướng.

Với trị riêng \lambda và không gian riêng E_\lambda thì AE_\lambda \subseteq E_\lambda. E_\lambda là một ví dụ của không gian con bất biến (invariant subspace) của A.

Tương tự, tập các trị riêng của A là tập con của \mathbb{C}, kí hiệu \Lambda\left(A\right).

2. Đa thức đặc trưng

Đa thức đặc trưng (characteristic polynomial) của ma trận A\in \mathbb{C}^{m\times m}, kí hiệu p_A là đa thức bậc m định nghĩa như sau:

\displaystyle p_A\left(z\right) = det\left(zI-A\right)                         (2)

Định lí 2.1. \lambda là trị riêng của A khi và chỉ khi p_A\left(\lambda\right) = 0.

Chứng minh:

\lambda là trị riêng của A

\Leftrightarrow tồn tại vector x khác zero sao cho \lambda x - Ax = 0

\Leftrightarrow phương trình \left(\lambda I - A\right) x = 0 có một nghiệm khác 0

\Leftrightarrow phương trình \left(\lambda I - A\right) x = 0 có vô số nghiệm

\Leftrightarrow det\left(zI-A\right) = 0 (đpcm)

Theo kết quả định lí cơ bản của Đại số (kết hợp với Định lí Bezout), mọi đa thức bậc m đều có đúng m nghiệm, nên p_A có thể viết lại như sau

\displaystyle p_A\left(z\right) = \left(z - \lambda_1\right)\left(z - \lambda_2\right)...\left(z - \lambda_m\right)                            (3)

trong đó \lambda_i \in \mathbb{C}. Như vậy ta thấy một ma trận thực cũng hoàn toàn có thể có các trị riêng ảo.

Theo định lí 2.1 thì mỗi \lambda_i là một trị riêng của A. Nếu trị riêng \lambda xuất hiện k lần trong (3) thì ta gọi \lambdatrị riêng bội k của A. Nếu k = 1 thì \lambdatrị riêng đơn. Người ta gọi khệ số đại số của \lambda (xem phần 3). Từ đó ta có định lí sau:

Định lí 2.2. Ma trận A\in\mathbb{C}^{m\times m} có đúng m trị riêng (đếm cả những trị riêng bội). Nếu đa thức đặc trưng của Am nghiệm phân biệt thì Am trị riêng phân biệt.

3. Hệ số hình học và hệ số đại số của trị riêng

Với mỗi trị riêng \lambda_i của A, có 2 hệ số (multiplicity – không biết dùng từ nào phù hợp hơn) đặc trưng cho nó là hệ số hình học (geometric multiplicity) và hệ số đại số (algebraic multiplicity).

Hệ số hình học của trị riêng \lambda là số chiều của không gian riêng E_\lambda tương ứng: dimE_\lambda. Nói cách khác đó chính là số lượng tối đa các vector riêng độc lập tuyến tính, ứng với trị riêng \lambda cho trước.

Hệ số đại số của trị riêng \lambda là số bội của \lambda, đó chính là số lần xuất hiện của \lambda trong phương trình đa thức đặc trưng (3).

Ta có định lí sau:

Định lí 3.1. Cho ma trận A \in \mathbb{C}^{m\times m}. Khi đó:

i) Nếu \lambda là trị riêng bội k của A thì 1 \leq dimE_\lambda \leq k, nói cách khác hệ số đại số của trị riêng luôn lớn hơn hay bằng hệ số hình học của nó.

ii) Nếu \lambda, \lambda ' là 2 trị riêng khác nhau của A thì E_\lambda \bigcap E_{\lambda '} = \{0\}.

Phần thứ nhất của định lí kéo theo hệ quả là nếu \lambda là trị riêng đơn thì dimE_\lambda = 1.

4. Biến đổi tương đương

Cho ma trận khả nghịch X\in \mathbb{C}^{m\times m}, khi đó phép biến đổi A \mapsto X^{-1}AX gọi là biến đổi tương đương (similarity transformation). Hai ma trận A và B gọi là tương đương (similar) nếu tồn tại ma trận khả nghịch X sao cho B = X^{-1}AX. Hai ma trận tương đương AX^{-1}AX có rất nhiều điểm chung. Ta nhấn mạnh bằng định lí sau

Định lí 4.1. Nếu X là ma trận khả nghịch thì AX^{-1}AX có cùng đa thức đặc trưng, trị riêng, và các trị riêng cũng có cùng hệ số hình học và hệ số đại số.

Định lí được chứng minh đơn giản bằng phép tính p_{X^{-1}AX}\left(z\right)=det\left(zI - X^{-1}AX\right).

Ngoài ra 2 ma trận tương đương còn có cùng hạng, định thức, trace.

5. Eigenvalue decomposition

Gọi \Lambda = diag\left(\lambda_1, \lambda_2, ..., \lambda_m\right), \Lambda \in \mathbb{C}^{m\times m} là ma trận đường chéo tạo bởi các trị riêng của A.

Với mỗi \lambda_j, gọi x_j là vector riêng tương ứng, khi đó Ax_j=\lambda_j x_j. Như vậy ta viết:

\displaystyle \Biggl[\begin{array}{c}A\end{array}\Biggr]\Biggl[\begin{array}{c|c|c|c}x_1&x_2&\dotsb&x_m\end{array}\Biggr]=\Biggl[\begin{array}{c|c|c|c}x_1&x_2&\dotsb&x_m\end{array}\Biggr]\left[\begin{array}{cccc}\lambda_1&\;&\;&\;\\\;&\lambda_2&\;&\;\\\;&\;&\ddots&\;\\\;&\;&\;&\lambda_m\end{array}\right]           (4)

Hay ngắn gọn hơn:

AX = X\Lambda              (5)

Trong đó \Lambda \in \mathbb{C}^{m\times m} là ma trận đường chéo chứa các trị riêng của A, X \in \mathbb{C}^{m\times m} là ma trận mà cột thứ j là vector riêng ứng với trị riêng \lambda_j.

Trong trường hợp X khả nghịch (nghĩa là khi Am vector riêng độc lập tuyến tính), ta có thể viết lại (5) như sau:

A = X\Lambda X^{-1}             (6)

Đây gọi là phân tích trị riêng (Eigenvalue decomposition, Eigendecomposition) của A. Lưu ý rằng không phải lúc nào cũng tồn tại phép phân tích này, nó chỉ tồn tại khi Am vector riêng độc lập tuyến tính.

Từ phương trình (6) ta thấy hai trong số nhiều ứng dụng của trị riêng, đó là tính lũy thừa của ma trận và tính ma trận nghịch đảo. Chi tiết trong phần 8.

6. Diagonalization

Trong trường hợp A có phân tích trị riêng, ta thấy ma trận \Lambda là ma trận đường chéo, nghĩa là ta có thể biểu diễn ma trận A dưới dạng ma trận đường chéo \lambda của các trị riêng.

Tổng quát hơn nếu tồn tại phép biến đổi P sao cho A = P^{-1}QP với  Q là ma trận đường chéo thì A gọi là chéo hóa được (diagonalizable), Q gọi là dạng chéo của A và P gọi là ma trận làm chéo A.

Ta có kết quả sau:

Định lí 6.1. Ma trận A\in \mathbb{C}^{m\times m} chéo hóa được khi và chỉ khi mọi trị riêng của nó đều có hệ số đại số bằng hệ số hình học.

Một cách dễ hiểu hơn, nếu A có k trị riêng \lambda_1, \lambda_2,\ldots,\lambda_k đôi một khác nhau (k \leq m) lần lượt là trị riêng bội r_1, r_2, \ldots, r_k thì đa thức đặc trưng của A có thể viết:

p_A\left(z\right) = \left(z - \lambda_1\right)^{r_1}\left(z - \lambda_2\right)^{r_2}\ldots\left(z - \lambda_k\right)^{r_k}               (7)

Khi đó, A chéo hóa được khi và chỉ khi dimE_{\lambda_i} = r_i, \forall i \leq k. (Người ta cũng dùng khái niệm nondefective để chỉ các ma trận chéo hóa được).

Đôi khi đối với ma trận A \in \mathbb{C}^{m\times m}, ta không những tìm được m vector riêng độc lập tuyến tính, mà còn có thể chọn sao cho chúng trực giao với nhau. Khi đó A gọi là chéo hóa được đơn vị (unitarily diagonalizable), nghĩa là tồn tại ma trận đơn vị Q sao cho:

A = Q\Lambda Q*              (8)

Nhắc lại rằng Q là ma trận đơn vị (unitary matrix) khi và chỉ khi nghịch đảo của nó bằng với ma trận chuyển vị liên hợp (conjugate transpose) của nó: Q^{-1} = Q^*, nghĩa là QQ^* = Q^*Q = I_n. Cần phân biệt ma trận unitary và ma trận identity I_n.

Điều thú vị là khi đó, phép phân tích này vừa là phân tích trị riêng (eigendecomposition), vừa là SVD, nếu như các phần tử trên \Lambda đều là số thực không âm.

Liên quan đến các ma trận chéo hóa được đơn vị, ta có thể hỏi những ma trận nào là ma trận đơn vị. Câu trả lời nằm trong kết quả định lí sau:

Định lí 6.2. Một ma trận A là chéo hóa được đơn vị khi và chỉ khi A*A = AA*.

Các ma trận A thỏa A*A = AA* được gọi là ma trận chuẩn (normal matrix). Như vậy mọi ma trận unitary đều là ma trận chuẩn.

Ma trận hermitian là ma trận chuẩn nên mọi ma trận hermitian đều chéo hóa được đơn vị. (nhắc lại rằng  A là ma trận hermitian nếu và chỉ nếu A = A*).

7. Phân tích Schur

Một trong những phép phân tích ma trận hay được dùng nhất trong ĐSTT là phân tích Schur, với lí do mọi ma trận vuông đều có phân tích Schur.

Theo định nghĩa, phân tích Schur (Schur factorization) của ma trận A là

A = QTQ^*          (9)

trong đó Q là ma trận unitary và T là ma trận tam giác trên. Để ý rằng do T và A là 2 ma trận tương đương nên các trị riêng của A nằm trên đường chéo của T. Ngoài ra, do T là tam giác trên nên ta cũng gọi đây là phép phân tích tam giác hóa đơn vị (unitary triagularization)

Ta nhấn mạnh tầm quan trọng của phân tích Schur bằng định lí sau:

Định lí 7.1. Mọi ma trận vuông đều có phân tích Schur.

Tóm lại, trong bài này ta đã xét đến 3 phép phân tích ma trận. Điểu đặc biệt là sau 3 phép phân tích này, các trị riêng của ma trận ban đầu đều xuất hiện trên đường chéo của ma trận phân tích được. Bao gồm:

  1. Chéo hóa A = X\Lambda X^{-1}, tồn tại khi và chỉ khi A chéo hóa được (xem định lí 5.1)
  2. Chéo hóa đơn vị A = Q\Lambda Q^*, tồn tại khi và chỉ khi A là ma trận chuẩn (AA* = A*A)
  3. Tam giác hóa đơn vị (Schur factorization) A = QTQ^*, luôn luôn tồn tại.

Để tìm các trị riêng, ta sẽ tìm cách thực hiện các phân tích này. Nhìn chung phân tích Schur được sử dụng do nó tồn tại với ma trận A bất kì. Nếu A là ma trận chuẩn thì kết quả của Schur factorization sẽ là ma trận đường chéo.

8. Ứng dụng của trị riêng và vector riêng

Trị riêng và vector riêng là vấn đề hấp dẫn trong numerical linear algebra một phần vì các thuật toán tìm trị riêng rất hiệu quả nhưng lại có tư tưởng ít tự nhiên. Ngoài lí do này thì cũng phải kể đến ứng dụng rộng rãi của chúng trong rất nhiều bài toán khác nhau. Phần này chỉ liệt kê một vài ứng dụng tiêu biểu.

  1. Định thức của A bằng tích các trị riêng: det(A)=\prod_{i=1}^k \lambda_i^{r_i}
  2. Trace của A bằng tổng các trị riêng: trace(A) = \sum_{i=1}^k r_i\lambda_i
  3. Nếu \lambda_i là các trị riêng của A thì các trị riêng của A^{-1}\lambda_i^{-1}. Các vector riêng của A cũng là vector riêng của A^{-1}.
  4. Ma trận A nghịch đảo không có nghĩa là nó có thể phân tích trị riêng, và ngược lại. Nói cách khác, hai khái niệm nghịch đảo và eigendecomposition (diagonalization) không tương đương nhau.
  5. Nếu A chéo hóa được và có biểu diễn A = X\Lambda X^{-1} thì
    A^k = X\Lambda^kX^{-1}, và
    A^{-1} = X\Lambda^{-1} X^{-1}
    Do \Lambda là ma trận đường chéo nên việc tính \Lambda^k là rất dễ dàng.

Bài này nêu lại một số vấn đề về trị riêng và vector riêng. Các bài sau sẽ viết về thuật toán hiệu quả tìm trị riêng.

About these ads

19 Responses to “Trị riêng và vector riêng”

  1. Chào anh,
    Cám ơn anh rất nhiều về loạt bài viết về phân tích ma trận và về trị riêng rất hữu ích. Em thấy bài viết của anh rất gần gũi và dễ hiểu. Nhưng có một vấn đề em chưa hiểu (có lẽ là rất cơ bản :P), đó là tính chất của các eigenvector, nó quan trọng như thế nào, nhất là trong tìm các thành phần liên thông của đồ thị và graph partioning. Nhờ anh giải thích dùm.

  2. Chào Tú,
    Tính chất cơ bản của eigenvector thì như mình nói, những eigenvector của 1 một eigenvalue, cùng với nhau, tạo thành một không gian con mà trên đó tác dụng của ma trận A có thể được “bắt chước” chỉ bằng phép nhân với 1 giá trị vô hướng.
    Nó “quan trọng như thế nào” thì tùy ngữ cảnh thôi :D Những ứng dụng nào dùng nó thì xem nó là quan trọng.
    Trong bài toán cụ thể là tìm thành phần liên thông và phân hoạch đồ thị thì eigenvector là 1 trong các phương pháp đang được dùng, vậy thôi :D

  3. anh có thể viết cho em mot đoạn code cho trị riêng vector riêng trong matlab dc ko
    em biết cách giải tay nhưng viết đoạn code em ko biết

  4. Hi em,
    Trong MATLAB em dùng hàm eig() để tính trị riêng và vector riêng nhé. Chi tiết ở đây: http://www.mathworks.com/help/techdoc/ref/eig.html

  5. Chào bạn,
    Bài viết của bạn rất hay. Bạn có thể viết bài hoặc cho link bài viết về chéo hóa ma trận dùng phép quay Givens không?

  6. Chào bạn,
    Bài viết của bạn rất hay. Bạn có thể viết bài hoặc cho link về chéo hóa ma trận dùng phép quay Givens không? Cảm ơn bạn.

  7. anh vũ cho em hỏi trong phương pháp SVD, singular value và singular vector có thể dịch là giá trị đơn, vecto đơn không anh?

    • Hi em,

      Hình như ở VN, “singular” thuờng được dịch là “suy biến”, nên e có thể gọi là “trị suy biến” và “vector suy biến”.

      Nhưng anh nghĩ tốt nhất là cứ dùng tên gốc của nó :)

  8. Anh Vũ ơi!
    A có code matlab của phương pháp danhislepky không ạ. Em hiểu về thuật toán nhưng code em mắc. Anh có thể giúp em được khong ạ.
    Cảm ơn anh nhiều!

  9. Chào bạn . cảm ơn bạn về bài viết của bạn . mình đang loay hoay tìm vector riêng bằng C hoặc C++ bạn có thể giúp mình được ko ? cảm ơn bạn rất nhiều

Trackbacks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 59 other followers

%d bloggers like this: