28.2: Eliminación gaussiana dispersa

Última actualización
Guardar como PDF

Page ID: 87719

Masayuki Yano, James Douglass Penn, George Konidaris, & Anthony T Patera
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Esta sección también es muy breve. Como ya describimos en la Unidad III, para resolver el sistema matricial\(A u=f\) en MATLAB solo necesitamos escribir\(u=\mathrm{A} \backslash \mathrm{f}\), el famoso operador de barras traseras. Ahora podemos revelar, armados con el material de la unidad actual, que el operador de barras traseras de hecho realiza la eliminación gaussiana (a excepción de sistemas sobredeterminados, en cuyo caso el problema de mínimos cuadrados se resuelve mediante un algoritmo QR). La diagonal hacia atrás realizará automáticamente el pivotamiento parcial (permutaciones de filas para elegir el pivote de máxima magnitud disponible) para garantizar para una matriz no singular\(K\) que nunca se encuentre un pivote cero y que además la amplificación de los errores numéricos de redondeo (en precisión finita) ) se minimiza.

El caso escaso es igualmente aerodinámico. Si\(A\) es una matriz matemáticamente dispersa y deseamos resolver\(A u=f\) por eliminación gaussiana dispersa como se describe en el capítulo anterior, solo necesitamos asegurarnos de que\(A\) se declare dispersa y luego escribir\(u=A \backslash f\). (En cuanto al producto vector de matriz, no es\(f\) necesario declarar escaso y el resultado no\(u\) será escaso.) En este caso, la diagonal hacia atrás hace más que simplemente eliminar cálculos innecesarios con operandos cero: la barras inversas permutará columnas (un reordenamiento) para minimizar el llenado durante el procedimiento de eliminación. (En cuanto al caso no escaso, también se perseguirán permutaciones de fila, con fines de estabilidad numérica).

El caso del\(A\) SPD es digno de mención. Como ya se indicó, en este caso el proceso de eliminación gaussiana es numéricamente estable sin ninguna permutación de fila. Para una matriz SPD, el operador de barras inversales permutará así las filas de manera similar a las columnas; las columnas, como antes, se permutan para minimizar el relleno, como se describe en el capítulo anterior. En el caso SPD se persigue una variante particular de la eliminación gaussiana, la factorización Cholesky.