Sample Problems

Math 464

The test is closed book. One notebook sized page of notes will be allowed on the test. You may use your calculator on problem number 1, but on all other problems, you should give any numerical answers in the form of a rational number or a simple expression involving radicals.

1. A machine uses the decimal system and represents real numbers in the form ±.m_{1}m_{2}m_{3}m_{4} × 10^{e} where each m_{j} is an integer, 0 ≤ m_{j} ≤ 9, m_{1} ≠ 0, and −5 ≤ e ≤ 5. The machine rounds to nearest even. On this machine the following formula is used to compute a function f:

f(x) = \sqrt{x − 1} − \sqrt{x − 2}

a) How many digits of accuracy will you get for f(100)? What is the relative error?

b) Suggest an alternate formula which is more accurate. What is the relative error?

2. Each of the following iterations may converge. If the iteration does converge it will be to a root of a polynomial p(x). In all three cases the convergence will be to some root of the same polynomial.

x_{k+1} = x_{k}^{2} − 2x_{k} + 2  (1)

x_{k+1} = x_{k} − \frac{x_{k}^{2} − 3x_{k} + 2}{2x_{k} − 3}  (2)

x_{k+1} = −x_{k}^{2} + 4x_{k} − 2  (3)

a) What is p(x)? What are its roots?

b) One of the iterations will converge to either of the two roots of p(x) if the initial guess is sufficiently close. Each of the others will converge to one root, but can’t possibly converge to the other unless the initial guess is exactly equal to the root. Which is which? Give a justification for your answer.

3. a) Find the P A = LU factorization of

[\begin{matrix}1 & 2 & 2 \\ 4 & 8 & 16 \\ −2 & −1 & −2 \end{matrix}]

by using Gaussian elimination and pivoting. L should have 1’s on the main diagonal. b) Use part a) to solve:

Ax = [\begin{matrix}1 \\ 0 \\ 1 \end{matrix}]

4. Let A = [\begin{matrix}1 & 2 \\ 2 & 2 \\ 2 & 3 \end{matrix}] b = [\begin{matrix}5 \\ 0 \\ −4 \end{matrix}]. Find the least squares solution to the problem Ax = b using the normal

equations.

5. a) Let A be row diagonally dominant. Prove that A^{−1} exists.

b) Let

A = [\begin{matrix}3 & 1 \\ 1 & 2 \end{matrix}] , b = [\begin{matrix}1 \\ 1 \end{matrix}] , x^{(0)} = [\begin{matrix}0 \\ 0 \end{matrix}]

Compute two steps, x^{(1)}, x^{(2)} of the Jacobi method for solving Ax = b. Give an error estimate for ∥x^{(2)} − x_{t}∥ in terms of ∥x^{(1)} − x^{(0)}∥, where x_{t} is the true solution.

6. Let

A = [\begin{matrix}3 & 1 \\ 2 & 1 \end{matrix}]

a) Compute κ_{∞}(A).

b) Let

b = [\begin{matrix}4 \\ 3 \end{matrix}]

and suppose that

x_{c} = [\begin{matrix}.9 \\ 1.1 \end{matrix}]

is a computed solution of Ax = b. Give upper and lower estimates on \frac{∥x_{c} − x_{t}∥}{∥x_{t}∥}, using κ_{∞}(A), where x_{t} is the true solution.

7. Consider the fixed point iteration

x_{n+1} = \frac{1}{3 + x_{n}} , x_{0} = 0

a) Prove that

|x_{n+1} − x_{n}| < \frac{1}{9}|x_{n} − x_{n−1}|

b) Prove that x_{n} converges to a limit, s.

c) Prove that x_{n} − s alternates in sign.

d) Find s.