martes, 5 de marzo de 2013

Metodos Iterarios



Métodos Iterarios
Un método iterativo trata de resolver un problema (como una ecuación o un sistema de ecuaciones) mediante aproximaciones sucesivas a la solución, empezando desde una estimación inicial.
Esta aproximación contrasta con los métodos directos, que tratan de resolver el problema de una sola vez (como resolver un sistema de ecuaciones Ax=bencontrando la inversa de la matriz A).
Los métodos iterativos son útiles para resolver problemas que involucran un número grande de variables (a veces del orden de millones), donde los métodos directos tendrían un coste prohibitivo incluso con la potencia del mejor computador disponible

Método de Regula Falsi
El cálculo numérico, el método de la regula falsi (regla falsa) o falsa posición es un método iterativo de resolución numérica de ecuaciones lineales. El método combina el método de bisección y el método de la secante.
Este método sirve para encontrar la raíz o solución real de una ecuación. Al decir que encuentra un resultado hay que tomar en cuenta que no todas las ecuaciones tienen un solo resultado, y que no todas tienen resultado, por lo que hay que tener una idea de la forma de la curva de la ecuación antes de aplicar el método para que sea efectivo.
Procedimiento
Debemos considerar si la raíz de una ecuación está localizada más cerca de los extremos del intervalo.
El Método de Bisección, conocido también como de corte binario, de partición en dos intervalos iguales o método de Bolzano, es un método de búsqueda incremental donde el intervalo se divide siempre en dos. Si la función cambia de signo sobre un intervalo, se evalúa el valor de la función en el punto medio. La posición de la raíz se determina situándola en el punto medio del su intervalo dentro del cual ocurre un cambio de signo. El proceso se repite hasta obtener una mejor aproximación.
Se busca una solución de la ecuación f(x) = 0, una raíz de f. Como en el método de bisección, se parte de un intervalo inicial [a0,b0] con f(a0) y f(b0) de signos opuestos, lo que garantiza que en su interior hay al menos una raíz (véase el teorema de Bolzano). El algoritmo va obteniendo sucesivamente en cada paso un intervalo más pequeño [akbk] que sigue incluyendo una raíz de la función f.
A partir de un intervalo [akbk] se calcula un punto interior ck:

Software de cómputo numérico


Netlib
Netlib (NET LI Brary) es una colección grande de software, documentos, bases de datos gratis que son de interes para las comunidades científicas y de métodos numéricos. El depósito es mantenido por los Laboratorios Bell de AT&T, la Universidad de Tennessee y el Laboratorio Nacional Oak Ridge, y replicado en varios sitios alrededor del mundo.
Netlib contiene software de alta calidad que ha sido probado en forma intensiva, pero todo el software libre no tiene garantía y poco (si existe) soporte. Para poder usar el software, primero se tiene que descargar en su computadora y entonces compilarlo.
Paquetes de software comercial para cómputo numérico general:
NAG
El Grupo de Algoritmos numéricos (Numerical Algorithms Group) (NAG) ha desarrollado una biblioteca de Fortran conteniendo alrededor de 1000 subrutinas accesibles al usuario para resolver problemas generales de matemáticas aplicadas, incluyendo: ecuaciones diferenciales ordinarias y parciales, transformada rápida de Fourier, cuadratura, álgebra lineal, ecuaciones no lineales, ecuaciones integrales, y más.
IMSL
La biblioteca numérica de Fortran IMSL hecha por Visual Numerics, Inc. cubre muchas de las áreas contenidas en la biblioteca NAG. También tiene soporte para analizar y presentar datos estadísticos en aplicaciones científicas y de negocios.
NUMERICAL RECIPES
Los libros de Numerical Recipes in C/Fortran son muy populares entre los ingenieros porque pueden ser usados como libro de cocina donde se puede encontrar una “receta (recipe)” para resolver algún problema a mano. Sin embargo, el software correspondiente de Numerical Recipes no es comparable en alcance o calidad al dado por NAG o IMSL. Es un software muy usado en universidades, centros de investigación y por ingenieros. En los últimos años ha incluido muchas más capacidades, como la de programar directamente procesadores digitales de señal, crear código VHDL y otras.
MATLAB
Es un programa de cálculo numérico, orientado a matrices y vectores. Por tanto desde el principio hay que pensar que todo lo que se pretenda hacer con él, será mucho más rápido y efectivo si se piensa en términos de matrices y vectores.
GNU OCTAVE
Es un programa libre para realizar cálculos numéricos. Como indica su nombre es parte de proyecto GNU. MATLAB es considerado su equivalente comercial. Entre varias características que comparten se puede destacar que ambos ofrecen un intérprete permitiendo ejecutar órdenes en modo interactivo. Nótese que Octave no es un sistema de álgebra computacional como podría ser GNU Máxima, sino que usa un lenguaje que está orientado al análisis numérico.

Tipos de Errores


Errores Inherentes a los Métodos Numéricos.

Un error es una incertidumbre en el resultado de una medida. Se define como la diferencia entre el valor real y una aproximación a este valor.

Error de redondeo
Se originan al realizar los cálculos que todo método numérico o analítico requieren y son debidos a la imposibilidad de tomar todas las cifras que resultan de operaciones aritméticas como los productos y los cocientes, teniendo que retener en cada operación el número de cifras que permita el instrumento de cálculo que se esté utilizando.

Error por Truncamiento
Existen muchos procesos que requieren la ejecución de un número infinito de instrucciones para hallar la solución exacta de un determinado problema. Puesto que es totalmente imposible realizar infinitas instrucciones, el proceso debe truncarse. En consecuencia, no se halla la solución exacta que se pretendía encontrar, sino una aproximación a la misma.

Error Numérico Total
Se entiende como la suma de los errores de redondeo y truncamiento introducidos en el cálculo.

Errores Humanos
Son los errores por negligencia o equivocación. Actualmente las computadoras son muy exactas y el error es atribuido a los hombres. Los errores humanos son inevitables pero se pueden minimizar.

Error inherente
En ocasiones, los datos que se inician los cálculos contienen un cierto error debido a que se han obtenido mediante la medida experimental de una determinada magnitud física.

Error Absoluto
El error absoluto no es negativo. Es una colección (suma) de errores. Debido a que si un número y su parte fraccionario conformada por un conjunto de dígitos infinita requieren ser representada numéricamente es su forma aproximada es donde se presenta este tipo de error.


Error relativo
Es el error absoluto dividido entre un número positivo adecuado. Generalmente, el divisor es una de tres elecciones: la magnitud del valor exacto, la magnitud del valor calculado (o redondeado) o el promedio de estas dos cantidades.

Conceptos Basicos


Cifras significativas: Cuando se emplea un número en un cálculo, debe haber seguridad de que pueda usarse con confianza. El concepto de cifras significativas tiene dos implicaciones importantes en el estudio de los métodos numéricos.
1.- Los métodos numéricos obtienen resultados aproximados. Por lo tanto, se debe desarrollar criterios para especificar que tan precisos son los resultados obtenidos.
2.- Aunque ciertos números representan número específicos, no se pueden expresar exactamente con un número finito de cifras.
Exactitud: Se refiere a que tan cercano está el valor calculado o medido del valor verdadero.
Precisión: Se refiere a qué tan cercano está un valor individual medido o calculado respecto a los otros.
Inexactitud: (conocida como sesgo) se define como un alejamiento sistemático de la verdad a calcular.
Imprecisión: También se le conoce como incertidumbre. Se refiere al grado de alejamiento entre sí, a las diversas aproximaciones a un valor verdadero.

Método de Bisección


Método de la Bisección
El método de la bisección o corte binario es un método de búsqueda incremental que divide el intervalo siempre en 2. Si la función cambia de signo sobre un intervalo, se evalúa el valor de la función en el punto medio. La posición de la raíz se determina situándola en el punto medio del subintervalo donde exista cambio de signo. El proceso se repite hasta mejorar la aproximación.
Algoritmo
Paso 1
Elegir los valores iniciales Xa y Xb, de tal forma de que la función cambie de signo:
f(Xa)f(Xb) < 0
Paso 2
La primera aproximación a la raíz se determina con la fórmula del punto medio de esta forma:
Descripción: http://www.monografias.com/trabajos43/metodo-biseccion/Image4626.gif
Paso 3
Realizar las siguientes evaluaciones para determinar el intervalo de la raíz:
a.    Si f(Xa)f(Xb) < 0, entonces la solución o raíz está entre Xa y Xpm, y Xb pasa a ser el punto medio (Xpm).
b.    Si f(Xa)f(Xb) > 0, entonces la solución o raíz está fuera del intervalo entre Xa y el punto medio, y Xa pasa a ser el punto medio (Xpm).
Paso 4
Si f(Xa)f(Xb) = 0 ó Error = | Xpm – Xpm – 1 | < Tolerancia
Donde Xpm es el punto medio de la iteración actual y Xpm – 1 es el punto medio de la iteración anterior.
Al cumplirse la condición del Paso 4, la raíz o solución es el último punto medio que se obtuvo.
Para el error relativo porcentual se tiene la siguiente fórmula:
Descripción: http://www.monografias.com/trabajos43/metodo-biseccion/Image4627.gif

Este es uno de los métodos más sencillos y de fácil intuición para resolver ecuaciones en una variable. Se basa en el Teorema de los Valores Intermedios (TVI), el cual establece que toda función continua  en un intervalo cerrado [a, b] toma todos los valores que se hallan entre f(a) y f(b). Esto es, que todo valor entre f(a) y f(b) es la imagen de al menos un valor en el intervalo [a, b]. En caso de que f(a) y f(b) tengan signos opuestos f(a)*f(b) <0, el valor cero sería un valor intermedio entre f(b) y f(b), por lo que con certeza existe un  en  que cumple f(p) = 0 . De esta forma, se asegura la existencia de al menos una solución de la ecuación f(x) =0.

Método de punto fijo


Método de la Bisección
El método de la bisección o corte binario es un método de búsqueda incremental que divide el intervalo siempre en 2. Si la función cambia de signo sobre un intervalo, se evalúa el valor de la función en el punto medio. La posición de la raíz se determina situándola en el punto medio del subintervalo donde exista cambio de signo. El proceso se repite hasta mejorar la aproximación.
Algoritmo
Paso 1
Elegir los valores iniciales Xa y Xb, de tal forma de que la función cambie de signo:
f(Xa)f(Xb) < 0
Paso 2
La primera aproximación a la raíz se determina con la fórmula del punto medio de esta forma:
Descripción: http://www.monografias.com/trabajos43/metodo-biseccion/Image4626.gif
Paso 3
Realizar las siguientes evaluaciones para determinar el intervalo de la raíz:
a.    Si f(Xa)f(Xb) < 0, entonces la solución o raíz está entre Xa y Xpm, y Xb pasa a ser el punto medio (Xpm).
b.    Si f(Xa)f(Xb) > 0, entonces la solución o raíz está fuera del intervalo entre Xa y el punto medio, y Xa pasa a ser el punto medio (Xpm).
Paso 4
Si f(Xa)f(Xb) = 0 ó Error = | Xpm – Xpm – 1 | < Tolerancia
Donde Xpm es el punto medio de la iteración actual y Xpm – 1 es el punto medio de la iteración anterior.
Al cumplirse la condición del Paso 4, la raíz o solución es el último punto medio que se obtuvo.
Para el error relativo porcentual se tiene la siguiente fórmula:
Descripción: http://www.monografias.com/trabajos43/metodo-biseccion/Image4627.gif

Este es uno de los métodos más sencillos y de fácil intuición para resolver ecuaciones en una variable. Se basa en el Teorema de los Valores Intermedios (TVI), el cual establece que toda función continua  en un intervalo cerrado [a, b] toma todos los valores que se hallan entre f(a) y f(b). Esto es, que todo valor entre f(a) y f(b) es la imagen de al menos un valor en el intervalo [a, b]. En caso de que f(a) y f(b) tengan signos opuestos f(a)*f(b) <0, el valor cero sería un valor intermedio entre f(b) y f(b), por lo que con certeza existe un  en  que cumple f(p) = 0 . De esta forma, se asegura la existencia de al menos una solución de la ecuación f(x) =0.

Importancia de los Métodos Numéricos



Los métodos numéricos son técnicas mediante las cuales es posible formular problemas matemáticos de tal forma que puedan resolverse usando operaciones aritméticas.
El análisis numérico trata de diseñar métodos para aproximar de una manera eficiente las soluciones de problemas expresados matemáticamente.
El objetivo principal es encontrar soluciones aproximadas a problemas complejos utilizando sólo las operaciones más simples de la aritmética.
Se requiere de una secuencia de operaciones algebraicas y lógicas que producen la aproximación al problema matemático.
Los métodos numéricos pueden ser aplicados para resolver procedimientos matemáticos en:  Cálculo de derivadas, Integrales, Ecuaciones diferenciales, Operaciones con matrices.
      

Método de Newton Raphson


Método de Newton-Raphson
Es uno de los métodos más usados en la ingeniería por llegar al resultad del problema planteado de forma más rápida. Se basa en trazar rectas tangentes que “toman la forma” de la función por medio de su primera derivada.
En análisis numérico, el método de Newton (conocido también como el método de Newton-Raphson o el método de Newton-Fourier) es un algoritmo eficiente para encontrar aproximaciones de los ceros o raíces de una función real. También puede ser usado para encontrar el máximo o mínimo de una función, encontrando los ceros de su primera derivada.
El método de Newton-Raphson es un método abierto, en el sentido de que su convergencia global no está garantizada. La única manera de alcanzar la convergencia es seleccionar un valor inicial lo suficientemente cercano a la raíz buscada. Así, se ha de comenzar la iteración con un valor razonablemente cercano al cero (denominado punto de arranque o valor supuesto). La relativa cercanía del punto inicial a la raíz depende mucho de la naturaleza de la propia función; si ésta presenta múltiples puntos de inflexión o pendientes grandes en el entorno de la raíz, entonces las probabilidades de que el algoritmo diverja aumentan, lo cual exige seleccionar un valor supuesto cercano a la raíz. Una vez se ha hecho esto, el método linealiza la función por la recta tangente en ese valor supuesto. La abscisa en el origen de dicha recta será, según el método, una mejor aproximación de la raíz que el valor anterior. Se realizarán sucesivas iteraciones hasta que el método haya convergido lo suficiente.
Sea f : [ab] -> R función derivable definida en el intervalo real [ab]. Empezamos con un valor inicial x0 y definimos para cada número natural n
Descripción: x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.
Donde f ' denota la derivada de f.
Nótese que el método descrito es de aplicación exclusiva para funciones de una sola variable con forma analítica o implícita cognoscible. Existen variantes del método aplicables a sistemas discretos que permiten estimar las raíces de la tendencia, así como algoritmos que extienden el método de Newton a sistemas multivariables, sistemas de ecuaciones, etc.

Metodo de la secante


Método de la secante
En análisis numérico el método de la secante es un método para encontrar los ceros de una función de forma iterativa.
Es una variación del método de Newton-Raphson donde en vez de calcular la derivada de la función en el punto de estudio, teniendo en mente la definición de derivada, se aproxima la pendiente a la recta que une la función evaluada en el punto de estudio y en el punto de la iteración anterior. Este método es de especial interés cuando el coste computacional de derivar la función de estudio y evaluarla es demasiado elevado, por lo que el método de Newton no resulta atractivo.
En otras palabras, el método de la secante es un algoritmo de la raíz de investigación que utiliza una serie de raíces de las líneas secantes para aproximar mejor la raíz de una función f. El método de la secante se puede considerar como una aproximación en diferencias finitas del método de Newton-Raphson. Sin embargo, este método fue desarrollado independientemente de este último.
El método se define por la relación de recurrencia:

Como se puede ver, este método necesitará dos aproximaciones iniciales de la raíz para poder inducir una pendiente inicial.
“Convergencia”
El orden de convergencia de este método, en un punto cercano a la solución, es Descripción:  \varphi donde

es el número áureo, por lo que se trata de una convergencia superlineal inferior a la del método de Newton-Raphson. En caso de que la aproximación inicial sea demasiado lejana o la raíz no sea simple, este método no asegura la convergencia y tiene un comportamiento similar al de Newton-Raphson.

Métodos para Sistemas de ecuaciones lineales



Metodo de Gaus
El método de Gauss resuelve un sistema de ecuaciones lineales de forma simultánea. El método consiste de dos fases. La primera fase se le conoce como “eliminación hacia adelante”, debido a que realiza una eliminación de coeficientes comenzando de arriba hacia abajo, hasta dejar una matriz de coeficientes del tipo triangular superior. La segunda se le conoce como “sustitución hacia atrás”, por que se parte de la última ecuación del sistema, para despejar la incógnita, la cual, ya se puede resolver debido a que en esa última ecuación únicamente se desconoce una incógnita, por el hecho de tener un sistema de ecuaciones de tipo matriz triangular superior.
 EJEMPLO:
Resolver el siguiente sistema de ecuaciones:
3x– 0.1x– 0.2x= 7.85 Ec.1
0.1x+ 7x-0.3x= -19.3 Ec.2
0.3x1 -0.2x2 + 10x3 = 71.4 Ec.3 
 ELIMINACION HACIA ADELANTE
Ecuación pivote = Ec.1
Elemento pivote = x(incógnita a eliminar de las ecuaciones restantes)
Se normaliza la ecuación 1 para restarla en Ec.2:
Para obtener la nueva Ec.2, se restan las ecuaciones
Ec.2 = Ec.2 – Ec.1’
0x+ 7.003333x-0.293334x= -19.561666 Ec.2
Se normaliza la ecuación 1 para restarla en Ec.3:

Métodos para Sistemas de ecuaciones no lineales


 Newton-Raphson Multivariable
El metodo de Newton-Raphson modificado el cual se describe acontinuacion consiste en aplicar el metodo de Newton-Raphson multivariable dos veces(para el caso de un sistema de necuaciones no lineales con n incógnitas, se aplicara n veces), una para cada variable. Cada vez que se hace esto, se considera las otras variables fijas.

Considerese de nuevo el sistema:
Tomando los valores iniciales x0,y0, se calcula a partir del metodo de Newton-Raphson univariable un nuevo valor x1 de la forma siguiente:
Ya teniendo f1(x0,y0) y df1/dx estos dos evaluados en x0,y0.
Hay que observar que se a obtenido x1 a partir de f1 y los valores mas recientes de X y Y; x0,y0.
Ahora emplearemos f2 y los valores mas recientes de X y Y; x1, y0 para calcular y1
De esta forma :
Donde df2/dy se evalúa en x1,y0. Se obtiene ahora x1 y y1. con estos valores se calcula x2, después y2, y así sucesivamente.
Este metodo converge a menudo si x0,y0 esta muy cerca de xnegada y ynegada, y requiere la evaluacion de solo 2n funciones por paso (cuatro para el caso de dos ecuaciones que se esta manejando). Hay que observar que se han empleado desplazamientos sucesivos, pero los desplazamientos simultaneos tambien son aplicables.
En la aplicación de este metodo se pudo tomar f2 para evaluar x1 y f1, a fin de evaluar y1, asi:

Derivacion Numerica



La derivación numérica es una técnica de análisis numérico para calcular una aproximación a la derivada de una función en un punto utilizando los valores y propiedades de la misma.

Por definición la derivada de una función f(x) es: 

Las aproximaciones numéricas que podamos hacer (para h > 0) serán:

La aproximación de la derivada por este método entrega resultados aceptables con un determinado error. Para minimizar los errores se estima que el promedio de ambas entrega la mejor aproximación numérica al problema dado:


La grafica siguiente presenta la diferencia entre las dos formas de obtener la derivada de una función  f en x= x0 ,
En la gráfica es evidente el error que existe al utilizar la expresión F(x0 + h) - F(x0)/h para evaluar la derivada o pendiente de f en x0.
una mejor alternativa para evaluar F'(x0) es la construccion de un polinomio de lagrange.

Con lo anterior aclarado se procede a la construcción del polinomio de Lagrage de primer orden y su término de error.:
donde
 es polinomio de primer orden definido por x0,x1.
El término  es un valor que está en función de x y se encuentra en el intervalo . Así, la función es ahora,

Integracion Numerica


En análisis numérico, la integración numérica constituye una amplia gama de algoritmos para calcular el valor numérico de una integral definida y, por extensión, el término se usa a veces para describir algoritmos numéricos para resolver ecuaciones diferenciales. El términocuadratura numérica (a menudo abreviado a cuadratura) es más o menos sinónimo de integración numérica, especialmente si se aplica a integrales de una dimensión a pesar de que para el caso de dos o más dimensiones (integral múltiple) también se utiliza. 
El problema básico considerado por la integración numérica es calcular una solución aproximada a la integral definida:

Este problema también puede ser enunciado como un problema de valor inicial para una ecuación diferencial ordinaria, como sigue:

Encontrar y(b) es equivalente a calcular la integral. Los métodos desarrollados para ecuaciones diferenciales ordinarias, como elmétodo de Runge-Kutta, pueden ser aplicados al problema reformulado. En este artículo se discuten métodos desarrollados específicamente para el problema formulado como una integral definida.

Métodos para integrales unidimensionales

Los métodos de integración numérica pueden ser descritos generalmente como combinación de evaluaciones del integrando para obtener una aproximación a la integral. Una parte importante del análisis de cualquier método de integración numérica es estudiar el comportamiento del error de aproximación como una función del número de evaluaciones del integrando. Un método que produce un pequeño error para un pequeño número de evaluaciones es normalmente considerado superior. Reduciendo el número de evaluaciones del integrando se reduce el número de operaciones aritméticas involucradas, y por tanto se reduce el error de redondeo total. También, cada evaluación cuesta tiempo, y el integrando puede ser arbitrariamente complicado.
De todos modos, un modo de integración por «fuerza bruta» puede hacerse siempre, de un modo muy simplista, evaluando el integrando con incrementos muy pequeños.

Polinomio de interpolacion de Lagrange


En análisis numérico, el polinomio de Lagrange, llamado así en honor a Joseph-Louis de Lagrange, es el polinomio que interpolaun conjunto de puntos dado en la forma de Lagrange. Fue descubierto por Edward Waring en 1779 y redescubierto más tarde por Leonhard Euler en 1783


Dado que existe un único polinomio interpolador para un determinado conjunto de puntos, resulta algo confuso llamar a este polinomio el polinomio interpolador de Lagrange. Un nombre más conciso es interpolación polinómica en la forma de Lagrange.

Existen en todas las ramas de la ciencia, en la Física, en la Matemática, en la Química, en la Astronomía, en Biología, etc.. situaciones en las que conociendo un conjunto de datos experimentales en un cierto intervalo de la variable independiente, esto es, conociendo una cierta cantidad de datos tabulados, se hace preciso encontrar una función que verifique todos esos datos y permita, por consiguiente, predecir la existencia de otros valores con la aproximación adecuada. El problema de la interpolación es de gran importancia en el análisis numérico. En este artículo vemos muy brevemente una manera elemental de interpolación y la obtención de la conocida Fórmula Interpoladora de Lagrange.

  • Interpolacion y Polinomio de Interpolacion de Lagrange
Se trata de encontrar un polinomio de grado n que pase por los puntos (x0f(x0)), (x1f(x1)), ... (xnf(xn)), se construye un cociente Ln,k(xk) con la propiedad de que
Ln,k(xi) = 0 cuando ¹ k y Ln,k(xk) = 1
Se requiere entonces que el numerador contenga
(x – x0) (x – x1)... (x – xk–1)(x – xk+1)... (x – xn)
El denominador debe coincidir con el numerador cuando x = xk.
  • N-ésimo polinomio interpolante de Lagrange