¿Cómo comprobar si m-n de tamaño vectores son linealmente independientes?

Question

Aviso Legal
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 álgebra), por lo que creo que la respuesta podría llegar a ser útil a alguien más en el futuro.

Ahora el problema
Estoy tratando de comprobar si m vectores de dimensión n son linealmente independientes. Si m == n que sólo puede construir una matriz usando los vectores y comprobar si el determinante es! = 0. Pero lo que si m

¿Alguna pista?

---

esta conferencia de vídeo .

Answer 1

Construir una matriz de los vectores (una fila por cada vector), y realizar una Gaussian eliminación en esta matriz. Si cualquiera de las filas de la matriz anula, no son linealmente independientes.

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

Answer 2

Construir un M matriz cuyas filas son los vectores y determinar 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 grado de M puede detener el procedimiento tan pronto como se obtenga una fila de ceros, pero el funcionamiento del algoritmo para la terminación tiene la bonanza añadida de proporcionar la dimensión del conjunto generador de los vectores. Oh, y el algoritmo para determinar el rango de M es la eliminación meramente gaussiana.

Tenga cuidado de inestabilidad numérica. Ver la advertencia al comienzo del capítulo dos en Numerical Recipes.

Answer 3

Si m<n, que tendrá que hacer alguna operación sobre ellos (hay varias posibilidades: la eliminación de Gauss, ortogonalización, etc., casi cualquier transformación que se puede utilizar para resolver ecuaciones va a hacer) y comprobar el resultado (por ejemplo, Gauss. eliminación => fila cero o columna, ortogonalización => cero vector, SVD => cero número singular)

Sin embargo, tenga en cuenta que esta pregunta es una mala pregunta para un programador para preguntar, y este problema es un problema de mal para un programa para resolver. Eso es porque cada conjunto linealmente dependiente de vectores n<m tiene un conjunto diferente de vectores linealmente independientes en las inmediaciones (por ejemplo. El problema es numéricamente inestable)

Answer 4

He estado trabajando en este problema en estos días.

Anteriormente, he encontrado algunos algoritmos con respecto a la eliminación de Gauss o de Gauss-Jordan, pero la mayoría de esos algoritmos sólo se aplican a la matriz cuadrada, no matriz general.

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

Puede encontrar tanto pseudo-código y el código fuente en varios idiomas. En cuanto a mí, he transformado el código fuente de Python a C ++, hace que el código C ++ proporcionada en el enlace de arriba es de alguna manera compleja e inapropiado para poner en práctica en mi simulación.

Espero que esto le ayudará, y buena suerte ^^

Answer 5

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

Answer 6

Otra forma de comprobar que m fila vectores son linealmente independientes, cuando se pone 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 sólo si M tiene algunas filas dependientes. Sin embargo eliminación de Gauss debería ser en general más rápido.

Answer 7

Lo siento hombre, mi error ...

---

El código fuente proporcionado en el enlace anterior resulta ser incorrecta, al menos el código pitón he probado y el código C ++ He transformado no genera la respuesta correcta todo el tiempo. (Mientras que para el exmample en el enlace anterior, el resultado es :) correcta -)

Para probar el código Python, basta con sustituir 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 manera de salir de esto. Es sólo esta vez transformado el código fuente de la función matalb rref a C ++. Puede ejecutar MATLAB y utilizar el comando type rref para obtener el código fuente de rref.

Sólo cuenta de que si se está trabajando con un valor muy grande o muy pequeño valor, asegúrese de que el uso del tipo de datos long double en C ++. De lo contrario, el resultado será truncado e inconsistente con el resultado de MATLAB.

He estado conduciendo grandes simulaciones en ns2, y todos los resultados observados son sonido. espero que esto le ayudará y cualquier otro que hayan encontered el problema ...

Answer 8

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

• m < n: eliminar filas (hacen que los vectores más corto) hasta que la matriz es cuadrada, y después
• m = n: comprobar si el determinante es 0 (como usted ha dicho)
• m < n (el número de vectores es mayor que su longitud): son linealmente dependientes (siempre)
.

La razón, en definitiva, es que cualquier solución al sistema de ecuaciones m x n es también una solución al sistema de ecuaciones n x n (que está tratando de resolver Av=0). Para una mejor explicación, consulte Wikipedia , que lo explica todo mejor que pueda.