math - saber - ¿Cómo verificar si los vectores de tamaño m n son linealmente independientes?

vectores linealmente independientes en r2 (8)

Construya una matriz de los vectores (una fila por vector) y realice una eliminación gaussiana en esta matriz. Si cualquiera de las filas de la matriz se cancela, no son linealmente independientes.

El caso trivial es cuando m> n, en este caso, no pueden ser linealmente independientes.

Renuncia
Esto no es estrictamente una cuestión de programación, pero la mayoría de los programadores, tarde o temprano, tienen que lidiar con las matemáticas (especialmente el álgebra), por lo que creo que la respuesta podría resultar útil para otra persona en el futuro.

Ahora el problema
Estoy tratando de verificar si m vectores de dimensión n son linealmente independientes. Si m == n puedes simplemente construir una matriz usando los vectores y verificar si el determinante es! = 0. ¿Pero y si m <n?

¿Algún consejo?

Ver también este video conferencia .

Construye una matriz M cuyas filas son los vectores y determina el rango de M Si el rango de M es menor que m (el número de vectores), entonces hay una dependencia lineal. En el algoritmo para determinar el rango de M puede detener el procedimiento tan pronto como obtenga una fila de ceros, pero ejecutar el algoritmo hasta su finalización tiene la bonanza adicional de proporcionar la dimensión del conjunto de expansión de los vectores. Ah, y el algoritmo para determinar el rango de M es meramente eliminación gaussiana.

Cuida la inestabilidad numérica. Ver la advertencia al comienzo del capítulo dos en Recetas Numéricas.

Si m<n , tendrá que hacer alguna operación con ellos (hay múltiples posibilidades: eliminación gaussiana, ortogonalización, etc., casi cualquier transformación que pueda usarse para resolver ecuaciones) y comprobar el resultado (por ejemplo, eliminación gaussiana). => cero fila o columna, ortogonalización => vector cero, SVD => cero número singular)

Sin embargo, tenga en cuenta que esta pregunta es una pregunta incorrecta para un programador, y este problema es un problema grave que un programa debe resolver. Esto se debe a que cada conjunto linealmente dependiente de n<m vectores tiene un conjunto diferente de vectores linealmente independientes cercanos (por ejemplo, el problema es numéricamente inestable)

Si la potencia de cálculo no es un problema, probablemente la mejor manera es encontrar valores singulares de la matriz. Básicamente, necesita encontrar valores propios de M''*M y observar la relación entre el más grande y el más pequeño. Si la relación no es muy grande, los vectores son independientes.

Otra forma de comprobar que m vectores de fila son linealmente independientes, cuando se los coloca en una matriz M de tamaño mxn, es calcular

det(M * M^T)

es decir, el determinante de una matriz cuadrada mxm. Será cero si y solo si M tiene algunas filas dependientes. Sin embargo, la eliminación gaussiana debería ser, en general, más rápida.

He estado trabajando en este problema estos días.

Previamente, he encontrado algunos algoritmos con respecto a la eliminación Gaussiana o Gaussiana-Jordania, pero la mayoría de esos algoritmos solo se aplican a la matriz cuadrada, no a la matriz general.

Para solicitar la matriz general, una de las mejores respuestas podría ser esta: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

Puede encontrar pseudocódigo y código fuente en varios idiomas. En cuanto a mí, transformé el código fuente de Python en C ++, hace que el código C ++ proporcionado en el enlace de arriba sea de alguna manera complejo e inapropiado de implementar en mi simulación.

Espero que esto te ayude, y buena suerte ^^

Lo siento, hombre, mi error ...

El código fuente proporcionado en el enlace anterior resulta ser incorrecto, al menos el código python que he probado y el código C ++ que he transformado no genera la respuesta correcta todo el tiempo. (Mientras que para el ejemplo en el enlace de arriba, el resultado es correcto :) -)

Para probar el código python, simplemente reemplace el mtx con

[30,10,20,0],[60,20,40,0]

y el resultado devuelto sería como:

[1,0,0,0],[0,1,2,0]

Sin embargo, tengo una forma de salir de esto. Es solo esta vez que transformé el código fuente de matalb de la función rref en C ++. Puede ejecutar matlab y usar el comando type rref para obtener el código fuente de rref .

Solo tenga en cuenta que si está trabajando con un valor realmente grande o un valor realmente pequeño, asegúrese de usar el tipo de datos long double en c ++. De lo contrario, el resultado será truncado e inconsistente con el resultado de matlab.

He estado realizando grandes simulaciones en ns2, y todos los resultados observados son sólidos. Espero que esto te ayude a ti y a cualquier otro que haya encontrado el problema ...

Una manera muy simple, que no es la más eficiente computacionalmente, es simplemente eliminar filas aleatorias hasta m=n y luego aplicar el truco determinante.

m < n : eliminar filas (acortar los vectores) hasta que la matriz sea cuadrada, y luego
m = n : verifica si el determinante es 0 (como dijiste)
m < n (el número de vectores es mayor que su longitud): son linealmente dependientes (siempre).

La razón, en resumen, es que cualquier solución al sistema de ecuaciones de mxn también es una solución para el sistema de ecuaciones nxn (estás tratando de resolver Av=0 ). Para una mejor explicación, mira Wikipedia , que lo explica mejor que yo.