В методе бисекции нахождения корней нелинейных уравнений за начальное приближение корня принимают (6 видео)

Метод деления отрезка пополам (метод бисекции)

Один из простейших методов нахождения корней нелинейных уравнений состоит в следующем. Допустим, что нам удалось найти отрезок [а, b], на котором расположено искомое значение корня (далее мы предполагаем, что х = с – единственный корень на отрезке [а, b], а если корней на [а, b] несколько, то в результате применения метода деления отрезка пополам и метода хорд (см. разд. 1.1.3) будет найдено приближенное значение одного из корней) х = с, т.е. .

В качестве начального приближения корня с0 принимаем середину этого отрезка: с0=(а+b)/2. Далее исследуем значения функции F(x) на концах отрезков [а, с0] и [с0, b], т.е. в точках а, с0, b. Тот из отрезков, на концах которого F(x) принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка [a1,b1]. Вторую половину отрезка [а, b], на которой знак F(x) не меняется, отбрасываем. В качестве первого приближения корня принимаем середину нового отрезка c1 = (a1+b1)/2 и т.д. Таким образом, k-е приближение вычисляем как

(1.2)

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

(1.3)

Пусть приближенное решение требуется найти с точностью до некоторого заданного малого числа ε > 0:

(1.4)

Взяв в качестве приближенного решения k-еприближение корня: , запишем (1.4) с учетом обозначения — сk в виде:

(1.5)

Из (1.2) следует, что (1.5) выполнено, если

(1.6)

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполнено условие (1.6).

Метод деления отрезка пополам проиллюстрирован на рис. 1.1. Пусть для определенности F(a) 0. В качестве начального приближения корня примем с0 = (а + b)/2. Поскольку в рассматриваемом случае F(c0) 0 и F(b) > 0. Таким образом, с[с0, c1],а2=с0, b2 = с1. Аналогично находим другие приближения: с2=(с0+c1)/2и т.д. до выполнения условия (1.6).

Рис. 1.1. Метод деления отрезка пополам

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

Однако метод деления отрезка пополам довольно медленный. Вычислим число итераций N, требуемое для достижения точности ε. Для этого выясним, пользуясь (1.3), для каких kвыполнено условие (1.6), и возьмем в качестве N наименьшее из таких k. Окончательно получим

(1.7)

где Е(х) – целая часть числа х. Обычно для метода деления отрезка пополам N больше, чем для некоторых других методов, что не является препятствием к применению этого метода, если каждое вычисление значения функции F(x) несложно.

Итерационный процесс можно завершать и тогда, когда значение функции F(x) после k-й итерации станет меньшим по модулю ε, т.е.

(1.8)

Такое условие окончания итераций аналогично условию (2.24). Действительно, для уравнения (1.1) величина F(ck)есть невязка(см. разд. 2.2.2),полученная на k—йитерации.

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

Рис. 1.2. Алгоритм метода деления отрезка пополам

Содержание

Уточнение корней
Метод деления отрезка пополам (метод бисекций)
Метод бисекции
Метод бисекции
Метод бисекции
🎥 Видео

Видео:Метод половинного деления. ДихотомияСкачать

Уточнение корней

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

Рассмотрим некоторые итерационные методы решения нелинейных уравнений.

Видео:Метод половинного деления решение нелинейного уравненияСкачать

Метод деления отрезка пополам (метод бисекций)

Пусть дано уравнение/(х) = 0. Допустим, удалось найти такой отрезок [а, Ь], на котором расположено значение корня т. е. а ], на концах которой/(х) имеет противоположные знаки, т. е. содержит искомый корень, поэтому его принимают в качестве нового отрезка [х₀, Ь]. Вторую половину отрезка, на концах которого знак функции /(х) нс меняется, отбрасывают: в данном случае [а, х₀]. Отрезок [х₀, Ь] вновь делят пополам. Следующее приближение: Х] = (хо+ b) / 2. Вновь исследуют функцию /(х) на концах отрезка и отбрасывают отрезок [xi, Ь], т. к.ДхД > 0 и f 0.

Рис. 2.5. Метод деления отрезка пополам

Отрезок [х₀, х,], на концах которого функция имеет противоположные знаки j <x)> 0,/(х₀) х₂=(х₀ + х,)/2 и т. д. Итерационный процесс продолжают до тех пор, пока длина отрезка после п-й итерации не станет меньше некоторого заданного малого числа е (погрешности), т. е.

Тогда за искомое значение корня принимают полученное приближение х„: ?,=х„ и говорят, что решение уравнения найдено с точностью е. Пример 2.3. Найти корни уравнения

