Low-Rank Approximation

Consider integral \[ I(s)=\int _C \frac {e^{s z^2}}{z^2-1}\,dz, \] \(C\) is the vertical line \(\operatorname {Re}z=2\), from \(z=2-i\infty \) to \(z=2+i\infty \), with large positive parameter \(s\). Find the three-term asymptotic expansion (approximation with three non-zero terms) of this integral as \(s\to +\infty \).

Consider integral \[ I(s)=\int _C \frac {e^{s z^2}}{z^2-1}\,dz, \] \(C\) is the vertical line \(\operatorname {Re} z=3\), from \(z=3-i\infty \) to \(z=3+i\infty \), with large (real) parameter \(s\). Find the three-term asymtotic expansion (approximation with three non-zero terms) of this integral as \(s\to +\infty \).

Consider the (square) linear system \(Ax=b\). Suppose you have obtained a numerical approximation \(\hat {x}\). Define the error and residual, respectively, by \[ e=x-\hat {x}\qquad \text {and}\qquad r=b-A\hat {x}. \] Let \(\|\cdot \|\) denote a vector norm, and the induced matrix norm. Show that \[ \frac {1}{\|A\|\|A^{-1}\|}\frac {\|r\|}{\|b\|} \leq \frac {\|e\|}{\|x\|} \leq \|A\|\|A^{-1}\|\frac {\|r\|}{\|b\|} \] and discuss the significance of these inequalities.

Linear Multistep Methods Consider the initial value problem \[ y'=f(x,y),\qquad y(a)=y_0 \] Let \(h\) be some stepsize, \(x_n=a+nh\), \(y_n\approx y(x_n)\), and \(f_n=f(x_n,y_n)\), for \(n=0,1,2,3,\ldots \). Let \(k\) be some step number, and ignore the question of obtaining starting values \(y_1,y_2,\ldots ,y_{k-1}\). Suppose the approximations \(y_n\), \(n=k,k+1,\ldots \) are obtained by the Linear Multistep Method \[ \sum _{j=0}^k \alpha _j y_{n+j} =h\sum _{j=0}^k \beta _j f_{n+j}. \tag {4} \] Define what is meant by the local truncation error and the order of the linear multistep method (4). Compute the order and the local truncation error of Euler’s Method \[ y_{n+1}-y_n=hf_n. \tag {5} \]

1. Find the first term of the asymptotic representation of \[ n!=\int _0^\infty \exp (-t)t^{a-1}\,dt \] for large \(n\). (This approximation is called Stirling’s formula.)
2. What is the order of the error term and how can this be rigorously justified? (Invoke the appropriate theorem.)

The Jacobi Method Let \(A\) be a strictly diagonally dominant \(n\times n\) matrix, i.e., \[ \lvert a_{ii}\rvert >\sum _{j\ne i}\lvert a_{ij}\rvert , \qquad i=1,\ldots ,n. \tag {2} \] Describe the Jacobi method applied to the linear system \[ Ax=b \tag {3} \] and prove that it converges for all initial approximations of the solution.

a) Show that the best uniform (\(L^\infty [-1,1]\)) approximation of an even polynomial \(p_n(x)\) of (even) degree \(n\) by polynomials of degree \(\le n-2\) on \([-1,1]\), is given by \(p_n(x)-c_nT_n(x)\), where \(T_n\) is the Tchebyshev polynomial of degree \(n\), and \(c_n\) is an appropriately chosen constant. Hint: First find the best approximation by polynomials of degree \(\le n-1\).

b) What are the zeroes of \(T_n\) and what are their significance in interpolation. In particular, estimate the error of interpolation at Tchebyshev nodes.

a) Find the order/rate of convergence of Newton’s method to a multiple root \(r\) of multiplicity \(m>1\) of the scalar equation \(f(x)=0\).

b) What method is obtained by applying Aitken’s acceleration in this situation? Show that it is at least quadratically convergent.

c) How would you extrapolate an integration formula whose error behaved asymptotically as \[ I-I_n=c_3h^3+c_6h^6+\cdots \] where \(I\equiv \int _a^b f(x)\,dx\) is the exact value, \(I_n\) is the approximation with \(n\) subintervals, and \(h\equiv \frac {b-a}{n}\).