PDF de programación - Programación: descomposición QR completa usando reflexiones de Householder

Programación: descomposición QR completa

usando reflexiones de Householder

Objetivos. Programar una función que realice el algoritmo de descomposición QR usando
reflexiones de Householder.

Requisitos. Reflexión ortogonal respecto a un hipersubespacio, construcción de un vector
de Householder.

Se recomienda resolver estos ejercicios antes de la clase práctica.

1. Reflexión ortogonal respecto a un hipersubespacio (repaso). Dado un vector
a ∈ R \ {0n}, denotamos por Ha a la matriz de reflexión ortogonal respecto al hipersu-
bespacio {a}⊥. Recuerde la fórmula para la matriz Ha:

Ha =

2. Aplicar la reflexión ortogonal simultáneamente a varias columnas. Suponga-
mos que a ∈ R \ {0n} y X ∈ Mn×m(R). Aplicamos Ha a todas las columnas de X:

HaX = X − 2
a2

aaX = X − 2

a2 a(aX).

Determine cuál de las dos fórmulas escritas requiere menos operaciones aritméticas con
entradas de matrices y vectores (en otras palabras, menos flops).
3. Construcción de un vector de Householder (repaso). Dado un vector f ∈ Rn
tal que f = fe1, encuentre un vector a ∈ Rn tal que Haf = fe1:

a =



?



.

Escriba una función householdervector que calcule este vector.

4. Descomposición QR completa con reflexiones de Householder, el caso de
tres columnas.

function [Q, R] = qrh3columns(A),

[n, m] = size(A); R = A; Q = eye(n);
# step 1
a = householdervector(R(1 : n, 1)); coef = 2 / (norm(a) ^ 2);
R(1 : n, 1 : 3) -= coef * a * (a’ * R(1 : n, 1 : 3));
Q(:, 1 : n) -= coef * (Q(:, 1 : n) * a) * a’;
# step 2

Programación: QR con reflexiones de Householder, página 1 de 2

a = householdervector(R(2 : n, 2)); coef = 2 / (norm(a) ^ 2);
R(2 : n, 2 : 3) -= coef * a * (a’ * R(2 : n, 2 : 3));
Q(:, 2 : n) -= coef * (Q(:, 2 : n) * a) * a’;
# step 3
a = householdervector(R(3 : n, 3)); coef = 2 / (norm(a) ^ 2);
R(3 : n, 3 : 3) -= coef * a * (a’ * R(3 : n, 3 : 3));
Q(:, 3 : n) -= coef * (Q(:, 3 : n) * a) * a’;

end

Prueba:

function [] = testqrh3columns(),

n = 5; m = 3;
A = rand(n, m);
[Q, R] = qrh3columns(A);
display(Q);
display(R);
display(norm(Q’ * Q - eye(n)));
display(norm(Q * R - A));

end

5. Problema: descomposición QR con reflexiones de Householder. Generalice las
funciones de ejercicios anteriores al caso de un número arbitrario de columnas.

Entrada: A ∈ Mn×m(R), donde n ≥ m y r(A) = m.
Salida: matrices Q ∈ Mn(R) y R ∈ Mn×m(R) tales que A = QR, QQ = In y
Rj,k = 0 para cualesquiera j, k tales que j > k.

6. Pruebas con matrices pequeñas. Haga pruebas pequeñas de la función programada
(con matrices de 3 columnas, de 4 columnas, de 5 columnas) para verificar que la función
es correcta.

7. Pruebas con matrices grandes. Haga pruebas con matrices aleatorias de tamaños
grandes (n = 200, n = 400, o más grandes, m = n o m = n/2), y analice cómo depende
de n el tiempo de ejecución.

8. Tarea optativa. Revise libros y encuentre sugerencias sobre el cálculo del vector de
Householder y la realización del método QR con reflexiones de Householder. Intente de
disminuir los errores de redondeo en la función programada.

Programación: QR con reflexiones de Householder, página 2 de 2