Mide siete veces: corta una vez o usa el dicho en la práctica

Me senté en el curso de Coursera. El curso estaba dirigido a principiantes en Java, y en uno de los tutoriales en video se planteó el tema 7 Pasos para resolver problemas .

Yo, con la conciencia tranquila, escuché el video tutorial, pensé para mí mismo, este negocio ha ido lejos y durante mucho tiempo.

El resto del curso fue fácil, relajado. Pero, en una de las asignaturas de la universidad, es decir, en la llamada "Programación científica", apareció la siguiente tarea:

Resolver un sistema de ecuaciones lineales. $$$Ax=b$usando la siguiente expansión de matriz $$$A$:

$$

$$A = LU,$$

Dónde $$$L$Es la matriz triangular inferior, y $$$U$Es la matriz triangular superior.

El tema del álgebra lineal, que tomamos en el 1er curso. Francamente, recordé los principios generales de las operaciones con matrices, vectores y el lugar santísimo: el método de Gauss. Si lo piensas bien con el cerebro, entonces no estudiamos ninguna descomposición de LU, pero el método de Google siempre ayuda. Rescatado, hasta este punto.

Encontré un algoritmo general para encontrar matrices $$$L$y $$$U$, pero a las tres y media de la mañana ningún café me dio la oportunidad de implementarlo adecuadamente (dado que codificamos allí en Octave). Como resultado, me asusté y decidí escuchar el inteligente proverbio.

1. Describe el problema a mano

Todo lo que te falta en la vida es entender cuál es realmente el problema. Tomemos un ejemplo del problema anterior y escríbalo en una hoja de papel. En el buen sentido, deben cumplirse las siguientes condiciones para la existencia de matrices$$$L$ y $$$U$:

- la matriz inversa debe existir$$$A$, Quiero decir $$$\exists{A^{-1}}$;
- todos los menores mayores no deben ser degenerados, es decir$$$\Delta_{(1,...,n)}\neq{0}$

Bueno, es por eso que al menos necesitamos una "prueba tonta", porque seguramente hay personas inteligentes que quieren usar la matriz que no es adecuada para nosotros. Pero por ahora, vamos a omitirlo.

El problema es claro para nosotros: encontrar matrices$$$L$ y $$$U$eso caerá bajo las condiciones anteriores. Después de haber tratado de buscar en Google los métodos de solución, es poco probable que pueda implementar correctamente el algoritmo la primera vez (si no es bueno en álgebra lineal). Después de pasar por muchos intentos, lo más probable es que desarrollemos una secuencia de acciones para resolver nuestro problema, y ​​luego procedemos al paso 2.

2. Describe lo que hiciste

Toma la matriz como ejemplo

$$

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

Ahora aplicamos nuestro método de Gauss y eliminamos los elementos adicionales en la línea 3, restando la primera línea, multiplicada por la relación del primer elemento de 3 líneas al primer elemento de 1 línea:

$$

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

Ahora, deshazte del segundo elemento de la línea 3 con una acción similar:

$$

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

Como resultado, obtenemos la matriz

$$

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

Y ahora, los coeficientes que encontramos (el resultado de la relación de elementos $$$\frac{{a_i}_j}{{a_j}_j}$) tomar los valores de la matriz $$$L$, y obten

$$

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

Mirando a través de la plantilla, ¿no es así?

3. Encontrar patrones

En esta etapa, lo más probable es que regrese a los pasos 1 y 2, porque la plantilla que no siempre encontró será verdadera para todos los casos. Pero nada, ya que no funcionó, sucederá después.

Entonces, en base a un ejemplo, podemos formular la siguiente plantilla de algoritmo / solución:

1. Definir una matriz cuadrada$$$A, n$orden
2. Establecer la matriz$$$L = I$dónde $$$I$- matriz de identidad $$$n$orden
3. Establecer la matriz$$$U = A$;
4. Aplicamos las siguientes transformaciones sucesivas a las matrices, siempre 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},$$

A $$$n = 3$obtenemos:

$$

$$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. Comprobación de la plantilla / algoritmo

Hay un algoritmo: ¡hay millones de matrices para probarlo! No puede preocuparse por esta plantilla, es obviamente cierto (probado personalmente en las matrices más no degeneradas posibles). Pero recuerda: date prisa, haces reír a la gente . Así que siempre verifique las plantillas que creó para que no continúe saltando como un demonio desde el principio.

5. Traducción del algoritmo a código

El paso obvio, todo lo que necesitas a menudo ya está en la sintaxis del lenguaje, y si no, nadie te molesta para crear clases y funciones para resolver este problema, entonces tienes un algoritmo. Como implementé este algoritmo como parte de un programa universitario educativo, solo pude usar Octave para la implementación, por lo que todo el código que les presento está en su sintaxis (es muy similar a Python, por lo que usaré su resaltado para formatear):

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. Búsqueda de pruebas fallidas

Siempre debe tratar de "romper" su código. Aquí (obviamente) no existe una completa "protección contra el tonto", pero tomé como base el supuesto de que se introducirá la matriz inicialmente correcta.

En este paso, debe encontrar todos los posibles errores, inexactitudes en su código, como resultado de lo cual también se puede revelar el sesgo del algoritmo construido. Por lo tanto, aquí debe probar tantas omisiones que se podrían haber hecho.

7. Depurar pruebas fallidas

El más lógico, y probablemente esperado de los pasos. El código debe estar sesgado y el algoritmo corregido. No hay nada más que agregar aquí.

Conclusión

Puedo decir que es poco probable que alguna vez tome en serio este enfoque para resolver problemas, si no fuera por mi estado de sueño. Pero vale la pena prestar atención a este método: es breve y toda su laboriosidad consiste solo en el hecho de que debe usarse.

Nota

Gracias a los libros de texto de álgebra lineal por el material para resolver el problema.