Iterative method

In computational mathematics, is an iterative method to solve a problem (as an equation or a system of equations) by successive approximations to the solution, starting from an initial estimate. This approach contrasts with the direct methods, which attempt to solve the problem once (like solving a system of equations Ax = b by finding the inverse of the matrix A). Iterative methods are useful for solving problems involving a large number of variables (sometimes in the millions), where direct methods would be prohibitively expensive even with the best available computer power.

metodos interativos


Jacobi Method

In numerical analysis method of Jacobi is an iterative method, used for solving systems of linear equations Ax = b. Type The algorithm is named after the German mathematician Carl Gustav Jakob Jacobi

The basis of the method is to construct a convergent sequence defined iteratively. The limit of this sequence is precisely the solution of the system. For practical purposes if the algorithm stops after a finite number of steps leads to an approximation of the value of x in the solution of the system.

The sequence is constructed by decomposing the system matrix as follows:



where

D is a diagonal matrix.
L is a lower triangular matrix.
U is an upper triangular matrix


From Ax = b, we can rewrite this equation as:



then:



If aii ≠ 0 for each i. For the iterative rule, the definition of the Jacobi method can be expressed as:



where k is the iteration counter, finally we have:



Note that when calculating xi ^ (k +1) requires all elements in x ^ (k), except the one with the same i. Therefore, unlike in the Gauss-Seidel method, you can not overwrite xi ^ (k) with xi ^ (k +1), since its value will be for the remainder of the calculations. This is the most significant difference between the methods of Jacobi and Gauss-Seidel. The minimum amount of storage is of two vectors of dimension n, and will need to make an explicit copy





Gauss-Seidel Method


The Gauss-Seidel is an iterative method for solving systems of linear equations. His name is a tribute to the German mathematicians Carl Friedrich Gauss and Philipp Ludwig von Seidel. It is similar to the method of Jacobi (and as such, follows the same convergence criteria). Convergence is a sufficient condition that the matrix is strictly diagonal dominant, i. y., is guaranteed the convergence of the sequence of values generated for the exact solution of linear system.

We seek the solution of the set of linear equations, expressed in terms of matrix as

The Gauss-Seidel iteration is:



where A = D + L + U, the matrix D, L, and U represent respectively the coefficient matrix A: the diagonal, strictly lower triangular and strictly upper triangular, and k is the counter iteraction. This matrix expression is mainly used to analyze the method. When implemented, Gauss-Seidel, an explicit approach is used entry by entry:



Differentiating, if the method of Gauss-Jacob



Since the Gauss-Seidel method has faster convergence than the latter.

EXAMPLE:

ejemplo1


RELAXATION METHODS

Relaxation methods have the following scheme



If 0 < w <1 is called subrelajación and is used when the Gauss-Seidel method does not converge.

If 1 < w is called Overrelaxation and serves to accelerate the convergence. Typical values of 1.2 to 1.7



In matrix form:



http://en.wikipedia.org/wiki/Iterative_method

http://www2.cs.uh.edu/~hadri/cosc_3367/lecture-07.pdf

www.scribd.com