Resuelve el sistema usando el método de Jordan Gauss en línea con una solución. Método de Gauss-Jordan. Cómo encontrar la inversa de una matriz usando transformaciones elementales
4. Jordan - Método de Gauss.
El esquema con la elección del elemento principal es que el requisito de que los elementos diagonales akk, en los que se produce la división en el proceso de eliminación, no sean iguales a cero será reemplazado por uno más estricto: de todos los elementos del K -ésima columna, seleccione el módulo más grande y reorganice las ecuaciones para que este elemento termine en lugar del elemento acc. La elección del elemento principal y la reorganización asociada de las filas son necesarias en los casos en que en cualquier i-ésimo paso ACC = 0 o hay muy pocos ACC para los elementos restantes de la i-ésima columna: al dividir por un “pequeño” ” ACC, los ACC grandes obtendrán números con grandes errores absolutos, como resultado de lo cual la solución puede verse muy distorsionada.
A continuación se muestra un algoritmo para eliminar completamente las incógnitas o el método de Jordan-Gauss. La esencia del método es que, considerando la primera ecuación, contiene una incógnita con un coeficiente distinto de cero (en adelante, el elemento resolutivo), y dividiendo la primera ecuación por este coeficiente, usando la primera ecuación, esta incógnita está excluido de todas las ecuaciones excepto la primera. Habiendo elegido una incógnita en la segunda ecuación con un coeficiente diferente de cero y dividiendo la segunda ecuación por él, usando la segunda se eliminan otras incógnitas de todas las ecuaciones excepto la segunda, etc., es decir usando una ecuación, eliminan completamente una incógnita. El proceso continúa hasta que se hayan utilizado todas las ecuaciones.
Como se sabe, los sistemas de ecuaciones algebraicas lineales pueden tener una solución, muchas soluciones o los sistemas pueden ser inconsistentes. Con transformaciones elementales de los elementos de la matriz del sistema, estos casos se revelan de la siguiente manera:
1. En el proceso de eliminación, el lado izquierdo de la primera ecuación del sistema se vuelve cero y el lado derecho es igual a algún número distinto de cero. aquellos. 02+=bc0.
Esto significa que el sistema no tiene soluciones, ya que la I-ésima ecuación no puede ser satisfecha por ningún valor de las incógnitas;
2. Los lados izquierdo y derecho de la primera ecuación desaparecen. Esto significa que la primera ecuación es una combinación lineal de las demás; cualquier solución encontrada para el sistema la satisface, por lo que puede descartarse. En un sistema, el número de incógnitas es mayor que el número de ecuaciones y, por tanto, dicho sistema tiene muchas soluciones;
3. Después de utilizar todas las ecuaciones para eliminar las incógnitas, se obtiene una solución del sistema.
Por tanto, el objetivo final de la transformación de Jordan-Gauss es obtener de un sistema lineal dado
| a11x1 + a12x2 + … + a1nxn = b1,n+1 |
| a21x1 + a22x2 + … + a2nxn = b2,n+1 |
| am1x1 + am2x2 + … + amnxn = bm.n+1 |
Aquí x1, x2,…, xn son incógnitas que deben determinarse. Se supone que a11, a12, …, amn (coeficientes del sistema) y b1, b2, ... bm (términos libres) son conocidos. Los índices de los coeficientes (aij) del sistema indican los números de la ecuación (i) y la incógnita (j) en los que se encuentra este coeficiente, respectivamente.
El sistema (1) se llama homogéneo si todos sus términos libres son iguales a cero (b1 = b2 =… = bm = 0), en caso contrario se llama no homogéneo.
El sistema (1) se llama cuadrático si el número m de ecuaciones es igual al número n de incógnitas.
La solución al sistema (1) es un conjunto de n números c1, c2,…, cn, tal que al sustituir cada ci en lugar de xi en el sistema (1) se convierten todas sus ecuaciones en identidades.
El sistema (1) se llama consistente si tiene al menos una solución e inconsistente si no tiene ninguna solución.
Un sistema conjunto de tipo (1) puede tener una o más soluciones.
Las soluciones c1(1), c2(1), …, cn(1) y c1(2), c2(2), …, cn(2) de un sistema conjunto de tipo (1) se llaman diferentes si al menos uno de las igualdades se viola:
c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).
Un sistema simultáneo de la forma (1) se llama definido si tiene una solución única; si tiene al menos dos soluciones diferentes, entonces se llama indefinido. Si hay más ecuaciones que incógnitas, se dice que está sobredeterminada.
Resolvamos el siguiente sistema de ecuaciones:
Escribámoslo como una matriz de 3x4, donde la última columna es un miembro libre:
Hagamos lo siguiente:
· A la línea 2 agregue: -4 * Línea 1.
· A la línea 3 agregue: -9 * Línea 1.
· A la línea 3 agregue: -3 * Línea 2.
· Divida la línea 2 por -2
· A la línea 1 agregue: -1 * Línea 3.
· A la línea 2 agregue: -3/2 * Línea 3.
· A la línea 1 agregue: -1 * Línea 2.
En la columna de la derecha obtenemos la solución:
.
En el método de Newton se observa una aceleración de la convergencia del proceso de aproximación. 5. Método tangente (método de Newton) El método tangente, asociado con el nombre de I. Newton, es uno de los métodos numéricos más eficaces para resolver ecuaciones. La idea del método es muy sencilla. Tomemos el punto de la derivada x0 y escribamos en él la ecuación de la tangente a la gráfica de la función f(x): y=f(x0)+ f ¢(x) (x-x0) (1.5) Gráficas...
Soluciones a partir de métodos de cálculo numérico. Para determinar las raíces de una ecuación no se requiere el conocimiento de las teorías de los grupos de Abel, Galois, Lie, etc. ni el uso de terminología matemática especial: anillos, campos, ideales, isomorfismos, etc. Para resolver una ecuación algebraica de enésimo grado, solo necesitas la capacidad de resolver ecuaciones cuadráticas y extraer raíces de un número complejo. Las raíces se pueden determinar por...
Matemáticas de sustitución trigonométrica y prueba de la efectividad de la metodología de enseñanza desarrollada. Etapas de trabajo: 1. Desarrollo de un curso optativo sobre el tema: “Aplicación de la sustitución trigonométrica en la resolución de problemas algebraicos” con estudiantes de clases de matemáticas avanzadas. 2. Realización del curso optativo desarrollado. 3. Realización de una prueba diagnóstica...
... “se manifiesta” sólo en el proceso de transformación. Examinaremos la obviedad y el “velado” de la nueva variable utilizando ejemplos específicos en el segundo capítulo de este trabajo. 2. Posibilidades de utilizar el método de sustitución de incógnitas al resolver ecuaciones algebraicas En este capítulo, identificaremos las posibilidades de utilizar el método de sustitución de incógnitas al resolver ecuaciones algebraicas en estándar y no estándar...
Asociamos cada sistema de ecuaciones lineales con matriz extendida, obtenido sumando a la matriz A columna de miembros gratuitos:
Método Jordan-Gauss utilizado para resolver el sistema metro ecuaciones lineales con norte tipos desconocidos:
Este método consiste en que, mediante transformaciones elementales, se reduce un sistema de ecuaciones a un sistema de ecuaciones equivalente con una matriz de cierto tipo.
Realizamos las siguientes transformaciones elementales en las filas de la matriz extendida:
1. reorganizando dos cuerdas;
2. multiplicar una cadena por cualquier número distinto de cero;
3. agregar a una cadena otra cadena multiplicada por un número determinado;
4. descartando una fila cero (columna).
Ejemplo 2.11. Resuelve sistemas de ecuaciones lineales usando el método de Jordan-Gauss:
A) X 1 + X 2 + 2X 3 = -1
2X 1 - X 2 + 2X 3 = -4
4X 1 + X 2 + 4X 3 = -2
Solución: creemos una matriz extendida:
Iteración 1
Seleccione el elemento como elemento guía. Convirtamos la primera columna en una sola columna. Para hacer esto, suma la primera línea a la segunda y tercera línea, multiplicada por (-2) y (-4), respectivamente. Obtenemos la matriz:
Esto completa la primera iteración.
Iteración 2
Seleccione un elemento guía. Desde , dividimos la segunda línea por -3. Luego multiplicamos la segunda línea por (-1) y 3, respectivamente, y la sumamos con la primera y tercera línea, respectivamente. Consigamos la matriz
Iteración 3
Seleccione un elemento guía. Como , dividimos la tercera línea por (-2). Convirtamos la tercera columna a unidad. Para hacer esto, multiplica la tercera línea por (-4/3) y (-2/3) respectivamente y súmala con la primera y segunda línea, respectivamente. Consigamos la matriz
dónde incógnita 1 = 1, incógnita 2 = 2, incógnita 3 = -2.
Una vez completada la solución, en la etapa de entrenamiento es necesario realizar una verificación sustituyendo los valores encontrados en el sistema original, que en este caso deberían convertirse en igualdades correctas.
b) X 1 – X 2 + X 3 – X 4 = 4
X1 + X2 + 2X3 + 3X4 = 8
2X 1 +4X 2 + 5X 3 +10X 4 = 20
2Х 1 – 4Х 2 + Х 3 – 6Х 4 = 4
Solución: La matriz extendida tiene la forma:
Aplicando transformaciones elementales, obtenemos:
El sistema original es equivalente al siguiente sistema de ecuaciones:
X 1 – 3X 2 – 5X 4 = 0
2X 2 + X 3 + 4X 4 = 4
Últimas dos filas de la matriz. A(2) son linealmente dependientes.
Definición. Filas de matriz mi 1 , mi 2 ,…, yo soy son llamados linealmente dependiente, si hay números que no son simultáneamente iguales a cero, de modo que una combinación lineal de filas de la matriz sea igual a la fila cero:
Dónde 0 =(0, 0…0). Las filas de la matriz son linealmente independiente, cuando la combinación de estas filas es igual a cero si y solo si todos los coeficientes son iguales a cero.
En álgebra lineal, el concepto es muy importante. rango de matriz, porque juega un papel muy importante en la resolución de sistemas de ecuaciones lineales.
Teorema 2.3 (sobre el rango de la matriz). El rango de una matriz es igual al número máximo de sus filas o columnas linealmente independientes, a través de las cuales se expresan linealmente todas sus demás filas (columnas).
rango de matriz A(2) es igual a 2, porque en él, el número máximo de filas linealmente independientes es 2 (estas son las dos primeras filas de la matriz).
Teorema 2.4 (Kronecker-Kapeli). Un sistema de ecuaciones lineales es consistente solo si el rango de la matriz del sistema es igual al rango de la matriz extendida de este sistema.
1. Si el rango de la matriz de un sistema conjunto es igual al número de variables, es decir r = n, entonces el sistema tiene una solución única.
2. Si el rango de la matriz del sistema es menor que el número de variables, es decir r< n, то система неопределённая и имеет бесконечное множество решений.
En este caso, el sistema tiene 4 variables y su rango es 2, por lo tanto, tiene infinitas soluciones.
Definición. Dejar r< norte, r variables incógnita 1 , incógnita 2 ,…, xr son llamados básico, si el determinante de una matriz a partir de los coeficientes de ellas ( menor básico) es diferente de cero. Descansar n – r las variables se llaman gratis.
Definición.Solución sistema en el que todo n – r las variables libres son iguales a cero se llama básico.
Sistema conjunto metro ecuaciones lineales con norte variables ( metro< n ) tiene un número infinito de soluciones, entre las cuales hay un número finito de soluciones básicas que no exceden , donde .
En nuestro caso, es decir el sistema no tiene más de 6 soluciones básicas.
La solución general es:
X1 = 3X2 +5X4
X 3 = 4 – 2X 2 – 4X 4
Busquemos soluciones básicas. Para hacer esto, asumimos X 2 = 0, X 4 = 0, luego X 1 = 0, X 3 = 4. La solución básica tiene la forma: (0, 0, 4, 0).
Obtengamos otra solución básica. Para ello, tomamos X 3 y X 4 como incógnitas libres. Expresemos las incógnitas X 1 y X 2 a través de las incógnitas X 3 y X 4:
X 1 = 6 – 3/2X 2 – X 4
X 2 = 2 – 1/2X 3 – 2X 4.
Entonces la solución básica tiene la forma: (6, 2, 0, 0).
Ejemplo 2.12. Resuelve el sistema:
X1 + 2X2 – X3 = 7
2X 1 – 3X 2 + X 3 = 3
4X 1 + X 2 – X 3 = 16
Solución: Transformar la matriz extendida del sistema.
Entonces, la ecuación correspondiente a la tercera fila de la última matriz es contradictoria: dio como resultado la igualdad incorrecta 0 = –1, por lo tanto, este sistema es inconsistente. Esta conclusión también se puede obtener observando que el rango de la matriz del sistema es 2, mientras que el rango de la matriz del sistema extendido es 3.
Aquí podrás resolver un sistema de ecuaciones lineales gratis Método de Gauss en línea tamaños grandes en números complejos con una solución muy detallada. Nuestra calculadora puede resolver online tanto los habituales sistemas de ecuaciones lineales definidos como indefinidos mediante el método de Gauss, que tiene un número infinito de soluciones. En este caso, en la respuesta recibirás la dependencia de unas variables a través de otras libres. También puede comprobar la coherencia del sistema de ecuaciones en línea utilizando la solución gaussiana.
Sobre el método
Al resolver un sistema de ecuaciones lineales en línea utilizando el método gaussiano, se realizan los siguientes pasos.
- Escribimos la matriz extendida.
- De hecho, la solución se divide en pasos hacia adelante y hacia atrás del método gaussiano. El enfoque directo del método gaussiano es la reducción de una matriz a una forma escalonada. Lo contrario del método gaussiano es la reducción de una matriz a una forma especial por pasos. Pero en la práctica, es más conveniente poner a cero inmediatamente lo que se encuentra tanto arriba como debajo del elemento en cuestión. Nuestra calculadora utiliza exactamente este enfoque.
- Es importante tener en cuenta que al resolver mediante el método gaussiano, la presencia en la matriz de al menos una fila cero con un lado derecho distinto de cero (columna de términos libres) indica la incompatibilidad del sistema. En este caso, no existe una solución para el sistema lineal.
Para comprender mejor cómo funciona el algoritmo gaussiano en línea, ingrese cualquier ejemplo, seleccione "solución muy detallada" y vea su solución en línea.
Berezneva T.D.
Tema 7
“SISTEMAS DE ECUACIONES ALGEBRAICAS LINEALES.
MÉTODO GAUSS-JORDAN."
( Disciplina academica “Introducción al Álgebra Lineal y Geometría Analítica”)
SISTEMAS DE ECUACIONES ALGEBRAICAS LINEALES.
GAUSS – MÉTODO JORDAN.
Conceptos básicos
Una ecuación con n variables se llama lineal, si todas las variables ( incógnita 1 , incógnita 2 , … incógnita norte ) están incluidos en él elevado a 1. La forma general de dicha ecuación se escribe formalmente de la siguiente manera:
a 1 incógnita 1 + a 2 incógnita 2 + … a j incógnita j + … a norte incógnita norte = b, (*)
=
b.
Cantidades a j , j = 1,…, norte, Y b son conocidos (dados). Cantidades a j son llamados coeficientes para variables(para incógnitas), y b - miembro gratis.
Resolver una ecuación lineal (*)
,
,…,
) valores de las variables, que, cuando se sustituyen en la ecuación (es decir, cuando x j se reemplaza por 
delante de todos j
de
1a norte lo convierte en identidad. Destacamos que la solución a una ecuación con n variables es siempre un conjunto de n números y cada uno de esos conjuntos de n números representa uno solución. Obviamente, si al menos un coeficiente de las variables no es igual a 0, entonces la ecuación (*) tiene solución. De lo contrario, sólo existe una solución para b = 0, y todos estos son conjuntos arbitrarios de n números.
Consideremos simultáneamente m ecuaciones de la forma (*), es decir sistemametroecuaciones algebraicas lineales connortevariables. Sea cada i -ésima ecuación, i = 1,2,...,m, especificada por los coeficientes de las variables a i 1, a i 2,..., a in y el término libre b i, es decir parece
a i1 incógnita 1 + un i2 incógnita 2 + … + un yo incógnita j + … + a en incógnita norte = b i .
Entonces, en forma general, un sistema de m ecuaciones algebraicas lineales con n variables se puede escribir como:
a 11 incógnita 1 + un 12 incógnita 2 + … + un 1j incógnita j + … + un 1n incógnita norte = segundo 1
a 21 incógnita 1 + un 22 incógnita 2 + … + un 2j incógnita j + … + un 2n incógnita norte = segundo 2
………………………………………………………………………………
a i1 incógnita 1 + un i2 incógnita 2 + … + un yo incógnita j + … + un en incógnita norte = segundo i (1)
…………………………………………………
a m1 incógnita 1 + un m2 incógnita 2 + … + un mj incógnita j + … + un Minnesota incógnita norte = segundo metro
o, lo que es lo mismo,
=
b i ,
i
= 1,…,
metro.
Si todos los términos libres son iguales a cero, entonces el sistema (1) se llama homogéneo, es decir. parece
=
0,
i
= 1,…,
metro, (1
0
)
de lo contrario - heterogéneo. Sistema (1 0 ) es un caso especial del sistema general (1) .
Resolviendo el sistema de ecuaciones (1) llamado conjunto ordenado ( 
,
,…,
) valores de variables que, cuando se sustituyen en las ecuaciones del sistema (1) (es decir, cuando se reemplaza x j por 
,
j = 1,…,norte) Todo convierte estas ecuaciones en identidades, es decir 
=b i para todo i = 1,…,m.
El sistema de ecuaciones (1) se llama articulación, si tiene al menos una solución. De lo contrario el sistema se llama no conjunto.
Llamaremos al conjunto de todas las soluciones del sistema de ecuaciones (1) muchas de sus soluciones y denotamos X b (X 0 si el sistema es homogéneo). Si el sistema es inconsistente, entonces X b = 
.
La tarea principal de la teoría de sistemas de ecuaciones algebraicas lineales es descubrir si el sistema (1) es consistente y, de ser así, describir el conjunto de todas sus soluciones. Existen métodos para analizar dichos sistemas que permiten describir el conjunto de todas las soluciones en el caso de sistemas conjuntos o verificar la incompatibilidad en caso contrario. Uno de esos métodos universales es método de eliminación secuencial completa de incógnitas, o métodoGauss - Jordania , que estudiaremos en detalle.
Antes de pasar a la descripción del método Gauss-Jordan, presentamos una serie de definiciones y afirmaciones útiles para su uso posterior.
Los dos sistemas de ecuaciones se llaman equivalente, si tienen el mismo conjunto de soluciones. En otras palabras, toda solución de un sistema es solución de otro y viceversa. Todos los sistemas incompatibles se consideran equivalentes entre sí.
De las definiciones de equivalencia y del conjunto de soluciones a sistemas de la forma (1) se desprende inmediatamente la validez de los siguientes enunciados, que formularemos en forma de teorema.
Teorema 1.
Si el sistema (1) tiene una ecuación con el númerok,
1
k
metro, tal quea kj
= 0
j, Eso
La validez del teorema se vuelve obvia si observamos que la k-ésima ecuación tiene la forma
0 incógnita 1 + 0 incógnita 2 + … + 0 incógnita j + … + 0 incógnita norte = b k .
Teorema 2. Si a una ecuación del sistema (1) le sumas otra ecuación del mismo sistema, multiplicada por cualquier número, obtienes un sistema de ecuaciones equivalente al sistema original.
Prueba. Multipliquemos, por ejemplo, la segunda ecuación del sistema (1) por un número determinado 
y sumarlo a la primera ecuación. Como resultado de esta transformación, obtenemos el sistema (1'), en el que todas las ecuaciones, comenzando por la segunda, no han cambiado, y la primera tiene la siguiente forma
=
b 1
+
b 2
.
Obviamente, si algún conjunto ( 
,
,…,
) los valores de las variables convierte todas las ecuaciones del sistema (1) en identidades, luego convierte todas las ecuaciones del sistema (1') en identidades. Por el contrario, la solución (x' 1 ,x' 2 ,…,x' j , … ,x' n) del sistema (1') también es solución del sistema (1), ya que se obtiene el sistema (1) del sistema (1') usando una transformación similar, cuando la segunda ecuación del sistema (1') se suma a la primera ecuación del sistema (1'), multiplicada por el número (- 
).
La siguiente afirmación se demuestra exactamente de la misma manera.
Teorema 2'.Multiplicar una ecuación arbitraria del sistema (1) por cualquier número distinto de cero transforma el sistema (1) en un sistema de ecuaciones equivalente.
Los teoremas 2 y 2' dan dos tipos de transformaciones, a que fue sometido el sistema (1), quedando equivalente a:
A) multiplicación (o división) de una ecuación arbitraria del sistema (1) por cualquier número distinto de cero;
b) sumar (o restar) a una ecuación otra, multiplicada por un número determinado.
Tales transformaciones a) y b) se denominan transformaciones elementales sistema de ecuaciones (1).
Si se aplican transformaciones elementales al sistema de ecuaciones (1) varias veces, entonces el sistema resultante obviamente también será equivalente al original.
El sistema de ecuaciones (1) se puede escribir en forma tabular:
Una tabla rectangular de números compuesta de coeficientes a ij para las incógnitas del sistema (1) se llama matriz sistema (1) y se denota por A (tiene m filas yn columnas), la columna de términos libres se denota por b. Una tabla rectangular compuesta de coeficientes a ij para incógnitas y de la columna de términos libres b del sistema (1) se llama matriz extendida 
sistema (1) y se denota 
= (A,b). En la i –ésima fila de la matriz 
contiene todo famoso parámetros que caracterizan la i -ésima ecuación del sistema (1), i = 1,…, m. La j-ésima columna de la matriz A contiene todos los coeficientes de la incógnita x j encontrada en el sistema (1).
Los números a ij se llaman elementos de la matriz A. El elemento a ij está ubicado en la i -ésima fila y j -ésima columna de la matriz A. Se acostumbra decir que el elemento a ij está ubicado en la interseccióni- oh líneas yj- ésima columna de la matriz A. Si todos los elementos de una fila (columna) de la matriz A (excepto uno) son iguales a cero y un elemento distinto de cero es igual a uno, entonces dicha fila (columna) se llama soltero(soltero).
Las transformaciones elementales del sistema (1) corresponden a las siguientes transformaciones elementales de la tabla (2):
A) multiplicar (o dividir) todos los elementos de una fila arbitraria de la tabla (2) por cualquier número distinto de cero,
b) suma (o resta) a una línea (elemento por elemento) de otra línea, multiplicada por un número determinado.
Como resultado de cualquier transformación elemental obtenemos nueva mesa, en el que en lugar de la línea a la que se sumó (o se multiplicó por cualquier número distinto de cero), se escribenueva linea , y las líneas restantes (incluida la que se agregó) se escriben sin cambios. La nueva tabla corresponde al sistema de ecuaciones, equivalente al sistema original.
Aplicando transformaciones elementales, la tabla (2) y, en consecuencia, el sistema (1) se pueden simplificar de modo que sea fácil resolver el sistema original. El método propuesto se basa en esto.
Método de eliminación secuencial completa de incógnitas.
(Gauss - método de Jordan)
Método de eliminación secuencial completa de incógnitas, o Método Gauss-Jordan, es un método universal para analizar cualquier sistema (no se sabe de antemano cuáles, compatible o incompatible) de ecuaciones algebraicas lineales. Le permite resolver sistemas compatibles o verificar la incompatibilidad de sistemas incompatibles.
Observemos la diferencia fundamental entre el método propuesto para resolver sistemas de ecuaciones algebraicas lineales y el método para resolver, digamos, una ecuación cuadrática estándar. Se resuelve mediante fórmulas conocidas en las que las incógnitas se expresan mediante los coeficientes de la ecuación. En el caso de sistemas generales de ecuaciones algebraicas lineales, no tenemos tales fórmulas y las usamos para encontrar soluciones. método de iteración, o método iterativo, o método iterativo. Estos métodos no especifican fórmulas, sino una secuencia de acciones.
El método Gauss-Jordan es una implementación secuencial de la serie. mismo tipo de escalones grandes (oiteraciones ). Este método de iteración particular es uno de los muchos métodos de iteración propuestos. Para resolución de sistemas de ecuaciones algebraicas lineales de la forma (1). Consiste en etapa inicial, etapa principal y etapa final. El escenario principal contiene repetición. las iteraciones son conjuntos de acciones similares.
Sea un sistema específico de ecuaciones algebraicas lineales (1). Esto significa que conocidonorte , metro , a yo , b i , i = 1,…, metro ; j = 1,…, norte . Describamos el método propuesto para resolver este sistema.
Etapa inicial incluye la construcción de la tabla I (0) de tipo (2) y la selección en la misma elemento principal – cualquier distinto de cero coeficiente para variables de la tabla (2). La columna y la fila en cuya intersección hay un elemento principal se llaman principal. (Seleccione el elemento a i 0 j 0. Entonces i 0 es la fila principal, j 0 es la columna principal). Pasemos al escenario principal. Tenga en cuenta que el elemento principal a menudo se llama permisivo.
escenario principal consiste en repetir iteraciones del mismo tipo con números k = 1, 2,…. Describamos en detalle las iteraciones del método Gauss-Jordan.
Al comienzo de cada iteración, se conoce una determinada tabla del tipo I (2); un elemento principal (de resolución) y, en consecuencia, se seleccionan en ella una columna principal y una fila principal. Además, hay información sobre qué filas y columnas ya han sido principal. (Entonces, por ejemplo, después de la etapa inicial, es decir, en la iteración 1, I (0), se conocen el elemento principal (de resolución) a i 0 j 0 y la i 0.ª fila principal, j 0.ª columna principal).
Iteración (con número k ) consta de las siguientes acciones.
Conversión columna principal(es decir, la columna que contiene el elemento principal) en unidad con 1 en lugar del elemento principal restando secuencialmente elemento por elemento de la fila principal (es decir, la fila que contiene el elemento principal), multiplicada por algunos números, de las filas restantes de la tabla. Sí misma línea principal se transforma dividiéndolo por elementos por el elemento principal.
Se escribe una nueva tabla I (k), (k es el número de iteración), en la que todas las columnas que alguna vez han estado liderando son simples.
Se comprueba si es posible seleccionar en la tabla I (k) nuevo elemento líder (de resolución). Por definición esto cualquier elemento distinto de cero que se encuentra en la intersección de una fila y una columna que no fueron presentadores .
Si tal elección es posible, entonces la columna y la fila en cuya intersección hay un elemento principal (de resolución) se denominan principal. Luego, la iteración se repite con una nueva tabla I(k), es decir, Los pasos 1 – 3 se repiten con una nueva tabla I (k). En este caso, se construye una nueva tabla I (k +1).
Si esta prohibido seleccione un nuevo elemento principal y luego pase a la etapa final.
La etapa final. Se hacen r iteraciones, se obtiene una tabla I (r), formada por una matriz de coeficientes para las variables A (r) y una columna de términos libres b (r), y en ella esta prohibido seleccione un nuevo elemento principal, es decir el método se detuvo. Tenga en cuenta que el método obligatorio o parar por número finito de pasos, porque r no puede ser mayor que min(m,n).
¿Cuáles son las opciones para detener un método? ¿Qué quieres decir con "no puedes seleccionar un nuevo elemento principal"? Esto significa que después de la r-ésima iteración en la matriz A (r) de un nuevo sistema equivalente al sistema (1), ya sea
a) todas las líneas A (r) estaban adelantadas, es decir cada línea contiene una y exactamente una unidad, que no aparece en ninguna otra línea,
b) quedan filas en A (r) que consisten únicamente en ceros.
Consideremos estas opciones.
a) En este caso r = m, m 
norte. Al reorganizar las filas y renumerar las variables (es decir, reorganizar las columnas), la tabla I (r) se puede representar como
Destacamos que en la tabla (3) cada variable con un número i que no exceda r aparece en una sola fila. La tabla (3) corresponde a un sistema de ecuaciones lineales de la forma
x1 + 
=b (r) 1 ,
x2 + 
=b (r) 2 ,
………………………, (4)
x r + 
=b(r)r,
en el que cada variable con número i, no superiorr, se expresa únicamente a través de las variables x r +1,…,x n, coeficientes matriciales a (r) ij, j = r+1,…,n, y el término libre b (r) i, presentado en la tabla (3). A variables incógnita r +1 , … , incógnita norte no superponerse sin restricciones, es decir. Ellos puede tomar cualquier valor . Por tanto, una solución arbitraria al sistema descrito en la tabla (3), o, lo que es lo mismo, una solución arbitraria al sistema (4), o, lo que es lo mismo, una solución arbitraria al sistema (1), tiene la forma
x yo = b (r) yo - 
a (r) ij x j , i = 1,…,r = m; x j – cualquiera para j = (r+1),…,n. (5)
Entonces el conjunto de soluciones del sistema (1) se puede escribir como
X b = (x=(x 1 , … ,x n) : x i = b (r) i - 
a (r) ij x j para i = 1,…, r = m; x j – cualquiera para j =(r+1),…,n.).
b) En este caso r< m, и существует хотя бы одна строка k, k >r, (asumimos que el reordenamiento de filas y columnas es el mismo que en el punto a)) tal que a (r) kj = 0 para todo j. Entonces, si el término libre correspondiente b (r) k no igual 0, entonces la k-ésima ecuación no tiene solución y, por lo tanto, el sistema completo no tiene solución, es decir sistema (1) incompatible .
Si el b (r) k correspondiente es igual a 0, entonces la k-ésima ecuación es redundante y puede descartarse. Descartando todas estas ecuaciones, encontramos que el sistema (1) es equivalente al sistema de r ecuaciones con n variables, que se escriben después de r pasos usando una tabla de la forma (3), en la que todas las filas estaban al principio. Así, hemos llegado al caso a) considerado anteriormente y podemos escribir una solución de la forma (5).
El método Gauss-Jordan se describe en su totalidad. Para número finito de iteraciones el sistema de ecuaciones algebraicas lineales se resolverá (si es consistente) o será obvio que es inconsistente (si efectivamente es inconsistente).
Variables correspondientes a elementos principales (habilitadores), o estar de pie en las columnas principales, generalmente se llaman básico, y las variables restantes son gratis.
Prestemos atención a lo siguiente.
1) Cuando empezamos a resolver un sistema usando el método de Gauss-Jordan, es posible que no sepamos si este sistema es consistente o no. El método de Gauss-Jordan responderá esta pregunta en un número finito de iteraciones r. En el caso de un sistema conjunto, con base en la última tabla se escribe la solución general del sistema original. En este caso número de variables básicas necesariamente igual al número r de la última iteración, es decir número de iteraciones completadas. El número r siempre no excede min(m,n), donde m es el número de ecuaciones del sistema, y n - número de variables del sistema. si r< n, Eso ( norte – r) es igual al número de variables libres.
2) Al escribir una solución general No hay necesidad renumerar las variables, como se hizo para facilitar la comprensión al describir la Etapa Final. Esto se hace para una comprensión más clara.
3) Al resolver el sistema (1) usando el método de Gauss - Jordan básico Las variables solo serán variables correspondientes a las columnas que actuaron como principal, y viceversa, si en alguna iteración la columna actuó como columna principal, la variable correspondiente definitivamente estará entre las básicas.
4) Si la solución general del sistema (1) contiene al menos una variable libre, entonces este sistema tiene infinitamente muchos soluciones privadas, pero si no hay variables libres, entonces el sistema tiene una solución única que coincide con la solución general.
5) Los elementos principales se pueden seleccionar de forma diferente en cada iteración. Lo único importante es que estos son coeficientes distintos de cero ubicados en la intersección de una fila y una columna que antes no eran principales. Varias opciones elementos principales pueden dar varias entradas muchas soluciones. Sin embargo, el conjunto de soluciones en sí es el mismo para cualquier notación.
Expliquemos el funcionamiento del método con ejemplos.
Ejemplo I. Resuelve el siguiente sistema de ecuaciones algebraicas lineales.
2x 1 – 3x 2 + 3x 3 +5x 4 = -1,
3x 1 + 4x 2 - 2 veces 3 + 6x 4 = 2, (6)
5 incógnita 1 – 4 incógnita 2 + 6 incógnita 3 + 10 incógnita 4 = 2
por el método de eliminación secuencial completa de incógnitas (método de Gauss-Jordan).
Etapa inicial. Primero, escribimos el sistema de ecuaciones (6) en una forma más conveniente: en forma de tabla I (0).
Como se sabe, el método de Jordan-Gauss, también conocido como método de eliminación secuencial de incógnitas, es una modificación del método de Gauss para la resolución de sistemas de ecuaciones algebraicas lineales (SLAE).
El método se basa en transformaciones elementales (transformar el sistema en uno equivalente), que incluyen:
- sumar a ambos lados de una ecuación de un sistema otra ecuación del mismo sistema, multiplicada por un número distinto de cero;
- reorganizar ecuaciones en el sistema;
- eliminación del sistema de ecuaciones de la forma 0 = 0.
A diferencia del método gaussiano, en cada paso se elimina una variable de todas las ecuaciones menos una.
El paso del método es el siguiente:
- seleccionar una incógnita en la siguiente ecuación con un coeficiente diferente de cero (elemento de resolución);
- dividir la ecuación seleccionada por el elemento de resolución;
- utilizando la ecuación seleccionada, excluya la incógnita en el elemento de resolución de todas las demás ecuaciones;
- en el siguiente paso, se excluye de manera similar otra incógnita de todas las ecuaciones excepto una;
- el proceso continúa hasta que se hayan utilizado todas las ecuaciones.
Puedes algoritmarlo así:
Para el SLAE en forma matricial A*x=b (matriz A de dimensión m*n, no necesariamente cuadrada), se compila la siguiente tabla:
El elemento de resolución a r,s ≠0 se selecciona en la tabla, luego r es la fila de resolución, s es la columna de resolución.
La transición a la siguiente tabla se realiza según las reglas:
1. Se calculan los elementos de la fila de resolución: a" r,j =a r,j /a r,s - es decir, la fila r de la tabla se divide por el elemento de resolución;
2. todos los elementos de la columna de resolución, excepto ar,s igual a uno, se vuelven iguales a cero;
3. Los elementos fuera de la fila y columna permisivas se calculan utilizando la fórmula que se muestra a continuación:
Es fácil evitar confusiones cuando ves que el numerador de esta fórmula es similar al cálculo del determinante de una matriz de 2 por 2.
4. En el cálculo manual, el valor de la última columna de control se compara con la suma de los elementos anteriores de la fila. Si los valores no coinciden, se deben buscar errores en esta línea. Para cálculos automatizados, se puede omitir la columna de control.
Son posibles los siguientes casos:
1. En el proceso de eliminación, el lado izquierdo de la ecuación del sistema se convierte en 0 y el lado derecho b≠0, entonces el sistema no tiene solución.
2. Se obtiene la identidad 0 = 0: la ecuación es una combinación lineal del resto y la línea de ceros se puede eliminar del sistema.
3. Después de usar todas las ecuaciones para eliminar las incógnitas, la tabla contiene la solución deseada o muestra la inconsistencia del sistema de restricciones.
Programemos el método en Excel usando una fórmula, que no debería ser demasiado difícil de cambiar. Por ejemplo, para resolver SLAE
Llenemos las celdas de la hoja de A1 a D4 inclusive con los coeficientes del sistema, seleccionemos el elemento de resolución a 1,1 =1, y hagamos el primer paso del método en la celda A6, donde ingresaremos la fórmula “universal” para la transformada de Jordan-Gauss:
SI(FILA($A$1)=FILA(A1);A1/$A$1;
SI(COLUMNA($A$1)=COLUMNA(A1),0,(A1*$A$1-
INDIRECTO(DIRECCIÓN(FILA(A1),COLUMNA($A$1)))*
INDIRECTO(DIRECCIÓN(FILA($A$1),COLUMNA(A1)))/$A$1))
En el siguiente paso, el elemento de resolución podría ser, por ejemplo, un 2,2 =1 (celda B7). Lo único que debemos hacer es copiar la fórmula de A6 a A11 (la dejamos en una línea vacía para separar visualmente los pasos del método), ingresar al modo de edición de fórmula (hacer doble clic en una celda o seleccionarla y presionar la tecla F2 tecla) y corrija (arrastre con cuidado el mouse fuera del borde) todos los enlaces fijados desde la celda A1 a B7.
Por supuesto, puede reemplazar el enlace fijado $A$1 en todas partes de la fórmula con una construcción como INDIRECTO(CELDA), que forma una dirección de enlace dinámico. Digamos, INDIRECTO(F8), y en la celda F8 la dirección de la celda del elemento de resolución se generará automáticamente de acuerdo con el número de fila y columna especificado por el usuario. Luego, para estos números de fila y columna tendrás que proporcionar celdas separadas, por ejemplo, así:
Por desgracia, todo esto no dará nada: en lugar de $A$1, simplemente tendremos que corregir INDIRECT($F$8) en la fórmula y luego arrastrar y soltar la misma cantidad de enlaces al copiar la fórmula. Además, también será necesario verificar la validez de los números de fila y columna ingresados “manualmente” (al menos como en la figura), por lo que no multiplicaremos entidades.
Puede ver el método en acción en las dos primeras hojas del archivo Excel adjunto (2 ejemplos diferentes).
Un método tan universal para resolver problemas de optimización lineal como método simplex. Sus descripciones suelen ser aterradoras, largas y sobrecargadas de teoremas. Intentemos hacer una descripción simple y desarrollar un algoritmo adecuado para el cálculo en Excel. De hecho, el método simplex ya está integrado en el complemento estándar Analysis Package y no es necesario programarlo "manualmente", por lo que nuestro código tiene un valor bastante educativo.
Primero, un mínimo de teoría.
Si los vectores columna del SLAE son linealmente independientes, las variables correspondientes son básico, y el resto - gratis. Por ejemplo, en SLAU
las variables x 2 y x 4 son básicas y x 1 y x 3 son libres. Las variables básicas son independientes entre sí y las libres se pueden convertir, por ejemplo, en ceros y obtener (x 2 =2, x 4 =1) – solución básica sistemas.
Eligiendo diferentes elementos de resolución, es posible obtener soluciones de SLAE con diferentes bases. Cualquier solución básica no negativa de un SLAE se llama secundario.
El método simplex proporciona una transición de una solución de referencia a otra hasta que se logra óptimo solución que da la función objetivo mínima.
El algoritmo del método simplex es el siguiente:
1. El problema LP se transforma a forma canónica:
Esto siempre se puede hacer de la siguiente manera: al problema escrito en la formulación estándar
se agregan otros adicionales variables del balance, cuyo número corresponde al número de restricciones de desigualdad m (no se tienen en cuenta las restricciones a la no negatividad de los valores de las incógnitas). Después de esto, las desigualdades con el signo “≤” se convierten en igualdades, por ejemplo, un sistema de restricciones de la forma
2*x1 +3*x2 ≤20
3*x 1 +x 2 ≤15
4*x1≤16
3*x2≤12
x1, x2 ≥0
tomará la forma
2*x 1 +3*x 2 +x 3 =20
3*x 1 +x 2 +x 4 =15
4*x 1 +x 5 =16
3*x 2 +x 6 =12
x 1 ,x 2 ,...,x 6 ≥0
Es decir, el significado "económico" de las variables del balance es muy simple: son los "restos" de recursos no utilizados de cada tipo.
Si en el problema original no se buscaba un mínimo, sino un máximo, la función objetivo Z será reemplazada por Z 1 = -Z. Las soluciones a los problemas coinciden, siendo min Z = - max Z 1 . Por ejemplo, objetivo
Z(x 1 ,x 2)=2*x 1 +5*x 2 (máx.)
reescrito como
Z 1 (x 1 ,x 2)=-2*x 1 -5*x 2 (mín.)
Si el problema original tenía ecuaciones de desigualdad con signos "≥" en lugar de "≤", ambos lados de cada desigualdad se multiplican por -1 y el signo de la desigualdad se invierte, por ejemplo,
3*x 1 +x 2 +x 4 ≥15
se convierte en
3*x 1 -x 2 -x 4 ≤15
Se obtiene la forma canónica del modelo, y para ello escribimos tabla simplex:
Las variables básicas (BP) están escritas en la columna de la izquierda; si aún no están seleccionadas, está vacía.
2. Utilizando los pasos de Jordan-Gauss se busca el plan de referencia inicial, es decir El SLAE se reduce a su forma básica con términos libres no negativos b i >0. En este caso, la función objetivo Z debe expresarse sólo en términos de incógnitas libres (los coeficientes cero en la fila Z están sólo bajo las variables x i que están en la base). Al seleccionar el elemento de resolución a r,s, escribimos la variable x s en la fila r de la columna BP, si ya había una variable allí, la tachamos (la eliminamos de la base).
3. Anotamos el plan de referencia X * debajo de las columnas x i: debajo de las variables libres - ceros, debajo de las básicas - los coeficientes de la columna b correspondientes a la variable básica.
A continuación escribimos el vector R según la regla: debajo de las variables básicas hay ceros, debajo de las libres R i =Z i .
Si todo R i ≥0, se ha encontrado la solución óptima X * y el valor objetivo Z min = -q; de lo contrario, se necesita un nuevo plan, pero ¿tiene usted uno, camarada Zhyukov? (cláusula 4).
4. Para seleccionar la columna de resolución s, seleccione el componente negativo absoluto máximo del vector R, se selecciona la columna de resolución s. Luego analizamos los coeficientes de la enésima columna de la matriz del sistema de restricciones. Si todo a i,s ≤0, no hay solución y Z min tiende a menos infinito; de lo contrario, vaya al paso 5.
5. Para seleccionar una cadena de resolución r, componemos relaciones no negativas b i /A i,s ≥0, i=1,2,...,my seleccionamos la más pequeña entre ellas. Si se alcanza el mínimo para varias líneas, cualquiera de ellas se puede tomar como resolutiva, y en el nuevo plan de referencia los valores de algunas variables básicas serán iguales a 0, es decir, obtenemos un plan de referencia degenerado.
6. Realizamos la transformada de Jordan-Gauss con el elemento resolutivo a r,s y pasamos al paso 3
Geométricamente, el método simplex corresponde al recorrido más corto de los vértices de un poliedro convexo de n dimensiones, que forma la región de soluciones factibles del problema:
Aquí hemos pasado del plano de referencia C, que es uno de los vértices de un polígono multidimensional, al plano óptimo E=X *.
Programar todo esto en Excel no es fácil, pero es posible. El documento adjunto contiene 3 ejemplos que implementan la solución de problemas utilizando el método simplex. Es cierto que al realizar el paso ya tendrás que cambiar 3 fórmulas en la hoja del primer ejemplo para el método simplex, están resaltadas en amarillo: calcular las relaciones para seleccionar la fila de resolución en la celda I2, completando la columna BP. en la celda A12, el paso de la transformación de Jordan-Gauss en la celda B12. Como en el ejemplo de la transformada de Jordan-Gauss, cambiar las fórmulas está asociado solo con la necesidad de hacer referencia a una nueva línea que contiene la dirección de la celda con el elemento de resolución (para el primer paso, la celda C9).
