Matrix decomposition solutions#
Solutions to the exercises on matrix decomposition.
Solution to Exercise 6.1
(a) Calculate LU decomposition of the coefficient matrix \(A = \left(\begin{matrix}2 & 3 & -1\\4 & 9 & -1\\0 & 3 & 2\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 2 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{2} \left( 4 \right) = 2, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{2} \left( 0 \right) = 0, \\
j &= 2: & u_{12} &= a_{12} = 3 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = 9 - 2 \left( 3 \right) = 3, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{3} \left( 3 - 0 \left( 3 \right) \right) = 1, \\
j &= 3: & u_{13} &= a_{13} = -1 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = -1 - 2 \left( -1 \right) = 1, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = 2 - 0 \left( -1 \right) - 1 \left( 1 \right) = 1, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0\\2 & 1 & 0\\0 & 1 & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}2 & 3 & -1\\0 & 3 & 1\\0 & 0 & 1\end{matrix}\right)\).
Solving \(L \vec{y} = \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0\\2 & 1 & 0\\0 & 1 & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \end{pmatrix} &=\left(\begin{matrix}4\\18\\11\end{matrix}\right) \\
y_{1} &= 4 \\
y_{2} &= 18 - 2 \left( 4 \right) = 10 , \\
y_{3} &= 11 - 0 \left( 4 \right) - 1 \left( 10 \right) = 1 .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}2 & 3 & -1\\0 & 3 & 1\\0 & 0 & 1\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix} &=\left(\begin{matrix}4\\10\\1\end{matrix}\right) \\
x_{3} &= \frac{1}{1} \left( 1 \right) = 1 , \\
x_{2} &= \frac{1}{3} \left( 10 - 1 \left( 1 \right) \right) = 3 , \\
x_{1} &= \frac{1}{2} \left( 4 - 3 \left( 3 \right) + 1 \left( 1 \right) \right) = -2 .
\end{align*} \end{split}\]
(b) Calculate LU decomposition of the coefficient matrix \(A = \left(\begin{matrix}3 & 9 & 5\\1 & 2 & 2\\2 & 4 & 5\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 3 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{3} \left( 1 \right) = \frac{1}{3}, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{3} \left( 2 \right) = \frac{2}{3}, \\
j &= 2: & u_{12} &= a_{12} = 9 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = 2 - \frac{1}{3} \left( 9 \right) = -1, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{-1} \left( 4 - \frac{2}{3} \left( 9 \right) \right) = 2, \\
j &= 3: & u_{13} &= a_{13} = 5 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = 2 - \frac{1}{3} \left( 5 \right) = 0, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = 5 - \frac{2}{3} \left( 5 \right) - 2 \left( \frac{1}{3} \right) = 1, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0\\\frac{1}{3} & 1 & 0\\\frac{2}{3} & 2 & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}3 & 9 & 5\\0 & -1 & \frac{1}{3}\\0 & 0 & 1\end{matrix}\right)\).
Solving \(L \vec{y} = \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0\\\frac{1}{3} & 1 & 0\\\frac{2}{3} & 2 & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \end{pmatrix} &=\left(\begin{matrix}20\\3\\4\end{matrix}\right) \\
y_{1} &= 20 \\
y_{2} &= 3 - \frac{1}{3} \left( 20 \right) = - \frac{11}{3} , \\
y_{3} &= 4 - \frac{2}{3} \left( 20 \right) - 2 \left( - \frac{11}{3} \right) = -2 .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}3 & 9 & 5\\0 & -1 & \frac{1}{3}\\0 & 0 & 1\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix} &=\left(\begin{matrix}20\\- \frac{11}{3}\\-2\end{matrix}\right) \\
x_{3} &= \frac{1}{1} \left( -2 \right) = -2 , \\
x_{2} &= \frac{1}{-1} \left( - \frac{11}{3} - \frac{1}{3} \left( -2 \right) \right) = 3 , \\
x_{1} &= \frac{1}{3} \left( 20 - 9 \left( 3 \right) - 5 \left( -2 \right) \right) = 1 .
\end{align*} \end{split}\]
(c) Calculate LU decomposition of the coefficient matrix \(A = \left(\begin{matrix}1 & 0 & 3 & 2\\3 & -2 & 5 & 1\\4 & -1 & -2 & -3\\0 & 2 & 0 & 3\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 1 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{1} \left( 3 \right) = 3, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{1} \left( 4 \right) = 4, \\
&& \ell_{41} &= \frac{1}{u_{11}} \left( a_{41} \right) = \frac{1}{1} \left( 0 \right) = 0, \\
j &= 2: & u_{12} &= a_{12} = 0 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = -2 - 3 \left( 0 \right) = -2, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{-2} \left( -1 - 4 \left( 0 \right) \right) = \frac{1}{2}, \\
&& \ell_{42} &= \frac{1}{u_{22}} \left( a_{42} - \ell_{41} u_{12} \right) = \frac{1}{-2} \left( 2 - 0 \left( 0 \right) \right) = -1, \\
j &= 3: & u_{13} &= a_{13} = 3 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = 5 - 3 \left( 3 \right) = 0, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = -2 - 4 \left( 3 \right) - \frac{1}{2} \left( -4 \right) = -12, \\
&& \ell_{43} &= \frac{1}{u_{33}} \left( a_{43} - \ell_{41} u_{13} - \ell_{42} u_{23} \right) = \frac{1}{-12} \left( 0 - 0 \left( 3 \right) - \left( -1 \right) \left( -4 \right) \right) = \frac{1}{3}, \\
j &= 4: & u_{14} &= a_{14} = 2 , \\
&& u_{24} &= a_{24} - \ell_{21} u_{14} = 1 - 3 \left( 2 \right) = 0, \\
&& u_{34} &= a_{34} - \ell_{31} u_{14} - \ell_{32} u_{24} = -3 - 4 \left( 2 \right) - \frac{1}{2} \left( -5 \right) = 0, \\
&& u_{44} &= a_{44} - \ell_{41} u_{14} - \ell_{42} u_{24} - \ell_{43} u_{34} = 3 - 0 \left( 2 \right) - \left(-1 \right) \left( -5 \right) - \frac{1}{3} \left( - \frac{17}{2} \right) = \frac{5}{6}, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0 & 0\\3 & 1 & 0 & 0\\4 & \frac{1}{2} & 1 & 0\\0 & -1 & \frac{1}{3} & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}1 & 0 & 3 & 2\\0 & -2 & -4 & -5\\0 & 0 & -12 & - \frac{17}{2}\\0 & 0 & 0 & \frac{5}{6}\end{matrix}\right)\).
Solving \(L \vec{y} = \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0 & 0\\3 & 1 & 0 & 0\\4 & \frac{1}{2} & 1 & 0\\0 & -1 & \frac{1}{3} & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{pmatrix} &=\left(\begin{matrix}21\\28\\-12\\13\end{matrix}\right) \\
y_{1} &= 21 \\
y_{2} &= 28 - 3 \left( 21 \right) = -35 , \\
y_{3} &= -12 - 4 \left( 21 \right) - \frac{1}{2} \left( -35 \right) = - \frac{157}{2} , \\
y_{4} &= 13 - 0 \left( 21 \right) + 1 \left( -35 \right) - \frac{1}{3} \left( - \frac{157}{2} \right) = \frac{25}{6} .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 3 & 2\\0 & -2 & -4 & -5\\0 & 0 & -12 & - \frac{17}{2}\\0 & 0 & 0 & \frac{5}{6}\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix} &=\left(\begin{matrix}21\\-35\\- \frac{157}{2}\\\frac{25}{6}\end{matrix}\right) \\
x_{4} &= \frac{1}{\frac{5}{6}} \left( \frac{25}{6} \right) = 5 , \\
x_{3} &= \frac{1}{-12} \left( - \frac{157}{2} + \frac{17}{2} \left( 5 \right) \right) = 3 , \\
x_{2} &= \frac{1}{-2} \left( -35 + 4 \left( 3 \right) + 5 \left( 5 \right) \right) = -1 , \\
x_{1} &= \frac{1}{1} \left( 21 - 0 \left( -1 \right) - 3 \left( 3 \right) - 2 \left( 5 \right) \right) = 2 .
\end{align*} \end{split}\]
(d) Calculate LU decomposition of the coefficient matrix \(A = \left(\begin{matrix}1 & 5 & 2 & 2\\-2 & -4 & 2 & 0\\3 & 1 & -2 & -1\\-3 & -3 & 4 & -1\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 1 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{1} \left( -2 \right) = -2, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{1} \left( 3 \right) = 3, \\
&& \ell_{41} &= \frac{1}{u_{11}} \left( a_{41} \right) = \frac{1}{1} \left( -3 \right) = -3, \\
j &= 2: & u_{12} &= a_{12} = 5 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = -4 - \left(-2 \right) \left( 5 \right) = 6, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{6} \left( 1 - 3 \left( 5 \right) \right) = - \frac{7}{3}, \\
&& \ell_{42} &= \frac{1}{u_{22}} \left( a_{42} - \ell_{41} u_{12} \right) = \frac{1}{6} \left( -3 - \left( -3 \right) \left( 5 \right) \right) = 2, \\
j &= 3: & u_{13} &= a_{13} = 2 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = 2 - \left(-2 \right) \left( 2 \right) = 0, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = -2 - 3 \left( 2 \right) - \left(- \frac{7}{3} \right) \left( 6 \right) = 6, \\
&& \ell_{43} &= \frac{1}{u_{33}} \left( a_{43} - \ell_{41} u_{13} - \ell_{42} u_{23} \right) = \frac{1}{6} \left( 4 - \left( -3 \right) \left( 2 \right) - 2 \left( 6 \right) \right) = - \frac{1}{3}, \\
j &= 4: & u_{14} &= a_{14} = 2 , \\
&& u_{24} &= a_{24} - \ell_{21} u_{14} = 0 - \left(-2 \right) \left( 2 \right) = 0, \\
&& u_{34} &= a_{34} - \ell_{31} u_{14} - \ell_{32} u_{24} = -1 - 3 \left( 2 \right) - \left(- \frac{7}{3} \right) \left( 4 \right) = 0, \\
&& u_{44} &= a_{44} - \ell_{41} u_{14} - \ell_{42} u_{24} - \ell_{43} u_{34} = -1 - \left(-3 \right) \left( 2 \right) - 2 \left( 4 \right) - \left(- \frac{1}{3} \right) \left( \frac{7}{3} \right) = - \frac{20}{9}, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0 & 0\\-2 & 1 & 0 & 0\\3 & - \frac{7}{3} & 1 & 0\\-3 & 2 & - \frac{1}{3} & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}1 & 5 & 2 & 2\\0 & 6 & 6 & 4\\0 & 0 & 6 & \frac{7}{3}\\0 & 0 & 0 & - \frac{20}{9}\end{matrix}\right)\).
Solving \(L \vec{y} = \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0 & 0\\-2 & 1 & 0 & 0\\3 & - \frac{7}{3} & 1 & 0\\-3 & 2 & - \frac{1}{3} & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{pmatrix} &=\left(\begin{matrix}-10\\10\\-2\\4\end{matrix}\right) \\
y_{1} &= -10 \\
y_{2} &= 10 + 2 \left( -10 \right) = -10 , \\
y_{3} &= -2 - 3 \left( -10 \right) + \frac{7}{3} \left( -10 \right) = \frac{14}{3} , \\
y_{4} &= 4 + 3 \left( -10 \right) - 2 \left( -10 \right) + \frac{1}{3} \left( \frac{14}{3} \right) = - \frac{40}{9} .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 5 & 2 & 2\\0 & 6 & 6 & 4\\0 & 0 & 6 & \frac{7}{3}\\0 & 0 & 0 & - \frac{20}{9}\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix} &=\left(\begin{matrix}-10\\-10\\\frac{14}{3}\\- \frac{40}{9}\end{matrix}\right) \\
x_{4} &= \frac{1}{- \frac{20}{9}} \left( - \frac{40}{9} \right) = 2 , \\
x_{3} &= \frac{1}{6} \left( \frac{14}{3} - \frac{7}{3} \left( 2 \right) \right) = 0 , \\
x_{2} &= \frac{1}{6} \left( -10 - 6 \left( 0 \right) - 4 \left( 2 \right) \right) = -3 , \\
x_{1} &= \frac{1}{1} \left( -10 - 5 \left( -3 \right) - 2 \left( 0 \right) - 2 \left( 2 \right) \right) = 1 .
\end{align*} \end{split}\]
Solution to Exercise 6.2
(a) Perform partial pivoting on the coefficient matrix
\[\begin{split} \begin{align*}
& \left(\begin{matrix}2 & 3 & -1\\4 & 9 & -1\\0 & 3 & 2\end{matrix}\right)
\begin{matrix} R_{1} \leftrightarrow R_{2}\\ \phantom{x} \\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}4 & 9 & -1\\2 & 3 & -1\\0 & 3 & 2\end{matrix}\right)
= PA.
\end{align*} \end{split}\]
Applying the same row operations to the identity matrix:
\[\begin{split} \begin{align*}
& \left(\begin{matrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{matrix}\right)
\begin{matrix} R_{1} \leftrightarrow R_{2}\\ \phantom{x} \\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}0 & 1 & 0\\1 & 0 & 0\\0 & 0 & 1\end{matrix}\right)
= P.
\end{align*} \end{split}\]
Calculate the LU decomposition of \(PA = \left(\begin{matrix}4 & 9 & -1\\2 & 3 & -1\\0 & 3 & 2\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 4 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{4} \left( 2 \right) = \frac{1}{2}, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{4} \left( 0 \right) = 0, \\
j &= 2: & u_{12} &= a_{12} = 9 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = 3 - \frac{1}{2} \left( 9 \right) = - \frac{3}{2}, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{-3/2} \left( 3 - 0 \left( 9 \right) \right) = -2, \\
j &= 3: & u_{13} &= a_{13} = -1 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = -1 - \frac{1}{2} \left( -1 \right) = 0, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = 2 - 0 \left( -1 \right) - \left(-2 \right) \left( - \frac{1}{2} \right) = 1, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0\\\frac{1}{2} & 1 & 0\\0 & -2 & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}4 & 9 & -1\\0 & - \frac{3}{2} & - \frac{1}{2}\\0 & 0 & 1\end{matrix}\right)\).
Solving \(L \vec{y} = P \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0\\\frac{1}{2} & 1 & 0\\0 & -2 & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \end{pmatrix} &=\left(\begin{matrix}18\\4\\11\end{matrix}\right) \\
y_{1} &= 18 \\
y_{2} &= 4 - \frac{1}{2} \left( 18 \right) = -5 , \\
y_{3} &= 11 - 0 \left( 18 \right) + 2 \left( -5 \right) = 1 .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}4 & 9 & -1\\0 & - \frac{3}{2} & - \frac{1}{2}\\0 & 0 & 1\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix} &=\left(\begin{matrix}18\\-5\\1\end{matrix}\right) \\
x_{3} &= \frac{1}{1} \left( 1 \right) = 1 , \\
x_{2} &= \frac{1}{- \frac{3}{2}} \left( -5 + \frac{1}{2} \left( 1 \right) \right) = 3 , \\
x_{1} &= \frac{1}{4} \left( 18 - 9 \left( 3 \right) + 1 \left( 1 \right) \right) = -2 .
\end{align*} \end{split}\]
(b) Perform partial pivoting on the coefficient matrix
\[\begin{split} \begin{align*}
& \left(\begin{matrix}3 & 9 & 5\\1 & 2 & 2\\2 & 4 & 5\end{matrix}\right)
\begin{matrix} \phantom{x} \\ R_{2} \leftrightarrow R_{3}\\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}3 & 9 & 5\\2 & 4 & 5\\1 & 2 & 2\end{matrix}\right)
= PA.
\end{align*} \end{split}\]
Applying the same row operations to the identity matrix:
\[\begin{split} \begin{align*}
& \left(\begin{matrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{matrix}\right)
\begin{matrix} \phantom{x} \\ R_{2} \leftrightarrow R_{3}\\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\end{matrix}\right)
= P.
\end{align*} \end{split}\]
Calculate the LU decomposition of \(PA = \left(\begin{matrix}3 & 9 & 5\\2 & 4 & 5\\1 & 2 & 2\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 3 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{3} \left( 2 \right) = \frac{2}{3}, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{3} \left( 1 \right) = \frac{1}{3}, \\
j &= 2: & u_{12} &= a_{12} = 9 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = 4 - \frac{2}{3} \left( 9 \right) = -2, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{-2} \left( 2 - \frac{1}{3} \left( 9 \right) \right) = \frac{1}{2}, \\
j &= 3: & u_{13} &= a_{13} = 5 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = 5 - \frac{2}{3} \left( 5 \right) = 0, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = 2 - \frac{1}{3} \left( 5 \right) - \frac{1}{2} \left( \frac{5}{3} \right) = - \frac{1}{2}, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0\\\frac{2}{3} & 1 & 0\\\frac{1}{3} & \frac{1}{2} & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}3 & 9 & 5\\0 & -2 & \frac{5}{3}\\0 & 0 & - \frac{1}{2}\end{matrix}\right)\).
Solving \(L \vec{y} = P \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0\\\frac{2}{3} & 1 & 0\\\frac{1}{3} & \frac{1}{2} & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \end{pmatrix} &=\left(\begin{matrix}20\\4\\3\end{matrix}\right) \\
y_{1} &= 20 \\
y_{2} &= 4 - \frac{2}{3} \left( 20 \right) = - \frac{28}{3} , \\
y_{3} &= 3 - \frac{1}{3} \left( 20 \right) - \frac{1}{2} \left( - \frac{28}{3} \right) = 1 .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}3 & 9 & 5\\0 & -2 & \frac{5}{3}\\0 & 0 & - \frac{1}{2}\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix} &=\left(\begin{matrix}20\\- \frac{28}{3}\\1\end{matrix}\right) \\
x_{3} &= \frac{1}{- \frac{1}{2}} \left( 1 \right) = -2 , \\
x_{2} &= \frac{1}{-2} \left( - \frac{28}{3} - \frac{5}{3} \left( -2 \right) \right) = 3 , \\
x_{1} &= \frac{1}{3} \left( 20 - 9 \left( 3 \right) - 5 \left( -2 \right) \right) = 1 .
\end{align*} \end{split}\]
(c) Perform partial pivoting on the coefficient matrix
\[\begin{split} \begin{align*}
& \left(\begin{matrix}1 & 0 & 3 & 2\\3 & -2 & 5 & 1\\4 & -1 & -2 & -3\\0 & 2 & 0 & 3\end{matrix}\right)
\begin{matrix} R_{1} \leftrightarrow R_{3}\\ \phantom{x} \\ \phantom{x} \\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}4 & -1 & -2 & -3\\3 & -2 & 5 & 1\\1 & 0 & 3 & 2\\0 & 2 & 0 & 3\end{matrix}\right)
\begin{matrix} \phantom{x} \\ R_{2} \leftrightarrow R_{4}\\ \phantom{x} \\ \phantom{x} \end{matrix}
\\ \longrightarrow
& \left(\begin{matrix}4 & -1 & -2 & -3\\0 & 2 & 0 & 3\\1 & 0 & 3 & 2\\3 & -2 & 5 & 1\end{matrix}\right)
\begin{matrix} \phantom{x} \\ \phantom{x} \\ R_{3} \leftrightarrow R_{4}\\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}4 & -1 & -2 & -3\\0 & 2 & 0 & 3\\3 & -2 & 5 & 1\\1 & 0 & 3 & 2\end{matrix}\right)
= PA.
\end{align*} \end{split}\]
Applying the same row operations to the identity matrix:
\[\begin{split} \begin{align*}
& \left(\begin{matrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{matrix}\right)
\begin{matrix} R_{1} \leftrightarrow R_{3}\\ \phantom{x} \\ \phantom{x} \\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}0 & 0 & 1 & 0\\0 & 1 & 0 & 0\\1 & 0 & 0 & 0\\0 & 0 & 0 & 1\end{matrix}\right)
\begin{matrix} \phantom{x} \\ R_{2} \leftrightarrow R_{4}\\ \phantom{x} \\ \phantom{x} \end{matrix}
\\ \longrightarrow
& \left(\begin{matrix}0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\1 & 0 & 0 & 0\\0 & 1 & 0 & 0\end{matrix}\right)
\begin{matrix} \phantom{x} \\ \phantom{x} \\ R_{3} \leftrightarrow R_{4}\\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\0 & 1 & 0 & 0\\1 & 0 & 0 & 0\end{matrix}\right)
= P.
\end{align*} \end{split}\]
Calculate the LU decomposition of \(PA = \left(\begin{matrix}4 & -1 & -2 & -3\\0 & 2 & 0 & 3\\3 & -2 & 5 & 1\\1 & 0 & 3 & 2\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 4 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{4} \left( 0 \right) = 0, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{4} \left( 3 \right) = \frac{3}{4}, \\
&& \ell_{41} &= \frac{1}{u_{11}} \left( a_{41} \right) = \frac{1}{4} \left( 1 \right) = \frac{1}{4}, \\
j &= 2: & u_{12} &= a_{12} = -1 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = 2 - 0 \left( -1 \right) = 2, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{2} \left( -2 - \frac{3}{4} \left( -1 \right) \right) = - \frac{5}{8}, \\
&& \ell_{42} &= \frac{1}{u_{22}} \left( a_{42} - \ell_{41} u_{12} \right) = \frac{1}{2} \left( 0 - \frac{1}{4} \left( -1 \right) \right) = \frac{1}{8}, \\
j &= 3: & u_{13} &= a_{13} = -2 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = 0 - 0 \left( -2 \right) = 0, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = 5 - \frac{3}{4} \left( -2 \right) - \left(- \frac{5}{8} \right) \left( 0 \right) = \frac{13}{2}, \\
&& \ell_{43} &= \frac{1}{u_{33}} \left( a_{43} - \ell_{41} u_{13} - \ell_{42} u_{23} \right) = \frac{1}{13/2} \left( 3 - \frac{1}{4} \left( -2 \right) - \frac{1}{8} \left( 0 \right) \right) = \frac{7}{13}, \\
j &= 4: & u_{14} &= a_{14} = -3 , \\
&& u_{24} &= a_{24} - \ell_{21} u_{14} = 3 - 0 \left( -3 \right) = 0, \\
&& u_{34} &= a_{34} - \ell_{31} u_{14} - \ell_{32} u_{24} = 1 - \frac{3}{4} \left( -3 \right) - \left(- \frac{5}{8} \right) \left( 3 \right) = 0, \\
&& u_{44} &= a_{44} - \ell_{41} u_{14} - \ell_{42} u_{24} - \ell_{43} u_{34} = 2 - \frac{1}{4} \left( -3 \right) - \frac{1}{8} \left( 3 \right) - \frac{7}{13} \left( \frac{41}{8} \right) = - \frac{5}{13}, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\\frac{3}{4} & - \frac{5}{8} & 1 & 0\\\frac{1}{4} & \frac{1}{8} & \frac{7}{13} & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}4 & -1 & -2 & -3\\0 & 2 & 0 & 3\\0 & 0 & \frac{13}{2} & \frac{41}{8}\\0 & 0 & 0 & - \frac{5}{13}\end{matrix}\right)\).
Solving \(L \vec{y} = P \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\\frac{3}{4} & - \frac{5}{8} & 1 & 0\\\frac{1}{4} & \frac{1}{8} & \frac{7}{13} & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{pmatrix} &=\left(\begin{matrix}-12\\13\\28\\21\end{matrix}\right) \\
y_{1} &= -12 \\
y_{2} &= 13 - 0 \left( -12 \right) = 13 , \\
y_{3} &= 28 - \frac{3}{4} \left( -12 \right) + \frac{5}{8} \left( 13 \right) = \frac{361}{8} , \\
y_{4} &= 21 - \frac{1}{4} \left( -12 \right) - \frac{1}{8} \left( 13 \right) - \frac{7}{13} \left( \frac{361}{8} \right) = - \frac{25}{13} .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}4 & -1 & -2 & -3\\0 & 2 & 0 & 3\\0 & 0 & \frac{13}{2} & \frac{41}{8}\\0 & 0 & 0 & - \frac{5}{13}\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix} &=\left(\begin{matrix}-12\\13\\\frac{361}{8}\\- \frac{25}{13}\end{matrix}\right) \\
x_{4} &= \frac{1}{- \frac{5}{13}} \left( - \frac{25}{13} \right) = 5 , \\
x_{3} &= \frac{1}{\frac{13}{2}} \left( \frac{361}{8} - \frac{41}{8} \left( 5 \right) \right) = 3 , \\
x_{2} &= \frac{1}{2} \left( 13 - 0 \left( 3 \right) - 3 \left( 5 \right) \right) = -1 , \\
x_{1} &= \frac{1}{4} \left( -12 + 1 \left( -1 \right) + 2 \left( 3 \right) + 3 \left( 5 \right) \right) = 2 .
\end{align*} \end{split}\]
(d) Perform partial pivoting on the coefficient matrix
\[\begin{split} \begin{align*}
& \left(\begin{matrix}1 & 5 & 2 & 2\\-2 & -4 & 2 & 0\\3 & 1 & -2 & -1\\-3 & -3 & 4 & -1\end{matrix}\right)
\begin{matrix} R_{1} \leftrightarrow R_{3}\\ \phantom{x} \\ \phantom{x} \\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}3 & 1 & -2 & -1\\-2 & -4 & 2 & 0\\1 & 5 & 2 & 2\\-3 & -3 & 4 & -1\end{matrix}\right)
\begin{matrix} \phantom{x} \\ R_{2} \leftrightarrow R_{3}\\ \phantom{x} \\ \phantom{x} \end{matrix}
\\ \longrightarrow
& \left(\begin{matrix}3 & 1 & -2 & -1\\1 & 5 & 2 & 2\\-2 & -4 & 2 & 0\\-3 & -3 & 4 & -1\end{matrix}\right)
\begin{matrix} \phantom{x} \\ \phantom{x} \\ R_{3} \leftrightarrow R_{4}\\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}3 & 1 & -2 & -1\\1 & 5 & 2 & 2\\-3 & -3 & 4 & -1\\-2 & -4 & 2 & 0\end{matrix}\right)
= PA.
\end{align*} \end{split}\]
Applying the same row operations to the identity matrix:
\[\begin{split} \begin{align*}
& \left(\begin{matrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{matrix}\right)
\begin{matrix} R_{1} \leftrightarrow R_{3}\\ \phantom{x} \\ \phantom{x} \\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}0 & 0 & 1 & 0\\0 & 1 & 0 & 0\\1 & 0 & 0 & 0\\0 & 0 & 0 & 1\end{matrix}\right)
\begin{matrix} \phantom{x} \\ R_{2} \leftrightarrow R_{3}\\ \phantom{x} \\ \phantom{x} \end{matrix}
\\ \longrightarrow
& \left(\begin{matrix}0 & 0 & 1 & 0\\1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 0 & 1\end{matrix}\right)
\begin{matrix} \phantom{x} \\ \phantom{x} \\ R_{3} \leftrightarrow R_{4}\\ \phantom{x} \end{matrix}
&& \longrightarrow
\left(\begin{matrix}0 & 0 & 1 & 0\\1 & 0 & 0 & 0\\0 & 0 & 0 & 1\\0 & 1 & 0 & 0\end{matrix}\right)
= P.
\end{align*} \end{split}\]
Calculate the LU decomposition of \(PA = \left(\begin{matrix}3 & 1 & -2 & -1\\1 & 5 & 2 & 2\\-3 & -3 & 4 & -1\\-2 & -4 & 2 & 0\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & u_{11} &= a_{11} = 3 , \\
&& \ell_{21} &= \frac{1}{u_{11}} \left( a_{21} \right) = \frac{1}{3} \left( 1 \right) = \frac{1}{3}, \\
&& \ell_{31} &= \frac{1}{u_{11}} \left( a_{31} \right) = \frac{1}{3} \left( -3 \right) = -1, \\
&& \ell_{41} &= \frac{1}{u_{11}} \left( a_{41} \right) = \frac{1}{3} \left( -2 \right) = - \frac{2}{3}, \\
j &= 2: & u_{12} &= a_{12} = 1 , \\
&& u_{22} &= a_{22} - \ell_{21} u_{12} = 5 - \frac{1}{3} \left( 1 \right) = \frac{14}{3}, \\
&& \ell_{32} &= \frac{1}{u_{22}} \left( a_{32} - \ell_{31} u_{12} \right) = \frac{1}{14/3} \left( -3 - \left( -1 \right) \left( 1 \right) \right) = - \frac{3}{7}, \\
&& \ell_{42} &= \frac{1}{u_{22}} \left( a_{42} - \ell_{41} u_{12} \right) = \frac{1}{14/3} \left( -4 - \left( - \frac{2}{3} \right) \left( 1 \right) \right) = - \frac{5}{7}, \\
j &= 3: & u_{13} &= a_{13} = -2 , \\
&& u_{23} &= a_{23} - \ell_{21} u_{13} = 2 - \frac{1}{3} \left( -2 \right) = 0, \\
&& u_{33} &= a_{33} - \ell_{31} u_{13} - \ell_{32} u_{23} = 4 - \left(-1 \right) \left( -2 \right) - \left(- \frac{3}{7} \right) \left( \frac{8}{3} \right) = \frac{22}{7}, \\
&& \ell_{43} &= \frac{1}{u_{33}} \left( a_{43} - \ell_{41} u_{13} - \ell_{42} u_{23} \right) = \frac{1}{22/7} \left( 2 - \left( - \frac{2}{3} \right) \left( -2 \right) - \left( - \frac{5}{7} \right) \left( \frac{8}{3} \right) \right) = \frac{9}{11}, \\
j &= 4: & u_{14} &= a_{14} = -1 , \\
&& u_{24} &= a_{24} - \ell_{21} u_{14} = 2 - \frac{1}{3} \left( -1 \right) = 0, \\
&& u_{34} &= a_{34} - \ell_{31} u_{14} - \ell_{32} u_{24} = -1 - \left(-1 \right) \left( -1 \right) - \left(- \frac{3}{7} \right) \left( \frac{7}{3} \right) = 0, \\
&& u_{44} &= a_{44} - \ell_{41} u_{14} - \ell_{42} u_{24} - \ell_{43} u_{34} = 0 - \left(- \frac{2}{3} \right) \left( -1 \right) - \left(- \frac{5}{7} \right) \left( \frac{7}{3} \right) - \frac{9}{11} \left( -1 \right) = \frac{20}{11}, \\
\end{align*} \end{split}\]
So \(L = \left(\begin{matrix}1 & 0 & 0 & 0\\\frac{1}{3} & 1 & 0 & 0\\-1 & - \frac{3}{7} & 1 & 0\\- \frac{2}{3} & - \frac{5}{7} & \frac{9}{11} & 1\end{matrix}\right)\) and \(U = \left(\begin{matrix}3 & 1 & -2 & -1\\0 & \frac{14}{3} & \frac{8}{3} & \frac{7}{3}\\0 & 0 & \frac{22}{7} & -1\\0 & 0 & 0 & \frac{20}{11}\end{matrix}\right)\).
Solving \(L \vec{y} = P \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}1 & 0 & 0 & 0\\\frac{1}{3} & 1 & 0 & 0\\-1 & - \frac{3}{7} & 1 & 0\\- \frac{2}{3} & - \frac{5}{7} & \frac{9}{11} & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{pmatrix} &=\left(\begin{matrix}-2\\-10\\4\\10\end{matrix}\right) \\
y_{1} &= -2 \\
y_{2} &= -10 - \frac{1}{3} \left( -2 \right) = - \frac{28}{3} , \\
y_{3} &= 4 + 1 \left( -2 \right) + \frac{3}{7} \left( - \frac{28}{3} \right) = -2 , \\
y_{4} &= 10 + \frac{2}{3} \left( -2 \right) + \frac{5}{7} \left( - \frac{28}{3} \right) - \frac{9}{11} \left( -2 \right) = \frac{40}{11} .
\end{align*} \end{split}\]
Solving \(U \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}3 & 1 & -2 & -1\\0 & \frac{14}{3} & \frac{8}{3} & \frac{7}{3}\\0 & 0 & \frac{22}{7} & -1\\0 & 0 & 0 & \frac{20}{11}\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix} &=\left(\begin{matrix}-2\\- \frac{28}{3}\\-2\\\frac{40}{11}\end{matrix}\right) \\
x_{4} &= \frac{1}{\frac{20}{11}} \left( \frac{40}{11} \right) = 2 , \\
x_{3} &= \frac{1}{\frac{22}{7}} \left( -2 + 1 \left( 2 \right) \right) = 0 , \\
x_{2} &= \frac{1}{\frac{14}{3}} \left( - \frac{28}{3} - \frac{8}{3} \left( 0 \right) - \frac{7}{3} \left( 2 \right) \right) = -3 , \\
x_{1} &= \frac{1}{3} \left( -2 - 1 \left( -3 \right) + 2 \left( 0 \right) + 1 \left( 2 \right) \right) = 1 .
\end{align*} \end{split}\]
Solution to Exercise 6.3
(a) Calculate Cholesky decomposition of the coefficient matrix \(A = \left(\begin{matrix}16 & 16 & 4\\16 & 25 & 10\\4 & 10 & 6\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & \ell_{11} &= \sqrt{a_{11}} = \sqrt{16} = 4, \\
&& \ell_{21} &= \frac{1}{ \ell_{11} } \left( a_{21} \right) = \frac{1}{4} \left( 16 \right) = 4, \\
&& \ell_{31} &= \frac{1}{ \ell_{11} } \left( a_{31} \right) = \frac{1}{4} \left( 4 \right) = 1, \\
j &= 2: & \ell_{22} &= \sqrt{a_{22} - \ell_{21}^2} = \sqrt{25- 4^2} = 3, \\
&& \ell_{32} &= \frac{1}{ \ell_{22} } \left( a_{32} - \ell_{31} \ell_{21} \right) = \frac{1}{3} \left( 10 - 1 \left( 4 \right) \right) = 2, \\
j &= 3: & \ell_{33} &= \sqrt{a_{33} - \ell_{31}^2 - \ell_{32}^2} = \sqrt{6- 1^2- 2^2} = 1, \\
\end{align*} \end{split}\]
so \(L = \left(\begin{matrix}4 & 0 & 0\\4 & 3 & 0\\1 & 2 & 1\end{matrix}\right)\) .
Solving \(L \vec{y} = \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}4 & 0 & 0\\4 & 3 & 0\\1 & 2 & 1\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \end{pmatrix} &=\left(\begin{matrix}-8\\-47\\-30\end{matrix}\right) \\
y_{1} &= \frac{1}{4} \left( -8 \right) = -2 , \\
y_{2} &= \frac{1}{3} \left( -47 - 4 \left( -2 \right) \right) = -13 , \\
y_{3} &= \frac{1}{1} \left( -30 - 1 \left( -2 \right) - 2 \left( -13 \right) \right) = -2 .
\end{align*} \end{split}\]
Solving \(L^\mathsf{T} \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}4 & 4 & 1\\0 & 3 & 2\\0 & 0 & 1\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix} &=\left(\begin{matrix}-2\\-13\\-2\end{matrix}\right) \\
x_{3} &= \frac{1}{1} \left( -2 \right) = -2 , \\
x_{2} &= \frac{1}{3} \left( -13 - 2 \left( -2 \right) \right) = -3 , \\
x_{1} &= \frac{1}{4} \left( -2 - 4 \left( -3 \right) - 1 \left( -2 \right) \right) = 3 .
\end{align*} \end{split}\]
(b) Calculate Cholesky decomposition of the coefficient matrix \(A = \left(\begin{matrix}4 & 2 & 8\\2 & 17 & 20\\8 & 20 & 41\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & \ell_{11} &= \sqrt{a_{11}} = \sqrt{4} = 2, \\
&& \ell_{21} &= \frac{1}{ \ell_{11} } \left( a_{21} \right) = \frac{1}{2} \left( 2 \right) = 1, \\
&& \ell_{31} &= \frac{1}{ \ell_{11} } \left( a_{31} \right) = \frac{1}{2} \left( 8 \right) = 4, \\
j &= 2: & \ell_{22} &= \sqrt{a_{22} - \ell_{21}^2} = \sqrt{17- 1^2} = 4, \\
&& \ell_{32} &= \frac{1}{ \ell_{22} } \left( a_{32} - \ell_{31} \ell_{21} \right) = \frac{1}{4} \left( 20 - 4 \left( 1 \right) \right) = 4, \\
j &= 3: & \ell_{33} &= \sqrt{a_{33} - \ell_{31}^2 - \ell_{32}^2} = \sqrt{41- 4^2- 4^2} = 3, \\
\end{align*} \end{split}\]
so \(L = \left(\begin{matrix}2 & 0 & 0\\1 & 4 & 0\\4 & 4 & 3\end{matrix}\right)\) .
Solving \(L \vec{y} = \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}2 & 0 & 0\\1 & 4 & 0\\4 & 4 & 3\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \end{pmatrix} &=\left(\begin{matrix}36\\50\\122\end{matrix}\right) \\
y_{1} &= \frac{1}{2} \left( 36 \right) = 18 , \\
y_{2} &= \frac{1}{4} \left( 50 - 1 \left( 18 \right) \right) = 8 , \\
y_{3} &= \frac{1}{3} \left( 122 - 4 \left( 18 \right) - 4 \left( 8 \right) \right) = 6 .
\end{align*} \end{split}\]
Solving \(L^\mathsf{T} \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}2 & 1 & 4\\0 & 4 & 4\\0 & 0 & 3\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \end{pmatrix} &=\left(\begin{matrix}18\\8\\6\end{matrix}\right) \\
x_{3} &= \frac{1}{3} \left( 6 \right) = 2 , \\
x_{2} &= \frac{1}{4} \left( 8 - 4 \left( 2 \right) \right) = 0 , \\
x_{1} &= \frac{1}{2} \left( 18 - 1 \left( 0 \right) - 4 \left( 2 \right) \right) = 5 .
\end{align*} \end{split}\]
(c) Calculate Cholesky decomposition of the coefficient matrix \(A = \left(\begin{matrix}9 & -9 & 0 & 6\\-9 & 25 & 8 & -10\\0 & 8 & 8 & -2\\-6 & -10 & -2 & 33\end{matrix}\right)\):
\[\begin{split} \begin{align*}
j &= 1: & \ell_{11} &= \sqrt{a_{11}} = \sqrt{9} = 3, \\
&& \ell_{21} &= \frac{1}{ \ell_{11} } \left( a_{21} \right) = \frac{1}{3} \left( -9 \right) = -3, \\
&& \ell_{31} &= \frac{1}{ \ell_{11} } \left( a_{31} \right) = \frac{1}{3} \left( 0 \right) = 0, \\
&& \ell_{41} &= \frac{1}{ \ell_{11} } \left( a_{41} \right) = \frac{1}{3} \left( -6 \right) = -2, \\
j &= 2: & \ell_{22} &= \sqrt{a_{22} - \ell_{21}^2} = \sqrt{25- -3^2} = 4, \\
&& \ell_{32} &= \frac{1}{ \ell_{22} } \left( a_{32} - \ell_{31} \ell_{21} \right) = \frac{1}{4} \left( 8 - 0 \left( -3 \right) \right) = 2, \\
&& \ell_{42} &= \frac{1}{ \ell_{22} } \left( a_{42} - \ell_{41} \ell_{21} \right) = \frac{1}{4} \left( -10 - -2 \left( -3 \right) \right) = -4, \\
j &= 3: & \ell_{33} &= \sqrt{a_{33} - \ell_{31}^2 - \ell_{32}^2} = \sqrt{8- 0^2- 2^2} = 2, \\
&& \ell_{43} &= \frac{1}{ \ell_{33} } \left( a_{43} - \ell_{41} \ell_{31} - \ell_{42} \ell_{32} \right) = \frac{1}{2} \left( -2 - -2 \left( 0 \right) - -4 \left( 2 \right) \right) = 3, \\
j &= 4: & \ell_{44} &= \sqrt{a_{44} - \ell_{41}^2 - \ell_{42}^2 - \ell_{43}^2} = \sqrt{33- -2^2- -4^2- 3^2} = 2, \\
\end{align*} \end{split}\]
so \(L = \left(\begin{matrix}3 & 0 & 0 & 0\\-3 & 4 & 0 & 0\\0 & 2 & 2 & 0\\-2 & -4 & 3 & 2\end{matrix}\right)\) .
Solving \(L \vec{y} = \vec{b}\) using forward substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}3 & 0 & 0 & 0\\-3 & 4 & 0 & 0\\0 & 2 & 2 & 0\\-2 & -4 & 3 & 2\end{matrix}\right) \begin{pmatrix} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{pmatrix} &=\left(\begin{matrix}12\\-116\\-58\\91\end{matrix}\right) \\
y_{1} &= \frac{1}{3} \left( 12 \right) = 4 , \\
y_{2} &= \frac{1}{4} \left( -116 + 3 \left( 4 \right) \right) = -26 , \\
y_{3} &= \frac{1}{2} \left( -58 - 0 \left( 4 \right) - 2 \left( -26 \right) \right) = -3 , \\
y_{4} &= \frac{1}{2} \left( 91 + 2 \left( 4 \right) + 4 \left( -26 \right) - 3 \left( -3 \right) \right) = 2 .
\end{align*} \end{split}\]
Solving \(L^\mathsf{T} \vec{x} = \vec{y}\) using back substitution
\[\begin{split} \begin{align*}
\left(\begin{matrix}3 & -3 & 0 & -2\\0 & 4 & 2 & -4\\0 & 0 & 2 & 3\\0 & 0 & 0 & 2\end{matrix}\right) \begin{pmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{pmatrix} &=\left(\begin{matrix}4\\-26\\-3\\2\end{matrix}\right) \\
x_{4} &= \frac{1}{2} \left( 2 \right) = 1 , \\
x_{3} &= \frac{1}{2} \left( -3 - 3 \left( 1 \right) \right) = -3 , \\
x_{2} &= \frac{1}{4} \left( -26 - 2 \left( -3 \right) + 4 \left( 1 \right) \right) = -4 , \\
x_{1} &= \frac{1}{3} \left( 4 + 3 \left( -4 \right) - 0 \left( -3 \right) + 2 \left( 1 \right) \right) = -2 .
\end{align*} \end{split}\]
Solution to Exercise 6.4
(a)
\[\begin{split} \begin{align*}
j &= 1: & \vec{u}_1 &= \vec{a}_1 = \left(\begin{matrix}1\\-1\end{matrix}\right), \\
&& r_{11} &= \|\vec{u}_1\| = \sqrt{2}, \\
&& \vec{q}_1 &= \frac{\vec{u}_1}{r_{11}} = \frac{1}{\sqrt{2}} \left(\begin{matrix}1\\-1\end{matrix}\right) = \left(\begin{matrix}\frac{\sqrt{2}}{2}\\- \frac{\sqrt{2}}{2}\end{matrix}\right), \\
j &= 2: & r_{12} &= \vec{q}_1 \cdot \vec{a}_2 = \left(\begin{matrix}\frac{\sqrt{2}}{2}\\- \frac{\sqrt{2}}{2}\end{matrix}\right) \cdot \left(\begin{matrix}1\\0\end{matrix}\right)= \frac{\sqrt{2}}{2}, \\
&& \vec{u}_2 &= \vec{a}_2 - r_{12} \vec{q}_1 = \left(\begin{matrix}1\\0\end{matrix}\right) - \frac{\sqrt{2}}{2} \left(\begin{matrix}\frac{\sqrt{2}}{2}\\- \frac{\sqrt{2}}{2}\end{matrix}\right) = \left(\begin{matrix}\frac{1}{2}\\\frac{1}{2}\end{matrix}\right), \\
&& r_{22} &= \|\vec{u}_2\| = \frac{\sqrt{2}}{2}, \\
&& \vec{q}_2 &= \frac{\vec{u}_2}{r_{22}} = \frac{1}{\frac{\sqrt{2}}{2}} \left(\begin{matrix}\frac{1}{2}\\\frac{1}{2}\end{matrix}\right) = \left(\begin{matrix}\frac{\sqrt{2}}{2}\\\frac{\sqrt{2}}{2}\end{matrix}\right), \\
\end{align*} \end{split}\]
so \(Q = \left(\begin{matrix}\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2}\\- \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2}\end{matrix}\right)\) and \(R = \left(\begin{matrix}\sqrt{2} & \frac{\sqrt{2}}{2}\\0 & \frac{\sqrt{2}}{2}\end{matrix}\right)\).
(b)
\[\begin{split} \begin{align*}
j &= 1: & \vec{u}_1 &= \vec{a}_1 = \left(\begin{matrix}6\\3\\2\end{matrix}\right), \\
&& r_{11} &= \|\vec{u}_1\| = 7, \\
&& \vec{q}_1 &= \frac{\vec{u}_1}{r_{11}} = \frac{1}{7} \left(\begin{matrix}6\\3\\2\end{matrix}\right) = \left(\begin{matrix}\frac{6}{7}\\\frac{3}{7}\\\frac{2}{7}\end{matrix}\right), \\
j &= 2: & r_{12} &= \vec{q}_1 \cdot \vec{a}_2 = \left(\begin{matrix}\frac{6}{7}\\\frac{3}{7}\\\frac{2}{7}\end{matrix}\right) \cdot \left(\begin{matrix}6\\6\\1\end{matrix}\right)= 8, \\
&& \vec{u}_2 &= \vec{a}_2 - r_{12} \vec{q}_1 = \left(\begin{matrix}6\\6\\1\end{matrix}\right) - 8 \left(\begin{matrix}\frac{6}{7}\\\frac{3}{7}\\\frac{2}{7}\end{matrix}\right) = \left(\begin{matrix}- \frac{6}{7}\\\frac{18}{7}\\- \frac{9}{7}\end{matrix}\right), \\
&& r_{22} &= \|\vec{u}_2\| = 3, \\
&& \vec{q}_2 &= \frac{\vec{u}_2}{r_{22}} = \frac{1}{3} \left(\begin{matrix}- \frac{6}{7}\\\frac{18}{7}\\- \frac{9}{7}\end{matrix}\right) = \left(\begin{matrix}- \frac{2}{7}\\\frac{6}{7}\\- \frac{3}{7}\end{matrix}\right), \\
j &= 3: & r_{13} &= \vec{q}_1 \cdot \vec{a}_3 = \left(\begin{matrix}\frac{6}{7}\\\frac{3}{7}\\\frac{2}{7}\end{matrix}\right) \cdot \left(\begin{matrix}1\\1\\1\end{matrix}\right)= \frac{11}{7}, \\
&& r_{23} &= \vec{q}_2 \cdot \vec{a}_3 = \left(\begin{matrix}- \frac{2}{7}\\\frac{6}{7}\\- \frac{3}{7}\end{matrix}\right) \cdot \left(\begin{matrix}1\\1\\1\end{matrix}\right)= \frac{1}{7}, \\
&& \vec{u}_3 &= \vec{a}_3 - r_{13} \vec{q}_1 - r_{23} \vec{q}_2 = \left(\begin{matrix}1\\1\\1\end{matrix}\right) - \frac{11}{7} \left(\begin{matrix}\frac{6}{7}\\\frac{3}{7}\\\frac{2}{7}\end{matrix}\right) - \frac{1}{7} \left(\begin{matrix}- \frac{2}{7}\\\frac{6}{7}\\- \frac{3}{7}\end{matrix}\right) = \left(\begin{matrix}- \frac{15}{49}\\\frac{10}{49}\\\frac{30}{49}\end{matrix}\right), \\
&& r_{33} &= \|\vec{u}_3\| = \frac{5}{7}, \\
&& \vec{q}_3 &= \frac{\vec{u}_3}{r_{33}} = \frac{1}{\frac{5}{7}} \left(\begin{matrix}- \frac{15}{49}\\\frac{10}{49}\\\frac{30}{49}\end{matrix}\right) = \left(\begin{matrix}- \frac{3}{7}\\\frac{2}{7}\\\frac{6}{7}\end{matrix}\right), \\
\end{align*} \end{split}\]
so \(Q = \left(\begin{matrix}\frac{6}{7} & - \frac{2}{7} & - \frac{3}{7}\\\frac{3}{7} & \frac{6}{7} & \frac{2}{7}\\\frac{2}{7} & - \frac{3}{7} & \frac{6}{7}\end{matrix}\right)\) and \(R = \left(\begin{matrix}7 & 8 & \frac{11}{7}\\0 & 3 & \frac{1}{7}\\0 & 0 & \frac{5}{7}\end{matrix}\right)\).
(c)
\[\begin{split} \begin{align*}
j &= 1: & \vec{u}_1 &= \vec{a}_1 = \left(\begin{matrix}1\\1\\1\\1\end{matrix}\right), \\
&& r_{11} &= \|\vec{u}_1\| = 2, \\
&& \vec{q}_1 &= \frac{\vec{u}_1}{r_{11}} = \frac{1}{2} \left(\begin{matrix}1\\1\\1\\1\end{matrix}\right) = \left(\begin{matrix}\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\end{matrix}\right), \\
j &= 2: & r_{12} &= \vec{q}_1 \cdot \vec{a}_2 = \left(\begin{matrix}\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\end{matrix}\right) \cdot \left(\begin{matrix}2\\4\\-4\\2\end{matrix}\right)= 2, \\
&& \vec{u}_2 &= \vec{a}_2 - r_{12} \vec{q}_1 = \left(\begin{matrix}2\\4\\-4\\2\end{matrix}\right) - 2 \left(\begin{matrix}\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\end{matrix}\right) = \left(\begin{matrix}1\\3\\-5\\1\end{matrix}\right), \\
&& r_{22} &= \|\vec{u}_2\| = 6, \\
&& \vec{q}_2 &= \frac{\vec{u}_2}{r_{22}} = \frac{1}{6} \left(\begin{matrix}1\\3\\-5\\1\end{matrix}\right) = \left(\begin{matrix}\frac{1}{6}\\\frac{1}{2}\\- \frac{5}{6}\\\frac{1}{6}\end{matrix}\right), \\
j &= 3: & r_{13} &= \vec{q}_1 \cdot \vec{a}_3 = \left(\begin{matrix}\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\end{matrix}\right) \cdot \left(\begin{matrix}1\\3\\6\\1\end{matrix}\right)= \frac{11}{2}, \\
&& r_{23} &= \vec{q}_2 \cdot \vec{a}_3 = \left(\begin{matrix}\frac{1}{6}\\\frac{1}{2}\\- \frac{5}{6}\\\frac{1}{6}\end{matrix}\right) \cdot \left(\begin{matrix}1\\3\\6\\1\end{matrix}\right)= - \frac{19}{6}, \\
&& \vec{u}_3 &= \vec{a}_3 - r_{13} \vec{q}_1 - r_{23} \vec{q}_2 = \left(\begin{matrix}1\\3\\6\\1\end{matrix}\right) - \frac{11}{2} \left(\begin{matrix}\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\\\frac{1}{2}\end{matrix}\right) + \frac{19}{6} \left(\begin{matrix}\frac{1}{6}\\\frac{1}{2}\\- \frac{5}{6}\\\frac{1}{6}\end{matrix}\right) = \left(\begin{matrix}- \frac{11}{9}\\\frac{11}{6}\\\frac{11}{18}\\- \frac{11}{9}\end{matrix}\right), \\
&& r_{33} &= \|\vec{u}_3\| = \frac{11 \sqrt{2}}{6}, \\
&& \vec{q}_3 &= \frac{\vec{u}_3}{r_{33}} = \frac{1}{\frac{11 \sqrt{2}}{6}} \left(\begin{matrix}- \frac{11}{9}\\\frac{11}{6}\\\frac{11}{18}\\- \frac{11}{9}\end{matrix}\right) = \left(\begin{matrix}- \frac{\sqrt{2}}{3}\\\frac{\sqrt{2}}{2}\\\frac{\sqrt{2}}{6}\\- \frac{\sqrt{2}}{3}\end{matrix}\right), \\
\end{align*} \end{split}\]
so \(Q = \left(\begin{matrix}\frac{1}{2} & \frac{1}{6} & - \frac{\sqrt{2}}{3}\\\frac{1}{2} & \frac{1}{2} & \frac{\sqrt{2}}{2}\\\frac{1}{2} & - \frac{5}{6} & \frac{\sqrt{2}}{6}\\\frac{1}{2} & \frac{1}{6} & - \frac{\sqrt{2}}{3}\end{matrix}\right)\) and \(R = \left(\begin{matrix}2 & 2 & \frac{11}{2}\\0 & 6 & - \frac{19}{6}\\0 & 0 & \frac{11 \sqrt{2}}{6}\end{matrix}\right)\).
Solution to Exercise 6.5
(a) \(j = 1\)
import numpy as np
A = np.array([[1, 1], [-1, 0]])
m = A.shape[0]
R = np.copy(A)
Q = np.eye(m)
# j = 1
e = np.eye(m)[:,0]
u = R[:,0]
u = u + np.sign(u[0]) * np.linalg.norm(u) * e
v = u / np.linalg.norm(u)
H = np.eye(m) - 2 * np.dot(v.T, v)
print(np.dot(v, v.T))
print("j = 1:\nH = \n", H)
R = np.dot(H, R)
Q = np.dot(Q, H)
print("R = \n", R)
print("Q = \n", Q)
# j = 2
e = np.eye(m)[:,1]
u = R[:,1]
u[0] = 0
u = u + np.sign(u[0]) * np.linalg.norm(u) * e
u /= np.linalg.norm(u)
H = np.eye(m) - 2 * np.dot(u, u.T)
print("j = 2:\nH = \n", H)
R = np.dot(H, R)
Q = np.dot(Q, H)
print("R = \n", R)
print("Q = \n", Q)
0.9999999999999998
j = 1:
H =
[[-1. -2.]
[-2. -1.]]
R =
[[ 1. -1.]
[-1. -2.]]
Q =
[[-1. -2.]
[-2. -1.]]
j = 2:
H =
[[-1. -2.]
[-2. -1.]]
R =
[[ 1. 4.]
[-1. 2.]]
Q =
[[5. 4.]
[4. 5.]]