S V D - р о з к л а д у представляє собою декілька етапів (за винятком модифікацій методу Якобі).

1. Матрицю А необхідно привести до двохдіагонального вигляду A U1 B V1T , де U1 та V1 є ортогональними матрицями, В – верхньою

двохдіагональною. Для цього можна скористатися відображенням Хаусхолдера.

2. Виконується сингулярний розклад двохдіагональної матриці В. B U2 V2T , де U1 та V1 є ортогональними матрицями, Σ – діагональ-

ною матрицею сингулярних чисел. При цьому сингулярні числа матриці В будуть співпадати з сингулярними числами матриці А.

3. Розклади етапів 1 та 2 комбінуються, щоб отримати розклад A (U1 U2 ) B (V1 V1)T . Сингулярними векторами матриці А є U U1 U2

і V V1 V2 .

2. ПОСТАНОВКА ЗАВДАННЯ

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

Варіант 1

1.Додати в розроблений клас «Матриця» метод, що дозволяє обчислити власні значення і власні вектори симетричної матриці за допомогою класичного алгоритму Якобі.

2.Додати метод, що реалізує рядковий циклічний алгоритм Якобі для симетричної матриці. Передбачити можливість обчислення власних векторів за цим алгоритмом.

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

4.Порівняти роботу модифікацій методів Якобі на тестових матрицях (див. приклади). Контролювати зміну норми позадіагональної частини

48

матриці off A після кожної чистки. За результатами спостережень для

кожної з модифікацій заповнити таблицю, аналогічну табл. 1.1.

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

Варіант 2

1.Додати в розроблений клас «Матриця» метод, що дозволяє знайти власні значення симетричної матриці за допомогою QR-алгоритму зі зсувами, що обираються за стратегією Уілкінсона. Передбачити попереднє приведення матриці до тридіагонального вигляду.

2.Додати метод, що дозволяє за допомогою QR-алгоритму знайти власні вектори матриці.

3.Додати метод, що дозволяє обчислити власні значення і власні вектори симетричної матриці за допомогою класичного алгоритму Якобі.

4.Порівняти час роботи методів на тестових матрицях різного розміру для знаходження всіх власних значень. За результатами роботи побудувати графік збільшення часу роботи методів від розміру матриці у відносних координатах. Прийняти за час, що дорівнює одиниці, час роботи QR-алгоритму зі зсувами.

5.Провести дослідження, аналогічне п. 4, для пошуку власних векторів матриці.

Варіант 3

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

2.Додати метод, що реалізує RQ-алгоритм для знаходження власних значень і векторів.

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

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

49

внює одиниці, час роботи методу бісекції при пошуку першого власного значення.

5. Порівняти час роботи методів на тестових матрицях різного розміру для знаходження максимального за модулем власного значення та відповідного власного вектора. За результатами роботи побудувати графік збільшення часу роботи методів від розміру матриці у відносних координатах. Прийняти за час, що дорівнює одиниці, час роботи RQ-алгоритму.

Варіант 4

1.Додати в розроблений клас «Матриця» метод, що дозволяє обчислити власні значення і власні вектори симетричної матриці за допомогою алгоритма «поділяй та пануй». Передбачити попереднє приведення матриці до тридіагонального вигляду.

2.Додати метод, що дозволяє знайти власні значення симетричної матриці за допомогою QR-алгоритму зі зсувами, що обираються за стратегією Уілкінсона. Передбачити попереднє приведення матриці до тридіагонального вигляду.

3.Додати метод, що дозволяє за допомогою QR-алгоритму знайти власні вектори матриці.

4.Порівняти час роботи методів на тестових матрицях різного розміру для знаходження всіх власних значень. За результатами роботи побудувати графік збільшення часу роботи методів від розміру матриці у відносних координатах. Прийняти за час, що дорівнює одиниці, час роботи QR-алгоритму.

5.Провести дослідження, аналогічне п. 4, для пошуку власних векторів матриці.

Варіант 5

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

2.Додати метод, що дозволяє знайти власні значення симетричної матриці за допомогою QR-алгоритму зі зсувами, що обираються за стратегією Уілкінсона. Передбачити попереднє приведення матриці до тридіагонального вигляду.

50

3.Додати метод, що дозволяє за допомогою QR-алгоритму знайти власні вектори матриці.

4.Порівняти час роботи методів на тестових матрицях різного розміру для знаходження всіх власних значень. За результатами роботи побудувати графік збільшення часу роботи методів від розміру матриці у відносних координатах. Прийняти за час, що дорівнює одиниці, час роботи QR-алгоритму.

5.Провести дослідження, аналогічне п. 4, для пошуку власних векторів матриці.

