Xấp xỉ Chebyshev và Minimax

Xấp xỉ minimax tìm kiếm hàm xấp xỉ có sai số lớn nhất nhỏ nhất có thể, đảm bảo độ chính xác đồng đều; đa thức Chebyshev và thuật toán Remez là các công cụ trung tâm để tính toán và hiểu các xấp xỉ đồng đều tốt nhất như vậy.

Definition

Xấp xỉ Minimax là việc xác định hàm xấp xỉ làm giảm thiểu sai số tuyệt đối tối đa trên miền, và xấp xỉ Chebyshev là tập hợp lý thuyết và phương pháp được xây dựng xung quanh đa thức Chebyshev nhằm đạt được hoặc tiếp cận gần nhất với sự phù hợp đồng đều tốt nhất này.

Scope

Chủ đề này bao gồm xấp xỉ đồng đều tốt nhất (minimax) trong chuẩn tối đa, định lý dao động đều Chebyshev, vai trò và tính gần tối ưu của đa thức Chebyshev và nội suy Chebyshev, cũng như thuật toán trao đổi Remez để tính toán xấp xỉ đa thức và phân thức minimax.

Core questions

• Điều gì đặc trưng cho xấp xỉ đồng đều tốt nhất, và tại sao nó là duy nhất?
• Tại sao đa thức Chebyshev lại là trung tâm của xấp xỉ đa thức gần tối ưu?
• Thuật toán Remez tính toán xấp xỉ minimax thực sự một cách lặp lại như thế nào?
• Khi nào thì một sự phù hợp minimax được ưu tiên hơn một sự phù hợp bình phương nhỏ nhất, và với chi phí tính toán nào?

Key theories

Định lý dao động đều

Một đa thức có bậc tối đa n là xấp xỉ đồng đều tốt nhất cho một hàm liên tục nếu và chỉ nếu sai số của nó đạt độ lớn tối đa với dấu xen kẽ tại ít nhất n+2 điểm; đặc điểm này làm cho xấp xỉ tốt nhất là duy nhất và có thể tính toán được.

Tính gần tối ưu của xấp xỉ Chebyshev

Nội suy hoặc mở rộng theo đa thức Chebyshev tại các điểm Chebyshev tạo ra các xấp xỉ có sai số tối đa nằm trong một yếu tố nhỏ, tăng theo logarit so với mức tốt nhất có thể, do đó các phương pháp Chebyshev cung cấp một sự thay thế không tốn kém cho các sự phù hợp minimax thực sự.

Thuật toán trao đổi Remez

Thuật toán Remez điều chỉnh lặp lại một tập hợp các điểm tham chiếu ứng cử viên để thực thi điều kiện dao động đều, hội tụ nhanh chóng đến xấp xỉ minimax đa thức hoặc phân thức tốt nhất chính xác.

Mechanisms

Thuật toán Remez bắt đầu với một phỏng đoán về các điểm dao động đều, giải một hệ phương trình tuyến tính nhỏ để sai số dao động đều với cùng độ lớn và dấu xen kẽ trên tập tham chiếu đó, sau đó di chuyển các điểm tham chiếu đến các cực trị sai số mới và lặp lại; quy trình này hội tụ bậc hai đến nghiệm minimax. Xấp xỉ Chebyshev thay vào đó mở rộng hàm theo đa thức Chebyshev — có thể tính toán hiệu quả thông qua biến đổi Fourier nhanh — khai thác tính chất chuẩn sup tối thiểu của chúng để đạt được độ chính xác gần tốt nhất mà không cần lặp lại.

Clinical relevance

Xấp xỉ Minimax và Chebyshev được sử dụng để xây dựng các hàm cơ bản trong thư viện toán học, để thiết kế các bộ lọc số với sai số đáp ứng tần số đồng đều, và để xây dựng các xấp xỉ nhỏ gọn, chính xác đồng đều cho tính toán nhúng và thời gian thực, nơi giới hạn sai số trường hợp xấu nhất quan trọng hơn sai số trung bình.

History

Lý thuyết này bắt nguồn từ nghiên cứu của Chebyshev vào thế kỷ XIX về xấp xỉ đồng đều tốt nhất và nguyên lý dao động đều; Evgeny Remez đã phát minh ra thuật toán trao đổi của mình vào những năm 1930, và tính toán dựa trên Chebyshev đã trở thành một trụ cột thực tế của phần mềm số học vào cuối thế kỷ XX, đặc biệt thông qua công nghệ Chebyshev không cần vi phân tự động trong các hệ thống hiện đại.

Key figures

• Pafnuty Chebyshev
• Evgeny Remez
• Lloyd N. Trefethen

Seminal works

• trefethen2013
• powell1981
• cheney1966

Frequently asked questions

Dao động đều có nghĩa là gì một cách trực quan?

Nó có nghĩa là xấp xỉ đồng đều tốt nhất phân phối sai số của nó sao cho đường cong sai số liên tục chạm đến độ cao tối đa của nó, xen kẽ giữa dương và âm, tại đủ các điểm. Bất kỳ ứng cử viên nào khác đều có thể được cải thiện, vì vậy mô hình sai số cân bằng này báo hiệu tính tối ưu.

Tại sao sử dụng nội suy Chebyshev thay vì đa thức minimax chính xác?

Việc tính toán đa thức minimax chính xác yêu cầu thuật toán Remez lặp lại, trong khi nội suy Chebyshev nhanh và không lặp lại, và đạt được sai số gần bằng mức tốt nhất có thể, vì vậy nó thường là lựa chọn thực tế.