Учимся программировать

учимся
программировать

Программированию нельзя научить, можно только научится

Главная » Уроки по Численным методам » Урок 15. Решение СЛУ методом Крамера и методом Гаусса.

Урок 15. Решение СЛУ методом Крамера и методом Гаусса.

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

(СЛУ)
— определитель системы
Если определитель СЛУ отличен от нуля, тогда решение системы определяется однозначно по формулам Крамера:
, , ()
где:

	Для этого в столбец, где стоит переменная х, а значит в первый столбец, вместо коэффициентов при х, ставим свободные коэффициенты, которые в системе уравнений стоят в правых частях уравнений
	Для этого в столбец, где стоит переменная y (2 столбец), вместо коэффициентов при y, ставим свободные коэффициенты, которые в системе уравнений стоят в правых частях уравнений
	Для этого в столбец, где стоит переменная z, а значит втретий столбец, вместо коэффициентов при z, ставим свободные коэффициенты, которые в системе уравнений стоят в правых частях уравнений

Задание 1. Решить СЛУ с помощью формул Крамера в Excel

Ход решения

1. Запишем уравнение в матричном виде:

2. Введите матрицу А и В в Excel.

3. Найдите определитель матрицы А. Он должен получится равным 30.

4. Определитель системы отличен от нуля, следовательно — решение однозначно определяется по формулам Крамера.

5. Заполните значения dX, dY, dZ на листе Excel (см.рис.ниже).

6. Для вычисления значений dX, dY, dZ в ячейки F8, F12, F16 необходимо ввести функцию, вычисляющую определитель dX, dY, dZ соответственно.

7. Для вычисления значения X в ячейку I8 необходимо ввести формулу =F8/B5 (по формуле Крамера dX/|A|).

8. Самостоятельно введите формулы для вычисления Y и Z.

Задание 2: самостоятельно найти решение СЛУ методом Крамера:

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

Метод Гаусса

Процесс решения по методу Гаусса состоит из двух этапов.

1. Прямой ход: система приводится к ступенчатому (в частности, треугольному) виду.

Для того чтобы решить систему уравнений выписывают расширенную матрицу этой системы

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

2. Обратный ход: идет последовательное определение неизвестных из этой ступенчатой системы.

Пример. Установить совместность и решить систему

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

.

Имеем Ранги матрицы системы и ее расширенной матрицы совпали с числом неизвестных. Согласно теореме Кронекера-Капелли система уравнений совместна и решение ее единственно.
Обратный ход: Выпишем систему уравнений, расширенную матрицу которой мы получили в результате преобразований:

Итак, имеем .
Далее, подставляя в третье уравнение, найдем .
Подставляя и во второе уравнение, получим .
Подставляя в первое уравнение найденные получим .
Таким образом, имеем решение системы .

Читайте так же:

Исходный текст в excel

Решение СЛУ методом Гаусса в Excel:

В тексте будет предлагаться ввести в диапазон ячеек формулу вида: <=A1:B3+$C$2:$C$3>и т.п., это так-называемые «формулы массива». Microsoft Excel автоматически заключает ее в фигурные скобки ( < >). Для введения такого типа формул необходимо выделить весь диапазон, куда нужно вставить формулу, в первой ячейке ввести формулу без фигурных скобок (для примера выше – =A1:B3+$C$2:$C$3) и нажать Ctrl+Shift+Enter.
Пускай имеем систему линейных уравнений:

1. Запишем коэффициенты системы уравнений в ячейки A1:D4 а столбец свободных членов в ячейки E1:E4. Если в ячейке A1 находится 0, необходимо поменять строки местами так, чтоб в этой ячейке было отличное от ноля значение. Для большей наглядности можно добавить заливку ячеек, в которых находятся свободные члены.

2. Необходимо коэффициент при x1 во всех уравнениях кроме первого привести к 0. Для начала сделаем это для второго уравнения. Скопируем первую строку в ячейки A6:E6 без изменений, в ячейки A7:E7 необходимо ввести формулу: <=A2:E2-$A$1:$E$1*(A2/$A$1)>. Таким образом мы от второй строки отнимаем первую, умноженную на A2/$A$1, т.е. отношение первых коэффициентов второго и первого уравнения. Для удобства заполнения строк 8 и 9 ссылки на ячейки первой строки необходимо использовать абсолютные (используем символ $).

3. Копируем введенную формулу формулу в строки 8 и 9, таким образом избавляемся от коэффициентов перед x1 во всех уравнениях кроме первого.

4. Теперь приведем коэффициенты перед x2 в третьем и четвертом уравнении к 0. Для этого скопируем полученные 6-ю и 7-ю строки (только значения) в строки 11 и 12, а в ячейки A13:E13 введем формулу <=A8:E8-$A$7:$E$7*(B8/$B$7)>, которую затем скопируем в ячейки A14:E14. Таким образом реализуется разность строк 8 и 7, умноженных на коэффициент B8/$B$7. Не забываем проводить перестановку строк, чтоб избавиться от 0 в знаменателе дроби.

5. Осталось привести коэффициент при x3 в четвертом уравнении к 0, для этого вновь проделаем аналогичные действия: скопируем полученные 11, 12 и 13-ю строки (только значения) в строки 16-18, а в ячейки A19:E19 введем формулу <=A14:E14-$A$13:$E$13*(C14/$C$13)>. Таким образом реализуется разность строк 14 и 13, умноженных на коэффициент C14/$C$13. Не забываем проводить перестановку строк, чтоб избавиться от 0 в знаменателе дроби.

6. Прямая прогонка методом Гаусса завершена. Обратную прогонку начнем с последней строки полученной матрицы. Необходимо все элементы последней строки разделить на коэффициент при x4. Для этого в строку 24 введем формулу <=A19:E19/D19>.

7. Приведем все строки к подобному виду, для этого заполним строки 23, 22, 21 следующими формулами:

23: <=(A18:E18-A24:E24*D18)/C18>– отнимаем от третьей строки четвертую умноженную на коэффициент при x4 третьей строки.

22: <=(A17:E17-A23:E23*C17-A24:E24*D17)/B17>– от второй строки отнимаем третью и четвертую, умноженные на соответствующие коэффициенты.

21: <=(A16:E16-A22:E22*B16-A23:E23*C16-A24:E24*D16)/A16>– от первой строки отнимаем вторую, третью и четвертую, умноженные на соответствующие коэффициенты.

Читайте так же:

Как в ворде писать сбоку от картинки

Результат (корни уравнения) вычислены в ячейках E21:E24.

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

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

Скачать:

Вложение	Размер
vektor.docx	838.24 КБ

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

Введение 2
Понятие матрицы 5
Немного из биографии Гаусса 6
Решение систем линейных уравнений методом Гаусса 7
Проведение обучающего эксперимента 12
Заключение 14
Список используемой литературы 15

Увлечение математикой начинается с размышления над какой-то интересной задачей или проблемой.

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

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

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Выдающегося немецкого математика Карла Фридриха Гаусса (1777–1855) современники называли «королём математики». Ещё в раннем детстве он проявлял незаурядные математические способности.

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

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

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

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

Научиться решать системы уравнений с помощью метода Гаусса

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

1. Познакомиться с понятием «матрица» и «матрица системы».

2. Изучить метод Гаусса.

3. Научиться применять метод Гаусса на практике .

Объект(изучения): Метод Гаусса

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

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

Гипотезы: С помощью данного метода увеличивается скорость решения систем линейных уравнений . Метод Гаусса можно изучать на уроках алгебры в 7 — 8 классах как дополнительный метод решения систем уравнений с двумя и более переменными.

Математика, которая мне нравится

$\left\{\begin{array}{l} a_{11}x_1+a_{12}x_2+\ldots+a_{1n}x_n=b_1,\\ a_{21}x_1+a_{22}x_2+\ldots+a_{2n}x_n=b_2,\\ \ldots,\\ a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n=b_m. \end{array}\right.$

и расширенная матрица — с присоединенными свободными членами:

$(A|B)=\left(\begin{array}{ccc|c} a_{11}&\ldots&a_{1n}&b_1\\ a_{21}&\ldots&a_{2n}&b_2\\ \ldots&&&\ldots\\ a_{m1}&\ldots&a_{mn}&b_m \end{array}\right).$

Элементарными преобразованиями системы линейных уравнений называются:

1. умножение уравнения на отличное от нуля число;

2. прибавление к одному уравнению любого другого, умноженного на любое число;

3. перестановка уравнений местами.

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

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

$\begin{array}{r} c_{11}x_1+\ldots+c_{1r}x_r+c_{1,r+1}x_{r+1}+\ldots+c_{1n}x_n=d_1,\\ \ldots,\\ c_{rr}x_r+c_{r,r+1}x_{r+1}+\ldots+c_{rn}x_n=d_r,\\ 0=d_{r+1},\\ \ldots,\\ 0=d_m. \end{array}$

Если хотя бы одно из чисел $d_{r+1},\ldots,d_m$ отлично от нуля, то данная система уравнений решений не имеет (несовместна). Если же все они равны нулю, то последние равенств не несут никакой информации и могут быть отброшены. Тогда, если , то неизвестным $x_{r+1},\ldots,x_m$ можно придавать произвольные значения, а неизвестные $x_1,\ldots,x_r$ находим из решения системы с треугольной матрицей

$\left(\begin{array}{ccc} c_{11}&\ldots&c_{1r}\\ \ldots&&\\ 0&\ldots&c_{rr} \end{array}\right) .$

Эту систему удобно решать, определив из -го уравнения , затем из -го $x_{r-1}$ и т.д. Таким образом, можно выразить переменные $x_1,\ldots,x_r$ через $x_{r+1},\ldots,x_n$ и получить общее решение системы. Если , то система (в случае совместности) имеет единственное решение.

Преобразование системы уравнений к системе с трапециевидной матрицей называется прямым ходом метода Гаусса. Последовательное вычисление неизвестных в порядке $x_n,\ldots,x_1$ называется обратным ходом.

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

$\left\{\begin{array}{l} 2x_1-x_2+3x_3-7x_4=5,\\ 6x_1-3x_2+x_3-4x_4=7,\\ 4x_1-2x_2+14x_3-31x_4=18. \end{array}\right.$

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

$\left(\begin{array}{crcr|c} 2&-1&3&-7&5\\ 6&-3&1&-4&7\\ 4&-2&14&-31&18 \end{array}\right) .$

Первую строку умножим на 3 и вычтем из второй. Затем первую строку умножим на 2 и вычтем из третьей. Получим

$\left(\begin{array}{crrr|c} 2&-1&3&-7&5\\ 0&0&-8&17&-8\\ 0&0&8&-17&8 \end{array}\right) .$

Далее вторую строку прибавим к третьей и отбросим нулевую строку, получим

$\left(\begin{array}{crrr|c} 2&-1&3&-7&5\\ 0&0&-8&17&-8 \end{array}\right) .$

Запишем полученные уравнения:

$\left\{\begin{array}{l} 2x_1-x_2+3x_3-7x_4=5,\\ -8x_3+17x_4=-8. \end{array}\right.$

Из второго уравнения выразим :

$x_3=\frac{17x_4+8}{8}=\frac{17}{8}x_4+1.$

Полученное выражение подставляем в первое уравнение и выражаем из него :

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

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

Решение СЛАУ методом Гаусса состоит из двух этапов:

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

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

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

Матрица A называется основной матрицей системы, а матрица b — столбцом свободных членов.

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

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

Таким образом, переменные x j1 , …, x jr называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число β i ≠ 0, где i > r , то рассматриваемая система несовместна.

Пусть, что β i = 0 для любых i > r .

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом (α ij , i = 1, …, r , где i — номер строки):

Где i = 1, …, r , k = i + 1, …, n .

Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (т.е. от нижнего уравнения к верхнему), то в результате получим все решения этой СЛАУ. Так как эта система найдена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, т.е. множества их решений совпадают.

Если в совместной системе все переменные главные, то данная система является определённой.

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

Модификации метода Гаусса

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

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

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

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

Если на k-м шаге в качестве главного элемента выбирается ¹ , то в матрице A¢ должны быть переставлены местами строки c номерами k и p и столбцы с номерами k и q.

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

Существуют две более простые модификации метода Гаусса:

— с выбором главного элемента по столбцу;

— с выбором главного элемента по строке.

В первом случае в качестве главного элемента выбирается наибольший по абсолютной величине элемент k-й строки (среди элементов , i = ). Во втором — наибольший по абсолютной величине элемент k-го столбца (среди элементов , i = ). Наибольшее распространение получила первый подход, поскольку здесь не изменяется нумерация переменных.

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

LU-разложение. В современном математическом обеспечении ЭВМ метод Гаусса реализуется с использованием LU-разложения, под которым понимают представление матрицы коэффициентов A в виде произведения A = LU двух матриц L и U, где L – нижняя треугольная матрица, U — верхняя треугольная матрица

Если LU-разложение получено, то решение исходной системы уравнений (2) сводится к последовательному решению двух следующих систем уравнений с треугольными матрицами коэффициентов

линейный алгебраический уравнение численный

где Y = — вектор вспомогательных переменных.

Такой подход позволяет многократно решать системы линейных уравнений с разными правыми частями B. При этом наиболее трудоемкая часть (LU-разложение матрицы A) выполняется только один раз. Эта процедура соответствует прямому ходу метода Гаусса и имеет оценку трудоемкости O(n 3 ). Дальнейшее решение систем уравнений (6) и (7) может выполняться многократно (для различных B), причем решение каждой из них соответствует обратному ходу метода Гаусса и имеет оценку вычислительной сложности O(n 2 ).

Для получения LU-разложения можно воспользоваться следующим алгоритмом.

1. Для исходной системы (1) выполнить прямой ход метода Гаусса и получить систему уравнений треугольного вида (5).

2. Определить элементы матрицы U по правилу

u_ij = C_ij (i = ; j = )