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

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

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

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

นิยามและสมบัติ[แก้]

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

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

Q = I - 2 vv^T.

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

และ 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