Лабораторная работа 1 решение систем линейных алгебраических уравнений прямыми и итерационными методами


НазваниеЛабораторная работа 1 решение систем линейных алгебраических уравнений прямыми и итерационными методами
страница1/6
Дата публикации11.05.2013
Размер0.59 Mb.
ТипЛабораторная работа
referatdb.ru > Математика > Лабораторная работа
  1   2   3   4   5   6
«УТВЕРЖДАЮ»

зав. кафедрой ИСТ

________О.И.Наранович

Протокол №

от «___»_________2012 г

ЛАБОРАТОРНАЯ РАБОТА 1

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

ПРЯМЫМИ И ИТЕРАЦИОННЫМИ МЕТОДАМИ



Цель: изучить точные и приближенные методы решения систем линейных алгебраических уравнений (СЛАУ), научиться разрабатывать алгоритмы реализации методов решения СЛАУ.
Основные теоретические сведения
Прямые методы решения СЛАУ

Матричный метод

Системой из линейных уравнений с неизвестными называются соотношения вида:




(1.1)


В этой системе — неизвестные, подлежащие определению; — числа, называемые коэффициентами при неизвестных; — числа, называемые свободными членами (или правыми частями).

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

Если система линейных уравнений имеет хотя бы одно решение, то она называется совместной, иначе — несовместной.

Совместная система, имеющая единственное решение, называется определённой, а система, имеющая более одного решения — неопределённой.

Система линейных уравнений имеет очень компактную форму записи в матричном виде.

Составим из коэффициентов системы матрицу:

Определим еще две матрицы:
, ,
тогда систему можно кратко записать в виде матричного уравнения:
.
Рассмотрим частный случай системы, когда число уравнений равно числу неизвестных (), тогда матрица — квадратная. Если , то система имеет единственное решение. Действительно, в этом случае матрица имеет обратную матрицу . Умножим обе части равенства слева на получим . Но , а , следовательно, .

Это и есть формула матричного решения системы линейных уравнений. Выполнив матричные операции в правой части, получим численное решение системы.

Отметим, что — матрица-столбец, и если записана как строка, то при решении по формуле матрицу необходимо транспонировать, и формула матричного решения будет иметь вид:
.


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

Посредством первого уравнения системы (1.1) исключается х1 из последующих уравнений. Далее, посредством второго уравнения, исключается х2 из последующих уравнений и т. д. Этот процесс называется прямым ходом Гаусса. Исключение неизвестных повторяется до тех пор, пока в левой части последнего n-го уравнения не останется одно неизвестное хn


,

(1.2)


где ann и b — коэффициенты, полученные в результате линейных (эквивалентных) преобразований.

Прямой ход реализуется по формулам:


;

,

(1.3)

где m — номер уравнения, из которого исключается xk;

k — номер неизвестного, которое исключается из оставшихся (n k) уравнений, а также обозначает номер уравнения, с помощью которого исключается xk;

i — номер столбца исходной матрицы;

akk — главный (ведущий) элемент матрицы.

Во время счета необходимо следить, чтобы akk  0. В противном случае прибегают к перестановке строк матрицы.

Обратный ход метода Гаусса состоит в последовательном вычислении xn, xn–1, ..., x1, начиная с уравнения (1.2) по алгоритму



.

(1.4)

Точность полученного решения оценивается посредством «невязки» (1.5). В векторе невязки (r1, r2, ..., rn)Т отыскивается максимальный элемент и сравнивается с заданной точностью . Приемлемое решение будет, если rmax < . В противном случае следует применить схему уточнения решения.

Существуют две величины, характеризующие степень отклонения полученного решения от точного, которые появляются в связи с округлением и ограниченностью разрядной сетки ЭВМ, — погрешность  и «невязка» r:




(1.5)

где — вектор решения. Как правило, значения вектора — неизвестны.

Доказано, что если   0, то и r = 0. Обратное утверждение не всегда верно. Однако если система неплохо обусловлена, для оценки точности решения используют невязку r.

Метод Гаусса с выбором главного элемента
В данном случае помимо соблюдения условия akk  0 при реализации формул (1.2—1.4) необходимо, чтобы ведущий (главный) элемент в текущем столбце в процессе преобразований исходной матрицы имел максимальное по модулю значение. Это также достигается перестановкой строк матрицы.

Блок-схема модифицированного метода Гаусса представлена на рисунке 1.1 [11]


Рисунок 1.1 — Блок-схема модифицированного метода Гаусса
Метод прогонки
Метод прогонки также является модификацией метода Гаусса для частного случая разреженных систем — систем с матрицей трехдиагонального типа.

Каноническая форма их записи такова

(1.6)

или в развернутом виде:



(1.7)

При этом, как правило, все коэффициенты bi  0. Метод реализуется в два этапа — прямым и обратным ходами.

Прямой ход. Каждое неизвестное xi выражается через xi+1

xi = Ai xi+1 + Bi для i = 1,2, ..., – 1 (1.8)

посредством прогоночных коэффициентов Ai и Bi. Определим алгоритм их вычисления. Для этого из первого уравнения системы (1.7) находим x1:
.

Из уравнения (1.8) при i = 1 находим x1 = A1 x2 + B1. Следовательно,


.

(1.9)


Из второго уравнения системы (1.7) определяем x2 через x3, подставляя найденное значение x1:
а2 (A1 x2 + B1) + b2 x2 + c2 x3 = d2 ,

откуда




(1.9*)

и согласно уравнению (1.8) при i = 2 x2 = A2x3 + B2 , следовательно:
,

где е2 = а2А1 + b2 .

Ориентируясь на соотношения индексов при коэффициентах уравнений (1.9) и (1.9*), можно получить эти соотношения для общего случая:
,

где еi = аi Аi–1 + bi (= 2,3, ..., – 1) . (1.10)

Обратный ход. Из последнего уравнения системы (1.7) с использованием данных выражения (1.8) при i = n – 1


.

(1.11)

Далее, посредством системы уравнений (1.7) и прогоночных коэффициентов выражений (1.8) и (1.9) последовательно вычисляем xn–1, xn–2, ..., x1.

При реализации метода прогонки нужно учитывать, что при условии
(1.12)

или хотя бы для одного bi имеет место строгое неравенство (1.12), деление на «0» исключается и система имеет единственное решение.

Заметим, что условие (1.12) является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем (1.7) метод прогонки может быть устойчивым и при несоблюдении условия (1.12).

Схема алгоритма метода прогонки может иметь вид, представленный на рисунке 1.2 [11].

Рисунок 1.2 — Блок-схема метода прогонки
Итерационные методы решения СЛАУ
Метод простой итерации
Достоинством итерационных методов является их применимость к плохо обусловленным системам и системам высоких порядков, самоисправляемость и простота реализации на ЭВМ. Итерационные методы для начала вычисления требуют задания какого-либо начального приближения к искомому решению.

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

Для применения метода итераций исходную систему необходимо привести к итерационному виду

(1.13)

и затем итерационный процесс выполнить по рекуррентным формулам:
, k = 0, 1, 2, ... . (1.13*)

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

Для сходимости метода (1.13*) необходимо и достаточно, чтобы |i(G)| < 1, где i(G) — все собственные значения матрицы G. Сходимость будет и в случае, если ||G|| < 1, ибо |i(G)| <  ||G|| ( — любой).

Символ ||...|| означает норму матрицы. При определении ее величины чаще всего останавливаются на проверке двух условий:
||G|| = или ||G|| = , (1.14)
где . Сходимость гарантирована также, если исходная матрица А имеет диагональное преобладание, т. е.
. (1.15)

Когда условия (1.14) или (1.15) выполняются, метод итерации сходится при любом начальном приближении . Чаще всего вектор берут или нулевым, или единичным, или сам вектор из системы (1.13).

Если выполняется условие (1.15), тогда преобразование к итерационному виду (1.13) можно осуществить просто, решая каждое i-е уравнение системы (1.1) относительно xi по следующим рекуррентным формулам:


gij = − aij / aii ; gii = 0; fi = bi / aii , (1.15*)

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

Метод Зейделя
Метод Зейделя является модификацией метода простой итерации и для системы (1.13) имеет следующую технологию:
(1.16)

Суть его состоит в том, что при вычислении очередного приближения в системе (1.16) и в формуле (1.15*), если имеет место соотношение (1.15), вместо используются уже вычисленные ранее , т. е. формула (1.15*) преобразуется к виду
, i = 1, …, n. (1.17)

Это позволяет ускорить сходимость итераций почти в два раза. Оценка точности аналогична методу простой итерации. Схема алгоритма аналогична схеме метода простой итерации, если x0j заменить на xj и убрать строки x0i = 1, x0i = xi.

Решение СЛАУ средствами MathCad




Проверка достаточного условия сходимости метода Зейделя


Достаточное условие выполнено.


Результат работы функции zeid — 10 первых приближений





^ ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
1. Разработайте алгоритмы и решите систему линейных уравнений (Таблица 1.1) методами: a) матричным (MathCad); б) Гаусса с выбором главного элемента; в) простых итераций (MathCad); г) Зейделя. Проанализируйте полученные результаты с точки зрения сходимости (расходимости) метода. Итерационными методами решение задачи найдите с точностью














1

3 12 –1 0

–5 2 0 32

2 0 16 –3

12 3 0 0

18

–15

0

21

16

4 2 32 0

2 30 0 –4

36 0 4 –5

0 0 11 40

–19

39

40

31

2

4 20 1 0

16 2 0 –2

–4 0 4 32

2 0 10 0

24

–13

0

7

17

4 –5 40 0

10 –4 0 50

32 0 4 –4

0 32 0 –9

19

0

34

–49


3

2 16 –3 0

–8 5 0 40

25 0 –2 3

0 –3 20 0

9

98

5

–7

18

9 40 2 0

12 –4 0 96

–4 0 64 8

36 0 0 9

81

119

–15

7

4

5 –2 32 0

4 25 0 –3

20 0 2 –7

0 0 –9 40

27

34

–28

5

19

7 –5 64 0

9 50 0 –4

0 9 –7 80

40 11 0 0

18

0

128

–19

5

–7 2 40 0

9 –5 0 50

25 0 4 –1

0 32 0 9

21

–14

13

21

20

11 64 –2 0

50 3 0 –12

0 13 –9 100

17 0 80 0

–34

0

131

85

6

8 40 –3 0

–7 5 0 50

8 0 64 –11

32 0 0 5

28

0

18

12

21

15 80 –4 0

64 7 0 –5

0 11 –8 128

0 37 100 0

93

131

–34

125

7

–9 4 64 0

10 50 0 –4

0 –14 7 80

40 9 0 0

24

–5

14

29

22

17 100 –9 0

80 –7 0 –5

0 21 128 –4

0 0 19 256

0

–79

139

–54

8

–8 64 5 0

50 –13 0 2

0 17 –9 100

–11 0 80 0

37

38

0

115

23

4 –1 20 0

18 3 0 –2

0 10 1 –1

0 4 0 20

38

–14

15

29

9

–13 80 2 0

64 9 0 –5

0 12 –9 128

0 27 100 0

64

29

0

231

24

3 20 –2 0

5 –4 0 20

0 5 32 –3

12 0 0 3

41

–19

34

29

10

–13 100 9 0

80 10 0 –5

0 –14 128 7

0 0 31 256

–128

34

95

–69

25

4 25 –1 0

6 5 0 40

25 0 3 4

0 –5 30 0

17

0

–34

9

11

1 –2 16 0

10 –1 0 1

0 12 1 –1

0 2 0 16

31

0

–28

29

26

9 –2 36 0

4 25 0 –3

40 0 5 –4

0 0 11 40

19

–18

44

21

12

2 20 –3 0

4 –2 0 24

0 2 16 –1

12 0 0 3

39

0

–25

18

27

9 –2 40 0

11 –3 0 50

30 0 –4 5

0 32 0 8

78

–114

–21

40

13

2 16 –1 0

3 –8 0 60

4 0 24 –3

12 3 0 0

32

–64

0

45

28

2 40 5 0

4 –9 0 72

4 0 64 8

36 0 0 9

42

88

119

54

14

5 –2 40 0

4 32 0 –6

7 0 3 32

20 0 4 0

39

0

21

–19

29

8 –3 64 0

–7 50 0 5

0 12 –9 80

40 9 0 0

131

–84

52

78

15

5 30 –3 0

–8 5 0 40

24 0 3 –4

0 7 25 0

17

31

39

8

30

7 64 –2 0

50 5 0 –8

0 18 5 112

15 0 80 0

111

98

219

–31


УКАЗАНИЕ. Для выполнения достаточного условия сходимости воспользуйтесь перестановкой строк в исходной системе уравнений.

  1   2   3   4   5   6

Похожие рефераты:

Программа пгк по дисциплине «Математика»
Ранг матрицы и методы ее вычисления. Системы линейных алгебраических уравнений. Правило Крамера. Матричная форма записи системы линейных...
Вопросы к вступительному экзамену в аспирантуру по специальности
Однородные системы линейных алгебраических уравнений. Решение систем линейных уравнений с помощью метода Гаусса
Вопросы к вступительному экзамену в аспирантуру по специальности
Однородные системы линейных алгебраических уравнений. Решение систем линейных уравнений с помощью метода Гаусса
Вопросы к вступительному экзамену в аспирантуру по специальности
Однородные системы линейных алгебраических уравнений. Решение систем линейных уравнений с помощью метода Гаусса
Вопросы к вступительному экзамену в аспирантуру по специальности...
Однородные системы линейных алгебраических уравнений. Решение систем линейных уравнений с помощью метода Гаусса
Вопросы к экзамену по дисциплине «Математика» I семестр
Системы линейных алгебраических уравнений. Основные понятия. Методы решения систем при m=n
Вопросы к экзамену по дисциплине «Математика»
Обратная матрица. Матричный метод решения невырожденных систем линейных алгебраических уравнений (слау)
Контрольные вопросы Внимание!!! Некоторые выполняемые коды заданий содержат «ловушки»
Цель: Знакомство с рабочей средой MatLab. Изучение приемов простых вычислений арифметических и алгебраических выражений. Решение...
Разработка и реализация эффективных технологий параллельного решения...
Министерство образования республики беларусь белорусский государственный университет
Программа вступительного экзамена по специальности для поступающих...
Системы линейных алгебраических уравнений. В данной теме вводится понятие системы линейных уравнений, изучаются структура и число...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза