BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
NGUYỄN THỊ THÚY
CÁC PHƯƠNG PHÁP TỰA NỘI SUY SPLINE VÀ ỨNG DỤNG
LUẬN VĂN THẠC SỸ
Chuyên ngành : TOÁN GIẢI TÍCH Mã số : 60 46 01 02
Người hướng dẫn khoa học:
TS. NGUYỄN VĂN TUẤN
HÀ NỘI, 2014
Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Nguyễn Văn Tuấn, người đã định hướng chọn đề tài và tận tình hướng dẫn để tôi hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới các thầy cô phòng sau đại học, cùng các thầy cô giáo dạy cao học chuyên ngành Toán giải tích, trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ tôi trong suốt qúa trình học tập. Xin cảm ơn gia đình, bạn bè đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và hoàn thành luận văn. Hà Nội, tháng 12 năm 2014 Tác giả
Nguyễn Thị Thúy
2
Lời cam đoan Tôi xin cam đoan, dưới sự hướng dẫn của TS. Nguyễn Văn Tuấn, luận văn Thạc sĩ chuyên ngành Toán giải tích với đề tài: “Các phương pháp tựa nội suy spline và ứng dụng” được hoàn thành bởi nhận thức của tác giả. Trong quá trình nghiên cứu thực hiện luận văn, tác giả đã kế thừa thành tựu của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 12 năm 2014 Tác giả
Nguyễn Thị Thúy
3
Mở đầu
6
1 Kiến thức chuẩn bị
8
1.1
Không gian vectơ . . . . . . . . . . . . . . . . . . . . . . .
8
1.2
Không gian metric . . . . . . . . . . . . . . . . . . . . . . . 10
1.3
Không gian định chuẩn . . . . . . . . . . . . . . . . . . . . 12
1.4
Số gần đúng và sai số . . . . . . . . . . . . . . . . . . . . . 14
1.5
Phương pháp nội suy . . . . . . . . . . . . . . . . . . . . . 14 1.5.1
Đa thức nội suy Lagrange . . . . . . . . . . . . . . . 15
1.5.2
Đa thức nội suy Hermitte . . . . . . . . . . . . . . . 16
1.5.3
Spline đa thức . . . . . . . . . . . . . . . . . . . . . 16
2 Phương pháp tựa nội suy
19
2.1
Không gian các hàm spline và B-spline . . . . . . . . . . . . 19
2.2
Tính chất của spline và B-spline . . . . . . . . . . . . . . . 21
2.3
2.2.1
Sự độc lập tuyến tính và đa thức đại diện . . . . . . 21
2.2.2
Phép lấy vi phân và tính trơn của B-spline . . . . . 26
2.2.3
B-spline làm cơ sở cho đa thức từng đoạn . . . . . . 30
Tựa nội suy . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.1
Tựa nội suy . . . . . . . . . . . . . . . . . . . . . . 31
2.3.2
Các tính chất . . . . . . . . . . . . . . . . . . . . . 36
2.3.3
Hai cơ sở tựa nội suy trên phiếm hàm điểm . . . . . 38
4
3 Ứng dụng
41
3.1
Tựa nội suy bằng các hàm spline bậc 1 . . . . . . . . . . . 41
3.2
Tựa nội suy bằng các hàm spline bậc 2 . . . . . . . . . . . 45
Kết luận
49
Tài liệu tham khảo
50
5
Mở đầu 1. LÝ DO CHỌN ĐỀ TÀI Trong thực tế, vấn đề tìm giá trị của hàm số, tính tích phân xác định có ý nghĩa quan trọng, nên có nhiều phương pháp khác nhau để giải các bài toán trên. Việc giải tìm nghiệm đúng của các bài toán này nhiều trường hợp không giải được hoặc nghiệm đúng không có ý nghĩa thiết thực, bởi vậy người ta sử dụng nhiều phương pháp gần đúng khác nhau để giải quyết các vấn đề trên. Hàm spline là các đa thức trên từng đoạn có nhiều ưu điểm trong tính toán do vậy được ứng dụng trong tính toán gần đúng. Trong phương pháp nội suy, các điểm nút là các mốc nội suy được cố định. Người ta có thể sử dụng các điểm nút nội suy linh hoạt, đó là phương pháp tựa nội suy. Khi áp dụng hàm spline và phương pháp tựa nội suy để xấp xỉ hàm số, người ta chia khoảng xác định của hàm số thành nhiều đoạn, trên mỗi đoạn ta xấp xỉ bằng một hàm spline, qua đó sẽ xấp xỉ được hàm số đã cho. Phương pháp này có nhiều ưu điểm do đó, tôi đã chọn đề tài : “Các phương pháp tựa nội suy spline và ứng dụng”. 2. MỤC ĐÍCH NGHIÊN CỨU Tìm hiểu khái niệm và các tính chất của hàm spline, B-spline. Khái niệm phương pháp tựa nội suy spline và một số ứng dụng của phương pháp tựa nội suy bằng hàm spline, B-spline. 3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU Đối tượng nghiên cứu: Phương pháp tựa nội suy bằng hàm spline. Phạm vi nghiên cứu: Phương pháp tựa nội suy spline, xấp xỉ hàm số, 6
lập trình Maple để giải các bài toán đặt ra. 4. PHƯƠNG PHÁP NGHIÊN CỨU Sử dụng phương pháp nội suy và phương pháp hàm spline trong quá trình thực hiện luận văn. 5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI Áp dụng phương pháp tựa nội suy vào xấp xỉ một lớp hàm số có ứng dụng trong thực tế. Làm rõ một số tính chất của hàm spline và phương pháp tựa nội suy. 6. CẤU TRÚC CỦA LUẬN VĂN Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận văn gồm 3 chương. Chương 1. Kiến thức chuẩn bị, chương này trình bày khái niệm và kiến thức để sử dụng cho các chương sau. Chương 2. Phương pháp tựa nội suy, trong chương này trình bày khái niệm và các tính chất của hàm spline, B-spline, phương pháp tựa nội suy và các tính chất. Chương 3. Ứng dụng, trình bày ứng dụng phương pháp tựa nội suy để xấp xỉ các lớp hàm cho trước.
7
Chương 1 Kiến thức chuẩn bị 1.1
Không gian vectơ
Định nghĩa 1.1.1. Một tập X được gọi là một không gian vectơ, nếu:
* Ứng với mỗi phần tử x, y của X ta có, theo quy tắc nào đó, một phần tử của X , gọi là tổng của x với y , và được kí hiệu x + y ; ứng với mỗi phần tử x của X và mỗi số thực α ta có, theo một quy tắc nào đó, một phần tử của X gọi là tích của x với α và được kí hiệu αx. * Các quy tắc nói trên thỏa mãn 8 tiên đề sau: 1. x + y = y + x, ∀x, y ∈ X. 2. (x + y) + z = x + (y + z), ∀x, y, z ∈ X . 3. Tồn tại duy nhất phần tử 0 sao cho x + 0 = x với mọi x ∈ X ( phần tử này gọi là phần tử không). 4. Ứng với mỗi phần tử x ∈ X , tồn tại duy nhất phần tử −x ∈ X sao cho x + (−x) = 0 (phần tử −x gọi là phần tử đối của x). 5. 1.x = x, ∀x ∈ X . 6. α(βx) = (αβ)x, ∀x ∈ X, ∀α, β ∈ R . 7. (α + β)x = αx + βx, ∀x ∈ X, ∀α, β ∈ R. 8. α(x + y) = αx + αy, ∀x, y ∈ X, ∀α ∈ R. 8
E 2 = {(x1 , x2 ) : x1 và x2 là các số thực}. Với mỗi số thực α và các vectơ x = (x1 , x2 ), y = (y1 , y2 ) ∈ X , phép cộng và nhân vô hướng được định nghĩa:
x + y = (x1 + y1 , x2 + y2 ) αx = (αx1 , αx2 ) là không gian vectơ. Ví dụ 1.2. Xét không gian tuyến tính thực
C[a,b] = {x = x(t) : x(t) là hàm số liên tục trên [a, b]}, với mỗi số thực α và f (t), g(t) ∈ C[a, b], phép cộng và nhân vô hướng được định nghĩa:
(f + g)(t) = f (t) + g(t), a ≤ t ≤ b (αf )(t) = αf (t) là không gian vectơ. Định nghĩa 1.1.2. Các vectơ x1 , x2 , …, xk ∈ X gọi là độc lập tuyến tính nếu bất cứ tổ hợp tuyến tính nào của các vectơ ấy mà đã bằng không thì mọi hệ số bằng không, nghĩa là: α1 x1 + α2 x2 + … + αk xk = 0 nhất thiết kéo theo α1 = α2 = … = αk = 0. Các vectơ x1 , x2 , …, xk gọi là phụ thuộc tuyến tính nếu chúng không độc lập tuyến tính. Nghĩa là tồn tại những số α1 , α2 , …, αk trong đó có ít nhất một số khác 0 sao cho α1 x1 + α2 x2 + … + αk xk = 0.
9
Định nghĩa 1.1.3. Giả sử X là một không gian tuyến tính trên trường K , (K = R hoặc K = C). Một hệ vectơ trong X gọi là một hệ sinh của X nếu mọi vectơ của X đều biểu thị tuyến tính theo hệ đó. Nếu X có một hệ sinh gồm hữu hạn phần tử thì X được gọi là một không gian tuyến tính hữu hạn sinh. Một hệ vectơ trong X gọi là một cơ sở của X nếu mọi vectơ của X đều biểu thị tuyến tính duy nhất theo hệ đó. Định nghĩa 1.1.4. Giả sử X là không gian tuyến tính hữu hạn sinh. Khi đó X có cơ sở hữu hạn và số phần tử của các cơ sở trong X đều như nhau. Số đó được gọi là số chiều của không gian tuyến tính X . Nếu X là một K – không gian tuyến tính có số chiều là n, ta viết dimX = n hoặc dimK X = n. Định nghĩa 1.1.5. Giả sử X là một không gian tuyến tính trên R. Tập con X1 của X được gọi là một không gian tuyến tính con của không gian X nếu X1 cùng hai phép toán cảm sinh của X trên X1 tạo thành một không gian tuyến tính. Định nghĩa 1.1.6. Giả sử X và Y là hai không gian tuyến tính trên R. Khi đó ánh xạ T : X → Y được gọi là tuyến tính nếu: 1. T (x1 + x2 ) = T (x1 ) + T (x2 ), ∀x1 , x2 ∈ X 2. T (kx) = kT (x), ∀k ∈ R, ∀x ∈ X .
1.2
Không gian metric
Định nghĩa 1.2.1. Xét một tập hợp X cùng với ánh xạ
d:X ×X →R thỏa mãn các điều kiện: 1. d(x, y) ≥ 0, ∀x, y ∈ X; d(x, y) = 0 ⇔ x = y; 2. d(x, y) = d(y, x), ∀x, y ∈ X; 10
Định nghĩa 1.2.2. Cho dãy các phần tử xn ∈ X, ∀n ∈ N và phần tử x∗ ∈ X . Khi đó x∗ được gọi là giới hạn của dãy {xn }n∈N nếu
lim d(xn , x∗ ) = 0
n→∞
và kí hiệu lim xn = x∗ . n→∞
d(T x, T x, ) 6 αd(x, x, ) Định lý 1.1. (Nguyên lí ánh xạ co). Giả sử X là không gian metric đủ và ánh xạ T : X → X thỏa mãn điều kiện
d(T x, T x, ) 6 αd(x, x, ) với hằng số α < 1 và ∀x, y ∈ X . Khi đó tồn tại duy nhất phần tử x∗ ∈ X sao cho x∗ = T x∗ , hơn nữa với x0 ∈ X thì dãy {xn }n∈N xác định bởi xk+1 = T xk , ∀k ∈ N, là hội tụ đến x∗ , đồng thời ta có ước lượng:
d (xn , x∗ ) 6
αn 1−α d (x1 , x0 )
11
1.3
Không gian định chuẩn
Ví dụ 1.6. Không gian L[a,b] , là không gian định chuẩn với chuẩn:
kxk =
Rb
a
Định nghĩa 1.3.2. Dãy điểm (xn ) của không gian định chuẩn X gọi là hội tụ tới điểm x ∈ X , nếu lim kxn − xk = 0. Kí hiệu lim xn = x hay n→∞
n→∞
xn → x(n → ∞). Định nghĩa 1.3.3. Cho không gian tuyến tính X và kXk1 , kXk2 là hai chuẩn đã cho trên X . Hai chuẩn kXk1 , và kXk2 gọi là tương đương nếu tồn tại hai số dương α, β sao cho:
αkxk1 ≤ kxk2 ≤ βkxk1 , ∀x ∈ X. Định nghĩa 1.3.4. Cho không gian định chuẩn X và dãy điểm (xn ) ⊂ X . Ta gọi chuỗi là biểu thức có dạng:
Chuỗi này gọi là hội tụ nếu các tổng bộ phận sn = x1 + x2 + … + xn của nó lập thành một dãy hội tụ. Định nghĩa 1.3.5. Giả sử không gian định chuẩn X là một không gian metric đầy đủ (với khoảng cách d(x, y) = kx − yk). Khi đó X được gọi là một không gian định chuẩn đầy đủ, hay còn gọi là không gian Banach. Định nghĩa 1.3.6. Giả sử X , Y là hai không gian tuyến tính định chuẩn và T : X → Y là một toán tử tuyến tính. Nếu tồn tại giá trị hữu hạn: xk kT k = sup kT kxk < +∞ x∈X
p
(x, x), x ∈ H .
Ta gọi không gian tuyến tính con đóng của không gian Hilbert H là không gian Hilbert con của không gian H .
13
1.4
Số gần đúng và sai số
f 0xi
là đạo hàm theo xi tính tại điểm trung gian. n
P f¯0 (x1 , …, xn )∆xi Vì f là khả vi liên tục, ∆xi quá bé nên: ∆y = xi i=1
i=1
1.5
Phương pháp nội suy
Trong thực tế tính toán, ta thường phải tính giá trị của hàm y = f (x) với x bất kì trong đoạn [a, b], trong khi chỉ biết các giá trị yi = f (xi ) , xi ∈ [a, b] , i = 0, 1, …, n. Ở một số trường hợp khác biểu thức giải tích của f (x) đã biết, nhưng quá phức tạp. Với những trường hợp như vậy, người ta thường xây dựng một hàm số P (x) đơn giản và thỏa mãn điều kiện P (xi ) = f (xi ) , và xi 6= xj , ∀i 6= j, xi ∈ [a, b], ∀i = 0, 1, …, n 14
Ngoài ra, tại x ∈ [a, b] , x 6= xi thì P (x) xấp xỉ y = f (x) theo một độ chính xác nào đó. Hàm số như vậy gọi là hàm nội suy của f (x), còn các xi , i = 0, 1, …, n gọi là các mốc nội suy. Bài toán xây dựng hàm số P (x) như vậy gọi là bài toán nội suy. Trong quá trình xây dựng hàm P (x), ta xây dựng P (x) có đặc tính tương tự với hàm số y = f (x). chẳng hạn, nếu f (x) tuần hoàn với chu kì T thì P (x) cũng tuần hoàn với chu kì T . Dùng hàm nội suy P (x) có thể dễ dàng tính được các giá trị f (x) tại x bất kì thuộc [a, b] tương đối chính xác. Từ đó có thể tính gần đúng đạo hàm, hoặc tích phân của f (x) trên đoạn [a, b]. vì các đa thức đại số là đơn giản nên trước tiên ta nghĩ đến việc xây dựng P (x) ở dạng đa thức đại số.
1.5.1
Đa thức nội suy Lagrange
Bài toán: Cho xi ∈ [a, b] , i = 0, 1, …, n, xi 6= xj , ∀i 6= j và yi = f (xi ) , i = 0, 1, …, n. Hãy xây dựng đa thức nội suy Ln (x) thỏa mãn deg Ln (x) 6 n, Ln (xi ) = yi , ∀i = 0, 1, …, n. n n Q Q Trước hết ta xét: Φj (x) = (x − xj )/ (xj − xi ). Rõ ràng i=0,i6=j
i=0,i6=j
deg Φj (x) = n, ∀j = 0, 1, …, n và (
Φj (x) =
Đặt Ln (x) =
yj Φj (x), ta có deg Ln (x) 6 n và Ln (xi ) = yi , ∀i =
j=0
0, 1, …, n. Vậy Ln (x) thỏa mãn mọi yêu cầu của bài toán đặt ra và Ln (x) xây dựng n Q như vậy được gọi là đa thức nội suy Lagrange. Đặt ωn+1 (x) = (x − xi ), i=0
ta có:
Ln (x) =
e n (x) thỏa mãn các điều kiện trên khi đó gọi Giả sửh còn có đa thứciL e n (x) thì deg ϕ (x) 6 n và nhận ít nhất là (n + 1) ϕ (x) = Ln (x) − L e n (x) ≡ Ln (x). nghiệm x0 , x1 , …, xn , do đó ϕ (x) ≡ 0, do vậy L 15
Vậy tồn tại duy nhất một đa thức thỏa mãn các điều kiện kể trên. Đa thức nội suy Lagrange với mốc cách đều Giả sử xi+1 − xi = h, ∀i = 0, 1, …, (n − 1), x0 = a, xn = b. Khi đó dùng phép đổi biến x = x0 + th, xj = x0 + jh với j = 0, 1, …, n − 1 và thay vào biểu thức của Φj (x) ta được n−j
Φj (x) =
Khi đó ta thu được:
Ln (x) = Ln (x0 + th) =
1.5.2
cn
Đa thức nội suy Hermitte
Bài toán: Hãy tìm đa thức nội suy H2n+1 (x) thỏa mãn các điều kiện 1. deg H2n+1 (x) 6 2n + 1. 2. H2n+1 (xi ) = f (xi ) , ∀i = 0, 1, …, n. 0 (xi ) = f 0 (xi ) , ∀i = 0, 1, …, n. 3. H2n+1 0 Trong đó xi ∈ [a, b] , xi 6= xj , ∀i 6= j , và f 0 (xi ), H2n+1 (xi ) tương ứng là đạo hàm của hàm số f (x) và H2n+1 (x) tại xi . Đa thức:
là đa thức nội suy Hermitte. Đa thức nội suy Hermitte có đặc điểm riêng khác với đa thức nội suy Lagrange là ngoài các yêu cầu về sự trùng nhau giữa đa thức nội suy và hàm số đã cho tại các mốc nội suy thì còn có yêu cầu về sự trùng nhau của các giá trị đạo hàm của chúng.
1.5.3
Spline đa thức
Người ta có nhiều cách dựng các hàm spline, sau đây là cách một xây dựng hàm spline. 16
Bài toán: Xét phân hoạch a = x0 < x1 < … < xn−1 < xn = b. Một spline đa thức bậc 3 trên đoạn [a, b] với phân hoạch đã cho là hàm số y = S(x) thỏa mãn hai điều kiện sau đây: 2 1. S (x) ∈ C[a,b] .
2. Hạn chế của S(x) trên mỗi ∆i = [xi ; xi+1 ] là một đa thức đại số
S (xi ) = yi , S 0 (xi ) = yi0 , ∀i = 0, 1, …, n. Để giải quyết bài toán này, ta kí hiệu hi = (xi+1 − xi ) , i = 0, 1, …, (n − 1) và mi = S 00 (xi ) , i = 0, 1, …, n. Vì S 00 (x) là đa thức bậc 6 1 trên ∆i nên có thể viết
Thay x = xi thì có mi = αi hi , do vậy αi = Thay x = xi+1 thì có mi+1 = βi hi nên viết dưới dạng:
− xi )3 +
− xi )3 + ξ (xi+1 − x) + η (x − xi ).
Tương tự như trên, thay x = xi và x = xi=1 ta thu được:
−
3
x) + m6hi+1i (x − xi )3 + hyii
−
(xi+1 − x) +
Lấy đạo hàm ta có : 0
2
− x)
+ m2hi+1i (x
2
− xi ) −
17
−
.
và bi =
h
−
yi −yi−1 hi−1
i
thì hệ trên được
viết dưới dạng: (
(1 − ai ) mi−1 + 2mi + ai mi+1 = bi . 16i6n−1
Chú ý đến hai điều kiện S 0 (x0 ) = y00 và S 0 (xn ) = yn0 ta thu được hai phương trình:
18
Chương 2 Phương pháp tựa nội suy 2.1
Không gian các hàm spline và B-spline
Định nghĩa 2.1.1. Cho đoạn thẳng [a, b], giả sử chia đoạn thẳng [a, b] thành n − 1 đoạn bởi các điểm chia a = t1 6 t2 6 … 6 tn = b. Kí hiệu các điểm chia đó là t = (tj )nj=1 , ti là các điểm nút. Giả sử trên mỗi đoạn [tj , tj+1 ], j = 1, 2, …, n − 1 ta có một hàm đa thức, các hàm đa thức liên tục tại các điểm nút. Khi đó ta có đường cong đa thức từng đoạn gọi là đường cong spline. Định nghĩa 2.1.2. Cho d là một số nguyên không âm và cho t = (tj )n+d+1 j=1 , các điểm nút là dãy số thực không giảm. B-spline thứ j bậc d với điểm nút t được định nghĩa bởi
Bj,d,t (x) =
tj+1+d −x x−tj tj+d −tj Bj,d−1,t (x)+ tj+1+d −tj+1 Bj+1,d−1,t (x) , j
= 1, 2, …, n+d+1
Với mọi số thực x, trong đó (
Bj,0,t (x) =
Để đơn giản trong các trường hợp tránh sự nhầm lẫn, ta thường kí hiệu spline thứ j bậc d là Bj,d , Bj,t hoặc Bj thay cho Bj,d,t (x). Nếu trong dãy các điểm nút t = (tj )n+d+1 có điểm tj xuất hiện m lần: tj = tj+1 = … = tj+m−1 j=1 thì ta nói tj là nút bội m. Dãy t = (tj )n+d+1 gọi là các điểm nút của n j=1 đường spline. 19
Ví dụ 2.1. (B-spline bậc 1) x−t
t
−x
Sd,t = span{B1,d , …, Bn,d } = {
j=1
thì Sd,t là không gian tuyến tính. Một phần tử f =
cj Bj,d của Sd,t được
j=1
Cụ thể, một phần tử f =
q cj Bj,d của Sd,t được gọi là hàm vectơ spline
hoặc đường cong spline tham số bậc d với điểm nút t, và (cj )nj=1 được gọi là hệ số B-spline hoặc điểm điều khiển của f . 20