41. Метод хорд и касательных Метод половинного деления




Скачать 63.74 Kb.
Название41. Метод хорд и касательных Метод половинного деления
Дата публикации30.08.2013
Размер63.74 Kb.
ТипДокументы
skachate.ru > Информатика > Документы
41. Метод хорд и касательных

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

Другие названия: метод бисекции, метод дихотомии (от греч. δίχα − на две части и τοµή − сечение). Метод половинного деления можно рассматривать как дальнейшее усовершенствование описанной выше процедуры поиска корня уравнения.

Отличие метода половинного деления состоит в том, что отрезок на каждом шаге разбивается не на любое произвольное число частей N, а делится только на две части, то есть N = 2. Графически процедура поиска корня уравнения f(x) методом половинного деления показана на рис . 4.



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

Метод включает следующие операции (рис. 5). Вначале на концах исходного отрезка [a, b], содержащего корень, вычисляют значения функции f(a) и f(b). Затем находят точку, делящую [a, b] на две равные части, по итерационной формуле xc=(a+b)/2 (6) и вычисляют значение функции f(xc). Далее по перемене знака функции выбирают ту половину [a, b], в которой расположен корень. Если знаки f(xc) и f(a) совпадают, то в дальнейшем полагают a = xc и f(a) = f(xc).

Если же, напротив, знаки f(xc) и f(a) различаются, а знаки f(xc) и f(b) совпадают, то полагают b = xc и f(b) = f(xc). В результате этих действий получают новый отрезок, содержащий корень. Этот отрезок имеет длину в два раза меньше, чем исходный.

Точно так же, как и в предыдущем случае, если очередное рассчитанное значение f(x) достаточно близко к нулю, вычисления прекращаются. Иначе процесс половинного деления продолжается.

В некоторых случаях для остановки итерационной процедуры используют условие малости полученного на очередном шаге отрезка, записывая его, например, как (7)

Приняв δ = 0,01, можно таким образом получить положение корня с точностью порядка одного процента. Метод половинного деления позволяет заметно ускорить поиск решения по сравнению с пошаговым поиском.

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

В то же время нетрудно подсчитать, что в методе половинного деления для получения аналогичного результата необходимо сделать 20 шагов, так как при N = 2 и K = 20 получается сужение в NK = 220 = =1048576 раз.




Рис.5 Алгоритм метода половинного деления

При этом расчет функции f(x) для этого потребуется провести лишь в N × 20 = 1 × 20 = 20 новых точках. В итоге объем и время вычислений по сравнению с ранее рассмотренной процедурой сокращается примерно в пятнадцать раз.

^ Метод хорд

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

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

(8)

С помощью хорды на отрезке [a,b] выбирается точка xс, в которой y(xc) = 0. Для этого подставим в (8) y(x) = y(xc) = 0 и получим итерационную формулу метода хорд:

(9)

Точка xc делит отрезок [a, b] на две части. Также как и в методе половинного деления из двух частей выбирается та, на краях которой функция f(x) имеет противоположные знаки. Далее описанный процесс повторяется многократно и может быть остановлен по условию (5) или (7). Процесс поиска корня методом хорд показан графически на рис. 6.



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

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

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

Этот метод в отличие от ранее рассмотренных не требует предварительно указывать интервал, в котором располагается корень уравнения. Для начала работы требуется задать лишь одну начальную точку x0, расположенную вблизи от предполагаемого корня. Направление поиска определяется из этой точки с помощью линейной экстраполяции f(x). Таким образом, при начале расчета из заданной точки x0 определяется точка x1, затем из точки x1 рассчитывается x2 и так далее. Продолжение этого процесса далее дает последовательность чисел x0, x1, x2, x3, …, xi, ... последовательно приближающихся к корню уравнения.

Для получения итерационной формулы метода Ньютона воспользуемся разложением функции f(x) в окрестности точки xi в ряд Тейлора:

(10)

где , и ‒ первая, вторая и третья производные от функции по .

Сократим (10), отбросив слагаемые, содержащие во второй и более высоких степенях. Тогда


Полагая далее, что в окрестностях xi имеется точка xi+1=xi+∆x, в которой функция равна нулю, получим линейное уравнение

из которого найдем xi+1: (11)


Рис. 7. Алгоритм метода

Ньютона


Это соотношение является итерационной формулой метода Ньютона.

Алгоритм метода Ньютона представлен на рис. 7.

Получаемые методом Ньютона точки xi образуют ряд чисел x0, x1, x2, x3, …, который сходится к точному решению, то есть к корню уравнения. Из (11) следует, что каждый шаг метода Ньютона требует большего объема вычислений чем, например, метод половинного деления, так как приходится находить значение не только функции f(x), но и ее производной. Несмотря на это метод Ньютона и его модификации широко используются на практике.

Это обусловлено, во-первых, тем, что он не требует задания отрезка [a, b], содержащего корень, а может стартовать от одной начальной точки.

Во-вторых, он имеет более высокую скорость сходимости, чем ранее рассмотренные методы.

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

Если на очередном шаге достигнута погрешность не более 0,5 то за пять-шесть итераций она уменьшится до величины порядка 2-64, что сопоставимо с погрешностью вычислений на ЭВМ. В методе половинного деления для достижения такой же погрешности количество итераций потребовалось бы увеличить более чем на порядок.
Рис. 8. Метод Ньютона и метод секущих

На рис. 8, а представлен ход решения методом Ньютона в графическом виде.

При использовании метода Ньютона следует учитывать ряд его особенностей. Одна из них состоит в необходимости правильного выбора начального приближения. Чтобы понять, как влияет выбор начальной точки на работу метода, попробуйте графически найти решение для рис. 8, начав его из точки x0 = a.

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

Другая проблема заключается в том, что производная f'(x) в (11) находится в знаменателе. Это означает, что f'(x) не должна обращаться в ноль, так как в противном случае итерационная формула перестает работать. Трудности могут возникнуть и в том случае, если f'(x) не равна нулю, но достаточно мала, вследствие чего результат деления f(x)/f'(x) может оказаться неприемлемо большим.

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

Похожие:

41. Метод хорд и касательных Метод половинного деления iconКонтрольная работа по курсу «Методы оптимизации»
Вычислить указанное минимальное или максимальное значение функции f(X) на отрезке [a,b], используя метод половинного деления: fmin(X),...
41. Метод хорд и касательных Метод половинного деления iconКонтрольная работа по курсу «Методы оптимизации»
Вычислить указанное минимальное или максимальное значение функции f(X) на отрезке [a,b], используя метод половинного деления: fmin(X),...
41. Метод хорд и касательных Метод половинного деления icon16. Численные методы решения систем конечных уравнений (метод итераций,...
Численные методы решения систем конечных уравнений (метод итераций, метод Ньютона)
41. Метод хорд и касательных Метод половинного деления iconРешение Для определения коэффициентов и в соответствии с методом...
Определить количество действительных корней уравнения, отделить эти корни и, применяя метод хорд и касательных, найти их приближенное...
41. Метод хорд и касательных Метод половинного деления icon«Моделирование территориальных систем»
Методы, используемые для анализа территориальной организации хозяйства: сравнительно-географический метод, статистический метод,...
41. Метод хорд и касательных Метод половинного деления iconОтчет по практике за I курс 2004-2005 учебный год
Реализовать демонстрационный режим решения нелинейных уравнений четырьмя способами: методом дихотомии, методом Ньютона, методом хорд...
41. Метод хорд и касательных Метод половинного деления iconКонцепции современного естествознания
Метод единственного сходства, метод единственного различия, соединенный метод сходства и различия, метод сопутствующих изменений,...
41. Метод хорд и касательных Метод половинного деления iconМетод административного права 11
Совокупность норм, объединенных в правовые институты регулирующих определенную сферу общественных отношений, образует отрасль права....
41. Метод хорд и касательных Метод половинного деления iconЛинейное программирование
Ранспортная задача: общая постановка задачи, математическая модель, типы задачи, сведение задачи открытого типа к закрытому. Методы...
41. Метод хорд и касательных Метод половинного деления icon«брянский государственный технический университет» Кафедра «Компьютерные технологии и системы»
Метод условного градиента. Методы сведения задач с ограничениями к задачам безусловной оптимизации. Методы внешних и внутренних штрафных...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница