قياس سبع مرات - قطع مرة واحدة ، أو استخدام القول في الممارسة

جلست في دورة Coursera. كانت الدورة موجهة للمبتدئين في Java ، وفي أحد دروس الفيديو تم طرح الموضوع 7 خطوات لحل المشكلات .

لقد استمعت ، بضمير مرتاح ، إلى الفيديو التعليمي ، وقلت لنفسي ، إن هذا العمل ذهب بعيداً ولفترة طويلة.

بقية الدورة كانت سهلة ومريحة. ولكن ، فيما يتعلق بأحد موضوعات الجامعة ، وتحديدا فيما يسمى "البرمجة العلمية" ، ظهرت المهمة التالية:

حل نظام المعادلات الخطية $$$Ax=b$باستخدام توسيع المصفوفة التالية $$$A$:

$$

$$A = LU,$$

أين $$$L$هي المصفوفة الثلاثية السفلية و $$$U$هي المصفوفة المثلثة العليا.

موضوع الجبر الخطي الذي تناولناه في الدورة الأولى. بصراحة ، تذكرت المبادئ العامة للعمليات باستخدام المصفوفات والنواقل وأقدس الأقداس - طريقة غاوس. إذا كنت تفكر في الأمر مع العقول ، فإننا لم ندرس أي تحلل LU ، ولكن طريقة "google" تساعد دائمًا. انقاذ حتى هذه اللحظة.

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

1. صف المشكلة يدويًا

كل ما تفتقر إليه في الحياة هو فهم المشكلة حقًا. لنأخذ مثالاً للمشكلة المذكورة أعلاه ونكتبها على قطعة من الورق. بطريقة جيدة ، يجب استيفاء الشروط التالية لوجود المصفوفات$$$L$ و $$$U$:

- يجب أن توجد المصفوفة العكسية$$$A$، انا اعني $$$\exists{A^{-1}}$؛
- يجب ألا يتدهور جميع القاصرين ، أي$$$\Delta_{(1,...,n)}\neq{0}$

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

إن المشكلة واضحة بالنسبة لنا: البحث عن المصفوفات$$$L$ و $$$U$التي ستندرج تحت الشروط المذكورة أعلاه. بعد أن حاولت استخدام Google لأساليب الحل ، من غير المحتمل أن تتمكن من تنفيذ الخوارزمية بشكل صحيح في المرة الأولى (إذا لم تكن جيدًا في الجبر الخطي). بعد اجتياز العديد من المحاولات ، سنقوم على الأرجح بتطوير سلسلة من الإجراءات لحل مشكلتنا ، ثم ننتقل إلى الخطوة 2.

2. صف ما فعلته

خذ المصفوفة كمثال

$$

$$A = \begin{pmatrix} 1&2&3 \newline 0&-2&4 \newline 1&-1&0 \end{pmatrix}.$$

الآن نقوم بتطبيق طريقة Gauss الخاصة بنا عليها والتخلص من العناصر الإضافية في السطر 3 ، بطرح السطر الأول منه ، مضروبًا في نسبة العنصر الأول من 3 سطور إلى العنصر الأول من السطر 1:

$$

$$a_3=a_3-a_1 \cdot\frac { {a_3}_1 }{ {a_1}_1 }.$$

الآن ، تخلص من العنصر الثاني في السطر 3 بإجراء مماثل:

$$

$$a_3=a_3-a_2 \cdot\frac { {a_3}_2 }{ {a_2}_2 }.$$

ونتيجة لذلك ، نحصل على المصفوفة

$$

$$A = \begin{pmatrix} 1&2&3 \newline 0&-2&4 \newline 0&0&0 \end{pmatrix}=U.$$

والآن ، المعاملات التي وجدناها (نتيجة لنسبة العناصر $$$\frac{{a_i}_j}{{a_j}_j}$) خذ قيم المصفوفة $$$L$، واحصل على

$$

$$L = \begin{pmatrix} 1&0&0 \newline 0&1&0 \newline 1&\frac{1}{2}&1 \end{pmatrix}.$$

بالنظر إلى القالب ، أليس كذلك؟

3. إيجاد الأنماط

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

لذا ، بناءً على مثال ، يمكننا صياغة قالب الحل / الخوارزمية التالي:

1. تحديد مصفوفة مربعة$$$A, n$الترتيب عشر ؛
2. تعيين المصفوفة$$$L = I$أين $$$I$- مصفوفة الهوية $$$n$الترتيب عشر ؛
3. تعيين المصفوفة$$$U = A$؛
4. نطبق التحولات المتعاقبة التالية على المصفوفات شريطة ذلك$$$\begin{cases} i=2,\ldots, n \newline j=1,\ldots,i \end{cases}$

$$

$$\begin{array}{c} {l_i}_j=\frac{{u_i}_j}{{u_j}_j} \newline u_i = u_i-u_j\cdot{{{l_i}_j}} \end{array},$$

في $$$n = 3$نحن نحصل:

$$

$$L = \begin{pmatrix} 1&0&0 \newline {l_2}_1&1&0 \newline {l_3}_1&{l_3}_2&1 \end{pmatrix},\quad U = \begin{pmatrix} {u_1}_1&{u_1}_2&{u_1}_3 \newline 0&{u_2}_2&{u_2}_3 \newline 0&0&{u_3}_3 \end{pmatrix}$$

4. التحقق من القالب / الخوارزمية

هناك خوارزمية - هناك الملايين من المصفوفات لاختبارها! لا يمكنك أن تقلق بشأن هذا النموذج ، فمن الواضح أنه صحيح (تم اختباره شخصيًا على معظم المصفوفات المحتملة غير المنحطة). لكن تذكر: اسرع - أنت تضحك الناس . لذا تحقق دائمًا من النماذج التي أنشأتها حتى لا تستمر في القفز مثل اللعنة حتى البداية.

5. ترجمة الخوارزمية إلى كود

الخطوة الواضحة ، كل ما تحتاجه غالبًا ما تكون في صياغة اللغة ، وإذا لم يكن الأمر كذلك ، فلا يزعجك أحد لإنشاء فئات ووظائف لحل هذه المشكلة ، فلديك خوارزمية. نظرًا لأنني قمت بتطبيق هذه الخوارزمية كجزء من برنامج جامعي تعليمي ، كان بإمكاني فقط استخدام Octave للتنفيذ ، لذا فإن كل التعليمات البرمجية التي أقدمها لك موجودة في صيغتها (وهي مشابهة جدًا لـ Python ، لذلك سأستخدم تمييزها للتنسيق):

A = input("Enter the matrix A: ")
numOfRows = size(A, 1)
numOfCols = size(A, 2)

if numOfRows ~= numOfCols
    disp("Wrong matrix.")
else
    n = numOfCols
    disp("----------------")
    L = eye(3)
    disp("Making U = A")
    U = A
    disp("----------------")

    for i=2:n
        disp("Step "), disp(i-1)
        for j=1:i-1
            L(i,j) = U(i,j)/U(j,j)
            U(i,:) = U(i,:) - U(j,:)*L(i,j)
        end
        disp("----------------")
    end

    disp("Check the answer of L*U: "), disp(L*U)
end

6. البحث عن اختبارات فاشلة

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

في هذه الخطوة ، يجب أن تجد جميع الأخطاء المحتملة ، وعدم الدقة في التعليمات البرمجية الخاصة بك ، ونتيجة لذلك قد يتم الكشف عن تحيز الخوارزمية التي تم إنشاؤها. لذلك ، هنا يجب عليك تجربة أكبر عدد ممكن من الإغفالات التي يمكن إجراؤها.

7. فشل اختبارات التصحيح

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

استنتاج

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

ملحوظة

بفضل كتب الجبر الخطية للمواد لحل المشكلة.