Đa thức nội suy lagrange

  -  

Nội suy đa thức (Polyminal Interpolation) là làm sao suy đoán ra hàm số mà đi qua gần đúng tất cả các điểm dữ liệu cho trước, nhờ đó chúng ta nhận xét được tính quy luật của chúng và dự đoán được điểm dữ liệu tiếp theo.

Bạn đang xem: đa thức nội suy lagrange

Đầu tiên chúng ta cùng nghiên cứu 2 phương pháp giúp nội suy đa thức có dạng thuần nhất

*
, ko chứa các hàm toán học đặc biệt như lượng giác hay logarit. n+1 là số điểm dữ liệu mà bạn có. Điều này nghe có vẻ kỳ lạ, ví dụ bạn khảo sát một đại lượng y mà bạn tin rằng nó quan hệ với đại lượng x theo hàm bậc 2, mà bạn đo n+1 lần, hổng nhẽ hàm của bạn phải là hàm bậc n? Thực ra hàm nội suy ko phản ánh đúng mối quan hệ thực tế của 2 đại lượng. Càng thu thập nhiều điểm dữ liệu thì hàm nội suy càng tiệm cận với hàm thực, các hệ số của các số hạng bậc cao sẽ dần bé đi thôi.

Nội suy Lagrange:

Đa thức nội suy có dạng:

*
trong đó
*
.

#include‹stdio.h›int main() { int n, i, j; printf("Nhap so diem cho truoc: "); scanf("%d",&n); double x, y, X, Y=0, L; printf("Nhap toa do cac diem:\n"); for(i=0;i‹n;i++) { printf("(x%d,y%d)= ",i,i); scanf("%lf %lf",&x,&y); } printf("X= "); scanf("%lf",&X); for(i=0;i‹n;i++) { L=1; for(j=0;j‹n;j++) if(j!=i) L*=(X-x)/(x-x); Y+=L*y; } printf("Y= %lf\n",Y);}Code: computational-physics/Lagrange_Interpolation.c Nhược điểm của phương pháp nội suy Lagrange là nếu bổ sung thêm điểm dữ liệu mới là phải tính lại từ đầu. Bây giờ là làm sao khi thêm dữ liệu mới vẫn tận dụng được đa thức đã tính trước đó. Chúng ta cùng bước sang phương pháp hiệu quả hơn, đó là nội suy Newton.

Nội suy Newton:

*
*
trong đó
*
là các đạo hàm tại x=x0.

Xem thêm:

*
,
*
, …Chúng ta đặt ký hiệu như thế này:
*
+ f(x-x_0) + f(x-x_0)(x-x_1) + \cdots" class="latex" />
*
\prod^{i-1}_{j=0} (x-x_j)" class="latex" /> .Tính các đạo hàm bằng cách tạo dựng ma trận D như sau:
*
\\ y_2 & f & f \\ \vdots \\ y_n & f & \cdots & f \end{bmatrix}" class="latex" />Đạo hàm bậc cao được tạo nên bởi 2 đạo hàm bậc thấp hơn. Có cột đầu tiên là các giá trị đã biết, các cột tiếp theo được tính bằng cách
*
.

#include‹stdio.h›int main() { int n, i, j; printf("Nhap so diem cho truoc: "); scanf("%d",&n); double x, y, X, Y=0, L, D; for(i=0;i‹n;i++) { printf("(x%d,y%d)= ",i,i); scanf("%lf %lf",&x,&y); } printf("X= "); scanf("%lf",&X); for(j=0;j‹n;j++) { if(j==0) for(i=0;i‹n;i++) D=y; else for(i=j;i‹n;i++) D=(D-D)/(x-x); L=1; for(i=0;i‹j;i++) L*=X-x; Y+=D*L; } printf("Y= %lf\n",Y);}Code: computational-physics/Newton_Interpolation.c

Cả 2 phương pháp ở trên đều có nhược điểm là số bậc của đa thức nội suy gắn liền với số lượng điểm dữ liệu thu thập. Tức là mặc dù càng nhiều thông tin thì việc dự đoán điểm tiếp theo càng chính xác, nhưng hàm nội suy sẽ càng phức tạp lên ko cần thiết, tai hại hơn là làm tăng khối lượng tính toán. Phương pháp nội suy Spline ra đời, giúp chúng ta tìm ra hàm nội suy với bậc thấp hơn và ko phụ thuộc vào số lượng điểm dữ liệu. Chi tiết về thuật toán này mình sẽ tìm hiểu sau.

Nội suy Lagrange, Newton, và cả nội suy Spline đều cố vẽ ra một hàm đi qua hết tất cả các điểm, điều này ko hay lắm vì trong các thí nghiệm vật lý, sai số đo đạc là điều tất yếu, các điểm dữ liệu đâu hoàn toàn nằm trên đường đồ thị lý thuyết mà quanh quẩn gần đường lý tưởng đó thôi. Càng cố nối điểm, chúng ta càng xa rời với đường lý tưởng hơn. Bởi vậy phương pháp bình phương tối thiểu được xem là hiệu quả nhất trong các thí nghiệm thực tế, đó là vẽ ra một đường sao cho tổng bình phương khoảng cách từng điểm dữ liệu tới đường đồ thị đó là nhỏ nhất, tức là thoả mãn điều kiện

*
^2 \;\mathrm{min}" class="latex" /> với m là số bậc của đa thức, ko phụ thuộc vào số điểm dữ liệu n.

Xem thêm: Hướng Dẫn Cài Đặt Zalo Và Sử Dụng Trên Máy Tính, Đăng Nhập Zalo Trên Máy Tính

*
^2 \;\mathrm{min}" class="latex" />
*
*
^2 = 0" class="latex" /> với k = 0, 1, …, m .
*
*
= 0" class="latex" />
*
*
.Ta biểu diễn được phương trình trên bằng phép toán ma trận như sau:
*
*
*
*
*
*
*
Như vậy chúng ta chỉ cần dùng các phương pháp giải hệ phương trình như khử Gauss-Jordan chẳng hạn, giải ma trận:
*
" class="latex" />
*
*

#include‹stdio.h›int main() { int m, n, i, j, k; printf("Nhap so bac cua da thuc: m= "); scanf("%d",&m); printf("Nhap so diem du lieu cho truoc: n= "); scanf("%d",&n); double x, y, X, Y=0, F, a, p; printf("Nhap gia tri cac diem cho truoc:\n"); for(i=0;i‹n;i++) { printf("(x%d,y%d)= ",i,i); scanf("%lf %lf",&x,&y); F<0>=1; for(j=1;j‹m+1;j++) F=F*x; F=y; } for(k=0;k‹m+1||k‹n-1;k++) for(i=k+1;i‹n;i++) { p=F/F; for(j=k;j‹m+2;j++) F-=p*F; } for(k=k-1;k›0;k--) for(i=k-1;i›=0;i--) { p=F/F; for(j=k;j‹m+2;j++) F-=p*F; } for(k=0;k‹m+1||k‹n-1;k++) a=F/F; printf("Nhap X= "); scanf("%lf",&X); for(j=m;j›=0;j--) Y=Y*X+a; printf("Y= %lf\n",Y);}Code: computational-physics/Least_square_Method.c