Ir al contenido principal

3.3 Estrategias de pivoteo


3.3 Estrategias de pivoteo
Resultado de imagen para 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

Comentarios

Publicar un comentario

Entradas populares de este blog

6.3 Métodos de pasos múltiples

6.3 Métodos de pasos múltiples Los métodos de un paso descritos en las secciones anteriores utilizan información en un solo punto xi para predecir un valor de la variable dependiente yi+1 en un punto futuro xi+1. Procedimientos alternativos, llamados métodos multipaso, se basan en el conocimiento de que una vez empezado el cálculo, se tiene información valiosa de los puntos anteriores y esta a nuestra disposición. La curvatura de las líneas que conectan esos valores previos proporciona información con respecto a la trayectoria de la solución. Los métodos multipaso que exploraremos aprovechan esta información para resolver las EDO. Antes de describir las versiones de orden superior, presentaremos un método simple de segundo orden que sirve para demostrar las características generales de los procedimientos multipaso. Observe la ecuación ec. 2  alcanza ) a expensas de emplear un tamaño de paso mas grande, 2h. Además...
Publicar un comentario
Leer más

6.2 Métodos de un paso: Método de Euler, Método de Euler mejorado y Método de Runge-Kutta

6.2 Métodos de un paso: Método de Euler, Método de Euler mejorado y Método de Runge-Kutta   Método de Euler El método de Euler es un procedimiento de integración numérica para resolver ecuaciones diferenciales ordinarias a partir de un valor inicial dado. El método de Euler es el más simple de los métodos numéricos para resolver un problema del siguiente tipo: Consiste en multiplicar los intervalos que van de x0 a xf en n subintervalos de ancho h; Osea: de manera que se obtiene un conjunto discreto de n+1 puntos: x0, x1, x2, ... , xn del intervalo de interés [x0,xf]. Para cualquiera de estos puntos de cumple que:  0<i<n. La condición inicial y(x0)=y0, representa el punto P0=(x0,y0) por donde pasa la curva solución de la ecuación del plantamiento inicial, la cual se denotará cmo F(x)=y. Ya teniendo el punto P0 se puede evaluar la primera derivada de F(x) en ese punto; por lo tanto: Con esta información se traza una recta, aquella que ...
Publicar un comentario
Leer más

2.1 Métodos de intervalos: Gráficos, Bisección y falsa posición

2.1 Métodos de intervalos: Gráficos, Bisección y falsa posición. El problema de obtener las soluciones o raíces de una ecuación algebraica o trascendente de la forma F(x)=0 se representa frecuentemente dentro el campo de la ingenierá. Se puede definir a la raíz de una ecuación como el valor de x que hace a f(x) = 0. Asi, que un método simple para obtener a la raíz de la ecuación f(x)=0, consiste en graficar la función y observar donde cruza el eje x. Por eso estos tipos de métodos, son llamados "Métodos Graficos" Debido a ello, el desarrollo de métodos que nos permiten solucionarlo es amplio; en esta unidad presentamos algunos para determinar las raíces reales o complejas de ecuaciones de este tipo, tales como: Método de Bisección o Bolzano El método de la bisección o también llamado Método de Bolzano, parte de una funcion F(x) y un intervalo [x1,x2] tal que F(x1) y F(x2) tienen signos contrarios. Si la función es continua en este intervalo, entonces existe una raíz de F(x)...
Publicar un comentario
Leer más