Bài giảng Lý thuyết về số gần đúng - Chương 3: Hệ phương trình tuyến tính

CHƯƠNG 3
HỆ PHƯƠNG TRÌNH
TUYẾN TÍNH
I. ĐẶT BÀI TOÁN :
Hệ phương trình tuyến tính n pt và n 
ẩn có dạng
Ax = b
với
Các phương pháp giải
➢ Phương pháp giải chính xác
▪ Phương pháp Gauss
▪ Phương pháp nhân tử LU
▪ Phương pháp Cholesky
➢ Phương pháp giải gần đúng
▪ Phương pháp lặp Jacobi
▪ Phương pháp lặp Gauss-Seidel
II. PHƯƠNG PHÁP GAUSS
1. Các dạng ma trận đặc biệt : 
a. Ma trận tam giác dưới
detA = a11a22 . . . ann ≠ 0 ⇔ aii ≠ 0, ∀i
Phương trình có nghiệm
b. Ma trận tam giác trên : 
detA = a11a22 . . . ann ≠ 0 ⇔ aii ≠ 0, ∀i
Phương trình có nghiệm
2. Phương pháp Gauss : 
Ta sử dụng các phép biến đổi sơ cấp theo 
dòng để chuyển ma trận A về ma trân tam 
giác trên
Các phép biến đổi sơ cấp theo dòng
➢ hoán chuyển 2 dòng
➢ nhân 1 dòng với 1 số khác 0
➢ cộng 1 dòng với dòng khác
Ví dụ : Giải hệ phương trình 
Giải
Giải pt ma trận tam giác trên, ta được nghiệm
x = (-7, 3, 2, 2)t
III. PHƯƠNG PHÁP NHÂN TỬ LU
Phân tích ma trận A thành tích 2 ma trận L và U
A = LU
L : ma trận tam giác dưới
U : ma trận tam giác trên
Phương trình Ax = b ⇔ L(Ux) = b
Ta đưa về giải 2 hệ phương trình
Phương pháp Doolittle :
Giả sử A ma trận không suy biến và a11 ≠ 0 
Ta có thể phân tích A thành 
A = LU
Ma trân Δ dưới
Ma trân Δ trên
Các phần tử của L và U được xác định theo 
công thức
Ví dụ : Giải hệ phương trình 
Giải 
Ta phân tích
Giải hệ Ly = b
Giải hệ Ux = y
IV. PHƯƠNG PHÁP CHOLESKY
Định nghĩa : 
➢ Ma trân A gọi là đối xứng nếu
 A = At
➢ Ma trân A gọi là xác định dương nếu
Phương pháp Cholesky là pp LU với A là ma trận 
đối xứng và xác định dương
Để kiểm tra xác định dương, ta dùng đình lý sau:
Định lý : 
Ma trận A là xác định dương khi và chỉ khi tất cả 
các định thức con chính của nó đều dương
Ví dụ : Kiểm tra tính xác định dương của ma trận
Giải
Các định thức con chính:
Vậy A là xác định dương
Định lý (Cholesky) : 
Nếu A ma trận đối xứng và xác định dương, thì tồn 
tại ma trận Δ dưới, khả đảo B sao cho
A = BBt
Ma trận B = (bij) tìm theo công thức sau : 
Ví dụ : Giải hệ phương trình Ax = b
Giải
Ta có A ma trận đối xứng và xác định dương
Phân tích A = BBt
Các hệ số 
Giải hệ By = b
Giải hệ Bt x = y
Ví dụ :
a. Kiểm tra tính xác định dương
b. Phân tích A = BBT theo pp cholesky
Tính b11+b22+b33
a. Các định thức con chính:
Vậy A là xác định dương
Các hệ số b.
b11+b22+b33 = 6
V. CHUẨN :
1. Chuẩn vector : 
Có nhiều công thức chuẩn, thường ta dùng 
chuẩn ∞ và chuẩn 1
∀x= (x1,x2,, xn)
t
2. Chuẩn ma trận : 
Cho ma trận A = (aij), ta có
Ví dụ :
Ví dụ :
Tính
V. Hệ pt ổn định và số điều kiện : 
Xét hệ phương trình Ax = b
Định nghĩa : 
Hệ phương trình gọi là ổn định nếu mọi thay 
đổi nhỏ của A hay b thì nghiệm của hệ chỉ thay 
đổi nhỏ 
1. Hệ pt ổn định : 
Ví dụ : Xét hệ phương trình Ax = b với
Hệ phương trình có nghiệm x = (1, 1)T
Thay đổi 
Nghiệm của hệ : x=(-17, 10)T 
Ta thấy nghiệm của hệ khác rất xa khi b thay 
đổi nhỏ. Vậy hệ không ổn định
2. Số điều kiện : 
Ta tìm điều kiện để hệ ổn định 
Định nghĩa : Số
k(A) = ||A|| ||A-1||
Gọi là số điều kiện của ma trận A
Nhận xét : 
Số điều kiện của ma trận đặc trưng cho tính ổn 
định của hệ phương trình
➢ k(A) càng gần 1 thì hệ càng ổn định
➢ k(A) càng xa 1 thì hệ càng không ổn định
Ví dụ :
Ta có 
● k(A) = 3.01 x 401 = 1207.01 >> 1
Vậy hệ không ổn định
Tính số điều kiện k(A) theo chuẩn ∞
Ví dụ :
Ta có
● k(A) = ||A||1||A
-1||1=6 x 20/13 = 9.2308 
Tính số điều kiện k(A) theo chuẩn 1
VI. PHƯƠNG PHÁP LẶP : 
Ta chuyển hệ pt về dạng
x = Tx + c 
Với T là ma trận vuông cấp n và c là 1 vector
Để tìm nghiệm gần đúng, với vector ban đầu 
x(0), ta xây dựng dãy lặp theo công thức
x(m) = Tx(m-1)+ c, ∀m=1,2,
Ta cần khảo sát sự hội tụ của dãy {x(m)}
Ta có định lý sau 
Định lý : 
Nếu ||T|| < 1 thì dãy lặp x(m) sẽ hội tụ về nghiệm x 
của hệ pt, với mọi vector ban đầu x(0).
Ta có công thức đánh giá sai số : 
hoặc 
1. Phương pháp lặp Jacobi : 
Ta phân tích 
A = D + L + U
trong đó
Phương trình Ax = b
⇔ (D+L+U)x = b
⇔Dx = -(L+U)x + b
⇔ x = -D-1(L+U)x + D-1b 
⇔ x = Tx + c
với T = -D-1(L+U) và c = D-1b
pp lặp theo phân tích trên gọi là pp lặp Jacobi
Bây giờ ta tìm điều kiện để pp lặp Jacobi HT
Định nghĩa : 
Ma trận A gọi là ma trận đường chéo trội nghiêm 
ngặt nếu nó thỏa điều kiện sau : 
Nhận xét : 
Nếu A là ma trận đường chéo trội nghiêm ngặt thì
detA ≠ 0 và aii ≠ 0 ∀i=1,n
Định lý : 
Nếu A là ma trận đường chéo trội nghiêm ngặt, thì pp 
lặp Jacobi hội tụ với mọi vector ban đầu x(0) 
A ma trân đường chéo trội nghiêm ngặt nên
⇒ pp lặp hội tụ
Thay vao, ta có công thức lặp Jacobi
x(m) = Tx(m-1)+ c, ∀m=1,2,
Ví dụ : Cho hệ phương trình 
a. Tìm nghiệm gần đúng x(5) với vector ban đầu x(0) 
= 0
b. Tính ma trận T và c
c. Tính sai số của nghiệm x(5) theo công thức hậu 
nghiệm
a.
Công thức lặp Jacobi
m 0 1 2 3 4 5
x1
(m) 0 0.7 0.71 0.725 0.7267 0.72717
x2
(m) 0 0.8 0.64 0.640 0.6368 0.63648
x3
(m) 0 0.9 0.89 0.907 0.9085 0.90899
b. Ta có 
c. Công thức sai số
Ta có ||T||∞=0.2, nên
2. Phương pháp lặp Gauss-Seidel : 
Ta phân tích 
A = D + L + U
như trong phần trước
Phương trình Ax = b
⇔ (D+L+U)x = b
⇔ (D+L)x = -Ux + b
⇔ x = -(D+L)-1Ux + (D+L)-1b 
⇔ x = Tx + c
với T = -(D+L)-1U và c = (D+L)-1b
pp lặp theo phân tích này gọi là pp lặp Gauss-Seidel
Định lý : 
Nếu A là ma trận đường chéo trội nghiêm ngặt, thì 
pp lặp Gauss-Seidel hội tụ với mọi vector ban đầu 
x(0) 
Ta có công thức lặp Gauss-Seidel
Ví dụ : Cho hệ phương trình 
a. Tìm nghiệm gần đúng x(4) với vector ban đầu x(0) 
=(0,0,0)
b. Tính ma trận T và c
c. Tính sai số của nghiệm x(4) theo công thức hậu 
nghiệm
a.
Công thức lặp Gauss-Seidel
m 0 1 2 3 4
x1
(m) 0 0.6 0.5519 0.554268975 0.554233852
x2
(m) 0 0.62 0.661955 0.661700938 0.661713904
x3
(m) 0 0.791 0.78828775 0.788511944 0.788509080
b. Ta có 
Ta có ||T||∞=0.15, nên
c. Công thức sai số