- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Hey!
Let $A$ a $n\times n$ matrix with known LU decomposition, let $u\in \mathbb{R}^n, v\in \mathbb{R}^{n+1}$.
Show that the number of multiplications and divisions that are needed to get a LU decomposition of the $(n+1)\times (n+1)$ matrix $$\begin{pmatrix}A & u \\ v^T\end{pmatrix}$$ is at most $O(n^2)$.
To get $U$, we have to eliminate $n$ terms below the main diagonal (which is the elements of $u^T$ except the last element of that row). Each elimination requires computing the row multiplier, which involves division by the pivotal element.
So we have $n$ divisions, or not? :unsure:
Let $A$ a $n\times n$ matrix with known LU decomposition, let $u\in \mathbb{R}^n, v\in \mathbb{R}^{n+1}$.
Show that the number of multiplications and divisions that are needed to get a LU decomposition of the $(n+1)\times (n+1)$ matrix $$\begin{pmatrix}A & u \\ v^T\end{pmatrix}$$ is at most $O(n^2)$.
To get $U$, we have to eliminate $n$ terms below the main diagonal (which is the elements of $u^T$ except the last element of that row). Each elimination requires computing the row multiplier, which involves division by the pivotal element.
So we have $n$ divisions, or not? :unsure:
Last edited by a moderator: