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

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