Numerical Methods

jueves, 22 de julio de 2010

Jacobi Method

In numerical linear algebra, the Jacobi method is an algorithm for determining the solutions of a system of linear equations with largest absolute values in each row and column dominated by the diagonal element. Each diagonal element is solved for, and an approximate value plugged in. The process is then iterated until it converges. This algorithm is a stripped-down version of the Jacobi transformation method of matrix diagonalization. The method is named after German mathematician Carl Gustav Jakob Jacobi.

Given a square system of n linear equations:

$A\mathbf x = \mathbf b$

where:

$A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad \mathbf{x} = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix} , \qquad \mathbf{b} = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.$

Then A can be decomposed into a diagonal component D, and the remainder R:

$A=D+R \qquad \text{where} \qquad D = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & a_{nn} \end{bmatrix}, \qquad R = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ a_{21} & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & 0 \end{bmatrix}$

The system of linear equations may be rewritten as:

$(D + R )\mathbf{x} = \mathbf{b}$

$D \mathbf{x} + R \mathbf{x} = \mathbf{b}$

and finally:

$D \mathbf{x} = \mathbf{b} - R \mathbf{x}$

The Jacobi method is an iterative technique that solves the left hand side of this expression for x, using previous value for x on the right hand side. Analytically, this may be written as:

$\mathbf{x}^{(k+1)} = D^{-1} (\mathbf{b} - R \mathbf{x}^{(k)}).$

The element-based formula is thus:

$x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k)}_j\right),\quad i=1,2,\ldots,n.$

Note that the computation of x_i^(k+1) requires each element in x^(k) except itself. Unlike the Gauss–Seidel method, we can't overwrite x_i^(k) with x_i^(k+1), as that value will be needed by the rest of the computation. This is the most meaningful difference between the Jacobi and Gauss–Seidel methods, and is the reason why the former can be implemented as a parallel algorithm, unlike the latter. The minimum amount of storage is two vectors of size n.

Gauss Seidel Method

Gauss-Seidel Method

The Gauss-Seidel method (called Seidel's method by Jeffreys and Jeffreys 1988, p. 305) is a technique for solving the

equations of the linear system of equations

one at a time in sequence, and uses previously computed results as soon as they are available,

x_i^((k))=(b_i-sum_(j<i)a_(ij)x_j^((k))-sum_(j>i)a_(ij)x_j^((k-1)))/(a_(ii)).

There are two important characteristics of the Gauss-Seidel method should be noted. Firstly, the computations appear to be serial. Since each component of the new iterate depends upon all previously computed components, the updates cannot be done simultaneously as in the Jacobi method. Secondly, the new iterate

depends upon the order in which the equations are examined. If this ordering is changed, the components of the new iterates (and not just their order) will also change.

In terms of matrices, the definition of the Gauss-Seidel method can be expressed as

where the matrices

, and

represent the diagonal, strictly lower triangular, and strictly upper triangular parts of

, respectively.

The Gauss-Seidel method is applicable to strictly diagonally dominant, or symmetric positive definite matrices

martes, 20 de julio de 2010

MATRIX

SERIE TAYLOR

serie taylor

lunes, 28 de junio de 2010

Fixed Point Iteration

METODOS ABIERTOS

FALSE POSITON METHOD

False Position Method

miércoles, 26 de mayo de 2010

THE BISECTION METHOD

the bisection method. Given a nonlinear function f(x), we seek a value of x for which

f(x) = 0

Such a solution value for x is called a root of the equation, and a zero of the

function f(x).

The essence of the bisection method lies in the fact that the sign of a function f(x) changes on opposite sides of a root. Suppose the function f(x) has one root in the interval between x = a and x = c, or [a,c], as shown in the Figure below.

The bisection method is based on the fact that when an interval [a,c] contains a

root, the sign of the function at the two ends (f(a) and f(c)) are opposite each

other, namely

f(a)*f(c) < 0

The first step in the bisection method is to bisect the interval [a,c] into two

halves, namely [a,b] and [b,c], where

b=(a + b)/2

By checking the sign of

f(a)*f(b)

the half-interval containing the root can be identified. If

f(a)*f(b) < 0

then, the interval [a,b] has the root, otherwise the other interval [b,c] has the

root. Then the new interval containing the root is bisected again. As the procedure is repeated the interval becomes smaller and smaller. At each step, the midpoint of the interval containing the root is taken as the best approximation of the root. The iterative procedure is stopped when the halfinterval size is less than a prespecified size.

This method is illustrated in the following flowchart.