Bài giảng 20: Ước Lượng Lặp Cho Giá Trị Riêng

(Nếu công thức chưa load được hoặc mờ, các bạn ấn refresh để công thức hiện và rõ nét hơn nhé!)

Trong các ứng dụng khoa học của đại số tuyến tính, giá trị riêng hiếm khi được biết chính xác. May mắn thay, một xấp xỉ số gần đúng thường là đủ. Thực tế, một số ứng dụng chỉ cần một xấp xỉ thô của giá trị riêng lớn nhất. Thuật toán đầu tiên được mô tả dưới đây có thể hoạt động tốt trong trường hợp này. Ngoài ra, nó cung cấp nền tảng cho một phương pháp mạnh mẽ hơn có thể đưa ra các ước lượng nhanh cho các giá trị riêng khác.

Phương Pháp Lũy Thừa

Phương pháp lũy thừa áp dụng cho một ma trận $n\times n$ có một giá trị riêng trội tuyệt đối $\lambda_1$ , nghĩa là $\lambda_1$ có giá trị tuyệt đối lớn hơn tất cả các giá trị riêng khác. Trong trường hợp này, phương pháp lũy thừa tạo ra một dãy số hội tụ đến $\lambda_1$ và một dãy vector hội tụ đến một vector riêng tương ứng.

Nền tảng của phương pháp dựa trên phân rã vector riêng được sử dụng ở bài trước. Giả sử đơn giản rằng $A$ là ma trận chéo hóa được và không gian $\mathbb{R}^n$ có một cơ sở các vector riêng $\mathbf{v}_1,...,\mathbf{v}_n$ , được sắp xếp sao cho các giá trị riêng tương ứng $\lambda_1,...,\lambda_n$ giảm dần về độ lớn, với $\lambda_1$ là giá trị riêng trội tuyệt đối đầu tiên. Nghĩa là:

(1) $\begin{equation*}|\lambda_1|>|\lambda_2|\geq|\lambda_3|\geq...\geq|\lambda_n|\end{equation*}$

Như chúng ta đã biết, nếu $\mathbf{x}$ trong $\mathbb{R}^n$ được viết dưới dạng: $\mathbf{x}=c_1\mathbf{v}_1+\dots+c_n\mathbf{v}_n$ , thì

$A^k\mathbf{x}=c_1(\lambda_1)^k\mathbf{v}_1+c_2(\lambda_2)^k\mathbf{v}_2+\dots+c_n(\lambda_n)^k\mathbf{v}_n\quad(k=1,2,\dots)$

Giả sử $c_1\neq 0$ . Chia cả hai vế cho $(\lambda_1)^k$ , ta có:

(2) $\begin{equation*}\frac{1}{(\lambda_1)^k}A^k\mathbf{x}=c_1\mathbf{v}_1+c_2\left(\frac{\lambda_2}{\lambda_1}\right)^k\mathbf{v}_2+\dots+c_n\left(\frac{\lambda_n}{\lambda_1}\right)^k\mathbf{v}_n\quad(k=1,2,\dots)\end{equation*}$

Từ bất đẳng thức (1), các tỉ số ${\lambda_2}/{\lambda_1},\dots,{\lambda_n}/{\lambda_1}$ đều có độ lớn nhỏ hơn 1, do đó lũy thừa của chúng tiến về 0. Do đó:

(3) $\begin{equation*}(\lambda_1)^{-k}A^k\mathbf{x}\to c_1\mathbf{v}_1\quad\text{khi}\:k\to\infty\end{equation*}$

Vậy, với $k$ lớn, một bội vô hướng của $A^k\mathbf{x}$ xác định gần như cùng hướng với vector riêng $\mathbf{v}_1$ . Vì các bội vô hướng dương không làm thay đổi hướng của vector, nên $A^k\mathbf{x}$ sẽ gần như cùng hướng với $\mathbf{v}_1$ hoặc $-\mathbf{v}_1$ , miễn là $c_1\neq 0$ .

Ví dụ 1: Cho $A=\begin{bmatrix}1.8&.8\\.2&1.2\end{bmatrix},\,\mathbf{v}_1=\begin{bmatrix}4\\1\end{bmatrix}$ và $\mathbf{x}=\begin{bmatrix}-.5\\1\end{bmatrix}$ . Khi đó, $A$ có các giá trị riêng là 2 và 1, và không gian riêng ứng với $\lambda_1=2$ là đường thẳng đi qua 0 và $\mathbf{v}_1$ . Với $k=0,\dots,8$ , hãy tính $A^k\mathbf{x}$ và xác định đường thẳng đi qua 0 và $A^k\mathbf{x}$ . Điều gì xảy ra khi $k$ tăng?

Giải: Ba phép tính đầu tiên là:

$\begin{matrix}&A\mathbf{x}&=\begin{bmatrix}1.8&.8\\.2&1.2\\\end{bmatrix}\begin{bmatrix}-.5\\1\end{bmatrix}&=\begin{bmatrix}-1\\1.1\end{bmatrix}\\\\A^{2}\mathbf{x}=&A(A\mathbf{x})&=\begin{bmatrix}1.8&.8\\.2&1.2\\\end{bmatrix}\begin{bmatrix}-1\\1.1\end{bmatrix}&=\begin{bmatrix}.7\\1.3\end{bmatrix}\\\\A^{3}\mathbf{x}=&A(A^{2}\mathbf{x})&=\begin{bmatrix}1.8&.8\\.2&1.2\\\end{bmatrix}\begin{bmatrix}.7\\1.3\end{bmatrix}&=\begin{bmatrix}2.3\\1.7\end{bmatrix}\\\end{matrix}$

Các phép tính tương tự hoàn thành Bảng 1.

Bảng 1: Các lần lặp của một vector.

$k$	$\mathbf{0}$	$\mathbf{1}$	$\mathbf{2}$	$\mathbf{3}$	$\mathbf{4}$	$\mathbf{5}$	$\mathbf{6}$	$\mathbf{7}$	$\mathbf{8}$
$A^{k}\mathbf{x}$	$\begin{bmatrix}-.5\\1\end{bmatrix}$	$\begin{bmatrix}-.1\\1.1\end{bmatrix}$	$\begin{bmatrix}.7\\1.3\end{bmatrix}$	$\begin{bmatrix}2.3\\1.7\end{bmatrix}$	$\begin{bmatrix}5.5\\2.5\end{bmatrix}$	$\begin{bmatrix}11.9\\4.1\end{bmatrix}$	$\begin{bmatrix}24.7\\7.3\end{bmatrix}$	$\begin{bmatrix}50.3\\13.7\end{bmatrix}$	$\begin{bmatrix}-101.5\\26.5\end{bmatrix}$

Các vector $\mathbf{x},A\mathbf{x},\dots,A^4\mathbf{x}$ được hiển thị trong hình 1. Các vector khác trở nên quá dài để hiển thị, tuy nhiên, các đoạn thẳng được vẽ để hiển thị hướng của các vector đó. Thực tế, điều chúng ta thực sự muốn quan sát là hướng của các vector, không phải bản thân các vector. Các đường này dường như đang tiến gần đến đường biểu diễn không gian riêng được tạo bởi $\mathbf{v}_1$ .

Chính xác hơn, góc giữa đường (dưới không gian) được xác định bởi $A^k\mathbf{x}$ và đường (không gian riêng) được xác định bởi $\mathbf{v}_1$ tiến dần về 0 khi $k\to\infty$ .

Hình 1: Các hướng được xác định bởi $\mathbf{x},A\mathbf{x},A^2\mathbf{x},\dots,A^7\mathbf{x}$

Hình 1: Các hướng được xác định bởi $\mathbf{x},A\mathbf{x},A^2\mathbf{x},\dots,A^7\mathbf{x}$

Các vector $(\lambda_1)^{-k}A^k\mathbf{x}$ trong phương trình (3) được chia tỷ lệ để làm chúng hội tụ đến $c_1\mathbf{v}_1$ , với điều kiện $c_1\neq 0$ . Chúng ta không thể chia tỷ lệ $A^k\mathbf{x}$ theo cách này vì không biết $\lambda_1$ . Nhưng có thể chia tỷ lệ từng $A^k\mathbf{x}$ để giá trị lớn nhất của nó bằng 1. Kết quả là dãy $\{\mathbf{x}_k\}$ sẽ hội tụ đến một bội số của $\mathbf{v}_1$ mà giá trị lớn nhất bằng 1.

Hình 2 hiển thị dãy được chia tỷ lệ trong ví dụ 1. Giá trị riêng $\lambda_1$ cũng có thể được ước lượng từ dãy $\{\mathbf{x}_k\}$ .

