Math 641-600 Assignments

Assignment 1 - Due Thursday, September 6.

• Read sections 1.1-1.3.
• Do the following problems.
  1. Section 1.1, problem 5, page 49.
  2. Section 1.1 problem 9(b), page 50. (Do up to degree 3.)
  3. Let U be a subspace of an inner product space V, with the inner product and norm being < ·,· > and ||·|| Also, let v be in V, but suppose v is not in U. Show that if there is a u₀ for which

     min _u ||v-u|| = ||v-u₀||,

     then v-u₀ is orthogonal to every u in U. Also, show that u₀ is unique, if it exists.
  4. Consider the tent function T(x) := (1 − |x|)₊, and let φ_k(x) = T(n(x-k/n)). Show that the set B = {φ_k, k=0,...,n} is a basis for the space of linear splines with nodes at x = 0,1/n,2/n,...,1.
  5. Section 1.2, problem 1, page 50.
  6. Section 1.2, problem 9, page 52.

Assignment 2 - Due Thursday, September 13.

• Read sections 1.1-1.5
• Do the following problems.
  1. Section 1.2, problem 5(b), page 51.
  2. Section 1.2 problem 6(b), page 51.
  3. Let U be a finite dimensional subspace of an inner product space V, with the inner product and norm being < ·,· > and ||·||. Define the projection of v in V onto U via Pv = u₀. Show that P is a linear transformation and that P² = P. (You may use the theorem we stated in class on 9/6/07, which characterizes u₀ via the normal equations.)
  4. This problem concerns several important inequalities and the p-norms for Rⁿ.
     1. Show that if α, β are positive and α + β =1, then for all u,v ≥ 0 we have
        u^αv^β ≤ αu + βv.
     2. Let x,y be in Rⁿ, and let p > 1 and define q by q^-1 = 1 - p^-1. Prove Hölder's inequality,
        |∑_j x_jy_j| ≤ ||x||_p ||y||_q.
        Hint: use the inequality in part (a), but with appropriate choices of the parameters. For example, u = (|x_j|/||x||_p)^p
     3. Let x,y be in Rⁿ, and let p > 1. Prove Minkowski's inequality,
        ||x+y||_p ≤ ||x||_p + ||y||_p.
        Use this to show that ||x||_p defines a norm on Rⁿ. Hint: you will need to use Hölder's inequality, along with a trick.
  5. Let A be an n×n real, invertible matrix, with B = A⁻¹ being its inverse. Using the definition of biorthogonal sets of vectors given in Section 1.2, problem 9, page 52, show that the columns of A and B^* (the transpose of B) are biorthogonal.

Assignment 3 - Due Thursday, September 20.

• Read sections 1.1-1.5
• Do the following problems.
  1. Section 1.2, problem 10(a), page 52.
  2. Let V be a finite dimensional inner product space and let U be a subspace of V. The orthogonal complement of U is
     U^⊥ = {v ∈ V | < v,w> = 0 for all w ∈ U}
     Show that V = U⊕U^⊥. (You may need to look up the definition of ⊕, which symbolizes the direct sum of vector spaces.)
  3. Let U be a finite dimensional subspace of a finite dimensional inner product space V, with the inner product and norm being < ·,· > and ||·||. Let Pv be the projection of v onto U. That is, for v in V, Pv is the unique vector in U that is closest to v; Pv satisfies the normal equations; P² = P, etc.
     1. Show that P is selfadjoint; i.e., P^* = P.
     2. Show that if v is in U^⊥, then Pv = 0.
     3. Find the eigenvalues and eigenvectors of P.
  4. Let U be a unitary, n×n matrix. Do the following.
     1. Show that < Ux, Uy > = < x, y >.
     2. Show that the eigenvalues of U all lie on the unit circle, |λ|=1.
     3. Show that U is diagonalizable. (Scalars must be complex).
     4. Suppose that U is real as well as unitary. (Such matrices are orthogonal.) In an odd dimensional space, show that either 1 or − 1 is an eigenvalue of U. (It's possible for both 1 and − 1 to be eigenvalues.)
  5. Do an internet search for Gershgorin's theorem. Write out both a statement and a proof of the theorem, even if all you do is copy by hand what's on the web site. (Please reference the site used.) Use Gershgorin's theorem to answer the questions below.
     1. Show that the eigenvalues of the matrix A (pg. 23) satisfy λ_j ≤ 0. (The book directly shows that they are actually negative.)
     2. Consider the matrix B =

        4  1  1
        0  3 -2
        1  2  4
        

        Show that the eigenvalues of B are all in the right-half plane. (I.e., Re(λ) > 0.)
  6. Section 1.3, problem 2, page 53.

Assignment 4 - Due Thursday, September 27.

• Read sections 2.1-2.2.2
• Do the following problems.
  1. Section 1.4, problem 3, page 54.
  2. Section 1.4, problem 4, page 54.
  3. Suppose data samples Y_-2, Y_-1, Y₀, Y₁, Y₂ are taken at the times t = t₀ − 2h, t₀ − h, t₀, t₀ + h, t₀ + 2h.
     1. For this data, find the linear least squares fit, y(t) = a + bt.
     2. Show that y(t₀) = (Y_-2 + Y_-1 + Y₀ + Y₁ + Y₂)/5.
     3. Smoothing filter. A strategy for removing noise from data is use the average at t₀ to replace the actual data at t₀. That is, we replace Y(t₀) by y(t₀). Perform the following numerical experiment. Let f(t) = sin(πt), where −1 ≤ t ≤1. Sample f(t) at 101 equally spaced points, starting at t = −1 and ending at t = 1. (This means that h = 0.02). To each sample value f(t), add random noise between −0.05 and +0.05. This gives a vector fn(t). Use the strategy above to filter fn to get y(t). How well does y compare to f? (In Matlab, you can use the filter command. But be careful! This gives something slightly different from what you want.) Make separate plots of f-fn and f-y vs. t.
  4. Section 1.5, problem 1(b), page 54.
  5. Section 1.5, problem 3, page 55.
  6. Section 1.5, problem 4, page 55.
  7. Section 1.5, problem 10, page 56.

Assignment 5 - Due Thursday, October 4.

• Read sections 2.1-2.2.2
• Do the following problems.
  1. Section 2.1, problem 5, page 94.
  2. Section 2.1, problem 6, page 94.
  3. Calculus problem: Let g be C² on an interval [a,b]. Let h = b − a. Show that if g(a) = g(b) = 0, then
     ||g||_C[a,b] ≤ (h²/8) ||g′′||_C[a,b].
     Give an example that shows that 1/8 is the best possible constant.
  4. Use the previous problem to show that if f ∈ C²[0,1], then the equally spaced linear spline interpolant f_n satisfies
     ||f − f_n||_C[a,b] ≤ (8n²) ^{− 1} ||f′′||_C[0,1]

  5. Fix f∈ C[0,1] and let ω(f;δ) be the mudulus of continuity of f.
     1. Show that if f ∈ C¹[0,1], then ω(f;δ) ≤ δ||f′||_C[0,1]
     2. Show that ω(f;δ) is nonincreasing as a function of δ.
     3. In class, we said that lim _δ↓0 ω(f;δ) = 0. Show that this is true.
  6. Recall that a function f:[0,1] → R is measurable if and only if for all c ∈ R the set f ⁻¹(c,∞) is measurable.
     1. Show that the characteristic function of A, which is defined by
        χ(t) = 1 if t ∈ A, and χ(t) = 0 if t ∉ A,
        is measurable.
     2. Show that ∫ ₀¹χ(t) dt = m(A).

Assignment 6 - Due Thursday, October 11.

• Read sections 2.1-2.2.2
• Do the following problems.
  1. Let F(s) = ∫ ₀^∞ e ^{− s t} f(t)dt be the Laplace transform of f ∈ L¹([0,∞)). Use the Lebesgue dominated convergence theorem, which holds here, to show that F is continuous from the right at s = 0. That is, show that
     lim_s↓0 F(s) = F(0)= ∫ ₀^∞f(t)dt.
  2. Let f_n(x) = n^3/2 x e^{-n x}, where x ∈ [0,1] and n = 1, 2, 3, ....
     1. Verify that the pointwise limit of f_n(x) is f(x) = 0.
     2. Show that ||f_n||_C[0,1] → ∞ as n → ∞, so that f_n does not converge uniformly to 0.
     3. Find a constant C such that for all n and x fixed f_n(x) ≤ C x^-1/2, x ∈ (0,1].
     4. Use the Lebesgue Dominated convergence theorem to show that
        lim_{n→ ∞} ∫₀¹ f_n(x)dx = 0.
  3. Section 2.1, problem 10, page 94.
  4. Section 2.1, problem 11, page 94.
  5. Let f ∈ C¹[0,1], and suppose that f(0) = f(1) = 0. Show that this version of the Sobolev inequality holds for all x ∈ [0,1]:
     |f(x)| ≤ (∫₀¹|f′(t)|² dt)^1/2.
     

Assignment 7 - Due Thursday, November 8.

• Read sections 2.2.7, 3.2.
• Do the following problems.
  1. Section 2.2, problem 2(a,c), page 95. (Use the real form of the Fourier series; see p. 75 for formulas.)
  2. Section 2.2, problem 9, page 95.
  3. Consider all 2π periodic functions f with Fourier series f(t) = &sum_n c_ne^int such that &sum_n |c_n| is convergent. Show that the Fourier series for f converges uniformly to f and that f is continuous.
  4. Prove the Convolution Theorem for the DFT. (See Notes on the Discrete Fourier Transform, pg. 3.)
  5. Let a, x, y be column vectors with entries a₀, ..., a_n-1, etc., and let α,ξ,η be n-periodic sequences, with the entries for one period being those of a, x, and y, repectively.
     1. Show that the convolution η = α∗ξ is equivalent to the matrix equation y=Ax, where A is an n×n matrix whose first column is a, and whose remaining columns are a with the entries cyclically permuted. For example, if n = 4, and a = (a b c d)^T, then A =

        a d c b
        b a d c
        c b a d
        d c b a
        

     2. Such matrices are called cyclic. Use the DFT and the convolution theorem to find the eigenvalues of a cyclic matrix A.
  6. Let ψ(x) be the Haar wavelet. Show that if f ∈ L²(R) is a uniformly continuous function on R, then the wavelet coefficient
     d^j_k = 2^j < f(x), ψ(2^jx - k) >
     satisfies the bound | d^j_k | ≤ 2^-1 ω(f,2^-j-1), where ω is the modulus of continuity.
  7. Working in the Haar MRA, where the scaling function is φ(x)=N₁(x), let f¹ ∈ S₁ be defined by
     
     Express f¹ in terms of the φ(2x-k)'s, then decompose f¹ into f⁰ ∈ S₀ plus w⁰ ∈ W₀. Sketch all three functions.

Assignment 8 - Due Thursday, November 15.

• Read sections 3.2 and 3.3.
• Do the following problems.
  1. Section 2.2, problem 18, page 97.
  2. Section 2.2, problem 25, page 98.
  3. Finite element problem. We want to solve the boundary value problem (BVP):  -u'' = f(x), u(0) = u(1) = 0.
     1. Let H be the set of all continuous functions vanishing at x = 0 and x = 1, and having L² derivatives. Show that
        < f,g >_H = ∫₀¹ f ′(x) g ′(x) dx,
        is an inner product for H.
     2. Write the BVP in weak form.
     3. Let f(x) = x² in the rest of the problem. Find the exact solution to the BVP for this choice of f.
     4. Let φ_j(x) := N₂(nx-j+1), where N₂ is the linear B-spline. Find the β_j's, where
        β_j = < y,φ_j >_H = ∫₀¹ f(x) φ_j(x) dx, j=1 ... n-1.

     5. Show that Φ_kj = < φ_j, φ_k >_H, the k-j entry in the Gram matrix for the problem, satisfies
        Φ_j,j = 2n, j = 1 ... n-1
        Φ_j,j-1 = - n, j = 2 ... n-1
        Φ_j,j+1 = - n, j = 1 ... n-2
        Φ_j,k = 0, all other possible k.
        For example, if n=5, then Φ is

        10  -5   0   0
        -5  10  -5   0
         0  -5  10  -5 
         0   0  -5  10
        

     6. Numerically solve Φα = β for n = 10, 25, 50. Use your favorite software (mine is MATLAB) to plot the exact solution y and, for each n, the linear finite element approximation to y,
        v(x) = ∑_j α_j φ_j(x),
        which is also the least squares approximation to y in the inner product < · , · >_H defined above.
  4. Let V be a Banach space. Show that a linear operator L:V → V is bounded if and only if L is continuous.

Assignment 9 - Due Tuesday, November 27.

• Read sections 3.3 and 3.4.
• Do the following problems.
  1. Prove the polarization identity for u,v in a hilbert space H:
     ||u+v||² + ||u-v||² = 2(||u||² + ||v||²).
     

  2. Let M is a closed subspace of a Hilbert space H.
     1. Show that if h ∈ H and if
        α := inf_v∈M|| h- v||,
        then there is a sequnce of vectors {p_j} in M for which
        lim_j→∞|| h- p_j|| = α
        
     2. In class, we used the polarization identity to show that
        ||p_j − p_k||² = 2||h − p_j||² + 2||h − p_k||² − 4||h − ½(p_j+p_k)||².
        Use this identity to prove that {p_j} is a Cauchy sequence. From there, finish the proof of the Projection theorem.
     3. Show that M is closed if and only if M = (M^&perp)^&perp.

  3. Weak solutions. In this problem, let
     < f,g >_H = ∫₀¹(f ′(x) g ′(x) +P(x)f(x)g(x))dx,
     where f,g are continuous functions vanishing at x = 0 and x = 1, and having L² derivatives. In addition, we assume that P is continuous and strictly positive on [0,1]. Show that the boundary value problem (BVP) below has a unique weak solution in H, given that H is known to be a Hilbert space. (Hint: use the Riesz Representation Theorem.)
     -u''+P(x)u = f(x), u(0) = u(1) = 0, f ∈ L²[0,1].

  4. Section 3.2 problem 3(d), page 128. (Assume the appropriate operators are closed and that λ is real.)

  5. Section 3.3 problem 2, page 129. (Assume the appropriate operators are closed and that λ is real.)

  6. A sequence {f_n} in H is said to be weakly convergent to f∈H if and only if lim _{n → ∞} < f_n,g> = < f,g> for every g∈H. When this happens, we write f = w-lim f_n. For example, in class we showed that if {φ_n} is any orthonormal sequence, then φ_n converges weakly to 0. One can show that every weakly convergent sequence is a bounded sequence; that is, there is a constant C such that ||f_n|| ≤ C for all n. Prove the following:

     Let K be a compact linear operator on a Hilbert space H. Show that if f_n weakly converges to f, then Kf_n converges strongly to Kf – that is,
     lim _{n → ∞} || Kf_n - Kf || =0.

     Hint: Suppose this doesn't happen, then there will be a subsequence of {f_n}, say {g_k}, such that
     || Kg_k - Kf || ≥ ε
     for all k. Use this and the compactness of K to arrive at a contradiction.

Updated 11/15/07 (fjn).