Tiểu luận Phương pháp xấp xỉ b-Spline

PHƯƠNG PHÁP XẤP XỈ B-SPLINE
Tóm tắt giải thuật spline tự nhiên:
Bước 1:
Tính :
k=0,..n-1 và giải hệ phương trình sau để tìm k=0,..n
k=1.n-1 (*)
Bước 2:
Tính theo công thức:
Bước3:
Xây dựng hàm nội suy spline bậc ba tự nhiên g(x)cần tìm:
Ví dụ:
Tìm spline bậc ba tự nhiên nội suy từ bảng số
x
0	1	3
y
1	2	8
GiẢI:
Trong đoạn [0,3]của hàm
Ta có hệ phương trình (*)dùng để xác định hệ số có dạng
vì là spline tự nhiên nên và do đó 
với k =0: ta có và và do đó
Với k=1 ta có và và do đó
Như vậy spline bậc ba cần tìm có dạng
 g(x)= 0 ≤ x ≤ 1
 1 ≤ x ≤ 3
Ví dụ 2:
x
	0	1	2
f(x)
 0 1	2
Thế vào (*)ở trên ta được
 Với k=0 ta có 
 Với k=1 ta có 
	 không phải là spline bậc ba
Ví dụ 3:
Xây dựng hàm spline bậc ba
 f(x) = cosπx
với các điểm x =0 ; 0,25 ; 0,5 ; 0,75 ; 1
Giải:
x
	0	1
f(x)
	1	 0 	-1
Xét trên [0,]
Với k=0 ta có 
	với k=1 ta có 
Xét [,1]
Ta có 
Ta được phương trình:
Với k=0 ta có 
	Với k=1 ta có
G(x)
Các Bài Toán:
B-Spline bậc ba:
Ví dụ 1: Tìm B- Spline bậc 3 tự nhiên nội suy bảng số trong đoạn [0,3] của hàm y=2x
X
0
1
0
Y
1
2
8
 Giải:
Ta có h0 = 1, h1 = 2
Dựa vào hệ phương trình : để xác định các hệ số mk có dạng: 
Vì là Spline tự nhiên nên m0 = m2 = 0 và do đó m1 = 2
Với k = 0: ta có :A0 = 1, B0 = 
Với k=1 tacó A1 = và B1 = 8 
Như vậy Spline bậc 3 cần tìm có dạng:
Trên đây là hình vẽ so sánh đồ thị hàm nội suy Spline bậc 3: y = g(x) với y= 2x trong đoạn [0,3].
Ví dụ 2:
 Hình bên chỉ ra nội suy 4 điểm bằng cách dùng 3 (cubic) f1(x) , f2(x), f3(x). Tổng quát nếu có (n + 1 ) điểm, ta cần có n hàm Spline Bậc 3 dạng:
fi(x) = A1i + A2i + A3iX2 + A4iX2
i = 1, 2, 3,, n
Có 4n hệ số Ạji , có thể xác định theo các điểm điều kiện sau :
Hàm Cubic phải gặp tất cả các điểm ở bên trong : có dược 2n phương trình:
f 1(X1)= y1; i = 1, , n
f i + 1(X1)= y1; i = 1, , n
Đạo hàm bậc 1 phải liên tục tại các điểm bên trong, dẫn đến được(n-1) phương trình f’1(Xi)= f’i + 1(X1), i = 1, 2, , n-1
Đạo hàm bậc 2 cũng phải liên tục tại các điểm bên trong ,thêm được (n-1) phương trình nữa: f’i(Xi)=f’’i+1(X1), i = 1, 2, , n-1
Hai điều kiện cuối cùng dựa vào 2 điểm cuối của đường Spline, ở đây thường 
Đăt: f’1(X0) = 0 và f’n(Xn) = 0.
Sắp xếp lại hàm f1(X0), ta chỉ cần (n-1) phương trìnhcần thiết để giải, có dạng 
Với , Với i =1, 2, , n
Đạo hàm phương trình này và áp dụng điều kiện liên tục về đạo hàm bậc nhất ta được:
Với: , Với: i =1, 2, , n - 1
Điều này tương đương với hệ phương trình tuyến tính có ẩn là đạo hàm bậc 2 tại các điểm bên trong của đường cong nội suy.
Giải hệ đại truyến này ta tìm được f’’(x1), với i = 1, 2, , n – 1 cộng với hai điều kiện biên 2 đầu.
f’(x0) = f’(xn) = 0 , đường cong nội suy sẽ hoàn toàn xác định.
Dạng ma trận của đường B-Spline bậc 2:
Ví dụ 1: Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
V6
V7
V8
V9
V10
X
-4
4
4
-4
-4
2
2
-4
-4
3
Y
3
3
-3
-3
-1.5
-1.5
1.5
1.5
0
0
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chiếu bộ (V1,V2,V3) xuống x, y ta được:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Ví dụ 2: Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
X
2
-2
2
2
Y
2
2
-2
-2
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chi ếu bộ (V1,V2,V3) xu ống x, y ta được:
T ương tự chiếu bộ xuống x, y ta được
Ví dụ 3: Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
X
-4
-3
0
2
3
Y
1
0,5
3
1,5
2
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chi ếu bộ (V1,V2,V3) xu ống x, y ta được:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Ví dụ 4: Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
V6
V7
V8
V9
V10
X
-2
-2,5
0
-3
0
5
3,5
5
4
3,5
Y
0
1
0,5
5
6
4
3
3
0
0,5
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên.
Chi ếu bộ (V1,V2,V3) xu ống x, y ta đ ược:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
 Ví dụ 5: Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
