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

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

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

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

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

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

${\displaystyle Q=I-2vv^{T}}$ .

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

• มันเป็นเมทริกซ์สมมาตร: ${\displaystyle Q=Q^{T}}$ 
• มันเป็นเมทริกซ์เชิงตั้งฉาก: ${\displaystyle Q^{-1}=Q^{T}}$ 
• ดังนั้นมันจึงเป็นอาวัตนาการ: ${\displaystyle Q^{2}=I}$ .

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

${\displaystyle Qx=x-2vv^{T}x=x-2\langle v,x\rangle v}$ ,

เมื่อ ${\displaystyle \langle v,x\rangle }$  คือผลคูณจุดของ ${\displaystyle x}$  และ ${\displaystyle v}$  ซึ่งมีค่าเท่ากับระยะห่างของจุดปลายที่ไม่ใช่จุดกำเนิดของ ${\displaystyle x}$  จากระนาบเกินที่ตั้งฉากกับ ${\displaystyle v}$  ด้วยเหตุนี้จุดปลายที่ไม่ใช่จุดกำเนิดของ ${\displaystyle Qx}$  จึงอยู่คนละข้างของระนาบเกินกับจุดปลายของ ${\displaystyle x}$  และห่างจากระนาบเกินเท่ากับระยะห่างจากจุดปลายของ ${\displaystyle x}$  กับระนาบเกิน กล่าวคือเป็นภาพสะท้อนของ ${\displaystyle x}$  นั่นเอง

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

ในการแยก QR เราต้องการเขียนเมทริกซ์ ${\displaystyle A_{n\times n}}$  ที่ำกำหนดให้ในรูป ${\displaystyle A=QR}$  โดย ${\displaystyle Q}$  เป็นเมทริกซ์เชิงตั้งฉากและ ${\displaystyle R}$  เป็นเมทริกซ์สามเหลี่ยมด้านบน เราสามารถใช้การแปลงเฮาส์โฮลเดอร์ในการคำนวณ ${\displaystyle Q}$  และ ${\displaystyle R}$  ได้ดังต่อไปนี้

ให้ ${\displaystyle e_{1}}$  แทนเวกเตอร์ ${\displaystyle (1,0,\dots ,0)^{T}}$  ที่มีศูนย์อยู่ ${\displaystyle n}$  ตัว ให้ ${\displaystyle \|x\|}$  แทนนอร์มของเวกเตอร์ ${\displaystyle x}$  ใดๆ และให้ ${\displaystyle a_{1}}$  เป็นเวกเตอร์หลักที่ 1 ของ ${\displaystyle A}$  แล้ว กำหนด

${\displaystyle v_{1}=a_{1}-\|a_{1}\|e_{1}}$ 

และ

${\displaystyle Q_{1}=I_{n}-2{\frac {v_{1}v_{1}^{T}}{\|v_{1}\|^{2}}}}$ 

(${\displaystyle I_{n}}$  คือเมทริกซ์เอกลักษณ์ขนาด ${\displaystyle n\times n}$ ) เป็นการแปลงเฮาส์โฮลเดอร์ที่สะท้อนเวกเตอร์กับระนาบเกินที่ตั้งฉากกับ ${\displaystyle v_{1}}$  แล้ว เราจะได้ว่า

${\displaystyle Q_{1}a_{1}=\|a_{1}\|e_{1}}$ 

หรือ

${\displaystyle Q_{1}A={\begin{bmatrix}\|a_{1}\|&\star &\dots &\star \\0&&&\\\vdots &&A'_{2}&\\0&&&\end{bmatrix}}}$ 

โดยที่ ${\displaystyle A'_{2}}$  เป็นเมทริกซ์ขนาด ${\displaystyle (n-1)\times (n-1)}$  กล่าวคือ ${\displaystyle Q_{1}}$  ทำให้หลักแรกของ ${\displaystyle A}$  มีสมาชิกที่ไม่ใช่ศูนย์อยู่เพียงตัวเดียว

เราสามารถใช้กรรมวิธีข้างต้นหาการแปลงเฮาส์โฮลเดอร์ ${\displaystyle Q'_{2}}$  ที่ทำให้

${\displaystyle Q_{1}A'_{2}={\begin{bmatrix}\star &\star &\dots &\star \\0&&&\\\vdots &&A'_{3}&\\0&&&\end{bmatrix}}}$ 

และ ${\displaystyle Q'_{3}}$ , ${\displaystyle Q'_{4}}$ , ${\displaystyle \dots }$ , ${\displaystyle Q'_{n-1}}$  ที่มีผลเช่นเดียวกันกับ ${\displaystyle A'_{3}}$ , ${\displaystyle A'_{4}}$ , ${\displaystyle \dots }$ , ${\displaystyle A'_{n-1}}$  ตามลำดับ และเมื่อเราให้

${\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}}$ 

สำหรับ ${\displaystyle 2\leq k\leq n-1}$  แล้ว เราจะได้ว่า

${\displaystyle Q_{n-1}Q_{n-2}\cdots Q_{2}Q_{1}A={\begin{bmatrix}\|a_{1}\|&\star &\star &\dots &\star &\star \\0&\star &\star &\dots &\star &\star \\0&0&\star &\dots &\star &\star \\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\0&0&0&0&\star &\star \\0&0&0&0&0&\star \end{bmatrix}}=R}$ 

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

${\displaystyle A=(Q_{n-1}Q_{n-2}\cdots Q_{1})^{-1}R=Q_{1}Q_{2}\cdots Q_{n-1}R}$ 

และเนื่องจาก ${\displaystyle Q_{i}}$  ทุกตัวเป็นเมทริกซ์ฮาส์โฮลเดอร์ซึ่งเป็นเมทริกซ์เชิงตั้งฉาก ทำให้ ${\displaystyle Q=Q_{1}Q_{2}\cdots Q_{n-1}}$  เป็นเมทริกซ์เชิงตั้งฉากตามไปด้วย ${\displaystyle A=QR}$  จึงเป็นการแยก 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