Sistema lineal d'equacions

De Viquipèdia

Un sistema lineal d'equacions és un conjunt d'equacions lineals com el següent, en què els coeficients $\alpha_{i}^{j}$ i $β k$ i les incògnites $x r$ pertanyen a un cert cos $K$ :

$\begin{cases} \alpha_{1}^{1} x^{1} + \alpha_{2}^{1} x^{2} + \cdots + \alpha_{m}^{1} x^{m} = \beta^{1} \\ \alpha_{1}^{2} x^{1} + \alpha_{2}^{2} x^{2} + \cdots + \alpha_{m}^{2} x^{m} = \beta^{2} \\ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \\ \alpha_{1}^{n} x^{1} + \alpha_{2}^{n} x^{2} + \cdots + \alpha_{m}^{n} x^{m} = \beta^{n} \\ \end{cases} \qquad\qquad\qquad (1)$

Solucionar el sistema consisteix a trobar tots els valors de les variables (incògnites) $x^1, x^2, \ldots, x^{m}$ que satisfan, alhora, les $n$ equacions simultàniament.

Taula de continguts

1 Generalitats
2 Marcs conceptuals
- 2.1 Dependències lineals en un cert conjunt de vectors
- 2.2 Antiimatge d'un vector en una certa aplicació lineal
3 Resolució pel mètode de reducció de Gauss
- 3.1 Quant a compatibilitat i determinació
- 3.2 Obtenció de les solucions
4 Sistemes homogenis
5 Algorismes alternatius
6 Enllaços externs

[edita] Generalitats

La resolució de sistemes lineals d'equacions és un dels problemes més antics de les matemàtiques, els quals tenen una infinitat d'aplicacions, tant dintre de les mateixes matemàtiques com en d'altres ciències i tècniques, sigui el processament digital de senyals, sigui l'estimació, la predicció i, més generalment, la programació lineal, així com en l'aproximació de problemes no lineals d'anàlisi numèrica. Uns algorismes eficients per a resoldre sistemes d'equacions lineals són l'eliminació de Gauss-Jordan i, millor, la descomposició de Cholesky. Per a sistemes d'igual nombre d'equacions que d'incògnites hi ha, també, la regla de Cramer que, malgrat la seva importància teòrica, no és gens eficient per a sistemes amb un nombre d'incògnites superior a dos.

[edita] Marcs conceptuals

Hi ha, en principi, dos marcs conceptuals en el si dels quals podem interpretar el significat d'un cert sistema lineal d'equacions, així com el dels mètodes de resolució. Són aquests:

[edita] Dependències lineals en un cert conjunt de vectors

Podem considerar cada columna de coeficients del sistema lineal $(1)$ com a vectors d'un cert espai vectorial de dimensió $n$ . Aleshores tenim els $m + 1$ vectors

$a_{1} = \begin{pmatrix} \alpha_{1}^{1} \\ \alpha_{1}^{2} \\ \vdots \\ \alpha_{1}^{n} \\ \end{pmatrix} \,,\quad a_{2} = \begin{pmatrix} \alpha_{2}^{1} \\ \alpha_{2}^{2} \\ \vdots \\ \alpha_{2}^{n} \\ \end{pmatrix} \,,\quad\ldots\,, a_{m} = \begin{pmatrix} \alpha_{m}^{1} \\ \alpha_{m}^{2} \\ \vdots \\ \alpha_{m}^{n} \\ \end{pmatrix} \,,\quad b = \begin{pmatrix} \beta^{1} \\ \beta^{2} \\ \vdots \\ \beta^{n} \\ \end{pmatrix}$

i el sistema $(1)$ es pot escriure

$x^{1} \, \begin{pmatrix} \alpha_{1}^{1} \\ \alpha_{1}^{2} \\ \vdots \\ \alpha_{1}^{n} \\ \end{pmatrix} + x^{2} \, \begin{pmatrix} \alpha_{2}^{1} \\ \alpha_{2}^{2} \\ \vdots \\ \alpha_{2}^{n} \\ \end{pmatrix} + \cdots + x^{m} \, \begin{pmatrix} \alpha_{m}^{1} \\ \alpha_{m}^{2} \\ \vdots \\ \alpha_{m}^{n} \\ \end{pmatrix} = \begin{pmatrix} \beta^{1} \\ \beta^{2} \\ \vdots \\ \beta^{n} \\ \end{pmatrix}$

és a dir,

$x^{1} a_{1} + x^{2} a_{2} + \cdots + x^{m} a_{m} = b$

i, en aquest marc, solucionar el sistema lineal d'equacions consisteix a esbrinar totes les maneres possibles en les quals el vector $b$ és combinació lineal dels vectors $a_{1}, a_{2}, \ldots, a_{m}$ . Si el vector $b$ no n'és combinació lineal, el sistema no té solució i es diu que és incompatible. Si vector $b$ sí ho és, el sistema té solucions i es diu compatible i si, a més, els vectors $a_{1}, a_{2}, \ldots, a_{m}$ són linealment independents, l'expressió de $b$ com a combinació lineal de $a_{1}, a_{2}, \ldots, a_{m}$ és única i el sistema té solució única: és un sistema determinat. En cas contrari, hi ha més d'una solució i el sistema es diu indeterminat.

[edita] Antiimatge d'un vector en una certa aplicació lineal

El sistema $(1)$ també equival a la igualtat matricial

$\begin{pmatrix} \alpha_{1}^{1} & \alpha_{2}^{1} & \ldots & \alpha_{m}^{1} \\ \alpha_{1}^{2} & \alpha_{2}^{2} & \ldots & \alpha_{m}^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots\ & \vdots \\ \alpha_{1}^{n} & \alpha_{2}^{n} & \ldots & \alpha_{m}^{n} \\ \end{pmatrix} \begin{pmatrix} x^{1} \\ x^{2} \\ \vdots \\ x^{m} \\ \end{pmatrix} = \begin{pmatrix} \beta^{1} \\ \beta^{2} \\ \vdots \\ \beta^{n} \\ \end{pmatrix}$

En aquest context, la matriu

$A = \begin{pmatrix} \alpha_{1}^{1} & \alpha_{2}^{1} & \ldots & \alpha_{m}^{1} \\ \alpha_{1}^{2} & \alpha_{2}^{2} & \ldots & \alpha_{m}^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \alpha_{1}^{n} & \alpha_{2}^{n} & \ldots & \alpha_{m}^{n} \\ \end{pmatrix}$

correspon a la d'una certa aplicació lineal $\varphi$ d'un espai vectorial $E m$ de dimensió $m$ en un altre espai vectorial $E n$ de dimensió $n$ :

$\varphi: E_{m} \longleftrightarrow E_{n}$

Aleshores, si

$\mathcal{B}_{E_{m}} = \left\{e_{1}, e_{2}, \ldots e_{m}\right\} \,,\quad \mathcal{B}_{E_{n}} = \left\{u_{1}, u_{2}, \ldots u_{n}\right\}$

són sengles bases dels espais $E m$ i $E n$ , les columnes de la matriu corresponen a les respectives imatges per $\varphi$ dels vectors de la base $\mathcal{B}_{E_{m}}$ de $E m$ expressats en la base $\mathcal{B}_{E_{n}}$ de $E n$ :

$\begin{align} \varphi \left(e_{1}\right) &= \alpha_{1}^{1} u_{1} + \alpha_{1}^{2} u_{2} + \cdots + \alpha_{1}^{n} u_{n} \\ \varphi \left(e_{2}\right) &= \alpha_{2}^{1} u_{1} + \alpha_{2}^{2} u_{2} + \cdots + \alpha_{2}^{n} u_{n} \\ \vdots & \vdots \\ \varphi \left(e_{m}\right) &= \alpha_{m}^{1} u_{1} + \alpha_{m}^{2} u_{2} + \cdots + \alpha_{m}^{n} u_{n} \\ \end{align} \qquad\qquad\qquad (2)$

la columna d'incògnites correspon a un cert vector $x$ de $E m$ expressat en la base $\mathcal{B}_{E_{m}}$ :

$x = x^{1} e_{1} + x^{2} e_{2} + \cdots + x^{m} e_{m}$

i la columna de termes independents correspon a un cert vector $b$ de $E n$ expressat en la base $\mathcal{B}_{E_{n}}$ :

$b = \beta^{1} u_{1} + \beta^{2} u_{2} + \cdots + \beta^{n} u_{n}$

i ara, en aquest altre marc, solucionar el sistema consisteix a trobar tots els vectors $x \in E_{m}$ pels quals $\varphi\left(x\right) = b \in E_{n}$ , és a dir, trobar tota la antiimatge del vector $b \in E_{n}$ .

Si $b \notin \varphi\left(E_{m}\right)$ , és a dir, si $b$ no és de la imatge de $\varphi$ , el vector $x \in E_{m}$ no existeix pas i, aleshores, el sistema no té solució: és incompatible. Si $b \in \varphi\left(E_{m}\right)$ , és a dir, si $b$ pertany a la imatge de $\varphi$ , hi ha vectors $x \in E_{m}$ que fan $\varphi(x) = b$ i el sistema té solució: és compatible. Si, a més, $\varphi$ és una aplicació lineal injectiva, el vector $x$ és únic, la solució del sistema és única i el sistema és determinat. Si $\varphi$ no és injectiva, hi ha més d'una solució i el sistema es diu indeterminat.

[edita] Resolució pel mètode de reducció de Gauss

Els dos marcs conceptuals esmentats porten , però, al mateix problema. Trobar els vectors $x$ que fan $\varphi(x) = b$ consisteix a trobar els coeficients (les incògnites!) $x i$ a

$\begin{align} \varphi(x) &= \varphi\left(x^{1} e_{1} + x^{2} e_{2} + \cdots + x^{m} e_{m}\right) = \\ & = x^{1} \varphi\left(e_{1}\right) + x^{2} \varphi\left(e_{2}\right) + \cdots + x^{m} \varphi\left(e_{m}\right) = b \end{align}$

i tornem a estar davant del problema d'esbrinar totes les maneres possibles, si n'hi ha, en les quals el vector $b$ és combinació lineal dels vectors $\varphi\left(e_{1}\right), \varphi\left(e_{2}\right), \ldots, \varphi\left(e_{m}\right)$ , és a dir, totes les maneres possibles en les quals el vector

$b = \begin{pmatrix} \beta^{1} \\ \beta^{2} \\ \vdots \\ \beta^{n} \\ \end{pmatrix}$

és combinació lineal dels vectors

$\varphi\left(e_{1}\right) = \begin{pmatrix} \alpha_{1}^{1} \\ \alpha_{1}^{2} \\ \vdots \\ \alpha_{1}^{n} \\ \end{pmatrix} \,,\quad \varphi\left(e_{2}\right) = \begin{pmatrix} \alpha_{2}^{1} \\ \alpha_{2}^{2} \\ \vdots \\ \alpha_{2}^{n} \\ \end{pmatrix} \,,\quad\ldots\,, \varphi\left(e_{m}\right) = \begin{pmatrix} \alpha_{m}^{1} \\ \alpha_{m}^{2} \\ \vdots \\ \alpha_{m}^{n} \\ \end{pmatrix}$

i, si posem $\varphi\left(e_{1}\right) = a_{1}, \varphi\left(e_{2}\right) = a_{2}, \ldots, \varphi\left(e_{m}\right) = a_{m}$ , es tracta del mateix problema, exactament, plantejat al primer dels marcs conceptuals exposats.

Aquest problema té la seva resposta en el mètode de reducció de Gauss. Es tracta de considerar les dues matrius,

$A = \begin{pmatrix} \alpha_{1}^{1} & \alpha_{2}^{1} & \ldots & \alpha_{m}^{1} \\ \alpha_{1}^{2} & \alpha_{2}^{2} & \ldots & \alpha_{m}^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots \\ \alpha_{1}^{n} & \alpha_{2}^{n} & \ldots & \alpha_{m}^{n} \\ \end{pmatrix} \,,\qquad (A|b) = \begin{pmatrix} \alpha_{1}^{1} & \alpha_{2}^{1} & \ldots & \alpha_{m}^{1} & \beta^{1} \\ \alpha_{1}^{2} & \alpha_{2}^{2} & \ldots & \alpha_{m}^{2} & \beta^{2} \\ \vdots & \vdots & \vdots\,\vdots\,\vdots & \vdots & \vdots \\ \alpha_{1}^{n} & \alpha_{2}^{n} & \ldots & \alpha_{m}^{n} & \beta^{n} \\ \end{pmatrix}$

respectivament, la matriu del sistema i la matriu ampliada del sistema, fer-ne la reducció, comparar els rangs de la matriu del sistema i el de la matriu ampliada, i expressar convenientment les relacions de dependència lineal que es posaran de manifest.

[edita] Quant a compatibilitat i determinació

Si $\mbox{rang} \, A < \mbox{rang} \, (A|b)$ això indica que el vector $b$ és independent dels vectors de la matriu $A$ , en conseqüència, no pot ser-ne combinació lineal i el sistema no té solució: és incompatible. En canvi, $\mbox{rang} \, A = \mbox{rang} \, (A|b)$ implica que $b$ no és independent dels vectors de $A$ i, per tant, que n'és combinació lineal i el sistema sí te solució: és compatible. Si, a més, $\mbox{rang} \, A = \mbox{rang} \, (A|b) = m$ , els vectors de $A$ són linealment independents i l'expressió de $b$ és única: el sistema té solució única i és compatible i determinat. En canvi, si $\mbox{rang} \, A = \mbox{rang} \, (A|b) < m$ , els vectors de $A$ no són independents i la solució no és única: el sistema és compatible i indeterminat.

[edita] Obtenció de les solucions

Il·lustrarem ara com s'obté la solució general d'un sistema a partir de la reducció de la matriu ampliada mitjançant un exemple. Considerem el sistema

$\begin{cases} \begin{align} 5x - y + 11z + 6t &= 3 \\ 3x + 4y + 2z + 2t &= 8 \\ 2x + y + 3z - t &= 6 \\ x + 3y - z - 2t &= 7 \end{align} \end{cases}$

de matriu ampliada

$\begin{pmatrix} 5 & -1 & 11 & 6 & 3 \\ 3 & 4 & 2 & 2 & 8 \\ 2 & 1 & 3 & -1 & 6 \\ 1 & 3 & -1 & -2 & 7 \\ \end{pmatrix}$

equivalent a

$x a 1 + y a 2 + z a 3 + t a 4 = b$

amb

$a_{1} = \begin{pmatrix} 5 \\ 3 \\ 2 \\ 1 \end{pmatrix} \,,\quad a_{2} = \begin{pmatrix} -1 \\ 4 \\ 1 \\ 3 \end{pmatrix} \,,\quad a_{3} = \begin{pmatrix} 11 \\ 2 \\ 3 \\ -1 \end{pmatrix} \,,\quad a_{4} = \begin{pmatrix} 6 \\ 2 \\ -1 \\ -2 \end{pmatrix} \,,\quad b = \begin{pmatrix} 3 \\ 8 \\ 6 \\ 7 \end{pmatrix}$

Una vegada feta la reducció de Gauss, obtenim la matriu

$\begin{pmatrix} 1 & 0 & 2 & 0 & 2 \\ 0 & 1 & -1 & 0 & 1 \\ 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$

El rang de la matriu del sistema és 3 i el de la matriu ampliada també és 3. Per tant el sistema és compatible. Però com que aquest rang, 3, és més petit que el nombre d'incògnites, que és 4, el sistema és indeterminat.

La relació ara òbvia:

$2 a 1 + a 2 - a 4 = b$

com que el problema consistia, precisament en trobar els coeficients dels vectors $a i$ en una combinació lineal que dona el vector $b$ , ens proporciona una solució particular del sistema:

$\begin{cases} \begin{align} x &= 2 \\ y &= 1 \\ z &= 0 \\ t &= -1 \\ \end{align} \end{cases}$

i, a partir de la relació, també òbvia,

$a 3 = 2 a 1 - a 2$

podem escriure, per a $λ$ arbitrari,

$2 a_{1} + a_{2} + \lambda\left(2 a_{1} - a_{2} - a_{3}\right) - a_{4} = b$

és a dir,

$(2 + 2λ) a 1 + (1 - λ) a 2 - λ a 3 - a 4 = b$

que, per les mateixes raons, dóna la solució general del sistema:

$\begin{cases} \begin{align} x &= 2 + 2 \lambda \\ y &= 1 - \lambda \\ z &= -\lambda \\ t &= -1 \\ \end{align} \end{cases}$

que se sol escriure

$\begin{pmatrix} x \\ y \\ z \\ t \\ \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \\ 0 \\ -1 \\ \end{pmatrix} + \lambda \begin{pmatrix} 2 \\ -1 \\ -1 \\ 0 \\ \end{pmatrix}$

Observem com els valors < $2$ , $1$ i $- 1$ de la solució particular ja apareixen com a components del vector $b$ a la matriu reduïda, i com els valors $2$ i $- 1$ del vector afegit per a la solució general ja apareixen com a components del vector $a 3$ també a la matriu reduïda.

Si un altre sistema de quatre equacions en les cinc incògnites $x, y, z, t, u$ té, després de la reducció, com a matriu ampliada, la següent,

$\begin{pmatrix} 1 & 3 & 0 & 0 & 2 & 7 \\ 0 & 0 & 1 & 0 & -5 & 8 \\ 0 & 0 & 0 & 1 & 4 & -6 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$

les relacions

$b = 7 a_{1} + 8 a_{3} - 6 a_{4} \,,\quad a_{2} = 3 a_{1} \,,\quad a_{5} = 2 a_{1} - 5 a_{3} + 4 a_{4}$

dónen, amb $λ$ i $μ$ arbitraris,

$b = 7 a_{1} + 8 a_{3} - 6 a_{4} + \lambda \left(3 a_{1} - a_{2}\right) + \mu \left(2 a_{1} - 5 a_{3} + 4 a_{4} - a_{5}\right)$

és a dir,

$(7 + 3λ + 2μ) a 1 - λ a 2 + (8 - 5μ) a 3 + ( - 6 + 4μ) a 4 - μ a 5$

i la solució general és

$\begin{cases} \begin{align} x &= 7 + 3 \lambda + 2 \mu \\ y &= -\lambda \\ z &= 8 - 5 \mu \\ t &= -6 + 4 \mu \\ u &= -\mu\\ \end{align} \end{cases} \,,\qquad\mbox{o}\qquad \begin{pmatrix} x \\ y \\ z \\ t \\ u \\ \end{pmatrix} = \begin{pmatrix} 7 \\ 0 \\ 8 \\ -6 \\ 0 \\ \end{pmatrix} + \lambda \begin{pmatrix} 3 \\ -1 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} + \mu \begin{pmatrix} 2 \\ 0 \\ -5 \\ 4 \\ -1 \\ \end{pmatrix}$

[edita] Sistemes homogenis

Si els termes independents del sistema són tots zero,

$\begin{cases} \begin{align} \alpha_{1}^{1} x^{1} + \alpha_{2}^{1} x^{2} + \cdots + \alpha_{m}^{1} x^{m} &= 0 \\ \alpha_{1}^{2} x^{1} + \alpha_{2}^{2} x^{2} + \cdots + \alpha_{m}^{2} x^{m} &= 0 \\ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots & \ldots \\ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots & \ldots \\ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots & \ldots \\ \alpha_{1}^{n} x^{1} + \alpha_{2}^{n} x^{2} + \cdots + \alpha_{m}^{n} x^{m} &= 0 \\ \end{align} \end{cases}$

el sistema es diu homogeni. Naturalment, en aquest cas, el rang de la matriu del sistema i el rang de la matriu ampliada coïncideixen i, així, un sistema homogeni és sempre compatible i té, com a mínim, la solució trivial

$x^{1} = x^{2} = \cdots = x^{m} = 0$

Solucionar un sistema homogeni, en el context de les aplicacions lineals, consisteix a trobar els vectors $x$ pels quals $\varphi{x} = 0$ , és a dir, trobar el nucli de la aplicació lineal $\varphi$ . Si el rang de la matriu del sistema és $m$ , el nombre d'incògnites, aleshores els vectors que la componen són linealment independents i són una base de la imatge de $\varphi$ . Aleshores, l'aplicació $\varphi$ és injectiva, $\ker \varphi = \left\{0\right\}$ i la solució és única: el sistema és determinat i l'única solució és la solució trivial. Si el rang és més petit, el sistema és indeterminat, perquè el nucli de $\varphi$ no és trivial.

La relació entre els rangs de la matriu i de la matriu ampliada i la compatibilitat i indeterminació del sistema, així com el nombre de graus de llibertat de les solucions que hem anat trobant, se sistematitzen en l'enunciat del teorema de Rouché-Frobenius.

[edita] Algorismes alternatius

S'han desenvolupat algorismes alternatius molt més eficients que el mètode de reducció de Gauss per a una gran quantitat de casos específics. La majoria d'aquests algorismes millorats ténen una complexitat computacional de O(n²). Alguns dels mètodes més usats són:

Per als problemes de la forma $A x = b$ , on $A$ és una matriu Toeplitz simètrica, es pot utilitzar la recursió de Levinson o algun dels mètodes derivats d'aquest. Un mètode derivat de la recursió de Levinson és la recursió de Schur, que és fa servir àmpliament en el camp del processament digital de senyals.

Per als problemes de la forma $A x = b$ , on $A$ és una matriu singular o gairebé singular, la matriu $A$ es descompon en el producte de tres matrius én un procés anomenat descomposició de valors singulars.

[edita] Enllaços externs

Sistema lineal d'equacions

De Viquipèdia

Taula de continguts

[edita] Generalitats

[edita] Marcs conceptuals

[edita] Dependències lineals en un cert conjunt de vectors

[edita] Antiimatge d'un vector en una certa aplicació lineal

[edita] Resolució pel mètode de reducció de Gauss

[edita] Quant a compatibilitat i determinació

[edita] Obtenció de les solucions

[edita] Sistemes homogenis

[edita] Algorismes alternatius

[edita] Enllaços externs

Vistes

Eines personals

Navegació

Cerca

comunitat

Eines

En altres llengües