3.3 Estrategias de pivoteo

3.3 Estrategias de pivoteo

Pivoteo y Complejidad

Cuando se aplica una operación elemental sobre una determinada fila para lograr un 0 en el coeficiente apq, con p = q + 1, q + 2, . . . ,N utilizo el elemento aqq de la matriz, y dicho elemento recibe el nombre de pivote. Los números mpq = apq/aqq se llaman multiplicadores y son los que se multiplican en la fila pivote para restarla de las correspondientes filas.



Al estar trabajando con sistemas de cómputos, cuya precisión está fijada de antemano, cada vez que se produce una operación aritmética se comete un error, en este caso de redondeo. Es por eso que la elección del pivote en cada paso la tomo por algún criterio no trivial de tal forma de tratar que dicho sea el menor posible.

Existen varias estrategias una de ellas consiste en la denominada estrategia de pivoteo parcial. La idea de este método consiste en lo siguiente: comparo el tamaño de todos los elementos de la columna de la fila q-´e sima (a partir del coeficiente que se encuentra en la diagonal) hasta la última fila, y me quedo con aquel elemento que tenga mayor valor absoluto. Una vez encontrada la fila que cumpla lo anterior, la llamo fila i-´e sima, aplico la operación de intercambio de filas entre la q-´e sima y la i-´e sima, de forma tal de lograr multiplicadores mpq menores a uno en valor absoluto.

Durante la derivación del algoritmo de la eliminación Gaussiana con sustitución hacia atrás, se encontró que para obtener un cero para el elemento pivote a(k) kk era necesario un intercambio de filas de la forma (Ek) $ (Ep) donde k + 1 · p · n era el entero más pequeño con a(k) pk 6= 0. En la práctica frecuentemente es deseable realizar intercambios de las filas que contienen a los elementos pivote, aun cuando estos no sean cero. Cuando los cálculos se realizan usando aritmética de dígitos finitos, como será el caso de las soluciones generadas con calculadora u ordenador, un elemento pivote que sea pequeño comparado con los elementos de debajo del en la misma columna puede llevar a un error de redondeo sustancial.

Pivoteo parcial

La onda con el pivoteo es hacer Gauss-Jordan pero eligiendo el mejor valor para hacer cuentas, de manera tal que los errores de las cuentas de la maquinita sean los menores. Así, se implementa un criterio para reordenar filas de manera tal que se queden los valores mayores al momento de dividir. El método consiste en elegir en la iteración i-ésima, el elemento de la columna que sea el de mayor valor absoluto entre todos los que están por encima de la diagonal, el menor valor de p≥i

|api|=maxi≤k≤n|aki|





Pivoteo parcial escalado

Cuando hay algún valor muy zarpado en las ecuaciones en comparación con el resto, el pivoteo solito no alcanza. Ahí hay que usar escalado. El escalado implica usar un factor de escala para cada fila, que se define

sk=max1≤j≤n|akj|

Eliminacion Gaussiana con Pivoteo




Eliminación gaussiana con pivoteo

Una técnica que se desarrollo para combatir los errores de truncamiento por ceros en la diagonal o los errores de redondeo por números cercanos a cero es la técnica de pivoteo parcial, esta técnica consiste en ubicar en la fila pivote el termino de mayor magnitud de tal forma que al realizar la división por dicho termino no se incurre en la violación de división por números cercanos a cero ni la división por cero.

Se define entonces como:

En cada etapa k se busca el mayor de los elementos de la columna k, que ocupan posiciones mayores o iguales que k, ocupe la posición akk, donde k<=i<=n. después se realiza el intercambio de filas. El proceso como tal es idéntico a eliminación gaussiana simple solo que antes de calcular los multiplicadores se realiza el pivoteo si es necesario. Al realizar el pivoteo se obtienen valores lo más pequeños posibles para los multiplicadores reduciendo así el error de redondeo.

Pseudocodigo eliminacion gaussiana con pivoteo Lea A, b Ab=[A b] Para k= 1 hasta  n – 1 Ab-à pivoteo(Ab,n,k)             Para i= k + 1 hasta n                         Mik= Abik/Abkk                                                                   Para j= k hasta n+1                                                Abik= Abij – mik. Abkj                                           Fin para                                Fin para Fin para X(n)=Ab(n,n+1)/Ab(n,n) para i=n-1hasta 1 paso -1     acum=0     para j= i+1 hasta n         acum = acum + Ab(i,j)*X(j)       Fin para     X(i)=(Ab(i,n+1)-acum)/Ab(i,i) Fin para Muestre A Muestre X