Методом половинного деления в последовательности чисел. Метод половинного деления. Комбинация метода хорд и метода половинного деления

Иванов Иван

При прохождении темы численные методы учащиеся уже умеют работать с электронными таблицами и составлять программы на языке паскаль. Работа комбинированного характера.Расчитана на 40 минут. Цель работы повторить и закрепить навыки паботы с программами EXCEL, ABCPascal. Материал содержит 2 файла. Один содержит теоретический материал, так как он и предлагается ученику. Во 2-м файле пример работы ученика Иванова Ивана.

Скачать:

Предварительный просмотр:

Решение уравнений

Аналитическое решение некоторых уравнений, содержащих, например тригонометрические функции может быть получено лишь для единичных частных случаев. Так, например, нет способа решить аналитически даже такое простое уравнение, как cos x=x

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

Приближённое нахождение обычно состоит из двух этапов:

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

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

Мы будем рассматривать решения уравнений вида f(x)=0. Функция f(x) определена и непрерывна на отрезке [а.Ь]. Значение х 0 называется корнем уравнения если f(х 0 )=0

Для отделения корней будем исходить из следующих положений:

• Если f(a)* f(b] \a, b\ существует, по крайней мере, один корень
• Если функция y = f(x) непрерывна на отрезке , и f(a)*f(b) и f "(x) на интервале (a, b) сохраняет знак, то внутри отрезка [а, b] существует единственный корень уравнения

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

Метод дихотомии

Для уточнения корня разделим отрезок [а, b] пополам и вычислим значение функции f(х) в точке x sr =(a+b)/2. Выбираем ту из половин или , на концах которых функция f(x) имеет противоположные знаки.. Продолжаем процесс деления отрезка пополам и проводим то же рассмотрение до тех пор, пока. длина станет меньше заданной точности . В последнем случае за приближённое значение корня можно принять любую точку отрезка (как правило, берут его середину). Алгоритм высокоэффективен, так как на каждом витке (итерации) интервал поиска сокращается вдвое; следовательно, 10 итераций сократят его в тысячу раз. Сложности могут возникнуть с отделением корня у сложных функций.

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

ПРИМЕР : Определим графически корень уравнения . Пусть f1(х) = х , a и построим графики этих функций. (График). Корень находится на интервале от 1 до 2. Здесь же уточним значение корня с точностью 0,001(на доске шапка таблицы)

Алгоритм для программной реализации

1. а:=левая граница b:= правая граница
2. m:= (a+b)/2 середина
3. определяем f(a) и f(m)
4. если f(a)*f(m)
5. если (a-b)/2>e повторяем, начиная с пункта2
   

Метод хорд.

Точки графика функции на концах интервала соединяются хордой. Точка пересечения хорды и оси Ох (х*) и используется в качестве пробной. Далее рассуждаем так же, как и в предыдущем методе: если f(x a ) и f(х*) одного знака на интервале, нижняя граница переносится в точку х*; в противном случае – переносим верхнюю границу. Далее проводим новую хорду и т.д.

Осталось только уточнить, как найти х*. По сути, задача сводится к следующей: через 2 точки с неизвестными координатами (х 1 , у 1 ) и (х 2 , у 2 ) проведена прямая; найти точку пересечения этой прямой и оси Ох.

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

В точке пересечения этой прямой и оси Ох у=0, а х=х*, то есть

Откуда

процесс вычисления приближённых значений продолжается до тех пор, пока для двух последовательных приближений корня х„ и х п _1 не будет выполняться условие abs(xn-x n-1 ) е - заданная точность

Сходимость метода гораздо выше предыдущего

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

Уравнения для самостоятельного решения: (отрезок в excel ищем самостоятельно)

1. sin(x/2)+1=x^2 (х=1,26)

1. x-cosx=0 (х=0,739)

1. x^2+4sinx=0 (х=-1,933)

1. x=(x+1) 3 (х=-2,325)

