GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
1
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP HCM
KHOA KHOA HỌC CƠ BẢN BÀI GIẢNG
PHƯƠNG PHÁP TÍNH
GV: HUỲNH HỮU DINH
TP HỒ CHÍ MINH 2/2011
GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
2
Chương 0. SỐ XẤP XỈ, SAI SỐ 0.1. Số gần đúng và sai số



    ta lần
lượt gọi là sai số tuyệt đối và sai số tương đối của
a
.
Rõ ràng ta có:
a A a
    
hoặc
A a
  

Nếu
A
không phải là số có hữu hạn chữ số thì lẽ đương nhiên ta cần
a
là số có hữu hạn chữ
số và khi đó

sẽ có cùng dạng với
A
. Chẳng hạn, lấy
; 3,14
A a

 
thì
0, 0015926
 

a
, kí hiệu là
a

, là số không nhỏ
hơn sai số tương đối giới hạn của
a
.
GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
3
Có nghĩa là:
a
a
 

hay
a
A




Từ đây
a
A

 

Theo định nghĩa sai số tuyệt đối giới hạn, ta có thể chọn
a a

m m m n m n
A s s s s s s s
     

. Chữ số thứ
n
của
A
là số
1
m n
s
 
tính từ
trái qua phải. Kí hiệu
1 0 1 2 1
,
m m m n
a s s s s s s
    

là số làm tròn đến chữ số thứ
n
từ số
A
. Qui tắc
làm tròn như sau:
. Nếu
5
m n


thì
1 1
1
m n m n
s s
   
 
khi
1
m n
s
 
là số lẻ,
1 1
m n m n
s s
   

khi
1
m n
s
 
là số
chẵn
Từ qui tắc làm tròn ở trên ta thấy, sai số tuyệt đối giới hạn là:
1
1
5.10 10

là số làm tròn đến năm chữ số của số
e
nên ta có
0, 00001 0, 00005
  
nên
a
có năm chữ số tin cậy với số cuối cùng đã được làm tròn.
Với số
A
và
a
nói trong mục 0.2, ta sẽ thấy
1
1 1
2 10
n
m
a
s


 






 

0, 0025%
2 2 10
a


 


 



 


Ví dụ
Phải tính
3
29
với bao nhiêu chữ số thập phân để có
0,1%
a


. Ta thấy phần nguyên của số
này là 3. Do vậy áp dụng (1) ta được:
1
10
0, 001 4
6

m p
 
và
n p q
 
. Khi đó
ta được
0, 5.10
q
a

 

0.4. Sai số thực hiện các phép toán
0.4.1. Sai số của phép cộng
Xét tổng
1 2

n
u x x x
   
với
i
x
là các số gần đúng với sai số tương ứng là
i
x

. Hiển
nhiên là ta phải có:

x
cùng dấu thì có thể thấy:


1 2
max , , ,
n
u x x x
   


GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
5
Từ đây ta suy ra


1 2
max , , ,
n
u x x x
   


0.4.2. Sai số của phép trừ
Về nguyên tắc đánh giá (2) đúng cả cho phép trừ. Tuy nhiên, chúng ta xét riêng trường hợp
này để nhấn mạnh một điều rất cần chú ý khi lập trình. Xét hiệu số
1 2
u x x
 


  
ta phải lấy căn của
99, 99
tới 10 chữ số thập phân.
0.4.3. Sai số của phép nhân
Xét tích số
1 2

n
u x x x

với
0
i
x

. Giả sử
0, 1,
i
x i n
 
. Khi đó ta có
1 2
ln ln ln ln
n
u x x x
   

Mặt khác, ta cũng có
 

   
Từ đây ta có:

1 2
1 2

n
n
u x x x
u x x x
   
   
Hay là:
1 2

n
u x x x
   
   

Do vậy ta có thể lấy
1 2

n
u x x x
   
   

0.4.4. Sai số trong phép chia
Xét thương số

x

đã cho. Ta cần
đánh giá sai số tuyệt đối
u

qua các
i
x

. Coi các
i
x

là các đại lượng nhỏ, ta có thể dùng công
thức Taylor để đánh giá:
   
1 1 1
1 1
, , , ,
n n
n n n i i
i i
i i
f f
u f x x x x f x x x x
x x
 
 
          

  


(3)
Cũng từ biểu thức này, ta có thể nhận được
1
ln
n
i
i
i
u
u x
x



 


hay là
1
ln
i
n
u x
i
i
u
x

1
0, 5 233, 68; 302, 64
6
V V
d d
d


 
    
 

Sử dụng (3) ta được:
3
233, 68 0, 05 302, 64 0, 0016 12,2
12,2
1,3%
950, 3
V
V
V
cm
V

     

  

0.4.6. Bài toán xác định sai số ngược
GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]

    
. Khi đó từ (3) ta dễ dàng có:
1
; 1,
i
u
x
n
i
i
i n
u
x


  




Trường hợp 2: Giả sử ta có
; , 1,
i j
x x
i j
u u
i j n
x x
 
   

1 1
i
u i
u
x
n n
i i
i i
i i
x
u u
x x
x x

 


   
 
 
 

Ví dụ
Một hình trụ có bán kính đáy


2
r m

, chiều cao

 

  
      
  

Sử dụng (5) ta có:
 
0, 0009
3
V
r
m
V
r

  



Tương tự, ta tính được
   
0, 0027 ; 0, 0028
h
m m

   

cần thiết. Do đó, chúng ta cần quan tâm đến những phương pháp giải gần đúng, nhất là những
phương pháp có thể dùng máy tính hỗ trợ.
Để giải gần đúng phương trình (*), ta tiến hành các bước sau:
. Thứ nhất là tách nghiệm, nghĩa là tìm một khoảng


,
a b
đủ nhỏ sao cho phương trình (*) có
nghiệm duy nhất


*
,
x a b

.
. Thứ hai là chính xác hóa nghiệm gần đúng đến độ chính xác cần thiết.
Cơ sở để tách nghiệm là những kết quả sau đây mà bạn có thể bắt gặp ở tất cả các cuốn sách
về Giải tích.
Định lí 1.1.1. Giả sử


f x
liên tục trên


,
a b
và


0
f a f b

, hơn nữa, hàm số


f x
có đạo
hàm
 
f x

liên tục trên đoạn


,
a b
và
 
f x

không đổi dấu trên


,
a b
thì nghiệm nói trên là duy
nhất.
Bước tách (li) nghiệm thường được tiến hành nhờ phương pháp chia đôi hoặc phương pháp đồ

. Lại chia đôi đoạn


1 1
,
a b
và gọi


2 2
,
a b
là một trong hai đoạn con mà
GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
9




2 2
0
f a f b

