Consider the system $Ax=b\,\!$. The GMRES method starts with a point $\,\!x_{0}$ and normalizes the residual $\,\!r_{0}=b-Ax_{0}$ so that $\,\!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
$\,\!AV_{k}=V_{k+1}H_{k}$
where $\,\!H_{k}$ is a $\,\!(k+1)\times k$ upper Hessenberg matrix. One then looks for an approximation to $\displaystyle x$ of the form
$\,\!x(c)=x_{0}+V_{k}c$
choosing $\,\!c_{k}$ so that $\,\!\|r(c)\|=\|b-Ax(c)\|$ is minimized, where $\,\!\|\cdot \|$ is the usual Euclidean norm.
Suppose we choose to solve the least squares problem in part a for $c_{k}\!\,$ by the method of orthogonal triangularization (QR). What is the order of the floating point operation for this method. Give reasons.
We need $k\!\,$ Given's Rotation multiplies to zero out each of the $k\!\,$ subdiagonal entries and hence transform $H_{k}\!\,$ into upper triangular form $R\!\,$,
Each successive Given's Rotations multiply on an upper Hessenberg matrix requires four fewer multiplies because each previous subdiagonal entry has been zeroed out by a Given's Rotation multiply.
Hence the cost of $k\!\,$ Given's Rotations multiplies is
State the composite trapezoidal rule $Q_{T,n}\!\,$ for approximating $I(f)\!\,$ on a uniform partitioning of width $h={\frac {b-a}{n}}\!\,$, and give a formula for the error $I(f)-Q_{T,n}\!\,$ that is in a form suitable for extrapolation.
The error in polynomial interpolation can be found by using the following theorem:
Assume $f^{n+1}\!\,$ exists on $[a,b]\!\,$ and $\{x_{0},x_{1},\ldots ,x_{n}|x\in [a,b]\}.\!\,$$P_{n}\!\,$ interpolates $f\!\,$ at $\{x_{j}\}_{j=0}^{n}\!\,$.
Then there is a $\xi _{x}\!\,$ ($\xi \!\,$ is dependent on $x\!\,$) such that
$f(x)-p_{n}(x)={\frac {(x-x_{0})(x-x_{1})...(x-x_{n})}{(n+1)!}}f^{(n+1)}(\xi _{x})\!\,$
where $\xi _{x}\!\,$ lies in $(m,M)\!\,$, $m=\min\{x_{0},x_{1},\ldots ,x_{n},X\}\!\,$, $M=\max\{x_{0},x_{1},\ldots ,x_{n},X\}\!\,$
Since $a\!\,$ is the start of the interval, $x-a\!\,$ is always positive. Conversely, since $b\!\,$ is the end of the interval, $x-b\!\,$ is always negative. Hence, $w(x)<0\!\,$ is always of one sign. Hence from the mean value theorem of integration, there exists a $\zeta \in [a,b]\!\,$ such that
Use the error formula to derive a new quadrature rule obtained by performing one step of extrapolation on the composite trapezoidal rule. What is this rule, and how does its error depend on $h\!\,$? You may assume here that $f\!\,$ is as smooth as you need it to be.
With $2n\!\,$ points, there are twice as many intervals, but the intervals are half as wide. Hence, the error for the composite trapezoidal rule at $2n\!\,$ points in $[a,b]\!\,$ is
We can eliminate the $h^{2}\!\,$ term by choosing using an appropriate linear combination of $E_{n}\!\,$ and $E_{2n}\!\,$. This gives a new error rule with $h^{3}\!\,$error.
specify the orthogonal matrix $Q_{k}\!\,$ used to perform this step when Givens rotations are used. The matrix should be described in terms of the entries of the shifted matrix.
$Q_{k}^{T}\!\,$ is an orthogonal 2x2 Given's rotations matrix. $Q_{k}^{T}\!\,$'s entries are chosen such that when $Q_{k}^{T}\!\,$ is pre-multiplied against the 2x2 matrix ${\tilde {A}}_{k}\!\,$, $Q_{k}^{T}\!\,$ will zero out the (2,1) entry of ${\tilde {A}}_{k}\!\,$ and scale ${\tilde {A}}_{k}\!\,$'s remaining three entries i.e.
where $*\!\,$ denotes calculable scalar values we are not interested in and $R_{k}\!\,$ is our desired upper triangular matrix sought by the QR algorithm.
Since $Q_{k}^{T}\!\,$ is orthogonal, the above equation implies
Suppose $a_{21}=\delta \!\,$, a small number, and $|a_{12}|\leq (a_{11}-a_{22})^{2}\!\,$. Demonstrate that with an appropriate shift $\sigma _{k}\!\,$, the (2,1)-entry of $A_{k+1}\!\,$ is of magnitude $O(\delta ^{2})\!\,$. What does this suggest about the convergence rate of the QR iteration?
Let $A_{k+1}(2,1)\!\,$ be the (2,1) entry of $A_{k}\!\,$. Using the above equation, we can find $A_{k+1}(2,1)\!\,$ by finding the inner product of the second row of $R_{k}\!\,$ and first column $Q_{k}\!\,$ and adding the (2,1) entry of $\sigma _{k}I\!\,$ i.e.