Question

b) State the error ε that results in the approximation of the largest eigenvalue
of a symmetric matrix An×n by the power method. Assume the x not equals 0 is a given
real vector to be used in the computation.

Answer 1

the true relative error

is EC(&/&)~~, and so we need to take roughly 2k iterations to get an estimated

error equal to the true error after k iterations. Put another way, if the estimated

error is y, the true error will be zC”y2.

Next consider the inequality (1.1) with ,fi = ej&&k_2(c&+2 - 1)/02k. We have

02k-2(@2k+2 - l)/WZk X5 (4/C:)(~2/h)2k+2,

and so m M Cj(L2/A1)2k, where C, = Cm. It follows that this estimate

is within a constant factor of optimal, but is off by a factor of

m = ,/‘m, which can be roughly v’% This is precisely the near

factor of 2 discarded in the estimate 3.1 + Ebj > 21 used in the proof of Theorem

1.1. Of course, our main problem with applying this estimate is that we do not

know of any way of computing (even a good estimate of) Wzk_2(c+&+2 - 1)/02k

(based on computable quantities).

As a compromise, we consider inequality (1.1) with fk = Ek(w - 1)

(L2/Ll)2kp2. To apply this, we require an estimate of &. To do this, first assume

that we have verified by some method that i2 6 &k/(k + 1). Notice (by differ-

entiation) that the function f(x) = x2k(Rk - x)’ IS ’ strictly increasing in x from 0

to x, = Rkk/(k + 1); if f (x0) = B, then x0 = gB(xo), where g(x) = B”(2k)(&-

x)-Ilk. The monotonicity off implies that x,, gs(x,), gB(gs(x*)), . . is monotone

decreasing with limit x0. In particular we have x0 < ga(gB(x*)).