El algoritmo de Bareiss es un algoritmo para calcular el determinante o escalar una matriz con elementos enteros usando aritmética puramente entera. El nombre de E. Bareys . Cualquier división realizada por el algoritmo garantiza una división exacta (sin resto ). El método también se puede utilizar para calcular el determinante de una matriz con elementos reales (aproximados) , lo que elimina los errores de redondeo , excepto los errores ya presentes en la entrada.
El algoritmo general de Bareis difiere del algoritmo del mismo nombre para invertir matrices de Toeplitz .
En algunos países de habla hispana, el algoritmo también se conoce como algoritmo Bareis-Monante , debido a que René Mario Montante Pardo, profesor de la Universidad Autónoma de Nuevo León en México , popularizó el método entre los estudiantes.
La definición del determinante usa solo las operaciones de multiplicación, suma y resta . Obviamente, el determinante será entero si todos los elementos de la matriz son enteros. Sin embargo, calcular el determinante, ya sea puramente a partir de la definición o usando la fórmula de Leibniz , no es práctico porque requiere operaciones.
El método gaussiano tiene complejidad , pero usa división, lo que da como resultado errores de redondeo si se implementa con aritmética de punto flotante .
Los errores de redondeo se pueden evitar almacenando todos los números como fracciones en lugar de números de punto flotante. Sin embargo, el tamaño de cada elemento crece exponencialmente dependiendo del número de filas [1] .
Bareis planteó la cuestión de mantener las eliminaciones en números enteros, manteniendo el valor de los coeficientes intermedios lo suficientemente pequeño. Se han propuesto dos algoritmos [2] [3] :
Para completar, Bareis también propuso métodos de eliminación sin multiplicación, pero con fracciones [2] .
La estructura computacional de este algoritmo es un bucle triple simple, como en el método habitual de Gauss . Sin embargo, en este caso se modifica la matriz para que cada elemento contenga un principal principal menor [M] k, k . La corrección del algoritmo se muestra fácilmente por inducción en k [4] .
Si la suposición de que los principales menores no son iguales a cero resulta incorrecta, es decir , y algunos lo son, entonces podemos reorganizar las filas k-1 e i en lugares, cambiando el signo del valor final.
Durante la ejecución del algoritmo de Bareis, cualquier número entero calculado es el determinante de una submatriz de la matriz de entrada. Esto permite usar la desigualdad de Hadamard para limitar el tamaño de los números enteros. De lo contrario, el algoritmo de Bareis puede verse como una variante del método de Gauss , que requiere prácticamente el mismo número de operaciones aritméticas.
De ello se deduce que para una matriz con un valor máximo (absoluto) para cada elemento, el algoritmo de Bareis se ejecuta en O( n 3 ) operaciones elementales con una restricción sobre el valor absoluto de los valores intermedios. La complejidad computacional del algoritmo equivale entonces a usar aritmética elemental o usar multiplicaciones rápidas .
Métodos numéricos de álgebra lineal | |
---|---|
Conceptos clave | Número de punto flotante • Robustez computacional |
Tareas | Sistema de ecuaciones algebraicas lineales • Descomposición de matrices • Multiplicación de matrices ( algoritmos ) • Desdoblamiento de matrices • Matriz dispersa |
soporte de hardware | Caché del procesador • Búfer de traducción • Algoritmos insensibles a la caché • SIMD • Multiprocesamiento |
Software | MATLAB • BLAS • LAPACK • Comparación de bibliotecas de álgebra lineal • Comparación de bibliotecas de propósito general |