Итерационный процесс решения системы уравнений сходится

Сходимости итерационного процесса

Итерационный процесс будет сходящимся, если модуль коэффициента на главной диагонали больше суммы (или равен сумме) модулей остальных элементов строки (свободные члены при этом не учитываются)

Это достаточное условие сходимости, но не необходимое, т.е. данное условие гарантирует сходимость итерационного процесса. Условие не является чрезмерным в электрических системах оно часто выполняется, в том числе для матриц узловых проводимостей Y_у при решении систем узловых уравнений Y_iU_у=I_у и контурных сопротивлений Z_к при решении системы контурных уравнений Z_кI_к= .

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

Пример: Условие сходимости не выполняется

Поменяем строки местами

, т.е.

Или поменяем столбцы местами

, т.е.

Условие сходимости также выполняется.

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

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

Метод Зейделя представляет модификацию метода простой итерации. Идея состоит в том, что на каждой к-й итерации при вычислении значения переменной используются значения переменных , . . . . , , уже подсчитанных на этой же к-й итерации.

Пример:

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

Зададимся исходным приближением и ε = 0,001.

Делаем первую итерацию по методу Зейделя

;

;

Занесем результаты расчетов в таблицу

№ итерации (к)
1,2	1,06	0,948
0,9992	1,00548	0,9991
0,9996	1,0002	1,0000
1,0000	1,0000	1,0000

Метод Зейделя, имеет, как правило, лучшую сходимость, чем метод простой итерации. И сходится в ряде случаев даже тогда, когда метод простой итерации не обеспечивает сходимость. Но (значительно реже) бывает и наоборот.

Дата добавления: 2016-02-16 ; просмотров: 6067 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Метод итераций решения системы уравнений. Пример решения

Решение получаем с помощью калькулятора Решение СЛАУ методом итераций .

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

Прежде чем применять метод итераций, необходимо переставить строки исходной системы таким образом, чтобы на диагонали стояли наибольшие по модулю коэффициенты матрицы. Если при этом условие все таки не выполняется, то иногда удается обеспечить сходимость метода с помощью следующего метода.
Пусть дана система Ax = b. Преобразуем ее к виду: x= Qx + c
где Q = E — D•A, c = D•b
Здесь D — некоторая матрица. Нам необходимо подобрать такую матрицу D, чтобы выполнялось условие |Q| 0 =β, тогда:
x 1 =b — a x 0
x 2 =b — a x 1
.
x k+1 =b — a x k
Для нашей задачи достаточное условие сходимости выполняется.

Приведем к виду:
x₁=0.5-(0.2x₂-0.1x₃)
x₂=-4.07-(0.33x₁+0.17x₃)
x₃=3-(0.0833x₁-0.25x₂)
Покажем вычисления на примере нескольких итераций.
N=1
x₁=0.5 — 0 • 0.2 — 0 • (-0.1)=0.5
x₂=-4.07 — 0 • 0.33 — 0 • 0.17=-4.07
x₃=3 — 0 • 0.0833 — 0 • (-0.25)=3
N=2
x₁=0.5 — (-4.07) • 0.2 — 3 • (-0.1)=1.61
x₂=-4.07 — 0.5 • 0.33 — 3 • 0.17=-4.74
x₃=3 — 0.5 • 0.0833 — (-4.07) • (-0.25)=1.94
N=3
x₁=0.5 — (-4.74) • 0.2 — 1.94 • (-0.1)=1.64
x₂=-4.07 — 1.61 • 0.33 — 1.94 • 0.17=-4.93
x₃=3 — 1.61 • 0.0833 — (-4.74) • (-0.25)=1.68
Остальные расчеты сведем в таблицу.

Ответ: x₁=1.64, x₂=-4.89, x₃=1.64

Пример №2 . Решить систему уравнений Ax = b с точностью 0.05 методами: 1) простой итерации; 2) Зейделя. Указание. Для обеспечения выполнения достаточного условия сходимости воспользоваться перестановкой строк в исходной системе уравнений.

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

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

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

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

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