´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

An´alisis Num´erico M´etodos directos para la resoluci´on de sistemas lineales CNM-425 Departamento de Matem´ aticas Facultad de Ciencias Exactas y Naturales Universidad de Antioquia

©

2010. Reproducci´ on permitida bajo los Copyleft t´ erminos de la licencia de documentaci´ on libre GNU.

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Contenido

1

´ Algebra de matrices

2

Sistemas de ecuaciones lineales

3

Factorizaci´ on de matrices

4

Pivoteo

Factorizaci´ on de matrices

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Notaci´on Definici´ on 1.1 Escalares: n´ umeros reales o complejos, los denotamos en min´ usculas: a, b, c, x, y, z... Matrices: arreglos rectangulares de escalares, las denotamos en negrilla: A, B, C, X, Y, Z, u, v . . .

2

6 6 6 6 A=6 6 6 6 4

a11 a21 .. . ai1 .. . am1

a12 a22 .. . ai2 .. . am2

··· ··· ··· ···

a1j a2j .. . aij .. . amj

··· ··· ··· ···

a1n a2n .. . ain .. . amn

3 7 7 7 7 7 7 7 7 5

⇐⇒

A = [aij ]m×n i : f ila j : columna

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Matrices en Octave Ejemplo: 2

2 A=4 1 −2

En Octave:

3 0 4

5 3 6

3 −3 7 5 0

=⇒

a11 = 2, a14 = −3, a34 = 0, etc.

octave:#> A = [2 3 5 -3; 1 0 3 7; -2 4 6 0] A = 2 3 5 -3 1 0 3 7 -2 4 6 0 octave:#> A(1,1) ans = 2

octave:#> A(3,1) ans = -2

octave:#> A(1,4) ans = -3

octave:#> A(1,3) ans = 5

octave:#> A(3,4) ans = 0

octave:#> A(2,1)-A(1,3)*A(2,4) ans = -34

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Notaci´on Definici´ on 1.2 vector columna: matrices que consisten de una sola columna vector fila: matrices que consisten de una sola fila vector: vector columna

octave:#> x = [8 6 -4 7] x = 8 6 -4 7

octave:#> y = [1; 6; 8] y = 1 6 8

octave:#> x(1,3) ans = -4

octave:#> x(3) ans = -4

octave:#> x(3,1) error: invalid row index = 3

octave:#> y(2,1) ans = 6

octave:#> y(2) ans = 6

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Definici´ on 1.3 (Igualdad de matrices) Dos matrices A = [aij ]m×n y B = [bij ]p×q son iguales si tienen el mismo as n´ umero de filas (m = p) y columnas (n = q), y adem´ aij = bij , octave:#> x x = 8 6 -4

7

octave:#> y y = 1 6 8 octave:#> x == y error: mx el eq: nonconformant arguments (op1 is 1x4, op2 is 3x1) octave:#> z = [8 -6 4 7] z = 8 -6 4 7

para todo i, j octave:#> x == z ans 1 0 0 1

octave:#> z(2)=6; z(3)=-4;

octave:#> z z = 8 6 -4

7

octave:#> x == z ans 1 1 1 1

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Comandos para manipulaci´on de arreglos Comando inicio:incremento:final linspace(inicio,final,n) zeros(m,n) ones(m,n) rand(m,n) magic(n) eye(n)

Descripci´ on Crea Crea Crea Crea Crea Crea Crea

vector fila con sus elementos igualmente espaciados vector fila con n elementos igualmente espaciados matriz de puros ceros con m filas y n columnas matriz de puros unos con m filas y n columnas matriz m×n con entradas aleatorias “cuadrado m´ agico” n×n la matriz identidad n×n

octave:#> a = 0:0.25:1 a = 0.00000 0.25000 0.5000

0.75000

1.00000

octave:#> b = linspace(0,1,5) a = 0.00000 0.25000 0.5000 0.75000

1.00000

octave:#> c = zeros(3,2) c = 0 0 0 0 0 0

octave:#> u = ones(2,3) u = 1 1 1 1 1 1

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Comandos para manipulaci´on de arreglos Comando inicio:incremento:final linspace(inicio,final,n) zeros(m,n) ones(m,n) rand(m,n) magic(n) eye(n)

Descripci´ on Crea Crea Crea Crea Crea Crea Crea

vector fila con sus elementos igualmente espaciados vector fila con n elementos igualmente espaciados matriz de puros ceros con m filas y n columnas matriz de puros unos con m filas y n columnas matriz m×n con entradas aleatorias “cuadrado m´ agico” n×n la matriz identidad n×n

octave:#> r = rand(2,3) r = 0.75845 0.54151 0.33671 0.33042 0.11906 0.31983

octave:#> unos = ones(3) unos = 1 1 1 1 1 1 1 1 1

octave:#> m = magic(3) m = 8 1 6 3 5 7 4 9 2

octave:#> id = eye(3) id = 1 0 0 0 1 0 0 0 1

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Funciones sobre arreglos Funci´ on length(x) [m.n] = size(X) reshape(X,m,n) max(x) max(X) min(x) min(X)

Descripci´ on Retorna Retorna Retorna Retorna Retorna Retorna Retorna

octave:#> t = 1:6 u = 1 2 3 4 5 6 octave:#> length(t) ans = 6 octave:#> u u = 1 1 1 1 1 1 octave:#> [m,n] = size(u) m = 2 n = 3

el n´ umero de elementos de un vector x el n´ umero de filas y columnas de una matriz X una matriz m×n con elementos tomados de X el mayor elemento de un vector x vector fila con los elementos mayores de cada columna de X el menor elemento de un vector x vector fila con los elementos menores de cada columna de X

octave:#> Q = reshape(t,2,3) Q = 1 3 5 2 4 6 octave:#> max(Q) ans = 2 4 6 octave:#> max(max(Q)) ans = 6 octave:#> min(min(Q)) ans = 1

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Notaci´on 2

6 6 6 6 A=6 6 6 6 4

a11 a21 .. . ai1 .. . am1

··· ···

a12 a22 .. . ai2 .. . am2

··· ···

a1j a2j .. . aij .. . amj

··· ··· ··· ···

a1n a2n .. . ain .. . amn

3 7 7 7 7 7 7 7 7 5

⇐⇒

A = [aij ]m×n

Fila i-´esima de A: Ai∗ =

ˆ

ai1

ai2

···

Columna j-´esima de 2 a1j 6 a2j 6 A∗j = 6 . 4 .. anj

A: 3 7 7 7 5

ain

˜

octave:#> A(i,:)

octave:#> A(:,j)

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Comandos para extraer elementos de un arreglo Comando A(i,:) A(:,j) A(:) A(j:k) A(:,j:k) A(i,[1:i-1,i+1:n])

octave:#> A A = 2 3 5 -3 1 0 3 7 -2 4 6 0 octave:#> A(1,:) ans = 2 3 5 -3 octave:#> A(:,2) ans = 3 0 4

Descripci´ on Fila i-´ esima de A Columna j-´ esima de A Retorna una columna con todos los elementos de A Retorna A(j), A(j+1), . . . , A(k) Retorna A(:,j), A(:,j+1), . . . , A(:,k) Retorna la fila i-´ esima sin el elemento A(i,i)

octave:#> A(:) ans = 2 1 -2 3 0 4 5 3 6 -3 7 0 octave:#> A(3) ans = -2

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Comandos para extraer elementos de un arreglo Comando A(i,:) A(:,j) A(:) A(j:k) A(:,j:k) A(i,[1:i-1,i+1:n])

octave:#> A A = 2 3 5 -3 1 0 3 7 -2 4 6 0 octave:#> A(:,2:4) ans = 3 5 -3 0 3 7 4 6 0 octave:#> A(1:2,:) ans = 2 3 5 -3 1 0 3 7

Descripci´ on Fila i-´ esima de A Columna j-´ esima de A Retorna una columna con todos los elementos de A Retorna A(j), A(j+1), . . . , A(k) Retorna A(:,j), A(:,j+1), . . . , A(:,k) Retorna la fila i-´ esima sin el elemento A(i,i)

octave:#> A(2,[1:1,3:4]) ans = 1 3 7

octave:#> A([1:1,3:3],3) ans = 5 6

octave:#> A(2:3,1:2) ans = 1 0 -2 4

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

´ Algebra de matrices Definici´ on 1.4 (Suma de matrices) Si A y B son matrices m × n, la suma de A y B es la matriz m × n que se obtiene al sumar las entradas correspondientes de cada matriz, i.e., A + B = [aij + bij ] octave:#> X = [1 0 -1; 2 -3 5] X = 1 0 -1 2 -3 5 octave:#> Y = [-2 3 1; 2 4 -5] Y = -2 3 1 2 4 -5 octave:#> X+Y ans = -1 3 0 4 1 0

octave:#> A A = 2 3 5 -3 1 0 3 7 -2 4 6 0

octave:#> A+X ans = error: operator +: nonconformant arguments (op1 is 3x4, op2 is 2x3) error: evaluating binary operator ‘+’ near line 41, column 2

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

´ Algebra de matrices Definici´ on 1.5 (Multiplicaci´ on por escalar) Si A es una matriz m × n y α un esclar, el producto de α por A es la matriz m × n que se obtiene al multiplicar cada entrada de A por α, i.e., αA = [αaij ] octave:#> X X = 1 0 -1 2 -3 5

octave:#> 2*X ans = 2 0 -2 4 -6 10

octave:#> Y Y = -2 3 1 2 4 -5

octave:#> -3*Y Y = 6 -9 -3 -6 -12 15

octave:#> X-Y ans = 3 -3 -2 0 -7 10

octave:#> 2*X-3*Y ans = 8 -9 -5 -2 -18 25

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

´ Algebra de matrices Definici´ on 1.6 (Transpuesta de una matriz) Si A es una matriz m × n, su transpuesta, denotada por AT es la matriz n × m que se obtiene al intercambiar filas por columnas en A, i.e., A = [aij ] =⇒ AT = [aji ]

octave:#> M = [1 2; 3 4; 5 6] M = 1 2 3 4 5 6

octave:#> M’ ans = 1 3 5 2 4 6

octave:#> N = [1; 3; 0; 5] N = 1 3 0 5

octave:#> transpose(N) ans = 1 3 0 5

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

´ Algebra de matrices Definici´ on 1.7 (Definici´ on de matriz adjunta) Para una matriz A = [aij ], su conjugada est´ a definida por A = [ aij ]. La matriz transpuesta de A, denotada por A∗ , es la transpuesta de la conjugada, i.e., T A∗ = A

»

1 − 4i 3

i 2+i

octave:#> P = [1-4i i 2; 3 2+i 0] P = 1 - 4i 0 + 1i 2 + 0i 3 + 0i 2 + 1i 0 + 0i

2 0

–∗

2

1 + 4i = 4 −i 2

3 3 2−i 5 0

octave:#> ctranspose(P) P = 1 + 4i 3 - 0i 0 - 1i 2 - 1i 2 - 0i 0 - 0i

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Definiciones Definici´ on 1.8 (Propiedades de la transpuesta) Si A y B son matrices del mismo tama˜ no y α es un escalar, entonces (A + B)T = AT + BT (αA)T = αAT

y (A + B)∗ = A∗ + B∗ y (αA)∗ = αA∗

Observaciones Para escalares reales los conceptos de transpuesta y adjunta son los mismos A∗ = AT . Algunas veces la transposici´ on no cambia nada. Por ejemplo, si 0

1 A=@ 2 3

2 4 5

1 3 5 A, 6

entonces

AT = A.

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Definiciones

Matriz diagional 2 λ11 0 6 0 λ22 6 D=6 . .. 4 .. . 0 0

··· ··· .. . ···

0 0 .. . λnn

3 7 7 7 5

octave:#> D = diag ([1, 2, 3]) D = 1 0 0 0 2 0 0 0 3

Matrices diagonales son sim´etricas: D = DT

octave:#> D’ ans = 1 0 0 0 2 0 0 0 3

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

´ Algebra de matrices Definici´ on 1.9 (Simetr´ıas) Sea A = [aij ] una matriz cuadrada. A es una matriz sim´ etrica si AT = A A es una matriz anti-sim´ etrica si AT = −A A es una matriz hermitiana si A∗ = A A es una matriz anti-hermitiana si A∗ = −A

octave:#> transpose(A)- A ans = 0 + 0i 0 - 8i 0 + 6i

octave:#> ctranspose(A)- A ans = 0 - 0i 0 + 0i 0 + 0i

octave:#> A = [1 2+4i 1-3i; 2-4i 3 8+6i; 1+3i 8-6i 5] A = 1 + 0i 2 + 4i 1 - 3i 2 - 4i 3 + 0i 8 + 6i 1 + 3i 8 - 6i 5 + 0i

octave:#> B = [1 2+4i 1-3i; 2+4i 3 8+6i; 1-3i 8+6i 5] B = 1 + 0i 2 + 4i 1 - 3i 2 + 4i 3 + 0i 8 + 6i 1 - 3i 8 + 6i 5 + 0i

0 + 8i 0 - 6i 0 + 0i 0 + 12i 0 - 12i 0 + 0i

