Bài giảng 21: Ước Lượng Lặp Cho Giá Trị Riêng (tiếp theo)

(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 Nghịch Đảo

Phương pháp này cung cấp một xấp xỉ cho bất kỳ giá trị riêng nào, với điều kiện có một ước lượng ban đầu tốt $\alpha$ của giá trị riêng $\lambda$ . Trong trường hợp này, ta đặt $B=(A-\alpha I)^{-1}$ và áp dụng phương pháp lũy thừa cho $B$ . Có thể chứng minh rằng nếu các giá trị riêng của $A$ là $\lambda_1,\dots,\lambda_n$ , thì các giá trị riêng của $B$ là:

$\frac{1}{\lambda_1-\alpha},\frac{1}{\lambda_2-\alpha},\dots,\frac{1}{\lambda_n-\alpha}$

và các vectơ riêng tương ứng vẫn giữ nguyên như đối với $A$ .

Ví dụ, giả sử $\alpha$ gần với $\lambda_2$ hơn so với các giá trị riêng khác của $A$ . Khi đó, ${1}/(\lambda_2-\alpha)$ sẽ là giá trị riêng trội tuyệt đối của $B$ . Nếu $\alpha$ thực sự rất gần với $\lambda_2$ , thì ${1}/(\lambda_2-\alpha)$ sẽ lớn hơn nhiều so với các giá trị riêng khác của $B$ , và phương pháp lũy thừa nghịch đảo sẽ nhanh chóng hội tụ về $\lambda_2$ với hầu hết các lựa chọn của $\mathbf{x}_0$ . Thuật toán sau đây cung cấp các chi tiết cụ thể.

PHƯƠNG PHÁP LŨY THỪA NGHỊCH ĐẢO ĐỂ XÁC ĐỊNH XẤP XỈ GIÁ TRỊ RIÊNG $\lambda$ CỦA $A$

Chọn một ước lượng ban đầu $\alpha$ đủ gần với $\lambda$ .
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,2,...$
a. Giải phương trình $(A-\alpha I)\mathbf{y}_k=\mathbf{x}_k$ để tìm $\mathbf{y}_k$ .
b. Chọn $\mu _{k}$ là một phần tử trong $\mathbf{y}_k$ có giá trị tuyệt đối lớn nhất.
c. Tính $\nu _{k}=\alpha+(1/\mu _{k})$ .
d. Tính $\mathbf{x}_{k+1}=(1/\mu_k)\mathbf{y}_k$ .
Với hầu hết các lựa chọn của $\mathbf{x}_0$ , dãy $\{\nu_k\}$ hội tụ về giá trị riêng $\lambda$ của $A$ , và dãy $\{x_k\}$ hội tụ về một vector riêng tương ứng.

Lưu ý rằng ma trận $B$ , hay chính xác hơn là $(A-\alpha I)^{-1}$ , không xuất hiện trong thuật toán. Thay vì tính $(A-\alpha I)^{-1}\mathbf{y}_k$ để có được vector tiếp theo trong dãy, cách tốt hơn là giải phương trình $(A-\alpha I)^{-1}\mathbf{y}_k=\mathbf{x}_k$ để tìm $\mathbf{y}_k$ (sau đó chuẩn hóa $\mathbf{y}_k$ để tạo ra $\mathbf{x}_{k+1}$ . Vì phương trình này phải được giải cho mỗi $k$ , nên việc phân tích LU của $A-\alpha I$ sẽ giúp tăng tốc quá trình tính toán.

Ví dụ 3: Trong một số ứng dụng, đôi khi cần biết giá trị riêng nhỏ nhất của một ma trận $A$ và có sẵn các ước lượng sơ bộ về các giá trị riêng. Giả sử các giá trị ước lượng cho giá trị riêng của ma trận $A$ dưới đây là $21,3.3$ và $1.9$ . Hãy tìm giá trị riêng nhỏ nhất với độ chính xác đến sáu chữ số thập phân.

$A=\begin{bmatrix}10&-8&-4\\-8&13&4\\-4&5&4\end{bmatrix}$

Giải: Hai giá trị riêng nhỏ nhất có vẻ khá gần nhau, vì vậy ta sử dụng phương pháp lũy thừa ngược cho $A-1.9I$ . Kết quả tính toán bằng MATLAB được hiển thị trong bảng 3. Ở đây, $\mathbf{x}_0$ được chọn tùy ý, $\mathbf{y}_k=(A-1.9I)^{-1}\mathbf{x}_k,\mu_k$ là phần tử lớn nhất của $\mathbf{y}_k$ , $\nu_k=1.9+1/\mu_k$ , và $\mathbf{x}_{k+1}=(1/\mu_k)\mathbf{y}_k$ . Hóa ra ước lượng ban đầu về giá trị riêng khá chính xác và dãy lũy thừa ngược hội tụ nhanh chóng. Giá trị riêng nhỏ nhất chính xác là 2.

BẢNG 3: Phương Pháp Lũy Thừa Ngược

$k$	$\mathbf{0}$	$\mathbf{1}$	$\mathbf{2}$	$\mathbf{3}$	$\mathbf{4}$
$\mathbf{x}_k$	$\begin{bmatrix}1\\1\\1\end{bmatrix}$	$\begin{bmatrix}.5736\\.0646\\1\end{bmatrix}$	$\begin{bmatrix}.5054\\.0045\\1\end{bmatrix}$	$\begin{bmatrix}.5004\\.0003\\1\end{bmatrix}$	$\begin{bmatrix}.50003\\.00002\\1\end{bmatrix}$
$\mathbf{y}_k$	$\begin{bmatrix}4.45\\.50\\7.76\end{bmatrix}$	$\begin{bmatrix}5.0131\\.0442\\9.9197\end{bmatrix}$	$\begin{bmatrix}5.0012\\.0031\\9.9949\end{bmatrix}$	$\begin{bmatrix}5.0001\\.0002\\9.9996\end{bmatrix}$	$\begin{bmatrix}5.000006\\.000015\\9.999975\end{bmatrix}$
$\mu _k$	$7.76$	$9.9197$	$9.9949$	$9.9996$	$9.999975$
$\nu _{k}$	$2.03$	$2.0008$	$2.00005$	$2.000004$	$2.0000002$

Nếu không có ước lượng ban đầu cho giá trị riêng nhỏ nhất của một ma trận, ta có thể chọn đơn giản $\alpha=0$ trong phương pháp lũy thừa ngược. Lựa chọn này thường hoạt động khá tốt nếu giá trị riêng nhỏ nhất gần 0 hơn nhiều so với các giá trị riêng khác.

Hai thuật toán được trình bày trong phần này là những công cụ thực tế cho nhiều trường hợp đơn giản và cung cấp cái nhìn tổng quan về vấn đề ước lượng giá trị riêng. Một phương pháp lặp mạnh mẽ hơn và được sử dụng rộng rãi là thuật toán QR. Chẳng hạn, đây là thuật toán cốt lõi của lệnh eig(A) trong MATLAB, giúp tính toán nhanh chóng giá trị riêng và vector riêng của $A$ .

Phương Pháp Lũy Thừa Nghịch Đảo

PHƯƠNG PHÁP LŨY THỪA NGHỊCH ĐẢO ĐỂ XÁC ĐỊNH XẤP XỈ GIÁ TRỊ RIÊNG $\lambda$ CỦA $A$

Để 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 21: Ước Lượng Lặp Cho Giá Trị Riêng (tiếp theo)

Lesson Attachments

Phương Pháp Lũy Thừa Nghịch Đảo

PHƯƠNG PHÁP LŨY THỪA NGHỊCH ĐẢO ĐỂ XÁC ĐỊNH XẤP XỈ GIÁ TRỊ RIÊNG CỦA

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

PHƯƠNG PHÁP LŨY THỪA NGHỊCH ĐẢO ĐỂ XÁC ĐỊNH XẤP XỈ GIÁ TRỊ RIÊNG $\lambda$ CỦA $A$