Programación numérica (página 2)

Partes: 1, 2

FPR
Potencia
Pot(x,y)=x*pot(x,y-1)
Pot(x,0)=1

La recursión desde el punto de vista de C
Como se crean funciones (tamaños y tipos de datos.
Se puedo aproximar el numero de veces que una Recursión se va ha realizar.
El Stack (over flow y underflow)
Esqueleto de una función
Funciones Vacías
Ejercicios
Imprimir números del 1 al 10
Hacia delante
Hacia atrás

Que procesos hace la recursión en la computadora
Bajo una llamada recursiva el sistema reserva espacio (tabla de activación, también llamada Stack o Pila) donde almacenar una copia de los objetos locales y parámetros del subprograma en ese momento (variables locales, parámetros y la dirección de reingreso).
La tabla de activación se amontona sobre las llamadas recursivas anteriores formando lo que se conoce como pila recursiva.
Este proceso termina cuando un nuevo valor del parámetro no produce una nueva llamada recursiva (se alcanza el caso base).
Una vez alcanzada esta situación el sistema va liberando el espacio reservado conforme los subprogramas se van ejecutando sobre su tabla de activación.
Este proceso finaliza con la llamada inicial.

Como Funciona la memoria de la computadora

Función que busca un dato en un arreglo (tarea modificarlo para que busque en un arreglo bidimensional)
Función que imprime una cadena al revés (ejemplo de cuando no usar la recursión)

Procesos recursivos e iterativos
x=0 0; x=1 1
Fibonacci(X)
x>2 fibonacci(x-1) + fibonacci(x-2)

int fbI(int z)
{ int R,i,a,b;
R=1;
a=0; b=1; i=1;
while(i< z)
{ R=a+b;
a=b; b=R;
i++
}
}
int fbR(int z)
{ if (z==0)
return 0;
else
if (z==1)
return 1;
else
return fbR(z-1)+fbR(z-2);
}

Números de catalán
Uso de los números de Catalán.
El juego de la vida problemas poblacionales

Número Aureo

Particiones y combinatorias
Como obtener las combinatorias de un conjunto de términos o de un conjunto

Búsqueda en profundidad y anchura

Particiones de números
Dado un número natural n llamamos “particiones de n” a todas las maneras de escribir n como suma de números naturales. Por ejemplo: hay 11 particiones del número 6:
1+1+1+1+1+1 2+1+1+1+1
2+2+1+1 2+2+2
3+1+1+1 3+2+1
3+3 4+1+1
4+2 5+1
6

Diversos matemáticos han propuesto teorías de cómo calcular el numero de formas de partir un número en sumas, el más conocido de ellos fue Leonard Euler quien expuso una serie de conjeturas al respecto

Particiones de números
De las teorías de Euler se desprende que la suma de valores anteriores de la serie de números nos establece el numero de particiones de un numero.
Por ejemplo si p(n) representa el numero de particiones de un numero “n” es decir p(n) son el total de formas distintas de obtener “n”, haciendo sumas temenos que:
p(4)= p(3)+p(2)
p(6)= p(5)+p(4)-p(1)
P(5)=p(4)+p(3)-p(1)
p(9)=p(8)+p(7)-p(4)-p(2)

Particiones de números
Estos valores provienen de la formula matemática

En donde el limite ó paro de la sumatoria esta dado por el hecho de que la resta de n con el término debe de ser positivo o cero, y conocemos que p(0)=1;

Dos problemas

Particiones de números
Como se representaría de forma 100% recursiva esta formula?
Como se pueden obtener las combinaciones en si?, es decir todas las sumas?
Planteando el problema desde otro punto de vista: tenemos a un conjunto formado por números del 1 hasta n, que combinación con repetición podemos hacer de ese conjunto de elementos de tal suerte que la suma de los elementos de cada combinación sumen n.
1,2,3,
4,5,6
Conjunto de elementos para n=6, el problema de esto es la cantidad de combinaciones a evaluar, 46656 combinaciones.

Particiones de conjuntos
Una partición de un conjunto X es una colección
{A1,A2, . . . ,An} de subconjuntos de X, no vacíos y disjuntos
dos a dos, tales que A1 U A2 U .. . U An = X.
A cada uno de los conjuntos Ai se le llama bloque de la partición.
Las particiones del conjunto {a, b, c} son:
{a, b, c} (un solo bloque),
{a, b}, {c} (2 bloques),
{a, c}, {b} (2 bloques),
{b, c}, {a} (2 bloques),
{a}, {b}, {c} (3 bloques).

Particiones de conjuntos
Para un conjunto de 3 elementos tenemos 5 formas diferentes de partir el conjunto.
El número total de particiones que admite un conjunto de n elementos se denomina número de Bell de orden n y se denota Bn.
Se sabe que Los primeros números de Bell son
B0 = 1, B1 = 1, B2 = 2 B3 = 5.
SE puede obtener el numero de particiones de un conjunto a partir de la siguiente formula

Coeficientes Binomiales
Los coeficientes binomiales, que son los coeficientes enteros de la expansión de (a+b)n fueron conocidos en el siglo XII. El triángulo de Pascal que es un arreglo triangular de los coeficientes binomiales fue desarrollado en el siglo XIII.
En donde cada entrada de la tabla es la suma de los dos números que están inmediatamente encima de ella

Particiones de conjuntos
Por otra parte, el número de particiones que admite un conjunto de n elementos con exactamente k bloques se denomina número de Stirling de segunda clase con índices n y k y se denota mediante el símbolo

Cuya relación de recurrencia es la siguiente :

Torres de Hanoi
El problema consiste en mover n discos (todos ellos de diferente tamaño) de un poste a otro siguiendo las reglas
Solo se puede mover un disco a la vez
Un disco grande no puede quedar encima de otro de menor tamaño

Torres de Hanoi

Posibilidades de 4 discos

Torres de Hanoi
Solución: No seguir un proceso ordenado podría llevarnos a un camino cerrado o a un serie de pasos redundantes.
Realmente la solución viene dada por el hecho de solucionar un problema previo, es decir antes de mover el último disco necesitamos mover todos los de arriba de él a otro poste.

Torres de Hanoi
Solución
1- Mover n-1 discos de A a B
2- Mover 1 disco de A a C
3- Mover n-1 discos de B a C

Torres de Hanoi
void Hanoi( n, inicial, aux, final )
{ if ( n>0 )
{ Hanoi(n-1, inicial, final, aux );
printf("Mover %d de %c a %c", n, inicial, final );
Hanoi(n-1, aux, inicial, final );
}
}

Josephus Problem
Cuenta una leyenda sobre el historiador Josephus Flavius que, durante las guerras judeo-romanas, él y otros 40 soldados judíos quedaron atrapados en una cueva rodeados por los romanos.  Visto que tenían pocas posibilidades de salir con vida, decidieron suicidarse. Josephus y un amigo suyo no estaban muy felices con esa idea. Así pues, propusieron que si había que hacerlo, se hiciera con cierto orden: se colocarían en círculo y se irían suicidando por turno cada tres empezando a contar por uno determinado.
Josephus y su amigo se colocaron de tal forma que fueron los dos últimos y así, como ya nadie les podía llevar la contraria, decidieron seguir viviendo.

Fractales
Un fractal es un objeto semi geométrico cuya estructura básica se repite a diferentes escalas.
El término fue propuesto por el matemático Benoît Mandelbrot en 1975 y deriva del Latín fractus, que significa quebrado o fracturado. Los fractales pueden ser generados por un proceso recursivo o iterativo, capaz de producir estructuras auto-similares a cualquier escala de observación. Los fractales son estructuras geométricas irregulares y de detalle infinito. Muchas estructuras naturales son de tipo fractal.

Fractales
LA CONSTRUCCIÓN de un fractal, esta la posibilidad de utilizarlo para producir, almacenar, analizar o transmitir una imagen se simplifica considerablemente haciendo uso de la computadora. De hecho, el efecto y la utilidad que ha demostrado tener la geometría fractal no se hubieran manifestado sin las facilidades de cálculo y representación gráfica que proporciona el trabajo en computadora; parecen estar hechos el uno para el otro. Los fractales se generan a través de procesos en los que una misma operación se repite un sin número de veces, y eso es precisamente lo que una computadora sabe hacer mejor.

Tipos de fractales
IFS, sistemas de funciones iteradas
Lindermayer y Sierpinsky
Orbitas Caóticas
Aleatorios y Celulares
Algoritmos de escape, Malderbrot y Julia

Fractales
La mayoría de los métodos desarrollados para construir imágenes fractales se basan en procedimientos muy sencillos que en cualquier lenguaje computacional se expresan en unos cuantos renglones; de ahí la sorpresa que provoca observar la complejidad de la imagen que hacen surgir en la pantalla.

Fractales
Los fractales más simples de crear se basan en las teorías de Lindermayer y Sierpinski, normalmente son procesos recursivos o iterativos que van creando una estructura simétrica basa en procesos pendientes.

Dentro de este grupo de fractales se encuentran los de Niels Helge von Koch y David Hillbert, el primero para la simulación de copos de nieves y el segundo para la creación de semilaberintos.

Fractales
Que se necesita para hacer un fractal de éste tipo?
Un proceso recursivo o iterativo
Un determinado numero de repeticiones que permitan ver el efecto, con un paro determinado por las condiciones del problema
Un número de ramificaciones dentro del proceso que permita representar mejor el problema que se plantea

Solución Ec. No Lineales Raíces de ecuaciones
Sea f(x)=y. Los valores de x que hacen que y=0 se denominan raíces de la ecuación.

Solución Ec. No Lineales Raíces de ecuaciones
Las raíces de un polinomio pueden ser reales o complejas.
Si un polinomio tiene coeficientes a0, a1, a2, a3, .. an-1, an reales, entonces todas las raíces complejas siempre ocurrirán en pares conjugados complejos. Por ejemplo, un polinomio cúbico tiene la siguiente forma general:

El teorema fundamental del álgebra indica que un polinomio de grado n, tiene n raíces. En el caso del polinomio cúbico pueden darse los siguientes casos:
Tres raíces reales distintas.
Una raíz real con multiplicidad 3.
Una raíz real simple y una raíz real con multiplicidad 2.
Una raíz real y un par conjugado complejo.

Solución Ec. No Lineales Raíces de ecuaciones Ejemplo1
3 Raíces reales diferentes
f(x)= x3-3×2-x+3
(x-3)(x+1)(x-1)
x1=3, x2=-1, x3=1

Solución Ec. No Lineales Raíces de ecuaciones Ejemplo 2
1 Raíz real simple y 1 raíz Real con multiplicidad 2
f(x)= x3-12x+16
(x-4)(x-2)2
x1=4, x2=2, x3=2

Solución Ec. No Lineales Raíces de ecuaciones Ejemplo 3
1 Raíz real simple y 1 par conjugado complejo
f(x)= x3-2×2-3x+10
(x+2)(x-(2+i)) (x-(2-i))
x1=-2, x2=2+i, x3=2-i
Tarea investigar cuales son las
Ecuaciones trascendentales.

Solución Ec. No Lineales Raíces reales de ecuaciones algebraicas y trascendentales
En general, los métodos para encontrar las raíces reales de ecuaciones algebraicas y trascendentales se dividen en métodos de intervalos y en métodos abiertos.

Solución Ec. No Lineales Raíces reales de ecuaciones algebraicas y trascendentales
Los métodos de intervalos aprovechan el hecho de que una función en forma típica cambia de signo en la vecindad de una raíz. Reciben dicho nombre debido a que se necesita de dos valores iniciales que deben “encapsular” a la raíz. A través de este tipo de métodos se va reduciendo gradualmente el tamaño del intervalo de manera que la aplicación repetida de los métodos siempre generan aproximaciones cada vez más cercanas al valor real de la raíz, por lo que se dice que son métodos convergentes.

Solución Ec. No Lineales Raíces reales de ecuaciones algebraicas y trascendentales
Los métodos abiertos, en contraparte, se basan en fórmulas que requieren de un solo valor inicial x  (aproximación inicial a la raíz). Algunas veces, estos métodos se alejan del valor real de la raíz conforme crece el número de iteraciones, es decir, divergen .

Solución Ec. No LinealesBisección
El método de Bisección es un método recursivo donde se empieza a analizar el intervalo (x0,x) .
Bisección(x0,x)
Calcular xr
Si f(xr)=0 ó muy pequeño ó se tiene definido un margen de error relativo xr es la solución
Si no Si f(x0)*f(xr)< 0 Bisección(x0,xr)
sino Bisección(xr,x)

Solución Ec. No Lineales Bisección

Solución Ec. No Lineales Bisección
Ejemplo encuentre una raíz que calcule la función x2-9=0, puede ser obvio que la respuesta es -3 ó 3
Si consideramos el intervalos de -5 y 3 estos serían los pasos
mab= (a+b)/2=(-5+3)/2=-1
f(a)=16; f(mab)=-8; f(b)=0
Aunque hay dos cambios de signo lo cual ya nos dice que hay por lo menos 2 soluciones tomamos la 1a.
b=mab osea b=-1

Solución Ec. No Lineales Bisección
Como no encontramos la solución y el error no lo estamos considerando hacemos otra vuelta de cálculos
mab= (a+b)/2=(-5-1)/2=-3
f(a)=16; f(mab)=0; f(b)=-8
Como el cambio de signo se da entre el medio y b cambiamos a
a=mab osea a=-3
Pero como f(mab)=0 el método termina

Solución Ec. No Lineales Bisección
Sin embargo el método no es exacto y tiene muchos error de aproximación aplique el método para el intervalo -5 y 4.
Que sucede.
Que desventajas presenta el método de Bisección, dedúzcalas e investíguelas.

Solución Ec. No Lineales Regla Falsa

Solución Ec. No Lineales Regla Falsa
Basados en la teoría de la línea recta
((x1 –x0 )*f(x1))
xnew = x1 – ——————-
f(x1)-f(x0)
Si f(xnew)=0 ó el margen de error es aceptabe, xnew es la solución
Si no se calculan f(x0) y f(x1), hay que observar el cambio de signo como en bisección y ajustar el punto x0 ó x1 al xnew según sea el caso.
El error se puede calcular en términos relativos
|x new (actual) – x new (anterior) |
—————————————– X 100
x new (actual)

Este forma de calculo del margen de error no es exclusivo de este método se puede utilizar en cualquier calculo que se busque una aproximación

Coeficientes binomiales negativos
Cuando el Exponente a que se va a elevar un binomio es Negativo ó Fraccionario el proceso para obtener los coeficientes es el mismo que para una potencia positiva, con la variación de que su desarrollo es Infinito.

La razón de que su desarrollo tiende a infinito, es que de acuerdo con el “Teorema del Binomio”, en un binomio elevado a cualquier potencia el ultimo término del desarrollo es aquel que tiene el primer término del binomio elevado a la potencia cero por lo tanto cuando se tiene un exponente negativo cada vez que calculamos un término nos alejamos cada vez mas del cero, y si tuviéramos un exponente fraccionario al ir calculando los términos lo brincaríamos.

Coeficientes binomiales negativos
Los CBN son un resultado estándar de las teorías combinacionales, el cual fue derivado por Planck en 1900, y se relacionan con el método de Poisson para el pronostico de comportamientos de eventos.

http://books.google.com.mx/books?id=-pZX2KS2KqMC&pg=PA141&lpg=PA141&dq=%22negative+binomial+coefficient%22&source=web&ots=_RkqEmTqAn&sig=uvQt3bbRYwbUacjf2jpg0FlV2ew&hl=es&sa=X&oi=book_result&resnum=1&ct=result

Funciones enteras y diferencias finitas

Operadores
Sigma S, Sumatoria
Delta ?, incremento
Nabla ? , Gradiente (como delta pero invertido)
Corrimiento , mover los elementos

Ecuaciones Recursivas Homogéneas
Las recurrencias lineales homogéneas tienen la forma: a0tn + a1tn-1 + … + aktn-k = 0 [1]
Donde los ti son los valores buscados (aplicamos el adjetivo de lineal por que no hay términos de la forma titi+j ó ti2, por ejemplo), los coeficientes ai son constantes y la recurrencia es homogénea por que la combinación lineal de los ti es igual a 0.
Soluciones buscadas de la forma tn=xn, donde x es una constante.
Si sustituimos esta solución en [1] obtenemos:
a0xn + a1xn-1 + … + ak xn-k = 0 [2]
Esta ecuación tiene dos soluciones: x=0, que no nos sirve, y

Ecuaciones Recursivas Homogéneas
Esta ecuación tiene dos soluciones: x=0, que no nos sirve, y
a0xk + a1xk-1 + … + ak= 0, ecuación característica asociada a la ecuación recurrente inicial.
Supongamos que las k raíces de esta ecuación característica son r1, r2, …, rk, entonces cualquier combinación lineal

Ecuaciones Recursivas Homogéneas

de términos rin es solución para la ecuación recurrente lineal homogénea

Ecuaciones Recursivas Homogéneas
Por una relación recursiva lineal homogénea de segundo orden con coeficientes constantes entenderemos una expresión definida para todo n número natural positivo de la forma
x n+2 =ax n+1 + bxn ,
donde a y b son dos números reales no nulos y para la que están dados dos valores
reales iniciales x0 y x1 .

Ecuaciones Recursivas Homogéneas
Esta expresión nos permite obtener una sucesión de números reales.
Tiene el inconveniente de que para conocer el valor de la función en un número natural
k arbitrario hay que conocer cuando menos los dos anteriores.
Por esto es deseable encontrar una regla de correspondencia que nos indique cómo calcular el n -ésimo valor de la sucesión sin necesidad de conocer los valores previos.
A esta regla de correspondencia se le llama “forma cerrada” de la relación de recurrencia.

Raíces de la ecuación característica
Las raíces de la ecuación característica nos van a proporcionar un sistema
fundamental de soluciones. Estas raíces pueden ser de varios tipos:
• Si ? es una raíz real simple de la ecuación característica, proporciona una
solución y = e?x de la ecuación diferencial lineal homogénea con coeficientes
constantes.
• Si ? es una raíz real múltiple de orden m de la ecuación característica,
proporciona las soluciones (independientes) y = e?x, y =xe?x, … , y =xm-1e?x de la
ecuación diferencial.
• Si ?= a ± bi son raíces complejas conjugadas de la ecuación característica,
proporciona las soluciones y =eaxcos bx, y =eaxsen bx.
• Si ?= a ± bi son raíces complejas conjugadas de multiplicidad m de la ecuación
característica, proporciona las soluciones y =eaxcos bx, y =eaxsen bx, y =xeaxcos
bx, y =xeax sen bx, … , y =xm-1eaxcos bx , y =xm-1eaxsen bx

Búsqueda de polinomios ajustados a puntos
El análisis de regresión es una técnica estadística para la investigación de la relación entre dos o mas variables, puede emplearse para construir un modelo que permita predecir el comportamiento de una variable y (dependiente, respuesta) en función de una o mas variables (independientes, predictivas) x.
Los comportamientos de estas variables pueden estar definidos en un modelo teórico, o no.

Búsqueda de polinomios ajustados a puntos
Lo anterior se puede lograr usando un diagrama de dispersión lo que nos conduciría a desarrollar un modelo empírico de la relación que mantienen las variables en estudio.

Funciones y Diferencias finitas
Ejemplo : Tenemos un sensor que nos arroja los siguientes datos .

¿Que ecuación nos representa mejor
el comportamiento del dispositivo?

Funciones y Diferencias finitas
Que pasa si tenemos que el mismo el sensor da diferentes valores en muestreos diferentes? Que ecuación representa este comportamiento

Funciones y Diferencias finitas
Cuando conocemos la expresión que denota el comportamiento de cualquier problema encontrar un valor de “y”no es mucho problema.
Que pasa si solo conocemos el comportamiento y no el polinomio que lo representa?

Regresion Lineal
Un polinomio con solamente una variable es cualquier expresión que se puede escribir de la forma
anxn + an-1xn-1 + · · · + a1x1 + a0
donde x es una variable, los exponentes son números enteros no negativos, y los coeficientes son números reales. Una función de la forma
Pn(x)= anxn + an-1xn-1 + · · · + a1x1 + a0 es una función polinomial.

Calculo del error
El problema de ajuste consiste en encontrar los coeficientes ai que hagan que este polinomio se parezca lo más posible a los datos de acuerdo a alguna definición de error.
Definimos el error ei del polinomio en el punto xi como la diferencia entre el valor que toma el polinomio y el valor fi, es decir:
ei = yi – Pn(xi)
Como lo que se busca es minimizar el error hay que sumar todos los errores, de cada punto, la forma final es una ecuación de la forma:

Calculo del error
La importancia de un ajuste radica mas el comportamiento de los datos que en el ajuste de los puntos.
Si tenemos los puntos rojos como la muestra conocida y las líneas verde (Ec. Lineal) y azul (Ec. Cubica o transendental) me muestran 2 ecuaciones, debe de ser obvio que el mejor ajuste lo tiene la azul.

Calculo del error
Que pasa si calculamos un valor fuera del rango conocido?
Las ecuaciones deberían mostrar tendencias claras sobre el comportamiento de la muestra, y en nuestro ejemplo mostrar una tendencia hacia arriba.
¿Cuál ecuación muestra una mejor tendencia?
La respuesta es muy relativa, pero con la información que se tiene la respuesta debería ser la verde.
De aquí se puede desprender que a mayor cantidad de puntos en el muestreo es mejor para establecer el comportamiento de los datos.

El método de diferencias finitas
Este método sirve para encontrar el grado de un polinomio hipotético con el cual se puede representar el comportamiento del dispositivo o problema.
Consiste en empezar a obtener las diferencias entre los valores obtenidos de la variable dependiente.
La variable dependiente puede ser cualquiera de las 2 (x ó y) normalmente es y.

El método de diferencias finitas
Primer diferencia

El método de diferencias finitas
Segunda diferencia, esta se obtiene de los valores de la 1ª diferencia.

El método de diferencias finitas
Se repite el proceso hasta que las diferencias entre los valores disminuye a un rango aceptable.
Que es lo que buscamos encontrar, una linealidad, con lo cual hemos encontrado el grado aparente del comportamiento del problema.

El método de diferencias finitas
Lo que sigue es igual de fácil, es determinar el polinomio, para ellos necesitamos puntos conocidos y la ecuación general del grado del polinomio que creemos que es, en nuestro ejemplo la ecuación sería a2x2+a1x+a0=0.
Tomemos 3 puntos y creemos un sistema simultaneo de ecuaciones.
a2(0)2+a1(0)+a0=2
a2(0.2)2+a1(0.2)+a0=1.804
a2(0.45)2+a1(0.35)+a0=1.008

El método de diferencias finitas
Utilice los datos siguientes para encontrar la f(x), utilice la desviación estándar como paro, valor esperado de la Desviación estándar 0.04 (se pudo haber utilizado la varianza)
La respuesta esta dada cuando la desviación estándar llega a : 0.030038 , siendo un polinomio de grado 3, parecido a : 0.9973 – 0.8044 x – 0.4878 x2 + 0.5327×3

Método de mínimos cuadrados
Es una técnica de optimización matemática que, dada una serie de mediciones, intenta encontrar una función que se aproxime a los datos (un "mejor ajuste").
Supóngase que el conjunto de datos consiste en los puntos (xi,yi) siendo i=1,2,3,..,n. Queremos encontrar f(xi) ? yi
Para llegar a este objetivo, necesitamos obtener los coeficientes de la ecuación hasta un grado razonable. Se utiliza la suma de los residuos al cuadrado, es decir la diferencia del valor obtenido menos la evaluación de la función en el punto x

Esto explica el nombre de mínimos cuadrados.

Mínimos cuadrados
Sin embargo el primer problema es encontrar la ecuación para evaluarla, por lo tanto utilizando derivadas hipotéticas sobre la función hipotética se obtiene que tales derivadas se obtienen de la suma de la incógnita en las subecuaciones derivadas.
De lo cual se deriva una tabla en forma matricial que nos da una razón de coeficientes.

Mínimos cuadrados

Mínimos cuadrados
x={0.05, 0.11, 0.15, 0.31, 0.46, 0.52, 0.7, 0.74, 0.82, 0.98, 1.17}
y={0.956, 0.89, 0.832, 0.717, 0.571, 0.539, 0.378, 0.37, 0.306, 0.242, 0.104}
?xi=6.01 N=11
?xi2=4.6545 ?Yi=5.905
?xi3= 4.1150 ?xiYi=2.1839
?xi4= 3.9161 ?xi2Yi=1.3335
F(x)=0.998-1.018x+0.225×2

Mínimos cuadrados
Como saber a que grado se debe ajustar el polinomio?
En cuanto se aumente el grado del polinomio se reduce el margen de error de los puntos involucrados, pero esto no es bueno.
La respuesta esta en la estadística.
El grado del polinomio se incrementa mientras haya un decremento estadístico SIGNIFICATIVO de la varianza.

Mínimos cuadrados
Para el ejemplo anterior tenemos la siguiente tabla