Точные методы решения системы линейных уравнений

Точные и приближенные методы решения систем линейных уравнений

Дата добавления: 2015-06-12 ; просмотров: 5268 ; Нарушение авторских прав

Самое простое уравнение — это линейное уравнение с од­ной переменной х вида:

Обобщением таких уравнений является линейное уравнение с несколькими переменными х₁, х₂, . х_n вида:

Многие задачи сводятся к решению конечного множества уравнений вида (2), то есть системы линейных уравнений. В общем виде система n линейных уравнений с n переменными x₁, x₂. x_n записывается как совокупность числовых равенств:

(3)

Коэффициенты a_ij системы для их упорядочения снабжаются двумя индексами, причем индекс i соответствует номеру строки, а j —номеру столбца (i = 1, 2. n; j = 1, 2. n). Тогда свободный член запишется в виде b_i(i = 1, 2. n), а переменная— х_j (j = 1, 2. n). Будем далее считать, что упорядоченные наборы чисел a_ij, x_j и b_i берутся из множества действительных чисел R. Решением системы (3) n уравнений с n переменными называют упорядоченную совокупность n чисел c₁, c₂, . c_n . являющуюся решением каждого из уравнений, входящих в систему. Ясно, что эта совокупность чисел при подстановке ее в систему (3) вместо х₁, х₂, . х_n обращает каждое уравнение системы в истинное числовое равенство. Таким образом, множество решений системы является пересечением множеств решений, входящих в систему уравнений.

В частном случае, при n = 2 и n = 3 получаем хорошо знакомые системы двух линейных уравнений с двумя переменными:

(4)

и трех линейных уравнений с тремя переменными:

(5)

Решением системы (4) является упорядоченная пара чисел (c₁, c₂), а решением системы (5) — упорядоченная тройка чисел (с₁, c₂, c₃).

Известно, что исследование и нахождение решения для систем (4) и (5) не представляют особых трудностей. Но задачи практического содержания сводятся к исследованию и решению систем линейных уравнений, содержащих десятки, сотни и даже тысячи переменных. Число элементарных операций при решении линейных систем с n переменными пропорционально примерно n 3 , поэтому решение таких задач стало возможным только с появлением быстродействующих ЭВМ.

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

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

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

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

4.1 Алгоритм метода Гаусса

Пусть дана система n линейных уравнений с n переменными:

Коэффициенты а_ij при переменных будем рассматривать как элементы двумерного массива A (N, N), а свободные члены b_i— как элементы одномерного массива В (N). Решение x_i(i = ) разместим в одномерном массиве В (N). Коэффициенты а_ij и свободные члены b_i будем рассматривать как элементы расширенной матрицы

.

Предписываемые методом Гаусса преобразования будем выполнять над элементами расширенной матрицы. Опишем формально алгоритм решения линейной системы методом Гаусса без выбора главного элемента.

1. Элементы первой строки расширенной матрицы (А | В)делим на а₁₁. Полученную после такого деления первую строку умножаем последовательно на a_k1(k = ) и вычитаем ее затем из k-ой строки (k = ). После этого преобразования в первом столбце массива A (кроме ) все элементы будут равны нулю, то есть получим матрицу:

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

3. Продолжаем этот процесс исключения переменных (получения нулей) до тех пор, пока подобная процедура не будет проделана с (n — 1)-й строкой матрицы. После этого получим матрицу:

4. Элементы n-й строки делим на и в результате получаем:

На этом закончился прямой ход метода Гаусса.

5. Выполняем обратный ход метода Гаусса: в (п—1)-ю строку последней матрицы подставляем значение х_n и находим значение x_n-1, затем последовательно находим x_n-2, x_n-3, . , x₂, x₁ по формулам:

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

Значения переменных x_n, x_n-1, . x₁ присваиваются элементам массива свободных членов В.

Метод Гаусса с выбором главного элементазаключается в том,что при прямом ходе производится выбор наибольшего по модулю (главного) элемента и перестановка строк или столбцов. Последнее исключает деление на 0, если матрица коэффициентов содержит нулевые элементы, и повышает точность вычислений при наличии ошибок округления. Обычно для программ, ведущих вычисления с числами с плавающей точкой, достаточен выбор A_ii ¹ 0.

Метод вращения является разновидностью метода Гаусса. Он обладает повышенной устойчивостью к “провалам” промежуточных вычислений. Этот метод обеспечивает приведение исходной системы к системе с верхней треугольной матрицей (см. литературу).

4.2 Правило Крамера

Правило Крамера рассмотрим на примере двух линейных уравнений с двумя переменными:

(17)

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

Умножим первое уравнение системы (17) на коэффициент а₂₂, а второе — на — a₁₂ и полученные уравнения сложим. Тогда имеем:

Если a₁₁a₂₂ — a₂₁a₁₂ 0, то получаем значение переменной

Аналогично, умножая первое уравнение системы (17) на —a₂₁, второе — на а₁₁ и складывая их, получаем:

Введем обозначения: a₁₁a₂₂ — a₂₁a₁₂ = = ;

b₁a₂₂ — b₂a₁₂ =

a₁₁b₂ — a₂₁b₁ =

Следовательно, — определитель матрицы коэффициентов системы (17). Определитель получается из определителя , если коэффициенты системы (17) при x₁ (первый столбец матрицы А) заменить свободными членами

B = ;

Определитель — если заменить коэффициенты системы (17) при x₂ (второй столбец матрицы А) свободными членами.

Определитель называется главным определителем системы (17), а определители ₁ и ₂ — вспомогательными.

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

Таким образом, если главный определитель системы уравнений (17) , то система имеет единственное решение, определяемое формулами

(18)

Формулы (18) называются формулами Крамера.

Нахождение решения линейной системы (17) по формулам (18) называется правилом Крамера, который одним из первых пришел к понятию определителя и доказал сформулированное выше предложение.

Справедливы также следующие два предложения:

1. Если главный определитель системы (17) = 0, но хотя бы один из вспомогательных определителей ₁ или ₂ отличен от нуля, то система (17) не имеет решений (система несовместна).

2. Если все три определителя , ₁ и ₂ системы (17) равны нулю, но среди коэффициентов а_ij(i, j = 1,2) есть хотя бы один, отличный от нуля, то система (17) имеет бесконечное множество решений.

Легко дать геометрическое истолкование этим предложениям. Поскольку каждому уравнению системы (17) в плоскости соответствует некоторая прямая, то система (17) имеет единственное решение, если прямые имеют одну общую точку; не имеет решений, если прямые параллельны; и имеет бесконечное множество решений, если прямые сливаются.

Правило Крамера решения системы n линейных уравнений с n переменными имеет определенное теоретическое значение; практически им уже при n = 4 не пользуются. Установлено, что число операций умножения и деления, которые необходимо выполнить при решении линейной системы алгебраических уравнений порядка n по формулам Крамера, равно:

N(n)= (n 2 — 1)n! + n,

а по схеме единственного деления метода Гаусса:

N(n) = (n 2 + 3n — 1).

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

по Крамеру по Гауссу

при n = 5 2885 65

при n =10 360*10 6 430

Поэтому все современные ЭВМ имеют стандартные подпрограммы, реализующие различные модификации метода Гаусса.

4.3 Метод итераций и метод Зейделя

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

. (19)

Предположим, что определитель системы отличен от нуля и что диагональные коэффициенты

Выразим из первого уравнения x₁, из второго x₂, и т. д. Тогда получим эквивалентную систему:

где

Полученную систему запишем так:

(20)

и назовем ее системой нормального вида.

Будем решать ее методом последовательных приближений. За нулевое приближение возьмем, например, столбец свободных членов

Подставив в правую часть системы (20) значения (i = ), получим первое приближение: .

Затем аналогично второе: и т. д.

Таким образом, зная k-e приближение, (k + 1)-е приближение вычисляют по формуле (21)

Если последовательность приближений ( ) (j = ) имеет предел

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

Описанный метод последовательных приближений называется методом итераций. Рабочие формулы метода итераций имеют вид:

(22)

гарантирует теорема о достаточном признаке сходимости процесса итераций.

Достаточным условием сходимости итерационных методов является условие

При методе Зейделя итерационный процесс подобен описанному для метода простых итераций, однако уточненные значения Х_i j+1 сразу подставляются в последующие уравнения. Формула итерационного процесса имеет вид:

Не нашли то, что искали? Google вам в помощь!

Контрольная работа: Точные методы численного решения систем линейных алгебраических уравнений

Министерство науки и образования Украины

