PDF de programación - Programación: el método iterativo con direcciones aleatorias y con la búsqueda exacta sobre cada recta

Programaci´on: el m´etodo iterativo

con direcciones aleatorias

y con la b´usqueda exacta sobre cada recta

Objetivos. Programar el m´etodo iterativo con direcciones aleatorias y con la b´usqueda
exacta sobre cada recta.

Requisitos. Soluci´on de sistemas sim´etricas positivas definidas por medio de la minimi-
zaci´on de un funcional.

1. El m´ınimo de una forma cuadr´atica sobre una recta. Sea A una matriz real
sim´etrica estrictamente positiva definida de orden n, y sea b ∈ Rn. Dado un vector x ∈ Rn
y una direcci´on p ∈ Rn \ {0}, consideremos la funci´on

g(α) =

(x + αp)(cid:62)A(x + αp) − b(cid:62)(x + αp).

1
2

Escriba g como un polinomio de grado 2 en la variable α, calcule g(cid:48) y encuentre el punto
αmin donde g alcanza su valor m´ınimo. Se recomienda usar la notaci´on r = b − Ax.
2. El cambio del residuo al cambiar el vector. Sean A, b, x, p, r los mismos que en
el ejercicio anterior. Definimos el vector nuevo y como

y = x + αp.

Exprese el residuo nuevo b − Ay a trav´es del residuo previo:

b − Ay = b − Ax

+???.

(cid:124) (cid:123)(cid:122) (cid:125)

r

3. Algoritmo.

function [x, s] = randomiter(A, b, tol, smax),

n = length(b);
x = zeros(n, 1);
r = b;
s = 0;
while (s < smax) && (norm(r) >= tol),

p = 2 * rand(n, 1) - ones(n, 1);
q = A * p;
alpha = (p’ * r) / (p’ * q);
x = x + alpha * p;
r = r - alpha * q;
s = s + 1;

end

end

Programaci´on: direcciones aleatorias, p´agina 1 de 3

4. Una modificaci´on del algoritmo que guarda los pasos.

function [xsequence] = randomitersequence(A, b, tol, smax),

n = length(b);
xsequence = zeros(n, smax);
x = zeros(n, 1); r = b; s = 0;
while (s < smax) && (norm(r) >= tol),

p = 2 * rand(n, 1) - ones(n, 1);
q = A * p;
alpha = (p’ * r) / (p’ * q);
x = x + alpha * p;
r = r - alpha * q;
s = s + 1;
xsequence(:, s) = x;

end

end

5. Prueba en el plano con un dibujo. El siguiente c´odigo consiste de dos funciones y
se debe guardar en un archivo plotrandomiter.m

function [] = plotrandomiter(),

A = [3 -2; -2 2];
sol = [1; -6]; # exact solution
b = A * sol;
n = length(b);
xsequence = randomitersequence(A, b, 1.0E-8, 6);
disp(xsequence);
r = max(abs(xsequence(:, 1) - sol));
plotdomain = [sol(1) - r, sol(1) + r, sol(2) - r, sol(2) + r];
plot(xsequence(1, :), xsequence(2, :), ’-w’, ’linewidth’, 3);
hold on;
ezcontourf(@(var1, var2) f(var1, var2, A, b, sol), plotdomain, 100);

end

function [result] = f(var1, var2, A, b, sol),

[size1, size2] = size(var1);
result = zeros(size1, size2);
for j = 1 : size1,

for k = 1 : size2,

x = [var1(j, k); var2(j, k)];
result(j, k) = sqrt(0.5 * (x - sol)’ * A * (x - sol));

end

end

end

Programaci´on: direcciones aleatorias, p´agina 2 de 3

El dibujo correspondiente:

6. Pruebas con matrices y vectores de tama˜nos grandes. Escriba una funci´on que
haga pruebas de la funci´on randomiter con matrices y vectores aleatorios de tama˜nos
grandes. Observe c´omo se cambia el tiempo de ejecuci´on y el n´umero de pasos al aumentar
n. Para generar matrices aleatorias sim´etricas y positivas definidas se pueden usar los
siguientes comandos:

B = rand(n, n); A = B’ * B;

Programaci´on: direcciones aleatorias, p´agina 3 de 3

var2var1f (var1, var2, A, b, sol)0.70.80.911.11.21.3-2.3-2.2-2.1-2-1.9-1.8-1.7