5.1: Revisitada la eliminación gaussiana

En esta sección, revisamos la eliminación gaussiana y exploramos algunos problemas para implementarla de la manera sencilla que describimos en la Sección 1.2. En particular, veremos cómo el hecho de que las computadoras solo aproximen las operaciones aritméticas nos puede llevar a encontrar soluciones que están lejos de las soluciones reales. Segundo, exploraremos cuánto trabajo se requiere para implementar la eliminación gaussiana e idear un medio más eficiente para implementarla cuando queremos resolver ecuaciones\(A\mathbf x = \mathbf b\) para varios vectores diferentes\(\mathbf b\text{.}\)

Vista previa Actividad 5.1.1.

Para comenzar, recordemos cómo implementamos la eliminación gaussiana considerando la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrrr} 1 & 2 & -1 & 2\\ 1 & 0 & -2 & 1\\ 3 & 2 & 1 & 0\\ end {array}\ derecha]\ end {ecuación*}

1. ¿Cuál es la operación de primera fila que realizamos? Si la matriz resultante es\(A_1\text{,}\) encontrar una matriz\(E_1\) tal que\(E_1A = A_1\text{.}\)
2. Cuál es la inversa matricial La\(E_1^{-1}\text{?}\) puedes encontrar usando tu técnica favorita para encontrar una inversa matricial. Sin embargo, puede ser más fácil pensar en el efecto que tiene la operación de fila y cómo se puede deshacer.
3. Realice los dos pasos siguientes en el algoritmo de eliminación gaussiana para obtener\(A_3\text{.}\) Representar estos pasos usando multiplicación por matrices\(E_2\) y\(E_3\) para que
   \ begin {ecuación*} E_3E_2E_1A = A_3\ text {.} \ end {ecuación*}
4. Supongamos que necesitamos escalar la segunda fila por\(-2\text{.}\) ¿Cuál es la\(3\times3\) matriz que realiza esta operación de fila por multiplicación izquierda?
5. Supongamos que necesitamos intercambiar la primera y segunda filas. ¿Cuál es la\(3\times3\) matriz que realiza esta operación de fila por multiplicación izquierda?

Pivote parcial

El primer tema que abordaremos es el hecho de que las computadoras no realizan operaciones arithemticas exactamente. Por ejemplo, si le pedimos a Python que evalúe 0.1 + 0.2, reporta 0.30000000000000004 aunque sabemos que el valor verdadero es 0.3. Hay un par de razones para ello.

En primer lugar, las computadoras realizan aritmética usando números base 2, lo que significa que los números que ingresamos en forma decimal, como\(0.1\text{,}\) deben ser convertidos a base 2. Aunque 0.1 tiene una forma decimal simple, su representación en la base 2 es el decimal repetido

\ begin {ecuación*} 0.0001100110011001100110011001100110011001100110011\ lpuntos\ texto {.} \ texto {,}\ final {ecuación*}

Para representar con precisión este número dentro de una computadora requeriría un número infinito de dígitos. Dado que una computadora solo puede contener un número finito de dígitos, necesariamente estamos usando una aproximación cuando simplemente representamos este número en una computadora.

Además, las operaciones aritméticas, como la suma, son propensas al error. Para mantener las cosas simples, supongamos que tenemos una computadora que representa números usando solo tres dígitos decimales. Por ejemplo, el número 1.023 se representaría como 1.02 mientras que 0.023421 sería 0.0234. Si sumamos estos números, tenemos 1.023 + 0.023421 = 1.046421; la computadora reporta esta suma como 1.02 + 0.0234 = 1.04, cuyo último dígito no se redondea correctamente. En términos generales, veremos este problema, que se llama error de redondeo, siempre que agreguemos números de magnitudes señalizantemente diferentes.

Recuerde que la eliminación gaussiana, cuando se aplica a una\(n\times n\) matriz, requiere aproximadamente\(\frac 23 n^3\) operaciones. Si tenemos una\(1000\times1000\) matriz, realizar la eliminación gaussiana requiere aproximadamente mil millones de operaciones, y los errores introducidos en cada operación podrían acumularse. ¿Cómo podemos tener confianza en el resultado final? Nunca podemos evitar por completo estos errores, pero podemos tomar medidas para mitigarlos. En la siguiente actividad se introducirá una de esas técnicas.

Actividad 5.1.2.

Supongamos que tenemos una computadora hipotética que representa números usando solo tres dígitos decimales, como hemos estado discutiendo. Consideraremos el sistema lineal

\ begin {ecuación*}\ begin {alineada} {3} 0.0001x & {} + {} & y & {} = {} & 1\\ x & {} + {} & y & {} = {} & 2\ texto {.}\\ final {alineada}\ final {ecuación*}

1. Demuestre que este sistema tiene la solución única
   \ begin {ecuación*}\ begin {alineado} x & {} = {}\ frac {10000} {9999} = 1.00010001\ ldots,\\ y & {} = {}\ frac {9998} {9999} = 0.99989998\ lpuntos\ texto {.} \ end {alineado}\ end {ecuación*}
2. Si representamos esta solución dentro de nuestra computadora que solo contiene 3 dígitos decimales, ¿qué encontramos para la solución? Esto es lo mejor que podemos esperar encontrar usando nuestra computadora.
3. Imaginemos que usamos nuestra computadora para encontrar la solución usando la eliminación gaussiana; es decir, después de cada operación aritmética, guardamos solo tres dígitos decimales. Nuestro primer paso es multiplicar la primera ecuación por 10000 y restarla de la segunda ecuación. Si representamos números usando solo tres dígitos decimales, ¿qué da esto para el valor de\(y\text{?}\)
4. Al sustituir nuestro valor\(y\) en la primera ecuación, ¿qué encontramos para\(x\text{?}\)
5. Comparar la solución que encontramos en nuestro equipo con la solución real y evaluar la calidad de la aproximación.
6. Ahora modifiquemos el sistema lineal simplemente intercambiando las ecuaciones:
   \ begin {ecuación*}\ begin {alineada} {3} x & {} + {} & y & {} = {} & 2\\ 0.0001x & {} + {} & y & {} = {} & 1\ texto {.}\\ final {alineada}\ final {ecuación*}

   Por supuesto, esto no cambia la solución real. Imaginemos que usamos nuestra computadora para encontrar la solución usando la eliminación gaussiana. Realiza el primer paso donde multiplicamos la primera ecuación por 0.0001 y restamos de la segunda ecuación. ¿Qué da esto\(y\) si representamos números usando solo tres dígitos decimales?

7. Sustituye el valor que encontraste\(y\) en la primera ecuación y resuelve por\(x\text{.}\) Luego compara la solución aproximada encontrada con nuestra hipotética computadora con la solución exacta.
8. ¿Qué enfoque produce la aproximación más precisa?

Esta actividad demuestra cómo los aspectos prácticos de la computación difieren de los teóricos. Sabemos que el orden en que escribimos las ecuaciones no tiene ningún efecto sobre el espacio de solución; el intercambio de filas es una de nuestras tres operaciones de fila permitidas en el algoritmo de eliminación gaussiana. Sin embargo, cuando solo podemos realizar operaciones aritméticas aproximadamente, aplicar intercambios de filas puede mejorar drásticamente la precisión de nuestras aproximaciones.

Si pudiéramos calcular la solución exactamente, encontramos

\ begin {ecuación*} x = 1.00010001\ lpuntos,\ qquad y = 0.99989998\ lpuntos\ texto {.} \ end {ecuación*}

Dado que nuestra computadora hipotética representa números usando solo tres dígitos decimales, nuestra computadora encuentra

\ begin {ecuación*} x\ approx 1.00,\ qquad y\ approx 1.00. \ end {ecuación*}

Esto es lo mejor que podemos esperar hacer con nuestra computadora ya que es imposible representar exactamente la solución.

Cuando las ecuaciones están escritas en su orden original y multiplicamos la primera ecuación por 10000 y restamos de la segunda, encontramos

\ begin {equation*}\ begin {aligned} (1-10000) y & {} = {} 2-10000\\ -9999 y & {} = {} -9998\\ -10000y& {}\ approx {} -10000\\ y & {}\ approx {} 1.00\ text {.}\\ final {alineado}\ final {ecuación*}

De hecho, encontramos el mismo valor para\(y\) cuando intercambiamos las ecuaciones. Aquí multiplicamos la primera ecuación por 0.0001 y restamos de la segunda ecuación. Luego encontramos

\ begin {ecuación*}\ begin {alineado} (1-0.0001) y & {} = {} 2-0.0001\\ -0.9999 y & {} = {} -0.9998\\ -y& {}\ approx {} -1.00\ y & {}\ approx {} 1.00\ text {.}\\ final {alineado}\ final {ecuación*}

La diferencia ocurre cuando sustituimos\(y\approx 1\) en la primera ecuación. Cuando las ecuaciones están escritas en su orden original, tenemos

