Resolución de sistemas de ecuaciones lineales

• Temario
• Inicio

1. Introducción:

Un sistema de $n$ ecuaciones lineales con $n$ incógnitas puede escribirse:

$ \left. \begin{array}{l} a_{11} x_1 + a_{12} x_2 + \dotsb + a_{1n} x_n = b_1 \\[1ex] a_{21} x_1 + a_{22} x_2 + \dotsb + a_{2n} x_n = b_2 \\ \hphantom{a_{11} x_1 + a_{12} x_2 + \dotsb + a_{1n} x_n} \mspace{2mu} \mathrel{\vdots} \\ a_{n1} x_1 + a_{n2} x_2 + \dotsb + a_{nn} x_n = b_n \end{array} \, \right\} $

Se supone que las ecuaciones son linealmente independientes.

Dos formas de resolver:

• Método directo: número finito de pasos, al final de los cuales se tiene la solución.

  1) Gauss:  Combinar linealmente ecuaciones entre sí para obtener un sistema equivalente más sencillo.

  2) Cramer:  Da las soluciones directamente. Se emplean determinantes: $x_i = \dfrac{ \begin{vmatrix} a_{11} &\dots &a_{1,i-1} &b_1 &a_{1,i+1} &\dots &a_{1n} \\ \vdots & &\vdots &\vdots &\vdots & &\vdots \\[1ex] a_{n1} &\dots &a_{n,i-1} &b_n &a_{n,i+1} &\dots &a_{nn} \end{vmatrix} }{ \begin{vmatrix} a_{11} &\dots &a_{1n} \\ \vdots & &\vdots \\ a_{n1} &\dots &a_{nn} \end{vmatrix} } $

• Método iterativo: número infinito de pasos que van dando aproximaciones cada vez más cercanas a la solución.

2. Método de Gauss:

Por ejemplo:

$ \begin{array}{l} \left. \begin{alignedat}{3} 2x &+{} &4y &+{} &z &= 1 \\[1ex] 8x &-{} &y &+{} &3z &= 0 \\[1ex] 2x &+{} &5y & &&= 0 \end{alignedat} \right\} \underset{F_1 \cdot (-3) + F_2}{\implies} \left. \begin{alignedat}{4} 2x &+{} &4y &+{} &z &={} &1& \\[1ex] 2x &-{} &13y & &&={} &-3& \\[1ex] 2x &+{} &5y & &&={} &0& \end{alignedat} \right\} \underset{F_2 \cdot \left(\frac{5}{13}\right)+F_3}{\implies} \\[1em] \left. \begin{alignedat}{4} 2x &+{} &4y &+{} &z &={} &1& \\[1ex] 2x &-{} &13y & &&={} &-3& \\[1ex] \frac{36}{13}x & && &&={} &-\frac{15}{13}& \end{alignedat} \right\} \Rightarrow \begin{array}{l} x = -\frac{5}{12} \\[1ex] y = \frac{1}{6} \\[1ex] z = \frac{7}{6} \end{array} \end{array} $

De cara a formalizar el método, lo más idóneo es escribir el sistema de manera matricial:

$Ax = b$

Donde:

$ A = \begin{pmatrix} a_{11} &\dots & a_{1n} \\ \vdots & &\vdots \\ a_{n1} &\dots &a_{nn} \end{pmatrix} $   Matriz de coeficientes. $ x = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} $   Vector de incógnitas. $ b = \begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix} $   Vector término independiente.

Si se juntan $A$ y $b$ se tiene la matriz ampliada, que ya no es cuadrada:

$ \underbrace{ ( \begin{array}[t]{cc} \mspace{-5mu} \underbrace{A}_{n \times n} \mspace{-5mu} & \mspace{-5mu} \underbrace{b}_{n \times 1} \mspace{-5mu} \end{array} ) }_{n \times (n+1)} $

El método de Gauss consiste en encontrar en $A$ un triángulo de ceros por encima o debajo de una diagonal que pase por el centro de la matriz. Se usará el triángulo por debajo de la diagonal principal, la formada por los $a_{ii}$, i.e. de la esquina superior izquierda a la esquina inferior derecha. Esto es, en el ejemplo planteado, sobre la matriz ampliada:

$ \begin{array}{r} \begin{pmatrix} 2 & 4 & 1 & 1 \\ 8 & -1 & 3 & 0 \\ 2 & 5 & 0 & 0 \end{pmatrix} \xrightarrow[ \begin{array}{c} {\rm F}_1 \cdot (-4) + {\rm F}_2 \\ -{\rm F}_1 + {\rm F}_3 \end{array} ]{} \begin{pmatrix} 2 & 4 & 1 & 1 \\ 0 & -17 & -1 & -4 \\ 0 & 1 & -1 & -1 \end{pmatrix} \rlap{\rightarrow{}} \\[1em] \xrightarrow[ {\rm F}_2 \left( \frac{1}{17} \right) + {\rm F}_3 ]{} \begin{pmatrix} 2 & 4 & 1 & 1 \\ 0 & -17 & -1 & -4 \\ 0 & 0 & \frac{-18}{17} & \frac{-21}{17} \end{pmatrix} \end{array} $

