El pivote o elemento pivote es el elemento de una matriz , o una matriz , que se selecciona primero mediante un algoritmo (por ejemplo , eliminación gaussiana , algoritmo simplex , etc.), para realizar ciertos cálculos. En el caso de los algoritmos matriciales, normalmente se requiere que una entrada pivote sea al menos distinta de cero y, a menudo, distante de él; en este caso, encontrar este elemento se llama pivotar . El pivote puede ir seguido de un intercambio de filas o columnas para llevar el pivote a una posición fija y permitir que el algoritmo proceda con éxito y posiblemente para reducir el error de redondeo. A menudo se utiliza para verificar la forma escalonada de las filas .
Se puede pensar en pivotar como intercambiar o clasificar filas o columnas en una matriz y, por lo tanto, se puede representar como una multiplicación por matrices de permutación . Sin embargo, los algoritmos rara vez mueven los elementos de la matriz porque esto costaría demasiado tiempo; en su lugar, solo realizan un seguimiento de las permutaciones.
En general, la pivotación agrega más operaciones al costo computacional de un algoritmo. Estas operaciones adicionales a veces son necesarias para que el algoritmo funcione. Otras veces, estas operaciones adicionales valen la pena porque añaden estabilidad numérica al resultado final.
Ejemplos de sistemas que requieren pivotar
En el caso de la eliminación gaussiana, el algoritmo requiere que los elementos pivote no sean cero. Es necesario intercambiar filas o columnas en el caso de un elemento de pivote cero. El siguiente sistema requiere el intercambio de las filas 2 y 3 para realizar la eliminación.
El sistema que resulta de pivotar es el siguiente y permitirá que el algoritmo de eliminación y la sustitución hacia atrás produzcan la solución en el sistema.
Además, en la eliminación gaussiana, generalmente es deseable elegir un elemento pivote con un valor absoluto grande . Esto mejora la estabilidad numérica . El siguiente sistema se ve dramáticamente afectado por el error de redondeo cuando se realizan la eliminación gaussiana y la sustitución hacia atrás.
Este sistema tiene la solución exacta de x 1 = 10,00 y x 2 = 1,000, pero cuando el algoritmo de eliminación y la sustitución hacia atrás se realizan utilizando aritmética de cuatro dígitos, el valor pequeño de un 11 provoca que se propaguen pequeños errores de redondeo. El algoritmo sin pivotante rendimientos a la aproximación de x 1 ≈ 9873,3 y x 2 ≈ 4. En este caso es deseable que se intercambian las dos filas de manera que un 21 está en la posición de pivote
Considerando este sistema, el algoritmo de eliminación y la sustitución hacia atrás usando aritmética de cuatro dígitos arrojan los valores correctos x 1 = 10,00 y x 2 = 1,000.
Pivotaje parcial y completo
En el pivote parcial , el algoritmo selecciona la entrada con el valor absoluto más grande de la columna de la matriz que se está considerando actualmente como el elemento pivote. El pivotamiento parcial suele ser suficiente para reducir adecuadamente el error de redondeo. Sin embargo, para ciertos sistemas y algoritmos, es posible que se requiera un giro completo (o giro máximo) para una precisión aceptable. El pivote completo intercambia filas y columnas para usar el elemento más grande (por valor absoluto) en la matriz como pivote. Por lo general, el pivote completo no es necesario para garantizar la estabilidad numérica y, debido al costo adicional de buscar el elemento máximo, la mejora en la estabilidad numérica que proporciona generalmente se ve superada por su eficiencia reducida para todas las matrices, excepto las más pequeñas. Por lo tanto, rara vez se usa. [1]
Pivotaje escalado
Una variación de la estrategia de pivote parcial es el pivote escalado. En este enfoque, el algoritmo selecciona como elemento pivote la entrada que es más grande en relación con las entradas en su fila. Esta estrategia es deseable cuando las grandes diferencias de magnitud de las entradas conducen a la propagación del error de redondeo. El pivote escalado debe usarse en un sistema como el que se muestra a continuación, donde las entradas de una fila varían mucho en magnitud. En el ejemplo siguiente, sería deseable intercambiar las dos filas porque el elemento pivote actual 30 es mayor que 5.291 pero es relativamente pequeño en comparación con las otras entradas de su fila. Sin intercambio de filas en este caso, los errores de redondeo se propagarán como en el ejemplo anterior.
Posición de pivote
Una posición de pivote en una matriz, A, es una posición en la matriz que corresponde a un 1 que encabeza una fila en la forma escalonada de fila reducida de A. Dado que la forma escalonada de fila reducida de A es única, las posiciones de pivote se determinan de forma única y no dependen de si se realizan o no intercambios de filas en el proceso de reducción. Además, el pivote de una fila debe aparecer a la derecha del pivote en la fila anterior en forma escalonada de fila .
Referencias
Este artículo incorpora material de Pivoting en PlanetMath , que tiene la licencia Creative Commons Attribution / Share-Alike License .
- RL Burden, JD Faires, Análisis numérico , octava edición, Thomson Brooks / Cole, 2005. ISBN 0-534-39200-8
- GH Golub, CF Loan, Matrix Computations , 3.a edición, Johns Hopkins, 1996. ISBN 0-8018-5414-8 .
- Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos de pivote". Programación Matemática, Serie B . Artículos del 16º Simposio Internacional de Programación Matemática celebrado en Lausana, 1997. 79 (1-3): 369–395. CiteSeerX 10.1.1.36.9373 . doi : 10.1007 / BF02614325 . Señor 1464775 . Preimpresión posdata .
- Terlaky, Tamás; Zhang, Shu Zhong (1993). "Reglas de pivote para la programación lineal: una encuesta sobre los desarrollos teóricos recientes". Anales de investigación operativa . Degeneración en problemas de optimización. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658 . doi : 10.1007 / BF02096264 . ISSN 0254-5330 . Señor 1260019 .