Phép nội suy-Tôn Thất Thái Sơn
Một tài liệu về phép nội suy! Đây là 1 bài tiểu kuận của mình...
Phép nội suy Tôn Thất Thái Sơn
MỞ ĐẦU
Thông thường trong một số lĩnh vực, đo đạc khí tượng chẳng hạn, các đại lượng khảo sát
thường không được cho dưới dạng hàm liên tục, mà là bảng các giá trị rời rạc. Các phương
pháp giải tích toán học thường tính toán với các hàm cho bởi các công thức, do đó không thể
áp dụng trực tiếp để nghiên cứu các hàm cho dưới dạng rời rạc như thế này. Cũng có khi ta
biết rằng đại lượng y là một hàm của đại lượng x, tức là y = f(x), nhưng ta không biết biểu
thức hàm f(x) mà chỉ biết một số giá trị yi tương ứng với các giá trị x tại các điểm xi.
Thông thường thì x0 < x1 < ... < xn và các điểm này có thể phân bố cách đều hoặc không.
Mặc dù ta chỉ biết các giá trị của y tại các điểm mốc xi, nhưng trong nhiều trường hợp ta cần
tính toán với các giá trị y tại các vị trí khác của x. Một câu hỏi đặt ra là: cho một điểm x
không thuộc các điểm xi cho ở trên, làm thế nào chúng ta có thể tính được giá trị y tương ứng
với nó, sao cho chúng ta có thể tận dụng tối đa các thông tin đã có?
Bài toán nội suy là bài toán tìm giá trị gần đúng của y tại các điểm nằm giữa các giá trị x
không có trong các xi trên. Nếu cần tìm các giá trị gần đúng của y tại các điểm x nằm ngoài
khoảng [ x0 ; xn ] thì bài toán được gọi là bài toán ngoại suy. Trong phần trình bày dưới đây,
chúng ta chỉ quan tâm đến bài toán nội suy.
Vì bài toán của chúng ta không chỉ giải quyết với một giá trị x cụ thể, mà là cả một miền
giá trị nào đó của x. Do đó câu hỏi trên cũng tương đương với vấn đề sau: hãy tìm một hàm
F(x) sao cho miền xác định của nó có chứa các điểm (x0,x1,…,xn) và hàm này xấp xỉ tốt nhất
tập số liệu đã có là các cặp (x0,y0), (x1,y1), …, (xn,yn). Chúng ta thấy rằng, tập số liệu là hữu
hạn, còn các tập giá trị cần ước lượng là vô hạn, nên sẽ có vô số hàm F(x) nếu chúng ta
không đưa ra một số ràng buộc nào đó về F(x). Điều đầu tiên chúng ta quan tâm là nên chọn
dạng hàm F(x) như thế nào.
Một cách tự nhiên, ta có thể đặt điều kiện về hàm F(x) như sau:
· F(xi) = f(xi) = yi với i = 0,1,…, n.
· F(x) là duy nhất theo một số điều kiện nào đó.
· Hàm F(x) liên tục, không có điểm gấp khúc và ít thay đổi trong từng đoạn [ xi ; xi +1 ] .
Sau đây ta sẽ tìm hiểu về cách xây dựng hàm F(x) trên.
1
Phép nội suy Tôn Thất Thái Sơn
CÁC KIẾN THỨC CHUẨN BỊ
1) Tỷ sai phân và sai phân
a. Tỷ sai phân
· Định nghĩa
Xét hàm y = f ( x) trên đoạn [a; b]
Từ bảng số yi = f ( xi ) (i = 0, n)
Các mốc nội suy a º x0 < x1 < x2 < ... < xn º b .
f ( xi ) - f ( xi -1 )
Ta gọi f [ xi , xi -1 ] = (i = 1, n) là tỷ sai phân cấp một của hàm f .
xi - xi -1
Tỷ sai phân cấp hai: là tỷ sai phân của tỷ sai phân cấp một, ký hiệu là:
f [ xi +1, xi ] - f [ xi , xi -1 ]
f [ xi +1, xi , xi -1 ] = (i = 1, n - 1) .
xi +1 - xi -1
Tỷ sai phân cấp n ký hiệu là:
f [ xn , xn-1 ,..., x1 ] - f [ xn-1,..., x1, x0 ]
f [ xn , xn-1,..., x1, x0 ] =
xn - x0
Ta thấy, tỷ sai phân cấp một cần hai mốc nội suy, cấp hai cần ba mốc,…, cấp n cần n+1
mốc.
Ví dụ
sin a - sin b 2 a +b a -b
sin[a, b] = = cos sin
a -b a -b 2 2
Có thể tính tỷ sai phân thông qua cách dựng bảng như sau:
x y f [. , .] f [. , . , .] f [. , . , . , .] f [. , . , . , . , .]
x0 y0
f [ x1 , x0 ]
x1 y1 f [ x2 , x1 , x0 ]
f [ x2 , x1 ] f [ x3 , x2 , x1 , x0 ]
x2 y2 f [ x3 , x2 , x1 ] f [ x4 , x3 , x2 , x1 , x0 ]
x3 y3 f [ x3 , x2 ] f [ x4 , x3 , x2 , x1 ]
f [ x4 , x3 , x2 ]
x4 y4 f [ x4 , x3 ]
2
Phép nội suy Tôn Thất Thái Sơn
· Các tính chất của tỷ sai phân
Tính chất 1
Tỷ sai phân cấp k của một tổng bằng tổng các tỷ sai phân cùng cấp:
( f + g )[ xk , xk -1,..., x0 ] = f [ xk , xk -1,..., x0 ] + g[ xk , xk -1,..., x0 ]
Hằng số nhân được đưa ra ngoài tỷ sai phân:
(cf )[ xk , xk -1,..., x0 ] = c. f [ xk , xk -1,..., x0 ]
Tính chất này được chứng minh bằng cách truy hồi (cho k = 1, k = 2,…)
Tính chất 2
Tỷ sai phân có tính chất đối xứng:
f [ xi -1, xi ] = f [ xi , xi -1 ] (i = 1, n)
f [ xi -1 , xi , xi +1 ] = f [ xi +1 , xi , xi -1 ] (i = 1, n - 1)
f [ x0 , x1 ,..., xn ] = f [ xn , xn-1 ,..., x1 , x0 ]
Tính chất này được suy ra từ định nghĩa.
Tính chất 3
Tỷ sai phân của hằng số bằng không.
Tỷ sai phân cấp m của đa thức bậc n có tính chất:
Nếu m = n thì tỷ sai phân cấp m là hằng số.
Nếu m > n thì tỷ sai phân cấp > n là bằng không.
Chứng minh
Giả sử f ( x) = C - const "x
Khi đó:
f ( xi ) - f ( xi -1 ) C - C
f [ xi , xi -1 ] = = = 0 (Đúng)
xi - xi-1 xi - xi-1
Xét f ( x) = x k (k: nguyên dương)
x k - xik-1
Ta có f [ xi , xi -1 ] = i = xik -1 + xik - 2 xi -1 + ... + xi xik--2 + xik--1 là đa thức cấp k–1 . Áp
xi - xi -1 1 1
dụng tính chất 1 và tính tỷ sai phân lần nữa ta được đa thức bậc k – 2, và cứ thế ta thu được
tỷ sai phân cấp k của x k là đa thức bâc không, nghĩa là hằng số.
Vậy tỷ sai phân cấp k của x k là hằng số, còn tỷ sai phân cấp k+1 trở đi của x k thì bằng
không.
Bây giờ, ta xét đa thức bậc n Pn ( x) :
Pn ( x) = an xn + an-1x n-1 + ... + a1x + a0 (an ¹ 0)
Áp dụng tính chất 1 và kết quả vừa chứng minh ta suy ra đpcm.
3
Phép nội suy Tôn Thất Thái Sơn
b. Sai phân
· Định nghĩa
Như đã biết, khi các mốc nội suy cách đều nhau 1 khoảng h , ta có khái niệm sai phân
bước nhảy h của f tại x như sau:
(Vh f )( x) = f ( x + h) - f ( x)
Sai phân cấp 2 với bước nhảy h của f là
Vh2 f ( x) = (Vh (Vh f ))( x)
……………….
Tương tự ta có sai phân cấp n với bước nhảy h của f là
Vhn f ( x) = (Vh (Vhn-1 f ))( x)
Quy ước: Vh0 f ( x) = f ( x)
· Tính chất
Ta có các tính chất đã được học như:
1. Vh ( f + g )( x) =Vh f ( x) +Vh g ( x)
2. Vh (a f )( x) = a Vh f ( x)
3. Vh ( f .g )( x) = g ( x + h).Vh f ( x) + f ( x).Vh g ( x)
4. Vh ( f )( x) = g ( x).Vh f ( x) - f ( x).Vh g ( x)
g g ( x + h).g ( x)
b-1
5. åV
x =a
h f ( x) = f (b) - f (a)
6. Sai phân cấp m của đa thức bậc n có tính chất:
Nếu m = n thì sai phân cấp m là hằng số.
Nếu m > n thì sai phân cấp > n là bằng không.
7. Giả sử f Î C n[a; b] và ( x; x + nh) Ì [a; b]
Khi đó
Vhn f ( x) = f (n) ( x + q nh), q Î (0;1)
n
h
Chứng minh
Ta chứng minh bằng quy nạp.
4
Phép nội suy Tôn Thất Thái Sơn
f ( x + h) - f ( x)
Với n=1 ta có công thức số gia hữu hạn = f '( x + q h)
h
Giả sử mệnh đề trên đúng với mọi k £ n , ta chứng minh mệnh đề cũng
đúng với k = n + 1. Thật vậy:
Vhn+1 f ( x) =Vh[Vhn f ( x)] =Vh[hn f (n) ( x + q ' nh)]
Trong đó q 'Î (0;1) . Áp dụng công thức số gia hữu hạn cho f ( n) ( x + q ' nh) ta được:
Vhn+1 f ( x) = hn Vh f (n) ( x + q ' nh)
= hn [ f ( n) ( x + q ' nh + h) - f ( n) ( x + q ' nh)]
= hn+1 f (n+1) ( x + q ' nh + q '' h)
Trong đó q ',q '' Î (0;1) . Đặt q =
q ' n + q '' Î (0;1) , ta được:
n +1
Vh f ( x) = h f ( x + q (n +1)h)
n +1 n +1 ( n +1)
Suy ra mệnh đề trên đúng với mọi n.
8. Nếu f Î C n[a; b] thì khi h đủ nhỏ f ( n) ( x) ;
Vhn f ( x)
hn
Nghĩa là f ( n) ( x) = lim
Vhn f ( x)
h ®0 hn
(Tính chất này là hệ quả của tính chất 7)
c. Liên hệ giữa tỷ sai phân và sai phân
Nếu các mốc nội suy cách đều nhau, ta có mối liên hệ như sau:
f ( xi +1 ) - f ( xi ) f ( xi + h) - f ( xi ) Vh f ( xi )
f [ xi +1 , xi ] = = = (i = 0, n - 1)
xi +1 - xi xi +1 - xi h
f [ xi +1, xi ] - f [ xi , xi -1 ]
f [ xi +1 , xi , xi -1 ] =
xi +1 - xi -1
= Vh 2!hi-1)
2
f (x
(i = 1, n - 1)
…………………
Vh f ( x0 )
k
f [ xk , xk -1 ,..., x1 , x0 ] = k = 1,2,...n
k !h
2) Định lý Rolle
Cho f :[a; b] ® ¡
Nếu f liên tục trên [a; b] , khả vi trên (a; b) và thoả f (a) = f (b) thì
tồn tại điểm c Î (a; b) sao cho f '(c) = 0 .
Chứng minh: (Giải tích 1)
5
Phép nội suy Tôn Thất Thái Sơn
3) Đa thức Chebyshev
Xét hàm số Tn ( x) = cos(n.arccos x) với | x |£ 1
Đặt a = arccos x (Þ cos a = x)
Do cos(n ± 1)a = cos a .cos na m sin a .sin na
Nên cos(n + 1)a + cos(n - 1)a = 2cos a .cos na = 2 x cos na
Hay:
Tn+1( x) = cos((n + 1).arccos x) = cos(n + 1)a
= 2 x cos na - cos(n - 1)a
Tn+1( x) = 2 xTn ( x) - Tn-1( x)
Ngoài ra T0 ( x) = cos0 = 1; T1 ( x) = cos(arccos x) = x
Nên T2 ( x) = 2 xT1 ( x) - T0 ( x) = 2 x2 - 1
Dễ dàng nhận thấy Tn ( x) là một đa thức đại số có bậc n và hệ số của x n là 2n-1 .
Đa thức Tn ( x) đó được gọi là đa thức Chebyshev.
Bây giờ ta xét phương trình Tn ( x) = cos(n.arccos x) = 0
2k + 1
Suy ra arccos xk = p k = 0, n - 1
2n
2k + 1
Hay xk = cos p k = 0, n - 1
2n
Xét phương trình:
n
T 'n ( x) = - sin(n.arccos x) = 0
1- x2
ip
Þ xi = cos (i = 1, n - 1)
n
Ta có bảng biến thiên của hàm Tn ( x) như sau:
Dựa vào bảng biến thiên ta thấy được, hàm đa thức Chebysev đạt cực trị trên đoạn [-1;1]
tại các điểm:
6
Phép nội suy Tôn Thất Thái Sơn
ip
xi = cos (i = 0, n)
n
Khi đó, max | Tn ( x) |= 1 .
| x|£1
4) Các dạng đa thức
n
- Dạng chính tắc: Pn ( x) = å ai xi
i =0
n
- Dạng chuẩn tắc: Pn ( x) = å bi ( x - a)i (a Î ¡)
i =0
n
- Dạng chính tắc suy rộng: Pn ( x) = å ci x[i]
i =0
n
- Dạng chuẩn tắc suy rộng: Pn ( x) = å di ( x - a)[i,h] (a, h Î ¡ )
i =0
ì
ï k -1
ï
ï Õ
( x - ih) k >0
ï i =0
[ k ,h ] ï
Trong đó x = í1 k =0
ï 1
ï
- k -1
k Phép nội suy Tôn Thất Thái Sơn
n
INPUT : n; a , a ,..., an ; a {Đa thức chuẩn tắc có dạng Pn ( x) = å ai ( x - a)i }
0 1
i =0
n
OUTPUT: a0 , a1 ,..., an {Đa thức chính tắc có dạng Pn ( x) = å ai xi }
i =0
Giải thuật:
B1: Với mỗi k lấy giá trị từ 0 ® n -1, thực hiện B2.
B2: Với mỗi i lấy giá trị từ 1 ® n - k , thực hiện:
Gán an-i := an-i +1 *(-a) + an-i
B3: Dừng và xuất các a j ( j = 0, n) .
f. Chuyển từ chính tắc sang chuẩn tắc suy rộng
n
INPUT : n ; a , a ,..., an ; a ; h {Đa thức chính tắc có dạng Pn ( x) = å ai xi }
0 1
i =0
OUTPUT: a0 , a1 ,..., an
n
{Đa thức chuẩn tắc suy rộng có dạng Pn ( x) = å ai ( x - a)[i,h] }
i =0
Giải thuật:
B1: Với mỗi k lấy giá trị từ 0 ® n -1, thực hiện B2.
B2: Với mỗi i lấy giá trị từ 1 ® n - k , thực hiện:
Gán an-i := an-i +1 *(a + k * h) + an-i
B3: Dừng và xuất các a j ( j = 0, n) .
b. Chuyển từ chuẩn tắc suy rông sang chính tắc
Ta có 2 cách:
INPUT : n ; a0 , a1 ,..., an ; a ; h
n
{Đa thức chuẩn tắc suy rộng có dạng Pn ( x) = å ai ( x - a)[i,h] }
i =0
n
OUTPUT: a0 , a1 ,..., an {Đa thức chính tắc có dạng Pn ( x) = å ai xi }
i =0
Giải thuật 1:
B1: Gán k:=0.
B2: Gán Sk := 1
k
S10 := -a
Chuyển qua B3.
8
Phép nội suy Tôn Thất Thái Sơn
B3: Với mỗi i lấy giá trị từ k +1 ® n thực hiện:
Gán Si-1 := 0
Sik := Sik--1 - (a + k * h) * Sik-1
1
Nếu k < n -1 thì gán k := k +1 và quay lại B2
Ngược lại thì chuyển qua B4:
B4: Gán Sn := 1 .
n
Chuyển qua B5:
B5: Với mỗi m lấy giá trị từ 0 ® n thực hiện B5:
B6:Gán am := 0
Với mỗi j lấy giá trị từ m ® n thực hiện:
Gán am := am + d j * S jm
B6: Dừng và xuất các am .
Giải thuật 2:
B1: Với mỗi k lấy giá trị từ 0 ® n -1 thực hiện B2:
B2: Với mỗi i lấy giá trị từ 1 ® n - k thực hiện:
Gán an-i := an-i - (a + (n - i - k )* h)* an-i +1
B3: Dừng và xuất các a j ( j = 0, n) .
c. Đa thức từng đoạn
Cho g là hàm xác định trên [a; b]
Ta nói g là hàm đa thức từng đoạn trên [a; b] nếu có a 0 ,a1,...,a k sao cho
- a = a 0 < a1 < ... < a k = b
- g [ai ;ai +1] là đa thức trên [ai ;ai +1] i = 0,1,...k -1
Nghĩa là
ì m1
å
ï ai x
ï i =0
i
, x Î[a 0 ;a1 ]
ï m2
g ( x) = å
ï b xi
ï , x Î[a1;a 2 ]
i
í i =0
ï
ï........................
ï mk
å
ï ci xi
ï i =0
î
, x Î[a k -1;a k ]
d. Tính giá trị đa thức dựa vào sơ đồ Hoorner
* Cho Pn là đa thức bậc n, ghi ở dạng chính tắc
n
Pn ( x) = å ai xi và a Ρ
i =0
9
Phép nội suy Tôn Thất Thái Sơn
Ta có
Pn (a ) = (...((a a + a )a + a )a + ... + a )a + a
n n -1 n-2 1 0
Quy trình trên có thể viết lại:
bn-1 := ana + an-1
bn-2 := bn-1a + an -2
bn-3 := bn-2a + an-3
....................
b0 := b1a + a0 = Pn (a )
Dựa vào sơ đồ trên, ta có thuật toán tính giá trị đa thức như sau:
INPUT : n; a0 , a1 ,..., an ; a
OUTPUT : Pn (a )
Giải thuật
B1: Gán Pn (a ) := an
B2: Với mỗi i chạy từ 1 ® n gán:
Pn (a ) := Pn (a )*a + an-i
B3: Dừng và xuất Pn (a )
* Cho Pn là đa thức bậc n, ghi ở dạng chuẩn tắc suy rộng
n
Pn ( x) = å ai ( x - a)[i,h] ( a, h Î ¡ )
i =0
Ta có:
Pn (a ) = (...(an (a - a - (n -1)h) + a )(a - a - (n - 2)h) + ... + a )(a - a) + a
n -1 1 0
Quy trình trên có thể viết lại:
bn-1 := an (a - a - (n - 1)h) + an-1
bn-2 := bn-1 (a - a - (n - 2)h) + an-2
bn-3 := bn-2 (a - a - (n - 3)h) + an-3
....................
b0 := b1 (a - a) + a0 = Pn (a )
Dựa vào sơ đồ trên, ta có thuật toán tính giá trị đa thức như sau:
INPUT : n ; a0 , a1 ,..., an ;a ; a ; h
OUTPUT : Pn (a )
Giải thuật:
B1: Gán Pn (a ) := an
B2: Với mỗi i chạy từ 1 ® n gán:
10
Phép nội suy Tôn Thất Thái Sơn
Pn (a ) := Pn (a )*(a - a - (n - i)* h) + an-i
B3: Dừng và xuất Pn (a )
g. Thuật toán làm tròn đến k chữ số sau dấu phẩy
INPUT : a ; k { a là số thập phân, k >0}
OUTPUT : kq { kq là kết quả làm tròn của a }
Giải thuật:
B1: Gán b := a *10k
B2: Chuyển b từ kiểu số thực sang kiểu số nguyên bằng cách bỏ đi phần thập phân sau
dấu phẩy (ép kiểu). Lưu ý rằng, đây không phải là bước lấy phần nguyên của b .
b
B3: Gán c :=
10k
d := a - c
1
B4: Nếu d > *10- k thì gán kq := c + 10- k và chuyển qua B6.
2
1
Nếu d < *10- k thì gán kq := c và chuyển qua B6.
2
1
Nếu d == *10- k thì gán e := c%2 { e là số dư trong phép chia c cho 2} và chuyển
2
qua B5:
B5: Nếu e == 0 thì gán kq := c
Ngược lại, gán kq := c + 10- k
B6: Dừng và xuất kq .
==================================================
11
Phép nội suy Tôn Thất Thái Sơn
Đầu tiên, ta sẽ tìm dạng của hàm F(x) thông qua gợi ý của 2 định lí sau:
Định lý Weierstrass 1 về xấp xỉ hàm:
Cho f ( x) là một hàm thực liên tục xác định trên đoạn [a; b] . Khi đó, với mọi e > 0 tồn
tại một đa thức Pn ( x) bậc n với các hệ số thực sao cho với mọi giá trị x Î[a; b] ta có
| f ( x) - Pn ( x) |< e .
Định lý Weierstrass 2 về xấp xỉ hàm:
Cho f ( x) là một hàm thực liên tục xác định trên đoạn [-p ;p ] , và f (-p ) = f (p ) .
Khi đó, với mọi e > 0 tồn tại một đa thức lượng giác
a0 n
2 å j
Pn ( x) = + [a cos( jx) + b j sin( jx)]
j =1
với các hệ số thực sao cho với mọi giá trị x Î[-p ;p ] ta có | f ( x) - Pn ( x) |< e .
Từ 2 định lý trên, ta thấy rằng chọn đa thức là thích hợp cho dạng hàm F(x). Đa thức
là hàm quen thuộc và ta đã biết nhiều tính chất của nó. Do đó, kể từ đây về sau, khi nói đến
hàm nội suy, ta hiểu ngầm đó chính là hàm đa thức.
PHÉP NỘI SUY
Xét hàm y = f ( x) trên đoạn [a; b] và giả sử tại n + 1 mốc xi Î[a; b] ta đã biết giá trị:
yi = f ( xi ) (i = 0, n)
Từ các giá trị đã cho trước ở trên, ta xây dựng đa thức Pn ( x) bậc không quá n sao cho
thoả mãn điều kiện:
Pn ( x) = yi (i = 0, n) (*)
Định lý1
Đa thức nội suy Pn ( x) của hàm số f ( x) được xây dựng từ các mốc trên nếu có là duy
nhất.
Chứng minh
Giả sử có hai đa thức Pn ( x) và Qn ( x) cùng nội suy hàm số f ( x) .
Khi đó: Pn ( xi ) = yi , Qn ( xi ) = yi (i = 0, n)
Xét đa thức H ( x) = Pn ( x) - Qn ( x) là đa thức bậc £ n .
Dễ dàng thấy được: H ( x ) = Pn ( x ) - Qn ( x ) = y - y = 0 (i = 0, n)
i i i i i
Điều này có nghĩa là đa thức H ( x) có bậc £ n nhưng có tới n + 1 nghiệm x0 , x1 ,..., xn .
Như vậy H ( x) º 0 , hay Pn ( x) = Qn ( x) .
Suy ra đpcm.
12
Phép nội suy Tôn Thất Thái Sơn
Nhận xét 1
Ta có thể xây dựng Pn ( x) bằng nhiều cách, ở nhiều dạng đa thức khác nhau, nhưng vì nó
có tính duy nhất nên tất cả các dạng của nó đều có thể quy về nhau được. Ta có thể xét các
cách xây dựng Pn ( x) như sau:
I. ĐA THỨC NỘI SUY CÓ MỐC BẤT KÌ
1) ĐA THỨC NỘI SUY LAGRANGE
a. Công thức:
Theo cách của Lagrange, trước hết ta lập các đa thức bâc n: Lj ( x) thoả mãn điều kiện:
0 i¹ j
Lj ( xi ) = ì
í (**)
î1 i = j
Ta có thể thấy: "j = 0, n thì:
( x - x0 )( x - x1 )...( x - x j -1 )( x - x j +1 )...( x - xn )
L j ( x) =
( x j - x0 )( x j - x1 )...( x j - x j -1 )( x j - x j +1 )...( x j - xn )
là đa thức bậc n thoả mãn điều kiện (**)
n
Ta chọn Pn ( x) = å y j L j ( x) thì dễ dàng thấy được, Pn ( x) thoả điều kiện (*)
j =0
Đa thức được xây dựng như trên được gọi là đa thức nội suy Lagrange.
Công thức được viết lại như sau:
n n x - xj
Pn ( x) = å P( xi )Õ
i =0 j =0 xi - x j
j ¹i
b. Thuật toán xác định dạng của đa thức nội suy Lagrange:
INPUT : n; xi ; yi (i = 0, n)
OUTPUT: ai
{Đa thức có dạng
n n n n
Pn ( x) = a0 Õ ( x - x j ) + a1Õ ( x - x j ) + a2 Õ ( x - x j ) + ... + an Õ ( x - x j ) }
j =0 j =0 j =0 j =0
j ¹0 j ¹1 j ¹2 j ¹n
Giải thuật:
B1: Với mỗi i lấy giá trị từ 0 ® n thực hiện B2:
B2: Gán ai := yi
Với mỗi j lấy giá trị từ 0 ® n thực hiện:
13
Phép nội suy Tôn Thất Thái Sơn
Nếu j ¹ i thì gán ai := ai *
1
x i -x j
B3: Dừng và xuất các ai .
c. Thuật toán xác định giá trị của đa thức nội suy Lagrange tại mốc nội suy
bất kì:
INPUT : a; n; a0 , a1,..., an ; x0 , x1,..., xn
n n n n
{Đa thức có dạng Pn ( x) = a0 Õ ( x - x j ) + a1Õ ( x - x j ) + a2 Õ ( x - x j ) + ... + an Õ ( x - x j ) }
j =0 j =0 j =0 j =0
j ¹0 j ¹1 j ¹2 j¹n
OUTPUT: Pn (a )
Giải thuật:
B1: Gán Pn (a ):= 0
i := 0
B2: Gán Li := ai
Chuyển qua B3.
B3: Với mỗi j lấy giá trị từ 0 ® n thực hiện:
Nếu j ¹ i thì Li := Li * (a - x j )
Nếu i < n thì gán i := i + 1 và quay lại B2
Ngược lại thì chuyển qua B4:
B4: Với mỗi k lấy gía trị từ 0 ® n thực hiện
Gán Pn (a ):= Pn (a ) + Lk
B5: Dừng và xuất Pn (a ) .
2) ĐA THỨC NỘI SUY NEWTON
Theo cách của Newton, ta có:
f ( x) - f ( x0 )
f [ x, x ] = , do đó:
0
x - x0
f ( x) = f ( x ) + ( x - x ) f [ x, x ]
0 0 0
(1)
f [ x, x0 ] - f [ x0 , x1 ]
Ta lại có: f [ x, x0 , x1 ] = , từ đó ta có:
x - x1
f [ x, x ] = f [ x , x ] + ( x - x ) f [ x, x , x ]
0 0 1 1 0 1
Tương tự như trên:
f [ x, x , x ] = f [ x , x , x ] + ( x - x ) f [ x, x , x , x ]
0 1 0 1 2 2 0 1 2
..............................
f [ x, x , x ,..., xn-1 ] = f [ x , x ,..., xn ] + ( x - xn ) f [ x, x , x ,..., xn ]
0 1 0 1 0 1
14
Phép nội suy Tôn Thất Thái Sơn
Lần lượt thay vào (1) ta được:
f ( x) = f ( x0 ) + ( x - x0 ) f [ x0 , x1 ] + ( x - x0 )( x - x1 ) f [ x0 , x1 , x2 ] + ...
+ ( x - x0 )( x - x1 )...( x - xn -1 ) f [ x0 , x1 ,..., xn ] +
( x - x0 )( x - x1 )...( x - xn -1 )( x - xn ) f [ x, x0 , x1 ,..., xn ] (2)
Trong công thức (2) nếu đặt:
Pn ( x) = f ( x0 ) + ( x - x0 ) f [ x0 , x1 ] + ( x - x0 )( x - x1 ) f [ x0 , x1 , x2 ] + ...
+ ( x - x0 )( x - x1 )...( x - xn -1 ) f [ x0 , x1 ,..., xn ] (3)
Và R( x) = ( x - x0 )( x - x1 )...( x - xn-1 )( x - xn ) f [ x, x0 , x1,..., xn ] (4)
Thì f ( x) = Pn ( x) + R( x) (5)
Pn ( x) là đa thức bậc n. Ta cần chứng minh Pn ( x) thoả mãn điều kiện (*)
Thật vậy, từ (5) ta có:
f ( xi ) = Pn ( xi ) + R( xi ) (i = 0, n)
Û yi = Pn ( xi ) + R( xi ) (i = 0, n)
Mặt khác, dễ dàng thấy được R( xi ) = 0 (i = 0, n)
Nên yi = Pn ( xi ) (i = 0, n) (thoả điều kiện (*))
Công thức (3) được viết lại như sau:
n-1 i
Pn ( x) = f ( x0 ) + å f [ xi+1, xi -1,..., x0 ]Õ ( x - x j ) (1*)
i =0 j =0
Công thức trên là đa thức nội suy Newton tiến (do xuất phát từ mốc x0 )
Do tỷ sai phân có tính chất đối xứng, nên nếu ta sắp xếp lại các mốc nội suy theo thứ tự :
xn , xn -1, xn-2 ,..., x1, x0
Và xây dựng tương tự như trên, ta có công thức:
Pn ( x) = f ( xn ) + ( x - xn ) f [ xn , xn-1 ] + ( x - xn )( x - xn-1 ) f [ xn , xn-1, xn-2 ]
(2*)
+ ... + ( x - xn )...( x - x1 ) f [ xn , xn -1,..., x0 ]
Đây là đa thức nội suy Newton lùi (do xuất phát từ mốc xn )
3) SAI SỐ CỦA PHÉP NỘI SUY
a. Định lý2
Giả sử f là 1 hàm khả vi liên tục đến cấp (n+1) trên (a; b) É {x0 , x1,..., xn}
Gọi Pn ( x) là đa thức nội suy của f ứng với bộ mốc nội suy ( xi , yi ) (i = 0, n)
Trong đó x0 < x1 < ... < xn
Khi đó:
15
Phép nội suy Tôn Thất Thái Sơn
"x Î[ x0 , xn ] , $x Î[ x0 , xn ]:
f (n+1) (x ) n
f ( x) = Pn ( x) + Õ ( x - xi )
(n + 1)! i =0
Chứng minh
Do Pn ( x) là đa thức nội suy của hàm f ( x) trên [a; b] nên:
Pn ( xi ) = f ( xi ) = yi (i = 0, n)
Cố định x Î[ x0 ; xn ]; x ¹ xi (i = 0, n) , ta gặp sai số tại điểm x là:
R( x) = f ( x) - Pn ( x)
Để đánh giá sai số đó, ta xét hàm:
F ( x) = R( x) - kwn+1 ( x)
Với:
n
wn+1 ( x) = ( x - x0 )( x - x1 )...( x - xn ) = Õ ( x - xi )
i =0
Trong đó k là hằng số sẽ được chọn sao cho F ( x) = 0
Nghĩa là k =
R( x) = f ( x) - Pn ( x) (6)
wn+1 ( x) wn+1 ( x)
ì R( x ) =
ï f ( xi ) - Pn ( xi ) = yi - yi = 0
Hơn nữa í i
"i = 0, n
ïwn+1( xi ) = 0
î
Nên suy ra F (x ) = 0
i "i = 0, n nghĩa là F ( x) = 0 có n+2 nghiệm là
x, x , x ,..., xn
0 1
Lần lượt áp dụng định lý Rolle cho n+1 khoảng rời nhau tạo bởi n+2 mốc trên ta suy ra
F '( x) có n+1 nghiệm trên [ x0 ; xn ] .
Tiếp tục như trên ta có các kết quả F ''( x) có n nghiệm, F (3) ( x) có n-1 nghiệm,…,
F ( n+1) ( x) có một nghiệm x Î[ x0 ; xn ] , nghĩa là:
0 = F (n+1) (x ) = R(n+1) (x ) - kwnn+1) (x )
(
+1
= f ( n+1) (x ) - k (n + 1)!
f ( n+1) (x )
Từ đó ta suy ra k = (7)
(n + 1)!
f ( n+1) (x )
Từ (6) và (7) ta được: R( x) = w ( x)
(n + 1)! n+1
f (n+1) (x ) n
Hay R( x) =
(n + 1)! Õ
( x - xi )
i =0
f (n+1) (x ) n
Vậy f ( x) = Pn ( x) +
(n + 1)! Õ ( x - xi )
i =0
(đpcm)
16
Phép nội suy Tôn Thất Thái Sơn
Nhận xét 2
f (n+1) (x ) n
f ( x) - Pn ( x) =
(n + 1)! Õ ( x - xi )
i =0
n
M
(n + 1)! Õ
£ ( x - xi )
i =0
Với M = sup { f ( n+1) (x ) : x Î[ x0 , xn ]}
4) Chọn mốc nội suy tối ưu
Ta có thể thấy rằng, khi đánh giá sai số cho phép nội suy
M = sup { f ( n+1) (x ) : x Î[ x0 , xn ]} là một số hoàn toàn xác định được.
Từ nhận xét 2 ở trên, ta nhận thấy sai số chỉ còn phụ thuộc vào
n
wn+1 ( x) = Õ ( x - xi )
i =0
Như vậy, vấn đề đặt ra là phải phân bổ các mốc nội suy như thế nào để
max | wn +1 ( x) | nhỏ nhất! Có nghĩa là tìm
a £ x £b
min{max | wn +1 ( x) |}
a £ x £b
Trước hết ta chứng minh định lý sau:
Định lý 3
Xét lớp Ãn ( x) = { P ( x) - đa thức bậc n có hệ số của
n x n bằng 1}. Trong các đa thức
thuộc lớp Ãn ( x) đó thì đa thức Chebysev có dạng nn-1
T ( x) sẽ có độ lệch so với “không” là
2
nhỏ nhất trên đoạn [-1;1] , nghĩa là nếu:
Pn ( x) = x n
+ an -1 x n -1 + ... + a0 thì:
max | Pn ( x)| ³ max
| Tn ( x)| = 1
| x|£1 | x|£1 2n-1 2n-1
Chứng minh
Ta chứng minh bằng phản chứng.
Giả sử có đa thức Qn ( x) = x n + bn-1 x n-1 + ... + b thoả max | Qn ( x)| <
1
| x|£1 2n-1
0
Khi đó G( x) = Tnn-1) - Qn ( x) là đa thức có bậc không quá n-1 .
(x
2
ip
Ngoài ra tại các điểm xi = cos (i = 0, n) thì:
n
Tn ( xi ) 1
G( xi ) = - Qn ( xi ) = ± - Qn ( xi ) sẽ luân phiên đổi dấu qua các điểm
2n-1 2n-1
xi (i = 0, n) . Vậy G( x) có ít nhất n nghiệm.
17
Phép nội suy Tôn Thất Thái Sơn
Suy ra G ( x) º 0 hay Qn ( x) = Tnn-x)
(
Suy ra max | Qn ( x)| =
1 .
1
2 |x|£1 2n-1
Điểu này mâu thuẫn với giả thiết max | Qn ( x)| <
1 .
| x|£1 2n-1
Suy ra đpcm.
Nhận xét 3
Từ định lý trên, ta suy ra các mốc nội suy được chọn là các nghiệm của đa thức Chebysev
thì w ( x) sẽ có độ lệch nhỏ nhất.
Chẳng hạn, xét trên đoạn [-1;1] = [a; b] thì Tn+1 ( x) sẽ có nghiệm là
2i +1
xi = cos p i = 0, n
2(n + 1)
n
Tn+1 ( x)
Nên wn +1 ( x) = Õ ( x - xi ) =
i =0 2n
Khi đó, ước lượng tốt nhất của phép nội suy là
| R( x)|=| f ( x) - Pn ( x) |£ M | wn+1( x) |£
M
(n + 1)! 2 (n +1)!
n
Trong trường hợp [a; b] bất kì, ta thực hiện phép đổi biến để đưa về đoạn [-1;1] như sau
t = 2 x - (b + a)
b-a
Khi đó nghiệm của đa thức Chebysev (các mốc nội suy) sẽ là:
ti = 2 xi - b + a = cos 2i + 1
p
b-a b-a 2(n + 1)
1 2i + 1
Suy ra xi = {(b - a)cos p + (b + a)} i = 0, n
2 2(n + 1)
Như vậy:
n
| Tn+1(t ) | 1
| wn +1 (t ) |=| Õ (t - ti ) | = £
i =0 2n 2n
n
2 x - (b + a) 2 b+a
Þ | Õ[ - xi + ]|£ 1n
i =0 b-a b-a b-a 2
n
2 x - (b + a) - 2 xi + (b + a) 1
Þ |Õ |£ n
i =0 b-a 2
n
2( x - xi ) 1
Þ |Õ |£ n
i =0 b-a 2
n
(b - a)n+1 (b - a)n+1
Þ | wn+1 ( x) |=| Õ ( x - xi ) |£ n n+1 =
i =0 2 .2 22n+1
18
Phép nội suy Tôn Thất Thái Sơn
Suy ra ước lượng tốt nhất của phép nội suy là
M (b - a)n+1
| R( x)|=| f ( x) - Pn ( x)|£
(n + 1)! 22n +1
Ví dụ
Xét đa thức Chebysev bâc 5 (n=5) ta có 6 mốc nội suy là x0 , x1,..., x5 với
xi = cos 2i + 1 p = cos(2i + 1) p
2(5 + 1) 12
x0 = cos p , x1 = cos 3p , x2 = cos 5p
12 12 12
x3 = cos 7p , x4 = cos 9p , x5 = cos 11p
12 12 12
II. ĐA THỨC NỘI SUY NEWTON CÓ MỐC NỘI SUY CÁCH ĐỀU
1) CÔNG THỨC
Khi các mốc nội suy cách đều 1 khoảng h ta có xi = x0 + ih
x - x0
- Nếu đặt t= Þ x = x0 + th thì từ công thức (1*) :
h
Ta có công thức nội suy Newton tiến với các mốc cách đều như sau:
Pn ( x) = å 1 i Vh f ( x0 )( x - x0 )[i,h]
n
i
i =0 i!h
- Nếu đặt t = x - xn Þ x = xn + th thì từ công thứ (2*):
h
Tương tự ta có công thức nội suy Newton lùi:
Pn ( x) = å 1 i Vh f ( xn-i )( x - xn + (i -1)h)[i,h]
n
i
i =0 i !h
2) THUẬT TOÁN XÁC ĐỊNH DẠNG CỦA ĐA THỨC NỘI SUY NEWTON
Ta có thể thấy công thức Newton khi các mốc cách đều được xây dựng bằng cách đổi
biến từ công thức Newton khi các mốc không cách đều. Do đó thuật toán trong trường hợp
các mốc nội suy không cách đều hoàn toàn có thể áp dụng cho trường hợp cách đều.Vì vậy ,
ở đây ta chỉ xây dựng thuật toán cho trường hợp tổng quát.
INPUT : n; xi ; yi (i = 0, n)
OUTPUT: ai
{Đa thức có dạng
Pn ( x) = a0 + a1( x - x0 ) + a2 ( x - x0 )( x - x1) + ... + an ( x - x0 )...( x - xn-1) }
19
Phép nội suy Tôn Thất Thái Sơn
Giải thuật:
B1: Gán a0 := y0 , chuyển qua B2.
B2: Với mỗi i chạy từ 0 ® n - 1 , thực hiện:
yi+1 - yi
tsp[i] =
xi+1 - xi
Gán a1 := tsp[0]
Chuyển sang B3.
B3: Với mỗi j chạy từ 2 ® n thực hiện:
Với mỗi i chạy từ 0 ® n - j thực hiện:
tsp[i + 1] - tsp[i]
tsp[i] =
xi + j - xi
Gán a j := tsp[0]
Chuyển sang B4.
B4: Dừng và xuất các ai .
* THUẬT TOÁN TÍNH GIÁ TRỊ HÀM NỘI SUY NEWTON TỔNG QUÁT
INPUT :a ; n; a0 , a1,..., an ; x0 , x1,..., xn
{Đa thức có dạng
Pn ( x) = a0 + a1( x - x0 ) + a2 ( x - x0 )( x - x1) + ... + an ( x - x0 )...( x - xn-1) }
OUTPUT: Pn (a )
Giải thuật:
B1: Gán Pn (a ):= a0
i := 1
B2: Gán Ni := ai
Chuyển sang B3:
B3: Với mỗi j lấy giá trị từ 0 ® i - 1 thực hiện:
Gán Ni := Ni * (a - x j )
Nếu i < n thì gán i := i + 1 và quay lại B2
Ngược lại thì chuyển qua B4:
B4: Với mỗi k lấy giá trị từ 1 ® n thực hiện:
Gán Pn (a ):= Pn (a ) + N k
B5: Dừng và xuất Pn (a ) .
Nhận xét 4:
Khi các mốc nội suy cách đều, công thức nội suy Newton cho ta 1 đa thức có dạng chuẩn
tắc suy rộng: với a = x0 (công thức tiến), khi đó, ta có thể chuyển đổi dạng đa thức và tính
giá trị hàm nội suy tại dựa vào các thuật toán đã trình bày ở phần đầu.
20