V6
V7
V8
V9
V10
X
-3
-2
0
-1
0
1
2
4
4
2
Y
0
2
0
4
5
2
1
4
1
0
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chi ếu bộ (V1,V2,V3) xu ống x, y ta đ ư ợc:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Ví dụ 6: Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
V6
V7
V8
V9
X
-4
-3
-2
-1
0
1
2
3
4
Y
1
3
-1
1
-2
2
-2
-1
2
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chi ếu bộ (V1,V2,V3) xuống x, y ta được:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Ví dụ 7: Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
X
-2,5
-1,5
0
1,5
2,5
Y
0
-1
2
-1
0
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chi ếu bộ (V1,V2,V3) xuống x, y ta được:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Ví dụ 8:Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
V6
V7
V8
V9
X
-3
0
-1,5
-1,5
1
3,5
3,5
2
5
Y
0
0
2
3,5
4
3,5
2
0
0
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chi ếu bộ (V1,V2,V3) xuống x, y ta được:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Ví dụ 9:Cho bảng các giá trị : Dùng B–spline bậc 2 :
Điểm
V1
V2
V3
V4
V5
V6
V7
V8
X
-3,5
-3
-2
0
-2
1
4
5
Y
0
4
0
1
4
6
5
0
Hãy tìm công thức biểu diễn toạ độ từng đoạn. Vẽ chúng.
Giải:
Bài toán có đồ thị như hình bên dưới.
Chi ếu bộ (V1,V2,V3) xuống x, y ta được:
T ương tự chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được:
Chiếu bộ xuống x, y ta được
Chiếu bộ xuống x, y ta được
Ví dụ 10 : Cho bản các giá trị : dùng B – spline bậc 2 (mặt phẳng)
Điểm
V1
V2
V3
V4
V5
V6
x
-5
-3
-1
2
5
8
y
1
3
0
5
-1
2
Hãy tìm công thức biểu diễn tọa độ từng đoạn. Vẽ chúng.
Giải
Ma trận tọa độ :
 	(*)
Ta xét trên từng bộ 3 đỉnh ()
Bộ (V1, V2, V3 ), chiếu xuống trục x, y thì (*) trở thành :
Điểm (), 0 ≤ t ≤ 1, vẽ nên đoạn cong 
Bộ (V2, V3, V4 ), chiếu xuống trục x, y thì (*) trở thành
Điểm (), 0 ≤ t ≤ 1, vẽ nên đoạn cong BC
Bộ (V3, V4, V5 ), chiếu xuống trục x, y thì (*) trở thành
Điểm (), 0 ≤ t ≤ 1, vẽ nên đoạn cong CD
Bộ (V4, V5, V6 ), chiếu xuống trục x, y thì (*) trở thành
Điểm (), 0 ≤ t ≤ 1, vẽ nên đoạn cong DE
Ví dụ 11 : Cho bảng các giá trị : Dùng B – Spline bậc 2 (mặt phẳng) 
Điểm
V1
V2
V3
V4
V5
V6
V7
V8
V9
x
-1
-4
5
6
4
1
3
-1
-4
y
-1
2
-1
2
4
3
6
6
2
Hãy tìm cônng thức biểu diễn tọa độ từng đoạn. Vẽ chúng .
Giải
Ma trận tọa độ :
 	(*)
Ta xét trên từng bộ 3 đỉnh ()
Ta có V9 = V2
Bộ (V1, V2, V3 ), chiếu xuống trục x, y thì (*) trở thành :
Tương tự các đoạn còn lại :
Bộ 
Bộ 
Bộ 
Bộ 
Bộ 
Bộ 
PHỤ LỤC
Cách vẽ đồ thị của đường B-Spline bằng Mathlab:
Vào Mathlab, ta gõ cú pháp sau : 
points = [x1 x2  xn ;
 	y1 y2  yn ]; 
plot(points(1,:),points(2,:),':') 
values = spcrv(points,3); 
hold on, plot(values(1,:),values(2,:)), hold off
Trong đó: x1, x2, , xn là các giá trị của x, y1, y2, , yn là các giá trị của y tương ứng. Giữa các giá trị x, y có khoảng trắng.
Sauk hi gõ xong ta enter, Mathlab sẽ hiện lên một cửa sổ Figure có vẽ đồ thị của ta. Để chỉnh sửa ta vào EditAxes Property. Trên bảng Property Editor Axes ta đánh dấu ô X, Y ở mục Grid, Gõ tên trục X ở pần X label, gõ vào giới hạn của đồ thị ở phần X limits. Ta làm tươpng tự đối với mục Y axis. 
Xong, ta vào View Plot Browser, rồi ta click phải lên các đường cong, đường thẳng để chọn màu sắc, kíchcỡ, loại đường cho đồ thị của chúng ta.
Tính đường B-spline bằng Ecxel: (double click vào hình bên dưới để xem