Знаходження коренів систем лінійних рівнянь методом Гаусса, методом Зейделя та методом простих ітерацій

2

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

Кафедра інформатики

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

Тема: «Знаходження коренів систем лінійних рівнянь методом Гаусса, методом Зейделя та методом простих ітерацій»

з дисципліни “Програмування”

ПОЯСНЮВАЛЬНА ЗАПИСКА

21

Керівник                                                                   Руденко Діана Олександрівна

Студент гр. КІ-09-2                                                 Лещенко Юрій Геннадійович

Харків 2010

ЗА Д А Н И Е

на курсовую работу студента

Лещенко Юрий Геннадиевич

(фамилия, имя, отчество)

1.Тема работы Решение систем линейных уравнений методом Гаусса, методом Зейделя и методом простых итераций.

2. Срок сдачи студентом законченной работы                

3. Исходные данные к работе: Данные по предметной области,  методические указания, ДСТУ 3008-95                                                                  

4. Содержание расчётно-пояснительной записки (перечень подлежащих разработке вопросов) : введение, постановка задачи, теоретические сведения, выводы, список используемых источников, приложение А Текст программы.

5. Перечень графического материала : 3 иллюстраций к курсовой работе.

6. Дата выдачи задания  20.12.2009.

21

21

РЕФЕРАТ

Пояснительная записка: 36 с., 0 рис., 3 рисунка, 3 источника.

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

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

Целью данной работы является получение навыков программирования в интегрированной среде Visual C++ и особенностей синтаксиса языка С++.

              МЕТОД ГАУССА, МЕТОД ЗЕЙДЕЛЯ, МЕТОД ПРОСТЫХ ИТЕРАЦИЙ, VISUAL C++.

21

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…………………………………………………………………………5

1 ПОСТАНОВКА ЗАДАЧИ…………………………………………………......…6

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ………………………………………………......….7

2.1  Разрешимость системы линейных уравнений…………………………7

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

2.3 Метод простых итераций………………………………………………13

2.4 Метод Зейделя…………………………………………………………. 18

ВЫВОДЫ……………………………………………………………………......…21

ПЕРЕЧЕНЬ ССЫЛОК…………………………………………………..….......…22

ПРИЛОЖЕНИЕ А Текст программы...…………………………….……..….. …23

ВВЕДЕНИЕ

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

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

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

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

1 ПОСТАНОВКА ЗАДАЧИ

              В данном курсовом проекте необходимо разработать программу на языке С++, с помощью которой можно находить корни системы линейных алгебраических уравнений.  В частности в данном курсовом проекте используются следующие методы: “Метод Гаусса”, “Метод простых итераций”, “Метод Зейделя”. Для нахождения корней системы необходимо преобразовать матрицу в вид, соответствующий к каждому методу, и аналогично найти необходимое решение.

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу n×n, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.

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

Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.

Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:

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

2.            Δ = 0 и хотя бы один дополнительный определитель Δxi ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных xi, пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений.

2.2 Метод Гаусса – прямой и обратный ход.

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:

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

C2-(a21/a11)*C1,

...

Cm-(am1/a11)*C1,

т.е. Ci-(ai1/a11)*C1, i = 2, 3, ..., m.

Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а11.

В результате получим матрицу:

Т. е. первая строка осталась без изменений, а в столбце под а11 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – aij, где I = j.

Повторим наши элементарные преобразования, но уже для элемента α22.

C1-(a12/α22)*C2,

...

Cm-(αm2/α22)*C2,

т.е. Ci-(αi2/α22)*C2, i = 3, ..., m.

Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α22.

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

Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:

γmn*xn = δm.

Отсюда легко можно найти значение первого корня – xn = δm/γmn.

Подставив это значение в предыдущее m-1-е уравнение, легко получим значение xn-1-ого корня.

Таким образом, поднимаясь до самого верха обратным ходом метода Гаусса, мы последовательно найдем все корни системы уравнений.

Пример 1

Рассмотрим систему уравнений:

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

Δ = [1*(-4)*(-2)+2*2*1+(-1)*(-1)*(-1)]-[1*(-4)*(-1)+2*(-1)*(-2)+2*(-1)*1] = [8+4-1]-[4+4-2] = 11-6 =5,

т. е. Δ ≠ 0.

Т. е. система определена и разрешима. Решим ее по методу Гаусса.

Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:

Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C2-(a21/a11)*C1 = C2-(2/1)*C1 = C2-2*C1:

Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C3-(a31/a11)*C1 = C3-(-1/1)*C1 = C3+C1:

Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C3-(a32/a22)*C2 = C3-(1/-2)*C2 = C3+1/2C2:

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

Эта матрица эквивалентна системе:

Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х3:

-5/2x3 = 3/2,

x3 = (3/2):(-5/2) = 3/2*(-2/5) = -3/5.

Корень x3 = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x2-3x3 = 1):

-2x2-3(-3/5) = 1,

-2x2+9/5 = 1,

-2x2 = 1-9/5,

-2x2 = -4/5,

x2 = (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.

Корень x2 = 2/5 найден. Подставим его и корень х3 в верхнее (первое) уравнение системы (x1-x2+x3 = 0):

x1-2/5+(-3/5) = 0,

x1-5/5 = 0,

x1 = 5/5 = 1.

Проверка:

т. е.

т. е.

и т. д.

Рис.1. Решение методом Гаусса.

Вывод.

Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

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

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

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

2.3 Метод простых итераций.

При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми на ЭВМ прежде всего из-за сложности хранения и обработки матриц большой размерности. В то же время характерной особенностью ряда часто встречающихся в прикладных задачах СЛАУ является разреженность  матриц. Число ненулевых элементов таких матриц мало по сравнению с их размерностью.  Для решения СЛАУ с разреженными матрицами предпочтительнее использовать итерационные методы.