Постановка задачи[править]
Дана СЛАУ:
![{\displaystyle {\begin{cases}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{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50d26ee163d1112c38318bbb5cf1c4c40a877fc7)
![{\displaystyle A={\begin{pmatrix}a_{11}&\dots &a_{1m}\\\vdots &\ddots &\vdots \\a_{m1}&\dots &a_{mm}\end{pmatrix}}\quad x={\begin{pmatrix}x_{1}\\\vdots \\x_{m}\end{pmatrix}}\quad b={\begin{pmatrix}b_{1}\\\vdots \\b_{m}\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4cf1a21156f34a737aac31fd7ba5595572e9089)
Предполагаем, что
- невырожденная (
задача корректна).
- приближенное решение задачи.
Погрешность
. Невязка
Определение.
называется нормой вектора
, если обладает свойствами:
, ![{\displaystyle \|x\|=0\Leftrightarrow x=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/468488b6af2f2817e7228ee82b3789b343b4291e)
![{\displaystyle \|\alpha x\|=|\alpha |\|x\|\forall x\forall \alpha }](https://wikimedia.org/api/rest_v1/media/math/render/svg/79b1b62b5bf47882f3bb7813c725a91dbd39012c)
![{\displaystyle \|x+y\|\leq \|x\|+\|y\|\forall x,y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8d6ef6a470d8890ac6ca3d84c3ff798f6cabc04)
Три варианта задания нормы:
![{\displaystyle \|x\|_{1}=\sum _{i=1}^{m}|x_{i}|,\quad \|x\|_{2}=(\sum _{i=1}^{m}|x_{i}|^{2})^{\frac {1}{2}},\quad \|x\|_{\infty }=\max {1\leq i\leq m}|x_{i}|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6ebf13973788780026105084e0989ff7818cdec)
Скалярное произведение:
. Погрешности:
,
Определение. Сходимость по норме:
- последовательность векторов
при
, если
при
.
Норма матрицы
. Свойства:
![{\displaystyle \|A\|\geq 0\quad \|A\|=0\Leftrightarrow A=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a637a997cdd269768df5ee3126c0b507a29f72be)
![{\displaystyle \|\alpha A\|=|\alpha |\|A\|\forall A,\alpha }](https://wikimedia.org/api/rest_v1/media/math/render/svg/85a396f877e2951627838315cb9258ea3df0b338)
![{\displaystyle \|A+B\|\leq \|A\|+\|B\|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40903c28d5a238fac07dab341f5c936b4c9828ef)
![{\displaystyle \|A\cdot B\|\leq \|A\|\cdot \|B\|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4522512edbaa2df4529dab4123735382df4f04a)
![{\displaystyle \|Ax\|\leq \|A\|\cdot \|x\|\quad (\|x\|\neq 0\Rightarrow {\frac {\|Ax\|}{\|x\|}}\leq \|A\|-{\text{из определения}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3995b52d4267a9686ac8a6526d1c3389d6dde3e9)
![{\displaystyle \|A\|_{1}=\max {1\leq j\leq m}\sum _{i=1}^{m}|a_{ij}|,\quad \|A\|_{2}=\max {1\leq j\leq m}{\sqrt {\lambda _{j}(A^{T}A)}},\quad \|A\|_{\infty }=\max {1\leq j\leq m}\sum _{i=1}^{m}|a_{j}i|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d90bf598b4ab8f94b71ec9c710eea88a11de1337)
Это подчиненные нормы
Обусловленность задачи решения СЛАУ[править]
Лемма.
, где ![{\displaystyle r=b-Ax^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c2c9df84f5e6e10650f393b033d82e354ab5668)
Доказательство.
Теорема.
. Факты:
![{\displaystyle cond(E)=1\quad (E^{-1}=E,\|E\|=1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60220f7f89cae3cc8b0c466fd65f06a00f0f6ec8)
![{\displaystyle cond(A)\geq 1\quad (E=A^{-1}A,\|E\|\leq \|A^{-1}\|\cdot \|A\|)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab466685ec78c1695d03b88ff1b1fd3e7df21e96)
![{\displaystyle \forall \alpha \neq 0:cond(\alpha A)=cond(A)\quad (\|\alpha A\|\cdot \|\alpha A^{-1}\|=|\alpha |\|A\|\cdot |\alpha |^{-1}\|A^{-1}\|)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e91b5f89926bc5f1026eb7e6308553ea5fa112d)
Теорема.
- точное решение.
- приближено заданная матрица
. Тогда
, где
Доказательство.
Методы решения[править]
Прямой ход:
1-й шаг - пусть
. Найдем
. Из
уравнений вычитаем первое, домноженное на
. Получаем:
![{\displaystyle {\begin{matrix}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{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/008a25748d2c917829685d9aef717b9b9d2bf938)
2-й шаг - пусть
k-й шаг:
За (m-1) шаг получаем:
![{\displaystyle {\begin{matrix}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{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a11c2805fe127b4b49ed42bdddf50c9cdde6da9e)
Обратный ход:
Из последнего уравнения находим
, подставляем в предпоследнее, находим
.
Трудоемкость:
1. m-1 деление, (m-1)m умножений, (m-1)m вычитаний
k.
Обратный ход:
операций.
Необходимость выбора главных элементов: главный элемент не должен быть равен нулю. Если он близок к нулю, растет погрешность (это для ЭВМ).
Матричная форма метода Гаусса. (LU - разложение)[править]
После первого шага получаем
. Введем:
![{\displaystyle M_{1}={\begin{pmatrix}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{pmatrix}}M_{2}={\begin{pmatrix}1&0&0&\dots &0\\0&1&0&\dots &0\\0&-\mu _{32}&1&\dots &0\\\dots \\0&-\mu _{m2}&0&\dots &1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e13e87d9c9f43fa9286c41f848d7965a823654fd)
![{\displaystyle M_{m-1}={\begin{pmatrix}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{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cd65e3d0cf3616e322b5d9540c895c037f59820)
![{\displaystyle A^{(1)}=M_{1}A,b^{(1)}=M_{1}b,\quad A^{(m-1)}=M_{m-1}A^{(m-2)},b^{(m-1)}=M_{m-1}b^{(m-2)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da0c4d804ede1d7c8b0703c6c770ec7d808af2c5)
Начальная система:
.
- верхняя треугольная матрица
.
Свойства элементарных матриц:
![{\displaystyle \det M_{i}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5758e1ea4ef796096a62e25627b11b33367df918)
- нижние треугольные матрицы
- тоже, только у
вместо "-" стоит "+"
Теорема. Если все главные миноры матрицы
, то
нижняя треугольная матрица
вида
и верхняя треугольная матрица
такие, что
.
Использование:
- преобразуем
в ![{\displaystyle b^{(m-1)}\quad b^{(m-1)}=M_{m-1}...M_{2}M_{1}b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/854aeab880c5d78153c5729384f5082542cf8ce5)
- Решаем систему
![{\displaystyle Ux=b^{(m-1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7babb4b517158b1c1be3a6b231bcd66b42523082)
Количество действий:
Модификации Гаусса[править]
- на k-м шаге в качестве главного элемента выбираем максимальный по модулю коэффициент
и переставляем строки.
- на каждом шаге выбираем максимальный по модулю коэффициент из строк с номерами
и переставляем строки (столбцы)
Масштабирование - делим каждое уравнение на наибольший по модулю коэффициент.
Метод Холецкого[править]
,
- симметричная (
), положительно определенная (
- скалярное произведение
на
)
Проверка:
- Все главные миноры положительны
- диагональное преобладание
- столбцовое преобладание
Специальное
- разложение:
.
![{\displaystyle L={\begin{pmatrix}l_{11}&0&\dots &0\\l_{21}&l_{22}&\dots &0\\\dots \\l_{m1}&l_{m2}&\dots &l_{mm}\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f943b31dc75e23abe35c4e8c6ba7afda9aa6d0cc)
![{\displaystyle {\begin{matrix}&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{matrix}}\Rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c77d340cdd1e9f92b4a371af48ee6ae3fc251c5)
![{\displaystyle \Rightarrow {\begin{matrix}&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{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b50d07d777d1f8f81dd59bb6d04e6c5875429726)
После получения этого разложения решаем
. Это решение требует
действий
Метод Прогонки[править]
![{\displaystyle {\begin{matrix}&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{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/493d17fbe53c9f9a88df653d28261e8109350576)
Вывод:
![{\displaystyle {\begin{matrix}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{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d9f6a4bf9e7e7c1abd27b42d2c672ffad029ea9)
![{\displaystyle 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}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2cb9c0fa6ab81b7721a35ea28d3887bcd635d94)
Алгоритм
Прямой ход:
![{\displaystyle {\begin{aligned}\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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd6ae3b375c3f320f2c63c3716da500e1c91be5f)
Обратный ход:
![{\displaystyle {\begin{matrix}i=m&x_{m}=b_{m}\\i=m-1..1&x_{i}=a_{i}x_{i+1}+\beta _{i}\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2b8ebed3f78304c83beaa2d54871ec1f25a2880)
Количество операций:
.
Теорема. Пусть
. Тогда
и