algoritmos de raíz cuadrada refil

DEPARTAMENTO DE ELÉCTRICA Y ELECTRÓNICA

INGENIERÍA ELECTRÓNICA, AUTOMATIZACIÓN Y CONTROL

IDENTIFICACIÓN Y CONTROL ADAPTATIVO

INTEGRANTES:

MARCELO ÁLVAREZ

GABRIEL MONCAYO

MARLON MOROCHO

RAYHRA POZO

PROFESOR:

ING. EDWIN AGUILAR

FECHA:

6 DE FEBRERO DEL 2015

ALGORITMOS DE RAÍZ CUADRADA –REFIL NO RECURSIVO

Álvarez - Moncayo- Morocho - Pozo 2

Tabla de Contenidos

1. TEMA ...................................................................................................................................................................... 3

ALGORITMOS DE RAIZ CUADRADA – IDENTIFICACION REFIL .......................................................... 3

2. OBJETIVOS ........................................................................................................................................................... 3

2.1. OBJETIVO GENERAL ............................................................................................................................. 3

2.2. OBJETIVOS ESPECÍFICO ...................................................................................................................... 3

3. DESARROLLO ..................................................................................................................................................... 3

3.1. MARCO TEORICO: ....................................................................................................................................... 3

3.1.1. ALGORITO DE RAIZ CUADRADA ..................................................................................................... 3

3.1.2. REFIL ............................................................................................................................................................ 4

3.1.2.1. Factorización LU ........................................................................................................................... 4

3.1.3. METODO DE CHOLESKY ..................................................................................................................... 5

3.1.4. PROBLEMA ARITMÉTICO .................................................................................................................. 7

3.1.5. ALGORITO DEL PROBLEMA .............................................................................................................. 8

3.1.5.1. RESULTADOS ALGORITMO ..................................................................................................... 8

3.1.6. EJEMPLO DESCOMPOSICION LU................................................................................................ 9

3.1.6.1. Solución ............................................................................................................................................. 9

3.1.6.2. Comprobación por las Fórmulas......................................................................................... 10

3.1.7. COMANDOS PARA LA DESCOMPOSICION LU ......................................................................... 11

3.1.8. TARJETA STM32F4 DISCOVERY ................................................................................................... 12

3.1.8.1. Características ............................................................................................................................. 12

3.1.8.2. Microncontrolador STM32F407VGT6 ............................................................................. 13

3.1.8.3. Requisitos de hardware .......................................................................................................... 14

3.1.8.4. Requisitos de software ............................................................................................................ 14

4. CONCLUSIONES............................................................................................................................................... 14

5. BIBLIOGRAFÍA ................................................................................................................................................. 15



1. TEMA

ALGORITMOS DE RAIZ CUADRADA – IDENTIFICACION REFIL

2. OBJETIVOS

2.1. OBJETIVO GENERAL

- Analizar y explicar el algoritmo de identificación REFIL, con su respectiva

descomposición y factorización aplicado a un ejemplo práctico.

2.2. OBJETIVOS ESPECÍFICO

- Conocer matemáticamente y por medio de la teoría la comprensión de la

utilización de los algoritmos de raíz cuadrada.

- Analizar la descomposición de matrices LU.

- Comprender el algoritmo de identificación REFIL.

- Elaborar un algoritmo de fácil comprensión para utilizarlo después en una

aplicación física.

3. DESARROLLO

3.1. MARCO TEORICO:

3.1.1. ALGORITO DE RAIZ CUADRADA

Anteriormente se estudiaron los métodos de mínimos cuadrados para la identificación de

los diferentes modelos de estudio. Lo que a futuro con estos algoritmos se estudiaran los

mismos métodos , aunque considerando ahora otras modificaciones que están dirigidas,

sobre todo, a mejorar las propiedades numéricas de los algoritmos de identificación

mínimo – cuadrado.

𝐴𝑥 = 𝑏 (1)

Donde:

A= Es una matriz de dimensión 𝑚𝑥𝑛 , es un vector de dimensión 𝑛𝑥1.

b= Es un vector de dimensión 𝑚𝑥1, ya sabemos además que 𝑚 > 𝑛.



Una matriz A simétrica y positiva definida puede ser factorizada de manera eficiente por

medio de una matriz triangular inferior y una matriz triangular superior.

