ในการวิเคราะห์เชิงตัวเลขและพีชคณิตเชิงเส้นการแยกตัวประกอบล่าง-บน ( LU ) หรือการแยกตัวประกอบจะแยกเมทริกซ์ ออก เป็นผลคูณของเมทริกซ์สามเหลี่ยม ล่าง และเมทริกซ์สามเหลี่ยมบน (ดูการคูณเมทริกซ์และการแยกตัวประกอบเมทริกซ์ ) บางครั้งผลคูณอาจรวม ถึง เมทริกซ์การเรียงสับเปลี่ยนด้วย การแยกตัวประกอบ LU สามารถมองได้ว่าเป็นรูปแบบเมทริกซ์ของการกำจัดแบบเกาส์เซียนคอมพิวเตอร์มักจะแก้ระบบ สมการเชิงเส้นกำลังสอง โดยใช้การแยกตัวประกอบ LU และยังเป็นขั้นตอนสำคัญเมื่อทำการผกผันเมทริกซ์หรือคำนวณดีเทอร์มิแนนต์ของเมทริกซ์ บางครั้งก็เรียกว่า การแยกตัวประกอบ LR (แยกตัวประกอบเป็นเมทริกซ์สามเหลี่ยมซ้ายและขวา) อัลกอริทึมการแยกตัวประกอบ LU สำหรับเมทริกซ์ทั่วไปได้รับการแนะนำโดยนักดาราศาสตร์ชาวโปแลนด์Tadeusz Banachiewiczในปี 1938 ^{[ 1 ]}

ให้Aเป็นเมทริกซ์จัตุรัสการแยกตัวประกอบ LUหมายถึงการแสดงAออกมาเป็นผลคูณของตัวประกอบสองตัว คือ เมทริกซ์สามเหลี่ยมล่างLและเมทริกซ์สามเหลี่ยมบนUโดยที่A = LUบางครั้งการแยกตัวประกอบเป็นไปไม่ได้หากไม่มีการเรียงลำดับใหม่ของA ก่อน เพื่อป้องกันการหารด้วยศูนย์หรือการเพิ่มขึ้นของข้อผิดพลาดจากการปัดเศษอย่างควบคุมไม่ได้ ดังนั้นการแสดงออกทางเลือกจึงเป็นPAQ = LUโดยที่ในสัญลักษณ์อย่างเป็นทางการตัวประกอบเมทริกซ์การเรียงสับเปลี่ยนPและQแสดงถึงการเรียงสับเปลี่ยนแถว (หรือคอลัมน์) ของAในทางทฤษฎีP (หรือQ ) ได้มาจากการเรียงสับเปลี่ยนแถว (หรือคอลัมน์) ของเมทริกซ์เอกลักษณ์ในทางปฏิบัติ การเรียงสับเปลี่ยนที่สอดคล้องกันจะถูกนำไปใช้โดยตรงกับแถว (หรือคอลัมน์) ของ A

เมทริกซ์Aที่มีด้านยาวnมีสัมประสิทธิ์ ในขณะที่เมทริกซ์สามเหลี่ยมสองเมทริกซ์รวมกันมี สัมประสิทธิ์ n ( n + 1) ตัวดังนั้น สัมประสิทธิ์ nตัวของเมทริกซ์LU จึง ไม่เป็นอิสระต่อกัน ตามธรรมเนียมแล้วจะกำหนดให้Lเป็นเมทริกซ์สามเหลี่ยมหน่วย กล่าวคือ มีองค์ประกอบแนวทแยงหลักทั้งnตัวเท่ากับหนึ่ง อย่างไรก็ตาม การกำหนดให้Uเป็นเมทริกซ์สามเหลี่ยมหน่วยแทน จะลดลงเหลือขั้นตอนเดียวกันหลังจากสลับแถวและคอลัมน์ของผลคูณเมทริกซ์ (ดูคุณสมบัติของการสลับแถวและคอลัมน์ของเมทริกซ์): หลังจากสลับแถวและคอลัมน์แล้วU ^T จะเป็นเมทริกซ์สามเหลี่ยมล่าง ในขณะที่L ^Tจะเป็นเมทริกซ์สามเหลี่ยมหน่วยบนที่เป็นตัวประกอบของBสิ่งนี้แสดงให้เห็นว่าการดำเนินการกับแถว (เช่น การสลับแถว) เทียบเท่ากับการดำเนินการกับคอลัมน์ของเมทริกซ์ที่สลับแถวและคอลัมน์แล้ว และโดยทั่วไปแล้วการเลือกใช้อัลกอริทึมกับแถวหรือคอลัมน์นั้นไม่มีข้อได้เปรียบใดๆ ${\displaystyle n^{2}}$$${\displaystyle B=A^{\textsf {T}}=(LU)^{\textsf {T}}=U^{\textsf {T}}L^{\textsf {T}}.}$$

ในเมทริกซ์สามเหลี่ยมล่าง องค์ประกอบทั้งหมดที่อยู่เหนือเส้นทแยงมุมหลักจะเป็นศูนย์ ในเมทริกซ์สามเหลี่ยมบน องค์ประกอบทั้งหมดที่อยู่ใต้เส้นทแยงมุมจะเป็นศูนย์ ตัวอย่างเช่น สำหรับเมทริกซ์3 × 3การแยกตัวประกอบ LU จะมีลักษณะดังนี้: $${\displaystyle {\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}}={\begin{bmatrix}\ell _{11}&0&0\\\ell _{21}&\ell _{22}&0\\\ell _{31}&\ell _{32}&\ell _{33}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{bmatrix}}.}$$

หากไม่มีการเรียงลำดับหรือการเรียงสับเปลี่ยนที่เหมาะสมในเมทริกซ์ การแยกตัวประกอบอาจไม่เกิดขึ้น ตัวอย่างเช่น สามารถตรวจสอบได้ง่าย (โดยการขยายการคูณเมทริกซ์ ) ว่าถ้าแล้วอย่างน้อยหนึ่งในและต้องเป็นศูนย์ ซึ่งหมายความว่าLหรือU อย่างใดอย่างหนึ่ง เป็นเมทริก ซ์เอกฐาน ซึ่งเป็นไปไม่ได้หากAเป็นเมทริกซ์ไม่เอกฐาน (ผกผันได้) ในแง่ของการดำเนินการ การทำให้เป็นศูนย์/การกำจัดองค์ประกอบที่เหลือของคอลัมน์แรกของAเกี่ยวข้องกับการหารด้วยซึ่งเป็นไปไม่ได้หาก เป็น 0 นี่เป็นปัญหาเชิงกระบวนการ สามารถแก้ไขได้โดยการเรียงลำดับแถวของA ใหม่ เพื่อให้องค์ประกอบแรกของเมทริกซ์ที่เรียงสับเปลี่ยนแล้วไม่เป็นศูนย์ ปัญหาเดียวกันในขั้นตอนการแยกตัวประกอบในภายหลังสามารถแก้ไขได้ด้วยวิธีเดียวกัน เพื่อความเสถียรเชิงตัวเลขต่อข้อผิดพลาดจากการปัดเศษ/การหารด้วยจำนวนน้อย สิ่งสำคัญคือต้องเลือก ที่ มีค่าสัมบูรณ์มาก(ดูการสลับแกน) ${\textstyle a_{11}=\ell _{11}u_{11}}$${\textstyle a_{11}=0}$${\textstyle \ell _{11}}$${\textstyle u_{11}}$${\textstyle a_{21},a_{31}}$${\textstyle a_{11}}$${\textstyle a_{11}}$

