حل المعادلات الخطية في

نبذة عن حل المعادلات الخطية

أتذكر حين تعلمت الجبر لأول مرة في المدرسة الثانوية؟

عادةً ما كان يُعطى لنا نظام من المعادلات، ويُطلب منا إيجاد 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

لنفترض الآن أن لديك 1000 معادلة في 1000 مجهول؟ إذا بدا ذلك سخيفًا، فتذكر أن أجهزة الاستشعار الرقمية اللاسلكية أصبحت الآن رخيصة ومتعددة الاستخدامات (قياس الانفعال، سرعة الرياح، التسارع على ثلاثة محاور، وأي شيء آخر...). امتلاك 1000 منها لمراقبة منشأة حديثة مثل جسر معلق أمر معقول تمامًا. لا بد من وجود نظام تحكم يفسّر تدفق البيانات، مستعدًا لإطلاق إنذار إذا أصبحت الأمور مقلقة.

مرة أخرى، 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

هذا مثال بسيط، لكن هناك بعض التفاصيل التي يجب الانتباه إليها.

• يجب أن تصطف المعاملات في أعمدة، لذا أدخل أصفارًا حسب الحاجة للحدود المفقودة.
• يجب أن تكون المعادلات (ومن ثم صفوف المصفوفة) مستقلة خطيًا. فإذا كان الصف 3 مجرد مجموع الصفين 1 و2، فإنه لا يضيف أي معلومة جديدة وتكون المسألة ناقصة التحديد.

يعطيك الأمر 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. للأسف، علينا فقط أن نتعايش مع كلمات تنتقل من لغة إلى أخرى في منتصف الكلمة.

عادةً ما يُعلَّم الطلاب كيفية حساب القيم/المتجهات الذاتية لمصفوفات 2×2 يدويًا، لكن استخدام الحاسوب أسهل بكثير (وإن كان لا يزال بطيئًا نوعًا ما، ويتدرج بمعدل O(n^3) لمصفوفة n×n في الحالة العامة).

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 متجهات وحدة معيارها يساوي 1.

التطبيقات

شرح سبب أهمية المتجهات الذاتية مهمة تصلح لكتاب دراسي من 500 صفحة، لا لفقرات قصيرة قليلة. هذا الموضوع يتخلل قدرًا هائلًا من الرياضيات التطبيقية الحديثة.

على المستوى الأعلى، تمثل المتجهات الذاتية المحاور (الاتجاهات) «الأكثر أهمية» في مجموعة بيانات. تشير القيم الذاتية إلى «الأهمية النسبية» لكل محور (رهنًا ببعض الافتراضات حول تطبيع المدخلات).

ما يعنيه هذا فعليًا يتوقف على التطبيق.

تحليل المكونات الرئيسية

في مسألة نمطية في علم البيانات، قد يكون لدينا 100 «سمة» أو أكثر، مخزنة كأعمدة من البيانات. وبشكل شبه حتمي، سيكون هناك ضجيج وتكرار وارتباطات غير مرغوبة.

نحتاج إلى تقليل الأبعاد، وPCA طريقة لإحلال النظام في الفوضى:

• احسب مصفوفة التغاير للبيانات.
• أصبح لدينا الآن مصفوفة مربعة، لذا احسب بعد ذلك القيم الذاتية والمتجهات الذاتية.
• رتّب المتجهات الذاتية تنازليًا حسب قيمها الذاتية (وبدقة أكبر، حسب القيمة المطلقة |λ|).
• أصبحت المتجهات الذاتية k الأولى هي principal components، حيث k أصغر بكثير من العدد الأصلي للسمات.
• أسقط مجموعة البيانات الكاملة على هذه المحاور k، وابدأ في البحث عن أنماط مثيرة للاهتمام.

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

لا يعد PCA جزءًا من تثبيت Julia الأساسي، لكن (خارج Exercism) تحتوي حزمة MultivariateStats على ما تحتاجه.

معالجة الصور

بالانتقال بفكرة PCA خطوة أخرى، فإن الصور الرقمية مجرد مصفوفات من قيم البكسلات، ويمكننا حساب المكونات الرئيسية لها.

استُخدم هذا لعقود في ضغط الصور، حيث يرشد PCA إلى ما هو الأهم للحفاظ عليه عند تقليل حجم الملف.

وبشكل متزايد، أصبح PCA جزءًا حيويًا من مصنّفات الصور مثل التعرف على الوجوه. في المرة القادمة التي تمر فيها عبر مطار، لن يكون الأخ الأكبر يراقبك فقط، بل سيستخدم أيضًا الجبر الخطي ليفهم ما يراه!

الهندسة الميكانيكية

وبشكل أقل إثارة للجدل، فإن المحاور الرئيسية لمكوّن ميكانيكي هي المتجهات الذاتية لـموتر عزم القصور الذاتي I (مصفوفة باسم مختلف قليلًا).

كل عجلة في سيارتك لها على الأرجح ثقل موازنة واحد أو أكثر، يُضبط لتصفير العناصر خارج القطر في هذا الموتر I. لا شك أن ميكانيكي الورشة يتجنب إجراء الحسابات (على عكس مصممي الطائرات ومهندسي الصواريخ)، لكن «الاهتزاز» مجرد كلمة يومية لوصف الحدود المتقاطعة في الموتر، والتي تجعل رحلتك في هذه الحالة أقل راحة وتزيد التآكل الميكانيكي في المحامل.