Questions regarding the numerical method LU decomposition to decompose a matrix into the multiplication of two triangular matrices: A lower triangle matrix and an upper triangular matrix
Questions tagged [lu-decomposition]
147 questions
29
votes
2 answers
LU Decomposition vs. Cholesky Decomposition
What is the difference between LU Decomposition and Cholesky Decomposition about using these methods to solving linear equation systems?
Could you explain the difference with a simple example?
Also could you explain the differences between these…
mertyildiran
- 393
- 1
- 4
- 8
20
votes
1 answer
LU decomposition steps
I've been looking at some LU Decomposition problems and I understand that making a matrix A reduced to the form A=LU , where L is a lower triangular matrix and U is a upper triangular matrix, however I am having trouble understanding the steps to…
Sujaan Kunalan
- 10,548
- 16
- 57
- 94
11
votes
5 answers
Is the $L$ in $LU$ factorization unique?
I was doing an $LU$ factorization problem
\begin{bmatrix}
2 & 3 & 2 \\
4 & 13 & 9 \\
-6 & 5 &4
\end{bmatrix}
and I was going to multiply the second row by .$5$ and subtract the result from row $1$, then do something similar to…
thecat
- 1,808
- 3
- 13
- 20
10
votes
1 answer
Decompose invertible matrix $A$ as $A = LPU$. (Artin, Chapter 2, Exercise M.11)
Decompose matrix $A$ as $A = LPU$, where $A \in Gl_n( \mathbb{R}^n)$, $L$ is lower triangular, $U$ is upper triangular with diagonal elements of $1$, and $P$ is a permutation matrix.
It is fairly easy to decompose any invertible such $A$ as $PA =…
gnometorule
- 4,560
- 26
- 43
9
votes
2 answers
Proof of uniqueness of LU factorization
The first question: what is the proof that LU factorization of matrix is unique? Or am I mistaken?
The second question is, how can theentries of L below the main diagonal be obtained from the matrix $A$ and $A_1$ that results from the row echelon…
Tashima Sasaki
- 91
- 1
- 1
- 2
9
votes
0 answers
Can I go from the LU factorization of a symmetric matrix to its Cholesky factorization, without starting over?
I mistakenly computed the LU factorization and then realized that the question is asking for a Cholesky factorization, i.e., finding a lower triangular matrix L such that the symmetric matrix A has factorization $LL^T$.
Can I modify this…
User001
- 1
- 8
- 44
- 120
8
votes
1 answer
Cholesky decomposition when deleting one row and one and column.
I've thought about this problem for days but could not find a good answer.
Given Cholesky decomposition of a symmetric positive semidefinite matrix $A = LL^T$. Now, suppose that we delete the $i$-th row and the $i$-th column of $A$ to obtain $A'$…
user97656
7
votes
1 answer
Is $A$ ill conditioned matrix?
Suppose we have a matrix $A$ with is its $LU$-decomposition such that $A=LU$ and suppose that $U$ is ill conditioned ($\left \| U \right \|\left \| U^{-1} \right \|$ is large) , does it mean that $A$ is ill conditioned ?
Pedro Alvarès
- 700
- 4
- 10
6
votes
1 answer
What is the computation time of LU-, Cholesky and QR-decomposition?
I found these information about computation-time of following decompositions:
Cholesky: (1/3)*n^3 + O(n^2) --> So computation-time is O(n^3)
LU: 2*(n^3/3) --> So computation-time is O(n^3) also (not sure)
QR: (2/3)*n^3 + n^2 + (1/3)*n- 2 --> So…
ZelelB
- 315
- 3
- 16
5
votes
1 answer
Solve many linear equations of similar structure
Given
G: real and symmetric square matrix
v: real column vector
I need to solve n linear systems of the form
\begin{align} A = \begin{pmatrix} G & v \\\ v^T & 0 \end{pmatrix}\end{align}
\begin{align} Ax = b\end{align}
Where
n is large
G: real…
Walden95
- 55
- 5
5
votes
3 answers
Why is $LU$ preferred over $A^{-1}$ to solve matrix equations?
I understand the whole $LU$-decomposition vs Gaussian elimination argument. The fact that you can isolate the computationally expensive elimination step and re-use the $L$ and $U$ matrices for $Ax=b$ style equations with different $b$:s makes sense…
Erik
- 173
- 3
5
votes
2 answers
Complexity/Operation count for the forward and backward substitution in the LU decomposition?
If I have a linear system of equations $Ax=b$ where $A \in \mathbb{R} ^{n\times n}, x \in \mathbb{R} ^{n}, b \in \mathbb{R} ^{n} $ this system can be solved for $x$ via an LU decomposition: $$A = LU$$ where $U \in \mathbb{R} ^{n\times n}$ is upper…
silver96
- 89
- 1
- 6
4
votes
1 answer
Is a symmetric matrix positive definite iff $D$ in its LDU decomposition is positive definite?
Given
$$A=LDU$$
where
$A$ is a real symmetric matrix
$L$ is a lower unitriangular matrix
$D$ is a diagonal matrix
$U$ is an upper unitriangular matrix
can we say that
$$A>0 \iff D>0$$
?
Edit:
My thinking is that $(LD^{1/2})(D^{1/2}U)$ is…
Museful
- 849
- 5
- 12
4
votes
2 answers
Condition number and $LU$ decomposition
Consider $A: n \times n$ non-singular and the factors $L$ and $U$ of $A$ obtained with partial pivoting strategy, such as: $PA = LU$.
Proof that $$\kappa_{\infty}(A) \geq \dfrac{||A||_{\infty}}{\min_{j}|u_{jj}|}.$$
The condition number…
Samuel Francisco
- 135
- 9
3
votes
1 answer
$PA = LU$ decomposition
Consider a matrix $A= \begin{pmatrix}
1 & 2 & 1\\
3 & 6 & 1\\
0 & 4 & 1
\end{pmatrix}$
I am applying the transformations on matrix $A$ to convert it to $U$ using the following matrices:
(The i,j in $E_{ij}$ denotes the element in matrix A…
Kakarot_7
- 151
- 7