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

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

Государственное образовательное  учреждение высшего

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

«Нижегородский  государственный  университет им. Н. И. Лобачевского» 

Механико-математический факультет

Кафедра математического  моделирования экономических  систем 
 

«Численные  методы решения систем линейных уравнений» 
 
 

Исполнители:

студенты 3 курса

Воробьёва А.В.

Резников  М.А.

Сидоренко Д.В.

Научный руководитель: 

Тюхтина А.А. 
 
 
 

Нижний  Новгород, 2011 год

 

Содержание

1. Ведение………………………………………………………………....................................2

2. Цели и  задачи………………………………………………………………………………..4

3. Методы  решения систем линейных уравнений………………….…………………...….5

1. Прямые  методы решения…………………………………………………………...5

1. Матричный метод…………………………………………………………..5

2. Метод Крамера……………………………………………………………...6

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

2. Итерационные  методы решения………………………………………………….11

1. Метод простой  итерации (метод Якоби)…………………………………11

2. Общий неявный метод простой итерации……………………………….14

3. Метод Зейделя…………………………………………………………….16

4. Метод верхней релаксации………………………………………………..18

5. Метод П.Л. Чебышева……………………………………………………..20

4. Методы решения систем линейных уравнений в приложении MATLAB………………………………………………………………………………….....23

5.  Методы решения систем линейных уравнений в приложении MAPLE…………………………………………………………………………………………..26

6. Заключение………………………………………………………………………………….29

7. Литература…………………………………………………………………………………30

 

  Введение

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

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

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

  Дадим несколько определений.

  Система m линейных уравнений с n неизвестными (или, линейная система) в линейной алгебре — это система уравнений вида

  Здесь x₁, x₂, …, x_n — неизвестные, которые надо определить.

    a₁₁, a₁₂, …, a_mn — коэффициенты системы, а b₁, b₂, … b_m — свободные члены, которые предполагаются известными.

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

  

  или: Ax = B.

 

 

   Система называется однородной, если все  её свободные члены равны нулю ( ), иначе — неоднородной.

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

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

  Совместная  система вида  может иметь одно или более решений.

  Совместная  система вида  называется определенной, если она имеет единственное решение; если же у нее есть хотя бы два  различных решения, то она называется неопределенной. Если уравнений больше, чем неизвестных, она называется переопределённой. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Цели  и задачи

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

  Задачи: изучить различные методы решения систем линейных уравнений с вещественными коэффициентами.   

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

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

  Пусть дана система линейных уравнений  с n неизвестными:

  

  Тогда её можно переписать в матричной  форме:

  AX = B, где A — основная матрица системы, B и X — столбцы свободных членов и решений системы соответственно:

  

  Умножим это матричное уравнение слева  на A ^{− 1} — матрицу, обратную к матрице A:

  Так как A ^{− 1}A = E, получаем X = A ^{− 1}B. Правая часть этого уравнения даст столбец решений исходной системы. Условием применимости данного метода (как и вообще существования решения неоднородной системы линейных уравнений с числом уравнений, равным числу неизвестных) является невырожденность матрицы A. Необходимым и достаточным условием этого является неравенство нулю определителя матрицы A:

   .

  Для однородной системы линейных уравнений, то есть когда вектор B = 0, действительно обратное правило: система AX = 0 имеет нетривиальное (то есть ненулевое) решение, только если det A = 0.  
 
 
 

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

  Метод Крамера (правило  Крамера) — способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно). Назван по имени Габриэля Крамера (1704–1752), придумавшего метод.

  При решении систем линейных уравнений  по методу Крамера последовательно  выполняется следующий алгоритм:

  1. Записывают систему в матричном  виде (если это еще не сделано).

  2. Вычисляют главный определитель системы. Если главный определитель системы не равен нулю, то существует и притом единственное решение, определяемое формулами Крамера: 

  где - определитель матрицы, полученной из матрицы А заменой -го столбца на столбец свободных членов системы.

  3. Вычисляют все дополнительные определители системы. В главном определителе системы заменяют поочередно столбцы коэффициентов при x₁, x₂,..., x_n на столбец свободных членов, получаем n дополнительных определителей (для каждого из n неизвестных). Находят значения всех неизвестных по формулам Крамера для решения системы n линейных уравнений с n неизвестными. 

  Общий пример:

  Система линейных уравнений:

  

  Определители:

    

  

  Решение:

    

  Основное  значение формул Крамера состоит  в том, что они дают явное выражение  для решения квадратной системы  линейных уравнений (с определителем, отличным от нуля) через коэффициенты уравнений и свободные члены. Практическое применение формул Крамера  связано с довольно громоздкими  вычислениями (для решения системы  n уравнений с n неизвестными приходится вычислять (n+1) определитель n-го порядка). Если коэффициенты уравнений и свободные члены представляют собой лишь приближённые значения каких-либо измеряемых величин или округляются в процессе вычислений, то использование формул Крамера может привести к большим ошибкам и в ряде случаев является нецелесообразным.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Метод Гаусса

  Алгоритм  решения  систем линейных алгебраических уравнений методом Гаусса подразделяется на два этапа:

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

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

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

Преобразуем полученную систему при этом первое уравнение не будем трогать совсем.

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