Join / Forgotten your password?
 
HomeFeaturesStoreForumsWikiWorkshopsJobsPortfolioGalleryEvents Members
 
> CGWiki Home       > Community Portal       > Current Events      > Recent Changes     > Random Page       > Join       > Support Forum       > Help     
 

Iterative methods

See also:

Portal:Mathematics

Contents

[edit]

Brief Description

Iterative methods are used in mathematics to find a solution to a problem by initially guessing the solution, and then iteratively improving that solution until convergance. These methods are different from direct methods where we attempt to solve the problem "at once".
[edit]

Solving Systems of Linear Equations

Suppose we have a system of nlinear equations where the ith equation is:

b_i = \sum_{j=1}^n{a_{ij}x_j}
     (1)

This can be expressed much more succinctly in matrix notation as:

b = Ax
     (2)

where b is a known n \times 1 vector, A is a known n \times n matrix, and x is the unknown n \times 1 vector. Usually this is converted into an equivalent system of the form shown below, where neither B nor c depend on the iteration count k.

xk = Bxk − 1 + c
     (3)

where B in the above equation is, like A in (2), an n \times n matrix, c is an n \times 1 vector.

Note: The way equation (3) is derived depends on the template used. A few of these templates will be described later in this section


To find the values of x we first make a guess at an initial solution x0 (which can be completely random). We then use this initial vector to generate another vector by computing

x1 = Bx0 + c
     (4)

We then compare x1 to x0. If the change is less than a predefined threshold we accept x1 as the solution. However, if it exceeds the threshold we repeat the process. This iterative part of the technique is what gives iterative methods their name. Thus we can generalise equation (4) to

x^k = Bx^{k-1} + c \;\;\; k = 1,...
     (5)

Where we generate a sequence of vectors xk until it converges. The standard convergence criterion is

\frac{|x_i^k - x_i^{k-1}|}{|x_i^{k-1}|} \leq threshold,\;\;\; k = 1,...
     (6)

When this criterion is reached the error between the solution x^k and the unknown vector x is guaranteed to be less than or equal to the threshold value at each element, and the method has converged at the solution. The efficiency of a iterative method is normally measured by its convergence rate, which depends entirely on the problem being solved, the iterative method template used to solve it, and the initial values chosen for x0.

Note: There are cases when iterative methods makes a solution diverge rather than converge, and this must be taken into account when using iterative methods to solve problems.


[edit]

The Jacobi Method

If, in equation (1), we solve for xi while assuming no other x changes, we get:

b_i = a_{ii}x_i + \sum_{j=1,j\neq i}^n a_{ij}x_j \Longleftrightarrow x_i = (b_i - \sum_{j=1,j\neq i}^n a_{ij}x_j)/a_{ii}
     (7)

Allowing us to define its iterative method as

x_i^k = (b_i - \sum_{j=1,j\neq i}^n a_{ij}x_j^{k-1})/a_{ii}
     (8)

This equation is know as the Jacobi Method.

Note: The ordering of the equations is irrelevant as they are solved independently, using values from the previous iteration. If the value of a variable is updated early on in an iteration, the old estimate is still used when updating all other variables, until the end of the iteration.


[edit]

The Gauss-Seidel Method

The Gauss-Seidel Method is derived from equation (1) similarly to the Jacobi Method. However, instead of using only estimates from the previous iteration, we want to benefit from the work we have already done in the current iteration and use the new estimates of the variables we have already updated. Using equation (7) we can then define a slightly different iterative method

x_i^k = (b_i - \sum_{j=1}^{j < i}a_{ij}x_j^k - \sum_{j > i}^n a_{ij}x_j^{k-1})/a_{ii}
     (9)


Note: Unlike the Jacobi Method, when using the Gauss-Seidel method, the order in which we solve the equations does have an impact on the estimates at the end of an iteration, as well as the convergence rate. In general, faster convergence rates can be observed using the Gauss-Seidel method, while the Jacobi method benefits from the possibility of simultaneous updates of different variables.
[edit]

Group Iterative Methods

[edit]

Uses in Computer Graphics

[edit]

Related Publications

Retrieved from "http://wiki.cgsociety.org/index.php/Iterative_methods"