\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\else % if luatex or xelatex
\ifxetex
\usepackage{mathspec}
\makeatletter % undo the wrong changes made by mathspec
\let\RequirePackage\original@RequirePackage
\let\usepackage\RequirePackage
\makeatother
\else
\usepackage{fontspec}
\fi
\defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage{hyperref}
\hypersetup{unicode=true,
pdftitle={Homework 8},
pdfborder={0 0 0},
breaklinks=true}
\urlstyle{same} % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
\title{Homework 8}
\input{preamble.tex}
\title{Homework}
\begin{document}
\maketitle
\section{Homework 8}\label{homework-8}
Please answer the following questions in complete sentences in a clearly
prepared manuscript and submit the solution by the due date on
Blackboard (around Sunday, November 4th, 2018.)
Remember that this is a graduate class. There may be elements of the
problem statements that require you to fill in appropriate assumptions.
You are also responsible for determining what evidence to include. An
answer alone is rarely sufficient, but neither is an overly verbose
description required. Use your judgement to focus your discussion on the
most interesting pieces. The answer to ``should I include `something' in
my solution?'' will almost always be: Yes, if you think it helps support
your answer.
\subsection{Problem 0: Homework
checklist}\label{problem-0-homework-checklist}
\begin{itemize}
\item
Please identify anyone, whether or not they are in the class, with
whom you discussed your homework. This problem is worth 1 point, but
on a multiplicative scale.
\item
Make sure you have included your source-code and prepared your
solution according to the most recent Piazza note on homework
submissions.
\end{itemize}
\subsection{Problem 1: Accurate
summation}\label{problem-1-accurate-summation}
Consider a list of \(n\) numbers. For simplicity, assume that all
numbers are positive so you don't have to write a lot of absolute
values.
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Show that the following algorithm is backwards stable.
\begin{verbatim}
function mysum(x::Vector{Float64})
s = zero(Float64)
for i=1:length(x)
s += x[i]
end
return s
end
\end{verbatim}
Which requires showing that \(\text{mysum}(\vx) = \sum \hat{x}_i\)
where \(\normof{\hat{\vx} - \vx}/\normof{\vx} \le C_n \eps\) where
\(\eps\) is the unit-roundoff for Float64.
\item
Consider adding three positive numbers together \(a, b, c\). Describe
how to compute \(s = a+b+c\) with the greatest accuracy.
\item
Use the results of part 2 to describe a way to permute the input
\(\vx\) to \texttt{mysum} to attain the greatest accuracy. Find an
input vector \(\vx\) where this new ordering gives a measurable change
in the floating point accuracy as determined by the number of correct
digits in the mantissa. (Hint, this means you should know the true sum
of your vector so that you can identify it's best floating point
representation.)
\item
Lookup the Kahan summation algorithm and implement it to sum a vector.
Compare the accuracy with what you found in part 3.
\end{enumerate}
\subsection{Problem 2: Quadratic
equations}\label{problem-2-quadratic-equations}
Read through the stack exchange post on solving quadratic equations.
\url{https://math.stackexchange.com/questions/311382/solving-a-quadratic-equation-with-precision-when-using-floating-point-variables}
This suggests a number of approaches to compute the roots of a quadratic
equation through closed form solutions.
An alternative approach is to use an iterative algorithm to estimate
that root of an equation. In this case, we can use a simple bisection
approach, which works quite nicely for finding the root. Of course,
there are floating point issues here too! Read about how to do bisection
in floating point
\url{https://www.shapeoperator.com/2014/02/22/bisecting-floats/}
Your task for this problem is to implement a bisection algorithm to
return all the solutions of \(ax^2 + bx + c = 0\) when \(c \not= 0\).
\begin{verbatim}
""" Return all the solutions to ax^2 + bx + c. It is acceptable to return
NaN instead of a root as well. """
function roots(a::Float64,b::Float64,c::Float64)
end
\end{verbatim}
Compare the accuracy of this procedure to the methods suggested on the
stack exchange page and explain your results. Note that you may need to
look for extremal inputs.
\subsection{Problem 3: Inner-products are backwards
stable.}\label{problem-3-inner-products-are-backwards-stable.}
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
Show that computing an inner-product \(\vx^T \vy\) is backwards
stable.
\item
Show that computing a matrix-vector product \(\vy = \mA \vx\) is
backwards stable.
\end{enumerate}
\subsection{Problem 4: The advantages of
Float64}\label{problem-4-the-advantages-of-float64}
Consider the Candyland problem from HW2 where we worked out the expected
length of a game based on an infinite summation. Repeat this analysis
with Float16 arithmetic and also with BigFloat analysis. (This problem
may require julia to use both Float16 and BigFloat.) Make sure that all
intermediate computations use these types. To declare a vector of
Float16 or BigFloats, use \texttt{Vector\{Float16\}} or
\texttt{Matrix\{BigFloat\}} also helpful are
\texttt{zero(Float16),\ one(Float16)}. If there are questions about
using these types, please post to Piazza. Which answer is more accurate?
\end{document}