لکیری اقل مربعات

تجربات سے اکثر ایسا ڈیٹا اکٹھا ہوتا ہے جسے کسی کثیر رقمی سے تقرب کرنا مفید رہتا ہے۔ فرض کرو کہ کسی تجربے کے نتیجے میں ہمیں n پیمائش جوڑے ملتی ہیں:
:\ (x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)
ان کے گراف کو دیکھتے ہوئے ہم یہ فیصلہ کرتے ہیں کہ یہ دالہ \ y=f(x)، ذیل میں سے کسی کثیر رقمی
# \ y=a x + b (گراف لکیری خط)
# \ y=a x^2 + bx + c (درجہ دوم کثیر رقمی)
# \ y=a x^3 + bx^2 + cx + d (سہ کثیر رقمی)
# \ \cdots \cdots \cdots \cdots \cdots
# \ y=c_m x^m + c_{m-1}x^{m-1} + c_1 x + c_0 (m کثیر رقمی)
سے تقرب کی جا سکتی ہے۔

تصغیر
تصویر میں گیارہ نکتوں (x,y) کا درجہ دوم کثیر رقمی سے تقرب کیا گیا ہے۔

تجربہ سے حاصل ہونے والے n جوڑے اگر درجہ m کے کثیر رقمی میں ایک ایک کر کے ڈالے جائیں تو ہمارے پاس n مساوات حاصل ہوں گی، جنہیں درج ذیل میٹرکس مساوات کی صورت لکھا جا سکتا ہے (عام طور پر n > m ):


Y \approx M C


Y = \begin{bmatrix}
y_1 \\ y2 \\ \vdots \\y_n
\end{bmatrix} \,,\,
M = \begin{bmatrix}
1 & x_1 & x_1^2 & \cdots & x_1^m \\
1 & x_2 & x_2^2 & \cdots & x_2^m \\
\vdots & \vdots & & \vdots \\
1 & x_n & x_n^2 & \cdots & x_n^m \\
\end{bmatrix} \,,\,
C = \begin{bmatrix}
c_0 \\ c_1 \\ \vdots \\ c_m
\end{bmatrix}


عام طور پر یکلخت لکیری مساوات کا نظام
:MC=Y
ناموافق ہو گا، اس لیے اس کا کوئی حل نہیں ہو گا، یعنی ایسا کوئی C نہیں جو ان مساوات کی تسکین کرے۔ اس لیے کوشش یہ ہو گی کہ ایسا \ C^{*} نکلا جائے جس کا غلطی سمتیہ \ e = Y -MC^* کم سے کم ہو۔ یعنی غلطی سمتیہ کا امثولہ \|e \| کم سے کم ہو۔

چونکہ سمتیہ Y فضا \mathbb{R}^n میں ہے، اس لیے ہمیں اقلیدسی فضا میں امثولہ کی عام تعریف استعمال کرتے ہوئے
:\|e\|^2 = e_1^2 + e_2^2 + \cdots + e_n^2
کی تصغیر کرنا ہے۔

اب لکیری فضا \mathbb{R}^{m+1} کے کسی سمتیہ C کے لیے،
سمتیہ MC، میٹرکس M کی ستون فضا میں ہے، جو \mathbb{R}^n کی لکیری ذیلی فضا ہے۔ اب مسقط کی تعریف سے ہم جانتے ہیں کہ سمتیہ Y کا میٹرکس M کی ستون فضا میں مسقط، غلطی امثولہ \|e\| کی تصغیر کرتا ہے۔ ذیلی فضا MC میں سمتیہ Y کے مسقط کو ہم \ MC^{*} لکھتے ہیں۔ بہترین تقرب مسلئہ اثباتی کی رو سے غلطی سمتیہ قائم الزاویہ ہو گا ذیلی فضا کے۔ دوسرے لفظوں میں غلطی سمتیہ اور میٹرکس M کی ستون فضا کے کسی بھی سمتیہ MC کا اندرونی حاصل ضرب صفر ہو گا:
:\ (MC)^t (Y-MC^{*}) = 0
(اقلیدسی فضا میں اندرونی حاصل ضرب کی عام تعریف استعمال کرتے ہوئے)،
یا
:\ C^t M^t (Y-MC^{*}) = 0
:\ C^t (M^t Y- M^t MC^{*}) = 0
:\ \langle M^t Y- M^t MC^{*}, C \rangle = 0
جس سے یہ نتیجہ اخذ کیا جا سکتا ہے کہ
:\ M^t Y- M^t MC^{*} = 0
یا
:\ M^t MC^{*} = M^t Y
اگر میٹرکس \ M^t M مقلوب ہو تو حل یہ ہو گا
:\ C^{*} =(M^t M)^{-1} M^t Y
مصفاہ صورت

رقمی عملیت اشارہ میں اقل مربعات تخمینہ کو مصفاہ صورت میں پیش کیا جاتا ہے۔
تصغیر|تصویر 1۔ مصفاہ H(z)=\sum_{k=0}^K h_kz^{-k}

تصویر 1 میں اشارہ متوالیہ x_n کسی صورت میں اشارہ متوالیہ d_n سے متعلق ہے۔ ہم اشارہ متوالیہ x_n کو مصفاہ H سے گزار کر اشارہ y_n حاصل کرتے ہیں۔ ہمار مقصد یہ ہے کہ متوالیہ y_n تخمینہ ہو متوالیہ d_n کا۔ یعنی مصفاہ H اس طرح چنا جائے کہ متوالیہ d_n اور متوالیہ y_n کے درمیان غلطی متوالیہ e_n=d_n-y_n کا اقل مربع کم سے کم ہو:
:\min_{H} \sum_n e^2_n
اگر متوالیہ تصادفی بھی ہوں تو پھر بھی ہم صرف مشاہداتی متوالیہ استعمال کر کے حل نکالنا چاہتے ہی (اور متوالیہ کی احصائی نوعیت سے مستفید نہیں ہونا چاہتے)۔
مصفاہ H ایک متناہی متوالیہ h_0, h_1, \cdots, h_{K-1} سے بنا ہے۔ مصفاہ کے اخراج y_n اور ادخال x_n کے درمیان تلفیف کا رشتہ ہے۔ اس مسئلہ میں اس رشتہ کو مصفوفہ ضرب کے ذریعہ لکھنا مفید ہے۔ اخراج y_n کے ایک لمبائی N کے ٹکرے کو N\times 1 سمتیہ \underline{y}_n کے طور پر لکھتے ہوئے، ملفیف کو بطور قالب ضرب یوں لکھا جا سکتا ہے:
:
\begin{bmatrix}
y_n \\
y_{n-1} \\
\vdots \\
y_{n-(N-1)}
\end{bmatrix} =
\begin{bmatrix}
x_n & x_{n-1} & \cdots & x_{n-(K-1)}\\
x_{n-1} & x_{n-2} & \cdots & x_{n-1-(K-1)}\\
\vdots \\
x_{n-(N-1)} & x_{n-(N-1)-1} & \cdots & x_{n-(N-1)-(K-1)}\\
\end{bmatrix}
\begin{bmatrix}
h_0 \\
h_1 \\
\vdots \\
h_{(K-1)}
\end{bmatrix}

یا

\underline{y}_n = X \underline{h}

جہاں میٹرکس X کی جسامت N \times K ہے۔ یہ ایک معلوم بات ہے کہ اقل مربع غلطی \sum_{i=n-(N-1)}^{n} e^2_i کی تصغیر اسی وقت ہوتی ہے جب غلطی e_n ڈیٹا x_n کے قائم الزاویہ ہو، یعنی
:X^t \underline{e}_n=0
اس معلومہ کو استعمال کرتے ہوئے
:X^t \underline{e}_n=X^t (\underline{d}_n - \underline{y}_n)
=X^t (\underline{d}_n - X\underline{h})
=X^t \underline{d}_n - X^tX\underline{h}
= 0

اگر میٹرکس X^tX جس کی جسامت K\times K ہے، مقلوب ہو، تو اس سے ہمیں مصفاہ حاصل ہوتا ہے
:\underline{h} = (X^tX)^{-1} X^t \underline{d}_n
مزید دیکھیے

* لکیری وینر مصفاہ


زمرہ:عملیت اشارہ
زمرہ:خطی الجبرا
زمرہ:ویکی ڈیٹا سے مختلف مختصر وضاحت
زمرہ:شماریات
زمرہ:عددی تحلیل
زمرہ:1805ء میں سائنس
زمرہ:فرانس میں 1805ء
زمرہ:کمپیوٹری ریاضی