การวางเงื่อนไขและเสถียรภาพเชิงตัวเลข

การวางเงื่อนไข (Conditioning) วัดว่าผลเฉลยของปัญหาหนึ่งมีความไวต่อการรบกวนในข้อมูลมากน้อยเพียงใด ในขณะที่เสถียรภาพ (Stability) วัดว่าอัลกอริทึมหนึ่ง ๆ เพิ่มข้อผิดพลาดในการคำนวณเลขทศนิยมที่มีความแม่นยำจำกัดมากน้อยเพียงใด ซึ่งทั้งสองอย่างนี้ร่วมกันเป็นตัวกำหนดความแม่นยำของผลลัพธ์ที่คำนวณได้

Definition

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

Scope

หัวข้อนี้ครอบคลุมถึงเลขคณิตทศนิยม (floating-point arithmetic) และหน่วยการปัดเศษ (unit roundoff), เลขเงื่อนไข (condition number) ของปัญหาต่าง ๆ เช่น การแก้ระบบสมการเชิงเส้นและการประเมินค่าฟังก์ชัน, ข้อผิดพลาดไปข้างหน้า (forward error) และข้อผิดพลาดถอยหลัง (backward error), กฎทั่วไปที่ว่าข้อผิดพลาดไปข้างหน้าถูกจำกัดด้วยผลคูณของเลขเงื่อนไขกับข้อผิดพลาดถอยหลัง, และคำจำกัดความของเสถียรภาพถอยหลัง (backward stability) และเสถียรภาพไปข้างหน้า (forward stability)

Core questions

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

Key theories

เลขเงื่อนไข

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

การวิเคราะห์ข้อผิดพลาดถอยหลัง

แทนที่จะจำกัดข้อผิดพลาดในคำตอบโดยตรง จะแสดงให้เห็นว่าผลลัพธ์ที่คำนวณได้คือคำตอบที่แท้จริงของปัญหาที่อยู่ใกล้เคียง; อัลกอริทึมจะมีเสถียรภาพถอยหลังเมื่อปัญหาที่อยู่ใกล้เคียงนี้แตกต่างจากปัญหาเดิมในปริมาณของหน่วยการปัดเศษ

ข้อผิดพลาดไปข้างหน้าเท่ากับเลขเงื่อนไขคูณด้วยข้อผิดพลาดถอยหลัง

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

Mechanisms

ตัวเลขทศนิยมแสดงจำนวนจริงด้วยความแม่นยำที่จำกัด ดังนั้นการดำเนินการพื้นฐานแต่ละครั้งจึงเกิดข้อผิดพลาดสัมพัทธ์ที่ถูกจำกัดด้วยหน่วยการปัดเศษ การวิเคราะห์ข้อผิดพลาดถอยหลัง (backward error analysis) ติดตามข้อผิดพลาดเหล่านี้โดยระบุว่าเกิดจากการรบกวนข้อมูลมากกว่าผลลัพธ์ ซึ่งสร้างขอบเขตในรูปแบบ: คำตอบที่คำนวณได้เท่ากับคำตอบที่แท้จริงของข้อมูลนำเข้าที่ถูกรบกวน การรวมขอบเขตข้อผิดพลาดถอยหลังเข้ากับเลขเงื่อนไขของปัญหาจะให้ค่าประมาณข้อผิดพลาดไปข้างหน้า ซึ่งอธิบายว่าทำไมอัลกอริทึมที่มีเสถียรภาพจึงยังคงสูญเสียความแม่นยำในปัญหาที่มีเงื่อนไขไม่ดี (ill-conditioned problem) ได้

Clinical relevance

การทำความเข้าใจการวางเงื่อนไขและเสถียรภาพเป็นสิ่งสำคัญเมื่อต้องเชื่อถือผลลัพธ์ที่คำนวณได้: มันอธิบายว่าเหตุใดสูตรกำลังสองน้อยที่สุดบางสูตรจึงสูญเสียความแม่นยำ, เป็นแนวทางในการเลือกอัลกอริทึมที่มีเสถียรภาพและสูตรที่กำหนดไว้อย่างดี (well-posed formulations) ในการจำลองและการวิเคราะห์ข้อมูล, และเตือนเมื่อแบบจำลองที่มีเงื่อนไขไม่ดีไม่สามารถให้คำตอบที่เชื่อถือได้ไม่ว่าจะใช้วิธีใดก็ตาม

History

กรอบแนวคิดนี้ถูกสร้างขึ้นโดย Wilkinson ซึ่งการวิเคราะห์ข้อผิดพลาดถอยหลังของเขาในทศวรรษ 1960 ได้อธิบายความน่าเชื่อถือในทางปฏิบัติของการกำจัดแบบเกาส์ (Gaussian elimination) และต่อมาได้ถูกจัดระบบและขยายไปทั่วทั้งสาขาโดย Higham; มาตรฐานเลขทศนิยม IEEE 754 ได้วางพฤติกรรมการปัดเศษบนพื้นฐานที่มั่นคงและพกพาได้ในเวลาต่อมา

Key figures

• James H. Wilkinson
• Nicholas J. Higham
• Lloyd N. Trefethen
• William Kahan

Seminal works

• trefethen1997
• higham2002

Frequently asked questions

หากอัลกอริทึมมีเสถียรภาพ มันจะให้คำตอบที่แม่นยำเสมอไปหรือไม่?

ไม่ อัลกอริทึมที่มีเสถียรภาพถอยหลังรับประกันเพียงว่าคำตอบของมันถูกต้องสำหรับปัญหาที่อยู่ใกล้เคียงเท่านั้น; หากปัญหาเองมีเงื่อนไขไม่ดี ปัญหาที่อยู่ใกล้เคียงนั้นอาจมีผลเฉลยที่แตกต่างกันมาก ดังนั้นข้อผิดพลาดไปข้างหน้าจึงยังคงมีขนาดใหญ่ได้

หน่วยการปัดเศษคืออะไร?

หน่วยการปัดเศษคือข้อผิดพลาดสัมพัทธ์สูงสุดที่เกิดขึ้นเมื่อจำนวนจริงถูกปัดเศษเป็นจำนวนทศนิยมที่ใกล้ที่สุด; มันกำหนดความละเอียดของเลขคณิตทศนิยมและปรากฏในขอบเขตเสถียรภาพแทบทุกอัน