حل برای X: ترک کد معادلات خطی در علوم داده

ما می خواهیم به این موارد نگاه کنیم ، و سپس ببینیم که چگونه یک ایده جالب به نام شبه نارس می تواند همه آنها را با هم جمع کند.

یک تازه کننده سریع در رتبه بندی

یادآوری کردن درجه از آخرین گپ ما؟ در اینجا بسیار مهم خواهد بود. رتبه یک ماتریس تعداد ردیف ها یا ستون های خطی مستقل آن است. به یاد داشته باشید ، Row Rank همیشه برابر است با رتبه ستون – شما نمی توانید تعداد متفاوتی از ردیف های مستقل در مقابل ستون ها داشته باشید!

برای یک ماتریس $ m \ times n $ ، حداکثر رتبه ممکن که می تواند داشته باشد ، کوچکتر از $ M $ و $ N $ است. اگر $ m

مورد 1: هنگامی که معادلات متغیرهای برابر ($ m = n $)

این موردی است که ماتریس شما $ A $ مربع است ($ m \ times n $ و $ m = n $).

• اگر $ $ رده کامل باشد:
  “رتبه کامل” در اینجا به این معنی است که رتبه ماتریس برابر با $ M $ (یا $ n $ است ، زیرا آنها یکسان هستند). این به چه معنی است؟ این بدان معناست که تمام معادلات شما در سمت چپ مستقل هستند. شما نمی توانید با ترکیب دیگران ، هیچ معادله ای ایجاد کنید.
  در این مورد شاد ، وجود دارد راه حل منحصر به فرد به $ ax = b $. شاید از جبر به یاد داشته باشید که می توانید با یافتن معکوس $ A $ ، که به عنوان $ A^{-1} $ نوشته شده است ، این مسئله را حل کنید. راه حل به سادگی است:
  $ $ x = a^{-1} b $ $
  اگر تعیین کننده $ A $ صفر نباشد ، می توانید $ A^{-1} $ پیدا کنید. این سناریوی استاندارد و ساده است.

• اگر $ $ رده کامل نباشد:
  این بدان معنی است که رتبه $ A $ کمتر از $ M $ است. در این شرایط ، برخی از معادلات شما در سمت چپ در واقع ترکیب های خطی دیگران هستند-آنها به صورت خطی وابسته هستند.
  وقتی این اتفاق بیفتد ، بسته به اینکه مقادیر در سمت راست (در وکتور B $ $) قرار دارند ، دو امکان دریافت می کنید:

  1. سیستم سازگار: اگر وابستگی های سمت چپ مطابقت داشته باشد دقیقاً با وابستگی به سمت راست (مقادیر بردار $ B $) ، معادلات سازگار هستند. اما از آنجا که آنها وابسته هستند ، شما به اندازه کافی ندارید مستقل معادلات برای پین کردن یک راه حل واحد. این منجر به راه حل های نامتناهیبشر
  2. سیستم متناقض: اگر وابستگی های سمت چپ نه با مقادیر بردار $ B $ مطابقت دارد ، معادلات متناقض هستند. آنها با یکدیگر متناقض هستند ، و وجود دارد بدون راه حل این می تواند همه آنها را برآورده کند.

بیایید چند نمونه را برای این مورد $ m = n $ بررسی کنیم:

مثال 1: رتبه کامل (راه حل منحصر به فرد)

سیستم معادلات را در نظر بگیرید:
$ x_1 + 3x_2 = 7 $
$ 2x_1 + 4x_2 = 10 $

در فرم ماتریس $ ax = b $ ، این:
$ $
\ شروع {bmatrix}
1 و 3 \
2 و 4
\ پایان {bmatrix}
\ شروع {bmatrix}
x_1 \
x_2

\ شروع {bmatrix}
7 \
10
\ پایان {bmatrix}
$ $
در اینجا ، $ a = \ start {bmatrix} 1 & 3 \ 2 & 4 \ end {bmatrix} $. $ m = 2 $ ، $ n = 2 $.
ما می توانیم بررسی کنیم که آیا $ a $ با محاسبه تعیین کننده آن رتبه کامل دارد: $ (1 \ بار 4) – (3 \ بار 2) = 4 – 6 = -2 $. از آنجا که تعیین کننده 0 نیست ، ماتریس رتبه کامل دارد (رتبه = 2).
یک راه حل منحصر به فرد ، $ x = a^{-1} b $ وجود دارد. معکوس $ a $ $ \ start {bmatrix} -2 & 1.5 \ 1 & -0.5 \ end {bmatrix} $.
بنابراین ، $ x = \ start {bmatrix} -2 & 1.5 \ 1 & -0.5 \ end {bmatrix} \ start {bmatrix} 7 \ ​​10 \ end {bmatrix} = \ \ barmatrix} (-2 \ time 7) + (1.5 \ time 10) \ times 10) \ end {bmatrix} = \ start {bmatrix} -14 + 15 \ 7 – 5 \ end {bmatrix} = \ start {bmatrix} 1 \ 2 \ end {bmatrix} $.
راه حل منحصر به فرد $ x_1 = 1 $ و $ x_2 = 2 $ است. می توانید این موارد را به معادلات اصلی وصل کنید تا بررسی کنید (1 + 3 (2) = 7 $ ، 2 $ (1) + 4 (2) = 10 $). کار می کند!

می توانید این کار را به راحتی در نرم افزار نیز حل کنید. در R ، شما می توانید A و B را تعریف کنید و از آن استفاده کنید solve() فرمان

مثال 2: رتبه کامل ، سازگار نیست (راه حل های نامحدود)

سیستم را در نظر بگیرید:
$ x_1 + 2x_2 = 5 $
$ 2x_1 + 4x_2 = 10 $

در فرم ماتریس $ ax = b $:
$ $
\ شروع {bmatrix}
1 و 2 \
2 و 4
\ پایان {bmatrix}
\ شروع {bmatrix}
x_1 \
x_2

\ شروع {bmatrix}
5 \
10
\ پایان {bmatrix}
$ $
در اینجا ، $ a = \ start {bmatrix} 1 & 2 \ 2 & 4 \ end {bmatrix} $. $ m = 2 $ ، $ n = 2 $.
تعیین کننده را بررسی کنید: $ (1 \ بار 4) – (2 \ بار 2) = 4 – 4 = 0 $. تعیین کننده 0 است ، بنابراین ماتریس رتبه کامل ندارد (رتبه = 1). ستون ها وابسته هستند (ستون 2 2 * ستون 1 است) و ردیف ها وابسته هستند (ردیف 2 2 * ردیف 1).

اکنون ، خود معادلات را نگاه کنید. معادله دوم 2x_1 + 4x_2 = 10 $ دقیقاً 2 برابر معادله اول $ x_1 + 2x_2 = 5 $ است. این وابستگی به سمت چپ (2x_1 $ + 4x_2 $ 2 \ $ (x_1 + 2x_2) $) است همسان در سمت راست (10 دلار $ 2 \ برابر 5 $).
از آنجا که طرف های چپ و راست همان وابستگی خطی دارند ، سیستم است ثابتبشر
با این حال ، از آنجا یکی معادله مستقل ($ x_1 + 2x_2 = 5 $) با دو متغیر ($ x_1 ، x_2 $). این بدان معنی است که شما یک متغیر “رایگان” دارید.
می توانید انتخاب کنید هیچ ارزش $ x_2 $ ، و سپس $ x_1 $ را که کار می کند محاسبه کنید ($ x_1 = 5 – 2x_2 $).
به عنوان مثال:

• اگر $ x_2 = 0 $ ، $ x_1 = 5 $. راه حل: $ (5 ، 0) $.
• اگر $ x_2 = 1 $ ، $ x_1 = 3 $. راه حل: $ (3 ، 1) $.
• اگر $ x_2 = 2.5 $ ، $ x_1 = 0 $. راه حل: $ (0 ، 2.5) $. از آنجا که می توانید انتخاب کنید هیچ ارزش $ x_2 $ ، وجود دارد راه حل های نامتناهی به این سیستم

