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

Теорема Кронекера-Капелли. Исследование систем линейных уравнений на совместность. Первая часть.

Исследовать систему линейных агебраических уравнений (СЛАУ) на совместность означает выяснить, есть у этой системы решения, или же их нет. Ну и если решения есть, то указать сколько их.

Нам понадобятся сведения из темы «Система линейных алгебраических уравнений. Основные термины. Матричная форма записи». В частности, нужны такие понятия, как матрица системы и расширенная матрица системы, поскольку именно на них опирается формулировка теоремы Кронекера-Капелли. Как обычно, матрицу системы будем обозначать буквой $A$, а расширенную матрицу системы – буквой $\widetilde$.

Система линейных алгебраических уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы системы, т.е. $\rang A=\rang\widetilde$.

Следствие из теоремы Кронекера-Капелли

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

Исследовать СЛАУ $ \left \ <\begin& -3x_1+9x_2-7x_3=17;\\ & -x_1+2x_2-4x_3=9;\\ & 4x_1-2x_2+19x_3=-42. \end\right.$ на совместность. Если СЛАУ совместна, указать количество решений.

Чтобы выяснить наличие решений заданной СЛАУ, используем теорему Кронекера-Капелли. Нам понадобятся матрица системы $A$ и расширенная матрица системы $\widetilde$, запишем их:

Способ №1. Вычисление рангов по определению.

Согласно определению, ранг – это наивысший порядок миноров матрицы, среди которых есть хоть один, отличный от нуля. Обычно исследование начинают с миноров первого порядка, но здесь удобнее приступить сразу к вычислению минора третьего порядка матрицы $A$. Элементы минора третьего порядка находятся на пересечении трёх строк и трёх столбцов рассматриваемой матрицы. Так как матрица $A$ содержит всего 3 строки и 3 столбца, то минор третьего порядка матрицы $A$ – это определитель матрицы $A$, т.е. $\Delta A$. Для вычисления определителя применим формулу №2 из темы «Формулы для вычисления определителей второго и третьего порядков»:

$$ \Delta A=\left| \begin -3 & 9 & -7 \\ -1 & 2 & -4 \\ 4 & -2 & 19 \end \right|=-21. $$

Итак, есть минор третьего порядка матрицы $A$, который не равен нулю. Минор четвёртого порядка составить невозможно, так как для него требуется 4 строки и 4 столбца, а в матрице $A$ всего 3 строки и 3 столбца. Итак, наивысший порядок миноров матрицы $A$, среди которых есть хотя бы один не равный нулю, равен 3. Следовательно, $\rang A=3$.

Задача решена. Какие недостатки и преимущества имеет данный способ? Для начала поговорим о плюсах. Во-первых, нам понадобилось найти всего один определитель. После этого мы сразу сделали вывод о количестве решений. Обычно в стандартных типовых расчётах даются системы уравнений, которые содержат три неизвестных и имеют единственное решение. Для таких систем данный метод очень даже удобен, ибо мы заранее знаем, что решение есть (иначе примера не было бы в типовом расчёте). Т.е. нам остаётся только показать наличие решения наиболее быстрым способом. Во-вторых, вычисленное значение определителя матрицы системы (т.е. $\Delta A$) пригодится после: когда станем решать заданную систему методом Крамера или с помощью обратной матрицы.

Однако метод вычисления ранга по определению нежелательно применять, если матрица системы $A$ является прямоугольной. В этом случае лучше применить второй метод, о котором пойдёт речь ниже. Кроме того, если $\Delta A=0$, то мы ничего не сможем сказать о количестве решений заданной неоднородной СЛАУ. Может, СЛАУ имеет бесконечное количество решений, а может – ни одного. Если $\Delta A=0$, то требуется дополнительное исследование, которое зачастую является громоздким.

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

Способ №2. Вычисление ранга методом элементарных преобразований.

Какие преимущества второго способа? Главное преимущество – это его универсальность. Нам совершенно неважно, является ли матрица системы квадратной или нет. Кроме того, мы фактически провели преобразования прямого хода метода Гаусса. Осталось лишь пару действий, и мы смогли бы получить решение данной СЛАУ. Честно говоря, второй способ нравится мне более первого, но выбор – это дело вкуса.

Ответ: Заданная СЛАУ совместна и определена.

$$ \left( \begin 1 & -1 & 2 & -1\\ -1 & 2 & -3 & 3 \\ 2 & -3 & 5 & -4 \\ 3 & -2 & 5 & 1 \\ 2 & -1 & 3 & 2 \end \right) \begin \phantom<0>\\r_2+r_1\\r_3-2r_1\\ r_4-3r_1\\r_5-2r_1\end\rightarrow \left( \begin 1 & -1 & 2 & -1\\ 0 & 1 & -1 & 2 \\ 0 & -1 & 1 & -2 \\ 0 & 1 & -1 & 4 \\ 0 & 1 & -1 & 4 \end \right) \begin \phantom<0>\\\phantom<0>\\r_3-r_2\\ r_4-r_2\\r_5+r_2\end\rightarrow\\ $$ $$ \rightarrow\left( \begin 1 & -1 & 2 & -1\\ 0 & 1 & -1 & 2 \\ 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 \end \right) \begin \phantom<0>\\\phantom<0>\\\phantom<0>\\ r_4-r_3\\\phantom<0>\end\rightarrow \left( \begin 1 & -1 & 2 & -1\\ 0 & 1 & -1 & 2 \\ 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end \right) $$

Расширенная матрица системы приведена к ступенчатому виду. Ранг ступенчатой матрицы равен количеству её ненулевых строк, поэтому $\rang\widetilde=3$. Матрица $A$ (до черты) тоже приведена к ступенчатому виду, и ранг её равен 2, $\rang=2$.

Ответ: система несовместна.

Приводим расширенную матрицу системы к ступенчатому виду:

$$ \left( \begin 2 & 0 & 7 & -5 & 11 & 42\\ 1 & -2 & 3 & 0 & 2 & 17 \\ -3 & 9 & -11 & 0 & -7 & -64 \\ -5 & 17 & -16 & -5 & -4 & -90 \\ 7 & -17 & 23 & 0 & 15 & 132 \end \right) \overset> <\rightarrow>$$ $$ \rightarrow\left( \begin 1 & -2 & 3 & 0 & 2 & 17\\ 2 & 0 & 7 & -5 & 11 & 42\\ -3 & 9 & -11 & 0 & -7 & -64\\ -5 & 17 & -16 & -5 & -4 & -90 \\ 7 & -17 & 23 & 0 & 15 & 132 \end \right) \begin \phantom<0>\\ r_2-2r_1 \\r_3+3r_1 \\ r_4+5r_1 \\ r_5-7r_1 \end \rightarrow \left( \begin 1 & -2 & 3 & 0 & 2 & 17\\ 0 & 4 & 1 & -5 & 7 & 8\\ 0 & 3 & -2 & 0 & -1 & -13\\ 0 & 7 & -1 & -5 & 6 & -5 \\ 0 & -3 & 2 & 0 & 1 & 13 \end \right) \begin \phantom<0>\\ \phantom<0>\\4r_3+3r_2 \\ 4r_4-7r_2 \\ 4r_5+3r_2 \end \rightarrow $$ $$ \rightarrow\left( \begin 1 & -2 & 3 & 0 & 2 & 17\\ 0 & 4 & 1 & -5 & 7 & 8\\ 0 & 0 & -11 & 15 & -25 & -76\\ 0 & 0 & -11 & 15 & -25 & -76 \\ 0 & 0 & 11 & -15 & 25 & 76 \end \right) \begin \phantom<0>\\ \phantom<0>\\\phantom <0>\\ r_4-r_3 \\ r_5+r_2 \end \rightarrow \left( \begin 1 & -2 & 3 & 0 & 2 & 17\\ 0 & 4 & 1 & -5 & 7 & 8\\ 0 & 0 & -11 & 15 & -25 & -76\\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end \right) $$

Мы привели расширенную матрицу системы и саму матрицу системы к ступенчатому виду. Ранг расширенной матрицы системы равен трём, ранг матрицы системы также равен трём. Так как система содержит $n=5$ неизвестных, т.е. $\rang\widetilde=\rang\lt$, то согласно пункту №2 следствия из теоремы Кронекера-Капелли данная система является неопределённой, т.е. имеет бесконечное количество решений.

Ответ: система является неопределённой.

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

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

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

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

Пример №1 . Исследовать систему алгебраических уравнений (без непосредственного решения системы) с помощью теоремы Кронекера-Капелли.
Запишем систему в виде:

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

Добавим 2-ую строку к 1-ой:

Добавим 3-ую строку к 2-ой:

Умножим 3-ую строку на (2). Добавим 4-ую строку к 3-ой:

Умножим 1-ую строку на (3). Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой:

Умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Добавим 2-ую строку к 1-ой:

Это соответствует системе:
-3x₂ + 9x₃ = 6
-4x₁ + 5x₂ + 7x₃ — 10x₄ = 0
За базисные переменные примем x₁ и x₂. Тогда свободные x₃,x₄.
Ранг основной матрицы равен 2. Ранг расширенной матрицы тоже равен 2. Система совместна и имеет бесконечное множество решений.

Пример №2 .
Запишем систему в виде:

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

Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой:

Умножим 2-ую строку на (2). Умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Умножим 3-ую строку на (3). Умножим 4-ую строку на (-2). Добавим 4-ую строку к 3-ой:

Добавим 2-ую строку к 1-ой:

Умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Добавим 2-ую строку к 1-ой:

3x₂ -2x₃ – 3x₄ = 10
3x₁ -x₂ -2x₃ = 1
Необходимо переменные x₃,x₄ принять в качестве свободных переменных и через них выразить базисные – x₁, x₂.
Ранг основной матрицы равен 2. Ранг расширенной матрицы тоже равен 2. Система совместна и имеет бесконечное множество решений.

Пример №3 . Дана система линейных уравнений у которой число уравнений равно числу неизвестных. При каком условии эта система имеет единственное решение?
Ответ: Система имеет единственное решение, если ранг этой системы будет равен количеству переменных.

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

Содержание.

I Теоретическая часть

2. Численные методы . 6

1) Матричный метод. 6

2) Метод Крамера. 9

3) Метод Гаусса …………. 12

4) Итерации для линейных систем….…..…..17

a) Итерация Якоби..………………. …..18

b) Итерация Гаусса – Зейделя..……. …20

II Практическая часть

1) Матричный метод. 22

2) Метод Крамера. 24

3) Метод Гаусса……. 26

4) Листинг программы.……………………….28

III Польза введения расчётов.……………………………….65

IV Литература………... 66

I. Теоретическая часть.

Введение.

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

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

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

Любой численный метод линейной алгебры можно рассматривать как некоторую последовательность выполнения арифметических операций над элементами входных данных. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметических операций, то такой метод называется прямым. В противоположном случае численный метод называется итерационным. Прямые методы — это такие, как метод Гаусса, метод окаймления, метод пополнения, метод сопряжённых градиентов и др. Итерационные методы – это метод простой итерации, метод вращений, метод переменных направлений, метод релаксации и др. Здесь будут рассматриваться матричный метод, метод Гаусса и метод Крамера.

В данной работе будут рассмотрены численные методы в электронных таблицах Excel и программе MathCAD, Microsoft Visual Basic.

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

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

Достоинством MathCAD является также наличие в его составе электронных книг. Одна из них – учебник по самой программе, другие – справочник по различным разделам математики, физики, радиоэлектроники и др.

Microsoft Office Excel.Если же говорить о программе Excel, которая является одной из наиболее известных в обработке электронных таблиц, то без преувеличения можно утверждать, что ее возможности практически неисчерпаемы.Обработка текста, управление базами данных — программа настолько мощна, что во многих случаях превосходит специализированные программы — редакторы или программы баз данных. Такое многообразие функций может поначалу запутать, нежели заставить применять их на практике. Но по мере приобретения опыта начинаешь по достоинству ценить то, что границ возможностей Excel тяжело достичь.За всю историю табличных расчетов с применением персональных компьютеров требования пользователей к подобным программам существенно изменились. В начале основной акцент в такой программе, как, например, Visi Calc, ставился на счетные функции. Сегодня, положение другое. Наряду с инженерными и бухгалтерскими расчетами организация и графическое изображение данных приобретают все возрастающее значение. Кроме того, многообразие функций, предлагаемое такой расчетной и графической программой, не должно осложнять работу пользователя. Программы для Windows создают для этого идеальные предпосылки.В последнее время многие как раз перешли на использование Windows в качестве своей пользовательской среды. Как следствие, многие фирмы, создающие программное обеспечение, начали предлагать большое количество программ для Windows.Visual Basic.Microsoft Visual Basic – это мощная система программирования, позволяющая быстро и эффективно создавать приложения для Microsoft Windows. В отличие от Excel и MathCAD это наиболее удобная программа для решения систем линейных уравнений. Простой пользовательский интерфейс, позволяющий легко переключаться с проекта формы на сам код программы.

Удобное окно для кода самой программы:

Численные методы.

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

Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу nЧn, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.

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

Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.

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

1. Δ = 0 и каждый из дополнительных определителей Δx_i = 0. Это имеет место только тогда, когда коэффициенты при неизвестных x_i пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число k. При этом система имеет бесчисленное множество решений.

2. Δ = 0 и хотя бы один дополнительный определитель Δx_i ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных x_i, пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений.