Метод итерации для системы двух уравнений

Решение СЛАУ методом простой итерации

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

• Шаг №1
• Шаг №2
• Видеоинструкция

Рассмотрим достаточные условия сходимости итерационной последовательности n>.
Практически, для применения метода итерации систему линейных уравнений удобно «погрузить» в одну из трёх следующих метрик:
(3.4)
Для того, чтобы отображение F, заданное в метрическом пространстве соотношениями (3.2), было сжимающим, достаточно выполнение одного из следующих условий:
а) в пространстве с метрикой ρ₁: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по строкам, должна быть меньше единицы.
б) в пространстве с метрикой ρ₂: , т. е. максимальная из сумм модулей коэффициентов в правой части системы (3.2), взятых по столбцам, должна быть меньше единицы.
в) в пространстве с метрикой ρ₃: , т. е. сумма квадратов при неизвестных в правой части системы (3.2) должна быть меньше единицы

Пример . Вычислить два приближения методом простой итерации. Оценить погрешность второго приближения. В качестве начального приближения выбрать x 0 =(0; 0; 0).

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

Последовательные приближения будем искать по формулам:

Получаем:
x 1 =(-1.9022; 0.4889; 2.1456), x 2 =(-1.1720; 0.6315; 1.2389).
Для оценки погрешности в метрике ρ₁ вычисляем коэффициент μ
.
Вычисляем погрешность:

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

Метод итераций для системы уравнений в Excel

Для вычисления точности epsilon .
Итерация №1: =ABS(B7)-ABS(B6);=ABS(C7)-ABS(C6);=ABS(D7)-ABS(D6)
Итерация №2: =ABS(B8)-ABS(B7);=ABS(C8)-ABS(C7);=ABS(D8)-ABS(D7)
Скачать шаблон решения.

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

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

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

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

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

Метод итерации для системы двух уравнений

Пусть даны два уравнения с двумя неизвестными

(15.1),

действительные корни которых надо найти с заданной степенью точности.

Пусть х = х₀; у = у₀ – приближенные значения корней системы (15.1), полученные каким-либо способом (графическим, грубой прикидкой). Для этого представим систему (15.1) в виде

(15.2)

и построим последовательные приближения по формулам

(15.3)

Если итерационный процесс (15.3) сходится, т.е. существуют пределы

и ,

то, предполагая функции j₁(x, y) и j₂(x, y) непрерывными и переходя к пределу в равенстве (15.3) общего вида, получим:

,

т.е. предельные значения x и h являются корнями системы (15.2), а, следовательно, и (15.1). Взяв достаточно большое число итераций (15.3), мы получим числа x_n и y_n, которые будут отличаться от точных корней x = x и y = h сколь угодно мало. Для решения системы таким образом итерационный процесс должен быть сходящимся.

Теорема. Пусть в некоторой замкнутой окрестности R<a £ x £ A; b £ y £ B> имеется одна и только одна пара корней x = x и y = h системы (15.1).

Если: 1) функции j₁(x, y) и j₂(x, y) определены и непрерывно дифференцируемы в R;

2) начальные приближения x₀, y₀ и все последующие приближения x_n, y_n(n=1, 2¼) принадлежат R;

3) в R выполнены неравенства

то процесс последовательных приближений (15.3) сходится к корням x = x и y = h системы (15.2), т.е.

и .

Замечание. Теорема остается верной, если условие 3) в ней заменить условием 3¢):

Эту теорему примем без доказательства.

Пример. Для системы

найти положительные корни с четырьмя значащими цифрами.

Решение.Строим график функций f₁(x, y) = 0 и f₂(x, y) = 0. Приближенные значения интересующих корней есть x₀ = 3,5; y₀ = 2,2. Для применения метода итерации запишем нашу систему в таком виде:

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

.

Ограничиваясь окрестностью , будем иметь

;

;

; .

; (15.4)

. (15.5)

Видим, что условия сходимости выполняются.

приступаем к вычислению последовательных приближений по формулам

занося результаты в таблицу.

Таким образом, можно принять x = 3,487; h = 2,262.

Замечание. Вместо рассмотренного процесса последовательных приближений (15.3) иногда пользуются процессом Зейделя:

16. Решение систем линейных уравнений

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

(16.1)

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

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

Система вида (16.1) называется системой п линейных уравнений с n неизвестными, где x₁, x₂, ¼, x_n называются неизвестными системы, a₁₁, a₁₂, ¼, a_nn — коэффициентами при неизвестных системы, b₁, b₂, ¼, b_n — свободными членами системы. Кратко система (16.1) может быть записана в виде

(16.2)

Пользуясь матричными обозначениями, можно записать

A X = B , (16.3)

. (16.4)

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

Пусть дана система линейных уравнений (для простоты рассмотрим систему третьего порядка)

(16.5)

Введем следующие обозначения:

Здесь D — определитель системы, а D₁, D₂, D₃ — определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов.

Чтобы система (16.1) или ее частный случай – система (16.5) имела единственное решение, необходимо и достаточно, чтобы определитель этой системы был не равен нулю (D ¹ 0). Система в этом случае называется линейно независимой или определенной (или невырожденной) и решается с помощью методов линейной алгебры. Например, решение системы по формулам Крамера. В случае (16.5) эти формулы имеют вид:

. (16.6)

Определитель системы (16.1) равен сумме всех произведений элементов какой-либо строки или столбца на соответствующее алгебраическое дополнение

,

если раскрыть определитель по i-ой строке; или , если раскрыть определитель по j–ому столбцу. Алгебраическое дополнение равно минору M_ij, умноженному на (-1) i + j , т.е. A_ij =(-1) i + j M_ij. Минором M_ij называется определитель, получающийся вычеркиванием i-ой строки и j–ого столбца.

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

Методы же исключения уже сегодня позволяют вычислять определители, достигающие порядков до тысячи.

Пример. Решить с помощью формул Крамера систему линейных уравнений:

Решение. Находим определитель этой системы

;

1-й дополнительный определитель:

;

2-й дополнительный определитель:

;

3-й дополнительный определитель:

.

Метод Гаусса.

Этот метод является наиболее распространенным. Он называется также методом последовательного исключения неизвестных. Рассмотрим для простоты систему линейных алгебраических уравнений четвертого порядка

(16.7)

Предположим, что a₁₁ ¹ 0 (ведущий элемент). Разделив первое уравнение системы на a₁₁, получим

, (16.8)

где .

Пользуясь уравнением (16.8), исключим из системы неизвестную x₁. Из второго уравнения x₁ исключается следующим образом. Умножим уравнение (16.8) на коэффициент a₂₁:

(16.9)

Последнее уравнение вычтем из второго уравнения системы:

или ,

где .

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

(16.10)

где .

Допустим теперь, что ведущий элемент второй строки, т.е. коэффициент тоже отличен от нуля. Тогда, разделив на него первое из уравнений (16.10), получим уравнение

, (16.11),

где .

Исключив с помощью уравнения (16.11) неизвестную x₂ из двух последних уравнений в (16.10), приходим к следующей системе из двух уравнений с двумя неизвестными

(16.12),

где .

Теперь, если ведущий элемент и третьей строки не равен нулю, то, поделив на него первое из уравнений (16.12) и вычтя полученное уравнение, умноженное на , из второго уравнения, получим

, (16.13),

, (16.14),

где .

И, наконец, если ¹ 0, то, разделив на него (16.14), приведем к виду

, (16.15),

где .

Итак, если ведущие элементы не равны нулю, то исходная система эквивалентна следующей системе с треугольной матрицей:

(16.16)

Из системы (16.16) неизвестные x₁, x₂, x₃, x₄ находятся в обратном порядке по формулам

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

Поясним ход решения уравнения на примере заполнения таблицы 16.1. Прямой ход начинается с выписывания коэффициентов системы, включая свободные члены (раздел А). Последняя строка раздела представляет собой результат деления первой строки раздела на «ведущий элемент» a₁₁. Элементы следующего раздела схемы (А₁) равны соответствующим элементам предшествующего раздела без произведения их «проекций» на первый столбец и последнюю строку раздела А.

Последняя строка раздела А₁ находится путем деления первой строки раздела на «ведущий элемент» первой же строки. Аналогично строятся следующие разделы. Прямой ход заканчивается, когда мы дойдем до раздела, состоящего из одной строки, не считая преобразованной (в нашем случае А₃).

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

Для контроля вычислений используются так называемые «контрольные суммы»

, (16.18)

помещенные в столбце Sи представляющие сумму элементов строк матрицы исходной системы (16.7), включая свободные члены.

Если принять за новые свободные члены в системе (16.7), то преобразованная линейная система

или

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

.

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

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

Схема единственного деления

х1	x2	x3	x4	Свободные члены	S	Разделы схемы
a11 a21 a31 a41	a12 a22 a32 a42	a13 a23 a33 a43	a14 a24 a34 a44	a15 a25 a35 a45	a16 a16 a16 a16	A
					A1
				A2
	(x4)		A3
x4 x3 x2 x1		B

Пример. Решить систему

(16.19)

Решение. В раздел А таблицы 16.2 впишем матрицу коэффициентов системы, ее свободные члены и контрольные суммы. Далее заполняем последнюю (пятую) строку раздела А, деля первую строку на 7,9(на a₁₁).

Переходим к заполнению раздела А₁ таблицы. Взяв любой элемент раздела А (не находящийся в первой строке), вычитаем из него произведение первого элемента его строки на последний элемент столбца, к которому он принадлежит (т.е. на элемент, принадлежащий в этом столбце отмеченной (выделенной) строке), и записываем в соответствующем месте раздела А₁ схемы. Например, выбрав a₄₃ =-8,9, найдем :

.

Чтобы получить последнюю строку раздела А₁, делим все члены первой строки этого раздела на . Например, .

Аналогично заполняются остальные разделы таблицы. Например,

.

Для нахождения неизвестных используем строки, содержащие единицы, начиная с последней (отмеченные строки). Неизвестное x₄ представляет собой свободный член последней строки раздела А₃:

.

Значения остальных неизвестных x₃, x₂, x₁ получаются последовательно в результате вычитания из свободных членов отмеченных строк суммы произведений соответствующих коэффициентов на ранее найденные значения неизвестных.

Имеем:

Итак, x₁ = 0,96710; x₂ = 0,12480; x₃ = 0,42630; x₄ = 0,56790.

Текущий контроль вычислений осуществляется с помощью столбца S, над которым производятся те же действия, что и над остальными столбцами.

Решение системы по схеме единственного деления