Download TEMA: ALGEBRA LINEAL NUMERICA

Algebra y Geometría 2009
Tópicos Complementarios
TEMA: ALGEBRA LINEAL NUMERICA
En todo el trayecto de la cursada se han realizado cálculos numéricos:
• se resolvieron sistemas de ecuaciones lineales
• se multiplicaron matrices
• se buscaron bases
• se calcularon valores y vectores propios
• etc,
Todo sobre matrices de 2x2 o 3x3, excepto en algunos casos. Esto no significa que no
haya SEL o matrices de mayor tamaño, para los cuales el cálculo numérico manual
resulta tedioso.
El empleo masivo de calculadoras y computadoras ha permitido trabajar con matrices de
gran tamaño, obteniéndose resultados con mayor rapidez y exactitud.
Al resolver problemas en una computadora surgen dos planteos:
1. ¿Qué tan exactas son las respuestas.
2. ¿Cuánto tiempo requiere la computadora en dar dichas respuestas?.
El uso de estos instrumentos tecnológicos presenta ciertas imprecisiones, ya que las
computadoras no almacenan en forma completa los números con infinitas cifras
2
3
3
7
decimales y los números irracionales, tales como: ;7 ; 2 ; π ; etc.
1. ¿Qué tan exactas son las respuestas?
La mayor parte del trabajo de almacenamiento se realiza mediante la aritmética del
punto flotante:
Cada número se representa como: ± 0, d1 d 2 ....d n 10 m , llamado número de punto flotante;
donde:
• ± 0, d 1 d 2 ....d n 10 m es la mantisa.
• m es el exponente. Este número entero satisface M 1 ≤ m ≤ M 2 .
Los números M1 y M2 dependen de la computadora y del software con los
que se trabaja. Para la aritmética del punto flotante con precisión simple los
valores que se utilizan son M1=39 y M2=47 (en cambio para el Matlab
M1=M2=308 ).
• di son dígitos que satisfacen 1 ≤ d 1 ≤ 9, 0 ≤ d i ≤ 9 y 2 ≤ i ≤ n
• n es número de cifras significativas de la expresión.
Ejemplos:
Π1/4: 0,25
Π2375: 0,2375 104
Π-0,000816: -0,816 10-3
Π83,27: 0,8327 102
1/5
Algebra y Geometría 2009
Tópicos Complementarios
)
7
= 2,3 en la forma de punto flotante, donde N
3
tiene infinitas cifras decimales, sólo dispondremos de n cifras significativas.
Si queremos representar un número N=
Entonces, se debe hacer uso de una aproximación del número por:
a) Truncamiento: se conservan las primeras n cifras significativas, “eliminando”
simplemente las restantes.
)
7
1
ΠSi en particular n = 4, entonces = 2 ,3 = 0 ,2333 x10
3
b) Redondeo: si d k +1 ≥ 5 , entonces se le suma a d k una unidad y se trunca; en
caso contrario solo se trunca.
)
7
ΠPara n = 4, entonces = 2,3 = 0,2333 x101
3
)
2
ΠPara n = 4, entonces = 0,6 = 0,6667 x 10 0
3
Dicha forma de almacenamiento traen aparejado errores de redondeo. Estos errores no
son importantes si analizamos un número u operación aislados, pero no pueden dejar de
ser considerados cuando la computadora realiza miles de cálculos para obtener un
resultado.
Atento a ello es importante tener en cuenta cuál va a ser la acumulación por los errores.
Se definen dos tipos de error:
a)
*
Absoluto: x − x
b)
x* − x
Relativo:
x
Para
Œ x : valor real de un número.
Œ x* : el número que aparece en la computadora.
Ejemplo:
Œx=2
x* = 2,1
Error absoluto: 2 ,1 − 2 = 0 ,1
Πx = 2000
Error relativo:
2,1 − 2
= 0,05
2
x* = 2000,5
Error absoluto: 2000 ,5 − 2000 = 0 ,5
Error relativo:
2000,5 − 2000
= 0,00025
2000
Observamos el siguiente SEL:
2/5
Algebra y Geometría 2009
Tópicos Complementarios
El método de eliminación Gaussiana , puede presentar un problema cuando uno de los
elementos que se usan para hacer ceros, es muy cercano a cero.
Resolvámoslo por este método.
−1


5
3.33335
 0.00005 5 3.33335 R2 → R1  0.00005  + R2  0.00005

 →

1
1 
− 99999 − 66666
 0
 1
Obteniendo el siguiente sistema equivalente:
Siendo:
x2 =
)
2
= 0,6
3
x1 =
3.33335 − 5(x 2 )
0.00005
Recordemos que las operaciones aritméticas de la computadora se asumen que
corresponden a la operación exacta pero truncada al número de cifras significativas de
la máquina, esto se refiere a que el almacenamiento se realiza mediante la aritmética
del punto flotante.
En la siguiente tabla se observa como el resultado cambia drásticamente de acuerdo al
número de cifras significativas consideradas:
Cifras Significativas
x1
x2
Error relativo (*)
3
0,667
-0,33.10-2
100
4
0,6667
-0,3.10
10
5
0,66667
0
1
6
0,666667
0,3
0,1
7
0,6666667
0,33
0,01
(*) Para calcular este error se considera como valor verdadero de x1 = 1
3
Ahora resolvemos el mismo sistema intercambiando los renglones.
1
1  R2 →R1 (−0.00005)+R2  1
1
1 
 0.00005 5 3.33335 R12  1

 →
 

→
1
1 
 1
 0.00005 5 3.33335
 0 4.99995 3.33333
3/5
Algebra y Geometría 2009
Tópicos Complementarios
Lo cual nos da el sistema equivalente:
De donde obtenemos:
x2 =
)
2
= 0 ,6
3
x1 = 1 − x 2
Nuevamente tomamos distintas cifras significativas y resumimos los resultados en la
siguiente tabla:
Cifras Significativas
3
4
5
6
7
x2
0,667
0,6667
0,66667
0,666667
0,6666667
x1
Error relativo (*)
0,333
0,3333
0,33333
0,333333
0,3333333
0,001
0,0001
0,00001
0,000001
0,0000001
En este último caso, vemos que el error relativo no varía drásticamente como en la
solución anterior.
Así, vemos que los elementos que son cercanos a cero, son elementos malos para hacer
ceros. En general, para evitar este problema se elige como elemento para hacer ceros
(el cual recibe el nombre de elemento pivotal o simplemente pivote) como el elemento
mayor en valor absoluto de entre todos los candidatos.
Si hiciéramos el mismo trabajo utilizando el método de Eliminación de Gauss-Jordan,
que consiste en reducir la matriz asociada al sistema a una matriz equivalente
escalonada por renglones reducida, llegaríamos al mismo resultado pero con más
lentitud.
2. ¿Cuánto tiempo requiere la computadora en dar dichas respuestas?
Otro factor fundamental a considerar al resolver un problema es el tiempo que demanda
la resolución por computadora. Para estimarlo se deben considerar el tipo y la cantidad
de operaciones involucradas en el proceso.
La tabla muestra el tiempo promedio que utilizará una computadora para realizar las dos
operaciones básicas.
Operación
Tiempo promedio
Suma o resta
0,5.10-6=0,0000005
Multiplicación o división
2.10-6=0,0000002
[segundos]
4/5
Algebra y Geometría 2009
Tópicos Complementarios
No siempre resulta sencillo contar las operaciones que se precisan ejecutar para resolver
un problema.
El siguiente cuadro muestra el número de operaciones a llevar a cabo para resolver un
S.E.L. por eliminación de Gauss-Jordan y eliminación Gaussiana, donde A es una
matriz invertible de n x n.
Técnica
Solución Ax=b
por eliminación de Gauss
Solución Ax=b
por eliminación de Gauss-Jordan
Nº de multiplicaciones
n3 n 2
+
4
4
Nº de sumas
n3 n
−
4
4
n3 n2
+
2
2
n3 n
−
2
2
Analizamos el tiempo que insume resolver sistemas de diferente orden:
Técnica
3
33 3 2
+
2
2
Nº de
sumas
23 2
−
4
4
3
3
3
−
4
4
3
100 100
−
4
4
3
2
2
−
2
2
3
3
3
−
2
2
100
100 3 100 2
+
2
2
100 3 100
−
2
2
Orden
2
Eliminación
de Gauss
3
100
2
Eliminación
de GaussJordan
Nº de
multiplicaciones
23 2 2
+
4
4
3
3
32
+
4
4
3
100
100 2
+
4
4
3
2
2
2
+
2
2
Tiempo promedio
[segundos]
≅ 4,5.10-6 = 0,0000045
≅ 17.10-6 = 0,000017
≅ 0,62512
≅ 9.10-6 = 0,000009
≅ 33.10-6 = 0,000033
≅ 1,2524
CONCLUSIÓN
En gral, para resolver el sistema Ax=b en una computadora normal, ocurren errores de
redondeo en cada paso del proceso debido a la aritmética finita de la máquina, por lo
que no se obtienen los valores exactos de las incógnitas.
Por lo cual se estudia que estos errores no se propaguen o acumulen durante todo el
proceso y se estima el error en la solución calculada, mejorando los algoritmos de
resolución. Esto significa que los métodos que conocen no siempre son los adecuados
para resolver los sistemas que se les presentan. Existen otros métodos de resolución que
mejoran a estos y pueden abordar otro tipo de problemas.
Otro problema al que nos enfrentamos es el tamaño del sistema, por el tiempo que
conlleva su resolución. Esto depende del procesador con el que estamos trabajando.
Generalmente un sistema se considera de gran tamaño cuando tiene más de 10000
variables, pero esta noción cambia a medida que avanza la tecnología.
Queda evidenciada la importancia del continuo progreso en la optimización de los
algoritmos para resolver SEL y del avance de la tecnología.
5/5