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

اصطلاح	term
اقل مربعات تقرب	Least squares Approximation

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

$\ (x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{n},y_{n})$

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

1. $\ y=ax+b$     (گراف لکیری خط)
2. $\ y=ax^{2}+bx+c$     (درجہ دوم کثیر رقمی)
3. $\ y=ax^{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 MC$

$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$

مصفاہ صورت

رقمی عملیت اشارہ میں اقل مربعات تخمینہ کو مصفاہ صورت میں پیش کیا جاتا ہے۔

فائل:Linear wiener filter setup.png

تصویر 1۔ مصفاہ $H(z)=\sum _{k=0}^{K}h_{k}z^{-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_{n}^{2}$

اگر متوالیہ تصادفی بھی ہوں تو پھر بھی ہم صرف مشاہداتی متوالیہ استعمال کر کے حل نکالنا چاہتے ہی (اور متوالیہ کی احصائی نوعیت سے مستفید نہیں ہونا چاہتے)۔ مصفاہ 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_{i}^{2}$ کی تصغیر اسی وقت ہوتی ہے جب غلطی $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^{t}X{\underline {h}}=0$

اگر میٹرکس $X^{t}X$ جس کی جسامت $K\times K$ ہے، مقلوب ہو، تو اس سے ہمیں مصفاہ حاصل ہوتا ہے

${\underline {h}}=(X^{t}X)^{-1}X^{t}{\underline {d}}_{n}$

مزید دیکھیے

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

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