Lagrange इंटरपोलेशन एक ऐसी तकनीक है जिसका उपयोग एक ऐसा बहुपद (polynomial) निकालने के लिए किया जाता है जो $n$ बिंदुओं के समूह से होकर गुजरता है।

एक वेक्टर को बहुपद के रूप में इंटरपोलेट करना

उदाहरण

दो बिंदुओं से होकर गुजरने वाली एक सीधी रेखा

मान लीजिए कि यदि हमारे पास दो बिंदु हैं, तो उन्हें एक रेखा के साथ इंटरपोलेट किया जा सकता है। उदाहरण के लिए, $(1, 1)$ और $(2, 2)$ दिए जाने पर, हम एक ऐसी रेखा खींच सकते हैं जो दोनों बिंदुओं को काटती है, यह $1$ डिग्री (घात) का बहुपद $y = x$ होगा।

एक अकेला बिंदु

अब मान लीजिए कि यदि हमारे पास एक बिंदु है, तो हम उस बिंदु से 0 डिग्री वाले बहुपद के साथ एक रेखा खींच सकते हैं। उदाहरण के लिए, यदि बिंदु $(3, 5)$ है, तो हम उससे होकर एक रेखा $y = 5$ खींच सकते हैं (जो $0$ डिग्री का बहुपद है)।

तीन बिंदु और एक परवलय (parabola)

यह पैटर्न कि हम $n$ बिंदुओं से होकर (अधिकतम) $n - 1$ डिग्री वाले बहुपद के साथ “एक बहुपद खींच सकते हैं”, किसी भी संख्या में बिंदुओं के लिए लागू होता है। उदाहरण के लिए, बिंदु $(0, 0), (1, 1), (2, 4)$ को $y = x^2$ के साथ इंटरपोलेट किया जा सकता है। यदि ये बिंदु एक सीधी रेखा में होते, उदाहरण के लिए $(0, 0), (1, 1), (2, 2)$, तो हम 1 डिग्री वाले बहुपद $y = x$ के साथ $(1, 1)$ और $(2, 2)$ से होकर एक रेखा खींच सकते थे, लेकिन आम तौर पर, तीन बिंदु संरेख (collinear) नहीं होंगे, इसलिए हमें सभी बिंदुओं को पार करने के लिए 2 डिग्री वाले बहुपद की आवश्यकता होगी।

Lagrange इंटरपोलेशन के लिए Python कोड

हमारे उद्देश्यों के लिए यह समझना महत्वपूर्ण नहीं है कि इस बहुपद की गणना कैसे की जाए, क्योंकि इसके लिए गणित की लाइब्रेरी मौजूद हैं जो हमारे लिए यह काम करेंगी। सबसे आम एल्गोरिदम Lagrange interpolation है और हम दिखाते हैं कि इसे Python में कैसे किया जाता है।

Float का उदाहरण

हम Lagrange इंटरपोलेशन का उपयोग करके एक बहुपद $p(x)$ की गणना कर सकते हैं जो $(1,4), (2,8), (3,2), (4,1)$ बिंदुओं से होकर गुजरता है।

Copy
from scipy.interpolate import lagrange
x_values = [1, 2, 3, 4]
y_values = [4, 8, 2, 1]

print(lagrange(x_values, y_values))
#      3      2
# 2.5 x - 20 x + 46.5 x - 25

Finite field का उदाहरण

आइए पहले वाले ही बहुपद का उपयोग करें, लेकिन इस बार हम फ्लोटिंग पॉइंट नंबरों के बजाय finite field $\mathbb{F}_{17}$ का उपयोग करेंगे।

Copy
import galois
import numpy as np
GF17 = galois.GF(17)

xs = GF17(np.array([1,2,3,4]))
ys = GF17(np.array([4,8,2,1]))

p = galois.lagrange_poly(xs, ys)

assert p(1) == GF17(4)
assert p(2) == GF17(8)
assert p(3) == GF17(2)
assert p(4) == GF17(1)

इंटरपोलेटिंग बहुपद की विशिष्टता (Uniqueness)

हमारे बिंदुओं $(1, 1), (2, 2)$ के उदाहरण पर वापस चलते हैं, सबसे कम डिग्री का बहुपद जो उन्हें इंटरपोलेट करता है वह $y = x$ है। सामान्य तौर पर,

$n$ बिंदुओं के एक सेट के लिए, अधिकतम $n - 1$ डिग्री का एक विशिष्ट (unique) सबसे कम-डिग्री वाला बहुपद होता है जो उन्हें इंटरपोलेट करता है।

सबसे कम डिग्री का बहुपद जो बिंदुओं को इंटरपोलेट करता है उसे कभी-कभी Lagrange polynomial कहा जाता है।

इसका परिणाम यह है कि

यदि हम $n$ लंबाई वाले एक वेक्टर को Lagrange इंटरपोलेशन के माध्यम से बहुपद में बदलने के लिए $x$ मानों के रूप में $(1,2,...,n)$ बिंदुओं का उपयोग करते हैं, तो परिणामी बहुपद विशिष्ट (unique) होता है।

दूसरे शब्दों में, किसी वेक्टर को इंटरपोलेट करने के लिए x-मानों का एक सुसंगत आधार (consistent basis) दिए जाने पर, एक विशिष्ट बहुपद होता है जो दिए गए वेक्टर को इंटरपोलेट करता है। दूसरे तरीके से कहें तो, प्रत्येक $n$ लंबाई वाले वेक्टर का एक विशिष्ट बहुपद प्रतिनिधित्व (unique polynomial representation) होता है।

अनौपचारिक रूप से, प्रत्येक $n$ लंबाई वाले वेक्टर का एक विशिष्ट $n - 1$ डिग्री का बहुपद होता है जो इसका “प्रतिनिधित्व” करता है। यदि बिंदु संरेख (collinear) हैं, तो डिग्री कम हो सकती है, लेकिन वेक्टर विशिष्ट होगा।

“सबसे कम डिग्री” वाला हिस्सा महत्वपूर्ण है। दो बिंदु दिए जाने पर, ऐसे बहुपदों की एक बहुत बड़ी संख्या होती है जो उन दो बिंदुओं को पार करते हैं – लेकिन सबसे कम डिग्री वाला बहुपद विशिष्ट (unique) होता है।