Embed Size (px)
DESCRIPTION
Métodos Numéricos
Citation preview
UN MODELO APLICADO A LA AGRICULTURA RESUELTO CON EL METODO DE FACTORIZACION QR (POR HOUSEHOLDER)
Soto Fernández, Neisser Arturo.
Leonardo Rodríguez Deyvis Iván
2015
FACULTAD DE CIENCIAS FISICAS Y MATEMATICAS
Método de Factorización QR (Por Householder)
Sea A una matriz cuadrada.Las reflexiones de Householder se define de la siguiente manera 2 t
u nH I uu
Reflexiones aniquiladora de Householder
1 2 1 1 ..... .....T
j j j na a a a a a a
jH
Donde los son vectores columnas de la matriz
na 0A A
Si (modulo del vector ) y (signo de ) donde es la columna entonces:
2 2........j na a a ja0 j
1
0
01
2 ( )j
jj
n
a nua a
a
j uH H , satisface
1 1
1 1
1
.0
( )
0
j j
j j
j
n
a a
a a
H a
a
a
Así el mapeo aniquila los componentes por debajo de en el valor dado
La factorización puede usarse para resolver sistemas lineales.Si donde dónde donde
jx H x jaa
QRA QR
1TQ Q Ax b Rx C TC Q b
Algoritmo de triangulación superior ortogonal:
una matriz ortogonal que aniquila todos los elementos debajo de la diagonal de pero que no altere los ceros de la aniquilación previas. { tiene ceros debajo de sus primeros elementos diagonales}
Después: (Es una matriz triangular superior)
Donde: es un producto de matrices ortogonales y es ortogonal.Luego: donde yLa matriz aniquiladora de Householder puede usarse para
0 : n nA A 1j 1n Si y hacer:
:jP
1j jcol A
1: .j j jA P A jA
1 1 2 1( ..... . ).n nA P P P A
1 2 1..... .nP P P
A QR 1 2 1( ...... . )TnQ P P P 1nR A
j uH H jP
Ahora presentaremos un ejemplo aplicado a la agricultura y mediante ello resolveremos el sistema de ecuaciones lineales por el método de factorización QR (Por Householder).
Agricultura:
Un agricultor tiene 200 hectáreas de terreno adecuado para cultivos de maíz, papás y trigo. Los costos respectivos por hectárea de los cultivos de trigo, maíz y papas son S/.400, S/.600, S/.800, respectivamente. El agricultor dispone de S/.126,000 para el cultivo. Cada hectárea de cultivo de trigo requiere 20 horas de trabajo; cada hectárea de cultivo de maíz 25 horas de trabajo, y cada hectárea de cultivo de papas 40 horas de trabajo. El agricultor tiene un máximo de 5950 horas de trabajo disponibles. Si desea utilizar toda la tierra cultivable, todo el presupuesto y toda la mano de obra disponible. ¿Cuántas hectáreas debe plantar de cada cultivo?
Solución:
El número de hectáreas de cultivo de trigo.El número de hectáreas de cultivo de papas.El número de hectáreas de cultivo de maíz.
1
2
3
xxx
Las condiciones de utilizar toda la tierra cultivable se traduce en la ecuación:
1 2 3 200x x x
El costo total por los tres cultivos fue de soles, y como hay que ocupar todo el presupuesto, entonces
1 2 3400 600 800x x x
1 2 3400 600 800 126000x x x
Por último, la cantidad de trabajo necesaria para los tres cultivos es 1 2 320 25 40x x x
horas, y como debe utilizarse toda la mano de obra, se tiene:
1 2 320 25 40 5950x x x
Luego, el problema se reduce a resolver el siguiente sistema de ecuaciones lineales:
1 2 3 200x x x
1 2 3400 600 800 126000x x x
1 2 320 25 40 5950x x x
En forma matricial tenemos:
1 1 1400 600 80020 25 40
A
;
1
2
3
xx x
x
y
2001260005950
b
Resolvemos el sistema usando el método de factorización QR (Por Householder)
1 1 1400 600 80020 25 40
A
1
2
3
xx x
x
y
2001260005950
b
;
.A x b
Sea (Matriz inicial) ; donde0
3 3
1 1 1400 600 80020 25 40
A A
3n
Calcularemos los pasos a seguir del método
140020
a
, 2 2 21 400 20 400.5009
Donde el signo de es , 1ja 1j
1 400.50091 400
2(400.5009)(1 400.5009) 20
0.70800.70530.0353
u
0.7080 0.7053 0.0353Tu
Luego:
1 3
1
21 0 0 0.70800 1 0 2 0.7053 . 0.7080 0.7053 0.03530 0 1 0.0353
TuH H I uu
H
1
-0.0025 -0.9987 -0.0499-0.9987 0.0050 -0.0498-0.0499 -0.0498 0.9975
H
Entonces, Satisface:
1
1 400.5009. 400 020 0
H
Se asume 1 1P H
Luego:1 1 0
1
1
.-0.0025 -0.9987 -0.0499 1 1 1-0.9987 0.0050 -0.0498 . 400 600 800-0.0499 -0.0498 0.9975 20 25 4
0
-400.5009 -600.5005 -800.99940 0.7481 0.99870 4.9
626
0
A P A
A
A
.0499
Ahora la segunda columna de la matriz 1A
600.50050.74814.9626
a
2 20.7481 4.9626 5.0187 ,
Donde el signo de es , 0.7481ja 2j
01 . 0.7481 5.0187
2(5.0187)( 0.7481 5.0187) 4.9626u
00.75800.6523
u
0 0.7580 0.6523Tu
Luego:
2 3
2
21 0 0 00 1 0 2 0.7580 . 0 0.7580 0.65230 0 1 0.6523
TuH H I uu
H
2
1 0 00 0.1491 0.98880 0.9888 0.1491
H
Entonces, Satisface
2
600.5005 600.5005. 0.7481 5.0187
4.9626 0H
Se asume:2 2P H
Luego:
2 2 1
2
2
.1 0 0 -400.5009 -600.5005 -800.99940 0.1491 0.9888 . 0 0.7481 0.99870 0.9888 0.1491
0 4.9626 0.0499
-
0
4
0
A P A
A
A
.5009 -600.5005 -800.99940 5.0187 0.09950 0 0.9950
Por lo Tanto: 2 1.
TQ P P
1 0 0 -0.0025 -0.9987 -0.04990 0.1491 0.9888 . -0.9987 0.0050 -0.04980 0.9888 0.1491 -0.0499 -0.0498 0.9975
t
Q
-0.0025 0.0995 0.99500.9987 0.0499 0.00250.0499 0.
9938 0.0
995
Q
2
-400.5009 -600.5005 -800.99
940 5.0187 0.09950 0 0.995
0
R
R A
Ahora tenemos que comprobar que realmente la solución de y están correctamente, por lo tanto haremos lo siguiente para comprobarlo. Como entonces tenemos:
Q R.Q R A
.-0.0025 0.0995 0.9950 -400.5009 -600.5005 -800.99940.9987 0.0499 0.0025 . 0 5.0187 0.09950.0499 0.9938 0.0995 0 0 0.9950
Q R A
1 1 1400 600 80020 25 40
Resolviendo el sistema por Factorización QR (PorHouseholder)
.A x b Como entonces tenemos:.A Q R
.Q Rx b , llamamos entonces .R x y .Q y b
Resolviendo:
1
2
3
.-0.0025 0.0995 0.9950 2000.9987 0.0499 0.0025 . 1260000.0499 0.9938 0
.0995 5950
Q y byyy
Entonces:
1.26140.00360.0008
y
Ahora Resolvemos:
1
2
3
.-400.5009 -600.5005 -800.9994 1.2614
0 5.0187 0.0995 . 0.00360 0 0.9950
0.0008
x yx
R
xx
Entonces: 507080
x
Implementación del algoritmo por Factorización QR (Por Householder)
function [Q R]=hous(A)m=size(A,1)A0=A;Q0=eye(m);for k=1:m-1 fprintf('\n para K=%i',k);a=A(:,k);s=0;for j=k:m s=s+a(j)^2;endn=sqrt(s)for j=1:k-1 a(j)=0;endx=norm(a(k));g=sign(a(k))a(k)=a(k)+g*nu=(1/sqrt(2*n*(x+n)))*aH=eye(m)-2*u*u'A=H*AQ0=H*Q0;endR=A;Q=Q0';end
