Sieben Mal messen - einmal schneiden oder das Sprichwort in der Praxis verwenden

Ich saß auf dem Coursera-Kurs. Der Kurs richtete sich an Anfänger in Java, und in einem der Video-Tutorials wurde das Thema 7 Schritte zur Lösung von Problemen angesprochen .

Ich habe mir mit gutem Gewissen das Video-Tutorial angehört und dachte mir, dieses Geschäft ist weit und lange gegangen.

Der Rest des Kurses war einfach und entspannt. Zu einem der Fächer der Universität, nämlich der sogenannten „Wissenschaftlichen Programmierung“, stellte sich jedoch folgende Aufgabe:

Lösen Sie ein lineares Gleichungssystem $$$Ax=b$unter Verwendung der folgenden Matrixerweiterung $$$A$::

$$

$$A = LU,$$

Wo $$$L$Ist die untere Dreiecksmatrix und $$$U$Ist die obere Dreiecksmatrix.

Das Thema der linearen Algebra, das wir im 1. Kurs aufgenommen haben. Ehrlich gesagt erinnerte ich mich an die allgemeinen Prinzipien der Operationen mit Matrizen, Vektoren und dem Allerheiligsten - der Gauß-Methode. Wenn Sie es sich mit dem Gehirn überlegen, haben wir keine LU-Zerlegung untersucht, aber die Google-Methode hilft immer. Bis zu diesem Punkt gerettet.

Ich habe einen allgemeinen Algorithmus zum Finden von Matrizen gefunden $$$L$und $$$U$, aber um halb vier Uhr morgens gab mir kein Kaffee die Möglichkeit, es richtig umzusetzen (vorausgesetzt, wir haben dort auf Octave codiert). Am Ende flippte ich aus und beschloss, trotzdem das klug benannte Sprichwort zu hören.

1. Beschreiben Sie das Problem von Hand

Alles, was Ihnen im Leben fehlt, ist zu verstehen, was das Problem wirklich ist. Nehmen wir ein Beispiel für das obige Problem und schreiben es auf ein Blatt Papier. In guter Weise müssen die folgenden Bedingungen für die Existenz von Matrizen erfüllt sein$$$L$ und $$$U$:

- Die inverse Matrix muss existieren$$$A$, Ich meine $$$\exists{A^{-1}}$;;
- Alle großen Minderjährigen sollten nicht entartet sein$$$\Delta_{(1,...,n)}\neq{0}$

Deshalb brauchen wir zumindest einen "Narrentest", denn es gibt sicherlich kluge Leute, die die Matrix verwenden wollen, die für uns nicht geeignet ist. Aber lassen wir es jetzt weg.

Das Problem ist uns klar: Matrizen finden$$$L$ und $$$U$das wird unter den oben genannten Bedingungen fallen. Nachdem Sie versucht haben, die Lösungsmethoden zu googeln, ist es unwahrscheinlich, dass Sie den Algorithmus beim ersten Mal korrekt implementieren können (wenn Sie nicht gut in linearer Algebra sind). Nachdem wir unzählige Versuche durchlaufen haben, werden wir höchstwahrscheinlich eine Abfolge von Maßnahmen entwickeln, um unser Problem zu lösen, und dann fahren wir mit Schritt 2 fort.

2. Beschreiben Sie, was Sie getan haben

Nehmen Sie die Matrix als Beispiel

$$

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

Jetzt wenden wir unsere Gauß-Methode darauf an und entfernen unnötige Elemente in der 3. Zeile, indem wir die erste Zeile davon subtrahieren, multipliziert mit dem Verhältnis des ersten Elements von 3 Zeilen zum ersten Element von 1 Zeile:

$$

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

Entfernen Sie nun das zweite Element der 3-Zeile mit einer ähnlichen Aktion:

$$

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

Als Ergebnis erhalten wir die Matrix

$$

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

Und nun die Koeffizienten, die wir gefunden haben (das Ergebnis des Verhältnisses der Elemente $$$\frac{{a_i}_j}{{a_j}_j}$) nimm die Werte der Matrix $$$L$, und bekomme

$$

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

Schauen Sie sich die Vorlage an, nicht wahr?

3. Muster finden

In diesem Stadium kehren Sie höchstwahrscheinlich zu Schritt 1 und 2 zurück, da die Vorlage, die Sie nicht immer gefunden haben, in allen Fällen wahr ist. Aber nichts, da es nicht geklappt hat, wird es als nächstes passieren.

Anhand eines Beispiels können wir also den folgenden Algorithmus / die folgende Lösungsvorlage formulieren:

1. Definieren Sie eine quadratische Matrix$$$A, n$th Ordnung;
2. Stellen Sie die Matrix ein$$$L = I$wo $$$I$- Identitätsmatrix $$$n$th Ordnung;
3. Stellen Sie die Matrix ein$$$U = A$;;
4. Wir wenden die folgenden aufeinanderfolgenden Transformationen auf die Matrizen an, vorausgesetzt, dass$$$\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},$$

Beim $$$n = 3$wir bekommen:

$$

$$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. Überprüfen der Vorlage / des Algorithmus

Es gibt einen Algorithmus - es gibt Millionen von Matrizen, um ihn zu testen! Sie können sich über diese Vorlage keine Sorgen machen, es ist offensichtlich wahr (persönlich getestet auf der nicht entarteten der möglichen Matrizen). Aber denken Sie daran: Beeilen Sie sich - Sie bringen die Leute zum Lachen . Überprüfen Sie also immer die Vorlagen, die Sie erstellt haben, damit Sie nicht wie zum Anfang springen.

5. Übersetzung des Algorithmus in Code

Der offensichtliche Schritt, alles, was Sie brauchen, ist oft schon in der Syntax der Sprache, und wenn nicht, stört Sie niemand, Klassen und Funktionen zu erstellen, um dieses Problem zu lösen, dann haben Sie einen Algorithmus. Da ich diesen Algorithmus als Teil eines Bildungsuniversitätsprogramms implementiert habe, konnte ich Octave nur für die Implementierung verwenden, sodass der gesamte Code, den ich Ihnen präsentiere, in seiner Syntax vorliegt (er ist Python sehr ähnlich, daher werde ich sein Highlight für die Formatierung verwenden):

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. Suchen Sie nach fehlgeschlagenen Tests

Sie sollten immer versuchen, Ihren Code zu "brechen". Hier gibt es (offensichtlich) keinen vollständigen „Schutz vor dem Narren“, aber ich habe die Annahme zugrunde gelegt, dass die anfänglich korrekte Matrix eingeführt wird.

In diesem Schritt sollten Sie alle möglichen Fehler und Ungenauigkeiten in Ihrem Code finden, wodurch auch die Verzerrung des konstruierten Algorithmus aufgedeckt werden kann. Daher sollten Sie hier so viele Auslassungen ausprobieren, wie möglich gewesen wären.

7. Debuggen Sie fehlgeschlagene Tests

Die logischste und wahrscheinlich erwartete der Schritte. Der Code muss verzerrt und der Algorithmus korrigiert werden. Hier gibt es nichts mehr hinzuzufügen.

Fazit

Ich kann sagen, dass es unwahrscheinlich ist, dass ich diesen Ansatz zur Lösung von Problemen jemals ernst nehmen würde, wenn ich nicht schläfrig wäre. Es lohnt sich jedoch, auf diese Methode zu achten - sie ist kurz und all ihre Mühsal besteht nur darin, dass sie angewendet werden muss.

Hinweis

Dank der Lehrbücher zur linearen Algebra für das Material zur Lösung des Problems.