Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 41E / b

Table of contents
- Solution b

Solution

Put

M = \sum_{i \geq 2} a_{i}^{2}, c^{2} = 1 + ϵ^{2} M .

The Rayleigh quotient shift is exactly

s_{k} = \frac{λ _{1} + ϵ ^{2} \sum _{i \geq 2} a _{i}^{2} λ _{i}}{1 + ϵ ^{2} M} .

Expanding the denominator gives

s_{k} = λ_{1} + ϵ^{2} \sum_{i \geq 2} a_{i}^{2} (λ_{i} - λ_{1}) + O (ϵ^{4}) .

The question prints this as

s_{k} = λ_{1} - K ϵ^{2} + O (ϵ^{4})

, so its sign convention requires

K = i \geq 2 \sum a_{i}^{2} (λ_{1} - λ_{i}) < 0

unless every

a_{i}

vanishes. Equivalently,

- K

is the positive quadratic Rayleigh-quotient error.

The shifted inverse solve has the spectral decomposition

y = c^{- 1} [\frac{1}{λ _{1} - s _{k}} w_{1} + ϵ \sum_{i \geq 2} \frac{a _{i}}{λ _{i} - s _{k}} w_{i}] .

Only relative coefficients matter after normalization, so factor out

(λ_{1} - s_{k})^{- 1}

:

y ∥ w_{1} + ϵ \sum_{i \geq 2} a_{i} \frac{λ _{1} - s _{k}}{λ _{i} - s _{k}} w_{i} .

From the shift expansion,

λ_{1} - s_{k} = K ϵ^{2} + O (ϵ^{4}),

whereas, for

i \geq 2

,

λ_{i} - s_{k} = (λ_{i} - λ_{1}) + K ϵ^{2} + O (ϵ^{4}) .

Consequently

ϵ a_{i} \frac{λ _{1} - s _{k}}{λ _{i} - s _{k}} = ϵ^{3} \frac{K a _{i}}{λ _{i} - λ _{1}} + O (ϵ^{5}) .

After the final normalization,

x^{(k + 1)} = c_{1}^{- 1} (w_{1} + ϵ^{3} i \geq 2 \sum b_{i} w_{i} + O (ϵ^{5})), b_{i} = \frac{K a _{i}}{λ _{i} - λ _{1}} .

Thus an $O (ϵ)$ eigenvector-direction error becomes $O (ϵ^{3})$ in one step, proving the Local cubic convergence of Rayleigh quotient iteration for this symmetric matrix.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version