संख्यात्मक रैखिक बीजगणित

संख्यात्मक रेखीय बीजगणित, जिसे कभी-कभी व्यावहारिक रेखीय बीजगणित भी कहा जाता है, यह अध्ययन है कि कंप्यूटर कलनविधि बनाने के लिए आव्यूह (मैट्रिक्स) संचालन का उपयोग कैसे किया जा सकता है, जो कुशलतापूर्वक गणित में प्रश्नों के अनुमानित उत्तर निरन्तर और सटीक रूप से प्रदान करते हैं। यह संख्यात्मक विश्लेषण का उपक्षेत्र है, और एक प्रकार का रेखीय बीजगणित है। जो कंप्यूटर चल बिन्दु (floating-point) परिकलन का उपयोग करते हैं और वास्तव में अपरिमेय संख्या आँकड़ा का प्रतिनिधित्व नहीं कर सकते हैं, इसलिए जब एक कंप्यूटर कलनविधि को आँकड़ा के आव्यूह पर लागू किया जाता है, तो यह कभी-कभी कंप्यूटर में संग्रहीत संख्या और वास्तविक संख्या के बीच अंतर को बढ़ा सकता है, जिसका यह एक अनुमान है। कि संख्यात्मक रैखिक बीजगणित कंप्यूटर कलनविधि विकसित करने के लिए सदिश और आव्यूह के गुणों का उपयोग करता है, जो कंप्यूटर द्वारा प्रस्तुत की गई त्रुटि को कम करता है, और यह सुनिश्चित करने से भी संबंधित है कि कलनविधि जितना संभव हो उतना प्रभावशाली होती है।

संख्यात्मक रेखीय बीजगणित का उद्देश्य परिमित सटीक कंप्यूटरों का उपयोग करके निरंतर गणित की समस्याओं को हल करना है, इसलिए प्राकृतिक विज्ञान और सामाजिक विज्ञानों में इसके अनुप्रयोग उतने ही विशाल होते हैं जितने निरंतर गणित के अनुप्रयोग होते है। यह प्रायः अभियांत्रिकी और कम्प्यूटेशनल की समस्याओं का एक मूलभूत हिस्सा होता है, जैसे चित्र और संकेत प्रसंस्करण, दूरसंचार, कम्प्यूटेशनल पूँज़ी, पदार्थ विज्ञान अनुकरण, संरचनात्मक जीव विज्ञान, आँकड़ा खनन, जैव सूचना विज्ञान और द्रव गतिविज्ञान आव्यूह विधियों का विशेष रूप से परिमित तत्व (element) विधि, परिमित अवकलन विधि और अवकलन समीकरणों के प्ररूपों में उपयोग किया जाता है। संख्यात्मक रेखीय बीजगणित के व्यापक अनुप्रयोगों को ध्यान में रखते हुए, लॉयड एन. ट्रेफेथेन और डेविड बाऊ, III तर्क देते हैं कि यह गणितीय विज्ञान के लिए कैलकुलस (calculus) और अवकलन समीकरणों के रूप में अत्यन्त महत्वपूर्ण होते है, यद्यपि यह एक तुलनात्मक रूप से छोटा क्षेत्र है। क्योंकि आव्यूह और सदिश के कई गुण, कारक और संचालको पर भी लागू होते हैं, संख्यात्मक रैखिक बीजगणित को एक प्रकार के कार्यात्मक विश्लेषण के रूप में भी देखा जा सकता है, जिसमें व्यावहारिक कलन विधि पर विशेष महत्व दिया जाता है।

संख्यात्मक रैखिक बीजगणित में सामान्य समस्याओं में आव्यूह अपघटन जैसे विलक्षण (singular) मान अपघटन, QR गुणन, LU गुणन, या आइगेन अपघटन प्राप्त करना सम्मिलित है, जिसका उपयोग सामान्य रैखिक बीजगणितीय समस्याओं का उत्तर देने के लिए किया जा सकता है जैसे समीकरणों की रैखिक प्रणाली को हल करना, आइगेन मान का पता लगाना, या कम से कम वर्ग अनुकूलन कलनविधि विकसित करने के साथ संख्यात्मक रैखिक बीजगणित की केंद्रीय महत्व जो परिमित सटीक कंप्यूटर मे वास्तविक आँकड़ा पर लागू होने पर त्रुटियों का परिचय नहीं देती है, प्रायः प्रत्यक्ष के अतिरिक्त पुनरावृत्त तरीकों से प्राप्त की जाती है।