Para una matriz no singular la descomposición LU nos lleva a considerar una

descomposición de tal tipo A = LU; dadas las condiciones de A, simétrica y definida

positiva, no es necesario hacer pivoteo, por lo que ésta factorización se hace

eficientemente y en un número de operaciones la mitad de LU tomando la forma 𝐴 = 𝐿𝐿𝑇 ,

donde L (la cual podemos "ver" como la raíz cuadrada de A) es una matriz triangular

inferior donde los elementos de la diagonal son positivos.

Para resolver un sistema lineal Ax = b con A simétrica definida positiva y dada su

factorización de Cholesky 𝐴 = 𝐿𝐿𝑇 , primero debemos resolver Ly = b y entonces resolver

𝐿𝑇𝑥 = 𝑦 para lograr x.

3.1.2. REFIL

Consiste en una variante de los algoritmos de raíz cuadrada que está cercana al algoritmo

de identificación de mínimos cuadrados recursivo convencional. Su esencia consiste en

actualizar en cada iteración, no la matriz 𝐶 = 𝑖𝑛𝑣(𝑍𝑇 ∗ 𝑍), sino su raíz cuadrada definida

como una matriz triangular superior, aplicando el algoritmo de Cholevsky para

factorización de matrices LU.

3.1.2.1. Factorización LU

Es un método por medio del cual la matriz A se descompone en el producto de dos

matrices, una triangular inferior y otra triangular superior, así:

Esta factorización en términos generales consiste en: e

Dado un sistema homogéneo:

𝐴𝑥 = 𝑏

Si la matriz A es de rango completo se puede factorizar de tal manera que:

𝐴 = 𝐿 ∗ 𝑈

Entonces:

𝐴𝑋 = 𝐵 → 𝐿𝑈. 𝑋 = 𝐵, 𝑑𝑜𝑛𝑑𝑒

