...................................................."Даром дадено, даром давайте", - Исус Христос.
В предыдущей статье [1] был описан простейший способ решения систем линейных алгебраических уравнений (СЛАУ) методом Гаусса с приведением матрицы коэффициентов к традиционному правому верхнему (Right-Upper) треугольному виду (частному случаю ступенчатого вида), взятый из справочника Дьяконова [2]. Метод Гаусса требует O(n^3) арифметических операций [3].
Недостатками традиционного способа являются:
1. СЛАУ, в которых при приведении матрицы к треугольному виду (A'|b'), некоторые элементы в СЛАУ обнуляются и при вычислении очередного коэффициента A[I,J] происходит деление на 0, без обмена строк местами, не решаются традиционным методом Гаусса (Right-Upper), но решаются разновидностью метода Гаусса Left-Lower, и наоборот, поэтому метод Гаусса Left-Lower является полезным дополнением традиционного метода Гаусса (Right-Upper) и наоборот.
Пример 1, СЛАУ:
без обмена строк местами, не решается методом Left-Lower и Left-Upper, но решается методом Right-Upper и Right-Lower. Это не значит, что метод или СЛАУ плохие, а является недостатком алгоритма программы, а не самого метода. (Метод -> алгоритм программы -> программа. Методов не очень много, алгоритмов программ одного и того же метода больше, а вариантов (вариаций) самих программ одного и того же алгоритма ещё больше.) При обмене местами третьей и первой строк матрицы эта СЛАУ решается и методом Left-Lower.
Пример 2, в СЛАУ:
так как A[2,2] и A[2,3] равны, то при обнулении третьей колонки, во второй строке, обнуляется элемент матрицы на побочной диагонали A[2,2] и, без перестановки строк, СЛАУ методом Left-Upper не решается, но решается методом Right-Upper или обменом местами второй и третьей (последней) строки.
Пример 3, СЛАУ:
из-за элемента A[1,1]=0 на главной диагонали, без обмена строк, не решается традиционным методом Right-Upper. Для обмена строк требуется:
(считать первый элемент первой строки в буфер обмена + записать первый элемент второй строки в первую ячейку первой строки + записать элемент из буфера обмена в первую ячейку второй строки) и всё это умножить на N+1, на что требуется относительно большое время.
Но на равенство нулю элемент A[1,1] можно проверить одним оператором IF, на что требуется не очень большое время, и, если равен нулю, то перейти к методу Left-Lower или Left-Upper или, на худой конец, к Right-Lower, в которых A[1,1]=0 не является помехой для решения СЛАУ.
Также могут оказаться полезными дополнениями и две другие разновидности метода Гаусса с побочными диагоналями: Left-Upper и Right-Lower (программы 4-1LU.BAS и 4-1RL.BAS). При этом, множество СЛАУ, решаемых методом Гаусса, расширяется.
Но есть и другой способ увеличения быстродействия (ускорения вычислений): обозначить номера строк, а в худшем случае и столбцов, матрицы (массива) переменными и вместо действительного обмена строк или столбцов менять только номера строк или столбцов в переменных.
Определитель исходной матрицы A в способах Right-Upper и Left-Lower вычисляется по главной диагонали приведённой к треугольному виду матрицы A', а в способах Left-Upper и Right-Lower по побочной диагонали (side diagonal) приведённой к треугольному виду матрицы A', и, в общем случае, они разные.
2. вычисление корней в обратном порядке ("задом наперёд"), от X[N] до X[1] и
3. применение отдельного цикла для вывода корней в естественном прямом порядке, от X[1] до X[N], что требует трёх дополнительных строк в программе, увеличивает программу и уменьшает быстродействие программы.
В данной статье вниманию читателей предлагается упрощённый простейший метод Гаусса, расширяющий множество СЛАУ решаемых методом Гаусса, с приведением матрицы коэффициентов не к традиционному правому верхнему, а к левому нижнему, к левому верхнему или к правому нижнему треугольному виду, причём левые проще (упрощённые) и вычисляют и выводят корни в естественном прямом порядке, а правые (прежней сложности) - "задом наперёд" и для упорядоченного вывода требуют дополнительного цикла вывода корней:
1. Матрица коэффициентов A[I,J] и вектора-столбца свободных членов СЛАУ b[I] вводится в виде расширенной матрицы (A|b). Ввод расширенной матрицы СЛАУ (A|b) в виде квадратной матрицы коэффициентов A и присоединённого к ней вектора-колонки b упрощает и ускоряет дальнейшие вычисления.
2. Расширенная матрица СЛАУ (A|b) методом исключения неизвестных приводится к левому нижнему или к левому верхнему треугольному виду (A'|b').
Коэффициенты матрицы и свободный член ведущей строки в данном алгоритме при преобразовании не изменяются.
Если по ходу приведения матрицы к треугольному виду на активной диагонали (в случае Left-Lower - на главной диагонали) встречается элемент с нулевым значением, то блок SWAP/END SWAP делает обмен этой строки на первую строку с ненулевым значением элемента в той же колонке из следующих строк.
В ходе преобразоввания матрицы СЛАУ к треугольному виду элементы на активной диагонали с нулевыми значениями, кроме первого, в предыдущих вычислениях могут превратиться в ненулевые и наоборот, не нулевые в нулевые, поэтому проверка на ноль и обмен строк производятся не до преобразования, а по ходу преобразования.
Блок SWAP/END SWAP, даже в случае без действительного обмена строк, из-за множества дополнительных проверок оператором IF, уменьшает быстродействие программы, но немного увеличивает множество решаемых СЛАУ. Если в нём нет нужды, то его можно удалить из программы вовсе.
Построчное исключение неизвестных в колонках может быть, как сверху вниз, так и снизу вверх.
Если в дальнейших вычислениях не требуются обнулённые элементы матрицы коэффициентов, то их можно не записывать в матрицу, что увеличивает быстродействие.
3. После приведения исходной расширенной матрицы СЛАУ (A|b) к треугольному виду (A'|b') вычисляется определитель исходной матрицы A по формуле: det(A)=det(A')*(-1)^s, где s - количество обмена строк в исходной матрице. Если обмена строк нет, то s=0, (-1)^s=(-1)^0=1, а det(A)=det(A'), а если есть, то модуль остаётся прежним и меняется только знак.
В алгоритмах Left-Upper и Right-Lower для вычисления определителя вместо главной диагонали используется побочная диагональ (side diagonal), поэтому побочный определитель, в общем случае, не равен главному определителю.
4. Затем вычисляется и выводится вектор-строка x корней СЛАУ в естественном прямом порядке от x[1] до x[N], что не требует отдельного цикла для вывода корней в естественном упорядоченном виде, уменьшает программу и увеличивает быстродействие программы.
Первый корень можно вычислять и выводить внутри цикла, но отдельно - быстрее.
5. Для проверки правильности решения СЛАУ по формуле b=A*x вычисляется и выводится вычисленный вектор-столбец свободных членов b расширенной матрицы СЛАУ и сравнивается с исходным вектором-столбцом свободных членов СЛАУ. При совпадении вычисленного и исходного векторов-столбцов b найденное решение правильное.
Если пользователю не требуется упорядоченное вычисление корней, то можно пользоваться и прежним способом [1] с приведением матрицы коэффициентов к традиционному правому верхнему (Right-Left) треугольному виду.
Для, якобы, уменьшения ошибки вычислений в справочнике Дьяконова приведено очень небольшое описание разновидности метода Гаусса с выделением главного элемента и очень мудрёная программа 4.2. с двойным набором массивов для хранения матрицы СЛАУ. На самом деле, если не применяется округление, то эта разновидность метода Гаусса относительную ошибку вычислений не изменяет. Например, умножение или деление на 10^N только сдвигает мантиссу числа на N порядков от оптимальной 1.0 в сторону больших чисел или на те же N порядков от оптимальной 1.0 в сторону малых чисел, относительная ошибка вычислений при этом не изменяется. Кроме этого, теряется время на поиск главного элемента и обмен строк. Поэтому, хотя болшого смысла в этом нет, в статье [4] приведено упрощение и этой разновидности метода Гаусса с одинарным набором массивов для хранения матрицы СЛАУ.
Приведение матрицы СЛАУ к треугольному виду можно выполнить и методом вращения по программе 4.3 в справочнике Дьяконова, но он приблизительно вдвое медленнее, чем метод исключения в простейшем методе Гаусса, по измерениям в TurboBasic'е около 40 usec вместо около 20 usec.
В 1966 году Барейс предложил алгоритм приведения матрицы СЛАУ с целочисленными коэффициентами к треугольному виду вообще без использования операции деления, который применим и для действительных чисел (чисел с плавающей точкой). Сложность алгоритма такая же, как и в простейшем методе Гаусса - O(n^3), но при этом уменьшается максимальная величина коэффициентов матрицы, а быстродействие меньше, чем в простейшем методе Гаусса.
Вычисление корней можно выполнить и методом Гаусса-Жордана, но он медленнее простейшего метода Гаусса.
Метод Крамера со сложностью алгоритма O(n^4) тоже медленнее простейшего метода Гаусса, но решает некоторые системы не решаемые методом Гаусса.
1.1. Программа 4-1LL.BAS на Borland TurboBasic'е:
1.1. Программа 4-1LL.BAS c приведением матрицы коэффициентов СЛАУ к левому нижнему (Left-Lower) треугольному виду:
По измерениям в Borland TurboBasic'е с отключенными операторами обнуления, вычисления определителя матрицы, вывода на экран и без обмена строк:
1. система из 3-х уравнений решается приблизительно за 24-21 usec,
2. система из 4-х уравнений решается приблизительно за 46-43 usec.
Количество уравнений N, коэфффициенты матрицы A[I,J] и вектор-столбец свободных членов B[I] вводятся прямо в текст программы в операторах DATA в виде расширенной матрицы (A|b), не активные СЛАУ при этом выключаются оператором комментария ('). Ввод с клавиатуры, из другого блока пользовательской программы или из файла пользователи могут написать сами. Вывод на экран в нужном формате, передачу вектора с корнями в другой блок пользовательской программы или запись его в файл пользователи также могут написать сами.
Рис.1. Снимок с экрана результата прогона программы 4-1LL.BAS в компиляторе Borland TurboBasic.
На снимке можно убедиться, что после преобразования, матрица действительно стала левой нижней треугольной.
Хотя по смыслу в СЛАУ вектор корней x и является вектором-строкой, но, по правилам умножения матриц на вектор, которые в общем случае не обязательно являются матрицами СЛАУ, для проверки правильности решения СЛАУ матрицу коэффициентов СЛАУ A нужно умножать на него, как на вектор-столбец и записывать справа от матрицы b = A * x.
Наглядное пособие 4-1LLDEM.EXE (исходник: 4-1LLDEM.BAS) для изучающих метод последовательного исключения неизвестных Left-Lower, показывающее последовательность вычислений:
1.2. Программа 4-1LL2.BAS на Borland TurboBasic'е:
Более быстрый вариант программы, в котором, для увеличения быстродействия, матрица СЛАУ записывается не в двумерный массив, а в одномерный массив, так как обращение к элементам одномерного массива быстрее, чем обращение к элементам двумерного массива.
С приведением матрицы коэффициентов СЛАУ к левому нижнему треугольному виду:
По измерениям в Borland TurboBasic'е с отключенными операторами обнуления, вычисления определителя матрицы и вывода на экран:
1. система из 3-х уравнений решается приблизительно за 19-17 usec,
2. система из 4-х уравнений решается приблизительно за 38-36 usec.
Рис.2. Снимок с экрана результата прогона программы 4-1LL2.BAS в компиляторе TurboBasic.
На снимке можно убедиться, что после преобразования, матрица действительно стала левой нижней треугольной.
2. Программа 4-1LU.BAS на Borland TurboBasic'е:
Рис.4. Снимок с экрана результата прогона программы 4-1LU.BAS в компиляторе TurboBasic.
На снимке можно убедиться, что после преобразования матрица действительно стала левой верхней треугольной.
Наглядное пособие 4-1LUDEM.EXE (исходник:4-1LUDEM.BAS) для изучающих метод последовательного исключения неизвестных Left-Upper, показывающее последовательность вычислений:
3. Программа 4-1LL.C на C:
Рис.5. Снимок с экрана результата прогона программы 4-1LL.C в компиляторе Tiny C.
На снимке можно убедиться, что, после преобразования, матрица действительно стала левой нижней треугольной.
4. Программа 4-1LL.cpp на С++:
Рис.6. Снимок с экрана результата прогона программы 4-1LL.cpp в компиляторе Borland C++ 5.5 в IDE Code::Blocks 17.12.
5. Программа 4-1LL.py на Python'е:
Рис.7. Снимок с экрана прогона программы 4-1LL.py в онлайн компиляторе Python на странице https://ishaanbhimwal.github.io/online-python-compiler/
На снимке можно убедиться, что, после преобразования, матрица действительно стала левой нижней треугольной.
6. Программа 4-1LL.PAS на Pascal'е:
Рис.8. Снимок с экрана результата прогона программы 4-1LL.PAS в компиляторе Turbo Pascal 5.5.
Литература:
1. Решение СЛАУ методом Гаусса. Куликов А. С.
2. Д ь я к о н о в В. П.Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ: Справочник. - М.: Наука. гл. ред. физ.-мат. лит., 1989. - 240 с. - ISBN 5-02-014530-0.
2. Система линейных алгебраических уравнений. Википедия.
Приложение:
1.1. Скачать программу 4-1LL.BAS
1.2. Скачать программу 4-1LL2.BAS
2. Скачать программу 4-1LU.BAS
3. Скачать программу 4-1LL.C
4. Скачать программу 4-1LL.cpp
5. Скачать программу 4-1LL.py
6. Скачать программу 4-1LL.PAS
Версия 2025.10.16, исправленная и дополненная.