حل معادله‌ی خطی در

درباره‌ی حل معادله‌ی خطی

یادتان هست اولین بار چه وقت جبر یاد گرفتید، همان دوران دبیرستان؟

معمولاً یک دستگاه معادلات به ما می‌دادند و از ما می‌خواستند که x و y را حل کنیم.

4x - 3y = -2
2x + 7y = 16

دو معادله، دو مجهول: کمی جای‌گذاری کنید و به‌زودی می‌بینید که x = 1, y = 2.

یک بار دیگر به سمت چپ مثال قبلی نگاه کنید. به نظر می‌رسد ماتریسی [4 -3; 2 7] در بردار مجهولی [x, y] ضرب می‌شود تا بردار [-2, 16] را به دست دهد.

در نمادگذاری جبر خطی: A x = b، با پیروی از قرارداد معمول حروف بزرگ برای ماتریس‌ها و حروف کوچک برای بردارها.

A x = 0 و فضای پوچ

یک حالت خاص مهم زمانی است که سمت راست همه‌ی معادلات ما صفر باشد.

4x - 3y = 0
2x + 7y = 0

در مثال بالا، تنها جواب وقتی است که x = y = 0 باشد، که معمولاً چندان جالب نیست.

جواب‌های غیربدیهی برای A x = 0 تنها وقتی وجود دارند که دترمینان A صفر باشد.

julia> using LinearAlgebra

julia> A = [4 -3; 2 7]
2×2 Matrix{Int64}:
 4  -3
 2   7

julia> det(A)  # not zero!
34.0

در عوض، این معادلات را در نظر بگیرید:

4x - 3y = 0
8x + 6y = 0

معادله‌ی دوم فقط دو برابر معادله‌ی اول است و اطلاعات تازه‌ای اضافه نمی‌کند. هر مقداری که در آن x = 0.75y باشد، یک جواب خواهد بود.

این مقادیر (x, y) روی خطی در فضای دوبعدی قرار می‌گیرند. تعداد جواب‌ها بی‌نهایت است و این جواب‌ها فضای پوچ ماتریس را تشکیل می‌دهند.

در این حالت، سطرهای ماتریس مستقل خطی نیستند و رتبه ماتریس کمتر از تعداد سطر یا ستون است.

julia> A = [4 -3; 8 -6]
2×2 Matrix{Int64}:
 4  -3
 8  -6

julia> det(A)
0.0

julia> size(A)  # total number of rows and columns
(2, 2)

julia> rank(A)  # number of linearly-independent rows (or columns)
1

julia> nullspace(A)
2×1 Matrix{Float64}:
 -0.6
 -0.8

julia> nullspace(A) |> norm  # Julia returns unit vectors when possible
1.0

تابع nullspace() یک نقطه را برمی‌گرداند که طوری انتخاب شده که به یک بردار یکه نرمال‌سازی شود، اما هر مضرب اسکالری از این بردار نیز در فضای پوچ قرار دارد.

حل A x = b

حالا فرض کنید ۱۰۰۰ معادله با ۱۰۰۰ مجهول دارید؟ اگر این مسخره به نظر می‌رسد، یادتان باشد که مبدل‌های دیجیتال بی‌سیم امروز ارزان و همه‌کاره‌اند (کرنش، سرعت باد، شتاب سه‌محوره و از این قبیل را اندازه می‌گیرند...). اینکه ۱۰۰۰ عدد از آن‌ها سازه‌ای مدرن مانند یک پل معلق را پایش کنند، کاملاً معقول است. باید یک سیستم کنترلی وجود داشته باشد که جریان داده را تفسیر کند و آماده باشد در صورت نگران‌کننده شدن اوضاع، هشدار بدهد.

باز هم A x = b، که در آن A را داریم (از طراحی مهندسی) و b را (مقادیر اندازه‌گیری‌شده از مبدل‌ها)، اما باید x را پیدا کنیم.

اولین فکری که به ذهن هر ناآشنایی می‌رسد این است که به شکلی «طرفین را بر A تقسیم کنیم» تا آن را به سمت راست ببریم.

در واقع A وارون دارد (بیشتر ماتریس‌های مربعی وارون دارند، اما نه همه: دترمینان باید ناصفر باشد)، و محاسبه جواب می‌دهد (هرچند کند!).

julia> A = [4 -3; 2 7]
2×2 Matrix{Int64}:
 4  -3
 2   7

julia> b = [-2, 16]
2-element Vector{Int64}:
 -2
 16

# the inverse matrix
julia> inv(A)
2×2 Matrix{Float64}:
  0.205882   0.0882353
 -0.0588235  0.117647

julia> inv(A) * b
2-element Vector{Float64}:
 0.9999999999999999
 2.0

متأسفانه محاسبه‌ی وارون برای ماتریس‌های کوچک کند است و برای ماتریس‌های بزرگ به‌شدت کندتر. اگر پل شما در طول محاسبه فرو بریزد، ایده‌آل نیست!

خوشبختانه الگوریتم‌های دیگری به‌مراتب سریع‌ترند (در این مورد حذف گاوسی).

Julia (با تقلید از Matlab) برای حل‌کننده فقط از یک بک‌اسلش استفاده می‌کند (از نظر فنی، «تقسیم چپ»).

julia> x = A \ b
2-element Vector{Float64}:
 1.0
 2.0

این یک مثال ساده است، اما چند نکته هست که باید مراقبشان باشید.

• ضرایب باید در ستون‌ها هم‌تراز شوند، پس برای جمله‌های جاافتاده به‌اندازه‌ی لازم صفر بگذارید.
• معادلات (و در نتیجه سطرهای ماتریس) باید مستقل خطی باشند. اگر سطر ۳ فقط مجموع سطرهای ۱ و ۲ باشد، اطلاعات تازه‌ای اضافه نمی‌کند و مسئله کم‌تعیین می‌شود.

دستور rank() تعداد سطرها/ستون‌های مستقل خطی را می‌دهد، پس هدف این باشد که این عدد با تعداد متغیرهای مجهول برابر شود.

julia> rank(A)
2

ماتریس‌های مستطیلی

جایی پیش از نوجوانی، احتمالاً به شما یاد داده بودند که برای حل N مجهول به دستگاهی با N معادله نیاز دارید.

مثل بیشتر موارد در ریاضیات، واقعیت کمی ظریف‌تر است (و تنها به جزئیات استقلال خطی که در بخش قبل گفتیم محدود نمی‌شود).

سطرهای «خیلی کم»

با N-1 معادله (سطرهای ماتریس A)، مسئله کم‌تعیین است. آیا از ناامیدی تسلیم می‌شویم؟

بستگی دارد!

این N-1 معادله هنوز اطلاعات زیادی در خود دارند. از نظر هندسی، برای تعیین جواب به‌عنوان یک نقطه در فضای Nبعدی به N نیاز داریم، اما N-1 به ما می‌گوید که جواب باید جایی روی یک خط قرار داشته باشد.

این ما را با بی‌نهایت جواب رها می‌کند، اما همچنین با فضای پارامتری بی‌نهایتی که هیچ جوابی ندارد.

آیا خط جواب‌های شما از ناحیه‌ای از فضای پارامتر می‌گذرد که یک مهندس آبرومند باید نگرانش باشد؟ یا ناحیه‌ای که می‌تواند توجیه کند سازه را برای دسترسی عمومی ببندیم (پل‌های معلق در بادهای شدید عرضی می‌توانند سرزنده شوند)؟ شاید ارزش داشته باشد برای تعیین همین، محاسبات بیشتری انجام دهید!

julia> A3 = [4 -3 1; 2 2 2; 3 -4 -3]
3×3 Matrix{Int64}:
 4  -3   1
 2   2   2
 3  -4  -3

julia> b3 = [1, 12, -14]
3-element Vector{Int64}:
   1
  12
 -14

# fully-determined solution
julia> A3 \ b3
3-element Vector{Float64}:
 1.0
 2.0
 3.0

# remove row 3 from A3 and B3
julia> A2 = A3[1:2, :]
2×3 Matrix{Int64}:
 4  -3  1
 2   2  2

julia> b2 = b3[1:2]
2-element Vector{Int64}:
  1
 12

# an under-determined solution
julia> z1 = A2 \ b2
3-element Vector{Float64}:
 1.594594594594594
 2.445945945945947
 1.9594594594594592

حل‌کننده‌ی بک‌اسلش یک جواب به ما می‌دهد! غیررسمی، ظاهراً این جوابی است که کوچک‌ترین نُرم را دارد (از نظر هندسی، نزدیک‌ترین به مبدأ).

برای به دست آوردن جواب‌های دیگر، به nullspace ماتریس A2 نیاز داریم.

افزودن هر مضرب اسکالری از فضای پوچ به جواب اصلی، جواب معتبر دیگری به دست می‌دهد.

# get the nummspace of A2
julia> N = nullspace(A2)
3×1 Matrix{Float64}:
 -0.46499055497527725
 -0.3487429162314578
  0.813733471206735

# add a random multiple of the nullspace to the earlier solution
julia> z = z1 + rand() * N
3×1 Matrix{Float64}:
 1.274331860650258
 2.205748895487695
 2.5199192438620472

# our random z is a valid solution, recovering b2 = [1, 12]
julia> A2 * z
2×1 Matrix{Float64}:
  0.9999999999999947
 12.0

به همین ترتیب، N-2 معادله جواب‌های (بی‌نهایت) را به یک صفحه محدود می‌کند و همان اصول برقرارند.

سطرهای «خیلی زیاد»

وضعیت معکوس وقتی پیش می‌آید که تعداد معادلات از مجهول‌ها بیشتر باشد، با این حال به شکلی هنوز مستقل خطی باشند.

در مهندسی دنیای واقعی، این کاملاً عادی است و یک نکته‌ی مثبت به شمار می‌رود!

مبدل‌ها دقت محدودی دارند، بردار b دقت محدودی دارد و در محاسبه نویز وجود دارد. حالا جواب یک برازش کمترین مربعات بر داده‌های نویزی است.

ساده‌ترین روش از pseudoinverse ماتریس استفاده می‌کند که Julia آن را به‌صورت تابع pinv() پیاده‌سازی کرده است.

می‌توان از آن تقریباً مثل وارون یک ماتریس مربعی (نامنفرد) استفاده کرد، و به‌جای یک جواب دقیق، برآوردی به روش کمترین مربعات از متغیرها می‌دهد.

# create 5-row A and b for 2 variables
julia> A5 = [4 -3; 2 7; -1 2; 1 -1; 3 1]
5×2 Matrix{Int64}:
  4  -3
  2   7
 -1   2
  1  -1
  3   1

julia> rank(A5)
2

# add some random-normal noise to b5
julia> b5n = [-2, 16, 3, -1, 5] + randn(5) * 0.1
5-element Vector{Float64}:
 -1.9337349223581917
 16.024913008059457
  3.0087646177373992
 -0.8675748721176717
  4.914568047308805

# solve to get x ≈ 1, y ≈ 2, using the pseudoinverse
julia> pinv(A5) * b5n
2-element Vector{Float64}:
 1.006117942769543
 1.9962973764508272

مقدارهای ویژه و بردارهای ویژه

بخش قبلی جواب‌های A x = b را توصیف کرد، معادل همان جبر آشنای همیشگی.

این بخش درباره‌ی جواب‌های A x = λ x است، که در آن λ یک اسکالر است.

این مفهومی به‌طور مشخص متعلق به جبر خطی است، اما می‌توانیم آن را به‌صورت هندسی تفسیر کنیم:

برای مقادیر مناسب x و λ، ماتریس مربعی A بردار ناصفر x را از نظر طول با ضریب λ مقیاس می‌دهد، بدون اینکه جهت آن را تغییر دهد (جز اینکه λ منفی جهت را برعکس می‌کند).

این ممکن است خیلی تخصصی به نظر برسد، اما معلوم می‌شود که به‌طرز مسخره‌ای مفید است!

اصطلاح‌شناسی: مقادیر معتبر λ، _مقدارهای ویژه_ی A هستند و مقادیر متناظر x، _بردارهای ویژه_ی A. متأسفانه باید با واژه‌هایی کنار بیاییم که وسط راه زبان‌شان عوض می‌شود.

معمولاً به دانشجویان یاد می‌دهند که مقدارها/بردارهای ویژه را برای ماتریس‌های ۲×۲ به‌صورت دستی محاسبه کنند، اما استفاده از کامپیوتر بسیار ساده‌تر است (هرچند هنوز نسبتاً کند، و در حالت کلی برای یک ماتریس n×n با مرتبه‌ی O(n^3) رشد می‌کند).

julia> A = rand(-9:9, 2, 2)
2×2 Matrix{Int64}:
 9  5
 3  2

julia> F = eigen(A)
Eigen{Float64, Float64, Matrix{Float64}, Vector{Float64}}
values:
2-element Vector{Float64}:
  0.27984674554472466
 10.720153254455274
vectors:
2×2 Matrix{Float64}:
 -0.497417  0.945605
  0.867511  0.325317

# eigenvalues
julia> F.values
2-element Vector{Float64}:
  0.27984674554472466
 10.720153254455274

# each column is an eigenvector, normalized to a unit vector
julia> F.vectors
2×2 Matrix{Float64}:
 -0.497417  0.945605
  0.867511  0.325317

به‌طور کلی، یک ماتریس n×n تعداد n مقدار ویژه دارد، هرچند نه همیشه مقادیری متمایز. آن‌ها را ریشه‌های یک چندجمله‌ای از مرتبه‌ی n در نظر بگیرید (که چندجمله‌ای مشخصه نامیده می‌شود)، ریشه‌هایی که می‌توانند تکراری باشند و اغلب حتی برای یک ماتریس حقیقی، مختلط‌اند.