0 + 0i 0 - 0i 0 + 0i

0 + 0i 0 + 0i 0 - 0i

octave:#> transpose(B)- B ans = 0 0 0

0 0 0

0 0 0

octave:#> ctranspose(B)- B ans = 0 + 0i 0 - 8i 0 + 6i

0 - 8i 0 + 6i 0 - 0i 0 - 12i 0 - 12i 0 - 0i

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Producto de matrices Definici´ on 1.10 (Producto interno) Si x=

ˆ

x1 . . . xn

˜

y

2

3 y1 6 . 7 y = 4 .. 5 , yn

entonces el producto interno de x por y est´ a dado por xy := x1 y1 + x2 y2 + · · · + xn yn =

n X

x i yi .

i=1

Observaciones x debe ser 1 × n e y debe ser n × 1 y el resultado es un escalar: x1×n yn×1 = [ · ]1×1 = escalar Ejemplo: ˆ

2

4

−2

˜

2

3 1 4 2 5 = (2)(1) + (4)(2) + (−2)(3) = 4 3

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Producto de matrices Definici´ on 1.11 (Producto de matrices) Si A = [aij ]m×p

y

B = [aij ]p×n ,

entonces el producto de A por B es una matriz C = [cij ]m×n cuya entrada cij viene dada por el producto interno de la i-´esima fila de A con la j-´esima columna de B, i.e., 3 2 b1j p 7 ˜6 ˆ 6 b2j 7 X aik bkj . cij = ai1 ai2 . . . aip 6 . 7 = 4 .. 5 k=1 bpj Observaciones El n´ umero de columnas de A debe coincidir con el n´ umero de filas de B:

Am×p Bp×n = Cm×n

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Producto de matrices Operaci´ on

Matriz

Elemento a elemento

Multiplicaci´ on Potencia

∗ ∧

.∗ .∧

octave:#> x = [2 4 -2]; octave:#> y = [1; 2; 3];

octave:#> x*y ans = 4

octave:#> S = y*x S = 2 4 -2 4 8 -4 6 12 -6

octave:#> T = [1 2 3; 3 4 5] T = 1 2 3 4 5 6

octave:#> S*T ans = 28 56 -28 52 104 -52

octave:#> T*S ans = error: operator *: nonconformant arguments (op1 is 3x3, op2 is 2x3) error: evaluating binary operator ‘*’ near line 111, column 2

octave:#> x.*x ans = 4 16 4 octave:#> x.∧2 ans = 4 16 4

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Producto de matrices Proposici´ on 1.1 (Propiedades de la suma y producto) Si A, B y C tienen las dimensiones adecuadas, A+B = B+A A(B + C) = AB + AC A(BC) = (AB)C IA = AI = A λ(AB) = (λA)B = A(λB)

Observaci´ on Si A, B y C son matrices n × n, AB 6= BA AB = AC ; B = C

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Inversa de una matriz Equivalencia entre sistemas lineales y matrices: – – » –» » 3 x1 1 −4 x1 − 4x2 = 3 = ⇐⇒ 1 3 7 x2 3x1 + 7x2 = 1 Para un sistema m × n: a11 x1 a21 x1 .. . an1 x1

+ + +

a12 x2 a22 x2 .. . an2 x2

+ + +

··· ··· .. . ···

+ +

= =

a1n xn a2n xn .. . ann xn

+

=

b1 b2 .. . bn

⇐⇒

3

2

Ax = b

donde 2

6 6 A=6 4

a11 a21 .. . an1

a12 a22 .. . an2

··· ··· .. . ···

a1n a2n .. . ann

3

2

7 6 7 6 7, x = 6 5 4

x1 x2 .. . xm

7 6 7 6 7, b = 6 5 4

b1 b2 .. . bm

3 7 7 7 5

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Inversa de una matriz Definici´ on 1.12 (Inversa de una matriz) An×n es una matriz no singular si existe una matriz Bn×n tal que AB = BA = I

(1)

Observaciones Si A es no singular, la matriz B que satisface (1) es u ´nica A la matriz B se le denomina inversa de A A la inversa de A se le denota por A−1 Ejemplo A= porque

»

1 1

AA−1 =

2 3 »

1 1

–

=⇒

2 3

–»

A−1 =

3 −1

−2 1

» –

3 −1

=

»

1 0

−2 1

–

0 1

–

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Inversa de una matriz

Proposici´ on 1.2 (Propiedades) Sea A una matriz no singular n × n. Entonces: A−1 es no singular y su inversa satisface ` −1 ´−1 A =A

Si B es una matriz n × n no singular, AB es no singular y (AB)−1 = B−1 A−1

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Sistemas de ecuaciones Problema: calcular (si es posible) una soluci´ on del sistema de m ecuaciones lineales algebraicas y n inc´ ognitas a11 x1 a21 x1 .. . am1 x1

+ + +

a12 x2 a22 x2 .. . am2 x2

+ + +

··· ··· .. . ···

+ + +

a1n xm a2n xm .. . amn xm

= = =

b1 b2 .. . bm

(2)

Tres posibilidades: Soluci´ on u ´ nica: existe uno y s´ olo un conjunto de valores x1 , x2 , . . . , xn que satisfacen (2) No existe soluci´ on: no existe un conjunto de x′i s que satisfagan simult´ aneamente las ecuaciones de (2) Infinitas soluciones: existen infinitos conjuntos de x′i s que satisfacen simult´ aneamente las ecuaciones de (2)

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Sistemas de ecuaciones Ecuaci´ on i-´esima del sistema (2) Ei : ai1 x1 + ai2 x2 + · · · + ain xm = bi

(3)

El sistema (2) se puede escribir como

Dos sistemas 8 E1 > > > < E2 S= .. > > . > : En

8 E1 > > > < E2 S= .. > > . > : En

9 > > > =

9 > > > =

8 ′ E1 > > > < E2′ S′ = .. > > . > : ′ En

> > > ;

y

> > > ;

son equivalentes si tienen las mismas soluciones

9 > > > = > > > ;

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Sistemas de ecuaciones

Proposici´ on 2.1 (Operaciones elementales) Dado un sistema lineal S, las siguientes operaciones elementales transforman a S en un sistema equivalente S ′ : 1

Intercambiar la ecuaci´ on i-´esima por la ecuaci´ on j-´esima: Ei ←→ Ej

2

Reemplazar la ecuaci´ on i-´esima por un m´ ultiplo no nulo de si misma: λEi −→ Ei ,

3

λ 6= 0

Reemplazar la ecuaci´ on i-´esima por una combinaci´ on de si misma y un m´ ultiplo no nulo de la ecuaci´ on j-´esima: Ei + λEj −→ Ei ,

λ 6= 0

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on Gaussiana Ejemplo 2.1 Emplee operaciones elementales para resolver el sistema lineal 2x1 6x1 −2x1

+ + +

x2 2x2 2x2

+ + +

x3 x3 x3

= = =

1 −1 7

(4)

Soluci´ on 2x1 6x1 −2x1

+ + +

x2 2x2 2x2

E3 + E1 −→ E3 −→

2x1

+

x2 −1 x2

+ + +

2x1

+ − −

= = =

x3 x3 x3 +

x3 2x3 4x3

1 −1 7 x2 −1 x2 3x2

= = =

1 −4 −4

E2 − 3E1 −→ E2 −→

+ − +

x3 2x3 2x3

= = =

1 −4 8

2x1 −2x1

+ − +

x2 2x2 2x2

3E2 + E3 −→ E3 −→

+ + +

x3 x3 x3

= = =

1 −1 7

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on Gaussiana El sistema (16) es equivalente al sistema 2x1

+

x2 x2

+ − −

x3 2x3 4x3

= = =

1 −4 −4

El sistema (5) es triangular y se resuelve por sustituci´ on hacia atr´ as: x3 = 1 x2

=

x1

=

4 − 2x3 = 4 − 2(1) = 2 1 1 (1 − x2 − x3 ) = (1 − 2 − 1) = −1 2 2

Procedimiento desarrollado: eliminaci´ on Gaussiana N´ umero de operaciones realizadas para un sistema n × n: n3 3 3

n 3

+ n2 − +

2

n 2

−

n 3

multiplicaciones/divisiones

5n 6

sumas/restas

(5)

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on Gaussiana Representaci´ on matricial a11 x1 a21 x1 .. . an1 x1

+ + +

a12 x2 a22 x2 .. . an2 x2

+ +

··· ··· .. . ···

+

+ + +

= =

a1n xn a2n xn .. . ann xn

=

b1 b2 .. . bn

⇐⇒

Ax = b

donde 2

6 6 A=6 4

a11 a21 .. . an1

a12 a22 .. . an2

··· ··· .. . ···

a1n a2n .. . ann

Matriz aumentada del sistema 2 6 6 [A|b] = 6 4

3

2

7 7 7, 5

a11 a21 .. . an1

6 6 x=6 4

a12 a22 .. . an2

··· ··· .. . ···

x1 x2 .. . xn

a1n a2n .. . ann

3 7 7 7 5

y

3 b1 b2 7 7 7 b3 5 b4

2

6 6 b=6 4

b1 b2 .. . bn

3 7 7 7 5

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Algoritmo Eliminaci´on Gaussiana Fase de eliminaci´ on 2

a11 6 a21 6 6 . 4 .. an1 |

a12 a22 .. . an2

··· ··· .. . ··· {z

a1n a2n .. . ann

b1 b2 .. . bn

3 7 7 7 5

aij − λakj −→ aij bi − λbk −→ bi −→ j = k, k + 1, . . . , n

}

[A|b]

2 6 6 6 4

a′11 0 .. . 0

a′12 a′22 .. . 0

|

[A′ |b′ ]

for j = 1:n-1 for i = j+1:n if A(i,j) != 0

% para evitar dividir por 0

lambda = A(i,j)/A(j,j); A(i,j+1:n) = A(i,j+1:n) - lambda*A(j,j+1:n); b(i)= b(i) - lambda*b(j); end end end

··· ··· .. . ··· {z

a′1n a′2n .. . ′ ann

b′1 b′2 .. . b′n

3 7 7 7 5

}

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Algoritmo Eliminaci´on Gaussiana Fase de sustituci´ on hacia atr´ as: 2 6 6 6 4

a′11 0 .. . 0

a′12 a′22 .. . 0

a′n x′n = b′n

a′ii x′i

+

a′i,i+1 x′i+1

+··· +

a′in x′n

=

b′i

··· ··· .. . ···

a′1n a′2n .. . a′nn

b′1 b′2 .. . b′n

=⇒

x′n =

=⇒

x′i

=

3 7 7 7 5

b′n a′nn b′i

−

n X

j=i+1

for = n:-1:1 x(i) = (b(i) - A(i,i+1:n)*x(i+1:n))/A(i,i); end

a′ij x′j

!

1 a′ii

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on Gaussiana

gauss.m

function x = gauss(A,b) % Resuelve sistema A*x=b por eliminaci´ on Gaussiana n = length(b); x = zeros(n,1); for j = 1:n-1 % fase de eliminaci´ on for i = j+1:n if A(i,j) != 0 lambda = A(i,j)/A(j,j); A(i,j+1:n) = A(i,j+1:n) - lambda*A(j,j+1:n); b(i)= b(i) - lambda*b(j); end end end % fase sustituti´ on hacia atr´ as for i = n:-1:1 x(i) = (b(i) - A(i,i+1:n)*x(i+1:n))/A(i,i); end end

octave:#> A = [2 1 1; 6 2 1; -2 2 1]; octave:#> b = [1; -1; 7] octave:#> gauss(A,b) ans = -1 2 1

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on Gaussiana Ejemplo 2.2 (Infinitas soluciones) Utilice eliminaci´ on Gaussiana para resolver el sistema x 2x x

+ + +

y 2y y

+ + +

4 z 2z

= = =

4 6 6

Soluci´ on 2

1 4 2 1

1 2 1

1 1 2

3 4 6 5 6

E2 − 2E1 −→ E2 −→

=⇒

octave:#> A = [2 1 1; 6 2 1; -2 2 1]; A =

2

1 4 0 0

1 0 0

1 −1 1

x+y+z −z z

Soluci´ on = {(x, 2 − x, 2)|x ∈ R}

= = =

3

4 −2 5 2 4 −2 2

2 6 -2

1 2 2

1 1 1

octave:#> b = [4; 6; 6] b = 4 6 6 octave:#> gauss(A1,b1) ans = Nan Nan 2

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Eliminaci´on Gaussiana Ejemplo 2.3 (Sin soluci´ on) Utilice eliminaci´ on Gaussiana para resolver el sistema x 2x x

+ + +

y 2y y

+ + +

4 z 2z

= = =

4 4 6

Soluci´ on 2

1 4 2 1

1 2 1

1 1 2

3 4 4 5 6

E3 − E1 −→ E3 −→

=⇒

octave:#> b2 = [4; 4; 6] b = 2

1 4 0 0

1 0 0

x+y+z −z z Soluci´ on = ∅

1 −1 1 = = =

3 4 −4 5 2 4 −4 2

4 4 6 octave:#> gauss(A1,b2) ans = Inf -Inf 2

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on de Gauss-Jordan Variaci´ on del m´etodo de eliminaci´ on Gaussiana En cada paso, el elemento pivote es forzado a ser 1 En cada paso, los t´erminos por encima y por debajo del pivote son eliminados La soluci´ on (en caso de existir) aparece en la u ´ltima columna 2 6 6 6 4

|

a11 a21 .. . an1

a12 a22 .. . an2

··· ··· .. . ··· {z

[A|b]

a1n a2n .. . ann

b1 b2 .. . bn

3 7 7 7 5

}

Operaciones elementales −→

2 6 6 6 4 |

1 0 .. . 0

0 1 .. . 0

··· ··· .. . ··· {z

[I|s]

0 0 .. . 1

s1 s2 .. . sn

3 7 7 7 5

}

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on de Gauss-Jordan Ejemplo 2.4 Utilice el m´etodo de Gauss-Jordan para resolver el sistema lineal 2x1 2x1 −2x1

+ + −

2x2 x2 6x2

+ + −

6x3 7x3 7x3

= = =

4 6 −1

(6)

Soluci´ on 2 4

2 2 −2

2 1 −6

6 7 −7

2

1 4 0 0

1 −1 −4

2

1 4 0 0

0 1 0

4 −1 −5

2

0 1 0

0 0 1

1 4 0 0

3 1 −1

3 4 6 5 −1 3 2 2 5 3

3 4 −2 5 −5 3 0 −1 5 1

−E2 −→ E2 −→

− 1 E3 −→ E3 5 −→

=⇒

2

1 E −→ E 1 2 1 −→

2

4

2

1 4 0 0 2

1 4 0 0

3 2 6 5 −1

1 2 −2

1 1 −6

3 7 −7

1 1 −4

3 −1 −1

3 2 −2 5 3

E1 − E2 −→ E1 E3 + 4E2 −→ E3 −→

0 1 0

4 −1 1

3 4 −2 5 1

E1 − 4E3 −→ E1 E2 + E3 −→ E2 −→

3 2 3 x1 0 4 x2 5 = 4 −1 5 x3 1

E2 − 2E1 −→ E2 E3 + 2E1 −→ E3 −→

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Inversa de una matriz Sistema lineal n × n: a11 x1 a21 x1 .. . an1 x1

+ +

a12 x2 a22 x2 .. . an2 x2

+

+ + +

··· ··· .. . ···

+ + +

a1n xn a2n xn .. . ann xn

= = =

b1 b2 .. . bn

⇐⇒

Ax = b

Si A es no singular, Ax = b

=⇒ =⇒ =⇒

A−1 (Ax) = A−1 b ` −1 ´ A A x = A−1 b

octave:#> A\b

x = A−1 b

Retomando el ejemplo anterior: x1 + 2x2 = 2 ⇐⇒ Ax = b x1 + 3x2 = −1 – » x1 = A−1 b x2 – – » –» » 8 2 3 −2 = = −3 −1 −1 1

octave:#> A2 = [1 2; 1 3]; octave:#> b3 = [2 -1]; octave:#> gauss(A2,b3) ans = 8 -3

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Inversa de una matriz Proposici´ on 2.2 (Propiedades) Sea A una matriz no singular n × n. Entonces: A−1 es no singular y su inversa satisface ` −1 ´−1 A =A

Si B es una matriz n × n no singular, AB es no singular y (AB)−1 = B−1 A−1 ¿C´ omo distinguir las matrices no singulares de las singulares? Proposici´ on 2.3 (Existencia de la inversa) Sea A una matriz n × n. Los siguientes enunciados son equivalentes: A−1 es no singular (su inversa existe) A

Gauss−J ordan −−−−−−−−−>

Ax = 0

=⇒

I

x=0

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Proposici´ on 2.4 (Filas y columnas de un producto) Suponga A una matriz m × p y B una matriz p × n. [AB]i∗ = [A]i∗ B [AB]∗j = A[B]∗j [AB]i∗ = ai1 [B]1∗ + ai2 [B]2∗ + · · · + aip [B]p∗ [AB]∗j = [A]∗1 b1j + [A]∗2 b2j + · · · + [A]∗p bpj Ejemplo AB =

»

1 3

−2 −4

[AB]2∗ = [A]2∗ B =

ˆ

0 5

3

–

2

3 4 2 1

−4

[AB]∗j = A[B]∗j =

»

5

1 3

−5 −7 −2

˜

2

3 4 2 1

−2 −4

3 » 1 −1 2 5= 6 0 −5 −7 −2 2 – 0 4 5

9 3

−3 −5

3 1 ˆ 2 5= 6 3 0 3 – » −5 9 5 −7 = 3 −2

–

−5

˜

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Ecuaci´ones con matrices Proposici´ on 2.5 (Ecuaci´ ones con matrices) Si A una matriz n × n no singular, entonces la ecuaci´ on An×n Xn×p = Bn×p

(7)

tiene soluci´ on u ´nica y est´ a dada por X = A−1 B

(8)

Observaciones Resolver la ecuaci´ on matricial (7) es equivalente a resolver los p sistemas lineales Ax = B1∗ ,

Ax = B2∗ , . . . , Ax = Bp∗

Si X∗j es la soluci´ on del sistema j-´esimo en (9), X = [X∗1 |X∗2 | · · · |X∗p ]

(9)

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Ecuaci´ones con matrices Algoritmo para hallar la inversa Hallar A−1

⇐⇒

Resolver AX = I

⇐⇒

Resolver AX = I∗i

para j = 1, . . . , n. Para el sistema j-´esimo aplicamos Gauss-Jordan 2

a11 6 a21 6 6 . 4 .. an1 |

a12 a22 .. . an2

··· ··· .. . ··· {z

a1n a2n .. . ann

0 1 .. . 0

3 7 7 7 5

operaciones elementales

−→

6 6 6 4

1 0 .. . 0

0 1 .. . 0

|

}

[A|I∗j ]

2

··· 0 ··· 0 . .. . .. ··· 1 {z [I|X∗j ]

x1j x2j .. . xnj

3 7 7 7 5 }

Aplicando Gauss-Jordan simult´ aneamente a los n sistemas: 2 6 6 6 4 |

a11 a21 . .. an1

a12 a22 . .. an2

··· ··· .. . ···

a1n a2n . .. ann {z

[A|I]

1 0 . .. 0

0 1 . .. 0

... ... .. . ...

3 2 0 0 7 Gauss 6 7Jordan6 7 −→ 6 4 0 5 1

}

|

1 0 . .. 0

0 1 . .. 0

··· ··· .. . ···

0 0 . .. 1

x11 x21 . .. xn1 {z

[I|A−1 ]

x12 x22 . .. xn2

... ... .. . ...

x1n x2n . .. xnn

3 7 7 7 5

}

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Proposici´ on 2.6 (C´ omputo de la inversa) Dado A una matriz n × n, el m´etodo de eliminaci´ on de Gauss-Jordan puede ser utilizado para hallar la inversa de A en caso de existir: [A|I]

Gauss-Jordan −→

Observaciones

ˆ

I|A−1

˜

(10)

El algoritmo (10) falla cuando en lugar de la identidad I se obtiene una matriz con una fila de ceros (A es singular) Debido a la cantidad de c´ alculos involucrados, el algoritmo (10) no tiene aplicaciones pr´ acticas (sino te´ oricas): n3 productos/divisiones

n3 − 2n2 + n sumas/restas

Resolver el sistema Ax = b, calculando primero A−1 y luego A−1 b requiere n3 + n2 productos/divisiones

n3 − n2 sumas/restas

Eliminaci´ on Gaussiana con sustituci´ on hacia atr´ as requiere alrededor 3 3 de n3 productos/divisiones y n3 sumas/restas

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Determinantes Definici´ on 2.1 (Ecuaciones con matrices) Si A = [a], entonces det A = a Si A es n × n, el menor Mij asociado a A es el determinante de la submatriz (n − 1) × (n − 1) que se obtiene al subprimir la fila i-´esima y la columna j-´esima de A El cofactor Aij se define como Aij = (−1)i+j aij Mij Si A es n × n con n > 1, su determinante est´ a dado por det A =

n X

aij Aij =

j=1

n X

(−1)i+j aij Mij

(11)

(−1)i+j aij Mij

(12)

j=1

o tambi´en por det A =

n X i=1

aij Aij =

n X i=1

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on Gaussiana Ejemplo 2.5 Calcule el determinante de 2

2 6 4 A=6 4 −3 6

−1 −2 −4 −6

3 7 1 8

3 0 0 7 7 5 5 0

Soluci´ on det A

=

−0M14 + 0M24 − 5M34 + 0M44

=

−5M34 2

=

= =

2 −5 det 4 4 6 „ » −5 2 det −30

−1 −2 −6 −2 −6

3 3 7 5 8 – » 7 4 − (−1) det 8 6

7 8

–

+ 3 det

»

4 6

−2 −6

–«

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Propiedades

Proposici´ on 2.7 (Efectos de las operaciones elementales) Sea B la matriz que se obtiene de A por medio de alguna de las operaciones elementales: Tipo I: Ei ←→ Ej Tipo II: αEi −→ Ei , α 6= 0 Tipo III: λEi + Ej −→ Ej Entonces: det B = − det A si B se obtuvo de operaciones del tipo I det B = α det A si B se obtuvo de operaciones del tipo II det B = det A si B se obtuvo de operaciones del tipo III

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Propiedades

Proposici´ on 2.8 (Otras propiedades) Sean A y B matrices n × n det At = det A det(AB) = det A det B ` ´ Si A es no singular, det A−1 = (det A)−1

Si A = [aij ] es triangular (superior o inferior) o diagonal, entonces det A =

n Y

i=1

aii

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Relaci´ on entre no singularidad y determinantes

Proposici´ on 2.9 (Propiedades) Sea A una matriz n × n. Los siguientes enunciados son equivalentes: La matriz A es no singular det A = 0 La ecuaci´ on Ax = 0 tiene soluci´ on u ´nica x = 0 El sistema Ax = b tiene soluci´ on u ´nica para todo vector b Eliminaci´ on Gaussiana con intercambio de filas puede realizarse en el sistema Ax = b para todo vector b

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Factorizaci´ on de matrices Descomposici´ on de una matriz como producto de matrices en alguna “forma can´ onica” La factorizaci´ on permite expresar una matriz como producto de matrices m´ as “sencillas” Seg´ un las aplicaciones se tiene: Factorizaci´ on LU Factorizaci´ on de Cholesky Factorizaci´ on QR

M´ etodo

Forma inicial

Forma final

Eliminaci´ on Gaussiana Eliminaci´ on Gauss-Jordan Factorizaci´ on LU

Ax = b Ax = b Ax = b

Ux = b Ix = b LUx = b

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU Se busca descomponer una matriz An×n como A = LU donde

2

6 6 U=6 4

u11 0 . . . 0

u12 u22 . . . 0

··· ··· .. . ···

u1n u2n . . . unn

l11 6 l21 6 L=6 . 4 . . ln1 2

3 7 7 7 5

y

0 l22 . . . ln2

··· ··· .. . ···

0 0 . . . lnn

3 7 7 7 5

Matrices triangulares simplifican los c´ omputos: l11 6 l21 6 6 . 4 .. ln1 2 Lx = b

⇐⇒

0 l22 . . . ln2

··· ··· .. . ···

0 0 . . . lnn

b1 b2 . . . bn

3 7 7 7 5

=⇒

l11 x1 l11 x1 + l22 x2 . . . l11 x1 + l22 x2 + · · · + lnn xn

“Sustituci´ on hacia adelante”

= = = =

b1 b2 . . . bn

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU Se busca descomponer una matriz An×n como A = LU donde

2

6 6 U=6 4

u11 0 . . . 0

u12 u22 . . . 0

··· ··· .. . ···

u1n u2n . . . unn

l11 6 l21 6 L=6 . 4 . . ln1 2

3 7 7 7 5

y

0 l22 . . . ln2

··· ··· .. . ···

0 0 . . . lnn

3 7 7 7 5

Matrices triangulares simplifican los c´ omputos: l11 6 l21 6 6 . 4 .. ln1 2 Lx = b

⇐⇒

0 l22 . . . ln2

··· ··· .. . ···

0 0 . . . lnn

b1 b2 . . . bn

3 7 7 7 5

=⇒

l11 x1 l11 x1 + l22 x2 . . . l11 x1 + l22 x2 + · · · + lnn xn

“Sustituci´ on hacia adelante”

= = = =

b1 b2 . . . bn

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Proposici´ on 3.1 (Matrices elementales) Una matriz elemental n × n es una matriz que surge cuando operaciones elementales se le aplican las filas (columnas) de la matriz idendidad n × n: Tipo I: Ei ←→ Ej Tipo II: αEi −→ Ei , α 6= 0 Ejemplo

Tipo III: λEi + Ej −→ Ej

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Proposici´ on 3.1 (Matrices elementales) Una matriz elemental n × n es una matriz que surge cuando operaciones elementales se le aplican las filas (columnas) de la matriz idendidad n × n: Tipo I: Ei ←→ Ej Tipo II: αEi −→ Ei , α 6= 0

