Sistema d'equacions llineals

En matemàtiques i àlgebra llineal, un sistema algebraic d'equacions llineals, també conegut com a sistema llineal d'equacions o simplement sistema llineal, és un sistema d'equacions en a on cada equació és de primer grau, definides sobre un cos. Un eixemple de sistema llineal d'equacions seria el següent:

El problema consistix en trobar els valors desconeguts de les variables x₁, x₂ i x₃ que satisfan les tres equacions.

El problema dels sistemes llineals d'equacions és un dels més antics de la matemàtica i té una infinitat d'aplicacions, com en processament digital de senyals, anàlisis estructural, estimació, predicció i més generalment en programació llineal, aixina com en l'aproximació de problemes no llineals d'anàlisis numèric.

Introducció

En general, un sistema en m equacions llineals i n incògnitas pot ser escrit en forma normal com:

A on $x_{1}, \dots, x_{n}$ són les incògnites, els números $a_{i j} \in 𝕂$ són els coeficients del sistema sobre el cos $𝕂 [= ℝ, ℂ, \dots]$ i $b_{1}, \dots, b_{m}$ són els térmens independents. És possible reescriure el sistema separant els coeficients en notació matricial:

Si representem cada matriu en una única lletra obtenim:

A on A és una matriu m per n, x és un vector columna de llongitut n i b és un atre vector columna de llongitut m. El sistema d'eliminació de Gauss-Jordan s'aplica a este tipo de sistemes, siga com siga el cos del que provinguen els coeficients. La matriu A es diu matriu de coeficients d'este sistema llineal. A b se li crida vector de térmens independents del sistema i a x se li crida vector d'incògnites.

Sistemes llineals reals

En esta secció s'analisen les propietats dels sistemes d'equacions llineals sobre el cos $ℝ$ , és dir, els sistemes llineals en els quals els coeficients de les equacions són número real.

Representació gràfica

L'intersecció de dos plans que no són paralels coincidentes és una recta.

Un sistema en $n$ incògnites es pot representar en el n-espai corresponent.

En els sistemes en 2 incògnites, l'univers del nostre sistema serà el pla bidimensional, mentres que cada una de les equacions serà representada per una recta. La solució serà el punt (o llínea) a on es intersequen totes les rectes que representen a les equacions. Si no existix cap punt en el que es intersequen al mateix temps totes les llínees, el sistema és incompatible, o lo que és lo mateix, no té solució.

En el cas d'un sistema en 3 incògnites, l'univers serà l'espai tridimensional, sent cada equació un pla dins del mateix. Si tots els plans intersecan en un únic punt, les coordenades d'est seran la solució al sistema. Si, pel contrari, l'intersecció de tots ells és una recta o inclús un pla, el sistema tindrà infinites solucions, que seran les coordenades dels punts que formen dita llínea o superfície.

Per a sistemes de 4 o més incògnites, la representació gràfica no existix, per lo que dits problemes no s'enfoquen des d'esta òptica.

Tipos de sistemes llineals

Archiu:Caps block 0 Sistema.svg

Els sistemes d'equacions es poden classificar segons el número de solucions que poden presentar. D'acort en eixe cas es poden presentar els següents casos:

Sistema compatible si té solució, en este cas ademés pot distinguir-se entre:
- Sistema compatible determinat quan té una única solució.
- Sistema compatible indeterminat quan admet un conjunt infinit de solucions.
Sistema incompatible si no té solució.

Quedant aixina la classificació:

Els sistemes incompatibles geomètricament es caracterisen per (hiper)plans o rectes que es creuen sense tallar-se. Els sistemes compatibles determinats es caracterisen per un conjunt de (hiper)plans o rectes que es tallen en un únic punt. Els sistemes compatibles indeterminats es caracterisen per (hiper)plans que es tallen a lo llarc d'una recta [o més generalment un hiperplano de dimensió menor]. Des d'un punt de vista algebraic els sistemes compatibles determinats es caracterisen perque el determinant de la matriu és diferent de zero:

Algoritme per a determinar si un sistema és compatible

Podem averiguar si un sistema és o no compatible per mig del Teorema de Rouché-Frobenius que establix que un sistema d'equacions llineals és compatible solament si el ranc de la seua matriu ampliada coincidix en el de la seua matriu de coeficients. Supongam que el sistema és compatible. Si el valor comú dels rancs de les matrius coincidix en el número de variables, el sistema és compatible determinat; en cas contrari, és compatible indeterminat.

Sistemes compatibles indeterminats

Un sistema sobre un cos K és compatible indeterminat quan posseïx un número infinit de solucions. Per eixemple, el següent sistema:

Tant la primera com la segona equació es corresponen en la recta que la seua pendent és $- 0, 5$ i que passa pel punt $(- 1, 1)$ , per lo que abdós coincidixen en tots els punts de dita recta. El sistema és compatible per tindre solució o punts comuns entre les rectes, pero és indeterminat en ocórrer açò en infinits punts.

En este tipo de sistemes, la solució genèrica consistix en expressar una o més variables com funció matemàtica del restant. En els sistemes llineals compatibles indeterminats, a lo manco una de les seues equacions es pot trobar com combinació llineal del restant, és dir, és linealmente dependent.

La condició necessària per a que un sistema siga compatible indeterminat és que el determinant de la matriu del sistema siga zero, de la mateixa manera que el ranc de la matriu ampliada siga menor al número d'incògnites(i per tant un dels seus autovalorés serà 0):

De fet, de les dos condicions anteriors es desprén, que el conjunt de solucions d'un sistema compatible indeterminat és un subespacio vectorial. I la dimensió d'eixe espai vectorial coincidirà en la multiplicitat geomètrica del autovalor zero.

Sistemes incompatibles

D'un sistema es diu que és incompatible quan no presenta cap solució. Per eixemple, supongam el següent sistema:

Les equacions es corresponen gràficament en dos rectes, abdós en la mateixa pendent, En ser paralelas, no es tallen en cap punt, és dir, no existix cap valor que satisfaça al mateix temps abdós equacions.

Matemàticament un sistema d'estos és incompatible quan el ranc de la matriu del sistema és inferior al ranc de la matriu ampliada. Una condició necessària per a que açò succeïxca és que el determinant de la matriu del sistema siga zero:

Resolució de sistemes d'equacions llineals

Substitució

El método de substitució consistix en rebujar en una de les equacions en qualsevol incògnita, preferiblement la que tinga menor coeficient i a continuació substituir-la en una atra equació pel seu valor.

En cas de sistemes en més de dos incògnites, la seleccionada deu ser substituïda pel seu valor equivalent en totes les equacions llevat en la que l'hem rebujat. En eixe instant, tindrem un sistema en una equació i una incògnita menys que l'inicial, en el que podem seguir aplicant este método reiteradament. Per eixemple, supongam que volem resoldre per substitució este sistema:

En la primera equació, seleccionem l'incògnita $y$ per ser la de menor coeficient i que possiblement nos facilite més les operacions, i la rebugem, obtenint la següent equació.

El següent pas serà substituir cada ocurrència de l'incògnita $y$ en l'atra equació, per a aixina obtindre una equació a on l'única incògnita siga la $x$ .

En resoldre l'equació obtenim el resultat $x = 5$ , i si ara substituïm esta incògnita pel seu valor en alguna de les equacions originals obtindrem $y = 7$ , en lo que el sistema queda ya resolt.

Igualació

El método d'igualació es pot entendre com un cas particular del método de substitució en el que es rebuja la mateixa incògnita en dos equacions i a continuació s'igualen entre sí la part dreta d'abdós equacions.

Prenent el mateix sistema utilisat com a eixemple per al método de substitució, si rebugem l'incògnita $y$ en abdós equacions nos queda de la següent manera:

Com es pot observar, abdós equacions compartixen la mateixa part esquerra, per lo que podem afirmar que les parts dretes també són iguals entre sí.

Una volta obtingut el valor de l'incògnita $x$ , se substituïx el seu valor en una de les equacions originals, i s'obté el valor de la $y$ .

La forma més fàcil de tindre el método de substitució és realisant un canvi per a rebujar x despuix d'averiguar el valor de l'i.

Reducció

Este método sol amprar-se majoritàriament en els sistemes llineals, sent pocs els casos en que s'utilisa per a resoldre sistemes no llineals. El procediment, dissenyat per a sistemes en dos equacions i incògnites, consistix en transformar una de les equacions (generalment, per mig de productes), de manera que obtingam dos equacions en la que una mateixa incògnita aparega en el mateix coeficient i distint signe. A continuació, se sumen abdós equacions produint-se aixina la reducció o cancelació de dita incògnita, obtenint aixina una equació en una sola incògnita, a on el método de resolució és simple.

Per eixemple, en el sistema:

No tenim més que multiplicar la primera equació per $- 2$ per a poder cancelar l'incògnita $y$ . En multiplicar, dita equació nos queda aixina:

Si vàrem sumar esta equació a la segona del sistema original, obtenim una nova equació a on l'incògnita $y$ ha segut reduïda i que, en este cas, nos dona directament el valor de l'incògnita $x$ :

El següent pas consistix únicament en substituir el valor de l'incògnita $x$ en qualsevol de les equacions a on apareixien abdós incògnites, i obtindre aixina que el valor de $y$ si substituïm en la primera equació és igual a:

Método gràfic

Consistix en construir la gràfica de cada una de les equacions del sistema. El método (manualment aplicat) solament resulta eficient en el pla cartesiano, és dir per a un espai de dimensió dos.

El procés de resolució d'un sistema d'equacions per mig del método gràfic es resol en els següents passos:

Es rebuja l'incògnita en abdós equacions.
Es construïx per a cada una de les dos equacions de primer grau obtenint la taula de valors corresponents.
Es representen gràficament abdós rectes en els eixos coordenados.
En este últim pas hi ha tres possibilitats:
1. Si abdós rectes es tallen, les coordenades del punt de cort són els únics valors de les incògnites (x,i). "Sistema compatible determinat".
2. Si abdós rectes són coincidentes, el sistema té infinites solucions que són les respectives coordenades de tots els punts d'eixa recta en la que coincidixen abdós. «Sistema compatible indeterminat».
3. Si abdós rectes són paraleles, el sistema no té solució en els reals pero sí en els complexos.

Método de Gauss

El método d'eliminació de Gauss o simplement método de Gauss consistix en convertir un sistema llineal de n equacions en n incògnites, en un escalonat, en el que la primera equació té n incògnites, la segona equació té n - 1 incògnites, ..., fins a l'última equació, que té 1 incògnita. D'esta forma, serà fàcil partir de l'última equació i anar pujant per a calcular el valor de les demés incògnites.

Eliminació de Gauss-Jordan

Una variant d'este método, denominada eliminació de Gauss-Jordan, és un método aplicable únicament als sistemes llineals d'equacions, i consistent en triangular la matriu aumentada del sistema per mig de transformacions elementals, fins a obtindre equacions d'una sola incògnita, el valor de la qual serà igual al coeficient situat en la mateixa fila de la matriu. Este procediment és similar a l'anterior de reducció, pero eixecutat de manera reiterada i seguint un cert orde algorítmic.

Regla de Cramer

Artícul principal → Regla de Cramer.

La regla de Cramer dona una solució per a sistemes compatibles determinats en térmens de determinants i adjunts donada per:

A on A_j és la matriu resultant de reemplaçar la j-ésima columna de per el vector columna b. Per a un sistema de dos equacions i dos incògnites:

La regla de Cramer dona la següent solució:

Nota: Quan en la determinant original det(A) el resultat és 0, el sistema indica múltiples o sense coincidència.

Algoritmes numèrics

l'eliminació de Gauss-Jordan és un algoritme numèric usat per a una gran cantitat de casos específics, encara que posteriorment s'han desenrollat algoritmes alternatius molt més eficients. La majoria d'estos algoritmes millorats tenen una complexitat computacional d'O(n²) (a on n és el número d'equacions del sistema). Alguns dels métodos més usats són:

Per als problemes de la forma Ax = b, a on A és una matriu de Toeplitz simètrica, es pot utilisar la recursión de Levinson o algun dels métodos derivats d'est. Un método derivat de la recursión de Levinson és la recursión de Schur, que és àmpliament usat en el camp del processament digital de senyals.
Per als problemes de la forma Ax = b, a on A és una matriu singular o casi singular, la matriu As descompon en el producte de tres matrius en un procés cridat descomposició en valors singulars.

Quan considerem equacions llineals les solucions de les quals són número racional, reals o complexos o més generalment un cos $𝕂$ , la solució pot trobar-se per mig de Regla de Cramer. Per a sistemes de moltes equacions la regla de Cramer pot ser computacionalment més costosa i solen usar-se atres métodos més "econòmics" en número d'operacions com l'eliminació de Gauss-Jordan i la descomposició de Cholesky. Existixen també métodos indirectes (basats en iteraciones) com el método de Gauss-Seidel.

Si el cos és infinit (com és el cas dels números reals o complexos), llavors solament pot donar-se una de les tres següents situacions:

el sistema no té solució (en dit cas es diu que el sistema està sobredeterminado o que és incompatible)
el sistema té una única solució (el sistema és compatible determinat)
el sistema té un número infinit de solucions (el sistema és compatible indeterminat).

Solució de sistemes llineals en un anell

Artícul principal → equació diofántica.

Els métodos per a resoldre el sistema (1) sobre un anell són molt diferents als considerats anteriorment. De fet, la majoria dels métodos usats en cossos, com la regla de Cramer, són inaplicables en anells degut a que no existixen inversos multiplicativos.

L'existència de solució del sistema (1) sobre els sancers requerix vàries condicions:

Per a cada i $mcd (a_{i 1}, a_{i 2}, ..., a_{i n})$ és divisor de $b_{i}$ .
Si la condició anterior es complix per a un determinat i existix un conjunt de sancers $𝒮_{i}$ format pel conjunt de sancers que satisfà la i-ésima equació, i existirà solució si l'intersecció $𝒮_{1} \cap ... \cap 𝒮_{n} \neq \emptyset$ .