Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

obrazek

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Równania

Metoda Cramera

SPIS TREŚCI
Podrozdziały

Definicje

W poprzednim rozdziale rozwiązaliśmy układ dwóch równań liniowych:

Wyprowadziliśmy wzór na zmienną x:

Wyprowadźmy analogiczny wzór na zmienną y:

Ostatecznie:

Przyjrzyj się tym wzorom. W obu wzorach mianowniki ułamków są tym samym wyrażeniem. Różne są liczniki. Jeśli potraktujemy liczniki i mianowniki tych ułamków jako wyznaczniki macierzy drugiego stopnia, to:

Zapiszmy nasz układ równań zapiszemy w postaci macierzowej:

Macierz A  jest macierzą współczynników stojących przy niewiadomych:

Macierz Ax powstaje z macierzy A, gdy kolumnę współczynników zmiennej x zastąpimy macierzą wyrazów wolnych B:

Macierz Ay powstaje z macierzy A,  gdy kolumnę współczynników zmiennej y zastąpimy macierzą wyrazów wolnych B:

Układ posiada rozwiązanie, jeśli wyznacznik macierzy A jest różny od 0. Wykorzystując wyznaczniki, możemy teraz zapisać:

Na początek:  podrozdziału   strony 

Wzory Cramera

Wzory, które otrzymaliśmy w poprzednim podrozdziale, nie są przypadkowe. Matematyk szwajcarski Gabriel Cramer pokazał, iż za pomocą wyznaczników można rozwiązywać układy równań liniowych. Są to tak zwane wzory Cramera (ang. Cramer's rule).

Mamy układ n równań z n niewiadomymi:

Zapiszmy ten układ równań w postaci macierzowej:

Macierz kwadratowa A  stopnia n jest macierzą współczynników a, które stoją przy niewiadomych x.

Wektor X  jest macierzą niewiadomych x.

Wektor B  jest macierzą współczynników wolnych b.

Oznaczmy przez Xi macierz, która powstaje z macierzy A  przez zastąpienie wyrazów w kolumnie i-tej wyrazami wektora B:

Wartości zmiennych układu równań obliczamy ze wzorów Cramera:

Układ posiada rozwiązanie, jeśli wyznacznik macierzy współczynników A  jest różny od zera. Jeśli wyznacznik macierzy A  jest równy zero, to układ równań jest albo sprzeczny (nie posiada rozwiązań), albo nieoznaczony (posiada więcej niż jedno rozwiązanie).

Dla n niewiadomych x metoda Cramera wymaga policzenia n + 1 wyznaczników stopnia n. Powoduje to, iż ma ona klasę złożoności obliczeniowej równą O(n4), jeśli wyznaczniki są liczone za pomocą rozkładu LU. Istnieją lepsze metody rozwiązywania układów równań liniowych.

Przykład:

Rozwiązać układ równań:

Układ zapisujemy macierzowo:

Obliczamy wyznacznik macierzy współczynników A. Wykorzystujemy schemat Saurrusa:

Obliczamy wyznacznik macierzy X1:

Obliczamy wyznacznik macierzy X2:

Obliczamy wyznacznik macierzy X3:

Obliczamy niewiadome:

Sprawdzamy, czy wyliczone wartości niewiadomych spełniają równania:

Poniższy program rozwiązuje za pomocą wzorów Cramera układ równań liniowych. Program zawiera funkcję obliczającą wyznacznik macierzy, która wykorzystuje rozkład LU z piwotowaniem. Dane wejściowe do programu wyglądają następująco:

Pierwsza liczba n określa ilość równań w układzie. Następne n × n liczb definiują współczynniki a przy niewiadomych. Ostatnie n liczb definiują wyrazy wolne b.

Układ równań:

Dane wejściowe:

5
-1 2 -3 3 5
8 0 7 4 -1
-3 4 -3 2 -2
8 -3 -2 1 2
-2 -1 -6 9 0
56 62 -10 14 28
Przykładowy program w języku C++
// Wzory Cramera
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//---------------------------

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

const double EPS = 0.000000001;

// Funkcja oblicza wartość wyznacznika macierzy
// metodą rozkładu LU z piwotowaniem
// n - stopień macierzy
// A - wskaźnik macierzy
//---------------------------------------------

double det(int n, double ** A)
{
    int i, j, k, * W, md, maxw;
    double sum, akk, maxe;

    // Mnożnik korekcyjny dla wyznacznika
    md = 1;

    // Tworzymy wektor wierszowy
    W = new int [n];

    // Inicjujemy wektor wierszowy numerami wierszy
    for(i = 0; i < n; i++) W[i] = i;

    // Rozkład LU
    for(k = 0; k < n; k++)
    {
        maxw = k; // numer wiersza z elementem max
        maxe = fabs(A[W[k]][k]);

        // Szukamy elementu max
        for(i = k + 1; i < n; i++)
            if(fabs(A[W[i]][k]) > maxe)
            {
                maxw = i;
                maxe = fabs(A[W[i]][k]);
            }
        // Jeśli max jest zero, to macierz jest zdegenerowana
        if(maxe <= EPS) return 0;

        // Jeśli max nie leży na przekątnej, zamieniamy wiersze
        if(maxw != k)
        {
            md = -md; // Modyfikujemy mnożnik
            swap(W[k], W[maxw]);
        }

        // Dzielnik
        akk = A[W[k]][k];

        // Normalizujemy kolumnę
        for(i = k + 1; i < n; i++)
            A[W[i]][k] = A[W[i]][k] / akk;

        // Modyfikujemy podmacierz
        for(i = k + 1; i < n; i++)
            for(j = k + 1; j < n; j++)
                A[W[i]][j] = A[W[i]][j] - A[W[i]][k] *  A[W[k]][j];
    }

    // Obliczamy wyznacznik;
    sum = md * A[W[0]][0];
    for(k = 1; k < n; k++) sum *= A[W[k]][k];
    delete [] W;
    return sum;
}

// Program główny
//---------------

int main()
{
    setlocale(LC_ALL,"");

    cout << setprecision(5) << fixed;

    cout << "Rozwiązywanie układu równań liniowych wzorami Cramera" << endl
         << "-----------------------------------------------------" << endl << endl
         << "Wpisz dane wejściowe:" << endl << endl;

    int i,j,k; // Indeksy
    int n;     // Liczba równań w układzie

    cin >> n;

    // Tworzymy dynamicznie potrzebne macierze

    double ** A ;  // Macierz współczynników przy niewiadomych x
    double ** Xi ; // Macierz pomocnicza

    A = new double * [n];
    Xi = new double * [n];

    for(i = 0; i < n; i++)
    {
        A[i] = new double[n];
        Xi[i] = new double[n];
    }

    // Odczytujemy współczynniki

    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
        {
            cin >> A[i][j];
            Xi[i][j] = A[i][j];
        }

    double * B; // Macierz wyrazów wolnych

    B = new double[n];

    // Odczytujemy wyrazy wolne

    for(i = 0; i < n; i++) cin >> B[i];

    cout << endl;

    // Rozpoczynamy od obliczenia wyznacznika macierzy A

    double detA = det(n,Xi);

    if(fabs(detA) < EPS) cout << "Układ równań nie ma rozwiązania" << endl;
    else
    {
        // Tworzymy macierz rozwiąń

        double * X = new double[n];

        // Rozpoczynamy wyliczanie niewiadomych

        for(k = 0; k < n; k++)
        {
            // Ustawiamy macierz pomocniczą Xi

            for(i = 0; i < n; i++)
                for(j = 0; j < n; j++)
                    if(j == k) Xi[i][j] = B[i];
                    else       Xi[i][j] = A[i][j];

            // Obliczamy niewiadomą:

            X[k] = det(n,Xi) / detA;
        }

        // Wyświetlamy wyniki:

        for(i = 0; i < n; i++)
            cout << "x" << i << " = " << setw(12) << X[i] << endl;

        // Usuwamy tablicę dynamiczną:

        delete [] X;
    }

    cout << endl;

    for(i = 0; i < n; i++)
    {
        delete [] A[i];
        delete [] Xi[i];
    }
    delete [] A;
    delete [] Xi;
    delete [] B;
    return 0;
}
Wynik
Rozwiązywanie układu równań liniowych wzorami Cramera
-----------------------------------------------------

Wpisz dane wejściowe:

5
-1 2 -3 3 5
8 0 7 4 -1
-3 4 -3 2 -2
8 -3 -2 1 2
-2 -1 -6 9 0
56 62 -10 14 28

x0 =    1.00000
x1 =    3.00000
x2 =    5.00000
x3 =    7.00000
x4 =    9.00000
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.