# 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 $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}}