Complejidad temporal de la descomposición LU

Question

Estoy tratando de derivar la complejidad temporal de la descomposición LU para una matriz de $n \times n$.

Eliminar la primera columna requerirá $n$ sumas y $n$ multiplicaciones para $n-1$ filas. Por lo tanto, el número de operaciones para la primera columna es $2n(n-1)$. Para la segunda columna, tenemos $n-1$ sumas y $n-1$ multiplicaciones, y lo hacemos para $(n-2)$ filas dándonos $2(n-1)(n-2)$. Por lo tanto, el número total de operaciones requeridas para la descomposición completa se puede escribir como

$$ \sum_i^n 2(n-i) (n-i+1) $$

¿Cómo llegamos de esta suma a un costo total de $\frac{2}{3}n^3$?

Answer 1

Una transformación fácil ($j = n-i+1$) muestra fácilmente que \begin{align} \sum_{i=1}^n 2(n-i) (n-i+1) &= 2 \sum_{j=0}^{n-1}j(j+1)\\ &= 2 \sum_{j=0}^{n-1}(j^2+j)\\ &= 2 \left(\frac{1}{3} n^{3} - \frac{1}{3} n\right) \end{align>

Luego, dado que estamos interesados únicamente en el comportamiento asintótico, eliminamos la parte $\frac{2}{3}n$, y lo que queda es $\frac{2}{3} n^{3}$.

Answer 2

A continuación está la esencia. Espero que la notación ligeramente más limpia pueda ayudar a nuestra memoria.

$\sum_i^n 2(n-i) (n-i+1)\approx2\sum n^2\approx2\int x^2dx\approx\frac{2}{3}x^3$

$\approx$ está en el sentido del coeficiente del término superior.

Answer 3

Bueno, $$ 2\sum_i^n (n-i)(n-i)+(n-i) = 2\sum_i^n (n-i)^2+2\sum_i^n(n-i) $$

Ahora, reindexemos estas sumas hacia atrás para que se vea bonito. $$ 2\sum_i^n (i)^2+2\sum_i^n(i) $$

Ahora, si conoces un poco de inducción (o wolfram alpha) puedes demostrar que $$ \sum_i^n (i)^2 = n^3/3+n^2/2+n/6 $$ y $\sum_i^n i$ es a lo sumo $n^2$. Así que tenemos $\frac{2}{3}n^3$