На главную   ::   Содержание



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

Будем рассматривать систему вида $ Ax=b$, $ A$ -- квадратная матрица. Для больших размерностей нужны приближенные методы.

Будем строить решение в виде последовательности векторов $ x^0,x^1,\dots$. Если $ x^\ast$ -- решение, то последовательность должна сходиться к нему.

Определение 1.   $ x^0; x^{n+1}=S_n x^n+g_n$ -- общий вид одношагового нестационарного итерационного метода. Если $ S_n=s,
g_n=g$, то метод называется стационарным. Можно записать метод в канонической форме

$\displaystyle B_n\frac{x^{n+1}-x^n}{\tau_n}+Ax^n=b.$

Тогда метод называется явным, если $ B_n=E$, иначе неявный. Для перехода к общему виду в случае явного метода достаточно положить

$\displaystyle S_n=(E-\tau_n B_n^{-1}A); g_n=\tau_n B_n^{-1}b.$

Замечание 1.   Критерием сходимости данного метода в стационарном случае называют следующее утверждение: метод сходится $ \Leftrightarrow$ все собственные числа матрицы переходов $ S$ по модулю меньше единицы. Для матриц существует спектральная норма -- максимальное собственное число. Эта норма -- наименьшая. Т.е. достаточным условием сходимости является проверка какой-нибудь нормы матрицы, и если она меньше единицы, то и спектральная норма меньше единицы, т.е. выполнен критерий сходимости. В канонической форме достаточное условие сходимости выглядит так: матрица $ A$ -- симметрическая и $ B>\frac{\tau}{2}A$. Этим будем пользоваться в дальнейшем.

Метод Якоби.

Канонический вид метода

$\displaystyle D(x^{n+1}-x^n)+Ax^n=b,$

где $ D_{ij}=\begin{cases}0,&i\neq j\\
a_{ii},&i=j\end{cases}$. Если расписать в систему, то получим

\begin{displaymath}
\begin{cases}
x_1^{n+1}=-\frac{a_{12}}{a_{11}}x_2^n-\dots+\frac{b_1}{a_{11}}\\
\dots\\
\end{cases}
\end{displaymath}

По достаточному условию сходимости (здесь $ B=D$) получим $ D>\frac1{2}A$. Для этого достаточно диагонального преобладания и положительности элементов на главной диагонали. Если матрица $ A$ -- симметрическая и положительно определенная, то положительность элементов на главной диагонали гарантирована, т.к. $ (Ae_i,e_i)=a_{ii}>0$ по определению положительной определенности, тогда остается условие $ a_{ii}>\sum_{j\neq i}\vert a_{ij}$.

Метод Зейделя.

Этот метод похож на метод Якоби. Только на каждом последующем шаге, вычисляя $ x_i^{k+1}$, используются уже полученные значения $ x_{i-1}^{k+1},\dots,x_1^{k+1}$ и старые $ x_{i+1}^k,\dots,x_n^k$. Тогда канонический вид метода будет такой:

$\displaystyle (D+A^-)(x^{n+1}-x^n)+Ax^n=b,$

где матрица $ D$ такая же, а матрица $ A^-$ такая, что ниже главной диагонали в ней стоят элементы матрицы $ A$, а на ней и выше -- нули. Достаточное условие сходимости -- только симметричность и положительная определенность матрицы.

Метод релаксации.

Это обобщение метода Зейделя. Здесь есть константа $ \omega$, которая регулирует влияние предыдущего значения на новое. Канонический вид:

$\displaystyle (D+\omega A^-)\frac{x^{n+1}-x^n}{\omega}+Ax^n=b.$

Условие сходимости: $ A$ -- симметрическая и пол.опр., $ 0<\omega<2$.

Метод простых итераций.

Канонический вид

$\displaystyle \frac{x^{n+1}-x^n}{\tau}+Ax^n=b.$

Сходимость зависит от $ \tau$. Условие сходимости: матрица системы -- симметрическая и положительно определенная, $ \tau\leq
\frac2{\vert\vert A\vert\vert}$.

Метод минимальных невязок.

Внесем изменения в метод простых итераций так, чтобы на каждом шаге невязка $ r^n=Ax^n-b$ была бы минимальной. Канонический вид

$\displaystyle \frac{x^{n+1}-x^n}{\tau_{n+1}}+Ax^n=b.$

Можно получить следующий результат: $ \tau_{n+1}=\frac{(Ar^n,r^n)}{(Ar^n,Ar^n)}$.

Следующая группа методов основывается на теореме:

Теорема 1.   Для симметрической положительно определенной матрицы $ A$ вектор $ x^\ast$, который минимизирует функцию $ F(x)=(Ax,x)-2(x,b)$, одновременно является решением системы $ Ax=b$ и наоборот.

Метод градиентного спуска.

Для нахождения последующего приближения, будем сдвигаться на расстояние $ t^{n+1}$ в сторону градиента функции $ F$ в данной точке. Т.е. $ x^{n+1}=x^n-t^{n+1}\grad F(x)$. Можно получить следующий результат: $ t^{n+1}=\frac{(r^n,r^n)}{2(Ar^n,r^n)}$.



На главную   ::   Содержание