Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 37

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 37)

Напомним, чта функция э(х) называется липшиц-непрерывной с постоянной у на множестве Х, если для всех х', х"АХ выполняется неравенство ) з(х') — з(х") ] ~с)1х' — х"). (4) В дальнейшем в качестве Х будем брать отрезок (/,(а) =(х: ]х — и) ~») (5) длнны 2» с серединой в точке а. 196 6. Использование обратной интерполяции. Ряд итерационных методов можно получить с помощью интерполирования функции х=ср(у), обратной 1с(х). Заметим, что если х. — корень уравнения 1(х) =О, то ср(0) =х.. Таким образом, задача нахождения корня х, сводится к вычислению значения ср(О).

Предположим, что известны приближения х... л.„..., х,, к корню х.. Тогда можно нычислить у,=)(х,), с=О, 1,..., п, н считать, что по переменной д заданы узлы у„, д„..., д„н в них известны значения л„=ср(у„),..., х„=ср(у„), Па данным (уь ср(у ) ), с'=О, 1,..., и, строится интерполяцнанный многочлен 1,„(д) для функции ср(у) и в качестве следующего приближения х„., берется Е„(0). Линейная обратная интерполяция (п=1) приводит к методу секущих. !(вадратичная обратная интерполяция (п= 2) приводит к методу лссс=лс эсср(ус ус-с)+хс-сгсср(ум ус-с ус-с), отличному от метода парабол. Здесь ср(ум дл- ) и ср(ум у —, У вЂ”.)— разделенные разности первого н второго порядков саотвстственно. Сделаем следующее замечание.

Перечисленные выше итерационные методы в случае сходимости позволяют при заданных начальных приближениях найти лишь один из корней уравнения (1). Чтобы отыскать другие корни, надо менять начальные приближения. Может оказаться, что н прн других начальных данных метод сходится к таму же корню х=х.. Тогда целесообразно отделить этот корень, т.

е. применить итерационный метод к у(х) =)(х)с(х — х.). в 2. Сходимость метода простой итерации Теорема 1. Если з(х) липшиц-непрерывна с постоянной аеи ен(0, 1) на отрезке (1„(а), причем ! з (а) — а ( «(! — д) г, (6) то уравнение (2) имеет на отрезке 0,(а) единственное решение х, и метод простой итерации (3) сходится к х.

при любом начальном приблизсении х,~~/,(а), Для погрешности справедлива оценка 1»,— ».) =д'1»,— ».), й=О, 1, 2, (О Доказательство. Сначала докажем по индукции, что хке ев(1,(а), й=1, 2, ..., т, е. что метод простой итерации не выводит за пределы того множества, на котором з(х) липшиц-непрерывна с постоянной цен(0, 1). Предположим, что »1е=У,(а) при некотором 1)0, и докажем, что тогда х„„еи(1',(а). Из равенства х,,— а=з(х;) — а= (з(х) — в(а))+ (з(а) — а) получим 1»11.— а) «)в(»1) — з(а) 1+1з(а) — а).

Учитывая условие липшиц-непрерывности, предположение индук- ции и условие (6), имеем 1з(»1) — з(аЦ «д(х; — а) =.цг, )»1ч1 — а ( «дг + (1 — 11) т «г, т. е. »1+,АУ„(а). Оценим теперь разность двух соседних итераций х,,— х,. Имеем х„,— х;=в(х,) — з(х;,), и поскольку все точки хь 1 = 1, 2, ..., находятся на отрезке (/,(а), получаем оценку )»1Р.— х,) «д1»,— х1,) и, следовательно, )»,1,— х,) =д'1»,— х,), 1=1, 2,... (8) Оценка (8) позволяет доказать фундаментальность последовательности (х,).

Действительно, пусть р — любое натуральное число. Тогда Р хк,р — хр = ~ (х„; — хр„;,), 1=1 и согласно (8) имеем Р ~ р ) хыр — хк ) «1»1 — х„) '~~ ц"'1-' = ц' — 1»1 — х„) « — )»1 — хр), ! — д ! — д 1'=1 т. е. 1»ыр — хр1« ~ ~1»1 — хр ), й, р = 1, 2, 1 — е Поскольку правая часть неравенства (9) стремится к нулю при )г- оо и не зависит от р, последовательность (х») является фундаментальной. Следовательно, существует 1цп х»= с Е= (7 (а) Переходя в (3) к пределу при (с — со н учитывая непрерывность функции з(х), получим х,=з(х.), т. е. х.— решение уравнения (2). Предположим, что х.' — какое-то решение уравнения (2), принадлежащее отрезку (7„(а). Тогда х, — х' =з(х,) — з(х') и по условию теоремы )х — х ) < д ) х.

