´ Algebra II: Tema 8.

1

TEMA 8.- NORMAS DE MATRICES Y N´ uMERO DE CONDICI´ oN ´Indice 1. Introducci´ on

1

2. Norma vectorial y norma matricial. 2.1. Norma matricial inducida por normas vectoriales. . . . . . . . . 2.2. Algunos ejemplos de normas matriciales inducidas. . . . . . . .

2 4 6

3. N´ umero de condici´ on de una matriz 3.1. Caso de matrices normales. . . . . . . . . . . . . . . . . . . . . .

8 9

1.

Introducci´ on

Frecuentemente, el estudio de un sistema f´ısico pasa por la resoluci´on de un sistema de ecuaciones lineales Ax = b (que se supone compatible determinado en todo este tema). Sin embargo, incluso asumiendo que este modelo lineal representa perfectamente la realidad, las matrices A˜ y ˜b de las que se dispone no son id´enticas a las A y b “reales”, principalmente debido a errores num´ericos de redondeo o errores en la medici´on de par´ametros f´ısicos. As´ı, en lugar de obtener la soluci´on exacta x0 del sistema Ax = b, en realidad se obtiene la ˜ = ˜b. Naturalmente, interesa tener una aproximaci´on soluci´on x˜0 del sistema Ax de la distancia (en un sentido a´ un por precisar) entre x˜0 y x0 . El objetivo de este tema es precisamente profundizar en esta idea. En las pr´oximas secciones se ver´a que dicha distancia depende esencialmente de una caracter´ıstica de la matriz A a la que se denomina condicionamiento o n´ umero de condici´on. Ejemplo 1. El sistema de ecuaciones 

10−4 1 1 1



x1 x2



 =

1 2



tiene como soluci´on (con 7 decimales de precisi´on) 

x1 x2



 =

1,00010001 0,99989999

 .

Sin embargo, una resoluci´on mediante el m´etodo de Gauss (con una precisi´on de solo 3 decimales) proporcionar´ıa la soluci´on 

x˜1 x˜2



 =

0 1

 ,

´ Algebra II: Tema 8.

2

que no parece una aproximaci´on suficiente a la soluci´on anterior. Este error se puede reducir mediante pivoteo parcial o total. Ejemplo 2. Un ejemplo cl´asico de matriz mal condicionada es la matriz de Hilbert:  1  1 1 1 ··· 1 2 3 n 1 1 1  1  · · · n+1 3 4  2  1 1 1 1   · · · H= 3 4 5 n+2  ,  .. .. .. . . ..   . . . . .  1 1 1 1 · · · 2n−1 n n+1 n+2 que es muy sensible a errores num´ericos.

2.

Norma vectorial y norma matricial.

Definici´ on 1 Sea (E, K, +, ·) un espacio vectorial. Una norma en E es cualquier aplicaci´on k · k : E −→ R que verifique ∀λ ∈ K y ∀z, w ∈ E las siguientes propiedades: N1) kzk ≥ 0, y kzk = 0 ⇔ z = 0. N2) kλzk = |λ|kzk N3) kz + wk ≤ kzk + kwk

(Desigualdad triangular).

Ejemplo 3. Tres ejemplos cl´asicos de norma en E = Cn son: – norma 1: kzk1 = |z1 | + · · · + |zn | – norma 2 o eucl´ıdea: kzk2 =

p

|z1 |2 + · · · + |zn |2

– norma ∞ o norma del supremo: kzk∞ = m´ax {|z1 |, · · · , |zn |} . Por supuesto, se debe verificar que cada una de las expresiones anteriores satisfacen las tres condiciones de la definici´on de norma. Detallamos la comprobaci´on para la norma 1 a continuaci´on y dejamos la norma ∞ al lector. La norma 2 se discute un poco m´as abajo en el contexto de normas inducidas por un producto escalar.

´ Algebra II: Tema 8.

3

N1) kzk1 = |z1 | + · · · + |zn | ≥ 0 y adem´as 0 = kzk1 ⇔ z1 = · · · = zn = 0 ⇔ z = 0. N2) kλzk1 = |λz1 | + · · · + |λzn | = |λ| (|z1 | + · · · + |zn |) = |λ|kzk1 . N3) kz + wk1 =

n X

|zi + wi |

i=1

≤

n X i=1

|zi | +

n X

|wi |

i=1

= kzk1 + kwk1 . Adem´as, las normas 1 y 2 son casos particulares de la norma p, definida ∀p ∈ N como 1 kzkp = (|z1 |p + · · · + |zn |p ) p .

Observaci´ on.- Todo norma k·k en E induce una distancia d(z, w) := kz−wk en E. En particular, la norma eucl´ıdea en Rn induce la distancia habitual. Definici´ on 2 Se dice que dos normas k · k , k · k♣ en E son equivalentes si existen α, β > 0 tales que ∀u ∈ E,

αkuk ≤ kuk♣ ≤ βkuk .

Proposici´ on.- En dimensi´on finita, todas las normas son equivalentes.

Observaci´ on.- Todo producto escalar h·, ·i en E induce una norma en E, definida como p kzk := + hz, zi. Es trivial comprobar que esta definici´on satisface las condiciones N1 y N2, consecuencia de la sesquilinealidad herm´ıtica en C (bilinealidad sim´etrica en R) y definici´on positiva del producto escalar. N3 se demuestra empleando la desigualdad de Schwarz. En particular, la norma 2 anteriormente mencionada coincide con la norma inducida por el producto escalar est´andar en Cn , es decir: √ kzk2 = z h z.

´ Algebra II: Tema 8.

4

Ejemplo 4. Es conocido que la forma sesquilineal (es decir, lineal en la primera componente y antilineal en la segunda) h·, ·i : Cm×n × Cm×n −→ C (A, B) 7−→ tr(B h A) constituye un producto escalar en Cm×n . La norma inducida por este producto escalar es v uX n p u m X h kAkF = tr(A A) = t |aij |2 , i=1 j=1

denominada norma de Frobenius.

2.1.

Norma matricial inducida por normas vectoriales.

Definici´ on 3 Sean k · k , k · k♣ dos normas en Cm , Cn respectivamente. Se denomina norma matricial k · k en Cm×n inducida por dichas normas vectoriales a k · k : Cm×n −→ R 7−→ kAk := sup

A

x6=0

kAxk . kxk♣

La definici´on anterior verifica las propiedas de norma. Efectivamente: N1) 

 kAxk ∀x ∈ C , ≥ 0 ⇒ kAk ≥ 0, kxk♣ n

y kAk = 0 ⇔ ∀x ∈ Cn , kAxk = 0 ⇔ ∀x ∈ Cn , Ax = 0 ⇔ A = [0]. N2) kλAk = sup x6=0

kAxk kλAxk = |λ| sup = |λ|kAk. kxk♣ x6=0 kxk♣

N3) kAx + Bxk kxk♣ x6=0   kAxk kBxk + ≤ sup kxk♣ kxk♣ x6=0 kAxk kBxk ≤ sup + sup x6=0 kxk♣ x6=0 kxk♣ = kAk + kBk.

kA + Bk = sup

´ Algebra II: Tema 8.

5

Nota: Hasta el momento se ha insistido en la existencia de dos normas vectoriales k · k , k · k♣ (diferentes, en general) y una norma matricial k · k. En adelante, frecuentemente se omitir´an los sub´ındices  y ♣ para evitar una notaci´on recargada. El lector deber´a deducir del contexto qu´e norma es la aplicada en cada caso (y, por supuesto, si es vectorial o matricial). Adem´as, ser´a tambi´en frecuente que ambas normas k · k y k · k♣ sean del mismo tipo (es decir, por ejemplo, ambas la norma p) pero en Cm y Cn respectivamente. Observaci´ on.- Como consecuencia trivial de la definici´on, ∀x ∈ Cn ,

kAxk ≤ kAkkxk.

Observaci´ on.- Se verifica

1

kAxk

sup = sup Ax

= sup kAxk . x6=0 kxk x6=0 kxk kxk=1

Observaci´ on.- El cociente es decir,

kAxk kxk

alcanza su supremo en S = {x ∈ Cn : kxk = 1},

∃x1 ∈ Cn : kx1 k = 1, kAx1 k = kAk. Demostraci´ on: Por un lado, un subconjunto de Cn es compacto si y solo si es cerrado y acotado. El conjunto S es cerrado (por ser complementario de un abierto) y acotado, luego compacto. Por otro lado, las aplicaciones Cn −→ Cm x 7→ Ax y Cm −→ R y 7→ kyk son ambas continuas. Puesto que la composici´on de dos aplicaciones continuas es continua, la aplicaci´on Cn −→ R x 7→ kAxk

´ Algebra II: Tema 8.

6

tambi´en lo es. Finalmente, toda funci´on continua definida sobre un compacto alcanza sus extremos en puntos del compacto, quedando as´ı probada la observaci´on. Corolario.- El cociente

kAxk kxk

tambi´en alcanza su supremo en Cn \{0}.

La observaci´on y el corolario anterior permiten sustituir el t´ermino “supremo” por el t´ermino “m´aximo” y escribir kAxk = m´ax kAxk, x6=0 kxk kxk=1 expresi´on que se emplear´a en el resto del tema. kAk = m´ax

Proposici´ on.- Si k·k es una norma en Cn×n inducida por normas vectoriales, entonces ∀A, B ∈ Cn×n ,

kABk ≤ kAkkBk

Demostraci´ on: ∀x ∈ Cn , kABxk ≤ kAkkBxk ≤ kAkkBkkxk kABk = m´ax kABxk ≤ m´ax kAkkBkkxk = kAkkBk. kxk=1

kxk=1

Observaci´ on.- Si m = n y las normas k · k y k · k♣ coinciden, la norma k · k n×n en C inducida por ella(s) verifica kIk = m´ax x6=0

kIxk = 1. kxk

De esto se deduce que la norma √ de Frobenius no es inducida por ninguna norma vectorial, pues kIkF = n. (Nota: se puede demostrar que tampoco es inducida por dos normas vectoriales, aunque ´estas sean distintas).

2.2.

Algunos ejemplos de normas matriciales inducidas.

Ejemplos relevantes de normas matriciales inducidas por normas vectoriales son los siguientes: Norma 1: Si las normas k · k y k · k♣ son la norma 1 en Cm y Cn respectivamente, kAk1 = m´ax kAxk1 = m´ax kxk1 =1

1≤k≤n

( m X j=1

) |ajk | .

´ Algebra II: Tema 8.

7

Norma 2: Si las normas k · k y k · k♣ son la norma 2 en Cm y Cn respectivamente, kAk2 = m´ax kAxk2 , kxk2 =1

tambi´en denominada norma espectral, y tratada en la pr´oxima proposici´on. Norma ∞: Si las normas k · k y k · k♣ son la norma ∞ en Cm y Cn respectivamente, kAk∞ = m´ax kAxk∞ = m´ax

( n X

1≤j≤m

kxk∞ =1

Proposici´ on.- Sea A ∈ Cm×n . Entonces, kAk2 = senta el radio espectral.

) |ajk | .

k=1

p

ρ(Ah A), donde ρ repre-

Demostraci´ on : Recordamos que Ah A es herm´ıtica, y por tanto diagonalizable unitariamente con autovalores reales λ1 ≤ . . . ≤ λn . Adem´as, dichos autovalores son no negativos: si λ es autovalor de Ah A, kAuk22 = (Au)h Au = uh Ah Au = uh λu = λkuk22 ⇒ λ =

kAuk22 ≥ 0. kuk22

Tambi´en sabemos que para todo v no nulo se verifica: λ1 = m´ın u6=0

uh Ah Au v h Ah Av uh Ah Au ≤ ≤ m´ a x = λn . u6=0 uh u vhv uh u

De este modo, kAk2 = m´ax u6=0

kAuk2 = kuk2

s m´ax u6=0

uh Ah Au p = λn . uh u

Proposici´ on.- Cualquier norma k·k en Cn×n inducida por normas vectoriales verifica kAk ≥ ρ(A). Demostraci´ on: Sean λ1 , . . . , λn los valores propios de A, con |λ1 | ≤ · · · ≤ |λn |. Sea u un vector propio de A asociado a λn . Entonces: kAk ≥

kAuk kλn uk = = |λn | = ρ(A). kuk kuk

´ Algebra II: Tema 8.

3.

8

N´ umero de condici´ on de una matriz

Sea A ∈ Cm×n , con rg(A) = n ≤ m. Se define el n´ umero de condici´on de A asociado a una norma k · k como m´ax kAxk

c(A) =

kxk=1

m´ın kAxk

.

kxk=1

Comentario: El cociente anterior est´a bien definido, porque m´ın kAxk = 0 ⇔ ∃x 6= 0, Ax = 0 ⇔ rg(A) < n.

kxk=1

En el caso rg(A) < n, se define c(A) = ∞. El n´ umero de condici´on proporciona una cota superior para el error en la resoluci´on de un sistema de ecuaciones. Ve´amoslo en dos casos. Perturbaci´ on del t´ ermino independiente b. Se considera el sistema Ax = b, con A ∈ Cm×n y rg(A) = n ≤ m. Supongamos que tiene soluci´on u ´nica x0 6= 0. Se desea estudiar la variaci´on del vector soluci´on x0 ante variaciones del vector b. De este modo, se considera el sistema Ax = b + ∆b, y se asume que tambi´en tiene soluci´on u ´nica x0 + ∆x0 . Se pretende estimar k∆x0 k. Observamos Ax0 = b A (x0 + ∆x0 ) = b + ∆b. Restando ambas ecuaciones, A (∆x0 ) = ∆b. Denotando M = m´ax kAxk y m = m´ın kAxk, se tiene: kxk=1

kxk=1

kA∆x0 k k∆bk k∆bk kAxk ≤ = ⇒ k∆x0 k ≤ kxk6=0 kxk k∆x0 k k∆x0 k m

m = m´ın

kAxk kAx0 k kbk 1 M ≥ = ⇒ ≤ . kxk6=0 kxk kx0 k kx0 k kx0 k kbk

M = m´ax

Multiplicando ambas inecuaciones, k∆x0 k M k∆bk k∆bk ≤ = c(A) . kx0 k m kbk kbk En conclusi´on, el n´ umero de condici´on proporciona una cota superior para la amplificaci´on del error relativo.

´ Algebra II: Tema 8.

9

Perturbaci´ on de la matriz A. De nuevo se considera el sistema Ax = b, que (se asume) tiene soluci´on u ´nica x0 6= 0. Ahora se desea estudiar la variaci´on del vector soluci´on x0 ante variaciones de la matriz A. De este modo, se considera el sistema (A + ∆A)x = b. Supongamos que este nuevo sistema sigue teniendo soluci´on u ´nica x0 + ∆x0 , con ∆x0 6= 0. En este caso se verifica k∆Ak k∆x0 k ≤ c(A) . kx0 + ∆x0 k kAk La demostraci´on se omite. De nuevo, el n´ umero de condici´on proporciona una cota superior para la amplificaci´on del error relativo.

Observaci´ on.- Si A ∈ Cn×n es regular y k·k es una norma matricial inducida por una norma vectorial, entonces c(A) = kAkkA−1 k.

Demostraci´ on: Si A es regular, kA−1 xk x6=0 kxk kyk = m´ax y6=0 kAyk  −1 kAyk = m´ın y6=0 kyk  −1 = m´ın kAyk ,

kA−1 k = m´ax

kyk=1

de donde se obtiene inmediatamente la expresi´on anterior.

3.1.

Caso de matrices normales.

Si A ∈ Cn×n es normal, ∃U ∈ Cn×n unitaria tal que U h AU = D = diag(λ1 , . . . , λn ), con |λ1 | ≤ . . . ≤ |λn |. Adem´as U h Ah AU = (U h Ah U )U h AU = Dh D = diag(|λ1 |2 , . . . , |λn |2 ). Empleando de nuevo que el cociente de Rayleigh asociado a Ah A verifica

´ Algebra II: Tema 8.

|λ1 |2 = m´ın u6=0

10

uh Ah Au uh Ah Au uh Ah Au ≤ ≤ m´ a x = |λn |2 , u6=0 uh u uh u uh u

se deduce kAk2 = |λn | y c2 (A) =

|λn | , |λ1 |

donde c2 (A) representa el n´ umero de condici´on asociado a la norma 2, que tambi´en se denomina n´ umero de condici´on espectral.