Skip to Content
Análisis NuméricoIntroducción (AN)

Introducción (AN)

En Análisis Numérico se adquieren las herramientas básicas para formular y resolver problemas de matemática, los algoritmos necesarios, discernir las técnicas más convenientes para resolver cada problema e interpretar los resultados obtenidos.

Algunos temas son: análisis de errores, sistemas de punto flotante, interpolación polinomial, entre otros.

Modelos matemáticos

Un modelo matemático es una representación aproximada de un problema/situación de la vida real.

Podemos considerar un modelo matemático como una buena descripción del problema a estudiar.

Existen dos caminos posibles para solucionar el problema planteado en el modelo: la primera es hacer simplificaciones para obtener una solución analítica (pudiendo diferir mucho del problema real). La segunda es hacer aproximaciones numéricas (pudiendo introducir errores), estudiando/estimando como las aproximaciones afectan a la precisión de la solución.


Modelo Matemático 1


Problema Matemático

⇓

Solución Analítica

Modelo Matemático 2


Problema Matemático

⇓Aproximaciones

Problema Numérico

⇓

Solución Numérica

Un problema numérico es una descrición clara de la conexión funcional entre datos de entrada (variables independientes / input) y datos de salida (resultados deseados / output). Estos datos consisten en un conjunto finito de cantidades reales.

Para resolver un problema numérico, además de la teoría matemática, se utilizan computadoras y algoritmos.

Para un problema numérico, un algoritmo es una descripción de un número finito de pasos con operaciones definidas (sin ambiguedades), donde una lista de datos de entrada se convierte en una lista de datos de salida.

La materia Análisis Numérico formula y estudia métodos numéricos/algoritmos para obtener la solución de problemas modelizados matemáticamente.

Órdenes de convergencia

Las soluciones de problemas numéricos no suelen ser fórmulas cerradas, sino una sucesión de aproximaciones cuya precisión aumenta progresivamente. Por ello es necesario comprender los conceptos de convergencia de sucesiones (y su velocidad)

Sea {Xn}\{ X_n \} una sucesión de reales que converge a x∗  x_* \;,
{Xn}\{ X_n \} tiene tasa de convergencia es (al menos) lineal si existe una constante cc donde   0<c<1  ∧  N∈N\; 0 < c < 1 \; \land \; N \in \NN tal que:

∣xn+1−x∗∣≤c∣xn−x∗∣,  ∀n≥N|x_{n+1} - x_*| \leq c|x_{n} - x_*|, \; \forall n \geq N

Ejemplo:

La sucesión dada por xn=3−n,  n∈Nx_n = 3^{-n}, \; n \in \NN

xn=3−n=13nx_n = 3^{-n} = \frac{1}{3^n} \\

Su valor de convergencia es:

lim⁡n→∞  13n=0\displaystyle{\lim_{n \to \infty}} \; \frac{1}{3^n} = 0

Buscamos la constante cc en base a la definición anterior:

∣xn+1−x∗∣∣xn−x∗∣=c\frac{|x_{n+1} - x_*|}{|x_n - x_*|} = c

Reemplazamos xnx_n por el valor de la sucesión y x∗x_* por su valor de convergencia:

∣3−(n+1)−0∣∣3−n−0∣=3−(n+1)3−n=3n3n+1=3n3n⋅3=13\frac{|3^{-(n+1)} - 0|}{|3^{-n} - 0|} = \frac{3^{-(n+1)}}{3^{-n}} = \frac{3^n}{3^{n+1}} = \frac{\cancel{3^n}}{\cancel{3^n} \cdot 3} = \frac{1}{3}

Por lo tanto,

∣xn+1−0∣=13∣xn−0∣,  ∀n|x_{n+1} - 0| = \frac{1}{3}|x_n - 0| , \; \forall n

La tasa de convergencia es (al menos) superlineal si existe una sucesión {ϵn}\{ \epsilon_n \} que converge a   0  ∧  N∈N\; 0 \; \land \; N \in \NN tal que:

∣xn+1−x∗∣≤ϵn∣xn−x∗∣,  ∀n≥N|x_{n+1} - x_*| \leq \epsilon_n|x_{n} - x_*|, \; \forall n \geq N

Ejemplo:

La sucesión dada por xn=1n!,  n∈Nx_n = \frac{1}{n!}, \; n \in \NN. Como esta sucesión converge en 00, tenemos que:

∣xn+1−0∣∣xn−0∣=n!(n+1)!=n!n!⋅(n+1)=1n+1!\frac{|x_{n+1} - 0|}{|x_n - 0|} = \frac{n!}{(n+1)!} = \frac{\cancel{n!}}{\cancel{n!} \cdot (n+1)} = \frac{1}{n+1!}

La sucesión 1n+1\frac{1}{n+1} también converge a 00, se cumple que:

∣xn+1−0∣=1n!∣xn−0∣,  ∀n|x_{n+1} - 0| = \frac{1}{n!}|x_n - 0| , \; \forall n

La tasa de convergencia es (al menos) cuadrática si existe una constante   c>0  ∧  N∈N\; c > 0 \; \land \; N \in \NN tal que:

∣xn+1−x∗∣≤c∣xn−x∗∣2,  ∀n≥N|x_{n+1} - x_*| \leq c|x_{n} - x_*|^2, \; \forall n \geq N

Notación Big-O y Little-O

Sean {xn},{αn}\{x_n\}, \{\alpha_n\} sucesiones distintas, si existen una constante   c>0  ∧  r∈N\; c > 0 \; \land \; r \in \NN se establece:

∣xn∣≤c∣αn∣,  ∀n≥r  ⟹  xn=O(αn)|x_n| \leq c|\alpha_n|, \; \forall n \geq r \implies x_n = \bigO(\alpha_n)

Si existe una sucesión {ϵn}\{\epsilon_n\} que converge a   0\; 0, con ϵn≥0  ∧  r∈N\epsilon_n \geq 0 \; \land \; r \in \NN se establece:

∣xn∣≤ϵn∣αn∣,  ∀n≥r  ⟹  xn=o(αn)|x_n| \leq \epsilon_n|\alpha_n|, \; \forall n \geq r \implies x_n = o(\alpha_n)

(intuitivamente esto dice lim⁡n→∞  xnαn=0\displaystyle{\lim_{n \to \infty}} \; \frac{x_n}{\alpha_n} = 0)

Esta notación también se puede usar para comparar funciones de la siguiente forma:

∣f(x)∣≤c∣g(x)∣,  ∀x≥r  ⟹  f(x)=O(g(x)),  x→∞|f(x)| \leq c|g(x)| , \; \forall x \geq r \implies f(x) = \bigO(g(x)), \; x \rightarrow \infty 0<lim⁡x→∞  f(x)g(x)<∞  ⟹  f(x)=O(g(x)),  x→∞0 < \displaystyle{\lim_{x \to \infty}} \; \frac{f(x)}{g(x)} < \infty \implies f(x) = \bigO(g(x)), \; x \rightarrow \infty

Análogamente,

lim⁡x→∞  f(x)g(x)=0  ⟹  f(x)=o(g(x)),  x→∞\displaystyle{\lim_{x \to \infty}} \; \frac{f(x)}{g(x)} = 0 \implies f(x) = o(g(x)), \; x \rightarrow \infty

Ejemplo 1:

n+1n2=O(1n)\frac{n+1}{n^2} = \bigO(\frac{1}{n})

En base a la definición:

n+1n2≤c1nn+1n≤c\begin{aligned} \frac{n+1}{n^2} &\leq c \frac{1}{n} \\ \frac{n+1}{n} &\leq c \end{aligned}

Basta con tomar c=2,  r=1c = 2, \; r = 1

Ejemplo 2:

1nln⁡n=o(1n)\frac{1}{n \ln n} = o(\frac{1}{n})

Siguiendo la definición:

1nln⁡n≤ϵn1n\frac{1}{n \ln n} \leq \epsilon_n \frac{1}{n}

Basta con tomar ϵn=1ln⁡n\epsilon_n = \frac{1}{\ln n}

Última vez actualizado el
Recorridas de GrafosIntroducción (OdC)