Diferencia entre revisiones de «Método de Jacobi»
Contenido eliminado Contenido añadido
revirtiendo |
|||
| Línea 1: | Línea 1: | ||
| ⚫ | |||
El '''Método de Jacobi''' es un [[método iterativo]] de [[álgebra lineal]], usado para resolver [[Sistema de ecuaciones lineales|sistemas de ecuaciones lineales]] del tipo <math>Ax=b</math>. El [[algoritmo]] toma su nombre del matemático alemán [[Carl Gustav Jakob Jacobi]]. |
|||
Un método iterativo con el cual se resuleve el sistema lineal Ax = b comienza con una aproximación inicial x(0)a la solucion x y genera una sucesión de vectores x(k) que converge a x. Los métodos iterativos traen consigo un proceso que convierte el sistema Ax = b en otro equivalente de la forma x = Tx + c para alguna matriz fija T y un vector c. |
|||
== Descripción == |
|||
La base del método consiste en construir una [[Sucesión matemática|sucesión]] [[Convergencia|convergente]] definida [[Método iterativo|iterativamente]]. El límite de esta sucesión es precisamente la solución del sistema. A efectos prácticos si el algoritmo se detiene después de un número finito de pasos se llega a una aproximación al valor de ''x'' de la solución del sistema. |
|||
Luego de seleccionar el vector inicial x(0) la sucesión de los vectores de la solución aproximada se genera calculando: |
|||
La sucesión se construye descomponiendo la [[Matriz (matemática)|matriz]] del sistema <math>\mathbf{A}</math> en la forma siguiente: |
|||
{{ecuación|<math>\mathbf{A} = \mathbf{D} + \mathbf{L} + \mathbf{U}</math>||center}} |
|||
Donde: |
|||
:<math>\mathbf{D}</math>, es una matriz diagonal. |
|||
:<math>\mathbf{L}</math>, es una matriz triangular inferior. |
|||
:<math>\mathbf{U}</math>, es una matriz triangular superior. |
|||
Partiendo de <math> A x = b\, </math>, podemos reescribir dicha ecuación como: |
|||
{{ecuación|<math>\mathbf{D}x+\left( \mathbf{L}+\mathbf{U}\right)x = b</math>||center}} |
|||
Luego, |
|||
{{ecuación|<math>x=\mathbf{D}^{-1} \left[ b-\left( \mathbf{L}+\mathbf{U} \right)x \right]</math>||center}} |
|||
Si a<sub>''ii''</sub> ≠ 0 para cada ''i''. Por la regla iterativa, la definición del '''Método de Jacobi''' puede ser expresado de la forma: |
|||
{{ecuación|<math>x^{\left( k+1 \right)}=\mathbf{D}^{-1}\left[ b-\left( \mathbf{L}+\mathbf{U} \right)x^{(k)} \right]</math>||center}} |
|||
Donde <math>k</math> es el contador de iteración, Finalmente tenemos: |
|||
{{ecuación|<math>x_{i}^{\left( k+1 \right)}=\frac{1}{a_{ii}}\left( b_{i}-\sum\limits_{j\ne i}{a_{ij}x_{j}^{\left( k \right)}} \right),i=1,2,3,...</math>||center}} |
|||
x(k) = Tx(k-1) + c |
|||
Cabe destacar que al calcular ''x''<sub>''i''</sub><sup>(''k''+1)</sup> se necesitan todos los elementos en ''x''<sup>(''k'')</sup>, excepto el que tenga el mismo ''i''. Por eso, al contrario que en el [[Método de Gauss-Seidel|método Gauss-Seidel]], no se puede sobreescribir ''x''<sub>''i''</sub><sup>(''k'')</sup> con ''x''<sub>''i''</sub><sup>(''k''+1)</sup>, ya que su valor será necesario para el resto de los cálculos. Esta es la diferencia más significativa entre los métodos de Jacobi y Gauss-Seidel. |
|||
La cantidad mínima de almacenamiento es de dos vectores de dimensión ''n'', y será necesario realizar un copiado explícito. |
|||
para cada k = 1,2,3,.... |
|||
== Convergencia == |
|||
El método se escribe en la forma x(k) = Tx(k-1) + c separando A en sus partes diagonal D y fuera de la diagonal. Sea D la matriz diagonal cuya diagonal es la misma que A, sea -L la parte estrictamente triangular inferior de la parte A y sea -U la parte estrictamente triangular superior de A. |
|||
El método de Jacobi siempre converge si la matriz ''A'' es [[Matriz de diagonal estrictamente dominante|estrictamente diagonal dominante]] y puede converger incluso si esta condición no se satisface. Es necesario, sin embargo, que los elementos de la diagonal en la matriz sean mayores (en magnitud) que los otros elementos. |
|||
Con esta notacion A = D-L-U, entonces transformamos la ecuación Ax = b, o (D-L-U)x = b, en |
|||
== Algoritmo == |
|||
El método de Jacobi se puede escribir en forma de [[algoritmo]] de la siguiente manera: |
|||
Dx = (L+U)x + b |
|||
| ⚫ | |||
'''función''' Jacobi (<math>A</math>, <math>x^{0}</math>) |
|||
://<math>x^{0}</math> es una aproximación inicial a la solución// |
|||
:'''para''' <math>k\gets 1</math> '''hasta''' convergencia '''hacer''' |
|||
::'''para''' <math>i\gets 1</math> '''hasta''' <math>n\,</math> '''hacer''' |
|||
:::<math>\sigma\gets 0</math> |
|||
:::'''para''' <math>j\gets 1</math> '''hasta''' <math>n\,</math> '''hacer''' |
|||
::::'''si''' <math>j != i\,</math> '''entonces''' |
|||
:::::<math> \sigma = \sigma + a_{ij} x_j^{(k-1)} </math> |
|||
:::'''fin para''' |
|||
:::<math> x_i^{(k)} = {{\left( {b_i - \sigma } \right)} \over {a_{ii} }} </math> |
|||
::'''fin para''' |
|||
::comprobar si se alcanza convergencia |
|||
:'''fin para''' |
|||
}} |
|||
y, si D-1 existe, es decir, si ai,i es distinto de cero para cada i, entonces |
|||
== Enlaces externos == |
|||
*[http://www.math-linux.com/spip.php?article49 Jacobi Method from www.math-linux.com] |
|||
*[http://mathworld.wolfram.com/JacobiMethod.html Jacobi Method at Math World] |
|||
*[http://math.fullerton.edu/mathews/n2003/GaussSeidelMod.html Module for Jacobi and Gauss–Seidel Iteration] |
|||
*[http://pagerank.suchmaschinen-doktor.de/matrix-inversion.html Numerical matrix inversion] |
|||
{{ORDENAR:Metodo de Jacobi}} |
|||
x = D-1(L+U)x + D-1b. |
|||
[[Categoría:Álgebra lineal numérica]] |
|||
Esto da origen a la forma matricial del método iterativo de Jacobi: |
|||
[[de:Jacobi-Verfahren]] |
|||
[[en:Jacobi method]] |
|||
x(k) = D-1(L+U)x(k-1) + D-1b, k = 1,2,... |
|||
[[fr:Méthode de Jacobi]] |
|||
[[id:Metode Jacobi]] |
|||
Al introducir la notación Tj = D-1(L+U) y cj, esta técnica tiene la forma |
|||
[[it:Metodo di Jacobi]] |
|||
[[ja:ヤコビ法]] |
|||
x(k) = Tx(k-1) + c |
|||
[[nl:Methode van Jacobi]] |
|||
[[ru:Метод Якоби]] |
|||
[[ur:جیکبی طریقہ]] |
|||
Revisión del 02:23 18 jun 2009
Método de Jacobi
Un método iterativo con el cual se resuleve el sistema lineal Ax = b comienza con una aproximación inicial x(0)a la solucion x y genera una sucesión de vectores x(k) que converge a x. Los métodos iterativos traen consigo un proceso que convierte el sistema Ax = b en otro equivalente de la forma x = Tx + c para alguna matriz fija T y un vector c.
Luego de seleccionar el vector inicial x(0) la sucesión de los vectores de la solución aproximada se genera calculando:
x(k) = Tx(k-1) + c
para cada k = 1,2,3,....
El método se escribe en la forma x(k) = Tx(k-1) + c separando A en sus partes diagonal D y fuera de la diagonal. Sea D la matriz diagonal cuya diagonal es la misma que A, sea -L la parte estrictamente triangular inferior de la parte A y sea -U la parte estrictamente triangular superior de A.
Con esta notacion A = D-L-U, entonces transformamos la ecuación Ax = b, o (D-L-U)x = b, en
Dx = (L+U)x + b
y, si D-1 existe, es decir, si ai,i es distinto de cero para cada i, entonces
x = D-1(L+U)x + D-1b.
Esto da origen a la forma matricial del método iterativo de Jacobi:
x(k) = D-1(L+U)x(k-1) + D-1b, k = 1,2,...
Al introducir la notación Tj = D-1(L+U) y cj, esta técnica tiene la forma
x(k) = Tx(k-1) + c