Review-01-Scientific-Computing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review-01-Scientific-Computing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Answers to review questions from Chapter 1: Scientific Computing <cite data-cite=\"heath2018scientific\">(Heath, 2018)</cite>.\n",
    "\n",
    "---\n",
    "Questions marked with $\\bigtriangledown$ are considered more difficult."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">1.1. True or false: A problem is ill-conditioned if its solution is highly sensitive to small changes in the problem data.\n",
    "\n",
    "True.  A problem is ill-conditioned if the relative change in a solution is larger than the change in the input data. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.2. True or false: Using higher-precision arith- metic will make an ill-conditioned problem better conditioned.\n",
    "\n",
    "False. The condition number is the ratio of the relative forward error to the relative backward error and neither of these can be strictly reduced by increasing precision.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.3. True or false: The conditioning of a prob- lem depends on the algorithm used to solve it.\n",
    "\n",
    "False.  Conditioning refers to data.  Stability refers to algorithms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.4. True or false: A good algorithm will pro- duce an accurate solution regardless of the condi- tion of the problem being solved.\n",
    "\n",
    "False. A problem which is ill-conditioned **cannot** be solved accurately."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.5. True or false: The choice of algorithm for solving a problem has no effect on the propagated data error.\n",
    "\n",
    "True.  The propagated data error = $f(\\hat{x}) - f(x)$ and compares the result of the true function using approximate and true input, hence ignoring the choice of algorithm. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.6. True or false: A stable algorithm applied to a well-conditioned problem necessarily produces an accurate solution.\n",
    "\n",
    "True.  An accurate solution is by definition the result of stable algorithm and well-conditioned problem. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.7. True or false: If two real numbers are exactly representable as floating-point numbers, then the result of a real arithmetic operation on them will also be representable as a floating-point number.\n",
    "\n",
    "False.  There is no such guarantee."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.8. True or false: Floating-point numbers are distributed uniformly throughout their range.\n",
    "\n",
    "False.  Floating point numbers are **not** distributed uniformly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.9. True or false: Floating-point addition is as- sociative but not commutative.\n",
    "\n",
    "False.  Floating point addition is commutative, but **not** associative eg $(1 + \\epsilon) + \\epsilon \\neq 1 + (\\epsilon + \\epsilon)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.10. True or false: In a floating-point number system, the underflow level is the smallest positive number that perturbs the number 1 when added to it.\n",
    "\n",
    "False.  The machine epsilon $\\epsilon$ is the smallest number such that $1 + \\epsilon > 1$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.11. True or false: The mantissa in IEEE dou- ble precision floating-point arithmetic is exactly twice the length of the mantissa in IEEE single precision.\n",
    "\n",
    "False.  The mantissa in IEEE single precision is 24 bits and in IEEE double precision is 53 bits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.12. What three properties characterize a well- posed problem?\n",
    "\n",
    "1. solution exists\n",
    "2. solution is unique\n",
    "3. solution depends continuously on input (eg no discontinuities)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.13. List three sources of error in scientific com- putation.\n",
    "\n",
    "1. computational error\n",
    "  * truncation error\n",
    "  * rounding error \n",
    "2. data error\n",
    "  * approximations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.14. Explain the distinction between truncation (or discretization) and rounding\n",
    "\n",
    "Truncation is caused by use of mathematical approximations such as use of truncating series or discrete approximations.\n",
    "\n",
    "Rounding is caused by the inexact representation of real numbers and arithmetic in the floating point representation used by a computer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.15. Explain the distinction between absolute error and relative error.\n",
    "\n",
    "absolute error = approximate value - true value\n",
    "\n",
    "relative error = absolute error / true value\n",
    "\n",
    "The **relative error** is required in order to interpret the magnitude of an error in context of the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.16. Explain the distinction between computa- tional error and propagated data error.\n",
    "\n",
    "computational error = $\\hat{f}(\\hat{x}) - f(\\hat{x})$\n",
    "\n",
    "propagated data error = $f(\\hat{x}) - f(x)$\n",
    "\n",
    "The computational error describes the difference between the approximating function and true function.\n",
    "\n",
    "The propagated data error describes the difference between the approximate input and true input."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "\n",
    "> 1.17. Explain the distinction between precision and accuracy.\n",
    "\n",
    "Precision refers to how close two numbers are to each other.\n",
    "\n",
    "Accuracy refers to how close a computed solution is to the true solution.\n",
    "\n",
    "> 1.18. (a) What is meant by the conditioning of a problem?\n",
    "(b) Is it affected by the algorithm used to solve the problem?\n",
    "(c) Is it affected by the precision of the arithmetic used to solve the problem?\n",
    "\n",
    "(a) Conditioning refers to data and is the ratio of the relative forward error to the relative backward error.  Values of this ratio which are much larger than 1 indicate an ill-conditioned problem.\n",
    "\n",
    "(b) Conditioning refers to data, **not** algorithms.\n",
    "\n",
    "(c) Yes. The relative forward error consists in part of computational error which has as a component rounding error.\n",
    "\n",
    "> 1.19. If a computational problem has a condition number of 1, is this good or bad? Why?\n",
    "\n",
    "Good. If $\\text{cond} \\gg 1$ (eg much larger), then we say a problem is ill-conditioned.\n",
    "\n",
    "> 1.20. Explain the distinction between relative condition number and absolute condition number.\n",
    "\n",
    "Since relative condition number has input or output in denominator, it will be undefined when either is 0.  In such cases, use absolute condition number which is defined as the ratio of the absolute change in solution with change in input.  The absolute condition number is useful in some kinds of problems such as root finding where the solution is expected to be 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.21. What is an inverse problem? How are the conditioning of a problem and its inverse related?\n",
    "\n",
    "The condition number of inverse of f is reciprocal of condition number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.22. (a) What is meant by the backward error in a computed result?\n",
    "(b) When is an approximate solution to a given problem considered to be good according to back- ward error analysis?\n",
    "\n",
    "(a) Backward error = approximate input - true input\n",
    "\n",
    "(b) An approximate solution is good when it is an exact solution to a problem having a small backward error (referred to as \"nearby\")."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.23. Suppose you are solving a given problem using a given algorithm. For each of the follow- ing, state whether it is affected by the stability of the algorithm, and why.\n",
    "(a ) Propagated data error\n",
    "(b) Accuracy of computed result (c) Conditioning of problem\n",
    "\n",
    "(a) Propagated data error relates the result obtained from the true function using approximate and true input and is **not** related to stability.\n",
    "\n",
    "(b) Stability is concerned with the computational error which can affect the accuracy of the computed result, either through the introduction of truncation or rounding error.\n",
    "\n",
    "(c) Conditioning and stability are orthogonal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.24. (a) Explain the distinction between for- ward error and backward error.\n",
    "(b) How are forward error and backward error re- lated to each other quantitatively?\n",
    "\n",
    "(a) Forward error is the difference between the computed result and true result.   Backward error is the difference between the approximate input and the true input.\n",
    "\n",
    "(b) The condition number is the ratio of the relative forward error to the relative backward error. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.25. For a given floating-point number system, describe in words the distribution of machine num- bers along the real line.\n",
    "\n",
    "Floating point numbers are finite and discrete.\n",
    "\n",
    "This is in contrast to real numbers which are infinite and continuous."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.26. In floating-point arithmetic, which is gen- erally more harmful, underflow or overflow? Why?\n",
    "\n",
    "Overflow is generally more harmful since there is no way to approximate a quantity with an arbitrarily large magnitude.\n",
    "\n",
    "In contrast, 0 is often a good approximation for underflow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.27. In floating-point arithmetic, which of the following operations on two positive floating-point operands can produce an overflow?\n",
    "(a) Addition\n",
    "(b) Subtraction (c) Multiplication (d) Division\n",
    "\n",
    "Multiplication and division can produce overflow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.28. In floating-point arithmetic, which of the following operations on two positive floating-point operands can produce an underflow?\n",
    "(a) Addition\n",
    "(b) Subtraction (c) Multiplication (d) Division\n",
    "\n",
    "Addition and subtraction can produce underflow.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.29. List two reasons why floating-point number systems are usually normalized.\n",
    "\n",
    "* Makes each bit pattern unique.\n",
    "* Eliminates leading zeros, maximizing available precision."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.30. In a floating-point system, what quantity determines the maximum relative error in repre- senting a given real number by a machine number?\n",
    "\n",
    "The unit roundoff bounds the relative error in representing a number where $|\\frac{fl(x) - x}{x}| \\leq \\epsilon$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.31. (a) Explain the difference between the rounding rules “round toward zero” and “round to nearest” in a floating-point system.\n",
    "(b) Which of these two rounding rules is more ac- curate?\n",
    "(c) What quantitative difference does this make in the unit roundoff εmach?\n",
    "\n",
    "(a) round-to-zero chops or truncates digits whereas round-to-nearest finds the closest representable number\n",
    "\n",
    "(b) round-to-nearest is more accurate\n",
    "\n",
    "(c) The unit roundoff using round-to-nearest is 1/2 of unit roundoff using round-to-zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.32. In a p-digit binary floating-point system with rounding to nearest, what is the value of the unit roundoff εmach?\n",
    "\n",
    "$\n",
    "\\epsilon_{\\text{mach}} = \\frac{1}{2} \\beta^{1-p}\n",
    "$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.33. In a floating-point system with gradual un- derflow (subnormal numbers), is the representa- tion of each number still unique? Why?\n",
    "\n",
    "Yes, the representation is unique since a particular bit pattern in the exponent field is used to identify the subnormal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.34. In a floating-point system, is the product of two machine numbers usually exactly repre- sentable in the floating-point system? Why?\n",
    "\n",
    "The product of 2 p-digit mantissas can result in possible loss of digits if $p_i + p_j > \\text{precision}$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.35. In a floating-point system, is the quotient of two nonzero machine numbers always exactly representable in the floating-point system? Why?\n",
    "\n",
    "The quotient of 2 p-digit mantissas can result in loss of digits if $\\frac{p_i}{p_j} >$ precision."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.36. (a) Give an example to show that floating- point addition is not necessarily associative.\n",
    "(b) Give an example to show that floating-point multiplication is not necessarily associative.\n",
    "\n",
    "(a) $(1 + \\epsilon) + \\epsilon \\neq 1 + (\\epsilon + \\epsilon)$\n",
    "\n",
    "(b) $\\frac{1}{2} (\\text{max} + \\text{max}) \\neq \\frac{1}{2} \\text{max} + \\frac{1}{2} \\text{max}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.37. (a) In what circumstances does cancella- tion occur in a floating-point system? (b) Does the occurrence of cancellation imply that the true result of the specific operation causing it is not exactly representable in the floating-point system? Why?\n",
    "(c) Why is cancellation usually bad?\n",
    "\n",
    "(a) Subtracting 2 numbers of similar magnitudes results in the loss of the most significant aka leading digits.\n",
    "\n",
    "(b) If the numbers have the same magnitude, then the subtraction results in fewer significant digits and is exactly representable.\n",
    "\n",
    "(c) Cancellation is bad because the most significant digits are lost.  Compare this to rounding in which the least significant digits are lost."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.38. Give an example of a number whose deci- mal representation is finite (i.e., it has only a finite number of nonzero digits) but whose binary rep- resentation is not.\n",
    "\n",
    "1/10 is not exactly representable in binary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.39. Give examples of floating-point arithmetic operations that would produce each of the excep- tional values Inf and NaN.\n",
    "\n",
    "Inf: divide a finite number by 0 eg 1/0, 2/0, ....\n",
    "\n",
    "NaN: undefined operation or operation involving Inf eg 0/0, 0 * Inf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}