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

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

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

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

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

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

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

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

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

студенты 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-го порядка). Если коэффициенты уравнений и свободные члены представляют собой лишь приближённые значения каких-либо измеряемых величин или округляются в процессе вычислений, то использование формул Крамера может привести к большим ошибкам и в ряде случаев является нецелесообразным.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

  Метод Гаусса

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

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

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

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

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

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

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

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

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

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

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

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

  Рассмотрим  систему линейных уравнений с  вещественными коэффициентами, записанную в матричном виде: АХ = F.

  Предполагая однозначную разрешимость системы, заменим матричное уравнение 

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

  при произвольном выборе «нулевого» приближения.

  Метод  итерации  заключается в замене точного решения  системы-ой итераций с достаточно большим номером . Оценим погрешность   метода простой итерации.

  Отсюда  вытекает следующее матричное уравнение  для погрешности 

  ,

  где - единичная матрица порядка n. 

  Введем  в рассмотрение норму вектора  в пространстве Е^п и операторную норму квадратной матрицы порядка n. Как обычно, назовем нормой вектора X число ||X||, равное корню квадратному из суммы квадратов координат этого вектора. Назовем операторной нормой произвольной матрицы А число , равное либо точной верхней грани отношения на множестве всех ненулевых векторов X, либо (что то же самое) точной верхней грани норм на множестве всех векторов X, имеющих норму, равную единице.

  Итак, по определению 

  Напомним, что для любой симметричной матрицы  A операторная норма этой матрицы равна наибольшему по модулю собственному значению этой матрицы. 
 

  Из  вытекает следующее неравенство, справедливое для любой матрицы А и любого вектора X: 
 

  Из  матричного уравнения для погрешности  и из неравенства 
мы получим, что для любого номера k 
 

  Теорема: Для того чтобы итерационная последовательность при любом выборе нулевого приближения Х₀ и при данном значении параметра сходилась к точному решению X системы , достаточно, чтобы было выполнено условие 

  При этом последовательность сходится со скоростью геометрической  прогрессии со знаменателем 

  В случае, если матрица  А является симметричной, это условие является и необходимым условием сходимости итерационной последовательности при любом выборе нулевого приближения Х₀.

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

  Пусть задана -точность, с которой нам требуется получить точное решение системы. Требуется найти итерацию X_к с таким номером к, для которого  

    Из условия  вытекает, что , и, стало быть выполняется при , т. е. при .

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

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

  Минимум функции  достигается для значения , где ₁ и ₂ — соответственно минимальное и максимальное собственные значения матрицы А, причем минимальное значение функции равно

  . 

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

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

  Рассмотрим  систему линейных уравнений с вещественными коэффициентами, записанную в матричной виде: АХ = F.

  Заменим итерационную последовательность более  общей итерационной последовательностью, определяемой соотношением:

  В ((Х_к+1 - Х_к ) /()) + АХ_к =F.

  в котором В представляет собой некоторую «легко обратимую» квадратную матрицу n-го порядка, а - стационарный параметр. Такой метод составления итерационной последовательности и называется неявным методом простой итерации. Явный метод простой итерации получается из неявного метода в частном случае В =  Е, где Е —единичная матрица порядка п.

  Матрица А называется положительно определенной, если (АХ, X) > 0 для любого ненулевого вектора X. Необходимым и достаточным условием положительной определенности симметричной матрицы А (или, что то же самое, самосопряженного линейного оператора А) является положительность всех собственных значений этой матрицы (этого оператора).

  Если  матрица А является положительно определенной, то А > 0, В > А (или А <<В) в случае, если В — А > 0 (т. е. если матрица В—А является положительно определенной).

  Теорема: Пусть матрица А является симметричной и выполнены условия А > 0,

  В > 0 (симметричность матрицы В, вообще говоря, предполагается) .

  Тогда для того чтобы  итерационная последовательность, определяемая соотношением

  В ((Х_к+1 - Х_к ) /()) + АХ_к =F

  при любом выборе нулевого приближения Х₀ сходилась к точному решению X системы АХ = F достаточно, чтобы были выполнены условия

  2В>,>0

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

  Для оценки скорости сходимости неявного метода простой итерации введём энергетическую норму вектора Х, положив её равной _в = и обозначим _в.

  Энергетическая  норма вектора Х и его обычная  норма эквивалентны. Эта эквивалентность  обычной и энергетической норм можно  утверждать, что последовательность ||Х_к|| сходится к нулю тогда и только тогда, когда сходится к нулю последовательность ||Х_к||_в.

  Теорема: Пусть матрицы А и В симметричны и положительно определены, Z_к обозначает погрешность общего неявного метода простой итерации. Тогда, для того чтобы при было справедливо неравенство  ||Z_к||_в < ^к ||Z₀||_в  достаточно,  чтобы  было выполнено условие 

    В В 

  Основной  задачей является выбор такого параметра , при котором скорость сходимости является максимальной. Из неравенства ||Z_к||_в < ^к ||Z₀||_в  вытекает, что эта задача сводится к нахождения такого значения , при котором достигается минимальное значение функции .

  Так как обе матрицы А и В симметричны и положительно определены, то существуют положительные постоянные ₁ и ₂ такие, что справедливы неравенства ₁В < А < ₂В. Будем считать, что постоянные ₁ и ₂ в этих неравенствах нам заданы. Сопоставляя написанные неравенства с условием В В, мы получим, что минимальное значение   достигается при условии ₁, ₂ откуда получаем, оптимальное значение ₁+₂) и минимальное значение , равное

  (₂ - ₁) / (₂ + ₁). 
 
 
 
 
 

  Метод Зейделя

  Представим  симметричную матрицу А в виде суммы трёх матриц А=D+L+U, где

    D-диагональная матрица, а L и U-строго левая и строго правая  матрицы удовлетворяющие условию L`=U.

  Метод Зейделя получается из общего неявного метода простой итерации в том  частном случае, когда стационарный параметр равен единице, а матрица В равна сумме D + L. Таким образом, последовательные итерации в методе Зейделя определяются соотношением

  (D + L) (Х_к+1 - Хк) + AX_к = F.