ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

NGUYỄN THÙY DUNG

PHƯƠNG PHÁP BIẾN ĐỔI FOURIER
NHANH GIẢI PHƯƠNG TRÌNH
PARABOLIC TUYẾN TÍNH

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2019


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
-------------------------------

NGUYỄN THÙY DUNG

PHƯƠNG PHÁP BIẾN ĐỔI FOURIER
NHANH GIẢI PHƯƠNG TRÌNH
PARABOLIC TUYẾN TÍNH
Chuyên ngành: Toán ứng dụng
Mã số
: 8 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

1.2.2. Hàm xung . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.3. Mẫu dạng sóng . . . . . . . . . . . . . . . . . . . . 17
1.3. Biến đổi Fourier rời rạc . . . . . . . . . . . . . . . . . . . . 18
1.4. Biến đổi Fourier nhanh . . . . . . . . . . . . . . . . . . . . 20
1.4.1. Công thức ma trận . . . . . . . . . . . . . . . . . . 21
1.4.2. FFT với các ví dụ trực giác . . . . . . . . . . . . . 21
1.4.3. Đồ thị dòng tín hiệu . . . . . . . . . . . . . . . . . 25
1.4.4. Thuật toán FFT . . . . . . . . . . . . . . . . . . . 26
1.4.5. Nhân tử hóa W p . . . . . . . . . . . . . . . . . . . 28


2

Chương 2

Ứng dụng phương pháp Fourier nhanh giải phương

trình parabolic tuyến tính

30

2.1. Công thức sai phân hữu hạn . . . . . . . . . . . . . . . . . 30
2.2. Bài toán giá trị biên ban đầu rời rạc . . . . . . . . . . . . 32
2.3. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . 34

Kết luận

40

Tài liệu tham khảo



4

Chương 2 trình bày một ứng dụng của biến đổi FFT trong việc tìm
nghiệm số của phương trình truyền nhiệt tuyến tính hai chiều. Cũng
trong chương này có trình bày một vài ví dụ số minh họa cho tính hữu
hiệu của thuật toán đề xuất.
Luận văn này được hoàn thành với sự hướng dẫn và chỉ bảo tận tình
của TS. Nguyễn Thị Ngọc Oanh tự đáy lòng mình, em xin được bày tỏ
lòng biết ơn sâu sắc đối với sự quan tâm, động viên và sự chỉ bảo hướng
dẫn của cô.
Em xin gửi lời cảm ơn tới các thầy cô trong trường Đại học Khoa học
- Đại học Thái Nguyên, nhất là các thầy cô trong Khoa Toán - Tin, đã
tận tình giảng dạy tạo điều kiện cho em trong suốt quá trình học tập tại
trường. Đồng thời tôi xin gửi lời cảm ơn tới tập thể lớp Cao học Toán
K11 trường Đại học Khoa học đã giúp đỡ tôi trong quá trình hoc tập
tại trường.
Em xin trân thành cảm ơn!
Thái Nguyên, tháng 4 năm 2019
Tác giả

Nguyễn Thùy Dung


5

Chương 1

Giới thiệu về phương pháp Fourier

thường sẽ biểu thị cho hàm thời gian; biến đổi Fourier của hàm thời gian
này sẽ được biểu thị bằng chữ cái in hoa.


6

Nói chung, biến đổi Fourier là một đại lượng phức:
H(f ) = R(f ) + jI(f ) = |H(f )|eiθ(f )

(1.2)

trong đó R(f ) là phần thực, I(f ) là phần ảo của biến đổi Fourier; |H(f )|
là độ lớn hoặc phổ Fourier của h(t) và được cho bởi

R2 (f ) + I 2 (f );

θ(f ) là góc pha của biến đổi Fourier và được cho bởi tan−1 [I(f )/R(f )].
Ví dụ 1.1 Cho hàm

1,
h(t) =
0,

−T ≤ t ≤ T,
|t| > T.

Khi đó biến đổi Fourier của h(t) được cho bởi
T

e−if t = −

βe
0

−αt −jf t

e

e−(α+jf )t dt

=β
0

β
−β −(α+jf )t ∞
=
e
|0 =
α + jf
α + jf
βα
fβ
= 2
−
j
α + f2
α2 + f 2
β
−1
=
ej tan [f /α] .

Biến đổi Fourier ngược

Biến đổi Fourier ngược được định nghĩa như sau
∞

H(f )ei2πf t df

h(t) =
−∞

(1.3)


8

Phép biến đổi Fourier ngược (1.3) cho phép xác định hàm thời gian từ
phép biến đổi Fourier của nó. Nếu các hàm h(t) và H(f ) được xác định
từ công thức (1.1) và (1.3) thì chúng được gọi là cặp biến đổi Fourier
và ta sử dụng ký hiệu dưới đây để xác định mối quan hệ này
h(t) ⇔ H(f ).
1.1.3.

(1.4)

Sự tồn tại của tích phân Fourier

Định lý 1.1 Nếu h(t) khả tích theo nghĩa
∞

|h(t)|dt < ∞

−i2πf t

dt =

∞

x(t)e

−i2πf t

−∞

= X(f ) + Y (f ).

y(t)e−i2πf t dt

dt +
−∞


9

Khi đó có cặp biến đổi Fourier sau
x(t) + y(t) ⇔ X(f ) + Y (f ).
Tính chất 2. Tính đối xứng
Nếu h(t) ⇔ H(f ) thì H(t) ⇔ h(−f ).
Chứng minh. Thật vậy, từ công thức (1.3) ta có
∞

H(f )e−i2πf t df.

−∞

1 ∞
h(t )e−i2π(f /k)t dt
k −∞
1 f
= H( ).
k k
=

Như vậy với k > 0 ta có
1 f
h(kt) ⇔ H( ).
k k
Tính chất 4. Nhân với tần số
1
Nếu h(t) ⇔ H(f ) thì h(t/k) ⇔ H(kf ).
k
Chứng minh. Sử dụng công thức biến đổi Fourier ngược và đặt f = kf
ta có
∞

∞

H(kf )e
−∞

i2πf t

H(f )ei2π(f /k)t df /k


dt =
−∞

−∞

∞

h(s)e−i2πf s ds

= e−i2πf t0
−∞
−i2πf t0

=e

H(f ).

Tính chất 6. Dịch chuyển tần số
Với f0 là hằng số,
nếu h(t) ⇔ H(f ) thì ei2πtf0 h(t) ⇔ H(f − f0 ).
Chứng minh. Sử dụng công thức biến đổi Fourier ngược và đặt s =
f − f0 ta có
∞

∞

H(f − f0 )e

i2πf t


trong đó H ∗ (f ) là liên hợp của H(f ), tức là nếu H(f ) = R(f ) + iI(f )
thì H ∗ (f ) = R(f ) − iI(f ).


11

Chứng minh. Ta có
∞
∗

−i2πf t

H (f )e

∞

∗

df

=

−∞

∞

R(f )e

−i2πf t

∞

−i

∗

[R(f ) sin(2πf t) + I(f ) cos(2πf t)]df
−∞
∞

[R(f ) cos(2πf t) − I(f ) sin(2πf t)]df

=
−∞
∞

[R(f ) sin(2πf t) + I(f ) cos(2πf t)]df

+i
−∞
∞

[R(f ) + iI(f )][cos(2πf t) sin(2πf t)]df

=
−∞
∞

H(f )ei2πf t df.


=

he (t) sin(2πf t)dt
−∞

he (t) cos(2πf t)dt = Re (f ).
−∞

Dễ thấy Re (f ) là hàm chẵn.
Tính chất 9. Biến đổi Fourier của hàm lẻ
Nếu ho (t) là hàm lẻ, tức là ho (t) = −ho (−t) thì biến đổi Fourier cũng


12

là một hàm lẻ và ta có
∞

ho (t) ⇔ Io (f ) = −i

ho (t) sin(2πf t)dt.
−∞

Chứng minh. Ta có
∞

ho (t)e−i2πf t dt

H(f ) =
−∞


∞

[hr (t) sin(2πf t) − hi (t) cos(2πf t)]dt.

I(f ) = −
−∞

Chứng minh. Ta có
∞

[hr (t) + ihi (t)]e−i2πf t dt

H(f ) =
−∞
∞

=

[hr (t) cos(2πf t) + hi (t) sin(2πf t)]dt
−∞
∞

−i

[hr (t) sin(2πf t) − hi (t) cos(2πf t)]dt
−∞

= R(f ) + iI(f ).
1.1.5.

e−t , t ≥ 0
h(t) =
0, t < 0


sin t, 0 ≤ t ≤
và x(t) =
0, ngược lại

π
2

Khi đó nếu sử dụng công thức (1.6) ta nhận được
∞

x(τ )h(t − τ )dτ

y(t) =
−∞






t
−(t−τ )
,
0 sin(τ )e


2

=

π
2

Ta có định lý dưới đây về tích chập.
Định lý 1.3 Nếu H(f ), X(f ) tương ứng là các biến đổi Fourier của
h(t), x(t) thì tích chập y(t) = h(t)∗x(t) có biến đổi Fourier là H(f )X(f ),
tức là ta có cặp biến đổi Fourier
h(t) ∗ x(t) ⇔ H(f )X(f ).

(1.8)

Chứng minh. Từ công thức (1.1), ta có
∞

Y (f ) =

∞

y(t)e
−∞
∞

=

−i2πf t
∞


dt =

−∞

−∞

= e−i2πf τ H(f ).
Do đó
∞

x(τ )e−i2πf τ H(f )dτ = H(f )X(f ).

Y (f ) =
−∞

1.2.
1.2.1.

Hàm tuần hoàn và hàm xung
Hàm tuần hoàn

Định nghĩa 1.2 Chuỗi Fourier của hàm tuần hoàn y(t) với chu kỳ T0
được cho bởi công thức
∞

a0
y(t) =
+
[an cos(2πnt/T0 ) + bn sin(2πnt/T0 )].

cos(2πnt/T0 )dt = (ei2πnt/T0 + e−i2πnt/T0 )
2
1
sin(2πnt/T0 )dt = (ei2πnt/T0 − e−i2πnt/T0 )
2i
biểu diễn (1.9) có thể được viết lại như sau
a0 1
y(t) =
+
2
2

∞
i2πnt/T0

(an − ibn )e
n=1

1
+
2

∞

(an + ibn )e−i2πnt/T0 . (1.12)
n=1

Để đơn giản kí hiệu, với những giá trị n âm, từ công thức (1.10) và




2
T0

T0 /2

y(t) sin(−2πnt/T0 )dt
−T0 /2
T0 /2

y(t) sin(2πnt/T0 )dt
−T0 /2

= −bn , n = 1, 2, 3, . . . .
Do đó
∞

n=−1

an e

−i2πnt/T0

an ei2πnt/T0

(1.13)

ibn ei2πnt/T0 .

(1.14)


trong đó

a0 /2, n = 0,
αn =
1/2(a − ib ), n = ±1, ±2, . . . .
n
n
1
=
T0

T0 /2

y(t)e−i2πnt/T0 dt, n = 0, ±1, ±2, . . . .

(1.16)

−T0 /2

Ví dụ 1.4 Xác định chuỗi Fourier của hàm tuần hoàn tam giác được
cho như hình dưới đây


16

Hình 1.2: Hàm tuần hoàn tam giác

Vì hàm y(t) là hàm chẵn, theo công thức (1.16) ta có
1 T0 /2



T
 0
= π24T n12 , n = 1, 3, 5, . . .
0




0, n = 2, 4, , 6, . . . .

1
T0

T0 /2 2
( T0
0

−

4
t) cos(i2πnt/T0 )dt
T02

Do đó
y(t) =
1.2.2.

1


∞

δ(t)φ(t)dt = φ(0).

(1.19)

δ(t − t0 )φ(t)dt = φ(t0 ).

(1.20)

−∞

Tính chất 2.

∞
−∞

Tính chất 3.
∞

δ(at)φ(t)dt =
−∞

1
|a|

∞

δ(t)φ(t/a)dt.

Định nghĩa 1.4 (Mẫu dạng sóng) Nếu hàm h(t) là liên tục tại t =
T , khi đó một mẫu của h(t) tại thời điểm T được cho bởi
ˆ = h(t)δ(t − T ) = h(T )δ(t − T )
h(t)

(1.24)

trong đó tích được hiểu theo (1.23). Hàm xung xảy ra tại thời điểm T sẽ
có biên độ bằng hàm h(t) tại thời điểm T . Nếu h(t) liên tục tại t = nT
với n = 0, ±1, ±2, . . . , khi đó
∞

ˆ =
h(t)

h(nT )δ(t − nT )
n=−∞

được gọi là mẫu dạng sóng h(t) với mẫu trong khoảng T .

(1.25)


18

1.3.

Biến đổi Fourier rời rạc

Để rời rạc cặp biến đổi Fourier, trước tiên ta tạo mẫu dạng sóng h(t)

=

(1.27)

k=0

trong đó ta giả thiết rằng có N khoảng bằng nhau mà hàm xung nằm
trong khoảng hàm chặt cụt, tức là N = T0 /T .
Cuối cùng, ta tạo mẫu của biến đổi Fourier của (1.27). Trong miền
thời gian, tích này bằng với tích chập của hàm mẫu dạng sóng hàm chặt
cụt với hàm ∆1 (t) cho bởi
∞

δ(t − rT0 ).

∆1 (t) = T0
r=−∞

(1.28)


19

Tích chập này được cho như sau
N −1

˜ = [h(t)∆0 tx(t)] ∗ ∆1 (t) = q
h(t)

∞


h(kT )δ(t − kT − rT0 ) .

= T0
r=−∞

k=0

(1.29)
Để rời rạc biến đổi Fourier (1.29), ta chú ý rằng biến đổi Fourier của
một hàm tuần hoàn h(t) là một chuỗi các hàm xung cách đều
∞

n
˜ n =
αn δ(f − )
H(
T0 n=−∞
T0

(1.30)

trong đó
αn =

T0 −T /2

1
T0


h(kT )δ(t − kT )e−i2πnt/T0 dt

k=0

N −1

=

T0 −T /2

h(kT )
k=0
N −1

N −1

e−i2πnt/T0 δ(t − kT )dt

−T /2

h(kT )e−i2πknT /T0 .

=
k=0

(1.32)


20


NT

N −1

h(kT )e−i2πkr/N .

(1.35)

k=0

Tiếp theo đặt n = r + N, chú ý rằng
e−i2πk(r+N )/N = e−i2πkr/N e−i2πk = e−i2πkr/N .
Do đó
˜ r +N) =
H(
NT

N −1

h(kT )e−i2πk(r+N )/N
k=0
N −1

=
k=0

˜ r ).
h(kT )e−i2πkr/N = H(
NT



Xét biến đổi Fourier rời rạc (1.36), để cho tiện ta thay kT bởi k và
n
NT

bởi n
N −1

x0 (k)e−i2πnk/N , n = 0, 1, . . . , N − 1.

X(n) =

(1.37)

k=0

Ta chú ý rằng phương trình (1.37) biểu thị N phương trình. Ví dụ với
n = 3, đặt
W nk = e−i2πnk/N
khi đó phương trình (1.37) được viết lại như sau
X(0) = x0 (0)W 0 + x0 (1)W 0 + x0 (2)W 0 + x0 (3)W 0
X(1) = x0 (0)W 0 + x0 (1)W 1 + x0 (2)W 2 + x0 (3)W 3
X(2) = x0 (0)W 0 + x0 (1)W 2 + x0 (2)W 4 + x0 (3)W 6
X(3) = x0 (0)W 0 + x0 (1)W 3 + x0 (2)W 6 + x0 (3)W 9 .
Hay


 
X(0)
W0

 0 


W 3
 x0 (1)


x0 (2)
W 6


9
W
x0 (3)
0

(1.38)

hoặc
X(n) = W nk x0 (k).
1.4.2.

(1.39)

FFT với các ví dụ trực giác

Để minh họa thuật toán Fourier nhanh (FFT), ta chọn số điểm mẫu
của x0 (k) theo quan hệ N = 2γ , trong đó γ là một số nguyên. Như trong
minh họa trên thì N = 4 = 22 . Ta sẽ minh họa cách áp dụng phương
pháp FFT để tính toán (1.38) như sau:



W 1 W 2 W 3
 x0 (1)

.
x0 (2)
W 2 W 0 W 2


3
2
1
W W W
x0 (3)

(1.40)

Ma trận (1.40) được suy ra từ (1.38) bằng việc sử dụng W nk = W nk

mod N

Thật vậy, ta sẽ chứng minh với N = 4, n = 2, k = 3 thì W 6 = W 2 , những
đẳng thức khác được chứng minh hoàn toàn tương tự.
W6 = e

−i2π6
4

= e−i3π = e−iπ = e


0

0



0

1 0 W


0 0 
 0 1 0

2

1 W 1
 1 0 W
1 W3

0 1

0



0
x (0)
 0 


X(1)


X(3)
và



 
x (0)
1
 1  
x (1) 0
 1  

=
x1 (2) 1

 
x1 (3)
0

0 W
1

0

0



23

Ta thấy rằng, phần tử x1 (0) được tính bởi một phép nhân phức và một
phép cộng phức
x1 (0) = x0 (0) + W 0 x0 (2).

(1.45)

Phần tử x1 (1) cũng được tính bởi một phép nhân phức và một phép cộng,
tuy nhiên tới phần tử x1 (2) chỉ cần tới phép cộng bởi vì W 0 = −W 2
nên
x1 (2) = x0 (0) + W 2 x0 (2) = x0 (0) − W 0 x0 (2)

(1.46)

trong đó W 0 x0 (2) đã được tính từ công thức tính x1 (0). Tương tự như
vậy để tính x1 (3) ta chỉ cần tới một phép cộng phức và không cần tới
phép nhân. Như vậy véc tơ trung gian x1 (k) được tính bởi 4 phép nhân
và 2 phép cộng.
Ta tiếp tục tính toán công thức

 
 
X(0)
x (0)
1

  2  
X(1) x (1) 1


0
x (0)
 1 


0 
 x1 (1)

.
x1 (2)
W 1


3
W
x1 (3)

(1.47)

Ta thấy rằng, phần tử x2 (0) được tính bởi một phép nhân phức và một
phép cộng
x2 (0) = x1 (0) + W 0 x1 (1).

(1.48)

Phần tử x2 (1) cũng được tính bởi một phép cộng (để có điều này ta cần
chú ý W 0 = −W 2 ). Tương tự x2 (2) được xác định bởi một phép nhân
và một phép cộng và x2 (3) được xác định chỉ bởi một phép cộng.
¯