Решение систем линейных уравнений лекция

Решение систем линейных уравнений лекция

Системой m линейных уравнений с n неизвестными называется система вида

где a_ij и b_i (i=1,…,m; b=1,…,n) – некоторые известные числа, а x₁,…,x_n – неизвестные. В обозначении коэффициентов a_ij первый индекс iобозначает номер уравнения, а второй j – номер неизвестного, при котором стоит этот коэффициент.

Коэффициенты при неизвестных будем записывать в виде матрицы , которую назовём матрицей системы.

Числа, стоящие в правых частях уравнений, b₁,…,b_m называются свободными членами.

Совокупность n чисел c₁,…,c_n называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чисел c₁,…,c_n вместо соответствующих неизвестных x₁,…,x_n.

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

1. Система может иметь единственное решение.
2. Система может иметь бесконечное множество решений. Например, . Решением этой системы является любая пара чисел, отличающихся знаком.
3. И третий случай, когда система вообще не имеет решения. Например, , если бы решение существовало, то x₁ + x₂ равнялось бы одновременно нулю и единице.

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

Рассмотрим способы нахождения решений системы.

МАТРИЧНЫЙ МЕТОД РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

Матрицы дают возможность кратко записать систему линейных уравнений. Пусть дана система из 3-х уравнений с тремя неизвестными:

Рассмотрим матрицу системы и матрицы столбцы неизвестных и свободных членов

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

или короче A∙X=B.

Здесь матрицы A и B известны, а матрица X неизвестна. Её и нужно найти, т.к. её элементы являются решением данной системы. Это уравнение называют матричным уравнением.

Пусть определитель матрицы отличен от нуля |A| ≠ 0. Тогда матричное уравнение решается следующим образом. Умножим обе части уравнения слева на матрицу A -1 , обратную матрице A: . Поскольку A -1 A = E и E∙X = X, то получаем решение матричного уравнения в виде X = A -1 B.

Заметим, что поскольку обратную матрицу можно найти только для квадратных матриц, то матричным методом можно решать только те системы, в которых число уравнений совпадает с числом неизвестных. Однако, матричная запись системы возможна и в случае, когда число уравнений не равно числу неизвестных, тогда матрица A не будет квадратной и поэтому нельзя найти решение системы в виде X = A -1 B.

Примеры. Решить системы уравнений.

Найдем матрицу обратную матрице A.

,

Таким образом, x = 3, y = – 1.

Решите матричное уравнение: XA+B=C, где

Выразим искомую матрицу X из заданного уравнения.

Найдем матрицу А -1 .

Решите матричное уравнение AX+B=C, где

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

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

Рассмотрим систему 3-х линейных уравнений с тремя неизвестными:

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

называется определителем системы.

Составим ещё три определителя следующим образом: заменим в определителе D последовательно 1, 2 и 3 столбцы столбцом свободных членов

Тогда можно доказать следующий результат.

Теорема (правило Крамера). Если определитель системы Δ ≠ 0, то рассматриваемая система имеет одно и только одно решение, причём

Доказательство. Итак, рассмотрим систему 3-х уравнений с тремя неизвестными. Умножим 1-ое уравнение системы на алгебраическое дополнение A₁₁ элемента a₁₁, 2-ое уравнение – на A₂₁ и 3-е – на A₃₁:

Сложим эти уравнения:

Рассмотрим каждую из скобок и правую часть этого уравнения. По теореме о разложении определителя по элементам 1-го столбца

.

Далее рассмотрим коэффициенты при x₂:

Аналогично можно показать, что и .

Наконец несложно заметить, что

Таким образом, получаем равенство: .

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

Аналогично выводятся равенства и , откуда и следует утверждение теоремы.

Таким образом, заметим, что если определитель системы Δ ≠ 0, то система имеет единственное решение и обратно. Если же определитель системы равен нулю, то система либо имеет бесконечное множество решений, либо не имеет решений, т.е. несовместна.

Примеры. Решить систему уравнений

Решите систему уравнений при различных значениях параметра p:

Система имеет единственное решение, если Δ ≠ 0.

. Поэтому .

1. При
2. При p = 30 получаем систему уравнений которая не имеет решений.
3. При p = –30 система принимает вид и, следовательно, имеет бесконечное множество решений x=y,y Î R.

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

Вновь рассмотрим систему из трёх уравнений с тремя неизвестными:

.

Первое уравнение оставим без изменения, а из 2-го и 3-го исключим слагаемые, содержащие x₁. Для этого второе уравнение разделим на а₂₁ и умножим на –а₁₁, а затем сложим с 1-ым уравнением. Аналогично третье уравнение разделим на а₃₁ и умножим на –а₁₁, а затем сложим с первым. В результате исходная система примет вид:

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

Отсюда из последнего уравнения легко найти x₃, затем из 2-го уравнения x₂ и, наконец, из 1-го – x₁.

При использовании метода Гаусса уравнения при необходимости можно менять местами.

Часто вместо того, чтобы писать новую систему уравнений, ограничиваются тем, что выписывают расширенную матрицу системы:

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

К элементарным преобразованиям матрицы относятся следующие преобразования:

1. перестановка строк или столбцов;
2. умножение строки на число, отличное от нуля;
3. прибавление к одной строке другие строки.

Примеры: Решить системы уравнений методом Гаусса.

Вернувшись к системе уравнений, будем иметь

Выпишем расширенную матрицу системы и сведем ее к треугольному виду.

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

Разделим вторую строку матрицы на 2 и поменяем местами первый и третий столбики. Тогда первый столбец будет соответствовать коэффициентам при неизвестной z, а третий – при x.

Вернемся к системе уравнений.

Из третьего уравнения выразим одну неизвестную через другую и подставим в первое.

Таким образом, система имеет бесконечное множество решений.

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

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

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

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

Линейное уравнение с n неизвестными x0, x1, ѕ, xn-1 может быть определено при помощи выражения

( 8.1)

Множество из n линейных уравнений

( 8.2)

где A=(a_i,j) есть вещественная матрица размера nxn , а векторы b и x состоят из n элементов.

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

8.2. Алгоритм Гаусса

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

В подразделе дается общая характеристика метода Гаусса, достаточная для начального понимания алгоритма и позволяющая рассмотреть возможные способы параллельных вычислений при решении систем линейных уравнений . Более полное изложение алгоритма со строгим обсуждением вопросов точности получаемых решений может быть получено, например, в работах [ [ 6 ] , [ 22 ] , [ 47 ] ] и др.

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

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

• умножение любого из уравнений на ненулевую константу;
• перестановка уравнений;
• прибавление к уравнению любого другого уравнения системы.

Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе – прямой ход метода Гаусса – исходная система линейных уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду

где матрица коэффициентов получаемой системы имеет вид

На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной x_n-1 , после этого из предпоследнего уравнения становится возможным определение переменной x_n-2 и т.д.

8.2.1.1. Прямой ход алгоритма Гаусса

Прямой ход метода Гаусса состоит в последовательном исключении неизвестных в уравнениях решаемой системы линейных уравнений . На итерации i, 0 , метода производится исключение неизвестной i для всех уравнений с номерами k , большими i (т.е. i ). Для этого из этих уравнений осуществляется вычитание строки i , умноженной на константу ( a_ki/a_ii ), с тем чтобы результирующий коэффициент при неизвестной x_i в строках оказался нулевым – все необходимые вычисления могут быть определены при помощи соотношений:

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

На первой итерации производится исключение неизвестной x0 из второй и третьей строки. Для этого из этих строк нужно вычесть первую строку, умноженную соответственно на 2 и 1. После этих преобразований система уравнений принимает вид:

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

На рис. 8.1 представлена общая схема состояния данных на i -й итерации прямого хода алгоритма Гаусса . Все коэффициенты при неизвестных, расположенные ниже главной диагонали и левее столбца i , уже являются нулевыми. На i -й итерации прямого хода метода Гаусса осуществляется обнуление коэффициентов столбца i , расположенных ниже главной диагонали, путем вычитания строки i , умноженной на нужную ненулевую константу. После проведения (n-1) подобной итерации матрица, определяющая систему линейных уравнений , становится приведенной к верхнему треугольному виду.

При выполнении прямого хода метода Гаусса строка, которая используется для исключения неизвестных, носит наименование ведущей, а диагональный элемент ведущей строки называется ведущим элементом. Как можно заметить, выполнение вычислений является возможным только, если ведущий элемент имеет ненулевое значение. Более того, если ведущий элемент a_i,i имеет малое значение, то деление и умножение строк на этот элемент может приводить к накоплению вычислительной погрешности и вычислительной неустойчивости алгоритма.

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

Вычислительная сложность прямого хода алгоритма Гаусса с выбором ведущей строки имеет порядок O(n 3 ) .

8.2.1.2. Обратный ход алгоритма Гаусса

После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной x_n-1 , после этого из предпоследнего уравнения становится возможным определение переменной x_n-2 и т.д. В общем виде выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений:

Поясним, как и ранее, выполнение обратного хода метода Гаусса на примере рассмотренной в п. 8.2.1.1 системы линейных уравнений

Из последнего уравнения системы можно определить, что неизвестная x₂ имеет значение 3 . В результате становится возможным разрешение второго уравнения и определение значение неизвестной x₁=13 , т.е.

На последней итерации обратного хода метода Гаусса определяется значение неизвестной x₀ , равное -44 .

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

Вычислительная сложность обратного хода алгоритма Гаусса составляет O(n 2 ) .

Лекция на тему «Системы линейных уравнений»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Лекция натему «Системы линейных уравнений»

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

Здесь а_{i j} и b_i (i = ; j = ) — заданные, а x_j — неизвестные действительные числа. Используя понятие произведения матриц, можно переписать систему (5.1) в виде:

где A = (а_{i j}) — матрица, состоящая из коэффициентов при неизвестных системы (5.1), которая называется матрицей системы, X = (x₁, x₂. x_n) T ,
B = (b₁, b₂. b_m) T — векторы-столбцы, составленные соответственно из неизвестных x_j и из свободных членов b_i.

Упорядоченная совокупность n вещественных чисел (c₁, c₂. c_n) называется решением системы (5.1), если в результате подстановки этих чисел вместо соответствующих переменных x₁, x₂. x_n каждое уравнение системы обратится в арифметическое тождество; другими словами, если существует вектор C= (c₁, c₂. c_n) T такой, что AC  B.

Система (5.1) называется совместной, или разрешимой, если она имеет по крайней мере одно решение. Система называется несовместной, или неразрешимой, если она не имеет решений.

 A = ,

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

Вопрос о совместности системы (5.1) решается следующей теоремой.

Теорема Кронекера-Капелли. Система линейных уравнений совместна тогда и только тогда, когда ранги матриц A и  A совпадают, т.е.
r(A) = r(  A) = r.

Для множества М решений системы ( 1) имеются три возможности:

1) M =  (в этом случае система несовместна);

2) M состоит из одного элемента, т.е. система имеет единственное решение (в этом случае система называется определенной);

3) M состоит более чем из одного элемента (тогда система называется неопределенной). В третьем случае система (1) имеет бесчисленное множество решений.

Система имеет единственное решение только в том случае, когда
r(A) = n. При этом число уравнений — не меньше числа неизвестных (m  n); если m>n, то m-n уравнений являются следствиями остальных. Если 0

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

Системы (3) решаются одним из следующих способов:

1) методом Гаусса, или методом исключения неизвестных;

2) по формулам Крамера;

3) матричным методом.

Пример 1. Исследовать систему уравнений и решить ее, если она совместна:

Решение. Выписываем расширенную матрицу системы:

 A = .

Вычислим ранг основной матрицы системы. Очевидно, что, например, минор второго порядка в левом верхнем углу = 7  0; содержащие его миноры третьего порядка равны нулю:

M  ₃ = = 0, M  ₃ = = 0.

Следовательно, ранг основной матрицы системы равен 2, т.е. r(A)=2. Для вычисления ранга расширенной матрицы  A рассмотрим окаймляющий минор

= = -35  0,

значит, ранг расширенной матрицы r(  A) = 3. Поскольку r(A)  r(  A), то система несовместна.

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

Пример 2. Решить систему уравнений методом Гаусса:

Решение. Выпишем расширенную матрицу данной системы

и произведем следующие элементарные преобразования над ее строками:

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

;

б) третью строку умножим на (-5) и прибавим к ней вторую:

.

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

Из последнего уравнения находим z = -1,3. Подставляя это значение во второе уравнение, имеем y = -1,2. Далее из первого уравнения получим
x = — 0,7.

Метод Крамера состоит в том, что мы последовательно находим главный определитель системы (5.3), т.е. определитель матрицы А

и n вспомогательных определителей  _i (i=), которые получаются из определителя  заменой i-го столбца столбцом свободных членов.

Формулы Крамера имеют вид:

  x _i =  _i (i = ). (4)

Из (4) следует правило Крамера, которое дает исчерпывающий ответ на вопрос о совместности системы (5.3): если главный определитель системы отличен от нуля, то система имеет единственное решение, определяемое по формулам:

Если главный определитель системы  и все вспомогательные определители  _i = 0 (i= ), то система имеет бесчисленное множество решений. Если главный определитель системы  = 0, а хотя бы один вспомогательный определитель отличен от нуля, то система несовместна.

Пример 3. Решить методом Крамера систему уравнений:

Решение. Главный определитель этой системы

 = = -142  0,

значит, система имеет единственное решение. Вычислим вспомогательные определители  _i (i=), получающиеся из определителя  путем замены в нем столбца, состоящего из коэффициентов при x_i, столбцом из свободных членов:

 ₁ = = — 142,  ₂ = = — 284,

 ₃ = = — 426,  ₄ = = 142.