การ nội suy Lagrange (Lagrange Interpolation)

บทนำ

สำหรับการสร้างจุดข้อมูลใหม่ภายในช่วงของชุดจุดข้อมูลที่กำหนด ใช้เทคนิคการ nội suy (Interpolation) การ nội suyแบบ Lagrange เป็นหนึ่งในวิธีเหล่านี้ เมื่อจุดข้อมูลที่กำหนดกระจายไม่สม่ำเสมอ สามารถใช้วิธีนี้เพื่อหาคำตอบ สูตรสำหรับ Lagrange Interpolation มีดังนี้:

อินพุตและเอาต์พุต

Input: รายการค่า x และ f(x) หา f(3.25)
x: {0,1,2,3,4,5,6}
f(x): {0,1,8,27,64,125,216}
Output: ผลลัพธ์หลัง Lagrange interpolation f(3.25) = 34.3281

อัลกอริทึม

largrangeInterpolation(x: array, fx: array, x1)
Input: อาเรย์ x และ fx สำหรับข้อมูลที่รู้จัก และจุด x1
Output: ค่าของ f(x1)

Begin
    res := 0 และ 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

ตัวอย่างโค้ด (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;
        // สำหรับแต่ละรอบ ให้ initialize temp product
        for (int j = 1; j <= N; j++) {
            if (i != j) {
                // ถ้า i = j ตัวส่วนจะเป็น 0
                tempProd *= (x1 - x[j]) / (x[i] - x[j]);
                // คูณแต่ละพจน์ตามสูตร
            }
        }
        tempProd *= fx[i];  // คูณ 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);
}

ผลลัพธ์

Result after lagrange interpolation f(3.25) = 34.3281