วิธีการสลับแถวในเมทริกซ์ L เมื่อสลายเมทริกซ์ A เป็น PA = LU
ค้นหาเมทริกซ์การเปลี่ยนแปลง $P$เมทริกซ์สามเหลี่ยมล่าง $L$ และเมทริกซ์สามเหลี่ยมด้านบน $U$ ดังนั้น $$ PA=LU $$ ให้ $$ A= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ -2 & -3 & -4 & -5 & -6 & -7 \\ 3 & 7 & 11 & 16 & 21 & 27 \\ -4 & -5 & -5 & -5 & -5 & -5 \end{pmatrix}$$
ฉันมาไกลขนาดนี้
$$ U = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 2 & 3 & 4 \end{pmatrix}$$ และ $$ L= \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & 1 & 1 & 0 \\ -4 & 3 & 0 & 1 \end{pmatrix}$$ ขั้นตอนสุดท้ายที่ฉันต้องทำคือเปลี่ยนแถวที่สี่ด้วยแถวที่สาม แต่ฉันไม่รู้ว่าจะเปลี่ยนรายการในเมทริกซ์สามเหลี่ยมด้านล่าง L ได้อย่างไรใครสามารถอธิบายสิ่งที่ฉันต้องเปลี่ยนเป็น L ได้บ้าง
คำตอบ
คำตอบแบบยาว:ลองนึกถึงผลลัพธ์ของการกำจัดไปข้างหน้าว่าเป็นสมการเมทริกซ์ของรูปแบบ$U=E_r P_r E_{r-1} P_{r-1} \dots E_1 P_1 A$ ที่ไหน $E_i$ เป็นเมทริกซ์ "การกำจัด" (การล้างคอลัมน์ด้านล่างของ $i$หมุนไปตามปกติ) และ $P_i$ เป็นเมทริกซ์การเปลี่ยนแปลงที่ย้ายไฟล์ $i$หมุนไปที่ $i$หรืออื่น ๆ ที่เป็นเอกลักษณ์ (หากคุณไม่ได้ทำการแลกเปลี่ยนในขั้นตอนนั้น) เมทริกซ์การกำจัดเป็นรูปสามเหลี่ยมที่ต่ำกว่าและคงอยู่อย่างนั้นเมื่อคูณเข้าด้วยกัน แต่เมื่อรวมเมทริกซ์การเรียงสับเปลี่ยนพวกมันจะหยุดเป็นรูปสามเหลี่ยมที่ต่ำกว่า
ตอนนี้คุณมักจะต้องการกลับด้านของผลิตภัณฑ์นั้น $E_i P_i$ เพื่อแยก $A$. หากคุณรวมทั้งหมดเข้าด้วยกันสิ่งผกผันจะไม่เป็นรูปสามเหลี่ยมที่ต่ำกว่าซึ่งอยู่ใน$PA=LU$คุณต้องการให้เป็น ดังนั้นสิ่งที่คุณทำแทนคือคุณเขียนผลิตภัณฑ์ใหม่$E_r P_r \dots E_1 P_1$เพื่อให้เมทริกซ์การเปลี่ยนแปลงทั้งหมดอยู่ทางขวาและเมทริกซ์การกำจัดทั้งหมดจะอยู่ทางซ้าย ในการทำเช่นนั้นก็เพียงพอที่จะคิดออกว่าจะเขียนอย่างไร$PE$ เช่น $E' P'$.
ซึ่งสามารถทำได้ด้วย $P'=P$ และ $E'=P E P^{-1} = P E P^T$ง่ายต่อการตรวจสอบ: $E' P'=P E P^{-1} P=PE$. นี้$E'$ การใช้แบบฟอร์มนี้เป็นตัวอย่างของสถานการณ์ทั่วไปในพีชคณิตซึ่งการผันคำกริยาถูกใช้เพื่อใช้การดำเนินการ "ในบริบท" ของการดำเนินการแบบกลับด้านได้ถูกนำไปใช้แล้ว
การทำเช่นนั้นซ้ำแล้วซ้ำอีกคุณสามารถย้ายเมทริกซ์การเรียงสับเปลี่ยนทั้งหมดไปทางขวา ผลลัพธ์มีลักษณะดังนี้:
$$U=E_r (P_r E_{r-1}^T P_r^T) \cdot ((P_r P_{r-1}) E_{r-2} (P_r P_{r-1})^T) \cdot \dots \cdot ((P_r \dots P_2) E_1 (P_r \dots P_2)^T) \\ \cdot P_r \cdot \dots \cdot P_1 \cdot A.$$
ตอนนี้
$$L^{-1}=E_r (P_r E_{r-1} P_r^T) \cdot ((P_r P_{r-1}) E_{r-2} (P_r P_{r-1})^T) \cdot \dots \cdot ((P_r \dots P_2) E_1 (P_r \dots P_2)^T)$$
นี่หมายความว่าอะไรโดยสรุป? ก็หมายความว่าจะได้รับที่ถูกต้อง$L^{-1}$คุณต้องย้ายรายการที่ไม่สำคัญใน "computed $L^{-1}$"ตามการแลกเปลี่ยนแถวทั้งหมดที่คุณทำหลังจากคำนวณรายการเหล่านั้นแล้ว Inverting$L^{-1}$ ในตอนท้ายยังคงใช้งานได้เหมือนเดิม (คุณเพียงแค่พลิกเครื่องหมายบนรายการที่ไม่สำคัญ)
ดังนั้นในตัวอย่างของคุณผลของการสลับแถว $3$ และ $4$ คือคุณอัปเดต $L$ โดยการแลกเปลี่ยนบทบาทของดัชนี $3$ และ $4$, ที่เกิดขึ้นใน:
$$L=\begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -4 & 3 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{pmatrix}.$$
โปรดทราบว่าสิ่งนี้ไม่เหมือนกับการแลกเปลี่ยนแถวเท่านั้น$3$ ด้วยแถว $4$.
หลังจากนั้นคุณทำเสร็จแล้วในตัวอย่างนี้ แต่ถ้าคุณไม่เป็นเช่นนั้นคุณจะไม่แลกเปลี่ยน$3$ ด้วย $4$ ในขั้นตอนต่อไป
คำตอบสั้น ๆ :เมทริกซ์สุดท้ายของคุณ$P$บรรลุการแลกเปลี่ยนแถวทั้งหมดที่คุณทำ ที่จะได้รับ$L$ทุกครั้งที่คุณทำการแลกเปลี่ยนแถวซึ่งจะทำได้โดยการคูณทางด้านซ้ายด้วยเมทริกซ์การเรียงสับเปลี่ยน $P$คุณแทนที่ปัจจุบันของคุณ $L$ ด้วย $P L P^T$ซึ่งหมายความว่าคุณทำการเรียงสับเปลี่ยนทั้งในแถวและในคอลัมน์ปัจจุบันของคุณ $L$ (แต่ไม่ใช่ในรอบสุดท้าย $L$).
โดยใช้การลดแถวเรามาถึงที่
$$U = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 1 & 2 & 4 \\ 0 & 0 & 1 & 2 & 3 & 4 \end{pmatrix}$$
ในฐานะที่เป็นวิธีอื่นในการเขียนที่ยอดเยี่ยมโดย @Ian (+1) คุณสามารถย้อนกลับขั้นตอนการลดแถวรวมถึงการสลับได้เช่น $$A = E_1^{-1}E_2^{-1}E_3^{-1}E_4^{-1}U$$
ซึ่งส่งผลให้
$$L = \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ 3 & 1 &0 & 1 \\ -4 & 3 & 1 & 0 \end{pmatrix}$$
เราเห็นว่า $L$ ไม่ใช่รูปสามเหลี่ยมด้านล่างและเราเพียงแค่ต้องสลับแถวที่สามและสี่ส่งผลให้
$$L = \begin{pmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -4 & 3 & 1 & 0 \\3 & 1 &0 & 1\end{pmatrix}$$
การแลกเปลี่ยนนั้นต้องใช้เมทริกซ์การเปลี่ยนแปลง
$$P = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 &0 & 1 \\ 0 & 0 & 1 &0\end{pmatrix}$$
ตอนนี้เราสามารถตรวจสอบได้
$$PA = LU$$
คุณยังตรวจสอบได้อีกด้วย $$A = PLU = P^T LU = P^{-1} LU$$
ดูตัวอย่างเช่นการแยกตัวประกอบของ LU ในเมทริกซ์ที่ไม่ใช่กำลังสองได้อย่างไร?