Метод Якоби (простых итераций)

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 12Следующая ⇒

▷ Похожие статьи

Исходную систему

А х =В (1.11)

преобразуем к виду:

(1.12)

где i=1,2,...,m; a_ii¹0.

Первая сумма равна нулю, если верхний предел суммирования меньше нижнего.

Так (1.12) при i=1 имеет вид

По методу Якоби (метод простых итераций) (n+1 приближение х_i) ищем по формуле

(1.13)

где n – номер итерации (0,1,…,); i= .

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

Условие окончания счета:

,

где i= .

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

Система (1.11) преобразуется к виду (1.12) и организуем итерационную процедуру, где неизвестные х_i на n+1 шаге определяются по формулам

(1.14)

Например,

(1.15)

(1.16)

и так далее.

Итерационные процессы (1.13) и (1.14) сходятся, если норма матрицы А (А - матрица коэффициентов при неизвестных в правой части систем (1.13) и (1.14)) удовлетворяет условию:

.

1.2.3 Матричная запись методов Якоби и Зейделя

Исходную матрицу системы (1.11) представим в виде суммы трёх матриц

A=A₁+D+A₂,

где D - диагональная матрица;

D =diаg[а₁₁а₂₂…а_mm];

A₁ - нижняя треугольная матрица;

A₂ - верхняя треугольная матрица.

Пример: Дана матрица размерности (3´3):

.

А₁ А₂ D

Тогда исходную систему (1.11) можно записать в виде

x =-D^-1A₁ x – D^-1A₂ x +D^-1 b.

Тогда метод Якоби можно записать в виде:

или

. (1.17)

В матричной форме метод Зейделя будет выглядеть:

или

. (1.18)

Преобразуем формулы (1.17) и (1.18):

, (1.19)

. (1.20)

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

Пример для метода Якоби.

,

где t – числовой параметр.

Возникают вопросы:

1) При каких значениях t сходимость будет наиболее быстрой?

2) При каких значениях t метод сходится?

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

. (1.21)

Формула (1.21) получена путем объединения (1.19) и (1.20).

Матрица D_n+1 здесь задает тот или иной метод. Если существует обратная матрица к этой матрице, то из последней системы мы можем найти все неизвестные.

1. Метод (1.21) – явный, если матрица D_n совпадает с единичной матрицей и неявный - в противном случае.

2. Метод (1.21) – стационарный, если матрица D_n+1 = D, и параметр t не зависит от номера итерации и нестационарный - в противном случае.

1.2.4 Метод Ричардсона

Явный метод с переменным параметром t:

, (1.21а)

называется методом Ричардсона.

1.2.5 Метод верхней релаксации (обобщённый метод Зейделя)

, (1.21б)

где w - числовой параметр.

Если матрица А - симметричная и положительно определена, то последний метод сходится при (0 < w < 2). Последнюю формулу запишем в следующем виде:

, (1.22)

где Е - единичная матрица.

Тогда для вычисления неизвестных х_i (i= ) можно записать итерационную процедуру в виде:

. (1.23)

Например, для х₁ это будет такое выражение:

.

1.2.6 Сходимость итерационных методов

Рассмотрим систему

A x= B,

где А - невырожденная действительная матрица.

Для решения системы рассмотрим одношаговый стационарный метод

, (1.24)

при n=0,1,2….

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

Теорема. Условие сходимости итерационного метода.

Пусть А - симметричная положительно определенная матрица и выполнено условие D - 0.5tA > 0 (где t > 0). Тогда метод (1.24) сходится.

Следствие 1. Пусть А - симметричная и положительно определенная матрица с диагональным преобладанием, то есть:

,

при j=1,2,…,m. Тогда метод Якоби сходится.

Следствие 2. Пусть А - симметричная и положительно определенная матрица с диагональным преобладанием, тогда метод верхней релаксации сходится при (0< w<2).

Проверяется, при каком w - метод достигает заданной точности быстрее. В частности, при w=1 метод верхней релаксации превращается в метод Зейделя, следовательно, при w=1 метод Зейделя сходится.

Теорема. Итерационный метод (1.24) сходится при любом начальном векторе x⁰ тогда и только тогда, когда все собственные значения матрицы

по модулю меньше единицы.

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте