Метод простої ітерації для СЛР



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Метод простої ітерації для СЛР



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

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

В ітераційних методах (або методах послідовних наближень) завжди формують послідовність хn наближень, де кожне наступне обчислюється з попередніх за певним (рекурентним) правилом; наближення хn збігаються до точного значення розв’язку. Але ж найчастіше в таких методах рівняння чи систему рівнянь F(x) = 0 замінюють еквівалентним х = Ф(х), де Ф(х) – деяка неперервна функція на множині W допустимих значень F. Далі обирають початкове наближення х0 Î W і послідовно обчислюють наступні наближення: хk = Ф(хk-1), k = 1,2,… . Якщо послідовність хk має границю х*, тобто = х*, то ця границя буде розв’язком рівняння х = Ф(х). Справді, х* = хk = Ф(хk-1) = Ф( хk-1) = Ф(х*). Для кожної функції Ф(х) отримуємо свій ітераційний метод, який іноді називають стаціонарним або методом простої ітерації.

Перехід від заданої СЛР Ах = b (А – матриця СЛР) до еквівалентної форми Ф(х) = 0 виконується практично так само, як і для рівняння в розділі . Покладемо С = Е – А, де Е – одинична матриця. Звідси b = Ах = (Е – (Е – А))х = (Е – С)х = х – Сх і отже х = Сх + b. Тут функція Ф(х) = Сх + b є неперервною на відповідному n – вимірному просторі L і визначає деякий ітераційний процес х = Ф(х). Для довільного початкового х0 Î L послідовність наближень хk = Ф(хk-1), k = 1,2,… буде збігатися до границі х*, якщо Ф(х) є стискуючим відображенням (за принцип стискуючих відображень Банаха: теорема 4 розділу ). За означенням, Ф(х) є стискуючим, якщо для деякої норми ║ ║ на L і деякого числа q < 1 виконується нерівність ║Ф(х) – Ф(х')║ < q║x - x'║ при довільних х, х' Î L, звідки ║Ф(х) – Ф(х')║ = ║(Сх + b) – (Cx' + b)║ = ║Cx – Cx'║ = ║C(x – x')║ < q║x - x'║ (тобто якщо ║С║ < q). Тоді будуть виконуватись і всі наслідки принципу стискуючих відображень, у тому числі й оцінки похибок (теорема 6 розділу ). Така норма ║ ║ та таке число q знайдуться завжди за умовою, що спектральний радіус С (тобто максимум модулів власних значень цієї матриці) не перевищує одиниці. Природним прикладом СЛР, де можна скористатися такою умовою є система Ах = b, для матриці системи A якої ôaiiô > . Такі нерівності виконуються, наприклад, для матриць теорії інформації, де діагональні елементи aii є ймовірністю правильного кодування повідомлення з номером i, а aij з j ¹ i – ймовірності обрання альтернативних помилкових кодів.

Якщо такі нерівності виконуються для СЛР Aх = b, то поділимо кожне рівняння цієї системи на aii. Тоді для матриці А' отриманої еквівалентної системи А'х = b' діагональні елементи дорівнюють 1, для матриці С = Е – А' діагональні елементи дорівнюють нулю, а суми модулів недіагональних елементів < 1. Як і вище, СЛР А'х = b' еквівалентна рівності х = Ф(х) = Сх + b'. У якості норми в L візьмемо максимум модулів координат вектора: ║х║ = max ôxjô. Тоді для деякого числа q < 1 ║Сx║ < q║x║ при кожному х Î L, що означає: Ф – стискуюче відображення, а ітераційний процес хk = Ф(хk-1), k = 1, 2, … завжди буде збігатися при довільному х0 Î L.

Справді, нехай di = < 1, х = (х1, х2, … , хn) Î L. Тоді для вектора y = Cx маємо = £ = di × £ di × = di × ║x║. Остання нерівність випливає з того, що = 1, а опукла комбінація чисел ôxjô не перевищує . Якщо покласти q = < 1, то отримуємо ║Cx║ = ║у║ = £ q ×║x║, що й потрібно.

Задача 1.Розв’язати CЛР методом простої ітерації.

 

Розв’язання.Оскільки 3,9 > 1,25 + 0,98 , 3,45 > 0,74 + 0,84 , 2,38 > 0,65 + 1,18 , тобто виконана умова ôaiiô > , то скористаємося викладеним вище алгоритмом. Запишемо розширену матрицю даної СЛР в електронну таблицю:

 

  A B C D
3,9 1,25 -0,98 4,905
0,74 3,45 -0,84 6,031
-0,65 1,18 2,38 10,134

 

Поділимо кожний рядок цієї матриці на aii:

 

  A B C D
=A1/$A$1 ® ® ®
  =В2/$В$2 ® ®
    =С3/$С$3 ®

 

В результаті отримаємо матрицю системи А' для СЛР А'х = b', еквівалентної даній.

 

  A B C D
0,320513 -0,25128 1,257692
0,214493 -0,24348 1,748116
-0,27311 0,495798 4,257983

 

Наступним кроком знайдемо матрицю С = Е – А'. Для цього спочатку помножимо А' на – 1

 

  A B C
= – А5 ® ®
¯ ® ®
¯ ® ®

отримавши

  A B C
-1 -0,32051 0,251282
-0,21449 -1 0,243478
0,273109 -0,4958 -1

 

а потім додамо одиничну матрицю: фактично ж задамо 0 замість – 1 у її діагональних елементах:

  A B C
-0,32051 0,251282
-0,21449 0,243478
0,273109 -0,4958

Тепер застосуємо ітераційний процес хk = Ф(хk-1), k = 1, 2, … , де Ф(х) = Сх + b'; за початкове наближення візьмемо b', яке знаходиться в діапазоні D5:D7: х0 = b'. Cпочатку розташуємо вектор b' у горизонтальному діапазоні А16:С16, тобто транспонуємо його за допомогою відповідного вбудованого оператора Excel. Для цього виділимо цей діапазон і задамо там оператор ТРАНСП(D5:D7). У наступному рядку задамо формули ітераційного процесу хk = Схk-1 + b':

А17 = $А$16 + СУММПРОИЗВ($А$12:$С$12;А16:С16);

В17 = $В$16 + СУММПРОИЗВ($А$13:$С$13;А16:С16);

С17 = $С$16 + СУММПРОИЗВ($А$14:$С$14;А16:С16).

У наступні рядки стовпців А, В, С ці формули треба копіювати (тобто протягувати). В результаті дістанемо:

  A B C
1,257692 1,748116 4,257983
1,767353 2,515076 3,734758
1,390056 2,278364 3,493693
1,40535 2,300597 3,508011
1,401822 2,300803 3,501165
1,400035 2,299893 3,500099
1,400059 2,300017 3,500063
1,40001 2,300003 3,500008
1,400001 2,3 3,500002
1,4 2,3 3,5
1,4 2,3 3,5

 

У правильності отриманого розв’язку тут можна переконатись безпосередньою перевіркою:

  D
= СУММПРОИЗВ($А$26:$С$26;A1:C1)
¯
¯

звідки

  D
Проверка
4,905002
6,031
10,134

 

Метод Зейделя

Спочатку розглянемо метод Зейделя. Нехай задано СЛР Ах = b, де всі діагональні елементи відмінні від нуля. Якщо у m – вимірному просторі наближення хn = (хn1, хn2, …, хnm), то наступне наближення хn+1 = (хn+11, хn+12, …, хn+1m) визначається з такої системи рівнянь:

a11хn+11 + a12хn2 + a13хn3 + … + a1mхnm = b1,

a21хn+11 + a22хn+12 + a23хn3 + … + a2mхnm = b2, (1)

……………………………………………

am1хn+11 + am2хn+12 + am3хn+13 + … + ammхn+1m = bm.

 

Цю систему можна записати у вигляді Вхn+1 + Схn = b, де

a11 0 0 … 0 0 a12 a13 … a1m

a21 a22 0 … 0 0 0 a23 … a2m

В = ………………. , С = ………………. .

am1 am2 am3 … amm 0 0 0 … 0

 

Звідси отримуємо хn+1 = – В-1Схn + В-1b. Отже, метод Зейделя є еквівалентним деякому методу простої ітерації. Звідси, зокрема, для його збіжності необхідно й достатньо, щоб всі власні значення матриці В-1С по модулю були менше 1. Оскільки ║– В-1С – λE║ =

║ В-1║×║C + λB║, то власні значення матриці В-1С є коренями рівняння ║C + λB║ = 0.

Отже, необхідна й достатня умова збіжності методу Зейделя формулюється так:

всі корені рівняння

 

 

a11λ a12 a13 … a1m

a21λ a22λ a23 … a2m

……………………. = 0.

am1λ am2λ am3λ … ammλ

 

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

Теорема 1. Нехай для всіх і £ qôaiiô, де q < 1, х* – точний розв’язок СЛР Ах = b. Тоді ║xn – x*║1 £ q║xn+1 – x*║1 .

Задача розв’язання СЛР є модельною для більш складної задачі розв’язання систем нелінійних рівнянь і знаходження екстремуму функції багатьох змінних. Для перенесення методу Зейделя на ці більш складні задачі важливо зрозуміти найбільш загальні, якісні причини його збіжності, що можна здійснити за допомогою геометричної інтерпретації методу. Позначимо через Li площину = bi . При отримані наближення (хn+11 ; хn+12; … ; хn+1i-1 ; хn+1i ; … ; хn+1m) з наближення (хn+11 ; хn+12 ; … ; хn+1i-1 ; хni ; … ; хn+1m) згідно з (1) наближення переміщується паралельно вісі хi до перетину з площиною Li. Отже, метод Зейделя геометрично складається з циклічних переміщень паралельно координатним осям хi до перетину з площинами Li. Наступні рисунки ілюструють при m = 2 випадки, коли метод Зейделя збігається, розбігається або має цикл.

 

х2 х1

       
   
 
 

 

 


L1

 
 


L2 L1

 

       
   
 
 


Рисунок 1. х1 Рисунок 2. х1

 

х2

 

 


L2

L1

х1

Рисунок 3.

 

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

Нехай А – дійсна, симетрична, додатне визначена матриця. Тоді метод Зейделя є еквівалентним задачі мінімізації функції F(y) = (A(y – x*), y – x*) – (Ax*, x*).

Справді, для симетричної А маємо

F(y) = (A(y – x*), y – x*) – (Ax*, x*) = (Ay, y) – 2(Ax*, y) = (Ay, y) – 2(b, y).

Якщо А додатне визначена, то (A(y – x*), y – x*) > 0 за y ¹ x* і тому функція F(y) має мінімум, причому єдиний при y = x*. Отже, задача знаходження мінімуму функції F(y) рівносильна розв’язуванню рівняння Ах = b.

 

x2

 


x0

 

 
 

 


 

 
 


Рисунок 4. x1

 

Одним з методів мінімізації функції багатьох змінних є метод покоординатного спуску. Нехай маємо наближення ( , , …, ) до точки екстремуму функції F(х1 , х2 , … , хm). Розглянемо функцію F(х1 , , …, ), як функцію змінної х1 і знайдемо точку її мінімуму. Потім, виходячи з наближення ( , , …, ), шляхом мінімізації функції F( , х2 , , …, ), знаходимо наступне наближення ( , , , …, ). Цей процес циклічно повторюється. При уточненні компоненти хk виконується зміщення по прямій, паралельній вісі хk до точки з найменшім на цій прямій значенням F(х) = с. Очевидно, ця точка буде точкою дотику розглянутої прямої та лінії рівня F(х) = с. Тому у двовимірному випадку картина виглядає так, як на попередньому рисунку.

Застосуємо метод покоординатного спуску для знаходження екстремуму функції F. Позначимо F(y) + (Ax*, x*) = (A(y – x*), y – x*) через F0(y). При мінімізації по змінній хk виконується зміщення по прямій, паралельній вісі хk до точки, де = 0. Нове значення хk визначається з рівняння = 2 ( – bj) = 0, саме того ж, що у методі Зейделя. Отже, наближення покоординатного спуску мінімізації F і методу Зейделя розв’язання початкової СЛР співпадають. Можна довести, що при пошуку мінімуму функції F таким чином метод Зейделя завжди буде збігатись.

 

Питання, тести

 

1. У які з m рівнянь CЛР треба підставити упорядковану сукупність n чисел, щоб довести, що вона є розв’язком цієї системи ?

 

А у перше з них
Б у довільне рівняння
В у всі рівняння
Г у достатню кількість рівнянь

 

2. У CЛР

1 – 3х2 + 4х3 = 2

х1 – 2х2 + х3 = – 1

1 – х2 + 2х3 = 0

 

коефіцієнт а23 дорівнює

А Б В Г
– 1 – 2

 

3. Елементарні операції над СЛР – це

А Переміна місцями двох рівнянь
Б Переміна місцями двох змінних
В Множення обох частин рівняння на деяке число
Г Множення обох частин рівняння на деяке число, відмінне від нуля
Д Додавання до обох частин деякого рівняння відповідних частин іншого рівняння, помножених на число
Е Віднімання від обох частин деякого рівняння відповідних частин іншого рівняння, помножених на число

 

 

4. СЛР може мати таку кількість розв’язків

А Б В Г
безліч

 

5. В результаті кроку методу Гаусса отримаємо СЛР, у якій у порівнянні з СЛР, отриманій на попередньому кроці

 

А на одну змінну менше при тій же кількості рівнянь
Б на одне рівняння менше при тій же кількості змінних
В на одне рівняння та на одну змінну менше
Г на одну змінну менше та на одне рівняння більше

 

6. Результатом методу Гаусса є зведення даної СЛР до рівносильної їй системи

 

А трикутної форми
Б діагональної форми
В форми, що залежить від модифікації методу
Г форми, що залежить від ходу методу (прямого чи зворотного)

 

  1. Нехай задана СЛР . Матриця цієї системи – це

А:

  A B C D
3,9 1,25 -0,98 4,905
0,74 3,45 -0,84 6,031
-0,65 1,18 2,38 10,134

Б:

  A B C D
4,905 3,9 1,25 -0,98
6,031 0,74 3,45 -0,84
10,134 -0,65 1,18 2,38

В:

  A B C
3,9 1,25 -0,98
0,74 3,45 -0,84
-0,65 1,18 2,38

Г:

  A B C
1,25 -0,98 4,905
3,45 -0,84 6,031
1,18 2,38 10,134

 

  1. Розширена матриця даної СЛР задана такою таблицею:
  A B C D
x1 x2 x3 b
3,9 1,25 -0,98 4,905
0,74 3,45 -0,84 6,031
-0,65 1,18 2,38 10,134

 

Тоді перший крок алгоритму Гаусса реалізує така електронна таблиця:

А:

  A B C D
= A2/$A$2
= A3 – A6*A3
= A4 – A6*A4

 

Б:

  A B C D
= A2/$A$2
= A3 – A6*$A$3
= A4 – A6*$A$4

В:

  A B C D
= A2/$A$2
= A3 – A2*A3
= A4 – A6*A4

Г:

  A B C D
= A2/$A$2
= A3 – A2*$A$3
= A4 – A6*$A$4

 

  1. В результаті алгоритму Гаусса отримана така розширена матриця:

 

  A B C D
1,4
2,3
3,5

 

Тоді розв’язком даної СЛР є

А Б В Г
  розв’язок не є визначеним

 

  1. Дана розширена матриця деякої СЛР:

 

  A B C D Е
-2 -2
-3 -2 -2
-1 -1

 

Тоді це система трьох лінійних рівнянь з

 

А Б В Г
двома змінними трьома змінними чотирма змінними кількість змінних не є визначеною

 

  1. Розширена матриця даної СЛР задана такою таблицею:
  A B C D Е
x1 x2 x3 x4 b
-2 -2
-3 -2 -2
-1 -1

 

Тоді останній крок алгоритму Гаусса реалізує така електронна таблиця:

А:

  A B C D E
= C10 – C16*C10
= C11 – C16*C11
= C12/$C$12

Б:

  A B C D E
= C10 – C16*$C$10
= C11 – C16*$C$11
= C12/$C$12

В:

  A B C D E
= D10 – D16*$D$10
= D11 – D16*$D$11
= D12/$D$12

Г:

  A B C D E
= D10 – D16*D10
= D11 – D16*D11
= D12/$D$12

 

 

  1. В результаті алгоритму Гаусса отримана така розширена матриця:

 

  A B C D Е
0,04 -0,68
0,6 0,8
-0,28 1,76

 

Тоді загальним розв’язком даної СЛР є

А Б В Г

 

  1. В результаті алгоритму Гаусса отримана така розширена матриця:

 

  A B C D
1 7/12
1 1/3
- 1/12
5 1/3

 

Тоді загальним розв’язком даної СЛР є

 

А Б В Г
  розв’язку не існує

 

  1. Наступна СЛР методом Гаусса зведена до такої діагональної форми:

 

-0,5 6,5
-0,5 -1,5

 

Скільки розв’язків має дана система?

А Б В Г
безліч

 

  1. Нехай числа 3, – 5, – 2 задані у чарунках А1, А4, А7 відповідно; матриці

, і у діапазонах А2:С3, А5:С6, А8:С9 відповідно так, як указано в наступній таблиці

  A B C
   
-5
-5    
-3 -8 -5
-2
-2    
-2

Тоді для підрахунків матриці X = у діапазоні А11:С12 можна використати таку таблицю:

А:

  A B C
= $А$1*А2+$А$4*А5+$А$7*А8 ® ®
¯ ® ®

Б:

  A B C
= $А$1*А2–$А$4*А5–$А$7*А8 ® ®
¯ ® ®

В:

  A B C
=А1*А2–А4*А5–А7*А8 ® ®
¯ ® ®

 

 

Г:

  A B C
=3*A2–5*A5–2*A8 ® ®
¯ ® ®

 

  1. Добуток матриці у діапазоні А1:В3 на матрицю у діапазоні D1:D3 – це

 

А Б В Г Д
3 ´ 2 матриця 2 ´ 3 матриця 3 ´ 3 матриця 2 ´ 2 матриця такої матриці не існує

 

  1. Нехай А – 3 ´ 3 матриця, А = , АЕ – 3 ´ 6 матриця,

АЕ = . Зведемо матрицю АЕ до діагональної форми методом Гаусса: вона дістане вигляд ЕВ = , де В – деяка 3 ´ 3 матриця. Нехай Е – діагональна 3 ´ 3 матриця, Е = . Тоді

А Б В Г Д
А × В = Е В × А = Е В = А-1 А = В-1 матриці А × В не існує

 

18. Задамо в електронній таблиці матрицю

 

  A B C D E F
4,05 -0,93 -0,41
1,18 3,78 -0,87
-0,96 -1,02 3,68

 

Зведемо цю матрицю до діагональної форми методом Гаусса:

 

0,236737 0,069816 0,042881
-0,06376 0,263775 0,055257
0,044086 0,091324 0,298241

Тоді для матриць А = у діапазоні А1:С3 і В у діапазоні D13:F15

А Б В Г Д
А × В = Е В × А = Е В = А-1 А = В-1 матриці А × В не існує

 

19. Точними методами є

А метод Гаусса розв’язання СЛР
Б метод Ньютона розв’язання рівняння з одною змінною
В Знаходження коренів квадратного рівняння за формулою
Г Знаходження числа, оберненого до числа 1 + λ за формулою (1 + λ)-1 = 1 – λ

 

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

А метод Гаусса розв’язання СЛР
Б метод Ньютона розв’язання рівняння з одною змінною
В Знаходження коренів квадратного рівняння за формулою
Г Знаходження числа, оберненого до числа 1 + λ за формулою (1 + λ)-1 = 1 – λ

 

  1. Нехай 3 ´ 3 матриця С знаходиться в діапазоні А12:С14; вектор b у діапазоні А16:С16 (у А15:С15 нульові значення).

Тоді ітераційний процес хk = Схk-1 + b (k = 1, 2, … ) визначається такими формулами

А:

А17 = $А$16 + СУММПРОИЗВ($А$12:$С$12;А16:С16);

В17 = $В$16 + СУММПРОИЗВ($А$13:$С$13;А16:С16);

С17 = $С$16 + СУММПРОИЗВ($А$14:$С$14;А16:С16).

У наступні рядки стовпців А, В, С ці формули треба копіювати.

Б:

А17 = А16 + СУММПРОИЗВ($А$12:$С$12;А16:С16);

В17 = В16 + СУММПРОИЗВ($А$13:$С$13;А16:С16);

С17 = С16 + СУММПРОИЗВ($А$14:$С$14;А16:С16).

У наступні рядки стовпців А, В, С ці формули треба копіювати.

В:

А17 = $А$16 + СУММПРОИЗВ($А$12:$С$12;А15:С15);

В17 = $В$16 + СУММПРОИЗВ($А$13:$С$13;А15:С15);

С17 = $С$16 + СУММПРОИЗВ($А$14:$С$14;А15:С15).

У наступні рядки стовпців А, В, С ці формули треба копіювати.

Г:

А17 = $А$16 + СУММПРОИЗВ(А12:С12;А16:С16);

В17 = $В$16 + СУММПРОИЗВ(А13:С13;А16:С16);

С17 = $С$16 + СУММПРОИЗВ(А14:С14;А16:С16).

У наступні рядки стовпців А, В, С ці формули треба копіювати.

 

Завдання

 

1. Розв’язати СЛР методом Гаусса.

2. Знайти матрицю X = × – 5 × , використавши вбудовані оператори Excel.

3. Знайти матрицю, обернену до матриці А = методом Гаусса.

4. Розв’язати СЛР матричним методом, використавши вбудовані оператори Excel.

5. Розв’язати CЛР методом простої ітерації.

 

 



Последнее изменение этой страницы: 2016-04-23; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.192.21.182 (0.04 с.)