Skip to content

2.md

Latest commit

 

History

History
182 lines (133 loc) · 6.15 KB

2.md

File metadata and controls

182 lines (133 loc) · 6.15 KB

Task 2 Symmetric matrices, LDL decomposition

TOC

Explanation

Certainly! Let's break down these topics:

Symmetric Matrices

A symmetric matrix is a square matrix that is equal to its transpose. In other words, a matrix $A$ is symmetric if $A = A^T$, where $A^T$ denotes the transpose of $A$. This means that the element in the $i$-th row and $j$-th column is equal to the element in the $j$-th row and $i$-th column for all $i$ and $j$. Symmetric matrices arise naturally in a variety of applications, including physics (e.g., inertia tensors), computer graphics (e.g., covariance matrices), and optimization (e.g., quadratic forms).

Mathematically, for a symmetric matrix $A$, it holds that $a_{ij} = a_{ji}$ for all $i, j$.

LDL Decomposition

The LDL decomposition (also known as LDLT or LDL^T decomposition) is a factorization of a symmetric (or Hermitian, if complex) positive-definite matrix into the product of a lower triangular matrix $L$, a diagonal matrix $D$, and the transpose of the lower triangular matrix $L^T$. It is a variant of the Cholesky decomposition. The factorization can be written as:

$$ A = LDL^T $$

The LDL decomposition is useful because it can be computed more efficiently than the LU decomposition for symmetric matrices, and it can be used to solve linear systems, compute determinants, and perform other matrix operations more efficiently.

The decomposition proceeds as follows:

  1. The first step is to compute the first row (or column) of $L$ and the first diagonal element of $D$.
  2. The matrix $A$ is then updated by subtracting the outer product of the first column of $L$ with itself, scaled by the first element of $D$.
  3. The updated matrix, which is smaller by one row and one column, is then subjected to the same process, and the procedure is repeated until the entire matrix $A$ is decomposed.

The advantage of the LDL decomposition over the Cholesky decomposition is that it does not require the computation of square roots, which can be a source of numerical inaccuracy in some cases.

Example of LDL Decomposition

Let's say we have a symmetric matrix $A$ as follows:

$$ A = \begin{bmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{bmatrix} $$

The LDL decomposition of $A$ would result in matrices $L$, $D$, and $L^T$ such that $A = LDL^T$. Would you like to see a numerical example of how to compute the LDL decomposition for this matrix?

import numpy as np
import scipy.linalg as la

# Define the symmetric matrix A
A = np.array([
    [4, 12, -16],
    [12, 37, -43],
    [-16, -43, 98]
])

# Compute the LDL^T decomposition of the matrix A
L, D, perm = la.ldl(A)  # Note: Scipy's ldl returns also a permutation matrix due to pivoting
LDL_T = L @ D @ L.T

# Let's check our decomposition by comparing it to the original matrix A.
A_reconstructed = LDL_T

# Display the results
L, D, A_reconstructed, np.allclose(A, A_reconstructed)  # Check if the decomposition reconstructs A

The LDL decomposition of the symmetric matrix $A$ is given by the matrices $L$, $D$, and $L^T$, where $L$ is a lower triangular matrix with ones on the diagonal, $D$ is a diagonal matrix, and $L^T$ is the transpose of $L$. The computed matrices $L$ and $D$ for our matrix $A$ are:

$$ L = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 0.14705882 & 1 \\ -4 & 1 & 0 \end{bmatrix} $$

$$ D = \begin{bmatrix} 4 & 0 & 0 \\ 0 & 34 & 0 \\ 0 & 0 & 0.26470588 \end{bmatrix} $$

When we compute the product $LDL^T$, we get back our original matrix $A$:

$$ LDL^T = \begin{bmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{bmatrix} $$

The last check confirms that the decomposition is correct, as $LDL^T$ closely reconstructs the original matrix $A$.

Solution

  1. Consider matrix: $𝐴=\begin{bmatrix} 1 & 2 & 0 \ 2 & 6 & 4 \ 0 & 4 & 11 \end{bmatrix}$. Find the symmetric factorization $𝐴=LDL^T$, Find $𝐴^{-1}$ (10 pts.)

Let's perform the LDL decomposition of the given matrix $A$ step by step without direct library functions, and then use the decomposition to find the inverse of $A$.

For the matrix

$$ A = \begin{bmatrix} 1 & 2 & 0 \\ 2 & 6 & 4 \\ 0 & 4 & 11 \end{bmatrix}, $$

the LDL decomposition will proceed by finding $L$ and $D$ such that $A = LDL^T$.

Step 1: Decompose $A$ into $LDL^T$

  1. Since $A$ is symmetric, we start by setting $L_{11} = 1$ and $D_{11} = A_{11} = 1$.
  2. Then we calculate the first column of $L$ using $L_{21} = A_{21} / D_{11}$ and $L_{31} = A_{31} / D_{11}$.
  3. We proceed to update $A$ to create a new matrix $A^{(1)}$ by subtracting $L_{21}^2 \cdot D_{11}$ from $A_{22}$, and $L_{31}^2 \cdot D_{11}$ from $A_{33}$, and similarly for the off-diagonal terms.
  4. Now we consider the submatrix of $A^{(1)}$ excluding the first row and column, and repeat the process to find $L_{22}, L_{32}, D_{22}$, and so on.

Step 2: Calculate $A^{-1}$

Once we have $L$ and $D$, we can find $A^{-1}$ by using the fact that:

$$ A^{-1} = (LDL^T)^{-1} = (L^T)^{-1} D^{-1} L^{-1} $$

Let's begin by calculating the LDL decomposition.

The $L$ and $D$ matrices obtained through the manual LDL decomposition are:

$$ L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix}, $$

$$ D = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}. $$

Now, we will calculate $A^{-1}$ using these $L$ and $D$ matrices. To find $A^{-1}$, we need to compute $(L^T)^{-1}$, $D^{-1}$, and $L^{-1}$, and then multiply them together in the correct order:

$$ A^{-1} = (L^T)^{-1} D^{-1} L^{-1}. $$

Let's proceed with this calculation.

The inverse of the matrix $A$, expressed in fraction form, is:

$$ A^{-1} = \begin{bmatrix} \frac{25}{3} & -\frac{11}{3} & \frac{4}{3} \\ -\frac{11}{3} & \frac{11}{6} & -\frac{2}{3} \\ \frac{4}{3} & -\frac{2}{3} & \frac{1}{3} \end{bmatrix} $$