Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
Обычно точное значение корня неизвестно, а единственная информация о погрешности может быть получена только из оценок, поэтому следовало бы продолжить итерации дальше, чтобы гарантировать четыре верных знака после запятой у приближенного решения х(к\
Рассмотрим нелинейное уравнение х = ф(х), где ср — непрерывно дифференцируемая векторная функция, т. е. рассмотрим систему п уравнений с п неизвестными
*1=Ф1(*1> ->*»)>
Х2 = ф2(*1,
Зададим в Еп норму х (например, || х || = шах | х? |), шар S={x: || х —
1 < i < п
— х(0)||<г}, определим матрицу:
«м-
Верно следующее утверждение.
Теорема 9.5. Пусть функция ф(х) непрерывно дифференцируема в шаре 5. Пусть также в шаре Б
II в(х) ||< ос < 1
12*
||ф(х<°>)-*(0> К(1-а)г.
355
Тогда справедливо утверждение теоремы 9.3.
Для иллюстрации теоремы используем метод простой итерации для приближенного решения системы уравнений *!=(),Обе“*1*2, х2=0,05е-(*1+*2)-Определим шар S= max |jcf—.
—0,11<0,1 (рис. 9.10), а также матрицу
•*т
, . / —0,05x2e_Xi;t2-0,05x1e-;ti;,C2 \
; — 0,05е+х^—0,05е -(Xl+)’
Вычислим коэффициент сжатия:
a = max(0,05(x1 +x2)e~Xl *2, 0,1е-(*1-*2)) = 0,1.
s
Проверим условие (9.2.7), имеем
|| ф(х(0))—х<0) || =тах(|0,05е-(0,1^—0,11, |0,05е"°’2-0,11) =
= тах(5* 10“2, 6 • 10“2)<(1 — а)г = 9 • 10“2.
Условие выполнено. По теореме 9.5 последовательные приближения {х(к)} сходятся к точному решению
л?+1)^0,05е-*?,*?); х{0) = 0,1
x?+1)=0,05e_W‘,+x<2)); х^О)=0,1; к=0, 1, 2, ....
Вычислим два первых приближения:
х^1)=0,05е_(°’1)2=4,950249 • 10~2; х^2'=0,05е ~ '=4,989878 • 10"2,...
хУ)=0,05е“(°’2)=4,093654• 1(Г2; х^О^е-М'4*"’)=4,56765 • 10“2.
#9.3. Метод Ньютона
В основе метода Ньютона, как уже отмечалось в 9.1, лежит линеаризация нелинейного уравнения. Рассмотрим сначала метод Ньютона для скалярных уравнений, а затем для векторных.
9.3.1. Метод Ньютона для скалярных уравнений. Пусть имеется нелинейное уравнение
/(*) = 0, (9.3.1)
которое будем рассматривать в 5={л::\х—х(0)|<г}. Предположим, что Г(х)ф0 в 5. В точке л:(0) произведем линеаризацию (9.3.1), т. е. заменим в (9.3.1) функцию /(х) линейной функцией, проходящей
Х12) х0) х (о) Рис. 9.11
(Х(°)+г) Х
через х<°> и имеющей производную, равную /'(х<0)) (рис. 9.11). Получим линеаризованное уравнение
/(х(0)) +/' (х<0)) (х—х(0)) = 0.
Найдем корень уравнения (9.3.2). Обозначая его х(1),
(9.3.2) имеем
(9.3.3)
г(хту
Теперь, произведем линеаризацию (9.3.1) в точке х(1), повторим все этапы получения формулы (9.3.3), заменяя при этом х{0) на х{1\ а х(1)—на х{2) (см. рис. 9.11). Таким образом, для произвольного к получим формулу
/Ю
Г(х(к)У
к=0, 1, 2,
(9.3.4)
метода Ньютона приближенного определения корня уравнения /(х)=0.
Метод Ньютона называют еще методом касательных, что вполне соответствует геометрическому смыслу линеаризации на одном шаге.
Метод Ньютона является методом простой итерации Х(к+1) = <р(х{к)), к=0, 1, 2, ..., со специально подобранной по /(.х) функцией ф(х), а именно
/ \ /М
*ышх-т;
исходное уравнение при Г(х)ф0 эквивалентно уравнению
дг = ф(х).
Следующий пример показывает, что метод Ньютона может не давать последовательность {лг(Л)}, сходящуюся к корню (нарушено условие сходимости). Уравнение
аг^л; = 0
имеет единственный корень я;=0. Итерационный процесс Ньютона
(9.3.4) примет вид
х(к+ = х{к)—(1 +(х(к))2 аг^х{к) (9.3.5)
довательность
Л3)_
= -10
-3
Рис. 9.12
{.х(к)}. Например, г =9 * 10 - 8.
с(0)=1
и для достаточно больших значений |д:(0)| из (9.3.5) получаем расходящуюся последовательность {х(к)}. Например, х{0) = 2, х(1)=— 3,5, д:(2)= 13,9, д:(3)= —279
(рис. 9.12). В то же время для малых значений \х{0)\ из (9.3.5) получаем сходящуюся к корню после-, л;(1) = —0,57, *(2) = 0,17,
9.3.2. Достаточные условия сходимости метода Ньютона. Выведем достаточные условия сходимости метода Ньютона в предположении, что /(х) дважды непрерывно дифференцируема, из соответствующих условий метода простой итерации (см. теорему 9.4). Условие (9.2.8), учитывая вид ср(л:), запишем так:
сіх
ГМ)! '
Условие (9.2.9) принимает вид |(р(х(0>)-х<°>| =
Л*'0’)
Г(*т)
(1-а)
Г.
(9.3.6)
(9.3.7)
Окончательно, если в области 5={д::|х — лг(0)|<г} выполнены условия (9.3.6), (9.3.7), последовательность {х{к)}, получаемая методом Ньютона (9.3.4)/ сходится к решению уравнения /(х) = 0 в 5.
Скорость сходимости х(к) к решению находится из априорной оценки метода простой итерации |лг(Л)—х|<оЛ\ Однако эта оценка для метода Ньютона оказывается слишком грубой, при приближении х{к) к корню скорость сходимости является квадратичной.
Этот факт вытекает из следующих достаточных условий сходимости метода Ньютона, которые приводятся без доказательства.
Определим числа:
Ро:
Л-
<0)\
Г(-П
шах
/"(*)
Г(х)
к=РоРі, г=(\-^\-2к)рф'
Если
а = 2А<1, (9.3.8)
то последовательность {х{к)} метода Ньютона сходится к корню д: уравнения /(д:) = 0 в области 5 и имеет место оценка погрешности
^а2‘2 кр0И \ к = 0, 1, 2,
9.3.3. Применение программы В4А1. Для определения корня скалярного уравнения /(х) = 0 методом Ньютона может служить
