LU Decomposition and Partial Pivoting - MATLAB Video Lecture | MATLAB Programming for Numerical Computation - Software Development

नमस्कार और संख्यात्मक
अभिकलन के लिए MATLAB
प्रोग्रामिंग (MATLAB
programming for numerical computations) में
आपका स्वागत है।
हम मॉड्यूल 4 में हैं,
इस मॉड्यूल में, हम
टाइप करें ax = b के रैखिक
समीकरणों (linear equations)
को हल कर रहे हैं जहाँ,
a, n / n मैट्रिक्स है,
x और b एक आयामी कॉलम
वैक्टर हैं। पिछले
व्याख्यान में, हमने
जो कवर किया था, वह
एक लोकप्रिय तकनीक
थी जिसे गॉस एलिमिनेशन
(Gauss elimination) के रूप में
जाना जाता था और उसके
बाद वापस प्रतिस्थापन
होता था।
इस व्याख्यान में,
हम पिछले व्याख्यान
से उदाहरण लेंगे,
और दो अलग-अलग काम
करने के लिए, एक को
LU अपघटन (LU decomposition) नामक
नई विधि को देखना
है और दूसरा एक गॉस
एलिमिनेशन (Gauss elimination)
में आंशिक धुरी (partial
pivoting) को देखना है।
तो, आइए, पिछले व्याख्यान
से उदाहरण पर विचार
करें, जो कि एक 3/3 मैट्रिक्स
था, जैसा कि हम सभी
जानते हैं x एक 3-आयामी
वेक्टर है जिसमें
X1, x2 और x3 है जहां b 4,
7 और 9 है।
हम हल करते हैं गॉस
एलिमिनेशन (Gauss elimination)
और बैक प्रतिस्थापन
(back substitution) के उपयोग
से यह समस्या, और हम
जो करने जा रहे हैं,
वही कोड लेते हैं,
जिससे हमने पिछले
व्याख्यान में MATLAB
का उपयोग करके उत्पन्न
किया था, और इसका उपयोग
दो चीजें करने के
लिए किया था, LU अपघटन
और आंशिक धुरी (partial
pivoting) । इसलिए, हमें
MATLAB पर जाएं, और gauss elm
को संपादित करें।
तो, यह वह कोड था जो
हमने अपने पिछले
व्याख्यान में लिखा
था। इसलिए, हम एक तरह
से कोड को थोड़ा संशोधित
करेंगे।
इसलिए, हमने जो किया
है, A(1, 1) के साथ धुरी
तत्व (pivot element) के रूप
में, हमने पंक्ति
2 के लिए और साथ ही
पंक्ति 3 के लिए गणना
की है। तो, आइए हम
इसे संशोधित करें
और i= 2 से 3 के लिए a में
डालें। क्योंकि हमने
यहां पंक्ति 2 के लिए
ऐसा किया था। और हमने
यहां पंक्ति 3 के लिए
ऐसा किया। इसलिए,
जब i = 2 है, हमारे पास
जो कुछ भी है, हम 2 को
केवल i के साथ बदल
सकते हैं और देख सकते
हैं कि हमें क्या
मिलता है। और देखते
हैं कि हम Ab (i) को बदल
देंगे। Ab (i) और यह Ab1
है।
इसलिए, हमें इसे बदलना
नहीं है, और हमें बस
इसे हटाना होगा, end
टाइप करना होगा, और
यह हमारे लिए अच्छा
होना चाहिए, और बस
उचित रूप में किया
जाना चाहिए। और इस
विशेष मामले के लिए,
फिर से हम जो करने
जा रहे हैं, वह कुछ
इस तरह है, हम सिर्फ
i = 3 कहेंगे क्योंकि
i = 3, 2, 3 के लिए इस विशेष
मामले में। और alpha
Ab(2,2) से विभाजित करके
Ab (i, 2) और Ab (i,:) = Ab (i,:) alpha
*Ab (2,:) होने जा रहा है।
तो, आपने ऐसा किया
है। और अब हम इसे चलाते
हैं और जांचते हैं
कि कहीं कोई त्रुटि
तो नहीं है।
मैं run पर क्लिक करूंगा
और मैं MATLAB कमांड प्रॉम्प्ट
(command prompt) पर जाऊंगा,
और हमारे x टाइप करूंगा
और Ab मैट्रिक्स भी
टाइप करूंगा, हां
Ab मैट्रिक्स वास्तव
में कम त्रिकोणीय
मैट्रिक्स और x है,
समाधान वास्तव में
है जो हम 1 2 1 होने की
उम्मीद करते हैं।
इसलिए हम इस बदलाव
से खुश हैं। हमें
पावर प्वाइंट पर
वापस जाने के लिए
है। इसलिए, हमने अब
जो किया है, हमने पिछले
व्याख्यान से उदाहरणों
को समाप्त कर दिया।
और इसे संशोधित किया
ताकि हम मूल रूप से
लूप का उपयोग करें
ताकि गॉस एलिमिनेशन
(Gauss elimination) कम्प्यूटेशन
(computation) हो सके।
आइए अगली स्लाइड
LU अपघटन (LU decomposition) पर
चलते हैं। इसलिए,
एक LU अपघटन (LU decomposition)
में क्या होता है,
इस प्रकार है, रुचि
रखने वाले पाठक आगे
बढ़ सकते हैं और कम्प्यूटेशनल
तकनीकों के पाठ्यक्रम
को देख सकते हैं।
यह इस विशेष पाठ्यक्रम
की बहन है, आप उस पाठ्यक्रम
को देख सकते हैं, मॉड्यूल
नंबर 3, व्याख्यान
3 और वहां मैंने समझाया
है कि LUअपघटन क्या
है।
और मूल रूप से, LU अपघटन
के पीछे का विचार
है, कि किसी भी मैट्रिक्स
A को निचले त्रिकोणीय
मैट्रिक्स L और एक
ऊपरी त्रिकोणीय मैट्रिक्स
U के उत्पाद के रूप
में लिखा जा सकता
है, जहां U मैट्रिक्स
कुछ भी नहीं है, लेकिन
मैट्रिक्स जिसे हमने
गॉस एलिमिनेशन (Gauss
elimination) के बाद प्राप्त
किया है । इसका मतलब
क्या है, हमारा U मैट्रिक्स
कुछ भी नहीं है, लेकिन
यह 1, 1, 1; 0, -1, 1; 0, 0, -4 है।
वह हमारा U मैट्रिक्स
है। हमारे L मैट्रिक्स
क्या है? हमारे L मैट्रिक्स
कुछ भी नहीं है, लेकिन
1, 1, 1 विकर्ण तत्वों
के रूप में है और alpha
A(2,1)/A (1,1), A (3,1)/A(1,1), A(3,2)/A (2,2)
के अनुपात हैं। जो
हम पहले से ही गॉस
एलिमिनेशन (Gauss elimination)
से गणना कर चुके हैं,
L मैट्रिक्स ठीक है।
तो हम क्या करे? तो,
हमें क्या करने की
आवश्यकता है, U मैट्रिक्स
पहले से ही एक गॉस
एलिमिनेशन (Gauss elimination)
प्राप्त किया जाता
है। इसलिए, हमें वास्तव
में इसके बारे में
कुछ भी नहीं करना
है। हमें क्या करने
की आवश्यकता है, उस
L मैट्रिक्स को पहले
एक identity मैट्रिक्स
के रूप में परिभाषित
करने के लिए और उसके
बाद जैसे ही हम गॉस
एलिमिनेशन (Gauss elimination)
की गणना करते हैं,
बस तत्व alpha (2,1) को पॉप्युलेट
करते हैं, फिर तत्व
alpha (3,1) और alpha (3,2) को आबाद
करते हैं इत्यादि
इत्यादि।
जैसा कि हम अभिकलन
करते हैं, हमें MATLAB
पर चलते हैं और हम
जो करेंगे वह gauss elm
है। हम myLUcode के रूप
में save करेंगे ठीक
है। मैं बस इसे बदल
दूंगा, गॉस एलिमिनेशन
(Gauss elimination) का उपयोग
करके LU अपघटन (decomposition)
। सब कुछ वही रहता
है, जो हमें चाहिए,
L मैट्रिक्स और U मैट्रिक्स,
हमें बैक (back) प्रतिस्थापन
(substitution) की आवश्यकता
नहीं है। तो, हम चलते
हैं, अब, हमने अपना
बैक (back) प्रतिस्थापन
(substitution) हटा दिया है।
हमारे U मैट्रिक्स
कुछ भी नहीं है, लेकिन
Ab 1 से n तक, 1 से n। हम
नहीं चाहते हैं कि
इसका हिस्सा b। तो,
यही कारण है कि, हम
इस विशेष तरीके से
U क्यों लिख रहे हैं।
अब सवाल यह है कि L
कैसे प्राप्त करें?
जैसा कि मैंने पहले
कहा था, हम L के साथ
क्या करते हैं, इसे
initialize करें, आइडेंटिटी
मैट्रिक्स (identity matrix)
i n ठीक है। इसलिए, जब
हम इसे एक आइडेंटिटी
मैट्रिक्स (identity matrix)
के रूप में initialize करते
हैं, हम एक बार विकर्ण
तत्वों (diagonal elements) के
रूप में प्राप्त
करने जा रहे हैं।
उप विकर्ण तत्व (sub
diagonal matrix) अभी सभी 0s हैं
और जैसा कि हम गणना
करते हैं, हम उस विशेष
मैट्रिक्स को अच्छी
तरह से आबाद करने
जा रहे हैं। तो, हमें
क्या करने की आवश्यकता
है, यह alpha कुछ भी नहीं
है, लेकिन पहली कॉलम
पंक्ति 2 और पंक्ति
3।
इसलिए, L पंक्ति i, जो
पंक्ति 2 और पंक्ति
3 है और कॉलम नंबर
1 alpha के अलावा और कुछ
नहीं होने वाला है
। और हम लिखते हैं
कि, और यह हमारे लिए
काफी अच्छा होना
चाहिए, और यही बात
हम अपने कॉलम नंबर
2 के लिए भी लिखने
जा रहे हैं। इसलिए
हम इसे लिखने जा रहे
हैं और यह कॉलम नंबर
1 नहीं होगा, बल्कि
यह कॉलम नंबर 2 होने
वाला है। इसलिए, पंक्ति
संख्या 3, कॉलम नंबर
2, फिर से यह alpha है जिसे
यहां पर गणना की गई
थी।
ध्यान रखें, मैं alpha
के पहले यह L नहीं
लिख रहा हूं। मैं
alpha और myLUcode के बाद यह
L लिख रहा हूं और मैं
Enter दबाऊंगा। उम्मीद
है कि हमें कोई त्रुटि
(error) नहीं मिलेगी।
नहीं, हमें नहीं मिला,
इसलिए हम अपने L मैट्रिक्स
को देखते हैं और हम
अपने U मैट्रिक्स
को देखते हैं। तो,
यह हमारा L और U मैट्रिक्स
है। और हमें L*U product
ले लो और हमें देखें
कि हमें क्या मिलेगा
L और जब हम L*U कहते हैं,
तो हम ठीक उसी तरह
एक मैट्रिक्स वापस
प्राप्त करेंगे तो,
यह LU अपघटन (decomposition)
है।
और हम एक बार फिर से
कोड पर वापस जाते
हैं, और वास्तव में
देखते हैं कि हमने
वास्तव में क्या
बदलाव किए हैं। केवल
परिवर्तन, हमने यह
बनाया है कि यह विशेष
कमांड L(i, 1) इस समग्र
संगणना में जोड़ा
गया है और हमने अपने
L को पहचान मैट्रिक्स
(identity matrix) के रूप में
आरंभीकृत किया है
और अंत में हम इस विशेष
में अपने U की गणना
करते हैं। इसलिए,
वे एकमात्र परिवर्तन
हैं जो हमें आपको
इसे बचाने के लिए
करने हैं और हमने
quit कर दिया।
इसलिए, आंशिक धुरी
(partial pivoting) का विचार
निम्नानुसार है,
इसलिए हम गॉस एलिमिनेशन
(Gauss elimination) में क्या
कर रहे हैं, हम पंक्ति
विनिमय और पंक्ति
संचालन (row exchange and row operations)
का उपयोग करते हैं।
उप विकर्ण तत्वों
में 0s प्राप्त करने
के लिए, विकर्ण ठीक
नीचे के तत्वों में।
गॉस एलिमिनेशन (Gauss
elimination) में, हम बस आँख
बंद करके जो कुछ भी
करते हैं उसका उपयोग
करते हैं, समग्र परिणाम
जो हमारे पास होते
हैं, हम केवल आँख बंद
करके मैट्रिक्स A
का उपयोग करते हैं।
हम आंशिक रूप से धुरी
के साथ गॉस एलिमिनेशन
(Gauss elimination) के मामले
में उपयोग करते हैं।
हम क्या करने जा रहे
हैं, हम इस तरह से
विनिमय करने के लिए,
पंक्ति विनिमय (row
exchange) का उपयोग करने
जा रहे हैं। पंक्तियों
का इस तरह से आदान-प्रदान
करना, कि धुरी तत्व
सबसे बड़ा मूल्य
है, धुरी तत्व का पूर्ण
मूल्य धुरी स्तंभ
में सबसे बड़ा मूल्य
है। इसलिए पहले ऑपरेशन
में, जब A (1,1) उस बिंदु
पर धुरी तत्व होता
है, हम पहले कॉलम में
सभी गुणांक (coefficients)
को देखते हैं। और
सबसे बड़ा गुणांक
पंक्ति 1 के साथ स्वैप
(swap) किया जा रहा है।
इस मामले में, बड़ा
गुणांक 3 होता है।
इसलिए, हम इन 2 समीकरणों
को स्वैप (swap) करेंगे,
और फिर गॉस एलिमिनेशन
(Gauss elimination) का पहला चरण
ठीक करेंगे। तो, हम
MATLAB पर वापस जाते हैं,
और हमारे गॉस एलिमिनेशन
(Gauss elimination) कोड को ठीक
से खोलते हैं। और
मैं इसे गॉस एलिमिनेशन
(Gauss elimination) का उपयोग
करके आंशिक पिवटिंग
(pivoting) के साथ गॉस एलिमिनेशन
(Gauss elimination) के रूप में
save करूँगा, ठीक है।
तो मुझे जो करने की
ज़रूरत है वह अब A
(1, 1) धुरी तत्व परिवर्तन
है, यह सुनिश्चित
करने के लिए कि A (1,
1) कॉलम 1 में सबसे बड़ा
है।
तो, इसका क्या मतलब
है, यह है कि, हम कॉलम
1 को देखना चाहते हैं।
इसलिए, col 1=Ab, पूरी पंक्ति,
सभी पंक्तियों और
पहले कॉलम में देखें।
तो, वह कॉलम 1 है, हम
यह खोजना चाहते हैं
कि कौन सा सबसे बड़ा
है, और ऐसा करने के
लिए, हम max नामक कमांड
का उपयोग करते हैं।
हम पंक्ति 1 और 3 का
आदान-प्रदान कैसे
करते हैं, और हम Ab (3,:)
को याद करते हैं, यह
तीसरी पंक्ति है।
इसलिए अगर हमें Ab
(3,:) लिखना है और Ab (1,:)
को असाइन (assign) करना
है।
यह वास्तव में जा
रहा है, हमें तीसरी
पंक्ति दें और यह
पहली पंक्ति के बजाय
तीसरी पंक्ति को
ठीक कर देगा। इससे
समस्या होने वाली
है। मैं आपको दिखाऊंगा,
कि क्लिक (click) करने
से क्या समस्या है।
क्या आप देख सकते
हैं कि हमारे Ab मैट्रिक्स
की तुलना में समस्या
क्या थी? क्या आप वास्तव
में देख सकते हैं
कि समस्या क्या थी?
ठीक है।
समस्या यह है कि यह
जो हो रहा है उसे करने
से, हम अब अपनी पहली
पंक्ति को खो चुके
हैं। अब हम नहीं जानते
कि हमारा Ab (1, :) क्या
था। तो, हमें उस Ab (1,
:) को स्टोर (store) करने
के लिए एक तरीका चाहिए
और फिर इस विशेष कमांड
का उपयोग करना चाहिए।
तो चलिए हम इसे कॉपी
करते हैं और अपने
editor पर चलते हैं और
फिर से ऐसा करते हैं।
इससे पहले, हम ऐसा
करते हैं, हमें max भी
चाहिए। और हम Ab (1, :) को
पहले स्टोर (store) करना
चाहते हैं, हम (1,:) का
मान बदलते हैं। तो
चलिए हम उस वेरिएबल
(variable) dummy का पुनः उपयोग
करते हैं क्योंकि
वैसे भी वह वेरिएबल
(variable) dummy वेरिएबल (variable)
था।
तो dummy Ab(1:,) के अलावा
कुछ भी नहीं है। यह
पहली पंक्ति के लिए
एक अस्थायी स्थान
धारक है। और Ab(3,:) dummy
है लेकिन कुछ भी नहीं
है। तो, हम इसे save करते
हैं, और हम जो कर सकते
हैं वह यह है, ठीक
है। और मैं सिर्फ
राइट क्लिक (right click)
करके evaluate selection पर क्लिक
करूंगा, और देखूंगा
कि हमें क्या मिला।
यदि हम Ab टाइप करते
हैं, तो हमने देखा
है कि पंक्ति संख्या
3 का अब आदान-प्रदान
किया गया है, जो पहले
पंक्ति संख्या 1 थी,
इसलिए पंक्ति विनिमय
(row exchange) हुआ है। तो,
यह है कि आंशिक धुरी
कैसे काम करेगी।
तो, यह आंशिक धुरी
(partial pivoting) है।
हमने यहां पर जो किया
है, वह आंशिक रूप से
धुरी है। हमने वह
पहली पंक्ति के साथ
किया जब A (1, 1) धुरी
तत्व था। धुरी स्तंभ
में गणना ठीक है।
और हम इसे दोहराते
हैं, पंक्ति विनिमय
(row exchange) को ठीक करते
हैं। और फिर से हमें
केवल उप विकर्ण तत्वों
को देखने की आवश्यकता
है, इसलिए col2= Ab ((2 to end),
2) होने वाला है ठीक
है।
और पहले की तरह, बस
इसे कॉपी करें और
dummy, idx ठीक है, यह है,
और dummy = Ab (2, :)। Ab (2,:) = Ab
(idx) और Ab (idx) = dummy, और यही
बात हम यहाँ पर भी
कर सकते हैं। Ab (1,:)
dummy होने जा रहा है,
ठीक है। Ab (1,:) Ab (idx,:) है
और Ab (idx,:) dummy के अलावा
कुछ नहीं है, ठीक है।
इसलिए हमारे पास
यह है और हम अपने गॉस
एलिमिनेशन (Gauss elimination)
के साथ जारी रखते
हैं, इसलिए ठीक है।
तो इसे save करें और
हमें आशा है कि कोई
त्रुटि (error) नहीं है।
हमने इसे run किया है
और वापस जाकर जांच
करेंगे। हमारे Ab,
यह अब एक ऊपरी त्रिकोणीय
मैट्रिक्स है यहाँ
ठीक है। लेकिन हमने
यह आंशिक धुरीकरण
किया है, जिसके परिणामस्वरूप
पहले मामले में पंक्ति
संख्या 1 और 2 का आदान-प्रदान
हुआ है। और हम देखते
हैं, जो हमें समाधान
x के रूप में मिलता
है, बैक प्रतिस्थापन
(back substitution) के बाद। और
बैक प्रतिस्थापन
(back substitution) के बाद, हम
देखते हैं कि हमारा
x 1, 2, 1. से पहले के समान
है। हां, यह काम करता
है और हम इसका पता
लगाना चाहते हैं।
आइए हम बताते हैं
कि यहां पर idx बदला
है या नहीं। तो मैं
सिर्फ टाइप कर सकता
हूं, मुझे लगता है
कि यहां एक गलती थी।
मुझे लगता है कि यह
col2 होना चाहिए। मुझे
नहीं पता, मुझे यकीन
नहीं है कि, यह वास्तव
में चलता है, शायद
मैंने ऐसा इसलिए
किया है, आइए देखें
कि इस बार Ab में अलग
क्या है, ठीक है। जैसा
कि आप देख सकते हैं
कि Ab अलग है, लेकिन
x आपको सही समाधान
1, 2, 1 के रूप में मिलने
वाला है, और आप देखेंगे
कि इस विशेष मामले
में। आंशिक धुरी
के इस मामले में, इस
विशेष मामले में,
2 और 3 के बीच एक पंक्ति
विनिमय (row exchange) दूसरे
में हुआ था, दूसरे
धुरी तत्व के लिए।
इस मामले में, विशेष
पंक्ति विनिमय (row
exchange) नहीं हुआ था।
इसलिए, इन 2 उदाहरणों
के बीच एकमात्र अंतर
ठीक है। और हम आंशिक
धुरी का उपयोग करके
1 2 1 के रूप में हमारे
x समाधान प्राप्त
करते हैं। तो, यह मुझे
इस विशेष व्याख्यान
के अंत में लाता है
ठीक है।
इस व्याख्यान में
हमने जो कवर किया
है, दो अवधारणाएं,
एक LU अपघटन (decomposition)
की है जहां मैट्रिक्स
A को निचले और एक ऊपरी
त्रिकोणीय मैट्रिक्स
के product के रूप में
लिखा जा सकता है।
ऊपरी त्रिकोणीय मैट्रिक्स
कुछ भी नहीं था लेकिन
गॉस एलिमिनेशन (Gauss
elimination) के बाद प्राप्त
समाधान, और निचले
त्रिकोणीय मैट्रिक्स
alpha वाले मैट्रिक्स
रहे हैं।
और गॉस एलिमिनेशन
(Gauss elimination) प्लस आंशिक
धुरी (partial pivoting) के पीछे
का विचार, पंक्ति
आदान-प्रदान का उपयोग
करना था। यह सुनिश्चित
करने के लिए कि उस
विशेष कॉलम में A(i,
i) सबसे बड़ा तत्व
है, जब हम उप विकर्ण
तत्वों के साथ तुलना
कर रहे हैं । इस प्रकार,
हम इस विशेष व्याख्यान
को समाप्‍त करते
हैं। सुनने और देखने
के लिए धन्यवाद और
अगले व्याख्यान में
मिलते हैं।