tema 1 metodos matematicos sistemas lineales
TRANSCRIPT
1
Tema 1: Sistemas de Ecuaciones Lineales.
Dpto. de Matemáticas. Prof. Doctor Fernando Mallo Fernández
Métodos Matemáticos.
2º ciclo de INGENIERÍA INDUSTRIAL, 2012-2013
Índice
1. Introducción 3 1.1 Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Conceptos Básicos en Sistemas de Ecuaciones Lineales . . . . . 6 1.3 Existencia y Unicidad de Solución en S.E.L. Teorema de
Rouché-Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Sistemas Homogéneos y Sistemas de Cramer . . . . . . . . . . . . . 18 1.4.1 Sistemas Homogéneos. . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4.2 Sistemas de Cramer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5 Métodos Ingenuos para resolver Sistemas Lineales. . . . . . . . . 21 1.5.1 1−=x A b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.5.2 Regla de Cramer 21 1.5.3 Solución de Sistemas Lineales Diagonales . . . . . . . . . 22 2. Métodos directos para resolver sistemas de ecuaciones
lineales 22
2.1 Resolución de Sistemas Lineales Triangulares Superiores . . . 23 2.2 Métodos de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.1 Método de Eliminación Simple de Gauss . . . . . . . . . . 31 2.2.2 Método de Gauss con pivote parcial . . . . . . . . . . . . . . 43 2.2.3 Método de Gauss con pivote total . . . . . . . . . . . . . . . . 49 2.2.4 Método de Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . . 50 2.2.5 Método de Factorización LU de Gauss . . . . . . . . . . . . 52 2.2.6 Inconvenientes de los métodos de Gauss. . . . . . . . . . 55 2.2.7 Condicionamiento de sistemas lineales . . . . . . . . . . . 56 2.3 Método de Mínimos Cuadrados . . . . . . . . . . . . . . . . . . . . . . . . . 57 3. Métodos Iterativos para resolver sistemas de ecuaciones
lineales
64 3.1 Método de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.2 Método de Gauss-Seidel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.3 Métodos de Relajación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2
3
1. Introducción. Comenzaremos este tema exponiendo de forma breve la motivación de los
sistemas de ecuaciones lineales reales; a continuación se presentan los elementos teóricos básicos, con un lenguaje de fácil comprensión y, al final de cada exposición teórica, se resuelven varios ejercicios con la finalidad de permitir a los
alumnos adaptarlos a sus necesidades en aplicaciones a la ingeniería
industrial.
1.1 Motivación
Un problema muy común y de gran relevancia en las ciencias y las ingenierías consiste en la resolución de sistemas de ecuaciones lineales. Hasta la llegada de los computadores digitales (segunda mitad del s. XX) la capacidad de resolver sistemas de ecuaciones lineales estaba muy limitada, no por la dificultad conceptual del problema, sino por el gran número de operaciones aritméticas necesarias. Ahora se puede resolver con un PC un sistema 1000×1000 en menos de 1 segundo. Con programas especiales que aprovechan la estructura de la matriz se pueden resolver con PCs, de forma rutinaria, sistemas de decenas ó cientos de miles de ecuaciones lineales.
Muchos otros métodos matemáticos (cálculo de valores y vectores propios, integración de ecuaciones diferenciales, optimización,...) se reducen a la resolución repetida de sistemas de ecuaciones lineales.
El problema de los sistemas de ecuaciones lineales es uno de los más antiguos de la matemática y tiene una infinidad de aplicaciones, como en procesamiento digital de señales, análisis estructural, estimación, predicción y más generalmente en programación lineal así como en la aproximación de problemas no lineales de análisis numérico. Como consecuencia, en este tema veremos algunos de los métodos más usuales para encontrar la solución simultánea a esas ecuaciones.
Antes de hacer la presentación de los métodos de solución de sistemas de ecuaciones lineales, es importante tener claro el concepto de raíz ó solución de las mismas, concepto que se formaliza en la definición siguiente:
Definición. 1.1. a) En matemáticas y álgebra lineal, un sistema de
ecuaciones lineales, también conocido como sistema lineal de ecuaciones o simplemente sistema lineal, es un conjunto de ecuaciones lineales (es decir, un sistema de ecuaciones en donde cada ecuación es de primer grado), definidas sobre un cuerpo (por ejemplo los números reales) o un anillo conmutativo.
b) Llamaremos solución del sistema a todo conjunto de números 1 2, ,..., ns s s que
reemplazados en 1 2, ,..., nx x x haga verdaderas simultáneamente las m ecuaciones
del sistema.
4
En general, un sistema con m ecuaciones lineales y n incógnitas puede ser escrito en forma normal como:
(1)
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
...
...
... ... ... ... ...
...
n n
n n
m m mn n m
a x a x a x b
a x a x a x b
a x a x a x b
+ + + = + + + = + + + =
donde 1 2, ,..., nx x x son las incógnitas, (todas elevadas a la primera potencia, de
ahí el calificativo de lineales para estos sistemas), los números reales
, 1,..., , 1,...,ija i m j n∈ = =ℝ son los coeficientes del sistema sobre ℝ , y los
números reales ib ∈ℝ son los términos independientes de cada ecuación del
sistema.
Un sistema de ecuaciones lineales del tipo (1) no consiste más que en una formalización (o abstracción) de una realidad de tipo físico, como puede observarse en el ejemplo siguiente
Ejemplo 1.1. Sistema de ecuaciones lineales.
a) CIRCUITO ELÉCTRICO QUE ORIGINA EL SISTEMA (1)
b) SISTEMA EXPRESADO EN NOTACIÓN
MATEMÁTICA.
i1 - i2 - i3 = 0 - i1 + i2 + i3 = 0
5i1 + 5i3 = 0 10i2 - 5i3 = 16
5i1 + 10i2 = 26
a) Estamos ante un circuito eléctrico que genera un sistema de ecuaciones lineales donde las incógnitas son las corrientes i1, i2 e i3. Para plantear el sistema basta con tener en cuenta que los circuitos eléctricos se rigen por las leyes de Kirchhoff:
-Primera ley de Kirchhoff
La suma algebraica de corrientes en un nodo es igual a cero.
La suma de corrientes en el nodo A es cero: i1-i2-i3=0
La suma de corrientes en el nodo B es cero: i3+i2-i1=0
-Segunda ley de Kirchhoff
En una malla cerrada la suma de caídas de tensión es igual a la suma de fuerzas eléctricas aplicadas.
En la malla cerrada BCAB 5i1+5i3=0
5
En la malla cerrada BADB -5i3+10i2=16
En la malla cerrada BCADB 5i1+10i2=26
El signo − en la cuarta ecuación se debe a que la corriente va en sentido contrario, al sentido en que se recorre la malla.
Como resultado se obtiene el sistema de ecuaciones:
i1 - i2 - i3 = 0 i3 + i2 - i1 = 0 5i1 + 5i3 = 0 -5i3 + 10i2 = 16 5i1 + 10i2 = 26
b) El sistema viene dado en la forma algebraica convencional.
El problema consiste en encontrar los valores desconocidos de las variables i1, i2, i3 que satisfacen simultáneamente las cinco ecuaciones y es una abstracción formal del circuito eléctrico descrito en b). Es decir, un sistema lineal de ecuaciones donde las incógnitas son las corrientes i1, i2 e i3.
Es posible reescribir el sistema (1) en notación matricial en la forma:
(2)
� �
11 12 1 1 1
21 22 2 2 2
1 2
n
n
m m mn n m
X BA
a a a x b
a a a x b
a a a x b
=
⋯
⋯
⋮ ⋮ ⋱ ⋮ ⋮ ⋮
⋯��������
es decir, =Ax b , donde A es la matriz de los coeficientes del sistema, de
dimensión m por n, X es el vector columna de soluciones, de “longitud” n, y b es el vector columna de términos independientes, de ”longitud” m.
(3) ( )11 12 1 1
21 22 2 2
1 2
n
n
m m mn m
a a a b
a a a b
a a a b
=
⋯
⋯
⋮ ⋮ ⋱ ⋮ ⋮
⋯
A | b
Las matrices A y ( )Ab son llamadas respectivamente de los coeficientes (o
incompleta) y ampliada (o completa). La matriz ampliada contiene toda la
información del sistema: cada fila corresponde a una ecuación.
Designando por ( ) ( ) ( ):,1 , :, 2 ,..., :,nA A A , las columnas de la matriz A , el
sistema puede escribirse alternativamente en la forma:
6
(4)
11 12 1 1
21 22 2 2
1 2
1 2
...
n
n
n
m m mn m
a a a b
a a a bx x x
a a a b
+ + + =
⋮ ⋮ ⋮ ⋮
⇒ ( ) ( ) ( )1 2:,1 :, 2 ... :, nx x n x+ + + =A A A b
Ejemplo 1.2. Escribir en forma matricial y vectorial el sistema
1 2 3 4
1 2 3 4
1 3 4
1 2 3
4 3 5 0
6 8 2 5
2
2 5 2
x x x x
x x x x
x x x
x x x
+ − + =
− + − =
− + = − + − =
Forma matricial:
1
2
3
4
4 3 5 1 0
6 8 1 2 5
1 0 1 1 2
2 1 5 0 2
x
x
x
x
− − = − − −
Forma vectorial: 1 2 3 4
4 3 5 1 0
6 8 1 2 5
1 0 1 1 2
2 1 5 0 2
x x x x
− − − + + + = − − −
Estudiaremos dos cuestiones, una se refiere a la existencia y unicidad de estas soluciones y otra a los métodos para hallarlas.
1.2 Conceptos básicos en sistemas de ecuaciones lineales.
En esta sección se analizan algunos conceptos y propiedades de los sistemas de ecuaciones lineales en los coeficientes de las ecuaciones son números reales, es decir, sobre el cuerpo ℝ .
Para introducir de forma sencilla los sistemas lineales reales consideremos el siguiente ejemplo de sistema de dos ecuaciones con dos incógnitas:
(5) 1 2
1 2
3 22
4 3 1
x x
x x
+ =
− = −
Como sabemos existen tres métodos para resolver este sistema: Sustitución, Igualación y Reducción.
El método de sustitución consiste en despejar en una de las ecuaciones cualquier incógnita, preferiblemente la que tenga menor coeficiente, para, a continuación, sustituirla en otra ecuación por su valor. En caso de sistemas con más de dos incógnitas, la seleccionada debe ser sustituida por su valor equivalente en todas las ecuaciones excepto en la que la hemos despejado. En ese
7
instante, tendremos un sistema con una ecuación y una incógnita menos que el inicial, en el que podemos seguir aplicando este método reiteradamente. Por ejemplo, supongamos que queremos resolver por sustitución el sistema (5).
En la primera ecuación del sistema (5), seleccionamos la incógnita 2x por ser
la de menor coeficiente y que posiblemente nos facilite más las operaciones, y la despejamos, obteniendo la siguiente ecuación.
2 122 3x x= −
El siguiente paso será sustituir cada ocurrencia de la incógnita 2x en la otra
ecuación, para así obtener una ecuación donde la única incógnita sea 1x .
( )1 1 1 1 1 1 14 3 22 3 1 4 66 9 1 13 66 1 9 13 65x x x x x x x− − = − ⇒ − + = − ⇒ − = − + ⇒ =
de donde se obtiene la solución 1 5x = , y si ahora sustituimos esta incógnita por
su valor en alguna de las ecuaciones originales obtenemos 2 7x = , con lo que el
sistema queda resuelto.
El método de igualación se puede entender como un caso particular del método de sustitución en el que se despeja la misma incógnita en dos ecuaciones y a continuación se igualan entre sí la parte derecha de ambas ecuaciones.
2 122 3x x= −
( )1
2
4 1
3
xx
+=
( )1
2 1 1 1 1 1
4 122 3 66 9 4 1 13 65 5
3
xx x x x x x
+= − = ⇒ − = + ⇒ = ⇒ =
Una vez obtenido el valor de la incógnita 1x , se substituye su valor en una de
las ecuaciones originales, y se obtiene el valor 2 7x = .
El método de reducción suele emplearse mayoritariamente en los sistemas lineales, siendo pocos los casos en que se utiliza para resolver sistemas no lineales. El procedimiento, que ilustraremos para sistemas con dos ecuaciones e incógnitas, consiste en transformar una de las ecuaciones (generalmente, mediante productos), de manera que obtengamos dos ecuaciones en la que una misma incógnita aparezca con el mismo coeficiente y distinto signo. A continuación, se suman ambas ecuaciones produciéndose así la reducción o cancelación de dicha incógnita, obteniendo así una ecuación con una sola incógnita, donde el método de resolución es simple.
Utilizando este método
primera ecuación por 3
dicha ecuación nos queda así:
(3 3 3 * 22 9 3 66
Si sumamos esta ecuación a la segunda del sistema original, obtenueva ecuación donde la incógnita
directamente el valor de la incógnita
1 5x = , de donde 2 220 3 1 0 7x x− + =
Como podemos ver, el sistema tiene solución, encontrado por los tres métodos utilizados, y además esta solución es única, sistema determinado. En estos sistemas compatibles y linealmente indepedos rectas que se intersecan y su solución es el único punto de intersección.
___ 2 1x x
FIGURA 1. Solución única. Coincide con la intersección de ambas rectas.
Pero no siempre que el sistema tiene solución ésta es única (s
compatible indeterminado
incompatible. Veamos el primer caso:
Utilizando este método en el sistema (5) no tenemos más que multiplicar la
para poder cancelar la incógnita 2x .
dicha ecuación nos queda así:
( )1 2 1 23 3 3 * 22 9 3 66x x x x+ = ≈ + =
Si sumamos esta ecuación a la segunda del sistema original, obtenueva ecuación donde la incógnita y ha sido reducida y que, en este caso, nos da
directamente el valor de la incógnita 1x :
1 2
1 2
1
9 3 66
4 3 1
13 65
x x
x x
x
+ =
− = −
=
2 220 3 1 0 7x x− + = ⇒ = .
mo podemos ver, el sistema tiene solución, sistema compatible
por los tres métodos utilizados, y además esta solución es única, En estos sistemas las ecuaciones son consistentes o
compatibles y linealmente independientes, su representación gráfica rectas que se intersecan y su solución es el único punto de intersección.
1 2
1 2
3 22
4 3 1
x x
x x
+ =
− = −
2 122 3x x= − ___ ( )1
2
4 1
3
xx
+=
Solución única. Coincide con la intersección de ambas rectas.
Pero no siempre que el sistema tiene solución ésta es única (scompatible indeterminado), e incluso puede no tener solución,
. Veamos el primer caso:
8
enemos más que multiplicar la
Al multiplicar,
Si sumamos esta ecuación a la segunda del sistema original, obtenemos una ha sido reducida y que, en este caso, nos da
sistema compatible, que hemos por los tres métodos utilizados, y además esta solución es única,
as ecuaciones son consistentes o ndientes, su representación gráfica consiste en
rectas que se intersecan y su solución es el único punto de intersección.
Solución única. Coincide con la intersección de ambas rectas.
Pero no siempre que el sistema tiene solución ésta es única (sistema
), e incluso puede no tener solución, sistema
Resolvemos por el método de por 2 y sumando la segunda ecuación se obtiene:
es decir, cualquier valor de
existen infinitas solucioneso compatibles, pero son linealmente dependientes. En su representación gráfica una recta queda sobre la otra, por lo que su solución elos puntos de la recta, es decir
___ x
FIGURA 1. Infinitas soluciones.
En el tercer caso, no existe
por sustitución tenemos, de la primera ecuación:
1 2
1 2
2 3 12
4 6 24
x x
x x
+ =
− − = −
el método de reducción, multiplicando la primera ecuación sumando la segunda ecuación se obtiene:
1 2
1 2
1 2
4 6 24
4 6 24
0 0 0
x x
x x
x x
+ =− − = −
+ =
s decir, cualquier valor de 1x y de 2x satisface la ecuación
existen infinitas soluciones. En este caso también las ecuaciones son consistentes o compatibles, pero son linealmente dependientes. En su representación gráfica una recta queda sobre la otra, por lo que su solución está representada por todos
, es decir, el sistema es compatible pero indeterminado
1 2
1 2
2 3 12
4 6 24
x x
x x
+ =
− − = −
12
12 2
3
xx
−= ___ 12
24 4
6
xx
−=
Infinitas soluciones. Las dos rectas son coincidentes
no existe ninguna solución, se encuentra el sistema siguiente:
1 2
1 2
2 3 12
4 6 6
x x
x x
+ =
+ =
or sustitución tenemos, de la primera ecuación:
21
12 3
2
xx
−=
9
la primera ecuación
satisface la ecuación y por tanto
En este caso también las ecuaciones son consistentes o compatibles, pero son linealmente dependientes. En su representación gráfica
stá representada por todos , el sistema es compatible pero indeterminado.
Las dos rectas son coincidentes.
ninguna solución, se encuentra el sistema siguiente:
sustituyendo en la segunda e
212 34 6 6 24 6 6 6 24 6
2
x−
evidentemente esto es una contradicción
satisfaga la igualdad, por lo que concluimos que no existe ninguna solución para el sistema, por tanto estamos ante un sistema incompatibleinconsistentes o incompatibles
Los sistemas incompatibles geométricamente se caracterizan por rectas que no se cortan.
___
En general el sistema de ecuaciones lineales interpretaciones siguientes:
1. Intersección de hiperplanosque satisface las ecuaciones de todos los hiperplanos, es decir, su intersección. La intersección puede ser un punto, un subespacio de dimensión vacío. Graficamente:
ustituyendo en la segunda ecuación se tiene:
22 2 2
12 34 6 6 24 6 6 6 24 6
2
xx x x
+ = ⇒ − + = ⇒ =
,
evidentemente esto es una contradicción ⇒ no existe ningún valor de
satisfaga la igualdad, por lo que concluimos que no existe ninguna solución para mos ante un sistema incompatible, (las ecuaciones son
inconsistentes o incompatibles).
Los sistemas incompatibles geométricamente se caracterizan por rectas que
1 2
1 2
2 3 12
4 6 6
x x
x x
+ =
+ =
___ 21
12 3
2
xx
−= ___ 12
6 4
6
xx
−=
sistema de ecuaciones lineales =Ax b admite al menos las dos interpretaciones siguientes:
hiperplanos. La solución es el punto (o conjunto de puntos) es de todos los hiperplanos, es decir, su intersección. La
intersección puede ser un punto, un subespacio de dimensión n−r
FIGURA 1.
10
4 6 6 24 6 6 6 24 6
no existe ningún valor de 2x que
satisfaga la igualdad, por lo que concluimos que no existe ninguna solución para as ecuaciones son
Los sistemas incompatibles geométricamente se caracterizan por rectas que
admite al menos las dos
. La solución es el punto (o conjunto de puntos) es de todos los hiperplanos, es decir, su intersección. La
r, o el conjunto
11
2. Combinación lineal de vectores. El vector término independiente b es una combinación lineal de las columnas de A , cuyos coeficientes son los valores de x, tal como se muestra en la expresión (4).
La expresión (4) indica que para que el sistema de ecuaciones =Ax b tenga
solución, es necesario y suficiente que el vector b pertenezca a ( )Im A , es decir, al
subespacio generado por las columnas de A . La solución será única si hay una única forma de expresar b como combinación lineal de las columnas de A .
FIGURA 2.
Un sistema con n incógnitas se puede representar en el n-espacio correspondiente.
En los sistemas con 2 incógnitas, como hemos visto, el universo de nuestro sistema será el plano bidimensional, mientras que cada una de las ecuaciones será representada por una recta, si es lineal, o por una curva, si no lo es. La solución será el punto (o línea) donde se intersequen todas las rectas y curvas que representan a las ecuaciones. Si no existe ningún punto en el que se intersequen al mismo tiempo todas las líneas, el sistema es incompatible, o lo que es lo mismo, no tiene solución.
FIGURA 3. Algunos casos posibles del sistema =AX b en 2ℝ .
12
Como ejemplo ilustrativo en la Figura 3 se muestran geométricamente
algunos casos posibles de sistemas de ecuaciones en 2ℝ , teniendo en cuenta los números de ecuaciones, m, y de incógnitas, n, el rango de la matriz A , r, y el vector b . La interpretación es inmediata en la línea de la solución del sistema (4) que hemos expuesto.
Como hemos visto, los sistemas de ecuaciones lineales 2 2× o 3 2× se expresan gráficamente como rectas que pueden estar en tres casos. De igual manera las ecuaciones lineales de tres incógnitas se expresan en un sistema tridimensional con ejes ortogonales, (ejes que están mutuamente a 90º), como un plano infinito no curvado. Por supuesto que no podemos dibujar un plano infinito, por lo que sólo dibujaremos una parte de los planos. De nuevo, de acuerdo con las posibles relaciones que se pueden dar entre los tres planos, se determina el tipo de solución que tiene el sistema:
1. Tres planos que se cortan en un punto o en una recta. Este es el caso en que todos los planos intersecan en un único punto, en cuyo caso las coordenadas de este serán la solución al sistema, o también cuando la intersección de todos ellos es una recta, en este caso el sistema tendrá infinitas soluciones, las coordenadas de los puntos que forman dicha línea.
Sistema 3x3 con solución única en el punto (x, y, z)
Sistema 3x3 con planos coincidiendo en una línea. Infinidad de soluciones .
FIGURA 4. Tres planos que se cortan en un punto o en una recta. 2. Tres planos superpuestos. Este es el caso en que todos los planos intersecan
en un plano, este caso el sistema tendrá infinitas soluciones, que serán las coordenadas de los puntos que forman dicha superficie.
FIGURA 5. Tres planos superpuestos. Las tres ecuaciones que representan al mismo plano. Infinidad de soluciones (puntos en común en el plano)
13
3. Haz de planos paralelos.
Sistema 3x3 con planos paralelos. Sin solución.
Sistema 3x3 con dos planos paralelos. Sin solución.
FIGURA 6. Planos paralelos. En este caso el sistema no tiene solución.
Para sistemas de 4 ó más incógnitas, la representación gráfica no existe, por lo que dichos problemas no se enfocan desde esta óptica.
Como hemos visto tanto para sistemas 2 2× como para sistemas 3 3× pueden suceder tres casos: que el sistema no tenga solución, que tenga infinidad de soluciones o tenga solución única. Estos tres casos se generalizan a todos los sistemas de ecuaciones lineales, no sólo a los 2 2× o 3 3× .
1.3 Existencia y unicidad de solución en sistemas lineales. Teorema de Rouché-Frobenius.
Podemos generalizar a sistemas de m ecuaciones lineales con n incógnitas en la forma siguiente:
Una forma habitual de clasificar los sistemas de ecuaciones se basa en el número de soluciones, hecho con respecto al cual se pueden presentar los siguientes casos:
• Sistema incompatible si no tiene solución. Los sistemas incompatibles geométricamente se caracterizan por (hiper)planos o rectas que se cruzan sin cortarse.
• Sistema compatible si tiene solución, en este caso además puede distinguirse entre:
o Sistema compatible determinado cuando tiene una única solución. Los sistemas compatibles determinados se caracterizan por un conjunto de (hiper)planos o rectas que se cortan en un único punto.
o Sistema compatible indeterminado cuando admite un conjunto infinito de soluciones. Los sistemas compatibles indeterminados se
14
caracterizan por (hiper)planos que se cortan a lo largo de una recta [o más generalmente un hiperplano de dimensión menor].
DeterminadosCompatibles
Indeterminados
Incompatibles
Sistemas
Vamos a estudiar un teorema que permite conocer si un sistema de ecuaciones tiene solución a partir del estudio del rango de la matriz asociada al sistema (matriz de coeficientes A ) y del rango de la matriz ampliada de éste
(matriz ( )Ab ), el teorema de Rouché-Frobenius. Recordemos previamente
algunos conceptos de álgebra lineal: rango de una matriz, vectores linealmente independientes,
Definición. 1.2. a) Un conjunto de vectores es linealmente independiente si ninguno de ellos puede ser escrito con una combinación lineal de los restantes.
Por ejemplo, en 3ℝ , el conjunto de vectores ( ) ( ) ( )1, 0, 0 , 0, 1, 0 y 0, 0, 1 es
linealmente independiente, mientras que ( ) ( )(2, 1, 1), 1, 0, 1 y 3, 1, 2− − son
linealmente dependientes, ya que el tercero es la suma de los dos primeros.
c) El rango columna (filas) de una matriz A es el número máximo de columnas (filas de A respectivamente) que son linealmente independientes. Este rango es la dimensión del espacio columna de A (dimensión del espacio fila respectivamente).
d) Si el rango fila y columna son iguales, este número es llamado
simplemente rango de A y comúnmente se expresa como ( )rg A .
El rango de A será, por tanto, mayor o igual que uno y menor o igual que el mínimo entre m y n.
Teorema 1.1 (Rouché-Frobenius). Dado un sistema de m ecuaciones lineales con n incógnitas, =Ax b , se tiene:
a) =Ax b es compatible ⇔ ( ) ( )rg rg r= =A Ab .
b) Además, el sistema es determinado
el sistema es indeterminado
r n
r n
= ⇒ < ⇒
Los apartados a) y b) del teorema se sintetizan en el siguiente cuadro:
( ) ( )
( ) ( )
DeterminadoSistema Compatible
Indeterminado
Sistema Incompatible
r nrg rg r
r n
rg rg
= ⇒= = ⇒ < ⇒
≠ ⇒
A Ab
A Ab
15
Demostración:
a) Como sabemos el sistema puede escribirse en forma vectorial
(6) ( ) ( ) ( )1 2:,1 :, 2 ... :, nx x n x+ + + =A A A b
Demostraremos primero la condición necesaria (⇒⇒⇒⇒)))):
⇒⇒⇒⇒) Si el sistema es compatible, existe al menos una solución ( )1 2, ,..., ns s s
tal que ( ) ( ) ( )1 2:,1 :, 2 ... :, ns s n s+ + + =A A A b , por lo tanto el vector de los términos
independientes es combinación lineal de las columnas de la matriz de los
coeficientes A ⇒ ( ) ( )rg rg r= =A Ab .
A continuación demostraremos la condición suficiente:
⇐⇐⇐⇐) Si ( ) ( )rg rg=A Ab , entonces la columna de los términos independientes
es combinación lineal de las columnas de la matriz A y por tanto existen n
números reales 1 2, ,..., ns s s tales que
( ) ( ) ( )1 2:,1 :, 2 ... :, ns s n s= + + +b A A A
Por tanto ( )1 2, ,..., ns s s es una solución del sistema ⇒ el sistema es
compatible.
b) (Ejercicio a realizar por el alumno).
Desde un punto de vista algebraico, tal como se expresa en el siguiente corolario del teorema de Rouché-Frobenius, los sistemas compatibles determinados se caracterizan porque el determinante de la matriz de coeficientes es diferente de cero, los sistemas compatibles indeterminados porque tal determinante es igual a cero (y por tanto uno de sus autovalores será 0) y una condición necesaria para que un sistema sea incompatible es también que el determinante de la matriz de coeficientes sea igual a cero.
Corolario 1.1
a) El sistema =Ax b es compatible determinado ⇔ ( ) 0det ≠A .
b) El sistema =Ax b es compatible indeterminado ⇔ ( ) 0det =A .
c) Si sistema =Ax b es incompatible ⇒ ( ) 0det =A .
Demostración.
a) =Ax b es compatible determinado ⇔ ( ) ( )rg rg n= =A Ab ⇔ 1−=x A b ⇔
Existe 1−A ⇔ ( ) 0det ≠A .
16
b) =Ax b es compatible indeterminado ⇔ ( ) ( )rg rg n= <A Ab ⇔ ( ) 0det =A .
c) =Ax b incompatible ⇒ ( ) ( )rg rg<A Ab . Una condición necesaria para que
esto suceda es que el determinante de la matriz del sistema sea cero.
Nota: En los sistemas del tipo =Ax b la solución genérica consiste en expresar una o más variables como función matemática del resto. En los sistemas lineales compatibles indeterminados, al menos una de sus ecuaciones se puede hallar como combinación lineal del resto, es decir, es linealmente dependiente. De hecho, de las dos condiciones anteriores se desprende, que el conjunto de soluciones de un sistema compatible indeterminado es un subespacio vectorial. Y la dimensión de ese espacio vectorial coincidirá con la multiplicidad geométrica del autovalor cero.
Ejemplo 1.3. Solución, usando SCILAB, del sistema siguiente:
(7) 1 2 3
1 2 3
1 2 3
2 3 9
4 5 6 24
3 2 4
x x x
x x x
x x x
+ + =
+ + = + − =
Número de ecuaciones: n=3, Número de incógnitas: m=3
Matriz del sistema:
1 2 3
4 5 6
3 1 2
= −
A ,
Vector de términos independientes: ( )9, 24, 4T =b
17
Matriz ampliada
Discusión del sistema. (Teorema de Rouche-Frobenius).
1.- ¿
( ) ( )rg rg r= =A Ab ?
Se tiene ( ) ( ) 3rg rg n= = =A Ab , por tanto, por el teorema de Rouche-
Frobenius, el sistema =Ax bes compatible y determinado, y por el corolario 1.1
se verifica que ( ) 0det ≠A lo que implica que la solución venga dada por 1−=x A b .
Comprobamos que ( ) 0det ≠A y, por tanto, la existencia de 1−A .
18
A continuación requerimos a SCILAB la solución del sistema:
1.4. Sistemas Homogéneos y Sistemas de Cramer.
1.4.1 Sistemas Homogéneos
Definición. 1.3. Un sistema de ecuaciones lineales se dice homogéneo si los términos independientes son todos nulos, es decir, su expresión matricial adopta la forma =Ax 0 .
Corolario 1.2
a) = 0Ax es siempre un sistema compatible.
b) La solución nula o trivial 1 20, 0,..., 0ns s s= = = , es siempre
solución del sistema = 0Ax .
c) Si ( )rg n=A ⇒ El sistema es compatible determinado y la única
solución es la trivial.
d) Si ( )rg n<A ⇒ Sistema compatible indeterminado, y en este caso
tiene infinitas soluciones, además de la solución trivial.
Demostración: Aplicando el teorema de Rouché-Frobenius a un sistema homogéneo se tiene:
a) Si el sistema es homogéneo se tiene b = 0 y ( ) ( )rg rg=A0 ARouché Frobenius−
⇒
= 0Ax compatible.
b) Obviamente =A0 0 .
19
c) Por ser un sistema homogéneo, por a) es un sistema compatible y además
se verifica ( ) ( )rg rg n= =A0 A ⇒ El sistema es compatible determinado y, por
tanto, la única solución es la trivial, pues esta, por b) lo es siempre en un sistema homogéneo.
d) Es consecuencia inmediata del teorema de Rouché-Frobenius.
1.4.2 Sistemas de Cramer.
Definición. 1.4. Un sistema de ecuaciones lineales es un Sistema de
Cramer si el número de ecuaciones es igual al de incógnitas y el determinante de la matriz de los coeficientes del sistema es distinto de cero, es decir, es compatible determinado.
Ejemplo 1.4 : El sistema 1 2
1 2
2 3 4
2 0
x x
x x
− =
+ =
es de Cramer pues el número de
ecuaciones es igual al de incógnitas y 2 3
7 01 2
−= ≠ .
Proposición. 1.1 Todo Sistema de Cramer =Ax b es compatible deter-
minado.
Demostración: Dado que =Ax b es de Cramer ⇒ ( )det 0≠A ⇒ Existe 1−A y, por
lo tanto: 1 1 1− − −= ⇒ =A Ax A b x A b , es decir, la solución es única.
A continuación vamos estudiar la Regla de Cramer que consiste en un teorema en álgebra lineal que da la solución de un sistema lineal de ecuaciones de Cramer en términos de determinantes adjuntos. Recibe este nombre en honor a Gabriel Cramer (1704 - 1752), quien publicó la regla en su Introduction à l'analyse des lignes courbes algébriques de 1750.
La regla de Cramer da una solución para sistemas compatibles determinados en términos de determinantes y adjuntos.
Teorema 1.2- (Regla de Cramer). Si =Ax b es un sistema de Cramer de
n ecuaciones con n incognitas, , 1,...,j j n∀ = , la solución jx viene dada por
(8) ( )( )
det
det
j
j =A
xA
donde jA es la matriz resultante de remplazar la j-ésima columna de A por el
vector columna b .
20
Ejemplo 1.5 Para el sistema de tres ecuaciones y tres incógnitas (7):
1 2 3
1 2 3
1 2 3
2 3 9
4 5 6 24
3 2 4
x x x
x x x
x x x
+ + =
+ + = + − =
Matriz del sistema:
1 2 3
4 5 6
3 1 2
= −
A
Vector de términos independientes:
9
24
4
=
b
1 2 3
9 2 3 1 9 3 1 2 9
24 5 6 , 4 24 6 , 4 5 24
4 1 2 3 4 2 3 1 4
= = = − −
A A A
-->A=[1,2,3;4,5,6;3,1,-2];
-->A1=[9,2,3;24,5,6;4,1,-2];
-->A2=[1,9,3;4,24,6;3,4,-2];
-->A3=[1,2,9;4,5,24;3,1,4];
-->dA=det(A), dA1=det(A1), dA2=det(A2), dA3=det(A3)
dA = 3.
dA1 = 12.
dA2 = 9.
dA3 = - 6.
La regla de Cramer da la siguiente solución:
->x1=dA1/dA, x2=dA2/dA, x2=dA3/dA
x1 = 4.
x2 = 3.
x3 = -2.
21
1.5 Métodos ingenuos para resolver S.E. Lineales.
1.5.1 1−=x A b
Teóricamente, resolver el sistema =Ax b es equivalente a la expresión 1−=x A b , es suficiente, por tanto, calcular la matriz inversa de A para obtener la
solución del sistema, lo que nos induce a pensar ingenuamente que el problema está resuelto. ¿Porqué ingenuamente?, vamos a responder a esta cuestión.
Calcular la inversa de una matriz de dimensión 100x100 es mucho más costoso que resolver un sistema de 100 ecuaciones con 100 incógnitas por ciertos métodos apropiados, por esta razón para problemas reales de cierta envergadura, esta opción de resolución sólo se utiliza en deducciones teóricas, o, en muy raros
casos, cuando 1−A se obtiene muy fácilmente.
1.5.2 Regla de Cramer.
Otro método que podría utilizarse para resolver =Ax b es la regla de Cramer, descrita anteriormente. En la solución del sistema de orden 3 del ejemplo 1.5 se ven involucrados 4 determinantes, det(A), det(A1), det(A2), det(A3). Si suponemos que cada determinante se calcula por medio de
cofactores. Este cálculo se puede hacer utilizando cualquier fila o cualquier columna; utilizando la primera fila,
( ) 22 23 21 23 21 22
11 12 13
32 33 31 33 31 32
det det deta a a a a a
det a a aa a a a a a
= − +
A
En general, sea Mij la matriz (n−1)×(n−1) obtenida al suprimir de A la fila i y la columna j. Si se calcula det(A) utilizando la primera fila,
det(A)= a11 det(M11) − a12 det(M12) + � � � + (−1)(1+n) a1n det(M1n).
Sea µn el número de multiplicaciones necesarias para calcular, por cofactores, el determinante de una matriz de orden n. La fórmula anterior indica que µn > nµn−1. Como a su vez, µn−1 > (n−1)µn−2 y µn−2 > (n−2)µn−3, ..., entonces µn > n(n−1)(n−2) � � � µ2 = n(n−1)(n−2) � � � 2 ⇒ µn > n! .
dado que para resolver un sistema de n ecuaciones con n incógnitas por la regla de Cramer hay que calcular n+1 determinantes, entonces el número total de multiplicaciones necesarias para obtener la solución es superior a (n+1)!.
Consideremos un sistema, relativamente pequeño, n = 20, en este caso el número total de multiplicaciones necesarias para obtener la solución es
superior a 21! = 5.1091E19. Siendo muy optimistas (sin tener en cuenta las sumas y otras operaciones concomitantes), supongamos que un computador hace 1000 millones de multiplicaciones por segundo. Entonces, el tiempo necesario para resolver el sistema por la regla de Cramer y el método de cofactores es:
tiempo > 5.1091E10 segundos = 16.2 siglos
22
1.5.3 Solución de Sistemas Lineales Diagonales.
Un caso particularmente sencillo de resolver, y poco frecuente en la práctica, es el de un Sistema Diagonal, caracterizado por que su matriz de coeficientes es diagonal, =Dx b , (todos los elementos fuera de la diagonal tienen valor cero,
( ) 0,
0,
ij
ij
ij
d i jd ,
d i j
= ≠ ≠ =
D = ). Dado que para matrices triangulares, y en particular
para las diagonales, el determinante es el producto de los n elementos diagonales,
( )1,...,
iii n
det d=ΠD = , la matriz triangular es invertible si y solamente si todos los
elementos diagonales son diferentes de cero.
Por el teorema de Cramer, por ser ( ) 0det ≠D , la solución jx del sistema
=Dx b viene dada por ( )( )
det
det
j
j =D
xD
, donde jD es la matriz resultante de
remplazar la j-ésima columna de D por el vector columna b , es decir,
( )( )
11 22
11 22
det . ... ...
det . ... ...
j j nn j
j
jj nn jj
d d b d b
d d d d d= = =
Dx
D
Como los elementos diagonales son no nulos, no hay ningún problema para efectuar las divisiones.
2. Métodos directos para resolver Sistemas de Ecuaciones Lineales.
La existencia y unicidad de la solución de un sistema de ecuaciones lineales
está resuelta por el teorema de Rouché-Frobenius y en el caso de un sistema de n
ecuaciones con n incógnitas =Ax b , compatible y determinado, ( ( )rg n=A ,
existe -1A ), la solución viene dada por la regla de Cramer. El problema, por tanto, estaría resuelto de no ser porque la regla de Cramer resulta impracticable en muchos problemas reales donde n puede alcanzar un valor muy elevado.
Obtener la solución de forma directa a través de la expresión 1−=x A b puede resultar también tarea imposible por la misma razón. Por otro lado, los sistemas más fáciles de resolver, los sistemas diagonales, son escasos en el mundo real. Afortunadamente nos que aún una baza, los sistemas triangulares, sean superiores o inferiores, son muy fáciles de resolver y sin excesivas operaciones, es decir los métodos basados en estos sistemas, Gauss con o sin pivotes, Gauss-Jordan y la descomposición factorial LU de Gauss son más "económicos" en número de operaciones.
Los métodos directos se caracterizan por el hecho de que, si no hubiera errores de redondeo, se obtendría la solución exacta del sistema en un número finito de operaciones.
En este apartado analizaremos la obtención directa de la solución, en el caso
de que exista 1−=x A b , y la problemática asociada a la utilización de la Regla de
23
Cramer, ambos métodos conocidos como ingenuos. Por otro lado, estudiaremos métodos más apropiados para obtener la solución, tales como los métodos de
eliminación de Gauss (con o sin pivote), el método de eliminación de
Gauss-Jordan, el método de Gauss de factorización LU y el Método de
mínimos cuadrados.
2.1 Resolución de Sistemas Lineales Triangulares Superiores.
Los métodos directos no ingenuos que estudiaremos se basan principal-mente en los conceptos de sistemas equivalentes y sistemas triangulares.
Definición 1.5. Dos sistemas de ecuaciones lineales son equivalentes si toda solución de uno es también solución del otro.
Algunas de las operaciones que se pueden aplicar a un sistema, de manera que se obtenga un sistema equivalente, son las siguientes:
1. Intercambiar dos ecuaciones. 2. Multiplicar una ecuación por un número distinto de cero. 3. Añadir a una ecuación un múltiplo no nulo de otra.
Aplicar las operaciones arriba indicadas a un sistema, equivale a aplicar las correspondientes transformaciones elementales de filas a su matriz ampliada.
Definición 1.6 a) En álgebra lineal, una matriz triangular es un tipo especial de matriz cuadrada cuyos elementos por encima o por debajo de su diagonal principal son cero.
b) Una matriz cuadrada de orden n se dice que es triangular superior si es de la forma:
11 12 13 1
22 23 2
33 3
0
0 0
0 0 0
n
n
n
nn
u u u u
u u u
u u
u
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋱ ⋮
⋯
U =
c) Análogamente, una matriz de la forma:
11
21 22
31 32 33
1 2 3
0 0 0
0 0
0
n n n nn
l
l l
l l l
l l l l
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋱ ⋮
⋯
L =
se dice que es una matriz triangular inferior.
Se suelen emplear las letras U y L, respectivamente, ya que U es la inicial de "upper triangular matrix" y L de "lower triangular matrix", los nombres que reciben estas matrices en inglés.
24
Ejemplo 1. 6
2 3 3 0 1 0 0 0
0 3 2 2 2 2 0 0,
0 0 1 1 3 0 2 0
0 0 0 2 5 2 1 1
− − = − −
U = L
Las matrices triangulares poseen las siguientes propiedades:
i. El producto de dos matrices triangulares superiores (inferiores) es un matriz triangular superior (inferior).
ii. La transpuesta de una matriz triangular superior es una matriz triangular inferior y viceversa.
iii. El determinante de una matriz triangular es el producto de los elementos de la diagonal.
iv. Una matriz triangular es invertible si y solo si todos los elementos de la diagonal son no nulos. En este caso, la inversa de una matriz triangular superior (inferior) es otra matriz superior (inferior).
Los dos sistemas de ecuaciones =Lx d y =Ux d , donde L y U son matrices triangulares inferior y superior respectivamente, son muy fáciles de resolver.
Ejemplo 1.7 Resolver el siguiente sistema triangular superior siguiente:
1 2 3 4
2 3 4
3 4
4
4 3 2 4
0.25 2.5 4.25 4
45 79 203
2.8 5.6
x x x x
x x x
x x
x
+ − + =− + + = −
+ = −= −
De la cuarta ecuación, se deduce que x4 = −5.6/2.8 = −2. A partir de la tercera ecuación
43 4 3
203 7945 = 203 79
45
xx x x
− −− − ⇒ =
sustituyendo 4x por su valor, se obtiene 3 1x = − .
A partir de la segunda ecuación
( ) ( )3 4
2 3 4 2
4 2.5 4.250.25 4 2.5 4.25
0.25
x xx x x x
− − +− = − − + ⇒ =
−
sustituyendo 3x y 4x por sus valores, se obtiene 2 28x = − .
25
Finalmente, utilizando la primera ecuación,
( ) ( )2 3 4
1 2 3 4 1
4 3 2 4 4 3 2
4
x x xx x x x x
− − += − − + ⇒ =
reemplazando 2x , 3x y 4x por sus valores, se obtiene 1 22x = .
Algoritmos de resolución de sistemas triangulares superiores.
Un sistema triangular superior =Ux d puede escribirse como
11 1 12 2 13 3 1 1
22 2 23 3 2 2
33 3 3 3
n n
n n
n n
nn n n
u x u x u x u x d
u x u x u x d
u x u x d
u x d
+ + + + =+ + + =
+ + =
=
⋯
⋯
⋯
⋱ ⋮ ⋮ ⋮ ⋮
En general, para resolver un sistema triangular superior, primero se calcula
nn
nn
dx
u= . Con este valor se puede calcular 1nx − , y así sucesivamente, es decir,
siguiendo el simple algoritmo recursivo siguiente
1 1,
1
1, 1
2 23
2
22
1 12
1
11
nn
nn
n n n n
n
n n
n
j jj
n
j jj
dx
u
d u xx
u
d u xx
u
d u xx
l
− −−
− −
=
=
=
−=
−=
−=
∑
∑
⋮ ⋮ ⋮
es decir,
11,..., ,
n
i ij jj i
i
ii
d u xi n x
u
= +−
∀ = =∑
Como se supone que U es regular (invertible o no singular), los elementos diagonales son no nulos y no se presentan problemas al efectuar la división.
26
El esquema del algoritmo para la SOLUCIÓN DE UN SISTEMA TRIANGULAR
SUPERIOR es el siguiente:
nn
nn
dx
u=
para i = n-1, ...,1
1
n
i ij jj i
i
ii
d u xx
u
= +−
=∑
fin-para que se puede escribir en términos de SCILAB en la forma
( )( ) ( ) \ ,x n d n U n n=
for 1: 1:1i n= − −
( ) ( )( ) ( )( ) ( ) , 1: * , 1: / ,x i d i U i i n x i i n U i i= − + +
end
Ejercicio 1.1 Resolver usando la función SCILAB soltrisup, (Anexo I), el siguiente sistema triangular superior:
1 2 3 4
2 3 4
3 4
4
4 3 2 4
0.25 2.5 4.25 4
45 79 203
2.8 5.6
x x x x
x x x
x x
x
+ − + =− + + = −
+ = −= −
Solución: Las sentencias SCILAB para resolver el problema se encuentran escritas en Ejercicio1_1.sce:
-->U=[4,3,-2,1;0,-0.25,2.5,4.25;0,0,45,79;0,0,0,2.8]
27
U = 4. 3. - 2. 1.
0. - 0.25 2.5 4.25
0. 0. 45. 79.
0. 0. 0. 2.8
-->d=[4;-4;-203;-5.6]
dT = (4., - 4., - 203., - 5.6)
-->eps=1.0e-13;
-->[x, res]=soltrisup(U, d, eps);
-->x1= x (1); x 2= x(2); x 3= x(3); x 4= x (4); x1, x2, x3, x4
x1 = 22., x2 = - 28., x3 = - 1., x4 = - 2.
Ejercicio 1.2 Resolver usando la función SCILAB soltrisup con tolerancia de aproximación a cero de los elementos de la diagonal igual a eps=1.0e-13, el sistema triangular superior =Ux b , de 20 ecuaciones con 20 incógnitas, donde U y b vienen dadas por:
1 3 1 3 1 2 4 2 7 7 1 1 2 1 3 1 4 1 5 2
0 3 4 6 3 5 5 4 3 6 1 3 1 5 3 1 6 0 6 2
0 0 2 4 5 9 5 6 2 4 3 5 3 4 5 3 4 2 6 3
0 0 0 5 9 1 7 5 4 2 4 3 1 4 2 3 3 1 6 7
0 0 0 0 8 1 1 7 1 3 4 2 1 3 2 4 3 1 7 8
0 0 0 0 0 3 1 1 1 7 5 8 4 7 1 7 2 3 3 9
0 0 0 0 0 0 4 3 2 8 5 7 6 5 3 8 6 3 4 5
0 0 0 0 0 0 0 1 6 1 6 6 5 2 5 5 7 2 2 5
0 0 0 0 0 0 0 0 6 1 3 7 3 3 4 6 5 7 4 6
0 0 0 0 0 0 0 0 0 9 1 3 4 4 3 9 4 6U =
3 2
0 0 0 0 0 0 0 0 0 0 8 2 2 6 2 0 5 8 9 1
0 0 0 0 0 0 0 0 0 0 0 8 7 2 4 1 4 5 8 5
0 0 0 0 0 0 0 0 0 0 0 0 3 2 1 2 6 3 9 3
0 0 0 0 0 0 0 0 0 0 0 0 0 6 1 2 1 4 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 5 2 4 1 9
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 2 2 2 8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 3 3 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
( )4 4 2 6 2 6 2 1 3 2 5 8 9 2 1 0 2 9 5 3Td =
28
Además, obtener e imprimir el tiempo de operación, es decir el tiempo que el
ordenador tarda en realizar los cálculos necesarios para obtener la solución.
Solución: Se escriben en Scinotes las siguientes instrucciones SCILAB:
//Ejercicio 1.2
//Resolver usando la función SCILAB soltrisup el sistema
//triangular superior Ux=d.
U1 =[1,3,1,3,1,2,4,2,7,7,1,1,2,1,3,1,4,1,5,2]
U 2 =[0,3,4,6,3,5,5,4,3,6,1,3,1,5,3,1,6,0,6,2]
U 3 =[0,0,2,4,5,9,5,6,2,4,3,5,3,4,5,3,4,2,6,3]
U 4 =[0,0,0,5,9,1,7,5,4,2,4,3,1,4,2,3,3,1,6,7]
U 5 =[0,0,0,0,8,1,1,7,1,3,4,2,1,3,2,4,3,1,7,8]
U 6 =[0,0,0,0,0,3,1,1,1,7,5,8,4,7,1,7,2,3,3,9]
U 7 =[0,0,0,0,0,0,4,3,2,8,5,7,6,5,3,8,6,3,4,5]
U 8 =[0,0,0,0,0,0,0,1,6,1,6,6,5,2,5,5,7,2,2,5]
U 9 =[0,0,0,0,0,0,0,0,6,1,3,7,3,3,4,6,5,7,4,6]
U 10=[0,0,0,0,0,0,0,0,0,9,1,3,4,4,3,9,4,6,3,2]
U 11=[0,0,0,0,0,0,0,0,0,0,8,2,2,6,2,0,5,8,9,1]
U 12=[0,0,0,0,0,0,0,0,0,0,0,8,7,2,4,1,4,5,8,5]
U 13=[0,0,0,0,0,0,0,0,0,0,0,0,3,2,1,2,6,3,9,3]
U 14=[0,0,0,0,0,0,0,0,0,0,0,0,0,6,1,2,1,4,0,0]
U 15=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,5,2,4,1,9]
U 16=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,2,2,2,8]
U 17=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,3,3,3]
U 18=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,1,5]
U 19=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3]
U 20=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2]
U=[ U1; U2; U3; U4; U5; U6; U7; U8; U9; U10; U11; U12; U13; U14; U15; U16; U 17; U 18; U 19;
U20]
d=[4;-4;-2;6;2;6;2;1;3;-2;-5;-8;-9;2;1;0;-2;9;5;-3]
eps=1.0e-13
tic()
[x, res]=soltrisup(U, d, eps)
t_sol_tri = toc()
x'
printf('t_sol_tri = %f \ n', t_sol_tri)
x’ = (- 121.18398 9.06334 - 184.30779 148.24011 - 89.47592 - 12.89048
- 69.9197 110.52194 - 1.79612 .98748 - 7.27117 11.17136 - 22.88577
-0.18218 1.00637 - 0.22449 - 4.46428 1.75000 9.50000 - 1.50000)
Tiempo de operación t_sol_tri = 0.002000 seg.
De forma análoga puede resolverse un sistema dado por una matriz triangular inferior.
29
Esquema de algoritmo para sistemas lineales triangulares inferiores.
Un sistema triangular inferior d=Lx puede escribirse como
11 1 1
21 1 22 2 2
31 1 32 2 33 3 3
1 1 2 3 3n nn n nn n n
l x d
l x l x d
l x l x l x d
l x l x l x l x d
=+ =+ + =
+ + + + =⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮
⋯
En general, para resolver un sistema triangular inferior, primero se calcula
1
11
1
dx
l= . Con este valor se puede calcular 2x , y así sucesivamente. Conocidos los
valores , , ,1 2 i-1x x ... x , la formulación de ix es
1
1
i
i ij jj
i
ii
d l xx
l
−
=−
=∑
El algoritmo recursivo es en este caso:
( )
11
11
2 21 12
22
3 31 1 32 2
3
33
1
1
n
n nj jj
n
nn
dx
l
d l xx
l
d l x l xx
l
d l xx
l
−
=
=
−=
− +=
−=
∑
⋮ ⋮ ⋮
es decir, 1
11,..., ,
i
i ij jj
i
ii
d l xi n x
l
−
=−
∀ = =∑
Al igual que para el sistema triangular superior, se supone que L es regular,
por lo que los elementos diagonales son también no nulos y tampoco se presentan
problemas al efectuar la división.
El esquema del algoritmo para la SOLUCIÓN DE UN SISTEMA
TRIANGULAR INFERIOR es el siguiente:
30
11
11
dx
u=
para i = 2, ...,n
1
1
i
i ij jj
i
ii
d u xx
u
−
=−
=∑
fin-para
que se puede escribir en términos de SCILAB en la forma:
para i = 1, ..., n
( ) ( )( ) ( )( ) ( ) ,1: 1 * ,1: 1 / ,x i d i L i i x i i L i i= − − −
fin-para
Los sistemas triangulares, sean superiores o inferiores son muy fáciles de
resolver y sin excesivas operaciones. Y la pregunta de oro es: Dado un sistema
=Ax b que pretendemos resolver, ¿es posible encontrar otro sistema triangular
con la misma solución?. De ser así encontrar la solución de sistemas de
ecuaciones lineales sería muy sencillo, tal como hemos visto en esta sección.
Veremos en la sección siguiente que sí es posible, si bien aún debemos de ir
retirando piedras del camino que conduce de forma eficiente y rentable (en el
sentido de economizar número de operaciones) a la solución.
2.2 Métodos de Gauss.
Dado un S.E.L. =Ax b con n nM ×∈A invertible, el principio que rige los
métodos de Gauss para la resolución del sistema se puede resumir en la determinación de un sistema triangular superior equivalente al primero, y, por tanto, con las mismas soluciones, proceso de eliminación, y a continuación resolver el sistema triangular equivalente mediante el método de sustitución
hacia atrás.
Gauss, teniendo en cuenta que los sistemas triangulares, sean superiores o
inferiores, son de muy fácil solución y sin excesivas operaciones, tal como hemos
visto , resolvió la cuestión: dado un sistema =Ax b , ¿es posible encontrar otro
sistema triangular con la misma solución?. De ser así encontrar la solución de
sistemas de ecuaciones lineales sería muy sencillo.
Veremos en este apartado que en general sí es posible encontrar un
sistema triangular equivalente a uno dado, y métodos eficientes para obtener el
31
sistema triangular, proceso de eliminación simple de Gauss y proceso de
eliminación de Gauss con pivote parcial y con pivote total.
El método de solución de sistemas de ecuaciones lineales de Gauss se realiza en dos fases:
1. Triangularización del sistema: Proceso de eliminación sucesiva de incógnitas, por medio de operaciones sencillas, que conduce a un sistema triangular superior equivalente al primero.
2. Resolución del sistema triangular superior obtenido en la fase anterior. Se despejan las incógnitas comenzando con la última
ecuación y hacia arriba.
Por esta razón, muchas veces se dice que el método de eliminación
de Gauss consiste en la eliminación hacia adelante y sustitución hacia atrás.
Se pueden distinguir básicamente tres versiones del método de de Gauss, en función del método utilizado para obtener la matriz triangular superior ampliada del sistema:
Método de eliminación simple de Gauss.
Método de Gauss con pivote parcial
Método de Gauss con pivote total
Nota: Hemos destacado el segundo método por cuanto en general resulta ser el más adecuado.
2.2.1 Método de eliminación simple de Gauss, (o método de Gauss).
Para resolver sistemas de ecuaciones de cualquier tipo, una de las estrategias más utilizadas consiste en ir simplificando el sistema, para que sea cada vez más fácil de resolver, pero que siga teniendo las mismas soluciones que el sistema original. Por tanto, debemos usar el concepto de sistemas equivalentes.
Así, aplicar las operaciones arriba indicadas a un sistema, equivale a aplicar las correspondientes transformaciones elementales de filas a su matriz
ampliada, este proceso se conoce como proceso de eliminación simple de Gauss, generalización del método de reducción, que consiste en obtener una matriz triangular equivalente a la matriz aumentada del sistema mediante transformaciones elementales del tipo anterior.
En definitiva, el método de eliminación simple de Gauss consiste en la aplicación sucesiva del método de reducción, utilizando los criterios de equivalencia de sistemas para transformar la matriz ampliada en una matriz triangular, por ejemplo, superior, de modo que cada fila (ecuación) tenga una incógnita menos que la inmediatamente anterior. Se obtiene así un sistema triangular superior, tal que la última ecuación tiene una única incógnita, la
32
penúltima dos incógnitas, la antepenúltima tres incógnitas, etc.., y la primera todas las incógnitas. Formalmente, el proceso de eliminación simple de Gauss consiste en reducir un sistema de ecuaciones lineales =Ax b a otro sistema triangular equivalente =Ux d , que como decíamos es un procedimiento similar al método de reducción, pero ejecutado de manera reiterada y siguiendo un cierto orden algorítmico.
En la práctica, el proceso de eliminación simple de Gauss, para obtener un sistema de ecuaciones lineales triangular superior equivalente al sistema original, consiste en aplicar al sistema original tres operaciones básicas de la siguiente forma:
Paso 1: Si es necesario, intercambiar la primera ecuación con otra, para que
1x aparezca en la primera ecuación.
Paso 2: Eliminar 1x de cada ecuación (salvo la primera), sumándole un
múltiplo adecuado de la primera ecuación.
Paso 3: Ignorando temporalmente la primera ecuación, repetir todo el proceso con las restantes ecuaciones.
Recalcamos que al terminar de aplicar el proceso de eliminación simple de Gauss, habremos transformado el sistema en otro equivalente, muy fácil de resolver puesto que su matriz ampliada es triangular.
Ejercicio 1.3 Obtener por el algoritmo de eliminación simple de Gauss un sistema triangular superior equivalente al sistema siguiente:
1 2 32 3 9x x x+ + = ……………. R1
1 2 34 5 6 24x x x+ + = ……………. R2
1 2 33 2 4x x x+ − = ……………. R3
Solución:
1º Paso: Sumar (-4) veces la primera ecuación, R1, a la segunda, R2:
(1)
2 1 24R R R= − + :
1 2 34 8 12 36x x x− − − = − ……………. -4R1
1 2 34 5 6 24x x x+ + = ……………. R2
2 33 6 12x x− − = − ……………. R2(1)
1 2 3 1 2 3
1 2 3 2 3
1 2 3 1 2 3
2 3 9 2 3 9
4 5 6 24 3 6 12
3 2 4 3 2 4
x x x x x x
x x x x x
x x x x x x
+ + = + + =
+ + = − − = − + − = + − =
≡
33
2º Paso: Multiplicar por (-1/3) la ecuación R’2:
1
3
(2) (1)
2 2R R= − : ( )(2)
2 2 3 2 3
13 6 12 2 4
3R x x x x= − − − = − ≡ + =
1 2 3 1 2 3
1 2 3 2 3
1 2 3 1 2 3
2 3 9 2 3 9
4 5 6 24 2 4
3 2 4 3 2 4
x x x x x x
x x x x x
x x x x x x
+ + = + + =
+ + = + = + − = + − =
≡
3º Paso: Sumar (-3) veces la primera ecuación, R1, a la tercera, R3:
(1)
3 1 33R R R= − + :
1 2 33 6 9 27x x x− − − = − ……………. -4R1
1 2 33 2 4x x x+ − = ……………. R2
2 35 11 23x x− − = − ……………. R2(2)
1 2 3 1 2 3
1 2 3 2 3
1 2 3 2 3
2 3 9 2 3 9
4 5 6 24 2 4
3 2 4 5 11 23
x x x x x x
x x x x x
x x x x x
+ + = + + =
+ + = + = + − = − − = −
≡
4º Paso: Sumar 5 veces la segunda, (2)
2R , a la tercera, (1)
3R :
(2) (2) (1)
3 2 35R R R= + :
2 35 10 20x x+ = ……………. 5 (2)
2R
2 35 11 23x x− − = − ……………. (1)
3R
3 3x− = − ……………. (2)
3R
1 2 3 1 2 3
1 2 3 2 3
1 2 3 3
2 3 9 2 3 9
4 5 6 24 2 4
3 2 4 3
x x x x x x
x x x x x
x x x x
+ + = + + =
+ + = + = + − = − = −
≡
5º Paso: Multiplicar por (-1) la ecuación (2)
3R :
(3) (2)
3 3R R= − : ( )3 3
(2)
2 1 1R x x= − − = − ≡ =
1 2 3 1 2 3
1 2 3 2 3
1 2 3 3
2 3 9 2 3 9
4 5 6 24 2 4
3 2 4 3
x x x x x x
x x x x x
x x x x
+ + = + + =
+ + = + = + − = =
≡
Hemos obtenido de este modo un sistema equivalente al que tratamos de resolver con la matriz de los coeficientes triangular superior:
1 2 3 9 1 2 3 9
4 5 6 24 1 2 4
3 1 2 4 1 1
−
≡
34
Analizando el método utilizado en el ejemplo anterior para dar solución a un sistema de ecuaciones de tres incógnitas, podemos percatarnos que los símbolos usados para las variables carecen de importancia, y solo se tienen en cuenta los coeficientes de las mismas, por lo que podemos simplificar el proceso si se introduce un esquema con los coeficientes, de forma tal, que no haya necesidad de escribir las variables.
Matriz ampliada del sistema
1 2 3 9
4 5 6 24
3 1 2 4
−
Las transformaciones elementales de fila para obtener la matriz triangular superior equivalente pueden representarse en la forma siguiente:
1 2 3 9
4 5 6 24
3 1 2 4
→ −
(1)
2 1 24R R R= − + →
1 2 3 9
0 3 6 12
3 1 2 4
− − − −
( 2) (1)
2 2
1
3R R= − →
1 2 3 9
0 1 2 4
3 1 2 4
−
(1)
3 1 33R R R= − + →
1 2 3 9
0 1 2 4
0 5 11 23
− − −
(2) ( 2) (1)
3 2 35R R R= + →
1 2 3 9
0 1 2 4
0 0 1 3
− −
(3) ( 2)
3 3R R= − →
1 2 3 9
0 1 2 4
0 0 1 3
Se tiene así un sistema de ecuaciones lineales equivalente al original:
1 2 3
2 3
3
2 3 91 2 3 9 1 2 3 9
4 5 6 24 0 1 2 4 2 4
3 1 2 4 0 0 1 3 3
x x x
x x
x
+ + =
→ + = − =
⇔
35
Ejercicio 1.4 Obtener por el algoritmo de eliminación simple de Gauss un sistema triangular superior equivalente al sistema siguiente:
1 2 3 1x x x+ − = ……………. R1
1 2 32 3 2x x x+ + = ……………. R2
1 2 33 2 2 1x x x+ + = − ……………. R3
Solución: Matriz ampliada del sistema
1 1 1 1
2 1 3 2
3 2 2 1
− + −
Las transformaciones elementales de fila para obtener la matriz triangular equivalente pueden representarse en la forma siguiente:
1 1 1 1
2 1 3 2
3 2 2 1
−
→ + −
(1)
2 1 2R R R= + →
1 1 1 1
3 2 2 3
3 2 2 1
− + −
(1) (1)
3 2 3R R R= − →
1 1 1 1
3 2 2 3
0 0 0 4
− −
Con la matriz triangular superior final pasamos a un sistema de ecuaciones lineales equivalente al original:
1 2 3
1 2 3
11 1 1 1
3 2 2 3 3 2 2 3
0 0 0 4 0 4
x x x
x x x
+ − = −
+ + = − = −
⇔
La 3ª ecuación indica que el sistema es incompatible.
Ejercicio 1.5 Resolver por eliminación simple de Gauss el sistema:
1 2 3 1x x x+ − = ……………. R1
1 2 32 3 2x x x+ + = ……………. R2
1 2 33 2 2 3x x x+ + = ……………. R3
Solución: Matriz ampliada del sistema
1 1 1 1
2 1 3 2
3 2 2 3
−
36
Las transformaciones elementales de fila para obtener la matriz triangular equivalente pueden representarse en la forma siguiente:
1 1 1 1
2 1 3 2
3 2 2 3
−
→
(1)
2 1 2R R R= + →
1 1 1 1
3 2 2 3
3 2 2 3
−
(1) (1)
3 2 3R R R= − →
1 1 1 1
3 2 2 3
0 0 0 0
−
Con la matriz triangular final pasamos a un sistema de ecuaciones lineales equivalente al original:
1 2 3
1 2 3
3
11 1 1 1
3 2 2 3 3 2 2 3
0 0 0 0 0 0
x x x
x x x
x
+ − = −
+ + = =
⇔
La 3ª ecuación se verifica siempre, sea cual sea el valor de 3x . Por otro lado,
para cada valor de 3x se obtendrá un valor concreto para 1x y 2x , es decir el
sistema tiene infinitas soluciones, por tanto, es compatible indeterminado.
Como podemos ver después de realizar las transformaciones consideradas pertinentes en los tres ejercicios anteriores, se obtiene un sistema triangular superior.
Suponiendo que hubiésemos eliminado, de haberlas, las filas nulas ( )0,..., 0 ,
que corresponden a ecuaciones del tipo 0 0= , el sistema equivalente tendría ahora k ecuaciones lineales con n incógnitas.
Analizando el sistema resultante, por el teorema de Rouché-Frobenius, podemos efectuar su discusión del siguiente modo:
1.- Si alguna de las ecuaciones es del tipo 0 kb= (siendo 0kb ≠ ), el sistema es
incompatible y no tiene solución.
2.- Si no hay ecuaciones del tipo 0 kb= , y además k = n, es decir, el número
de ecuaciones del sistema equivalente es igual al número de incógnitas, el sistema es compatible determinado, (tiene una única solución).
3.- Si no hay ecuaciones del tipo 0 kb= y k < n, es decir, el número de
ecuaciones es menor que el número de incógnitas, el sistema es compatible indeterminado y, en consecuencia, tiene infinitas soluciones.
En este caso, tenemos que separar las incógnitas principales de las no principales.
37
Pero, ¿cuáles son las incógnitas principales?
Se puede dar el siguiente criterio:
Si el sistema es triangular y tiene k ecuaciones, las k primeras incógnitas serán las principales y las n-k restantes serán las no principales que pasaremos al segundo miembro como parámetros.
Algoritmo de eliminación simple de Gauss.
Es natural que nos preguntemos como se estructura un algoritmo para realizar el método de eliminación simple de Gauss automáticamente. Podemos aproximarnos a esta estructura a través del siguiente sistema de 3 ecuaciones y 3 incógnitas
11 12 13 1 1
21 22 23 2 2
31 32 33 3 3
a a a x b
a a a x b
a a a x b
=
matriz ampliada: 1 11 12 13 1
2 21 22 23 2
3 31 32 33 3
R a a a b
R a a a b
R a a a b
=
Se trata de conseguir ceros en la matriz triangular inferior.
Para conseguir 21 0a = , podríamos transformar R1 de tal modo que en esta
transformación se reemplace 11a por 21a− de forma que al sumar la primera fila
transformada a la segunda fila el elemento 21a se reemplace por 0.
Necesariamente tal transformación de R1 consiste en multiplicar cada uno de sus
elementos por 21
11
a
a
−. A continuación se suma la transformación de R1 a R2.
(1)
1 1 11 12 13 1
(1) 21 21 21 212 2 1 22 12 23 13 2 1
11 11 11 11
(1)
3 3 31 32 33 3
0
R R a a a b
a a a aR R R a a a a b b
a a a a
R R a a a b
=
− − − − = + = + + + =
Se repite el mismo proceso para R3. Para conseguir 31 0a = , se transforma R1
de tal modo que se reemplace 11a por 31a− de forma que al sumar la primera fila
transformada a la segunda fila el elemento 31a se reemplace por 0. Necesariamente tal transformación de R1 consiste en multiplicar cada uno de sus
elementos por 31
11
a
a
−. A continuación se suma la transformación de R1 a R3.
38
(2) (1) 11 12 13 11 1
(2) (1) 21 21 212 2 22 12 23 13 2 1
11 11 11(2) (1) (2)313 3 1 31 31 31
11 32 12 33 13 3 1
11 11 11
0
0
a a a bR R
a a aR R a a a a b b
a a aa
R R R a a aa a a a a b b
a a a
= − − − = = + + + − = + − − − + + +
Tras los dos pasos anteriores nuestra matriz resultante es:
(2) (2) (2) (2) (2)
1 11 12 13 1
(2) (2) (2) (2)
2 22 23 2
(2) (2) (2) (2)
3 32 33 3
0
0
R a a a b
R a a b
R a a b
=
Para conseguir (2)
32 0a = , se transforma (2)
2R de tal modo que se reemplace (2)
22a
por (2)
32a− de forma que al sumar la segunda fila transformada, (2)
2R , a la tercera
fila el elemento (2)
32a se reemplace por 0 . Necesariamente tal transformación de
(2)
2R consiste en multiplicar cada uno de sus elementos por (2)
32
(2)
22
a
a
−. A
continuación se suma la transformación de (2)
2R a (2)
3R .
(3) (2) (2) (2) (2) (2)
1 1 11 12 13 1
(3) (2) (2) (2) (2)
2 2 22 23 2
(2) (1) (1)(3) (2) (2) (2) (2) (2) (2)32 32 323 3 2 33 23 3 2(2) (1) (1)
22 22 22
0
0 0
R R a a a b
R R a a b
a a aR R R a a b b
a a a
= = =
− − − = + + +
siendo (2) 2122 22 12
11
aa a a
a
−= + y (2) 3132 32 12
11
aa a a
a
−= + .
Como se ha podido observar en el ejemplo anterior el proceso de
eliminación se realiza en (n-1) etapas: en cada etapa k-ésima se obtienen ceros
en la columna k por debajo de la diagonal principal. Así partiendo de ( ) =1A A ;
en la etapa k-ésima se construye (k+ )1A a partir de ( )( ) ( )k kija=A .
Para poder realizar cada etapa k-ésima se exigirá (y esta es la
característica esencial de Gauss normal) que:
( ) 0, 1, , kkk
a k n≠ = … .
Etapa k-ésima:
Se hacen ceros en la columna k por debajo de la diagonal principal sumando
a las filas i = k+1,…, n, la fila k multiplicada por ( )
( )
kikk
kk
a
a
−.
39
En resumen, el esquema de la triangularización o eliminación simple de
Gauss de un sistema de ecuaciones lineales es:
para k = 1, ..., n − 1
para i = k + 1, ..., n
lik = aik/akk, aik = 0
para j = k + 1, ..., n
aij = aij − lik akj
fin-para j
bi = bi−lik bk
fin-para i
fin-para k
que se puede escribir en términos de SCILAB en la forma:
for k=1:n−1
for i = k + 1: n
( ) ( ) ( ), , / , L i k A i k A k k=
( ), 0A i k =
A(i, k + 1 : n) = A(i, k + 1 : n)−L(i:k)∗A(k, k + 1 : n)
b(i) =b(i)−L(i,k)∗b(k)
end
end
Formalmente, el proceso de eliminación simple de Gauss consiste en reducir un sistema de ecuaciones lineales =Ax b a otro sistema triangular equivalente
=Ux d , que como decíamos es un procedimiento similar al método de reducción, pero ejecutado de manera reiterada y siguiendo un cierto orden algorítmico.
El esquema de eliminación simple de Gauss funciona siempre y cuando no
aparezca un pivote, kk
a , nulo o casi nulo. Cuando aparezca es necesario buscar
un elemento no nulo en el resto de la columna, en este caso diremos al proceso lo
denominaremos triangularización con control de pivote. Si, en el proceso de
triangularización, toda la columna ( ): ,A k n k es nula o casi nula, entonces A es
singular.
Ejemplo 1.8 Para resolver por eliminación simple de Gauss el sistema:
1 2 3 1x x x+ − = ……………. R1
1 2 32 2 3 2x x x+ + = ……………. R2
1 2 33 2 2 3x x x+ + = ……………. R3
40
Matriz ampliada del sistema:
1 1 1 1
2 2 3 2
3 2 2 3
−
Las transformaciones elementales de fila para obtener la matriz triangular equivalente son:
1 1 1 1
2 2 3 2
3 2 2 3
−
→
(1)
2 1 22R R R= − + →
1 1 1 1
0 0 5 1
3 2 2 3
−
En la fila 2 resultante el elemento se anula 22 (2, 2)a A= , lo que implica que no
existe ( ) ( ) ( )2,3 2,3 / 2, 2 L A A= por lo que el algoritmo de eliminación simple de
Gauss no podría resolver la situación. Este problema se soluciona intercambiando la fila 2 por la 3 (al intercambio de una fila por otra para controlar el efecto cero o “casi cero” del pivote se llama control de pivote):
1 1 1 1
0 5 1
3 2 2 3
0
−
(1) (1)
2 3R R↔ →
1 1 1 1
3 2 2 3
0 0 5 1
−
(1) (1)
2 3: 2 3.R R Intercambio de la fila por la fila↔
Una vez controlado el pivote, en cuantas filas sea necesario se continua el proceso de eliminación habitual.
1 1 1 1
3 2 2 3
0 0 5 1
−
→
( 2) (1) (1)
2 1 23R R R= − + →
1 1 1 1
0 1 5 0
0 0 5 1
−
− →
Con la matriz triangular final pasamos a un sistema de ecuaciones lineales equivalente al original:
1 2 3 1
2 3 2
33
11 1 1 1 0.20
0 1 5 0 5 0 1.
0 0 5 1 0.205 1
x x x x
x x x
xx
+ − =− = − − + = ⇒ = ==
⇔
Algoritmo de eliminación de Gauss con control de pivote.
Siendo ε la tolerancia respecto a la proximidad del valor absoluto del pivote a
cero, el esquema de la intercambio de filas, ( mkR R↔ , intercambio de la fila k por
la fila m), puede esquematizarse en la forma siguiente:
41
si |akk| ≤ ε entrar buscar m, k + 1 ≤ m ≤ n, tal que |amk| > ε si no fue posible salir
intercambiar ak,k:n con am,k:n
intercambiar(bk, bm)
fin-si
El algoritmo de eliminación simple de Gauss de un sistema de ecuaciones lineales con control de pivote podría adoptar la forma siguiente:
para k = 1, ..., n
si |akk| ≤ ε entrar buscar m, k + 1 ≤ m ≤ n, tal que |amk| > ε si no fue posible entonces salir
intercambiar ak,k:n con am,k:n
intercambiar(bk, bm)
fin-si
para i = k + 1, ..., n
lik = aik/akk, aik = 0
para j = k + 1, ..., n
aij = aij − lik akj
fin-para j
bi = bi−lik bk
fin-para i
fin-para k
que se puede escribir en términos de SCILAB en la forma:
for k=1:n
if abs(A(k,k)) ≤ ε for i = k+1:n
if abs(A(i,k)) > ε m = i
end
t = A(k,k:n)
A(k,k:n) = A(m,k:n)
A(m,k:n) = t
t = b(k)
b(k) = b(m)
b(m) = t
end
end
for i=k+1:n
lik = A(i,k)/A(k,k)
A(i,k) = 0
A(i,k+1:n) = A(i,k+1:n) - lik*A(k,k+1:n)
b(i) = b(i) - lik*b(k)
end
end
42
Ejercicio 1.6 Obtener por el algoritmo de eliminación simple un sistema triangular superior equivalente al sistema con matriz ampliada:
(Ab) = 1 3 1 3 1 2 4 2 7 7 4
0 3 4 6 3 5 5 4 3 6 -4
2 3 2 4 5 9 5 6 2 4 -2
6 7 9 5 9 1 7 5 4 2 6
1 2 3 4 8 1 1 7 1 3 2
3 5 7 1 1 3 1 1 1 7 6
6 5 1 3 5 3 4 3 2 8 2
2 3 6 8 1 1 8 1 6 1 1
5 2 3 7 8 3 6 1 6 1 3
1 1 4 3 2 2 1 2 1 9 - 2
Número de ecuaciones: m=10; Número de incógnitas: n=10
eps=1.0e-13
tic()
[U, d, res] = trisup(A, b, eps)
U
t_triang = toc()
printf('t_triang = %f \', t_triang)
Salida:
U= 1. 3. 1. 3. 1. 2. 4. 2. 7. 7.
0. 3. 4. 6. 3. 5. 5. 4. 3. 6.
0. 0. 4. 4. 6. 10. 2. 6. - 9. - 4.
0. 0. 0. - 8.66 - 12.5 - 36.83 - 7.5 - 18.83 12.75 23.66
0. 0. 0. 0. 3.48 - 6.25 - 2.71 2.05 2.01 0.42
0. 0. 0. 0. 0. 22.62 0.21 5.75 - 9.57 - 22.33
0. 0. 0. 0. 0. 0. - 6.71 0.70 - 7.3 - 19.20
0. 0. 0. 0. 0. 0. 0. 3.37 10.60 - 14.83
0. 0. 0. 0. 0. 0. 0. 0. 20.82 - 14.15
0. 0. 0. 0. 0. 0. 0. 0. 0. 16.98
d = 4.
- 4.
- 14.
29.16
7.21
- 13.10
- 3.17
19.93
31.58
- 5.57
t_triang = 0.01600
tic()
[x, res]=soltrisup(U, d, eps)
t_sol_tri = toc()
x
43
printf('t_sol_tri = %f \', t_sol_tri)
Salida:
x =[1.5812714; 0.6992383; 0.3625883; 0.1865239; - 0.7504622; 0.0475679; - 2.1939064;
0.8054871; 1.6978836; - 0.6666219]
t_sol_tri = 0.01600
2.2.2 Método de Gauss con Pivote Parcial.
No es difícil encontrar ejemplos de sistemas donde el método de eliminación simple de Gauss, (o método de Gauss), no puede llevarse a la práctica, puesto que
algún elemento k
kka resulta nulo. En este caso como hemos visto, es necesario,
antes del proceso de eliminación, un cambio de orden en las ecuaciones del
sistema a fin de obtener un elemento diagonal no nulo. En esto consiste en método de eliminación simple de Gauss con control de pivote.
En el método de eliminación simple de Gauss con control de pivote, únicamente se intercambian filas cuando el pivote, akk, es nulo o casi nulo. Como el pivote (el elemento akk en la iteración k) va a ser divisor para el cálculo de lik, y como el error de redondeo o de truncamiento se hace mayor cuando el divisor es cercano a cero, entonces es muy conveniente buscar que el pivote sea grande en valor absoluto. Es decir, hay que evitar los pivotes que sin ser nulos son cercanos a cero.
En el método de Gauss con pivote parcial se busca el elemento dominante, o sea, el de mayor valor absoluto en la columna k de la diagonal hacia abajo, es decir, entre los valores |akk|, |ak+1,k|, |ak+2,k|, ..., |akn|, y se intercambian la fila k,
(Rk), y la fila del valor dominante, (Rp). Esto mejora notablemente, en muchos casos, la precisión de la solución final obtenida, si bien añade al método simple de Gauss 3/2n(n-1) comparaciones y n(n+1)/2 - 1 divisiones.
Algoritmo del método de eliminación de Gauss con pivote parcial. para k = 1,...,n
buscar m, tal que |amk| = max{|akk|,|ak+1,k|,..., |ank|}
si |amk| ≤ ε entrar si no salir
si m > k entrar
intercambiar ak,k:n con am,k:n
intercambiar(bk, bm)
fin-si
para i = k+ 1,...,n
lik = aik/akk, aik = 0
ai,k+1:n= ai,k+1:n −lik ak,k+1:n
bi = bi−likbk
fin-para i
44
fin-para k
En Scilab la búsqueda del valor dominante y su fila se puede hacer mediante:
[vmax, posMax] = max(abs(A(k:n,k)))
m = k - 1 + posMax
if vmax <= eps, res = 0, return, end
El resto del algoritmo es igual que en el método de eliminación simple.
Ejercicio 1.7 Resolver por el método de Gauss con pivote parcial el siguiente sistema de 4 ecuaciones con 4 incógnitas:
4x1 + 3x2 − 2x3 + x4 = 4 3x1 + 2x2 + x3 + 5x4 = −8 −2x1 + 3x2 + x3 + 2x4 = −7 −5x1 + x3 + x4 = −8
La matriz ampliada es:
( )
4 3 2 1 4
3 2 1 5 8|
2 3 1 2 7
5 0 1 1 8
− − = − − − −
A b
El valor dominante de A(1:4, 1) es −5 y está en la fila 4. Entonces se intercambian las filas 1 y 4.
5 0 1 1 8
3 2 1 5 8
2 3 1 2 7
4 3 2 1 4
− − − − − −
Buscar ceros en las posiciones de a21, a31, a41 se hace de la manera habitual usando los valores de lik= 3/(−5) = −0.6, 0.4 y −0.8. Se obtiene
5 0 1 1 8
0 2 1.6 5.6 12.8
0 3 0.6 1.6 3.8
0 3 1.2 1.8 2.4
− − − − − −
El valor dominante de A(2 : 4, 2) es 3 y está en la fila 3 (o en la fila 4). Entonces se intercambian las filas 2 y 3.
5 0 1 1 8
0 3 0.6 1.6 3.8
0 2 1.6 5.6 12.8
0 3 1.2 1.8 2.4
− − − − − −
45
Buscar ceros en las posiciones de a32, a42 se hace usando los valores de lik= 2/3 = 0.6666 y 1. Se obtiene
5 0 1 1 8
0 3 0.6 1.6 3.8
0 0 1.2 4.533 10.267
0 0 1.8 1.2 1.4
− − − − −
Hay que intercambiar las filas 3 y 4.
5 0 1 1 8
0 3 0.6 1.6 3.8
0 0 1.8 0.2 1.4
0 0 1.2 4.533 10.267
− − − − −
El valor de lik es 1.2/(−1.8) = −0.6667. Se obtiene
5 0 1 1 8
0 3 0.6 1.6 3.8
0 0 1.8 0.2 1.4
0 0 0 4.667 9.333
− − − − −
Al resolver el sistema triangular superior, se encuentra la solución:
x = (1, 0, −1, −2).
El ejemplo del ejercicio anterior sirve simplemente para mostrar el desarrollo del método de Gauss con pivote parcial, pero no muestra sus ventajas. Para ver sus ventajas veremos el ejercicio 1.8, en el que resolveremos inicialmente el sistema por el método de Gauss sin pivote y después con pivote parcial.
Antes de ver el ejercicio 1.8 veremos algunos conceptos relativos a la “norma” de la diferencia entre las soluciones de un sistema y al vector residuo del sistema.
Definición. 1.7 a) Se llama norma vectorial en nℝ a toda aplicación
( )1: ,..., n
nx x• ∈ → ∈ℝ ℝx = x
que verifica
1. 0 npara todo≥ ∈ℝxx
2. 0= ⇔ = 0xx
3. npara todo yα αα = ∈ ∈ℝ ℝxx x
4. .npara todo ,≤ + ∈ℝx yx + y x y
46
b) A partir de la norma de un vector se define la distancia entre dos vectores: si 1 2, n∈ℝx x , se llama distancia vectorial entre 1
x , 2x , a la norma del vector
1 2 n∈ℝx - x , es decir al valor 1 2−x x .
Las normas 1ℓℓℓℓ , 2ℓℓℓℓ y ∞ℓℓℓℓ del vector ( )1,...,n
nx x ∈ℝx = están definidas por
1 21... nx x x= + + +x
2
2 1
n
iix
== ∑x
{ }1
ii n
máx x∞ ≤ ≤
=x
A la norma 2ℓℓℓℓ se le llama norma euclidea. La distancia euclidea entre 1
x , 2x , es
( )21 2 1 2
1
n
j jjx x
=− = −∑x x .
Si x es un vector fila o columna, entonces en SCILAB se tiene:
norm(x) calcula ||x||2 ,
norm(x, 2) calcula ||x||2 ,
norm(x, 1) calcula ||x||1 ,
norm(x, ’inf’) calcula ||x||∞ .
Sea x = ( 0.2267, 0.2770, 0.3300 )T, entonces
-->x = [0.2267; 0.2770; 0.3300]
0.2267
0.277
0.33
-->norm(x), norm(x,2), norm(x,1), norm(x,'inf') 0.4868489, 0.4868489, 0.8337, 0.33 Sea *
x la solución exacta del sistema =Ax b . Para comparar 1x y 2
x , dos
aproximaciones de la solución, se miran sus distancias a *x :
1 *−x x , −2 *x x
Si 1 * 2 *− < −x x x x , entonces 1x se aproxima mejor a *x que 2x .
Cuando no se conoce *x , entonces se utiliza la norma del vector residuo o
resto, r = Ax - b
47
Dado que la norma del resto de la solución exacta vale cero, para comparar
dos aproximaciones de la solución exacta, 1x y 2
x , hay que comparar 1Ax - b y
2Ax - b .
Ejercicio. 1.8 Resolver por los métodos de Gauss a) simple y b) con pivote parcial, el siguiente sistema de 4 ecuaciones con 4 incógnitas, indicando razonadamente cual de los dos métodos es “mejor” para nuestro objetivo, sabiendo que la solución exacta, tomada con cuatro cifras decimales, es x=(0.2245, 0.2814, 0.3279):
0.729 x1 + 0.8 1x2 + 0.9 x3 = 0.6867 x1 + x2 + x3 = 0.8338 1.331 x1 + 1.21 x2 + 1.1 x3 = 1
a) Al resolver el sistema por el método de Gauss, con cuatro cifras decimales y sin pivote, resultan los siguientes pasos:
0.7290 0.8100 0.9000 0.6867
1.0000 1.0000 1.0000 0.8338
1.3310 1.2100 1.1000 1.0000
Con lik = 1.3717 y con lik = 1.8258 se obtiene
0.7290 0.8100 0.9000 0.6867
0.0000 0.1111 0.2345 0.1081
0.0000 0.2689 0.5432 0.2538
− − − − − −
Con lik = 2.4203 se obtiene
0.7290 0.8100 0.9000 0.6867
0.0000 0.1111 0.2345 0.1081
0.0000 0.0000 0.0244 0.0078
− − −
La solución del sistema triangular es:
x = ( 0.2163, 0.2979, 0.3197 )T.
Para la solución obtenida por el método de Gauss sin pivote, el cálculo del residuo y la comparación con la solución exacta da:
Ax - b = 1.0357e-4 , *−x x = 0.0202 .
Por otra parte, si utilizamos el método de Gauss con pivote parcial, haciendo cálculos con 4 cifras decimales, se tiene,
48
0.7290 0.8100 0.9000 0.6867
1.0000 1.0000 1.0000 0.8338
1.3310 1.2100 1.1000 1.0000
Intercambio de las filas 1 y 3.
1.3310 1.2100 1.1000 1.0000
1.0000 1.0000 1.0000 0.8338
0.7290 0.8100 0.9000 0.6867
Con lik = 0.7513 y con lik = 0.5477
1.3310 1.2100 1.1000 1.0000
0.0000 0.0909 0.1736 0.0825
0.0000 0.1473 0.2985 0.1390
Intercambio de las filas 2 y 3.
1.3310 1.2100 1.1000 1.0000
0.0000 0.1473 0.2975 0.1390
0.0000 0.0909 0.1736 0.0825
Con lik = 0.6171 se obtiene
1.3310 1.2100 1.1000 1.0000
0.0000 0.1473 0.2975 0.1390
0.0000 0.0000 0.0100 0.0033
−
La solución del sistema triangular da:
x = ( 0.2267, 0.2770, 0.3300 )T.
El cálculo del residuo y la comparación con la solución exacta da:
Ax - b = 1.5112e-4 , *−x x = 0.0053 .
Se observa que para este ejemplo la norma del residuo es del mismo orden de magnitud que la norma del residuo correspondiente a la solución obtenida sin pivote, aunque algo mayor.
La comparación directa con la solución exacta favorece notablemente al
método de pivote parcial: 0.0053 y 0.0202, relación de 1 a 4 aproximadamente:
Método de Gauss sin pivote: 1Ax - b
= 1.0357e-4 , 1 *−x x
= 0.0202
Método de Gauss con pivote: 2Ax - b
= 1.5112e-4 , 2 *−x x
= 0.0053
49
2.2.3 Método de Gauss con Pivote Total.
En el método de eliminación de Gauss se dice que el pivote es total si en la iteración k se busca el mayor valor de {|aij| : k≤ i, j≤ n}.
Pivote total: Se toma (i, j) tal que
(9) ( ) ( )k k
ij rsk r nk s n
a máx a≤ ≤≤ ≤
=
y se permutan las ecuaciones i y k y las incógnitas j y k. La técnica de pivote total refina aún más la elección, tomando en cada paso i-
ésimo el mayor pivote posible en valor absoluto (apq ), en todas las columnas q a partir de la diagonal (q _ i) y por debajo de la diagonal (p _ i ). Esto implica intercambio de las filas i por la p: (Ri ) ↔ (Rp ), y de las columnas i por la q: (Ci ) ↔ (Cq).
En este caso se intercambian dos filas y dos columna. El cambio de filas afecta al vector b y el de columnas al vector x.
Dado que en el método de pivote parcial hay aproximadamente n(n+1)/2- 1 comparaciones y en el pivote total n(n-1)(2n+5)/6, a pesar de que con el pivote total se gana un poco de precisión, es evidente que se gasta bastante más tiempo. Así se consigue mejorar un poco la precisión con respecto al método de pivote parcial, pero a un costo nada despreciable. Por tanto, el balance aconseja preferir el pivote parcial.
50
2.2.4 Método de Gauss - Jordan.
El método de Gauss-Jordan es una variante del método de Gauss que se basa en transformar el sistema de ecuaciones lineales Ax = b en un sistema equivalente Dx = c , con D una matriz diagonal. Este método es más simple en la 2ª fase, ya que no es necesario despejar las incógnitas puesto que se obtienen directamente.
En cada etapa k se deben hacer cero las posiciones ( ) ( ) ( ) ( ), ,..,k k k k
1k k -1,k k+1,k n,ka ,..., a a a
donde ( etapas)k = 1,...,n, n .
Las características que distinguen el método de Gauss-Jordan de los métodos de eliminación de Gauss son:
- En cada paso, el elemento pivote tiene que ser 1.
- En cada paso, todos los términos por encima del pivote así como todos los que están por debajo deben ser anulados.
En otras palabras, si
( )11 12 1 1
21 22 2 2
1 2
n
n
n n nn n
a a a b
a a a b
a a a b
=
⋯
⋯
⋮ ⋮ ⋱ ⋮ ⋮
⋯
Ab
es la matriz ampliada del sistema, entonces mediante operaciones elementales se reduce a
1
2
1 0 0
0 1 0
0 0 1 n
s
s
s
⋯
⋯
⋮⋮ ⋮ ⋱ ⋮
⋯
La solución aparece en la última columna ( )i ix = s , por lo que no es necesaria
la sustitución hacia atrás.
El coste del método de Gauss-Jordan es n3+n2-2n, a falta de añadir n divisiones para calcular las incógnitas.
Ejercicio. 1.9 Resolver por el método de Gauss-Jordan el siguiente sistema:
1 2 3 1
1 2 3 2
1 2 3 3
2 2 6 4 .................
2 7 6 .................
2 6 7 1 .................
x x x R
x x x R
x x x R
+ + =
+ + =
− − − = −
51
Solución: Matriz ampliada del sistema
2 2 6 4
2 1 7 6
2 6 7 1
− − − −
Las transformaciones elementales de fila para obtener la matriz diagonal equivalente son las siguientes:
1
2 1
3 1
1 2
2
3 2
2 2 6 4 / 2 1 1 3 2
2 1 7 6 2 1 7 6 2
2 6 7 1 2 6 7 1 2
1 1 31 1 3 2 2
0 1 1 2 0 1 1 2
0 4 1 3 0 4 1 3 4
1 0 4 4 1 0 4 4
0 1 1 2 0 1 1 2
0 0 5 5 3 / 5 10 0 1
R
R R
R R
R R
R
R R
R
→ → → − − − − − − − − − +
− → − → − → − − → − − − − +
→ − − − → → − − − − −
1 3
2 3
4
1 0 0 0
0 1 0 1
0 0 1 1
R R
R R
−
→ +
→ −
Con la matriz diagonal final pasamos a un sistema de ecuaciones lineales
diagonal equivalente al original:
1
2
3
01 0 0 0
0 1 0 1 1
0 0 1 0 1
x
x
x
=
− = − =
⇔
Por tanto la solución es 1 0x = , 2 1x = − , 3 1x = .
52
2.2.5 Método de Factorización LU de Gauss.
Podemos formalizar el método de eliminación simple de Gauss en los términos siguientes:
Dado un sistema de ecuaciones lineales =Ax b con n nM ×∈A invertible, lo
que se pretende con el método de eliminación simple de Gauss es encontrar
una matriz triangular superior U tal que el sistema =Ax b sea equivalente
a =Ux d , donde U es una transformación de A .
Transformación( A)=U ⇒ existe H invertible tal que HA=U
por otro lado, =Ax b⇔ HAx = Hb⇒ HA=U y Hb = d , es decir, el principio que rige el método de eliminación simple de Gauss se puede resumir en:
“determinación de una matriz invertible H tal que
la matriz HA sea triangular superior”.
Como hemos visto, en forma matricialmente esto se corresponde con un
proceso que partiendo de (1)A = A , ( ) ( )(1)
ij ija a= , construye en la etapa k-ésima en
la forma siguiente:
(10) ( 1) ( ) ( )k k k+ =A H A , para 2,..., -1k n= .
con:
(11)
( )( )( )
1,( ) ( )
( )
( )
( )
1 0
1
1 det 1
0 0 1
k
k kk k
k
kk
k
nk
k
kk
a
a
a
a
+
− = = −
⋱
⋮ ⋱
H H
Recordemos que decíamos que para poder realizar cada etapa k-ésima se exige (y esta es la característica esencial de Gauss normal) que:
( ) 0, 1, , kkk
a k n≠ = … , por tanto, los elementos distintos de 0 y 1 están bien
definidos. Por otro lado obsérvese que en la etapa k-ésima se hacen ceros en la columna k por debajo de la diagonal principal sumando a las filas i = k+1,…, n, la
fila k multiplicada por ( )
( )
kikk
kk
a
a
−.
53
Por ejemplo, para k=1 y k=2, ( )kH viene dada por:
(1)
2,1
(1)
11
(1) (1)
,1
(1)
11
(1)
,1
(1)
11
1 0 0 0
1 0 0
0 1 0
0 0 1
k
n
a
a
a
a
a
a
− = − −
⋯ ⋯
⋯ ⋯
⋮ ⋮ ⋯ ⋮ ⋯ ⋮
⋯ ⋯
⋮ ⋮ ⋯ ⋮ ⋯ ⋮
⋯ ⋯
H
(2)
,2
2 (2)
22
(2)
,2
(2)
22
1 0 0 0
0 1 0 0
0 1 0
0 0 1
k
n
a
a
a
a
− = −
⋯ ⋯
⋯ ⋯
⋮ ⋮ ⋯ ⋮ ⋯ ⋮
⋯ ⋯
⋮ ⋮ ⋯ ⋮ ⋯ ⋮
⋯ ⋯
H
Una vez realizadas las (n-1) etapas se tiene:
(12) ( ) ( 1) 2 1...n n−= = =������H
A H H H A HA U
donde U es una matriz triangular superior.
Simultáneamente:
(13) ( 1) 2 1...n− =H H H b Hb
Esta interpretación matricial del Método Simple de Gauss origina el Método de factorización LU.
Teniendo en cuenta que todas las ( )kH son matrices triangulares inferiores con elementos diagonales iguales a uno (por tanto, invertibles), se tiene que la matriz:
(14) ( ) ( ) ( ) ( )1 1 1 11 ( 1) (2) (1) (1) (2) ( 1)... ...n n
− − − −− − −= =L H H H H = H H H
es triangular inferior con unos en la diagonal. Por tanto, se tiene:
(15) 1−= ⇔ =HA U A= H U LU , resultado que se recoge en el teorema 1.3.
Teorema. 1.3 (Factorización LU). Sea ( )ij n na M ×∈A = tal que las n
submatrices principales:
11 1
1
k
k
k kk
a a
, k = 1,...,n
a a
∆
⋯
⋮ ⋱ ⋮
⋯
=
sean invertibles ( ( )det 0, 1,...,k k n∆ ≠ ∀ = ). Entonces,
a) 1,..., , 0k
kkk n a∀ = ≠ y, por tanto, existe una matriz triangular inferior
( )ij n nl M ×∈L = , con elementos diagonales 1, 1,...,iil i n= ∀ = , y una matriz
triangular superior ( )ij n nu M ×∈U = , con elementos diagonales 1, 1,...,iiu i n= ∀ = ,
tales que A= LU
54
b) Además esta factorización es única y viene dada por:
Para i=1
1
1
11
, 1,...,
, 2,...,
ij j
j
ij
u a j n
al j n
u
= =
= =
Para i=2,…n 1
1
1
1
, ,...,
, 1,...,
i
ij ij ik kj
k
i
ij jk ki
kij
ii
u a l u j i n
a l u
l j i nu
−
=
−
=
= − =
−= = +
∑
∑
Como consecuencia del teorema 1.3, si la eliminación de Gauss es simple, la resolución del sistema =Ax b se puede sustituir por la resolución de LUx = b que integra dos sistemas con matriz triangular (por tanto, fácilmente resolubles):
(16) �=
≡ = ≡ =Y
LY bAx = b LUx b
Ux Y
Observación. A la hora de implementar el método de factorización LU de Gauss en el ordenador, esta estructura de cálculo permite almacenar cada iju en
la posición de ija y cada jil en la correspondiente posición de jia , con el
consiguiente ahorro de memoria. El coste de este método es de 22n operaciones.
Como aplicación directa del método LU se tiene que:
(17) ( ) ( ) ( ) ( )1
...11 22 nndet det det det u u u
=��
A = L U = U =
Ejercicio. 1.10 Resolver por el método de factorización de Gauss el siguiente sistema.
1 2 3
1 3 4
1 2 3 4
1 2 3 4
2 3 3 7
4 10 4 16
6 9 7 2 17
10 9 20 3 39
x x x
x x x
x x x x
x x x x
+ − = −
− + + =
+ − + = − − − + + =
Solución:
1
2
3
4
2 3 3 0 7
4 0 10 4 16:
6 9 7 2 17
10 9 20 3 39
x
x
x
x
− − − = − − − −
Ax = b
Aplicando (14) y (15) se tiene:
55
2 3 3 0 1 0 0 0 2 3 3 0
4 0 10 4 2 2 0 0 0 3 2 2
6 9 7 2 3 0 2 0 0 0 1 1
10 9 20 3 5 2 1 1 0 0 0 2
− − − − = = − − − − −
A LU =
Por (16) se obtiene:
(18)
1
2
3
4
1 1
2 2
3 3
4 4
1 0 0 0 7
2 2 0 0 16)
3 0 2 0 17
5 2 1 1 39)
)2 3 3 0
0 3 2 2)
0 0 1 1
0 0 0 2
y
ya
y
ya
bx y
x yb
x y
x y
− − = − −
= ≡ ≡ = − = −
LY bAx = b
Ux Y
De a) se obtiene fácilmente
1
2
3
4
7
1
2
0
y
y
y
y
− =
y sustituyendo en b) se tiene la solución
buscada
1
2
3
4
0
1
2
0
x
x
x
x
− =
.
2.2.6 Inconvenientes de los métodos de Gauss.
1. Errores de redondeo. La computadora maneja las fracciones en forma decimal con cierto número limitado de cifras decimales, y al manejar fracciones que se transforman a decimales que nunca terminan, se introduce un error en la solución de la computadora. Este se llama error por redondeo.
Cuando se va a resolver solamente un pequeño número de ecuaciones, el error por redondeo es pequeño y generalmente no se afecta sustancialmente la precisión de los resultados, pero si se van a resolver simultáneamente muchas ecuaciones, el efecto acumulativo del error por redondeo puede introducir errores relativamente grandes en la solución. Por esta razón el número de ecuaciones simultáneas que se puede resolver satisfactoriamente con el método de eliminación de Gauss, utilizando de 8 a 10 dígitos significativos en las operaciones aritméticas, se limita generalmente a 15 o 20.
56
2. Sistemas mal condicionados. La obtención de la solución depende de la condición del sistema. En sentido matemático, los sistemas bien condicionados son aquellos en los que un cambio en uno o más coeficientes provoca un cambio similar en la solución. Los sistemas mal condicionados son aquellos en los que cambios pequeños en los coeficientes provocan cambios grandes en la solución.
Una interpretación diferente del mal condicionamiento es que un rango
amplio de respuestas puede satisfacer aproximadamente al sistema. Ya
que los errores de redondeo pueden inducir cambios pequeños en los
coeficientes, estos cambios artificiales pueden generar errores grandes en
la solución de sistemas mal condicionados.
2.2.7 Condicionamiento de Sistemas Lineales.
Un ejemplo, propuesto por R. S. Wilson, muy ilustrativo para entender el problema de condicionamiento de un sistema de ecuaciones lineales es el siguiente:
Sistema de ecuaciones lineales cuya matriz ampliada y solución exacta son:
10 7 8 7 32 1
7 5 6 5 23 1
8 6 10 9 33 1
7 5 9 10 31 1
solución exacta
→
En este sistema si se produce una pequeña variación en los términos independientes se produce una fuerte variación en la solución del sistema:
−−
→
1.1
5.4
6.12
2.9
9.30
1.33
9.22
1.32
10957
91068
5657
78710
exactasolución
esto indica que el método de resolución empleado (Gauss) está mal condicionado.
57
2.3 Método de mínimos cuadrados.
Consideremos ahora un sistema de ecuaciones =Ax b , no necesariamente cuadrado, donde A es una matriz m×n cuyas columnas son linealmente independientes. Esto implica que hay más filas que columnas, m ≥ n, y que además el rango de A es n. Se desea que el sistema tenga solución, es decir, que se verifique cualquiera de las siguientes igualdades:
=Ax b , 0Ax - b = , 0-Ax b = ,
20-Ax b = ,
2
20-Ax b = .
Es muy probable que este sistema no tenga solución, es decir, tal vez no existe x que cumpla exactamente las m igualdades de =Ax b . Entonces se cambia el nivel de exigencia y se quiere que el incumplimiento (el error, medido por
2
2bAx − ) sea lo más pequeño posible, lo que equivale a minimizar esa cantidad,
es decir al siguiente problema de optimización
(19) 2
2mín -x
Ax b
El vector x que verifica (19) se llama solución por mínimos cuadrados. Si las columnas de A son linealmente independientes entonces tal solución x existe y es único.
Obtención de la solución:
Sea 2
2( )f x -= Ax b , entonces
( ) ( )2 2
11 1 12 2 1 1 1 1 2 2( ) n n m m mn n mf x a x a x a x b a x a x a x b= + +…+ − +…+ + +…+ −
Para obtener el mínimo de ( )f x se requiere que las n derivadas parciales
( ) ( ) ( )1 2
, ,...,n
f x f x f x
x x x
∂ ∂ ∂∂ ∂ ∂
sean nulas.
( ) ( ) )
( )( ) ( )( )( ) ( )( ) ( )
( ) ( ) ( ) ( ) ( )( )( )
11 1 12 2 1 1 11 1 1 2 2 1
1
1 11
1
T
1
T T
2 2( ]
2 1,: ,:
2 1,: ,..., ,: :,1
2 :,1 2 :,1 2 :,1
n n m m mn n m m
m m
m
fa x a x a x b a a x a x a x b a
x
b a m b a
b m b
b
∂= + +…+ − +…+ + +…+ −∂
= − +…+ −
= − −
= − = −− =
x
A x A x
A x A x A
Ax A Ax bb A A Ax
De forma similar,
58
( ) ( ) )
( ) ( ) ( )( ) ( )
11 1 12 2 1 1 12 1 1 2 2
T T
2
2
2 2( ]
2 :, 2 2 , : 2
n n m m mn n m m
fa x a x a x b a a x a x a x b a
x
b
∂= + +…+ − +…+ + +…+ −∂
= −− = A Ax b
x
A Ax
………………………………………………………………………………………………………………….
( ) ( ) )
( ) ( ) ( )( )( )
11 1 12 2 1 1 1 1 1 2
T
2
T
2 2( ]
2 : 2 , , :
n n n m m mn n m mn
n
fa x a x a x b a a x a x x b
x
n n
a a
b
∂= + +…+ − +…+ + +…+ −
−
∂
= − = A Ax b
x
A Ax
Igualando a cero las derivadas parciales y eliminando el 2 se tiene:
( )( )( )( )( )( )
( )( )( )
T
T
T
:,1 0
:, 2 0
....................................
:, 0n
− =
− =
− =
A Ax b
A Ax b
A Ax b
Es decir
(20) ( )( )( ) ( )( )( ) ( )( )( )( ) ( )
( ):,1 , :, 2 ,..., :, 0,0,...,0
(
T
T T
T T
T
n− − − =
⇒ − ⇔ == 0
A Ax b A Ax b A Ax b
A A Ax A bAx b
Las ecuaciones (20) se llaman ecuaciones normales para la solución (o pseudo-solución) de un sistema de ecuaciones por mínimos cuadrados.
La matriz TA A es simétrica de tamaño n×n. En general, si A es una matriz
m×n de rango r, entonces TA A también es de rango r. Como se supuso que el
rango de A es n, entonces TA A es invertible. Más aún, TA A es definida positiva.
Por ser TA A invertible, hay una única solución de (20), o sea, hay un solo vector x que hace que las derivadas parciales sean nulas. En general, las derivadas parciales nulas son simplemente una condición necesaria para obtener el mínimo de una función (también lo es para máximos o para puntos de silla),
pero en este caso, como TA A es definida positiva, f es convexa, y entonces anular las derivadas parciales se convierte en condición necesaria y suficiente para el mínimo.
En resumen, si las columnas de A son linealmente independientes, entonces la solución por mínimos cuadrados existe y es única. Para obtener la solución por mínimos cuadrados se resuelven las ecuaciones normales (20).
Si el sistema =Ax b tiene solución exacta, ésta coincide con la solución por mínimos cuadrados.
En SCILAB la orden para hallar por la solución por mínimos cuadrados es la misma que para resolver sistemas de ecuaciones cuadrados, a saber, A\b . Por ejemplo, para resolver el sistema
59
2 3 431
4 5 772
6 7 109
x
x
≅
basta con
-->A=[2,3;4,5;7,6]; b=[43;77;109]; -->x=A\b
El resultado obtenido es x =(7.6019417, 9.3009709)
La solución por mínimos cuadrados de un sistema de este tipo (sobre-
determinado) también se puede hacer en SCILAB mediante ( ) ( )'* \ '*A A A b o por
medio de ( )*pinv A b , pero ambas son menos eficientes que A\b.
Nota: ( )M pinv A= produce una matriz M de las mismas dimensiones que
A' tal que :
* * , * * A M A A M A M M= =
Los cálculos para obtener ( )M pinv A= se basan en la descomposición de
valores singulares, (función svd en SCILAB), y cualquier valor singular menor que una cierta tolerancia es tratado como cero. Se puede seleccionar la tolerancia a través de la siguiente sentencia SCILAB: ( ),M pinv A tol= .
Ejercicio. 1.11 Resolver por mínimos cuadrados el sistema dado por:
1
2
3
2 1 0 3.1
2 2 3 8.9
2 2 1 3.1
5 4 2 0.1
x
x
x
− − = − − −
Las ecuaciones normales T T=A Ax A b son:
1
2
3
2 1 0 3.12 2 2 5 2 2 2 5
2 2 3 8.91 2 2 4 1 2 2 4
2 2 1 3.10 3 1 2 0 3 1 2
5 4 2 0.1
x
x
x
− − − − − − − = − − − − − −
-->A'*A
37. 22. - 18.
22. 25. - 12.
- 18. - 12. 14.
->A'*b - 4.9
- 20.5
23.4
Por tanto la solución por mínimos cuadrados es,
60
1
2
3
37 22 18 4.9
20 25 12 20.5
15 12 14 23.4
x
x
x
− − − = −
− −
La solución por mínimos cuadrados se puede obtener con la sentencia SCILAB:
--> x= A’*A \ A’*b
2.324
- 1.068
3.744
( ) ( )1 2 3, , 2.324, 1.068, 3.744T x x x= = −x
El error de la solución, - Ax b , viene dado por:
-->A*x-b 0.48
- 0.18
0.06
- 0.24
Dado que
0.
0.-
0.
0.
≠
Ax b , el sistema no tiene solución exacta.
Ejercicio. 1.12 Resolver por mínimos cuadrados el sistema dado por:
1
2
3
2 1 3 3
2 2 0 9
2 2 6 3
5 4 6 0
x
x
x
− − = − − −
Las ecuaciones normales T T=A Ax A b son:
1
2
3
2 1 3 32 2 2 5 2 2 2 5
2 2 0 91 2 2 4 1 2 2 4
2 2 6 33 0 6 6 3 0 6 6
5 4 6 0
x
x
x
− − − − − − − = − − − − − −
-->A'*A
37. 22. 48.
22. 25. 15.
48. 15. 81.
->A'*b
- 6.
- 21.
27.
61
1
2
3
37 22 48 6
20 25 15 21
48 15 81 27
x
x
x
− = −
De nuevo la solución por mínimos cuadrados se puede obtener como
--> x= A’*A \ A’*b
- 8.1219512
3.6219512
4.4756098
( ) ( )1 2 3, , 8.1219512, 3.6219512, 4.4756098T x x x= = −x
El error, - Ax b , viene dado por:
-->A*x-b 11.812
- 11.512
- 26.248
29.812
Dado que
0.
0.-
0.
0.
≠
Ax b , tampoco en este caso el sistema tiene solución exacta.
Ejercicio. 1.13 Resolver por mínimos cuadrados el sistema dado por:
1
2
2 1 3
1 2 9
2 2 6
5 4 6
x
x
− − = − −
Las ecuaciones normales T T=A Ax A b son:
1
2
2 1 3
2 1 2 5 1 2 2 1 2 5 9
1 2 2 4 2 2 1 2 2 4 6
5 4 6
x
x
− − − − − − = − − − −
-->A'*A 34. 20.
20. 25.
-->A'*b
48.
15.
1
2
34 20 48
20 25 15
x
x
=
62
--> x= A’*A \ A’*b
2.
- 1.
( ) ( )1 2, 2., 1.T x x= = −x
El error, - Ax b , viene dado por:
-->A*x-b 0.
0.
0.
0.
- Ax b = (0, 0, 0, 0) indica que el sistema inicial tiene solución exacta y la solución por mínimos cuadrados coincide con ella.
Ejercicio. 1.14 Resolver por mínimos cuadrados el sistema con matriz de coeficientes:
A = [31.578356, 55.530697 , 21.362966, 34.903639, 20.426016, 7.7575968;
37.858232, 11.960808, 40.549980, 11.053652, 83.104313, 58.460923;
46.195234, 76.139997, 30.953712, 20.233778, 1.221633, 75.287136 ;
62.873698, 47.909885, 67.629716, 13.046910, 48.844617, 5.172298;
28.785153, 28.169693, 97.069163, 85.739530, 95.498771, 59.586251;
32.920487, 23.800978, 54.417966, 63.780164, 5.8743121, 38.337053;
47.192330, 32.942055, 2.0474797, 40.711227, 82.584649, 49.002203;
33.537696, 23.067280, 89.413650, 66.919379, 29.807416, 52.727951]
y vector de términos independientes
b=[36.159398; 26.739977; 7.7368706; 14.941003; 32.018391; 20.260546; 44.988587;
77.075744]
Solución:
-->A'*A =
13781.776 12658.604 15572.772 12008.962 14758.044 13319.484
12658.604 14296.672 13427.846 11054.156 10799.49 12531.701
15572.772 13427.846 28015.318 20562.853 19571.334 17901.673
12008.962 11054.156 20562.853 19474.858 16213.039 15585.303
14758.044 10799.49 19571.334 16213.039 26574.067 16895.555
13319.484 12531.701 17901.673 15585.303 16895.555 19374.469
-->A'*b
=
9747.6857
8276.8087
14300.991
12936.013
12889.568
11456.691
63
A\b A'*A\ A'*b pinv(A)* b
0.5651239
- 0.2902118
- 0.0827939
0.5455640
- 0.0014527
0.0294353
0.5651239
- 0.2902118
- 0.0827939
0.5455640
- 0.0014527
0.0294353
0.5651239
- 0.2902118
- 0.0827939
0.5455640
- 0.0014527
0.0294353
El error, - Ax b , viene dado por:
-->A*x-b - 16.957259
- 4.5432794
6.9628039
8.2863009
16.428484
22.846899
- 4.515764
- 34.202525
El sistema inicial no tiene solución exacta.
NOTAS Y RECOMENDACIONES:
Una característica importante de los métodos directos es que la solución se encuentra por métodos algebraicos con un número fijo de operaciones y la solución es exacta.
El número de operaciones que realizan los métodos directos para la resolución de sistemas de ecuaciones lineales es de orden n3.
La técnica de pivote parcial suele conducir a mejores resultados que la de pivote trivial en sistemas mal condicionados. Sin embargo, el pivote total resulta excesivamente costoso en relación al coste total de resolución.
Los métodos directos se recomiendan para:
• Sistemas lineales pequeños (n<=1000).
• Matriz de coeficientes de tipo matriz “llena”, donde la mayoría de los elementos son no nulos (aij ≠ 0)
64
3 Métodos iterativos para resolver sistemas lineales.
Los métodos iterativos (como el de Jacobi, Gauss Seidel y relajación) consisten básicamente en obtener una ecuación de recurrencia matricial,
sucesión de aproximaciones ( ) ( ) ( )( ){ }1 ,... ,k k k
nk
x x∈
=ℕ
x que converge a la solución del
sistema =Ax b , a partir de un vector solución inicial ( ) ( ) ( )( )1
0 0 0,..., nx x=x y
realizando las iteraciones necesarias hasta que la diferencia entre dos vectores consecutivos cumpla con una tolerancia predefinida, tol.
En general, los sistemas lineales de gran tamaño =Ax b , con ( )n n×∈ ℝA MMMM
invertible, que surgen en la práctica suelen tener la matriz con muchos ceros (matriz hueca o rala, “sparse”). Los métodos directos de resolución no suelen resultar eficaces en este caso ya que a lo largo del proceso de eliminación muchos de los coeficientes nulos de A dejan de serlo, elevando notablemente el uso de memoria en el ordenador.
Consideremos un sistema lineal =Ax b , siendo A una matriz invertible, es decir, el sistema es compatible y determinado. Un método iterativo para la
resolución del sistema anterior construye la sucesión { } k
k∈ℕx de vectores que
“aproximan” la solución exacta 1−=x A b , en el sentido
lim k
k→∞=x x
Los métodos iterativos que vamos a estudiar, y que generalmente son los más
usados, son los llamados métodos lineales que construyen la sucesión { } k
k∈ℕx
mediante el siguiente esquema lineal:
(21) ( )
( ) ( )
0
10,1,.....
k k
vector arbitrario
, k+ =
+
=
x
x Bx c
donde la matriz ( )n n×∈ ℝB MMMM (matriz del método) y el vector n∈ℝc (vector del
método) se eligen a partir de la matriz de los coeficientes del sistema, A , y del vector de términos independientes, b . Fundamentalmente los distintos métodos
iterativos se diferencian por la elección de B y c . Llamaremos a la expresión ( ) ( )1
0,1,.....k k
, k+ = + =x Bx c fórmula del método.
Definición. 1.8 (Norma de una matriz). Una norma en ( )n n× ℝMMMM es toda
aplicación ( ): n nו ∈ → ∈ℝ ℝA AMMMM
que verifica para todo ( )n n, ×∈ ℝA B MMMM y α ∈ℝ :
65
1. 0≥A
2. 0 es la matriz nula= ⇔ A A
3. αα =A A
4. ≤ +A+ B A B
5. .≤A* B A B
Proposición. 1.2 Si : n• ∈ → ∈ℝ ℝx x es una norma vectorial en nℝ ,
entonces
( )1
: n n máx× =• ∈ → = ∈ℝ ℝ
xA A AxMMMM
es una norma matricial llamada norma matricial inducida. Por ejemplo:
11 11 1
1
n
ijj n
i
máx máx a= ≤ ≤ =
= = ∑x
A Ax
∑=≤≤=
==n
i
ijnjx
amáxmáx1
2
12122
AxA
1 11
n
iji n
j
máx máx a∞
∞ ∞= ≤ ≤ =
= = ∑x
A Ax
-->A = [1, 2, 0.2267; 3, 4, 0.2770; -2, 5, 0.3300] 1. 2. 0.2267
3. 4. 0.277
- 2. 5. 0.33
-->norm(A)
6.7629832
-->norm(A,2)
6.7629832
-->norm(A,"inf")
7.33
-->norm(A,1)
11.
Definición. 1.9 (Radio espectral de una matriz). El radio espectral de una matriz M se define como
( ) { }1
/ .i ii n
máx es un autovalor deρ λ λ≤ ≤
=M M
Proposición. 1.3 . Si ( )n n×∈ ℝM MMMM entonces
( ) 1 1ρ < ⇔ <M M , para alguna norma matricial inducida.
Definición. 1.10 (Convergencia de un método lineal). Un método lineal se
dice convergente si cualquiera que sea el vector inicial 0 n∈ℝx se verifica
66
1lim k
k
−
→∞= =x x A b
En el supuesto de que el método sea convergente, entonces tomando límites en la fórmula del método se tiene:
( ) ( )( )1lim lim
k k
k k
+
→∞ →∞= = + +x x Bx c = Bx c
es decir, ( )-I B x = c
siendo x la solución exacta, y, por tanto,
( )- -1c = I B A b
Por tanto, B y c deben elegirse de tal modo que el sistema ( )-I B x = c tenga
solución (es decir, ( )-I B sea invertible) y los sistemas =Ax b e ( )-I B x = c sean
equivalentes (tengan la misma solución).
Tenemos entonces la siguiente relación:
( ) ( )( ) ( ) ( )
( )( ) ( )( ) ( )( )( ) ( )( ) ( )( )1
1 1 1 02 ...
k k k
k k k k
-+
− − −
= + − + = −
= + − + = − = − = = −
x x Bx c Bx c Bx x
B Bx c Bx c B B x x B x x B x x
(22) ( ) ( )( )1 01k k-
+ += −x x B x x
Como consecuencia de (22) se tiene el siguiente resultado de caracterización de la convergencia para los métodos iterativos lineales:
Teorema. 1.4 (Convergencia de los métodos iterativos). Para
cualquier vector semilla ( )0 n∈ℝx , la sucesión ( ){ }
k
k∈ℕx definida por
( ) ( )1k k+ = +x Bx c , 0para k ≥ , converge a la solución única de +Bx c si y sólo si
( ) 1ρ <B .
(23) ( )1lim 1k
kρ−
→∞= = ⇔ <x x A b B
Un aspecto fundamental de la convergencia de un algoritmo lo constituye la velocidad con que lo hace. Veamos cómo se define este concepto.
Velocidad de convergencia
De (22) se obtiene
(24) ( ) ( )( )0k k- ≤ −x x B x x
67
Esto puede interpretarse como que en cada una de las k primeras iteraciones
el error se ha reducido en un factor de 1/k
kB , y en consecuencia se puede estimar
que para que el error se reduzca en un factor de 10-q se deben realizar N iteraciones, verificándose
(25) ( )1/
10N
kk q−≤B , o bien,
( ) 1/
10log
kk
qN ≥
− B
Definición. 1.11 (Velocidad de convergencia en k iteraciones). Al número
( ) 1/
10log
kk kR = −B B
se le denomina velocidad media de convergencia en k iteraciones.
Se puede demostrar que ( ) 1/
limk
k
kρ
→∞=B B . Por tanto la expresión (25) puede
modificarse en la forma siguiente:
( )10log
qN
ρ≥
− B
Definición. 1.12 (Velocidad asintótica de convergencia). Al número
( )10
1log
ρ
− B
se le denomina velocidad asintótica de convergencia.
Como puede observarse, dado que se exige ( ) 1Bρ < , el método convergerá
más rápidamente cuanto más pequeño sea ( )Bρ .
Estimación del error
Una cuestión de indudable interés consiste en estimar el error cometido al estimar la solución exacta del sistema por la aproximación obtenida en la
iteración k, es decir ( )kerror -= x x . Para obtener tal estimación, partimos de
( ) ( )1/
lim limk kk k
k kρ ρ
→∞ →∞= ⇒ =B B B B y dado que ( ) ( )( )0k k
- ≤ −x x B x x
por (23)
(26) ( ) ( )( ) ( )( ) ( )0 0lim lim
kk k
k k- Bρ
→∞ →∞≤ − = −x x B x x x x
Por tanto, ( )( ) ( )0k
Bρ −x x es una buena estimación del error cometido al
aproximar la solución exacta de =Ax b por la solución obtenida en la iteración k,
68
( )k-x x . El problema reside en que no conocemos x . Ahora bien, si partimos de
( ) ( )( )2 1k k-
+ += −x x B x x tomando normas en la siguiente expresión
( ) ( ) ( ) ( )1 1 2 2k k k k- -
+ + + += + −x x x x x x
resulta ( ) ( ) ( ) ( ) ( ) ( ) ( )1 1 2 2 2 1 1k k k k k k k
- - -+ + + + + + +≤ + − ≤ + −x x x x x x x x B x x
es decir, ( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
1 1 2 1 1
1 11
k k k k k k
k k k
- - -
-
+ + + + +
+ +
− − ≤ = ⇒
− − ≤ ⇒
x x B x x x x B x x
B x x B x x
(26) ( )
( )( ) ( )1 1
1
k k k
Cota del error
error -+ += − ≤
−� �
Bx x x x
B
Parada del algoritmo iterativo
Otra cuestión importante consiste en decidir cuándo detener el proceso iterativo. Habitualmente el proceso se detiene cuando la aproximación a la solución es suficiente, es decir, cuando, dada una tolerancia adecuada, tol, se
verifica ( )1ktol
+ − ≤x x . Como se puede apreciar el problema consiste en conocer
qué cantidad colocar en la parte izquierda de la desigualdad anterior, pues la solución exacta no se conoce. Una opción muy interesante puede ser colocar la cota de error:
(27) ( )( ) ( )k+1 kB
x - x1- B
tol≤
El algoritmo iterativo se detendrá en la iteración N=k para la que se verifique (27).
Ejercicio 1.15 Consideremos el siguiente sistema de ecuaciones lineales:
1 2 3
1 2 3 4
1 2 3 4
2 3 4
10 2 6
11 3 25
2 10 11
3 8 15
x x x
x x x x
x x x x
x x x
− + =
− − − + =
− + − = − − + =
y un método iterativo lineal para resolver el sistema anterior con la matriz B y el vector c del método dados a continuación:
69
0 0.1 0.2 0 0.6
0.0909091 0 0.0909091 0.2727273 0.27272730,
0.2 0.1 0 0.1 1.1
0 0.375 0.125 0 1.875
− − − − = = − − −
B c
a) Calcular el número de iteraciones necesarias para que el error se reduzca en un factor 10-13.
b) Calcular la velocidad de convergencia para 30 iteraciones.
c) Calcular la velocidad de convergencia asintótica y la velocidad de convergencia para k=27 y k=500. Explicar los resultados obtenidos.
d) Estimar el error en las iteraciones k2, k=6, k=26 y en la “última iteración”.
Solución:
a) El número de iteraciones necesarias para reducir el error en el factor 10-13 viene dado por (25)
( ) 1/
10
13
logk
kN ≥
− B
que en función del radio espectral de B adopta la forma:
( )10
13
logN
ρ≥
− B
Por otro lado, el radio espectral
( ) { }1
/ .i ii n
máx es un autovalor deρ λ λ≤ ≤
=B B
se puede obtener en SCILAB a través de la sentencia
->re=max(abs(spec(B))) 0.3197102
y sustituyendo en la desigualdad se tiene,
10
1326.249713
log 0.3197102 N ≥ =
−
y como consecuencia N=27.
Además, ( ) 0.3197102 1reρ = = <B ⇒ para el sistema considerado, el método
iterativo definido por la matriz B es convergente, sea cual sea el vector semilla.
b) La velocidad de convergencia para 30 iteraciones, usando para “medir” B la norma infinita, viene dada por
( ) 1/3030 30
10logR∞
= −B B
70
Utilizando SCILAB:
-->B^30 10^(-15) *
- 0.0417015 0.3053955 - 0.0956411 - 0.0193451
- 0.2776323 1.378006 - 0.6558203 0.6015871
- 0.0956411 0.7214023 - 0.2187048 - 0.0678343
- 0.0241813 - 0.8271822 - 0.0847929 1.1084788
-->norm(B^ 30,"inf")
2.913D-15
-->-log10(norm(B^30,"inf")^(1/30))
0.4845218
Resulta que la velocidad de convergencia para 30 iteraciones es
( )30 0.4845218 R =B
c) Por su parte, la velocidad de convergencia asintótica viene dada por
( )10 10
1 1log log 0.4952435
0.3197102ρ = = B
Como puede observarse, la velocidad de convergencia para 30 iteraciones está muy próxima a la velocidad de convergencia asintótica.
Para 27 iteraciones, (con factor de error 10-13), se tiene
-->-log10(norm(B^27,"inf")^(1/27))
0.4848160
Y para un número alto de iteraciones se obtiene una velocidad de convergencia muy similar a la velocidad de convergencia asintótica:
-->-log10(norm(B^500,"inf")^(1/500))
0.4947236
( ) ( )1/500
500 500
10 100.4947231
log l6 0.49524g 35oRρ∞
= − = ≈ =
B B
B
d) Estimar el error en las iteraciones k=6, k=10, k=25 y en la “última iteración”.
Estamos ante un método iterativo lineal, por tanto la fórmula del método
viene dada por ( ) ( )10,1,.....
k k, k
+ = + =x Bx c , con ( ) ( )00,0,0,0=x . Entonces:
71
( ) ( )
( )
01
0 0.1 0.2 0 0
0.0909091 0 0.0909091 0.2727273 0
0.2 0.1 0 0.1 0
0 0.375 0.1
0.600000, -2.2727
25 0 0
0.6
0.27272730
27,
1.
-1.100000
1
1.875
, 1.875 000
− − − = + − −
− + −
Bx c =x
=
( ) ( )
( )
12
0 0.1 0.2 0 0.6
0.0909091 0 0.0909091 0.2727273 0.27272730
0.2 0.1 0 0.1 1.1
0 0.375 0.125 0 1.875
0.6
0.27272730
1.1
1.875
0.592727, -1.715909, -1.259773, 2.589773
− − − − = + − − −
− + −
x
=
Bx c =
( ) ( )56
0 0.1 0.2 0 0.671327
0.0909091 0 0.0909091 0.2727273 1.602753
0.2 0.1 0 0.1 1.164087
0 0.375 0.125 0 2.326620875
0.672542 -
0.6
0.27272730
1.1
1.
1.593398
875
-1.161879
− − − − = + − − −
− + −
=
Bx c =x
( ) 2.330521
72
( ) ( )226 5
0 0.1 0.2 0 0.672880
0.0909091 0 0.0909091 0.2727273 1.593578
0.2 0.1 0 0.1 1.161190
0 0.375 0.125 0 2.327443
0.6
0.
0.672880, -1.593578, -1.16
27272730
1.1
1.
11
875
9
− − − − = + − − −
− + −
x
=
Bx c =
( )0, 2.327443
( ) ( )227 6
0 0.1 0.2 0 0.672880
0.0909091 0 0.0909091 0.2727273 1.593578
0.2 0.1 0 0.1 1.161190
0 0.375 0.125 0 2.327443
0.6
0.
0.672880, -1.593578, -1.16
27272730
1.1
1.
11
875
9
− − − − = + − − −
− + −
x
=
Bx c =
( )0, 2.327443
La estimación de los errores con respecto a la solución exacta en k=2, k=6,
k=26 y k=27, utilizando la norma infinito para la matriz B viene dada por:
( )
( )( ) ( )1 1
( 1)1
k k k
Cota del error
error k -+ +∞
∞∞
+ = − ≤−� �
Bx x x x
B
-->norm(B,"inf") 0.5
( ) ( ) ( ) ( ) ( )1 1 10.5( 1)
0.5
k k k k kerror k - -
+ + +
∞ ∞+ = − ≤ =x x x x x x
x(1)
= [0.600000; -2.272727; -1.100000; 1.875000]
x(2)
= [0.592727; -1.715909; -1.259773; 2.589773]
x(5)
= [0.671327; -1.602753; -1.164087; 2.326620]
x(6)
= [0.672542; -1.593398; -1.161879; 2.330521]
x(25)
=[0.672880; -1.593578; -1.161190; 2.327443]
x(26)
=[0.672880; -1.593578; -1.161190; 2.327443]
x(27)
=[0.672880; -1.593578; -1.161190; 2.327443]
73
-->norm(x(2)
-x(1)
,"inf") 0.71477300000000010 -->norm(x
(6)-x
(5),"inf")
0.00935500000000000 -->norm(x
(26)-x
(25),"inf")
0. -->norm(x
(27)-x
(26),"inf")
0.
( ) ( ) ( )2 2 1(2) 0.71477300000000010 error -
∞= − ≤ =x x x x
( ) ( ) ( )6 6 5(6) 0.009355error -
∞= − ≤ =x x x x
( ) ( ) ( )26 26 25(26) 0.error -
∞= − ≤ =x x x x
( ) ( ) ( )27 27 26(27) 0.error -
∞= − ≤ =x x x x
En resumen, en el estudio de los métodos iterativos lineales para la
resolución de un sistema =Ax b se deben tener en cuentas las siguientes reglas:
1. Método bien construido: ( )-I B invertible y los sistemas =Ax b e
( )-I B x = c equivalentes.
2. Método convergente: Comprobar que ( ) 1Bρ < < 1 o que 1<B .
3. Alta velocidad de convergencia: Elegir entre los métodos posibles el
que tenga menor ( )Bρ .
La cuestión es ahora la siguiente: ¿qué método iterativo (es decir, qué matriz B y que vector c ) elegir para resolver el sistema =Ax b?. Cada elección de B y c
caracterizará un método distinto. En los siguientes apartados veremos tres de los métodos más populares y sin duda más eficaces en general, a saber, el método de
Jacobi, el método de Gauss-Seidel y el método de relajación. 3.1 Método de Jacobi.
Consideremos el sistema de ecuaciones lineales siguiente:
1 2 3
1 2 3
1 2 3
4 7
4 8 8 21
2 5 15
x x x
x x x
x x x
− + = − − = − − + + =
con solución exacta ( )2,4,3T=x .
Las ecuaciones del sistema anterior se pueden escribir en la forma siguiente:
74
2 31
1 32
1 23
7
4
21 4
8
15 2
5
x xx
x xx
x xx
+ −=
+ +=
+ −=
Esto sugiere el siguiente proceso iterativo
(27)
( )( ) ( )
( )( ) ( )
( )( ) ( )
1 2 31
1 1 32
1 1 23
7
4
21 4
8
15 2
5
k kk
k kk
k kk
x xx
x xx
x xx
+
+
+
+ −=
+ +=
+ −=
Si comenzamos con una “semilla” ( ) ( )01,2,2
T=x , entonces el proceso
recurrente anterior da lugar en la 1ª iteración al punto ( ) ( )11.75, 3.375, 3.00
T
=x
que está más cerca de la solución que el punto ( )0x .
K x1(k) x2(k) x3(k) 0 1.00 2.00 2.00
1 1.75 3.375 3.00
2 1.84375 3.875 3.025
3 1.96250 3.925 2.9625
4 1.99062500 3.97656250 3.000000000
5 1.99414063 3.99531250 3.000993750
15 1.99999993 3.99999985 2.999999930
19 2.00000000 4.00000000 3.000000000
Como se puede observar en (27), si a partir de la ecuación i-ésima del
sistema despejamos la incógnita ix y consideramos un punto semilla ( )0x , se
obtienen las siguientes aproximaciones como combinación lineal de los puntos recurrentes previamente obtenidos:
(28) ( )( ) ( ) ( ) ( ) ( )
1 1 , 1 1 , 1 11
1
... .., 1,..
..,
k k k k knk ij ji
i
jii
i i i i i i i i in
iij i
n
ii
ab a x a x a xbx i n
a a
x
a
x a− − +
=≠
++ − =− − − − − −
= = ∑
La expresión (28) proporciona los valores de las incógnitas en cada paso del método. Este proceso se conoce como método de iteración de Jacobi.
Siendo
75
11 12 1 11
21 22 2 22
1 2
12 1
21 2
1 2
0 0
0 0
0 0
0 0 0 0
0 0 0 0
0 0 0 0
n
n
n n nn nn
n
n
n n
a a a a
a a a a
a a a a
a a
a a
a a
=
− − − − = − −
⋯ ⋯
⋯ ⋯
⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮
⋯ ⋯
⋯ ⋯
⋯ ⋯
⋮ ⋮ ⋱ ⋮ ⋮ ⋮ ⋱ ⋮
⋯ ⋯
A= D
L= U
Se puede escribir =A D - L -U , de donde
( ) ( ) ( )( ) ( ) �
( )
1
1
1
1
1 1 1
.
J
J J, donde y
− − −
− −
− −
⇔ ⇔ ⇔
=
⇔
=
=
⇔
⇔
����J
J J
cB
D - L -U x = b Dx - L+U x = b Dx = L+U x+ b
D Dx = D L+U x+ D b x = D L+U
Ax b
x = B x+ c B D L+U c
x
D
+ D
b
b
donde
( )
112 1
11 11 11
2 221
2222 22
1 2
0
0,
0
n
n
nn n
nnnn nn
aa b
a a a
a ba
aa a
ba a
aa a
−− −− + = = − −
⋯
⋯
⋮⋮ ⋮ ⋱ ⋮
⋯
-1 -1
J JB = D L U c = D b
Los sistemas =Ax b y J J
B x + c son equivalentes. Por otro lado
(29) ( ) 11 1 1
1 1 111 11 111
,..., ,...,n n n
j j ij j nj ji n
j j jii nn nnj j i j n
a x a x a xb bb
a a a a a a
− −
= = =≠ ≠ ≠
− − −
∑ ∑ ∑D L+U x+ D b =
De la igualdad (29) se deduce el método iterativo de Jacobi, en el cual la
sucesión ( ){ } k
k∈ℕx se construye mediante el siguiente esquema lineal
(30) ( )
( ) ( )
0
10,1,.....
k k
J
vector arbitrario
, k+ =
= J
x
x B x + c
donde ( ) ( )1
n n
−×∈ ℝJB = D L+U MMMM y 1 n− ∈ℝJc = D b son respectivamente la matriz
y el vector del método.
76
En la práctica el método se aplica de acuerdo con el siguiente algoritmo de Jacobi:
1.- Se parte de una solución semilla arbitraria ( ) ( ) ( ) ( )( )0 0 0 0
1 ,..., ...,i n=x x x x .
2.- Se calcula ( ) ( ) ( ) ( )( )1 1 1 1
1 ,..., ...,k k k k
i n
+ + + +=x x x x , para 0k ≥ iterando con la
fórmula
( )( )
1
1
, 1,...,
knk ij ji
i
jii iij i
a xbx i n
a a
+
=≠
= − =∑
4. Una vez fijado el valor semilla, paso 1, el proceso se realiza consecutivamente para 0k ≥ , paso 2, hasta que se cumpla uno o varios de los siguientes criterios:
1) ( ) ( ) tolxx kk ≤−+1
2)
( ) ( )
( ) tolx
xx
k
kk
≤−+
+
1
1
3) tolb
bAx k
≤−)(
4) Cuando agotemos el número máximo de iteraciones prefijado.
siendo tol la tolerancia preestablecida.
Las normas más usuales en los criterios de parada de Jacobi son 1ℓℓℓℓ , 2ℓℓℓℓ y
∞ℓℓℓℓ . Si ( )1,...,n
nx x ∈ℝx =
1ℓℓℓℓ : 1 21... nx x x= + + +x
2ℓℓℓℓ : 2
2 1
n
iix
== ∑x
∞ℓℓℓℓ : { }1
ii n
máx x∞ ≤ ≤
=x .
Por ejemplo, si ( ) ( )
( )
( ) ( )( )( )( )
tol
x
xx
x
xx
n
i
k
n
i
kk
k
kk
≤−
=−
∑
∑
=
+
=
+
+
+
1
21
1
21
2
1
2
1
entonces stop, y por
tanto la solución resulta ser
( ) ( ) ( ) ( )( )1 1 1 1
1 ,..., ...,k k k k
i n
+ + + +=x x x x .
Ejercicio. 1.16 Dado el sistema de ecuaciones lineales:
1 2 3 4
1 2 3 4
1 3 4
1 2 3 4
7 3 2 25
2 8 4 3
3 10
2 2 2 6 15
x x x x
x x x x
x x x
x x x x
− + + =
− − + + =
+ − = + + + =
77
a) Calcular las matrices que definen la fórmula de recurrencia o iteración de Jacobi.
b) Calcular las normas 1
• y ∞• de las matrices obtenidas en el apartado
anterior.
c) Si se construye la sucesión de vectores que define el método de Jacobi a partir de un vector inicial cualquiera, ¿se puede garantizar la convergencia de esta sucesión a la solución del sistema?, razonar la respuesta.
d) Para la sucesión en la que se tiene garantizada la convergencia a la
solución del sistema, calcular la primera y la segunda iteración utilizando como vector de inicialización el vector nulo.
e) Calcular el mínimo número de iteraciones k que debemos realizar para garantizar que
( ) 1010k −
∞− ≤x x*
siendo x* la solución del sistema.
f) Calcular la velocidad de convergencia para 5 y 48 y iteraciones. g) Calcular la velocidad de convergencia asintótica y la velocidad de
convergencia para k=500. Explicar los resultados obtenidos.
h) Estimar el error en las iteraciones k=2 y k=48.
i) Calcular la solución utilizando la función x=Jacobi(A, b, x0, tol, maxit) que se proporciona, calcular también el residuo y su “medida” utilizando la norma infinito.
Solución.
Las matrices asociadas al sistema son
7 3 2 1 25
2 8 1 4 3,
1 0 3 1 10
1 2 2 6 15
− − − = =
A b
a) El método de Jacobi se basa en la descomposición =A D - L -U donde D=(Diag(A), L=-1*(tril(A)-D) y U=-1*(triu(A)-D) y, por tanto,
78
7 3 2 1 7 0 0 0
2 8 1 4 0 8 0 0
1 0 3 1 0 0 3 0
1 2 2 6 0 0 0 6
0 0 0 0 0 3 2 1
2 0 0 0 0 0 1 4
1 0 0 0 0 0 0 1
1 2 2 0 0 0 0 0
− − − − =
− − − − = − − − − −
A= D
L= U
La matriz y el vector que definen el método de Jacobi son respectivamente:
( )+-1
JB = D L U y 1−Jc = D b . Por tanto, por un lado se tiene
( )
7 0 0 0 0 0 0 0 0 3 2 1
0 8 0 0 2 0 0 0 0 0 1 4
0 0 3 0 1 0 0 0 0 0 0 1
0 0 0 6 1 2 2 0 0 0 0 0
1/ 7 0 0 0 0 3 2 1
0 1/ 8 0 0 2 0 1 4
0 0 1/ 3 0 1 0 0 1
0 0 0 1/ 6 1 2 2 0
0 0
− − − − − + = + − − − − −
− − − − − = − − − − −
−
=
-1
-1
JB = D L U
.4285714 0.28577143 0.1428571
0.25 0 0.125 0.5
0.3333333 0 0 0.3333333
0.1666667 0.3333333 0.3333333 0
− − −
y, por otro,
7 0 0 0 25 1/ 7 0 0 0 25 3.5714286
0 8 0 0 3 0 1/ 8 0 0 3 0.375
0 0 3 0 10 0 0 1/ 3 0 10 3.3333333
0 0 0 6 15 0 0 0 1/ 6 15 2.5
b
− − − = = =
-1
-1D
-->BJ=inv(D)*(L+U)
0. - 0.4285714 0.2857143 0.1428571
0.25 0. - 0.125 - 0.5
0.3333333 0. 0. - 0.3333333
0.1666667 0.3333333 0.3333333 0.
79
-->c=inv(D)*b
3.5714286
- 0.375
3.3333333
2.5
b) Se trata de calcular para las matrices D, L y U las normas matriciales
inducidas, que para una matriz M cualquiera, se formulan en la forma siguiente:
11 11 1
1
n
ijj n
i
máx máx m= ≤ ≤ =
= = ∑x
M Mx
1 11
n
iji n
j
máx máx m∞
∞ ∞= ≤ ≤ =
= = ∑x
M Mx
Para la matriz diagonal D:
{ }
4
1 1 41
7 0 0 0,0 8 0 0,0 0 3 0,
0 0 0 0
7,8,3,0 8
ijj
i
máx d máx
máx
≤ ≤ =
+ + + + − + + + + + = = + + +
= =
∑D
{ }
4
1 41
7 0 0 0,0 8 0 0,0 0 3 0,
0 0 0 0
7,8,3,0 8
iji
j
máx d máx
máx
∞ ≤ ≤ =
+ + + + − + + + + + = = + + +
= =
∑D
Para la matriz L:
{ }
4
1 1 41
0 2 1 1 ,0 0 0 2 ,0 0 0 2 ,
0 0 0 0
4,2, 2,0 4
ijj
i
máx l máx
máx
≤ ≤ =
+ − + + + + + + + + = = + + +
= =
∑L
{ }
4
1 41
0 0 0 0,0 2 0 0, 1 0 0 0,
1 2 2 0
0,2,1,5 5
iji
j
máx l máx
máx
∞ ≤ ≤ =
+ + + + − + + + + + = = + + +
= =
∑L
Para la matriz U:
{ }
4
1 1 41
0 0 0 0, 3 0 0 0, 2 1 0 0,
1 4 1 0
0,3,3,6 6
ijj
i
máx u máx
máx
≤ ≤ =
+ + + − + + + + + + = = + + − +
= =
∑U
{ }
4
1 41
0 3 2 1 ,0 0 1 4 ,0 0 0 1 ,
0 0 0 0
6,5,1,0 6
iji
j
máx u máx
máx
∞ ≤ ≤ =
+ − + + + + + + + + − = = + + +
= =
∑U
80
D L U
1• 8 4 6
∞• 8 5 6
En SCILAB:
-->norm(D,1), norm(D,"inf")
8. , 8. -->norm(L,1), norm(L,"inf") 4. , 5. -->norm(U,1), norm(U,"inf")
4. , 6.
c) La convergencia de los métodos iterativos viene caracterizada por el teorema.
1.4 que, en síntesis, dice que “para cualquier vector semilla ( )0 n∈ℝx ,
( ){ } ( )lim 1k
k kρ
→∞ ∈+ = ⇔ <
ℕBx c x B ,
siendo ( )ρ B el radio espectral de la matriz B .
El radio espectral de la matriz del método de Jacobi, J
B , es,
( ) ( ){ }1
/ .i ii n
máx es un autovalor deρ λ λ≤ ≤
= +-1
JB D L U
y se puede obtener en SCILAB a través de la sentencia
->re=max(abs(spec(inv(D)*(L+U))))
0.5911369
( ) 0.5911369 1J reρ = = <B ⇒ para el sistema lineal que estamos resolviendo el
método de Jacobi es convergente, sea cual sea el vector semilla.
Nota: La función radioespectralJacobi , con un argumento de entrada, la matriz de coeficientes del sistema, A , calcula las matrices D, L y U y el radio espectral de la matriz de Jacobi, JB .
-->radioespectralJacobi(A)
re = 0.5911369
d) La sucesión para la que está garantizada la convergencia, cualquiera que sea la semilla ( )0
x es ( ) ( )1
0,1,.....k k
J , k+ = =
Jx B x + c
donde ( )1−JB = D L+U y 1−
Jc = D b . Es decir,
( ) ( ) ( )10,1,.....
k k+ , k
+ = + =-1 -1x D L U x D b
81
Las dos primeras iteraciones utilizando como semilla ( ) ( )00,0,0,0
T=x son:
( ) ( ) ( ) ( ) ( ) ( )1 0 2 1+ += + = +-1 -1 -1 -1x D L U x D b, x D L U x D b
Por tanto,
( )1
0 0.4285714 0.28577143 0.1428571 0 3.5714286 3.5714286
0.25 0 0.125 0.5 0 0.375 0.375
0.3333333 0 0 0.3333333 0 3.3333333 3.3333333
0.1666667 0.3333333 0.3333333 0 0 2.5 2.5
+
− − − − − = = −
x
( )2
0 0.4285714 0.28577143 0.1428571 3.5714286 2.1011905
0.25 0 0.125 0.5 0.375 0.3988095
0.3333333 0 0 0.3333333 3.3333333 2.9761905
0.1666667 0.3333333 0.3333333 0 2.5 0.9186508
− − − − = = −
x
-->x1=BJ*x0+c;
-->x1'
3.5714286 - 0.3750000 3.3333333 2.5000000
-->x2=BJ*x1+c;
-->x2'
2.1011905 0.3988095 2.9761905 0.9186508
e) El número mínimo de iteraciones que debemos realizar para garantizar que
( ) 1010k −
∞− ≤x x*
(es decir, reducir el error en el factor 10-10) siendo x* la solución del sistema viene dado por (25)
( ) 1/
10
10
logk
kN ≥
−J
B
que en función del radio espectral de JB adopta la forma:
( )10
10
logN
ρ≥
−J
B
donde ( ) 0.5911369Jρ =B , por lo que sustituyendo se tiene
10
1043.7997260574620952
log 0.5911369 N ≥ =
−
y como consecuencia N=44.
82
e) La velocidad de convergencia para 5 iteraciones, usando para “medir” JB la
norma infinita, viene dada por
( ) 1/55 5
10logJ JR∞
= −B B
Utilizando SCILAB:
-->-log10(norm(BJ^5,"inf")^(1/5))
0.1808636
Resulta que la velocidad de convergencia para 5 iteraciones es
( )5 0.1808636 R =B
f) Por su parte, la velocidad de convergencia asintótica viene dada por
( )10 10
1 1log log 0.2283119
0.5911369ρ = = J
B
Como puede observarse, la velocidad de convergencia para 5 iteraciones no está muy próxima a la velocidad de convergencia asintótica.
Para un número alto de iteraciones, tal como 500, se obtiene una velocidad de convergencia muy similar a la velocidad de convergencia asintótica:
-->-log10(norm(BJ^500,"inf")^(1/500))
0.2278488
( ) ( )1/500
500 500
10 100.22781
488log log 0.2283119J J
J
Rρ∞
= − = ≈ =
B BB
i) Con respecto a encontrar la solución “optima” del sistema creemos conveniente recoger la siguiente cita, que pertenece al área de sistemas electromagnéticos:
“Hace ya más de 200 años, Leonard Euler, de quien dicen que jamás
dejaba de calcular, decidió abordar el problema del flujo del agua. El conocía
las ecuaciones de Newton, y sabía cómo aplicarlas a partículas o sólidos
rígidos.
En estos casos, el estado del sistema físico esta descrito por un número
finito de cantidades: las posiciones y las velocidades de las partículas, o la
posición y velocidad del centro de masas junto con la orientación del cuerpo y
su velocidad angular. No así con el agua: para definir su estado se necesita
saber la velocidad de cada partícula.
Matemáticamente, su estado se puede representar mediante el campo de
velocidades v(x, y, z). Euler logró derivar una ecuación que relacionaba el
cambio de la velocidad con el tiempo con su cambio en el espacio, una ecuación
en derivadas parciales, o una ecuación de campo.
83
100 años después, James Maxwell logró dar forma matemática a las ideas
de Michel Farady sobre las leyes del campo electromagnético. De nuevo se
encontró con ecuaciones en derivadas parciales, que en teoría permitirían
calcular los campos eléctrico E(x, y, z) y magnético B(x, y, z).
Este fue, sin duda alguna, el hecho más importante del siglo XIX, el
comienzo de la era eléctrica. Durante los años siguientes, el final del siglo XIX
y el siglo XX, los ingenieros aplicarían estas ecuaciones en un número
creciente de dispositivos.
Sin embargo, es curioso de que, salvo en raras ocasiones, no las resolvían,
las simplificaban. La razón, por supuesto, es que no se sabía resolverlas, salvo
en casos de una extrema idealización.
Hoy la situación es distinta. La razón es que la aparición de los
ordenadores (Lejanos descendientes de Farady y Maxwell, por otra parte)
permiten la resolución de grandes sistemas de ecuaciones algebraicas”.
Sin necesidad de ninguna aclaración adicional, hemos de reconocer que es el ordenador el gran aliado de la resolución de sistemas de ecuaciones algebraicas y en general de la resolución de los grandes problemas de cálculo que la actual y apasionante ingeniería conlleva.
Ya hemos utilizado sentencias y funciones de SCILAB para cálculos complejos referidos a distintos aspectos de la resolución de ecuaciones lineales. Pero nos pareció adecuado resaltar la importancia de los ordenadores en un ejemplo, (sencillo e ideal, pues cuatro variables no es precisamente lo habitual en los problemas reales de la ingeniería actual), de uno de los métodos iterativos de resolución de sistemas de ecuaciones lineales más populares, el método de Jacobi.
Para obtener la solución del sistema propuesto utilizaremos la función x=Jacobi(A, b, x0, tol, maxit) con un parámetro de salida, el vector solución, x, y cinco parámetros de entrada (matriz de coeficientes del sistema, A, vector de términos independientes, b, vector semilla, x0, tolerancia de la distancia entre dos aproximaciones consecutivas a la solución, tol y el número máximo de iteraciones aceptadas, maxit.
La función se proporciona al alumno, al igual que todas las utilizadas en este curso, en anexos que se irán añadiendo en los recursos de la asignatura en Moodle, dentro del tema correspondiente.
-->A=[7,-3,2,1;-2,-8,1,4;1,0,3,-1;1,2,2,6]
-->b=[25;3;10;15]
-->eps=1.0e-10
-->x0=zeros(4,1)
--->tic()
-->x=Jacobi(A,b,x0,10e-10,1000) -->tiempo_proceso=toc()
84
Salida
Se alcanzó la tolerancia con éxito en la iteración 43 y la solución aproximada es x =
2.5540641
- 0.0820283
2.8642804
1.1469053
Tiempo_proceso: 0.608 segundos.
k x(k)=(x1(k), x2(k), x3(k), x4(k)) εk
0 0.0000000 0.0000000 0.0000000 0.0000000
1 3.5714286 - 0.3750000 3.3333333 2.5000000 0.9999999998182
2 2.1011905 0.3988095 2.9761905 0.9186508 0.6143834112542
3 5.7012472 - 1.6165675 3.6534392 4.1875 0.1961904400758
4 5.9062972 - 1.5001181 3.8379157 4.1291651 0.0779112767835
5 5.9007644 - 1.4427477 3.9257107 4.2636487 0.0425493540094
6 5.9204733 - 1.5223471 3.8790386 4.3111151 0.0263051489880
7 5.9480334 - 1.535319 3.8697861 4.2723094 0.0125009960704
8 5.9454055 - 1.5078696 3.891908 4.2694946 0.0088609340556
9 5.9395599 - 1.5098844 3.8919703 4.2855804 0.0043048825855
10 5.9427392 - 1.5193965 3.8846598 4.2839553 0.0031240082302
11 2.553398 -0.078831 2.866744 1.146796 0.0015339140564
⋮ ⋮ ⋮ 25 2.554064 -0.082027 2.864282 1.146904 0.0000009818560
⋮ ⋮ ⋮ 32 2.554064 -0.082028 2.864280 1.146905 0.0000000267198
⋮ ⋮ ⋮
42 2.554064 -0.082028 2.864280 1.146905 0.0000000001462
43 2.5540641 - 0.0820283 2.8642804 1.1469053 0.0000000000769
( ) ( )
( )
1
2
10
2
k k
k k
x x
x eε
−
−
−=
+. Se suma 1.
10e− en el denominador para evitar que sea cero.
Procedemos ahora a calcular el residuo, diferencia entre A*x (con la solución aproximada y el vector de términos independientes b).
-->A*x-b
- 0.00000000015212720
- 0.00000000134284139
0.00000000037889158
- 0.00000000022958524
--> norm(A*x-b) (norma euclídea, también puede ponerse norm(A*x-b,2) ).
0.00000000142219334
85
El método de Jacobi puede usarse para resolver algunos sistemas de ecuaciones lineales, pero no siempre funciona bien y las iteraciones en lugar de acercarse a la solución se alejan. Por ejemplo, si en el sistema:
1 2 3
1 2 3
1 2 3
4 7
4 8 8 21
2 5 15
x x x
x x x
x x x
− + = − − = −− + + =
con solución ( )2,4,3T=x , se reordenan las ecuaciones de otra forma
1 2 3
1 2 3
1 2 3
2 5 15
4 8 8 21
4 7
x x x
x x x
x x x
− + + = − − = − − + =
entonces el método de Jacobi proporciona una sucesión divergente:
2 31
1 32
3 1 2
15 5
4
21 4
8
7 4
x xx
x xx
x x x
− + +=
+ +=
= − +
⇒
( ) ( )( 1) 2 31
( ) ( )( 1) 1 32
( 1) ( ) ( )
3 1 2
15 5
4
21 4
8
7 4
k kk
k kk
k k k
x xx
x xx
x x x
+
+
+
− + +=
+ +=
= − +
Si comenzamos con ( ) ( )01,2,2
T=x entonces el proceso recurrente anterior da
lugar en la 1ª iteración al punto ( ) ( )11.50, 3.375, 3.00
T
= −x que está más alejada
de la solución que el punto ( )0x .
k x1(k) x2(k) x3(k) 0 1.00 2.00 2.00
1 -1.5 3.375 5.00
2 6.6875 2.500 16.375
3 34.6875 8.015625 -17.250
4 -46.617188 17.812500 -123.73438
5 -307.929688 -36.150391 211.28125
6 502.627930 -124.929688 1202.56836
86
3.2 Método de Gauss-Seidel.
Algunas veces se puede acelerar la convergencia del método iterativo de Jacobi utilizando en el paso 1k + los valores obtenidos de las incógnitas anteriores en el mismo paso, por ejemplo en (27):
(31)
( )( ) ( )
( )( ) ( )
( )( ) ( )
1
1
1 2 31
1 1 32
1 1 23
1
7
4
21 4
8
15 2
5
k kk
kk
kk
k
k
x xx
x xx
x xx
+
+
+
+
++
+ −=
+ +=
+ −=
Ecuaciones que se pueden expresar formalmente para el caso general en la forma siguiente:
( )( ) ( ) ( ) ( )
( ) ( )1
1
1 1 1
1 1
1 1 , 1 1 , 1 1
(32)
...
1,.
.
..,
..
i nk k
ij j ij j
k j j iii
ii ii
k k k k
i i i i i i i i in n
ii
b a x a x a x aa x a x
bx
a a
i
x
a
n
+ +− − +
−+
+ = = ++− − − − − −=
+−=
=
∑ ∑
A través de esta fórmula se obtienen las siguientes aproximaciones como combinación lineal de los puntos recurrentes previamente obtenidos.
Normalmente el método de Gauss-Seidel converge más rápidamente que el
de Jacobi, si bien hay algunas excepciones.
k x1(k) x2(k) x3(k) 0 1.00000000 2.00000000 2.000000000
1 1.75000000 3.75000000 .950000000
2 1.95000000 3.96875000 2.986250000
⋮ ⋮ ⋮ ⋮ 8 1.99999983 3.99999988 2.999999996
9 1.99999998 3.99999999 3.000000000
10 2.00000000 4.00000000 3.000000000
En este caso la matriz y vector del método se obtienen en la forma siguiente:
Sea el sistema de ecuaciones lineales =Ax b , para , yD L U definidos como en el apartado anterior, =A D - L -U . De =Ax b resulta
( )D - L -U x = b
y, por tanto, ( )D - L x = Ux+ b
de donde
( ) ( ) ( ) ( ) ( ) ( )1 1 1 1 1− − − − −⇔D - L D - L x = D - L Ux + D - L b x = D - L Ux + D - L b
El sistema
( ) ( )( 1) (1 1( ) )kk k
GS GS
+ − − += D - L Ux + D B xL b = c-x
87
es un sistema triangular inferior en cada paso, que se resuelve por sustitución progresiva. Por tanto, el valor de cada incógnita en cada paso k del método es
( )
( ) ( )1
1
1 1 1, 1,...,
i nk k
ij j ij j
k j j iii
ii ii
a x a xb
x i na a
−+
+ = = +
+= − =
∑ ∑
La matriz y el vector del método son respectivamente ( ) 1
GS
−=B D - L U y
( ) 1
GS
−=c D - L b .
En la práctica el método se aplica de acuerdo con el siguiente algoritmo de Gauss-Seidel:
1.- Se parte de una solución semilla arbitraria ( ) ( ) ( ) ( )( )0 0 0 0
1 , ..., ...,i n=x x x x .
2.- Se calcula ( ) ( ) ( ) ( )( )1 1 1 1
1 ,..., ...,k k k k
i n
+ + + +=x x x x , para 0k ≥ iterando con la
fórmula
( )
( ) ( )1
1
1 1 1, 1,...,
i nk k
i ij j ij j
k j j i
i
ii
b a x a x
x i na
−+
+ = = +
− −= =
∑ ∑
3. Una vez fijado el valor semilla, paso 1, el proceso se realiza consecutivamente para 0k ≥ , paso 2, hasta que se cumplan los mismos criterios que para el algoritmo de Jacobi. Las normas usuales en los criterios de paro de Gauss-Seidel son también 1ℓℓℓℓ , 2ℓℓℓℓ y ∞ℓℓℓℓ .
Por ejemplo, si
( )kAx btol
b
∞
∞
−≤ entonces stop, y por tanto la solución es
( ) ( ) ( ) ( )( )1 1 1 1
1 ,..., ...,k k k k
i n
+ + + +=x x x x .
Definición. 1.14 (Matriz de diagonal estrictamente dominante por filas o
por columnas). a) Una matriz A, de orden nxn, se dice de diagonal estrictamente dominante por filas cuando
(33) 1 , 1 , 1... ... , 1,...,ii i i i i i ina a a a a i n− +> + + + + + =
Es decir, el valor absoluto de cada elemento de la matriz diagonal es mayor que la suma de los valores absolutos del resto de elementos de la fila correspondiente.
b) Análogamente, una matriz A, de orden nxn, se dice de diagonal estrictamente dominante por columnas cuando, para cada columna, el valor absoluto del elemento de la diagonal de esa columna es estrictamente mayor que la suma de los valores absolutos del resto de elementos de esa misma columna.
88
Definición. 1.13 En álgebra lineal, una matriz es de diagonal estrictamente
dominante, cuando lo es por filas o por columnas.
Teorema. 1.5 (Convergencia de los métodos iterativos de Jacobi y
Gauss-Seidel). Si la matriz de coeficientes del sistema de ecuaciones lineales =Ax b es de diagonal estrictamente dominante entonces los métodos de Jacobi y
Gauss-Seidel convergen a la única solución de =Ax b cualquiera que sea el vector
semilla de partida ( )0 n∈ℝx .
Detrás de este teorema de convergencia para ambos métodos se esconden los criterios de la diagonal pesada, latentes en todo método susceptible de los efectos del pivote:
1.- Condición necesaria: Que el valor absoluto de cada elemento de la matriz diagonal es mayor que los valores absolutos del resto de elementos de la fila correspondiente.
(34) 1 , 1 , 1,..., , ,..., , 1,...,ii i i i i i ina a a a a i n− +> =
2.- Condición suficiente: La matriz de coeficientes del sistema de ecuaciones
lineales =Ax b es de diagonal estrictamente dominante.
Notemos que en el método iterativo de Jacobi se utilizan las coordenadas del punto anterior para obtener las del nuevo punto, mientras que en el método iterativo de Gauss-Seidel para obtener el nuevo punto se emplean las coordenadas nuevas ya generadas y las del punto anterior para las aún no generadas.
Ejercicio. 1.17 Dado el sistema de ecuaciones lineales del ejercicio 1.16.
a) Calcular las matrices que definen la fórmula de recurrencia o iteración de Gaus-Seidel.
b) Si se construye la sucesión de vectores que define el método de Gauss-Seidel a partir de un vector inicial cualquiera, ¿se puede garantizar la convergencia de esta sucesión a la solución del sistema?, razonar la respuesta.
c) Para la sucesión en la que se tiene garantizada la convergencia a la
solución del sistema, calcular la primera y la segunda iteración utilizando como vector de inicialización el vector nulo.
d) Calcular el mínimo número de iteraciones k que debemos realizar para garantizar que
( ) 1010k −
∞− ≤x x*
siendo x* la solución del sistema.
e) Calcular la velocidad de convergencia para 5 y 48 y iteraciones.
89
f) Calcular la velocidad de convergencia asintótica y la velocidad de convergencia para k=500. Explicar los resultados obtenidos.
g) Calcular la solución utilizando la función x=GaussSeidel(A, b, x0, tol, maxit) que se proporciona, calcular también el residuo y su “medida” utilizando la norma infinito.
Solución.
a) La matriz y vector que definen la fórmula de recurrencia o iteración de Gaus-Seidel se obtienen también a partir de la descomposición =A D - L -U . Las matrices D=(Diag(A), L=-1*(tril(A)-D) y U=-1*(triu(A)-D) fueron calculadas en el apartado b) del ejercicio 1.16. Operando matricialmente según las igualdades siguientes:
( ) ( )1 1
GS GS
− −= =B D - L U, c D - L b
Se tiene
( )
7 0 0 0 0 0 0 0 0 3 2 1
0 8 0 0 2 0 0 0 0 0 1 4*
0 0 3 0 1 0 0 0 0 0 0 1
0 0 0 6 1 2 2 0 0 0 0 0
0.14285714 0. 0. 0.
GS
− − − − − = − − − − −
=
-1B = D - L U -
- 0.03571428 - 0.125 0. 0.
- 0.04761904 0. 0.33333333 0.
0.00396825 0.0416666
0 3 2 1
2 0 1 4
1 0 0 1
6 - 0.11111111 0.16666666 1 2 2 0
0. 0.42857142 - 0.28571428 - 0.14285714
0. - 0.10714285 0.19642857 0.53571428
0. - 0.14285714
− − − − − − − − −
= 0.09523809 0.38095238
0. 0.01190476 - 0.04960317 - 0.28174603
Y, por otro lado:
( )
0.14285714 0. 0. 0.
- 0.03571428 - 0.125 0. 0.
- 0.04761904 GS =-1
c = D - L b
25
3
0. 0.33333333 0. 10
0.00396825 0.04166666 - 0.11111111 0.16666666 15
es decir,
3.57142857
- 1.26785714
2.14285714
1.61309523
GS
=
c
90
En SCILAB:
-->BGS=inv(D-L)*U
0. 0.42857142 - 0.28571428 - 0.14285714
0. - 0.10714285 0.19642857 0.53571428
0. - 0.14285714 0.09523809 0.38095238
0. 0.01190476 - 0.04960317 - 0.28174603
-->cGS= inv(D-L)*b
3.57142857
- 1.26785714
2.14285714
1.61309523
b) La convergencia de los métodos iterativos viene caracterizada por los
teoremas, 1.4: que, en síntesis, dice que “para cualquier vector semilla ( )0 n∈ℝx ”,
( ){ } ( )lim 1k
k kρ
→∞ ∈+ = ⇔ <
ℕBx c x B ,
siendo ( )ρ B el radio espectral de la matriz B y 1.5: que dice “si la matriz de
coeficientes del sistema de ecuaciones lineales =Ax b es de diagonal estrictamente dominante entonces los métodos de Jacobi y Gauss-Seidel convergen a la única solución de =Ax b cualquiera que sea el vector semilla de
partida ( )0 n∈ℝx ”.
En el ejemplo 1.16 de aplicación del método de Jacobi analizamos la convergencia del método a través del teorema 1.4. Ahora para la aplicación del método de Gauss-Seidel utilizaremos el teorema 1.5.
Siendo la matriz de los coeficientes
7 3 2 1
2 8 1 4
1 0 3 1
1 2 2 6
− − − =
A
Como puede observarse, se verifica
1 , 1 , 1 4... ... , 1,..., 4ii i i i i i ia a a a a i− +> + + + + + =
7 3 2 1
8 2 1 4
3 1 0 1
6 1 2 2
> − + +
− > − + +
> + +
> + +
91
Por tanto la matriz de los coeficientes del sistema es estrictamente
dominante lo que implica (teorema 1.5) que la sucesión de vectores que define el método de Gauss-Seidel, a partir de un vector inicial cualquiera, converge a la solución del sistema.
c) La sucesión para la que está garantizada la convergencia del método de Gauss-Seidel, cualquiera que sea la semilla ( )0
x es
( ) ( )10,1,.....
k k
GS GS , k+ = =x B x + c
donde ( ) 1−Gs
B = D - L U y ( ) 1−Gs
c = D - L b .
Las dos primeras iteraciones utilizando como semilla ( ) ( )00,0,0,0
T=x son:
( ) ( ) ( ) ( )1 0 2 1
Gs GS Gs GSB +c B +c= =x x , x x
es decir,
( )1
0. 0.42857142 - 0.28571428 - 0.14285714
0. - 0.10714285 0.19642857 0.53571428
0. - 0.14285714 0.09523809 0.38095238
0. 0.01190476 - 0.04960317 - 0.28174603
=
x
0 3.57142857 3.57142857
0 - 1.26785714 - 1.26785714
0 2.14285714 2.14285714
0 1.61309523 1.61309523
+
=
( )2
0. 0.42857142 - 0.28571428 - 0.14285714
0. - 0.10714285 0.19642857 0.53571428
0. - 0.14285714 0.09523809 0.38095238
0. 0.01190476 - 0.04960317 - 0.28174603
=
x
3.57142857 3.57142857 3.5714286
- 1.26785714 - 1.26785714 0.375
2.14285714 2.14285714 3.3333333
1.61309523 1.61309523 2.5
+
− =
-->x1=BGS*x0+cGS;
-->x1'
3.57142857 - 1.26785714 2.14285714 1.61309523
-->x2=BGS*x1+cGS;
-->x2'
2.18537414 0.15306122 3.14257369 1.03722600
d) El número mínimo de iteraciones que debemos realizar para garantizar que
( ) 1010k −
∞− ≤x x*
(es decir, reducir el error en el factor 10-10) siendo x* la solución del sistema viene dado por (25)
( ) 1/
10
10
logk
kN ≥
−GS
B
que en función del radio espectral de GSB adopta la forma:
92
( )10
10
logN
ρ≥
−GS
B
El radio espectral es,
( ) { }1
/ .i ii n
máx es un autovalor deρ λ λ≤ ≤
=GS GSB B
y se obtiene en SCILAB a través de la sentencia
->re=max(abs(spec(BGS)))
0.19933987
( ) ( ) ( )10 10
10 10 0.19933987 14.27743694
log log 0.19933987GSρ
ρ= ⇒ = =
− −GS
BB
Por tanto, la covergencia se alcanzará en un número de iteraciones mayor de N=15.
Notas: a) Observese que ( ) 0.19933987 1GSρ = <B ⇒ para el sistema lineal
que estamos resolviendo, el método de Gauss-Seidel, converge sea cual sea el vector semilla, lo que confirma lógicamente lo afirmado en el apartado b), aplicando el teorema 1.5.
b) La función radioespectralJacobi , con un argumento de entrada, A , calcula las matrices D, L y U, BGS y el radio espectral de la matriz
del método de Gauss-Seidel, GsB .
g) La velocidad de convergencia para 5 iteraciones, usando para “medir” B la norma infinita, viene dada por
( ) 1/55 5
10logGS GSR∞
= −B B
Utilizando SCILAB:
-->BGS^5
0. - 0.00001413679806428 0.00002501683878442 - 0.00030093463744009
0. 0.00002645771727568 0.00006923023514096 0.00065271859417640
0. 0.00007519703075867 0.00007992356091628 0.00091101859056091
0. - 0.00003152878300074 - 0.00005388740514982 - 0.00047108995533909
-->norm(BGS^ 5,"inf")
0.00106613
-->-log10(norm(BGS^5,"inf")^(1/5))
0.59443721
Resulta que la velocidad de convergencia para 5 iteraciones es
( )5 0.59443721 R =B
93
h) La velocidad de convergencia asintótica viene dada por
( )10 10
1 1log log 0.70040582
0.59443721ρ = = BS
B
Como puede observarse, la velocidad de convergencia para 5 iteraciones no está muy próxima a la velocidad de convergencia asintótica.
Para 12 iteraciones se tiene
-->-log10(norm(BGS^12,"inf")^(1/12))
0.65306251
Se observa que la velocidad de convergencia mejorado bastante.
Para un número “alto” de iteraciones, 300, se obtiene una velocidad de convergencia muy similar a la velocidad de convergencia asintótica:
-->-log10(norm(BGS^300,"inf")^(1/300))
0.69851008
( ) ( )1/300
300 300
10 100.69851
1008 0.7004log log 0582GS GS
GS
Rρ∞
= − = ≈ =
B BB
i) Para obtener la solución del sistema propuesto utilizaremos la función x=GaussSeidel(A, b, x0, tol, maxit) con un parámetro de salida, el vector solución, x, y cinco parámetros de entrada (matriz de coeficientes del sistema, A, vector de términos independientes, b, vector semilla, x0, tolerancia de la distancia entre dos aproximaciones consecutivas a la solución, tol y el número máximo de iteraciones aceptadas, maxit.
-->A=[7,-3,2,1;-2,-8,1,4;1,0,3,-1;1,2,2,6]
-->b=[25;3;10;15]
-->eps=1.0e-10
-->x0=zeros(4,1)
-->tic() -->x=GaussSeidel(A,b,x0,10e-10,1000) -->tiempo_proceso=toc()
Salida de x=GaussSeidel(A, b, x0, tol, maxit)
Se alcanzó la tolerancia con éxito en la iteración 15; la solución aproximada es x =
2.5540641, - 0.0820283, 2.8642804, 1.1469053
tiempo_proceso = 0.249 segundos.
94
k x(k)=(x1(k), x2(k), x3(k), x4(k)) εk
1 3.571429 -1.267857 2.142857 1.613095 0.9999999997846
2 2.185374 0.153061 3.142574 1.037226 0.5784991454114
3 2.590973 -0.111309 2.815418 1.166801 0.1495660012189
4 2.552634 -0.077831 2.871389 1.143375 0.0197536665124
5 2.554336 -0.082973 2.863013 1.147597 0.0027042368279
6 2.553923 -0.081805 2.864558 1.146762 0.0005365921893
7 2.554101 -0.082074 2.864220 1.146935 0.0001243378131
8 2.554057 -0.082020 2.864292 1.146899 0.0000265598558
9 2.554065 -0.082030 2.864278 1.146906 0.0000051699658
10 2.554064 -0.082028 2.864281 1.146905 0.0000009929444
11 2.554064 -0.082028 2.864280 1.146905 0.0000001961992
12 2.554064 -0.082028 2.864280 1.146905 0.0000000394995
13 2.554064 -0.082028 2.864280 1.146905 0.0000000079369
14 2.554064 -0.082028 2.864280 1.146905 0.0000000015822
15 2.554064 -0.082028 2.864280 1.146905 0.0000000003145
εk =( ) ( )
( )
1
2
10
2
k k
k
x x
x e
−
−
−
+. Se suma
10e−en el denominador para evitar que sea cero).
Procedemos ahora a calcular el residuo, diferencia entre A*x(15) (con la solución aproximada x(15)) y el vector de términos independientes b.
-->A*x-b
0.00000000063199934
0.00000000085663920
- 0.00000000043336357
0.
--> norm(A*x-b) (norma euclídea, también puede ponerse norm(A*x-b,2) ).
0.00000000114937282
95
3.3 Métodos de Relajación.
Si para un sistema determinado, =Ax b , el método de Gauss-Seidel converge, entonces ha de verificarse, en general, que cada aproximación de cada incógnita
( 1)k
ix + estará más cerca de la solución que ( )k
ix ), para i = 1···n.
El método de relajación se basa en la idea de que el proceso de convergencia puede acelerarse ponderando la diferencia entre los valores ( 1)k
ix + y ( )k
ix ), para cada i = 1···n , es decir,
( 1) ( ) , 1,..., .k k
i i ix x d i nω+ = + =
donde ( 1) ( )ˆ k k
i i id x x+= − (denotamos por ( )k
ix la aproximación obtenida por el
método de relajación y por ( 1)ˆ k
ix + la que obtendríamos aplicando Gauss-Seidel)
Sustituyendo y operando:
( ) ( )( 1) ( ) ( ) ( 1) ( ) ( ) ( 1)ˆ ˆ1 , 1,...,k k k k k k k
i i i i i i i ix x d x x x x x para cada i nω ω ω ω+ + += + = + − = − + =
El proceso consiste, en consecuencia, en hallar cada iteración de Gauss-Seidel
y ponderarla con el ω elegido. La secuencia de pasos es la siguiente:
Primer paso: partiendo de la estimación inicial (0)
nx ) obtenemos la primera iteración
de Gauss-Seidel y la designamos
( )(1) (1) (1) (1)
1 2ˆ ˆ ˆ ˆ, ,..., nx x x x=
A continuación, hallamos la primera iteración de relajación según la fórmula de dicho método
( )( )
( )
(1) (0) (1)
1 1 1
(1) (0) (1)
2 2 2
(1) (0) (1)
ˆ1
ˆ1
.....................................
ˆ1n n n
x x x
x x x
x x x
ω ωω ω
ω ω
= − + = − + = − +
Segundo paso: con esta aproximación obtenida ( )(1) (1) (1) (1)
1 2, ,..., nx x x x= se
calcula la segunda iteración con Gauss-Seidel y la denotamos
( )(2) (2) (2) (2)
1 2ˆ ˆ ˆ ˆ, ,..., nx x x x=
y aplicamos la fórmula de relajación para obtener la segunda iteración
( )(2) (2) (2) (2)
1 2, ,..., nx x x x=
( )( )
( )
(2) (1) (2)
1 1 1
(2) (1) (2)
2 2 2
(2) (1) (2)
ˆ1
ˆ1
.....................................
ˆ1n n n
x x x
x x x
x x x
ω ωω ω
ω ω
= − + = − + = − +
96
y así sucesivamente.
En general
(35)
( )( )
( )
( 1) ( ) ( 1)
1 1 1
( 1) ( ) ( 1)
2 2 2
( 1) ( ) ( 1)
ˆ1
ˆ1
.....................................
ˆ1
k k k
k k k
k k k
n n n
x x x
x x x
x x x
ω ωω ω
ω ω
+ +
+ +
+ +
= − + = − + = − +
cuyo desarrollo completo es
( )
( )
( ) ( ) ( )( 1) ( ) 1 12 2 13 3 11 1
11
( ) ( )( 1) ( )
(
2 23 3 22 2
)
21 1
22
...1
...1
...............................................................................
ˆ
k k kk k n n
k kk k n n
k
b a x a x a xx x
a
b a xa ax x
x x
a
ω ω
ω ω
+
+
− − − −= − +
− − − −= − +
( )(
( 1)
) ( ) ( )
1 1 2 2 , 1 1( )
...............
.ˆ ..1
ˆ ˆk k k
n n n n n
nn
nk k
n n
bx x
a x a x a x
aω ω+ − − − − − −
= − +
La ecuación matricial del método se obtiene a partir de la ecuación de relajación (35)
(36) ( )( 1) ( ) ( 1)ˆ1k k kx x xω ω+ += − +
La solución ( 1)ˆ kx + del método se obtiene al despejar ( 1)kx + en la ecuación
( ) ( 1) ( )k k+D - L x =Ux + b
( ) ( )1 1( 1) ( )ˆ k k− −+x = D - L Ux + D - L b
Operando:
( ) ( ) ( )( )( ) ( )( ) ( )
1 1( ) ( )( 1)
1 1( )1
1 k kk
k
x
ω ω
ω ω
ω
− −+
− −−
= − +
+= +
x D - L Ux + D - L
I D - L U x D - L
b
b
De donde la matriz y el vector del método de relajación son respectivamente
( ) ( ) 11rB ω ω −= − +I D - L U y ( ) 1
r ω −=c D - L b .
En la práctica el método se aplica de acuerdo con el siguiente algoritmo de relajación:
1.- Se parte de una solución semilla arbitraria ( ) ( ) ( ) ( )( )0 0 0 0
1 , ..., ...,i n=x x x x .
2.- Se calcula ( ) ( ) ( ) ( )( )1 1 1 1
1 ,..., ...,k k k k
i n
+ + + +=x x x x , para 0k ≥ iterando con la
fórmula
97
( ) ( ) ( )
( ) ( )1
1
1 1 11 , 1,..., 0.
i nk k
i ij j ij j
k k j j i
i i
ii
b a x a x
x x i n ya
ω ω ω
−+
+ = = +
− − = − + = ≥
∑ ∑
3. Una vez fijado el valor semilla, paso 1, el proceso se realiza consecutivamente para 0k ≥ , paso 2, hasta que se cumplan los mismos criterios que para los algoritmos de Jacobi y Gauss-Seidel. Las normas usuales en los criterios de parada del método de relajación son también 1ℓℓℓℓ , 2ℓℓℓℓ y ∞ℓℓℓℓ .
Por ejemplo, si
( )
1
1
kAx btol
b
−≤ entonces stop, y por tanto la solución es
( ) ( ) ( ) ( )( )1 1 1 1
1 ,..., ...,k k k k
i n
+ + + +=x x x x .
Teorema. 1.6 (Convergencia de los métodos de relajación). Los métodos de relajación pueden converger sólo si 0 2ω< < .
OBSERVACIONES: Las elecciones de 1 2ω< < dan lugar a los métodos
denominados de sobre-relajación y sirven para acelerar la convergencia de sistemas que son convergentes con el método de Gauss-Seidel ( 1ω = ).
Los métodos que surgen al tomar las elecciones de 0 1ω< < se denominan
métodos de sub-relajación y pueden servir para obtener la convergencia para algunos sistemas para los que el método de Gauss-Seidel no converge.
Esquema del algoritmo de relajación.
(Se supone que no hay elementos diagonales nulos).
datos: A, b, ω, x0, tol, maxit x = x0 para k = 1, ...,maxit difx = 0 para i = 1, ..., n ri = bi – A(i,:) x δi = ri/aii
xi = xi + ωδi difx = max{difx, |ωδi|} fin-para i
si difx ≤ tol ent x∗ ≈ x, salir fin-para k
Como puede verse el esquema es muy es muy parecido al de Gauss-Seidel.
El método de relajación es muy útil para “sistemas sparse”.
98
Ejercicio. 1.18 Dado el sistema de ecuaciones lineales del ejercicio 1.16.
a) Calcular las matrices que definen la fórmula de recurrencia o iteración de relajación para una constante de relajación ω=1.4.
b) Si se construye la sucesión de vectores que define el método de relajación a partir de un vector inicial cualquiera, ¿se puede garantizar la convergencia de esta sucesión a la solución del sistema?, razonar la respuesta.
c) Para la sucesión en la que se tiene garantizada la convergencia a la
solución del sistema, calcular la primera y la segunda iteración utilizando como vector de inicialización el vector nulo.
d) Calcular el mínimo número de iteraciones k que debemos realizar para garantizar que
( ) 1010k −
∞− ≤x x*
siendo x* la solución del sistema.
e) Calcular la velocidad de convergencia para 15, 30 y 60 y iteraciones. f) Calcular la velocidad de convergencia asintótica y la velocidad de
convergencia para k=500. Explicar los resultados obtenidos.
g) Estimar el error en las iteraciones k=2 y k=60.
h) Calcular la solución utilizando la función x=relajacion(A, b, x0, tol, maxit) que se proporciona, calcular también el residuo y su “medida” utilizando la norma infinito.
Solución.
a) La matriz y vector que definen la fórmula de recurrencia o iteración de relajación se obtienen, del mismo modo que para Jacobi y para Gauss-Seidel, es decir, a partir de la descomposición =A D - L -U . Las matrices D=(Diag(A), L=-1*(tril(A)-D) y U=-1*(triu(A)-D) fueron calculadas en el apartado b) del ejercicio 1.16. Operando matricialmente según las igualdades siguientes:
( ) ( ) 11r ω ω −= − +B I D - L U , ( ) 1
r ω −=c D - L b
Con las matrices ( )= -1
GSB D - L U y ( ) 1
GSc−= D - L b ya calculadas en el ejercicio
1.7), para ω=1.4, se tiene
3.57142857 5.
- 1.26785714 - 1.77499999 1.4 1.4
2.14285714 3.
1.61309523 2.25833333
r GSc
= =
c =
99
1 0 0 0
0 1 0 00.4 1.4 0.4
0 0 1 0
0 0 0 1
0. 0.42857142 - 0.28571428 - 0.14285714
0. - 0.10714285 0.19642857 0.53571428 1.4
0. - 0.14285714 0.09523809 0.38095238
0.
r
= − + = −
GSB I B
+
0.01190476 - 0.04960317 - 0.28174603
- 0.39999999 0.6 - 0.39999999 - 0.19999999
0. - 0.54999999 0.27499999 0.75
0.
=
- 0.19999999 - 0.26666666 0.53333333
0. 0.01666666 - 0.06944444 - 0.79444444
En SCILAB:
-->Br=(1-ω)*eye(4,4)+ ω*inv(D-L)*U
- 0.39999999 0.6 - 0.39999999 - 0.19999999
0. - 0.54999999 0.27499999 0.75
0. - 0.19999999 - 0.26666666 0.53333333
0. 0.01666666 - 0.06944444 - 0.79444444
-->cr=ω* inv(D-L)*b
5.
- 1.77499999
3.
2.25833333
b) La convergencia de todos los métodos iterativos lineales viene
caracterizada por los teoremas, 1.4: “para cualquier vector semilla ( )0 n∈ℝx ”,
( ){ } ( )lim 1k
k kρ
→∞ ∈+ = ⇔ <
ℕBx c x B ,
siendo ( )ρ B el radio espectral de la matriz B y 1.6: para el método de relajación
que dice “los métodos de relajación pueden converger sólo si 0 2ω< < ”.
Hemos fijado el valor de ω en 1.4, por lo que se cumple la condición necesaria, ahora aplicaremos el teorema 1.4 para ver la condición suficiente:
En este caso la matriz del método es ( ) 10.6 1.4
−+I D - L U . Por tanto, el radio
espectral es,
100
( ) { }
1/ .r i i r
i nmáx es un autovalor deρ λ λ
≤ ≤=B B
y se puede obtener en SCILAB a través de la sentencia
->re=max(abs(spec(Br))
0.67907582
( ) 0.67907582 1r reρ = = <B ⇒ (teorema 1.4) que para el sistema lineal que
estamos resolviendo el método de relajación con ω=1.4 es convergente, sea cual sea el vector semilla.
Nota: La función radioespectralrelajacion , con dos argumentos de entrada, la matriz de coeficientes del sistema, A , y ω, calcula las matrices D, L y U, Br y
el radio espectral de la matriz de relajación, rB .
c) La sucesión para la que está garantizada la convergencia del método de relajación con ω=1.4, cualquiera que sea la semilla ( )0
x es
( 1) ( )k k
r
+ = + rx B x c
donde ( ) 10.4 1.4r
−= − +B I D - L U y ( ) 11.4
−r
c = D - L b .
Las dos primeras iteraciones utilizando como semilla ( ) ( )00,0,0,0
T=x son:
( ) ( ) ( ) ( )1 0 2 1
r r r rB +c B +c= =x x , x x
Es decir,
( )1
- 0.39999999 0.6 - 0.39999999 - 0.19999999
0. - 0.54999999 0.27499999 0.75
0. - 0.19999999 - 0.26666666 0.533333=x
0
0
33 0
0. 0.01666666 - 0.06944444 - 0.79444444 0
5. 5.
- 1.77499999
3.
2.25833333
+
=
- 1.77499999
3.
2.25833333
( )2
- 0.39999999 0.6 - 0.39999999 - 0.19999999
0. - 0.54999999 0.27499999 0.75
0. - 0.19999999 - 0.26666666 0.533333=x
5.
- 1.77499999
33 3.
0. 0.01666666 - 0.06944444 - 0.79444444 2.25833333
5.
- 1.7+
0.28333333
7499999 1.71999999
3. 3.75944444
2.25833333 0.22629629
=
101
-->x1=Br*x0+cr;
-->x1'
5. - 1.77499999 3. 2.25833333
-->x2=Br*x1+cr;
-->x2'
0.28333333 1.71999999 3.75944444 0.22629629
d) El número mínimo de iteraciones que debemos realizar para garantizar que
( ) 1010k −
∞− ≤x x*
(es decir, reducir el error en el factor 10-10) siendo x* la solución del sistema viene dado por (25)
( ) 1/
10
10
logk
kN ≥
−r
B
que en función del radio espectral de rB adopta la forma:
( )10
10
logN
ρ≥
−r
B
En el apartado b) calculamos el radio espectral ( ) 0.67907582rρ =B , y, por
tanto,
( ) ( )10 10
10 10 59.49486482
log log 0.67907582ρ= =
− −r
B
Por tanto, la convergencia se alcanzará en un número de iteraciones mayor a 59.
e) La velocidad de convergencia para 15 iteraciones, usando para “medir”
rB la norma infinita, viene dada por
( ) 1/1515 15
10logr rR∞
= −B B
Utilizando SCILAB:
-->-log10(norm(Br^15,"inf")^(1/15))
resulta ( )15 0.130121563 rR =B
f) Por otra parte, la velocidad de convergencia asintótica viene dada por
( )10 10
1 1log log 0.16808173
0.67907582ρ = = r
B
Como puede observarse, la velocidad de convergencia para 15 iteraciones no está “muy próxima” a la velocidad de convergencia asintótica.
Para 30 iteraciones se tiene:
102
-->-log10(norm(Br^30,"inf")^(1/30))
( )30 0.14912312 rR =B , que ya se aproxima más a la velocidad de conver-
gencia asintótica.
Para un número alto de iteraciones, como el caso de k=500, se obtiene una velocidad de convergencia muy similar a la velocidad de convergencia asintótica:
-->-log10(norm(Br^500,"inf")^(1/500))
( ) ( )1/500
300 500
10 100.16691
4429 0.1680log log 8173r GS
r
Rρ∞
= − = ≈ =
B BB
g) Para obtener la solución del sistema propuesto utilizaremos la función x=relajación(A, b, w, x0, tol, maxit) con un parámetro de salida, el vector solución, x, y seis parámetros de entrada (matriz de coeficientes del sistema, A, vector de términos independientes, b, vector semilla, x0, tolerancia de la distancia entre dos aproximaciones consecutivas a la solución, tol y el número máximo de iteraciones aceptadas, maxit.
-->A=[7,-3,2,1;-2,-8,1,4;1,0,3,-1;1,2,2,6]
-->b=[25;3;10;15]
-->eps=1.0e-10
-->w=1.4
-->x0=zeros(4,1)
-->tol=1.e-10
-->maxit=1000
-->tic()
-->x=relajacion(A,b,w,x0,1.tol,maxit)
-->tiempo_proceso=toc()
Salida x=relajación(A, b, w, x0, tol, maxit)
Se alcanzó la tolerancia con éxito en la iteración 64, con
( ) ( )
( )
64 63
10264 63 10
2
0.0000000000725<1.e
x x
x eε −
−=
−=
+ . La solución aproximada es
2.55406413
- 0.08202833
2.86428038
1.14690529
x =
tiempo_proceso = 0.983 segundos.
103
k x(k)=(x1(k), x2(k), x3(k), x4(k)) εk
1 5.000000 -1.775000 3.000000 2.258333 0.9999999998462
2 0.283333 1.720000 3.759444 0.226296 1.5080190553257
3 4.369630 -1.517431 1.774173 1.846148 1.0987279857997
4 1.262791 0.932095 3.814985 0.643175 1.1044992333825
5 3.399511 -0.756150 2.139278 1.497972 0.7603315491281
6 2.031200 0.352663 3.379674 0.907114 0.5499803725478
7 2.865826 -0.359219 2.512015 1.308860 0.3597166125648
8 2.371561 0.095019 3.100032 1.038085 0.2308407662417
9 2.660758 -0.196188 2.707966 1.219936 0.1492840296237
10 2.490810 -0.007453 2.967746 1.097839 0.0951746374421
11 2.592538 -0.131392 2.795606 1.179944 0.0623960877693
12 2.529919 -0.048985 2.910087 1.124604 0.0408146955524
13 2.569686 -0.104331 2.833563 1.161992 0.0272754096122
14 2.543704 -0.066894 2.884978 1.136681 0.0182530233367
15 2.561054 -0.092328 2.850281 1.153843 0.0123562305808
16 2.549300 -0.075010 2.873773 1.142195 0.0083698557351
17 2.557325 -0.086811 2.857833 1.150105 0.0056960627353
18 2.551829 -0.078771 2.868663 1.144731 0.0038742834847
19 2.555594 -0.084245 2.861301 1.148383 0.0026384537891
20 2.553018 -0.080520 2.866306 1.145902 0.0017950565230
21 2.554778 -0.083053 2.862903 1.147587 0.0012212626245
22 2.553578 -0.081332 2.865216 1.146442 0.0008301922018
23 2.554395 -0.082501 2.863645 1.147220 0.0005642227352
24 2.553840 -0.081707 2.864712 1.146692 0.0003832727361
25 2.554217 -0.082246 2.863987 1.147050 0.0002603187639
26 2.553961 -0.081880 2.864480 1.146807 0.0001767702336
27 2.554134 -0.082129 2.864145 1.146972 0.0001200327921
28 2.554016 -0.081960 2.864372 1.146860 0.0000815013577
29 2.554097 -0.082075 2.864218 1.146936 0.0000553401229
30 2.554042 -0.081997 2.864323 1.146884 0.0000375765274
31 2.554079 -0.082050 2.864252 1.146920 0.0000255156987
32 2.554054 -0.082014 2.864300 1.146896 0.0000173262679
33 2.554071 -0.082038 2.864267 1.146912 0.0000117655610
34 2.554059 -0.082022 2.864289 1.146901 0.0000079895970
35 2.554067 -0.082033 2.864274 1.146908 0.0000054255279
36 2.554062 -0.082025 2.864285 1.146903 0.0000036843495
37 2.554066 -0.082030 2.864278 1.146907 0.0000025019645
38 2.554063 -0.082027 2.864282 1.146904 0.0000016990317
39 2.554065 -0.082029 2.864279 1.146906 0.0000011537769
40 2.554064 -0.082028 2.864281 1.146905 0.0000007835048
41 2.554064 -0.082029 2.864280 1.146906 0.0000005320606
42 2.554064 -0.082028 2.864281 1.146905 0.0000003613101
43 2.554064 -0.082029 2.864280 1.146905 0.0000002453572
44 2.554064 -0.082028 2.864281 1.146905 0.0000001666162
45 2.554064 -0.082028 2.864280 1.146905 0.0000001131450
46 2.554064 -0.082028 2.864280 1.146905 0.0000000768340
47 2.554064 -0.082028 2.864280 1.146905 0.0000000521761
48 2.554064 -0.082028 2.864280 1.146905 0.0000000354315
104
49 2.554064 -0.082028 2.864280 1.146905 0.0000000240607
50 2.554064 -0.082028 2.864280 1.146905 0.0000000163390
51 2.554064 -0.082028 2.864280 1.146905 0.0000000110954
52 2.554064 -0.082028 2.864280 1.146905 0.0000000075346
53 2.554064 -0.082028 2.864280 1.146905 0.0000000051166
54 2.554064 -0.082028 2.864280 1.146905 0.0000000034746
55 2.554064 -0.082028 2.864280 1.146905 0.0000000023595
56 2.554064 -0.082028 2.864280 1.146905 0.0000000016023
57 2.554064 -0.082028 2.864280 1.146905 0.0000000010881
58 2.554064 -0.082028 2.864280 1.146905 0.0000000007389
59 2.554064 -0.082028 2.864280 1.146905 0.0000000005018
60 2.554064 -0.082028 2.864280 1.146905 0.0000000003407
61 2.554064 -0.082028 2.864280 1.146905 0.0000000002314
62 2.554064 -0.082028 2.864280 1.146905 0.0000000001571
63 2.554064 -0.082028 2.864280 1.146905 0.0000000001067
64 2.554064 -0.082028 2.864280 1.146905 0.0000000000725
εk =( ) ( )
( )
1
2
10
2
k k
k
x x
x e
−
−
−
+. Se suma
10e−en el denominador para evitar que sea cero).
A continuación procedemos a calcular el residuo, A*x(64)-b.
-->A*x-b
- 0.00000000035582914
- 0.00000000048070747
0.00000000024302160
0.
--> norm(A*x-b) (norma euclídea).
0.00000000064556452
MÉTODOS DIRECTOS FRENTE A MÉTODOS ITERATIVOS.
Directos Iterativos
(Gauss: simple, pivote parcial, pivote total,
Factorización LU, Mínimos cuadrados) (Jacobi, Gauss-Seidel, Relajación)
=Ax b x=Bx+c
A\b ( ) ( )10
k k, para k
+ = + ≥x Bx c
Tamaño moderado Tamaño grande
Modifican la estructura Conservan los ceros Error de redondeo Error de truncamiento
105
Ejercicio. 1.19 Una partícula se mueve en forma de zigzag a lo largo de cierta trayectoria, se mueve hacia la izquierda con frecuencia triple que a la derecha. Supongamos posiciones numeradas en la trayectoria de 0 a 20, de manera que, partiendo de 0 1x = y 20 0x = , las posiciones a lo largo del tiempo se
obtendrían resolviendo el sistema:
1 1
3 1
4 4k k kx x x− += +
(1) Resolver el sistema utilizando SCILAB.
(2) Aplicar el método iterativo de Jacobi para obtener la solución, analizando previamente la convergencia del método.
(3) Aplicar el método iterativo de Gauss-Seidel para obtener la solución, analizando previamente la convergencia del método.
(4) Experimenta con distintos valores de 20 0x = en el método de relajación
para acelerar la convergencia. Calcular el radio espectral de la matriz del método.
(5) El problema descrito es un problema de frontera para una ecuación en diferencias, cuya solución exacta es:
20
3 11 .
3 1
k
kx
−= −−
Calcular estos valores para 0, 1, 2,..., 20k = y comparar los resultados
con los obtenidos en los apartados anteriores.
Solución: En primer lugar generamos el sistema 1 1
3 1
4 4k k kx x x− += +
en SCILAB. La
siguiente función, para n=20, realiza el cometido:
function [A, b]=ejercicio1_15(n)
//
// Construcción del sistema (Ab) Ax=b.
A(1,1)=1;
A(n,n)=1;
for i=2:n-1
for j=1:n
if i==j
A(i,j)=-1;
elseif i==j-1
A(i,j)=0.25;
elseif i==j+1
A(i,j)=0.75;
end
end
end
b=zeros(n,1);
b(1)=1;
endfunction
106
-->ejercicio1_15(20)
A = 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0.75 - 1. 0.25 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0.75 - 1. 0.25 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0.75 - 1. 0.25 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0.75 - 1. 0.25 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0.75 - 1. 0.25 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0.75 - 1. 0.25 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.75 - 1. 0.25 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0.75 - 1. 0.25 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0.75 - 1. 0.25 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0.75 - 1. 0.25 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.75 - 1. 0.25 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.75 - 1. 0.25
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.75 - 1.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.75
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0.
0.25 0. 0. 0. 0. 0. 0.
- 1. 0.25 0. 0. 0. 0. 0.
0.75 - 1. 0.25 0. 0. 0. 0.
0. 0.75 - 1. 0.25 0. 0. 0.
0. 0. 0.75 - 1. 0.25 0. 0.
0. 0. 0. 0.75 - 1. 0.25 0.
0. 0. 0. 0. 0.75 - 1. 0.25
0. 0. 0. 0. 0. 0. 1.
b = (1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. .0)T
El sistema que se obtiene es:
(1) -->x=inv(A)*b
--> [x,indic]=gauss(A,b,10e-13)
indic = 1.
-->A\b
-->(A'*A)\(A'* b)
-->pinv(A)* b
107
x=inv(A)*b Gauss A\b (A'*A)\(A'* b) pinv(A)* b
x
1.0000000
1.0000000
1.0000000
1.0000000
1.0000000
0.9999999
0.9999998
0.9999994
0.9999981
0.9999944
0.9999831
0.9999492
0.9998476
0.9995428
0.9986283
0.9958848
0.9876543
0.9629630
0.8888889
0.6666667
0. 0000000
1. 0000000
1. 0000000
1.0000000
1.0000000
1.0000000
0.9999999
0.9999998
0.9999994
0.9999981
0.9999944
0.9999831
0.9999492
0.9998476
0.9995428
0.9986283
0.9958848
0.9876543
0.9629630
0.8888889
0.6666667
0. 0000000
1. 0000000
1. 0000000
1.0000000
1.0000000
1.0000000
0.9999999
0.9999998
0.9999994
0.9999981
0.9999944
0.9999831
0.9999492
0.9998476
0.9995428
0.9986283
0.9958848
0.9876543
0.9629630
0.8888889
0.6666667
0. 0000000
1. 0000000
1. 0000000
1.0000000
1.0000000
1.0000000
0.9999999
0.9999998
0.9999994
0.9999981
0.9999944
0.9999831
0.9999492
0.9998476
0.9995428
0.9986283
0.9958848
0.9876543
0.9629630
0.8888889
0.6666667
2.471D-17
1. 0000000
1. 0000000
1.0000000
1.0000000
1.0000000
0.9999999
0.9999998
0.9999994
0.9999981
0.9999944
0.9999831
0.9999492
0.9998476
0.9995428
0.9986283
0.9958848
0.9876543
0.9629630
0.8888889
0.6666667
- 3.745D-16
Tiempo (seg)
2bAx −
Para analizar la convergencia del método de Jacobi, se ha de utilizar una función que calcule el radio espectral de la matriz de Jacobi, tal como la proporcionada function re=radioespectralJacobi(A).
-->radioespectralJacobi(A)
re= 0.8553632
La matriz del método de Jacobi es en este caso es B=-D-1*(L+U). ( )El radio espectral de es max(abs(spec( inv(D)*(L U)))ρ = − +B B .
( ) 0.8553632 1reρ = = <B El método es convergente⇒ (El método es convergente
si ( ) 1Bρ < < 1 ó 1<B ).
A continuación buscamos la solución por el método de Jacobi con semilla el
vector nulo, ( ) ( ) ( ) ( )( ) ( )0 0 0 0
1 ,..., ..., 0,..., 0..., 0i n= =x x x x . Para ello utilizamos la
función: function x=Jacobi(A, b, x0, tol, maxit)
-->x0=Zeros(200,1)
-->Jacobi(x0,10e-10,200)
Se alcanzó la tolerancia con éxito en la iteración 155.000000 y la solución aproximada es
x = 1.0000000
108
1.0000000
1.0000000
1.0000000
1.0000000
0.9999999
0.9999998
0.9999994
0.9999981
0.9999944
0.9999831
0.9999492
0.9998476
0.9995428
0.9986283
0.9958848
0.9876543
0.9629630
0.8888889
0.6666667
0.0000000
(2) Para analizar la convergencia del método, se utiliza la siguiente función que calcula el radio espectral de la matriz de Gauss-Seidel:
function re = radioespectralGaussSeidel
A continuación, para resolver el sistema, se utiliza la siguiente función, que proporciona la aproximación a la solución por el método de Gauss-Seidel cuando se alcanza la tolerancia prefijada:
function x=GaussSeidel(x0,tol,maxit)
bAxx
−mín ( )0 0, ,0=−bAx1
1 11 11
n
ijj n
i
máx máx a= ≤ ≤ =
= = ∑x
A Ax ( )0 0, ,0=−bAx