Created
March 31, 2020 15:22
-
-
Save tiagox/f85134c3e4de138b4264030e2fb9894a to your computer and use it in GitHub Desktop.
UNTreF - Análisis Numérico
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"# Análisis Numérico\n", | |
"\n", | |
"**Nota final**: 50% (EF) + 30% (EP) + 20% (NC)\n", | |
"\n", | |
"- **NC**: nota de concepto. Viene de los TP's que hay que entregar durante el cuatrimestre (en fecha, calidad, prolijidad)\n", | |
"- **EP**: Examen parcial (quizás domiciliario)\n", | |
"- **EF**: Examen final: Entrega de un TP final.\n", | |
"\n", | |
"Para aprobar la materia.\n", | |
"\n", | |
"- Todos los TP's aprobadas.\n", | |
"- EP aprobado (nota $\\geq$ 4).\n", | |
"- EF aprobado (nota $\\geq$ 4).\n", | |
"- Nota final $\\geq$ 4." | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"$\n", | |
"\\require{cancel}\n", | |
"\\newcommand{\\annoterel}[3][]{\\underset{\\substack{#1\\uparrow\\\\#2}}{#3}}\n", | |
"$\n", | |
"# Clase 1\n", | |
"\n", | |
"## Errores de redondeo\n", | |
"\n", | |
"La mayoría de las computadoras trabajan en **sistema binario** (base 2) mientras que los humanos trabajos em **sistema decimal** (base 10).\n", | |
"\n", | |
"Vamos a repasar estos dos sistemas y a ver como pasar de uno a otro:\n", | |
"\n", | |
"Ejemplo:\n", | |
"\n", | |
"$(427,325)_{10} = 4 \\cdot 10^2 + 2 \\cdot 10^1 + 7 \\cdot 10^0 + 3 \\cdot 10^{-1} + 2 \\cdot 10^{-2} + 5 \\cdot 10^{-2}$\n", | |
"\n", | |
"Análogamente:\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"(1010.11101)_2 & = 1 \\cdot 2^3 + 0 \\cdot 2^2 + 1 \\cdot 2^1 + 0 \\cdot 2^0 + 1 \\cdot 2^{-1} + 1 \\cdot 2^{-2} + 1 \\cdot20^{-3} + 0 \\cdot 2^{-4} + 1 \\cdot 2^{-5} \\\\\n", | |
"& = 8 + 0 + 2 + 0 + \\dfrac{1}{2} + \\dfrac{1}{4} + \\dfrac{1}{8} + 0 + \\dfrac{1}{32} \\\\\n", | |
"& = 10.90625 = (10.90625)_{10}\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"¿Cómo paso de base 10 a base 2?\n", | |
"\n", | |
"Dos pasos:\n", | |
"\n", | |
"1. Parte entera (10 en este caso)\n", | |
"2. Parte decimal (0.90625 en este caso)\n", | |
"\n", | |
"**Parte entera**: Algoritmo (división entera)\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"10/2 & = 5 \\to resto = 0 \\\\\n", | |
"5/2 & = 2 \\to resto = 1 \\\\ \n", | |
"2/1 & = 1 \\to resto = 0 \\\\\n", | |
"1/2 & = 0 \\to resto = 1 \\uparrow (1010)_2\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"10 & = 8 + 2 \\\\\n", | |
"& = 2^3 + 2^1 \\\\ \n", | |
"& = (1010)_2\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"**Parte decimal**: Algotirmo, multiplicar por 2 y ver si es major a 1 o no.\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"0.90625 \\cdot 2 & = 1.8125 & \\geq 1 & \\to 1 \\downarrow (0.11101)_2 \\\\\n", | |
"0.8125 \\cdot 2 & = 1.625 & \\geq 1 & \\to 1 \\\\\n", | |
"0.625 \\cdot 2 & = 1.25 & \\geq 1 & \\to 1 \\\\\n", | |
"0.25 \\cdot 2 & = 0.5 & \\lt 1 & \\to 0 \\\\\n", | |
"0.5 \\cdot 2 & = 1.0 & \\geq 1 & \\to 1\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"Luego,\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"0.90625 & = 2^{-1} \\cdot (1 + 0.8125) \\\\\n", | |
" & = 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 0.625)) \\\\\n", | |
" & = 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 0.25))) \\\\\n", | |
" & = 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 2^{-1} \\cdot (0 + 0.5)))) \\\\\n", | |
" & = 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 2^{-1} \\cdot (0 + 2^{-1} \\cdot (1))))) \\\\\n", | |
" & = 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 0 \\cdot 2^{-1} + 1 \\cdot 2^{-2}))) \\\\\n", | |
" & = 2^{-1} \\cdot (1 + 2^{-1} \\cdot (1 + 1 \\cdot 2^{-1} + 0 \\cdot 2^{-2} + 1 \\cdot 2^{-3})) \\\\\n", | |
" & = 1 \\cdot 2^{-1} + 1 \\cdot 2^{-2} + 1 \\cdot 2^{-3} + 0 \\cdot 2^{-4} + 1 \\cdot 2^{-5} \\\\\n", | |
" & = (0.11101)_2\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"### Notación científica normalizada\n", | |
"\n", | |
"**Base 10**: Hay que multiplicar por una potencia de 10 (o sea $10^{(\\_)}$) para que todos los números distintos de cero queden a la derecha de la coma y además el primer número después de la coma sea distinto de cero.\n", | |
"\n", | |
"Ejemplo: $732.5051 = 0.7325051 \\cdot 10^3$\n", | |
"\n", | |
"Claramente, el número tiene que ser distinto de cero ($0$) (para poder escribirlo de esta manera).\n", | |
"\n", | |
"Del lado derecho, el número está escrito en notación científica normalizada.\n", | |
"\n", | |
"Otro ejemplo: $-0.005612 = -0.5612 \\cdot 10^{-2}$\n", | |
"\n", | |
"**En general**: Si $x \\in \\mathbb{R}$, $x \\neq 0$ siempre puedo escribir a $x$ de la forma:\n", | |
"\n", | |
"$x = \\pm r \\cdot 10^m$ con $\\dfrac{1}{10} \\leq r \\lt 1$ y $m$ un número **entero** ($m \\in \\mathbb{Z}$)\n", | |
"\n", | |
"**Base 2**: con el mismo razonamiento (escribiendo el número en base 2 y multiplicando por $2^{(\\_)}$ una potencia de 2)\n", | |
"\n", | |
"Si $x \\in \\mathbb{R}$ y $x \\neq 0$ siempre puedo escribir:\n", | |
"\n", | |
"$x = \\pm q \\cdot 2^m$, $\\dfrac{1}{2} \\leq q \\lt 1$, $m \\in \\mathbb{Z}$, $q$ en base 2\n", | |
"\n", | |
"**Referencias**:\n", | |
"\n", | |
"- $q$: mantisa\n", | |
"- $m$: exponente\n", | |
"- $x$: número flotante normalizado\n", | |
"\n", | |
"**Observaciones**: en una computadora binaria los números se representan en base 2, con restricciones en $q$ y en $m$.\n", | |
"\n", | |
"Ejemplo de computadora: 32 bits (digitos binarios).\n", | |
"\n", | |
"Sea $x$ un _número flotante normalizado_. $x \\neq 0$. Los 32 bits son alocados de la siguiente manera para representar a $x$\n", | |
"\n", | |
"- 1 bit: signo de $x$\n", | |
"- 1 bit: signo del exponente ($m$)\n", | |
"- 7 bits: exponente ($|m|$ número natural)\n", | |
"- 23 bits: mantisa ($|q| \\in \\mathbb{R}$)\n", | |
"\n", | |
"**Observaciones**:\n", | |
"\n", | |
"- Sabemos que el primer digito de $q$ es un $1$, entonces los 23 bits son guardados para los digitos 2do, 3ro, ..., 24avo de $q$. O sea, es como tener 24 bits para la mantisa.\n", | |
"- Si $|m|$ ocupa 7 bits y $|q|$ 24 bits, entonces es un _número de máquina_ y puede ser representado por la computadora de manera exacta.\n", | |
"- Si tenemos un `INPUT` que **no** es un número de máquina, entonces vamos a tener un error al representar este número por un número de máquina\n", | |
"- $\n", | |
"\\begin{align}\n", | |
"|m| \\leq (1111111)_2 & = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 \\\\\n", | |
"& = 2^7 - 1 = 127\n", | |
"\\end{align}\n", | |
"$ \n", | |
"\n", | |
" pues:\n", | |
"\n", | |
" $\n", | |
"\\begin{align}\n", | |
"1 + 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"(2 \\cdot 2^0) + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"2^1 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"(2 \\cdot 2^1) + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"2^2 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"(2 \\cdot 2^2) + 2^3 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"2^3 + 2^3 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"(2 \\cdot 2^3) + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"2^4 + 2^4 + 2^5 + 2^6 & = \\\\\n", | |
"(2 \\cdot 2^4) + 2^5 + 2^6 & = \\\\\n", | |
"2^5 + 2^5 + 2^6 & = \\\\\n", | |
"(2 \\cdot 2^5) + 2^6 & = \\\\\n", | |
"2^6 + 2^6 & = \\\\\n", | |
"(2 \\cdot 2^6) & = 2^7\n", | |
"\\end{align}\n", | |
"$ \n", | |
"\n", | |
"- Esto puede ser suficiente para algunos calculos científicos $\\implies$ doble precisión.\n", | |
"\n", | |
"### Distribución de Números Flotantes de Máquina (en la recta de números reales)\n", | |
"\n", | |
"Misma cantidad de números entre dos potencias de 2.\n", | |
"\n", | |
"Ejemplo: entre $2^{-1}$ y $2^0$ hay igual cantidad de números que entre $2^0$ y $2^1$.\n", | |
"\n", | |
"Luego, hay una distribución **NO** uniforme (en $\\mathbb{R}$, entre dos potencias de 2 sí), con más densidad cerca del $0$.\n", | |
"\n", | |
"### Representación de números enteros\n", | |
"\n", | |
"En una máquina de 32 bits, solo guardo 1 bit para el signo.\n", | |
"\n", | |
"$\n", | |
"\\annoterel{\\text{1 bit}\\\\\\text{signo}}{\\pm}\n", | |
"\\annoterel[\\Big]{\\text{31 lugares}}{(11\\dots11)_2}\n", | |
"$, de $-(2^{31} - 1)$ a $(2^{31} - 1)$\n", | |
"\n", | |
"### Error en la representación de números flotantes\n", | |
"\n", | |
"Supongamos $x \\gt 0$ (si $x \\lt 0$, se hace de forma análoga), y que tenemos 32 bits.\n", | |
"\n", | |
"$x = q \\cdot 2^m$; $\\dfrac{1}{2} \\leq q \\lt 1$ y $\\annoterel{\\text{x es un número}\\\\\\text{de maquina}}{|m| \\lt 127}$\n", | |
"\n", | |
"¿Cuál es el número de máquina más cercano?\n", | |
"\n", | |
"$x = (0.a_1a_2\\dots a_{24}a_{25}a_{26}\\dots)_2 \\cdot 2^m$\n", | |
"\n", | |
"```\n", | |
"<----------|----|----|----------> R\n", | |
" x' x x''\n", | |
"```\n", | |
"\n", | |
"Llamo $x'$ al número de la izquierda más cercano y $x''$ al de la derecha más cercano.\n", | |
"\n", | |
"Es claro que:\n", | |
"\n", | |
"$x' = (0.a_1a_2\\dots a_{24})_2 \\cdot 2^m$\n", | |
"\n", | |
"$x' = ((0.a_1a_2\\dots a_{24})_2 + 2^{-24})\\cdot 2^m$\n", | |
"\n", | |
"**Observaciones**:\n", | |
"\n", | |
"$x'' - x' = 2^{-24} \\cdot 2^m$\n", | |
"\n", | |
"Miro $x - x'$ y $x'' - x$ y me quedo con el $x'$/$x''$ que me dé más chica la cuenta.\n", | |
"\n", | |
"**Observaciones**:\n", | |
"\n", | |
"Si el más cercanoes $x'$ entonces:\n", | |
"\n", | |
"$|x - x'| \\leq \\dfrac{1}{2} \\cdot |x'' - x'| = \\dfrac{1}{2} \\cdot 2^{-24} \\cdot 2^m = 2^{-25}$\n", | |
"\n", | |
"**Nombres**:\n", | |
"\n", | |
"- $|x - x'|$ es el `ERROR`\n", | |
"- $\\dfrac{|x - x'|}{|x|}$ es el `ERROR RELATIVO`\n", | |
"\n", | |
"Además:\n", | |
"\n", | |
"$\\dfrac{|x - x'|}{|x|} \\leq \\annoterel{q \\geq \\frac{1}{2}}{\\dfrac{2^{n - 25}}{q \\cdot 2^m}} \\leq \\dfrac{2^{-25}}{2^{-1}} = 2^{-24}$\n", | |
"\n", | |
"- Si el más cercado es $x''$ hago lo mismo. ¿Sí $x$ está fuera del rango de la computadora?\n", | |
"- Si $m \\gt 0$ y $|m| > 127$ $\\implies$ `OVERFLOW` (en muchas computadoras `NaN`).\n", | |
"- Si $m \\lt 0$ y $|m| > 127$ $\\implies$ `UNDERFLOW` (en general devuelve $0$ y sigue...).\n", | |
"\n", | |
"**Resumen**:\n", | |
"\n", | |
"Si $x \\neq 0$ número flotane en el rango de la máquina. Llamamos y notamos:\n", | |
"\n", | |
"$x* = fl(x)$; al número de máquina más cercano\n", | |
"\n", | |
"**Observaciones**:\n", | |
"\n", | |
"$x* = x \\cdot (1 + \\delta)$; con $\\delta = \\dfrac{x* - x}{x}$\n", | |
"\n", | |
"y vimos que $|\\delta| \\leq 2^{-24}$; (en 32 bits).\n", | |
"\n", | |
"**Nombres**:\n", | |
"\n", | |
"$2^{-24}$ se llama **error de redondeo** de la unidad o épsilon de máquina.\n", | |
"\n", | |
"Ejemplo: calcular $x*$ en 32 bits para $x = \\dfrac{1}{10}$.\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"\\dfrac{1}{10} & = (0.0001100110011001100110011001100110011001100110011001101)_2 \\\\\n", | |
"& = (0.1100110011001100110011001100110011001100110011001101)_2 \\cdot 2^{-3}\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"x' & = (0.\\annoterel{\\text{24 lugares}}{110011001100110011001100})_2 \\cdot 2^{-3}\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"x'' & = (0.110011001100110011001101)_2 \\cdot 2^{-3}\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"x - x' & = (0.\\annoterel{\\text{24 lugares}}{000000000000000000000000}~1100110011001100110011001101)_2 \\cdot 2^{-3} \\\\\n", | |
"& = (0.1100110011001100110011001101)_2 \\cdot 2^{-24} \\cdot 2^{-3} \\\\\n", | |
"& = \\boxed{\\dfrac{1}{10} \\cdot 2^{-24}}\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"x'' - x & = (x'' - x') - (x - x') \\\\\n", | |
"& = 2^{-24} \\cdot 2^{-3} - \\dfrac{1}{10} \\cdot 2^{-24} \\\\\n", | |
"& = (\\dfrac{1}{8} - \\dfrac{1}{10}) \\cdot 2^{-24} \\\\\n", | |
"& = \\boxed{\\dfrac{1}{40} \\cdot 2^{-24}}\n", | |
"\\end{align}\n", | |
"$ \n", | |
"\n", | |
"Luego, $x* = x''$\n", | |
"\n", | |
"### Operaciones\n", | |
"\n", | |
"Vamos a asumir que la computadora opera con exactitud, luego normaliza y luego redondea.\n", | |
"\n", | |
"- Si $x$, $y$ son números de máquina:\n", | |
"\n", | |
" $fl(x \\odot y) = [x \\odot y] \\cdot (1 + \\delta)$ con $|\\delta| \\leq \\epsilon$\n", | |
" \n", | |
" $\\odot = +, -, \\times, \\div$. $\\epsilon$ (el épsilon de la máquina).\n", | |
" \n", | |
"- Si $x$, $y$ **no** son números de máquina\n", | |
"\n", | |
" $fl(fl(x) \\odot fl(y)) = [(x \\cdot (1 + \\delta_1)) \\odot (y \\cdot (1 + \\delta_2))] \\cdot (1 + \\delta_3)$ con $|\\delta_1| \\cdot |\\delta_2| \\cdot |\\delta_3| = \\epsilon$\n", | |
"\n", | |
"Ejemplo: $x$, $y$, $z$ números de máquina.\n", | |
"\n", | |
"$$\n", | |
"\\begin{align}\n", | |
"fl(x \\cdot (y + z)) & = x \\cdot fl(y + z) \\cdot (1 + \\delta_1) && |\\delta_1| \\leq \\epsilon \\\\\n", | |
"& = x \\cdot (y + z) \\cdot (1 + \\delta_2) \\cdot (1 + \\delta_1) && |\\delta_2| \\leq \\epsilon \\\\\n", | |
"& = x \\cdot (y + z) \\cdot (1 + \\delta_1 + \\delta_2 + \\delta_2\\delta_1) && \\delta_2\\delta_1 \\lt\\lt \\delta_2,\\delta_1 \\text{ lo podemos despreciar} \\\\\n", | |
"& \\approx x \\cdot (y + z) \\cdot (1 + \\delta_1 + \\delta_2) && \\delta_1 + \\delta_2 = \\delta_3 \\text{ y } |\\delta_3|\\leq 2 \\cdot \\epsilon\n", | |
"\\end{align}\n", | |
"$$\n", | |
"\n", | |
"**Observaciones**: en una máquina de 32 bits no siempre se puede hacer con exactitud $x \\odot y$. Pero se pueden usar más bits que los que se usan para los números de máquina.\n", | |
"\n", | |
"**Guard-bits**: temporalmente y con más presición\n", | |
"\n", | |
"### Algoritmo para estimar él número de máquina\n", | |
"\n", | |
"**Observaciones**: si $fl(1 + \\epsilon) = 1 \\implies \\dfrac{\\epsilon}{2} \\leq \\epsilon_M$ (y vamos a tomar $\\epsilon_M \\approx \\dfrac{\\epsilon}{2}$)\n", | |
"\n", | |
"**Desarrollo**:\n", | |
"\n", | |
"$$\n", | |
"\\begin{align}\n", | |
"fl(1 + \\epsilon) = (1 + \\epsilon) \\cdot (1 + \\delta) & = 1 && \\text{con } |\\delta| \\leq \\epsilon_M \\\\\n", | |
"1 + \\delta + \\epsilon + \\epsilon\\delta & = 1 \\\\\n", | |
"\\delta \\cdot (1 + \\epsilon) & = -\\epsilon \\\\\n", | |
"\\delta & = \\dfrac{-\\epsilon}{(1 + \\epsilon)}\n", | |
"\\end{align}\n", | |
"$$\n", | |
"\n", | |
"luego: $|\\delta| = \\dfrac{-\\epsilon}{(1 + \\epsilon)} \\annoterel{\\text{vamos a}\\\\\\text{tomar }\\epsilon \\leq 1}{\\geq} \\dfrac{\\epsilon}{2}$\n", | |
"\n", | |
"$\\implies \\dfrac{\\epsilon}{2} \\leq |\\delta| \\leq \\epsilon_M$\n", | |
"\n", | |
"$\\implies \\boxed{\\dfrac{\\epsilon}{2} \\leq \\epsilon_M}$\n", | |
"\n", | |
"Tomo $\\epsilon = 2^{-1}, 2^{-2}, \\dots$ hasta que se verifique $fl(1 + \\epsilon) = 1$" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"e_M: 5.551115123125783e-17\n" | |
] | |
} | |
], | |
"source": [ | |
"e = 2**(-1)\n", | |
"\n", | |
"while True:\n", | |
" if (1 + e) == 1:\n", | |
" print('e_M:', e / 2)\n", | |
" break\n", | |
" else:\n", | |
" e = e / 2" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"### Errores evitables\n", | |
"\n", | |
"El error de redondero es un error inevitable, pero hay otros errores que sí son evitables.\n", | |
"\n", | |
"Ejemplo: computadora decimal con 5 digitos de mantisa.\n", | |
"\n", | |
"$\n", | |
"\\begin{align}\n", | |
"x & = 0.3721478693 && \\to fl(x) = 0.37215 \\\\\n", | |
"y & = 0.3720230572 && \\to fl(y) = 0.37202 \\\\\n", | |
"\\implies x - y & = 0.000124812 && \\to fl(x) - fl(y) = 0.00013\n", | |
"\\end{align}\n", | |
"$\n", | |
"\n", | |
"$\\left|\\dfrac{(x - y) - (fl(x) - fl(y))}{x - y}\\right| = \\dfrac{0.000005188}{0.000124812} = 0.041\\dots$\n", | |
"\n", | |
"$\\implies$ error relativo $\\approx 4\\%$\n", | |
"\n", | |
"**Regla**: evitar (en lo posible) restar dos números parecidos.\n", | |
"\n", | |
"Ejemplo: $y = \\underbrace{\\sqrt{x^2 + 1}}_{A} - \\underbrace{1}_{B}$\n", | |
"\n", | |
"Si calculo $A$, después $B$, y después resto genera grandes errores si $x \\sim 0$\n", | |
"\n", | |
"Otra forma:\n", | |
"\n", | |
"$$\n", | |
"\\left(\\sqrt{x^2 + 1} - 1\\right) \\cdot \\dfrac{\\left(\\sqrt{x^2 + 1} + 1\\right)}{\\left(\\sqrt{x^2 + 1} + 1\\right)} = \\dfrac{x^2 + \\cancel 1 - \\cancel 1}{\\sqrt{x^2 + 1} + 1} = \\dfrac{\\overbrace{x^2}^{A}}{\\underbrace{\\sqrt{x^2 + 1} + 1}_{B}}\n", | |
"$$\n", | |
"\n", | |
"Calculo $A$, después $B$, después divido:\n", | |
"\n", | |
"### Procesos estables e inestables\n", | |
"\n", | |
"Ejemplo: calcular la siguiente sucesión recursiva.\n", | |
"\n", | |
"$$\n", | |
"\\begin{cases}\n", | |
"x_0 = 1 \\\\\n", | |
"x_1 = \\dfrac{1}{3} \\\\\n", | |
"x_{n+1} = \\dfrac{13}{3} \\cdot x_n - \\dfrac{4}{3} \\cdot x_{n - 1}\n", | |
"\\end{cases}\n", | |
"$$\n", | |
"\n", | |
"Se puede ver que $x_n = \\left(\\dfrac{1}{3}\\right)^n$\n", | |
"\n", | |
"Calcular la sucesión de manera recursiva es de por sí inestable (arrastro el error de los pasos anteriores) y además amplía el error por $\\frac{13}{3}$!!\n", | |
"\n", | |
"Mejor, ver que vale $x_n = \\left(\\dfrac{1}{3}\\right)^n$\n", | |
"\n", | |
"Se demuestra de manera inductiva:\n", | |
"\n", | |
"- Vale para $n = 0$ y $n = 1$\n", | |
"- $n \\implies n + 1$, si vale $\\forall n \\lt n + 1$ entonces también vale para $n + 1$.\n", | |
"\n", | |
"$$\n", | |
"\\begin{align}\n", | |
"x_{n + 1} & = \\dfrac{13}{3} \\cdot \\left(\\dfrac{1}{3}\\right)^n - \\dfrac{4}{3} \\cdot \\left(\\dfrac{1}{3}\\right)^{n -1} \\\\\n", | |
"& = \\left(\\dfrac{1}{3}\\right)^{n - 1} \\cdot \\left[\\dfrac{13}{3} \\cdot \\dfrac{1}{3} - \\dfrac{4}{3}\\right] \\\\\n", | |
"& = \\left(\\dfrac{1}{3}\\right)^{n - 1} \\cdot \\dfrac{1}{3} \\cdot \\left[\\dfrac{13}{3} - \\dfrac{4}{3}\\right] \\\\\n", | |
"& = \\left(\\dfrac{1}{3}\\right)^n \\cdot \\left(\\dfrac{13 - 12}{3}\\right) \\\\\n", | |
"& = \\left(\\dfrac{1}{3}\\right)^n \\cdot \\left(\\dfrac{1}{3}\\right) \\\\\n", | |
"& = \\boxed{\\left(\\dfrac{1}{3}\\right)^{n + 1}}\n", | |
"\\end{align}\n", | |
"$$\n", | |
"\n", | |
"¿Cómo sé que $x_n = \\left(\\dfrac{1}{3}\\right)^n$?\n", | |
"\n", | |
"Me fijo si existen $A, B, \\lambda, \\mu \\in \\mathbb{R}$ que satisfagan:\n", | |
"\n", | |
"$$x_n = A \\cdot \\lambda^n + B \\cdot \\mu^n \\tag{*}\\label{*}$$\n", | |
"\n", | |
"Y de la ecuación de recurrencia despejo $\\lambda$, $\\mu$, (luego de los datos $x_0$, $x_1$, voy a sacar $A$ y $B$).\n", | |
"\n", | |
"Si supongo que vale $\\eqref{*}$, entonces, en la fórmula de recurrencia:\n", | |
"\n", | |
"$$\n", | |
"\\begin{align}\n", | |
"A \\cdot \\lambda^{n + 1} + B \\cdot \\mu^{n + 1} = \\left(A \\cdot \\lambda^n + B \\cdot \\mu^n\\right) - \\dfrac{4}{3} \\cdot \\left(A \\cdot \\lambda^{n - 1} + B \\cdot \\mu^{n - 1}\\right) \\\\\n", | |
"A \\cdot \\left(\\lambda^{n + 1} - \\dfrac{13}{3} \\cdot \\lambda^n + \\dfrac{4}{3} \\cdot \\lambda^{n - 1}\\right) + B \\cdot \\left(\\mu^{n + 1} - \\dfrac{13}{3} \\cdot \\mu^n + \\dfrac{4}{3} \\cdot \\mu^{n - 1}\\right) = 0 \\\\\n", | |
"A \\cdot \\lambda^{n - 1} \\cdot \\left(\\lambda^2 - \\dfrac{13}{3} \\cdot \\lambda + \\dfrac{4}{3}\\right) + B \\cdot \\mu^{n - 1} \\cdot \\left(\\mu^2 - \\dfrac{13}{3} \\cdot \\mu + \\dfrac{4}{3}\\right) = 0\n", | |
"\\end{align}\n", | |
"$$\n", | |
"\n", | |
"esto tiene que valer $\\forall n \\in \\mathbb{N} \\implies \\lambda, \\mu$ soluciones de:\n", | |
"\n", | |
"$$\n", | |
"x^2 - \\dfrac{13}{3} \\cdot x + \\dfrac{4}{3} = 0 \\\\\n", | |
"3 \\cdot x^2 - 13 \\cdot x + 4 = 0 \\\\\n", | |
"x_{1,2} = \\dfrac{13 \\pm \\sqrt{13^2 - 4 \\cdot 3 \\cdot 4}}{2 \\cdot 3} = \\begin{cases}\n", | |
"x_1 = 4 \\\\\n", | |
"x_2 = \\dfrac{1}{3}\n", | |
"\\end{cases} \\\\\n", | |
"\\implies x_n = A \\cdot 4^n + B \\cdot \\left(\\dfrac{1}{3}\\right)^n\n", | |
"$$\n", | |
"\n", | |
"Usando $x_0$ y $x_1$, que son datos:\n", | |
"\n", | |
"$$\n", | |
"\\begin{align}\n", | |
"x_0 = A \\cdot 4^0 + B \\cdot \\left(\\dfrac{1}{3}\\right)^0 & = A + B = 1 \\tag{1}\\label{1}\\\\\n", | |
"x_1 = A \\cdot 4^1 + B \\cdot \\left(\\dfrac{1}{3}\\right)^1 & = A \\cdot 4 + B \\cdot \\dfrac{1}{3} = \\dfrac{1}{3} \\tag{2}\\label{2}\n", | |
"\\end{align}\n", | |
"$$\n", | |
"\n", | |
"Resolvemos el sistema de ecuaciones:\n", | |
"\n", | |
"$$\n", | |
"\\begin{align}\n", | |
"A = 1 - B \\implies \\left(1 - B\\right) \\cdot 4 + B \\cdot \\dfrac{1}{3} & = \\dfrac{1}{3} \\\\\n", | |
"4 - B \\cdot 4 + B \\cdot \\dfrac{1}{3} & = \\dfrac{1}{3} \\\\\n", | |
"B \\cdot \\left(\\cancel{\\dfrac{1}{3} - 4}\\right) & = \\underbrace{\\cancel{\\dfrac{1}{3} - 4}}_1 \\implies \\boxed{B = 1} \\implies \\boxed{A = 0} \\\\\n", | |
"\\boxed{x_n = \\left(\\dfrac{1}{3}\\right)^n}\n", | |
"\\end{align}\n", | |
"$$" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"### Notas de la clase\n", | |
"\n", | |
"- Programaremos en Python.\n", | |
"- Entrega 1 TP hasta el ejercicio 11: El próximo sábado, puede ser después de la clase." | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.7.6" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment