15.2 Review of Nonsingular Gravity Model

Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: 15.1 LU Factorization without Pivoting

Properties: N/A
Sufficiencies: N/A
Questions: N/A

Review of Nonsingular Gravity Model

Let's look back at our 12.2.1 Nonsingular Matrix to Model Gravity.

[\begin{matrix} 1 & 3.0 & 9.00 \\ 1 & 3.3 & 10.89 \\ 1 & 3.6 & 12.96 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}] = [\begin{matrix} 3.000 \\ 2.559 \\ 1.236 \end{matrix}]

Recall that the first thing we did was annihilate our first column step-by step.

\underset{S_{21} (- 1)}{\underset{⏟}{[\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]}} [\begin{matrix} 1 & 3.0 & 9.00 \\ 1 & 3.3 & 10.89 \\ 1 & 3.6 & 12.96 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}]

After annihilating that value, we moved down and annihilated the value under.

\underset{S_{31} (- 1)}{\underset{⏟}{[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 1 & 0 & 1 \end{matrix}]}} \underset{S_{21} (- 1)}{\underset{⏟}{[\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]}} [\begin{matrix} 1 & 3.0 & 9.00 \\ 1 & 3.3 & 10.89 \\ 1 & 3.6 & 12.96 \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}]

After that, we moved to pivot 2.

\underset{S_{32} (- 2)}{\underset{⏟}{[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & - 2 & 1 \end{matrix}]}} \underset{S_{31} (- 1) \cdot S_{21} (- 1) \cdot A}{\underset{⏟}{[\begin{matrix} 1 & 3.0 & 9.00 \\ 0 & 0.3 & 1.89 \\ 0 & 0.6 & 3.96 \end{matrix}]}}

Notice that

\begin{aligned} S_{31} (- 1) \cdot S_{21} (- 1) & = [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 1 & 0 & 1 \end{array}] [\begin{array}{c} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}] \\ = (I_{3} + - 1 \cdot {\vec{e}}_{3} {\vec{e}}_{1}^{T}) \cdot (I_{3} + - 1 {\vec{e}}_{2} \cdot {\vec{e}}_{1}^{T}) \\ = I_{3} + - 1 \cdot {\vec{e}}_{3} \cdot {\vec{e}}_{1}^{T} + (I_{3} + - 1 {\vec{e}}_{3} {\vec{e}}_{1}^{T}) \cdot - 1 \cdot {\vec{e}}_{2} {\vec{e}}_{1}^{T} \\ = I_{3} + - 1 {\vec{e}}_{3} {\vec{e}}_{1}^{T} + - 1 {\vec{e}}_{2} {\vec{e}}_{1}^{T} + - 1 {\vec{e}}_{3} {\vec{e}}_{1}^{T} \cdot - 1 \cdot {\vec{e}}_{2} \cdot {\vec{e}}_{1}^{T} \\ = I_{3} + - 1 \cdot {\vec{e}}_{3} \cdot {\vec{e}}_{1}^{T} + - 1 \cdot {\vec{e}}_{2} \cdot {\vec{e}}_{1}^{T} + 1 {\vec{e}}_{3} ({\vec{e}}_{1}^{T} \cdot {\vec{e}}_{2}) {\vec{e}}_{1}^{T} \\ ⟹ S_{31} (- 1) \cdot S_{21} (- 1) & = I_{3} + - 1 \cdot {\vec{e}}_{2} \cdot {\vec{e}}_{1}^{T} + - 1 \cdot {\vec{e}}_{2} \cdot {\vec{e}}_{1}^{T} \\ = [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] + [\begin{array}{c} 0 & 0 & 0 \\ 0 & 0 & 0 \\ - 1 & 0 & 0 \end{array}] + [\begin{array}{c} 0 & 0 & 0 \\ - 1 & 0 & 0 \\ 0 & 0 & 0 \end{array}] \\ ⟹ [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ - 1 & 0 & 1 \end{array}] \cdot [\begin{array}{c} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}] & = [\begin{array}{c} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & 0 & 1 \end{array}] \end{aligned}

For such a complex calculation that matrix multiplication is, we seem to get an elegant answer. It looks like the two shear matrices just overlapped on top of each other. Unfortunately, this doesn't always work.

S_{32} (- 2) \cdot S_{31} (- 1) \cdot S_{21} (- 1) \neq [\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & - 2 & 1 \end{matrix}]

Let's do the calculation to see why.

\begin{aligned} [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & - 2 & 1 \end{array}] [\begin{array}{c} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & 0 & 1 \end{array}] & = [\begin{array}{c} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ 1 & - 2 & 1 \end{array}] \end{aligned}

The stuff that happens in pivot 2 stays separate from the stuff that happens in pivot 2.

\begin{aligned} \underset{L_{2}}{\underset{⏟}{[\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & - 2 & 1 \end{array}]}} \underset{L_{1}}{\underset{⏟}{[\begin{array}{c} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & 0 & 1 \end{array}]}} \underset{A}{\underset{⏟}{[\begin{array}{c} 1 & 3.0 & 9.00 \\ 1 & 3.3 & 10.89 \\ 1 & 3.6 & 12.96 \end{array}]}} & = \underset{U}{\underset{⏟}{[\begin{array}{c} 1 & 3.0 & 9.00 \\ 0 & 0.3 & 1.89 \\ 0 & 0 & 0.18 \end{array}]}} \end{aligned}

Recall the definition

Gauss Transform

Let natural numbers $n, k \in N$ with $k < n$ . Let 3.1 Column Vector $\underset{tau}{\vec{τ}} \in R^{n}$ whose first $k$ components are zero. Suppose $\vec{τ}$ is in the form
${\vec{τ}}^{T} = [\begin{matrix} \underset{k}{\underset{⏟}{0 \dots 0}} & τ_{k + 1} & \dots & τ_{n} \end{matrix}]$
Then, a Gauss transformation is a matrix
$L_{k} = I_{n} - \vec{τ} \cdot {\vec{e}}_{k}^{T}$
We call the vector $\vec{τ}$ a Gauss vector.

Let's apply this definition to our example.

\begin{aligned} L_{1} = [\begin{array}{c} 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & 0 & 1 \end{array}] & = [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] + [\begin{array}{c} 0 & 0 & 0 \\ - 1 & 0 & 0 \\ - 1 & 0 & 0 \end{array}] \\ = [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] - [\begin{array}{c} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array}] \\ = [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}] - [\begin{array}{c} 0 \\ 1 \\ 1 \end{array}] [\begin{array}{c} 1 & 0 & 0 \end{array}] \\ ⟹ L_{1} & = I_{3} - {\vec{τ}}_{1} {\vec{e}}_{1}^{T} with {\vec{τ}}_{1} = [\begin{array}{c} 0 \\ 1 \\ 1 \end{array}] = [\begin{array}{c} 0 \\ \frac{a_{21}}{a_{11}} \\ \frac{a_{31}}{a_{11}} \end{array}] \end{aligned}

Why are we even using a Gauss Transform?

The whole idea is we're trying to solve a nonsingular linear systems problem by turning our modeling matrix into 8.9 Upper-Triangular Matrix. The whole process of turning our matrix into upper-triangular is multiplying $A$ on the left by a sequence of elementary matrices. In this case, our matrix is a 12.3 Regular Matrix. The trend that we notice is that the shear matrices for each pivot is "married" into one. This matrix is known as the 9.12 Gauss Transform. Instead of using a bunch of 9.8 Shear Matrix, we can put the $c$ values into the same column.

We solve our NLSP from left to right.

L_{2} \cdot L_{1} \cdot A = U

To get rid of $L_{2}$ first, we can multiply it by its 13.1 Inverse of a Square Matrix.

L_{2}^{- 1} \cdot L_{2} \cdot L_{1} \cdot A = L_{2}^{- 1} \cdot U

! Remember if we multiply on the left by inverse, we need to do the same on the other side!

Once we've gotten rid of $L_{2}$ , we want to get rid of $L_{1}$ .

\begin{aligned} L_{1}^{- 1} \cdot L_{2}^{- 1} \cdot L_{2} \cdot L_{1} \cdot A & = L_{1}^{- 1} \cdot L_{2}^{- 1} \cdot U \\ ⟹ L_{1}^{- 1} \cdot I_{3} \cdot L_{1} \cdot A & = L_{1}^{- 1} \cdot L_{2}^{- 1} \cdot U \\ ⟹ L_{1}^{- 1} \cdot L_{1} \cdot A & = L_{1}^{- 1} \cdot L_{2}^{- 1} \cdot U \\ ⟹ I_{3} \cdot A & = L_{1}^{- 1} \cdot L_{2}^{- 1} \cdot U \\ ⟹ A & = L_{1}^{- 1} \cdot L_{2}^{- 1} \cdot U \end{aligned}

Note the inverse of our first Gauss transform:

\begin{aligned} L_{1}^{- 1} & = (I_{3} - {\vec{τ}}_{1} {\vec{e}}_{1}^{T})^{- 1} \\ = (I_{3} + {\vec{τ}}_{1} {\vec{e}}_{1}^{T}) \end{aligned}

We can write a more general case as:

L_{k}^{- 1} = (I_{n} - {\vec{τ}}_{k} {\vec{e}}_{k}^{T})^{- 1} = (I_{n} + {\vec{τ}}_{k} {\vec{e}}_{k}^{T})

The first Gauss transform zeroes out the entries underneath the first pivot. The second Gauss transform zeroes out the entries underneath the second pivot. We can generalize, saying a Gauss transform zeroes out the entries underneath the $k$ th pivot.

\begin{aligned} ⟹ L_{1}^{- 1} \cdot L_{2}^{- 1} & = [\begin{array}{c} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{array}] [\begin{array}{c} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 2 & 1 \end{array}] \\ = [\begin{array}{c} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 2 & 1 \end{array}] = L \end{aligned}

& Because the matrices are in this order, we can simply "marry" the two matrices!

We now have our $L$ matrix for $L U$ factorization.

\begin{aligned} \underset{L}{\underset{⏟}{[\begin{array}{c} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 2 & 1 \end{array}]}} \underset{U}{\underset{⏟}{[\begin{array}{c} 1 & 3.0 & 9.00 \\ 0 & 0.3 & 1.89 \\ 0 & 0 & 0.18 \end{array}]}} & = \underset{A}{\underset{⏟}{[\begin{array}{c} 1 & 3.0 & 9.00 \\ 1 & 3.3 & 10.89 \\ 1 & 3.6 & 12.96 \end{array}]}} \\ ⟹ A \vec{x} = \vec{b} & ⟺ (L \cdot U) \vec{x} = \vec{b} \\ ⟺ L \cdot (U \cdot \vec{x}) = \vec{b} \\ ⟺ \underset{forward substitution}{L \vec{y} = \vec{b}}, \underset{backwards substitution}{U \vec{x} = \vec{y} B} \end{aligned}

Let's see $L U$ factorization in action by starting with 12.5 Forward Substitution.

\begin{aligned} [\begin{array}{c} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 2 & 1 \end{array}] [\begin{array}{c} y_{1} \\ y_{2} \\ y_{3} \end{array}] & = [\begin{array}{c} 3.000 \\ 2.559 \\ 1.236 \end{array}] \\ ⟹ y_{1} & = 3 \\ ⟹ 1 \cdot y_{1} + 1 \cdot y_{2} & = 2.559 \\ ⟹ y_{2} = \frac{1}{1} (2.559 - 1 (3)) & = - 0.441 \\ ⟹ 1 \cdot y_{1} + 2 \cdot y_{2} + 1 \cdot y_{3} & = 1.236 \\ ⟹ y_{3} = \frac{1}{1} (1.236 - 2 (- 0.441) - 3) & = - 0.882 \end{aligned}

Therefore,

\begin{aligned} ⟹ L \vec{y} = \vec{b} ⟹ \vec{y} = [\begin{array}{c} 3.000 \\ - 0.441 \\ - 0.882 \end{array}] \\ ⟹ U \vec{x} = \vec{y} ⟺ [\begin{array}{c} 1 & 3.0 & 9.00 \\ 0 & 0.3 & 1.89 \\ 0 & 0 & 0.18 \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \end{array}] = [\begin{array}{c} 3.000 \\ - 0.441 \\ - 0.882 \end{array}] \end{aligned}

We can solve this using 12.2 Backwards Substitution.

\begin{aligned} ⟹ x_{3} \cdot 0.18 & = - 0.882 \\ x_{3} & = - 4.9 \\ ⟹ x_{2} \cdot 0.3 + x_{3} \cdot 1.89 & = - 0.441 \\ x_{2} & = 29.4 \\ ⟹ 1 \cdot x_{1} + 3 \cdot x_{2} + 9 \cdot x_{3} & = 3 \\ x_{1} & = - 41.1 \\ ⟹ [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \end{array}] & = [\begin{array}{c} - 41.1 \\ 29.4 \\ - 4.9 \end{array}] \end{aligned}

This is the same solution we found in 12.2.1 Nonsingular Matrix to Model Gravity.