{ 𝐿𝑌 = 𝐵 → 𝑌

{𝑈𝑋 = 𝑌 → 𝑋



Donde L y U=L’ son matrices triangulares inferiores y superiores respectivamente.

Así, entonces el método consiste en factorizar la matriz A y luego despejar de cada

sistema los vectores Y, X en forma consecutiva.

Por lo tanto:

[ 𝑙1,1 0 0 0 0

𝑙2,1 𝑙2,2 0 0 0

𝑙3,1 𝑙3,2 𝑙3,3 0 0

𝑙4,1 𝑙4,2 𝑙4,3 𝑙4,4 0

𝑙5,1 𝑙5,2 𝑙5,3 𝑙5,4 𝑙5,5]

[ 𝑙1,1 𝑙2,1 𝑙3,1 𝑙4,1 𝑙5,1

0 𝑙2,2 𝑙3,2 𝑙4,2 𝑙5,2

0 0 𝑙3,3 𝑙4,3 𝑙5,3

0 0 0 𝑙4,4 𝑙5,4

0 0 0 0 𝑙5,5]

=

[ 𝑎1,1 𝑎1,2 . . 𝑎1,5

𝑎2,1 𝑎2,2 . . 𝑎2,5

. . . . .

. . . . .𝑎5,1 𝑎5,2 𝑎5,3 𝑎5,4 𝑎5,5]

Existen diferentes métodos comunes de obtener la factorización LU:

1. Eliminación Gaussiana

2. Calculo directo:

a. Forma de Doolittle

b. Forma Crout

c. Forma Cholevsky

En este documento se analiza el método de Cholevsky.

3.1.3. METODO DE CHOLESKY

Este método de factorizar la matriz A requiere que los elementos correspondientes a la

diagonal de L y U sean iguales, lo cual es muy útil cuando se lo aplica para matrices

definidas positivas simétricas.

[ 𝛼1,1 0 0 0 0

𝑙2,1 𝛼2,2 0 0 0

𝑙3,1 𝑙3,2 𝛼3,3 0 0

𝑙4,1 𝑙4,2 𝑙4,3 𝛼4,4 0

𝑙5,1 𝑙5,2 𝑙5,3 𝑙5,4 𝛼5,5]

[ 𝛼1,1 𝑢2,1 𝑢3,1 𝑢4,1 𝑢5,1

0 𝛼2,2 𝑢3,2 𝑢4,2 𝑢5,2

0 0 𝛼3,3 𝑢4,3 𝑢5,3

0 0 0 𝛼4,4 𝑢5,4

0 0 0 0 𝛼5,5]

En tal caso la matriz preserva la simetría y produce una factorización

𝑳 = 𝑼𝑻

Si reemplazamos tendremos que:

𝐴 = 𝐿 ∗ 𝑈

𝑨 = 𝑼 ∗ 𝑼𝑻



Una variante de la factorización de Cholesky es de la forma 𝐴 = 𝑅𝑇𝑅 , donde R es una

matriz triangular superior, en algunas aplicaciones se desea ver la matriz en esa forma y

no de otra.

Para encontrar la factorización 𝐴 = 𝐿𝐿𝑇 , bastaría ver la forma de L y observar las

ecuaciones que el producto derecho nos conduce al igualar elementos:

[

𝑎11 𝑎12 ⋯ 𝑎1𝑛

𝑎21 𝑎22 ⋯ 𝑎2𝑛

⋮ ⋮ ⋱ ⋮𝑎𝑛1 𝑎𝑛2 ⋯ 𝑎𝑛𝑛

] = [

𝐼11 0 ⋯ 0𝐼21 𝐼22 ⋯ 0⋮ ⋮ ⋱ ⋮

𝐼𝑛1 𝐼𝑛2 ⋯ 𝐼𝑛𝑛

] [

𝐼11 𝐼12 ⋯ 𝐼1𝑛

0 𝐼22 ⋯ 𝐼2𝑛

⋮ ⋮ ⋱ ⋮0 0 ⋯ 𝐼𝑛𝑛

]

Así obtendríamos que:

𝑎11 = 𝐼112 → 𝐼11 = √𝑎11

𝑎21 = 𝐼21𝐼11 → 𝐼12 =𝑎21

𝐼11, … . . 𝐼𝑛1 =

𝑎𝑛1

𝐼11

𝑎22 = 𝐼212 + 𝐼22

2 → 𝐼22 = √(𝑎22 − 𝐼212

𝑎32 = 𝐼31𝐼21 + 𝐼32𝐼22 → 𝐼32 =(𝑎32 − 𝐼31𝐼21)

𝐼22, 𝑒𝑡𝑐

De manera general, para 𝑖 = 1, … . . , 𝑛 𝑦 𝑗 = 𝑖 + 1,… . , 𝑛 :

𝑔𝑗𝑗 = √𝑎𝑗𝑗 − ∑ 𝑔𝑗𝑘2

𝑚

𝑘=𝑗+1

𝑔𝑖𝑗 =𝑎

𝑖𝑗−∑ 𝑔𝑖𝑘∗𝑔𝑗𝑘𝑗+1𝑘=𝑚

𝑔𝑗𝑗

Se debe tomar en cuenta que el valor de los elementos bajo la diagonal de la matriz debe

ser igual a 0.

Ahora bien, ya que A es simétrica y definida positiva, podemos asegurar que los elementos

sobre la diagonal de L son positivos y los restantes elementos reales desde luego.



3.1.4. PROBLEMA ARITMÉTICO

Resolver el siguiente sistema de ecuaciones lineales usando el método de Cholesky

A =

97922555

2255515

55156

Solución:

En el método de Cholesky el primer paso es encontrar la matriz L usando las fórmulas

ii

i

j

kjijki

kil

lla

l

1

1

1

1

2k

j

kjkkkk lal

La primera ecuación se usa para elementos fuera de la diagonal y la segunda para

elementos en la diagonal principal.

Entonces.

61111 al = 2.4495 4495.2

15

11

21

21 l

al = 6.1237

4495.2

55

11

31

21 l

al = 22.454 Ya sabemos que l12 = 0

22

212222 1237.655 lal = 4.1833

1833.4

)454.22)(1237.6(55

22

312132

32

l

llal = 20.916

De igual forma l13 = l23 = 0 y

)916.20454.22(979)( 222

32

2

313333 llal = 6.1106

La matriz L es igual a



1106.6916.20454.22

01833.41237.6

004495.2

L

En el método de Cholesky U = LT

1106.600

916.201833.40

454.221237.64495.2

U

3.1.5. ALGORITO DEL PROBLEMA

M=[6 15 55; 15 55 225; 55 225 979]; n = length( M ); L = zeros( n, n );

for i=1:n %Formula para índices iguales L(i, i) = sqrt( M(i, i) - L(i, end)*L(i, end)' ); %Formula para índices desiguales for j=(i + 1):n L(j, i) = ( M(j, i) - L(i, end)*L(j, end)' )/L(i, i); end

end L % Impresión matriz descompuesta triangular inferior L U=L' %Impresión matriz descompuesta triangular superior U

3.1.5.1. RESULTADOS ALGORITMO



3.1.6. EJEMPLO DESCOMPOSICION LU

En cierto sistema se miden los siguientes datos en el dominio del tiempo.

k 0 1 2 3 4 5 6 7 8 9 10 u 0

1 1.1 1.32 0.918 1.102 1.8491 2.2348 2.2122 2.0675 1.9884

y 1

0 1 0 1 1 1 1 1 1 1

Encontrar la respectiva descomposición LU de la matriz de mediciones para su

identificación mediante el desarrollo de un algoritmo en Matlab y compare

utilizando el método analítico y el comando chol de Matlab:

3.1.6.1. Solución

clear all; clc; %Entrada y salida del sistema a identificar y=[0 1 1.1 1.32 0.918 1.102 1.8491 2.2348 2.2122 2.0675 1.9884]; u=[1 0 1 0 1 1 1 1 1 1 1];

%Obtención de matrices de mediciones y de parámetros for i=1:11 ZZ(i,:)=[-y(i+1) -y(i) u(i+1) u(i)] YYT(i)=y(i+2); end

% Descomposición de la matriz de mediciones mediante algoritmo Z=ZZ'*ZZ n = length( Z ); L = zeros( n, n );

for i=1:n L(i, i) = sqrt( Z(i, i) - L(i, end)*L(i, end)' );

for j=(i + 1):n L(j, i) = ( Z(j, i) - L(i, end)*L(j, end)' )/L(i, i); end

end

%Identificación del sistema mediante el uso de nuestro algoritmo de LU L'; U=L'; P=inv(L*U)*ZZ'*YYT';

% Descomposición de la matriz de mediciones mediante comando chol U1=chol((ZZ'*ZZ));

%Identificación del sistema mediante el uso del comando chol de Matlab L1=U';



P1=inv(L1*U1)*ZZ'*YYT';

Donde:

La matriz a descomponer:

Comparación de resultados del algoritmo mediante comando chol de Matlab:

3.1.6.2. Comprobación por las Fórmulas

Que es la matriz que se deberá descomponer

Se usarán las siguientes fórmulas

ii

i

j

kjijki

kil

lla

l

1

1 y

1

1

2k

j

kjkkkk lal

Procedimiento:

Columna 1

𝑙11 = √𝑎11 = √27.5451 = 5.2483

𝑙21 =𝑎21

𝑙11=

24.574

5.2483= 4.6822

𝑙31 =𝑎31

𝑙11=

−13.4720

5.2483= −2.5669

𝑙41 =𝑎41

𝑙11=

−13.7740

5.2483= −2.6244

Columna 2



𝑙12 = 0

𝑙22 = √𝑎22 − (𝑙21)2 = √23.5414 − (4.6822)2 = 1.2917

𝑙32 =𝑎32 − 𝑙21 ∗ 𝑙31

𝑙22=

−12.7036 − (4.6822)(−2.5659)

1.2917= 0.5302

𝑙42 =𝑎42 − 𝑙21 ∗ 𝑙41

𝑙22=

−11.4836 − (4.6822)(−2.6244)

1.2917= 0.6227

Columna 3

𝑙13 = 0

𝑙23 = 0

𝑙33 = √𝑎33 − ((𝑙31)2 + (𝑙32)

2) = √8 − ((−2.5669)2 + (−0.5302)2) = 1.0654

𝑙43 =𝑎43 − ((𝑙31 ∗ 𝑙41) + (𝑙32 ∗ 𝑙42))

𝑙33=

6 − ((−2.5669)(−2.6244) + (−0.5302)(0.6227))

1.0654

= 0.3799

Columna 4

𝑙41 = 0

𝑙42 = 0

𝑙43 = 0

𝑙44 = √𝑎44 − ((𝑙41)2 + (𝑙42)

2 + (𝑙43)2) = √8 − ((−2.6244)2) + (0.6227)2 + (−0.3799)2

= 0.7619

Matriz

𝐿 = (

5.2483 0.0000 0.0000 0. 00004.6822

−2.5669−2.6244

1.2917 0.0000 0. 00000.5302 1.0654 0.00000.6227 −0.3799 0.7602

)

3.1.7. COMANDOS PARA LA DESCOMPOSICION LU

function [L,U] = lu(A)



Esta función descompone una matriz A, cuadrada e invertible, en dos factores L y U, L

triangular inferior y U triangular superior, tales que se cumple A=L*U.

function y = tri_sup (A,x)

Dada una matriz triangular superior A y un vector columna x, esta función resuelve el

sistema de ecuaciones lineales triangular superior A*y = x.

function y = tri_inf (A,x)

Dada una matriz triangular inferior A y un vector columna x, esta función resuelve el

sistema de ecuaciones lineales triangular inferior A*y = x.

3.1.8. TARJETA STM32F4 DISCOVERY

La placa de evaluación STM32F4 Discovery de ST Microelectronics es una entrenadora de

bajo costo para evaluar el alcance de microcontroladores ARM STM32 de 32 bit Cortex-

M4.

Figura 1.Tarjeta STM32F4 Discovery

3.1.8.1. Características

La placa STM32F4 Discovery ofrece las siguientes características:

- Microcontrolador STM32F40VGT6 con 1 MB de memoria flash, 192 KB de RAM,

encapsulado LQFP100.

- ST-LINK/V2 incorporado con selector usar el kit como un ST-LINK/V2

independiente (con conector SWD para programación y depuración).

- Fuente de alimentación: a través del bus USB o desde una fuente de alimentación

externa de 5V.



- Sensor de movimiento ST MEMS LIS302DL, acelerómetro con salida digital de 3

ejes.

- Sensor de audio ST MEMS MP45DT02, micrófono digital omnidireccional.

- Audio DAC CS43L22 con controlador integrado de altavoz clase D.

- Ocho LEDs:

Figura 2. Diseño físico de tarjeta STM32F4 Discovery

3.1.8.2. Microncontrolador STM32F407VGT6

Este procesador ARM Cortex-M4 32 bit con FPU tiene 210 DMIPS, 1 MB Flash, 196 KB

RAM, USB OTG HS/FS, Ethernet, 17 TIMs y 3 ADCs.

Figura 1 3. STM3F407VGT6

Este dispositivo proporciona las siguientes características:

- Diseñado para un alto rendimiento y muy elevada transferencia de datos,

acelerador ART, 32-bit.

- Eficiencia energética, ultra-bajo consumo de energía, RTC˂1 µA en modo VBAT, de

3,6 V hasta 1,7 V VD.



- Integración máxima: Hasta 1Mbyte de memoria Flash on-chip, 192 Kbytes de

SRAM

- Los periféricos innovadores que ofrecen nuevas posibilidades para conectar y

comunicar datos a alta velocidad, así como mayor precisión debido a su alta

resolución.

Figura 4. Diagrama de bloques del STM32F407VGT6

3.1.8.3. Requisitos de hardware

La única pieza de hardware necesaria para empezar a utilizar la entrenadora es un cable

de conexión USB A a mini-B y un puerto USB disponible en su PC.

3.1.8.4. Requisitos de software

Será necesaria una plataforma de Windows para ejecutar las herramientas de desarrollo

para microcontroladores STM32.

4. CONCLUSIONES

- Se comprobó que el algoritmo desarrollado cumple con las características de la

factorización de Cholesky.

- Se realizó la respectiva verificación con el algoritmo chol de Matlab para

comprobar que el algoritmo realizado es efectivo y su resultado es igual.



5. BIBLIOGRAFÍA

- https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/04LinearAlgebra/chole

sky/

- http://rosettacode.org/wiki/Cholesky_decomposition.

- Rodriguez Ramírez, D., & Alamo Cantarero, T. (s.f.). Ingeniería de Control:

Identificación mediante el método de los mínimos cuadrados. Obtenido de

http://www.control-

class.com/Tema_2/Slides/Tema_2_IdentificacionMinimosCuadrados.pdf

- www.disca.upv.es/aperles/.../guia_iniciacion_STM32F4_discovery.pdf

http://rosettacode.org/wiki/Cholesky_decomposition

algoritmos de raíz cuadrada refil

Documents