MA/CS/EGR 537: Assignment 3 Answers/Grading

Lemmas 2, 4, and 5 are worth 10 points each. Lemma 3 is worth 30 points (5 points per proof section). The computation section is worth 40 points. The total is 100 points.

For the 10 point proof sections, you could lose 5 points if you were going in the right direction, but got lost or used something unproven. For Lemma 3, you had to get the individual proofs right to collect points. I graded the proofs rather hard.

In the computation section you could lose 10 points for either of the following: (a) computing A*w more than once per iteration, and (b) not telling me how many iterations the code ran for. You could lose more points by not producing a code that had a hope of working or by turning in a relaxation algorithm instead of conjugate gradients.

Excluding the freebies and the 0's (i.e., the not turned in ones), the scores ranged from 30 to 95 with an average of 67 and a median of 65.

Note that there are many proofs for each of these problems. These proofs are just samples.

1. Proof of Lemma 1:

( wk+1 , Awk )	= ( rk+1 + betak wk , Awk )
	= ( rk+1 , Awk ) + betak ( wk , Awk )
	= ( rk+1 , Awk ) - [ ( rk+1 , Awk ) / ( wk , Awk ) ] ( wk , Awk )
	= 0

2. Proof of Lemma 3: An induction proof on all three equations is required. First, prove the three parts for q=k and j=1 (the notation is a little different from the stated problem).

(a)	( rk+1 , wk )	= ( rk+1 + alphak Awk , wk )
		= ( rk , wk ) - [ ( rk , wk ) / ( wk , Awk ) ] ( wk , Awk )
		= 0
	( rk+2 , wk )	= ( rk+1 , wk ) + alphak+1 ( Awk+1 , wk )
		= 0 (by previous equation) + 0 (by Lemma 2) = 0
(b)	( rk+1 , rk )	= ( rk+1 , wk - betak-1 wk-1 )
		= ( rk+1 , wk ) - betak-1 ( rk+1 , wk-1 )
		= 0 (by (a), eqn. 1) + 0 (by (a), eqn. 2) = 0
(c)	( wk+1 , Awk )	= 0 (by Lemma 2)

Now assume that the results are true for q=k+j. We must prove the results for q=k+j+1.

(a)	( rk+j+1 , wk )	= ( rk+j , wk ) + alphak+j ( Awk+j , wk )
		= 0 (by (a)) + 0 (by (c)) = 0
(b)	( rk+j+1 , rk )	= ( rk+j , rk ) + alphak+j ( Awk+j , rk )
		= 0 (by (b)) + 0 (by induction assumption for (c)) = 0
(c)	( wk+j+1 , Awk )	= ( rk+j+1 , Awk ) + betak ( wk+j , Awk )
		= ( rk+j+1 , Awk )
		= alphak-1 [ ( rk+j+1 , rk+1 ) - ( rk+j+1 , rk )
		= alphak-1 [ 0 (by (b)) - 0 (by (b)) ] = 0

where we used Aw_k = alpha_k^-1 ( r_k+1 - r_k ).

3. Proof of Lemma 4:

( rk+1 , rk+1 )	= ( rk + alphak Awk , rk+1 )
	= alphak ( Awk , rk+1 )
	= alphak ( Awk , wk+1 - betak wk )
	= - alphak betak ( Awk , wk )
	= alphak ( Awk - betak Awk-1 , wk+1 - betak wk )
	= alphak ( rk+1 , Ark )

4. Proof of Lemma 5:

betak	= betak [ ( rk , rk ) / ( rk , rk ) ]
	= betak [ ( rk , rk + betak-1 wk-1 ) / ( rk , rk ) ]
	= - [ ( rk , wk ) / ( wk , Awk ) ] [ ( Awk , rk+1 ) / ( rk , rk ) ]
	= alphak [ ( Awk , rk+1 ) / ( rk , rk ) ]
	= [ ( rk + alphak Awk , rk+1 ) / ( rk , rk ) ]
	= [ ( rk+1 , rk+1 ) / ( rk , rk ) ]

Cheers,
Craig C. Douglas