Escuela Técnica Superior de Ingenieros Industriales

Universidad Politécnica de Madrid Curso 2013–2014

Definiciones, notaciones y resultados básicos de matemáticas

José Luis de la Fuente O’Connor [email protected] [email protected] 1

2

E

N ESTA INTRODUCCIÓN a la asignatura Matemáticas de la Especialidad–Ingeniería Eléctrica se recopilan conceptos, definiciones, relaciones y resultados que puede ser útil recordar o considerar para seguir su desarrollo de manera provechosa. Todos o casi todos se han estudiado en otras asignaturas de cursos anteriores a aquél en el que se imparte ésta. En ningún caso es un exhaustivo recordatorio de las matemáticas elementales que debe conocer un ingeniero industrial. También se introduce una cierta notación que, de forma uniforme, trataremos de usar en todas las lecciones y presentaciones de las clases.

1 Conjuntos Un conjunto es una colección de objetos: los números naturales, las soluciones de un problema determinado, los municipios de una provincia, etc. Se identifica por una letra mayúscula: el conjunto S , el conjunto de los números naturales N, el de los enteros Z, el de los reales R, complejos C, racionales Q, etc. Cada uno de los objetos en la colección es un elemento o miembro del conjunto. Si un elemento a pertenece a un conjunto se indica a 2 S . Los conjuntos se definen mediante la enumeración entre llaves de sus elementos, S D fa; b; : : : g, o especificando, también entre llaves, la propiedad que los caracteriza, S D fx W x 2 R; x  2g: números reales menores o iguales que dos. El conjunto sin elementos se denomina vacío, designándose ;. Ejemplo: el conjunto S de los números reales x que son mayores que 1 y menores que 0: esto es, S D fx 2 R W x > 1; x < 0g. Si S y S 0 son dos conjuntos y todos los elementos del conjunto S 0 lo son de S, se dice que S 0 es un subconjunto del conjunto S , o que está contenido en S 0 , expresándose S 0  S o S  S 0 . La unión de dos conjuntos S y T , expresada S [ T , es el conjunto formado por los elementos que pertenecen a S o a T . La intersección de S y T , expresada S \ T , es el conjunto formado por los elementos que pertenecen a S y a T . Si S 0 es un subconjunto de S, el complemento de S 0 en S es el conjunto formado por los elementos de S que no pertenecen a S 0 . Si a y b son números reales, y a  b, el conjunto de números x de la recta real tales que a  x  b se indica Œa; b. El formado por los x tales que a < x  b, por .a; b. El de los x que verifican que a < x < b, por .a; b/. Si S es un conjunto no vacío de números reales acotados superiormente —mayorados—, existe un número real mínimo y tal que x  y para todo x 2 S . Al número y se le denomina cota superior mínima o supremo de S ; se expresa así: sup .x/ o x2S

sup fx W x 2 S g :

De forma similar se define la cota inferior máxima —o ínfimo— de un conjunto S no vacío de números reales acotados inferiormente o minorados: Kınf .x/ o

x2S

Kınf fx W x 2 Sg :

2 Aplicaciones Dados dos conjuntos S y T , una aplicación f de S en T , expresada como f W S ! T , es una asociación o criterio que a cada elemento de S hace corresponder uno de T . 3

La imagen de un elemento x 2 S con la aplicación f W S ! T es el elemento f .x/ 2 T . El conjunto imagen f .S/ = ff .x/ 2 T; para todo x 2 S g. La imagen de un subconjunto S 0  S con la aplicación f sería, por consiguiente, el subconjunto imagen f .S 0 /. El conjunto S se conoce como origen o dominio de definición y el T como dominio de valores. Una aplicación f W S ! T se dice inyectiva si para cualquier par de elementos x; y 2 S , x ¤ y, se cumple que f .x/ ¤ f .y/. Ejemplo, la aplicación f W R ! R, definida por f .x/ D x 2 , no es inyectiva, pues f .1/ D f . 1/ D 1. Una función es un caso particular de aplicación en donde los conjuntos origen e imagen son conjuntos de números: R, C, Z, N, etc. Una aplicación f W S ! T se dice suprayectiva —sobreyectiva, epiyectiva, suryectiva o exhaustiva— de un elemento x 2 S con aplicación f T W S; es ! Tdecir, es el elemento .x/ 2 Ty. El2 T existe un x 2 S si el conjunto imagenLaf imagen .S/ es igual a todo el laconjunto paraftodo conjunto imagen f .S/ = ff .x/ 2 T; para todo x 2 S g. La imagen de un subconjunto S  S con tal que f .x/ D y. la aplicación f sería, por consiguiente, el subconjunto imagen f .S /. El conjunto S se conoce como origen o dominio de definición y el T como dominio de valores. Una aplicación f W S ! T se dice Una aplicación seinyectiva dice biyectiva inyectiva Jn es el conjunto de los si para cualquiersi pares de elementos x; y 2ySsuprayectiva. , x ¤ y, se cumple queEjemplo, f .x/ ¤ f .y/. si Ejemplo, f W R ! R, definida por f .x/ D x , no es inyectiva, pues f .1/ D f . 1/ D 1. números enteros de la1aplicación a n, J D f1; : : : ; ng, y se define una aplicación  W J ! Jn que modifica el n es un caso particular de aplicación en donde los conjuntos origen e imagen son n conUna función R, C, Z, N,de etc. Jn —estas aplicaciones se denominan permutaciones—, tal orden de disposiciónjuntos de de losnúmeros: elementos Una aplicación f W S ! T se dice suprayectiva —sobreyectiva, epiyectiva, suryectiva o exhaustiva— aplicación es biyectiva. si el conjunto imagen f .S/ es igual a todo el conjunto T ; es decir, para todo y 2 T existe un x 2 S que f .x/ D y. Un conjunto S se taldice numerable si existe una biyección entre N y S : a cada unos de los n elemenUna aplicación se dice biyectiva si es inyectiva y suprayectiva. Ejemplo, si J es el conjunto de los tos k, 1  k  n, senúmeros le asocia esto k 7! . J que modifica el enteros un de 1 elemento a n, J D f1; : : a : ;k ng,2 y seS, define una es: aplicación  Wa J k! orden de disposición de los elementos de J —estas aplicaciones se denominan permutaciones—, tal aplicación es biyectiva. Una sucesión de elementos de un conjunto T es una aplicación de N en T : a cada elemento n  1 Un conjunto S.n/ se dice numerable si existe una N y S : a cada unos de los n elemense le hace corresponder un x 2 T : n 7! x .n/biyección . Tal entre sucesión se expresa como fx .1/ ; x .2/ ; : : : g o tos k, 1  k  n, se le asocia un elemento a 2 S, esto es: k 7! a . fx .n/ gn1 . Una sucesión de elementos de un conjunto T es una aplicación de N en T : a cada elemento n  1 se le hace corresponder un x 2 T : n 7! x . Tal sucesión se expresa como fx ; x ; : : : g o Los conjuntos dotados ciertas leyes de composición o asociación interna —adición, multiplicafx g de . Los conjuntos dotados ciertas leyes composiciónuna o asociación interna —adición, ción, división o cualquier otra—, sede dice quedeposeen estructura. Las multiplicaestructuras fundamentales ción, división o cualquier otra—, se dice que poseen una estructura. Las estructuras fundamentales grupo, anillo (Z por ejemplo), C, por ejemplo) y espacio vectorial. son: grupo, anillo (Zson:por ejemplo), cuerpocuerpo (R (Ry yC, por ejemplo) y espacio vectorial. 0

0

2

n

n

n

n

n

k

.n/

.n/

k

.n/

.1/

.2/

n1

C

3 Espacios vectoriales

R

Z

Q

N

4

Sea K un cuerpo, un espacio vectorial E sobre K es un conjunto dotado de una ley de composición interna, adición, con la siguientes propiedades —grupo conmutativo—, xCy DyCx .x C y/ C z D x C .y C z/ xCøDx x C . x/ D ø; 4

y una ley de composición externa, producto por un escalar, de la que el dominio de operadores es K, con las siguientes propiedades, 1
x Dx ˛.ˇx/ D .˛ˇ/x .˛ C ˇ/x D ˛x C ˇx ˛.x C y/ D ˛x C ˛y;

válidas cualesquiera que sean x; y; z en E y ˛; ˇ en K; a ø se le denomina elemento neutro y a x el opuesto de x. Es usual denominar vectores a los elementos de E y escalares a los de K. En las aplicaciones que se estudian en la asignatura los casos más importantes ocurren cuando K D R o K D C. Con la notación K designaremos a cualquiera de los cuerpos R o C y por x un vector cualquiera de un espacio vectorial. Un ejemplo característico de espacio vectorial lo constituye el formado por sucesiones ordenadas de n elementos cualesquiera de K, o n-uplas x D .x1 ; : : : ; xn /, definiendo la suma de vectores mediante .x1 ; : : : ; xn / C .y1 ; : : : ; yn / D .x1 C y1 ; : : : ; xn C yn / y el producto por un escalar mediante ˛.x1 ; : : : ; xn / D .˛x1 ; : : : ; ˛xn / :

P Otro espacio vectorial muy conocido es Pn , de polinomios de grado n, pn .x/ D nkD0 ak x k , con coeficientes ak , reales o complejos, n  0. Si X es un conjunto arbitrario, el conjunto de aplicaciones ' W X ! K se estructura también como un espacio vectorial definiendo las operaciones .' C / W x 7 ! '.x/ C .'/ W x 7 ! '.x/ :

.x/

El ejemplo anterior es un caso particular de este espacio vectorial tomando X D f1; 2; : : : ; ng. Un subespacio M , de un espacio vectorial E sobre un cuerpo K, es un subconjunto no vacío cerrado respecto de las operaciones de adición y producto por un escalar; es decir, se cumple que: 8x; y 2 M H) x C y 2 M; 8x 2 M y 8 2 K H) x 2 M:

La intersección de una familia cualquiera de subespacios de E es también un subespacio. Si X es un subconjunto cualquiera de E, el subespacio hX i engendrado por X es la intersección se todos los subespacios que contienen a X. Cuando hX i D E, se dice que X es una parte generadora de E. Dados vectores x1 ; : : : ; xn y escalares 1 ; : : : ; n , el vector formado según la expresión x D 1 x1 C


C n xn

se dice que es combinación lineal de los vectores x1 ; : : : ; xn de coeficientes 1 ; : : : ; n . Un subconjunto X de E es un subespacio si y sólo si contiene a cualquier combinación lineal de cualquier subconjunto finito de vectores de X . También se demuestra que el subespacio hX i es el conjunto de todas las combinaciones lineales de vectores de X. Un conjunto de vectores x1 ; x2 ; : : : ; xk se dicen linealmente dependientes si existen escalares i , P no todos cero, tales que kiD1 i xi D 0 ; linealmente independientes, si k X i D1

i xi D 0 H) i D 0; 5

0i k:

Una parte X de un espacio vectorial E se dice que es una familia libre si los vectores de cualquier subconjunto finito de X son linealmente independientes. La dimensión de un subespacio es el máximo número de vectores linealmente independientes en el subespacio. Una base de un espacio vectorial E es cualquier subconjunto B de E que sea, simultáneamente, una parte libre y generadora de E; dicho de otra forma, una base de un espacio vectorial es un conjunto —normalmente se supone ordenado (numerado)— de vectores linealmente independientes que generan dicho espacio. Se demuestra que cualquier espacio vectorial tiene una base y que todas las bases de un mismo espacio tienen la misma cardinalidad —se pueden poner en biyección—. Cuando el cardinal de las bases es un número natural, n 2 N, se dice que el espacio es de dimensión finita n. En un espacio vectorial K n , 2 3 2 3 2 3 0 0 1 6 7 6 7 6 7 6 0 7 6 1 7 6 0 7 7 6 : 7; 7 6 ; : : : ; e D ; e D e1 D 6 n 2 6 : 7 6 :: 7 6 :: 7 4 : 5 4 : 5 4 : 5 1

0

0

forman una base en dicho espacio; éste, por tanto, tiene dimensión n. Esta base se denomina base canónica de K n . En esta base, cualquier vector x T D Œx1 ; x2 ; : : : ; xn  se puede expresar de la siguiente forma: 2 3 2 3 2 3 2 3 x1 1 0 0 6 7 6 7 6 7 6 7 6 x2 7 6 0 7 6 1 7 6 0 7 6 : 7 D x1 6 : 7 C x2 6 : 7 C


C xn 6 : 7 : 6 : 7 6 : 7 6 : 7 6 : 7 4 : 5 4 : 5 4 : 5 4 : 5 xn

0

0

1

Si A y B son subconjuntos de un espacio vectorial E, el conjunto A C B se define como: A C B D fa C b W a 2 A; b 2 Bg :

Cuando A y B son subespacios, también lo es la suma A C B. Si además A \ B D ;, la suma se denomina directa, escribiéndose A ˚ B. Si A ˚ B D E, cualquier vector c 2 E se descompone de manera única como c D a C b, con a 2 A y b 2 B; también se dice que A y B son subespacios suplementarios. 3.1 Espacios normados Si en un espacio vectorial E sobre K (R o C) se define una norma vectorial como una aplicación k
k W E ! R que verifica kvk D 0 H) v D 0 y x ¤ 0 H) kxk > 0; k˛vk D j˛jkvk

para ˛ 2 K y v 2 E;

ku C vk  kuk C kvk

8u; v 2 E;

se dice que E es un espacio vectorial normado. La condición kuCvk  kukCkvk es la desigualdad de Minkowski; se conoce también como regla del triángulo. Es una generalización del hecho de que un lado de un triángulo no puede ser mayor que la suma de los otros dos: ver figura. Una variante de esta regla es la siguiente: ku

vk  kuk 6

kvk:

ku

vk  kuk

kvk:

v uCv u

3.1: Representación gráfica de la regla del tri Figura 3.1: Representación gráfica de la regla Figura del triángulo n espacio vectorial Kde , para 1  p < 1, se tiene la familia de En el espacio vectorial Kn , para 1  En p 0, existe un N 2 N tal que a partir de él, n  N , se cumple que kx .n/ vk < ". Cuando una sucesión fx .n/ g admite un vector límite v sólo tiene ese vector como límite —si existe límite es único—: se escribe lKımn!1 x .n/ D v. Es equivalente decir que lKımn!1 x .n/ D v y que lKımn!1 kx .n/ vk D 0. En particular, x .n/ ! 0 si y sólo si kx .n/ k ! 0. 1 Cuando

así lo aconseja la dificultad de la notación, una sucesión también se designa por fxn g; sus integrantes, x .k/ .

7

– Si el conjunto fx 2 R2 W kxk  1g es la bola cerrada unidad en R2, su forma para las normas vectoriales 1, 2, 1, y p son estas.
x
11 D = kxk

2 i 2


|xijx | ij

q 

|22+

i=1

iD1

√ q DxT xx T x

=2


x
22 D = jx |x11j C|xjx 2 2j kxk |2


x
1 max kxk D1≤i≤2 mKax|xjx ∞ = i| i j 1i2



1/p

p p 1=p
x
pp D = Œjx |x11|jpp+C|xjx p < p∞) kxk < 1/ 2 | 2 j , (1 ;≤.1

28/63

Figura 3.2: Forma de la bola unidad para diferentes normas en R2 a

b

c

d

e

f

h

i

j

g

1

2

3

9

4

6

10

8

7

5

Una sucesión fx .n/ g en un espacio vectorial normado por k
k se denomina sucesión de Cauchy, si para cada " > 0, existe un n 2 N tal que cualesquiera que sean p; q  n, se cumple que kx .p/ x .q/ k < ". Toda sucesión convergente es una sucesión de Cauchy pero pueden existir espacios normados con sucesiones de Cauchy que no son convergentes. Un espacio vectorial normado se dice completo si toda sucesión de Cauchy en él tiene límite. Un espacio de Banach es un espacio vectorial completo respecto de la norma a él asociada. Todo espacio vectorial normado de dimensión finita es un espacio de Banach. En un espacio de dimensión infinita esto no es cierto; por ejemplo, es fácil ver que en C Œ0; 1 la sucesión de funciones cuyas gráficas son las de la figura 3.3 es una sucesión de Cauchy para cualquier norma k
kp , pero no tiene límite en C Œ0; 1. fn .x/ 6 =

1 n

=






0

1






x



=

1 n

=

Figura 3.3: Gráfica de una de las funciones de una sucesión de Cauchy

8

3.2 Espacios con producto interior Sea E un espacio vectorial sobre un cuerpo K (R o C); una forma sesquilineal —vez y media lineal— sobre E es una aplicación, h
j
i W E  E ! K, que verifica2 : 1) h˛u C ˇvjwi D ˛hujwi C ˇhvjwi y 2) huj˛v C ˇwi D ˛hujvi C ˇhujwi;

cualesquiera que sean u, v, w en E y ˛; ˇ en K. Si además se cumple que hujvi D hvjui ; la forma se denomina hermítica. Es claro que hujui es siempre un número real. Cuando se cumple que u ¤ 0 H) hujui > 0 ; se dice que la forma es definida positiva, denominándosela también producto escalar. Una forma sesquilineal sobre R es siempre bilineal. Un espacio prehilbertiano es un espacio vectorial sobre K dotado de una forma hermítica definida positiva. Todo espacio prehilbertiano es un espacio normado mediante p kvk D hvjvi :

En la demostración de que esta definición corresponde a la de una norma en E juega un papel importante la desigualdad de Cauchy-Schwarz: a saber, ˇ ˇ ˇ ˇ ˇhujviˇ  kuk
kvk :

Un espacio de Hilbert p es un espacio prehilbertiano completo respecto de la norma que deriva del producto escalar k
k D h
;
i . Dicho de otra forma, un espacio prehilbertiano que con esta norma da un espacio de Banach. El espacio euclídeo n-dimensional, expresado Rn o En , es un espacio de Hilbert de dimensión finita. Dos vectores cuyo producto escalar es cero se denominan ortogonales; si su k
k2 es igual a la unidad, se denominan ortonormales. Para dos vectores ortogonales se tiene la identidad ku C vk2 D kuk2 C kvk2 ; que es una generalización del teorema de Pitágoras. En un espacio prehilbertiano, el único vector ortogonal a todos los vectores del espacio es el vector nulo; si este espacio es de dimensión finita es posible construir una base ortonormalizada. En un espacio euclídeo n-dimensional, el ángulo entre dos vectores x e y es  T  x y  D arc cos ; kxkkyk

donde

xT y kxkkyk cumple que 1    1, para cualesquiera x e y. D

2 La

barra designa complejo conjugado.

9

Dos vectores son ortogonales si x T y D 0 ( D =2;  D 0); alineados, si x T y D kxkkyk ( D 0;  D 1); opuestos, si x T y D kxkkyk ( D ;  D 1). Forman un ángulo agudo si x T y > 0 ( < =2;  > 0) y un ángulo obtuso si x T y < 0 ( > =2;  < 0). Una familia cualquiera de vectores distintos del nulo y ortogonales dos a dos es una familia libre. Si M es un subespacio de un espacio prehilbertiano E de dimensión finita, el subespacio ortogonal de M , M ? , es el subespacio formado por todos los vectores ortogonales a los de M , siendo un subespacio suplementario de M ; es decir M ˚ M ? D E. Cualquier x 2 E, por consiguiente, se puede expresar como x D a C b, con a 2 M y b 2 M ? . 3.3 Aplicaciones lineales Dados dos espacios vectoriales E y F , sobre el mismo cuerpo K, se define una aplicación lineal, transformación lineal, operador lineal u homomorfismo, f , de E en F , como una aplicación f W E ! F que verifica f .x C y/ D f .x/ C f .y/ ;

cualesquiera que sean los vectores x, y de E y los escalares  y . Existen dos casos particulares interesantes: el primero cuando E D F , en este caso se dice que f es un operador lineal de E o endomorfismo de E; el segundo cuando F D K —el cuerpo base—, en cuyo caso la aplicación se denomina forma lineal sobre E. El conjunto L.E; F / de todas las aplicaciones lineales del espacio E en el espacio F se estructura como un espacio vectorial si se definen las siguientes operaciones: a) adición .f C g/ W

b) producto por un escalar f W

.f C g/.x/ D f .x/ C g.x/ .f /.x/ D f .x/

8x 2 EI

8x 2 E y 8 2 K:

En particular, el conjunto L.E; K/ de formas lineales es un espacio vectorial denominado dual de E, representándose con E  . Para una aplicación lineal f W E ! F , el conjunto de vectores de F que son la imagen de los de un subespacio de E forma un subespacio de F . En particular, la imagen de todo E es un subespacio de F que se denomina subespacio imagen de f , representándose mediante Im.f /. Análogamente, el conjunto anti-imagen de un subespacio de F forma un subespacio de E. En particular, la anti-imagen del subespacio nulo de F forma lo que se denomina el núcleo de la aplicación, representándose por ker.f /. Así pues ker.f / D fx 2 E W f .x/ D 0g : Si b 2 F , la ecuación lineal f .x/ D b tiene solución si y sólo si b 2 Im.f /. En ese caso el conjunto de todas las soluciones es la variedad lineal —traslación de un subespacio— dada por x0 C ker.f /, donde x0 es una solución particular de la ecuación. En particular, la aplicación es inyectiva si y sólo si ker.f / D ;. Sean E y F dos espacios prehilbertianos sobre el cuerpo K; si f W E ! F es una aplicación lineal, la aplicación traspuesta de f es la aplicación f  W F ! E que cumple hxjf  .y/i D hf .x/jyi ;

cualesquiera que sean los vectores x 2 E e y 2 F . Particularmente importante es el caso en que E D F : f  se dice entonces que es el operador adjunto de f . Cuando un operador f de E cumple que f  D f se denomina operador autoadjunto. En el caso de que E sea un espacio vectorial real, también se dice que f es un operador simétrico y cuando es un espacio vectorial complejo, que f es un operador hermítico. Un operador simétrico cumple que hxjf .y/i D hf .x/jyi; 10

mientras que uno hermítico, que hxjf .y/i D hf .x/jyi: Un operador f de E es unitario cuando es invertible y su inverso coincide con su adjunto. Es decir, si f  D f 1 . Para un operador unitario se tiene que hf .x/jf .y/i D hf  .f .x//jyi D hxjyi ;

de manera que kf .x/k D kxk. Por este motivo a los operadores unitarios también se les denomina operadores isométricos. Dada una transformación lineal, u aplicación lineal, f W E ! E, se dice que un subespacio W de E es un subespacio invariante frente a f (o f -invariante) si para todo vector w 2 W se cumple que f .w/ 2 W . Dicho de otra manera, W es un subespacio invariante si f .W /  W .

4 Matrices Sean dos espacios vectoriales E y F de dimensiones finitas n y m sobre el mismo cuerpo K. Una aplicación lineal g W E ! F , g 2 L.E; F /, está caracterizada o representada en dos bases fe1 ; e2 ; : : : ; en g de E y ff1 ; f2 ; : : : ; fm g de F por una tabla de coeficientes, matriz asociada, de m filas y n columnas: 2 3 a11


a1n 6 : :: 7 :: mn :: AD6 : : : 7 4 52K am1


amn Los coeficientes aij están definidos por

g.ej / D El vector columna j -ésimo

m X

1  j  n:

aij fi ;

i D1

2

a1j

6 6 a2j 6 : 6 : 4 : amj

3 7 7 7 7 5

representa el vector g.ej / en la base .fi /. A partir de la matriz A se pueden calcular los componentes y1 ; y2 ; : : : ; ym del vector y D g.x/ en la base .fi /, conociendo los componentes x1 ; x2 ; : : : ; xn en la base .ej /. En efecto: 2 3 2 3 2 3 2 3 y1 a11 a12 a1n 6 7 6 7 6 7 6 7 6 y2 7 6 a21 7 6 a22 7 6 a2n 7 6 : 7 D x1 6 : 7 C x2 6 : 7 C


C xn 6 : 7 : 6 : 7 6 : 7 6 : 7 6 : 7 4 : 5 4 : 5 4 : 5 4 : 5 ym

am1

am2

Expresión que también se puede escribir de la siguiente forma: yD

n X i D1

11

xi ai ;

amn

donde ai es el vector columna i -ésimo de la matriz A. Así pues, si se fijan dos bases en E y F , cada aplicación lineal, g W E ! F , queda unívocamente representada por una matriz. Recíprocamente, toda matriz en K mn define unívocamente una aplicación lineal entre dos espacios E y F de dimensiones n y m en los que se han fijado dos bases. En particular, se pueden identificar las matrices m  n con las aplicaciones lineales de K n en K m . Las matrices de m filas y n columnas con coeficientes en el cuerpo K forman un espacio vectorial, mn K , sobre dicho cuerpo K. Si E y F son dos espacios de dimensión finita dotados de un producto escalar y la aplicación ˛ 2 L.E; F / se representa en dos bases ortonormalizadas mediante una matriz A, la aplicación ˛ T 2 L.F; E/, traspuesta de ˛, viene representada por la matriz A T , traspuesta de A. El núcleo y la imagen de una matriz A 2 K mn , ker.A/ y Im.A/, respectivamente, se definen como los subespacios de K n y K m que son el núcleo y la imagen de la aplicación lineal asociada: % ker.A/ D fx 2 K n W Ax D 0g : Im.A/ D fy 2 K m W y D Ax; x 2 K n g A2K mn Dicho de otra forma, la imagen de una matriz es el subespacio generado por los vectores columna de la matriz; los vectores fila también generan un subespacio que no es otro que la imagen de A T . Para una matriz A 2 Rmn se cumple que:
ker A T D .Im.A//?
Im A T D .ker.A//?

? ker.A/ D Im A T

? Im.A/ D ker A T : El Teorema fundamental del algebra lineal establece que si A 2 Rmn se cumple que
ker .A/ ˚ Im A T D Rn : El rango de una matriz es la dimensión3 de su subespacio imagen: rango.A/ D dim.Im.A// Una matriz A 2 K mn se dice de rango completo si rango.A/ D mKın.m; n/. Una matriz cuadrada A 2 K nn se denomina singular si rango.A/ < n; regular si rango.A/ D n. La aplicación asociada a una matriz A 2 Rmn es suprayectiva si rango.A/ D m. Para una matriz A 2 K mn se cumple que dim.ker.A// C rango.A/ D n ;

o, alternativamente, dim.ker.A// D n inyectiva, si y sólo si rango.A/ D n.

rango.A/. La aplicación lineal asociada a A es, por tanto,

4.1 Normas de matrices Aun cuando en lo que sigue nos limitaremos a matrices cuadradas, la mayor parte de las definiciones y resultados son extensibles a matrices rectangulares; también supondremos que las matrices son reales. 3 Recordemos:

máximo número de vectores linealmente independientes.

12

Las matrices cuadradas de orden n forman un espacio vectorial con un producto, esto es, un álgebra. Una norma matricial es una norma vectorial compatible con el producto. Se define formalmente sobre Rmn como una aplicación k
k W Rmn ! R que cumple: 1) kAk D 0 H) A D 0:

2) kAk D jj
kAk:

3) kA C Bk  kAk C kBk:

4) kABk  kAk
kBk:

Existen normas sobre el espacio Rmn que no son normas matriciales pues no cumplen la propiedad 4). Así, si se define kAk D mKax jaij j ; 1i;j n

h i se satisfacen 1), 2) y 3); sin embargo, tomando A D B D 11 11 , es fácil ver que kABk D 2 > kAk
kBk D 1, por lo que no se cumple 4). Un ejemplo importante de norma matricial es la norma de Frobenius, definida como: X kAk2F D aij2 D traza.A T A/; 1i;j n

P donde la traza de una matriz A de orden n es niD1 ai i . Es fácil ver que esta norma deriva del producto escalar hAjBi D traza.A T B/, que configura al espacio de las matrices cuadradas como un espacio prehilbertiano. La norma de Frobenius cumple que kABkF  kAkF
kBkF : Una norma matricial k
k sobre Rmn se dice consistente con una norma vectorial k
k0 sobre Rn cuando para cada matriz A y cada vector x se cumple que kAxk0  kAk
kxk0 : Por ejemplo, la norma de Frobenius y la norma euclídea de Rn son consistentes pues kAxk2  kAkF
kxk2 : Se demuestra que para toda norma matricial es posible construir una norma vectorial consistente. Recíprocamente, a toda norma vectorial sobre Rn se le puede asociar una norma matricial consistente. Una norma matricial consistente con una cierta norma vectorial k
k se construye mediante la definición kAxk : kAk D sup 0¤x2Rn kxk Esta norma matricial se dice inducida por la norma vectorial. Ejemplo: la norma matricial inducida por la norma euclídea de Rn es la norma espectral: " #1=2 p x T A T Ax kAk2 D sup D max .A T A/ D max .A/; Tx x n 0¤x2R

donde  designa un valor propio de A y  un valor singular. Si k
k es la norma inducida por una cierta norma vectorial y k
k0 es una norma matricial cualquiera consistente con esa norma vectorial, 13

se cumple, para toda matriz A, que kAk  kAk0 . En particular, para la norma espectral y la norma de Frobenius, se cumple que kAk2  kAkF : Las normas matriciales inducidas más usadas son kAk1

D

kAk1 D

mKax

1j n

mKax

1i m

m X

i D1 n X

j D1

jaij j y jaij j :

Ejemplo 4.1 El efecto que produce aplicar la transformación lineal basada en la matriz # " 1 2 AD 0 2 sobre la bola unidad definida a partir de las normas k
k1 , k
k2 y k
k1 en R2 , se representa en la figura 4.4. La aplicación transforma el vector e1 D Œ1; 0T en sí mismo y e2 D Œ0; 1T en Œ2; 2T . [2, 2]T [0, 1]T norma11 norma


A
1 = 4

[1, 0]T

[1, 0]T


A
2 ≈ 2,9208

norma22 norma


A
∞ = 3

norma1 ∞ norma

– La Figura aplicación transforma el vector e 1 Dunidad Œ1;para 0Tdiferentes en sí normas mismo y 4.4: Efecto de una aplicación lineal sobre la bola T T e 2 D Œ0; 1 en Œ2; 2 .

39/63

Tomando la norma 1, el vector unitario que más se amplifica al aplicarle la transformación es Œ0; 1T (o Œ0; 1T ), que pasa a ser Œ2; 2T . Su factor de amplificación, en términos de la norma 1, es 4. Tomando ala norma 2, el vector1 unitario que más se amplifica es el que se representa en la figura c 2 3 b con una recta discontinua. El factor de amplificación es 2,9208. g e f 9 4 6 5 d Para la norma 1,jigualmente, 10el vector unitario que más se amplifica es el que se representa tam8 7 i h bién con la recta discontinua: Œ1; 1T , que pasa a transformarse en Œ3; 2T . El factor de amplificación

14

correspondiente es en este caso 3 ya que

Œ1; 1T D 1 1

Œ3; 2T D 3: 1

u

4.2 Matrices ortogonales, matrices de permutación y matrices de proyección Una matriz Q 2 Rmn se dice ortogonal si verifica que QT Q D I; es decir, cuando sus vectores columna son ortogonales dos a dos y de norma euclídea unitaria (ortonormales). Si Q 2 Rnn es ortogonal, se cumple que QQT D QT Q D I. Las matrices ortogonales Q 2 Rmn verifican: 9 > kQk2 D 1 > > > 1=2 = kQkF D n si m  n kQAk2 D kAk2 > > > > kQAk D kAk ; F

F

