Xem mẫu
- 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
- 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
- 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
- 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≤𝑖
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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