Прямые методы решения систем линейных алгебраических уравнений

Постановка задачи

Дана СЛАУ:

$\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+...+a_{1m}{x}_m=b_1\\ \dots \\ a_{m1}{x}_1+a_{m2}{x}_2+...+a_{mm}{x}_m=b_m\end{array}$

$A=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1m}\\ ⋮& \ddots & ⋮\\ a_{m1}& \dots & a_{mm}\end{array}\right)x=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_m\end{array}\right)b=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right)$

$Ax=b$ Предполагаем, что $A$ - невырожденная ($\Rightarrow$ задача корректна). $x^{*}=(x_1^{*}\dots x_m^{*}{)}^T$ - приближенное решение задачи. Погрешность $e=x-x^{*}$. Невязка $r=b-A{x}^{*}\Rightarrow r=Ax-A{x}^{*}=A(x-x^{*})\Rightarrow e=A^{-1}r$

Шаблон:Определение Три варианта задания нормы:

$\Vert x{\Vert }_1=\sum _{i=1}^m|x_i|,\Vert x{\Vert }_2=(\sum _{i=1}^m|x_i{|}^2{)}^{\frac{1}{2}},\Vert x{\Vert }_{\mathrm{\infty }}=\max 1\le i\le m|x_i|$

Скалярное произведение: $(x,y)=x_1{y}_1+...+x_m{y}_m$. Погрешности: $\delta (x^{*})=\frac{\Vert x-x^{*}\Vert }{\Vert x\Vert }$, $\mathrm{\Delta }(x^{*})=\Vert x-x^{*}\Vert$

Норма матрицы $\Vert A\Vert =\max x\ne 0\frac{\Vert Ax\Vert }{\Vert x\Vert }$. Свойства:

1. $\Vert A\Vert \ge 0\Vert A\Vert =0\iff A=0$
2. $\Vert \alpha A\Vert =|\alpha |\Vert A\Vert \mathrm{\forall }A,\alpha$
3. $\Vert A+B\Vert \le \Vert A\Vert +\Vert B\Vert$
4. $\Vert A\cdot B\Vert \le \Vert A\Vert \cdot \Vert B\Vert$
5. $\Vert Ax\Vert \le \Vert A\Vert \cdot \Vert x\Vert (\Vert x\Vert \ne 0\Rightarrow \frac{\Vert Ax\Vert }{\Vert x\Vert }\le \Vert A\Vert -\text{из определения})$

$\Vert A{\Vert }_1=\max 1\le j\le m\sum _{i=1}^m|a_{ij}|,\Vert A{\Vert }_2=\max 1\le j\le m\sqrt{{\lambda }_j(A^{T}A)},\Vert A{\Vert }_{\mathrm{\infty }}=\max 1\le j\le m\sum _{i=1}^m|a_{j}i|$

Это подчиненные нормы $\Vert A{\Vert }_E=\sqrt{\sum _{i,j=1}^m\Vert a_{i}j{\Vert }^2}$

Методы решения

Метод Гаусса

Прямой ход:

1-й шаг - пусть $a_{11}\ne 0$. Найдем ${\mu }_{i1}=\frac{a_{i1}}{a11},i=\overline{2,m}$. Из $2..m$ уравнений вычитаем первое, домноженное на ${\mu }_{i1}$. Получаем:

$\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\dots +a_{1m}{x}_m=b_1\\ a_{22}^{(1)}{x}_2+\dots +a_{2m}^{(1)}{x}_m=b_2^{(1)}\\ \dots \\ a_{m2}^{(1)}{x}_2+\dots +a_{mm}^{(1)}{x}_m=b_m^{(1)}\end{array}$

$a_{ij}^{(1)}=a_{ij}-{\mu }_{i1}{a}_{ij},b_i^{(1)}=b_i-{\mu }_{i1}{b}_1$

2-й шаг - пусть $a_{22}^{(1)}\ne 0,{\mu }_{i2}=\frac{a_{i2}^{(1)}}{a_{22}^{(1)}}$

k-й шаг: $a_{kk}^{(k-1)}\ne 0,{\nu }_{ik}=\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}},i=\overline{k+1,m}$

За (m-1) шаг получаем:

$\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+a_{33}{x}_3+\dots +a_{1m}{x}_m=b_1\\ a_{22}^{(1)}{x}_2+a_{33}^{(1)}{x}_3+\dots +a_{2m}^{(1)}{x}_m=b_2^{(1)}\\ a_{33}^{(2)}{x}_3+\dots +a_{2m}^{(2)}{x}_m=b_2^{(2)}\\ \dots \\ a_{mm}^{(m-1)}{x}_m=b_m^{(m-1)}\end{array}$

Обратный ход:

Из последнего уравнения находим $x_m$, подставляем в предпоследнее, находим $x_{m-1}$. $x_m=b_m^{(m-1)}/a_{mm}^{(m-1)},x_k=(b_k^{(k-1)}-a_{k,k+1}^{(k-1)}{x}_{k+1}-...-a_{km}^{(k-1)}{x}_m)/a_{kk}^{k-1},k=\overline{m-1,1}$

Трудоемкость:

1. m-1 деление, (m-1)m умножений, (m-1)m вычитаний $\Rightarrow Q_1=2(m-1{)}^2+3(m-1)$

k. $Q_k=2(m-k{)}^2+3(m-k)$

$Q=\sum _{k=1}^{n-1}{Q}_k=2\sum _{k=1}^{m-1}(m-k{)}^2+3\sum _{k=1}^{m-1}(m-k)=2\sum _{k=1}^{m-1}{k}^2+3\sum _{k=1}^{m-1}k=\frac{2(m-1)m(2m-1)}{6}+\frac{3(m-1)m}{2}\approx \frac{2}{3}{m}^3$

Обратный ход: $m^2$ операций. Необходимость выбора главных элементов: главный элемент не должен быть равен нулю. Если он близок к нулю, растет погрешность (это для ЭВМ).

Матричная форма метода Гаусса. (LU - разложение)

После первого шага получаем $A^{(1)}x=b^{(1)}$. Введем:

$M_1=\left(\begin{array}{ccccc}1& 0& 0& \dots & 0\\ -{\mu }_{21}& 1& 0& \dots & 0\\ -{\mu }_{31}& 0& 1& \dots & 0\\ \dots \\ -{\mu }_{m1}& 0& 0& \dots & 1\end{array}\right)M_2=\left(\begin{array}{ccccc}1& 0& 0& \dots & 0\\ 0& 1& 0& \dots & 0\\ 0& -{\mu }_{32}& 1& \dots & 0\\ \dots \\ 0& -{\mu }_{m2}& 0& \dots & 1\end{array}\right)$

$M_{m-1}=\left(\begin{array}{ccccc}1& 0& \dots & 0& 0\\ 0& 1& \dots & 0& 0\\ 0& 0& \dots & 0& 0\\ \dots \\ 0& 0& \dots & -{\mu }_{m,m-1}& 1\end{array}\right)$

$A^{(1)}=M_{1}A,b^{(1)}=M_{1}b,A^{(m-1)}=M_{m-1}{A}^{(m-2)},b^{(m-1)}=M_{m-1}{b}^{(m-2)}$

Начальная система: $M_{m-1}\cdot ...\cdot M_2\cdot M_1\cdot Ax=M_{m-1}\cdot ...\cdot M_2\cdot M_1\cdot b$.

$M_{m-1}\cdot ...\cdot M_2\cdot M_1\cdot A$ - верхняя треугольная матрица $=A^{(m-1)}$.

$L=M_1^{-1}{M}_2^{-1}...M_{m-1}^{-1}=\left(\begin{array}{ccccc}1& 0& 0& ...& 0\\ {\mu }_{21}& 1& 0& ...& 0\\ {\mu }_{31}& {\mu }_{32}& 1& ...& 0\\ \dots \\ {\mu }_{m1}& {\mu }_{m2}& {\mu }_{m3}& ...& 1\end{array}\right)$

Свойства элементарных матриц:

1. $\det M_i=1$
2. $M_i$ - нижние треугольные матрицы
3. $M_i^{-1}$ - тоже, только у $\mu$ вместо "-" стоит "+"

$A=LU$

Шаблон:МатТеорема Использование:

1. преобразуем $b$ в $b^{(m-1)}{b}^{(m-1)}=M_{m-1}...M_2{M}_{1}b$
2. Решаем систему $Ux=b^{(m-1)}$

Количество действий: $\frac{2}{3}{m}^3+2m^2$

Модификации Гаусса

1. на k-м шаге в качестве главного элемента выбираем максимальный по модулю коэффициент $a_{i_k,k}$ и переставляем строки.
2. на каждом шаге выбираем максимальный по модулю коэффициент из строк с номерами $i=k..m$ и переставляем строки (столбцы)

Масштабирование - делим каждое уравнение на наибольший по модулю коэффициент.

Метод Холецкого

$Ax=b$, $A$ - симметричная ($A=A^T$), положительно определенная ($\mathrm{\forall }x\ne 0:(Ax,x)>0$ - скалярное произведение $Ax$ на $x$) Проверка:

1. Все главные миноры положительны
2. $|a_{ii}|>\sum _{j\ne i}|a_{ij}|$ - диагональное преобладание
3. $|a_{jj}|>\sum _{i\ne j}|a_{ij}|$ - столбцовое преобладание

Специальное $LU$ - разложение: $A=L{L}^T$.

$L=\left(\begin{array}{cccc}{l}_{11}& 0& \dots & 0\\ l_{21}& l_{22}& \dots & 0\\ \dots \\ l_{m1}& l_{m2}& \dots & l_{mm}\end{array}\right)$

$\begin{array}{ccc}& l_{11}^2=a_{11}& \\ & l_{i1}{l}_{11}=a_{i1}& i=\overline{2,m}\\ & l_{21}^2+l_{22}^2=a_{i2}& \\ & l_{i1}{l}_{21}+l_{i2}{l}_{22}=a_{i2}& i=\overline{3,m}\\ & \dots & \\ & l_{k1}^2+l_{k2}^2+...+l_{kk}^2=a_{kk}& \\ & l_{i1}{l}_{k1}+...+l_{ik}{l}_{kk}=a_{ik}& i=\overline{k+1,m}\\ & \dots & \\ & l_{m1}^2+...+l_{mm}^2=a_{mm}& \end{array}\Rightarrow$

$\Rightarrow \begin{array}{ccc}& l_{11}=\sqrt{a_{11}}& \\ & l_{i1}=a_{i1}/l_{11}& i=\overline{2,m}\\ & l_{22}=\sqrt{a_{i2}-l_{21}^2}& \\ & l_{i2}=(a_{i2}-l_{i1}{l}_{21})/l_{22}& i=\overline{3,m}\\ & \dots & \\ & l_{kk}=\sqrt{a_{kk}-l_{k1}^2-...-l_{k,k-1}^2}& \\ & l_{ik}=(a_{ik}-l_{i1}{l}_{k1}-...-l_{i,k-1}{l}_{k,k-1})/l_{kk}& i=\overline{k+1,m}\\ & \dots & \\ & l_{mm}=\sqrt{a_{mm}-l_{m1}^2-...-l_{m,m-1}^2}& \end{array}$

После получения этого разложения решаем $Ly=b,L^{T}x=y$. Это решение требует $2m^2$ действий

Метод Прогонки

$\begin{array}{ccc}& b_1{x}_1+c_1{x}_2& =d_1\\ & a_2{x}_1+b_2{x}_2+c_2{x}_3& =d_2\\ & \dots \\ & a_i{x}_{i-1}+b_i{x}_i+c_i{x}_{i+1}& =d_i\\ & \dots \\ & a_{m-1}{x}_{m-2}+b_{m-1}{x}_{m-1}+c_{m-1}{x}_m& =d_{m-1}\\ & a_m{x}_{m-1}+b_m{x}_m& =d_m\end{array}$

Вывод:

$\begin{array}{c}{x}_1={\alpha }_1{x}_2+{\beta }_1{\alpha }_1=-\frac{c_1}{b_1}{\beta }_1=\frac{d_1}{b_1}\\ x_2={\alpha }_2{x}_3+{\beta }_2{\alpha }_2=-\frac{c_2}{b_2+a_2{\alpha }_1}{\beta }_2=\frac{d_2-a_2{\beta }_1}{b_2+a_2{\alpha }_1}\\ \dots \\ x_i={\alpha }_i{x}_{i+1}+{\beta }_i{\alpha }_i=-\frac{c_i}{b_i+a_i{\alpha }_{i-1}}{\beta }_i=\frac{d_i-a_i{\beta }_{i-1}}{b_i+a_i{\alpha }_{i-1}}\\ \dots \\ x_{m-1}={\alpha }_{m-1}{x}_m+{\beta }_{mm-1}\end{array}$

$m:a_m(a_{m-1}{x}_m+{\beta }_{m-1})+b_m{x}_m\Rightarrow x_m={\beta }_m=\frac{d_m-a_m{\beta }_{m-1}}{b_m+a_m{\alpha }_{m-1}}$

Алгоритм

Прямой ход:

$\begin{array}{cccc}{\alpha }_i& =-\frac{c_i}{{\gamma }_i}{\beta }_i=\frac{d_i}{{\gamma }_i}{\gamma }_i=b_i,& i=1;& \\ {\alpha }_i& =-\frac{c_i}{{\gamma }_i}{\beta }_i=\frac{d_i-a_i{\beta }_{i-1}}{{\gamma }_i}{\gamma }_i=b_i+a_i{\alpha }_{i-1},& i=2..m-1;& \\ {\beta }_i& =\frac{d_i-a_i{\beta }_{i-1}}{{\gamma }_i}{\gamma }_i=b_i+a_i{\alpha }_{i-1},& i=m.& \end{array}$

Обратный ход:

$\begin{array}{cc}i=m& x_m=b_m\\ i=m-1..1& x_i=a_i{x}_{i+1}+{\beta }_i\end{array}$

Количество операций: $Q=8m$.