Aritmetica de la computadora la computadora trabaja con aritmetica finita los numeros representables son racionales se representan con numeros de punto flotante constan de una mantisa y un exponente en base dos y signo tambien pueden representarse los infinitos lo numeros no estan distribuidos uniformente se concentran entorno al cero esto hace que se mantenga el orden del error relativo cosas a evitar y consideraciones al operar con aritmetica finita evitar divisiones por numeros pequenios y multiplicaciones por grandes (ejemplo, piveteo en gauss) conviene operar con numeros pequenios que con grandes ya que estan distribuidos de manera mas densa sumar numeros de ordenes muy distintos puede hacer obsoleto al numero de orden mas bajo, debe considedarse esto al sumar muchos numeros (hacerlo en forma creciente) evitar restar dos numeros muy parecidos (cancelacion catastrofica) no comparar con cero, usar cierta tolerancia para definir que un modulo es lo suficientemente chico (se usa en gauss, en criterios de parada...) diferencia entre error relativo y absoluto epsilon de la computadora (o del sistema de representacion numeros decimales) es el minimo numero tal que 1+e != 1 es una cota superior del error relativo debido al redondeo el error relativo que se comete al representar un numero real x es O(|e|) mientras que el absoluto es de O(e*|x|) diferencia entre problema mal condicionado y algoritmo inestable numericamente si un metodo garantiza precision hasta el epsilon de la maquina entonces es optimo en el sentido de la precision debe tenerse cuidado con la tolerancia que se usa en un algoritmo ya que la aritmetica usada juega un paper importante si bien teoricamente podria converger, una perdida de precision puede evitar la convergencia. para esto se recomienda usar no solo un error relativo como criterio de parada sino tambien la cantidad de iteraciones la aproximacion a un numero puede ser realizada por truncamiento o por rendondeo las computadoras suelen usar redondeo pues se pierde menos precision Algoritmos de ecuaciones no lineales en una variable Motivaciones: puede ser una funcion muy complicada ya para polinomios de 5to grado en adelante no hay formula algebraica optimizacion: encontrar los ceros de una derivada en toda ciencia hay que resolver ecuaciones no lineales recordar que cualquier ecuacion puede llevarse a buscar una raiz hablar de definicion de convergencia lineal, cuadratica, bla hablar de criterios de parada y casos problematicos como la serie geometrica o la funcion 1/x biseccion hipotesis: dos puntos con signo distintos si la fucnion es continua, converge tiene convergencia lineal describir el metodo se basa en teorema de Bolzano iteraciones de punto fijo el problema del punto fijo es equivalente a la raiz de ecuacion definicion de itearcion de punto fijo si la iteracion de punto fijo converge entonces conv a pto fijo si una funcion es continua y va de la bola cerrada al mismo conjunto entonces tiene punto fijo si la derivada es menor o igual a un k menor a uno y va de un intervalo cerrado al mimso intervalo entonces la iteracion de punto fijo converge al UNICO punto fijo (partiendo desde cualquier punto inicial en el intervalo) si las primeras k-1 derivadas de G existen y son cero en el punto fijo y la k es distinta de cero entonces, si la iteracion de punto fijo converge lo hace con orden de convergencia k newtor es un caso particular de punto fijo converge (si la derivada no se anula en el punto y se esta suficientemente cerca) de forma cuadratica suele realizarse una primera aproximacion con biseccion para alcanzar el intervalo en el cual newton converge cuadraticamente (heuristica) hacer el dibujito de la interpretacion geometrica en cada paso se aproxima la funcion mediante su derivada y se busca el punto fijo puede ser muy dificil o caro conseguir la derivada secante igual que newton pero se aproxima la derivada con el coeficiente incremental la convergencia es supra lineal (el numero aureo) menor que cuadratica el problema es que se puede producir cancelacion catastrofica realizar el coeficiente incremental por otro lado esta bueno porque no hace falta conocer a la derivada de manera algebraica regula falsi similar a biseccion (mismas hipotesis) pero en lugar de usar el punto medio usas el punto que cruza la recta que une a con b de esta manera se esta aproximando a la funcion con una recta tiene convergencia lineal pero tiene una mejor constante que biseccion Resolucion de sistemas lineales Motivaciones aparece en todos los campos de la ciencia ecuaciones diferenciales (tenes aceleraciones y queres masas...) sirve para aproximar sistemas mas complejos es un problema completamente resuelto, para cualquier otro sistema de funciones se conocen soluciones en casos particulares pero nunca de forma tan general, ni hay metodos tan optimizados... muuchas funciones importantes son lineales eliminacion gaussiana en cada paso se multiplica por una matriz elemental matrices elementales permutaciones fila sumarle un mult de otra fila mult una fila por una constante dis de cero preservan el subespacio de soluciones del sistema estrategia de pivoteo para mejorar el error por perdida de precision por aritmetica finita se selecciona como pivote el numero de mayor modulo en la columna (piv parcial) si se busca en toda la submatriz piv completo (no suele utilizarse ya que no mejor taanto) LU explciar como se utiliza para resolver sistemas es super piola apra resolver sistemas pues toma cuadratico una vez que descompusiste puede utilizarse para resolver varios sistemas con la misma matriz asociada no toda matriz tiene LU es unica si L tiene 1 en la diag y A es inv A inversible tiene LU sii los menores principales son distintos de cero A de rango k tiene LU si los k menores principales son distintos de cero pero el reciproco no es cierto PLU toda matriz tiene PLU Cholesky, QR, SVD Motivacion resolver sistemas lineales de formas piolas cholesky L * L^t L lower mot puede usarse como criterio para ver si cierta matriz es sim def pos mas estable que gauss menos estacio y menos tiempo que gauss sistemas de ecuaciones cuando la matriz es sim def pos o sim semdef pos A sim def pos sii cholesky sii menores principales pos es una factorizacion unica si la diag es pos si la diag tiene cero entonces no es unica pero A es semidef pos y los mismos algoritmos suelen funcionar algoritmo basico plantear L * L^t y resolver de iz a der y arr ab si A tiene LU y A sim entonces A = LDL^t si D tiene diag pos entonces A tiene chol puede ser preferible quedarse con la factorizacion LDL ya que se evita hacer raices y hay mas matrices que tienen esta factorizacion, resolver el sistema seria igual de facil a partir de esta factorizacion complejidad CUBICA pero suele ser la mitad que LU en sistemas fisicos cuando tenes ecuaciones diferenciales parciales suelen presentarse sistemas sim def pos sirve para invertir matrices pues: B^(-1) = B^t * (B*B^t)^(-1) la ultima matriz se puede invertir con cholesky y el resto es trasponer y multiplicar QR Q ortogonal; R upper mot toda matriz tiene QR por mas que no sea cuadrada es unica si R es de rango completo y su diag es positiva muy estable pues las Q tiene numero de cond 1 sirve para cuadrados minimos lineales obviamente para sistemas de ecuaciones si Q' y Q'' ort entonces Q = Q' * Q'' es ort Q ort sii matiene normas sii columnas son BON sii Q*Q^t=Id se puede generar con reflexiones o rotaciones reflexion de householder (NO CONFUNDIR CON PROYECCION) se refleja con respecto a un hiperplano de manera tal de llevar a cierto vector (columna de la matriz) a un vector con ceros luego de cierto indice para esto se multiplica por una matriz de HH por bloques: Id 0 0 Id-2*u*u^t u = (x-y)/||x-y|| y = (+-||x||, 0, ..., 0) el mas menos es para evitar cancelacion catastrofica mejor que givens si la matriz no es esparza rotacion de givens se rota con respecto a un vector de manera tal de obtener un cero en una posicion especifica de la matriz en 2x2 se usa matriz de la forma (se generaliza "facilmente") c -s s c c = a/sqrt(a^2+b^2) s = -b/sqrt(a^2+b^2) donde a y b son los coeficientes de la matriz que se encuentran debajo de sonde se situan los dos vertices izquierdos de arriba (a) y abajo (b) del "cuadradito de givens" graficamente: - - - - (* indica el cuadradito de givens) - * - * (notar que el CdG siempre va en la diag) - - - - (y siempre es un cuadrado) - * - * givens sive mucho mas cuando es esparza se puede paralelizar! importante saber que estos metodos pueden usarse para llevar a la matriz a forma de hessemberg para luego usar el metodo QR por ejemplo SVD mot toda mat (rectangular o cuadrada) tiene SVD reduce problemas de data-mining y otras areas en dimension (pues se usan solamente componentes princip) condensa informacion reduce cualquier transformacion lineal (de espacio finito) a rotaciones-reflecciones estiramientos en los ejes y rotaciones-reflecciones sirve para cuadrados minimos calcular la pseudoinversa: M^+ = V * S^+ * U^t S^+ se calcula invirtiendo cada valor sing y trasponiendo obviamente para sistemas de ecuaciones UST^t U son autovec de A*A^t T son autovec de A^t*A S son autoval de cualquiera de las dos (valores sing de A) es relativamente caro pues deben calcularse autovalores y autovectores, pero hay metodos otimizados: se busca una forma de hessemberg (bidiagonal en este caso por ser simetrica) de A*A^t y A^t*A y se usa QR o algo asi... esta bueno porque puede iterarse hasta el epsilon de la maquina con lo cual se tiene precision optima Algoritmos iterativos para sistemas lineales Motivacion en matrices esparzas van a los pedos y te ahorras mucho espacio suele ser lineal en lugar de cuad si se usara LU nadie te garantiza que la L y la U sean esparzas en general, si la matriz es densa se usa LU, pues estos metodos no ganan mucho tiempo ?? se parte de un vector inicial y se va mejorando hasta obtener una buena aprox de una sol A = (D-L-U) jacobi despeja en cada iteracion usando el vector viejo se tiene que mantener siempre el vector de la iteracion pasada x' = D^(-1) * (L+U) * x + D^(-1) * b converge con diagonal dominante gauss siedel ? suele converger mas rapido despeja en cada iteracion usando los res nuevos puede sobreescribir la solucion en cada it converge con sim def pos converge con diag dom x' = (D-L)^(-1) * U * x + (D-L)^(-1) * b metodos generales x' = T * x + c converge si ro(T)<1 ( ro(T) es el radio espectral de T que es el modulo del autovalor de mayor modulo, puede ser acotado por ||T|| para cualquier norma inducida) se demuestra usando que si ro(T)<1 entonces (Id - T)^(-1) = Id + T + T^2 + ... gradiente conjugado (GC) sirve unicamente para matrices simetricas def pos tambien se usa cuando es esparza, si no se usa cholesky se basa en notar que resolver Ax=b es equivalente a encontrar el minimo de la forma cuadratica 1/2 * x^t * A * x - b^t * x + c para esto se usa steep descent para acelerar la convergencia se usan direcciones A conjugadas, pues son li y garantizan que en cada iteracion uno se mueve justo lo correcto en esa direccion, luego, en n iteraciones, yasta Algoritmos para autovalores y autovectores Motivacion aparecen en todos lados as fuck SVD - data mining - componentes principales diagonalizacion y forma de jordan (para exponenciar matrices para resolver eq dif por ejemplo) ?? metodo de la potencia se multiplica a un vector inicial bocha de veces por la matriz y puede normalizarselo en cada iteracion para que el modulo no diverja converge si la matriz tiene un autovalor simple de modulo mayor a los demas el vector inicial tiene una componente no nula con respecto al autovector asociado a dicho autovalor devuelve el autovalor de mayor modulo y su autovector asociado puede complementarse con la deflacion A - lambda * v^t * v se obtiene una matriz sin ese autovalor y que mantiene el resto de autovalores y autovectores en casos reales suele ser util porque es muy dificil que una matriz tenga un autovalor que no sea simple por ejemplo en componentes principales ya que uno busca los k vectores asociados a los k autovalores de mayor modulo metodo de la potencia inversa en lugar de usar A se usa (A - guess * I)^(-1) es lo mismo pero en lugar de devolver el autovalor de modulo mas grande, devuelve el de modulo mas parecido a guess metodo QR se saca QR y se hace RQ, luego se saca QR ... hasta que los numeros debajo de la diag se parezcan a cero funciona muucho mejor, pero es mas caro mas estable funciona mas piola empezando de una matriz relativamente esparza, por ejemplo de hessemberg, o banda si se puede. da todos los autovalores, y autovectores correspondientes puede optimizarse para no hacer las multiplicaciones explicitamente Cuadrados minimos lineales Motivacion fittear data puede tener outliers (dentro de fitear data se pueden nombrar muuchos casos distintos, saber si cierta data se corresponde con un modelo....) normas posibles a usar: infinito (min-max) da mucha importancia a los outliers 1 tiene problemas para analizarse pues el modulo no es una funcion suave 2 es una funcion suave es el estimador de maxima verosimilitud de distribucion normal maneras de resolver ecuaciones normales esta bueno porque queda una matriz semidefinida positiva con lo cual puede usarse cholesky o GC en caso de ser def pos incluso puede buscarse un precondicionador (precondicionamiento) para bajar el nomero de condicion esta malo porque el numero de condicion del sistema se eleva al cuadrado QR es bastante facil de implementar y no altera el numero de condicion pues usa transformacion ortogonal SVD es mas caro si bien puede no computarse la U explicitamente. es mas estable que QR cuando se trata de matriz con rango incompleto puede facilmente encontrarse la solucion menor norma en caso de rang inc Interpolacion polinomica Motivaciones tablas, si bien no se usan mas es posible que un programa lo guarde en un arreglo pues puede ser que computar la funcion sea caro, e interpolar barato evaluar funciones de las cuales se tienen pocos puntos ejemplo dibujar y evaluar funciones empiricas (densidad sobre temperatura de cierto materia...) sampling dibujar y evaluar funciones empiricas (densidad sobre temperatura de cierto materia...) splines: procesamiento de imagenes se usa para interpolar curvas suaves lagrange computacionalmente malo diferencias divididas computacionalmente muy piola metodo de naville maso siempre el mismo polinomio (es unico) con distintas formas splines: spline es igual a f en: los puntos las derivadas en los extremos (SI ES SUJETO) splines son iguales en: los puntos las derivadas primeras en los puntos las derivadas segundas en los puntos splines son polinomios de grado <= 3 en los extremos puede tener derivada segunda igual a cero SI ES NATURAL Integracion Motivaciones funciones dificiles de integrar analiticamente funciones que no se pueden integrar funciones que son una caja negra no se usa interpolacion de grado alto porque tiene mucha oscilaciones se usa de grado bajo (metodos compuestos) porque no importa la suavidad de las curvas metodos de newton-??? (abiertos y cerrados) casos particulares con puntos equidistantes (cerrados): metodo de trapecios regla de simpson esos mismos pero compuestos trapecio simple punto medio; error = h^3 / 12 8 f''(mu) trapecio compuesto paja, blah blah... esos mismos pero adaptativos, se va separando a lo divide and conquer, y se compara el error, una vez que el error comienza a converger (con cierto criterio) se para