Problems for Mathematics 617

Instructor: Andrew Sommese

November 26, 2004

10 November 22, 2004: Due November 29, 2004

Problem 10.1 Set up and solve on the square 0 ≤ x ≤ 1; 0 ≤ y ≤ 1

\frac{∂^{2}u(x, y)}{∂x^{2}} + \frac{∂^{2}u(x, y)}{∂y^{2}} = 4

with the boundary conditions u(x, y) = 0 on the boundary of the square. Use N = 1, i.e., x_{0} = 0, x_{1} = 0, 5, x_{2} = 1, y_{0} = 0, y_{1} = 0, 5, y_{2} = 1. The setting up of the problem is the main point of the problem, i.e., computing the approximate solution u_{1,1} requires almost no arithmetic after you have set it up.

y” + y= with the true solution .

Problem 10.2 You wish to solve y′′ + y = x ∗ (1 − x) − 2 on [0, 1] where y(0) = y(1) = 0. Use the Galerkin method to compute an approximate solution ŷ(x) using the hat functions and N = 3, i.e., the x nodes are at x_{0} = 0, x_{1} = 0, 25, x_{2} = 0.5, x_{3} = 0.75, x_{4} = 1.0. Compare the approximate solution ŷ(x) with the true solutions sin(x), e.g., compute ||ŷ(x)−x(1−x)||_{2}.

Warning:  the term ϕ(x)′′ is not 0 for ϕ(x) a hat function!

9 November 15, 2004: Due November 22, 2004

Problem 9.1 This is worth 3 points Solve the boundary value problem on [1, 2]

y′′ = \frac{x^{2}(y′)^{2} − 9y^{2} + 4x^{6}}{x^{5}} ; y(1) = 0 & y(2) = ln(256)

by the shooting method (with Newton’s method at x = 2). Use the Runge-Kutta method of order 4 with stepsize h = 0.05, i.e., x_{i} = 1 + i ∗ 0.05 for i = 0, …, 20. For your initial guess for t in Newton’s method, use t_{0} = 1.7. Stop when |t_{i} − t_{i−1}| < 10^{−6}. Letting ŷ = (y_{0}, …, y_{20}) be your approximate solution of the boundary value problem with t = t_{i}, and noting that x^{3} ln(x) is the exact solution, what is the estimate in the infinity norm of the absolute error, i.e.,

max_{0≤i≤20} {|y_{i} − x_{i}^{3} ln(x_{i})|} .

8 November 8, 2004: Due November 15, 2004

Problem 8.1 Use Gerschgorin’s Theorem (both the vertical and horizonal forms) to determine bounds for the eigenvalues of

B := [ \begin{matrix}1.0 & 0.25 & −0.5 & 1.0 \\ 0.25 & 1.0 & −0.3 & 0.3 \\ −0.5 & 1 & 3 & 1.1 \\ 1 & 0.3 & 1.1 & 4 \end{matrix} ]

Compare the bounds with the actual eigenvalues.

Problem 8.2 With the matrix B from Problem 8.1, do 25 iterations of the QR-algorithm, e.g.,

   (Q,R) := QRDecomposition(B);
   for j from 1 to 24 do
        C:= MatrixMatrixMultiply(R,Q);
    (Q,R):= QRDecomposition(C);
    od:
  MatrixMatrixMultiply(R,Q);

How do the these approximations compare with the eigenvalues computed by your favorite software package?

Problem 8.3 With the matrix

A := [ \begin{matrix}1.0 & 0.25 & −0.5 & 1.0 \\ 0.25 & 1.0 & −0.3 & 0.3 \\ −0.5 & −0.3 & 3 & 1.1 \\ 1 & 0.3 & 1.1 & 4 \end{matrix} ]

do 25 iterations of the QR-algorithm. Why is the last RQ almost diagonal?

Problem 8.4 Let E be the perturbation matrix

E := [ \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1.3 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ]

such that B = A + E for the matrices of the last two problems. The eigenvalue 2.6010781441 of B is a distance of 0.283111719 from ρ(A). How does this compare to the estimate we obtained in class?

Problem 8.5 If A is a unitary matrix and A = QR is the QR-factorization, what can you say about R? Assume here that we are normalizing the QRfactorization so that the diagonal entries of R are positive.

7 October 29, 2004: Due November 8, 2004

Problem 7.1 Let A be an m × n complex matrix. Show that ||A||_{1} = ||A^{∗}||_{∞}.

Problem 7.2 Let A, B be m × n complex matrices. Show that ||A + B|| ≤ ||A|| + ||B|| for any matrix norm.

Problem 7.3 Let A be an m × n complex matrix and let B be and n × p complex matrix. Show that ||A · B|| ≤ ||A|| · ||B|| for any matrix norm.

Problem 7.4 Let A be the Hilbert matrix

H_{n} := [ \begin{matrix}1 & 1/2 & ⋯ & 1/n \\ 1/2 & 1/3 & ⋯ & 1/(n + 1) \\ ⋮ & ⋮ & ... & ⋮ \\ 1/n & 1/(n + 1) & ⋯ & 1/(2n + 1) \end{matrix} ] .

Using only the SVD computed by your favorite program (Maple, Matlab,...)

1. compute cond_{2}(H_{n}) for n = 10, 20, 30; and

2. compute the absolute values of the eigenvalues of H_{10} and H_{20}.

6 October 15, 2004: Due October 29, 2004

Problem 6.1 Find the solution of the difference equation

y_{n+3} = 3y_{n+2} + 4y_{n+1} − 12y_{n} + 6,

with the initial conditions y_{0} = 1, y_{1} = 1, y_{2} = 6 and show that

lim_{n→∞} \frac{y_{n}}{3^{n}} = 1.

In part 2) of the Problem 6.2 you will need to use the Adams-Bashforth four-step method as predictor and the Adams-Moulton three-step method as corrector: both are fourth order methods. Recall from the Maple Worksheet multistep.mws, that to solve the IVP on [a, b]

y′ = f(x, y) with y(a) = α,

with h = \frac{b − a}{n} for some integer n > 0, the Adams-Bashforth four-step method is given by

y_{i+1} = y_{i}+[55f(x_{i}, y_{i}) − 59f(x_{i−1}, y_{i−1}) + 37f(x_{i−2}, y_{i−2}) − 9f(x_{i−3}, y_{i−3})] \frac{h}{24};

and the Adams-Moulton three-step method is given by

y_{i+1} = y_{i} + [9f(x_{i+1}, y_{i+1}) + 19f(x_{i}, y_{i}) − 5f(x_{i−1}, y_{i−1}) + f(x_{i−2}, y_{i−2})] \frac{h}{24}.

In both you need to start the process using some other fourth order method.

Problem 6.2 Consider the IVP (i.e., initial value problem)

y′′ − 2y′ + y = te^{t} on [0, 1]; y(0) = 1; y′(0) = 2.

1. Using the equivalent formulation as a first order initial value problem use the Runge-Kutta method of order 4 with h = 0.05 to find an approximation to (y(1), y′(1)).

2. Using the equivalent formulation as a first order initial value problem use the Adams 4th order predictor-corrector method with h = 0.05 (using Runge-Kutta of order four to get started) to find an approximation to (y(1), y′(1))

3. Using the exact solution to the IVP at the start of this problem

y(t) = e^{t} (\frac{t^{3}}{6} + t + 1) ,

give the absolute error in the infinity norm of the approximations to (y(1), y′(1)) = (5.8896, 9.9670) of part 1) and 2) of this problem.

5 October 8, 2004: Due October 15, 2004

Problem 5.1 A person wishes to find a zero of f(x) = x^{3}−5 for 1 ≤ x ≤ 2. That person decides to use the bisection method to accomplish this.

1. The first approximation to a solution by the bisection method is 1.5 with f(1.5) = \frac{−13}{8}. What is the second approximation to a solution by the bisection method?

2. You would like to find an approximation to a zero of f(x) on [1, 2] with an absolute error of no more than 0.001. Using the bisection method as outlined in the previous part of this problem, and the error estimate for the bisection method, which is the smallest integer n for which you know that on the n-th approximation you will be within 0.001 of the correct answer. Compute this approximation.

Problem 5.2 A person wishes to find a zero of f(x) = x^{3}−5 for 1 ≤ x ≤ 2. That person decides to use Newton’s method (also known as the Newton-Raphson method) for finding a solution of the equation f(x) = 0 on the interval, [1, 2].

1. Write down the iteration formula that Newton’s method gives for solving f(x) = 0. Then using 32 digit arithmetic with 2.0 as a starting guess, find the first six approximations to a solution of f(x) = 0 given by this formula.

2. How do these approximations compare with the tenth approximation of the bisection method computed in the previous problem.

Problem 5.3 A person wishes to find a zero of f(x) = x^{3}−5 for 1 ≤ x ≤ 2. That person decides to use the secant method for finding a solution of the equation f(x) = 0 on the interval, [1, 2].

1. Write down the iteration formula that the secant method gives for solving f(x) = 0. Then using 32 digit arithmetic with 1.0, 2.0 as the starting guesses, find the first six approximations to a solution of f(x) = 0 given by this formula.

2. For i from 1 to 6, compare the i-th approximation with the i-th approximation by Newton’s method.

Problem 5.4 Consider the initial value problem y′ = \frac{(y^{2}+y)}{t} on [1, 2] with y(1) = −3.0.

1. Write down the Taylor’s methods of order 1, 2, 3, and 4 for solving this problem.

2. Using each of these methods with stepsize h = 0.05, find the approximations to y(2).

3. Using the solution y(t) = \frac{3t}{2 − 3t}, we see the true value of y(2) is −1.5.

What are the absolute errors of the approximations to y(2) given in part 2) of this problem by the four methods?

Problem 5.5 Consider the IVP (i.e., initial value problem)

y′′ − 2y′ + y = te^{t} on [0, 1]; y(0) = 1; y′(0) = 2.

1. Write the first order initial value problem this is equivalent to; and

2. with this formulation use Taylor’s method of order 2 with h = 0.05 to find an approximation to (y(1), y′(1)).

3. Using the exact solution to the above IVP

y(t) = e^{t} (\frac{t^{3}}{6} + t + 1) ,

give the absolute error in the infinity norm of your approximation to (y(1), y′(1)) = (5.8896, 9.9670).

4 October 1, 2004: Due October 8, 2004

Problem 4.1 On the interval [−1, 1] find the Gaussian one point, two point and three point rules. Do this by hand.

Problem 4.2 On [a, b], for h be a positive real number such that (b − a)/N is a positive integer, let

T (f, h) = (f(a) + 2 ∑_{i=1}^{N−1} f(a + ih) + f(b)) \frac{h}{2}

denote the composite trapezoid rule.

1. Assume you know T (f, b − a) and T (f, (b − a)/2). What is the rule you obtain by using Richardson extrapolation.

2. Assume you know T (f, b − a) and T (f, (b − a)/3). What is the rule you obtain by using Richardson extrapolation.

You may assume that

T (f, h) = ∫_{a}^{b} f(x)dx + a_{1}h^{2} + O(h^{4})

where a_{1} is independent of h.

Problem 4.3 By hand compute the Bernoulli polynomials B_{2}(x), B_{3}(x), B_{4}(x) and the corresponding Bernoulli numbers. You may assume that B_{0}(x) = 1 and B_{1}(x) = x − 1/2.

3 September 15, 2004: Due September 22, 2004

Problem 3.1 Given a function f(x) ∈ C^{4}[a, b], write down the integration rule f(x) → I(f) obtained by using

I(f) := ∫_{a}^{b} p_{3}(x)dx

to approximate

∫_{a}^{b} f(x)dx,

where p_{3}(x) is the polynomial of degree ≤ 3 such that p(a) = f(a), p′(a) = f′(a), p(b) = f(b), p′(b) = f′(b).

Show that

||∫_{a}^{b} f(x)dx − I(f)|| := max_{[a,b]} |∫_{a}^{b} f(x)dx − I(f)| ≤ \frac{max_{[a,b]} |f^{(4)}(x)|}{720}(b − a)^{5}.

Problem 3.2 Compute (by hand) the spline

B_{0}(x) := 2(t − x)_{+}^{3}[0, 1, 1, 1, 2].

Plot B_{0}(x) for x from −1 to 3 (you can use any program you want for this).

Problem 3.3 Compute the weights for Newton-Cotes integration on [a, b] for n from 1 to 14. (I strongly recommend you do not do this by hand!) Which values of n have all their weights positive?

2 September 8, 2004: Due September 15, 2004

Problem 2.1 For x ∈ [1, 2] and given the knots w := {0, 1, 2, 3}, compute by hand the B-spline of order 3, which has support on [0, 1, 2, 3].

Problem 2.2 Plot the B-spline of order 10 with knots at 0, 0.5, 1, 2, 3, 4, 4.5, 6, 7, 8, 9, and its 4-th derivative.

Problem 2.3 Compute by hand the Newton form of the interpolating polynomial p of degree ≤ 5 such that p(0) = 0, p′(0) = 1, p(1) = 2, p′(1) = 0, p(2) = 1, p′(2) = 0.

Problem 2.4 Compute by hand the Newton form of the interpolating polynomial p of degree ≤ 3 such that p(a) = α_{0}, p′(a) = α_{1}, p(b) = β_{0}, p′(b) = β_{1}.

1 September 1, 2004: Due September 8, 2004

Problem 1.1 1. Using 3 digit arithmetic compute (1.2 + 0.004) + 0.004. What is the absolute and relative error?

2. Using 3 digit arithmetic with rounding compute 1.2 + (0.004 + 0.004). What is the absolute and relative error?

Problem 1.2 Prove Rolle’s Theorem.

Problem 1.3 Write down a Newton form of the unique interpolating polynomial p(x) of degree ≤ 4 such that p(1) = 1, p(2) = 1, p(3) = 2, p(4) = 3, and p(5) = 5. Compute this by hand with details given.

Problem 1.4 Plot on the same graph:

1. the function f(x) := \frac{1}{1 + 25x^{2}} on [−1, 1]; and

2. the interpolation polynomial p_{10}(x) of degree ≤ 10 with p(x_{i}) = f(x_{i}) for x_{i} = −1 + 0.2i for i = 0, …, 10.

Do this a second time with p_{16}(x) in place of p_{10}(x) x_{i} = −1 + 0.125i for i = 0, …, 16.

Problem 1.5 Let x_{0}, …, x_{n} be n + 1 distinct real or complex points. Let

L_{i}(x) := Π_{j≠i} \frac{x − x_{j}}{x_{i} − x_{j}}

be the ith Lagrange polynomial of degree ≤ n for these points, i.e., the unique interpolation polynomial of degree ≤ n such that L_{i}(x_{k}) = 0 for i ≠ k and

= 1 for i = k. Prove that ∑_{i=0}^{n} L_{i}(x) = 1.