Final Project
on Iterative Methods in Nonquadratic Optimization.
Due May 11, 1998

MATH 4660-001 and C SC 4666-001: Numerical Analysis II
Spring 1998. University of Colorado at Denver

Students are welcome to communicate with each other and the teacher on-line using the Web page
http://www-math.cudenver.edu/~aknyazev/teaching/98/4660/comments

Computer Project Description:

Let A be a given real symmertic, i.e. A=A', matrix. Then, its minimal eigenvalue is real and can be found as a minimum of the following function

R(x)=(Ax,x)/(x,x),

where x is an arbitary nonzero real column-vector, and (u,v)=u'v is the standard scalar product of real column vectors. The gradient of this function is

grad R(x) = Ax - R(x)x,

up to a scalar multiplier, which is not important for us.

Write and test a MATLAB program of the gradient descent method

x^{k+1} = x^k - alpha * (A*x^k - R(x^k)*x^k)

to find the minimum of function R(x), thus, to find the smallest eigenvalue of A. Use Algorithm 10.3, pp. 617-618 from the text. Test it for different matrices. Try to use it to find the smallest eigenvalue of the matrix NOS6:from set LANPRO, from the Harwell-Boeing Collection. Use a random vector as the initial guess. Use MATLAB build-in functions eig and eigs, to find the eigenvalue, too. Discuss numerical results and perfomance. Write a report and publish it on the Internet.

Hints:

• To write an efficient program, take advantange of the sparse representation of the matrix. See help sparfun to learn about build-in functions.

• Prove, that the given formula for the gradient is correct, using directional derivative, cf. 6664 Final, 1997.
• Find the following paper in a library:
  Knyazev, A. V. ; Skorokhodov, A. L. On exact estimates of the convergence rate of the steepest ascent method in the symmetric eigenvalue problem. Linear Algebra Appl. 154/156 (1991), 245--257.
  Take the optimal formula for alpha, which makes the method to be the steepest descent, from the paper and implement it in your program.
• Make a sound file, "Song of convergence", out of convergence history Feel free to use my sample MATLAB program SongofConvergence.m to test my program soundfile.m that makes sound. My program with length=4 produced the following stereo sound that you can hear in WAV and RealAudio formats. Try to catch the sound on the way to a sound card (I ended up using a tape recorder instead), and save it in a file in any audio format. Include the file in the report on the Internet. Comment: Hardware in the math department does not support sound, which makes this impossible to do unless you find MATLAB with sound support somewhere else.

Sample Report 1 and Report 2.