LU विघटन, पिवटिंग और त्रिकोणीय निकाय

उद्देश्य और परंपराएँ

विलोपन से आव्यूह के गुणक बनाना, त्रिकोणीय गुणकों से निकाय हल करना और पंक्ति क्रमपरिवर्तन सँभालना सीखें। पूर्वज्ञान: पंक्ति संक्रियाएँ, सारणिक तथा रैखिक निकाय। हम Doolittle परंपरा लेते हैं: L निचला त्रिकोणीय है और उसके विकर्ण पर एक हैं; U ऊपरी त्रिकोणीय है। पिवटिंग में PA=LU लिखेंगे, जहाँ P पंक्तियों का क्रम बदलता है। कुछ पुस्तकें अलग परिभाषित क्रमपरिवर्तन के साथ A=PLU लिखती हैं; केवल अक्षर नहीं, समीकरण पढ़ें।

1. विलोपन के गुणक जमा करना

A=[[2,1],[6,5]] का पहला पिवट 2 और गुणक l₂₁=6/2=3 है। R₂←R₂−3R₁ से U=[[2,1],[0,2]] मिलता है। गुणक को L=[[1,0],[3,1]] में रखें। गुणन से LU=[[2,1],[6,5]]=A सत्यापित होता है। L में 3 आता है, −3 नहीं: A दोबारा बनाते समय यह विलोपन को उलटता है।

सामान्य चरण k पर हर i>k के लिए mᵢₖ=aᵢₖ/aₖₖ लें और पंक्ति i से पिवट पंक्ति का mᵢₖ गुना घटाएँ। अनुपात में पहले के विलोपन के बाद की वर्तमान प्रविष्टियाँ आती हैं। गुणक L के विकर्ण के नीचे आते हैं। अंतिम U पिवट और ऊपरी प्रविष्टियाँ रखता है। शून्य पिवट से भाग अमान्य है; सूत्र को चुपचाप आगे न बढ़ाएँ।

3×3 उदाहरण में दो चरण देखें। A=[[2,1,1],[4,3,3],[8,7,9]] के लिए पहले m₂₁=2 और m₃₁=4 से नीचे की पंक्तियाँ [0,1,1] तथा [0,3,5] बनती हैं। फिर m₃₂=3 से [0,0,2] मिलता है। अतः L=[[1,0,0],[2,1,0],[4,3,1]] और U=[[2,1,1],[0,1,1],[0,0,2]]। LU की अंतिम पंक्ति जाँचें: 4[2,1,1]+3[0,1,1]+[0,0,2]=[8,7,9]।

2. आगे और पीछे का प्रतिस्थापन

A=LU हो तो पहले Ly=b, फिर Ux=y हल करें। 2×2 उदाहरण और b=(5,17)ᵀ में आगे के प्रतिस्थापन से y₁=5 तथा 3y₁+y₂=17, अतः y₂=2। पीछे से 2x₂=2 और 2x₁+x₂=5, इसलिए x=(2,1)ᵀ। Ax=(5,17)ᵀ से जाँचें।

इकाई-विकर्ण L के लिए yᵢ=bᵢ−Σⱼ<ᵢ lᵢⱼyⱼ। अशून्य विकर्ण वाले U के लिए xᵢ=(yᵢ−Σⱼ>ᵢ uᵢⱼxⱼ)/uᵢᵢ, जिसे अंतिम पंक्ति से ऊपर की ओर निकालते हैं। त्रिकोणीय हल में A⁻¹ बनाने की आवश्यकता नहीं। U की कोई विकर्ण प्रविष्टि शून्य हो तो अद्वितीय पीछे का प्रतिस्थापन उचित नहीं; संगति और स्वतंत्र चर जाँचें।

3. व्युत्क्रमणीय आव्यूह को भी अदला-बदली चाहिए हो सकती है

A=[[0,1],[1,1]] का det(A)=−1 है, इसलिए वह व्युत्क्रमणीय है, पर पहला पिवट शून्य। P=[[0,1],[1,0]] के लिए PA=[[1,1],[0,1]]। यहाँ L=I और U=PA। इस A का बिना अदला-बदली इकाई-निचला LU नहीं बन सकता: गुणन की (1,1) प्रविष्टि u₁₁=0 देगी, जिससे (2,1) प्रविष्टि l₂₁u₁₁=0 होगी, जबकि अपेक्षित 1 है।

PA=LU से Ax=b हल करते समय पहले b का क्रम बदलें: Ly=Pb, फिर Ux=y। b=(2,5)ᵀ हो तो Pb=(5,2)ᵀ, अतः y=(5,2)ᵀ और Ux=y से x₂=2, x₁=3। मूल A को (3,2)ᵀ से गुणा करने पर (2,5)ᵀ मिलता है। b का क्रम न बदलने पर अलग निकाय हल होगा।