هر بردار ویژه نماینده‌ی یک جهت است و هر مضرب اسکالری از آن نیز بردار ویژه‌ی معتبری است. برای راحتی در محاسبات بعدی، Julia بردارهای یکه‌ای با نُرم برابر ۱ برمی‌گرداند.

کاربردها

توضیح اینکه چرا بردارهای ویژه مهم‌اند، در حالت آرمانی کاری برای یک کتاب درسی ۵۰۰ صفحه‌ای است، نه چند پاراگراف کوتاه. این موضوع در بخش‌های بسیار زیادی از ریاضیات کاربردی مدرن رخنه کرده است.

در سطح کلان، بردارهای ویژه نماینده‌ی «مهم‌ترین» محورها (جهت‌ها) در یک مجموعه‌داده هستند. مقدارهای ویژه «اهمیت نسبی» هر محور را نشان می‌دهند (البته با فرض برخی پیش‌فرض‌ها درباره‌ی نرمال‌سازی ورودی‌ها).

اینکه این واقعاً چه معنایی دارد، به کاربرد بستگی دارد.

تحلیل مؤلفه‌های اصلی

در یک مسئله‌ی معمول علم داده، ممکن است ۱۰۰ یا بیشتر «ویژگی» داشته باشیم که به‌صورت ستون‌های داده ذخیره شده‌اند. تقریباً به‌طور اجتناب‌ناپذیر، نویز، افزونگی و همبستگی‌های ناخواسته وجود خواهد داشت.

باید کاهش بُعد انجام دهیم و PCA یکی از راه‌های نظم بخشیدن به این آشفتگی است:

• ماتریس کوواریانس داده‌ها را محاسبه کنید.
• حالا یک ماتریس مربعی داریم، پس در قدم بعد مقدارها و بردارهای ویژه را محاسبه کنید.
• بردارهای ویژه را به ترتیب نزولی مقدارهای ویژه‌شان مرتب کنید (به‌دقت‌تر، قدر مطلق |λ|).
• k بردار ویژه‌ی نخست حالا principal components شما هستند، که در آن k به‌طور چشمگیری کوچک‌تر از تعداد اولیه‌ی ویژگی‌هاست.
• کل مجموعه‌داده را روی این k محور تصویر کنید و به دنبال الگوهای جالب بگردید.

PCA در این شکل توسط گروه‌هایی به‌همان اندازه متنوع به کار رفته است، از دانشمندان علوم پزشکی که می‌کوشند خواص مولکولی را در طراحی دارو بهبود دهند تا فعالان سیاسی که می‌کوشند ترجیحات رأی‌دهندگان را از داده‌های نظرسنجی بفهمند. احتمالاً گروه‌های بازاریابی هم که می‌خواهند کالایی به شما بفروشند از آن استفاده کرده‌اند، اما هر فناوری می‌تواند برای خوب یا بد به کار برود.

PCA بخشی از یک نصب حداقلی Julia نیست، اما (بیرون از Exercism) بسته‌ی MultivariateStats آنچه لازم دارید را در خود دارد.

پردازش تصویر

اگر ایده‌ی PCA را یک قدم جلوتر ببریم، تصاویر دیجیتال فقط ماتریس‌هایی از مقادیر پیکسل هستند و می‌توانیم مؤلفه‌های اصلی را برای آن‌ها محاسبه کنیم.

این کار ده‌ها سال است که در فشرده‌سازی تصویر استفاده می‌شود، جایی که PCA راهنمایی است برای اینکه هنگام کاهش حجم فایل، چه مواردی را بیشتر از همه باید حفظ کرد.

روزبه‌روز، PCA بخشی حیاتی از طبقه‌بندهای تصویر مانند تشخیص چهره است. دفعه‌ی بعد که از فرودگاه عبور می‌کنید، برادر بزرگ فقط تماشا نمی‌کند، بلکه از جبر خطی هم برای فهمیدن آنچه می‌بیند استفاده می‌کند!

مهندسی مکانیک

با جنجال کمتر، محورهای اصلی یک قطعه‌ی مکانیکی، بردارهای ویژه‌ی تانسور ممان اینرسی I آن هستند (یک ماتریس با اسمی کمی متفاوت).

هر چرخ ماشین شما احتمالاً یک یا چند وزنه‌ی تعادل دارد که طوری تنظیم شده‌اند تا عناصر غیرقطری این تانسور I را صفر کنند. مکانیک تعمیرگاه بی‌شک از انجام این محاسبات پرهیز می‌کند (برخلاف طراحان هواپیما و مهندسان موشک)، اما «لرزش» فقط واژه‌ای روزمره برای توصیف جمله‌های متقاطع در تانسور است، که در این مورد سفر شما را کمتر راحت می‌کند و سایش مکانیکی یاتاقان‌ها را افزایش می‌دهد.