Схема алгоритма решения слау методом гаусса жордана. Метод гаусса онлайн
Записывается в виде расширенной матрицы, т.е. в столбец свободных членов помещается в одну матрицу с коэффициентами неизвестных. Аалгоритм заключается в приведении исходной матрицы, характеризующей систему линейных уравнений, к единичной путем эквивалентных преобразований (домножения строки матрицы на константу и сложения с другой строкой матрицы). В качестве константы используется 1/a[i][i] , т.е. число, обратное по отношению к элементу диагонали. Естественно, в ряде случаев возникают проблемы, связанные с делением на ноль, которые решаются перестановкой строк и столбцов:
Весь алгоритм можно представить 10 пунктами:
В качестве опорной выбираем первую строку матрицы.
Если элемент опорной строки, индекс которого равен номеру опорной строки, равен нулю, то меняем всю опорную строку на первую попавшуюся строку снизу, в столбце которого нет нуля.
Все элементы опорной строки делим на первый слева ненулевой элемент этой строки.
Из оставшихся снизу строк вычитают опорную строку, умноженную на элемент, индекс которого равен номеру опорной строки.
В качестве опорной строки выбираем следующую строку.
Повторяем действия 2 – 5 пока номер опорной строки не превысит число строк.
В качестве опорной выбираем последнюю строку.
Вычитаем из каждой строки выше опорную строку, умноженную на элемент этой строки с индексом равным номеру опорной строки.
В качестве опорной строки выбираем строку выше.
Повторяем 8 – 9 пока номер опорной строки не станет меньше номера первой строки.
Пример расчета 1
Пусть имеется система уравнений:
Запишем расширенную матрицу системы:
и выполним элементарные преобразования ее строк.
Для этого умножим первую строку на 1 и вычитаем из второй строки; затем умножим первую строку на 2 и вычтем из третьей строки.
В результате мы исключим переменную x 1 из всех уравнений, кроме первого. Получим:
Теперь вычтем из строки 3 строку 2, умноженную на 3:
Теперь вычитаем из 1 строки сначала 3 строку, а затем 2 строку:
После преобразований получаем систему уравнений:
Из этого следует, что система уравнений имеет следующее решение:
x1 = 1, x2 = 3 , x3 = -1
Пример расчета 2
В качестве примера решим систему уравнений, представленную в виде матрицы (Таблица 1), методом Гаусса – Жордана.
Делим первую строку на 3 (элемент первой строки, расположенный на главной диагонали), получим:
4/3 | 1/3 |
||
Умножаем первую строку на 1 и вычитаем из второй строки. Умножаем первую строку на 6 и вычитаем из третьей строки. Получим:
4/3 | 1/3 |
||
17/3 | 17/3 |
||
В первом столбце все элементы кроме диагонального равны нулю, займемся вторым столбцом, для этого выберем вторую строку в качестве опорной. Вторая Делим ее на 17/3:
4/3 | 1/3 |
||
3 /17 | |||
Умножаем строку 2 на -6 и вычитаем из третьей строки:
4/3 | 1/3 |
||
3 /17 | |||
3 3 /17 |
Теперь третья строка – опорная, делим ее на -33/17:
4/3 | 1/3 |
||
3 /17 | |||
17/3 |
Умножаем опорную строку на 3/17 и вычитаем ее из второй. Умножаем третью строку на 1 и вычитаем ее из первой
4/3 | |||
17/3 |
Получена треугольная матрица, начинается обратный ход алгоритма (во время которого получим единичную матрицу). Вторая строка становится опорной. Умножаем третью строку на 4/3 и вычитаем ее из первой:
10/3 |
|||
17/3 |
Последний столбец матрицы – решение системы уравнений.
Здесь вы сможете бесплатно решить систему линейных уравнений методом Гаусса онлайн больших размеров в комплексных числах с очень подробным решением. Наш калькулятор умеет решать онлайн как обычную определенную, так и неопределенную систему линейных уравнений методом Гаусса, которая имеет бесконечное множество решений. В этом случае в ответе вы получите зависимость одних переменных через другие, свободные. Также можно проверить систему уравнений на совместность онлайн, используя решение методом Гаусса.
О методе
При решении системы линейных уравнений онлайн методом Гаусса выполняются следующие шаги.
- Записываем расширенную матрицу.
- Фактически решение разделяют на прямой и обратный ход метода Гаусса. Прямым ходом метода Гаусса называется приведение матрицы к ступенчатому виду. Обратным ходом метода Гаусса называется приведение матрицы к специальному ступенчатому виду. Но на практике удобнее сразу занулять то, что находится и сверху и снизу рассматриваемого элемента. Наш калькулятор использует именно этот подход.
- Важно отметить, что при решении методом Гаусса, наличие в матрице хотя бы одной нулевой строки с НЕнулевой правой частью (столбец свободных членов) говорит о несовместности системы. Решение линейной системы в таком случае не существует.
Чтобы лучше всего понять принцип работы алгоритма Гаусса онлайн введите любой пример, выберите "очень подробное решение" и посмотрите его решение онлайн.
Каждой системе линейных уравнений поставим в соответствие расширенную матрицу , полученную присоединением к матрице А столбца свободных членов:
Метод Жордана–Гаусса применяется для решения системы m линейных уравнений с n неизвестными вида:
Данный метод заключается в том, что с помощью элементарных преобразований система уравнений приводится к равносильной системе уравнений с матрицей определенного вида.
Над строками расширенной матрицы осуществляем следующие элементарные преобразования:
1. перестановка двух строк ;
2. умножение строки на любое число, отличное от нуля ;
3. прибавление к одной строке другой строки, умноженной на некоторое число ;
4. отбрасывание нулевой строки (столбца) .
Пример 2.11. Решить методом Жордана–Гаусса системы линейных уравнений:
а ) Х 1 + Х 2 + 2Х 3 = -1
2Х 1 - Х 2 + 2Х 3 = -4
4Х 1 + Х 2 + 4Х 3 = -2
Решение: Составим расширенную матрицу:
Итерация 1
В качестве направляющего элемента выбираем элемент . Преобразуем первый столбец в единичный. Для этого ко второй и третьей строкам прибавляем первую строку, соответственно умноженную на (-2) и (-4). Получим матрицу:
На этом первая итерация закончена.
Итерация 2
Выбираем направляющий элемент . Так как , то делим вторую строку на -3. Затем умножаем вторую строку соответственно на (-1) и на 3 и складываем соответственно с первой и третьей строками. Получим матрицу
Итерация 3
Выбираем направляющий элемент . Так как , то делим третью строку на (-2). Преобразуем третий столбец в единичный. Для этого умножаем третью строку соответственно на (-4/3) и на (-2/3) и складываем соответственно с первой и второй строками. Получим матрицу
откуда Х 1 = 1, Х 2 = 2, Х 3 = -2.
Закончив решение, на этапе обучения необходимо выполнять проверку, подставив найденные значения в исходную систему, которая при этом должна обратиться в верные равенства.
б ) Х 1 – Х 2 + Х 3 – Х 4 = 4
Х 1 + Х 2 + 2Х 3 +3Х 4 = 8
2Х 1 +4Х 2 + 5Х 3 +10Х 4 = 20
2Х 1 – 4Х 2 + Х 3 – 6Х 4 = 4
Решение: Расширенная матрица имеет вид:
Применяя элементарные преобразования, получим:
Исходная система эквивалентна следующей системе уравнений:
Х 1 – 3Х 2 – 5Х 4 = 0
2Х 2 + Х 3 + 4Х 4 = 4
Последние две строки матрицы A (2) являются линейно зависимыми.
Определение. Строки матрицы e 1 , e 2 ,…, e m называются линейно зависимыми , если существуют такие числа , не равные одновременно нулю, что линейная комбинация строк матрицы равна нулевой строке:
где 0 =(0, 0…0). Строки матрицы являются линейно независимыми , когда комбинация этих строк равна нулю тогда и только тогда, когда все коэффициенты равны нулю.
В линейной алгебре очень важно понятие ранга матрицы , т.к. оно играет очень большое значение при решении систем линейных уравнений.
Теорема 2.3 (о ранге матрицы). Ранг матрицы равен максимальному числу её линейно независимых строк или столбцов, через которые линейно выражаются все остальные её строки (столбцы).
Ранг матрицы A (2) равен 2, т.к. в ней максимальное число линейно независимых строк равно 2 (это первые две строки матрицы).
Теорема 2.4 (Кронекера–Капели). Система линейных уравнений совместна и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы этой системы.
1. Если ранг матрицы совместной системы равен числу переменных, т.е. r = n, то система имеет единственное решение.
2. Если ранг матрицы системы меньше числа переменных, т.е. r < n, то система неопределённая и имеет бесконечное множество решений.
В данном случае система имеет 4 переменных, а её ранг равен 2, следовательно, она имеет бесконечное множество решений.
Определение. Пусть r < n , r переменных x 1 , x 2 ,…, x r называются базисными , если определитель матрицы из коэффициентов при них (базисный минор ) отличен от нуля. Остальные n – r переменных называются свободными .
Определение. Решение системы, в котором все n – r свободных переменных равны нулю, называется базисным .
Совместная система m линейных уравнений с n переменными (m < n ) имеет бесконечное множество решений, среди которых базисных решений конечное число, не превосходящее , где .
В нашем случае , т.е. система имеет не более 6 базисных решений.
Общее решение имеет вид:
Х 1 = 3Х 2 +5Х 4
Х 3 = 4 – 2Х 2 – 4Х 4
Найдем базисные решения. Для этого полагаем Х 2 = 0, Х 4 = 0, тогда Х 1 =0, Х 3 = 4. Базисное решение имеет вид: (0, 0, 4, 0).
Получим другое базисное решение. Для этого в качестве свободных неизвестных примем Х 3 и Х 4 . Выразим неизвестные Х 1 и Х 2 через неизвестные Х 3 и Х 4:
Х 1 = 6 – 3/2Х 2 – Х 4
Х 2 = 2 – 1/2Х 3 – 2Х 4 .
Тогда базисное решение имеет вид: (6, 2, 0, 0).
Пример 2.12. Решить систему:
X 1 + 2X 2 – X 3 = 7
2X 1 – 3X 2 + X 3 = 3
4X 1 + X 2 – X 3 = 16
Решение.Преобразуем расширенную матрицу системы
Итак, уравнение, соответствующее третьей строке последней матрицы, противоречиво – оно привелось к неверному равенству 0 = –1, следовательно, данная система несовместна. Данный вывод можно также получить, если заметить, что ранг матрицы системы равен 2, тогда как ранг расширенной матрицы системы равен 3.
метод Гаусса–Жордана - один из наиболее известных и широко применяемых методов решения систем линейных уравнений. Матричный метод и метод Крамера обладают тем недостатком, что они не дают ответа в том случае, когда detA = 0, а определяют лишь единственное решение при detA неравном 0. Еще одним недостатком является то, что объем математических вычислений в рамках этих методов резко возрастает с ростом числа уравнений. Метод Гаусса практически свободен от этих недостатков.
Алгоритм метода Гаусса
Комментарий к шагу 2 Метода Гаусса. Треугольной называют матрицу, в которой все элементы расположенные ниже главной диагонали равны нулю.
- На основании системы линейных уравнений составляем расширенную матрицу системы;
- Приводим матрицу к "треугольному" виду;
- Определяем ранги основной и расширенной матриц, и на основании этого делаем вывод о совместности системы и количестве допустимых решений;
- В случае, если система имеет единственное решение производим обратную подстановку и находим его, если система имеет множество решений: выражаем базисные переменные через переменные которые могут принимать произвольные значения;
Для приведения исходной расширенной матрицы к треугольному виду используем следующие два свойства определителей:
Свойство 1. Определитель не изменит свое значение, если ко всем элементам какой-либо строки (столбца) матрицы прибавить соответствующие элементы параллельной строки (столбца), умноженные на произвольное одно и то же число.
Свойство 2. При перестановке двух любых столбцов или строк матрицы ее определитель меняет знак на противоположный, а абсолютная величина определителя остается неизменной.
На основании этих свойств определителей составим алгоритм преобразования матрицы к треугольному виду:
- Рассматриваем строку i(начиная с первой). Если, элемент a i i равен нулю, меняем местами i-ю и i+1-ю строки матрицы. Знак определителя при этом изменится на противоположный. Если a 1 1 отличен от нуля - переходим к следующему шагу;
- Для каждой строки j, ниже i-й находим значение коэффициента K j =a j i /a i i ;
- Пересчитываем элементы всех строк j, расположенных ниже текущей строки i, с использованием соответствующих коэффициентов по формуле: a j k нов.=a j k -K j *a i k ; После чего, возвращаемся к первому шагу алгоритма и рассматриваем следующую строку, пока не доберемся до строки i=n-1, где n - размерность матрицы A
- В полученной треугольной матрице расчитываем произведение всех элементов главной диагонали Пa i i , которое и будет являтся определителем;
Другими словами, суть метода можно сформулировать следующим образом. Нам необходимо сделать нулевыми все элементы матрицы ниже главной диагонали. Сначала мы получаем нули в первом столбце. Для этого мы последовательно вычитаем первую строку, домноженную на нужное нам число (такое, чтоб при вычитании мы получили ноль в первом элементе строки), из всех ниже лежащих строк. Затем проделываем то же самое для второй строки, чтобы получить нули во втором столбце ниже главной диагонали матрицы. И так далее пока не доберемся до предпоследней строки.
4. Метод Жордана - Гаусса.
Схема с выбором главного элемента состоит в том, что требование неравенства нулю диагональных элементов akk, на которые происходит деление в процессе исключения, заменятся более жестким: из всех элементов К-го столба выбрать наибольший по модулю и переставить уравнения так, чтобы этот элемент оказался на месте элемента акк. Выбор главного элемента и связанная с ним перестановка строк необходимы в тех случаях, когда на каком-либо i-ом шаге акк=0 либо же акк очень мало по остальными элементами i- го столбца: при делении на такое «малое» акк будут получаться большие числа с большими абсолютными погрешностями, в результате чего решение может сильно исказиться.
Ниже излагается алгоритм полного исключения неизвестных или метод Жордана – Гаусса. Суть метода состоит в том, что, рассмотрев первое уравнение, в нем неизвестное с коеффициэнтом, отличным от нуля (в дальнейшем разрешающий элемент), и разделив первое уравнение на этот коэффициент, с помощью первого уравнения исключают это неизвестное из всех уравнений, кроме первого. Выбрав во втором уравнении неизвестное с коэффициентом, отличным от нуля, и разделив на него второе уравнение, с помощью второго исключают другие неизвестные из всех уравнений, кроме второго и т.д., т.е. с помощью одного уравнения производят полное исключение одного неизвестного. Процесс продолжается до тех пор, пока не будут использованы все уравнения.
Как известно, системы линейных алгебраических уравнений могут имеет одно решение, множество решений или системы несовместны. При элементарных преобразованиях элементов матрицы системы эти случаи выявляются в следующем:
1. В процессе исключений левая часть I –го уравнения системы обращается в нуль, а правая часть равна некоторому числу, отличному от нуля. т.е. 02+=bc0.
Это означает, что система не имеет решений, так как I – му уравнению не могут удовлетворять никакие значения неизвестных;
2. Левая и правая части I – го уравнения обращаются в нуль. Это означает, что I – ое уравнение является линейной комбинацией остальных, ему удовлетворяет любое найденное решение системы, поэтому оно может быть отброшено. В системе количество неизвестных больше количества уравнений и, следовательно, такая система имеет множество решений;
3. После того как все уравнения использованы для исключения неизвестных получено решение системы.
Таким образом, конечной целью преобразований Жордана-Гаусса является получение из заданной линейной системы
| a11x1 + a12x2 + … + a1nxn = b1,n+1 |
| a21x1 + a22x2 + … + a2nxn = b2,n+1 |
| am1x1 + am2x2 + … + amnxn = bm.n+1 |
Здесь x1, x2, …, xn - неизвестные, которые надо определить. a11, a12, …, amn - коэффициенты системы - и b1, b2, … bm - свободные члены - предполагаются известными. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.
Система (1) называется однородной, если все её свободные члены равны нулю (b1 = b2 = … = bm = 0), иначе - неоднородной.
Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.
Решение системы (1) - совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все ее уравнения в тождества.
Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у нее нет ни одного решения.
Совместная система вида (1) может иметь одно или более решений.
Решения c1(1), c2(1), …, cn(1) и c1(2), c2(2), …, cn(2) совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:
c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).
Совместная система вида (1) называется определенной, если она имеет единственное решение; если же у нее есть хотя бы два различных решения, то она называется неопределенной. Если уравнений больше, чем неизвестных, она называется переопределённой.
Решим следующую систему уравнений:
Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:
Проведём следующие действия:
· К строке 2 добавим: -4 * Строку 1.
· К строке 3 добавим: -9 * Строку 1.
· К строке 3 добавим: -3 * Строку 2.
· Строку 2 делим на -2
· К строке 1 добавим: -1 * Строку 3.
· К строке 2 добавим: -3/2 * Строку 3.
· К строке 1 добавим: -1 * Строку 2.
В правом столбце получаем решение:
.
В методе Ньютона наблюдается ускорение сходимости процесса приближений. 5. Метод касательных (метод Ньютона) Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку x0 и запишем в ней уравнение касательной к графику функции f(x): y=f(x0)+ f ¢(x) (x-x0) (1.5) Графики...
Решения от численных методов расчёта. Для определения корней уравнения не требуется знания теорий групп Абеля, Галуа, Ли и пр. и применения специальной математической терминологии: колец, полей, идеалов, изоморфизмов и т.д. Для решения алгебраического уравнения n - ой степени нужно только умение решать квадратные уравнения и извлекать корни из комплексного числа. Корни могут быть определены с...
Математики тригонометрической подстановки и проверка эффективности разработанной методики преподавания. Этапы работы: 1. Разработка факультативного курса на тему: «Применение тригонометрической подстановки для решения алгебраических задач» с учащимися классов с углубленным изучением математики. 2. Проведение разработанного факультативного курса. 3. Проведение диагностирующей контрольной...
... «проявляется» лишь в процессе преобразований. Очевидность и «завуалированность» новой переменной мы рассмотрим на конкретных примерах во второй главе данной работы. 2. Возможности применения метода замены неизвестного при решении алгебраических уравнений В этой главе выявим возможности применения метода замены неизвестного при решении алгебраических уравнений в стандартных и нестандартных...
