Linear Programming and Optimization

Least Squares Problems. Let \(A \in \mathbb {R}^{m \times n}\) with \(m > n\) have rank \(n\) and \(b \in \mathbb {R}^m\). The Least Squares problem is to find \(x \in \mathbb {R}^n\) which makes \(\|Ax - b\|_2\) as small as possible.

1. Show that \(x\) solves this Least Squares problem if and only if \(A^T Ax = A^T b\).
2. What is meant by the QR factorization of matrix \(A\)?
3. Show how to use the QR factorization of \(A\) to solve the Least Squares problem.

Sensitivity. For nonsingular \(A \in \mathbb {R}^{n \times n}\), and nonzero \(b \in \mathbb {R}^n\), consider the problems

1. Show that \[ \frac {\|x-\hat {x}\|}{\|x\|} \le \|A\|\|A^{-1}\|\frac {\|A-\hat {A}\|}{\|A\|}. \]
2. Give a bound on \(\|A-\hat {A}\|_2\) which ensures that \(\hat {A}\) is nonsingular if \(A\) is nonsingular.

Singular Value Decomposition. Let \(A \in \mathbb {R}^{m \times n}\), with \(m \ge n\).

1. What is the singular value decomposition (SVD) of \(A\)? Does every such matrix \(A\) have an SVD? Prove that it does or show an example of a matrix \(A\) which does not have an SVD.
2. For any \(m \times n\) matrix \(A\) with an SVD and \(\epsilon > 0\), show that there is a full-rank matrix \(B\) for which \(\|A - B\|_2 < \epsilon \).
3. For \(m \times n\) matrix \(A\), give orthonormal bases for the subspaces \(\operatorname {range}(A)\), \(\operatorname {null}(A)\), \(\operatorname {range}(A^*)\), and \(\operatorname {null}(A^*)\).

Solution of a nonlinear fixed point problem

Consider the fixed-point problem \(x = g(x)\) for a continuously differentiable real-valued function \(g\) and assume that it has a solution \(\alpha \) for which \(|g'(\alpha )| < 1\). State and prove a convergence theorem for fixed point iteration \(x^{(k+1)} = g(x^{(k)})\) for this problem. Note: Do not assume more about the function \(g\) than is stated in the problem.

(Matrix Norms). Show that \[ \|A\|_1 = \max _{j=1,\ldots ,n}\sum _{i=1}^n |a_{ij}|. \]

(QR and Cholesky Factorizations). Let \(A\) be a nonsingular square matrix and let \(A = QR\) and \(A^*A = U^*U\) be the QR factorization of \(A\) and the Cholesky factorization of \(A^*A\), respectively. Assume that the usual normalizations \(r_{jj}, u_{jj} > 0\) are in effect. Is it true or false that \(R = U\)? Justify your answer with mathematical details.

(Properties via SVD).

1. Consider \(A \in \mathbb {C}^{m \times n}\). Define what we mean by the singular value decomposition of \(A\).
2. Show that the rank of \(A\) is \(r\), the number of nonzero singular values.
3. Show that the largest singular value of \(A\), call it here \(\sigma _{\max }(A)\), satisfies the relation (with \(x\) and \(y\) are being nonzero vectors below), \[ \sigma _{\max }(A) = \max _{y \in \mathbb {C}^m,\ x \in \mathbb {C}^n} \frac {|y^*Ax|}{\|x\|_2\|y\|_2}. \]

(Hadamard’s Inequality). Prove algebraically: Let \(A \in \mathbb {C}^{m \times m}\) and let \(\mathbf {a}_j\) denote the \(j^{\text {th}}\) column of \(A\). Then, show that, \[ |\det (A)| \le \prod _{j=1}^m \|\mathbf {a}_j\|_2. \]

(Matrix Norms). Show that \[ \|A\|_1 = \max _{j=1,\ldots ,n}\sum _{i=1}^n |a_{ij}|. \]

(Properties via SVD). Suppose \(A \in \mathbb {C}^{m \times n}\) has an SVD, \(A = U\Sigma V^*\), where \(u_j\) are the left singular vectors, \(U = \{u_j\}\), \(v_j\) are the right singular vectors, \(V = \{v_j\}\), and \(\sigma _j\) are the singular values. Assume rank of the matrix \(A\) is \(r\). For any \(\nu \) with \(0 \le \nu \le r\), define \[ A_\nu = \sum _{j=1}^{\nu }\sigma _j u_j v_j^*, \] (if \(\nu = p = \min \{m,n\}\), define \(\sigma _{\nu +1} = 0\)). Show that, \[ \|A - A_\nu \|_2 = \inf _{\substack {B \in \mathbb {C}^{m \times n}\\ \operatorname {rank}(B) \le \nu }} \|A - B\|_2 = \sigma _{\nu +1}. \]

(Eigenvalues and Eigenvectors).

1. State the Rayleigh Quotient Iteration Algorithm to find eigenvalues/eigenvectors for general real symmetric matrix \(A \in \mathbb {R}^{m \times m}\).
2. Prove that the spectrum (the set of all eigenvalues) of any matrix \(A \in \mathbb {C}^{m \times m}\) is contained in the union of the following \(m\) disks, \(D_i\), in the complex plane: \[ D_i = \left \{z \in \mathbb {C} : |z - a_{ii}| \le \sum _{\substack {j=1\\ j\ne i}}^m |a_{ij}|\right \},\qquad 1 \le i \le m. \]

(Properties of the SPD Matrices) Let \(A \in \mathbb {R}^{n \times n}\) be a symmetric positive definite matrix (spd). Show that there exists a unique upper triangular matrix \(H \in \mathbb {R}^{n \times n}\) with positive diagonal entries such that, \(A = H^T H\).

(QR and Cholesky Factorizations). Let \(A\) be a nonsingular square matrix and let \(A = QR\) and \(A^*A = U^*U\) be the QR factorization of \(A\) and the Cholesky factorization of \(A^*A\), respectively. Assume that the usual normalizations \(r_{jj}, u_{jj} > 0\) are in effect. Is it true or false that \(R = U\)? Justify your answer with mathematical details.

(Properties via SVD). Suppose \(A \in \mathbb {C}^{m \times m}\) has an SVD, \(A = U\Sigma V^*\). Find an eigenvalue decomposition of the \(2m \times 2m\) hermitian matrix (using information about SVD for \(A\)), \[ \begin {bmatrix} 0 & A^* \\ A & 0 \end {bmatrix}. \]

(Properties of Projectors). Prove that a projector \(P\) is orthogonal if and only if \(P = P^*\).

(Properties of Gaussian Elimination). Show that for Gaussian elimination with partial pivoting applied to any matrix \(B \in \mathbb {C}^{n \times n}\), the growth factor \(\rho \) satisfies \(\rho \le 2^{n-1}\). Recall that the growth factor is defined as, \[ \rho = \frac {\max _{i,j}|u_{ij}|}{\max _{i,j}|b_{ij}|}, \] where \(u_{i,j}\) are the entries of the upper triangular matrix that results from performing Gaussian elimination on \(B\).

Least Squares Problems. Let \(A \in \mathbb {R}^{m \times n}\) with \(m > n\) have rank \(n\) and \(b \in \mathbb {R}^m\). The Least Squares problem is to find \(x \in \mathbb {R}^n\) which makes \(\|Ax - b\|_2\) as small as possible.

1. Show that \(x\) solves this Least Squares problem if and only if \(A^T Ax = A^T b\).
2. What is meant by the QR factorization of matrix \(A\)?
3. Show how to use the QR factorization of \(A\) to solve the Least Squares problem.

Sensitivity. For nonsingular \(A \in \mathbb {R}^{n \times n}\), and nonzero \(b \in \mathbb {R}^n\), consider the problems

1. Show that \[ \frac {\|x-\hat {x}\|}{\|x\|} \le \|A\|\|A^{-1}\|\frac {\|A-\hat {A}\|}{\|A\|}. \]
2. Give a bound on \(\|A-\hat {A}\|_2\) which ensures that \(\hat {A}\) is nonsingular if \(A\) is nonsingular.

Singular Value Decomposition. Let \(A \in \mathbb {R}^{m \times n}\), with \(m \ge n\).

1. What is the singular value decomposition (SVD) of \(A\)? Does every such matrix \(A\) have an SVD? Prove that it does or show an example of a matrix \(A\) which does not have an SVD.
2. For any \(m \times n\) matrix \(A\) with an SVD and \(\epsilon > 0\), show that there is a full-rank matrix \(B\) for which \(\|A - B\|_2 < \epsilon \).
3. For \(m \times n\) matrix \(A\), give orthonormal bases for the subspaces \(\operatorname {range}(A)\), \(\operatorname {null}(A)\), \(\operatorname {range}(A^*)\), and \(\operatorname {null}(A^*)\).

Solution of a nonlinear fixed point problem

Consider the fixed-point problem \(x = g(x)\) for a continuously differentiable real-valued function \(g\) and assume that it has a solution \(\alpha \) for which \(|g'(\alpha )| < 1\). State and prove a convergence theorem for fixed point iteration \(x^{(k+1)} = g(x^{(k)})\) for this problem. Note: Do not assume more about the function \(g\) than is stated in the problem.

(Rank-One Perturbation of the Identity). If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B = I + uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1} = I + \beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

(Properties via SVD).

1. Consider \(A \in \mathbb {C}^{m \times n}\). Define what we mean by the singular value decomposition of \(A\).
2. Prove that any matrix in \(\mathbb {C}^{m \times n}\) is the limit of a sequence of matrices of full rank. Use the 2-norm for your proof.

(Hadamard’s Inequality). Prove algebraically: Let \(A \in \mathbb {C}^{m \times m}\) and let \(\mathbf {a}_j\) denote the \(j^{\text {th}}\) column of \(A\). Then, show that, \[ |\det (A)| \le \prod _{j=1}^m \|\mathbf {a}_j\|_2. \]

(Iterative Solvers).

1. State Gauss-Seidel method for the solution of the linear system \(Ax = b\), where \(A \in \mathbb {R}^{m \times m}\).
2. Show that if \(A\) is a strictly diagonally dominant matrix by rows, the Gauss-Seidel method is convergent for any \(x^{(0)}\).

(Rank-One Perturbation of the Identity). If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B = I + uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1} = I + \beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

(Properties via SVD).

1. Consider \(A \in \mathbb {C}^{m \times n}\). Define what we mean by the singular value decomposition of \(A\).
2. Show that the rank of \(A\) is \(r\), the number of nonzero singular values.
3. Show that the largest singular value of \(A\), call it here \(\sigma _{\max }(A)\), satisfies the relation \[ \sigma _{\max }(A) = \max _{y \in \mathbb {C}^m,\ x \in \mathbb {C}^n} \frac {|y^*Ax|}{\|x\|_2\|y\|_2}. \]

(Properties of Projectors). Prove algebraically:

1. Show that if \(P \in \mathbb {C}^{m \times m}\) is a nonzero projector, then \(\|P\|_2 \ge 1\).
2. Show that if \(P\) is an orthogonal projector, then \(I - 2P\) is unitary.

(Hadamard’s Inequality). Prove algebraically: Let \(A \in \mathbb {C}^{m \times m}\) and let \(\mathbf {a}_j\) denote the \(j^{\text {th}}\) column of \(A\). Then, show that, \[ |\det (A)| \le \prod _{j=1}^m \|\mathbf {a}_j\|_2. \]

(Matrix properties) For each of the following statements, either prove that it is true, or show it’s false with a counterexample.

a. For \(A \in \mathbb {C}^{m \times n}\) any matrix, and \(U \in \mathbb {C}^{m \times m}\) any unitary matrix, then \(\|UA\|_2 = \|A\|_2\). b. For \(A \in \mathbb {C}^{n \times n}\) any matrix, if \(\rho (A) = 0\), then \(A = 0\). (Recall that \(\rho (A)\) is the spectral radius of \(A\), i.e., the maximum of the moduli of the eigenvalues of \(A\).)

c. For \(A \in \mathbb {C}^{m \times n}\) any matrix with \(m \ge n\), then the squared singular values of \(A\) equal the eigenvalues of \(A^*A\).

(Finite difference formulas) Given \(h > 0\), compute weights \(\{w_j\}_{j=0}^2\) for the following one-sided finite difference formula for the first derivative \(f'(x)\): \[ f'(x) \approx \sum _{j=0}^2 w_j f(x+jh) = w_0 f(x) + w_1 f(x+h) + w_2 f(x+2h). \]

What is the order of accuracy of your formula?

(Quadrature rules) Compute the weights \(\{A_0, A_1, B_0, B_1\}\) for a 4-point quadrature rule of the form \[ \int _0^1 f(x)\,dx \approx A_0 f(0) + A_1 f(1) + B_0 f'(0) + B_1 f'(1) \]

that is exact when \(f\) is any polynomial of degree 3 or less.

Rank-One Perturbation of the Identity

If \(x\) and \(y\) are \(m\)-vectors, the matrix \(A=I+xy^*\) is known as a rank-one perturbation of the identity. Show that if \(A\) is nonsingular, then its inverse has the form \(A^{-1}=I+\beta xy^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(x\) and \(y\) is \(A\) singular? If it is singular, what is \(\operatorname {null}(A)\)?

Properties via SVD 

Prove that any matrix in \(\mathbb {C}^{m\times n}\) is the limit of a sequence of matrices of full rank. Use the 2-norm for your proof.

Numerical Integration

Determine a formula \[ \int _{-\pi }^{\pi } f(x)\cos (x)\,dx \approx A_0 f\left (-\frac {3}{4}\pi \right ) +A_1 f\left (-\frac {1}{4}\pi \right ) +A_2 f\left (\frac {1}{4}\pi \right ) +A_3 f\left (\frac {3}{4}\pi \right ) \] that is exact when \(f\) is a polynomial of degree 3.

Numerical Algorithm to Find Eigenvalues/Eigenvectors

State the Rayleigh Quotient Iteration Algorithm to find eigenvalues/eigenvectors for general real symmetric matrix \(A\in \mathbb {R}^{m\times m}\).

Interpolation

Let \(x_0,\ldots ,x_n\) be distinct real points, and consider the following interpolation problem. Choose a function \[ F_n(x)=\sum _{j=0}^{n}a_j e^{jx} \] such that \[ F_n(x_i)=y_i,\qquad i=0,1,\ldots ,n \] with the \(\{y_i\}\) given data. Show there is a unique choice of \(a_0,\ldots ,a_n\).

Unstable Multistep Method

Consider the numerical method \[ y_{k+1}=3y_k-2y_{k-1} +\frac {h}{2}\left (f(x_k,y_k)-3f(x_{k-1},y_{k-1})\right ), \qquad k\ge 1 \] Illustrate with an example of a simple initial value problem that the above scheme is unstable.

 Heat Equation and Stability of the Scheme

Consider the implicit in time, Backward Euler method for the solution of the heat equation: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - 4\frac {u_{m+1}^{n+1}-2u_m^{n+1}+u_{m-1}^{n+1}}{h^2} = f_m^{n+1}, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1, \] and investigate the stability of the scheme using the von Neumann analysis.

Consider the sequence of linear operators \((U_n)\) where \(U_n:H\to H\), \(H\) is a Hilbert space and the \(U_n\) are unitary, i.e. \(U_n^*U_n=I\), where \(I\) is the identity operator on \(H\). Show that if \(U_n\to U\) in the operator norm, the limit \(U\) must also be unitary, i.e. \(U^*U=I\).

Let \(X\) be a real Banach space, \(f:X\to \mathbb {R}\) be a bounded linear functional and \(T:X\to X\) a bounded linear operator. In the following \(y\in X\) is fixed and \(\alpha \in \mathbb {R}\).

1. Prove that there exists a constant \(C>0\) such that if \(\lvert \alpha \rvert <C\), then the non-linear equation \[ x+\alpha f(x)Tx=y, \tag {1} \] has a unique solution \(x\) in the ball \(B=\{x\in X\mid \lVert x-y\rVert \le 1\}\).
2. Suggest an iterative procedure for approximating the unique solution \(x\) to equation (1).

Let \(T:X\to X\) be a compact linear operator and \(S:X\to X\) be a bounded linear operator, defined on a Banach space \(X\).

1. Show that \(TS\) is a compact linear operator.
2. Show that \(ST\) is a compact linear operator.

Show that a mapping \(T:X\to Y\) where \(X\) and \(Y\) are metric spaces is continuous if and only if the inverse image of any closed set \(M\subset Y\) is a closed set in \(X\).

Let \(x_+=xH(x)\), where \(x\in \mathbb {R}\) and \(H(x)\) is the Heaviside function so that \(x_+=x\) for \(x>0\) and \(x_+=0\) for \(x\le 0\).

1. Show that differentiating in the sense of distributions we have for any integer \(k\ge 0\) that \[ \partial (x_+^k)= \begin {cases} kx_+^{k-1}, & \text {if } k\ge 1,\\ \delta , & \text {if } k=0. \end {cases} \]
2. Let \(k\ge 1\) be an integer. Use (a) to find a distribution \(E\) such that \(\partial ^kE=\delta \).

Consider the complex function \(f(z)=\ln ((z-1)(z-2))\). Find the branch points. Choose a branch cut and find the corresponding principal branch of the function.

You must justify the choice of angles in the dual polar coordinate representation.

1. Show that the transformation \(w=2z+1/z\) maps the unit circle conformally onto the ellipse \[ \left (\frac {u}{3}\right )^2+v^2=1. \] Here \(w=u+iv\).
2. Find the Möbius transformation that takes the points \(z_1=0\), \(z_2=1\), \(z_3=-i\) into \(w_1=1\), \(w_2=0\), \(w_3=i\).

Evaluate \[ I=2\int _{-\infty }^{\infty }\frac {x\sin x}{x^2+4}\,dx. \] You must indicate the contour of integration and treat integration over each contour.

Find the entire asymptotic expansion of \[ I(x)=\int _x^\infty e^{-t^2}\,dt \qquad \text {as }x\to 0^+. \]

Matrix Factorizations

Let \(A\) be a nonsingular square real matrix and let \(A=QR\) and \(A^TA=H^TH\) be QR and Cholesky factorizations, respectively, with the usual normalizations \(r_{jj},h_{jj}>0\). Is it true or false that \(R=H\)? Justify your answer.

Let \((u_n)\) and \((v_n)\) be two orthonormal sequences in a Hilbert space \(H\). Assume that \[ \sum _{n=1}^{\infty }\lVert u_n-v_n\rVert <1. \] Show that if \((u_n)\) is a total orthonormal sequence, then \((v_n)\) is also a total orthonormal sequence.

Hint: Assume for contradiction that \((v_n)\) is not total.

Let \((e_n)\) be a total orthonormal sequence in a Hilbert space \(H\). Let \((x_n)\subset H\) be a sequence. Prove that the two following statements are equivalent.

1. \(x_n\to x\) weakly.
2. The sequence \((x_n)\) is bounded and for any \(j\ge 1\), \(\langle x_n,e_j\rangle \to \langle x,e_j\rangle \) as \(n\to \infty \).

Hint: Show that if (ii) holds and \(y_N\in \operatorname {span}\{e_1,\ldots ,e_N\}\) then \(\langle x_n,y_N\rangle \to \langle x,y_N\rangle \) as \(n\to \infty \).

Consider the nonlinear integral equation \[ u(x)-\lambda \int _a^b w(x,y)\sin (u(y))\,dy=\phi (x), \] where \(\lambda \in \mathbb {R}\), \(\phi \) is continuous on the interval \([a,b]\) and \(w(x,y)\) is continuous on \([a,b]\times [a,b]\). Find a constant \(C>0\) such that \(\lvert \lambda \rvert <C\) implies that the nonlinear integral equation has a unique solution \(u\).

Hint: You may assume the inequality \(\lvert \sin (x)-\sin (y)\rvert \le \lvert x-y\rvert \), for any \(x,y\in \mathbb {R}\).

Consider the left shift operator \(L:\ell ^2\to \ell ^2\), defined for a sequence \((x_n)\in \ell ^2\) by \[ L(x_1,x_2,x_3,\ldots )=(x_2,x_3,x_4,\ldots ). \]

1. Prove that \(\lVert L\rVert =1\).
2. Explain why if \(\lambda \in \mathbb {C}\) with \(\lvert \lambda \rvert >1\), then \(\lambda \in \rho (L)\), the resolvent set of \(L\).
3. Prove that that if \(\lambda \in \mathbb {C}\) with \(\lvert \lambda \rvert <1\), then \(\lambda \in \sigma _p(L)\), the point spectrum of \(L\).
4. Deduce what is \(\sigma (L)\), the spectrum of \(L\).

Let \(L\) be a partial differential operator of the form: \[ L=\sum _{j=0}^{m-1} c_j\partial ^j, \] where the \(c_j\) are arbitrary constants. Show that \(x^m(L\delta )=0\) as distributions in \(\mathcal {D}'(\mathbb {R})\). Here \(\delta \in \mathcal {D}'(\mathbb {R})\) is the usual “delta function”.

Let \(f(z)\) be an entire function such that there exists a constant \(M\), an \(R>0\) and an integer \(n\ge 1\) with \(\lvert f(z)\rvert \le M\lvert z\rvert ^n\) for \(\lvert z\rvert >R\). Show that \(f(z)\) is a polynomial of degree at most \(n\).

1. Find the Laurent expansion of \[ f(z)=\frac {z}{(z+i)(z-2)} \] for \(1<\lvert z\rvert <2\).
2. Classify the singularities of the function \[ f(z)=\frac {z+1}{z\sin (z)}. \]

Evaluate \[ I=\int _{-\infty }^{\infty }\frac {\cos (2x)}{(x+1)^2+4}\,dx. \] You must clearly show the contour of integration and treat integration over each contour separately.

Find the leading non constant behavior as \(x\to 0^+\) of \[ \int _1^\infty \cos (xt)t^{-1}\,dt. \] You must express the constant term in terms of known quantities and/or constants.

Let \((e_n)\) be an orthonormal sequence of a Hilbert space \(H\). Show that \(e_n\to 0\) weakly.

Let \(T:X\to X\) be a bounded linear operator on a complex Banach space \(X\). Prove that the spectrum \(\sigma (T)\) lies in the complex plane disk: \[ \{\lambda \in \mathbb {C}:\lvert \lambda \rvert \le \lVert T\rVert \}. \]

Let \(T\) be a bounded linear operator on a complex Hilbert space \(H\). Show that the operator \(I+T^*T\) is injective.

Let \(H\) be a Hilbert space. Recall that an operator \(T\in B(H)\) is Hilbert-Schmidt if there exits a complete orthonormal sequence, \((e_n)\in H\) such that \[ \sum _{n=1}^{\infty }\lVert Te_n\rVert ^2<\infty . \] Show that every Hilbert-Schmidt operator is compact.

Consider the distribution \(u\in \mathcal {D}'(\mathbb {R})\) defined by \[ \langle u,\phi \rangle =\int _{-\infty }^{\infty }\lvert x\rvert \phi (x)\,dx, \qquad \phi \in \mathcal {D}(\mathbb {R}). \] Find its derivative, \(\partial u\).

Prove the fundamental theorem of algebra:

Every polynomial of degree \(n(\ge 1)\) has exactly \(n\) zeros (each zero being counted according to its multiplicity).

The following function \(f(x)\) [\(x\) is a real variable] is expanded in a series in powers of \((x+3)\). Find the radius of convergence of the series in each case. \[ \begin {array}{rcl} \text {(a)}\quad f(x)&=&e^{x^2},\\[1.4ex] \text {(b)}\quad f(x)&=&\left (\dfrac {\sin x-3}{\sin x-2}\right )^2,\\[1.8ex] \text {(c)}\quad f(x)&=&\dfrac {\sin (x+1)}{(x+1)(x+3)}. \end {array} \]

Evaluate the integrals \[ \begin {array}{rcll} \text {(a)}&\displaystyle \int _{-\infty }^{\infty }\frac {\sin ax}{x}\,dx &&\text {(\(a\) is a real parameter)},\\[2.2ex] \text {(b)}&\displaystyle \int _0^\infty \frac {x^\alpha }{x+1}\,dx &&\text {(\(\alpha \) is a real parameter, \(-1<\alpha <0\))}. \end {array} \]

1. Consider a 2-dimensional map \((x,y)\to (u,v)\).

   Explain: If the map is given by an analytic function [\(u+iv=f(x+iy)\)] and at some point \(z_0=x_0+iy_0\) the derivative \(f'(z_0)\ne 0\), then this map preserves small shapes in the vicinity of \(z_0\).

2. Does there exist a conformal transformation \(u+iv=f(x+iy)\) that maps triangle \[ \Delta =\{(x,y):0<x<1,\ 0<y<1,\ x+y<1\} \] to circle \[ D=\{(u,v):u^2+v^2<1\}\,? \]

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 \).

Finite difference formulas

Given \(h>0\), compute weights \(v_0\) and \(\{w_j\}_{j=-1}^{1}\) for the following finite difference formula for the third derivative \(f^{(3)}(x)\): \[ f^{(3)}(x)\approx v_0f'(x)+\sum _{j=-1}^{1}w_j f(x+jh) \] \[ =v_0f'(x)+w_{-1}f(x-h)+w_0f(x)+w_1f(x+h). \] What is the order of accuracy of your formula?

Lebesgue’s Lemma

Let \(I\) be a closed, bounded interval on the real line and let \(\|f\|_\infty :=\sup _{x\in I}|f(x)|\). Given \(N\) distinct points \(x_1,\ldots ,x_N\in I\) and a continuous function \(f\), consider the Lagrange form of the degree-\((N-1)\) polynomial interpolant of \(f\): \[ I_N f := \sum _{j=1}^{N}f(x_j)\ell _j(x), \]

where \(\{\ell _j(\cdot )\}_{j=1}^{N}\) are cardinal Lagrange polynomials. Show that \[ \sup _{\|g\|_\infty =1}\|I_N g\|_\infty \le \Lambda := \sum _{j=1}^{N}|\ell _j(x)|, \] and that \[ \|f-I_N f\|_\infty \le (1+\Lambda )\inf _{p\in P_{N-1}}\|f-p\|_\infty , \] where \(P_{N-1}=\operatorname {span}\{1,x,\ldots ,x^{N-1}\}\).

Note: In problems 5–8, the notations \(k=\Delta t\) and \(h=\Delta x\) are used.

Heat Equation Stability

Consider the variable coefficient diffusion equation \[ v_t=(\beta (x)v_x)_x,\qquad 0<x<1,\quad t>0 \] with Dirichlet boundary conditions \[ v(0,t)=0,\qquad v(1,t)=0 \] and initial data \(v(x,0)=f(x)\). Assume that \(\beta (x)\ge \beta _0>0\), and that \(\beta (x)\) is smooth. Let \(\beta _{j+1/2}=\beta (x_{j+1/2})\). A scheme for this problem is: \[ \frac {u_j^{n+1}-u_j^n}{k} = \frac {1}{h^2} \left \{ \beta _{j-1/2}u_{j-1}^{n+1} -(\beta _{j-1/2}+\beta _{j+1/2})u_j^{n+1} +\beta _{j+1/2}u_{j+1}^{n+1} \right \}. \] Analyze the 2-norm stability of this scheme for solving this initial boundary value problem.

DO NOT NEGLECT THE FACT THAT THE PROBLEM HAS VARIABLE COEFFICIENTS AND THAT THERE ARE BOUNDARY CONDITIONS AT 0 AND 1!

Higher Order Methods

Consider the following problem for \(v(x)\) on \([0,1]\): \[ v''(x)=f(x), \tag {2} \] with \(v(0)=v(1)=0\). Let \(N\cdot h=1\) and define \(x_j=j\cdot h\) for \(j=0,1,\ldots ,N\). The finite-difference scheme \[ \Delta _h U_j^h\equiv \frac {1}{h^2}\left (U_{j-1}^h-2U_j^h+U_{j+1}^h\right ) = f_j^h, \] for \(j=1,\ldots ,N-1\) with \(U_0^h=U_N^h=0\) gives values \(U_j^h\) that approximate \(v(x_j)\) with an error of \(O(h^2)\). Here the superscript \(h\) is used to indicate the grid size for the solution. Show how to use this method to find a numerical solution \(W_j\) whose values approximate \(v(x_j)\) with an error of \(O(h^4)\) and a numerical solution \(Y_j\) whose values approximate \(v(x_j)\) with an error of \(O(h^6)\).

Consider the nonlinear integral equation \[ f(x)-\lambda \int _a^b k(x,y;f(y))\,dy=\phi (x) \] where \(\lambda \in \mathbb {R}\), \(\phi \) is continuous on \([a,b]\), \(k\) is continuous on \(C=[a,b]\times [a,b]\times \mathbb {R}\), and \(k\) satisfies a Lipschitz condition of the form \[ \lvert k(x,y;z_1)-k(x,y;z_2)\rvert \le L\lvert z_1-z_2\rvert \] in its ‘functional argument’. Show that the nonlinear integral equation has a unique solution, \(f\), for any \(\lambda \) such that \[ \lvert \lambda \rvert <\frac {1}{L(b-a)}. \]

Let \(T:X\to X\) be a compact linear operator on a normed space \(X\). Show that for every \(\lambda \ne 0\), the null space of \(T_\lambda =T-\lambda I\) is finite dimensional.

Let \(a\in \ell ^2\setminus \{0\}\). Consider the bounded linear operator \(T:\ell ^2\to \ell ^2\) defined by \[ Tu=\langle u,a\rangle a. \]

1. Show that the operator \(T\) is compact and self-adjoint.
2. Use the Fredholm Alternative Theorem to find a simple condition on \(a\) guaranteeing that the equation \[ (T-I)u=v \] has a unique solution \(u\) for all \(v\in \ell ^2\). What is the solution?

Consider the operator \(T:L^2[0,1]\to L^2[0,1]\) defined by \((Tx)(t)=tx(t)\).

1. Show that \(T\) is self-adjoint and satisfies \(\langle x,Tx\rangle \ge 0\) for every \(x\in L^2[0,1]\).
2. Find the spectrum \(\sigma (T)\), point spectrum \(\sigma _p(T)\), continuum spectrum \(\sigma _c(T)\), residual spectrum \(\sigma _r(T)\) and resolvent \(\rho (T)\).

Let \(\delta \in \mathcal {D}'(\mathbb {R})\) denote the ‘delta function’. Find \(u\in \mathcal {D}'(\mathbb {R})\) that solves the following linear partial differential equation: \[ \partial ^2 u=\delta . \] Is the solution unique?

Hint: You can solve this equation by guessing the distribution and then verifying that is solves the equation.

Function \(f(x)\) (see below) is expanded in powers of \(x-x_0\), i.e. in the Taylor or Laurent series with center \(x_0\) (\(x\) is a real variable, \(x_0\) is a real number). Find the radius of convergence of this series. \[ \begin {array}{rcll} \text {(a)}\quad f(x)&=&\dfrac {\sin x^2}{(x-3)^2(x^2+1)},& x_0=3,\\[1.4ex] \text {(b)}\quad f(x)&=&\dfrac {\sin x}{x},& x_0=5,\\[1.4ex] \text {(c)}\quad f(x)&=&\dfrac {\sin x}{\sin x+3},& x_0=8. \end {array} \]

Solve Laplace’s equation \(\phi _{xx}+\phi _{yy}=0\) in the domain \[ D=\{(x,y)\in \mathbb {R}^2:x^2+y^2>1,\ (x+2)^2+y^2<9\} \] with boundary conditions: \(\phi (x,y)=a\) when \(x^2+y^2=1\) and \(\phi (x,y)=b\) when \((x+2)^2+y^2=9\).

Calculate the following integrals (\(a\) and \(b\) are positive parameters) \[ \begin {array}{rcl} \text {(a)}\quad I(a)&=&\displaystyle \int _{-\infty }^{\infty }\frac {\sin ax}{x}\,dx,\\[2.2ex] \text {(b)}\quad I(a,b)&=&\displaystyle \int _{-\infty }^{\infty } \frac {\cos ax-\cos bx}{x^2}\,dx. \end {array} \]

\(F(\omega )\) is the Fourier transform of \(f(x)\) (which is continuous and not identical zero), \(x\) and \(\omega \) are real variables. Explain why it is impossible that both functions \(f(x)\) and \(F(\omega )\) have finite support.

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 \).

Projections

Let \(P\in \mathbb {C}^{N\times N}\) be a projection matrix. Prove that \(\ker (P)\perp \operatorname {range}(P)\) if and only if \(P=P^*\). (I.e., you are being asked to justify the definition of an orthogonal projection matrix.)

Hadamard’s inequality

Let \(A\in \mathbb {C}^{N\times N}\) be comprised of columns \(a_i\in \mathbb {C}^N\), \(i=1,\ldots ,N\). Prove that \[ |\det A|\le \prod _{i=1}^{N}\|a_i\|_2. \] You may use, for example, a QR decomposition/Gram-Schmidt argument.

Quadrature

Consider the quadrature rule \[ \int _{-1}^{1} f(x)\,dx \approx w_{-1}f(-1)+w_0f(0)+w_1f(1)+w_0'f'(0). \] Compute weights \(w_{-1}\), \(w_0\), \(w_1\), and \(w_0'\) such that this quadrature rule is exact for polynomials up to degree 3.

Finite difference formulas

Given \(h>0\), compute weights \(w_j\) for the following 5-point finite difference formula for the third derivative \(f^{(3)}(x)\): \[ f^{(3)}(x)\approx \sum _{j=-2}^{2}w_j f(x+jh) \] \[ = w_{-2}f(x-2h)+w_{-1}f(x-h)+w_0f(x)+w_1f(x+h)+w_2f(x+2h). \] What is the order of accuracy of your formula?

Trapezoid rule

For the ODE \(y'=f(t,y)\), the Trapezoid rule is \[ \frac {y_{n+1}-y_n}{\Delta t} = \frac {1}{2}\left (f(t_n,y_n)+f(t_{n+1},y_{n+1})\right ). \] Compute the region of absolute stability for the Trapezoid rule. Is this method \(A\)-stable?

Unconditionally stable scheme

For the one-dimensional heat equation, \[ u_t=u_{xx}, \] consider the Crank-Nicolson, central difference scheme \[ \frac {u_j^{n+1}-u_j^n}{\Delta t} = \frac {1}{2} \left ( \frac {u_{j+1}^{n+1}-2u_j^{n+1}+u_{j-1}^{n+1}}{h^2} + \frac {u_{j+1}^{n}-2u_j^{n}+u_{j-1}^{n}}{h^2} \right ) \] where \(\Delta t\) and \(h\) are temporal and spatial stepsizes, respectively, and where \(u_j^n\) is the numerical approximation to \(u(x=jh,t=n\Delta t)\), with \(x_0=0\) and the initial time \(t=0\). Use von Neumann stability analysis to show that this scheme is unconditionally stable.

Central scheme

Consider the one-dimensional advection equation, \[ u_t=cu_x, \] where \(c\in \mathbb {R}\) is the wavespeed. Use von Neumann stability analysis to determine the values of \(c\) for which the following the central difference, forward Euler scheme is stable: \[ \frac {u_j^{n+1}-u_j^n}{\Delta t} = c\frac {u_{j+1}^{n}-u_{j-1}^{n}}{2h}. \]

Rank-One Perturbation of the Identity

If \(u\) and \(v\) are \(n\)-vectors, the matrix \(B=I+uv^*\) is known as a rank-one perturbation of the identity. Show that if \(B\) is nonsingular, then its inverse has the form \(B^{-1}=I+\beta uv^*\) for some scalar \(\beta \), and give an expression for \(\beta \). For what \(u\) and \(v\) is \(B\) singular? If it is singular, what is \(\operatorname {null}(B)\)?

Properties via SVD

Prove that any matrix in \(\mathbb {C}^{m\times n}\) is the limit of a sequence of matrices of full rank. Use the 2-norm for your proof.

Unstable Multistep Method

Consider the numerical method \[ y_{p+1}=3y_p-2y_{p-1} +\frac {h}{2}\left (f(x_p,y_p)-3f(x_{p-1},y_{p-1})\right ), \qquad p\ge 1, \]

for the solution of the initial value problem \[ y'=f(x,y),\qquad y(x_0)=y_0. \] Illustrate with an example of a simple initial value problem that the above numerical scheme is unstable.

Heat Equation and Stability of the Scheme

Consider the implicit in time, Backward Euler method for the solution of the heat equation: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - \frac {u_{m+1}^{n+1}-2u_m^{n+1}+u_{m-1}^{n+1}}{h^2} = f_m^{n+1}, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1. \] and investigate the stability of the scheme using the von Neumann analysis.

Let \(H\) be a Hilbert space. Show that an isometric linear operator \(T:H\to H\) satisfies \(T^*T=I\), where \(I\) is the identity operator on \(H\).

Let \((X,d)\) be a complete metric space and \(f\) a contraction on \(X\) with contraction constant \(\alpha <1\). Let \(x_f\) be the unique fixed point of \(f\). Fix \(x_0\in X\) and consider the sequence of points defined by \(x_n=f(x_{n-1})\) for \(n\in \mathbb {N}\).

1. Prove that \[ d(x_n,x_f)\le \frac {\alpha ^n}{1-\alpha }d(x_0,x_1). \] Hint: consider \(d(x_m,x_n)\) for \(m>n\).
2. Let \(S=[1,\infty )\) and \(f:S\to S\) be defined by \(f(x)=\frac {1}{2}(x+2/x)\). Prove that \(f\) is a contraction mapping on \(S\) and compute a contraction constant. Determine all fixed points of \(f\) on \(S\). Using part (a), explain why the sequence \((x_n)\) might be useful.

Let \(X\) be an inner product space with inner product \(\langle \cdot ,\cdot \rangle \). Let \((a_j)\) be a sequence of complex numbers and let \((\psi _j)\) and \((\phi _j)\) be two orthonormal sequences in \(X\). Let \(T:X\to X\) be an operator defined by \[ Tx=\sum _{j=1}^{\infty } a_j\langle \psi _j,x\rangle \phi _j. \] State and prove a (nontrivial) sufficient condition on \((a_j)\) so that \(T\) is a compact operator.

The right-shift operator \(R:\ell ^2\to \ell ^2\) is defined by \(R(\xi _1,\xi _2,\ldots )=(0,\xi _1,\ldots )\) and the left-shift operator \(L:\ell ^2\to \ell ^2\) is defined by \(L(\xi _1,\xi _2,\ldots )=(\xi _2,\xi _3,\ldots )\).

1. Show that \(L\) and \(R\) are adjoint to each other.
2. Show that \(\lVert R\rVert =\lVert L\rVert =1\).
3. Prove that the spectrum of \(L\) is given by \[ \sigma _p(L)=\{\lambda \in \mathbb {C}:\lvert \lambda \rvert <1\},\quad \sigma _c(L)=\{\lambda \in \mathbb {C}:\lvert \lambda \rvert =1\},\quad \sigma _r(L)=\emptyset . \]
4. Prove that the spectrum of \(R\) is given by \[ \sigma _p(R)=\emptyset ,\quad \sigma _c(R)=\{\lambda \in \mathbb {C}:\lvert \lambda \rvert =1\},\quad \sigma _r(R)=\{\lambda \in \mathbb {C}:\lvert \lambda \rvert <1\}. \]

Let \(X\) be a complex Banach space and \(T\in B(X,X)\). Show that the resolvent, \(R_\lambda (T)\), satisfies \(\lVert R_\lambda (T)\rVert \to 0\) as \(\lambda \to \infty \).

1. State and prove Liouville’s theorem.
2. Show that every polynomial of degree \(n\ge 1\) in the complex plane has at least one root.

Find the real-valued function \(\Phi (z)\) that solves Laplace’s equation in the region between the two noncentric circles \(\lvert z\rvert =1\) and \(\lvert z-1\rvert =\frac {5}{2}\) subject to the boundary conditions \(\Phi =0\) on \(\lvert z\rvert =1\) and \(\Phi =1\) on \(\lvert z-1\rvert =\frac {5}{2}\).

Consider the transformation on the extended complex plane \(\overline {\mathbb {C}}\) \[ f(z)=w=z+\frac {1}{z}. \]

1. Find all possible fixed points.
2. Show that the image of the points in the upper half \(z\)-plane that are exterior to the circle \(\lvert z\rvert =1\) corresponds to the entire upper half \(w\)-plane.
3. Find the image of the unit circle.
4. Show that \(f(z)\) is a two-to-one function.

Evaluate the integral \[ \int _0^\infty \frac {\sin (ax)}{x}\,dx \qquad \text {for }a>0. \] You must clearly show the contours of integration and treat integration over each contour separately.

Consider the Dawson’s integral \[ D(x)=e^{-x^2}\int _0^x e^{t^2}\,dt \qquad \text {as }x\to \infty . \]

1. Find the first non-constant term of the asymptotic expansion of \(D(x)\) and show that the relationship is asymptotic.
2. Find the full asymptotic series of \(D(x)\).

HINT: Introduce a cutoff parameter.

If \((x_n)\) is a weakly convergent sequence in a normed space \(X\), say, \(x_n\to x_0\) weakly, show that there is a sequence \((y_n)\) of linear combinations of elements of \((x_n)\) which converges strongly to \(x_0\). Hint: First prove that \(x_0\in \overline {\operatorname {span}(x_n)}\).

Let \(f\) be a real-valued and twice continuously differentiable on an interval \([a,b]\). Let \(\hat {x}\) be a simple zero of \(f\), i.e. \(f'(\hat {x})\ne 0\). Use the Banach Fixed Point Theorem to show that Newton’s method, defined by \[ x_{n+1}=x_n-\frac {f(x_n)}{f'(x_n)} \] converges to \(\hat {x}\) for any \(x_0\) sufficiently close to \(\hat {x}\).

Let \(X,Y\) be Hilbert spaces and let \((e_n)\subset X\) be a total orthonormal sequence. Recall that an operator \(T:X\to Y\) is said to be Hilbert-Schmidt if the Hilbert-Schmidt norm \[ \lVert T\rVert _{\mathrm {HS}}:=\left (\sum _{n=1}^{\infty }\lVert Te_n\rVert ^2\right )^{1/2} \] is finite.

1. Show that the Hilbert-Schmidt norm is independent of the sequence \((e_n)\) chosen. Hint: Use Parseval’s identity.
2. Show that a Hilbert-Schmidt operator is compact.
3. For a Hilbert-Schmidt operator, \(T\), show that \(\lVert T\rVert \le \lVert T\rVert _{\mathrm {HS}}\), where \(\lVert \cdot \rVert \) denotes the operator norm.

Let \(T:H\to H\) be a compact, self-adjoint linear operator defined on a separable Hilbert space \(H\). Let \((v_n)\) be a complete orthonormal sequence of eigenvectors of \(T\) and let \((\lambda _n)\) be the corresponding eigenvalues.

1. Let \(\lambda \in \rho (T)\). Show that the resolvent of \(T\) at \(\lambda \), acting on some \(x\in H\) can be written as \[ R_\lambda x=\sum _{n=1}^{\infty }\frac {1}{\lambda _n-\lambda }\langle x,v_n\rangle v_n. \]
2. Use part (a) to show that if \(\lambda ,\mu \in \rho (T)\) then the first resolvent identity holds: \[ R_\lambda -R_\mu =(\lambda -\mu )R_\lambda R_\mu . \]

1. Find all values of \(i^i\).
2. Find all solutions of the equation \(\cos z=2\).
3. Find all solutions of the equation \(\tan z=i\).

The following function \(f(x)\) [\(x\) is a real variable] can be represented by a series (Taylor or Laurent) in powers of \(x\). Find the radius of convergence of the series in each case \[ \begin {array}{rcl} \text {(a)}\quad f(x)&=&\left (\dfrac {\sin x}{x}\right )^2,\\[1.4ex] \text {(b)}\quad f(x)&=&\dfrac {\sin x}{x^2},\\[1.4ex] \text {(c)}\quad f(x)&=&\left (\dfrac {x}{\sin x}\right )^2,\\[1.4ex] \text {(d)}\quad f(x)&=&\dfrac {x^2}{\sin x},\\[1.4ex] \text {(e)}\quad f(x)&=&\dfrac {\sin x}{x^2+1}. \end {array} \] [You do not need to find the series themselves.]

Integrate \[ \begin {array}{rcl} \text {(a)}&\displaystyle \int _0^{2\pi }\frac {d\phi }{(p+q\cos \phi )^2} &\text {(parameters }p>q>0\text {)},\\[2.2ex] \text {(b)}&\displaystyle \int _{-\infty }^{\infty }\frac {e^{\alpha x}}{1+e^x}\,dx &\text {(parameter }\alpha \in (0,1)\text {)},\\[2.2ex] \text {(c)}&\displaystyle \int _0^{\infty }\sin (a^2x^2)\,dx &\text {(positive parameter }a\text {)}. \end {array} \]

Prove that if all singularities of an analytic function \(f(z)\) in the extended complex plane \(\overline {\mathbb {C}}\) are poles, then \(f(z)\) is a rational function (i.e. the ratio of two polynomials).

Consider the operator \(T:\ell ^2\to \ell ^2\) defined for \(x=(\xi _j)\in \ell ^2\) by \[ Tx=(0,\xi _1\alpha _1,\xi _2\alpha _2,\ldots ), \] for some sequence \((\alpha _j)\) with \(\alpha _j\to 0\). Show that \(T\) is compact.

Let \(X\) be a Banach space and consider the non-linear mapping \(F:X\to X\) defined by \[ F(x)=y-\alpha \lVert x\rVert x, \] where \(y\in X\) is fixed and \(\alpha \) is a scalar. Show that there is a constant \(C>0\) such that for any \(\lvert \alpha \rvert <C\), \(F\) is a contraction on the open ball of radius \(1\) centered at \(y\).

Let \(M\) be a subset of a Hilbert space \(H\). Assume \(M\) is such that for any \(v,w\in H\) for which the equality \[ \langle v,x\rangle =\langle w,x\rangle \] holds for all \(x\in M\), we must have \(v=w\). Show that \(M^\perp =\{0\}\).

Let \(X\) be a real Banach space. Assume \(f\in X^*\) has a closed nullspace \(\mathcal {N}(f)\). The goal of this problem is to show that \(f\) must be a bounded linear functional.

1. Let \(x_0\in X\) be such that \(f(x_0)=1\). Explain why there is an \(\epsilon >0\) for which the ball \[ B(x_0,\epsilon )\equiv \{x\in X\mid \lVert x-x_0\rVert <\epsilon \} \] satisfies \(B(x_0,\epsilon )\subset X-\mathcal {N}(f)\).
2. Prove that \(f(x)>0\) for all \(x\in B(x_0,\epsilon )\), where \(\epsilon \) is as in part (a). To prove this, you may assume for contradiction that there is some \(y\in B(x_0,\epsilon )\) with \(f(y)<0\).
3. Any \(x\in B(x_0,\epsilon )\) can be written as \(x=x_0+\epsilon u\) for some \(u\) with \(\lVert u\rVert <1\). Use the result of part (b) to show that \(\lvert f(u)\rvert <1/\epsilon \).
4. To conclude, give an upper bound for \(\lVert f\rVert \).

Let \(T:X\to X\) be a bounded linear operator on a complex Banach space \(X\). Prove that \(\sigma (T)\) lies in the complex plane disk: \[ \{\lambda \in \mathbb {C}\mid \lvert \lambda \rvert \le \lVert T\rVert \}. \]

The following function \(f(x)\) [\(x\) is a real variable] can be represented by a series (Taylor or Laurent) in powers of \((x-7)\). Find the radius of convergence of the series in each case \[ \begin {array}{rcl} \text {(a)}\quad f(x)&=&e^{(x-7)^{10}},\\[0.6ex] \text {(b)}\quad f(x)&=&\left (\dfrac {\sin x-3}{\sin x-2}\right )^2,\\[1.4ex] \text {(c)}\quad f(x)&=&\dfrac {\sin x-2}{x^2-49}. \end {array} \] [You do not need to find the series themselves.]

1. Prove: If a function is analytic then its real and imaginary parts are harmonic.
2. Prove: If a function \(u(x,y)\) is harmonic in a domain \(D\), then \(u(x,y)\) cannot attain a strict local maximum in \(D\). [Hint: If \(f(z)=u+iv\), then function \(\phi (z)=e^{f(z)}\) has absolute value \(\lvert \phi (z)\rvert =e^u\).]

Integrate

1. \[ \int _0^\infty \frac {\sin \alpha x}{x}\,dx, \]
2. \[ \int _0^\infty \frac {x^\alpha }{1+x}\,dx, \]
3. \[ \int _0^\infty \sin x^2\,dx \]

[Explain the logic (in particular, the choice of contour), but do not worry about getting the exact numbers; \(\alpha \) is a real parameter.]

1. Consider a 2-dimensional map \((x,y)\to (u,v)\). Explain: If the map is given by an analytic function [\(u+iv=f(x+iy)\)] and at some point \(z_0=x_0+iy_0\) the derivative \(f'(z_0)\ne 0\), then this map preserves small shapes in the vicinity of \(z_0\).
2. Is a square conformally equivalent to a circle?
3. Explain: A map by analytic function preserves Laplace’s equation.

Solve Laplace’s equation \[ u_{xx}+u_{yy}=0 \quad \text {in the domain}\quad D=\{(x,y)\in \mathbb {R}^2:\ (x-1)^2+y^2>1\ \& \ (x-2)^2+y^2<4\} \] subject to the boundary condition \[ u(x,y)=a\text { when }(x-1)^2+y^2=1 \qquad \text {and}\qquad u(x,y)=b\text { when }(x-2)^2+y^2=4 \] [\(a\) and \(b\) are real parameters; the two circles touch each other; express your answer in terms of the original real variables \(x,y\)].

Let \(A\in \mathbb {C}^{m\times m}\) be hermitian:

a) Prove that all eigenvalues of \(A\) are real.

b) Prove that if \(x\) and \(y\) are eigenvectors corresponding to distinct eigenvalues, then \(x\) and \(y\) are orthogonal.

Numerical Algorithm to Find Eigenvectors/Eigenvalues

State the Inverse Iteration Algorithm to find eigenvectors/eigenvalues for general real symmetric matrix \(A\in \mathbb {R}^{m\times m}\).

Singular Value Decomposition

a) Consider \(A\in \mathbb {C}^{m\times n}\). Define what we mean by the singular value decomposition of \(A\).

b) Show that the rank of \(A\) is \(r\), the number of nonzero singular values.

CG Method

a) Formulate the Conjugate Gradient (CG) algorithm for the solution of the linear system \(Ax=b\), where \(A\in \mathbb {R}^{n\times n}\) is symmetric positive definite matrix.

b) Show that for any initial guess \(x_0\in \mathbb {R}^n\), Conjugate Gradient algorithm converges to the solution \(x\) of the linear system \(Ax=b\) in at most \(n\) steps.

Interpolation

a) State the theorem about the existence and uniqueness of interpolating polynomial. Give a proof. (You can consider any proof of your choice).

b) Let \(f(x)=x^3+2x^2+x+1\). Find the polynomial of degree 4 that interpolates the values of \(f\) at \(x=-2,-1,0,1,2\).

Linear Multistep Methods

Give the definition of linear multistep method (give formula).

a) State necessary and sufficient condition for linear multistep method to be consistent.

b) State root condition for linear multistep method.

c) Construct an example of a consistent but not stable linear multistep method. Justify your answer.

Upwind Scheme

Consider the advection equation \[ u_t+5u_x=0,\qquad x_L<x<x_R,\qquad 0<t\le T, \] where \(u(x,0)=g(x)\), and \(u(x_L,t)=u_L(t)\) for \(t>0\).

a) Write the Upwind Scheme for this problem.

b) What is the local truncation error of the Upwind Scheme?

c) What is the stencil of the scheme? What is the CFL condition for this method?

d) Investigate the stability of the method using Von Neumann Stability Analysis.

Let \(X\) be a Banach space, let \(z\in X\) with \(z\ne 0\), and let \(f\in X'\) with \(f\ne 0\). Consider the linear operator \(T:X\to X\) defined for \(x\in X\) by \[ Tx=f(x)z. \]

1. Briefly explain why \(T\) is compact.
2. Use Neumann series to give a condition on \(f\) and \(z\) that ensures the equation \(x+Tx=y\) admits a unique solution \(x\) for all \(y\in X\).
3. Use the Fredholm alternative to find a condition on \(f\) and \(z\) that ensures the equation \(x+Tx=y\) admits a unique solution \(x\) for all \(y\in X\).

Let \(X\) and \(Y\) be normed vector spaces. Show that a linear operator \(T:X\to Y\) is compact if and only if for every sequence \((x_n)\) with \(\lVert x_n\rVert \le 1\), the sequence \((Tx_n)\) has a convergent subsequence.

Let \(T\) be a bounded linear operator on a complex Hilbert space \(H\). Show that the operator \(I+T^*T\) is injective.

Let \(Y\) be a subspace of a Hilbert space \(H\). Show that \(Y\) is closed if and only if \(Y=Y^{\perp \perp }\).

Let \(X\) be a Banach space. Let \((f_n)\) be a sequence in \(X'\).

1. Show that \(f_n\to f\) weakly in \(X'\) implies that for all \(x\in X\), we have \(f_n(x)\to f(x)\).
2. If there is an \(f\in X'\) such that \(f_n(x)\to f(x)\) for all \(x\in X\), does \(f_n\to f\) weakly in \(X'\)? Explain your answer.

Find the sum \[ \cos x+\cos 3x+\cos 5x+\cdots +\cos 99x. \]

Prove the fundamental theorem of algebra:

Every polynomial of degree \(n(\ge 1)\) has exactly \(n\) zeros (each zero being counted according to its multiplicity).

Evaluate the integrals

1. \[ \int _{-\infty }^{\infty }\frac {\sin x}{x}\,dx, \]
2. \[ \int _0^\infty \frac {x^\alpha }{x+1}\,dx. \]

Show that Fourier transform \[ f(x)\to F(\mu )=\int _{-\infty }^{\infty } f(x)e^{i\mu x}\,dx \] preserves the inner product and the \(L_2\) norm (Plancherel’s equations): \[ \int _{-\infty }^{\infty }\bar {f}(x)g(x)\,dx = \int _{-\infty }^{\infty }\bar {F}(\mu )G(\mu )\,\frac {d\mu }{2\pi }, \] \[ \text {and}\qquad \int _{-\infty }^{\infty }\lvert f(x)\rvert ^2\,dx = \int _{-\infty }^{\infty }\lvert F(\mu )\rvert ^2\,\frac {d\mu }{2\pi }. \] (\(\overline {\phantom {x}}\) denotes complex conjugation).

Solve Laplace’s equation \[ \phi _{xx}+\phi _{yy}=0 \quad \text {in the domain}\quad D=\{z:\lvert z-1\rvert >1,\ \lvert z-2\rvert <2\} \] subject to the boundary condition \[ \phi (x,y)=a\text { when }\lvert z-1\rvert =1 \qquad \text {and}\qquad \phi (x,y)=b\text { when }\lvert z-2\rvert =2 \] (\(a\) and \(b\) are real parameters).

Numerical Integration

Find a formula of the form \[ \int _0^{2\pi } f(x)\,dx = A_1 f(0)+A_2 f(\pi ) \] that is exact for any function having the form \[ f(x)=c+d\cos (x). \]

Matrix Properties

Show that if a matrix \(B\in \mathbb {R}^{m\times m}\) is both upper triangular and orthogonal, then it is diagonal.

Singular Value Decomposition (SVD)

a) Consider \(A\in \mathbb {C}^{m\times n}\). Define what we mean by the singular value decomposition of \(A\).

b) Consider \(A\in \mathbb {C}^{m\times m}\) and show that \[ \lvert \det (A)\rvert =\prod _{i=1}^m\sigma _i, \] where \(\{\sigma _i\}\) are the singular values of \(A\).

Overdetermined Linear System

Solve the following overdetermined linear system in the sense of the least squares: \[ z+y=1,\qquad z-y=2,\qquad 4z+2y=4.8. \]

Interpolation

a) State the theorem about the existence and uniqueness of interpolating polynomial. Give a proof.

b) Let \(f(x)=5x^2+x+1\). Find the polynomial of degree 3 that interpolates the values of \(f\) at \(x=-1,0,1,2\).

Linear Multistep Methods

Define linear multistep method (give formula).

a) State necessary and sufficient condition for linear multistep method to be consistent.

b) State root condition for linear multistep method.

c) What can you say about consistency and stability properties of the method: \[ y_{n+1}-3y_n+2y_{n-1}=-h f(y_{n-1})? \]

Upwind Scheme

Consider the advection equation \[ u_t-u_x=0,\qquad x_L<x<x_R,\qquad 0<t\le T, \] where \(u(x,0)=g(x)\), and \(u(x_R,t)=u_R(t)\) for \(t>0\).

a) Write the Upwind Scheme for this problem.

b) What is the stencil of the scheme? What is the CFL condition for this method?

c) Investigate the stability of the method using Von Neumann Stability Analysis.

Assume a bounded, self-adjoint operator \(T:H\to H\), where \(H\) is a Hilbert space, satisfies \[ \langle Tx,x\rangle \ge \beta \lVert x\rVert ^2, \tag {1} \] for some \(\beta >0\). The goal of this problem is to show that \(T\) is one-to-one and onto.

1. Show that the nullspace of \(T\) is trivial, i.e. \(\mathcal {N}(T)=\{0\}\).
2. Show that the range \(\mathcal {R}(T)\) is closed.
3. Show that \(\mathcal {R}(T)^\perp =\{0\}\).
4. Why do we have \(\mathcal {R}(T)=H\)?

Let \(X\) be a Banach space, \(f:X\to \mathbb {R}\) be a bounded linear functional, \(y\in X\) fixed and \(\alpha \in \mathbb {R}\).

1. Prove that there exists a constant \(C>0\) such that if \(\lvert \alpha \rvert <C\), then the non-linear equation \[ x+\alpha f(x)x=y, \tag {2} \] has a unique solution \(x\) in the ball \(B=\{x\in X\mid \lVert x-y\rVert \le 1\}\).
2. Suggest an iterative procedure for approximating the unique solution \(x\) to equation (2).

Let \((e_n)\) be an orthonormal sequence of a Hilbert space \(H\). Show that \(e_n\to 0\) weakly.

Let \((\lambda _j)\) be a sequence real numbers with \(\lambda _j\ne 1\) for all \(j\) and \(\lambda _j\to 1\). Consider the operator \(T:\ell ^2\to \ell ^2\) defined for \((\xi _j)\in \ell ^2\) by \[ T(\xi _j)=(\lambda _j\xi _j). \]

1. Find the spectrum \(\sigma (T)\), point spectrum \(\sigma _p(T)\), continuum spectrum \(\sigma _c(T)\), residual spectrum \(\sigma _r(T)\) and resolvent set \(\rho (T)\).
2. Give a condition on the \(\lambda _j\) for \(T\) to be invertible.

Consider the distribution \(u\in \mathcal {D}'(\mathbb {R})\) defined for \(\phi \in \mathcal {D}(\mathbb {R})\) by \[ \langle u,\phi \rangle =\int _{-\infty }^{\infty }\lvert x\rvert \phi (x)\,dx. \] Find its derivative \(\partial u\).

The following functions \(f(x)\) [\(x\) is a real variable] can be represented by series (Taylor or Laurent) in powers of \((x-2)\). Find the radius of convergence of the series in each case \[ \begin {array}{rcl} \text {(a)}\quad f(x)&=&e^{x^2},\\[0.6ex] \text {(b)}\quad f(x)&=&\dfrac {\sin x-3}{\sin x-2},\\[1.2ex] \text {(c)}\quad f(x)&=&\dfrac {e^x}{(x-2)(1+e^x)}. \end {array} \]

Integrate \[ \int _{-\infty }^{\infty }\frac {\sin \alpha x}{\sinh \pi x}\,dx. \]

Solve Laplace’s equation \[ \phi _{xx}+\phi _{yy}=0 \quad \text {in the domain}\quad D=\{(x,y)\in \mathbb {R}^2:\ x^2+y^2>1,\ x^2+(y+1)^2<4\} \] subject to the boundary condition \[ \phi (x,y)=a\text { when }x^2+y^2=1 \qquad \text {and}\qquad \phi (x,y)=b\text { when }x^2+(y+1)^2=4 \] (\(a\) and \(b\) are real parameters; the two circles touch each other; express your answer in terms of the original real variables \(x\) ans \(y\)).

1. Calculate the Fourier transform of a Gaussian \(f(x)=e^{-x^2}\) (\(x\in \mathbb {R}\)).
2. Is it possible that a function \(f(x)\) (\(x\in \mathbb {R}\)) and its Fourier transform \(F(\mu )\) (\(\mu \in \mathbb {R}\)) both have finite support?

Find the three-term asymtotic expansion of the integral \[ I(s)=\int _0^1 \ln (t)\,e^{ist}\,dt \] with large real parameter \(s\to +\infty \).

Interpolation Suppose \(f\) is arbitrarily often differentiable and let \(p\) be the unique polynomial of degree \(d\) satisfying \[ p(x_i)=f(x_i),\qquad i=0,\ldots ,n \] where the abscissas \(x_i\) are distinct. Derive a suitable expression for the error \(f(x)-p(x)\) and discuss its properties.

Positive Definite Matrices The Cholesky decomposition of a (symmetric and) positive definite matrix is defined to be a factorization of the form \(A=LL^T\) where \(L\) is lower triangular. Show that the Cholesky decomposition exists. Discuss whether or not it is unique.

Iterative Methods for Linear Systems Consider the square linear system \(Ax=b\) and the Gauss-Jacobi Method \[ x_i^{[k+1]}= \frac {1}{a_{ii}}\left ( b_i-\sum _{j=1}^{i-1}a_{ij}x_j^{[k]} -\sum _{j=i+1}^{n}a_{ij}x_j^{[k]} \right ) \] where \(i=1,\ldots ,n\) and \(k=0,1,\ldots \). Show that this method converges for all starting vectors \(x^{[0]}\) if \(A\) is diagonally dominant, i.e., \[ \sum _{j=1}^{k}\lvert a_{ij}\rvert + \sum _{j=k+1}^{n}\lvert a_{ij}\rvert < \lvert a_{ii}\rvert \qquad \text {for all } i=1,2,\ldots ,n. \]

Padé Approximants Define what is meant by the Padé approximant of a function \(f\) and compute the \([1/1]\) Padé approximant of the exponential.

ODEs Consider the initial value problem for a system of ODEs \(y'=Ay\) where \(A\) has eigenvalues that are widely spread in the left half plane. Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. \[ \begin {aligned} (1)\quad y^{n+1} &= y^n+kAy^n,\\ (2)\quad y^{n+1} &= y^n+kAy^{n+1},\\ (3)\quad y^{n+1} &= y^n+\frac {k}{2}A\left (y^n+y^{n+1}\right ). \end {aligned} \]

Wave Equation Consider the wave equation in one space dimension: \[ u_{tt}=c^2u_{xx},\qquad c>0. \] Suppose \(0\le x\le 1\) and \(t\ge 0\). The problem requires initial and boundary conditions but you can ignore them for the purposes of this question. Consider the usual discretization \[ \frac {1}{k^2}\left (U_m^{n+1}-2U_m^n+U_m^{n-1}\right ) = \frac {c^2}{h^2}\left (U_{m+1}^n-2U_m^n+U_{m-1}^n\right ) \] where \[ U_m^n\approx u(x_m,t_n) \] and \[ x_m=mh,\qquad h=\frac {1}{M},\qquad \text {and}\qquad t_n=nk,\qquad h,k>0. \] Let the grid constant \(r\) be defined by \[ r=\frac {kc}{h}. \] Derive the constraint on \(r\) imposed by the Courant-Friedrichs-Lewy condition. There is a value of \(r\) for which the local truncation error of the difference scheme is zero. Derive that value.

Heat Equation Consider the following heat equation problem \[ u_t=u_{xx},\qquad t>0,\qquad 0<x<1, \] \[ u(0,t)=u(1,t)=0,\qquad t>0, \] \[ u(x,0)=u_0(x),\qquad 0\le x\le 1. \] Using the forward or backward difference for the time derivative and central difference for the space derivative, derive the explicit and implicit schemes. What’s the stability condition for each case? Perform a Fourier analysis on both the explicit and implicit methods and use the von Neumann condition to verify these stability conditions.

Let \(M\) be a subset of a Hilbert space \(H\). The goal of this problem is to show that: \[ \overline {\operatorname {span}M}=H \quad \text {if and only if}\quad M^\perp =\{0\}. \]

1. Assume \(\overline {\operatorname {span}M}=H\) and let \(x\in M^\perp \). Show that \(x=0\).
2. Assume \(M^\perp =\{0\}\). Show that \(\overline {\operatorname {span}M}=H\).

Let \((x_n)\) be a sequence in a Hilbert space \(H\). Show that: \[ x_n\to x\ \textbf {strongly} \quad \text {if and only if}\quad (x_n\to x\ \textbf {weakly}\text { and }\lVert x_n\rVert \to \lVert x\rVert ). \]

Let \(u,v\) be non-zero elements of a Hilbert space \(H\). Consider the linear operator \(T:H\to H\) defined for \(x\in H\) by \(Tx=u(x,v)\).

1. Briefly explain why the operator \(T\) is compact.
2. Find a condition on \(u\) and \(v\) that guarantees that the equation \[ (I-T)x=y \] admits a unique solution \(x\) for all \(y\in H\).

Let \((\lambda _n)\in \ell ^2\) and consider the operator \(T:\ell ^2\to \ell ^2\) defined by \(y=Tx\), where \(x=(\xi _j)\in \ell ^2\), \(y=(\eta _j)\in \ell ^2\) and \[ \eta _j=\sum _{k=1}^{\infty }\alpha _{jk}\xi _k,\qquad j=1,2,\ldots , \] where the \(\alpha _{jk}\) satisfy \[ \sum _{j=1}^{\infty }\sum _{k=1}^{\infty }\lvert \alpha _{jk}\rvert ^2<\infty . \] Show that \(T\) is a compact operator. Hint: Approximate \(T\) with finite rank operators \(T_n\).

Let \(T:X\to X\) be a bounded linear operator defined on a Banach space \(X\). Denote by \(R_\lambda \) the resolvent operator associated with \(T\) for some \(\lambda \in \rho (T)\). The resolvent set of \(T\) is denoted by \(\rho (T)\).

1. Use Neumann series to show that for \(\lambda ,\mu \in \rho (T)\), \[ R_\lambda =\sum _{j=0}^{\infty }(\lambda -\mu )^j R_\mu ^{j+1}, \] where the series is absolutely convergent in the operator norm when \[ \lvert \lambda -\mu \rvert <\lVert R_\mu \rVert ^{-1}. \]
2. Deduce from part (a) whether the spectrum \(\sigma (T)\) is open, closed or neither.

Find the radius of convergence of the Taylor series with the center at the origin (\(x_0=0\)) for the following function

1. \[ f(x)=\frac {\sqrt {x+3}}{x^2+3} \]
2. \[ f(x)=\frac {1}{(\cos x+3)^2} \]

(\(x\) is a real variable; you do not need to find the series themselves).

Let \(D_1\) and \(D_2\) be two disjoint domains, whose boundaries share a common curve \(\Gamma \). Let

• \(f(z)\) be analytic in \(D_1\) and continuous in \(D_1\cup \Gamma \)
• \(g(z)\) be analytic in \(D_2\) and continuous in \(D_2\cup \Gamma \)
• \(f(z)=g(z)\) for \(z\in \Gamma \)

Show that the function \[ H(z)= \begin {cases} f(z), & z\in D_1,\\ f(z)=g(z), & z\in \Gamma ,\\ g(z), & z\in D_2 \end {cases} \] is analytic in \(D=D_1\cup \Gamma \cup D_2\).

[Hint: Use the Morera theorem.]

1. Show that any analytic function (not identically equal to zero) can have only isolated zeros inside its analyticity domain.
2. Can an analytic function have a non-isolated singularuty?
3. Prove the Uniqueness Theorem: If two functions are analytic in a domain \(D\) and equal on some set of points that has a limiting point inside \(D\), then these functions are identically equal in \(D\).

Evaluate

1. \[ \int _{-\infty }^{\infty } e^{ix^2}\,dx \]
2. \[ \int _0^\infty \frac {\sin x}{x}\,dx. \]

Find the leading behavior, as \(s\to +\infty \), of the integral

1. \[ I(s)=\int _0^3 \frac {1}{\sqrt {x^2+2x}}e^{-sx}\,dx \]
2. \[ I(s)=\int _0^{\pi /2} e^{is\cos x}\,dx \]

Let \(A\) be an \(m\times n\) matrix where you may assume that \(m\geq n\). Define what is meant by the Singular Value Decomposition of \(A\). Then use it to show that if the rank of \(A\) is \(p\) then there exists an \(m\times p\) matrix \(X\) and an \(n\times p\) matrix \(Y\) such that \[ A=XY^T. \]

Consider the quadrature rule \[ \int _a^b w(x)f(x)dx = \sum _{j=1}^n w_jf(x_j)+E_n. \] Assume that \(w\) is a positive weight function. Discuss how to pick the knots \(x_1,\ldots ,x_n\) and weights \(w_1,\ldots ,w_n\) to make the error \(E_n\) zero for all polynomials \(f\) up to a degree as high as possible.

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.

Suppose \(A\) is an \(m\times n\) real matrix with \(m>n\), and \(b\in \mathbb {R}^m\). For any vector \(v\in \mathbb {R}^m\), let \[ \|v\|_2=\sqrt {\sum _{i=1}^m v_i^2} \] as usual. Describe how to solve the Least Squares Problem \[ \|Ax-b\|_2=\min \] using the \(QR\) factorization of \(A\). Briefly state how you would compute the \(QR\) factorization.

Explain how to combine the Shooting method and Newton’s Method to solve the boundary value problem \[ y''=f(x,y,y'),\qquad a\leq x\leq b,\qquad y(a)=A,\qquad y(b)=B \] where \(y=y(x)\) and \(y\) and \(f\) are scalar valued.

Consider the variational principle: \[ I(u)=\int _0^1 \left (u'(x)\right )^2+k^2\left (u(x)\right )^2 dx=\min \qquad \text {subject to}\qquad u(0)=u(1)=1. \] Suppose you want to use the Ritz Method to approximate the solution of this problem by a polynomial of degree \(n\). Derive a linear system for the coefficients of that polynomial.

Consider the initial-boundary-value problem \[ u=u(x,t)=?,\qquad u_t=u_{xx},\qquad x\in [0,1],\qquad t\geq 0, \] subject to the initial and boundary conditions \[ u(x,0)=f(x),\qquad u(0,t)=g_0(t),\qquad u(1,t)=g_1(t) \] Explain how to use the method of lines to solve this problem. Describe the scheme you obtain by using the Backward Euler Method to solve the resulting ODEs and compute the local truncation error of that scheme.

Let \(T:L^1[0,1]\to L^2[0,1]\) be a bounded linear operator. Let \(a\in L^\infty [0,1]\) and \(g\in L^1[0,1]\).

1. Prove that there exists a constant \(C>0\) such that if \(\lVert a\rVert _{L^\infty }<C\) then the equation \[ f+a(Tf)^2=g \tag {1} \] has a unique solution \(f\) in the set \[ B=\{u\in L^1[0,1]:\lVert u-g\rVert _{L^1}\le 1\}. \] Note: the constant \(C\) may depend on \(T\) and/or \(g\).
2. Suggest an iterative procedure for approximating the unique solution \(f\) to equation (1).

Let \(X\) be a separable Hilbert space and \((e_n)\) be a total orthonormal sequence of \(X\). Let \(T:X\to X\) be a bounded linear operator satisfying \[ \sum _{n=1}^{\infty }\lVert Te_n\rVert ^2<\infty . \tag {2} \] Define the operators \(T_k:X\to X\), \(k=1,2,\ldots \), that applied to an arbitrary \[ x=\sum _{n=1}^{\infty }x_ne_n\in X \qquad \text {give}\qquad T_kx=\sum _{n=1}^k x_nTe_n. \]

1. Are the operators \(T_k\) compact? Explain why or why not.
2. Using equation (2), show that the sequence \((T_k)\) converges uniformly to \(T\), i.e. show that \(\lVert T-T_k\rVert \to 0\) as \(k\to \infty \).
3. Is \(T\) compact? Explain why or why not.

Assume a compact self-adjoint operator \(T:X\to X\), where \(X\) is a separable Hilbert space, satisfies \(\langle Tx,x\rangle \ge 0\) for all \(x\in X\).

1. State the spectral theorem for compact self-adjoint operators.
2. Show that all the eigenvalues of \(T\) are non-negative.
3. Construct an operator \(S:X\to X\) such that \(T=S^2\).

Let \(\ell ^{1'}\) be the dual space of \(\ell ^1\). The objective here is to show that \(\ell ^{1'}\) is isomorphic to \(\ell ^\infty \). You may use that a Schauder basis for \(\ell ^1\) (and \(\ell ^\infty \)) is \((e_k)\), where \(e_k=(\delta _{kj})\), i.e. the sequence with zeroes everywhere except for a \(1\) in the \(k\)–th position.

1. Show that any \(f\in \ell ^{1'}\) corresponds to a sequence \(g=(\gamma _k)\in \ell ^\infty \).
2. Show that any sequence \(g=(\gamma _k)\in \ell ^\infty \) corresponds to some \(f\in \ell ^{1'}\).
3. Parts (a) and (b) define a bijective linear mapping \(G:\ell ^{1'}\to \ell ^\infty \). Prove that \(G\) is an isomorphism by showing \(\lVert f\rVert _{\ell ^{1'}}=\lVert G(f)\rVert _{\ell ^\infty }\) for any \(f\in \ell ^{1'}\).

Let \(K:L^2[0,1]\to L^2[0,1]\) be the linear operator defined by \[ (Kx)(t)=\int _0^1 k(t,\tau )x(\tau )\,d\tau \] where \(k:[0,1]\times [0,1]\to \mathbb {R}\) is continuous.

1. Show that \(K\) is bounded and give an upper bound for \(\lVert K\rVert \) (in terms of \(k\)).
2. Show that there is a constant \(C\) such that if \(\lvert \mu \rvert <C\), the operator \(I+\mu K\) is invertible.
3. Assuming \(\lvert \mu \rvert <C\), where \(C\) is as in part (b), express \((I+\mu K)^{-1}\) as a series. Specify whether the series converges and in what sense.

Find the radius of convergence of the Taylor series with the center at \(x_0=1\) for the following function

1. \[ f(x)=x^{1/3} \]
2. \[ f(z)=\frac {(\sin x+2)^2}{(\sin x-2)^2} \]

(\(x\) is a real variable; you do not need to find the series themselves).

1. Show that any analytic function (not identically equal to zero) can have only isolated zeros inside its analyticity domain.
2. Prove the Uniqueness Theorem: If two functions are analytic in a domain \(D\) and equal on some set of points that has a limiting point inside \(D\), then these functions are identically equal in \(D\).

Evaluate the integrals:

1. \[ I=\int _0^\infty \frac {\sin x}{x}\,dx, \]
2. \[ I=\int _0^\infty \frac {x^\alpha }{2+x}\,dx \qquad (-1<\alpha <0). \]

1. Calculate the Fourier transform of a Gaussian \(f(x)=e^{-x^2}\).
2. Formulate and prove Heisenberg’s uncertainty principle.

Consider integral \[ I(s)=\int _C \frac {e^{s(z^2-1)}}{z-1}\,dz \] with large parameter \(s\to +\infty \); \(C\) is the vertical line \(\operatorname {Im}z=3\), from \(z=3-i\infty \) to \(z=3+i\infty \).

1. What is the saddle point \(z_0\)?

   What is the path \(C_0\) of steepest descent from \(z_0\)?

   What is the path of steepest ascent from \(z_0\)?

2. Find the three-term asymtotic expansion of the integral.

Consider the problem \(u''(x)=x\delta '(x)\), where \(\delta \) is the “delta function”. Explain what it means for this problem to have a solution \(u\) in the sense of distributions. Find a distributional solution \(u\) and prove that it does in fact solve the problem in the sense of distributions.

Let \(A\) be a real \(m\times n\) matrix, and let \(b\in \mathbb {R}^m\) be a column vector. Consider the problem \[ A^*Ax=A^*b. \tag {*} \]

1. Explain the relationship between \((*)\) and the problem \[ \min _{x\in \mathbb {R}^n}\lVert Ax-b\rVert ^2. \]
2. Under what conditions on \(A\), \(A^*\), and \(b\) is it guaranteed that \((*)\) has a solution \(x\)? Under what conditions is it guaranteed that \((*)\) has a unique solution?
3. Given \(\varepsilon >0\), consider the problem \[ (A^*A+\varepsilon I)x_\varepsilon =A^*b. \tag {**} \] Formulate an associated minimization problem, describe existence and uniqueness, and explain how \(\lim _{\varepsilon \to 0+}x_\varepsilon \) is related to solutions of \((*)\).

Consider the problem \(u''(x)=f(x)\), on \((0,1)\), with boundary conditions \(u'(0)=u'(1)=0\).

1. Write down the weak formulation of the problem.
2. Using a piecewise linear finite element basis with uniform grid size \(h\), use the Galerkin method to find a finite-dimensional (matrix) approximate representation for the problem. Do not solve the equations.
3. Neither of the problems (a) and (b) have unique solutions in general. Explain why not, and describe what can be done to correct the deficiency.

Define \[ Ku(x)=\sum _{n=0}^{10}\left (\int _{-1}^{1}e^{-ny}u(y)\,dy\right )x^n, \qquad x\in [-1,1]. \]

1. Find the adjoint \(K^*\) of the operator \(K\).
2. Assuming \(\lambda \ne 0\) is fixed and real, use the Fredholm Alternative to characterize the set of functions \(g\) such that the problem \((K-\lambda I)u=g\) on \([-1,1]\) has a solution.
3. From the structure of the operator \(K\), what can be said about the set \[ \sigma _p=\{\lambda \in \mathbb {C}:(K-\lambda I)u=0\text { has a solution }u\ne 0\}? \] There is no need to actually calculate \(\sigma _p\).

Construct the Green’s function for the problem \[ u''(x)+\alpha ^2u(x)=f(x),\quad \text {on }(0,1),\qquad u(0)=u(1)=0. \] Write the solution \(u\) in terms of the Green’s function, and determine values of \(\alpha \) for which the Green’s function does not exist.

The function \(f(z)\) is analytic in the extended complex plane except for two points \(z=0\) and \(z=2\), where it has simple poles. It is known that \[ \oint _{|z|=1} f(z)\,dz=1, \qquad \oint _{|z|=3} f(z)\,dz=0. \] Find \(f(z)\) (unique up to an arbitrary additive constant).

Find the radius of convergence of the Taylor series \[ \text {for the function } f(x)=\frac {1}{\cos ^2 x+4} \quad \text {around the origin } x_0=0. \] {You do not need to find the Taylor series itself.}

Evaluate the integral \[ \int _0^\infty e^{ix^2}\,dx. \]

Find the leading behavior of the integral \[ I=\int _0^3\frac {\cos x}{\sqrt {x}}e^{-sx}\,dx \] for large positive \(s\).

Suppose that \(E\) is a bounded linear operator on a Hilbert space \(H\), with operator norm \(\lVert E\rVert =r<1\). Show that the operator \(I-E\), where \(I\) is the identity, is bounded and invertible. Give an estimate for \(\lVert (I-E)^{-1}\rVert \), and a convergent series representation for \((I-E)^{-1}\).

Suppose that the square real matrix \(A=(a_{ij})\) satisfies \(a_{ij}=a_{ji}\) for all \(i,j\).

1. Show that every eigenvalue \(\lambda \) of \(A\) must be real.
2. Show that for any eigenpairs \((\lambda _1,u_1)\), \((\lambda _2,u_2)\), with \(\lambda _1\ne \lambda _2\), the eigenvectors \(u_1\) and \(u_2\) must be orthogonal.
3. Let \[ c=\min _{\lVert u\rVert =1}u^TAu. \] Prove that if \(c>0\), then \(A^{-1}\) exists. In this case, find an estimate for the matrix operator norm \(\lVert A^{-1}\rVert \).

Consider the problem \(Lu=1\) on \((0,\pi )\), where \(Lu=u''+u\) with boundary conditions \(u'(0)=u'(\pi )=0\).

1. Write down the weak formulation of the problem.
2. Find the \(L^2[0,\pi ]\) adjoint of \(L\), and determine whether or not \(L\) is self-adjoint.
3. Find the nullspace of \(L\). Use Fredholm theory to characterize the set of functions \(f\) such that \(Lu=f\) has a solution. Verify that \(f=1\) satisfies your condition, and find an infinite set of solutions to the problem \(Lu=1\).

Define the operator \(K\) on \(L^2[0,1]\) by \[ Ku(x)=\int _0^1 k(x,y)u(y)\,dy, \] for \(x\in [0,1]\), where \(k(x,y)\) is a real-valued, bounded, continuous function, with \(k(x,y)>0\).

1. Find the \(L^2\) adjoint \(K^*\) for \(K\), and find a condition on \(k\) which guarantees that \(K\) is self-adjoint.
2. Describe the properties of the set \[ \{\lambda \in \mathbb {C}:(K-\lambda I)u=0\text { for some }u\ne 0\} \] (cardinality, bounds, etc..).
3. Consider the problem \(Ku=f\). Let \(X\) be the set of all \(f\in L^2[0,1]\) such that a unique solution \(u=K^{-1}f\) exists. Can we be assured that there is a constant \(C\) such that \(\lVert K^{-1}f\rVert \le C\lVert f\rVert \), for all \(f\in X\)? Why or why not?

Let \(f(x)=|x|-1\) on the interval \([-1,1]\).

1. Treating \(f\) as a distribution, calculate \[ \int _{-1}^{1} f'(x)f'(x)\,dx \quad \text {and}\quad \int _{-1}^{1} f(x)f''(x)\,dx. \]
2. Explain why \[ \int _{-1}^{1} f'(x)f''(x)\,dx \quad \text {and}\quad \int _{-1}^{1} f(x)f'''(x)\,dx \] do not make sense.
3. In general, what property is required of \(g(x)\) so that \[ \int _{-1}^{1} g(x)f^{(n)}(x)\,dx \] is well-defined for a given \(n\)th derivative?

Find the radius of convergence of the Taylor series for the function \[ \frac {1}{2+\cos x} \qquad (x\text { is a real variable}) \] around the origin (\(x_0=0\)). {You do not need to find the Taylor series itself.}

1. Show that any bilinear map takes circles into circles.
2. Find the image of the triangle \[ \{z=x+iy:\ x\ge 0,\ y\ge 0,\ x+y\le 1\} \] under the mapping \(w=1/z\).

Evaluate the integrals:

1. \[ I=\int _0^\infty \frac {\sin x}{x}\,dx, \]
2. \[ I=\int _0^\infty \frac {x^\alpha }{2+x}\,dx \qquad (-1<\alpha <1). \]

Formulate and derive the uncertainty principle. Is its inequality optimal? Explain.

Find the leading behavior, as \(s\to +\infty \), of the integral

1. \[ I=\int _0^3\frac {1}{\sqrt {x^2+2x}}e^{-sx}\,dx, \]
2. \[ I=\int _0^{\pi /2} e^{is\cos x}\,dx. \]

The \(n\) data points \((x_i,y_i)\), \(i=1,2,\ldots ,n\) are believed to lie on an exponential curve \[ y_i=A\exp (\lambda x_i). \] Estimate \(\lambda \).

1. Find all conditions on \(\alpha ,\beta ,\gamma \), and \(f(x)\) for which solutions of \[ u''+\alpha ^2u=f(x),\qquad u(0)=\beta ,\qquad \alpha u'(0)-u'(1)=\gamma \tag {1} \] exist.
2. Find an integral representation for the solution in the case that \(\alpha =0\).

Consider the integral equation \[ \phi (x)-\lambda \int _0^\pi \sin (x+t)\phi (t)\,dt=\cos (x)+\sin (x), \qquad 0\le x\le \pi . \]

1. Find the unique solution when \(\lambda \ne \pm 2/\pi \). Why is a unique solution guaranteed to exist?
2. Show that there is no solution when \(\lambda =2/\pi \).
3. Show that when \(\lambda =-2/\pi \) there is a one-parameter family of solutions of the form \[ \phi (x)=f_p(x)+\alpha f_h(x). \] Determine \(f_h(x)\).

1. Describe the Gram-Schmidt orthogonalization procedure for a set of \(n\)-vectors \(\{u_1,u_2,\ldots ,u_k\}\).
2. Suppose \(k<n\) and that the vectors \(\{u_1,u_2,\ldots ,u_k\}\) are linearly independent. Show that the Gram-Schmidt procedure is equivalent to factoring the matrix \(U\) with column vectors \(\{u_1,u_2,\ldots ,u_k\}\) as \(U=QR\) where \(R\) is triangular. What is the structure of \(Q\)?
3. Use this factorization of \(U\) to find the least-squares solution of \(Ux=b\).

1. Formulate and derive the argument principle [which determines the difference between the number of zeros \((N_0)\) and poles \((N_\infty )\) of an analytic function \(f(z)\)].
2. Applying this principle, determine the number of zeros located inside the first quadrant \(\{z=x+iy:\ x>0,\ y>0\}\) of the function \(f(z)=z^5+1\).

Find the image of the half-strip \[ \{z=x+iy:\ x>0,\ 0<y<1\} \] under the mapping \(w=1/z\).

Calculate the integral \[ I=\int _0^\infty \frac {x^\alpha }{1+x}\,dx, \] where \(\alpha \) is a real number for which the integral converges.

Formulate and derive the uncertainty principle. Is its inequality optimal?

Find at least three terms of the asymptotic expansion of the integral \[ I(s)=\int _0^1 \ln t\, e^{ist}\,dt, \qquad s\text { is real and }s\to +\infty . \]

Full rank matrix

Given \(A\in \mathbb {C}^{m\times n}\) with \(m\geq n\), show that \(A^*A\) is nonsingular if and only if \(A\) has full rank.

\(QR\) and Cholesky Factorizations

Let \(A\) be a nonsingular square matrix and let \(A=QR\) and \(A^*A=U^*U\) be the \(QR\) factorization of \(A\) and the Cholesky factorization of \(A^*A\), respectively. Assume that the usual normalizations \(r_{jj},u_{jj}>0\) are in effect. Is it true or false that \(R=U\)? Justify your answer.

Midpoint Rule

Derive error estimate for the midpoint rule in the form: \[ |E_n^M|\leq \frac {h^2(b-a)}{24} \max _{a\leq x\leq b}|f''(x)| \] Midpoint rule: \[ M_n(f)=h(f(x_1)+f(x_2)+\cdots +f(x_n)) \] where \(h=(b-a)/n\) and \[ x_j=a+\left (j-\frac {1}{2}\right )h,\qquad j=1,\ldots ,n \]

Spectral Radius

Let \(A\in \mathbb {C}^{m\times m}\) and \(\|\cdot \|\) denote any operator norm on \(m\times m\) matrices. Show that \[ \lim _{k\to \infty }\|A^k\|^{1/k}=\rho (A). \]

Interpolating Polynomial

Define \(l_{i,n}(x)\) - Lagrange basis functions with \(x_0,x_1,\ldots ,x_n\). Prove that for any \(n\geq 1\), \[ \sum _{i=0}^n l_{i,n}(x)=1 \] for all \(x\).

Linear Multistep Methods

Construct an example of:

a) a consistent but not stable (not zero-stable) linear multistep method

b) a stable (zero-stable) but not consistent linear multistep method

What kind of behavior do you expect from the numerical solution produced by the methods in a) and in b)?

Convergence of Linear Multistep Method

Consider the method \[ y_{n+2}-2y_{n+1}+y_n = \frac {h}{2}\left (f(t_{n+2},y_{n+2})-f(t_n,y_n)\right ) \] Apply the method to the scalar IVP \(y'=y\), \(y(0)=1\) and solve exactly the resulting difference equation, considering the starting values to be \(y_0=y_1=1\). Show theoretically that the numerical solution does not converge as \(h\to 0\) and \(n\to \infty \).

Stability of the Scheme

Using the von Neumann method investigate the stability of the implicit downwind scheme: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - \frac {u_m^{n+1}-u_{m-1}^{n+1}}{h} = f_m^n, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1. \]

Numerical Quadrature

Show that there is no set of nodes \(x_1,x_2,\ldots ,x_n\) and coefficients \(\alpha _1,\alpha _2,\ldots ,\alpha _n\) such that the quadrature rule \[ \sum _{j=1}^n \alpha _j f(x_j) \] exactly equals to the integral \(\int _a^b f(x)w(x)dx\) for all polynomials \(f(x)\) of degree less than or equal to \(2n\). \(w(x)\) is the weight function.

Existence and Uniqueness of the Interpolating Polynomial

State the theorem about the existence and uniqueness of the interpolating polynomial.

Give the proof. (You can consider any proof of your choice.)

Stability of the Scheme

Using the von Neumann method investigate the stability of the implicit upwind scheme: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - \frac {u_{m+1}^{n+1}-u_m^{n+1}}{h} = f_m^n, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1. \] Comment on the CFL condition for this scheme.

The Companion Matrix Show that \[ \begin {aligned} &\det \left ( \begin {bmatrix} \alpha _{n-1} & \alpha _{n-2} & \cdots & \alpha _1 & \alpha _0\\ 1 & 0 & \cdots & 0 & 0\\ 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end {bmatrix} - \lambda I \right ) \\ &\qquad = (-1)^n\left [\lambda ^n-\sum _{j=0}^{n-1}\alpha _j\lambda ^j\right ]. \end {aligned} \tag {1} \] Describe how this fact can be used to find the roots of a polynomial. Also briefly describe why the reverse process, finding the eigenvalues of a matrix by computing the characteristic polynomial, and finding its roots, is not generally viable.

Sherman-Morrison-Woodbury Formula Suppose \(A\) is an invertible \(n\times n\) matrix, and \(U\) and \(V\) are \(n\times k\) matrices such that \(A+UV^T\) and the \(k\times k\) matrix \(I+V^TA^{-1}U\) are invertible. Show that \[ (A+UV^T)^{-1} = A^{-1}-A^{-1}U(I+V^TA^{-1}U)^{-1}V^TA^{-1} \tag {2} \] Explain why this means that a rank \(k\) change of \(A\) leads to a rank \(k\) change of \(A^{-1}\).

SVD Let \(A\) be an \(m\times n\) matrix. Define what we mean by the singular value decomposition of \(A\). Show that the singular value decomposition exists.

The interpolant to symmetric data is symmetric Suppose you are given symmetric data \[ (x_i,y_i),\qquad i=-n,-n+1,\cdots ,n-1,n, \tag {3} \] such that \[ x_{-i}=-x_i,\qquad \text {and}\qquad y_{-i}=y_i\qquad i=0,1,\cdots ,n. \tag {4} \] What is the required degree of the interpolating polynomial \(p\)? Show that the interpolating polynomial is even, i.e., \[ p(x)=p(-x) \tag {5} \] for all real numbers \(x\).

Explicit Methods Define what we mean by Linear Multistep Method and what we mean by its region of absolute stability. Show that a convergent explicit linear multistep method cannot have an unbounded region of absolute stability.

Crank Nicolson Method Describe the Crank-Nicolson Method for the solution of the equation \[ u_t=u_{xx} \tag {6} \] and use the von Neumann method to examine its stability.

Local Truncation Error Consider the wave equation \[ u_{tt}=c^2u_{xx} \tag {7} \] and its discretization \[ x_m=mh,\qquad t_n=nk,\qquad U_m^n\approx u(x_m,t_n) \tag {8} \] and \[ U_m^{n+1}-2U_m^n+U_m^{n-1} = r\left (U_{m+1}^n-2U_m^n+U_{m-1}^n\right ) \tag {9} \] where \(r=c^2k^2/h^2\) is the grid constant. For the purposes of this problem, ignore the issues of initial and boundary conditions. Compute the local truncation error of (9) and show that there is a value of \(r\) for which the local truncation error is exactly zero. Give a physical interpretation of this fact.

1. State and prove the Fredholm Alternative Theorem for a linear transformation \(A:\mathbb {R}^n\to \mathbb {R}^m\).
2. Find and give a graphical interpretation of the pseudo-inverse of the matrix \[ A= \begin {pmatrix} 1 & 1\\ 2 & 2 \end {pmatrix}. \]

This problem examines features of the differential operator \[ Lu=u'' \] subject to boundary conditions \(u(-1)+u(1)=0\) and \(u'(-1)=u'(1)\).

1. What is the adjoint of this operator? Is it self-adjoint?
2. What is the nullspace of the operator and what is the nullspace of the adjoint operator?
3. Under what conditions on \(f\), \(a\), and \(b\) does the boundary value problem \[ u''=f,\qquad u(-1)+u(1)=a,\qquad u'(-1)-u'(1)=b \] have a solution?
4. Find the smallest least squares solution for the boundary value problem \[ u''=1,\qquad u(-1)+u(1)=1,\qquad u'(-1)-u'(1)=1. \] What equation does this least squares solution satisfy?

1. Find all the eigenvalues and eigenfunctions for the operator \[ (Lu)(x)=\int _0^1 xyu(y)\,dy. \]
2. Do these eigenfunctions form a complete set? If so, how do you know (state a relevant theorem) and on what Hilbert space, and if not, why not?

1. Find the weak formulation for the boundary value problem \[ u''-\delta (x)u=1 \] subject to boundary conditions \(u(-1)=u(1)=0\).
2. Find the solution to this boundary value problem.

Let \(P_n(x)\), \(n=0,1,\cdots \), be the Legendre polynomials, \[ P_n(x)=\frac {1}{2^n n!}\frac {d^n}{dx^n}(x^2-1)^n, \] which are also eigenfunctions for the linear differential operator \[ Lu=-\frac {d}{dx}\left ((1-x^2)\frac {du}{dx}\right ) \] on the interval \(-1\le x\le 1\).

1. Determine the eigenvalue associated with \(P_n\)
2. Show that the Legendre polynomials are orthogonal.
3. Suppose \(f(x)\) is square integrable on the interval \(-1<x<1\). Use that the Legendre polynomials are orthogonal to prove that \[ g(x)=\sum _{n=0}^{\infty }\alpha _nP_n(x) \] where \[ \alpha _n= \frac {\int _{-1}^{1}f(x)P_n(x)\,dx}{\int _{-1}^{1}P_n^2(x)\,dx}, \] is also square integrable.

For a function \(f(z)\) which is analytic within a simple, nonintersecting, closed curve \(C\) a corollary of the Cauchy integral formula implies that for any point \(z\) inside \(C\), \[ f'(z)=\frac {1}{2\pi i}\int _C\frac {f(\xi )}{(\xi -z)^2}\,d\xi . \] Use this to prove Liouville’s theorem that any function which is bounded and analytic in the entire complex plane must be a constant, and hence prove the fundamental theorem of algebra that an \(n\)th order polynomial \(P_n(z)\) has \(n\) roots (counting multiplicity) in the complex plane.

The fourth quadrant \(x\ge 0\), \(y\le 0\) is occupied by an impermeable solid, around which air flows. Treating the flow as incompressible and irrotational use conformal mapping to map to a simpler problem and give one non-trivial solution for the complex potential \(f(z)\) in the original coordinates. Find the equation in polar coordinates for the streamline passing through \(z=-1\). What happens to the fluid velocity as one approaches the corner?

Use antiderivatives to evaluate the contour integral \[ I=\int _C\frac {1}{z+i} \] where \(C\) is a contour (possibly with loops) starting at \(z=0\) and ending at \(z=1\). Express your answer in the form \(I=a+ib\) where \(a\) and \(b\) are real. The answer is multivalued. Explain the interpretation of the different values, and account for the difference between successive values using the residue theorem.

The operator \(Lu=-u''\) on \(L^2(-\infty ,\infty )\) has a Green’s function defined by \(-G''-\lambda G=\delta (x-\xi )\) given by \[ G(x,\xi ;\lambda )=-\frac {e^{i\sqrt {\lambda }|x-\xi |}}{2i\sqrt {\lambda }}. \] Assume the representation \[ -\frac {1}{2\pi i}\int _{C_\infty }G(x,\xi ;\lambda )\,d\lambda =\delta (x-\xi ) \] and show how it leads to the Fourier Transform Theorem that \[ f(x)=\frac {1}{2\pi }\int _{-\infty }^{\infty }e^{-i\mu x}F(\mu )\,d\mu , \qquad F(\mu )=\int _{-\infty }^{\infty }e^{i\mu x}f(x)\,dx. \]

Use the method of steepest descent to estimate the integral \[ I(s)=\int _0^1 e^{s(-z^3+iz^3)}\,dz \] for large positive real values of \(s\).

Iterative Methods for Linear Systems

Consider the boundary value problem \[ -u''(x)+\beta u(x)=f(x),\qquad \text {for } 0\leq x\leq 1 \] where \(\beta >0\), and with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+(2+\beta h^2)U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\), \(F_j\equiv h^2f(jh)\), and \(U_0=U_N=0\).

Analyze the convergence properties of the Jacobi iterative method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor \(\delta \) depend on \(h\)? In practice, would you use this method to solve the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?

Elliptic Problems:

Consider the standard five-point difference approximation (centered difference for both the gradient and divergence operators) for the variable coefficient Poisson equation \[ -\nabla \cdot (a\nabla v)=f \] with Dirichlet boundary conditions, in a two-dimensional rectangular region. We assume that \(a(x,y)\geq a_0>0\). The approximate solution \(\{u_{i,j}\}\) satisfies a linear system \(Au=b\).

1. State and prove the maximum principle for the numerical solution \(u_{i,j}\).

2. Derive the matrix \(A\) in the one-dimensional case and show that it is symmetric and positive definite.

3. For the one-dimensional and constant-coefficient case, show that the global error \(e_j=v(x_j)-u_j\) satisfies \(\|e\|_2=O(h^2)\) as the space step \(h\to 0\).

4. Discuss the advantages and disadvantages of trying to solve the system for the two-dimensional problem using (i) the SOR (Successive Over Relaxation) method and (ii) the (preconditioned) Conjugate Gradient method.

Let \[ A= \begin {pmatrix} 2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2 \end {pmatrix}. \]

1. Find the eigenvalues and eigenvectors of \(A\), and the range of the function \[ \phi (x)=\frac {\langle Ax,x\rangle }{\langle x,x\rangle } \] where \(x=(x_1,x_2,x_3)\) is a real-valued vector.
2. Compute \(\exp (A)\).
3. Consider the equation \[ Ax=\mu x \] Find all solutions for \(\mu =1\) and for \(\mu =3\).

Consider linear operator \[ H=-\frac {d^2}{dx^2}, \] acting on \(\psi (x)\in L^2[0,\pi ]\) with periodic boundary conditions \(\psi (0)=\psi (\pi )=0\). Find the eigenvalues and eigenfunctions of \(H\). Show that the eigenvectors of \(H\) corresponding to distinct eigenvalues are orthogonal. Are the eigenvectors of \(H\) complete, and if so, in what sense?

(b) Solve the equation \[ H\psi (x)=x^2, \] representing the solution as an expansion in eigenfunctions of \(H\).

Let \[ f(x)= \begin {cases} \frac {100}{n}, & x\ \text {rational},\ x=\frac {m}{n},\\ -2, & x\ \text {irrational}. \end {cases} \] Does the Riemann integral of \(f(x)\) over the interval \([-1,1]\) exist? If so, compute it.

Does the Lebesgue integral of \(f(x)\) over the interval \([-1,1]\) exist? If so, compute it.

Why is the Lebesgue integral used in defining the Hilbert space \(L^2[0,1]\), and not the Riemann integral?

Let \[ f(x)=\operatorname {signum}(x)= \begin {cases} 1, & x>0,\\ 0, & x=0,\\ -1, & x<0. \end {cases} \]

1. Find its first and second derivatives using the theory of distributions.
2. Compute \[ \begin {aligned} I_0&=\int _{-1}^{\infty }\log (x+10)f(x)\,dx,\\ I_1&=\int _{-1}^{\infty }\log (x+10)f'(x)\,dx,\\ I_2&=\int _{-1}^{\infty }\log (x+10)f''(x)\,dx. \end {aligned} \]

Using Green’s functions, solve the problem \[ \frac {d^2u}{dx^2}=\frac {1}{1+x^2},\qquad u(-1)=u(1)=0 \] for \(u(x)\), \(x\in [-1,1]\) (obtain an integral representation for the solution, but do not evaluate the integral).

Find a solution \(u(x,y)\) of Laplace’s equation on the domain \(-\infty <x<\infty \), \(0<y<\infty \) for which \(u(x,0)=x^{1/2}\) for \(0<x<\infty \). What is \(u(x,0)\) for \(-\infty <x<0\)?

Use Jordan’s Lemma (and describe how Jordan’s Lemma is used) to evaluate the integral \[ I=\int _0^\infty \frac {\cos ax}{x^2+1}\,dx. \]

Use Fourier transforms to solve the integral equation \[ \int _{-\infty }^{\infty } k(x-y)u(y)\,dy-u(x)=f(x) \] with \(k(x)=H(x)\), the Heaviside function.

Use the \(z\)-transform to solve the system of equations \[ \frac {du_n}{dt}=\frac {1}{h^2}\left (u_{n+1}-2u_n+u_{n-1}\right ), \qquad -\infty <n<\infty \] with \(u_n(t=0)=\sin \frac {2\pi n}{k}\), with \(k\) an integer.

Find the leading order term of the asymptotic expansion of the integral \[ I(s)=\int _{-\infty }^{\infty } e^{is\left (t+\frac {t^3}{3}\right )}\,dt, \qquad s\text { is real and }s\to +\infty , \] as well as a rigorous estimate of the error.

Iterative Methods for Linear Systems

Consider the boundary value problem \[ -u''(x)+\beta u(x)=f(x),\qquad \text {for } 0\leq x\leq 1 \] where \(\beta >0\), and with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+(2+\beta h^2)U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\), \(F_j\equiv h^2f(jh)\), and \(U_0=U_N=0\).

Analyze the convergence properties of the Jacobi iterative method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor \(\delta \) depend on \(h\)? In practice, would you use this method to solve the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?

Elliptic Problems:

Consider the standard five-point difference approximation (centered difference for both the gradient and divergence operators) for the variable coefficient Poisson equation \[ -\nabla \cdot (a\nabla v)=f \] with Dirichlet boundary conditions, in a two-dimensional rectangular region. We assume that \(a(x,y)\geq a_0>0\). The approximate solution \(\{u_{i,j}\}\) satisfies a linear system \(Au=b\).

1. State and prove the maximum principle for the numerical solution \(u_{i,j}\).

2. Derive the matrix \(A\) in the one-dimensional case and show that it is symmetric and positive definite.

3. For the one-dimensional and constant-coefficient case, show that the global error \(e_j=v(x_j)-u_j\) satisfies \(\|e\|_2=O(h^2)\) as the space step \(h\to 0\).

4. Discuss the advantages and disadvantages of trying to solve the system for the two-dimensional problem using (i) the SOR (Successive Over Relaxation) method and (ii) the (preconditioned) Conjugate Gradient method.

1. Let \[ A= \begin {pmatrix} 3 & 1\\ 1 & 3 \end {pmatrix}. \] Find the maximum value of the quadratic form \(\langle Ax,x\rangle \) for \(\lVert x\rVert \le 1\).
2. Prove that eigenvectors corresponding to distinct eigenvalues of a self-adjoint matrix are orthogonal.
3. Let \(H=-\frac {d^2}{dx^2}\) on \(L^2[0,1]\) with boundary conditions \(\psi (0)=\psi (1)=0\). Find the eigenvalues and eigenvectors of \(H\). Show that the eigenvectors of \(H\) corresponding to distinct eigenvalues are orthogonal.

1. Define Cauchy sequence, and what it means for a linear space to be complete.
2. Let \(C[0,1]\) be the set of real-valued functions which are continuous on \([0,1]\). Show that \(C[0,1]\) is complete under under the uniform norm \(\lVert f\rVert =\sup _{x\in [0,1]}|f(x)|\).
3. Let \(f_n(x)=x^n\) for \(x\in [0,1]\). Find \(f=\lim _{n\to \infty }f_n\). Is \(f(x)\) continuous? Does this violate the completeness you showed in (a)? Explain.

Let \(T:\ell ^2\longrightarrow \ell ^2\) be defined by \(y=Tx\) with \(y_j=x_je^{-j}\) for \(j=1,2,3,\ldots \), where \(x=(x_1,x_2,\ldots )\) and \(y=(y_1,y_2,\ldots )\). Prove that \(T\) is a compact operator on \(\ell ^2\).

1. Let \(f(x)=|x|\). Find its first and second derivatives using operational calculus, that is, the theory of distributions.
2. Using Green’s functions, find the solution to \[ \frac {d^2u}{dx^2}=f(x),\qquad u(0)=u(1)=0. \] Use the reproducing property of the delta distribution to formally verify that your solution satisfies the equation.

Formulate and prove the Maximum Modulus Theorem.

Suppose \(f(z)\) is analytic in some neighborhood of the point \(z_0\) without the point \(z_0\) itself; let \(z_0\) be an essential singularity of \(f(z)\).

Show that for any complex number \(C\), there is a sequence of points \(z_n\) (\(n=0,1,2,\ldots \)) such that \[ z_n\to z_0\qquad \text {and}\qquad f(z_n)\to C. \] (In other words, in every neighborhood of an essential singularity, the function \(f(z)\) is arbitrary close to every complex number.)

Evaluate the integral \[ I=\int _{-\infty }^{+\infty } e^{iax^2}\,dx \] (\(a\) is a positive parameter).

Evaluate the integral \[ I=\int _0^\infty \frac {x^\alpha \,dx}{(x^2+1)} \] (where \(\alpha \) is a parameter, such that the integral converges).

Obtain the first two terms of the asymptotic expansion of \[ I(k)=\int _0^5 \frac {e^{-kt}}{\sqrt {t^2+2t}}\,dx, \qquad k\text { is real and } k\to +\infty . \]

Polynomial Interpolation Let \(I=[a,b]\), let \(x_i\), \(i=0,\ldots ,n\), be \(n+1\) distinct points in \(I\), and let \(y_i\), \(i=0,\ldots ,n\), be \(n+1\) given real numbers. Show that there exists a unique polynomial \[ p(x)=\sum _{i=0}^n \alpha _i x^i \] such that \[ p(x_i)=y_i,\qquad i=0,\ldots ,n. \]

Linear Programming Define the phrase “Linear Programming Problem”. Let \(A\) be a given \(m\times n\) matrix with \(m>n\), and let \(b\in \mathbb {R}^m\) be a given vector. Write the problem \[ \text {Find }x\in \mathbb {R}^n\quad \text {such that }\|Ax-b\|_\infty =\min \] as a linear programming problem.

The Gershgorin Theorem Let \(\lambda \) be an eigenvalue of \(A\in A^{n\times n}\). Show that there exists an \[ i\in \{1,2,\cdots ,n\} \tag {2} \] such that \[ |a_{ii}-\lambda |\leq \sum _{\substack {j=1\\ i\neq j}}^n |a_{ij}| \tag {3} \]

For every eigenvalue \(\lambda \), the inequality (3) describes a circle in the complex plane called a Gershgorin circle. Let \(S\) be a set that is the union of \(k\leq n\) Gershgorin circles such that the intersection of \(S\) with all other Gershgorin circles is empty. Show that \(S\) contains precisely \(k\) eigenvalues of \(A\) (counting multiplicities). Without proof or counterproof state whether it is possible for a Gershgorin Circle not to contain any eigenvalue at all.

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} \]

Numerical PDEs Consider the one-dimensional heat equation: Find \(u(x,t)\) such that \[ u_t=u_{xx},\qquad t\geq 0,\qquad x\in [0,1],\qquad u(x,0)=f(x),\qquad u(0,t)=u(1,t)=0. \] Describe how this problem might be solved by applying the Method of Lines and Euler’s Method. Give formulas that could be used to write a suitable computer code.

1. The least squares psuedo-inverse of \(A\) is a matrix \(B\) which satisfies what two properties?
2. Find the pseudoinverse of the matrix \[ A= \begin {pmatrix} 1 & 2\\ 1 & 2 \end {pmatrix}. \]

The Haar function \(\phi (x)\) is defined by \[ \phi (x)= \begin {cases} 1, & 0<x<1,\\ 0, & \text {elsewhere} \end {cases} \] and the mother Haar wavelet \(W(x)\) is defined by \[ W(x)= \begin {cases} 1, & 0<x<1/2,\\ -1, & 1/2<x<1,\\ 0, & \text {elsewhere}. \end {cases} \] Express the function \[ f(x)= \begin {cases} 2, & 0<x<1/4,\\ 0, & 1/4<x<1/2,\\ -1, & 1/2<x<3/4,\\ 1, & 3/4<x<1,\\ 0, & \text {elsewhere} \end {cases} \] as a linear combination of 4 orthogonal functions: the Haar function and 3 Haar wavelets \[ W_{mn}(x)=2^{m/2}W(2^mx-n), \] where \(m\) and \(n\) are appropriate integers.

1. Define what is meant by a precompact (or sequentially compact) set and what is meant by a compact linear operator, assuming linear operators and bounded sets have been already been defined.
2. If \(K\) is a compact linear operator and if \(\{\phi _n\}\) is an infinite set of orthonormal functions then (using Bessel’s inequality, if needed) show that \[ \lim _{n\to \infty }K\phi _n=0. \]

For the differential operator \(Lu=u''+(x^2-1)u'\) on the interval \([0,1]\) with boundary conditions \(u(0)=u'(1)\) and \(u(1)=u'(0)\) find the adjoint operator and its domain.

1. Write down the set of linear equations which if solved give the Green’s function for the operator \(Lu=d^3u/dx^3\) on the interval \([0,1]\) with boundary conditions \(u(0)=u'(0)=u(1)=0\). (There is no need to explicitly solve these equations).
2. Letting \(G(x,y)\) denote the Green’s function which solves (a), and using a particular solution of \(d^3u/dx^3=0\), find the general solution to \(d^3u/dx^3=f(x)\) on the interval \([0,1]\) with boundary conditions \(u(0)=u'(0)=0\) and \(u(1)=1\).

1. Verify that the real and imaginery parts of a complex analytic function satisfy Laplace’s equation.
2. Give an interpretation of the complex function \[ w(z)=z+\frac {a^2}{z} \] as a flow past some object. That is, determine the streamlines for this function. Where are the stagnation points?

1. Use contour integration to explicitly evaluate \[ f(a)=\int _0^\infty \frac {x\sin x\,dx}{x^2-a} \] for complex \(a\). For what values of complex \(a\) is this possible?
2. Is the function \(f(a)\) an analytic function of \(a\)? Identify all singularities, branch points, branch cuts, etc.

The windowed Fourier transform of a function \(f(x)\in L^2(-\infty ,\infty )\) is defined by \[ Gf(\omega ,\mu )=\int _{-\infty }^{\infty }g(x-\mu )f(x)e^{-\omega x}\,d\mu \,dx. \] Suppose \(g(x)\) is a real valued function. State and verify the formula for the reconstruction of \(f(x)\) from \(Gf\), including any additional conditions on \(g(x)\). You may assume the validity of the Fourier transform.

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.)

QR factorization Show how to compute the QR factorization of a real \(m\times n\) matrix \(A\) (with \(m\geq n\)) using Householder reflections, and describe how to use the QR factorization to solve the Least Squares problem \[ \|Ax-b\|_2=\min . \tag {1} \]

Gaussian Quadrature Let \(w\) be a positive weight function. Explain how to pick the knots \(x_i\) and the weights \(w_i\), \(i=1,\ldots ,n\) such that the integration formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n w_i f(x_i) \tag {2} \] is exact for polynomials \(f\) of degree as high as possible, and show why this works. How high a polynomial degree is possible?

Interpolation error Let \(I=[a,b]\) and \(f\in C^\infty [a,b]\). Let \(x_i\), \(i=0,\ldots ,n\) be \(n+1\) distinct points in \(I\). Let \(p(x)\) be the unique polynomial of degree at most \(n\) satisfying \(p(x_i)=f(x_i)\), \(i=0,\ldots ,n\). Given \(x\) in \([a,b]\), show that there exists some point \(\xi \in [a,b]\) such that \[ f(x)-p(x) = \frac {\prod _{i=0}^n(x-x_i)}{(n+1)!}\,f^{(n+1)}(\xi ). \tag {3} \]

Singular Value Decomposition Let \(A\) be an \(m\times n\) matrix. You may assume that \(m\geq n\). Define what is meant by the singular value decomposition of \(A\) and show that every \(m\times n\) matrix has one.

Absolute Stability Consider solving the initial value problem \[ y'=f(x,y),\qquad y(a)=y_0 \tag {4} \] by the linear multistep method (LMM) \[ \sum _{j=0}^k \alpha _j y_{n+j} = h\sum _{j=0}^k \beta _j f_{n+j}. \tag {5} \]

where we use the standard notation \[ x_n=a+nh,\qquad y_n\approx y(x_n),\qquad f_n=f(x_n,y_n). \tag {6} \] Define what it means that the LMM is explicit. Define its region of absolute stability. Show that an explicit linear multistep method cannot have an infinite region of absolute stability.

Convergence Consider the one-dimensional heat equation initial boundary value problem \[ u_t=u_{xx},\quad x\in [0,1],\quad t\geq 0,\quad u(x,0)=f(x),\quad u(0,t)=u(1,t)=0 \tag {7} \] and the discretization \[ x_m=mh,\qquad t_n=nk,\qquad \text {and}\qquad U_m^n\approx u(x_m,t_n) \tag {8} \] where \[ U_m^{n+1}=U_m^n+r\left (U_{m-1}^n-2U_m^n+U_{m+1}^n\right ) \tag {9} \] and \(r=k/h^2\) is the grid constant. Define what it means that this method is convergent, say for what values of \(r\) it is convergent, and show that your statement is correct.

Local Truncation Error Consider the wave equation \[ u_{tt}=c^2u_{xx} \tag {10} \] and its discretization \[ x_m=mh,\qquad t_n=nk,\qquad U_m^n\approx u(x_m,t_n) \tag {11} \] and \[ U_m^{n+1}-2U_m^n+U_m^{n-1} = r\left (U_{m+1}^n-2U_m^n+U_{m-1}^n\right ) \tag {12} \] where \(r=c^2k^2/h^2\) is the grid constant. For the purposes of this problem, ignore the issues of initial and boundary conditions. Compute the local truncation error of (12) and show that there is a value of \(r\) for which the local truncation error is exactly zero. Give a physical interpretation of this fact.

Find a singular value decomposition and pseudoinverse of the matrix \[ A= \begin {pmatrix} 1 & 1\\ 2 & 2\\ 0 & 0 \end {pmatrix}. \]

1. Explain what is meant by a Cauchy sequence, Completeness of a space, and a Hilbert space (you can assume the definitions of norm, inner product, and linear space are known).
2. Prove that the set of continuous functions on the interval \([a,b]\) is complete with respect to the uniform norm \[ \lVert f\rVert =\max _{x\in [a,b]} |f(x)|. \]

Prove that if a linear operator \(K\) can be approximated (in the operator norm) by a sequence of compact operators \(K_n\), with, \[ \lim _{n\to \infty }\lVert K_n-K\rVert =0, \] then \(K\) is a compact operator.

On the interval \([0,1]\) use eigenfunctions to find the resolvent of the integral equation \[ u(x)-\lambda \int _0^1 x^2y^2u(y)\,dy=f(x). \] When does a solution not exist? Write down the pseudoresolvent in this case.

1. Using Green’s functions, find the solution to the equation \[ u''=f(x),\qquad u(0)=0,\qquad u(1)=1. \]
2. Find the necessary and sufficient condition on \(f(x)\) for a solution to \[ u''+m^2\pi ^2u=f(x),\qquad u(0)=u(1)=0 \] to exist.

Find a solution \(u(x,y)\) of Laplace’s equation in 2 dimensions for which \(u(x,0)=|x|^{1/2}\).

Evaluate the integral \[ I=\int _0^\infty \frac {\cos ax}{(x+1)^2}\,dx. \]

Solve the integral equation \[ \int _{-\infty }^{\infty } k(x-y)u(y)\,dy-u(x)=f(x) \] with \(k(x)=H(x)\), the Heaviside function.

Solve the system of equations \[ \frac {du_n}{dt}=\frac {1}{h^2}\left (u_{n+1}-2u_n+u_{n-1}\right ), \qquad -\infty <n<\infty \] with \(u_n(t=0)=\sin \frac {2\pi n}{k}\), with \(k\) an integer.

Find the leading term of the asymptotic expansion of the integral \[ I(s)=\int _{-\infty }^{\infty } e^{is\left (t+\frac {t^3}{3}\right )}\,dt, \qquad s\text { is real and }s\to +\infty , \] as well as a rigorous estimate of the error.

Singular Value Decomposition Let \(A\) be a real \(m\times n\) matrix \((m>n)\) of full rank. We are interested in the singular value decomposition of \(A=U\Sigma V^T\). It is known that algorithms for SVD can be derived by turning the SVD problem into an eigenvalue problem. One such approach is to find the eigenvalue decomposition of the \((m+n)\times (m+n)\) symmetric matrix \[ \begin {bmatrix} 0 & A^T\\ A & 0 \end {bmatrix}. \] Establish the connections between the singular values, left and right singular vectors of \(A\) and the eigenvalues, eigenvectors of the above matrix. You should pay particular attention to the case \(m>n\). Comment on the advantages and disadvantages of this approach compared with an approach based on the eigendecomposition of \(A^TA\).

Elliptic Problems:

Consider the standard five-point difference approximation (centered difference for both the gradient and divergence operators) for the variable coefficient Poisson equation \[ -\nabla \cdot (a\nabla v)=f \] with Dirichlet boundary conditions, in a two-dimensional rectangular region. We assume that \(a(x,y)\geq a_0>0\). The approximate solution \(\{u_{i,j}\}\) satisfies a linear system \(Au=b\).

1. State and prove the maximum principle for the numerical solution \(u_{i,j}\).

2. Derive the matrix \(A\) in the one-dimensional case and show that it is symmetric and positive definite.

3. For the one-dimensional and constant-coefficient case, show that the global error \(e_j=v(x_j)-u_j\) satisfies \(\|e\|_2=O(h^2)\) as the space step \(h\to 0\).

4. Discuss the advantages and disadvantages of trying to solve the system for the two-dimensional problem using (i) the SOR (Successive Over Relaxation) method and (ii) the (preconditioned) Conjugate Gradient method.

Least Squares

Suppose \(A\in \mathbb {R}^{m\times n}\) has linearly independent columns, and \(C\in \mathbb {R}^{\ell \times n}\) has linearly independent rows. Let \(d\in \mathbb {R}^\ell \) and \(b\in \mathbb {R}^m\). Show how two full-rank QR factorizations can be used to solve the linearly constrained least squares problem: \[ \text {Find } x^*\in \{x\in \mathbb {R}^n:Cx=d\} \text { which minimizes } \|b-Ax^*\|_2. \]

ODEs

Consider the initial value problem for a system of ODEs \[ y'=Ay \] where \(A\) has eigenvalues with real parts ranging from \(-10^6\) to \(-1\). Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. Does your answer change depending on the size and condition number of \(A\)? Explain your answer. \[ y^{n+1}=y^n+kAy^n, \tag {1} \] \[ y^{n+1}=y^n+kAy^{n+1}, \tag {2} \] \[ y^{n+1}=y^n+\frac {k}{2}(Ay^n+Ay^{n+1}). \tag {3} \]

The dilation equation is \[ \phi (x)=\sum _k c_k\phi (2x-k) \] and the associated wavelet is \[ W(x)=\sum _k(-1)^k c_{1-k}\phi (2x-k). \]

1. Show that the function \[ N_2(x)= \begin {cases} x, & 0<x<1,\\ 2-x, & 1\le x<2,\\ 0, & \text {elsewhere} \end {cases} \] satisfies the dilation equation and determine the values of \(c_k\). Sketch the associated wavelet. Briefly explain whether or not \(N_2(x)\) can act as a scaling function for a multiresolution analysis?
2. Prove that if the functions \(\{\phi (x-k)\}_k\) form an orthonormal set then \[ \int _{-\infty }^{\infty }W(x)W(x-m)\,dx = \delta _{0,m}\int _{-\infty }^{\infty }\phi ^2(x)\,dx. \]
3. Prove that \[ \int _{-\infty }^{\infty } W(x)\phi (x-m)\,dx=0 \] for all \(m\).

1. Show that a test function \(\psi (x)\) is of the form \(\psi =(x\phi )'\) where \(\phi \) is a test function if and only if \[ \int _{-\infty }^{\infty }\psi (x)\,dx=0 \quad \text {and}\quad \int _0^{\infty }\psi (x)\,dx=0. \]
2. Solve the following equation in the sense of distribution: \[ x^2\frac {d\phi }{dx}=0. \]

Consider the integral equation \[ \phi (x)-\lambda \int _0^\pi \sin (x+t)\phi (t)\,dt = \cos (x)+\sin (x), \qquad 0\le x\le \pi . \]

1. Find the unique solution when \(\lambda \ne \pm 2/\pi \).
2. Use the Fredholm alternative theorem to show that there is no solution when \(\lambda =2/\pi \).
3. Use the Fredholm alternative theorem to show that when \(\lambda =-2/\pi \) there is a one-parameter family of solutions of the form \[ \phi (x)=\frac {\cos (x)+\sin (x)}{2}+\alpha (\cos (x)-\sin (x)). \]

1. By constructing the one-dimensional Green’s function solve the inhomogeneous equation \[ \frac {d^2u}{dx^2}=f(x),\qquad u(0)=\alpha ,\qquad u(1)=\beta . \]
2. Use Green’s functions to solve \[ \frac {d^2u}{dx^2}-\alpha ^2u=f(x)\quad \text {on }L^2(-\infty ,\infty ) \] with \(\alpha \) real.

Solve Laplace’s equation \(\Delta \phi =0\) in the domain between the two nonconcentric circles \(|z|=1\) and \(|z-1|=5/2\), subject to the boundary conditions \(\phi =a\) on \(|z|=1\) and \(\phi =b\) on \(|z-1|=5/2\).

Evaluate the integral \[ I=\int _0^\infty \frac {x^\alpha \,dx}{(x+1)^2} \] (where \(\alpha \) is a constant parameter, so that the integral converges).

Evaluate the integral \[ \int _{-\infty }^{\infty }\frac {\sin \alpha x}{x}\,dx \] (\(\alpha \) is a constant parameter). Explain your steps.

Find the two-term asymptotic expansion of the integral \[ I(s)=\int _{-\infty }^{\infty }\frac {e^{s(ix+1)^2}}{(x+i)^2}\,dx, \qquad s\text { is real and }s\to +\infty . \]

1. State the Riesz Representation Theorem (a proof is not required).
2. Use the Riesz Representation theorem to prove that a bounded linear operator on a Hilbert Space has an adjoint. Prove that the adjoint is a bounded linear operator on the Hilbert space.
3. Find the adjoint for the operator \[ (Ku)(y)=\int _0^1 \min (x,y)u(x)\,dx. \]

1. What is the weak formulation for the boundary value problem \(u''=f(x)\) subject to boundary conditions \(u(0)=u(1)=0\)?
2. Let \(\phi (x)=N_2(x+1)\) where \(N_2(x)\) is the piecewise linear function \[ N_2(x)= \begin {cases} x, & 0<x<1,\\ 2-x, & 1\le x<2,\\ 0, & \text {elsewhere}. \end {cases} \] Divide the unit interval \([0,1]\) into \(N\) uniform subintervals with endpoints at \(x_k=\frac {k}{N}\), \(k=0,\ldots ,N\). Use \(\phi (x)\) to define a finite element basis for continuous piecewise linear functions on the unit interval which interpolates function values at \(x_k\). Suppose \(u_k=u(x_k)\) is known. Express \(u(x)\) in terms of \(\phi (x)\).
3. Use the Galerkin method to find equations for \(u_k=u(x_k)\) that approximately solve the boundary value problem in part (a), using the piecewise linear finite element basis.

1. Find all conditions on \(\alpha \), \(\beta \), \(\gamma \), and \(f(x)\) for which solutions of \[ u''+\alpha ^2u=f(x),\qquad u(0)=\beta ,\qquad \alpha u'(0)-u'(1)=\gamma \] exist.
2. Find an integral representation for the solution in the case that \(\alpha =0\).

The \(n\) data points \((x_i,y_i)\), \(i=1,2,\ldots ,n\), are believed to lie on an exponential curve \(y_i=A\exp (\lambda x_i)\). Formulate a linear regression problem to estimate \(\lambda \).

The Legendre polynomials are given by \[ P_n(x)=\frac {1}{2^n n!}\frac {d^n}{dx^n}(x^2-1)^n, \] and are eigenfunctions of the differential operator \(Lu=-((1-x^2)u')'\) on the interval \(-1<x<1\).

1. Find the eigenvalue \(\lambda _n\) corresponding to the eigenfunction \(P_n(x)\).
2. In what sense, if any, are the functions \(\{P_n(x)\}\) complete?
3. Prove or disprove that \(L\) is a positive definite operator.

Evaluate the integral \[ \int _0^\infty \frac {\sin x}{x}\,dx. \] Explain your reasoning.

Solve the Laplace equation \(\Delta \phi =0\) subject to the boundary conditions: \[ \begin {aligned} \phi& =a &&\text {on } \{z: |z|=2,\ z\ne 2\},\\ \phi& =b &&\text {on } \{z: |z-1|=1,\ z\ne 2\}. \end {aligned} \] (\(a\) and \(b\) are real constants; \(z=x+iy\).)

Evaluate the integral \[ I=\int _0^\infty \frac {x^\alpha \,dx}{(x-1)^2+1}. \] (where \(\alpha \) is a constant, such that the integral converges: \(|\alpha |<1\)).

Find the two-term asymptotic expansion of the integral \[ I(s)=\int _0^3 \frac {e^{s(-t^2+4t-3)}}{5+t}\,dt, \] \(s\) is real, and \(s\to +\infty \).

Sensitivity Analysis

(a) Let \(X\in \mathbb {R}^{n\times n}\) such that \(\lVert X\rVert <1\) for some induced norm. Show that \(I-X\) is nonsingular and \[ \lVert (I-X)^{-1}\rVert \le \frac {1}{1-\lVert X\rVert }. \]

(b) Assume that \(A\in \mathbb {R}^{n\times n}\) is nonsingular, and the linear system \[ Ax=b \] is perturbed to \[ (A+\delta A)(x+\delta x)=b+\delta b, \] and the perturbations are small enough so that \[ \lVert \delta A\rVert \le \epsilon \lVert A\rVert ,\qquad \lVert \delta b\rVert \le \epsilon \lVert b\rVert , \] for some small \(\epsilon >0\), and \(\epsilon \kappa (A)=r<1\), where \(\kappa (A)\) is the condition number of \(A\). Show that \(A+\delta A\) is nonsingular.

(c) Let \(\tilde {x}=x+\delta x\), show that \[ \lVert \tilde {x}\rVert \le \frac {1+r}{1-r}\lVert x\rVert ; \] and \[ \frac {\lVert \delta x\rVert }{\lVert x\rVert } \le \frac {2\epsilon }{1-r}\kappa (A). \]

SVD Let \(A\) be a real \(m\times n\) matrix \((m\ge n)\) of full rank. We are interested in the singular value decomposition of \(A=U\Sigma V^T\). It is known that algorithms for SVD can be derived by turning the SVD problem into an eigenvalue problem. One such approach is to find the eigenvalue decomposition of the \((m+n)\times (m+n)\) symmetric matrix \[ \begin {bmatrix} 0 & A^T\\ A & 0 \end {bmatrix}. \] Establish the connections between the singular values, left and right singular vectors of \(A\) and the eigenvalues, eigenvectors of the above matrix. You should pay particular attention to the case \(m>n\). Comment on the advantages and disadvantages of this approach compared with an approach based on the eigendecomposition of \(A^T A\).

Numerical Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n \alpha _i f(\xi _i)+E, \] for the integral of \(f\) with a given positive weight function \(w(x)>0\). We would like to use \(n\) knot values \((f(\xi _i), i=1,\ldots ,n)\) to achieve the exact integral if \(f\) is a polynomial of degree up to \(2n-1\).

(a) Start from the special case \(a=-1\), \(b=1\) and \(w(x)=1\), define the orthogonal polynomials over \([-1,1]\).

(b) Use those orthogonal polynomials and polynomial division to simplify the integral. How would you pick the knots \(\xi _i\) and the weights \(\alpha _i\) such that the formula is exact (i.e., \(E=0\)) for all polynomials of degree up to \(2n-1\)? Verify that your choice works.

(c) Show that you can extend the approach to more general integrals, with arbitrary \(a<b\) and positive weight function \(w\).

ODE Consider the initial value problem for a system of ODEs \[ y'=Ay \] where \(A\) has eigenvalues ranging from \(-10^4\) to \(-1\). Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. \[ y^{n+1}=y^n+hAy^n, \tag {1} \] \[ y^{n+1}=y^n+hAy^{n+1}, \tag {2} \] \[ y^{n+1}=y^n+\frac {h}{2}(Ay^n+Ay^{n+1}). \tag {3} \]

Wave Equation For the PDE \(v_t+cv_x=0\), derive the Lax-Wendroff scheme \[ u_j^{n+1}=u_j^n -\frac {1}{2}\left (\frac {c\Delta t}{\Delta x}\right ) (u_{j+1}^n-u_{j-1}^n) +\frac {1}{2}\left (\frac {c\Delta t}{\Delta x}\right )^2 (u_{j-1}^n-2u_j^n+u_{j+1}^n). \] Analyze this scheme in terms of accuracy and stability. Does this scheme satisfy a maximum principle? If it does, explain why. If it does not, give an example to show this.

Convection-Diffusion Equation For the convection-diffusion equation \[ v_t+av_x=bv_{xx}, \] where \(a>0\) and \(b>0\), a natural Crank-Nicolson scheme is \[ \begin {aligned} \frac {u_j^{n+1}-u_j^n}{\Delta t} &+\frac {a}{2}\left ( \frac {u_{j+1}^n-u_{j-1}^n}{2\Delta x} +\frac {u_{j+1}^{n+1}-u_{j-1}^{n+1}}{2\Delta x} \right ) \\ &= \frac {b}{2}\left ( \frac {u_{j+1}^n-2u_j^n+u_{j-1}^n}{(\Delta x)^2} +\frac {u_{j+1}^{n+1}-2u_j^{n+1}+u_{j-1}^{n+1}}{(\Delta x)^2} \right ). \end {aligned} \] Let \(\nu =b\Delta t/(\Delta x)^2\) and \(\mu =a\Delta t/(2\Delta x)\). Show that the scheme is stable in the maximum norm if \(\mu \le \nu \le 1\). Also use Fourier analysis to derive the stability condition in the \(\ell _2\) norm and show that the scheme is always stable in the \(\ell _2\) norm. Suppose \(u\) stands for some volume fraction of a certain species, which norm is more appropriate? Explain why this scheme is so restrictive that it is not a good choice for many applications.

Ordinary Differential Equations Consider the initial value problem for a system of two ODEs \[ y'=Ay \] where \(A\) has eigenvalues \(-10^4\) and \(1\). Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. \[ y^{n+1}=y^n+hAy^n, \tag {1} \] \[ y^{n+1}=y^n+hAy^{n+1}, \tag {2} \] \[ y^{n+1}=y^n+\frac {h}{2}(Ay^n+Ay^{n+1}). \tag {3} \]

Wave Equation Consider the Lax-Friedrichs scheme below for the PDE \(v_t+cv_x=0\), where you may assume that \(c>0\): \[ u_j^{n+1}=\frac {1}{2}(u_{j-1}^n+u_{j+1}^n) -\frac {ck}{2h}(u_{j+1}^n-u_{j-1}^n), \] where \(h\) is the spacestep and \(k\) is the timestep. Note that the scheme can also be written \[ u_j^{n+1}=u_j^n-\frac {ck}{2h}(u_{j+1}^n-u_{j-1}^n) +\frac {1}{2}(u_{j-1}^n-2u_j^n+u_{j+1}^n). \]

a) Analyze the stability of this scheme in terms of \(\alpha =\frac {ck}{h}\).

b) Recall that a modified equation for a scheme is the PDE satisfied, to a certain order, by a smooth solution \(u(x,t)\) of the difference scheme. To zeroth order in \(k\) and \(h\), the modified equation for the Lax-Friedrichs scheme is \(u_t+cu_x=0\). Derive the modified equation through terms of first order in \(k\) and \(h\). You may assume that \(\alpha \) is constant. Does this modified equation predict the same stability condition as your analysis in part a)? Explain your answer. What does the modified equation suggest about the numerical solution that will be obtained for the step-function initial data \(u(x,0)=1\) for \(x\le 0\) and \(u(x,0)=0\) for \(x>0\)?

Iterative Methods Consider the fixed-point problem \(x=Tx+c\), where \(T\) is a real \(N\times N\) matrix and \(x\) and \(c\) are real \(N\)-vectors.

a) Show that the fixed point iteration \[ x^{(k+1)}=Tx^{(k)}+c \] converges for any choice of initial vector \(x^{(0)}\) if and only if the spectral radius of \(T\), \(\rho (T)\), satisfies \(\rho (T)<1\).

b) Consider the linear system \(Ax=b\) where \(A\) is a strictly diagonally dominant matrix, that is, \(a_{ii}>\sum _{j\ne i}\lvert a_{ij}\rvert \) for all \(i\), and strict inequality holds for at least one value of \(i\). Show that the Jacobi iterative scheme converges for this problem.

Interpolation and Integration

a) Consider equally spaced points \(x_j=a+jh\), \(j=0,\ldots ,J+1\) on the interval \([a,b]\), where \((J+1)h=b-a\). Let \(f(x)\) be a function defined on \([a,b]\). Consider the problem of finding a cubic spline approximation \(s(x)\) to \(f(x)\) that interpolates \(f\) at the points \(x_j\), is twice continuously differentiable, and satisfies \(s''(a)=s''(b)=0\). Does this problem always have a solution? If your answer is yes, derive formulas by which to determine the spline. If your answer is no, explain your reasoning.

b) Let \(I_n(f)\) denote the result of using the composite Trapezoidal rule to approximate \[ I(f)=\int _a^b f(x)\,dx \] using \(n\) equally sized subintervals of length \(h=(b-a)/n\). It can be shown that the integration error \(E_n(f)=I(f)-I_n(f)\) satisfies \[ E_n(f)=d_2h^2+d_4h^4+d_6h^6+\cdots \] where \(d_2,d_4,d_6,\ldots \) are numbers that depend only on the values of \(f\) and its derivatives at \(a\) and \(b\). Suppose you have a black-box program that, given \(f\), \(a\), \(b\), and \(n\) calculates \(I_n(f)\). Show how to use this program to obtain an \(O(h^4)\) approximation and an \(O(h^6)\) approximation to \(I(f)\).

Projectors Recall that a square matrix \(P\) that satisfies \(P^2=P\) is called a projector and that the subspaces \(\operatorname {range}(P)\) and \(\operatorname {null}(P)\) are complementary subspaces. Recall also that a projector \(P\) is an orthogonal projector if these two subspaces are perpendicular to one another, or equivalently, if \(P\) is Hermitian.

a) Let \(P\) be a nonzero projector. Show that \(\lVert P\rVert _2\ge 1\), with equality if and only if \(P\) is an orthogonal projector.

b) Given an \(m\times n\) matrix \(A\) \((m\ge n)\) with rank \(r\). Describe a stable algorithm for constructing an orthogonal projector onto \(\operatorname {range}(A)\). Why do you think your algorithm is stable?

Let \(A\in \mathbb {R}^{n\times m}\), \(B\in \mathbb {R}^{r\times m}\), and \(b\in \mathbb {R}^n\) be given. Assume \(R(B^*)=N(A)\). For fixed \(\mu \ge 0\), consider the problem \[ \min _{x\in \mathbb {R}^m} \|Ax-b\|_2^2+\mu \|Bx\|_2^2. \]

1. Find the necessary conditions (analogous to the normal equations for the standard least-squares problem) and prove that the necessary conditions have a solution when \(\mu =0\).
2. Prove that the necessary conditions have a unique solution if \(\mu >0\).

Consider the distribution \(g\) defined by \(\langle g,\phi \rangle =\int _{-\infty }^{\infty } e^{-|x|}\phi (x)\,dx\), for all test functions \(\phi \).

1. Calculate the second derivative \(g''\) explicitly. Prove \(g''\) is a distribution of order zero.
2. Find a differential equation for which \(g\) is a Green’s function.

Let \(K:H\to H\) be a compact linear operator on the infinite-dimensional Hilbert space \(H\).

1. Prove that \(K^{-1}\), if it exists, is not bounded.
2. Given \(T>0\), let \(H=L^2(0,T)\). For \(u\in H\), define \[ (Ku)(t)=\int _0^T e^{-st}u(s)\,ds,\qquad 0\le t\le T. \] Prove that \(K:H\to H\) is a compact operator. What are the consequences of this fact for the utility of the Laplace transform as a numerical method?

Consider the fourth-order differential equation \[ \begin {aligned} u^{(4)} &= f, && \text {on } (0,1),\\ u(0) &= u(1), && u'(0)=u'(1),\\ u''(1) &= -2, && u^{(3)}(1)=1. \end {aligned} \]

1. Find the least restrictive constraint(s) on \(f\in L^2(0,1)\) under which a solution to the problem exists.
2. With fixed \(f\) chosen such that a solution exists, is the solution unique? If the solution is unique, prove it. Otherwise provide a counterexample.

Prove that the nonlinear integral equation \[ u(x)-\int _0^1 \frac {u^2(y)}{4+x^2-y}\,dy=\frac {x^3}{3},\qquad 0\le x\le 1, \] has exactly one continuous solution \(u\) satisfying \(\max _{0\le x\le 1}|u(x)|\le 1\). Describe, but do not carry out, an iterative procedure for obtaining an approximation to this solution.

Use contour integration to show that \[ \int _0^\infty \frac {x^\alpha }{(1+x)^2}\,dx=\frac {\pi \alpha }{\sin \pi \alpha } \] where \(0<\alpha <1\).

Consider the wave equation \[ \frac {\partial ^2\phi }{\partial t^2}=\frac {\partial ^2\phi }{\partial x^2}, \qquad 0\le x\le l \] with the following boundary conditions \[ \begin {gathered} \phi (x,0)=0,\qquad \frac {\partial \phi }{\partial t}(x,0)=0,\\ \phi (0,t)=0,\qquad \phi (l,t)=f(t). \end {gathered} \]

1. Show that the Laplace transform of the solution \(\widehat {\Phi }(x,s)\) is given by \[ \widehat {\Phi }(x,s)=\frac {\widehat {F}(s)\sinh sx}{\sinh sl} \] where \(\widehat {F}(s)\) is the Laplace transform of \(f(t)\).
2. Suppose that \(\phi _0(x,t)\) is the solution when \(f(t)=1\). Show that the solution for general \(f\) is given by \[ \phi (x,t)=\int _0^t \frac {\partial \phi _0}{\partial t'}(x,t')f(t-t')\,dt'. \]

Discuss the flow pattern associated with the complex potential \[ \Omega (z)=Q_0z+\frac {\overline {Q_0}a^2}{z}+\frac {i\gamma }{2\pi }\log z \] with \(a>0\), \(\gamma \) real and \(Q_0=U_0+iV_0\). Sketch the flow when \(\gamma =0\). Given that the complex force on a cylindrical obstacle with boundary \(C\) is \[ \overline {F}=\frac {1}{2}i\rho \int _C\left (\frac {d\Omega }{dz}\right )^2\,dz, \] where \(\rho \) is the density of fluid, determine the lift when \(\gamma \ne 0\).

Suppose that \(\psi _+(z)\) is analytic on the upper half plane and \(\psi _-(z)\) is analytic on the lower half plane such that on the real axis \[ \psi _+(x)-\psi _-(x)=f(x) \] Assuming that the integrable function \(f(x)\) can be analytically extended in a neighborhood of the real axis, show that a solution to this problem is given by the Cauchy integral \[ \Psi (z)=\frac {1}{2\pi i}\int _{-\infty }^{\infty }\frac {f(\xi )}{\xi -z}\,d\xi \] with \(\psi _\pm (x)=\lim _{\epsilon \to 0+}\Psi (x\pm i\epsilon )\). Hence, establish that \[ \psi _+(x)+\psi _-(x)=\frac {1}{\pi i}\operatorname {PV} \int _{-\infty }^{\infty }\frac {f(\xi )}{\xi -x}\,d\xi \] where \(\operatorname {PV}\) denotes the principal value.

Sensitivity Analysis In this problem, we consider a real, non-singular \(n\times n\) matrix \(A\) and vectors \(b,x\in \mathbb {R}^n\). We are concerned with the error in solving the linear system \(Ax=b\). It turns out that the numerical solution \(\hat {x}\) is only an approximate solution to this equation. However, it satisfies a perturbed equation \(\hat {A}\hat {x}=b\) exactly, where \(\hat {A}=A+\delta A\). Let the error be defined as \(\delta x=\hat {x}-x\); we are interested in bounding \(\lVert \delta x\rVert \) in terms of \(\lVert \delta A\rVert \lVert A^{-1}\rVert \), or \(\lVert \delta A\rVert \lVert \hat {A}^{-1}\rVert \), and \(\lVert x\rVert \), or \(\lVert \hat {x}\rVert \), where \(\lVert \cdot \rVert \) is some suitable norm, and we proceed as follows:

a) First prove the identity \[ A^{-1}-\hat {A}^{-1}=A^{-1}\cdot \delta A\cdot \hat {A}^{-1}, \] and hence deduce that \[ \lVert A^{-1}-\hat {A}^{-1}\rVert \le \lVert A^{-1}\rVert \cdot \lVert \delta A\rVert \cdot \lVert \hat {A}^{-1}\rVert . \]

b) Assuming that \(\hat {\delta }=\lVert \delta A\rVert \lVert \hat {A}^{-1}\rVert <1\), show that \[ \lVert A^{-1}\rVert \le \frac {1}{1-\hat {\delta }}\lVert \hat {A}^{-1}\rVert ,\qquad \lVert A^{-1}-\hat {A}^{-1}\rVert \le \frac {\hat {\delta }}{1-\hat {\delta }}\lVert \hat {A}^{-1}\rVert . \]

c) By comparing the equations \(Ax=b\) and \((A+\delta A)(x+\delta x)=b\), show that \[ \lVert \delta x\rVert \le \frac {\hat {\delta }}{1-\hat {\delta }}\lVert \hat {x}\rVert . \] Similarly, show that if \(\delta =\lVert \delta A\rVert \lVert A^{-1}\rVert <1\), \[ \lVert \delta x\rVert \le \frac {\delta }{1-\delta }\lVert x\rVert . \]