ตัวอย่าง เมทริกซ์ 3 × 3 ข้างต้น แสดงให้เห็นว่า ผลคูณเมทริกซ์ของแถวบนสุดและคอลัมน์ซ้ายสุดของเมทริกซ์ที่เกี่ยวข้องมีบทบาทพิเศษต่อความสำเร็จ ของ LU ให้เรากำหนดเวอร์ชันที่ต่อเนื่องกันของเมทริกซ์ด้วย และจากนั้นเขียนผลคูณเมทริกซ์ในลักษณะที่แถวและคอลัมน์เหล่านี้แยกออกจากส่วนที่เหลือ ในการทำเช่นนั้น เราจะใช้ สัญกรณ์ เมทริกซ์บล็อกเช่นเป็นจำนวนธรรมดาเป็นเวกเตอร์แถวเป็นเวกเตอร์คอลัมน์ และเป็นเมทริกซ์ย่อยของเมทริกซ์ที่ไม่มีแถวบนสุดและคอลัมน์ซ้ายสุด จากนั้นเราสามารถแทนที่ ด้วย ผลคูณเมทริกซ์ บล็อกกล่าวคือ ปรากฏว่าเราสามารถคูณบล็อกเมทริกซ์ในลักษณะราวกับว่าเป็นจำนวนธรรมดา กล่าวคือ แถวคูณคอลัมน์ ยกเว้นว่าตอนนี้ส่วนประกอบของพวกมันเป็นเมทริกซ์ย่อย บางครั้งลดรูปเป็นสเกลาร์หรือเวกเตอร์ ดังนั้น จึงหมายถึงเวกเตอร์ที่ได้จากหลังจากคูณแต่ละส่วนประกอบด้วยจำนวนคือผล คูณ ภายนอกของเวกเตอร์ กล่าวคือเมทริกซ์ที่มีคอลัมน์แรกเป็นถัดไปเป็นและอื่นๆ สำหรับส่วนประกอบทั้งหมดของ และคือผลคูณของเมทริกซ์ย่อยของ${\displaystyle (0),\;(1),\dots }$${\displaystyle A\equiv A^{(0)}=L^{(0)}U^{(0)}}$${\displaystyle a\equiv a_{11}}$${\displaystyle {\bf {w}}^{\textsf {T}}\equiv (a_{12},a_{13})^{\textsf {T}}}$${\displaystyle {\bf {v}}=(a_{21},a_{31})}$${\displaystyle A'}$${\displaystyle A^{(0)}}$${\displaystyle A^{(0)}=L^{(0)}U^{(0)}}$${\displaystyle u{\bf {l}}}$${\displaystyle {\bf {l}}}$${\displaystyle u}$${\displaystyle {\bf {lu}}^{\textsf {T}}}$${\displaystyle {\bf {l,u}}}$${\displaystyle u_{12}{\bf {l}}}$${\displaystyle u_{13}{\bf {l}}}$${\displaystyle {\bf {u}}}$${\displaystyle L^{(1)}คุณ^{(1)}}$${\displaystyle L^{(0)},\;U^{(0)}}$$${\displaystyle {\begin{aligned}\left({\begin{array}{c|c}a&{\bf {w}}^{\textsf {T}}\\\hline \\[-0.5em]{\bf {v}}&\quad A'\quad \\[-0.5em]\\\end{array}}\right)&=\left({\begin{array}{c|c}{\rm {1}}&{\bf {0}}^{\textsf {T}}\\\hline \\[-0.5em]{\bf {l}}&\quad L^{(1)}\quad \\[-0.5em]\\\end{array}}\right)\;\left({\begin{array}{c|c}u&{\bf {u}}^{\textsf {T}}\\\hline \\[-0.5em]{\bf {0}}&\quad U^{(1)}\\[-0.5em]\\\end{array}}\right)\\&=\left({\begin{array}{c|c}u&{\bf {u}}^{\textsf {T}}\\\hline \\[-0.5em]u{\bf {l}}&\quad {\bf {lu}}^{\textsf {T}}+L^{(1)}U^{(1)}\\[-0.5em]\\\end{array}}\right)\end{aligned}}}$$

จากความเท่าเทียมกันของเมทริกซ์แรกและเมทริกซ์สุดท้าย จะได้ผลลัพธ์สุดท้ายคือ, ,ในขณะที่เมทริกซ์จะได้รับการอัปเดต/แทนที่ด้วย ตอน นี้มาถึงข้อสังเกตที่สำคัญ: ไม่มีอะไรขัดขวางไม่ให้เราดำเนินการในลักษณะเดียวกับที่เราทำกับซ้ำๆ กัน หากมิติของคือn × nหลังจากn − 1ขั้นตอนดังกล่าว คอลัมน์ทั้งหมดจะประกอบเป็นส่วนย่อยแนวทแยงของเมทริกซ์สามเหลี่ยมและจุดหมุนทั้งหมดที่รวมกับแถวจะประกอบเป็นเมทริกซ์สามเหลี่ยมด้านบนตามที่ต้องการ ในตัวอย่างข้างต้นn = 3ดังนั้นจึงใช้เพียงสองขั้นตอนก็เพียงพอแล้ว ${\displaystyle u=a}$${\displaystyle {\bf {u=w}}}$${\displaystyle {\bf {l}}={(1/a)}{\bf {v}}}$${\displaystyle A'}$${\displaystyle A^{(1)}\equiv L^{(1)}U^{(1)}=}$${\displaystyle A'-{\bf {lu}}^{\textsf {T}}}$${\displaystyle A^{(1)}}$${\displaystyle A^{(0)}}$${\displaystyle A}$${\displaystyle {\bf {v}}}$${\displaystyle L}$${\displaystyle a}$${\displaystyle {\bf {w}}^{\textsf {T}}}$${\displaystyle U}$

ขั้นตอนข้างต้นแสดงให้เห็นว่าในทุกขั้นตอน ค่าตัวหลักแนวทแยงมุมบนสุดของเมทริกซ์ย่อยที่อยู่ติดกันจะต้องไม่เป็นศูนย์ เพื่อหลีกเลี่ยงปัญหานี้ อาจสลับคอลัมน์หรือแถวเพื่อให้ค่าตัวหลักไม่เป็นศูนย์ ขั้นตอนดังกล่าวที่เกี่ยวข้องกับการเรียงสับเปลี่ยนเรียกว่าLUP ( Level of Power) หรือการแยกส่วนโดยใช้ตัวหลัก (Decomposition with Pivoting) ${\displaystyle a}$${\displaystyle a}$

การเรียงสับเปลี่ยนคอลัมน์สอดคล้องกับผลคูณเมทริกซ์โดยที่เป็นเมทริกซ์การเรียงสับเปลี่ยน กล่าวคือ เมทริกซ์เอกลักษณ์หลังจากการเรียงสับเปลี่ยนคอลัมน์เดียวกัน หลังจากขั้นตอนทั้งหมด การแยกส่วน LUP ดังกล่าวจะนำไปใช้กับแผนการคำนวณปัจจุบันและที่คล้ายกันใน Cormen et al. ^{[ 2 ]}เป็นตัวอย่างของอัลกอริธึมแบบเวียนเกิดซึ่งแสดงให้เห็นคุณสมบัติทั่วไปสองประการของการแยกตัวประกอบ LU: ${\displaystyle AQ^{(0)}}$${\displaystyle Q^{(0)}}$${\displaystyle I}$${\displaystyle AQ^{(0)}\cdots Q^{(n-1)}\equiv AQ=LU}$

อัลกอริทึมแบบเวียนเกิดนั้นไม่สิ้นเปลืองทรัพยากรในการคำนวณทางพีชคณิตมากนัก แต่ก็มีข้อเสียในทางปฏิบัติเนื่องจากจำเป็นต้องอัปเดตและจัดเก็บค่าส่วนใหญ่ของเมทริกซ์Aในแต่ละขั้นตอน จะเห็นได้ว่าการจัดลำดับการคำนวณใหม่จะช่วยลดความจำเป็นในการจัดเก็บค่าระหว่างกลางได้

ปรากฏว่าการเรียงสับเปลี่ยนแถว (หรือคอลัมน์) ที่เหมาะสมเพื่อเลือกคอลัมน์ (หรือแถว) ที่มีค่าสูงสุดสัมบูรณ์ของตัวหมุนa ₁₁นั้นเพียงพอสำหรับการแยกตัวประกอบ LU ที่เสถียรทางตัวเลข ยกเว้นกรณีที่ผิดปกติที่ทราบกันดี เรียกว่าการแยกตัวประกอบ LU ด้วยการหมุนบางส่วน (LUP): โดยที่LและUเป็นเมทริกซ์สามเหลี่ยมล่างและบนอีกครั้ง และPและQเป็นเมทริกซ์การเรียงสับเปลี่ยน ที่สอดคล้องกัน ซึ่งเมื่อคูณทางซ้ายและขวาตามลำดับกับAจะเรียงลำดับแถวและคอลัมน์ของAใหม่ ปรากฏว่าเมทริกซ์จัตุรัสทั้งหมดสามารถแยกตัวประกอบได้ในรูปแบบนี้^{[ 3 ]}และการแยกตัวประกอบนั้นเสถียรทางตัวเลขในทางปฏิบัติ^{[ 4 ]}ทำให้การแยกตัวประกอบ LUP เป็นเทคนิคที่มีประโยชน์ในทางปฏิบัติ $${\displaystyle PA=LU,\quad (AQ=LU),}$$

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

การแยกตัวประกอบ LU ด้วยการสลับตำแหน่งแบบเต็มเกี่ยวข้องกับการเรียงสับเปลี่ยนทั้งแถวและคอลัมน์เพื่อค้นหาองค์ประกอบสูงสุดสัมบูรณ์ในเมทริกซ์ย่อยทั้งหมด โดยที่L , UและPถูกกำหนดไว้ก่อนหน้านี้ และQเป็นเมทริกซ์การเรียงสับเปลี่ยนที่จัดเรียงคอลัมน์ของAใหม่^{[ 5 ]}$${\displaystyle PAQ=LU,}$$

การแยกส่วนแบบล่าง-แนวทแยง-บน (LDU) คือการแยกส่วนในรูปแบบ ที่Dเป็นเมทริกซ์แนวทแยงและLกับUเป็นเมทริกซ์สามเหลี่ยมเอกภาคซึ่งหมายความว่าค่าทุกค่าบนแนวทแยงของLและUเป็นหนึ่ง $${\displaystyle A=LDU,}$$

ข้างต้นเรากำหนดให้Aเป็นเมทริกซ์จัตุรัส แต่การแยกส่วนเหล่านี้สามารถขยายไปสู่เมทริกซ์สี่เหลี่ยมผืนผ้าได้เช่นกัน^{[ 6 ]}ในกรณีนั้นLและDเป็นเมทริกซ์จัตุรัสซึ่งมีจำนวนแถวเท่ากับAและUมีมิติเท่ากับA ทุกประการ 'เมทริกซ์สามเหลี่ยมบน' ควรตีความว่ามีเพียงรายการศูนย์ที่อยู่ด้านล่างเส้นทแยงมุมหลัก ซึ่ง เริ่ม ต้นที่มุมบนซ้าย ในทำนองเดียวกัน คำที่แม่นยำกว่าสำหรับUคือรูปแบบขั้นบันไดแถวของเมทริกซ์A

เราแยกตัวประกอบ เมทริกซ์ 2 × 2 ต่อไปนี้ : $${\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}\ell _{11}&0\\\ell _{21}&\ell _{22}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}.}$$

วิธีหนึ่งในการหาการแยกตัวประกอบ LU ของเมทริกซ์อย่างง่ายนี้คือการแก้สมการเชิงเส้นโดยการตรวจสอบโดยตรง การขยายการคูณเมทริกซ์จะได้ $${\displaystyle \left\{{\begin{alignedat}{4}\ell _{11}\cdot u_{11}&&\;+\;&&0\cdot 0&&\;=\;&&4\\\ell _{11}\cdot u_{12}&&\;+\;&&0\cdot u_{22}&&\;=\;&&3\\\ell _{21}\cdot u_{11}&&\;+\;&&\ell _{22}\cdot 0&&\;=\;&&6\\\ell _{21}\cdot u_{12}&&\;+\;&&\ell _{22}\cdot u_{22}&&\;=\;&&3\end{alignedat}}\right.}$$

ระบบสมการนี้มีตัวกำหนดไม่ครบในกรณีนี้ สมาชิกที่ไม่เป็นศูนย์สองตัวใดๆ ของเมทริกซ์LและU จะเป็นพารามิเตอร์ของคำตอบ และสามารถกำหนดให้เป็นค่าที่ไม่เป็นศูนย์ใดๆ ก็ได้ ดังนั้น เพื่อหาการแยกตัวประกอบ LU ที่ไม่ซ้ำกัน จำเป็นต้องกำหนดข้อจำกัดบางอย่างให้กับเมทริกซ์ LและUตัวอย่างเช่น เราสามารถกำหนดให้เมทริกซ์สามเหลี่ยมล่างLเป็นเมทริกซ์สามเหลี่ยมเอกลักษณ์ได้ ซึ่งหมายความว่าค่าทั้งหมดในแนวทแยงมุมหลักของเมทริกซ์ L จะเป็นหนึ่ง จากนั้นระบบสมการจะมีคำตอบดังต่อไปนี้: $${\displaystyle {\begin{aligned}\ell _{11}&=\ell _{22}=1\\\ell _{21}&=1.5\\u_{11}&=4\\u_{12}&=3\\u_{22}&=-1.5\end{aligned}}}$$

เมื่อแทนค่าเหล่านี้ลงในการแยกตัวประกอบ LU ข้างต้น จะได้ผลลัพธ์ดังนี้ $${\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}1&0\\1.5&1\end{bmatrix}}{\begin{bmatrix}4&3\\0&-1.5\end{bmatrix}}.}$$

เมทริกซ์จัตุรัสใดๆAยอมรับการแยกตัวประกอบ LUP และ PLU ^{[ 3 ]}ถ้าAสามารถผกผันได้มันจะยอมรับการแยกตัวประกอบ LU (หรือ LDU) ก็ต่อเมื่อไมเนอร์หลักนำหน้าทั้งหมดไม่เป็นศูนย์^{[ 7 ] [ 8 ]} (ตัวอย่างเช่นไม่ยอมรับการแยกตัวประกอบ LU หรือ LDU) ถ้าAเป็นเมทริกซ์เอกฐานที่มีอันดับkมันจะยอมรับการแยกตัวประกอบ LU ถ้า ไมเนอร์หลักนำหน้า k ตัวแรก ไม่เป็นศูนย์ แม้ว่าในทางกลับกันจะไม่เป็นจริงก็ตาม^{[ 9 ]}$\left[{\begin{smallmatrix}0&1\\1&0\end{smallmatrix}}\right]$

ถ้าเมทริกซ์จัตุรัสที่ผกผันได้มีการแยกตัวประกอบ LDU (โดยที่ค่าในแนวทแยงมุมทั้งหมดของLและUเท่ากับ1 ) การแยกตัวประกอบนั้นจะเป็นเอกลักษณ์^{[ 8 ]}ในกรณีนั้น การแยกตัวประกอบ LU ก็จะเป็นเอกลักษณ์เช่นกัน หากเรากำหนดให้แนวทแยงมุมของLหรือUประกอบด้วยเลขหนึ่ง

โดยทั่วไป เมทริกซ์จัตุรัสA _{ขนาด n × n} ใดๆ อาจมีคุณสมบัติอย่างใดอย่างหนึ่งดังต่อไปนี้:

1. การแยกตัวประกอบ LU ที่เป็นเอกลักษณ์ (ดังที่กล่าวไว้ข้างต้น)
2. การแยกตัวประกอบ LU มีจำนวนอนันต์ หากคอลัมน์แรก( n − 1)คอลัมน์ใด ๆ มีความสัมพันธ์เชิงเส้น
3. ไม่สามารถแยกตัวประกอบ LU ได้หากคอลัมน์แรก( n − 1)เป็นอิสระเชิงเส้นและอย่างน้อยหนึ่งไมเนอร์หลักนำหน้าเป็นศูนย์

ในกรณีที่ 3 เราสามารถประมาณการแยกตัวประกอบ LU ได้โดยการเปลี่ยนรายการแนวทแยงa _ijเป็น a _ij ± εเพื่อหลีกเลี่ยงไมเนอร์หลักนำที่เป็นศูนย์^{[ 10 ]}

ถ้าAเป็นเมทริกซ์สมมาตร (หรือ เมทริกซ์ เฮอร์มิเชียนถ้าAเป็นจำนวนเชิงซ้อน) ที่เป็นบวกแน่นอนเราสามารถจัดเรียงให้Uเป็นเมทริกซ์สลับเปลี่ยนเชิงสังยุคของLได้ นั่นคือ เราสามารถเขียนAได้ดังนี้ $${\displaystyle A=LL^{*}\,.}$$

การแยกส่วนนี้เรียกว่าการแยกส่วนแบบโคลสกี้ (Cholesky decomposition ) ถ้าเมท ริก ซ์ Aเป็นเมทริกซ์บวกแน่นอน (positive definite) การแยกส่วนแบบโคลสกี้จะมีอยู่และมีเพียงหนึ่งเดียว นอกจากนี้ การคำนวณการแยกส่วนแบบโคลสกี้มีประสิทธิภาพและเสถียรทางตัวเลขมากกว่าการคำนวณการแยกส่วนแบบ LU อื่นๆ บางแบบ

สำหรับเมทริกซ์ (ไม่จำเป็นต้องผกผันได้) บนฟิลด์ใดๆ เงื่อนไขที่จำเป็นและเพียงพอที่แน่นอนภายใต้ซึ่งมีการแยกตัวประกอบ LU นั้นเป็นที่ทราบกันดี เงื่อนไขเหล่านี้แสดงออกมาในรูปของอันดับของเมทริกซ์ย่อยบางส่วน อัลกอริทึมการกำจัดแบบเกาส์เซียนสำหรับการได้มาซึ่งการแยกตัวประกอบ LU ได้รับการขยายไปสู่กรณีทั่วไปที่สุดนี้ด้วย^{[ 11 ]}

เมื่อมีการแยกตัวประกอบ LDU อยู่และเป็นเอกลักษณ์ จะมีสูตรปิด (ชัดเจน) สำหรับองค์ประกอบของL , DและUในรูปของอัตราส่วนของดีเทอร์มิแนนต์ของเมทริกซ์ย่อยบางส่วนของเมทริกซ์Aดั้งเดิม^{[ 12 ]}โดยเฉพาะอย่างยิ่งD ₁ = A _1,1และสำหรับi = 2, ... , n , D _iคืออัตราส่วนของ เมทริกซ์ย่อยหลักที่ iต่อ เมทริกซ์ย่อยหลักที่ ( i − 1)การคำนวณดีเทอร์มิแนนต์มีค่าใช้จ่ายในการคำนวณสูงดังนั้นสูตรที่ชัดเจนนี้จึงไม่ได้ใช้ในทางปฏิบัติ

อัลกอริทึมต่อไปนี้เป็นรูปแบบที่ดัดแปลงมาจากการกำจัดแบบเกาส์เซียนการคำนวณการแยกตัวประกอบ LU โดยใช้อัลกอริทึมนี้ต้องใช้⁠2/3⁠ การดำเนินการจุดลอยตัว ^{3 ครั้ง}โดยไม่สนใจพจน์ลำดับต่ำกว่าการสลับแกน บางส่วน จะเพิ่มพจน์กำลังสองเท่านั้น ซึ่งไม่เป็นเช่นนั้นสำหรับการสลับแกนแบบเต็ม ^{[ 13 ]}

กำหนดเมทริกซ์N × Nให้เป็นเวอร์ชันดั้งเดิมที่ไม่ได้รับการแก้ไขของเมทริกซ์A ตัวยกในวงเล็บ (เช่น(0) ) ของเมทริกซ์Aคือเวอร์ชันของเมทริกซ์ เมทริกซ์A ^{( n )}คือ เมทริกซ์ Aที่องค์ประกอบด้านล่างแนวทแยงหลักถูกกำจัดให้เป็น 0 แล้วโดยใช้การกำจัดแบบเกาส์เซียนสำหรับnคอลัมน์ แรก${\displaystyle A=(a_{i,j})_{1\leq i,j\leq N}}$${\displaystyle A^{(0)}}$

ด้านล่างนี้คือเมทริกซ์ที่จะช่วยให้เราจำสัญลักษณ์นี้ได้ (โดยที่* แต่ละ ตัวแทนจำนวนจริง ใดๆ ในเมทริกซ์):

${\displaystyle A^{(n-1)}={\begin{pmatrix}*&&&\cdots &&&*\\0&\ddots &&&&\\&\ddots &*&&&\\\vdots &&0&a_{n,n}^{(n-1)}&&&\vdots \\&&\vdots &a_{i,n}^{(n-1)}&*\\&&&\vdots &\vdots &\ddots \\0&\cdots &0&a_{i,n}^{(n-1)}&*&\cdots &*\end{pmatrix}}}$

ในระหว่างกระบวนการนี้ เราจะค่อยๆ ปรับเปลี่ยนเมทริกซ์Aโดยใช้การดำเนินการแถว จนกระทั่งกลายเป็นเมทริกซ์Uซึ่งองค์ประกอบทั้งหมดที่อยู่ใต้เส้นทแยงมุมหลักมีค่าเท่ากับศูนย์ ในขณะเดียวกัน เราจะสร้างเมทริกซ์แยกกันสองเมทริกซ์คือP และ L โดยที่PA = LU

เรากำหนดเมทริกซ์การเรียงสับเปลี่ยน สุดท้าย Pให้เป็นเมทริกซ์เอกลักษณ์ที่มีแถวทั้งหมดเหมือนกันแต่สลับลำดับเดียวกันกับ เมทริกซ์ Aในขณะที่แปลงเป็นเมทริกซ์Uสำหรับเมทริกซ์A ^{( n −1)} ของเรา เราอาจเริ่มต้นด้วยการสลับแถวเพื่อให้ได้เงื่อนไขที่ต้องการสำหรับ คอลัมน์ที่ nตัวอย่างเช่น เราอาจสลับแถวเพื่อทำการสลับแถวบางส่วน หรือเราอาจทำเช่นนั้นเพื่อกำหนดให้องค์ประกอบหลักa _n,nบนแนวทแยงมุมหลักเป็นจำนวนที่ไม่เป็นศูนย์ เพื่อให้เราสามารถทำการกำจัดแบบเกาส์เซียนให้เสร็จสมบูรณ์ได้

สำหรับเมทริกซ์A ^{( n −1)} ของเรา เราต้องการตั้งค่าองค์ประกอบทุกตัวด้านล่างให้เป็นศูนย์ (โดยที่คือองค์ประกอบใน คอลัมน์ที่ nของแนวทแยงหลัก) เราจะกำหนดองค์ประกอบแต่ละตัวด้านล่างเป็น(โดยที่i = n +1, ... , N ) ในการตั้งค่าให้เป็นศูนย์ เราจะกำหนดแถว_i = แถว_i − ( ℓ _i,n )⋅ แถว_nสำหรับแต่ละแถวiสำหรับการดำเนินการนี้.เมื่อเราทำการดำเนินการแถวสำหรับ คอลัมน์ N − 1 แรก เสร็จ แล้ว เราจะได้เมทริกซ์สามเหลี่ยมบนA ^{( N −1)}ซึ่งกำหนดโดยU${\displaystyle a_{n,n}^{(n-1)}}$${\displaystyle a_{n,n}^{(n-1)}}$${\displaystyle a_{n,n}^{(n-1)}}$${\displaystyle a_{i,n}^{(n-1)}}$${\displaystyle a_{i,n}^{(n-1)}}$${\textstyle \ell _{i,n}:={a_{i,n}^{(n-1)}}/{a_{n,n}^{(n-1)}}}$

เราสามารถสร้าง เมทริกซ์ สามเหลี่ยมล่างซึ่งแทนด้วยL ได้ โดยการป้อนค่าℓ _i,n ที่คำนวณไว้ก่อนหน้านี้โดยตรง ผ่านสูตรด้านล่าง

$${\displaystyle L={\begin{pmatrix}1&0&\cdots &0\\\ell _{2,1}&\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &0\\\ell _{N,1}&\cdots &\ell _{N,N-1}&1\end{pmatrix}}}$$

ถ้าเราได้รับเมทริกซ์ เราจะเลือกที่จะใช้การสลับแถวบางส่วนและสลับแถวแรกและแถวที่สองเพื่อให้เมทริกซ์A ของเราและเมทริกซ์ Pในรอบแรกของเรากลายเป็น ตามลำดับ เมื่อเราสลับแถวแล้ว เราสามารถกำจัดองค์ประกอบที่อยู่ใต้เส้นทแยงมุมหลักในคอลัมน์แรกได้โดยดำเนินการ ดังนี้ เมื่อลบแถวเหล่านี้ออกแล้ว เราจะได้เมทริกซ์ จาก A ⁽¹⁾$${\displaystyle A={\begin{pmatrix}0&5&{\frac {22}{3}}\\4&2&1\\2&7&9\\\end{pmatrix}},}$$$${\displaystyle A^{(0)}={\begin{pmatrix}4&2&1\\0&5&{\frac {22}{3}}\\2&7&9\\\end{pmatrix}},\quad P^{(0)}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\\\end{pmatrix}}.}$$$${\displaystyle {\begin{alignedat}{0}row_{2}=row_{2}-(\ell _{2,1})\cdot row_{1}\\row_{3}=row_{3}-(\ell _{3,1})\cdot row_{1}\end{alignedat}}}$$$${\displaystyle {\begin{alignedat}{0}\ell _{2,1}={\frac {0}{4}}=0\\\ell _{3,1}={\frac {2}{4}}=0.5\end{alignedat}}}$$$${\displaystyle A^{(1)}={\begin{pmatrix}4&2&1\\0&5&{\frac {22}{3}}\\0&6&8.5\\\end{pmatrix}}.}$$

เนื่องจากเรากำลังดำเนินการสลับแถวบางส่วน เราจึงสลับแถวที่สองและสามของเมทริกซ์ที่ได้มาและ เมทริกซ์ P เวอร์ชันปัจจุบันของเรา ตามลำดับ เพื่อให้ได้ จากนั้น เรากำจัดองค์ประกอบที่อยู่ใต้เส้นทแยงมุมหลักในคอลัมน์ที่สองโดยดำเนินการแถวที่₃ = แถวที่₃ − ( ℓ _3,2 )⋅ แถวที่₂โดยที่ℓ _3,2 = ⁠$${\displaystyle A^{(1)}={\begin{pmatrix}4&2&1\\0&6&8.5\\0&5&{\frac {22}{3}}\\\end{pmatrix}},\quad P^{(1)}={\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\\\end{pmatrix}}.}$$5/6เนื่องจากไม่มีองค์ประกอบที่ไม่เป็นศูนย์อยู่ใต้เส้นทแยงมุมหลักในการวนซ้ำปัจจุบันของเมทริกซ์ Aหลังจากการลบแถวนี้ การลบแถวนี้จึงได้ เมทริกซ์ A สุดท้าย (แทนด้วย U ) และ เมทริกซ์ P สุดท้าย : หลังจากสลับแถวที่สอดคล้องกันแล้ว เราจะได้ เมทริกซ์ L สุดท้าย : $${\displaystyle A^{(2)}=A^{(N-1)}=U={\begin{pmatrix}4&2&1\\0&6&8.5\\0&0&0.25\\\end{pmatrix}},\quad P={\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\\\end{pmatrix}}.}$$$${\displaystyle L={\begin{pmatrix}1&0&0\\\ell _{3,1}&1&0\\\ell _{2,1}&\ell _{3,2}&1\\\end{pmatrix}}={\begin{pmatrix}1&0&0\\0.5&1&0\\0&{\frac {5}{6}}&1\\\end{pmatrix}}}$$

เมท ริกซ์เหล่านี้มีความสัมพันธ์กันในลักษณะที่ว่าPA = LU

หากเราไม่สลับแถวเลยในระหว่างกระบวนการนี้ เราสามารถดำเนินการกับแถวพร้อมกันสำหรับแต่ละคอลัมน์nโดยกำหนดให้เป็นเมท ริกซ์เอกลักษณ์ N × Nที่ คอลัมน์ ที่ nถูกแทนที่ด้วยเวกเตอร์ทรานสโพส(0 ⋯ 0 1 − ℓ _{n +1, n}   ⋯  − ℓ _{N , n} ) ^T${\displaystyle A^{(n)}:=L_{n}^{-1}A^{(n-1)},}$${\displaystyle L_{n}^{-1}}$

กล่าวอีกนัยหนึ่งคือ เมทริกซ์สามเหลี่ยมล่าง $${\displaystyle L_{n}^{-1}={\begin{pmatrix}1&&&&&\\&\ddots &&&&\\&&1&&&\\&&-\ell _{n+1,n}&&&\\&&\vdots &&\ddots &\\&&-\ell _{N,n}&&&1\end{pmatrix}}.}$$

การดำเนินการแถวทั้งหมดสำหรับคอลัมน์แรกN − 1คอลัมน์โดยใช้ สูตร นั้น เทียบเท่ากับการหาการแยกส่วน โดยกำหนดให้L = L ₁ ⋯ L _{N −1}ดังนั้นA = LA ^{( N −1)} = LU${\displaystyle A^{(n)}:=L_{n}^{-1}A^{(n-1)}}$$${\displaystyle A=L_{1}L_{1}^{-1}A^{(0)}=L_{1}A^{(1)}=L_{1}L_{2}L_{2}^{-1}A^{(1)}=L_{1}L_{2}A^{(2)}=\dotsm =L_{1}\dotsm L_{N-1}A^{(N-1)}.}$$

ต่อไปเรามาคำนวณลำดับของL ₁ ⋯ L _{N −1}กัน เราทราบว่าL _iมีสูตรดังต่อไปนี้: $${\displaystyle L_{n}={\begin{pmatrix}1&&&&&\\&\ddots &&&&\\&&1&&&\\&&\ell _{n+1,n}&&&\\&&\vdots &&\ddots &\\&&\ell _{N,n}&&&1\end{pmatrix}}}$$

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

${\displaystyle \left({\begin{array}{ccccc}1&0&0&0&0\\77&1&0&0&0\\12&0&1&0&0\\63&0&0&1&0\\7&0&0&0&1\end{array}}\right)\left({\begin{array}{ccccc}1&0&0&0&0\\0&1&0&0&0\\0&22&1&0&0\\0&33&0&1&0\\0&44&0&0&1\end{array}}\right)=\left({\begin{array}{ccccc}1&0&0&0&0\\77&1&0&0&0\\12&22&1&0&0\\63&33&0&1&0\\7&44&0&0&1\end{array}}\right)}$

สุดท้าย คูณL ₁เข้าด้วยกันและสร้างเมทริกซ์ที่รวมกันซึ่งแสดงด้วยL (ดังที่กล่าวไว้ก่อนหน้านี้) โดยใช้เมทริกซ์Lเราจะได้ A = LU

เป็นที่ชัดเจนว่าเพื่อให้ขั้นตอนวิธีนี้ทำงานได้ จำเป็นต้องมีเงื่อนไขในแต่ละขั้นตอน (ดูคำจำกัดความของℓ _i,n ) หากเงื่อนไขนี้ไม่เป็นจริงในบางจุด จำเป็นต้องสลับ แถวที่ n กับแถวอื่นที่อยู่ด้านล่างก่อนดำเนินการต่อ นี่คือเหตุผล ที่ การแยกตัวประกอบ LU โดยทั่วไปมีลักษณะเป็นP ⁻¹ A = LU${\displaystyle a_{n,n}^{(n-1)}\neq 0}$

แม้ว่าอัลกอริทึมการแยกตัวประกอบ LU ของ Banachiewicz (1938) จะมาก่อนการมาถึงของคอมพิวเตอร์อิเล็กทรอนิกส์แบบโปรแกรมได้ แต่ก็พร้อมสำหรับการนำไปใช้ในโค้ดโดยตรง เนื่องจากฟังก์ชันการสลับดัชนี การสลับแถวและคอลัมน์ และการคูณแบบคอลัมน์ต่อคอลัมน์ยังคงเป็นความสามารถพื้นฐานของภาษาโปรแกรมส่วนใหญ่ และคอมไพเลอร์จะจัดการฟังก์ชันเหล่านี้เองโดยแทบไม่มีความล่าช้าในการประมวลผลจริง สัญกรณ์เมทริกซ์ที่ Banachiewicz ใช้ทำให้เขาสามารถคูณเมทริกซ์แบบคอลัมน์ต่อคอลัมน์ ซึ่งเป็นคุณสมบัติที่สะดวกสำหรับการคำนวณเชิงกล เนื่องจากเขาสามารถเปิดเผยตัวประกอบที่ต่อเนื่องกันได้โดยการเลื่อนไม้บรรทัดไปยังแถวถัดไปของเมทริกซ์ อย่างไรก็ตาม สำหรับผู้อ่านที่เป็นมนุษย์ สมการของเขาจะดีที่สุดหากแปลงเป็นสัญกรณ์เมทริกซ์มาตรฐาน เพื่อให้ได้เมทริกซ์สามเหลี่ยมUและL จากเมทริกซ์ A ที่สมบูรณ์ ให้เริ่มต้นด้วยการคัดลอกแถวบนสุดและคอลัมน์ซ้ายสุดของAไปยังตำแหน่งที่สอดคล้องกันของเมทริกซ์UและL ตาม ลำดับ องค์ประกอบแนวทแยงมุมหน่วยที่ทราบของLจะไม่ถูกจัดเก็บหรือใช้ตลอดกระบวนการทั้งหมด การคำนวณต่อไปจะดำเนินต่อไปสำหรับแถวและคอลัมน์ถัดไปจนถึงมุมล่างขวาของA

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

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

อัลก อริ ทึม LU แบบ pivoting บางส่วนทั้งหมดมีค่าใช้จ่ายโดยประมาณเท่ากัน คือจำนวนการดำเนินการ โดยที่nคือจำนวนแถวหรือคอลัมน์ของA${\textstyle O\left({2 \over 3}n^{3}\right)}$

โปรดสังเกตว่าการแยกส่วนประกอบที่ได้จากกระบวนการนี้คือ การแยกส่วนประกอบแบบดูลิตเติล ( Doolittle decomposition ) กล่าวคือ เส้นทแยงมุมหลักของ เมทริก ซ์ Lประกอบด้วยเลข 1 เพียงอย่างเดียว หากเราดำเนินการโดยการลบองค์ประกอบ ที่ อยู่เหนือเส้นทแยงมุมหลักโดยการบวกผลคูณของคอลัมน์ (แทนที่จะลบองค์ประกอบที่อยู่ใต้เส้นทแยงมุมโดยการบวกผลคูณของแถว ) เราจะได้การแยก ส่วนประกอบ แบบครูท (Crout decomposition ) ซึ่งเส้นทแยงมุมหลักของเมทริก ซ์ Uประกอบด้วยเลข 1 เพียงอย่างเดียว

อีกวิธีหนึ่ง (ที่เทียบเท่ากัน) ในการสร้างการแยกส่วนแบบ Crout ของเมทริกซ์A ที่กำหนดให้ คือ การหาการแยกส่วนแบบ Doolittle ของเมทริกซ์สลับตำแหน่งของAแท้จริงแล้ว ถ้าA ^T = L ₀ U ₀คือการแยกส่วนแบบ LU ที่ได้จากอัลกอริทึมที่นำเสนอในส่วนนี้ แล้วโดยการใช้L = U^ที₀และU = L^ที₀เราทราบว่าA = LUเป็นการแยกตัวประกอบแบบ Crout

เป็นไปได้ที่จะค้นหาการประมาณอันดับต่ำของการแยกส่วน LU โดยใช้อัลกอริทึมแบบสุ่มเมื่อกำหนดเมทริกซ์อินพุตAและอันดับต่ำที่ต้องการkการแยกส่วน LU แบบสุ่มจะส่งคืนเมทริกซ์การเรียงสับเปลี่ยนP , Qและเมทริกซ์สี่เหลี่ยมคางหมูล่าง/บนL , Uที่มีขนาดm × kและk × nตามลำดับ โดยมีความน่าจะเป็นสูง ที่ ‖ PAQ − LU ‖ ₂ ≤ Cσ _{k +1}โดยที่Cเป็นค่าคงที่ที่ขึ้นอยู่กับพารามิเตอร์ของอัลกอริทึม และσ _{k +1}คือ ค่าเอกพจน์ลำดับที่ ( k +1)ของเมทริกซ์^{อินพุต} A [ ^{14 ]}

^{ถ้าเมทริกซ์สองเมทริก ซ์}ที่มีอันดับnสามารถคูณกันได้ในเวลาM ( n )โดยที่M ( n ) ≥ n ^aสำหรับบางa > 2แล้วการแยกส่วน LU สามารถคำนวณได้ในเวลาO( M ( n )) [ ^{15 ]}ซึ่งหมายความว่า ตัวอย่างเช่น มีอัลกอริทึม O( n ^2.376 )ที่ใช้พื้นฐานจากอัลกอริทึม Coppersmith–Winogradดูบทความเกี่ยวกับอัลกอริทึมการคูณเมทริกซ์ที่รวดเร็วสำหรับรายละเอียดเพิ่มเติม

มีการพัฒนาอัลกอริทึมพิเศษสำหรับการแยกตัวประกอบเมทริกซ์แบบเบาบาง ขนาดใหญ่ อัลกอริทึมเหล่านี้พยายามค้นหาตัวประกอบแบบเบาบางLและUโดยในอุดมคติแล้ว ต้นทุนในการคำนวณจะถูกกำหนดโดยจำนวนรายการที่ไม่เป็นศูนย์ มากกว่าขนาดของเมทริกซ์

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

การจัดการลำดับที่ลดช่องว่างให้น้อยที่สุดโดยทั่วไป สามารถทำได้โดยใช้ทฤษฎีกราฟ

กำหนดให้ระบบสมการเชิงเส้นในรูปแบบเมทริกซ์ $${\displaystyle A\mathbf {x} =\mathbf {b} ,}$$

เราต้องการแก้สมการหาค่าx โดยกำหนดค่าAและbให้ สมมติว่าเราได้การแยกส่วน LUP ของA แล้ว โดยที่PA = LUดังนั้นLU x = P b

ในกรณีนี้ วิธีแก้ปัญหาจะดำเนินการตามขั้นตอนเชิงตรรกะสองขั้นตอน:

1. ขั้นแรก เราแก้สมการL y = P bสำหรับy
2. ประการ ที่สอง เราแก้สมการU x = yสำหรับx

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

ขั้นตอนข้างต้นสามารถนำมาใช้ซ้ำได้หลายครั้งเพื่อแก้สมการสำหรับค่า b ที่แตกต่างกัน ในกรณีนี้ การแยกตัวประกอบ LU ของเมทริกซ์Aเพียงครั้งเดียวแล้วแก้เมทริกซ์สามเหลี่ยมสำหรับค่าb ที่แตกต่างกันนั้นเร็วกว่า (และสะดวกกว่า) การใช้การกำจัดแบบเกาส์เซียนทุกครั้ง เมทริกซ์LและUอาจถือได้ว่า "เข้ารหัส" กระบวนการกำจัดแบบเกาส์เซียนไว้แล้ว

ค่าใช้จ่ายในการแก้ระบบสมการเชิงเส้นโดยประมาณคือ⁠2/3ใช้การคำนวณเลขทศนิยม n³ ครั้ง หากเมทริกซ์ Aมีขนาดnซึ่งทำให้เร็วกว่าอัลกอริทึมที่ใช้การแยกส่วน QRโดยมีค่าใช้จ่ายประมาณ n³^{ครั้ง}4/3⁠การดำเนินการจุดลอยตัว ^{3 ครั้ง}เมื่อใช้การสะท้อนของ Householder ^{ด้วยเหตุนี้จึงมักนิยมการแยกส่วน LU มากกว่า [ 16 ]}

เมื่อแก้ระบบสมการbมักถูกมองว่าเป็นเวกเตอร์ที่มีความยาวเท่ากับความสูงของเมทริกซ์Aอย่างไรก็ตาม ในการผกผันเมทริกซ์ แทนที่จะใช้เวกเตอร์bเราจะใช้เมทริกซ์Bโดยที่Bเป็น เมทริกซ์ขนาด n × pดังนั้นเราจึงพยายามหาเมทริกซ์X (ซึ่งเป็น เมทริกซ์ขนาด n × p เช่นกัน ) $${\displaystyle AX=LUX=B.}$$

เราสามารถใช้อัลกอริทึมเดียวกันกับที่นำเสนอไว้ก่อนหน้านี้เพื่อแก้ปัญหาแต่ละคอลัมน์ของเมทริกซ์Xสมมติว่าBเป็นเมทริกซ์เอกลักษณ์ขนาดn , I _nดังนั้นผลลัพธ์Xจะต้องเป็นเมทริกซ์ผกผันของA ^{[ 17 ]}

เมื่อกำหนดการแยกส่วน LUP ของเมทริกซ์จัตุรัสA เป็น A = P ⁻¹ LU แล้ว ดีเทอร์มิแนนต์ของAสามารถคำนวณได้โดยตรงดังนี้ $${\displaystyle {\begin{aligned}\det(A)&=\det \left(P^{-1}\right)\det(L)\det(U)\\&=(-1)^{S}\left(\prod _{i=1}^{n}l_{ii}\right)\left(\prod _{i=1}^{n}u_{ii}\right).\end{aligned}}}$$

สมการที่สองเป็นผลมาจากข้อเท็จจริงที่ว่าดีเทอร์มิแนนต์ของเมทริกซ์สามเหลี่ยมคือผลคูณของสมาชิกในแนวทแยงมุม และดีเทอร์มิแนนต์ของเมทริกซ์การเรียงสับเปลี่ยนเท่ากับ(−1) ^Sโดยที่Sคือจำนวนการสลับแถวในการแยกส่วน

ในกรณีของการแยกตัวประกอบ LU ด้วยการสลับแถวและคอลัมน์อย่างสมบูรณ์det( A )จะเท่ากับด้านขวาของสมการข้างต้นเช่นกัน หากเรากำหนดให้Sเป็นจำนวนการสลับแถวและคอลัมน์ทั้งหมด

วิธีการเดียวกันนี้สามารถนำไปใช้กับการแยกตัวประกอบ LU ได้อย่างง่ายดาย โดยการกำหนดให้Pเท่ากับเมทริกซ์เอกลักษณ์

การแยกส่วน LU เกี่ยวข้องกับการกำจัดระบบสมการเชิงเส้น ดังที่ Ralston ได้อธิบายไว้^{[ 18 ]}การแก้สมการเชิง เส้น NสมการในNตัวแปรที่ไม่ทราบค่าโดยการกำจัดนั้นเป็นที่รู้จักกันมาตั้งแต่สมัยโบราณในจีน^{[ 19 ]}ก่อนหน้า Gauss นักคณิตศาสตร์หลายคนในยูเรเซียได้ทำการและพัฒนาวิธีการนี้ แต่เมื่อวิธีการนี้ถูกลดระดับลงไปอยู่ในระดับโรงเรียน มีเพียงไม่กี่คนที่ทิ้งคำอธิบายโดยละเอียดไว้ ดังนั้นชื่อการกำจัดแบบ Gaussian จึงเป็นเพียงคำย่อที่สะดวกสำหรับประวัติศาสตร์ที่ซับซ้อน

Tadeusz Banachiewicz นักดาราศาสตร์ชาวโปแลนด์ได้นำเสนอการแยกส่วน LU ในปี พ.ศ. 2481 ^{[ 20 ]}เกี่ยวกับ Banachiewicz Paul Dwyer กล่าวว่า: ^{[ 21 ]}

ดูเหมือนว่า Gauss และ Doolittle จะนำวิธีการ [การกำจัด] มาใช้เฉพาะกับสมการสมมาตรเท่านั้น นักเขียนรุ่นใหม่กว่า เช่น Aitken, Banachiewicz, Dwyer และ Crout ... ได้เน้นย้ำการใช้วิธีการนี้ หรือรูปแบบต่างๆ ของมัน ในการแก้ปัญหาที่ไม่สมมาตร ... Banachiewicz ... มองเห็นประเด็น ... ว่าปัญหาพื้นฐานจริงๆ แล้วคือปัญหาของการแยกตัวประกอบเมทริกซ์ หรือ "การแยกส่วน" อย่างที่เขาเรียก

Banachiewicz ^{[ 20 ]}เป็นคนแรกที่พิจารณาการกำจัดในแง่ของเมทริกซ์และกำหนดการแยกตัวประกอบ LU ด้วยวิธีนี้ ดังที่แสดงให้เห็นโดยภาพประกอบกราฟิกของเขา การคำนวณของเขาเป็นไปตามเมทริกซ์ทั่วไป แต่สัญลักษณ์แตกต่างออกไปตรงที่เขาเลือกที่จะเขียนตัวประกอบหนึ่งตัวที่สลับตำแหน่ง เพื่อให้สามารถคูณพวกมันโดยอัตโนมัติทีละคอลัมน์ โดยการเลื่อนไม้บรรทัดลงไปตามแถวที่ต่อเนื่องกันของทั้งสอง (โดยใช้เครื่องวัดเลข ) เมื่อรวมกับการสลับลำดับของดัชนี สูตรของเขาในสัญลักษณ์สมัยใหม่จะอ่านได้ดังนี้ $${\displaystyle {\begin{aligned}{\mathbf {x} }\cdot IA'={\mathbf {0} }&\rightarrow A'{\mathbf {x} =0}\equiv (A|{\mathbf {l} }){\mathbf {x} },\\A=G\cdot H&\rightarrow A^{T}=G^{T}H,\end{aligned}}}$$

โดยที่IA → A ^T ; x ≡ [ x ₁ , ... , x _n , −1] ; A ′หมายถึงAที่ขยายด้วยคอลัมน์สุดท้าย และส่วนประกอบสุดท้ายของxคือ−1สูตรเมทริกซ์สำหรับการคำนวณแถวและคอลัมน์ของตัวประกอบ LU โดยการเวียนเกิดจะแสดงอยู่ในส่วนที่เหลือของบทความของ Banachiewicz เป็นสมการ (2.3) และ (2.4) บทความของ Banachiewicz นี้ประกอบด้วยการหาค่าตัวประกอบLUและR ^T Rของเมทริกซ์ที่ไม่สมมาตรและสมมาตรตามลำดับ บางครั้งอาจเกิดความสับสนเนื่องจากสิ่งพิมพ์ในภายหลังมักจะเชื่อมโยงชื่อของเขากับการค้นพบการแยกตัวประกอบ Cholesky อีกครั้งเท่านั้น บานาชีวิชเองอาจได้รับการยกเว้นจากการไม่กระทำการใดๆ เนื่องจากในปีถัดมาเขาก็ถูกผู้ยึดครองกดขี่ข่มเหง โดยใช้เวลาสามเดือนในค่ายกักกันซัคเซินเฮาเซนหลังจากได้รับการปล่อยตัว เขาได้อุ้มอันโตนี วิลค์ ผู้ร่วมมือและเพื่อนร่วมคุกของเขาลงจากรถไฟ ซึ่งต่อมาวิลค์เสียชีวิตจากความอ่อนเพลียในอีกหนึ่งสัปดาห์ต่อมา

โมดูลmlu Implicit None Integer , Parameter :: SP = Kind ( 1 d0 ) ! ตั้งค่าความแม่นยำจริงของ I/O Private  Public luban , lusolve Contains  Subroutine luban ( a , tol , g , h , ip , condinv , detnth ) ! วิธีการแยกตัวประกอบ LU โดย Banachiewicz (1938, ต่อไปนี้เรียกว่า B38) คำนวณสามเหลี่ยม L=G^T และ U=H ที่ทำให้สี่เหลี่ยม B=A^T=G^TH=LU การสลับแกนบางส่วน! โดยการเรียงสับเปลี่ยนคอลัมน์ IP(:) คือการบวกแบบสมัยใหม่! ภายในโค้ด a, g สอดคล้องกับ B38 A^T และ G^T ดังนั้น a=gh จึงเป็นจริง! ! การใช้งานปกติคือสำหรับสี่เหลี่ยม A อย่างไรก็ตามสำหรับ RHS l ที่ทราบอยู่แล้ว! อินพุตของ (A|l)^T ให้ผลลัพธ์เป็น (L|y^T)^T โดยที่ x ใน L^Tx=y คือคำตอบของ Ax=l Real ( SP ), Intent ( In ) :: a (:, :) ! เมทริกซ์อินพุต A(m,n), n<=m Real ( SP ), Intent ( In ) :: tol ! ค่าความคลาดเคลื่อนสำหรับจุดหมุนใกล้ศูนย์Real ( SP ), Intent ( Out ) :: g ( size ( a , dim = 1 ), size ( a , dim = 2 )) ! L(m,n) Real ( SP ), Intent ( Out ) :: h ( size ( a , dim = 2 ), size ( a , dim = 2 )) ! U(n,n) ! หมายเหตุ คอลัมน์ U ถูกสลับReal ( SP ), Intent ( Out ) :: condinv ! 1/cond(A), 0 สำหรับ A เอกฐานReal ( SP ), Intent ( Out ) :: detnth ! sign*Abs(det(A))**(1/n) Integer , Intent ( Out ) :: ip( size ( a , dim = 2 )) ! การเรียงสับเปลี่ยนคอลัมน์! จำนวนเต็ม:: k , n , j , l , isig จำนวนจริง( SP ) :: tol0 , pivmax , pivmin , piv ! n = size ( a , dim = 2 ) tol0 = Max ( tol , 3._SP * epsilon ( tol0 )) ! ใช้ค่าเริ่มต้นสำหรับ tol=0 ! ! อนุญาตให้ใช้รูปสี่เหลี่ยมผืนผ้า A และ G ได้ภายใต้เงื่อนไข: ถ้า( n > size ( a , dim = 1 ) . หรือ. n < 1 ) หยุด91 สำหรับทุก( k = 1 : n ) ip ( k ) = k h = 0._SP g = 0._SP isig = 1 detnth = 0._SP pivmax = Maxval ( Abs ( a ( 1 , :))) pivmin = pivmax ! ทำk = 1 , n ! Banachiewicz (1938) สมการ (2.3) h ( k , ip ( k :)) = a ( k , ip ( k :)) - Matmul ( g ( k , : k - 1 ), h (: k - 1 , ip ( k :))) ! ! หาค่าหลักของแถวj = ( Maxloc ( Abs ( h ( k , ip ( k :))), dim = 1 ) + k - 1) ถ้า( j /= k ) แล้ว! สลับคอลัมน์ j และ k isig = - isig ! เปลี่ยนเครื่องหมาย Det(A) เนื่องจากการเรียงสับเปลี่ยนl = ip ( k ) ip ( k ) = ip ( j ) ip ( j ) = l End If piv = Abs ( h ( k , ip ( k ))) pivmax = Max ( piv , pivmax ) ! ปรับ condinv pivmin = Min ( piv , pivmin ) ถ้า( piv < tol0 ) แล้ว! เมทริกซ์เอกฐานisig = 0 pivmax = 1._SP ออก มิฉะนั้น! พิจารณาการมีส่วนร่วมของ pivot ต่อเครื่องหมายและค่าของ Det(A) ถ้า( h ( k , ip ( k )) < 0._SP ) isig = - isig detnth = detnth + Log ( piv ) End If ! ! สมการ Banachiewicz (1938) ที่สลับตำแหน่ง (2.4) g ( k + 1 :, k ) = ( a ( k + 1 :, ip ( k )) - & Matmul ( g ( k + 1 :, : k - 1 ), h (: k - 1 , ip ( k )))) / h ( k , ip ( k )) g ( k , k ) = 1._SP End Do ! detnth = isig * Exp ( detnth / n ) condinv = Abs (isig ) * pivmin / pivmax ! ทดสอบหาเมทริกซ์สี่เหลี่ยม A(n,n) โดยการยกเลิกการคอมเมนต์ด้านล่าง! พิมพ์ *, '|AQ-LU| ',Maxval (Abs(a(:,ip(:))-Matmul(g, h(:,ip(:))))) สิ้นสุด ซับรูทีน luban ซับรูทีนlusolve ( l , u , ip , x ) ! แก้ระบบ Ax=b โดยใช้ตัวประกอบสามเหลี่ยม LU=A Real ( SP ), Intent ( In ) :: l (:, :) ! เมทริกซ์สามเหลี่ยมล่าง L(n,n) Real ( SP ), Intent ( In ) :: u (:, :) ! เมทริกซ์สามเหลี่ยมบน U(n,n) Integer , Intent ( In ) :: ip (:) ! การเรียงสับเปลี่ยนคอลัมน์ IP(n) Real ( SP ), Intent ( InOut ) :: x (:, :) ! อินพุต: m ชุดของ RHSs B(n,m), ! เอาต์พุต: ชุดตัวแปรที่ไม่ทราบค่าที่สอดคล้องกัน X(n,m) จำนวนเต็ม:: n , m , i , j n = size ( ip ) m = size ( x , dim = 2 ) ถ้า( n < 1. หรือ. m < 1. หรือ. ใดๆ([ n , n ] /= shape ( l )). หรือ. ใดๆ( shape ( l ) /= shape ( u )). หรือ. & n /= size ( x , dim = 1 )) หยุด91 ทำi = 1 , m ทำj = 1 , n x ( j , i ) = x ( j , i ) - dot_product ( x )(: j - 1 , i ), l ( j ,: j - 1 )) End Do  Do j = n , 1 , - 1 x ( j , i ) = ( x ( j , i ) - dot_product ( x ( j + 1 :, i ), u ( j , ip ( j + 1 :)))) / & u ( j , ip ( j )) End Do  End Do  End Subroutine lusolve End Module mlu

/* อินพุต: A - อาร์เรย์ของพอยเตอร์ไปยังแถวของเมทริกซ์จัตุรัสที่มีมิติ N * Tol - ค่าความคลาดเคลื่อนเล็กน้อยเพื่อตรวจจับความล้มเหลวเมื่อเมทริกซ์ใกล้เสื่อมสภาพ* เอาต์พุต: เมทริกซ์ A จะถูกเปลี่ยนแปลง โดยจะมีสำเนาของเมทริกซ์ LE และ U ทั้งสองเมทริกซ์เป็น A=(LE)+U โดยที่ P*A=L*U * เมทริกซ์การเรียงสับเปลี่ยนไม่ได้ถูกจัดเก็บเป็นเมทริกซ์ แต่ในเวกเตอร์จำนวนเต็ม P ขนาด N+1 * ที่มีดัชนีคอลัมน์ที่เมทริกซ์การเรียงสับเปลี่ยนมีค่าเป็น "1" องค์ประกอบสุดท้าย P[N]=S+N * โดยที่ S คือจำนวนการสลับแถวที่จำเป็นสำหรับการคำนวณดีเทอร์มิแนนต์ det(P)=(-1)^S */ int LUPDecompose ( double ** A , int N , double Tol , int * P ) {int i , j , k , imax ; double maxA , * ptr , absA ;for ( i = 0 ; i <= N ; i ++ ) P [ i ] = i ; //เมทริกซ์การเรียงสับเปลี่ยนหน่วย P[N] เริ่มต้นด้วย Nสำหรับ( i = 0 ; i < N ; i ++ ) { maxA = 0.0 ; imax = i ;สำหรับ( k = i ; k < N ; k ++ ) ถ้า(( absA = fabs ( A [ k ][ i ])) > maxA ) { maxA = absA ; imax = k ; }ถ้า( maxA < Tol ) ให้คืนค่า0 ; // ล้มเหลว เมทริกซ์เสื่อมสภาพถ้า( imax != i ) { // การหาค่าหลัก P j = P [ i ]; P [ i ] = P [ imax ]; P [ imax ] = j ;// แถวที่หมุนของ A ptr = A [ i ]; A [ i ] = A [ imax ]; A [ imax ] = ptr ;//นับจำนวนจุดหมุนเริ่มต้นจาก N (สำหรับดีเทอร์มิแนนต์) P [ N ] ++ ; }สำหรับ( j = i + 1 ; j < N ; j ++ ) { A [ j ][ i ] /= A [ i ][ i ];for ( k = i + 1 ; k < N ; k ++ ) A [ j ][ k ] -= A [ j ][ i ] * A [ i ][ k ]; } }ส่งคืนค่า1 ; // การแยกส่วนเสร็จสิ้น}/* อินพุต: A, P ที่กรอกใน LUPDecompose; b - เวกเตอร์ด้านขวา; N - มิติ* เอาต์พุต: x - เวกเตอร์คำตอบของ A*x=b */ void LUPSolve ( double ** A , int * P , double * b , int N , double * x ) {สำหรับ( int i = 0 ; i < N ; i ++ ) { x [ i ] = b [ P [ i ]];for ( int k = 0 ; k < i ; k ++ ) x [ i ] -= A [ i ][ k ] * x [ k ]; }สำหรับ( int i = N - 1 ; i >= 0 ; i-- ) { สำหรับ( int k = i + 1 ; k < N ; k ++ ) x [ i ] -= A [ i ] [ k ] * x [ k ];x [ i ] /= A [ i ][ i ]; } }/* อินพุต: A, P ที่กรอกใน LUPDecompose; N - มิติ* เอาต์พุต: IA คือเมทริกซ์ผกผันของเมทริกซ์เริ่มต้น*/ void LUPInvert ( double ** A , int * P , int N , double ** IA ) { for ( int j = 0 ; j < N ; j ++ ) { for ( int i = 0 ; i < N ; i ++ ) { IA [ i ][ j ] = P [ i ] == j ? 1.0 : 0.0 ;for ( int k = 0 ; k < i ; k ++ ) IA [ i ][ j ] -= A [ i ][ k ] * IA [ k ][ j ]; }สำหรับ( int i = N - 1 ; i >= 0 ; i-- ) { สำหรับ( int k = i + 1 ; k < N ; k ++ ) IA [ i ][ j ] -= A [ i ][ k ] * IA [ k ][ j ] ;IA [ i ][ j ] /= A [ i ][ i ]; } } }/* อินพุต: เมทริกซ์ A และ P ที่กรอกใน LUPDecompose; N - มิติ* เอาต์พุต: ฟังก์ชันส่งคืนค่าดีเทอร์มิแนนต์ของเมทริกซ์เริ่มต้น*/ double LUPDeterminant ( double ** A , int * P , int N ) {double det = A [ 0 ][ 0 ];for ( int i = 1 ; i < N ; i ++ ) det *= A [ i ][ i ];กลับ( P [ N ] - N ) % 2 == 0 ? เดช: - เดช; }

public class SystemOfLinearEquations { public double [] SolveUsingLU ( double [,] matrix , double [] rightPart , int n ) { // การแยกส่วนของเมทริกซ์double [,] lu = new double [ n , n ]; double sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ i , k ] * lu [ k , j ]; lu [ i , j ] = matrix [ i , j ] - sum ; } for ( int j = i + 1 ; j < n ; j ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ j , k ] * lu [ k , i ]; lu [ j , i ] = ( 1 / lu [ i , i ]) * ( matrix [ j , i ] - sum ); } }// lu = L+UI // หาคำตอบของ Ly = b double [] y = new double [ n ]; for ( int i = 0 ; i < n ; i ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ i , k ] * y [ k ]; y [ i ] = rightPart [ i ] - sum ; } // หาคำตอบของ Ux = y double [] x = new double [ n ]; for ( int i = n - 1 ; i >= 0 ; i -- ) { sum = 0 ; for ( int k = i + 1 ; k < n ; k ++ ) sum += lu [ i , k ] * x [ k ]; x [ i ] = ( 1 / lu [ i , i ]) * ( y [ i ] - sum ); } return x ; } }