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

Пусть дана система n линейных уравнений с n переменными:

а₁₁x₁+a₁₂+…+a_1nx_n=b₁

а₂₁x₁+a₂₂+…+a_2nx_n=b₂ (1)

………………………

a_n1x₁+a_n2+…+a_nnx_n=b_n

с/ п равносильных преобразований приведем эту систему к виду:

x₁=ά₁₂* x2+…+ ά_1n * x_n+ß₁ (2)

x₂=ά₂₂* x2+…+ ά_2n * x_n+ß₂

……………………………..

x_n=ά_n2* x2+…+ ά_nn * x_n+ ß_n

о ситеме 2 говорят, что она приведена к норм.виду

используя правую часть норм.системы 2 и выбрав начальную точку:

x⁰( ; ; ; …; ) – начальная точка.

Можно построить итерационную последовательность точек:

x⁰, x¹,x², … , xⁿ,...(3)

при определенных условиях итерационная последовательность 3 сходиться к решению системы 2 и тем самым системы 1.

Сформулируем эти условия. Решение этого вопроса зависит от способа метризации пространства, т.е определения расстояния между двумя его точками. Существует несколько способов метризации.

Пусть x(x₁, x₂,...,x_n) и y (y₁, y₂,…, y_n) две точки пространства для применения метода простой итерации СЛАУ удобно поместить в пространство с одной из 3- х метрик:

1) ρ₁(x ,y) = max (4)

1 ≤ i ≤ n

2) ρ₂(x ,y) = (5) евклидова метрика

3) ρ₃(x ,y) = (6)

Условия сходимости последовательности 3 в пространствах с метриками ρ₁, ρ₂, ρ₃выражается через коэффициенты α_ij.

1. В пространстве с метрикой ρ₁:

γ₁ = max (7)

1 ≤ i ≤ n

Т.еmax из сумм модулей коэффициентов взятых по строкам должны быть меньше 1.

2. С метрикой ρ₂:

γ₂ = max (8)

1 ≤ i ≤ n

Т.еmax из сумм модулей коэффициентов взятых по столбцам должны быть меньше 1.

3. С метрикой ρ₃:

γ₃ = (9)

т.е корень из суммы квадратов всех коэффициентов должны быть меньше 1.

Замечание: Каждая из условий (7)-(9) является достаточным, но не является необходимым для результативности метода итераций, т.е итерационная последовательность 3 может оказаться сходящейся и при не выполнение не одного из этих уловий.

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

Результатом установления одного из условий (7)-(9) является получение значения γ которое затем используется для оценки погрешности:

ρ (x^(k); x^(k-1)) ≤ (10), где ρ – метрика по которой была установлена сходимость и выбрано значение γ.

Практика по методу простой итерации:

Решить систему методом простой итерации

(2)

α₂₁ =3; α₂₂ = 0; α₂₃= ; β₂ = ;

α₃₁ =2; α₃₂ = 16; α₃₃ = 0 ;β₃ = - 5;

т.к , то

для этого систему 1 приводим к виду с преобладающими диагональными коэффициентами:

(2)

α₁₁ =0; α₁₂ = ; α₁₃ = ; β₁ = ;

α₂₁ = ; α₂₂ = 0; α₂₃= ; β₂ = ;

α₃₁= ; α₃₂ = ; α₃₃ = 0 ; β₃ = - ;

γ₁<1; γ₂<1; γ₃<1;

γ₁ = = { }

γ₂= = { }

γ₃= =

т.к для всех γ; выполняется условие γ<1, то для критерия сходимости мы можем выбрать любую γ и соответствующую ей метрику; выберем γ₁ в качестве начальной точки выберем столбец ρ; x⁽⁰⁾ = ,для нахождения точки x⁽¹⁾ воспользуемся системой вида 2 в которую подставим значение x⁽⁰⁾

x₁⁽¹⁾ = = = ;

x₂⁽¹⁾ = =

x₃⁽¹⁾ =

ρ (x^(k); x^(k-1)) ≤

ρ₁ (x^(k); x^(k-1)) ≤

ρ₁ (x⁽¹⁾; x⁽⁰⁾)≤ max = =

( + )

Ответ: корень уравнения с заданной точностью

(x₁=5/24;x₂=55/192;x₃= -31/192)

Если неравенство оказалось неверным, то находим следующее приближение x²( ; ; ).

ρ₁ (x⁽²⁾; x⁽¹⁾) ≤

ρ₁ = max

Поиск по сайту: