next up previous index
Next: Progressive refinement Up: Solution of the linear Previous: Solution of the linear

Gauss-Seidel iteration

 

The convergence of the iteration can be improved by the method of Gauss-Seidel iteration. Its basic idea is to use the new iterated values immediately when they are available, and not to postpone their usage until the next iteration step. Consider the calculation of tex2html_wrap_inline1772 in the normal iteration:

equation558

During the calculation of tex2html_wrap_inline2304 , values tex2html_wrap_inline2306 have already been calculated, so they can be used instead of their previous value, modifying the iteration, thus:

displaymath2308

equation567

(recall that tex2html_wrap_inline2310 in the radiosity equation).

A trick, called  successive relaxation, can further improve the speed of convergence. Suppose that during the mth step of the iteration the radiosity vector tex2html_wrap_inline2314 was computed. The difference from the previous estimate is:

equation575

showing the magnitude of difference, as well as the direction of the improvement in N dimensional space. According to practical experience, the direction is quite accurate, but the magnitude is underestimated, requiring the correction by a relaxation factor tex2html_wrap_inline2318 :

equation580

The determination of tex2html_wrap_inline2318 is a crucial problem. If it is too small, the convergence will be slow; if it is too great, the system will be unstable and divergent. For many special matrices, the optimal relaxation factors have already been determined, but concerning our radiosity matrix, only practical experiences can be relied on. Cohen [CGIB86] suggests that relaxation factor 1.1 is usually satisfactory.



Szirmay-Kalos Laszlo
Mon Oct 21 14:07:41 METDST 1996