Mesurer sept fois - couper une fois ou utiliser le dicton dans la pratique

Je me suis assis sur le cours Coursera. Le cours était destiné aux débutants en Java, et dans l'un des didacticiels vidéo, le sujet 7 étapes pour résoudre les problèmes a été soulevé .

Moi, en toute conscience, j'ai écouté le tutoriel vidéo, je me suis dit, cette affaire est allée loin et depuis longtemps.

Le reste du cours a été facile, détendu. Mais, sur l'un des sujets de l'université, à savoir la soi-disant «Programmation scientifique», la tâche suivante est apparue:

Résoudre un système d'équations linéaires $$$Ax=b$en utilisant l'expansion de matrice suivante $$$A$:

$$

$$A = LU,$$

Où $$$L$Est la matrice triangulaire inférieure, et $$$U$Est la matrice triangulaire supérieure.

Le sujet de l'algèbre linéaire, que nous avons abordé au 1er cours. Franchement, je me suis souvenu des principes généraux des opérations avec des matrices, des vecteurs et le saint des saints - la méthode de Gauss. Si vous y réfléchissez avec le cerveau, alors nous n'avons étudié aucune décomposition LU, mais la méthode "google" aide toujours. Sauvé, jusqu'à ce point.

J'ai trouvé un algorithme général pour trouver des matrices $$$L$et $$$U$, mais à trois heures et demie du matin, aucun café ne m'a donné l'occasion de le mettre en œuvre correctement (étant donné que nous y avons codé sur Octave). En fin de compte, j'ai paniqué et j'ai décidé d'écouter néanmoins le proverbe intelligemment nommé.

1. Décrivez le problème à la main

Tout ce qui vous manque dans la vie, c'est de comprendre quel est réellement le problème. Prenons un exemple du problème ci-dessus et écrivons-le sur une feuille de papier. Dans le bon sens, les conditions suivantes d'existence de matrices doivent être remplies$$$L$ et $$$U$:

- la matrice inverse doit exister$$$A$, Je veux dire $$$\exists{A^{-1}}$;
- tous les mineurs majeurs ne doivent pas être dégénérés, c'est-à-dire$$$\Delta_{(1,...,n)}\neq{0}$

Eh bien, c'est pourquoi nous avons au moins besoin d'un «test de dupes», car il y a sûrement des gens intelligents qui veulent utiliser la matrice qui ne nous convient pas. Mais nous allons omettre cela pour l'instant.

Le problème est clair pour nous: trouver des matrices$$$L$ et $$$U$qui tombera dans les conditions ci-dessus. Après avoir essayé de google les méthodes de solution, il est peu probable que vous puissiez implémenter correctement l'algorithme la première fois (si vous n'êtes pas bon en algèbre linéaire). Après avoir traversé des tonnes de tentatives, nous développerons très probablement une séquence d'actions pour résoudre notre problème, puis nous passerons à l'étape 2.

2. Décrivez ce que vous avez fait

Prenons la matrice comme exemple

$$

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

Maintenant, nous lui appliquons notre méthode de Gauss et éliminons les éléments inutiles de la 3ème ligne, en soustrayant la première ligne de celle-ci, multipliée par le rapport du premier élément de 3 lignes au premier élément de 1 ligne:

$$

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

Maintenant, débarrassez-vous du deuxième élément de la ligne 3 avec une action similaire:

$$

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

En conséquence, nous obtenons la matrice

$$

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

Et maintenant, les coefficients que nous avons trouvés (le résultat du rapport des éléments $$$\frac{{a_i}_j}{{a_j}_j}$) prendre les valeurs de la matrice $$$L$, et obtenir

$$

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

En regardant à travers le modèle, n'est-ce pas?

3. Trouver des modèles

À ce stade, vous retournerez probablement aux étapes 1 et 2, car le modèle que vous n'avez pas toujours trouvé sera vrai pour tous les cas. Mais rien, car cela n'a pas fonctionné, cela se produira ensuite.

Ainsi, sur la base d'un exemple, nous pouvons formuler le modèle d'algorithme / solution suivant:

1. Définir une matrice carrée$$$A, n$e ordre;
2. Définissez la matrice$$$L = I$où $$$I$- matrice d'identité $$$n$e ordre;
3. Définissez la matrice$$$U = A$;
4. Nous appliquons les transformations successives suivantes aux matrices, à condition que$$$\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$on a:

$$

$$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. Vérification du modèle / algorithme

Il y a un algorithme - il y a des millions de matrices pour le tester! Vous ne pouvez pas vous inquiéter de ce modèle, c'est évidemment vrai (personnellement testé sur la plus non dégénérée des matrices possibles). Mais souvenez-vous: dépêchez-vous - vous faites rire les gens . Vérifiez donc toujours les modèles que vous avez créés afin de ne pas continuer à sauter comme un sacré au tout début.

5. Traduction de l'algorithme en code

L'étape évidente, tout ce dont vous avez besoin est souvent déjà dans la syntaxe du langage, et sinon, personne ne vous dérange pour créer des classes et des fonctions pour résoudre ce problème, alors vous avez un algorithme. Depuis que j'ai implémenté cet algorithme dans le cadre d'un programme universitaire universitaire, je ne pouvais utiliser que Octave pour l'implémentation, donc tout le code que je vous présente est dans sa syntaxe (il est très similaire à Python, donc j'utiliserai son surlignage pour le formatage):

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. Recherche d'échecs de tests

Vous devriez toujours essayer de «casser» votre code. Ici (évidemment) il n'y a pas de «protection complète contre le fou», mais j'ai pris comme base l'hypothèse que la matrice initialement correcte sera introduite.

À cette étape, vous devriez trouver toutes les erreurs, inexactitudes possibles dans votre code, à la suite desquelles le biais de l'algorithme construit peut également être révélé. Par conséquent, ici, vous devriez essayer autant d'omissions qui auraient pu être faites.

7. Déboguer les tests ayant échoué

La plus logique et probablement attendue des étapes. Le code doit être biaisé et l'algorithme corrigé. Il n'y a rien de plus à ajouter ici.

Conclusion

Je peux dire qu'il est peu probable que je prenne jamais au sérieux cette approche pour résoudre des problèmes, sinon pour mon état de somnolence. Mais il vaut la peine de prêter attention à cette méthode - elle est courte, et toute sa pénibilité consiste uniquement dans le fait qu'elle doit être utilisée.

Remarque

Merci aux manuels d'algèbre linéaire pour le matériel pour résoudre le problème.