Khóa luận tốt nghiệp
Khoa Toán
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
........................
NGUYỄN THỊ HUỆ
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành : Giải tích
HÀ NỘI, 2012
Nguyễn Thị Huệ
1
Lớp K34A
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
........................
NGUYỄN THỊ HUỆ
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành : Giải tích
Người hướng dẫn khoa học
TS. NGUYỄN VĂN HÙNG
HÀ NỘI, 2012
Lời cảm ơn
Sau một thời gian miệt mài nghiên cứu cùng sự giúp đỡ của các thầy cô
giáo và các bạn sinh viên đến nay khóa luận của em đã được hoàn thành.
Em xin bày tỏ lòng biết ơn sâu sắc của mình đến Tiến Sĩ Nguyễn Văn
Hùng đã hướng dẫn và giúp đỡ em tận tình trong quá trình chuẩn bị và hoàn
thành khóa luận.
Em xin trân thành cảm ơn ban chủ nhiệm khoa Toán đã tạo điều kiện
cho em có cơ hội để tập dượt với việc nghiên cứu khoa học. Đồng thời em xin
trân thành cảm ơn sự giúp đỡ quý báu của các thầy cô trong tổ giải tích, sự
động viên giúp đỡ, đóng góp ý kiến của bạn bè đã dành cho em trong quá
trình học tập và hoàn thành khóa luận.
Vì đây là lần đầu tiên em được làm quen với công việc nghiên cứu và
kiến thức của bản thân còn hạn chế nên không thể tránh khỏi những thiếu sót.
Em rất mong sự đóng góp ý kiến của các thầy cô và các bạn sinh viên để khóa
luận của em được hoàn thiện hơn.
Em xin trân thành cảm ơn!
Hà Nội, tháng 5 năm 2012
Sinh viên
Nguyễn Thị Huệ
Lời cam đoan
Em xin cam đoan khóa luận là công trình nghiên cứu của riêng em.
Trong khi nghiên cứu, em đã kế thừa những thành quả nghiên cứu của
các nhà khoa học, nhà nghiên cứu với sự trân trọng và biết ơn.
Những kết quả nêu trong khóa luận chưa được công bố trên bất kì công
trình nào khác.
Hà Nội, tháng 5 năm 2012
Sinh viên
Nguyễn Thị Huệ
Mục lục
Lời cảm ơn……………………………………………………………………1
Lời cam đoan…………………………………………………………………2
Mở đầu………………………………………………………………………..4
Nội dung
Chương 1: Một số kiến thức cơ bản………………………………………….6
1.1 Số gần đúng và sai số…………………………………………………...6
1.2. Chữ số có nghĩa, chữ số chắc…………………………………………...8
1.3. Sai số tính toán…………………………..………………………….…..9
1.4. Bài toán ngược của bài toán tham số…………………………………..12
Chương 2: Lý thuyết về hệ phương trình tuyến tính………………………...13
2.1. Các dạng biểu diễn hệ phương trình tuyến tính…………………………13
2.2. Một số khái niệm………………………………………………………..14
2.3. Nghiệm và điều kiện tồn tại nghiệm………………………...………….14
2.4. Hệ n phương trình n ẩn…………………………………………………15
2.5. Phân tích sai số………………………………………………………….17
2.6. Chuẩn của ma trận và chuẩn củavec tơ…………………………………19
Chương 3: Một số phương pháp giải hệ phương trình tuyến tính………..….20
3.1.
Phương pháp trực tiếp giải hệ phương trình tuyến tính………………20
3.1.1. Phương pháp Gauss…………………………………………………..20
3.1.2. Phương pháp Cholesky……………………………………………….27
3.1.3. Phương pháp trực giao hóa…………………………………………...31
3.2.
Phương pháp gián tiếp giải hệ phương trình tuyến tính…..…………..34
3.2.1. Phương pháp lặp đơn…………………………………………..……..34
3.2.2. Phương pháp Jacobi…………………………………………………..40
3.2.3. Phương pháp Seidel…………………………………………………..42
3.2.4. Phương pháp Gauss-Seidel……………………………………..…….45
Chương 4: Bài tập áp dụng…………………………………………………..48
Kết luận……………………………………………………...………………63
Tài liệu tham khảo…………………………………………………………..64
MỞ ĐẦU
1. Lí do chọn đề tài
Các bài toán ứng dụng trong kinh tế kĩ thuật thường là không đẹp và
không thể giải theo các phương pháp tính đúng. Người ta cần các phương
pháp giải có tính chất thuật giải và nếu các kết quả là gần đúng thì sai số phải
“đủ nhỏ” (thường là hội tụ về 0). Cho dù các phương pháp đó đòi hỏi lượng
phép tính lớn, thì với máy tính bài toán dễ dàng được giải quyết. Một trong
các ngành học nghiên cứu các phương pháp như trên là giải tích số.
Phương pháp giải tích số có ý nghĩa rất lớn trong đại số tuyến tính, đặc
biệt là đối với việc giải hệ phương trình tuyến tính. Khi số các phương trình
lớn các phương pháp truyền thống nhiều khi gặp khó khăn, chúng ta không
thể giải quyết một cách chính xác mà chỉ có thể đưa ra lời giải gần đúng cho
một bài toán. Chính vì vậy em đã chọn đề tài “ Hệ phương trình tuyến tính”
với nội dung chủ yếu là tìm những phương pháp giải gần đúng hệ n phương
trình tuyến tính n ẩn để làm khóa luận tốt nghiệp.
2. Mục đích nghiên cứu
- Tìm hiểu các kiến thức về hệ phương trình tuyến tính.
-Làm rõ các phương pháp giải gần đúng hệ phương trình tuyến tính.
3. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: kiến thức về hệ phương trình tuyến tính.
Phạm vi nghiên cứu: kiến thức cơ bản về sai số; phương pháp giải trực
tiếp; gián tiếp hệ phương trình tuyến tính.
4. Nhiệm vụ nghiên cứu
- Trình bày lý thuyết cơ bản về hệ phương trình tuyến tính.
- Đề xuất các phương pháp giải gần đúng hệ phương trình tuyến tính.
5. Phương pháp nghiên cứu
Nghiên cứu sử dụng các lí luận, các công cụ toán học.
Nghiên cứu sách tham khảo, các tài liệu liên quan.
Nghiên cứu lí luận, tổng hợp, đánh giá.
6. Cấu trúc của khóa luận
Gồm 3 phần:
Phần I: Mở đầu
Phần II: Nội dung
Gồm 4 chương
Chương 1: Một số kiến thức cơ bản
Chương 2: Lý thuyết về hệ phương trình tuyến tính
Chương 3: Các phương pháp giải hệ phương trình tuyến tính
Chương 4: Bài tập áp dụng
NỘI DUNG
Chương 1: Một số kiến thức cơ bản
1.1. Số gần đúng và sai số
1.1.1 Định nghĩa
*
Trong thực tế tính toán ta thường không biết số đúng a mà chỉ biết số
đủ gần nó là a . Ta nói a là số gần đúng
của nhiều.
Đại lượng
*
*
a , nếu a không sai khác a
a được gọi là sai số thực sự của a .
a
*
Do không biết a* nên cũng không biết nhưng ta có thể tìm được
số
a
0 sao cho a
a
a
*
(1.1) hay
a
a*
a
a a
Số a thỏa mãn (1.1) được gọi là sai số tuyệt đối của a .
Tỉ số
được gọi là sai số tương đối của a .
a
a
a
*
Ví dụ 1.1.1. Cho số a ; 3.14
a
3.14
*
3.14 a
*
a
3.15;
3.142 ;
a 0.01
0.002
a
Trong phép đo nói chung sai số tuyệt đối càng nhỏ càng tốt.
Ví dụ 1.1.2. Đo độ dài hai đoạn thẳng AB, CD ta được a 10cm và b
1cm ;
với
a
b
0.01. Khi đó ta có
0,1%
a
còn
b
1%
hay
b 10a .
Hiển nhiên rằng phép đo a chính xác hơn phép đo b mặc dù
a b. Như vậy độ chính xác của phép đo phản ánh qua sai số
tương đối.
1.1.2. Sai số thu gọn
Xét số thập phân a được biểu diễn dưới dạng
a (
.10
.10 )
0 .1 p1 ...
p
pq
p
p
p
Trong đó 0 9 ; > 0 p 1
;
i
i
p q
p
Nếu p
q
0 thì a là số nguyên.
Nếu
p
q
p q chữ
số.
0 thì a là số thập phân có phần lẻ gồm
thì a là số thập phân vô hạn.
Nếu p
q
Ví dụ 1.1.2.1.
2403
2
4
10 102
3
Ta thấy
p
Ví dụ 1.1.2.2.
q
25.134
Ta thấy p
3 chữ số.
q
0
1
10
310
0
0 nên 2403 là số nguyên.
2
1
10
5 1
0
1
10
10
3
2
10
4 10
3
3 nên 25.134 là số thập phân có phần lẻ gồm
a
Thu gọn a là vứt bỏ một số các chữ số bên phải của a để được số
ngắn gọn hơn nhưng vẫn đảm bảo độ chính xác cần thiết .
Quy tắc thu gọn
Giả sử :
a
(p .
10
p
... j.
10
j
...
.10
pq
p q
)
Giả sử ta muốn giữ lại đến hàng thứ j, gọi phần bỏ đi là M. Khi đó ta
được số thu gọn là :
a (.10
0 .1
p
p
j
j
0
j
0.5j
10
.10 )
j
j
0.5 10
j
M
0.5 10
j
10
j
M
1
Nếu M
...
p
Trong đó
p1
nếu
thì
j
j
là chẵn và
j
j
nếu
j 1
lẻ
j
vì tính toán với số chẵn tiện hơn.
Ví dụ 1.1.2.3.
□ 3.141592 3.14159 □ 3.1416 □ 3.142 □ 3.14 □ 3.1 □ 3.
□
Giả sử sai số thu gọn của a là a . Ta có a
a
a
a
*
a a a
a
a
a
*
*
a .
a
a
a
a
Từ đánh giá trên ta có nhận xét : Khi thu gọn số a thì sai số tuyệt đối
*
*
của a với a lớn hơn hoặc bằng sai số tuyệt đối của a và a .
1.2. Chữ số có nghĩa, chữ số chắc
1.2.1. Chữ số có nghĩa
Chữ số có nghĩa là mọi chữ số khác 0 và cả chữ số 0 nếu nó kẹp giữa
hai chữ số có nghĩa hoặc nó đại diện cho hàng được giữ lại.
Ví dụ 1.2.1.
= 0.000870190
Bốn chữ số 0 đầu tiên là những chữ số không có nghĩa, toàn bộ những
chữ số còn lại là những chữ số có nghĩa.
1.2.2. Chữ số chắc
Xét số :
a
(p .
10
p
... j.
10
j
...
.10
p q
)
pq
Chữ số được gọi là chữ số chắc nếu 10i . Với
a
là số cho
j
trước. Tham số được chọn để một chữ số vốn đã chắc sau khi thu gọn
vẫn là chữ số chắc.
Ví dụ 1.2.2.
a 1.70134 ;
Khi đó
a
0
110
Chọn
Nguyễn Thị Huệ
a
7
1
10
0.001
0
2
10
10
3
4 10
3
4
110 310
5
1 thì a có bốn chữ số chắc là 1; 7; 0; 1 còn lại là hai chữ số
10
Lớp K34A
không Chọn
chắc là 3; 4.
0.5 thì a có ba chữ số chắc là 1; 7; 0 còn 1; 3; 4 là ba chữ
số không chắc.
Ta xét việc chọn . Giả sử a được viết dưới dạng :
Nguyễn Thị Huệ
11
Lớp K34A
a ( .
p
10
p
... j.
10
j
...
.10
pq
i
Ta chọn sao cho sau khi thu gọn đến bậc
)
vẫn là chắc.
1
(i+1) thì Muốn vậy phải có :
a a 10
p q
i 1
10i 0.5
i 1
10
10
i 1
5
10
5
9
Trong thực tế người ta chọn = 1 hoặc = 0.5
Nếu = 1 người ta nói chữ số là chắc theo nghĩa rộng, còn khi
= 0.5 người ta nói chữ số là chắc theo nghĩa hẹp.
Lưu ý: Khi viết số gần đúng ta chỉ nên giữ lại một hai chữ số không
chắc để khi tính toán sai số sai số chỉ tác động lên những chữ số không chắc
mà thôi.
1.3. Sai số tính toán
Giả sử ta phải tính đại lượng y theo công thức y
*
*
*
*
*
f (x1; x2 ; ... ; xn ) .
*
Gọi x (x ; x ; ... ; x ) f (x ) là các giá trị đúng. Giả sử ta
1
2
n
; y
không biết các giá trị đúng này, mà ta chỉ biết các giá trị x (x ; x ; ... ; x )
;
1
2
n
*
*
lần lượt là các giá trị gần đúng của x và y
y f
.
(x)
Giả sử xi ; (với
i
xi
1,n ) là các sai số tuyệt đối và tương đối
của
các đối số. Khi đó sai số của hàm y f (x ; x ; ... ; x ) được gọi là sai số
1
2
n
tính toán.
Giả sử f (x1; x2 ; ... ; xn ) là hàm số khả vi liên tục thì:
*
*
y y y
n
2
xi
1
n
=
;
'
f (x
*
f (x1; x2 ; ... ; xn f (x1 ; x2 ; ... ; xn )
)
*
1
i
i
x ; ... ; x )
*
x x
*
xn là điểm giữa x và x . Vì f khả vi liên tục và
)
Với x (x1; x2 ;
... ;
*
xi
xi
khá bé nên
xi
y
n
f xi' (x) với
i1
xi x
n
Vậy
y
y
f (x)
i
1
(x1; x2 ; ... ; xn )
xi
ln
xi
y
Và cũng có thể viết
y
ln y
1.3.1. Sai số của phép toán cộng, trừ
Nếu y
n
thì
yx
xi
y
1,n .
i
i1
Vậy ta có :
1
với i
'
n
xi
2
'
f
x
i1
x
i
1
...
x
n
x
n
x
i
i1
n
Chú ý rằng nếu tổng đại số y xi bé về giá trị
tuyệt đối thì
y
y
lớn;
i1
phép tính sẽ kém chính xác. Ta khắc phục bằng cách tránh công thức đưa đến
hiệu của hai số gần nhau.
Ví dụ 1.3.1.
y 2.01 2.00
Ta có: y
0.01
2.01
□
2.00 □
0.01
0.0035
1.42 1.41
Nhận xét: Sai số tuyệt đối của một tổng bằng tổng các sai số tuyệt đối
của các số hạng thành phần.
1.3.2. Sai số của phép toán nhân, chia
Sai số của phép nhân
Giả sử
y
x .x. x
Ta có y
ln y
1
2
n
x1 . x2 .... xn
ln
x1
ln x2 ... ln xn
ln y
ln
x1
ln
x2
.
...
ln xn
y 1
... x
x
x
2
n
y y y
Vậy sai số tương đối của một tích bằng tổng các sai số tương đối của
các số hạng thành phần.
Sai số của phép chia
x
Xét y 1
x2
Ta có
y
x22
1
x1 x2 ;
x1
;
y
x2
x2
x1
Suy ra
y
x
x22
2
y
y
=
1
( x1
x
y
2
1
x1
1
x
x
1
1
x1
x
2
x2 ) x:1 x2
2
1
+ x
x
x
x
2
1
2
2
1.3.3. Sai số của phép tính lũy thừa
Xét y
x
(
R,
x
0) , khi đó
y
x
Như vậy nếu > 1 thì độ chính xác là giảm đi, nếu <1 thì
độ chính
xác tăng lên. Nếu
=
nếu
1
,
kk
1 (phép nghịch đảo) thì độ chính xác là không đổi,
N (phép khai căn) thì độ chính xác tăng lên.
*
1.3.4. Sai số của phép tính logarit
Xét y
ln x ; ta có:
y
x
Ví dụ 1.3.4. Biết diện tích hình vuông
S
và S 0.01. Hãy tính
cạnh
12.34
Gọi x là cạnh của hình vuông, thì x S
3.5128.
của hình vuông.
□
Xét S
S
S
□ 0.008.
Vậy
x = 3.5128 0.0004 □
1.4
10
3
,
từ đó ta thấy rằng x có 4 chữ số chắc.
1.4. Bài toán ngược của bài toán tham số
Giả sử đại lượng y được tính theo công thức
y
Cần tính
xi
;
để
y
f (x1; x2 ; ... ; xn ) .
0 cho trước. Theo công thức tính toán ta
phải có :
y
Suy ra xi
f
i
1
xi
n
xi
nf'
xi
Kết luận: Nếu các biến xi có vai trò đều nhau thì ta có thể lấy
xi f '
n xi
Khi đó
y
.
Ví dụ 1.4.1. Một hình trụ có chiều cao
h 3m , bán kính
đáy
R 2m .
Tính
h, R , số để thể tích chính xác đến 0.1m3 .
V
2
2
R .
Ta có V R h , nên có :
2
R h ; 2Rh ;
V
V
R
Vậy
0.1
3.12
h
0.003 ; h
0,1
R
3 .4
0.001
0.1
0.003 ;
3.2 .
2.3
Chương 2: Lý thuyết về hệ phương trình tuyến tính
2.1. Các dạng biểu diễn hệ phương trình tuyến tính
2.1.1. Dạng tổng quát
Xét hệ m phương trình bậc nhất đối với n ẩn x ; x ; x ; ... ; x
1
2
3
n
a11 x1
21 x1
a
a1n
...
xn a2
...
x
n n
... ... ...
...
a12
x2
a22
x2
...
... ...
a x am 2
m1 1
x2
...
b1
b2
... ...
(2.1.1)
bm
amn
xn
Hệ này được gọi là một hệ phương trình tuyến tính ở dạng tổng quát.
. aij được gọi là hệ số của
các ẩn
xj
(i
1,m 1, n ).
; j
. bi 1,m ) gọi là hệ số tự do.
(i
a11
a1
2
a a
A = 21
22
... ...
am1 am
... a1n
... a
là ma trận hệ số của hệ (2.1.1)
2n
...
... amn
...
2
a11
a1
... a1 b1
2
a22
A
a21
... ...
am1 am
2
n
... a2 b
2
là ma trận mở rộng của hệ (2.1.1)
n
... ...
... amn m
...
2.1.2. Dạng ma trận
Đưa vào các ma trận cột
b1
b2
x1
x
2
T
x
(x1 , x2 , x3 , ... , xn )
T
(b , b , b ,
... , b )
;b
xn
b n
1
2
3
m
Ta có hệ (2.1.1) tương đương với một phương trình ma trận:
Ax = b
(2.1.2)
2.1.3. Dạng vectơ
Ta kí hiệu a là vectơ cột thứ j của ma trận A và xem x , b cũng là các
j
vectơ cột, tức là:
aj
x
b
a
1j
; a2 j ; ... ; amj
x ; x ; ... ; x
1
2
n
(b1; b2 ; ... ; bm )
Khi đó hệ một có thể viết dưới dạng một phương trình vectơ:
a1 x1
2.2. Một số khái niệm
a2
x2
... an xn
b
(2.1.3)
Hệ phương trình tuyến tính (2.1.1) được gọi là :
Thuần nhất nếu tất cả các bi
0
( i 1,m )
Không thuần nhất nếu có ít nhất một b
i
0
(i
1,m ).
Tương thích nếu hệ có ít nhất một nghiệm, tức là tồn tại một bộ giá
trị của x ; x ; x ; ... ; x mà khi thay vào sẽ có một đồng nhất thức.
1
2
3
n
Hệ không tương thích nếu không có một nghiệm nào.
Hệ xác định nếu hệ chỉ có một nghiệm duy nhất.
Hệ bất định nếu tồn tại quá một nghiệm.
2.3. Nghiệm và điều kiện tồn tại nghiệm
2.3.1. Nghiệm
Một vectơ n chiều x
(2.1.1) nếu ta thay các ẩn
c ; c ; c ; ... ; c
1
2
3
xj bởi các số cj , (
j
n
được gọi là nghiệm của hệ
1, n ) vào tất cả các
phương
trình của hệ ta được các đẳng thức đúng.
Hai hệ phương trình tương đương nếu chúng có cùng tập nghiệm.
2.3.2. Định lí về sự tồn tại nghiệm
Định lí (Croncke-capelly)
Điều kiện cần và đủ để một hệ phương trình tuyến tính có nghiệm là hệ
đó có hạng của ma trận mở rộng bằng hạng của ma trận hệ số.
Chứng minh
Ta kí hiệu A =
a1; a2 a3 ; ... an là hệ vectơ cột của ma trận A
; ;
a1;
B=
a2 a3 ; ... an b là hệ vectơ cột của ma trận bổ sung A
; ;
; của
hệ (2.1.1)
U là không gian sinh bởi hệ vectơ A , W là không gian sinh bởi hệ
vectơ B.
Vì A B nên U W.