Добавлен: 06.02.2019
Просмотров: 4553
Скачиваний: 4
31
продолжая подстановку, находим х
(2)
и т.д. Получим последовательность
точек
}
х
,...,
х
,
х
{
)
к
(
)
(
)
(
1
1
0
, которая приближается к исходному решению
х.
3.1.1 Условия сходимости метода.
Пусть '(x) - матрица Якоби (якобиан), соответствующая системе (3.4)
и в некоторой
-окрестности решения х функции
)
х
(
i
(i=1,2,…,m)
дифференцируемы и выполнено неравенство вида:
q
х )
(
,
где (0 q < 1), q - постоянная.
Тогда независимо от выбора х
(0)
из -окрестности корня итерационная
последовательность {х
k
} не выходит за пределы данной окрестности, метод
сходится со скоростью геометрической прогрессии и справедлива оценка
погрешности
x
x
n
q
х
n
х
)
0
(
)
(
.
3.1.2 Оценка погрешности.
В данной окрестности решения системы, производные функции
i
(x)
(i=1,…,m) должны быть очень малы по абсолютной величине, т.е. сами
функции должны быть почти постоянными. Тогда исходную систему (3.1)
следует преобразовать к виду (3.3) с учетом условий сходимости.
Пример. Рассмотрим предыдущий пример и приведем систему к
удобному для итераций виду
.
x
ln
x
x
ln
x
x
x
,
x
x
x
x
1
1
2
2
2
2
3
3
2
2
1
1
8
Проверяем условие сходимости вблизи точки С. Вычислим матрицу
Якоби
2
2
2
1
1
2
3
2
3
2
2
1
2
2
1
3
2
3
2
1
2
2
1
1
1
1
1
1
8
3
3
8
8
3
8
x
ln
x
ln
x
ln
x
ln
)
x
x
x
(
x
x
)
x
x
(
x
)
x
,
x
(
.
32
Так как x
1
3.8, x
2
2, то при этих значениях вычисляем норму матрицы
)
x
(
||
)
x
(
|| ||
)
,
.
(
2
8
3
|| 0.815.
Запишем итерационную процедуру
.
)
k
(
x
ln
)
k
(
x
)
k
(
x
ln
)
k
(
x
)
k
(
x
)
k
(
x
,
)
)
k
(
x
(
)
k
(
x
)
k
(
x
)
k
(
x
1
1
2
2
2
1
2
3
3
2
2
1
8
1
1
Следовательно, метод простых итераций будет сходиться со скоростью
геометрической прогрессии, знаменатель которой q 0.815. Вычисления
поместим в таблице 1.
Таблица 1 Решение системы нелинейных уравнений
К
0
1
…
8
9
)
k
(
x
1
3.80000
3,75155
….
3,77440
x
1
=3,77418
)
k
(
x
2
2.00000
2,03895
…
2,07732
x
2
=2,07712
При К=9 критерий окончания счета выполняется при =10
-3
и можно
положить x
1
=3.774 0.001
x
2
=2.077 0.001.
3.2 Метод Ньютона
Суть метода состоит в том, что система нелинейных уравнений
сводится к решению систем линейных алгебраических уравнений. Пусть дана
система (3.1) и задано начальное приближение x
(0)
, приближение к решению
х строим в виде последовательности
)
(
,...,
)
(
,
)
(
n
х
х
х
1
0
.
В исходной системе (3.1) каждую функцию
),
x
,...,
x
,
x
(
f
n
i
2
1
где i=
m
,
1
,
раскладывают в ряд Тейлора в точке х
(n)
и заменяют линейной частью её
разложения
Для каждого уравнения получаем
m
j
)
n
(
j
j
j
)
n
(
i
)
n
(
i
i
)
x
x
(
x
)
x
(
f
)
x
(
f
)
x
(
f
1
.
33
В матричной форме
где f ' - матрица Якоби.
Предположим, что матрица не вырождена, то есть существует обратная
матрица
1
)
(
)
( n
x
f
.
Тогда система (3.6) имеет единственное решение, которое и
принимается за очередное приближение x
(n+1)
. Отсюда выражаем решение
x
(n+1)
по итерационной формуле:
Формула (3.7) и есть итерационная формула метода Ньютона для
приближенного решения системы нелинейных уравнений.
Замечание. В таком виде уравнение (3.7) используется редко в виду
того, что на каждой итерации нужно находить обратную матрицу. Поэтому
поступают следующим образом: вместо системы (3.6) решают систему
линейных алгебраических уравнений вида
Это система линейных алгебраических уравнений относительно
поправки x
(n+1)
= x
(n+1)
- x
(n)
. Затем полагают
3.2.1 Сходимость метода
Теорема. Пусть в некоторой окрестности решения х системы (3.1)
функции f
i
(при i=
m
,
1
) дважды непрерывно дифференцируемы и матрица
Якоби не вырождена. Тогда найдется такая малая окрестность вокруг
решения х, что при выборе начального приближения x
0
из этой окрестности
0
0
1
1
1
1
m
j
)
n
(
j
j
j
)
n
(
m
)
n
(
m
m
j
)
n
(
j
j
j
)
n
(
)
n
(
)
x
x
(
x
)
x
(
f
)
x
(
f
.
.
.
.
.
.
.
.
.
.
.
)
x
x
(
x
)
x
(
f
)
x
(
f
.
(3.5)
0
)
(
)
(
)
(
)
(
)
(
)
(
n
n
n
x
x
x
f
x
f
(3.6)
)
(
)
(
'
)
(
)
(
)
(
)
(
n
n
n
n
x
f
x
f
x
x
1
1
.
(3.7)
f (x
(n)
)* x
(n+1)
=-f(x
(n)
).
(3.8)
x
(n+1)
=x
(n)
+ x
(n+1)
.
(3.9)
34
итерационный метод (3.7) не выйдет за пределы этой окрестности
решения и справедлива оценка вида
2
1
1
x
x
x
x
n
n
)
(
)
(
,
где n - номер итерации.
Метод Ньютона сходится с квадратичной скоростью. На практике
используется следующий критерий остановки:
)
(
)
(
1
n
n
x
x
.
35
4 Решение проблемы собственных значений
Пусть дана квадратная матрица A размерностью (m*m) и существует
такое число , что выполняется равенство
0
x
,
x
x
А
,
тогда такое число называется собственным значением матрицы А, а x–
соответствующим ему собственным вектором.
Перепишем это равенство в эквивалентной форме
Система (4.1) - однородная система линейных алгебраических
уравнений. Для существования нетривиального решения системы (4.1)
должно выполняться условие
Определитель в левой части уравнения является многочленом m-ой
степени относительно , его называют - характеристическим определителем
(характеристическим многочленом). Следовательно, уравнение (4.2) имеет m
корней или m собственных значений. Среди них могут быть как
действительные, так и комплексные корни.
Задача вычисления собственных значений сводится к нахождению
корней характеристического многочлена (4.2). Корни могут быть найдены
одним из итерационных методов (в частности методом Ньютона).
Если найдено некоторое собственное значение матрицы A, то
подставив это число в систему (4.1) и решив эту систему однородных
уравнений, находим собственный вектор х, соответствующий данному
собственному значению.
Собственные вектора будем при нахождении нормировать (вектор х
умножаем на ||х||
-1
, и таким образом они будут иметь единичную длину),
нахождение собственных значений матрицы A и соответствующих им
собственных векторов и есть полное решение проблемы собственных
значений.
А
нахождение
отдельных
собственных
значений
и
соответствующих им векторов - называется решением частной проблемы
собственных значений.
Эта проблема имеет самостоятельное значение на практике.
Например, в электрических и механических системах собственные
значения отвечают собственным частотам колебаний, а собственные вектора
характеризуют соответствующие формы колебаний.
(A - E) *
x
= 0 .
(4.1)
det(A - E) = 0 .
(4.2)