Nội suy Lagrange (Lagrange Interpolation)

Giới thiệu

Để xây dựng các điểm dữ liệu mới trong phạm vi của một tập hợp điểm dữ liệu rời rạc đã cho, kỹ thuật nội suy được sử dụng. Nội suy Lagrange là một trong số đó. Khi các điểm dữ liệu cho trước không được phân bố đều, ta có thể sử dụng phương pháp nội suy này để tìm giải pháp. Đối với nội suy Lagrange, ta phải tuân theo phương trình sau:

Đầu vào và Đầu ra

Đầu vào: Danh sách x và f(x). Tìm f(3.25)
x: {0,1,2,3,4,5,6}
f(x): {0,1,8,27,64,125,216}
Đầu ra: Kết quả sau nội suy Lagrange f(3.25) = 34.3281

Thuật toán

largrangeInterpolation(x: array, fx: array, x1)
Đầu vào: Mảng x và mảng fx để lấy dữ liệu đã biết trước, và điểm x1.
Đầu ra: Giá trị của f(x1).

Begin
    res := 0 và tempSum := 0
    for i := 1 to n, do
        tempProd := 1
        for j := 1 to n, do
            if i ≠ j, then
                tempProf := tempProd * (x1 – x[j])/(x[i] – x[j])
        done
        tempPord := tempProd * fx[i]
        res := res + tempProd
    done
    return res
End

Ví dụ (C++)

#include <iostream>
#define N 6
using namespace std;

double lagrange(double x[], double fx[], double x1) {
    double res = 0, tempSum = 0;
    for(int i = 1; i <= N; i++) {
        double tempProd = 1;
        // mỗi lần lặp khởi tạo temp product
        for(int j = 1; j <= N; j++) {
            if(i != j) {
                // nếu i = j, mẫu số sẽ là 0
                tempProd *= (x1 - x[j])/(x[i] - x[j]);
                // nhân từng hạng tử theo công thức
            }
        }
        tempProd *= fx[i];  // nhân f(xi)
        res += tempProd;
    }
    return res;
}

main() {
    double x[N+1] = {0,1,2,3,4,5,6};
    double y[N+1] = {0,1,8,27,64,125,216};
    double x1 = 3.25;
    cout << "Result after lagrange interpolation f(" << x1 << ") = " << lagrange(x, y, x1);
}

Kết quả

Result after lagrange interpolation f(3.25) = 34.3281