— х !. Так как в<1, последнее неравенство может выполняться лишь при х.'=х„т. е. решение единственно. Докажем оценку погрешности (7). Из уравнения (3) получим х»»,— х.=з(х„) — х,=з(х„) — л(х.), и так как х„, х.~У,(а), приходим к неравенству ) х„„— х, ! ='д (х„— х, ), (10) справедливому для всех 77=0, 1, ..., из которого и следует оценка (7). Теорема 1 доказана. 3 з меча я не 1. Если для погрешности какого-либо нтерацпонного метода выполняется неравенство 1«„— «.1(м»ч»1«» — «.1, где д~(0, 1) и М~ пе зависит ог д то говорят, что метод сходится лпяейяо со скоростью геометрической прогрессии со знаменателем д. Такая терминология объясняется тем, что пря й о» погрешность убывает нзк д».

Замечание х. Зафиксируем и неравенстве (9) яндеяс й я устремим р к бесконечности. Тогда получим оценку погрешности 1«» — хь)~ — )з(ха) — «о1, й= 1, 2... ° ч (11) 1 † правую часть оценки (!1) яходят только яззестпые аелячяяы, в то время кзк опенка (7) содержит заранее неизвестное значение «.. Приведем следствия из теоремы 1, содержащие более удобные для проверки условия сходимости. Будем предполагать, что з(х) непрерывно дифференцируема на отрезке У,(а), С л е д с т в и е 1. Если (л'(х) ( ='д<1 (12) для хее(7,(а), вьтолнено условие (6) и х,я(7,(а), то уравнение (2) имеет единственное решение х,~И,(а), метод (3) сходится и справедлива оценка (7). Действительно, из (12) следует (4) с де=(0, 1).

197 Следств не 2, Пусть уравнение (2) имеет решение х., функг(ия з(х) непрерывно дифференцируетва на отрезке и„(«,)=(х: ~« — х,) <т) (!3) и )в'(х,) ! <1. Тогда существует е)0 такое, что на отрезке К(х,) уравнение (2) не илиеет других решений и лсетод (3) сходится, если только х„ен(л',(х.). Д о к а з а т е л ь с т в о. Поскольку в (х) непрерывно дифференцируема на отрезке (Т,(х.) и )в'(х.) (<1, найдутся числа вез(0, 1) и ее=(0, т) такие, что )в'(х) ) (д< 1 для всех хен(Т,(х,). 2.

Метод Эйткена ускорения сходимости. Предположим, что ка- кой-либо итерационный метод имеет линейную сходимость, т. е. х,— «.=ау', д~(0, 1), )г=1, 2,... Числа а, а, х. заранее неизвестны, но их можно найти, используя трн последовательных итерации х,, х„„ х,, Составим уравнения х,— «. = аг(", х„»,— х, = ал)" »', х„,— «. = ау'»' (здесь равенства надо понимать как приближенные), из которых найдем Лхь = хь,„— х, = ад' (д — 1), тл'«ь = Лхь„— Л«л = ау" (д — 1)', (Лх,,)' х.= хь,— Л'» (14) Метод Эйткена ускорения сходимости состоит в том, что после вычисления х„х,»„х„, производится пересчет по формуле (Лхл»,)л улн =хе.»вЂ” (15) Л'хь 198 и значение у„„принимается за новое приближение.

Гслн бы равенство (14) выполнялось точно, то у,, совпало бы с точным решением х.. В общем случае у„„дает лучшее приближение к х., чем очередная итерация х„, Подчеркнем, что главным предположением здесь является требование линейной сходимости основного итерационного метода. В случае методов, имеющих более высокую скорость сходпмостп (напрнмер метода Ньютона), ускорение по Эйткену в форме (15) неэффективно. На практике не обязательно проводить пересчет по формуле (15) на каждой итерации )г.

Употребительиы методы, в которых такой пересчет осушествляется циклически, т. е. через определенное число основных итераций. С помошью метода Эйткена на основе известных итерационных методов можно получить иногда новые итерационные методы, об- ладаюшне оолее высокой сходимостью. Рассмотрим, например, ме- тод релаксации +/(х») = О (см.

(6) из 9 1), который имеет линейную сходимость, если Л~,~/'(х) ~О, О~ ~2'М,. (16) Предполозкпм, что прп некотором /г получены значения х„ х„„, х„,. Вычислим согласно (15) величину (*»; х»ы) //»ы = х»»»в ! '»»»я~» + х» и исключим из (17) с помощью (!6) величины х,„„х„,. Имеем х»ы — х» т/ (х»)> х», = х»»м — т/ (х»,») = .㻠— т/(х») — т/ (х» — т/'(х»)), следовательно, /» с .) и»„= х... — т / (х») — / (.~„— т/ (х») ) Проведенные построения позволяют предположить, что одношагоный итерационный метод / (9») 𻻠— — у» — т (18) / Ы вЂ” / (໠— т/ Ь»)1 обладает более оыстрой сходнмостью, чем исходный метод релак- сации (16).

Действительно, как показано, например, в (25), метод (18) при т=1 (метод Стеффенсена) имеет квадратичную сходи- мость. 9 3. Сходимость метода Ньютона / (х») х»», = х» — , /г = О, 1, ... /' (х») Заметим прежде всего, что (2) ногино рассматривать как част. ный случай метода простой итерации х„,=з(х„), /г=о, 1, ..., (3) (2) для которого з(х) =х —— /ОО /' (х) (4) 199 1. Простой вещественный корень. Предположим, что уравнение /(х) =О (1) имеет простой вещественный корень х=х, так что /(х.) = О, /'(х.)ФО. Будем предполагать, что /(х) дважды непрерывно*дифференцируема в окрестности корни х..

Исследуем сходимость метода Ньютона В $2 было показано, что для сходимости метода (3) достаточно потребовать, чтобы в некоторой окрестности искомого корня выполнялось неравенство (з'(х) ) (д(1. (5) Для функции (4) имеем з'(х) =~ (р (х))~ и если х. — корень ~(х), то в'(х.) =О. Поэтому найдется окрестность корня, в которой выполнено неравенство (5).

Тем самым при надлежащем выборе начального приближения метод Ньютона сходится. Однако следствием малости з'(х) в окрестности х является не просто сходимость, а сходимость существенно более быстрая, чем в общем случае метода простой итерации. В следующей теореме доказано, что метод Ньютона имеет квадратичную сходимость, т. е. что он сходится и погрешность на (й+1)-й итерации пропорциональна квадрату погрешности на я-й итерации. Теорема 1.

Характеристики

Список файлов книги