Gauss
|
Determinante
|
Gauss-Jordan
|
Matriz inversa
|
Cramer
|
Jacobi
|
Gauss-Seidel
|
Proyecciones sucesivas
|
Se desea resolver el sistema lineal AX = B. Si el sistema no tiene solución se dice que es incompatible (determinante de la matriz de coeficientes = 0). En caso contrario se dice que es compatible determinado (determinante de la matriz de coeficientes 0) o compatible indeterminado (determinante de la matriz de coeficientes = 0), en este caso se poseen infinitas soluciones
Los siguientes métodos consideran que la matriz es cuadrada y el determinante es no singular,
esto es det(A) != 0 (se lee determinante de A es distinto de cero)
Eliminación Gaussiana
Sea A una matriz de dimensión nxn, X y B nx1
Del sistema AX=B se toma la matriz de coeficientes A y la matriz solución B. Construyendose la matriz extendida AB de dimensión nx(n+1)
El algoritmo de Gauss o de eliminación Gaussiana trabaja con la matriz extendida AB
entradas A, B
//se construye la matriz extendida c = AB
para i <- 0 hasta n
para j <- 0 hasta n+1
si j <= n entonces
c(i,j) = a(i,j)
sino
c(i,j) = b(i)
fin
fin j
fin i
// luego
para k <-0 hasta n-1
para j <- k+1 hasta n
Del sistema AX=B se toma la matriz de coeficientes A y la matriz solución B. Construyendose la matriz extendida AB de dimensión nx(n+1)
El algoritmo de Gauss o de eliminación Gaussiana trabaja con la matriz extendida AB
entradas A, B
//se construye la matriz extendida c = AB
para i <- 0 hasta n
para j <- 0 hasta n+1
si j <= n entonces
c(i,j) = a(i,j)
sino
c(i,j) = b(i)
fin
fin j
fin i
// luego
para k <-0 hasta n-1
para j <- k+1 hasta n
m <- c(j,k)/c(k,k);
para i <- 0 hasta n+1
c(j,i) <- c(j,i) - c(k,i)*m;
fin i
fin j
fin k
para i <- 0 hasta n+1
c(j,i) <- c(j,i) - c(k,i)*m;
fin i
fin k
para i <- 0 hasta n*2
c(j,i) <- c(j,i) - c(k,i)*m;
fin i
fin k
Luego nos queda una matriz triangular superior de donde despejamos las incógnitas desde la ecuación de la última fila, siguiendo con la penultima, antepenultima y así, hasta llegar a la primera.
para i <- 0 hasta n+1
c(j,i) <- c(j,i) - c(k,i)*m;
fin i
fin k
para i <- 0 hasta n*2
c(j,i) <- c(j,i) - c(k,i)*m;
fin i
fin k
Luego nos queda una matriz triangular superior de donde despejamos las incógnitas desde la ecuación de la última fila, siguiendo con la penultima, antepenultima y así, hasta llegar a la primera.
Determinante
Luego de efectuar la eliminación Gaussiana se procede a multiplicar los elementos de la diagonal principal
det = 1
para i <- 0 hasta n
det = det * c(i,i)
fin i
Gauss-Jordan
El algoritmo de Gauss-Jordan trabaja con la matriz extendida ABentradas A, B
//se construye la matriz extendida c
para i <- 0 hasta n
para j <- 0 hasta n+1
si j <= n entonces
c(i,j) = a(i,j)
sino
c(i,j) = b(i)
fin
fin j
fin i
// luego
para k <-0 hasta n
piv <- c(k,k)
para i <- 0 hasta n+1
a(k,i) <- a(k,i)/piv
fin i
para j <- 0 hasta n
si ( j!=k) entonces
m <- c(j,k)/c(k,k);
fin fin j
Al finalizar el algoritmo el lado derecho de la matriz extendida se habrá convertido en una matriz Identidad y
los valores numéricos que quedan del lado derecho de la matriz extendida son la solución del sistema lineal considerado
Matriz inversa
Se construye la matriz extendida AI, siendo A la matriz de coeficientes e I la matriz identidad, esta debe ser de igual dimensión que A
//La matriz identidad posee unos (1) en la diagonal principal y el resto de los elementos son cero (0)
//se construye la matriz extendida c = AI
para i <- 0 hasta n
para j <- 0 hasta n+1
si j <= n entonces
cij = aij
sino
cij = Iij
fin
fin j
fin i
Luego se procede a aplicar el algoritmo de Gauss Jordan sobre la matriz extendida teniendo cuidado de modificar los limites en las iteraciones donde los subindices se mueven a través de las columnas. Observe que el limite para i es n*2 y no n+1
para k <-0 hasta n
piv <- c(k,k)
para i <- 0 hasta n*2
a(k,i) <- a(k,i)/piv
fin i
para j <- 0 hasta n
si ( j!=k) entonces
m <- c(j,k)/c(k,k);
fin fin j
Obtener la matriz inversa nos permite aplicar la siguiente ecuación matricial para resolver el sistema
// inv(A) se lee: inversa de A
AX = B, premultiplicamos ambos lados de la ecuación por la inversa de A, esto es
inv(A)AX = inv(A)B, como inv(A)A = I, nos queda
IX = inv(A)B, obteniendose así la solución del sistema
6.- JacobiEntradas A, B, Nmax, vector inicial y
mientras k < Nmax
para j <- 0 hasta n
sum <- 0
para i <-0 hasta n
si (i != j ) entonces
sum = sum + a(j,i)y(i)
fin
fin i
x(j) <- (b(j)-sum)/a(j,j)
fin j
para i <- 0 hasta n
y(i ) <- x(i)
fin i
fin
Camer
La solución de sistemas lineales mediante el método de Cramer se efectúa calculando determinantes.
Sea AX = B el sistema lineal que se desea resolver
X la matriz de dimensión (nx1) de incógnitas X0, X1, X2, X3, ..........., Xn
B la matriz solución de dimensión (nx1) de elementos b0, b1, b2, b3, ..........., bn
Definimos
D: determinante de la matriz de coeficientes A
Dx0: el determinante de la matriz que resulta de sustituir en la primera columna de la matriz A todos los elementos de la matriz solución B
Dx1: el determinante de la matriz que resulta de sustituir en la segunda columna de la matriz A todos los elementos de la matriz solución B
:
:
:
Dxn: el determinante de la matriz que resulta de sustituir en la columna (n+1) de la matriz A todos los elementos de la matriz solución B
Luego
X0 = Dx0/D
X1 = Dx1/D
:
:
:
Xn = Dxn/D
Gauss-Seidel
Entradas A, B, Nmax, vector inicial x
mientras k < Nmax
para j <- 0 hasta n
sum <- 0
para i <-0 hasta n
si (i != j ) entonces
sum = sum + a(j,i)x(i)
fin
fin i
x(j) <- (b(j)-sum)/a(j,j)
fin j
fin
Proyecciones Sucesivas
Se desea hallar el punto xi proyectado sobre el hiperplano CT X = b. Esto es, hallar xi+1.
La dirección normal al plano está dada por los coeficientes del hiperplano, es decir, el vector C. Entonces
xi+1 = xi + C (1)
Como xi Satisface CT X = b, tenemos
CT Xi = b (2)
Sustituyendo el lado derecho de la ecuación (1) en (2)
CT (xi + C) = b
Distribuimos y despejamos
CT xi + CT C = b
= (b - CT xi )/(CT C)
Finalmente el punto proyectado que estamos buscando se calcula mediante
xi+1 = xi +[(b - CT xi )/(CT C)]C
La idea consiste en proyectar un punto aleatorio sobre el primer hiperplano del sistema lineal considerado y luego proyectar el punto nuevo obtenido sobre el siguiente hiperplano del sistema, la proyección continua hasta proyectar sobre el último hiperplano del sistema. El proceso anterior se repite mientras no se alcance la solución o al menos mientras no se satisfaga el criterio de parada del algoritmo.
xi+1 = xi + C (1)
Como xi Satisface CT X = b, tenemos
CT Xi = b (2)
Sustituyendo el lado derecho de la ecuación (1) en (2)
CT (xi + C) = b
Distribuimos y despejamos
CT xi + CT C = b
= (b - CT xi )/(CT C)
Finalmente el punto proyectado que estamos buscando se calcula mediante
xi+1 = xi +[(b - CT xi )/(CT C)]C
La idea consiste en proyectar un punto aleatorio sobre el primer hiperplano del sistema lineal considerado y luego proyectar el punto nuevo obtenido sobre el siguiente hiperplano del sistema, la proyección continua hasta proyectar sobre el último hiperplano del sistema. El proceso anterior se repite mientras no se alcance la solución o al menos mientras no se satisfaga el criterio de parada del algoritmo.
