एक रैखिक समीकरण हल करना

मुझे सी, उद्देश्य सी, या (यदि आवश्यक हो) सी ++ में रैखिक समीकरणों की एक प्रणाली को प्रोग्रामेटिक रूप से हल करने की आवश्यकता है।

समीकरणों का एक उदाहरण यहां दिया गया है:

-44.3940 = a * 50.0 + b * 37.0 + tx
-45.3049 = a * 43.0 + b * 39.0 + tx
-44.9594 = a * 52.0 + b * 41.0 + tx

इससे, मैं a , b , और tx के लिए सबसे अच्छा अनुमान प्राप्त करना चाहता हूं।

0
जोड़ा संपादित
विचारों: 2
अन्य लोगों ने इसका उत्तर दिया है, लेकिन किन्साइड और चेनी द्वारा न्यूमेरिकल एनालिसिस: वैज्ञानिक कंप्यूटिंग के गणित पुस्तक को देखें। पुस्तक बड़े पैमाने पर समीकरणों की विभिन्न प्रणालियों को हल करने के बारे में है।
जोड़ा लेखक Matthew, स्रोत

13 उत्तर

Reutenauer के "फ्री लाइ Algebras" में, खंड 7.6.2:

A direct bijection between primitive necklaces of length n over F and the set of irreducible polynomials of degree n in F[x] may be described as follows: let K be the field with qn elements; it is a vector space of dimension n over F, so there exists in K an element θ such that the set {θ, θq, ..., θqn-1} is a linear basis of K over F.

With each word w = a0...an-1 of length n on the alphabet F, associate the element β of K given by β = a0θ + a1θq + ... + an-1 θqn-1. It is easily shown that to conjugate words w, w' correspond conjugate elements β, β' in the field extension K/F, and that w \mapsto β is a bijection. Hence, to a primitive conjugation class corresponds a conjugation class of cardinality n in K; to the latter corresponds a unique irreducible polynomial of degree n in F[x]. This gives the desired bijection.

25
जोड़ा

See section 38.10 "Generating irreducible polynomials from Lyndon words" of http://www.jjj.de/fxt/#fxtbook

4
जोड़ा

मेरा मानना ​​है कि इस तरह के एक विभाजन में प्रस्तुत किया गया है

एस गोल्ब। इर्रेड्यूसिबल बहुपद, कोड सिंक्रनाइज़ करना, आदिम हार और चक्रवात बीजगणित। प्रक्रिया में कन्फ कॉम्बिनेटोरियल मैथ। और इसके एप्ला।, पेज 358- 370, चैपल हिल, 1 9 6 9। यूनिवर्सिटी। उत्तरी कैरोलिना प्रेस के।

लेकिन मेरे पास इस पेपर तक तुरंत पहुंच नहीं है - मुझे पूरा यकीन है कि यह वहां है।

3
जोड़ा
अतिरिक्त साक्ष्य का एक छोटा सा हिस्सा (अभी भी निर्णायक नहीं है): springerlink.com/index/P6X9P2BV73L2X2GG.pdf "जैसा कि लिंडन शब्दों के बीच एक विचित्रता है जो कार्डिनलिटी के वर्णमाला और एफके [10] पर irreducible polynomials पर वर्णित है ..." जहां संदर्भ [10] गोल्म्ब के पेपर के लिए है।
जोड़ा लेखक CodingWithoutComments, स्रोत
मुझे लगता है कि यह या तो कम से कम एक अन्य पेपर नहीं है ( Berstel "rel =" nofollow noreferrer "> jstor.org/stable/2001573"> Berstel और Reutenauer ) सुझाव देता है कि यह एक खुली समस्या है। असल में मेरे पास यह सवाल पूछने के लिए अनिवार्य रूप से एक ही प्रेरणा है, इसलिए मुझे लगता है कि मैं इस पेपर को अधिक सावधानी से पढ़ना चाहिए था।
जोड़ा लेखक Qiaochu Yuan, स्रोत

गोल्बॉम्ब द्वारा आविष्कार किया गया पत्राचार आदेश q ^ n के क्षेत्र में एक आदिम तत्व की पसंद पर निर्भर करता है। फिर, प्रत्येक लिंडन शब्द एल = (l_0, l_1, ..., l_ {n-1}) में से एक आदिम बहुपद को मूल रूप से एक ^ {एम (एल)} तत्व के रूप में निर्दिष्ट करता है जहां एम (एल) है l_i * q ^ का पूर्णांक योग i = 0,1, ..., n-1।

3
जोड़ा

क्या आप ऐसे सॉफ़्टवेयर पैकेज की तलाश में हैं जो काम करेगा या वास्तव में मैट्रिक्स ऑपरेशंस कर रहा है और ऐसा करेगा और प्रत्येक चरण करेगा?

पहला, मेरा एक सहकर्मी ने अभी Ocaml GLPK का उपयोग किया था। यह पीडीएफ । अगर आपको आगे बढ़ने में विशिष्ट सहायता की ज़रूरत है, तो हमें बताएं और मुझे यकीन है कि, मैं या कोई भी वापस भटक जाएगा और मदद करेगा, लेकिन, मुझे लगता है कि यह यहां से काफी आगे है। शुभ लाभ!

0
जोड़ा

निजी तौर पर, मैं संख्यात्मक व्यंजनों के एल्गोरिदम के आंशिक हूं। (मुझे सी ++ संस्करण का शौक है।)

यह पुस्तक आपको सिखाएगी कि एल्गोरिदम क्यों काम करते हैं, साथ ही आपको उन एल्गोरिदम के कुछ सुंदर-अच्छी तरह से डीबग किए गए कार्यान्वयन दिखाते हैं।

बेशक, आप केवल क्लासिक का उपयोग कर सकते हैं (मैंने इसे बड़ी सफलता के साथ उपयोग किया है), लेकिन मैं पहले गॉसियन एलिमिनेशन एल्गोरिदम को हाथ से टाइप करता हूं, कम से कम इस तरह के काम के बारे में एक बेहोश विचार है जो इन एल्गोरिदम को स्थिर बनाने में चला गया है।

बाद में, यदि आप अधिक दिलचस्प रैखिक बीजगणित कर रहे हैं, तो Octave के स्रोत कोड को देख रहे हैं। बहुत सारे सवालों का जवाब देंगे।

0
जोड़ा

आप इसे एक प्रोग्राम के साथ ठीक उसी तरह हल कर सकते हैं जैसे आप इसे हाथ से हल करते हैं (गुणा और घटाव के साथ, फिर परिणामों को समीकरणों में वापस खिलाते हैं)। यह सुंदर मानक माध्यमिक-विद्यालय स्तर के गणित है।

-44.3940 = 50a + 37b + c (A)
-45.3049 = 43a + 39b + c (B)
-44.9594 = 52a + 41b + c (C)

(A-B): 0.9109 =  7a -  2b (D)
(B-C): 0.3455 = -9a -  2b (E)

(D-E): 1.2564 = 16a (F)

(F/16):  a = 0.078525 (G)

Feed G into D:
       0.9109 = 7a - 2b
    => 0.9109 = 0.549675 - 2b (substitute a)
    => 0.361225 = -2b (subtract 0.549675 from both sides)
    => -0.1806125 = b (divide both sides by -2) (H)

Feed H/G into A:
       -44.3940 = 50a + 37b + c
    => -44.3940 = 3.92625 - 6.6826625 + c (substitute a/b)
    => -41.6375875 = c (subtract 3.92625 - 6.6826625 from both sides)

तो आप के साथ समाप्त होता है:

a =   0.0785250
b =  -0.1806125
c = -41.6375875

यदि आप इन मानों को ए, बी और सी में वापस प्लग करते हैं, तो आप पाएंगे कि वे सही हैं।

यह चाल एक साधारण 4x3 मैट्रिक्स का उपयोग करना है जो 3x2 मैट्रिक्स में बदल जाती है, फिर एक 2x1 जो "ए = एन" है, n वास्तविक संख्या है। एक बार आपके पास यह हो जाने के बाद, आप इसे अगले मैट्रिक्स में एक और मान प्राप्त करने के लिए फ़ीड करते हैं, फिर उन दो मानों को अगले मैट्रिक्स में तब तक फ़ीड करें जब तक आप सभी चर हल नहीं कर लेते।

बशर्ते आपके पास एन विशिष्ट समीकरण हों, आप हमेशा एन चर के लिए हल कर सकते हैं। मैं अलग कहता हूं क्योंकि ये दोनों नहीं हैं:

 7a + 2b =  50
14a + 4b = 100

वे वही समीकरण दो से गुणा हो गए हैं, इसलिए आप उनसे कोई समाधान नहीं प्राप्त कर सकते हैं - पहले दो को गुणा करके फिर आपको वास्तविक लेकिन बेकार कथन के साथ पत्तियों को घटाना:

0 = 0 + 0

उदाहरण के तौर पर, यहां कुछ सी कोड है जो आपके प्रश्न में एक साथ समीकरण समीकरणों को काम करता है। पहले कुछ आवश्यक प्रकार, चर, एक समीकरण मुद्रण के लिए एक समर्थन समारोह, और मुख्य की शुरुआत:

#include 

typedef struct { double r, a, b, c; } tEquation;
tEquation equ1[] = {
    { -44.3940,  50, 37, 1 },      // -44.3940 = 50a + 37b + c (A)
    { -45.3049,  43, 39, 1 },      // -45.3049 = 43a + 39b + c (B)
    { -44.9594,  52, 41, 1 },      // -44.9594 = 52a + 41b + c (C)
};
tEquation equ2[2], equ3[1];

static void dumpEqu (char *desc, tEquation *e, char *post) {
    printf ("%10s: %12.8lf = %12.8lfa + %12.8lfb + %12.8lfc (%s)\n",
        desc, e->r, e->a, e->b, e->c, post);
}

int main (void) {
    double a, b, c;

इसके बाद, तीन अज्ञातों के साथ तीन समीकरणों में दो अज्ञातों के साथ दो समीकरणों में कमी:

    // First step, populate equ2 based on removing c from equ.

    dumpEqu (">", &(equ1[0]), "A");
    dumpEqu (">", &(equ1[1]), "B");
    dumpEqu (">", &(equ1[2]), "C");
    puts ("");

    // A - B
    equ2[0].r = equ1[0].r * equ1[1].c - equ1[1].r * equ1[0].c;
    equ2[0].a = equ1[0].a * equ1[1].c - equ1[1].a * equ1[0].c;
    equ2[0].b = equ1[0].b * equ1[1].c - equ1[1].b * equ1[0].c;
    equ2[0].c = 0;

    // B - C
    equ2[1].r = equ1[1].r * equ1[2].c - equ1[2].r * equ1[1].c;
    equ2[1].a = equ1[1].a * equ1[2].c - equ1[2].a * equ1[1].c;
    equ2[1].b = equ1[1].b * equ1[2].c - equ1[2].b * equ1[1].c;
    equ2[1].c = 0;

    dumpEqu ("A-B", &(equ2[0]), "D");
    dumpEqu ("B-C", &(equ2[1]), "E");
    puts ("");

इसके बाद, दो अज्ञातों के साथ दो समीकरणों को एक अज्ञात के साथ एक समीकरण में कमी:

    // Next step, populate equ3 based on removing b from equ2.

    // D - E
    equ3[0].r = equ2[0].r * equ2[1].b - equ2[1].r * equ2[0].b;
    equ3[0].a = equ2[0].a * equ2[1].b - equ2[1].a * equ2[0].b;
    equ3[0].b = 0;
    equ3[0].c = 0;

    dumpEqu ("D-E", &(equ3[0]), "F");
    puts ("");

Now that we have a formula of the type number1 = unknown * number2, we can simply work out the unknown value with unknown <- number1 / number2. Then, once you've figured that value out, substitute it into one of the equations with two unknowns and work out the second value. Then substitute both those (now-known) unknowns into one of the original equations and you now have the values for all three unknowns:

    // Finally, substitute values back into equations.

    a = equ3[0].r / equ3[0].a;
    printf ("From (F    ), a = %12.8lf (G)\n", a);

    b = (equ2[0].r - equ2[0].a * a) / equ2[0].b;
    printf ("From (D,G  ), b = %12.8lf (H)\n", b);

    c = (equ1[0].r - equ1[0].a * a - equ1[0].b * b) / equ1[0].c;
    printf ("From (A,G,H), c = %12.8lf (I)\n", c);

    return 0;
}

