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

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

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

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

Перехід від заданої СЛР Ах = b (А – матриця СЛР) до еквівалентної форми Ф(х) = 0 виконується практично так само, як і для рівняння в розділі. Покладемо С = Е – А, де Е – одинична матриця. Звідси b = Ах = (Е – (Е – А))х = (Е – С)х = х – Сх і отже х = Сх + b. Тут функція Ф(х) = Сх + b є неперервною на відповідному n – вимірному просторі L і визначає деякий ітераційний процес х = Ф(х). Для довільного початкового х₀ Î 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 якої ô a _iiô > . Такі нерівності виконуються, наприклад, для матриць теорії інформації, де діагональні елементи a _ii є ймовірністю правильного кодування повідомлення з номером i, а a _ij з j ¹ i – ймовірності обрання альтернативних помилкових кодів.

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

Справді, нехай d_i = < 1, х = (х₁, х₂, …, х_n) Î L. Тоді для вектора y = Cx маємо = £ = d_i × £ d_i × = d_i × ║x║. Остання нерівність випливає з того, що = 1, а опукла комбінація чисел ôx_jô не перевищує . Якщо покласти 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, тобто виконана умова ô a _iiô > , то скористаємося викладеним вище алгоритмом. Запишемо розширену матрицю даної СЛР в електронну таблицю:

 

	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 _ii:

 

	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: х₀ = 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) визначається з такої системи рівнянь:

a₁₁х_n+11 + a₁₂х_n2 + a₁₃х_n3 + … + a_1mх_nm = b₁,

a₂₁х_n+11 + a₂₂х_n+12 + a₂₃х_n3 + … + a_2mх_nm = b₂, (1)

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

a_m1х_n+11 + a_m2х_n+12 + a_m3х_n+13 + … + a_mmх_n+1m = b_m.

 

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

a₁₁ 0 0 … 0 0 a₁₂ a₁₃ … a_1m

a₂₁ a₂₂ 0 … 0 0 0 a₂₃ … a_2m

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

a_m1 a_m2 a_m3 … a_mm 0 0 0 … 0

 

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

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

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

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

 

 

a₁₁λ a₁₂ a₁₃ … a_1m

a₂₁λ a₂₂λ a₂₃ … a_2m

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

a_m1λ a_m2λ a_m3λ … a_mmλ

 

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

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

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

 

х₂ х₁

 

 

L₁

L₂ L₁

 

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

 

х₂

 

 

L₂

L₁

х₁

Рисунок 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.

 

x₂

 

x₀

 

 

 

Рисунок 4. x₁

 

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

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

 

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

 

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

 

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

 

2. У CЛР

2х₁ – 3х₂ + 4х₃ = 2

х₁ – 2х₂ + х₃ = – 1

3х₁ – х₂ + 2х₃ = 0

 

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

А	Б	В	Г
	– 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ЛР методом простої ітерації.