Homework 5

Due: Tues 4/17

---

1. Recall that for an $n\times m$ matrix $\mathbf{A}$ where $n > m$ the system $\mathbf{A}\mathbf{x} = \mathbf{b}$ is over determined for any $\mathbf{b}$ in $\mathbb{R}^n$. Instead, we look for the least squares solution, which satisfies the normal equations \[ \mathbf{A}^\top\mathbf{A}\mathbf{x} = \mathbf{A}^\top\mathbf{b} \] and has a unique solution if $\mathbf{A}$ has linearly independent columns. However, the matrix $\mathbf{A}^\top\mathbf{A}$ is often badly conditioned and therefore solving the normal equations is typically unstable. An alternative approach is to use the $QR$ factorization $\mathbf{A} = \mathbf{Q}\mathbf{R}$, where $\mathbf{Q}$ is an $n\times n$ orthogonal matrix and $\mathbf{R}$ is an $n\times m$ matrix of the form $\mathbf{R} = \begin{bmatrix} \mathbf{R}_m \\ \mathbf{0} \end{bmatrix}$ where $\mathbf{R}_m$ is an $m\times m$ upper triangular matrix. We showed in class that the least squares solution also satisfies the following triangular system \[ \mathbf{R}_m \mathbf{x} = (\mathbf{Q}^\top \mathbf{b})_{1:m} \] which is more stable to solve. The following problems, concern the least squares solution to

   \[ \mathbf{A}\mathbf{x} = \mathbf{b},\quad \mathbf{A} = \begin{bmatrix}1 + 10^{-8} & -1 \\ -1 & 1\\ 1 & -1\end{bmatrix},\quad \mathbf{b} = \begin{bmatrix} 2 \\ 1 \\ -1\end{bmatrix}. \]

   1. Using MATLAB's \ command, find the solution to the normal equations $\mathbf{A}^\top\mathbf{A}\mathbf{x} = \mathbf{A}^\top\mathbf{b}$.

   2. Using MATLAB's qr command and it's \ command, find the solution to the triangular system $\mathbf{R}_m \mathbf{x} = (\mathbf{Q}^\top \mathbf{b})_{1:m}$. Compare this to the solution to the normal equations. How far apart are the answers?

   3. Using MATLAB's cond command, what are the condition numbers of $\mathbf{A}$, $\mathbf{A}^\top\!\mathbf{A}$, and $\mathbf{R}_m$?. Which condition number should we worry about in double precisions floating point arithmetic? Which answer computed in part (a) and (b) is more accurate?

2. Using Gram-Schmidt orthogonalization, find the first $n$ orthogonal (not necessarily normal) polynomials, $P_0,P_1, \ldots, P_{n-1}$ associated to the weight function $w(x)$ in the indicated interval

   1. $w(x) = \ln(x)$, on $[0,1]$, $n=2$

   2. $w(x) = x$, on $[0,1]$, $n= 3$

   3. $w(x) = \sqrt{1-x^2}$, on $[-1,1]$, $n=2$

   4. $w(x) = 1$, on $[-1,3]$, $n=3$

3. Verify that the following two formulas actually approximate the third derivative. Find their error terms. Which formula is more accurate?

   \[ f^{\prime\prime\prime}(x) \approx \frac{1}{h^3}\left(f(x+3h) - 3f(x+2h) + 3f(x+h) - f(x)\right), \] \[ f^{\prime\prime\prime}(x) \approx \frac{1}{2h^3}\left(f(x+2h) - 2f(x+h) + 2f(x-h) - f(x-2h)\right). \]

4. Establish the most accurate formula of the form

   \[ f^{\prime\prime}(x) \approx \frac{1}{h^2}\left(Af(x+ 3h) + Bf(x+2h) + C f(x+h) + Df(x)\right). \]

   What is the order?

5. Let $L$ be an exact quantity that is approximated by $D(h)$ such that

   \[ L = D(h) + a_1h + a_3h^3 + a_4 h^4 + \ldots \]

   Use Richardson’s extrapolation to obtain a third-order approximation of $L$. Use again Richardson’s extrapolation to obtain a fourth-order approximation of $L$.