Operaciones aritméticas de punto de flotante cuando fila reducción de matrices

Question

Una nota numérica en mi álgebra lineal texto establece lo siguiente: "En general, el avance de la fase de reducción de la fila tarda mucho más que el retroceso de la fase. Un algoritmo para resolver un sistema se mide generalmente en flops (o de operaciones de punto flotante). Un flop es una operación aritmética $(+,-,*,/)$ en los dos reales los números de punto flotante. Para un $n\times(n+1)$ matriz, la reducción a la forma escalonada puede tomar $$ \frac{2}{3}n^3+\frac{1}{2}n^2-\frac{7}{6}n\etiqueta{1} $$ flops (que es aproximadamente el $2n^3/3$ flops al $n$ es moderadamente grande-por ejemplo, $n\geq 30$). En contraste, la reducción adicional a la reducción de la forma escalonada de las necesidades en la mayoría de las $n^2$ flops."

No hay ninguna explicación en absoluto cómo el autor se acercó con la expresión en $(1)$. Es evidente que hay una razón para que la expresión y el $n^2$ mencionó al final de la cita. Puede alguien con conocimientos de álgebra lineal o la arquitectura de la pc, etc., explique por qué estas expresiones son el camino? Parece que el autor apenas sacado de la nada.

Answer 1

Las operaciones que intervienen en el $k$th paso de la transformación a REF, donde $k=1,\ldots,n-1$, son: para cada fila $l=k+1,\ldots,n$,

1. calcular el multiplicador de filas: dividir la entrada de $(k,l)$ por pivote de entrada de $(k,k)$;
2. actualización de las entradas de la columna de $k+1,\ldots,n+1$ de la $l$th fila (uno de multiplicación y suma por entrada).

(Hacemos el Punto 1 y el Punto 2 de las filas $k+1,\ldots,n$, por lo que los números de ambos artículos deben ser multiplicados por $n-k$.) Esto da el número de flops en el paso $k$ $$ (n-k)[1+2(n-k+1)]=2k^2-(4n+3)k+n(2n+3) $$ y el número total de flops $$ \sum_{k=1}^{n-1}[2k^2-(4n+3)k+n(2n+3)]=\frac{2}{3}n^3+\frac{1}{2}n^2-\frac{7}{6}n. $$

Las operaciones que intervienen en el $k$th paso de la transformación de la REF a RREF, donde $k=n,n-1,\ldots,1$, son:

1. normalizar la entrada de $(k,k)$; esto implica una división en la entrada de $(k,n+1)$, a partir de la entrada $(k,k)$ hace $1$ y todas las demás entradas de la $k$th fila son cero;
2. actualización de las entradas en las filas $1,\ldots,k-1$ de la columna de $n+1$ (esto le da $k-1$ multiplicaciones y $k-1$ adiciones).

Por lo tanto, para el paso de $k$, tenemos $$ 1+2(k-1)=2k-1 $$ las operaciones y el total de $$ \sum_{k=1}^n(2k-1)=n^2. $$

NOTA: es útil recordar las sumas $$ \sum_{k=1}^n k^2 = \frac{1}{6}n(n+1)(2n+1), \quad \sum_{k=1}^n k = \frac{1}{2}n(n+1). $$