No Image

Решение уравнений методом деления отрезка пополам

СОДЕРЖАНИЕ
389 просмотров
10 марта 2020

Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.

Содержание

Обоснование [ править | править код ]

Алгоритм основан на следующем следствии из теоремы Больцано — Коши:

Пусть непрерывная функция f ( x ) ∈ C ( [ a , b ] ) <displaystyle f(x)in mathrm ([a,;b])> , тогда, если s i g n ( f ( a ) ) ≠ s i g n ( f ( b ) ) <displaystyle sign(f(a))
eq sign(f(b))> , то ∃ c ∈ [ a , b ] : f ( c ) = 0 <displaystyle exists cin [a,;b]:;f(c)=0> .

Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается.

Точность вычислений задаётся одним из двух способов:

  1. ε f ( x ) <displaystyle varepsilon _>по оси y <displaystyle y>, что ближе к условию f ( x ) = 0 <displaystyle f(x)=0>из описания алгоритма; или
  2. ε x <displaystyle varepsilon _>, по оси x <displaystyle x>, что может оказаться удобным в некоторых случаях.

Процедуру следует продолжать до достижения заданной точности.

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

Описание алгоритма [ править | править код ]

Задача заключается в нахождении корней нелинейного уравнения

f ( x ) = 0. ( 1 ) <displaystyle f(x)=0.qquad (1)>

Для начала итераций необходимо знать отрезок [ x L , x R ] <displaystyle [x_,x_]> значений x <displaystyle x> , на концах которого функция принимает значения противоположных знаков.

Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:

f ( x L ) ⋅ f ( x R ) 0 , ( 2.1 ) <displaystyle f(x_)cdot f(x_)

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

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

s i g n ( f ( x L ) ) ≠ s i g n ( f ( x R ) ) , ( 2.2 ) <displaystyle sign(f(x_))
eq sign(f(x_)),qquad (2.2)>

так как одна операция сравнения двух знаков двух чисел требует меньшего времени, чем две операции: умножение двух чисел (особенно с плавающей запятой и двойной длины) и сравнение результата с нулём. При данном сравнении, значения функции f ( x ) <displaystyle f(x)> в точках x L <displaystyle x_> и x R <displaystyle x_> можно не вычислять, достаточно вычислить только знаки функции f ( x ) <displaystyle f(x)> в этих точках, что требует меньшего машинного времени.

Из непрерывности функции f ( x ) <displaystyle f(x)> и условия (2.2) следует, что на отрезке [ x L , x R ] <displaystyle [x_,x_]> существует хотя бы один корень уравнения (в случае не монотонной функции f ( x ) <displaystyle f(x)> функция имеет несколько корней и метод приводит к нахождению одного из них).

Найдём значение x <displaystyle x> в середине отрезка:

x M = ( x L + x R ) / 2 , ( 3 ) <displaystyle x_=(x_+x_)/2,qquad (3)>

в действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:

x D = ( x R − x L ) , <displaystyle x_=(x_-x_),>

а в цикле вычисляют длину очередных новых отрезков по формуле: x D = x D / 2 <displaystyle x_=x_/2> и новую середину по формуле:

x M = x L + x D . <displaystyle x_=x_+x_.>

Вычислим значение функции f ( x M ) <displaystyle f(x_)> в середине отрезка x M <displaystyle x_> :

Читайте также:  Шрифты для названий улиц

  • Если f ( x M ) = 0 <displaystyle f(x_)=0>или, в действительных вычислениях, | f ( x M ) | ≤ ε f ( x ) <displaystyle |f(x_)|leq varepsilon _>, где ε f ( x ) <displaystyle varepsilon _>— заданная точность по оси y <displaystyle y>, то корень найден.
  • Иначе f ( x M ) ≠ 0 <displaystyle f(x_)
    eq 0>или, в действительных вычислениях, varepsilon _>"> | f ( x M ) | > ε f ( x ) <displaystyle |f(x_
    )|>varepsilon _>varepsilon _<>"/> , то разобьём отрезок [ x L , x R ] <displaystyle [x_,x_]>на два равных отрезка: [ x L , x M ] <displaystyle [x_,x_]>и [ x M , x R ] <displaystyle [x_,x_]>.

Теперь найдём новый отрезок, на котором функция меняет знак:

  • Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, f ( x L ) ⋅ f ( x M ) 0 <displaystyle f(x_)cdot f(x_) или s i g n ( f ( x L ) ) ≠ s i g n ( f ( x M ) ) <displaystyle sign(f(x_))
    eq sign(f(x_))>, то, соответственно, корень находится внутри левого отрезка [ x L , x M ] <displaystyle [x_
    ,x_]>. Тогда возьмём левый отрезок присвоением x R = x M <displaystyle x_=x_>, и повторим описанную процедуру до достижения требуемой точности ε f ( x ) <displaystyle varepsilon _>по оси y <displaystyle y>.
  • Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке, f ( x M ) ⋅ f ( x R ) 0 <displaystyle f(x_)cdot f(x_) или s i g n ( f ( x M ) ) ≠ s i g n ( f ( x R ) ) <displaystyle sign(f(x_))
    eq sign(f(x_))>, то, соответственно, корень находится внутри правого отрезка [ x M , x R ] <displaystyle [x_
    ,x_]>. Тогда возьмём правый отрезок присвоением x L = x M <displaystyle x_=x_>, и повторим описанную процедуру до достижения требуемой точности ε f ( x ) <displaystyle varepsilon _>по оси y <displaystyle y>.

За количество итераций N <displaystyle N> деление пополам осуществляется N <displaystyle N> раз, поэтому длина конечного отрезка в 2 N <displaystyle 2^> раз меньше длины исходного отрезка.

Существует похожий метод, но с критерием останова вычислений ε x <displaystyle varepsilon _> по оси x <displaystyle x> [1] , в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси x <displaystyle x> : varepsilon _>"> ( x R − x L ) > ε x <displaystyle (x_-x_)>varepsilon _> varepsilon _"/> . В этом методе отрезок на оси x <displaystyle x> может достичь заданной величины ε x <displaystyle varepsilon _> , а значения функций f ( x ) <displaystyle f(x)> (особенно крутых) на оси y <displaystyle y> могут очень далеко отстоять от нуля, при пологих же функциях f ( x ) <displaystyle f(x)> этот метод приводит к большому числу лишних вычислений.

В дискретных функциях x L , x M <displaystyle x_,x_> и x R <displaystyle x_> — это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность ( x R − x L ) <displaystyle (x_-x_)> не может быть меньше ε x = 1 <displaystyle varepsilon _=1> .

Псевдокод [ править | править код ]

  • xn — начало отрезка по х;
  • xk — конец отрезка по х;
  • xi — середина отрезка по х;
  • epsy — требуемая точность вычислений по y (заданное приближение интервала [xn; xk] : xk — xn к нулю).

Тогда алгоритм метода бисекции можно записать в псевдокоде следующим образом:

Поиск значения корня монотонной дискретной функции [ править | править код ]

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

Читайте также:  Canon mf5700 драйвер windows 10 x64

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

Если знаки значений массива массив[леваяГраница] и массив[середина] противоположны, то приближение к корню ищут в левой половине массива, то есть значением праваяГраница становится середина и на следующей итерации исследуется только левая половина массива. Если знаки значений массив[леваяГраница] и массив[середина] одинаковы, то осуществляется переход к поиску приближения к корню в правой половине массива, то есть значением переменной леваяГраница становится середина и на следующей итерации исследуется только правая половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.

Например, если длина массива равна 1023, то после первого сравнения область сужается до 511 элементов, а после второго — до 255. Т.о. для поиска приближения к корню в массиве из 1023 элементов достаточно 10 проходов (итераций).

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

Суть метода в следующем:

(6.4)

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

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

(6.5)

или длина отрезка [a,b] на i-ой итерации

не станет меньше по модулю некоторого заданного малого числа.

6.2.2. Метод пропорциональных частей Метод хорд

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

выпукла вниз выпукла вверх

Для точки пересечения хорды с осью на первой итерации координаты х=х1 и у=0.

Далее рассматривая отрезки [a1], [х1,b], оставляем тот из них, для которого выполняется теорема 1, второй при этом отбрасываем.

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

Для рассмотренного рисунка видно, что неподвижным на всех итерациях является конец b отрезка [a,b].

выпукла вниз выпукла вверх

(6.6)

Для случая 2 (неподвижен конец а)

(6.7)

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

– неподвижен тот конец, для которого знак функции совпадает со знаком ее второй производной.

Естественно при этом требуется вычислить значении

Читайте также:  Как привязать аккаунт в инстаграм к facebook

При использовании этих формул условие окончания вычислений

6.2.3. Метод Ньютона. Метод касательных

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

Уравнение касательной по формуле Тейлора

Для точки пересечения касательной с осью на первой итерации координаты х=х1, у=0.

Далее проверяем значения функции на концах отрезка [a1], [х1,b] и оставляем тот из концов отрезка, для которого выполняется теорема 1.

На рисунке 6.3 видно, что для данного поведения функции конец а отрезка [a,b] остается неподвижным.

На рисунке 6.4 неподвижным остается конец b.

Таким образом, также как и для метода хорд, можно написать формулу, связывающую между собой два соседних приближения корня

(6.8)

При этом в качестве х принимается тот из концов отрезка [a,b], для которого выполняется условие: значение функции и значение второй производной одинаковы по знаку

Из анализа расчетной формулы метода Ньютона следует, что

должно быть ,

на каждой итерации объем вычислений больший, чем в рассмотренных ранее методах дихотомии и хорд, так как требуется вычислить не только , (6.9)

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

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

Деление отрезка пополам (метод дихотомии) — это численный метод нахождения (одного) решения x (с заданной точностью ε) нелинейного уравнения вида f(x)=0.

Содержание

[править] Описание метода

Суть метода деления отрезка пополам состоит в разбиении отрезка [a,b] (при условии f(a)f(b) [править] Алгоритм решения

Входные данные: f(x), a, b, ε.

Выходные данные: x.

Значение x является решением с заданной точностью ε нелинейного уравнения вида f(x)=0.

Если f(x)=0, то x — точное решение.

[править] Методы решения уравнений:

  • Комбинированный метод;
  • Метод итераций;
  • Метод касательных;
  • Метод хорд;
  • Универсальный метод итераций.
  • Для решения систем нелинейных уравнений используется метод Ньютона.

[править] Численные методы:

[править] Литература

  • Демидович Б. П., Марон И. А. Основы вычислительной математики — М.: Наука, 1970.
Персональные инструменты
Пространства имён
Варианты
Просмотры
Действия
Поиск
Навигация
Инструменты
  • Последнее изменение этой страницы: 19:49, 1 декабря 2018.
  • К этой странице обращались 22 888 раз.

Текст страницы доступен по условиям лицензии GNU Free Documentation License. Материалы могут быть скопированы при условии указания активной ссылки на источник копирования в теле статьи (на той же странице). В отдельных случаях могут действовать условия лицензии Creative Commons Attribution-ShareAlike (CC BY-SA 3.0), информацию об этом можно просмотреть на странице обсуждения или в истории правок. В частности, условия лицензии CC BY-SA 3.0 действуют в отношении статей, перенесенных из Википедии (указание на факт переноса всегда есть в истории правок статьи).

  • Политика конфиденциальности
  • Описание Циклопедии
  • Отказ от ответственности
Комментировать
389 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock
detector