ข้ามไปเนื้อหา

การแปลงเฮาส์โฮลเดอร์

จากวิกิพีเดีย สารานุกรมเสรี

การแปลงเฮาส์โฮลเดอร์ (อังกฤษ: Householder transformation) ในคณิตศาสตร์ และในปริภูมิสามมิติ เป็นการสะท้อนเวกเตอร์กับระนาบ ในปริภูมิยูคลิเดียนทั่วไป การแปลงเฮาส์โฮลเดอร์เป็นการแปลงเชิงเส้นซึ่งเวกเตอร์กับระนาบเกินที่ผ่านจุดกำเนิด

อัลสตัน สกอตต์ เฮาส์โฮลเดอร์ ตีพิมพ์ผลงานเกี่ยวกับการแปลงชนิดนี้เป็นครั้งแรกในปี พ.ศ. 2501 การแปลงเฮาส์โฮลเดอร์เป็นเครื่องมือสำคัญในการหาการแยก QR ของเมทริกซ์

นิยามและสมบัติ

[แก้]

ระนาบเกินที่จะใช้สะท้อนเวกเตอร์นั้นสามารถแทนได้โดยเวกเตอร์หนึ่งหน่วย ซึ่งตั้งฉากกับระนาบเกินนั้น

ถ้า คือเมทริกซ์เอกลักษณ์ การแปลงเชิงเส้นที่กล่าวในบทนำของบทความนี้สามารถแทนใดโดยเมทริกซ์เฮาส์โฮลเดอร์

.

โดยแมทริกซ์เฮาส์โฮลเดอร์มีสมบัติดังต่อไปนี้

และ สะท้อนเวกเตอร์ ใดๆ กับระนาบเกินที่ตั้งฉากกับ โดยข้อความนี้สามารถแสดงให้เห็นจริงได้โดยสมการ

,

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

การประยุกต์ใช้ในการแยก QR

[แก้]

ในการแยก QR เราต้องการเขียนเมทริกซ์ ที่ำกำหนดให้ในรูป โดย เป็นเมทริกซ์เชิงตั้งฉากและ เป็นเมทริกซ์สามเหลี่ยมด้านบน เราสามารถใช้การแปลงเฮาส์โฮลเดอร์ในการคำนวณ และ ได้ดังต่อไปนี้

ให้ แทนเวกเตอร์ ที่มีศูนย์อยู่ ตัว ให้ แทนนอร์มของเวกเตอร์ ใดๆ และให้ เป็นเวกเตอร์หลักที่ 1 ของ แล้ว กำหนด

และ

( คือเมทริกซ์เอกลักษณ์ขนาด ) เป็นการแปลงเฮาส์โฮลเดอร์ที่สะท้อนเวกเตอร์กับระนาบเกินที่ตั้งฉากกับ แล้ว เราจะได้ว่า

หรือ

โดยที่ เป็นเมทริกซ์ขนาด กล่าวคือ ทำให้หลักแรกของ มีสมาชิกที่ไม่ใช่ศูนย์อยู่เพียงตัวเดียว

เราสามารถใช้กรรมวิธีข้างต้นหาการแปลงเฮาส์โฮลเดอร์ ที่ทำให้

และ , , , ที่มีผลเช่นเดียวกันกับ , , , ตามลำดับ และเมื่อเราให้

สำหรับ แล้ว เราจะได้ว่า

เป็นเมทริกซ์สามเหลี่ยมด้านบน ดังนั้น

และเนื่องจาก ทุกตัวเป็นเมทริกซ์ฮาส์โฮลเดอร์ซึ่งเป็นเมทริกซ์เชิงตั้งฉาก ทำให้ เป็นเมทริกซ์เชิงตั้งฉากตามไปด้วย จึงเป็นการแยก QR ตามที่เราต้องการ

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

อ้างอิง

[แก้]
  • Alston S. Householder, Unitary Triangularization of a Nonsymmetric Matrix, Journal ACM, 5 (4), 1958, 339-342. DOI:10.1145/320941.320947
  • David D. Morrison, Remarks on the Unitary Triangularization of a Nonsymmetric Matrix, Journal ACM, 7 (2), 1960, 185-186. DOI:10.1145/321021.321030