Решение СЛАУ методом Гаусса: от теории к практике

Введение в системы линейных уравнений и их матричное представление

Добро пожаловать на курс «Решение СЛАУ методом Гаусса: от теории к практике». Мы начинаем наше путешествие с фундаментальных основ. Прежде чем мы научимся виртуозно решать сложные системы, нам нужно понять, из чего они состоят, как они выглядят и почему математики придумали для них специальный язык — язык матриц.

Что такое линейное уравнение?

Начнем с простого. Вы наверняка сталкивались с уравнениями в школе. Но что делает уравнение именно линейным?

Линейное уравнение — это уравнение, в котором все переменные входят только в первой степени. Здесь нет квадратов (), кубов (), корней (), синусов или произведений разных переменных друг на друга (например, ).

Графически такое уравнение (если в нем две переменные) представляет собой прямую линию. Отсюда и название — линейное.

Рассмотрим простейший пример:

Где:

и — это коэффициенты (числа перед переменными).

и — это переменные (неизвестные величины).

— это свободный член (число, не умноженное на переменную).

Если мы попробуем подобрать числа вместо и , чтобы равенство было верным, мы найдем решение. Например, и подходят, так как .

Система линейных алгебраических уравнений (СЛАУ)

В реальной жизни и науке редко встречается ситуация, когда у нас есть только одно условие. Обычно условий много, и все они должны выполняться одновременно. Совокупность таких уравнений называется системой.

!Графическая интерпретация системы двух линейных уравнений с двумя неизвестными: решение — это точка пересечения прямых.

Запишем систему из двух уравнений в общем виде:

Где:

— фигурная скобка, объединяющая уравнения в систему (означает «и то, и другое одновременно»).

— неизвестные переменные, общие для обоих уравнений.

— коэффициенты при переменных.

— свободные члены.

Решить систему — значит найти такую пару чисел , которая превращает каждое уравнение системы в верное равенство. Геометрически это означает найти точку, где пересекаются линии, описываемые этими уравнениями.

Общий вид СЛАУ

Математики любят обобщать. Представьте, что у нас не две переменные, а сто. И не два уравнения, а пятьдесят. Использовать буквы алфавита () станет неудобно — они быстро закончатся. Поэтому используют индексы.

Система из уравнений с неизвестными выглядит так:

Где:

— количество уравнений (строк).

— количество переменных (столбцов).

— неизвестные переменные.

— свободные члены (правые части уравнений).

— коэффициент при -й переменной в -м уравнении.

Обратите внимание на двойной индекс у коэффициентов :

Первая цифра () указывает на номер уравнения (строки).

Вторая цифра () указывает на номер переменной (столбца).

Например, — это коэффициент во втором уравнении при третьей переменной.

Матричное представление СЛАУ

Писать каждый раз и знаки плюса очень утомительно, особенно если система большая. Здесь нам на помощь приходят матрицы.

Матрица — это просто прямоугольная таблица чисел. Мы можем «упаковать» нашу систему уравнений в компактную матричную форму.

Основные компоненты

Для записи СЛАУ нам понадобятся три элемента:

Матрица системы (Матрица коэффициентов) —

В неё мы выписываем только числа, стоящие перед переменными.

Где — это матрица размером (m строк, n столбцов), состоящая из коэффициентов .

Вектор неизвестных —

Это столбец, в котором перечислены все наши переменные.

Где — это вектор-столбец высотой , содержащий искомые переменные.

Вектор свободных членов —

Это столбец чисел, стоящих в правой части уравнений.

Где — это вектор-столбец высотой , содержащий свободные члены .

Матричное уравнение

Теперь всю громоздкую систему уравнений можно записать одной короткой и элегантной формулой:

Где:

— матрица коэффициентов.

— столбец неизвестных.

— столбец свободных членов.

Умножение матрицы на вектор по правилам матричного умножения как раз и дает левые части наших уравнений.

!Визуальная схема перехода от записи системы уравнений к матричному уравнению AX=B.

Расширенная матрица системы

Для метода Гаусса, который мы будем изучать в этом курсе, нам понадобится особое понятие — расширенная матрица.

Это матрица, которая получается, если к матрице коэффициентов приписать справа столбец свободных членов . Обычно их разделяют вертикальной чертой для удобства восприятия, но математически это единая таблица чисел.

Обозначается она часто как или .

Где:

Левая часть (до черты) — это коэффициенты при переменных.

Правая часть (после черты) — это свободные члены.

Именно с этой таблицей мы и будем работать, применяя метод Гаусса. Мы будем преобразовывать строки этой матрицы, чтобы найти решение, не таская за собой громоздкие на каждом шаге.

Сколько решений может иметь система?

Прежде чем бросаться решать систему, полезно понимать, чего мы вообще ожидаем. В мире линейной алгебры существует всего три сценария:

Единственное решение.

Это идеальный случай. Прямые (или плоскости в 3D) пересекаются ровно в одной точке. Система имеет конкретный набор значений для всех переменных. Пример: и . Решение: .

Нет решений (Система несовместна).

Это происходит, если уравнения противоречат друг другу. Геометрически это параллельные прямые, которые никогда не пересекутся. Пример: и . Очевидно, что сумма двух чисел не может быть одновременно равна и 2, и 5.

Бесконечно много решений (Система неопределена).

Это случается, если уравнения описывают одну и ту же зависимость, просто записанную по-разному. Геометрически прямые совпадают (накладываются друг на друга). Пример: и . Второе уравнение — это просто первое, умноженное на 2. Любая пара чисел, дающая в сумме 2, будет решением.

!Три возможных случая взаимного расположения прямых, иллюстрирующие количество решений системы.

Почему это важно?

Понимание матричной записи — это ключ к современной обработке данных. Компьютеры не «видят» уравнения так, как мы. Они видят массивы чисел — матрицы.

Метод Гаусса, к которому мы перейдем в следующих статьях, — это алгоритм, позволяющий последовательно упрощать расширенную матрицу, приводя её к виду, из которого ответ становится очевидным. Вместо того чтобы хаотично подставлять переменные, мы будем действовать как хирурги, выполняя точные операции над строками матрицы.

В следующей статье мы разберем, какие именно операции разрешено проводить над матрицами, чтобы не «сломать» систему уравнений, и что такое элементарные преобразования.

Прямой ход метода Гаусса: элементарные преобразования и приведение к ступенчатому виду

В предыдущей статье мы научились переводить громоздкие системы линейных уравнений (СЛАУ) на лаконичный язык матриц. Мы узнали, что такое расширенная матрица системы . Теперь настало время магии. Ну, или почти магии.

Сегодня мы разберем первую половину метода Гаусса, которая называется прямой ход. Наша цель — превратить сложную, запутанную матрицу в аккуратную «лесенку», из которой решения будут видны как на ладони.

Идея метода: упрощай и властвуй

Представьте, что у вас есть уравнение:

Где — коэффициент, — переменная, — свободный член.

Вы легко находите . А если уравнение выглядит так:

Где — числа, — переменная.

Вы сначала вычитаете 4 из обеих частей, получая , и снова приходите к ответу. Вы меняете вид уравнения, но не меняете его суть (корень остается тем же).

Метод Гаусса работает так же, но со всей системой сразу. Мы будем менять внешний вид матрицы, сохраняя верными решения системы. Такие системы называются эквивалентными.

Элементарные преобразования строк

В арсенале «матричного хирурга» есть всего три инструмента. Три действия, которые разрешено совершать над строками расширенной матрицы, не боясь испортить решение. Они называются элементарными преобразованиями.

Запомните: когда мы работаем с матрицей, каждая строка — это уравнение. То, что мы делаем со строкой матрицы, мы фактически делаем с левой и правой частью уравнения.