Варіант 6

1. Додати в розроблений клас «Матриця» метод, що обчислює SVDрозклад прямокутної матриці А, використовуючи QR-алгоритм зі зсувами, що обираються за стратегією Уілкінсона, який застосовується для симет-

ричної матриці AT A або AAT . Передбачити попереднє приведення отриманої симетричної матриці до тридіагонального вигляду.

2. Додати метод, що дозволяє обчислити SVD-розклад прямокутної матриці А, використовуючи класичний алгоритм Якобі для симетричної

матриці AT A або AAT .

3.Для перевірки правильності роботи методів передбачити можливість встановлення вихідної матриці за введеним її SVD-розкладом.

4.Порівняти точність знаходження сингулярних чисел матриці, отриманих за допомогою QR-алгоритму і методу Якобі, а також в залеж-

ності від порядку множення матриць AT A або AAT .

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

3. КОНТРОЛЬНІ ЗАПИТАННЯ

1. Які проблеми (задачі) при знаходженні власних значень і векторів існують? Наведіть приклади алгоритмів, що розв’язують кожну з проблем власних значень.

51

2.Які чисельні методи передбачають перед обчисленням власних значень попереднє приведення симетричної матриці до тридіагональної форми?

3.Яка кількість арифметичних операцій необхідна для приведення симетричної матриці до тридіагонального вигляду? Як зміниться ця величина, якщо потрібні також власні вектори?

4.Які існують методи приведення симетричної матриці до тридіагональної форми?

5.На чому ґрунтується головна ідея методу Якобі?

6.Які модифікації методу Якобі існують та які вони мають алгорит-

ми?

7.Яка швидкість збіжності методу Якобі?

8.Яку кількість арифметичних операцій має метод Якобі при знаходженні власних значень симетричної матриці?

9.В чому полягають особливості застосування QR-алгоритму знаходження власних значень і векторів у випадку симетричної матриці?

10.В чому полягає стратегія Уілкінсона при виборі зсувів у QRалгоритмі?

11.Яка швидкість збіжності QR-алгоритма?

12.Яку кількість арифметичних операцій має QR-алгоритм при знаходженні власних значень симетричної матриці? Як зміниться ця величина, якщо також потрібні і власні вектори матриці?

13.Що дозволяє знайти метод скалярних добутків та який він має ал-

горитм?

14.Як застосувати метод скалярних добутків для знаходження інших власних пар?

15.Яка швидкість збіжності SP-алгоритма?

16.Що дозволяє знайти RQ-ітерація та який вона має алгоритм?

17.Яка швидкість збіжності RQ-ітерації?

18.Які існують особливості практичного застосування RQ-ітерації?

19.На чому ґрунтується ідея методу бісекції та які величини він дозволяє знайти?

20.Який алгоритм методу бісекції?

21.Які способи обчислення визначників можуть використовуватися в методі бісекції?

22.Що називають послідовністю Штурма та які вона має властивос-

ті?

52

23.Які проблеми існують при обчислені послідовності Штурма на

ЕОМ?

24.Яку кількість арифметичних операцій при знаходженні одного власного значення має метод бісекції?

25.В яких випадках метод бісекції буде швидшим за QR-алгоритм?

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

27.На чому ґрунтується ідея методу «поділяй та пануй»? Хто є його автором?

28.Який алгоритм має метод «поділяй та пануй»?

29.Яку кількість арифметичних операцій має метод «поділяй та па-

нуй»?

30.Який чисельний метод звичайно використовують у методі «поділяй та пануй» при пошуку коренів рівняння. Яку він має кількість арифметичних операцій при пошуку одного кореня?

31.В яких випадках метод «поділяй та пануй» буде швидшим за QRалгоритм?

32.Який із етапів алгоритма методу «поділяй та пануй» вимагає найбільших обчислювальних затрат? Завдяки чому вдається на практиці скоротити цю величину?

33.На чому ґрунтується ідея методу Ланцоша та в яких випадках він може застосовуватися?

34.Як за допомогою метода Ланцоша привести симетричну матрицю до тридіагонального вигляду?

35.Який алгоритм має метод Ланцоша для знаходження власних значень і векторів матриці?

36.Які величини називають апроксимувальною парою Релея–Рітца?

37.Яким чином контролюють точність розрахунків у методі Ланцоша при знаходженні власних значень?

38.Що називають сингулярним розкладом матриці?

39.Які вчені внесли великий вклад у розробку сингулярного розкладу матриць?

40.Для яких типів матриць існує сингулярний розклад?

41.Які основні алгебраїчні та геометричні властивості сингулярного розкладу?

42.Яка геометрична інтерпретація сингулярного розкладу матриці?

53