Top 4 # Xem Nhiều Nhất Phương Pháp Lặp Đơn Trong Phương Pháp Tính Mới Nhất 3/2023 # Top Like

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 PHẠM ANH NGHĨA PHƯƠNG PHÁP LẶP ĐƠN VÀ PHƯƠNG PHÁP NEWTON – KANTOROVICH GIẢI HỆ PHƯƠNG TRÌNH PHI TUYẾN LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 PHẠM ANH NGHĨA PHƯƠNG PHÁP LẶP ĐƠN VÀ PHƯƠNG PHÁP NEWTON – KANTOROVICH GIẢI HỆ PHƯƠNG TRÌNH PHI TUYẾN Chuyên ngành: Toán Giải Tích Mã số: 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: chúng tôi KHUẤT VĂN NINH HÀ NỘI, 2015 – 1 – LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học sư phạm Hà Nội 2 dưới sự hướng dẫn của thầy giáo chúng tôi Khuất Văn Ninh. Sự giúp đỡ và hướng dẫn tận tình của thầy trong suốt quá trình thực hiện luận văn này đã giúp tác giả rất nhiều trong cách tiếp cận một vấn đề mới. Tác giả xin bày tỏ lòng biết ơn, kính trọng sâu sắc nhất đối với thầy. Tác giả cũng trân trọng cảm ơn Ban Giám hiệu trường Đại học sư phạm Hà Nội 2, Phòng Sau đại học, các thầy cô giáo trong nhà trường, các thầy cô giáo dạy cao học chuyên ngành Toán Giải tích đã giúp đỡ, tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập, nghiên cứu và hoàn thành luận văn. Hà Nội, tháng 11 năm 2015 Tác giả Phạm Anh Nghĩa – 2 – LỜI CAM ĐOAN Tác giả xin cam đoan luận vănThạc sĩ chuyên ngành Toán Giải tích với đề tài: ” Phương pháp lặp đơn và phương pháp Newton – Kantorovich giải hệ phương trình phi tuyến” là công trình nghiên cứu của riêng tác giả dưới sự hướng dẫn của chúng tôi Khuất Văn Ninh. Trong suốt quá trình nghiên cứu và hoàn thành luận văn, tác giả đã kế thừa thành quảkhoa học của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 11 năm 2015 Tác giả Phạm Anh Nghĩa – 3 – MỤC LỤC Mở đầu…………………………………………………………………….. 5 Chương 1. Một số kiến thức chuẩn bị……………………………………… 7 1.1. Không gian metric, nguyên lý ánh xạ co…………………………… 7 1.1.1. Không gian metric…………………………………………….. 7 1.1.2. Nguyên lý ánh xạ co…………………………………………….. 18 1.2. Không gian Banach………………………………………………. 20 1.3. Phép tính vi phân trong không gian Banach……………………… 23 Chương 2. Phương pháp lặp đơn, phương pháp Newton – Kantorovich giải hệ phương trình phi tuyến…………………………………………….. 29 2.1.Phương pháp lặp đơn giải hệ phương trình phi tuyến……………………. 29 2.1.1. Phương pháp lặp đơn giải phương trình phi tuyến…………….. ..29 2.1.2. Phương pháp lặp đơn giải hệ phương trình phi tuyến………….. 37 2.2. Phương pháp Newton – Kantorovich giải hệ phương trình phi tuyến………………………………………………………………………. 45 2.2.1. Phương pháp Newton – Kantorovich giải phương trình toán tử phi tuyến ……………………………………………………………………….. 45 2.2.2. Phương pháp Newton – Kantorovich giải hệ phương trình phi tuyến trong n ……………………………………………………………… 51 2.3. Sự kết hợp của phương pháp lặp đơn và phương pháp Newton – Kantorovich giải hệ phương trình phi tuyến ………………………………. 56 Chương 3. Ứng dụng…………………………………………………….. 61 3.1. Giải hệ phương trình phi tuyến ………………………………….. 61 3.1.1. Phương pháp lặp đơn giải hệ phương trình phi tuyến …………. 61 3.1.2. Phương pháp Newton – Kantorovich giải hệ phương trình phi tuyến ……………………………………………………………………….. 64 – 4 – 3.2. Lập trình trên Maple giải số hệ phương trình phi tuyến…………… 75 Kết luận………………………………………………………………………………………….. 88 Tài liệu tham khảo……………………………………………………………………………. 89 – 5 – MỞ ĐẦU 1. Lý do chọn đề tài Như chúng ta đã biết khi giải số phương trình vi phân, phương trình tích phân thường dẫn đến giải hệ phương trình phi tuyến; có nhiều vấn đề, nhiều bài toán trong khoa học tự nhiên, trong kỹ thuật, kinh tế cũng có thể dẫn đến việc nghiên cứu nghiệm của hệ phương trình. Hệ phương trình thường có dạng tổng quát A.x  f (1), trong đó A là các toán tử đi từ không gian định chuẩn  n vào không gian định chuẩn  n . Trong thực tế người ta khó tìm được nghiệm chính xác của hệ phương trình . Vì vậy việc giải xấp xỉ hệ phương trình (1) là một vấn đề được quan tâm nghiên cứu. Có nhiều phương pháp giải xấp xỉ phương trình đã được đề xuất và sử dụng như : Phương pháp lặp,phương pháp Newton và các mở rộng, phương pháp biến phân ….Người ta xét đến những đặc thù của toán tử Ađể chọn phương pháp xây dựng nghiệm xấp xỉ của phương trình. Phương pháp lặp dựa trên nguyên lí ánh xạ co Banach là phương pháp thường được sử dụng để chứng minh sự tồn tại nghiệm của phương trình và tìm nghiệm xấp xỉ thông qua phép lặp đơn. Để sử dụng phương pháp này người ta phải đưa phương trình (1) về dạng x = Bx trên một hình cầu đóng nào đó hoặc trên toàn không gian  n , sao cho nghiệm của phương trình (1) là điểm bất động của ánh xạ B. Bước tiếp theo là tìm điểm bất động của ánh xạ đó. Nguyên lí điểm bất động cũng chỉ ra cách tìm xấp xỉ điểm bất động. Phương pháp Newton và các mở rộng của nó như Newton – Raphson, Newton – Kantorovich cho ta cách tìm nghiệm xấp xỉ của một phương trình phi tuyến thông qua việc giải những phương trình tuyến tính. Phương pháp Newton và các mở rộng có ưu điểm là bậc hội tụ cao, tuy nhiên phải biết thông tin về một hình cầu đủ nhỏ chứa nghiệm. – 6 – Với mong muốn tìm hiểu và nghiên cứu sâu hơn về các phương pháp giải xấp xỉ hệ phương trình (1), nên em đã chọn đề tài : ” Phương pháp lặp đơn và phương pháp Newton – Kantorovich giải hệ phương trình phi tuyến” để thực hiện luận văn của mình. 2. Mục đích nghiên cứu Luận văn trình bày một số phương pháp giải hệ phương trình đó là phương pháp lặp đơn, phương pháp Newton – Kantorovich, sự kết hợp của hai phương pháp đó trong giải phương trình trong tập số thực  và hệ phương trình phi tuyến trong không gian  n . Ứng dụng giải một số phương trình và hệ phương trình cụ thể. 3. Nhiệm vụ nghiên cứu Nghiên cứu phương pháp lặp đơn, phương pháp Newton – Kantorovich giải phương trình và hệ phương trình phi tuyến. 4. Đối tượng và phạm vi nghiên cứu – Đối tượng nghiên cứu: Phương pháp giải hệ phương trình phi tuyến. – Phạm vi nghiên cứu: Phương pháp lặp đơn, phương pháp Newton – Kantorovich, sự kết hợp của hai phương pháp đó hệ phương trình phi tuyến trong không gian  n ; ứng dụng vào giải các phương trình và hệ phương trình cụ thể. 5. Phương pháp nghiên cứu – Vận dụng các kiến thức, phương pháp của Giải tích hàm, Giải tích số và áp dụng phần mềm Maple trong tính toán và vẽ đồ thị . 6. Dự kiến đóng góp của đề tài Hệ thống lại phương pháp lặp đơn và phương pháp Newton – Kantorovich giải phương trình và hệ phương trình phi tuyến. Áp dụng giải một số hệ phương trình phi tuyến cụ thể. – 7 – CHƯƠNG I MỘT SỐ KIẾN THỨC CHUẨN BỊ 1.1 Không gian metric, nguyên lý ánh xạ co 1.1.1.Không gian metric Định nghĩa 1.1.1. Xét một tập hợp X   cùng với một ánh xạ d : X  X   thoả mãn các tiên đề sau đây: 1) d  x, y   0,(x, y  X) , d  x, y  0  x  y ( tiên đề đồng nhất); 2) d  x, y   d  y, x  ,(x, y  X) ( tiên đề đối xứng); 3) d  x, y   d  x, z   d  z, y  ,  x, y, z  X  ( tiên đề tam giác). Khi đó tập hợp X cùng với ánh xạ d gọi là một không gian metric. Ánh xạ d gọi là một metric trên X , số d  x, y  gọi là khoảng cách giữa hai phần tử x, y . Các phần tử của X gọi là các điểm; các tiên đề 1), 2), 3) gọi là hệ tiên đề metric. Không gian metric được kí hiệu là X   X,d  . Định nghĩa 1.1.2. Cho không gian metric X   X,d  . Một tập con bất kỳ X0   của tập hợp X cùng với metric d trên X lập thành một không gian metric. Không gian metric X 0   X 0 , d  gọi là không gian metric con của không gian metric đã cho. Ví dụ 1.1.1. Với hai phần tử bất kỳ x,y ∈ℝ ta đặt: d  x, y   x  y (1.1.1) Từ tính chất của giá trị tuyệt đối trong tập hợp số thực ℝ, suy ra hệ thức (1.1.1)xác định một metric trên  , không gian tương ứng được ký hiệu là 1 .Ta gọi metric (1.1.1) là metric tự nhiên trên  . – 8 – Ví dụ 1.1.2. Với hai phần tử bất kỳ x   x1 , x 2 ,…, x k  , y   y1 , y2 ,…, yk  thuộc không gian véc tơ thực k chiều  k ( k là số nguyên dương nào đó) ta đặt: k d  x, y   x 2 j  y j  (1.1.2) j1 Dễ dàng thấy hệ thức (1.1.2) thoả mãn các tiên đề 1), 2) về metric. Để kiểm tra hệ thức (1.1.2) thoả mãn tiên đề 3) về metric, trước hết ta chứng minh bất đẳng thức Cauchy – Bunhiacopski: Với 2k số thực a j ,bj ,  j  1, 2,…, k  ta có k k Thật vậy k  a 2j .  a jb j  j1 j1 b j1 2 j (1.1.3) k  k k k k k k k 2 0     a i b j  a jbi     a i2 b2j  2 a i bi a jb j   a 2j bi2 i 1  j1 i 1 j1 i 1 j1  i1 j1 2  k  k   k   2   a 2j    b 2j   2   a j b j    j1   j1   j1 Từ đó suy ra bất đẳng thức (1.1.3). Với 3 véc tơ bất kỳ x   x1 , x 2 ,…, x k  , y   y1 , y2 ,…, yk  , z   z1 , z2 ,…, zk  thuộc  k ta có : 2 k 2 k d  x, y     x j  y j     x j  z j    z j  y j   j1 k j1 2 k k j1 j1 2    x j  z j   2  x j  z j  z j  y j     z j  y j  j1 = d2  x, z   2d  x, z  d  z, y   d2  z, y  2   d  x, z   d  z, y    d  x, y   d  x, z   d  z, y  Do đó hệ thức (1.1.2) thoả mãn tiên đề 3) về metric. – 9 – Vì vậy hệ thức (1.1.2) xác định một metric trên không gian  k . Không gian metric tươg ứng vẫn ký hiệu là  k và thường gọi là không gian Euclide, còn metric (1.1.2) gọi là metric Euclide.  Ví dụ chúng tôi ký hiệu  2 là tập tất cả các số thực hoặc phức x  x n n 1 sao 2  cho chuỗi số dương  x n hội tụ . n 1   Với hai dãy số bất kỳ x  x n n 1 , y  yn n 1 ta đặt  d  x, y   x 2 n  yn (1.1.4) n 1 Hệ thức (1.1.4) xác định một ánh xạ d :  2   2   . Thật vậy, với mọi n  1, 2,… ta có 2 2 2  2 x n  yn  x n2  2x n .yn  y2n  x n  2 x n . yn  yn  2 x n  yn 2  Do đó mọi số p dương đều có 2 p  n 1 Suy ra p 2 p 2 2   x n  y n  2 x n  2 y n  2 x n  2 y n n 1 2   n 1 2  n 1 2 n 1 2 x n  2 y n  x n  y n  2 n 1 n 1 n 1 Nghĩa là chuỗi số trong vế phải của hệ thức (1.1.4) hội tụ. Dễ dàng thấy hệ thức (1.1.4) thoả mãn các tiên đề 1), 2) về metric.    Với ba dãy số bất kỳ x  x n n 1 , y  yn n 1 , z  zn n 1 thuộc  2 và với số p nguyên dương tuỳ ý ta có: p 1 2 p   2  x n  yn     x n  z n  z n  yn  n 1   n 1  2 1 2    – 10 – 1 1 2 2  p  p 2 2   x n  z n     z n  y n  .   n 1   n 1 Cho p   ta được  1 2 1 2   1 2    2 2 2 d(x, y)    x n  y n     x n  z n     z n  y n   d  x, z   d  z, y   n 1   n 1   n 1  Do đó hệ thức (1.1.4)thoả mãn tiên đề 3) về metric. Vì vậy hệ thức (1.1.4) xác định một metric trên  2 . Không gian metric tương ứng vẫn ký hiệu là  2 . Không gian metric  2 đôi khi còn gọi là không gian Euclide vô hạn chiều. Ví dụ 1.1.4. Ta ký hiệu C a ,b  là tập tất cả các hàm số giá trị thực xác định và liên tục trên đoạn a,b ,    a  b   . Với hai hàm số bất kỳ x  t  , y  t   Ca,b ta đặt d  x, y   max x  t   y  t  . (1.1.5) atb Vì các hàm x  t  , y  t  liên tục trên đoạn a,b , nên hàm số x  t   y  t  cũng liên tục trên đoạn a,b .Do đó hàm số này đạt giá trị lớn nhất trên đoạn a,b . Suy ra hệ thức (1.1.5) xác định một ánh xạ từ Ca ,b   Ca ,b   . Dễ dàng thấy ánh xạ (1.1.5) thoả mãn các tiên đề về metric. Không gian metric tương ứng vẫn kí hiệu là C a ,b  . Ví dụ 1.1.5. Ta ký hiệu L a ,b  là tập tất cả các hàm số giá trị thực và khả tích Lebesgue trên đoạn a,b .Với hai hàm số bất kỳ x  t  , y  t   La ,b ta đặt b d  x, y    x  t   y  t  dt a Hệ thức (1.1.6) xác định một ánh xạ từ L a ,b   L a ,b    . (1.1.6) – 11 – Với hai hàm số bất kỳ x  t  , y  t   La ,b ta có b x  t   y  t   0, t   a, b  d  x, y    x  t   y  t   0 a b d  x, y  0   x  t   y  t   0 a  x  t   y  t   0 h.k.n trên  a,b  x  t   y  t  h.k.n trên  a, b. Vì tích phân Lebesgue của một hàm số không thay đổi khi ta thay đổi giá tri của hàm số đó trên tập có độ đo Lebesgue bằng 0, nên trong không gian La, b ta đồng nhất hai hàm số khi chúng chỉ khác nhau trên một tập có độ đo Lebesgue bằng 0. Nhờ đó ánh xạ (1.1.6) thoả mãn tiên đề 1) về metric. Dựa vào các tính chất của tích phân Lebesgue dễ dàng suy ra ánh xạ (1.1.6) thoả mãn các tiên đề 2), 3) về metric. Vì vậy ánh xạ (1.1.6) xác định một metric trên tập L a ,b  . Không gian tương ứng vẫn ký hiệu là L a ,b  . Định nghĩa chúng tôi không gian metric X   X,d  ,dãy điểm xn   X , điểm x 0  X . Dãy điểm x n  gọi là hội tụ tới điểm x 0 trong không gian X khi n  , nếu   0, n0  N* , n  n0 , d(xn ,x0 )   . x n  x 0 hay xn  xo (n ) Kí hiệu: xlim  Điểm x o còn gọi là giới hạn của dãy x n  trong không gian X. Ví dụ 1.1.6. Sự hội tụ của một dãy điểm x n  trong không gian 1 là sự hội tụ của dãy số thực đã biết trong giải tích toán học. Ví dụ 1.1.7. Sự hội tụ của một dãy điểm trong không gian Eukleides  k tương đương với sự hội tụ theo toạ độ. – 12 – Thật vậy, giả sử dãy điểm x  n    x1 n  , x 2n  ,…, x kn   , n  1, 2,… hội tụ tới điểm x   x1 , x 2 ,…, x k  trong  k . Theo định nghĩa ,   0, n0  * , n  n0 , ta có:  k    x   x  d xn , x  n j 2 j  j1 Suy ra x jn   x j  , n  n 0 , j  1, 2,3,…, k (1.1.7) Các bất đẳng thức (1.1.7) chứng tỏ , với mỗi j  1, 2,…, k dãy số thực x jn   hội tụ tới số thực x j khi n  . Sự hội tụ đó được gọi là sự hội tụ theo toạ độ . Ngược lại, giả sử dãy điểm x  n    x1 n  , x 2n  ,…, x kn   , n  1, 2,… hội tụ theo toạ độ 0 , với mỗi j  1, 2,…, k , tới điểm x   x1, x 2 ,…, x k  . Theo định nghĩa ,  n j  * , n  n j , x jn   x j   . n n Đặt n0  max n1, n 2 ,…, n k  , thì n  n0 , x j  x j    x jn   x j  2  k 2 ,  j  1, 2,…, k    x jn   x j n j1   2  , j  1, 2,…, k n k  2    x   x  n j j 2   , n  n0 . j1 Do đó dãy điểm đã cho hội tụ theo metric Euclide của không gian  k . Ví dụ 1.1.8. Sự hội tụ của một dãy điểm trong không gian C a ,b  tương đương với sự hội tụ đều của dãy hàm liên tục trên đoạn a,b . Thật vậy, giả sử dãy hàm  x n  t    Ca,b hội tụ tới hàm x  t  trong không gian C a ,b  . Theo định nghĩa   0, n 0  N* , n  n 0 , d  x n , x   max x n  t   x  t    atb Suy ra : xn  t   x  t   , n  n0 , t  a,b (1.1.8) – 13 – Các bất đẳng thức (1.1.8) chứng tỏ dãy hàm số liên tục  x n  t   hội tụ đều tới hàm số x  t  trên đoạn  a, b. Ngược lại, giả sử hàm số  x n  t    Ca,b hội tụ đều tới hàm số x  t  trên đoạn a, b , nghĩa là x  t   Ca,b . Theo định nghĩa sự hội tụ đều của dãy hàm   0,  n 0  N * , n  n 0 ,  t   a, b  , x n  t   x  t    x n  t   x  t   , n  n 0 Suy ra: max a t b Hay : d  x n , x   , n  n 0 Do đó dãy số  x n  t   hội tụ tới hàm số x  t  theo metric của không gian C a ,b  . Ví dụ 1.1.9. Sự hội tụ của dãy điểm trong không gian metric rời rạc X  (X, d) tương đương với sự hội tụ của dãy dừng. Thật vậy, giả sử dãy điểm xn   X hội tụ đến điểm x trong không gian X. * Theo định nghĩa,   0,   1, n0  N , n  n0 ,d  x n , x   . Suy ra d  x n , x   0, n  n0  x n  x, n  n 0 . Dãy điểm như thế gọi là dãy dừng. * Ngược lại, dãy điểm xn   X là dãy dừng, nghĩa là n0  N , n  n0 , xn  xn 0 , thì hiển nhiên dãy đó hội tụ theo metric của không gian X . Định nghĩa 1.1.4. Cho không gian metric X   X,d  , a  X , r  0 , Tập hợp S(a, r)  x  X : d  x, a   r được gọi là hình cầu mở tâm a, bán kính r. Tập hợp S'(a, r)  x  X : d  x, a   r được gọi là hình cầu đóng tâm a, bán kính r. Mỗi hình cầu mở S(a, r) được gọi là một lân cận của phần tử a trong X . – 14 – Định nghĩa chúng tôi hai không gian metric X  (X,d1 ) , Y  (Y,d2 ). Ánh xạ f : X  Y được gọi là liên tục tại điểm x0  X nếu như   0,   0 , sao cho x  X thoả mãn d1(x, x0 )   thì d2 (f (x),f (x0 ))   . Hay nói cách khác Ánh xạ f : X  Y gọi là liên tục tại điểm xo  X , nếu với lân cận cho trước tuỳ ý Uf (x )  S y0 ,    Y của điểm y0  f  x 0  trong Y 0 tìm được lân cận Vx  S x0 ,  của điểm x 0 trong X sao cho f(Vx )  Uy . 0 0 0 Định nghĩa 1.1.6. Ánh xạ f : X  Y gọi là liên tục tại điểm x0  X nếu với mọi dãy điểm xn   X hội tụ tới điểm x 0 trong X kéo theo dãy điểm  f (x n )  hội tụ tới điểm f  x0  trong Y. x n  x 0 và f  x  là hàm liên tụctại điểm x0  X thì Như vậy nếu: nlim  lim f  x n   f  x 0  . n  Định nghĩa 1.1.7.Ánh xạ f gọi là liên tục trên tập A  X nếu ánh xạ f liên tục tại mọi điểm x  A. Khi A  X thì ánh xạ f gọi là liên tục. Định nghĩa 1.1.8. Ánh xạ f gọi là liên tục đều trên tập A  X nếu   0,   0 sao cho  x, x ‘  A thoả mãn d1 (x, x ‘)   thì d2 (f (x),f (x ‘))  . Định nghĩa 1.1.9.Một dãy điểm x n  trong không gian metric X   X,d  gọi lim d(x n , xm )  0 Nghĩa là   0 , là một dãy Cauchy hay dãy cơ bản nếu: m,n  n0 * sao cho d(x n , x m )  , n, m  n0 ( Rõ ràng mọi dãy hội tụ đều là dãy Cauchy). Định nghĩa 1.1.10.Không gian metric X= (X,d) là một không gian đầy (hay đủ) nếu mọi dãy cơ bản trong không gian này đều hội tụ. – 15 – Ví dụ 1.1.10.Không gian metric 1 là không gian đầy, điều đó suy ra từ tiêu chuẩn Cauchy về sự hội tụ của dãy số thực đã biết trong giải tích toán học. Ví dụ 1.1.11. Không gian  k là không gian đầy. Thật vậy, giả sử x  n    x1 n  , x 2n  ,…, x kn   , n  1, 2,… là dãy cơ bản tuỳ ý trong không gian Euclide  k . Theo định nghĩa dãy cơ bản,    0, n 0  N* , m, n  n 0 , d x   , x   x j   x j n m n m k    hay   x    x   n j m j 2  j1 (1.1.9)  , m, n  n 0 , j  1, 2, …, k Các bất đẳng thức (1.1.9) chứng tỏ, với mỗi j  1, 2,…, k , dãy  x jn   là dãy số thực cơ bản, nên phải tồn tại giới hạn: lim x jn   x j , ( j  1, 2,…, k). n  Đặt x   x1, x 2 ,…, x k  , ta nhận được dãy x  n     k đã cho hội tụ theo toạ độ tới x . Nhưng sự hội tụ trong không gian Euclide  k tương đương với sự hội tụ theo toạ độ, nên dãy cơ bản x  n   đã cho hội tụ tới x trong không gian  k . Vậy không gian Euclide  k là không gian đầy. Ví dụ 1.1.12. Không gian C a ,b  là không gian đầy. Thật vậy, giả sử  x n  t   là dãy cơ bản tuỳ ý trong không gian C a ,b  , theo định nghĩa dãy cơ bản:     0 ,  n 0  N * ,  m, n  n 0 , d x  n  , x  m   max x n  t   x m  t    a tb  x n  t   x m  t   , m, n  n0 , t  a, b . (1.1.10) Các bất đẳng thức (1.1.10) chứng tỏ , với mỗi t cố định tuỳ ý thuộc đoạn a,b , dãy  x n  t   là dãy số thực cơ bản , nên phải tồn tại giới hạn – 16 – lim x n  t   x  t  , t  a, b n Ta nhận được hàm số x  t  xác định trên đoạn a,b . Vì các đẳng thức (1.1.10) không phụ thuộc t, nên qua giới hạn trong các đẳng thức này khi n  ta được: x n  t   x  t   , n  n 0 , t  a, b  (1.1.11) Các bất đẳng thức (1.1.11) chứng tỏ dãy hàm số  x n  t    Ca,b hội tụ đều tới hàm số x  t  trên đoạn  a,b nên x  t   Ca,b . Nhưng sự hội tụ trong không gian C a ,b  tương đương với sự hội tụ đều của dãy hàm liên tục trên đoạn a,b , nên dãy cơ bản  x n  t   đã cho hội tụ tới x  t  trong không gian C  a ,b  . Vậy C a ,b  là không gian đầy. Ví dụ 1.1.13. Không gian  2 là không gian đầy. Thật vậy, giả sử x  n    x1 n  , x 2n  ,…, x kn   , n  1, 2,… là dãy cơ bản tuỳ ý trong  2 , theo định nghĩa dãy cơ bản :      x   x     0, n 0  N* , m, n  n 0 , d x  n  , x  m   n k m k 2  . k 1 Suy ra p   x   x m k n k k 1 x k   x k n m  2  , m, n  n 0 , p  1, 2,… (1.1.12)  , m, n  n 0 , k  1, 2,… (1.1.13) Các bất đẳng thức (1.1.13) chứng tỏ, với mỗi k cố định tuỳ ý dãy  x kn   là dãy số cơ bản, nên phải tồn tại giới hạn: nlim  xkn    x k , k  1, 2,…  – 17 – Đặt x   x1 , x 2 ,…, x k ,…   x k  . Vì các bất đẳng thức (1.1.12) không phụ thuộc vào p , nên có thể cho qua giới hạn trong các bất đẳng thức này khi m   ta được: p  x   x n k 2  , n  n 0 , p  1, 2,… k k 1 (1.1.14) Tiếp tục cho qua giới hạn trong các bất đẳng thức (1.1.14) khi p   ta được  2  xkn   x k  , n  n0 Mặt khác k 1  2 x k  x k  x kn   x kn  2  x n k (1.1.15)  x k  x kn  2  2 2  2 x kn   2 x kn   x k ,  k, n  1, 2,… (1.1.16) Từ các bất đẳng thức (1.1.15), (1.1.16) suy ra: p  p 2 k 1 k 1   p 2 2 x k  2 x kn1   2 x kn1   x k k 1  n1   2 x k k 1 2 2   n1   2 k 1  2  2 x k  x k  2 x kn1   2 2 , với n1  n 0 k 1 2   x k  2 x k 1   2 2 , với n1  n 0 k 1 n k 1 Do đó dãy x   x k   2 .Các bất đẳng thức (1.1.15) chứng tỏ, dãy cơ bản  x   đã cho hội tụ tới x  trong không gian  n 2 Vì vậy không gian  2 là không gian đầy. 2 . – 18 – 1.1.2. Nguyên lý ánh xạ co Định nghĩa 1.1.11. Cho không gian metric X  (X, d) .Ánh xạ A : X  X được gọi là ánh xạ co nếu tồn tại số α, 0    1 sao cho: d(Ax1,Ax2 )  d(x1, x2 ), x1 , x 2  X. Định lý 1.1.1.( Nguyên lý Banach về ánh xạ co) Mọi ánh xạ co A từ không gian metric đầy X  (X, d) vào chính nó đều có một điểm bất động duy nhất, nghĩa là tồn tại duy nhất một điểm x*  X sao cho Ax*  x* ; điểm x* là giới hạn của dãy x n  được xây dựng bởi công thức: x n  Ax n 1 , x 0 tuỳ ý, x 0  X và công thức đánh giá sai số d(x n , x * )  d(x n , x * )  n d(x1 , x 0 ), n  1, 2,… 1   d(x n , x n 1 ) , n  1, 2,… 1  Trong đó  là hệ số co của ánh xạ co A. Chứng minh. Lấy một điểm bất kỳ x0  X . Xây dựng dãy x n  xác định bởi công thức: x n  Ax n 1 , n  1, 2,… Ta được d(x2 , x1 )  d(Ax1,Ax0 )  d(x1, x0 )  d(Ax0 , x0 ) 2 d(x 3 , x 2 )  d(Ax 2 , Ax1 )  d(x 2 , x1 )   d(Ax 0 , x 0 ) … n d(x n 1 , x n )  d(Ax n , Ax n 1 )  d(x n , x n 1 )  …   d(Ax 0 , x 0 ) ,với n  1, 2, … Từ đó ta suy ra  n, p  1, 2,… ta có

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

VŨ THỊ VUI

PHƯƠNG PHÁP LẶP GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH SỐ CHIỀU LỚN

LUẬN VĂN THẠC SĨ TOÁN HỌC

Hà Nội – 2015

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

VŨ THỊ VUI

PHƯƠNG PHÁP LẶP GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH SỐ CHIỀU LỚN

Chuyên ngành: Toán giải tích Mã số: 60 46 01 02

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học: TS. Hà Bình Minh

Hà Nội – 2015

Lời cảm ơn Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của thầy giáo TS. Hà Bình Minh. Sự giúp đỡ và hướng dẫn tận tình, nghiêm túc của thầy trong suốt quá trình thực hiện luận văn này đã giúp tôi trưởng thành hơn rất nhiều trong cách tiếp cận một vấn đề mới. Tôi xin bày tỏ lòng biết ơn, lòng kính trọng sâu sắc nhất đối với thầy. Tôi xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư phạm Hà Nội 2, phòng Sau đại học, các thầy cô giáo trong nhà trường đã giúp đỡ, tạo điều kiện thuận lợi cho tôi trong suốt quá trình học tập. Tôi xin chân thành cảm ơn gia đình, người thân, bạn bè đã giúp đỡ, động viên và tạo điều kiện thuận lợi để tôi hoàn thành khóa học Thạc sĩ cũng như hoàn thành luận văn này.

Hà Nội, ngày 09 tháng 06 năm 2015 Tác giả

Vũ Thị Vui

Lời cam đoan Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của TS. Hà Bình Minh. Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi. Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự trân trọng và biết ơn. Tôi xin cam đoan rằng các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc.

Hà Nội, ngày 09 tháng 06 năm 2015 Tác giả

Vũ Thị Vui

i

i

Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

Chương 1. Một số phương pháp lặp cổ điển . . . . . . . . . . . . . . .

3

1.1. Phương pháp Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.2. Điều kiện hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.1.3. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2. Phương pháp Gauss – Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.2.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.2.2. Điều kiện hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2.3. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

Chương 2. Các phương pháp Krylov . . . . . . . . . . . . . . . . . . . . .

14

2.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2. Phương pháp Gradient liên hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.3. Phương pháp GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.3.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.3.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.4. Phương pháp QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.4.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.4.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

2.5. Phương pháp Bi-CGSTAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.5.1. Giới thiệu phương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.5.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

ii

Chương 3. Ứng dụng của phương pháp lặp . . . . . . . . . . . . . . .

39

3.1. Ứng dụng trong giải phương trình Poisson . . . . . . . . . . . . . . . . . .

39

3.2. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

Phụ lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

1

Mở đầu 1. Lí do chọn đề tài Nhiều bài toán trong thực tế đòi hỏi phải giải hệ phương trình tuyến tính cỡ lớn có dạng Ax b, trong đó A là ma trận có số chiều lớn và thưa (tức là chỉ có một số ít các phần tử khác 0). Chẳng hạn, những hệ phương trình này xuất hiện ta giải bài toán biên của phương trình đạo hàm riêng bằng các phương pháp rời rạc hóa, như phương pháp sai phân hoặc phương pháp phần tử hữu hạn. Những phương pháp cổ điển để giải hệ phương trình tuyến tính, chẳng hạn như phương pháp khử Gauss, sẽ rất khó có thể áp dụng để giải những hệ này. Lý do là vì phương pháp khử Gauss được áp dụng cho ma trận đặc và khi áp dụng cho ma trận thưa sẽ làm cho số phép toán trở nên rất lớn, không thể thực hiện nổi đối với máy tính thông thường. Hơn nữa, số lượng bộ nhớ sử dụng cho phương pháp Gauss cũng trở nên rất lớn. Với những lý do nêu trên, phương pháp lặp giải hệ phương trình tuyến tính cỡ lớn được nghiên cứu từ lâu. Theo phương pháp này, bắt đầu từ một vector khởi tạo xp0q , ta sẽ sinh ra một dãy các vector

xp0q

Ñ xp1q Ñ xp2q Ñ . . .

hội tụ đến nghiệm x. Quá trình sinh vector xpk 1q từ vector xpkq sử dụng phép nhân ma trận A với một vector nào đó. Phép nhân này rất tiết kiệm do A là ma trận thưa và chỉ cần số ít bộ nhớ để lưu trữ. Hai phương pháp lặp được biết đến nhiều nhất theo hướng này là phương pháp Jacobi và phương pháp Gauss-Seidel. Bên cạnh đó, một lớp các phương pháp lặp được phát triển trong thời gian gần đây là lớp các phương pháp Krylov. Đặc trưng của lớp các phương pháp này quá trình lặp sẽ hội tụ đến nghiệm chính xác sau một số hữu hạn bước lặp. Cụ thể, quá trình lặp sẽ cho nghiệm xpkq sẽ là xấp xỉ tốt nhất

2

nghiệm của hệ Ax b trong không gian Krylov k chiều. Một số phương pháp lặp thuộc lớp này phải kể đến là: phương pháp gradient liên hợp của Hestenes và Stiefel (1952) cho hệ tuyến tính có ma trận A đối xứng xác định dương; phương pháp GMRES của Saad và Schultz (1986); phương pháp QMR của Freund và Nachtigal (1991); và phương pháp Bi-CGSTAB của van der Vorst (1992).

2. Mục đích và nhiệm vụ nghiên cứu Khảo cứu một số phương pháp lặp dùng để giải hệ phương trình tuyến tính cỡ lớn, và áp dụng để nghiệm số cho phương trình đạo hàm riêng.

3. Đối tượng và phạm vi nghiên cứu Hệ phương trình tuyến tính cỡ lớn, phương trình vi phân đạo hàm riêng.

4. Phương pháp nghiên cứu Sử dụng các phương pháp giải số, ngôn ngữ lập trình MATLAB,…

5. Đóng góp mới của đề tài Áp dụng phương pháp lặp để giải hệ phương trình tuyến tính cỡ lớn, sau đó lập trình, thực hiện các phương pháp này bằng phần mềm MATLAB.

3

CHƯƠNG 1

Một số phương pháp lặp cổ điển Nội dung của chương này được tham khảo chủ yếu từ các tài liệu [1, 2].

1.1. Phương pháp Jacobi 1.1.1. Giới thiệu phương pháp Xét hệ phương trình tuyến tính

Ax b,

(1.1)

được khai triển dưới dạng sau:

.

..

an1 an2

Để sử dụng phương pháp lặp Jacobi, ta giả thiết rằng ma trận A có tính chéo trội, được định nghĩa như sau: Định nghĩa 1.1.1 (Ma trận chéo trội). Ma trận A được gọi là có tính chéo trội nếu giá trị tuyệt đối của các phần tử nằm trên đường chéo chính lớn hơn tổng các giá trị tuyệt đối của các phần còn lại nằm trên cùng hàng, tức là ņ j 1,j i

(1.2)

4

Ví dụ 1.1.1. Ma trận

A

,

là ma trận chéo trội. Trong phương pháp lặp Jacobi, trước hết, ta biến đổi hệ (1.1) về dạng sau:

aii xi

ñ

aij xj

bi, pi 1, nq,

¸

ñ

xi

x Bx

B

g

(1.3)

j

Ý tưởng của phương pháp lặp Jacobi là tính một dãy các vector xp0q , xp1q , . . . ,

xpnq , . . . dựa trên phương trình (1.3), cụ thể như sau: Phương pháp lặp Jacobi: Đầu vào: Ma trận A, b.

Đầu ra: Dãy xp0q , xp1q , . . . , xpnq , . . . . Với B , g xác định bởi (1.3), ta chọn vector khởi tạo xp0q và xác định các phần tử của dãy xp0q , xp1q , . . . , xpnq , . . . theo các bước sau:

5

Bxp0q Tính xp2q Bxp1q

* Bước 1: Tính xp1q * Bước 2: …

* Bước k: Tính xpkq

Bxpk1q

g.

1.1.2. Điều kiện hội tụ Một phép lặp Jacobi chỉ đem lại hiệu quả khi vector xpkq hội tụ đến

nghiệm chính xác x . Điều kiện để một dãy sinh bởi phép lặp Jacobi hội tụ được nêu trong Định lý 1.1.1. Định lí 1.1.1. Xét phương trình x Bx g và vector khởi tạo xp0q cho trước. Nếu }B } 1 với một chuẩn nào đó, thì sẽ tồn tại x sao cho

x

kÑlim8 xpkq là nghiệm chính xác của (1.1). Hơn nữa, vector xpkq trong

phép lặp

g,

Bxp1q

g,

Bxpk1q

xpkq

g,

sẽ hội tụ tới nghiệm duy nhất x . Hơn nữa, sai số giữa xpkq và nghiệm chính xác x được đánh giá bằng các công thức sau:

}xpkq x} ¤ 1 }B}}B } }xpkq xpk1q},

(1.4)

hoặc

}xpkq x}

(1.5)

6

Ta sẽ áp dụng định lý trên cho phép lặp Jacobi. Trong phép lặp Jacobi, ma trận B được cho bởi

0 ann ann Ta thấy rằng nếu A là ma trận chéo trội thì

}B }8 : 1max ¤i¤n

nên theo Định lý 1.1.1, phép lặp Jacobi là hội tụ. Như vậy, Điều kiện cần để Phương pháp lặp Jacobi hội tụ là A là ma trận chéo trội.

1.1.3. Ví dụ số minh họa Ví dụ 1.1.2. Tìm nghiệm gần đúng của hệ phương trình sau:

7

* Bước 2: Đưa hệ về dạng x Bx

g như sau:

x2 0.03 0 0.05 x2

x3 0.01 0.02 0 x3 loooooooooooooomoooooooooooooon

B

* Bước 3: Kiểm tra điều kiện hội tụ }B }8

}B }8

0.06

g.

0.02; 0.03

0.05; 0.01

0.02

maxp0.08; 0.08; 0.03q 0.08 1.

Vậy điều kiện hội tụ được thỏa mãn.

* Bước 4: Chọn vector khởi tạo xp0q

2 3 5

T

0q

, rồi tính xp1q , xp2q , . . .

theo Phương pháp lặp Jacobi, ta được bảng kết quả sau:

xp0q

xp1q

xp2q

xp3q

3

3.19

1.9094

3.1944

1.909228

3.194948

5

5.04

5.0446

5.044794

* Đánh giá sai số: giả sử ta xem xp3q là nghiệm gần đúng cần tìm, ta sẽ đánh giá sai số giữa xp3q và nghiệm chính xác x theo công thức (1.4) như sau:

}xp3q x}8 ¤ 1 }B}}B8} }xp3q xp2q}8 8 ¤ 1 0.08 maxp0.000172; 0.000548; 0.000194q 0.08 0.0000476 5 105.

8

1.2. Phương pháp Gauss – Seidel 1.2.1. Giới thiệu phương pháp Tương tự như phương pháp lặp Jacobi, ta biến đổi hệ (1.1) về dạng sau:

aii xi

aij xj

bi, pi 1, nq,

ñ

xi

B1

ñ

x B1 x

(1.6)

.

..

B2

B2 x

g

(1.7)

trong đó

B2

j

j

9

Ý tưởng của phương pháp lặp Gauss-Seidel là tính dãy các vector xp0q , xp1q , . . . , xpnq , . . . , dựa trên phương trình (1.7), như sau: Phương pháp lặp Gauss-Seidel: Đầu vào: Ma trận A, b.

Đầu ra: Dãy xp0q , xp1q , . . . , xpnq , . . . . Với B1 , B2 , g cho bởi (1.7), ta chọn vector khởi tạo xp0q và xác định các phần tử tiếp theo của dãy như sau:

B1xp1q Tính xp2q B1 xp2q

* Bước 1: Tính xp1q * Bước 2: …

* Bước k: Tính xpkq

B1xpkq

B2 xp0q

g.

B2 xp1q

g.

B2 xpk1q

g.

Trong bước thứ k , do B1 là ma trận tam giác dưới nên phép nhân B1 xpkq

pkq

pkq

1.2.2. Điều kiện hội tụ Phương pháp Gauss-Seidel sẽ hội tụ khi ma trận A là chéo trội. Ta có định lý sau: Định lí 1.2.1. Nếu ma trận A có tính chéo trội thì phương pháp GaussSeidel sẽ hội tụ. Chứng minh. Vì ma trận A có tính chéo trội, nên }B }8 B pbij qn1 , với $

1, trong đó

10

Áp dụng Định lý 1.1.1 suy ra phương trình (1.3) có nghiệm x duy nhất. Để đánh giá sai số, ta xét hiệu

Suy ra

j ¡i

pkq x q.

bij pxj

j

°

¸

0

0

(1.8)

0

0

hay

k xpk 1q x k8 ¤ trong đó ν

γi0 k xpkq x k8 ¤ ν k xpkq x k8 , 1 βi0

Vì

βi

γi

nên

γi

βi p1 βi γi q

γi 1max ¤ max pβ γiq }B }8 1. ¤i¤n 1 βi 1¤i¤n i Từ (1.9) suy ra k xpkq x k8 Ñ 0, pk Ñ 8q. ν

(1.9)

11

Nhận xét: 1. Điều kiện hội tụ của phương pháp lặp Gauss-Seidel cũng giống với phương pháp lặp Jacobi. Phương pháp Gauss-Seidel nói chung hội tụ nhanh hơn phương pháp Jacobi. 2. Phương pháp Gauss – Seidel tiết kiệm bộ nhớ, vì các thành phần vừa tính được, được sử dụng ngay để tính các thành phần tiếp theo.

1.2.3. Ví dụ số minh họa Ví dụ 1.2.1. Tìm nghiệm gần đúng của hệ phương trình sau theo phương pháp lặp Gauss-Seidel:

Các ma trận tham số của hệ Ax b tương ứng là:

A 0.09

12

* Bước 2: Đưa hệ về dạng x B1 x

B2 x

g như sau:

x2 0.03 0 0 x2

0 0 0.05 x2 3

g

B2

B1 x

B2 x

g.

* Bước 3: Kiểm tra điều kiện hội tụ }B }8

}B }8

0.06

0.02; 0.03

0.05; 0.01

0.02

maxp0.08; 0.08; 0.03q 0.08 1.

Vậy điều kiện hội tụ được thỏa mãn.

* Bước 4: Chọn vector khởi tạo xp0q

2 3 5

T

0q

, rồi tính xp1q , xp2q , . . .

theo Phương pháp lặp Gauss-Seidel, ta được bảng kết quả sau:

xp0q

3

5

xp2q

xp3q

1.9093489

3.194952

1.909199

3.1949643

5.0448056

5.0448073

* Đánh giá sai số: giả sử ta xem xp3q là nghiệm gần đúng cần tìm, ta sẽ đánh giá sai số giữa xp3q và nghiệm chính xác x theo công thức sau: }xp3q x}8 ¤ 1 ν ν }xp3q xp2q}8. Ta có

}xp3q xp2q}8 maxp0.0001499; 0.000123; 0.0000017q 0.0001499,

13

ν

Như vậy

}xp3q x}8 ¤ 1 0.08 0.0001499 1.3 105 . 0.08

14

CHƯƠNG 2

Các phương pháp Krylov Nội dung của chương này được tham khảo chủ yếu từ tài liệu [2], mục 8.7.

2.1. Giới thiệu Xét hệ phương trình tuyến tính

Ax b, với A là ma trận thực không suy biến. Bắt đầu từ một vector xp0q , phương pháp Krylov sẽ sinh ra một dãy các vector

xp0q

Ñ xp1q Ñ Ñ xpmq,

tiến tới nghiệm chính xác xpmq

m ¤ n.

x : A1b sau nhiều nhất m bước, với

Các Phương pháp Krylov: sử dụng phép lặp để sinh ra dãy txpkq u thỏa mãn

xpkq

P xp0q

Kk prp0q , Aq, với mọi k

1, 2, . . . ,

trong đó Kk prp0q , Aq là không gian Krylov được định nghĩa như sau:

Kk prp0q , Aq : spanrrp0q , Arp0q , . . . , Ak1 rp0q s, k

1, 2, . . .

SIM có nghĩa là gì? SIM là viết tắt của Thưa thớt phương pháp lặp đi lặp lại. Nếu bạn đang truy cập phiên bản không phải tiếng Anh của chúng tôi và muốn xem phiên bản tiếng Anh của Thưa thớt phương pháp lặp đi lặp lại, vui lòng cuộn xuống dưới cùng và bạn sẽ thấy ý nghĩa của Thưa thớt phương pháp lặp đi lặp lại trong ngôn ngữ tiếng Anh. Hãy nhớ rằng chữ viết tắt của SIM được sử dụng rộng rãi trong các ngành công nghiệp như ngân hàng, máy tính, giáo dục, tài chính, cơ quan và sức khỏe. Ngoài SIM, Thưa thớt phương pháp lặp đi lặp lại có thể ngắn cho các từ viết tắt khác.

SIM = Thưa thớt phương pháp lặp đi lặp lại

Tìm kiếm định nghĩa chung của SIM? SIM có nghĩa là Thưa thớt phương pháp lặp đi lặp lại. Chúng tôi tự hào để liệt kê các từ viết tắt của SIM trong cơ sở dữ liệu lớn nhất của chữ viết tắt và tắt từ. Hình ảnh sau đây Hiển thị một trong các định nghĩa của SIM bằng tiếng Anh: Thưa thớt phương pháp lặp đi lặp lại. Bạn có thể tải về các tập tin hình ảnh để in hoặc gửi cho bạn bè của bạn qua email, Facebook, Twitter, hoặc TikTok.

Như đã đề cập ở trên, SIM được sử dụng như một từ viết tắt trong tin nhắn văn bản để đại diện cho Thưa thớt phương pháp lặp đi lặp lại. Trang này là tất cả về từ viết tắt của SIM và ý nghĩa của nó là Thưa thớt phương pháp lặp đi lặp lại. Xin lưu ý rằng Thưa thớt phương pháp lặp đi lặp lại không phải là ý nghĩa duy chỉ của SIM. Có thể có nhiều hơn một định nghĩa của SIM, vì vậy hãy kiểm tra nó trên từ điển của chúng tôi cho tất cả các ý nghĩa của SIM từng cái một.

Ý nghĩa khác của SIM

Bên cạnh Thưa thớt phương pháp lặp đi lặp lại, SIM có ý nghĩa khác. Chúng được liệt kê ở bên trái bên dưới. Xin vui lòng di chuyển xuống và nhấp chuột để xem mỗi người trong số họ. Đối với tất cả ý nghĩa của SIM, vui lòng nhấp vào “thêm “. Nếu bạn đang truy cập phiên bản tiếng Anh của chúng tôi, và muốn xem định nghĩa của Thưa thớt phương pháp lặp đi lặp lại bằng các ngôn ngữ khác, vui lòng nhấp vào trình đơn ngôn ngữ ở phía dưới bên phải. Bạn sẽ thấy ý nghĩa của Thưa thớt phương pháp lặp đi lặp lại bằng nhiều ngôn ngữ khác như tiếng ả Rập, Đan Mạch, Hà Lan, Hindi, Nhật bản, Hàn Quốc, Hy Lạp, ý, Việt Nam, v.v.

Phương pháp tính giá trong kế toán áp dụng cho mọi loại hình từ thương mại dịch vụ cho tới sản xuất.

