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

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

Метод половинного деления. Дихотомия

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

Один из простейших методов нахождения корней нелинейных уравнений состоит в следующем. Допустим, что нам удалось найти отрезок [а, 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. Каждый такой шаг называется итерацией.

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

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

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

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

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

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

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

Отрезок [х0, х,], на концах которого функция имеет противоположные знаки j <x)> 0,/(х0) х2=(х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.

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

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

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

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

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

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

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

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

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

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

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

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

При мер 2.4. Найти корни уравнения В методе бисекции нахождения корней нелинейных уравнений за начальное приближение корня принимают

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Видео:Метод простых итераций пример решения нелинейных уравненийСкачать

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

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

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

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

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

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

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

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

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

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

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

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

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

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

🔥 Видео

Решение нелинейного уравнения методом половинного деления (программа)Скачать

Решение нелинейного уравнения методом половинного деления (программа)

Алгоритмы. Нахождение корней уравнений методом деления отрезка пополам.Скачать

Алгоритмы. Нахождение корней уравнений методом деления отрезка пополам.

10 Численные методы решения нелинейных уравненийСкачать

10 Численные методы решения нелинейных уравнений

14 Метод половинного деления Ручной счет Численные методы решения нелинейного уравненияСкачать

14 Метод половинного деления Ручной счет Численные методы решения нелинейного уравнения

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

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

8 Метод половинного деления Calc Excel Численные методы решения нелинейного уравненияСкачать

8 Метод половинного деления Calc Excel Численные методы решения нелинейного уравнения

Метод половинного деленияСкачать

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

1.1 Решение нелинейных уравнений метод деления отрезка пополам (бисекций) Мathcad15Скачать

1.1 Решение нелинейных уравнений метод деления отрезка пополам (бисекций) Мathcad15

15 Метод Ньютона (Метод касательных) Ручной счет Численные методы решения нелинейного уравненияСкачать

15 Метод Ньютона (Метод касательных) Ручной счет Численные методы решения нелинейного уравнения

Метод хордСкачать

Метод хорд

Численное решение уравнений, урок 3/5. Метод хордСкачать

Численное решение уравнений, урок 3/5. Метод хорд

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

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

Решение нелинейного уравнения методом простых итераций (программа)Скачать

Решение нелинейного уравнения методом простых итераций (программа)

Методы решения систем нелинейных уравнений. Метод Ньютона. Численные методы. Лекция 14Скачать

Методы решения систем нелинейных уравнений. Метод Ньютона. Численные методы. Лекция 14

1,2 Решение нелинейных уравнений методом хордСкачать

1,2 Решение нелинейных уравнений методом хорд

Метод секущихСкачать

Метод секущих
Поделиться или сохранить к себе: