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

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

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

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

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

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

$Q=I-2v{v}^T$.

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

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

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

$Qx=x-2v{v}^{T}x=x-2⟨v,x⟩v$,

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

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

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

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

$v_1=a_1-\Vert a_1\Vert e_1$

และ

$Q_1=I_n-2\frac{v_1{v}_1^T}{\Vert v_1{\Vert }^2}$

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

$Q_1{a}_1=\Vert a_1\Vert e_1$

หรือ

$Q_{1}A=\left[\begin{array}{cccc}\Vert a_1\Vert & \star & \dots & \star \\ 0& & & \\ ⋮& & A{\text{'}}_2& \\ 0& & & \end{array}\right]$

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

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

$Q_{1}A{\text{'}}_2=\left[\begin{array}{cccc}\star & \star & \dots & \star \\ 0& & & \\ ⋮& & A{\text{'}}_3& \\ 0& & & \end{array}\right]$

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

$Q_k=\left[\begin{array}{cc}{I}_{k-1}& 0\\ 0& {Q_k}^{\prime }\end{array}\right]$

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

$Q_{n-1}{Q}_{n-2}\cdots Q_2{Q}_{1}A=\left[\begin{array}{cccccc}\Vert a_1\Vert & \star & \star & \dots & \star & \star \\ 0& \star & \star & \dots & \star & \star \\ 0& 0& \star & \dots & \star & \star \\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& 0& \star & \star \\ 0& 0& 0& 0& 0& \star \end{array}\right]=R$

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

$A=(Q_{n-1}{Q}_{n-2}\cdots Q_1{)}^{-1}R=Q_1{Q}_2\cdots Q_{n-1}R$

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