उस कोड का आउटपुट इस उत्तर में पहले की गणना से मेल खाता है:

         >: -44.39400000 =  50.00000000a +  37.00000000b +   1.00000000c (A)
         >: -45.30490000 =  43.00000000a +  39.00000000b +   1.00000000c (B)
         >: -44.95940000 =  52.00000000a +  41.00000000b +   1.00000000c (C)

       A-B:   0.91090000 =   7.00000000a +  -2.00000000b +   0.00000000c (D)
       B-C:  -0.34550000 =  -9.00000000a +  -2.00000000b +   0.00000000c (E)

       D-E:  -2.51280000 = -32.00000000a +   0.00000000b +   0.00000000c (F)

From (F    ), a =   0.07852500 (G)
From (D,G  ), b =  -0.18061250 (H)
From (A,G,H), c = -41.63758750 (I)
0
जोड़ा

आपके प्रश्न के शब्द से, ऐसा लगता है कि आपके पास अज्ञात से अधिक समीकरण हैं और आप विसंगतियों को कम करना चाहते हैं। यह आम तौर पर रैखिक प्रतिगमन के साथ किया जाता है, जो विसंगतियों के वर्गों के योग को कम करता है। डेटा के आकार के आधार पर, आप इसे स्प्रेडशीट में या सांख्यिकीय पैकेज में कर सकते हैं। आर एक उच्च गुणवत्ता वाला, मुफ्त पैकेज है जो कई अन्य चीजों के बीच रैखिक प्रतिगमन करता है। रैखिक प्रतिगमन (और बहुत सारे गॉचा) के लिए बहुत कुछ है, लेकिन सरल मामलों के लिए यह सरल है। यहां आपके डेटा का उपयोग करके एक आर उदाहरण है। ध्यान दें कि "टीएक्स" आपके मॉडल में अवरोध है।

> y <- c(-44.394, -45.3049, -44.9594)
> a <- c(50.0, 43.0, 52.0)
> b <- c(37.0, 39.0, 41.0)
> regression = lm(y ~ a + b)
> regression

Call:
lm(formula = y ~ a + b)

Coefficients:
(Intercept)            a            b  
  -41.63759      0.07852     -0.18061  
0
जोड़ा

In terms of run-time efficiency, others have answered better than I. If you always will have the same number of equations as variables, I like Cramer's rule as it's easy to implement. Just write a function to calculate determinant of a matrix (or use one that's already written, I'm sure you can find one out there), and divide the determinants of two matrices.

0
जोड़ा

Cramer's Rule and Gaussian Elimination are two good, general-purpose algorithms (also see Simultaneous Linear Equations). If you're looking for code, check out GiNaC, Maxima, and SymbolicC++ (depending on your licensing requirements, of course).

संपादित करें: मुझे पता है कि आप सी भूमि में काम कर रहे हैं, लेकिन मुझे SymPy के लिए भी एक अच्छा शब्द डालना होगा (पायथन में एक कंप्यूटर बीजगणित प्रणाली)। आप इसके एल्गोरिदम से बहुत कुछ सीख सकते हैं (यदि आप थोड़ा पाइथन पढ़ सकते हैं)। इसके अलावा, यह नए बीएसडी लाइसेंस के तहत है, जबकि अधिकांश मुफ्त गणित पैकेज जीपीएल हैं।

0
जोड़ा
असल में, न तो क्रैमर का शासन और न ही गाऊशियन उन्मूलन वास्तविक दुनिया में बहुत अच्छा है। न तो अच्छे संख्यात्मक गुण हैं, और न ही गंभीर अनुप्रयोगों के लिए बहुत अधिक उपयोग किया जाता है। एलडीयू कारक बनाने का प्रयास करें। या बेहतर, एल्गोरिदम के बारे में चिंता न करें, और इसके बजाय LAPACK का उपयोग करें।
जोड़ा लेखक Peter, स्रोत
परिवर्तनीय कोड 4 से कम संख्या के लिए, क्रैमर नियम नियम कोड इमो लिखने के लिए सबसे अच्छा है
जोड़ा लेखक Ge Rong, स्रोत

Template Numerical Toolkit from NIST has tools for doing that.

क्यूआर अपघटन का उपयोग करने के लिए अधिक विश्वसनीय तरीकों में से एक है।

यहां एक रैपर का एक उदाहरण दिया गया है ताकि मैं अपने कोड में "GetInverse (A, InvA)" को कॉल कर सकूं और यह इनवर्स को इनवॉव में डाल देगा।

void GetInverse(const Array2D& A, Array2D& invA)
   {
   QR qr(A);  
   invA = qr.solve(I); 
   }

पुस्तकालय में Array2D परिभाषित किया गया है।

0
जोड़ा
q <.s code> qr.solve (I) में I क्या है?
जोड़ा लेखक Ponkadoodle, स्रोत

माइक्रोसॉफ्ट सॉल्वर फाउंडेशन पर एक नज़र डालें।

इसके साथ आप इस तरह कोड लिख सकते हैं:

  SolverContext context = SolverContext.GetContext();
  Model model = context.CreateModel();

  Decision a = new Decision(Domain.Real, "a");
  Decision b = new Decision(Domain.Real, "b");
  Decision c = new Decision(Domain.Real, "c");
  model.AddDecisions(a,b,c);
  model.AddConstraint("eqA", -44.3940 == 50*a + 37*b + c);
  model.AddConstraint("eqB", -45.3049 == 43*a + 39*b + c);
  model.AddConstraint("eqC", -44.9594 == 52*a + 41*b + c);
  Solution solution = context.Solve();
  string results = solution.GetReport().ToString();
  Console.WriteLine(results); 

Here is the output:
===Solver Foundation Service Report===
Datetime: 04/20/2009 23:29:55
Model Name: Default
Capabilities requested: LP
Solve Time (ms): 1027
Total Time (ms): 1414
Solve Completion Status: Optimal
Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver
Directives:
Microsoft.SolverFoundation.Services.Directive
Algorithm: Primal
Arithmetic: Hybrid
Pricing (exact): Default
Pricing (double): SteepestEdge
Basis: Slack
Pivot Count: 3
===Solution Details===
Goals:

Decisions:
a: 0.0785250000000004
b: -0.180612500000001
c: -41.6375875

0
जोड़ा
तो, हम इससे क्या संख्यात्मक स्थिरता गुणों की उम्मीद कर सकते हैं? चूंकि यह खुला स्रोत नहीं है, इसलिए यह उचित परिश्रम के साथ आना चाहिए, एलएपीएक्स जैसे मुख्यधारा के पुस्तकालयों के खिलाफ बेंचमार्क, मालिकाना समाधान के साथ जाने के लिए कुछ महत्वपूर्ण लाभ होना चाहिए।
जोड़ा लेखक Evgeni Sergeev, स्रोत
function x = LinSolve(A,y)
%
% Recursive Solution of Linear System Ax=y
% matlab equivalent: x = A\y 
% x = n x 1
% A = n x n
% y = n x 1
% Uses stack space extensively. Not efficient.
% C allows recursion, so convert it into C. 
% ----------------------------------------------
n=length(y);
x=zeros(n,1);
if(n>1)
    x(1:n-1,1) = LinSolve( A(1:n-1,1:n-1) - (A(1:n-1,n)*A(n,1:n-1))./A(n,n) , ...
                           y(1:n-1,1) - A(1:n-1,n).*(y(n,1)/A(n,n))); 
    x(n,1) = (y(n,1) - A(n,1:n-1)*x(1:n-1,1))./A(n,n); 
else
    x = y(1,1) / A(1,1);
end
0
जोड़ा
तो क्या होगा यदि ए (एन, एन) शून्य है?
जोड़ा लेखक Evgeni Sergeev, स्रोत