Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 39
Текст из файла (страница 39)
Иными словами, систему (7.1) следует преобразовать к такому виду (7.5), чтобы функции ((г( слабо менялись при изменении аргументов, т.е. были "почти постоянны ми". Каких-либо общих рецептов, как это следует делать, в общем случае нет. 3 а м е ч а н и е 2. В условиях теоремы 7.1 верна апостериорнал оценка погрешности ~х(П) в~ ~ ~и(и) х(П)) ~ 1 — д (7.10) которая удобна для формулирования критерия окончания итераций, если известна величина ().
Однако найти значение (), удовлетворяющее неравенству (7.8) для всех х.из некоторой (т-окрестности корня, далеко не просто. В ряде случаев при наличии достаточно хорошего начального приближения х(о) можно, считая, что () (( ()о— = ~ р (и( о' ) 1, использовать следующий практический критерий окончания итерационного процесса: 1х(") — а("1) ~ < 61 —— 1 — В Чо Пример 7.3. Используя метод простой итерации, найдем с точностью Е = = 10 Х решение х(, хг системы (7.4). Приведем систему к виду, удобному для итераций: х1 = 8хх — хх х2 х( л)2 — хг + 1пхг )пх) 8х( — Зхг г 8хг 3( 8 х х — уЗ) 2/г 1 1 1+ — —— 1пхг 1пг хг З(8 х — )2Р 1 1 1п2Т, 1пх1 дх( дхг дУг Фг дх( дхг 198 Здесь (()1 (х(, лг) = 8х х — х 2, ((гг(х), хг) = хг + — — — . Провери)( 2 2 хг 1пхг 1пх) ' выполнение условия с)(одимости вблизи точки С Вычислим матрицу Якоби Так как х) м 3.8 и хг и 2, то для х)з х имеем Г 0.379 0.4361 "('1' ") ' " ("' ) ' ~-Ы88 .0.3613 Тогда $92'(х), хг)$ )) 192'(3.8, 2)$ )з 0.379 + 0,436 = 0.815.
Следовательно, метод простой итерации з (й 1) 1 з (7.11) х х("" = х'"' + — ~ —— 2 2 1пх(Г) 1п (х) 2 1 будет сходиться со скоростью геометрической прогрессии, знаменатель которой примерно равен 0.815, если начальные приближения брать в достаточно малой окрестности решения. Возьмем х()о) = 3.8, х'о) = 2 и будем вести итерации по формулам (7.11), используя критерий окончания (7.10), в котором х = 10 з, д = 0.815. Резуль- таты вычислений с шестью знаками мантиссы приведены в табл. 7.1. Таблица71 2 3 4 .( )с) 1 х( Й) г х( Й) 1 3.77198 3.77399 3.77450 3.77440 3.77418 х( й) г 2.07920 2.07850 2.07732 2.07712 2.07778 При Й = 9 критерий окончания выполняется и.можно положить х) = 3.774 х х 0.001 хг = 2 077 х 0 001.
199 3.80000 3.75155 2.00000 2.03895 3.74960 2.06347 3.75892 2.07498 3.76720 2.07883 удовлетворяющая равенству (7.7), а последовательность х~ ~1, удовлет- воряющая равенству х' ~" ' = уг *( х' "' ). (7.12) Будем считать, что абсолютная погрешность вычисляемых значе- ний у'(х) вектор-функции ьт мала и что «фх) — у'(х) « ~ Ь(у'), Наличие погрешности вычисления уг приводит к появлению области неопределенности решения х, радиус е которой можно приближенно оценить, пользуясь неравенством е < е ' = Ь(уг')/(1 — д) в том случае, если «у'(х)« ~ д. Сформулируем следующий результат, являющийся аналогом теорем 4.5 и 6.2. Т е о р е и а 7.2. Пусть выполнены условия теоремы 7.1 и для всех х иэ гт — окрестпности решения х выполнено неравенство «фх) — р~(х)«Ь — Мю*) ~ Ь(уг*). Предположим, также что е* = «т (т.е.
величина 1 — о Ь(у') достаточно мали). Тогда если вычисления по формула и (7.7) и (7.12) начинаются с одного начального приближения х~ о> = х< о', х (где гт1 принадлежащего гт1-окрестности решения = тшп 1о, (гт — в*)/у)), то последооательностпь х<п' не выходит эа пределы тт-окрестности решения х и для всех п 1 1 справедливы оценки «х(п> х(п~ «< е «хгп) х«< Чп«х<ог х«+ 6Ф, «хгп~ х« ~ ч «хсп1 ~лпч> « 1 — д 4. Модификации метода простой итерации. В некоторых случаях для ускорения сходимости полезно использовать следующий аналог метода Зейделя (см. ~ 6.2): 200 3.
Влияние погрешности вычислений. В силу наличия погрешностей при вычислении на ЭВМ получается не последовательность к<т'1, 4"" = ~~(х~" '2"' з"' — ".") ( ь+1) р (хс ус~ ы х( Рс) .( 7с~ ( яс) ) х'~ ' = уз(х' ' х' ' ' х' ' ". х'~') 4 1+1) = р (хи+1) х( 1+1) хаий+1) х( й) ) в ~ 1 ' 2 ' 3 ''"' а Более общий вариант метода Зейделя состоит в следующем: з-я компонента решения на (Й + 1)-й итерации метода определяется как решение нелинейного уравнения Р(х'," ") = О, где Г (х) = Ях',"">, ..., х',.~'>, хь хф, ..., ю<~>)'.
Преимущества зтого подхода состоят в возможности использования методов решения уравнений с одним известным и в отсутствии необходимости приведения системы уравнений к виду, удобному для итераций. Указанный метод сходится, если для матрицы Якоби ~'(х) выполнены условия диагонального преобладания. Иногда существенный выигрыш дает использование метода, являющегося аналогом метода релаксации (см. ~ 6.3). В нем после вычисления очередной ~-й компоненты (Й + 1)-го приближения по формуле метода Зейделя хФ" ~ = р(х(ь'и ...
х~.""~ х<,"> ... х(")) В ] > з ~-$ 7 ~ У ' > а приближение х~."" > вычисляют по формуле х'-~'> = х~. "" > + 1. (~ Ц( (/с ~) .~й)) $7.3. Метод Ньютона для решения систем нелинейных уравнений 1 Описание метода. Обобщим метод Ньютона, изложенный в З 4.6 для решения одного нелинейного уравнения, на решение систем нелинейных уравнений (7.1). При этом будем исходить из трактовки метода Ньютона как метода линеаризации. 201 Предположим, что исходя из начального приближения х(о' к реше нию х построены приближения х('), х(з), ..., х("). Заменим в системе (7.1) каждую из функций Я() = 1, 2, ..., т) линейной частью ее разло- жения по формуле Тейлора в точке х("): т дЛ(х( и) 1 Й.) У,(.(-))+ ~ " '(; — .).
дх) В результате придем к системе линейных алгебраических уравнений и д((х(п) ) Й.(.))+ ~ '( '(,—.())=О, дх~ в ф (х[а) ~ (2(х()()) -+ Х ' ' (х — х(")) = О, дх( ~ 3 Ущ(х(п)) + Е а (х,— х(.й)) = О, а ф„(х( а) ) )з ( дх) ) >. имеющей в матричной форме записи следующий вид: ~(х( п) ) + ~(х(п) )(х х( и) ) — О (7.13) решению х. Таким образом, приближение х("" удовлетворяет равен- ству ~(х( и) ) + у'(х( а) )(х( и+1) х()1) ) — О (7.14) выражая из которого х(""), выводим итерационную формулу метода Ньютона: х'"'"' = х'") — (/'(х("))) )у(х'")). (7.15) 3 а м е ч а н и е. Формула (7.15) предполагает использование трудоемкой операции обращения матрицы (см.
гл. 5), поэтому непосредственное ее использование для вычисления х(""' в большинстве случаев нецелесообразно. Обычно вместо этого решают эквивалентную системе (7.14) систему линейных алгебраических уравне- ний 202 Здесь (' — матрица Якоби (7.3). Предположим, что матрица ~'(х(") ) невырожденная, т.е. существует обратная матрица (~'(х(") )) '. Тогда система (7.13) имеет единственное решение, которое и принимается за очередное приближение х("')) к 7'(х( и) ) Ь х( "'1) = — 1 (х( ") ) (7.16) относительно поправки Ьх("+') = х("+') — х("'. Затем полагают Х( п+! ) — Х( и) + Д Х( и+1) (7.17) 2. Сходимость метода. Сформулируем основную теорему о сходимости метода Ньютона. Т е о р е м а 7.3. Пусть в некоп!орой окрестности решения х системы (7,1) функции Я!' = 1, 2, ..., т) дважды непрерывно дифференцируемы и матрица )" (х) невырождена.
То!да найдется такая малая 6- окрестность решения х, что при произвольном выборе начального приближения х(о' из этой окрестности итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка: 1х("'!' — х~/ ( О(~!х(п) — х~~г и ~ 0 Эта оценка означает, что метод сходится с квадратичной скоростью. Квадратичная скорость сходимости метода Ньютона позволяет использовать простой практический критерий окончания: (7.18) 5х[п) х(п-!) ~! ~ е Пример 7.3.
Используя метод Ньютона, найдем с точностью е = 10 ~ решение х(, хг системы (7.4). Возьмем х!( = 3.8, х(2 ) = 2 и будем вести вычисления по формулам (о) (7.16), (7.17), в которых Результаты вычислений с шестью знаками мантиссы приведены в табл. 7.2. Т а б л и ц а 72 2 3 3.77258 3.77388 3.77389 2.07189 2.07708 2.07710 3.80000 2.00000 х( )с) г 203 х! + хг — 821хг з з Зх! — 8хг г г(х) =, ~ (х) = хг 211пхг — хг 1пх! 1пх2 —— 34 -8х, х! ..) х2 При й = 3 критерий окончания 1х~"' — х'1 ы '1 < е = 10 4 выполняется н можно положить х~ — 3.7739 х 0.0001, хт — 2.0771 1 0.0001. 3. Трудности использования.
Изложенные в 3 4.6 трудности использования метода Ньютона не только сохраняются при применении его к решению систем нелинейных уравнений, но и усугубляются. Во-первых, возникает проблема вычисления на каждой итерации матрицы ~'(х) из ти2 частных производных, что само по себе может оказаться весьма сложным делом. Во-вторых, обостряется проблема нахождения хорошего начального приближения. Ее решить в многомерном случае гораздо труднее, чем в одномерном. 4.
Влияние погрешности вычислений. Пусть 1* и (~') ' — вычисляемые на ЭВМ приближенные значения вектор-функции ~ и матрицы Якоби ~". Пусть для решения системы линейных алгебраических уравнений используется схема частичного выбора (см. 3 5.5). Будем считать, что матРица ~' достаточно хоРошо обУсловлена (сопд(1') ~;и < 1) и вычисляется не слишком грубо (~~Д' — (1') *$ < '11'1). Тогда при выборе начального приближения из малой окрестности решения метод Ньютона является устойчивым и дает возможность найти решение с гарантированной точностью е е = ~(Г(х)) '1~10 ) $7.4. Модификации метода Ньютона Если оценивать качество метода Ньютона только по числу необходимых итераций, то следовало бы сделать вывод о том, что этот метод стоит применять всегда, когда он сходится.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
