close

Вход

Забыли?

вход по аккаунту

?

Численный алгоритм решения нелинейных уравнений с использованием вторых производных.

код для вставкиСкачать
Математические
структуры и моделирование
УДК 62.501.12
2003, вып. 11, с. 1014
ЧИСЛЕННЫЙ АЛОИТМ ЕШЕНИЯ
НЕЛИНЕЙНЫХ УАВНЕНИЙ С ИСПОЛЬЗОВАНИЕМ
ВТОЫХ ПОИЗВОДНЫХ
А.Т. Когут
In this artile a modifiation of Newton's method for solution of nonlinear
equation is reviewed. The Newton's method may be derived by deomposition
of nonlinear smooth funtions in linear setion of Taylor's series taking
into aount only the first derivative. It is offered a linear approximation,
based on Taylor's series and inluding seond-order derivative. Both forms
of linearization were reeived by means of whih the reurrene proedures,
that use lassial Newton's method, were designed. Convergene of worked
out algorithms was examined and the ubi speed was obtained.
Введение
Простейший итерационный метод решения нелинейных уравнений содержит
значения самой ункции, метод Ньютона первую производную и обладает
уже квадратичной скоростью сходимости. Существуют итерационные методы
высших порядков, которые содержат вторые и более высокие производные [1?. В
работе предлагается один из возможных подходов к получению рекуррентных
процедур второго порядка путем построения линейных аппроксимаций, основанных на разложении нелинейной ункции в ряд Тейлора и учитывающих
вторые производные.
1.
Построение алгоритмов
[ ?
f (x) = 0;
ассмотрим определение на интервале a; b корня x нелинейного уравнения
()
(1)
где f x трижды непрерывно диеренцируемая ункция.
Для численного решения уравнения (1) часто применяется метод Ньютона,
представляющий собой рекуррентную процедуру [1?:
xk+1
2003
А.Т. Когут
=x
( )
(x )
f xk
k
f0
k
Омский государственный университет путей сообщения
(2)
Математические структуры и моделирование. 2003. Вып. 11.
и его модиикацию
xk+1
( )
( )
=x
f xk
;
hk+1 0
f xk
k
11
(3)
где hk+1 в общем случае переменный шаг, вводимый для ускорения сходимости.
Формула (3) может быть получена из разложения f xk+1 в ряд Тейлора
вида
f xk+1
f xk
f 0 xk x O x2 :
(4)
(
) = ( ) + ( ) + ( )
(
)
В выражении (4) разность
x = x
k +1
(5)
xk :
Для получения явных вычислительных схем допустим,что
(
f xk+1
) = 0:
(6)
( )
Отбрасывая слагаемое O x2 с учетом ормул (5)и (6), получим рекуррентную процедуру (3).
В разложении (4) учитывается только первая производная. ассмотрим приближение f xk+1 квадратичным многочленом Тейлора следующего вида:
(
)
(
f xk+1
) = f (x ) + f 0(x )x + 21 f 00(x )x x:
k
k
(7)
k
Заменим в (7) одну из разностей x на некоторую известную величину Жk+1 ,
тогда одним из возможных представлений приближения для f xk+1 является
(
f xk+1
или
) = f (x ) + f 0(x )x + 21 f 00(x )Ж x
k
k
k
k +1
)
k +1
k
[f 0 (x ) + 12 f 00 (x )Ж ?x = f (x )
k
(
( )
f xk :
k +1
Применяя последовательно ормулы (6) и (7), получим
( )
:
(8)
1
f 0 (x ) + f 00 (x )Ж
2
Заменив в (7) произведение x x на Ж , можно получить для f (x )
=x
xk+1
k
f xk
hk+1
k
k +1
k
2
другое приближение
(
k +1
k +1
f xk+1
) = f (x ) + f 0(x )x + 21 f 00(x )Ж
k
k
k
2
k +1
:
Выполняя аналогичные преобразования, запишем
xk+1
=x
k
( ) 21 f 00(x )Ж
f 0 (x )
hk+1 f xk
k
k
2
k +1
:
(9)
12
А.Т. Когут.
Алгоритм решения нелинейных уравнений
Как показано в работе [2?, третья возможная орма аппроксимации является неработоспособной.
На основании ормул (8) и (9) можно получить вычислительный алгоритм
только в том случае, если известен или задан способ определения разности Жk+1 .
Допустим, что
= x~
Жk+1
~
(10)
xk :
k +1
В разности (10) значение xk+1 , вообще говоря, может быть рассчитано по
любому рекуррентному алгоритму. Для сохранения общности будем определять
xk+1 по методу Ньютона
~
( )
( )
~ =x
xk+1
( +1)
f xk
:
hk+1 0
f xk
k
(11)
На k
-й итерации на основе известного приближения xk по ормуле (11)
вычисляется xk+1 , ормируется по (10) разность Жk+1 , которая в дальнейшем
подставляется в (8) или в (9) в зависимости от используемой ормы алгоритма
второго порядка. Итерационная процедура, как обычно, продолжается до тех
пор, пока не будет выполнено условие достаточной точности.
2.
~
Анализ сходимости
В [1? показано, что метод Ньютона обладает квадратичной скоростью сходимости. Оценим сходимость предлагаемых вычислительных алгоритмов при
hk+1
. Подставим в ормулу (8) выражения (10), (11) и запишем
=1
( )
h f (x ) i :
1
00
0
f (x )
2 f (x ) f 0 (x )
=x
xk+1
f xk
k
(12)
k
k
k
k
Вычтем из левой и правой частей (12) значение x и перепишем в виде
xk+1
=x
x
k
h f (x ) i
x
( )
(x ) f 0(x ) 1 f 00(x )h f (x ) i :
2
f 0 (x )
f 0 xk
k
f0
k
k
k
k
k
Учитывая, что в соответствии с [1, . 468?
( ) = (x
0
f (x )
f xk
00
) 21 ff0((x )) (x
x
k
)
x 2 ;
k
k
k
(13)
где заключено между x и xk ,
получим
xk+1
x
=x
k
x
h
(x
k
x
00
) 12 ff0((x )) (x
k
k
x
i
) 2
13
Математические структуры и моделирование. 2003. Вып. 11.
f0
h
(x ) 21 f 00(x ) (x
k
k
( )
1 f 00( ) (x
x )
2 f 0 (x )
f 0 xk
k
x
k
k
)
2
i:
Приведем к общему знаменателю и получим
1 hf 00( ) f 00(x )i(x x ) + 1 f 00(x )f 00 ( ) (x x)
2
4 f 0 (x )
x =
i
h
1
f 00 ( )
1
00
0
f (x )
2 f (x ) (x x ) 2 f 0 (x ) (x x )
k
k
2
k
k
xk+1
k
k
3
:
(14)
:= max
jf (y )j:
2
(15)
k
k
2
k
k
Введем обозначения
m1
:= min
jf 0 (y )j;
2
y
[a;b?
jf 00(y)j ;
:= max
2
jf 0 (y )j
2
M21
y
(3)
M3
[a;b?
y
[a;b?
Естественно, что выполняется следующее:
jf 00( )
( )j 6 M j
f 00 xk
3
xk
j 6 M jx
3
k
j
x ;
(16)
j
(17)
поэтому для (14) можно записать
jx
x
k +1
j 6 jf 0(x ) + +O(x
M3
2
k
M21
4
x
k
)j jx
k
x 3 :
Оценим выражение, стоящее в знаменателе. При достаточно малом jxk
соблюдается условие
jO (x
x
k
x
j
)j < m2 :
1
Теперь допустим, что для знаменателя выполняется требование
jf 0 (x ) + O (x
k
Тогда
k
jf 0 (x ) + O (x
k
x
k
x
)j < m2 :
1
)j + jO (x
x
k
)j < m ;
1
но в силу неравенства треугольника
jf 0 (x ) + O (x
k
k
поэтому
x
)j + jO (x
k
x
)j > jf 0 (x )j;
k
jf 0 (x )j < m ;
1
k
что противоречит определению m1 . Следовательно, для знаменателя ормулы
(17) должно выполняться
jf 0 (x ) + O (x
k
k
x
)j > m2 :
Окончательно (17) можно записать в виде
1
14
А.Т. Когут.
Алгоритм решения нелинейных уравнений
jx
x
k +1
+ M jx
j 6 2M 2m
3
j
x 3 ;
21
k
1
т.е. алгоритм второго порядка (8) обладает кубической скоростью сходимости.
Оценим сходимость вычислительной процедуры (9). Для этого подставим в
(9) ормулы (10), (11), вычтем из левой и правой частей x и после преобразований получим
x
xk+1
=x
x
k
С учетом ормулы (13) запишем
( ) 1 f 00(x ) h f (x ) i :
f 0 (x )
2 f 0 (x ) f 0 (x )
f xk
k
k
k
k
k
2
h
00
00
) 12 ff 0((xx )) (x x ) 21 ff0((x )) (x
Выпишем все слагаемые до (x
x ) включительно:
x
xk+1
00
= 21 ff0((x )) (x
x
k
2
k
k
k
k
x
00
00
= 21 f (f) 0(xf ) (x ) (x
k
k
x
k
)
2
i2
:
3
k
xk+1
k
x
k
00
00
) + 21 f (fx0(x)f) ( ) (x
2
k
k
2
k
x
) + O (x
3
k
)
x 4 :
С учетом неравенства (16), а также ормул (15) в окончательном виде получим
jx
k +1
где
x
j 6 2Mm + 12 M jx
3
1
22
k
j
x 3 ;
jf 00(y)j :
:= max
2
jf 0 (y )j
2
M22
y
[a;b?
2
Таким образом, алгоритм (9), как и процедура (8), обладает кубической
сходимостью, то есть на порядок выше, чем у классического метода Ньютона.
3.
Заключение
Получены две ормы итерационных процедур численного решения нелинейных
уравнений, основанных, как и метод Ньютона, на разложении ункций в ряд
Тейлора, но учитывающих кроме первой и вторую производную. Исследована сходимость предложенных алгоритмов и доказана их кубическая скорость
сходимости, что на порядок превышает сходимость метода Ньютона. Методика
линеаризации может быть распространена и на учет производных более высоких порядков.
Литература
1. Березин И.С., Жидков Н.П. Методы вычислений. Том 1. М.: Наука, 1966.
2. Когут А.Т., Малютин А.., Щегольский И.А. Применение квадратичной аппроксимации в задачах параметрической идентиикации и оптимизации // Инорматика и процессы управления. 1997. С.44-48.
Документ
Категория
Без категории
Просмотров
6
Размер файла
133 Кб
Теги
численные, нелинейные, решение, уравнения, алгоритм, использование, вторых, производной
1/--страниц
Пожаловаться на содержимое документа