\ begin {equation*}\ begin {aligned} 0.0001x + 1.00 & {}\ approx {} 1.00\\ 0.0001x & {}\ approx {} 0.00\ x & {}\ approx {} 0.00\ text {.}\\ end {alineado}\ end {alineado}\ end {ecuación*}

Cuando las ecuaciones están escritas en su orden original, encontramos la solución\(x\approx 0.00, y \approx 1.00\text{.}\)

Cuando escribimos la ecuación en el orden opuesto, sin embargo, sustituyendo\(y\approx 1\) en la primera ecuación da

\ begin {equation*}\ begin {aligned} x + 1.00 & {}\ approx {} 2.00\\ x & {}\ approx {} 1.00\ text {.}\\ end {alineado}\ end {equation*}

En este caso, encontramos la solución aproximada\(x\approx 1.00, y\approx1.00\text{,}\) que es la solución más precisa que nuestra hipotética computadora puede encontrar. El simple intercambio del orden de la ecuación produce una solución mucho más precisa.

Podemos entender por qué esto funciona gráficamente. Cada ecuación representa una línea en el plano, y la solución es el punto de intersección. Observe que las pendientes de estas líneas difieren considerablemente.

Cuando las ecuaciones se escriben en su orden original, sustituimos\(y\approx1\) en la ecuación\(0.00001x + y = 1\text{,}\) que es una línea casi horizontal. A lo largo de esta línea, un pequeño cambio en\(y\) conduce a un gran cambio en\(x\text{.}\) La ligera diferencia en nuestra aproximación\(y\approx 1\) del valor exacto\(y=0.9998999\ldots\) conduce a una gran diferencia en la aproximación\(x\approx0\) del valor exacto\(x=1.00010001\ldots\text{.}\)

Si intercambiamos el orden en que se escriben las ecuaciones, sustituimos nuestra aproximación por\(y\approx 1\) la ecuación\(x+y=2\text{.}\) Observe que la pendiente de la línea asociada es\(-1\text{.}\) En esta línea, un pequeño cambio en\(y\) conduce a un cambio relativamente pequeño en\(x\) también. Por lo tanto, la diferencia en nuestra aproximación\(y\approx1\) con respecto al valor exacto conduce a solo una pequeña diferencia en la aproximación\(x\approx1\) con respecto al valor exacto.

Este ejemplo motiva la técnica que suelen utilizar las computadoras para realizar la elimación gaussiana. En la práctica, solo necesitamos realizar un intercambio de filas cuando se produce un cero en una posición de pivote, como

\ begin {ecuación*}\ left [\ begin {array} {rrrr} 1 & -1 & 2 & 2\\ 0 & 0 & -3 & 1\\ 0 & 2 & 2 & -3\\ end {array}\ right]\ text {.} \ end {ecuación*}

En su lugar, realizaremos un intercambio de filas para poner la entrada que tenga la entrada de valor absoluto más grande posible en la posición de pivote. Por ejemplo, al realizar la eliminación gaussiana en la siguiente matriz, comenzamos intercambiando la primera y tercera fila para que la entrada superior izquierda tenga el mayor valor absoluto posible.

\ begin {ecuación*}\ left [\ begin {array} {rrrr} 2 & 1 & 2 & 3\\ 1 & -3 & -2 & 1\\ -3 & 2 & 3 & -2\\ end {array}\ derecha]\ sim\ left [\ begin {array} {rrrr} -3 & 2 & 3 & -2\\ 1 & -3 & -2 & 1\\ 2 & 1 & 2 & 3\\\ end {array}\ derecha]\ text {.} \ end {ecuación*}

Esta técnica se llama pivotamiento parcial, y significa que, en la práctica, realizaremos muchas más operaciones de intercambio de filas de las que normalmente hacemos al calcular exactamente a mano.

\(LU\)factorizaciones

En la Subsección 1.3.3, vimos que el número de operaciones aritméticas necesarias para realizar la eliminación gaussiana en una\(n\times n\) matriz es aproximadamente\(\frac23 n^3\text{.}\) Esto significa que una\(1000\times1000\) matriz, requiere alrededor de dos tercios de mil millones de operaciones.

Supongamos que tenemos dos ecuaciones,\(A\mathbf x = \mathbf b_1\) y\(A\mathbf x = \mathbf b_2\text{,}\) que nos gustaría resolver. Por lo general, formaríamos matrices aumentadas\(\left[\begin{array}{c|c} A & \mathbf b_1 \\ \end{array}\right]\)\(\left[\begin{array}{c|c} A & \mathbf b_2 \\ \end{array}\right]\) y aplicaríamos la eliminación gaussiana. Por supuesto, los pasos que realizamos en estos dos cómputos son casi idénticos. ¿Hay alguna manera de almacenar algunos de los cómputos que realizamos para reducirlos\(\left[\begin{array}{c|c} A & \mathbf b_1 \\ \end{array}\right]\) y reutilizarlos en la resolución de ecuaciones posteriores? La siguiente actividad nos apuntará en la dirección correcta.

Actividad 5.1.3.

Consideraremos la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrr} 1 & 2 & 1\\ -2 & -3 & -2\\ 3 & 7 & 4\\ end {array}\ derecha]\ end {ecuación*}

y comenzar a realizar la eliminación gaussiana.

1. Realice operaciones de reemplazo de dos filas para encontrar la matriz equivalente de fila
   \ begin {ecuación*} A' =\ left [\ begin {array} {rrr} 1 & 2 & 1\\ 0 & 1 & 0\\ 0 & 1 & 1\\\ end {array}\ right]\ text {.} \ end {ecuación*}

   Encuentra matrices elementales\(E_1\) y\(E_2\) que realizan estas dos operaciones para que\(E_2E_1 A = A'\text{.}\)

2. Realizar un reemplazo de tercera fila para encontrar la matriz triangular superior
   \ begin {ecuación*} U =\ left [\ begin {array} {rrr} 1 & 2 & 1\\ 0 & 1 & 0\\ 0 & 0 & 1\\\ end {array}\ right]\ text {.} \ end {ecuación*}

   Encuentra la matriz elemental de\(E_3\) tal manera que\(E_3E_2E_1A = U\text{.}\)

3. Podemos escribir\(A=E_1^{-1}E_2^{-1}E_3^{-1} U\text{.}\) Encuentra las matrices inversas\(E_1^{-1}\text{,}\)\(E_2^{-1}\text{,}\) y\(E_3^{-1}\) y el producto\(L = E_1^{-1}E_2^{-1}E_3^{-1}\text{.}\) Luego verificar que\(A=LU\text{.}\)
4. Supongamos que queremos resolver la ecuación\(A\mathbf x = \mathbf b = \threevec4{-7}{12}\text{.}\) Vamos a escribir
   \ begin {ecuación*} A\ mathbf x = LU\ mathbf x = L (U\ mathbf x) =\ mathbf b\ end {ecuación*}

   e introducir un vector desconocido\(\mathbf c\) tal que\(U\mathbf x = \mathbf c\text{.}\) Find\(\mathbf c\) señalando eso\(L\mathbf c = \mathbf b\) y resolviendo esta ecuación.

5. Ahora que hemos encontrado\(\mathbf c\text{,}\) encontrar\(\mathbf x\) resolviendo\(U\mathbf x = \mathbf c\text{.}\)
6. Usa la factorización\(A=LU\) y este proceso de dos pasos, resuelve la ecuación\(A\mathbf x = \threevec{2}{-2}{7}\text{.}\)

Esta actividad introduce un método para factorizar una matriz\(A\) como producto de dos matrices triangulares,\(A=LU\text{,}\) donde\(L\) es triangular inferior y\(U\) es triangular superior. La clave para encontrar esta factorización es representar las operaciones de fila que aplicamos en el algoritmo de eliminación gaussiana a través de la multiplicación por matrices elementales.

Comenzando con la matriz\(A = \left[\begin{array}{rrr} 1 & 2 & 1 \\ -2 & -3 & -2 \\ 3 & 7 & 4 \\ \end{array}\right] \text{,}\) multiplicamos la primera fila por\(2\) y agregamos el resultado a la segunda fila. El resultado se obtiene multiplicando\(A\) por la matriz\(E_1 = \left[\begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array}\right] \text{.}\) Observe que la inversa de\(E_1\) es\(E_1^{-1} = \left[\begin{array}{rrr} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 0 \\ \end{array}\right] \text{.}\) No se requiere cómputos para encontrar para\(E_1^{-1}\text{;}\) deshacer el efecto de simplemente\(E_1\text{,}\) multiplicamos la primera fila por\(-2\text{,}\) en lugar de\(2\text{,}\) y la agregamos a la segunda fila. En la práctica, para encontrar la inversa de una matriz elemental correspondiente a una operación de reemplazo de fila, simplemente cambiamos el signo del número por debajo de la diagonal. ¡Eso es fácil!

Asimismo, los siguientes reemplazos de dos filas son realizados por

\ begin {ecuación*} E_2 =\ left [\ begin {array} {rrr} 1 & 0 & 0\\ 0 & 1 & 0\\ -3 & 0 & 1\\\ end {array}\ derecha],\ qquad E_3 =\ left [\ begin {array} {rrr} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 1\\ fin array}\ derecho]\ texto {.} \ end {ecuación*}

A partir de aquí, encontramos\(A = E_1^{-1}E_2^{-1}E_3^{-1} U\) para que

\ begin {ecuation*} A =\ left [\ begin {array} {rrr} 1 & 2 & 1\\ -2 & -3 & -2\\ 3 & 7 & 4\\ end {array}\\ end {array}\ right] = LU =\ left [\ begin {array} {rrr} 1 & 0 & 0\\ -2 & 1 & 0\ 3 & 1 & 1\ end {array}\ derecha] izquierda\ [\ begin {array} {rrr} 1 & 2 & 1\\ 0 & 1 & 0\\ 0 & amp; 0 & 1\\\ end {array}\ derecha]\ text {.} \ end {ecuación*}

Si queremos resolver la ecuación primero\(A\mathbf x = LU\mathbf x = \mathbf b\text{,}\) resolvemos resolviendo\(L\mathbf c = \mathbf b\text{.}\) Una vez que tenemos\(\mathbf c\text{,}\) resolvemos\(U\mathbf x = \mathbf c\) para el vector\(\mathbf x\text{,}\) que es la solución a la ecuación original\(A\mathbf x = \mathbf b\text{.}\) En nuestro ejemplo,\(U\mathbf x = \mathbf c\)

\ begin {ecuación*}\ begin {alineado}\ L\ mathbf c =\ threevec {4} {-7} {12}, &\ qquad\ mathbf c =\ threevec {4} {1} {-1}\\\ U\ mathbf x =\ mathbf c=\ threevec {4} {1} {-1}, &\ qquad\ mathbf x =\ tresevec {3} {1} {-1}\ texto {.}\\\ final {alineado}\ final {ecuación*}

Si queremos resolver\(A\mathbf x = \mathbf b\) por un lado derecho diferente simplemente\(\mathbf b\text{,}\) podemos repetir este proceso de dos pasos.

Ahora hemos introducido las\(LU\) factorizaciones como técnica para resolver ecuaciones\(A\mathbf x = \mathbf b\text{,}\) pero aún tenemos que explicar por qué son útiles. Se hace evidente cuando consideramos el tipo de ecuaciones que estamos resolviendo; por ejemplo,\(L\mathbf c = \mathbf b\) en nuestro ejemplo tiene la forma

\ begin {ecuación*}\ left [\ begin {array} {rrr} 1 & 0 & 0\\ -2 & 1 & 0\\ 3 & 1 & 1 & 1\ end {array}\ right]\ mathbf c =\ tresevec4 {-7} {12}\ text {.} \ end {ecuación*}

Debido a que\(L\) es una matriz triangular inferior, contiene muchos ceros. De hecho, somos capaces de leer el primer componente de\(\mathbf c\) directamente de las ecuaciones: Entonces\(c_1 = 4\text{.}\) tenemos\(-2c_1+c_2 = -7\text{,}\) cuál da\(c_2 = 1\text{,}\) y\(3c_1 + c_2 + c_3 = 12\text{,}\) cuál da\(c_3=-1\text{.}\) Como esto muestra, resolver ecuaciones que involucran matrices triangulares es bastante fácil porque esencialmente solo necesitamos realizar una secuencia de sustituciones.

De hecho, resolver una ecuación con una matriz\(n\times n\) triangular requiere aproximadamente\(\frac 12 n^2\) operaciones. Una vez que tenemos la factorización\(A=LU\text{,}\) resolvemos la ecuación\(A\mathbf x=\mathbf b\) resolviendo dos ecuaciones que involucran matrices triangulares, lo que requiere sobre\(n^2\) operaciones. Por ejemplo, si\(A\) es una\(1000\times1000\) matriz, resolvemos la ecuación\(A\mathbf x = \mathbf b\) usando alrededor de un millón de pasos. El compara con la tercera de mil millones de operaciones que necesitamos para realizar la eliminación gaussiana. Eso representa un ahorro significativo. Por supuesto, primero tenemos que encontrar la\(LU\) factorización de\(A\) y esto requiere aproximadamente la misma cantidad de trabajo que realizar la eliminación gaussiana. Sin embargo, una vez que tenemos la\(LU\) factorización, podemos usarla\(A\mathbf x=\mathbf b\) para resolver diferentes lados de la mano derecha\(\mathbf b\text{.}\)

Nuestra discusión hasta el momento ha ignorado un tema, sin embargo. Recuerde que a veces tenemos que realizar operaciones de intercambio de filas además del reemplazo de filas. Un intercambio de filas típico está representado por la multiplicación por una matriz como

\ begin {ecuación*} P =\ left [\ begin {array} {rrr} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\\ end {array}\ right]\ text {,}\ end {ecuación*}

que tiene el efecto de intercambiar la primera y la tercera fila. Observe que esta matriz no es triangular por lo que realizar un intercambio de filas arruinará la\(LU\) factorización que buscamos. Aquí no daremos los detalles, pero los paquetes de software de álgebra lineal proporcionan una matriz\(P\) que describe cómo se permutan las filas en el proceso de eliminación gaussiana. En particular, escribiremos\(PA = LU\text{,}\) dónde\(P\) está una matriz de permutación,\(L\) es triangular inferior, y\(U\) es triangular superior.

Por lo tanto, para resolver la ecuación primero\(A\mathbf x = \mathbf b\text{,}\) multiplicamos ambos lados por\(P\) para obtener

\ begin {ecuación*} PA\ mathbf x = LU\ mathbf x = P\ mathbf b\ texto {.} \ end {ecuación*}

Es decir, multiplicamos\(\mathbf b\) por\(P\) y luego encontramos\(\mathbf x\) usando la factorización:\(L\mathbf c = P\mathbf b\) y\(U\mathbf x = \mathbf c\text{.}\)

Actividad 5.1.4.

Sage creará\(LU\) factorizaciones; una vez que tengamos una matriz A, escribimos P, L, U = A.LU () para obtener las matrices\(P\text{,}\)\(L\text{,}\) y\(U\) tal que\(PA = LU\text{.}\)

1. En la actividad anterior, encontramos la\(LU\) factorización
   \ begin {ecuation*} A =\ left [\ begin {array} {rrr} 1 & 2 & 1\\ -2 & -3 & -2\\ 3 & 7 & 4\\ end {array}\\ end {array}\ right] = LU =\ left [\ begin {array} {rrr} 1 & 0 & 0\\ -2 & 1 & 0\ 3 & 1 & 1\ end {array}\ derecha] izquierda\ [\ begin {array} {rrr} 1 & 2 & 1\\ 0 & 1 & 0\\ 0 & amp; 0 & 1\\\ end {array}\ derecha]\ text {.} \ end {ecuación*}

   Usando Sage, defina la matriz\(A\) y luego pida a Sage la\(LU\) factorización. ¿Cuáles son las matrices\(P\text{,}\)\(L\text{,}\) y\(U\text{?}\)

   Observe que Sage encuentra una\(LU\) factorización diferente a la que encontramos en la actividad anterior. Esto se debe a que Sage utiliza el pivotamiento parcial, como se describe en el apartado anterior, cuando realiza la eliminación gaussiana. Esto se refleja en el hecho de que la permutación no\(P\) es la identidad.

2. Definir el vector\(\mathbf b = \threevec4{-7}{12}\) en Sage y computar\(P\mathbf b\text{.}\)
3. Usa las matrices L y U para resolver\(L\mathbf c = P\mathbf b\) y\(U\mathbf x = \mathbf c\text{.}\) deberías encontrar la misma solución\(\mathbf x\) que encontraste en la actividad anterior.
4. Usa la factorización para resolver la ecuación\(A\mathbf x = \threevec{11}{-17}{35}\text{.}\)
5. ¿Cómo nos muestra la factorización que\(A\) es invertible y que, por lo tanto, cada ecuación\(A\mathbf x=\mathbf b\) tiene una solución única?
6. Supongamos que tenemos la matriz
   \ begin {ecuación*} A =\ left [\ begin {array} {rrr} 3 & -1 & 2\\ 2 & -1 & 1\\ 2 & 1\\ 2 & 1 & 3\\ end {array}\ right]\ text {.} \ end {ecuación*}

   Usa Sage para encontrar la\(LU\) factorización. Explique cómo la factorización muestra que no\(A\) es invertible.

7. Considerar la matriz
   \ begin {ecuación*} A =\ left [\ begin {array} {rrrr} -2 & 1 & 2 & -1\\ 1 & -1 & 0 & 2\\ 3 & 2 & -1 & 0\\ end {array}\ derecha]\ end {ecuación*}

   y encontrar su\(LU\) factorización. Explique por qué\(A\) y\(U\) tenga el mismo espacio nulo y utilice esta observación para encontrar una base para\(\nul(A)\text{.}\)

Resumen

Volvimos a la eliminación gaussiana, que hemos utilizado como herramienta primaria para encontrar soluciones a sistemas lineales, y exploramos su practicidad como herramienta de computación, tanto en términos de precisión numérica como esfuerzo computacional.

• Vimos que la precisión de los cálculos implementados en una computadora podría mejorarse mediante el pivotamiento parcial, una técnica que realiza intercambios de filas para que la entrada en una posición de pivote tenga la mayor magnitud posible.
• Comenzando con una matriz se\(A\text{,}\) utilizó el algoritmo de eliminación gaussiana para escribir\(PA = LU\text{,}\) dónde\(P\) está una matriz de permutación,\(L\) es triangular inferior y\(U\) es triangular superior.
• Encontrar esta factorización implica aproximadamente tanto trabajo como realizar la eliminación gaussiana. Sin embargo, una vez que tenemos la factorización, somos capaces de resolver rápidamente ecuaciones de la forma\(A\mathbf x = \mathbf b\) resolviendo primero\(L\mathbf c = P\mathbf b\) y luego\(U\mathbf x = \mathbf c\text{.}\)

Ejercicios 5.1.4Ejercicios

1

En esta sección, vimos que los errores cometidos en la aritmética informática pueden producir soluciones aproximadas que están lejos de las soluciones exactas. Aquí hay otro ejemplo en el que esto puede suceder. Considerar la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {cc} 1 & 1\\ 1 & 1.0001\\\ end {array}\ right]\ text {.} \ end {ecuación*}

1. Encuentra la solución exacta a la ecuación\(A\mathbf x = \twovec{2}{2}\text{.}\)
2. Supongamos que este sistema lineal surge en medio de un cálculo mayor excepto que, debido a algún error en el cálculo del lado derecho de la ecuación, nuestro ordenador piensa que queremos resolver\(A\mathbf x = \ctwovec{2}{2.0001}\text{.}\) Encuentra la solución a esta ecuación y compararla con la solución de la ecuación en la anterior parte de esta exericse.

Observe cómo un pequeño cambio en el lado derecho de la ecuación conduce a un gran cambio en la solución. En este caso, decimos que la matriz\(A\) está mal condicionada porque las soluciones son extremadamente sensibles a pequeños cambios en el lado derecho de la ecuación. Aunque no lo haremos aquí, es posible crear una medida de la matriz que nos diga cuándo una matriz está mal condicionada. Lamentablemente, no hay mucho que podamos hacer para remediar este problema.

2

En esta sección, encontramos la\(LU\) factorización de la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrr} 1 & 2 & 1\\ -2 & -3 & -2\\ 3 & 7 & 4\\ end {array}\ derecha]\ end {ecuación*}

en una de las actividades, sin utilizar pivotamiento parcial. Aplique una secuencia de operaciones de fila, ahora usando pivotamiento parcial, para encontrar una matriz triangular superior\(U\) que sea fila equivalente a\(A\text{.}\)

3

En los siguientes ejercicios, utilice las\(LU\) factorizaciones dadas para resolver las ecuaciones\(A\mathbf x = \mathbf b\text{.}\)

1. Resolver la ecuación
   \ begin {ecuación*} A\ mathbf x =\ left [\ begin {array} {rr} 1 & 0\\ -2 & 1\\\ end {array}\ right]\ left [\ begin {array} {rr} 3 & 1\\ 0 & -2\\ end {array}\ right]\ mathbf x =\ twovec {-3} {0}\ text {.} \ end {ecuación*}
2. Resolver la ecuación
   \ begin {ecuación*} A\ mathbf x =\ left [\ begin {array} {rrr} 1 & 0 & 0\\ -2 & 1 & 0\\ -1 & 2 & 1\\\ end {array}\ right]\ left [\ begin {array} {rrr} 2 & 1 & 0\\ 0 & -1 & 3\\ 0 & 0 & 1\\\ end {array} derecha\]\ mathbf x =\ tresevec {5} {-5} {7}\ texto {.} \ end {ecuación*}

4

Usa Sage para resolver la siguiente ecuación encontrando una\(LU\) factorización:

\ begin {ecuación*}\ left [\ begin {array} {rrr} 3 & 4 & -1\\ 2 & 4 & 1\\ -3 & 1 & 4\\\ end {array}\\ right]\ mathbf x =\ threevec {-3} {-3} {-4}\ text {.} \ end {ecuación*}

5

Aquí hay otro problema con la aritmética computacional aproximada que encontraremos en la siguiente sección. Considerar la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrr} 0.2 & 0.2 & 0.4\\ 0.2 & 0.3 & 0.1\\ 0.6 & 0.5 & 0.5\\ end {array}\ right]\ text {.} \ end {ecuación*}

1. Observe que se trata de una matriz estocástica positiva. ¿Qué sabemos de los valores propios de esta matriz?
2. Usa Sage para definir la matriz\(A\) usando decimales como 0.2 y la matriz de\(3\times3\) identidad\(I\text{.}\) Pide a Sage para calcular\(B = A-I\) y encontrar la forma de escalón de fila reducida de\(B\text{.}\)
3. ¿Por qué es incorrecto el cálculo que Sage realizó?
4. Explicar por qué es problemático usar una computadora para encontrar los vectores propios de una matriz\(A\) encontrando una base para\(\nul(A-\lambda I)\).

6

En la práctica, rara vez se encuentra la inversa de una matriz\(A\text{.}\) Se requiere un esfuerzo considerable para calcular, y podemos resolver cualquier ecuación de la forma\(A\mathbf x = \mathbf b\) usando una\(LU\) factorización, lo que significa que la inversa no es necesaria. En cualquier caso, la mejor manera de calcular una inversa es usando una\(LU\) factorización, como demuestra esta exericse.

1. Supongamos que\(PA = LU\text{.}\) explicar por qué\(A^{-1} = U^{-1}L^{-1}P\text{.}\)

   Dado que\(L\) y\(U\) son triangulares, encontrar sus inversas es relativamente eficiente. Eso hace que este sea un medio efectivo para encontrar\(A^{-1}\text{.}\)

2. Considerar la matriz
   \ begin {ecuación*} A =\ left [\ begin {array} {rrr} 3 & 4 & -1\\ 2 & 4 & 1\\ -3 & 1 & 4\\\ end {array}\ right]\ text {.} \ end {ecuación*}

   Encuentra la\(LU\) factorización de\(A\) y úsalo para encontrar\(A^{-1}\text{.}\)

7

Considerar la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrrr} a & a & a & a\\ a & b & b & b\\ a & b & b & c & c\\ a & b & c & d\\ end {array}\ right]\ text {.} \ end {ecuación*}

1. Encuentra la\(LU\) factorización de\(A\text{.}\)
2. ¿En qué condiciones\(a\text{,}\)\(b\text{,}\)\(c\text{,}\) y\(d\) garantía que\(A\) es invertible?

8

En la\(LU\) factorización de una matriz, las entradas diagonales de\(L\) son todas\(1\) mientras que las entradas diagonales de no\(U\) son necesariamente\(1\text{.}\) Este ejercicio explorará esa observación considerando la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrr} 3 & 1 & 1\\ -6 & -4 & -1\\ 0 & -4 & 1\\\ end {array}\ right]\ text {.} \ end {ecuación*}

1. Realizar eliminación gaussiana sin pivotar parcial para encontrar\(U\text{,}\) una matriz triangular superior que sea fila equivalente a\(A\text{.}\)
2. Las entradas diagonales de\(U\) se llaman pivotes. Explique por qué\(\det A\) es igual al producto de los pivotes.
3. Qué es\(\det A\) para nuestra matriz\(A\text{?}\)
4. De manera más general, si hemos\(PA=LU\text{,}\) explicado por qué\(\det A\) es igual a más o menos el producto de los pivotes.

9

Por favor, proporcione una justificación a sus respuestas a estas preguntas.

1. En esta sección, nuestra hipotética computadora solo podía almacenar números usando 3 decimales. La mayoría de las computadoras pueden almacenar números usando 15 o más decimales. ¿Por qué todavía necesitamos preocuparnos por la precisión de nuestros cálculos a la hora de resolver sistemas de ecuaciones lineales?
2. Encontrar la\(LU\) factorización de una matriz\(A\) es aproximadamente la misma cantidad de trabajo que encontrar su forma de escalón de fila reducida. ¿Por qué es útil entonces la\(LU\) factorización?
3. ¿Cómo podemos detectar si una matriz es invertible a partir de su\(LU\) factorización?

10

Considerar la matriz

\ begin {ecuación*} A =\ left [\ begin {array} {rrrr} -1 & 1 & 0 & 0\\ 1 & -2 & 1 & 0\\ 0 & 0\\ 0 & 1 & -2 & 1\\ 0 & 0 & -1 & 1\\ end {array}\ right]\ text {.} \ end {ecuación*}

1. Encuentra la\(LU\) factorización de\(A\text{.}\)
2. Utilice la factorización para encontrar una base para\(\nul(A)\text{.}\)
3. Hemos visto eso\(\nul(A) = \nul(U)\text{.}\) ¿Es cierto que\(\col(A) = \col(L)\text{?}\)