; quá trình cứ thế tiếp tục, (nếu tại
i
a
mà


0


y f x

với trục hoành; hoặc ta biến đổi


0
f x

về dạng




x x
 

. Khi đó nghiệm của phương trình


0
f x

là hoành độ giao điểm của hai đồ thị


y x


và


GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
10
Bài 2. PHƯƠNG PHÁP LẶP ĐƠN Xét phương trình


0
f x

(1)
có khoảng li nghiệm là


,
a b
.
Ta biến đổi phương trình (1) về dạng tương đương:


x x


(2)
Với xấp xỉ ban đầu
0
x
thuộc khoảng

 
có giới hạn
*
lim
n
n
x x


thì
*
x
chính là nghiệm đúng của phương trình (2)
và cũng là nghiệm của (1)
Tiếp theo, ta tìm hiểu một số điều kiện để dãy


0,
n
n
x
 
hội tụ.
Định lí 1.2.1. Giả sử hàm số


y x


khả vi liên tục trên


thì dãy số


0,
n
n
x
 
được xây
dựng bởi hệ thức


1
, 0
n n
x x n


  
hội tụ đến nghiệm
*
x
của phương trình


0
f x

và ta có

Nhận xét: Phương pháp lặp đơn có tính chất tự điều chỉnh, nghĩa là nếu tại một vài bước tính
toán trung gian ta mắc phải sai số thì dãy


0,
n
n
x
 
vẫn hội tụ đến
*
x
, tất nhiên chỉ một vài bước sai
và sai số mắc phải không vượt ra ngoài đoạn.
Một tính chất đặc biệt của phép lặp này là có thể đánh giá ngay từ đầu số bước lặp mà ta cần
phải làm để có được độ chính xác theo yêu cầu. Thật vậy, từ biểu thức
*
0 1
1
n
n
L
x x x x
L
  


GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
11
nếu ta muốn có nghiệm gần đúng với sai số

 

 

Từ định lí 1.2.1 cho thấy, nếu
L
càng nhỏ thì tốc độ hội tụ càng nhanh, và tốc độ hội tụ của
phương pháp này rất chậm khi
L
càng gần 1.
Trên đây ta nhắc đến việc chuyển từ (*) sang dạng tương đương (**) sao cho điều kiện
 


' 1, ;
x L x a b

   
được thỏa mãn. Về vấn đề này có mấy nhận xét sau:
. Giả sử


0 '
m f x M
  
(với trường hợp


' 0
M f x m

3
1000 0
x x
  
(1)
Giải
Đặt
 
3
1000
f x x x
  
thì ta thấy




9 . 10 0
f f

. Mặt khác
 


2
3 1 0, 9,10
f x x x

    


x

 , vậy
 
2
2
1000
x
x
x



.
3
1000
x x
 
, vậy
 
3
3
1000
x x

 

Rõ ràng trong trường hợp 3,
 
3

4
10

, ta có thể coi
*
3
x x

.

Bài 3. PHƯƠNG PHÁP NEWTON (PHƯƠNG PHÁP TIẾP TUYẾN) Trong mục này, ta xét lại phương trình


0
f x

.
Giả sử rằng ta đã tìm được một khoảng li nghiệm của phương trình trên là khoảng


,
a b
, đồng
thời
   
,
f x f x

n




 











Ta có thể chứng minh được, với một số điều kiện thích hợp phương pháp Newton hội tụ,
chẳng hạn với điều kiện sau
Định lí 1.3.1. Nếu phương trình


0
f x

có


,
a b

x
,được gọi là điểm Fourier, thường được chọn là một trong hai đầu mút a hoặc b). Khi đó dãy


0,
n
n
x
 
xây dựng như trên hội tụ đến nghiệm
*
x
của phương trình


0
f x

và ta có ước lượng
2
*
1 1
2
n n n
M
x x x x
m
 
  
với

GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
13


 
1
0
0
n
n n
f x
x x
f x
n




 












f x x

 



Dễ thấy rằng




3 3 0
f f


nên ta chọn
0
3
x

. Ta xây dựng dãy


1,
n
n
x
 
như sau:






Với
0
3
x

, ta tính được


1 1
2.5600 1.6572
x f x
 



2 1
2.4662 0, 0668
x f x
 

4
3 3
2.4621 1.2501.10GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
14
Bài 4. PHƯƠNG PHÁP DÂY CUNG (THAM KHẢO) Trong mục này, ta phương trình


0
f x

.
Giả sử rằng ta đã tìm được một khoảng li nghiệm của phương trình trên là khoảng


,
a b
, đồng
thời
   
,
f x f x
 
liên tục và không đổi dấu trên đoạn



.
Trường hợp 1: Nếu


0
f a

, ta xây dựng dãy


0,
n
n
x
 
theo hệ thức:
 
 
 
 
0
1
n
n n n
n
x b
f x
x x x a
f x f a
n

đơn điệu giảm, bị chặn và:
*
1 0

n n
a x x x x b

      

Trường hợp 2: Nếu


0
f a

, ta xây dựng dãy


0,
n
n
x
 
theo hệ thức:
 
 
 
 
0
1

Khi đó ta sẽ có dãy


0,
n
n
x
 
đơn điệu giảm, bị chặn và:
*
0 1 1

n n
a x x x x x b

       

Định lý 1.4.1: Nếu phương trình


0
f x

có


,
a b
là khoảng li nghiệm, đồng thời
 



0
f x

và ta có ước lượng
*
1 1
n n n
M m
x x x x
m
 

  
với
,
m M
là hai hằng số thỏa mãn
GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
15
 


0 , ,
m f x M x a b

    

Ví dụ:

f x x x

  

    

Từ đây ta suy ra
 
1 6
f x

 
.
Dễ thấy


0 1 0
f
  
. Ta xét dãy


0,
n
n
x
 
được xây dựng như sau:

 

 


   


  




 




Từ đây ta tính được
6 7 8
0, 5428763, 0,543428, 0, 543605
x x x
  
.
Ta đánh giá sai số của
8
x
so với nghiệm đúng
* 4 3
8 8 7
6 1
0, 543605 0, 543428 8, 85.10 10
Nhiều vấn đề của khoa học kĩ thuật, kinh tế, môi trường quy về việc giải hệ phương trình
tuyến tính:
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2

n n
n n
m m mn n m
a x a x a x b
a x a x a x b
a x a x a x b

   




   







trường hợp
m n

và
det 0
A

. Cụ thể hơn, ta có:
det
det
j
j
A
x
A

Trong đó
j
A
là ma trận nhận được từ
A
bằng cách thay cột thứ
j
của
A
bằng ma trận cột hệ số tự do
b
. Tuy nhiên, ý nghĩa sử dụng thực tế công thức này chỉ có đối với
n
đủ nhỏ

17
 
1
0
0
sup . inf
x
x
Ax Ax
cond A
x x



   
 
 

 
 
 
 
 
   

làm đặc trưng cho ma trận
A
thì hệ phương trình với



Ax Ax Ax Ax
x x A x b
x x x x
  
   
       
   
   
      
   
   
   
   
   
       

Mặt khác
1 1 1
* * *
0 0 0 0
sup sup sup sup
x x x x
Ax Ax Ax Ax
x x Ax b
x x x x
  
   
       
   
   

 
 
 
 
 
 
 
   

Ước lượng trên chứng tỏ sai số tương đối của nghiệm có thể bằng tích của


cond A
với sai số
ở vế phải. Từ đó suy ra rằng với ma trận
A
thể trạng yếu thì nghiệm của nó thay đổi nhiều so với
những thay đổi nhỏ ở hệ số và các hạng số tự do. Như vây, giải hệ phương trình tuyến tính thể trạng
yếu là bài toán khó của toán học tính toán.
Các phương pháp giải hệ có thể phân làm hai nhóm chính: nhóm các phương pháp trực tiếp và
nhóm các phương pháp lặp. Đối với các phương pháp trực tiếp thì số các phép toán có thể dự đoán
trước được, còn đối với phương pháp lặp thì nói chung không thể dự đoán trước được số lần cần lặp
để có được nghiệm xấp xỉ với sai số mong muốn. Các phương pháp lặp thường được sử dụng đối với
hệ có số ẩn và số phương trình lớn, hệ gần suy biến hay thể trạng yếu. Sau đây, ta sẽ đi vào một số
phương pháp thông dụng để giải hệ phương trình.

   







   




Không mất tổng quát, chúng ta luôn giả thuyết
11
0
a

. Để ma trận
A
có dạng tam giác hoặc
là hình thang, đầu tiên, chúng ta làm cho các phần tử ở cột thứ nhất, dòng thứ hai trở đi biến thành
0

bằng cách nhân dòng một với
1
11
i
a





  









  



(*)
Trong đó:
'
1
1
11
i
ij ij j
a
a a a
a
 

1 2
0 0 0
n
x x x b
   
với
0
b


Khi đó hệ vô nghiệm
Chú ý:
1. Trong quá trình biến đổi trong hệ xuất hiện phương trình dạng
1 2
0 0 0 0
n
x x x
   

Khi đó, chúng ta có thể loại bỏ phương trình này ra khỏi hệ phương trình
2. Về mặt thực hành, để giải hệ phương trình tuyến tính bằng phương pháp khử ẩn liên tiếp, ta
làm như sau:
. Xác định ma trận hệ số mở rộng


|
A A b


. Sử dụng các phép biến đổi sơ cấp trên dòng để biến đổi sao cho ma trận hệ số



Giải
Bước 1: Lập ma trận hệ số mở rộng
A

 
2 1 3
4
| 1 2 1 0
3 0 2 1
A A b
 










  




 




   




 



 



 
1 2 1 0
2 1 3 4
3 0 2 1
 











d d d
d d d
 
 
 
 


 



 


















 

Bước 3: Khôi phục lại hệ phương trình
1 2 3
2 3
3
2 0
5 5 4
29
5
x x x
x x
x




  




 





 


21
Bài 2. PHƯƠNG PHÁP PHÂN RÃ (DECOMPOSITION METHOD) Xét lại phương trình
Ax b

với
A
là ma trận vuông cấp
n
. Giả sử ma trận
A
có thể biểu
diễn dưới dạng
A LU

trong đó
11
21 22
1 2
0 0
0
n n nn
l
l l
L
l l l
 


là một ma trận tam giác dưới, còn
U
là ma trận tam giác trên:
11 12 1
22 2
0
0 0
n
n
nn
u u u
u u
U
u
 














 






Vấn đề giải hệ phương trình trên rất đơn giản, đầu tiên là giải hệ
Ly b

để tìm
y
, sau đó với
y
vừa tìm được, ta giải hệ
Ux y


Trường hợp riêng :
a. Giải hệ bằng phương pháp Crout
Với phương pháp Crout thì ta cho
1, 1,
ii
u i n
 
, từ đó tìm các phần tử còn lại của ma trận
L
và
U
.
Sau đây ta sẽ dùng phương pháp Crout để phân rã ma trận cấp 3. Ta có
11


























 
 
 















   









 
 




  


31 12 32 32 32 32 31 12
l u l a l a l u
    13
11 13 13 13
11
a
l u a u
l
  

23 21 13
21 13 22 23 23 23
22
a l u
l u l u a u
l

   

31 13 32 23 33 33 33 33 31 13 32 23
l u l u l a l a l u l u
      

Bằng cách tương tự, ta có thể phân rã ma trận vuông cấp
n
. Cụ thể hơn, nếu
A









 


   


thì các phần tử của hai ma trận
,
L U
được xác định như sau:
1 1
1
1
11
, 1,2, ,
, 2, 3, ,
i i
j
j
l a i n
a
u j n

l


 


    





 


và
GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
23
1
1
n
nn nn nk kn
k
l a l u


 


Ví dụ: Giải hệ phương trình:

7 13
3
2 5
L
 














 











 
 

















 

Trước hết ta giải hệ
1 1
2 2
3 3
2
2 0 0 4
2
4 5 0 6
5



 




 


 


 
 


 

     
 
 




 
 



 




 

Tiếp theo, ta giải hệ
1 1
2 2
3 3
1 1
1
2
2 2
1
3 2
0 1 2
5 5
4
0 0 1 4
x x
x x
x x
 




 


 

 


 
    
 






 
 




 
 
 

 



   

24
Phương pháp Choleski là phương pháp phân rã ma trận đối xứng xác định dương. Với một ma
trận đối xứng xác định dương bất kì ta luôn có sự phân rã duy nhất
T
A U U


trong đó
11 12 1
22 2
0
0 0
n
n
nn
u u u
u u
U
u
 











, 2, 3, ,
, 2, 3, ,
1
, 2, 3, , ; 1, 2, ,
j
j
i
ii ii ki
k
i
ij ij ki kj
k
ii
u a
a
u j n
u
l a u j n
u a u u i n j i i n
u





 
  
 







1 1
1 1 1 1
T
T T
A U U U U U U
 
   
   với
U
là một ma trận tam giác trên. Vì
U
là một ma
trận tam giác trên nên
1
U

cũng là một ma trận tam giác. Ta giả sử


1
ij
U



, ta dễ dàng tính được GV: Huỳnh Hữu Dinh – Trường Đại học Công Nghiệp TPHCM Email: [email protected]
25
Bài 3. PHƯƠNG PHÁP LẶP ĐƠN 2.3.1. Phương pháp: Trong
n

người ta thường xét hai chuẩn quen thuộc sau:
1
1
1
max
i
i n
n
i
i
x x
x x

 











Để giải hệ phương trình
Ax b

(1) bằng phương pháp lặp đơn, ta biến đổi (1) về dạng:
x Bx g
 
(2)
Sau đó với


0
n
x


, ta thiết lập dãy




k
x
bằng cách đặt:


sẽ hội tụ đến nghiệm đúng
*
x
của hệ (1).
Phương pháp lặp xác định theo hệ thức (3) để giải hệ phương trình (1) được gọi là phương pháp lặp
đơn.
Sau đây ta xét một số điều kiện của ma trận
B
để dãy




k
x
hội tụ đến nghiệm đúng
*
x
của
(1).
2.3.2. Các định lí cơ bản:
Định lí 2.3.2.1 : Nếu
1
1
B

(hoặc
1
B


x x x x
B
 
  


hoặc
     
1 1*
1
k k k
B
x x x x
B
 

 

  

với
0
k
