PDF de programación - Algunos algoritmos para matrices de Toeplitz

Imágen de pdf Algunos algoritmos para matrices de Toeplitz

Algunos algoritmos para matrices de Toeplitzgráfica de visualizaciones

Actualizado el 21 de Marzo del 2018 (Publicado el 19 de Noviembre del 2017)
1.195 visualizaciones desde el 19 de Noviembre del 2017
136,1 KB
6 paginas
Creado hace 3a (30/08/2016)
Algunos algoritmos para matrices de Toeplitz

Estos apuntes est´an escritos por varios estudiantes de la ESFM del IPN, bajo la direc-
ci´on del profesor Egor Maximenko. Participaron Jocelyn Hern´andez, Jareth Le´on, Mario
Guzm´an Silverio, Maria de los Angeles Isidro P´erez, Dar´ıo Couti˜no Aquino, Rodrigo Ga-
briel Castillo Gonz´alez, Andrea Alejandra Rend´on Pe˜na, Luis Enrique Villanueva L´opez.

En estos apuntes se estudian algunos algoritmos num´ericos para las matrices de Toe-

plitz. Por ejemplo, para n = 4, son matrices de la forma

 a1

b4
b2
b3
b3
a2 a1
b2
a3 a2 a1
b2
a4 a3 a2 a1

 .

´Indice

1. Construcci´on de matrices de Toeplitz

2. Convoluci´on discreta c´ıclica

3. Matrices circulantes

4. Multiplicaci´on r´apida de una matriz de Toeplitz por un vector

2

4

5

6

1

1. Construcci´on de matrices de Toeplitz

Una matriz cuadrada se llama matriz de Toeplitz si sus diagonales (paralelas a la
diagonal principal) son constantes. Una matriz de Toeplitz se puede definir por su primera
columna y su primer rengl´on.

1 Ejemplo. Las matrices de Toeplitz de orden 4 son de la siguiente forma:

 a1

b4
b3
b2
b3
a2 a1
b2
b2
a3 a2 a1
a4 a3 a2 a1

 .

Los sistemas de ´algebra computacional MATLAB y Wolfram Mathematica tienen fun-
ciones que generan matrices de Toeplitz a partir de los vectores a y b. En estos sistemas
se supone que el vector b es de la misma longitud que el vector a, con b1 = a1. Nosotros
seguimos el mismo convenio.
2 Definici´on. Sea n ∈ {1, 2, . . . ,} y sean a, b ∈ Rn, con a1 = b1. La matriz de Toeplitz
generada por los vectores a y b es una matriz cuadrada A de orden n cuya entrada (j, k)
est´a definida mediante la regla

(cid:40)

Aj,k =

aj−k+1
bk−j+1

si j ≥ k;
si k > j.

3 Algoritmo (generaci´on de una matriz de Toeplitz en forma completa por su primera
columna y su primer rengl´on). Dados dos vectores a, b ∈ Rn la siguiente funci´on construye
la matriz de Toeplitz en la forma completa.

function [T] = toeplitzmatrix(a, b),

n = length(a);
T = zeros(n, n);
for j = 1 : n,

for k = 1 : j,

T(j, k) = a(j - k + 1);

endfor
for k = (j + 1) : n,

T(j, k) = b(k - j + 1);

endfor

endfor

endfunction

2

Para evitar ciclos anidados notamos que cada columna de la matriz se compone de

una parte del vector a y una parte del vector b invertido:

(cid:21)

(cid:20) a1

a2

a(??? :???) =

b(??? : −1 :???) =

,

 .

 b5

b4
b3
b2



T =

 ,

b5
b4
b3
b2
a1
b6
b4
b5
b3
a2 a1
b2
b3
a3 a2 a1
b2
b4
a4 a3 a2 a1
b2
b3
a5 a4 a3 a2 a1
b2
a6 a5 a4 a3 a2 a1

Escrimos los comandos para rellenar las columnas 3–6 de la matriz T :

# column 3 of T:
T(1 : 2, 3) = b(3 : -1 : 2);
T(3 : 6, 3) = a(1 : 4);
# column 4 of T:
T(1 : 3, 4) = b(4 : -1 : 2);
T(4 : 6, 4) = a(??? : ???);
# column 5 of T:
T(1 : 4, 5) = b(??? : -1 : ???);
T(5 : 6, 5) = a(??? : ???);
# column 6 of T:
T(1 : 5, 6) = b(??? : -1 : ???);
T(6 : 6, 6) = a(??? : ???);

La misma idea funciona tambi´en para las columnas 1 y 2 de la matriz T . En el caso
de fragmentos vac´ıos no se realizan ningunas acciones, tampoco se generan errores. Ge-
neralizando los comandos anteriores llegamos a una versi´on m´as eficiente del algoritmo
anterior:

4 Algoritmo (generaci´on de una matriz de Toeplitz en forma completa por su primera
columna y su primer rengl´on, usando operaciones vectoriales). Dados dos vectores a, b ∈
Rn la siguiente funci´on construye la matriz de Toeplitz en la forma completa.

function [T] = toeplitzmatrix(a, b),

n = length(a);
T = zeros(n, n);
for k = 1 : n,

T(??? : ???, k) = a(??? : ???);
T(??? : ???, k) = b(??? : -1 : ???);

endfor

endfunction

3

2. Convoluci´on discreta c´ıclica
5 Ejemplo. Sean a, b ∈ C3:

Entonces su convoluci´on discreta c´ıclica es el vector

 a1
 b1
 ,
 a1b1 + a2b3 + a3b2

a2
a3

b2
b3

b =

 .
 .

???
???

a =

a ∗ b =

(a ∗ b)j =???.

ωn = e− 2πi

n

Fn =

ω(j−1)(k−1)

n

(cid:104)
 ω???

ω???
ω???

3

3

3

(cid:105)n

.

j,k=1

 .

3

ω???
ω???
ω???

3

3

3

ω???
ω???
ω???

3

3

F3 =

6 Definici´on (convoluci´on discreta c´ıclica de dos vectores). Dados dos vectores a, b ∈ Cn,
su convoluci´on discreta c´ıclica es un vector a ∗ b ∈ Cn cuya j-´esima componente es

7 Definici´on (transformada discreta de Fourier). Denotemos por ωn al n´umero

y definimos la matriz Fn mediante la regla

El operador lineal x (cid:55)→ Fnx se llama la transformada discreta de Fourier.
8 Ejemplo (matriz de la transformada discreta de Fourier de orden 3).

9 Definici´on (transformada r´apida de Fourier). Existe un algoritmo, llamado la trans-
formada r´apida de Fourier, para calcular Fnx con solamente Cn log2 n operaciones, donde
C es una constante. En el lenguaje de MATLAB la transformada r´apida de Fourier se
puede calcular con el comando fft(x), y la transformada inversa se puede calcular con
ifft(x).
10 Definici´on (producto de dos vectores por componentes). Dados a, b ∈ Cn, denotemos
por a (cid:12) b su producto por componentes:

En el lenguaje de MATLAB el producto a (cid:12) b se puede calcular como a .* b.
11 Teorema (teorema de la convoluci´on discreta c´ıclica). Sean a, b ∈ Cn. Entonces

Fn(a ∗ b) = (Fna) (cid:12) (Fnb).

(cid:105)n

a (cid:12) b =

ajbj

.

j=1

(cid:104)

4

3. Matrices circulantes
12 Ejemplo. Sean a, b ∈ C3. La matriz circulante generada por a es

a2 a1 a3
a3 a2 a1
Notamos que el producto C(a)b es lo mismo que a ∗ b:

C(a) =

 a1 a3 a2

a2 a1 a3
a3 a2 a1

C(a)b =

 a1 a3 a2
 b1
 =

b2
b3

 .
 ???

???
???

 = a ∗ b.

13 Definici´on (matriz circulante generada por un vector). Dado un vector a ∈ Cn,
denotamos por C(a) a la matriz circulante de tama˜no n× n, con la entrada (j, k) definida
mediante la siguiente regla:

C(a)j,k =???.

1 Proposici´on (producto de una matriz circulante por un vector). Sean a, b ∈ Cn.
Entonces

C(a)b = a ∗ b = F −1

n (Fn(a) (cid:12) Fn(b)) .

14 Algoritmo (multiplicaci´on r´apida de una matriz circulante por un vector). Dados dos
vectores a, b ∈ Cn, la siguiente funci´on calcula el producto C(a)b usando la transformada
r´apida de Fourier.

function [result] = myfastconv(a, b):

result = ???;

endfunction

5

4. Multiplicaci´on r´apida de una matriz de Toeplitz

por un vector

Notamos que cada matriz de Toeplitz 4× 4 se puede extender a una matriz circulante

de tama˜no 9 × 9:

 a1

b4
b3
b2
b3
b2
a2 a1
a3 a2 a1
b2
a4 a3 a2 a1

 (cid:55)→



b4
b3
b2
a1

b3
b2
a1
a2

b2
a1
a2
a3

??? ??? ??? ??? ???
a1
??? ??? ??? ??? ???
a2
??? ??? ??? ??? ???
a3
??? ??? ??? ??? ???
a4
??? ??? ??? ??? ??? ??? ??? ??? ???
??? ??? ??? ??? ??? ??? ??? ??? ???
??? ??? ??? ??? ??? ??? ??? ??? ???
??? ??? ??? ??? ??? ??? ??? ??? ???
??? ??? ??? ??? ??? ??? ??? ??? ???



.

Algunas entradas de la matriz extendida pueden tener valores arbitrarios; en esas entradas
se recomienda poner 0. Notamos que la primera columna de la matriz extendida contiene
el vector a completo, el vector b casi completo (las entradas de ??? a ??? en el orden
invertido), y algunas entradas cero.
M´as general, cada matriz de Toeplitz n × n se puede extender a una matriz circulante de
tama˜no m × m, si

m ≥??? (una expresi´on misteriosa en t´erminos de n).

15 Algoritmo (extensi´on de una matriz de Toeplitz a una matriz circulante). Sean
a, b ∈ Rn y sea m ∈ {1, 2, . . .} tal que m > 2015n ???. La siguiente funci´on construye un
vector g ∈ Rm su submatriz ubicada en la intersecci´on de los primeros n renglones y las
primeras n columnas de la matriz C(g) coincide con la matriz de Toeplitz asociada a los
vectores a y b.

function [g] = extendtoeplitztocirculant(a, b, m),

n = length(a);
g = ???;
endfunction

16 Algoritmo (multiplicaci´on r´apida de una matriz de Toeplitz por un vector). Sean
a, b, x ∈ Rn La siguiente funci´on multiplica la matriz de Toeplitz generada por a y b por
el vector x, usando la transformada r´apida de Fourier.

function [result] = fasttoeplitzbyvector(a, b, x),

result = ???;

endfunction

6
  • Links de descarga
http://lwp-l.com/pdf7582

Comentarios de: Algunos algoritmos para matrices de Toeplitz (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad