Numerical Analysis I, Fall 2011 (http://www.math.nthu.edu.tw/˜ wangwc/)

Notes on Handing in the Programming Homework

1. The 1D problem is just a warm up. But you do need to start from 1D.

2. For the 2D problem, problem 1(b), you have to solve the same linear system many times. You can either solve it with a direct method or an iterative method. The first part of your report is your analysis of the total cost in order to get O(h^{2}) accuracy at time t = 1, for both methods. In the procedure, you will need the spectral radius of standard iterative methods which can be found in homework 11. The operator here is slightly changed from the one in homework 11, so are the spectral radius and the optimal parameter. But you can still use them in your analysis. The difference is minor.

You can choose either method. They carry different difficulties upon implementation.

The second part of your report should contain your results. Report your numerical error at time t = 1 at different N (just put on the numbers and need not make a figure for this). Also report your total CPU time for different N (use help on ’tic’ and ’toc’). For smaller N, the CPU time is just a few seconds and you may need to setup an outer loop to run your code, say 10 times and divide the CPU time by 10 to get more accurate results. This will tell you what your actual operation count is (ie. the p in CN^{p}). If all things are done correctly. This should match your analysis above.

There are different tricks to accelerate both direct and iterative methods. For example, if you choose direct methods, you should not use A\f directly, since the same most expensive part will be repeated over and over and it is totally unnecessarily. Forming the matrix A directly is not possible for this problem. A sample code on creating a sparse matrix in matlab/octave will be posted on the course homepage. On the other hand, if you are using iterative methods, a careful chosen initial guess for the linear systems (not the initial data at t = 0, but the initial approximate solution for the linear system at each t^{n}) can significantly improve the performance. The fact that the solution varies with t continuously can be utilized for this purpose. In addition, you also need to think about when to stop the iteration. How small should the residual be when you stop the iteration? For that, you may need some information on the condition number of A. In one of your homeworks, you have seen that it is O(h^{−2}) for the 1D case. It is the same order for the 2D problem.

3. For problem 1(c), there is an additional decision to make for the nonlinear iteration. Newton or fixed point?

The combination for the choice of the nonlinear iteration and the choice of the linear system solver (direct or iterative) makes it a little more complicated to analyze. Again you can use any combination, but you need to report the analysis part as best as you can, in addition to your numerical results.