Метод Гауса — Жордана

Метод Гауса — Жордана використовується для розв'язання систем лінійних алгебраїчних рівнянь, знаходження оберненої матриці, знаходження координат вектора у заданому базисі, відшукання рангу матриці. Метод є модифікацією методу Гауса. Названий на честь Гауса та німецького математика та геодезиста Вільгельма Йордана.

Алгоритм

1. Обирається перша зліва колонка, що містить хоч одне ненульове значення.
2. Якщо верхнє число у цій колонці - нуль, то обмінюється увесь перший рядок матриці з іншим рядком матриці, де у цій колонці нема нуля.
3. Усі елементи першого рядка діляться на верхній елемент обраної колонки.
4. Від рядків, що залишились, віднімається перший рядок, помножений на перший елемент відповідного рядка, з метою отримання у якості першого елемента кожного рядка (крім першого) нуля.
5. Далі, повторюємо ці операції із матрицею, отриманою з початкової матриці після викреслювання першого рядка та першого стовпчика.
6. Після повторення операцій n-1 разів отримаємо верхню трикутну матрицю.
7. Віднімаємо від передостаннього рядка останній рядок, помножений на відповідний коефіцієнт, щоб у передостанньому рядку залишилась лише 1 на головній діагоналі.
8. Повторюємо попередній крок для наступних рядків. У результаті отримуємо одиничну матрицю і рішення на місці вільного вектора (над ним необхідно виконувати ті самі перетворення).

Приклад

Розв'яжемо систему рівнянь:

$\left\{\begin{array}{ccccccl} a &+& b &+& c &=& 0\\ 4a &+& 2b &+& c &=& 1\\ 9a &+& 3b &+& c &=& 3 \end{array}\right.$

Запишемо її у вигляді матриці 3×4, де останній стовпчик є вільним членом:

$\begin{pmatrix} 1 & 1 & 1 & | & 0 \\ 4 & 2 & 1 & | & 1 \\ 9 & 3 & 1 & | & 3 \end{pmatrix}$

Виконаємо такі дії:

• До рядка 2 додамо: -4 * рядок 1.
• До рядка 3 додамо: -9 * рядок 1.

Отримаємо:

$\begin{pmatrix} 1 &\ 1 &\ 1 & | & 0 \\ 0 & -2 & -3 & | & 1 \\ 0 & -6 & -8 & | & 3 \end{pmatrix}$

• До рядка 3 додамо: -3 * рядок 2.
• Рядок 2 ділимо на -2

$\begin{pmatrix} 1 & 1 & 1 & | &\ 0 \\ 0 & 1 & {3 \over 2} & | & -{1 \over 2} \\ 0 & 0 & 1 & | &\ 0 \end{pmatrix}$

• До рядка 1 додамо: -1 * рядок 3.
• До рядка 2 додамо: -3/2 * рядок 3.

$\begin{pmatrix} 1 & 1 & 0 & | &\ 0 \\ 0 & 1 & 0 & | & -{1 \over 2} \\ 0 & 0 & 1 & | &\ 0 \end{pmatrix}$

• До рядка 1 додамо: -1 * рядок 2.

$\begin{pmatrix} 1 & 0 & 0 & | &\ {1 \over 2} \\ 0 & 1 & 0 & | & -{1 \over 2} \\ 0 & 0 & 1 & | &\ 0 \end{pmatrix}$

У правому стовпчику отримаємо рішення:

$a = \frac{1}{2} \; ; \ b = -\frac{1}{2} \; ; \ c = 0$ .

Приклад програми на Java (J2SE 1.5)

/**    
 * Клас, що розв'язує системи рівнянь методом Ґаусса-Жордана    
 *     
 * @author Лісніченко Дмитро aka Dmitrius, ІО-61, ФІОТ, КПІ - Київський     Політехнічний Інститут
 * Поширюється під ліцензією GNU General Public License    
 */    
public class EquationsSet {    
    /**    
     * Коефіцієнти рівнняння. Вкладеність: Рядок - колонка. Останній елемент    
     * кожного рядка - вільний член.    
     */    
    public double[][] Coefficients; // Рядок - колонка    
 
    /**    
     * Розв'язує систему рівнянь методом Гауса-Жордана.    
     *     
     * @return вектор із рішеннями.    
     */    
    public double[] Solve() {    
        // Фактично є проксі-методом, що переадресовує запит до рекурсивної ф-ї    
        // розв'язання системи, а потім повертає результат. Так зроблено для    
        // зручності введення рекурсії    
        this.Simplify();    
        this.MakeNullsInUpperLines();    
        double[][] t = Coefficients;    
        double[] Result = new double[t.length];    
        // У результат переписую вільні члени після розв'язання    
        for (int i = 0; i < Result.length; i++) {    
            Result[i] = t[i][t[i].length - 1];    
        }    
        return Result;    
    }    
 
    /**    
     * Виводить на екран коефіцієнти системи    
     */    
    public void print() {    
        for (int i = 0; i < Coefficients.length; i++) {    
            for (int j = 0; j < Coefficients.length; j++) {    
                System.out.printf("%-7f ", Coefficients[i][j]);    
            }    
            System.out.println(" = "    
                    + Coefficients[i][Coefficients[i].length - 1]);    
        }    
 
    }    
 
    public static void main(String[] args) {    
        EquationsSet S = new EquationsSet();    
        {    
            double[][] t = {{1.43, 0.87, -1.57, -0.58, 2.3},     
                            {0.63, -0.57, -2.34, 0.66, 0.77},     
                            {1.57, 0.66, -0.57, 1.15, -0.2},    
                            {0.88, -0.67, 0.55, -0.45, 0.56}};    
            S.Coefficients = t;    
        }    
        S.print();    
        System.out.println();    
        double[] t = S.Solve();    
        System.out.println("Solution:");    
        for (double e : t) {    
            System.out.println(e);    
        }    
    }    
 
    /**    
     * Спрощує та розв'язує систему. Використовується рекурсія    
     *     
     * @return двовимірний масив коефіцієнтів розв'язаної системи    
     */    
    private double[][] Simplify() {    
        int[] notNull = FindFirstNotNull();    
        Make1LineNotStartingWithNull(notNull[0], notNull[1]);    
        // Всі елементи 1 рядка діляться на 1 елемент обраної колонки    
        DivideOn(0, Coefficients[notNull[0]][notNull[1]]);    
        // Отримання нулів у першій колонці    
        MakeNulls();    
        EquationsSet es = new EquationsSet();    
        es.Coefficients = GetTruncatedArray();    
        if (es.Coefficients.length > 1) { // Роблю так доки не залишається    
            // жодного рівняння.    
            // Рекурсивний виклик самої себе для обробки масиву    
            // коефіцієнтів розміром n-1    
            es.Simplify();    
        } else {    
            es.Coefficients[0][1] /= es.Coefficients[0][0];    
            es.Coefficients[0][0] = 1;    
        }    
        this.RIP(es);    
        return this.Coefficients;    
    }    
 
    /**    
     * Обирає першу зліва колонку, де є ненульове значення    
     *     
     * @return координати цього числа (рядок-колонка)    
     */    
    private int[] FindFirstNotNull() {    
        int[] Result = new int[2];    
        Result[0] = 0;    
        Result[1] = 0;    
        find_column: for (Result[0] = 0; Result[0] < Coefficients.length; Result[0]++) {    
            for (Result[1] = 0; Result[1] < Coefficients.length - 1; Result[1]++) {    
                if ((Coefficients[Result[1]][Result[0]]) != 0)    
                    break find_column;    
            }    
        }    
        return Result;    
    }    
 
    /**    
     * Якщо перше число у 1 рядку 0, то міняю її місцями з тим, у якого перше    
     * число не нуль    
     *     
     * @param i    
     *            Номер рядка з ненульовим елементом    
     * @param h    
     *            Номер стовпчика    
     */    
    private void Make1LineNotStartingWithNull(int i, int h) {    
        if (Coefficients[0][0] == 0) {    
            // Знаходжу рядок, що не починається з нуля    
            int j;    
            for (j = 1; j < Coefficients.length; j++) {    
                if ((Coefficients[j][0]) != 0)    
                    break;    
                else if (j == Coefficients.length - 1) {    
                    // Немає ненульових коефіцієнтів у першій колонці    
                    // Метод не спрацює    
                    System.out    
                            .println("Помилка: У першій колонці нема ненульових елементів...");    
                    System.out.println("Коректна робота не гарантується");    
                    // System.exit(-1); //Можна б і завершити програму    
                }    
            }    
            double[] t = new double[Coefficients[0].length];    
            // Запам'ятовую старі коефіцієнти першого рівняння    
            t = Coefficients[0];    
            Coefficients[0] = Coefficients[j];    
            Coefficients[j] = t;    
        }    
    }    
 
    /**    
     *     
     * Ділить рядок з вказаним номером на вказане число    
     *     
     * @param lineNumber    
     *            Який рядок поділити    
     * @param p    
     *            На що поділити    
     */    
    private void DivideOn(int lineNumber, double p) {    
        for (int j = 0; j < Coefficients[0].length; j++) {    
            Coefficients[lineNumber][j] /= p;    
        }    
    }    
 
    /**    
     * Віднімаю від інших рівнянь перше рівняння, помножене на їх перші    
     * коефіцієнти    
     */    
    private void MakeNulls() {    
        for (int k = 1; k < Coefficients.length; k++) { // Для кожного рівн.,    
            // поч з ІІ    
            double t = Coefficients[k][0]; // Перший елемент кожного рівняння    
            for (int l = 0; l < Coefficients[0].length; l++) {// Для кожного    
                // коефіцієнта    
                // рівняння    
                Coefficients[k][l] -= Coefficients[0][l] * t;    
            }    
        }    
    }    
 
    /**    
     * Обрізає масив коефіцієнтів    
     *     
     * @return масив коефіцієнтів із вирізаними першими рядком та стовпчиком    
     */    
    private double[][] GetTruncatedArray() {    
        double[][] result = new double[Coefficients.length - 1][Coefficients[0].length - 1];    
        for (int k = 1; k < Coefficients.length; k++) {    
            for (int l = 1; l < Coefficients[0].length; l++) {    
                result[k - 1][l - 1] = Coefficients[k][l];    
            }    
        }    
        return result;    
    }    
 
    /**    
     * Витягує у масив коефіцієнтів викликаючого екземпляра дані з масиву    
     * екземпляра-параметра. Мається на увазі поміщення коефіцієнтів параметра у    
     * нижній прямокутник nx(n-1)масиву викликаючого екземпляра    
     *     
     * @param o    
     *            екземляр з даними    
     */    
    private void RIP(EquationsSet o) {    
        for (int i = 0; i < o.Coefficients.length; i++) {    
            for (int j = 0; j < o.Coefficients[i].length; j++) {    
                // Рядок із врахуванням зміщення у коефіцієнтах викл.    
                // екземплярів    
                int line = this.Coefficients.length - 1 - i;    
                // Колонка із врахуванням зміщення у коефіцієнтах    
                // викл.екземплярів    
                int column = this.Coefficients[line].length - 1 - j;    
                // Номер рядка у коеф. параметра    
                int parLine = o.Coefficients.length - i - 1;    
                // Номер колонки у коеф. параметра    
                int parCol = o.Coefficients[parLine].length - j - 1;    
                // Переписую коефіцієнти із зміщенням    
                this.Coefficients[line][column] = o.Coefficients[parLine][parCol];    
 
            }    
        }    
    }    
 
    /**    
     * Віднімає з верхніх рядків останні, помножені на відповідні коефіцієнти, з    
     * метою отримати нулі всюди, крім головної діагоналі та вільних членів.    
     */    
    private void MakeNullsInUpperLines() {    
        int j = 0;    
        for (int i = Coefficients.length - 1; i >= 0; i--) { // Номер    
            // активного    
            // рівняння    
            for (j = i - 1; j >= 0; j--) { // Номер рівняння, яке    
                // перетворюється    
                // Номер останнього коефіцієнта (вільного члена) у рядку    
                int t = Coefficients[i].length - 1;    
                // Проводжу операцію над вільним членом    
                Coefficients[j][t] -= Coefficients[j][i] * Coefficients[i][t];    
                // Коефіцієнт над одиницею перетворюється в нуль    
                Coefficients[j][i] = 0;    
            }    
        }    
    }    
}

Джерела

• Гельфанд И.М. (1971). Лекции по линейной алгебре (вид. четверте). Москва: Наука. с. 271. ISBN 5791300158. 
• Мальцев А. И. (1970). Основы линейной алгебры (вид. третє). Новосибірськ: Наука. с. 400. 

Посилання

• Lipschutz, Seymour, and Lipson, Mark. "Schaum's Outlines: Linear Algebra". Tata McGraw-hill edition. Delhi 2001. pp. 69-80.
• Algorithm for Gauss-Jordan elimination in Matlab
• Algorithm for Gauss-Jordan elimination in Python