Вступ до Розкладу Матриць

Розв’язання систем типу $A \vec{x} = \vec{b}$ може бути обчислювально складним, особливо для великих систем.

Розклад матриці спрощує цей процес шляхом розбиття матриці $A$ на простіші частини, які можна розв’язувати поетапно.

LU проти QR

Ми розкладаємо матрицю $A$ на інші структуровані матриці.

LU-розклад

Розбиття $A$ на нижню та верхню трикутні матриці:

• Побудовано за допомогою гаусового виключення;
• Найкраще підходить для квадратних матриць.

$$A = LU$$

QR-розклад

Розбиття $A$ на ортогональну та верхню матриці:

• Часто використовується для неквадратних матриць;
• Ідеально підходить для задач найменших квадратів або коли LU не застосовується.

$$A = QR$$

LU-розклад

Почнемо з квадратної матриці:

$$A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

Наша мета — записати це як:

$$A = LU$$

Де:

$$L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}$$

Такий розклад можливий якщо A квадратна та оборотна.

Важливі моменти:

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

Гаусове виключення

Застосування методу Гаусового виключення для обнулення елемента під верхньою лівою опорною точкою:

$$R_2 \rarr R_2 - \frac{6}{4}R_1$$

Отримуємо:

$$R'_2 = [0, -1.5]$$

Оновлені матриці мають вигляд:

$$U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}$$

Із нашої операції над рядками відомо:

$$L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}$$

Важливі моменти:

• Гаусове виключення систематично обнуляє елементи під опорною точкою в кожному стовпці шляхом віднімання масштабованих версій опорного рядка від рядків нижче;
• Цей процес перетворює A на верхню трикутну матрицю U;
• Множники, використані для обнулення цих елементів, зберігаються в L, що дозволяє представити A як добуток LU.

Результат LU-розкладу

Перевіряємо:

$$A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

Тепер систему $A \vec{x} = \vec{b}$ можна розв’язати у два етапи:

1. Розв’язати $L \vec{y} = \vec{b}$ методом прямої підстановки;
2. Розв’язати $U \vec{x} = \vec{y}$ методом зворотної підстановки.

QR-розклад

Потрібно подати матрицю $A$ у вигляді добутку двох матриць:

$$A = QR$$

Де:

• $A$ — вхідна матриця (наприклад, дані, коефіцієнти тощо);
• $Q$ — ортогональна матриця (її стовпці — ортонормовані вектори);
• $R$ — верхня трикутна матриця.

Приклад розбиття за формою:

$$A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}$$

Цей розклад часто використовується, коли:

• Матриця A не є квадратною;
• Розв’язуються задачі найменших квадратів;
• LU-розклад є нестійким.

Що таке ортонормовані вектори?

Ортогональні вектори

Два вектори $u, v$ є ортогональними, якщо їхній скалярний добуток дорівнює нулю:

$$u \cdot v = 0$$

Нормований вектор

Вектор $u$ є нормованим, якщо $|u| = 1$.

Ортонормований набір

Набір векторів $\{q_1, q_2, ..., q_k\}$ є ортонормованим, якщо кожен з них має одиничну довжину та вони попарно ортогональні:

$$q_i \cdot q_j = \begin{cases} 1,\ \text{якщо}\ \ i = j,\\ 0,\ \text{якщо}\ \ i \neq j. \end{cases}$$

Чому це важливо: ортонормовані стовпці у $Q$ зберігають геометрію, спрощують проєкції та підвищують числову стійкість.

Визначення матриці A

Почнемо з такого прикладу:

$$A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$$

Ми використаємо процес Грама-Шмідта, щоб знайти матриці $Q$ і $R$ такі, що $A=QR$. Процес Грама-Шмідта створює ортонормований набір векторів зі стовпців $A$.

Це означає, що вектори у $Q$ всі взаємно перпендикулярні (ортогональні) та мають одиничну довжину (нормовані). Така властивість спрощує багато обчислень і підвищує числову стійкість при розв'язанні систем.

Отже, тут мета:

• Зробити стовпці $Q$ ортонормованими;
• Створити матрицю $R$, яка буде кодувати проєкції.

Обчислення першого базисного вектора

Виділяємо перший стовпець $A$:

$$a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}$$

Щоб нормувати його, обчислюємо норму:

$$|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}$$

Далі:

$$q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}$$

Це перший ортонормований вектор для $Q$.

Як нормувати вектор

Нехай дано вектор:

$$v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}$$

Обчислюємо його норму:

$$|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}$$

Далі нормуємо:

$$\hat{v} = \frac{1}{|v|}v$$

Приклад:

$$v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5$$

Отже, наш нормований вектор:

$$\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}$$

Коли ми знаємо, як нормувати та ортогоналізувати вектори, можемо застосувати процес Грама-Шмідта для формування матриці $Q$ і використати її для обчислення $R$ у QR-розкладі.

Обчислення $q_2$ за допомогою методу Грама-Шмідта

Щоб обчислити $q_2$, починаємо з другого стовпця $A$:

$$a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}$$

Далі проектуємо $a_2$ на $q_1$:

$$r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30$$

Віднімаємо проєкцію від $a_2$:

$$u_2 = a_2 - r_{12}q_1$$

Потім нормалізуємо (як показано вище):

$$q_2 = \frac{u_2}{|u_2|}$$

Тепер $q_1$ і $q_2$ утворюють ортонормований базис для $Q$. Далі формуємо остаточний результат:

$$Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}$$

Ці матриці задовольняють умову:

$$A = QR$$