4. आंशिक पिवटिंग और बाद की अदला-बदली

आंशिक पिवटिंग वर्तमान पिवट स्तम्भ की शेष पंक्तियों में सबसे बड़े निरपेक्ष मान वाली प्रविष्टि चुनती है और उस पंक्ति को पिवट स्थान पर लाती है। उपयोगी प्रविष्टि मौजूद हो तो यह शून्य से भाग रोकती है और सामान्यतः बहुत छोटे पिवट का जोखिम घटाती है। यह हर संख्यात्मक त्रुटि मिटने की गारंटी नहीं है। पूरा शेष पिवट स्तम्भ शून्य हो तो वहाँ अशून्य पिवट उपलब्ध नहीं; रैंक और संगति पर ध्यान दें।

यदि पहले के स्तम्भ घटाने के बाद अदला-बदली हो, तो L के पहले से निकाले स्तम्भों में भी उन्हीं पंक्तियों को बदलें। उसके अछूते इकाई-विकर्ण ढाँचे को पूरा न बदलें। हर अदला-बदली P में जमा करें ताकि PA=LU बना रहे।

बाद की अदला-बदली का उदाहरण: A=[[2,0,0],[1,0,1],[1,1,0]]। पहले स्तम्भ के दोनों गुणक 1/2 हैं। शेष पंक्तियाँ [0,0,1] और [0,1,0] बनती हैं, इसलिए पंक्ति 2 तथा 3 बदलनी पड़ती हैं। P इन्हें बदले तो L=[[1,0,0],[1/2,1,0],[1/2,0,1]] तथा U=diag(2,1,1)। इस उदाहरण में पहले से जमा दोनों गुणक बराबर हैं, इसलिए बदलने पर मान नहीं बदलते। LU=PA=[[2,0,0],[1,1,0],[1,0,1]] से जाँच होती है। सामान्य उदाहरण में जमा गुणक अलग हो सकते हैं और उन्हें बदलना जरूरी है।

5. अस्तित्व, सारणिक और पुनः उपयोग

व्युत्क्रमणीय वर्ग आव्यूह में बिना अदला-बदली Doolittle विलोपन के सभी पिवट अशून्य तभी होते हैं जब सभी अग्रणी मुख्य उपसारणिक अशून्य हों। क्रम k का अग्रणी मुख्य उपसारणिक ऊपर-बाएँ k×k खण्ड का सारणिक है। यह व्युत्क्रमणीय, बिना अदला-बदली मामले की कसौटी है; यह दावा नहीं कि हर अव्युत्क्रमणीय आव्यूह का LU असंभव है। पंक्ति पिवटिंग से हर व्युत्क्रमणीय वर्ग आव्यूह का अशून्य पिवट वाला PA=LU बनता है। इकाई-विकर्ण परंपरा में बिना अदला-बदली व्युत्क्रमणीय LU, जब मौजूद हो, अद्वितीय है।

PA=LU में det(L)=1 तथा det(U)=∏ᵢuᵢᵢ। यदि P में s पंक्ति अदला-बदलियाँ हैं तो det(A)=(−1)ˢ∏ᵢuᵢᵢ। बिना अदला-बदली 3×3 उदाहरण का सारणिक 2×1×2=4। अदला-बदली वाले 2×2 उदाहरण का −1×1×1=−1।

सघन आव्यूह का विलोपन O(n³) अंकगणितीय संक्रियाएँ लेता है। गुणक तैयार हों तो हर नए दाएँ पक्ष के लिए दो त्रिकोणीय हल O(n²) लेते हैं। इसलिए कई b वाले एक ही A के लिए LU उपयोगी है। अव्युत्क्रमणीय निकाय के हल हो सकते हैं, पर स्वचालित अद्वितीय-हल विधि के लिए व्युत्क्रमणीयता चाहिए।

जाँच-सूची

A=LU या PA=LU तथा विकर्ण की परंपरा बताएँ। वर्तमान पिवट और गुणक लिखें, अदला-बदली को P तथा L के पुराने स्तम्भों में सँभालें और गुणन से जाँचें। दाएँ पक्ष पर ठीक PA=LU वाला क्रमपरिवर्तन लगाएँ, पहले निचला फिर ऊपरी निकाय हल करें, और मूल निकाय में रखकर सत्यापित करें। सारणिक के अदला-बदली चिह्न को विलोपन गुणकों से अलग रखें।

मौलिक अभ्यास: छह एक-सही-विकल्प प्रश्न

ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक विकल्प चुनें।

LU01. बिना पिवटिंग A=[[2,1],[6,5]] में इकाई-विकर्ण L के लिए विलोपन गुणक l₂₁ क्या है?

A. −3 B. 3 C. 6 D. 1/3

उत्तर: B

A: पंक्ति संक्रिया में पहली पंक्ति का 3 गुना घटाते हैं, पर L में गुणक 3 आता है।

B: l₂₁=a₂₁/a₁₁=6/2=3।

C: पिवट 2 से भाग दें।

D: यह अनुपात उलटता है।

LU02. L=[[1,0],[3,1]], U=[[2,1],[0,2]] के लिए LU क्या है?

A. [[2,1],[6,5]] B. [[2,1],[3,2]] C. [[2,0],[6,2]] D. [[2,3],[1,5]]

उत्तर: A

A: पंक्ति-स्तम्भ गुणन से नीचे की पंक्ति (6,5) है।

B: यह आवश्यक गुणन के बिना प्रविष्टियाँ नकल करता है।

C: ऊपर दाएँ 1 और नीचे दाएँ 5 है।

D: दिए क्रम का गुणन ये प्रविष्टियाँ नहीं देता।

LU03. सामान्य पहले-स्तम्भ विलोपन में A=[[0,1],[1,1]] को पंक्ति अदला-बदली क्यों चाहिए?

A. A अव्युत्क्रमणीय है B. A व्युत्क्रमणीय होते हुए भी पहला पिवट शून्य है C. दोनों पंक्तियाँ शून्य हैं D. उसका सारणिक शून्य है

उत्तर: B

A: det(A)=−1, इसलिए A व्युत्क्रमणीय है।

B: गुणक 1/0 अपरिभाषित है; अदला-बदली से अशून्य पिवट मिलता है।

C: कोई पंक्ति शून्य नहीं है।

D: सारणिक −1 है।

LU04. PA=LU दिया है। Ax=b हल करने के लिए कौन-से दो निकाय हल करें?

A. Ly=b, Ux=y B. Uy=Pb, Lx=y C. Ly=Pb, Ux=y D. Ly=Pb, Ux=Py

उत्तर: C

A: दाएँ पक्ष पर वही पंक्ति क्रमपरिवर्तन लगना चाहिए।

B: इसमें गुणकों का क्रम उलट गया।

C: PAx=Pb से LUx=Pb; y=Ux रखें।

D: b पर क्रमपरिवर्तन पहले ही लग चुका है; यहाँ अतिरिक्त P नहीं चाहिए।

LU05. PA=LU में L का विकर्ण इकाई, diag(U)=(2,−3,4) और P एक पंक्ति अदला-बदली है। det(A) क्या है?

A. −24 B. 24 C. −5 D. 9

उत्तर: B

A: −24, det(U)=det(PA) है; अदला-बदली गिनने के बाद det(A) नहीं।

B: det(P)=−1 और det(L)=1; अतः −det(A)=−24 तथा det(A)=24।

C: U की विकर्ण प्रविष्टियों का गुणनफल लें और पंक्ति अदला-बदली का चिह्न शामिल करें; इससे 24 मिलता है, −5 नहीं।

D: गुणनफल और क्रमपरिवर्तन का चिह्न दोनों चाहिए।

LU06. स्तम्भ k पर आंशिक पिवटिंग में पंक्ति k,…,n से कौन-सी पिवट पंक्ति चुनते हैं?

A. स्तम्भ k में सबसे बड़े निरपेक्ष मान वाली पंक्ति B. A में कहीं भी सबसे बड़ी चिह्नित प्रविष्टि वाली पंक्ति C. बिना जाँच हमेशा पंक्ति k D. स्तम्भ k में सबसे छोटे निरपेक्ष मान वाली पंक्ति

उत्तर: A

A: आंशिक पिवटिंग में वर्तमान शेष स्तम्भ के |aᵢₖ| को अधिकतम करते हैं।

B: खोज वर्तमान स्तम्भ तक सीमित है और निरपेक्ष मान लेती है।

C: शून्य या छोटे पिवट के लिए अदला-बदली आवश्यक हो सकती है।

D: छोटे पिवट बड़े गुणक बना सकते हैं और पूर्णांकन त्रुटि बढ़ा सकते हैं।

स्रोत और सीमा

आधिकारिक LU decomposition शीर्षक का सीधा समर्थन और रैखिक निकाय से संबंध। पिवटिंग की परंपरा और त्रिकोणीय हल शामिल हैं; सभी छह प्रश्न मौलिक हैं।

Official GATE 2026 CS syllabus (verified 2026-10-14).