مثال 3: رتبه کامل ، متناقض نیست (بدون راه حل)

سیستم را در نظر بگیرید:
$ x_1 + 2x_2 = 5 $
$ 2x_1 + 4x_2 = 9 $

در فرم ماتریس $ ax = b $:
$ $
\ شروع {bmatrix}
1 و 2 \
2 و 4
\ پایان {bmatrix}
\ شروع {bmatrix}
x_1 \
x_2

\ شروع {bmatrix}
5 \
9
\ پایان {bmatrix}
$ $
در اینجا ، $ a = \ start {bmatrix} 1 & 2 \ 2 & 4 \ end {bmatrix} $ مانند گذشته است ، بنابراین رتبه کامل نیست (رتبه = 1). سمت چپ وابستگی یکسانی دارد (ردیف 2 2 * ردیف 1).
اما به سمت راست (وکتور $ B $) نگاه کنید. سمت راست معادله اول 5 است. اگر آن را با 2 ضرب کنید (ضریب مقیاس بین سمت چپ) ، 2 \ بار 5 = 10 $ دریافت می کنید.
با این حال ، سمت راست معادله دوم 9 است ، نه 10.
وابستگی به سمت چپ (جایی که سمت چپ معادله دوم دو برابر است) نه سمت راست را مطابقت دهید (9 $ \ neq 2 \ برابر 5 $). معادلات با یکدیگر متناقض هستند (2x_1 $ + 4x_2 $ نمی تواند برابر باشد هر دو 10 وت 9 به طور همزمان بر اساس معادله اول).
سیستم است متناقض، و وجود دارد بدون راه حل این می تواند هر دو معادله را برآورده کند.

بنابراین ، برای مورد $ m = n $ (ماتریس مربع A): اگر A کامل باشد ، راه حل منحصر به فرد ؛ اگر A رتبه کامل نداشته باشد ، قوام را بررسی کنید – اگر سازگار باشد ، راه حل های نامحدود. اگر متناقض باشد ، هیچ راه حلی وجود ندارد.

مورد 2: معادلات بیشتر از متغیرها ($ m> n $)

حال بیایید به موردی که معادلات بیشتری نسبت به متغیرها دارید ، نگاه کنیم. مانند تلاش برای یافتن دو شماره ($ x_1 ، x_2 $) که پنج شرط مختلف را برآورده می کند.

$ $ AX = B \ Quad (\ Text {که در آن m> n}) $ $

از آنجا که معادلات بیشتری نسبت به متغیرها دارید ، به طور کلی یافتن یک راه حل عالی $ x $ غیرممکن است تک تک معادله درست است (یعنی ، $ ax $ دقیقاً برابر با $ B $). اگر می توانستید چنین $ x $ کامل پیدا کنید ، $ ax – b $ یک بردار از همه صفرها خواهد بود.

اما از آنجا که یک راه حل عالی معمولاً دور از دسترس نیست ، بهترین چیز بعدی چیست؟ ما می خواهیم یک راه حل $ x $ پیدا کنیم که ما را به عنوان نزدیک در صورت امکان برای رضایت همه معادلات. به عبارت دیگر ، ما می خواهیم یک $ $ $ پیدا کنیم که تفاوت بین $ AX $ و $ B $ را تا حد ممکن کوچک کند.

به $ ax – b $ به عنوان یک بردار “خطاها” فکر کنید ، جایی که هر عنصر خطا در یک معادله است.
معادله 1 خطا: $ e_1 = (a_ {11} x_1 + a_ {12} x_2 + … + a_ {1n} x_n) – b_1 $
معادله 2 خطا: $ e_2 = (a_ {21} x_1 + a_ {22} x_2 + … + a_ {2n} x_n) – b_2 $
…
معادله m خطا: $ e_m = (a_ {m1} x_1 + a_ {m2} x_2 + … + a_ {mn} x_n) – b_m $

بردار خطاها $ E = AX – B $ است. ما می خواهیم $ x $ را پیدا کنیم که این وکتور خطا $ e $ را تا حد امکان “کوچک” می کند. چگونه اندازه یک بردار خطاها را اندازه گیری می کنیم؟ ما فقط خطاها را اضافه نمی کنیم ($ E_1 + E_2 + … $) ، زیرا خطاهای مثبت و منفی می توانند از بین بروند ، و باعث می شود یک خطای کلی بزرگ مانند صفر به نظر برسد.

یک روش متداول برای اندازه گیری خطای کلی ، به حداقل رساندن مجموع است مربع خطاها: $ E_1^2 + E_2^2 + … + E_M^2 $. این امر به این دلیل است که مربع سازی همه خطاها را مثبت می کند و خطاهای بزرگتر به طور قابل توجهی بیشتر کمک می کنند. این رویکرد پیدا کردن حداقل راه حل مربعبشر

به حداقل رساندن مجموع خطاهای مربع ($ E_1^2 + … + E_M^2 $) همان اندازه به حداقل رساندن طول مربع (یا هنجار مربع) بردار خطا $ e = AX – B $ است. ما طول مربع یک بردار $ v $ را به عنوان $ || v ||^2 $ می نویسیم ، که $ v^t v $ است (بردار منتقل شده توسط بردار اصلی).
بنابراین ، ما می خواهیم $ || AX – B ||^2 $ را به حداقل برسانیم ، که $ (AX – B)^T (AX – B) $ است.

$ $ \ text {minimize} (ax – b)^t (ax – b) $ $

برای یافتن $ x $ که این امر را به حداقل می رساند ، می توانید از حساب استفاده کنید. شما مشتق این عبارت را با توجه به بردار $ x $ می گیرید و آن را برابر با صفر می کنید. پس از انجام حساب و برخی از جبر ماتریس (که ما در اینجا به جزئیات نمی پردازیم ، دقیقاً مانند سخنرانی) ، معادله ای که برای حل آن برای X $ $ حل می کنید:

$ $ a^مالیات = a^tb $ $

جایی که $ a^t $ انتقال ماتریس $ a $ است (شما ردیف ها و ستون های آن را می چرخانید).

حال ، اگر ماتریس $ a^ta $ غیرقابل برگشت باشد (اگر ستون های ماتریس اصلی $ a $ به صورت خطی مستقل باشند – مربوط به رتبه!) ، می توانید با قیمت x $ حل کنید:

$ $ x = (a^ta)^{-1} a^tb $ $

این راه حل $ x $ است حداقل راه حل مربعبشر این X $ $ است که مجموع اختلافات مربع بین $ $ $ و $ B $ را به حداقل می رساند. این $ $ $ ممکن است $ Ax $ ایجاد نکند دقیقاً برابر با $ B $ (از آنجا که ممکن است یک راه حل کامل وجود نداشته باشد) ، اما بهترین حالت ممکن را به معنای حداقل مربعات به شما می دهد.

این دیدگاه بهینه سازی راهی برای یافتن یک “راه حل” معنی دار حتی اگر معادلات بیشتری نسبت به متغیرها داشته باشیم ، یک وضعیت مشترک در اتصالات داده ها است.

چه چیزی بعدی؟

تا کنون ، ما موردی را پوشش داده ایم که $ m = n $ (همان تعداد معادلات و متغیرها) و موردی که $ m> n $ (معادلات بیشتر از متغیرها) است و ایده کمترین راه حل مربع را برای دومی معرفی می کند.

در قسمت بعدی ، ما به مورد سوم خواهیم پرداخت که $ m

سرانجام ، خواهیم دید که چگونه این ایده حداقل مربعات و مفهوم دیگری به نام شبه در واقع می تواند یک روش واحد و زیبا برای فکر کردن در مورد حل $ AX = B $ که هر سه مورد را پوشش می دهد ، ارائه دهد!

با ما همراه باشید!