Hệ phương trình tuyến tính
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (150.29 KB, 48 trang )
CHÖÔNG 3
HEÄ PHÖÔNG TRÌNH
TUYEÁ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
11 12 1 1 1
21 22 2 2 2
1 2
...
...
( )
... ... ... ... ... ...
...
n
n
ij
n n nn n n
a a a x b
a a a x b
A a x b
a a a x 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 Gauss-Jordan
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 chéo :
11
22
0 ... 0
0 ... 0
... ... ... ...
0 0 ...
nn
a
a
A
a
=
detA = a
11
a
22
. . . a
nn
≠ 0 ⇔ a
ii
≠ 0, ∀i
Nghiệm x
i
= b
i
/a
ii
b. Ma traọn tam giaực dửụựi
11
21 22
1 2
0 ... 0
... 0
... ... ... ...
...
n n nn
a
a a
A
a a a
=
detA = a
11
a
22
. . . a
nn
0 a
ii
0, i
Phửụng trỡnh coự nghieọm
1
1
11
1
1
1
[ ] , 2,
k
k k kj j
j
kk
b
x
a
x b a x k n
a
=
=
= =
c. Ma traọn tam giaực treõn :
11 12 1
22 2
...
0 ...
... ... ... ...
0 0 ...
n
n
nn
a a a
a a
A
a
=
detA = a
11
a
22
. . . a
nn
0 a
ii
0, i
Phửụng trỡnh coự nghieọm
1
1
[ ] , 1, 1
n
n
nn
n
k k kj j
j k
kk
b
x
a
x b a x k n
a
= +
=
= =
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
1 2 3 4
1 2 3 4
1 2 3
1 2 3 4
2 8
2 2 3 3 20
2
4 3 4
x x x x
x x x x
x x x
x x x x
− + − =−
− + − =−
+ + =−
− + + =
Giải
1 1 2 1 8
2 2 3 3 20
[ / ]
1 1 1 0 2
1 1 4 3 4
− − −
− − −
=
−
−
A b
2 3
4 4
/2
1 1 2 1 8
0 2 1 1 6
0 0 1 1 4
0 0 1 2 6
↔
=
− − −
−
→
− − −
h h
h h
Giải pt ma trận tam giác trên, ta được nghiệm
x = (-7, 3, 2, 2)
t
2 2 1
3 3 1
4 4 1
2
1 1 2 1 8
0 0 1 1 4
0 2 1 1 6
0 0 2 4 12
= −
= −
= −
− − −
− − −
→
−
h h h
h h h
h h h
4 4 3
1 1 2 1 8
0 2 1 1 6
0 0 1 1 4
0 0 0 1 2
= +
− − −
−
→
− − −
h h h
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
Ly b
Ux y
=
=
Phương pháp Doolittle :
Giả sử A ma trận không suy biến và a
11
≠ 0
Ta có thể phân tích A thành
A = LU
21
1 2
1 0 ... 0
1 ... 0
... ... ... ...
... 1
n n
l
L
l l
=
11 12 1
22 2
...
0 ...
... ... ... ...
0 0 ...
n
n
nn
u u u
u u
U
u
=
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
1 1
1
1
11
1
1
1
1
, 1
, 2
, 1
1
[ ], 1
j j
i
i
i
ij ij ik kj
k
j
ij ij ik kj
k
jj
u a j n
a
l i n
u
u a l u i j
l a l u j i
u
−
=
−
=
= ≤ ≤
= ≤ ≤
= − < ≤
= − < <
∑
∑
Vớ duù : Giaỷi heọ phửụng trỡnh
1 2 3
1 2 3
1 2 3
2 2 3 9
4 3 4 15
2 2 3
x x x
x x x
x x x
+ =
+ =
+ + =
Giaỷi
Ta phaõn tớch
22 23
32 33
2 2 3 1 0 0 2 2 3
4 3 4 2 1 0 0
2 1 2 1 1 0 0
A u u
l u
= =
22 22 21 12
23 23 21 13
32 32 31 12
22
33 33 31 13 32 23
1
2
1
( ) 1
3
= =
= =
= =
= =
u a l u
u a l u
l a l u
u
u a l u l u
Vớ duù : Giaỷi heọ phửụng trỡnh
1 2 3
1 2 3
1 2 3
2 2 3 9
4 3 4 15
2 2 3
x x x
x x x
x x x
+ =
+ =
+ + =
Giaûi heä Ly = b
1
2
3
1 0 0 9 9
2 1 0 15 3
1 1 1 3 3
− = − ⇒ =
− −
y
y y
y
Giaûi heä Ux = y
1
2
3
2 2 3 9 2
0 1 2 3 1
0 0 3 3 1
x
x x
x
−
− = ⇒ =
− −
Nghieäm x
1
= 2, x
2
= 1, x
3
= -1
TH đặc biệt : A ma trận 3 đường chéo
11 12
21 22 23
32 33
1
0 ... 0 0
... 0 0
0 ... 0 0
... ... ... ... ... ...
0 0 0 ...
nn nn
a a
a a a
A a a
a a
−
=
Ta phân tích A thành LU với
11 12
22 23
21
33
32
0 ... 0
1 0 0 ... 0
0 ... 0
1 0 ... 0
0 0 ... 0
0 1 ... 0
... ... ... ... ...
... ... ... ... ...
0 0 0 ...
0 0 0 ... 1
nn
u u
u u
l
L U u
l
u
= =
Các phần tử của L và U được xác đònh theo
công thức
21
11 11 12 12 21
11
1 1
1 1
1
1
, ,
, 2,
, 2, 1
, 2, 1
ii ii i i i i
i i i i
i i
i i
ii
a
u a u a l
u
u a l u i n
u a i n
a
l i n
u
− −
+ +
+
+
= = =
= − =
= = −
= = −
Vớ duù : Giaỷi heọ phửụng trỡnh Ax = b
2 1 0 2
1 2 1 1
0 1 2 2
A b
= =
Giaỷi
Ta phaõn tớch
22 23
32 33
1 0 0 2 1 0
1 / 2 1 0 0
0 1 0 0
A u u
l u
=
22 22 21 12
32
23 23 32
22
33 33 32 23
3 / 2
1, 2 / 3
4 / 3
u a l u
a
u a l
u
u a l u
= =
= = = =
= =
Giaûi heä Ly = b
1
2
3
1 0 0 2 2
1 / 2 1 0 1 2
0 2 / 3 1 2 10 / 3
y
y y
y
− = ⇒ =
−
Giaûi heä Ux = y
1
2
3
2 1 0 2 5 / 2
0 3 / 2 1 2 3
0 0 4 / 3 10 / 3 5 / 2
x
x x
x
−
− = ⇒ =
Nghieäm x
1
= 5/2, x
2
= 3, x
3
= 5/2
III. PHƯƠNG PHÁP CHOLESKY
Đònh nghóa :
Ma trân A gọi là đối xứng nếu
A = A
t
Ma trân A gọi là xác đònh dương nếu
1 2
1 1
0, ( , ,..., ) , 0
= =
= > ∀ = ∈ ≠
∑∑
n n
t t n
ij i j n
i j
x Ax a x x x x x x R x
Để 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
1 1 1
1 2 0
1 0 4
A
−
=
−
Giải
Các đònh thức con chính:
1 2
1 1
1 0, 1 0
1 2
∆ = > ∆ = = >
3
1 1 1
1 2 1 1 1 1
1 2 0 1 0 4 2 0
1 0 1 0 1 2
1 0 4
−
∆ = = − − + = >
− −
−
Vậy A là xác đònh dương
