Tema 1: Introducción al Cálculo Numérico

Curso 2020-21

R. Marta Garcı́a

[Link]@[Link]

15 de febrero de 2021

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 1 / 35

 Introducción a la resolución aproximada de problemas

Secciones

1 Introducción a la resolución aproximada de problemas

Ejemplo: Método de Horner

2 Introducción al estudio del error

3 Normas

4 Uso de herramientas computacionales

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 2 / 35

 Introducción a la resolución aproximada de problemas

Los problemas y las Matemáticas

”Puede haber Matemáticas sin teoremas

pero no sin problemas”

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 3 / 35

 Introducción a la resolución aproximada de problemas

Necesidad del Cálculo Numérico

Algunos ejemplos
1 Cálculo de la integral
Z b
f (x) dx
a

cuando no existe primitiva.

2 Calcular la suma de la serie

1 + 1/4 + 1/9 + 1/16 + . . .

3 Determinante de una matriz de orden d
X
det(A) = ±a1i1 . . . a1id

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 4 / 35

 Introducción a la resolución aproximada de problemas

Costo operativo y eficiencia

Algoritmo
Secuencia finita de operaciones algebraicas y lógicas que producen una solución aproximada
del problema matemático.

Ante dos métodos numéricos

Eficiencia
Tamaño de los errores.
Costo operativo.

C.N. ⇒ diseño de algoritmos y estudio de su eficiencia

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 5 / 35

 Introducción a la resolución aproximada de problemas

Debemos aprender a :
1 Convivir con errores
2 Apreciar la importancia del costo operativo
3 Apreciar la eficiencia

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 6 / 35

 Introducción a la resolución aproximada de problemas Ejemplo: Método de Horner

Método de Horner
Supongamos que deseamos hallar el valor de un polinomio de grado 4
a0 + a1 x + a2 x2 + a3 x3 + a4 x4
para un valor dado x0 de la variable x con ai ∈ R.
Método ingenuo
Calculo sucesivo de los productos (3 multiplicaciones)

x02 = x0 ∗ x0
x03 = x02 ∗ x0
x04 = x03 ∗ x0
Calculo de los productos ai xi (4 multiplicaciones)
Finalmente la 4 sumas/restas
TOTAL: 4 sumas/restas y 7 multiplicaciones

Método de Horner
Calculo sucesivo de los productos

a0 + x0 ∗ [a1 + x0 ∗ [a2 + x0 ∗ [a3 + x0 ∗ a4 ]]]

TOTAL: 4 sumas/restas y 4 multiplicaciones

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 7 / 35
 Introducción a la resolución aproximada de problemas Ejemplo: Método de Horner

Algoritmo de Horner

Definición formal

qN−1 = aN
qN−i−1 = qN−i x0 + aN−i , i = 1, . . . , N
P(x0 ) = q−1

Ejercicio: Horner en la calculadora

¿Cómo llevar a cabo el algoritmo de Horner con una calculadora de bolsillo que sólo puede
guardar un número en memoria?

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 8 / 35

 Introducción a la resolución aproximada de problemas Ejemplo: Método de Horner

Horner con lapiz y papel

Para el cálculo con lápiz y papel

aN aN−1 aN−2 ... a1 a0
x0 qN−1 x0 qN−2 x0 ... q1 x0 q0 x0

qN−1 qN−2 qN−3 ... q0 q−1

Ejercicio
a) Usar el esquema anterior para evaluar Q(x) = −12 − x2 − 4x3 + x4 + x5 en
x0 = ±1, ±2, ±3, ±4, ±6, ±12
b) ¿Cuáles son las soluciones enteras de la ecuación Q(x) = 0

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 9 / 35

 Introducción al estudio del error

Secciones

1 Introducción a la resolución aproximada de problemas

2 Introducción al estudio del error

3 Normas

4 Uso de herramientas computacionales

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 10 / 35

 Introducción al estudio del error

Errores

Error absoluto y error relativo

Supongamos que el resultado buscado es sólo un número real V y la solución numérica
calculada es N
1 Llamaremos error absoluto a la diferencia E = N − V
2 Si V 6= 0 llamaremos error relativo al cociente
|E|
|V|
3 Llamaremos error porcentual al error relativo multiplicando por 100

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 11 / 35

 Introducción al estudio del error

Cotas y estimaciones del error

Supongamos que el resultado buscado es sólo un número real V y la solución numérica

calculada es N
Una cota del error es un número positivo C para el que se pueda probar (rigurosamente en
sentido matemático) que |E| < C
Muchos métodos numéricos proporcionan junto con el valor de N una estimación ε del
error E
Se espera que ε ∼ E pero tal cosa podrı́a no ser cierta

Definición
La solución numérica N aproxima a V con t cifras significativas si t es el mayor entero no
negativo para el cual
|E|
< 5 · 10−t
|V|

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 12 / 35

 Introducción al estudio del error

Estimaciones del error

Ejemplo
1 1 1
Consideremos la serie 1 + 4
+ 9
+ 16
+ ...
La diferencia entre el verdadero valor S de la serie y la aproximación Sn es el llamado resto
de la serie
1 1
Rn = + + ...
(n + 1)2 (n + 2)2
Como Sn < S el error es por defecto. Además puede demostrarse que
1 1
< S − Sn <
1+n n
1 1
De modo que n
es una cota superior del error (absoluto) y n+1
es una cota inferior del
error.

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 13 / 35

 Introducción al estudio del error

Acotación de Rn

1 1
(x+1)2
≤ f(x) ≤ x2

1 1
Integrando entre n e ∞ se tiene < Rn <
1+n n

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 14 / 35

 Normas

Secciones

1 Introducción a la resolución aproximada de problemas

2 Introducción al estudio del error

3 Normas
Representaciones numéricas
Condicionamiento y estabilidad de un algoritmo
Velocidad de convergencia de un algoritmo

4 Uso de herramientas computacionales

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 15 / 35

 Normas Representaciones numéricas

Mantisa y exponente

Por ejemplo, podemos expresar −618,45 como:

−618,45 + 0
−61,845 + 1
−6184,5 − 1
−6,1845 + 2

que significa −618,45 × 100

−61,845 × 101
−6184, 5 × 10−1
−6,1845 × 102

6,1845 es la mantisa y 2 es el exponente

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 16 / 35

 Normas Representaciones numéricas

Notación decimal de punto flotante

Ejemplo
El formato decimal es incómodo si el número es en valor absoluto muy grande o muy
pequeño. Por ejemplo el número de Avogadro (1776-1856)

602213670000000000000000

La masa de un protón

0,0000000000000000000000000016726231

Conviene entonces usar las representaciones

6,0221367 × 1023
1,6726231 × 10−27

Esta representación se llama de punto flotante

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 17 / 35

 Normas Representaciones numéricas

Notación normalizada

Se llama notación decimal en punto flotante normalizada a aquella de la forma

±m ± E

donde m es la mantisa y E el exponente siendo 1 ≤ m < 10 y E ∈ N ∪ {0}

Aplicación

±0.d1 d2 d3 . . . dk · 10±E
con 1 ≤ d1 ≤ 9; 0 ≤ dj ≤ 9 j ≥ 2. Los números representables de esta forma exacta en el
ordenador se llaman números máquina

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 18 / 35

 Normas Representaciones numéricas

Aritmética de simple y doble precisión

Representación de números de punto flotante en simple y doble precisión

Propiedad Simple Precisión Doble Precisión
Mayor número representable 3.402823466 1038 1.7976931348623157 10308
Menor número sin pérdida de precisión 1.175494351 10−38 2.2250738585072014 10−308
Menor númer representable 1.401298464 10−45 5 10−324
Bits de mantisa 23 52
Bits de exponente 8 11
Epsilon 1.1929093 10−7 2.220446049250313 10−16

[Link]

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 19 / 35

 Normas Representaciones numéricas

Error especı́fico unitario

Error máquina
1 La diferencia entre dos números máquina consecutivos se llama error de redondeo de la
máquina
2 El error de redondeo unitario  de la máquina se define como la distancia desde el número
1 al siguiente en coma flotante. Suele estar almacenado en la variable eps
3 Si fl(x) es la representación en coma flotante de un número x distinto de cero se verifica

fl(x) = x(1 + δ)

donde |δ| ≤ 

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 20 / 35

 Normas Representaciones numéricas

Error especı́fico unitario

Ejercicio
Un sistema rudimentario que tuviese una mantisa de sólo dos cifras
¿ Cuántos números del intervalo 1 ≤ x ≤ 2 puede representar?

Respuesta
Once.
1,0 × 100 ; 1,1 × 100 ; . . . ; 2,0 × 100

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 21 / 35

 Normas Representaciones numéricas

La aritmética de punto flotante

Como consecuencia de la representación en punto flotante, la aritmética en punto flotante es

diferente a la ”verdadera”
Normas
Conviene formular los algoritmos de forma que se evite susbstraer cantidades casi iguales
No existe la asociatividad en coma flotante. Basta tomar las variables
x = 1 × 1020 , y = −1 × 1020 , z = 1 y calcular x + (y + z) y (x + y) + z en MATLAB y
comprobar que conducen a 0 y 1 respectivamente
En general ha de evitarse sumar reiteradamente sumandos de pequeña magnitud a una
cantidad grande, siendo preferible sumar primero las cantidades pequeñas entre sı́ y luego
agregarlas a la grande
A veces a los errores derivados de la mantisa finita que usa el ordenador se les llama
errores de redondeo

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 22 / 35

 Normas Condicionamiento y estabilidad de un algoritmo

Propagación del error

Los errores se propagan a través de los cálculos, debido a la estructura propia del algoritmo.
Para estudiar esta propagación, y por tanto el error final, consideramos dos conceptos:
Condicionamiento
Estabilidad

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 23 / 35

 Normas Condicionamiento y estabilidad de un algoritmo

Condicionamiento y estabilidad de un algoritmo

Condicionamiento Estabilidad
Se refiere a cuán sensible es la Un algoritmo es estable si está
solución de un problema respecto de limitado el efecto acumulativo de
pequeños cambios relativos a los errores.
datos de entrada. Un algoritmo es inestable si la
Para ello se introduce el llamado acumulación de errores de redondeo
número de condición de dicho produce una solución colmada de
problema, especı́fico del problema, errores.
que es mejor cuanto más cerca de 1
(el problema está bien condicionado)
y peor cuanto más grande sea (peor
condicionado).

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 24 / 35

 Normas Condicionamiento y estabilidad de un algoritmo

Ejemplo de mal condicionamiento

Consideremos el sistema

x+y = 1
1,1x + y = 2
La solución exacta es x = 10, y = −9.

Si ahora cambiamos sólamente un coeficiente del sistema...


x+y = 1
1,05x + y = 2
La solución exacta es x = 20, y = −19.

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 25 / 35

 Normas Condicionamiento y estabilidad de un algoritmo

Propagación de errores de redondeo

Teorema
Sean x1 , x2 , ..., xn números máquina positivos en un ordenador cuyo error de redondeo unitario
es .Entonces el error de redondeo relativo al calcular
n
X
xi
i=1

de la manera usual es, a lo sumo, (1 + )n − 1 ∼ n.

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 26 / 35

 Normas Condicionamiento y estabilidad de un algoritmo

Un ejemplo de algoritmo inestable

Consideremos la sucesión definida por

a0 = 6
a1 = 6
1130 3000
an+1 = 111 − + n≥2
an an an−1

Cálculo simbólico
Se puede demostrar por inducción sobre n que an = 6 n≥1

Cálculo con MATLAB

> a0=6;a1=6; a2 = 6, 000000
> for k=2:300;
a8 = 6, 000000
> ak=111-1130/a1+3000/(a0*a1);
> fprintf(1,’El término k-esimo a9 = 5, 999995
es’,k,ak) ..
> a0=a1; .
> a1=ak; a16 = 105, 039728
> end a17 = 100, 287876
[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 27 / 35
 Normas Velocidad de convergencia de un algoritmo

Órdenes de convergencia

Métodos iterativos
Son quellos métodos numéricos que generan una sucesión de soluciones aproximadas (o
iterantes), cada vez más precisas.

Orden de convergencia
Describe la velocidad de convergencia de una sucesión a a una solución.

Definición
Se dice que la sucesión {xn }∞ ∞
n=1 es de orden {yn }n=1 cuando n → ∞ si existen constantes M y
N tal que
|xn | < M|yn | n > N
En este caso se dice que xn = O(yn ). (Notación O de Landau)

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 28 / 35

 Normas Velocidad de convergencia de un algoritmo

Órdenes de convergencia

Sea {xn }∞
n=1 una sucesión de números reales que tiende a un lı́mite x
∗

Convergencia lineal Se dice que la convergencia es, por lo menos lineal si existe una constante
C < 1 y un entero N ∈ N tales que

|xn+1 − x∗ | < C|xn − x∗ | para todo n ≥ N

Convergencia superlineal El orden de convergencia es superlineal si existe una sucesión

{n }∞
n=1 tendiendo a cero y un entero N ∈ N tales que

|xn+1 − x∗ | < n |xn − x∗ | para todo n ≥ N

Convergencia cuadrática La convergencia es, al menos cuadrática, si existe una constante

M ∈ R y un entero N ∈ N tales que

|xn+1 − x∗ | < M|xn − x∗ |2 para todo n ≥ N

Convergencia de orden α En general, si existen dos constantes reales M, α ∈ R y un entero

N ∈ N tales que

|xn+1 − x∗ | < M|xn − x∗ |α para todo n ≥ N

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 29 / 35

 Uso de herramientas computacionales

Secciones

1 Introducción a la resolución aproximada de problemas

2 Introducción al estudio del error

3 Normas

4 Uso de herramientas computacionales

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 30 / 35

 Uso de herramientas computacionales

Ejercicio

Sea f (x) = 1,013x5 − 5,262x3 − 0,01732x2 + 0,8389x − 1,912 Evaluar f (2,279), calculando en primer
lugar 2,2792 , 2,2793 , 2,2794 , 2,2795 usando aritmética de 4 cifras y redondeo
>>A=2.279.ˆ[0 1 2 3 4 5]

A =

1 2.2790 5.1938 11.8368 26.9760 61.4783

>> %redondeo a 4 cifras de A

a =
1 2.2790 5.1940 11.8400 26.9800 61.4800

>> B=[-1.912 0.8390 -0.0170 -5.2620 0 1.0130]

B =
-1.912 0.8390 -0.0170 -5.2620 0 1.0130

>> %redondeo a 4 cifras de B

>> b=[-1.912 0.839 -0.017 -5.262 0 1.013]

b =
-1.912 0.839 -0.017 -5.262 0 1.013

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 31 / 35

 Uso de herramientas computacionales

Ejercicio

Sea f (x) = 1,013x5 − 5,262x3 − 0,01732x2 + 0,8389x − 1,912 Evaluar f (2,279), calculando en primer
lugar 2,2792 , 2,2793 , 2,2794 , 2,2795 usando aritmética de 4 cifras y redondeo
a =

1 2.279 5.194 11.84 26.98 61.48

b =

-1.912 0.839 -0.017 -5.262 0 1.013

>> v=a.*b
% con redondeo a 4 cifras
v =

-1.912 1.912 -0.088 -62.30 0 62.28

>> sum(v)

ans =

-0.108

-0.108

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 32 / 35

 Uso de herramientas computacionales

Ejercicio

Archivo horner.m en MATLAB

function [ p, pp ] = horner ( c, x )
%
% HORNER evaluates a polynomial and its derivative at a point x.
%
n = size ( c, 2 );

pp = 0.0; p = c(1);
for i = 2: n
pp = pp * x + p;
p = p * x + c(i);
end

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 33 / 35

 Uso de herramientas computacionales

Ejercicio

Utilizando el Método de Horner

>>[ p, pp ]=horner([1.013 0 -5.262 -0.01732 0.8389 -1.912],2.279)
p =
-0.0977
pp =
55.4033
>> [ p, pp ] = horner ( [1.013 0 -5.262 -0.017 0.839 -1.912],2.27
p =
-0.0958
pp =
55.4049

-0.096

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 34 / 35

 Uso de herramientas computacionales

Aproximación a y = ln(x + 1) en [−1, 1]

[Link]@[Link] (Dpto. Matemáticas) Métodos Numéricos I. Mecánica 15 de febrero de 2021 35 / 35