где функция 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), если найден интервал, на котором она изменяет знак. В том случае, когда корни не отделены, будет найден один из корней уравнения. Метод всегда сходится, но скорость сходимости является небольшой, так как за одну итерацию точность увеличивается примерно в два раза. Поэтому на практике метод половинного деления обычно применяется для грубого нахождения корней уравнения, поскольку при повышении требуемой точности значительно возрастает объем вычислений.

Пусть 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 используется метод Лагерра.

ВВЕДЕНИЕ 4

1. ПОСТАНОВКА ЗАДАЧИ 5

2. ВЫБОР И ОПИСАНИЕ МЕТОДОВ РЕШЕНИЯ 6

2.1. МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ 6

2.2. МЕТОД ХОРД 9

2.3. МЕТОД НЬЮТОНА (МЕТОД КАСАТЕЛЬНЫХ) 12

3 .СООТВЕТСТВИЕ МЕЖДУ ПЕРЕМЕННЫМИ, ПРИНЯТЫМИ ПРИ ОПИСАНИИ ЗАДАЧИ И В ПРОГРАМЕ 15

4. СТРУКТУРНАЯ СХЕМА ПРОГРАММ И ЕЕ ОПИСАНИЕ 18

5. ЛИСТИНГ ПРОГРАМЫ 26

6. КОНТРОЛЬНЫЙ ПРИМЕР И АНАЛИЗ РЕЗУЛЬТАТА 27

7. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ 32

ЗАКЛЮЧЕНИЕ 33

СПИСОК ЛИТЕРАТУРЫ 34

ПРИЛОЖЕНИЯ 35

ПРИЛОЖЕНИЕ А 36

ПРИЛОЖЕНИЕ Б. 38

ПРИЛОЖЕНИЕ Д. 39

ВВЕДЕНИЕ

Паскаль − один из наиболее распространенных процедурно-ориентированных языков программирования 80 - 90-х годов, имеет свою достаточно интересную историю, начало которой положило объявление в 1965 г. конкурса по созданию нового языка программирования - преемника Алгола - 60. Участие в конкурсе принял швейцарский ученый Николаус Вирт, который работал на факультете информатики Стэндфордского университета. Проект, предложенный им, был отвергнут комиссией в 1967 г. Но Вирт не прекратил работу. Вернувшись в Швейцарию, совместно с сотрудниками Швейцарского федерального института технологии в Цюрихе, он уже в 1968 г. разработал новую версию языка Паскаль, названного так в честь великого французского математика и механика Блеза Паскаля, создавшего в 1642 г. первую счетную машину. В 1971 г. Н. Вирт выпустил описание своего языка, а в 1975 г. было разработано руководство для пользователей версии Паскаля, которая практически легла в основу стандарта языка. Но стандарт языка появился только в 1982 г.

Предназначенный для обучения, язык оказался очень простым и одновременно строгим. Однако вскоре выяснилось, что он также является достаточно эффективным в самых различных приложениях. Pascal поддерживает самые современные методологии проектирования программ (нисходящее, модульное проектирование, структурное программирование). В связи с этим появились многочисленные реализации языка для разных машинных архитектур и наиболее удачной и популярной оказалась разработка фирмы Borland International для персональных IBM - совместимых ЭВМ. Эта реализация языка получила название Turbo Pascal (Турбо Паскаль) и имеет уже несколько версий.

Turbo Pascal представляет собой систему программирования, включающую в себя текстовый редактор, компилятор, компоновщик, загрузчик, отладчик, файловую систему, системную библиотеку, справочную систему. Все эти компоненты объединены в интегрированную среду с многооконным интерфейсом и развитой системой меню, что обеспечивает высокую производительность труда программиста при создании программ производственного, научного и коммерческого назначения.

1. ПОСТАНОВКА ЗАДАЧИ

Написать программу на языке программирования Pascal, выполняющую решение нелинейного уравнения. Результат работы программы должен выводиться на экран и в файл.

В программе реализовать следующее меню:

1-Ввести данные из файла

2-Ввести данные с клавиатуры

Отладить программу на уравнении f(x)=x 2 -x-6 с точностью 0,001

2. ВЫБОР И ОПИСАНИЕ МЕТОДОВ РЕШЕНИЯ

Процесс нахождения приближенного значения корней уравнения можно подразделить на два этапа 1) отделение корней; 2) уточнение корней до заданной степени точности. Корень ξ считается отделённым на отрезке , если на этом отрезке уравнение

: метод половинного деления, Ньютона

2.1. МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ

Пусть дано уравнение f (x ) = 0, где f (х ) – непрерывная функция. Требуется найти корень этого уравнения ξ с точностью до ε, где е – некоторое положительное достаточно малое число.

Будем считать, что корень ξ отделен и находится на отрезке [а , b ], т. е. имеет место неравенство а ≤ ξ ≤ b . Числа а и b – приближенные значения корня ξ соответственно с недостатком и с избытком. Погрешность этих приближений не превышает длины отрезка b – а . Если b – а ≤ε, то необходимая точность вычислений достигнута, и за приближенное значение корня ξ можно принять либо а , либо b . Но если b – а > ε, то требуемая точность вычислений не достигнута и необходимо сузить интервалов котором находится корень ξ, т. е. подобрать такие числа а и b , чтобы выполнялись неравенства a b и . При вычисления следует прекратить и за приближенное значение корня с точностью до ε принять либо а , либо b . Следует отметить, что значение корня будет более точным, когда за приближенное значение корня приняты не концы отрезка а и b , а середина этого отрезка, т.е. . Погрешность в этом случае не превышает величины
.

Метод проб . Пусть дано уравнение f (x ) = 0 [f (x ) – непрерывная функция] и корень ε отделен на отрезке [а , b ], т. е. f (а ) ∙ f (b ) b – а > ε. Требуется найти значение корня ξ с точностью до ε (рис. 2.1)

Принцип решения уравнения типа y=f(x) методом проб

Принцип решения уравнения типа y=f(x) методом половинного деления

На отрезке [a , b ] выберем произвольным образом точку a 1 , которая разделит его на два отрезка и . Из этих двух отрезков следует выбрать тот, на концах которого функция принимает значения, противоположные по знаку. В нашем примере f (а ) ∙ f (a 1) > 0, f (a 1) ∙ f (b ) a 1 ,b ]. Затем на этом суженом отрезке опять произвольным образом возьмем точку а 2 и найдем знаки произведений f (a 1) ∙ f (a 2) и f (a 2) ∙ f (b ). Так как f (a 2)× f (b ) a 2 , b ]. Этот процесс продолжаем до тех пор, пока длина отрезка, на котором находится корень, не станет меньше ε. Корень ξ получим как среднее арифметическое концов найденного отрезка, причем погрешность корня не превышает ε/2.

Метод проб в таком виде на ЭВМ не применяется. Для составления программ и расчетов на ЭВM метод проб применяется в виде так называемого метода половинного деления .

Пусть корень ξ уравнения f (х ) = 0 отделен и находится на отрезке [a , b ], т.е. f (a ) ∙ f (b ) b – а > ε [здесь f (х) – непрерывная функция]. Как и ранее, возьмем на отрезке [a , b ] промежуточную точку, однако не произвольным образом, а так, чтобы она являлась серединой отрезка [a , b ], т. е. с = (а + b )/2. Тогда отрезок [a , b ] точкой с разделится на два равных отрезка [а , с ] и [с , b ], длина которых равна (b – а )/2 (рис. 2.2). Если f (с ) = 0, то с – точный корень уравнения f (х ) = 0. Если же f (с ) ≠ 0, то из двух образовавшихся отрезков [a , с ] и [с , b ] выберем тот, на концах которого функция f (х) принимает значения противоположных знаков; обозначим его [a l , b 1 ]. Затем отрезок [a l , b 1 ] также делим пополам и проводим те же рассуждения. Получим отрезок [а 2 , b 2 ], длина которого равна (b – а )/2 2 . Процесс деления отрезка пополам производим до тех пор, когда на каком-то n-м этапе либо середина отрезка будет корнем уравнения (случай, весьма редко встречающийся на практике), либо будет получен отрезок [a n , b n ] такой, что b n – а n = (b – а)/2 n ≤ ε и а n ≤ ξ ≤ b n (число n указывает на количество проведенных делений). Числа а n и b n – корни уравнения f (х ) = 0 с точностью до ε. За приближенное значение корня, как указывалось, выше, следует взять ξ = (a n + b n)/2, причем погрешность не превышает (b – а )/2 n +1 .

2.2. МЕТОД ХОРД

Метод хорд является одним из распространенных методов решения алгебраических и трансцендентных уравнений. В литературе он также встречается под названиями «метода ложного положения» (regula falsi), «метода линейного интерполирования» и «метода пропорциональных частей».

Пусть дано уравнение f(х) = 0, где f (х) – непрерывная функция, имеющая в интервале [а, b] производные первого и второго порядков. Корень считается отделенным и находится на отрезке [а, b], т.е. f(a)-f (b)

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

Ранее мы рассмотрели четыре случая расположения дуги кривой, учитывая значения первой и второй производных.

Рассмотрим случаи, когда первая и вторая производные имеют одинаковые знаки, т. е, f"(х) ∙ f"" (х) > 0.

Пусть, например, f(a) 0, f"(х) > 0, f""(х) > 0 (рис. 3.18, а). График функции проходит через точки А 0 (a; f(a)), В(b; f(b))- Искомый корень уравнения f(х) = 0 есть абсцисса точки пересечения графика функции у = f(х) с осью Ох. Эта точка нам неизвестна, но вместо нее мы возьмем точку x 1 пересечения хорды А и В с осью Ох. Это и будет приближенное значение корня.

Уравнение хорды, проходящей через точки А 0 и В, имеет вид

Найдем значение х = х 1 , для которого у = 0:

Эта формула носит название формулы метода хорд. Теперь корень ξ находится внутри отрезка . Если значение корня х 1 нас не устраивает, то его можно уточнить, применяя метод хорд к отрезку [х 1 , b].

Соединим точку А 1 (x 1 ; f (x 1) с точкой В (b; f (b)) и найдем х 2 – точку пересечения хорды А 1 В с осью Ох:

Продолжая этот процесс, находим

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

По приведенным выше формулам вычисляются корни и для случая, когда f(а) > 0, f(b)

Теперь рассмотрим случаи, когда первая и вторая производные имею разные знаки, т.е. f"(x) ∙ f"(x)

Пусть, например, f(a) > 0, f(b) 0 (рис. 3.19, а). Соединим точки A (a; f (а)) и В 0 (b; f (b)) и запишем уравнение хорды, проходящей через А и B 0:

Найдем х 1 , как точку пересечения хорды с осью Ох, полагая у = 0:

Корень ξ теперь заключен внутри отрезка . Применяя меч од хорд к отрезку [а, x 1 ], получимМетоды решения нелинейного уравненияЛабораторная работа >> Математика

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

Методы компьютерных вычислений и их приложение к физическим задачам

Методичка >> Информатика

2) Умножение и деление приближенных чисел Очевидно, ... Следовательно, при умножении и делении приближенных чисел необходимо принимать... метод Гаусса-Кристоффеля (вычисление несобственных интегралов) и метод Маркова. Метод прямоугольников. Различают метод ...

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

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

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

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

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

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

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

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

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

Задача

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

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

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

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

Мы заранее можем указать «вилку» для угла: 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)=0. Его можно было бы назвать методом артиллерийской пристрелки. Но математики называют его методом половинного деления.

Алгоритм

1) Найдем середину отрезка : c=(a+b)/2;

2) Вычислим значения функции в точках a и c и найдем произведение полученных значений: d=f(c)?f(a);

3) Если d>0, то теперь точкой a станет c: a=c; Если d<0, то точкой b станет c: b=c;

4) Вычислим разность a и b, сравним ее с точностью?: если |a-b|> ?, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;