140 lines
3.9 KiB
TeX
140 lines
3.9 KiB
TeX
\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. |