GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
KHOA TOÁN MÔN: PHƯƠNG PHÁP TÍNH
Chủ Đề 3:

THUẬT TOÁN XÁC ĐỊNH CÔNG THỨC TÍNH GIÁ TRỊ
CỦA ĐA THỨC, GHI Ở DẠNG CHÍNH TẮC, TRÊN CƠ SỞ
DÙNG CÔNG THỨC NỘI SUY NEWTON

Giảng viên hướng dẫn: TS. TRỊNH CÔNG DIỆU
Sinh viên thực hiện:

1. BÙI THỊ THƠM
2. TRẦN VĂN TÂN
3. NGUYỄN THỊ CHÍ THANH BÀI TIỂU
LUẬN
GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

TÓM TẮT NỘI DUNG

GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

II. Thuật toán:
1.Trường hợp 1: Khi các mốc nội suy cách đều (bước nhảy h đều)
2. Trường hợp 2: Khi các mốc nội suy không cách đều
III. Mã giả
Phần 4: MỘT SỐ VÍ DỤ CHI TIẾT
Phần 5: ĐOẠN CHƯƠNG TRÌNH
NHẬN XÉT CHUNG

GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

PHẦN 1: MỞ ĐẦU

Bài toán: Cho
 
Px
là đa thức bậc
n
biết:
x
0
x

1
x

…….
……
n
x

 
Px

0
y

n
y

……
…….
n



Quy ước: Trường hợp h =1 ta viết a
(n)
thay cho a
(n;h)
và đọc vắn tắt là lũy thừa suy rông bậc
n của a
II. Các dạng biểu diễn đa thức:
Cho
 
Px
là đa thức bậc n theo biến x
Dạng chính tắc của P(x) là:
 
0
n
i
i
i
P x a x



với
01
,a , ,a
n
a
là các hằng số.

0
n
i
i
i
P x c x



với
01
,c , ,c
n
c
là các hằng số.
Dạng chuẩn tắc suy rộng của
 
Px
là:
   
 
,
0
0
n
ih
i
i
P x d x x


là đa thức ở dạng chính tắc
 
1
0
n
n
i
i
P x a x




. Khi đó dư của phép chia
P(x) cho
 
x


là
 
P

.
Chứng minh:
Nếu ta chia P(x) cho
 
x



1
0
n
n
i
i
ax



,

là một số thực bất kỳ. Khi đó, ta có đẳng thức:
   
1
1
00
nn
n i n i
i i n
ii
P x a x b x x b


  


   



  
  
     

    

         


    

GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

Đồng nhất hệ số của hai vế, ta có:
00
1
,i 1,2, ,n
i i i
ba
b a b





  


V. Hệ quả:



  



(I)
+ Biến đổi từ vế trái sang vế phải của (I) đó chính là dùng phương pháp dùng sơ đồ hoocner ngược
với các hệ số cho bởi :
00
1
,i 1,2, ,n
i i i
ba
b a a





  


+ Biến đổi từ vế phải sang vế trái (I) đó chính là phương pháp dùng sơ đồ hoocner với các hệ số
cho bởi
00
1
b ,i 1,2, ,n
i i i
ab

i
i
i
P x a x




Bước 1:
Đặt
 
 
       
 
,
0 0 0 0 0 0 0
00
1 1
nn
ih
i
ii
x x P x x x x x x h x x x x h x x n h

                


Đặt:
 
0

i
P
về dạng chính tắc
0
, 0,1, ,
i
ij
i ij
j
P a x i n





Áp dụng định lý 2 ta có:
0 00
11Pb  

10 00
1 0 0 0 0
11 0 00 0
1
( ) ( ) ,
.
bb
P x x x x P x
b x b x





……
1
1 2 1
1 ( 1)0 ( 1)1 ( 1)(n 1) ( 1) j
0

n
n n n j
n n n n n
j
P b x b x b b x

   
     

    


1
0 1 n j
0

n
n n n j
n n n n n
j
P b x b x b b x


, 0,1, ,
i
ij
i ij
j
P a x i n





Để đơn giản khi tính toán ta trình bày dạng bảng như sau:
0
0



1
0
10
x

  

1
0
x

b


( 1)2i
b


…

 
 
0
1
i
x i h

    

1
2 ( 1)1
.1
i i i
bb


  

2 ( 1)1 ( 1)2
.
i i i i

nn
bBảng 1:Ttính các hệ số
ij
b
của đa thức
i
P
viết ở dạng chính tắc bằng sơ đồ Hoocne ngược
GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

Bước 2:
Ta có:
 
 
,
0
00
nn
ih
i
ii
x x P





i
ij
i i i ij
j
Q d P c x i n


  


, (0,1, , ),i 0,1, ,n
ij i ij
c d b j i   

Bảng tính các hệ số của
i
Q
:

0
d

00
c 1

…
….
….
…
….
n
d

0n
c

1n
c

……
…….
nn
cBảng 2: xác định các hệ số
ij
c
của
i
Q

Bước 3 Ta tính các hệ số
i
a…
….
….
…. I
0i
c1i
c

…
….

……
…
….
….
…

n-1
( 1)0n
c
0n
a
1n
a
2n
a

… nn
aGVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

Bảng 3: xác định các hệ số
ij
a
của
 

ax



VII. Sai phân:
1. Định nghĩa:
Định nghĩa 1:
Cho f là hàm số thực, biến số thực:
0
,xh

 Giả sử f xác định tại
00
,x x h
. Sai phân của f tại
0
x
, bước nhảy h, là số định bởi công thức:
      
0 0 0h
f x f x h f x   
. (Để đơn giản ghi
 
0h
fx
thay cho
  
0h
fx
)

:
hh
f x f x
.
 Toán tử sai phân cấp hai, bước nhảy h là ánh xạ:
22
:
hh
ff
.
Định nghĩa tương tự cho các sai phân cấp cao hơn.
Khi cần nhấn mạnh cấp của sai phân, ta gọi sai phân của hàm f trong định nghĩa là sai phân
cấp một của hàm f, hơn nữa để đơn giản trong trình bày ta quy ước gọi hàm f là sai phân cấp 0
của hàm f. Ký hiệu: hàm sai phân cấp i (
0,in
), bước nhảy h, của hàm f là:
i
h
f

Quy ước: Khi h = 1 ta bỏ bớt nhóm từ “bước nhảy h” trong các thuật ngữ trên và khi đó ta ký hiệu
f
thay cho
1
f

2. Bảng sai phân dùng tính sai phân các cấp của hàm f tại điểm
0
x
:

 
ii
y P x

 
hi
Px

 
2
hi
Px

…
 
1n
hi
Px



 
n
hi
Px

0
x

0


….
….
…. …
…
…
2n
x


2n
y


2 1 2n n n
t y y
  


2 1 2n n n
u t t
  



i
x

4
6
8
i
y

93
259
569

Giải:
Áp dụng công thức tính sai phân, ta có bảng sai phân của hàm f như sau:
i
x

i
y

 
2 i
fx

 
2
2 i
fx


.
h h h h h
f g x f x h g x f x g x f x g x f x g x h          

iii.
 
 
 
     
 
   
hh
h
f x g x - f x g x
f
x=
g g x g x+h






iv.
 
m n m n
ff

   
với

nh
f x x x n x h   
. Khi đó:
   
 
1,
0
nh
n
f x nh x x

  
.
Chứng minh:
i. Ta chứng minh
 
0,
i
h
f x i n   
(*)bằng phương pháp quy nạp
Với
1n 
, ta có
()f x x
. Khi đó:
2
( ) ( )
( ) ( ( )) 0
h

i
h
fx
,
1ik  

Ta có:
       
1
1
11
1
1
k
k
k j j k j
hk
j
f x f x h f x x h x C h x


  


       


Suy ra:
   
 

0, ( ) 1n f x
. Khi đó:
00
( ) ( ) 1 0!
h
f x f x h   

Với
0nk
, giả sử (**) đúng. Nghĩa là ta có:
( ) !
kk
h
F x k h
với
()
k
f x x
(1)
Với
1nk
, ta chứng minh (**) đúng
GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

Tức là ta chứng minh:
11
( ) ( 1)!
kk
h

1
( ) , 1, 1
ki
i
g x x i k

  

Theo cách đặt thì
deg( ) , 1, 1
i
g k i k  

Theo giả thiết quy nạp và theo (*) ta có:
! ,( 1)
()
0, 2, 1
k
k
hi
k h k
gx
ik








( ) ( )
nh
F x x x
=
1
0
0
()
n
i
x x ih





Suy ra:
( ) ( ) ( )
h
F x F x h F x   11
00
00
( ) ( )
nn
ij
x h x ih x x jh




  


[ 1, ]
0
( ) . .
nh
x x nh



VIII. Nội suy Newton :
1. Đa thức nội suy Newton:
Theo cách của Newton, ta có:
GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2 0
0
0
( ) ( )
[ , ]
f x f x
xx
f x x



0 1 0 1 0 11
, , , , , , ,[ , ] [ , ] ( ) [ , , ]
n n n n
f x x x x f x x x x x f x x x x

  

Lần lượt thay vào (1) ta được:

0 0 0 1 0 1 0 1 2
0 1 1 0 1
0 1 1 0 1
( ) ( ) ( ) [ , ] ( )( ) [ , , ]
( )( ) ( ) [ , , , ]
( )( ) ( )( ) [ , , , , ]
nn
n n n
f x f x x x f x x x x x x f x x x
x x x x x x f x x x
x x x x x x x x f x x x x


      
    
   
(2)
Trong công thức (2) nếu đặt:

0 0 0 1 0 1 0 1 2
0 1 1 0 1

xP
thoả mãn điều kiện (*)
Thật vậy, từ (5) ta có:

0,
0,
( ) ( ) ( ) ( )
( ) ( ) ( )
i i i
i i i
n
n
n
ny
f x x x i
x x i
PR
PR
  


Mặt khác, dễ dàng thấy được
0,( ) 0 ( )
i
nxiR 

Nên
0, ( ) ( )
iin
ny xiP 

Cho bộ
( , )
ii
xy
trong đó
0i
x x ih
(
, 0,h i n
). Giả sử P là một hàm đa thức có bậc bé
hơn hoặc bằng n sao cho
()
ii
P x y
. Khi đó:
    
 
,
00
0
1
!
n
ih
i
h
i
i
P x P x x x
ih

Như vậy, ta chỉ cần xác định
( 0, )
i
d i n
.
Ta có thể thấy ngay
 
00
d P x
.
 Ta xác định
1
d
:
Theo mệnh đề 1 và 2 ta có:
   
 
 
 
 
 
 
 
0, 1, 1,
1 0 2 0 0
1
0
0 1 1
.1. .2. . .
h h n h

0
2 2 2
0 2 2 0
22
.2.1. 3.2. . . 1 .
1
.2.1.
2.1. 2!
h h n h
hn
h
hh
P x d h x x d h x x d n n h x x
Px
P x d h d P x
hh

        

      

Ta xác định
3
d

   
 
    
 
 


 Tiếp tục quá trình trên ta sẽ có được:
 
0
1
!
i
ih
i
d P x
ih


Khi đó:
    
 
,
00
0
1
!
n
ih
i
h
i
i
P x P x x x
ih


i
h
i
ix f x x x
ih
hP


 


Như vậy ta đã có được công thức tính P(x) ghi ở dạng chuẩn tắc suy rộng. Sau đó, áp dụng thuật
toán ở chủ đề 2 để đưa công thức tìm được về dạng chính tắc.
IX. Cách chuyển từ bài toán có các mốc nội suy không đều về bài toán có mốc cách đều:
Nếu bài toán đa thức nội suy không cách đều ta chỉ cần thêm các mốc nội suy sao cho được
các mốc mới cách đều, sau đó dùng công thức nội suy Lagange để tính các giá trị hàm số.
Lúc này bài toán sẽ chuyển về bài toán nội suy có bước nhảy cách đều.
 Việc thêm mốc nội suy sẽ là đơn giản nếu các mốc nội suy có giá trị không quá lớn, lúc này
ta sẽ chọn bước nhảy h sao cho ít phải thêm các mốc mới nhất
Ví dụ: Ta có bảng giá trị sau:
i
x

0
1
2
4
i
y


1
2
6
9
()
ii
P x y

3
2
293
5
GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

