Elimination เบื้องต้น

4 min readAug 7, 2018

หมายเหตุ ผู้อ่านสามารถดู table of contents ของ Linear Algebra Recapได้ที่ http://bit.ly/2Oly2gz

ในบทความที่แล้วเราได้ทำการส่องวิธีการจัดการ linear equations เบื้องต้นกันไปแล้ว ในบทความนี้เราจะมาดูอีก 1 วิธีในการจัดการ linear equations กัน ซึ่งวิธีนี้เรียกว่า elimination

ก่อนอื่นเรามาดูโจทย์ตัวอย่างของบทความนี้กันก่อนนะครับ

จากนั้นขั้นต่อไปเราแปลง equations ให้อยู่ในรูปแบบของ matrix ได้ว่า

ในบทความที่แล้วถ้ายังพอจำกันได้ linear equations สามารถเขียนให้อยู่ในรูปแบบของสมการย่อได้ว่า Ax = b ซึ่งในที่นี้ vector x หรือสิ่งที่เราจะทำการหากันต่อไป โดยในขั้นตอนการทำ elimination เราจะตัด vector x ออกจากภาพไปก่อนและรวม matrix A และ vector b เข้าด้วยกันเสมือนเป็น matrix (3 x 4) เพื่อพร้อมเข้าสู่การคำนวน

ขั้นตอนของ elimination เริ่มจากการหา pivot point ซึ่งเราจะเริ่มพิจารณาหา pivot point ตั้งแต่ element i,j (กำหนดให้ i และ j เริ่มจาก 1) โดยดูว่าค่าใน element ดังกล่าวต้องไม่เท่ากับ 0 จากนั้น กำหนดให้ element i + 1,j เป็น elimination point สิ่งที่เราต้องทำก็คือหาตัวเลขที่คูณกับ pivot point แล้วนำผลลัพธ์ดังกล่าวมาลบค่าออกจาก elimination point แล้วทำให้ elimination point เป็น 0 จากนั้นเราก็จะเลื่อนไปยัง column ถัดไปคือ j = j + 1 โดยตำแหน่ง pivot point และ elimination point ยังอยู่ที่เดิม นำตัวเลขที่คูณกับ pivot point ในขั้นตอนที่แล้วมาลบออกจาก element ปัจจุบัน ทำเช่นนี้ไปเรื่อยๆจนถึง column สุดท้ายจากนั้นเราก็จะเปลี่ยนเลื่อนไปยัง row ถัดไปนั้นก็คือ i = i + 1 และหา pivot point เช่นเดิม เรามาดูตัวอย่างทีละ step ของการคำนวนเพื่อความเข้าใจเพิ่มเติมกันเลยนะครับ

เริ่มต้น focus ที่ element i,j กำหนดให้ i และ j เริ่มจาก 1 วึ่งก็คือ element 1,1 นั้นเอง ถัดมาดูค่าใน element ดังกล่าวว่าเป็น 0 หรือไม่ ซึ่งใน element 1,1 นี้มีค่าเท่า 1 ซึ่งตรงกับที่เราต้องการว่าค่าใน element ต้องไม่เท่ากับ 0 ขั้นตอนต่อไปกำหนดให้ element 2,1 เป็น elimination point ที่เราต้องทำให้กลายเป็น 0 ซึ่งตอนนี้ element 2,1 มีค่าเป็น 3 ต่อมาเราต้องหาตัวเลขที่คูณกับ pivot point แล้วสามารถนำผลลัพธ์มาลบออกจาก elimination point แล้วทำให้ elimination point เท่ากับ 0 คำตอบก็คือเราต้องคูณด้วย 3

ซึ่งเมื่อ 3-(3*1) และค่าใน element 2,1 ก็จะกลายเป็น 0 โดยค่าตัวเลข 3 ที่นำมาคูณกับ pivot point จะถูกใช้คูณกับทุก column ที่เหลือใน row 1 ในขั้นต่อไป ถัดไปเราก็จะเลื่อนตำแหน่งของ column โดย j = j + 1 มาอยู่ใน element 2,2 ซึ่งมีค่าเป็น 8 จากนั้นนำตัวเลข 3 ที่เราได้จากการหาขั้นตอนก่อนหน้ามาคูณด้วย element 1,2 ได้ว่า 8–(3*2) = 2 ซึ่งกำหนดให้ element 2,2 มีค่าเท่ากับ 2 ถัดไปเราเลื่อนตำแหน่งของ column เช่นเดิมไปที่ element 2,3 ซึ่งมีค่าเป็น 1 เมื่อประมวณผลจะได้ว่า 1-(3*1) = -2 (element 2,3 = -2) ถัดไปเราเลื่อนตำแหน่งของ column ไปยัง column สุดท้ายนั้นก็คือ 12 เมื่อประมวณผลจะได้ว่า 12-(3 * 2) =6 (element 2,4 = 6) ซึ่งเมื่อถึงจุดนี้เราจะได้ค่าใหม่ใน row ดังนี้

ถัดไปเราก็จะเลื่อนตำแหน่งของ i ไปยัง i = i + 1 ซึ่งนั้นก็คือ row 2 จากนั้นเราจะเริ่มพิจารณา column 1 ของ row 2 ว่าควรจะกำหนดเป็น pivot point หรือไม่ ซึ่งผลคือไม่สามารถเป็นจุด pivot point ได้เพราะ element 2,1 มีค่าเป็น 0 เราต้องทำการเลื่อนไปยัง column ถัดไปนั้นก็คือ element 2,2 ที่มีค่าเท่ากับ 2 และกำหนดตำแหน่งดังกล่าวเป็น pivot point และกำหนด element 3,1 เป็น elimination point จากนั้นทำขั้นตอนเหมือนที่ทำก่อนหน้าคือหาตัวเลขที่คูณกับ pivot point แล้วสามารถนำผลลัพธ์มาลบออกจาก elimination point แล้วทำให้ elimination point เป็น 0 ได้ซึ่งนั้นก็คือ 2 จากนั้นทำการคำนวนเช่นเดิมซึ่งจะได้ผลลัพธ์ออกมาดังนี้

กำหนดจุด pivot point และ elimination point

จากนั้นเราก็ทำการเลื่อนไปยัง row ที่ 3 จากนั้นหา pivot point เช่นเดิมแต่เราไม่มี row ถัดไปจาก row นี้แล้วทำให้ไม่สามารถกำหนด elimination point ถือเป็นการจบขบวนการ ซึ่งเมื่อถึงจุดนี้เราจะกำหนด matrix และ vector ที่ได้นี้ว่าเป็น matrix U กับ vector c

สิ่งที่เราจะทำให้ขั้นตอนต่อไปคือการทำ back substitution เริ่มจากแปลง matrix และ vector ให้กลับไปอยู่ในรูปแบบของ equations เช่นเดิมโดยสามารถเขียนได้ว่า

จากนั้นพิจารณา equation ตัวสุดท้ายไล่ลำดับไปจนถึง equation ตัวสุดแรก โดย equation ตัวท้ายนั้นก็คือ 5z = -10 เพื่อหาค่า z ที่ถูกต้องที่ทำให้ equation นี้เป็นจริง นั้นก็คือ z = -2 ถัดไปขยับมาที่ equation ที่ 2 นั้นคือ 2y-(2*-2) = 6 เพื่อหาค่า y ซึ่งได้ว่า y = 1 จะทำให้ equation นี้สมบูรณ์ และสุดท้ายขยับมายัง equation ตัวแรกนั้นก็คือ x + (2*1) -2= 2 ซึ่งจะได้ว่า x = 2 ถึงตรงนี้เราก็จะได้ค่า unknown vector ดังนี้ x=2, y=1, z=-2

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

ถ้าพิจารณาดูระหว่าง matrix A และ matrix Q แล้วจะเห็นว่า row 1 และ 3 มีค่าเหมือนกันนั้นเท่ากับว่า ไม่ว่า matrix ที่คูณกับ matrix A จะเป็นอะไรแค่ต้องยังคงทำให้ row ดังกล่าวไม่มีการเปลี่ยนแปลงค่า ซึ่งตามที่หลายท่านอาจจะทราบอยู่แล้วว่า matrix ที่คูณกับ matrix ใดๆแล้วทำให้ matrix นั้นมีค่าเท่าเดิมเช่นเดียวกับ 1 ไม่ว่าคูณกับตัวเลขใดก็จะได้เท่าเดิมนั้นคือ identity matrices

ดังนั้นเราจะทำคือนำ identity matrices มาแปลงโดยใน row 1 และ 3 ของ identity matrices เราจะยังคงไว้ซึ่งค่าเดิม สิ่งที่เราต้องการคือแปลง row 2 ซึ่งจากที่เราได้จากการทำ elimination เราต้องนำ 3 มาคูณกับ pivot point เพื่อลบออกจาก 3 ในตำแหน่ง row 2, column 1 ให้กลายเป็น 0 ดังนั้นค่าที่เรามองหาอยู่คือ

step ต่อมาเราต้องหา matrix ที่คูณ matrix Q แล้วได้เป็น matrix U

ซึ่งจาก matrix Q กับ matrix U จะเห็นได้ว่า row 1 และ 2 ไม่มีการเปลี่ยนแปลงเราก็นำรูปแบบของ identity matrices มาใช้เช่นเดิมซึ่งเราจะคงค่าใน row 1 และ 2 ไว้เช่นเดิมเราจะทำการเปลี่ยนแปลงแค่ row 3 ซึ่งจาก step ที่ 2 ที่เราทำ elimination ไปพบว่าเราต้องนำ 2 มาคูณกับค่าในตำแหน่ง row 2, column 2 แล้วนำมาลบออกจาก 4 ในตำแหน่ง row 2, column 2 ซึ่งสามารถแปลงข้อมูลดังกล่าวออกมาเป็น matrix E32 ดังนี้