درباره‌ی مبانی جبر خطی
«جبر خطی» چیست؟
تعاریف فنی زیادی وجود دارد، در ویکی‌پدیا، در کتاب‌های درسی و در وب‌سایت‌های عالی مانند 3Blue1Brown، اما برای اهداف ما می‌توانیم غیررسمی‌تر باشیم.
جبر خطی درباره‌ی کارهای جالب (و بسیار مفید) زیادی است که می‌توانید با بردارها و ماتریس‌ها انجام دهید.
نگهدارندگان Julia (و Python) عاشق این جور چیزها هستند.
مدیریت Exercism، نه چندان.
این مفهوم به جنبه‌های ساده‌تر یک موضوع عظیم محدود خواهد شد، اما هشدار: این ناگزیر مفهومی کاملاً ریاضی است.
بردار چیست؟
بستگی دارد از چه کسی بپرسید، و اینکه چگونه می‌خواهید موضوعی نسبتاً انتزاعی را تجسم کنید.
- در Julia،
Vector{T} فقط یک نام دیگر برای Array{T, 1} است، و eltype T می‌تواند هر نوعی باشد.
- در (بیشتر) فیزیک، بردار پیکانی است با
length و direction در فضای N-بعدی، اما بدون موقعیت ثابت.
- در جبر خطی، پیکان فیزیکدان‌ها در فضا ثابت است، با دُم آن در مبدأ. این باعث می‌شود بدنه‌ی پیکان زائد باشد، بنابراین می‌توانیم بردار را به صورت یک
point در فضای N-بعدی نمایش دهیم، که N عنصر آن فاصله از مبدأ را در امتداد هر یک از N محور نشان می‌دهند.
برای اهداف کنونی، بردارهای رشته‌ها یا کاراکترها را نادیده بگیرید.
ما در این مفهوم با انواع عددی کار خواهیم کرد: Int، Float، یا Complex.
ماتریس چیست؟
باز هم، پاسخ‌های متنوعی خواهید یافت.
- آرایه‌ای مستطیلی دوبعدی از اعداد (بدون لبه‌های ناهموار). ماتریس مربعی یک حالت خاص رایج است.
- یک
linear combination از بردارهای ستونی، که کنار هم چیده شده‌اند.
- یک
transformation که می‌تواند به یک بردار اعمال شود، همان‌طور که یک function به سایر انواع ورودی اعمال می‌شود.
برخی از انواع ماتریس مربعی آنقدر رایج هستند که نام‌های خاص دارند.
ماتریس قطری: همه‌ی درایه‌های غیرصفر روی main diagonal (از بالا-چپ به پایین-راست) قرار دارند.
julia> [1 0 0; 0 2 0; 0 0 3]
3×3 Matrix{Int64}:
1 0 0
0 2 0
0 0 3
# a convenient shortcut
julia> diagm(1:3)
3×3 Matrix{Int64}:
1 0 0
0 2 0
0 0 3
ماتریس همانی: یک ماتریس قطری که فقط یک‌ها روی قطر دارد (به دلایلی که بعداً واضح‌تر خواهند شد).
اغلب به صورت I خلاصه می‌شود.
julia> Matrix{Float64}(I, 3, 3)
3×3 Matrix{Float64}:
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
مثلثی بالا: مقادیر غیرصفر روی قطر و بالای آن، صفرها در پایین.
مثلثی پایین را خودتان می‌توانید حدس بزنید.
ترانهاده‌ی یک ماتریس
اگر واقعاً می‌خواهید سطرها را با ستون‌ها جابه‌جا کنید، تابع permutedims() این کار را انجام می‌دهد و یک ماتریس جدید به شما می‌دهد.
این کار شامل کپی کردن است، که هنگام کار با ماتریس‌های بزرگ کند و پرمصرف از نظر حافظه است.
برای اهداف جبر خطی، تابع transpose() مفیدتر است، چون به‌سرعت یک پوشش تنبل حول ماتریس اصلی ایجاد می‌کند.
حتی مفیدتر تابع adjoint() است، که علامت بخش موهومی را در اعداد مختلط برعکس می‌کند (اگر تعجب می‌کنید چرا اینقدر مهم است، یک پاسخ سریع مکانیک کوانتومی است).
این عملیات آنقدر رایج است که می‌توانیم فقط یک آپاستروف ' به اسم متغیر اضافه کنیم تا الحاقی را بسازیم.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
# new, full copy
julia> permutedims(m)
3×2 Matrix{Int64}:
1 4
2 5
3 6
# lazy version
julia> transpose(m)
3×2 transpose(::Matrix{Int64}) with eltype Int64:
1 4
2 5
3 6
julia> mc = [1+2im 2+3im; 3+2im 1+2im]
2×2 Matrix{Complex{Int64}}:
1+2im 2+3im
3+2im 1+2im
# lazy conjugate transpose
julia> adjoint(mc)
2×2 adjoint(::Matrix{Complex{Int64}}) with eltype Complex{Int64}:
1-2im 3-2im
2-3im 1-2im
# syntactic sugar for adjoint
julia> mc'
2×2 adjoint(::Matrix{Complex{Int64}}) with eltype Complex{Int64}:
1-2im 3-2im
2-3im 1-2im
ضرب
باقی این سند شامل قابلیت‌هایی از ماژول LinearAlgebra است.
یک خط using LinearAlgebra آن را به فضای نام می‌آورد، اما این را در مثال‌ها تکرار نمی‌کنیم (شلوغی بصری زیاد).
بردارها، ضرب عنصری
این در مفهوم عملیات برداری بحث شد.
عملگر .* است، که به صورت جفتی روی بردارهای ورودی عمل می‌کند و خروجی‌ای هم‌اندازه و هم‌تایپ ورودی‌ها می‌دهد.
julia> [1, 2] .* [3, 4]
2-element Vector{Int64}:
3
8
بردارها، ضرب داخلی
این عملیات بسیار رایج در کتاب‌های درسی به صورت u ⋅ v نوشته می‌شود و «ضرب داخلی» نام دارد.
یک ضرب داخلی معادل مجموع ضرب عنصری است.
دو بردار را می‌توان با عملگر معمول * ضرب کرد، اما فقط اگر بردار چپ یک adjoint باشد: به‌راحتی به صورت u' * v نوشته می‌شود.
این باید در بخش بعدی درباره‌ی ضرب ماتریس روشن‌تر شود.
نقطه‌ی بالا (_وسط) در Julia (با وارد کردن \cdot و زدن تب) به عنوان روشی ساده‌تر برای نوشتن تابع dot() در دسترس است.
نیازی به مشخص کردن الحاقی نیست، چون این جزئیات به صورت خودکار انجام می‌شود.
julia> using LinearAlgebra
# with element-wise syntax
julia> sum([1, 2] .* [3, 4])
11
# with u' * v syntax
julia> [1, 2]' * [3, 4]
11
# with dot()
julia> dot([1, 2], [3, 4])
11
# with \cdot syntax
julia> [1, 2] ⋅ [3, 4]
11
برای بردارهای مختلط، بردار چپ باید مزدوج باشد (علامت بخش موهومی برعکس شود).
تابع dot این کار را خودکار انجام می‌دهد، روش نوشتن u' آن را صریح انجام می‌دهد، اما sum(u .* v) اگر u و v مختلط باشند شکست می‌خورد.
بردارها، ضرب خارجی
کمی نوستالژی برای هر کسی که در گذشته دوره‌ی الکتریسیته و مغناطیس گذرانده است!
همچنین مهندسانی که با محاسبه‌ی بردارهای گشتاور یا تکانه‌ی زاویه‌ای آشنا هستند.
در حالی که ضرب داخلی دو بردار را به یک scalar تبدیل می‌کند، ضرب خارجی دو بردار سه‌بعدی را به یک بردار سه‌بعدی سوم تبدیل می‌کند.
در نمایش هندسی فضای برداری، بردار جدید عمود بر صفحه‌ای است که دو بردار ورودی را در بر می‌گیرد.
اگر دو ورودی موازی باشند (تا حد یک علامت)، صفحه‌ای تعریف نمی‌کنند، بنابراین خروجی [0, 0, 0] خواهد بود.
ترتیب مهم است: u × v == -(v × u).
این همان قاعده‌ی دست راست معروف است، که بسیاری از ما را واداشته در حالی که انگشت شست و دو انگشت دیگرمان را در فضا می‌چرخانیم به آن‌ها خیره شویم (اغلب با حالتی گیج).
# with \times syntax
julia> [1, 2, 3] × [3, 4, 5]
3-element Vector{Int64}:
-2
4
-2
# with cross()
julia> cross([1, 2, 3], [3, 4, 5])
3-element Vector{Int64}:
-2
4
-2
توجه کنید که این عملیات به بردارهای با طول ۳ محدود است (معادل فضای اقلیدسی با محورهای متعامد x, y, z).
ریاضی‌دانان با کمال میل این عملیات را برای ابعاد دیگر تعریف می‌کنند، و نتیجه چیزی می‌شود شبیه سالاد کلمه‌ای نامفهوم (تانسورهای مرتبه‌ی بالاتر، ضرب گوه‌ای، ضرب خارجی، چندبرداری‌ها...).
بیشتر ما در آن نقطه فرار می‌کنیم یا سریع موضوع را عوض می‌کنیم!
نُرم‌ها
یک بردار چقدر «بزرگ» است؟
norm تلاشی برای به دست آوردن این است، با کاهش بردار به یک اسکالر مناسب.
خانواده‌ای کامل از نُرم‌ها تعریف شده است، اما تا اینجا رایج‌ترین آن‌ها نُرم ۲ است، که برابر √(v ⋅ v) است.
این عملیات ریشه‌ی میانگین مربعات، فاصله‌ی فیثاغورسی از مبدأ است (در فضای N-بعدی).
اگر بردار را به صورت پیکانی تجسم کنیم که دُم آن در مبدأ است، نُرم ۲ طول پیکان است.
هر p-نُرمی را می‌توان با دادن p به عنوان آرگومان دوم محاسبه کرد.
نُرم ۱ گاهی مفید است: به سادگی مجموع قدر مطلق درایه‌هاست (بنابراین محاسبه‌ی آن بسیار سریع و آسان است).
# defaults to the 2-norm
julia> norm([1, 2, 3])
3.7416573867739413
# the 1-norm
julia> norm([1, -2, 3], 1)
6.0
ضرب ماتریس
گاهی به نظر می‌رسد که هر ریاضی‌دان کاربردی در جهان بیشتر ۸۰ سال گذشته را صرف تبدیل هر محاسبه به مجموعه‌ای از ضرب‌های ماتریسی کرده است.
این عملیاتی است که کامپیوترها در آن بسیار خوب هستند:
- بسیار تکراری است.
- می‌توان آن را به طور کارآمد موازی‌سازی کرد.
- سخت‌افزار تخصصی زیادی برای سریع‌تر کردن آن توسعه یافته است، از Cray-1 ۸۰ میلیون دلاری در دهه‌ی ۱۹۷۰ تا واحد پردازش گرافیکی (GPU) که احتمالاً در لپ‌تاپ شما تعبیه شده است.
جزئیات نسبتاً ساده است، هرچند در نگاه اول چندان شهودی نیست.
ماتریس A را در نظر بگیرید که در بردار v ضرب می‌شود تا خروجی w را بدهد (طبق قرارداد جبر خطی، برای ماتریس‌ها از حروف بزرگ و برای بردارها از حروف کوچک استفاده می‌کنیم).
سطر اول A در v ضرب داخلی می‌شود تا عنصر اول w به دست آید، سطر دوم عنصر دوم را می‌دهد، و به همین ترتیب تا پایین.
julia> A = [1 2; 3 4]
2×2 Matrix{Int64}:
1 2
3 4
julia> v = [5, 6]
2-element Vector{Int64}:
5
6
julia> A * v
2-element Vector{Int64}:
17 # equals [1, 2] ⋅ [5, 6]
39 # equals [3, 4] ⋅ [5, 6]
ضرب ماتریس در ماتریس این را به ستون‌های ماتریس سمت راست تعمیم می‌دهد.
برای C = A * B، می‌توانیم در نظر بگیریم که A هر ستون B را ضرب می‌کند تا ستون متناظر C را بدهد: مجموعه‌ای از ضرب‌های ماتریس-بردار.
به طور معادل، می‌توان گفت که سطر اول A در هر ستون B ضرب داخلی می‌شود تا سطر اول C به دست آید، سطر دوم سطر دوم را می‌دهد، و به همین ترتیب.
چندین نمایش ذهنی از این دست وجود دارد، و دانشجویان علاقه‌مند می‌توانند یک سخنرانی کامل MIT را تماشا کنند که درباره‌ی آن‌ها بحث می‌کند.
julia> A
2×2 Matrix{Int64}:
1 2
3 4
julia> B = [5 7; 6 8]
2×2 Matrix{Int64}:
5 7
6 8
# left column is the same as A*v previously
julia> A * B
2×2 Matrix{Int64}:
17 23
39 53
julia> B * A
2×2 Matrix{Int64}:
26 38
30 44
همان‌طور که در مثال بالا نشان داده شد، ضرب ماتریس جابه‌جایی‌پذیر نیست: هیچ رابطه‌ی ساده‌ای بین A*B و B*A وجود ندارد.
ضرب ماتریس احتمالاً برای هر تازه‌واردی فقط با خواندن متن سخت قابل تجسم است.
YouTube ویدیوهای زیادی دارد که آن را به صورت گرافیکی نشان می‌دهند، پس «ضرب ماتریس» را جستجو کنید و یکی را با سبک، سطح جزئیات و زبان دلخواهتان انتخاب کنید.
ابعاد
ضرب داخلی دو بردار به هم‌اندازه بودن آن‌ها بستگی دارد.
به همین ترتیب، برای ضرب ماتریس، تعداد ستون‌های ماتریس چپ باید با تعداد سطرهای ماتریس راست مطابقت داشته باشد.
با بیان اندازه‌ها به صورت چندتایی‌های (nrows, ncols)، همان‌طور که size(A) خروجی می‌دهد، داریم (a, b) * (b, c) -> (a, c).
ابعاد «داخلی»، اینجا b و b، با گرفتن ضرب داخلی سازگارند.
ابعاد «خارجی»، اینجا a و c، ابعاد خروجی را تعیین می‌کنند.
مثالی با ماتریس‌های مستطیلی:
julia> D = reshape(1:6, 2, 3)
2×3 reshape(::UnitRange{Int64}, 2, 3) with eltype Int64:
1 3 5
2 4 6
julia> E = reshape(1:12, 3, 4)
3×4 reshape(::UnitRange{Int64}, 3, 4) with eltype Int64:
1 4 7 10
2 5 8 11
3 6 9 12
julia> D * E
2×4 Matrix{Int64}:
22 49 76 103
28 64 100 136
# (3, 4) * (2, 3) not possible
julia> E * D
ERROR: DimensionMismatch: matrix A has axes (Base.OneTo(3),Base.OneTo(4)), matrix B has axes (Base.OneTo(2),Base.OneTo(3))
ضرب جفت‌های بردار به سبک ماتریسی دو امکان دارد.
طبق قرارداد، از u' * v به عنوان معادلی برای ضرب داخلی استفاده می‌کنیم.
ابعاد (1, 3) * (3, 1) هستند، و Julia خروجی (1, 1) را به یک اسکالر ساده می‌کند (برخلاف مثلاً R).
به طور جایگزین، می‌توانیم از u * v' با ابعاد (3, 1) * (1, 3) -> (3, 3) استفاده کنیم تا همه‌ی جفت‌های ممکن عناصر را ضرب کنیم و بردارها را به یک ماتریس گسترش دهیم.
julia> u = [1, 2]
2-element Vector{Int64}:
1
2
julia> v = [3, 4]
2-element Vector{Int64}:
3
4
julia> u' * v
11
julia> u * v'
2×2 Matrix{Int64}:
3 4
6 8
u' * v گاهی ضرب داخلی نامیده می‌شود.
u * v' (کمتر رایج) به همان ترتیب ضرب بیرونی است.
این به ضرب تانسوری مربوط است، هرچند آن بسیار فراتر از حوزه‌ی ماست.
دوران‌ها
یک نوع به‌خصوص رایج از ضرب ماتریس شامل ماتریس‌های دوران است.
در دوبعد، ماتریس نسبتاً ساده‌ای برای چرخاندن یک بردار در جهت پادساعتگرد به اندازه‌ی θ رادیان وجود دارد.
julia> rot2d(θ, vec) = [cos(θ) -sin(θ); sin(θ) cos(θ)] * vec
rot2d (generic function with 1 method)
# unit vector in the x direction
julia> i_hat = [1, 0]
2-element Vector{Int64}:
1
0
# rotate 45 degrees
julia> rot2d(π/4, i_hat)
2-element Vector{Float64}:
0.7071067811865476
0.7071067811865475
# rotate 90 degrees -> unit vector in the y direction, j_hat
julia> rot2d(π/2, i_hat)
2-element Vector{Float64}:
6.123233995736766e-17 # zero, within numerical error
1.0
دوران‌ها در سه‌بعد به ماتریس پیچیده‌تری نیاز دارند، با دو زاویه.
نمایش این در یک سند Markdown بدون جاسازی LaTeX زیاد دشوار است، پس فرمول را در ویکی‌پدیا ببینید.
برای گرافیک سه‌بعدی، مانند OpenGL و جانشینانش، قرارداد کار با مختصات همگن است.
هر راس با یک بردار ۴تایی (یا معادلاً یک ستون ماتریس) نمایش داده می‌شود: [x, y, z, 1.0] برای نقطه‌ای در (x, y, z).
این امکان ماتریس‌های تبدیل مفصل‌تر را فراهم می‌کند.
دوران همچنان در A[1:3, 1:3] است، انتقال‌ها [Δx, Δy, Δz] در A[1:3, 4] هستند، مقیاس‌دهی روی قطر است، و احتمالات دیگری برای کج‌شدگی، پرسپکتیو و غیره وجود دارد.
کارایی
در دپارتمان‌های علوم کامپیوتر در سراسر جهان، پایان‌نامه‌های دکتری زیادی وجود دارد که یک یا چند فصل آن‌ها درباره‌ی بهبودهای کوچک و تدریجی در الگوریتم‌های ضرب ماتریس است.
این واقعاً مهم است، و سازمان‌های مختلف حاضرند برای منفعت خودشان از این پژوهش حمایت مالی کنند.
کارایی موضوع بزرگی است که نمی‌توانیم عمیقاً به آن بپردازیم، اما برای مثال می‌توانیم ضرب ماتریس‌های تصادفی با اندازه‌های مختلف را امتحان کنیم.
کد زیر یک تخمین سریع و سرهم‌بندی است (برای رویکرد بهتر از BenchmarkTools.jl استفاده کنید).
سیستم استفاده‌شده یک رایانه‌ی شخصی کوچک ۴۳۰ دلاری (آمریکا) بود: پردازنده‌ی Ryzen ۹، ۳۲ گیگابایت رم، Linux Mint ۲۲.۱، Julia ۱.۱۱.۶.
julia> mmul(A) = A * A
mmul (generic function with 1 method)
julia> A = rand(Float64, 1_000, 1_000);
julia> @time mmul(A);
0.011055 seconds (3 allocations: 7.629 MiB)
julia> A = rand(Float64, 10_000, 10_000);
julia> @time mmul(A);
7.236284 seconds (1.61 k allocations: 763.027 MiB, 17.92% gc time, 0.15% compilation time)
به طور تقریبی، یک جفت ماتریس میلیون‌عنصری چند میلی‌ثانیه طول کشید، ماتریس‌های ۱۰۰ میلیون‌عنصری چند ثانیه.
افزودن چند مرتبه‌ی بزرگی دیگر به سخت‌افزار بهتری نیاز دارد...
1 تمرین
مبانی جبر خطی را یاد بگیرید