Tipo III: λEi + Ej −→ Ej

Ejemplo E1 ←→ E2 : 2

1 4 0 0

0 0 1

32 0 a11 1 5 4 a21 0 a31

a12 a22 a32

3 2 a11 a13 a23 5 = 4 a31 a21 a33

a12 a32 a22

3 a13 a33 5 a23

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Proposici´ on 3.1 (Matrices elementales) Una matriz elemental n × n es una matriz que surge cuando operaciones elementales se le aplican las filas (columnas) de la matriz idendidad n × n: Tipo I: Ei ←→ Ej Tipo II: αEi −→ Ei , α 6= 0

Tipo III: λEi + Ej −→ Ej

Ejemplo E1 ←→ E2 : 2

1 4 0 0 λE2 −→ E2 : 2

1 4 0 0

0 0 1

0 λ 0

32 0 a11 1 5 4 a21 0 a31

32 0 a11 0 5 4 a21 1 a31

a12 a22 a32

a12 a22 a32

3 2 a11 a13 a23 5 = 4 a31 a21 a33

3 2 a11 a13 a23 5 = 4 λa21 a31 a33

a12 a32 a22

a12 λa22 a32

3 a13 a33 5 a23

3 a13 λa23 5 a33

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Proposici´ on 3.1 (Matrices elementales) Una matriz elemental n × n es una matriz que surge cuando operaciones elementales se le aplican las filas (columnas) de la matriz idendidad n × n: Tipo I: Ei ←→ Ej Tipo II: αEi −→ Ei , α 6= 0

Tipo III: λEi + Ej −→ Ej

Ejemplo E1 ←→ E2 : 2

1 4 0 0 λE2 −→ E2 : 2

1 4 0 0

32 0 a11 1 5 4 a21 0 a31

0 0 1

0 λ 0

32 0 a11 0 5 4 a21 1 a31

λE2 + E3 −→ E3 : 2 32 1 0 0 a11 4 0 1 0 5 4 a21 0 λ 1 a31

a12 a22 a32

a12 a22 a32

a12 a22 a32

3 2 a11 a13 a23 5 = 4 a31 a21 a33

3 2 a11 a13 a23 5 = 4 λa21 a31 a33

3 2 a13 a11 a23 5 = 4 a21 a33 λa21 + a31

a12 a32 a22

a12 λa22 a32

3 a13 a33 5 a23

3 a13 λa23 5 a33

a12 a22 λa22 + a32

3 a13 5 a23 λa23 + a33

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Proposici´ on 3.1 (Matrices elementales) Una matriz elemental n × n es una matriz que surge cuando operaciones elementales se le aplican las filas (columnas) de la matriz idendidad n × n: Tipo I: Ei ←→ Ej Tipo II: αEi −→ Ei , α 6= 0

Tipo III: λEi + Ej −→ Ej

Ejemplo E1 ←→ E2 : 2

1 4 0 0 λE2 −→ E2 : 2

1 4 0 0

32 0 a11 1 5 4 a21 0 a31

0 0 1

0 λ 0

32 0 a11 0 5 4 a21 1 a31

λE2 + E3 −→ E3 : 2 32 1 0 0 a11 4 0 1 0 5 4 a21 0 λ 1 a31

a12 a22 a32

a12 a22 a32

a12 a22 a32

3 2 a11 a13 a23 5 = 4 a31 a21 a33

3 2 a11 a13 a23 5 = 4 λa21 a31 a33

3 2 a13 a11 a23 5 = 4 a21 a33 λa21 + a31

a12 a32 a22

a12 λa22 a32

3 a13 a33 5 a23

3 a13 λa23 5 a33

a12 a22 λa22 + a32

3 a13 5 a23 λa23 + a33

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Matrices elementales El algoritmo para determinar la inversa se puede enunciar en t´erminos de matrices elementales [A|I]

Gauss-Jordan −→

ˆ

I|A−1

˜

(13)

Si E1 , E2 , . . . , Em son las matrices elementales asociadas a las operaciones elementales involucradas en (15), entonces Em Em−1 · · · E2 E1 A = I

=⇒

A−1 = Em Em−1 · · · E2 E1

Proposici´ on 3.2 (Producto de matrices elementales) An×n una matriz no singular si, y s´ olo si, A se puede expresar como el producto de matrices elementales Demostracion Por (1), A = (Em Em−1 · · · E2 E1 )−1 = E1 −1 E2 −1 · · · Em −1

(14)

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Matrices elementales El algoritmo para determinar la inversa se puede enunciar en t´erminos de matrices elementales [A|I]

Gauss-Jordan −→

ˆ

I|A−1

˜

(13)

Si E1 , E2 , . . . , Em son las matrices elementales asociadas a las operaciones elementales involucradas en (15), entonces Em Em−1 · · · E2 E1 A = I

=⇒

A−1 = Em Em−1 · · · E2 E1

Proposici´ on 3.2 (Producto de matrices elementales) An×n una matriz no singular si, y s´ olo si, A se puede expresar como el producto de matrices elementales Demostracion Por (1), A = (Em Em−1 · · · E2 E1 )−1 = E1 −1 E2 −1 · · · Em −1

(14)

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU M´etodo de eliminaci´ on Gaussiana para Ax = b: [A|b]

operaciones elementales

−→

donde U es triangular superior

ˆ

U|b′

˜

(15)

Si E1 , E2 , . . . , Em son las matrices elementales asociadas a las operaciones elementales involucradas en (15), entonces Em Em−1 · · · E2 E1 A = U

=⇒

A = E1 −1 E2 −1 · · · Em −1 U = LU

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU M´etodo de eliminaci´ on Gaussiana para Ax = b: operaciones elementales

[A|b]

−→

donde U es triangular superior

ˆ

U|b′

˜

(15)

Si E1 , E2 , . . . , Em son las matrices elementales asociadas a las operaciones elementales involucradas en (15), entonces Em Em−1 · · · E2 E1 A = U

A = E1 −1 E2 −1 · · · Em −1 U = LU

=⇒

Ejemplo 2

2 4 4 6

2 7 18

3 2 7 5 22

−2E1 +E2 →E2

−→

−4E2 +E3 →E2

−→

2

2 4 0 6 2 2 4 0 0

2 3 18 2 3 0

3 2 −3E1 +E3 →E3 −→ 3 5 22 3 2 3 5= U 4

2

2 4 0 0

2 3 12

3 2 3 5 16

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU M´etodo de eliminaci´ on Gaussiana para Ax = b: operaciones elementales

[A|b]

−→

donde U es triangular superior

ˆ

U|b′

˜

(15)

Si E1 , E2 , . . . , Em son las matrices elementales asociadas a las operaciones elementales involucradas en (15), entonces Em Em−1 · · · E2 E1 A = U

A = E1 −1 E2 −1 · · · Em −1 U = LU

=⇒

Ejemplo 2

2 4 4 6

2 7 18

3 2 7 5 22

−2E1 +E2 →E2

−→

−4E2 +E3 →E2

−→

2

2 4 0 6 2 2 4 0 0

2 3 18 2 3 0

3 2 −3E1 +E3 →E3 −→ 3 5 22 3 2 3 5= U 4

2

2 4 0 0

2 3 12

3 2 3 5 16

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU En t´erminos de matrices elementales: 2

1 E3 E2 E1 = 4 0 0

0 1 −4

−1

−1

A = E1

E2

32 1 0 0 54 0 −3 1

E3

−1

2

0 1 0

1 U = 4 −2 5

32 1 0 0 5 4 −2 0 1 0 1 −4

0 1 0

32 0 2 0 54 0 1 0

3 2 1 0 0 5 = 4 −2 5 1 2 3 0

0 1 −4

3 2 3 5 = LU 4

3 0 0 5 1

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU En t´erminos de matrices elementales: 2

1 E3 E2 E1 = 4 0 0

0 1 −4

−1

−1

A = E1

E2

32 1 0 0 54 0 −3 1

E3

−1

0 1 0

2

1 U = 4 −2 5

32 1 0 0 5 4 −2 0 1 0 1 −4

0 1 0

32 0 2 0 54 0 1 0

3 2 1 0 0 5 = 4 −2 5 1 2 3 0

0 1 −4

3 0 0 5 1

3 2 3 5 = LU 4

Proposici´ on 3.3 (Factorizaci´ on LU) Si A es una matriz n × n tal que al aplicarle eliminaci´ on Gaussiana no resulta un pivote cero, entonces A puede factorizarse como el producto A = LU donde: 1

L es una matriz triangular inferior y U es triangular superior

2

ℓii = 1 y uii 6= 0 para i = 1, . . . , n

3

Bajo la diagonal de L la entrada ℓij = 1 es el m´ ultiplo de la fila j-´esima que es restada de la fila i-´esima con el fin de cancelar la entrada (i, j)

4

U es la matriz que se obtiene al aplicar eliminaci´ on Gaussina

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Factorizaci´ on LU En t´erminos de matrices elementales: 2

1 E3 E2 E1 = 4 0 0

0 1 −4

−1

−1

A = E1

E2

32 1 0 0 54 0 −3 1

E3

−1

0 1 0

2

1 U = 4 −2 5

32 1 0 0 5 4 −2 0 1 0 1 −4

0 1 0

32 0 2 0 54 0 1 0

3 2 1 0 0 5 = 4 −2 5 1 2 3 0

0 1 −4

3 0 0 5 1

3 2 3 5 = LU 4

Proposici´ on 3.3 (Factorizaci´ on LU) Si A es una matriz n × n tal que al aplicarle eliminaci´ on Gaussiana no resulta un pivote cero, entonces A puede factorizarse como el producto A = LU donde: 1

L es una matriz triangular inferior y U es triangular superior

2

ℓii = 1 y uii 6= 0 para i = 1, . . . , n

3

Bajo la diagonal de L la entrada ℓij = 1 es el m´ ultiplo de la fila j-´esima que es restada de la fila i-´esima con el fin de cancelar la entrada (i, j)

4

U es la matriz que se obtiene al aplicar eliminaci´ on Gaussina

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Errores aritm´eticos y de redondeo Notaci´ on punto flotante normalizada Un n´ umero en punto flotante con k d´ıgitos viene dado por f = ±.d1 d2 . . . dk × 10n ,

con

d1 6= 0

y 0 ≤ di ≤ 9 para i = 1, . . . k. Podemos aproximar un n´ umero real x por una aproximaci´ on en punto flotante f l(x) por medio dos m´etodos: Truncamiento: Si x = .d1 d2 . . . dk dk+1 dk+2 . . . × 10n , la aproximaci´ on en punto flotante f l(x) viene dada por f l(x) = .d1 d2 . . . dk × 10n Redondeo: Si x = ±.d1 d2 . . . dk dk+1 dk+2 . . . × 10n , la aproximaci´ on en punto flotante f l(x) viene dada por f l(x) =



n ` .d1 d2 . . . dk × 10´ . d1 d2 . . . dk + 10−k × 10n

si dk+1 < 5 si dk+1 ≥ 5

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo

Eliminaci´on Gaussiana y errores de redondeo Ejemplo 4.1 Utilice aritm´etica de redondeo a 3 d´ıgitos para resolver el sistema −10−4 x x

+ +

y y

= =

1 2

(16)

cuya soluci´ on exacta viene dada por x=

1 1.0001

y

y=

1.0002 1.0001

Soluci´ on »

−10−4 1 1 1 Porque:

1 2

–

104 E1 + E2 −→ E2

»

−10−4 0

1 104

1 104

–

f l(104 + 1) = f l(0.10001 × 105 ) = 0.100 × 105 = 104 f l(104 + 2) = f l(0.10002 × 105 ) = 0.100 × 105 = 104

=⇒

x=0 y=1

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Pivoteo parcial En el ejemplo anterior (4.1), multiplicar por 104 amplific´ o el error T´ecnica de pivoteo parcial: 2

⋆ 6 0 6 6 0 4 0 0

⋆ ⋆ 0 0 0

⋆ ⋆ a b c

⋆ ⋆ ⋆ ⋆ ⋆

⋆ ⋆ ⋆ ⋆ ⋆

⋆ ⋆ ⋆ ⋆ ⋆

3 7 7 7 5

Ejemplo (4.1) con pivoteo parcial: »

−10−4 1

1 2

1 1

−4

10 Porque:

–

E1 ←→ E2

E1 + E2 −→ E2

»

»

1 −10−4 1 0

1 1

– 1 2 1 1 – 2 =⇒ 1

x=1 y=1

f l(104 + 1) = f l(0.10001 × 101 ) = 0.100 × 101 = 1 f l(2 × 104 + 1) = f l(0.10002 × 101 ) = 0.100 × 101 = 1

Pivoteo

´ Algebra matricial

Sistemas de ecuaciones lineales

Factorizaci´ on de matrices

Referencias

R.L. Burden, J.D. Faires. An´ alisis num´erico S´eptima Edici´ on. Editorial Thomson. 2002. http://www.as.ysu.edu/∼faires/Numerical-Analysis/

J.W. Eaton GNU Octave: A high-level interactive language for numerical computations Network Theory Ltd., 2002 http://www.network-theory.co.uk/octave/manual/

Pivoteo