Elemento pivote

El pivote o elemento pivote es el elemento de una matriz o arreglo que un algoritmo (por ejemplo, eliminación gaussiana , algoritmo simplex , etc.) selecciona primero para realizar ciertos cálculos. En el caso de los algoritmos matriciales, generalmente se requiere que una entrada pivote sea al menos distinta de cero, y a menudo alejada de él; en este caso, encontrar este elemento se denomina pivoteo . El pivoteo puede ir seguido de un intercambio de filas o columnas para colocar el pivote en una posición fija y permitir que el algoritmo proceda correctamente, y posiblemente para reducir el error de redondeo. Se utiliza a menudo para verificar la forma escalonada de filas .

El pivoteo puede entenderse como el intercambio o la ordenación de filas o columnas en una matriz, y por lo tanto, puede representarse como la multiplicación por matrices de permutación . Sin embargo, los algoritmos rara vez mueven los elementos de la matriz, ya que esto consumiría demasiado tiempo; en su lugar, simplemente registran las permutaciones.

En general, el pivoteo añade más operaciones al coste computacional de un algoritmo. Estas operaciones adicionales a veces son necesarias para que el algoritmo funcione correctamente. Otras veces, resultan beneficiosas porque aportan estabilidad numérica al resultado final.

En el caso de la eliminación gaussiana, el algoritmo requiere que los elementos pivote no sean cero. Si un elemento pivote es cero, es necesario intercambiar filas o columnas. El sistema que se muestra a continuación requiere el intercambio de las filas 2 y 3 para realizar la eliminación.

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]}$

El sistema que resulta del pivoteo es el siguiente y permitirá que el algoritmo de eliminación y la sustitución hacia atrás generen la solución al sistema.

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]}$

Además, en la eliminación gaussiana suele ser conveniente elegir un elemento pivote con un valor absoluto elevado . Esto mejora la estabilidad numérica . El siguiente sistema se ve afectado drásticamente por el error de redondeo al realizar la eliminación gaussiana y la sustitución hacia atrás.

${\displaystyle \left[{\begin{array}{cc|c}0.00300&59.14&59.17\\5.291&-6.130&46.78\\\end{array}}\right]}$

Este sistema tiene la solución exacta de x ₁ = 10.00 y x ₂ = 1.000, pero cuando se realiza el algoritmo de eliminación y la sustitución hacia atrás utilizando aritmética de cuatro dígitos, el pequeño valor de un ₁₁ provoca que se propaguen pequeños errores de redondeo. El algoritmo sin pivoteo produce la aproximación de x ₁ ≈ 9873.3 y x ₂ ≈ 4. En este caso, es conveniente intercambiar las dos filas de modo que un ₂₁ quede en la posición de pivote.

${\displaystyle \left[{\begin{array}{cc|c}5.291&-6.130&46.78\\0.00300&59.14&59.17\\\end{array}}\right].}$

Considerando este sistema, el algoritmo de eliminación y la sustitución hacia atrás utilizando aritmética de cuatro dígitos dan como resultado los valores correctos x ₁ = 10,00 y x ₂ = 1,000.

En el pivoteo parcial , el algoritmo selecciona el elemento con el mayor valor absoluto de la columna de la matriz que se está considerando como pivote. Más específicamente, al reducir una matriz a la forma escalonada por filas, el pivoteo parcial intercambia filas antes de la reducción de la columna para que el pivote tenga el mayor valor absoluto en comparación con los elementos inferiores de la misma columna. El pivoteo parcial suele ser suficiente para reducir adecuadamente el error de redondeo.

Sin embargo, para ciertos sistemas y algoritmos, puede ser necesario el pivoteo completo (o pivoteo máximo) para lograr una precisión aceptable. El pivoteo completo intercambia filas y columnas para usar el elemento de mayor valor absoluto en la matriz como pivote. Generalmente, el pivoteo 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 suele verse contrarrestada por su menor eficiencia, excepto para las matrices más pequeñas. Por lo tanto, rara vez se utiliza. ^{[ 1 ]}

Otra estrategia, conocida como pivoteo de torre, también intercambia filas y columnas, pero solo garantiza que el pivote elegido sea simultáneamente la entrada más grande posible en su fila y la entrada más grande posible en su columna, en lugar de la más grande posible en toda la submatriz restante. ^{[ 2 ]} Cuando se implementa en computadoras seriales, esta estrategia tiene un costo esperado de solo aproximadamente tres veces el del pivoteo parcial y, por lo tanto, es más barata que el pivoteo completo. Se ha demostrado que el pivoteo de torre es más estable que el pivoteo parcial, tanto teórica como prácticamente.

Una variante de la estrategia de pivote parcial es el pivote escalado. En este enfoque, el algoritmo selecciona como elemento pivote la entrada de mayor valor relativo a las entradas de su fila. Esta estrategia es conveniente cuando las grandes diferencias de magnitud entre las entradas provocan la propagación de errores de redondeo. El pivote escalado debe utilizarse en sistemas como el que se muestra a continuación, donde las entradas de una fila varían considerablemente en magnitud. En el ejemplo siguiente, sería conveniente intercambiar las dos filas, ya que el elemento pivote actual (30) es mayor que 5,291, pero relativamente pequeño en comparación con las demás entradas de su fila. Sin el intercambio de filas en este caso, los errores de redondeo se propagarán como en el ejemplo anterior.

${\displaystyle \left[{\begin{array}{cc|c}30&591400&591700\\5.291&-6.130&46.78\\\end{array}}\right]}$

Una posición pivote en una matriz A es aquella que corresponde a un 1 al inicio de la fila en la forma escalonada reducida de A. Dado que esta forma es única, las posiciones pivote están determinadas de forma unívoca y no dependen de si se realizan o no intercambios de filas durante el proceso de reducción. Además, el pivote de una fila debe aparecer a la derecha del pivote de la fila superior en la forma escalonada .

Este artículo incorpora material de Pivoting on PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .

• RL Burden, JD Faires, Análisis numérico , 8.ª edición, Thomson Brooks/Cole, 2005. ISBN 0-534-39200-8
• GH Golub, CF Loan, Cálculos matriciales , 3.ª 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 cruzados: una nueva perspectiva sobre los algoritmos de pivote". Mathematical Programming, Series B. Artículos del  16.º Simposio Internacional sobre Programación Matemática celebrado en Lausana, 1997.  79 ( 1–3 ) : 369–395 . CiteSeerX 10.1.1.36.9373 . doi : 10.1007 / BF02614325 . MR 1464775. S2CID 2794181. Preimpresión Postscript .   
• Terlaky, Tamás; Zhang, Shu  Zhong (1993). "Reglas de pivote para programación lineal: una revisión de los desarrollos teóricos recientes". Annals of Operations Research . 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 . MR 1260019. S2CID 6058077 .