أيهما أسرع / أكثر استقرارا: مصفوفة طالب أو حل ثلاثة أنظمة لمعادلات خطية مع عدة جوانب يمينية متعددة؟

Question

لدي معادلات اثنين أنا حلها على كل جولة متكررة:

X = A - Inv (B) * y * Inv (b)، x = x + a '* inv (b) * a،

أنا حل المشكلة بهذه الطريقة:

ج = Inv (ب)Y <=> BC = Y، حل C. D = CInv (b) <=> DB = C <=> B'D '= C'، SOLVE D '

E = Inv (B) * A <=> BE = A، حل E.

تتغير جميع المصفوفات مع مرور الوقت، لذلك يجب علي القيام بذلك (أو إبطال) مرة أخرى كل قوائم. ن عادة حوالي 1-10، ربما أكثر، ولكن عادة ما يكون هناك شيء من هذا القبيل. B موجبة محددة حتى أتمكن من استخدام Cholesky على العامل، ثم حل معادلات من الجانبين اليد اليمنى المتعددة.

هل هذا أبطأ بكثير أو أسرع من مجرد تجنب ب ثم القيام بصدد مصفوفة مع ذلك؟ واحد invertion مقابل حل ثلاثة أنظمة لمعادلات خطية (هناك معادلة أخرى أيضا) بالإضافة إلى بعض الانتقال. أعتقد أنه على الأقل أكثر استقرارا أكثر استقرارا من قلبه؟

شكرا.

Answer 1

بادئ ذي بدء، دعونا نفترض أن كل مصفوفاتك هي من أمر NX N. يمكن بعد ذلك القيام بعمليات Cholesky في عمليات O (n ^ 3/6) (للقيم الكبيرة من N).

حل B * C (I) = y (i) أو l * l '* c (i) = y (i) (cholesky) هو 2 * o (n ^ 2/2) أو O (n ^ 2)، ولكن حل BC = Y هو حل N من هذه المعادلات (لأن y هو NXN)، لذلك في المجموع لدينا O (N ^ 3).

حل D 'من الواضح أن هذا، حتى آخر س (ن ^ 3).

نقل D 'إلى D هو Rougly O (n ^ 2)، لا توجد حسابات، فقط تبديل البيانات (بصرف النظر عن العناصر القطرية التي هي نفسها).

حل E في BE = أ

a '* e هو n ^ 2 * (n mult and n-1 أضف) وهو O (2 * n ^ 3 - n ^ 2)

هذا يلخص ما يصل إلى: O (n ^ 3/6) + 3 * o (n ^ 3) + O (n ^ 2) + O (2 * n ^ 3 - n ^ 2) ~ o (31 * n ^ 3 / 6) ~ o (5 * n ^ 3) (للقيم الكبيرة من n)

لاحظ أنني لم أقم بحسبت إضافات / طروقات مصفوفة، لكن هذا ليس ذا صلة لأنها ستكون هي نفسها إذا قررنا الانقلاب B. لقد تخطيت أيضا A إلى نفس الأسباب.

حسنا، كم تكلف مكلفة مصفوفة؟ حسنا، نرتب على حل معادلة المصفوفة:

ب * Inv (b) = i، وهو نفس حل b * x (i) = e (i) = 1..n، حيث e (i) هي ناقلات الوحدة الأساسية في I. هذا هو عادة تم القيام به باستخدام القضاء Gauss لتحويل النظام إلى نموذج Triangular، الذي يستغرق عمليات O (N ^ 3/3). عند إجراء التثليث، يأخذ عمليات O (N ^ 2/2) لحلها (استبدال الخلفي). ولكن يجب أن يتم ذلك N مرات، مما يمنحنا ما مجموعه O (N ^ 4/3) + O (n ^ 3/2) العمليات، حتى تتمكن من رؤية نحن بالفعل على الحافة.

ومع ذلك، حساب Invulating Inv (B) عند معرفة عاملات Cholesky B هو O (n ^ 3) (لأن حل L * L '* Inv (B) = I هو نفسه حل = أ)

لذلك لدينا بعد ذلك: O (n ^ 3/6) (cholesky of b) + O (n ^ 3) (حساب Invul (b) باستخدام Choldsky) + 4 * O (2N ^ 3-n ^ 2) (أربعة مصفوفة الصدد) ~ O (9 * n ^ 3) وهو أفضل قليلا، ولكن لا يزال أسوأ.

لذلك أقترح عليك البقاء مع نهجك الحالي. ولكن عليك أن تضع في اعتبارها أن هذا هو لقيم كبيرة من n. ما لم يكن N 100+ لا أعتقد أنه يهم ذلك على أي حال.