Método del Gradiente

Gradiente

El gradiente de una función escalar de n variables "f(x₁,x₂……….xₐ)" denotado por grad(f), es el vector n-dimensional.
La idea consiste en que el gradiente es un vector perpendicular a las curvas de nivel, con lo cual dependiendo del valor (positivo o negativo) habrá una aproximación al máximo o al mínimo, poniendo un ejemplo, en función del gradiente se puede conocer qué dirección debo tomar para subir o bajar más rápidamente una montaña.
El Hessiano de una función escalar de n variables f(x1,x2……..xa) denotado por Hf, es la matriz de dimensión nxn.

matriz%20hessiana.png

Método del Gradiente

Supongamos que f(x) es una función de una variable a ser minimizada y que f(x) y f’(x) existen, entonces: x(k+1)=x(k)-f’(x(k)).
Se utiliza una constante para “escalar” por el gradiente:
$x(k+1)=x(k)-∝f'(x(k))$ (Método del gradiente modificado)
En un principio el valor ∝ ∈(0,1] , es decir, un parámetro ajustable seleccionado por el analista.
Es deseable que alfa decrezca a medida que progresa la búsqueda, lo que hace que tengamos dos parámetros por ajustar: alfasub0 y la tasa de disminución de alfa.

Método del Gradiente Conjugado

Este método, denominado método del descenso más rápido, es una de las técnicas más antiguas para minimizar una función definida en un espacio multidimensional. Su filosofía es muy sencilla: misma dirección pero sentido contrario al del vector gradiente en un punto es la dirección de más rápido decrecimiento de la función en ese punto. Es un método iterativo, así que se puede aplicar a los sistemas dispersos que son demasiado grandes para ser tratados por métodos directos como la descomposición de Cholesky.
La idea esencial que trata el método del gradiente conjugado consiste en construir una base de vectores ortogonales y utilizarla para realizar la búsqueda de la solución en forma más eficiente.
El procedimiento a seguir es el siguiente:

Se selecciona un punto inicial xi sobre la superficie y se determina el gradiente f(x) en ese punto. Para funciones cuadráticas cualquier elección del punto inicial en principio es igualmente satisfactoria, pero para funciones generales es posible que converja a un mínimo no deseado.

Se determina un nuevo punto según la fórmula:

$x(i+1)=xi-alfagradf(x)$

Se repite el paso 2º hasta que se encuentre un punto x(i+1) tal que gradf(x(i+1))=0

Script del método del gradiente conjugado:

grad_conj:=proc(n,A,b,semilla,eps,maxiter, sol, niter,tol)
local d, i, alpha,x,y,r,z,iter,rho:
x:=vector(n):
tol:=array(0..maxiter):
y:=vector(n):
r:=vector(n):
d:=vector(n):
z:=vector(n):
sol:=vector(n):
x:=evalm(semilla):
i:=0:
r:=evalm(b-A&*x):
d:=evalm(r):
tol[0]:= norm(r,1):
while ((i < maxiter) and (tol[i] > eps) ) do
z:=evalm(A&*d):
rho:=dotprod(r,d)/dotprod(d,z):
y:=evalm(x+rho*d):
r:=evalm(b-A&*y):
alpha:=dotprod(r,z)/dotprod(d,z):
d:=evalm(r-alpha*d):
i:=i+1:
tol[i]:=norm(r,1):
x:=evalm(y):
od:
sol:=evalm(x):
niter:=i:
end

Comandos de MatLab

El comando pcg(): resuelve un sistema de ecuaciones lineales por el método del Gradiente Conjugado Pre-condicionado. La matriz debe ser simétrica y positivo-definida.
El comando bicg(): resuelve para el caso anterior cuando las matrices cuadradas que no son simétricas y positivo-definidas.

Ejercicio. Diseño de una tobera

Queremos diseñar una tobera convergente divergente. Para ello impondremos que el radio de salida sea 10 veces mayor que el radio de la garganta, y que la tobera se forma mediante dos parábolas, una con eje en y y otra con eje en x. Las condiciones serán que en el punto de empalme de los dos arcos haya continuidad tanto de la función como de la derivada primera. Las dos funciones a ajustar serán entonces (con el problema convenientemente adimensionalizado)

$y-=Px2+0.1$

$y+=Ax+B$

Entonces tenemos el sistema de ecuaciones siguiente, donde l es el punto en x donde se empalman los dos arcos:

$2Pl=A/(2Al+B)$

$Pl2+0.1=Ax+B$

$A+B=1$

Donde se demuestra que existe solución para P aproximadamente 0.9<P<1.2.
Resolver el sistema de ecuaciones anterior y representar las soluciones de P=0.9, P=1 y P=1.2

Guía para la resolución del ejercicio

Lo primero que debemos hacer es entender el enunciado, para ver más claro lo que se pide, es bueno dibujar las dos curvas que se nos proponen, para ello haremos;
octave:1> fplot('[x. ^2+0.1,sqrt(x)]',[0,1])

Para resolver numéricamente sistemas de ecuaciones lineales usaremos la función fsolve. Para saber cómo funciona teclearemos en la línea de comandos:
octave:2> help fsolve

Solución del ejercicio

El script que nos resuelve el problema es el siguiente:

function[f]=ttb(x)
global Pi
f(1)=x(1)/(2*sqrt(x(1)*x(3)+x(2)))-2*Pi*x(3);
f(2)=Pi*x(3)**2+0.1-sqrt(x(1)*x(3)+x(2));
f(3)=sqrt(x(1)+x(2))-1;
end

function[f]=tobera(x,a,b,l,P)
if x<l
f=P*(x*x)+0.1;
else
f=sqrt(a*x+b);
endif
end
x0=[1 1 1];
P=[0.9 1 1.2];
hold on
for i=1:3
global Pi
Pi=P(i);
[res]=fsolve('ttb',x0);
xcoord=linspace(0,1,100);
for j=1:100
tob(j)=tobera(xcoord(j),res(1),res(2),res(3),P(i));
end
plot(xcoord,tob)
end

hold off

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License