26.3: General\(n \times n\) Systems

Ahora consideremos un sistema\(n \times n\) lineal general. Nuevamente utilizaremos un enfoque sistemático de dos pasos: eliminación gaussiana y sustitución de espalda:

Esta vez, vamos a prestar especial atención al conteo de operaciones requerido para cada paso. Además, utilizaremos la representación gráfica mostrada en la Figura\(26.4\) para facilitar la discusión. En la figura, el azul representa (en general) una entrada distinta de cero, el blanco representa una entrada cero, el cuadrado rojo representa el pivote, los cuadrados naranjas identifican las filas de trabajo, las regiones sombreadas representan las filas o columnas de pivotes ya procesadas, y las regiones no sombreadas representan las filas y columnas de pivotes aún no procesadas.

Como antes, el primer paso de la eliminación gaussiana identifica la primera ecuación (eqn 1) como la ecuación de pivote y elimina el primer coeficiente (columna 1) de la ecuación 2 a la eqn\(n\). A cada una de esas filas, le sumamos la fila de pivote apropiadamente escalada (determinada por la relación del primer coeficiente de la fila y el pivote). Debemos escalar (es decir, multiplicar) y sumar\(n\) coeficientes, por lo que la eliminación del primer coeficiente requiere\(2 n\) operaciones por fila. Dado que hay\(n-1\) filas para trabajar, el\[\begin{aligned} & \operatorname{STEP~1:~} \underset{n \times n}{A} \underset{n \times 1}{u}=\underset{n \times 1}{f} \rightarrow \underset{n \times n}{U} \underset{n \times 1}{u}=\underset{n \times 1}{\hat{f}} \end{aligned}\] PASO 2: conteo\[\begin{aligned} & U u=\hat{f} \quad \Rightarrow \quad u \end{aligned}\] total de operaciones para la eliminación de la columna 1 de eqn 2 a eqn\(n\) es\(2 n(n-1) \approx 2 n^{2}\). La figura 26.4 (b) ilustra el proceso de eliminación trabajando en la cuarta fila. La figura\(26.4(\mathrm{c})\) muestra la matriz parcialmente procesada con ceros en la primera columna:\(U\) a-a-ser después del primer paso, i.e\(\tilde{U}(k=1)\).

En el segundo paso, identificamos la segunda ecuación como la ecuación de pivote. La eliminación de la columna 2 de eqn 3 a través de eqn\(n\) requiere la adición de un\((n-1)\) -vector - una versión apropiadamente escalada de la fila de pivote de\(\tilde{U}(k=1)\) - de la fila dada. Dado que hay\(n-2\) filas para trabajar, el recuento total de operaciones para la eliminación de la columna 2 de eqn 3 a través de eqn\(n\) es\(2(n-1)(n-2) \approx 2(n-1)^{2}\). Obsérvese que el trabajo requerido para la eliminación del segundo coeficiente en este segundo paso es menor que el trabajo requerido para la eliminación del primer coeficiente en el primer paso porque 1) no alteramos la primera fila (es decir, hay una fila menos de la que eliminar el coeficiente) y 2) la primer coeficiente de todas las filas de trabajo ya se han establecido en cero. En otras palabras, estamos trabajando en el\((n-1) \times(n-1)\) subbloque inferior de la matriz original, eliminando el primer coeficiente del subbloque. Esta interpretación del subbloque del proceso de eliminación es clara a partir de las Figuras 26.4 (c) y 26.4 (d); debido a que el primer pivote ya ha sido procesado, solo necesitamos trabajar en el área no sombreada de la matriz.

En general, en el\(k^{\text {th }}\) paso de eliminación gaussiana, utilizamos la\(k^{\text {th }}\) fila para eliminar el\(k^{\text {th }}\) coeficiente de eqn\(k+1\) a través de eqn\(n\), trabajando en el\((n-k+1) \times(n-k+1)\) sub-bloque. Así, el conteo de operaciones para el paso es\(2(n-k+1)\). Sumando el trabajo requerido para el primero al\(n^{\text {th }}\) paso, el recuento total de operaciones para la eliminación gaussiana es\[2 n^{2}+2(n-1)^{2}+\cdots+2 \cdot 3^{2}+2 \cdot 2^{2} \approx \sum_{k=1}^{n} 2 k^{2} \approx \frac{2}{3} n^{3} \text { FLOPs }\] Tenga en cuenta que el costo de la eliminación gaussiana crece bastante rápido con el tamaño del problema: como el tercer poder de\(n\). La matriz final triangular superior,\(U=\tilde{U}(k=n)\), se muestra en la Figura 26.4 (f).

Durante el proceso de eliminación gaussiana, también debemos construir el lado derecho modificado\(\hat{f}\). Al eliminar el primer coeficiente, modificamos el lado derecho de eqn 2 a través de\(n(n-1\) ecuaciones eqn), cada una requiriendo dos operaciones para multiplicar y sumar, resultando en operaciones\(2(n-1) \approx 2 n\) totales. En general, el\(k^{\text {th }}\) paso de eliminación gaussiana requiere la modificación del\((n-k)\) subvector -en el lado derecho. Así, el recuento total de operación para la construcción del lado derecho es\[2 n+2(n-1)+\cdots+2 \cdot 3+2 \cdot 2 \approx \sum_{k=1}^{n} 2 k \approx n^{2} \text { FLOPs }\] A medida que el costo para construir las escalas del lado derecho modificado como\(n^{2}\), se vuelve insignificante en comparación con\(2 n^{3} / 3\) las operaciones requeridas para la manipulación de la matriz para una gran \(n\). Así, concluimos que el costo total de la eliminación gaussiana, incluyendo la construcción del lado derecho modificado, es\(2 n^{3} / 3\).

Ahora consideremos el conteo de operaciones de sustitución de espalda. Recordemos que el sistema triangular\(n \times n\) superior toma la forma\[\left(\begin{array}{ccccc} U_{11} & U_{12} & \cdots & \cdots & U_{1 n} \\ & U_{22} & & & U_{2 n} \\ & \ddots & & \vdots \\ & 0 & & U_{n-1 n-1} & U_{n-1 n} \\ & & & U_{n n} \end{array}\right)\left(\begin{array}{c} u_{1} \\ u_{2} \\ \vdots \\ u_{n-1} \\ u_{n} \end{array}\right)=\left(\begin{array}{c} \hat{f}_{1} \\ \hat{f}_{2} \\ \vdots \\ \hat{f}_{n-1} \\ \hat{f}_{n} \end{array}\right) .\] Procedemos a resolver para las incógnitas a\(u_{1}, \ldots, u_{n}\) partir de la última desconocida\(u_{n}\) usando la\(n^{\text {th }}\) ecuación y resolviendo secuencialmente para\(u_{n-1}, \ldots, u_{1}\) en eso orden. Esquemáticamente, el proceso de solución toma la forma\[\begin{array}{rlr} \text { eqn } n \text { : } & U_{n n} u_{n}-\hat{f}_{n} \Rightarrow u_{n}=\frac{\hat{f}_{n}}{U_{n n}} \\ \text { eqn } n-1: & U_{n-1 n-1} u_{n-1}+U_{n-1 n} u_{n}=\hat{f}_{n-1} \\ & \Downarrow \\ \vdots & U_{n-1 n-1} u_{n-1}=\hat{f}_{n-1}-U_{n-1 n-1} u_{n-1} \Rightarrow u_{n-1} \\ \text { eqn 1: } & U_{11} u_{1}+U_{12} u_{2}+\cdots+U_{1 n} u_{n}=\hat{f}_{1} \\ & \Downarrow \\ U_{11} u_{1}=\hat{f}_{1}-U_{12} u_{2}-\cdots-U_{1 n} u_{n} & \Rightarrow u_{1} . \end{array}\] Resolver para\(u_{n}\) requiere una operación. Resolver para\(u_{n-1}\) requiere un par multiplicación-resta (dos operaciones) y una división. En general, resolver para\(u_{k}\) requiere\((n-k)\) multiplicaciónpares de resta (\(2(n-k)\)operaciones) y una división. Sumando todas las operaciones, el recuento total de operaciones para la sustitución posterior es\[1+(1+2)+(1+2 \cdot 2)+\cdots+(1+2(n-1)) \approx \sum_{k=1}^{N} 2 k \approx n^{2} \text { FLOPs } .\] Tenga en cuenta que el costo del paso de sustitución posterior se escala como la segunda potencia del tamaño del problema\(n\); por lo tanto, el costo de la sustitución posterior se vuelve insignificante en comparación con el de la eliminación gaussiana para un grande\(n\).