ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 206
Скачиваний: 2
11
Он отличается от метода простой итерации тем, что, найдя очередную
компоненту вектора
r
k
, мы сразу же используем ее при вычислении
следующей. Другими словами, вычисления здесь ведутся по формуле
x
d x
d x
c
i
k
ij
j
k
ij
j
k
i
j i
n
j
i
=
+
+
-
=
=
-
å
å
1
1
1
(
)
k
=
1 2
, ,
K
.
Области сходимости метода простой итерации и метода Зейделя не
совпадают, а лишь пересекаются. Это значит, что существуют такие системы,
для которых метод Зейделя сходится, а метод простой итерации нет, и
наоборот. Однако можно показать, что первое и второе достаточные условия
для сходимости метода простой итерации одновременно являются и
достаточными условиями для сходимости процесса Зейделя. Часто метод
Зейделя дает более быструю сходимость, чем простая итерация.
6. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
6.1. Постановка задачи
При решении практических задач часто приходится сталкиваться с реше-
нием уравнений . Всякое уравнение с одним неизвестным можно записать в
виде
f x
( )
=
0
(6.1)
Найти точные значения корней уравнения (6.1) можно только в
исключительных случаях, кроме того коэффициенты некоторых уравнений
являются приближенными числами, и, следовательно, вопрос о нахождении
точных корней вообще не может быть поставлен.
Поэтому большое значение приобретают методы приближенного
вычисления корней уравнения (6.1). Задача нахождения корней считается
решенной, если корни вычислены с заданной степенью точности.
Процесс нахождения приближенных значений корней уравнения
разбивается на 2 этапа:
1) отделение корней;
2) уточнение корней до заданной степени точности.
6.2. Отделение корней.
x
уравнения
f x
( )
=
0
считается отделенным на отрезке [a,b]
1
,
если на этом отрезке уравнение
f x
( )
=
0
не имеет других корней. Отделить
корни - это значит разбить всю область допустимых значений на отрезки, в
каждом из которых содержится один корень. Отделение корней можно
произвести двумя способами - графическим и аналитическим.
1
Рассматривается случай действительной функции
f x
( ) .
12
Графический метод.
Строят график функции
y
f x
=
( )
для уравнения
(6.1) или представляют уравнение в виде
j
( )
( )
x
g x
=
и строят графики функций
y
x
=
j
( )
и
y
g x
=
( )
. Значения действительных корней уравнения являются
абсциссами точек пересечения графика функции
y
f x
=
( )
с осью
Ox
или
абсциссами точек пересечения графиков функций
y
x
=
j
( )
и
y
g x
=
( )
. Отрезки,
в которых заключено только по одному корню, легко находятся.
Графический способ отделения корней не обладает большой точнос-тью.
Он дает возможность грубо определить интервалы изоляции корня.
Аналитический метод.
Аналитически корни уравнения (6.1) можно
отделить, используя свойства функций, известные из курса математического
анализа.
à
Если функция непрерывна на отрезке [a, b] и принимает на концах этого
отрезка значения разных знаков, то внутри отрезка [a, b] существует хотя бы
один корень уравнения
f x
( )
=
0
.
à
Если функция непрерывна и монотонна на отрезке [a, b] и принимает на
концах этого отрезка значения разных знаков, то внутри отрезка [a, b]
существует корень уравнения
f x
( )
=
0
и притом единственный.
Можно рекомендовать следующий порядок действий для отделения
корней аналитическим методом.
1) Найти
¢
f x
( ) - первую производную.
2) Составить таблицу знаков функции, полагая
x
равным : а) критическим
значениям (корням) производной или ближайшим к ним; б) граничным
значениям (исходя из области допустимых значений неизвестного).
3) Определить интервалы, на концах которых функция принимает значения
противоположных знаков. Внутри этих интервалов содержится по одному и
только по одному корню.
6.3. Уточнение корней.
Для уточнения корней, т.е. для доведения их до заданной степени
точности, разработано много различных итерационных методов.
6.3.1. Метод деления пополам (метод бисекций).
Пусть корень
x
уравнения
f x
( )
=
0
отделен и находится на отрезке
[ , ]
a b
.
Итерационный метод бисекций состоит в построении последовательности
вложенных отрезков
{[
,
] [
] .... [ , ]}
,
a b
a
b
a b
n
n
n
n
Ì
Ì
Ì
-
-
1
1
, на концах которых
функция принимает значения разных знаков. Каждый последующий отрезок
получают
делением
пополам
предыдущего. Процесс
построения
последовательности отрезков позволяет найти корень уравнения с любой
заданной точностью.
Опишем один шаг итераций. Пусть на
(
)
n
-
1
-ом шаге найден отрезок
[
] [ , ]
,
a
b
a b
n
n
-
-
Ì
1
1
, такой что
f a
f b
n
n
(
) (
)
-
-
<
1
1
0. Делим его пополам точкой
x
=
+
-
-
(
) /
a
b
n
n
1
1
2 и вычисляем
f
( )
x
. Если
f
( )
x
=
0 , то
x
- корень уравнения.
13
Если
f
( )
x
¹
0 , то из двух половин отрезка выбираем ту, на концах которой
функция имеет противоположные знаки. Таким образом,
a
a
n
n
=
-
1
,
b
n
=
x
, если
f
f a
n
( ) (
)
x
-
<
1
0 ,
a
n
=
x
,
b
b
n
n
=
-
1
, если
f
f a
n
( ) (
)
x
-
>
1
0 .
Если требуется найти корень с точностью
e
, то деление пополам
продолжается до тех пор , пока на каком-то n-ом этапе середина
x
отрезка
будет точным корнем уравнения, т.е.
f
( )
x
=
0 (случай, весьма редко
встречающийся на практике), либо будет получен отрезок
[
]
,
a b
n n
, длина
которого меньше
2
e
. Тогда координата середины этого отрезка и есть значение
корня с требуемой точностью.
Метод бисекций - простой и надежный метод поиска простого корня
уравнения (6.1) (корень
x
=
x
называют простым корнем дифференцируемой
функции
f x
( )
, если
f
( )
x
=
0 и
¢
¹
f
( )
x
0 ). Он сходится для любых
непрерывных функций
f x
( )
, в том числе недифференцируемых. Скорость
сходимости невелика. Для достижения точности
e
необходимо совершить
N
итераций, где
N
b a
»
-
log
2
e
.
6.3.2. Метод простых итераций (метод последовательных приближений).
Обычно в итерационных методах уравнение (6.1) сводят к равносильному
ему уравнению вида
x
x
=
j
( )
(6.2)
таким образом, что искомый корень
x
=
x
уравнения (6.1) является и корнем
уравнения (6.2). Затем на отрезке
[ , ]
a b
выбирается
x
0
- начальное
приближение, и строится последовательность
x
x
k
k
=
-
j
(
),
1
k
=
1 2
, ,...
(6.3)
При определенных условиях эта последовательность сходится к корню
x
.
Определение.
Если существует некоторая окрестность (круг)
R
корня
x
(
{
})
R
x
r
=
- £
x
, такая, что для любых
¢
x
и
¢¢ Î
x
R
,
j
j
( )
( )
¢ -
¢¢ £
¢ - ¢¢
x
x
M x
x
(6.4)
где
M
const
=
, то говорят, что
j
( )
x
удовлетворяет условию Липшица.
Замечание.
Условие Липшица с константой
M
будет иметь место, если в
некоторой окрестности корня
x
=
x
производная
¢
£
j
( )
x
M
. (6.5)
Теорема (без доказательства).
Каково бы ни было
x
R
0
Î
, последовательность
x
x
k
k
k
=
=
-
j
(
),
, ,...
1
1 2
сходится к корню
x
уравнения
x
x
=
j
( )
, если только
14
j
( )
x
в круге
R
корня
x
удовлетворяет условию Липшица с константой
M
<
1.
При этом скорость сходимости характеризуется неравенством
x
M x
k
k
- £
-
x
x
0
. (6.6)
На практике для выполнения этого условия достаточно оценить
¢
j x
( ) .
Если
¢
<
j x
( ) 1
, то такая окрестность, в которой
¢
£
<
j
( )
x
M
1
, существует.
y
x
y =x
y =
j
( x )
x
x
x
x
2
1
0
а )
y
x
y =x
y =
j
( x )
x x
x
x
1
3
2
0
x
б )
Рис. 1
Для случая, когда
j
( )
x
– действительная функция переменной
x
,
описанный метод простых итераций имеет ясную геометрическую
интерпретацию. Построим графики функций
y x
=
и
y
x
=
j
( )
. Корнем
x
уравнения
x
x
=
j
( )
является абсцисса точки пересечения кривой
y
x
=
j
( )
с
прямой
y x
=
(рис.1). Взяв в качестве начальной произвольную точку
[ ]
x
a b
0
Î
,
,
строим ломаную линию (рис.1 а,б).
Абсциссы вершин этой ломаной представляют собой последовательные
приближения корня
x
. Из рис. видно, что если
¢
<
j
( )
x
0 на отрезке
[ ]
a b
,
, то
последовательные приближения
x
x
k
k
=
-
j
(
)
1
колеблются около корня
x
, если
же производная
¢
j
( )
x
положительна, то последовательные приближения
сходятся к корню монотонно.
Рассмотрим вопрос о способах построения функции
j
( )
x
. Поступают
следующим образом. Если уравнение
f x
( )
=
0
имеет корень
x
=
x
, а функция
j
( )
x
непрерывна и не обращается в 0 в окрестности
x
=
x
, то очевидно, что
уравнение
x x
x f x
= -
y
( ) ( )
(6.8)
также имеет единственный корень
x
=
x
. Обозначая
x
x f x
x
-
º
y
j
( ) ( )
( )
, (6.9)
получаем требуемый вид уравнения (6.2). Различные итерационные методы
различаются выбором функции
y
( )
x
.
6.3.3. Метод хорд (метод секущих).
15
Рассмотрим метод хорд. Пусть
f x
( )
- действительная непрерывная
функция действительной переменной, имеющая в интервале
[ , ]
a b
непрерывные
производные первого и второго порядка, не меняющие своего знака в этом
интервале. (Будем считать, что корень уравнения (6.1)
x
=
x
- простой и
находится на отрезке
[ , ]
a b
). Пусть
x
*
- произвольная точка из
[ , ]
a b
, в которой
f x f
x
( )
( )
*
*
¢¢
>
0
(например, в качестве
x
*
можно выбрать одну из границ
отрезка
[ , ]
a b
). В качестве функции
y
( )
x
возьмем функцию
y
( )
( )
( )
x
x x
f x
f x
=
-
-
*
*
. (6.10)
Тогда
j
( )
( )
( )
( )
( )
( )
( )
( )
x
x
x x
f x
f x
f x
x f x
xf x
f x
f x
= -
-
-
=
-
-
*
*
*
*
*
, (6.11)
и уравнение
x
x f x
xf x
f x
f x
=
-
-
*
*
*
( )
( )
( )
( )
(6.12)
также имеет корень
x
=
x
. За
начальное приближение
x
0
примем любую точку из
[ , ]
a b
, в которой
f x
( )
0
имеет
знак, противоположный знаку
f x
( )
*
(например, за
x
0
можно взять другую границу
отрезка
[ , ]
a b
). Последующие
приближения
строим
обычным образом:
x
x f x
x
f x
f x
f x
k
k
k
k
=
-
-
*
-
-
*
-
*
(
)
( )
(
)
( )
1
1
1
.
(6.13)
Геометрическая интерпре-тация этого метода состоит в том, что через точки
(
)
x f x
*
*
, ( )
и
(
)
x
f x
k
k
-
-
1
1
, (
)
проводится прямая (т.е. дуга кривой
y
f x
=
( )
заменяется стягивающей ее хордой на малом отрезке
[
]
x
x
k
-
*
1
,
). За следующее
приближение
x
k
берется точка пересечения этой прямой с осью абсцисс (см.
рис.2).
6.3.4. Метод Ньютона (метод касательных).
В методе Ньютона в качестве
y
( )
x
выбираем
y
x
a=x
0
x
1
x
2
x
3
x
b=x
*
0
Рис. 2