外语学习-日语学习

1. Phát biểu bài toán:

Cho miền  là hình vuông có dạng  = (0,l) x (0,l), S là biên của . Phương trình elliptic có dạng:

uxx + uyy = f (x,y) trên 

u = g(x,y) trên S (1)

2. Phân rã bài toán :  Cho N, ta chia miền  thành (N+1)2 hình vuông cạnh là hcác điểm chia ( xm , yn ) = ( (m-1)h, (n-1)h ).

 Áp dụng công thức sai phân trung tâm để xấp xỉ (uxx + uyy) :

l với Nuxxuyy

u(xnh,ym)u(xnh,ym)u(xn,ymh)u(xn,ymh)4u(xn,ym)h2Đặt Umn = u( xn , ym ), fmn = f( xn , ym ) , ta có các phương trình sai phân

Umn1Um,n1Um1,nUm1,n4Um,nfmn 2m,nN 2hhay

Um,n1Um,n1Um1,nUm1,n4Um,nh2fm,n 2m,nN

 Tại các điểm trên biên, ta có:

Um,ng(xn,ym)khi m = 1 hoặc n = 1

Như vậy ta có được một hệ gồm ( N-1)2 phương trình và ( N-1)2 ẩn cần tìm là Umn , với 2  m,n  N .

 Đánh chỉ số lại theo cách : ( i , j )  ( N+1) ( i-1) + j ta viết lại U ở dạng vectơ và có hệ phương trình :

AU = B (2) * Hệ (2 ) có các tính chất sau : 1/- Số chiều của vectơ U bằng ( N-1)2

2/- Vectơ B xác định bởi các điều kiện biên và các số hạng không phụ thuộc U như fm,n , h .

3/- Ma trận A có cấp ( N-1)2  ( N-1)2 . Cấp của A là một hàm giảm theo h . Do đó , mặc dù các phần tử của A không phụ thuộc h nhưng các trị riêng của A, cũng như trị riêng của các ma trận dẫn xuất từ A, là hàm phụ thuộc h. A là một ma trận khối gồm (N-1)(N-1) ma trận con, A có dạng:

HI000IHI0IH0000II0HI000 IHTrong đó I là ma trận đơn vị cấp (N-1) và H là ma trận (N-1)  (N-1) có dạng

41000141014000011041000 144/- Nếu bài toán (1) ban đầu có duy nhất nghiệm và h đủ nhỏ, ma trận A

không suy biến, tức là hệ (2) có duy nhất nghiệm .

3. Phƣơng pháp lặp để giải hệ AU = b Ta hoàn toàn có thể giải hệ AU = b một cách trực tiếp (chẳng hạn bằng phương pháp khử Gauss). Tuy nhiên, khi ma trận A có kích thước quá lớn và

nhiều có phân tử nhiều phần tử bằng 0, người ta thường dùng phương pháp lặp để cài đặt vì phương pháp này tiết kiệm bộ nhớ và cho kết quả số chính xác hơn việc

k

giải trực tiếp. Phương pháp lặp sẽ tạo ra một dãy các nghiệm U xấp xỉ nghiệm chính xác. Các phương pháp lặp điểm để giải hệ (2) gồm có:  Phương pháp lặp điểm Jacobi

k1kkkkU(UUUU mnm1,nm,n1m1,nm,n1Fmn)/4 (3)

 Phương pháp lặp điểm Gauss Seidel Umnk1k1k1kk(UmUUU1,nm,n1m1,nm,n1Fmn)/4 (4)

 Phương pháp lặp điểm SOR. Uk1mnk1k1kk(UmUUU1,nm,n1m1,nm,n1Fmn)/4

Uk1m,nUk1m,nk1(1)Um,n(02) (5)

* Các tính chất của những phương pháp lặp điểm trên như sau: 1/ Các điều kiện biến được đảm bảo bằng cách đặt Umngmn tại các

điểm biên với mọi k = 0, 1, 2, . . . 2/ Trong 3 phương pháp trên, giá trị khởi tạo Umn có thể chọn tùy ý và khi k tiến về  , dãy Uk sẽ hội tụ về nghiệm chính xác.

3/ Ta có:

Fmn = - h2 fmn

4/ Trong phương pháp Jacobi, thứ tự duyệt các điểm nút không quan trọng. 5/ Trong phương pháp Gauss-Seidel, thứ tự duyệt các điểm nút rất quan trọng. Cụ thể ở đây, các nút sẽ được duyệt theo chiều tăng dần của các hàng, trên mỗi hàng duyệt theo chiều tăng dần của các cột, 6/ Phương pháp Gauss-Seidel khác phương pháp Jacobi ở chỗ: các giá trị mới của U sẽ được cập nhật ngay để tính những giá trị kế tiếp.

0k7/ Phương pháp SOR tuơng tự phương pháp Gauss-Seidel nhưng có đưa thêm hệ số  ( relaxation paraneter) để đẩy nhanh tốc độ hội tụ. Với = 1, ta có trở lại phương pháp Gauss-Seidel.

4. Sự hội tụ của phƣơng pháp lặp điểm: Viết ma trận A như sau: A = - L + D – U , trong đó L , D , U lần lượt là các ma trận tam giác trên ngặt , ma trận chéo và ma trận tam giác dưới ngặt . Ta giả sử thêm det (D) khác 0. Các phương pháp (2), (3), (4) được biểu diển dưới dạng ma trận như sau :

 Phương pháp lăp điểm Jacobi

Uk+1 = TJ Uk + CJ (5) ( Trong đó TJ = D-1 (L+U) , CJ = D-1B )  Phương pháp lặp điểm Gauss-Seidel :

Uk+1 = TG Uk + CG (6) (Trong đó TG = ( D-L)-1 U , CG = ( D-L)-1 B )  Phương pháp lặp điểm SOR:

Uk+1=TωUk+Cω (7) (Trong đó T(DL)1(1)DU,C(DL)1B )

Như vậy cả 3 phương pháp lặp đều có dạng tổng quát là:

Uk+1 = TUk + C

Xét ánh xạ:

F:(N1)2(N1)2UF(U)TUC

Ta thấy: Uk+1 = F (Uk) . Do F liên tục nên nếu U* là giới hạn của dãy Uk thì ***

ta có U = F( U*) , tức là U = TU + C. Như vậy, trong cả 3 phương pháp (5), (6), (7), nếu U* là giới hạn của dãy Uk thì rõ ràng AU* = b , nghĩa là U* là nghiệm của phương trình ban đầu.

Điều kiện để dãy Uk hội tụ được đề cập trong các định lý sau:

 Định lý 1: Dãy { Uk } xác định bởi Uk+1 = TUk + C , với U0 tùy ý, hội tụ về một vectơ duy nhất U* ( U* độc lập với U0 ) khi và chỉ khi (T) < 1 ( trong đó (T) là bán kính phổ của ma trận T, tức là

(T) = max {  |  là trị riêng (phức) của ma trận T }  Nhận xét: Ta không chứng minh chính xác định lý trên, tuy nhiên ta sẽ nêu một vài điểm liên quan để làm rõ định lý hơn. Xét ánh xạ F như trên:

F:(N1)2(N1)2UF(U)TUC

Như vậy , Uk+1 = F (Uk). Điều kiện đủ để dãy Uk hội tụ là ánh xạ F co, nghĩa là: tồn tại 1 sao cho

F(V1)F(V2)V1V2

Mặt khác, ta thấy:

F(V1)F(V2) = T(V1V2)T.V1V2

Như vậy nếu chuẩn của T nhỏ hơn 1 thì điều kiện hội tụ của dãy Uk được đảm bảo. Ứng với mỗi chuẩn của vectơ U trong (N1), ta có chuẩn tương ứng cho

2ma trận T : Tsup{ T(U)|U1}. Như vậy một ma trận T có nhiều chuẩn và các chuẩn này đều tương đương. Ta nhắc lại định lý:

(T)inf||.|| T

Khi (T)1, do định nghĩa của inf, tồn tại chuẩn || T || sao cho || T || nhỏ hơn 1. Lúc đó F là ánh xạ co và dãy Uk hội tụ . Như vậy ta đã thấy (T)1 chính là điều kiện đủ để dãy Uk hội tụ.



Khi ma trận A có dạng (*), người ta chứng minh được rằng

(TG)(TJ)1,(T)1 khi 02 , tức là các phương pháp lặp điểm Jacobi, Gauss-Seidel và SOR hội tụ về nghiệm chính xác khi k tiến về vô cùng.

5. Tốc độ hội tụ: Từ phần nhận xét ở định lý 1 ta cũng thấy được mối quan hệ giữa tốc độ hội tụ và bán kinh phổ (T). Ta có

UkUTkU(0)U

Điều này đúng với mọi chuẩn của T nên ta có thể xấp xỉ

U(k)U[(T)]kU(0)U

Như vậy (T)càng nhỏ thì tốc độ hội tụ càng cao.

 Định nghĩa 1: Tốc độ hội tụ = - log10 [(T)]

Để so sánh tốc độ hội tụ của các phương trình lặp , ta cần tính (TJ), (TG) và (T) . Ta có bảng tổng kết sau : Phương pháp Tốc độ hội tụ Tốc độ hội tụ tiệm cận Jacobi lặp điểm - log (cos h) 1h2() 2h h2 2Gauss-Seidel lặp điểm - log (cos2 h) SOR lặp điểm tối ưu h1sin-log  h1sinVới ma trận A có dạng (*) , người ta chứng minh được rằng, relaxation number ; 2 sẽ cực đại hóa tốc độ hội tụ ( tức là cực tiểu hóa 211(TJ)p SOR với relaxation number  (T) ) của phương pháp SOR. Phương phá

này được gọi là phương pháp SOR tối ưu. Hơn nữa, với ma trận A dạng (*), ta tính được (Tj)cos

6. Đánh giá sai số:  Định nghĩa 2: (Vec tơ thặng dư) Rk = b – AUk

Trên thực tế, ta không biết nghiệm chính xác nên không thể tính được sai số

UUk. Vì vậy, ta sẽ đánh giá sai số thông qua vector thặng dư Rk . Rõ rang, nếu Uk là nghiệm của phương trình thì Rk = 0. Do đó, khi || Rk || nhỏ thì một cách hợp lý

k

ta có thể cho rằng || U-U|| cũng nhỏ. Điều này không phải luôn luôn đúng, tuy nhiên, ta có nhận xét :

h.

UUkA1RkA1.Rk

Kết hợp với: bAUA.U, ta được

UUkURk.A1.Ab

Do đó, trong những trường hợp ma trận A là ma trận điều kiện tốt ( nghĩa là

A1.A tương đối nhỏ) thì Rk nhỏ sẽ dẫn đến sai số tương đối của || U-Uk ||

nhỏ.

Trong quá trình cài đặt matlab để tính Uk , ta đặt điều kiện để dừng vòng lặp là k lớn hơn một số K cho trước hoặc Rk nhỏ hơn một sai số  cho trước.