PDF de programación - Programación: ortogonalización con respecto al producto interno no canónico usando el método de Gram-Schmidt modificado

Programaci´on: ortogonalizaci´on con respecto

al producto interno no can´onico

usando el m´etodo de Gram–Schmidt modificado

Objetivos. Aplicar el m´etodo de Gram–Schmidt modificado a un ejemplo, usando el
producto interno inducido por una matriz real sim´etrica positiva definida.

Requisitos. Operaciones con vectores (operaciones lineales y el producto punto), ciclos,
la idea del m´etodo de Gram–Schmidt modificado.

Producto interno no can´onico

Los siguientes comandos est´an escritos en el lenguaje de MATLAB y se pueden ejecutar
en MATLAB o en sus an´alogos libres (GNU Octave, Scilab, FreeMat).

1. Producto interno asociado a una matriz positiva definida. Sea A una matriz
real sim´etrica positiva definida. Denotemos por (cid:104)·,·(cid:105)A al producto interno asociado a esta
matriz:

(cid:104)x, y(cid:105)A := x(cid:62)Ay.

Ejecute los siguientes comandos en el int´erprete:

# the matrix is autoadjoint
# the eigenvalues are strictly positive

A = [1 -1 -1; -1 4 1; -1 1 3];
A’ - A
eig(A)
x = [3; -1; 4]
y = [1; 5; -3]
x’ * A * y
y’ * A * x

2. Generaci´on de matrices aleatorias positivas definidas. Recordemos que una
matriz A ∈ Mn(R) es sim´etrica y positiva semidefinida (A(cid:62) = A y x(cid:62)Ax ≥ 0 para cada
x ∈ Rn) si, y s´olo si, existe una matriz B ∈ Mn(R) tal que A = B(cid:62)B. Adem´as, si una
matriz A es sim´etrica positiva semidefinida y ε > 0, entonces la matriz A + εIn es positiva
definida.

B = rand(3, 3);
A = B’ * B + 0.1 * eye(3);
A’ - A
eig(A)

Programaci´on: Gram–Schmidt modificado, producto interno no can´onico, p´agina 1 de 4

Proyecci´on ortogonal
3. Vectores A-conjugados. Sea A ∈ Mn(R) una matriz real sim´etrica positiva definida.
Dos vectores x, y ∈ Rn se llaman A-ortogonales o A-conjugados si

esto es, si

(cid:104)x, y(cid:105)A = 0,

x(cid:62)Ay = 0.

4. Proyecci´on ortogonal de un vector al otro con respecto al producto interno
no can´onico. Sea A una matriz real sim´etrica positiva definida. Dados dos vectores a y
v en R3, calculemos λ ∈ R tal que a ⊥A (v − λa), esto es,

a(cid:62)A(v − λa) = 0.

Denotemos λa por u y v−λa por w. Verifiquemos que se cumple la identidad de Pit´agoras
para los vectores u, w, v (con respecto a la norma (cid:107) · (cid:107)A).

A = [1 -1 -1; -1 4 1; -1 1 3];
a = [-3; 2; 1]
v = [-8; 1; 4]
lambda = (a’ * A * v) / (a’ * A * a)
u = lambda * a
w = v - u
a’ * A * w
[(u’ * A * u) + (w’ * A * w), (v’ * A * v)]

Programaci´on: Gram–Schmidt modificado, producto interno no can´onico, p´agina 2 de 4

Proceso de ortogonalizaci´on de Gram–Schmidt modificado
para un producto interno no can´onico
5. Ortogonalizaci´on de Gram–Schmidt. Dada una matriz A ∈ M3(R) real sim´etrica
positiva definida y tres vectores a1, a2, a3 ∈ R3, construimos tres vectores A-ortonormales
b1, b2, b3 ∈ R4 aplicando el algoritmo de Gram–Schmidt modificado a los vectores dados
a1, a2, a3. Al final comprobamos que los vectores b1, b2, b3 son A-ortogonales a pares cal-
culando su matriz de Gram con respecto al producto (cid:104)·,·(cid:105)A. El siguiente c´odigo se puede
guardar en un archivo MGSAexample.m.

function [] = MGSAexample(),

a1 = [-2; 5; 1]
a2 = [-1; 6; 3]
a3 = [-11; 20; 9]

b1 = a1;
b2 = a2;
b3 = a3;

# Step 1
nu1 = sqrt(b1’ * A * b1)
b1 = b1 / nu1
lambda21 = b1’ * A * b2
b2 = b2 - lambda21 * b1
lambda31 = b1’ * A * b3
b3 = b3 - lambda31 * b1

# Step 2
nu2 = sqrt(b2’ * A * b2)
b2 = b2 / nu2
lambda32 = b2’ * A * b3
b3 = b3 - lambda32 * b2

# Step 3
nu3 = sqrt(b3’ * A * b3)
b3 = b3 / nu3

# Verify that b1, b2, b3 form an A-orthonormal list
b1b2b3 = [b1 b2 b3]
G = b1b2b3’ * A * b1b2b3

end

Programaci´on: Gram–Schmidt modificado, producto interno no can´onico, p´agina 3 de 4

Descomposici´on QR generalizada

6. Descomposici´on QR generalizada de una matriz de tres columnas usando
el m´etodo de Gram–Schmidt modificado. El siguiente algoritmo construya una des-
composici´on de la matriz dada V de tres columnas en un producto QR tal que R es
triangular superior y las columans de Q son A-conjugadas.

function [Q, R] = QRMGSA3(V, A),

[n, m] = size(V);
Q = V; R = eye(m);
# primer paso
R(1, 1) = sqrt(Q(:, 1)’ * A * Q(:, 1));
Q(:, 1) = Q(:, 1) / R(1, 1);
R(1, 2) = Q(:, 1)’ * A * Q(:, 2);
Q(:, 2) = Q(:, 2) - R(1, 2) * Q(:, 1);
R(1, 3) = Q(:, 1)’ * A * Q(:, 3);
Q(:, 3) = Q(:, 3) - R(1, 3) * Q(:, 1);
# segundo paso
R(2, 2) = sqrt(Q(:, 2)’ * A * Q(:, 2));
Q(:, 2) = Q(:, 2) / R(2, 2);
R(2, 3) = Q(:, 2)’ * A * Q(:, 3);
Q(:, 3) = Q(:, 3) - R(2, 3) * Q(:, 2);
# tercer paso
R(3, 3) = sqrt(Q(:, 3)’ * A * Q(:, 3));
Q(:, 3) = Q(:, 3) / R(3, 3);

end

Prueba:

function [] = testQRA3(),

# A es real simetrica positiva definida

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

end

7. Problema principal. Generalice el algoritmo anterior al caso de una matriz V rec-
tangular de tama˜no general n × m, n ≥ m, con columnas linealmente independientes.
Escriba la funci´on correspondiente QRMGSA. Haga pruebas con datos peque˜nos y con
datos grandes.

Programaci´on: Gram–Schmidt modificado, producto interno no can´onico, p´agina 4 de 4