El método de Gauss-Seidel PDF

Preview

Summary

Definición, fórmula y algoritmo del método de Gauss-Seidel. Incluye un ejemplo del mismo, además de un código para ejecutarlo en MATLAB....

Description

Universidad Nacional Experimental del Táchira Vicerrectorado Académico Decanato de Docencia Departamento de Matemática y Física

MÉTODO DE GAUSS-SEIDEL

Integrantes: José Cáceres, 23.095.417 José Méndez, 20.879.881 Jorge Contreras, 23.547.538 Yonathan Chacón, 24.360.669 Asignatura: Análisis Numérico Sección: 02 Profesora: Jenny Pérez San Cristóbal, Abril 2016

Índice Introducción………………………………………………………………………………..3 Definición del método Gauss-Seidel…………………………………………………….4 Obtención de la fórmula de Gauss-Seidel……………………………………………...5 Algoritmo de Gauss-Seidel……………………………………………………………….8 Ejemplo del método de Gauss Seidel…………………………………………...….......9 Programa del método iterativo de Gauss-Seidel……………………………………..11 Referencias Bibliográficas………………………………………………………………14

Introducción Uno de los problemas básico del Análisis Numérico es encontrar los valores de las incógnitas que afecta a un sistema de ecuaciones. Una solución considerablemente eficiente a este desafío es la aplicación de un método iterativo, el cual, por medio de una sucesión de procedimientos, logra llegar a un valor muy cercano a la solución deseada. Esta aproximación contrasta con los métodos directos, que tratan de resolver el problema de manera inmediata, una alternativa poco útil cuando es necesario resolver problemas que involucran un gran número de variables. De hecho, las técnicas iterativas rara vez son empleadas para resolver problemas de dimensiones pequeñas, debido a que el tiempo requerido para lograr una precisión suficiente excede a las técnicas directas. Las fórmulas iterativas no siempre convergen, su análisis tiende a ser complicado y además requieren la elección de un vector inicial para comenzar el proceso iterativo. Estas desventajas restan valor a este tipo de procedimientos, aunque también atraen el interés de los teóricos matemáticos y aquellos que tenga que lidiar regularmente con grandes sistemas de ecuaciones lineales con matrices esparcidas. Para definir un método iterativo, es necesario reemplazar el sistema Ax = b por la forma (D – L – U)x = b, donde D es la matriz diagonal de A, L es la matriz estrictamente triangular inferior y U es la matriz estrictamente triangular superior. Esta nueva expresión es posteriormente operada algebraicamente hasta obtener una representación equivalente que permite generar una serie de soluciones aproximadas para x. Dos de los métodos iterativos más usados son el método de Jacobi y el método de Gauss-Seidel, siendo este último una modificación del primero.

3

Definición del método de Gauss-Seidel El método de Gauss-Seidel es un método iterativo cuyo nombre rinde honor a los matemáticos alemanes Carl Friedrich Gauss y Philipp Ludwig von Seidel. Al igual que otros procedimientos semejantes, permite solucionar sistemas de ecuaciones lineales por medio de una aproximación inicial, la cual, luego de una serie de aproximaciones sucesivas, arroja una solución válida con una margen de error tan pequeño como se desee. El número de iteraciones a realizar depende de las ecuaciones a tratar, el número de dígitos que se conservan en el resultado de las operaciones aritméticas y el procedimiento de redondeo. En esencia, se trata de una modificación del método de Jacobi, por lo que ambos funcionan de manera semejante. Sin embargo, mientras que la propuesta de Jacobi se utiliza el valor de se utiliza el valor de las incógnitas para determinar una nueva aproximación, en el de Gauss-Seidel se va utilizando los valores de las incógnitas recién calculados en la misma iteración. Por este motivo, se puede suponer que el método de Gauss-Seidel en general converge o diverge más rápidamente que el método de Jacobi. Los programas que siguen los pasos planteados por este método tienden a emplear menor tiempo de computación por iteración, además pocos requerimientos de memoria. Sin embargo, su misma naturaleza acarrea desventajas notables, tales como un bajo ritmo de convergencias, resultando en un mayor número de iteraciones. Generalmente, este método convergirá siempre a una solución cuando la magnitud de coeficientes del sistema sea una matriz diagonal dominante, es decir, cuando el valor absoluto de los elementos que conforman la diagonal principal son mayores que la suma de los valores absolutos de los demás elementos de la fila correspondiente. Esta condición es conocida como condición de convergencia del método. No obstante, esta condición es suficiente, mas no necesaria. Existen sistemas de ecuaciones que no son diagonalmente dominantes, y sin embargo, convergen a una solución.

4

Obtención de la fórmula de Gauss-Seidel El método Gauss-Seidel entra en la familia de los métodos iterativos concernientes a la resolución de sistemas de ecuaciones, considerando su naturaleza matricial, es por esto que se requiere una formula en especial.

Se considera que el método de Gauss-Seidel es una mejora al método jacobi, pues la iteración de Gauss-Seidel se define al tomar un sistema de ecuaciones como una matriz A, donde la matriz Q es a su vez considerada como la parte triangular inferior de A incluyendo los elementos de la diagonal:

Si, como en el caso anterior, definimos la matriz R=A-Q

Un elemento cualquier, i, del vector Qx(k) vendrá dado por la ecuación:

Si tenemos en cuenta la peculiar forma de las matrices Q y R, resulta que todos los sumandos para los que j > i en la parte izquierda son nulos, mientras que en la parte derecha son nulos todos los sumandos para los que j es menor o igual a i. Podemos escribir entonces: 5

Es decir que para calcular Xn, se usan las componentes de Xn. Como, para i >1, los anteriores valores:

Ya han sido calculadas y supuestamente son mejores aproximaciones a la solución real que las de la iteración anterior, parece razonable calcular Xn, usando los valores calculados más recientemente. Para i = 1, 2,..., n, en vez de la ecuación Esta técnica se llama método iterativo de Gauss-Seidel. Para escribir este método en la forma matricial se multiplican ambos lados de la ecuación (6.10) por aij y se pasan todos los términos de la etapa k-ésima al mismo lado quedando:

Para cada i = 1, 2,..., n. Escribiendo las n ecuaciones tenemos:

Y por lo tanto, en forma matricial, el método de Gauss-Seidel puede representarse como: 6

O bien se puede representar también de la manera:

Para que la matriz triangular inferior D - L sea no singular, es necesario y suficiente que aij diferente de 0, para cada i = 1, 2,..., n.

7

Algoritmo de Gauss-Seidel Se desea resolver un sistema de ecuaciones lineales Ax = b de orden (n ×n) en forma iterativa, para ello es necesario conocer un vector de aproximación inicial X(0) =( x1(0), x2(0), . . . , xn(0))t , un error de tolerancia permitido ε , para ello se deben seguir los pasos descritos a continuación: Paso 1: se inicializa el proceso k=1. Paso 2: Para cada

i =1, . . . ,

n ; hacer

n

∑

k

aij x j −¿

j=i +1 i−1

aij x j

k−1

∑¿ j=1

(k) i

x =

1 ¿ a ii

Paso 3: Se calcula el error de tolerancia utilizando la forma infinita l∞ .

‖x( k ) − x(k−1)‖ ∞= i=1, ... ,n{|x( k ) − x(k−1)|, . .. , |x (k)−x (k−1)|} Si ‖x(k) −x(k−1)‖ ∞< ε vaya al paso 5 Si ‖x( k ) − x(k−1)‖ ∞> ε vaya al paso 4 máx

Paso 4: Haga

k =k +1 y vaya al paso2

Paso 5: Finaliza el proceso.

8

Ejemplo del método de Gauss-Seidel Uso el método de Gauss-Seidel para resolver el sistema de ecuaciones dado. La tolerancia usada es igual a 0,1.

Programa del método iterativo de Gauss-Seidel fprintf('Introduzca la Matriz: \n'); Matriz=input('','s'); fprintf('----------------------------------------------------\n'); A=str2num(Matriz); vector=input('Ingrese el Vector B como vector columna: \n','s'); b=str2num(vector); vectori=input('Ingrese el vector aproximacion inicial como vector columna: \n','s'); x=str2num(vectori); tol=input('tolerancia: '); n=input('Numero maximo de iteraciones: '); fprintf('----------------------------------------------------\n'); dim=size(A); y=zeros(dim(2),1); k=1; band=0; while k...