जावा उलटा मैट्रिक्स गणना

Question

मैं जावा में व्यस्त मैट्रिक्स की गणना करने की कोशिश कर रहा हूं।

मैं adjoint विधि का पालन कर रहा हूं (adjoint मैट्रिक्स की पहली गणना, फिर इस मैट्रिक्स को स्थानांतरित करें और अंत में, निर्धारक के मूल्य के विपरीत के लिए इसे गुणा करें)।

यह काम करता है जब मैट्रिक्स बहुत बड़ा नहीं होता है। मैंने जांच की है कि मैट्रिक्स के लिए 12x12 के आकार तक परिणाम तुरंत प्रदान किया जाता है। हालांकि, जब मैट्रिक्स 12x12 से बड़ा होता है, तो उस समय गणना को पूरा करने की आवश्यकता होती है जो तेजी से बढ़ जाती है।

मैट्रिक्स मुझे उलटा करने की आवश्यकता है 1 9 x19 है, और इसमें बहुत अधिक समय लगता है। विधि जो अधिक समय लेती है वह निर्धारक की गणना के लिए उपयोग की जाने वाली विधि है।

कोड मैं का उपयोग कर रहा है:

public static double determinant(double[][] input) { 
    int rows = nRows(input);  //number of rows in the matrix 
    int columns = nColumns(input); //number of columns in the matrix 
    double determinant = 0; 

    if ((rows== 1) && (columns == 1)) return input[0][0]; 

    int sign = 1;  
    for (int column = 0; column < columns; column++) { 
    double[][] submatrix = getSubmatrix(input, rows, columns,column); 
    determinant = determinant + sign*input[0][column]*determinant(submatrix); 
    sign*=-1; 
    } 
    return determinant; 
} 

किसी को कैसे और अधिक कुशलता से एक बड़ी मैट्रिक्स के निर्धारक गणना करने के लिए पता है? यदि नहीं, तो क्या कोई जानता है कि अन्य एल्गोरिदम का उपयोग करके बड़े मैट्रिक्स के उलटा कैलकुलेट कैसे करें?

धन्यवाद

Answer 1

घातीय रूप से? नहीं, मेरा मानना ​​है कि मैट्रिक्स उलटा ओ (एन^3) है।

मैट्रिक्स समीकरण को हल करने के लिए LU decomposition का उपयोग करने की सलाह दूंगा। जब आप इसका उपयोग करते हैं तो आपको निर्धारक के लिए हल करने की आवश्यकता नहीं है।

बेहतर अभी तक, आपकी सहायता के लिए एक पैकेज में देखें। JAMA दिमाग में आता है।

12x12 या 1 9 x19 बड़ी मैट्रिक्स नहीं हैं। आजादी की डिग्री के दसियों या सैकड़ों हजार के साथ समस्याओं को हल करना आम बात है।

यहां जामा का उपयोग करने का एक उदाहरण उदाहरण है।

package linearalgebra; 

import Jama.LUDecomposition; 
import Jama.Matrix; 

public class JamaDemo 
{ 
    public static void main(String[] args) 
    { 
     double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}}; // each array is a row in the matrix 
     double [] rhs = { 9, 1, 0 }; // rhs vector 
     double [] answer = { 1, 2, 3 }; // this is the answer that you should get. 

     Matrix a = new Matrix(values); 
     a.print(10, 2); 
     LUDecomposition luDecomposition = new LUDecomposition(a); 
     luDecomposition.getL().print(10, 2); // lower matrix 
     luDecomposition.getU().print(10, 2); // upper matrix 

     Matrix b = new Matrix(rhs, rhs.length); 
     Matrix x = luDecomposition.solve(b); // solve Ax = b for the unknown vector x 
     x.print(10, 2); // print the solution 
     Matrix residual = a.times(x).minus(b); // calculate the residual error 
     double rnorm = residual.normInf(); // get the max error (yes, it's very small) 
     System.out.println("residual: " + rnorm); 
    } 
} 

यहाँ एक ही समस्या है अपाचे कॉमन्स गणित का उपयोग कर हल quant_dev की सिफारिश के अनुसार:

package linearalgebra; 

