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

 

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

 

A·x = f , (3.27)

 

где матрица A = [a_ij] (i, j = 1, 2, …m) имеет обратную матрицу;
x = (x₁, x₂, x₃, …x_m) – вектор неизвестных, f – вектор свободных членов.

Преобразуем систему (3.27) к следующему виду:

 

(i = 1, 2, …m), (3.28)

 

где , , при этом предполагаем, что .

Условимся, как обычно, считать значение суммы равным нулю, если верхний предел суммирования меньше нижнего. Тогда при i = 1 уравнение (3.28) имеет вид

(3.29)

 

В методе простой итерации (методе Якоби) исходят из записи системы в виде (3.28), итерации при этом определяют следующим образом:

 

(3.30)

 

Начальные значения – (i = 0, 1, … m) задаются произвольно. Окончание итерационного процесса определяют либо заданием максимального числа итераций n₀, либо следующим условием:

 

(3.31)

 

где ε > 0.

В качестве нулевого приближения в системе (3.30) примем

 

. (3.32)

 

Если последовательность приближений x₁⁽⁰⁾, x₂⁽⁰⁾, ..., x_m⁽⁰⁾, x₁⁽¹⁾, x₂⁽¹⁾, ..., x_m⁽¹⁾, ..., x₁^(k), x₂^(k), ..., x_m^{(k )} имеет предел

 

, (3.33)

 

то этот предел является решением системы (3.28).

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

 

(3.34)

 

 

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

 

Этот метод представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (k+1)-го приближения неизвестной x _i учитываются уже вычисленные ранее (k+1)-е приближения (x₁ x₂, ..., x_i-1).

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

 

(i = 1, 2, …n). (3.35)

Выберем произвольно начальные приближения корней , стараясь, конечно, чтобы они в какой-то мере соответствовали неизвестным x₁, x₂, x₃, ..., x_n.

Предположим, что k-е приближение корней известно, тогда в соответствии с идеей метода будем строить (k+1) – е приближение по следующим формулам:

(3.36)

(k = 0, 1, 2,...).

 

Обычно процесс Зейделя сходится быстрее, чем метод Якоби. Бывает, что процесс Зейделя сходится, когда простая итерация расходится и, т.п. Правда, бывает и наоборот. Во всяком случае, достаточные условия сходимости для метода Якоби достаточны и для сходимости метода Зейделя. Если выполняется достаточное условие сходимости для системы (3.35) – по строкам, то в методе Зейделя выгодно расположить уравнения (3.36) так, чтобы первое уравнение системы имело наименьшую сумму модулей коэффициентов:

. (3.37)

 

Пример 3.6.

 

Для того чтобы обеспечить достаточные условия сходимости итерационного процесса (преобладающие значения диагональных элементов), преобразуем исходную систему и приведем к удобному виду. Чтобы дальнейшие преобразования были понятны, обозначим уравнения исходной системы буквами А, Б, В и Г соответственно:

 

х₁= -0.2х₂ +0.1х₃ – 0.2х₄ – 0.4; (Г)

х₂ = -0.2х₁ – 0.2х₃ + 0.2; (А – Б)

х₃ = 0.2х₁ – 0.4х₂ + 0.2х₄ – 0.4; (Б)

х₄ = 0.333х₁ - 1.111. (2А – Б + 2В – Г)

 

Преобразованную систему будем решать методом Зейделя, тогда, с учетом требования (3.37), окончательно получим:

 

 

В качестве нулевого приближения (k = 0) возьмем . Зададим количество итераций k = 2 и все результаты вычислений сведем в табл. 3.1.

 

Таблица 3.1

Итерация, k	Значения неизвестных	Невязки
x1	x2	x3	x4	ε 1	ε 2	ε 3	ε 4
	-0.4	0.2	-0.4	-1.111	-2.711	-1.911	0.444	-1.422
	-0.263	0.36	-0.846	-1.244	-0.309	1.0	0.734	0.446
	-0.329	0.422	-0.874	-1.199	0.095	-0.000	0.009	0.029

 

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

Анализ данных, приведенных в табл. 3.1, показывает, что итерационный процесс быстро сходится, о чем свидетельствуют как быстрое уменьшение невязок, так и уменьшение изменений неизвестных (см. формулу (3.31) метода Якоби).

 

 

3.8. Метод скорейшего спуска (градиента) для случая
системы линейных алгебраических уравнений

 

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

Представим систему линейных уравнений в следующем виде:

(3.38)

Запишем выражение (3.38) в операторной форме:

 

(3.39)

 

Здесь приняты следующие обозначения:

 

; ; . (3.40)

 

В методе скорейшего спуска решение ищут в виде

 

, (3.41)

 

где и - векторы неизвестных на p и p+1 шагах итераций; вектор невязок на p-ом шаге определяется выражением

 

, (3.42)

 

а (3.43)

 

В формуле (3.43) используется скалярное произведение двух векторов, которое определяется следующей формулой:

 

(3.44)

В формуле (3.43) - транспонированная матрица Якоби, вычисленная на p-ом шаге. Матрица Якоби вектор – функции f(x) определяется как

 

(3.45)

 

Нетрудно убедиться, что для системы (3.39) матрица Якоби равна

 

(3.46)

 

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

 

Замечания

· Как видно из выражения (3.45), матрица Якоби не зависит от шага итерации.

· Требования минимизации погрешности на каждом шаге обусловили то, что метод градиента более сложен (трудоемок), чем методы Якоби и Зейделя.

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

 

Обсуждение

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

· Итерационный процесс можно прервать на любом k–ом шаге и продолжить позднее, введя в качестве нулевого шага значения x^(k).

· В качестве недостатка приближенных методов можно отметить то, что они часто расходятся, достаточные условия сходимости (преобладание диагональных элементов) можно обеспечить только для небольших систем из 3 – 6 уравнений.

 

Пример 3.7. Методом скорейшего спуска решим систему уравнений

 

 

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

 

 

Следовательно, вектор невязок на нулевом шаге равен

 

 

Далее последовательно вычисляем

 

 

 

Отсюда

причем

 

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

 

Вопросы для самопроверки

 

· Назовите известные вам методы решения СЛАУ.

· Чем точные методы отличаются от приближенных?

· Что такое прямой и обратный ход в методе Гаусса?

· Нужен ли обратный ход при вычислении методом Гаусса а) обратной матрицы; б) определителя?

· Что такое невязка?

· Сравните достоинства и недостатки точных и приближенных методов.

· Что такое матрица Якоби?

· Надо ли пересчитывать матрицу Якоби на каждом шаге итерации в методе градиента?

· Исходная СЛАУ решается независимо тремя методами – методом Якоби, методом Зейделя и методом градиента. Будут ли равны значения

а) начального приближения (нулевой итерации);

б) первой итерации?

· При решении СЛАУ (n > 100) итерационными методами решение расходится. Как найти начальное приближение?

4. Приближенное решение нелинейных
и трансцендентных уравнений

Постановка задачи

 

Пусть дано уравнение

 

f(x) = 0 , (4.1)

 

где функция f(x) определена и непрерывна в конечном или бесконечном интервале a < x < b.

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

Приближенное нахождение изолированных действительных корней уравнения (4.1) складывается обычно из двух этапов:

1. Отделение корней, то есть установление возможно тесных промежутков [α, β ], в которых содержится один и только один корень исходного уравнения (4.1).

2. Уточнение приближенных корней, то есть доведение их до заданной степени точности.

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: