Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 26

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

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

Алгебраическими уравнениями называются уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлеп является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и др.), называются трансцендентными.

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

Алгоритм нахождения корня уравнения с помощью итерационного метода состо~т из двух агапов: а) отыскания приближенного значения корпя или содержащего его отрезка; б) уточнения приближенного значения до некоторой заданной степени точности, Приближенное значение корпя (начальное приближение) может быть найдено различными способами: из физических соображений, из решения аналогичной задачи при других исходных данных, с помощью графических методов.

Если такие априорные оценки исходного приближения провести не удается, то находят две близко расположенные точки а и Ь, в которых непрерывная ГЛ. 5. НЕЛИНЕЙНЫЕ УРАВНЕНИЯ Г(а) функция Г(х) принимает значения разных знаков, т. е. 1'(а)Г(Ь)(0. В этом случае между точками а и Ь есть по крайней мере одна точка, в которой Г(х) = О. В качестве начального приближения х, можно припять середину отрезка [а, Ь], т. е. х, = (а+ Ь)/2.

Итерационный процесс состоит в последовательном уточнении начального приближения х,. Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корпя х~, х~, ..., х„. Если эти значения с ростом и приближаются к истинному значению корня, то говорят, что итерационный процесс сходится. Ниже рассматриваются некоторые итерационные методы решения трансцендентных уравнений. Они могут использоваться также и для нахождения корней алгебраических уравнений, некоторые особенности решения которых будут рассмотрены в ~ 2.

2. Метод деления отрезка пополам (метод бисекции). Это один из простейших методов нахождения корней не- .- линейных уравнений, Он состоит в следующем, Допустим, что нам удалось найти отрезок [а, Ь), в котором расположено искомое значение корня х = с, т. е. а (с ( ( Ь. В качестве начального приближения корня с.

-принимаем середину этого отрезка, т, е. с, =(а+ Ь)/2. Далее исследуем значения функции Р(х) на концах отрезков [а, со)- и [с„Ь~, т. е. в точках а, с„Ь. Тот из них, на концах которого Г(х) принимает значения разных Г(Ь) знаков, содержит искоУ= Ж ~ мый корень; поэтому его принимаем в качестве но- а со с'г О вого отрезка. Вторую ноас, ловину отрезка [а, Ь~, на которой знак Г (х) не меняется, отбрасываем. В качестве первой итерации Рис, 23. Метод делевкя отрезка коРнЯ принимаем середипополам ну нового отрезка и т. д. Таким образом, после каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, т. е. после п итераций он сокращается в 2" раз. Пусть для определенности г" (а) ( О, г" (Ь) ) 0(рис.'23).

В качестве начального приближения корня примем с, = 9 $. уРАЙнения с Одним неизвестным 157 = (а + Ь) /2. Поскольку в рассматриваемом случае .с (с,) < О, то с. < с < 6, и рассматриваем только отрезок ~с„61. Следующее приближение: с, =(с, + 6)/2. При этом отрезок ~с„6~ отбрасываем, поскольку Г(с,)) О и Г(6) ~ . О, т. е. с, < с < с,. Аналогично находим другне приближения: с. = (с, + с,)/2 и т, д. Рис. 24.

Блок-схема метода деления отрезка пополам Итерационный процесс продолжаем до тех пор, пока значение функции 1'(х) после и-й итерации не станет меньшим по модулю некоторого заданного малого числа е, т. е. ~/'(с„) ~ < в. Можно также оценивать длину полученного отрезка: если она становится меньше допустимой погрешности, то счет прекращается. На рис. 24 .представлена блок-схема итерационного процесса нахождения корня уравнения (5.1) методом деления отрезка пополам.

Здесь сужение отрезка производится путем замены границ а или Ь на текущее значение корня с. При этом значение Р(а) вычисляется лишь один раз, поскольку нам нужен только знак функции /'(х) на левой границе, а он в процессе итераций не меняется, ГЛ, б. НЕЛИНЕИНЫЕ УРАВНЕНИЯ Метод деления отрезка пополам довольно медленный, однако он всегда сходится, т. е. при его использовании решение получается всегда, причем с заданной точностью (разумеется, в рамках разрядности ЭВМ) . Требуемое обычно большее число итераций по сравпению с некото- рыми другими метода- У А ми не является препятствием к применению этого метода, если каждое вычисление значения функции Г(х) пе- О с сложно.

. Метод хорд. Пусть 3. мы нашли отрезок [а, Ь), па котором функция г'(х) меняет знак Для определенности прпРис. 25, Метод хоРд мем Р(а) > О, г" (Ь) < с О (рис. 25). В данном методе процесс итераций состоит в том, что в качестве приближений к корню уравнения (5.1) принимаются значепия сб, с„... точек пересечения хорды с осью абсцисс. Сначала находим уравнение хорды АВб у — Р (а) х — а Р (Ь) — Е (а) Ь вЂ” а' Для точки пересечения ее с осью абсцисс (х = с„у = 0) получим уравнение Ь вЂ” а са — а — Г (Ь) — Р( ) Р(а). (5.2) Далее, сравнивая знаки величин Е(а) и Р(с.) для рассматриваемого случая, приходим к выводу, что корень находится в интервале (а, с,), так как Р(а) Р(сб) ( О. Отрезок [с„Ь1 отбрасываем. Следующая итерация состоит в определении нового приближения с~ как точки пересечения хорды АВ~ с осью абсцисс и т.

д. Итерационный процесс продолжается до тех пор, пока значение т" (с„) не станет по модулю меньше заданпого числа е. Блок-схема метода хорд аналогична приведенной на рпс. 24 для метода деления отрезка пополам с той лишь разницей, что вместо вычисления приближения корня по формуле с =(а+ Ь)/2 нужно использовать формулу (5.2). 8 ь уРАВпкпия с одпим неизвестным 1з9 Кроме того, в блок-схему необходимо ввести операторы вычисления значений Е(х) на границах новых отрезков. Советуем читателю самостоятельно построить блок-схему метода хорд.

Как видим, алгоритмы метода деления отрезка пополам и метода хорд похожи, однако второй из них в ряде случаев дает более быструю сходимость итерационного процесса. При этом успех его применения, как и в методе деления отрезка пополам, гарантирован. 4. Метод Ньютона (метод касательных). Его отличие от предыдущего метода состоит в том, что на Й-й итерации вместо хорды проводится касательная к кривой у = =Е(х) при х=с„и ищется точка пересечения касательной с осью абсцисс.

При этом не обязательно задавать отрезок ~а, Ь~, содержащий корень уравнения (5.1), а достаточно лишь найти некоторое начальное приближение корня х = с, (рис. 26), Рис. 26. Метод касательных Уравнение касательной, проведенной к кривой у= Г(х) в точке Л7, с координатами с, и Р(с,), имеет вид у — Г(с,) = Г'(с,) (х — со). Отсюда найдем следующее приолижение корня с, как абсциссу точки пересечения касательной с осью х (у = 0): с~ = с, — Г (с~) !Г' (с,). Аналогично могут быть найдены и следующие прнолижепия как точки пересечения с осью абсцисс касательных, проведенных в точках ЛХ„М, и т. д.

Формула для п+1-го приближения имеет впд с + = с — Г(с„)!Г'(с„)'. (5.3) ГЛ. 5. НЕЛИНЕЙНЫЕ УРАВНГЕ1ИЯ При зтом необходимо, чтооы г" (с.) не равнялась нулю. Для окончания итерационного процесса может быть использовано или условие !Г (с„)! = е, или условие близости двух последовательных приближений: !с„+, — с„! ( е. Из (5.3) следует, что на каждой итерации объем вычислений в методе Ньютона болыний, чем в рассмотренных ранее методах, поскольку приходится находить значение пе только функции Г(х), но и ее производной. Однако скорость сходимости здесь значительно выше, чем в других методах.

Остановимся па некоторых вопросах, связанных со сходимостью метода Ньютона и его использованием. Имеет место следующая Т е о р е м а. Пусть х = с — корень уравнения (5.1), т. е. Г(с)=0, а Г (с)~0 и Г (х) непрерывна. Тогда существует окрестность В корня с (с~.О) такая, что если начальное приближение с,, принадлежит этой окрестности, то для метода Ньютона последовательность значений (с„) сходится к с при и — . При этом для погрешности корня е. =с„— с имеет место соотношение е„+, р«(с) 2 2 2Г' (с) Фактически зто означает, что па каждой итерации погрешность возводится в квадрат, т. е. число верных знаков корня удваивается. Если с" (с) 2Г' (с) то легко показать, что при 1е„! ( 0.5 после пяти-шести итераций погрешность станет величиной порядка 2-".

Это наименьшее возможное значение погрешности при вычислениях на современных ЭВМ да1ке с удвоенной точпость1о. Заметим, что для получения столь малой погрешности в методе деления отрезка пополам потреоовалось бы более 50 итераций. Трудность в применении метода Ньютона состоит в выборе начального приближения, которое должно находиться в окрестности Й.

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

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