Talk:Crank–Nicolson method

From Wikipedia, the free encyclopedia

Two dimensional Crank-Nicolson method: It appears that the 2-d CN method is not going to lead to a tridiagonal system. Instead, we get a large square matrix, with small square matrices arranged tridiagonally on it: M = \left(\begin{array}{ccccc} T & I & 0 & 0 & 0 \\ I & T & I & 0 & 0 \\ 0 & I & T & I & 0 \\ 0& 0 & I & T & I \\ 0&0& 0 & I & T \end{array} \right) with T a tridiagonal (5 X 5) matrix, I the (5 X 5) identity matrix and 0 the (5 X 5) matrix of zeros (this is obviously for the case of 5 points in each direction). To get this matrix, I have ordered the points with increasing x, followed by increasing y.

This matrix is still sparse (so storage is not a problem), but it is not tridiagonal, and so the linear system will be quite slow to solve. Does anyone know a way around this? i.e. Is there a way to set up the problem so that we get a tridiagonal system, or is there a good algorithm for solving the linear system with this type of coefficient matrix?

Woodford 15:40, 9 November 2006 (UTC)Simon

This is not quite my area, but perhaps I can give you some hints to get you started. I don't know of a set-up which gives a tridiagonal matrix, but there are a lot of methods for solving systems with M. You can use a general method for sparse matrices, like the Gauss-Seidel method or successive over-relaxation, or a more complicated but faster methods like conjugate gradient. These methods can be improved by using multigrid techniques. There are also methods exploiting the special structure of the matrix M; one of them is the Hockney method which is based on the fast Fourier transform. Such methods are called "fast Poisson solvers"; a search on that term should give some useful documents.
Source: Iserles, A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press. -- Jitse Niesen (talk) 07:08, 10 November 2006 (UTC)

The 2d Crank-Nicolson will lead to a band diagonal matrix rather than a tridiagonal one. Crack open your favorite Numerical Recipes book for methods on quickly solving band diagonal matrices. Axemanstan 15:39, 9 November 2007 (UTC)

[edit] Phyllis Nicolson

I would be grateful if someone could add a page for PN (if appropriate). See eg Wikipedia:MacTutor archive which leads to http://www-history.mcs.st-andrews.ac.uk/Biographies/Nicolson.html. (I would do it myself but she was my mother.) roundhouse 20:11, 10 January 2007 (UTC)