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

การแปลงเฮาส์โฮลเดอร์ (Householder transformation) ในคณิตศาสตร์ และในปริภูมิสามมิติ เป็นการสะท้อนเวกเตอร์กับระนาบ ในปริภูมิยูคลิเดียนทั่วไป การแปลงเฮาส์โฮลเดอร์เป็นการแปลงเชิงเส้นซึ่งเวกเตอร์กับระนาบเกินที่ผ่านจุดกำเนิด
อัลสตัน สกอตต์ เฮาส์โฮลเดอร์ ตีพิมพ์ผลงานเกี่ยวกับการแปลงชนิดนี้เป็นครั้งแรกในปี พ.ศ. 2501 การแปลงเฮาส์โฮลเดอร์เป็นเครื่องมือสำคัญในการหาการแยก QR ของเมทริกซ์
== นิยามและสมบัติ ==
ระนาบเกินที่จะใช้สะท้อนเวกเตอร์นั้นสามารถแทนได้โดยเวกเตอร์หนึ่งหน่วย v ซึ่งตั้งฉากกับระนาบเกินนั้น
ถ้า I คือเมทริกซ์เอกลักษณ์ การแปลงเชิงเส้นที่กล่าวในบทนำของบทความนี้สามารถแทนใดโดยเมทริกซ์เฮาส์โฮลเดอร์
Q = I - 2 vv^T.
โดยแมทริกซ์เฮาส์โฮลเดอร์มีสมบัติดังต่อไปนี้
มันเป็นเมทริกซ์สมมาตร: Q = Q^T
มันเป็นเมทริกซ์เชิงตั้งฉาก: Q^{-1}=Q^T
ดังนั้นมันจึงเป็นอาวัตนาการ: Q^2=I.
และ Q สะท้อนเวกเตอร์ x ใดๆ กับระนาบเกินที่ตั้งฉากกับ v โดยข้อความนี้สามารถแสดงให้เห็นจริงได้โดยสมการ
Qx = x-2vv^Tx = x - 2\langle v,x\rangle v,
เมื่อ \langle v,x\rangle คือผลคูณจุดของ 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 ตัว ให้ \| x\| แทนนอร์มของเวกเตอร์ x ใดๆ และให้ a_1 เป็นเวกเตอร์หลักที่ 1 ของ A แล้ว กำหนด
v_1 = a_1 - \| a_1 \|e_1 
และ
Q_1 = I_n - 2\frac{v_1v_1^T}{\| v_1 \|^2}
(I_n คือเมทริกซ์เอกลักษณ์ขนาด n \times n) เป็นการแปลงเฮาส์โฮลเดอร์ที่สะท้อนเวกเตอร์กับระนาบเกินที่ตั้งฉากกับ v_1 แล้ว เราจะได้ว่า
Q_1a_1 = \| a_1 \|e_1
หรือ
Q_1 A = \begin{bmatrix}
\| a_1 \| &\star&\dots&\star\\
0    &     &     &    \\
\vdots  &     &  A'_2 &    \\
0    &     &     & \end{bmatrix}
โดยที่ A'_2 เป็นเมทริกซ์ขนาด (n-1) \times (n-1) กล่าวคือ Q_1 ทำให้หลักแรกของ A มีสมาชิกที่ไม่ใช่ศูนย์อยู่เพียงตัวเดียว
เราสามารถใช้กรรมวิธีข้างต้นหาการแปลงเฮาส์โฮลเดอร์ Q'_2 ที่ทำให้
Q_1 A'_2 = \begin{bmatrix}
\star &\star&\dots&\star\\
0    &     &     &    \\
\vdots  &     &  A'_3 &    \\
0    &     &     & \end{bmatrix}
และ Q'_3, Q'_4, \dots, Q'_{n-1} ที่มีผลเช่นเดียวกันกับ A'_3, A'_4, \dots, A'_{n-1} ตามลำดับ และเมื่อเราให้
Q_k = \begin{bmatrix} I_{k-1} & 0\\ 0 & Q_k'\end{bmatrix}
สำหรับ 2 \leq k \leq n-1 แล้ว เราจะได้ว่า
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
เป็นเมทริกซ์สามเหลี่ยมด้านบน ดังนั้น
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
เรขาคณิต
พีชคณิตเชิงเส้น
เมทริกซ์