Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 36
Текст из файла (страница 36)
Построим интерполяционный многочлен Ньютона (см. (11) из 9 1 гл. 3) Р,(х) =)(х„) + (х — х„))(х„, х,,) + (х — х,)(х — х„,))(х„ х, „ х,,) н обозначим з=х — х,. Тогда уравнение Р,(х) =0 примет вид аг'+ Ьг+ с = О, (12) где а=)'(х„ х, „ х,,), б=~(хь х„,) + (х„ — х,,)1(хм х„ „ х,,), с= =Пх,). Решая уравнение (12), получим два, может быть комплексных, корня, г"' и г"', по которым вычислим хо'=х„+з'", хо>=х,+го'. В качестве следующего приближения в методе парабол выбирается то из значений х'", х'", которое ближе к х„т. е. отвечающее минимальному по модулю корню уравнения (12).
Метод парабол удобен тем, что позволяет получить комплексные корни уравнения (7), пользуясь вещественными начальными приближениями х„х„х,. !94 1. Теорема о сходимости. Перепишем уравнение )(х) =0 в эквивалентном виде х=з(х) (2) и рассмотрим метод простой итерации х,,=з(х,), А=О, 1, ..., х, задан. (3) Говорят, что итерационный метод сходится, если последовательность (х») имеет предел при А — »оо. В следующей теореме формулируются условия на функцию з(х), гарантирующие существование и единственность решения уравнения (2) и сходимость метода простой итерации к этому решению.
Напомним, что функция з(х) называется липшиц-непрерывной с постоянной д на множестве Х, если для всех х', х"енХ выполняется неравенство ) з(х') — з(х") ) (д)х' — х"). (4) В дальнейшем в качестве Х будем брать отрезок У,(а) =(х: !х — а) <г) (5) длины 2г с серединой в точке а. 7» 195 6.
Использование обратной интерполяции. Ряд итерационных методов можно получить с помощью интерполирования функции х=~р(у), обратной 1'(х). Заметим, что если х.— корень уравнения )(х) =О, то ~р(0) =х„Таким образом, задача нахождения корня х. сводится к вычислению значения ~г(0). Предположим, что известны приближения х„х„..., х„к корню х.. Тогда можно вычислить у,=г(х;), 1=0, 1,..., и, и считать, что по переменной у заданы узлы у„у„..., у„и в них известны значения х,=»э(у,), ..., х„=ср(у„). По данным (у„гр(у,)), 1=0, 1,..., и, строится интерполяционный многочлен Е„(у) для функции»р(у) и в качестве следующего приближения х„„, берется г'.„(0).
Линейная обратная интерполяция (и= 1) приводит к методу секущих, Квадратичная обратная интерполяция (я=2) приводит к методу х„„ =х„ — х»»р(у„ у» ,) +х» ,х»»р (у», у»-„ у»-»), отличному от метода парабол. Здесь ср(у„у»,) и ср(у», у —, у»- )— разделенные разности первого и второго порядков соответственно. Сделаем следующее замечание. Перечисленные выше итерационные методы в случае сходимости позволяют при заданных начальных приближениях найти лишь один из корней уравнения (1). Чтобы отыскать другие корни, надо менять начальные приближения.
Может оказаться, что и при других начальных данных метод сходится к тому же корню х=х.. Тогда целесообразно отделить этот корень, т. е. применить итерационный метод к д(х) =)(х)Дх — х.). 5 2. Сходимость метода простой итерации Теорема 1. Если з(х) липшиц-непрерывна с постоянной оен ен(0, !) на отрезке с»'„(а), причем 1з(а) — а1((1 — о)г, (6) то уравнение (2) имеет на отрезке 11,(а) единственное решение х.
и метод простой итерации (3) сходится к х. при любом начальном приблизсении х,енс»',(а). Для поерешности справедлива оценка )х„— х.) (»)")х,— х,), я=О, 1, 2,... (О Д о к а з а тел ь с т в о. Сначала докажем по индукции, что х,е. ен(1,(а), й=1, 2, ..., т. е. что метод простой итерации не выводит за пределы того множества, на котором з(х) липшиц-непрерывна с постоянной оен(0, 1).
Предположим, что х,Ы,(а) при некотором 1)0, и докажем, что тогда х+»~У,(а). Из равенства х,,— а=з(х,) — а= (з(х;) — з(а)) + (з(а) — а) получим )х1, — а) = 1з(х,) — з(а)1 + )з(а) — а). Учитывая условие липшиц-непрерывности, предположение индук- ции и условие (6), имеем !з(х1) — з(а)! (д1х; — а(~~»)г, ! х;„, — а ~ ( цг + (1 — о) г:- г, т.
е. х,+,вне„(а). Оценим теперь разность двух соседних итераций х;~,— хь Имеем х,.„,— х, = з (х;) — з (х,,), и поскольку все точки хь 1= 1, 2, ..., находятся на отрезке с»',(а), получаем оценку )х„.,— х,) (д)х; — х; »! и, следовательно, )х+» — х;) (д')х,— х,), 1=1, 2,... (8) Оценка (8) позволяет доказать фундаментальность последовательности (хь). Действительно, пусть р — любое натуральное число. Тогда о хь».„— хь = 'Я (хь„— хь„чн), 1=1 и согласно (8) имеем р ь»- -1 ч ь )хь, — хь)(1х,— хь)~~р д~'»-'=»)ь — )х,— хь)( — х,— хь(, 1 — ч 1 — д т.
е. (9) 1хщ,— хь1( — )хт — хь), й, р=1, 2, ч' 1 — д Поскольку правая часть неравенства (9) стремится к нулю при й-ьоо и не зависит от р, последовательность (х,) является фундаментальной. Следовательно, существует 1пп ха = х. Е= (?, (а). Переходя в (3) к пределу при й- оо и учитывая непрерывность функции з(х), получим х.=з(х.), т. е. х. — решение уравнения (2). Предположим, что х.' — какое-то решение уравнения (2), принадлежащее отрезку У„(а).
Тогда х, — х' = з (х.) — з (х') и по условию теоремы ! х, — х' ~ < д ! х„— х' ~. Так как у<1, последнее неравенство может выполняться лишь при х.'=х., т. е. решение единственно. Докажем оценку погрешности (?). Из уравнения (3) получим х,+,— х.=з(х,) — х.=з(хь) — з(х.), и так как х„, х.~У,(а), приходим к неравенству (х„,— х. ~ < д ~ хь — х.
~, (10) справедливому для всех й=0, 1, ..., из которого и следует оценка (7). Теорема 1 доказана. Замечание 1. Если для погрешности какого-лвбо нтерацяонного метода выполняется неравенство 1ль — л 1(мгч" (хе — х 1, где дш(0, 1) и М~ не завяснт от й, то говорят, что метод сходится линейно со скоростью геометрической прогрессии со знаменателем д. Такая терминология объясняется тем, что при Ьа.со погрешность убывает как Еа. Замечание 2. Зафиксируем в неравенстве (9) индекс й и устремим р н бесконечности. Тогда получим оценку погрешности (ка — х, ! ~( — ! з(хч) — ке(, А = 1, 2..., г (1Ц 1 — д В правую часть оценки (11) входят только известные величины, в то время как оценка (7) содержит заранее неизвестное значение х .
Приведем следствия из теоремы 1, содержащие более удобные для проверки условия сходимости. Будем предполагать, что з(х) непрерывно дифференцируема на отрезке У.(а). Следствие 1. Если )з'(х) ~ <9<1 (12) для хЫ,(а), вьитолнено условие (6) и х,ен(?„(а), то уравнение (2) имеет единственное решение х,ен(У,(а),метод (3) сходится и справедлива оценка (7). Действительно, из (12) следует (4) с дев(0, 1). 197 ' л едет в ие 2.
Пусть уравнение (2) имеет решение х., функция з(х) непрерывно дифференцируема на отрезке и,(х.) =(х: ~ — х„)<г) (13) и )з'(х.) ( <1. Тогда существует е)0 такое, что на отрезке П,(х.) уравнение (2) не имеет других решений и метод (3) сходится, если только „=и,( .). Д о к а з а т е л ь с т в о. Поскольку в (х) непрерывно дифференцируема на отрезке П,(х.) и )з'(х.) ~ <1, найдутся числа цен(0, 1) и е~(0, г) такие, что ~з'(х) ) <у<1 для всех хек(1,(х.).
2. Метод Эйткена ускорения сходимости. Предположим, что ка- кой-либо итерационный метод имеет линейную сходимость, т. е. х„— х.=аа', ве=(0, 1), й=!, 2,... Числа а, д, х. заранее неизвестны, но их можно найти, используя три последовательных итерации х„ х,~„ х„~,. Составим уравнения х,— х„=ау, х„,— х.=ауь+', х„.,— х,=ау ~ (здесь равенства надо понимать как приближенные), из которых найдем Лхь = хь+, — хь = аць (а — 1), Льхь = ахам — Лхь = ачь (д — 1)~, (Лхь,,)~ х,=хь„— Л~хь (14) Метод Эйткена ускорения сходимости состоит в том, что после вычисления х„, х„„х,, производится пересчет по формуле (Лхь~,)~ уь 1=хь.~— Льхь и значение у,+, принимается за новое приближение.
Если бы равенство (14) выполнялось точно, то у„, совпало бы с точным решением х.. В общем случае у,„, дает лучшее приближение к х., чем очередная итерация х,, Подчеркнем, что главным предположением здесь является требование линейной сходимости основного итерационного метода, В случае методов, имеющих более высокую скорость сходимости (например метода Ньютона), ускорение по Эйткену в форме (15) неэффективно. На практике не обязательно проводить пересчет по формуле (15) на каждой итерации А.
Употребительны методы, в которых такой пересчет осуществляется циклически, т. е. через определенное число основных итераций. С помощью метода Эйткена на основе известных итерационных методов можно получить иногда новые итерационные методы, об- 198 ладающие более высокой сходимостью. Рассмотрим, например, ме- тод релаксации +/(хь)= 0 (см.
(6) из 5 1), который имеет линейную сходимость, если М,)/'(х) )О, 0<т(2/М,. Предположим, что при некотором й получены значения х„хь.ь х,+ь Вычислим согласно (15) величину (-"ьм — ь- )' уь~ — — хь,— (17) хх — 2хь, + хх (16) и исключим из (17) с помощью (16) величины хь.ь х„+,. Имеем хь.~ = хь — т/ (хь), х4„= хь., — т/ (хь.,) = хь — т/ (хь) — т/ (хь — т/(хь)), следовательно, /~ (хх) У4„= Хь — т / (хь) — / (ха — т/ (х )) обладает более быстрой сходимостью, чем исходный метод релак- сации (!6). Действительно, как показано, например, в (261, метод (18) при т=1 (метод Стеффенсена) имеет квадратичную сходи- мость. $ 3. Сходимость метода Ньютона 1.
Простой вещественный корень. Предположим, что уравнение /(х) =0 (1) имеет простой вещественный корень х=х„ так что /(х,) =О, /'(х.)~0. Будем предполагать, что /(х) дважды непрерывно дифференцируема в окрестности корня х,. Исследуем сходимость метода Ньютона / (Х4) хь,=хь — —, 1=0,1, ... /' (хь) Заметим прежде всего, что (2) можно рассматривать как частный случай метода простой итерации х„.„,=з(х,), й=О, 1, ..., (3) (2) для которого Проведенные построения позволяют предположить, что одношаговый итерационный метод /' (у~) Уь.~ = Уь — т (18) /(У~) /(Уь /(Ух)) з(х) =х — —" / (х) /' (х) (4) 199 В $ 2 было показано, что для сходимости метода (3) достаточно потребовать, чтобы в некоторой окрестности искомого корня выполнялось неравенство (з'(х) ((д -1.
(5) Для функции (4) имеем ,. (,) 1(х) Г (х) (р (х))ч и если х,— корень)(х), то з'(х.) =О. Поэтому найдется окрестность корня, в которой выполнено неравенство (5). Тем самым при надлежащем выборе начального приближения метод Ньютона сходится. Однако следствием малости з'(х) в окрестности х. является не просто сходимость, а сходимость существенно более быстрая, чем в общем случае метода простой итерации. В следующей теореме доказано, что метод Ньютона имеет квадратичную сходимость, т.
е. что он сходится и погрешность на (й+1)-й итерации пропорциональна квадрату погрешности на й-й итерации. Теорема 1. Пусть х.— простой вещественный корень уравнения (1) и пусть 1'(х) ~0 в окрестности П„(х.) =(х: )х — х./ (т), Предположим, что )ч(х) непрерывна в У„(х,) и О ( т, = 1п1 ((' (х) ~, Ма = зпр (7" (х) ), (6) хна,<х.> хЮ/,.Щ причем Мь (хь — х,( 2ы1 Тогда если х,енУ,(х,), то метод Ньютона (2) сходится, причем для погрешности справедлива оценка (х,— х. ~ « д*»-' ~ х,— х. ~, (8) где Ма(хо — к„( ~ 1 (9) Доказательство. Из уравнения (2) получим т (хь) хь„— х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