import org.apache.commons.math.linear.Array2DRowRealMatrix; 
import org.apache.commons.math.linear.ArrayRealVector; 
import org.apache.commons.math.linear.DecompositionSolver; 
import org.apache.commons.math.linear.LUDecompositionImpl; 
import org.apache.commons.math.linear.RealMatrix; 
import org.apache.commons.math.linear.RealVector; 

public class LinearAlgebraDemo 
{ 
    public static void main(String[] args) 
    { 
     double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}}; 
     double [] rhs = { 9, 1, 0 }; 

     RealMatrix a = new Array2DRowRealMatrix(values); 
     System.out.println("a matrix: " + a); 
     DecompositionSolver solver = new LUDecompositionImpl(a).getSolver(); 

     RealVector b = new ArrayRealVector(rhs); 
     RealVector x = solver.solve(b); 
     System.out.println("solution x: " + x);; 
     RealVector residual = a.operate(x).subtract(b); 
     double rnorm = residual.getLInfNorm(); 
     System.out.println("residual: " + rnorm); 
    } 
} 

अपनी स्थिति के लिए इन अनुकूलन जब आप संकलन और चलाने के लिए अपनी CLASSPATH में जामा जार करना होगा।

Answer 2

मैट्रिक्स उलटा कम्प्यूटेशनल रूप से बहुत गहन है। चूंकि डफिमो ने उत्तर दिया कि लू एक अच्छा एल्गोरिदम है, और अन्य रूप हैं (उदाहरण के लिए क्यूआर)।

दुर्भाग्यवश आप भारी गणना से छुटकारा नहीं पा सकते हैं ... और यदि आप अनुकूलित लाइब्रेरी का उपयोग नहीं कर रहे हैं तो शायद बोटलैक getSubmatrix विधि है।

इसके अलावा, विशेष मैट्रिक्स संरचनाएं (बैंड-मैट्रिकिटी, समरूपता, विकर्णता, दुर्लभता) गणना में मानी जाने पर प्रदर्शन में एक बड़ा प्रभाव डालती है। आपका माइलेज भिन्न हो सकता है ...

Answer 3

आप इस तरह से एक व्यस्त मैट्रिक्स की गणना कभी नहीं करना चाहते हैं। ठीक है, उलटा स्वयं की गणना से बचा जाना चाहिए, क्योंकि यह एक ल्यू जैसे कारक बनाने के लिए लगभग हमेशा बेहतर होता है।

रिकर्सिव कंप्यूटेशंस का उपयोग करके निर्धारक की गणना एक संख्यात्मक अश्लील काम है। यह पता चला है कि एक निर्धारक की गणना करने के लिए एक LU कारक का उपयोग करना बेहतर विकल्प है।लेकिन, यदि आप LU कारकों की गणना करने के लिए परेशान होने जा रहे हैं, तो आप संभवतः उलटा गणना क्यों करना चाहेंगे? आप LU कारकों की गणना करके पहले से ही कठिन काम कर चुके हैं।

एक बार आपके पास LU कारक होने के बाद, आप उन्हें वापस करने और प्रतिस्थापन को आगे बढ़ाने के लिए उपयोग कर सकते हैं।

जहां तक ​​1 9 x 9 1 मैट्रिक्स बड़ा होता है, यह उतना ही करीब नहीं है जितना मैं बड़ा सोचता हूं।

Answer 4

मैटलैब को अपने खेल में हरा करना मुश्किल है। वे परिशुद्धता के बारे में भी सावधान हैं। यदि आपके पास 2.0 और 2.00001 पिवट के रूप में हैं - देखें! आपका जवाब बहुत कमजोर हो सकता है। इसके अलावा, पाइथन के कार्यान्वयन की जांच करें (यह कहीं भी numpy/scipy में है ...)

Answer 5

एक निर्धारक की गणना करने के लिए आपका एल्गोरिदम वास्तव में घातीय है। मूल समस्या यह है कि आप परिभाषा से गणना कर रहे हैं, और सीधी परिभाषा गणना करने के लिए subdeterminants की घातीय राशि की ओर जाता है। इसके निर्धारक या इसके विपरीत की गणना करने से पहले आपको वास्तव में पहले मैट्रिक्स को बदलने की आवश्यकता है। (मैंने गतिशील प्रोग्रामिंग के बारे में बताने के बारे में सोचा था, लेकिन इस समस्या को गतिशील प्रोग्रामिंग द्वारा हल नहीं किया जा सकता है क्योंकि उपप्रोबम्स की संख्या घातीय भी है।)

LU decomposition, जैसा कि दूसरों द्वारा अनुशंसित किया गया है, एक अच्छा विकल्प है। यदि आप मैट्रिक्स गणना के लिए नए हैं, तो आप निर्धारक और उलटा गणना करने के लिए गॉसियन उन्मूलन को भी देखना चाहेंगे, क्योंकि पहले इसे समझना थोड़ा आसान हो सकता है।

और मैट्रिक्स उलटाई में याद रखने की एक बात संख्यात्मक स्थिरता है, क्योंकि आप फ़्लोटिंग पॉइंट नंबर से निपट रहे हैं। सभी अच्छे एल्गोरिदम में उपयुक्त पिवट चुनने के लिए पंक्तियों और/या स्तंभों के क्रमिक क्रम शामिल होते हैं, जिन्हें वे कहते हैं। कम से कम गॉसियन उन्मूलन में, आप कॉलम परमिट करने के लिए प्रत्येक चरण में, ताकि पूर्ण मूल्य में सबसे बड़ा तत्व पिवट के रूप में चुना जाता है, क्योंकि यह सबसे स्थिर विकल्प है।

Answer 6

मैं इसके लिए अपाचे कॉमन्स मैथ 2.0 का उपयोग करने की सलाह दूंगा। जामा एक मृत परियोजना है। एसीएम 2.0 ने वास्तव में जामा से रैखिक बीजगणित लिया और इसे और विकसित किया।

Answer 7

क्या आपके पास सही समाधान होना चाहिए? एक अनुमानित सॉल्वर (Gauss-Seidel बहुत ही प्रभावशाली और कार्यान्वित करने में आसान है) आपके लिए काम करेगा, और बहुत तेज़ी से अभिसरण करेगा। 1 9 x 9 1 काफी छोटा मैट्रिक्स है। मुझे लगता है कि मैंने जो गॉस-सेडल कोड इस्तेमाल किया था, वह आंखों के झपकी में 128x128 मैट्रिक्स को हल कर सकता है (लेकिन मुझे उस पर उद्धरण न दें, यह थोड़ी देर हो गया है)।

Answer 8

la4j (जावा के लिए लीनियर बीजगणित) पुस्तकालय मैट्रिक्स उलटा समर्थन करता है।

Matrix a = new Basic2DMatrix(new double[][]{ 
    { 1.0, 2.0, 3.0 }, 
    { 4.0, 5.0, 6.0 }, 
    { 7.0, 8.0. 9.0 } 
}); 

Matrix b = a.invert(Matrices.DEFAULT_INVERTOR); // uses Gaussian Elimination 

Answer 9

के बाद से एसीएम पुस्तकालय वर्षों में अपडेट किया गया है, यहाँ कार्यान्वयन मैट्रिक्स उलट के लिए नवीनतम परिभाषा के अनुरूप है: यहाँ संक्षिप्त उदाहरण है।

import org.apache.commons.math3.linear.Array2DRowRealMatrix; 
import org.apache.commons.math3.linear.ArrayRealVector; 
import org.apache.commons.math3.linear.DecompositionSolver; 
import org.apache.commons.math3.linear.LUDecomposition; 
import org.apache.commons.math3.linear.RealMatrix; 
import org.apache.commons.math3.linear.RealVector; 

public class LinearAlgebraDemo 
{ 
    public static void main(String[] args) 
    { 
     double [][] values = {{1, 1, 2}, {2, 4, -3}, {3, 6, -5}}; 
     double [][] rhs = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; 

     // Solving AB = I for given A 
     RealMatrix A = new Array2DRowRealMatrix(values); 
     System.out.println("Input A: " + A); 
     DecompositionSolver solver = new LUDecomposition(A).getSolver(); 

     RealMatrix I = new Array2DRowRealMatrix(rhs); 
     RealMatrix B = solver.solve(I); 
     System.out.println("Inverse B: " + B); 
    } 
} 

Answer 10

LU अपघटन स्पैस मैट्रिस के लिए अच्छी तरह से काम करता है। अन्य गॉस जोर्डन कर सकते हैं। आप डोडसन विधि को भी आजमा सकते हैं, लेकिन आपको शून्य से विभाजन के साथ सावधान रहना चाहिए।