Archivo de la etiqueta: desigualdad

Seminario de Resolución de Problemas: Principio de Inducción, Parte 2

En esta entrada continuaremos con ejemplos de uso del principio de inducción en la resolución de problemas. Es una continuación de la entrada anterior. Como recordatorio, aquí está el principio de inducción en la forma en la que lo hemos estado usando:

Principio de inducción. Sea P(n) una afirmación (o proposición o propiedad) que depende del número natural n. Si

  • la afirmación P(a) es cierta y
  • la veracidad de la afirmación P(n) implica la veracidad de la afirmación P(n+1),

entonces la afirmación P(n) es cierta para toda n \geq a.

Lo que nos interesa ahora es ver cómo el principio de inducción se mezcla con algunas de las heurísticas de resolución de problemas.

Inducción y trabajar hacia atrás

Lo que hemos hecho hasta ahora es lo siguiente. Tomamos un enunciado que depende de un entero n. Comenzamos probándolo para la base inductiva. Luego, suponemos la veracidad del enunciado para cierto entero n. A partir de ahí, intentamos conseguir la veracidad del enunciado para el entero n+1.

Como vimos cuando platicamos de trabajar hacia atrás, eso no siempre es lo más natural en la resolución de un problema. En algunas ocasiones nos conviene más empezar con el enunciado que queremos demostrar y mostrar que mediante pasos reversibles podemos llegar a algo cierto. Queremos aplicar esta idea para la demostración del paso inductivo.

Consideremos el siguiente ejemplo.

Problema. Demuestra que para todo entero no negativo n se tiene que

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}\]

es un número entero.

Solución. Tenemos que probar la afirmación para n\geq 0 entero. Procedemos por inducción sobre n. Si n=0, la expresión es igual a 0, así que la afirmación es cierta. Supongamos entonces que

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}\]

es entero y consideremos la expresión

    \[\frac{(n+1)^5}{5}+\frac{(n+1)^4}{2}+\frac{(n+1)^3}{3}-\frac{(n+1)}{30}.\]

Nuestro objetivo es mostrar que esta expresión es entera. Nos gustaría usar la hipótesis inductiva, así que queremos intentar encontrar dentro de esta expresión la expresión para n. Esto lo podemos hacer usando el binomio de Newton para abrir los binomios a potencias y luego agrupando. Tenemos que

    \begin{align*}\frac{(n+1)^5}{5}&=\frac{n^5+5n^4+10n^3+10n^2+5n+1}{5}\\&=\frac{n^5}{5}+n^4+2n^3+2n^2+n+\frac{1}{5}\\\frac{(n+1)^4}{2}&=\frac{n^4+4n^3+6n^2+4n+1}{2}\\&=\frac{n^4}{4}+2n^3+3n^2+2n+\frac{1}{2}\\\frac{(n+1)^3}{3}&=\frac{n^3+3n^2+3n+1}{3}\\&=\frac{n^3}{3}+n^2+n+\frac{1}{3}\\-\frac{n+1}{30}&=-\frac{n}{30}-\frac{1}{30}.\end{align*}

Así, cuando hagamos la suma tenemos los términos

    \[\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30},\]

cuya suma es entera por hipótesis inductiva,

    \[n^4+2n^3+2n^2+n+2n^3+3n^2+2n+n^2+n,\]

que es entero pues n es entero y \frac{1}{5}+\frac{1}{2}+\frac{1}{3}-\frac{1}{30}=1, de modo que la suma total es suma de enteros y por lo tanto es un entero. Esto termina la prueba por inducción.

\square

Si no comenzábamos a manipular la expresión para n+1, hubiera sido muy difícil, sólo a partir de la de n, llegar a la de n+1.

Inducción y generalización

Una forma sencilla de combinar inducción con generalización es la siguiente:

  • Nos piden demostrar una afirmación para un natural muy específico.
  • En vez de eso, construimos un problema más general que funcione «para todos los naturales».
  • Resolvermos ese problema por inducción.

Veamos un ejemplo.

Problema. Muestra que

    \[\left(\frac{3+\sqrt{17}}{2}\right)^{2020}+ \left(\frac{3-\sqrt{17}}{2}\right)^{2020}\]

es un entero impar.

Solución. Sean \alpha=\frac{3+\sqrt{17}}{2} y \beta=\frac{3-\sqrt{17}}{2}. Se pide mostrar que \alpha^{2020}+\beta^{2020} es un entero impar. Mostraremos que, de hecho, \alpha^n+\beta^n es un entero impar para todo entero n\geq 1. Vamos a proceder por inducción fuerte (hablaremos un poco más de eso más adelante).

El primer caso es n=1 y notemos que \alpha^1+\beta^1=\alpha+\beta=3. Notemos también que \alpha\beta=\frac{9-17}{4}=-2, de modo que \alpha^2+\beta^2=(\alpha+\beta)^2-2ab=9+4=13, que también es impar. Supongamos ahora que sabemos que la afirmación es cierta para exponentes n-1 y n.

Consideremos el polinomio cuadrático

    \[(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+\alpha\beta=x^2-3x-2.\]

Como \alpha y \beta son raíces, tenemos que \alpha^2-3\alpha-2=0 y \beta^2-3\beta -2=0. Multiplicando estas igualdades por \alpha^{n-1} y \beta^{n-1} respectivamente, sumando ambas igualdades obtenidas, y despejando \alpha^{n+1}+\beta^{n+1} llegamos a

    \[\alpha^{n+1}+\beta^{n+1}=3(\alpha^n+\beta^n})+2(\alpha^{n-1}+\beta^{n-1}).\]

De aquí la conclusión inductiva es inmediata. Como la hipótesis inductiva es que el resultado es cierto para los exponentes n y n-1, entonces en el lado derecho tenemos una suma de un entero impar con un entero par, que es un entero impar. Esto muestra que la afirmación es cierta para cuando los exponentes son n+1.

Para demostrar el problema original, basta con hacer la observación de que, en particular, \alpha^{2020}+\beta^{2020} es un entero impar.

\square

Hay otra forma de combinar inducción con generalización, pero es un poco más sofisticada. Para explicarla, es mejor comenzar con un ejemplo.

Problema. Demuestra que para todo entero n\geq 1 se tiene que

    \[\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots + \frac{1}{n(n+1)} <1.\]

Antes de resolver el problema, intentemos hacer una solución «ingenua» que quiera usar inducción de manera directa. No hay ningún problema con hacer la base de inducción, pues para n=1 al lado izquierdo tenemos únicamente \frac{1}{2} y al lado derecho 1. Supongamos que el resultado es cierto para n, es decir, que

    \[\frac{1}{1\cdot 2}+\ldots + \frac{1}{n(n+1)} <1.\]

Llamémosle M a la expresión del lado izquierdo. Lo que queremos probar ahora es que el resultado es cierto para n+1, es decir, que M+\frac{1}{(n+1)(n+2)}<1. Sabemos que M<1, pero ahora estamos sumando un término positivo adicional. Es posible que este término arruine la desigualdad, pues M<1 es una afirmación «muy débil». Veamos cómo darle la vuelta a esta dificultad.

Solución. Sea P(n) la afirmación del problema. Consideremos la afirmación Q(n) que dice que para todo entero n\geq 1 se tiene que

    \[\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots + \frac{1}{n(n+1)}} =1-\frac{1}{n+1}.\]

Si logramos demostrar Q(n), entonces P(n) será cierta de manera inmediata, pues 1-\frac{1}{n+1}<1. Vamos a demostrar Q(n) por inducción.

Tenemos que Q(1) es cierto pues en ambos lados de la igualdad queda \frac{1}{2}. Supongamos que Q(n) es cierto. Usando esto, tenemos que

    \begin{align*}\frac{1}{1\cdot 2}+\ldots+\frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} &=\left(1-\frac{1}{n+1}\right)+\frac{1}{(n+1)(n+2)}\\&=1-\frac{(n+2)-1}{(n+1)(n+2)}\\&=1-\frac{1}{n+2},\end{align*}

es decir, que Q(n+1) es cierto. Así, por inducción Q(n) es cierto para todo entero n y con eso P(n) también.

\square

Lo que sucedió fue lo siguiente. Al hacer el paso inductivo, intentamos mostrar que P(n) implica P(n+1). Pero esto es imposible pues P(n) «es muy débil», o bien «pierde información de todo lo que está pasando». Sin embargo, cuando consideramos la afirmación auxiliar Q(n), resulta que esta «tiene más información». Aquí, esta información es «qué tal lejos está la expresión de 1 «

La afirmación Q(n) tiene tanta información, que ahora sí con ella se puede probar Q(n+1). Se termina el problema usando que Q(n) implica P(n). Así, la estrategia fue la siguiente:

  • Se tiene una afirmación P(n) que se quiere demostrar para todos los naturales. Hacer inducción no parece funcionar, pues P(n) parece no ser suficiente para probar P(n+1)
  • Se considera entonces una afirmación Q(n) más fuerte (que implique a P(n)), pero para la cual Q(n) sí pueda probar Q(n+1).
  • Se prueba Q(n) por inducción, y se concluye que P(n) es cierta.

Hay que ser cuidadosos. Parte del ingenio en usar esta estrategia consiste en poder identificar un balance la generalización Q(n) que necesitamos de modo que sí sirva para solucionar el problema original, pero que no sea demasiado ambiciosa como para que sea falsa.

Más ejemplos

Hay más ejemplos bastante elaborados del uso de estas ideas en Problem Solving Through Problems de Loren Larson, Secciones 2.1, 2.2, 2.3 y 2.4. Otro libro con muchos ejemplos interesantes es el Putnam and Beyond, de Gelca y Andreescu. También hay otros ejemplos de inducción en las siguientes entradas:

Un problema de probabilidad y escuchar música

El problema

Les comparto un problema que se me ocurrió en las (muchas) horas que he pasado en el carro escuchando música, cuando vivía en la Ciudad de México. El estéreo del carro ordena las canciones alfabéticamente. Tiene un botón que permite «avanzar una canción». Pero a veces tarda mucho: si estoy escuchando «Adele – Hello», hay que apretar el botón muchas veces para llegar a «Shakira – Dónde están los ladrones».

En esas épocas descubrí una estrategia «intuitiva» para llegar más rápido a la canción. La idea es la siguiente: pasar temporalmente al modo de «canción aleatoria», apretar el botón unas cuantas veces para acercarme a la canción que quiero (en el ejemplo anterior, digamos que después de dos o tres veces el botón me lleva a «Paquita la del Barrio – Rata de dos Patas»), y de ahí quitar el aleatorio y avanzar normal. Eso, intuitivamente, siempre me ahorró muchos pasos. El problema consiste en encontrar la estrategia óptima, en donde se permiten mezclar pasos normales y aleatorios.

Para eso, voy a plantear un problema muy concreto. De aquí en adelante supondré que el lector sabe un poco de probabilidad. Pensemos que hay 2n canciones, numeradas de 1 a 2n. Estoy en la canción n y quiero llegar a la canción 2n. Pensemos que el estéreo tiene exactamente dos botones, el A que avanza 1 (y de 2n lleva a 1), y el B que lleva a una canción aleatoria (cualquiera de las canciones, incluida la actual, tiene probabilidad 1/2n de ser elegida). En cada paso se permite ver en qué canción estoy, y de ahí decidir apretar A o B. ¿Cuál es la estrategia que en valor esperado tiene menos pasos? ¿Cuál es ese valor esperado?

En la imagen de aquí abajo se muestra un ejemplo de una forma de apretar los botones para n=5, con 2n=10 canciones. Las flechas rojas corresponden a avanzar 1 apretando el botón A. Las flechas azules corresponden a ir a un lugar aleatorio apretando el botón B. Se apretaron los botones en el orden ABBAA, de modo que se hicieron 5 pasos.

Ejemplo de estrategia ABBAA
Un ejemplo en el que se usa la estrategia ABBAA. La canción 1 es de ABBA. Es Dancing Queen. «Feel the beat form the tambourine… Oh yeah…».

Ese es el enunciado del problema. De aquí en adelante empiezo a hablar de ideas para resolverlo, así que si quieres intentarlo, este es el momento correcto.

Primeras ideas

Notemos que la estrategia «siempre A, hasta llegar a 2n» toma exactamente n pasos siempre. La estrategia «siempre B» es para intentar atinarle, y en cada paso tiene probabilidad de éxito 1/2n. Entonces, en esta segunda estrategia la cantidad de pasos requeridos es una variable aleatoria con distribución geométrica de parámetro p=1/2n, de modo que el número esperado de pasos es 1/p=2n.

Sin embargo, suena a que la estrategia esbozada al inicio de esta entrada es intuitivamente mejor: usar el B para acercarse y luego el A para llegar.

La solución

Vamos a mostrar que la mejor estrategia en valor esperado es la siguiente: «apretar el botón B hasta llegar aproximadamente al intervalo [n-2\sqrt{n}, n], y de ahí apretar el botón A» hasta llegar a n.

El primer argumento es que en cada paso, lo que hace la estrategia sólo depende de en qué canción estamos. En efecto, el paso A es determinista y el B es una variable uniforme independiente de todo lo demás.

El segundo argumento es que, si en algún momento de la estrategia usamos el botón A, entonces después de ello nunca nos conviene usar el botón B. Lo probamos por contradicción: supongamos que por cualquier razón en la estrategia óptima tenemos que hacer un AB. El paso A es determinista, y sabíamos exactamente a qué canción nos iba a llevar (a la siguiente). Pero hacer el paso B en cualquier lugar que estemos es simétrico, pues nos lleva a una canción aleatoria. Si a priori sabíamos que íbamos a hacer un paso B, lo mejor es hacerlo lo antes posible. Así, la estrategia que substituye esos pasos AB por B se ahorra un paso, y no es óptima. Contradicción.

Ahora, afirmo lo siguiente. Si la estrategia óptima es apretar A cuando estamos en la canción j, entonces también va a ser apretar A cuando estemos en cualquier canción k con j\leq k < 2n. Esto es debido al argumento anterior: al apretar A llegamos a j+1, que por el párrafo de arriba, no le puede tocar B. Entonces le toca A. De ahí llegamos a j+2, que de nuevo no le puede tocar B. Y así sucesivamente (inductivamente), hasta llegar a 2n-1.

Lo que acabamos de probar es que la estrategia óptima se ve de la siguiente manera para algún entero k: «Apretar B hasta que lleguemos a alguno de los últimos k elementos. De ahí, apretar A hasta llegar a 2n.» Nos falta determinar cuál es la mejor k que podemos usar.

A estas alturas ya podemos calcular explícitamente el valor esperado de pasos en esta estrategia. El evento «llegar a alguno de los últimos k elementos» tiene probabilidad k/2n de ocurrir cada que se aprieta el botón B, así que la cantidad de veces que hay que apretar B para ello es una variable aleatoria geométrica de valor esperado 2n/k. Una vez que llegamos a los últimos k elementos, caemos a cualquier elemento del intervalo \{2n-k+1, 2n-k+2,\ldots,2n\} con la misma probabilidad, y respectivamente nos tomará \{k-1, k-2,\ldots, 0\} pasos en llegar a 2n, es decir, la cantidad de pasos que hacemos es una variable aleatoria uniforme discreta de media (k-1)/2.

Así, en total usamos (2n/k) + (k-1)/2 pasos para llegar. Queremos lograr que esta expresión sea lo más pequeña posible. Usando la desigualdad entre la media geométrica y la aritmética, notamos que

    \[\frac{2n}{k}+\frac{k-1}{2}=\frac{2n}{k}+\frac{k}{2}-\frac{1}{2} \geq 2\sqrt{n} - \frac{1}{2},\]

y que la igualdad se da si y sólo si \frac{2n}{k}=\frac{k}{2}, es decir, si y sólo si k=2\sqrt{n}. En este caso, la cantidad media de pasos que usamos es 2\sqrt{n}-\frac{1}{2}.

Aquí arriba hicimos un poquito de trampa. En realidad k=2\sqrt{n} tiene sentido para la estrategia sólo cuando \sqrt{n} es un número entero. Sin embargo, por la convexidad de la función \frac{2n}{k}+\frac{k}{2} tenemos la garantía de que o bien \lfloor 2\sqrt{n} \rfloor o bien \lceil 2\sqrt{n} \rceil dan el máximo.

Conclusión y otros problemas

Está cool que hayamos bajado la cantidad de pasos que se necesitan de valor esperado de algo que era n a algo que es del tamaño 2\sqrt{n}. Para hacerse una idea de los pasos que se pueden ahorrar, toma una colección de 800 canciones. Originalmente se necesitaban 400 pasos +1 para ir de la mitad al final. Con la nueva estrategia se requieren como 40.

Hacer esta estrategia en la vida real es un poco complicado pues los estéreos no muestran el número exacto de la canción en la que se está, además de que es difícil memorizar a qué canción le toca qué número. Pero a veces sí muestran el nombre de la canción y más o menos «se le puede aproximar».

Hay un par de variantes interesantes. Una es ¿qué sucede si además de tener botón +1 y aleatorio, también tenemos botón -1?. En esta variante la solución no cambia mucho, pero es bueno intentarla para repasar las ideas de la prueba.

La otra variante es la siguiente. La estrategia óptima, como está descrita arriba, tiene un problema: es posible que nunca termine, o que tome muchísimos pasos en terminar (esto será muy improbable y por eso el valor medio se compensa). Así, imaginemos que queremos la restricción adicional de que la estrategia que usemos nunca use más de, digamos, 4n pasos. En esta variante: ¿cuál es la estrategia óptima? ¿cuántos pasos toma?

¿Ahora qué?

Si te gustó esta entrada, puedes compartirla o revisar otras relacionadas con matemáticas a nivel universitario:

