Метод гаусса зейделя кратко

Обновлено: 05.07.2024

Назначение сервиса . Сервис предназначен для решения СЛАУ в онлайн режиме методом Зейделя. Дополнительно генерируется шаблон решения в Excel . Метод Зейделя представляет собой модификацию метода простой итераций.

Метод Зейделя представляет собой модификацию метода простой итераций.
Пусть дана приведённая система:

и известно начальное приближение (x 0 ₁, x 0 ₂. x 0 _n)=x 0 . Основная идея заключается в том, что при вычислении (k+1) - го приближения неизвестной xi учитываются уже вычисленные ранее (k+1) - приближение неизвестных x₁, x₂, . x_i_-1.
Итерационная схема имеет вид:

Положим α = B + C, где
; .
Тогда процесс Зейделя в матричном виде можно записать как:
x k +1 = B x k +1 + C x k + β

Процесс Зейделя для нормальной системы

матрица С – симметрическая;
все элементы главной диагонали c_ij > 0;
матрица С - положительно определена.

Достаточные условия сходимости итерационной последовательности

Достаточные условия сходимости итерационной последовательности приближенных решений системы и оценка погрешности проводятся по тем же формулам, что и в методе простой итерации.

Пример №1 . Рассмотрим вычисление двух приближений по методу Зейделя для примера, решенного выше для метода простой итерации и оценим погрешность.
Вычисления будем проводить по формулам:

Выбираем начальное приближение: x (0) =(0;0;0) и получаем:
x (1) =(-1,9022;0,6791;1,2091), x (2) =(-1,6004;0,6291;1,3498).

Пример №2 . Система двух Линейных Алгебраических Уравнения (СЛАУ) с двумя неизвестными задана своей расширенной матрицей. Решите СЛАУ методом Зейделя с точностью до 0.001. Поменяйте порядок уравнений в СЛАУ и решите полученную таким образом СЛАУ тем же методом Зейделя. Постройте графики уравнений СЛАУ в обоих СЛАУ в обоих случаях и покажите на них первые три-четыре итерации.

Пример №3 . Методом Зейделя решить с точностью 0,001 систему линейных уравнений, приведя ее к виду, удобному для итерации.
3.6x₁ + 1.8x₂ - 4.7x₃ = 3.8
2.7x₁ - 3.6x₂ + 1.9x₃ = 0.4
1.5x₁ + 4.5x₂ + 3.3x₃ = -1.6
Решение. Умножаем матрицы A T A.

Приведем к виду:
x₁=0.55+0.16x₂-0.3x₃
x₂=-0.0494+0.0963x₁-0.0123x₃
x₃=-0.61-0.19x₁-0.0123x₂
Покажем вычисления на примере нескольких итераций.
N=1
x₁=0.55 - 0 • 0.16 - 0 • (-0.3)=0.55
x₂=-0.0494 - 0.55 • 0.0963 - 0 • (-0.0123)=-0.1
x₃=-0.61 - 0.55 • (-0.19) - (-0.1) • (-0.0123)=-0.51
N=2
x₁=0.55 - (-0.1) • 0.16 - (-0.51) • (-0.3)=0.41
x₂=-0.0494 - 0.41 • 0.0963 - (-0.51) • (-0.0123)=-0.0952
x₃=-0.61 - 0.41 • (-0.19) - (-0.0952) • (-0.0123)=-0.54
N=3
x₁=0.55 - (-0.0952) • 0.16 - (-0.54) • (-0.3)=0.4
x₂=-0.0494 - 0.4 • 0.0963 - (-0.54) • (-0.0123)=-0.0946
x₃=-0.61 - 0.4 • (-0.19) - (-0.0946) • (-0.0123)=-0.54
Остальные расчеты сведем в таблицу.

N	x₁	x₂	x₃	e₁	e₂	e₃
0	0	0	0
1	0.55	-0.1	-0.51	0.55	0.1	0.51
2	0.41	-0.0952	-0.54	-0.14	-0.0071	0.0259
3	0.4	-0.0946	-0.54	-0.00899	-0.000546	0.00167
4	0.4	-0.0946	-0.54	-0.000594	-3.7E-5	0.000111

Ответ: x₁ = 0.4; x₂ = -0.0946; x₃ = -0.54.

Пример №4 . Выполнить три итерации по методу Зейделя для системы уравнений Ax=b (не переставляя строк). В качестве начального приближения взять нулевой вектор. Изобразить графически поведение итерационного процесса. Сопоставить его сходимость с выполнением достаточных условий сходимости метода.

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

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

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

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

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

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

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

Метод Якоби

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

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

b i j = - a i j / a i i , i , j = 1 , 2 . . . , n

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

d i = b i / a i i , i = 1 , 2 , . . . , n

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

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

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

x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b

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

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

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

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

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

10 x 1 + x 2 - x 3 = 11 x 1 + 10 x 2 - x 3 = 10 - x 1 + x 2 + 10 x 3 = 10

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

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

x 1 = - 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = - 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 - 0 , 1 x 2 + 1

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

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

x 1 ( 1 ) = - 0 , 1 × 1 + 0 , 1 × 1 + 1 , 1 = 1 , 1 x 2 ( 1 ) = - 0 , 1 × 1 , 1 + 0 , 1 + 1 = 0 , 99 x 3 ( 1 ) = 0 , 1 × 1 , 1 - 0 , 1 × 1 + 1 = 1 , 01

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

x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111

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

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

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

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

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

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

x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .

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

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

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

x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i - 1 x i - 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +

+ . . . + b i m x m ( n ) + d i

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

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

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

2 x 1 + x 2 = 3 x 1 - 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 - x 2 = 1 , 2 x 1 - 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1

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

x 1 ( n + 1 ) = - 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = - 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) - 1 , 2 x 1 - 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .

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

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

1-ая система: x ( 0 ) = 1 , 5 - 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109

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

2-ая система: x ( 0 ) = 3 - 1 , x ( 1 ) = 5 9 , x ( 2 ) = - 15 - 31 , x ( 3 ) = 65 129

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

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

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

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

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

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

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

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

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

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

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

Пусть λ m i n и λ m a x - максимальные и минимальные собственные значения матрицы А .

τ = 2 / ( λ m i n + λ m a x ) - оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n - λ m a x ) .

Данный метод является одним из самых распространенных итерационных методов решения СЛАУ, поскольку он отличается простотой и легкостью программирования. Рассмотрим его суть. Допустим, диагональные коэффициенты исходной матрицы a_ij>отличны от нуля (в противном случае можно переставить местами уравнения исходной системы). Представим исходную систему (2.1) в следующем виде:

Если теперь задать для неизвестных их начальные приближенные значения , то система (2.5) позволяет вычислить более точные значения неизвестных на первом шаге (на первой итерации):

Используя найденные значения неизвестных, можно еще более уточнить их на второй итерации:

В данном методе для нахождения значения i-го неизвестного на каждой итерации используются значения предыдущих неизвестных, уже найденные на данной итерации. Общую формулу определения i-го неизвестного на k-й итерации для системы n уравнений можно записать так:

i = 1, 2, … , n; k = 1, 2, …

(2.8)

Итерационный процесс продолжается до тех пор, пока все значения x_i ( k ) ,не станут достаточно близкими к x_i ( k -1) . Близость этих значений можно охарактеризовать максимальной абсолютной величиной их разности d. Тогда при заданной точности вычислений e > 0 критерий окончания итерационного процесса можно записать в виде

При выполнении этого условия итерационный процесс называется сходящимся. В этом случае максимальные разности между значениями соответствующих неизвестных в двух последовательных итерациях убывают, а сами значения стремятся к решению системы.

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

При этом хотя бы для одного уравнения неравенство (2.10) должно выполняться строго.

В качестве примера рассмотрим решение методом Гаусса-Зейделя системы (2.2). Заметим, что достаточное условие сходимости итерационного процесса (2.10) для этой системы соблюдается. Запишем исходную систему в виде

В качестве начальных приближений возьмем нули, т.е. примем x₂ (0) = x₃ (0) = 0.

Найдем значения неизвестных на первой итерации:

Далее произведем вторую итерацию:

Производя аналогично третью и последующие итерации, найдем:

Нетрудно заметить, что разности между значениями соответствующих неизвестных в процессе итераций убывают, следовательно, процесс решения сходящийся, что и следовало ожидать. Если принять точность вычислений e = 0,02, то итерации следует закончить. При увеличении заданной точности вычисления корней, число итераций возрастает, например, при e = 0,00001 следует выполнить 11 итераций, а результат будет x₁ (11) = 1,000000; x₂ (11) = 1,999998; x₃ (11) = 2,999999.

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

program SLAU2;

label 1,2,3;

const n=3;

var a:array [1..n,1..n] of real;

b,x:array [1..n] of real;

i,j,k,m:integer;

e,s,d,d1,c:real;

Begin

for i:=1 to n do

Begin

writeln (‘Введите коэффициенты уравнения’,i);

for j:=1 to n do read (a[i,j]);

writeln (‘Введите свободный член уравнения’,i);

readln (b[i]);

end;

writeln ('Введите точность');readln (e);

writeln ('Введите допустимое кол-во итераций');readln (m);

for i:=2 to n do x[i]:=0;

k:=1;

Repeat

d1:=0;

for i:=1 to n do

Begin

s:=0;

for j:=1 to n do

Begin

if i=j then goto 1;

s:=s+a[i,j]*x[j];

1: end;

d:=abs(c-x[i]);

if d1 m then goto 2;

until d1

Используя найденные значения неизвестных, можно еще более уточнить их на второй итерации:

i = 1, 2, … , n; k = 1, 2, …

(2.8)

При этом хотя бы для одного уравнения неравенство (2.10) должно выполняться строго.

В качестве начальных приближений возьмем нули, т.е. примем x₂ (0) = x₃ (0) = 0.

Найдем значения неизвестных на первой итерации:

Далее произведем вторую итерацию:

Производя аналогично третью и последующие итерации, найдем:

program SLAU2;

label 1,2,3;

const n=3;

var a:array [1..n,1..n] of real;

b,x:array [1..n] of real;

i,j,k,m:integer;

e,s,d,d1,c:real;

Begin

for i:=1 to n do

Begin

writeln (‘Введите коэффициенты уравнения’,i);

for j:=1 to n do read (a[i,j]);

writeln (‘Введите свободный член уравнения’,i);

readln (b[i]);

end;

writeln ('Введите точность');readln (e);

writeln ('Введите допустимое кол-во итераций');readln (m);

Решение системы уравнений методом Гаусса-Зейделя — это решение системы уравнений при помощи последовательных замещений, которые считаются стандартным итерационным методом решения системы линейных уравнений.

Введение

При решении определённых классов прикладных задач появляется потребность в определении корней СЛАУ (системы линейных алгебраических уравнений). Методики решения СЛАУ подразделяются на следующие большие классы:

Точные методы решения, такие как, к примеру, метод Гаусса, способны определить точные значения корней СЛАУ, причём при правильной организации программы точность может определяться лишь погрешностями, которые сопряжены с округлениями и представлениями чисел в электронных вычислительных машинах (ЭВМ).

Итерационные методики решения СЛАУ могут быть охарактеризованы тем фактом, что точное решение системы они способны определить только в качестве предела определённой бесконечной очерёдности векторов. Исходное приближение при этом должно быть найдено каким-нибудь иным методом или задано произвольно. При исполнении заданных требований может быть получен оперативно сходящийся к решению итерационный процесс. К данному типу методологий могут быть отнесены метод итераций и метод Зейделя.

Решение системы уравнений методом Гаусса-Зейделя

Предположим, что необходимо решить систему уравнений следующего вида:

Рисунок 1. Система уравнений. Автор24 — интернет-биржа студенческих работ

Готовые работы на аналогичную тему

Приведённая выше система уравнений может быть записана в матрично-векторной форме:

Здесь А является матрицей коэффициентов системы, которая содержит n строк и n столбцов. В является заданным вектором правых частей. Х является искомым вектором.

Метод Гаусса базируется на известном из обычного школьного курса алгебры методе исключений. Путём комбинирования каким-нибудь образом уравнений системы, можно добиться того, что во всех уравнениях, кроме одного, исключается одна неизвестная. Далее исключаются следующая неизвестная, третья и так далее.

Пусть имеется система уравнений размера n х n. Алгоритм Гауссова исключения имеет в своём составе несколько шагов. Если система записана в указанном выше исходном виде, то первым шагом станет исключение х из последних n-1 уравнений. Это может быть достигнуто путём вычитания из второго уравнения первого, умноженного на $а_ / а_$, из третьего уравнения первого, умноженного на $а_ / а_$, и так далее. В результате этого процесса получается преобразованная система уравнений.

Рисунок 2. Преобразованная система уравнений. Автор24 — интернет-биржа студенческих работ

Если теперь применить такой же самый процесс к последним n-1 уравнениям данной системы, то можно исключить $х_2$ из последних n - 2 уравнений и так далее, пока вся система не превратится в треугольную форму. В этой форме верхние индексы показывают, какое количество раз менялись соответствующие коэффициенты. Этим завершается фаза, которая считается прямым исключением (или приведением к треугольной форме) алгоритма гауссова исключения. Решение треугольной системы может быть легко получено на фазе обратной подстановки, при которой уравнения, приведённой выше системы, могут решаться в обратном порядке.

Метод Зейделя является некоторой модификацией метода простой итерации. Главная его идея состоит в том, что при вычислении (k+1)-го приближения неизвестной xi должны учитываться уже вычисленные ранее (k+1) – е приближения неизвестных $х_1, х_2, . х_$. В данном методе, аналогично методу простой итерации, следует привести систему к определённому виду, чтобы диагональные коэффициенты были максимальными по модулю, а далее нужно проверить условия сходимости. Условия сходимости метода Зейделя можно сформулировать в следующем виде. Для того чтобы итерационный процесс удовлетворял условиям сходимости, необходимо и достаточно, чтобы суммарная величина абсолютных значений компонентов каждой строки (за исключением диагональной строки) была меньше, чем абсолютное значение диагонального компонента соответствующей строки.

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

при этом они должны хотя бы в какой-то мере соответствовать искомым неизвестным. За нулевое приближение может быть принят столбец свободных членов, то есть х(0) = b, а именно x1(0)=b1, x2(0)=b2, x3(0)=b3. Определим первое приближение х(1) по формулам:

Рисунок 3. Формулы. Автор24 — интернет-биржа студенческих работ

Необходимо учитывать особенность метода Зейделя, состоящую в том, что найденное в первом уравнении значение х1(l) сразу же применяется во втором уравнении, а значения х1(1), х2(1) применяются в третьем уравнении и так далее. То есть все найденные значения х1(1) необходимо подставить в уравнения для определения хi+1(1).

Действующие формулы метода Зейделя для системы трех уравнений будут иметь следующий вид:

Рисунок 4. Формулы. Автор24 — интернет-биржа студенческих работ

Для системы из n-уравнений рабочие формулы имеют следующий вид:

Рисунок 5. Формулы. Автор24 — интернет-биржа студенческих работ

Читайте также: