ในพีชคณิตเชิงเส้นเชิงตัวเลขการแยกตัวประกอบ LU ที่ไม่สมบูรณ์ (ย่อว่าILU ) ของเมทริกซ์คือ การประมาณค่า แบบเบาบางของการแยกตัวประกอบ LUซึ่งมักใช้เป็นตัวปรับสภาพเบื้องต้น

พิจารณาระบบสมการเชิงเส้นแบบเบาบาง โดยทั่วไปแล้วระบบเหล่านี้จะแก้ได้โดยการคำนวณการแยกตัวประกอบโดยที่L เป็นเมทริกซ์ สามเหลี่ยมล่างแบบหน่วยและU เป็น เมทริกซ์สามเหลี่ยมบนจากนั้นจึงแก้สมการซึ่งสามารถทำได้อย่างมีประสิทธิภาพเนื่องจากเมทริกซ์เป็นเมทริกซ์สามเหลี่ยม ${\displaystyle Ax=b}$${\displaystyle A=LU}$${\displaystyle Ly=b}$${\displaystyle Ux=y}$

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

การแยกตัวประกอบที่ไม่สมบูรณ์จะแสวงหาเมทริกซ์สามเหลี่ยมLและUที่ทำให้ แทนที่จะ เป็นการแก้หาสามารถทำได้อย่างรวดเร็ว แต่จะไม่ให้คำตอบที่แน่นอนสำหรับดังนั้น เราจึงใช้เมทริกซ์เป็นตัวปรับสภาพเบื้องต้นในอัลกอริทึมการแก้ปัญหาแบบวนซ้ำอื่น เช่นวิธีการไล่ระดับแบบสังยุคหรือGMRESแทน ${\displaystyle A\approx LU}$${\displaystyle A=LU}$${\displaystyle LUx=b}$${\displaystyle Ax=b}$${\displaystyle M=LU}$

สำหรับเมทริกซ์ที่กำหนดเราสามารถนิยามกราฟได้ดังนี้ ${\displaystyle A\in \mathbb {R} ^{n\times n}}$${\displaystyle G(A)}$

${\displaystyle G(A):=\left\lbrace (i,j)\in \mathbb {N} ^{2}:A_{ij}\neq 0\right\rbrace \,,}$

ซึ่งใช้ในการกำหนดเงื่อนไขที่รูปแบบความเบาบาง ต้องปฏิบัติตาม ${\displaystyle S}$

${\displaystyle S\subset \left\lbrace 1,\dots ,n\right\rbrace ^{2}\,,\quad \left\lbrace (i,i):1\leq i\leq n\right\rbrace \subset S\,,\quad G(A)\subset S\,.}$

การแยกส่วนในรูปแบบที่เงื่อนไขต่อไปนี้เป็นจริง ${\displaystyle A=LU-R}$

• ${\displaystyle L\in \mathbb {R} ^{n\times n}}$เป็นเมทริกซ์สามเหลี่ยมหน่วยล่าง
• ${\displaystyle U\in \mathbb {R} ^{n\times n}}$เป็นเมทริกซ์สามเหลี่ยมบน
• ${\displaystyle L,U}$มีค่าเป็นศูนย์นอกรูปแบบความเบาบาง:${\displaystyle L_{ij}=U_{ij}=0\quad \forall \;(i,j)\notin S}$
• ${\displaystyle R\in \mathbb {R} ^{n\times n}}$มีค่าเป็นศูนย์ภายในรูปแบบความเบาบาง:${\displaystyle R_{ij}=0\quad \forall \;(i,j)\in S}$

เรียกว่าการแยกส่วน LU ที่ไม่สมบูรณ์ (โดยพิจารณาจากรูปแบบความเบาบาง) ${\displaystyle S}$

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

เกี่ยวกับเสถียรภาพของ ILU ทฤษฎีบทต่อไปนี้ได้รับการพิสูจน์โดย Meijerink และ van der Vorst ^{[ 1 ]}

ให้เป็นเมทริกซ์ Mการแยกตัวประกอบ LU (สมบูรณ์) กำหนดโดยและการแยกตัวประกอบ ILU กำหนดโดยแล้ว ${\displaystyle A}$${\displaystyle A={\hat {L}}{\hat {U}}}$${\displaystyle A=LU-R}$

${\displaystyle |L_{ij}|\leq |{\hat {L}}_{ij}|\quad \forall \;i,j}$

เป็นเช่นนั้น ดังนั้น ILU จึงมีความเสถียรอย่างน้อยก็เท่ากับการแยกส่วนประกอบ LU (แบบสมบูรณ์)

เราสามารถหาพรีคอนดิชันเนอร์ที่แม่นยำยิ่งขึ้นได้โดยอนุญาตให้มีการเติมส่วนเกินในระดับหนึ่งในการแยกตัวประกอบ ตัวเลือกที่นิยมใช้คือการใช้รูปแบบความเบาบางของA ²แทนAเมทริกซ์นี้มีความหนาแน่นมากกว่าA อย่างเห็นได้ชัด แต่ก็ยังคงเบาบางอยู่ดี พรีคอนดิชันเนอร์นี้เรียกว่า ILU(1) จาก นั้น เราสามารถขยายขั้นตอนดังกล่าวได้ พรีคอนดิชันเนอร์ ILU(k) ของเมทริกซ์Aคือการแยกตัวประกอบ LU ที่ไม่สมบูรณ์ด้วยรูปแบบความเบาบางของเมทริกซ์A ^k+1

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

การประมาณค่าการแยกตัวประกอบ ILU สามารถทำได้โดยใช้การวนซ้ำจุดคงที่ในลักษณะขนานสูง^{[ 2 ]}

• การแยกตัวประกอบ Cholesky ที่ไม่สมบูรณ์

• การแยกตัวประกอบ LU ที่ไม่สมบูรณ์ใน CFD Wiki

บทความเกี่ยวกับคณิตศาสตร์ประยุกต์นี้ เป็น บทความย่อคุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มข้อมูลที่ขาดหายไป

• วี
• ที
• อี