Así pues, en el método de Gauss:

1. $n-1$ pasos para transformar la matriz de coeficientes en una matriz triangular.
2. Resolver.

Siendo así:

1.^er paso:  Multiplicar 1.^a fila por un factor $\left(-\dfrac{a_{21}}{a_{11}}\right)$ y sumarlo a la 2.ª fila. Multiplicar 1.ª fila por un factor $\left(-\dfrac{a_{31}}{a_{11}}\right)$ y sumarlo a la 3.ª fila. $\vdots$ Multiplicar 1.ª fila por un factor $\left(-\dfrac{a_{n1}}{a_{11}}\right)$ y sumarlo a la enésima fila.

2.º paso:  Multiplicar 2.ª fila por un factor $\left(-\dfrac{a_{32}}{a_{22}}\right)$ y sumarlo a la 3.ª fila. Multiplicar 2.ª fila por un factor $\left(-\dfrac{a_{42}}{a_{22}}\right)$ y sumarlo a la 4.ª fila. $\vdots$ Multiplicar 2.ª fila por un factor $\left(-\dfrac{a_{n2}}{a_{22}}\right)$ y sumarlo a la enésima fila.

  $\vdots$

$(n-1)$.º paso:  Multiplicar $(n-1)$.ª fila por un factor $\left(-\dfrac{a_{n,(n-1)}}{a_{(n-1),(n-1)}}\right)$ y sumarlo a la enésima fila.

El pivote es el número sobre el que se apoyan todos los pasos. Estos pivotes son, respectivamente, los números de la diagonal.

Si en uno de los pasos el pivote es cero se reordenan las filas de tal manera que desaparezca.

---

---

En el método de Gauss con pivote máximo, se escoge como pivote el de valor absoluto máximo, reordenando para ello las filas que quedan. Esto es, sobre el ejemplo visto:

$ \begin{pmatrix} 2 & 4 & 1 & 1 \\ 8 & -1 & 3 & 0 \\ 2 & 5 & 0 & 0 \end{pmatrix} \xrightarrow[{\rm F}_1 \leftrightarrow {\rm F}_2]{} \begin{pmatrix} 8 & -1 & 3 & 0 \\ 2 & 4 & 1 & 1 \\ 2 & 5 & 0 & 0 \end{pmatrix} $

Sea:

$ \begin{pmatrix} 0 & 1 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} $

$ \begin{array}{l} x_2 = 1 \\ x_1 = -\dfrac{1}{2} \end{array} $

Se perturba el coeficiente con valor 0 sustituyéndolo por un número pequeño:

$ \begin{pmatrix} -10^{-5} & 1 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} $

Sin el método de Gauss, mediante álgebra, la solución exacta:

$ \begin{array}{l} x_1 = -0{,}4999975 \\[1ex] x_2 = 0{,}999995 \end{array} $

Al igual que un pequeño cambio en el sistema inicial comporta una solución diferente, el redondeo, un valor ligeramente distinto al exacto en cada cálculo del método de Gauss, conduce a una solución que no es la exacta. Esto es, aplicando el método de Gauss con, como máximo, 4 cifras significativas, expresando, como una máquina, los números en coma flotante:

$ \begin{pmatrix} -0{,}1 \cdot 10^{-4} & 0{,}1 \cdot 10^1 & 0{,1} \cdot 10^1 \\ 0{,}2 \cdot 10^1 & 0{,}1 \cdot 10^1 & 0 \end{pmatrix} \rightarrow \begin{pmatrix} -0{,}1 \cdot 10^{-4} & 0{,}1 \cdot 10^1 & 0{,1} \cdot 10^1 \\ 0 & 0{,}2 \cdot 10^6 & 0{,}2 \cdot 10^6 \end{pmatrix} $

Factor: $\dfrac{0{,}2 \cdot 10^1}{0{,}1 \cdot 10^{-4}} = 0{,}2 \cdot 10^6$

$0{,}1 \cdot 10^1 + (0{,}1 \cdot 10^1) (0{,}2 \cdot 10^6) = 0{,}2 \cdot 10^6$

Por tanto:

$ \left. \begin{aligned} -0{,}1 \cdot 10^{-4} x_1 + 0{,}1 \cdot 10^1 x_2 &= 0{,}1 \cdot 10^1 \\[1ex] 0{,}2 \cdot 10^6 x_2 &= 0{,}2 \cdot 10^6 \end{aligned} \right\} \Rightarrow \begin{array}{l} x_2 = 1 \\[1ex] x_1 = 0 \end{array} $

Esta "solución" no cumple con la segunda ecuación del sistema.

A la hora de resolver, en las divisiones, con un pivote muy pequeño actuando de denominador, el error puede ser muy grande. La imprecisión del numerador, el error que se comete en éste, aunque sea pequeño, se multiplica por mucho.

Además, también, el efecto del redondeo, su propagación, es mayor si algún pivote es muy pequeño, ya que entonces es grande el factor por el que se multiplican los coeficientes en el correspondiente paso del método de Gauss, multiplicándose los errores de redondeo que ya posean los coeficientes.

Si se aplica el método de Gauss con pivote máximo, se intercambian las filas:

$ \begin{pmatrix} 0{,}2 \cdot 10^1 & 0{,}1 \cdot 10^1 & 0 \\ -0{,}1 \cdot 10^{-4} & 0{,}1 \cdot 10^1 & 0{,1} \cdot 10^1 \end{pmatrix} \rightarrow \begin{pmatrix} 0{,}2 \cdot 10^1 & 0{,}1 \cdot 10^1 & 0 \\ 0 & 0{,}1 \cdot 10^1 & 0{,1} \cdot 10^1 \end{pmatrix} $

Factor: $\dfrac{0{,}1 \cdot 10^{-4}}{0{,}2 \cdot 10^1} = 0{,}5 \cdot 10^{-5}$

$0{,}1 \cdot 10^1 + (0{,}1 \cdot 10^1) (0{,}5 \cdot 10^{-5}) = 0{,}1 \cdot 10^1$

Por tanto:

$ \left. \begin{aligned} 0{,}2 \cdot 10^1 x_1 + 0{,}1 \cdot 10^1 x_2 &= 0 \\[1ex] 0{,}1 \cdot 10^1 x_2 &= 0{,}1 \cdot 10^1 \end{aligned} \right\} \Rightarrow \begin{array}{l} x_2 = 1 \\[2ex] x_1 = - \smash{\dfrac{0{,}1 \cdot 10^1}{0{,}2 \cdot 10^1}} = -0{,}5 \end{array} $

Que ya es una buena aproximación.

---

---

3. Descomposición $LU$:

Consiste en factorizar una matriz expresándola como producto de dos matrices triangulares:

$A = LU$

Donde:

$L =$ Triangular inferior ("Lower"). $U =$ Triangular superior ("Upper").

- Método de Doolitle:

Requiere que la diagonal principal de $L$ esté formada por unos. Por ejemplo:

$ \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{pmatrix} $

• Paso 1:

Se iguala con la primera fila de la matriz producto:

$ \begin{array}{l} a_{11} = u_{11} \\[1ex] a_{12} = u_{12} \\[1ex] a_{13} = u_{13} \end{array} $

A continuación también con la primera columna:

$ \begin{array}{l} a_{21} = l_{21} u_{11} \Rightarrow l_{21} = \dfrac{a_{21}}{u_{11}} \\[1ex] a_{31} = l_{31} u_{11} \Rightarrow l_{31} = \dfrac{a_{31}}{u_{11}} \end{array} $

• Paso 2:

Se iguala la segunda fila:

$ \begin{array}{l} a_{22} = l_{21}u_{12} + u_{22} \Rightarrow u_{22} = a_{22} - l_{21}u_{12} \\[1ex] a_{23} = l_{21}u_{13} + u_{23} \Rightarrow u_{23} = a_{23} - l_{21}u_{13} \end{array} $

Ahora la segunda columna:

$a_{32} = l_{31}u_{12} + l_{32} u_{22} \Rightarrow l_{32} = \dfrac{1}{u_{22}} (a_{32} - l_{31}u_{12})$

• Paso 3:

En la tercera fila:

$a_{33} = l_{31}u_{13} + l_{32}u_{23} + u_{33} \Rightarrow u_{33} = a_{33} - l_{31}u_{13} - l_{32}u_{23}$

Teniéndose ya completadas las dos matrices triangulares.

En general, para una matriz $A$ de dimensión $n \times n$:

$ \begin{array}{l} u_{ij} = a_{ij} - \displaystyle \sum_{k=1}^{i-1} l_{ik} u_{kj} \quad i \leq j \\ l_{ii} = 1 \\ l_{ij} = \dfrac{1}{u_{jj}} \left( a_{ij} - \displaystyle \sum_{k=1}^{j-1} l_{ik} u_{kj} \right) \quad i > j \end{array} $

---

---

En un sistema lineal:

$ \begin{array}{c} A x = b \\[1ex] L \mspace{-2mu} \underbrace{Ux}_y \mspace{-2mu} = b \Rightarrow Ly = b \end{array} $

Entonces:

1.^er paso: Hallar $y$ tal que $Ly = b\,$.

2.º paso: Hallar $x$ tal que $Ux = y\,$.

---

---

4. Norma y condición de una matriz:

1) Norma de un vector, que es una medida de su magnitud, siendo éste:

$ x = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} $

Se denota por $\|x\|$.

Propiedades:

a) $\|x\| \geq 0\,.$

b) $\|x\| = 0$ sólo si $x = 0\,.$

c) $\|\alpha x\| = |\alpha| \|x\|\,,$ $\alpha$ es un escalar.

d) $\|x+y\| \leq \|x\| + \|y\|\,,$ desigualdad triangular.

Se define:

$\|x\|_2 = (x_1^2 + x_2^2 + \dotsb + x_n^2)^{1/2}\,,$   norma euclídea.

Alternativas:

1. $\|x\|_1 = |x_1| + |x_2| + \dotsb + |x_n|$
2. $\|x\|_\infty = \max (|x_1|, |x_2|, \dotsc, |x_n|)\,,$   norma del máximo.

Todas ellas cumplen las propiedades.

---

---

2) Norma de una matriz, siendo ésta:

$ A = \begin{pmatrix} a_{11} & \dots & a_{1n} \\ \vdots & & \vdots \\ a_{n1} & \dots & a_{nn} \end{pmatrix} $

Se define:

$ \|A\| = \max\limits_{\|x\| = 1} \|Ax\| \Rightarrow \left\{ \begin{array}{l} \|A\|_2 \\[1ex] \|A\|_1 \\[1ex] \|A\|_\infty \end{array} \right. $

Que es la cantidad máxima que un vector de longitud (norma) 1, de todos los posibles, se magnifica al ser multiplicado por $A$.

---

---

Propiedades:

a) $\|A\| \geq 0\,.$

b) $\|A\| = 0$ sólo si $A = 0\,.$

c) $\|\alpha A\| = |\alpha| \|A\|\,,$ $\alpha$ es un escalar.

d) $\|A + B\| \leq \|A\|+\|B\|\,.$

e) $\|Ax\| \leq \|A\|\|x\|\,.$

g) $\|A B\| \leq \|A\| \|B\|\,.$

3) Número de condición de una matriz, el cual se define como:

$ \kappa(A) = \|A\| \|A^{-1}\| \Rightarrow \left\{ \begin{array}{l} \kappa_{\infty}(A) \\[1ex] \kappa_2(A) \\[1ex] \kappa_1(A) \end{array} \right. $

---

---

Para un sistema lineal $Ax = b$:

Error $\Delta b \Rightarrow$ Error $\Delta x$

Esto es:

$ \begin{array}{c} A(x + \Delta x) = b + \Delta b \\[1ex] \cancel{Ax} \! + A \Delta x = \! \cancel{b} \! + \Delta b \\[1ex] A \Delta x = \Delta b \\[1ex] \Delta x = A^{-1} \Delta b \end{array} $

Siendo el error de forma relativa (o error relativo):

$\dfrac{\|\Delta x\|}{\|x\|} \,; \dfrac{\|\Delta b\|}{\|b\|}$

Para averiguar su importancia, se empieza por:

$ \begin{array}{c} \|\Delta x\| = \|A^{-1} \Delta b\| \leq \|A^{-1}\| \|\Delta b\| \\[1ex] \dfrac{\|\Delta x\|}{\|x\|} \leq \dfrac{\|A^{-1}\| \|\Delta b\|}{\|x\|} \end{array} $

También:

$ \begin{array}{c} \|b\| = \|Ax\| \leq \|A\| \|x\| \\[1ex] \dfrac{1}{\|x\|} \leq \dfrac{\|A\|}{\|b\|} \end{array} $

Así que:

$\dfrac{\|\Delta x\|}{\|x\|} \leq \dfrac{\|A^{-1}\| \|\Delta b\|}{\|x\|} \leq \underbrace{\|A\| \|A^{-1}\|}_{\kappa(A)} \dfrac{\|\Delta b\|}{\|b\|}$

Por tanto:

$\boxed{\dfrac{\|\Delta x\|}{\|x\|} \leq \kappa(A) \dfrac{\|\Delta b\|}{\|b\|}}$

Siendo:

$\kappa(A) = \|A\|\|A^{-1}\| \geq \|AA^{-1}\| = \|I\|$

Donde $I$ es la matriz identidad, para la cual:

$\|I\| = \max\limits_{\|x\| = 1} \|Ix\| = \max\limits_{\|x\| = 1} \|x\| = 1$

Así pues:

$\kappa(A) \geq 1$

Cuando su valor es grande se dice que es un problema mal condicionado.

---

---

Temario

• <
• >