ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
CHƯƠNG TRÌNH CHẤT LƯỢNG CAO VIỆT-PHÁP

Môn: Phương Pháp Tính

NEVILLE’SMETHOD
METHOD
NEVILLE’S

Lớp: VP2016/1
Nhóm 5
Tp Hồ Chí Minh, ngày 19 tháng 4 năm 2018

GVHD: ThS. Lê Thái Thanh


Nhóm 5
Vy Bảo Đạt

1610685

Lý Trung Kiên

1611682

Huỳnh Thế Hào

1610875

Nguyễn Hồng Chung

1510313

Võ Nguyễn Gia Luật

1611944


1

2

Phương pháp Neville

Bài tập áp dụng


1. Phương pháp Neville


Định nghĩa

Cho hàm f được xác định tại các điểm x0, x1, x2, … xn và m1, m2, …, mk là k số nguyên phân biệt
sao cho 0 ≤ mi ≤ n. Khi đó, đa thức Largange cho hàm f(x) tại k điểm xm1, xm2, …, xmk được kí
hiệu là Pm1,m2, …,mk(x).


Ví dụ:

Cho hàm f(x) =


Xác định đa thức nội suy

ex

và các điểm

x0 = 1, x1 = 2 , x2 = 3, x3 = 4 , x4 = 6

và sử dụng
P
xthức
) này để tính xấp xỉ f(5).
1,2,4 (đa


► Đây là đa thức Lagrange cho hàm f(x) tại 3 điểm

P1,2,4 ( x ) =

x1 = 2 , x2 = 3, x4 = 6

( x − x1 )( x − x2 )
( x − x2 )( x − x4 )
( x − x1 )( x − x4 )
f ( x4 ) +
f ( x1 ) +
f ( x2 )
( x4 − x1 )( x4 − x2 )
( x1 − x2 )( x1 − x4 )

( x2 − x1 )( x2 − x4 )

P1,2,4 ( x ) =

( x − 2)( x − 3) 6 ( x − 3)( x − 6) 2 ( x − 2)( x − 6) 3
e +
e +
e
(6 − 2)(6 − 3)
(2 − 3)(2 − 6)
(3 − 2)(3 − 6)

⇒ f (5) ≈ P1,2,4 (5) =

(5 − 2)(5 − 3) 6
(5 − 3)(5 − 6) 2 (5 − 2)(5 − 6) 3
e +
e +
e
(6 − 2)(6 − 3)
(2 − 3)(2 − 6)
(3 − 2)(3 − 6)

1 6 1 2
= e − e + e3 ≈ 218.105
2
2


Định lý


 

Cho hàm f được xác định tại các điểm x0, x1, x2, … xk và xj, xi là hai số phân biệt trong bộ số
trên. Khi đó,

P(x) =

là đa thứ Larange thứ k nội suy hàm f tại k +1 điểm x0, x1, x2, …, xk .


Chứng minh:

Để dễ dàng chứng minh, ta đặt:

Q = P0,1,2,...,i −1,i +1,..., k =

( x − x0 )( x − x1 )...( x − xi −1 )( x − xi +1 )...( x − xk −1 )
f ( xk ) + ...
( xk − x0 )( xk − x1 )...( xk − xi −1 )( xk − xi +1 )...( xk − xk −1 )

Và:

)
Q = P0,1,2,..., j −1, j +1,..., k =

=> Q(x) và

( x − x0 )( x − x1 )...( x − x j −1 )( x − x j +1 )...( x − xk −1 )
( xk − x0 )( xk − x1 )...( xk − x j −1 )( xk − x j +1 )...( xk − xk −1 )


)
Q
xthức
) có bậc
là
các(đa

,

≤ k P( x)

có bậc cao nhất là k

f ( xk ) + ...


Chứng minh:
Xét tại x =

xi

Ta có:

)
( xi − x0 )( xi − x1 )...( xi − xi −1 )( xi − xi +1 )...( xi − xk )
Q ( xi ) =
f ( xi ) = f ( xi )
( xi − x0 )( xi − x1 )...( xi − xi −1 )( xi − xi +1 )...( xi − xk )


⇒ P ( xi ) =

)
( xi − x j )Q ( xi ) − ( xi − xi )Q ( xi )
xi − x j

)
= Q ( xi ) = f ( xi )


Chứng minh:
Xét tại x =

xj

Ta có:

Q( x j ) =

( x j − x0 )( x j − x1 )...( x j − x j −1 )( x j − x j +1 )...( x j − xk )
( x j − x0 )( x j − x1 )...( x j − x j −1 )( x j − x j +1 )...( x j − xk )

⇒ P( x j ) =

)
( x j − x j )Q ( x j ) − ( x j − xi )Q ( x j )
xi − x j

f (x j ) = f (x j )


= Q( x j ) = f ( x j )


Chứng minh:
Xét tại x =

với

xr

0 ≤ r ≤ k , r ≠ i, r ≠ j

Ta có:

Q ( xr ) =

( xr − x0 )( xr − x1 )...( xr − x j )...( xr − xk )
( xr − x0 )( xr − x1 )...( xr − x j )...( xr − xk )

f ( xr ) = f ( xr )

)
( xr − x0 )( xr − x1 )...( xr − xi )...( xr − xk )
Q ( xr ) =
f ( xr ) = f ( xr )
( xr − x0 )( xr − x1 )...( xr − xi )...( xr − xk )

⇒ P ( xr ) =

)

( xr − x j )Q ( xr ) − ( xr − xi )Q ( xr )
xi − x j

=

( xr − x j − xr + xi )
xi − x j

f ( xr ) = f ( xr )


► Để hạn chế số chỉ số dưới nhiều, gây khó khăn cho ghi chép và tính toán, ta đặt:

Qij = Pi − j ,i − j +1,...,i −1,i
Với

0≤ j≤i

là đa thức nội suy bậc j đi qua j+1 điểm :

xi − j , xi − j +1 ,..., xi −1 , xi

►Khi đó, định lí Neville được viết lại dưới dạng:

Qij =

( x − xi − j )Qi , j −1 − ( x − xi )Qi −1, j −1
xi − xi − j



2. Bài tập áp dụng


Bài 1 (ví dụ 4.2, trang 47): Cho bảng số liệu:
x

0

1

3

4

y

1

1

2

-1

Tính gần đúng giá trị của hàm nội suy Lagrange tại x=2.

►Sử dụng phương pháp Neville, lập bảng:

x0 = 0 Q0,0 = y0 = 1
x1 = 1 Q1,0 = y1 = 1

x2 = 3 Q = y = 2
2,0
2
x3 = 4 Q3,0 = y3 = −1

Q1,1
Q2,1

Q3,1

Q2,2
Q3,2

Q3,3


►Áp dụng công thức Neville để tính các giá trị trong bảng:

Qi , j =
⇒ Q1,1 =

⇒ Q2,1 =

⇒ Q3,1 =

( x − xi − j ).Qi , j −1 − ( x − xi ).Qi −1, j −1

( x − x0 ).Q1,0 − ( x − x1 ).Q0,0
x1 − x0
( x − x1 ).Q2,0 − ( x − x2 ).Q1,0

x2 − x1
( x − x2 ).Q3,0 − ( x − x3 ).Q2,0
x3 − x2

xi − xi − j
(2 − 0).1 − (2 − 1).1
=
=1
1− 0
(2 − 1).2 − (2 − 3).1
=
= 1,5
3 −1
(2 − 3).(−1) − (2 − 4).2
=
=5
4−3


⇒ Q2,2 =
⇒ Q3,2 =

⇒ Q3,3 =

( x − x0 ).Q2,1 − ( x − x2 ).Q1,1
x2 − x0
( x − x1 ).Q3,1 − ( x − x3 ).Q2,1
x3 − x1

( x − x0 ).Q3,2 − ( x − x3 ).Q2,2

x3 − x0

(2 − 0).1,5 − (2 − 3).1 4
=
=
3−0
3
(2 − 1).5 − (2 − 4).1,5 8
=
=
3−0
3

8
4
(2 − 0). − (2 − 4).
3
3 =2
=
4−0


►Ta được kết quả:

0

1

1


1

1

3

2

1,5

4/3

4

-1

5

8/3

►Giá trị của hàm nội suy Lagrange tại x=2 là:

Q3,3 = 2

2


,
Bài 2: Cho hàm :
Với


f ( x) = ln(1 + x)

x0 = 7 , x1 = 8 , x2 = 9 , x3 = 10 , x4 = 11

Sử dụng đa thức Lagrange, xấp xỉ giá trị của hàm tại x=8,25


►Sử dụng phương pháp Neville, lập bảng:

x0 = 7 Q0,0 = f ( x0 ) = 2, 0794
x1 = 8 Q1,0 = f ( x1 ) = 2,1972
x2 = 9 Q2,0 = f ( x2 ) = 2,3026
x3 = 10 Q3,0 = f ( x3 ) = 2,3979
x4 = 11 Q4,0 = f ( x4 ) = 2, 4849

Q1,1
Q2,1
Q3,1
Q4,1

Q2,2
Q3,2
Q4,2

Q3,3
Q4,3

Q4,4



►Áp dụng công thức Neville để tính các giá trị trong bảng:

( x − xi − j ).Qi , j −1 − ( x − xi ).Qi −1, j −1

Qi , j =
⇒ Q1,1 =
⇒ Q2,1 =
⇒ Q3,1 =
⇒ Q4,1 =

xi − xi − j

( x − x0 ).Q1,0 − ( x − x1 ).Q0,0
x1 − x0
( x − x1 ).Q2,0 − ( x − x2 ).Q1,0
x2 − x1

( x − x2 ).Q3,0 − ( x − x3 ).Q2,0
x3 − x2
( x − x3 ).Q4,0 − ( x − x4 ).Q3,0
x4 − x3

(8, 25 − 7).2,1972 − (8, 25 − 8).2, 0794
=
= 2, 2267
8−7
(8, 25 − 8).2,3026 − (8, 25 − 9).2,1972
=
= 2, 2236

9−8
(8, 25 − 9).2,3979 − (8, 25 − 10).2,3026
=
= 2, 2311
10 − 9

(8, 25 − 10).2, 4849 − (8, 25 − 11).2,3979
=
= 2, 2457
11 − 10


( x − x0 ).Q2,1 − ( x − x2 ).Q1,1

⇒ Q2,2 =

⇒ Q3,2 =

(8, 25 − 7).2, 2236 − (8, 25 − 9).2, 2267
=
= 2, 2248
9−7

x2 − x0
( x − x1 ).Q3,1 − ( x − x3 ).Q2,1

⇒ Q4,2 =

x3 − x1


(8, 25 − 8).2, 2311 − (8, 25 − 10).2, 2236
=
= 2, 2245
10 − 8

( x − x2 ).Q4,1 − ( x − x4 ).Q3,1
x4 − x2

(8, 25 − 9).2, 2457 − (8, 25 − 11).2, 2311
=
= 2, 2256
11 − 9


⇒ Q3,3 =

⇒ Q4,3 =

⇒ Q4,4 =

( x − x0 ).Q3,2 − ( x − x3 ).Q2,2
x3 − x0
( x − x1 ).Q4,2 − ( x − x4 ).Q3,2
x4 − x1
( x − x0 ).Q4,3 − ( x − x4 ).Q3,3
x4 − x0

(8, 25 − 7).2, 2245 − (8, 25 − 10).2, 2248
=
= 2, 2247

10 − 7
(8, 25 − 8).2, 2256 − (8, 25 − 11).2, 2245
=
= 2, 2246
11 − 8
(8, 25 − 7).2, 2246 − (8, 25 − 11).2, 2247
=
= 2, 2247
11 − 7


►Ta được kết quả:
7

2,0794

8

2,1972

2,2267

9

2,3026

2,2236

2,2248


10

2,3979

2,2311

2,2245

2,2247

11

2,4849

2,2457

2,2256

2,2246

►Giá trị xấp xỉ của hàm tại x=8,25 là:

Q4,4 = 2, 2247

2,2247


Cảm ƠN ThẦY VÀ CÁC BẠN
ĐÃ CHÚ Ý LẮNG NGHE


AU R
EVOI
R