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

Челябинский Юридический Колледж

 

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

по дисциплине «Математические  методы»

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

 

 

 

 

Выполнил:

Студент ПО(Д)-01-10

Кузнецов М.М.

Проверила:

Хабибуллина Н.Р.

 

 

 

 

Челябинск

2012

Оглавление

 

Введение 3

I. Теоретическая часть 4

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

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

1.2. Метод Гаусса с выбором главного элемента

1.3. Оценка погрешности при решении системы линейных уравнений

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

2. Итерационные методы решения систем линейных уравнений

2.1. Метод простой итерации Якоби

2.2. Метод Гаусса-Зейделя

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

2.4. Решение системы линейных уравнений с трехдиаганальной матрицей методом прогонки Томаса

3. Замечания

II. Практическая часть 

Заключение 

Список  литературы 

 

Введение

 

Проблема численного решения  линейных уравнений интересует математиков  уже несколько столетий. Первые математические результаты появились в XVIII веке. В 1750 году Г. Крамер (1704-1752) опубликовал свои труды по детерминантам квадратных матриц и предложил алгоритм нахождения обратной матрицы, известный как правило Крамера. Гаусс в 1809 году опубликовал работу, посвященную движению небесных тел, в которой был изложен метод для решения линейных систем, известный как метод исключения.

В 40-х годах XX века с появлением компьютеров сильно возрос интерес к численным методам. Тогда же началось активное исследование существующих методов для их реализации на ЭВМ и предпринимались активные попытки увеличить их точность.

Вплоть до 80-х годов  решение вычислительных задач было ограничено ресурсами ЭВМ, поэтому  особое значение придавалось экономичности  алгоритмов.

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

Целью данной курсовой является краткое изложение в идейном плане некоторых прямых и итерационных методов решения линейных систем.

 

I. Теоретическая часть

 

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

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

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

 

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

 

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

Для иллюстрации смысла метода Гаусса рассмотрим систему линейных уравнений:

 

     (1)

 

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

 

    (2)

 

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

На первом шаге прямого  хода умножим первое уравнение на и вычтем из второго, тогда исключится переменная из второго уравнения. Затем, умножим первое уравнение на и вычтем из третьего, тогда система (2) преобразуется в систему вида:

   (3)

 

На втором шаге прямого  хода из третьего уравнения исключаем  , т.е. из третьего уравнения вычитаем второе, умноженное, на , что приводит систему (3) к треугольному виду (4)

 

    (4)

 

Систему (4) переписываем в  привычном виде:

 

     (5)

 

Теперь, из системы (5) можем  находить решение в обратном порядке, т.е. сначала находим из третьего уравнения  , далее, подставляя во второе уравнение, находим . Подставляя и в первое уравнение системы (5), находим . Нахождение решения из системы (5) называют обратным ходом.

Теперь, на основе рассмотренного примера, составим общий алгоритм метода Гаусса для системы:

 

   (6)

 

Метод Гаусса состоит из двух этапов:

а) прямой ход – когда  матрица системы (6) приводится к  треугольному виду;

б) обратный ход – когда  последовательно вычисляются неизвестные  в обратном порядке, т.е. в последовательности: .

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

 

   (7)

 

Далее, применяем туже самую  процедуру, для уравнений системы (7), начиная со второго уравнения, т.е. первое уравнение исключается  из «игры». Теперь стараемся обнулить коэффициенты при переменной , начиная с третьего уравнения и т.д., пока не приведём систему к треугольному виду. Если , то система всегда приводима (теоретически) к треугольному виду. Общий алгоритм прямого хода можно представить в виде:

 

     (8)

 

б) Обратный ход: Вычисляем  неизвестные по формулам:

 

    (9)

 

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

     (10)

 

 

1.2. Метод Гаусса  с выбором главного элемента

 

Метод Гаусса настолько универсален, что для некоторых систем получаются практически «плохие» результаты, поэтому  разрабатываются различные хитрые выходы из ситуации. В случае, когда  некоторые коэффициенты матрицы  системы близки между собой, как  известно относительные погрешности  сильно возрастают при вычитании, поэтому  классический метод Гаусса даёт большие  погрешности. Чтобы обойти эту трудность, стараются в прямом ходе Гаусса выбрать  то уравнение, у которого коэффициент  при  максимален и в качестве основного «игрока» выбирают именно это уравнение, тем самым обходя трудности вычитания близких чисел (если это возможно). Далее, когда нужно обнулить все коэффициенты переменной , кроме одного уравнения – этим особым уравнением опять выбирают то уравнение, у которого коэффициент при максимальный и т.д., пока не получим треугольную матрицу.

Обратный ход происходит так же, как и в классическом методе Гаусса.

 

 

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

 

Для того, чтобы понять суть метода Крамера, необходимо знать такие  понятия, как определитель и матрица.

Так как в нашем случае используется определитель 3-го порядка, то введём определение определителя 3-го порядка.

Определителем 3-го порядка  называется число, обозначаемое

 

 a₁₁ a₁₂ a₁₃

a₂₁ a₂₂ a₂₃

a₃₁ a₃₂ a₃₃

 

и равное a₁₁a₂₂a₃₃+a₁₃a₂₂a₃₂+a₁₂a₂₃a₃₁-a₁₃a₂₂a₃₁-a₁₂a₂₁a₃₃-a₁₁a₂₃a_32.

Определитель обозначается Δ.

Матрицей называется таблица, содержащая m строк и n столбцов вида

 

 a₁₁ a₁₂ ..... a_1n

a₂₁ a₂₂ ..... a₁₁

. . . . . .

a_m1 a_m2 ....a_mn

 

где a_ij – элемент матрицы, находящийся в i-той строке и j-ом столбце, где i изменяется от 1 до m, j – от 1 до n, m и n – порядки матрицы. Отсюда вытекает определение системы линейных уравнений.

Система вида a₁₁x₁+a₁₂x₂+.....+a_1nx_n=b₁

 a₂₁x₁+a₂₂x₂+.....+a_2nx_n=b₂

. . . . . . . . . . .

a_m1x₁+a_m2x₂+.....+a_mnx_n=b_m

где a_ij (i изменяется от 1 до m; j – от 1 до n) – коэффициенты при неизвестных x₁, x₂,…., x_n, b_i (i изменяется от 1 до m) – свободные члены, называется системой линейных уравнений.

Теперь непосредственно  перейдём к методу Крамера.

Рассмотрим систему вида

 

 a₁₁x₁+a₁₂x₂+.....+a_1nx_n=b₁

 a₂₁x₁+a₂₂x₂+.....+a_2nx_n=b₂

. . . . . . . . . . .

a_m1x₁+a_m2x₂+.....+a_mnx_n=b_m

 

Назовём данную систему “система 1”.

Умножим 1-е уравнение  системы 1 на А₁₁. Умножим 2-е уравнение системы 1 на А₂₁. Умножим n-е уравнение системы 1 на А_n1. Сложим полученные уравнения:

 

(a₁₁А₁₁+a₂₁А₂₁+….+a_n1А_n1)x₁+(a₁₂А₁₂+a₂₂А₂₁+....+a_n1А_n1)x₁+....+(a_1nА₁₁+a_2nА₂₁+ +....+a_nnА_n1)x_n=b₁А₁₁+b₂А₂₁+....+b_nА_n1

 

detA x₁=detA₁,

 

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

 

detA x₂=detA₂,

 

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

 

detA x_n=detA_n,

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

Если обозначим Δ=detA, то получим

 

 Δ x₁=Δ₁

 Δ x₂=Δ₂

. . . .

 Δ x_n=Δ_n

 

где Δ_i – определитель, полученный из определителя Δ заменой i-го столбца столбцом свободных членов системы 1.

Назовём данную систему “система 2”.

Рассмотрим 3 случая:

1) Если в системе 2 Δ≠0, то x₁=Δ₁/Δ, x₂=Δ₂/Δ, ….. , x_n=Δ_n/Δ. Полученные формулы называются формулами Крамера.

2) Если в системе 2 Δ=0 и все Δ_i=0 для любого i, изменяющегося от 1 до n, то система имеет бесчисленное множество решений.

3)Если в системе 2 Δ=0 и существует Δ_i≠0, то решения системы 2 не существуют.

 

 

 

1.4. Оценка погрешности при решении системы линейных уравнений

 

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

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

 

     (11)

 

(Евклидова норма)   (12)

 

(Чебышевская норма) (13)

 

Для всякой нормы векторов можно ввести соответствующую норму  матриц:

 

    (14)

 

которая согласована с  нормой векторов в том смысле, что

 

     (15)

 

Можно показать, что для  трёх приведённых выше случаев нормы  матрицы  задаются формулами:

      (16)

 

      (17)

 

      (18)

 

Здесь - являются сингулярными числами матрицы , т.е. это положительные значения квадратных корней - матрицы (которая является положительно-определённой матрицей, при ).

Для вещественных симметричных матриц - где - собственные числа матрицы .

Абсолютная погрешность  решения системы:

 

      (19)

 

где - матрица системы, - матрица правых частей, оценивается нормой:

 

      (20)

 

Относительная погрешность  оценивается по формуле:

 

      (21)

где .

 

2. Итерационные  методы решения систем линейных  уравнений

 

Рассмотрим систему линейных уравнений, которая плохо решается методами Гаусса. Перепишем систему  уравнений в виде:

 

      (22)

 

где - заданная числовая матрица -го порядка, - заданный постоянный вектор.

 

2.1 Метод простой  итерации Якоби

 

Этот метод состоит  в следующем: выбирается произвольный вектор (начальное приближение) и строится итерационная последовательность векторов по формуле:

 

,     (23)

 

Приведём теорему, дающую достаточное условие сходимости метода Якоби.

Теорема. Если , то система уравнений (22) имеет единственное решение и итерации (23) сходятся к решению.

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

       (24)

 

Строим алгоритм решения:

а) переписываем уравнение (24) в однородном виде и умножаем на постоянную - которую далее найдём из условий сходимости итерационного процесса:

 

      (25)

 

б) добавляем  к обеим частям (25) и получаем:

 

     (26)

 

в) строим итерационную формулу  Якоби:

 

     (27)

 

где постоянную находим из условий сходимости итерационного процесса (27), который в данном случае имеет вид:

 

      (28)

 

где - вектор-функция из (26) или исходя из теоремы о сжатых отображениях , где - единичная матрица.

Рассмотрим числовой пример:

Пусть имеем систему уравнений:

Переписываем систему  в виде:

 

 

Составляем итерационную формулу:

 

 

Коэффициент выбираем из условий: , т.е.

 

.

 

2.2 Метод Гаусса-Зейделя

 

Для решения линейной системы  уравнений разработано множество  итерационных методов. Тем более, что  метод простой итерации Якоби  сходится медленно. Одним из таких  методов является метод Гаусса-Зейделя.

Для иллюстрации метода рассмотрим числовой пример:

      (29)

 

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