วันศุกร์ที่ 21 สิงหาคม พ.ศ. 2558

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

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

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

0.001x1 + 200x2 + x3 - 10x4 - 200x5 = 5      สมการที่ (1)
0.6x1 + 5x2 + 11.5x3 + 4x4 + 3x5 = -3       สมการที่ (2)
-11x1 + 3x2 + 0.8x3 + x4 - 15.8x5 = 7      สมการที่ (3)
2x1 + 2x2 + 2x3 + 0.000067x4 + 7x5 = 6      สมการที่ (4)
-3x1 - x2 + 2x3 + 8x4 + 1.3x5 = -11      สมการที่ (5)

จะทำการหาคำตอบของระบบสมการ (ค่า x1, x2, x3, x4 และ x5) เปรียบเทียบกันระหว่างการใช้ Gauss elimination โดยไม่มีการหาตัวหลัก และการใช้ Gauss elimination ร่วมกับการทำการหาตัวหลักแบบบางส่วน (Partial pivoting) การคำนวณกระทำโดยใช้โปรแกรม Spreadsheet ของ OpenOffice 3.3.0

รูปที่ ๑ เป็นการหาคำตอบด้วยเทคนิค Gauss elimination โดยไม่มีการหาตัวหลัก ตัวเลขสีเขียวที่อยู่ข้างหน้าสุดคือตัวเลขที่ใช้ในการกำจัดตัวแปร xi (i = 2-5) ออกทีละตัวจากแต่ละสมการ ตัวเลขสีแดงคือตัวเลขที่อยู่ในแนวทแยงมุมที่ทำหน้าที่เป็นตัวหาร จะเห็นว่าเมื่อนำค่า xi (i = 1-5) ที่คำนวณได้แทนค่ากลับเข้าไปในโจทย์ พบว่าค่าที่ได้จากสมการที่ (2)-(5) นั้นมีความคลาดเคลื่อนไปจากค่าที่ควรจะเป็น (ค่า df ซึ่งเป็นผลต่างระหว่างค่าที่ได้จากการนำเอาค่า x1, x2, x3, x4 และ x5 ที่คำนวณได้ แทนกลับเข้าไปในโจทย์ กับค่าที่โจทย์กำหนดมาให้คือค่าทางด้านขวามือของเครื่องหมายเท่ากับ) ทั้งนี้เป็นผลของค่าความคลาดเคลื่อนที่สะสมอยู่ในตัวแปร x แต่ละตัว
  
รูปที่ ๒ เป็นการหาคำตอบด้วยเทคนิค Gauss elimination ร่วมกับการหาตัวหลักแบบบางส่วน ในที่นี้พบว่าก่อนที่จะเริ่มทำการกำจัดไปข้างหน้าเป็นครั้งแรก ควรที่จะทำการจัดลำดับสมการใหม่ก่อน โดยเลื่อนสมการที่ (3) ให้มาเป็นสมการที่ (1) ทั้งนี้เพราะค่าสัมประสิทธิ์หน้าตัวแปร x1 ในสมการที่ (3) ที่มีขนาดเท่ากับ 11 นั้นมีขนาดที่ใหญ่กว่าขนาดของค่าสัมประสิทธิ์หน้าตัวแปร x1 ในสมการที่ (1) ที่มาค่าเพียง 0.001
  
และหลังจากกำจัด x1 ออกจากสมการที่ (2) ถึง (5) ไปแล้ว (ตัวเลขในหลักที่ 1 ของแถวที่ 2-5 ของเมทริกซ์ A มีค่าเป็น 0) ก่อนที่จะทำการกำจัดไปข้างหน้าในครั้งต่อไป (เพื่อกำจัดตัวแปร x2 ออกจากสมการที่ (3) ถึง (5)) ก็ต้องทำการตรวจสอบว่าค่าสัมประสิทธิ์ของตัวแปร x2 ในสมการที่เหลือ ของสมการใดมีขนาดที่ใหญ่ที่สุด โดยในที่นี้พบว่าค่าสัมประสิทธิ์ของตัวแปร x2 ของสมการที่ (2) มีขนาดที่ใหญ่ที่สุดเมื่อเทียบกับของสมการอื่นที่เหลือ ดังนั้นจึงไม่จำเป็นต้องมีการจัดลำดับสมการใหม่ สามารถทำการกำจัดไปข้างหน้าเป็นครั้งที่สองได้เลยเพื่อกำจัดตัวแปร x2 ออกจากสมการที่ (3) ถึง (5)
  
ทำนองเดียวกันก่อนที่จะกำจัดตัวแปร x3 ออกจากสมการที่ (4) ถึง (5) ก็ต้องทำการตรวจสอบว่าค่าสัมประสิทธิ์ของตัวแปร x3 ในสมการที่เหลือ ของสมการใดมีขนาดที่ใหญ่ที่สุด โดยในที่นี้พบว่าค่าสัมประสิทธิ์ของตัวแปร x3 ของสมการที่ (3) มีขนาดที่ใหญ่ที่สุดเมื่อเทียบกับของสมการอื่นที่เหลือ ดังนั้นจึงไม่จำเป็นต้องมีการจัดลำดับสมการใหม่ สามารถทำการกำจัดไปข้างหน้าเป็นครั้งที่สองได้เลยเพื่อกำจัดตัวแปร x3 ออกจากสมการที่ (4) และ (5)
  
ในขั้นตอนสุดท้ายซึ่งเป็นการกำจัดตัวแปร x4 ออกจากสมการที่ (5) ในที่นี้พบว่าสัมประสิทธิ์หน้าตัวแปร x4 ของสมการที่ (5) (ตัวเลขสีน้ำเงิน) มีขนาดใหญ่กว่าของสัมประสิทธิ์หน้าตัวแปร x4 ในสมการที่ (4) ดังนั้นก่อนจะทำการกำจัดไปข้างหน้าจึงทำการจัดลำดับสมการใหม่ โดยสลับลำดับสมการที่ (4) และ (5)
 
รูปที่ ๒ (ต่อ) เป็นการแทนค่าย้อนกลับเพื่อหาค่าตัวแปร x1, x2, x3, x4 และ x5 และนำคำตอบที่ได้แทนค่ากลับเข้าไปในโจทย์ ในที่นี้พบว่าค่าที่ได้จากทุกสมการนั้นตรงกับค่าที่โจทย์กำหนดให้ พึงสังเกตว่าในกรณีของตัวอย่างที่ยกมานี้ความแตกต่างของ x1, x2, x3, x4 และ x5 ที่ได้จากการคำนวณโดยมีและไม่มีการหาตัวหลักนั้นอยู่ที่ทศนิยม ๓ ตำแหน่งสุดท้าย

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

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

ไม่มีความคิดเห็น: