Eficiencia computacional de la descomposición QR

Question

Me cuesta encontrar una referencia para esto: En términos de la notación Big Oh, ¿alguien sabe de alguna expresión para el tiempo de cálculo de los algoritmos comúnmente utilizados para las descomposiciones QR?

Answer 1

Wikipedia dice que la complejidad es $O(n^3)$ operaciones de multiplicación en coma flotante cuando se utilizan los reflejos de los propietarios.

La siguiente tabla indica el número de operaciones en el $k$ -paso de la descomposición QR por la transformación Householder, suponiendo una matriz cuadrada de tamaño $n$ .

$$\begin{array}{c|c|} \text{Operation} & \text{Number of operations in $ k $th step} \\ \hline \text{Multiplications} & 2(n-k+1)^2 \\ \hline \text{Additions} & (n-k+1)^2 + (n-k+1)(n-k)+2 \\ \hline \text{Divisions} & 1 \\ \hline \text{Square Root} & 1 \\ \hline \end{array}$$

La suma de estas cifras sobre el $n-1$ pasos (para una matriz cuadrada de tamaño $n$ ), la complejidad del algoritmo (en términos de multiplicaciones en coma flotante) viene dada por

$$\frac{2}{3}n^3 + n^2+\frac{1}{3}n-2=O(n^3)$$

Sorprendentemente, no he encontrado un análisis de la complejidad de la factorización QR indicada en Golub & van Loan. Qué raro.