Una prueba del teorema de la función inversa

Introducción

Uno de los teoremas clave de los cursos de cálculo de varias variables es el teorema de la función inversa (TFI). En la Facultad de Ciencias de la UNAM se estudia en la materia Cálculo III. En esta entrada me gustaría presentar de la manera más auto-contenida posible este resultado.

Platicaré un poco de las definiciones de los términos que aparecen en el enunciado, así como de la intuición de por qué el teorema es cierto. Después presentaré los ingredientes principales para la prueba «clásica». Finalmente, presentaré la prueba intentando motivarla y dividiéndola en secciones pequeñas.

El enunciado con el que trabajaremos es el siguiente:

Teorema de la función inversa

Sea F:\mathbb{R}^n\to \mathbb{R}^n una función de clase \mathcal{C}^1 con matriz Jacobiana DF. Supongamos que F(a)=b y que DF(a) es invertible. Entonces existen vecindades abiertas U y V de a y b respectivamente para las cuales:

a) F:U\to V es una biyección,
b) su inversa F^{-1}:V\to U es de clase \mathcal{C}^1 y
c) DF^{-1}(b)=DF(a)^{-1}.

Lo que nos espera es aproximadamente lo que está en el siguiente diagrama, donde las flechas indican a grandes rasgos qué resultado se usa para probar qué otro.

Definiciones e intuición

La función con la que comenzamos es una función de \mathbb{R}^n a \mathbb{R}^n, así que la podemos descomponer en sus funciones coordenadas de la siguiente manera:

    \[F(x)=(F_1(x), F_2(x),\ldots, F_n(x))\]

Que la función sea de clase \mathcal{C}^1 quiere decir que las derivadas parciales con respecto a cada una de las variables existen, que estas son continuas y que localmente F «se comporta» como la transformación lineal correspondiente a la matriz Jacobiana siguiente:

    \[DF(x)=\begin{pmatrix}\frac{\partial F_1}{\partial x_1}(x) & \cdots & \frac{\partial F_1}{\partial x_n}(x)\\\vdots & \ddots & \vdots \\\frac{\partial F_n}{\partial x_1}(x) & \cdots & \frac{\partial F_n}{\partial x_n}(x)\end{pmatrix}\]

Entonces, a grandes rasgos lo que nos dice el teorema de la función inversa es lo siguiente. Si F se comporta como una transformación lineal T invertible «cerquita» del punto a, entonces en realidad es invertible «cerquita» del punto a y más aún, la inversa se comporta como la transformación lineal T^{-1} «cerquita» del punto b=f(a).

Suena bastante razonable, pero hay algunos aspectos que son sorprendentes. Uno es que se garantiza la invertibilidad en todo un abierto U. Si no se requiriera que fuera abierto, sería chafa porque podríamos tomar U=\{a\} y V=\{b\} y la restricción sería trivialmente invertible. Lo otro es que el teorema también garantiza que la inversa es diferenciable, lo cual de entrada no es evidente.

