= Solution
Since $Q^{-1}=Q^T$, the <QR factorization> gives
$$
Ax=b\quad\Longleftrightarrow\quad Rx=Q^Tb.
$$
First compute $y=Q^Tb$ by a <matrix-vector product>, costing $n^2$ scalar multiplications and $n(n-1)$ additions for dense $Q$. Then solve the <upper triangular matrix> system $Rx=y$ by <back substitution>:
$$
\boxed{x_i=\frac{y_i-\sum_{j=i+1}^nr_{ij}x_j}{r_{ii}},\qquad i=n,n-1,\ldots,1.}
$$
Every denominator is nonzero because $R=Q^TA$ is invertible. The <back substitution> costs $n(n-1)$ multiplications and subtractions together, plus $n$ divisions, for $n^2$ <arithmetic operations>. Including $Q^Tb$, the total is $3n^2-n$ <arithmetic operations> under this scalar counting convention, hence \b[$O(n^2)$], with $O$ denoting <Big O notation>. The already supplied <QR factorization> is reused; no <matrix inverse> needs to be computed.
Back to article page
