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

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

อัลสตัน สกอตต์ เฮาส์โฮลเดอร์ ตีพิมพ์ผลงานเกี่ยวกับการแปลงชนิดนี้เป็นครั้งแรกในปี พ.ศ. 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

หมวดหมู่:เรขาคณิต
หมวดหมู่:พีชคณิตเชิงเส้น
หมวดหมู่:เมทริกซ์