การคำนวณเชิงตัวเลข (๑๑) เปรียบเทียบ Gauss elimination ที่มีและไม่มีการทำ Pivoting MO Memoir : Friday 21 August 2558

Memoir ฉบับนี้จัดทำขึ้นเพื่อขยายความในเอกสารประกอบคำสอนวิชาคณิตศาสตร์สำหรับวิศวกรรมเคมี ในส่วนของการคำนวณเชิงตัวเลข เรื่องการแก้ปัญหาระบบสมการพีชคณิตเชิงเส้น

เทคนิคการกำจัดของเกาส์ (หรือ Gauss elimination) เป็นเทคนิคหลักในการหาคำตอบของระบบสมการพีชคณิตที่มีจำนวนสมการไม่มาก (สมการอยู่ในรูปแบบ A.x = b) เทคนิคนี้ประกอบด้วยขั้นตอนหลัก ๒ ขั้นตอนคือ ขั้นตอนแรกเป็นขั้นตอนของการกำจัดไปข้างหน้า (Forward elimination) ซึ่งเป็นการทำให้ตัวเลขในซีกซ้ายล่างของเมทริกซ์ A มีค่าเป็น 0 และขั้นตอนที่สองคือการแทนค่าย้อนกลับ (Back substitution) ที่เป็นการหาค่า ย้อนกลับจากค่า x_n มาจนถึง x₁ 
   

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

เพื่อให้เห็นภาพเรามาลองดูตัวอย่างกันดีกว่า โดยสมมุติว่าเรามีระบบสมการพีชคณิต 5 สมการ 5 ตัวแปรดังต่อไปนี้

0.001x₁ + 200x₂ + x₃ - 10x₄ - 200x₅ = 5      สมการที่ (1)

0.6x₁ + 5x₂ + 11.5x₃ + 4x₄ + 3x₅ = -3       สมการที่ (2)

-11x₁ + 3x₂ + 0.8x₃ + x₄ - 15.8x₅ = 7      สมการที่ (3)

2x₁ + 2x₂ + 2x₃ + 0.000067x₄ + 7x₅ = 6      สมการที่ (4)

-3x₁ - x₂ + 2x₃ + 8x₄ + 1.3x₅ = -11      สมการที่ (5)

จะทำการหาคำตอบของระบบสมการ (ค่า x₁, x₂, x₃, x₄ และ x₅) เปรียบเทียบกันระหว่างการใช้ Gauss elimination โดยไม่มีการหาตัวหลัก และการใช้ Gauss elimination ร่วมกับการทำการหาตัวหลักแบบบางส่วน (Partial pivoting) การคำนวณกระทำโดยใช้โปรแกรม Spreadsheet ของ OpenOffice 3.3.0

รูปที่ ๑ เป็นการหาคำตอบด้วยเทคนิค Gauss elimination โดยไม่มีการหาตัวหลัก ตัวเลขสีเขียวที่อยู่ข้างหน้าสุดคือตัวเลขที่ใช้ในการกำจัดตัวแปร x_i (i = 2-5) ออกทีละตัวจากแต่ละสมการ ตัวเลขสีแดงคือตัวเลขที่อยู่ในแนวทแยงมุมที่ทำหน้าที่เป็นตัวหาร จะเห็นว่าเมื่อนำค่า x_i (i = 1-5) ที่คำนวณได้แทนค่ากลับเข้าไปในโจทย์ พบว่าค่าที่ได้จากสมการที่ (2)-(5) นั้นมีความคลาดเคลื่อนไปจากค่าที่ควรจะเป็น (ค่า df ซึ่งเป็นผลต่างระหว่างค่าที่ได้จากการนำเอาค่า x₁, x₂, x₃, x₄ และ x₅ ที่คำนวณได้ แทนกลับเข้าไปในโจทย์ กับค่าที่โจทย์กำหนดมาให้คือค่าทางด้านขวามือของเครื่องหมายเท่ากับ) ทั้งนี้เป็นผลของค่าความคลาดเคลื่อนที่สะสมอยู่ในตัวแปร x แต่ละตัว
  

รูปที่ ๒ เป็นการหาคำตอบด้วยเทคนิค Gauss elimination ร่วมกับการหาตัวหลักแบบบางส่วน ในที่นี้พบว่าก่อนที่จะเริ่มทำการกำจัดไปข้างหน้าเป็นครั้งแรก ควรที่จะทำการจัดลำดับสมการใหม่ก่อน โดยเลื่อนสมการที่ (3) ให้มาเป็นสมการที่ (1) ทั้งนี้เพราะค่าสัมประสิทธิ์หน้าตัวแปร x₁ ในสมการที่ (3) ที่มีขนาดเท่ากับ 11 นั้นมีขนาดที่ใหญ่กว่าขนาดของค่าสัมประสิทธิ์หน้าตัวแปร x₁ ในสมการที่ (1) ที่มาค่าเพียง 0.001
  

และหลังจากกำจัด x₁ ออกจากสมการที่ (2) ถึง (5) ไปแล้ว (ตัวเลขในหลักที่ 1 ของแถวที่ 2-5 ของเมทริกซ์ A มีค่าเป็น 0) ก่อนที่จะทำการกำจัดไปข้างหน้าในครั้งต่อไป (เพื่อกำจัดตัวแปร x₂ ออกจากสมการที่ (3) ถึง (5)) ก็ต้องทำการตรวจสอบว่าค่าสัมประสิทธิ์ของตัวแปร x₂ ในสมการที่เหลือ ของสมการใดมีขนาดที่ใหญ่ที่สุด โดยในที่นี้พบว่าค่าสัมประสิทธิ์ของตัวแปร x₂ ของสมการที่ (2) มีขนาดที่ใหญ่ที่สุดเมื่อเทียบกับของสมการอื่นที่เหลือ ดังนั้นจึงไม่จำเป็นต้องมีการจัดลำดับสมการใหม่ สามารถทำการกำจัดไปข้างหน้าเป็นครั้งที่สองได้เลยเพื่อกำจัดตัวแปร x₂ ออกจากสมการที่ (3) ถึง (5)
  

ทำนองเดียวกันก่อนที่จะกำจัดตัวแปร x₃ ออกจากสมการที่ (4) ถึง (5) ก็ต้องทำการตรวจสอบว่าค่าสัมประสิทธิ์ของตัวแปร x₃ ในสมการที่เหลือ ของสมการใดมีขนาดที่ใหญ่ที่สุด โดยในที่นี้พบว่าค่าสัมประสิทธิ์ของตัวแปร x₃ ของสมการที่ (3) มีขนาดที่ใหญ่ที่สุดเมื่อเทียบกับของสมการอื่นที่เหลือ ดังนั้นจึงไม่จำเป็นต้องมีการจัดลำดับสมการใหม่ สามารถทำการกำจัดไปข้างหน้าเป็นครั้งที่สองได้เลยเพื่อกำจัดตัวแปร x₃ ออกจากสมการที่ (4) และ (5)
  

ในขั้นตอนสุดท้ายซึ่งเป็นการกำจัดตัวแปร x₄ ออกจากสมการที่ (5) ในที่นี้พบว่าสัมประสิทธิ์หน้าตัวแปร x₄ ของสมการที่ (5) (ตัวเลขสีน้ำเงิน) มีขนาดใหญ่กว่าของสัมประสิทธิ์หน้าตัวแปร x₄ ในสมการที่ (4) ดังนั้นก่อนจะทำการกำจัดไปข้างหน้าจึงทำการจัดลำดับสมการใหม่ โดยสลับลำดับสมการที่ (4) และ (5)
 

รูปที่ ๒ (ต่อ) เป็นการแทนค่าย้อนกลับเพื่อหาค่าตัวแปร x₁, x₂, x₃, x₄ และ x₅ และนำคำตอบที่ได้แทนค่ากลับเข้าไปในโจทย์ ในที่นี้พบว่าค่าที่ได้จากทุกสมการนั้นตรงกับค่าที่โจทย์กำหนดให้ พึงสังเกตว่าในกรณีของตัวอย่างที่ยกมานี้ความแตกต่างของ x₁, x₂, x₃, x₄ และ x₅ ที่ได้จากการคำนวณโดยมีและไม่มีการหาตัวหลักนั้นอยู่ที่ทศนิยม ๓ ตำแหน่งสุดท้าย

ไฟล์ที่แนบมาด้วยเป็นไฟล์ Spreadsheet ที่ใช้ในการคำนวณ
  

รูปที่ ๑ การหาคำตอบด้วยเทคนิค Gauss elimination โดยไม่มีการหาตัวหลัก
  

รูปที่ ๒ การหาคำตอบด้วยเทคนิค Gauss elimination ร่วมกับการหาตัวหลัก ในที่นี้มีการสลับลำดับสมการสองครั้ง คือการสลับลำดับครั้งแรกกระทำก่อนที่จะทำการกำจัดไปข้างหน้าครั้งแรก โดยได้ทำการย้ายสมการที่ (3) ขึ้นไปแทนที่สมการที่ (1) และดันสมการที่ (1) ลงมาเป็นสมการที่ (2) และดันสมการที่ (2) ลงมาเป็นสมการที่ (3) การสลับลำดับสมการครั้งที่สองเกิดขึ้นอีกครั้งก่อนที่จะทำการกำจัดไปข้างหน้าในครั้งที่สี่ โดยทำการสลับลำดับสมการที่ (4) และ (5) ทั้งนี้เพราะค่าสัมประสิทธิ์ของตัวแปร x₄ ในสมการที่ (5) (ตัวเลขสีน้ำเงิน) มีขนาดใหญ่กว่าค่าสัมประสิทธิ์ของตัวแปร x₄ ในสมการที่ (4)
  

รูปที่ ๒ (ต่อ) การหาคำตอบด้วยเทคนิค Gauss elimination ร่วมกับการหาตัวหลัก

ดาวน์โหลดไฟล์ pdf ที่ link นี้