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

Table of contents
- Solution a

Solution

For a fixed shift

s

that is not an eigenvalue, inverse iteration is the power method applied to

(A - s I)^{- 1}

. Before normalization, the

k

th vector is proportional to

(A - s I)^{- k} x^{(0)} = \sum_{i = 1}^{n} c_{i} (λ_{i} - s)^{- k} w_{i} .

If

s < λ_{1}

, factor out the first coefficient:

(A - s I)^{- k} x^{(0)} = c_{1} (λ_{1} - s)^{- k} [w_{1} + \sum_{i = 2}^{n} \frac{c _{i}}{c _{1}} (\frac{λ _{1} - s}{λ _{i} - s})^{k} w_{i}] .

Every ratio in parentheses lies strictly between zero and one. The bracket therefore tends to

w_{1}

, and normalization in the Euclidean norm gives

x^{(k)} ⟶ sgn (c_{1}) w_{1} .

This proves the stated convergence to

w_{1}

or

- w_{1}

and exhibits the convergence of fixed-shift inverse iteration rate.

Now suppose

λ_{m} < s < λ_{m + 1}

. The closest eigenvalue to

s

is one of

λ_{m}

and

λ_{m + 1}

.

If $s - λ_{m} < λ_{m + 1} - s$ , the direction approaches $w_{m}$ , but $(λ_{m} - s)^{- 1} < 0$ , so consecutive iterates alternate signs.
If $s - λ_{m} > λ_{m + 1} - s$ , the iterates approach one fixed sign of $w_{m + 1}$ because $(λ_{m + 1} - s)^{- 1} > 0$ .
At the midpoint, the two dominant inverse eigenvalues have equal modulus and opposite signs. Generic iterates alternate between the two normalized combinations proportional to $c_{m} w_{m} + c_{m + 1} w_{m + 1}$ and $- c_{m} w_{m} + c_{m + 1} w_{m + 1}$ .

Finally, if

λ_{n} < s

, the closest eigenvalue is

λ_{n}

and its inverse eigenvalue is negative. Thus the direction approaches the line spanned by

w_{n}

, while normalized vectors alternate between the two signs. These cases are the sign behavior of fixed-shift inverse iteration.

 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