Матричні операції - Математика
4. Матричні операції
4.1 Матричне множення
Існує два можливі способи впливати оператором на функцію в рамках вейвлет-теорії. Вони називаються стандартним та нестандартним матричним множенням.
У досить гладких функцій більшість їх вейвлет-коефіцієнтів досить малі. Для широкого класу операторів більшість їх матричних елементів також виявляються невеликими. Розглянемо структуру тих елементів матричного уявлення деякого оператора Т, які досить великі. Матричні елементи задовольняють наступним співвідношенням.
при , (4.1.1)
при , (4.1.2)
Топологія розподілу цих матричних елементів усередині матриці може бути дуже заплутаною.
Розглянемо дію оператора Т на функцію f, яка перетворює її на функцію g.
(4.1.3)
Як g, так і f можуть бути представлені у вигляді вейвлет-рядів з вейвлет-коефіцієнтами (f sj, k; f dj, k) і (g sj, k; g dj, k). На найбільш детальному рівні дозволу jn відмінні від нуля тільки s-коефіцієнти, і перетворення має вигляд
. (4.1.4)
На наступному рівні отримуємо
, (4.1.5)
, (4.1.6)
та заміна нижніх індексів S®D відповідає підстановці j®y під знаком інтеграла.
Є зв'язок між різними рівнями, тому що всі s-коефіцієнти на цьому (jn-1)-му рівні мають бути розкладені за допомогою швидкого вейвлет-перетворення на s- та d-коефіцієнти вищих рівнів. Тому, навіть маючи майже діагональний вигляд на початковому етапі, стандартна матриця набуває потім досить складного вигляду, як це показано на рис.1.
На кінцевому етапі ми маємо справу з вейвлет-поданням, що описується формулою (2.1), в якій у векторах залишається тільки один s-коефіцієнт,представляє зважене середнє функції по всьому інтервалу її завдання, а SS-перехід f до g описується верхнім лівим квадратиком на цьому малюнку. У той же час на шляху до цієї формули від скейлінг-подання нам доводилося мати справу із середніми величинами на проміжних рівнях, розкладаючи їх потім на кожному етапі на частини s і d наступних рівнів дозволу. Ці проміжні s-коефіцієнти були опущені, тому що ми заміняли їх на s-і d-коефіцієнти рівних рівнів. Саме тому остаточна матриця при стандартному підході набуває такого складного вигляду.
Рис.1. Матричне подання за стандартного підходу до вейвлет-аналізу.
Частини матриці з ненульовими вейвлет-коефіцієнтами заштриховані.
З метою спрощення виду матричного уявлення було запропоновано використати перевизначений набір вейвлет-коефіцієнтів. Збережемо ці усереднені величини у вигляді відповідних проміжних s-коефіцієнтів як початкових, так і в кінцевих векторах, що представляють функції f і g. Звичайно, в цьому випадку доведеться мати справу з векторами, які набагато більше необхідних для кінцевої відповіді. Однак відомий алгоритм приведення цих перевизначених виразів до остаточної неперевизначеної форми. У той самий час в такий спосіб можна значно спростити вид матриці перетворення та чисельні розрахунки.
Рис.2. Нестандартне матричне множення під час вейвлет-аналізу.
Різні рівні виявилися повністю розв'язаними, тому що в матриці тепер відсутні блоки, які раніше переплутували їх. Блок із SS-елементами вилучено, а на його місце вставлено нульову матрицю. Повна матриця відповідно штучно збільшилася. Разом з нею збільшились і вектори, що характеризуютьфункції f та g. Тепер утримуються всі проміжні s-коефіцієнти вейвлет-розкладання функції f. Кожен блок Sj+1 виходить із Sj та Dj. У матриці перетворення дорівнюють нулю всі SS-елементи за винятком їх величин на нижчому рівні S0S0. Решта SD-, DS-, DD-матриці майже діагональні внаслідок кінцівки області завдання вейвлетів і скейлінг функцій. Наведена на рис. 2 форма функції g перетворюється на її звичайне вейвлет-подання з рис. 1 шляхом поділу кожного Sj в Sj-1 та Dj-1 стандартним методом. Потім ці Sj-1 та Dj-1 додаються у відповідні компоненти вектора. Ця процедура ітерується, починаючи тепер уже з Sj-1, вполоти до S0, коли ми приходимо до звичайного вейвлет-подання функції g. У такий спосіб ми позбавляємося всіх s-коефіцієнтів за винятком s0. Обчислення можна тепер зробити дуже швидко.
4.2 Звернення матриці
Твердження 1. Послідовність матриць Xk така, що
де А * - сполучена матриця і a вибирається таким чином, щоб найбільше власне значення матриці a А * А менше двох. Тоді послідовність сходить до узагальненої зворотної матриці А-1.
Якщо це твердження скомбінувати з алгоритмом швидкого матричного множення, виходить алгоритм для побудови зворотної матриці в стандартній формі з трудомісткістю і в нестандартній формі з трудомісткістю , де R - число обумовленості матриці. За допомогою числа R можна оцінити співвідношення між найбільшим та найменшим сингулярними числами вище за поріг точності.
4.3 Обчислення експоненти, синуса та косинуса від матриці.
При зверненні матриці використовувався раніше відомий алгоритм, який виходить на зовсім інший рівень, коли застосовується разом із вейвлет-поданням.
Алгоритм обчислення експонентівматриці ґрунтується на тотожності
. (4.3.1)
По-перше, exp(2 -LA) може бути порахована, наприклад, за допомогою ряду Тейлора. Число L вибирається таким чином, щоб найбільше сингулярне число матриці 2 -L A було менше одиниці. На другому кроці алгоритму досягнення результату матриця 2 -L A зводиться в квадрат L разів.
Аналогічно, синус і косинус від матриці можуть бути пораховані з використанням формул подвійного кута.
(4.3.2)
, (4.3.3)
(4.3.4)
, (4.3.5)
де I – тотожність. Знову вибираємо L таким чином, щоб найбільше сингулярне число матриці 2 -L A було менше одиниці, обчислюємо синус і косинус матриці 2 -LA, за допомогою рядів Тейлора, а потім використовуємо формули (4.3.4) і (4.3.5).
Зазвичай такі алгоритми вимагають щонайменше O(N 3 ) операцій, оскільки має бути виконано досить багато операцій з множення густих матриць. Швидкий алгоритм для множення матриць у стандартній формі зменшує складність не більше ніж операцій, а швидкий алгоритм для множення матриць у нестандартній формі – до O(N) операцій.
Beylkin G. Wavelets and Fast Numerical Algorithms.
Beylkin G. Wavelets, Multiresolution Analysis and Fast Numerical Algorithms.
Дремін І.М., Іванов О.В., Нечитайло В.А. Вейвлети та їх використання // Успіхи фізичних наук - 2001 №5. - С.465-500