Biến đổi Fourier
Tích phân Fourier
Tích phân Fourier được xác định bởi biểu thức
Nếu tích phân tồn tại cho mọi giá trị của tham số f, thì biến đổi Fourier H(f) của h(t) được định nghĩa bởi công thức (1.1) Trong đó, h(t) là hàm của biến thời gian và H(f) là hàm của tần số Trong luận văn này, chúng tôi sẽ sử dụng ký hiệu t để biểu thị thời gian và f để biểu thị tần số Hơn nữa, ký hiệu chữ thường sẽ đại diện cho hàm thời gian, trong khi biến đổi Fourier của hàm thời gian sẽ được ký hiệu bằng chữ cái in hoa.
Nói chung, biến đổi Fourier là một đại lượng phức:
H(f) = R(f) +jI(f) =|H(f)|e iθ(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 p
R 2 (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)].
Khi đó biến đổi Fourier của h(t) được cho bởi
−T e −if t = − 1 if e −if T −e if T dt
Ví dụ 1.2 Để minh họa sự biến thiên các phần tử trong biến đổi Fourier, ta xét hàm của biến thời gian t h(t)
Theo công thức (1.1) ta có
Ta có minh họa như hình dưới đây
Hình 1.1: Phần thực, phần ảo, độ lớn và góc pha trong biến đổi Fourier
Biến đổi Fourier ngược
Biến đổi Fourier ngược được định nghĩa như sau h(t) Z ∞
Phép biến đổi Fourier ngược cho phép xác định hàm thời gian từ phép biến đổi Fourier tương ứng của nó Nếu h(t) và H(f) được xác định từ các công thức liên quan, chúng được gọi là cặp biến đổi Fourier, được ký hiệu là h(t) ⇔ H(f).
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 < ∞ (1.5) thì biến đổi Fourier H(f) tồn tại và thỏa mãn biến đổi Fourier ngược (1.3).
Định lý 1.1 chỉ là điều kiện đủ cho sự tồn tại của biến đổi Fourier, không phải điều kiện cần Có những hàm không thỏa mãn Định lý 1.1 nhưng vẫn có biến đổi thỏa mãn điều kiện (1.3) Theo Định lý 1.2, nếu hàm h(t) = β(t) sin(2πf t + α) với f và α là hằng số bất kỳ, và β(t + k) < β(t) cùng với điều kiện |t| > λ > 0, thì hàm h(t)/t khả tích tuyệt đối theo nghĩa (1.5) sẽ dẫn đến sự tồn tại của H(f) và thỏa mãn biến đổi Fourier ngược (1.3).
Tính chất của biến đổi Fourier
Tính chất 1 Tính tuyến tính Nếu x(t) và y(t) có các biến đổi Fourier tương ứng là X(f) và Y(f) thì tổng x(t) + y(t) có biến đổi Fourier là X(f) +Y(f).
Chứng minh Thật vậy, ta có
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
Chứng minh Thật vậy, từ công thức (1.3) ta có h(−t) Z ∞
H(f)e −i2πf t df. Đổi biến f bởi t từ công thức trên ta nhận được h(−f) Z ∞
Tính chất 3 Nhân với thời gian
Nếu h(t)⇔ H(f) thì h(kt) ⇔ 1 kH(f k), với k > 0.
Chứng minh Đặt t 0 = kt, ta có
Như vậy với k > 0 ta có h(kt) ⇔ 1 kH(f k).
Tính chất 4 Nhân với tần số
Chứng minh.Sử dụng công thức biến đổi Fourier ngược và đặtf 0 = kf ta có
Tính chất 5 Dịch chuyển theo thời gian Với t 0 là hằng số, nếu h(t) ⇔H(f) thì 1 kh(t−t 0 ) ⇔ H(f)e −i2πf t 0 Chứng minh Sử dụng công thức biến đổi Fourier và đặt s= t−t0 ta có
Tính chất 6 Dịch chuyển tần số
Với f 0 là hằng số, nếu h(t)⇔ H(f) thì e i2πtf 0 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 −f 0 ta có
Tính chất 7 Công thức biến đổi Fourier ngược
Công thức biến đổi Fourier ngược (1.3) có thể được viết lại dưới dạng h(t) hZ ∞
H ∗ (f)e −i2πf t df i∗ 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).
Chứng minh Ta có hZ ∞
Tính chất 8 Biến đổi Fourier của hàm chẵn
Nếu h e (t) là hàm chẵn, tức làh e (t) = h e (−t)thì biến đổi Fourier cũng là một hàm chẵn và ta có h e (t) ⇔R e (f) Z ∞
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 là một hàm lẻ và ta có h o (t)⇔ I o (f) = −i
Dễ thấy I o (f) là hàm lẻ.
Tính chất 10 Biến đổi Fourier của hàm phức
Nếu h(t) = h r (t) +ih i (t) thì ta có ho(t) ⇔ H(f) =R(f) +iI(f) với
[hr(t) sin(2πf t)−hi(t) cos(2πf t)]dt.
[hr(t) cos(2πf t) +hi(t) sin(2πf t)]dt
[hr(t) sin(2πf t)−hi(t) cos(2πf t)]dt
Tích chập
Định nghĩa 1.1 Tích chập y(t) của hai hàm x(t) và h(t) được ký hiệu bởi x(t)∗y(t) và được cho bởi công thức sau đây y(t) Z ∞
Chú ý công thức (1.6) có thể thay bằng công thức y(t) Z ∞
0, ngược lại Khi đó nếu sử dụng công thức (1.6) ta nhận được y(t) Z ∞
Định lý 1.3 về tích chập cho biết rằng nếu H(f) và X(f) là các biến đổi Fourier của h(t) và x(t), thì biến đổi Fourier của tích chập y(t) = h(t)∗x(t) sẽ là H(f)X(f) Điều này có nghĩa là cặp biến đổi Fourier h(t)∗x(t) tương ứng với H(f)X(f).
Sử dụng công thức đổi biến σ = t−τ ta nhận được
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ỳ T 0 được cho bởi công thức y(t) = a0
Các hệ số a n , b n được cho bởi công thức an = 2
Bằng việc sử dụng công thức cos(2πnt/T0)dt = 1
2(e i2πnt/T 0 +e −i2πnt/T 0 ) sin(2πnt/T 0 )dt = 1
2i(e i2πnt/T 0 −e −i2πnt/T 0 ) biểu diễn (1.9) có thể được viết lại như sau y(t) = a0
(a n +ib n )e −i2πnt/T 0 (1.12) Để đơn giản kí hiệu, với những giá trị n âm, từ công thức (1.10) và
Thay biểu diễn (1.13) và (1.14) vào công thức (1.12) ta nhận được chuỗi Fourier dạng mũ như sau y(t) = a0
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
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ó αn = 1
Hàm xung
Định nghĩa 1.3 (Hàm xung) Hàm xung (hay còn gọi là hàm δ) được định nghĩa như sau δ(t−t0) = 0, ∀t 6= t0 (1.17) và
Hàm xung có một số tính chất sau đây:
Tính chất 4 Tích của hàmδ với một hàm thông thường h(t) được cho bởi công thức sau đây
Nếu h(t) liên tục tại t =t0 thì δ(t 0 )h(t) = h(t 0 )δ(t 0 ) (1.23)
Mẫu dạng sóng
Mẫu dạng sóng được định nghĩa như sau: Nếu hàm h(t) là liên tục tại t = T, thì một mẫu của h(t) tại thời điểm T được biểu diễn bởi h(t) = h(T)δ(t−T), trong đó δ(t−T) là hàm xung xảy ra tại thời điểm T với biên độ bằng giá trị của hàm h(t) tại thời điểm này Nếu hàm h(t) liên tục tại các thời điểm t = nT với n = 0, ±1, ±2, , thì ta có thể xác định mẫu dạng sóng tương ứng.
X n=−∞ h(nT)δ(t−nT) (1.25) được gọi là mẫu dạng sóng h(t) với mẫu trong khoảng T.
Biến đổi Fourier rời rạc
Để thực hiện biến đổi Fourier rời rạc, trước tiên cần tạo mẫu dạng sóng h(t), có thể sử dụng ký hiệu h(t)∆0t với ∆0t là miền thời gian Giả sử khoảng mẫu là T, ta có thể viết lại phương trình (1.25) dưới dạng h(t)∆0t.
X k=−∞ h(kT)∆(t−kT) (1.26) Tiếp theo ta nhân hàm mẫu với hàm hình chữ nhật có dạng x(t)
0, nếu ngược lại trong đó T 0 là khoảng thời gian của hàm chặt cụt Ta có h(t)∆0tx(t) h X ∞ k=−∞ h(kT)δ(t−kT) i x(t)
X k=0 h(kT)δ(t−kT) (1.27) 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, chúng ta sẽ xây dựng mẫu biến đổi Fourier của (1.27) Trong miền thời gian, tích này tương đương với tích chập giữa hàm mẫu dạng sóng chặt cụt và hàm ∆ 1 (t).
Tích chập này được cho như sau ˜h(t) = [h(t)∆0tx(t)]∗∆1(t) = q h N−1 X k=0 h(kT)δ(t−kT) i∗h
(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
−T /2 h(t)e˜ −i2πnt/T 0 dt, n = 0,±1,±2, (1.31) Thay công thức (1.29) vào công thức (1.31) ta nhận được αn = 1
X k=0 h(kT)δ(t−kT −rT0)e −i2πnt/T 0 dt
Vì T0 = N T nên phương trình (1.32) được viết lại dưới dạng αn N−1
Khi đó biến đổi Fourier của (1.29) có dạng
Cho n = r với r là số nguyên bất kỳ, phương trình (1.34) trở thành
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
X k=0 h(kT)e −i2πnk/N , n = 0,1, , N −1 (1.36)Công thức (1.36) được gọi là biến đổi Fourier rời rạc.
Biến đổi Fourier nhanh
Công thức ma trận
Xét biến đổi Fourier rời rạc (1.36), để cho tiện ta thay kT bởi k và n
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
FFT với các ví dụ trực giác
Để minh họa thuật toán Fourier nhanh (FFT), chúng ta chọn số điểm mẫu x0(k) theo mối quan hệ N = 2^γ, trong đó γ là một số nguyên Ví dụ, với N = 4 = 2^2, chúng ta sẽ trình bày cách áp dụng phương pháp FFT để thực hiện tính toán (1.38).
Trước tiên ta viết lại (1.38) dưới dạng sau
Ma trận (1.40) được suy ra từ (1.38) thông qua công thức W nk = W nk mod N Để minh chứng điều này, ta xét trường hợp với N = 4, n = 2, k = 3, từ đó suy ra W 6 = W 2 Các đẳng thức tương tự cũng có thể được chứng minh theo cách tương đồng.
Bước tiếp theo ta biến đổi ma trận vuông trong công thức (1.40) dưới dạng sau
Tích hai ma trận vuông theo công thức (1.42) sẽ cho ra một ma trận vuông tương tự như trong công thức đó, chỉ khác ở chỗ dòng 1 và dòng 2 được hoán đổi.
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 tính bằng một phép nhân phức và một phép cộng, trong khi phần tử x1(2) chỉ cần phép cộng do W0 = −W2, dẫn đến x1(2) = x0(0) - W0 x0(2) Tương tự, để tính x1(3), chỉ cần một phép cộng phức mà không cần phép nhân Tổng cộng, véc tơ trung gian x1(k) được tính bằng 4 phép nhân và 2 phép cộng.
Ta tiếp tục tính toán công thức (1.40) Đặt
Ta thấy rằng, phần tử x 2 (0) được tính bởi một phép nhân phức và một phép cộng x 2 (0) = x 1 (0) +W 0 x 1 (1) (1.48)
Phần tử x2(1) được tính thông qua phép cộng với điều kiện W 0 = −W 2 Tương tự, x2(2) được xác định bởi cả phép nhân và phép cộng, trong khi x2(3) chỉ được xác định bởi phép cộng.
Để tính X(n)¯ theo công thức (1.42), cần thực hiện 4 phép nhân và 8 phép cộng, trong khi công thức (1.38) yêu cầu 16 phép nhân và 12 phép cộng Quá trình nhân tử hóa đã giúp giảm số lượng phép nhân cần thiết.
Với N = 2 γ, thuật toán FFT thực hiện quá trình phân tích ma trận N×N thành γ ma trận, nhằm tối ưu hóa số phép nhân và phép cộng Cụ thể, trong ví dụ minh họa, thuật toán FFT yêu cầu N γ/2 = 4 phép nhân để đạt được hiệu quả tối đa.
Trong khi tính toán trực tiếp phương trình (1.38), chúng ta cần thực hiện N² phép nhân và N(N − 1) phép cộng Nếu giả định thời gian tính toán tỷ lệ với số phép nhân, thì tỷ lệ thời gian giữa phương pháp tính trực tiếp và phương pháp FFT sẽ được xác định.
Khi N = 2^10, việc tính toán giảm hơn 200 lần so với phương pháp thông thường Số lượng phép nhân cần thiết khi áp dụng phương pháp FFT so với tính toán thông thường được thể hiện rõ qua hình minh họa dưới đây.
Hình 1.3: So sánh số lượng phép nhân khi tính toán trực tiếp và khi sử dụng phương pháp FFT
Đồ thị dòng tín hiệu
Đồ thị dòng tín hiệu trong phương trình (1.42) được minh họa như hình dưới đây, trong đó các véc tơ dữ liệu x0(k) được biểu diễn bằng cột thẳng đứng các nốt bên trái đồ thị Cột thẳng đứng thứ hai thể hiện mảng của véc tơ x1(k) được tính toán từ phương trình (1.44), trong khi cột tiếp theo biểu diễn véc tơ x2(k) Với N = 2, γ sẽ cho ra γ cột tính.
Hình 1.4: Đồ thị tín hiệu FFT, N = 4 Đồ thị dòng tín hiệu được mô tả như sau: Mỗi nốt được đưa vào bởi
Trong biểu đồ dòng tín hiệu, hai đường đậm có mũi tên thể hiện đường truyền từ tín hiệu trước, với mỗi đường truyền dẫn một đại lượng từ một nốt trong mảng nhân với đại lượng ký hiệu bởi Wp Kết quả được đưa vào nốt trong mảng kế tiếp, và Wp được hiểu là 1 tại các vị trí không có Kết quả từ hai đường truyền được kết hợp bằng phép cộng Ví dụ, nút x1(2) được tính theo công thức x1(2) = x0(0) + W2 x0(2), và các nút khác trong đồ thị cũng được tính toán tương tự.
Biểu đồ dòng tín hiệu là một phương pháp hiệu quả để thể hiện các tính toán trong nhân tử ma trận của thuật toán FFT Mỗi cột trong biểu đồ tương ứng với một nhân tử ma trận, với tổng cộng γ cột Việc sử dụng dạng biểu diễn đồ thị này giúp đơn giản hóa quá trình mô tả nhân tử hóa ma trận khi N lớn.
Ta minh họa đồ thị dòng tín hiệu cho trường hợp N = 16 = 2 4 như hình dưới đây
Thuật toán FFT
Ta trình bày thuật toán FFT trong trường hợp N = 2 γ với γ nhận giá trị nguyên Xét biến đổi Fourier rời rạc (1.37)
X k=0 x 0 (k)W nk , n = 0,1, , N −1 (1.50) trong đó, đặt W = e −i2π/N Tiếp theo ta biểu diễn số nguyên k và n dưới dạng nhị phân Ví dụ như với N = 4, γ = 2 thì k, n = 0,1,2,3 và được biểu diễn là k = 0,1,2,3 hay k = (k 1 , k 0 ) = 00,01,10,11 n = 0,1,2,3 hay n = (n 1 , n 0 ) = 00,01,10,11.
Cách ngắn gọn để biểu diễn k, n đó là k = 2k 1 +k 0 , n = 2n 1 +n 0 (1.51) trong đó n0, n1, k0, k1 chỉ nhận các giá trị là 0 hoặc 1.
Sử dụng biểu diễn (1.51), ta viết lại (1.50) cho trường hợp N = 4 như sau
Hình 1.5: Đồ thị tín hiệu FFT, N = 16
Nhân tử hóa W p
Ta xét nhân tử W p , vì W a+b = W a W b nên ta có
= W 2n 0 k 1 W (2n 1 +n 0 )k 0 (1.53) Chú ý rằng đẳng thức trên có được do
Phương trình (1.52) được viết lại như sau
Phương trình (1.54) là nền tảng của thuật toán FFT Chi tiết hơn, ta có thể xét từng tổng trong (1.54) Trước tiên ta viết tổng trong ngoặc dạng x 1 (n 0 , k 0 ) 1
Tính toán các phương trình trong (1.55) ta nhận được x1(0,0) =x0(0,0) +x0(1,0)W 0 x1(0,1) =x0(0,1) +x0(1,1)W 0 x1(1,0) =x0(1,0) +x0(1,0)W 2 (1.56) x1(1,1) =x0(0,1) +x0(1,1)W 2 hay viết lại (1.56) dưới dạng ma trận sau
Tương tự, ta viết tổng còn lại trong (1.54) như sau x2(n0, n−1) 1
Ta cũng nhận được ma trận
Từ phương trình (1.54) và (1.58) ta có
X(n 1 , n 0 ) =x 2 (n 0 , n 1 ) (1.60) Kết hợp phương trình (1.55), (1.58) và (1.60) ta được x1(n0, k0) 1
X(n1, n0) = x2(n0, n1). Đây chính là công thức của thuật toán Fourier nhanh trong trường hợp
Chương 2 Ứng dụng phương pháp Fourier nhanh giải phương trình parabolic tuyến tính
Trong chương này, chúng ta sẽ khám phá ứng dụng của phương pháp Fourier nhanh để giải các phương trình parabolic tuyến tính cấp 2 Nội dung chủ yếu của chương được xây dựng dựa trên các kiến thức đã được trình bày trong tài liệu [3].
2.1 Công thức sai phân hữu hạn
Xét phương trình truyền nhiệt dạng
∂x 2 2 ) (2.1) trong đó κ là hằng số, t là biến thời gian và (x 1 , x 2 ) trong không gian véc tơ 2 chiều.
Phương pháp sai phân hữu hạn được sử dụng để tìm nghiệm của phương trình (2.1) bằng cách thay thế các đạo hàm riêng bằng các sai phân hữu hạn thích hợp Trong chương này, chúng ta sẽ xem xét phương trình (2.1) trong hình chữ nhật R trên mặt phẳng x Phương pháp này tạo ra một lưới phủ hình chữ nhật với các bước lưới ∆x1 và ∆x2 tương ứng trên các trục x1 và x2.
Trong bài viết này, chúng ta có thể thấy rằng ∆x = ∆x1 = ∆x2, trong đó ký hiệu bước thời gian là ∆t Cần lưu ý rằng các bước thời gian không nhất thiết phải bằng nhau và thường nhỏ hơn ∆x để đảm bảo tính ổn định trong quá trình tính toán.
Bài toán giá trị ban đầu yêu cầu tìm hàm u(x, t) thỏa mãn phương trình (2.1) với điều kiện ban đầu u(x, 0) = f(x) Đồng thời, giá trị trên biên của hàm này được xác định bởi các điều kiện Dirichlet, cụ thể là u(x, t) = 0 với t ≥ 0 và x thuộc ∂R.
Trong bài viết này, chúng ta xem xét phương trình ∂x i (x, t) = 0 với điều kiện Neumann cho t ≥ 0 và x thuộc ∂R Cụ thể, chúng ta áp dụng điều kiện hỗn hợp giữa điều kiện Neumann và điều kiện Dirichlet ở một cạnh của hình chữ nhật, trong khi các cạnh còn lại áp dụng điều kiện Neumann.
Ta rời rạc hóa phương trình (2.1) Đặt m = (m 1 , m 2 ) và t = n∆t. Đạo hàm theo thời gian trong phương trình (2.1) được xấp xỉ bởi
∆t trong đó u n m chỉ giá trị nghiệm rời rạc tại điểm lưới (m, n) với chú ý rằng n là biến chỉ thời gian Đạo hàm riêng cấp hai ∂ ∂x 2 u 2
Như vậy dạng rời rạc của phương trình (2.1) có dạng
Phương trình sai phân hiện được mô tả bởi công thức ∇tu n+1 m = r[δ x 2 1 u n m +δ x 2 2 u n m ] (2.2), trong đó r = κ∆t/(∆x) 2 Giá trị của u tại bước thời gian n+1 được tính dựa trên giá trị u tại bước thời gian n Mặc dù lược đồ sai phân hiện cho phép tính toán nghiệm cho các giá trị n lớn hơn, nhưng nó có nhược điểm là không ổn định khi r lớn Cụ thể, lược đồ (2.2) sẽ ổn định trong các điều kiện nhất định.
0 < r ≤ 1 4 [3] Một cải tiến cho lược đồ (2.2) ta sử dụng lược đồ dưới đây u n+1 m = (1 +rδ 2 x 1 )(1 +rδ x 2 2 )u n m (2.3)
Theo nghiên cứu trong [3], lược đồ (2.3) được xác định là ổn định trong khoảng 0 < r ≤ 1/2, với sai số xấp xỉ (2.1) đạt cấp độ [∆t + (∆x)²] Tuy nhiên, khi r = 1/6, độ chính xác của lược đồ sai phân (2.3) có sự khác biệt, với sai số ở trường hợp này đạt cấp độ [(∆t)² + (∆x)⁴].
Lược đồ sai phân ẩn liên quan đến các giá trị nghiệm tại bước thời gian n+1, được xác định thông qua các phương trình tại bước n và n+1 Một trong những lược đồ sai phân ẩn nổi tiếng là Crank-Nicolson.
Khi áp dụng lược đồ Mitchell-Fairweather, cần sử dụng 10 điểm lưới thay vì 6 điểm như trong phương pháp trước đó Mặc dù cấp sai số của lược đồ ẩn không đạt yêu cầu tốt với mức độ sai số là [(∆t)² + (∆x)²], nhưng lược đồ Mitchell-Fairweather lại cung cấp độ chính xác cao hơn với sai số đạt cấp [(∆t)² + (∆x)⁴].
2.2 Bài toán giá trị biên ban đầu rời rạc
Tiếp theo ta sẽ rời rạc bài toán giá trị biên ban đầu và điều kiện biên. Điều kiện ban đầu được xấp xỉ bởi u 0 m = fm = f(m∆x), với 0 ≤ m1 ≤ M1,0 ≤ m2 ≤ M2.
Giả sử giải bài toán trong hình chữ nhật R = (0 ≤ x 1 ≤ L 1 ,0 ≤ x 2 ≤
Biên của lưới cho phương trình rời rạc được xác định bởi các giá trị m với m 1 = 0, m 1 = M 1, m 2 = 0, m 2 = M 2, trong đó M 1 và M 2 là các số nguyên thỏa mãn M1∆x = L1 và M2∆x = L2 Điều kiện biên Dirichlet được thể hiện qua u n+1 m = 0, trong khi điều kiện biên Neumann được mô tả bằng đạo hàm không gian thông qua sai phân trung tâm.
Giá trị giả của u n m tại m 1 = −1 thường được thay thế bởi u 1,m 2 trong lược đồ sai phân.
Ta biểu diễn nghiệm u n m dưới dạng u n m = X k 1 = 0 M 1 −1 X k 2 = 0 M 2 −1 U k n sin πk 1 m 1
M2 và nghiệm này rõ ràng thỏa mãn điều kiện biên.
Biểu diễn tích chập cho bài toán rời rạc cung cấp một cách tiếp cận tương tự để tìm nghiệm của bài toán ban đầu, được thể hiện qua công thức u(x, t) = K(x, t) * f(x) Ở đây, điều kiện ban đầu và nghiệm được giả định cho toàn bộ mặt phẳng x Trong không gian hai chiều, hàm Green K(x, t) có thể được biểu diễn như tích của hai hàm Green trong không gian một chiều k(x₁, t) và k(x₂, t), với k(s, t) = e^(-s²/4t) / √.
Chúng tôi sử dụng ký hiệu FFT[ã] để biểu thị biến đổi Fourier nhanh Để biểu diễn nghiệm, chúng tôi đặt U n (k) = F F T[u n m ] Biến đổi này được áp dụng cho các phần tử khác nhau trong công thức (2.5).
FFT[δ x 2 2 u n+1 m ] = FFT[u n m i +1 −2u n m +u n m i −1 ] = e iw i −2 +e −iw i FFT[u n m ] do vậy
FFT[δ x 2 2 u n+1 m ] = −2[1−cos(wi)]U n (k) (2.6) trong đó w i = πk/M i , i= 1,2 Ta chú ý rằng
FFT[δ x 2 1 δ x 2 2 u n m ] = 4[1−cos(w 1 )][1−cos(w 2 )]U n (k) (2.7) Kết hợp (2.6) và (2.7) ta có
FFT[(1 +r b δ x 2 1 )(1 +r b δ 2 x 2 )u n m ] 1−2r a (1−cosw 1 )−2r a (1−cosw 2 ) + 4r a 2 (1−cosw 1 )(1−cosw 2 )
U n (k). Đây là biến đổi vế phải của (2.5) và biến đổi vế trái tương tự Kết quả sau khi áp dụng biến đổi cho cả phương trình ta có
1−2rb(1−coswi). Nghiệm của phương trình (2.8) được tính trực tiếp và được cho bởi
Ta kí hiệu hàm Green rời rạc dạng G n m Vậy nghiệm của phương trình được cho bởi u n m ∗ f m (2.10)
2.3 Ví dụ số minh họa
Trong phần này, bài viết giới thiệu hai ví dụ cụ thể áp dụng thuật toán FFT để tìm nghiệm cho bài toán biên Dirichlet và bài toán biên Neumann liên quan đến phương trình parabolic trong không gian hai chiều và thời gian một chiều.
Ta xét hình chữ nhật R = 0 ≤ x 1 ≤ 1,0 ≤ x 2 ≤ 1, bước lưới
∆x1 = ∆x2 = ∆x = 0.02 Thời điểm cuối T = 1, bước thời gian
Ví dụ 2.1 Xét bài toán biên Dirichlet sau ut(x, t)−10 −2 ux 1 x 1(x, t)−10 −2 ux 2 x 2(x, t)
= sin(πx1) sin(πx2) −1 + 2.10 −2 π 2 (1−t) u(x,0) = sin(πx 1 ) sin(πx 2 ) u(x, t) = 0 với x∈ ∂R.
Nghiệm chính xác được cho bởi u(x, t) = sin(πx1) sin(πx2)(1−t).
Thời gian tính toán 0.147304 giây.
Hình 2.1: : Kết quả số cho bài toán biên Dirichlet (a) nghiệm chính xác tại thời điểm t = 0.2; (b) nghiệm ước lượng tại thời điểm t = 0.2; (c) sai số từng điểm tại thời điểm t = 0.2.
Ví dụ 2.2 Xét bài toán biên Neumann sau u t −(a 1 u x 1 ) x 1 −(a 2 u x 2 ) x 2 =f u(x,0) =u 0 trong đó a1(x1, x2, t) = a2(x1, x2, t) = 10 −1 (1 + 10 −2 cos(πx1t) cos(πx2)) u0
2x2, nếu x2 ≤ 0.5 và x2 ≤ x1 và x1 ≤ 1−x2, 2(1−x2), nếu x2 ≥ 0.5 và x2 ≥ x1 và x1 ≥ 1−x2, 2x1, nếu x1 ≤ 0.5 và x1 ≤ x2 và x2 ≤ 1−x1,
Nghiệm chính xác được cho bởi u(x, t)
2x2(1−t), nếu x2 ≤ 0.5 và x2 ≤ x1 và x1 ≤ 1−x2, 2(1−x2)(1−t), nếu x2 ≥ 0.5 và x2 ≥ x1 và x1 ≥ 1−x2, 2x 1 (1−t), nếu x 1 ≤ 0.5 và x 1 ≤ x 2 và x 2 ≤ 1−x 1 ,
2(1−x 2 )(1−t), ngược lại. Điều kiện biên Neumann được cho bởi trên tất cả các cạnh của hình chữ nhật R đều nhận giá trị bằng −2.10 −2
Thời gian tính toán là 0.559307 giây Hình 2.3 thể hiện nghiệm chính xác, nghiệm xấp xỉ và sai số tại thời điểm t = 0.2, trong khi Hình 2.4 trình bày các kết quả tương tự tại thời điểm t = 0.8.
Hình 2.2: : Kết quả số cho bài toán biên Dirichlet (a) nghiệm chính xác tại thời điểm t = 0.8; (b) nghiệm ước lượng tại thời điểm t = 0.8; (c) sai số từng điểm tại thời điểm t = 0.8.
Hình 2.3: : Kết quả số cho bài toán biên Neumann (a) nghiệm chính xác tại thời điểm t = 0.2; (b) nghiệm ước lượng tại thời điểm t = 0.2; (c) sai số từng điểm tại thời điểm t = 0.2.
Hình 2.4: : Kết quả số cho bài toán biên Neumann (a) nghiệm chính xác tại thời điểm t = 0.8; (b) nghiệm ước lượng tại thời điểm t = 0.8; (c) sai số từng điểm tại thời điểm t = 0.8.
Luận văn đã đạt được một số kết quả sau đây:
Biến đổi Fourier là một công cụ quan trọng trong phân tích tín hiệu, bao gồm các khái niệm như tích phân Fourier, biến đổi Fourier ngược, và tích chập Nó cho phép chuyển đổi giữa miền thời gian và miền tần số, giúp phân tích các hàm tuần hoàn và hàm xung Bên cạnh đó, biến đổi Fourier rời rạc cũng đóng vai trò quan trọng trong việc xử lý tín hiệu số, cung cấp các phương pháp hiệu quả để phân tích và xử lý dữ liệu.
- Trình bày lại một số kiến thức cơ bản liên quan tới biến đổi Fourier nhanh.
- Trình bày ứng dụng của biến đổi Fourier nhanh trong việc tìm nghiệm số của phương trình parabolic tuyến tính, có ví dụ số minh họa kèm theo.
