Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân Tích Lỗi Làm Tròn Cải Tiến cho Các Yếu Tố Twiddle Tính Toán Trước
Tóm tắt
Việc tính toán trước các yếu tố twiddle một cách chính xác là cần thiết để thực hiện các biến đổi lượng giác rời rạc. Bài báo này trình bày cả phân tích trường hợp tồi tệ nhất và trường hợp trung bình về các lỗi làm tròn xảy ra trong tám phương pháp tính toán trước các yếu tố twiddle. Chúng tôi quan tâm đến các phương pháp có lỗi làm tròn nhỏ, độ phức tạp thấp và chỉ sử dụng ít bộ nhớ máy tính. Các bài kiểm tra số học xác nhận các kết quả lý thuyết.
Từ khóa
#yếu tố twiddle #lỗi làm tròn #biến đổi lượng giác #tính toán trước #phân tích lỗiTài liệu tham khảo
M. Arioli, H. Munthe-Kaas, and L. Valdettaro, Componentwise error analysis for FFTs with applications to fast Helmholtz solvers, Numer. Algorithms 12, 65-88 (1996).
O. Bunemann, Stable on-line creation of sines and cosines of successive angles, Proc. IEEE 75, 1434-1435 (1987).
D. Calvetti, A stochastic roundoff error analysis for the fast Fourier transform, Math. Comp. 56, 755-774 (1991).
C. Y. Chu, The Fast Fourier Transform on Hypercube Parallel Computers, PhD Thesis, Technical Report 87-882, Cornell University (1987).
H. Deuflhard and A. Hohmann, Numerische Mathematik, de Gruyter, Berlin (1991).
N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia (1996).
C. Van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, Philadelphia (1992).
J. Oliver, Stable methods for evaluating the points cos(iπ/n), J. Inst. Math. Appl. 16, 247-257 (1975).
D. Potts, G. Steidl, and M. Tasche, Numerical Stability of Fast Trigonometric Transforms, Preprint, Medical University of Lübeck (1999).
M. Tasche and H. Zeuner, Roundoff Error Analysis for the Fast Fourier Transform with Precomputed Twiddle Factors, Preprint, Medical University of Lübeck (1999).
M. Tasche and H. Zeuner, Worst and average case roundoff error analysis for FFT, BIT 41, 563-581 (2001)