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

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

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

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

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

Part 1a

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

Solution 1a

We wish to show that

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

{\displaystyle {\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}}}