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

Методы решения нелинейных уравнений делятся на две группы:

1. точные методы
;
2. итерационные методы
.

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

Как известно, многие уравнения и системы уравнений не имеют аналитических решений. В первую очередь это относится к большинству трансцендентных уравнений. Доказано также, что нельзя построить формулу, по которой можно было бы решить произвольное алгебраическое уравнение степени выше четвертой. Кроме того, в некоторых случаях уравнение содержит коэффициенты, известные лишь приблизительно, и, следовательно, сама задача о точном определении корней уравнения теряет смысл. Для их решения используются итерационные методы с заданной степенью точности.

Пусть дано уравнение

1. Функция f (x ) непрерывна на отрезке [a, b ] вместе со своими производными 1-го и 2-го порядка.
2. Значения f (x ) на концах отрезка имеют разные знаки (f (a ) * f (b ) < 0).
3. Первая и вторая производные f" (x ) и f"" (x ) сохраняют определенный знак на всем отрезке.

Условия 1) и 2) гарантируют, что на интервале [a, b ] находится хотя бы один корень, а из 3) следует, что f (x ) на данном интервале монотонна и поэтому корень будет единственным.

Решить уравнение (1) итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.

Всякое значение , обращающее функцию f (x ) в нуль, т.е. такое, что:

называется корнем уравнения (1) или нулем функции f (x ).

Задача нахождения корня уравнения f (x ) = 0 итерационным методом состоит из двух этапов:

1. отделение корней
- отыскание приближенного значения корня или содержащего его отрезка;
2. уточнение приближенных корней
- доведение их до заданной степени точности.

Процесс отделения корней начинается с установления знаков функции f (x ) в граничных x = a и x = b точках области ее существования.

Пример 1. Отделить корни уравнения:

f(x ) є x 3 - 6х + 2 = 0.

Составим приблизительную схему:

Следовательно, уравнение (2) имеет три действительных корня, лежащих в интервалах [-3, -1], и .

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

В инженерной практике распространен графический способ определения приближенных корней.

Принимая во внимание, что действительные корни уравнения (1) - это точки пересечения графика функции f (x ) с осью абсцисс, достаточно построить график функции f (x ) и отметить точки пересечения f (x ) с осью Ох, или отметить на оси Ох отрезки, содержащие по одному корню. Построение графиков часто удается сильно упростить, заменив уравнение (1) равносильным ему уравнением:

Уравнение (4) удобно переписать в виде равенства:

Отсюда ясно, что корни уравнения (4) могут быть найдены как абсциссы точек пересечения логарифмической кривой y = lg x и гиперболы y = . Построив эти кривые, приближенно найдем единственный корень уравнения (4) или определим его содержащий отрезок .

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

Для нахождения корня уравнения (1), принадлежащего отрезку [a, b ], делим этот отрезок пополам. Если f = 0 , то x = является корнем уравнения. Если f не равно 0 (что, практически, наиболее вероятно), то выбираем ту из половин или , на концах которой функция f (x ) имеет противоположные знаки. Новый суженный отрезок [ а 1 , b 1] снова делим пополам и производим те же самые действия.

Метод половинного деления практически удобно применять для грубого нахождения корня данного уравнения, метод прост и надежен, всегда сходится.

Пример 3. Методом половинного деления уточнить корень уравнения

f(x ) = x 4 + 2 x 3 - x - 1 = 0

лежащий на отрезке [ 0, 1] .

Последовательно имеем:

f(0) = - 1; f (1) = 1; f (0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;

f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;

f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;

f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;

f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;

f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 и т. д.

Можно принять

x = (0,859 + 0,875) = 0,867

В данном методе процесс итераций состоит в том, что в качестве приближений к корню уравнения (1) принимаются значения х 1 , х 2 , ..., х n точек пересечения хорды АВ с осью абсцисс (Рисунок 3). Сначала запишем уравнение хорды AB :

.

Для точки пересечения хорды AB с осью абсцисс (х = х 1 , y = 0) получим уравнение:

Пусть для определенности f"" (x ) > 0 при а х b (случай f"" (x ) < 0 сводится к нашему, если записать уравнение в виде - f (x ) = 0). Тогда кривая у = f (x ) будет выпукла вниз и, следовательно, расположена ниже своей хорды АВ . Возможны два случая: 1) f (а ) > 0 (Рисунок 3, а ) и 2) f (b ) < 0 (Рисунок 3, б ).

Рисунок 3, а, б.

В первом случае конец а неподвижен и последовательные приближения: x 0 = b ;x , где функция f (х ) имеет знак, противоположный знаку ее второй производной f"" (х ).

Итерационный процесс продолжается до тех пор, пока не будет обнаружено, что

| x i - x i - 1 |< e ,

где e - заданная предельная абсолютная погрешность.

Пример 4. Найти положительный корень уравнения

f(x ) = x 3 - 0,2 x 2 - 0,2 х - 1,2 = 0

с точностью e = 0,01.

Прежде всего, отделяем корень. Так как

f (1) = -0,6 < 0 и f (2) = 5,6 > 0,

то искомый корень x лежит в интервале . Полученный интервал велик, поэтому разделим его пополам. Так как

f (1,5) = 1,425 > 0, то 1< x < 1,5.

Так как f"" (x ) = 6 x - 0,4 > 0 при 1 < х < 1,5 и f (1,5) > 0, то воспользуемся формулой (5) для решения поставленной задачи:

= 1,15;

| x 1 - x 0 | = 0,15 > e ,

следовательно, продолжаем вычисления;

f (х 1) = -0,173;

= 1,190;

|x 2 - x 1 | = 0,04 > e ,

f (х 2) = -0,036;

= 1,198;

| x 3 - x 2 | = 0,008 < e .

Таким образом, можно принять x = 1,198 с точностью e = 0,01.

Заметим, что точный корень уравнения x = 1,2.

где функция f(x) определена и непрерывна на некотором конечном или бесконечном интервале x . В частности, в форме нелинейных уравнений представляются математические модели анализа статических свойств объектов проектирования или их элементов. Если функция f(x) представляет собой многочлен n-й степени видаa0 + a1 x + a2 x2 + ... + anxn, то уравнение (1) называется алгебраическим. Когда x находится под знаком трансцендентной функции (показательной, логарифмической, тригонометрической и т.п.), уравнение называется трансцендентным. Значение аргумента x, при котором функция f(x) обращается в нуль, т.е. f(x*) = 0, называется корнем уравнения.

В общем случае для функции f(x) не существует аналитических формул для нахождения корней. Более того, их точное вычисление не всегда является необходимым. Это объясняется тем, что встречающиеся в инженерной практике уравнения часто содержат коэффициенты, величины которых имеют приближенные значения. В таких случаях решается задача определения корней с некоторой заранее заданной степенью точности.

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

• 1) отделение корней, т.е. нахождение интервалов , внутри которых содержится один и только один корень уравнения;
• 2) уточнение приближенных значений отдельных корней до заданной степени точности.

Этап отделения корней может быть выполнен различными способами. Во-первых, приближенное значение корня иногда бывает известно из физического смысла задачи. Во-вторых, для отделения корней может использоваться графический способ, основанный на построении графика функции

нелинейный уравнение половинный деление

где приближенные значения действительных корней уравнения f(x) = 0 соответствуют абсциссам точек пересечения или касания графика с осью 0x (y = 0). Наиболее часто применяется метод отделения корней, основанный на следующем положении: если на концах некоторого интервала значения непрерывной функции f(x) имеют разные знаки, т.е. f(a)f(b) , то на этом интервале уравнение (1) имеет хотя бы один корень. При этом корень является единственным, если производная функции f"(x) существует и сохраняет постоянный знак внутри интервала .Рассмотрим простейший алгоритм отделения корней нелинейных уравнений, ориентированный на использование ЭВМ. Исходный интервал [, ], на котором определена и непрерывна функция f(x), разбивается на n отрезков равной длины

(x0, x1), (x1, x2), ..., (xn -1, xn),где x0 x1 ...xn и x0 = , xn =

Затем вычисляются значения функции f(xj) в точках xj (j =) и выбирается отрезок (xi, xi+1), на концах которого функция имеет разные знаки, т.е. f(xi)f(xi+1) 0. Если длина этого отрезка достаточно мала (можно предположить единственность корня), то считается, что корень отделен на интервале , где a = xi, b = xi+1. В противном случае границы исходного интервала сдвигаются, т.е. = xi, = xi + 1, и процедура повторяется.

Необходимо отметить, что длина исходного интервала , на котором определена функция f(x), может изменяться в широких пределах. Поэтому число отрезков n, а также длина искомого интервала являются переменными величинами, которые должны задаваться в каждом конкретном случае с учетом физического смысла решаемой задачи.

На втором этапе решения нелинейных уравнений полученные приближенные значения корней уточняются различными итерационными методами до некоторой заданной погрешности.

Метод половинного деления. Для этого метода существенно, чтобы функция f(x) была непрерывна и ограничена в заданном интервале , внутри которого находится корень. Предполагается также, что значения функции на концах интервала f(a) и f(b) имеют разные знаки, т.е. выполняется условие f(a)f(b) .

Обозначим исходный интервал как . Для нахождения корня уравнения f(x) = 0 отрезок делится пополам, т.е. вычисляется начальное приближение x0 = (a0 + b0)/2. Если f(x0) = 0, то значение x0 = x* является корнем уравнения. В противном случае выбирается один из отрезков или , на концах которого функция f(x) имеет разные знаки, так как корень лежит в этой половине. Далее выбранный отрезок обозначается как , вновь делится пополам точкой x1 = (a1 + b1)/2 и т.д. В результате на некоторой итерации получается точный корень x* уравнения f(x) = 0, либо бесконечная последовательность вложенных отрезков , , ..., , ..., таких, что f(ai)f(bi) (i =1, 2, ...), сходящихся к корню x*.

Если требуется определить корень x* с погрешностью, то деление исходного интервала продолжают до тех пор, пока длина отрезка не станет меньше 2, что записывается в форме условия bi - ai 2.

В этом случае середина последнего интервала с требуемой степенью точности дает приближенное значение корня

x* (ai + bi) / 2.

Метод половинного деления легко реализуется на ЭВМ и является наиболее универсальным среди итерационных методов уточнения корней. Его применение гарантирует получение решения для любой непрерывной функции f(x), если найден интервал, на котором она изменяет знак. В том случае, когда корни не отделены, будет найден один из корней уравнения. Метод всегда сходится, но скорость сходимости является небольшой, так как за одну итерацию точность увеличивается примерно в два раза. Поэтому на практике метод половинного деления обычно применяется для грубого нахождения корней уравнения, поскольку при повышении требуемой точности значительно возрастает объем вычислений.

Министерство общего и профессионального образования

Стерлитамакский Государственный Педагогический Институт

кафедра информатики и вычислительной техники

КУРСОВАЯ РАБОТА

«Метод половинного деления в школьном курсе информатики»

Работу выполнили студенты 42 группы ФМФ: Дубовицкий Сергей и Волков Антон

Руководитель: доцент Хусаинова Г.Я.

Стерлитамак 2001

Введение

Метод половинного деления................................................................................................................................................... 4

Задача......................................................................................................................................................................................................... 4

Алгоритм................................................................................................................................................................................................... 6

Блок схема................................................................................................................................................................................................. 7

Заключение............................................................................................................................................................................................... 8

Литература................................................................................................................................................................................................. 9

Целью данной курсовой работы является раскрытие содержания темы «Метод половинного деления» и дальнейшее ее закрепление путем выполнения лабораторной работы и практических заданий.

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

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

В школьном курсе информатики метод половинного деления изучается в 11 классе на 42 уроке при изучении раздела «Компьютерное моделирование», закрепляется тема на 43 уроке в виде Лабораторной работы.

Решение алгебраического уравнения. Для численного решения алгебраических уравнений существует множество способов. Среди самых известных можно назвать метод Ньютона, метод Хорд, и «всепобеждающий» метод Половинного Деления. Сразу оговоримся, что любой метод является приближенным, и по сути дела лишь уточняющим значение корня. Однако уточняющим до любой точности, заданной Нами.

Метод половинного деления или дихотомии (дихотомия - сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f (x)=0 состоит в делении пополам отрезка [ a; b ] , где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка [ a; b ] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [ a; b ] становится меньше заданной погрешности нахождения корня ε , либо функция попадает в полосу шума ε 1 – значение функции сравнимо с погрешностью расчетов.

Сначала поставим задачу. Дана монотонная, непрерывная функция f(x) , которая содержит корень на отрезке , где b>a . Определить корень с точностью ε , если известно, что f(a)*f(b)<0

Дано уравнение вида:

f(x)=0 ; (1)

необходимо найти удовлетворяющие ему значения x .

Итак, приступим к решению. Первым делом, определимся, что значит f(x)=0 . Посмотрите на рис.1. На нем изображен график некоей функции. В некоторых точках этот график пересекает ось абсцисс. Координаты x этих точек нам и нужно найти. Если вид уравнения простой или стандартный, например, квадратное уравнение или линейное, то применять численный метод здесь совершенно ни к чему. Но если уравнение у нас такое:

f(x)=x3-14x2+x+ex ; (2)

то ни в каком учебнике вы не найдете метода аналитического решения этого кошмара. Здесь и приходит на помощь непобедимый численный метод. Метод половинного деления. Из самого названия метода можно предположить, что нам понадобится что-то делить пополам.

Ученикам метод половинного деления можно преподнести в виде решения задачи.

Задача

Идет осада неприятельской крепости. На некотором расстоянии от нее установили новую пушку. Под каким углом к горизонту надо стрелять из этой пушки, чтобы попасть в заданный участок крепостной стены.

Над моделью этой задачи физики изрядно поработали. Оно и понятно: ведь многие научные задачи, как и эта, возникали прежде всего в военном деле. И решение этих задач почти всегда считалось приоритетным.

Какие же факторы принять за существенные в этой задаче? Поскольку речь идет о средневековье, то скорость снаряда и дальность полета невелики. Значит можно считать несущественным, что Земля круглая (помните обсуждение в параграфе 27), и пренебречь сопротивлением воздуха. Остается единственный фактор – сила земного притяжения. В этом случае, как вы знаете из физики, горизонтальное (х) и вертикальное (у) смещение снаряда за время t описывается формулами

,

где g – ускорение свободного падения, v – начальная скорость снаряда, α – угол наклона пушки к горизонту. Эти формулы задают математическую модель полета снаряда. Нас же интересует, на какой высоте окажется снаряд, пролетев расстояние S .

Впрочем, это нетрудно найти. Выразим время полета снаряда на расстояние S из первой формулы:

,

и подставим во вторую:

Следуя нашей задаче, нам требуется найти такое значение угла наклона α, чтобы снаряд, пролетев заданное расстояние S , попал на нужную высоту Н .

Математик тут бы сказал, что надо решить уравнение. Мы тоже будем решать, только приближенно и очень похоже на то, как делают настоящие артиллеристы. Они же поступают следующим образом: производят несколько выстрелов, беря цель «в вилку», т.е. одно попадание выше цели, а другое ниже. Затем делят пополам угол между этими выстрелами, и при стрельбе под таким углом снаряд ложится к цели намного ближе. Но если все же не попали, то новую «вилку» снова делят пополам и т.д.

Мы заранее можем указать «вилку» для угла: 0 и π/4 (мы надеемся, что вы помните какой угол имеет радианную меру π/4 и чему приближенно равно π ). А дальше будем делить пополам эту «вилку» и смотреть, куда попадает снаряд, пока не добьемся нужного результата.

Как же долго нам придется вести «пристрелку», чтобы получить угол α , с нужной точностью? Чтобы ответить на этот вопрос, отвлечемся от нашей задачи и сформулируем на чисто математическом языке, что и как мы находили.

Нам даны некоторая функция f(x) и отрезок , причем на концах этого отрезка эта функция принимает значения противоположных знаков. Если функция непрерывна, т.е. ее график – непрерывная линия, то ясно, что график функции пересекает ось абцисс в некоторой точке с отрезка , как показано на рисунке 1. Иными словами, f(c) =0 , т.е. с - корень уравнения f(x)=0 .

Как же предлагается находить этот корень? А вот так. Делим отрезок пополам, т.е. берем середину отрезка а+ b/2 . В этой точке вычисляем значение функции f(x) (рис. 2). Если это значение 0, то корень найден; если нет, то оно имеет тот же знак, что и значение на одном из концов отрезка . Тогда этот конец заменям точкой а+ b/2 . Новый отрезок тоже содержит корень уравнения f(x)=0 , поскольку на его концах функция f(x) снова имеет разные знаки. Однако этот отрезок в 2 раза короче предыдущего. И самое главное – с ним можно поступить точно так же . со следующим отрезком еще раз проделать то же самое и т.д. поскольку длина отрезка каждый раз уменьшается вдвое, мы можем получить отрезок сколь угодно малой длины, внутри которого содержится корень уравнения f(x)=0 . Например, если исходный отрезок был , т.е. имел длину 1 , то через десять шагов мы получим отрезок длиной

. Это означает, что концы отрезка дают нам приближенное значение корня с точностью, равной длине отрезка: левый конец отрезка – приближенное значение корня с недостатком, правый конец – приближенное значение корня с избытком.

Пусть f (x ) – непрерывная функция на [a ; b ], .

Метод Ньютона (метод касательных)

Пусть f (x ) – дважды непрерывно дифференцируемая функция на отрезке [a ; b ],
,
и
не меняют знак на [a ; b ].

Обозначим через тот конец отрезка, где знаки
и
совпадают. Последовательные приближения к точному корнюc находим по формуле

для
.

Тогда
является точным корнем уравнения (1).

Вычислительный процесс обычно останавливают, когда
оказывается меньше заданной точностиε . Однако это условие не может строго гарантировать, что заданная точность достигнута. Для полной гарантии можно выполнить проверку точности, как было указано в начале раздела. Если точность не достигнута, то нужно повторить итерации еще несколько раз.

Метод секущих

Пусть есть какое-то начальное приближение . Получим еще одну точку по формуле
, гдеh – небольшое число. Будем считать, что мы выполнили несколько шагов метода, и к данному моменту у нас есть два последовательных приближения и
к точному корню (на начальном этапе – этои). Тогда следующее приближение находим по формуле

,

Процесс останавливается по такому же критерию, как и в методе Ньютона.

Метод итераций

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

Преимущества и недостатки методов

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

Метод Ньютона обладает очень быстрой сходимостью (квадратичная сходимость), т.е.

,

где c – точное значение корня; M – некоторая константа, зависящая от функции. Грубо говоря, начиная с некоторой итерации, число верных знаков после запятой станет удваиваться на каждой итерации.

Для гарантии сходимости метода Ньютона требуется выполнение довольно многих условий. Вообще говоря, начать вычисления по методу Ньютона можно и без проверки этих условий, но тогда сходимость может не наблюдаться.

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

Метод итераций дает скорость сходимости значительно меньшую, чем метод Ньютона. При наличии сходимости действует оценка
, где
– числа,
,
;c –точное значение корня. Величины M , q зависят от функции и не зависят от номера итерации. Если же
близок к 1, тоq тоже близко к 1 и сходимость метода будет медленной. Счет по методу итераций можно начать без проверки условий на
и. В этом случае процесс может оказаться расходящимся, и тогда ответ не будет получен.

Существует много методов нахождения корней нелинейного уравнения, отличных от перечисленных. В MATHCAD функция root в формате
использует метод секущих, а если он не приводит к желаемым результатам, то – метод Мюллера. В последнем, в отличие от метода секущих, на каждом шаге берутся две дополнительные точки, график функции заменяется параболой, проходящей через три точки, и за следующее приближение берется точка пересечения параболы с осьюOx . В функции root в формате root(f (x ), x , a , b ) используются методы Риддера и Брента. Для нахождения корней многочлена в MATHCAD используется метод Лагерра.

Метод половинного деления

Считаем, что отделение корней уравнения f (x ) = 0 проведено и на отрезке [ a , b ] расположен один корень, который необходимо уточнить с погрешностью ε. В качестве начального приближения корня принимаем середину этого отрезка: c 0 = (a + b) / 2 (рис. 4):

Рис. 4. Метод половинного деления.

Затем исследуем значение функции f (x ) на концах отрезков [ a , c 0 ] и [ c 0 , b ] . Тот из отрезков, на концах которого f (x ) принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка [ a 1 , b 1 ] (на рис. 4 это отрезок [ a , c 0 ]). Вторую половину отрезка [ a , b ], на которой f (x ) не меняет знак, отбрасываем. В качестве следующего приближения корня принимаем середину нового отрезка
c 1 = (a 1 + b 1 ) / 2 и т.д. Таким образом, k -е приближение вычисляется как

После каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после k итераций в 2 k раз:

Прекратить итерационный процесс следует, когда будет достигнута заданная точность, т.е. при выполнении условия |x 0 – c k | < ε

Поскольку корень x 0 принадлежит отрезку [ a k , b k ], а c k – середина этого отрезка, то величина |x 0 – c k | всегда будет меньше половины длины от резка [ a k , b k ] (см. рис. 4):

Следовательно, условие |x 0 – c k | < ε будет выполнено, если

| b k – a k | < 2ε

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполнено условие | b k – a k | < 2ε .

В отличие от большинства других методов уточнения, метод половинного деления сходится всегда, т.е. обладает безусловной сходимостью. Кроме этого он чрезвычайно прост, поскольку требует лишь вычисления значений функции f (x ) и, поэтому применим для решения любых уравнений.

Однако метод половинного деления довольно медленный. С каждым шагом погрешность приближенного значения уменьшается в два раза, т.е.

поэтому данный метод является методом с линейной сходимостью.

З а м е ч а н и е . Метод половинного деления не требует знания дополнительной информации о функции на всем интервале [ a , b ]. Например, не требуется, чтобы функция была дифференцируема. Даже для разрывных функций рассмотренный метод обладает гарантированной сходимостью. Если на этом интервале существует несколько корней уравнения, один из корней обязательно будет найден.

Метод хорд

Рассматриваемый метод так же, как и метод половинного деления, предназначен для уточнения корня на интервале [ a , b f (x ) принимает значения разных знаков. Очередное приближение в отличие от метода половинного деления берем не в середине отрезка, а в точке x , где пересекает ось абсцисс прямая линия (хорда), проведенная через точки А и В (рис. 5).

Рис. 5. Метод хорд.

Запишем уравнение прямой, проходящей через точки А и В :

Для точки пересечения прямой с осью абсцисс (x = x 0 , y = 0) получим уравнение

В качестве нового интервала для продолжения итерационного процесса выбираем тот из двух [ a , x 0 ] и [ x 0 , b ], на концах которого функция f (x ) принимает значения разных знаков. Для рассматриваемого случая (рис. 5) выбираем отрезок [ a , x 0 ], так как
f(a) × f(x 0) < 0 . Следующая итерация состоит в определении нового приближения x 1 как точки пересечения хорды AB 1 с осью абсцисс и т.д.

Заканчиваем процесс уточнения корня, когда расстояние между очередными приближениями станет меньше заданной точности, т.е.

x k +1 – x k < ε

З а м е ч а н и е . Метод хорд и метод половинного деления очень похожи. При этом второй их них в ряде случаев дает более быструю сходимость итерационного процесса. Оба метода не требуют знания дополнительной информации о функции на всем интервале [ a , b ]. Например, не требуется, чтобы функция была дифференцируема. Даже для разрывных функций рассмотренные методы обладают гарантированной сходимостью.

Метод Ньютона (метод касательных)

Метод Ньютона также предназначен для уточнения корня на интервале [ a , b ], на концах которого функция f (x ) принимает значения разных знаков. Но этот метод использует дополнительную информацию о функции f (x ). Как результат он обладают более быстрой сходимостью, но в то же время, применим для более узкого класса функций, и его сходимость не всегда гарантирована.

Отделяя корни функции, следует учесть, что применение метода Ньютона требует, чтобы функция была монотонна и дважды дифференцируема, причем вторая производная f’’(x) на этом интервале не должна менять знак.

Cходимость итерационной последовательности, получаемой в методе Ньютона, зависит от выбора начального приближения x 0 . В общем случае, если задан интервал [ a , b ], содержащий корень, и известно, что функция f (x ) монотонна на этом интервале, то в качестве начального приближения x 0 можно выбрать ту границу отрезка [ a , b ], где совпадают знаки функции f (x ) и второй производной f’’(x) . Такой выбор начального приближения гарантирует сходимость метода Ньютона при условии монотонности функции на отрезке локализации корня.

Пусть нам известно начальное приближение к корню x 0 . Проведем в этой точке касательную к кривой y = f (x ) (рис. 6). Эта касательная пересечет ось абсцисс в точке, которую будем рассматривать в качестве следующего приближения.