Para la prueba necesitamos hablar de dos normas. Cuando tengamos un vector x=(x_1,\ldots,x_n) en \mathbb{R}^n, \norm{x} denotará la norma euclideana

    \[\norm{x}=\sqrt{\sum_{i=1}^nx_i^2.\]

Necesitaremos también la norma de Frobenius. Como recordatorio, para una matriz A=(a_{ij}) de n\times n, su norma de Frobenius está dada por

    \[\norm{A}=\sqrt{\sum_{i=1}^n\sum_{j=1}^n a_{ij}^2},\]

o equivalentemente, si A_i es el i-ésimo renglón de A, tenemos que

    \[\norm{A}=\sqrt{\sum_{i=1}^n\norm{A_{i}}^2},\]

pues ambas expresiones suman todas las entradas de la matriz al cuadrado.

Ingredientes para la prueba

Pasemos ahora a algunos resultados auxiliares que es más cómodo probar desde antes. Algunos de ellos son más generales que lo que enuncio (e incluso con la misma prueba), pero con el fin de que la demostración sea auto-contenida, he decidido enunciar sólo lo que necesitamos.

Teorema del punto fijo de Banach (para \mathbb{R}^n)

Sea X un compacto de \mathbb{R}^n y \varphi:X\to X una función continua. Supongamos que \varphi es una contracción, es decir, que existe un real 0<\lambda<1 para el cual \norm{\varphi(x)-\varphi(y)}\leq\lambda \norm{x-y} para todos x,y \in X.

Entonces \varphi tiene un único punto fijo, es decir existe uno y sólo un punto x_0\in X para el cual \varphi(x_0)=x_0.

Para probar el teorema del punto fijo de Banach basta tomar cualquier punto inicial x_1 y considerar la sucesión \{x_m\} construida recursivamente con la regla x_m=\varphi(x_{m-1}) para m\geq 2. Usando que \varphi es contracción y la fórmula para series geométricas se puede mostrar inductivamente que para m>m' se tiene

    \[\norm{x_m-x_m'}\leq\lambda ^{m'-1} \norm{x_2-x_1} \left(\frac{1}{1-\lambda}\right).\]

Como \lambda<1, el lado derecho se hace arbitrariamente pequeño conforme m' se hace grande, así que ésta es una sucesión de Cauchy. Por la compacidad de X y completud de \mathbb{R}^n, tenemos que la sucesión converge a un punto x_0. Por continuidad, este punto satisface:

    \[x_0=\lim_{m\to \infty} x_{m+1} = \lim_{m\to \infty} \varphi(x_m)=\varphi\left(\lim_{m\to \infty} x_m\right) = \varphi(x_0).\]

La unicidad no necesita la compacidad de X, sino únicamente que \varphi sea contracción. En efecto, si hay otro punto fijo x entonces

    \[\norm{x-x_0}=\norm{\varphi(x)-\varphi(x_0)}\leq \lambda \norm{x-x_0},\]

de donde \norm{x-x_0}=0, pues si no se tendría una contradicción. Así, x=x_0.

Desigualdades entre la norma de Frobenius

Para x\in \mathbb{R}^n y A,B matrices reales de n\times n tenemos que
a) \norm{Ax}\leq \norm{A} \norm{x} y
b) \norm{AB}\leq \norm{A} \norm{B}.

La desigualdad (a) se prueba usando la desigualdad de Cauchy-Schwarz. En efecto, si A_1,\ldots, A_n son los renglones de la matriz A, tenemos que

    \[Ax=(A_1\cdot x, A_2\cdot x, \ldots, A_n\cdot x),\]

entrada a entrada tenemos por Cauchy-Schwarz que

    \[(A_i\cdot x)^2\leq \norm{A_i}^2\norm{x}^2,\]

de modo que sumando para i=1,\ldots, n tenemos que

    \[\norm{Ax}^2\leq \left(\sum_{i=1}^n \norm{A_i}^2\right)\norm{x}^2=\norm{A}^2\norm{x}^2,\]

lo cual prueba la desigualdad (a). La desigualdad (b) se prueba de manera similar, tomando fila por fila a la matriz A y columna por columna a la matriz B.

Desigualdad del valor medio

Sea U\subset \mathbb{R}^n un abierto convexo y F:U\to \mathbb{R}^n una función de clase \mathcal{C}^1. Sean x,y puntos en U para los cuales la cual la norma de Frobenius del Jacobiano \norm{DF} está acotada sobre el segmento xy por una constante C. Entonces:

    \[\norm{F(x)-F(y)}\leq C \norm{x-y}.\]

La desigualdad del valor medio requiere de algunos pasos intermedios. Definamos h=y-x. La clave es probar las siguientes tres afirmaciones:

    \begin{align*}F(x)-F(y)&=\int_0^1 DF(x+th) h \,dt\\\norm{\int_0^1 DF(x+th) h \,dt} &\leq \int_0^1 \norm{DF(x+th)}\norm{h}\, dt\\\int_0^1 \norm{DF(x+th)}\norm{h}\, dt &\leq C \norm{h}.\end{align*}

La primera es una «generalización» del teorema del valor medio de una variable. Se prueba coordenada a coordenada usando el Teorema Fundamental del Cálculo, la regla de la cadena y un intercambio de integral con suma (usando la continuidad de las derivadas parciales).

La segunda se prueba usando desigualdad del triángulo para integrales y la desigualdad (a) que probamos arriba para la norma de Frobenius.

La tercera se sigue de manera inmediata de la cota hipótesis para la matriz Jacobiana, pues x+th=x+t(y-x) recorre el segmento xy conforme t recorre el intervalo [0,1].

Combinando las tres afirmaciones concluimos

    \[\norm{F(x)-F(y)}\leq C\norm{h}=C\norm{y-x},\]

que es justo lo que queríamos probar.

Con esto terminamos los pre-requisitos para probar el TFI. Aquí ya se ve algo interesante sucediendo. En el TFI queremos mostrar que cierta restricción es biyectiva, osea que cierto sistema de ecuaciones tiene una y sólo una solución. Esto se asemeja al teorema del punto fijo de Banach, donde, bajo ciertas condiciones de contracción, hay uno y sólo un punto fijo. El teorema de la desigualdad media puede ayudar a mostrar que una función contrae. Todo esto no es casualidad. A continuación veremos cómo combinar estos ingredientes.

Demostración del TFI

Estamos listos para dar la demostración del teorema de la función inversa. Por comodidad, aquí lo enunciamos de nuevo:

Teorema de la función inversa

Sea F:\mathbb{R}^n\to \mathbb{R}^n una función de clase \mathcal{C}^1 con matriz Jacobiana DF. Supongamos que F(a)=b y que DF(a) es invertible. Entonces existen vecindades abiertas U y V de a y b respectivamente para las cuales:

a) F:U\to V es una biyección,
b) su inversa F^{-1}:V\to U es de clase \mathcal{C}^1 y
c) DF^{-1}(b)=DF(a)^{-1}.

Para el teorema necesitamos definir quién es el abierto U. Lo tomaremos como U:=B(a,\epsilon), una bola abierta y centrada en a de radio \epsilon. La idea es tomar \epsilon tan pequeño como para que para x\in U tengamos que DF(x) sea invertible y

    \[\norm{DF(a)-DF(x)}\leq \frac{1}{2\norm{DF(a)^{-1}}}.\]

Ambas cosas las podemos hacer pues la asignación x \mapsto DF(x) es continua ya que F de clase \mathcal{C}^1. En el transcurso de la prueba discutiremos la motivación de esta elección. A V lo tomaremos como F(U).

Lo primero que haremos es reformular parte (a) en términos de puntos fijos. Queremos que la restricción F:U\to V que estamos buscando sea biyectiva. En otras palabras, para y\in V queremos que la ecuación y=F(x) tenga una y sólo una solución x en U. Como por hipótesis la matriz DF(a) es invertible, esto sucede si y sólo si

    \[x+DF(a)^{-1}(y-F(x))=x,\]

es decir, si y sólo si x es un punto fijo de la función \varphi_y(x)=x+DF(a)^{-1}(y-F(x)). Parece un poco artificial haber introducido a DF(a)^{-1}, pero como veremos a continuación tiene sentido pues nos ayudará para que \varphi_y sea contracción.

Teniendo en mente que queremos usar la desigualdad del valor medio, calculamos y acotamos la norma de la derivada de \varphi_y como sigue

    \begin{align*}\norm{D\varphi_y (x)} &= \norm{I - DF(a)^{-1} DF(x)} \\ &= \norm{DF(a)^{-1}(DF(a) - DF(x))}\\&\leq \norm{DF(a)^{-1}}\norm{DF(a)-DF(x)}\end{align*}

Aquí es donde usamos (y se motiva parte de) nuestra elección de U: nos permite acotar \norm{DF(a)-DF(x)} superiormente con \frac{1}{2\norm{DF(a)^{-1}}} y por lo tanto podemos concluir la desigualdad anterior como

(1)   \begin{align*}\norm{D\varphi_y (x)} \leq \frac{1}{2}.\end{align*}

Por la desigualdad del valor medio, concluimos la siguiente observación clave:

Para y en V tenemos que \varphi_y es contracción en U con factor \lambda=\frac{1}{2}. En otras palabras, para x,w en U, tenemos

    \[\norm{\varphi_y(x)-\varphi_y(w)}\leq \frac{\norm{x-x'}}{2}.\]

La prueba a partir de ahora se divide en los siguientes pasos:

  1. Mostrar que F:U\to V es biyectiva.
  2. Mostrar que V es abierto
  3. Mostrar que F^{-1}:V\to U es diferenciable y y DF^{-1}(b)=DF(a)^{-1}
  4. Mostrar que las derivadas parciales son continuas

F:U\to V es biyectiva.

La suprayectividad la tenemos gratis, pues por definición V=F(U).

Para la inyectividad, tomamos y\in V y supongamos que existen x y w en U tales que F(x)=y=F(w). Esto quiere decir que x y w son puntos fijos de la contracción \varphi_y. Como vimos en la prueba del teorema del punto fijo de Banach, esto implica que x=w. Así, x=w, de modo que F:U\to V es inyectiva y por lo tanto es biyectiva.

Nota: Aquí no estamos usamos el teorema del punto fijo de Banach pues U no es compacto. Sólo estamos usando que las contracciones son inyectivas.

V es abierto

Tomemos y' en V, es decir, para la cual existe x' en U con F(x')=y'. Queremos ver que si «y está muy cerquita de y'» , entonces hay una solución para F(x)=y con x en U.

Como U es abierto, existe r tal que la bola B(x',2r) abierta de centro x' y radio 2r se queda contenida en U. Tomemos y en la bola B\left(y',\frac{r}{2\norm{DF(a)^{-1}}}\right). Vamos a ver que F(x)=y tiene solución en U. Consideremos la función \varphi_y, pero restringida a la bola cerrada X:=\overline{B}(x',r)\subset U. Mostraremos que la imagen de \varphi_y se queda contenida en \overline{B}(x',r). En efecto:

    \begin{align*}\norm{\varphi_y(x)-x'}&=\norm{\varphi_y(x)-\varphi_y(x')+DF(a)^{-1}(y-y')}\\&\leq \norm{\varphi_y(x)-\varphi_y(x')}+\norm{DF(a)^{-1}}\norm{y-y'}\\&\leq \frac{\norm{x-x'}}{2}+\frac{r}{2}\leq r.\end{align*}

De este modo, \varphi_y es una contracción del compacto X a sí mismo. Por lo tanto, tiene un punto fijo en X, de modo que F(x)=y para x\in X\subset U. Esto muestra que V=F(U) es abierto.

F^{-1}:V\to U es diferenciable y DF^{-1}(b)=DF(a)^{-1}

Vamos a demostrar que F^{-1}:V\to U es diferenciable a partir de la definición de diferenciabilidad. Más aún, veremos que si y=F(x) para x en U, entonces DF^{-1}(y)=DF(x)^{-1}. Aquí es donde se termina de motivar nuestra elección en U, pues nos garantiza que a la derecha en efecto tenemos una matriz invertible.

Tomemos entonces y=F(x). Nos interesa el límite cuando \norm{h}\to 0 de la siguiente expresión

    \[\frac{\norm{F^{-1}(y+h)-F^{-1}(y)-DF(x)^{-1}h}}{\norm{h}},\]

Como U es abierto, si \norm{h} es pequeña entonces y+h está en U. De este modo, existe k tal que x+k \in U y F(x+k)=y+h. Así, la expresión anterior la podemos reescribir como

(2)   \begin{align*}\frac{\norm{DF(x)^{-1}(F(x+k)-F(x)-DF(x)k)}}{\norm{k}}\frac{\norm{k}}{\norm{h}}\end{align*}

Antes de continuar, probemos una desigualdad auxiliar. Notemos que

    \begin{align*}\norm{k}-\norm{DF^{-1}(a)h} &\leq \norm{k-DF^{-1}(a)h}\\&=\norm{\varphi_y(x+k)-\varphi_y(x)}\\&\leq\frac{\norm{k}}{2},\end{align*}

así,

(3)   \begin{align*}\norm{k}\leq 2\norm{DF^{-1}(a)h} \leq 2\norm{DF^{-1}(a)}\norm{h}.\end{align*}

Substituyendo el valor de \norm{k} en (2), concluimos que la expresión es menor o igual a

(4)   \begin{align*}2\norm{DF(x)^{-1}}\frac{\norm{F(x+k)-F(x)-DF(x)k}}{\norm{k}}\norm{DF^{-1}(a)}\end{align*}

Estamos listos para terminar. La desigualdad (3) también garantiza que \norm{k}\to 0 cuando \norm{h}\to 0. Así, como F es diferenciable, tenemos que la expresión (4) tiende a 0. Esto muestra que F^{-1} es diferenciable en y con DF^{-1}(y)=DF(x)^{-1}, tal como queríamos.

Las derivadas parciales son continuas

Esta parte es sencilla a partir de la parte anterior. Tenemos que:

    \[DF^{-1}(b)=DF(F^{-1}(b))^{-1}\]

Por la regla de Cramer la inversa de una matriz depende continuamente de las entradas de la matriz original. Además, la asignación b \mapsto F^{-1}(b) es continua. Así, las entradas de DF^{-1}(b) (las derivadas parciales de F^{-1}) dependen continuamente de las derivadas parciales de F, que dependen continuamente de b por hipótesis.

Con esto termina la prueba.

¿Ahora qué?

Si te gustó esta entrada, puedes compartirla o revisar otras relacionadas con matemáticas a nivel universitario:

Modificar el problema

HeuristicasOtra técnica de resolucion de problemas es proponer un problema que ayude, pero que no necesariamente sea equivalente. Esto puede ser a través de problemas más particulares o de problemas más difíciles.

En esta serie de videos veremos esta técnica en acción en cuatro problemas.

Ir a los videos…