Hình 2: Các bội được chuẩn hóa của $\mathbf{x},A\mathbf{x},A^2\mathbf{x},\dots,A^7\mathbf{x}$

Khi $\mathbf{x}_k$ gần với một vector riêng của $\lambda_1$ , vector $A\mathbf{x}_k$ sẽ gần với $\lambda_1\mathbf{x}_k$ , với mỗi phần tử trong $A\mathbf{x}_k$ xấp xỉ bằng $\lambda_1$ lần phần tử tương ứng trong $\mathbf{x}_k$ . Vì phần tử lớn nhất trong $\mathbf{x}_k$ là 1, nên phần tử lớn nhất trong $A\mathbf{x}_k$ sẽ gần bằng $\lambda_1$ .

PHƯƠNG PHÁP LŨY THỪA ĐỂ ƯỚC LƯỢNG GIÁ TRỊ RIÊNG ƯU THẾ

Chọn một vector ban đầu $\mathbf{x}_0$ sao cho phần tử lớn nhất của nó bằng 1.
Với $k=0,1,\dots,$
a. Tính $A\mathbf{x}_k$ .
b. Chọn $\lambda_k$ là một phần tử trong $A\mathbf{x}_k$ có giá trị tuyệt đối lớn nhất.
c. Tính $\mathbf{x}_{k+1}=({1}/{\mu _k})A\mathbf{x}_k$ .
Với hầu hết các lựa chọn của $\mathbf{x}_0$ , dãy $\{\mu _k\}$ sẽ tiến dần đến giá trị riêng ưu thế, và dãy $\{\mathbf{x}_k\}$ sẽ tiến đến một vector riêng tương ứng.

Ví dụ 2: Áp dụng phương pháp lũy thừa cho $A=\begin{bmatrix}6&5\\1&2\end{bmatrix}$ với $\mathbf{x}_0=\begin{bmatrix}0\\1\end{bmatrix}$ . Dừng lại khi $k=5$ và ước lượng giá trị riêng ưu thế cùng với một vector riêng tương ứng của $A$ .

Giải: Các phép tính trong ví dụ này và ví dụ tiếp theo được thực hiện bằng MATLAB, vốn tính toán với độ chính xác 16 chữ số, mặc dù ở đây chỉ hiển thị một vài chữ số có ý nghĩa. Bắt đầu, tính $A\mathbf{x}_0$ và xác định phần tử lớn nhất $\mu _0$ trong $A\mathbf{x}_0$ :

$A\mathbf{x}_0=\begin{bmatrix}6&5\\1&2\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}=\begin{bmatrix}5\\2\end{bmatrix},\quad\mu _0=5$

Chuẩn hóa $A\mathbf{x}_0$ bằng $1/\mu _0$ để thu được $\mathbf{x}_1$ , sau đó tính $A\mathbf{x}_1$ và xác định phần tử lớn nhất trong $A\mathbf{x}_1$ :

$\mathbf{x}_1=\frac{1}{\lambda_0}A\mathbf{x}_0=\frac{1}{5}\begin{bmatrix}5\\2\end{bmatrix}=\begin{bmatrix}1\\.4\end{bmatrix}$

$A\mathbf{x}_1=\begin{bmatrix}6&5\\1&2\end{bmatrix}\begin{bmatrix}1\\.4\end{bmatrix}=\begin{bmatrix}8\\1.8\end{bmatrix},\quad\mu _1=8$

Tiếp tục chuẩn hóa $A\mathbf{x}_1$ bằng $1/\mu _1$ để thu được $\mathbf{x}_2$ , sau đó tính $A\mathbf{x}_2$ và xác định phần tử lớn nhất trong $A\mathbf{x}_2$ :

$\mathbf{x}_2=\frac{1}{\mu _1}A\mathbf{x}_1=\frac{1}{8}\begin{bmatrix}8\\1.8\end{bmatrix}=\begin{bmatrix}1\\.225\end{bmatrix}$

$A\mathbf{x}_2=\begin{bmatrix}6&5\\1&2\end{bmatrix}\begin{bmatrix}1\\.225\end{bmatrix}=\begin{bmatrix}7.125\\1.450\end{bmatrix},\quad\mu _2=7.125$

Tiếp tục chuẩn hóa $A\mathbf{x}_2$ bằng $1/\mu _2$ để thu được $\mathbf{x}_3$ , và cứ tiếp tục như vậy. Kết quả của các phép tính MATLAB trong năm lần lặp đầu tiên được trình bày trong Bảng 2.

Bảng 2: Phương Pháp Lũy Thừa Cho Ví Dụ 2

$k$	$\mathbf{0}$	$\mathbf{1}$	$\mathbf{2}$	$\mathbf{3}$	$\mathbf{4}$	$\mathbf{5}$
$\mathbf{x}_k$	$\begin{bmatrix}0\\1\end{bmatrix}$	$\begin{bmatrix}1\\.4\end{bmatrix}$	$\begin{bmatrix}1\\.225\end{bmatrix}$	$\begin{bmatrix}1\\.2035\end{bmatrix}$	$\begin{bmatrix}1\\.2005\end{bmatrix}$	$\begin{bmatrix}1\\.20007\end{bmatrix}$
$A\mathbf{x}_k$	$\begin{bmatrix}5\\2\end{bmatrix}$	$\begin{bmatrix}8\\1.8\end{bmatrix}$	$\begin{bmatrix}7.125\\1.450\end{bmatrix}$	$\begin{bmatrix}7.0175\\1.4070\end{bmatrix}$	$\begin{bmatrix}7.0025\\1.4010\end{bmatrix}$	$\begin{bmatrix}7.00036\\1.40014\end{bmatrix}$
$\mu _k$	$5$	$8$	$7.125$	$7.0175$	$7.0025$	$7.00036$

Dữ liệu từ Bảng 2 cho thấy rõ ràng rằng dãy $\{\mathbf{x}_k\}$ tiến gần đến $(1,.2)$ và dãy $\{\mu _k\}$ tiến gần đến 7. Nếu đúng như vậy, thì $(1,.2)$ là một vector riêng và 7 là giá trị riêng ưu thế. Điều này có thể dễ dàng xác minh bằng cách tính:

$A\begin{bmatrix}1\\.2\end{bmatrix}=\begin{bmatrix}6&5\\5&1\end{bmatrix}\begin{bmatrix}1\\.2\end{bmatrix}=\begin{bmatrix}7\\1.4\end{bmatrix}=7\begin{bmatrix}1\\.2\end{bmatrix}$

Dãy $\{\mu _k\}$ trong ví dụ 2 hội tụ nhanh đến $\lambda_1=7$ vì giá trị riêng thứ hai của $A$ nhỏ hơn rất nhiều. (Thực tế, $\lambda_2=1$ .)

Nhìn chung, tốc độ hội tụ phụ thuộc vào tỷ lệ $\left|\lambda_2/\lambda_1\right|$ , vì trong phương trình (2), vector $c_2\left({\lambda_2}/{\lambda_1}\right)^k\mathbf{v}_2$ là nguồn lỗi chính khi sử dụng phiên bản chuẩn hóa của $A^k\mathbf{x}$ để xấp xỉ $c_1\mathbf{v}_1$ . (Các tỷ lệ khác $\lambda_j/\lambda_1$ thường nhỏ hơn.) Nếu $\left|{\lambda_2}/{\lambda_1}\right|$ gần 1, thì $\{\mu _k\}$ và $\{\mathbf{x}_k\}$ có thể hội tụ rất chậm, và có thể cần sử dụng các phương pháp xấp xỉ khác.

Với phương pháp lũy thừa, có một xác suất nhỏ rằng vector ban đầu $\mathbf{x}$ được chọn không có thành phần nào theo hướng của $\mathbf{v}_1$ (tức là $c_1=0$ ). Tuy nhiên, do lỗi làm tròn trong quá trình tính toán $\mathbf{x}_k$ trên máy tính, khả năng cao sẽ xuất hiện một thành phần nhỏ theo hướng của $\mathbf{v}_1$ . Nếu điều đó xảy ra, dãy $\mathbf{x}_k$ sẽ bắt đầu hội tụ về một bội số của $\mathbf{v}_1$ .

Phương Pháp Lũy Thừa

PHƯƠNG PHÁP LŨY THỪA ĐỂ ƯỚC LƯỢNG GIÁ TRỊ RIÊNG ƯU THẾ

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 20: Ước Lượng Lặp Cho Giá Trị Riêng

Lesson Attachments

Phương Pháp Lũy Thừa

PHƯƠNG PHÁP LŨY THỪA ĐỂ ƯỚC LƯỢNG GIÁ TRỊ RIÊNG ƯU THẾ

Để lại một bình luận Hủy