\subsection{Problem 3}
Solve the system:
\begin{equation*}
    \systeme{0.0001x_1+x_2=1,x_1+x_2=2}
\end{equation*}
with the Gaussian elimination with and without pivoting at the round-off error limited to 3 significant digits. Compute the condition number of the system matrix.
\subsubsection*{Mathematics}
Not only pivoting helps with $a_{ii}=0$ problem but, by choosing the biggest entry, ensures the stability of the LU factorization. As explained in detail in~~\cite[section 3.3]{GoluVanl96} for the factorization errors to be small, the diagonal entries of $\matr{U}$ matrix has to be small. Please note that in both solutions and condition number computations precision was limited to 3 significant digits.
\subsubsection*{Solution without pivoting}
\begin{equation*}
\begin{split}
    \begin{amatrix}{1}{1}
        \matr{A} & \matr{b}
    \end{amatrix} = 
    \begin{amatrix}{2}{1}
        10^{-4} & 1 & 1\\
        1 & 1 & 2
    \end{amatrix}
    \xrightarrow[\substack{R_2-10^{4}R_1}]{}
    \begin{amatrix}{2}{1}
        10^{-4} & 1 & 1\\
        0 & -10^{4} & -10^{4}
    \end{amatrix}
\end{split}
\end{equation*}
gives us
\begin{equation*}
    \begin{cases}
    x_1=0\\
    x_2=1\\
    \end{cases}
\end{equation*}
which is obviously contradictory to $R_2$.

\subsubsection*{Solution with pivoting}
\begin{equation*}
\begin{split}
    \begin{amatrix}{1}{1}
        \matr{A} & \matr{b}
    \end{amatrix} = 
    \begin{amatrix}{2}{1}
        10^{-4} & 1 & 1\\
        1 & 1 & 2
    \end{amatrix}
    \xrightarrow[R_1\leftrightarrow R_2]{}
    \begin{amatrix}{2}{1}
        1 & 1 & 2 \\
        10^{-4} & 1 & 1
    \end{amatrix}
    \xrightarrow[\substack{R_2-10^{-4}R_1}]{}
    \begin{amatrix}{2}{1}
        1 & 1 & 2 \\
        0 & 1 & 1
    \end{amatrix}
\end{split}
\end{equation*}
gives us
\begin{equation*}
    \begin{cases}
    x_1=1\\
    x_2=1
    \end{cases}
\end{equation*}
\subsubsection*{Condition number}
Condition number should describe the stability of a computed matrix. The bigger the condition number $\kappa$ the less stable the (coefficient) matrix is. It is computed as: 
\begin{equation}
    \kappa(\mathbf{A})=||\mathbf{A}||_2\cdot||\mathbf{A}^{-1}||_2
\end{equation}
where 
\begin{equation}\label{eqn:2-norm}
\begin{split}
    ||\mathbf{A}||_2 = \sqrt{\lambda_{max}A^TA}
\end{split}
\end{equation}
$\matr{A}^{-1}$ may be computed via Gauss-Jordan algorithm with pivoting:
\begin{equation*}
\begin{split}
    \begin{amatrix}{1}{1}
        \matr{A} & \matr{I}
    \end{amatrix} = 
    \begin{amatrix}{2}{2}
        \frac{1}{1000} & 1 & 1 & 0\\
        1 & 1 & 0 & 1
    \end{amatrix}
    \xrightarrow[R_1\leftrightarrow R_2]{}
    \begin{amatrix}{2}{2}
        1 & 1 & 0 & 1\\
        \frac{1}{1000} & 1 & 1 & 0
    \end{amatrix}
    \xrightarrow[\substack{R_2-\frac{1}{1000}R_2}]{}\\
    \xrightarrow[\substack{R_2-\frac{1}{1000}R_2}]{}
    \begin{amatrix}{2}{2}
        1 & 1 & 0 & 1\\
        0 & 1 & 1 & 0
    \end{amatrix}
    \xrightarrow[\substack{R_1-R_2}]{}
    \begin{amatrix}{2}{2}
        1 & 0 & -1 & 1\\
        0 & 1 & 1 & 0
    \end{amatrix} = 
    \begin{amatrix}{1}{1}
        \matr{I} & \matr{A^{-1}}
    \end{amatrix}
\end{split}
\end{equation*}
Now, using the equation~\ref{eqn:2-norm}

\parbox{0.5\textwidth}{
\begin{gather*}
    \matr{A}^T\matr{A} = 
    \begin{bmatrix}
        1 & 1 \\
        1 & 2
    \end{bmatrix} \\
    \det\begin{pmatrix}
        1-\lambda & 1 \\
        1 & 2-\lambda
    \end{pmatrix} = 0 \\
    \lambda=\frac{3\pm\sqrt{5}}{2}
    \end{gather*}
}
\parbox{0.5\textwidth}{
\begin{gather*}
     \matr{A}^{-1^T}\matr{A}^{-1} = 
    \begin{bmatrix}
        2 & -1 \\
        -1 & 1
    \end{bmatrix} \\
    \det\begin{pmatrix}
        2-\lambda & -1 \\
        -1 & 1-\lambda
    \end{pmatrix} = 0 \\
    \lambda=\frac{3\pm\sqrt{5}}{2}
\end{gather*}
}
we finally obtain
\begin{equation*}
    \kappa(\mathbf{A})=\frac{3\pm\sqrt{5}}{2}\approx2.618
\end{equation*}
which is a very low number indicating, that the matrix $\matr{A}$ is computationally stable.