BỘ MÔN TOÁN ỨNG DỤNG - ĐHBK

PHƯƠNG PHÁP TÍNH – HK 2 0506
CHƯƠNG 3
NỘI SUY VÀ BÌNH PHƯƠNG CỰC TIỂU
•
TS. NGUYỄN QUỐC LÂN (04/2006)
NỘI DUNG

1- NỘI SUY ĐA THỨC LAGRANGE
2- SAI SỐ NỘI SUY LAGRANGE
5- BÌNH PHƯƠNG CỰC TIỂU
3- NỘI SUY NEWTON (MỐC CÁCH ĐỀU)
4- NỘI SUY GHÉP TRƠN (SPLINE) BẬC BA
BÀI TOÁN TỔNG QUÁT VỀ NỘI SUY

x
k
: mốc nội suy, y
k
: giá trị (hàm) nội suy
Từ bảng này, nội suy giá trị y
bảng
tại điểm x = α?
Moác noäi suy x
0
x
1
… x = α ∉{ x
k
} … x

,y
k
)} , k = 0 → n
∃! đa thức L(x), bậc ≤ n, thoả đ/kiện nội suy L(x
k
) = y
k
, k = 0 … n
Cách 1: 3 mốc ⇒ n = 2 ⇒ L(x) = ax
2
+ bx + c (3 hệ số cần tìm)
Tìm đa thức nội suy Minh hoạ bảng 3 dữ liệu: {(x
k
,y
k
)} , k=0→2
Tại x = 3, y
bảng
≈?
Moác noäi suy x
k
2 2.5 4
Giaù Trò noäi suy y
k
0.5 0.4 0.25
( )
( )
( )



VÍ DỤ SAI SỐ

[ ]
( )
( )
( )
( ) ( )
xn
n
ba
xxxx
n
xf
xLxf
taïi suy Noäi
∆=−−
+
≤−
+

0
1
,
!1
max
)()(
Sai số:
Giải:
( )
[ ] [ ]

2
= 144. Yêu cầu: Làm tròn kết quả (sai
số) đến chữ số lẻ thứ 4
115
x
NHIỀU MỐC → ĐA THỨC NỘI SUY CƠ SỞ

Đa thức nội suy cơ sở tại x
k
: L
k
(x
k
) = 1, L
k
(x
i
) = 0 ∀ i ≠ k
( )
( )( )
( )( )
45.225.2
42
1
−−
−−
=
xx
xL
( )

, y
k
)}?
3 mốc ⇒ 3 ĐT NSCS
( )
xL
0
( )
xL
1
( )
xL
2
( )
xL
( )( )
( )( )
425.22
45.2
)(
0
−−
−−
=
xx
xL
CÔNG THỨC TỔNG QUÁT

(n+1) mốc ⇒ (n+1) đa thức nội suy cơ sở. Đa thức nội suy
cơ sở L

xxxxxxxx
xxxxxxxx
xL
nkkkkkk
nkk
k
≤≤
−−−−
−−−−
=
+−
+−
0,)(
110
110


)()()()(
1100
xLyxLyxLyxL
nn
+++=⇒  suy noäi thöùc Ña
Ưu điểm: Công thức tổng quát cho đa thức nội suy L(x)
Chỉ phụ thuộc bộ mốc {x
k
} (0 ≤ k ≤ n), không phụ thuộc y
k
VÍ DỤ

Bảng 4 mốc 1, 2, 3, 4 ; 4 giá trị 5, 7, 8, 9. Viết ra biểu thức

45.335.315.3
5.3
1
L
( )
)(98)(7)(5)(
3210
xLxLxLxLxL +++=
( )
4375.85.3 =⇒ L
Viết biểu thức L
k
(x) (Không tính!) Thay x → Giá trị
NỘI SUY NEWTON – MỐC CÁCH ĐỀU

Bảng {(x
k
,y
k
)} , k = 0 → n, mốc nội suy cách đều: x
0
, x
1
=
x
0
+ h, x
2
= x
1

y
2
∆
k
y
3
∆
0
y∆
1
y∆
2
y∆
0
2
y∆
1
2
y∆
0
3
y∆
∆
2
y
k
= ∆y
k+1
– ∆y
k

ĐA THỨC NỘI SUY NEWTON

Đa thức nội suy Newton tiến: x ≈x
0
(đầu bảng)
h
xx
t
0
−
=
⇔ x = x
0
+th ⇒ Đa thức nội suy tiến:
( )
( )
00
2
00
!
)1()1(
!2
1
y
n
nttt
y
tt
ytyxN
n

ntt
y
tt
ytyxN
n
nnn
∆
−+
++∆
+
+∆+=
−−


Đa thức theo t & Sai phân nằm trên đường chéo tiến
Sai phân nằm trên đường chéo lùi (từ cuối bảng đi lên)
VÍ DỤ NỘI SUY NEWTON

Cho bảng giá trị sinx từ 15° → 55°. Xây dựng đa
thức nội suy tiến (lùi) cấp 3 & tính sin16° (sin54°)
x y ∆y ∆
2
y ∆
3
y
15 0.2588
20 0.3420
25 0.4226
30 0.5
35 0.5736

x = 16° ⇒
t = 0.2 ⇒ N
1
(0.2) = 0. 2756
sin16° = 0. 2756
Đa thức nội suy lùi: x ≈ 55°
tx
x
t 555
5
55
+=⇔
−
=⇒
( ) ( )( )
!3
21
0003.0
2
1
0057.00532.08192.0)(
2
++
−
+
−+=
ttttt
ttN
x = 54°
⇒

1
138.0
038.0
Giá trị L(0.95) = Giá trị chính xác f(0.95) = 0.04
x
k
–1 –0.5 0. 0.5 1.
y
k
KẾT QUẢ

So sánh đồ thị hàm ban đầu f(x) và đa thức nội suy P
4
(x)
Tăng số nút có thể khiến sai số tăng!
NỘI SUY GHÉP TRƠN

Nội suy Lagrange: Bậc quá lớn ⇒ Đồ thị phức tạp
Thay đa thức
nội suy bậc n
bằng đa thức
nội suy bậc
thấp (bậc 1, 2,
3 …) trên
từng đoạn
[x
k
, x
k+1
],

=
=
1110
1110
1110
''''
''
xSxS
xSxS
xSxS
( )
0''
00
=xS
( )
000
yxS =
( )
110
yxS =
XÂY DỰNG HÀM NỘI SUY GHÉP TRƠN BẬC 3

Tìm hàm bậc 3 trên từng đoạn, liên tục và có đạo
hàm đến cấp 2 nội suy bảng số liệu sau:
Hàm nội suy:
( )
( )
[ ]
( )
[ ]

=
3,2,2
2,1,1
111
000
xxbaxS
xxbaxS
xS


x 1 2 3
y 2 3 –4
NỘI SUY SPLINE (GHÉP TRƠN) BẬC 3

1/ Hàm dạng bậc 3 trên từng đoạn [x
k
,x
k+1
], k = 0 → n –1
2/ Điều kiện nội suy: S(x
k
) = y
k
, k = 0, 1 … n
3/ Ghép trơn:

4/ Điều kiện biên tự nhiên: S’’(x
0
) = S’’(x
n

[ ]
( ) ( )
[ ]







∈+−+−+=
∈−+−+−+=
∈−+−+−+=
=
−−−−−−− nnnnnnnn
xxxxxcxxbaS
xxxxxdxxcxxbaS
xxxxxdxxcxxbaS
S
,,
,,
,,
1
2
111111
21
3
11
2
111111

n
)/2) hệ Ac = e với


















+
+
+
=
−−−−
10 0
)(20

0)(20
00)(2












−
−
−
−
−
−
−
−
−
=
−
−−
−
−
0
)(3)(3

)(3)(3
)(3)(3

1 0,
3
)2(
11
−=
+
−
−
=
++
nk
cch
h
aa
b
kkk
k
kk
k
10,
3
1
−=
−
=
+
nk
h
cc
d

= 2





=S
( ) ( ) ( )
[ ]
2,1,111
3
0
2
000
∈−+−+−+ xxdxcxba
( ) ( ) ( )
[ ]
3,2,222
3
1
2
111
∈−+−+−+ xxdxcxba
( ) ( ) ( )
[ ]
4,3,333
3
2
2
222

b
k
e
k
c
k
d
k

0 1 2 0 0
1 1 1
2 1 3
3 2 0 0
III/ b
k
, d
k
, 0 ≤ k ≤ 2:


0
01
0
3h
cc
d
−
=
( )


kk
yxh −
[ ]
min)(
1
2
→−=
∑
=
n
k
kk
yxhF
Giải quyết: h(x) xấp xỉ bảng {(x
k
, y
k
)} theo nghĩa BPCT
TRƯỜNG HỢP TUYẾN TÍNH

h tuyến tính: h(x) = ax + b
( )
[ ]
∑
=
−+=⇒
n
k
kk
ybaxbaF

=+
⇒
∑∑
∑∑∑
==
===
n
k
k
n
k
k
n
k
kk
n
k
k
n
k
k
ynbxa
yxxbxa
11
111
2
Giải hệ 2 phương trình 2 ẩn tìm a, b. So với đường cong y
= h
1
(x) ⇔ Tổng S = Σ (h

2
2
,,
Điểm dừng:








=
∂
∂
=
∂
∂
=
∂
∂
0
0
0
c
F
b
F
a
F

k
n
k
k
1
2
1
3
1
4
Tổng quát: Điểm dừng hàm tổng bình phương độ lệch
h = ax
2
+ bx
( )
[ ]
∑
=
−+=⇒
n
k
kkk
ybxaxbaF
1
2
2
,
0=
∂
∂