37861

РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ

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

Математика и математический анализ

Множина чисел яка перетворює кожне з рівнянь системи на тотожність називається розв’язком системи. Методи виключення Гаусса Методи виключення Гаусса послідовного виключення змінних ґрунтуються на ідеї еквівалентного перетворення зведення вихідної системи до трикутного вигляду прямий хід і подальшого її розв’язання зворотний хід. Поділивши перше рівняння системи 3. Тоді поділивши на нього перше рівняння системи 3.

Украинкский

2013-09-25

566 KB

2 чел.

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

РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ

Мета роботи – дослідити прямі та ітераційні методи розв’язання систем лінійних алгебраїчних рівнянь.

3.1. Короткі теоретичні відомості

Система лінійних алгебраїчних рівнянь (СЛАР) з  невідомими має вигляд

         (3.1)

...

,

де  ­ невідомі;  ­ коефіцієнти;     ­ вільні члени.

Множина чисел {}, яка перетворює кожне з рівнянь системи на тотожність, називається розв’язком системи.

У матричному вигляді систему (3.1) записують як

,

де  ­  матриця коефіцієнтів; Х – вектор-стовпець невідомих;  ­  вектор-стовпець вільних членів.

Розрізняють прямі або точні методи розв’язання СЛАР, які дозволяють одержати розв’язок за скінченну кількість алгебраїчних дій, та ітераційні, в яких розв’язок одержують як границю послідовних наближень, які обчислюють за деякою однаковою схемою.

З першої групи методів у цій роботі розглядаються три модифікації методу виключення Гаусса – схема єдиного поділу, виключення Гаусса-Жордана та схема з вибором головного елемента. З другої – метод простої ітерації та метод ітерації Зейделя.

3.1.1. Методи виключення Гаусса

Методи виключення Гаусса (послідовного виключення змінних) ґрунтуються на ідеї еквівалентного перетворення (зведення) вихідної системи до трикутного вигляду (прямий хід) і подальшого її розв’язання (зворотний хід).

Схема єдиного поділу.  Розглянемо СЛАР 3-го порядку:

;

 ;                 (3.2)

 .

Верхній індекс вказує номер кроку перетворення коефіцієнтів.

Припустимо, що  (головний елемент першого рядка). Поділивши перше рівняння системи (3.2) на , матимемо

                                   ,                   (3.3)

де   (j = 2, 3, 4). Якщо тепер рівняння (3.3) послідовно множити на   (i = 2, 3) і віднімати його з другого та третього рівнянь, коефіцієнти при  у двох останніх рівняннях дорівнюватимуть 0, тобто змінну  буде виключено з них. Перетворені рівняння матимуть вигляд

                    ;

            ,          (3.4)

                             

де  ( i = 2, 3; j = 2, 3, 4).

Припустимо, що головний елемент другого рядка також не є нулем. Тоді, поділивши на нього перше рівняння системи (3.4), отримаємо  

                                       ,                    (3.5)

де   (j = 3, 4). Виключимо тепер невідоме , помноживши (3.5) на  і віднявши його з другого рівняння системи (3.4).

Внаслідок цього дістанемо

           ,           (3.6)

де   (j = 3, 4).

Нарешті, якщо , то поділивши на нього рівняння (3.6), отримаємо

                       ,           (3.7)

де .

Об’єднаємо тепер рівняння (3.3), (3.5) та (3.7) у систему з трикутною матрицею, що еквівалентна вихідній системі:

                   ;

                               ;              (3.8)

                                            .

З останньої системи невідомі  можуть бути одержані у зворотному порядку:

                             ;

                             ;              (3.9)

                             .

Процес зведення системи (3.2) до трикутного вигляду називають прямим, а визначення невідомих за формулами (3.9) ­ зворотним ходом.

З а у в а ж е н н я. Головні елементи, які отримують при прямому ході, дають можливість обчислити головний визначник матриці коефіцієнтів вихідної системи:

.

Недоліком розглянутої схеми є те, що в ході реалізації прямого ходу один з головних елементів може виявитися рівним нулю, а це робить неможливим отримання розв’язку СЛАР; тоді як система може бути сумісною і мати єдиний розв’язок. Крім того, аналіз похибок показує, що при виконанні прямого ходу похибка тим менша, чим більший . Ці обставини враховуються при реалізації схеми з вибором головного елемента.

Bиключення Гаусса-Жордана. Ідея методу полягає в тому, щоб за допомогою послідовного виключення змінних звести матрицю коефіцієнтів вихідної системи до одиничної матриці. При цьому відпадає необхідність у зворотному ході.

Розглянемо СЛАР 3-го порядку:

                                                          (3.10)

                                

Верхній індекс вказує номер кроку перетворення коефіцієнтів.

Припустимо, що  (головний елемент першого рядка). Поділивши перший рядок (3.10) на , матимемо

                 (3.11)

де  (j = 2, 3, 4). Якщо тепер перше рівняння системи (3.11) послідовно множити на  і віднімати його з другого та третього рівнянь, коефіцієнти при  у двох останніх рівняннях дорівнюватимуть 0, тобто змінну  буде виключено з них. Перетворені рівняння матимуть вигляд

         (3.12)

,

де  (i = 2, 3;  j = 2, 3, 4).

Припустимо, що головний елемент другого рядка також не є нулем, тобто  0. Тоді, поділивши на нього другий рядок системи (3.12), отримаємо

     

                                                                         (3.13)

                 

де ,  . Якщо тепер друге рівняння системи (3.13) послідовно множити на  та  і віднімати його з першого та третього рівнянь, коефіцієнти при  у першому й третьому рівняннях дорівнюватимуть 0, тобто змінну буде виключено з них. Перетворені рівняння матимуть вигляд

 

                     

                               (3.14)

                      ,

де  , ,.

Нарешті, якщо , то поділивши на нього третій рядок системи (3.14), отримаємо

                             

                                     (3.15)

                         ,

де (j = 3,4).

Якщо тепер третє рівняння системи (3.15) послідовно множити на  і віднімати його з першого та другого рівнянь, коефіцієнти при  у першому й другому рівняннях дорівнюватимуть 0, тобто змінну буде виключено з них.

Перетворені рівняння матимуть вигляд

 

                                             

                                                      (3.16)

                                        ,

де ,  .

Як наслідок, розв'язок вихідної системи (3.10) отримуємо безпосередньо з (3.16), а саме

    ,           ,

Схема з вибором головного елемента.  В обох розглянутих вище методах у випадку, якщо черговий головний елемент дорівнює нулю, подальше перетворення матриці стає неможливим. Втім, це ще не означає, що система несумісна і не має єдиного розв’язку. Цей недолік відсутній у схемі з вибором головного елемента. Крім того, ця схема менш чутлива до помилок округлення.

 Отже, маємо систему

Розглянемо розширену матрицю  з коефіцієнтів системи й вільних членів

Виберемо ненульовий і найбільший за модулем коефіцієнт,  що не належить до стовпця вільних членів , й обчислимо множники

 ,

Рядок з номером  матриці  називається головним рядком. Далі до кожного неголовного рядка i додамо головний, помножений на відповідний множник . Як наслідок, отримаємо матрицю, в якій р-й стовпець складається з нулів (за винятком ) . Відкидаючи цей стовпець і головний рядок, одержимо матрицю  з меншою на одиницю кількістю рядків і стовпців.

З матриці  таким самим чином отримаємо  і т.д.:

,

де остання матриця є двочленною матрицею-рядком; її також вважаємо головним рядком. Для визначення невідомих  об’єднуємо в систему всі головні рядки, починаючи з останнього –.

Далі невідомі обчислюють з трикутної матриці – так само як у схемі єдиного поділу. Після відповідної зміни нумерації невідомих отримуємо розв’язок вихідної системи.

Метод завжди приводить до розв’язку, якщо головний визначник системи не дорівнює нулю:

.

3.1.2. Ітераційні методи

Метод простої ітерації. Нехай задана СЛАР виду (3.1). Припустивши, що діагональні елементи системи відмінні від нуля, перетворимо її до вигляду

;

;

                            (3.17)

,

де ,  , при  та  при , .

Систему (3.17) розв’яжемо методом послідовних наближень, вибравши, наприклад, як нульове наближення вектор β:

, .

Чергове наближення отримаємо у вигляді

                ;

                ;                 (3.18)  

     

                

Якщо послідовність наближень  має границю, то ця границя є розв’язком системи.

Достатньою умовою збіжності системи (3.17) є виконання принаймні  однієї з умов:

1)   ;

або           (3.19)

2)   ,

причому процес ітерації збігається до єдиного розв’язку незалежно від вибору початкового наближення. З (3.19) випливає, що метод простої ітерації забезпечує збіжність, якщо ), тобто модулі діагональних коефіцієнтів для кожного рівняння більші за суму модулів решти коефіцієнтів (без урахування вільних членів).

Зрозуміло, що далеко не кожна система відповідає зазначеним вимогам. Але кожна система, головний визначник якої не дорівнює нулю, може бути зведена до вигляду, де ці умови виконуються.

Робиться це так. Із заданої системи вилучають рівняння з коефіцієнтами, модулі яких більші за суму модулів решти коефіцієнтів рівняння. Кожне виділене рівняння записують у такий рядок нової системи, щоб найбільший за модулем коефіцієнт став діагональним.

З решти невикористаних виділених рівнянь системи утворюють лінійно незалежні комбінації так, щоб нові рівняння відповідали (3.19), і кожне невикористане ще рівняння потрапило б принаймні в одну лінійну комбінацію, яка є рівнянням нової системи.

П р и к л а д. Підготувати до розв’язання методом простої ітерації систему

  (1)    

  (2)         

  (3)      

Зведемо систему до вигляду, придатного для ітерації:

 

  

             

              

Метод ітерації Зейделя. Основна ідея методу полягає в тому, що при обчисленні (k + 1)-го наближення невідомого xi враховуються вже раніше обчислені (k +1)-і наближення x1(k+1), x2(k+1), …xi-1(k+1). Вважаючи, що k-і наближення xj(k) (j = 1,2,…i) коренів відомі, будемо обчислювати

(k + 1)-е наближення за формулами

         n

   x1(k+1) = β1 +    α1j xj(k)

            j=1

                 n

   x2(k+1) = β2 + α21 x1(k+1) +  α2j xj(k)

                      j=2

       i–1                          n

   xi(k+1) = βi +  αij xj(k+1) + αij xj(k)

        j=1                        j=i

        n–1

   xn(k+1) = βn +  αnj xj(k+1) + αnn xn(k)

          j=1   

k = 0, 1, 2, …, n

Достатні умови збіжності ітерації Зейделя визначаються наступною теоремою.

Т е о р е м а. Якщо для лінійної системи

                                                  x = αx + β                           (3.20)

виконується умова

|| α ||m < 1,  

де , то процес ітерації Зейделя для системи (3.20) збігається до єдиного розв’язку при будь-якому виборі початкового вектора X(0).

Наведена теорема про збіжність справедлива й для простої ітерації. Як правило, метод Зейделя дає кращу збіжність, ніж метод простої ітерації. Процес Зейделя може збігатися, навіть коли проста ітерація не є збіжною. Хоча можливі й винятки.

 Оцінка точності отриманих наближень. Для обох методів може бути застосована оцінка точності отриманого наближення з використанням m-норми матриці α. Якщо в процесі обчислень буде виявлено, що

, де q = || α || < 1 ,

то || X – X(k) || ≤  , де || α || є m–нормою матриці α:

Існує можливість знаходження необхідної кількості ітерацій для досягнення заданої точності

.

При цьому вважається, що початковим наближенням  було вибрано      вектор .

3.2. Завдання для лабораторної роботи

Розв’язати СЛАР (відповідно до варіанту, табл. 3.1) одним прямим й одним ітераційним методом. Для визначення методів номер залікової книжки поділити за модулем 6:

0 – схема єдиного поділу, метод ітерації Зейделя;

1 – виключення Гаусса-Жордана,  метод простої ітерації;

2 – схема з вибором головного елемента,  метод простої ітерації;

3 – схема з вибором головного елемента,  метод ітерації Зейделя;

4 – виключення Гаусса-Жордана,  метод ітерації Зейделя;

5 – схема єдиного поділу,  метод простої ітерації.

Звіт про лабораторну роботу має містити вихідний текст програми, таблицю з результатами та висновки.

3.3. Контрольні запитання та завдання

  1.  Що таке прямий та зворотний хід у методі Гаусса?
  2.  Наведіть оцінку обчислювальної складності схеми єдиного поділу.
  3.  Що є головним недоліком схеми єдиного поділу?
  4.  У чому полягає ідея виключення Гаусса-Жордана?
  5.  Які переваги має схема з вибором головного елемента?
  6.  У чому полягає сутність методу простої ітерації?
  7.  Наведіть оцінку обчислювальної складності методу простої ітерації.
  8.  Якими є умови збіжності методу простої ітерації?
  9.  Наведіть оцінку точності отримуваного наближення у методі простої ітерації.
  10.   У чому полягає відмінність ітерації Зейделя від простої ітерації?

             3.4. Глосарій

Система лінійних алгебраїчних рівнянь System of linear equations (or linear

system)

Прямі або точні методи    Direct (Forward) methods

Ітераційні методи     Iterative methods

Схема єдиного поділу    Gaussian elimination

Перетворення (зведення) вихідної   Bringing a matrix to row echelon form

системи до трикутного вигляду

Прямий хід      Direct elimination

Зворотний хід     Backward substitution (backsubstitution)

Головний елемент рядка    Pivot or pivot element

Схема з вибором головного елемента Complete pivoting

Метод простої ітерації    Direct iteration

Метод ітерації Зейделя    Gauss–Seidel method

3.5. Біографічна довідка

Карл Фрідріх Га́усс (Carl Friedrich Gauß; 1777 – 1855) – видатний німецький математик, астроном і фізик, вважається одним з найвидатніших математиків усіх часів.

З ім'ям Гаусса пов'язані фундаментальні дослідження майже у всіх галузях математики: алгебрі, диференціальній і неевклідовій геометрії, в математичному аналізі, теорії функцій комплексної змінної, теорії ймовірностей, а також в астрономії, геодезії та механіці. У кожній галузі глибина опрацювання матеріалу, сміливість думки й важливість результату були настільки вражаючими, що Гаусса називали „королем математиків“.

Наприклад, хоча Гаусс і не першим відкрив поширений у природі нормальний закон розподілу, але він настільки ретельно його дослідив, що графік розподілу з того часу часто називають гауссіаною.

У фізиці Гаусс заклав основи математичної теорії електромагнетизму, розвинув теорію  капілярності, теорію системи лінз.

Філіп Людвіг Зéйдель (Philipp Ludwig von Seidel, 1821 – 1896) – німецький математик і астроном. У галузі математики праці Зейделя стосуються, головним чином, теорії рядів та інших нескінченних форм. В астрономії відомий своїми дослідженнями про силу світла (яскравість) нерухомих зірок.

Вільгельм Жóрдан (Wilhelm Jordan, 1842 – 1899) – німецький геодезист, засновник німецького геодезичного журналу. У середовищі математиків він відомий як співавтор методу виключення Гаусса-Жордана. Цей метод був викладений ним у третьому виданні його підручника з геодезії (Handbuch der Vermessungskunde, 1888).

Не слід ототожнювати Вільгельма Жóрдана ні з відомим французьким математиком Каміллом Жордáном, ні з німецьким фізиком  Паскалем Жóрданом.

Таблиця 3.1

Варіанти завдань для лабораторної роботи 3

Варіант

Матриця коефіцієнтів

Стовпець вільних членів

Варіант

Матриця коефіцієнтів

Стовпець вільних членів

1

2

3

4

5

6

1

10

4

20

19

37

2

8

4

8

20

148

1

30

18

10

71

8

27

12

6

87

16

4

26

5

29

16

13

46

16

157

1

10

12

16

37

19

10

17

17

169

3

9

11

11

12

214

4

3

7

6

0

63

12

24

2

9

186

13

49

20

15

353

20

4

41

16

470

20

19

50

10

437

7

13

9

3

140

17

7

17

17

225

продовження табл. 3.1

1

2

3

4

5

6

5

6

12

20

15

155

6

14

19

15

4

180

15

42

17

9

275

17

33

5

10

208

1

16

22

4

158

11

6

28

10

230

10

2

17

7

103

6

19

3

13

149

7

2

13

16

9

96

8

12

6

2

16

148

4

31

18

8

125

20

56

18

17

218

18

9

36

8

213

18

0

34

15

230

20

8

7

7

130

2

5

17

17

144

9

11

14

5

8

98

10

13

12

3

16

242

3

38

18

16

108

0

28

17

10

279

18

4

32

9

185

9

1

14

3

111

12

9

13

4

111

10

14

3

0

143

11

6

3

11

17

155

12

10

2

0

19

44

0

16

5

10

161

2

24

7

14

114

11

5

25

8

147

10

14

29

4

108

5

5

11

15

151

20

13

3

8

61

13

15

8

19

7

69

14

3

19

11

8

149

15

41

16

9

76

9

31

3

18

257

0

3

20

16

100

11

7

32

13

143

15

7

8

18

113

12

19

12

5

144

15

2

11

13

15

33

16

3

2

8

3

35

12

38

18

7

114

17

51

13

20

407

20

1

27

5

3

0

3

7

3

28

15

2

15

5

6

16

4

20

16

124


17

7

8

13

6

138

18

14

7

18

12

139

18

49

11

19

418

3

38

20

14

222

11

7

27

8

211

0

7

19

11

111

2

15

8

19

172

1

18

6

3

83

19

15

12

18

14

209

20

13

14

17

14

146

18

36

10

7

301

9

26

7

9

135

1

5

10

3

94

8

4

24

11

119

19

2

13

9

118

15

11

5

16

109

21

11

5

1

20

75

22

10

11

14

3

128

19

57

19

18

437

12

45

17

15

325

6

10

33

16

117

9

16

31

5

240

15

14

5

14

149

0

4

17

15

120


продовження табл. 3.1

1

2

3

4

5

6

23

10

5

5

16

72

24

20

20

20

0

180

19

38

18

0

76

16

37

14

6

163

16

19

53

17

98

18

6

33

8

218

10

14

14

4

48

16

9

14

13

142

25

19

15

7

1

95

26

19

19

16

4

111

0

13

1

11

133

8

31

16

6

56

16

13

31

1

83

9

16

37

11

82

12

17

15

1

107

10

9

1

16

51

27

7

8

10

17

173

28

2

1

2

9

13

19

3

7

4

138

16

48

15

16

46

8

8

17

0

134

1

4

12

18

42

8

0

20

5

177

10

7

36

18

90

29

11

2

15

10

154

30

16

7

14

5

174

16

43

8

18

336

17

25

6

1

211

1

9

17

6

122

20

2

27

4

224

0

3

16

7

90

5

15

11

11

151

PAGE   \* MERGEFORMAT 33


 

А также другие работы, которые могут Вас заинтересовать

55509. Групи слів за значенням: синоніми, антоніми. Синоніми. Типи синонімів. Синонімічні ряди. Антоніми 65.5 KB
  Групи слів за значенням: синоніми антоніми. Антоніми. Мета: поглибити знання про групи слів за значенням; формувати вміння визначати в реченнях і текстах синоніми і антоніми; учити утворювати синонімічні ряди і добирати антонімічні пари доречно вживати їх у мовленні...
55510. Розробка заняття з інформатики на тему "Використання сортування, фільтрації даних, робота з підсумками, перевіркою даних, захистом листів" з використанням інтерактивних методів та програми Radmin 383 KB
  Цілеспрямований розвиток індивідуальності можливий лише тоді, коли теорія освіти не декларуватиме необхідність творчості педагога і творчості студента, а систематично за допомогою доцільних методів втілюватиме її у навчально-виховному процесі.
55511. Чтобы радость людям дарить, надо добрым и вежливым быть 59.5 KB
  Дорогие ребята! Весь учебный год наш класс работал на маршруте «Путешествие в страну Вежливых». Мы продолжаем наше путешествие. И сегодня остановка на станции «Доброта». Девиз (читают с доски): «Чтобы радость людям дарить, надо добрым и вежливым быть»
55512. Щедра осінь 506 KB
  Вчити бачити красу рідного краю, виразно читати вірші. Розвивати усне мовлення, збагачувати словниковий запас, розвивати спостережливість, естетичні смаки, творчі здібності. Виховувати любов до природи, праці, шанобливе ставлення до хліба, повагу до традицій рідного краю