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

संख्यात्मक रेखीय बीजगणित, जिसे कभी-कभी व्यावहारिक रेखीय बीजगणित भी कहा जाता है, यह अध्ययन है कि कंप्यूटर कलनविधि बनाने के लिए आव्यूह(मैट्रिक्स) संचालन का उपयोग कैसे किया जा सकता है, जो कुशलतापूर्वक गणित में प्रश्नों के अनुमानित उत्तर निरन्तर और सटीक रूप से प्रदान करते हैं। यह संख्यात्मक विश्लेषण का उपक्षेत्र है, और एक प्रकार का रेखीय बीजगणित है। जो कंप्यूटर चल बिन्दु(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: singular value decomposition

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

क्यूआर गुणनखंड

Main article: QR decomposition

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

लू गुणनखंड

Main article: LU decomposition

आव्यूह A के LU गुणनखंड में निम्न त्रिकोणीय आव्यूह L और एक ऊपरी त्रिकोणीय आव्यूह U होता है ताकि A = LU हो। आव्यूह यू एक ऊपरी त्रिकोणीयकरण प्रक्रिया द्वारा पाया जाता है जिसमें आव्यूह की एक श्रृंखला द्वारा बाएं-गुणा ए शामिल होता है $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: Eigendecomposition of a matrix

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

एल्गोरिदम

गाऊसी उन्मूलन

Main article: Gaussian elimination

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

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

Main article: System of linear equations

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

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

Main article: Numerical methods for linear least squares

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

कंडीशनिंग और स्थिरता

Main article: Numerical analysis § Numerical stability and well-posed problems

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

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

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

पुनरावृत्ति के तरीके

Main article: Iterative methods

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

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

सॉफ्टवेयर

Main article: List of numerical analysis software

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

आगे की पढाई

• 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.

इस पेज में लापता आंतरिक लिंक की सूची

• फ़्लोटिंग-पॉइंट अंकगणित
• अंक शास्त्र
• पदार्थ विज्ञान
• बायोइनफॉरमैटिक्स
• सीमित तत्व विधि
• अनिश्चितता का प्रसार
• द्रव गतिविज्ञान
• मूर्ति प्रोद्योगिकी
• अंतर समीकरण
• लीनियर अलजेब्रा
• क्यूआर फैक्टराइजेशन
• विलक्षण मान अपघटन
• चलने का
• लू गुणनखंडन
• आंशिक विभेदक समीकरण
• गुणक
• आधार (रैखिक बीजगणित)
• विलक्षण मूल्य
• क्यूआर एल्गोरिदम
• रैखिक न्यूनतम-वर्ग
• रेखीय प्रतिगमन
• हालत संख्या
• लैंक्ज़ोस एल्गोरिथम
• क्रायलोव सबस्पेस
• अर्नोल्ड पुनरावृत्ति
• मेपल (सॉफ्टवेयर)
• पायथन (प्रोग्रामिंग भाषा)
• एनालिटिका (सॉफ्टवेयर)
• सी (प्रोग्रामिंग भाषा)

बाहरी कड़ियाँ

• 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