Метод покоординатного спуска относится к, метод покоординатного спуска что это, метод покоординатного спуска геометрическая интерпретация

У этого термина существуют и другие значения, см. метод покоординатного спуска.

Метод Гаусса—Зейделя^[1] является классическим итерационным методом решения системы линейных уравнений.

Содержание

1 Постановка задачи
2 Метод
3 Условие сходимости
4 Условие окончания
5 Пример алгоритма на с++
6 Пример алгоритма на pascal (для кв. системы)
7 Примечания
8 См. также

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

Возьмём систему: , где $A=\left( \begin{array}{ccc} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{array} \right),\quad \vec{b}=\left( \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right)$

Или $\left\{ \begin{array}{rcl} a_{11}x_1 + \ldots + a_{1n}x_n& = & b_{1} \\ & &\\ a_{n1}x_1 + \ldots + a_{nn}x_n & = & b_{n} \end{array} \right.$

И покажем, как её можно решить с использованием метода Гаусса-Зейделя.

Метод

Чтобы пояснить суть метода, перепишем задачу в виде:

$\left\{ \begin{array}{lcr} a_{11}x_1 & = &-a_{12}x_2 - a_{13}x_3 -\ldots - a_{1n}x_n + b_1\\ a_{21}x_1 + a_{22}x_2 & = & -a_{23}x_3 - \ldots - a_{2n}x_n + b_2\\ \ldots & &\\ a_{(n-1)1}x_1 + a_{(n-1)2}x_2 +\ldots+ a_{(n-1)(n-1)}x_{n-1} & = & -a_{(n-1)n}x_n + b_{n-1}\\ a_{n1}x_1 + a_{n2}x_2 +\ldots+ a_{n(n-1)}x_{n-1}+ a_{nn}x_n & = & b_n \end{array} \right.$

Здесь в -м уравнении мы перенесли в правую часть все члены, содержащие , для . Эта запись может быть представлена:

где в принятых обозначениях D означает матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы A, а все остальные нули; тогда как матрицы U и L содержат верхнюю и нижнюю треугольные части A, на главной диагонали которых нули.

Итерационный процесс в методе Гаусса-Зейделя строится по формуле после выбора соответствующего начального приближения .

Метод Гаусса-Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что новые значения используются здесь сразу же по мере получения, в то время как в методе Якоби они не используются до следующей итерации:

$\left\{\begin{array}{ccccccccccc} {x_{1}}^{(k+1)} &=& c_{12}{x_2^{(k)}} &+& c_{13}x_3^{(k)}&+& {\ldots}&+& c_{1n}{x_n}^{(k)} &+& d_1 \\ {x_{2}}^{(k+1)} &=& c_{21}{x_1^{(k+1)}} &+& c_{23}x_3^{(k)}&+& {\ldots}&+& c_{2n}{x_n}^{(k)} &+& d_2 \\ \ldots & & & & & & & & & & \\ {x_{n}}^{(k+1)} &=& c_{n1}{x_1^{(k+1)}} &+& c_{n2}{x_2^{(k+1)}}&+& {\ldots}&+& c_{n(n-1)}{x_{n-1}}^{(k+1)} &+& d_n \end{array}\right.,$

где

Таким образом i-тая компонента -го приближения вычисляется по формуле:

Условие сходимости

Приведём достаточное условие сходимости метода.

Теорема.
Пусть , где – матрица, обратная к . Тогда при любом выборе начального приближения :

метод Гаусса-Зейделя сходится;
скорость сходимости метода равна скорости сходимости геометрической прогрессии со знаменателем ;
верна оценка погрешности: .

Условие окончания

Условие окончания итерационного процесса Зейделя при достижении точности в упрощённой форме имеет вид:

Более точное условие окончания итерационного процесса имеет вид

и требует больше вычислений. Хорошо подходит для разреженных матриц.

Пример алгоритма на с++

 // Условие сходимости
bool converge(double *xk, double *xkp)
{
    for (int i = 0; i < n; i++) 
    {
        if (fabs(xk[i] - xkp[i]) >= eps) 
            return false;
    }
    return true;
}
 
/*
    Ход метода, где:
    a[n][n] - Матрица коэффициентов
    x[n], p[n] - Текущее и предыдущее решения
*/
 
do
{
    for (int i = 0; i < n; i++)
    {
        double var = 0;
        for (int j = 0; j < n; j++)
            if (j != i) var += (a[i][j] * x[j]);
        p[i] = x[i];
        x[i] = (b[i] - var) / a[i][i];
    }
}
while (!converge(x, p));

Пример алгоритма на pascal (для кв. системы)

type ar2d=array[1..50,1..50] of double;
     ar1d=array[1..50] of double;
 
procedure seidel(n:byte;e:extended;a:ar2d;b:ar1d;x:ar1d);
var i,j:longint;
    s,v,m:double;
begin
// проверка на совместность
for i:=1 to n do
 begin
 s:=0;
 for j:=1 to n do
  if j<>i then s:=s+abs(a[i,j]);
 if s>=abs(a[i,i]) then
  begin
  writeln('SLAE is uncompactible');
  exit
  end;
end;
// Сам алгоритм
repeat
m:=0;
for i:=1 to n do
 begin
 s:=0;
 for j:=1 to n do
   if i<>j then 
     s:=s+a[i,j]*x[j];
 v:=x[i];
 x[i]:=(b[i]-s)/a[i,i];
 if abs(v-x[i])>m then m:=abs(v-x[i]);
 end;
until m<e;
// OUTPUTTING
writeln('roots: ');
for i:=1 to n do writeln('x[',i,']= ',x[i]:0:4);
end;

Примечания

↑ Людвиг Зейдель (1821—1896) — немецкий астроном и математик, Карл Фридрих Гаусс (1777—1855) — немецкий математик, астроном и физик

См. также

Метод покоординатного спуска относится к, метод покоординатного спуска что это, метод покоординатного спуска геометрическая интерпретация.

Krasorion.ru

Упаковочные материалы

Категории