BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HCM
KHOA TOÁN – TIN HỌC
1
GVHD: TS TRỊNH CÔNG DIỆU
LỚP: VB2 K2
Nhóm 22 gồm:
Hồ Thị Thu Sương
Lê Thị Mỹ Tiên
Chung Thị Bích Ngọc
Nguyễn Văn Minh
TP.Hồ Chí Minh năm 2014
Bài thuyết trình môn:
Vấn đề:
Thuật toán xác định biểu diễn thập phân căn bậc n của
một số thực không âm (n là số nguyên dương); Kết quả
ghi ở dạng biểu diễn thập phân.
Từ đó xây dựng thuật toán xác định dạng thập phân căn
bậc n của một số thực.
ỨNG DỤNG PHƯƠNG PHÁP NỘI SUY LAGRANGE
Mục lục
PHƯƠNG PHÁP NỘI SUY LAGRANGE 3
I.Đặt vấn đề: 3
II.Đa thức nội suy Lagrange : 3
III.ĐÁNH GIÁ SAI SỐ CỦA NỘI SUY LAGRANGE 5
IV. ỨNG DỤNG VÀ VÍ DỤ : 7
V.Thuật toán tính gần đúng f(c) dựa trên đa thức nội suy lagrange: 9
VI. Hạn chế của đa thức nội suy lagrange: 9
2
PHƯƠNG PHÁP NỘI SUY LAGRANGE
I. Đặt vấn đề:

Trong toán học ta thường gặp các bài toán liên quan đến khảo sát và tính giá trị
các hàm
( )y f x=
nào đó. Tuy nhiên trong thực tế có trường hợp ta không xác
định được biểu thức của hàm
( )f x
mà chỉ nhận được các giá trị rời rạc:
0
y
,
1
y
, ,
n
y
tại các điểm tương ứng
0 1
, , ,
n
x x x
.
Vấn đề đặt ra là làm sao để tính
( )y f c=
Cho nên ta dùng phương pháp nội suy
LAGRANGE
II. Đa thức nội suy Lagrange :
1. Định nghĩa : cho n số
0 1 2
( , , , , )
n

x x x x
phân biệt và n số
0 1 2
( , , , , )
n
y y y y

tùy ý thì tồn tại một đa thức
( )p x
với bậc không quá
1n −
thỏa mãn:
( ) ; 1,2,3, , (1)
i i
p x y i n= ∀ =
Công thức nội suy:
( )
( )
0
( )
n
i
i
j j i
j i
x x
p x
x x
= ≠
−

=
−
∏
,
1,2,3, , i n=
(2)
Khi đó:
( )
( )
0 0
0
( ) ( ) . (3)
n
n n
i
i i i
i i
j j i
j i
x x
L x y p x y
x x
= =
= ≠
−
= =
−
∑ ∑
∏
•

0 1 2
, , , ,
n
x x x x
được gọi là các nút nội suy
• Với
2n =
đa thức là:
( )
( )
( )
( )
0
1
0 1
0 1 1 0
( ) . (4)
x xx x
L x y y
x x x x
−−
= +
− −
• Với
3n =
đa thức là:
( ) ( )
( ) ( )
( )
( )

( )
( )
( )
( )
( ) ( )
0 2 0 1
1 2
0 1 2
0 1 0 2 1 0 1 2 2 0 2 0
( ) . . (5)
x x x x x x x xx x x x
L x y y y
x x x x x x x x x x x x
− − − −− −
= + +
− − − − − −
• Với n thì đa thức với bậc không quá
1n
−
có dạng:
3
( )
( )
0 0
0
( ) ( ) .
n
n n
i
i i i

i i
j j i
j i
x x
L x y p x y
x x
= =
= ≠
−
= =
−
∑ ∑
∏
Ý nghĩa hình học:
•
Với
deg ( ) 2, ( )P x y P x= =
là parabol đi qua 3 điểm.
• Với
deg ( ) 1, ( )P x y P x= =
là đường thẳng đi qua 3 điểm không cùng phương
với trục hoành.
• Với
deg ( ) 0, ( )P x y P x= =
là đường thẳng đi qua 3 điểm cùng phương với trục
hoành.
2. CÁCH XÁC ĐỊNH :
Cho
1n +
mốc nội suy

0 0
( , ), ,( , )
n n
x y x y
đa thức nội suy
( )
k
f x x=
theo
LAGRANGE được xác định như sau:
Bước 1: chọn mốc nội suy
0 0
( , ), ,( , )
n n
x y x y
sao cho thỏa điều kiện
0 0
1
k
n x n≤ < +
và cho giá trị sai số tốt nhất.
Bước 2: xác định các đa thức lagrange dưới dạng cơ bản
( )
i
p x
có dạng:
( )
( ) ( )
( ) ( )
( ) ( ) ( ) ( ) ( )

( )
( )
0 1 2 3
0
0 1 2 3

( )

n
j
n
i
j j i
i i i i i n
i j
x x
x x x x x x x x x x
p x
x x x x x x x x x x
x x
= ≠
−
− − − − −
= =
− − − − −
−
∏
4
0,1, ,i n=
{

1
0
( )
k i
i k k i
p x
=
≠
=
Bước 3 : đa thức nội suy lagrange được xác định bởi:
( )
( )
0 0
0
( ) ( ) .
n
n n
j
i i i
i i
j j i
i j
x x
L x y p x y
x x
= =
= ≠
−
= =
−

∑ ∑
∏
( ) ( )
( ) ( )
( ) ( ) ( ) ( )
( )
( )
( ) ( )
( )
( )
( ) ( )
( )
( )
( ) ( )
( ) ( ) ( ) ( )
1 2 3
0
0 1 2 0 3 0
0 2 3
1
1 0 1 2 1 3 1
0 1 3 1
0 2 3 1



.




.

n
o n
n
n
n
n
n n n n n
x x x x x x x x
y
x x x x x x x x
x x x x x x x x
y
x x x x x x x x
x x x x x x x x
y
x x x x x x x x
−
−
− − − −
=
− − − −
− − − −
+
− − − −
+ +
− − − −
+
− − − −

III. ĐÁNH GIÁ SAI SỐ CỦA NỘI SUY LAGRANGE
a. Định lý rolle
Nếu
( )f x
liên tục trên đoạn
[ ]
,a b
khả vi tại mọi
( )
,x a b∈
với
( ) ( )f a f b=
thì
tồn tại
( , )a b
ε
∈
sao cho
( ) 0f
ε
′
=
Áp dụng đánh giá sai số khi tính
( ) ( )
n
f c L c≈
Giả xử
( )f x
có đạo hàm liên tục đến cấp
1n +

trên đoạn
0
[ , ]
n
x x
Tìm các phần dư có dạng:
5
( )
1
0
( )
n
n i
i
R x k x x
+
=
= −
∏

Đặt
0
( ) ( ) ( ) ( )
n
n i
i
F x f x L x k x x
=
= − − −
∏

Tính k sao cho F(x) có ít nhất
2n +
nghiệm
0 1
( , , , và c)
n
x x x

• F(x) có
2n +
nghiệm
⇒
( ) ó 1F x c n
′
+
nghiệm (định lý Rolle)
• F(x) có
1n +
nghiệm
⇒
( ) ó F x c n
′′
nghiệm (định lý Rolle)
• …
• Tương tự :
1
( )
n
F x
+

có 1 nghiệm, ta gọi nghiệm nội suy
ξ

1 1 1 1
0
( ) =0 ( ) ( ) ( ( )) 0
n
n n n n
n i
i
F f L k x x
ξ ξ ξ
+ + + +
=
⇔ + + − =
∏
Mà :
1
( ) 0( )
n
n
L x x
+
= ∀
1
0
( ( )) ( 1)!
n
n
i

i
k x x k n
+
=
− = +
∏
vậy sai số có dạng cần tìm:
1
1
1
0
( )
( ) = ( ) ( ) ( ))
( 1)!
n
n
n
n n i
i
f
R x f x L x x x
n
ξ
+
+
+
=
− = −
+
∏

nếu
1
0
( ) ( ( , )
n
n
f x M x x x
+
≤ ∀ ∈
thì sai số của lagrange có thể viết
1
0
( ) = ( ) ( ) ( )
( 1)!
n
n n i
i
M
R x f x p x x x
n
+
=
− = −
+
∏
b/ Chọn mốc nội suy tối ưu.
Với công thức đánh giá sai số
1 1
0
| | | ( ) ( ) | | ( ) | | ( ) |

( 1)! ( 1)
n
n n i n
i
M M
R f x L x x x x
n n
π
+ +
=
= − ∂ ≤ − =
+ +
∏

6
Cần chọn các
[ ]
;
i
x a b∈
để
[ ;b]
max ( )
x a
f x
∈
là nhỏ nhất
IV. ỨNG DỤNG VÀ VÍ DỤ :
Với n giá trị phân biệt
0 1 2

, , , ,
n
x x x x
áp dụng công thức nội suy cho đa thức
1
1
( ) , 1
k
y f x x n
k
= = ≤ −
(
deg ( ) 1f x n= −
)
( )
1
1
1,
1 1
( )
( ) .
( ) ( ) ( )
n
k
j j
n n
k
i j i
i
i

i j
j j i
x x x
x p x
f x y
x x p x f x
= ≠
= =
−
= =
′ ′
−
∏
∑ ∑
Vậy biểu thức của đa thức có hệ số
1n
x
−
là
1
1
( ) .
( )
k
n
j
i
j
i
x

f x y
f x
=
=
′
∑
so sánh với
1
( )
k
y f x x= =
ta được đẳng thức sau:
1
1
0
( )
k
n
j
j
i
x
f x
=
=
′
∑
(1,2,3, , -2)k n∀ =
1
1

1
( ) .
( )
k
n
j
i
j
i i
x
f x y
f x y
=
= =
′
∑
(
1
1n
k
≤ −
)
Ví d ụ 1 : Tìm đa thức nội suy đối với hàm
( )y f x x= =
được cho trong bảng.
0 4x≤ ≤
i
x
0 1 4
i

y
0 1 2
Giải: Các Đa Thức Lagrange Cơ Bản
( ) ( )
( ) ( )
2
0
1 4
5 4
( )
0 1 0 4 4
x x
x x
p x
− −
− +
= =
− −
7
( ) ( )
( ) ( )
2
1
0 4
4
( ) =
1 0 1 4 3
x x
x x
p x

− −
−
=
− − −

( ) ( )
( ) ( )
2
4
0 1
( )
4 0 4 1 12
x x
x x
p x
− −
−
= =
− −
Đa thức nội suy lagrange:
3 3 3
2 0 0 1 1 2 3
0
2
( ) ( ) ( ) ( ) ( )
1 7
6 6
n
n
i i

i
L x y p x y p x y p x y p x
x x
=
= = + +
−
= +
∑
Tính
(2)f
=?
2
1 7 5
(2) 4 2 1,6666(6)
6 6 3
L
−
= + = =
Ví dụ 2: cho f(x) bởi bảng sau: tính
(3) ?f =
với
( )f x x=
,
0 49x≤ ≤
i
x
0 1 4 9 16 25 36 49
i
y
0 1 2 3 4 5 6 7

Đa thức nội suy lagrange: với n=7
7
0
1
( ) ( ) ( 4)( 9)( 16)( 25)( 36)( 49)
14515200
1
- x(x-1)(x-9)(x-16)(x-25)(x-36)(x-49)
10886400
1
+ x(x-1)(x-4)(x-16)(x-25)(x-
14515200
n
n
i i
i
L x y p x x x x x x x x
=
= = − − − − − −
∑
36)(x-49)
1
- x(x-1)(x-4)(x-9)(x-25)(x-36)(x-49)
29937600
1
+ x(x-1)(x-4)(x-9)(x-16)(x-36)(x-49)
95800320
1
- x(x-1)(x-4)(x
518918400

-9)(x-16)(x-25)(x 49)
1
+ x(x-1)(x-4)(x-9)(x-16)(x-25)(x-36)
6227020800
−
8
3
7814664 15629328 2604888 253 299 23 11
(3)
14515200 10886400 14515200 6300 40320 25200 218400
=1.828198642
L = + − + − + −
Từ ví dụ 2: ta có sai số lagrange như sau:
1
1
1
0
( )
( ) = ( ) ( ) ( ))
( 1)!
n
n
n
n n i
i
f
R x f x p x x x
n
ξ
+

+
+
=
− = −
+
∏
Với n=7,
7
(3) 1.828198642L =
8
7
8
0
( )
( ) = ( ) ( ) ( )
8!
n
n i
i
f
R x f x p x x x
ξ
=
=
+ = −
∏
Với
8 8
8 4
8

1 1 1
( ) ( ( )
2 3 20736
(2 )
f f x
x
ξ
′
= ≤ = =
8
7
8
0
8 4
( )
( ) = ( )
8!
1
( 1)( 4)( 9)( 16)( 25)( 36)( 49)
8!2 3
1
.(15629328) 0.01869367973
8!20736
n
i
i
f
R x x x
x x x x x x x x
ξ

=
=
−
= − − − − − − −
= =
∏
Vậy:
(3) 1.828198642 0.01869367973f = ±
V. Thuật toán tính gần đúng f(c) dựa trên đa thức nội suy lagrange:
• Input: cho mảng {(x
0
,y
0
),(x
1
,y
1
),…,(x
n
,y
n
)}
• L=0 ;
• I=0,1,2,…,n
{
//Tính giá trị đa thức Lagrange cơ bản thứ i
P
i
=1
• J=0,1,2,…,n

If i≠j then
P
i
=P
i
*(c-xj)/(x
i
-x
j
)
//Cộng y
i
*L
i
vào kết quả
o L=L+y
i
*P
i ;
}
Return L ; // L là giá trị gần đúng của F(c) tìm được
VI. Hạn chế của đa thức nội suy lagrange:
9
Mỗi khi thêm mốc nội suy, ta phải tính lại toàn bộ đa thức (các đa thức lagrange
cơ bản và đa thức nội suy lagrange).
Đa thức newton khắc phục được tình trạng này.
TÀI LIỆU THAM KHẢO:
/> /> />Các bài giảng Phương pháp tính của TS Trịnh Công Diệu.
10