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

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

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

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

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

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

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

Q = I - 2 v v 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$ ด้วยเหตุนี้จุดปลายที่ไม่ใช่จุดกำเนิดของ $Q x$ จึงอยู่คนละข้างของระนาบเกินกับจุดปลายของ $x$ และห่างจากระนาบเกินเท่ากับระยะห่างจากจุดปลายของ $x$ กับระนาบเกิน กล่าวคือเป็นภาพสะท้อนของ $x$ นั่นเอง

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

ในการแยก QR เราต้องการเขียนเมทริกซ์ $A_{n \times n}$ ที่ำกำหนดให้ในรูป $A = Q R$ โดย $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 = Q R$ จึงเป็นการแยก QR ตามที่เราต้องการ

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