أساسيات الجبر الخطي في

نبذة عن أساسيات الجبر الخطي

ما هو "الجبر الخطي"؟

توجد تعريفات تقنية كثيرة، على ويكيبيديا، وفي الكتب المدرسية، وعلى مواقع ممتازة مثل 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 ثم Tab) كصيغة مختصرة للدالة 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

لاحظ أن هذه العملية مقصورة على المتجهات ذات الطول 3 (أي ما يكافئ فضاءً إقليديًا بمحاور متعامدة x, y, z). ويسعد علماء الرياضيات بتعريف العملية لأبعاد أخرى، وتكون النتيجة خليطًا غير مفهوم من الكلمات (تنسورات من رتب أعلى، الجداء الوتدي، الجداء الخارجي، المتجهات المتعددة...). ومعظمنا يهرب أو يغيّر الموضوع بسرعة عند هذه النقطة!

المعايير

ما مدى "ضخامة" المتجه؟

المعيار norm محاولة لالتقاط ذلك، باختزال المتجه إلى عدد قياسي مناسب.

تُعرَّف عائلة كاملة من المعايير، لكن الأكثر شيوعًا بفارق كبير هو المعيار 2، وهو √(v ⋅ v).

هذه العملية، أي الجذر التربيعي لمتوسط المربعات، هي مسافة فيثاغورس من نقطة الأصل (في فضاء بُعده N). إذا تخيّلنا المتجه سهمًا ذيله عند نقطة الأصل، فإن المعيار 2 هو طول السهم.

يمكن حساب أي معيار p بتقديم p كوسيط ثانٍ. المعيار 1 مفيد أحيانًا: فهو ببساطة مجموع القيم المطلقة للعناصر (لذا حسابه سريع وسهل جدًا).

# 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 الذي كلّف 80 مليون دولار في سبعينيات القرن الماضي إلى وحدة معالجة الرسومات (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 للحصول على مقاربة أفضل).

الجهاز المستخدم كان حاسوبًا شخصيًا صغيرًا بثمن 430 دولارًا (أمريكيًا): معالج Ryzen 9، وذاكرة RAM بسعة 32GB، وLinux Mint 22.1، وJulia 1.11.6.

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)

بشكل تقريبي، استغرق زوج من المصفوفات بمليون عنصر بضعة أجزاء من الثانية، واستغرقت مصفوفات بمئة مليون عنصر بضع ثوانٍ. وإضافة بضع رتب أخرى من حيث الحجم ستتطلب عتادًا أفضل...