Homework 3, due in class 2016-02-12ΒΆ

Floating point systems (From or adopted from Higham)

  • Consider a number system with base \(\beta=2\), precision \(t=3\) and limits \(e_{\rm min} = -1\) and \(e_{\rm max} = 3\) on the exponent. State all non-negative numbers in this system. Also draw them on the line and discuss the relative and absolute accuracy for the representation of real numbers inside this floating point number system.

  • Show that

    \[\begin{equation} 0.1 = \sum_{i=1}^{\infty} (2^{-4i} + 2^{-4i-1}), \end{equation}\]

    and write down the (repeating) base 2 representation of 0.1.

  • Use Heron’s formula to compute the area for triangles with different angles but with the area 1. How does the accuracy depend on the angles (shape) of the triangle?

Matrix-matrix multiply

  • Implement Strassen’s algorithm in Matlab and record the execution time for matrices of different sizes. Try different levels of recursion depth and try to find break even points in terms of size of the matrices. For simplicity consider square matrices of size \(2^r\). Compute the nuclear norm of the error in the computed matrix (the product). You can use the built in Matlab multiply to get the exact solution.

Backward error analysis

  • In class we performed a backward error analysis of the computation of the inner product of two vectors. In particular we saw that when summing for left to right we had that all the perturbations in the data were bound by \(\gamma_n = \frac{nu}{1-nu}\). The ordering of summation is not important and we may write the backward error result as

    \[\begin{equation} {\rm fl} (x^T y) = (x+\Delta x)^T y = x^T (y+\Delta y), \ \ , |\Delta x | \le \gamma_n |x|, \ \ |\Delta y | \le \gamma_n |y|. \end{equation}\]

    Investigate how the bounds on \(|s_n-\hat{s}_n |\) can be improved by splitting the sum of the terms into \(k\) smaller pieces. What is the optimal choice of \(k\)? What is the corresponding bound?

  • Discuss how the above bound can be further improved by using pairwise summation. Hint see Higham’s paper.

  • For an outer product \(A = xy^T, x,y \in \mathbb{R}^n\) we have that \(\hat{a}_{ij} = x_i y_j (1+\delta_{ij}),|\delta_{ij}| \le u\) so that \(\hat{A}=xy^T + \Delta, \ \ |\Delta| \le u |xy^T|\). Computing an outer product is thus forward stable. Is it backward stable? Why? Why not?

  • Let \(x = a+ib\) and \(y=c+id\) be complex numbers and consider the division

    \[\begin{equation} x/y = \frac{ac+bd}{c^2+d^2} + i \frac{bc-ad}{c^2+d^2}. \end{equation}\]

    Find a bound on \(\delta\) so that \({\rm fl}(x/y)= (x/y)(1+\delta)\) holds.