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

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح term
اقل مربعات
تقرب
Least squares
Approximation

تجربات سے اکثر ایسا ڈیٹا اکٹھا ہوتا ہے جسے کسی کثیر رقمی سے تقرب کرنا مفید رہتا ہے۔ فرض کرو کہ کسی تجربے کے نتیجے میں ہمیں n پیمائش جوڑے ملتی ہیں:

\ (x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)

ان کے مخطط کو دیکھتے ہوئے ہم یہ فیصلہ کرتے ہیں کہ یہ دالہ \ y=f(x)، ذیل میں سے کسی کثیر رقمی

  1. \ y=a x + b      (مخطط لکیری خط)
  2. \ y=a x^2 + bx + c      (درجہ دوم کثیر رقمی)
  3. \ y=a x^3 + bx^2 + cx + d      (سہ کثیر رقمی)
  4. \ \cdots  \cdots  \cdots \cdots  \cdots
  5. \ y=c_m x^m + c_{m-1}x^{m-1} + c_1 x + c_0      (m کثیر رقمی)

سے تقرب کی جا سکتی ہے۔

Ls poly 2 fit.png

تصویر میں گیارہ نکتوں (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

اور دیکھو[ترمیم]


E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات