EXAMEN ALGORÍTMICA NUMÉRICA Julio 2015

- La duración del examen será de 1 hora y 30 minutos.

- Los tres ejercicios tienen el mismo peso en la nota del examen.
- Las notas y el procedimiento para la revisión del examen se comunicará a través de Aula Virtual.
- Fecha estimada de publicación de notas: 14 de julio.

Problema 1: Se considera la siguiente tabla de valores de una función f(x):

xk x0 = 2 x1 = 2.5 x2 = 3 x3 = 4
f ( xk ) 3 2.4 2 1.5

Se pide:

a) Construir el polinomio de interpolación de Newton de grado mínimo que

interpola los tres primeros puntos ( x 0 = 2 , x 1 = 2.5 , x 2 = 3 ) de la tabla.

Si se añade un nodo más de interpolación x 3 = 4 , esto es, se considera la tabla

completa dada inicialmente, construir el polinomio de interpolación de grado
mínimo en los cuatro puntos.

b) Dar la expresión del sistema lineal sobredeterminado que se obtendría para

calcular el polinomio de grado dos con derivada 0 en x=0 que mejor ajuste los
datos de la tabla en el sentido de mínimos cuadrados.

Problema 2: Al aplicar el método de Newton a una función f(x) de la que

sabemos que tiene una raíz en el intervalo [1,2], obtenemos los siguientes
resultados usando el punto medio del intervalo (x0=1.5) como punto inicial:

x 0 = 1.50000 x 1 = 1.44444 x 2 = 1.44225

a) Sabiendo que si el método de Newton converge se verifica que e n ≈ x n − x n +1

y que el método es de convergencia cuadrática, estimar los errores absolutos e k
de las tres iteraciones y dar una cota del error relativo para la última iteración.

b) Si estamos usando para nuestros cálculos una representación en coma

flotante (en base 2) con 16 bits dedicados a la mantisa, ¿cuántas iteraciones
adicionales tiene sentido calcular con el método anterior?

c) ¿Cuántas iteraciones serían necesarias si usamos el método de la bisección

(usando también x0=1.5 como punto inicial) para alcanzar una precisión similar?
EXAMEN ALGORÍTMICA NUMÉRICA Julio 2015

Problema 3: Dado el sistema lineal A·x = b correspondiente a las ecuaciones:

0.66 ⋅ x + 3.34 ⋅ y = 4
1.99 ⋅ x + 10.01 ⋅ y = 12
se pide:

a) Utilizando factorización LU, calcular la inversa A −1 de la matriz del sistema.

b) Si se produce un error en el sistema y el término independiente pasa a ser

⎛ 3.96 ⎞
b = ⎜⎜ ⎟⎟
⎝11.94 ⎠
calcular una cota superior del error relativo producido en la solución

c) Utilizando la definición de matriz ortogonal ( A ⋅ A T = I ), acotar el error

relativo producido en la solución del sistema ortogonal siguiente:
0.50 ⋅ x − 0.87 ⋅ y = 4
0.87 ⋅ x + 0.50 ⋅ y = 12

si se produce la variación del término independiente indicada en el

apartado b). Comparar el efecto de la perturbación en ambos sistemas.

NOTA: Trabajar con la norma y redondear los resultados de todas las

operaciones a 2 dígitos decimales.
EXAMEN ALGORÍTMICA NUMÉRICA Julio 2015

Problema 2: Al aplicar el método de Newton a una función f(x) de la que

sabemos que tiene una raíz en el intervalo [1,2], obtenemos los siguientes
resultados en las tres primeras iteraciones:
x 0 = 1.50000 x 1 = 1.44444 x 2 = 1.44225

a) Sabiendo que si el método de Newton converge se verifica que e n ≈ x n − x n +1

y que el método es de convergencia cuadrática, estimar los errores absolutos e k
de las tres iteraciones y dar una cota del error relativo para la última iteración.

Como e n ≈ x n − x n +1 podemos estimar e 0 ≈ x 0 − x 1 y e1 ≈ x 1 − x 2

e0 ≅ |1.5 – 1.44444 | = 0.05556 e1 ≅ |1.44444-1.44225| = 0.00219

2
Para estimar e2 usamos la convergencia cuadrática de Newton e n ≈ k ⋅ e n −1

e1 0.00219
Usando e1 y e0 (ya "conocidos") podemos aproximar k ≅ 2
= = 0.709
e0 0.05556 2
2
Usando ese valor k podemos ahora estimar e 2 ≈ k ⋅ e1 ≈ 0.709 ⋅ 0.00219 2 = 3.4 ⋅10 −6

Como se que la solución verifica que s>=1, Erel = Eabs/s <= e2/1 = e2, y
podemos usar e2 como cota del error relativo.

También podríamos hacer Erel = Eabs/s @ 3.4e-6 / 1.44 = 2.36e-6

b) Si estamos usando una representación en coma flotante (base 2) con 16 bits

dedicados a la mantisa, ¿cuántas iteraciones adicionales tiene sentido calcular en
el método de Newton anterior?

Una mantisa de 16 bits (base 2) corresponde a una precisión (error relativo) del
orden de 2 −16 o, en base 10, 1.5 ⋅10 −5 (puede haber un factor 2 adicional
dependiendo de si truncamos/redondeamos, pero no afecta a la discusión
posterior).

Vemos que ya hemos alcanzado esa precisión en x2, ya que el error relativo
estimado para x2 (3.4e-6) es más pequeño que la precisión de la representación.
Si iterásemos otra vez el error se iría a 1e-12, mucho más pequeño de lo que
puede manejar la representación.

c) ¿Cuántas iteraciones serían necesarias si usamos el método de la bisección

(con x0=1.5 como punto inicial) para alcanzar una precisión similar?

