Итерационные методы решения СЛАУ: метод Якоби, Зейделя, простой итерации

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

    В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.

    Общие сведения об итерационных методах или методе простой итерации

    Определение 1

    Метод итерации — это численный и приближенный метод решения СЛАУ.

    Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x0.

    Пример 1

    Рассмотрим систему Ax=b.

    Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x=Bx+d. Затем выбираем начальное приближение к решению СЛАУ x(0)=(x10, x20,...xm0)  и находим последовательность приближений к корню. 

    Для сходимости итерационного процесса является достаточным заданное условие В<1. Окончание итерации зависит от того, какой итерационный метод применили.

    Метод Якоби

    Определение 2

    Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x1, из 2-го выражаем неизвестное x2 и т.д.

    Результатом служит матрица В, в которой на главной диагонали находятся нулевые элементы, а все остальные вычисляются по формуле:

    bij=-aij/aii, i,j=1, 2..., n

    Элементы (компоненты) вектора d вычисляются по следующей формуле:

    di=bi/aii, i=1, 2,..., n

    Расчетная формула метода простой итерации:

    x(n+1)=Bx(x)+d

    Матричная запись (координатная):

    xi(n+1)=bi1xn1+bi2x(n)2+...+b

    Критерий окончания в методе Якоби:

    x(n+1)-x(n)<ε1, где ε1=1-BBε

    В случае если B<1/2, то можно применить более простой критерий окончания итераций:

    x(n+1)-x(n)<ε

    Пример 2

    Решить СЛАУ методом Якоби:

    10x1+x2-x3=11x1+10x2-x3=10-x1+x2+10x3=10

    Как решить?

    Необходимо решить систему с показателем точности ε=10-3.

    Приводим СЛАУ к удобному виду для итерации:

    x1=-0,1x2+0,1x3+1,1x2=-0,1x1+0,1x3+1x3=0,1x1-0,1x2+1

    Выбираем начальное приближение, например: x(0)=1,111 — вектор правой части.

    В таком случае, первая итерация имеет следующий внешний вид:

    x1(1)=-0,1×1+0,1×1+1,1=1,1x2(1)=-0,1×1,1+0,1+1=0,99x3(1)=0,1×1,1-0,1×1+1=1,01

    Аналогичным способом вычисляются приближения к решению:

    x(2)=1,1020,9911,011x(3)=1,1020,99091,0111x(4)=1,102020,990911,01111

    Находим норму матрицы В, для этого используем норму B.

    Поскольку сумма модулей элементов в каждой строке равна 0,2, то B=0,2<1/2, поэтому можно вычислить критерий окончания итерации:

    x(n+1)-x(n)<ε

    Далее вычисляем нормы разности векторов:

    x(3)-x(2)=0,002x(4)-x(3)=0,00002.

    Поскольку x(4)-x(3)<ε, то можно считать, что мы достигли заданной точности на 4-ой итерации.

    Ответ:

    x1=1,102x2=0,991x3=1,101.

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

    Определение 2

    Метод Зейделя — метод является модификацией метода Якоби.

    Суть: при вычислении очередного (n+1)-го приближения к неизвестному xi при i >1 используют уже найденные (n+1)-е приближения к неизвестным x1, x2, ..., xi 1, а не n-ое приближение, как в методе Якоби.

    Матричная запись:

    xi(n+1)=bi1x1(n+1)+bi2x2(n+1)+...+bi,i-1xi-2(n+1)+bi,i+1xi+1(n)+

    +...+bimxm(n)+di

    i=1, 2,...m...

    За условия сходимости и критерий окончания итераций можно принять такие же значения, как и в методе Якоби.

    Пример 2

    Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.

    Как решать?

    Решим 3 системы уравнений:

    2x1+x2=3x1-2x2=1x1+2x2=32x1-x2=12x1-0,5x2=32x1+0,5x2=1

    Приведем системы к удобному для итерации виду:

    x1(n+1)=-0,5x2(n)+1,5x2(n+1)=0,5x1(n+1)+0,5x1(n+1)=-2x2(n)+3x2(n+1)=2x1(n+1)-12x1-0,5x2=32x1+0,5x2=1.

    Отличительная особенность, условие сходимости выполнено только для первой системы:

    B<1

    Вычисляем 3 первых приближения к каждому решению:

    1-ая система: x(0)=1,5-0,5x(1)=1,750,375x(2)=1,31250,1563x(3)=1,42190,2109

    Решение: x1=1,4x2=0,2. Итерационный процесс сходится.

    2-ая система: x(0)=3-1x(1)=59x(2)=-15-31x(3)=65129

    Итерационный процесс разошелся.

    Решение: x1=1, x2=2

    3-я система: x(0)=1,52x(1)=2-6x(2)=02x(3)=02

    Итерационный процесс зациклился.

    Решение: x1=1, x1=2

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

    Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:

    x=x-τ(Ax-b), τ - итерационный параметр.

    Расчетная формула имеет следующий внешний вид:

    x(n+1)=x(n)-τ(Axn-b).

    Здесь B=E-τA и параметр τ>0 выбирают таким образом, чтобы по возможности сделать максимальной величину B2.

    Пусть λmin и λmax - максимальные и минимальные собственные значения матрицы А.

    τ=2/(λmin+λmax) - оптимальный выбор параметра. В этом случае B2 принимает минимальное значение, которое равняется (λmin+λmax)/(λmin-λmax).

    Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
    Средняя оценка статьи
    5,0 из 5 (8 голосов)