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

Problem 3

Let $A,B\in R^{n\times n}$ be symmetric and positive definite matrices, and let $b\in R^n$. Consider the quadratic function $Q(x)=\frac{1}{2}{x}^{T}Ax-x^{T}b$ for $x\in R^n$ and a descent method to approximate the solution of $Ax=b$: $x_{k+1}=x_k+{\alpha }_k{d}_k$

Problem 3a

Define the concept of steepest descent $d_k$ and show how to compute the optimal stepsize ${\alpha }_k$

Descent Direction

$\mathrm{\nabla }Q(x_k)\cdot d_k<0$

Optimal step size

Choose ${\alpha }_k$ such that $Q(x_k+{\alpha }_k{d}_k)$ is minimized i.e.

${\alpha }_k:\underset{{\alpha }_k}{\min }Q(x_k+{\alpha }_k{d}_k)$

$Q(x_k+{\alpha }_k{d}_k)=⟨x_k+{\alpha }_k{d}_k,A{x}_k+{\alpha }_{k}A{d}_k⟩-⟨x_k+{\alpha }_k{d}_k,b⟩$

$\frac{d}{d\alpha }Q(x_k+{\alpha }_k{d}_k)=⟨A{d}_k,x_k⟩+{\alpha }_k⟨A{d}_k,d_k⟩-⟨d_k,b⟩$

Setting the above expression equal to zero gives the optimal ${\alpha }_k$:

${\alpha }_k=\frac{⟨d_k,b-A{x}_k⟩}{⟨A{d}_k,d_k⟩}$

Note that since $A$ is symmetric

$⟨d_k,A{x}_k⟩=⟨A{d}_k,x_k⟩$

Problem 3b

Formulate the steepest descent (or gradient method) method and write a pseudocode which implements it.

Solution 3b

Note that $d_k=-\mathrm{\nabla }Q(x_k)=b-A{x}_k=r_k$. Then the minimal ${\alpha }_k$ is given by $\frac{⟨r_k,r_k⟩}{⟨r_k,r_k{⟩}_A}$

Given $x_0\in R^n$

For $k=0,1,2,\dots$
 $\begin{array}{cc}{r}_k& =b-A{x}_k\\ & \text{If }{r}_k=0,\text{ then quit }\\ d_k& =r_k\\ {\alpha }_k& =\frac{⟨r_k,r_k⟩}{⟨r_k,r_k{⟩}_A}\\ x_{k+1}& =x_k+{\alpha }_k{d}_k\end{array}$

Problem 3c

Let $B^{-1}$ be a preconditioner of $A$. Show how to modify the steepest descent method to work for $B^{-1}Ax=B^{-1}b$ and write a pseudocode. Note that $B^{-1}A$ may not be symmetric. (Hint: proceed as with the conjugate gradient method).

Solution 3

Since $B$ is symmetric, positive definite, $B=E^{T}E$ where $E$ is upper triangular (Cholesky Factorization).

Then $B^{-1}=E^{-1}{E}^{-T}$

Hence,

$\begin{array}{cc}{B}^{-1}Ax& =B^{-1}b\\ E^{-1}{E}^{-T}Ax& =E^{-1}{E}^{-T}b\\ E^{-T}Ax& =E^{-T}b\\ \underset{\tilde{A}}{\underbrace{E^{-T}A{E}^{-1}}}\underset{\tilde{x}}{\underbrace{Ex}}& =\underset{\tilde{b}}{\underbrace{E^{-T}b}}\end{array}$

$\tilde{A}$ is symmetric:

$(E^{-T}A{E}^{-1}{)}^T=E^{-T}A{E}^{-1}$ since $A$ symmetric

$\tilde{A}$ is positive definite:

$x^T{E}^{-T}A{E}^{-1}x=(E^{-1}x{)}^{T}A(E^{-1}x)>0$ since $A$ positive definite

Pseudocode

Given $x_0\in R^n$

For $k=0,1,2,\dots$
 $\begin{array}{cc}\widetilde{x_k}& =E{x}_k\\ r_k& =\tilde{b}-\tilde{A}\widetilde{x_k}\\ & \text{If }{r}_k=0,\text{ then quit }\\ d_k& =r_k\\ {\alpha }_k& =\frac{⟨r_k,r_k⟩}{⟨r_k,r_k{⟩}_{\tilde{A}}}\\ x_{k+1}& =x_k+{\alpha }_k{d}_k\end{array}$