Xem mẫu

  1. Matlab trong Giải tích số 1/57 Chương 4: Ứng dụng Matlab trong Giải tích số Viện Toán ứng dụng và Tin học, ĐHBK Hà Nội Hà Nội, tháng 8 năm 2015 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Matlab trong Giải tích số 2/57 Đa thức nội suy Nội dung 1 Đa thức nội suy Nội suy Lagrange Nội suy Newton Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Hermit (đọc thêm) 2 Giải gần đúng phương trình Phương pháp chia đôi Phương pháp dây cung Phương pháp Newton - Raphson 3 Giải gần đúng hệ phương trình Phương pháp lặp đơn Phương pháp Jacobi Phương pháp Gauss-Seidel Phương pháp Newton giải hệ phương trình phi tuyến 4 Giải gần đúng phương trình vi phân thường Phương pháp Euler Phương pháp Euler cải tiến (Modified Euler hay RK-2) Phương pháp Runge-Kutta Hệ phương trình vi phân CuuDuongThanCong.com thường và phương trình vi phân cấp cao https://fb.com/tailieudientucntt
  3. Matlab trong Giải tích số 3/57 Đa thức nội suy Đa thức nội suy Trong thực tế, nhiều khi ta phải tìm hàm 𝑦 = 𝑓 (𝑥) mà chỉ biết giá trị 𝑦𝑖 tại các điểm 𝑥𝑖 ∈ [𝑎, 𝑏] (𝑖 = 0, 1, . . . , 𝑛). Hoặc trong nhiều trường hợp biểu diễn giải tích của 𝑓 (𝑥) đã cho nhưng quá cồng kềnh. Khi dùng phép nội suy ta có thể dễ dàng tính được 𝑓 tại bất kỳ điểm 𝑥 ∈ [𝑎, 𝑏] mà độ chính xác không kém bao nhiêu. Bài toán đặt ra: Cho các mốc nội suy 𝑎 ≤ 𝑥0 < 𝑥1 < · · · < 𝑥𝑛 ≤ 𝑏. Hãy tìm đa thức (bậc 𝑛) 𝑛 𝑐𝑖 𝑥𝑖 sao cho: ∑︀ 𝑃𝑛 (𝑥) = 𝑖=0 𝑃𝑛 (𝑥𝑖 ) = 𝑦𝑖 = 𝑓 (𝑥𝑖 ) (𝑖 = 0 ÷ 𝑛) (1.1) Đa thức 𝑃𝑛 (𝑥) gọi là đa thức nội suy của hàm 𝑦 = 𝑓 (𝑥). Ta chọn đa thức để nội suy hàm vì đa thức là loại hàm đơn giản, luôn có đạo hàm và nguyên hàm. Việc tính giá trị của nó theo thuật toán Horner cũng đơn giản. CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Matlab trong Giải tích số 4/57 Đa thức nội suy Đa thức nội suy Cách tiếp cận Vandermond Các hệ số 𝑐0 , 𝑐1 , . . . , 𝑐𝑛 của đa thức nội suy bậc 𝑛 có thể được tính bằng cách giải hệ 𝑥𝑛−1 ⎡ 𝑛 ··· 𝑥20 ⎤⎡ ⎤ ⎡ ⎤ 𝑥0 0 𝑥0 1 𝑐0 𝑦0 ⎢𝑥𝑛 1 𝑥1𝑛−1 ··· 𝑥21 𝑥1 1⎥ ⎢ 𝑐1 ⎥ ⎢ 𝑦1 ⎥ 𝑥2𝑛−1 ⎢ 𝑛 𝑥22 ⎥⎢ ⎥ ⎢ ⎥ ⎢𝑥2 ··· 𝑥2 1⎥⎥ ⎢ 𝑐2 ⎥ = ⎢ 𝑦2 ⎥ ⎢ ⎥ ⎢ ⎥ ⎥⎢ . ⎥ ⎢ . ⎥ ⎢ ⎢ . .. ⎣ .. . ⎦ ⎣ .. ⎦ ⎣ .. ⎦ 𝑥𝑛𝑛 𝑥𝑛−1 𝑛 ··· 𝑥2𝑛 𝑥𝑛 1 𝑐𝑛 𝑦𝑛 hay 𝐴𝑐 = 𝑦 𝑛 ∏︀ Hệ trên có định thức Vandermond |𝐴| = (𝑥𝑗 − 𝑥𝑖 ) ̸= 0 nên có nghiệm 1≤𝑖
  5. Matlab trong Giải tích số 5/57 Đa thức nội suy Nội suy Lagrange Nội suy Lagrange Trước hết tìm đa thức 𝐿𝑖 (𝑥) có bậc 𝑛 sao cho: {︃ 1 nếu 𝑖 = 𝑗 𝐿𝑖 (𝑥𝑗 ) = , (∀𝑖, 𝑗 = 0 ÷ 𝑛) 0 nếu 𝑖 ≠ 𝑗 Dễ thấy 𝐿𝑖 (𝑥) có dạng: ∏︀ (𝑥 − 𝑥𝑗 ) 𝑗̸=𝑖 𝐿𝑖 (𝑥) = ∏︀ (𝑥𝑖 − 𝑥𝑗 ) 𝑗̸=𝑖 ∏︀ (𝑥 − 𝑥𝑗 ) 𝑛 ∑︀ 𝑛 ∑︀ 𝑗̸=𝑖 Đặt 𝑃 (𝑥) = 𝑦𝑖 .𝐿𝑖 (𝑥) = 𝑦𝑖 ∏︀ ta có ngay: 𝑖=0 𝑖=1 (𝑥𝑖 − 𝑥𝑗 ) 𝑗̸=𝑖 𝑛 ∑︁ 𝑃 (𝑥𝑗 ) = 𝑦𝑖 .𝐿𝑖 (𝑥𝑗 ) = 𝑦𝑗 (𝑗 = 0 ÷ 𝑛) (1.2) 𝑖=1 Vậy 𝑃 (𝑥) CuuDuongThanCong.com là đa thức nội suy duy nhất cần tìm. https://fb.com/tailieudientucntt
  6. Matlab trong Giải tích số 6/57 Đa thức nội suy Nội suy Newton Nội suy Newton Nội suy Newton tiến Công thức nội suy Lagrange có ưu điểm là đơn giản, dễ lập trình nhưng nếu thêm mốc nội suy thì phải tính lại toàn bộ. Nhược điểm này sẽ được khắc phục trong công thức Newton. Công thức nội suy Newton tiến 𝑃𝑛 (𝑥) =𝑓 (𝑥0 ) + (𝑥 − 𝑥0 ) 𝑓 [𝑥0 , 𝑥1 ] + (𝑥 − 𝑥0 ) (𝑥 − 𝑥1 ) 𝑓 [𝑥0 , 𝑥1 , 𝑥2 ] + · · · + (𝑥 − 𝑥0 ) (𝑥 − 𝑥1 ) . . . (𝑥 − 𝑥𝑛−1 ) 𝑓 [𝑥0 , 𝑥1 , . . . , 𝑥𝑛 ] , trong đó các tỷ hiệu được tính theo công thức 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥𝑖−1 ) 𝑓 [𝑥𝑖−1 , 𝑥𝑖 ] = ; 𝑥𝑖 − 𝑥𝑖−1 𝑓 [𝑥1 , . . . , 𝑥𝑛 ] − 𝑓 [𝑥0 , . . . , 𝑥𝑛−1 ] 𝑓 [𝑥0 , 𝑥1 , . . . , 𝑥𝑛 ] = (1.3) CuuDuongThanCong.com https://fb.com/tailieudientucntt 𝑥𝑛 − 𝑥0
  7. Matlab trong Giải tích số 6/57 Đa thức nội suy Nội suy Newton Nội suy Newton Nội suy Newton tiến Công thức nội suy Lagrange có ưu điểm là đơn giản, dễ lập trình nhưng nếu thêm mốc nội suy thì phải tính lại toàn bộ. Nhược điểm này sẽ được khắc phục trong công thức Newton. Công thức nội suy Newton tiến 𝑃𝑛 (𝑥) =𝑓 (𝑥0 ) + (𝑥 − 𝑥0 ) 𝑓 [𝑥0 , 𝑥1 ] + (𝑥 − 𝑥0 ) (𝑥 − 𝑥1 ) 𝑓 [𝑥0 , 𝑥1 , 𝑥2 ] + · · · + (𝑥 − 𝑥0 ) (𝑥 − 𝑥1 ) . . . (𝑥 − 𝑥𝑛−1 ) 𝑓 [𝑥0 , 𝑥1 , . . . , 𝑥𝑛 ] , trong đó các tỷ hiệu được tính theo công thức 𝑓 (𝑥𝑖 ) − 𝑓 (𝑥𝑖−1 ) 𝑓 [𝑥𝑖−1 , 𝑥𝑖 ] = ; 𝑥𝑖 − 𝑥𝑖−1 𝑓 [𝑥1 , . . . , 𝑥𝑛 ] − 𝑓 [𝑥0 , . . . , 𝑥𝑛−1 ] 𝑓 [𝑥0 , 𝑥1 , . . . , 𝑥𝑛 ] = (1.3) CuuDuongThanCong.com https://fb.com/tailieudientucntt 𝑥𝑛 − 𝑥0
  8. Matlab trong Giải tích số 7/57 Đa thức nội suy Nội suy Newton Nội suy Newton Nội suy Newton lùi Nếu các mốc nội suy được sắp xếp theo thứ tự giảm dần 𝑥𝑛 , 𝑥𝑛−1 , . . . , 𝑥1 , 𝑥0 thì ta có công thức nội suy Newton lùi xuất phát từ mốc 𝑥𝑛 : 𝑃𝑛 (𝑥) =𝑓 (𝑥𝑛 ) + (𝑥 − 𝑥𝑛 ) 𝑓 [𝑥𝑛 , 𝑥𝑛−1 ] + (𝑥 − 𝑥𝑛 ) (𝑥 − 𝑥𝑛−1 ) 𝑓 [𝑥𝑛 , 𝑥𝑛−1 , 𝑥𝑛−2 ] + · · · + (𝑥 − 𝑥𝑛 ) (𝑥 − 𝑥𝑛−1 ) . . . (𝑥 − 𝑥1 ) 𝑓 [𝑥𝑛 , 𝑥𝑛−1 , . . . , 𝑥1 , 𝑥0 ] , trong đó các tỷ hiệu được tính như trong công thức (1.3). CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. Matlab trong Giải tích số 8/57 Đa thức nội suy Nội suy Newton Sai số của phép nội suy Định lý 1.1 Giả sử hàm 𝑓 : R → R khả vi liên tục đến cấp 𝑛 + 1 trên [𝑎, 𝑏] (𝑓 ∈ 𝐶 (𝑛+1) [𝑎, 𝑏]) và 𝑥𝑖 ∈ [𝑎, 𝑏], 𝑖 = 0 : 𝑛. Khi đó tồn tại 𝜉 = 𝜉(𝑥) ∈ [𝑎, 𝑏] sao cho 1 𝑓 (𝑥) − 𝑃𝑛 (𝑥) = 𝑓 (𝑛+1) (𝜉)(𝑥 − 𝑥0 ) . . . (𝑥 − 𝑥𝑛 ). (𝑛 + 1)! Từ đó ta có công thức ước lượng sai số 1 |𝑓 (𝑥) − 𝑃𝑛 (𝑥)| ≤ 𝑀𝑛+1 (𝑓 ) |(𝑥 − 𝑥0 ) . . . (𝑥 − 𝑥𝑛 )| , (𝑛 + 1)! ⃒ ⃒ trong đó 𝑀𝑛+1 (𝑓 ) = max ⃒𝑓 (𝑛+1) (𝑥)⃒. ⃒ ⃒ 𝑥∈[𝑎,𝑏] CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. Matlab trong Giải tích số 9/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Xét trường hợp nội suy đa thức cho hàm 𝑓 (𝑥) trên đoạn [−1, 1] dựa trên các mốc nội suy −1 ≤ 𝑥0 < 𝑥1 < · · · < 𝑥𝑛 ≤ 1. Khi đó công thức đánh giá sai số của các đa thức nội suy Lagrange và Newton đều có dạng 1 ⃒ ⃒ |𝑓 (𝑥) − 𝑃𝑛 (𝑥)| ≤ |𝑤(𝑥)| max ⃒𝑓 (𝑛+1) (𝑥)⃒ , ⃒ ⃒ (𝑛 + 1)! 𝑥∈[−1,1] trong đó đa thức bậc 𝑛 + 1: 𝑤(𝑥) = (𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) . . . (𝑥 − 𝑥𝑛 ). Ta muốn chọn các mốc nội suy {𝑥𝑖 }𝑛 𝑖=0 để cực tiểu giá trị max |𝑤(𝑥)|. −1≤𝑥≤1 Điều này dẫn tới việc sử dụng đa thức nội suy Chebyshev. CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. Matlab trong Giải tích số 9/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Xét trường hợp nội suy đa thức cho hàm 𝑓 (𝑥) trên đoạn [−1, 1] dựa trên các mốc nội suy −1 ≤ 𝑥0 < 𝑥1 < · · · < 𝑥𝑛 ≤ 1. Khi đó công thức đánh giá sai số của các đa thức nội suy Lagrange và Newton đều có dạng 1 ⃒ ⃒ |𝑓 (𝑥) − 𝑃𝑛 (𝑥)| ≤ |𝑤(𝑥)| max ⃒𝑓 (𝑛+1) (𝑥)⃒ , ⃒ ⃒ (𝑛 + 1)! 𝑥∈[−1,1] trong đó đa thức bậc 𝑛 + 1: 𝑤(𝑥) = (𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) . . . (𝑥 − 𝑥𝑛 ). Ta muốn chọn các mốc nội suy {𝑥𝑖 }𝑛 𝑖=0 để cực tiểu giá trị max |𝑤(𝑥)|. −1≤𝑥≤1 Điều này dẫn tới việc sử dụng đa thức nội suy Chebyshev. CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. Matlab trong Giải tích số 10/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Định nghĩa 1.1 Các hàm 𝑇𝑛 (𝑥) = cos(𝑛 arccos(𝑥)), 𝑛 = 0, 1, 2, . . . gọi là các đa thức Chebyshev trong đoạn [−1, 1]. Chú ý 1.1 Các hàm trên thực sự là các đa thức. Thật vậy, đặt 𝛿 = arccos(𝑥). Đồng nhất thức cos(𝑛 + 1)𝛿 + cos(𝑛 − 1)𝛿 = 2 cos 𝛿 cos 𝑛𝛿 cho ta công thức truy hồi 𝑇𝑛+1 (𝑥) = 2𝑥𝑇𝑛 (𝑥) − 𝑇𝑛−1 (𝑥). Với 𝑇0 (𝑥) = 1, 𝑇1 (𝑥) = 𝑥, rõ ràng 𝑇𝑛 (𝑥) ∈ 𝒫𝑛 . CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. Matlab trong Giải tích số 11/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Bảng một số đa thức nội suy Chebyshev đầu tiên 𝑇0 (𝑥) = 1 𝑇1 (𝑥) = 𝑥 𝑇2 (𝑥) = 2𝑥2 − 1 𝑇3 (𝑥) = 4𝑥3 − 3𝑥 𝑇4 (𝑥) = 8𝑥4 − 8𝑥2 − 1 𝑇5 (𝑥) = 16𝑥5 − 20𝑥3 + 5𝑥 𝑇6 (𝑥) = 32𝑥6 − 48𝑥4 + 18𝑥2 − 1 𝑇7 (𝑥) = 64𝑥7 − 112𝑥5 + 56𝑥3 − 7𝑥 ... CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. Matlab trong Giải tích số 12/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Một số tính chất của đa thức Chebyshev Các hệ số của đa thức Chebyshev 𝑇𝑛 đều nguyên. Hệ số ứng với bậc cao nhất là 𝑎𝑛 = 2𝑛−1 . 𝑇2𝑛 là hàm chẵn, 𝑇2𝑛+1 là hàm lẻ. |𝑇𝑛 (𝑥)| ≤ 1 với 𝑥 ∈ [−1, 1] và 𝑇𝑛 (𝑥) = 1 với 𝑥𝑘 = cos(𝑘𝜋/𝑛). 𝑇𝑛 (1) = 1, 𝑇𝑛 (−1) = (−1)𝑛 . (︂ )︂ (2𝑘 − 1)𝜋 𝑇𝑛 (𝑥𝑘 ) = 0 với 𝑥𝑘 = cos , 𝑘 = 1, . . . , 𝑛. 2𝑘 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. Matlab trong Giải tích số 12/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Một số tính chất của đa thức Chebyshev Các hệ số của đa thức Chebyshev 𝑇𝑛 đều nguyên. Hệ số ứng với bậc cao nhất là 𝑎𝑛 = 2𝑛−1 . 𝑇2𝑛 là hàm chẵn, 𝑇2𝑛+1 là hàm lẻ. |𝑇𝑛 (𝑥)| ≤ 1 với 𝑥 ∈ [−1, 1] và 𝑇𝑛 (𝑥) = 1 với 𝑥𝑘 = cos(𝑘𝜋/𝑛). 𝑇𝑛 (1) = 1, 𝑇𝑛 (−1) = (−1)𝑛 . (︂ )︂ (2𝑘 − 1)𝜋 𝑇𝑛 (𝑥𝑘 ) = 0 với 𝑥𝑘 = cos , 𝑘 = 1, . . . , 𝑛. 2𝑘 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. Matlab trong Giải tích số 12/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Một số tính chất của đa thức Chebyshev Các hệ số của đa thức Chebyshev 𝑇𝑛 đều nguyên. Hệ số ứng với bậc cao nhất là 𝑎𝑛 = 2𝑛−1 . 𝑇2𝑛 là hàm chẵn, 𝑇2𝑛+1 là hàm lẻ. |𝑇𝑛 (𝑥)| ≤ 1 với 𝑥 ∈ [−1, 1] và 𝑇𝑛 (𝑥) = 1 với 𝑥𝑘 = cos(𝑘𝜋/𝑛). 𝑇𝑛 (1) = 1, 𝑇𝑛 (−1) = (−1)𝑛 . (︂ )︂ (2𝑘 − 1)𝜋 𝑇𝑛 (𝑥𝑘 ) = 0 với 𝑥𝑘 = cos , 𝑘 = 1, . . . , 𝑛. 2𝑘 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. Matlab trong Giải tích số 12/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Một số tính chất của đa thức Chebyshev Các hệ số của đa thức Chebyshev 𝑇𝑛 đều nguyên. Hệ số ứng với bậc cao nhất là 𝑎𝑛 = 2𝑛−1 . 𝑇2𝑛 là hàm chẵn, 𝑇2𝑛+1 là hàm lẻ. |𝑇𝑛 (𝑥)| ≤ 1 với 𝑥 ∈ [−1, 1] và 𝑇𝑛 (𝑥) = 1 với 𝑥𝑘 = cos(𝑘𝜋/𝑛). 𝑇𝑛 (1) = 1, 𝑇𝑛 (−1) = (−1)𝑛 . (︂ )︂ (2𝑘 − 1)𝜋 𝑇𝑛 (𝑥𝑘 ) = 0 với 𝑥𝑘 = cos , 𝑘 = 1, . . . , 𝑛. 2𝑘 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. Matlab trong Giải tích số 12/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Một số tính chất của đa thức Chebyshev Các hệ số của đa thức Chebyshev 𝑇𝑛 đều nguyên. Hệ số ứng với bậc cao nhất là 𝑎𝑛 = 2𝑛−1 . 𝑇2𝑛 là hàm chẵn, 𝑇2𝑛+1 là hàm lẻ. |𝑇𝑛 (𝑥)| ≤ 1 với 𝑥 ∈ [−1, 1] và 𝑇𝑛 (𝑥) = 1 với 𝑥𝑘 = cos(𝑘𝜋/𝑛). 𝑇𝑛 (1) = 1, 𝑇𝑛 (−1) = (−1)𝑛 . (︂ )︂ (2𝑘 − 1)𝜋 𝑇𝑛 (𝑥𝑘 ) = 0 với 𝑥𝑘 = cos , 𝑘 = 1, . . . , 𝑛. 2𝑘 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. Matlab trong Giải tích số 12/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Một số tính chất của đa thức Chebyshev Các hệ số của đa thức Chebyshev 𝑇𝑛 đều nguyên. Hệ số ứng với bậc cao nhất là 𝑎𝑛 = 2𝑛−1 . 𝑇2𝑛 là hàm chẵn, 𝑇2𝑛+1 là hàm lẻ. |𝑇𝑛 (𝑥)| ≤ 1 với 𝑥 ∈ [−1, 1] và 𝑇𝑛 (𝑥) = 1 với 𝑥𝑘 = cos(𝑘𝜋/𝑛). 𝑇𝑛 (1) = 1, 𝑇𝑛 (−1) = (−1)𝑛 . (︂ )︂ (2𝑘 − 1)𝜋 𝑇𝑛 (𝑥𝑘 ) = 0 với 𝑥𝑘 = cos , 𝑘 = 1, . . . , 𝑛. 2𝑘 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  20. Matlab trong Giải tích số 13/57 Đa thức nội suy Nội suy bằng đa thức Chebyshev Nội suy bằng đa thức Chebyshev Định lý 1.2 Giả sử 𝑛 cố định. Trong số tất cả các cách chọn 𝑤(𝑥) và các mốc phân biệt {𝑥𝑖 }𝑛 𝑛 𝑖=0 ∈ [−1, 1], đa thức 𝑇 (𝑥) = 𝑇𝑛+1 (𝑥)/2 là sự lựa chọn suy nhất thỏa mãn max {|𝑇 (𝑥)|} ≤ max {|𝑤(𝑥)|} . −1≤𝑥≤1 −1≤𝑥≤1 Hơn nữa 1 max {|𝑇 (𝑥)|} = . −1≤𝑥≤1 2𝑛 CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn