A.7 · การแยก LU และ Nullity ของฟังก์ชันประกอบ

เตรียมสอบ GRE ระดับปริญญาตรี วัตถุประสงค์ภายในขอบเขต ETS ที่ทบทวนนี้คือการสอนต้นฉบับ ไม่ใช่การทดสอบหรือตัวทำนายคะแนนอย่างเป็นทางการ

ความรู้ก่อนหน้า: การดำเนินการตามแถว ระบบสามเหลี่ยม และ rank-nullity

• แก้ระบบเชิงเส้นที่แยกตัวประกอบด้วยการแทนค่าไปข้างหน้าและถอยหลัง
• ใช้การสลับแถวอย่างสม่ำเสมอเมื่อต้องการ pivoting
• กำหนดขอบเขตมิติของเคอร์เนลจากการประกอบโดยใช้อินเตอร์เซกชันระหว่างอิมเมจและเคอร์เนล

การแทนค่าไปข้างหน้า (forward substitution): การแก้ระบบสมการสามเหลี่ยมล่างโดยเริ่มจากสมการแรกแล้วทำลง haciaล่าง

นัลลิตี้ (nullity): มิติของเคอร์เนลของฟังก์ชันเชิงเส้น

การแยกตัวประกอบ A=LU แสดงว่าเมทริกซ์กำลังเป็นผลคูณของเมทริกซ์สามเหลี่ยมล่าง L และสามเหลี่ยมบน U เมื่อ L มีหลักdiagเป็นหนึ่ง การแทนค่าไปข้างหน้าจะง่ายเป็นพิเศษ เมทริกซ์ที่กลับได้ไม่จำเป็นต้องมีรูปแบบนี้โดยไม่มีการแลกเปลี่ยนแถว หากพิกัดนำเป็นศูนย์อาจต้องใช้การสลับตำแหน่ง สำหรับ PA=LU ให้แก้ Ly=Pb ก่อน แล้วแก้ Ux=y การสลับตำแหน่งมีผลทั้งต่อฝั่งขวาและเมทริกซ์สัมประสิทธิ์ พิกัดนำหลักที่ไม่เป็นศูนย์เป็นการยืนยันวิธีกำจัดแบบไม่แลกเปลี่ยน ซึ่งไม่ใช่แค่ความกลับได้เท่านั้น

ในสมการ Ly=b คำนวณ y จากบนลงล่าง โดยลบพจน์ที่ทราบแล้วออก แล้วหารด้วยหลักdiagปัจจุบันเว้นแต่จะเป็นหนึ่ง ในสมการ Ux=y คำนวณ x จากล่างขึ้นบน สำหรับแต่ละสมการให้แทนค่ากลับเข้าไปในแถวเดิมเพื่อตรวจสอบ การใช้ LU ซ้ำหลายครั้งสำหรับฝั่งขวาต่าง ๆ ช่วยหลีกเลี่ยงการกำจัดซ้ำ การแยกตัวประกอบหนาแน่นใช้เวลาระดับลูกบาศก์ตามมิติ ในขณะที่การแก้ระบบสามเหลี่ยมแต่ละครั้งใช้เวลาเพียงระดับกำลังสอง การคำนวณที่แม่นยำสามารถตรวจสอบตัวอย่างเล็ก ๆ ได้ แต่การเลือกพิกัดทางตัวเลขช่วยลดปัญหาการปัดเศษได้บางส่วนแต่ไม่สามารถขจัดความไวต่อการรบกวน inherent ได้

For B:V→W and A:W→Z, ker B is contained in ker(A∘B), but the latter can be larger. Extra vectors are those mapped by B into ker A. Restrict B to ker(A∘B): its image is im B∩ker A and its kernel is ker B. Rank-nullity on this restricted map gives dim ker(A∘B)=dim ker B+dim(im B∩ker A). The intersection, not the whole kernel of A, determines the extra nullity.

สำหรับ endomorphisms ของ R⁶ ที่มี nullity A=2 และ nullity B=3, rank B=3 และมิติอินเตอร์เซกชันสามารถอยู่ระหว่าง 0 ถึง 2 ดังนั้น nullity ของ A∘B จะอยู่ในช่วง 3 ถึง 5 ขอบเขตขึ้นอยู่กับพื้นที่กลางร่วม: สำหรับสับสเปซที่มีมิติ r และ s ในสเปซที่มีมิติ m อินเตอร์เซกชันจะมีมิติระหว่าง max(0,r+s−m) และ min(r,s) การกลับลำดับการประกอบสามารถเปลี่ยน nullity ได้ แม้ว่าจะมี AB และ BA ทั้งคู่ก็ตาม ควรเลือกสเปซที่สอดคล้องกันก่อนใช้สูตรเหล่านี้

ให้ L=[[1,0,0],[2,1,0],[−1,3,1]], U=[[2,1,−1],[0,3,2],[0,0,4]], และ b=(−1,−1,12) การแทนค่าหน้าให้ y=(−1,1,8) การแทนค่าหลังให้ x₃=2, x₂=(1−4)/3=−1, และ x₁=(−1−(−1)+2)/2=1 ดังนั้น x=(1,−1,2) การคูณ Ux ได้ y และการคูณ Ly ได้ b ตรวจสอบลำดับการแยกตัวประกอบได้อย่างอิสระ

แก้สมการโดยเริ่มจาก L ก่อนและ U หลัง และสลับ b หาก PA=LU Nullity ของฟังก์ชันประกอบไม่ได้เป็นผลรวมของ nullity ทั้งสองโดยอัตโนมัติ; เฉพาะผลตัดกันระหว่าง image กับ kernel เท่านั้นที่เพิ่มเข้าไปใน nullity ของ B

ให้ $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$, $U=\begin{pmatrix}3&1\\0&2\end{pmatrix}$ และ $b=(5,12)^T$ แก้ LUx=b และตรวจสอบในเมทริกซ์ที่คูณกัน สำหรับ PA=LU เมื่อแก้ Ax=b P จะมีผลต่อส่วนไหน?

วิธีทำตัวอย่าง

ขั้นแรกแก้ Ly=b: $y_1=5$, $2y_1+y_2=12$, จะได้ $y_2=2$ จากนั้น Ux=y ให้ $x_2=1$ และ $3x_1+1=5$, ดังนั้น $x_1=4/3$ เมทริกซ์ผลคูณคือ $A=\begin{pmatrix}3&1\\6&4\end{pmatrix}$; นำไปใช้กับ $(4/3,1)^T$ จะได้ $(5,12)^T$ หาก PA=LU ให้คูณสมการเดิมด้วย P แล้วแก้ Ly=Pb ตามด้วย Ux=y การละ P ออกจาก b จะทำให้แก้ระบบที่ต่างกัน

ให้ A และ B เป็น endomorphisms ของ $\mathbb R^5$ ที่มี nullities เท่ากับสองและสาม ตามลำดับ จงหา nullities ทั้งหมดที่เป็นไปได้ของ AB พร้อมอธิบายทั้งขอบเขตและการบรรลุค่าเหล่านั้น

ตรวจสอบหลังทำแบบฝึกหัดแล้ว

Rank B เท่ากับสอง จำกัด B ที่ $\ker(AB)$ เพื่อได้

The two subspaces in the intersection both have dimension two in five dimensions, so intersection dimension may be zero, one or two. Thus nullity is 3, 4 or 5. To realise each, take $\ker A=\operatorname{span}(e_1,e_2)$ and image B respectively $\operatorname{span}(e_3,e_4)$, $\operatorname{span}(e_1,e_3)$ or $\operatorname{span}(e_1,e_2)$. Choose any rank-two B onto that image. These constructions prove attainability rather than only a loose interval bound.