Λύνοντας μια γραμμική εξίσωση

ψήφοι
35

Πρέπει να λύσει προγραμματισμού ένα σύστημα γραμμικών εξισώσεων σε C, του στόχου C, ή (εάν είναι απαραίτητο) C ++.

Εδώ είναι ένα παράδειγμα των εξισώσεων:

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

Δημοσιεύθηκε 03/08/2008 στις 19:14
πηγή χρήστη
Σε άλλες γλώσσες...                            


10 απαντήσεις

ψήφοι
17

Κανόνας του Cramer και απαλοιφή Gauss είναι δύο αλγόριθμοι καλή, γενικής χρήσης (βλέπε επίσης ταυτόχρονη γραμμικών εξισώσεων ). Αν ψάχνετε για κωδικό, ελέγξτε GiNaC , Maxima , και SymbolicC ++ (ανάλογα με τις απαιτήσεις της άδειάς σας, φυσικά).

EDIT: Ξέρω ότι εργάζεστε σε C γη, αλλά πρέπει επίσης να θέσει σε μια καλή κουβέντα για SymPy (ένα σύστημα άλγεβρας υπολογιστών στην Python). Μπορείτε να μάθετε πολλά από αλγόριθμους του (αν μπορείτε να διαβάσετε ένα κομμάτι της python). Επίσης, είναι στο πλαίσιο της νέας άδειας BSD, ενώ τα περισσότερα από τα δωρεάν πακέτα μαθηματικά είναι GPL.

Απαντήθηκε 03/08/2008 στις 19:37
πηγή χρήστη

ψήφοι
15

Μπορείτε να λύσετε αυτό με ένα πρόγραμμα ακριβώς με τον ίδιο τρόπο μπορείτε να το λύσει με το χέρι (με τον πολλαπλασιασμό και την αφαίρεση, στη συνέχεια τροφοδοτεί τα αποτελέσματα πίσω στις εξισώσεις). Αυτό είναι αρκετά πρότυπο μαθηματικών στη δευτεροβάθμια εκπαίδευση επιπέδου.

-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 το οποίο είναι «a = n», όπου το η είναι ένας πραγματικός αριθμός. Μόλις έχετε ότι, μπορείτε να τροφοδοτήσει την επόμενη μήτρα μέχρι να πάρετε μια άλλη αξία, τότε αυτές τις δύο τιμές στον επόμενο πίνακα μέχρι να έχετε έλυσε όλες τις μεταβλητές.

Εφόσον έχετε Ν διακριτές εξισώσεις, μπορείτε πάντα να λύσει για Ν μεταβλητές. Το λέω ξεχωριστό, γιατί αυτά τα δύο δεν είναι οι εξής:

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

Είναι η ίδια εξίσωση πολλαπλασιάζεται επί δύο, έτσι δεν μπορείτε να πάρετε μια λύση από αυτούς - πολλαπλασιάζοντας το πρώτο από τα δύο τότε αφαιρώντας σας φύλλα με την αλήθεια, αλλά άχρηστο δήλωση:

0 = 0 + 0

Ως παράδειγμα, εδώ είναι μερικά κώδικα C που λειτουργεί από τις ταυτόχρονες εξισώσεις που έχετε τοποθετηθεί στην ερώτησή σας. Πρώτη κάποια απαραίτητα είδη, μεταβλητές, μια λειτουργία υποστήριξης για την εκτύπωση από μια εξίσωση, και η έναρξη της main:

#include <stdio.h>

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 ("");

Τώρα που έχουμε μια φόρμουλα του τύπου number1 = unknown * number2, μπορούμε απλά να επεξεργαστούμε την άγνωστη τιμή με unknown <- number1 / number2. Στη συνέχεια, αφού έχετε καταλάβει ότι η αξία έξω, να υποκαταστήσει σε μία από τις εξισώσεις με δύο αγνώστους, και υπολογισμός του δεύτερου αξία. Στη συνέχεια αντικαταστήσει τις δύο αυτές (τώρα γνωστό) άγνωστοι σε μία από τις αρχικές εξισώσεις και έχετε τώρα τις τιμές για τις τρεις αγνώστους:

    // 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)
Απαντήθηκε 26/02/2009 στις 11:59
πηγή χρήστη

ψήφοι
7

Για ένα σύστημα 3x3 γραμμικών εξισώσεων υποθέτω ότι θα είναι εντάξει για να αναπτύξουν το δικό σας αλγορίθμους.

Ωστόσο, ίσως χρειαστεί να ανησυχείτε για την ακρίβεια, η διαίρεση με το μηδέν ή πολύ μικρούς αριθμούς και τι θα κάνουμε με απείρως πολλές λύσεις. Η πρότασή μου είναι να πάει με μια τυπική αριθμητική γραμμική άλγεβρα πακέτο, όπως LAPACK .

Απαντήθηκε 08/08/2008 στις 18:59
πηγή χρήστη

ψήφοι
6

Ρίξτε μια ματιά στο Solver Ίδρυμα της Microsoft .

Με αυτό μπορείτε να γράψετε κώδικα όπως αυτό:

  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); 

Εδώ είναι η έξοδος:
=== Επίλυση Ίδρυμα Υπηρεσία Έκθεση ===
ημέρας-ώρας: 04/20/2009 23:29:55
Όνομα μοντέλου: Προεπιλογή
Δυνατότητες ζήτησε: LP
Λύστε Χρόνος (ms): 1027
Σύνολο χρόνου (ms): 1414
Λύστε ολοκλήρωση Κατάσταση: Βέλτιστη
Επίλυση Επιλεγμένα: Microsoft.SolverFoundation.Solvers.SimplexSolver
οδηγίες:
Microsoft.SolverFoundation.Services.Directive
Αλγόριθμος: Primal
Αριθμητική: Υβριδικό
Τιμή (ακριβής): Προεπιλογή
Τιμολόγηση (διπλό): SteepestEdge
Βάση: Slack
άξονα Count: 3
== = Λύση Λεπτομέρειες ===
Στόχοι:

αποφάσεις:
α: 0.0785250000000004
β: -0,180612500000001
c: -41.6375875

Απαντήθηκε 21/04/2009 στις 04:33
πηγή χρήστη

ψήφοι
3

Πρότυπο Αριθμητική Toolkit από το NIST έχει τα εργαλεία για να το κάνουμε αυτό.

Ένας από τους πιο αξιόπιστους τρόπους είναι να χρησιμοποιήσετε ένα QR αποσύνθεση .

Εδώ είναι ένα παράδειγμα μιας περιτύλιγμα ώστε να μπορώ να αποκαλώ «GetInverse (Α, ΙηνΑ)» με κωδικό μου και θα θέσει το αντίστροφο σε ΙηνΑ.

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

Array2D ορίζεται στη βιβλιοθήκη.

Απαντήθηκε 25/08/2008 στις 19:53
πηγή χρήστη

ψήφοι
3

Ψάχνετε για ένα πακέτο λογισμικού που θα κάνει τη δουλειά ή πραγματικά να κάνει τις λειτουργίες μήτρα και, όπως και να το κάνουμε κάθε βήμα;

Η πρώτη, μια συνάδελφος μου χρησιμοποιηθεί μόνο OCaml GLPK . Είναι απλά ένα περιτύλιγμα για την GLPK , αλλά αφαιρεί πολλά από τα βήματα της δημιουργίας πράγματα. Φαίνεται σαν να πρόκειται να πρέπει να κολλήσει με την GLPK, σε C, όμως. Για την τελευταία, χάρη στο υπέροχο για την εξοικονόμηση ένα παλιό άρθρο που χρησιμοποιείται για να μάθω LP λίγο πίσω, PDF . Αν χρειάζεστε ειδική βοήθεια για τη δημιουργία περαιτέρω, ενημερώστε μας και είμαι σίγουρος, μου ή κάποιος θα περιπλανηθείτε πίσω και να βοηθήσει, αλλά νομίζω ότι είναι αρκετά απλό από εδώ. Καλή τύχη!

