كيفية التحقق مما إذا كانت المتجهات بحجم m n مستقلة خطيًا؟
https://stackoverflow.com/questions/532029
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
تنصل
هذا ليس سؤالًا برمجيًا بشكل صارم، ولكن سيتعين على معظم المبرمجين عاجلاً أم آجلاً التعامل مع الرياضيات (خاصة الجبر)، لذلك أعتقد أن الإجابة قد تكون مفيدة لشخص آخر في المستقبل.
الآن المشكلة
أحاول التحقق مما إذا كانت متجهات m ذات البعد n مستقلة خطيًا.إذا كانت m == n، فيمكنك فقط إنشاء مصفوفة باستخدام المتجهات والتحقق مما إذا كان المحدد هو != 0.ولكن ماذا لو م <ن؟
أي تلميحات؟
أنظر أيضا هذه المحاضرة بالفيديو.
المحلول
أنشئ مصفوفة للمتجهات (صف واحد لكل متجه)، وقم بإجراء القضاء غاوسي على هذه المصفوفة.إذا تم إلغاء أي من صفوف المصفوفة، فهي ليست مستقلة خطيا.
الحالة التافهة هي عندما تكون m > n، في هذه الحالة، لا يمكن أن تكون مستقلة خطيًا.
نصائح أخرى
بناء مصفوفة M صفوفها هي المتجهات وتحدد رتبة M.إذا كانت رتبة M اقل من m (عدد المتجهات) فهناك اعتماد خطي.في الخوارزمية لتحديد رتبة M يمكنك إيقاف الإجراء بمجرد حصولك على صف واحد من الأصفار، ولكن تشغيل الخوارزمية حتى الاكتمال له ميزة إضافية تتمثل في توفير بُعد المجموعة الممتدة من المتجهات.أوه، والخوارزمية لتحديد رتبة M هو مجرد حذف غاوسي.
احذر من عدم الاستقرار العددي.انظر التحذير في بداية الفصل الثاني في الوصفات الرقمية.
لو m<n, ، سيتعين عليك إجراء بعض العمليات عليها (هناك احتمالات متعددة:الحذف الغوسي، والتعامد، وما إلى ذلك، تقريبًا أي تحويل يمكن استخدامه لحل المعادلات سيفي بالغرض) والتحقق من النتيجة (على سبيل المثال.الحذف الغوسي => صف أو عمود صفر، التعامد => متجه صفر، SVD => رقم مفرد صفر)
ومع ذلك، لاحظ أن هذا السؤال هو سؤال سيء يجب على المبرمج طرحه، وهذه المشكلة هي مشكلة سيئة يجب على البرنامج حلها.وذلك لأن كل مجموعة تعتمد خطيا من n<m تحتوي المتجهات على مجموعة مختلفة من المتجهات المستقلة خطيًا القريبة (على سبيل المثال.المشكلة غير مستقرة عدديا)
لقد كنت أعمل على هذه المشكلة هذه الأيام.
في السابق، وجدت بعض الخوارزميات المتعلقة بالحذف الغوسي أو الغوسي الأردني، لكن معظم هذه الخوارزميات تنطبق فقط على المصفوفة المربعة، وليس المصفوفة العامة.
لتقديم طلب للحصول على مصفوفة عامة، قد تكون إحدى أفضل الإجابات هي:http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB
يمكنك العثور على كل من الكود الزائف والكود المصدري بلغات مختلفة.بالنسبة لي، قمت بتحويل كود مصدر Python إلى C++، لأن كود C++ الموجود في الرابط أعلاه معقد إلى حد ما وغير مناسب للتنفيذ في المحاكاة الخاصة بي.
آمل أن يكون هذا مفيدًا لك، ونتمنى لك حظًا موفقًا ^^
إذا لم تكن قوة الحوسبة مشكلة، فربما تكون أفضل طريقة هي العثور على القيم المفردة للمصفوفة.في الأساس تحتاج إلى العثور على القيم الذاتية لـ M'*M وانظر إلى نسبة الأكبر إلى الأصغر.إذا لم تكن النسبة كبيرة جدًا، تكون المتجهات مستقلة.
هناك طريقة أخرى للتحقق من أن متجهات الصف m مستقلة خطيًا، عند وضعها في مصفوفة M بحجم mxn، وهي الحساب
det(M * M^T)
أي.محدد مصفوفة مربعة mxmسيكون صفرًا إذا وفقط إذا كان M يحتوي على بعض الصفوف التابعة.ومع ذلك، يجب أن يكون الحذف الغوسي أسرع بشكل عام.
آسف يا رجل، خطأي...
تبين أن كود المصدر الموجود في الرابط أعلاه غير صحيح، على الأقل كود بايثون الذي اختبرته ورمز C++ الذي قمت بتحويله لا يولد الإجابة الصحيحة طوال الوقت.(أما بالنسبة للمثال الموجود في الرابط أعلاه فالنتيجة صحيحة :) -- )
لاختبار كود بايثون، ما عليك سوى استبدال ملف mtx مع
[30,10,20,0],[60,20,40,0]
وستكون النتيجة التي تم إرجاعها مثل:
[1,0,0,0],[0,1,2,0]
ومع ذلك، فقد حصلت على وسيلة للخروج من هذا.لقد قمت هذه المرة فقط بتحويل كود مصدر matalb لـ rref الدالة إلى C++.يمكنك تشغيل MATLAB واستخدام type rref أمر للحصول على الكود المصدري لـ rref.
لاحظ فقط أنه إذا كنت تعمل بقيمة كبيرة جدًا أو قيمة صغيرة جدًا، فتأكد من استخدام long double نوع البيانات في C++.وإلا، سيتم اقتطاع النتيجة وغير متسقة مع نتيجة MATLAB.
لقد أجريت عمليات محاكاة كبيرة في ns2، وكانت جميع النتائج المرصودة سليمة.آمل أن يكون هذا مفيدًا لك ولأي شخص آخر واجه المشكلة ...
هناك طريقة بسيطة للغاية، وليست الأكثر كفاءة من الناحية الحسابية، وهي ببساطة إزالة الصفوف العشوائية حتى m=n ثم قم بتطبيق الحيلة المحددة.
m < n:قم بإزالة الصفوف (اجعل المتجهات أقصر) حتى تصبح المصفوفة مربعة، ثمm = n:تحقق مما إذا كان المحدد هو 0 (كما قلت)m < n(عدد المتجهات أكبر من طولها):إنهم يعتمدون خطيًا (دائمًا).
والسبب باختصار هو أن أي حل لنظام m x n المعادلات هي أيضا حل ل n x n نظام المعادلات (أنت تحاول حلها Av=0).للحصول على شرح أفضل، راجع ويكيبيديا, ، وهو ما يفسر ذلك أفضل مما أستطيع.
