lizfcm/homeworks/hw-5.tex

95 lines
3.5 KiB
TeX
Raw Permalink Normal View History

2023-11-06 10:52:40 -05:00
% Created 2023-11-01 Wed 20:49
2023-10-30 21:07:43 -04:00
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\notindent \notag \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
\author{Elizabeth Hunt}
\date{\today}
\title{Homework 5}
\hypersetup{
pdfauthor={Elizabeth Hunt},
pdftitle={Homework 5},
pdfkeywords={},
pdfsubject={},
pdfcreator={Emacs 28.2 (Org mode 9.7-pre)},
pdflang={English}}
\begin{document}
\maketitle
\setlength\parindent{0pt}
\section{Question One}
2023-11-06 10:52:40 -05:00
\label{sec:org4e80298}
2023-10-30 21:07:43 -04:00
See LIZFCM \(\rightarrow\) Matrix Routines \(\rightarrow\) \texttt{lu decomp} \& \texttt{bsubst}.
The test \texttt{UTEST(matrix, lu\_decomp)} is a unit test for the \texttt{lu\_decomp} routine,
and \texttt{UTEST(matrix, bsubst)} verifies back substitution on an upper triangular
3 \texttimes{} 3 matrix with a known solution that can be verified manually.
Both can be found in \texttt{tests/matrix.t.c}.
\section{Question Two}
2023-11-06 10:52:40 -05:00
\label{sec:orga73d05c}
2023-10-30 21:07:43 -04:00
Unless the following are met, the resulting solution will be garbage.
\begin{enumerate}
\item The matrix \(U\) must be not be singular.
\item \(U\) must be square (or it will fail the \texttt{assert}).
\item The system created by \(Ux = b\) must be consistent.
2023-11-06 10:52:40 -05:00
\item \(U\) is (quite obviously) in upper-triangular form.
2023-10-30 21:07:43 -04:00
\end{enumerate}
Thus, the actual calculation performing the \(LU\) decomposition
(in \texttt{lu\_decomp}) does a sanity
check for 1-3 will fail an assert, should a point along the diagonal (pivot) be
zero, or the matrix be non-factorable.
\section{Question Three}
2023-11-06 10:52:40 -05:00
\label{sec:org35163c5}
2023-10-30 21:07:43 -04:00
See LIZFCM \(\rightarrow\) Matrix Routines \(\rightarrow\) \texttt{fsubst}.
\texttt{UTEST(matrix, fsubst)} verifies forward substitution on a lower triangular 3 \texttimes{} 3
matrix with a known solution that can be verified manually.
\section{Question Four}
2023-11-06 10:52:40 -05:00
\label{sec:org79d9061}
2023-10-30 21:07:43 -04:00
See LIZFCM \(\rightarrow\) Matrix Routines \(\rightarrow\) \texttt{gaussian\_elimination} and \texttt{solve\_gaussian\_elimination}.
\section{Question Five}
2023-11-06 10:52:40 -05:00
\label{sec:orgc6ac464}
2023-10-30 21:07:43 -04:00
See LIZFCM \(\rightarrow\) Matrix Routines \(\rightarrow\) \texttt{m\_dot\_v}, and the \texttt{UTEST(matrix, m\_dot\_v)} in
\texttt{tests/matrix.t.c}.
\section{Question Six}
2023-11-06 10:52:40 -05:00
\label{sec:org66fedab}
2023-10-30 21:07:43 -04:00
See \texttt{UTEST(matrix, solve\_gaussian\_elimination)} in \texttt{tests/matrix.t.c}, which generates a diagonally dominant 10 \texttimes{} 10 matrix
and shows that the solution is consistent with the initial matrix, according to the steps given. Then,
we do a dot product between each row of the diagonally dominant matrix and the solution vector to ensure
it is near equivalent to the input vector.
\section{Question Seven}
2023-11-06 10:52:40 -05:00
\label{sec:org6897ff2}
2023-10-30 21:07:43 -04:00
See \texttt{UTEST(matrix, solve\_matrix\_lu\_bsubst)} which does the same test in Question Six with the solution according to
\texttt{solve\_matrix\_lu\_bsubst} as shown in the Software Manual.
\section{Question Eight}
2023-11-06 10:52:40 -05:00
\label{sec:org5d529dd}
2023-10-30 21:07:43 -04:00
No, since the time complexity for Gaussian Elimination is always less than that of the LU factorization solution by \(O(n^2)\) operations
(in LU factorization we perform both backwards and forwards substitutions proceeding the LU decomp, in Gaussian Elimination we only need
back substitution).
\section{Question Nine, Ten}
2023-11-06 10:52:40 -05:00
\label{sec:org0fb8e09}
2023-10-30 21:07:43 -04:00
See LIZFCM Software manual and shared library in \texttt{dist} after compiling.
\end{document}