Системы линейных алгебраических уравнений
Области применения
- линейные интегральные уравнения
- линейные дифференциальные уравнения
- линейная оптимизация
- приближение в линейном пространстве
- задача об устойчивости конструкций
- нахождение обратной матрицы в нелинейных задачах (дифференциальные уравнения, оптимизация, нелинейные уравнения)
Методы решения
- Прямые методы
- находят точное решение $\boldsymbol{x}$;
- используются для плотных матриц малой размерности;
- Итерационные методы
- рассчитывают такое $\boldsymbol{x_k}$, что $k \to \infty \quad \Longrightarrow \quad \boldsymbol{A} \boldsymbol{x_k} - \boldsymbol{b} \to \boldsymbol{0}$;
- используются для разреженных матриц большой размерности.
Матричная форма СЛАУ имеет вид:
\begin{equation*}
\begin{bmatrix}
a_{11} & \dots & a_{1n} \\
\vdots & & \vdots \\
a_{n1} & \dots & a_{nn}
\end{bmatrix}
\begin{bmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{bmatrix}
=
\begin{bmatrix}
b_{1} \\
\vdots \\
b_{n}
\end{bmatrix}
\end{equation*}
или кратко $\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}$, где $\boldsymbol{A} \in \mathbb{R}^{n \times n}$, $\boldsymbol{x} \in \mathbb{R}^{n}$ и $\boldsymbol{b} \in \mathbb{R}^{n}$.
Метод Гаусса
Структура метода Гаусса:
- прямой ход: приведение матрицы $\boldsymbol{A}$ к треугольному виду с помощью элементарных преобразований;
- обратный ход: нахождение решения $\boldsymbol{x}$ с помощью рекурсивной подстановки.
Найдем количество операций в методе Гаусса, учитывая только операции умножения/деления.
Метод Гаусса с выбором главного элемента
Метод Гаусса в общем случае является неустойчивым:
- если на $k$-й итерации $a_{kk}^{(k-1)} \ll a_{ik}^{(k-1)}$, то множитель $m_{ik} = \frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}} \to \infty$;
- происходит усиление погрешности округления в результате последующих умножений на $m_{ik}$.
Проблема может быть решена с помощью перестановки строк или столбцов, что происходит на каждой итерации прямого хода.
Частичный выбор главного элемента
Перестановка строк так, что
\begin{equation*}
|a_{kk}^{(k)}| = \max_{k \leq i \leq n} |a_{ik}^{(k)}|.
\end{equation*}
- частичный выбор требует суммарно $O(n^2)$ сравнений;
- используется по умолчанию в большинстве случаев.
Полный выбор главного элемента
Перестановка строк и столбцов так, что
\begin{equation*}
|a_{kk}^{(k)}| = \max_{k \leq i, j \leq n} |a_{ij}^{(k)}|.
\end{equation*}
- полный выбор требует суммарно $O(n^3)$ сравнений;
- используется только в задачах, чувствительных к погрешности округления.
LU-разложение
LU-разложением называется разложение матрицы $\boldsymbol{A}$ в нижнюю и верхнюю треугольные матрицы:
\begin{equation*}
\boldsymbol{A} = \boldsymbol{L}\boldsymbol{U}.
\end{equation*}
Тогда решение СЛАУ $\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}$ мы получаем путем решения двух СЛАУ:
\begin{align*}
\boldsymbol{L} \boldsymbol{y} &= \boldsymbol{b} \\
\boldsymbol{U} \boldsymbol{x} &= \boldsymbol{y}.
\end{align*}
- каждый из шагов требует $O(n^2)$ операций;
- LU-разложение требует $O(n^3)$ операций (прямой ход метода Гаусса);
- тогда один раз разложив матрицу $\boldsymbol{A}$, решение $\boldsymbol{x}$ для различных $\boldsymbol{b}$ находится в $O(n^2)$ шагов.
Заметим, что $k$-я итерация прямого хода метода Гаусса эквивалента:
\begin{equation*}
\boldsymbol{A}^{(k)} = \boldsymbol{M}^{(k)} \boldsymbol{A}^{(k-1)},
\end{equation*}
где $\boldsymbol{M}^{(k)}$ имеет вид:
\begin{equation*}
\boldsymbol{M}^{(k)}
=
\begin{bmatrix}
1 & 0 & \dots & \dots & \dots & \dots & \dots & 0 \\
0 & \ddots & \ddots & & & & & \vdots \\
\vdots & \ddots & \ddots & \ddots & & & & \vdots \\
\vdots & & 0 & \ddots & \ddots & & & \vdots \\
\vdots & & \vdots & -m_{k+1, k} & \ddots & \ddots & & \vdots \\
\vdots & & \vdots & \vdots & 0 & \ddots & \ddots & \vdots \\
\vdots & & \vdots & \vdots & \vdots & \ddots & \ddots & 0 \\
0 & \dots & 0 & -m_{nk} & 0 & \dots & 0 & 1
\end{bmatrix},
\end{equation*}
где индексы в $m_{ij}$ соответствуют строке и колонке матрицы.
Для примера рассмотрим вторую итерацию прямого хода для матрицы $\boldsymbol{A} \in \mathbb{R}^{4 \times 4}$:
$$
\boldsymbol{A}^{(2)} = \boldsymbol{M}^{(2)} \boldsymbol{A}^{(1)}
=
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & -m_{32} & 1 & 0 \\
0 & -m_{42} & 0 & 1
\end{bmatrix}
\begin{bmatrix}
a_{11} & a_{12} & a_{13} & a_{14} \\
0 & a_{22}^{(1)} & a_{23}^{(1)} & a_{24}^{(1)} \\
0 & a_{32}^{(1)} & a_{33}^{(1)} & a_{34}^{(1)} \\
0 & a_{42}^{(1)} & a_{43}^{(1)} & a_{44}^{(1)}
\end{bmatrix}
=
\begin{bmatrix}
a_{11} & a_{12} & a_{13} & a_{14} \\
0 & a_{22}^{(1)} & a_{23}^{(1)} & a_{24}^{(1)} \\
0 & 0 & -m_{32} a_{23}^{(1)} + a_{33}^{(1)} & -m_{32} a_{24}^{(1)} + a_{34}^{(1)} \\
0 & 0 & -m_{42} a_{23}^{(1)} + a_{43}^{(1)} & -m_{42} a_{24}^{(1)} + a_{44}^{(1)}
\end{bmatrix}
$$
где $m_{32} = \frac{a_{32}^{(1)}}{a_{22}^{(1)}}$ и $m_{42} = \frac{a_{42}^{(1)}}{a_{22}^{(1)}}$.
Найдем выражение для верхней треугольной матрицы $\boldsymbol{U}$ и нижней треугольной матрицы $\boldsymbol{L}$:
Обратная матрица $\left(\boldsymbol{M}^{(k)}\right)^{-1} = \boldsymbol{L}^{(k)}$ имеет вид:
\begin{equation*}
\left(\boldsymbol{M}^{(k)}\right)^{-1}
=
\boldsymbol{L}^{(k)}
=
\begin{bmatrix}
1 & 0 & \dots & \dots & \dots & \dots & \dots & 0 \\
0 & \ddots & \ddots & & & & & \vdots \\
\vdots & \ddots & \ddots & \ddots & & & & \vdots \\
\vdots & & 0 & \ddots & \ddots & & & \vdots \\
\vdots & & \vdots & m_{k+1, k} & \ddots & \ddots & & \vdots \\
\vdots & & \vdots & \vdots & 0 & \ddots & \ddots & \vdots \\
\vdots & & \vdots & \vdots & \vdots & \ddots & \ddots & 0 \\
0 & \dots & 0 & m_{nk} & 0 & \dots & 0 & 1
\end{bmatrix}.
\end{equation*}
Тогда нижняя треугольная матрица $\boldsymbol{L}$ имеет вид:
\begin{equation*}
\boldsymbol{L}
=
\boldsymbol{L}^{(1)} \cdots \boldsymbol{L}^{(n-1)}
=
\begin{bmatrix}
1 & 0 & \dots & 0 \\
m_{21} & 1 & \ddots & \vdots \\
\vdots & \ddots & \ddots & 0 \\
m_{n1} & \dots & m_{n, n-1} & 1
\end{bmatrix}.
\end{equation*}
Заметим, что:
- в выводе LU-разложения мы не предполагали перестановок строк;
- перестановки можно учесть с помощью матрицы перестановки:
- матрица перестановки $\boldsymbol{P}$ образуется с помощью перестановки строк единичной матрицы $\boldsymbol{E}$;
- $\boldsymbol{P} \boldsymbol{A}$ переставляет строки матрицы $\boldsymbol{A}$;
- $\boldsymbol{A} \boldsymbol{P}$ переставляет столбцы матрицы $\boldsymbol{A}$.
Учитывая перестановки, можно найти LU-разложение для матрицы:
\begin{equation*}
\boldsymbol{P} \boldsymbol{A} = \boldsymbol{L} \boldsymbol{U},
\end{equation*}
и затем найти решение уравнения:
\begin{equation*}
\boldsymbol{P} \boldsymbol{A} \boldsymbol{x} = \boldsymbol{P} \boldsymbol{b}.
\end{equation*}
Матрицы с диагональным преобладанием
Диагональное преобладание
Матрица $\boldsymbol{A}$ является матрицей с диагольным преобладанием, если
\begin{equation*}
|a_{ii}| \geq \sum_{\substack{j = 1\\ i \neq j}}^n |a_{ij}|, \quad i = 1, \dots, n.
\end{equation*}
Строгое диагональное преобладание
Матрица $\boldsymbol{A}$ является матрицей со строгим диагольным преобладанием, если
\begin{equation*}
|a_{ii}| > \sum_{\substack{j = 1\\ i \neq j}}^n |a_{ij}|, \quad i = 1, \dots, n.
\end{equation*}
Cвойства матриц со строгим диагональным преобладанием:
- являются невырожденными;
- метод Гаусса для них не требует перестановок строк и столбцов;
- метод Гаусса для них является вычислительно устойчивым.
Теорема о невырожденности матриц со строгим диагональным преобладанием
Матрица $\boldsymbol{A}$ со строгим диагональным преобладанием является невырожденной.
Доказательство
Положительно определенные матрицы
Определение
Матрица $\boldsymbol{A}$ называется положительно определенной, если она симметричная, и верным является
неравенство $\boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x} > 0$ для любого вектора
$\boldsymbol{x} \neq \boldsymbol{0}$.
Заметим, что: $\displaystyle \boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x} = \sum_{i = 1}^n \sum_{j = 1}^n a_{ij} x_i x_j$.
Теорема о свойствах
Пусть $\boldsymbol{A}$ – положительно определенная матрица. Тогда верно следующее:
- существует $\boldsymbol{A}^{-1}$;
- $a_{ii} > 0, i = 1, \dots, n$;
- $\max_{1\leq i \leq n} |a_{ii}| \geq \max_{1\leq k, j\leq n} |a_{kj}|$;
- $a_{ii} a_{jj} > a_{ij}^2, i \neq j$.
Доказательство свойств 1 и 2
Решение СЛАУ с положительно определенными матрицами
Особенности
- метод Гаусса для положительно определенных матриц не требует перестановок строк и столбцов;
- метод Гаусса для них является вычислительно устойчивым.
Разложения
- $LDL^T$ разложение (существует и для симметричных матриц);
- $LL^T$ разложение (разложение Холецкого).
Теорема
Матрица $\boldsymbol{A}$ является положительно определенной тогда и только тогда, когда существует разложение
$\boldsymbol{A} = \boldsymbol{L} \boldsymbol{D} \boldsymbol{L}^T$, где $\boldsymbol{L}$ – нижняя
треугольная матрица с единицами на диагонали, $\boldsymbol{D}$ – диагональная матрица с положительными
элементами.
Рассмотрим $LDL^T$ разложение для положительно определенной матрицы $\boldsymbol{A} \in \mathbb{R}^{3 \times 3}$:
Разложение Холецкого
Теорема
Матрица $\boldsymbol{A}$ является положительно определенной тогда и только тогда, когда существует разложение
$\boldsymbol{A} = \boldsymbol{L} \boldsymbol{L}^T$, называемое разложением Холецкого, где
$\boldsymbol{L}$ – нижняя треугольная матрица с ненулевыми элементами на диагонали.
Вывод разложения Холецкого из $LDL^T$ разложения:
\begin{equation*}
\boldsymbol{L} \boldsymbol{D} \boldsymbol{L}^T = \boldsymbol{L} \boldsymbol{\sqrt{D}} \boldsymbol{\sqrt{D}} \boldsymbol{L}^T =
\left(\boldsymbol{L} \boldsymbol{\sqrt{D}}\right) \left(\boldsymbol{L} \boldsymbol{\sqrt{D}}\right)^T = \boldsymbol{\tilde L} \boldsymbol{\tilde L}^T.
\end{equation*}
Рассмотрим разложение Холецкого для положительно определенной матрицы $\boldsymbol{A} \in \mathbb{R}^{3 \times 3}$:
Ленточные матрицы
Ленточные матрицы
Квадратная матрица $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ называется ленточной, если существуют такие $p, q \in \mathbb{Z}$, где $1 < p, q < n$, что $j - i \geq p \Longrightarrow a_{ij} = 0$ и $i - j \geq q \Longrightarrow a_{ij} = 0$.
Трехдиагональные матрицы
$$
\boldsymbol{A}
=
\begin{bmatrix}
a_{11} & a_{12} & 0 & \dots & \dots & \dots & 0 \\
a_{21} & a_{22} & a_{23} & \ddots & & & \vdots \\
0 & a_{32} & a_{23} & a_{34} & \ddots & & \vdots \\
\vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\
\vdots & & \ddots & \ddots & \ddots & \ddots & 0 \\
\vdots & & & \ddots & a_{n-1, n-2} & a_{n-1, n-1} & a_{n-1, n} \\
0 & \dots & \dots & \dots & 0 & a_{n, n-1} & a_{nn} \\
\end{bmatrix}.
$$
Пример
- Ширина ленты: $w = p + q - 1$;
- $p$ – число ненулевых диагоналей над главной диагональю (включая ее);
- $q$ – число ненулевых диагоналей под главной диагональю (включая ее);
- ленточная матрица является частным случаем разреженной матрицы.
Метод прогонки / Thomas algorithm
Метод прогонки является эффективным алгоритмом решения СЛАУ с трехдиагональными матрицами:
\begin{equation*}
\begin{bmatrix}
a_{11} & a_{12} & 0 & \dots & \dots & \dots & 0 \\
a_{21} & a_{22} & a_{23} & \ddots & & & \vdots \\
0 & a_{32} & a_{33} & a_{34} & \ddots & & \vdots \\
\vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\
\vdots & & \ddots & \ddots & \ddots & \ddots & 0 \\
\vdots & & & \ddots & a_{n-1, n-2} & a_{n-1, n-1} & a_{n-1, n} \\
0 & \dots & \dots & \dots & 0 & a_{n, n-1} & a_{nn} \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\vdots \\
\vdots \\
x_{n-1} \\
x_{n} \\
\end{bmatrix}
=
\begin{bmatrix}
b_1 \\
b_2 \\
b_3 \\
\vdots \\
\vdots \\
b_{n-1} \\
b_{n} \\
\end{bmatrix}.
\end{equation*}
Каждая строка эквивалентна рекуррентному соотношению вида:
\begin{equation*}
\label{eq:thomas_original_recur}
a_{i, i-1} x_{i-1} + a_{ii} x_i + a_{i, i+1} x_{i+1} = b_i.
\end{equation*}
Метод прогонки / Thomas algorithm
Методом последовательного исключения можно привести такую СЛАУ к верхней треугольной форме:
\begin{equation*}
\begin{bmatrix}
\tilde a_{11} & \tilde a_{12} & 0 & \dots & \dots & 0 \\
0 & \tilde a_{22} & \tilde a_{23} & \ddots & & \vdots \\
\vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\
\vdots & & \ddots & \ddots & \ddots & 0 \\
\vdots & & & \ddots & \tilde a_{n-1, n-1} & \tilde a_{n-1, n} \\
0 & \dots & \dots & \dots & 0 & \tilde a_{nn} \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
\vdots \\
\vdots \\
x_{n-1} \\
x_{n} \\
\end{bmatrix}
=
\begin{bmatrix}
\tilde b_1 \\
\tilde b_2 \\
\vdots \\
\vdots \\
\vdots \\
\tilde b_{n-1} \\
\tilde b_{n} \\
\end{bmatrix}.
\end{equation*}
Найдем рекуррентные соотношения, позволяющие вычислить $x_i$:
Заметим, что:
- алгоритмическая сложность метода прогонки: $O(n)$;
- метод прогонки устойчив для матриц со строгим диагональным преобладанием (следствие вывода метода прогонки из метода Гаусса).