Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/Practice Problems and Solutions

Introduction

This is a compilation of problems and solutions from past numerical methods qualifying exams at the University of Maryland.

August 2008

Problem 1

Consider the system $\displaystyle Ax=b$. The GMRES method starts with a point $\displaystyle x_{0}$ and normalizes the residual $\displaystyle r_{0}=b-Ax_{0}$ so that $\textstyle v_{1}={\frac {r_{0}}{\nu }}$ has 2-norm one. It then constructs orthonormal Krylov bases $\scriptstyle V_{k}=(v_{1}\,v_{2}\,\cdots v_{m})$ satisfying

$\displaystyle AV_{k}=V_{k+1}H_{k}$

where $\displaystyle H_{k}$ is a $\textstyle (k+1)\times k$ upper Hessenberg matrix. One then looks for an approximation to $\displaystyle x$ of the form

$\displaystyle x(c)=x_{0}+V_{k}c$

choosing $\displaystyle c_{k}$ so that $\textstyle \|r(c)\|=\|b-Ax(c)\|$ is minimized, where $\textstyle \|\cdot \|$ is the usual Euclidean norm.

Part 1a

Show that $\displaystyle c_{k}$ minimizes $\|\nu e_{1}-H_{k}c\|$.

Solution 1a

We wish to show that

$\displaystyle \|b-Ax(c)\|=\|\nu e_{1}-H_{k}c\|$

${\begin{aligned}\|b-Ax(c)\|&=\|b-A(x_{0}+V_{k}c)\|\\&=\|b-Ax_{0}-AV_{k}c\|\\&=\|r_{0}-AV_{k}c\|\\&=\|r_{0}-V_{k+1}H_{k}c\|\\&=\|\nu v_{1}-V_{k+1}H_{k}c\|\\&=\|V_{k+1}\underbrace {(\nu e_{1}-H_{k}c)} _{h_{c}}\|\\&=(V_{k+1}h_{c},V_{k+1}h_{c})^{\frac {1}{2}}\\&=((V_{k+1}h_{c})^{T}V_{k+1}h_{c})^{\frac {1}{2}}\\&=(h_{c}^{T}V_{k+1}^{T}V_{k+1}h_{c})^{\frac {1}{2}}\\&=(h_{c}^{T}h_{c})^{\frac {1}{2}}\\&=\|h_{c}\|\\&=\|\nu e_{1}-H_{k}c\|\end{aligned}}$