unidad 1: fuentes y propagación de errores€¦ · unidad 1: fuentes y propagación de errores...

Unidad 1: Fuentes y propagación de erroresTemas Objetivos específicos Estrategias metodológicas

1.1 Qué es el Análisis Numérico.Fuentes de errores.Errores de redondeo ydiscretización.Propagación de errores.

(1) Conceptos de algoritmo y método numérico.

(2) Identificar los tipos de errores(3) Definir herramientas para medir los tipos de erro-

res: errores absolutos y relativos;decimales correc-tos y cifras significativas, los símbolos o pequeña yO grande.

(4) Estudiar la propagación de los errores en las op-eraciones elementales (suma, resta, producto, co-ciente), y la fórmula general de propagación deerrores.

(a) Hacer una breve descripción de los pasos a seguirpara la resolución de un problema de análisisnumérico.

(b) Introducción de ejemplos clásicos y fundamentalesdel análisis numérico.

(c) Establecer diferencia entre un problema numéricode un problema matemático.

(d) Implementación de algoritmos en seudo-códigospara la creación de programas de computadores.

1.2 Sistemas numéricos.Aritmética del computador.

(1) Sistemas de posición en cualquier base.(2) Sistemas de punto flotante y operaciones con punto

flotante.(3) Aritmética del computador.

(a) Reconocer el sistema de punto flotante o númerosde máquina.

(b) Entender y trabajar con números de punto flotante.

1.3 Estabilidad y condición. (1) Reconocer una problema mal condicionado(2) Concepto de estabilidad numérica(3) Reconocer y analizar los métodos numéricamente

inestables

(a) Establecer diferencias entre problemas estables conmétodos inestables.

(b) Replantear los métodos numéricamente inestablespara obtener métodos numéricamente estables

1

Unidad 1: Fuentes y propagación de errores

Objetivos de la Unidad:

¨ Conocer las principales herramientas utilizadas en el análisis numérico.

Estrategias de evaluación:

¨ Resolver una guía de problemas teórico-prácticos:Consiste de una guía de problemas con una parte de ejercicios teóricos sobre la unidad y otra partede problemas de programación para resolver con el computador.

¨ La parte teórica se evalúa en un examen escrito general y representa el 60 % de la nota de la unidad.¨ La parte práctica se evalúa mediante un examen individual frente al computador y al profesor y valdrá el resto 40 % de la nota de la unidad.¨ La nota de la unidadvaldrá un15 % de la nota total.

Recursos:

¨ Las clases son dictada con ayuda de las notas del curso análisis numérico.¨ Videobeam¨ Pizarrón.¨ Marcadores de color.

Cronología:

Las actividades de esta unidad se realizará en 1 semana y media: 3 clases teóricas o (4 1/2 horas) y 2 prácticas (4 horas).

2

Unidad 2: Solución de ecuaciones no lineales de una variableTemas Objetivos específicos Estrategias metodológicas

2.1 El método de la bisección.El método de la secante. Elmétodo de Newton.

(1) Fórmula de recurrencia. Sucesión de iterados.Convergencia.

(2) Orden de convergencia: lineal, superlineal,cuadrática, cúbica etc.

(3) Comparación entre el método de Newton con elmétodo de la secante

(a) Problema general:f(x) = 0 conf deRn enRm.(b) Casos particulares:n = m = 1 y polinomios de gradon.(c) Obtención de un método numérico gráficamente.(d) Motivación del problema mediante la construcción de un método

numérico par calcular la raíz positiva de un número real.

2.2 Teoría general para méto-dos iterativos.

(1) Función y sucesión de iteración.(2) Definición de punto fijo. Existencia y unicidad

de punto fijo.(3) Convergencia de un proceso iterativo.(4) Métodos iterativos de orden superior. Ejemplos.

(a) Ejemplos de funciones de iteración.(b) Condiciones necesarias y suficientes para la convergencia de una

sucesión de iterados al punto fijo.(c) Graficación de la convergencia en escalera y oscilante.(d) Caracterización de los métodos de orden superior.(e) Demostración de la convergencia de segundo orden del método de

Newton usando la teoría de métodos iterativos.

2.3 Técnicas de aceleración.Análisis del error.

(1) Estimación del orden de convergencia.(2) Aceleración de la convergencia: Método de ace-

leración de Aitken o método de extrapolación deAityken o método∆2-Aitken.

(3) Método de Aitken Modificado o Método deSteffensen.

(a) Mejora significativa de los métodos iterativos lineales.(b) Convergencia más rápida en el sentido de que

lımx→∞

x′n − α

xn − α= 0

2.4 Criterios de parada. (1) Criterio 1|f(xn)| ≤ ε(2) Criterio 2|xn+1 − xn| ≤ ε

(3) Criterio 3|xn+1 − xn| ≤ 1− λ

λε

(a) ¿Cuando parar un proceso iterativo específico?(b) El criterio 1 puede resultar inconveniente.(c) El criterio 2 resulta muy apropiado para Newton.(d) El criterio 3 es conveniente para los métodos lineales.

3

Unidad 2: Solución de ecuaciones no lineales de una variableTemas Objetivos específicos Estrategias metodológicas

2.5 Raíces simples y múltiples.(1) Franja e intervalo de incertidum-bre.

(2) Método de Newton para raícesmúltiples.

(3) Métodos generales.

(a) La franja de incertidumbre da la región de incertidumbre en la evaluacióndef(x) debido a errores de redondeo y a la aritmética finita.

(b) En la discusión del método de Newton y de la secante supusimos quef ′(x) 6= 0, es decir queα es raíz simple. Sif ′(x) = 0 los métodos pierdensu orden de convergencia.

(c) Método de Newton para raíces múltiples.(d) Si no se conoce a priori la multiplicidadp se puede aplicar los métodos

anteriores a la funciónK(x) = f(x)f ′(x) que tiene aα como raíz simple.

2.6 Cálculos de raíces de poli-nomios. Método de Muller.

(1) Regla de Horner. Deflación.(2) Método de Newton-Raphson apli-

cado a polinomios.(3) Estrategia de Wilkinson.(4) Ecuaciones algebraicas mal

condicionadas.(5) Método de Muller.

(a) El esquema de horner reduce considerablemente el número de multipli-caciones necesarias para la evaluación de un polinomio. También permiteevaluar la derivada de manera eficiente y como consecuencia el método deNewton aplicado a los polinomios es muy adecuado.

(b) Por deflaciones sucesivas se pueden obtener los ceros de un polinomio ma-nipulando polinomios de orden inferior.

(c) Las raíces de los polinomios de determinan en orden decreciente de mag-nitud.

(d) Toda raíz obtenida usando Newton sobre un polinomio reducido por de-flación debería ser inmediatamente refinada aplicando Newton nuevamenteal polinomio original pero usando la raíz calculada como aproximación ini-cial.

(e) El método de Muller generaliza el método de la secante y si bien se aplicaa funciones en general, vamos a desarrollarlo para polinomios.

(f) La convergencia del método de Muller esp ≈ 1,84

4

Unidad 2: Solución de ecuaciones no lineales de una variable


¨ Reconocer, diferenciar y comprender los principales métodos numéricos para la resolución de una ecuación no lineal; así como también su aplicación alcaso particular de los polinomios.

¨ Estudiar la teoría de punto fijo y su aplicación en los métodos iterativos en general.




Recursos:


Cronología: Las actividades de esta unidad se realizará en 4 semanas: 8 clases teóricas (12 horas) y 3 prácticas (6 horas).

5

Unidad 3: Solución de sistemas de ecuaciones linealesTemas Objetivos específicos Estrategias metodológicas

3.1 Métodos directos. (1) Problema general.(2) Sistemas Triangulares.

(a) Un método directo permite obtener la solución del sistema en un númerofinito de pasos.

(b) El estudio de un método directo lleva a examinar el costo del método, ex-presado en el número de operaciones elementales y la propagación de loserrores de redondeo y estabilidad del método.

(c) Resolver un sistema triangular superior (o inferior) involucran2 opera-ciones.

3.2 Método de eliminacióngaussiana.

(1) Pivotes y multiplicadores.(2) Estrategia de pivoteo (parcial y to-

tal).

(a) Operaciones elementales. Sistemas escalonados.(b) Modificación de la matriz de coeficientes a la forma triangular superior.(c) El método de eliminación gaussiana involucraO(2n2/3) operaciones(d) La estrategia del pivoteo asegura la culminación del método de eliminación

gaussiana de una manera estable.

3.3 Descomposición LU.Factorización de Cholesky.Matrices en banda.

(1) Teorema de existencia y unicidadde la descomposiciónLU

(2) Variante de la descomposiciónLUutilizando pivoteos parcial y total.

(3) Descomposición de Cholesky con ysin raíces cuadradas.

(4) Matrices tridiagonales.

(a) Son útiles cuando los segundos miembros de varios sistemas de ecuacionesno están disponible de una sola vez, sino que éstos pueden estar en funciónde la matrizA en una matriz triangular inferior. invertible y otra superior

(b) El pivoteo parcial (total) nos lleva a la descomposiciónA′ = LU dondeA′

es la permutación de las filas (y columnas) de la matrizA en el pivoteo.(c) El método de Cholesky requiere sólon(n + 1)/2 lugares de memoria, en

vez de losn2 lugares usuales y el número de operaciones es den3/3, lamitad de las requeridas en la descomposiciónLU .

(d) Resaltar la forma simplificada de la descomposiciónLU cuando la matrizes tridiagonal que asegura la estabilidad numérica del método y un ahorrosignificativo de operaciones y espacio de memoria

6

Unidad 3: Solución de sistemas de ecuaciones linealesTemas Objetivos específicos Estrategias metodológicas

3.4 Norma vectoriales y matri-ciales. Análisis del error.Número de condición.

(1) Definición de norma vectorial.Equivalencia de las normas enespacio de dimensión finita.

(2) Definición de norma matricial. Nor-mas matriciales inducidas por unanorma vectorial.

(3) Estimación del error. Vector residu-al.

(4) Método de refinamiento iterativo.(5) Número de condición. Sistema mal

condicionado.

(a) Definición de norma, propiedades y ejemplos de normas vectoriales y ma-triciales.

(b) La normap y las esferas unitarias para las normas más utilizadas. Normasequivalentes. Convergencia de una sucesión en

(c) Interpretación geométrica de la norma matricial subordinada(d) Cálculos de las normas matriciales inducidas:

‖ · ‖1, ‖ · ‖∞ y ‖ · ‖2.(e) Mediante un ejemplo se demuestra que una vector residual pequeño no

implica una buena aproximación.(f) El número de condición de la matriz de coeficientes muestra que tan sensi-

ble es el sistema a perturbaciones en los datos iniciales.

3.5 Métodos Indirectos (itera-tivos): método de Jacobi,Gauss-Seidel y SOR (sobrerelajación sucesiva)

(1) Métodos de Jacobi y Gauss-Seidely algoritmos.

(2) Convergencia de los métodositerativos estacionarios. Matriz deiteración.

(3) Estimación del error de losmétodos iterativos estacionarios.Aceleración de Aitken para dichosmétodos.

(4) Aceleración de los métodos itera-tivos estacionarios: Método de re-lajación: subrelajaciónω < 1 ysobrerelajaciónω > 1

(a) Los métodos indirectos son técnicas iterativas más rápidas para sistemalineales muy grandes pero con menor requerimiento de memoria.

(b) Obtención de las matrices de iteración de Jacobi y Gauss-Seidel.(c) Establecer condiciones necesaria y suficientes para la convergencia de los

métodos iterativos para toda aproximación inicial.(d) Determinar lo práctico de la condición suficiente‖B‖ < 1 para la conver-

gencia de los métodos iterativos.(e) Resultados comparativos de los métodos: Teorema de Stein-Rosenberg.(f) Condiciones necesarias para la convergencia de los métodos SOR(1 <

ω < 2).

7

Unidad 3: Solución de sistemas de ecuaciones lineales


¨ Estudiar los principales métodos numéricos para la resolución de un sistema lineal de ecuaciones: convergencia, estabilidad, aplicación etc.¨ Ampliar algunos conocimientos de algebra lineal y su aplicación en los métodos iterativos.




Recursos:


Cronología:

Las actividades de esta unidad se realizará en 2 semanas y media: 5 clases teóricas (7 1/2 horas) y 2 prácticas (4 horas).

8

Unidad 4: Teoría de interpolaciónTemas Objetivos específicos Estrategias metodológicas

4.1 Interpolación polinomial (1) Aproximación e Interpolación.(2) Dada una norma y seminorma en

C[a, b] buscar un polinomio de gra-do especificado que minimice el er-ror de aproximación. Si tal poli-nomio existe establecer la unicidady la manera de calcularlo.

(a) Establecer la diferencia entre norma y seminorma.(b) Tomar la aproximación por polinomios de Taylor como ejemplo.

4.2 Forma de Lagrange delpolinomio de interpolación.

(1) Teorema de existencia y unicidadpara el polinomio de interpolación.

(2) Teorema del error de interpolación.

(a) Dar tres demostraciones distintas del teorema de aproximación tal y co-mo aparecen en las notas de clases. Así mismo, resaltar la importancia delcálculo del error en la interpolación.

(b) Aplicar los teoremas a varios problemas.(c) Analizar la propagación de los errores de redondeo en la interpolación

lineal y dejar al estudiante analizar la propagación en la interpolacióncuadrática

4.3 Diferencias divididas. For-ma de Newton del poli-nomio de interpolación.

(1) Diferencias divididas de ordenn:Definición, propiedades y tablas.

(2) Otras propiedades y extensiones delas diferencias divididas

(a) Entender bien los algoritmos para evaluar las diferencias divididas y paraevaluar un polinomio de ordenn.

(b) Considerar la fórmula de Hermite-Genocchi para extender el concepto dediferencias divididas con nodos repetidos.

(c) Derivada de la diferencia dividida.

9

Unidad 4: Teoría de interpolaciónTemas Objetivos específicos Estrategias metodológicas

4.4 Diferencias divididas conpuntos igualmente espacia-do. y polinomio de interpo-lación.

(1) Operadores de diferencias progre-sivas y regresivas de ordenn ypropiedades.

(2) Formulas de diferencia progresivas(o regresivas) de Newton para elpolinomio de interpolación.

(3) Diferencias centrales. Fórmula deEverett para el polinomio de inter-polación.

(a) Denotar que la forma de Newton para el polinomio de interpolación sereduce considerablemente al usar cualquiera de las diferencias (progresivas,regresivas o centrales).

(b) Simplificación de los operadores de diferencias cuando se utilizan nodosigualmente espaciados.

4.5 La convergencia de los poli-nomios de interpolación.

(1) Interpolación equidistante.(2) Fenómeno de Runge.(3) Interpolación y nodos de Cheby-

shev.

(a) Mostrar resultados sobre la convergencia uniformemente de los polinomiosde interpolación.

(b) Destacar lo inconveniente de la elección de polinomios de interpolación degrado muy alto.

(c) Deducción de la fórmula de recurrencia para obtener los polinomios deChebyshev.

(d) Propiedades de los polinomios de Chebyshev.(e) Error de interpolación eligiendo los nodos de Chebyshev.

4.6 Interpolación con funcionessplines. Splines cúbicas.

(1) Definición de spline: Interpolacióncon spline.

(2) Spline lineales y cúbicas.(3) Spline natural,con condiciones en la

frontera y condiciones de fronteraperiódica.

(a) Dar ejemplos de las spline de distintos ordenes: constante, lineal y cubica.(b) Resaltar el hecho que las spline cúbica son muy convenientes para trazar

datos debido a su regularidad.(c) Explicar que las distintas spline son solución de problemas de mini-

mización.

10

Unidad 4: Teoría de interpolación


¨ Construir el polinomio de interpolación en las distintas formas.¨ Conocer las funciones spline (a trozos) como funciones de aproximación.




Recursos:


Cronología:

Las actividades de esta unidad se realizará en 4 semanas: 8 clases teóricas (12 horas) y 2 prácticas (4 horas).

11

Unidad 5: Integración NuméricaTemas Objetivos específicos Estrategias metodológicas

5.1 Cuadratura Numérica. (1) El problema de cuadratura numérica.(2) Forma general de las integrales

numéricas.Fórmula de cuadratura numérica

(a) Destacar en la fórmula de cuadratura los nodos y los pesos correspondi-entes.

(b) Resaltar el hecho que la mayoría de las fórmulas de integración numéricase basan en definirfn(x) mediante interpolación polinomial a trozos.

(c) Recordar el teorema de valor medio generalizado para integrales.

5.2 Métodos de cuadraturas(1) La regla del rectángulo. Estimación delerror del método.

(2) La regla compuesta del rectángulo.Fórmula del error.

(3) Regla (compuesta) del trapecio. Cálcu-lo del error.

(4) Métodos de Simpson y Simpson3/8.

(a) La regla del rectángulo se obtiene al aproximarf(x) por el polinomio con-stantef(a+b

2 ).(b) Mediante las propiedades de integrales se puede calcular el error del méto-

do.(c) Si [a, b] es muy grande, la regla del rectángulo se aplica sobre subintervalos

pequeños, para luego tomar la integral como suma de integrales.(d) Se entiende el análisis hecho a la regla del rectángulo a los caso de los

polinomios de aproximación son de grado1, 2, y 3.

5.3 Polinomios Ortogo-nales.

(1) Propiedades de los polinomios ortogo-nales.

(2) Polinomios de Legendre.(3) Polinomios de Chebyshev.(4) Polinomios de Laguerre.(5) Raíces de polinomios ortogonales.

Aplicaciones.

(a) Es necesario introducir el concepto de polinomios ortogonales: productointerno, propiedades, teorema de gram-Schmidt, etc.

(b) Formula de recurrencia para los polinomios ortogonales.(c) Desarrollar las distintas familias polinomios ortogonales para distintos pro-

ductos escalares; diferencia de la función peso.

5.4 Cuadratura gaussiana. (1) Fórmula de cuadratura gaussiana.(2) Error de la cuadratura gaussiana.

(a) Explotar la propiedad de los polinomios ortogonales que dice que todas susraíces son reales y se encuentran en el propio intervalo(a, b).

(b) Ajustar los coeficientes de la fórmula de cuadratura para hacer exacta lafórmula para todo polinomio de mayor grado posible.

12

Unidad 5: Integración Numérica


¨ Construir las principales fórmulas de cuadraturas junto a su análisis del error.




Recursos:


Cronología:

Las actividades de esta unidad se realizará en 2 semanas: 4 clases teóricas (6 horas) y 2 prácticas (4 horas).

13

unidad 1: fuentes y propagación de errores€¦ · unidad 1: fuentes y propagación de errores...

Documents