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

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

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

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

Не существует каких-то общих регулярных приемов решения задачи о расположении корней произвольной функции 1(х). Наиболее полно изучен вопрос о расположении корней алгебраических многочленов )(х) =а,+а,к+ах'+...+а х . (2) Например известно, что если длн многочлена (9) с действительными ноэффнпентамн выполнены неравенства 1(с) > О, 1'(с) ) О, ..., 1<"'>(с) >О„ !90 то положительные корни /(х) не превосходят числа с. Действительно, из формулы Тейлора (х — с)а (х — с)'" / (х) = / (с) + (х — с) /'(с) + /" (с) + ...

+ / '" (с) получаем, что /(х) >О при х)с. Численные методы решения нелинейных уравнений являются, как правило, итерационными методами, которые предполагают задание достаточно близких к искомому решению начальных данных. Прежде чем переходить к изложению конкретных итерационных методов, отметим два простых приема отделения действительных корней уравнения (1). Предположим, что /(х) определена н непрерывна на (а, Ь). Первый прием состоит в том, что вычисляется таблица значений функции /(х) в заданных точках х,~[а, Ь), /с=О, 1,...

„н. Если обнаружится, что при некотором /е числа /(х„), /(х,+,) имеют разные знаки, то это будет означать, что на интервале (х,, х,е,) уравнение (1) имеет по крайней мере один действительный корень (точнее, имеет нечетное число корней на (х„ х„,)). Затем можно разбить интервал (х„, х„е,) на более мелкие интерналы и с помощью аналогичной процедуры уточнить расположение корня. Более регулярным способом отделения действительных корней является лсегод бисекцыи (деления пополам). Предположим, что на (а, Ь) расположен лишь один корень х. уравнения (1). Тогда /(а) и /(Ь) имеют различные знаки, Пусть для определенности /(а) > >О, /(Ь) <О. Положим х,=0,5(а+Ь) и вычислим /(х,).

Если /(хс) < <О, то искомый корень находится на интервале (а, х,), если же /(х,) >О, то х,~(х„Ь). Далее, из двух интервалов (а, х,) и (х„Ь) выбираем тот, на границах которого функция /(х) имеет различные знаки, находим точку х, — середину выбранного интервала, вычисляем /(х,) и повторяем указанный процесс. В результате получаем последовательность интервалов, содержащих искомый корень х,, причем длина каждого последующего интервала вдвое меньше, чем предыдущего, Процесс заканчивается, когда длина вновь полученного интервала станет меньше заданного числа е>0, и в качестве корня х. приближенно принимается середина этого интервала Заметим, что если на (а, Ь) имеется несколько корней, то указанный процесс сойдется к одному из корней, но заранее неизвестно, к какому именно, Можно использовать прием выделения корней: если корень х=х.

кратности т найден, то рассматривается функция д(х) =/(х)/(х — х.)" и для нее повторяется процесс нахождения корня. 2. Метод простой итерации. Он состоит в том, что уравнение (1) заменяется эквивалентным уравнением х=з(х) (3) и итерации образуются по правилу х„,=з(х„), и=О, 1, ..., (4) 191 причем задается начальное приближение х„. Для сходимости большое значение имеет выбор функции з(х).

Эту функцию можно задавать различными способами, однако обычно она берется в виде з(х) =х+т(х)!(х), (б) причем функция т(х) ие меняет знака на том отрезке, где отыскивается корень. В й 2 будет показано, что метод простой итерации сходится при надлежащем выборе начального приближения х„ если )з'(х.) ~ <1, где х.— корень уравнения (1). Отметим, что в форме метода простой итерации (4) можно записать, по существу, любой одношаговый итерационный метод. В частности, если т(х) =-т=сопз1, то получим метод релаксации "=1(х„), п=0, 1, ..., (6) для которого з'(х) = 1+ т!'(х) „и метод сходится при условии — 2<т!"'(х.) <О, (7) Если в некоторой окрестности корпя выполняются условия )'(х) <О, 0<т,< (~'(х) ( <М„ (8) то метод релаксации сходится при теи(0, 2/М,).

Чтобы выбрать оптимальный параметр т в методе релаксации, рассмотрим уравнение для погрешности г„=х„ — х,. Подставляя х„ =х,+г„ в (б), получим уравнение = ! (х„+ г„). т По теореме о среднем имеем 1(х.+г„) =~(х.)+г„!'(х.+Ог„) =г„)'(х.+Ог„), где Оси(0, 1). Таким образом, для погрешности метода релаксации выполняется уравнение "=Г (х. +Ох,) г,.

Отсюда приходим к оценке ) г„„! ~ ) 1 + т!' (х, + Ог„) ) ) г„! ( шах ~ 1 + тГ' (х„+ Ог„) ) ) г„), к н если выполнены условия (8), то ) г„+, ) < гп ах ( ( 1 — тМ, ), ) 1 — тт, ) ) ( г„), Таким образом, задача выбора оптимального параметра сводит- ся к нахождению т, для которого функция д(т) =снах()1 — тМ,), !1 — тт,)) принимает минимальное значение. 492 Из рассмотрения графика функции д(т) видно, что точка минимума определяется условием 11 — тМ,! = ! 1 — тт,! и равна т=та=2((М,+ан,). При этом значении т имеем ! — й лч у(та) — ра — —, $ —— !+а А(, так что для погрешности справедлива оценка т!~р!та!60! 3.

Метод Ньютона. Пусть начальное приближение хь известно. Заменим 1(х) отрезком ряда Тейлора 1(х) = Н, (х) =1 (ха) + (х — х„) 1'(х,) и за следующее приближение х, возьмем корень уравнения Н,(х) = =О, т. е. 1(ха) х„=х р (х„) Вообще, если итерация х„известна, то следующее приближение х„„, в методе Ньютона определяется по правилу 1 (хх) ха„=ха —,, й=О, 1, ... Г (хх) (9) применяют в том случае, когда хотят избежать многократного вычисления производной 1Р(х). Метод (10) предъявляет меньше тре- А. А. Самарский, А.

В. Гулиа 193 Метод Ньютона называют также методом касательных, так как новое приближение х,, является абсциссой точки пересечения касательной, проведенной в точке (х„, )(х,)) к графику функции 1(х), с осью Ох. Исследование сходимости метода Ньютона будет проведено в 5 3. Здесь отметим без доказательства лишь две особенности этого метода.

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

Метод (!0) гарантирует отсутствие деления па нуль, если !'(х,) ~0. 4. Метод секущих. Этот метод получается пз метода Ньютона ! /хз) — ! (."и-1) (9) заменой !'(х„) разделенной разностью ' ' 1-, вычисхь — хп ленной по известным значениям х, и х,, В результате получаем итерационный метод хги=х.,— ' — " ' ~(хп), й=1, 2,,, (!1) ! Ып) — у (хг,) который в отличие от ранее рассмотренных методов является двух.

шаговым, т. е. новое приближение х„.„, определяется двумя предыдущими итерациями х, и х„,. В методе (1!) необходимо задавать два начальных приближения х„и х,. Геометрическая интерпретация метода секущих состоит в следувшем. Через тачки (х„„)(х,,)), (х„!(х,)) проводится прямая, абсцисса точки пересечения этой прямой с осью Ох и является новым приближением х„, Иначе говоря, на отрезке [х, „х„[ функция !(х) интерпалируе~ся многачлепам первой степени и за очередное приближение х... принимается корень этого многочлена. 5. Интерпаляциаиные методы. Идея интерполяг)ионных методов состоит в там, что нахождение корней уравнения (1) заменяется нахождением корней пнтерполяционного многочлена„построенного для [(х). Интерполяционный метод первого порядка приводят к методу секущих.

г!нтерполяцпонный метод второго порядка называется таетодо.и парабол. Метод Ньютона (9) можно получить, заменяя )(х) интерполяцнанным многочленом Эрмнта первой степени. Получим формулы метода парабол. Пусть прибляження х,, х; „х, известны. Построим ннтерполяционный мнагочлен Ньюзона (см. (11) из ф 1 гл. 3) Р,(х) =)(х„) + (х — х,))(х, х„,) + (х — х,) (х — х„,)!(хь х, „х,,) и обозначим г=х — х„. Тогда уравнение Рп(х) =0 примет вид иг"-+ог+с=0, (12) где а=)(х„, х, „ х„ ,), 5=[(х„ х„ ,) )- (х„ — х„ ,)[(х„ х, „ х, ,), с= =1(х„). Решая уравнение (12), получим два, может быть комплексных, корня, гга и г'""', по которым вычислим хо'=х„+г'", х'п=л,+г'-'. В качестве следующего приближения в методе парабол выбирается то из значений х'", х"', которое ближе к х„, т. е.

отвечающее минимальному по модулю корню уравнения (!2). Метод парабол удобен тем, что позволяет получить комплексные корни уравнения (7), пользуясь вещественными начальными приближениями х,, х„х,. !. Теорема о сходимости. Перепишем уравнение 1'(х) =0 в эквивалентном виде х=з(х) (2) и рассмотрим метод простой итерации х,сс=э(х„), п=О, 1, ..., х, задан. (3) Говорят, что итерационный метод сходится, если последовательность (х,) имеет предел при сс-~-ссо. В следующей теореме формулируются условия на функцию з(х), гарантирующие существование и единственность решения уравнения (2) и сходимость метода простой итерации к этому решению.

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

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