Algoritmo.
Un algoritmo es la secuencia de pasos lgicos necesarios para llevas a cabo una
tarea especfica, como la resolucin de un problema. Para realizar este objetivo,
un buen algoritmo debe contar con los siguientes atributos:
1. Cada paso debe ser determinado, es decir, no puede ser obra de la
casualidad. Los resultados finales no pueden depender de quien sigue el
algoritmo. En este sentido, un algoritmo es como una receta de cocina. Dos
cocineros que trabajan por su lado con una buena receta deberan preparar
platillos esencialmente idnticos.
2. El proceso debe ser siempre terminar despus de un nmero finito de
pasos. Un algoritmo no puede tener un final abierto.
3. El algoritmo debe ser lo suficientemente generalizado como para ocuparse
de cualquier contingencia.
La resolucin de un problema exige el diseo de un algoritmo que resuelva el
problema propuesto.
Los pasos para la resolucin de un problema son:
a) Diseo de algoritmo, que describe la secuencia ordenada de pasos que
conducen a la solucin de un problema dado. (Anlisis del problema y
desarrollo del algoritmo).
b) Expresar el algoritmo como un programa de lenguaje de programacin
adecuado. (Fase decodificacin.)
c) Ejecucin y validacin del programa por la computadora.
Para llegar a la realizacin de un programa es necesario el diseo previo de
algoritmo, de modo que sin algoritmo no puede existir un programa.
Los algoritmos son independientes tanto del lenguaje de programacin en que
se expresan como de la computadora que lo ejecuta.
Aproximaciones.
La mayor parte de las tcnicas tiene la caracterstica de poseer errores. Aunque la
perfeccin es una meta digna de alabarse, es difcil, si no imposible, alcanzarla.
Sin embargo, sus distribuciones aleatorias se agrupan muy prximas alrededor de
la prediccin.
En algunos conceptos bsicos de los Mtodos Numricos podemos encontrar los
siguientes: Cifra Significativa, Precisin, Exactitud, Incertidumbre Y Sesgo. Que
forman parte a las aproximaciones y predicciones numricas adecuadas.
Cifras significativas: Cuando se emplea un nmero en un clculo, debe haber
seguridad de que pueda usarse con confianza. El concepto de cifras significativas
tiene dos implicaciones importantes en el estudio de los mtodos numricos.
1.- Los mtodos numricos obtienen resultados aproximados. Por lo tanto, se
debe desarrollar criterios para especificar qu tan precisos son los resultados
obtenidos.
2.- Aunque ciertos nmeros representan nmero especficos, no se pueden
expresar exactamente con un nmero finito de cifras.
Por lo que podemos tener unos Algoritmos De Aproximacin.
Dado un problema completo, es probable que no sepamos resolverlo de manera
precisa y completa utilizando un algoritmo polimico en tiempo. Para este tipo de
problemas, los algoritmos que no conducen a una solucin ptima se llaman
algoritmos de aproximacin. Sin embargo, resulta parcialmente interesante que
estos garanticen una cota en el margen de imprecisin.
Exactitud y Precisin: La exactitud se refiere a que tan cercano est el valor
calculado o medido del valor verdadero. La precisin se refiere a qu tan cercano
est un valor individual medido o calculado respecto a los otros.
Tipos de errores:
porcentual,
Error
absoluto,
error
relativo,
error
Error absoluto:
Es la diferencia entre el valor exacto (un nmero determinado, por ejemplo) y
su valor calculado o redondeado:
Error absoluto = [exacto - calculado]
Debido a que la definicin se dio en trminos del valor absoluto, el error
absoluto no es negativo. As pues, una coleccin (suma) de errores siempre se
incrementan juntos, sin reducirse. Este es un hecho muy pesimista, dado que
el redondeo y otros errores rara vez estn en la misma direccin, es posible
que una suma ("algebraica") de errores sea cero, con aproximadamente la
mitad de los errores positiva y la otra mitad negativa. Pero tambin es
demasiado optimista esperar que errores con signo sumen cero a menudo. Un
enfoque realista es suponer que los errores, en especial el redondeo, estn
estadsticamente distribuidos.
Error relativo:
Es el error absoluto dividido entre un nmero 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. La mayor parte de las veces utilizaremos
Error relativo= [exacto - calculado]/[exacto]
El error relativo es una mejor medida del error que el error absoluto, en
especial cuando se utilizan sistemas numricos de punto flotante. Puesto que
los elementos de un sistema de punto flotante no estn distribuidos de manera
uniforme, la cantidad de redondeos posibles depende de la magnitud de los
nmeros que se redondean. El denominador de la ecuacin de arriba
compensa este efecto.
Una caracterstica relacionada de error relativo es que los efectos de escalar la
variable (es decir, de multiplicarla por una constante distinta de cero,
incluyendo cambios en la unidad de medicin) se cancelan. Una buena medida
del error debera ser "invariante de las escalas", de modo que al cambiar de
yardas a pulgadas, digamos, no debera amplificar el error aparente por 36,
como sucedera en la ecuacin de arriba. Si bien las matemticas puras se
inclinaran a utilizar el error absoluto, en general el error relativo se emplea en
las ciencias aplicadas.
Los mtodos numricos han sido desarrollados con el objeto de resolver
problemas matemticos cuya solucin es difcil o imposible de obtener por medio
de los procedimientos tradicionales.
Las soluciones que ofrecen los mtodos numricos son aproximaciones de los
valores reales y, por tanto se tendr un cierto grado de error que ser conveniente
determinar. Los errores numricos se generan con el uso de aproximaciones para
representar las operaciones y cantidades matemticas. Esto incluye errores de
truncamiento que resultan de representar aproximadamente un procedimiento
matemtico exacto, y los errores de redondeo, que resultan de presentar
aproximadamente nmeros exactos. Para los tipos de errores, la relacin entre el
resultado exacto o verdadero y el aproximado esta dado por:
a) Valor verdadero= aproximacin + error
Reordenando la ecuacin a se encuentra que el error numrico es igual a la
diferencia entre el valor verdadero y el valor aproximado, esto es:
b)
valor verdadero aproximacin
Donde
se usa para denotar el valor exacto del error. Se incluye el subndice v
para denotar que se trata del error verdadero. Como ya se mencion
brevemente, esto contrasta con los otros casos, donde se debe emplear una
estimacin aproximada del error.
Un defecto de esta definicin es que no toma en consideracin el orden de
magnitud del valor que se est probando. Por ejemplo, un error de un centmetro
es mucho ms significativo si se est midiendo un remache de un puente. Una
manera de medir las magnitudes de las cantidades que se est evaluando es
normalizar el error respecto al valor verdadero, como en:
Error relativo fraccional= error verdadero/ valor verdadero
Donde, como se dijo en la ecuacin b, error= valor verdadero valor
aproximado. El error relativo tambin puede multiplicarse por el 100% para
expresarlo como:
c)
Donde
100%
denota el error relativo porcentual verdadero.
Clculo de errores.
Supngase que se tiene que medir la longitud de un puente y de un remache,
obtenindose 9 999 y 9 cm, respectivamente. Si los valores verdaderos son 10
000 y 10 cm, calclese a) el error verdadero y b) el error relativo porcentual
verdadero de cada caso.
Solucin:
a) El error en la medicin del puente es (ecuacin b).
Y para el remache es de
b) El error relativo porcentual para el puente es (ecuacin c).
Y para el remache es de
Por lo tanto, aunque ambas medidas tienen un error de 1cm, el error relativo
porcentual del remache es mucho ms grande. Se puede concluir que se ha
hecho un buen trabajo en la medicin del puente, mientras que la estimacin para
el remache deja mucho que desear.
Para los mtodos numricos el valor verdadero nicamente se conocer cuando
se habla de funciones que se pueden resolver analticamente. Sin embargo, en
aplicaciones reales, no se conoce la respuesta verdadera. En estos casos,
normalizar el error es una alternativa usando la mejor estimacin posible del valor
verdadero, esto es a la aproximacin misma, como:
.100%
Donde el subndice a significa que el error est normalizado a un valor
aproximado. Uno de los retos a que se enfrentas los mtodos numricos es el de
determinar estimaciones del error en ausencia de conocimiento de los valores
verdaderos. El error se calcula como la diferencia entre la aproximacin previa y la
actual. Por lo tanto, el error relativo porcentual est dado por:
]100%
A menudo, cuando se realizan clculos, puede no importar mucho el signo del
error, si no ms bien que su valor absoluto porcentual sea menor que una
tolerancia porcentual prefijada . Por lo tanto, con frecuencia es til emplear un
valor absoluto de las ecuaciones b a la e. En estos casos, los clculos se
repiten hasta que:
Si se cumple la relacin anterior, entonces se considera que el resultado obtenido esta
dentro del nivel aceptable, es decir, aun error previamente fijado es:
ERROR DE REDONDEO Y ERROR DE TRUNCAMIENTO
Los errores de redondeo se deben a que las computadoras solo guardan un
nmero finito de cifras significativas durante un clculo. Las computadoras realizan
esta funcin de maneras diferentes; esta tcnica de retener solo los primeros siete
trminos se llam truncamiento en el ambiente de computacin. De preferencia
se llamara de corte, para distinguirlo de los errores de truncamiento. Un corte
ignora los trminos restantes de la representacin decimal completa.
La mayor parte de las computadoras tienen entre 7 y 14 cifras significativas, los
errores de redondeo pareceran no ser muy importantes. Sin embargo, hay dos
razones del por qu pueden resultar crticos en algunos mtodos numricos:
1) Ciertos mtodos requieren cantidades extremadamente grandes para obtener
una respuesta. Adems, estos clculos a menudo dependen entre s, es decir, los
clculos posteriores son dependientes de los anteriores. En consecuencia, aunque
un error de redondeo individual puede ser muy pequeo, el efecto de acumulacin
en el transcurso de la gran cantidad de clculos puede ser significativo.
2) El efecto de redondeo puede ser exagerado cuando se llevan a cabo
operaciones algebraicas que emplean nmeros muy pequeos y muy grandes al
mismo tiempo. Ya que este caso se presenta en muchos mtodos numricos, el
error de redondeo puede resultar de mucha importancia.
Las reglas del redondeo se aplican al decimal situado en la siguiente posicin al
nmero de decimales que se quiere transformar, es decir, si tenemos un nmero
de 3 decimales y queremos redondear a 2, se aplicar las reglas de redondeo:
Dgito menor que 5: Si el siguiente decimal es menor que 5, el anterior no
se modifica.
Ejemplo: 12,612. Redondeando a 2 decimales deberemos tener en cuenta el
tercer decimal: 12,612= 12,61.
En el subcampo matemtico del anlisis numrico, truncamiento es el trmino
usado para reducir el nmero de dgitos a la derecha del separador decimal,
descartando los menos significativos.
Por ejemplo dados los nmeros reales:
3,14159265358979...
32,438191288
6,3444444444444
Para truncar estos nmeros a 4 dgitos decimales, slo consideramos los 4 dgitos
a la derecha de la coma decimal.
El resultado es:
3,1415
32,4381
6,3444
Si tenemos con seguridad una cantidad de cifras exactas de un nmero decimal,
podemos dar una aproximacin de ese nmero de menos cifras de dos formas:
Truncamiento: Cortamos el nmero a partir de cierta cifra. Por ejemplo
= 3,14[Link],
truncado a las milsimas sera = 3,141 y a las
diezmilsimas = 3,1415
Redondeo: Cortamos el nmero a partir de cierta cifra, pero sumamos uno
a la ltima cifra que aparezca, en el caso de que la primera que omitamos
sea mayor o igual que 5. Por ejemplo, redondeando el nmero
= 3,14[Link] a las centsimas tenemos = 3,14, a las milsimas
= 3,142 y a las diezmilsimas = 3; 1416. En general es preferible el
redondeo al truncamiento, ya que cometemos un error menor.
Algunas veces con el fin de facilitar los clculos, se suelen redondear los nmeros
con los que se opera, y los resultados que se obtienen no son verdaderos, sino
que se consideran estimaciones.
CONVERGENCIA
Se entiende por convergencia de un mtodo numrico la garanta de que, al
realizar un buen nmero de repeticiones (iteraciones), las aproximaciones
obtenidas terminan por acercarse cada vez ms al verdadero valor buscado.
En la medida en la que un mtodo numrico requiera de un menor nmero de
interacciones que otro, para acercarse al valor numrico deseado, se dice que
tiene una mayor rapidez de convergencia.
Se entiende por estabilidad de un mtodo numrico el nivel de garanta de
convergencia, y es que algunos mtodos numricos no siempre convergen y, por
el contrario divergen; es decir, se alejan cada vez ms y ms del resultado
deseado.
En la medida en la que un mtodo numrico, ante una muy amplia gama de
posibilidades de modelado matemtico, es ms seguro que converja que otro,
entonces se dice que tiene una mayor estabilidad.
Normalmente se puede encontrar mtodos que convergen rpidamente, pero son
demasiado inestables y, por el contario, modelos muy estables, pero de lenta
convergencia.
En Mtodos numrico la velocidad con la cual una sucesin converge a su lmite
es llamada orden de convergencia. Este concepto es, desde el punto de vista
prctico, muy importante si necesitamos trabajar con secuencias de sucesivas
aproximaciones de un mtodo iterativo. Incluso puede hacer la diferencia entre
necesitar diez o un milln de iteraciones.
Supongamos que la secuencia {xk} converge al nmero .
Decimos que la sucesin converge con orden q a , si El nmero q es llamado
orden de convergencia.
En particular, convergencia de orden 1 es llamada convergencia lineal, la de orden
2 convergencia cuadrtica y la convergencia de orden 3 convergencia cbica.
En matemtica computacional, un mtodo iterativo trata de resolver un problema
(como una ecuacin o un sistema de ecuaciones) mediante aproximaciones
sucesivas a la solucin, empezando desde una estimacin inicial. Esta
aproximacin contrasta con los mtodos directos, que tratan de resolver el
problema de una sola vez (como resolver un sistema de ecuaciones Ax=b
encontrando la inversa de la matriz A). Los mtodos iterativos son tiles para
resolver problemas que involucran un nmero grande de variables (a veces del
orden de millones), donde los mtodos directos tendran un coste prohibitivo
incluso con la potencia del mejor computador disponible.
Dado que estos mtodos forman una base, el mtodo converge en N iteraciones,
donde N es el tamao del sistema. Sin embargo, en la presencia de errores de
redondeo esta afirmacin no se sostiene; adems, en la prctica N puede ser muy
grande, y el proceso iterativo alcanza una precisin suficiente mucho antes. El
anlisis de estos mtodos es difcil, dependiendo de lo complicada que sea la
funcin del espectro del operador.
10