y

kQk2

D1

D m1=2

kQkF

9 > > > > =

kAQk2 D kAk2 > > > > kAQk D kAk ; F

si m  n

F

Una matriz de permutación es una matriz cuadrada cuyas columnas están formadas por las de la matriz unidad permutadas. Una matriz de permutación es una matriz ortogonal. Una matriz se dice simétrica si se verifica que A T D A. Para una matriz cualquiera A 2 Rmn , la matriz A T A es simétrica. Se denomina proyector o matriz de proyección a una matriz P 2 Rnn que verifica que P2 D P

Si P además es simétrica, se denomina proyector ortogonal o matriz de proyección ortogonal. Si, en este último caso, F es el subespacio imagen de la matriz P (el mismo que el de la matriz P T ), Px define la proyección ortogonal del vector x sobre F . Se denomina proyector suplementario de P al proyector S D I P. Si F D Im.P/ y G D ker.P/, entonces F D ker.S/ y G D Im.S/. En el caso de un proyector ortogonal P en el que F D Im.P/, se tiene que Rn D F ˚ F ? , verificándose que kPxk2  kxk2 y que kx

Pxk2 D

mKın

y2Im.P /DF

kx

yk2 :

5 Valores propios, valores singulares y formas cuadráticas 5.1 Valores propios Sea A una matriz cuadrada de orden n y coeficientes en K (R o C). Un vector no nulo u 2 Kn se denomina vector propio de A si para algún  2 K se cumple que Au D u : 15

A este  se le denomina valor propio o autovalor de la matriz A. El conjunto de los valores propios de una matriz A se denomina espectro de A, designándose por ƒ.A/. El radio espectral, .A/, se define de la siguiente manera: .A/ D mKax ji j: 1i n

Para que un número  sea valor propio de A, el sistema lineal y homogéneo de ecuaciones dado por .I A/x D 0

debe tener soluciones distintas de la trivial x D 0. Esto equivale a que det.A

I/ D 0 :

Esta es una ecuación polinómica de grado n en  que se denomina ecuación característica, o polinomio característico, de la matriz A. La ecuación característica admite la raíz  D 0 si y sólo si det.A/ D 0. Una matriz es invertible, por tanto, si y sólo si no admite al cero como vector propio. Una matriz real de orden n no tiene necesariamente valores propios reales pero, como consecuencia del teorema fundamental del álgebra, cualquier matriz compleja tiene al menos un valor propio complejo. El número máximo de valores propios es n. Siendo  un valor propio de la matriz A, el conjunto de soluciones del sistema de ecuaciones A/x D 0

.I

es un subespacio de Kn que se denomina subespacio propio asociado al valor propio , designándose con E . Si n es la multiplicidad de  como raíz de la ecuación característica de A, se cumple que dim.E /  n :

La intersección de subespacios propios correspondientes a valores propios distintos se reduce al subespacio nulo; esto es,  ¤  H) E \ E D ; : De este modo, la suma de subespacios propios es directa. Se cumple que M E D Kn 2ƒ.A/

si y sólo si para cada  2 ƒ.A/, dim.E / D n ; en ese caso existe una base de Kn formada toda ella por vectores propios de A. Siendo V una matriz cuadrada invertible de orden n cuyas columnas son los vectores de esa base, se tiene que AV D V D ; donde D D diag.1 ; : : : ; n /. Alternativamente, se puede escribir que V

1

AV D D ;

por lo que la matriz A es semejante a una matriz diagonal; se dice entonces que la matriz A es diagonalizable por semejanza. Toda matriz real y simétrica tiene todos sus valores propios reales y es diagonalizable por semejanza. Se demuestra además que los subespacios propios correspondientes a valores propios distintos son ortogonales. De aquí se sigue que es siempre posible formar una base ortonormalizada de vectores propios para una matriz real y simétrica A. Existe entonces una matriz ortogonal Q tal que se verifica que QT AQ D D; con QT D Q 1 ;

y, de aquí que, toda matriz real y simétrica es congruente ortogonal con su reducida diagonal. Este resultado fundamental de la teoría de matrices es la versión elemental del denominado teorema espectral. 16

5.2 Valores singulares La noción de valor propio, o autovalor, no tiene significado para matrices rectangulares. En éstas, por el contrario, se introduce el concepto de valor singular. Si A es una matriz rectangular m  n con coeficientes en R, se definen sus valores singulares i ; i D 1; : : : ; mKınfm; ng, como las raíces cuadradas positivas de los valores propios de la matriz cuadrada A T A 2 Rnn . Se demuestra que si A 2 Rmn , existen dos matrices ortogonales, U D Œu1 ; : : : ; um  2 Rmm

y

V D Œv1 ; : : : ; vn  2 Rnn ; tales que y donde

U T AV D diag.1 ; : : : ; p /;

p D mKınfm; ng ;

1  2 


 p  0 :

Los vectores ui se denominan vectores singulares izquierdos; los vi , vectores singulares derechos. Los valores singulares de A son las longitudes de los semiejes del hiperelipsoide E definido por E D fy W y D Ax; kxk2 D 1g : Es decir, las longitudes de los semiejes del hiperelipsoide imagen de la esfera unidad resultante de la aplicación que caracteriza la matriz A. En la figura 5.5 se describe gráficamente el caso en que m D n D 2.

σ2

{x}

σ1

{Ax}

Figura 5.5: Representación en dos dimensiones de una transformación lineal de la esfera unidad

Para una matriz A 2 Rmn cuya descomposición en valores singulares es A D U †V T , se define su matriz pseudoinversa, A Ž , como AŽ D V †ŽU T ; donde

† Ž D diag.1 1 ; : : : ; r 1 ; 0; : : : ; 0/ 2 Rnm :

Si A 2 Rmn es de rango completo y m > n, si m < n

AŽ D AT A 17




1

AT I

A Ž D A T AA T




1

:

Para cualquier matriz A 2 Rmn , la matriz A Ž A es la matriz n  n de proyección ortogonal sobre el subespacio de los vectores fila de A, AA Ž la m  m de proyección ortogonal sobre la imagen de la matriz A (subespacio de sus vectores columna) y .I A Ž A/ la de proyección ortogonal sobre el núcleo de A, ker.A/. 5.3 Formas cuadráticas Una forma cuadrática en n variables es un polinomio de segundo grado en esas variables. La expresión más general de una forma cuadrática es q.x/ D x T Qx ; donde Q D QT es una matriz simétrica de orden n. Nos limitaremos al análisis de formas cuadráticas con coeficientes reales. Mediante una transformación lineal de variables, x D T y, una forma cuadrática se puede reducir a la forma canónica de suma de cuadrados siguiente: q.x/ D

p X

X

pCq

yi2

i D1

yi2 :

i DpC1

El rango de la forma es p C q y la signatura p q (p números positivos y q negativos). Una forma cuadrática real es definida positiva si para todo vector x ¤ 0, q.x/ > 0. El rango y signatura de una forma cuadrática definida positiva valen n. Si Q la forman los coeficientes qij y se introducen los números menores como 2 3 q11 q12


q1i 6 7 6 q21 q22


q2i 7 i D det 6 :: : : : 7; 6 :: : :: 7 : 4 : 5 qi1 qi 2


qi i

la forma cuadrática asociada a Q es definida positiva si y sólo si todos los menores i son positivos. Sean 1 ; : : : ; n los valores propios —que sabemos son reales— de la matriz Q; por el teorema espectral, existe una matriz ortogonal P tal que P T QP D diag.1 ; : : : ; n /: Haciendo en la forma cuadrática q.x/ D x T Qx el cambio de variables x D Py, se tiene que q.x/ D y T P T QPy D 1 y12 C


C n yn2 ;

lo que hace ver que el rango de la forma cuadrática es el número total —teniendo en cuenta las multiplicidades— de valores propios no nulos de Q, mientras que la signatura coincide con la diferencia entre los números de valores propios positivos y negativos. En particular, la forma cuadrática asociada a Q es definida positiva si y sólo si todos los valores propios de Q son positivos. En ciertos casos es importante acotar el cociente de una forma cuadrática al cuadrado de la norma euclídea, es decir, el cociente x T Qx ; r.x/ D T x x 18

x ¤ 0:

Mediante una transformación ortogonal x D Py, este cociente se escribe como

1 y12 C


C n yn2 r.x/ D ; y12 C


C yn2 de manera que se deducen las acotaciones

x T Qx  max .Q/ : xT x Estas acotaciones no se pueden mejorar ya que si Qv D v, mi n .Q/ 

vT Qv D : vT v

Una matriz A se dice definida positiva si la forma cuadrática x T Ax es positiva para todo vector x ¤ 0. De forma similar se definen matrices semidefinida positiva, definida negativa y semidefinida negativa, si x T Ax  0, < 0 y  0, respectivamente, para todo vector x ¤ 0. La matriz A se dice indefinida si la forma x T Ax es positiva para algún x y negativa para otros. Lema 5.1 Para que una matriz simétrica sea definida positiva es necesario que todos los coeficientes de la diagonal principal sean positivos. Lema 5.2 Para que una matriz simétrica A sea definida positiva es necesario que el coeficiente de mayor valor absoluto esté en la diagonal principal. Más concretamente, mKax jaij j < mKax akk : i ¤j

k

Lema 5.3 Si en cada fila de una matriz simétrica A el coeficiente de la diagonal principal es mayor que la suma de los valores absolutos de todos los demás coeficientes de la fila, es decir, si akk >

n X j D1

jakj j

k D 1; : : : ; n;

j ¤k

A es definida positiva. D EMOSTRACIÓN . Para x ¤ 0 se tendrá que XX X q.x/ D aij xi xj  ai i xi2 0 1 i X X @ > jaij jA jxi2 j i

j

i

D D

XX i

j ¤i

j ¤i

jaij jjxi j jxi j

1 XX

2

i

j ¤i

jaij j jxi j

XX

XX i

j ¤i

i

j ¤i

jaij jjxi jjxj j

jaij jjxi jjxj j


XX jxj j D jaij jjxj j jxj j


2 jxj j  0:

i

j ¤i


jxi j

Es importante destacar que este último criterio define una condición suficiente, no necesaria. En efecto, la matriz 2 3 3 2 2 6 7 4 2 3 2 5; 2 2 3 19

es definida positiva, pues q.x/ D x12 C x22 C x32 C 2.x1 C x2 C x3 /2 ; lo que atestigüa que, cualquiera que sea x ¤ 0, q.x/ > 0. Esta matriz, sin embargo, no satisface el lema 5.3. Como ya se ha visto, una matriz simétrica definida positiva tiene todos sus valores propios reales y positivos; si es semidefinida, alguno es cero. Si la matriz es negativa definida, todos sus valores propios son negativos. Un resultado muy interesante para averiguar el orden de magnitud de los valores propios de una matriz es el del teorema de Gerschgorin, que dice que si A 2 Rnn es una matriz simétrica con valores propios 1 ; 2 ; : : : ; n , entonces 8 9 ˆ > ˆ > n < = X mKın i  mKın ai i jaij j ; 1i n 1in ˆ > ˆ > j D1 : ; j ¤i 8 9 ˆ > ˆ > n < = X mKax i  mKax akk C jakj j : > 1kn 1kn ˆ ˆ > j D1 : ; j ¤k

Se dice que una matriz compleja A, de coeficientes aij , cuadrada y de orden n, es de diagonal estrictamente dominante por filas, o simplemente de diagonal dominante por filas, cuando cumple que X jaij j; i D 1; : : : ; n: jai i j > j ¤i

Puede darse una definición análoga de matriz de diagonal dominante por columnas.

6 Topología En un espacio vectorial normado se define una bola abierta, S.x0 ; r/, de centro x0 y radio r, como el conjunto de puntos x que verifican kx x0 k < r. Es decir: S.x0 ; r/ D fx 2 Rn W kx

x0 k < rg:

N 0 ; r/, se define, por el contrario, como el conjunto de puntos x que verifican Una bola cerrada, S.x kx x0 k  r. Es decir: N 0 ; r/ D fx 2 Rn W kx x0 k  rg: S.x Consideraremos en lo que sigue de este apartado un subconjunto S del espacio vectorial métrico hasta ahora estudiado (puede ser, por ejemplo, Rn ). Un punto y 2 S es un punto interior del conjunto S si existe un " tal que kx

yk < " ) x 2 S :

En otras palabras, existe una bola abierta S.y; "/ de centro y y radio " contenida íntegramente en S. El conjunto de todos los puntos interiores del conjunto S se denomina interior de S . Este conjunto puede, evidentemente, ser vacío. Ejemplo: un plano del espacio R3 . Un subconjunto de S se dice abierto si coincide con su interior; es decir, si alrededor de todo punto de S existe una bola abierta contenida íntegramente en S. Dos ejemplos: la bola abierta unidad, 20

S.x; 1/ D fx W kxk < 1g y el espacio Rn en su totalidad. En general los subconjuntos o conjuntos abiertos se caracterizan por no tener límites definidos o ser disjuntos de su frontera (ver más adelante la definición del concepto frontera). Un entorno de un punto x, E.x/, es un conjunto abierto que contiene a x. En otras palabras, E.x/ es un entorno de x si contiene una bola abierta de centro x. Se dice que un punto x es un punto de acumulación del subconjunto S si en todo entorno de x existen un número infinito de puntos de S . Un punto x se denomina punto de adherencia del subconjunto S cuando todo entorno de dicho punto x contiene al menos un punto de S ; es decir, para todo " existe un y 2 S tal que kx yk < ". El conjunto de todos los puntos de adherencia se denomina adherencia —en la literatura anglosajona y latinoamericana, clausura cl.S/—. La adherencia de la bola abierta S.x; 1/ D fx W kxk < 1g es la cerrada SN .x; 1/ D fx W kxk  1g. Se denomina frontera de un conjunto a la parte de la adherencia que no está en el interior. Un conjunto, o subconjunto, se dice cerrado si coincide con su adherencia. La adherencia de cualquier conjunto S es el conjunto cerrado más pequeño que contiene a S . Se puede demostrar que un conjunto es cerrado si y sólo si toda sucesión convergente de elementos de S tiene un límite en ese conjunto. Un conjunto, o subconjunto, se dice compacto si es cerrado y acotado (contenido en una bola de radio r < 1). Un importante resultado, debido a Weierstrass, dice que si S es un conjunto compacto, de cada sucesión o sucesión infinita fx .n/ gn2N de elementos de dicho conjunto es posible extraer una subsucesión n o x .`/ LN `2L

que converge a un elemento del propio conjunto S . Si fr .k/ g es una sucesión de números reales y s .k/ D sup fr .i / W i  kg, entonces fs .k/ g converge a un número real s0 ; a este número se le denomina límite superior de fr .k/ g y se expresa como     o lKım r .k/ : lKım sup r .k/ k!1

El límite superior de una sucesión de números reales es el mayor punto de acumulación de la sucesión. De forma similar se define el límite inferior.

7 Teorema de la proyección Gran parte de las teorías de sistemas de ecuaciones y de optimización que se estudian en la asignatura están basadas en unos pocos resultados simples e intuitivos. Entre estos, quizás el más sencillo y usado sea el teorema de la proyección. Su aplicación en la teoría de mínimos cuadrados lineales es fundamental. En un espacio Euclídeo ordinario de tres dimensiones determina que la distancia más corta de un punto exterior a un plano a ese plano la proporciona la perpendicular al plano desde dicho punto. La expresión formal de este teorema en espacios de Hilbert es la que sigue. Teorema 7.1 Sea H un espacio de Hilbert y M un subespacio cerrado de H . Para todo vector x 2 H existe un único vector m0 2 M tal que kx m0 k2  kx mk2 , para todo m 2 M . La condición necesaria y suficiente además para que m0 2 M sea el vector mínimo único es que x m0 sea ortogonal a M . D EMOSTRACIÓN . Primero probaremos que si m0 es un vector que minimiza kx mk, x m0 es ortogonal a M . Supongamos para ello, por el contrario, que existe un m que no es ortogonal a x m0 ; 21

sin pérdida de generalidad podemos suponer que kmk D 1 y que hx el vector m1 2 M como m1 D m0 C ım. Tendremos que kx

m1 k22 D kx D kx

m0 ımk22 D kx m0 k22 jıj2 < kx

m0 k22 hx m0 k22 :

m0 jımi

m0 jmi D ı ¤ 0. Definamos hımjx

m0 i C jıj2

De esta manera, si x m0 no es ortogonal a M , m0 no es el mínimo que decíamos. Veamos ahora cómo, si x m0 es ortogonal al subespacio M , m0 es el único vector de M que minimiza kx mk2 . En efecto, para todo m 2 M , el teorema de Pitágoras dice que kx

mk22 D kx

m0 C m0

mk22 D kx

m0 k22 C km0

mk22 :

Por lo tanto kx mk2 > kx m0 k2 para m ¤ m0 . Demostraremos ahora la existencia de un m0 que minimiza kx mk2 . Si x 2 M , entonces m0 D x y todo estaría probado como es obvio. Si x … M , definamos un ı D Kınfm2M kx mk2 ; lo que queremos es obtener un m0 2 M tal que kx m0 k2 D ı. A tal fin, sea fm.i / g una M >talfque m.i / kx2 2!,ı.xPor deldistancia me tal sucesión que jx de x  jvectores < . Si en f .x/ .x  /kx para todo ¤ xla ,ley a una 4   paralelogramo se tiene que x , se dice que x es un mínimo relativo estricto de f en .

.j /

2 .j /

2

2 /

.m x/ C .x Proposición m.i / / 2 C 8.1 .m (Condiciones x/ .x necesarias m.i / / 2 de D primer 2 m.jorden) x Sea C 2  un subconjunto d

1  2 , para toda direcc función f W  ! R, f 2 C . Si x en un mínimoC2 relativo

x de m.if/ en : 2   factible desde x , se cumple que rf .x /d  0. Reordenando, se obtiene 1

8.2 Sea Rn y una

2Corolario

2  un

subconjunto

2 de .i / función .j / 2f W  ! R, f 2 C .

m C m

.j /

.j /

f en  y x .i /es

cumple interior de , se que rf .x  / D 0 m.i / mínimo D 2 mrelativo x de C 2 x m un punto 4

m

x

: 2 2 2 2 2

8.3está (Condiciones necesarias de segundo orden)(lineal). Sea  De un la subconjunto d .i / Para todo i; j , el vector .mProposición C m.j / /=2 en M pues éste es un espacio vectorial 2 función W .i/ C !m R,.jf/ /=2k 2C  . Siı,xporenloun mínimo relativo de f en , para toda direcc definición de ı se deduce que kx f.m que 2 factible desde x  , se cumple que:

2

2

.i.j

.j /

.j / .i / 2 .i / 2 2 .i / 2 / / m m  2 m x C 2 x m 4ı 2i;: j ! 1. Es decir, fm.i / g es Como km xk2 ! ı cuando 0 cuando

i ! 1,rf

km.x  /d

m k0: 2 ! 2 una sucesión de Cauchy;2 como MExercise es un subespacio cerrado, la 2sucesión fm.i / g tiene un límite m0 en  Si rf .x Dı.0; entonces d T r 2 f .x  /d .i/ 0: 2 debido / .i / 2 m0 k/d M a la continuidad la .jnorma, ! xky, ! ı 2 cuando i ! 1,dekm mkx k ! 02 cuando i; j ! 1. Es decir, fm g es

Como km.i / 2 2 una sucesión de Cauchy; como M es un subespacio cerrado, la sucesión fm.i / g tiene un límite m0 en given two n-vectors 6= 0, y pone en evidencia que El teorema de laxproyección la solución del problema Proposición 8.4kx (Condiciones necesarias de segundo orden) Sea x  un punto interior M y, debido a la continuidad de la norma, m0 k2 ! ı. póngase que también unminimizar mínimo relativo de f W  ! R, f 2 C 2 . Entonces: ktx yk t ktx − yk minimize (over t)la El teorema de la proyección pone en evidencia que solución del problema  / D 0: es el vector proyección ortogonal de y sobre x: txrf en.x la figura. minimizar ktx yk Para todo d; d T r 2 f .x  /d  0:

geometrically, tx is the projection t of a vector y on the line through 0 and x

es el vector proyección ortogonal de y sobre x: tx en la figura. Proposición 8.5 (Condiciones suficientes de segundo orden) Sea f 2 C 2 una función x interior. Supóngase además que: una región en la cual x  es un punto

tx .x  / D 0: rf

La matriz Hessiana r 2 f .x  / es definida positiva:

y

x  es entonces un mínimo relativo estricto de f .

0 4 Para

u, w 2 M , ju C wj2 C ju

D 2juj2 C 2jwj2 . convexos 9wj2Conjuntos

8 Conjuntos convexos

22 n

Vectors

convexo y sólo para todo de puntos x1 ; x2 2 C convexo  R sesi dice Un conjunto Un C conjunto Rn se dice y sólo si para si todo par desi puntos x1 ; xpar 2 2 C todas las 1-20 combinaciones de la forma x D x C .1 /x , con 0    1, están en C . Es decir 1 0    1,2están en C . Es decir, cuando combinaciones de la forma x D x1 C .1 /x2 , con para cada par puntosconvexo, del conjunto convexo, todos los puntos de laestán recta los une están en cada par de puntos del de conjunto todos los puntos de la recta que los une enque el conjunto.

x  es entonces un mínimo relativo estricto de f .

9 Conjuntos convexos

8 Conjuntos convexos

se dice si ytodo sólopar si de para todoxpar de puntos x ; x 2 C tod Un C conjunto C dice  R Un conjunto  Rn se convexo si yconvexo sólo si para puntos 1 ; x2 2 C todas 1las 2 combinaciones .1 0 /x con 0 enC. Es 1, decir, estáncuando en C . Es combinaciones de la formadex la Dforma x1 Cx.1D x /x12 C , con  están paradecir, cuand 2 , 1, cada par de puntos delpuntos conjunto todos los puntos de la que de los la une estánque en el cada par de delconvexo, conjunto convexo, todos losrecta puntos recta losconjunto. une están en el con n

24

2 Conjunto convexo

Convex sets

Conjunto no convexo

La expresión x D x1 C .1 /x2 , 0    1, define la combinación convexa de x1 y x2 . Si 0 <  < 1, es decir  2 .0; 1/, la combinación se denomina estrictamente convexa. La expresión x D x1 C .1 /x2 , 0    1, define la combinación convexa de x1 y El concepto se la puede generalizarse a cualquier finito de convexa. puntos de 0 < de c y H D x 2 Rn W aT x < c . Los semiespacios de borde H son convexos; la unión de HC y H es el espacio Rn .

a H+ x¯0 a

y H−

H

Hiperplano x1 4x C 24xD lossemiespacios semiespacios en R R2 2 D FiguraFigura 8.10: 8.10: Hiperplano x1 C 1111y ylos en los losque quedivide divide 2

En la figura se representa ellahiperplano x1 C4x2 elDdesplazamiento 11, su vector característico Œ 1; 4T En un 8.10 hiperplano aT x D c, constante c determina del hiperplano a delDorigen. Un hiperplanoH seCpuede de la forma fx W aT .x x0 / D 0g, donde x0 es cualquier punto del y los semiespacios y H expresar . T hiperplano (a xa0T D Esalaúltima expresión se puede trabajar un poco másdel pueshiperplano fx W aT .x del x0origen. /D En un hiperplano x c). D c, constante c determina el desplazamiento ? ? T 0g D x0 C a , donde a es el complemento ortogonal de a, es decir fv W a v D 0g. Lo que lleva Un hiperplano se puede expresar de la forma fx W aT .x x / D 0g, donde x es cualquier punto del a que unT hiperplano consiste en un desplazamiento x0 más0 todos los vectores0 ortogonalesT al vector hiperplano (a x0 Da:c). Esa última expresiónde seapuede trabajar un poco más pues fx W a .x x0 / D T característico el conjunto de soluciones x D c: x0 C ker.a/, recordemos. ? ? 0g D x0 C a , donde a es el complemento ortogonal de a, es decir fv W aT v D 0g. Lo que lleva

Un politopo es un conjunto formado por la intersección de un número finito de semiespacios cerrados. Un politopo cónico es un conjunto formado por la intersección de un número finito de semiespa25 cios cerrados que pasan por un punto. B.3y no Separating Supporting Hyperplanes Un poliedro es un politopo acotado vacío. Es fáciland comprobar que la intersección de conjuntos 519 convexos es convexa y que por lo tanto los politopos y los poliedros son conjuntos convexos. En esta figura se muestran varios politopos; el del centro es un poliedro.

a que un hiperplano consiste en un desplazamiento x0 más todos los vectores ortogonales al vector característico a: el conjunto de soluciones de aT x D c: x0 C ker.a/, recordemos. Un politopo es un conjunto formado por la intersección de un número finito de semiespacios cerrados. Un politopo cónico es un conjunto formado por la intersección de un número finito de semiespacios cerrados que pasan por un punto. B.3 Separating and Supporting Hyperplanes 519 Un poliedro es un politopo acotado y no vacío. Es fácil comprobar que la intersección de conjuntos convexos es convexa y que por lo tanto los politopos y los poliedros son conjuntos convexos. En esta figura se muestran varios politopos; el del centro es un poliedro.

Si un politopo P es un poliedro, cualquier punto se puede expresar como combinación convexa de Fig. B.5 Polytopes sus puntos extremos. Teorema 8.1 Sea C un conjunto convexo e y un punto exterior a la adherencia de C . Existe un vector a tal que aT y < Kınfx2C aT x.

It is easy to see that half spaces are convex sets and that the union of H+ and EMOSTRACIÓN . Sea HD − is the whole space. Definition.

ı D Kınf kx x2C

yk2 > 0:

A set which can be expressed as the intersection of a finite number

Existe un x0 en la frontera de C tal que kx0 yk2 D ı. Esto es así pues la función continua of Dclosed half spaces is said to be a convex polytope. f .x/ kx yk 2 alcanza su mínimo en cualquier conjunto cerrado y acotado por lo que sólo es necesario considerar x en la intersección de la adherencia de C y la bola abierta de centro y y radio 2ı. We see that convex polytopes are the sets obtained as the family of solutions to aAset of linearprobaremos inequalities continuación que of a Dthe x0 form y satisface las condiciones del enunciado del teorema. En efecto, para cualquier ˛, 0  ˛  1, al ser C un conjunto convexo, el punto x0 C ˛.x x0 / 2 C , por lo que a1T x  b1 kx0 C ˛.x a xT0 /x  ykb22  kx0 yk22 : Desarrollando,

2

2

· · 2˛.x0 y/T .x x0 / C ˛ 2 kx x0 k22  0: · · Considerando esta expresión cuando ˛ ! 0C, se tiene que · · T T .x0 ay/x .x x0 /  0 m  bm  o que

since each individual Tinequality defines a half space and the solution family is .x0 y/ x  .x0 y/T x0 D .x0 y/T y C .x0 y/T .x0 y/ the intersection of these half spaces. (If some a = 0, the resulting set can still, as D .x0 y/Tiy C ı 2 : the reader may verify, be expressed as the intersection of a finite number of half Haciendo a D x0 y queda probado el teorema. spaces.) Several polytopes are illustrated in es Fig. note that a polytope may ybe La interpretación geométrica de este teorema que,B.5. dadoWe un conjunto convexo C y un punto exteriorbounded, a la adherencia C , existe un hiperplano a y, sin tocar a C , estando C en is unoof empty, or de unbounded. The caseque ofcontiene a nonempty bounded polytope de sus semiespacios abiertos. Este hiperplano (de vector característico a en el teorema) se denomina special interest and we distinguish this case by the following. hiperplano separador de C e y. Definition.

A nonempty bounded polytope is called a polyhedron. 26

Si C y D son dos conjuntos convexos disjuntos, C \ D D ;, existe entonces un a ¤ 0 y un b tales que aT x  b, para todo x 2 C , y aT x  b, para todo x 2 D. ˚Dicho de otra manera, la función aT x b es no positiva en C y no negativa en D. El hiperplano x W aT x D b es un hiperplano separador de los conjuntos C y D.

aT x ≤ b

aT x ≥ b

D C a

Existen bastantes principios de dualidad T que se usan en la asignatura, en especial en la teoría y Figurede 2.19 The hyperplane {x | aun xproblema = b} separates thededisjoint sets vectorial técnicas optimización, que relacionan en términos vectoresconvex en un espacio T C and D. The affine function a x − b isennonpositive and nonnegative con otro expresado en términos de subespacios ese espacio. on En C gran cantidad de esos principios on D. está presente la relación que se ilustra en la figura que sigue. La distancia más corta de un punto a un conjunto convexo es igual al máximo de las distancias desde el punto a los hiperplanos que separan el conjunto convexo del punto. El problema original de minimización sobre vectores se convierte en otro de maximización sobre hiperplanos.

Figura 8.11: Distancia más corta de un punto a un conjunto convexo en términos de las distancias a hiperplanos separadores

Teorema 8.2 Sea C un conjunto convexo e y un punto frontera de C . Existe un hiperplano que contiene a y y a C en uno de sus semiespacios cerrados. D EMOSTRACIÓN . Sea fy .k/ g una sucesión de puntos exteriores a la adherencia de C . Sea fa.k/ g la sucesión de puntos normalizados, ka.k/ k2 D 1, obtenida de aplicar el teorema anterior a la sucesión anterior, tales que,  T  T a.k/ y .k/ < Kınf a.k/ x: x2C

27

2.6

2.6.1

Como fa.k/ g es una sucesión acotada, una subsucesión fa.k/ g, k 2 H, convergerá a un límite a. Para este a se tiene que, para cualquier x 2 C ,  T  T aT y D lKım a.k/ y .k/  lKım a.k/ x D aT x: k2H

k2H

Un hiperplano que contiene un conjunto convexo C en uno de sus semiespacios cerrados y que contiene algún punto frontera de C se denomina hiperplano de apoyo de C . acuerdo con esta el teorema anterior dice que, dado un conjunto convexo C y 2.6 DeDual cones anddefinición, generalized inequalities un punto frontera y de C , existe un hiperplano de apoyo de C que contiene y. En esta figura

a x0 C

˚ x W aT x DFigure aT x0 2.21 es el hiperplano de apoyo{x de| C : el punto x y elxconjunto C esThe hyperplane aTen x el = punto aT x0 }x0supports C0 at 0. ˚ T T por el el hiperplano ˚tán separados hiperplano x W a x D a x0 . Geométricamente ˚quiereTdecir que T T T x W a x D a x0 es tangente al conjunto C en x0 y el semiespacio x W a x  a x0 contiene a C. that the8.3 point x0 and the set C are separated by the hyperplane {x | aT x = aT x0 }. Lema (Farkas) El sistema de ecuaciones

The geometric interpretation is that the hyperplane {x | aT x = aT x0 } is tangent 0; T b; to .IC/ at x0 , and the halfspace {xAx | aD x ≤ aTxx 0 } contains C. This is illustrated in figure 2.21. no tiene solución si y sólo si la tiene el sistema A basic result, called the supporting hyperplane theorem, states that for any .II / y T A  0T ; bT y > 0; nonempty convex set C, and any x0 ∈ bd C, there exists a supporting hyperplane to 2 Rmn . C donde at x0 .A The supporting hyperplane theorem is readily proved from the separating hyperplane theorem. We distinguish two cases. If the interior of C is nonempty, D EMOSTRACIÓN . El lema se puede reformular de la siguiente manera. Si existe un x  0 tal que the result follows immediately by applying the separating hyperplane theorem to Ax D b, no existe ningún y tal que y T A  0T y bT y > 0. Recíprocamente, si no existe ningún T the and int C. If 0 }Ax x sets 0 tal{x que D b, existe un the y talinterior que y T A of  0CT yisbempty, y > 0. then C must lie in an affine set of dimension than n, and any hyperplane containing contains Supongamos queless el sistema (I) tiene una solución x tal que Ax D b y that x  0.affine Sea yset un punto tal T T T T T T T Cque and is aeste (trivial) supporting y xA0 ,and 0 . En caso b y D x A y hyperplane.  0 pues x  0 y y A  0 . Esto demuestra que bTThere y no puede ser positivo y, por lo tanto, elofsistema (II) no tiene solución. is also a partial converse the supporting hyperplane theorem: If a set is closed, has nonempty hassolución. a supporting hyperplane point Supongamos ahora que el interior, sistema (I)and no tiene Esto quiere decir que bat… every S D fv D x  0g; es decir queitb is no convex. pertenece al politopo cónico2.27.) S. Observando la figura 8.12, está claro inAx itsW boundary, then (See exercise que si b … S, existe un hiperplano separador definido por un y, que separa S y b, y para el cual y T ai  0, i D 1; : : : ; n y y T b > 0, es decir, y forma un ángulo de más de 90 grados con cada uno

Dual cones and generalized28 inequalities Dual cones

5

8.1 Dualidad y condiciones de o´ptimo

473

Politopo c´ onico S

a3

a2

a1

a4

a5

Hiperplano

b∈ /S y

Figura 8.2 Figura 8.12: Demostración del lema de Farkas

Descripci´ on geom´etrica de la existencia de un hiperplano separador

de los vectores columna de A y de menos de 90 grados con5 b. Esto verifica que el sistema (II) tiene El par (P)-(D) se denomina habitualmente, en la literatura especializada, forma sim´etrica solución. de la dualidad. A continuaci´ on exponemos dos teoremas que caracterizan las soluciones o´ptimas del par de

Elproblemas lema de Farkas es un resultado importante para el estudio de sistemas lineales de igualdades y primal-dual. desigualdades. Su interpretación geométrica es la siguiente: Teorema 8.3 (Complementariedad de Holguras) Sean x e y soluciones factibles del par de

1. Siprogramas ai ; i D 1; :primal-dual : : ; n, son los vectores columna de la matriz A, que cumpla quenecesarias b D Ax, xy  0, ennforma etrica (P)-(D) de (8.8). Lassecondiciones Pn sim´ quiere decir que el vector b D a x , x  0; en otras palabras, que b pertenece al politopo i i respectivos i suficientes para que sean o ´ptimosi D1 de sus problemas son: cónico generado por los vectores columna de A. En la figura 8.13 se muestra un ejemplo donde T = 0 al cono generado por a1 , a2 (8.9) (cT − el sistema (I) no tiene solución: el vector b ynoA)x pertenece , a3 y an . T T Lay intersección del cono fy W y A  0 g (conjunto formado por los vectores y que forman un ángulo mayor o igual de 90ı con los vectores abierto y T (Ax −columna b) = 0. de la matriz A) y el semiespacio (8.10) T fy W b y > 0g, no es el conjunto vacío: el sistema (II) tiene solución, pues b y cualquier y en el cono que define la zona sombreada forma un ángulo menor de 90ı y, por lo tanto, bT y > 0. ´ n. Como x e y son soluciones factibles de (P) y (D), respectivamente, se tiene Demostracio

2. El sistema (II) no tiene solución si la intersección del cono fy W y T A  0T g y el semiespacio que s = Ax −b≥ x ≥ 0 8.14 se muestra un ejemplo(8.11) abierto fy W bT y > 0g es el conjunto vacío. En0,la figura donde el sistema (II) no tiene solución. Todo vector y en la zona que define el cono indicado forma un y ángulo mayor de 90ı con b. La tiene al cono generado por a1 , a2 wT =sin cT embargo − y T A ≥(I) 0Tpues , yb≥pertenece 0. (8.12) y an .

9 Funciones Recordemos que una función es un caso particular de aplicación donde los conjuntos origen e imagen son conjuntos de números. 5 El hiperplano separador del politopo cónico S de la figura debería “casi” tocar a éste a lo largo de a . El hiperplano de apoyo correspondiente, sí 5 tocaría a a5 .

29

474

Cap´ıtulo 8. Dualidad y an´ alisis de sensibilidad

Semiespacio abierto {y : bT y > 0}

a2 an a1

a3 b

Cono {y : y T A ≤ 0T }

Figura 8.3 no tiene solución; si (II) Figura 8.13: El sistema (I) del lema de Farkas El sistema (I) del lema de Farkas no tiene soluci´ on. La tiene (II)

Una función f W Rn ! R se dice continua en x si para toda sucesión fx .k/ g que converge a x (expresado x .k/ ! x), se cumple que fa2.x .k/ / ! f .x/. De forma equivalente, f se dice continua en x si dado un " > 0, existe un ı > 0 tal que ky

a1

xk < ı H) kf .y/

an f .x/k < ":

b

Una función f W R ! R se dice satisface la condición de Lipschitz con constante en un conjunto X , si para todo x e y pertenecientes a X se cumple que Semiespacio abierto {y : bT y > 0} jf .x/

f .y/j  jx

yj:

Una función que satisface la condición de Lipschitz en un conjunto X se dice continua -Lipschitz en ese X, designándose f 2 Lip .X/. Dada una norma vectorial k
k en Rn y otra matricial k
k en Rmn , m; n > 0, una función T Cono {y : yde ALipschitz ≤ 0T } con constante en un abierto D  Rn , si g W Rn ! Rmn se dice satisface la condición para todo x e y pertenecientes a D se cumple que kg.x/

g.y/k  kx Figura 8.4

yk:

El sistema del lema Farkas no on. La tiene (I) Una función g que satisface la (II) condición de de Lipschitz en tiene D se soluci´ dice continua

-Lipschitz en ese D, designándose g 2 Lip .D/. Un resultado muy interesante referido a funciones continuas es el teorema de Weierstrass, que dice que una función continua definida en un conjunto compacto S tiene un punto donde alcanza un mínimo en S . Es decir, existe un x  2 S tal que para todo x 2 S , f .x/  f .x  /. Un conjunto de funciones f1 ; f2 ; : : : ; fm de Rn en R se puede considerar como una función vectorial f D Œf1 ; f2 ; : : : ; fm T :

Esta función asigna a todo vector x 2 Rn otro vector f .x/ D Œf1 .x/; f2 .x/; : : : ; fm .x/T de Rm . Tal función vectorial se dice continua si lo es cada uno de sus componentes f1 ; f2 ; : : : ; fm . Si cada uno de los componentes de f D Œf1 ; f2 ; : : : ; fm T es continua en algún conjunto abierto de Rn , se dice f 2 C . Si además cada función componente tiene derivadas parciales de primer 30

Figura 8.3 El sistema (I) del lema de Farkas no tiene soluci´ on. La tiene (II) a2 an a1

b Semiespacio abierto {y : bT y > 0}

Cono {y : y T A ≤ 0T }

Figura 8.14: El sistema (II) no tiene Figura 8.4 solución. La tiene (I)

El sistema (II) del lema de Farkas no tiene soluci´ on. La tiene (I)

orden continuas en ese abierto, se dice que f 2 C 1 . En general, si las funciones componentes tienen derivadas parciales de orden p continuas, se indica f 2 C p . Si f W Rn ! R y f 2 C 1 , se define el vector gradiente de f como el vector   @f .x/ @f .x/ @f .x/ T rf .x/ D ; ;:::; : @x1 @x2 @xn También se puede ver expresado alguna vez como fx .x/. Si f 2 C 2 , se define la Hessiana, o matriz Hessiana, de f en x como la matriz n  n 2 2 3 @2 f .x/ @ f .x/ @2 f .x/


6 @2 x 1 @x1 @x2 @x1 @xn 7 6 7 6 @2 f .x/ @2 f .x/ 7 2 @ f .x/ 6 7


6 7 2 r 2 f .x/ D 6 @x2 @x1 @ x2 @x2 @xn 7 : 6 7 :: :: :: :: 6 7 : : : : 6 7 4 @2 f .x/ @2 f .x/ @2 f .x/ 5


@xn @x1 @xn @x2 @2 xn A esta matriz también se la puede ver designada como F .x/. Para una función vectorial f D Œf1 ; f2 ; : : : ; fm T , si f 2 C 1 , simplemente, la Jacobiana, como la matriz m  n 2 @f1 .x/ @f1 .x/


6 @x @x2 1 6 6 @f .x/ @f .x/ 2 2 6


6 rf .x/ D J .x/ D 6 @x1 @x2 6 :: :: :: 6 : : : 6 4 @fm .x/ @fm .x/


@x1 @x2

se define la matriz Jacobiana o, @f1 .x/ @xn @f2 .x/ @xn :: : @fm .x/ @xn

3

7 7 7 7 7 7: 7 7 7 5

Si f 2 C 2 , es posible definir m Hessianas F1 .x/; F2 .x/; : : : ; Fm .x/ correspondientes a cada una 31

de las m funciones componentes. Teorema 9.1 Teorema de Taylor. Si f W Rn ! R y f 2 C 1 en una región que contiene el segmento Œx1 ; x2 , es decir puntos ˛x1 C .1 ˛/x2 ; 0  ˛  1, existe un , 0    1, tal que
f .x2 / D f .x1 / C r T f x1 C .1 /x2 .x2 x1 / : Además, si f 2 C 2 , existe un ; 0    1, tal que f .x2 / D f .x1 / C r T f .x1 /.x2

1 x1 / C .x2 2

x1 /T F x1 C .1


/x2 .x2

x1 / ;

donde F denota la matriz Hessiana de f . Si la función f W R ! R es continua y derivable k C 1 veces en un intervalo, o segmento, Œx; x0 , existe un b entre x y x0 tal que
f 00 .x0 / x0 C x 2Š
k f .kC1/ .b/ x0 C x .k C 1/Š

f .x/ D f .x0 / C f 0 .x0 / x f .k/ .x0 / C x kŠ

x0 x0


2

C


kC1

:

f 000 .x0 / x 3Š

x0


3

C




Figura 9.15: Función sen.x/ y, en x D 0, las aproximaciones por Taylor de primer orden, de orden 3, 5, 7, 9, 11 y 13

Una función f W Rn ! R se dice convexa si cumple que f .˛x C ˇy/  ˛f .x/ C ˇf .y/ para todo x; y 2 Rn y todo ˛; ˇ 2 R, con ˛ C ˇ D 1, ˛  0, ˇ  0. Una función f W Rn ! Rm es afín si es la suma de una función lineal y una constante; es decir, tiene la forma f .x/ D Ax C b, donde A 2 Rmn y b 2 Rm . Si S  Rn es un conjunto convexo y f W Rn ! Rm es una función afín, la imagen de f .S/ D ff .x/ W x 2 S g es un conjunto convexo. De forma similar, si f W Rk ! Rn es una función afín, la

32

7.4 Convex and Concave Functions

193

y y = f(x)

convex (a) Figura 9.16: Función convexa

imagen inversa f

1

x

.S/ D fx Wf f .x/ 2 Sg también es convexa.

Teorema 9.2 Teorema del valor intermedio. Si f W R ! R es una función continua en el intervalo Œa; b, toma todos los20 valores entre f .a/0 yFundamentals f .b/. Más concretamente, si y es un número entre f .a/ | CHAPTER y f .b/, existe un número c dentro de Œa; b, es decir, tal que a  c  b, en el que f .c/ D y.

f(c)

f(

y

x

convex (b) a c f

b

a

b

c (b)

(a)

9.3 Teorema del valor medio. Si f W R ! R es una función continua
y derivable en el CHAPTER Teorema 0 Fundamentals 0 intervalo Œa; b, existe un número c entre a y b tal que f .c/Figure D f 0.1 .b/ Three f .a/important =.b a/.theorems from calculus.

a and b such that: (a) f (c) = y, for any given y betwee 0.4, the Intermediate Value Theorem (b) the instantaneo (f (b) − f (a))/(b − a) by Theorem 0.6, the Mean Value f(c) region is equal in area to the horizontally shaded regio Value Theorem for Integrals, shown in the special case

f(c) y

(Intermediate Value Theorem) Let f be a continuous f f realizes every value between f (a) and f (b). More x nonconvex f (a) and f (b), then there exists a number c with a ≤

THEOREM 0.4

a c

b (a)

a

c

(c) (b)

b

a

c

b

(c)

2 − 3 on en Fig. 7.3f Convex and functions Teorema 9.4 Teorema de Rolle. Si W R ! 0.7 R esnonconvex una función continua intervalo[1, 3] must ta  EXAMPLE Show that f (x) = yxderivable theel0interval Œa; b y suponemos que f .a/ f .b/,important existe entonces un número c entre aThere y b tal quenumbers f .c/ Dc 0. Figure 0.1DThree theorems from calculus. exist between

f (1) −2 fand f (3) = 6, all values a and b such that: (a) f (c) = y, for any givenBecause y between f (a)=and (b), by Theorem √ 1, must taken on byslope f . For setting c = 3 0.4, the Intermediate Value Theorem (b) thebeinstantaneous of fexample, at c equals f (2) = 1. (f (b) − f (a))/(b − a) by Theorem 0.6, the Mean Value Theorem (c) the vertically shaded 33 secondly, region is equal in area to the horizontally shaded region, by Theorem 0.9, the Mean Value Theorem for Integrals, shown in the special case g(x) = 1. THEOREM 0.5

(Continuous Limits) Let f be a continuous function in

Teorema 9.5 Teorema del valor medio de las integrales. Si f W R ! R es una función continua en el intervalo Œa; b y g W R ! R una función integrable que no cambia de signo en Œa; b, existe entonces un número c entre a y b tal que Z b Z b f .x/g.x/ dx D f .c/ g.x/ dx: a

f(c)

a

f (c)

a

b

c

a

(b)

c

b (c)

9.1 Condiciones necesarias y There suficientes de primer y segundo orden que ha de cumplir un Three important theorems from calculus. exist numbers c between

ch that: (a) f (c) =punto y, for mínimo any given y between f (a) and f (b), by Theorem ermediate ValueSeTheorem (b) thecondiciones instantaneous slope ofy fsuficientes at c equals trata de definir necesarias para determinar si un punto x  cumple )/(b − a) by Theorem 0.6, the Mean Value Theorem (c) the vertically shaded minimizar f .x/; qual in area to the horizontally shaded region, by Theorem x 0.9, the Mean em for Integrals, n dondeshown f W  in!the R yspecial  2 Rcase . g(x) = 1.

Un punto x  2  se dice que es un mínimo local de la función f W  ! R si existe un  > 0 tal que fLet .x/ f be f .xacontinuous / para todo xfunction 2  a unaondistancia menor[a, queb].  de x  . Es decir, para todo x 2  alue Theorem) the interval Then  tal quefjx(a) xand j precisely, f .x  / paraiftodo , x ¤between x  , a una distancia menor que  de y value between (b). y isxa 2number   x , se dice que x es un mínimo local estricto de f en .

then there exists a number c with a ≤ c ≤ b such that f (c) = y.



Teorema 9.6 Condiciones necesarias de primer orden Sea  un subconjunto de Rn y una función f W  ! R, f 2 C 1 . Si x  en un mínimo local de f en , se cumple que rf .x  / D 0.

= x 2 − 3 onSithe interval [1, 3] must take on the values 0 and 1. en x  se cumple que rf .x  / D 0, al punto x  se le denomina estacionario.

se f (1) = −2 and f 9.7 (3) Condiciones = 6, all values between −2 and 6, including 0 and Teorema necesarias de segundo orden Sea  un subconjunto de Rn y una función √ √  f W example,  ! R, f setting 2 C 2 . Sic x= en 3, un note mínimo local de f=en que rf .x  / D 0 y r 2 f .x  / n on by f . For that f (c) f , ( se 3)cumple = 0, and es semidefinida positiva. = 1. 

Teorema 9.8 Condiciones suficientes de segundo orden Sea  un subconjunto de Rn y una función f W  ! R, f 2 C 2 . Si se cumple que rf .x  / D 0 y r 2 f .x  / es definida positiva, x  en un mits) Let f mínimo be a continuous function local estricto de f en in .a neighborhood of x0 , and assume

0.

Then

Teorema 9.9 Si f es convexa, mínimo local x  es un mínimo global de f . Si además f  cualquier  es cualquier mínimo local x ). es un mínimo global de f . limderivable, f (x f (x ) = f lim x =

n→∞

n

n→∞

n

0



rds, limits may be brought inside continuous functions.

heorem) Let f be a continuously differentiable function on the interval re exists a number c between a and b such that f (c) 34 = (f (b) − f (a))/ 

10 Teorema de la función implícita Teorema 10.1 Sea x0 D .x01 ; x02 ; : : : ; x0n / un punto de Rn que satisface estas condiciones: (a) Las m funciones fi 2 C p , i D 1; 2; : : : ; m, en algún entorno de x0 , para alguna p  1.

(b) fi .x0 / D 0; i D 1; 2; : : : ; m:

2

6 6 (c) La matriz Jacobiana de la función vectorial, rf .x0 / D 6 6 4 regular.

@f1 .x0 / @f1 .x0 /


@x1 @xm :: :: :: : : : @fm .x0 / @fm .x0 /


@x1 @xm

3

7 7 7, es 7 5

Entonces existe un entorno de xO 0 D .x0mC1 ; x0mC2 ; : : : ; x0n / 2 Rn m tal que para xO D O i D 1; 2; : : : ; m tales que: .xmC1 ; xmC2 ; : : : ; xn / en ese entorno existen funciones i .x/, (i) i 2 C p .

(ii) x0i D i .xO 0 /; i D 1; 2; : : : ; m.

O 2 .x/; O : : : ; m .x/; O x/ O D 0; i D 1; 2; : : : ; m. (iii) fi .1 .x/; Este teorema —cuyos orígenes están asociados a Newton, Leibnitz y Lagrange, pero que fue formulado por Cauchy— es muy útil para respaldar la caracterización de puntos óptimos en programación matemática con y sin condiciones, solución de ecuaciones lineales y no lineales y muchos otros aspectos que analizamos en la asignatura. Supóngase que se tiene una función vectorial f W Rn ! Rm que cumple fi .x/ D 0;

i D 1; 2; : : : ; m:

El teorema de la función implícita estudia, si n m de las variables son fijas, si el problema se puede resolver en m incógnitas. Es decir, si x1 , x2 ; : : : ; xm se pueden expresar en función de las restantes n m de la forma xi D i .xmC1 ; xmC2 ; : : : ; xn / ; i D 1; 2; : : : ; m: A las funciones i W Rn

m

! R, si existen, se las denomina funciones implícitas.

Ejemplo 10.1 Consideremos la ecuación x12 C x2 D 0. Una solución de la misma es x1 D, x2 D 0. En un entorno de esta solución, sin embargo, no hay función  tal que x1 D .x2 /. En esta solución no se cumple la condición .c/ del teorema de la función implícita. En cualquier otra solución si existe u dicha . Ejemplo 10.2 Sea A una matriz m  n y considérese el sistema de ecuaciones lineales Ax D b. Si A se estructura así, A D ŒB; C , donde B es m  m, entonces se satisface la condición .c/ del teorema de la función implícita si, y sólo si, B es regular. Esta condición se corresponde con los requisitos y enunciados de la teoría de ecuaciones lineales. La función implícita se puede considerar como una u generalización no lineal de la teoría lineal.

11 Bibliografía B ERTSEKAS , D.P. 2003. Convex Analysis and Optimization. Athena Scientific. 35

B OYD , S. Y VANDENBERGHE , L. 2004. Convex Optimization. Cambridge University Press. F UENTE , J.L. 1998. Técnicas de cálculo para sistemas de ecuaciones, programación lineal y programación entera. Segunda edición. Reverté. DE LA

ROCKAFELLAR , R.T. 1970. Convex Analysis. Princeton University Press. H ALMOS , P.R. 1974. Finite-Dimensional Vector Spaces. Springer Verlag. K UHN , H.W. Y T UCKER , A.W. 1951. Nonlinear Programming. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. Verlag. L UENBERGER , D.G. 1969. Optimization by Vector Space Methods. John Wiley and Sons. L UENBERGER , D.G. Y Y E , Y. 2009. Linear and Nonlinear Programming. Springer Verlag. R IAZA , R. Y Á LVAREZ , M. 1996. Cálculo infinitesimal. Vol. I. Sociedad de Amigos de la Escuela Técnica Superior de Ingenieros Industriales de Madrid. R IAZA , R. Y Á LVAREZ , M. 1997. Cálculo infinitesimal. Vol. II. Sociedad de Amigos de la Escuela Técnica Superior de Ingenieros Industriales de Madrid. W OLFE , P. 1961. A Duality Theorem for Non-Linear Programming. Quart. Appl. Math. 19, Nı 3.

36