 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/iii/solution

x

x = G x + c

. Subtracting it from the iteration gives the error recurrence

e_{n} = G e_{n - 1}

, with

e_{n} = x_{n} - x

. Multiplying by

S^{- 1}

and using

G = S D S^{- 1}

gives

f_{n} = S^{- 1} GS f_{n - 1} = D f_{n - 1} .

Iterating proves $f_{n} = D^{n} f_{0}$ , including

n = 0

because

D^{0} = I

. This argument does not assume

S

is orthogonal; it simply expresses the error in an eigenbasis.

 New to topics? Read the docs here!