 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/digital-systems-linear-algebra-introduction-to-formal-proof/6/a/iv/solution

Write

D = diag (λ_{1}, \dots, λ_{m})

and let

∣Λ∣ = max_{i} ∣ λ_{i} ∣

. The stated Euclidean norm gives

∥ f_{n} ∥^{2} = \sum_{i} ∣ λ_{i} ∣^{2 n} ∣ (f_{0})_{i} ∣^{2} \leq ∣Λ ∣^{2 n} \sum_{i} ∣ (f_{0})_{i} ∣^{2} = ∣Λ ∣^{2 n} ∥ f_{0} ∥^{2} .

Taking nonnegative square roots proves $∥ f_{n} ∥ \leq ∣Λ ∣^{n} ∥ f_{0} ∥$ . At

n = 0

this is equality. This is a contraction bound in the transformed coordinates; an arbitrary nonorthogonal

S

does not give the same unit-constant bound for the original error norm.

 New to topics? Read the docs here!