Сумской государственный университет

“Точные методы численного решения систем линейных алгебраических уравнений”

Сумы 2006

Постановка задачи

2. Точные методы решения СЛАУ

3. Практическая реализация метода Халецкого

3.1 Программа на языке Pascal

3.2 Решение в Excel

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

1. Введение

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

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

Пример системы линейных уравнений:

Или в матричном виде: ,

где матрица коэффициентов системы;

— вектор неизвестных; — вектор свободных членов.

2. Точные методы решения СЛАУ

Метод главных элементов.

Пусть дана система линейных алгебраических уравнений. Рассмотрим расширенную матрицу, состоящую из коэффициентов системы a[i,j] и свободных членов b[i]. Метод главных элементов — это обобщение метода исключения переменных (метода Гаусса). Обозначим матрицу, состоящую из коэффициентов при неизвестных и столбца свободных членов исходной системы за M.

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

Далее производим следующие преобразования: к каждой неглавной строке прибавим главную строку, умноженную на соответствующий множитель для этой строки. В результате мы получим матрицу, у которой q-й столбец состоит из нулей. Отбросим этот столбец и главную p-ю строку, получим новую матрицу с меньшим на единицу числом строк и столбцов. Над матрицей повторяем те же операции, после чего получаем матрицу и т.д. Таким образом, мы построим последовательность матриц

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

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

Метод квадратных корней

Метод квадратных корней разработан для решения линейных систем с симметричной матрицей коэффициентов. Пусть дана линейная система

где или (симметрическая матрица).

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

Перемножим матрицы T’ и T. Из T’ i-ю строку из T j-тый столбец, получим следующие уравнения:

После подстановки в систему, последняя распадается на две системы с треугольными матрицами.

Решим систему T’*y=b. Запишем её в развёрнутом виде:

Отсюда последовательно находим

Решаем систему T*x=y, записав её в развёрнутом виде:

Решение имеет вид

Прямым ходом с помощью формул вычисляются t[i,j] и y[i], обратным ходом по формуле находятся x[i].Текущий контроль прямого хода осуществляется с помощью так называемых «контрольных сумм», которые представляют собой сумму элементов строк матрицы исходной системы, включая свободные члены. Если над контрольными суммами в каждой строке проделывать те же операции, что и над остальными элементами этой строки, то при отсутствии ошибок в вычислениях сумма преобразованных элементов равна преобразованной сумме. Обратный ход контролируется следующим образом: если в формулах для определения вместо столбца свободных членов взять соответствующие элементы из столбца контрольных сумм, то получим новые неизвестные, которые обозначим‘.

При отсутствии ошибок ‘-=1.

Метод Халецкого

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

,

где A=[a_ij ] – квадратная матрица порядка n и

, — векторы-столбцы.

Представим матрицу A в виде произведения нижней треугольной матрицы B=[b_ij ] и верхней треугольной матрицы C=[c_ij ] с единичной диагональю , где

и .

Тогда элементы b_ij и c_ij определяются по формулам

и

Отсюда искомый вектор x может быть вычислен из уравнений и .

Так как матрицы B и C – треугольные, то системы легко решаются:

и

Из этих двух формул видно, что числа y_i выгодно вычислять вместе с коэффициентами c_ij . Этот метод получил название схемы Халецкого . В схеме применяется обычный контроль с помощью сумм. Если матрица A – симметрическая a_ij =a_ji , то

Пример. Решить систему

В первый раздел таблицы впишем матрицу коэффициентов системы, ее свободные члены и контрольные суммы. Далее так как , то первый столбец из раздела 1 переносится в первый столбец раздела II. Чтобы получить первую строку раздела II, делим все элементы первой строки раздела I на элемент , в нашем случае на 3.

;

;

;

;

.

Переходим к заполнению второго столбца раздела II, начиная со второй строки. Пользуясь формулами, определяем :

;

;

.

Далее определяя по формулам, заполняем вторую сетку для раздела II:

Затем переходим к третьему столбцу, вычисляя его элементы и по формулам и т.д., пока не будет заполнена вся таблица раздела II. Таким образом, заполнение раздела II происходит способом “елочки”: столбец — строка, столбец — строка и т.д.

В разделе Ш, пользуясь формулами, определяем и .

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

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

Решение систем линейных алгебраических уравнений (СЛАУ), несомненно, является важнейшей темой курса линейной алгебры. Огромное количество задач из всех разделов математики сводится к решению систем линейных уравнений. Этими факторами объясняется причина создания данной статьи. Материал статьи подобран и структурирован так, что с его помощью Вы сможете

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

Краткое описание материала статьи.

Сначала дадим все необходимые определения, понятия и введем обозначения.

Далее рассмотрим методы решения систем линейных алгебраических уравнений, в которых число уравнений равно числу неизвестных переменных и которые имеют единственное решение. Во-первых, остановимся на методе Крамера, во-вторых, покажем матричный метод решения таких систем уравнений, в-третьих, разберем метод Гаусса (метод последовательного исключения неизвестных переменных). Для закрепления теории обязательно решим несколько СЛАУ различными способами.

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

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

В заключении рассмотрим системы уравнений, сводящиеся к линейным, а также различные задачи, при решении которых возникают СЛАУ.

Навигация по странице.

Определения, понятия, обозначения.

Будем рассматривать системы из p линейных алгебраических уравнений с n неизвестными переменными ( p может быть равно n ) вида

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

Такую форму записи СЛАУ называют координатной.

В матричной форме записи эта система уравнений имеет вид ,
где — основная матрица системы, — матрица-столбец неизвестных переменных, — матрица-столбец свободных членов.

Если к матрице А добавить в качестве (n+1)-ого столбца матрицу-столбец свободных членов, то получим так называемую расширенную матрицу системы линейных уравнений. Обычно расширенную матрицу обозначают буквой Т , а столбец свободных членов отделяют вертикальной линией от остальных столбцов, то есть,

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

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

Если система уравнений решений не имеет, то она называется несовместной.

Если СЛАУ имеет единственное решение, то ее называют определенной; если решений больше одного, то – неопределенной.

Если свободные члены всех уравнений системы равны нулю , то система называется однородной, в противном случае – неоднородной.

Решение элементарных систем линейных алгебраических уравнений.

Если число уравнений системы равно числу неизвестных переменных и определитель ее основной матрицы не равен нулю, то такие СЛАУ будем называть элементарными. Такие системы уравнений имеют единственное решение, причем в случае однородной системы все неизвестные переменные равны нулю.

Такие СЛАУ мы начинали изучать в средней школе. При их решении мы брали какое-нибудь одно уравнение, выражали одну неизвестную переменную через другие и подставляли ее в оставшиеся уравнения, следом брали следующее уравнение, выражали следующую неизвестную переменную и подставляли в другие уравнения и так далее. Или пользовались методом сложения, то есть, складывали два или более уравнений, чтобы исключить некоторые неизвестные переменные. Не будем подробно останавливаться на этих методах, так как они по сути являются модификациями метода Гаусса.

Основными методами решения элементарных систем линейных уравнений являются метод Крамера, матричный метод и метод Гаусса. Разберем их.

Решение систем линейных уравнений методом Крамера.

Пусть нам требуется решить систему линейных алгебраических уравнений

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

Пусть — определитель основной матрицы системы, а — определители матриц, которые получаются из А заменой 1-ого, 2-ого, …, n-ого столбца соответственно на столбец свободных членов:

При таких обозначениях неизвестные переменные вычисляются по формулам метода Крамера как . Так находится решение системы линейных алгебраических уравнений методом Крамера.

Решите систему линейных уравнений методом Крамера .

Основная матрица системы имеет вид . Вычислим ее определитель (при необходимости смотрите статью определитель матрицы: определение, методы вычисления, примеры, решения):

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

Составим и вычислим необходимые определители (определитель получаем, заменив в матрице А первый столбец на столбец свободных членов , определитель — заменив второй столбец на столбец свободных членов, — заменив третий столбец матрицы А на столбец свободных членов):

Находим неизвестные переменные по формулам :

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

Для более детальной информации смотрите раздел метод Крамера: вывод формул, примеры, решения.

Решение систем линейных алгебраических уравнений матричным методом (с помощью обратной матрицы).

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

Так как , то матрица А – обратима, то есть, существует обратная матрица . Если умножить обе части равенства на слева, то получим формулу для нахождения матрицы-столбца неизвестных переменных . Так мы получили решение системы линейных алгебраических уравнений матричным методом.

Решите систему линейных уравнений матричным методом.

Перепишем систему уравнений в матричной форме:

Так как

то СЛАУ можно решать матричным методом. С помощью обратной матрицы решение этой системы может быть найдено как .

Построим обратную матрицу с помощью матрицы из алгебраических дополнений элементов матрицы А (при необходимости смотрите статью методы нахождения обратной матрицы):

Осталось вычислить — матрицу неизвестных переменных, умножив обратную матрицу на матрицу-столбец свободных членов (при необходимости смотрите статью операции над матрицами):

или в другой записи x₁ = 4, x₂ = 0, x₃ = -1 .

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

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

Решение систем линейных уравнений методом Гаусса.

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

Суть метода Гаусса состоит в последовательном исключении неизвестных переменных: сначала исключается x₁ из всех уравнений системы, начиная со второго, далее исключается x₂ из всех уравнений, начиная с третьего, и так далее, пока в последнем уравнении останется только неизвестная переменная x_n . Такой процесс преобразования уравнений системы для последовательного исключения неизвестных переменных называется прямым ходом метода Гаусса. После завершения прямого хода метода Гаусса из последнего уравнения находится x_n , с помощью этого значения из предпоследнего уравнения вычисляется x_n-1 , и так далее, из первого уравнения находится x₁ . Процесс вычисления неизвестных переменных при движении от последнего уравнения системы к первому называется обратным ходом метода Гаусса.

Кратко опишем алгоритм исключения неизвестных переменных.

Будем считать, что , так как мы всегда можем этого добиться перестановкой местами уравнений системы. Исключим неизвестную переменную x₁ из всех уравнений системы, начиная со второго. Для этого ко второму уравнению системы прибавим первое, умноженное на , к третьему уравнению прибавим первое, умноженное на , и так далее, к n-ому уравнению прибавим первое, умноженное на . Система уравнений после таких преобразований примет вид

где , а .

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

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

Будем считать, что (в противном случае мы переставим местами вторую строку с k-ой , где ). Приступаем к исключению неизвестной переменной x₂ из всех уравнений, начиная с третьего.

Для этого к третьему уравнению системы прибавим второе, умноженное на , к четвертому уравнению прибавим второе, умноженное на , и так далее, к n-ому уравнению прибавим второе, умноженное на . Система уравнений после таких преобразований примет вид

где , а . Таким образом, переменная x₂ исключена из всех уравнений, начиная с третьего.

Далее приступаем к исключению неизвестной x₃ , при этом действуем аналогично с отмеченной на рисунке частью системы

Так продолжаем прямой ход метода Гаусса пока система не примет вид

С этого момента начинаем обратный ход метода Гаусса: вычисляем x_n из последнего уравнения как , с помощью полученного значения x_n находим x_n-1 из предпоследнего уравнения, и так далее, находим x₁ из первого уравнения.

Решите систему линейных уравнений методом Гаусса.

Исключим неизвестную переменную x₁ из второго и третьего уравнения системы. Для этого к обеим частям второго и третьего уравнений прибавим соответствующие части первого уравнения, умноженные на и на соответственно:

Теперь из третьего уравнения исключим x₂ , прибавив к его левой и правой частям левую и правую части второго уравнения, умноженные на :

На этом прямой ход метода Гаусса закончен, начинаем обратный ход.

Из последнего уравнения полученной системы уравнений находим x₃ :

Из второго уравнения получаем .

Из первого уравнения находим оставшуюся неизвестную переменную и этим завершаем обратный ход метода Гаусса .

Более детальную информацию и дополнительные примеры смотрите в разделе решение элементарных систем линейных алгебраических уравнений методом Гаусса.

Решение систем линейных алгебраических уравнений общего вида.

В общем случае число уравнений системы p не совпадает с числом неизвестных переменных n :

Такие СЛАУ могут не иметь решений, иметь единственное решение или иметь бесконечно много решений. Это утверждение относится также к системам уравнений, основная матрица которых квадратная и вырожденная.

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

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

Прежде чем находить решение системы линейных уравнений необходимо установить ее совместность. Ответ на вопрос когда СЛАУ совместна, а когда несовместна, дает теорема Кронекера – Капелли:
для того, чтобы система из p уравнений с n неизвестными ( p может быть равно n ) была совместна необходимо и достаточно, чтобы ранг основной матрицы системы был равен рангу расширенной матрицы, то есть, Rank(A)=Rank(T) .

Рассмотрим на примере применение теоремы Кронекера – Капелли для определения совместности системы линейных уравнений.

Выясните, имеет ли система линейных уравнений решения.

Найдем ранг основной матрицы системы . Воспользуемся методом окаймляющих миноров. Минор второго порядка отличен от нуля. Переберем окаймляющие его миноры третьего порядка:

Так как все окаймляющие миноры третьего порядка равны нулю, то ранг основной матрицы равен двум.

В свою очередь ранг расширенной матрицы равен трем, так как минор третьего порядка

отличен от нуля.

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

система решений не имеет.

Итак, мы научились устанавливать несовместность системы с помощью теоремы Кронекера – Капелли.

А как же находить решение СЛАУ, если установлена ее совместность?

Для этого нам потребуется понятие базисного минора матрицы и теорема о ранге матрицы.

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

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

Для примера рассмотрим матрицу .

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

Базисными являются следующие миноры второго порядка, так как они отличны от нуля

Миноры базисными не являются, так как равны нулю.

Теорема о ранге матрицы.

Если ранг матрицы порядка p на n равен r , то все элементы строк (и столбцов) матрицы, не образующие выбранный базисный минор, линейно выражаются через соответствующие элементы строк (и столбцов), образующих базисный минор.

Что нам дает теорема о ранге матрицы?

Если по теореме Кронекера – Капелли мы установили совместность системы, то выбираем любой базисный минор основной матрицы системы (его порядок равен r ), и исключаем из системы все уравнения, которые не образуют выбранный базисный минор. Полученная таким образом СЛАУ будет эквивалентна исходной, так как отброшенные уравнения все равно излишни (они согласно теореме о ранге матрицы являются линейной комбинацией оставшихся уравнений).

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

Если число уравнений r в полученной системе будет равно числу неизвестных переменных, то она будет определенной и единственное решение можно будет найти методом Крамера, матричным методом или методом Гаусса.

Решите систему линейных алгебраических уравнений .

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

а рассмотренный выше минор второго порядка отличен от нуля. На основании теоремы Кронекера – Капелли можно утверждать совместность исходной системы линейных уравнений, так как Rank(A)=Rank(T)=2 .

В качестве базисного минора возьмем . Его образуют коэффициенты первого и второго уравнений:

Третье уравнение системы не участвует в образовании базисного минора, поэтому исключим его из системы на основании теоремы о ранге матрицы:

Так мы получили элементарную систему линейных алгебраических уравнений. Решим ее методом Крамера:

Если число уравнений r в полученной СЛАУ меньше числа неизвестных переменных n , то в левых частях уравнений оставляем слагаемые, образующие базисный минор, остальные слагаемые переносим в правые части уравнений системы с противоположным знаком.

Неизвестные переменные (их r штук), оставшиеся в левых частях уравнений, называются основными.

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

Теперь считаем, что свободные неизвестные переменные могут принимать произвольные значения, при этом r основных неизвестных переменных будут выражаться через свободные неизвестные переменные единственным образом. Их выражение можно найти решая полученную СЛАУ методом Крамера, матричным методом или методом Гаусса.

Разберем на примере.

Решите систему линейных алгебраических уравнений .

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

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

Таким образом, ранг основной матрицы равен трем. Ранг расширенной матрицы также равен трем, то есть, система совместна.

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

Для наглядности покажем элементы, образующие базисный минор:

Оставляем в левой части уравнений системы слагаемые, участвующие в базисном миноре, остальные переносим с противоположными знаками в правые части:

Придадим свободным неизвестным переменным x₂ и x₅ произвольные значения, то есть, примем , где — произвольные числа. При этом СЛАУ примет вид

Полученную элементарную систему линейных алгебраических уравнений решим методом Крамера:

Следовательно, .

В ответе не забываем указать свободные неизвестные переменные.

, где — произвольные числа.

Чтобы решить систему линейных алгебраических уравнений общего вида, сначала выясняем ее совместность, используя теорему Кронекера – Капелли. Если ранг основной матрицы не равен рангу расширенной матрицы, то делаем вывод о несовместности системы.

Если ранг основной матрицы равен рангу расширенной матрицы, то выбираем базисный минор и отбрасываем уравнения системы, которые не участвуют в образовании выбранного базисного минора.

Если порядок базисного минора равен числу неизвестных переменных, то СЛАУ имеет единственное решение, которое находим любым известным нам методом.

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

Метод Гаусса для решения систем линейных алгебраических уравнений общего вида.

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

С точки зрения вычислительной работы метод Гаусса является предпочтительным.

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

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

Разберемся сначала с однородными системами.

Фундаментальной системой решений однородной системы из p линейных алгебраических уравнений с n неизвестными переменными называют совокупность линейно независимых решений этой системы, где r – порядок базисного минора основной матрицы системы.

Если обозначить линейно независимые решения однородной СЛАУ как ( – это матрицы столбцы размерности n на 1 ), то общее решение этой однородной системы представляется в виде линейной комбинации векторов фундаментальной системы решений с произвольными постоянными коэффициентами , то есть, .

Что обозначает термин общее решение однородной системы линейных алгебраических уравнений (орослау)?

Смысл прост: формула задает все возможные решения исходной СЛАУ, другими словами, взяв любой набор значений произвольных постоянных , по формуле мы получим одно из решений исходной однородной СЛАУ.

Таким образом, если мы найдем фундаментальную систему решений, то мы сможем задать все решения этой однородной СЛАУ как .

Покажем процесс построения фундаментальной системы решений однородной СЛАУ.

Выбираем базисный минор исходной системы линейных уравнений, исключаем все остальные уравнения из системы и переносим в правые части уравнений системы с противоположными знаками все слагаемые, содержащие свободные неизвестные переменные. Придадим свободным неизвестным переменным значения 1,0,0,…,0 и вычислим основные неизвестные, решив полученную элементарную систему линейных уравнений любым способом, например, методом Крамера. Так будет получено X (1) — первое решение фундаментальной системы. Если придать свободным неизвестным значения 0,1,0,0,…,0 и вычислить при этом основные неизвестные, то получим X (2) . И так далее. Если свободным неизвестным переменным придадим значения 0,0,…,0,1 и вычислим основные неизвестные, то получим X (n-r) . Так будет построена фундаментальная система решений однородной СЛАУ и может быть записано ее общее решение в виде .

Для неоднородных систем линейных алгебраических уравнений общее решение представляется в виде , где — общее решение соответствующей однородной системы, а — частное решение исходной неоднородной СЛАУ, которое мы получаем, придав свободным неизвестным значения 0,0,…,0 и вычислив значения основных неизвестных.

Разберем на примерах.

Найдите фундаментальную систему решений и общее решение однородной системы линейных алгебраических уравнений .

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

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

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

Третье уравнение исходной СЛАУ не участвует в образовании базисного минора, поэтому, может быть исключено:

Оставляем в правых частях уравнений слагаемые, содержащие основные неизвестные, а в правые части переносим слагаемые со свободными неизвестными:

Построим фундаментальную систему решений исходной однородной системы линейных уравнений. Фундаментальная система решений данной СЛАУ состоит из двух решений, так как исходная СЛАУ содержит четыре неизвестных переменных, а порядок ее базисного минора равен двум. Для нахождения X (1) придадим свободным неизвестным переменным значения , тогда основные неизвестные найдем из системы уравнений
.

Решим ее методом Крамера:

Таким образом, .

Теперь построим X (2) . Для этого придадим свободным неизвестным переменным значения , тогда основные неизвестные найдем из системы линейных уравнений
.

Опять воспользуемся методом Крамера:

Получаем .

Так мы получили два вектора фундаментальной системы решений и , теперь мы можем записать общее решение однородной системы линейных алгебраических уравнений:
, где C₁ и C₂ – произвольные числа.

Найдите общее решение неоднородной системы линейных алгебраических уравнений .

Общее решение этой системы уравнений будем искать в виде .

Исходной неоднородной СЛАУ соответствует однородная система

общее решение которой мы нашли в предыдущем примере
.

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

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

Для нахождения придадим свободным неизвестным переменным значения , тогда система уравнений примет вид , откуда методом Крамера найдем основные неизвестные переменные:

Имеем , следовательно,

где C₁ и C₂ – произвольные числа.

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

Решение систем уравнений, сводящихся к СЛАУ.

Некоторые системы уравнений с помощью замены переменных можно свести к линейным. Рассмотрим несколько примеров.