Método jacobi

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de abril de 2022; las comprobaciones requieren 2 ediciones .

El método de Jacobi es una variación del método de iteración simple para resolver un sistema de ecuaciones algebraicas lineales . El nombre de Carl Gustav Jacobi .

Planteamiento del problema

Tomemos un sistema de ecuaciones lineales:

$A\vec{x}=\vec{b}$ , dónde $A=\left( \begin{array}{ccc} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \ldots & a_{nn} \ end{matriz} \right),\quad \vec{b}=\left( \begin{matriz}{c} b_1 \\ \vdots \\ b_n \end{matriz} \right)$

O $\left\{{\begin{matriz}{rcl}a_{{11}}x_{1}+\ldots +a_{{1n}}x_{n}&=&b_{{1}}\\\ldots ~ ~~~~~~~~~~~~~~~~~~~\\a_{{n1}}x_{1}+\ldots +a_{{nn}}x_{n}&=&b_{ { n}}\end{matriz}}\right.$

Descripción del método

Para construir un procedimiento iterativo del método de Jacobi, es necesario realizar una transformación preliminar del sistema de ecuaciones a la forma iterativa . Se puede hacer de acuerdo con una de las siguientes reglas: $A\vec{x}=\vec{b}$ ${\vec {x}}=B{\vec {x}}+{\vec {g}}$

$B=ED^{{-1}}A=D^{{-1}}(DA),\quad {\vec {g}}=D^{{-1}}{\vec {b}}) ;$

$B=-D^{{-1}}(L+U)=-D^{{-1}}(AD),\quad {\vec {g}}=D^{{-1}}{\ vec{b}}$

$D_{{ii}}^{{-1}}=1/D_{{ii}},D_{{ii}}\neq 0,\,i=1,2,...,n\quad ;$

donde, en la notación aceptada, significa una matriz cuya diagonal principal contiene los elementos correspondientes de la matriz y todos los demás ceros; mientras que las matrices y contienen partes triangulares superior e inferior , en cuya diagonal principal se encuentran los ceros, se encuentra la matriz identidad . $D$ $A$ $tu$ $L$ $A$ $mi$

Entonces el procedimiento para encontrar una solución es:

{\vec {x}}^{{(k+1)}}=B{\vec {x}}^{{(k)))+{\vec {g}},

O como una fórmula elemento por elemento:

x_{i}^{{(k+1)}}={\frac {1}{a_{{ii}}}}\left(b_{i}-\sum_{{j\neq i}}a_ {{ij}}x_{j}^{{(k)}}\right),\quad i=1,2,\ldots,n.

donde está el contador de iteraciones. $k$

A diferencia del método de Gauss-Seidel, no podemos reemplazar con durante el procedimiento iterativo, ya que estos valores serán necesarios para el resto de los cálculos. Esta es la diferencia más significativa entre el método de Jacobi y el método de Gauss-Seidel para resolver SLAE . Así, en cada iteración habrá que almacenar ambos vectores de aproximación: el antiguo y el nuevo. ${\ Displaystyle x_{i}^{(k)))$ $x_{i}^{{(k+1)}}$

Condición de convergencia

Presentemos una condición suficiente para la convergencia del método.

teorema _
deja_ Entonces, para cualquier opción de aproximación inicial:

{\ estilo de visualización \|B\|<1}

\vec{x}^{(0)}

el método converge;
la tasa de convergencia del método es igual a la tasa de convergencia de una progresión geométrica con el denominador ; ${\ estilo de visualización q = \|B\|}$
estimación correcta del error: . $\|{\vec {x}}^{(k)}-{\vec {x}}\|<q^{k}\,\|{\vec {x}}^{(0) }-{\vec{x}}\|$

Condición de parada

La condición para el final del proceso iterativo cuando se alcanza la precisión tiene la forma: $\varepsilon$

\parallel x^{(k+1)}-x^{(k)}\parallel \leq {\frac {1-q}{q}}\varepsilon .

Para una matriz suficientemente bien condicionada (para ), se cumple para $B$ ${\ estilo de visualización \ paralelo B \ paralelo = q <1/2}$

\parallel x^{(k+1)}-x^{(k)}\parallel \leq \varepsilon .

Este criterio no requiere el cálculo de la norma matricial y se usa a menudo en la práctica. En este caso, la condición exacta para la terminación del proceso iterativo tiene la forma

\parallel Ax^{(k)}-b\parallel \le \varepsilon

y requiere una multiplicación matriz-vector adicional en cada iteración, lo que duplica aproximadamente la complejidad computacional del algoritmo.

Algoritmo

A continuación se muestra el algoritmo de implementación en C++

#incluir <matemáticas.h> const doble eps = 0.001 ; ///< precisión deseada ......................... /// N - dimensión de la matriz; A[N][N] - matriz de coeficientes, F[N] - columna de términos libres, /// X[N] - aproximación inicial, la respuesta también está escrita en X[N]; void Jacobi ( int N , doble ** A , doble * F , doble * X ) { doble * TempX = nuevo doble [ N ]; doble norma ; // norma, definida como la mayor diferencia entre los componentes de la columna x de las iteraciones vecinas. hacer { para ( int yo = 0 ; yo < norte ; yo ++ ) { TempX [ i ] = F [ i ]; para ( int gramo = 0 ; gramo < norte ; gramo ++ ) { si ( yo != g ) TempX [ i ] -= A [ i ] [ g ] * X [ g ]; } TempX [ i ] /= A [ i ][ i ]; } norma = fábricas ( X [ 0 ] - TempX [ 0 ]); para ( int h = 0 ; h < norte ; h ++ ) { if ( fábricas ( X [ h ] - TempX [ h ]) > norma ) norma = fabs ( X [ h ] - TempX [ h ]); X [ h ] = TempX [ h ]; } } while ( norma > eps ); borrar [] TempX ; }

El siguiente es el algoritmo de implementación en Python

de collections.abc import Sequence , MutableSequence def Jacobi ( A : Secuencia [ Secuencia [ float ]], b : Secuencia [ float ], eps : float = 0.001 , x_init : MutableSequence [ float ] | Ninguno = Ninguno ) -> list [ float ]: """ Método Jacobi para A*x = b(*) :param A: Matriz (*) a la izquierda :param b: vector conocido (*) a la derecha :param x_init: aproximación inicial :retorno: valor x aproximado (*) """ def sum ( a : Secuencia [ float ], x : Secuencia [ float ], j : int ) -> float : S : float = 0 for i , ( m , y ) in enumerate ( zip ( a , x )): if i != j : S += m * y devuelve S def norma ( x : Secuencia [ float ], y : Secuencia [ float ]) -> float : return max (( abs ( x0 - y0 ) for x0 , y0 in zip ( x , y ))) si x_init es Ninguno : y = [ a / A [ i ][ i ] for i , a in enumerate ( b )] else : y = x . copiar () x : list [ float ] = [ - ( sum ( a , y , i ) - b [ i ]) / A [ i ][ i ] for i , a in enumerate ( A )] while norma ( y , x ) > eps : for i , elem in enumerate ( x ): y [ i ] = elem for i , a in enumerate ( A ): x [ i ] = - ( sum ( a , y , i ) - b [ i ]) / A [ i ][ i ] devuelve x

Véase también

Método de Gauss-Seidel

Métodos para resolver SLAE
Métodos directos	método matricial método de Gauss Método de Gauss-Jordan método Cramer descomposición LU Descomposición de Cholesky método de barrido
Métodos iterativos	método jacobi Método de Gauss-Seidel método de iteración método de relajación método de gradiente conjugado Método de gradiente biconjugado Método de gradiente biconjugado estabilizado
General	matriz inversa Métodos de proyección para resolver SLAE preacondicionamiento