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

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

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

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

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

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

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

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

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

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

Выполнил:

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

Юшин Андрей

Проверила:

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

Абакан, 2013

Задание

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

 (1)

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

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

Решение

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

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

Пусть  (ведущий элемент). Первое уравнение системы (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-ой:

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

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

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

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

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

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

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

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

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

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

= -6.67 - (2.56x2 + 1.58x3 - 1.12x4)= -4.23 - (0.83x3 + 0.24x4)= -5 - (3.2x4)= 0.71

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

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

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

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

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

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

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

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

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

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

 (4)

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

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

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

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

В(0) =; Х(0) =

В(1) =

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

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

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

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

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

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

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

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

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

,

где , , .

 (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):

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

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