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

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

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

ГЛАВА 5 РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ УРАВНЕНИЙ 5 1. Примеры итерационных методов решения нелинейных уравнений 1. Введение. Пусть задана функция 1(х) действительного переменного. Требуется найти корни уравнения 1(х) =0 (1) или, что то же самое, нули функции 1(х). Уже на примере алгебраического многочлена известно, что нули 1(х) могут быть как действительными, так и комплексными.

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

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

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

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

Первый прием состоит в том, что вычисляется таблица значений функции)(х) в заданных точках х„~(а, Ь), А=О, 1,..., п. Если обнаружится, что при некотором й числа 1(х,), )(х„+,) имеют разные знаки, то это будет означать, что на интервале (х„х„+,) уравнение (1) имеет по крайней мере один действительный корень (точнее, имеет нечетное число корней на (х„, х„т,)). Затем можно разбить интервал (х„х,+,) на более мелкие интервалы и с помощью аналогичной процедуры уточнить расположение корня.

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

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

Заметим, что если на (а, Ь) имеется несколько корней, то указанный процесс сойдется к одному из корней, но заранее неизвестно, к какому именно. Можно использовать прием выделения корней: если корень х=х. кратности и найден, то рассматривается функция д(х) =)(х)/(х — х.)'" и для нее повторяется процесс нахождения корня.

2.! Метод простой итерации. Он состоит в том, что уравнение (1) заменяется эквивалентным уравнением х=з(х) (3) и итерации образуются по правилу х„+,— — з(х„), в=О, 1, ..., (4) 191 причем задается начальное приближение х,. Для сходимости большое значение имеет выбор функции з(х). Эту функцию можно задавать различными способами, однако обычно она берется в виде з(х) =х+т(х)!(х), (5) причем функция т(х) не меняет знака на том отрезке, где отыскивается корень. В 52 будет показано, что метод простой итерации сходится при надлежащем выборе начального приближения х„ если ~ з'(х.) ~ <1, где х.

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

По теореме о среднем имеем !(х.+г„) =!(х.)+г„!'(х.+Ог ) =г„~'(х.+Ог„), где 8~(0, 1). Таким образом, для погрешности метода релаксации выполняется уравнение = 7'(х. + Ог„) г,. Отсюда приходим к оценке !г„„~<~1+т~'(х.+Ог„)~ ~г„!(шах~1+т~'(х,+Ог„)~ ° !г,~, х и если выполнены условия (8), то ~г.+,~ =шахЦ1 — тМ,), !1 — тт,!)!г„~. Таким образом, задача выбора оптимального параметра сводится к нахождению т, для которого функция д(т) =шах(!1 — тМ,~, ~1 — тт,!) принимает минимальное значение. Из рассмотрения графика функции ю)(т) видно, что точка минимума определяется условием 11 — тМ,! =11 — тт,~ н равна т= тю — — 2/(М,+ т,) .

При этом значении т имеем 1 — $ мю у(та) =ра= —, 5=— 1+5 Мю так что для погрешности справедлива оценка (еа ~ ~ ~Рю" !ею ~, и = О, 1, 3. Метод Ньютона. Пусть начальное приближение хй известно. Заменим 1(х) отрезком ряда Тейлора ) (х) =Н, (х) =) (х,) + (х — х,) )'(х,) и за следующее приближение х, возьмем корень уравнения Н,(х) = =О, т. е. 1 (лю) х,=х,— —, Г(.) Вообще, если итерация х, известна, то следующее приближение х„+, в методе Ньютона определяется по правилу ) (хй) хам=хе — —, Й=О, 1, ...

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

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

Самарский, А. В. Гулиа 193 бований к выбору начального приближения х„однако обладает лишь линейной сходимостью, т. е. х„е,— х.=О(х,— х.). Метод (10) гарантирует отсутствие деления на нуль, если Г (х,) ФО, 4. Метод секущих. Этот метод получается из метода Ньютона ) (хг) — ! (хь ) (9) заменой )'(х,) разделенной разностью ', вычискь — хе, ленной по известным значениям х, и х,, В результате получаем итерационный метод хь„=хь — " ' ~(х~), й= 1, 2, ..., (11) ! (хх) — ) (х~ ,) который в отличие от ранее рассмотренных методов является двух- шаговым, т, е.

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

Идея интерполячионных методов состоит в том, что нахождение корней уравнения (1) заменяется нахождением корней интерполяционного многочлена, построенного для 1(х). Интерполяционный метод первого порядка приводит к методу секущих. Интерполяционный метод второго порядка называется методом парабол. Метод Ньютона (9) можно получить, заменяя ((х) интерполяционным многочленом Эрмита первой степени. Получим формулы метода парабол. Пусть приближения х, „ х„„х, известны.

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

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