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

Размещено на http://www.allbest.ru/

Минобрнауки России

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

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

"Хакасский государственный университет им. Н.Ф. Катанова"

Институт информационных технологий и инженерного образования

Кафедра информационных систем и технологий

Лабораторная работа №3

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

Выполнил:

Студент группы 41

Юшин Андрей

Проверила:

Молчанова Е.А.

Абакан, 2013

Задание

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

(1)

1. Решить систему уравнений с точностью =0.001 методом Гаусса с минимизацией невязки и методом простых итераций.

2. Найти для матрицы коэффициентов определитель.



Решение

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

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

Пусть (ведущий элемент). Первое уравнение системы (1) оставим без изменения, а из второго уравнения вычтем первое уравнение, домноженное на , получим:

где

Такие же преобразования проделаем с третьим и четвертым уравнением:

(2)



Проводя аналогичные преобразования с целью исключения , где n=4, приведем систему к треугольному виду:

(3)

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

Значение переменной х4 определяется из четвертого уравнения:



Подставив полученное значение в третье уравнение системы (3), можно найти значение х3, а затем из второго и первого уравнений можно найти значения переменных х2 и х1 соответственно

Таким образом, решение системы распадается на два этапа:

1. Прямой ход: приведение системы (2) к треугольному виду.

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

Воспользовавшись данным методом, найдем значения переменных для системы уравнений (1).

Запишем систему в виде расширенной матрицы:

Для удобства вычислений поменяем строки местами:

Работаем со столбцом №1

Умножим 3-ую строку на (m= -2.51 / 5.77 = -0.435) и добавим к 4-ой:



7.42	19.03	11.75	-8.32	-49.49
6.36	11.75	10	3.64	-41.7
5.77	7.42	6.36	-2.69	-27.67
0	-12.868	-10.687	-3.12	54.427

Умножим 2-ую строку на (m= -5.77 / 6.36 = -0.907) и добавим к 3-ой:

7.42	19.03	11.75	-8.32	-49.49
6.36	11.75	10	3.64	-41.7
0	-3.24	-2.712	-5.992	10.162
0	-12.868	-10.687	-3.12	54.427

Умножим 1-ую строку на (m = -6.36 / 7.42 = -0.857) и добавим к 2-ой:

7.42	19.03	11.75	-8.32	-49.49
0	-4.561	-0.0714	10.771	0.72
0	-3.24	-2.712	-5.992	10.162
0	-12.868	-10.687	-3.12	54.427

Для удобства вычислений поменяем строки местами:

Работаем со столбцом №2

Умножим 3-ую строку на (m = -3.24 / 4.561 = -0.71) и добавим к 4-ой:

7.42	19.03	11.75	-8.32	-49.49
0	-12.868	-10.687	-3.12	54.427
0	-4.561	-0.0714	10.771	0.72
0	0	-2.662	-13.643	9.65



Умножим 2-ую строку на (m = -4.561 / 12.868 = -0.354) и добавим к 3-ой:

7.42	19.03	11.75	-8.32	-49.49
0	-12.868	-10.687	-3.12	54.427
0	0	3.717	11.877	-18.573
0	0	-2.662	-13.643	9.65

Работаем со столбцом №3

Умножим 3-ую строку на (m = 2.662 / 3.717 = 0.716) и добавим к 4-ой:

7.42	19.03	11.75	-8.32	-49.49
0	-12.868	-10.687	-3.12	54.427
0	0	3.717	11.877	-18.573
0	0	0	-5.138	-3.65

Получим единицы на главной диагонали. Для этого всю строку делим на соответствующий элемент главной диагонали:

Теперь исходную систему можно записать как:

x1 = -6.67 - (2.56x2 + 1.58x3 - 1.12x4)

x2 = -4.23 - (0.83x3 + 0.24x4)

x3 = -5 - (3.2x4)

x4 = 0.71

Из 4-ой строки выражаем x4

Из 3-ой строки выражаем x3

2

Из 2-ой строки выражаем x2

4

Из 1-ой строки выражаем x1

1

Метод минимизации невязки

Обозначим через приближенное решение системы уравнений, полученное методом Гаусса. Подставим это приближенное решение в систему и вычислим правые части :

Так как отличаются от истинного значения, то и , будут отличаться от .

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



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

Подставим в систему вместо столбца свободных членов столбец невязок, а вместо переменных хi - неизвестные поправки:

(4)

Решая эту систему, получаем значения и новое приближенное решение системы:

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

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

Применяя данный метод найдем новые значения переменных в соответствии с заданной точностью =0.001 и полученными поправками:



В(0) =; Х(0) =

В(1) =

Получим невязки:

Подставляем эти невязки в столбец свободных членов

Решая данную систему методом получим погрешность:



Тогда по формуле найдем значения переменных с учетом погрешности:

уравнение гаусс матрица невязка

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

Укрупненная блок-схема метода представлена в приложении 1

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

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

,

где , , .

Предположим, что диагональные элементы матриц A исходной системы не равны 0 (aii ? 0, i = 1, 2, …, n). Разрешим первое уравнение системы относительно x1, второе относительно x2 и т.д. Получим следующую эквивалентную систему, записанную в скалярном виде:



(4),

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

(5)

Аналогично находятся следующие приближения , где в (5) вместо необходимо подставить .

Или в общем случае:

. (3)

или



Условие окончания итерационного процесса

.

Достаточное условие сходимости: Если выполнено условие диагонального преобладания, т.е.

,

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

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

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

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

,

|6.36|<|11.75|+|10|+|3.64|

|19.03|<|7.42|+|11.75|+|-8.32|

|6.36|<|5.77|+|7.42|+|-2.69|

|-4.29|<|2.51|+|-9.64|+|-7.92|

Условие не выполняется, но процесс итераций может все таки сойтись, для того чтобы это проверить приводим приводим систему уравнений к виду (4):

В качестве начального приближения возьмем значения

Все расчеты сведем в таблицу.

N	x1	x2	x3	x4	e1	e2	e3	e4
0	0	0	0	0
1	-5.08	-3.16	-4.43	1.41	5.08	3.16	4.43	1.41
2	6.57	2.06	2.55	-6.2	1.5	-1.1	-1.88	4.79
3	-14.79	-8.26	-11.26	8.2	8.22	6.2	8.72	1.99
4	27.18	11.46	15.16	-19.3	12.39	3.2	3.89	11.1
5	-53.04	-26.66	-35.9	33.94	25.86	15.2	20.74	14.64
6	102.04	46.7	62.35	-68.41	49	20.04	26.46	34.47
7	-196.36	-94.71	-127.05	128.98	94.32	48.01	64.7	60.57
8	378.91	177.71	237.8	-251.19	182.56	82.99	110.75	122.22
9	-729.23	-347.22	-465.26	481.42	350.32	169.51	227.46	230.23
10	1406.12	664.17	889.3	-930.06	676.88	316.95	424.04	448.64
11	-2708.03	-1284.56	-1720.68	1789.61	1301.91	620.39	831.37	859.55
12	5219.1	2470.17	3308.08	-3450.49	2511.07	1185.61	1587.41	1660.88
13	-10054.49	-4764.3	-6381.2	6646.01	4835.4	2294.14	3073.11	3195.52
14	19374.2	9174.82	12287.72	-12807.52	9319.71	4410.51	5906.52	6161.51
15	-37327.88	-17682.57	-23682.91	24674.87	17953.68	8507.76	11395.19	11867.35
16	71923.7	34065.29	45623.97	-47544.82	34595.83	16382.72	21941.05	22869.95
17	-138578.26	-65640.62	-87914.07	91605.52	66654.56	31575.33	42290.1	44060.69
18	267009.39	126469.16	169382.18	-176504.32	128431.13	60828.53	81468.11	84898.81

Производя итерации я убедился что процесс не сходиться и данный метод к этой системе неприменим!.

Нахождение методом Гаусса определителя матрицы

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

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

,

или, подробнее

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

Т.о., определитель исходной матрицы равен произведению диагональных элементов верхней треугольной матрицы.

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



Тогда определить матрицы будет равен произведению диагональных элементов :

В нашем случае определитель равен



Приложение. Блок-схема метода минимизации невязок

Размещено на Allbest.ru