Meça sete vezes - corte uma vez ou use o ditado na prática

Sentei-me no curso Coursera. O curso foi voltado para iniciantes em Java e, em um dos tutoriais em vídeo, foi abordado o tópico 7 Etapas para Solução de Problemas .

Eu, com a consciência limpa, ouvi o vídeo tutorial, pensei comigo mesmo: esse negócio está longe e há muito tempo.

O resto do curso foi fácil, relaxado. Mas, em uma das disciplinas da universidade, nomeadamente na chamada "Programação Científica", apareceu a seguinte tarefa:

Resolver um sistema de equações lineares $$$Ax=b$usando a seguinte expansão de matriz $$$A$:

$$

$$A = LU,$$

Onde $$$L$É a matriz triangular inferior e $$$U$É a matriz triangular superior.

O tópico de álgebra linear, que abordamos no 1º curso. Francamente, lembrei-me dos princípios gerais de operações com matrizes, vetores e o santo dos santos - o método de Gauss. Se você pensa sobre isso com o cérebro, não estudamos nenhuma decomposição da LU, mas o método “google” sempre ajuda. Resgatado, até este ponto.

Encontrei um algoritmo geral para encontrar matrizes $$$L$e $$$U$, mas às três e meia da manhã nenhum café me deu a oportunidade de implementá-lo adequadamente (já que codificamos o código no Octave). No final, eu surtei, e decidi, no entanto, ouvir o provérbio habilmente nomeado.

1. Descreva o problema manualmente

Tudo o que falta na vida é entender qual é realmente o problema. Vamos pegar um exemplo do problema acima e escrevê-lo em um pedaço de papel. De uma maneira boa, as seguintes condições para a existência de matrizes devem ser satisfeitas$$$L$ e $$$U$:

- a matriz inversa deve existir$$$A$, Quero dizer $$$\exists{A^{-1}}$;
- todos os menores menores não devem ser degenerados, ou seja,$$$\Delta_{(1,...,n)}\neq{0}$

Bem, é por isso que pelo menos precisamos de um "teste de idiota", porque certamente existem pessoas inteligentes que desejam usar a matriz que não é adequada para nós. Mas, por enquanto, vamos omitir.

O problema está claro para nós: encontre matrizes$$$L$ e $$$U$que cairá nas condições acima. Tendo tentado pesquisar no google os métodos da solução, é improvável que você consiga implementar corretamente o algoritmo na primeira vez (se você não é bom em álgebra linear). Depois de realizar várias tentativas, provavelmente desenvolveremos alguma sequência de ações para resolver nosso problema e, em seguida, prosseguiremos para a etapa 2.

2. Descreva o que você fez

Tome a matriz como exemplo

$$

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

Agora aplicamos nosso método Gauss a ele e nos livramos dos elementos extras na linha 3, subtraindo a primeira linha dele, multiplicada pela razão do primeiro elemento de 3 linhas com o primeiro elemento de 1 linha:

$$

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

Agora, livre-se do segundo elemento da linha 3 com uma ação semelhante:

$$

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

Como resultado, obtemos a matriz

$$

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

E agora, os coeficientes que encontramos (o resultado da relação de elementos $$$\frac{{a_i}_j}{{a_j}_j}$) pega os valores da matriz $$$L$, e pegue

$$

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

Olhando através do modelo, não é?

3. Encontrar padrões

Nesse estágio, provavelmente, você retornará às etapas 1 e 2, porque o modelo que você nem sempre encontrou será verdadeiro para todos os casos. Mas nada, como não deu certo, acontecerá a seguir.

Portanto, com base em um exemplo, podemos formular o seguinte modelo de algoritmo / solução:

1. Defina uma matriz quadrada$$$A, n$ordem;
2. Defina a matriz$$$L = I$Onde $$$I$- matriz de identidade $$$n$ordem;
3. Defina a matriz$$$U = A$;
4. Aplicamos as seguintes transformações sucessivas às matrizes, desde 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},$$

At $$$n = 3$Nós temos:

$$

$$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. Verificando o modelo / algoritmo

Existe um algoritmo - existem milhões de matrizes para testá-lo! Você não pode se preocupar com esse modelo, é obviamente verdade (testado pessoalmente na mais não-degenerada das matrizes possíveis). Mas lembre-se: apresse-se - você faz as pessoas rirem . Portanto, sempre verifique os modelos que você criou para não continuar pulando como um maldito desde o início.

5. Tradução do algoritmo em código

A etapa óbvia, tudo que você precisa já está na sintaxe da linguagem e, se não, ninguém o incomoda para criar classes e funções para resolver esse problema, então você tem um algoritmo. Como eu implementei esse algoritmo como parte de um programa universitário educacional, eu só poderia usar o Octave para implementação, portanto, todo o código que apresento está em sua sintaxe (é muito semelhante ao Python, então usarei seu destaque para formatação):

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. Procure por testes com falha

Você deve sempre tentar "quebrar" seu código. Aqui (obviamente) não existe uma "proteção completa do tolo", mas tomei como base a suposição de que a matriz inicialmente correta será introduzida.

Nesta etapa, você deve encontrar todos os erros possíveis, imprecisões no seu código, como resultado dos quais o viés do algoritmo construído também pode ser revelado. Portanto, aqui você deve experimentar o máximo de omissões que poderiam ter sido feitas.

7. Testes com falha na depuração

A mais lógica e provavelmente esperada das etapas. O código deve ser tendencioso e o algoritmo corrigido. Não há mais nada a ser adicionado aqui.

Conclusão

Posso dizer que é improvável que eu levaria a sério essa abordagem para resolver problemas, se não fosse o meu estado de sono. Mas vale a pena prestar atenção a esse método - é curto e toda a sua laboriosa consiste apenas no fato de que deve ser usado.

Nota

Graças aos livros de álgebra linear do material para resolver o problema.