อ่าน 3 นาที
องค์ประกอบหลัก
ตัว หลัก หรือ องค์ประกอบหลัก คือองค์ประกอบของ เมทริกซ์ หรือ อาร์เรย์ ที่ถูกเลือกเป็นอันดับแรกโดย อัลกอริทึม (เช่น การกำจัดแบบเกาส์ อั ลกอริทึมซิมเพล็กซ์ ฯลฯ
องค์ประกอบหลัก
ตัวหลักหรือองค์ประกอบหลักคือองค์ประกอบของเมทริกซ์หรืออาร์เรย์ที่ถูกเลือกเป็นอันดับแรกโดยอัลกอริทึม (เช่นการกำจัดแบบเกาส์อัลกอริทึมซิมเพล็กซ์ฯลฯ) เพื่อใช้ในการคำนวณบางอย่าง ในกรณีของอัลกอริทึมเมทริกซ์ โดยทั่วไปแล้วองค์ประกอบหลักจะต้องแตกต่างจากศูนย์อย่างน้อย และมักจะต้องอยู่ห่างจากศูนย์มาก ในกรณีนี้ การหาองค์ประกอบนี้เรียกว่าการเลือกองค์ประกอบหลักการเลือกองค์ประกอบหลักอาจตามด้วยการสลับแถวหรือคอลัมน์เพื่อนำองค์ประกอบหลักไปยังตำแหน่งคงที่และอนุญาตให้อัลกอริทึมดำเนินการได้อย่างสำเร็จ และอาจช่วยลดข้อผิดพลาดจากการปัดเศษได้ มักใช้สำหรับการตรวจสอบรูป แบบขั้นบันไดแถว
การจัดวางองค์ประกอบ ในเมทริกซ์ (Pivoting) อาจเปรียบได้กับการสลับหรือจัดเรียงแถวหรือคอลัมน์ในเมทริกซ์ และสามารถแสดงได้ในรูปของ การคูณ ด้วยเมทริกซ์การเรียงสับเปลี่ยนอย่างไรก็ตาม อัลกอริทึมส่วนใหญ่ไม่ค่อยเคลื่อนย้ายองค์ประกอบของเมทริกซ์ เพราะจะใช้เวลานานเกินไป ดังนั้นจึงใช้วิธีติดตามการเรียงสับเปลี่ยนแทน
โดยรวมแล้ว การเปลี่ยนแกน (pivoting) จะเพิ่มจำนวนการคำนวณให้กับอัลกอริทึม ซึ่งบางครั้งการคำนวณเพิ่มเติมเหล่านี้จำเป็นเพื่อให้อัลกอริทึมทำงานได้ ในบางครั้งการคำนวณเพิ่มเติมเหล่านี้ก็คุ้มค่า เพราะช่วยเพิ่มความเสถียรเชิงตัวเลขให้กับผลลัพธ์สุดท้าย
ตัวอย่างของระบบที่ต้องใช้การปรับเปลี่ยนทิศทาง
ในกรณีของการกำจัดแบบเกาส์เซียน อัลกอริทึมนี้ต้องการให้ค่าหลัก (pivot element) ไม่เป็นศูนย์ หากค่าหลักเป็นศูนย์ จำเป็นต้องสลับแถวหรือคอลัมน์ ระบบด้านล่างนี้ต้องการให้สลับแถวที่ 2 และ 3 เพื่อทำการกำจัด
ระบบที่ได้จากการหมุนแกนมีดังต่อไปนี้ และจะช่วยให้ขั้นตอนวิธีในการกำจัดและการแทนค่าแบบย้อนกลับสามารถแสดงผลลัพธ์ที่เป็นคำตอบของระบบได้
นอกจากนี้ ในการกำจัดแบบเกาส์เซียน โดยทั่วไปแล้วควรเลือกองค์ประกอบหลักที่มีค่าสัมบูรณ์ มาก ซึ่งจะช่วยเพิ่มเสถียรภาพเชิงตัวเลขระบบต่อไปนี้ได้รับผลกระทบอย่างมากจากข้อผิดพลาดจากการปัดเศษเมื่อทำการกำจัดแบบเกาส์เซียนและการแทนค่าแบบย้อนกลับ
ระบบนี้มีคำตอบที่แน่นอนคือx 1 = 10.00 และx 2 = 1.000 แต่เมื่อใช้อัลกอริธึมการกำจัดและการแทนค่าแบบย้อนกลับโดยใช้เลขคณิตสี่หลัก ค่าเล็กน้อยของ11 จะทำให้เกิดข้อผิดพลาดจากการปัดเศษเล็กน้อย อัลกอริธึมที่ไม่มีการสลับตำแหน่งจะให้ค่าประมาณของx 1 ≈ 9873.3 และx 2 ≈ 4 ในกรณีนี้ เป็นที่พึงปรารถนาที่เรา จะสลับแถวทั้งสองเพื่อให้21อยู่ในตำแหน่งหลัก
เมื่อพิจารณาระบบนี้แล้ว อัลกอริทึมการกำจัดและการแทนค่าแบบย้อนกลับโดยใช้เลขคณิตสี่หลักจะให้ค่าที่ถูกต้องคือx 1 = 10.00 และx 2 = 1.000
การหมุนบางส่วน การหมุนเรือ และการหมุนสมบูรณ์
ใน การเลือกแกนหลัก แบบบางส่วน (partial pivoting ) อัลกอริทึมจะเลือกค่าที่มีค่าสัมบูรณ์มากที่สุดจากคอลัมน์ของเมทริกซ์ที่กำลังพิจารณาว่าเป็นองค์ประกอบหลัก โดยเฉพาะอย่างยิ่ง เมื่อลดเมทริกซ์ให้อยู่ในรูปแบบขั้นบันไดแถว (row echelon form) การเลือกแกนหลักแบบบางส่วนจะสลับแถวก่อนที่จะลดแถวของคอลัมน์นั้น เพื่อให้องค์ประกอบหลักมีค่าสัมบูรณ์มากที่สุดเมื่อเทียบกับองค์ประกอบด้านล่างในคอลัมน์เดียวกัน โดยทั่วไปแล้ว การเลือกแกนหลักแบบบางส่วนก็เพียงพอที่จะลดข้อผิดพลาดจากการปัดเศษได้อย่างเหมาะสม
อย่างไรก็ตาม สำหรับบางระบบและอัลกอริธึม อาจจำเป็นต้องใช้ การสลับแถวและคอลัมน์อย่างสมบูรณ์ (หรือการสลับแถวและคอลัมน์สูงสุด) เพื่อให้ได้ความแม่นยำที่ยอมรับได้ การสลับแถวและคอลัมน์อย่างสมบูรณ์จะสลับทั้งแถวและคอลัมน์เพื่อใช้องค์ประกอบที่ใหญ่ที่สุด (ตามค่าสัมบูรณ์) ในเมทริกซ์เป็นตัวสลับแถวและคอลัมน์ โดยปกติแล้วการสลับแถวและคอลัมน์อย่างสมบูรณ์ไม่จำเป็นต่อการรักษาเสถียรภาพเชิงตัวเลข และเนื่องจากต้นทุนเพิ่มเติมในการค้นหาองค์ประกอบสูงสุดการปรับปรุงเสถียรภาพเชิงตัวเลขที่ได้รับมักจะถูกหักล้างด้วยประสิทธิภาพที่ลดลง ยกเว้นเมทริกซ์ขนาดเล็กที่สุด ดังนั้นจึงไม่ค่อยได้ใช้[ 1 ]
กลยุทธ์อีกอย่างหนึ่งที่เรียกว่าการสลับตำแหน่งหมากรุก (rook pivoting)ก็สลับทั้งแถวและคอลัมน์เช่นกัน แต่รับประกันเฉพาะว่าตัวสลับตำแหน่งที่เลือกนั้นเป็นค่าที่ใหญ่ที่สุดที่เป็นไปได้ในแถวนั้นและค่าที่ใหญ่ที่สุดที่เป็นไปได้ในคอลัมน์นั้นพร้อมกัน ไม่ใช่ค่าที่ใหญ่ที่สุดที่เป็นไปได้ในเมทริกซ์ย่อยที่เหลือทั้งหมด[ 2 ]เมื่อนำไปใช้กับคอมพิวเตอร์แบบอนุกรม กลยุทธ์นี้มีต้นทุนที่คาดหวังเพียงประมาณสามเท่าของการสลับตำแหน่งบางส่วน และจึงมีราคาถูกกว่าการสลับตำแหน่งแบบสมบูรณ์ การสลับตำแหน่งหมากรุกได้รับการพิสูจน์แล้วว่ามีเสถียรภาพมากกว่าการสลับตำแหน่งบางส่วนทั้งในทางทฤษฎีและในทางปฏิบัติ
การหมุนตามมาตราส่วน
กลยุทธ์การเลือกแกนหลักแบบปรับขนาด (Scale pivoting) เป็นอีกรูปแบบหนึ่งของกลยุทธ์การเลือกแกนหลัก ในวิธีการนี้ อัลกอริทึมจะเลือกค่าที่ใหญ่ที่สุดเมื่อเทียบกับค่าอื่นๆ ในแถวเดียวกันเป็นค่าแกนหลัก กลยุทธ์นี้เหมาะสมเมื่อค่าต่างๆ มีความแตกต่างกันมาก ทำให้เกิดข้อผิดพลาดจากการปัดเศษ การเลือกแกนหลักแบบปรับขนาดควรใช้ในระบบเช่นระบบด้านล่างที่ค่าในแถวมีความแตกต่างกันมาก ในตัวอย่างด้านล่าง การสลับแถวสองแถวจะเป็นสิ่งที่เหมาะสม เนื่องจากค่าแกนหลักปัจจุบัน 30 มีค่ามากกว่า 5.291 แต่มีค่าค่อนข้างน้อยเมื่อเทียบกับค่าอื่นๆ ในแถวเดียวกัน หากไม่สลับแถวในกรณีนี้ ข้อผิดพลาดจากการปัดเศษจะแพร่กระจายเหมือนในตัวอย่างก่อนหน้า
ตำแหน่งจุดหมุน
ตำแหน่งหลัก (pivot position) ในเมทริกซ์ A คือตำแหน่งในเมทริกซ์ที่สอดคล้องกับเลข 1 ที่อยู่แถวนำในรูปแบบขั้นบันไดลดรูปของ A เนื่องจากรูปแบบขั้นบันไดลดรูปของ A มีเอกลักษณ์เฉพาะตัว ตำแหน่งหลักจึงถูกกำหนดอย่างมีเอกลักษณ์และไม่ขึ้นอยู่กับว่ามีการสลับแถวในกระบวนการลดรูปหรือไม่ นอกจากนี้ หลักของแถวจะต้องปรากฏอยู่ทางด้านขวาของหลักในแถวด้านบนในรูปแบบขั้นบันไดด้วย
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ องค์ประกอบหลัก
ตัว หลัก หรือ องค์ประกอบหลัก คือองค์ประกอบของ เมทริกซ์ หรือ อาร์เรย์ ที่ถูกเลือกเป็นอันดับแรกโดย อัลกอริทึม (เช่น การกำจัดแบบเกาส์ อั ลกอริทึมซิมเพล็กซ์ ฯลฯ
ตัวอย่างของระบบที่ต้องใช้การปรับเปลี่ยนทิศทาง
ในกรณีของการกำจัดแบบเกาส์เซียน อัลกอริทึมนี้ต้องการให้ค่าหลัก (pivot element) ไม่เป็นศูนย์ หากค่าหลักเป็นศูนย์ จำเป็นต้องสลับแถวหรือคอลัมน์ ระบบด้านล่างนี้ต้องการให้สลับแถวที่ 2 และ 3 เพื่อทำการกำจัด
การหมุนบางส่วน การหมุนเรือ และการหมุนสมบูรณ์
ใน การเลือกแกนหลัก แบบบางส่วน (partial pivoting ) อัลกอริทึมจะเลือกค่าที่มีค่าสัมบูรณ์มากที่สุดจากคอลัมน์ของเมทริกซ์ที่กำลังพิจารณาว่าเป็นองค์ประกอบหลัก โดยเฉพาะอย่างยิ่ง เมื่อลดเมทริกซ์ให้อยู่ในรูปแบบขั้นบันไดแถว (row echelon form)...
การหมุนตามมาตราส่วน
กลยุทธ์การเลือกแกนหลักแบบปรับขนาด (Scale pivoting) เป็นอีกรูปแบบหนึ่งของกลยุทธ์การเลือกแกนหลัก ในวิธีการนี้ อัลกอริทึมจะเลือกค่าที่ใหญ่ที่สุดเมื่อเทียบกับค่าอื่นๆ ในแถวเดียวกันเป็นค่าแกนหลัก กลยุทธ์นี้เหมาะสมเมื่อค่าต่างๆ มีความแตกต่างกันมาก...