Numerical ODEs

a) The difference equation \[ y_{n+k}+a_1y_{n+k-1}+\cdots +a_ky_n=0 \] can, after the substitution \(\mathbf {y}_j=(y_j,y_{j+1},\ldots ,y_{j+k-1})^T\), be written in the form \(\mathbf {y}_{n+1}=A\mathbf {y}_n\). What does the matrix \(A\) look like? Describe the condition for \(y\) to remain bounded in terms of \(A\).

b) The differential equation \[ y^{(k)}+a_1y^{(k-1)}+\cdots +a_ky=0 \] can, after the substitution \(\mathbf {y}=(y,y',\ldots ,y^{(k-1)})^T\), be written in the form \(\mathbf {y}'=A\mathbf {y}\). What does the matrix \(A\) look like? Describe the condition for \(y\) to remain bounded in terms of \(A\).

c) Show that all solutions of the difference equation \[ y_{n+1}-2\lambda y_n+y_{n-1}=0 \] are bounded, as \(n\to \infty \), if \(\lambda \) is real and \(\lvert \lambda \rvert <1\).

Sensitivity Analysis In this problem, we consider a real, non-singular \(n\times n\) matrix \(A\) and vectors \(f\), \(b\), \(x\in \mathbb {R}^n\).

a) (6%) First we consider the conditioning of matrix-vector multiplication \(f=Ax\), that is, find the smallest factor \(\kappa >0\) such that, when \(x\) is perturbed by any small \(\delta x\), the perturbation for \(f\) satisfies \[ \frac {\lVert \delta f\rVert }{\lVert f\rVert } \le \kappa \frac {\lVert \delta x\rVert }{\lVert x\rVert }. \] Here we assume no perturbation in matrix \(A\).

b) (8%) For the linear system \(Ax=b\), a numerical solution \(\hat {x}\) actually solves a slightly different problem due to roundoff errors: \[ (A+\delta A)\hat {x}=b+\delta b. \] If we denote \(\delta x=\hat {x}-x\), derive an upper bound for the relative error \[ E=\frac {\lVert \delta x\rVert }{\lVert x\rVert } \] in terms of the condition number of \(A\), \(\kappa (A)\), and the norms of \(A\), \(\delta A\), \(b\) and \(\delta b\), where \(\lVert \cdot \rVert \) is a suitable vector norm.

c) (6%) In practice, \(x\) is not available so \(\hat {x}\) is often used in the above bound to generate an approximate bound for \(\delta x\). Comment on this practice as what the advantages and disadvantages are, point out cases where this approximation may be inappropriate.

LS Problems and SVD Let \(A\) be a real \(m\times n\) matrix \((m>n)\) of full rank and let \(b\in \mathbb {R}^m\), the least square problem is to find \(x\in \mathbb {R}^n\) such that \[ \lVert Ax-b\rVert _2 \] is minimized.

a) (13%) Describe the following three approaches to solve the problem: 1) normal equations, 2) QR decomposition, and 3) singular value decomposition (SVD). Discuss briefly the advantages and disadvantages of each approach. In particular, give a geometric interpretation of the normal equation approach, and explain why it is often to be avoided.

b) (7%) In addition to minimizing the above norm, we impose the constraint: \(\lVert x\rVert _2\le \beta \), for some constant \(\beta >0\). This is a constrained LS problem. Use SVD to formulate and solve this problem, notice that there are different cases where a Lagrange multiplier may be needed.

Eigenvalue Problems

a) (8%) QR iteration can be viewed as an extension of the power method. We assume \(n\times n\) real symmetric, nonsingular matrix \(A\), with distinct eigenvalues. Here is the algorithm of orthogonal iteration for two linearly independent vectors \(z_1\) and \(z_2\), listed in an \(n\times 2\) matrix \(Z_0=[z_1,z_2]\):

\(i=0\)

repeat \[ \begin {aligned} Y_{i+1} &= AZ_i,\\ \text {QR Factor }Y_{i+1} &= Z_{i+1}R_{i+1},\\ i &= i+1 \end {aligned} \] until convergence

Notice that \(Y_i,Z_i\) are \(n\times 2\) matrices, and \(R_i\) is a \(2\times 2\) upper triangular matrix. Our assumptions allow us to write \(A=S\Lambda S^{-1}\), where \(\Lambda \) is a diagonal matrix containing all eigenvalues \(\lvert \lambda _1\rvert >\lvert \lambda _2\rvert >\cdots >\lvert \lambda _n\rvert \), \(S=[s_1,s_2,\ldots ,s_n]\) contains all the eigenvectors.

Show that \[ \operatorname {span}\{Z_{i+1}\} = \operatorname {span}\{Y_{i+1}\} = \operatorname {span}\{AZ_i\}, \] so \[ \operatorname {span}\{Z_i\} = \operatorname {span}\{A^iZ_0\} = \operatorname {span}\{S\Lambda ^iS^{-1}Z_0\}. \] Analyze it by writing \[ S\Lambda ^iS^{-1}Z_0=\lambda _2^i S D_i(S^{-1}Z_0). \] Derive the diagonal \(D_i\) and the \(n\times 2\) matrix \(Z'_0=S^{-1}Z_0\), find the limiting span of \(Z_i\) as \(i\to \infty \). How do we obtain the approximating eigenvalues \(\lambda _1,\lambda _2\) and approximating eigenvectors \(s_1\) and \(s_2\), once iterations are terminated?

b) (6%) Assume that we can continue this extension to \(n\) linearly independent vectors, contained in an \(n\times n\) nonsingular \(Z_0\); in particular when \(Z_0=I\), we will have the method of QR iteration. Describe the QR algorithm (without shift) and argue for the rate of convergence based on the analysis in part a).

c) (6%) To speed up convergence, we should use shifting. Describe the QR iteration with a shift, and make a suggestion as what shift should be used. How fast is the convergence?

Numerical ODEs

a) (8%) Consider the general system of ODEs for \(y(x)\in \mathbb {R}^n\), \(x\in \mathbb {R}\), and \[ f=[f_1(x,y),\ldots ,f_n(x,y)]^T: \qquad y'=f(x,y), \] where we assume \(f\) is continuously differentiable in both \(x\) and \(y\). To study local stability, we compare two solutions \(y_1(x)\) and \(y_2(x)\) where \(y_1(x_0)\approx y_2(x_0)\). Derive the linearized system for \(e(x)=y_1(x)-y_2(x)\) near \(x=x_0\) to show that \[ e'\approx Ae \] and find this square matrix \(A\). What is the most important property of \(A\) we need to find that will affect the choice of numerical schemes and step sizes?

b) (12%) Now consider the initial value problem \[ y''+2\mu y'+(1+\mu ^2)y=0, \] \[ y(0)=0,\qquad y'(0)=1, \] where \(\mu >0\) is a given constant. If we use a simple explicit Euler’s method, determine the maximum step size \(h\) that is allowed for the solution to be stable.

Convection-Diffusion Equation For the convection-diffusion equation \[ u_t+au_x=bu_{xx}, \] where \(a>0\) and \(b>0\), a natural Crank-Nicolson scheme is \[ \begin {aligned} \frac {U_j^{n+1}-U_j^n}{\Delta t} &+\frac {a}{2}\left ( \frac {U_{j+1}^n-U_{j-1}^n}{2\Delta x} + \frac {U_{j+1}^{n+1}-U_{j-1}^{n+1}}{2\Delta x} \right )\\ &= \frac {b}{2}\left ( \frac {U_{j+1}^n-2U_j^n+U_{j-1}^n}{(\Delta x)^2} + \frac {U_{j+1}^{n+1}-2U_j^{n+1}+U_{j-1}^{n+1}}{(\Delta x)^2} \right ). \end {aligned} \] Denote \(\nu =b\Delta t/(\Delta x)^2\) and \(\mu =a\Delta t/(2\Delta x)\); show that the scheme is stable in the max norm if \(\mu \le \nu \le 1\). Also use Fourier analysis to derive the stability condition in the \(\ell _2\) norm and show that the scheme is always stable in the \(\ell _2\) norm. Suppose \(u\) stands for some chemical concentration, which norm is more appropriate? Explain why this scheme is so restrictive that it is not often used.

The dilation equation is \[ \phi (x)=\sum _k c_k\phi (2x-k) \] and the associated wavelet is \[ W(x)=\sum _k (-1)^k c_{1-k}\phi (2x-k). \]

1. Show that the function \[ N_2(x)= \begin {cases} x, & 0<x<1,\\ 2-x, & 1\le x<2,\\ 0, & \text {elsewhere} \end {cases} \] satisfies the dilation equation and determine the values of \(c_k\)? Construct the associated wavelet.
2. Prove that if the functions \(\{\phi (x-k)\}_k\) form an orthonormal set then the functions \(\{2^{j/2}W(2^jx-k)\}_k\) form an orthonormal set for each fixed integer \(j\).

Consider a linear chain of \(2N\) atoms with the same spacing \(a\) and force constant \(\beta \) but of two different masses \(m,M\), \(M>m\), placed alternately. Label the light atoms by even integers \(2n\), \(n=0,\ldots ,N-1\) and the heavy atoms by odd integers \(2n-1\), \(n=1,\ldots ,N\). Denoting their displacements from equilibrium by the variables \(U_{2n}\) and \(V_{2n-1}\), Newton’s law of motion gives \[ \begin {aligned} m\ddot {U}_{2n} &= \beta [V_{2n-1}+V_{2n+1}-2U_{2n}],\\ M\ddot {V}_{2n-1} &= \beta [U_{2n}+U_{2n-2}-2V_{2n-1}]. \end {aligned} \] Determine the modes of vibration of the system and sketch the resulting pair of dispersion curves. [Assume periodic boundary conditions \(U_0=U_{2N}\) and \(V_1=V_{2N+1}\).]

Find the eigenvalues and eigenfunctions of the integral operator \[ (Ku)(x)=\int _0^1 k(x,y)u(y)\,dy \] where \[ k(x,y)=\min \{x,y\}. \] Solve the corresponding integral equation \[ u(x)-\lambda \int _0^1 k(x,y)u(y)\,dy=f(x) \] using the eigenfunctions of \(K\) assuming that \(\lambda \ne 1/a_n^2\) for any integer \(n\), where \(a_n=(2n+1)\pi /2\) (i.e. determine the resolvent operator). Write down the Fredholm alternative condition for \(f\) when \(\lambda =1/a_n^2\).

1. Prove that the eigenvalues of a self-adjoint linear operator acting in a Hilbert space \(H\) are real and that the eigenfunctions of distinct eigenvalues are orthogonal.
2. Prove that if \(L\) is a bounded linear operator in \(H\) then the adjoint \(L^*\) is also a bounded linear operator.

Construct the Green’s function for the equation \[ u''(x)+\alpha ^2u(x)=f(x),\qquad u(0)=u(1),\qquad u'(0)=u'(1) \] and express the solution in terms of the Green’s function. For what values of \(\alpha \) does the Green’s function fail to exist?

Show that \[ \int _0^\infty \frac {\cosh ax}{\cosh \pi x}\,dx=\frac {1}{2}\sec \left (\frac {a}{2}\right ), \qquad |a|<\pi \] Use a rectangular contour with corners at \(\pm R\) and \(\pm R+i\).

Obtain the inverse Laplace transform of the function \[ \widehat {F}(s)=s^{-a},\qquad 0<a<1 \] by evaluating the associated Bromwich contour integral with a branch cut along the negative real axis. Express the answer in terms of the gamma function \[ \Gamma (z)=\int _0^\infty t^{z-1}e^{-t}\,dt. \]

Consider the flow around a thin airfoil of length \(2a\) that is inclined at an angle \(\alpha \) to the \(x\)-axis. Assume that there is uniform flow at \(\infty \) with velocity \(U_x=U\), \(U_y=0\).

1. Show that the conformal map \[ z=\frac {ae^{-i\alpha }}{2}\left (\omega +\frac {1}{\omega }\right ) \] maps the unit circle in the \(\omega \)-plane to the airfoil in the \(z\)-plane.
2. Consider the complex potential \[ \Gamma (\omega )=\frac {aU}{2}\left (e^{-i\alpha }\omega +\frac {e^{i\alpha }}{\omega }\right ) -\frac {i\gamma }{2\pi }\log \omega . \] Calculate the corresponding potential \(\Omega (z)=\Gamma (\omega (z))\) where \(\omega (z)\) is the inverse of the conformal map in part (a). What does the term in \(\gamma \) represent?
3. Calculate \(\Omega '(z)\) and show that it satisfies the correct asymptotic flow. Determine what happens at the end points of the airfoil, and use this to calculate \(\gamma \).

Find the solution of Laplace’s equation on the circular domain \(0\le r\le R\), \(0\le \theta <2\pi \), with Dirichlet boundary data \(u(R,\theta )=f(\theta )\).

Liouville’s theorem states that a function analytic and bounded in the complex plane is necessarily a constant.

Prove this theorem. Using it prove the Fundamental theorem of algebra: Every polynomial \(P(z)\) which is not a constant has at least one complex root.

Householder Reflections A Householder Reflection \(H\) is an \(n\times n\) orthogonal matrix of the form \[ H=I-2uu^T \tag {1} \] where \[ \lVert u\rVert _2=1 \tag {2} \] and \(I\) is the \(n\times n\) identity matrix. Let \(a\in \mathbb {R}^n\) be a given (non-zero) vector. Show how to pick \(u\) in (1) such that \[ Ha=\lVert a\rVert _2 e_1 \tag {3} \] where \(e_1\) is the first unit vector. Describe how to use this technique to compute the \(QR\) factorization of an \(n\times n\) matrix \(A\).

Frobenius Norm The Frobenius Norm \(\lVert A\rVert _F\) of an \(n\times n\) matrix \(A\) is defined by \[ \lVert A\rVert _F= \sqrt {\sum _{i=1}^n\sum _{j=1}^n a_{ij}^2}. \tag {4} \] Let \(H=I-2uu^T\) be a Householder reflection as in the preceding problem and compute the Frobenius Norm of \(H\).

Gaussian Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n \alpha _i f(\xi _i)+E. \tag {5} \] \(w\) is a given positive weight function. How do you pick the knots \(\xi _i\) and the weights \(\alpha _i\) such that the formula is exact (i.e., \(E=0\)) for all polynomials of degree up to \(2n-1\)? Show that your choice works and that you can find suitable weights and knots for all intervals \([a,b]\) and positive weight functions \(w\).

Bernstein-Bezier Form Let \(T\) be a non-degenerate triangle with vertices \(V_1\), \(V_2\), and \(V_3\). The barycentric coordinates \(b_1\), \(b_2\), and \(b_3\) of a point \(x\in \mathbb {R}^2\) with respect to \(T\) are defined by \[ x=\sum _{i=1}^3 b_i V_i \qquad \text {where}\qquad \sum _{i=1}^3 b_i=1. \tag {6} \] A polynomial \(p\) of degree \(d\) can be written uniquely in its Bernstein-Bezier form as \[ p(x)=\sum _{i+j+k=d}\frac {d!}{i!j!k!}c_{ijk}b_1^i b_2^j b_3^k. \tag {7} \] Assuming you know the coefficients \(c_{ijk}\) of \(p\) as a polynomial of degree \(d\), show how to write \(p\) as a polynomial of degree \(d+1\) in Bernstein-Bezier form. What are the coefficients of \(p\) if \(p(x)=1\)?

Sensitivity Analysis Consider the (square, non-singular) linear system \[ Ax=b. \tag {8} \] Suppose you compute (by any method) a numerical solution \(\hat {x}\) and you are concerned about the relative error \[ E=\frac {\lVert x-\hat {x}\rVert }{\lVert x\rVert } \tag {9} \] where \(\lVert \cdot \rVert \) denotes a suitable vector norm. Derive upper and lower bounds on \(E\) in terms of the residual \(r=b-A\hat {x}\) and the condition number of \(A\) with respect to \(\lVert \cdot \rVert \).

ODEs Consider the initial value problem of ODEs: \[ y'=f(x,y),\qquad y(a)=y_0. \tag {10} \] Describe the Trapezoidal Rule applied to this problem and analyze its local accuracy and its region of absolute stability.

PDEs Consider the one-dimensional Heat Equation \[ u_t=u_{xx},\qquad t\ge 0,\qquad x\in [0,1],\qquad u(x,0)=f(x),\qquad u(0,t)=u(1,t)=0. \tag {11} \] Describe how to discretize this problem by applying the Method of Lines and the Backward Euler Method. Analyze the stability and local accuracy of your method.

1. Prove that \(x\delta (x)=0\) in the sense of distribution.
2. Formulate the differential equation \(xu'-u=0\) as a problem in the sense of distribution and find its general solution, also in the sense of distribution.

The \(n\) data points \((x_i,y_i)\), \(i=1,2,\ldots ,n\) are believed to lie on an exponential curve \(y_i=A\exp (\lambda x_i)\). Estimate \(\lambda \).

The Chebyshev functions are given by \(T_n(x)=\cos (n\cos ^{-1}x)\), and are eigenfunctions of the differential operator \[ Lu=-\sqrt {1-x^2}\left (\sqrt {1-x^2}u'\right )' \] on the interval \(-1<x<1\).

1. Find the eigenvalue \(\lambda _n\) corresponding to the eigenfunction \(T_n(x)\).
2. In what sense, if any, are the functions \(\{T_n(x)\}\) complete?
3. Prove or disprove that \(L\) is a positive definite operator.

The “best” least squares solution of the boundary value problem \(u''+u=0\), \(u(0)=\alpha \), \(u(\pi )=0\) is the unique exact solution of what problem?

Prove that if \(L\) is a bounded linear operator in a Hilbert Space \(H\), then the adjoint operator \(L^*\) exists.

1. Using Jordan’s lemma show that \[ \int _0^\infty \frac {\cos ax}{1+x^2}\,dx=\frac {\pi }{2}e^{-a}. \]
2. Show that \[ \int _0^{2\pi }\frac {d\theta }{A+B\sin \theta }= \frac {2\pi }{\sqrt {A^2-B^2}} \] where \(A^2>B^2\), \(A>0\).

Use contour integration to show that \[ \int _0^\infty \frac {x^\alpha }{(1+x)^2}\,dx=\frac {\pi \alpha }{\sin \pi \alpha } \] where \(|\operatorname {Re}\alpha |<1\).

Discuss the flow pattern around a circular obstacle associated with the complex potential \[ \Omega (z)=u_0\left (z+\frac {a^2}{z}\right )+\frac {i\gamma }{2\pi }\log z. \] Show that \(r=a\) is a streamline. Determine the asymptotic velocity when \(z\to \infty \). Calculate the stagnation points. Sketch the flow when \(\gamma =0\). Use the Blasius formula \[ F_x-iF_y=\frac {1}{2}i\rho \int _C\left (\frac {d\Omega }{dz}\right )^2\,dz \] to determine the lift on the obstacle when \(\gamma \ne 0\).

Use Fourier transforms to show that the solution of the diffusion equation \[ \frac {\partial \phi }{\partial t}=\frac {\partial ^2\phi }{\partial x^2},\qquad -\infty <x<\infty \] with initial data \(\phi (x,0)=h(x)\) takes the form \[ \phi (x,t)=\int _{-\infty }^{\infty } g(x-x',t)h(x')\,dx' \] where \[ g(x,t)=\frac {e^{-x^2/4Dt}}{2\sqrt {\pi Dt}}. \] Determine \(\lim _{t\to 0}g(x,t)\).

Consider the bilinear transformation \[ \omega =\frac {az+b}{cz+d},\qquad ad-bc\ne 0. \]

1. Show that this transformation maps circles to circles.
2. Show that the bilinear transformations form a group.
3. In the case \((a,b,c,d)=(1,-i,1,i)\) show that the upper-half plane is mapped on to the unit disc.

Newton’s Method Describe how (the two-variable version of) Newton’s Method can be used to solve the nonlinear system \[ \begin {aligned} x^2+y^2 &= 1,\\ e^x-y &= 0 \end {aligned} \tag {1} \] Discuss the selection of a starting point and the advantages and disadvantages of Newton’s method.

The \(QR\) factorization Describe the \(QR\) factorization of an \(m\times n\) matrix \(A\), how to compute it, and what it can be used for.

The QR Algorithm Outline the basic ingredients of the \(QR\) algorithm for solving eigenvalue problems.

The Singular Value Decomposition Define the term “singular value decomposition” and show that every \(m\times n\) matrix \(A\) has a singular value decomposition.

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.

Spline Spaces Let \(T\) be a triangulation of a domain \(\Omega \), and \(S\) the linear space of functions on \(T\) that are continuous on \(\Omega \) and that on each triangle in \(T\) can be written as a (bivariate) polynomial of degree \(d\). Derive the dimension of \(S\).

Numerical PDEs Consider the Initial-Boundary Value Problem \[ u_t=u_{xx},\qquad x\in [0,1],\qquad t\ge 0, \qquad u\text { given for }x=0,\ x=1,\text { and }t=0. \tag {4} \] Describe the Crank-Nicolson Method, and analyze its local truncation error and stability.

Ill Conditioning Define the condition number of a square matrix \(A\) and its significance for the solution of the linear system \[ Ax=b. \tag {5} \] Can you define a similar number that describes the conditioning of the eigenvalue problem \[ Ax=\lambda x? \tag {6} \]

Suppose that \(A\) is an \(n\times n\) matrix with \(n\) distinct eigenvalues.

1. How are the eigenvalues of \(A\) and \(A^*\) related?
2. Show that the eigenvectors of \(A\) and \(A^*\) form a biorthogonal set, that is, if \(\{\phi _i\}_{i=1}^n\) and \(\{\psi _i\}_{i=1}^n\) are the eigenvectors of \(A\) and \(A^*\), appropriately ordered, then \(\langle \phi _i,\psi _j\rangle =0\) if \(i\ne j\).
3. Establish that \(\langle \phi _i,\psi _i\rangle \ne 0\).

1. Determine the conditions on \(f(x)\), \(\alpha \) and \(\beta \) for which there solutions of \[ \frac {d^2u}{dx^2}=f(x),\qquad u(0)=\alpha ,\qquad u'(1)-u(1)=\beta . \]
2. Find the “best” solution of \[ \frac {d^2u}{dx^2}=1,\qquad u(0)=1,\qquad u'(1)-u(1)=1. \]

Consider the non-local differential operator \[ Lu=Du''-u(g(x)) \] with boundary conditions \(u(0)=u(1)=0\) and where \(g(x)\) is a monotone increasing function with \(g(0)=0\), \(g(1)=1\), and \(g(x)<x\) for \(0<x<1\).

1. Find the adjoint of the operator \(L\).
2. Prove that the operator \(L\) is invertible.
3. Devise an iteration scheme that could be used to solve \(Lu=f(x)\). Under what conditions on \(D\) is this iteration scheme a contraction mapping?

Use piecewise linear finite element basis functions with uniform grid size \(h\) and the Galerkin method to find an approximate representation for the differential equation \(a\frac {d^2u}{dx^2}+b\frac {du}{dx}+u(x)=f(x)\), with \(u(0)=0\), \(u(1)=0\), on the interval \([0,1]\). (It is only necessary to find the approximating equations, not to solve them.)

1. Evaluate the following real integrals by contour integration: \[ \int _0^{2\pi }\frac {d\theta }{(5-3\sin \theta )^2}. \]
2. Let \[ e^{t/2(z-1/z)}=\sum _{n=-\infty }^{\infty }J_n(t)z^n. \] Show from the definition of Laurent series and properties of complex integration that the Bessel function \[ J_n(t)=\frac {1}{\pi }\int _0^\pi \cos (n\theta -t\sin \theta )\,d\theta . \]

Discuss the flow pattern around a circular obstacle associated with the complex potential \[ \Omega (z)=u_0\left (z+\frac {a^2}{z}\right )+\frac {i\gamma }{2\pi }\log z. \] Show that \(r=a\) is a streamline. Determine the asymptotic velocity when \(z\to \infty \). Calculate the stagnation points. Sketch the flow when \(\gamma =0\). Use the Blasius formula \[ F_x-iF_y=\frac {1}{2}i\rho \int _C\left (\frac {d\Omega }{dz}\right )^2\,dz \] to determine the lift on the obstacle when \(\gamma \ne 0\).

Consider the bilinear transformation \[ \omega =\frac {az+b}{cz+d},\qquad ad-bc\ne 0. \]

1. Show that this transformation maps circles to circles.
2. Show that the bilinear transformations form a group.
3. In the case \((a,b,c,d)=(1,-i,1,i)\) show that the upper-half plane is mapped on to the unit disc.

Sensitivity Analysis For the linear system \(Ax=b\) where \(A\) is a square, real non-singular matrix, a numerical solution \(\hat {x}\) actually solves a slightly different problem due to roundoff errors: \[ (A+\delta A)\hat {x}=b+\delta b. \]

(a) If we denote \(\delta x=\hat {x}-x\), derive an upper bound for the relative error \[ E_1=\frac {\lVert \delta x\rVert }{\lVert \hat {x}\rVert } \] in terms of the condition number of \(A\), \(\kappa (A)\), and the norms of \(A,\hat {x},\delta A,\delta b\), where \(\lVert \cdot \rVert \) is a suitable vector norm.

(b) We can define another relative error \[ E_2=\frac {\lVert \delta x\rVert }{\lVert x\rVert }, \] based on the exact solution. Derive an upper bound for \(E_2\) in terms of \(\kappa (A)\) and the norms of \(\delta A,A,\delta b\) and \(b\).

(c) Strictly speaking, the relative error is given by \(E_2\), even though in many applications we simply use \(E_1\) since it is more readily available. Point out cases where this approximation may not be appropriate. Explain the significance of the condition number \(\kappa (A)\), and express the relative distance of \(A\) to its nearest singular matrix in terms of \(\kappa (A)\).

Linear Least Squares and Singular Value Decomposition Let \(A\) be a real \(m\times n\) matrix \((m>n)\) of full rank and let \(b\in \mathbb {R}^m\), the least square problem is to find \(x\in \mathbb {R}^n\) such that \[ \lVert Ax-b\rVert _2 \] is minimized.

Describe the following three approaches to solve the problem: 1) normal equations, 2) QR decomposition, and 3) singular value decomposition (SVD). Discuss briefly the advantages and disadvantages of each approach. In particular, give a geometric interpretation of the normal equation approach, and explain why it is often to be avoided. Characterize the difficulties in a rank-deficient least square problem and make a suggestion about which method you should use.

Eigenvalue Problems

(a) For the general eigenvalue problem of a nonsingular matrix \(A\), the simplest method is the power method, which converges to the largest eigenvalue in magnitude, assuming it is simple. The algorithm is the following:

\(i=0\)

repeat \[ \begin {aligned} y_{i+1} &= Ax_i,\\ x_{i+1} &= y_{i+1}/\lVert y_{i+1}\rVert _2,\\ \tilde {\lambda }_{i+1} &= x_{i+1}^T A x_{i+1},\\ i &= i+1 \end {aligned} \] until convergence

The inverse iteration algorithm takes advantage of the fact the if \(\sigma \) (the shift) is closest to one of the simple eigenvalues \(\lambda \), then \(1/(\lambda -\sigma )\) will be the largest eigenvalue in magnitude of the matrix \((A-\sigma I)^{-1}\). Use this fact to construct the inverse iteration algorithm. Note that we will not need to construct the explicit inverse of \(A-\sigma I\). How fast does it converge to the desired eigenvalue? When do you expect the convergence to be slow? How do we find the corresponding eigenvector?

(b) Now consider the symmetric eigenvalue problem where \(A\) is symmetric. What is the Rayleigh quotient? The Rayleigh quotient method is the inverse iteration algorithm described above applied to a symmetric matrix, when the shift is chosen to be the Rayleigh quotient \(\rho _i\) of \(A\) and the updated vector \(x_i\). Explain the rationale of choosing \(\rho _i\) to be the shift and determine the speed of convergence of \(\rho _i\) to \(\lambda \).

Numerical ODEs

(a) Consider the general system of ODEs for \(y(x)\in \mathbb {R}^n\), \(x\in \mathbb {R}\) and \(f=[f_1,\ldots ,f_n]^T\): \[ y'=f(x,y), \] where we assume \(f\) to be Lipschitz continuous. To study the numerical stability, we linearize \(f\) near \(x=x_0,y=y_0\) to obtain: \[ y'\approx f(x_0,y_0)+f_x(x_0,y_0)(x-x_0)+\nabla _y f(x_0,y_0)(y-y_0). \] If we denote \(A=\nabla _y f(x_0,y_0)\), then we claim that the local stability of the above system can be analyzed by studying the following constant coefficient system \[ y'=Ay. \] Justify this claim by analyzing the simple scalar equation \[ y'=a+bx+cy, \] where \(a,b,c\) are constants, in the explicit Euler’s method, to show that the stability is determined by how we solve \(y'=cy\). What is the most important property of \(A\) we need to find that will affect the choice of numerical schemes and step sizes?

(b) Now consider the initial value problem \[ y''+2\mu y'+(1+\mu ^2)y=0, \] \[ y(0)=0,\qquad y'(0)=1, \] where \(\mu >0\) is a given constant. If we use a simple explicit Euler’s method, determine the maximum step size \(h\) that is allowed for the solution to be stable.

Heat Equation Derive the Crank-Nicolson scheme for the following problem \[ u_t=u_{xx},\qquad t>0,\qquad 0<x<1, \] with the boundary conditions \[ u(0,t)=u(1,t)=0,\qquad t\ge 0, \] and the initial data \[ u(x,0)=u_0(x),\qquad 0\le x\le 1, \] for some given function \(u_0\). Use the usual discretization with uniform mesh points \(x_j=jh\) where \(h=1/N\) and \(j=0,1,2,\ldots ,N\). Show that the method is second order by deriving the truncation error. What other conditions do we need to guarantee the convergence of the numerical solution? Derive the stability condition in \(\ell _2\) norm by using Fourier analysis. For any value of \(\nu =\Delta t/(\Delta x)^2\), do we always have the maximum principle satisfied? If we have some initial data such that \(0\le u_0(x)\le 1\), derive the condition that should be imposed on \(\nu \) so that \(0\le u_j^n\le 1\) also holds for all \(j\) and \(n>0\).

Consider the error function \[ E(\mathbf {w})=\sum _{p=1}^{P}(y_p-\mathbf {w}\cdot \mathbf {x}_p)^2 \] where \(\mathbf {w}\) and \(\mathbf {x}_p\) are \(N\)-component vectors, \(N\ge P\), and \(y_p,\mathbf {x}_p\) are prescribed.

1. Show that if \(\mathbf {w}_0\) is a minimizer of \(E\) then \[ [X^TX]\mathbf {w}_0=X^T\mathbf {y} \] where \(X_{pj}=[\mathbf {x}_p]_j\), \(j=1,\ldots ,N\), \(X^T\) is the transpose of the matrix \(X\), and \(\mathbf {y}=(y_1,\ldots ,y_P)^T\).
2. Suppose that the weight vector \(\mathbf {w}\) is updated at each time step \(m\) using the gradient decent algorithm \[ w_j(m+1)=w_j(m)-\eta \frac {\partial E(\mathbf {w}(m))}{\partial w_j(m)}. \] Show that \(\mathbf {w}(m)\to \mathbf {w}_0\) as \(m\to \infty \) provided that the rate parameter \(\eta \) satisfies \[ |1-\eta \lambda _j|<1,\qquad j=1,\ldots ,N \] where \(\lambda _j\) are the eigenvalues of the symmetric \(N\times N\) matrix \(X^TX\). [Hint: Explicitly calculate \(\partial E/\partial w_j\), use part (a) to rewrite the difference equation in terms of \(\Delta \mathbf {w}(m)=\mathbf {w}(m)-\mathbf {w}_0\), and then diagonalize. Assume that \(X^TX\) is invertible so that \(\mathbf {w}_0\) is unique].

Consider a linear chain of \(2N\) atoms with the same spacing \(a\) and force constant \(\beta \) but of two different masses \(m,M\), \(M>m\), placed alternately. Label the light atoms by even integers \(2n\), \(n=0,\ldots ,N-1\) and the heavy atoms by odd integers \(2n-1\), \(n=1,\ldots ,N\). Denoting their displacements from equilibrium by the variables \(U_{2n}\) and \(V_{2n-1}\), Newton’s law of motion gives \[ \begin {aligned} m\ddot {U}_{2n} &= \beta [V_{2n-1}+V_{2n+1}-2U_{2n}],\\ M\ddot {V}_{2n-1} &= \beta [U_{2n}+U_{2n-2}-2V_{2n-1}]. \end {aligned} \] Determine the modes of vibration of the system and sketch the resulting pair of dispersion curves. [Assume periodic boundary conditions \(U_0=U_{2N}\) and \(V_1=V_{2N+1}\).]

Find the eigenvalues and eigenfunctions of the integral operator \[ (Ku)(x)=\int _0^1 k(x,y)u(y)\,dy \] where \[ k(x,y)= \begin {cases} x(1-y), & 0\le x<y\le 1,\\ y(1-x), & 0\le y<x\le 1. \end {cases} \] Solve the corresponding integral equation \[ u(x)-\lambda \int _0^1 k(x,y)u(y)\,dy=f(x) \] using the eigenfunctions of \(K\) assuming that \(\lambda \ne n^2\pi ^2\) for any integer \(n\) (i.e. determine the resolvent operator). Write down the Fredholm alternative condition for \(f\) when \(\lambda =m^2\pi ^2\) for some integer \(m\).

Suppose that the real scaling function \(\phi \) satisfies the dilation equation \[ \phi (x)=\sum _k c_k\phi (2x-k). \] Also assume that \(\{\phi (x-k),\, k\in \mathbb {Z}\}\) forms an orthonormal set with respect to the inner product \(\langle u,v\rangle =\int _{-\infty }^{\infty }u(x)v(x)\,dx\). Define the corresponding wavelet function according to \[ \psi (x)=\sum _k(-1)^k c_{1-k}\phi (2x-k). \]

1. Prove that \[ \sum _{k\in \mathbb {Z}} c_kc_{k-2p}=2\delta _{0,p}. \]
2. Show that \(\{2^{j/2}\psi (2^jx-k),\, k\in \mathbb {Z}\}\) forms an orthonormal set.
3. Briefly explain signal decomposition and reconstruction within the framework of multiresolution analysis.

Consider the differential operator \(Lu=u''+k^2u\), \(k\ne 0\), subject to homogeneous boundary conditions \(u(0)=u(1)=0\). Show by direct calculation that the associated Green’s function is \[ g(x,y)= \begin {cases} \dfrac {\sin kx\,\sin k(y-1)}{k\sin k}, & 0\le x<y\le 1,\\[1.2ex] \dfrac {\sin ky\,\sin k(x-1)}{k\sin k}, & 0\le y<x\le 1, \end {cases} \] provided \(\sin k\ne 0\). Using the fact that \(L\) is self-adjoint, show that the solution to the equation \[ u''(x)+k^2u(x)=f(x) \] with inhomogeneous boundary data \(u(0)=\alpha \), \(u(1)=\beta \) is \[ u(x)=\int _0^1 g(x,y)f(y)\,dy-\frac {\alpha }{\sin k}\sin k(x-1) +\frac {\beta }{\sin k}\sin kx \] provided \(\sin k\ne 0\). What happens when \(k=m\pi \)?

1. Using Jordan’s lemma show that \[ \int _0^\infty \frac {\cos ax}{1+x^2}\,dx=\frac {\pi }{2}e^{-a}. \]
2. Show that \[ \int _0^{2\pi }\frac {d\theta }{A+B\sin \theta }= \frac {2\pi }{\sqrt {A^2-B^2}} \] where \(A^2>B^2\), \(A>0\).

Use contour integration to show that \[ \int _0^\infty \frac {x^\alpha }{(1+x)^2}\,dx=\frac {\pi \alpha }{\sin \pi \alpha } \] where \(|\operatorname {Re}\alpha |<1\).

Discuss the flow pattern around a circular obstacle associated with the complex potential \[ \Omega (z)=u_0\left (z+\frac {a^2}{z}\right )+\frac {i\gamma }{2\pi }\log z. \] Show that \(r=a\) is a streamline. Determine the asymptotic velocity when \(z\to \infty \). Calculate the stagnation points. Sketch the flow when \(\gamma =0\). Use the Blasius formula \[ F_x-iF_y=\frac {1}{2}i\rho \int _C\left (\frac {d\Omega }{dz}\right )^2\,dz \] to determine the lift on the obstacle when \(\gamma \ne 0\).

Use Fourier transforms to show that the solution of the diffusion equation \[ \frac {\partial \phi }{\partial t}=\frac {\partial ^2\phi }{\partial x^2},\qquad -\infty <x<\infty \] with initial data \(\phi (x,0)=h(x)\) takes the form \[ \phi (x,t)=\int _{-\infty }^{\infty } g(x-x',t)h(x')\,dx' \] where \[ g(x,t)=\frac {e^{-x^2/4Dt}}{2\sqrt {\pi Dt}}. \] Determine \(\lim _{t\to 0}g(x,t)\).

Show that the conformal transformation \[ w=\frac {z-a}{z+a},\qquad a=\sqrt {c^2-\rho ^2} \] where \(0<\rho <c\), maps the domain bounded by the circle \(|z-c|=\rho \) and the imaginary axis onto an annular region centered about the origin with outer radius \(|w|=1\) and inner radius \(|w|=\delta \). Find the radius \(\delta \).

Numerical Methods for ODEs Consider the Linear Multistep Method \[ y_{n+2}-\frac {4}{3}y_{n+1}+\frac {1}{3}y_n=\frac {2}{3}hf_{n+2} \] for solving an initial value problem \(y'=f(y,x)\), \(y(0)=\eta \). You may assume that \(f\) is Lipschitz continuous with respect to \(y\) for all \(x\).

a) Analyze the consistency, stability, accuracy, and convergence properties of this method.

b) Would it be more reasonable to use this method or Euler’s method for the initial value problem: \[ y'=-10^8[y-\cos (x)]-\sin (x),\qquad y(0)=1? \] Justify your answer.

1. Describe the Gram-Schmidt orthogonalization procedure for a set of \(n\)-vectors \(\{u_1,u_2,\ldots ,u_k\}\).
2. Suppose \(k<n\) and that the vectors \(\{u_1,u_2,\ldots ,u_k\}\) are linearly independent. Show that the Gram-Schmidt procedure is equivalent to factoring the matrix \(U\) with column vectors \(\{u_1,u_2,\ldots ,u_k\}\) as \(U=QR\) where \(R\) is triangular. What is the structure of \(Q\)?
3. Use this factorization of \(U\) to find the least-squares solution of \(Ux=b\).

The dilation equation is \[ \phi (x)=\sum _k c_k\phi (2x-k). \] Show that the function \[ N_2(x)= \begin {cases} x, & 0<x<1,\\ 2-x, & 1\le x<2,\\ 0, & \text {elsewhere} \end {cases} \] satisfies the dilation equation. What are the values of \(c_k\)? Are the wavelets formed from \(N_2(x)\) an orthogonal set? Why or why not?

1. State the Riesz Representation Theorem.
2. Use the Riesz Representation theorem to prove that a bounded linear operator on a Hilbert Space has an adjoint. Prove that the adjoint is a bounded linear operator on the Hilbert space.
3. Find the adjoint for the operator \[ (Ku)(y)=\int _0^1 \min (x,y)u(x)\,dx. \]

1. What is the weak formulation for the boundary value problem \(u''=f(x)\) subject to boundary conditions \(u(0)=u(1)=0\)?
2. Let \(\phi (x)=N_2(x+1)\) where \(N_2(x)\) is the piecewise linear function given in Problem A.2. Divide the unit interval \([0,1]\) interval \(N\) uniform subintervals with endpoints at \(x_k=\frac {k}{N}\), \(k=0,\ldots ,N\). Use \(\phi (x)\) to define a finite element basis for continuous piecewise linear functions on the unit interval which interpolates function values at \(x_k\). Suppose \(u_k=u(x_k)\) is known. Express \(u(x)\) in terms of \(\phi (x)\).
3. Use the Galerkin method to find equations for \(u_k=u(x_k)\) that approximately solve the boundary value problem in part (a), using the piecewise linear finite element basis.

1. Find all conditions on \(\alpha \), \(\beta \), \(\gamma \), and \(f(x)\) for which solutions of \[ u''+\alpha ^2u=f(x),\qquad u(0)=\beta ,\qquad \alpha u'(0)-u'(1)=\gamma \] exist.
2. Find an integral representation for the solution in the case that \(\alpha =0\).

Evaluate \[ \int _0^\infty \frac {\sqrt {x}}{x^2+1}\,dx. \]

1. Derive the “diffusion” or “heat” equation in several spatial dimensions.
2. In the derivation of this equation, it is routinely assumed that \[ \frac {d}{dt}\int _\Omega u(x,t)\,dx=\int _\Omega \frac {\partial u}{\partial t}\,dx. \] Under what conditions is this interchange of order valid? Prove your result. Hint: Examine the function \[ w(t)=\int _0^t\left (\int _\Omega \frac {\partial u(x,t)}{\partial t}\,dx\right )\,dt. \]

Find an integral representation for the solution of the telegrapher’s equation \[ u_{tt}+au_t+bu=u_{xx} \] with \(u(0,t)=f(t)\) and \(u_x(0,t)=g(t)\) specified for all time.

1. Find the leading order behavior of \[ G(x)=\int _0^\infty \cos \left (x\left (\frac {t^3}{3}-t\right )\right )\,dt \] for large \(x\).
2. Outline the method to find more terms in the asymptotic expansion of \(G(x)\).

Useful information: \[ \int _{-\infty }^{\infty }\cos (ax^2)\,dx =\int _{-\infty }^{\infty }\sin (ax^2)\,dx =\sqrt {\frac {\pi }{2a}}. \]

Sensitivity Analysis Consider the linear system \(Ax=b\) where \(A\) is a square, non-singular matrix. A numerical solution \(\hat {x}\) actually satisfies \[ (A+\delta A)\hat {x}=b+\delta b. \] If we denote \(\delta x=\hat {x}-x\), derive an upper bound for the relative error \[ E_1=\frac {\lVert \delta x\rVert }{\lVert \hat {x}\rVert } \] in terms of the condition number of \(A\) and the norms of \(A,\hat {x},\delta A,\delta b\), where \(\lVert \cdot \rVert \) is a suitable vector norm. Also, we can define another relative error \[ E_2=\frac {\lVert \delta x\rVert }{\lVert x\rVert }. \] Derive an upper bound for \(E_2\) in terms of the condition number of \(A\) and the norms of \(\delta A,A,\delta b\) and \(b\). When are these two errors close to each bound? What’s the significance of the condition number?

Linear Least Squares Let \(A\) be a real \(m\times n\) matrix of full rank \((m>n)\) and let \(b\in \mathbb {R}^m\). The Least Square problem is to find \(x\in \mathbb {R}^n\) such that \[ \lVert Ax-b\rVert _2 \] is minimized.

Describe the following three approaches to solve the problem: 1) normal equations, 2) QR decomposition, and 3) Singular Value Decomposition (SVD). Discuss briefly the advantages and disadvantages of these approaches. In particular, give a geometric interpretation of the normal equation approach and explain why it is not often used?

Eigenvalue Problems Let \(\lambda \) be a simple eigenvalue of \(A\) (not necessarily symmetric), with right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Let \(\lambda +\delta \lambda \) be the corresponding eigenvalue of \(A+\delta A\).

a) Show that \[ \delta \lambda =\frac {y^*\delta A x}{y^*x}+O(\lVert \delta A\rVert ^2), \] and derive an upper bound for \(\lvert \delta \lambda \rvert \). What is the condition number for \(\lambda \) with respect to changes in \(A\)?

b) Consider the matrix \[ \begin {bmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ \epsilon & 0 & \cdots & 0 & 0 \end {bmatrix}. \] Compute \(d\lambda /d\epsilon \) and show that the condition number becomes infinite as \(\epsilon \) approaches zero.

c) Describe the power method for finding the eigenvalue of the largest absolute magnitude, and inverse iteration for the eigenvalue closest to a given value. How fast do you expect these algorithms to converge?

Singular Value Decomposition Define the singular value decomposition of a real \(m\times n\) matrix with \(m\ge n\). Is the SVD unique for a given matrix \(A\)? How is an SVD problem connected with an eigendecomposition of a symmetric matrix? Sketch the general structure of algorithms for those imported from eigendecomposition, namely, how do you reduce \(A\) to some form more manageable? How do you obtain the information about the rank of \(A\) through the SVD of \(A\)? If \(A\) is square and nonsingular, how does the SVD of \(A\) help you determine the sensitivity of the solution \(x\) for \(Ax=b\)?

Iterative Methods for Linear Systems Consider the linear system \(Ax=b\) and a splitting of \(A:A=M-K\), with \(M\) nonsingular, and the iteration \[ x_{m+1}=Rx_m+c, \] where \(R=M^{-1}K\) and \(c=M^{-1}b\). Show that the method converges for any \(x_0\) if \(\lVert R\rVert <1\) where \(\lVert \cdot \rVert \) is any operator norm.

Given an \((N-1)\times (N-1)\) \[ \setlength {\arraycolsep }{5pt} A= \begin {bmatrix} 2 & -1 & 0 & \cdots & 0\\ -1 & 2 & -1 & \ddots & 0\\ 0 & -1 & \ddots & \ddots & 0\\ \vdots & \ddots & -1 & 2 & -1\\ 0 & \cdots & 0 & -1 & 2 \end {bmatrix}, \qquad b=\frac {1}{N^2} \begin {pmatrix} f_1\\ f_2\\ \cdot \\ f_{N-2}\\ f_{N-1} \end {pmatrix}. \] Analyze the convergence properties of the Jacobi and Gauss-Seidel methods for this problem. For each method, express the convergence speed as a function of \(N\). How does the number of iterations required to reduce the initial error by a factor of \(\delta \) depend on \(N\) for each method?

Wave Equations Consider the wave equation in one space dimension: \[ u_t+au_x=0,\qquad -\infty <x<\infty ,\qquad t>0, \] with initial condition \[ u(x,0)=u_0(x). \] Consider the usual discretization \[ U_m^k\approx u(x_m,t_k) \] where \(x_m=m\Delta x\) and \(t_k=k\Delta t\). For an explicit scheme, what is the CFL condition? Give an intuitive explanation of the condition. Give the first-order upwind scheme for this equation and derive the truncation error.

Heat Equation Consider the following heat equation problem \[ u_t=u_{xx},\qquad t>0,\qquad 0<x<1, \] \[ u(0,t)=u(1,t)=0,\qquad t>0, \] \[ u(x,0)=u_0(x),\qquad 0\le x\le 1. \] Using the forward or backward difference for the time derivative and central difference for the space derivative, derive the explicit and implicit schemes. What’s the stability condition for each case? Perform a Fourier analysis on both the explicit and implicit methods and use the von Neumann condition to verify these stability conditions.

1. State the Singular Value Decomposition Theorem.
2. For any \(n\times m\) real matrices \(A\) and \(B\), show the \(\operatorname {Tr}(AB^*)=\operatorname {Tr}(BA^*)\).
3. Show that \(\lVert A\rVert =\sqrt {\operatorname {Tr}(AA^*)}\) is a norm.
4. Suppose \(A\) and \(B\) are \(n\times m\) real matrices. Find the orthogonal matrix \(Q\) that minimizes \(\lVert QA-B\rVert \) using the norm of part c.

Suppose the function \(\phi (x)\) is Lipschitz continuous on the unit interval \(0<x<2\pi \) and that \(\lim _{x\to 0}\phi (x)=\phi (0^+)\) exists. Suppose \(\int _0^\infty \frac {\sin x}{x}\,dx=\alpha \) is known. Evaluate \(\lim _{k\to \infty }\int _0^{2\pi }\phi (x)\frac {\sin kx}{x}\,dx\) (with \(k\) restricted to be integer-valued).

1. Show that the functions \(\{e^{inx}\}_{n=-\infty }^{\infty }\) form an orthogonal set in \(L^2[0,2\pi ]\).
2. Suppose \(f(x)\in L^2[0,2\pi ]\). Let \(\alpha _n=\int _0^{2\pi }f(x)e^{inx}\,dx\). Prove that \(\{\alpha _n\}_{n=-\infty }^{\infty }\) is convergent in \(\ell ^2\) and also that \(\sum _{n=-\infty }^{\infty }\alpha _ne^{inx}\) is convergent in \(L^2[0,2\pi ]\). What does \(\sum _{n=-\infty }^{\infty }\alpha _ne^{inx}\) converge to?
3. Suppose \(f(x)\) and \(g(x)\) are \(2\pi \) periodic functions and square integrable on the interval \(0<x<2\pi \). State and prove the Convolution Theorem for these functions, that is, find the Fourier coefficients of the function \(h(x)=\int _0^{2\pi } f(x-t)g(t)\,dt\) in terms of the Fourier coefficients of \(f(x)\) and \(g(x)\).

Under what conditions does a solution of the boundary value problem \(u''+u=f(x)\) with \(u(0)=\alpha \), \(u'(\pi /2)=\beta \) exist?

Find the representation of the delta function and the appropriate transform pair for the differential operator \(Lu=-u''\) on the interval \(0<x<\pi \) subject to boundary conditions \(u'(0)=0\), \(u(\pi )=0\).

Evaluate \[ \int _{-\infty }^{\infty }\frac {\sin x}{x}\,dx. \]

1. Find the Fourier transform of \(\dfrac {\sin x}{x}\).
2. Suppose that the Fourier transform of the function \(f(t)\) is 0 for frequencies whose absolute value is greater than \(\pi /h\). Find the representation of \(f(t)\) in terms of sinc functions.

Solve the discretized heat equation \(u_{nt}=\frac {1}{h^2}(u_{n+1}-2u_n+u_{n-1})\) with \(-\infty <n<\infty \) and initial data \(u_n(t=0)=\sin \frac {2\pi n}{k}\) where \(k\) is a fixed integer.

Suppose \(\Omega \) is some closed, bounded domain in two spatial dimensions.

1. Under what conditions does the equation \(\nabla ^2\phi =0\) in \(\Omega \), \(\mathbf {n}\cdot \nabla \phi =f\) on \(\partial \Omega \), have a solution? Is it unique?
2. Find an integral equation for \(\phi \) on the boundary \(\partial \Omega \). Be as explicit as possible.
3. Under what conditions does this integral equation have a solution?

Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=0}^n \alpha _i f(\xi _i)+E. \tag {1} \] \(w\) is a given positive weight function. The knots \(\xi _i\) and the weights \(\alpha _i\) are at your disposal. How do you choose them so that the error \(E\) is 0 for all polynomials \(f\) of degree as high as possible? How high is possible? Give reasons for your answers.

Spline Spaces Let \(T\) be a triangulation of a domain \(\Omega \), and \(S\) the linear space of functions on \(T\) that are continuous on \(\Omega \) and that on each triangle in \(T\) can be written as a (bivariate) polynomial of degree \(d\). Derive the dimension of \(S\)?

A Matrix Compute the eigenvalues and eigenvectors of the tridiagonal \(N\times N\) matrix \[ \setlength {\arraycolsep }{5pt} A= \begin {bmatrix} 2 & 1 & 0 & \cdots & 0 & 0\\ 1 & 2 & 1 & \cdots & 0 & 0\\ 0 & 1 & 2 & \ddots & 0 & 0\\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & \ddots & 2 & 1\\ 0 & 0 & 0 & \cdots & 1 & 2 \end {bmatrix}. \tag {2} \] Note that the diagonal entries are indeed meant to be positive 2, not -2.

Sensitivity Analysis Consider the (square, non-singular) linear system \[ Ax=b. \tag {3} \] Suppose you compute (by any method) a numerical solution \(\hat {x}\) and you are concerned about the relative error \[ E=\frac {\lVert x-\hat {x}\rVert }{\lVert x\rVert } \tag {4} \] where \(\lVert \cdot \rVert \) denotes a suitable vector norm. Derive upper and lower bounds on \(E\) in terms of the residual \(r=b-A\hat {x}\) and the condition number of \(A\) with respect to \(\lVert \cdot \rVert \).

Numerical PDEs Consider the PDE \[ u_t+u_x=0 \tag {5} \] and the usual discretization \[ U_m^n\approx u(x_m,t_n) \qquad \text {where}\qquad x_m=mh\quad \text {and}\quad t_n=nk. \tag {6} \] The Leap Frog Method is given by \[ U_m^{n+1}=U_m^{n-1}-\frac {k}{h}\left (U_{m+1}^n-U_{m-1}^n\right ). \tag {7} \] Compute the local truncation error and discuss the stability of this method.

Construct the Green function for the equation \[ -u''+u=f(x)\qquad (-\infty \le x\le +\infty ),\qquad u(x)\to 0\text { as }x\to \pm \infty . \]

Solve the differential equation in the sense of distributions \[ xu'=\delta (x^4-1),\qquad x\in [-2,2],\qquad u(-2)=u(2)=0. \] Discuss why two boundary conditions are provided for the first order differential equation.

Suppose that \(T\) is a transformation of a complete metric space \(X\), and \(T^n\) (for a certain positive integer \(n\)) is a contraction with fixed point \(a\). Show that

1. \(a\) is a fixed point of \(T\);
2. \(T\) has only one fixed point;
3. the sequence of successive iterations \(u_0\), \(u_1=Tu_0\), \(u_2=Tu_1,\ldots \) tends to \(a\) for any initial element \(u_0\in X\).

Let \(C\) be a closed convex set in a Hilbert space \(H\), and let \(u\) be an arbitrary vector in \(H\). Show that there exists one and only one element in \(C\) which is closest to \(u\).

Prove the following statement. In an arbitrary real Hilbert space \(H\) an orthonormal system \((\phi _1,\phi _2,\ldots ,\phi _n,\ldots )\) is complete if and only if the equality \[ \lVert f\rVert ^2=\sum _{n=1}^{\infty }\langle f,\phi _n\rangle ^2 \] holds for any \(f\in H\).

Evaluate the integral \[ I=\int _0^\infty \frac {\sin x}{x}\,dx. \]

Evaluate the integral \[ I=\int _0^\infty \frac {x^\alpha }{x^2+1}\,dx \] where \(\alpha \) is a parameter, \(-1<\alpha <1\).

Find a conformal transformation of the domain \(D\) between the unit circle \(\Gamma _1=\{z=x+iy: |z|=1\}\) and the vertical line \(\Gamma _2=\{z=x+iy: x=5/3\}\) onto a domain between two concentric circles.

Liouville’s theorem states that a function analytic and bounded in the complex plane is necessarily a constant.

Prove this theorem. Using it prove the Fundamental theorem of algebra: Every polynomial \(P(z)\) which is not a constant has at least one complex root.

Find the bounded solution \(u(x,y)\) of the Laplace equation in the sector \[ D=\{(r,\theta ): 0<\theta <3\pi /4\}\qquad (x+iy=z=re^{i\theta }) \] satisfying the boundary conditions \[ u=0\text { when }\theta =0,\qquad u=5\text { when }\theta =\frac {3\pi }{4}. \]

Eigenvalue Problems

a) Consider the problem of computing an eigenvalue/eigenvector pair of a real symmetric \(m\times m\) matrix \(A\) with eigenvalues of distinct magnitudes. Two algorithms for trying to do this are Power Iteration and Rayleigh Quotient Iteration:

i) Analyze the convergence properties of the Power Iteration algorithm for a generic guess \(v^0\).

ii) Suppose that the Rayleigh Quotient Iteration iterates \(\lambda ^{(k)}\) converge to a simple eigenvalue \(\lambda \) of \(A\). Analyze the speed of convergence of \(\lambda ^{(k)}\) to \(\lambda \).

b) Many algorithms for finding eigenvalues of a complex \(m\times m\) matrix \(A\) are based on the existence of a Schur decomposition of \(A\), namely, \(A=QTQ^*\) where \(Q\) is unitary and \(T\) is upper triangular. Prove that every matrix \(A\) has a Schur decomposition and explain how knowing the Schur decomposition of \(A\) would help one determine the eigenvalues of \(A\).

Numerical Methods for ODEs Consider the Linear Multistep Method \[ y_{n+1}-y_n=\frac {1}{2}h(f_{n+1}+f_n) \] for solving an initial value problem \(y'=f(y,x)\), \(y(0)=\eta \). You may assume that \(f\) is Lipschitz continuous with respect to \(y\) for all \(x\).

a) Analyze the consistency, stability, accuracy, and convergence properties of this method.

b) Would it be more reasonable to use this method or Euler’s method for the initial value problem: \[ y'=-10^8[y-\cos (x)]-\sin (x),\qquad y(0)=1? \] Justify your answer.

Prove the following statement. In an arbitrary real Hilbert space \(H\) an orthonormal system \((\phi _1,\phi _2,\ldots ,\phi _n,\ldots )\) is complete if and only if the equality \[ \lVert f\rVert ^2=\sum _{n=1}^{\infty }\langle f,\phi _n\rangle ^2 \] holds for any \(f\in H\).

Consider the integral equation \[ u(x)=f(x)+\frac {1}{2}\int _0^1 xtu(t)\,dt,\qquad \text {for }0\le x\le 1 \] where \(f(x)\) is a prescribed function.

1. Show that the equation has at most one solution.
2. Derive a formula for the solution.
3. Calculate the solution for the special case \(f(x)=5x/6\).

Construct the Green function for the equation \[ u''(x)=f(x)\quad \text {on the interval }0\le x\le 1 \] if \(u\) satisfies the auxiliary conditions \[ \int _0^1 xu(x)\,dx=0\qquad \text {and}\qquad u(0)+u'(1)=0. \]

Using complex integration, evaluate the integral \[ I=\int _0^{2\pi }\frac {1}{1+\frac {1}{3}\cos \phi }\,d\phi . \]

Evaluate by contour integration \[ I=\int _0^\infty \frac {x\sin 3x}{4+x^2}\,dx. \]

Using conformal mapping find the electrostatic potential \(\phi (x,y)\) in the region between the circumferences \[ \gamma =\{z:\ |z|=1\}\qquad \text {and}\qquad \Gamma =\{z:\ |z-1|=2.5\} \] satisfying the boundary conditions \[ \phi \equiv 0\text { on }\gamma ,\qquad \phi \equiv 1\text { on }\Gamma . \]

The so called “Brachistochrone problem” admits such formulation. “A particle is sliding along a trough (in a vertical plane from the point \((0,0)\) to some given point \((x_1,y_1)\) \((x_1>0,\ y_1<0)\) under the effect of gravity without friction (having zero initial velocity). Find the form \(y=Y(x)\) of the trough which minimizes the time of descent of this particle.”

1. Find the functional that ought to be minimized.
2. Using this functional, write the boundary value problem that ought to be solved for finding the solution of the “Brachistochrone problem”. You do not need to solve this boundary value problem.

Sensitivity of Solution of Linear System Suppose that \(A\) is a real non-singular \(n\times n\) matrix. Consider the family of linear systems \(Ax(\epsilon )=b+\epsilon c\), where \(b\) and \(c\) are given nonzero vectors in \(\mathbb {R}^n\), and \(\epsilon \) is a real parameter. Let \(x=x(0)\) be the solution for \(\epsilon =0\). Let \(\lVert \cdot \rVert _2\) denote the Euclidean vector norm. Show that \[ \frac {\lVert x(\epsilon )-x\rVert _2}{\lVert x\rVert _2} \le \lVert A\rVert _2\lVert A^{-1}\rVert _2 \frac {\lVert \epsilon c\rVert _2}{\lVert b\rVert _2}. \] The expression \(\lVert A\rVert _2\lVert A^{-1}\rVert _2\) is the condition number of \(A\). Interpret the above inequality and explain its significance?

Eigenvalue Problems Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). a) Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). b) Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues. c) Sketch a reasonably efficient algorithm for finding the largest eigenvalue of a symmetric matrix \(A\) with distinct eigenvalues. How fast do you expect this algorithm to converge?

Iterative Methods for Linear Systems Consider the boundary value problem \[ -u''(x)=f(x),\qquad \text {for }0\le x\le 1 \] with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+2U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\) and \(F_j=h^2f(jh)\).

Analyze the convergence properties of both the Jacobi and Gauss Seidel iterative methods for this problem. In particular, for each, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor \(\delta \) depend on \(h\) for each method? In practice, would you use one of these methods to solve the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?

Newton’s Method Suppose \(f(x)\) is a real-valued function defined for all values of the real variable \(x\), and that \(f'\) is Lipschitz continuous. State and prove a local convergence theorem for Newton’s method for finding a simple zero of \(f\). How does this result change if the root is a double root? Is Newton’s method globally convergent? If you answered yes, prove your claim. If you answered no, sketch an example which illustrates your claim, and outline a method that has the Newton method’s local convergence properties but which is globally convergent.

Broyden’s Method Consider the nonlinear system: \[ F(x)=0\qquad \text {where }F:\mathbb {R}^n\to \mathbb {R}^n \] and the iteration \[ x^{(k+1)}=x^{(k)}-(A^{(k)})^{-1}F(x^{(k)}) \] where \(x^{(0)}\in \mathbb {R}^n\) is given.

Newton’s Method is defined by the choice \(A^{(k)}=F'(x)\) where \(F'(x)\) is the Jacobean matrix of \(F\). An alternative choice for \(A^{(k+1)}\) is made in Broyden’s Method and is motivated as follows:

Let \(A^{(0)}\) be a given and suitably chosen matrix. The scalar Secant Method suggests imposing on \(A^{(k+1)}\) the condition \[ A^{(k+1)}(x^{(k+1)}-x^{(k)})=F(x^{(k+1)})-F(x^{(k)}). \] This however does not uniquely determine \(A^{k+1}\) as it does not give any information on how \(A^{k+1}\) acts on vectors perpendicular to \((x^{(k+1)}-x^{(k)})\). Thus require also that: \[ A^{(k+1)}t=A^{(k)}t \qquad \text {for all }t\in \mathbb {R}^n\text { such that } t^T(x^{(k+1)}-x^{(k)})=0 \] Use these conditions to derive an explicit expression for \(A^{(k+1)}\) in terms of \(A^{(k)}\), \(x^{(k)}\), and \(x^{(k+1)}\).

Numerical Methods for ODEs Consider the Linear Multistep Method \[ y_{n+2}-\frac {4}{3}y_{n+1}+\frac {1}{3}y_n=\frac {2}{3}hf_{n+2} \] for solving an initial value problem \(y'=f(y,x)\), \(y(0)=\eta \). You may assume that \(f\) is Lipschitz continuous with respect to \(y\) for all \(x\).

a) Analyze the consistency, stability, accuracy, and convergence properties of this method.

b) Would it be more reasonable to use this method or Euler’s method for the initial value problem: \[ y'=-10^8[y-\cos (x)]-\sin (x),\qquad y(0)=1? \] Justify your answer.

Let \(x\) and \(y\) be vectors in an inner product space.

1. Verify that the choice \[ \alpha =\frac {\langle x,y\rangle }{\lVert y\rVert ^2} \] makes \(\lVert x-\alpha y\rVert ^2\) as small as possible.
2. Show that \(|\langle x,y\rangle |^2=\lVert x\rVert ^2\lVert y\rVert ^2\) if and only if \(x\) and \(y\) are linearly dependent.

Suppose \(A\in \mathbb {R}^{n\times m}\) and \(b\in \mathbb {R}^n\).

1. Show that the equation \[ A^*Ax=A^*b \] has a solution. Under what conditions on \(A\) is the solution unique?
2. Show that the eigenvalues of \(A^*A\) are non-negative and that its positive eigenvalues are the same as the positive eigenvalues of \(AA^*\).

Let \(H\) be a Hilbert space and \(L:H\to H\).

1. Find and prove the condition that ensures \[ Lu=\int _0^1 k(x,y)u(y)\,dy \] is a bounded linear operator in \(L^2[0,1]\).
2. Under what condition does the adjoint operator \(L^*\) exist? Assuming that this condition is satisfied, give \(L^*\).

Use a Green’s function to find the representation of a possible solution to \[ y''+\omega ^2y=f(x),\qquad y(0)=y'(1)=0 \] for arbitrary values of the parameter \(\omega \). For what values of \(\omega \) does the solution exist? If the solution does not exist find the least square solution. Explain the meaning of the least square solution.

Derive the boundary value problem for a minimizer \(w_0\) of the functional \[ \min _{\substack {w\in C^2[0,1]\\ w(0)=0}} \frac {\int _0^1\left (\phi (x)(w'')^2+w^2\right )\,dx} {\int _0^1\phi (x)(w')^2\,dx+\beta w(1)^2} \] where \(\phi (x)>0\), \(\forall x\in [0,1]\), \(\beta \) is a real parameter.

Evaluate the integral \[ I=\int _0^\infty \frac {x^2\cos x}{x^4+a^4}\,dx \] by contour integration. Use the Jordan lemma.

Define and find the Green’s function for the discrete operator \(Lu=-\Delta u-\lambda u\) defined on the space of doubly infinite sequences \(u=\{u_n\}\), \(-\infty <n<\infty \), with \(\sum _{n=-\infty }^{\infty }u_n^2<\infty \), and with \((\Delta u)_n=u_{n+1}-2u_n+u_{n-1}\).

Prove that the Hermite polynomials form a complete set on \(-\infty <x<\infty \) with the inner product \(\langle u,v\rangle =\int _{-\infty }^{\infty }u(x)v(x)e^{-x^2/2}\,dx\).

Hint: The following steps will prove useful:

1. Show that if the Hermite-Bessel coefficients of \(f(x)\) are all zero, then \(\int _{-\infty }^{\infty }e^{-x^2/2}x^nf(x)\,dx=0\) for all \(n\).
2. Show that the Fourier transform \(F(z)\) of the function \(f(x)e^{-x^2/2}\) has no singularities in the complex plane and is therefore an entire function.
3. Calculate the Taylor series of \(F(z)\) and show that it is zero. What conclusion can you draw about \(f(x)\) and what does this say about Hermite polynomials?

State and prove the Fredholm Alternative Theorem for linear operators \(L:\mathbb {R}^n\to \mathbb {R}^m\).

Given a set of linearly independent vectors \(u_1,u_2,\ldots ,u_n\)

1. Describe the Gram-Schmidt procedure to produce an orthogonal set of vectors from the original set.
2. Suppose \(U\) is a matrix with linearly independent columns. Describe the \(QR\) factorization of \(U\) using Householder transformations.
3. In what sense are these two procedures equivalent? Prove your answer.

Let \(A\) be an \(m\times n\) matrix and let the \(n\times m\) matrix \(A'\) denote the Least Square Pseudo-Inverse of \(A\).

1. State the conditions that define \(A'\).
2. Show that \(A'\) always exists.
3. Construct \(A'\) explicitly for the \(2\times 2\) matrix \[ A=\begin {pmatrix} 1 & 1\\ 0.5 & 0.5 \end {pmatrix}. \]

Suppose \(f(\theta )\) is a \(2\pi \) periodic function. Define its Hilbert Transform as follows: Let \(u(r,\theta )\) be the solution of Laplace’s equation on the unit circle satisfying Neumann data \(u_r(1,\theta )=f(\theta )\). The Hilbert transform of \(f\) is \(H(f)=u_\theta (1,\theta )\).

Use separation of variables to find the Hilbert Transform of \(f\) in terms of its Fourier coefficients.

Philosophy. Why are matrices important? Why do we multiply a matrix with a vector the way we do?

The QR Factorization. Let \(A\) be an \(m\times n\) matrix, where \(m\ge n\). What is the QR factorization of \(A\)? How do you compute it? What do you use it for?

Gaussian Elimination is LU Factorization. What is the LU factorization of a square matrix? How do you solve a linear system \(Ax=b\) by Gaussian Elimination? Show that for a general \(4\times 4\) system the matrix part of Gaussian Elimination is equivalent to computing the LU factorization of \(A\).

Gaussian Quadrature. What is Gaussian quadrature? How do you pick the weights and knots? Why?

Least Squares. Describe in general the problem of approximating a given function in the Least Squares sense by a linear combination of certain basis functions. Discuss the significance of orthogonal basis functions. If you have a basis that is not orthogonal, how can you obtain an orthogonal basis that spans the same space?

Interpolation. Suppose you are given an arbitrarily smooth function \(f\) of a single variable \(x\), and points \[ x_0<x_1<\cdots <x_n. \] Let \(p\) be the interpolating polynomial of degree \(n\) satisfying \[ p(x_i)=f(x_i),\qquad i=0,1,\ldots ,n. \] Derive an expression for the error \[ f(x)-p(x) \] for a general value of \(x\), in terms of the derivatives of \(f\).

Discretization and Convergence. What is a discretization? What does it mean for a discretization to be convergent? Give a precise definition for a differential equation problem and a discretization of your choice.

Local Truncation Error. What is the local truncation error of a numerical scheme? What does consistency mean? Give a specific and precise example.

Stability. What does stability of a numerical scheme mean? Give a specific example.

Convergence is equivalent to stability and convergence. Describe and prove a specific example for this fundamental result.

Iterative Methods for Linear Systems Consider the boundary value problem \[ -u''(x)=f(x),\qquad \text {for }0\le x\le 1 \] with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+2U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\) and \(F_j=h^2f(jh)\). Imagine applying the Jacobi iterative method to solve this system of linear equations. Analyze the convergence properties of the Jacobi method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). You may find it helpful to recall that the \((N-1)\times (N-1)\) matrix \(M\) defined by \[ m_{ij}= \begin {cases} 2, & \text {if } i=j,\\ -1, & \text {if } \lvert i-j\rvert =1,\\ 0, & \text {otherwise} \end {cases} \] has eigenvalues \[ \mu _l=4\sin ^2\left (\frac {\pi l}{2N}\right ),\qquad l=1,2,\ldots ,N-1. \] (NOTE: This is a model problem designed to give you a simple linear system on which to analyze the Jacobi method; one would certainly not use an iterative method to solve a tri-diagonal system in practice!)

Eigenvalue Problems Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). a) Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). b) Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues. c) Sketch a reasonably efficient algorithm for finding the largest eigenvalue of a symmetric matrix \(A\) with distinct eigenvalues. How fast do you expect this algorithm to converge?

Newton Type Methods Suppose \(f(x)\) is a real-valued function defined for all values of the real variable \(x\), and that \(f'\) is Lipschitz continuous. Consider the discrete Newton method: Guess \(x_0\) and for \(k=0,1,2,\ldots \), do: \[ a_k=\frac {f(x_k+h_k)-f(x_k)}{h_k} \] \[ x_{k+1}=x_k-\frac {f(x_k)}{a_k} \] Analyze the local convergence properties of this method. How does the speed of convergence depend on the choice of \(h_k\) (ignore any effect of round-off errors in this analysis)? Now taking roundoff into account what would be a reasonable size for \(h_k\) in practice?

Numerical Methods for ODEs Consider the Linear Multistep Method \[ y_{n+2}-\frac {4}{3}y_{n+1}+\frac {1}{3}y_n=\frac {2}{3}hf_{n+2} \] for solving an initial value problem \(y'=f(y,x)\), \(y(0)=\eta \). You may assume that \(f\) is Lipschitz continuous with respect to \(y\) for all \(x\). a) Analyze the consistency, stability, accuracy, and convergence properties of this method. b) Would this method be a reasonable one to use for the initial value problem: \[ y'=-10^8[y-\cos (x)]-\sin (x),\qquad y(0)=1? \] Justify your answer.

Finite-Difference Methods Consider the spatially-periodic initial value problem for \(v(x,t)\): \[ v_t=cv_x,\qquad \text {for }0\le x\le 1 \] with \[ v(x,0)=f(x),\qquad \text {for }0\le x\le 1. \] Here the function \(f\) has period 1, and \(c\) is a positive constant. Note that the exact solution of the problem is \(v(x,t)=f(x+ct)\).

Consider the following difference approximations to the PDE: \[ \begin {aligned} \text {i)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{h}(u_{j+1}^n-u_j^n),\\ \text {ii)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{h}(u_j^n-u_{j-1}^n),\\ \text {iii)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{2h}(u_{j+1}^n-u_{j-1}^n). \end {aligned} \] In each case, \(Nh=1\), and the difference scheme is supplemented with the discrete initial conditions \(u_j^0=f(jh)\) for \(j=0,1,\ldots ,N\) and boundary conditions \(u_N^n=u_0^n\), \(u_{-1}^n=u_{N-1}^n\), and \(u_{N+1}^n=u_1^n\) for all time levels \(n\ge 0\). For each scheme, tell whether it is a reasonable scheme to use on the above problem, and justify your answers.

Finite-Element Methods Consider the problem: \[ -u''+u=f,\qquad \text {on }[0,1] \] with \[ u(0)=0\qquad \text {and}\qquad u(1)=1. \]

Derive a variational formulations of this problem (be sure to define the space on which your variational problem is to be solved). Formulate a Galerkin finite-element method for the variational problem using piecewise linear functions. Prove that the linear system which arises in the finite-element method has a solution. In what sense is the solution optimal?

Let \(A\) be a real \(m\times n\) matrix with adjoint \(A^*\).

1. Prove that if \(R(A)\) and \(N(A)\) denote the range and nullspace of \(A\) respectively, then \[ R(A)\oplus N(A^*)=\mathbb {R}^m. \] (\(\oplus \) means orthogonal direct sum.)
2. Using the result of (a), state and prove Fredholm’s Alternative Theorem.

Let \(A\) be a real \(m\times n\) matrix.

1. Define the Least Square Pseudo-Inverse \(A'\).
2. Show how Gaussian Elimination can be used to compute \(A'\).

Let \(S=\{\phi _1,\phi _2,\ldots ,\phi _n,\ldots \}\) be a countable orthonormal set in a Hilbert space \(\mathcal {H}\). Prove that \(S\) is a complete orthonormal set if and only if it is a maximal orthonormal set; i.e., there exists no unit vector \(\psi \) such that \(\{\psi ,\phi _1,\phi _2,\ldots ,\phi _n,\ldots \}\) is an orthonormal set.

Let \(f(x)\) be in the Hilbert space \(L^2(-\infty ,\infty )\). Construct and use a Green’s function to find the solution in \(L^2(-\infty ,\infty )\) of the equation \[ u''-\alpha ^2u=f(x),\qquad (\alpha >0). \]

Liouville’s theorem states that a bounded entire function \(f(z)\) must be a constant.

1. Prove Liouville’s theorem.
2. Use Liouville’s theorem to prove the Fundamental Theorem of Algebra: every polynomial \(P_n(z)\) of degree \(n\ge 1\) has a root.

1. State and prove Jordan’s Lemma of complex function theory.
2. Use Jordan’s Lemma and the residue theorem to prove the equation \[ \int _0^\infty \frac {\cos (x)}{x^2+a^2}\,dx=\frac {\pi e^{-a}}{2a} \] where \(a>0\).

The (generalized) Hilbert transform \(H\) of a periodic function \(f\) can be defined as follows: For any simply connected two-dimensional domain \(\Omega \), let \(\phi \) satisfy \(\nabla ^2\phi =0\) with \(\nabla \phi \cdot \mathbf {n}=f\) on \(\partial \Omega \). Then \(Hf=\nabla \phi \cdot \mathbf {t}\) on \(\partial \Omega \). (\(\mathbf {n}\) is the exterior unit normal, \(\mathbf {t}\) is the unit tangent vector.)

1. Prove that \(H(Hf)=-f\).
2. Find a relationship between the Fourier transform and the Hilbert transform, using a unit circle as the domain \(\Omega \).
3. What is the Hilbert transform of \(f(x)=a\sin (x)+b\cos (2x)\)?

Using an integral representation for the \(n\)-th order Bessel function \(J_n(x)\), find the leading order asymptotic representation of \(J_n(x)\) for large positive \(x\).

a) Derive a multistep method to approximate \(y'=f(t,y)\) of the form \[ y_{n+1}=y_n+h(b_{-1}y'_{n+1}+b_0y'_n+b_1y'_{n-1}) \] with \(y'_j=f(t_j,y_j)\), \(t_j=t_0+jh\) by interpolating \(f(s,y(s))\) at \(t_{n-1}\), \(t_n\), \(t_{n+1}\).

b) Analyze the local truncation error of this method and the consequences regarding convergence. What would be an appropriate predictor for this method?

c) Discuss the region of absolute stability of this method, and the predictor-corrector method described in part b).

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.

Compare the stability of the Euler Predictor-Trapezoidal Corrector and Backwards Euler timestepping methods for solution of the heat equation \[ u_t=u_{xx}\qquad u(x,0)=u_0(x) \] using the centered second difference operator \[ u_j \to \frac {u_{j+1}-2u_j+u_{j-1}}{h^2}\qquad j=1,\ldots ,J \] where \(u_j\approx u(jh)\) on the interval \([0,2\pi ]\) with periodic boundary conditions, and mesh-size \(h=2\pi /J\). Discuss the accuracy of these methods?

a) What set of four nonlinear equations are satisfied by the nodes and weights for Gaussian quadrature with degree of precision 3, on the interval \([0,1]\).

b) Describe Newton’s method as applied to solving this system of equations.

c) Show how and why the weights and nodes for Gaussian quadrature may be modified from the standard interval to an arbitrary interval.

a) What is the best least squares approximation to \(f(x)=\cos 3x\) by functions of the form \[ a_0+a_1\cos x+a_2\cos ^2 x+b_1\sin x+b_2\sin ^2 x \] with the inner product given by \[ (v,w)_C=\frac {1}{2\pi }\int _0^{2\pi }v(x)\overline {w(x)}\,dx \]

b) What if the inner product is \[ (v,w)_D=\frac {1}{J}\sum _{j=0}^{J-1}v(x_j)\overline {w(x_j)} \] with \(x_j=jh\), \(h=2\pi /J\).

c) Briefly discuss the normal equations (do they form a well- or ill-conditioned system?), the Gram-Schmidt process, QR factorization in the context of parts a) and b). Observe the connection with problem #2.

a) Show that Jacobi’s method for solving \(Ax=b\) iteratively is convergent when \(A\) is strictly diagonally dominant. What does this imply about the spectral radius of another matrix obtained from \(A\).

b) Describe the successive over-relaxation (SOR) method with parameter \(\omega \) and it’s rate of convergence. Give a sufficient condition upon \(A\) and \(\omega \) for convergence.

c) Briefly compare the complexity of solving Poisson’s problem in three dimensions by direct and iterative methods. Assume the simplest methods, grid, differencing scheme, boundary conditions, etc.

a) Give an example to demonstrate the role of pivoting in Gaussian elimination in solving \(Ax=b\). Define and explain the significance of the condition number of \(A\). Compare the condition numbers, with respect to the norm of your choice, of \(A\) and \(PA\), where \(P\) is a permutation matrix.

b) Explain the \(LU\) decomposition of a matrix \(A\), in particular why the entries of \(L\) are multipliers used in Gaussian elimination, and how to solve \(Ax=b\) using \(L\) and \(U\). How much work does this take?

a) Give an identity that is the basis of one stage of the Fast Fourier Transform algorithm applied to a vector of length \(2^J\). Explain the approximate operation count for the complete algorithm.

b) Describe the application of the FFT to the solution of the heat equation with periodic boundary conditions, and how this may be viewed as performing a fast convolution.

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}\).

Prove that an orthonormal sequence \(\{\phi _1,\phi _2,\ldots ,\phi _n\}\) in a Hilbert space \(\mathcal {H}\) is complete if and only if Parseval’s relation \[ \lVert f\rVert ^2=\sum _{n=1}^{\infty }|\langle f,\phi _n\rangle |^2 \] holds for all vectors \(f\in \mathcal {H}\).

Let \(A\) be an \(m\times n\) matrix and let the \(n\times m\) matrix \(A'\) denote the Least Square Pseudo-Inverse of \(A\).

1. State the conditions that define \(A'\).
2. Show that \(A'\) always exists.
3. Construct \(A'\) explicitly for the \(2\times 2\) matrix \[ A=\begin {pmatrix} 1 & 1\\ 0 & 0 \end {pmatrix}. \]

Consider the boundary value problem \(u''=f(x)\), \(u'(0)=0\), \(u(1)=0\) where \(f(x)\) is a prescribed function.

1. Show that the problem has at most one solution.
2. Show that the solution can be written as \[ u(x)=\int _0^1 k(x,y)f(y)\,dy \] for all continuous functions \(f(x)\) where \[ k(x,y)= \begin {cases} x-1, & \text {for }0\le y\le x\le 1,\\ y-1, & \text {for }0\le x\le y\le 1. \end {cases} \]

Find the general solution, in the sense of distribution theory, of the differential equation \[ x^2u'(x)=\delta (x^2-1). \]

Construct the Green’s function for the equation \(u''(x)=f(x)\) on the interval \(0\le x\le 1\) if \(u\) satisfies the auxiliary conditions \[ \int _0^1 xu(x)\,dx=0\qquad \text {and}\qquad u(0)+u'(1)=0. \]

Find the adjoint operator, its domain and the least squares solution of the problem \(Lu\equiv 4u''+u=e^x\) for \(0\le x\le \pi /2\) if \(u(0)=\alpha \) and \(u(\pi /2)=\beta \).

Find the spectral representation of the delta function for the operator \(L\) defined by \(Lu=-u''\) on \(x\in (-\infty ,0]\) with boundary condition \(u(0)=0\). Then solve the problem \(Lu=f\) if \(f(x)=1\) for \(-2\le x\le -1\) and \(f(x)=0\) elsewhere.

Describe quantitatively the diffusion of 3 units of a diffusing material which is placed at the initial moment \(t=0\) at the origin of an infinite two-dimensional plane. Assume that the plane has unit conductivity.