Ở ví dụ này ta sẽ thêm
0
0x 
,
3x 
vào công thức nội suy Lagrange để tính các giá trị
i
y
và ta sẽ
có bảng giá trị mới:
x
i

0
1


…
 
1n
hi
Px



 
n
hi
Px

1
!
i
i
m
ih


 
0
1
!
i
ih
i
d P x

y

1 2 1
t y y

1 2 1
u t t

….
1 2 1
s r r

….
1
m

1 1 0
.d m t

….
…. …
…
…
….
…
2n
x

t y y

…. ….
….
n
x

n
y
n
m

0
.
nn
d m z

1
 
00
x h x  

 
00
x h x

0

…….
1
…
…….
….

………
1
( 1)1i
b


( 1)2i
b


…


…

…….

 
 
0
1
n
x n h

    

1
1n
b

2n
b

…
nn
b

GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2 Bảng 1: Tính các hệ số
ij

…. i
d

0i
c

1i
c

…
….

……
…
….
….
…
….
n
d

0n
c

1n
c…
….
….
…. i
0i
c1i
c

…
….

……
…
….
….
…

n-1
( 1)0n
c



0n
a
1n
a
2n
a

… nn
aBảng 3: Xác định các hệ số
ij
a
của
 
Px

3. Dạng bảng của thuật toán chuyển từ dạng chuẩn tắc suy rộng về dạng chính
tắc theo nhóm 2:

0
– x
0*

a'''
1

x
0

a'''
n
= d
n

a'''
n-1
= a''
n-1
– x
1*

a''
n

a'''
1
= a''
1
– x
a
1
= d
1…
…
…
…
…
…
X
n-1
= x
0
+ (n-1)*h
a
n
= d
n

a
n-1
= d
n-1
các tiến trình giải như sau:
a. Tiến trình 1: Dùng công thức nội suy Newton để xác định công thức của
 
Px
ở dạng
chuẩn tắc suy rộng.
Bước 1: Tính sai phân các cấp của
 
Px
.
Bước 2: Áp dụng định lý và công thức nội suy newton tính được giá trị của

 
Px
ở dạng
chuẩn tắc suy rộng.
b. Tiến trình 2: Chuyển từ dạng chuẩn tắc suy rộng về dạng chính tắc.
o Cách 1: Dùng thuật toán chuyển từ chuẩn tắc suy rộng sang chính tắc.(tham khảo đề tài
của nhóm 2).
o Cách 2: Dùng hoocne ngược chuyển từ dạng chuẩn tắc suy rộng về chính tắc.
2. Trường hợp 2: Khi các mốc nội suy không cách đều ta sẽ thêm các mốc nội suy
mới sao cho các mốc nội suy cách đều hoặc chọn
0
0, 1xh
rồi thêm các mốc mới
sau đó dùng công thức nội suy Lagrange tính các giá trị của hàm cho các mốc mới
thêm.
Bước 1: Tính giá trị
 
Px

x
sao cho ta được bước nhảy
1ii
h x x


là đều nhau
Bước 3: Thay các giá trị của
i
x
vừa tìm được vào công thức
 
Px
ta được giá trị
i
y
tương
ứng.
Lúc này ta được bảng giá trị mới và bài toán trở thành bài toán ở trường hợp 1 với bước
nhảy đều. Sau đó ta thực hiện các bước làm như trong trường hợp 1.
III. MÃ GIẢ:
// Nhập dữ liệu
Nhập n - số lượng các bộ (x,y)
Cho i chạy từ 0 đến n, nhập các bộ (x,y)

//Kiem tra buoc nhay h (moc deu, moc ko deu)
Sắp xếp lại các bộ số theo x tang dần
GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2


Cho i chạy từ 0 đến (n-1), z[i][i]=d[i]
Cho i giảm từ (n-2) đến 0
Cho j giảm từ (n-1) đến i
Tính các z[i][j] theo công thức z[i][j]=z[i+1][j] - x[i+1]*z[i+1][j+1]
GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

//Mảng z[][] là bước đệm để tính các hệ số a[i]
a[n] = z[n][n];
Cho j giảm từ n đến 0, tính a[j] = z[0][j] - x[0]*z[0][j+1]

// Xuất dữ liệu
Xuất các a[i],
0,in

PHẦN 4: VÍ DỤ CHI TIẾT

Ví dụ 1: Hãy xác định công thức tính P(x) bằng công thức nội suy Newton ghi ở dạng chính tắc,
biết:
 Lập bảng sai phân:
i
x

i
y

 

2

83
8
569 1
8

18

 Theo công thức nội suy Newton ta xác định được P(x) ở dạng chuẩn tắc suy rộng:
 
 
 
 
1,2 2,2
( ) 93 83 4 18 4P x x x    

 Bảng biểu diễn các hệ số của P(x) ở dạng chính tắc:
Cách 1: Chuyển theo phương pháp của nhóm 2

i
a

i
x

Vậy dạng chính tắc của P(x) là:
2
( ) 193 97 18P x x x  

Cách 2: Làm theo phương pháp dùng hoocne ngược
Ta tính các hệ số
ij
b
trước dựa vào bảng sau:
i


ij
b

0
1
0 -4
1
-4
0

-6
1
-10
24

a

93
93
0

83
83
-320
0
18
18
-180
432
ij
a

18
-97
193

Vậy dạng chính tắc của P(x) là:
2
( ) 193 97 18P x x x  

Ví dụ 2: Hãy dùng công thức nội suy Newton tìm giá trị của biểu thức
 
Px
, chuyển
 

y

sau đó sẽ dùng công thức nội suy Newton cho bài toán có bước nhảy đều.
Ta thấy vì
1 0 2 1 3 2 4 3
1x x x x x x x x       

Nên ta chọn thêm vào bảng
4
3x 
. Áp dụng công thức nội suy Lagrange:
 
 
0
0
0
()
j
ji
n
j
i
i
ij
ji
j
xx
P x y
xx



Ta dùng công thức nội suy Newton để tìm giá trị của bài toán ở dạng chuẩn tắc suy rộng.
Ta có bảng sai phân như sau:
i
x

i
y

 
1 i
fx

 
2
1 i
fx

 
3
1 i
fx

1
!
i
i
m
ih


3
-4
1
6

1

Giá trị của bài toán ở dạng chuẩn tắc suy rộng:
 
Px
     
3,1 2,1 1,1
5
2
2
x x x   

GVHD: TS. TRỊNH CÔNG DIỆU Lớp: Toán VB2- K2
NHÓM 3- LỚP: VB2-TOÁN-K2

Chuyển bài toán từ dạng chuẩn tắc suy rộng sang dạng chính tắc:
Cách 1: (theo phương pháp của nhóm 2)
Ta lập bảng sau:
i
x

1


3
1

 
32
11 11
2
22
P x x x x   

Cách 2: (theo phương pháp hoocne ngược)
Ta tính các hệ số
ij
b
trước dựa vào bảng sau:
i


ij
b

0
1


ij
c

2
2
0 1
1
0
0

5
2


5
2


5
2


0
0
1
1

0
0
3
1
-3
2
0
i
a

1
11
2


11
2

2
Vậy dạng chính tắc cần tìm là:
 
32
11 11
2
22
P x x x x   

PHẦN 5: ĐOẠN CHƯƠNG TRÌNH
Chương trình xác định hàm theo công thức nội suy Newton với bước nhảy tùy ý:
#include <iostream>

}

int main()
{
// Nhap du lieu
cout << "Nhap so luong cac bo (xi,yi) (i>0): "; cin >> n; cout << endl;
n=n-1;
cout << "Nhap cac bo gia tri (xi,yi):" << endl;;
for (int i=0; i<=n; i++) cin >> x[i] >> y[i];
cout << endl;

//Kiem tra buoc nhay h (moc deu, moc ko deu)
long tmp;
for (int i=0; i<=n; i++)
for (int j=i+1; j<=n; j++)
if (x[i]>x[j])
{
tmp=x[i];x[i]=x[j];x[j]=tmp;
tmp=y[i];y[i]=y[j];y[j]=tmp;
}
h[1] = abs(x[1]-x[0]);
for (int i=1; i<n; i++)
if (abs(x[i+1]-x[i])!=h[1])
{
h[1]=1;
Lagrange();
break;
}

//Khoi tao cac gia tri ban dau