´ Algebra Lineal y Num´ erica (Grupo 1) 1 20/9/16 Estas NO son unas notas de la asignatura, simplemente un recuento del desarrollo de las clases. En la bibliograf´ ıa se pueden encontrar textos mucho m´as completos y exhaustivos • Sistemas de ecuaciones lineales a 11 x 1 + a 12 x 2 + ··· + a 1n x n = b 1 , a 21 x 1 + a 22 x 2 + ··· + a 2n x n = b 2 , . . . a n1 x 1 + a n2 x 2 + ··· + a nn x n = b n , (1) donde a ij ,1 ≤ i, j ≤ n, son los llamados coeficientes del sistema, x i son las inc´ognitas y b i los t´ erminos independientes, con 1 ≤ i ≤ n. Todos estos escalares pertenecen al cuerpo K = R o C. El sistema (1) se puede escribir matricialmente como Ax = b, (2) donde A =(a ij )= a 11 a 12 ··· a 1n a 21 a 22 ··· a 2n . . . . . . . . . . . . a n1 a n2 ··· a nn , x = x 1 x 2 . . . x n , b = b 1 b 2 . . . b n , siendo A la matriz de coeficientes, x la matriz de variables o inc´ognitas y b la matriz de t´ erminos independientes. La matriz (A|b) se denomina matriz ampliada del sistema. El sistema (1) o (2) es incompatible si no posee soluci´ on. Si la posee, diremos que el sistema es compatible ; en este caso tendremos que (2) es compatible determinado si la soluci´ on es ´ unica, mientras que es compatible indeterminado si posee m´ as de una soluci´ on, en cuyo caso tendr´ a infinitas soluciones. Tambi´ en se dice que dos sistemas de ecuaciones lineales son equiva- lentes si poseen las mismas soluciones. 1
Transcript
Algebra Lineal y Numerica (Grupo 1)
1 20/9/16
Estas NO son unas notas de la asignatura, simplemente un recuento deldesarrollo de las clases. En la bibliografıa se pueden encontrar textos muchomas completos y exhaustivos
donde aij , 1 ≤ i, j ≤ n, son los llamados coeficientes del sistema, xison las incognitas y bi los terminos independientes, con 1 ≤ i ≤ n.Todos estos escalares pertenecen al cuerpo K = R o C.
El sistema (1) se puede escribir matricialmente como
Ax = b, (2)
donde
A = (aij) =
a11 a12 · · · a1na21 a22 · · · a2n...
.... . .
...an1 an2 · · · ann
, x =
x1x2...xn
, b =
b1b2...bn
,
siendo A la matriz de coeficientes, x la matriz de variables o incognitasy b la matriz de terminos independientes. La matriz (A|b) se denominamatriz ampliada del sistema.
El sistema (1) o (2) es incompatible si no posee solucion. Si la posee,diremos que el sistema es compatible; en este caso tendremos que (2)es compatible determinado si la solucion es unica, mientras que escompatible indeterminado si posee mas de una solucion, en cuyo casotendra infinitas soluciones.
Tambien se dice que dos sistemas de ecuaciones lineales son equiva-lentes si poseen las mismas soluciones.
1
• Matrices. Elementos.
Una matriz de tamano m× n con coeficientes en k, es un conjunto dem · n elementos de k dispuestos en m filas y n columnas. Si notamosA una tal matriz, el elemento situado en la fila i, columna j, se notaraaij .
Por ejemplo, la matriz de Hilbert se define como hij = 1i+j .
• Operaciones con matrices: suma, producto por un escalar.
Dadas dos matrices del mismo tamano, A y B, su suma es otra matrizC, del mismo tamano, verificando cij = aij + bij .
Dado α ∈ k, la matriz α · A es otra matriz del mismo tamano que A,cuyas entradas son αaij
• Producto de matrices. Inversa de una matriz.
El producto de las matrices A ∈ Mm×n(k) y B ∈ Mn×p(k) es unamatriz C ∈Mm×p(k), cuya entrada ij es el producto de la fila i de Apor la columna j de B.
cij =n∑k=1
aik · bkj
Si A ·B = B ·A = In decimos que B es la inversa de A.
• Traspuesta de una matriz
At se obtiene intercambiando filas por columnas, At ∈Mn×m(k)
• Determinante de una matriz (desarrollo por una fila/columna).
A cada matriz A cuadrada se le asigna un numero que llamaremosdeterminante de A y representaremos por det(A) o |A|.Una submatriz de una matriz A es la matriz resultante de eliminar enA determinadas filas y/o columnas. Un menor de una matriz A es eldeterminante de una submatriz cuadrada.
Se denomina menor complementario del elemento aij de A, y se denotapor αij , al determinante de la submatriz obtenida al eliminar en A lafila i–esima y la columna j–esima.
Se denomina adjunto del elemento aij de A, y lo denotaremos por Aij ,a
Aij = (−1)i+jαij .
2
El calculo del determinante de una matriz cuadrada A puede ser real-izado mediante la siguiente formula recurrente:
– Si n = 1 entonces A = (a11), y se define |A| = a11.
– Si n > 1, entonces
|A| =n∑i=1
akiAki, para cualquier 1 ≤ k ≤ n.
Observese que mediante esta formula recurrente, el calculo de un de-terminante de una matriz de orden n se traslada al calculo de n deter-minantes de otras tantas matrices de orden n− 1, que son los menorescomplementarios de todos los elementos de la fila k-esima.
Propiedades de los determinantes:
1. El valor de |A| no depende de la fila k elegida.
2. |At| = |A|.Como consecuencia de esta propiedad, podemos dar una definicionequivalente del determinante cambiando el papel de las filas porel de las columnas:
|A| =n∑i=1
aikAik, para cualquier 1 ≤ k ≤ n.
Y mas importante aun,
|AB| = |A| |B|.
• Matrices elementales
Se denominan transformaciones elementales a ciertas transformacionesque se realizan en una matriz y que nos seran de gran utilidad en laresolucion de sistemas de ecuaciones lineales ası como en otras opera-ciones con matrices.
• Transformacion Fij . Intercambia las filas i–esima y j–esima de Aal multiplicar por la izquierda, A por la matriz Fij , siendo esta elresultado de intercambiar las filas i–esima y j–esima de la matriz Im.
3
2 23/9/16
• Transformacion Fi(α). Multiplica la fila i–esima de A por un numeroα 6= 0. Esto se consigue multiplicando por la izquierda A por la matrizFi(α), siendo esta el resultado de multiplicar por α la fila i–esima dela matriz Im.
• Transformacion Fij(α). Suma a la fila i–esima de A su fila j–esimamultiplicada por α 6= 0, que se consigue multiplicando por la izquierdala matriz A por la matriz Fij(α), siendo esta la resultante de sumar ala fila i–esima de la matriz Im su fila j–esima multiplicada por α.
Transformaciones elementales de columnas. Son las analogas a las trans-formaciones elementales de fila pero operando por columnas.
Propiedades:
1. Fij = Fji
2. Cij = Cji
3. Fij = Cij
4. Fi(α) = Ci(α) y Fij(α) = Cji(α)
5. |Fij | = |Cij | = −1
6. |Fi(α)| = |Ci(α)| = α
7. |Fij(α)| = |Cij(α)| = 1
8. F−1ij = Fij y C−1ij = Cij
9. Si α 6= 0, F−1i (α) = Fi(1/α) y C−1i (α) = Ci(1/α)
10. F−1ij (α) = Fij(−α) y C−1ij (α) = Cij(−α)
• Forma reducida de una matriz
Dada A existen matrices Fi, Cj tales que
Fn · · ·F1 ·A · C1 · · ·Cl =
(Ir 00 0
)esta es la llamada forma reducida de la matriz A.
• Rango de una matriz
Es la dimension de la identidad en su forma reducida.
4
3 27/09/16
Aplicaciones de la forma reducida
• Calculo del determinante de una matriz por medio de su forma re-ducida.
El determinante de una matriz no se altera si aplicamos transforma-ciones elementales del tipo Fij(α) o Cij(α) hasta que conseguimos unamatriz triangular (o diagonal), cuyo determinante es el producto delas entradas de su diagonal principal (desarrollando el determinantepor las filas o columnas que tienen todos sus elementos nulos, salvouno).
• Calculo de la inversa de una matriz por medio de su forma reducida.
Si una matriz es invertible, su forma reducida es la identidad, luego laformula
F ·A = I o A · C = I
nos proporciona un metodo para calcular la inversa de A (a condicionde que nos limitemos a aplicar solo operaciones por filas o solo porcolumnas).
• Ejercicios 1.1 al 1.4 del boletın.
4 30/09/16
• Sistema de ecuaciones. Soluciones.
Un sistema de ecuaciones lineales se escribe A · x = b, donde
1. A es la matriz de coeficientes.
2. x es el vector incognita.
3. b es el termino independiente (si b = 0 el sistema se dice ho-mogeneo).
4. (A|b) es la matriz ampliada del sistema.
5
Una solucion de un sistema es un vector
α1...αn
, verificando que
A ·
α1...αn
= b
Un sistema se dice compatible (S.C.) si tiene solucion, e incompatible(S.I.) si no la tiene.
En caso de tener solucion, si esta es unica, el sistema es compatibledeterminado (S.C.D.) y si existe mas de una, es compatible indetermi-nado (S.C.I.)
• Teorema de Rouche-Frobenius.
Sea Ax = b un sistema de m ecuaciones con n incognitas, entonces
1. El sistema es compatible si y solo si rg(A|b) = rg(A).
2. Si b = 0, las soluciones del sistema forman una variedad lineal dedimension n− rg(A).
3. Si b 6= 0 las soluciones del sistema son de la forma x1+u donde x1es una solucion particular del sistema y u es la solucion generaldel sistema homogeneo asociado.
• Sistemas de ecuaciones homogeneos y no homogeneos.
• Base de soluciones. Solucion particular
• Espacios vectoriales.
Un espacio vectorial es una cuaterna (V,+, ·, k) donde V es un conjunto(cuyos elementos se llaman vectores), + es una operacion interna en V ,es decir + : V ×V −→ V (suma de vectores), un producto por escalar,· : k × V −→ V , y un cuerpo k verificando las siguientes propiedades:
1. x+ y = y + x, ∀x, y ∈ V2. (x+ y) + z = x+ (y + z), ∀x, y, z ∈ V3. ∃ 0 ∈ V tal que x+ 0 = 0 + x = x, ∀x ∈ V4. ∀x ∈ V , ∃a ∈ V , tal que x+ a = a+ x = 0
5. α · (x+ y) = α · x+ α · y, ∀α ∈ k, ∀x, y ∈ V
6
6. (α+ β) · x = α · x+ β · x, ∀α, β ∈ k, ∀x ∈ V7. α · (β · x) = (α · β) · x, ∀α, β ∈ k, ∀x ∈ V8. ∃ 1 ∈ k tal que 1 · x = x, ∀x ∈ V
• Ejemplos de espacios vectoriales:
1. Rn,
2. Pn(R) polinomios de grado menor o igual que n con coeficientesreales,
3. Mm×n(R) (matrices m× n con coeficientes reales).
• Combinacion lineal de vectores.
Un vector x es combinacion lineal de {x1, . . . , xr} si se verifica
α1 · x1 + · · ·+ αr · xr = x
para unos ciertos valores de los αi.
• Dependencia e independencia lineal de vectores
Un conjunto de vectores {x1, . . . , xr} es linealmente dependiente (l.d.)si existen α1, . . . , αr NO TODOS NULOS, tales que
α1 · x1 + · · ·+ αr · xr = 0
En otro caso, los vectores se dicen linealmente independientes (l.i.)
Observaciones
1. x depende linealmente de {x1, . . . , xr} si el sistema
α1x1 + · · ·+ αrxr = x
es compatible.
2. {x1, . . . , xr} linealmente dependiente si α1x1 + · · · + αrxr = 0tiene mas de una solucion.
• Sistemas generadores. Base. Un conjunto de vectores {x1, . . . , xr} esun sistema generador de un espacio vectorial si cualquier vector deV se puede poner como combinacion lineal de ellos. Si un sistemagenerador es, ademas, linealmente independiente, se dice que es unabase del espacio vectorial.
Observaciones
7
1. {x1, . . . , xr} es un sistema generador si
α1x1 + · · ·+ αrxr = x
es compatible para todo vector x.
2. {x1, . . . , xr} es una base si α1x1 + · · · + αrxr = x es compatibledeterminado.
• Dado el conjunto {x1, . . . , xr}, se define su rango, como el numero devectores linealmente independiente en dicho conjunto.
A partir de cualquier conjunto de vectores podemos obtener un sub-conjunto maximo de vectores independientes, agregandolos de uno enuno y comprobando si son linealmente independientes, desechando losque no lo sean.
• Bases. Dimension. Todas las bases de un espacio vectorial V tienen elmismo numero de elementos. A dicho numero se le llama dimensionde V , y se nota dim (V ).
5 4/10/16
• Si B = {x1, . . . , xr} es una base de V y x ∈ V se escribe (de maneraunica), como
x = a1x1 + · · ·+ arxr
diremos que las coordenadas de x respecto de la base B, son los coefi-cientes de dicha combinacion lineal
xB =
a1...ar
• Cambio de bases
Si tenemos dos bases de un mismo espacio vectorial, B = {x1, . . . , xr}y C = {y1, . . . , yr} la expresion del cambio de base de B a C viene dadapor la matriz de coordenadas de los elementos de la base de partidaen funcion de los de llegada,
vC =(x1C x2C
... xrC
)· vB
8
• Variedades lineales. Una variedad lineal L de un espacio vectorial Ves un subconjunto de vectores verificando:
1. x+ y ∈ L para todos x, y ∈ L.
2. α · x ∈ L, para todos α ∈ k, x ∈ L.
Dados {a1, . . . , ak} ∈ V , la variedad lineal generada por ellos, notadaL = L〈a1, . . . , ak〉, es el conjunto de todas las posibles combinacioneslineales de dichos vectores.
Si del s.g. {a1, . . . , ak} extraemos una base {a′1, . . . , a′l}, diremos quela dimension de L es l.
Si x ∈ L se escribe x = α1 · a′1 + · · ·+ αl · a′l, a los numeros α1, . . . , αlse les llamara coordenadas de x respecto de la base {a′1, . . . , a′l}.
• Ecuaciones de una variedad lineal.
Sin perdida de generalidad, podemos suponer que el sistema generadorde partida, esta formado por vectores linealmente independientes (sino es ası, eliminamos los que sobren)
L = L〈a1, . . . , ak〉 y {a1, . . . , ak} es una base de L.
• Ecuaciones vectoriales de una variedad lineal. x = α1a1 + · · ·+ αrar x1...xn
= α1
a11...a1n
+ · · ·+ αk
ak1...akn
• Ecuaciones parametricas de una variedad lineal.
x1 = α1a11 + · · ·+ αkak1...
...xn = α1a1n + · · ·+ αkakn
• Ecuaciones implıcitas de una variedad lineal.
x ∈ L, si rg(a1, . . . , ak, x) = k, con lo que el numero de ecuaciones in-dependientes implıcitas de una variedad de dimension k en un espaciode dimension n es exactamente n− k.
Ejemplo: La variedad lineal L de R3 generada por u = (1, 2, 3)t yv = (0, 1, 2)t tiene dimension 2 (pues sus generadores son l.i.) y sus
9
ecuaciones implıcitas vienen dadas por la condicion x ∈ L = 〈u, v〉 sirg(u|v|x) = 2, pero
rg
1 0 x2 1 y3 2 z
= rg
1 0 x0 1 y − 2x0 2 z − 3x
= rg
1 0 x0 1 y − 2x0 0 x− 2y + z
,
luego su ecuacion sera L : x − 2y + z = 0 (unica, puesto que hay3− dim(L)).
Recıprocamente, si queremos calcular una base de L, debemos solu-cionar el sistema homogeneo L : x − 2y + z = 0, cuya matriz decoeficientes (1,−2, 1) tiene rango r maximo (igual a 1 en este caso),seleccionamos r pivotes (por ejemplo la columna primera, y escribi-mos el sistema como x = 2y − z; ahora, dando a los parametros (y, z)los valores de la matriz identidad y resolviendo, obtenemos la base{(2, 1, 0)t, (−1, 0, 1)t} requerida.
6 7/10/16
Laboratorio. Introduccin a SAGE
7 11/10/16
• Operaciones con variedades. Suma e interseccion de variedades
Dadas dos variedades lineales L1, L2, de un espacio vectorial V , lavariedad lineal interseccion es
L1 ∩ L2 = {x ∈ V : x ∈ L1 ∧ x ∈ L2}
Ecuaciones de L1 ∩ L2 =
{Ec.L1
Ec.L2
Dadas dos variedades lineales L1, L2, de un espacio vectorial V , lavariedad lineal suma es
L1 + L2 = 〈L1 ∪ L2〉
Sistema generador de L1 + L2 = (s.g.L1) ∪ (s.g.L2).
Ejemplo: Consideremos las siguientes variedades lineales de R4
10
L1 :
{x− y − z + t = 0x+ y − z − t = 0
L2 = 〈
1111
,
222−2
〉Para calcular la interseccion, comenzamos por las ecuaciones implıcitas
de L2, 2 = rg
1 2 x1 2 y1 2 z1 −2 t
= rg
1 2 x0 0 y − x0 0 z − x0 −4 t− x
= rg
1 2 x0 −4 t− x0 0 y − x0 0 z − x
,
esto es, L2 :
{y − x = 0z − x = 0
Ahora, pues, L1 ∩ L2 :
x− y − z + t = 0x+ y + z + t = 0
y − x = 0z − x = 0
Pero estas ecuaciones son linealmente dependientes, puesto que
rg
1 −1 −1 11 1 −1 −1−1 1 0 0−1 0 1 0
= rg
1 −1 −1 10 2 0 −20 0 −1 10 −1 0 1
= rg
1 −1 −1 10 2 0 −20 0 −1 10 0 0 0
,
con lo que unas ecuaciones independientes1 de la interseccion serıan
L1 ∩ L2 =
x− y − z + t = 0
2y − 2t = 0−z + t = 0
Para la suma, las ecuaciones son L1 =
{x− y − z + t = 0
2y − 2t = 0, seleccio-
nando las columnas 1 y 2, podemos escribir L1 =
{x− y = z − t
2y = 2t, y
dando valores de la matriz identidad a los parametros z y t obtenemosuna base de L1
L1 = 〈
1010
,
0101
〉1De las que se podrıa obtener una base, si fuese necesario
11
Con lo que un sistema generador de L1 + L2 sera el formado por launion de los sistemas generadores de ambas variedades
L1 + L2 = 〈
1010
,
0101
,
1111
,
222−2
〉De dicho sistema generador se puede obtener una base2 de L1 + L2,
– rg
1010
= 1, base {
1010
, . . . }
– rg
1 00 11 00 1
= 2, base {
1010
,
0101
, . . . }
– rg
1 0 10 1 11 0 10 1 1
= 2, base {
1010
,
0101
, . . . }
– rg
1 0 20 1 21 0 20 1 −2
= 3, base {
1010
,
0101
,
222−2
}
8 14/10/16
Problemas
9 18/10/16
• Sistemas compatibles determinados
• Eliminacion Gaussiana. La idea del metodo consiste en aplicar a lamatriz ampliada del sistema transformaciones elementales sobre las
2A partir de la cual podrıamos obtener unas ecuaciones, si fuese necesario
12
filas obteniendo, de esta forma, sistemas equivalentes al dado perocada vez mas manejables. Ası se consigue un sistema equivalente alinicial cuya matriz de coeficientes es triangular superior.
Este metodo, tambien conocido como de eliminaciones sucesivas ometodo de escalonamiento, comienza restando multiplos de la primeraecuacion o, lo que es lo mismo, de la primera fila a las restantes,con el fin de eliminar la incognita x de las ultimas ecuaciones. Estopuede hacerse por ser a11 6= 0; este coeficiente se conoce como pivote.Procederemos entonces como sigue:
– Comencemos por anular todos los elementos ai1 con 2 ≤ i ≤ n.
∗ Si a11 6= 0, mediante transformaciones elementales de filas,
Fij(α), con α = − ai1a11
, podemos anular todos los elementos
de la primera columna situados por debajo de el.
∗ Si a11 = 0 y existe un 2 ≤ i ≤ n tal que ai1 6= 0, pode-mos permutar la primera e i–esima filas mediante la trans-formacion F1i y proceder despues como en el caso anterior.
∗ Si ai1 = 0 ∀ i = 1, . . . , m, la primera columna es de ceros ypor tanto, ai1 = 0 ∀ i > 1, es decir, se trata de una columnadel tipo de las matrices escalonadas.
– Consideremos ahora el elemento a22 resultante de las transforma-ciones anteriores y, al igual que hicimos antes con a11, si a22 6= 0,lo utilizamos para hacer ceros por debajo de el en la segundacolumna. Si fuese a22 = 0 y algun elemento ai2 6= 0, 3 ≤ i ≤ n,entonces realizamos la transformacion F2i, etc.
– Reiterando el proceso, llegamos a una matriz escalonada U .
Hasta ahora hemos considerado como pivotes elementos cualesquieraque no sean nulos. Hagamos algunas observaciones en cuanto a laeleccion del pivote en cada etapa de eliminacion.
Ejemplo: Consideremos el sistema lineal(2−26 1
1 1
)(xy
)=
(12
).
La solucion exacta del sistema viene dada por
x = 2− y ≈ 1.00000001490116, y =1− 2−25
1− 2−26≈ 0.99999998509884.
13
Si tomamos 2−26 como pivote, obtenemos(2−26 1 1
1 1 2
)−→
(2−26 1 10 1− 226 2− 226
)=⇒ y = 1, x = 0.
Pero si el pivote elegido es 1,(2−26 1 1
1 1 2
)−→
(1 1 20 1− 2−26 1
)≈(
1 1 20 1 1
)=⇒ x = 1, y = 1.
Este ejemplo pone de manifiesto que errores de redondeo con efectodesastroso provienen de la division por pivotes “muy pequenos”. Enla practica, para eludir este problema, se recurre a las estrategias depivoteo parcial y total, que se estudiaran en las clases de laboratorio.
10 21/10/16
Laboratorio 2. Gauss. Pivote parcial y Total
11 25/10/16
• Descomposicion LU de una matriz
Al aplicar la eliminacion gaussiana al sistema Ax = b realizamos trans-formaciones elementales para conseguir triangular A. Si esto se lograsesin intercambios de filas, obtendrıamos una matriz triangular superior
U = FkFk−1 · · ·F1A,
donde Fi, 1 ≤ i ≤ k, son transformaciones de fila aplicadas a la matrizA.
Como |Fi| = ±1, 1 ≤ i ≤ k,
∃ (FkFk−1 · · ·F1)−1 = L.
Ası, se tiene que A = LU , con L = (lij) una matriz triangular inferiortal que lii = 1, 1 ≤ i ≤ n. Ademas, esta factorizacion es unica.
Calculo efectivo de la factorizacion LU
Ejemplo: Considerese la matriz A =
3 1 26 3 2−3 0 −8
. Entonces
14
A =
3 1 26 3 2−3 0 −8
L =
11
1
F31(1)F21(−2)A =
3 1 20 1 −20 −1 −6
L =
12 1−1 1
F32(1)F31(1)F21(−2)A =
3 1 20 1 −20 0 −8
L =
12 1−1 −1 1
Es decir,
A = LU =
1 0 02 1 0−1 −1 1
3 1 20 1 −20 0 −12
.
• Descomposicion de Cholesky de una matriz
Si la matriz A es simetrica, admite factorizacion LU, y es definidapositiva (todos los pivotes obtenidos son positivos), entonces se puedecalcular la factorizacion de Cholesky de la matriz A, que no es masque la factorizacion anterior, donde las matrices L y U son la una latraspuesta de la otra, siendo A = LLt.
Dicha factorizacion se puede calcular directamente por sustitucion re-gresiva, ya que si A = (aij) y L = (lij) con lij = 0 si i < j
lii = aii −i−1∑k=1
l2ki lij =aij −
∑j−1k=1 lkilkjljj
Ejemplo: Considerese la matriz A =
1 −1 2−1 3 −1
2 −1 5
. Entonces
A =
l11 0 0l21 l22 0l31 l32 l33
· l11 l21 l31
0 l22 l320 0 l33
De aquı:
– l211 = 1⇒ l11 = 1
– l11l21 = −1⇒ l21 = 1
15
– l11l31 = 2⇒ l31 = 2
– l221 + l222 = 3⇒ l22 =√
2
– l21l31 + l22l32 = −1⇒ l32 = 1/√
2 =√
2/2
– l231 + l232l233 = 5⇒ l33 = 1/
√2 =√
2/2
Una matriz simetrica es definida positiva si todos sus menores princi-pales Ar = det(aij)1≤i,j≤r son estrictamente positivos. En el ejemploanterior, |A1| = 1, |A2| = 2 y |A3| = 1 son todos positivos.
12 28/10/16
• Transformaciones de Householder
Dado un vector v ∈ Rn, se define la transformacion de Householderasociada al vector v como:
Hv =
{I v = 0I − 2
vtvvvt v 6= 0
Ejemplo: Si v = (3, 1, 0)t, entonces
Hv =
−4/5 −3/5 0−3/5 −4/5 0
0 0 1
Hv verifica:
1. Htv = Hv (simetrica)
2. H−1v = Hv (unitaria)
• Transformaciones de Householder
El efecto que tiene una transformacion de Householder sobre un vectores, dependiendo de su posicion con respecto a v es:
a) Hv(v) = −v.
b) Si x ⊥ v, entonces Hv(x) = x.
Ahora debemos utilizar transformaciones de Householder para simpli-ficar un sistema de ecuaciones, sin empeorar su numero de condicion.
La idea es llevar cada columna de la matriz de coeficientes A en unvector que tenga el mayor numero posible de entradas nulas, esto ha
16
de hacerse de forma secuencial, respetando las columnas que ya hayansido transformadas, y teniendo en cuenta que el modulo de cada vectory su transformado deben coincidir.
Para llevar el vector x en el y (siendo ‖x‖ = ‖y‖), debemos elegirv = x−y
‖x−y‖ .
Ejemplo: si x = (1, 2, 2)t e y = (3, 0, 0)t, entonces
v = 1√12
(−2, 2, 2)t = 1√3(−1, 1, 1)t
13 31/10/16
• Errores
Dada una aproximacion x∗ del numero x, se definen los errores absolutoy relativo de la aproximacion, respectivamente, como
Ea = |x− x∗|; Er =Ea|x|, o bien, Er =
Ea|x|
100%.
• Normas matriciales
Una norma en un espacio vectorial V es una aplicacion ‖ . . . ‖ : V −→ kverificando
Nos interesa extender esta nocion de norma a matrices, pero verifi-cando las siguientes propiedades:
1. ‖A ·B‖ ≤ ‖A‖ · ‖B‖ (normas multiplicativas)
2. ‖A · x‖ ≤ ‖A‖ · ‖x‖ (consistentes con la vectorial)
Ejemplos de unas tales normas,
1. ‖A‖2 = max{√xtAtAx :
√xtx = 1} (norma euclıdea)
2. ‖A‖F =√tr(AtA) (norma de Frobenius)
17
• Condicionamiento de un sistema
Si tenemos un sistema compatible determinado A ·x = b, tenemos que
‖b‖ ≤ ‖A‖ · ‖x‖ ‖x‖ ≤ ‖A−1‖ · ‖b‖
Al introducir un error εb en el valor de b, el valor obtenido comosolucion sera x+ εx, verificandose que
‖εb‖ ≤ ‖A‖ · ‖εx‖ ‖εx‖ ≤ ‖A−1‖ · ‖εb‖
Si notamos cond(A) = ‖A‖‖A−1‖, se tiene que
1
cond(A)
‖εb‖‖b‖≤ ‖εx‖‖x‖
≤ cond(A)‖εb‖‖b‖
Si un ordenador tiene una precision de 10−n y de un sistema Ax = b sesabe que cond(A) ' 10k, si se precisa la solucion con n − k cifras exactas,se dice que el sistema esta bien condicionado. Si se requieren mas de n− kcifras, se dice que el sistema esta mal condicionado.
En un caso ideal, cond(A) = 1, se tiene ‖εb‖‖b‖ = ‖εx‖‖x‖ .
• Transformaciones y condicionamiento
Si a un sistema Ax = b se le aplica una transformacion F para re-solverlo, se convierte en el sistema FAx = Fb, que tiene como numerode condicion cond(FA), y se verifica
cond(FA) ≤ cond(F ) · cond(A)
con lo que debemos aplicar transformaciones que no empeoren el condi-cionamiento inicial del mismo. Lo optimo es usar transformaciones Fcon numero de condicion igual a 1
• Matrices unitarias
Una matriz A se dice unitaria si At ·A = I.
La norma euclıdea de una matriz unitaria es 1 y por tanto su numerode condicion euclıdeo es 1.
• Descomposicion QR
El metodo QR para resolver un sistema Ax = b, consiste en llevarla matriz A en una triangular superior R por medio de transforma-ciones de Householder, Hvr . . . Hv2Hv1Ax = Hvr . . . Hv2Hv1b, dondeA = (Hvr . . . Hv2Hv1)−1R = Hv1 . . . HvrR = QR.
18
14 4/11/16
Laboratorio. Practica 3. LU y Cholesky
15 8/11/16
Primera prueba parcial
16 11/11/16
• Aplicaciones lineales entre espacios vectoriales.
Una aplicacion f entre dos conjuntos X e Y es cualquier regla que nospermite asignar a cada elemento x del conjunto inicialX un unico elementoy del conjunto final Y . Se denota por f : X → Y .
Se dice que f : U → V es una aplicacion lineal entre espacios vectori-ales si
– ∀u, v ∈ U =⇒ f(u+ v) = f(u) + f(v)
– ∀λ ∈ k y ∀u ∈ U =⇒ f(λu) = λf(u).
• Matriz de una aplicacion lineal
Una aplicacion lineal f : U → V queda definida cuando conocemos lostransformados f(ui) de una base B = {u1, . . . , un} de U .
Dado que f(ui) ∈ V , podemos expresarlos de la forma
que expresado en forma matricial quedax′1x′2...x′m
=
a11 a21 · · · an1a12 a22 · · · an2...
.... . .
...a1m a2m · · · anm
x1x2...xn
⇐⇒ x′ = Ax
Es decir, f(x) = Ax donde A es la matriz cuyas columnas son lascoordenadas, respecto de la base BV de V , de los transformados deuna base BU de U .
Dicha matriz recibe el nombre de matriz asociada a la aplicacion linealf respecto de las bases BU de U y BV de V .
Ejemplo: Consideremos la aplicacion f : R3 → R2, que a cada vector(x, y, z)t ∈ R3 le hace corresponder el vector (x− 2y, y + z)t ∈ R2
Esta aplicacion es lineal, puesto que, para todos u = (u1, u2, u3)t,
v = (v1, v2, v3)t ∈ R3, tenemos
f(u)+f(v) = f
u1u2u3
+f
v1v2v3
=
(u1 − 2u2u2 + u3
)+
(v1 − 2v2v2 + v3
)=
=
(u1 − 2u2 + v1 − 2v2u2 + u3 + v2 + v3
)=
((u1 + v1)− 2(u2 + v2)(u2 + v2) + (u3 + v3)
)= f(u+v),
f(λu) = f
λu1λu2λu3
=
(λu1 − 2λu2λu2 + λu3
)= λ
(u1 − 2u2u2 + u3
)= λf(u)
Si elegimos bases en cada espacio, B3 = {(1, 0, 0)t, (0, 1, 0)t, (0, 0, 1)t}(la canonica de R3) y la canonica de R2, B2 = {(1, 0)t, (0, 1)t}, porejemplo, la matriz de la aplicacion lineal respecto de estas bases secalcula colocando (por columnas) las coordenadas de las imagenes delos elementos de B3 respecto de B2, lo que nos da una matriz 2× 3
f
100
=
(10
), f
010
=
(−2
1
), f
001
=
(01
)
20
Con lo que
Mf (B3, B2) =
(1 −2 00 1 1
)
17 15/11/16
• Imagen y antiimagen de una variedad lineal
Si M es una variedad lineal, f(M) es la variedad lineal engendradapor las imagenes de los elementos de una base de M .
Ejemplo: Si M en R3 cuya base es v = (1, 1,−2)t ∈ R3, la imagen deM por f , estara engendrada por el vector f(v) = (−1,−1)t ∈ R2.
Si L es una variedad lineal, su imagen inversa por la aplicacion linealf, f−1(L) es otra variedad lineal.
x ∈ f−1(L) =⇒ f(x) ∈ L
Imponiendo al vector f(x) que verifique las ecuaciones implıcitas de Lobtenemos las ecuaciones implıcitas de f−1(L). Matricialmente pode-mos tambien resolver esta cuestion de la siguiente forma:
Sea L una variedad lineal dada por sus ecuaciones implıcitas respectode una base fijada. A la matriz asociada al sistema de ecuaciones queconstituye dichas ecuaciones implıcitas, la llamaremos B, con lo quelas ecuaciones implıcitas de L las representamos matricialmente comoBy = 0.
Sea f la aplicacion lineal dada por y = f(x) y sea A la matriz asociadaa f , por lo que y = Ax.
x ∈ f−1(L) ⇐⇒ f(x) ∈ L ⇐⇒ Ax ∈ L
como Ax es un vector, la condicion para que pertenezca a L es queverifique sus ecuaciones implıcitas, es decir que B(Ax) = 0.
BA es la matriz asociada a las ecuaciones implıcitas de f−1(L).
Ejemplo: Si L en R2 tiene ecuaciones x + y = 0, la variedad f−1(L)tiene ecuaciones
(1 1
)( 1 −2 00 1 1
) xyz
= 0.
Esto es, x− y + z = 0.
Problema 4.2
21
18 18/11/16
Problemas
19 22/11/16
• Nucleo e imagen de una aplicacion lineal
Sea f : U → V una aplicacion lineal.
Se denomina nucleo de f y se denota por ker f al conjunto
ker f = {x ∈ U : f(x) = 0} = f−1(0)
Una vez obtenidas las ecuaciones de la aplicacion lineal x′ = Ax, elsistema Ax = 0 nos proporciona unas ecuaciones implıcitas del nucleode la aplicacion.
Se denomina imagen de f y se denota por Imf o f(U) al conjunto
Imf = f(U) = {v ∈ V : v = f(u) con u ∈ U}
• Subespacios invariantes para una aplicacion lineal.
Dada una aplicacion lineal f : V −→ V , un subespacio L de V se diceinvariante para f si verifica f(L) ⊆ L.
Si V = L1⊕L2⊕· · ·⊕Lr es una descomposicion de V en suma directade subespacios invariantes, entonces la union de las bases de cada unode los subespacios constituye una base de V y se tiene que la matrizde f respecto de esta base, es diagonal por cajas.
Si, ademas, dim(Li) = 1 para todos los i, las cajas son de tamano 1, ydiremos que la aplicacion lineal es diagonalizable, puesto que su matrizsera diagonal.
Se dice que λ ∈ k es un autovalor de f si existe algun vector no nulox ∈ V tal que f(x) = λx. A dicho vector x no nulo se le denominaautovector de f asociado al autovalor λ.
A · x = λ · x ⇐⇒ (λI − A)x = 0, pero este sistema unicamente tienesolucion no trivial si el rango de la matriz (λI −A) no es maximo, esdecir, cuando el determinante de la matriz (λI −A) es igual a 0.
22
Se denomina polinomio caracterıstico de una matriz A al polinomioque se obtiene desarrollando el determinante de la matriz λI −A.
Los autovalores corresponden a las raıces del polinomio caracterısticode la matriz.
Los autovectores asociados al autovalor λi son las soluciones de laecuacion (λiI −A)x = 0
20 25/11/16
Problemas diagonalizacion, 4.8 y 4.7
21 29/11/16
• Metodos iterativos de resolucion de sistemas: convergencia
A partir de un sistema Ax = b, descomponemos la matriz A como sumade dos matrices M + N , de modo que M sea facilmente invertible, ytransformamos el sistema en Mx = −Nx + b, y posteriormente esteen x = −M−1Nx+M−1b, es decir, en un sistema equivalente:
x = Bx+ c
A partir de esta expresion, elegimos un valor inicial (o semilla) x0,y definimos la sucesion xn+1 = Bxn + c. Si existe el lımite de estasucesion, x, tendrıamos que x = Bx + c, es decir, de converger estasucesion, lo harıa a la solucion del sistema.
Si x es la solucion del sistema, xn−x = B(xn−1−x) = B2(xn−2−x) =· · · = Bn(x0 − x), luego el comportamiento de la sucesion xn dependedel comportamiento de la potencia n-esima de B.
Si B = PDP−1, con D diagonal, tenemos Bn = PDnP−1, con lo quela sucesion converge en el caso en que todos los autovalores de D (queson los de B) son menores que 1 en valor absoluto.
• Metodo de Jacobi
Ax = b, descomponemos A = L+D+U donde L es la parte de A pordebajo de la diagonal principal, D la diagonal de A y U la parte de Apor encima de la diagonal principal. Ahora M = D y N = L+U , conlo que:
23
B = −D−1(L+ U) c = D−1b
este metodo convergera si y solo si el mayor autovalor (en modulo) de−D−1(L+ U) es menor que 1
Ejemplo:
{5x+ 2y = 1x− 4y = 0
, D =
(5 00 −4
), L + U =
(0 21 0
),
ahora B =
(0 −2
514 0
), c =
(150
).
• Metodo de Gauss-Seidel
Ax = b, descomponemos A = L+D+U donde L es la parte de A pordebajo de la diagonal principal, D la diagonal de A y U la parte de Apor encima de la diagonal principal. Ahora M = D+L y N = U , conlo que:
B = −(D + L)−1U c = (D + L)−1b
este metodo convergera si y solo si el mayor autovalor (en modulo) de−(D + L)−1U es menor que 1
Ejemplo:
{5x+ 2y = 1x− 4y = 0
, D + L =
(5 0−1 −4
), U =
(0 20 0
).
Ejercicio: Aplicar Jacobi y Gauss-Seidel al siguiente sistema, real-izando tres iteraciones y comenzando por x0 = (0, 0, 0)t,
10x+ 3y + z = 142x− 10y + 3z = −5x+ 3y − 10z = 14
• Metodo S.O.R. Este metodo (llamado de relajacion), consiste en trans-formar el sistema Ax = b en αAx = αb para α ∈ (0, 2) y descomponerla matriz αA como suma de (D + αL) + ((α− 1)D + αU), con lo quemanejamos una infinidad de casos, y el problema se reduce a localizarel valor de α que nos proporcione una convergencia mas veloz.
22 2/12/16
Laboratorio. Practica 4. Jacobi y Gauss-Seidel
24
23 9/12/16
Sistemas superdeterminados: solucion de mınimos cuadradosUn sistema superdeterminado es un sistema de ecuaciones en el que el
numero de ecuaciones es mayor que el de incognitas.Dado un sistema Ax = b incompatible, con rg(A) = r (maximo) y
rg(A|b) = r+1, el vector b no pertenece al espacio de columnas de la matrizA. Sin embargo, tomando un vector cualquiera b del espacio C(A), el sistemaAx = b tiene solucion unica.
Se conoce como problema de los mınimos cuadrados al problema de en-contrar, de entre todos los vectores de C(A), aquel que minimiza su distanciaal vector b, es decir, aquel vector b ∈ C(A) tal que ‖b− b‖ es mınima.
• Producto escalar
Un producto escalar es una aplicacion 〈−,−〉 : Rn ×Rn → R verifi-cando:
1. 〈x+ y, z〉 = 〈x, z〉+ 〈y, z〉2. 〈x, y〉 = 〈y, x〉3. 〈λx, y〉 = λ〈x, y〉4. 〈x, x〉 ≥ 0 y 〈x, x〉 = 0 solo si x = 0.
Ejemplo: 〈x, y〉 = x1y1 +2x1y2 +2x2y1 +5x2y2 +3x3y3 es un productoescalar en el espacio real tridimensional.
• Expresion matricial de un producto escalar.
Elegida una base B = {a1, . . . , an}, el producto escalar queda deter-minado por 〈ai, aj〉, si llamamos Q a la matriz
Cada producto escalar tiene asociada la norma ‖x‖ =√〈x, x〉
25
• Perpendicularidad: variedades ortogonales
Dos vectores se dicen ortogonales si su producto escalar es igual a 0.
• Ortonormalizacion: Gram-Schmidt
Dada una base {x1, . . . , xr} de un espacio vectorial dotado de un pro-ducto escalar 〈, 〉, podemos construir una B.O.N. (base ortonormal){y1, . . . , yr} que verifica L(x1, . . . , xi) = L(y1, . . . , yi) para todo i, sinmas que definir yi = xi + α1y1 + · · ·+ αi−1yi−1 y determinando los αde tal forma que yi sea ortogonal a todos los yk para k < i.
Operando ası, encontramos una base ortogonal, lo unico que falta porhacer es dividir cada vector yi por su modulo (lo que se llama nor-malizar el vector).
Ejemplo: Sea [V, 〈 〉] un espacio vectorial euclıdeo y sea A =
(2 11 2
)la matriz del producto escalar asociada a la base B = {v1, v2} ={(1,−1), (2, 0)} de V .
1. Tomamos, en primer lugar w1 = v1 y hacemos
w2 = v2 + λw1
con la condicion de que w2 ⊥ w1, es decir
〈v2 + λw1, w1〉 = 〈v2, w1〉+ λ〈w1, w1〉 = 0
Dado que
〈v2, w1〉 =(
2 0)( 2 1
1 2
)(1−1
)= 2
〈w1, w1〉 =(
1 −1)( 2 1
1 2
)(1−1
)= 2
=⇒ 2 + 2λ = 0
λ = −1 =⇒ w2 = v2 − w1 = (1, 1)
2. Normalizando los vectores obtenemos
u1 =w1
‖w1‖=
w1√〈w1, w1〉
=w1√
2= (
1√2,−1√
2)
〈w2, w2〉 =(
1 1)( 2 1
1 2
)(11
)= 6
u2 =w2
‖w2‖=
w2√〈w2, w2〉
=w2√
6= (
1√6,
1√6
)
26
Por lo que
B∗ = {( 1√2,−1√
2), (
1√6,
1√6
)}
es una base ortonormal de V .
24 13/12/16
• Sistemas incompatibles: seudosolucion
Un sistema superdeterminado es un sistema de ecuaciones en el que elnumero de ecuaciones es mayor que el de incognitas.
Dado un sistema Ax = b incompatible, con rg(A) = r (maximo) yrg(A|b) = r + 1, el vector b no pertenece al espacio de columnas de lamatriz A. Sin embargo, tomando un vector cualquiera b del espacioC(A), el sistema Ax = b tiene solucion unica.
Se conoce como problema de los mınimos cuadrados al problema deencontrar, de entre todos los vectores de C(A), aquel que minimiza sudistancia al vector b, es decir, aquel vector b ∈ C(A) tal que ‖b− b‖ esmınima.
Dicho vector es la proyeccion ortogonal de b sobre el espacio C(A), ental caso b = b+ a donde a ∈ C(A)⊥, con lo que Atb = Atb.
Las ecuaciones AtAx = Atb reciben el nombre de ecuaciones normalesdel sistema superdeterminado Ax = b, y su solucion seudosolucion delsistema Ax = b.
Ejemplo: Calcular la recta del plano que pasa por los puntos A =(1, 1), B = (2, 3) y C = (3,−1)
Si escribimos la ecuacion de la recta de la forma y = mx+n, el sistemaque debemos resolver es
m + n = 12m + n = 33m + n = −1
Este sistema es incompatible, sus ecuaciones normales AtAx = Atb
(1 2 31 1 1
) 1 12 13 1
( mn
)=
(1 2 31 1 1
) 13−1
27
esto es, (14 66 3
)(mn
)=
(43
)cuya solucion es m = −1, n = 3.
El error sera
‖Ax− b‖ = ‖
1 12 13 1
( −13
)−
13−1
‖ = ‖
1−2−1
‖ =√
6
25 20/14/16
• Transformaciones unitarias en sistemas superdeterminados
Si partimos de un sistema superdeterminado y realizamos operacioneselementales, puede que el sistema obtenido no posea la misma seu-dosolucion que el original3. Esto se evita si nos limitamos a realizartransformaciones unitarias, como, por ejemplo, transformaciones deHouseholder, que nos permiten transformar la matriz A en otra
HA = Hn . . . H1A =
t11 t12 . . . t1n0 t22 . . . t2n...
.... . .
...0 0 . . . tnn0 0 . . . 0...
......
0 0 . . . 0
=
(TO
)
Ası, el sistema HAx = Hb sera
(TO
)x =
(b1b2
), con lo que la
seudosolucion sera la solucion de Tx = b1 y el error sera ‖b2‖.
Determinacion de autovalores, cociente de Rayleigh, potencia simple,potencia inversa.
• Vamos a comenzar, por ello, a estudiar como podemos aproximar elautovalor correspondiente a un determinado autovector cuando lo queconocemos es una aproximacion de este.
3si en el ejemplo anterior modificamos el sistema inicial haciendo F31(−1) y resolvemospor medio de las ecuaciones normales, la solucion obtenida es m = −2/3, n = 3.
28
Dada una matriz cuadrada A y un vector x, se denomina cociente deRayleigh del vector x respecto de la matriz A al cociente
x∗Ax
x∗x.
• Metodo de la potencia simple
Sea A una matriz diagonalizable y supongamos que sus autovaloresverifican que:
|λ1| > |λ2| ≥ · · · ≥ |λn|
en cuyo caso diremos que λ1 es el autovalor dominante de la matriz.
Sea B = {x1, x2, · · · , xn} una base formada por autovectores asociadosa λ1, λ2, . . . , λn respectivamente. Se verifica entonces que
Akxi = λki xi para cualquier i = 1, 2, . . . , n
Dado un vector z0 se define, a partir de el, la sucesion (zn) con
zn = Azn−1 = A2zn−2 = · · · = Anz0.
Si las coordenadas del vector z0 respecto de la base B son (α1, α2, . . . , αn)se tiene que z0 = α1x1 + α2x2 + · · ·+ αnxn, por lo que
que es un autovector de A asociado al autovalor λ1.
29
Si k es suficientemente grande, se tiene
Azk = zk+1 ≈ λk+11 α1x1 = λ1(λ
k1α1x1) = λ1zk
por lo que la sucesion (zn) nos proporciona un metodo para aproximarel autovalor λ1.
El metodo no convergera a un vector en concreto ya que
zk+1 ≈ λ1zk 6= zk.
Ahora bien, dado que zk+1 y zk tienen la misma direccion, ambosrepresentan al autovector buscado.
Escalado
Si |λ1| > 1 la sucesion (zn) converge a una direccion determinada (ladel autovector), pero las normas de los vectores van creciendo llegandoa diverger a un vector de coordenadas infinitas. Si, por el contrario,|λ1| < 1, la sucesion (zn) converge al vector nulo. Es decir: en ningunode los dos casos podremos calcular ni el autovalor ni el autovector.
Como solo nos interesa la direccion y los vectores de la sucesion (zn)convergen a una determinada direccion, podemos dividir o multiplicaren cada paso el vector zk por una constante sin que ello modifique sudireccion. Con ello conseguiremos que la sucesion (zn) converja a unautovector asociado a λ1. Este proceso de modificar las normas de losvectores recibe el nombre de escalado.
Ejemplo: Sea la matriz A =
1 2 52 2 35 3 6
.
Si elegimos como vector inicial z0 = (1, 0, 0)t obtenemos una sucesionzn = Azn−1
z0, z1 =
125
, z2 =
302141
, z3 =
277255459
, z4 =
302223814814
. . .
Y una sucesion de cocientes de Rayleigh4 1, 9.23, 10.54, 10.59, 10.60,que converge rapidamente al autovalor dominante, 10.6001870845
4Estos cocientes son invariantes por escalado, pero la necesidad del mismo se haceevidente al observar el crecimiento de la norma infinito en la sucesion de vectores zn