с точностью 8 = 0,1.

В результате процедуры отделения корней было получено три отрезка, содержащих действительные корни. Выберем отрезок [-3,-1] и определим корень уравнения, используя метод деления отрезка пополам.

Последовательность решения. Определяем знак функции на концах отрезка [-3,-1]:

Делим данный отрезок пополам:

Значение функции в этой точке:

У(—2) = —8 + 12 + 2 = 6

имеет положительное значение. Отбрасываем половину отрезка, на концах которого функция Дх) имеет положительные знаки, а именно — отрезок [-2, -1]. Полученный отрезок [-3, -2] делим пополам:

• /(-2,5) > 0, следовательно, отбрасываем отрезок [-2,5; -2], а отрезок [-3; -2,5] делим пополам:

• /(-2,75) 0. Следовательно, вновь полученный отрезок будет Проверим условие окончания расчетов по формуле (2.3*):

Таким образом, за искомое значение корня принимают значение:

На рис. 2.6 представлена блок-схема определения корня уравнения (2.1) методом деления отрезка пополам (бисекций).

Рис. 2.6. Блок-схема алгоритма метода деления отрезка пополам 2.2.2. Метод Ньютона (метод касательных)

Если известно начальное приближение к корню уравнения /(д’) = 0, то эффективным методом уточнения корней является метод Ньютона (метод касательных) 3.

Сформулируем достаточные условия сходимости метода Ньютона.

Пусть функцияУ(д’) имеет первую и вторую производные на отрезке [а, Ь]. Выполняется условие знакопеременности функции: /(я) • /(&) 0, можно построить следующую итерационную последовательность:

которая сходится к единственному на отрезке [а, 6] решению ?, уравне- нияУ(х) = 0.

В данном методе процесс поиска корня состоит в том, что в качестве приближений к корню принимаются значения х₀, Х, х₂ . точек пересечения касательной к кривой у=/(х) с осью абсцисс. Таким образом, геометрически метод Ньютона эквивалентен замене небольшой дуги кривой У = Л Х ) касательной. При этом необязательно задавать отрезок [а, 6], содержащий корень уравнения _Дх) = 0, а достаточно найти некоторое начальное приближение корня х=хо (рис. 2.7).

В качестве начального приближения выбирается х₀=а, для которого выполняется условие /(х₀) •/»(*о) > 0. Проведем касательную в точке Ло[хо,_Дхо)]. Первым приближением корня будет точка пересечения этой касательной с осью абсцисс х,. Через точку А[хьДхО] вновь проводим касательную, точка пересечения которой с осью Ох даст нам второе приближение корня х₂ и т. д.

На рис. 2.8 приведены возможные варианты выбора в качестве начального приближения правого или левого конца отрезка.

Вывод формулы Ньютона. Запишем уравнение касательной, проведенной к кривой y=j <x)в точке Ло[х₀,_Дх₀)]:

Найдем отсюда следующее приближение корня.

Принимаем х=х (у=0), тогда

Аналогично найдем следующие приближения корня, как точки пересечения с осью ОХ касательных, проведенных в точках А, А₂ и т. д. Формула Ньютона для (п+ 1)-го приближения будет иметь следующий вид:

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

При мер 2.4. Найти корни уравнения

На этапе отделения корней уравнения было выделено три интервала, на которых функция меняет знак, следовательно, уравнение имеет три действительных корня. Вычислим по методу Ньютона (касательных) значение корня на отрезке [4, 6]. Выберем начальное приближение таким образом, чтобы выполнялось условие Дх₀) •/»(*о) > 0.

Запишем первую и вторую производные функцииДт):

Вычислим значения Д,т₀) и f»(xо).

При

Следовательно, за начальное приближение можно принимать ,т₀ = 6. Найдем корень уравнения по Формуле (2.4) с точностью е = 0,001:

Таким образом, корнем данного уравнения с точностью е = 0,001 примем значение х=5,000.

Проверяем по формуле (2.7*) условие окончания вычислений:

Блок-схема алгоритма метода Ньютона приведена на рис. 2.9.

Рис. 2.9. Блок-схема метода Ньютона:

Хо — начальное приближение:

X— последовательное приближение (значение) корня

Видео:Метод Ньютона (метод касательных) Пример РешенияСкачать

Метод бисекции

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

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

Метод бисекции

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

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

Итерационная формула проста:

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

В качестве критерия останова берут один из следующих:

— значение функции на данной итерации стало меньше заданого ε.

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