Інтераційний метод Гаусса-Зейделя.

Сутність даного методу викладемо для СЛАР (2.3). Припустимо, що тоді:

 

(2.25)

(2.26)

(2.27)

Нехай () – деякий грубо наближений розв’язок системи. Назвемо цю сукупність чисел початковим наближенням. За початкове наближення можна взяти нульові значення змінних чи значенням вільних членів .

Підставивши обчисленні значення у рівняння (2.25-2.27) маємо:

(2.28)

(2.29)

(2.30)

Ітераційний процес триває доти, поки не виконуватимуться нерівності

(і =1,2,3),

де і - два послідовних наближених; - задана точність.

Загальний випадок k -те наближення визначається:

Наприклад: Розв’язати систему лінійних рівнянь з точністю до 0,01 за допомогою ітераційного методу Гаусса-Зейделя.

Розв’язок:

Для даної системи умови (i,j = 1,2,3) збіжності ітераційного процесу виконуються:

Розв’яжемо перше рівняння системи відносно х₁, друге – відносно х₂, третє – відносно х₃:

чи, виконавши ділення, одержимо:

За нульові наближення, візьмемо відповідні значення вільних членів системи: ; ; .

Знайдемо перші наближення, користуючись формулами (2.28-2.30)

Занесемо послідовність наближених коренів системи в таблицю:

Номер інтерації
	1,60000 1,00600 1,00108	2,60000 1,99640 2,00012	3,100000 2,999400 2,999892

Другі наближення:

і т.д.

Наступні наближення наведено в таблиці, з якої випливає, що для ітерацій 2 і 3 виконується нерівність:

(i =1,2).

Відповідь: .

Контрольне завдання

1. Вибрати СЛАР відповідно до свого варіанта.

2. Розв’язати вибрану СЛАР методом Гаусса.

4. Розв’язати вибрану СЛАР методом прогонки.

5. Розв’язати вибрану СЛАР методом LU -декомпозицій.

6. Розв’язати вибрану СЛАР методом простої ітерації з похибкою не більше 1%.

7. Розв’язати вибрану СЛАР методом Гаусса-Зейделя з похибкою не більше 1%.

8. Порівняти результати розв’язування різними методами. Оцінити відхил розв’язку.

Варіанти завдань

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.
27.		28.
29.		30.

Розділ 3. ВЛАСНІ ЧИСЛА І ВЛАСНІ ВЕКТОРИ

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

 

Розглянемо квадратну матрицю -го порядку:

. (3.1)

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

, (3.2)

де Е – одинична матриця;

Ψ – власний вектор матриці А, що відповідає деякому власному числу l_i.

Із рівнянь (3.1), (3.2) випливає, що власні числа можна визначити з характеристичного рівняння:

З останнього рівняння випливає, що будь-яка матриця n´n має n власних чисел з урахуванням їх кратності. Множина власних чисел матриці називається її спектром.

Визначивши власні числа, з умови (3.2) можна знайти власні вектори. Однак у разі великих розмірностей матриці А складність розрахунку значно зростає. Тому розроблено ряд спеціальних методів, що полегшують розв’язання задачі на власні числа і власні вектори.

 

Степеневий метод

Розглянемо типову задачу відшукання максимального за модулем власного значення. Нехай { Ψ _n }– система власних векторів, а {l_i} – система власних значень матриці А:

. (3.3)

Нехай власні значення розташовані з урахуванням їх кратності в порядку зростання:

.

Задамо деяке початкове наближення X₀ до вектора Ψ _n і будемо послідовно обчислювати вектори

X _k = A X _k–1, k = 1, 2… (3.4)

Оскільки система власних векторів { Ψ _i } повна, то X₀ можна подати у вигляді

де c _i – коефіцієнти розкладання. Тоді з (3.3), (3.4) маємо:

(3.5)

З огляду на те, що | l_n | > | l_n–1 |, для досить великих k з (3.5) маємо

(3.6)

Із виразу (3.6) випливає, що якщо c_n ¹ 0, то при досить великому k

.

Отже, максимальне за модулем власне значення l_n можна знайти з ітераційного процессу (3.4). При цьому k -те наближення до власного значення l_n оцінюють як

,

а k -те наближення до власного вектора Ψ :

. (3.7)

Критерієм зупинки ітераційного процесу (3.4) є виконання умови

де e – задане значення відносної похибки.

Якщо треба знати знак l_n, то його знаходять за формулою

.

Із виразів (3.2) та (3.5) випливає, що швидкість збіжності ітераційного процесу лінійна і визначається відношенням , оскільки

.

Для стійкості числового процесу необхідно час від часу нормувати век­тор X_k, щоб ||X_k|| = 1. Інакше, якщо | l_n | > 1, то, як випливає з виразу (3.6), ||X_k|| ® ¥ якщо k ¥. Тому за досить великого k може відбутися переповнення розрядної сітки обчислювальної системи. Якщо |l_n| < 1, то ||X_k|| 0 і внаслідок скінченності розрядної сітки обчислювальної системи може статися, що починаючи з деякого k X_k = 0.

Для пошуку мінімального за модулем власного числа використовують той факт, що мінімальне за модулем власне число матриці A дорівнює величині, оберненій до максимального за модулем власного числа оберненої матриці А ^-1. Це дозволяє обчислити максимальне за модулем власне число l_maxinv матриці А ^-1, а потім знайти шукане мінімальне за модулем власне число матриці А з виразу .

Проте обчислення оберненої матриці – складна операція, яка у разі числової реалізації призводить до значної похибки внаслідок округлення. Тому на практиці під час пошуку мінімального за модулем власного числа чергове наближення вектора X _k знаходять не з ітераційного процесу X _k= A ^-1 · X_k–1, а з розв’язку системи лінійних рівнянь AX _k = X _k–1.

При цьому m -те наближення до власного значення l_min можна оцінити так:

Наприклад: Знайдемо максимальне і мінімальне власні числа та відповідні їм власні вектори для матриці , яка має власні числа l₁ = 2, l₂ = 20 та відповідні їм власні вектори Ψ , Ψ . Спочатку знаходимо максимальне за модулем власне число та відповідний вектор.

Нехай . Тоді згідно з виразом (3.4) маємо:

Далі обчислимо мінімальне за модулем власне число і відповідний власний вектор.

Нехай . Тоді:

Метод скалярного добутку

Для симетричної матриці А максимальне за модулем власне число доцільно шукати з ітераційного процесу:

(3.8)

де k – номер ітерації; – k -те наближення максимального за модулем власного числа; Ψ – k -те наближення відповідного власного вектора. Для початку ітераційного процесу необхідно задати початкове наближення вектора X ₀.

Найменше за модулем власне число симетричної матриці А шукають з ітераційного процесу:

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

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

Наприклад: Знайдемо максимальне і мінімальне власні числа та відповідні їм власні вектори для матриці з попереднього прикладу . Спочатку знайдемо максимальне за модулем власне число та відповідний власний вектор.

Нехай . Тоді згідно з (3.8) маємо:

Далі обчислимо мінімальне за модулем власне число і відповідний власний вектор.

Нехай Тоді:

.

 

Метод Віландта

Часто в практичних задачах виникає необхідність знаходження власного числа, яке є найближчим до деякого заданого числа m. У такому випадку можна розв’язати задачу за допомогою методу Віландта. Суть методу полягає в тому, що спочатку знаходять деяку додаткову матрицю , де Е – одинична матриця. Після цього визначають максимальне за модулем власне число матриці n. Це можна зробити будь-яким відомим методом (наприклад, методом скалярних добутків). Остаточно шукане власне число l обчислюють за формулою

.

Наприклад: Знайдемо власне число матриці , яке є найближчим до числа m = 4.

 

Контрольне завдання

1. Вибрати матрицю A як матрицю коефіцієнтів СЛАР контрольного завдання другого розділу відповідно до свого варіанта.

2. Знайти максимальне і мінімальне власні числа матриці та відповідні власні вектори степеневим методом та методом скалярного добутку з похибкою не більше 1 %.

3. Знайти власне число матриці, найближче до заданого числа m з похибкою не більше 1 %. Значення числа m вибрати з табл. 3.1 відповідно до варіанта.

4. Оцінити число обумовленості матриці.

5. Порівняти результати розв’язку різними методами.

Таблиця 3.1. Значення числа m

Варіант	m	Варіант	m	Варіант	m	Варіант	m	Варіант	m
	–6		–4		–2		–4		–5