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

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

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

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

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

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

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

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

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

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

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

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

Будем рассматривать системы из 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₂ – произвольные числа.

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

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

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

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

Содержание:

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

Метод Крамера

Определение: Системой линейных алгебраических уравнений (СЛАУ) называется выражение

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

Крамер предложил следующий метод решения СЛАУ: умножим главный определитель на для этого умножим все элементы первого столбца на эту неизвестную:

Второй столбец умножим на третий столбец — на -ый столбец — на и все эти произведения прибавим к первому столбцу, при этом произведение не изменится:

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

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

Поступая аналогично тому, как описано выше, найдем все вспомогательные определители СЛАУ:

31. Для того чтобы найти вспомогательный определитель i, надо в главном определителе СЛАУ заменить столбец i на столбец свободных коэффициентов.

Определение: Полученные выше соотношения называются формулами Крамера. Используя формулы Крамера, находят неизвестные величины Проанализируем полученные формулы:

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

Пример:

Решить СЛАУ методом Крамера

Решение:

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

Найдем главный определитель СЛАУ (раскрываем по первой строке)

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

Воспользуемся формулами Крамера

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

Выполним проверку Отсюда видно, что СЛАУ решена верно.

Матричный способ решения СЛАУ

Для решения СЛАУ матричным способом введем в рассмотрение матрицу, составленную из коэффициентов при неизвестных матpицы-столбцы неизвестных и свободных коэффициентов

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

Пример:

Решить СЛАУ матричным способом

Решение:

Введем в рассмотрение следующие матрицы

Найдем матрицу (см. Лекцию № 2): найдем детерминант матрицы А.

Пример:

Решение:

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

Отсюда находим, что х = 1; y = l; z = l.

Метод Гаусса

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

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

Обменяем в расширенной матрице первую и вторую строки местами, получим Приведем матрицу к треугольному виду, выполнив следующие преобразования: умножим элементы первой строки на (-2) и прибавим к соответствующим элементам второй строки Разделим все элементы второй строки на (-5), получим эквивалентную матрицу

Умножим элементы первой строки на (—1) и прибавим к соответствующим элементам третьей строки Разделим все элементы третьей строки на (-3), получим Таким образом, эквивалентная СЛАУ имеет вид (напомним, что первый столбец это коэффициенты при неизвестной х, второй — при неизвестной у, третий — при неизвестной z, а за вертикальной чертой находится столбец свободных коэффициентов):

Из первого уравнения находим, что х = 1.

Вывод: Из вышеизложенного материала следует, что вне зависимости от

способа решения СЛАУ всегда должен получаться один и тот же ответ.

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

Ранг матрицы. Теорема Кронекера-Капелли

Определение: Рангом матрицы называется наивысший порядок отличного от нуля минора этой матрицы.

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

При вычислении ранга необходимо начинать вычислять миноры 2 порядка, затем миноры 3 порядка и так далее, пока не будут найдены миноры, обращающиеся в нуль. Если все миноры порядка p равны нулю, то и все миноры, порядок которых больше p, равны нулю.

Пример:

Найти ранг матрицы

Решение:

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

Теорема Кронекера-Капелли (критерий совместности СЛАУ). Для совместности системы линейных алгебраических уравнений (СЛАУ) необходимо и достаточно, чтобы ранг расширенной матрицы совпадал с рангом основной матрицы, составленной из коэффициентов при неизвестных величинах.

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

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

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

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

• Скалярное произведение и его свойства
• Векторное и смешанное произведения векторов
• Преобразования декартовой системы координат
• Бесконечно малые и бесконечно большие функции
• Критерий совместности Кронекера-Капелли
• Формулы Крамера
• Матричный метод
• Экстремум функции

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

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

Министерство транспорта Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

Омский государственный университет путей сообщения

Кафедра «Автоматика и системы управления»

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

ИНМВ. 800008. 000 ТР

Студентка гр. 23 и

Тематический реферат содержит 19 страниц, 3 рисунка, 5 источников.

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

Объектом исследования являются системы линейных алгебраических уравнений

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

Рассмотрены наиболее известные алгоритмы решения СЛАУ.

1 СЛАУ: основные понятия и определения, методы решения. 3

1.1 Метод Крамера. 3

1.2 Метод Гаусса. 3

1.3 Матричный метод. 3

1.4 Метод итерации. 3

2 Практическая часть. 3

2.1 Метод Крамера. 3

2.2 Метод Гаусса. 3

2.3 Матричный метод. 3

Библиографический список. 3

Введение

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

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

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

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

1 СЛАУ: основные понятия и определения, методы решения

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

Здесь m — количество уравнений, а n— количество неизвестных. x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …,amn — коэффициенты системы — и b1, b2, … bm — свободные члены — предполагаются известными. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

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

Пример: проверить, является ли набор решением системы

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

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

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

Рангом системы строк (столбцов)матрицы А с m строк и nстолбцов называется максимальное число линейно независимых строк (столбцов). Несколько строк (столбцов) называются линейно независимыми, если ни одна из них не выражается линейно через другие. Ранг системы строк всегда равен рангу системы столбцов, и это число называется рангом матрицы.

Элементарные преобразования системы уравнений — это вычеркивание из системы тривиальных уравнений, т. е. таких, у которых все коэффициенты равны нулю; умножение любого уравнения на число, отличное от нуля; прибавление к любому i-му уравнению любого j-то уравнения, умноженного на любое число.

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

СЛАУ называется совместной, если она имеет, хотя бы одно решение.

система является совместной, т. к. она имеет, по крайней мере, одно решение , y = 3 .

В противном случае система называется несовместной.

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

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

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

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

Пример:

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

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

Существует также возможность представления линейных уравнений в матричной форме как:

или:

Здесь A — это матрица системы, x — столбец неизвестных, а, b —столбец свободных членов. Если к матрице Aприписать справа столбец свободных членов, то получившаяся матрица называется расширенной.

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

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

Для решения СЛАУ применяют прямые и итерационные методы решения.

Прямые методы дают алгоритм, по которому можно найти точное решение СЛАУ. И если бы точность была абсолютной, они бы нашли его. Реальная ЭВМ, естественно, работает с погрешностью, поэтому решение будет приближённым.

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

К наиболее известным прямым методам относятся: метод Гаусса, метод Гаусса-Жордана, метод Крамера, матричный метод, метод прогонки, метод квадратных полей (разложение Холецкого), метод вращения.

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

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

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

Итерационные методы делятся на несколько типов, в зависимости от применяемого подхода: основанные на расщеплении, вариационного типа, проекционного типа.

Наиболее известные итерационные методы: метод Якоби (метод простой итерации), метод Гаусса-Зейделя, метод релаксации, метод Монтанте, многосеточный метод, метод обобщенных минимальных невязок, метод Абрамова, метод бисопряженных градиентов, стабилизированный и квадратичный методы бисопряженных градиентов, метод квази — минимальных невязок.

1.1 Метод Крамера

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

Метод Крамера может быть использован в решении системы стольких линейных уравнений, сколько в каждом уравнении неизвестных. Если определитель системы не равен нулю, то метод Крамера может быть использован в решении, если же равен нулю, то не может.

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

Определители получаются путём замены коэффициентов при соответствующих неизвестных свободными членами:

Формулы Крамера для нахождения неизвестных:

Найти значения и возможно только при условии, если.

Этот вывод следует из следующей теоремы.

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

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

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

(система совместна и определённа).

Условия:

Рисунок 1.1— система имеет одно решение

Второй: система линейных уравнений имеет бесчисленное множество решений(система совместна и неопределённа)

Условия: , ,т. е. коэффициенты при неизвестных и свободные члены пропорциональны.

Рисунок 1.2— система имеет бесчисленное множество решений

Третий: система линейных уравнений решений не имеет(система несовместна).

Условия: .

Рисунок 1.3— система не имеет решений

1.2 Метод Гаусса

Метод Гаусса идеально подходит для решения систем содержащих больше трех линейных уравнений, для решения систем уравнений, которые не являются квадратными (чего не скажешь про метод Крамера и матричный метод). То есть метод Гаусса — наиболее универсальный метод для нахождения решения любой системы линейных уравнений, он работает в случае, когда система имеет бесконечно много решений или несовместна.

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

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

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

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

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

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

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

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

Недостатки: вычислительно неустойчивый метод, для больших СЛАУ метод Гаусса не оптимален по скорости.

1.3 Матричный метод

С помощью данного метода можно находить решение только для квадратных СЛАУ.

Нам дана система уравнений, запишем ее в матричном виде:

Если матрица А невырожденная, то тогда с помощью операций над матрицами выразим неизвестную матрицу Х. Операция деления на множестве матриц заменена умножением на обратную матрицу, поэтому домножим последнее равенство на матрицу слева:

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

Необходимым и достаточным условием этого метода является неравенство нулю определителя матрицы.

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

1.4 Метод итерации

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

Суть такого метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным). Метод позволяет получить значения корней системы с заданной точностью. Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x0.

Пусть дана СЛАУ вида: , где:

Предполагая, что не равно 0, , выразим через первое уравнение, — через второе и т. д.

Обозначим:

В матричном виде получим:

За нулевое приближение примем столбец свободных членов.

Остальные приближения аналогичным образом.

,

Тогда, — решение системы.

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

Условия сходимости: (где ), аналогично со строками.

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

2.1 Метод Крамера

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

Для этого находим определитель системы:

Следовательно, система является определённой. Для нахождения её решения вычисляем определители:

По формулам Крамера находим:

Итак, (1; 0; -1) – единственное решение системы

2.2 Метод Гаусса

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

Путем элементарных преобразований из указанной выше матрицы получим:

Проведем теперь обратный ход метода Гаусса (метод Гаусса-Жордана), то есть сделаем нули над главной диагональю. Начнем с элементов третьего столбца. Надо обнулить элемент а23, для этого от второй строки отнимем третью:

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

Полученной матрице соответствует система:

Это и есть решение

2.3 Матричный метод

Решить СЛАУ:

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

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

Тогда,

Ответ: ,

Заключение

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

Для реализации тематического реферата мною были прочитаны и исследованы литература подобной тематики и некоторые интернет-ресурсы, представленные в библиографическом списке.

Библиографический список

1. , Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 280 с.

2. Вержбицкий численных методов. — М.: Высшая школа,009. — С. 80—84. — 840 с.

3. Мальцев линейной алгебры. — Изд. 3-е, перераб.,М.: «Наука», 1970. — 400 c.

4. Электронный ресурс — Википедия

5. СТП ОмГУПС–1.2–2005. Работы студенческие учебные и выпускные квалификационные. Общие требования и правила оформления текстовых документов / Омский гос. ун-т путей сообщения. Омск, 2005. 29 с.