Численные методы решения систем уравнений: итерации, Якоби, Зейдель, Ньютон

3 Численные методы решения систем уравнений.
Многие методы, рассмотренные нами для решения одиночных уравнений,
можно расширить на решение систем линейных либо нелинейных уравнений.
3.1 Метод простых итераций.
Пусть требуется найти корни следующей системы нелинейных уравнения:
{
F1 ( x 1 , x 2 , ... , x n )=0,
F2 ( x 1 , x 2 , ... , x n )=0,
................................
F n ( x 1 , x 2 , ... , x n )=0.
(3.1)
или коротко в векторной форме:
(3.2)
F ( X )=0
Функции
Fi
должны
удовлетворять
условию
определенности
и
непрерывности вместе со своими частными производными в некоторой области,
которой принадлежит точное решение рассматриваемой системы уравнений.
Точное решение системы (3.1) обозначим:
X *=( x *1 , x *2 , ... , x *n )
(3.3)
Для того, чтобы систему (3.1) решить методом простых итераций
преобразуем ее к виду:
x 1=f 1 ( x 1 , x 2 , ... , x n)
x 2=f 2 ( x 1 , x 2 , ... , x n )
...............................
x n=f n ( x 1 , x 2 ,... , x n )
(3.4)
или, коротко в векторной форме:
(3.5)
X=f ( X )
Функции f i должны удовлетворять тем же условиям, что и F i .
Для решения системы уравнений (3.4) будем использовать простой
итерационный процесс:
i+1
i
i
i
i+1
i
i
i
x 1 =f 1 ( x 1 , x 2 , ... , x n )
x 2 =f 2 ( x 1 , x 2 , ... , x n )
...............................
i
i
i
x i+1
n =f n ( x 1 , x 2 ,... , x n )
(3.6)
или, коротко в векторной форме:
1
X
i +1
i
=f ( X )
(3.7)
Алгоритм поиска решения методом простых итераций следующий:
1) задается вектор начального приближения X0;
2) рассчитывается следующее приближение по формуле (3.6);
3) рассчитывается погрешность ε, если она выше заданной, итерации
продолжаются, если нет – решение считается найденным.
3.2 Метод Якоби.
В зависимости от способа перехода от системы (3.1) к системе (3.4) можно
выделить несколько методов, основанных на методе простых итераций.
Для систем линейных алгебраических уравнений (СЛАУ) одним из самых
простых является метод Якоби.
Запишем СЛАУ:
{
a 11 x 1+ a12 x 2 +...+a1n x n=b 1,
a21 x 1+a 22 x 2 +...+a2n x n=b 2,
................................
an1 x 1+a n2 x 2+...+a nn x n =b n.
(3.8)
В матричной форме:
A X=B
(3.9)
Представим матрицу коэффициентов в виде:
A=L+ D+ R
(3.10)
Где D – матрица диагональных коэффициентов, а L и R, соответственно
левые и правые треугольные матрицы.
Тогда, если решение уравнения выразить в виде:
X=−D−1 ( L+ R ) X+ D−1 B
(3.11)
Мы приходим к методу Якоби.
Итерационная формула метода Якоби имеет вид:
X i +1=−D−1 ( L+ R ) X i + D−1 B
(3.12)
Важным условием осуществимости метода Якоби является отсутствие
нулевых элементов на главной диагонали матрицы A. Метод Якоби для СЛАУ
сходится к решению системы только тогда, когда все собственные числа матрицы
D−1 ( L+ R ) по модулю меньше 1.
2
Если упоминается метод простых итераций, то для СЛАУ чаще всего
имеется ввиду именно метод Якоби. Для нелинейных уравнений переход от
системы (3.1) к системе (3.4) обычно осуществляется способом, требующим
наименьшее количество алгебраических действий, либо таким образом, чтобы
образующаяся система обладала хорошей сходимостью.
Чаще всего используют преобразование вида:
i
i
i
i
i
i
f 1 ( x 1 , x 2 ,... , x n )= x 1+ F 1 ( x 1 , x 2 ,... , x n )
f 2 ( x 1 , x 2 ,... , x n )= x 2 +F 2 ( x 1 , x 2 ,... , x n )
...............................
f n ( x i1 , x i2 , ... , x in) =x n + F n ( x 1 , x 2 , ... , x n )
(3.13)
Тогда итерационная формула метода Якоби для нелинейных уравнений
будет иметь вид (3.6).
3.3 Метод Зейделя.
Можно ускорить сходимость итерационного процесса, если изменить
формулу перехода на:
i+1
i
i+1
i+1
i
i
x 1 =f 1 ( x 1 , x 2 , ... , x n )
i
i
x 2 =f 2 ( x 1 , x 2 , ... , x n )
...............................
i+1
i+1
i
x i+1
n =f n ( x 1 , x 2 , ... , x n )
(3.14)
Или для СЛАУ:
X
i +1
−1
i
−1
=−( D+ L ) R X + ( D+ L ) B
(3.15)
Такой метод называется методом Зейделя.
Метод Зейделя решения СЛАУ является сходящимся, если все собственные
−1
числа матрицы −( D+ L ) R по модулю меньше 1. Для нелинейных уравнений
вопрос о сходимости метода является более сложной задачей, обычно считают
что метод сходится, если начальное приближение взято достаточно близко от
точки истинного решения задачи. Также как и для метода Якоби, важным
условием осуществимости метода Зейделя для СЛАУ является отсутствие
нулевых элементов на главной диагонали матрицы A.
3
3.4 Метод ПВР.
Сходимость метода Зейделя для СЛАУ можно еще ускорить, иногда в
несколько раз, используя так называемые методы релаксации.
Рассмотрим данные методы.
Пусть вектор Z i+ 1 есть приближение к решению по методу Зейделя, тогда
итерационный процесс метода релаксации выражается следующей формулой:
X i +1= X i + ω ( Z i +1 − X i )
(3.16)
Или более подробно:
X i +1= X i + ω ( −( D+ L ) R X i + ( D+ L ) B− X i )
−1
−1
(3.17)
Оптимальное значение параметра релаксации находится в пределах
ω∈(0;2) .
При значении параметра релаксации ω = 1 метод тождественен методу
Зейделя, при ω < 1 метод называется последовательной нижней релаксацией, при
ω > 1 последовательной верхней релаксацией.
Обычно ускорение сходимости метода наблюдается только при ω∈(1 ;2) , и
поэтому в понятие методов релаксации часто заменяют понятием методов
последовательной верхней релаксацией (ПВР или SOR).
Наибольшее увеличение сходимости наблюдается при минимальном
спектральном радиусе матрицы:
−1
( D+ ω L ) ⋅(( 1−ω ) D−ω R )
(3.18)
В общем случае задача определения оптимального значения параметра
релаксации решения не имеет и подбор ведется методом проб. Однако для
определенного типа матриц, называемых «упорядоченных согласовано со
свойством А» имеется формула для расчета оптимального параметра релаксации:
ω opt =
2
2
1+ √ 1− ρ
(3.19)
Где ρ – спектральный радиус матрицы:
D−1⋅( R+ L )
(3.20)
Например, для одной распространенной задачи, встречающейся при
решении уравнений в частных производных методом Кранка-Николсон, параметр
релаксации рассчитывается по формуле:
4
ω opt =
2
√
1+ 1−cos2
(
π
N +1
(3.21)
)
Где N – размерность матрицы.
Для нелинейных уравнений тоже можно составить схему, аналогичную
методу ПВР, но подбор параметра релаксации в этом случае представляет собой
еще более нетривиальную задачу.
3.5 Метод Ньютона и его производные.
Если для перехода от системы (3.1) к системе (3.4) использовать формулы,
применяемые при решении одиночного уравнения методом Ньютона, мы придем
к методу Ньютона для систем уравнений.
Введем матрицу производных:
[ ]
∂f1
∂ x1
∂f2
f '( X)= ∂ x 1
...
∂fn
∂ x1
∂f 1
∂ x2
∂f 2
∂ x2
...
∂fn
∂ x2
∂f1
∂ xn
∂f2
...
∂ xn
... ...
∂fn
...
∂ xn
...
(3.22)
Тогда итерационный процесс метода Ньютона в матричной форме
представится следующим образом:
−1
X i +1= X i −f ' ( X i ) f ( X i )
(3.23)
Этот метод обладает гораздо более быстрой сходимостью, чем метод
простой итерации, но имеет большие вычислительные затраты на каждом шаге
итерации.
Уменьшить
вычислительны
затраты
можно
применяя
т. н.
модифицированный метод Ньютона, который отличается тем, что матрицу
производных
вычисляют
только
на
первом
шаге
итераций.
Формула
итерационного процесса модифицированного метода Ньютона имеет вид:
−1
X i +1= X i −f ' ( X 0 ) f ( X i )
(3.24)
Тем не менее сходимость модифицированного метода Ньютона гораздо
ниже основного метода. Как компромиссный вариант можно применять
5
комбинацию
методов
(3.23)
и
(3.24),
перевычисляя
значение
матрицы
производных через определенное количество итерационных шагов.
Так же можно использовать аппроксимацию производных их разностным
аналогом, при этом приходим к методу секущих для систем уравнений.
Список литературы.
1. Вержбицкий, В.М. Основы численных методов / В.М. Вержбицкий. – М.:
Высшая школа, 2002. – 840 с.
2. Бахвалов Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.М.
Кобельков. – М.: Бином, 2004. – 634 с.
3. Корнюшин, П.Н. Численные методы / П.Н. Корнюшин. – Владивосток :
из-во Дальневосточного ун-та, 2002 . – 104 с.
4. Ортега, Дж. Введение в численные методы решения дифференциальных
уравнений / Дж. Ортега, У. Пул. – М.: Наука, 1986. – 288 с.
5. Вайникко, Г.М. Итерационные процедуры в некорректных задачах / Г.М.
Вайникко, А.Ю. Веретенников. – М.: Наука, 1986. – 183 с.
6. Волков, Е.А. Численные методы / Е.А. Волков. – М.: Физматлит, 2003. –
248 с.
6