#hw5.txt, 9Feb, Andrew Lohr #Problem 1: #the approach described in the notes requires ALOT of repeated calculation, making it quadradic in k instead of linear #This one instead relies on memoization, and doesn't result in unneccesary recalculation #it would probably also be more efficeint to do repeated squaring of A prior to applying it to x, getting (A^i x) in poly-log time instead of linear. This is not done here(out of laziness). MemoizedRPowStep:=proc(A,x0) local x5,ma,j: option remember: x5:=MatMult(A,x0): ma:=max( seq( abs(x5[j][1]), j=1..nops(A))): x5:=[seq([x5[j][1]/ma], j=1..nops(A))]: x5: end: RPowEigenval := proc(A,x6) option remember: MatMult(Tra(x6), MatMult(A,x6))[1][1]/MatMult(Tra(x6),x6)[1][1]: end: RPower := proc(A,D1) local i,x1,x2: x1 := [seq([1],i=1..nops(A))]: x2 := [seq([1],i=1..nops(A))]: for i from 1 to 10 do x1 := MemoizedRPowStep(A,x1): od: while (RPowEigenval(A,x1) - RPowEigenval(A,x2)) >10^(-D1-2) do x1 := MemoizedRPowStep(A,x1): x2 := MemoizedRPowStep(A,x2): od: RPowEigenval(A,x1): end: