5.2: Узагальнення матриці

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

$$\mathbf{A}\, \mathbf{x} = \mathbf{b},$$

де$\mathbf{x}$ і$\mathbf{b}$ є$N\times M$ матрицями, а не просто векторами. Прикладом, для$M=2$, є

$$\begin{bmatrix}1 &2 &3 \\ 3 &2 &2 \\ 2 &6 &2\end{bmatrix} \begin{bmatrix} x_{00} & x_{01} \\ x_{10} & x_{11} \\ x_{20} & x_{21} \end{bmatrix} = \begin{bmatrix}3 & 6 \\ 4 & 8 \\ 4 & 2\end{bmatrix}.$$

Це може стати трохи нудним, щоб продовжувати записувати$x$ елементи в системі рівнянь, особливо коли$\mathbf{x}$ стає матрицею. З цієї причини ми переходимо на позначення, відоме як розширена матриця:

$$\left[\begin{array}{ccc|cc} 1 & 2 & 3 & 3 & 6 \\ 3 & 2 & 2 & 4 & 8 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right].$$

Тут записи зліва від вертикального роздільника позначають ліву частину системи рівнянь, а записи праворуч від роздільника позначають праву частину системи рівнянь.

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

• Усунути елемент можна при$(1,0)$:
  $$\left[\begin{array}{ccc|cc} 1 & 2 & 3 & 3 & 6 \\ 0 & -4 & -7 & -5 & -10 \\ 2 & 6 & 2 & 4 & 2 \end{array}\right]$$
• Усунути елемент можна при$(2,0)$:
  $$\left[\begin{array}{ccc|cc} 1 & 2 & 3 & 3 & 6 \\ 0 & -4 & -7 & -5 & -10 \\ 0 & 2 & -4 & -2 & -10 \end{array}\right]$$
• Усунути елемент можна при$(2,1)$:
  $$\left[\begin{array}{ccc|cc} 1 & 2 & 3 & 3 & 6 \\ 0 & -4 & -7 & -5 & -10 \\ 0 & 0 & -7.5 & -4.5 & -15 \end{array}\right]$$

Крок зворотної підстановки перетворює ліву частину розширеної матриці в матрицю ідентичності:

• Вирішити для рядка$2$:
  $$\left[\begin{array}{ccc|cc} 1 & 2 & 3 & 3 & 3 \\ 0 & -4 & -7 & -5 & -10 \\ 0 & 0 & 1 & 0.6 & 2 \end{array}\right]$$
• Вирішити для рядка$1$:
  $$\left[\begin{array}{ccc|cc} 1 &\; 2 & \;\;\;3 \;\;& 3 & \;3 \\ 0 & \;1 & \;\;\;0\;\; & 0.2 & \;-1 \\ 0 & \;0 & \;\;\;1\;\; & 0.6 & \;2 \end{array}\right]$$
• Вирішити для рядка$0$:
  $$\left[\begin{array}{ccc|cc} 1 & \;0 & \;\;\;0\;\; & 0.8 & \;2 \\ 0 & \;1 & \;\;\;0\;\; & 0.2 & \;-1 \\ 0 & \;0 & \;\;\;1\;\; & 0.6 & \;2 \end{array}\right]$$

Після завершення роботи алгоритму права частина доповненої матриці містить результат для$\mathbf{x}$. Аналізуючи час виконання, використовуючи ті самі міркування, що і раніше, ми виявляємо, що крок зменшення рядків масштабується як$O\Big(N^2(N+M)\Big)$, а крок зворотної заміни масштабується як$O\Big(N(N+M)\Big)$.

Ця матрична форма алгоритму гаусової елімінації є стандартним методом обчислення матричних обертань. Якщо$\mathbf{b}$ є матрицею$N\times N$ ідентичності, то розв'язок$\mathbf{x}$ буде зворотним$\mathbf{A}$. Таким чином, час виконання для обчислення матриці обернено масштабується як$O(N^{3})$.