การประมาณค่าแบบเชบีเชฟและมินิแมกซ์

การประมาณค่าแบบมินิแมกซ์เป็นการค้นหาค่าประมาณที่ให้ข้อผิดพลาดสูงสุดน้อยที่สุดเท่าที่จะเป็นไปได้ ซึ่งรับประกันความแม่นยำที่สม่ำเสมอ พหุนามเชบีเชฟและอัลกอริทึม Remez เป็นเครื่องมือหลักในการคำนวณและทำความเข้าใจการประมาณค่าแบบสม่ำเสมอที่ดีที่สุดดังกล่าว

Definition

การประมาณค่าแบบมินิแมกซ์คือการกำหนดค่าประมาณที่ลดข้อผิดพลาดสัมบูรณ์สูงสุดในช่วงโดเมน และการประมาณค่าแบบเชบีเชฟคือทฤษฎีและวิธีการที่สร้างขึ้นจากพหุนามเชบีเชฟ ซึ่งให้ผลลัพธ์ที่เหมาะสมที่สุดแบบสม่ำเสมอ หรือใกล้เคียงกับผลลัพธ์ดังกล่าว

Scope

หัวข้อนี้ครอบคลุมการประมาณค่าแบบสม่ำเสมอที่ดีที่สุด (มินิแมกซ์) ในนอร์มสูงสุด ทฤษฎีการแกว่งเท่าของเชบีเชฟ บทบาทและความใกล้เคียงกับค่าเหมาะสมที่สุดของพหุนามเชบีเชฟและการประมาณค่าในช่วงแบบเชบีเชฟ และอัลกอริทึมการแลกเปลี่ยนของ Remez สำหรับการคำนวณพหุนามมินิแมกซ์และการประมาณค่าตรรกยะ

Core questions

• อะไรคือลักษณะเฉพาะของการประมาณค่าแบบสม่ำเสมอที่ดีที่สุด และเหตุใดจึงมีเพียงหนึ่งเดียว?
• เหตุใดพหุนามเชบีเชฟจึงมีความสำคัญต่อการประมาณค่าพหุนามที่ใกล้เคียงกับค่าเหมาะสมที่สุด?
• อัลกอริทึม Remez คำนวณการประมาณค่ามินิแมกซ์ที่แท้จริงซ้ำๆ ได้อย่างไร?
• เมื่อใดที่การปรับค่าแบบมินิแมกซ์ดีกว่าการปรับค่าแบบกำลังสองน้อยที่สุด และมีค่าใช้จ่ายในการคำนวณเท่าใด?

Key theories

ทฤษฎีการแกว่งเท่า

พหุนามที่มีดีกรีไม่เกิน n เป็นการประมาณค่าแบบสม่ำเสมอที่ดีที่สุดสำหรับฟังก์ชันต่อเนื่องก็ต่อเมื่อข้อผิดพลาดของมันมีขนาดสูงสุดที่มีเครื่องหมายสลับกันที่จุดอย่างน้อย n+2 จุด ลักษณะเฉพาะนี้ทำให้การประมาณค่าที่ดีที่สุดมีเพียงหนึ่งเดียวและสามารถคำนวณได้

ความใกล้เคียงกับค่าเหมาะสมที่สุดของการประมาณค่าแบบเชบีเชฟ

การประมาณค่าในช่วงหรือการขยายในพหุนามเชบีเชฟที่จุดเชบีเชฟให้ค่าประมาณที่มีข้อผิดพลาดสูงสุดอยู่ในปัจจัยที่เพิ่มขึ้นแบบลอการิทึมขนาดเล็กของค่าที่ดีที่สุดที่เป็นไปได้ ดังนั้นวิธีการเชบีเชฟจึงเป็นทางเลือกที่ไม่แพงสำหรับการปรับค่ามินิแมกซ์ที่แท้จริง

อัลกอริทึมการแลกเปลี่ยนของ Remez

อัลกอริทึม Remez จะปรับชุดจุดอ้างอิงที่เสนอซ้ำๆ เพื่อบังคับใช้เงื่อนไขการแกว่งเท่า โดยจะลู่เข้าสู่การประมาณค่าพหุนามหรือตรรกยะมินิแมกซ์ที่ดีที่สุดอย่างรวดเร็ว

Mechanisms

อัลกอริทึม Remez เริ่มต้นด้วยการคาดเดาจุดแกว่งเท่า แก้ระบบสมการเชิงเส้นขนาดเล็กเพื่อให้ข้อผิดพลาดแกว่งเท่ากันด้วยขนาดที่เท่ากันและสลับเครื่องหมายบนชุดอ้างอิงนั้น จากนั้นย้ายจุดอ้างอิงไปยังจุดสุดขีดของข้อผิดพลาดใหม่และทำซ้ำ ขั้นตอนนี้จะลู่เข้าสู่ผลลัพธ์มินิแมกซ์แบบกำลังสอง ในทางกลับกัน การประมาณค่าแบบเชบีเชฟจะขยายฟังก์ชันในพหุนามเชบีเชฟ ซึ่งสามารถคำนวณได้อย่างมีประสิทธิภาพผ่านการแปลงฟูริเยร์แบบเร็ว โดยใช้ประโยชน์จากคุณสมบัติ sup-norm ขั้นต่ำเพื่อให้ได้ความแม่นยำที่ใกล้เคียงที่สุดโดยไม่ต้องทำซ้ำ

Clinical relevance

การประมาณค่าแบบมินิแมกซ์และเชบีเชฟถูกนำมาใช้ในการสร้างรูทีนฟังก์ชันพื้นฐานในไลบรารีทางคณิตศาสตร์ เพื่อออกแบบตัวกรองดิจิทัลที่มีข้อผิดพลาดการตอบสนองความถี่ที่สม่ำเสมอ และเพื่อสร้างการประมาณค่าที่กระชับและแม่นยำสม่ำเสมอสำหรับการคำนวณแบบฝังตัวและแบบเรียลไทม์ ซึ่งขอบเขตข้อผิดพลาดกรณีที่เลวร้ายที่สุดมีความสำคัญมากกว่าข้อผิดพลาดเฉลี่ย

History

ทฤษฎีนี้มีต้นกำเนิดจากการศึกษาการประมาณค่าแบบสม่ำเสมอที่ดีที่สุดและหลักการแกว่งเท่าของเชบีเชฟในศตวรรษที่ 19; Evgeny Remez ได้คิดค้นอัลกอริทึมการแลกเปลี่ยนของเขาในทศวรรษที่ 1930 และการคำนวณโดยใช้เชบีเชฟได้กลายเป็นหลักสำคัญในซอฟต์แวร์เชิงตัวเลขในช่วงปลายศตวรรษที่ 20 โดยเฉพาะอย่างยิ่งผ่านเทคโนโลยีเชบีเชฟที่ปราศจากการหาอนุพันธ์อัตโนมัติในระบบสมัยใหม่

Key figures

• Pafnuty Chebyshev
• Evgeny Remez
• Lloyd N. Trefethen

Seminal works

• trefethen2013
• powell1981
• cheney1966

Frequently asked questions

การแกว่งเท่าหมายถึงอะไรโดยสัญชาตญาณ?

หมายความว่าการประมาณค่าแบบสม่ำเสมอที่ดีที่สุดจะกระจายข้อผิดพลาดเพื่อให้เส้นโค้งข้อผิดพลาดสัมผัสกับความสูงสูงสุดซ้ำๆ โดยสลับระหว่างค่าบวกและค่าลบที่จุดจำนวนมาก ผู้สมัครรายอื่นสามารถปรับปรุงได้ ดังนั้นรูปแบบข้อผิดพลาดที่สมดุลนี้จึงบ่งบอกถึงความเป็นค่าเหมาะสมที่สุด

เหตุใดจึงใช้การประมาณค่าในช่วงแบบเชบีเชฟแทนที่จะใช้พหุนามมินิแมกซ์ที่แม่นยำ?

การคำนวณพหุนามมินิแมกซ์ที่แม่นยำต้องใช้อัลกอริทึม Remez แบบวนซ้ำ ในขณะที่การประมาณค่าในช่วงแบบเชบีเชฟนั้นรวดเร็วและไม่วนซ้ำ และให้ข้อผิดพลาดที่ใกล้เคียงกับค่าที่ดีที่สุดที่เป็นไปได้ในปัจจัยเล็กน้อย ดังนั้นจึงมักเป็นทางเลือกที่ใช้งานได้จริง