Numerical Analysis I, Fall 2000

Assignment 3.

Given Oct 17 2000, due Oct 27 2000.

NOTE: This homework is quite time consuming. You should start IMMEDIATELY and ask for help before it’s too late.

(1) Programming:

(a)Do exercises 2.13 and 2.16 of the textbook. (b)Apply the iterative refinement method in solving the system

( \begin{matrix}420 & 210 & 140 & 105 \\ 210 & 140 & 105 & 84 \\ 140 & 105 & 84 & 70 \\ 105 & 84 & 70 & 60 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix} ) = ( \begin{matrix}875 \\ 539 \\ 399 \\ 319 \end{matrix} ) .

The true solution is (x_{1}, x_{2}, x_{3}, x_{4}) = (1, 1, 1, 1). Do five iterations to see how the computed solutions converges.

(2) We showed in class a (rare) situation where the relative error is really amplified by

a factor κ(A) in solving Ax = b with A = ( \begin{matrix}1 & 0 \\ 0 & ϵ \end{matrix} ). Give an estimate for the

amplification factor of relative error when Δb = ( \begin{matrix}δ \\ δ \end{matrix} ).

(3) We showed in class the derivation of the condition number inequality (2.22) for the special case Δb = 0. We have implicitly used the matrix norm inequality

∥AB∥ ≤ ∥A∥ ∥B∥

in the process.

(a) Prove this inequality and use it to show the condition number lower bound

κ(A) ≥ 1

(b) (harder) Review the derivation for the special case mentioned above and prove the general case (2.22). (Hint: to produce the ∥b∥ term at the right hand side, use the trick

\frac{1}{∥A∥∥x∥} ≤ \frac{1}{∥b∥}

)