MATH 417 Lecture 20

« previous | Thursday, April 3, 2014 | next »

Gaussian Elimination with Partial Pivoting

Step 0. System of equations Ax=b

$\left[{\begin{array}{ccc|c}0&2&2&2\\1&2&2&1\\1&1&2&3\end{array}}\right]$

Step 1. cell [1,1] is 0. That's unfortunate, so Switch rows 1 & 2

$\left[{\begin{array}{ccc|c}1&2&2&1\\0&2&2&2\\1&1&2&3\end{array}}\right]$

Step 2. subtract 1*(top row) from (bottom row)

$\left[{\begin{array}{ccc|c}1&2&2&1\\0&2&2&2\\0&-1&0&2\end{array}}\right]$

Step 3. multiply (second row) by 1/2

$\left[{\begin{array}{ccc|c}1&2&2&1\\0&1&1&1\\0&-1&0&2\end{array}}\right]$

Step 4. multiply (bottom row) by -1

$\left[{\begin{array}{ccc|c}1&2&2&1\\0&1&1&1\\0&1&0&-2\end{array}}\right]$

Step 5. subtract (second row) from (bottom row)

$\left[{\begin{array}{ccc|c}1&2&2&1\\0&1&1&1\\0&0&-1&-3\end{array}}\right]$

Step 5. multiply (bottom row) by -1

$\left[{\begin{array}{ccc|c}1&2&2&1\\0&1&1&1\\0&0&1&3\end{array}}\right]=U$

Step 7. Perform back substitution to get

${\begin{aligned}x_{3}&=3\\x_{2}&=-2\\x_{1}&=-1\end{aligned}}$

At each step, we left multiply by an elementary matrix. This elementary matrix is the identity matrix with the same operation performed on it:

$I={\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}\quad \longrightarrow \quad E_{1}={\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}}$
$I={\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}\quad \longrightarrow \quad E_{2}={\begin{bmatrix}1&0&0\\0&1&0\\-1&0&1\end{bmatrix}}$
$I={\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}\quad \longrightarrow \quad E_{3}={\begin{bmatrix}1&0&0\\0&{\frac {1}{2}}&0\\0&0&1\end{bmatrix}}$

and so on...

Observation: Each $E_{k}$ has two possibilities:

row permutations
lower triangular matrix

Note, if we perform row permutations $P_{1}\cdot P_{2}\dots P_{n}$ at the start, then we can proceed with Gaussian elimination without pivoting.

Let ${\tilde {A}}:=P_{n}\,\dots \,P_{2}\,P_{1}\,A$

Now since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_k \dots E_3 \, E_2 \, \tilde{A} = U} , we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = (E_k \, \dots \, E_3 \, E_2)^{-1} \, U} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (E_k \dots E_3 \, E_2)^{-1} = L = E_2^{-1} \, E_3^{-1} \, \dots \, E_k^{-1}}

What is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_i^{-1}} ?

row-scaling: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E = \begin{bmatrix}\lambda & 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \quad\longrightarrow\quad E^{-1} = \begin{bmatrix} \frac{1}{\lambda} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}
row-addition: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ \alpha & 0 & 1\end{bmatrix} \quad\longrightarrow\quad E^{-1} = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ -\alpha & 0 & 1 \end{bmatrix}}

To multiply these inverses, take superposition of matrices

combine nonzero entries not along diagonal
multiply corresponding entries on diagonals

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1\end{bmatrix} \cdot \begin{bmatrix}1 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & 0 & 1\end{bmatrix} = \begin{bmatrix}1 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ -1 & 0 & 1\end{bmatrix}}

Therefore, given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , if we can run gaussian elimination without pivoting, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = L \, U} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L = \begin{bmatrix}\ell_{11} & 0 \\ \ell_{ij} & l_{nn}\end{bmatrix}} ; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U = \begin{bmatrix}1 & u_{ij} \\ 0 & 1 \end{bmatrix}}

In practice, we can store Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} in the same matrix: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{bmatrix}\ell_{11} & u_{ij} \\ \ell_{ij} & \ell_{nn}\end{bmatrix}}

In contrast, we can do Gaussian elimination without pivoting (i.e. leave diagonal entries ≠ 1). In this case, our LU decomposition is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L = \begin{bmatrix}1 & 0 \\ \ell_{ij} & 1\end{bmatrix}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U = \begin{bmatrix}u_{11} & u_{ij} \\ 0 & u_{nn}\end{bmatrix}}

If we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = A^T} , can we get Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \tilde{L} = \tilde{L}^T} ? we should be able to (see later)

Diagonalization

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} L \, U &= \begin{bmatrix}1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ \ell_{31} & \ell_{32} & 1\end{bmatrix} * \begin{bmatrix}u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33}\end{bmatrix} \\ &= \begin{bmatrix}1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ \ell_{31} & \ell_{32} & 1\end{bmatrix} * \begin{bmatrix}u_{11} & 0 & 0 \\ 0 & u_{22} & 0 \\ 0 & 0 & u_{33}\end{bmatrix} * \begin{bmatrix}1 & \frac{u_{12}}{u_{11}} & \frac{u_{13}}{u_{11}} \\ 0 & 1 & \frac{u_{23}}{u_{22}} \\ 0 & 0 & 1\end{bmatrix} \\ &= L \, \Delta \, \tilde{U} \end{align}}

In this case, the diagonal entries of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta} are the eigenvalues of the matrix.

Theorem: If there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} eigenvalues, then there will be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} independent eigenvectors.

LDL Decomposition / Choleski Factorization

Above we saw a decomposition of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = L \, D \, L^T} . This is called LDL decomposition.

We can alternatively write this as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L \, \sqrt{D} \, \sqrt{D} \, L^T = (L \, \sqrt{D}) \, (L \, \sqrt{D})^T = \tilde{L} \, \tilde{L}^T}

So in the example above, we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell_{21} = \frac{u_{12}}{u_{11}}}

Special Matrices

Diagonally Dominant

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = (a_{ij})} , for every row, we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| a_{ii} \right| \ge \sum_{j \ne i} \left| a_{ij} \right| \ge 0}

"strictly" variant: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| a_{ii} \right| > \sum_{j \ne i} \left| a_{ij} \right| \ge 0}

We will consider only this "strict" case

Positive Definite

For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x} \ne \vec{0}} , we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x}^T \, A \, \vec{x} \ge 0}

also called non-negative definite

"strictly" variant: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x}^T \, A \, \vec{x} > 0}

We will consider only this "strict" case

Theorem

Theorem. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is strictly diagonally dominant or strictly positive definite, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is non-singular.

Proof. Assume to the contrary that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is singular. Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \, \vec{x} = \vec{0}} has a non-trivial solution (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x} \ne \vec{0}} )

Case 1: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is diagonally dominant. Take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x} = \begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix}} . Find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_j} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| x_j \right| = \max_{1 \le i \le n}{ \left| x_i \right| }}

Solve the system for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{jj} \, x_j = -\sum_{k=1; k \ne j}^n a_{jk} \, x_k} . Hence

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left| a_{jj} \right| \, \left| x_j \right| &= \left| \sum_{k \ne j} a_{jk} \, x_k \right| \le \sum_{k \ne j} \left| a_{jk} \right| \, \left| x_k \right| \\ \left| a_{jj} \right| \le \sum_{k \ne j} \left| a_{kj} \right| \, \left| \frac{x_k}{x_j} \right| \end{align}}

Observe that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| \frac{x_k}{x_j} \right| \le 1} , so

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| a_{jj} \right| \le \sum_{k \ne j} \left| a_{kj} \right| \, \left| \frac{x_k}{x_j} \right| \le \sum_{k \ne j} \left| a_{jk} \right| < a_{jj}}

→CONTRADICTION

Case 2: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is positive definite and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \, \vec{x} = \vec{0}} for some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x} \ne \vec{0}} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 < \vec{x}^T \, A \, \vec{x} = \vec{x}^T \, \vec{0} = 0}

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda_1} is an eigenvalue of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \, \vec{x_1} = \lambda_1 \, x_1} for some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x}_1 \, A \vec{x}_1 = \vec{x}_1^T \, \lambda_1 \, \vec{x}_1 = \lambda_1 \, \vec{x}_1^T \, \vec{x}_1 > 0}

Hence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda_1 > 0} .

...

quod erat demonstrandum

Going back to diagonal dominance. If we do Gaussian elimination, we are guaranteed that we will not need any pivoting