1. Перестановка строк местами

Мы можем поменять местами любые две строки матрицы. Это логично: от того, что мы запишем уравнения в другом порядке, решение системы не изменится.

Обозначение:

Где — первая строка, — вторая строка, а стрелка указывает на операцию обмена.

2. Умножение строки на число, не равное нулю

Мы можем умножить (или разделить) все элементы любой строки на одно и то же число . Это равносильно тому, что мы умножаем обе части уравнения на число.

Обозначение:

Где мы умножили вторую строку на (или разделили на 2), упростив числа во второй строке.

3. Прибавление к одной строке другой строки, умноженной на число

Это самый мощный инструмент. Мы можем взять одну строку, умножить её (в уме) на какое-то число и прибавить результат к другой строке. При этом изменяется только та строка, к которой мы прибавляем.

Обозначение:

Допустим, мы хотим получить ноль на месте первой цифры во второй строке:

Где:

Первая строка () осталась без изменений.

Вторая строка изменилась: из старого значения мы вычли (получили ), а из вычли (получили ).

Цель прямого хода: Ступенчатый вид

Зачем нам эти преобразования? Наша цель — привести матрицу к ступенчатому виду (или треугольному виду).

Матрица имеет ступенчатый вид, если:

Все нулевые строки (если они есть) находятся в самом низу.

Первый ненулевой элемент каждой строки находится правее первого ненулевого элемента предыдущей строки.

Визуально это выглядит как «лесенка» из чисел, под которой живут одни нули.

!Визуализация ступенчатого вида матрицы: под «ступеньками» находятся только нули.

В общем виде для матрицы мы стремимся к такому результату:

Где — это любые числа, а — это нули, которые мы обязаны получить.

Такой вид позволяет нам легко найти последнюю переменную, затем предпоследнюю и так далее. Но об этом — в следующей статье про обратный ход.

Алгоритм прямого хода

Алгоритм Гаусса — это строгая последовательность действий. Мы идем слева направо, столбец за столбцом, «обнуляя» всё, что находится под главной диагональю.

Шаг 1. Выбор ведущего элемента

Смотрим на первый столбец. Нам нужно, чтобы в верхнем левом углу (элемент ) стояло число, не равное нулю. Это будет наш «опорный» элемент. * Если там ноль, ищем ниже в этом же столбце ненулевое число и меняем строки местами. * Для удобства вычислений желательно, чтобы там стояла или (тогда считать проще), но это не обязательно.

Шаг 2. Обнуление столбца

Используя первую строку, мы делаем нули во всех ячейках первого столбца, которые находятся ниже первой строки. Для этого мы используем третье элементарное преобразование (вычитаем первую строку с нужным коэффициентом).

Шаг 3. Переход к следующей подматрице

Забываем про первую строку и первый столбец. Теперь мы работаем с оставшейся частью матрицы (начиная со второй строки и второго столбца). Повторяем процедуру: выбираем опорный элемент и обнуляем всё под ним.

Разбор примера

Лучший способ понять — увидеть числа в действии. Решим (точнее, приведем к ступенчатому виду) следующую систему:

Где — неизвестные, а числа справа — свободные члены.

1. Запишем расширенную матрицу:

2. Упростим первую строку (необязательно, но полезно). Заметим, что все числа в первой строке делятся на 2. Разделим строку на 2, чтобы получить единицу в начале.

Где первая строка была разделена на 2.

3. Обнуляем первый столбец (под диагональю). Нам нужно убрать во второй строке и в третьей строке.

* Чтобы убрать из второй строки (), вычтем из неё три первых строки: . * Чтобы убрать из третьей строки (), прибавим к ней первую строку: .

Считаем: * Новая : * Новая :

Матрица принимает вид:

4. Переходим ко второму столбцу. Первый столбец готов (1, 0, 0). Теперь работаем с подматрицей, начиная со второй строки. Наш новый опорный элемент — это (во второй строке, втором столбце). Нам нужно получить ноль под ним (там, где сейчас стоит ).

Сначала упростим вторую строку, разделив её на 2 (заметили, что все числа четные?):

Где была разделена на 2.

Теперь обнулим тройку в третьей строке. Для этого из третьей строки вычтем три вторых: .

Считаем новую : * Первый элемент: (ноль сохранился, это важно!) * Второй элемент: (цель достигнута) * Третий элемент: * Четвертый элемент:

5. Финальный результат прямого хода:

Поздравляю! Мы получили ступенчатый вид. Под главной диагональю (числа ) стоят только нули.

Что мы получили?

Давайте перепишем эту матрицу обратно в вид уравнений, чтобы понять смысл наших действий:

Посмотрите на последнее уравнение: . Отсюда мы можем мгновенно найти . Зная , мы подставим его во второе уравнение и найдем . А затем найдем .

Именно этим — обратным ходом — мы и займемся в следующей статье. Мы научимся «подниматься» по нашей лестнице снизу вверх, собирая значения переменных.

Резюме

Прямой ход метода Гаусса — это процесс приведения матрицы к ступенчатому виду.

Мы используем элементарные преобразования: меняем строки местами, умножаем на числа, складываем строки.

Наша цель — получить нули под главной диагональю.

Это значительно упрощает систему, позволяя в дальнейшем легко найти корни.

Обратный ход метода Гаусса и нахождение неизвестных переменных

Мы продолжаем наш курс по методу Гаусса. В прошлой статье мы остановились на том, что превратили нашу запутанную систему уравнений в аккуратную ступенчатую матрицу. Мы выполнили прямой ход. Теперь перед нами стоит финальная задача — извлечь из этой красивой формы конкретные значения переменных ( и так далее). Этот этап называется обратным ходом.

Если прямой ход можно сравнить с разбором сложного механизма на детали, то обратный ход — это сборка, но уже в правильном порядке, когда каждая деталь встает на свое место без усилий.

Логика обратного хода

Почему этот этап называется «обратным»? Потому что мы будем двигаться снизу вверх: от последнего уравнения к первому, от последней переменной к первой.

Вспомним, как выглядит матрица после прямого хода (в случае, если решение единственное):

Где:

— коэффициенты при переменных после преобразований.

— свободные члены после преобразований.

Нули под главной диагональю показывают, что мы исключили переменные из нижних уравнений.

Давайте перепишем эту матрицу обратно в вид обычной системы уравнений:

Посмотрите внимательно на третье уравнение. В нем осталась только одна неизвестная — . Это и есть наш ключ к решению всей системы.

!Визуальная метафора обратного хода: подъем по ступеням решения от последней переменной к первой.

Алгоритм действий

Процесс нахождения корней состоит из последовательных шагов:

Найти последнюю переменную. Из последнего уравнения мы выражаем . Это делается элементарным делением.

Подняться на строку выше. Мы берет найденное значение и подставляем его в предпоследнее уравнение. Теперь в этом уравнении остается только одна неизвестная — .

Найти предпоследнюю переменную. Решаем полученное простое уравнение.

Повторять до победного. Мы продолжаем подниматься вверх, подставляя все уже найденные значения, пока не доберемся до первого уравнения и не найдем .

Практический пример

Давайте разберем это на конкретных числах. Допустим, после прямого хода мы получили следующую расширенную матрицу:

Перепишем её в виде системы для наглядности:

Где — наши неизвестные переменные.

Шаг 1: Находим

Смотрим на нижнюю строку (третье уравнение):

Отсюда легко найти :

Мы нашли первый корень! .

Шаг 2: Находим

Поднимаемся ко второй строке:

Мы уже знаем, что . Подставим это значение:

Теперь выразим :

Второй корень найден: .

Шаг 3: Находим

Поднимаемся на самый верх, к первой строке:

Подставляем известные нам и :

Выражаем :

Третий корень найден: .

Ответ: Система решена. Вектор решения .

Особые случаи при обратном ходе

Не всегда всё идет так гладко. В конце прямого хода вы можете столкнуться с двумя ситуациями, которые требуют особого внимания.

1. Система не имеет решений (Несовместность)

Если в процессе приведения к ступенчатому виду вы получили строку вида:

Это соответствует уравнению:

Или просто:

Где — результат сложения нулей слева, а — число справа.

Так как ноль никогда не равен пяти, это уравнение не имеет смысла. Это означает, что вся система не имеет решений. Геометрически это значит, что прямые или плоскости нигде не пересекаются одновременно.

2. Бесконечно много решений (Неопределенность)

Если вы получили строку, состоящую полностью из нулей:

Это соответствует уравнению . Это истина, но она не дает нам информации о переменных. Такую строку можно просто вычеркнуть.

Если после вычеркивания количество оставшихся уравнений () стало меньше количества переменных (), значит, решений бесконечно много.

В этом случае переменные делятся на: * Базисные (зависимые) — те, которые стоят на «ступеньках» матрицы. * Свободные — те, которым не досталось ступеньки.

Свободным переменным мы можем присвоить любое значение (например, ), и выразить через них базисные переменные. Ответ будет записан в общем виде, зависящем от параметра .

Проверка решения

Хороший математик всегда сомневается. После того как вы нашли числа , настоятельно рекомендуется подставить их в исходную (самую первую, данную в условии) систему уравнений.

Если при подстановке все равенства верны — поздравляю, вы виртуозно применили метод Гаусса!

В следующей части курса мы рассмотрим, как этот метод применяется для вычисления определителей и поиска обратных матриц, расширяя наш инструментарий.

Исследование систем на совместность: теорема Кронекера-Капелли и типы решений

Мы уже прошли большой путь: научились записывать системы в матричном виде, освоили прямой ход метода Гаусса для получения ступенчатого вида и обратный ход для поиска корней. Казалось бы, мы умеем решать всё. Но в математике, как и в жизни, не на каждый вопрос существует ответ, и иногда ответов бывает слишком много.

В этой статье мы научимся предсказывать судьбу системы уравнений еще до того, как начнем вычислять конкретные . Мы ответим на вопросы: всегда ли система имеет решение? Когда решений бесконечно много? И как это определить, глядя на матрицу?

Понятие ранга матрицы

Прежде чем сформулировать главную теорему этой темы, нам нужно познакомиться с понятием ранга матрицы. Звучит грозно, но на практике, особенно в контексте метода Гаусса, это очень простая вещь.

Когда мы приводим матрицу к ступенчатому виду (делаем прямой ход), некоторые строки могут полностью обнулиться. Те строки, в которых остались ненулевые элементы, несут полезную информацию. Строки, состоящие из одних нулей, информации не несут.

Ранг матрицы — это количество ненулевых строк в её ступенчатом виде.

Обозначается ранг обычно как , или .

Рассмотрим пример. Допустим, после прямого хода мы получили такую матрицу:

Где:

Первая строка — ненулевая.

Вторая строка — ненулевая.

Третья строка — нулевая.

В этой матрице две ненулевые строки. Значит, .

Теорема Кронекера-Капелли

Это фундаментальная теорема линейной алгебры, которая дает исчерпывающий ответ на вопрос о том, имеет ли система решения. Система, имеющая хотя бы одно решение, называется совместной. Система, не имеющая решений, называется несовместной.

Для применения теоремы нам нужно сравнить ранги двух матриц:

Матрицы системы () — это матрица, составленная только из коэффициентов при переменных (левая часть до черты).

Расширенной матрицы ( или ) — это матрица, включающая и коэффициенты, и столбец свободных членов (вся таблица целиком).

!B). Стрелки указывают на вычисление ранга каждой из них. Весы, на одной чаше ранг A, на другой ранг расширенной матрицы. | Сравнение ранга матрицы коэффициентов и ранга расширенной матрицы.

Формулировка теоремы: Система линейных алгебраических уравнений совместна (имеет решение) тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы.

Где:

— ранг матрицы коэффициентов.

— ранг расширенной матрицы.

Давайте разберем возможные сценарии.

Сценарий 1: Система несовместна (Нет решений)

Это происходит, если ранг расширенной матрицы больше ранга матрицы коэффициентов.

Как это выглядит на практике? В ступенчатом виде это означает появление строки вида:

Где (число не равно нулю).

Посчитаем ранги для такой строки:

Для матрицы (левая часть) эта строка нулевая. Она не увеличивает ранг.

Для матрицы (вся строка целиком) эта строка ненулевая, так как в конце стоит . Она увеличивает ранг.

Получаем противоречие , что невозможно. Система решений не имеет.

Сценарий 2: Система совместна (Решения есть)

Если ранги равны, решение точно существует. Но какое оно? Единственное или их много? Здесь в игру вступает количество переменных ().

#### Случай А: Единственное решение

Если ранг равен количеству переменных:

Где:

— количество неизвестных переменных ().

Это «идеальный» случай. У нас столько же независимых уравнений, сколько и неизвестных. Каждая переменная жестко зафиксирована своим уравнением. Мы получаем треугольную матрицу, где на главной диагонали нет нулей.

#### Случай Б: Бесконечно много решений

Если ранг меньше количества переменных:

Это означает, что уравнений (информации) меньше, чем неизвестных. Мы не можем однозначно найти все . Некоторые переменные останутся «свободными».

!B). Ветка 'Не равны' ведет к блоку 'Нет решений'. Ветка 'Равны' ведет к сравнению r и n. Если r=n -> 'Одно решение'. Если r<n -> 'Бесконечно много решений'. | Алгоритм определения типа решения системы на основе рангов.

Свободные и базисные переменные

Давайте подробнее остановимся на случае с бесконечным количеством решений. Это часто вызывает трудности, но логика здесь проста.

Представьте, что у вас уравнение . Одно уравнение, две переменные (). Ранг меньше количества переменных. Вы можете выбрать абсолютно любым числом, а подстроится под него ().

В общем случае переменные делятся на две группы:

Базисные (зависимые) переменные. Их количество равно рангу матрицы (). Это те переменные, которые стоят на «ступеньках» в начале строк ступенчатой матрицы.

Свободные переменные. Их количество равно разнице между общим числом переменных и рангом (). Это переменные, которым не досталось своей «ступеньки».

Пример решения неопределенной системы

Рассмотрим систему после приведения к ступенчатому виду:

Проанализируем её:

Матрица коэффициентов имеет 2 ненулевые строки. .

Расширенная матрица тоже имеет 2 ненулевые строки (последняя строка полностью из нулей, мы её игнорируем). .

Ранги равны система совместна.

Количество переменных ().

() решений бесконечно много.

Шаг 1. Определяем свободные переменные. Количество свободных переменных: . Одна переменная будет свободной. Смотрим на ступеньки. Ступеньки начинаются в 1-м столбце (для ) и во 2-м столбце (для ). Значит, и — базисные. Переменной ступеньки не досталось. Значит, — свободная.

Шаг 2. Выражаем базисные через свободные. Пусть , где — любое число (константа).

Из второго уравнения:

Где мы выразили базисную переменную через параметр .

Из первого уравнения:

Подставляем найденные значения:

Где мы выразили базисную переменную через параметр .

Общее решение системы:

Подставляя вместо любые числа, мы будем получать бесконечное множество верных решений.

Геометрическая интерпретация

Чтобы лучше понять суть, полезно представить это визуально (для системы 3x3, где каждое уравнение — это плоскость в пространстве).

Единственное решение: Три плоскости пересекаются в одной единственной точке. Это как угол комнаты, где сходятся две стены и пол.

Нет решений: Плоскости могут быть параллельны друг другу (как пол и потолок) или образовывать «призму» (треугольную трубу), где попарные пересечения есть, но общей точки для всех трех нет.

Бесконечно много решений: Плоскости могут пересекаться по одной прямой (как страницы открытой книги) или вовсе совпадать (три листа бумаги, сложенные вместе).

Резюме

Теорема Кронекера-Капелли — это мощный инструмент диагностики. Прежде чем пытаться найти ответ, мы проверяем, существует ли он.

Считаем ранг матрицы коэффициентов () и расширенной матрицы ().

Если — решений нет. Пишем «система несовместна» и радуемся, что не нужно ничего считать.

Если — решение одно. Ищем его обратным ходом.

Если — решений бесконечно много. Выделяем свободных переменных и выражаем ответ через них.

В следующей статье мы рассмотрим метод Гаусса-Жордана, который позволяет довести матрицу до еще более совершенного вида и находить решение без обратного хода.

Вычислительные аспекты: выбор главного элемента и борьба с погрешностями округления

Добро пожаловать на очередной этап нашего курса «Решение СЛАУ методом Гаусса: от теории к практике». В предыдущих статьях мы изучили теорию: как приводить матрицу к ступенчатому виду, как находить ранги и как вычислять корни. На бумаге, работая с целыми числами или простыми дробями, метод Гаусса работает безупречно.

Но как только мы переносим этот алгоритм в память компьютера, мы попадаем в совершенно другой мир — мир конечной точности. Здесь никогда не равна точно одной трети, а превращается в . Здесь маленькая неточность в начале вычислений может превратиться в катастрофическую ошибку в ответе.

Сегодня мы разберем, почему классический метод Гаусса может «сломаться» на компьютере и как его улучшить с помощью стратегии выбора главного элемента.

Проблема машинной арифметики

Компьютеры не умеют хранить действительные числа с бесконечной точностью (кроме символьных вычислений, которые работают медленно). Они используют формат с плавающей точкой (floating point). Это значит, что любое число хранится как набор из ограниченного количества цифр.

Представьте, что ваш калькулятор умеет хранить только 3 значащие цифры. Попробуем сложить:

Где — первое слагаемое, а — второе слагаемое.

Точный ответ: . Но наш воображаемый калькулятор округлит это до . Информация о просто исчезла. Это называется ошибкой округления.

В методе Гаусса мы совершаем огромное количество операций умножения и сложения. Если не быть осторожными, эти ошибки накапливаются, как снежный ком, и в итоге мы можем получить ответ, который не имеет ничего общего с реальностью.

Ловушка малого ведущего элемента

Самая опасная ситуация в методе Гаусса возникает, когда ведущий элемент (тот, на который мы делим, чтобы обнулить столбец) очень близок к нулю.

Рассмотрим классический пример. Допустим, мы решаем систему, и наш гипотетический компьютер хранит только 3 значащие цифры:

Где:

— неизвестные переменные.

— коэффициент при в первом уравнении (очень маленький).

и — остальные коэффициенты и свободные члены.

Точное решение этой системы: , .

Что произойдет, если решать «в лоб»?

Мы берем первое уравнение как опорное. Чтобы обнулить во втором уравнении, нам нужно найти множитель :

Где:

— множитель, на который мы умножим первую строку.

— элемент, который мы хотим обнулить.

— наш ведущий элемент.

Теперь вычитаем из второй строки первую, умноженную на :

Новый коэффициент при :

Новый свободный член:

Второе уравнение превращается в:

Отсюда:

Пока всё похоже на правду. Но теперь найдем из первого уравнения:

Стоп. В этом примере всё сошлось, потому что числа были удобными. Но если бы мы использовали округление на промежуточных этапах (например, если бы получилось и округлилось до ), то при подстановке в первое уравнение ошибка умножилась бы на .

Деление на маленькое число равносильно умножению на огромное. Это усиливает любую, даже самую крошечную ошибку округления, допущенную ранее.

Стратегия выбора главного элемента (Pivoting)

Чтобы избежать деления на маленькие числа, математики придумали элегантный трюк. Мы помним, что перестановка строк местами — это законное элементарное преобразование, которое не меняет решение системы.

Идея проста: перед тем как обнулять столбец, давайте найдем в этом столбце (ниже текущей строки) самое большое по модулю число и поставим строку с этим числом наверх.

Это называется выбором главного элемента по столбцу (Partial Pivoting).

!Визуализация процесса выбора главного элемента: поиск максимума в столбце и перестановка строк.

Алгоритм с выбором главного элемента

Допустим, мы находимся на шаге (работаем с -м столбцом).

Поиск: Просматриваем все элементы в -м столбце, начиная с -й строки и до самого низа (-й строки).

Сравнение: Находим элемент с максимальным абсолютным значением (по модулю).

Где — модуль элемента в -й строке и -м столбце.

Перестановка: Если максимальный элемент находится не в строке , а в строке , мы меняем местами строку и строку .

Исключение: Теперь, когда на месте ведущего элемента () стоит самое большое доступное число, мы продолжаем обычный алгоритм Гаусса.

Почему это работает?

Вернемся к нашему примеру:

Смотрим на первый столбец. У нас есть кандидаты и . Очевидно, что .

Меняем строки местами:

Теперь ведущий элемент — . Множитель для обнуления нижнего элемента будет:

Мы умножаем на маленькое число (), а не на огромное (). Ошибки округления не усиливаются, а наоборот, уменьшаются. Решение будет устойчивым.

Полный выбор главного элемента

Существует еще более радикальный метод — полный выбор главного элемента (Full Pivoting). В этом случае мы ищем максимум не только в текущем столбце, а во всей оставшейся части матрицы (среди всех строк и всех столбцов).

Если максимум найдется в другом столбце, нам придется поменять местами не только строки, но и столбцы. А перестановка столбцов означает переименование переменных (например, становится на место ).

Это дает максимальную точность, но требует гораздо больше вычислений для поиска максимума и усложняет алгоритм из-за путаницы с переменными. На практике выбора главного элемента только по столбцу почти всегда достаточно.

Плохая обусловленность системы

Иногда даже выбор главного элемента не спасает. Это случается, когда сама система уравнений «больная». В математике такие системы называют плохо обусловленными (ill-conditioned).

Геометрически это означает, что прямые (или плоскости), описываемые уравнениями, почти параллельны. Они пересекаются под очень острым углом.

Представьте два уравнения:

Решение: .

А теперь чуть-чуть изменим свободный член во втором уравнении (на уровне погрешности измерения):

Решение резко меняется: . Крошечное изменение входных данных привело к колоссальному изменению ответа.

Для таких систем существуют специальные показатели — числа обусловленности, но это тема для более продвинутых курсов. Важно помнить: если определитель матрицы очень близок к нулю (но не равен ему), стоит ждать проблем с точностью.

Резюме

Компьютерная арифметика не идеальна. Ошибки округления неизбежны.

Деление на малые числа опасно. Оно масштабирует ошибки, превращая муху в слона.

Partial Pivoting (Выбор главного элемента по столбцу) — обязательная процедура в профессиональных алгоритмах. Мы всегда ставим наверх строку с самым большим по модулю коэффициентом в текущем столбце.

Это гарантирует, что множители, на которые мы умножаем строки, будут по модулю не больше единицы, что сдерживает рост погрешности.

Теперь вы знаете не только теоретическую красоту метода Гаусса, но и инженерную суровую реальность его применения. В следующих разделах мы перейдем к матричным разложениям, которые являются основой современных библиотек линейной алгебры.