Απαντήθηκε 03/08/2008 στις 19:27
πηγή χρήστη

ψήφοι
2

Από την άποψη της αποτελεσματικότητας χρόνου εκτέλεσης, άλλοι έχουν απαντηθεί καλύτερα από εμένα Εάν πάντα θα έχουν τον ίδιο αριθμό εξισώσεων και μεταβλητών, μου αρέσει κανόνα του Cramer , όπως είναι εύκολο να εφαρμοστούν. Απλά γράψετε μια συνάρτηση για τον υπολογισμό ορίζουσα ενός πίνακα (ή χρησιμοποιήστε ένα που έχει ήδη γράψει, είμαι βέβαιος ότι μπορείτε να βρείτε ένα από εκεί), και χωρίζουν τους καθοριστικούς παράγοντες των δύο πινάκων.

Απαντήθηκε 19/09/2008 στις 04:36
πηγή χρήστη

ψήφοι
2

Από τη διατύπωση της ερώτησής σας, θα φαίνεται σαν να έχετε περισσότερες εξισώσεις από αγνώστους και θέλετε να ελαχιστοποιήσετε τις ασυνέπειες. Αυτό γίνεται τυπικά με γραμμική παλινδρόμηση, η οποία ελαχιστοποιεί το άθροισμα των τετραγώνων των ασυνέπειες. Ανάλογα με το μέγεθος των δεδομένων, μπορείτε να το κάνετε αυτό σε ένα υπολογιστικό φύλλο ή σε ένα στατιστικό πακέτο. R είναι ένα υψηλής ποιότητας, δωρεάν πακέτο που κάνει γραμμική παλινδρόμηση, ανάμεσα σε πολλά άλλα πράγματα. Υπάρχουν πολλά να γραμμική παλινδρόμηση (και πολλά πέτυχα), αλλά είναι εύκολο να κάνει για απλές περιπτώσεις. Εδώ είναι ένα παράδειγμα R χρησιμοποιώντας τα δεδομένα σας. Σημειώστε ότι η «TX» είναι το σημείο τομής με το μοντέλο σας.

> 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  
Απαντήθηκε 17/09/2008 στις 15:22
πηγή χρήστη

ψήφοι
1
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
Απαντήθηκε 30/12/2014 στις 15:24
πηγή χρήστη

ψήφοι
1

Προσωπικά, είμαι εν μέρει με τους αλγόριθμους της Αριθμητική Συνταγές . (Είμαι λάτρης της ++ έκδοση C).

Το βιβλίο αυτό θα σας διδάξει γιατί λειτουργούν οι αλγόριθμοι, καθώς και να σας δείξω κάποια πολύ-πολύ λάθη εφαρμογές αυτών των αλγορίθμων.

Φυσικά, θα μπορούσατε απλά τυφλά χρησιμοποιούν CLAPACK (έχω χρησιμοποιήσει με μεγάλη επιτυχία), αλλά θα ήθελα να από πρώτο χέρι, πληκτρολογήστε έναν αλγόριθμο απαλοιφή Gauss να έχουν τουλάχιστον μια αμυδρή ιδέα για το είδος της εργασίας που έχει πάει στην παραγωγή αυτών των αλγορίθμων σταθερός.

Αργότερα, αν κάνετε πιο ενδιαφέρουσα γραμμική άλγεβρα, κοιτάζοντας γύρω από τον πηγαίο κώδικα του Octave θα απαντήσει σε πολλές ερωτήσεις.

Απαντήθηκε 25/08/2008 στις 19:22
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more