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

Федеральное агентство железнодорожного транспорта

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

высшего профессионального образования

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

ОмГУПС (ОмИИТ)

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

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

Тематический реферат

ИНМВ. 800008. 000 ТР

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

Омск 2015

Реферат

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

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

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

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

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

Содержание

Введение. 3

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

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

Введение

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

НЕ нашли? Не то? Что вы ищете?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Виды систем:

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

Пример:

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

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

Пример:

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

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

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

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

Пример:

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

Пример:

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

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

$\begin{pmatrix}a_{11}$

или: Ax = b

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

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

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

Методы решения:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Условия:

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

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

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

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

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

Условия: .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание метода:

$\mathrm{A}=\begin{bmatrix}a_{11}$ Пусть дана СЛАУ вида: AX = B , где:

$\left\{$ Предполагая, что $a_{ii}$ не равно 0, $i = \overline{1,n}$ , выразим через первое уравнение, — через второе и т. д.

$\frac{b_i}{a_{ii}$ $\alpha=\begin{bmatrix}\alpha_{11}$ Обозначим:

В матричном виде получим: $X = \beta + \alpha x$

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

$\begin{bmatrix}x_1^{(0)} \\ \vdots \\ x_n^{(0)}\end{bmatrix} = \begin{bmatrix}\beta_1 \\ \vdots \\ \beta_n\end{bmatrix}$

Первое приближение:

$\begin{bmatrix}x_1^{(1)} \\ \vdots \\ x_n^{(1)}\end{bmatrix} = \begin{bmatrix}\beta_1 \\ \vdots \\ \beta_n\end{bmatrix} + \begin{bmatrix}\alpha_{11} & \cdots & \alpha_{1n} \\ \vdots & \ddots & \vdots \\ \alpha_{n1} & \cdots & \alpha_{nn}\end{bmatrix} \begin{bmatrix}x_1^{(0)} \\ \vdots \\ x_n^{(0)}\end{bmatrix}$

Второе приближение:

$\begin{bmatrix}x_1^{(2)} \\ \vdots \\ x_n^{(2)}\end{bmatrix} = \begin{bmatrix}\beta_1 \\ \vdots \\ \beta_n\end{bmatrix} + \begin{bmatrix}\alpha_{11} & \cdots & \alpha_{1n} \\ \vdots & \ddots & \vdots \\ \alpha_{n1} & \cdots & \alpha_{nn}\end{bmatrix} \begin{bmatrix}x_1^{(1)} \\ \vdots \\ x_n^{(1)}\end{bmatrix}$

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

$X^{(k)}=\beta+\alpha X^{(k-1)}$ , $k =1, 2, \dots$

$X=\lim_{k\to\infty}X^{(k)}$ Тогда, — решение системы.

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

Условия сходимости: $\sum_{j=1}^n\vert\alpha_{ij}\vert<1$ (где $i=1,2,\dots,n$ ), аналогично со строками.

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 с.

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

Введение

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

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

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

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

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

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

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

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

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

Заключение

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

Домашний очаг

Справочная информация

Техника

Общество

Образование и наука

Мир

Бизнес и финансы