حذف گاوس-جردن

2.1 مقدمه

2.1.1 تکامل حل دستگاه‌های معادلات خطی

دستگاه‌های معادلات خطی چهار هزار سال پیش توسط ریاضیدانان بابلی مورد بررسی قرار گرفتند.¹ آنها قادر به حل دستگاه‌های ساده دو مجهولی مانند $x+y=12$، $x-y=2$ بودند. ریاضیدانان چینی، در «نه فصل هنر ریاضی»، این را به دستگاه‌های سه معادله‌ای و همچنین به زمینه‌های نظریه اعداد مرتبط که به شکل قضیه باقی‌مانده چینی ظاهر می‌شود، گسترش دادند. مسئله حل دستگاه‌های معادلات همچنین در آنالیز، مانند بیشینه‌سازی توابع با قیود، ظاهر شد. روش دترمینان‌ها که توسط لایبنیتس پیشگام شد، با گابریل کرامر به فرمول‌های حل صریح دستگاه‌ها یا معادلات انجامید. رویکرد مدرن حل دستگاه‌های معادلات از یک فرایند حذف شفاف استفاده می‌کند. این فرایند بسیار سریع است و توسط کارل فریدریش گاوس رسمیت یافت. این روشی است که ما امروزه هنوز از آن استفاده می‌کنیم. همچنین امکان محاسبه مؤثر دترمینان‌ها را فراهم می‌کند.

2.1.2 حذف گاوسی

البته حذف مدت‌ها قبل از گاوس استفاده می‌شد. ما آن را در ابتدا به عنوان حذف معمولی یاد می‌گیریم. برای مثال، یک متغیر را حل کرده و در بقیه قرار دهید تا دستگاهی با مجهولات کمتر داشته باشید. کاری که گاوس انجام داد نوشتن یک فرایند حذف رسمی بود. این حدود سال ۱۸۰۹ بود. او حذف معمولی را "eliminationem vulgarem" نامید. این فرایند ناگهانی پدید نیامد. کار بر روی مسائل نسبتاً کاربردی باید به آن منجر شده باشد. برای مثال، گاوس در سال ۱۸۰۱ توانست در عرض چند هفته مسیر سیاره کوچک سرس را از $24$ اندازه‌گیری منتشر شده در تابستان ۱۸۰۱ پیش‌بینی کند. گزارش شده که گاوس برای تعیین $5$ پارامتر مدار به بیش از $100$ ساعت زمان نیاز داشت. تمرین‌هایی مانند این قطعاً گاوس را برای نوشتن رویه‌های رسمی‌تر بعدی که امکان حل مسائل خطی یا مسائل کلی‌تر برازش داده را فراهم می‌کرد، برانگیخت. نام "حذف گاوسی" اولین بار توسط جورج فورسایت استفاده شد، در حالی که آلن تورینگ آن را به روشی که امروزه آموزش می‌دهیم توصیف کرد. در اینجا به طور رسمی خواهیم دید که این فرایند به روشی یکتا تعیین می‌شود.²

2.2 سخنرانی

2.2.1 تبدیلات خطی و معادلات

اگر یک ماتریس $n\times m$ $A$ در یک بردار $x\in {ℝ}^m$ ضرب شود، یک بردار جدید $Ax$ در ${ℝ}^n$ به دست می‌آید. فرایند $x\to Ax$ یک نگاشت خطی از ${ℝ}^m$ به ${ℝ}^n$ تعریف می‌کند. با داشتن $b\in {ℝ}^n$، می‌توان خواستار یافتن $x$ای شد که در دستگاه معادلات خطی $Ax=b$ صدق کند. از نظر تاریخی، این دروازه به جبر خطی مدت‌ها قبل از آنکه ماتریس‌ها حتی شناخته شوند، پیموده شد: ریشه‌های بابلی و چینی وجود دارد که به هزاران سال پیش بازمی‌گردد. ³

2.2.2 ماتریس‌های افزوده و کاهش سطری

بهترین راه برای حل دستگاه، کاهش سطری ماتریس افزوده $$B=[A\mid b]$$ است. این یک ماتریس $n\times (m+1)$ است زیرا اکنون $m+1$ ستون وجود دارد. الگوریتم حذف گاوس-جردن از یک ماتریس $B$ یک ماتریس کاهش‌یافته سطری $\mathrm{rref}(B)$ تولید می‌کند. این الگوریتم امکان انجام سه کار را می‌دهد: کم کردن یک سطر از سطر دیگر، مقیاس‌دهی یک سطر و جابجایی دو سطر. اگر به دستگاه معادلات نگاه کنیم، همه این عملیات فضای جواب را حفظ می‌کنند. هدف ما تولید یک‌های پیشرو “$1$” است، که درایه‌های ماتریسی $1$ هستند که اولین درایه غیرصفر در یک سطر می‌باشند. هدف رسیدن به ماتریسی است که در فرم سطری کاهش‌یافته پلکانی باشد. این بدان معناست:

1. هر سطری که صفر نیست یک یکِ پیشرو دارد،
2. هر ستونی که یک $1$ پیشرو دارد هیچ درایه غیرصفر دیگری به جز آن یک پیشرو ندارد. شرط سوم این است که
3. هر سطر بالای یک سطر با یک پیشرو، یک پیشرو در سمت چپ دارد.

2.2.3 یکتایی فرم سطری کاهش‌یافته پلکانی

ما این فرایند را در کلاس و تکالیف تمرین خواهیم کرد. در اینجا یک قضیه است

2.2.4 لم افراز ماتریس در ساختار اثبات

یک لم جداگانه امکان شکستن یک اثبات را می‌دهد:

2.2.5

این درست نیست که اگر $A$ در فرم سطری کاهش‌یافته پلکانی باشد، آنگاه هر زیرماتریس در فرم سطری کاهش‌یافته پلکانی است. آیا می‌توانید مثالی بیابید؟

2.3 مثال‌ها

2.4 تصاویر

دستگاه معادلات

یک مسئله توموگرافی است. این مسائل در تصویربرداری تشدید مغناطیسی ظاهر می‌شوند. یک پیش‌درآمد، توموگرافی کامپیوتری با اشعه ایکس (CT) بود که آلن مک‌لئود کورمک برای آن در سال ۱۹۷۹ جایزه نوبل را دریافت کرد (کورمک در سال‌های ۱۹۵۶-۱۹۵۷ یک مرخصی مطالعاتی در هاروارد داشت، جایی که این ایده شکل گرفت). کورمک تا سال ۱۹۹۸ در وینچستر ماساچوست زندگی کرد. او در اصل یک فیزیکدان بود. کار او تأثیر شگرفی بر پزشکی داشت.

ما ماتریس افزوده $[A\mid b]$ را می‌سازیم و کاهش سطری می‌دهیم. ابتدا مجموع سه سطر اول را از سطر $4$ام کم کنید، سپس علامت ستون $4$ام را تغییر دهید:

اکنون می‌توانیم جواب‌ها را بخوانیم. می‌بینیم که $v$ و $w$ می‌توانند آزادانه انتخاب شوند. آنها متغیرهای آزاد هستند. می‌نویسیم $v=r$ و $w=s$. سپس فقط برای متغیرها حل کنید:

تمرین‌ها