Phương pháp tính giá trong kế toán được tổng hợp trong tài liệu nguyên lý kế toán là những phần căn bản nhất mà một kế toán viên giỏi cần phải nắm vững nguyên tắc để thực hiện công tác kế toán trong doanh nghiệp

Vai trò của phương pháp tính giá trong kế toán

Tính giá tài sản có ý nghĩa hết sức quan trọng , ảnh hưởng đến việc thực hiện các phương pháp kế toán khác và cung cấp thông tin cho quản lý . Vai trò của tính giá được thể hiện qua các điểm sau :

+ Đảm bảo theo dõi , tính toán được các đối tượng của hạch toán kế toán (phản ánh chính xác tài sản của doanh nghiệp theo tài sản và nguồn hình thành của tài sản).

+ Có thể tính toán chính xác chi phí từ đó xác định được hiệu quả sản xuất kinh doanh .

+ Cung cấp thông tin cần thiết về tình hình tài chính của doanh nghiệp .

Yêu cầu tính giá

Tính giá tài sản cần quán triệt các yêu cầu sau :

– Chính xác : giá trị của tài sản được tính phải phù hợp với giá thị trường , với chất lượng , số lượng của tài sản

-Thống nhất : nhằm đảm bảo đánh giá đúng hiệu quả kinh tế giữa các doanh nghiệp trong nền kinh tế ở từng thời kỳ khác nhau .

– Đầy đủ , kịp thời : Tính giá phải đảm bảo tính đầy đủ các yếu tố tạo nên giá trị tài sản ; tất cả các loại tài sản cần được tính giá và kết quả tính giá phải kịp thời phục vụ cung cấp thông tin cho quản lý .

Nguyên tắc tính giá

1/ Xác định đối tượng tính giá phù hợp:

Đối tượng tính giá cần phải phù hợp với đối tượng thu mua, sản xuất, tiêu thụ. Đối tượng tính giá có thể là từng loại vật tư , hàng hoá , tài sản mua vào , sản phẩm , dịch và thực hiện , …

Tuỳ theo yêu cầu quản lý và nhu cầu về thông tin kế toán mà đối tượng tính giá có thể được mở rộng hoặc thu hẹp

2/ Phân loại chi phí một cách hợp lý:

– Chi phí là bộ phận cơ bản cấu tạo nên giá của tài sản . Có nhiều loại chi phí khác nhau nên cần phải phân loại chi phí một cách hợp lý để có thể tính giá một cách chính xác . Nói cách khác , để có thể tính giá tài sản chính xác , cần xác định được các loại chi phí cấu thành nên giá trị của tài sản đó .

Có một số cách phân loại chi phí dựa trên các căn cứ cơ bản sau :

– Căn cứ trên lĩnh vực phát sinh chi phí :

+ Chi phí bán hàng : bao gồm toàn bộ các chi phí phát sinh phục vụ cho việc tiêu thụ sản phẩm, hàng hóa, lao vụ, dịch vụ như chi phí nhân viên bán hàng , chi phí vật liệu bao gói , chi phí khấu hao , chi phí bảo hành sản phẩm , hàng hóa,..

+ Chi phí quản lý doanh nghiệp : bao gồm toàn bộ chi phí mà doanh nghiệp đã bỏ ra nhằm duy trì việc tổ chức, điều hành và quản lý hoạt động chung của toàn bộ doan nghiệp : các chi phí điện , nước , điện thoại , văn phòng phải phục vụ công tác quản lý DN , lương nhân viên quản lí DN, chi phí khấu hao …

– Căn cứ trên quan hệ với khối lượng sản phẩm sản xuất:

+ Biến phí : là các chi phí có tổng số biến đổi tỉ lệ thuận với số lượng sản phẩm sản xuất.

+ Định phí : là các chi phí có tổng số không thay đổi khi số lượng sản phẩm sản xuất thay đổi trong phạm vi công suất thiết kế

3/ Lựa chọn tiêu thức phân bổ chi phí thích hợp

Công thức phân bổ chi phí:

Chi phí phân bổ cho từng đối tượng = (Tổng chi phí từng loại cần phân bổ / Tổng tiêu thức phân bổ của tất cả các đối tượng) x Tổng tiêu thức phân bổ của từng đối tượng

Tuỳ theo từng điều kiện cụ thể mà kế toán lựa chọn tiêu thức phân bổ thích hợp (có thể dựa trên mối quan hệ giữa chi phí với đối tượng tính giá ) .

Các mô hình tính giá cơ bản

1/Mô hình tính giá tài sản mua vào

-Bước 1 : Xác định giá mua ghi trên hoá đơn của người bán .

Trường hợp đơn vị được khấu trừ thuế GTGT đầu vào khi mua tài sản , giá mua được tính là giá hoá đơn không bao gồm thuế GTGT đầu vào . Trường hợp thuế GTGT đầu vào ghi trên hoá đơn mua tài sản không được khấu trừ , giá mua sẽ là tổng giá thanh toán bao gồm cả thuế GTGT đầu vào.

– Bước 3 : Tổng hợp chi phí và tính ra giá ban đầu ( giá thực tế) của tài sản

Công thức tính giá tài sản mua vào có thể khái quát như sau :

Tổng giá trị tài sản mua = Giá hoá đơn + Thuế nhập khẩu + Thuế TTĐB hàng nhập khẩu + Thuế bảo vệ môi trường + Chi phí thu mua – Chiết khấu thương mại được hưởng – Giảm giá hàng mua

Giá đơn vị tài sản mua = Tổng giá trị tài sản mua / số lượng tài sản mua

Trong công thức trên, chiết khấu thương mại được hưởng và giảm giá hàng mua chỉ trừ ra khỏi giá mua của tài sản khi chúng phát sinh sau thời điểm đã tiếp nhận hoá đơn . Trong trường hợp giá mua ghi trên hoá đơn đã trừ chiết khấu thương mại và giảm giá thì kế toán không trừ đi khi tính giá tài sản một lần nữa .

2/ Mô hình tính giá các loại tài sản mua vào chủ yếu được khái quát như sau :

a/ Mô hình tính giá nguyên vật liệu , công cụ , hàng hoá mua vào .

b/ Mô hình tính giá tài sản cố định mua ngoài

– Giá mua ( giá hoá đơn + thuế nhập khẩu (nếu có))

– Giá xây dựng , lắp đặt ( giá quyết toán được duyệt )

– Giá cấp phát .

– Giá thị trường tương đương .

– Chi phí vận chuyển , bốc dỡ .

– Chi phí lắp đặt , chạy thử

– Tiền thuê , chi phí kho hàng , bến bãi .

– Lệ phí trước bạ .

– Hoa hồng môi giới

NGUYÊN GIÁ TÀI SẢN CỐ ĐỊNH MUA SẮM , XÂY DỰNG

Giá trị còn lại của TSCĐ đang sử dụng

Giá trị hao mòn của tài sản cố định

Ví dụ: DN mua chịu 2.500kg nguyên vật liệu theo giá hoá đơn có thuế GTGT 10 % là 65.000 đồng/kg. Chi phí vận chuyển nguyên vật liệu về kho doanh nghiệp thanh toán bằng tiền mặt 6.600.000 đồng ,trong đó thuế GTGT 10 %.Theo ví dụ này , giá trị nguyên vật liệu mua được tính như sau :

Tổng giá trị nguyên vật liệu mua=(2.500 * 65.000)+6.000.000 = 168.500.000 đồng

Giá 1 kg nguyên vật liệu mua = 168.500.000 / 2.500=67.400 đồng / kg

c/ Mô hình tính giá sản phẩm, dịch vụ sản xuất

Việc tính giá sản phẩm , dịch vụ sản xuất sẽ hình thành nên giá thành sản xuất của sản phẩm , dịch vụ . Trình tự tính giá thành sản phẩm ,dịch vụ sản xuất bao gồm các bước sau:

– Bước 2 : Tập hợp và phân bổ chi phí sản xuất chung cho các đối tượng tính giá

– Bước 3 : Xác định giá trị sản phẩm dở dang cuối kỳ .

– Bước 4 : Tính ra tổng giá thành sản phẩm và giá thành đơn vị sản phẩm.

Công thức tính giá thành sản phẩm , dịch vụ sản xuất :

Tổng Zsp = Gía trị SPDD đầu kỳ + CPSX thực tế PS trong kỳ – Giatrị SPDD cuối kỳ .

Z đơn vị SP = Tổng Zsp /Số lượng SP , dịch vụ hoàn thành .

Ví dụ : Một doanh nghiệp có tài liệu như sau ( Đơn vị : 1.000 đồng ) :

– Giá trị sản phẩm dở dang đầu tháng : 46.500 .

– Chi phí sản xuất phát sinh trong tháng bao gồm : Giá trị vật tư sử dụng 182.000 , chi phí tiền lương công nhân sản xuất 67.000 , chi phí khấu hao máy móc , thiết bị sản xuất 22.000 , chi phí điện nước 7.500 , chi phí công cụ dụng cụ sản xuất 4.400 , chi phí tiền lương nhân viên quản lý phân xưởng 9 600 .

– Giá trị sản phẩm dở dang cuối tháng : 34.000

– Cuối tháng , doanh nghiệp hoàn thành nhập kho 160 sản phẩm , còn dở dang 45 sản phẩm .

Theo tài liệu trên , giá thành sản xuất được tính như sau

Tổng giá thành sản xuất sản phẩm = 46.500 +182.000 + 67.000 + 22.000 + 7.500 + 4.400 + 9.600 – 34.000 = 305.000

Giá thành sản xuất đơn vị = 305.000 / 160 = 1.906.25 ( nghìn đồng / sản phẩm )

d/ Mô hình tính giá gốc sản phẩm , dịch vụ tiện thụ và vật tư xuất dùng cho sản xuất kinh doanh

Tính giá gốc sản phẩm , dịch vụ tiêu thụ hình thành nên giá vốn hàng bán , tính giá gốc vật tư xuất dùng hình thành nên chi phí sản xuất kinh doanh . Trình tự tính giá gốc sản phẩm , dịch vụ , hàng hoá tiêu thụ và giá vật tư xuất dùng cho sản xuất kinh doanh gồm các bước sau :

– Bước 1 : Xác định số lượng sản phẩm , hàng hoá , dịch vụ tiêu thụ theo từng loại , chi tiết cho từng khách hàng ,cùng với số lượng vật liệu,công cụ đã xuất dùng cho sản xuất kinh doanh.

– Bước 2 : Xác định giá đơn vị của từng loại hàng xuất bán , xuất dùng (với sản phẩm , dịch vụ : Giá thành sản xuất; với hàng hoá : Đơn giá mua ; với vật tư xuất dùng : Giá thực tế xuất kho )

Để xác định giá đơn vị của hàng xuất bán , xuất dùng kế toán có thể sử dụng một số phương pháp sau đây:

– Phương pháp giá đơn vị thực tế đích danh : Phương pháp này xác định giá trị hàng tồn kho xuất bằng cách lấy số lượng hàng tồn kho xuất nhân với giá đơn vị của lần nhập kho hàng tồn kho tương ứng . Hay nói cách khác , hàng lượng hàng tồn kho nào có ở gần thời điểm xuất nhất sẽ được dùng để tính giá hàng tồn kho xuất , nếu lượng hàng tồn kho của lần nhập đó không tồn kho nhập theo giá nào thì khi xuất được tính đúng theo giá đó . Như vậy, phương pháp này có ưu điểm là kết quả tính toán đạt độ chính xác rất cao nhưng đòi hỏi đơn vị phải tách riêng hàng tồn kho giữa các lần nhập kho khác nhau .

– Phương pháp Nhập trước – Xuất trước : Phương pháp này tính giá hàng tồn kho xuất trên cơ sở giả định rằng lượng hàng tồn kho nào có trước sẽ được xuất sử dụng trước . Giá đơn vị của lượng hàng tồn kho nhập đầu tiên sẽ được dùng để tính giá hàng tồn kho xuất , nếu lượng hàng tồn kho của lần nhập đó không đủ để xuất thì tính theo giá của lần nhập tiếp theo . Giá trị hàng tồn kho tồn cuối kỳ sẽ là giá của những lần nhập kho sau cùng .

– Phương pháp Nhập sau – Xuất trước : Phương pháp này tính giá hàng tồn kho xuất trên cơ sở giả định rằng lượng hàng tồn kho nào có ở gần thời điểm xuất nhất sẽ được xuất sử dụng trước . Giá đơn vị của lượng hàng tồn kho nhập gần thời điểm xuất nhất sẽ được dùng để tính giá hàng tồn kho xuất,nếu lượng hàng tồn kho của lần nhập đó không đủ để xuất thì tính theo giá của lần nhập trước đó. Giá trị hàng tồn kho cuối kỳ sẽ là giá của những lần nhập đầu tiên trong kỳ.(Phương pháp này hiện không được áp dụng trong Chế độ kế toán doanh nghiệp của Việt Nam ) .

– Phương pháp Giá đơn vị bình quân : Theo phương pháp này , giá trị hàng tồn kho xuất được xác định trên sở lấy số lượng hàng tồn kho xuất nhân với giá đơn vị bình quân . Phạm vi tính giá đơn vị bình quân của hàng tồn kho có thể là cuối kỳ trước , sau mỗi lần nhập hoặc cả kỳ hiện . Nhìn chung , phương pháp giá đơn vị bình quân có ưu điểm là tính toán đơn giản nhưng độ chính xác không cao.

– Bước 3 : Phân bổ phí thu mua cho hàng tiêu thụ ( với kinh doanh thương mại) theo tiêu thức phù hợp ( số lượng khối lượng , doanh thu , trị giá mua )

– Bước 4 : Nhân số lượng sản phẩm , hàng hóa xuất bán , vật tư xuất dùng với giá đơn vị của từng loại tương ứng . Đối với kinh doanh thương mại thì cộng thêm với chi phí thu mua đã phân bổ cho hàng hóa tiêu thụ.

Công thức tính giá vật tư, sản phẩm, hàng hóa xuất:

Giá trị vật tư xuất ( Chi phí vật tư ) = Số lượng vật tư xuất* Giá đơn vị vật tư xuất

Giá trị sản phẩm, hàng hóa xuất bán ( Giá vốn ) = Số lượng sản phẩm, hàng hóa xuất bán * Giá đơn vị sản phẩm, hàng hóa xuất.

e/ Mô hình tính giá sản phẩm, dịch vụ, hàng hóa xuất bán và vật tư xuất dùng có thể được khái quát qua các sơ đồ sau:

Mô hình tính giá sản phẩm, dịch vụ tiêu thụ và giá vật tư xuất dùng cho sản xuất kinh doanh :

Giá vốn sản phẩm , dịch vụ đã bán , đã cung cấp cho khách hàng

Giá thành thực tế vật tư xuất dùng cho sản xuất kinh doanh

Giá thành sản xuất của sản phẩm ,dịch vụ

– Giá mua thực tế

– Giá thuê gia công

– Thuế nhập khẩu

– Chi phí mua vật tư

Chi phí nguyên vật liệu trực tiếp

Chi phí nhân công trực tiếp

Chi phí sản xuất chung

Mô hình tính giá hàng hoá tiêu thụ

Ví dụ: Ngày 18 / N , doanh nghiệp xuất bán 1.900 sản phẩm cho khách hàng theo giá hoá đơn chưa có thuế GTGT 10 % là 180.000 đồng / sản phẩm . Giá trị sản phẩm xuất kho được tính theo phương pháp nhập trước – xuất trước , trong đó 850 sản phẩm được tính theo giá 142.000 đồng / sản phẩm , số sản phẩm còn lại được tính theo giá 142.800 đồng / sản phẩm . Theo ví dụ này , tổng giá trị thành phẩm xuất bán được xác định như sau :

Giá vốn thành phẩm bán=(850*142.000) + (1.050 * 142.800 ) = 270.640.000 đồng

Bài viết trước: Chứng từ là gì và phương pháp chứng từ kế toán

⇒ Học kế toán sản xuất – Dạy cách tính giá thành sản phẩm trong doanh nghiệp sản xuất

⇒ Học kế toán thương mại dịch vụ – Dạy cách tính giá xuất kho, kiểm soát hàng tồn trong doanh nghiệp thương mại

Các bài viết mới

Các tin cũ hơn