En la bisección el error se reduce a la mitad en cada iteración. Dado que

empezamos con una cota de error de 0.5 para x0, para alcanzar la precisión de
la máquina necesitaremos 15 o 16 iteraciones (≅ número de bits en mantisa., lo
cuál no es una coincidencia). Comparar con las 2 iteraciones necesarias en el
apartado anterior usando Newton.
Dado el sistema lineal 𝐴𝐴𝐴𝐴 = 𝑏𝑏:
0.66 𝐴𝐴 + 3.34 𝑦𝑦 = 4
1.99 𝐴𝐴 + 10.01 𝑦𝑦 = 12
Se pide:

a) Utilizando la factorización 𝐿𝐿𝐿𝐿, calcular la matriz inversa 𝐴𝐴−1 de la matriz del sistema.
b) Si se produce un error en el sistema dado y el término independiente pasa a ser:

𝑏𝑏 ∗ = (3.96, 11.94)𝑇𝑇

Calcular una cota superior del error relativo producido en la solución

c) Utilizando la definición de matriz ortogonal 𝐴𝐴𝐴𝐴𝑇𝑇 = 𝐼𝐼, acotar el error relativo
producido en la solución del sistema ortogonal:

0.50 𝐴𝐴 − 0.87 𝑦𝑦 = 4
0.87 𝐴𝐴 + 0.50 𝑦𝑦 = 12

si se produce la variación del término independiente indicada en el apartado b)

Comparar el efecto de la perturbación en ambos sistemas.

NOTA: Trabajar con la norma ∞ y redondear los resultados de todas las operaciones a
2 dígitos decimales.

SOLUCIÓN

a) 5 puntos. Factorización 𝐿𝐿𝐿𝐿

0.66 3.34 1 0 0.66 3.34
𝐴𝐴 = � � = 𝐿𝐿𝐿𝐿 = � �� �
1.99 10.01 3.02 1 0 −0.08
Cálculo de la inversa 𝐴𝐴−1
0.66 3.34 𝐴𝐴11 𝐴𝐴12 1 0
𝐴𝐴𝐴𝐴−1 = 𝐼𝐼 → � � �𝐴𝐴 𝐴𝐴 �=� �
1.99 10.01 21 22 0 1
Utilizando la factorización 𝐿𝐿𝐿𝐿
𝐴𝐴 1 𝐴𝐴 0
(𝐿𝐿𝐿𝐿) �𝐴𝐴11 � = � � 𝑦𝑦 (𝐿𝐿𝐿𝐿) �𝐴𝐴12 � = � �
21 0 22 1
Resolviendo ambos sistemas
−189.53 63.26
𝐴𝐴−1 = � �
37.75 −12.50
∗
3puntos. Si 𝐴𝐴 es la solución del sistema original y 𝐴𝐴 es la solución del sistema
perturbado, 𝑏𝑏 = (4 12)𝑇𝑇 el término independiente del sistema original y 𝑏𝑏 ∗ =
(3.96 11.94)𝑇𝑇 el término independiente del sistema perturbado, se verifica:

‖𝐴𝐴 − 𝐴𝐴 ∗ ‖∞ ‖𝑏𝑏 − 𝑏𝑏 ∗ ‖∞
≤ ‖𝐴𝐴‖∞ ‖𝐴𝐴−1 ‖∞
‖𝐴𝐴‖∞ ‖𝑏𝑏‖∞
Con nuestros datos:
‖𝐴𝐴‖∞ = 12
‖𝐴𝐴−1 ‖∞ = 252.79
 4 3.96 0.04
‖𝑏𝑏 − 𝑏𝑏 ∗ ‖∞ �� � − � �� �� ��
12 11.94 ∞ 0.06 ∞ 0.06
= = = = 0.01
‖𝑏𝑏‖∞ 4 4 12
�� �� �� ��
12 ∞ 12 ∞
Sustituyendo
‖𝐴𝐴 − 𝐴𝐴 ∗ ‖∞
≤ 12 ∙ 252.79 ∙ 0.01 = 30.33
‖𝐴𝐴‖∞
Siendo el número 12 ∙ 252.79 = 3033.48 = ‖𝐴𝐴‖∞ ‖𝐴𝐴−1 ‖∞ = 𝑐𝑐(𝐴𝐴) el número de
condición de la matiz del sistema, que es grande y por tanto, amplifica la perturbación
producida en el término independiente. El sistema es un sistema mal condicionado.
b) 2 puntos. Como la matriz del sistema es ortogonal, se verifica 𝐴𝐴−1 = 𝐴𝐴𝑇𝑇
0.5 0.87
𝐴𝐴−1 = � �
−0.87 0.5
Si se produce en este sistema el mismo error/variación que en el sistema anterior
‖𝐴𝐴‖∞ = 1.13
‖𝐴𝐴−1 ‖∞ = 1.13
4 3.96 0.04
‖𝑏𝑏 − 𝑏𝑏 ∗ ‖∞ �� � − � �� �� ��
12 11.94 ∞ 0.06 ∞ 0.06
= = = = 0.01
‖𝑏𝑏‖∞ 4 4 12
�� �� �� ��
12 ∞ 12 ∞
Por lo que
‖𝐴𝐴 − 𝐴𝐴 ∗ ‖∞
≤ 1.13 ∙ 1.13 ∙ 0.01 = 0.01
‖𝐴𝐴‖∞
En este caso 𝑐𝑐(𝐴𝐴) = 1.28 que está próximo a 1
La variación relativa de la solución del sistema es igual a la variación relativa del término
independiente, lo que significa que la variación del término independiente se transmite
“directamente” a la solución del sistema sin ser amplificada. El sistema está bien
condicionado.