इतिहास

जॉन वॉन न्यूमैन, एलन ट्यूरिंग, जेम्स एच विल्किंसन, एलस्टन स्कॉट हाउसहोल्डर, जॉर्ज फ़ोर्सिथ और हेंज रूटिशौसर जैसे कंप्यूटर खोज करने वालों द्वारा संख्यात्मक रैखिक बीजगणित विकसित किया गया था, ताकि प्रारम्भिक कंप्यूटरों को निरंतर गणित की समस्याओं, जैसे कि प्राक्षेपिकीय (ballistics) समस्याओं के लिए लागू किया जा सके। तथा आंशिक अवकल समीकरणों की प्रणालियों का समाधान 1947 में जॉन वॉन न्यूमैन और हरमन गोल्डस्टाइन का कार्य वास्तविक आँकड़ा के लिए कलनविधि के अनुप्रयोग में कंप्यूटर त्रुटि को कम करने का पहला गंभीर प्रयास है। इस क्षेत्र का विकास हुआ है क्योंकि तकनीक ने अत्यधिक बड़े उच्च-परिशुद्धता आव्यूह पर जटिल समस्याओं को हल करने के लिए शोधकर्ताओं को तेजी से सक्षम किया है, और कुछ संख्यात्मक कलनविधि प्रमुखता से बढ़े ,हैं क्योंकि समानांतर कंप्यूटिंग जैसी तकनीकों ने उन्हें वैज्ञानिक समस्याओं के लिए व्यावहारिक दृष्टिकोण बना दिया है।

आव्यूह अपघटन

विभाजित आव्यूह

Main article: ब्लॉक आव्यूह

व्यावहारिक रेखीय बीजगणित में कई समस्याओं के लिए, स्तंभ (column) सदिशों के संयोजन के रूप में आव्यूह के परिप्रेक्ष्य को चुनना उपयोगी होता है।

उदाहरण के लिए, रैखिक प्रणाली को हल करते समय $x=A^{-1}b$ के उत्पाद के रूप में समझने के अतिरिक्त $A^{-1}$ b के साथ, A के स्तंभ द्वारा गठित आधार में b के रैखिक विस्तार में गुणांक के सदिश के रूप में x के बारे में सोचना सहायक होता है। आव्यूह को स्तंभों के संयोजन के रूप में सोचना भी आव्यूह कलनविधि के प्रयोजनों के लिए एक व्यावहारिक दृष्टिकोण है एक आव्यूह A के कॉलम पर और दूसरा A की पंक्तियों पर उदाहरण के लिए, आव्यूह के लिए $A^{m\times n}$ और सदिश $x^{n\times 1}$ और $y^{m\times 1}$, हम Ax + y की गणना करने के लिए कॉलम विभाजन परिप्रेक्ष्य का उपयोग कर सकते हैं।

for q = 1:n
 for p = 1:m
  y (p) = A (p,q)*x (q) + y (p)
 end
end

विलक्षण मान अपघटन

Main article: विलक्षण मान अपघटन

एक आव्यूह $A^{m\times n}$ का विलक्षण मान अपघटन $A=U\Sigma V^{\ast }$ है जहां U और V एकात्मक आव्यूह हैं, और $\Sigma$ विकर्ण आव्यूह है। तथा विकर्ण प्रविष्टियाँ $\Sigma$ A के विलक्षण मान कहलाती हैं। क्योंकि विलक्षण मान के अभिलक्षणिक (eigen) मान ​​​​के वर्गमूल $AA^{\ast }$ हैं, विलक्षण मान अपघटन और अभिलक्षणिक मान अपघटन के बीच एक जटिल संबंध है। इसका अर्थ यह है कि विलक्षण मान अपघटन की गणना के लिए अधिकांश विधियाँ अभिलक्षणिक मान विधियों के समान होती हैं। संभवतः सबसे सामान्य हाउसहोल्डर (Householder) प्रक्रिया विधि सम्मिलित है।

QR गुणनखण्ड

Main article: QR अपघटन

एक आव्यूह $A^{m\times n}$ का QR गुणनखण्ड आव्यूह $Q^{m\times m}$ और $R^{m\times n}$ है। इसलिए A = QR, जहाँ Q लंबकोणीय (orthogonal) आव्यूह है और R त्रिकोणीय (triangular) आव्यूह है। QR गुणनखंडों की गणना के लिए दो मुख्य कलन विधि हाउसहोल्डर प्रक्रिया और ग्राम-श्मिट प्रक्रिया हैं। QR गुणनखण्ड का उपयोग प्रायः रैखिक न्यूनतम-वर्ग समस्याओं और अभिलक्षणिक मान समस्याओं (पुनरावृत्ति QR एल्गोरिथम के माध्यम से) को हल करने के लिए किया जाता है।

LU गुणनखण्ड

Main article: LU अपघटन

आव्यूह A के LU गुणनखण्ड में निम्न त्रिकोणीय आव्यूह L और एक ऊपरी त्रिकोणीय आव्यूह U होता है ताकि A = LU हो।। आव्यूह U एक ऊपरी त्रिकोणीयकरण प्रक्रिया द्वारा पाया जाता है जिसमें आव्यूह की एक श्रृंखला द्वारा बाएं-गुणा A सम्मिलित होता है $M_{1},\ldots ,M_{n-1}$ उत्पाद बनाने के लिए $M_{n-1}\cdots M_{1}A=U$, जिससे कि समान रूप से $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$.

अभिलक्षणिक मान अपघटन

Main article: आव्यूह का अतिलक्षणिक अपघटन

आव्यूह $A^{m\times m}$ का अभिलक्षणिक मान अपघटन $A=X\Lambda X^{-1}$ है , जहां X के कॉलम A का अभिलक्षणिक सदिश हैं, और $\Lambda$ एक विकर्ण आव्यूह है जिसकी विकर्ण प्रविष्टियाँ A के संगत अभिलक्षणिक मान हैं। एक स्वेच्छ (arbitrary) आव्यूह के अभिलक्षणिक मान अपघटन को खोजने के लिए कोई प्रत्यक्ष तरीका नहीं होता है। क्योंकि एक प्रोग्राम लिखना संभव नहीं है, जो सीमित समय में एक यादृच्छिक बहुपद के सटीक वर्गो को ढूंढता है, किसी भी सामान्य अभिलक्षणिक मान समाधानकर्ता को आवश्यक रूप से पुनरावृत्तीय होना चाहिए।

कलनविधि (Algorithms)

गाऊसी विलोपन

Main article: गाउस विलोपन

संख्यात्मक रेखीय बीजगणित के दृष्टिकोण से गाउस विलोपन एक आव्यूह A को उसके LU गुणनखण्ड में कारक बनाने की एक प्रक्रिया है, जिसे गाउस विलोपन आव्यूह की कार्यप्रणाली द्वारा बाएं-गुणा A द्वारा $L_{m-1}\cdots L_{2}L_{1}A=U$ पूरा करता है। जब तक U ऊपरी त्रिकोणीय है और L निचला त्रिकोणीय है, जहां $L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}$. गाउस विलोपन के लिए सरल कार्यक्रम अत्यधिक अस्थिर हैं, और कई महत्वपूर्ण अंकों के साथ आव्यूह पर लागू होने पर बड़ी त्रुटियां उत्पन्न करते हैं। सबसे सरल समाधान धुरी तत्व को प्रस्तुत करना है, एक संशोधित गाउस विलोपन कलनविधि उत्पन्न करता है, जो स्थिर होता है।

रैखिक प्रणालियों के समाधान

Main article: रैखिक समीकरणों की प्रणाली

संख्यात्मक रैखिक बीजगणित विशेष रूप से स्तंभ सदिश के संयोजन के रूप में आव्यूह तक पहुंचता है। रैखिक प्रणाली को हल करने के लिए $x=A^{-1}b$, पारंपरिक बीजगणितीय दृष्टिकोण x को उत्पाद के रूप में $A^{-1}$ बी के साथ समझना है। संख्यात्मक रैखिक बीजगणित इसके अतिरिक्त A के स्तंभों द्वारा गठित आधार में b के रैखिक विस्तार के गुणांक के सदिश के रूप में x की व्याख्या करता है।

आव्यूह A और सदिश x और b की विशेषताओं के आधार पर, रैखिक समस्या को हल करने के लिए कई अलग-अलग अपघटन का उपयोग किया जा सकता है, जो दूसरों की तुलना में एक कारक को प्राप्त करना बहुत आसान बना सकता है। यदि A = QR, A का QR गुणनखंड है, तो समतुल्य $Rx=Q^{\ast }b$. आव्यूह गुणनखण्ड के रूप में गणना करना आसान होता है। यदि $A=X\Lambda X^{-1}$ एक अभिलक्षणिक A है, और हम b खोजने की कोशिश करते हैं ताकि b = Ax, के साथ $b'=X^{-1}b$ और $x'=X^{-1}x$, तो हमारे पास $b'=\Lambda x'$ हैं . यह विलक्षण मान अपघटन का उपयोग करते हुए रैखिक प्रणाली के समाधान से निकटता से संबंधित है, क्योंकि एक आव्यूह के विलक्षण मान इसके अभिलक्षणिक मान के वर्गमूल हैं। और यदि A = LU, A का LU गुणनखंड है, तो Ax = b को त्रिकोणीय आव्यूह Ly = b और Ux = y का उपयोग करके हल किया जा सकता है।

कम से कम वर्ग अनुकूलन

Main article: रैखिक कम से कम वर्गों के लिए संख्यात्मक तरीके

आव्यूह अपघटन रैखिक प्रणाली r = b - Ax को हल करने के कई तरीके हैं, जहाँ हम r को कम करना चाहते हैं, जैसा कि प्रतिगमन समस्या में है। QR कलनविधि पहले y = Ax को परिभाषित करके और फिर A के घटे हुए QR गुणनखंड की गणना करके और प्राप्त करने के लिए पुनर्व्यवस्थित करके ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ इस समस्या को हल करता है। यह ऊपरी त्रिकोणीय प्रणाली तब b के लिए हल की जा सकती है। SVD रैखिक कम से कम वर्ग प्राप्त करने के लिए एक कलनविधि भी सुझाव है। कम SVD अपघटन की गणना करके $A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }$ और फिर सदिश की गणना करना ${\widehat {U}}^{\ast }b$, हम कम से कम वर्ग समस्या को सरल विकर्ण प्रणाली में कम करते हैं। तथ्य यह है कि QR और SVD गुणनखंडों द्वारा कम से कम वर्गों के समाधान का उत्पादन किया जा सकता है, इसका अर्थ है कि रैखिक कम से कम वर्गों के लिए शास्त्रीय (classical) संख्यात्मक तरीकों के अतिरिक्त # कम से कम वर्गों की समस्याओं को हल करने के लिए सामान्य समीकरणों के आव्यूह को उलट देना, इन समस्याओं को भी हल किया जा सकता है तथा उन विधियों द्वारा जिनमें ग्राम-श्मिट कलनविधि और हाउसहोल्डर विधियाँ सम्मिलित हैं।

अनुकूलन और स्थिरता (Conditioning and stability)

Main article: संख्यात्मक विश्लेषण § संख्यात्मक स्थिरता और अच्छी तरह से उत्पन्न समस्याएं

अनुमति दें कि एक समस्या एक कार्य $f:X\to Y$ है , जहां X आँकड़ा का एक मानक सदिश समष्टि है और Y समाधानों का भि एक मानक सदिश समष्टि है। कुछ आँकड़ा बिंदु के लिए $x\in X$, समस्या को कुगठित (ill-conditioned) त्रिकोण स्थिति कहा जाता है। यदि x में एक अल्प क्षोभ (perturbation) f (x) के मान में एक बड़ा परिवर्तन उत्पन्न करता है। हम एक प्रतिबंधी संख्या को परिभाषित करके इसकी मात्रा निर्धारित कर सकते हैं जो दर्शाती है कि समस्या कितनी अच्छी तरह से वातानुकूलित है, जिसे परिभाषित किया गया है।

$${\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.$$

अस्थिरता कंप्यूटर कलनविधि की प्रवृत्ति है, जो चल बिन्दु (floating-point) परिकलन पर निर्भर करती है, ऐसे परिणाम उत्पन्न करने के लिए जो किसी समस्या के सटीक गणितीय समाधान से प्रभावशाली तरीके से भिन्न होते हैं। जब एक आव्यूह में कई महत्वपूर्ण अंकों के साथ वास्तविक आँकड़ा होता है, तो समीकरणों की रैखिक प्रणाली या कम से कम वर्गों के अनुकूलन जैसी समस्याओं को हल करने के लिए कई कलनविधि अत्यधिक गलत परिणाम उत्पन्न कर सकते हैं। कुगठित स्थिति वाली समस्याओं के लिए स्थिर कलनविधि बनाना संख्यात्मक रेखीय बीजगणित में एक केंद्रीय सोचने का विषय है। एक उदाहरण यह है कि हाउसहोल्डर त्रिकोणीयकरण की स्थिरता इसे रैखिक प्रणालियों के लिए एक विशेष रूप से जटिल समाधान विधि बनाती है, जबकि कम से कम वर्गों की समस्याओं को हल करने के लिए सामान्य समीकरण पद्धति की अस्थिरता आव्यूह अपघटन विधियों का पक्ष लेने का एक कारण है, जैसे विलक्षण मान अपघटन का उपयोग करना, कुछ आव्यूह अपघटन विधियाँ अस्थिर हो सकती हैं, लेकिन उनमें सीधे संशोधन होते हैं, जो उन्हें स्थिर बनाते हैं। एक उदाहरण अस्थिर ग्राम-श्मिट है, जिसे स्थिर संशोधित ग्राम-श्मिट का उत्पादन करने के लिए आसानी से परिवर्तित किया जा सकता है। संख्यात्मक रेखीय बीजगणित में एक और शास्त्रीय समस्या यह है कि गाउस विलोपन अस्थिर होता है, लेकिन धुरी के प्रारम्भ के साथ स्थिर हो जाता है।

पुनरावृत्ति के तरीके (Iterative methods)

Main article: पुनरावर्ती तरीके

दो कारण हैं कि पुनरावृत्ति कलनविधि संख्यात्मक रैखिक बीजगणित का एक महत्वपूर्ण भाग हैं। सबसे पहले, कई महत्वपूर्ण संख्यात्मक समस्याओं का कोई सीधा समाधान नहीं होता है। एक यादृच्छिक (arbitrary) आव्यूह के अभिलक्षणिक मान ​​​​और अभिलक्षणिक सदिश को खोजने के लिए, हम केवल एक पुनरावृत्ति दृष्टिकोण को अपना सकते हैं। दूसरा, यादृच्छिक के लिए गैर-साहित्यिक कलनविधि $m\times m$ आव्यूह की आवश्यकता है $O(m^{3})$ समय, जो आश्चर्यजनक रूप से प्रखर है, यह देखते हुए कि आव्यूह में केवल $m^{2}$ संख्या सम्मिलित हैं। पुनरावृत्त दृष्टिकोण इस समय को कम करने के लिए कुछ आव्यूह की कई विशेषताओं का लाभ उठा सकते हैं। उदाहरण के लिए, जब एक आव्यूह विरल आव्यूह होता है, तो एक पुनरावृत्त कलनविधि के कई चरणों को छोड़ सकता है, तथा एक प्रत्यक्ष दृष्टिकोण का अनिवार्य रूप से पालन करेंगे, यद्यपि वे अत्यधिक संरचित आव्यूह दिए गए निरर्थक चरण हों।

संख्यात्मक रेखीय बीजगणित में कई पुनरावृत्त विधियों का मूल एक निम्न आयामी क्राइलोव उप-स्थान पर एक आव्यूह का प्रक्षेपण है, जो एक उच्च-आयामी आव्यूह की सुविधाओं को कम आयाम वाले स्थान में प्रारम्भ होने वाले समान आव्यूह की समतुल्य विशेषताओं की पुनरावृत्त रूप से गणना करके अनुमानित करने की अनुमति देता है। और क्रमिक रूप से उच्च आयामों की ओर बढ़ रहा है। जब A सममित होता है और हम रैखिक समस्या Ax = b को हल करना चाहते हैं, शास्त्रीय पुनरावृत्त दृष्टिकोण संयुग्मी प्रवणता विधि है। यदि A सममित नहीं है, तो रैखिक समस्या के पुनरावृत्त समाधान के उदाहरण सामान्यीकृत न्यूनतम अवशिष्ट विधि और सामान्य समीकरणों पर संयुग्मित प्रवणता विधि # संयुग्म प्रवणता हैं। यदि A सममित है, तो अभिलक्षणिक मान ​​​​और अभिलक्षणिक सदिश समस्या को हल करने के लिए हम लैंक्ज़ोस (Lanczos) कलनविधि का उपयोग कर सकते हैं, और यदि A गैर-सममित है, तो हम अर्नोल्डी (Arnoldi) पुनरावृति का उपयोग कर सकते हैं।

सॉफ्टवेयर

Main article: संख्यात्मक विश्लेषण सॉफ्टवेयर की सूची

कई प्रोग्रामिंग भाषाए संख्यात्मक रैखिक बीजगणित अनुकूलन तकनीकों का उपयोग करती हैं और संख्यात्मक रैखिक बीजगणित कलनविधि को लागू करने के लिए बनाई की गई हैं इन भाषाओं में MATLAB, Analytica (सॉफ़्टवेयर), Maple और Mathematica सम्मिलित हैं। अन्य प्रोग्रामिंग भाषाएं जो स्पष्ट रूप से संख्यात्मक रैखिक बीजगणित के लिए प्रारूपित नहीं की गई हैं, वे पुस्तकालय (लाइब्रेरी) मे जो संख्यात्मक रैखिक बीजगणित दिनचर्या और अनुकूलन प्रदान करते हैं। C (प्रोग्रामिंग भाषा) और फोरट्रान के पास प्रारम्भिक रेखीय बीजगणित उपप्रोग्राम और LAPACK जैसे पैकेज हैं, पायथन (python) में पुस्तकालय NumPy है, और पर्ल (Perl) के पास पर्ल डेटा भाषा है। R (प्रोग्रामिंग भाषा) में कई संख्यात्मक रैखिक बीजगणित तर्क LAPACK जैसे इन अधिक मुख्य पुस्तकालयों पर निर्भर करते हैं। अधिक पुस्तकालयों को संख्यात्मक पुस्तकालयों की सूची में प्राप्त किया जा सकता है।

आगे की पढाई (Further reading)

• Dongarra, Jack; Hammarling, Sven (1990). "Evolution of Numerical Software for Dense Linear Algebra". In Cox, M. G.; Hammarling, S. (eds.). Reliable Numerical Computation. Oxford: Clarendon Press. pp. 297–327. ISBN 0-19-853564-3.

बाहरी लिंक्ड (External links)

• Freely available software for numerical algebra on the web, composed by Jack Dongarra and Hatem Ltaief, University of Tennessee
• NAG Library of numerical linear algebra routines
• Numerical Linear Algebra Group on Twitter (Research group in the United Kingdom)
• siagla on Twitter (Activity group about numerical linear algebra in the Society for Industrial and Applied Mathematics)
• The GAMM Activity Group on Applied and Numerical Linear Algebra